mlsanityData to 14 Oct 2026

Context-lumpable stochastic bandits

arXiv 2306.13053 ↗First posted 22 Jun 2023cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We consider a contextual bandit problem with S contexts and K actions. In each round t=1,2,dots, the learner observes a random context and chooses an action based on its past experience. The learner then observes a random reward whose mean is a function of the context and the action for the round. Under the assumption that the contexts can be lumped into r≤ minS,K groups such that the mean reward for the various actions is the same for any two contexts that are in the same group, we give an algorithm that outputs an ε-optimal policy after using at most widetilde O(r (S +K )/ε2) samples with high probability and provide a matching Omega(r(S+K)/ε2) lower bound. In the regret minimization setting, we give an algorithm whose cumulative regret up to time T is bounded by widetilde O(√r3(S+K)T). To the best of our knowledge, we are the first to show the near-optimal sample complexity in the PAC setting and widetilde O(√poly(r)(S+K)T) minimax regret in the online setting for this problem. We also show our algorithms can be applied to more general low-rank bandits and get improved regret bounds in some scenarios.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 28 of its 62 references that are in the map. First posted on arXiv 22 Jun 2023.

Builds on

28 of 62 references.

References · 28

  1. 2019Introduction to Multi-Armed Banditscited by 481
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  3. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  4. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  5. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  6. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
  7. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  8. 2014Online Clustering of Banditscited by 102
  9. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  10. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  11. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 70
  12. 2021Meta-Thompson Samplingcited by 63
16 more
  1. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  2. 2019Bilinear Bandits with Low-rank Structurecited by 55
  3. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  4. 2020Low-Rank Generalized Linear Bandit Problemscited by 49
  5. 2020Meta-learning with Stochastic Linear Banditscited by 46
  6. 2016On Context-Dependent Clustering of Banditscited by 44
  7. 2020Latent Bandits Revisitedcited by 44
  8. 2017Stochastic Low-Rank Banditscited by 28
  9. 2016Contextual Bandits with Latent Confounders: An NMF Approachcited by 26
  10. 2016Stochastic Rank-1 Banditscited by 23
  11. 2019Solving Bernoulli Rank-One Bandits with Unimodal Thompson Samplingcited by 23
  12. 2018State Aggregation Learning from Markov Transition Datacited by 20
  13. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 18
  14. 2021Bandit Phase Retrievalcited by 12
  15. 2023Optimal Algorithms for Latent Bandits with Cluster Structurecited by 12
  16. 2020Meta-Learning Bandit Policies by Gradient Ascentcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 0; 2026: 1.

4 papers.

  1. 2024Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recoverycited by 6
  2. 2024Symmetric Linear Bandits with Hidden Symmetrycited by 1
  3. 2024Online Matrix Completion: A Collaborative Approach with Hott Itemscited by 0
  4. 2026Optimal Online Regret for Context-Lumpable Banditscited by 0