# Parallelizing Contextual Bandits

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

## 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 (most cited first, 22 of 22)

- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [AdaLead: A simple and robust adaptive greedy search algorithm for sequence design](https://mlsanity.com/paper/2010.02141/) (2020)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [Counterfactual Risk Minimization: Learning from Logged Bandit Feedback](https://mlsanity.com/paper/1502.02362/) (2015)
- [Batched Gaussian Process Bandit Optimization via Determinantal Point Processes](https://mlsanity.com/paper/1611.04088/) (2016)
- [Design by adaptive sampling](https://mlsanity.com/paper/1810.03714/) (2018)
- [Population-Based Black-Box Optimization for Biological Sequence Design](https://mlsanity.com/paper/2006.03227/) (2020)
- [The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms](https://mlsanity.com/paper/2002.10121/) (2020)
- [Batched Neural Bandits](https://mlsanity.com/paper/2102.13028/) (2021)
- [A primer on model-guided exploration of fitness landscapes for biological sequence design](https://mlsanity.com/paper/2010.10614/) (2020)

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

- [Second Order Bounds for Contextual Bandits with Function Approximation](https://mlsanity.com/paper/2409.16197/) (2024)
- [Experiment Planning with Function Approximation](https://mlsanity.com/paper/2401.05193/) (2024)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [A Theoretical Framework for Partially Observed Reward-States in RLHF](https://mlsanity.com/paper/2402.03282/) (2024)

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