# Asymptotically optimal regret in communicating Markov decision processes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2025.

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

- [Towards Blackwell Optimality: Bellman Optimality Is All You Can Get](https://mlsanity.com/paper/2510.13476/) (2025)
- [Model-Based Learning of Whittle indices](https://mlsanity.com/paper/2511.20397/) (2025)

## Abstract (arXiv)

In this paper, we present a learning algorithm that achieves asymptotically optimal regret for Markov decision processes in average reward under a communicating assumption. That is, given a communicating Markov decision process M, our algorithm has regret K(M) log(T) + o(log(T)) where T is the number of learning steps and K(M) is the best possible constant. This algorithm works by explicitly tracking the constant K(M) to learn optimally, then balances the trade-off between exploration (playing sub-optimally to gain information), co-exploration (playing optimally to gain information) and exploitation (playing optimally to score maximally). We further show that the function K(M) is discontinuous, which is a consequence challenge for our approach. To that end, we describe a regularization mechanism to estimate K(M) with arbitrary precision from empirical data.