Maximum Entropy Monte-Carlo Planning

2019-12-01 · NeurIPS 2019 12 · Chenjun Xiao, Ruitong Huang, Jincheng Mei, Dale Schuurmans, Martin Müller

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.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

Atari Games Decision MakingSequential Decision Making

Methods 이 논문이 사용한 방법론

Monte-Carlo Tree Search Monte-Carlo Tree Search is a planning algorithm that accumulates value estimates obtained from Monte Carlo simulations in order to successively direct simulations towards more…

Softmax The Softmax output function transforms a previous layer's output into a vector of probabilities. It is commonly used for multiclass classification. Given an input vector $x$…

Monte Carlo Tree Search with Boltzmann Exploration

2024-04-11 · NeurIPS 2023 11 · Michael Painter, Mohamed Baioumy, Nick Hawes, Bruno Lacerda

Monte-Carlo Tree Search (MCTS) methods, such as Upper Confidence Bound applied to Trees (UCT), are instrumental to automated planning techniques. However, UCT can be slow to explore an optimal action when it initially ap…

Game of Go

Learning Reward Models for Cooperative Trajectory Planning with Inverse Reinforcement Learning and Monte Carlo Tree Search

2022-02-14 · Karl Kurzer, Matthias Bitzer, J. Marius Zöllner

Cooperative trajectory planning methods for automated vehicles can solve traffic scenarios that require a high degree of cooperation between traffic participants. However, for cooperative systems to integrate into human-…

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

Maximum entropy GFlowNets with soft Q-learning

2023-12-21 · Sobhan Mohammadpour, Emmanuel Bengio, Emma Frejinger, Pierre-Luc Bacon

Generative Flow Networks (GFNs) have emerged as a powerful tool for sampling discrete objects from unnormalized distributions, offering a scalable alternative to Markov Chain Monte Carlo (MCMC) methods. While GFNs draw i…

Q-Learning Reinforcement Learning (RL)

Continuous Monte Carlo Graph Search

2022-10-04 · Kalle Kujanpää, Amin Babadi, Yi Zhao, Juho Kannala 외

Online planning is crucial for high performance in many complex sequential decision-making tasks. Monte Carlo Tree Search (MCTS) employs a principled mechanism for trading off exploration for exploitation for efficient o…

continuous-control Continuous Control Decision Making Sequential Decision Making

Cross-Entropy Games and Frost Training

2026-05-26 · Arthur Renard, Franck Gabriel, Valentin Hartmann, Clément Hongler arxiv

We present Frost Training, a method for improving Monte Carlo-based policy optimization for a large family of LLM-as-a-judge tasks called Cross-Entropy Games. The key idea is to exploit the gradient of the reward functio…