Monte Carlo Tree Search (MCTS) revolutionized AI for games like Go, but it faces a fundamental "cold start" problem. In the early stages of a search, the algorithm has very few simulations to guide its decisions. With a high branching factor, most moves have zero data, forcing the algorithm to choose blindly.
Rapid Action Value Estimation (RAVE) solves this by sharing information across different branches of the search tree. It operates on a simple but powerful intuition: if a move is strong in one sequence of play, it is likely strong in another, regardless of exactly when it was played.
The All-Moves-As-First Heuristic
Standard MCTS updates the value of a move only for the specific state where it was chosen. However, as David Silver et al. describe in Combining online and offline knowledge in UCT, we can use the all-moves-as-first (AMAF) heuristic to extract more information from every simulation.
In AMAF, if a move $a$ is played at any point during a simulation, the algorithm updates the statistics for $a$ as if it had been played immediately at the current node. This allows the search to "generalize" move quality across different branches. As Sylvain Gelly et al. explain in The grand challenge of computer Go: Monte Carlo tree search and extensions, RAVE recognizes that the value of a move is often independent of its specific timing within a sequence.
Trading Bias for Variance
The core of RAVE is a classic bias-variance tradeoff.
- Standard MCTS provides an unbiased estimate of a move's value, but it has high variance because it requires many simulations to converge.
- RAVE provides a biased estimate (since the order of moves actually does matter in games), but it has low variance because it aggregates data from many more simulations.
In Achieving Master Level Play in 9 x 9 Computer Go, Sylvain Gelly et al. demonstrate that accepting this bias early in the search accelerates convergence. By using RAVE estimates to bias the search when data is sparse, the algorithm quickly identifies promising regions of the tree. As more simulations are performed, the algorithm gradually shifts its weight from the biased RAVE estimate to the unbiased MCTS estimate.
Generalizing Beyond Go
While RAVE was popularized in Go, its mechanism for "global action-value averaging" is broadly applicable. Hilmar Finnsson et al. show in Learning Simulation Control in General Game-Playing Agents that tracking the success rate of moves across all simulations provides a computationally inexpensive heuristic for General Game Playing (GGP).
The technique has proven effective in various domains:
- NoGo: Cheng-Wei Chou et al. found in Revisiting Monte-Carlo Tree Search on a Normal Form Game: NoGo that RAVE's ability to leverage information from simulations passing through a move was more impactful than simply increasing the number of simulations.
- Havannah: Fabien Teytaud demonstrated in Du jeu de Go au Havannah : variantes d'UCT et coups décisifs that RAVE helps manage the massive action spaces of complex board games, though it requires careful parameter tuning to remain effective as simulation counts increase.
- Feature Selection: Even outside of games, Romaric Gaudel et al. applied RAVE in Feature Selection as a One-Player Game to maintain global estimates of a feature's utility across different subsets, navigating astronomical search spaces more efficiently.
By treating every move in a simulation as a piece of evidence for that move's general utility, RAVE allows search algorithms to "see" the potential of an action long before the standard search would have enough data to confirm it.
Key Foundational Work
Combining online and offline knowledge in UCT (2007) — contributed 2 concept elements to this direction.
Achieving Master Level Play in 9 x 9 Computer Go (2008) — contributed 2 concept elements to this direction.