Thresholds for sensitive optimality and Blackwell optimality in stochastic games

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 αsf 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 αsf d ∈ [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 Oleft((1-α)-1right) 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.