Metraipolis › archive › dc_5d180d2ece27
Smoothed analysis of policy iteration and value iteration for deterministic discounted and mean-payoff games played on any graph — arXiv:2610.22149
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.22149
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:12:19.441Z
- SHA-256 of the archived text
4d6c15629565dd3464320e55cc17371878e3df1929cbb3716e4b4935f5d99bb9- Stable URL of this page
https://metraipolis.com/documento/dc_5d180d2ece27
How to cite
Smoothed analysis of policy iteration and value iteration for deterministic discounted and mean-payoff games played on any graph — arXiv:2610.22149 — arXiv (en), https://arxiv.org/abs/2610.22149 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5d180d2ece27 (Metraipolis archive dc_5d180d2ece27, sha256 4d6c15629565dd3464320e55cc17371878e3df1929cbb3716e4b4935f5d99bb9)
BibTeX
@misc{dc5d180d2ece27,
title = {Smoothed analysis of policy iteration and value iteration for deterministic discounted and mean-payoff games played on any graph — arXiv:2610.22149},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.22149},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5d180d2ece27; sha256 4d6c15629565dd3464320e55cc17371878e3df1929cbb3716e4b4935f5d99bb9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.22149. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Our understanding of turn-based stochastic games is reminiscent of our understanding of linear programming in the 1970s. Instead of the simplex method, we have two families of algorithms - policy iteration and value iteration - which work well in practice but are known to run in exponential time on some input instances, and we still lack an algorithm that runs in polynomial time on all instances. A recent result by Loff and Skomra showed that, for deterministic discounted and mean-payoff games played on an ergodic graph, a variant of policy iteration runs in smoothed polynomial time. This offered an explanation of why policy iteration performs well in practice, analogous to Spielman and Teng's explanation for the simplex method. In this paper, we drop the ergodicity assumption: we show that their policy iteration algorithms run in smoothed polynomial time for any game graph. We do this by defining a condition number that naturally generalizes theirs, showing that sufficiently-perturbed games are well-conditioned with high probability, and showing that their algorithms are efficient on well-conditioned instances. Although the outline is similar, our proof requires a substantially new approach, based on log-Lipschitz distributions which recently appeared in work on the smoothed analysis of the simplex method. For our second contribution, we propose three new value iteration algorithms for solving deterministic mean-payoff games (also on any graph). All three are based on iterative methods for finding fixed points of non-expansive operators, which we show can be applied to the Shapley operator. The first two are simple applications of Krasnoselskii-Mann iteration and Halpern iteration. The third is quadratically faster but more complicated: it runs Zwick-Paterson and Halpern iterations in parallel. We prove that all three algorithms are correct and run in smoothed polynomial time. Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno). Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2610.22149 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T08:46:02.647Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).