mlsanityData to 14 Oct 2026

Parallelizing Contextual Bandits

arXiv 2105.10590 ↗First posted 21 May 2021stat.ML cs.LG q-bio.BMcited by 4

Not on the map. Why?

Abstract (arXiv)

Standard approaches to decision-making under uncertainty focus on sequential exploration of the space of decisions. However, textitsimultaneously proposing a batch of decisions, which leverages available resources for parallel experimentation, has the potential to rapidly accelerate exploration. We present a family of (parallel) contextual bandit algorithms applicable to problems with bounded eluder dimension whose regret is nearly identical to their perfectly sequential counterparts -- given access to the same total number of oracle queries -- up to a lower-order ``burn-in" term. We further show these algorithms can be specialized to the class of linear reward functions where we introduce and analyze several new linear bandit algorithms which explicitly introduce diversity into their action selection. Finally, we also present an empirical evaluation of these parallel algorithms in several domains, including materials discovery and biological sequence design problems, to demonstrate the utility of parallelized bandits in practical settings.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 22 of its 51 references that are in the map. First posted on arXiv 21 May 2021.

Builds on

22 of 51 references.

References · 22

  1. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  2. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  3. 2013Online Learning under Delayed Feedbackcited by 141
  4. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  5. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  6. 2019Batched Multi-armed Bandits Problemcited by 98
  7. 2018Practical Contextual Bandits with Regression Oraclescited by 93
  8. 2020AdaLead: A simple and robust adaptive greedy search algorithm for sequence designcited by 65
  9. 2018A Contextual Bandit Bake-offcited by 64
  10. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  11. 2018Linear Bandits with Stochastic Delayed Feedbackcited by 55
  12. 2017Stochastic Bandit Models for Delayed Conversionscited by 54
10 more
  1. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  2. 2016Distributed Clustering of Linear Bandits in Peer to Peer Networkscited by 50
  3. 2013Distributed Exploration in Multi-Armed Banditscited by 46
  4. 2015Counterfactual Risk Minimization: Learning from Logged Bandit Feedbackcited by 33
  5. 2016Batched Gaussian Process Bandit Optimization via Determinantal Point Processescited by 33
  6. 2018Design by adaptive samplingcited by 32
  7. 2020Population-Based Black-Box Optimization for Biological Sequence Designcited by 29
  8. 2020The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Armscited by 28
  9. 2021Batched Neural Banditscited by 22
  10. 2020A primer on model-guided exploration of fitness landscapes for biological sequence designcited by 7

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 3.

4 papers.

  1. 2024Second Order Bounds for Contextual Bandits with Function Approximationcited by 9
  2. 2024Experiment Planning with Function Approximationcited by 5
  3. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  4. 2024A Theoretical Framework for Partially Observed Reward-States in RLHFcited by 1