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. The notion of d-sensitive optimality interpolates between mean-payoff optimality (corresponding to the case d=-1) and Blackwell optimality (d=+∞). The Blackwell threshold α_ Bw ∈ [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 α_ d ∈ [0,1[ is defined analogously. Bounding α_ Bw and α_ 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((1-α)⁻¹) iterations. We provide the first bounds on the d-sensitive threshold α_ d beyond the case d=-1, and we establish improved bounds for the Blackwell threshold α_ 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.