Planning in entropy-regularized Markov decision processes and games

Jean-Bastien Grill, Omar Darwiche Domingues, Pierre Ménard, Rémi Munos, Michal ValkoNeurIPS 2019 · OpenReview

TL;DR

Researchers have introduced SmoothCruiser, a new planning algorithm that achieves a polynomial sample complexity of $\tilde{\mathcal{O}}(1/\epsilon^4)$ for estimating value functions in Markov Decision Processes (MDPs) and two-player games. By applying entropy regularization, the authors "smooth out" the mathematical landscape of the problem, turning a traditionally non-polynomial search into a much more efficient, problem-independent process.

The Challenge of Planning in Large State Spaces

In reinforcement learning and AI, "planning" is often described as "thinking before acting." An agent uses a generative model (a simulator or "oracle") to look ahead and estimate the value of different actions. However, in large or continuous state spaces, this look-ahead process usually hits a wall known as the "curse of dimensionality."

Standard algorithms like Sparse Sampling (SSA) have a sample complexity that is non-polynomial—meaning as you ask for more precision ($\epsilon$), the number of required simulations explodes. Other popular methods, like UCT (the backbone of many game-playing AIs), can even perform exponentially poorly in worst-case scenarios. The gap addressed by this research is the lack of a planning algorithm with guaranteed polynomial sample complexity that doesn't depend on specific, often restrictive, properties of the environment.

Methods: Smoothing the Landscape

The authors introduce SmoothCruiser, which relies on a clever mathematical trick: entropy regularization.

In a standard MDP, the Bellman operator (the math used to update value estimates) uses a max function, which is "pointy" and non-differentiable. By adding an entropy term to the rewards, the max is replaced by a LogSumExp function. This makes the operator smooth (specifically, $L$-smooth).

SmoothCruiser exploits this smoothness through two recursive procedures:

  1. estimateQ: Averages multiple samples to get a rough estimate of the action-value function.
  2. sampleV: Uses the smoothness property to create a local linear approximation of the value function.
Pseudocode for the sampleV and estimateQ algorithms, the core recursive components of SmoothCruiser.

Because the landscape is smooth, a linear approximation at a coarse resolution is "good enough" to guide the search for higher precision. This allows the algorithm to use fewer samples as it recurses deeper into the planning tree, eventually leading to the $\tilde{\mathcal{O}}(1/\epsilon^4)$ complexity bound.

Tree diagram illustrating the recursive structure of SmoothCruiser, showing how the search strategy changes based on the precision threshold.

Key Insights and Ideas

  • Regularization as a Computational Tool: Usually, entropy regularization is used in Reinforcement Learning to encourage exploration or improve robustness. This paper provides a new "why": it fundamentally changes the computational complexity of planning, making it easier to solve.
  • Smoothing the "Max": The transition from a hard max to a smooth LogSumExp allows the algorithm to use tools from smooth optimization (like Taylor expansions) in a domain where they typically don't apply.
  • Problem-Independent Bounds: Unlike previous algorithms whose performance might degrade based on the specific "branching factor" or "depth" of a problem, SmoothCruiser’s complexity is tied primarily to the desired accuracy $\epsilon$, making it more predictable across different environments.
  • MCTS Connection: The authors show that SmoothCruiser can be viewed as a specific instance of Monte-Carlo Tree Search (MCTS), providing a theoretical bridge between high-level heuristic searches and rigorous complexity bounds.

Key Results

  • Polynomial Sample Complexity: The headline result is the proof that SmoothCruiser requires only $\tilde{\mathcal{O}}(1/\epsilon^4)$ oracle calls to reach an accuracy of $\epsilon$.
  • Consistency: The authors prove that the algorithm is consistent, meaning the estimate it produces will converge to the true regularized value with high probability.
  • Breaking the Non-Polynomial Barrier: For non-regularized settings, there are no known algorithms with guaranteed polynomial sample complexity in the worst case. SmoothCruiser proves that by slightly changing the objective (adding regularization), we can achieve a massive leap in theoretical efficiency.

Limitations and Future Work

  • Practicality vs. Theory: The authors candidly admit that SmoothCruiser makes a "large amount of recursive calls," which may make it impractical for real-time use in its current form. It is more of a theoretical "existence proof" than a ready-to-use library.
  • The Regularization Trade-off: The algorithm estimates the regularized value function. While this is often a good proxy for the optimal value, it is not exactly the same. As the regularization constant $\lambda$ goes to zero (to get closer to the "true" value), the smoothness disappears, and the complexity returns to being non-polynomial.
  • Future Directions: The authors suggest exploring adaptive regularization—starting with high smoothing to navigate the search tree quickly and gradually reducing it to gain precision, potentially combining the best of both worlds.

Summary updated

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 SmoothCruiser. SmoothCruiser makes use of the smoothness of the Bellman operator promoted by the regularization to achieve problem-independent sample complexity of order $\tilde{\mathcal{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.
BibTeX
@inproceedings{grill2019planning,
  author = {Jean-Bastien Grill and Omar Darwiche Domingues and Pierre Ménard and Rémi Munos and Michal Valko},
  title = {{Planning in entropy-regularized Markov decision processes and games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=kRspHjQ4Xod},
}
Figure