Planning in entropy-regularized Markov decision processes and games

Jean-Bastien Grill (1, 2) , Omar D Domingues (1) , Pierre Ménard (1) , Rémi Munos (2, 1) , Michal Valko (2, 1)

1 SEQUEL - Sequential Learning
2 DeepMind [Paris]

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/ε 4) for a desired accuracy ε, whereas for non-regularized settings there are no known algorithms with guaranteed polynomial sample complexity in the worst case.

Domaines: Machine Learning [stat.ML]

Jean-Bastien Grill, Omar D Domingues, Pierre Ménard, Rémi Munos, Michal Valko. Planning in entropy-regularized Markov decision processes and games. Neural Information Processing Systems, 2019, Vancouver, Canada. ⟨hal-02387515⟩