Source-linked AI summary
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
Kaixuan Ji, Qiwei Di, Qingyue Zhao, Heyang Zhao, Quanquan Gu
TL;DR
Many practical decision problems admit multiple satisfactory answers, motivating the study of bandits with multiple optimal arms and the minimax regret they permit. The paper sharpens sub-sampling analysis and establishes a near-complete minimax characterization, while showing limits on adapting across different numbers of optimal arms.
Problem
The paper asks what minimax regret is attainable in multi-armed bandits with multiple optimal arms, a setting motivated by practical problems with multiple satisfactory solutions.
Source: §1 · pp. 1–2Method
The paper sharpens the analysis of prior sub-sampling algorithms and develops lower-bound arguments for the minimax characterization.
Source: §6.2 · p. 11, §7 · p. 12Results
The characterization sharpens the previous regret upper bound by eΘ((K −A)/K) when K −A = o(K), and near-optimal regret on ΞK,A entails a multiplicative loss on ΞK,B for well-separated A > B.
Source: §1 · p. 2Takeaways & Limitations
Near-optimality imposes exploration constraints that prevent uniform adaptation across sufficiently many models with distinct numbers of optimal arms.
Source: §7 · p. 12The adaptation result in Theorem 6.1 is constrained to B = eO(A) and B ≤ K −A, with the latter constraint tied to its proof technique.
Source: §6 · p. 9
Abstract
from arXiv · showhide
We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For $K$-armed bandits with $A$ optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a $\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)$ minimax regret, where $T$ is the total number of interactions and $\tilde O(\cdot)$ drops all constant and logarithmic factors, improving the previous $\tilde{O}(\sqrt{KT/A})$ regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of $A$ up to $\tilde{O}(1)$ factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of $K$-armed bandits with $A$ over the entire range of $1 \leq A \leq K-1$.
1 Introduction
The paper characterizes minimax regret for K-armed bandits with A optimal arms across the full range of A, and examines whether a learner can attain the appropriate rate without knowing A. It sharpens prior regret analysis and shows that near-optimal performance across sufficiently different values of A is not simultaneously attainable.
1 Introduction
- Multi-armed bandits model sequential decisions under uncertainty, and multiple satisfactory solutions motivate studying the benefit of multiple optimal arms.The classical regret characterization does not capture that benefit.Source: §1 · pp. 1–2
- Earlier sub-sampling regret bounds do not fully capture the benefit of many optimal arms, motivating a minimax characterization over the full range of A.For A = K −1, sampling two arms gives probability only O(1/K) that either is suboptimal.Source: §1 · p. 2
- The refined analysis and a lower bound for A > K/4 establish minimax regret up to logarithmic factors for all K, T ≥ K and A ∈ [1, K −1].The characterization also sharpens the previous upper bound by a factor of eΘ((K −A)/K) when K −A = o(K).Source: §1 · p. 2
- Any strategy near-optimal on ΞK,A incurs a multiplicative loss relative to the minimax-optimal rate on ΞK,B for well-separated A > B.This shows why knowledge of A is necessary for near-optimal regret.Source: §1 · p. 2
- The lower-bound technique uses symmetric instances and a common all-equal reference, with a multiplicative change-of-measure argument, when instances share optimal arms.Standard two-point arguments based on disjoint optimal-arm sets become ineffective when the number of optimal arms is close to K.Source: §1 · p. 2
2 Related Work
Prior work studies multiple optimal arms in both pure exploration and regret minimization, while the online minimax characterization has been incomplete when few arms are suboptimal. Related work also shows that adapting to unknown problem parameters can be intrinsically hard.
2 Related Work
- Multiple optimal arms also reduce sample complexity in pure exploration, and prior work establishes best-arm identification rates when A is known or unknown.For regret minimization, uniformly fast-convergent algorithms have asymptotic regret growing linearly with K −A.Source: §2 · p. 3
- Prior online minimax regret results were restricted to K −A = Ω(K), leaving the regime K −A = o(K) unresolved.Standard lower-bound techniques such as Le Cam’s method are ineffective in that regime.Source: §2 · p. 3
- Sub-sampling yields eO(√(KT/A)) worst-case regret, near-optimal when K −A = Ω(K), but does not characterize all A.Prior work also studies instance-dependent regret in regret-minimization settings.Source: §2 · p. 3
- Adaptation to unknown parameters has both affirmative results and hardness results across bandit settings.For the proportion of optimal arms, prior work proves non-adaptivity and characterizes Pareto-optimal gap-independent rates.Source: §2 · pp. 3–4
- Earlier non-adaptivity constructions based on disjoint optimal arms do not cover A + B > K, where instances from the two classes share an optimal arm.The paper’s hardness result covers this overlapping-optima regime.Source: §2 · p. 4
3 Problem Setup
The paper studies regret minimization in a finite K-action bandit with a known number A of optimal arms. Rewards are unknown and noisy, and the objective is to characterize minimax regret for the corresponding instance class.
3 Problem Setup
- The setting has K = |A| finite actions, an unknown reward function r, and horizon T ≥ 1.At each round, the learner selects an action and observes its reward with 1-sub-Gaussian noise.Source: §3 · p. 4
- The learner’s objective is to minimize regret relative to the maximum mean reward r* over actions.The regret expectation is taken over the algorithm and the noise.Source: §3 · p. 4
- The number of optimal arms A is known and lies in [1, K −1], and ΞK,A denotes instances with exactly A optimal arms.The paper seeks the minimax characterization for given K, A, and T.Source: §3 · p. 4
4 Algorithms and Upper Bounds
The algorithm uniformly samples a subset of arms and runs a minimax-optimal bandit algorithm on it. A sharper analysis improves the expected regret bound, particularly when many arms are optimal, while the guarantee cannot be extended to high probability.
4 Algorithms and Upper Bounds
- Algorithm 1 samples a subset B of arms and runs a minimax-optimal algorithm on B for T rounds.The subset size L is set according to (4.1).Source: §4 · p. 4, §4.1 · p. 6
- The refined analysis shaves off a factor of (K −A)/K from the previous eO(√(KT/A)) bound, especially benefiting instances with many optimal arms.The guarantee is an improvement in expectation only; any algorithm satisfying it must incur eΩ(√T) regret with non-vanishing probability.Source: §4 · p. 5
4.1 Proof Overview of Theorem 4.1
- The proof separates subsets containing no optimal arms, both optimal and suboptimal arms, or only optimal arms.These cases respectively use a trivial regret bound, a conditional expected-regret bound, or zero regret.Source: §4.1 · p. 5
- The earlier analysis chose L of order K/A to make the probability of missing all optimal arms negligible, yielding O(√(KT/A)) regret.That rate is optimal up to logarithmic factors when K −A = Ω(K).Source: §4.1 · p. 5
- When A is close to K, the sharper analysis uses zero regret on subsets containing only optimal arms and a suboptimal-arm probability of (K −A)/K.With L = eO(1), a union bound makes the contribution from missing every optimal arm negligible.Source: §4.1 · pp. 5–6
5 Lower Bounds
The section establishes lower bounds that, together with the upper bound, characterize minimax regret up to logarithmic factors across the full range of A. It also explains why the lower-bound argument changes when optimal-arm sets may overlap.
5.1 Proof Overview of Theorem 5.1
- For A ≤ K/4, a Le Cam two-point construction makes the instances hard to distinguish while their optimal-arm sets are disjoint, forcing regret on one instance.The proof selects a gap that keeps the trajectory distributions close and yields a regret lower bound.Source: §5 · p. 6, §5.1 · pp. 6–7
5.2 Proof Overview of Theorem 5.2
- When A is comparable to K, overlapping optimal-arm sets defeat the two-point argument, so the proof uses a larger instance family and an all-equal reference.A multiplicative change-of-measure transfers behavior from the reference instance to candidate hard instances.Source: §5 · p. 6, §5.2 · pp. 7–8
5 Lower Bounds
- Theorems 5.1 and 5.2, together with Theorem 4.1, characterize minimax regret up to logarithmic factors for all 1 ≤ A ≤ K−1.The lower bounds address A ≤ K/4 and A > K/4, respectively.Source: §5 · p. 6
6 Impossibility to Adapt to Number of Optimal Arms
The section shows that near-optimal regret generally cannot be attained across different numbers of optimal arms without knowing that number up to logarithmic factors. It treats disjoint and overlapping optimal-arm regimes separately, using different lower-bound arguments.
6 Impossibility to Adapt to Number of Optimal Arms
- When B = o(A), an algorithm cannot attain near-optimal regret simultaneously on ΞK,A and ΞK,B, making knowledge of A up to logarithmic factors necessary.The results divide the analysis according to whether B ≤ K−A or B ≥ K−A.Source: §6 · pp. 8–9
6.1 Proof Overview of Theorem 6.1
- For B ≤ K−A, Theorem 6.1 compares hard-to-distinguish instances with disjoint optimal-arm sets, while its proof requires this regime condition.The paper identifies extending that proof beyond B ≤ K−A as requiring a fundamentally different approach.Source: §6.1 · pp. 9–10, §6 · p. 9
6.2 Proof Overview of Theorem 6.2
- Because ΞK,A instances can share optimal arms with ΞK,B instances, the proof characterizes exploration on a common all-equal reference instead of relying on disjoint optima.The paper notes that whether sub-sampling-like behavior is necessary for near-optimality remains open.Source: §6.2 · pp. 11–12
- On the all-equal reference, near-optimality for ΞK,A permits only eO(TB^2/K^2) pulls of a fixed super-arm, below the eΩ(TB/K) required for ΞK,B when B ≪ K.This exploration mismatch yields the non-adaptivity result in the overlapping regime.Source: §6.2 · pp. 11–12
7 Conclusion
The paper studies regret minimization in K-armed bandits with A optimal arms, sharpening the analysis of prior sub-sampling algorithms and establishing lower bounds. It also shows that near-optimality imposes exploration constraints that prevent uniform adaptation across sufficiently many models with different numbers of optimal arms.
7 Conclusion
- The paper provides a sharper analysis of prior sub-sampling algorithms and lower bounds for regret minimization with A optimal arms.Together, these results establish a regret characterization, though its rate is not specified in these passages.Source: §7 · p. 12
- Near-optimality imposes exploration constraints that prevent uniform adaptation across sufficiently many models with distinct numbers of optimal arms.The paper identifies closing logarithmic gaps, designing Pareto-optimal algorithms, and characterizing necessary exploration behavior as directions for future work.Source: §7 · p. 12
A.1 Proof of Theorem 4.1
The proof bounds regret by separating the cases where the sampled subset contains an optimal arm and where it contains a suboptimal arm. It controls the probability of missing all optimal arms and uses the minimax guarantee of MOSS when the subset includes both types of arms.
A.1 Proof of Theorem 4.1
- For L = K − A + 1, the probability that the sampled subset contains no optimal arms is zero; otherwise the proof bounds that probability by (2T)^−1.The bound follows by treating A ≤ K/2 and A > K/2 separately, then combining the cases.Source: §A.1 · p. 13
- The proof bounds the probability that the sampled subset contains a suboptimal arm but no optimal arm, then uses MOSS’s minimax guarantee when it contains both types.When the subset contains only optimal arms, no regret is incurred; when it contains no optimal arms, per-round regret is at most 1.Source: §A.1 · p. 13
- The proof controls the regret contribution from missing optimal arms using the bound on that event’s probability and the per-round regret bound of 1.Rewards belong to [0, 1], so total regret is at most T.Source: §A.1 · pp. 13–14
- The resulting regret bound is achieved by a valid algorithm uniformly over all instances with exactly A optimal arms, establishing the claimed minimax upper bound.The proof derives a bound on L using log(K/(K − A)) ≥ A/K and substitutes it into the preceding regret bound.Source: §A.1 · p. 14
B.1 Proof of Theorem 5.1
This section develops regret lower bounds using hard bandit instances and change-of-measure arguments, and analyzes sampling-probability bounds. It establishes logarithmic-factor tightness and shows that near-minimax algorithms with B optimal arms must sufficiently often sample every fixed set of B arms.
B.1 Proof of Theorem 5.1
- The construction chooses S1 as the A least-sampled arms in S∁0; this subset exists because A ≤ K/4, and hence A < K − A.For each a ∈ S1, rewards are N(0, 1) under ν0 and N(2Δ, 1) under ν1.Source: §B.1 · pp. 14–15
B.2 Proof of Theorem 5.2
- For any algorithm, the proof obtains a worst-case regret lower bound by comparing an all-equal Gaussian instance with instances having A optimal arms.It chooses Δ = (T log K)^−1 after bounding the likelihood ratio; the supplied passage does not show the final bound’s formula.Source: §B.2 · pp. 18, 20
C.1 Formal Version and Proof of Lemma 6.4
- For fixed S, stopping time τS occurs when the pull count on S is exactly m; at that point, the algorithm cannot reliably distinguish θ from νS.Source: §C.1 · p. 21
C.2 Tightness of Lemma C.1
- For m = eO(T) and A ≥ K/2, both bounds of Lemma C.1 are tight when ℓ is chosen at the stated scale.SMOSS attains the lower envelope, with qSMOSS(m) ≤ L(K − A)/K for m ≤ T/L; a constructed minimax-optimal algorithm attains the upper envelope for prescribed m ≤ T/2.Source: §C.2 · pp. 23–25
- Both bounds in Lemma C.1 cannot be improved beyond logarithmic factors, and Algorithm 2 remains minimax-optimal up to logarithmic factors.Source: §C.2 · p. 25
C.3 Exploration profile of Near Minimax-Optimal Algorithms
- For an algorithm near-minimax optimal on ΞK,B, Lemma C.2 requires sufficiently frequent pulls of every fixed B-arm set, including on the all-equal instance.The stated result covers every U of size B and integers m up to T/2; the supplied passages do not include the full bound.Source: §C.3 · pp. 26–27
C.4 Proof of Theorem 6.1
The proof compares an instance with A optimal arms to one with B optimal arms by promoting a least-sampled set of arms. A change-of-measure argument controls how distinguishable the two instances are.
C.4 Proof of Theorem 6.1
- The proof constructs ν0 with A optimal arms, then selects a set S1 of B least-sampled arms outside S0 and promotes them to form ν1 with exactly B optimal arms.Under ν1, arms outside S1 have suboptimality gap at least Δ.Source: §C.4 · pp. 28–29
- A change-of-measure argument bounds the difference in expected pulls of S1 under the two instances using the trajectory distributions’ total variation distance.The instances differ only on S1; there, rewards change from N(1/2 − Δ, 1) under ν0 to N(1/2 + Δ, 1) under ν1.Source: §C.4 · p. 28
- Choosing Δ = min{1/4, (K − A)/(16BRA)} yields KL(P0∥P1) ≤ 1/8 and consequently TV(P0, P1) ≤ 1/4.Source: §C.4 · p. 29
C.5 Proof of Theorem 6.2
The proof builds a hard instance by perturbing selected arms from an all-equal reference, then controls regret through a stopped change-of-measure argument and a tail-aggregation bound.
C.5 Proof of Theorem 6.2
- A square-root-tail aggregation lemma bounds the expected truncated counts of q possibly dependent nonnegative integer-valued variables by qδ + 2qc√m.The proof truncates the variables at m and decomposes the event that their sum exceeds m.Source: §C.5 · pp. 29–30
- The constructed instance has exactly B optimal arms in U, while every arm outside U has gap Δ from the optimum.The proof compares it with an all-equal reference instance.Source: §C.5 · pp. 30, 32
- At a stopping time, the proof bounds the reference-to-hard-instance KL divergence and uses Pinsker’s inequality to transfer an event between the two trajectory distributions.It chooses Δ = 1/(4√m + 1), yielding total variation at most 1/8.Source: §C.5 · p. 31
- Because every pull outside U incurs regret Δ under the hard instance, the transferred event yields a regret lower bound that the proof then simplifies under its horizon condition.The proof completes that simplification using the definition of the lower-bound quantity and the assumed horizon condition.Source: §C.5 · p. 32
D High-probability Lower Bound
The section establishes a high-probability lower bound for strategies with near-minimax expected regret when A>K/2. It also supplies auxiliary inequalities used in the proof.
D High-probability Lower Bound
- δ ~ exp(-K/(K −A)) ≪ (K −A)/K is required by the analogous high-probability rate, contradicting the theorem’s condition for near-minimax expected regret.Theorem D.1 assumes A>K/2, an expected-regret factor Γ, and T≥8Γ²ℓ/c0².Source: D High-probability Lower Bound · pp. 32–33
- The remark contrasts the lower bound with UCB-type algorithms’ near-minimax regret and high-probability bound, noting that the analogous rate requires exceptionally small δ.The required δ is much smaller than (K−A)/K.Source: D High-probability Lower Bound · p. 33
- The proof constructs an instance by lowering the means of a set S of K−A arms from an all-equal auxiliary instance, then transfers an event at a stopping time.The transferred event has probability at least on the order of (K−A)/K under the constructed instance.Source: D High-probability Lower Bound · p. 33
E Auxiliary Lemmas
- A stopped sub-Gaussian martingale inequality provides a time-uniform bound for an adapted process at any stopping time up to T.Its conditions require nondecreasing V_t and exp(sM_t − s²V_t/2) to be a nonnegative supermartingale for every s>0.Source: E Auxiliary Lemmas · p. 35
- The auxiliary lemmas also give change-of-measure bounds using total variation, Pinsker’s inequality, and the Bretagnolle–Huber inequality.These are presented as standard tools for lower-bound arguments.Source: E Auxiliary Lemmas · p. 35