Evolution of Information in Interactive Decision Making:  A Case Study for Multi-Armed Bandits
Authors: Yuzhou Gu
Yanjun Han
Jian Qian
Venue: NeurIPS 2025 poster ()
Keywords: multi-armed bandits
mutual information
Fano's inequality
Primary area: theory

Abstract: We study the evolution of information in interactive decision making through the lens of a stochastic multi-armed bandit problem. Focusing on a fundamental example where a unique optimal arm outperforms the rest by a fixed margin, we characterize the optimal success probability and mutual information over time. Our findings reveal distinct growth phases in mutual information---initially linear, transitioning to quadratic, and finally returning to linear---highlighting curious behavioral differences between interactive and non-interactive environments. In particular, we show that optimal success probability and mutual information can be decoupled, where achieving optimal learning does not necessarily require maximizing information gain. These findings shed new light on the intricate interplay between information and learning in interactive decision making.

Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits
Yuzhou Gu New York University yuzhouguênyu. edu
Yanjun Han New York University yanjunhan@nyu.com edu
Jian Qian New York University
jianqianEnyu. edu
Abstract
We study the evolution of information in interactive decision making through the lens of stochastic multi-armed bandit problem. Focusing on fundamental example where a unique optimal arm outperforms the rest by fixed margin, we characterize the optimal success probability and mutual information over time. Our findings reveal distinct growth phases in mutual information- Conimation-iiitillly linear, transitioning to quadratic, and finally returning to linear linear- highlighinggg curious behavioral differences between interactive and non -on-interective environments. In partieular, we show that optimal success probability and mutual information can be decoupled, where achieving optimal learning does not necessarily require maxi- mizing information gain. These findings shed new light on the intricate interplay between information and learning in interactive decision making.
Introduction
Consider the following instance of stochastic multi- aulti-armed bandit problem: there are arms in total, where the optimal arm a" [n] is uniformly at random, and the reward distribution of arm is
Ber
1+
if==
(1)
Ber
otherwise.
Here A E (0, 1] is fixed noise parameter. In other words, the best arm a² is uniformly better than the rest of the arms by a fixed margin A. Readers familiar with the bandit literature shall immediately find that this is the lower bound instance for the multi-armed bandit, where it is well-known (see, e.g., (Lattimore and Szepesvári, 2020, Chapter 15)) that the sample complexity of identifying the best arm is O [x ). In contrast, is also classical result (e.g., via Fano's inequality) that in the
non-interactive setting, the sample complexity becomes θ (n lo
In other words, the interactive sampling nature of multi-armed bandits offers O(log n) gain in the sample complexity compared with the non- inninteracctive sampling.
In this paper, we take closer look into this seemingly toy example, and investigate how an interactive procedure starts to accumulate information and identify the best arm below the sample complexity, i.e, when í < zz. Specifically, denoting by E [r]] the action taken at time and Hi (a1, Rt Ct, r( (+) the available history up to time I, we will study the following two quantities:
P. = sup P(ar+1 a 1 = sup I(a"; H.))
(2)
Alg
Alg
In other words, P is the optimal success probability of identifying the best arm a" after rounds, and It is the optimal mutual information accumulated through time horizon of t rounds. Here both supremums are taken over all possible interactive algorithms with the knowledge of n and A. In the rest of this paper, we will be interested in the evolution of P and I; as function of t, especially for the curious regime of small t. In fact, before the learner can reliably identify the best arm a", the optimal information 1 exhibits a nonlinear accumulation
for very small t we expect little
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

difference between interactive and non- non-interactive settings, so the heuristic from the non interactive setting would suggest linear scaling I; fAa, however, since the optimal bandit algorithm only n samples to identify the best arm reliably, we should have I x log n for this choice of needs t x 27
which is (log n) larger than the non-interactive heuristic. Again, just like the O(log n) gain in the sample complexity under the interactive case, even in this toy example, it is unknown when and how interactive learning departs from non-interactive learning and leads to nonlinear learning curve.
We remark that this stylized toy example is merely used for a case study, and that we do not intend to advocate the use of our algorithms in more general settings; they are designed specifically for theoretical analysis. However, in this case study, we find this toy example to be sufficiently illustrative for several interesting phenomena in interactive learning, as well as failures in existing approaches of establishing them:
1. Understanding the true shape of learning multi-armed bandits: The influential work (Garivier et al., 2019) characterizes the "true shape of regret" in bandit problems, where the growth of optimal regret progresses through three regimes: initially linear in time, then squared root in time, and finally logarithmic in time. Building on this, we ask for the "true shape of learning", especially for the initial phase (or the "burn-in" period). Even in the first regime, where the regret grows linearly, the optimal algorithm still engages in nontrivial learning, accumulating information about the environment. Notably, interactive learning plays a pivotal role in this initial phase, enabling G(log n) reduction in the sample complexity compared with the non- interactive approaches. Therefore, characterizing the trajectories of (vi, Ii), even in this toy example, provides deeper insight into the mechanisms of bandit learning beyond regret analysis. 2. Characterization of mutual information for general interactive decision making: There have been recent advances the statistical complexity of general interactive decision making, most notably the DEC (decision-estimatie One important remaining question in the DEC framework is to close the gap of the so-called "estimation complexity", which precisely corresponds to, in the multi-armed bandits problem, the O(log n) reduction of the regret. Towards closing this general gap, the recent work (Chen et al., 2024) develops a unified lower bound proposing to keep track of certain notions of information, such as the mutual information; however, this work does not address the problem of how to bound the mutual information in interactive scenarios. This task could be very challenging, as witnessed by another recent work (Rajaraman et al., 2024) which proposes an entirely new line of information -hteorrticcc analysis in the special case of non-lineaa ridge bandits. Unfortunately. as will be shown later, even in this toy example their tool falls short of giving the right evolution of I; in some important regimes. Therefore, this work adds new ideas and tools to the literature on bounding the success probability and mutual information in interactive environments.
coefficient) framework (Foster et al., 2021, 2022, 2023).
3. Exploring the interplay between information and learning: A more interesting question is whether the high-level proposal of using information to characterize interactive learning in (Chen et al., 2024) could have inherent limitations. In bandit literature, upper bound of Iž is often translated into an upper bound of pt (e.g., via Fano's 's inequality). Conversely, working in the ridge bandit setting inspired by (Lattimore and Hao, 2021; Huang et al., 2021), (Rajaraman et al., 2024) leveraged the reverse direction, critically using an upper bound of p. to bound the information gain 1,+1 1 in interactive settings. However, it is a priori unclear if some of these links could be strictly loose, where the evolution of P (learning) may not always align with the evolution of I (information). For instance, the algorithms that achieve optimal learning may not accumulate the largest amount of information. If such discrepancies arise, mutual information alone might not suffice establish fundamental limits of learning, and new technical tools will be called for. Our multi-armed bandit example is very natural and exactly identifies this important separation.
Notation and terminology. Logarithms have base e. For two non-negative functions f and g, we use f S.S g (or means that S f: and f x g (or f = (gg) means f S and g S f. For probability measures P and Q over the same space, let QV(P,Q)
O(g)) to denote that f < Cg for a universal constant C 0; f Z 9 (or f = l(g))
1 [ dQI be the total variation distance, (P) = f(VaP - 2 be the squared Hellinger distance, and (L(I))Q) = I dP dr be the Bullback-Leibbe divergence. For joint distribution Pxy, let I(X;Y) = KL (Px be the mutual information between X and Y. For x. y E R. let x Ay == min(s,y) and x V == max(z, y). Instead of calling upper and lower bounds which may cause confusion, throughout the paper we will use "achievability" to refer to lower bounds of p and 7, via constructing explicit algorithms, and "converse" to refer to upper bounds of pG and 1; that hold for all possible algorithms.
do
2

---

1.1 Main results and discussions
Our main result is a complete characterization of the optimal success probability pi and the optimal mutual information I
Theorem 1.1. Assume 0 < A -1(1). For 2 L, we have
AAa
if If I
ift 1
n ((
if < t S log
Pr
if1 t S n
x=
(3)
log
if log < t I
ift
log 92
if
Furthermore, all achievablity results can be attained by Algorithm in Section 2.
Remark 1.1. The same characterization also holds for the frequentist counterpart of p defined as Pī,F = suPAtg min P-. (A++1 a²). This follows from PÝ,F I Pi, and that the achievability results in Algorithm I achieve a frequentist guarantee. However, the definition of the mutual information I does not directly extend to the frequentist setting.
Remark 1.2. The achievability results for P can be obtained using an algorithm which randomly samples T arms and runs bandit algorithm with optimal regret them (such the median climination algorithm in Even- wer- et al. (2002)). However, it is unclear whether such an algorithm can attain the achievability results for 17-
In comparison, in the non-interactive case, the corresponding quantities are
t
[N x tA?
Pi,N
n2 log( 1 + AA2)'
whenever S. a log For completeness we include the proof of (4) in Appendix B. Comparing A
(3) and (4), we see that while Pi,Nı is slightly sublinear in (due the logarithmic factor on the denominator), P. becomes precisely linear in t after exiting the easy regime p x 1. become evident in algorithm, this difference arises because, in the interactive case, the learner can strategically sample suboptimal arms fewer times.
n² As will
The evolution of information in the interactive case is more intriguing. While [N grows linearly in t, the growth of I features three distinct transitions at 1 x 1, log n, n. Intuitively, since ((1/A²) pulls of an estimate its mean reward within accuracy A with constant probability, we define m = / 2 E [0, ni. as the "effective" number of arms pulled by the algorithm. Depending on m, the evolution of I follows four distinct regimes:
1. First linear regime m I. 1: In this early stage, the time is too limited to learn even single arm. The optimal strategy is to query single arm chosen uniformly at random, making the process non-interactivv. Consequently, the growth of 1 is identical in both the interactive and non-interactive cases, exhibiting a linear dependence on t.
2. Quadratic regime 1
< log In this intermediate regime, the time budget suffices to confidently learn one arm but not to achieve (1 - 1/n) confidence. Interaction now plays a crucial role: the learner observes the arm's performance and decides whether keep pulling for more confidence or switch to a new arm. The optimal strategy is to stick with the current arm if preliminary estimates suggest it is promising, otherwise switching explore different arm. This strategy ensures that the information gain / - Iī is proportional to the probability of pulling the best arm, which increases with thanks interaction. As result, 1 exhibits quadratic growth with f.
3. Second linear regime logn m S. n: In this regime, the best arm can be identified with high confidence if pulled, and pulling it yields diminishing returns in terms of additional information. The total information gain determined by the probability of identifying the best arm within the time budget, which scales as m/n and again linear in m (and t). Compared with the first linear regime, the slope here benefits from an additional Ollg n) factor, for the best arm can now provide Ologg n) bits of information once pulled, again thanks to interaction.
4. Saturation regime m > n: In the final regime, the learner can reliably identify the best arm, so the quantity I saturates at its maximum value (log n), the Shannon entropy of a (nl).
3

---

Finally, we examine the relationship between learning and information accumulation. A classical inequality between p and I is the Fano's 's inequality (Fano, 1968), which in our setting can be expressed as
p S 1 + h2(pt)
(5)
log
where h2(p) :- p plog| + (1 p) log p-p is the binary entropy function. Using the upper bound hz(p) S p log 1
p
p + p, this simplifies to:
rip Ir. p log
(6)
From (3) and (4), it is clear that the relationship (5) (or (6)) is tight in the non-interactive case, and in the interactive regimes where tタ² O(1) tA? 2221), However, in the intermediate regime of the interactive case where 1 > and log(t = o(log n). Fano's 's inequality becomes strictly loose. This looseness is not specific to Fano's inequality but applies more broadly mutual information. Notably, there exists an algorithm in this regime that achieves the optimal success probability pt while accumulating strictly less information than L; (see Section 4.2). This indicates that the success probability p cannot always be inferred from mutual information alone. This surprising observation suggests that mutual information, while powerful, may be insufficient fully characterize the fundamental limits of learning in interactive decision making.
The potential looseness of Fano's 'ss inequality also introduces new challenges on the technical side. For certain values of f, we require tools beyond mutual information to establish tight converse results for pt. Existing approaches fall short, particularly when aiming prove small success probability (see Section 4.1). ) To address these gaps, we propose the following technical innovations for the converse:
1. To upper bound the success probability pj. we devise reduction scheme which relates pž for small to 2 for large t, and utilize the classical result pI S 1- - c for some constant value of O when t 27. A noteworthy feature of this reduction is the use of the same algorithm employed in the achievability results as a component of the reduction itself, a novel interplay between these two facets of the analysis.
2. To upper bound the mutual information I;, for t S log we critically leverage the upper bound A
of P (established via the aforementioned reduction) to constrain the information gain. This presents an intriguing contrast Fano's inequality, where 1 is typically used to upper bound p;: here, we reverse the roles and use pa to bound /;- For large / we use a simple but powerful mhange-of-divergence technique to obtain the additional O(log n.) factor.
1.2 Related work
Multi-armed bandits. The multi- bandit problem dates back to (Robbins, 1952; Lai and
Robbins, 1985). Early algorithms like UCB and EXP3 achieved an Ö(vnTT) minimax regret bound, which is tight up to logarithmic factors (Auer et al., 1995, 2002a.b). (Audibert and Bubeck, 2009) first removed this extra logarithmic factor-the key difference between interactive and non-interactive settings- via new potential (INF policy) or an optimistic upper confidence bound (MOSS algorithm). Extensions of these algorithms, such as the anytime variant (Degenne and Perchet, 2016) and best-of- both-worlds guarantees (Zimmert and Seldin, 2019), are also available in the literature. However, a deeper understanding of the trajectories of these algorithms in the initial learning period is still missing, and the tight separation between non-interactive and interactive algorithms largely remains mystery for general decision making after a rich line of DEC developments (Foster et al., 2021, 2022, 2023; Chen et al., 2024). A similar mystery holds for the mutual information: for example, while information-direee
sampling (Russo and Van Roy, 2018) seeks to maximize the information gain in the initial steps, its analysis critically relies on the information ratio (Russo and Van Roy, 2016) and does not provide insights into the evolution of information.
Best arm identification. Our problem formulation in (1), modulo the specific prior a* Unif( aligns with best arm identification in multi- bandits. Algorithms based on various principles such as the frequentist method of UCB (Bubeck et al., 2011) and arm elimination (Audibert et al., 2010) or the Bayesian method of knowledge gradient (Frazier and Powell, 2008) and Thompson sampling (Russo, 2016), have been proposed for best arm identification. In particular, the asymptotic complexity in the fixed confidence setting has been completely characterized in (Garivier and

---

Kaufinann, 2016), and progress has also been made on the fixed budget setting (Carpentier and Locatelli, 2016; Kato et al., 2022: Komiyama et al., 2022). The stopping rule used in our Algorithm I is inspired by this body of work and relies on the sequential probability ratio test dating back to Wald (Wald, 1945). Under our problem formulation, it also known that the "median elimination algorithm" in (Even-Dar et al., 2002; Mannor and Tsitsiklis, 2004) achieves the optimal sample complexity without the log 7 factor. However, most existing guarantees for best arm identification are inapplicable for small time horizons É or when the error probability is 1 1-o(1). For example, although (Audibert et al., 2010) established a lower bound of exp(-(c+ (1)))A2//)) on the error probability specialized to our setting, the o(1) factor becomes negligible only when 2 n² n2/2?. As another example, the error probability upper bound exp(-(c+ (()))t (H log n)) in the fixed budget setting of (Komiyama et al., 2022), with H x X in our setting, has extra (log n) factor and requires large >> n²2 Similar requirements for large t are also present in the results of KattzSSamulss and Jamieson, 2020; Zhao et al., 2023; Carpentier and Locatelli, 2016; Karnin et al., 2013; Atsidakou et al., 2022). In contrast, our work establishes the tight probability of success for small S A as well, and identifies curious phase transitions in the mutual information behind the large error probabilities.
Feedback communication and noisy computation. The objectives of minimizing error probability and maximizing mutual information align closely with concepts from feedback communication, a classical topic in information theory (Burnašev, 1980; Tatikonda and Mitter, 2008). For instance, (Burnašev, 1980) established upper bounds on mutual information that reveal two distinct phases in interactive environments, which parallel the "burn-in phase" and "learning phase" in our problem. Although interactive decision making operates under a more constrained model than communication systems-learners can only pull one of arms rather than utilize an arbitrary encoder- perspective in (Burnashev, 1976) has proven valuable in addressing recent noisy computation challenges, such as noisy sorting (Wang et al., 2024), particularly for deriving converse results. However, unlike in feedback communication, our multi-an aemd bandit problem does not always exhibit linear growth in mutual information during the "burn-in phase".
Our problem can also be framed novel noisy computation task, where the learner would like to locate the maximum of a random permutation of ((1 + A)/2, (1 22, (1 - 2) through noisy queries. Recent years have seen a resurgence of interest in such problems, revisiting classical questions in noisy sorting (Wang et al.. 2024; Gu and Xu, 2023) and the noisy computation of thresh- old (Wang et al., 2025; Gu et al., 2025), MAX, and OR functions (Zhu et al., 2024). These works often leverage a powerful converse technique from (Feige et al., 1994), which reduces interactive environ- ments to a two-phase process comprising a non-interactive phase and an interactive phase that returns the clean output. We will show in Section 4.1 that this approach does not directly succeed in our problem. Our converse results on success probability are derived using a distinct reduction method.
Converse techniques. Beyond the techniques in (Burnašev, 1980; Feige et al., 1994) discussed carlier, we review additional methods used to establish converse results in the statistics and bandit literature. The most common approach for proving regret lower bounds in multi-armed bandits relies on a change-of-measur argument (Lai and Robbins, 1985) (see also (Lattimore and Szepesvári, 2020, Chapter 15.2) for minimax lower bounds and (Simchowitz et al., 2017) for more advanced treatments). However, as these methods are special cases of Le Cam's 's two-point method, the resulting lower bound on error probability cannot exceed 1/2 (achievable by random coin flip). Even when generalized to test multiple hypotheses, as we show in Section 4.1, this approach still yields a weaker converse result p. = ((1/n + (vt/n A (t/n))a).
Controlling mutual information can overcome the limitations of the two-point method, Despite that early works (Agarwal al., 2012; Raginsky and Rakhlin, 201 la.b) showed that the amount information acquired by an interactive algorithm could be harder to quantify, this approach has been revisited recently in the interactive framework (Rajaraman al., 2024; Chen et al., 2024). For instance, (Chen et al., 2024) extended the idea of (Chen et al., 2016) to develop an algorithmic version of Fano's 's inequality for interactive settings, but did not address the critical problem of bounding mutual information. This challenging task was tackled in (Rajaraman et al., 2024) in the context of ridge bandits using an induction argument that required the success probability at each step to be exponentially small, allowing the application of a union bound. However, this approach fails for multi-armed bandits, as even a random guess achieves success probability of ((1/n) at each step, which is not small enough to apply union bound. This is the high-level reason why such an
5

---

Achievability for pi Section
Converse for pi, large
Converse for p; small Section 3.2
Section
Algorithm Scction
Achievability for 4i Appendix
Converse for d/ large Section
Converse I small Section 3.3
Figure Dependency between different parts of our proof of Theorem 1.I. We make one node opaque to highlight that achievability results for pł are also available in the literature (cf. Remark 1.2).
argument can only be applied for small & < log,. for larger t, different technique- on A²
change-of-divergenne argument-providde the correct upper bound on mutual information. While conceptually simple, this method offers the first known proof (to the authors' knowledge) of lower bounds in multi-amin aanti-areed bandits using mutual information and Fano's inequality.
1.3 Organization
The rest of the paper is organized follows. In Section 2, based the sequential probability ratio test, we introduce a simple algorithm (Algorithm 1) for identifying the best arm a". Based on the theory of biased random walks, we show that this algorithm achieves the claimed success probability (in Section 2) and mutual information (in Appendix A). Section 3 establishes the converse results for Pž and Iř, and the proof distinguishes into the cases of large and small For large t, directly establish an upper bound of I; and apply Fano's ' inequality to upper bound p, The converse analysis of small / more involved, where the upper bound of P is proven via reduction to the case of large i, with the help of the same algorithm in Section 2. Furthermore, this upper bound of př is crucially used in information-theoretii argument upper bound I;. Dependency between different parts of our proof of Theorem 1.1 is shown in Figure 1.
We provide some discussions in Section 4. Specifically, establish the suboptimality of several existing approaches for the converse in Section 4.1, and prove the separation between learning and information gain in Section 4.2.
2
Achievability
In this section we show a simple algorithm can strategically sample suboptimal arms fewer times and achieve the success probability lower bounds Theorem 1.1. This algorithm is based on the sequential probability ratio test for Ho Ber (يد against H1 r Ber (1+ described in Algorithm 1.
Algorithm 1 SEQUENTIAL PROOUETTTTAPPPL..LLLEETTTTTTTTTT
input: action set A, number rounds f, noise parameter A
2: output: an estimate of the best arm à E A
3: Permute A uniformly random. Relabel elements of A as I,..., where [A].
4: 0 < 11/A
5: for 1 n do
6: X'+0
7: while true do if s = 1 then return @ =
8:
9:
Pull action i and receive reward ra E {0.1)
10:
X + X + 2r) 1, s ++1 +1
Random walk for X
11:
x < then break
12:
return
Under Bernoulli rewards, the sequential probability ratio test is biased random walk for each arm, with bias A for the best arm and bias - A for all suboptimal arms. Algorithm I its walk drops below the threshold 0 = -1 A, and keeps pulling the arm otherwise. The key property of biased random walks is that, it only takes (11/²²) steps in expectation for suboptimal arm to reach the threshold 0, while with 2(1) probability the best arm never hits This a consequence of the following standard results stopping times of biased random walk (c.g., (Feller, 1970)).
I eliminates an arm once

---

Lemma 2.1 (Stopping time of biased random walk). Let < 0 and 0 < A < 1. Let (Xe) be random walk starting from with i.i.d. steps drawn from some distribution D, which either D- = 1- + - D+ = - + - 8-1- Let T E NU (+00) be the stopping time for Xr S Then the following statements hold:
(a) For the downward random walk D = D_, ET - - a:
(b) For the upward random walk D = D_, PPT < x0) S
S exp(220).
1+A
Based on Lemma 2.1, we prove that Algorithm achieves the success probability lower bounds in Theorem 1.1. We restate the result here for convenience.
Theorem 2.1 (Achievability for success probability). Algorithm achieves the success probability bounds in Theorem I.1.
In the remainder of this section, prove Theorem 2.1 for t S A2 as a larger only makes learning easier. First, we restate the algorithm:
1. Permute the arms uniformly at random.
2. For each arm i, the random walk (X)) starts at with steps from D+ if is the best arm, and from D_ otherwise. All walks are independent.
3. For each i E [n]. let T, be the first time that X7; S S =0=-1/A. Return arm where is the small-
est index such that Σi= Ta > L. If such exists (i.e. all arms eliminated), return 1.
Now let m [ < and define three events: let E1 be the event that the best arm is among the first m arms (after the random permutation); let &S be the event that Σ Eisism, T₁ S t, where is the optimal arm after the random permutation; let & be the event that T:- =
00. =00
Clearly, when & n & O &3 holds, Algorithm outputs the best arm. It remains to lower bound the success probability ((E)NE)EEs) Clearly (PE)) n and P(EglE)) S exp(2A0) e-2 < 1/5 by
Lemma 2.1. In addition, by Markov's incquality, IP(E)(E;) S E Eisism T.
m-1 0.1
TA
by Lemma 2.1 and the definition of Therefore,
0.7m
+ 1 1+
P(& 3 2 P(E)))))))))))) (1 (1-P())))- P(E(E)))
Ω
n
n
which is our target. We defer the proofs of achievability results for mutual information to Appendix A.
3
Converse
In this section, we prove converse results on pž and I7 as illustrated in Figure 1.
3.1
Converse for large
This section establishes the following converse results for I; and Pž for large t.
Theorem 3.1 (Converse for large t). The following statements hold under the setting of Theorem 1.1:
(a) For any 2 0, we have I S t log log n. .,1))
(b) For any 2 A2, we have P 1 A
The remainder of this section is devoted to the proof of Theorem 3.1.
argument to prove the converse for Ir Recall that H, denotes the history up time t and at denotes the optimal arm. For any fixed algorithm, we have
Mutual information. We apply a
T(a"; H.) = E., [TT. [KT.(P.. [Px.)] S (2 log R.a (HP(Pr.lar: PH..)
(b)
< 2(2 + logn) inf (Ea- [H2 (Pr Pu.)] + H2 (PH.: PH.))
PH:
(c)
(d) 4(2 log n) inf E. [22 (P PM))) I 4(2 + log inf E. (KL,H,, [Pr) Prs
PHi

---

Algorithm 2 BOOSTING(A, I, A, A)
1: input: action set A, number of rounds f, noise parameter A, boosting parameter m, algorithm A for best arm identification with time budget
2: output: estimate of the best arm ā E A
3: <-
4: for from to do
5: Permute uniformly at random
6: Let 04 AAA, 1, A) be the best estimate returned by algorithm A in rounds
7: B < B {ai}
8: Remove duplicate elements from B and let m' be the remaining size ROW m'/ A)
9:
return
> Algorithm
where (a) uses (Yang and Barron, 1998, Lemma 4) and notes that thanks to a* Uni(((n), the density ratio of the two arguments in the KI. divergence is upper bounded by almost surely, steps (b) and (c) use the triangle inequality and convexity of the Hellinger distance, respectively, and (d) follows from HP Q) I KL(PIIQ).
Now let PH. be the dummy model where all arms have reward distribution Ber A)) and E be the expectation taken with respect Ph.- By the chain rule of the KL-divergence,
1 +
A
1
A
1(a, -
E. [KL(HH.l) (PH.lIPuala)) ([lP Eg.
E
KL
Ber
Ber
/A2
$ SE
B[A a')]
n
where the first inequality follows by the assumption that = 1- and the second identity follows by the symmetry between all arms for both P and a*, Combining all above, get 1ī x fA log The other upper bound 17 z (a*) ) = log
trivial.
Success probability. Suppose that t 2
n= for some constant > 0. By the upper bound of 17 2
and Fano's 's inequality (6), we have Pt log upi S 1; S tA? log
If p 2 ta? then Pt log np: 2
Pł log ž cpt log n. Combining both inequalities we conclude that p n
!A and pt S trivially.
Success probability for small
This section establishes the converse results for pt in the entire range of S n/
Theorem (Success probability converse for small l). Under the setting of Theorem 1.1, we have P S 1+rA² for < n X=
The proof of Theorem 3.2 is via reduction from the success probability lower bound for large and the following boosting argument.
Proposition 3.1. For any integers I, 2 0 it holds that Pmtt+m/ AA 2 2
pf )m
Proof. Suppose A is an algorithm that achieves the optimal success probability pI using t pulls. Let Aboust be the boosting algorithm given Algorithm 2, which runs algorithm m times to obtain candidate action set B of size m' < m. and then runs Algorithm on the action set B. We establish Proposition 3.1 by showing that Aboost always uses most probability Ω (1 pł) ).).
m/ A pulls and achieves success
Number of pulls. Pulls are used only in Lines 6 and 9. Line 6 is executed m times and each time uses pulls. Line uses m'/A /2 pulls with m Therefore the total number of pulls is at most mt + m/ 2
Success probability. Because we permute the arms uniformly at random before each call in Line the event that each call succeeds (i.e. outputs the best arm a²) are independent. Let & be the event that the optimal arm in B, then (P{E] 2 1 - (1 - mm Conditioned E, there a unique optimal arm in B. By Theorem 2. Line 9 succeeds with probability I(1). Therefore the overall success

---

probability of Aboost is f1 - (1 (0-pp (.
We are now ready to prove Theorem 3.2. By Proposition 3.1, there exists > 0 such that
Pmt+m/42 2 c1(1 (1 p)) By Theorem 3.1(b), for any 02 O, there exists C3 with P Pagn/A2 $ C2. Take C2 = / and choose C3 accordingly.
Let (c/n/(122 + 1) that mt + m/A² < can/A². By the previous paragraph,
have 2 2 Pe Penn/2 2 (1 (1 pt) 2 c1 (1 - -mpp) Solving this inequality gives that
P S log2 tA'+1 establishing Theorem 3.2.
m
3.3 Mutual information for small
This section establishes the converse for 1 when log Note that when result in Theorem 3.1 is already tight.
log A
the converse
Theorem 3.3 (Mutual information converse for small f). The following statements hold under the setting of Theorem I.I:
(a) For t S AT. we have 17 < 1
(b) For 1
logn 2 <ts
AT, we have I 2 (123)²
The proof of Theorem 3.3 follows from Lemma 3.1 and Theorem 3.2 by simple calculation.
Lemma 3.1. For any t, it holds that I, - A2 -
Proof. Given any learning algorithm. let I, = I [aa; H.) be the mutual information accumulated by this algorithm until time s. In the sequel upper bound the information gain I, - using the upper bounds of P in Theorem 3.2.
By the chain rule of the mutual information, we have La ---1 = [aa;; :r [H ag). By the variational representation (e.g., (Polyanskiy and Wu, 2025, Theorem 4. 1)) of the mutual information I(X;Y Y Z) = min@riz Σx,z KL (Py (9y1x.21lQx12)) we have
1- 1-4
(( (H,-1, a.) S Eaa a. 1)
KL Progar
Ber
2
(1-A))
)
Faaa H1-))
KT. Ber
+ Al(as = (000=a0) =a*))
Ber
(?
2
2
S (a Ha-1)
LA a')] < A
Summing over = 1,...,4 completes the proof.
Discussions
4.1 Failure of existing approaches for converse
We comment on the failure of existing approaches in fully establishing the converse results in Theorem 1.1. The standard bandit lower bound (see, e.g. (Lattimore and Szepesvári, 2020, Chapter 15.2)) uses binary hypothesis testing arguments, and generalization to the uniform prior Unif([n]) (a variant of (Gao et al., 2019, Lemma 3)) reads as
P(a++1 = a²) s + inf Σ TV.P..P... 1=1
n
Po n
Here P, denotes the distribution of H4 under a" = i. and Po is any reference distribution. By choosing
Po to be the case where all reward distributions are Ber (²=A). it is easy to that (7) gives the tight bound pł < -1 for 0 and p; t, (7) only gives the following lower bound, which does not exhibit the correct scaling on A.
2(1) for x 4. However, for intermediate values of
Proposition 4.1. For any 2a. there exists learner such that infy, EE TV(P,, a ((+ v ))

---

Next, we consider the two-phase approach in (Feige et al., 1994), whose failure is more delicate. Specialized our problem, the idea in (Feige al., 1994) consider stronger model with two phases: 1) in the non-interactive phase, each arm is pulled 1 1/A² times; 2) in the interactive case, the learner can query m = [t arms based on the outcome from the non-interactive phase, and an oracle gives clean answers to the learner about the true mean rewards of the queried arms. Clearly this m model can simulate our original model, so a converse on this stronger model taking the form P S n (i.e. the second phase is still "random guess") would establish the converse in the original model. However, the following result shows that the learner can perform strictly better under the new model.
there exists a learner under the two- two-phase Proposition 4.2. For t of ) and A = ol Vlog T2
model which achieves a success probability Z exp (S2 (vlog -
w
122
Finally we discuss the inductive proof of the converse result of (Rajaraman et al., 2024), which inspires our argument in Lemma 3.1. Its failure is straightforward: each inductive step of (Rajaraman et al., 2024) derives upper bound of p from the current upper bound of I7, which in view of the following section is inherently loose for ! E (I) (2)))
4.2 Optimal algorithm with suboptimal mutual information
In the introduction, by comparing Theorem 1.1 with (5) and (6), we see that Fano's 's inequality does not give a tight relationship between P; and 7, when t E w(1) n oo()) One may wonder if some relationship between pt and It, other than Fano's inequality, turns out be tight for any learning algorithm. The answer turns out to be negative, as shown by the following result where an optimal algorithm may achieve suboptimal mutual information.
Proposition 4.3. There exists a learner achieving the optimal success probability ( S A. but a suboptimal mutual information O (12 log(t = =o(Tt) if E w(1) O (o1))
Proposition 4.3 implies that generic relationship pt S S(1) that holds for any algorithm cannot be used to establish the tight converse for the success probability. The new algorithm is described in Algorithm 3 in the Appendix: the main difference from Algorithm 1 is an upper threshold 6, >> 0 for the random walks such that the best arm is pulled for fewer times (i.e. early stopping), ensuring the same success probability but providing less information.
4.3 Fixed time budget vs stopping time
Another interesting question is how our results change when the fixed time budget / is relaxed to stopping time with expectation at most l. Let P, and Ii be the corresponding quantities when the algorithm can stop at such stopping time, clearly P 2 po and L7 2 IT- The following result gives tight characterization for p and an achievability result for Ii,
Proposition 4.4. Fort tart= < N. it holds that P
L+AA² and 1i, 6 log
T
Comparing Proposition 4.4 with Theorem 1.1, one observes that the elbows for the optimal mutual information evaporate upon allowing random stopping time. Intuitively, by randomization a learner can achieve the upper convex envelope of I,, so that Li exhibits fast linear growth even at the very beginning. We conjecture that the achievability result for di in Proposition 4.4 tight; see Appendix C.5 for more discussions.
Acknowledgments and Disclosure of Funding
YH is supported in part by an AI for Math grant from Renaissance Philanthropy. JQ acknowledges support from ARO through award NSF through awards DMS-200 2031 883 and PHY-2019786.
as well as the Simons Foundation and the
10

---

References
Alekh Agarwal, Peter L Bartlett, Pradeep Ravikumar, and Martin Wainwright. Information information-theoreticc lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 58(5):3235-322 -2449, 2012.
Alexia Atsidakou, Sumeet Katariya, Sujay Sanghavi, and Branislav Kveton. Bayesian fixed- budgeb best-arm identification. arXiv preprint arXiv:2211.08572, 2022.
Jean-Y Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pages 1-122, 2009.
Jean-Y Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In Conference on Learning Theory, 2010.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pages 322-331. IEEE, 1995.
Peter Auer, Nicolo Cesa- (esa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learming, 47(2-3):235-256 2002a.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert H. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002b.
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in finitely-armed and continuous- armed bandits. Theoretical Computer Science, 41 +12(119):832-1855 2011.
MV Burnašev. Sequential discrimination of hypotheses with control of observations. Mathematics of the USSR-Izvestiya, 15(3):419, 1980.
Marat Valievich Burnashev. Data transmission over discrete channel with feedback. random transmission time. Problemy peredachi informatsii, 10(4): 1976.
Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Conference on Learning Theory, pages 590-604. PMLR, 2016.
Fan Chen, Dylan J Foster, Yanjun Han, Jian Qian, Alexander Rakhlin, and Yunbei Xu. Assouad, fano, and cam with interaction: A unifying lower bound framework and characterization for bandit learnability. In The T'hirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Xi Chen, Adityanand Guntuboyina, and Yuchen Zhang. On bayes risk lower bounds. Journal of Machine Learning Research, 17(218):1-58, 2016.
Rémy Degenne and Vianney Perchet. Anytime optimal algorithms in stochastic multi-armed bandits. In International Conference on Machine Learning, pages 1587-1595. PMLR, 2016.
Eyal Even-Dar, Shic Mannor, and Yishay Mansour, Pac bounds for multi- armed bandit and markov decision processes. In Computational Learning Theory: 15th Annual Conference on Computational Learning Theory, COLT 2002 Sydney, Australia, July 8-10, 2002 Proceedings 15, pages 255-270. Springer, 2002.
Robert M Fano. Transmission of information: statistical theory of communications. MIT press, 1968.
Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM Journal on Computing, 1001 1994.
William Feller. An Introduction Probability Theory and Its Applications, 3rd Edition. Wiley, 1970.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13448 2021.

---

Dylan J Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan. On the complexity of adversarial decision making. Advances in Neural Information Processing Systems, 35:35404- 35417, 2022.
Dylan J Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimen estimation coefficient. In The Thirty Sixth Annual Conference on Learning Theory, pages 3969-4043. PMLR, 2023.
Peter Frazier and Warren B Powell. The knowledge-gradient stopping rule for ranking and selection. In 2008 Winter Simulation Conference, pages 305-312. IEEE, 2008.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, 32, 2019.
Aurélien Garivier and Emilie Kaufmaann Optimal best arm identification with fixed confidence. In Conference Learning Theory, pages 998 1028-107.0000 2016.
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
Yuzhou Gu and Yinzhan Xu. Optimal bounds for noisy sorting. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1502-1515, 2023.
Yuzhou Gu, Xin Li, and Yinzhan Xu. Tight bounds for noisy computation of high-influence functions, connectivity, and threshold. In Conference on Learning Theory. PMLR, 2025.
Baihe Huang, Kaixuan Huang, Sham Kakade, Jason Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. Optimal gradient- based algorithms for non-concave bandit optimization. Advances in Neural Information Processing Systems, 34:29101-299 1900011211,111111 29, 2021.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International conference on machine learning, pages 1238-1246. PMLR, 2013.
Masahiro Kato, Kaito Ariu, Masaaki Imaizumi, Masatoshi Uehara, Masahiro Nomura, and Chao Qin. Best arm identification with a fixed budget under a small gap. Stat, 1050:11, 2022.
Julian Katz-Samuels and Kevin Jamieson. The true sample complexity of identifying good arms. In International Conference Artificial Intelligence and Statistics, pages 1781-1791. PMLR, 2020.
Mark Kelbert. Survey of distances between the most popular distributions. Analytics, 2(1):225-245. 2023.
Junpei Komiyama, Taira Tsuchiya, and Junya Honda. Minimax optimal algorithms for fixed- buddeb best arm identification. Advances in Neural Information Processing Systems, 35:10393- 10404, 2022.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4 22, 1985.
Tor Lattimore and Botao Hao. Bandit phase retrieval. Advances in Neural Information Processing Systems, 14:18801-18811, 2021.
Tor Lattimore and Csaha Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armes bandit problem. Journal of Machine Learning Research, 5(Jun):623 2004.
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge Univer- sity Press, 2025. Draft version available at https:: /tttppe//poppe..ee lids. mit. www.mmi.ttt..mmmmoee edu/yp/homepage/ fitaa/ttbookeeexpoo pdf.
Maxim Raginsky and Alexander Rakhlin. Information-hased complexity, feedback and dynamics in convex programming. IEEE Transactions on Information Theory, 57(10):006-7755, 201 la.
12

---

Maxim Raginsky and Alexander Rakhlin. Lower bounds for passive and active learning. In Advances in Neural Information Processing Systems, pages 1026-1034, 201
Nived Rajaraman, Yanjun Han, Jiantao Jiao, and Kannan Ramchandran. Statistical complexity and optimal algorithms for nonlinear ridge bandits. The Annals of Statistics, 52(6):253722882, 2024.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Sociery, 58(5):527-535, 1952.
Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, pages 1417-1418, 2016.
Damiel Russo and Benjamin Van Roy. An information analysis of thompson sampling. The Journal of Machine Learning Research, 17(1):2442-2471, 2016.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-direeted sampling. Operations Research, 66(1):230-252, 2018.
Max Simchowitz, Kevin Jamieson, and Benjamin Recht. The simulator: Understanding adaptive sampling in the moderate-confidence regime. In Conference on Learning Theory, pages 1794 1834. PMLR, 2017.
Sekhar Tatikonda and Sanjoy Mitter. The capacity of channels with feedback. IEEE Transactions on Information Theory, 55(1):323-349, 2008.
Wald. Sequential tests of statistical hypotheses. The Annals of Mathematical Statistics, 16(2): 117-186, 1945.
Ziao Wang, Nadim Ghaddar, Banghua Zhu, and Lele Wang. Noisy sorting capacity. IEEE Transac- lions on Information Theory, 2024.
Ziao Wang, Nadim Ghaddar, Banghua Zhu, and Lele Wang. Noisy computing of the threshold function. In Algorithmic Learning Theory, pages 1313-1315. PMLR, 2025.
Yuhong Yang and Andrew Barron. An asymptotic property of model selection criteria. IEEE Transactions on Information Theory, 44(1):95-116, 1998.
Yao Zhao, Connor Stephens, Csaba Szepesvári, and Kwang-Sung Jun. Revisiting simple regret: Fast rates for returning good arm. In International Conference on Machine Learning, pages 421 42158. PMLR, 2023.
Banghua Zhu, Ziao Wang. Nadim Ghaddar, Jiantao Jiao, and Lele Wang. Noisy computing of the or and max functions. IEEE Journal on Selected Areas in Information Theory, 2024.
Huangjun Zhu, Zihao Li, and Masahito Hayashi. Nearly tight universal bounds for the binomial tail probabilities. arXiv preprint arXiv:2211.0 2022.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits, In The 22nd International Conference on Artificial Intelligence and Statistics, pages 467-475. PMLR, 2019.
13

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction accurately state the scope of the paper and the main contribution of the paper (Theorem 1.1).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: This is theoretical paper with explicit settings. The limitations are specified in the discussion of motivation (Section I) and the discussion section (Section 4).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
14

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced, and complete proofs are provided in either the main paper or the supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Thcorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
15

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This is theoretical paper and does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr http://guiiie//ooeuuusseseeeesse
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / mnipssccopublic//uidee wtwpiiideeeeeeeeeiiiisisiiieeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
This is theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
16

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is a theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is theoretical paper and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt///nuriip.oo
17

---

Answer: [Yes]
The research conducted in the paper conforms with the NeurIPS Code of Ethics.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification:
This is theoretical paper and there is no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is theoretical paper and there is such risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring
18

---

that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This is theoretical paper and does existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This is theoretical paper and does not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
19

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This a theoretical paper and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is a theoretical paper and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: This is theoretical paper and does not involve LLMs as any important, original, or ntn-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.LM policy (https: ftttps://neurips //tarrppp..cc///ofeeeeee///////2 for what should or should be described.
20

---

A Achievability for Mutual Information
In this section prove that Algorithm I achieves the mutual information lower bounds in Theo- rem 1.1. We restate the result here for convenience.
Theorem A.1 (Achievability for mutual information). Under the setting of Theorem 1.1, for & n Algorithm I achieves mutual information
A
(a) Ω
aA? when 0 S z
(b) Ω
when 1 3
<
t S
log n A
(c) ? (102 when
log A
< S
n A
Because the optimal arm chosen uniformly random, the random permutation step in Algorithm does not affect the mutual information achieved by the algorithm, and we remove it in the proof.
A.1 Proof of (a)
By chain rule of mutual information,
Σ I (a";is51 as41)
(8)
05a51-1
1 22. we have r(a"; Bot1 Hs,0s41) = Ω (4*). with hidden constant
We prove that for I
independent of For fixed S 3.. define & as the following event:
1. The first pulls are to the same arm (i.e., 01 =
1).
2. - < x < sA
2 T. where X denotes the value of X at time
We prove that
P(E) = f2(1),
(9)
12
(a drt1 H., a E,
(10)
n
Since the event can be determined by H., (9) and (10) imply that (a": He, as+1) =
Ω A? which implies the desired lower bound by (8).
Proof of (9). Let (Z,)i20 be an upward random walk starting from 0 with steps drawn from D+ = - 8 + - 8_ Let (W5)520 be downward random walk starting from 0 with steps drawn from D_ 1-AS, + و_1. Conditioned on a" = 1 (resp. a" * 1), the trajectory of the X variable can be coupled with (Zj) (resp. (W,) as long as it has not reached below 0 = -11 A
Let us first prove P(E = 1) = =(1) Let & denote the event that mingsuse Zn - and Z, < sA+ + 2. then P(E =) = -PE4). ). By Lemma 2.1(b), IP (mminnguu. Z, > - 2 é
By Hoeffding's incquality, (Z, 2 $A
S exp(- (2/A)² 2s S e By union bound, P( 2
1 1 2e = 2(1).
Let us now transfer the above bound to a* * 1. Let E_ denote the event that minogas. Wa > and W, < =A + 10 satisfying E+. Then
x. Then P(E + 1) = P(E_). Let (zo...., z,) be any trajectory of (2,),20
+ (s+,,)/2
28-2.)/2
IP ((Zo.... 2,) = =
2
2
21

---

and
-1+4 (a-2,)/2
1- A
(++x))/2
P ((WW 0...., W.) (20. :......:2.))
:2,)
2
1-4
=P((Zo).. .(....... [s) (20....,
I+A
Since for A = 1-1(1),
= =exp(-O(Az))) = =xp()))sA) = =((),
1+A
a change of measure gives that
P(E_) 2 P(E-) 2(1) = Q(1)
Consequently, P(E) 2 min (P(E4), =Q()).
Proof of (10). In the sequel we condition on &. Then the next pull the algorithm makes will to arm 1, i.e., 0s+1 = 1. For any i + we have Ka (==2)x; = =((1, which implies that PP(a* = 1|H, a,+1, 8) = θ (H). Therefore,
P(r2+t) = 1174, as+1, E, a- = =1) 1+A
2
1+ A
1 A P(a* 1|Hs, a,+1, 8) +
P(r 1/Hs 1,+1,
Paa" + 1/Ht, as+1, E)
2
2
1-
A
A
+
2
n
is then clear that
KL (. F-1
retl ( -S(A3).
Finally,
1(a'r100 (o (,,1 P(aa" -1KKL (P ( (
((A2)) 5
A
n n
A.2 Proof of (b)
If /. S A7 for some absolute constant C < to be chosen later, then this follows from (a) by
C
t 22 to -1 and the monotonicity of mutual information. In the following assume that t C and define a variable X measurable with respect to a" and variable Y measurable with respect to H.. By the data processing inequality, we have [(a;; H.) Z I(X;Y. So it suffices to prove the desired lower bounds for T(X;Y).
Let X 1 faa [m]), with algorithm pulls at most arms, and the random walk satisfies X > 0.1tA for the action â returned by the algorithm. We will prove the following estimates:
20.1 Let Y be the indicator for the following event: the
P(Y = 1|X = 1) = 2(11)
(11)
PPY 1|X 1)
log P(Y = 1 = 00) 2(112))
(12)
Proof of (11). The proof is a modification of the proof of Theorem 2.1. For k E [m 1]. let (W)) 320 be m independent downward random walks. Let (Zz)iz0 be upward random walk. Conditioned on X 1, we can couple the m bad arm iterations with W1 Wi...., W and the best arm iteration with Z.
22

---

Let Tj be the first time that T reaches 0 = 1/A,, and & be the event that Σ ~ Ta S 0.2t. By Lemma (a) and the same Markov's inequality in the proof of Theorem 1, we have P(Ei) 2 0.5.
Let Eg be the event that jinoggg: Zj > - By Lemma 2.1(b), P(E2) 2 1 - exp( 22. Let Eg be the event that Zo.8r 2 0.3tA. By Hoeffding's incquality, P(Eş) > 1 - exp (- (2t)) >
1 - exp (-C/8), which is 2 0.9 if we take C = O(1) large enough. Let & be the event that Z0.8t) Z -0.2 By Lemma 2b)(b), P(E)) 2 1- exp(-2 0.21 > mino,st-is: which is 2 0.9 if we take C' = O(1) large enough. Because & Eg, E4 are all monotone events in the steps of (Zz)520. we have P(E2 n & n & 2 P(E)))()))((E))) 2(1).
1 - e
Note that E3 n & implies that ming mijjo 23 2 0.1/A.
Via the coupling between the algorithm and the random walks (W2) and (2z),20. when El.... & all happen, we have Y = 1. Therefore PP(Y = 1|x = 1) 2 &( = 2(1).
Proof of (12), Fix a history He under which Y = 1. Let s denote the number of pulls to arm ã, then
(= (x+x*)//
(م-A) (s (s=x*)/2
X²
P( la = à) P(H|XX (2-4) (0+22)/2 (1+A) (s (x-x#)/2
1 +
2 exp (2Ax*) 2 exp(0.21A2).
1 - A
2
Therefore.
P(H. X = 1)
1
PHH la ā)
exp(0.21
m
P(H X 0) 2
2 exp(O.1tA2).
P(H X = 0)
[0.11271
Finishing the proof.
Let us prove KL(Py x=) = ?(tA²) using (11) and (12).
First, we have
IP(Y 1)
m
(1
m
P(Y 1|X- 0)
+
P(Y = 1|X =
11
n
P(Y = 1|X 1)
m
+
[1
m
exp( ((t(2))
n
n
_ exp( -exp((
m
< 2 max
In addition, it holds trivially that
P(Y = - 1)
P(Y = 0JX = 1) log
min x log(z)) -1. 0$#51
P(Y = 0)
Combining the above displays, we have
KT.(Py)==1llP>) = PPY = 1|X = 1) log IP(Y = 1|X 1)
+ +P(Y 0|X = 1) P(Y = 0| 1))
P(Y 1)
P(Y = 0)
2 9(1) min log n a(t22)) - -log?) 2) -1 1
= =((t)²)
where the last step follows from 2 2 C for a large enough constant C, and that log n = Mlogg) = 2(1 by our assumption of 1A2 2 & logn. Finally,
m
1(x;)) 2 P(X = (PYx-(P)))))))P)) = "h -((=)) = 1()
A.3 Proof of (c)
In fact, the only place where we used the assumption t < log n in the proof of (b) is to ensure that log n ?t(t for m ?0. Consequently, for log n < t S vn. the argument in the proof of (b) now gives
m
KL (I(Pyxx=llIPP) = 2(log
23

---

so that
m 2log n)
f log n
H(a ((XY)) 2 P(X 1)KL(Py/x=1111/)
f2
n
which is the desired result of (c). When vn S t n, recall the lower bound of the success probability Pt and Fano's ' inequality in (6) to get
Top:
1
1A ))
(A
log
I(a" H4) 2 Pe log
log
e
n
e
n
which is again the desired result of (c).
B Non-Interactive Case
In this section we prove (4) for non-interactive algorithms, restated as follows for / plogn,
1
1
PiNI
[N
n. log(1 + 1A2)'
n
Achievability for success probability. the largest integer solution
A non-interactive algorithm is as follows. Pick m E [n] as
4ym log m
A
St
so that Ω
2
log(1 (A2)
The learner randomly permutes the action set [n]. pulls each of the first m arms 1log times, and 2=
outputs the arm with the largest average reward. By the definition of m, this algorithm runs in at most rounds. With probability m. the best arm a* is one of the first m arms. Conditioned on that, the algorithm correctly outputs the best arm a with probability at least 1 (m 1)p by the union bound, where is the probability that a Bin
41og A
1+A random variable is less than or equal to
an independent Bin
mlogm A
1-A
random variable. By Hoeffding's inequality, we have
A²
4 m
p exp
2
A
m²
Therefore, the overall success probability of this algorithm is at least
m
3m
tAa
m²
4n
=
n log(1 + tA2)
Achievability for mutual information. The above algorithm also attains the optimal mutual information. For 1A > C' with a large enough constant = O(1), note that Fano's inequality (6) gives
:a);HH) 2 PI,II log 7Pt,NI = Ωt
1 log(1 + (A2) log
(1og(1
112 (oog(1 (1og(1+ + ))
(12
52
For 1 < 1, note that m 1 holds in the above algorithm, so it simply pulls a uniformly random arm (say arm 1) for t times. Then the scenario is precisely the same Appendix A.1. where 01 =
a; 1 always holds, and one can regard the auxiliary random walk X being recorded during the execution of the algorithm. Therefore, Appendix A.1 implies that T(a";r" Hs, ax+1)= = 2 A? for any S a with the hidden constant independent of s. By the chain rule, T(a He) 2 t for all AZ.
Finally, for the case 1/ < T., we simply the monotonicity of mutual information obtain
I(a" H4) 2 I(a"; (1/==))/s²) 2 (1))
(tA²
n
claimed.
24

---

Converse for mutual information. Suppose non-interactive algorithm takes actions d1 .1...... dt. Let :'......??? be the corresponding rewards. Because [aa; H₁) Eas....a, H, H.lo.......0 a.). we can without loss of generality assume that a1,-..:.0 are deterministic. Then (01, ri )...., (4t, rt are independent conditioned on a* So
H4) S
Σ I(a";)))) tI(a"))''). 2m
By Theorem 3.3(a), we have [(a";1]))
We thus conclude that [n S tAa
Converse for success probability. (6), we have
By the converse for mutual information and Fano's inequality
TPp.NI
(np(,NI) log
S NI O(taa).
Solving this inequality gives Pi 2 n. mog((++177)
1A2
C Deferred Proofs in Section 4 and More Discussions
C.1 Proof of Proposition 4.1
Consider the sampling strategy where each action is pulled for t/n times (for t < n we simply pull each of the first arms once). If n, then for any P, and Pj, by data-processing inequality,
1- Ber
Ber 1+ 1+
))
TV(P,, P2) 2 TV
[1 or j is pulled)
2
= I(i or j is pulled).
For any and j that are pulled, we have by the triangle inequality that for any reference distribution Fo.
TV(P., P.) TV(Po,P)) IV(P..
This shows that
tA TV P.) + Ω
inf Po
n
If 2 n, without loss of generality we assume that t/n an integer. For any P, and Py,, by data-processing inequality,
Bin t 1-4 t
1 4
TV(P,, PP)) Z TV
2
2
Here the last inequality uses the TV lower bound for two binomial distributions in Lemma C.2, whose proof is deferred to the end of this section. By the triangle inequality, we have that for any reference distribution Po.
t
TV,,, P.) TV(P., TV(P.,)))
Finally, this shows that for any choice of reference model
1
1 Σ TV(P.
1
inf Po
+2
1=1
Combining the above two cases completes the proof of Proposition 4.1.
To complete this section, we include some useful results, and the proof of (7) for completeness.
Lemma C.1. For any k 2 and k-yk < El
lttk 2
we have ( 2 2k
AVE
25

---

Proof. We have
((+(1)/22) (k/2)
Vk/22
k/2
II
k/22 + vk/2-1 -
VR22 II :=1
vk/2
k/2 + V1//2-1
VR/2
2 21
Σ
Vk/2
2
1
k/2+ vk/2 -
2'
1=1
where have used the simple inequality II Thus, we obtain
(1 a:)
1 Σ ag for al,,.,, an (0, 1).
k
1 1/1 k
2
(K++ /
2 2 k/2
2
AVT
where the last step follows from Stirling's approximation.
Lemma C.2. For any TV (Binkk,, 1 Bin ++ parameter and p.
< A 2(1), for any integer 1 such that k 1, we have
2 )) Z VkA? where Bin(k, p) denotes the binomial distribution with
Proof. By Kelbert (2023, Proposition 6), we have
TV TV(Bin(k Bin(k, 1 A ), Bin(k; 1+
++A)
(1+A)/2
P(Sx-1(u) -- 1)du,
(1-A1/2
where 14- ~ Bin(k 1, u) and is in the interval [k(1 / k(1 + A)/2). By Lemma C.I. we have for any [[1 22, (1
A) and & E [k(1 ( A)/2].
P(S ll 1)
1
(1 A) 1)--1444/2 (1 + A) 1)
1-1-12/2
>
1
4v k
Vi
In turn, we have shown
TV Bin(k; 1 A 1 A k
1+-4
(1+A)/2
Bin(k,
P(SA-1(u) = 1)du
2
(1-2)/2
1
~ k A
VkA?
V
This concludes our proof.
Proof of (7). This is essentially (Gao et al., 2019, Lemma 3) applied to the star graph with center Fo. For any fixed distribution Po. we have
1 Σ
P(a+1 = =a) =
P. Pa = a.))
Pol(a+1 = TV(P,,
TV(Po,
n
Then, by taking infimum over the distribution Po. we obtain the desired result.
C.2 Proof of Proposition 4.2
Consider the following learner under the two-phase model: The learner computes the total reward for each arm in the first phase, and then queries the [ arms with the highest total reward in the interactive phase. W.l.o.g., assume a* = n and that the total rewards for each arm are Rı, Ry, Clearly the learner succeeds if R,, is among the largest numbers in Ri,..., R,.
26

---

Define the threshold u² > 0 as the solution to
2
Ber( u²A || Ber
1 1 +-))
))
m
1 exp
A
KL
2
=
2n
(13)
By Pinsker's inequality, we see from (13) that 2² = Olvlog #t As A
of Vlogn
1
we have
u" A ((1) and therefore
u
Berl 1+ = (u* + A))
KL Ber
2
2
from which we readily conclude from (13) that 2² = 0 log ) In addition, since m = o(n) and A o( Viogn) for large enough n have 2 S u² 22
Next we invoke accurate tail estimates for the binomial distribution in Lemma C.3. Since R₁ ) for any i E [n 1). the upper bound in Lemma C.3 gives
Bin( d2, =
1 A
P(R: 2 2
i [n-1]. 1].
2n'
Since R1,"
Rn-1 are independent, the Chernoff bound gives
1 4 u² A
There are more than m suboptimal arms with total rewards larger than
2A²
1 u² A
m
1)m==== = = -1)
E
m/2
P
R Z
2A2
1=1
This implies that IP(E = (1). Moreover, by the lower bound in Lemma C.3, we have
1 1 4² A
1 u
1 2
1 2 A
1 A - ))
P RM >
exp
KT.
Ber
Ber
2A2
2
By simple algebra,
KT. Ber( 1 - u²
1 1-4)
1
-
u²
A
1 + A ))
1 A 1 A
Ber(
KT.
Ber(
Ber(
... A log
2
2
2
1 1²
A
1
1 A
s KL
Ber
Ber(
)) u2= 2
2
2
This, in turn, gives us
P Rn
1 u² A
1
exp
1
KL
Ber(
1 -
22 A
}
Ber(
1 A
1
)) c²"
2A²
u
A2
2
2
(13)
4n
Altogether, by independence of go and Rn we have shown that
pt 2 P 0 and Rr 2 ++
A
(Q
(n( log i^
n
)
1A2
exp
2
n
where we recall that u² = -og/lo )). This concludes our proof.
Lemma C.3. Let A E (0, 111 and E 12, 1. For X ~ Bin 3Z holds that
1- and Y ~ Bin(
1 1+ ), it
Ie, 2
P(X
> 1+4 < 2 exp(
NZ (Ber I-HA I-VA
Ber 1+4
2
IP(Y
H4A
exp(
J (
Ber
1- 2
2A
1tu
Proof. By (Zhu al., 2022, Theorem 2.1 and 2.2), we have
1 uA)
4 (
I-AA 2A
1+A 2
1
1- u1 =u)
1 A 2
2 ))
P x
exp
KL
Ber
Ber(
2
2T
A
A
2
27

---

where the function L(k,z, p) is defined as
2), x kp v (kp 1 x 1)2 + 4(1 pp)
2(1 p)r
=1
kp+1 x Vkkp + 1 x)) + 4(1 p)r
We thus estimate
uA 1 A 2
2 21 I-nA
=1+
22
1 2A2
1
1t + V (1+ +
1tu 2 )² + (1-م)\--5)
22
22
A
(1 A (1 -A)
< 1
2
A
(1 + A) A)(1 + uA)
1
2A (1 + u)
A(1 +
where the last step uses (1 + A)(1 uA) < 5 1
1 2
< 2. Thus combining with the assumption that
S 23
we have
1 +
4
4AL
I-vA 1+
us >1 2
1 1 1+A
))
P
x
2A
exp
KL
Ber(
Ber(
2A²
v 2T(( 12
A2
2
I+u u (- AZ
2
1
- uA
1 4 1) Ber(
1+4
exp
KL
Ber(
as desired. Similarly, we have for the other side by (Zhu et al., 2022, Theorem 2.2).
1+ uA
2AL
I-NA ) AV. 23
1
Berr 1 uA 2
Ber( 2 - )
KT.
exp
2
V8(1 V8(1-22A7) u²
A
We lower bound the function L. as
(1+A)(1-ua)
1
uA
1 1
A
L
= -1
2A
A
212
2
1 4-1
+ 1(1
x-1 2 +
(1+1)1-aa)
24
24
A²
(1 A) (1 UA)
1+
A(1+u)
Thus, we have
1+ uua u
2AL( A7: 2A
1-4A IA
us
1 1-41 ))
P Y 2
exp
KL
Ber(
Ber(
2
V 8(1 A222)
A
2
2
1-
1 1-
A 2
))
exp
1 KT. Ber(
Ber(
1 u
2
This concludes our proof.
C.3
Proof of Proposition 4.3
We present an algorithm (cf. Algorithm 3) that achieves an optimal success probability but suboptimal mutual information when i E w(1) 201)
-2 AT.
Success probability. The proof is a modification of the proof of Theorem 2.1. The main difference between Algorithm 3 and Algorithm 1 is that in addition to the lower threshold 6j, we now have an upper threshold 6,, When the random walk for an arm reaches 8,, we immediately return as our estimate for the best arm instead of continuing pulling it. Another minor difference is that, Algorithm 3 only pulls the first w = 2 arms, even if the time budget has not been exhausted.
By the same reasoning as the proof of Theorem 2.1, Algorithm 3 can be restated as follows.
28

---

Algorithm 3 PIDDTTEESSQQUENTTAPPPRAAAIIII
1: input: action set A, number of rounds t, noise parameter A
2: output: an estimate of the best arm E
3: Permute A uniformly random. Relabel elements of A as 1,..., where |A].
4: <- [1A7], 0r -1/A, 0, log
log ++
5: for i 1 to w do
Only explores the first w arms
6:
X" <
7:
while true do
8:
if 8 f then return @ =
9:
Pull action and receive reward rf E {0,1]
10:
X 4- X + 2r) 1, 8 s
11:
X 2 0, then return =
b Early stops for a promising estimate
12:
if X S 0, then break
13:
return
1. Permute the arms uniformly at random.
2. For each arm i, if arm i best arm, let (X)) the upward random walk (starting from O with steps drawn from D+); otherwise let (Xj)520 be the downward random walk (starting from with steps drawn from D_). All these random walks independent.
3. Let T, the first time that X1; I 0 and U; be the first time that X 2 6,. Let é be the smallest index such that Σkenj Ta > and j be the smallest index such that Uj < co. either i or exists, return arm [i. Otherwise return arm 1.
w(1) Let m [0.11A Because f E A n A= we have m E w(1) no(1) Let be the event that the best arm is among the first m arms (after random permutation). Let &g be the event that Lie(m]((r> T; < i, where is the optimal arm after the random permutation. Let Eg the event that U, = oo for E [mm] Mi*) Let & be the event that Tü = cc. If & n & & n & happens, then the algorithm returns the correct answer after rounds. the following, we prove that PE E n n E4) = (=).
Clearly, PFEE) = m By the same proof as Theorem 2.1, we have P(Eg(&1) 2 0.9 and (1) 2 1 1-e -ee" 2 It remains to consider Eg. By Lemma 2.1(b), for i # 1" IPU; < xo) < (1 + with
[/A 27 By union bound, &)) m-1 < 0.1. Therefore
u
- P P(ET)E)) = Ω
m (
This completes the proof.
Mutual information. The analysis relies on an explicit expression for the posterior distribution Pa Pa-1H, of the optimal arm given observations. Given H,, let s; denote the number of pulls arm and 6; denote the value of X when the algorithm returns, for each E [n]. Then we have
P(H,la" =
(gytos)/2
(+1-0))/2)
( A (aitc:)/2 /1 (1- - A
(#:-c;)/2
- A
1+4 A
2
2
A
1 A
exp
c; log
A
I
A
By Bayes' theorem, the posterior distribution Pa-1H, satisfies
PH (i) exp (c log I- A
1 + A
(14)
In particular, the posterior distribution depends only 's. but not on s,'s.
29

---

Let dp be the last arm pulled by the algorithm (before it returns). Let U S [n]] be the set of arms that were pulled, excluding in- Let S [ni] be the set of arms that were not pulled. Note that [U] S 1 and [n|] UUVU U ( Next we compute the posterior distribution Pa (P4, based on (14). For
i E U, we have C₁ = [0r]. and
1+4
1 A A exp [ log
exp
log
exp (+()) (().
T-
In the middle step have used the assumption A Q((). For i V, simply have G; O. For the arm in. we have Oi
< Cip & [0,] 80
(2(1) exp
Cio log +
I exp
[0, log
1 A
S exp logg w + log
1 + A
A (ww).
A
1
1-
A
Consequently, according to (14), the posterior distribution of a* given H4 is
a
P Pa-Ine =
7
7 7
U
where exp (10r) log } ( b exp
Clo log 1
e and
Z ka + b + (n ---1
the normalizing factor, with k |U| w 1. By the above expression of ParIH,, we have
KL (Pa (Pa-116, 176, (nif( = k log
a
na
+
b
log
nb
+ (n
- k
log
n z
Z
Z
Z
Z
n
a 7
log
+
log + 7
log
7
Z
ka log + b log
+
Z
k a
+
bb 1
ka log a + b blog
Z
w log w
n
so that
uu log =0 (1 (1A2log((42)
- n
I(a"; H4) En, [KL
n
which is the claimed result.
C.4 Proof of Proposition 4.4
" and return a uniformly random arm otherwise. The expected number of pulls is f/v 1t? = t. When the former happens, we get 12(1) success probability and Q(log n) mutual information by Theorem 1.1. When the latter happens, we get 1. success probability and mutual information. So the expected success
Achievability. We run Algorithm with 2 rounds with probability 142
(12 + (1-) =
maxx { 1 12? { and the expected mutual information n
probability is Ω
is 1
(A3 log v2
Converse for success probability. By Theorem 1.1, there exists > such that any algorithm that always makes at most en A² pulls has success probability at most 0.1. Now suppose we have an algorithm A that makes 0.1en queries in expectation. By Markov's inequality, the probability that A
A makes more than AZ queries is at most 0. Let A'' be the algorithm that runs A, but stops and returns a uniformly random arm when A is about to make more than X7 queries. Then A' always makes at most en queries, thus has success probability at most 0.1. By union bound, has success probability most 0.2. We have proved that Pi_ S 0.2 for any algorithm that makes most 0.1er queries in expectation. The rest of the proof uses the boosting argument in Section 3.2 and is omitted.
cm
A
30

---

C.5 A conjecture for the stopping time setting
We conjecture that our achievability result for Te in Proposition 4.4 is tight (i.e., T S and leave this as an open problem.
1 log
Using the randomization argument in the above proof, one can show that f45, is non-inereasing
function in t. Therefore, our conjecture is equivalent to that lim L X A logg
n
Let us briefty discuss the difficulty in proving tight converse for L The most natural idea is to adapt our proof of Theorem (a) to the stopping time setting. During the proof, we need to upper bound inf p E [KI. (Px.l Pr.jaa) for model Ph. of our choice. For the fixed time budget case, we choose PH. be the dummy model where all arms have reward distribution Ber أش ). However, for the stopping time case, it is not guaranteed that the expected number of pulls under this dummy model still most t. In fact, there exist algorithms that have expected number of pulls t under the actual model, but have infinite expected number of pulls under the dummy model. Therefore, is unclear how to adapt the proof of Theorem (a) to the stopping time case.
31


Reviews:
[{"review_id": "sTEbksoxJA", "reviewer": "Reviewer_qePv", "summary": "This paper investigates the mutual information (MI) and the probability-of-error objectives in a classical stationary Bernoulli bandit ranking & selection problem, where the best arm must be identified after a fixed number of samples. The authors provide a rigorous theoretical analysis demonstrating that the policies optimizing cumulative MI about the best arm differ systematically from those optimizing the probability of correctly identifying that best arm. Additionally, the paper shows that standard information-theoretic tools, such as Fano’s inequality, can become loose in certain regimes, motivating novel bounding techniques.", "questions": "Can you provide clear, practical scenarios where the MI-based optimization objective would be naturally superior to the classic ranking & selection objective?\n\nWhy hasn't the existing ranking & selection literature (knowledge gradient, Bayesian optimization) already made this distinction clear? How does your information-theoretic perspective uniquely illuminate these subtle differences?\n\nAre your insights robust to more general settings (Gaussian or restless bandits)? How would your phase-based analysis of MI accumulation extend to these broader scenarios?", "limitations": "No. Actually not at all. I don't see any discussion of limitations, only some propositions in the Discussion. By failing to contextualing the current work conceptually in contrast to other related theoretical work on bandits, the Discussion also missed a chance to say how the current paper doesn't address but can potentially be expanded to address problems such as Gaussian reward distributions, restless bandits, contextual bandits, dueling bandits, etc.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nHidden conceptual depth: While initially appearing somewhat esoteric and purely theoretical, upon careful reflection the paper actually reveals a subtle and important conceptual distinction. Specifically, the authors implicitly characterize conditions under which one should optimize the probability of a correct decision (linear in error probability) versus those conditions under which one should optimize mutual information (logarithmic in error probability). While the former may seem more directly practically useful (choosing the right medication after a trial period, picking the right manufacturing process after prototyping several, etc.), the latter can also be quite useful for practical scenarios involving \"communication penalties\", or correctional overhead after decisions.\n\nTechnical rigor and clarity: The paper presents mathematically rigorous and clearly explained theoretical results. The phase-based analysis of MI accumulation is novel and provides a potentially useful framework for future analyses of related problems.\n\nPotential interdisciplinary relevance: The underlying insights could be relevant to diverse communities (information theory, ranking & selection, reinforcement learning, cognitive modeling), although the authors do not explicitly draw out these connections.\n\nWeaknesses:\n\nLack of practical framing: A major missed opportunity of this paper is the absence of any clear, practical motivation or interpretation of why and when one would care about the mutual information objective (versus classical success probability). Given the interdisciplinary interest in bandit tasks, it is especially important to provide intuition or motivation that would help a broader audience see practical implications of the theoretical insights. In its way of formulating the problem and relating to existing work, it appeared at first glance a pure intellectual exercise of interest only to information theorist, with little use or interest for the broader NeurIPS community. Upon deeper reflection, I feel that is not actually true (see my first point under Strengths above), but the authors didn't make sufficient attempt to relate to the broader community.\n\nNarrow contextualization: The authors largely frame their work as a novel application of information-theoretic analysis to a standard bandit problem, but they do not sufficiently engage with closely related literature (such as Peter Frazier's \"knowledge gradient\" and other ranking & selection literature), leaving readers without clear reference points for the importance and novelty of their contribution.\n\nLimited scope: The paper restricts itself to a highly stylized Bernoulli bandit scenario. Demonstrating or discussing generalizations (e.g., structured, contextual or restless bandits) could significantly strengthen the relevance and potential impact of the paper.\n\nI lean toward accepting this paper due to the subtle yet important theoretical insight it provides, which becomes clearer upon deeper reflection. The authors reveal that maximizing probability of correct identification (traditional ranking & selection) and maximizing MI (information-theoretic objective) differ fundamentally. However, it shouldn't be up to the reviewer or reader to have to come up with a motivation for how these two objectives correspond to two different classes of practically meaningful scenarios; it behooves the manuscript to make that front and center from the beginning. Thus, the authors should significantly improve how they communicate the broader practical value and relevance of their findings. Currently, the paper appears narrowly theoretical, diminishing its impact and appeal to the broader NeurIPS community.", "was_revised": true, "final_justification": "I thank the authors for providing the rebuttal. However, the rebuttal seems to consist largely of identical main text for all reviewers, and in particular do not really address or acknowledge my concerns or suggestions about more concrete discussions of practical utility or better contextualization with other existing work. As such, the rebuttal does not change my mind sufficiently to change my score.", "rebuttal": "We sincerely thank you for your thoughtful feedback and valuable suggestions.\n\n**General response**\n\nWe thank the reviewers for suggesting more topics of practical motivation and broader relevance. We will include more discussions accordingly. Indeed, our paper is not really about new algorithms but more a conceptual study about how the information gain (and success probability) behaves in adaptive settings in comparison to non-adaptive ones. The scenario we choose is a natural choice for studying mutual information in adaptive settings with general implications, for the following reasons: \n\n- Upper bounding mutual information is difficult for general adaptive settings and inspires recent works on ridge bandits [1] or linear bandits [2]; \n\n- Mutual information is conjectured to be key for understanding sample complexity [2], in addition to recent DEC progresses, which rely on two-point lower bounds; and\n\n- The specific multi-armed bandit case we use is standard for lower bound constructions, reflecting core challenges of the problem. In particular, here the simplicity of this setting is a strength, for it reveals a surprising phenomenon and underscores the need for new analytical tools even in this well-understood baseline scenario. \n\nWe make the following contributions by studying this special case: \n\n- We propose simple yet powerful tools to upper bound success probability and mutual information in multi-armed bandits, a canonical problem with a different structure from [1, 2], rendering their techniques inapplicable; \nWe reveal a decoupling between mutual information and optimal sample complexity, providing a surprising limitation of the general program in [2]. \n\n- We would also like to note that the algorithm is not really our focus: an algorithm which randomly samples $\\lceil t\\Delta^2 \\rceil$ arms and runs a bandit algorithm with optimal regret on them (such as the median elimination algorithm in [3]) would achieve the same success probability. Instead, we use an algorithm that is intuitive (making the source of the logarithmic improvement easy to explain) and simple to analyze the mutual information. \n\n**Specific response**\n\nCan you provide clear, practical scenarios where the MI-based optimization objective would be naturally superior to the classic ranking & selection objective?\n\n- The central motivation for studying MI is its universality in establishing lower bounds for regret [2]. More practically, it is possible to come up with bandit scenarios where MI is directly the target, including the well-known information-directed sampling algorithm in the bandit literature, and in cases like measuring a worker’s actual performance in terms of the information acquired as opposed to their final selection.\n\nWhy hasn't the existing ranking & selection literature (knowledge gradient, Bayesian optimization) already made this distinction clear? How does your information-theoretic perspective uniquely illuminate these subtle differences?\n\n- Thanks for bringing up these relevant topics. In short, existing works like the knowledge gradient (KG) [Frazier et al.] or Bayesian optimization focus on specific acquisition functions, often tied to expected improvement or posterior variance. While they are related to information acquisition, they do not explicitly study the trajectory of MI. We will include a more detailed discussion in the revised version.\n\nAre your insights robust to more general settings (Gaussian or restless bandits)? How would your phase-based analysis of MI accumulation extend to these broader scenarios?\n\n- Our results and observations still hold for other reward distributions such as Gaussian. Essentially, instead of a biased random walk on integers, we get a biased random walk on real numbers. The same statements will hold for both success probability and mutual information, whereas the analysis gets more complicated. Restless bandits, on the other hand, require a lot more investigation, and we believe it is a valuable future direction.\n\n\n[1] Rajaraman, N., Han, Y., Jiao, J., & Ramchandran, K. (2024). Statistical complexity and optimal algorithms for nonlinear ridge bandits. The Annals of Statistics, 52(6), 2557-2582.\n\n[2] Chen, F., Foster, D. J., Han, Y., Qian, J., Rakhlin, A., & Xu, Y. (2024). Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability. Advances in Neural Information Processing Systems, 37, 75585-75641.\n\n[3] Even-Dar, E., Mannor, S., & Mansour, Y. (2002, June). PAC bounds for multi-armed bandit and Markov decision processes. In International Conference on Computational Learning Theory (pp. 255-270). Berlin, Heidelberg: Springer Berlin Heidelberg.\n\n[4] Garivier, A., Ménard, P., & Stoltz, G. (2019). Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2), 377-399."}, {"review_id": "TsbAdlzJ1M", "reviewer": "Reviewer_QCA6", "summary": "This paper studies the evolution of information in interactive decision making through a toy multi-armed bandit instance where one optimal arm outperforms others by a fixed margin $\\Delta$. Providing the related literature and discussing in a detailed fashion, the authors find a good niche that has not yet been analysed and answered. The authors characterize the optimal success probability ($p_t$) and mutual information ($I_t$) over time, revealing distinct growth phases and demonstrating that optimal learning doesn't necessarily require maximizing information gain. The work provides both achievability results and matching converse bounds.", "questions": "1. **Extension to other MAB setups**: What are the possible relaxations to the current framework that could potentially be theoretically tractable? What are the barriers preventing extension to the other setups?\n\n2. **Regime Connections**: The authors talk about \"true shape of regret\". To that, how do the temporal regimes in this paper compare to the regime in the referenced paper? Do they have the same underlying structure or philosophy/intuition?", "limitations": "Apart from the toy model for the Multi-armed bandit setup, I do not think there are particular limitations that are not touched upon in the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n**Theoretical Sound**: The complete characterization with tight upper and lower bounds across all three regimes is mathematically sound (I have glanced at the proofs; I could have missed some details). \n\n**Surprising Insight**: The analysis of decoupling of $p^*_t$ and mutual information $I^*_t$ is a nice, interesting find and is genuinely surprising and challenges established intuitions about exploration-exploitation trade-offs. This would serve as a nice addition to the fundamental understanding of the multi-armed bandit theory.\n\n**Technical Innovation**: Several proof techniques come together in the proof: the change-of-divergence argument for large t, the reversal of Fano's inequality application, and the careful analysis of temporal transitions. This would serve as a nice template for future research in this direction. \n\n**Literature Integration**: The positioning relative to existing work is comprehensive and demonstrates a clear understanding of the broader landscape.\n\n**Weaknesses:**\n\n**Insufficient Motivation**: The paper fails to adequately justify why mutual information merits study as a fundamental quantity in this context. It would be a great addition to understand the impact of mutual information in popular established algorithms, which would make it a justified problem to pursue.\n\n**Presentation Gaps**: Several technical elements are introduced without a proper foundation (I could be mistaken):\n- Equation (2) presents I*_t and I(·,·) without definition\n- The \"frequentist approach\" reference in Remark 1.1 lacks context\n- Notation in the change-of-divergence argument (P_H_t, P̄_H_t, P_H_t|a*) appears without explanation\n\n**Further Ramification**: The theoretical insights offer no clear path toward any potential future improvement. After getting a better understanding of the dynamics of interactive decision making, one would assume there are some implications for better algorithmic design to follow.", "was_revised": true, "final_justification": "I am partially satisfied with the author's response on the importance of mutual information. However, I would have liked to see more ramifications of what they prove in the paper regarding the downstream impact.", "rebuttal": "We sincerely thank you for your thoughtful feedback and valuable suggestions.\n\n**General response** \n\nWe thank the reviewers for suggesting more topics of practical motivation and broader relevance. We will include more discussions accordingly. Indeed, our paper is not really about new algorithms but more a conceptual study about how the information gain (and success probability) behaves in adaptive settings in comparison to non-adaptive ones. The scenario we choose is a natural choice for studying mutual information in adaptive settings with general implications, for the following reasons: \n\n- Upper bounding mutual information is difficult for general adaptive settings and inspires recent works on ridge bandits [1] or linear bandits [2]; \n\n- Mutual information is conjectured to be key for understanding sample complexity [2], in addition to recent DEC progresses, which rely on two-point lower bounds; and\n\n- The specific multi-armed bandit case we use is standard for lower bound constructions, reflecting core challenges of the problem. In particular, here the simplicity of this setting is a strength, for it reveals a surprising phenomenon and underscores the need for new analytical tools even in this well-understood baseline scenario. \n\nWe make the following contributions by studying this special case: \n\n- We propose simple yet powerful tools to upper bound success probability and mutual information in multi-armed bandits, a canonical problem with a different structure from [1, 2], rendering their techniques inapplicable; \nWe reveal a decoupling between mutual information and optimal sample complexity, providing a surprising limitation of the general program in [2]. \n\n- We would also like to note that the algorithm is not really our focus: an algorithm which randomly samples $\\lceil t\\Delta^2 \\rceil$ arms and runs a bandit algorithm with optimal regret on them (such as the median elimination algorithm in [3]) would achieve the same success probability. Instead, we use an algorithm that is intuitive (making the source of the logarithmic improvement easy to explain) and simple to analyze the mutual information. \n\n**Specific response**\n\nExtension to other MAB setups: What are the possible relaxations to the current framework that could potentially be theoretically tractable? What are the barriers preventing extension to the other setups?\n\n- It is shown that the mutual information can be tractable for linear bandits [2]. For ridge bandits, a new notion of information (i.e. the chi-squared informativity) is tractable [1]. So our work complements these in a tabular setting like MAB. The main barrier remains the tractability of mutual information. Indeed, one central contribution of our paper is to provide a novel approach to bounding mutual information.\n\nRegime Connections: The authors talk about \"true shape of regret\". To that, how do the temporal regimes in this paper compare to the regime in the referenced paper? Do they have the same underlying structure or philosophy/intuition?\n\n- The connection is more on the topic of multi-armed bandits. We focus mainly on the initial phase of learning (where the regret grows linearly in time), a topic which is overlooked in the literature. For example, the “true shape of regret” in [4] treats all regimes in our paper as the linear regret regime, without revealing the surprising growth of success probability and MI. \n\n[1] Rajaraman, N., Han, Y., Jiao, J., & Ramchandran, K. (2024). Statistical complexity and optimal algorithms for nonlinear ridge bandits. The Annals of Statistics, 52(6), 2557-2582.\n\n[2] Chen, F., Foster, D. J., Han, Y., Qian, J., Rakhlin, A., & Xu, Y. (2024). Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability. Advances in Neural Information Processing Systems, 37, 75585-75641.\n\n[3] Even-Dar, E., Mannor, S., & Mansour, Y. (2002, June). PAC bounds for multi-armed bandit and Markov decision processes. In International Conference on Computational Learning Theory (pp. 255-270). Berlin, Heidelberg: Springer Berlin Heidelberg.\n\n[4] Garivier, A., Ménard, P., & Stoltz, G. (2019). Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2), 377-399."}, {"review_id": "Dxls5MIpqQ", "reviewer": "Reviewer_NFDf", "summary": "This work studies a stochastic multi-armed bandit instance where one optimal arm outperforms all others by a fixed gap. The authors study the optimal success probability and the mutual information over time. In particular, they show a a linear trend, then a quadratic, then linear again.", "questions": "Please try to address my concern 1 above. I'm more than happy to increase my rating as long as clear and convincing answers are provided.", "limitations": "n/a", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "My biggest concerns are the following:\n\n1) I have been trying unsuccessfully to exactly position this work in the literature, which makes it hard to compare their results to existing ones. \n\nThere already exist BAI results derived for fixed t: \n- Freq. Upper: \"Almost Optimal Exploration in Multi-Armed Bandits\" by Karnin et al,\n- Freq. Lower: \"Tight (Lower) Bounds for the Fixed Budget Best Arm Identification\nBandit Problem\" by Carpentier and Locatelli,\n- Bayesian Upper & Lower: \"Bayesian Fixed-Budget Best-Arm Identification\" by Atsidakou et al.\n\nOverall, although the authors make a strong case on the importance of studying the different values of the budget $t$, they haven't rigorously stated how existing works (the above and others) perform for different values of $t$.. And if their paper improves upon any existing guarantees. \n\n(Also studying success probability instead of standard error probability (as in the BAI literature) can be misleading in regimes where the success probability is of $\\Theta(1)$, but the error is still non-zero)\n\n2) Assuming knowledge of $/Delta$ is usually considered a very limiting practice. It allows to create a priori confidence intervals and test the arms against them. \n\nI am still very skeptical and would love to hear back clarifications from the authors on these.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your thoughtful feedback and valuable suggestions.\n\n**General response**\n\nWe thank the reviewers for suggesting more topics of practical motivation and broader relevance. We will include more discussions accordingly. Indeed, our paper is not really about new algorithms but more a conceptual study about how the information gain (and success probability) behaves in adaptive settings in comparison to non-adaptive ones. The scenario we choose is a natural choice for studying mutual information in adaptive settings with general implications, for the following reasons: \n\n- Upper bounding mutual information is difficult for general adaptive settings and inspires recent works on ridge bandits [1] or linear bandits [2]; \n\n- Mutual information is conjectured to be key for understanding sample complexity [2], in addition to recent DEC progresses, which rely on two-point lower bounds; and\n\n- The specific multi-armed bandit case we use is standard for lower bound constructions, reflecting core challenges of the problem. In particular, here the simplicity of this setting is a strength, for it reveals a surprising phenomenon and underscores the need for new analytical tools even in this well-understood baseline scenario. \n\nWe make the following contributions by studying this special case: \n\n- We propose simple yet powerful tools to upper bound success probability and mutual information in multi-armed bandits, a canonical problem with a different structure from [1, 2], rendering their techniques inapplicable; \nWe reveal a decoupling between mutual information and optimal sample complexity, providing a surprising limitation of the general program in [2]. \n\n- We would also like to note that the algorithm is not really our focus: an algorithm which randomly samples $\\lceil t\\Delta^2 \\rceil$ arms and runs a bandit algorithm with optimal regret on them (such as the median elimination algorithm in [3]) would achieve the same success probability. Instead, we use an algorithm that is intuitive (making the source of the logarithmic improvement easy to explain) and simple to analyze the mutual information. \n\n**Specific response**\n\nClarification on prior work (see original review)\n\n- Thanks for bringing the references to our attention. We will include a more detailed discussion in the revised version. In short, all the referenced papers provide looser bounds than ours or non-applicable bounds on success probability in the setup we consider. More specifically:\n\n  - Theorem 2 by Carpentier and Locatelli, and Theorem 8 by Atsidakou et al. provide upper bounds on the success probability. They are looser than ours because in our regime, where T \\leq C n/\\Delta^2, their bounds are at a constant level. A constant level upper bound is vacuous for our regime.\n\n  - Theorem 4.1 by Karnin et al. provides lower bounds on the success probability.  It is also looser than ours because in our regime. Their bound is negative in our regime and hence vacuous.\n\n  - Atsidakou et al. consider the Gaussian case, and the bounds obtained depend on their prior form and are thus not applicable. Meanwhile, Theorems 1 and 2 by Atsidakou et al. provide lower bounds on the success probability, but do not recover the tight linear growth rate compared to ours.  \t\n\nAssuming knowledge of Delta is usually considered a very limiting practice. It allows to create a priori confidence intervals and test the arms against them.\n\n- As in our general response, our focus is a case study about how the information gain (and success probability) could have surprising behaviors in adaptive settings, rather than propose an algorithm for this toy case. We choose to use our random walk algorithm that is intuitive (making the source of the logarithmic improvement easy to explain) and simple to analyze the mutual information. \n\n[1] Rajaraman, N., Han, Y., Jiao, J., & Ramchandran, K. (2024). Statistical complexity and optimal algorithms for nonlinear ridge bandits. The Annals of Statistics, 52(6), 2557-2582.\n\n[2] Chen, F., Foster, D. J., Han, Y., Qian, J., Rakhlin, A., & Xu, Y. (2024). Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability. Advances in Neural Information Processing Systems, 37, 75585-75641.\n\n[3] Even-Dar, E., Mannor, S., & Mansour, Y. (2002, June). PAC bounds for multi-armed bandit and Markov decision processes. In International Conference on Computational Learning Theory (pp. 255-270). Berlin, Heidelberg: Springer Berlin Heidelberg.\n\n[4] Garivier, A., Ménard, P., & Stoltz, G. (2019). Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2), 377-399."}, {"review_id": "xWUFGmCCQ5", "reviewer": "Reviewer_VwpF", "summary": "The paper's starting point is an interesting observation on multi-armed bandits.\nAssume that we have $n$ arms with Bernoulli rewards,\nwhere the optimal arm has parameter $(1+\\Delta)/2$ and all other arms\nhave parameters $(1-\\Delta)/2$. It is known that the sample complexity of\nfinding the best arm in the multi-armed bandit problem is (ignoring constant factors\nhere and throughout)\n$n/\\Delta^2$. However, if we were to consider a non-interactive setting (i.e., we take a bunch of samples\nfrom all arms at the beginning without adaptively choosing which arm to sample) then\nthe problem requires $n\\log(n)/\\Delta^2$ samples. \nTherefore, clearly adaptivity helps. \n\nThe question the authors study is how this \"help\" accumulates in time.\nSpecifically, they look at two key quantities, the mutual information of the best arm\nwith the history at time $t$ as well as the probability of being able to pick the best arm at time $t$.\nThey track how these quantities grow as $t$ increases, obtaining a sharp\ncharacterization up to constant factors.\nThey identify different growth regimes in both cases;\nIn the case of maximizing probability of identifying the best arm,\nthe probability is $1/n$ initially (basically random choice)\nthen linearly increases until it reaches $\\Theta(1)$.\nIn the case of mutual information, the growth consists of 4 phases:\nan initial linear growth regime, a quadratic regime, a second linear growth regime and a final\n\"saturation\" regime where the information reaches $\\log(n)$ which is the maximum value possible\nas it corresponds to the Shannon entropy of the best arm.", "questions": "Questions:\n- The current bounds seem to assume that the algorithm \"plans\" for time $t$ from the beginning.\n  Do you know how (and if) the results would change if we have a single\n  algorithm attempting to give a good answer for all $t$?\n  In particular, can an algorithm always obtain the bounds you get\n  for all $t$ at the same time?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- I really like the problem statement as it is very simple\n  and intellectually interesting. The results\n  are also interesting and paint an interesting picture which was not known before.\n\nWeaknesses:\n- While I like the problem, I think it can feel a bit too \"toy\" for broader interest in the community.\n  In particular, the work does not really consider a generic bandit instance\n  and while it paints a very detailed picture, the picture is for a single bandit\n  instance.", "was_revised": true, "final_justification": "I have read the author's response. While I see their point about studying simple settings, I had already taken the positive aspects of the clean result in my evaluation. I still have the concern about the narrowness of the current setting and as such keep my score.", "rebuttal": "We sincerely thank you for your thoughtful feedback and valuable suggestions.\n\n**General response**\n\nWe thank the reviewers for suggesting more topics of practical motivation and broader relevance. We will include more discussions accordingly. Indeed, our paper is not really about new algorithms but more a conceptual study about how the information gain (and success probability) behaves in adaptive settings in comparison to non-adaptive ones. The scenario we choose is a natural choice for studying mutual information in adaptive settings with general implications, for the following reasons: \n\n- Upper bounding mutual information is difficult for general adaptive settings and inspires recent works on ridge bandits [1] or linear bandits [2]; \n\n- Mutual information is conjectured to be key for understanding sample complexity [2], in addition to recent DEC progresses, which rely on two-point lower bounds; and\n\n- The specific multi-armed bandit case we use is standard for lower bound constructions, reflecting core challenges of the problem. In particular, here the simplicity of this setting is a strength, for it reveals a surprising phenomenon and underscores the need for new analytical tools even in this well-understood baseline scenario. \n\nWe make the following contributions by studying this special case: \n\n- We propose simple yet powerful tools to upper bound success probability and mutual information in multi-armed bandits, a canonical problem with a different structure from [1, 2], rendering their techniques inapplicable; \nWe reveal a decoupling between mutual information and optimal sample complexity, providing a surprising limitation of the general program in [2]. \n\n- We would also like to note that the algorithm is not really our focus: an algorithm which randomly samples $\\lceil t\\Delta^2 \\rceil$ arms and runs a bandit algorithm with optimal regret on them (such as the median elimination algorithm in [3]) would achieve the same success probability. Instead, we use an algorithm that is intuitive (making the source of the logarithmic improvement easy to explain) and simple to analyze the mutual information. \n\n**Specific response**\n\nWhile I like the problem, I think it can feel a bit too \"toy\" for broader interest in the community. In particular, the work does not really consider a generic bandit instance and while it paints a very detailed picture, the picture is for a single bandit instance.\n\n- Please refer to our general response. We view the simplicity of this setting as a strength rather than a weakness, for it reveals a surprising phenomenon and underscores the need for new analytical tools even in this well-understood baseline scenario. \n\n\nThe current bounds seem to assume that the algorithm \"plans\" for time t from the beginning. Do you know how (and if) the results would change if we have a single algorithm attempting to give a good answer for all t? In particular, can an algorithm always obtain the bounds you get for all t at the same time?\n\n- Our Algorithm 1 achieves the optimal success probability and mutual information for all $t$ at the same time. If $t$ is not known in advance, we can remove the stopping criterion in Algorithm 1, Line 8, and output $i$ as the current guess for the optimal arm at every step.\n\n[1] Rajaraman, N., Han, Y., Jiao, J., & Ramchandran, K. (2024). Statistical complexity and optimal algorithms for nonlinear ridge bandits. The Annals of Statistics, 52(6), 2557-2582.\n\n[2] Chen, F., Foster, D. J., Han, Y., Qian, J., Rakhlin, A., & Xu, Y. (2024). Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability. Advances in Neural Information Processing Systems, 37, 75585-75641.\n\n[3] Even-Dar, E., Mannor, S., & Mansour, Y. (2002, June). PAC bounds for multi-armed bandit and Markov decision processes. In International Conference on Computational Learning Theory (pp. 255-270). Berlin, Heidelberg: Springer Berlin Heidelberg.\n\n[4] Garivier, A., Ménard, P., & Stoltz, G. (2019). Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2), 377-399."}, {"review_id": "oOXPKkXL7G", "reviewer": "Reviewer_TiQo", "summary": "In the context of best arm identification with bandit feedback, the paper establishes bounds on the probability to identify the best arm, and the mutual information between the index of the best arm and the sequence of actions and rewards. The bounds remains tights in the small budget regims ($t \\leqslant \\frac{1}{\\Delta^2}$, $t \\leqslant \\frac{\\log n}{\\Delta^2}$, and $t \\leqslant \\frac{n}{\\Delta^2}$).", "questions": "Current achievability analysis is based on a specific form of the reward distributions and on the knowledge of the gap $\\Delta$. Can we expect an algorithm which would require less assumptions?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "* S1: The analysis showcases the challenges of the small budget regims.\n* S2: The paper includes thorough discussions on the interpretation of these results\n* S3: The paper includes thorough comparisons of these results to state of the art in several related fields of research.\n\n* W1: The algorithm used to showcase the achievability of the bound  requires a the rewards to follow Bernoulli distributions of means close to 0.5, with a known gap $\\Delta$, which questions the generality of the bound.\n* (small/related) W2: In its current form, this algorithm does not offer to choose its error probability. \n* (small/related) W3: In its current form, the error probability in the achievability bound takes the form $C.\\frac{t\\Delta^2}{n}$ where $C$ is a universal constant.\n\n### Remarks\n* It's hard to get a proper intuition of $m$ as an \"effective number of arms pulleds by the algorithm\" at Line 107. The problem arises from the fact that there is no indication on the form of the algorithm before, and the algorithm is somehow surprising.\n* typo at L107: it should be $m=\\lceil t\\Delta^2\\rceil$\n* L132: is it binary entropy or natural entropy (given that you use $1 = \\log e$ to get Equation (6))\n* Algorithm 2 is displayed in the core of the paper but neither cited nore discussed. I think the paragraph introducing Section C.1 would be more informative here.", "was_revised": true, "final_justification": "The reviews and discussions did clarify the role played by Algorithms 1 and 2, and therefore the position of the paper.  \nAlso, the authors did express their willingness to update the paper in line with these discussions.\n\nOverall, it pushes me to raise the score of the paper. But up to some limit, because, like other reviewers, I would appreciate to feel a more general applicability of the presented results: other bandit instances, improvement of bandit algorithms, ...", "rebuttal": "We sincerely thank you for your thoughtful feedback and valuable suggestions.\n\n**General response**\n\nWe thank the reviewers for suggesting more topics of practical motivation and broader relevance. We will include more discussions accordingly. Indeed, our paper is not really about new algorithms but more a conceptual study about how the information gain (and success probability) behaves in adaptive settings in comparison to non-adaptive ones. The scenario we choose is a natural choice for studying mutual information in adaptive settings with general implications, for the following reasons: \n\n- Upper bounding mutual information is difficult for general adaptive settings and inspires recent works on ridge bandits [1] or linear bandits [2]; \n\n- Mutual information is conjectured to be key for understanding sample complexity [2], in addition to recent DEC progresses, which rely on two-point lower bounds; and\n\n- The specific multi-armed bandit case we use is standard for lower bound constructions, reflecting core challenges of the problem. In particular, here the simplicity of this setting is a strength, for it reveals a surprising phenomenon and underscores the need for new analytical tools even in this well-understood baseline scenario. \n\nWe make the following contributions by studying this special case: \n\n- We propose simple yet powerful tools to upper bound success probability and mutual information in multi-armed bandits, a canonical problem with a different structure from [1, 2], rendering their techniques inapplicable; \nWe reveal a decoupling between mutual information and optimal sample complexity, providing a surprising limitation of the general program in [2]. \n\n- We would also like to note that the algorithm is not really our focus: an algorithm which randomly samples $\\lceil t\\Delta^2 \\rceil$ arms and runs a bandit algorithm with optimal regret on them (such as the median elimination algorithm in [3]) would achieve the same success probability. Instead, we use an algorithm that is intuitive (making the source of the logarithmic improvement easy to explain) and simple to analyze the mutual information. \n\n**Specific response**\n\nThe algorithm used to showcase the achievability of the bound requires the rewards to follow Bernoulli distributions of means close to 0.5, with a known gap $\\Delta$ which questions the generality of the bound.\n\n- Please refer to our general response. Our paper is not really about new algorithms but more a conceptual study about how the information gain (and success probability) behaves in adaptive settings in comparison to non-adaptive ones. \n\nIn its current form, this algorithm does not offer to choose its error probability.\n\n- Our converse results show that ANY algorithm (including those that can choose its error probability) cannot achieve a success probability better than our bound. Our achievability results use an algorithm which does not need to choose its error probability. \n\nIn its current form, the error probability in the achievability bound takes the form has a universal constant.\n\n- Rate-optimal results (i.e. optimal within universal constants) are standard practice in the bandit literature. For example, most regret guarantees involve universal constants, and best arm identification with a fixed confidence will also involve a universal constant in the sample complexity bound.\n\nCurrent achievability analysis is based on a specific form of the reward distributions and on the knowledge of the gap Delta. Can we expect an algorithm which would require less assumptions?\n\n- As in our general response, our focus is a case study about how the information gain (and success probability) could have surprising behaviors in adaptive settings, rather than propose an algorithm for this toy case. We choose to use our random walk algorithm that is intuitive (making the source of the logarithmic improvement easy to explain) and simple to analyze the mutual information.\n\n[1] Rajaraman, N., Han, Y., Jiao, J., & Ramchandran, K. (2024). Statistical complexity and optimal algorithms for nonlinear ridge bandits. The Annals of Statistics, 52(6), 2557-2582.\n\n[2] Chen, F., Foster, D. J., Han, Y., Qian, J., Rakhlin, A., & Xu, Y. (2024). Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability. Advances in Neural Information Processing Systems, 37, 75585-75641.\n\n[3] Even-Dar, E., Mannor, S., & Mansour, Y. (2002, June). PAC bounds for multi-armed bandit and Markov decision processes. In International Conference on Computational Learning Theory (pp. 255-270). Berlin, Heidelberg: Springer Berlin Heidelberg.\n\n[4] Garivier, A., Ménard, P., & Stoltz, G. (2019). Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2), 377-399."}]

Author rebuttal:

Meta-review: This paper studies an interesting problem of characterizing the benefits of interactive versus non-interactive decision-making in the context of stochastic bandits. The authors clearly motivate the problem at the beginning using a toy example, and the theoretical results presented are both solid and significant. The reviewers and AC appreciated the contributions of this work. The paper also opens the door for additional research in this direction and is clearly above the acceptance threshold.
Decision: Accept (poster)