Search-based Reinforcement Learning through Bandit Linear Optimization

Milan Peelman, Antoon Bronselaer, Guy De TréIJCAI 2022 · DOI

Abstract

While AlphaZero has achieved superhuman performance in sequential games like Chess and Go, its underlying search algorithm, Polynomial Upper Confidence Bounds for Trees (PUCT), faces challenges in simultaneous move environments. This paper establishes a mathematical equivalence between PUCT and log-barrier regularization. By extending this framework to Bandit Linear Optimization (BLO) with Tsallis entropy regularization ($\alpha=0.5$), the authors introduce a new algorithm that guarantees convergence to a Nash equilibrium and achieves theoretically optimal regret. Empirical results on the "Pod Pursuit" benchmark demonstrate that BLO significantly outperforms standard AlphaZero, particularly under constrained search budgets.

Introduction

Reinforcement learning (RL) combined with Monte-Carlo Tree Search (MCTS) has revolutionized artificial intelligence in sequential games. However, simultaneous move games—where players act concurrently—present a unique challenge. In these settings, the standard PUCT algorithm used by AlphaZero does not guarantee convergence to a Nash equilibrium, a state where no player can improve their outcome by unilaterally changing their strategy. This paper addresses these limitations by bridging the gap between MCTS and the field of Bandit Linear Optimization.

Theoretical Framework: PUCT as Regularization

A key contribution of this work is the formal proof that action selection in PUCT is an approximation of a policy optimization problem regularized by a "log-barrier." This log-barrier is mathematically equivalent to Tsallis entropy with a parameter $\alpha=0$. This insight is transformative because it allows researchers to apply decades of "Bandit" mathematics to Reinforcement Learning search processes.

The BLO-Alpha0.5 Algorithm

Building on this link, the authors propose the Bandit Linear Optimization (BLO) framework. Drawing from bandit theory, they show that setting the Tsallis parameter to $\alpha=0.5$ (corresponding to the squared Hellinger distance) provides the theoretically optimal regret bound of $O(\sqrt{KT})$. This specific value of $\alpha$ acts as a "sweet spot," creating a hybrid strategy that balances the strong exploration of UCT with the effective use of prior knowledge found in PUCT.

To make this practical, the authors developed a computationally efficient method to solve the resulting convex optimization problem using a dichotomic search. This allows BLO to be used in real-time game-playing scenarios without significant overhead.

Strategy Averaging and Consistency

Unlike traditional MCTS, which typically uses empirical visit counts to decide the final move, the BLO method stores and utilizes a log-weighted average of the optimized strategies found during the search. This weighting scheme is crucial; it allows the agent to "forget" early, sub-optimal search results more quickly, leading to faster convergence. This ensures the algorithm is "Hannan consistent," meaning it does not have regrets in the long run and reliably converges toward a Nash equilibrium in adversarial settings.

Experimental Evaluation: Pod Pursuit

To test the efficacy of BLO, the researchers utilized Pod Pursuit, a zero-sum, two-player simultaneous move game adapted from the "Mad Pod Racing" bot-programming game on the CodinGame platform. The environment features continuous state and action spaces governed by 2D physics.

Initial configuration of the Pod Pursuit benchmark, showing pods and checkpoints.

In this benchmark, one player (the pursuer) attempts to reach checkpoints while the other (the evader) tries to block or intercept them. The game requires complex tactical reasoning, including the use of "shielding" to change a pod's mass and momentum to gain a physical advantage.

Key Results and Insights

The study compared three primary variants: standard AlphaZero (PUCT), BLO-Alpha0 (the BLO framework using log-barrier), and BLO-Alpha0.5.

  • Superior Performance: BLO-Alpha0.5 consistently achieved significantly higher Elo ratings than standard AlphaZero across various tests.
  • Search Efficiency: The performance gap was most dramatic when the "search budget" (the number of iterations allowed per move) was low, such as 50 iterations per turn. BLO-Alpha0.5 demonstrated much faster learning and reached higher peak performance than the standard approach.
  • Robustness: Even at higher search budgets (200 iterations), the BLO algorithms maintained a clear lead. This suggests that a more mathematically precise search strategy provides benefits regardless of the available compute power.

Conclusion

By reframing AlphaZero's search as a regularized optimization problem, this research provides a robust theoretical foundation for mastering simultaneous move games. The transition from log-barrier to Tsallis entropy ($\alpha=0.5$) achieves optimal regret and superior empirical performance. Future work will explore the generalization of BLO to non-adversarial domains, such as cooperative multi-agent systems or single-agent tasks, and test its performance in more complex environments like real-time strategy games or poker.

Summary updated

BibTeX
@inproceedings{peelman2022search,
  author = {Milan Peelman and Antoon Bronselaer and Guy De Tré},
  title = {{Search-based Reinforcement Learning through Bandit Linear Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/469},
}
Figure