Playing against a stationary opponent
Preprint
Abstract
This paper investigates properties of Blackwell $ε$-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, we show that Markovian Blackwell $ε$-optimal strategies may fail to exist, yet we prove the existence of Blackwell $ε$-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 $ε$-optimal strategies that are independent of the adversary's decisions. Our findings point to a contrast between absorbing games and generalized Big Match games, and provide new insights into the properties of optimal policies for robust Markov decision processes.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Robust Markov Decision Processes: Beyond RectangularityMathematics of Operations Research, 2023
- A Continuous Time Approach for the Asymptotic Value in Two-Person Zero-Sum Repeated GamesSIAM Journal on Control and Optimization, 2012
- Explicit formulas for repeated games with absorbing statesInternational Journal of Game Theory, 2009
- Absorbing Games with Compact Action SpacesMathematics of Operations Research, 2009
- Robust Dynamic ProgrammingMathematics of Operations Research, 2005
- Three-Player Absorbing GamesMathematics of Operations Research, 1999
- Finitely Repeated Games with Finite AutomataMathematics of Operations Research, 1998
- Repeated games with absorbing states and no signalsInternational Journal of Game Theory, 1992
- Stochastic games have a valueProceedings of the National Academy of Sciences, 1982
- Repeated Games with Absorbing StatesThe Annals of Statistics, 1974