Planning in entropy-regularized Markov decision processes and games
SmoothCruiser is a new planning algorithm for estimating value functions in entropy-regularized Markov decision processes and games. It exploits the smoothness of the regularized Bellman operator to achieve problem-independent sample complexity of Oe(1/ε4) for desired accuracy ε. This offers a polynomial sample complexity guarantee where none was previously known.