Manipulating the Distributions of Experience used for Self-Play Learning in Expert Iteration

Dennis J. N. J. Soemers, Éric Piette, Matthew Stephenson, Cameron Browne

Abstract

Expert Iteration (ExIt) is a powerful framework for self-play learning, famously utilized in systems like AlphaZero. However, standard ExIt typically samples experience uniformly from a replay buffer, which can lead to inefficiencies due to the over-representation of long games and redundant training on "easy" states. This paper investigates three techniques to optimize experience distributions: Weighting according to Episode Durations (WED), Prioritized Experience Replay (PER), and Cross-Entropy Exploration (CEE). Evaluated across 14 diverse board games in the Ludii system, these methods—particularly WED—demonstrate significant improvements in learning speed and overall performance compared to standard ExIt.

Introduction

In Expert Iteration, an "apprentice" (typically a neural network) learns to mimic an "expert" (a search algorithm like Monte-Carlo Tree Search). While this cycle of self-play and improvement is effective, the quality of the training data is paramount. Standard approaches often treat every state encountered during self-play as equally important. This research asks whether some experiences are more valuable than others and proposes methods to prioritize high-signal data.

The Challenge of Uniform Sampling

Uniform sampling in ExIt faces two primary issues:

  1. Over-representation of Long Games: Long, drawn-out matches contribute significantly more states to the replay buffer than short, decisive ones. This biases the apprentice toward mid-game "slogs" rather than critical opening or endgame transitions.
  2. Low Information Density: Many states in a game are redundant. Training on states where the apprentice already aligns with the expert provides little new information, wasting computational resources.

Proposed Experience Manipulation Techniques

The authors propose three distinct extensions to the ExIt framework:

  • Weighting according to Episode Durations (WED): This technique uses Importance Sampling (IS) to downweight states from long games and upweight those from short games. The objective is to ensure every episode (complete game) contributes equally to the learning process, regardless of its length.
  • Prioritized Experience Replay (PER): Adapted from Deep Q-Learning, PER samples states more frequently if the apprentice’s current policy differs significantly from the expert’s search results. This focuses the model on "surprising" states where it has the most to learn.
  • Cross-Entropy Exploration (CEE): This proactive approach trains a secondary exploratory policy to navigate toward states where the apprentice and expert are likely to disagree, effectively seeking out the AI's own weaknesses to generate higher-quality training data.

Experimental Results

The methods were tested using the Ludii general game system across 14 different board games, ranging from classics like Reversi and English Draughts to modern mathematical games like Hex and Amazons.

Learning curves comparing various experience manipulation techniques against standard Expert Iteration (ExIt) and other baselines.

The results indicate that these manipulations are most effective during the early-to-mid stages of training. As shown in the learning curves, the combination of WED, PER, and CEE (without Importance Sampling corrections) achieved significantly higher win rates against the baseline after a small number of training games.

Comparison of agents based on the number of top ranks and average strategy mass across 14 games.

Quantitative analysis using $\alpha$-rank confirms the robustness of these techniques. WED emerged as the most consistently high-performing individual technique, securing the highest number of "top ranks" across the 14 games. While CEE is theoretically promising, it requires careful handling to avoid over-exploring "weird" states that rarely occur in competitive play.

Conclusion

This research demonstrates that moving beyond uniform sampling can dramatically improve the efficiency of self-play learning. Simple adjustments, such as balancing the influence of games of different lengths (WED), provide a strong signal that helps the AI find the "essence" of a game faster. Future work will look into stabilizing Importance Sampling corrections and exploring how targeted exploration can be transferred between similar games.

Paper Citation: Dennis J. N. J. Soemers, Éric Piette, Matthew Stephenson, and Cameron Browne. "Manipulating the Distributions of Experience used for Self-Play Learning in Expert Iteration." arXiv:2006.00283v1 [cs.LG], 2020.

Summary updated

BibTeX
@inproceedings{soemers2020manipulating,
  author = {Dennis J. N. J. Soemers and Éric Piette and Matthew Stephenson and Cameron Browne},
  title = {{Manipulating the Distributions of Experience used for Self-Play Learning in Expert Iteration}},
  booktitle = {CoG},
  year = {2020},
  doi = {10.1109/cog47356.2020.9231589},
}

Loading related content...

Figure