TLDR: A new research paper by Schm¨ocker, Dockhorn, and Rosenhahn addresses a critical, often overlooked, issue in Monte Carlo Tree Search (MCTS) when using state and action abstractions. They found that when multiple actions share the same abstract node and UCB value, the implicit random tiebreaking policy is suboptimal. Their proposed UCT (Upper Confidence Bound) intra-abstraction policy significantly outperforms the random approach, offering a more effective and efficient way to select actions within abstract nodes, especially with coarser abstractions, and introduces negligible runtime overhead.
Monte Carlo Tree Search (MCTS) is a widely used algorithm for making decisions, particularly in complex scenarios like games. While powerful, MCTS can sometimes be slow. To make it more efficient, researchers often use “abstractions.” These abstractions work by grouping similar states or actions together, which helps the algorithm share information and simplify its search.
A common way abstractions improve MCTS is by enhancing the Upper Confidence Bound (UCB) value. This value guides the algorithm in deciding which actions to explore next. However, a challenge arises when multiple actions, all originating from the same parent state, are grouped into a single abstract node. In this situation, all these actions would have the exact same UCB value, creating a tie. When a tie occurs, a “tiebreaking rule” is needed to choose which specific action to take.
Interestingly, in many existing abstraction algorithms, such as pruned On the Go Abstractions (pruned OGA), this tiebreaking situation has been largely overlooked, and a random choice was implicitly made. The authors of a new research paper, Robin Schm¨ocker, Alexander Dockhorn, and Bodo Rosenhahn, point out that this isn’t a rare event; these ties happen frequently. They argue that the way these ties are broken, which they call “intra-abstraction policies,” can significantly affect the algorithm’s performance.
In their paper, “Investigating Intra-Abstraction Policies for Non-Exact Abstraction Algorithms,” the researchers introduce a new framework called Alternating State And State-Action Pair Abstractions (ASASAP). This framework helps to unify and understand various abstraction methods. Within this context, they propose and thoroughly evaluate seven different intra-abstraction policies as alternatives to the random approach. These policies include UCT, FIRST, GREEDY, MOST VISITS, LEAST VISITS, LEAST OUTCOMES, and RANDOM GREEDY. Each policy offers a distinct method for selecting an action when multiple options within an abstract node have identical UCB values.
The experimental results are compelling. The random policy, which has been the default, was consistently outperformed by at least one of the new strategies. The UCT (Upper Confidence Bound) policy stood out as the most effective. It either matched or surpassed the random policy’s performance across a wide array of environments and settings. Crucially, UCT achieved these gains with only a minimal increase in the algorithm’s running time.
Also Read:
- AUPO: Enhancing AI Decision-Making with Reward-Based Abstraction
- Rethinking Experience Stitching: How Model Scale Outperforms Algorithmic Bias in Reinforcement Learning
This research underscores the importance of carefully considering how ties are broken within abstract nodes in MCTS. The UCT policy offers a robust and straightforward improvement, especially valuable when using broader, more generalized abstractions. The authors suggest that UCT should become the standard choice for handling these intra-abstraction decisions in MCTS-based abstraction methods. For a deeper dive into their findings, you can access the full research paper here.
