pith. machine review for the scientific record. sign in

arxiv: 2604.19695 · v1 · submitted 2026-04-21 · 💻 cs.LG

Recognition: unknown

Planning in entropy-regularized Markov decision processes and games

Jean-bastien Grill , Omar Darwiche Domingues , Pierre M\'enard , R\'emi Munos , Michal Valko
Authors on Pith no claims yet

Pith reviewed 2026-05-10 03:19 UTC · model grok-4.3

classification 💻 cs.LG
keywords entropy-regularized MDPplanning algorithmsample complexityBellman operator smoothnessvalue function estimationgenerative modeltwo-player gamesMarkov decision processes
0
0 comments X

The pith

SmoothCruiser achieves problem-independent O(1/epsilon^4) sample complexity for value estimation in entropy-regularized MDPs and games by using the smoothness of the regularized Bellman operator.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces SmoothCruiser as a planning algorithm that estimates value functions when a generative model of the environment is available. It relies on entropy regularization to make the Bellman operator smooth, which in turn yields a sample complexity bound of roughly one over epsilon to the fourth that does not grow with other problem parameters. This matters because standard non-regularized planning lacks any known polynomial worst-case sample guarantees. A reader would care if they want reliable planning procedures in settings where regularization is already used to promote exploration or uniqueness of solutions.

Core claim

SmoothCruiser estimates the value function to accuracy epsilon using a number of samples from the generative model that scales as O~(1/epsilon^4) independently of the size or other details of the entropy-regularized MDP or two-player game, by directly exploiting the smoothness property that the entropy term imparts to the Bellman operator.

What carries the argument

SmoothCruiser algorithm, which converts the smoothness of the entropy-regularized Bellman operator into an explicit, problem-independent bound on the number of generative-model queries needed.

If this is right

  • Planning becomes tractable with polynomial samples in any entropy-regularized MDP or game once a generative model exists.
  • The same smoothness argument extends the guarantees from single-agent MDPs to two-player zero-sum games.
  • Value-function estimates can be obtained without the sample cost growing with the number of states or actions.
  • Regularization turns an otherwise intractable planning problem into one with explicit, accuracy-driven sample bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Choosing the regularization strength could trade off the smoothness benefit against the bias introduced in the original objective.
  • The approach might extend to other operators or objectives that induce similar Lipschitz or smoothness properties without explicit entropy terms.
  • In practice, the generative-model assumption could be relaxed by combining SmoothCruiser with model-learning methods that themselves enjoy polynomial sample rates.
  • The result suggests regularization as a general design lever for making planning and reinforcement-learning problems computationally easier.

Load-bearing premise

Entropy regularization must be present to create the required smoothness in the Bellman operator, and the algorithm must have direct access to a generative model that can produce next-state samples on demand.

What would settle it

An explicit entropy-regularized MDP instance together with a generative model where any algorithm, including SmoothCruiser, requires more than order 1/epsilon^4 samples to reach epsilon accuracy in the worst case.

Figures

Figures reproduced from arXiv: 2604.19695 by Jean-bastien Grill, Michal Valko, Omar Darwiche Domingues, Pierre M\'enard, R\'emi Munos.

Figure 1
Figure 1. Figure 1: Visualization of a call to SmoothCruiser(s0, ε0, δ′ ). 3.1 Smooth sailing Algorithm 1 SmoothCruiser Input: (s, ε, δ′ ) ∈ S × R+ × R+ Mλ ← sups∈S |Fs(0)| = λ log K κ ← (1 − √γ)/(KL) Set δ ′ , κ, and Mλ as global parameters Qbs ← estimateQ(s, ε) Output: Fs  Qbs  The most important part of the algorithm is the pro￾cedure sampleV, that returns a low-bias estimate of the value function. Having the estimate of… view at source ↗
Figure 2
Figure 2. Figure 2: Simulated number of calls to the generative model made by [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Number of calls to the generative model made by [PITH_FULL_IMAGE:figures/full_fig_p026_3.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proposes SmoothCruiser, a planning algorithm for estimating the value function in entropy-regularized Markov decision processes and two-player games given access to a generative model. It exploits the smoothness of the Bellman operator induced by entropy regularization to obtain a problem-independent sample complexity of order Õ(1/ε⁴) for ε-accurate estimates, in contrast to the non-regularized setting where no polynomial sample complexity guarantees are known in the worst case.

Significance. If the claimed bound holds, the result would be a meaningful advance in sample-efficient planning for regularized RL and game-theoretic settings. By turning the regularization-induced smoothness into a concrete, problem-independent rate, the work provides a route around known worst-case hardness for non-regularized planning and could inform algorithm design where entropy regularization is already used for exploration or stability.

major comments (1)
  1. [Main complexity theorem and its proof (Section 3)] The central complexity claim (Õ(1/ε⁴) sample complexity) is load-bearing and rests on the smoothness of the regularized Bellman operator. The derivation that converts the smoothness modulus into the stated sample bound, including the precise dependence on the regularization strength and the concentration arguments used, is not presented with sufficient detail to verify the rate or its independence from other problem parameters.
minor comments (2)
  1. [Abstract] The abstract states the complexity result but does not indicate how the regularization parameter enters the smoothness or the final bound; a single clarifying sentence would help readers assess the claim at a glance.
  2. [Preliminaries] Notation for the entropy-regularized value function and the smoothness constant is introduced without an explicit reference to the defining equation; adding a forward pointer would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback on our manuscript. We address the major comment below and will revise the paper to incorporate additional details as suggested.

read point-by-point responses

  1. Referee: [Main complexity theorem and its proof (Section 3)] The central complexity claim (Õ(1/ε⁴) sample complexity) is load-bearing and rests on the smoothness of the regularized Bellman operator. The derivation that converts the smoothness modulus into the stated sample bound, including the precise dependence on the regularization strength and the concentration arguments used, is not presented with sufficient detail to verify the rate or its independence from other problem parameters.

    Authors: We thank the referee for highlighting this important point. We agree that the current presentation of the proof in Section 3 would benefit from expanded detail to make the derivation fully transparent. In the revised manuscript, we will add a step-by-step expansion of how the smoothness modulus of the entropy-regularized Bellman operator (which depends explicitly on the regularization strength τ) is used to obtain the Õ(1/ε⁴) bound. This will include: (i) the precise statement of the smoothness property and its modulus; (ii) the application of concentration inequalities (leveraging boundedness induced by regularization) to control the deviation of the empirical operator; and (iii) the chaining of these to yield the final sample complexity. We will also clarify that the resulting bound is independent of the state-action space cardinality and other problem parameters precisely because the smoothness allows uniform control without problem-dependent covering arguments. The dependence on τ will be stated explicitly, with a note that the bound holds for any fixed τ > 0. These additions will appear in the main text of Section 3 with supporting calculations moved to the appendix for completeness. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The abstract and description present SmoothCruiser as a new algorithm that exploits the known smoothness property of the entropy-regularized Bellman operator to obtain an O~(1/epsilon^4) sample-complexity bound under a generative model. No load-bearing step reduces by definition, by fitting a parameter that is then renamed a prediction, or by a self-citation chain whose cited result itself depends on the target claim. The non-regularized hardness statement is presented as background, not as a derived result internal to the paper. The central claim therefore rests on independent analysis of the regularized operator rather than on circular re-use of its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on access to a generative model and the domain assumption that entropy regularization induces sufficient smoothness in the Bellman operator to enable the stated sample bound; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Entropy regularization promotes smoothness of the Bellman operator
    Invoked directly to obtain the problem-independent O(1/epsilon^4) sample complexity.
  • domain assumption A generative model of the environment is available
    Required for the planning setting and sample complexity analysis.

pith-pipeline@v0.9.0 · 5384 in / 1267 out tokens · 36873 ms · 2026-05-10T03:19:53.150206+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 15 canonical work pages · 1 internal anchor

  1. [1]

    http://researchers.lille.inria.fr/ valko/hp/publications/bartlett2019scale-free Scale-free adaptive planning for deterministic dynamics & discounted rewards

    Peter L Bartlett, Victor Gabillon, Jennifer Healey, and Michal Valko. http://researchers.lille.inria.fr/ valko/hp/publications/bartlett2019scale-free Scale-free adaptive planning for deterministic dynamics & discounted rewards . In International Conference on Machine Learning (ICML), 2019

    2019

  2. [2]

    http://sbubeck.com/COLT10_BM.pdf Open-loop optimistic planning

    Sébastien Bubeck and Rémi Munos. http://sbubeck.com/COLT10_BM.pdf Open-loop optimistic planning . In Conference on Learning Theory (COLT), 2010

    2010

  3. [3]

    https://hal.archives-ouvertes.fr/hal-00756736/document Optimistic planning for Markov decision processes

    Lucian Bu s oniu and Rémi Munos. https://hal.archives-ouvertes.fr/hal-00756736/document Optimistic planning for Markov decision processes . In International Conference on Artificial Intelligence and Statistics (AISTATS), 2012

    2012

  4. [4]

    and Munos, R

    Pierre-Arnaud Coquelin and Rémi Munos. https://arxiv.org/pdf/1408.2028.pdf Bandit algorithms for tree search . In Uncertainty in Artificial Intelligence, 2007

    work page arXiv 2028

  5. [5]

    https://hal.inria.fr/inria-00116992/document Efficient selectivity and backup operators in Monte-Carlo tree search

    Rémi Coulom. https://hal.inria.fr/inria-00116992/document Efficient selectivity and backup operators in Monte-Carlo tree search . Computers and games, 4630: 0 72–83, 2007

    2007

  6. [6]

    https://arxiv.org/pdf/1712.10285.pdf SBEED: Convergent reinforcement learning with nonlinear function approximation

    Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. https://arxiv.org/pdf/1712.10285.pdf SBEED: Convergent reinforcement learning with nonlinear function approximation . In International Conference on Machine Learning (ICML), 2018

    work page arXiv 2018

  7. [7]

    https://www.jair.org/index.php/jair/article/view/10905/26003 Simple regret optimization in online planning for Markov decision processes

    Zohar Feldman and Carmel Domshlak. https://www.jair.org/index.php/jair/article/view/10905/26003 Simple regret optimization in online planning for Markov decision processes . Journal of Artificial Intelligence Research, 2014

    2014

  8. [8]

    https://arxiv.org/pdf/1901.11275.pdf A Theory of regularized Markov decision processes

    Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. https://arxiv.org/pdf/1901.11275.pdf A Theory of regularized Markov decision processes . In International Conference on Machine Learning (ICML), pages 2160--2169, 2019

    work page arXiv 1901

  9. [9]

    https://hal.inria.fr/hal-01389107v3/document Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning

    Jean-Bastien Grill, Michal Valko, and Rémi Munos. https://hal.inria.fr/hal-01389107v3/document Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning . In Neural Information Processing Systems (NeurIPS), 2016

    2016

  10. [10]

    https://arxiv.org/pdf/1702.08165.pdf Reinforcement learning with deep energy-based policies

    Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. https://arxiv.org/pdf/1702.08165.pdf Reinforcement learning with deep energy-based policies . In International Conference on Machine Learning (ICML), 2017

    work page arXiv 2017

  11. [11]

    Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor

    Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. https://arxiv.org/abs/1801.01290 Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor . In International Conference on Machine Learning (ICML), 2018

    work page internal anchor Pith review arXiv 2018

  12. [12]

    https://arxiv.org/pdf/1008.0530.pdf Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor

    Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. https://arxiv.org/pdf/1008.0530.pdf Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor . Journal of the ACM, 60, 2013

    work page arXiv 2013

  13. [13]

    https://hal.archives-ouvertes.fr/hal-00830182/document Optimistic planning of deterministic systems

    Jean-Francois Hren and Rémi Munos. https://hal.archives-ouvertes.fr/hal-00830182/document Optimistic planning of deterministic systems . In European Workshop on Reinforcement Learning, 2008

    2008

  14. [14]

    Ajallooeian, Csaba Szepesv \' a ri, and Martin M \" u ller

    Ruitong Huang, Mohammad M. Ajallooeian, Csaba Szepesv \' a ri, and Martin M \" u ller. https://arxiv.org/pdf/1706.05198.pdf Structured best-arm identification with fixed confidence . In Algorithmic Learning Theory, 2017

    work page arXiv 2017

  15. [15]

    and Koolen, W

    Emilie Kaufmann and Wouter M Koolen. https://arxiv.org/pdf/1706.02986.pdf Monte-carlo tree search by best-arm identification . In Neural Information Processing Systems (NeurIPS), 2017

    work page arXiv 2017

  16. [16]

    Michael Kearns, Yishay Mansour, and Andrew Y. Ng. https://www.cis.upenn.edu/ mkearns/papers/sparsesampling-journal.pdf A sparse sampling algorithm for near-optimal planning in large Markov decision processes . In International Conference on Artificial Intelligence and Statistics (AISTATS), 1999

    1999

  17. [17]

    http://ggp.stanford.edu/readings/uct.pdf Bandit-based Monte-Carlo planning

    Levente Kocsis and Csaba Szepesv \' a ri. http://ggp.stanford.edu/readings/uct.pdf Bandit-based Monte-Carlo planning . In European Conference on Machine Learning (ECML), 2006

    2006

  18. [18]

    and Maillard, O.-A

    Edouard Leurent and Odalric-Ambrym Maillard. https://arxiv.org/pdf/1904.04700.pdf Practical open-loop pptimistic planning . In European Conference on Machine Learning (ECML), 2019

    work page arXiv 1904

  19. [19]

    Asynchronous methods for deep reinforcement learning.arXiv preprint arXiv:1602.01783,

    Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. https://arxiv.org/pdf/1602.01783.pdf Asynchronous methods for deep reinforcement learning . In International Conference on Machine Learning (ICML), 2016

    work page arXiv 2016

  20. [20]

    arXiv preprint arXiv:1705.07798 , year=

    Gergely Neu, Anders Jonsson, and Vicenç G \' o mez. https://ui.adsabs.harvard.edu/abs/2017arXiv170507798N A unified view of entropy-regularized Markov decision processes . In arXiv:1705.07798, 2017

    work page arXiv 2017

  21. [21]

    http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20&path=ASIN/0471619779 Markov Decision Processes: Discrete Stochastic Dynamic Programming

    Martin L Puterman. http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20&path=ASIN/0471619779 Markov Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley & Sons, New York, NY, 1994

    work page arXiv 1994

  22. [22]

    Trust Region Policy Optimization

    John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. https://arxiv.org/pdf/1502.05477.pdf Trust region policy optimization . In International Conference on Machine Learning (ICML), 2015

    work page Pith review arXiv 2015

  23. [23]

    Equivalence between policy gradients and soft Q-learning

    John Schulman, Xi Chen, and Pieter Abbeel. https://ui.adsabs.harvard.edu/abs/2017arXiv170406440S Equivalence between policy gradients and soft Q-learning . In arXiv:1704.06440, 2017

    work page arXiv 2017

  24. [24]

    Richard S. Sutton. Dyna, an integrated architecture for learning, planning, and reacting https://doi.org/10.1145/122344.122377. SIGART Bulletin , 2 0 (4): 0 160--163, 1991

    work page doi:10.1145/122344.122377 1991

  25. [25]

    Sutton and Andrew G

    Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction http://incompleteideas.net/book/the-book-2nd.html. The MIT Press, second edition, 2018

    2018

  26. [26]

    Balázs Sz \" o r \' e nyi, Gunnar Kedenburg, and Rémi Munos. https://papers.nips.cc/paper/5368-optimistic-planning-in-markov-decision-processes-using-a-generative-model.pdf Optimistic planning in Markov decision processes using a generative model . In Neural Information Processing Systems (NeurIPS), 2014

    2014

  27. [27]

    https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1880/2049 Integrating sample-based planning and model-based reinforcement learning

    Thomas J Walsh, Sergiu Goschin, and Michael L Littman. https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1880/2049 Integrating sample-based planning and model-based reinforcement learning . AAAI Conference on Artificial Intelligence (AAAI), 2010

    2049