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.
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.
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