Meta-Learning Effective Exploration Strategies for Contextual Bandits

Amr Sharaf, Hal Daumé IiiAAAI 2021 · DOI

Abstract

Contextual bandit algorithms face a fundamental trade-off between exploring new actions to gather information and exploiting known high-reward actions. Traditional strategies rely on hand-crafted heuristics like $\epsilon$-greedy or LinUCB, which often fail to adapt to specific task structures. We present MÊLÉE (MEta LEarner for Exploration), a novel approach that learns exploration policies from data. By framing exploration as an imitation learning problem on fully labeled synthetic datasets, MÊLÉE develops a generalizable policy that outperforms standard baselines across hundreds of real-world tasks, demonstrating faster convergence and superior reward accumulation.

Introduction

In online decision-making, the contextual bandit framework models scenarios where an agent must choose actions based on side information (context) and receives feedback only for the chosen action. This partial feedback necessitates a balance between exploration and exploitation. While theoretical "worst-case" optimal strategies exist, they are often overly pessimistic in practice.

MÊLÉE addresses this by treating exploration as a skill to be learned. Instead of relying on fixed mathematical rules, it uses meta-learning to identify the optimal moments to explore based on the current state of the learner and the history of interactions.

Methodology

MÊLÉE frames the exploration task as a Markov Decision Process (MDP) and employs the AggreVaTe imitation learning framework for training.

Meta-Learning Setup

The algorithm is trained on "fully labeled" datasets where the rewards for all possible actions are known. This allows for the simulation of an "oracle" expert. MÊLÉE learns to select actions that minimize the "cost-to-go" relative to this expert.

Task-Independent Meta-Features

To ensure generalization to unseen tasks, MÊLÉE operates on meta-features rather than raw data:

  • Model Confidence: Calibrated prediction probabilities and entropy.
  • Interaction History: Action counts, mean rewards, and reward variance.
  • Temporal Context: The current round index.

A critical component is probability calibration; MÊLÉE uses a small set of labeled examples (e.g., 30) at test time to ensure the base classifier's confidence estimates are reliable.

Results and Discussion

MÊLÉE was evaluated against a suite of traditional and modern baselines across 300 OpenML datasets and the large-scale MSLR-10K ranking dataset.

Convergence Speed

A primary advantage of MÊLÉE is its ability to learn effective representations quickly. On the MSLR-10K task, MÊLÉE reached near-optimal performance in approximately 40 rounds, whereas competitive baselines required nearly 200 rounds to achieve similar reward levels.

Progressive reward comparison on the MSLR-10K dataset. MÊLÉE (green) achieves high reward significantly faster than traditional exploration strategies.

Robustness Across Diverse Tasks

In a comprehensive head-to-head comparison across 300 binary classification datasets from OpenML, MÊLÉE consistently outperformed standard heuristics. The meta-learned policy proved robust across varied domains, from medical diagnostics to text processing.

Pairwise win-loss matrix across 300 OpenML datasets. Positive values in the MÊLÉE row indicate it outperforms the corresponding column strategy in more datasets.

Ablation and Insights

Ablation studies highlighted that history-based features (like reward variance) are crucial for performance, providing a significant boost over policies relying solely on classifier confidence. Furthermore, the success of a policy trained on simple 2D synthetic data when applied to high-dimensional real-world tasks suggests that exploration logic is a highly generalizable meta-skill.

Conclusion

MÊLÉE demonstrates that exploration strategies for contextual bandits can be effectively learned rather than manually engineered. By leveraging imitation learning and meta-features, it provides a flexible, high-performance alternative to traditional heuristics. Future work includes relaxing the requirement for initial labeled calibration data and extending the framework to handle dynamic action spaces common in large-scale recommendation systems.

Summary updated

BibTeX
@inproceedings{sharaf2021meta,
  author = {Amr Sharaf and Hal Daumé III},
  title = {{Meta-Learning Effective Exploration Strategies for Contextual Bandits}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i11.17149},
}
Figure