Source-linked AI summary
Corralling a Band of Bandit Algorithms
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, Robert E. Schapire
TL;DR
The paper asks how to combine bandit algorithms so a master can remain competitive with the best base algorithm despite each base receiving less feedback. It proposes CORRAL, built from specialized Online Mirror Descent and adaptive learning rates, and applies it across bandit settings to robust and model-adaptive algorithms. The results are subject to stability conditions and leave open whether all base algorithms can simultaneously retain their individual regret bounds.
Problem
The problem is to combine bandit algorithms so a master performs nearly as well as the best base algorithm run alone, despite reduced feedback that can starve initially exploratory bases.
Method
CORRAL combines a special Online Mirror Descent mirror map with a learning-rate schedule that increases a base’s rate when it receives relatively little feedback.
Results
The approach achieves regret bounds similar to the best base algorithm and applies to multi-armed, contextual, and convex bandits.
Takeaways & Limitations
The master can support robust performance in worst-case environments, better performance in easier environments, and simultaneous adaptation across different environmental assumptions or loss structures.
Takeaways & Limitations
The guarantees require conditions such as stability, and the current approach does not generally inherit all base algorithms’ regret bounds simultaneously because one learning rate requires different tunings.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper studies how to combine bandit algorithms so a master remains competitive with the best base algorithm, despite partial feedback and the risk of starving algorithms that improve later. It introduces CORRAL, based on adaptive exploration and specialized Online Mirror Descent, and applies it to robust and model-adaptive bandit algorithms.
- The goal is to combine online learning algorithms with partial feedback so the master performs well whenever one base algorithm performs well.
- A master can starve an initially exploratory base algorithm, preventing it from receiving enough feedback to reach its later strong-performance regime.
- CORRAL adaptively explores base algorithms and achieves regret bounds similar to the best base algorithm under a natural stability assumption.
- The framework covers multi-armed, contextual, and convex bandits, and supports algorithms that adapt between robust worst-case and easier environments or between different models.
- The approach combines a special Online Mirror Descent mirror map with a learning-rate schedule that increases emphasis on bases receiving relatively little feedback.
- In contextual bandits, the informal theorem gives e O(T) regret when contexts and losses are i.i.d., and eO(T 3/4) regret when losses are adversarial but contexts remain i.i.d.
2. Formal Setup
The paper formulates bandit learning as repeated interaction with an environment that reveals side information, receives a decision, and reveals only the incurred loss. It defines the master’s objective as competing with base algorithms’ isolated performance while recognizing that this goal requires important conditions and caveats.
- Each round reveals side information, the learner selects a decision while the environment specifies a loss function, and only the incurred loss is observed.
- Performance is measured by expected pseudo-regret over the randomness of both the learner and the environment.
- An environment is a randomized mapping from past history to new side information and loss functions, encompassing Bayesian settings when randomness is drawn in advance.
- The general setup includes multiarmed, convex, and contextual bandits, with decision sets representing available policies or actions and environments representing assumptions about the adversary.
- The master receives suggestions from M base algorithms, selects among those suggestions, and is intended to compete with each base’s counterfactual performance when run alone.
- The aspirational master guarantee is subject to important conditions and caveats, because base algorithms receive less data under the master than in isolation.
3. Assumption and Algorithm
The section shows that strong isolated regret guarantees are insufficient for combining bandit algorithms, motivating a stability assumption and the CORRAL master algorithm. CORRAL uses LOG-BARRIER-OMD and adaptive learning rates to maintain exploration while combining base algorithms.
- Hardness and stability: Ω(T) regret is unavoidable for some master algorithm even when one of two base algorithms has constant regret.The lower bound shows that isolated performance alone cannot guarantee successful combination.
- Hardness and stability: The lower bound motivates requiring base algorithms to remain robust under importance-weighted feedback generated by the master.The induced environment changes the loss scale, so stability measures how regret degrades under that change.
- Hardness and stability: Stability requires regret under importance weighting to grow according to a controlled function of the maximum inverse sampling probability ρ.The definition uses parameters α and R and defines ρ as maxt∈[T] 1/pt.
- Hardness and stability: The stability condition is described as natural and mild, and is shown to hold for most existing bandit algorithms or simple modifications.The paper notes that linear scaling can be obtained by rescaling losses and that many algorithms have suitable second-moment behavior.
- CORRAL: Standard exponential weighting can assign exponentially small probabilities to initially poor base algorithms, starving them before they reach better performance.This issue persists even after imposing the stability assumption, so an alternative master update is needed.
- CORRAL: CORRAL combines LOG-BARRIER-OMD with a sophisticated learning-rate schedule to encourage exploration without sacrificing regret guarantees.The log-barrier mirror map is chosen because it limits how quickly inverse selection probabilities grow, while CORRAL implements the update over base algorithms.
4. Main Results
CORRAL provides performance guarantees when base algorithms satisfy a stability condition, with bounds that account for both master-level exploration and each base algorithm’s regret. The results also support adaptive use across environments, policy classes, and computational-statistical trade-offs.
- CORRAL’s general guarantee applies when each base algorithm is stable under the master’s importance-weighted loss modifications.The bound combines standard adversarial bandit terms, hierarchical exploration terms, and the base algorithm’s stability-controlled regret.
- The analysis uses a negative regret term that grows when CORRAL assigns a base algorithm low probability and increases its learning rate.This term is crucial for obtaining better regret than prior approaches when another base algorithm consistently outperforms the underweighted one.
- When αi = 1, CORRAL attains the ideal comparison bound, but its initial learning rate must be chosen using the target base algorithm’s regret bound.For a set of competing algorithms, the bound can instead be interpreted using the maximum regret bound Rmax(T).
- The framework supports model-selection applications in which one master must perform well across different environments, decision spaces, or policy classes.The paper also presents applications combining worst-case robustness with better performance in easy environments.
- When αi < 1, CORRAL improves adaptation across base algorithms with different statistical and computational properties.In the contextual-bandit example, it avoids either a substantially suboptimal O(T 2/3) guarantee or no non-trivial guarantee for the richer policy class.
5. Applications
CORRAL combines base algorithms to adapt across environments, assumptions, and computational trade-offs. Applications cover contextual, convex, multi-armed, and other bandit settings.
- Contextual bandits: The contextual-bandit applications combine algorithms with different policy classes, regret guarantees, and computational costs.
- Contextual bandits: CORRAL combines contextual-bandit algorithms with stochastic and adversarial guarantees, adapting to whether losses are stochastic or adversarial.
- Convex bandits: In convex bandits, CORRAL combines SCRiBLe and BGD, which are stable under linear and Lipschitz loss assumptions, respectively.
- Multiple environments: CORRAL can combine Thompson Sampling instances using different priors and select the instance matching the true prior.
- Other examples: Other applications use different context representations, structural assumptions, or link functions so performance can remain good when one representation or model is appropriate.
6. Conclusion and Open Problems
The paper concludes that CORRAL combines bandit algorithms and supports adaptive black-box constructions. It leaves open whether its dependence on time and the number of base algorithms can be improved.
- CORRAL combines base algorithms and performs as well as the best of them in the bandit setting.
- A central open problem is matching the regret scaling in T of all stable base algorithms simultaneously, although impossibility is known in a special case.
- The current approach cannot achieve those simultaneous bounds because they require different tunings of the same learning rate η.
- Another open problem is reducing dependence on M, the number of base algorithms, from polynomial to logarithmic without worsening other parameter dependencies.
Appendix A. More Examples of the Setting
The framework encompasses multi-armed, contextual, and convex bandits, along with stochastic and adversarial variants. These examples illustrate the breadth of environments and loss structures covered.
- Multi-armed bandits: Multi-armed bandits use K arms with no side information, including stochastic environments and adversarial environments with adaptive loss vectors.
- Contextual bandits: Contextual bandits add side information and represent decisions as policies mapping contexts to actions.
- Contextual bandits: Contextual-bandit variants include i.i.d. contexts and losses, adversarial contexts with structured losses, and i.i.d. contexts with adversarial losses.
- Convex bandits: Convex bandits use a compact convex decision space and convex loss functions, including adversarial linear and general Lipschitz-continuous losses.
- Scope: The framework is intended to capture many partial-feedback settings, including variants with changing losses, gap dependence, and metric-space structure.
Appendix B. Proof of Theorem 2
A two-environment construction shows that no master can always perform well when base algorithms require feedback from actions the master does not select. The resulting regret is linear in at least one environment.
- Two base algorithms specialize in different environments, with B1 having constant regret in E1 and B2 having constant regret in E2.
- Any master follows the wrong base algorithm with constant probability in the first round because it does not know the environment.
- When the master follows the wrong algorithm, it lacks feedback about the other algorithm’s suggested action, preventing that algorithm from updating correctly.
- Consequently, every master incurs expected regret Ω(T) under at least one of the two environments.
Appendix C. Proofs of Main Results
The appendix proves the master’s regret guarantees using LOG-BARRIER-OMD, whose special log-barrier mirror map and learning-rate schedule yield a bound with a negative term involving ρT,i. The proofs combine this master bound with base-algorithm stability and unbiased fake losses.
- LOG-BARRIER-OMD: LOG-BARRIER-OMD uses a special log-barrier mirror map in the part of the analysis differing from prior work.The remaining proof largely follows standard regret analysis.
- LOG-BARRIER-OMD: After T rounds, LOG-BARRIER-OMD provides a regret guarantee for every comparator u ∈ ∆M.The guarantee is stated as Lemma 12 and derived using the generalized Pythagorean theorem.
- Master-to-base analysis: The master-to-base regret bound includes a negative term involving ρT,i.This term is used in the subsequent decomposition of master and base regret.
- Master-to-base analysis: The proofs of Theorems 4, 5, and 7 decompose regret into master-to-base and base-to-fixed-point components.The negative term is used to cancel the base algorithm’s large regret in the combined analysis.
- Stability-based guarantees: Theorem 4 follows from the base algorithm’s stability condition and Lemma 13 because the fake loss function is an unbiased estimator of the true loss.The proof concludes by taking expectations.
Appendix D. Omitted Details for Section 5
The appendix defines weak stability and shows that it suffices for CORRAL’s guarantees when base algorithms receive an appropriate loss-range parameter and are restarted as that range increases. The resulting analysis partitions the game into logarithmically many restart segments.
- Weak stability: An algorithm is (α, R)-weakly-stable when its regret remains controlled under induced environments, with R non-decreasing.The definition also includes the environment and decision-space conditions.
- Weak stability: The weak-stability analysis assumes a known loss-range upper bound ρT ≥ ρ supplied to the algorithm.Here ρ is the maximum inverse sampling probability over the T rounds.
- CORRAL modification: CORRAL initializes base algorithms with ρ1,i = 2M and restarts Bi with the updated range parameter ρt+1,i.The modification ensures received losses do not exceed each instance’s range parameter.
- Weak-stability guarantee: If Bi is (αi, Ri)-weakly-stable, running CORRAL under E preserves the main results up to constants.This is the conclusion of Theorem 15.
- Weak-stability guarantee: Restarting Bi divides the game into ni + 1 ≤ ⌈log2 T⌉ segments.The segment decomposition supports the weak-stability regret analysis.
D.1. Contextual Bandits
The contextual-bandit appendix verifies weak stability for ILOVETOCONBANDITS, BISTRO+, Epoch-Greedy, and EXP4 under their respective settings. The proofs adapt loss estimators, concentration arguments, and relaxation analyses to the master-induced losses.
- Algorithms covered: The appendix analyzes ILOVETOCONBANDITS, BISTRO+, Epoch-Greedy, and EXP4 as contextual-bandit base algorithms.Their stability parameters and environment classes are listed in the corresponding lemmas.
- EXP4: EXP4’s weak-stability proof starts from its standard expected-regret bound and accounts for the master-induced loss estimator.The appendix states the result for any context-loss sequence.
- ILOVETOCONBANDITS: ILOVETOCONBANDITS retains the martingale structure needed for regret analysis despite history-dependent sampling probabilities.The proof scales concentration quantities with the loss-range parameter ρ.
- BISTRO+: BISTRO+ is adapted by modifying its relaxation with Rademacher variables and a random variable supported on {0, Lρ}.The modified relaxation is shown to satisfy admissibility conditions, and L is optimized in the resulting regret bound.
- Epoch-Greedy: Epoch-Greedy begins with T0 uniformly random actions, constructs an importance-weighted training set, and then uses an ERM-selected policy.The analysis applies martingale concentration and derives an expected-regret bound after setting δ = 1/T.
D.2. Convex Bandits
The convex-bandit appendix establishes weak-stability results for SCRiBLe and BGD by adapting their gradient-based regret analyses to master-scaled feedback. The resulting bounds depend on the loss geometry or gradient-estimator scale used by each base algorithm.
- SCRiBLe: SCRiBLe is weakly stable when losses are linear, with the base algorithm facing loss ⟨θ, stct⟩.Its analysis follows the cited SCRiBLe regret proof after accounting for the master-scaled loss.
- SCRiBLe: SCRiBLe’s final regret bound is obtained by bounding the relevant inner product and choosing the optimal internal learning rate η′.The resulting order is expressed in terms of the dimension d and the loss-range parameter ρ.
- BGD: BGD is weakly stable for L-Lipschitz losses.The proof treats BGD as stochastic online gradient descent using gradient estimators g1, …, gT.
- BGD: Under the master, BGD uses scaled gradient estimators s1g1, …, sTgT, with E[st] ≤ ρ.The corresponding stochastic online-gradient-descent regret bound is then adjusted for this scaling.
- BGD: The adjusted BGD analysis yields a regret bound of the stated order.The appendix summarizes this final step after applying the master-induced estimator scaling.
D.3. Multi-Armed Bandits
The analysis establishes a Thompson Sampling result under the true prior and adapts its posterior updates to the master algorithm's feedback. It then modifies the analysis to account for the master-controlled loss and retains the remainder of the original argument.
- Lemma 22 analyzes Thompson Sampling when it is run with the true prior P.
- The master passes s_t to Thompson Sampling so its posterior for the loss c_t is updated only when feedback is received.When s_t = 0, no posterior update occurs.
- The modified analysis uses c′_t = s_tc_t and q_t, the posterior distribution of the optimal arm.
- Conditional expectations and the optimal arm θ∗ are used to formulate the key modification to the Russo and Van Roy (2014) analysis.
- With θ_t denoting Thompson Sampling's output, the resulting step is combined with the same argument as the original analysis.The remaining analysis is unchanged.