# Thresholds for sensitive optimality and Blackwell optimality in stochastic games

arXiv: https://arxiv.org/abs/2506.18545 · HTML: https://mlsanity.com/paper/2506.18545/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2025.

## Built on by (most cited first, 1 of 1)

- [Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain](https://mlsanity.com/paper/2509.14203/) (2025)

## Abstract (arXiv)

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.