# Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 12 Feb 2022.

## Builds on (most cited first, 28 of 28)

- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [Adaptive Regret of Convex and Smooth Functions](https://mlsanity.com/paper/1904.11681/) (2019)
- [The Pareto Frontier of model selection for general Contextual Bandits](https://mlsanity.com/paper/2110.13282/) (2021)
- [Adaptive Online Learning](https://mlsanity.com/paper/1508.05170/) (2015)
- [Corralling Stochastic Bandit Algorithms](https://mlsanity.com/paper/2006.09255/) (2020)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles](https://mlsanity.com/paper/2102.13240/) (2021)
- [Open Problem: Model Selection for Contextual Bandits](https://mlsanity.com/paper/2006.10940/) (2020)
- [Comparator-adaptive Convex Bandits](https://mlsanity.com/paper/2007.08448/) (2020)
- [Linear Bandits on Uniformly Convex Sets](https://mlsanity.com/paper/2103.05907/) (2021)

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

- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Adapting to Continuous Covariate Shift via Online Density Ratio Estimation](https://mlsanity.com/paper/2302.02552/) (2023)
- [Dynamic Regret of Online Markov Decision Processes](https://mlsanity.com/paper/2208.12483/) (2022)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [An Equivalence Between Static and Dynamic Regret Minimization](https://mlsanity.com/paper/2406.01577/) (2024)
- [Offline-to-online hyperparameter transfer for stochastic bandits](https://mlsanity.com/paper/2501.02926/) (2025)
- [Anytime Model Selection in Linear Bandits](https://mlsanity.com/paper/2307.12897/) (2023)
- [Universal Online Convex Optimization with 1 Projection per Round](https://mlsanity.com/paper/2405.19705/) (2024)
- [Dynamic Regret Reduces to Kernelized Static Regret](https://mlsanity.com/paper/2507.05478/) (2025)
- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Parameter-Free Dynamic Regret for Unconstrained Linear Bandits](https://mlsanity.com/paper/2603.25916/) (2026)
- [Adversarial Bandits against Arbitrary Strategies](https://mlsanity.com/paper/2205.14839/) (2022)
- [Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality](https://mlsanity.com/paper/2511.06597/) (2025)
- [A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions](https://mlsanity.com/paper/2510.27177/) (2025)
- [A Perturbation Approach to Unconstrained Linear Bandits](https://mlsanity.com/paper/2603.28201/) (2026)
- [Tracking the Best Strategy in an Extensive-Form Game](https://mlsanity.com/paper/2608.09501/) (2026)
- [Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary](https://mlsanity.com/paper/2609.13547/) (2026)

## Abstract (arXiv)

We consider the problem of combining and learning over a set of adversarial bandit algorithms with the goal of adaptively tracking the best one on the fly. The CORRAL algorithm of Agarwal et al. (2017) and its variants (Foster et al., 2020a) achieve this goal with a regret overhead of order widetildeO(√MT) where M is the number of base algorithms and T is the time horizon. The polynomial dependence on M, however, prevents one from applying these algorithms to many applications where M is poly(T) or even larger. Motivated by this issue, we propose a new recipe to corral a larger band of bandit algorithms whose regret overhead has only logarithmic dependence on M as long as some conditions are satisfied. As the main example, we apply our recipe to the problem of adversarial linear bandits over a d-dimensional ℓp unit-ball for p ∈ (1,2]. By corralling a large set of T base algorithms, each starting at a different time step, our final algorithm achieves the first optimal switching regret widetildeO(√d S T) when competing against a sequence of comparators with S switches (for some known S). We further extend our results to linear bandits over a smooth and strongly convex domain as well as unconstrained linear bandits.