acceptodds
Under review as a conference paper at ICLR 2027

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

Abstract

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 -armed bandits with optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu & Nowak, 2020), establishing a minimax regret, where is the total number of interactions and drops all constant and logarithmic factors, improving the previous 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 up to 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 -armed bandits with over the entire range of .

Primary area:
learning theory
Keywords:
Bandits, Multiple correct answer, Optimal complexity

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_XKnuOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies stochastic KK-armed bandits with exactly AA optimal arms. It presents the minimax rate Θ~((K−A)T/KA)\widetilde{\Theta}((K-A)\sqrt T/\sqrt{KA}) for T≥KT\ge K, based on a sharper analysis of subsampling followed by MOSS and matching lower bounds up to logarithmic factors. It also extends non-adaptivity lower bounds to regimes where optimal-arm sets necessarily overlap, under specified separation and horizon conditions.

Critical strengths
  • The sharper minimax characterization can give a polynomial improvement over existing bounds when almost all arms are optimal, e.g., Θ~(T/K)\widetilde\Theta(\sqrt T/K) when A=K−1A=K-1. This gives upper and lower bounds that match up to logarithm factors across the full range of AA.

  • The non-adaptivity result for overlapping optimal-arm sets is also an interesting contribution. It shows that adaptation can remain difficult even when instances necessarily share many optimal arms, extending beyond earlier constructions that are based on disjoint optima.

Critical weaknesses

My main reservation is the precision and clarity of the main-text explanations. The non-adaptivity claim on page 6 is too broad for comparable optimal-arm counts, although the formal statements do impose separation conditions. More importantly, the overview of Theorem 6.2 treats a pull-count bound on an event as controlling the full-trajectory KL divergence; the appendix instead uses a stopped experiment. These passages make the scope and reasoning of a main contribution harder to follow than necessary.

Minor technical point: Appendix A absorbs an additive 1/21/2 into the claimed regret bound, which tends to zero when A=K−1A=K-1 and T=KT=K. This step is not justified uniformly as written. Retaining the sharper miss-probability estimate appears to repair the argument without changing the claimed rate.

Questions for authors

None

3 comments

Thank you for your supportive feedback! We answer your questions as follows.

Q1: The non-adaptivity claim on page 6 is too broad for comparable optimal-arm counts.

A1: Thank you for pointing out this issue, we have revised our paper accordingly to specify that the non-adaptivity result is only applicable when A=ω~(B)A = \tilde{\omega}(B).

Q2: The overview of Theorem 6.2 treats a pull-count bound on an event as controlling the full-trajectory KL divergence; the appendix instead uses a stopped experiment.

A2: We thank the reviewer for pointing out this imprecision in our proof overview. We would like to clarify the motivation for introducing the stopped experiment in Appendix C.5 and its connection to the high-level argument in Section 6.2.

At a high level, the key step in proving Theorem 6.2 is to establish a regret lower bound on the hard instance ν\nu. To this end, we aim to show that the event E:=NU(T)≤m\mathcal{E}:=\\{N_{\mathcal U}(T)\le m\\} occurs with constant probability under Pν\mathbb P_\nu. Our argument proceeds in two steps. First, using the exploration constraints imposed by near-optimality on ΞK,A\Xi_{K,A}, we establish that Pθ(E)≥1/2\mathbb P_\theta(E)\ge 1/2 on the all-equal reference instance θ\theta. Second, we transfer this probability lower bound from θ\theta to ν\nu. The key intuition is that, when Δ≍1/m\Delta\asymp 1/\sqrt m, the two instances cannot be reliably distinguished before the algorithm has pulled arms in U\mathcal U more than mm times. Consequently, the event E\mathcal E must also occur with constant probability under ν\nu, so that Pν[E]\mathbb P_\nu[\mathcal{E}] is properly lower bounded. This is the central intuition conveyed by the proof overview in Section 6.2.

The formal proof in Appendix C.5 follows precisely this roadmap, with the stopped experiment providing a rigorous justification for the second step. A standard approach to establishing indistinguishability is to bound the KL divergence between the trajectory distributions induced by the two instances. However, directly bounding the KL divergence between the full-trajectory distributions Pθ\mathbb P_\theta and Pν\mathbb P_\nu does not yield the desired result. Specifically, on the event NU(T)>m{N_{\mathcal U}(T)>m}, the algorithm may pull arms in U\mathcal U substantially more than mm times. Such trajectories can contribute significantly to the full-trajectory KL divergence, preventing us from obtaining a sufficiently tight bound.

To address this issue, we introduce the stopping time τ\tau, defined as the first time the algorithm pulls an arm in U\mathcal U for the (m+1)(m+1)-th time, or TT if no such time exists. Under this definition, the event E\mathcal E is measurable with respect to Fτ\mathcal F_\tau. Crucially, on the event NU(T)>m\\{N_{\mathcal U}(T)>m\\}, the portion of the trajectory after time τ\tau, which may contribute substantially to the full-trajectory KL divergence, is marginalized out. Consequently, the KL divergence between the restricted distributions Pθ∣Fτ\mathbb P_\theta|{\mathcal F\tau} and Pν∣Fτ\mathbb P_\nu|{\mathcal F\tau} is smaller and can be upper-bounded by the desired quantity.

We view the stopped experiment as a technical device for formalizing the intuition that the two instances remain indistinguishable as long as the algorithm has not sufficiently explored U\mathcal U. For this reason, we originally omitted it from the high-level proof overview. Nevertheless, we agree that the original presentation could incorrectly suggest that the pull-count bound on E\mathcal{E} directly controls the full-trajectory KL divergence. We have therefore revised Section 6.2 to explicitly distinguish the event-restricted intuition from the formal stopped-experiment argument, and clarified the motivation for introducing the stopping time in Appendix C.5.

Q3: Appendix A absorbs an additive 1/21/2 into the claimed regret bound, which tends to zero when A=K−1A=K-1 and T=KT=K.

A3: Thank you for catching this issue! We have fixed this issue in our revision.

Thank you for the response and revisions. These largely address my concerns, and I maintain my scores.

Two minor corrections remain: (i) reverse the final ceiling comparison on page 14 and retain log⁡(2TK)\log(2TK) in the subsequent bound on LL; (ii) use the additive total-variation comparison from Appendix C.5 in Section 6.2 to make the constant-probability conclusion explicit

We thank the reviewer for the follow-up comments and helpful suggestions. We are glad to hear that our previous rebuttal has addressed your main concerns.

Q1: Reverse the final ceiling comparison on page 14 and retain log⁡(2TK)\log(2TK) in the subsequent bound on LL.

A1: Thank you for catching this remaining issue! We have revised Appendix A.1 to correct the direction of the inequalities involving the ceiling functions and consistently replaced log⁡(2T)\log(2T) with log⁡(2TK)\log(2TK) wherever the logarithmic factor arises from LL.

Q2: Use the additive total-variation comparison from Appendix C.5 in Section 6.2 to make the constant-probability conclusion explicit.

A2: Thank you for this suggestion! We have revised lines 475–483 of the manuscript to explicitly state that the change-of-measure argument relies on an additive comparison in total variation distance. We then apply Pinsker's inequality to establish a constant upper bound on the total variation distance, thereby making the constant-probability conclusion explicit.

Reviewer_E6k4OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper characterizes the minimax regret rate for multi-armed bandits with A optimal arms. Assuming A is known, the authors provide a regret-minimizing algorithm which achieves regret O~(K−AKAT)\tilde O(\frac{K-A}{\sqrt{KA}}\sqrt{T}), where KK is the number of arms and TT the time horizon. Moreover, they show that this bound is tight. This improves over the previous bound O~(KT/A)\tilde O(\sqrt{KT/A}) for large AA. Finally, the paper extends existing impossibility results for adapting to an unknown number of optimal arms.

Critical strengths

The study of settings with multiple optimal arms is interesting and well motivated. The paper completes the characterization by extending the existing bound to the regime in which almost all arms are optimal, namely K−A=o(K)K-A=o(K).

Critical weaknesses

My main concern is the significance of the improvement over previous work. Whenever A is a constant fraction of K strictly smaller than one, the new bound has the same order as the previous bound. The improvement concerns the regime in which the fraction of suboptimal arms vanishes, which might seem a not so significant regime. I would have liked a stronger explanation of why this regime is important.

A second concern is the limited technical novelty of the upper-bound analysis. The algorithm follows the same framework as previous work, and the improvement appears to come from a relatively simple refinement of the analysis. For example, when A≤K/2A\le K/2, the regret rate in Theorem 4.1 already follows from previous guarantees. Since A is assumed known, this regime can be handled directly using existing results.

Questions for authors

Why is the regime K−A=o(K)K-A=o(K) important?

Could you clarify how your approach differs from previous work and which ideas are new?

4 comments

Thank you for your supportive feedback! We answer your questions as follows.

Q1: The improvement concerns the regime in which the fraction of suboptimal arms vanishes. Why is this regime important?

A1: We appreciate this thoughtful question and agree that when K−A=Ω(K)K - A = \Omega(K), the previous Θ~(KT/A)\tilde{\Theta}(\sqrt{KT/A}) bound [1,2] already captures the minimax order. Nonetheless, resolving the complementary regime K−A=o(K)K - A = o(K) is essential for a complete and tight theoretical understanding of bandits with multiple optimal arms. Intuitively, as AA increases, the problem becomes progressively easier and must eventually incur zero regret when A=KA = K. However, the prior bound O~(KT/A)\tilde{O}(\sqrt{KT/A}) saturates at O~(T)\tilde{O}(\sqrt{T}) across the entire range A=Θ(K)A = \Theta(K), predicting no further gain as AA approaches KK (for example, missing a polynomial factor of KK when A=K−1A = K - 1, where the true minimax rate is Θ~(T/K)\tilde{\Theta}(\sqrt{T}/K)), while existing lower-bound arguments break down once K−A=o(K)K - A = o(K). To our knowledge, our work is the first to establish a tight minimax characterization Θ~(K−AKAT)\tilde{\Theta}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T}\Big) across the full range 1≤A≤K−11 \le A \le K - 1, smoothly bridging the classical Θ(KT)\Theta(\sqrt{KT}) rate at A=1A = 1 and the zero-regret limit at A=KA = K.

Beyond completing the minimax rate characterization, the regime K−A=o(K)K-A=o(K) reveals qualitatively new statistical phenomena that do not arise when K−A=Ω(K)K-A=\Omega(K). First, this regime gives rise to an overlapping structure that is absent when A<K/2A<K/2. This structure necessitates fundamentally different techniques for establishing the lower bounds and non-adaptivity results compared with those used in the non-overlapping regime A<K/2A<K/2. In particular, as discussed in Section 5.2, when A>K/2A>K/2, any two instances in ΞK,A\Xi_{K,A} necessarily share optimal arms, rendering the standard Le Cam two-point argument ineffective. Addressing this challenge requires a new construction of hard instances and additional technical tools, such as Proposition 5.3, to transfer probability bounds between the distributions induced by different instances. Similarly, for the non-adaptivity result when A+B>KA+B>K, the overlapping structure again precludes a direct application of Le Cam-type arguments, motivating a novel characterization of the exploration profile, as demonstrated in Lemma 6.4.

Second, this regime reveals a fundamental separation between expected and high-probability minimax regret. While both criteria share the Θ~(KT/A)\tilde{\Theta}(\sqrt{KT/A}) rate when K−A=Ω(K)K-A=\Omega(K), any algorithm achieving the optimal O~(K−AKT)\tilde{O}\Big(\frac{K-A}{K}\sqrt{T}\Big) expected regret in the regime K−A=o(K)K-A=o(K) must still incur Ω~(T)\tilde{\Omega}(\sqrt{T}) pseudo-regret with probability Ω((K−A)/K)\Omega((K-A)/K), as established in Remark 4.2 and Appendix D (Theorem D.1).

Q2: The technical novelty of the upper-bound analysis is limited. Could you clarify how your approach differs from previous work and which ideas are new?

A2: We would like to highlight the three key technical novelties of our paper.

Our first novelty is the sharper upper-bound analysis. While we acknowledge that the previous analysis in [1,2] is already sufficient for the regime K−A=Ω(K)K-A=\Omega(K), it is loose in the complementary regime K−A=o(K)K-A=o(K), as they miss a key effect: when optimal arms make up almost all of the arms, the sub-sampled set consists almost entirely of optimal arms with high probability. Our analysis uses this saturation effect directly, which improves the bound by a factor of Θ~((K−A)/K)\tilde{\Theta}((K-A)/K). To our knowledge, this observation and the resulting improvement have not appeared in prior work.

The minimax lower bound for the regime K−A=o(K)K-A=o(K) also incorporated substantial technical novelty. As discussed in Section 5.1, the lower-bound technique in [1,2] requires the hard instances to have disjoint sets of optimal arms. When K−A=o(K)K-A=o(K), the optimal sets necessarily overlap, so this construction cannot be used. To address this, we first construct a new family of hard instances, consisting of a set of symmetric instances together with the instance where all rewards are equal. We further introduces a new application of the multiplicative change-of-measure argument (Proposition 5.3), which lets us compare these overlapping instances. Neither the instance construction nor this use of change-of-measure appears in prior work.

Moreover, we extend the previous non-adaptivity results from the restricted A+B≤KA+B \leq K, to full range of A>BA>B such that A=ω(B)A=\omega(B). Prior non-adaptivity results [2] hold only for A+B≤KA+B\le K, because their proof builds hard instances whose optimal sets do not overlap. This is impossible once A+B>KA+B>K. We extend the result to the full range A>BA>B with A=ω(B)A=\omega(B). Our proof uses a new characterization of the exploration profile of any near-minimax algorithm on ΞK,A\Xi_{K,A}. The characterization shows that when AA is close to KK, any such algorithm must explore in a highly non-uniform way. That exploration pattern conflicts with the one required to be near-optimal for small BB, and this conflict yields the non-adaptivity result. The exploration-profile characterization is itself a new technical tool.

In summary, our technical novelty consists of three parts: the sharper analysis of the sub-sampling algorithm for K−A=o(K)K-A=o(K); the first matching lower bound for the regime K−A=o(K)K-A=o(K), based on a novel design of hard instances and a new application of the change-of-measure argument; and the non-adaptivity result for the overlapping regime A+B>KA+B>K, based on a novel characterization of the exploration profile.

References:

[1] Zhu, Yinglun, and Robert Nowak. "On regret with multiple best arms." Advances in Neural Information Processing Systems 33 (2020): 9050-9060.

[2] De Heide, Rianne, et al. "Bandits with many optimal arms." Advances in Neural Information Processing Systems 34 (2021): 22457-22469.

Thanks for the detailed response. I will maintain my positive evaluation of the work.

Thank you for your support!

Reviewer_hfTDOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies stochastic multia-armed bandits with exactly A optimal arms. For T≥KT\ge K, it establishes the expected minimax regret Θ~(K−AKAT)\widetilde{\Theta}\left(\frac{K-A}{\sqrt{KA}}\sqrt{T}\right). The upper bound follows from a refined analysis of an existing subsampling algorithm. The main lower-bound contribution concerns instances with many optimal arms, where overlapping optimal sets prevent the usual construction using two instances with disjoint optima. The paper also extends non-adaptivity results to this overlapping regime and establishes a separation between expected regret and certain high-probability guarantees.

Critical strengths
  • The paper is very well-written. As a nonexpert in the field, the paper is very clean and provides well-written technical overviews for the main proofs, highlighting which parts of the proofs are new.
  • The paper builds on established work on multi-armed bandits and studies an interesting problem setting.
  • The authors give a tight characterization on the complexity of minimax regret for this problem.
Critical weaknesses
  • (Minor): The practical motivation might be limited. Multiple satisfactory answers need not correspond to exactly equal expected rewards.
Questions for authors

N/A

1 comment

Thank you for your supportive feedback! We answer your questions as follows.

Q1: The practical motivation might be limited. Multiple satisfactory answers need not correspond to exactly equal expected rewards.

A1: We thank the reviewer for raising this point. While exact reward ties arise directly under binary pass-or-fail feedback (where every valid solution attains the same optimal mean r∗r^*), our theoretical conclusions also extend naturally when a set Agood⊆A\mathcal{A}^{\mathrm{good}} \subseteq \mathcal{A} of AA near-optimal arms has slightly unequal expected rewards satisfying r∗−r(a)≤δr^* - r(a) \le \delta for all a∈Agooda \in \mathcal{A}^{\mathrm{good}}, where r∗=max⁡a∈Ar(a)r^* = \max_{a \in \mathcal{A}} r(a). We discuss the exact mechanism of how our main results extends to this setting as follows

First, under standard regret against the strict global maximum r∗r^*, our upper bound in Theorem 4.1 carries over directly whenever δ=O~(K−AKA T)\delta = \tilde{O}\Big(\frac{K-A}{\sqrt{KA\,T}}\Big). Specifically, applying the three-event decomposition in Section 4.1 with Agood\mathcal{A}^{\mathrm{good}} in place of Aopt\mathcal{A}^{\mathrm{opt}}, the per-round regret on Eopt={B⊆Agood}\mathcal{E}_{\mathrm{opt}} = \{\mathcal{B} \subseteq \mathcal{A}^{\mathrm{good}}\} increases from 00 to at most δ\delta, while on Esub\mathcal{E}_{\mathrm{sub}} the best sampled arm satisfies r∗−max⁡a∈Br(a)≤δr^* - \max_{a \in \mathcal{B}} r(a) \le \delta. Algorithm 1 therefore achieves Regret(T)≤O~(K−AKAT)+δT\mathrm{Regret}(T) \le \tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T}\Big) + \delta T, which preserves the O~(K−AKAT)\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T}\Big) rate verbatim for any δ=O~(K−AKA T)\delta = \tilde{O}\Big(\frac{K-A}{\sqrt{KA\,T}}\Big). Notably, in the many-optima regime A>K/2A > K/2, this threshold is also tight under standard regret: if K−AKT≪δ≲1Tlog⁡K\frac{K-A}{K\sqrt{T}} \ll \delta \lesssim \frac{1}{\sqrt{T \log K}} (for instance, one arm with mean 1/21/2 and A−1A - 1 arms with mean 1/2−δ1/2 - \delta), those AA arms remain statistically indistinguishable over TT rounds, so by the same change-of-measure argument as Theorem 5.2, any learner must pull the (1/2−δ)(1/2 - \delta)-arms Ω(T)\Omega(T) times and incur Ω(δT)\Omega(\delta T) regret against r∗r^*.

Additionally if we consider the relaxed setting, where all top AA arms are viewed as satisfactory solutions and regret is measured relative to the AA-th largest mean reward r(A)r_{(A)}, namely ∑t=1TE[(r(A)−r(at))+]\sum_{t=1}^T \mathbb{E}[(r_{(A)} - r(a_t))_+] [1], then (r(A)−r(at))+=0(r_{(A)} - r(a_t))_+ = 0 on Eopt\mathcal{E}_{\mathrm{opt}} and (r(A)−r(at))+≤max⁡a∈Br(a)−r(at)(r_{(A)} - r(a_t))_+ \le \max_{a \in \mathcal{B}} r(a) - r(a_t) on Esub\mathcal{E}_{\mathrm{sub}}. Under this benchmark, Algorithm 1 achieves O~(K−AKAT)\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T}\Big) for arbitrary reward differences among the top AA arms, with exact-tie instances ΞK,A\Xi_{K,A} serving as the canonical worst-case class.

References:

[1] Chaudhuri, Arghya Roy, and Shivaram Kalyanakrishnan. "Quantile-regret minimisation in infinitely many-armed bandits." UAI (2018): 425-434.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.