Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2505.02623 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913820482469888 |
|---|---|
| author | Hansen, Kristoffer Arnsfelt Ibsen-Jensen, Rasmus Neyman, Abraham |
| author_facet | Hansen, Kristoffer Arnsfelt Ibsen-Jensen, Rasmus Neyman, Abraham |
| contents | We study the memory resources required for near-optimal play in two-player zero-sum stochastic games with the long-run average payoff. Although optimal strategies may not exist in such games, near-optimal strategies always do.
Mertens and Neyman (1981) proved that in any stochastic game, for any $\varepsilon>0$, there exist uniform $\varepsilon$-optimal memory-based strategies -- i.e., strategies that are $\varepsilon$-optimal in all sufficiently long $n$-stage games -- that use at most $O(n)$ memory states within the first $n$ stages. We improve this bound on the number of memory states by proving that in any stochastic game, for any $\varepsilon>0$, there exist uniform $\varepsilon$-optimal memory-based strategies that use at most $O(\log n)$ memory states in the first $n$ stages. Moreover, we establish the existence of uniform $\varepsilon$-optimal memory-based strategies whose memory updating and action selection are time-independent and such that, with probability close to 1, for all $n$, the number of memory states used up to stage $n$ is at most $O(\log n)$.
This result cannot be extended to strategies with bounded public memory -- even if time-dependent memory updating and action selection are allowed. This impossibility is illustrated in the Big Match -- a well-known stochastic game where the stage payoffs to Player 1 are 0 or 1. Although for any $\varepsilon > 0$, there exist strategies of Player 1 that guarantee a payoff {exceeding} $1/2 - \varepsilon$ in all sufficiently long $n$-stage games, we show that any strategy of Player 1 that uses a finite public memory fails to guarantee a payoff greater than $\varepsilon$ in any sufficiently long $n$-stage game. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_02623 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Stochastic Games with Limited Public Memory Hansen, Kristoffer Arnsfelt Ibsen-Jensen, Rasmus Neyman, Abraham Computer Science and Game Theory Optimization and Control We study the memory resources required for near-optimal play in two-player zero-sum stochastic games with the long-run average payoff. Although optimal strategies may not exist in such games, near-optimal strategies always do. Mertens and Neyman (1981) proved that in any stochastic game, for any $\varepsilon>0$, there exist uniform $\varepsilon$-optimal memory-based strategies -- i.e., strategies that are $\varepsilon$-optimal in all sufficiently long $n$-stage games -- that use at most $O(n)$ memory states within the first $n$ stages. We improve this bound on the number of memory states by proving that in any stochastic game, for any $\varepsilon>0$, there exist uniform $\varepsilon$-optimal memory-based strategies that use at most $O(\log n)$ memory states in the first $n$ stages. Moreover, we establish the existence of uniform $\varepsilon$-optimal memory-based strategies whose memory updating and action selection are time-independent and such that, with probability close to 1, for all $n$, the number of memory states used up to stage $n$ is at most $O(\log n)$. This result cannot be extended to strategies with bounded public memory -- even if time-dependent memory updating and action selection are allowed. This impossibility is illustrated in the Big Match -- a well-known stochastic game where the stage payoffs to Player 1 are 0 or 1. Although for any $\varepsilon > 0$, there exist strategies of Player 1 that guarantee a payoff {exceeding} $1/2 - \varepsilon$ in all sufficiently long $n$-stage games, we show that any strategy of Player 1 that uses a finite public memory fails to guarantee a payoff greater than $\varepsilon$ in any sufficiently long $n$-stage game. |
| title | Stochastic Games with Limited Public Memory |
| topic | Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2505.02623 |