2023/05/03 by Marianne Akian, Stéphane Gaubert, Akian, Marianne +5 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #47H09 #91A15 #Computability, Logic, AI Algorithms #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Model Reduction and Neural Networks #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2305.02458
openalex publication_date 2023/05/03 · openalex created_date 2023/05/07 · openalex updated_date 2026/07/28
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.