Timezone: »

 
Poster
Maximum Entropy Monte-Carlo Planning
Chenjun Xiao · Ruitong Huang · Jincheng Mei · Dale Schuurmans · Martin Müller

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #215
in Reinforcement Learning and Planning -- Planning »

We develop a new algorithm for online planning in large scale sequential decision problems that improves upon the worst case efficiency of UCT. The idea is to augment Monte-Carlo Tree Search (MCTS) with maximum entropy policy optimization, evaluating each search node by softmax values back-propagated from simulation. To establish the effectiveness of this approach, we first investigate the single-step decision problem, stochastic softmax bandits, and show that softmax values can be estimated at an optimal convergence rate in terms of mean squared error. We then extend this approach to general sequential decision making by developing a general MCTS algorithm, Maximum Entropy for Tree Search (MENTS). We prove that the probability of MENTS failing to identify the best decision at the root decays exponentially, which fundamentally improves the polynomial convergence rate of UCT. Our experimental results also demonstrate that MENTS is more sample efficient than UCT in both synthetic problems and Atari 2600 games.

Keywords: Reinforcement Learning and Planning · Planning · Reinforcement Learning and Planning
[ Paper]  [ Poster] 

Author Information

Chenjun Xiao (University of Alberta)
Ruitong Huang (Borealis AI)
Jincheng Mei (University of Alberta)
Dale Schuurmans (Google)
Martin Müller (University of Alberta)

More from the Same Authors