Planning in entropy-regularized Markov decision processes and games

Jean-Bastien Grill, Omar Darwiche Domingues, Pierre Ménard, Rémi Munos, Michal Valko
4/21/2026
cs.LG

No confident code implementation found for this paper.

Abstract

We propose SmoothCruiser, a new planning algorithm for estimating the value function in entropy-regularized Markov decision processes and two-player games, given a generative model of the environment. SmoothCruiser makes use of the smoothness of the Bellman operator promoted by the regularization to achieve problem-independent sample complexity of order O~(1/epsilon^4) for a desired accuracy epsilon, whereas for non-regularized settings there are no known algorithms with guaranteed polynomial sample complexity in the worst case.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{grill2026planning,
  title  = {Planning in entropy-regularized Markov decision processes and games},
  author = {Jean-Bastien Grill and Omar Darwiche Domingues and Pierre Ménard and Rémi Munos and Michal Valko},
  year   = {2026},
  eprint = {2604.19695},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2604.19695v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2604.19695.svg)](https://codeofpaper.com/paper/2604.19695)

Discussion