Technical Summary: Revisiting Regularized Policy Optimization for Stable and Efficient Reinforcement Learning in Two-Player Games

Problem Statement

Two-player zero-sum games, particularly board games, have served as traditional benchmarks for reinforcement learning (RL). While search-based methods like AlphaZero (Silver et al., 2018) have achieved superhuman performance by combining deep neural networks with look-ahead search (e.g., Monte-Carlo Tree Search, MCTS), they incur substantial computational costs. Training AlphaZero, for instance, reportedly requires over 10 GPU-years (Silver et al., 2018; Tian et al., 2019). This resource intensity hinders reproducibility and practical application in resource-constrained environments (Zhao et al., 2022).

Although recent studies have attempted to reduce the computational burden of search-based methods by limiting tree depth or rollout counts (Hessel et al., 2021; Danihelka et al., 2022), they still fundamentally rely on look-ahead search. Conversely, model-free RL methods, which are efficient in robotics and continuous control, have not been fully explored in board games due to perceived instability in multi-agent self-play settings. The central question addressed by this work is: Can a pure model-free RL algorithm achieve stable and competitive learning in two-player games with significantly fewer training resources than search-based counterparts?

Methodology

The authors propose KLENT (KL and Entropy Regularized Policy Optimization), a model-free RL algorithm that eliminates the need for MCTS during training. The approach is grounded in revisiting regularized policy optimization with two specific components: reverse Kullback-Leibler (KL) regularization and entropy regularization.

1. Policy Update Rule

The core of KLENT is a regularized policy optimization problem defined as:
$$\max_{\pi'} \mathbb{E}_{A \sim \pi'(\cdot|s)}[Q^\pi(s, A)] - \beta D_{KL}(\pi'(\cdot|s) \parallel \pi(\cdot|s)) + \alpha H(\pi'(\cdot|s))$$
where:

• $\pi'$ is the new policy, and $\pi$ is the prior policy.
• $D_{KL}(\pi' \parallel \pi)$ is the reverse KL divergence, promoting gradual policy updates to handle non-stationarity in self-play.
• $H(\pi')$ is the entropy, encouraging sustained exploration to prevent overfitting to the agent's own policy.
• $\alpha$ and $\beta$ are non-negative hyperparameters.

Given the finite action space of board games, the optimal policy $\pi'$ admits a closed-form analytical solution:
$$\pi'(a|s) = \frac{1}{Z(s)} \exp\left( \frac{Q^\pi(s, a) + \beta \log \pi(a|s)}{\alpha + \beta} \right)$$
In KLENT, a neural network $\pi_\theta$ is trained to minimize the cross-entropy between its output and this analytically derived target $\pi'$.

2. Value Function Learning

Unlike search-based methods that estimate action values via MCTS backups, KLENT directly parameterizes the action-value function $Q^\pi(s, a)$ using a neural network. To stabilize learning and manage the bias-variance trade-off, the algorithm uses $\lambda$-returns ($G^\lambda$) as the learning target for the value function, rather than standard Monte Carlo returns ($\lambda=1$). Preliminary experiments indicated that an intermediate $\lambda \in (0, 1)$ minimizes the sum of squared bias and variance better than $\lambda=1$.

3. Algorithm Structure

KLENT alternates between a self-play phase (collecting on-policy data) and a fitting phase (updating network parameters). The loss function simultaneously optimizes the policy and action-value networks:
$$L(\theta) = \mathbb{E}_D \left[ -\sum_{a \in A} \pi'(a|S) \log \pi_\theta(a|S) + (Q_\theta(S, A) - G^\lambda)^2 \right]$$
Crucially, KLENT requires no tree search during training, relying solely on the neural network's predictions and the analytical policy update.

Key Contributions

The paper makes three primary contributions, focusing on the theoretical and empirical characterization of this specific regularization combination rather than proposing entirely new algorithmic ingredients:

1. Algorithmic Formulation: The authors derive a practical model-free RL algorithm (KLENT) based on the combination of reverse-KL and entropy regularization, providing a closed-form policy update rule.
2. Theoretical Guarantees: Novel convergence guarantees are provided for the policy update rule in two settings:
   • Normal-Form Games: The paper proves local linear convergence to a unique fixed point under the condition $\alpha(\alpha + 2\beta) > \|R\|_2^2/4$. This condition covers a broader range of regularization coefficients than previous results (e.g., Sokota et al., 2022).
   • Finite-Length Games: The authors prove that the KLENT policy converges to an entropy-regularized optimal policy (Quantal Response Equilibrium) via backward induction, assuming a finite game horizon.
3. Empirical Validation: Comprehensive experiments on five board games (Animal Shogi, Gardner Chess, 9x9 Go, Hex, and Othello) demonstrate that KLENT achieves significantly higher training efficiency than existing search-based and model-free baselines.

Results

Training Efficiency

Experiments show that KLENT learns more efficiently than existing methods across all tested environments.

• Performance Gain: On average, KLENT achieved up to 4x higher training efficiency compared to Gumbel AlphaZero (the strongest search-based baseline in the study). For example, Gumbel AlphaZero required 300 million simulator evaluations to reach a 50% win rate, whereas KLENT required only 75 million.
• Scalability: The efficiency gap widens in games with higher branching factors (e.g., 9x9 Go, Hex), where search-based methods require substantial simulator budgets. KLENT's advantage is attributed to avoiding look-ahead search and using stable $\lambda$-returns.
• Large-Scale Performance: In 19x19 Go, KLENT maintained competitive learning efficiency compared to AlphaZero, despite the increased complexity.

Ablation Studies

The study validates the necessity of three key techniques:

• Reverse-KL Regularization: Removing this (setting $\beta=0$) leads to abrupt policy updates and degraded performance, particularly in 9x9 Go.
• Entropy Regularization: Removing this (setting $\alpha=0$) causes the policy to become overly deterministic (entropy drops to near zero), leading to unstable learning and performance collapse.
• $\lambda$-Returns: Replacing $\lambda$-returns with 1-step backups or Monte Carlo returns resulted in performance drops, confirming the importance of balancing bias and variance.

Test-Time Performance

When equipped with test-time MCTS (800 rollouts), KLENT agents achieved high win rates against baselines, outperforming AlphaZero and Gumbel AlphaZero in head-to-head matches on 9x9 Go and 19x19 Go.

Significance and Claims

The authors position this work as a demonstration that properly revisiting existing regularization techniques can lead to stable and efficient learning in domains long dominated by search-based methods.

• Modest Claims: The paper explicitly states that its main contribution is not a new algorithmic ingredient but a new theoretical and empirical characterization of regularized policy optimization in two-player games.
• Limitations: The authors acknowledge that while KLENT achieves high efficiency, it does not necessarily guarantee superior asymptotic performance when unlimited computational resources are available. They do not preclude the effectiveness of search-based approaches like AlphaZero when massive resources (e.g., thousands of GPUs) are accessible.
• Broader Impact: The authors suggest that the underlying assumption (finite-action MDP) applies to real-world problems such as discrete optimization, algorithmic discovery, and mathematical proving, where search-based methods are currently prevalent. They hope this work encourages extending such efficient, model-free approaches to other fields.

In summary, KLENT offers a computationally efficient alternative to search-based RL for board games, achieving competitive performance with a fraction of the training resources by leveraging the stability of reverse-KL and entropy regularization.