TY - GEN
T1 - Solving Irreducible Stochastic Mean-Payoff Games and Entropy Games by Relative Krasnoselskii–Mann Iteration
AU - Akian, Marianne
AU - Gaubert, Stéphane
AU - Naepels, Ulysse
AU - Terver, Basile
N1 - Publisher Copyright:
© Marianne Akian, Stéphane Gaubert, Ulysse Naepels, and Basile Terver;
PY - 2023/8/1
Y1 - 2023/8/1
N2 - We analyse an algorithm solving stochastic mean-payoff games, combining the ideas of relative value iteration and of Krasnoselskii–Mann damping. We derive parameterized complexity bounds for several classes of games satisfying irreducibility conditions. We show in particular that an ϵ-approximation of the value of an irreducible concurrent stochastic game can be computed in a number of iterations in O(|log ϵ|) where the constant in the O(·) is explicit, depending on the smallest non-zero transition probabilities. This should be compared with a bound in O(ϵ−1|log(ϵ)|) obtained by Chatterjee and Ibsen-Jensen (ICALP 2014) for the same class of games, and to a O(ϵ−1) bound by Allamigeon, Gaubert, Katz and Skomra (ICALP 2022) for turn-based games. We also establish parameterized complexity bounds for entropy games, a class of matrix multiplication games introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. We derive these results by methods of variational analysis, establishing contraction properties of the relative Krasnoselskii–Mann iteration with respect to Hilbert’s semi-norm.
AB - We analyse an algorithm solving stochastic mean-payoff games, combining the ideas of relative value iteration and of Krasnoselskii–Mann damping. We derive parameterized complexity bounds for several classes of games satisfying irreducibility conditions. We show in particular that an ϵ-approximation of the value of an irreducible concurrent stochastic game can be computed in a number of iterations in O(|log ϵ|) where the constant in the O(·) is explicit, depending on the smallest non-zero transition probabilities. This should be compared with a bound in O(ϵ−1|log(ϵ)|) obtained by Chatterjee and Ibsen-Jensen (ICALP 2014) for the same class of games, and to a O(ϵ−1) bound by Allamigeon, Gaubert, Katz and Skomra (ICALP 2022) for turn-based games. We also establish parameterized complexity bounds for entropy games, a class of matrix multiplication games introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. We derive these results by methods of variational analysis, establishing contraction properties of the relative Krasnoselskii–Mann iteration with respect to Hilbert’s semi-norm.
KW - Hilbert projective metric
KW - Krasnoselskii–Mann fixed point algorithm
KW - Stochastic mean-payoff games
KW - concurrent games
KW - entropy games
KW - relative value iteration
U2 - 10.4230/LIPIcs.MFCS.2023.10
DO - 10.4230/LIPIcs.MFCS.2023.10
M3 - Conference contribution
AN - SCOPUS:85171478592
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
A2 - Leroux, Jerome
A2 - Lombardy, Sylvain
A2 - Peleg, David
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
Y2 - 28 August 2023 through 1 September 2023
ER -