Thresholds for sensitive optimality and Blackwell optimality in stochastic games
Stéphane Gaubert, Julien Grand-Clément, Ricardo D. Katz · 2025
Read Thresholds for sensitive optimality and Blackwell optimality in stochastic games by Stéphane Gaubert, Julien Grand-Clément, Ricardo D. Katz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-18545.txt.
Introduction
Stephane Gaubert, Julien Grand-Clement, and Ricardo Katz bound key thresholds in stochastic games in a 2025 math paper. In such games, two players with opposed goals face random moves, and a common score is the long run average payoff. A finer idea asks for a strategy that stays best when the discount on future payoffs is close to one, called Blackwell optimality.
A threshold marks the discount above which all best discounted strategies are already Blackwell best. That threshold controls how hard the finer problem is to compute. The authors give the first bounds for a family of in between thresholds and improve the Blackwell bound, using number theory tools on algebraic numbers.
Catalog record
| CREATOR | Stéphane Gaubert, Julien Grand-Clément, Ricardo D. Katz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-18545
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Thresholds for sensitive optimality and Blackwell optimality in stochastic games Stéphane Gaubert, Julien Grand-Clément, Ricardo D. Katz Abstract 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 1 . The notion of d d -sensitive optimality interpolates between mean-payoff optimality (corresponding to the case d = − 1 d=-1 ) and Blackwell optimality ( d = ∞ d=\infty ). The Blackwell threshold α 𝖡𝗐 ∈ [ 0 , 1 [ \alpha_{\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 d -sensitive threshold α 𝖽 ∈ [ 0 , 1 [ \alpha_{\sf d}\in[0,1[ is defined analogously. Bounding α 𝖡𝗐 \alpha_{\sf Bw} and α 𝖽 \alpha_{\sf d} are fundamental problems in algorithmic game theory, since these thresholds control the complexity for computing Blackwell and d d -sensitive optimal strategies, by reduction to discounted games which can be solved in O ( ( 1 − α ) − 1 ) O\left((1-\alpha)^{-1}\right) iterations. We provide the first bounds on the d d -sensitive threshold α 𝖽 \alpha_{\sf d} beyond the case d = − 1 d=-1 , and we establish improved bounds for the Blackwell threshold α 𝖡𝗐 \alpha_{\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. 1 Introduction Two-player perfect-information zero-sum stochastic games (SGs) are an important class of Shapley’s stochastic games Sha 53 where every state is controlled by a unique player. SGs are a cornerstone of game theory, with important applications in auctions LLP+ 99 , mechanism design Nar 14 , multi-agent reinforcement learning Lit 94 , robust optimization GCPV 23 ; CGK+ 23 , and \mu -calculus model-checking CHV+ 18 . Shapley originally considered the sum of discounted instantaneous rewards as the objective; the mean-payoff objective was studied in Gil 57 . Stationary and deterministic optimal strategies exist for these objectives in the perfect-information case Sha 53 ; LL 69 . The mean-payoff objective coincides with the limit of the discounted objective as the discount factor goes to 1 . This suggests to study the variation of the set of optimal strategies in the discounted game, as a function of the discount factor. Blackwell showed (in the one-player case) that, for finite state and action models, there exist strategies that remain discount optimal for all values of the discount factor that are sufficiently close to 1 Bla 62 . These are now called Blackwell optimal strategies . As the discount factor approaches 1 , the “weight” given to the rewards received in the distant future increases. Therefore, Blackwell optimal strategies can be considered as the most farsighted (or least greedy) strategies for models in long horizon. This is why better understanding Blackwell optimality is referred to as “ one of the pressing questions in reinforcement learning ” in DDE+ 20 . Veinott introduced (still in the one-player case) the notion of d -sensitive optimality , interpolating between mean-payoff optimality (obtained for d=-1 ) and Blackwell optimality (obtained for d=\infty ). The value associated with a given stationary strategy has a Laurent series expansion in the powers of 1-\alpha , where \alpha is the discount factor, with a pole of order at most -1 at \alpha=1 . Veinott’s d -sensitive objective involves the sequence of coefficients of this expansion, up to order d , which is maximized or minimized with respect to the lexicographic order (see Theorem 10.1.6 in Put 14 ). In particular, any d -sensitive optimal strategy is d^{\prime} -sensitive optimal for all d^{\prime}<d . Moreover, for models with n states, every (n-2) -sensitive optimal strategy is Blackwell optimal. The notion for d=0 is also known as bias optimality . It is worth emphasizing that the notions of Blackwell optimality and mean-payoff optimality have received increased attention recently in the reinforcement learning community, see DDE+ 20 ; DG 22 ; TRMV 21 ; YGA+ 16 . More generally, computing mean-payoff optimal strategies is an important open question in algorithmic game theory and has been extensively studied. Pseudo- polynomial algorithms exist for mean-payoff deterministic instances, based on pumping GKK 88 and value iteration ZP 96 ; CGB 03 ; GS 08 . In more generality, computing mean-payoff or bias optimal strategies is difficult, since the Bellman operator is no longer a contraction when \alpha=1 , and the mean-payoff and bias objectives may be discontinuous in the entries of stationary strategies (e.g., Chapter 4 of FS 12 ). In fact, strategy iteration may cycle for the mean-payoff objective in multichain instances (see Section 6 of ACTDG 12 ), and other algorithms have an exponential dependence on the number of states with stochastic (non-deterministic) transitions or undetermined complexities ACTDG 12 ; BEGM 10 . Besides the method based on the Blackwell threshold discussed below, the only algorithm we are aware of to compute Blackwell optimal policies consists in performing policy iteration, considering the discount factor as a formal parameter, and encoding the discounted value function associated to a pair of policies by its Laurent series expansion truncated at order n-2 , leading to a nested lexicographic policy iteration method, see ( Put 14 , Chapter 10.3) for a presentation in the one player case. A counter example of Friedmann implies that for deterministic games, this algorithm can take an exponential time Fri 09 . The existence of the Blackwell threshold , defined as the smallest number \alpha_{\sf Bw}\in[0,1[ such that strategies that are optimal for any discount factor \alpha\geq\alpha_{\sf Bw} are Blackwell optimal, is well-known, e.g. AM 09 . We define the d -sensitive threshold as the smallest number \alpha_{\sf d}\in[0,1[ such that strategies that are discount optimal for any discount factor \alpha\geq\alpha_{\sf d} are d -sensitive optimal. The existence of \alpha_{\sf Bw} and \alpha_{\sf d} suggests a simple method for computing Blackwell and d -sensitive optimal strategies: compute discount optimal strategies for a discount factor \alpha close to 1. This approach has the advantage that any advances in solving discounted SGs transfer to algorithms for Blackwell and mean-payoff optimal strategies. Note that the term (1-\alpha)^{-1} controls the complexity of computing discount optimal strategies: for known game parameters (rewards and transitions), strategy iteration and value iteration scale as \tilde{O}((1-\alpha)^{-1}) HMZ 13 (hiding the dependence on the number of states/actions, and lower order terms in 1-\alpha ). For unknown game parameters, model-based methods ZKBY 23 or model-free methods based on Q-learning SWYY 20 scale as \tilde{O}((1-\alpha)^{-3}) . Thus, for computational purposes, it is crucial to upper bound \alpha_{\sf Bw} and \alpha_{\sf d} , or equivalently to lower bound 1-\alpha_{\sf Bw} and 1-\alpha_{\sf d} . For such bounds to be useful, they should only rely on a few game parameters that are available by design. In this paper we consider SGs that satisfy the next assumption. Assumption 1.1 . \Gamma is a perfect-information stochastic game with n\in\mathbb{N} states, integer rewards with absolute values bounded by W\in\mathbb{N} , and transition probabilities with common denominator M\in\mathbb{N} . Main results. We provide upper bounds for the Blackwell threshold