mlsanityData to 14 Oct 2026

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

arXiv 2302.00036 ↗First posted 31 Jan 2023cs.LGcited by 13

Not on the map. Why?

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.

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

18 of 64 references.

References · 18

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2016OpenAI Gymcited by 1,736
  3. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
  4. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
  5. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 50
  6. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  7. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  8. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  9. 2018Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterationscited by 25
  10. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 22
  11. 2023Robust Average-Reward Markov Decision Processescited by 22
  12. 2013Improved and Generalized Upper Bounds on the Complexity of Policy Iterationcited by 21
6 more
  1. 2019A First-Order Approach To Accelerated Value Iterationcited by 17
  2. 2022On the convex formulations of robust Markov decision processescited by 10
  3. 2020Average Reward Adjusted Discounted Reinforcement Learning: Near-Blackwell-Optimal Policies for Real-World Applicationscited by 6
  4. 2021Examining average and discounted reward optimality criteria in reinforcement learningcited by 6
  5. 2021Taylor Expansion of Discount Factorscited by 4
  6. 2013Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomialcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 4; 2025: 7; 2026: 1.

13 papers.

Sort:

By area:

  1. 2024Robust Markov Decision Processes: A Place Where AI and Formal Methods Meetcited by 18
  2. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewardscited by 14
  3. 2023Solving Long-run Average Reward Robust MDPs via Stochastic Gamescited by 10
  4. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processescited by 9
  5. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 3
  6. 2025Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factorcited by 2
  7. 2025Qualitative Analysis of ω-Regular Objectives on Robust MDPscited by 2
  8. 2024On shallow planning under partial observabilitycited by 1
  9. 2025An Empirical Study of Deep Reinforcement Learning in Continuing Taskscited by 1
  10. 2025Efficient Computation of Blackwell Optimal Policies using Rational Functionscited by 1
  11. 2025Towards Blackwell Optimality: Bellman Optimality Is All You Can Getcited by 1
  12. 2025Revisiting Value Iteration: Unified Analysis of Discounted and Average-Reward Casescited by 1
1 more
  1. 2026Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Gamescited by 0