Boosting Expert Ensembles for Rapid Concept Recall

Achim Rettinger, Martin Zinkevich, Michael H. BowlingAAAI 2006 · OpenReview

Abstract

Many learning tasks in adversarial domains tend to be highly dependent on the opponent. Predefined strategies optimized for play against a specific opponent are not likely to succeed when employed against another opponent. Learning a strategy for each new opponent from scratch, though, is inefficient as one is likely to encounter the same or similar opponents again. We call this particular variant of inductive transfer a concept recall problem. We present an extension to AdaBoost called ExpBoost that is especially designed for such a sequential learning tasks. It automatically balances between an ensemble of experts each trained on one known opponent and learning the concept of the new opponent. We present and compare results of Exp-Boost and other algorithms on both synthetic data and in a simulated robot soccer task. ExpBoost can rapidly adjust to new concepts and achieve performance comparable to a classifier trained exclusively on a particular opponent with far more data.

Introduction

In adversarial domains such as robot soccer, poker, or high-frequency trading, the "target concept"—the optimal strategy—is highly dynamic and depends heavily on the current opponent. This phenomenon is a form of concept drift. Traditional approaches face a dual challenge: learning from scratch is prohibitively slow in fast-paced environments, yet reusing old knowledge can be "noisy" if previous strategies are misapplied to a new opponent.

The authors define Concept Recall as a specific type of inductive transfer. Rather than adapting the internal structure of old models, the goal is to efficiently "recall" and combine the predictions of a pool of existing experts to master a new, slightly different task as rapidly as possible.

Methodology: The ExpBoost Algorithm

ExpBoost builds upon the AdaBoost.M1 framework. While standard AdaBoost iteratively trains "weak learners" on reweighted training data to create a strong ensemble, ExpBoost introduces a mechanism to leverage prior knowledge:

  1. Expert Pool: The algorithm maintains a library of hypotheses ($H^B$) trained on previous tasks or opponents.
  2. Competitive Selection: In each boosting iteration, ExpBoost evaluates both a newly trained weak learner and the entire pool of existing experts against the current weighted distribution of samples.
  3. Optimal Selection: It selects the hypothesis (old or new) with the lowest error.
  4. Weighting: Similar to AdaBoost, it assigns a weight ($\alpha$) to the chosen hypothesis based on its performance.

This allows the system to "lean" on relevant old experts early on and switch to learning new patterns when existing expertise is insufficient.

Experimental Setup

The researchers evaluated ExpBoost across three scenarios:

  • Synthetic Separation Task: A 2D binary classification problem.
  • Rotating Hyperplane Task: An 18D problem requiring Support Vector Machines (SVM) as base learners.
  • Simulated Robot Soccer (RoboCup): The primary real-world application involving "pass evaluation"—predicting the success of a pass based on 15-dimensional feature vectors (e.g., ball speed, distance to goal, opponent positions).

Results and Discussion

ExpBoost demonstrates a significant "Warm Start" advantage. It can outperform the best single expert after seeing as few as 5 to 20 samples, which is critical in short-duration competitive matches.

ExpBoost demonstrates superior learning speed and accuracy compared to standard AdaBoost and other baselines as the number of samples increases.

A key insight is the failure of "generalist" models. Training a single model on all previous data ($h_{b\_together}$) often leads to poor performance because conflicting strategies from different opponents create noise. ExpBoost’s "ensemble of specialists" approach proves far more robust.

Comparison of predictive accuracy across different models. ExpBoost significantly outperforms individual experts and generalist models, approaching the performance of an optimal classifier.

In the robot soccer task, ExpBoost achieved ~65% accuracy with only 50 samples. For a standard classifier to reach that same level of performance, it required over 1,000 samples. Furthermore, ExpBoost's performance nearly matched an "optimal" hypothetical classifier that had access to the entire dataset for that specific opponent.

Limitations and Future Work

While effective, ExpBoost is currently limited to binary classification. Future work includes extending the framework to regression and Reinforcement Learning (RL). Additionally, as the expert pool grows, the computational cost of evaluating every expert in every iteration may become a bottleneck. The authors also suggest that dynamically adjusting the number of boosting iterations could prevent overfitting and reduce dependency on specific base learners. Finally, automating the detection of "concept drift" without an explicit "new game" signal remains an open challenge.

Summary updated

Abstract

Many learning tasks in adversarial domains tend to be highly dependent on the opponent. Predefined strategies optimized for play against a specific opponent are not likely to succeed when employed against another opponent. Learning a strategy for each new opponent from scratch, though, is inefficient as one is likely to encounter the same or similar opponents again. We call this particular variant of inductive transfer a concept recall problem. We present an extension to AdaBoost called ExpBoost that is especially designed for such a sequential learning tasks. It automatically balances between an ensemble of experts each trained on one known opponent and learning the concept of the new opponent. We present and compare results of Exp-Boost and other algorithms on both synthetic data and in a simulated robot soccer task. ExpBoost can rapidly adjust to new concepts and achieve performance comparable to a classifier trained exclusively on a particular opponent with far more data.
BibTeX
@inproceedings{rettinger2006boosting,
  author = {Achim Rettinger and Martin Zinkevich and Michael H. Bowling},
  title = {{Boosting Expert Ensembles for Rapid Concept Recall}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=SyZzc0xOWB},
}
Figure