# Tractable Optimality in Episodic Latent MABs

arXiv: https://arxiv.org/abs/2210.03528 · HTML: https://mlsanity.com/paper/2210.03528/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 52 references that are in the map.
- First posted on arXiv 5 Oct 2022.

## Builds on (most cited first, 20 of 20)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Sample-Efficient Reinforcement Learning of Undercomplete POMDPs](https://mlsanity.com/paper/2006.12484/) (2020)
- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [Sample Complexity of Multi-task Reinforcement Learning](https://mlsanity.com/paper/1309.6821/) (2013)
- [Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1602.07764/) (2016)
- [Near-optimal Representation Learning for Linear Bandits and Linear RL](https://mlsanity.com/paper/2102.04132/) (2021)
- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [On the Prior Sensitivity of Thompson Sampling](https://mlsanity.com/paper/1506.03378/) (2015)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Low-rank Bandits with Latent Mixtures](https://mlsanity.com/paper/1609.01508/) (2016)
- [Regime Switching Bandits](https://mlsanity.com/paper/2001.09390/) (2020)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)

## Built on by (most cited first, 3 of 3)

- [Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learning](https://mlsanity.com/paper/2406.05064/) (2024)
- [RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation](https://mlsanity.com/paper/2406.01389/) (2024)
- [Prospective Side Information for Latent MDPs](https://mlsanity.com/paper/2310.07596/) (2023)

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