📊 statistics

Best Agent Identification for General Game Playing

This paper proposes an efficient, optimistic selection procedure based on multi-armed bandits to accurately identify the best-performing algorithm for each sub-task in general game playing, demonstrating significant improvements in simple regret and error probability over existing methods on the GVGAI and Ludii frameworks.

Original authors: Matthew Stephenson, Alex Newcombe, Eric Piette, Dennis Soemers

Published 2026-04-22

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Matthew Stephenson, Alex Newcombe, Eric Piette, Dennis Soemers

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the head coach of a massive sports team, but instead of just one sport, you have to manage players for 1,000 different games at once. Some are chess, some are soccer, some are video games, and some are board games.

You have a roster of 50 different players (agents). Your goal isn't to find the single "best player in the world." Your goal is much more specific: For every single game, you need to find the one player who is best at that specific game.

The Problem: The Time Trap

Here's the catch: You don't have infinite time.

To know for sure who is the best at Chess, you might need to play 1,000 matches.
To know who is best at Soccer, you need another 1,000 matches.
If you try to test every player on every game thoroughly, you'll be playing games until the sun burns out.

In the world of Artificial Intelligence, this is called the "Best Agent Identification" problem. The researchers in this paper asked: How do we find the right player for the right game as fast as possible, without wasting time on players who are clearly bad at that specific game?

The Old Way: The "Fairness" Mistake

Previous methods tried to be "fair." They would say, "Let's give every player exactly 100 turns at every game."

The Flaw: This is like making a world-class grandmaster play 100 rounds of Tic-Tac-Toe just to prove they are good at it. It's a waste of time.
The Flaw 2: It also means you might not give the good players enough turns at the hard games to prove they are actually the best.

The New Solution: The "Regret Detective" (RCP)

The authors, led by Matthew Stephenson, invented a new method called RCP (Regret Change Potential).

Think of RCP as a smart, impatient detective who is trying to solve 1,000 mysteries at once. Instead of treating every mystery equally, the detective looks at the clues and asks:

"If I spend one more minute investigating this specific game, how much closer will I get to the truth? Or, if I keep ignoring this game, how much will I regret it?"

How it works (The Metaphor):

Imagine you are betting on horses in 100 different races.

The "Confidence Interval" (The Crystal Ball): For every horse in every race, the detective has a "Crystal Ball" that shows a range of possible outcomes.
- Horse A (The clear winner): The ball says, "90% chance of winning." The range is tight.
- Horse B (The mystery): The ball says, "Could be 10%, could be 90%." The range is huge and fuzzy.
The "Regret" Calculation: The detective calculates the potential regret.
- If the detective picks the wrong horse for a race where the winner is obvious, the regret is low (it was easy to guess).
- If the detective picks the wrong horse for a race where the winner is a total mystery, the regret is huge.
The Decision: The detective ignores the easy races (where the winner is obvious) and the impossible races (where no one can win). Instead, they focus all their energy on the races where the outcome is uncertain and where picking the wrong horse would be a disaster.

Why is this better?

The paper tested this "Regret Detective" against old methods using two famous AI playgrounds:

GVGAI: A collection of 100+ arcade-style video games (like Pac-Man or Space Invaders).
Ludii: A collection of 1,000+ board and puzzle games (like Chess, Go, or checkers).

The Results:

Speed: The RCP method found the best players 35% to 70% faster than the old methods.
Accuracy: It made fewer mistakes in identifying the best player.
Efficiency: It stopped wasting time on players who were clearly terrible at a specific game and stopped wasting time on players who were clearly the best. It focused only on the "toss-up" games where the decision was hard.

The Big Picture

In the real world, this is like a doctor trying to find the best medicine for 1,000 different patients. Instead of giving every patient every drug to see what happens (which is dangerous and slow), the doctor uses a smart system to quickly rule out drugs that definitely won't work and focus testing on the few drugs that might work.

In summary:
The paper introduces a smart algorithm that acts like a resourceful manager. It stops trying to be "fair" with time and instead focuses its energy exactly where it's needed most: on the difficult decisions where a wrong choice would cost the most. This allows AI researchers to evaluate thousands of game-playing bots in a fraction of the time it used to take.

1. Problem Definition

The paper addresses the challenge of efficiently identifying the best-performing AI agent for specific tasks within a multi-problem domain, specifically General Game Playing (GGP).

Context: In GGP frameworks (like GVGAI and Ludii), researchers must evaluate numerous agents across hundreds or thousands of distinct games. Running sufficient trials to get statistically accurate performance estimates for every game-agent pair is computationally prohibitive.
Formalization: The authors frame this as a Multi-Bandit Best Arm Identification (MB-BAI) problem.
- Bandits: Each game represents a distinct multi-armed bandit.
- Arms: Each available agent represents an arm within that bandit.
- Goal: Instead of maximizing cumulative reward (standard bandit problem), the goal is to identify the single best arm (agent) for each bandit (game) after a limited budget of trials ( $n$ ).
Key Metrics: The primary performance metric is Average Simple Regret ( $r(n)$ ), defined as the average difference between the true best reward and the reward of the selected agent across all games. A secondary metric is the Average Probability of Error ( $e(n)$ ), the frequency of selecting a non-optimal agent.
Domain Constraints:
- Rewards are bounded in $[0, 1]$ .
- Agents may not be compatible with all games (unequal number of arms per bandit).
- Multiple agents may achieve the same optimal reward (non-unique best arms).
- The algorithm must support "Stop Anytime" functionality (returning a valid result at any round $t$ , not just a pre-defined $n$ ).

2. Methodology: The RCP Algorithm

The authors propose a novel algorithm called RCP (Regret Change Potential).

Core Philosophy: RCP adopts an "optimism in the face of uncertainty" approach. It selects the bandit-arm pair that has the highest potential to change the overall simple regret if pulled again.
Mechanism:
1. Confidence Intervals: For each game-agent pair $(m, k)$ , the algorithm calculates upper ( $b^+$ ) and lower ( $b^-$ ) confidence bounds based on a chosen interval estimator (e.g., Wilson Score, Jeffreys, PAC).
2. Regret Change Calculation ( $\Delta_{mk}$ ):
  - If arm $k$ is the current best for game $m$ : $\Delta_{mk} = \hat{\mu}^*_m - b^-_{mk}$ . This represents the potential decrease in regret if the true mean is actually lower than the current estimate (pessimistic view of the current best).
  - If arm $k$ is not the current best: $\Delta_{mk} = b^+_{mk} - \hat{\mu}^*_m$ . This represents the potential increase in regret (or rather, the potential to find a better arm) if the true mean is higher than the current estimate (optimistic view of the challenger).
3. Selection: The algorithm pulls the arm with the maximum $\Delta_{mk}$ across all bandits.
4. Dynamic Allocation: Unlike previous methods that split trials evenly, RCP dynamically allocates trials to bandits where the uncertainty (and potential regret change) is highest.
Flexibility: The algorithm supports adding new games or agents at runtime and allows for different numbers of arms per game.

3. Key Contributions

Novel Algorithm (RCP): Introduction of a multi-bandit BAI algorithm specifically designed to minimize simple regret rather than probability of error, utilizing a "Regret Change Potential" metric.
Domain Adaptation: Adaptation of the BAI framework to handle GGP-specific constraints, including non-unique best agents, unequal arm counts, and binary/non-binary reward distributions.
Comprehensive Evaluation: A rigorous comparison of RCP against state-of-the-art algorithms (GapE, UCB-E, Successive Rejects, Sequential Halving) across two major GGP domains:
- GVGAI: 108 games, 27 agents, ~4 million trials.
- Ludii: 1,085 games, 29 agents, ~3.4 million trials.
Confidence Interval Analysis: Systematic testing of various confidence interval estimators (Wilson, Jeffreys, Clopper-Pearson, Agresti-Coull, KL-UCB, PAC) to determine suitability for GGP reward distributions.

4. Experimental Results

The experiments demonstrated that RCP significantly outperforms existing methods in terms of Average Simple Regret.

Performance Gains:
- GVGAI (All Levels): RCP reduced simple regret by 35.7% compared to the second-best algorithm (UCB-E) and 64.5% compared to uniform sampling.
- GVGAI (Level 1): RCP reduced simple regret by 47.3% compared to UCB-E and 70.5% compared to uniform sampling.
- Ludii: RCP reduced simple regret by 35.5% compared to UCB-E and 55.7% compared to uniform sampling.
Probability of Error (APE): While RCP also improved APE, the gains were smaller (approx. 10-20%) because the algorithm prioritizes reducing the magnitude of the error (regret) rather than strictly finding the single "true" best agent when multiple agents perform nearly identically.
Algorithm Behavior:
- RCP excels in early-to-mid rounds by aggressively exploring high-uncertainty pairs.
- GapE and UCB-E often struggle in GGP because they focus on finding the "one true" best arm among near-ties, wasting trials on low-regret-difference arms.
- Successive Rejects/Sequential Halving performed poorly in the Ludii dataset due to their requirement for a fixed total number of pulls, which led to inefficient trial distribution when the number of games was large relative to the trial budget.
Confidence Intervals: The Wilson Score and Jeffreys intervals generally provided the best performance for RCP. The PAC interval, while offering theoretical fixed-confidence guarantees, performed poorly in practice for this specific domain.

5. Significance and Impact

Efficiency in Evaluation: The proposed method allows researchers to identify high-performing agents with significantly fewer trials, reducing the computational cost of evaluating new GGP agents.
Portfolio Agents: The approach can be used to generate high-quality "ground truth" labels for training portfolio agents (meta-agents that select the best sub-agent for a specific game), thereby accelerating the development of robust general game players.
Generalizability: While tested on GGP, the RCP framework is applicable to any multi-task domain with high runtime costs and bounded rewards (e.g., hyperparameter tuning, clinical trial design) where minimizing the cost of sub-optimal decisions is critical.
Stop-Anytime Capability: Unlike many prior BAI algorithms, RCP provides valid, improving results at any point in time, making it suitable for real-world scenarios where time or computational budgets are unpredictable.

In conclusion, the paper establishes that shifting the focus from "finding the absolute best arm" to "minimizing the potential regret change" via the RCP algorithm yields substantial improvements in identifying optimal agents for complex, multi-game environments.