mlsanityData to 7 Oct 2026

Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design

arXiv 2007.01980 ↗First posted 4 Jul 2020cs.LG cs.DS stat.MLcited by 51

Not on the map. Why?

Abstract (arXiv)

Motivated by practical needs such as large-scale learning, we study the impact of adaptivity constraints to linear contextual bandits, a central problem in online active learning. We consider two popular limited adaptivity models in literature: batch learning and rare policy switches. We show that, when the context vectors are adversarially chosen in d-dimensional linear contextual bandits, the learner needs O(d log d log T) policy switches to achieve the minimax-optimal regret, and this is optimal up to poly(log d, log log T) factors; for stochastic context vectors, even in the more restricted batch learning model, only O(log log T) batches are needed to achieve the optimal regret. Together with the known results in literature, our results present a complete picture about the adaptivity constraints in linear contextual bandits. Along the way, we propose the distributional optimal design, a natural extension of the optimal experiment design, and provide a both statistically and computationally efficient learning algorithm for the problem, which may be of independent interest.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 7; 2023: 9; 2024: 7; 2025: 7; 2026: 9.

51 papers.

Sort:

By area:

  1. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  2. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  3. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  4. 2023Active learning for data streams: a surveycited by 29
  5. 2022A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Banditscited by 28
  6. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  7. 2021Batched Neural Banditscited by 22
  8. 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
  9. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  10. 2021Parallelizing Thompson Samplingcited by 20
  11. 2021Batched Thompson Samplingcited by 19
  12. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
38 more
  1. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
  2. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  3. 2022Distributed Contextual Linear Bandits with Minimax Optimal Communication Costcited by 13
  4. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  5. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  6. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  7. 2021Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Banditscited by 9
  8. 2023A Lipschitz Bandits Approach for Continuous Hyperparameter Optimizationcited by 9
  9. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  10. 2024Optimal Batched Linear Banditscited by 7
  11. 2024Infrequent Resolving Algorithm for Online Linear Programmingcited by 7
  12. 2021Online Convex Optimization with Continuous Switching Constraintcited by 6
  13. 2024Experiment Planning with Function Approximationcited by 5
  14. 2021Parallelizing Contextual Banditscited by 4
  15. 2023CO-BED: Information-Theoretic Contextual Optimization via Bayesian Experimental Designcited by 4
  16. 2023Federated Linear Bandits with Finite Adversarial Actionscited by 3
  17. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  18. 2024Batched Nonparametric Contextual Banditscited by 3
  19. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  20. 2024Batched Stochastic Bandit for Nondegenerate Functionscited by 2
  21. 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximationcited by 2
  22. 2025Optimal and Practical Batched Linear Bandit Algorithmcited by 2
  23. 2025Achieving Limited Adaptivity for Multinomial Logistic Banditscited by 2
  24. 2026Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Banditscited by 1
  25. 2026Active Learning for Stochastic Contextual Linear Banditscited by 1
  26. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraintscited by 1
  27. 2026Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updatescited by 1
  28. 2021Encrypted Linear Contextual Banditcited by 0
  29. 2021A Benchmark for Low-Switching-Cost Reinforcement Learningcited by 0
  30. 2023From Random Search to Bandit Learning in Metric Measure Spacescited by 0
  31. 2025Breaking the log(1/Delta2) Barrier: Better Batched Best Arm Identification with Adaptive Gridscited by 0
  32. 2025Stochastic Matching Bandits with Rare Optimization Updatescited by 0
  33. 2025Batched Bandits with Heavy-Tailed Rewardscited by 0
  34. 2025The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margincited by 0
  35. 2026Demystifying Design Choices of Reinforcement Fine-tuning: A Batched Contextual Bandit Learning Perspectivecited by 0
  36. 2026Shuffle and Joint Differential Privacy for Generalized Linear Contextual Banditscited by 0
  37. 2026Learning in Prophet Inequalities with Noisy Observationscited by 0
  38. 2026Contextual Slate GLM Bandits with Limited Adaptivitycited by 0

50 most cited of 51 All 51 (JSON)