Research map / Bandits and online learning / Contextual bandits and Thompson sampling
A Classification View on Meta Learning Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Meta-learns interpretable, short exploration plans for contextual bandits from a known finite collection of separated bandits by casting test-task identification as classification, implemented as a decision tree (DT-ECE).
Problem
Regret of exploration in stochastic contextual bandits meta-learned from a finite collection of bandits; existing methods (UCB/TS-style) give opaque, hard-to-interpret exploration and regret scaling with sqrt(MH) in worst case without separation.
Approach
Under reward separation, identify the test bandit by classification with informative probing tests; define a classification-coefficient linking meta-learning regret to the complexity of classifying bandits, and implement Explicit Classify then Exploit with a greedy decision tree whose splits are arm-mean threshold tests.
Key results
- DT-ECE regret is O(lambda^-2 C_lambda(M) log^2(MH)) in theory, with a nearly matching lower bound Omega(lambda^-2 randomized classification coefficient) for separated bandits.
- In experiments, DT-ECE attains regret comparable to mUCB and mTS on synthetic Bernoulli collections, commits to the optimal strategy before mTS on the hard instance, and classifies among 40 bandits with 40 arms using under 1000 samples on average.
- mUCB fails on the hard instance because optimal arms do not overlap with informative arms, so its regret grows steadily.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DT-ECE instead of mUCB on hard bandit collections | Meta-learning bandits · hard-5-10, \lambda = 0.4; hard-5-10, \lambda = 0.04 | regret | Helped |
| Use DT-ECE instead of mTS on hard bandit collections | Meta-learning bandits · hard-5-10, \lambda = 0.4; hard-5-10, \lambda = 0.04 | regret | Mixed |
| Use DT-ECE instead of mUCB on randomly generated collections | Meta-learning bandits · rand-10-20, \lambda = 0.4; rand-40-40, \lambda = 0.4 | regret | Helped |
| Classify the test task with DT-ECE on a 40-task, 40-arm collection | DT-ECE · rand-40-40, \lambda = 0.4 | samples: less than 1000 samples on average | Helped |
| Use DT-ECE rather than mUCB or mTS | Meta-learning bandits · Experiments across hard and rand collections | regret | No clear effect |
Surprising findings
- Optimistic mUCB performs poorly on the hard instance because its optimal actions are not informative about the test task.
Limitations
- Theory assumes known bandit distributions in the ideal setting; practical DT-ECE is only validated on small synthetic non-contextual experiments
- Worst-case design can underperform mUCB/mTS on more forgiving instances such as the rand family
- Regret bounds depend on separation parameter lambda and classification coefficient which may be as large as M
Experimental setup
Datasets: synthetic bandit collections (hard-5-10, rand-10-20, rand-40-40)
Benchmarks: synthetic hard and random Bernoulli bandit collections
Metrics: cumulative regret
Baselines: mUCB mTS
Builds on: latent bandits Thompson sampling decision-estimation coefficient
Closest papers by meaning
- From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.88)
- Test-Time Regret Minimization in Meta Reinforcement Learning (ICML 2024 · similarity 0.87)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.87)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.87)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.87)
- Exploration via Feature Perturbation in Contextual Bandits (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.