Tractable Optimality in Episodic Latent MABs
Not on the map. Why?
Abstract (arXiv)
We consider a multi-armed bandit problem with M latent contexts, where an agent interacts with the environment for an episode of H time steps. Depending on the length of the episode, the learner may not be able to estimate accurately the latent context. The resulting partial observation of the environment makes the learning task significantly more challenging. Without any additional structural assumptions, existing techniques to tackle partially observed settings imply the decision maker can learn a near-optimal policy with O(A)H episodes, but do not promise more. In this work, we show that learning with em polynomial samples in A is possible. We achieve this by using techniques from experiment design. Then, through a method-of-moments approach, we design a procedure that provably learns a near-optimal policy with O(textttpoly(A) + textttpoly(M,H)min(M,H)) interactions. In practice, we show that we can formulate the moment-matching via maximum likelihood estimation. In our experiments, this significantly outperforms the worst-case guarantees, as well as existing practical methods.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 20 of its 52 references that are in the map. First posted on arXiv 5 Oct 2022.
Builds on
20 of 52 references.
References · 20
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
- 2015Contextual Markov Decision Processescited by 213
- 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
- 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
- 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
- 2014Online Clustering of Banditscited by 99
- 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
- 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
- 2021Meta-Thompson Samplingcited by 62
- 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
- 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
- 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
8 more
- 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
- 2020The Gossiping Insert-Eliminate Algorithm for Multi-Agent Banditscited by 37
- 2013Smoothed Analysis of Tensor Decompositionscited by 19
- 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
- 2015On the Prior Sensitivity of Thompson Samplingcited by 14
- 2016Low-rank Bandits with Latent Mixturescited by 11
- 2020Regime Switching Banditscited by 9
- 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
Built on by
Citing papers per year: 2023: 1; 2024: 2.
3 papers.