Source-linked AI summary
Planning in entropy-regularized Markov decision processes and games
Jean-Bastien Grill, Omar Darwiche Domingues, Pierre Ménard, Rémi Munos, Michal Valko
TL;DR
The paper addresses how to estimate state values for entropy-regularized MDPs and two-player games from a generative model. It introduces SmoothCruiser, which exploits smooth Bellman operators, and reports problem-independent sample complexity of order O~(1/ε^4). The method is theoretically scoped to arbitrary state spaces but is described as impractical in most situations because of many recursive calls.
Problem
The paper seeks accurate value estimates for individual states in MDPs and games using oracle samples, including settings where existing non-regularized planning methods lack guaranteed polynomial worst-case sample complexity.
Method
SmoothCruiser recursively estimates action values and applies the smooth Bellman operator induced by entropy regularization.
Results
O~(1/ε^4) is the problem-independent sample-complexity order obtained for desired precision ε.
Takeaways & Limitations
The guarantee applies to entropy-regularized MDPs and discounted games with arbitrary state-space cardinality, and extends to smooth Bellman operators with nonnegative gradients.
Takeaways & Limitations
SmoothCruiser makes large numbers of recursive calls, making it impractical in most situations; it also assumes access to a generative model.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies state-value planning in MDPs and two-player games using a generative model, targeting accuracy without dependence on state-space size. SmoothCruiser exploits entropy-induced Bellman smoothness to obtain problem-independent polynomial sample complexity.
- Problem setting: Planning uses an oracle that returns rewards and next states for queried state-action pairs in MDPs and two-player turn-based zero-sum games.The total number of oracle calls is the sample complexity.
- Problem setting: Estimating one fixed state value can avoid dependence on the size of the state space, including when the space is very large or continuous.The algorithm must be rerun when a new state is encountered.
- Contribution: SmoothCruiser estimates a value function at a given state under smoothness conditions induced by entropy-regularized rewards.The approach is designed for planning problems whose Bellman operators satisfy the required smoothness.
- Contribution: O~(1/ε^4) is the claimed problem-independent sample-complexity order for the desired precision ε.The guarantee is presented for the regularized planning setting.
- Prior limitations: Existing sparse-sampling methods have non-polynomial dependence on 1/ε, while UCT can be worse than exponential in 1/ε in some environments.These limitations are associated with uniform search or exploration issues.
2 Setting and motivation
The setting formalizes MDPs and turn-based zero-sum games with finite actions, arbitrary state spaces, and oracle access to reward and transition samples. Entropy regularization smooths max/min Bellman operations, enabling SmoothCruiser to interpolate between strongly regularized and unregularized planning regimes.
- Setting: MDPs and two-player games are modeled with states, finite actions, transitions, rewards, and a discount factor, while the state space may be arbitrary.Games can be represented as MDPs with an augmented state space indicating the player to move.
- Regularization: Entropy-regularized values replace max and min operations with LogSumExpλ and −LogSumExp−λ, respectively, producing smooth Bellman operators.The approximation error between LogSumExpλ and max is bounded by λ log K.
- Regularization: The Bellman function Fs is L-smooth and has a nonnegative, unit-ℓ1 gradient, which defines a probability distribution.These properties are the structural assumptions exploited by the algorithm.
- Setting: The learner accesses an independent generative-model sample of reward and next state for any queried state-action pair.The oracle is assumed available for arbitrary state-action pairs.
- Planning regimes: Strong regularization yields O~(1/ε^2) oracle calls through linearity and Monte Carlo trajectory sampling, whereas no regularization leads to recursive sparse sampling.The unregularized construction uses progressively finer estimates to reach depth H = O(log(1/ε)).
- SmoothCruiser: SmoothCruiser recursively combines sampleV and estimateQ, then applies Fs to the estimated Q-vector to produce the value estimate.The procedure uses the smoothness assumption to interpolate between the two extreme regularization cases.
3 SmoothCruiser
SmoothCruiser recursively estimates state values and action values, using smooth Bellman operators to improve accuracy allocation and sample efficiency. Its key mechanism linearizes the regularizer below a threshold, while retaining sampling-based estimation above it.
- Core procedures: SmoothCruiser alternates sampleV, which produces a low-bias value estimate, and estimateQ, which averages sampleV outputs to estimate action values.The final estimate is Fs applied to the estimated Q-vector, with 1-Lipschitzness transferring Q-estimation accuracy to value accuracy.
- Accuracy regimes: The algorithm divides target accuracies around κ ≜ (1 − √γ)/(KL), using direct estimation above κ and smooth linear approximations below κ.The threshold marks the largest accuracy scale at which linear approximation of Fs supports a good estimate.
- Smoothness step: For ε < κ, SmoothCruiser estimates Q with precision √κε and uses a local linear approximation of Fs to obtain an O(ε)-accurate value estimate.This replaces the more expensive O(1/ε^2) sampling requirement with a smoother recursive step.
- Sample complexity: The recursion uses progressively coarser accuracies, with one sampleV call making O(1/ε) recursive calls at accuracy O(√ε), yielding total sample complexity O(1/ε^4).The displayed recursion captures the product of successive accuracy-dependent costs.
- MCTS analogy: SmoothCruiser has an analogy to Monte-Carlo tree search: sampleV acts as search, estimateQ supports action selection, and sparse sampling evaluates leaves.The analogy identifies the corresponding planning components rather than changing the algorithm’s guarantees.
4 Theoretical guarantees
SmoothCruiser has deterministic, problem-independent oracle complexity and provides a high-probability approximation guarantee. Regularization gives a polynomial dependence on 1/ε whose exponent is independent of γ, unlike the non-regularized comparison.
- Complexity guarantee: SmoothCruiser’s sample complexity is deterministic and problem independent because its oracle-call count does not depend on oracle outcomes.The algorithm is non-adaptive and therefore makes the same number of calls for fixed ε and δ′.
- Theorem 1: Theorem 1 bounds the oracle calls with constants depending only on K, L, and γ.The exact constants are given in the appendix.
- Accuracy guarantee: For any δ′ satisfying δ′n(ε, δ′) ≤ δ, the output is an (ε, δ)-correct approximation of V(s).The consistency result supplies a suitable δ′ for any desired ε and δ.
- Regularization effect: Entropy-regularized values approximate non-regularized values within λ log K/(1 − γ) uniformly over states.This follows from the 1-Lipschitz property and the LogSumExp approximation to max.
- Comparison: For regularized problems, the sample-complexity exponent is independent of γ, whereas the non-regularized lower-bound exponent grows as γ approaches 1.The comparison concerns different estimated values because regularization changes the objective.
5 Generalization of SmoothCruiser
The analysis extends beyond entropy regularization to value functions defined by smooth Bellman operators with nonnegative gradients. The guarantee applies whenever the function family satisfies the stated differentiability, gradient, and smoothness conditions.
- General conditions: The theoretical results apply to any state-indexed function family Fs satisfying the listed conditions, not only LogSumExp.The paper states differentiability, bounded nonzero gradient norm, nonnegative gradients, and L-smoothness.
- Algorithmic modification: When ε < κ, the generalized procedure modifies sampleV’s output and action-sampling rule.These changes adapt the algorithm to the broader function class.
- Scope: SmoothCruiser can handle more general regularization schemes when their Bellman operators satisfy these assumptions.The paper gives an example of such a scheme in Appendix E.
6 Conclusion
The paper presents SmoothCruiser as a problem-independent planner for smooth Bellman operators, with O(1/ε^4) sample complexity over arbitrary-cardinality state spaces. It interprets entropy regularization as a smooth relaxation that improves precision-dependent planning complexity, while noting substantial computational cost.
- Conclusion: SmoothCruiser estimates values in entropy-regularized MDPs and discounted games, and more generally under smooth Bellman operators with nonnegative gradients.The guarantee covers state spaces of arbitrary cardinality.
- Conclusion: The algorithm achieves polynomial sample complexity of order O(1/ε^4), with ε denoting the desired precision.The stated guarantee is problem independent.
- Interpretation: Entropy regularization can be viewed as a smooth relaxation of planning that permits faster estimation of an approximate value function.The approximation differs from the non-regularized value by a regularization-dependent amount discussed in the theoretical analysis.
- Limitation and outlook: SmoothCruiser makes many recursive calls and is impractical in most situations, despite its role in understanding how regularization speeds planning.The authors suggest its connection to Monte-Carlo tree search may inspire more practical algorithms.
B Sample complexity
The sample-complexity analysis bounds SmoothCruiser’s recursive and oracle calls across accuracy regimes, culminating in a polynomial guarantee for estimating the value function.
- Theorem 1 bounds SmoothCruiser’s oracle calls for any state and accuracy parameters.
- The number of recursive sampleV calls equals the number of oracle calls, allowing the recursive bounds to establish SmoothCruiser’s sample-complexity bound.
- Lemma 1 is proved by induction on the recursion depth h and bounds nsampleV(ε, δ′) by B(ε).
- Theorem 2 states that SmoothCruiser’s output satisfies the desired value-estimation guarantee with sample complexity of order O(1/ε^(4+c)) for any c > 0.
- The analysis separates ε ≥ κ and ε < κ, using Proposition 1 for the uniform-sampling regime and Lemma 1 for the smaller-error regime.
C.2 Proofs
The proofs establish that recursive value estimates are controlled through boundedness, independence, concentration, and separate treatment of the algorithm’s accuracy regimes.
- Lemma 2 analyzes bVε(s) = sampleV(s, ε) by induction over the recursion depth h.
- The proof bounds the random variables used in estimation and establishes their conditional independence before applying Hoeffding’s inequality.
- The final theorem states that the SmoothCruiser estimate satisfies the required high-probability accuracy guarantee.
- Theorem 2 selects δ′ as a function of ε and δ so that the failure probability remains at most δ while retaining polynomial dependence on ε.
D Auxiliary results
The auxiliary results provide analytic properties of the smoothing map and justify the use of LogSumExpλ and related regularizations in the framework.
- Fact 1 bounds Fs(x) by the infinity norm of x plus the supremum of |Fs(0)|.
- Clipping preserves the infinity-norm error when the comparison vector lies in the clipping interval.
- The proof decomposes a bound into terms whose asymptotic orders establish the stated sample-complexity result.
- The framework focuses on LogSumExpλ but also applies to any max approximation satisfying the listed Section 5 properties.
- The analyzed smooth approximation has gradient ∇QF(Q) = π⋆ and is shown to be L-smooth on the relevant compact domain.
F.1 Checking the sample complexity guarantee
The experiments check SmoothCruiser’s theoretical sample-complexity bound by comparing simulated oracle calls with the bound and with Sparse Sampling.
- Figure 2 plots simulated nsampleV(ε, δ′) calls against 1/ε, the Lemma 1 theoretical bound, and Sparse Sampling’s required calls.
- The simulated values are obtained by computing the specified recurrence for several ε values.
- For relative error 0.017, fewer generative-model samples are required as regularization λ increases.
- For small λ, SmoothCruiser has no advantage over Sparse Sampling, while its advantage becomes very large as λ grows.
F.2 Checking the consistency guarantee
This section checks SmoothCruiser’s consistency guarantee through a simplified experiment using noisy true Q-function values and simulated estimates across environments.
- SmoothCruiser’s sanity check replaces estimateQ calls with the true Q function plus accuracy-dependent noise, producing sampleVcheck.This isolates the computationally costly selectAction and evaluateLeaf operations that rely on Q-function estimates.
- λ = (1 + λ log K)/(1 −γ) is used as an upper bound on the regularized value function.
- Table 1 reports simulated values of b∆(s, ε) and their standard deviations across environments.The simulations use ε = 0.35, Nsim = 32723, γ = 0.2, and λ = 10.
- The simulation count Nsim was selected so that b∆(s, ε) is close to its mean using Hoeffding’s inequality and a high-probability boundedness assumption.The boundedness assumption is attributed to Lemma 2.
- The experiment code is publicly available in the SmoothCruiser-check repository.