A Classification View on Meta Learning Bandits
Not on the map. Why?
Abstract (arXiv)
Contextual multi-armed bandits are a popular choice to model sequential decision-making. E.g., in a healthcare application we may perform various tests to asses a patient condition (exploration) and then decide on the best treatment to give (exploitation). When humans design strategies, they aim for the exploration to be fast, since the patient's health is at stake, and easy to interpret for a physician overseeing the process. However, common bandit algorithms are nothing like that: The regret caused by exploration scales with √H over H rounds and decision strategies are based on opaque statistical considerations. In this paper, we use an original classification view to meta learn interpretable and fast exploration plans for a fixed collection of bandits mathbbM. The plan is prescribed by an interpretable decision tree probing decisions' payoff to classify the test bandit. The test regret of the plan in the stochastic and contextual setting scales with O (λ-2 Cλ (mathbbM) log2 (MH)), being M the size of mathbbM, λ a separation parameter over the bandits, and Cλ (mathbbM) a novel classification-coefficient that fundamentally links meta learning bandits with classification. Through a nearly matching lower bound, we show that Cλ (mathbbM) inherently captures the complexity of the setting.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 32 of its 56 references that are in the map. First posted on arXiv 6 Apr 2025.
Builds on
32 of 56 references.
References · 32
- 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
- 2015Contextual Markov Decision Processescited by 220
- 2021The Statistical Complexity of Interactive Decision Makingcited by 218
- 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
- 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
- 2021Understanding Domain Randomization for Sim-to-real Transfercited by 80
- 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 70
- 2021Meta-Thompson Samplingcited by 63
- 2020Low-Rank Generalized Linear Bandit Problemscited by 49
- 2020Meta-learning with Stochastic Linear Banditscited by 46
- 2020Latent Bandits Revisitedcited by 44
- 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 44
20 more
- 2019Adaptive Exploration in Linear Contextual Banditcited by 43
- 2017Minimal Exploration in Structured Stochastic Banditscited by 41
- 2013Sequential Transfer in Multi-armed Bandit with Finite Set of Modelscited by 38
- 2021Hierarchical Bayesian Banditscited by 35
- 2021No Regrets for Learning the Prior in Banditscited by 30
- 2017Stochastic Low-Rank Banditscited by 28
- 2022Deep Hierarchy in Banditscited by 19
- 2016Latent Contextual Bandits and their Application to Personalized Recommendations for New Userscited by 18
- 2014Bounded Regret for Finite-Armed Structured Banditscited by 15
- 2019Stochastic Linear Bandits with Hidden Low Rank Structurecited by 15
- 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
- 2020Non-Stationary Latent Banditscited by 12
- 2023Optimal Algorithms for Latent Bandits with Cluster Structurecited by 12
- 2020A Novel Confidence-Based Algorithm for Structured Banditscited by 7
- 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
- 2024A Theory of Interpretable Approximationscited by 7
- 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 6
- 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
- 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
- 2023Prospective Side Information for Latent MDPscited by 4
Built on by
Citing papers per year: 2026: 1.
1 paper.