Sharper bounds improve understanding of optimal strategies in stochastic games
Sharper bounds on the thresholds for sensitive and Blackwell optimality
Computer Science and Game Theory
Summary
This paper looks at special kinds of two-player games where players see everything that happens and can make decisions with some randomness involved. The authors focus on how to measure when certain decision strategies become the best as players care more about the future. They find better mathematical limits for when these strategies match up, improving on earlier work. Their results apply even to more complicated game situations that weren't studied before.
What this means in practice
- •For game theory programmers: Determine precise discount factors needed to guarantee optimal strategies in perfect-information stochastic games.
- •For algorithm designers: Use tighter polynomial bounds to optimize algorithms finding Blackwell and sensitive optimal strategies in multi-state decision processes.
A theory result. No direct application yet.
Authors
Xavier Allamigeon, Stéphane Gaubert, Julien Grand-Clément, Ricardo Katz
Abstract
In perfect-information two-player stochastic games, the notions of Blackwell and sensitive optimality provide generalizations of the classical mean-payoff optimality and discount optimality criteria to account for more farsighted preferences. We provide bounds on the Blackwell threshold $α_{\sf bw}$ and the $d$-sensitive thresholds $α_{\sf d}$, defined as the smallest discount factors above which discount optimal policies coincide with Blackwell optimal policies and $d$-sensitive optimal policies respectively. Our refined bounds improve upon prior work by focusing on ``reduced'' families of polynomials and, crucially, our bounds are tight in terms of controlling the degrees and heights of the minimal polynomials of the Blackwell thresholds. We apply classical root separation based on Mahler's and Cauchy's bounds to our reduced families to derive the strongest upper and lower bounds on $α_{\sf bw}$ in the literature, and we are the first to obtain bounds on $α_{\sf d}$ in the multichain stochastic setting.