English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We analyse an algorithm solving stochastic mean-payoff games, combining theideas of relative value iteration and of Krasnoselskii-Mann damping. We deriveparameterized complexity bounds for several classes of games satisfyingirreducibility conditions. We show in particular that an$\epsilon$-approximation of the value of an irreducible concurrent stochasticgame can be computed in a number of iterations in $O(|\log\epsilon|)$ where theconstant in the $O(\cdot)$ is explicit, depending on the smallest non-zerotransition probabilities. This should be compared with a bound in$O(|\epsilon|^{-1}|\log(\epsilon)|)$ obtained by Chatterjee and Ibsen-Jensen(ICALP 2014) for the same class of games, and to a $O(|\epsilon|^{-1})$ boundby Allamigeon, Gaubert, Katz and Skomra (ICALP 2022) for turn-based games. Wealso establish parameterized complexity bounds for entropy games, a class ofmatrix multiplication games introduced by Asarin, Cervelle, Degorre, Dima, Hornand Kozyakin. We derive these results by methods of variational analysis,establishing contraction properties of the relative Krasnoselskii-Manniteration with respect to Hilbert's semi-norm.

Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration