Planning in entropy-regularized Markov decision processes and games

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.

• AN
  Agence Nationale de la Recherche

  Awards: ANR-16-CE23-0003, CE23-0003
• MD
  Ministère de l'Education Nationale, de l'Enseignement Superieur et de la Recherche
• FM
  Fondation Mathématique Jacques Hadamard
• OV
  Otto von Guericke University Magdeburg
• C
  CHIST-ERA