Source-linked AI summary
Batched Multi-armed Bandits Problem
Zijun Gao, Yanjun Han, Zhimei Ren, Zhengqing Zhou
TL;DR
The paper asks how the number of batches and adaptive batch timing affect regret in multi-armed bandits. It introduces BaSE, which achieves rate-optimal regrets within logarithmic factors, and proves lower bounds showing that adaptive grids provide essentially no improvement.
Problem
The dependence of multi-armed bandit regret on the number of batches, and the value of adaptively chosen batch sizes, remain underexplored.
Method
BaSE explores across early batches, eliminates likely suboptimal arms, and commits to the best remaining arm in the final batch.
Results
The paper obtains upper bounds and matching lower bounds within logarithmic factors, including when batch grids are adaptively chosen.
Takeaways & Limitations
Adaptive grids are essentially no better than the best static grid, and the regret rates are characterized within logarithmic factors.
Takeaways & Limitations
Whether the M −2 term in the adaptive-grid lower bound can be removed remains open.
Abstract
from arXiv · showhide
In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has been completely characterized in \cite{perchet2016batched}, the effect of the number of arms on the regret for the multi-armed case is still open. Moreover, the question whether adaptively chosen batch sizes will help to reduce the regret also remains underexplored. In this paper, we propose the BaSE (batched successive elimination) policy to achieve the rate-optimal regrets (within logarithmic factors) for batched multi-armed bandits, with matching lower bounds even if the batch sizes are determined in an adaptive manner.
1 Introduction and Main Results
This paper characterizes how limited interaction rounds affect minimax and problem-dependent regret in batched multi-armed bandits, including adaptively chosen batch grids. It proposes BaSE and establishes near-matching upper and lower bounds within logarithmic factors.
- Problem setting: Batched bandits restrict policies to decisions based only on observations from completed batches, interpolating between batch learning and fully adaptive online learning.Static grids are fixed before sampling, whereas adaptive grids may use observations from previous batches.
- Problem setting: The paper targets the dependence of minimax and problem-dependent regret on the number of batches M.The batched setting addresses applications where data arrive in groups or interaction rounds are limited.
- Upper bounds: M = O(log log T) batches suffice for optimal minimax regret within logarithmic factors, while M = O(log T) suffice for optimal problem-dependent regret.The upper bounds are achieved by two policies under static grids, with polylogarithmic factors in K and T hidden in the bounds.
- Lower bounds: Static-grid lower bounds match the upper bounds within poly-logarithmic factors, and adaptive-grid lower bounds are only slightly weaker.The adaptive analysis loses a polynomial factor in M because the policy space is larger.
- Lower bounds: For either static or adaptive grids, achieving optimal minimax regret requires M = Ω(log log T), while optimal problem-dependent regret requires M = Ω(log T / log log T).Thus adaptive grids are essentially no better than the best static grid for the batch counts considered.
2 The BaSE Policy
BaSE adapts successive elimination to batched bandits by exploring across early batches, eliminating inferior arms, and committing to the best remaining arm. Minimax and geometric grids support the paper’s regret guarantees, with analysis controlling random active-arm counts under batch constraints.
- Policy design: BaSE is a batched version of successive elimination designed for settings with M ≤ T batches.The policy extends the fully adaptive successive-elimination approach to batched interaction.
- Policy design: The policy explores during the first M − 1 batches, eliminates arms that are significantly worse, and commits to the highest-average-reward remaining arm in the last batch.All active arms are sampled equally within each exploration batch before elimination decisions are made.
- Grid choices: BaSE requires a pre-specified grid, with a minimax grid for minimax regret and a geometric grid for problem-dependent regret.The paper also specifies static-grid constructions and notes that rounding issues do not change the regret rate.
- Regret analysis: Theorem 4’s guarantees imply Theorem 1, while the main technical difficulty is controlling arm-pull counts when the active set becomes random across batches.The good event used in the proof ensures that suboptimal arms are eliminated appropriately and the optimal arm is retained with high probability.
- Regret analysis: The regret analysis partitions arms by when they are eliminated or retained, then bounds the regret contributions from each resulting set.The proof separately handles arms eliminated after the first batch, eliminated before the last batch, and retained through the final batch.
3 Lower Bound
The lower-bound analysis uses multiple-hypothesis testing to characterize regret under static grids and then extends the argument to adaptive grids. It shows that adaptive batch timing does not substantially improve performance over the best static grid.
- Static grids: The lower-bound program first constructs a fixed multiple-hypothesis testing problem for policies using static grids.The candidate reward distributions make different arms optimal while assigning at least Δ regret to pulling a wrong arm.
- Static grids: For any static grid, the analysis derives a minimax regret lower bound by choosing the smallest gap Δ appropriately.Lemma 2 supplies the grid-dependent bound, and the theorem follows after selecting Δ and using t0 = 0 and tM = T.
- Static grids: A tree-based testing inequality lower-bounds the error probability of identifying the optimal arm from batched observations.The proof applies the inequality with a star tree and uses the number of pulls before the current batch.
- Adaptive grids: For adaptive grids, the proof defines events partitioning the probability space and constructs policy-dependent reward distributions that differ in one arm.The construction supports indistinguishability arguments for randomized or sequentially adaptive batch boundaries.
- Adaptive grids: Lemmas 4 and 5 combine to show that some event has probability at least (2M)^−1 and therefore forces the desired adaptive-grid lower bound.Lemma 4 converts a sufficiently likely event into large regret, while Lemma 5 guarantees such an event exists.
4 Experiments
The experiments evaluate BaSE under several batch grids and compare its empirical regret with centralized UCB1. They use a three-armed, three-batch setting with fixed horizon and reward means.
- Experimental setup: The experiments compare BaSE under minimax, geometric, and arithmetic grids against centralized UCB1 without batch constraints.The arithmetic grid uses tj = jT/M for j ∈[M].
- Experimental setup: The default setting uses T = 5 × 10^4, K = 3, M = 3, γ = 1, with means 0.6 for the optimal arm and 0.5 for the others.
- Results: Figure 1 reports the empirical regret performances of the BaSE policy.
A Auxiliary Lemmas
The auxiliary lemmas provide probabilistic and graph-theoretic tools used in the lower-bound and elimination analyses. They derive inequalities for probability measures and trees, including a bound based on acyclicity.
- Probability inequality: Lemma 6 generalizes a probability-measure inequality attributed to Tsybakov.Its proof uses the earlier argument and the inequality √(1 − x) ≤ 1 − x/2 for x ∈ [0, 1].
- Tree inequality: Lemma 7 establishes a graph-theoretic inequality for any tree on [n] and vector x ∈ R^n.After ordering the vector coordinates, the proof bounds induced edges using the fact that a restricted tree remains acyclic.
B.1 Proof of Lemma 1
The proof of Lemma 1 bounds the probability of incorrect elimination events and combines these bounds to obtain the desired upper bound. Union bounds control both accidental elimination of the optimal arm and failure to eliminate a suboptimal arm.
- Elimination events: If the optimal arm is eliminated by arm i after τ pulls each, the event has probability at most 1/(TK) for fixed τ.
- Elimination events: A union bound aggregates the fixed-τ probability bounds for elimination of the optimal arm.
- Elimination events: The proof similarly bounds the probability that the optimal arm fails to eliminate arm i at its scheduled elimination time.The argument conditions on fixed realizations of the elimination time and pull count before applying a union bound.
- Conclusion: Combining the elimination bounds with the preceding inequalities and the chosen value of b yields the desired upper bound.
B.2 Deferred proof of Theorem 4
The proof bounds regret separately for three arm groups under the geometric-grid BaSE policy, then combines those bounds to obtain the theorem’s upper bound.
- Regret decomposition: BaSE partitions the arms into I0, I1, and I2 using the smallest positive gap Δ, treating each group separately.The analysis follows the same partitioning framework as Section 2.2.
- Regret decomposition: The regret from arms in I0, I1, and I2 is bounded separately through three group-specific inequalities.The I2 contribution additionally accounts for an arm pulled Ti times.
- Conclusion: Combining inequalities (14)–(16) with inequality (6) and the choice of b in (3) yields the desired upper bound (5).
B.3 Proof of Lemma 3
The supplied passages only indicate that Lemmas 6 and 7 provide the remaining ingredients for the proof of Lemma 3.
- Optimization step: The minimizer of the relevant expression is identified as part of the proof.The supplied passage does not include the expression or the minimizer’s value.
- Proof step: Lemmas 6 and 7 are invoked to derive the next inequality in the proof of Lemma 3.
B.4 Proof of Lemma 4
Lemma 4 is proved by reducing the lower-bound argument to multiple hypothesis testing over carefully modified reward distributions and averaging the resulting bounds.
- Hypothesis construction: The proof reduces the minimax lower bound to multiple hypothesis testing using reward-distribution families indexed by j and k.For each alternative arm, its mean is increased by 3Δj relative to the base distribution.
- Hypothesis construction: Under each Qj,k,ℓ, arm ℓ is optimal, every other arm incurs regret at least Δj, and only component ℓ differs across alternatives.
- Testing argument: The testing argument lower-bounds distinguishability using policy observations, total variation, data processing, and KL-divergence calculations.The event Aj is determined by observations up to time Tj−1, enabling the data-processing steps.
- Conclusion: Averaging the bound over k and using pj ≥ 1/(2M) completes the proof of Lemma 4.
B.5 Proof of Lemma 5
The supplied passages show that the proof of Lemma 5 applies data processing to an event determined by observations before time Tj−1 and compares component-wise perturbations.
- Data-processing step: The event Aj is determined by observations up to time Tj−1, so data processing yields the next lower bound.
- Distribution comparison: Each Pj,k differs from PM only in component k, with mean difference Δj + ΔM.
- Divergence calculation: The proof counts pulls of arm k before Tj−1 through τk when evaluating the resulting divergence bound.