What is Monte Carlo Beam Search in neural networks?

Question

Monte Carlo Beam Search is often referenced in neural network and reinforcement learning research. What is it and how is it different than Monte Carlo search.

Answer 1

Monte Carlo tree search a best first, rollout based tree search algorithm, which is state of the art for multiple games. It works by expanding search tree based on random sampling of the search space.

Beam search expands only the most promising node in a limited set. It is widely used in sequence-based tasks such as NLP and music generation. One main advantage of beam search is that it maintains tractability for large systems where the number of possible outcomes can exceed memory limits.

Monte Carlo Beam Search, introduced in 2012 by two papers by Cazenave and Baier, et al., extends Nested Monte Carlo Search, where games are played choosing each move based on results of a lower level of Nested Monte Carlo Search. The lowest level is a playout (game where moves are played at random).

Quoting the paper:

The size of a beam is fixed for each level. Only the best playouts are kept at a given level.

For example, a beam search size 2 means that at each move, the best two positions among all children are kept. This is much more memory efficient than keeping all of the children.