Uniform Value and Decidability in Ergodic Blind Stochastic Games

References

• [1] Alden JM, Smith RL (1992) Rolling horizon procedures in nonhomogeneous Markov decision processes. Oper. Res. 40(3-supplement-2):S183–S194.Link, Google Scholar
• [2] Arapostathis A, Borkar VS, Fernández-Gaucherand E, Ghosh MK, Marcus SI (1993) Discrete-time controlled Markov processes with average cost criterion: A survey. SIAM J. Control Optim. 31(2):282–344.Crossref, Google Scholar
• [3] Baier C, Gröβer M, Bertrand N (2012) Probabilistic ω-automata. J. ACM 59(1):1–52.Crossref, Google Scholar
• [4] Bean JC, Smith RL, Lasserre JB (1990) Denumerable state nonhomogeneous Markov decision processes. J. Math. Anal. Appl. 153(1):64–77.Crossref, Google Scholar
• [5] Bewley T, Kohlberg E (1976) The asymptotic theory of stochastic games. Math. Oper. Res. 1(3):197–208.Link, Google Scholar
• [6] Chadha R, Sistla AP, Viswanathan M (2013) Probabilistic automata with isolated cut-points. Internat. Sympos. Math. Foundations Comput. Sci., 254–265.Google Scholar
• [7] Chatterjee K (2007) Stochastic ω-regular games. PhD thesis, UC Berkeley.Google Scholar
• [8] Chatterjee K, Doyen L (2014) Partial-observation stochastic games: How to win when belief fails. ACM Trans. Comput. Log. 15(2):1–44.Google Scholar
• [9] Chatterjee K, Henzinger TA (2010) Probabilistic automata on infinite words: Decidability and undecidability results. Internat. Sympos. Automated Tech. Verification Anal., 1–16.Google Scholar
• [10] Chatterjee K, Tracol M (2012) Decidable problems for probabilistic automata on infinite words. 27th Annual IEEE Sympos. Logic Comput. Sci., 185–194.Google Scholar
• [11] Chatterjee K, Chmelik M, Tracol M (2016) What is decidable about partially observable Markov decision processes with ω-regular objectives. J. Comput. System Sci. 82(5):878–911.Google Scholar
• [12] Chatterjee K, Doyen L, Henzinger TA (2013) A survey of partial-observation stochastic parity games. Form. Methods System Des. 43(2):268–284.Google Scholar
• [13] Chatterjee K, Majumdar R, Henzinger TA (2008) Stochastic limit-average games are in EXPTIME. Internat. J. Game Theory 37(2):219–234.Google Scholar
• [14] Chatterjee K, Saona R, Ziliotto B (2022) Finite-memory strategies in POMDPs with long-run average objectives. Math. Oper. Res. 47(1):100–119.Google Scholar
• [15] Chatterjee K, Chmelik M, Gupta R, Kanodia A (2016) Optimal cost almost-sure reachability in POMDPs. Artif. Intell. 234:26–48.Crossref, Google Scholar
• [16] Chatterjee K, Kafshdar Goharshady A, Ibsen-Jensen R, Velner Y (2018) Ergodic mean-payoff games for the analysis of attacks in crypto-currencies. 29th Internat. Conf. Concurrency Theory, vol. 118, 11:1–11:17.Google Scholar
• [17] Chevalier PY, Gusev VV, Jungers RM, Hendrickx JM (2017) Sets of Stochastic Matrices with Converging Products: Bounds and Complexity. Preprint, submitted December 7, https://arxiv.org/abs/1712.02614.Google Scholar
• [18] Daubechies I, Lagarias JC (1992) Sets of matrices all infinite products of which converge. Linear Algebra Appl. 161:227–263.Crossref, Google Scholar
• [19] Durbin R, Eddy SR, Krogh A, Mitchison G (1998) Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [20] Gimbert H, Oualhadj Y (2014) Deciding the value 1 problem for-acyclic partially observable Markov decision processes. Internat. Conf. Current Trends Theory Practice Inform., 281–292.Google Scholar
• [21] Givan R, Leach S, Dean T (2000) Bounded-parameter Markov decision processes. Artif. Intell. 122(1):71–109.Crossref, Google Scholar
• [22] Hansen EA, Bernstein DS, Zilberstein S (2004) Dynamic programming for partially observable stochastic games. Proc. 19th AAAI Conf. Artif. Intell., vol. 4, 709–715.Google Scholar
• [23] Hernández-Lerma O, Montes-De-Oca R, Cavazos-Cadena R (1991) Recurrence conditions for Markov decision processes with Borel state space: A survey. Ann. Oper. Res. 28(1):29–46.Crossref, Google Scholar
• [24] Hoffman AJ, Karp RM (1966) On nonterminating stochastic games. Management Sci. 12(5):359–370.Link, Google Scholar
• [25] Hopp WJ, Bean JC, Smith RL (1987) A new optimality criterion for nonhomogeneous Markov decision processes. Oper. Res. 35(6):875–883.Link, Google Scholar
• [26] Iosifescu M (1972) On two recent papers on ergodicity in nonhomogeneous Markov chains. Ann. Math. Statist. 43(5):1732–1736.Crossref, Google Scholar
• [27] Kolmogoroff A (1931) Über die analytischen methoden in der wahrscheinlichkeitsrechnung. Math. Ann. 104(1):415–458.Crossref, Google Scholar
• [28] Madani O, Hanks S, Condon A (2003) On the undecidability of probabilistic planning and related stochastic optimization problems. Artif. Intell. 147(1–2):5–34.Crossref, Google Scholar
• [29] Mertens JF, Neyman A (1981) Stochastic games. Internat. J. Game Theory 10(2):53–66.Crossref, Google Scholar
• [30] Mertens JF, Sorin S, Zamir S (2015) Repeated Games (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [31] Mohri M (1997) Finite-state transducers in language and speech processing. Comput. Linguist. 23(2):269–311.Google Scholar
• [32] Mott J (1957) Conditions for the ergodicity of non-homogeneous finite Markov chains. Proc. Roy. Soc. Edinburgh Sect. A Math. 64(4):369–380.Google Scholar
• [33] Neumann J V (1928) Zur theorie der gesellschaftsspiele. Math. Ann. 100(1):295–320.Crossref, Google Scholar
• [34] Nowak AS (1999) Sensitive equilibria for ergodic stochastic games with countable state spaces. Math. Methods Oper. Res. 50(1):65–76.Crossref, Google Scholar
• [35] Oliu-Barton M (2021) New algorithms for solving zero-sum stochastic games. Math. Oper. Res. 46(1):255–267.Link, Google Scholar
• [36] Park Y, Bean JC, Smith RL (1993) Optimal average value convergence in nonhomogeneous Markov decision processes. J. Math. Anal. Appl. 179(2):525–536.Crossref, Google Scholar
• [37] Paz A (1965) Definite and quasidefinite sets of stochastic matrices. Proc. Amer. Math. Soc. 16(4):634–641.Crossref, Google Scholar
• [38] Paz A (1971) Introduction to Probabilistic Automata (Academic Press, Cambridge, MA).Google Scholar
• [39] Puterman ML (2014) Markov Decision Processes: Discrete Stochastic Dynamic Programming (Wiley, Hoboken, NJ).Google Scholar
• [40] Rabin MO (1963) Probabilistic automata. Inform. Control 6(3):230–245.Crossref, Google Scholar
• [41] Renault J, Ziliotto B (2020) Hidden stochastic games and limit equilibrium payoffs. Games Econ. Behav. 124:122–139.Crossref, Google Scholar
• [42] Rosenberg D, Solan E, Vieille N (2002) Blackwell optimality in Markov decision processes with partial observation. Ann. Statist. 30(4):1178–1193.Crossref, Google Scholar
• [43] Seneta E (2006) Non-Negative Matrices and Markov Chains (Springer Science & Business Media, Berlin).Google Scholar
• [44] Shapley LS (1953) Stochastic games. Proc. Natl. Acad. Sci. USA 39(10):1095–1100.Crossref, Google Scholar
• [45] Sobel MJ (1971) Noncooperative stochastic games. Ann. Math. Statist. 42(6):1930–1935.Crossref, Google Scholar
• [46] Solan E, Ziliotto B (2016) Stochastic games with signals. Adv. Dynamic Evolutionary Games Theory Appl. Numer. Methods 14:77–94.Crossref, Google Scholar
• [47] Venel X (2015) Commutative stochastic games. Math. Oper. Res. 40(2):403–428.Link, Google Scholar
• [48] Vrieze O (2003) Stochastic games and stationary strategies. Neyman A, Sorin S, eds. Stochastic Games and Applications, NATO Science Series C: Mathematical and Physical Sciences, vol. 570 (Kluwer Academic Publishers, Dordrecht, Netherlands), 37–50.Google Scholar
• [49] Wachs AO, Schochetman IE, Smith RL (2011) Average optimality in nonhomogeneous infinite horizon Markov decision processes. Math. Oper. Res. 36(1):147–164.Link, Google Scholar
• [50] Wolfowitz J (1963) Products of indecomposable, aperiodic, stochastic matrices. Proc. Amer. Math. Soc. 14(5):733–737.Crossref, Google Scholar
• [51] Ziliotto B (2016) Zero-sum repeated games: Counterexamples to the existence of the asymptotic value and the conjecture maxmin=limv_n. Ann. Probab. 44(2):1107–1133.Crossref, Google Scholar