# Corralling a Band of Bandit Algorithms

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

## Key facts

- Cited by 100 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2016.

## Built on by (most cited first, 30 of 100)

- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity](https://mlsanity.com/paper/2210.09579/) (2022)
- [Tactical Optimism and Pessimism for Deep Reinforcement Learning](https://mlsanity.com/paper/2102.03765/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case](https://mlsanity.com/paper/2102.05284/) (2021)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2110.12615/) (2021)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Adaptively Exploiting d-Separators with Causal Bandits](https://mlsanity.com/paper/2202.05100/) (2022)
- [Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces](https://mlsanity.com/paper/2207.05849/) (2022)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Thompson Sampling with a Mixture Prior](https://mlsanity.com/paper/2106.05608/) (2021)
- [Efficient Sequential Decision Making with Large Language Models](https://mlsanity.com/paper/2406.12125/) (2024)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [On component interactions in two-stage recommender systems](https://mlsanity.com/paper/2106.14979/) (2021)
- [Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure](https://mlsanity.com/paper/2111.00781/) (2021)
- [Oracle Inequalities for Model Selection in Offline Reinforcement Learning](https://mlsanity.com/paper/2211.02016/) (2022)
- [Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL](https://mlsanity.com/paper/2106.11935/) (2021)
- [Model Assessment and Selection under Temporal Distribution Shift](https://mlsanity.com/paper/2402.08672/) (2024)
- [Model Selection in Batch Policy Optimization](https://mlsanity.com/paper/2112.12320/) (2021)
- [Best of Both Worlds Model Selection](https://mlsanity.com/paper/2206.14912/) (2022)
- [Data-Driven Online Model Selection With Regret Guarantees](https://mlsanity.com/paper/2306.02869/) (2023)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Time-Varying Gaussian Process Bandits with Unknown Prior](https://mlsanity.com/paper/2402.01632/) (2024)

## Abstract (arXiv)

We study the problem of combining multiple bandit algorithms (that is, online learning algorithms with partial feedback) with the goal of creating a master algorithm that performs almost as well as the best base algorithm if it were to be run on its own. The main challenge is that when run with a master, base algorithms unavoidably receive much less feedback and it is thus critical that the master not starve a base algorithm that might perform uncompetitively initially but would eventually outperform others if given enough feedback. We address this difficulty by devising a version of Online Mirror Descent with a special mirror map together with a sophisticated learning rate scheme. We show that this approach manages to achieve a more delicate balance between exploiting and exploring base algorithms than previous works yielding superior regret bounds. Our results are applicable to many settings, such as multi-armed bandits, contextual bandits, and convex bandits. As examples, we present two main applications. The first is to create an algorithm that enjoys worst-case robustness while at the same time performing much better when the environment is relatively easy. The second is to create an algorithm that works simultaneously under different assumptions of the environment, such as different priors or different loss structures.