Thresholds for sensitive optimality and Blackwell optimality in stochastic games
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915355358658560 |
|---|---|
| author | Gaubert, Stéphane Grand-Clément, Julien Katz, Ricardo D. |
| author_facet | Gaubert, Stéphane Grand-Clément, Julien Katz, Ricardo D. |
| contents | We investigate refinements of the mean-payoff criterion in two-player zero-sum perfect-information stochastic games. A strategy is Blackwell optimal if it is optimal in the discounted game for all discount factors sufficiently close to $1$. The notion of $d$-sensitive optimality interpolates between mean-payoff optimality (corresponding to the case $d=-1$) and Blackwell optimality ($d=+\infty$). The Blackwell threshold $α_{\sf Bw} \in [0,1[$ is the discount factor above which all optimal strategies in the discounted game are guaranteed to be Blackwell optimal. The $d$-sensitive threshold $α_{\sf d} \in [0,1[$ is defined analogously. Bounding $α_{\sf Bw}$ and $α_{\sf d}$ are fundamental problems in algorithmic game theory, since these thresholds control the complexity for computing Blackwell and $d$-sensitive optimal strategies, by reduction to discounted games which can be solved in $O\left((1-α)^{-1}\right)$ iterations. We provide the first bounds on the $d$-sensitive threshold $α_{\sf d}$ beyond the case $d=-1$, and we establish improved bounds for the Blackwell threshold $α_{\sf Bw}$. This is achieved by leveraging separation bounds on algebraic numbers, relying on Lagrange bounds and more advanced techniques based on Mahler measures and multiplicity theorems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18545 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Thresholds for sensitive optimality and Blackwell optimality in stochastic games Gaubert, Stéphane Grand-Clément, Julien Katz, Ricardo D. Computer Science and Game Theory We investigate refinements of the mean-payoff criterion in two-player zero-sum perfect-information stochastic games. A strategy is Blackwell optimal if it is optimal in the discounted game for all discount factors sufficiently close to $1$. The notion of $d$-sensitive optimality interpolates between mean-payoff optimality (corresponding to the case $d=-1$) and Blackwell optimality ($d=+\infty$). The Blackwell threshold $α_{\sf Bw} \in [0,1[$ is the discount factor above which all optimal strategies in the discounted game are guaranteed to be Blackwell optimal. The $d$-sensitive threshold $α_{\sf d} \in [0,1[$ is defined analogously. Bounding $α_{\sf Bw}$ and $α_{\sf d}$ are fundamental problems in algorithmic game theory, since these thresholds control the complexity for computing Blackwell and $d$-sensitive optimal strategies, by reduction to discounted games which can be solved in $O\left((1-α)^{-1}\right)$ iterations. We provide the first bounds on the $d$-sensitive threshold $α_{\sf d}$ beyond the case $d=-1$, and we establish improved bounds for the Blackwell threshold $α_{\sf Bw}$. This is achieved by leveraging separation bounds on algebraic numbers, relying on Lagrange bounds and more advanced techniques based on Mahler measures and multiplicity theorems. |
| title | Thresholds for sensitive optimality and Blackwell optimality in stochastic games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2506.18545 |