# Efficient Computation of Blackwell Optimal Policies using Rational Functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 45 references that are in the map.
- First posted on arXiv 25 Aug 2025.

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

- [Self-Driving Cars: A Survey](https://mlsanity.com/paper/1901.04407/) (2019)
- [Average-reward model-free reinforcement learning: a systematic review and literature mapping](https://mlsanity.com/paper/2010.08920/) (2020)
- [Convergence of Policy Gradient for Entropy Regularized MDPs with Neural Network Approximation in the Mean-Field Regime](https://mlsanity.com/paper/2201.07296/) (2022)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality](https://mlsanity.com/paper/2312.03618/) (2023)
- [Average Reward Adjusted Discounted Reinforcement Learning: Near-Blackwell-Optimal Policies for Real-World Applications](https://mlsanity.com/paper/2004.00857/) (2020)
- [On the Complexity of Policy Iteration](https://mlsanity.com/paper/1301.6718/) (2013)
- [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)
- [A nearly Blackwell-optimal policy gradient method](https://mlsanity.com/paper/2105.13609/) (2021)
- [Simulation-Driven Reinforcement Learning in Queuing Network Routing Optimization](https://mlsanity.com/paper/2507.18795/) (2025)

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

- [Towards Blackwell Optimality: Bellman Optimality Is All You Can Get](https://mlsanity.com/paper/2510.13476/) (2025)

## Abstract (arXiv)

Markov Decision Problems (MDPs) provide a foundational framework for modelling sequential decision-making across diverse domains, guided by optimality criteria such as discounted and average rewards. However, these criteria have inherent limitations: discounted optimality may overly prioritise short-term rewards, while average optimality relies on strong structural assumptions. Blackwell optimality addresses these challenges, offering a robust and comprehensive criterion that ensures optimality under both discounted and average reward frameworks. Despite its theoretical appeal, existing algorithms for computing Blackwell Optimal (BO) policies are computationally expensive or hard to implement. In this paper we describe procedures for computing BO policies using an ordering of rational functions in the vicinity of 1. We adapt state-of-the-art algorithms for deterministic and general MDPs, replacing numerical evaluations with symbolic operations on rational functions to derive bounds independent of bit complexity. For deterministic MDPs, we give the first strongly polynomial-time algorithms for computing BO policies, and for general MDPs we obtain the first subexponential-time algorithm. We further generalise several policy iteration algorithms, extending the best known upper bounds from the discounted to the Blackwell criterion.