# Planning in entropy-regularized Markov decision processes and games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 21 Apr 2026.

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Equivalence Between Policy Gradients and Soft Q-Learning](https://mlsanity.com/paper/1704.06440/) (2017)
- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)
- [Monte-Carlo Tree Search by Best Arm Identification](https://mlsanity.com/paper/1706.02986/) (2017)
- [Structured Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1706.05198/) (2017)
- [Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning](https://mlsanity.com/paper/2604.14974/) (2026)
- [Practical Open-Loop Optimistic Planning](https://mlsanity.com/paper/1904.04700/) (2019)
- [Scale-free adaptive planning for deterministic dynamics & discounted rewards](https://mlsanity.com/paper/2604.18312/) (2026)

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

- [Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing](https://mlsanity.com/paper/2609.06484/) (2026)
- [Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation](https://mlsanity.com/paper/2609.19956/) (2026)

## Abstract (arXiv)

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.