mlsanityData to 14 Oct 2026

Towards Blackwell Optimality: Bellman Optimality Is All You Can Get

arXiv 2510.13476 ↗First posted 15 Oct 2025cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

Although average gain optimality is a commonly adopted performance measure in Markov Decision Processes (MDPs), it is often too asymptotic. Further incorporating measures of immediate losses leads to the hierarchy of bias optimalities, all the way up to Blackwell optimality. In this paper, we investigate the problem of identifying policies of such optimality orders. To that end, for each order, we construct a learning algorithm with vanishing probability of error. Furthermore, we characterize the class of MDPs for which identification algorithms can stop in finite time. That class corresponds to the MDPs with a unique Bellman optimal policy, and does not depend on the optimality order considered. Lastly, we provide a tractable stopping rule that when coupled to our learning algorithm triggers in finite time whenever it is possible to do so.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 12 of its 20 references that are in the map. First posted on arXiv 15 Oct 2025.

Builds on

12 of 20 references.

References · 12

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  2. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  3. 2020Tightening Exploration in Upper Confidence Reinforcement Learningcited by 25
  4. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  5. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  6. 2025Near-Optimal Sample Complexity for MDPs via Anchoringcited by 14
  7. 2023Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factorcited by 13
  8. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 13
  9. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 5
  10. 2025Logarithmic Regret of Exploration in Average Reward Markov Decision Processescited by 2
  11. 2025Asymptotically optimal regret in communicating Markov decision processescited by 2
  12. 2025Efficient Computation of Blackwell Optimal Policies using Rational Functionscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approachcited by 0