Playing Against a Stationary Opponent

• 成果类型: Article; Early Access
• 署名作者: Grand-Clement, Julien; Vieille, Nicolas
• 署名单位: Hautes Etudes Commerciales (HEC) Paris; Hautes Etudes Commerciales (HEC) Paris
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2025.0904
• 发表日期: 2026-07-13
• 关键词: Stochastic games; Blackwell optimality; robust Markov decision processes; repeated games; stochastic games; equilibria

摘要

This paper investigates properties of Blackwell s-optimal strategies in zero-sum stochastic games when the adversary is restricted to stationary strategies, motivated by applications to robust Markov decision processes. For a class of absorbing games (including generalized Big Match games), we show that Markovian Blackwell s-optimal strategies may fail to exist, yet we prove the existence of Blackwell s-optimal strategies that can be implemented by a two-state automaton whose internal transitions are independent of actions. For more general absorbing games, however, there need not exist Blackwell s-optimal strategies that are independent of the adversary's decisions. Our findings provide new insights into the properties of optimal policies for robust Markov decision processes.