# Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 64 references that are in the map.
- First posted on arXiv 31 Jan 2023.

## Builds on (most cited first, 18 of 18)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations](https://mlsanity.com/paper/1808.03971/) (2018)
- [Average-reward model-free reinforcement learning: a systematic review and literature mapping](https://mlsanity.com/paper/2010.08920/) (2020)
- [Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2301.00858/) (2023)
- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [A First-Order Approach To Accelerated Value Iteration](https://mlsanity.com/paper/1905.09963/) (2019)
- [On the convex formulations of robust Markov decision processes](https://mlsanity.com/paper/2209.10187/) (2022)
- [Average Reward Adjusted Discounted Reinforcement Learning: Near-Blackwell-Optimal Policies for Real-World Applications](https://mlsanity.com/paper/2004.00857/) (2020)
- [Examining average and discounted reward optimality criteria in reinforcement learning](https://mlsanity.com/paper/2107.01348/) (2021)
- [Taylor Expansion of Discount Factors](https://mlsanity.com/paper/2106.06170/) (2021)
- [Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial](https://mlsanity.com/paper/1310.4953/) (2013)

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

- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards](https://mlsanity.com/paper/2410.12175/) (2024)
- [Solving Long-run Average Reward Robust MDPs via Stochastic Games](https://mlsanity.com/paper/2312.13912/) (2023)
- [On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2403.06806/) (2024)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor](https://mlsanity.com/paper/2505.00795/) (2025)
- [Qualitative Analysis of ω-Regular Objectives on Robust MDPs](https://mlsanity.com/paper/2505.04539/) (2025)
- [On shallow planning under partial observability](https://mlsanity.com/paper/2407.15820/) (2024)
- [An Empirical Study of Deep Reinforcement Learning in Continuing Tasks](https://mlsanity.com/paper/2501.06937/) (2025)
- [Efficient Computation of Blackwell Optimal Policies using Rational Functions](https://mlsanity.com/paper/2508.18252/) (2025)
- [Towards Blackwell Optimality: Bellman Optimality Is All You Can Get](https://mlsanity.com/paper/2510.13476/) (2025)
- [Revisiting Value Iteration: Unified Analysis of Discounted and Average-Reward Cases](https://mlsanity.com/paper/2510.23914/) (2025)
- [Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games](https://mlsanity.com/paper/2608.24986/) (2026)

## Abstract (arXiv)

We introduce the Blackwell discount factor for Markov Decision Processes (MDPs). Classical objectives for MDPs include discounted, average, and Blackwell optimality. Many existing approaches to computing average-optimal policies solve for discounted optimal policies with a discount factor close to 1, but they only work under strong or hard-to-verify assumptions such as ergodicity or weakly communicating MDPs. In this paper, we show that when the discount factor is larger than the Blackwell discount factor γbw, all discounted optimal policies become Blackwell- and average-optimal, and we derive a general upper bound on γbw. The upper bound on γbw provides the first reduction from average and Blackwell optimality to discounted optimality, without any assumptions, and new polynomial-time algorithms for average- and Blackwell-optimal policies. Our work brings new ideas from the study of polynomials and algebraic numbers to the analysis of MDPs. Our results also apply to robust MDPs, enabling the first algorithms to compute robust Blackwell-optimal policies.