Uniform Value and Decidability in Ergodic Blind Stochastic Games
- 10 November 2026
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Abstract
We study a class of two-player zero-sum stochastic games known as blind stochastic games, where players neither observe the state nor receive any information about it during the game. A central concept for analyzing long-duration stochastic games is the uniform value. A game has a uniform value v if for every [Formula: see text], Player 1 (resp., Player 2) has a strategy such that, for all sufficiently large n, his average payoff over n stages is at least [Formula: see text] (resp., at most [Formula: see text]). Prior work has shown that the uniform value may not exist in general blind stochastic games. To address this, we introduce a subclass called ergodic blind stochastic games, defined by imposing an ergodicity condition on the state transitions. For this subclass, we prove the existence of the uniform value and provide an algorithm to approximate it, establishing the decidability of the approximation problem. Notably, this decidability result is novel even in the single-player setting of Partially Observable Markov Decision Processes (POMDPs). Furthermore, we show that no algorithm can compute the uniform value exactly, emphasizing the tightness of our result. Finally, we establish that the uniform value is independent of the initial belief. Funding: This research was supported by the French Association Nationale de la Recherche et de la Technologie (ANRT) under the French CIFRE Ph.D. program [Grant CIFRE 2022/0513], through a collaboration between Paris-Dauphine University-PSL and NyxAir (France), by the French Agence Nationale de la Recherche (ANR) under [Grants ANR-21-CE40-0020 (CONVERGENCE project) and ANR-17-EURE-0010 (Investissements d’Avenir program)], by the European Research Council (ERC) under [Grant ERC CoG 863818 (ForM-SMArt)], and by the Austrian Science Fund (FWF) under [Grant 10.55776/COE12].This publication has 42 references indexed in Scilit:
- Stochastic Games with Signals2016
- Deciding the Value 1 Problem for $\sharp$ -acyclic Partially Observable Markov Decision ProcessesLecture Notes in Computer Science, 2014
- Probabilistic Automata with Isolated Cut-PointsLecture Notes in Computer Science, 2013
- Probabilistic Automata on Infinite Words: Decidability and Undecidability Results2010
- Stochastic Games and Stationary Strategies2003
- Optimal Average Value Convergence in Nonhomogeneous Markov Decision ProcessesJournal of Mathematical Analysis and Applications, 1993
- Recurrence conditions for Markov decision processes with Borel state space: A surveyAnnals of Operations Research, 1991
- Stochastic gamesInternational Journal of Game Theory, 1981
- ber die analytischen Methoden in der WahrscheinlichkeitsrechnungMathematische Annalen, 1931
- Zur Theorie der GesellschaftsspieleMathematische Annalen, 1928