# Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2023.

## 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)
- [Solving Robust Markov Decision Processes: Generic, Reliable, Efficient](https://mlsanity.com/paper/2412.10185/) (2024)
- [Solving Long-run Average Reward Robust MDPs via Stochastic Games](https://mlsanity.com/paper/2312.13912/) (2023)
- [Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPs](https://mlsanity.com/paper/2405.04941/) (2024)
- [Bellman Optimality of Average-Reward Robust Markov Decision Processes with a Constant Gain](https://mlsanity.com/paper/2509.14203/) (2025)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Qualitative Analysis of ω-Regular Objectives on Robust MDPs](https://mlsanity.com/paper/2505.04539/) (2025)
- [Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values](https://mlsanity.com/paper/2603.00945/) (2026)
- [Efficient Computation of Blackwell Optimal Policies using Rational Functions](https://mlsanity.com/paper/2508.18252/) (2025)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [DomAgent: Leveraging Knowledge Graphs and Case-Based Reasoning for Domain-Specific Code Generation](https://mlsanity.com/paper/2603.21430/) (2026)
- [Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games](https://mlsanity.com/paper/2608.24986/) (2026)
- [Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2609.28792/) (2026)

## Abstract (arXiv)

Robust Markov Decision Processes (RMDPs) are a widely used framework for sequential decision-making under parameter uncertainty. RMDPs have been extensively studied when the objective is to maximize the discounted return, but little is known for average optimality (optimizing the long-run average of the rewards obtained over time) and Blackwell optimality (remaining discount optimal for all discount factors sufficiently close to ). In this paper, we prove several foundational results for RMDPs beyond the discounted return. We show that average optimal policies can be chosen stationary and deterministic for sa-rectangular RMDPs but, perhaps surprisingly, we show that for s-rectangular RMDPs average optimal policies may not exist, and if they exist, may need to be history-dependent (Markovian). We also study Blackwell optimality for sa-rectangular RMDPs, where we show that ε-Blackwell optimal policies always exist, although Blackwell optimal policies may not exist. We also provide a sufficient condition for their existence, which encompasses virtually any examples from the literature. We then discuss the connection between average and Blackwell optimality, and we describe several algorithms to compute the optimal average return. Interestingly, our approach leverages the connections between RMDPs and stochastic games. Overall, our paper emphasizes the superior practical properties of distance-based sa-rectangular models over s-rectangular models for average and Blackwell optimality.