Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms
Authors: William Réveillard
Richard Combes
Venue: NeurIPS 2025 poster ()
Keywords: Multi-armed bandits
Structured bandits
Non-convex optimization
Primary area: theory
TL;DR: We develop a computationally tractable algorithm to solve the Graves-Lai problem for multimodal bandits.

Abstract: We consider a stochastic multi-armed bandit problem with i.i.d. rewards where the expected reward function is multimodal with at most $m$ modes. We propose the first known computationally tractable algorithm for computing the solution to the Graves-Lai optimization problem, which in turn enables the implementation of asymptotically optimal algorithms for this bandit problem.

Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms
William Réveillard
Richard Combes
Division of Decision and Control Systems
Laboratoire des signaux et systèmes
KTH Royal Institute of Technology 11428 Stockholm, Sweden wilrevêkth
Université Paris- Saclay, CNRS, CentraleSupélec
91190 Gif-sur- Yvette, France fr
x wtc.harrd.cmmmeeeecnteeeee
Abstract
We consider stochastic multi-armed bandit problem with i.idd. rewards where the expected reward function is multimodal with at most m modes. We propose the first known computationally tractable algorithm for computing the solution the Graves-Lai optimization problem, which turn enables the implementation asymptotically optimal algorithms for this bandit problem.
Introduction
We consider a stochastic multi-armed bandit with K 2 arms. At time t E TT), with T 2 1, based on her previous observations, a learner selects an arm k(t) in [K] (I......K] and subsequently observes random reward Xa(a).. The successive rewards (Xk,1)een obtained when sampling given arm E [ are drawn i.i.d. from a family of distributions VA (fx) parameterized by their expectation μąg The vector of mean rewards μ (ux){e[K] unknown to the learner. The Iearner's
goal is to select arms in order to discover the optimal arm k*t (HL) arg ma M4. More precisely, the learner aims at minimizing the regret
R(p, T) (mmxx (1))
kE K]
EE(T]
which is the expected difference between the total reward obtained by an oracle who knows in advance and always chooses the arm with the largest mean reward, and the total reward obtained by the learner. If we were to assume that is arbitrary, then the problem at hand would reduce to the classical stochastic multi-armin bandit. Here we consider a structured stochastic multi-armed bandit, where the structure is encoded by a graph G.
We consider graph G (V. F.) whose vertices the arms V = are neighbors if and only if (k: E) E E. Arm is mode of 4a with respect to G and only if it has a strictly greater reward than all of its neighbors: Pk maxe:(k.f)e Me and say that μ m-modal with respect to G if it has m modes with respect to G.
[K]. and say that arms & and é
In this work, assume that is at most m-modal with respect to graph G known to the learner. We emphasize that, while G is known to the learner, fu is not, so that finding the optimal arm requires sampling from suboptimal arms repeatedly. We note that for unimodal vector, thus the problem reduces to unimodal bandits [8] If G is line graph, a mode an arm whose reward is greater than that of its left and right neighbors. We will assume that G is tree.
1. a 1-modal vector is simply
With slight abuse of notation, also refer µ the reward function of the bandit problem.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

2 Related work and contribution
In the absence of a multimodal structure, our problem reduces to the classical multi-armed bandit studied by [3). and several asymptotically optimal algorithms are known for this problem, such as KL-UCB, proposed by [6. DMED, proposed by 2 and Thompson Sampling, as analyzed by [TO].
When adding multimodal structure with m 1 mode. obtain the unimodal bandit problem, originally studied by [8] and revisited by [25]. Several asymptotically optimal algorithms have been proposed for this problem including the KL-UCBB style algorithm of 22, the Thompson Sampling style algorithm of [21 and the DMED style algorithm of [1]] A common feature of these algorithms is that they are all based local search, where only arms that are neighbors of the optimal arm are selected logarithmic amount of time. Local search is necessary for asymptotic optimality in unimodal bandits because the strategy that minimizes the Graves-Lai bound, as introduced by 77. is local.
Multimodal bandits with 2 1 modes generalize unimodal bandits, and have been considered in [17 and [18]. These works explored local search strategies, which, as we shall see, are not necessarily asymptotically optimal. The main motivation behind multimodal bandits is the fact that many objective functions encountered in applications are not convex nor unimodal, such as the empirical risk of deep neural networks. Methods for optimizing or sampling (which are closely related) multimodal functions include bayesian methods studied by B and MCMC methods considered by [4.. Multimodal functions have also been considered in active learning setting by [16). An
interesting application of bandit problems with multimodal rewards is pricing (115 241).
For structured bandits, the Graves-Lai bound is an information-theorede regret lower bound, stated as an optimization problem. Its optimal solution identifies strategies for optimal exploration, i.e., the rate which suboptimal arms must be selected ensure minimal regret. Several asymptotically optimal algorithms with regret matching the Graves- Lai bound have been proposed by 77]. [. [5], 222. The main advantage of these algorithms is their universality in the sense that they apply to all structured bandits.
While the above algorithms are indeed universally asymptotically optimal, they often pose tremen- dous computational challenge, because they must solve the Graves-Lai optimization problem. In some simple structures, the Graves-Lai optimization problem admits closed-form solution, for instance: classical bandits (I3), unimodal bandits ((2) dueling bandits (IIT) to name a few. For some other structures such combinatorial bandits ([4)), the Graves-Lai optimization problem can be solved with efficient iterative algorithms. For multimodal bandits, solving the Graves- Lai optimization problem is challenging, as we shall see, primarily due to the highly non-convex nature of its constraint set.
Our contribution. In this work, we provide the first known computationally tractable algorithm to solve the Graves-Lai optimization problem for multimodal bandits. The algorithm is involved and uses combination of discretization, dynamic programming and projected subgradient descent in order to navigate the intricate structure the constraint set. The algorithm applies to a wide variety of reward distributions, and any tree graph. We further demonstrate that local search strategies are suboptimal, which means that solving the Graves-Lai problem unavoidable for optimality. The code for the proposed algorithms, which are involved, is publicly available at ltttt::///////. //tp:://///thb com/ www.ww/wwwww.. Mult imwdatimmmall 1Baddits
3 Asymptotically optimal algorithms for multimodal bandits
In this section, we state our problem assumptions, present the Graves-Lai lower bound specialized to the case of multimodal bandits, and recall how solving the Graves-Lai optimization problem enables one design asymptotically optimal algorithms, i.e., with regret matching the Graves-Lai lower bound.
To ease exposition, we use the following notation. All vectors are represented with bold symbols. We denote by ((k) E R the k-th canonical basis vector of R and by ||œ|||p = (Eke(K) (c//))/P the Lp norm. The closure of a set S C R is denoted by S. We denote μr" maxte[K] Me and p. minne(K] μ4 the maximum and minimum mean reward, respectively. We
Notation.

---

assume that the optimal arm k* (p())= = arg [K]] H4 is unique, We define the vector of gaps A = -1² [e] and the minimal gap Amin = m Ak.
For a given tree G = (V. E) with V [K], we denote by diam(G) its diameter and deg(G) its maximal degree. MM(μ) is the set of modes of with respect to G, so that μ is m-modal if [M(μ)]] = m, and (())) is the set of modes and neighbors of modes of J.. We define F&m (resp. Fm) the set of reward functioon of TR K with at most m modes (resp. exactly m modes) with respect to G. We assume that f. Fggm for some m. > 1, and that m is known to the learner.
Finally, we sometimes consider the tree G to be directed. Then, for a given arm k E [K]. we denote by C(k) the set of children of k, (kk) the set of descendants of k, pkk) the parent of k and p² (l) the grandparent of & (i.e., the parent of p(k)).
The rewards from arm & E [K] form an i... sample from distribution vk (. Let dy (Ms, Ax) (rx (ux) (xx))) denote the relative entropy between the rewards distributions of arm & under parameters μi and Ag. For μt, À IR we use the vectorized notation d(ps, X) = (d& (JuR, >x )EEK) We make two assumptions regarding these relative entropies.
Assumptions on reward distributions.
Assumption 1. For all fs. E TR and & E [K], X ++ du (14 Ax) is strictly decreasing for dE. < Pk and strictly increasing for Ak >> jAk-
Assumption 2. For all & [K] Ja. E TRK and X, X' in (e), we have [d[su, A) d(p, X)IlI S
Mpp)] - X111 where (1( 2 0 can be understood as the Lipschitz constant of the relative entropy
when its first argument is held constant.
The first assumption boils down to the relative entropy de being unimodal, and its unique mode being the minimizer X jug- The second assumption is satisfied whenever the divergence is continuously diffcrentiable over [u., ,=|*A, For example, when 1/ (px)) = (O, 1), it holds with ((r) = 1u' pe..
Regret lower bound. Proposition states that the asymptotic regret of any uniformly good algo- rithm (i.e., whose regret scales subpolynomially on all problem instances) must be lower bounded by the value of the Graves-Lai optimization problem multiplied by Tn We denote this optimization problem by P&L)
Proposition 1. Consider an algorithm such that lim
R(H,T) = ffrrr all a > and all μ E Fsm T
Then its asymptotic regret is lower bounded as lim infT where (mr. po) is the value of:
R(
2 C(m, for all μ Fmm I
minimize,, T7 A subject to
inf XE
dTd(u, A) > and n 2 0
(PGL)
with B(m, 11) = F Ax-(W) 1r" k (A) + k- (n)).
PGt. is a semi-infinite linear program. There are infinitely many constraints, and these constraints are described by B(m, which is the set of confusing parameters. X B(m, (1) is confusing to the learner because cannot be distinguished from f by selecting the optimal arm k. (p1), thereby forcing the learner to explore suboptimal arms. In particular, for a fixed n 2 we call most confusing parameter the minimizer X of À 1 n7 d(ju, A) over B(m, (1). The set B(m, (1) has a complicated structure, which is why solving Pot is non non-trivial. Proposition T is a direct consequence of the general bound of Theorem in 7 or alternatively the simpler lower bound of Theorem 1 in
Asymptotically optimal algorithms. We recall that, PeL can be solved, then there exists a wide
variety of algorithms that are asymptotically optimal, such as those presented by 77 M1 5 and (2]. All these algorithms attempt to select arm k * k ((z) a number of times 7 In T + when T + co, where 17* is solution to Poz. The only requirement is that one is able to solve Par. several times in order to decide which arm to explore.
Theorem 1 (Theorem 2 in (I) Consider Gaussian rewards with variance one and assume that for any μ E Fsmm a solution to the Graves-Lai problem can be computed. Then, the OSSE algorithm
R(,,T)
with parameters E = 7 = 0 is such that for all μ E Frms lim sup
S C(m,p)).
T-400
InT
For completeness, the pseudo-code of OSS3 provided in Appendix solve Paz for multimodal bandit problems.
A.I
We now focus on how to
3

---

4 A computationally tractable algorithm to solve the Graves-Lai problem
In this section, we propose an algorithm to solve the Graves-Lai optimization problem a computa- tionally tractable manner, which constitutes our main contribution. The algorithm is rather intricate, and we go through its derivation step by step. The complete approach is summarized in Figure For clarity, detailed proof' are provided in Appendix
(A) Penalized subgradient descent
(B) Decompusition into subproblems
(C) Dynamic programining solver
Gosl: compone Ale) angriiisatioal niA d)..A)
Coal: comper A a plmaa Mi3] dlu.
Curcai samplin rass
Decomppae into subprob- over all pais
lenac
Compute mos confising perameter Alo)
Forward pass Compus cools fel from lcases
For each sebpectiem. dixcetine (ss. M)
Updas nace sia suburaliou step qle + 1) = (lboe) - (okgofel-1))
Backwardd pass Recorsima: X(RA1) from moil kervos
Salve esch discretized sabpeohicm
Seleet Alxs) as the selu- Sen loscit overall cost
Figure 1: Summary of the procedure to solve Pol.
4.1 Reducing the constraint of Pat to tractable subproblems
On the difficulty of computing the constraint. In the unimodal case where m = 1, solving PoL can be done in closed form, however for m > 1 this is much less straightforward. The main difficulty to compute the value of the constraint inf x (mm,p) 17' d(p,, A). While À ++ 77 d(ju, A) is usually a convex function, minimizing it over B(m, 11) is difficult, due to the particular structure of the set B(m, (1). Indeed, B(m, (u) is not convex, nor is it connected. In Proposition 2 we show that, if one wanted to express [m,, (1) as union of (K, m) convex sets (so that we could minimize d(p, A) over each set using convex programming). then one would require U(K, m) be exponentially large in K. For example, if G is line graph with K = 100 nodes, and we consider multimodal functions with m modes, then the number of convex components Ut K, m) must be greater than 10'.
Proposition Assume that B(m, (u) can be written as union of U(K, m) convex sets. Then for any m > 1, we have:
U(K 2 ((deg(G) - 1)m) (ddeg(G)m)) (K (deg(G) + 1)m)"
hence m) grows exponentially with m.
In contrast to the unimodal case (m 1), where the most confusing parameter X is obtained by perturbing single neighbor of the optimal arm k- (() (as shown by (2)), the multimodal setting (m > 1) introduces more complex possibilities. While one might expect the most confusing parameter to be such that A 4* for a single & E N(μ) \ 1e* (H), and equal μ elsewhere, this intuition fails in general. Depending on the value of n, it may be more confusing to set d u² for k & (H), and to ensure that X E Fsm. set Ag = de for some E M(H) \ 1e (1) and such that (K', E) E E. Figure 2 provides concrete illustration of
A"
Am Expeciation
Index
Figure 2: 2-modal example.

---

this phenomenon on line graph, with A = arg min miggminneeaa. (2 77 n d(d(,, A) for = (1,,,4,2,3). "7 (0.01, 0.25, 1, 0.255, 1), and Gaussian rewards with variance one.
Restricting the constraint and solution spaces. We first show some elementary properties of the so- lution, which will allow to restrict both the spaces where 1, and À lie. First, we decompose the con- straint set as m,,, 11) = Ukptk (n) BE B5&(n (m, (4) with (m, (1) = {> E Fgmm ( = =,²,, k (A) k}. Clearly, minimizing
d(p, A) over X E Bim. (4) amounts to minimizing 7 ddd(H,, X) over E (m p) for each + k- (J)). Proposition 3 states that this minimization problem is straight- forward when l has strictly less than modes or when k is in the neighborhood of the modes of
Proposition 3. Let m 2 0 and + (p)... 1f E N(p)) or [M(p)] < m,
inf (m)
n T d'd(p. 2) = (ux,
which is attained for X μ (e* u1x (k)) (B( pt).
We now focus on the case |M(H))] = m and &o & (p)).. Proposition 4 shows that the constraint
B& (m, p)) is equivalent to a constraint on compact set whose elements have entries comprised between the minimum and maximum of μr, and that have the same value μ³ at k and k" (pt).
Proposition& 4. Let v 2 0, k & ((1)) and B% (m, 11) = {A E ju,, NFF dE = )x) = p²)
Then
inf T d(p,,)== (m..)
min XEB (m).44)
n d(d,,,
Proposition shows that, in order to compute a solution to PGL we can restrict our attention to a compact region, and that the entries of n cannot be larger than 2 (z). In turn, B(μ)) may be interpreted as the regret predicted by the Lai-Robbins bound in absence of a multimodal structure, divided by the minimal gap.
Proposition 5. There is a solution ny" of PGL such that "y [0, B(n)] where B(u)
Amin Exida )
Location of modes in subproblems. We have shown the previous section that the computation of the constraint of PaL can be reduced to solving the following subproblem for all n and for each t E [K] ((():
minimizex n7 Td( A) subject to A E (m,, p4).
(PGL(k))
We now present the most important structural result about the solution to Por. (k) which pertains to the location of its modes. Proposition states that the modes of the solution to Par. all lie in the set of modes of μu, apart from kt which must course be a mode since it is maximizer. This is in fact the reason why one is able to compute the solution to (k)(k) While this will be made clearer by exhibiting an efficient algorithm to compute the solution, is understood searching over X is much easier when the location of its modes is known.
Proposition 6. Consider X the solution to PGI.(k) Then M(x* C M(U) U (k).
If [M(H]] = m, we have (M(() U [k}] m + 1, which implies that there must exist a mode of μ that is not mode of X", and all of the modes of x apart from k are modes of μ.. Additionally, can assume that &' * ((1).. Indeed, if k* (H)). the constraint )g- = ut" would yield A 2 μt*
for some neighbor É of k* (u). This cannot improve upon the solution given by Proposition 3 This means that we can restrict our attention to the sets BE (m, μ)) for k MM()) (K" (4)} with
(m, p)) {} [,,, M((A) C CM2)) (1) \ [K'), Am-(0) A = μ²}
which is the set of vectors whose modes lie in M(U) U {k} \ [A'} and attain their maximum at k (14) and kt and that have the same value a K- (1z). We must solve the subproblems, for l E [K] (V()), W' E M(μ)) {K* (H)):
minimizex 17 d(p, A) subject to X E (m, 1d).
(PoL(k,k))
5

---

Diseretizing the subproblems. The last step before we can solve PaL (k) j' is to discretize the space in which À lies, which will allow us design a discrete search procedure over X. Proposition 7 states that discretizing each entry of X E BR, (m, 14) with grid of n points (n,, p4), incurs a small approximation error that can be controlled, and vanishes at a rate inversely proportional to n. is noted that this result is non trivial in the sense that there exists sets of large volume whose intersection with some grid can be empty, and holds because of the particular structure of BK (m, μt). In essence, we can round À to ensure both small rounding ertor while leaving the set of modes of À unchanged.
Proposition 7. Consider Dnn, p1) the following uniform discretization of [p,, (²"] with n discretiza- tion points:
D(n, po) = {u. + (i/n)(u²* - -.), E [m]].
Then there exists À E (m, (1) 1 (n,, 10) such that for any 1) E [0, (H)]
nT'd(,, C(HL) S
" d(p, A) S n T d(p X) (m.,))
min
with C(p) = diam(G) - -4.) (.))
4.2 Computing the constraint sets via dynamic programming
We now explain how to efficiently solve the discretized version of Par. (k, k')
namely
minimize> v) d(pt, A) subject to À Ba (m. p)) for BR (m, (1) = Bx,x-(m, 11) n D(n, u²²
(Poz (ks k"))
K. We use dynamic programming procedure which necessitates viewing G' as directed tree G obtained by performing depth-first search the undirected tree G starting at node (which is consequently the root of G*). We recall the notations C(E), D(E), p(E) and (e) to denote the children, descendants, parent and grandparent of node é in Gk The high-level idea of the procedure is to compute the value of Par. (k; k') recursively with a formula that relates the minimal obtainable value of LjeD(Eju()) [jdj(1j (Mjj) >3) to that of EjED(e) njdz (My Aÿ) for any node f. Note that when & = k, the former is equal to the value of (k k') and when l' is leaf of G* the latter is equal to O. This recursion formula heavily relies on the fact that all modes of the solution to Par. k') are in M(μμ) U {k} \ (K).
We now introduce some important quantities for our dynamic programming approach. For node l * k in Gk we define fe(z, u) as the minimal obtainable value of
(djر( JED(OU(()
Σ
subject to the constraints E BR, (m, p), d and d > >p(e) if u (resp. de Apre) и -1). To simplify the notations further, we introduce the following auxiliary function [1 +1) = min a=>2
fe(w, +1), [E = min Je(w,-1) [²(=) = min (2, -E(-1,+1)
ws=
which represent the minimal obtainable value of EyEp(enuer 7n (M;)( for X E B (m, pi) when d > Xp(e) = 2, d I Ap(e) = = and Ap(e) = z, respectively. Finally, to ensure that the constraint ) = n² is satisfied during the dynamic programming procedure, we set (m) = +00, and we use the convention that (k-(w) otherwise.
2) equals 0 if = n² and too
The functions fe(z, u) for E [K], 2 E D(n, u) and u E {11, +1} obey the following recursion:
Proposition 8.
e M(H) (K): fe(z. medelue 2) + (z),,, and and & M(H) U (k) \ (W):
nedelHe, 2) + E Ejec(e) f2)
if = -1 if = 1,)(())))))))))))))))) + +u=+1,c(()=
fe(z,u)=
nedelue, 2) E Ejec(e) f2(2) + min (z)
t00
"The minima are taken with the implicit constraint w E D(n, 11)
Recall that the value of (x) has impact on the solution to (k,k')

---

where (2) (2, (o(2,-1)) 1)} - (2), and the value of PaL (k, k2) equals f& (u u) for any E {-1.+1}.
Since the discretized search space ((n, 14) is finite, we can straightforwardly compute the values of fe(z, u). fł (z, u) and f? (z) for each 8 E [K] [(n, (4) and {-1, +1} with the dynamic programming equations of Proposition 8 The solution X of (k, k') can then be obtained recursively as Corollary 1 in which the condition & = arg minpve((((e) 90 (o(A ((e)) can be understood as é being the children of P(() that induces the smallest cost when constrained by the value of p(().
Corollary 1. The solution X of Por. k²) is such that X - 1²* and for l + k: 1f((() & M(2) U {k} [K'). Ao()) > Xip(e) and E = arg min)ee((p(e) 9u () )p())
arg min x20) fe(2,+1) Xo(e)
p(e)) -1) if f/ (x (xcey, fe(1p(1) 1).
if (x -1) - fe(2 p()))
x2
arg minl
Se(2,+)
if [2 (Xpee +1) S l/ (Dpce -1)
and otherwise X2 =
(io)
arg min p(o)
fe(z,
if (2 p00) +1) > f2 (2 -1).
Furthermore, computing the solution to Pal (k. k') lary 7 can be done in time and memory O(nK).
using the procedure of Proposition 8 and Corol-
Overall time complexity. This procedure allows us to solve the subproblems Par k') for all k & (1) and k' E M(()) (k= (m)]. By comparing these solutions with the trivial parameters from Proposition 3 can find the most confusing parameter in (mm, p4) D(n, vz) for any sampling rate in time O 0(Kmmn). In practice, these subproblems are independent and can be solved in parallel. In Appendix E, we describe a more involved dynamic program that runs in time (KK)
without requiring parallelism.
Illustration of the dynamic programming approach. We now illustrate the computation of the most confusing parameter in B(m, (1) n D(n, 4)* with the line graph example of Figure 2 There, the divergence is d& (Ax, = 1 {Ax - px R the optimal arm k* (u) 3, the modes are M(U) (3. 5). and their neighborhood ((u) (2, 3, 4, If k = k (A) is chosen in N ((4),
applying Proposition yields
inf TT d(u A) XE A
Otherwise, we must have l: 1, and the only choice for the mode of μa to be removed is K' 5.
We can then solve Paz k') for (k, (1, by applying Proposition as follows. We first form the directed tree G as line graph, rooted at 1, with leaf node 5. For each node and each grid value D(n, 11) the program computes and stores in memory the values
fe(z,
fe(z,+1)
together with the auxiliary minima (2, ) and ff(z), as defined in Proposition g obtained directly from the divergence:
The leaf entry is
75 2 (14 - 2)², fs(z, +1) = +00,
fu(2, -1)
and (2, are then computed by minimizing over the grid D(n, μu). For an internal node l. A 5, the recursion in Proposition is applied: each entry fe(z.-) is derived from the already computed child cost values as prescribed in the proposition. Finally, the value of the discretized subproblem (kr,k, A')jis is read off at the root as (u ( where 1 = in the present example. The minimizer is finally recovered by backtracking, as described in Corollary [ In the limit - xi, this minimizer approaches X' (4, 2, 4, 2.8, 2.8). This non-trivial confusing parameter turns out to be the global minimizer of Pat. as its value approaches 0.145 < 0.5.
7

---

4.3 Solving Pcl via penalized subgradient descent
We are now capable of computing a minimizer of 7) d(j.. X) over B(m, p)nD pu) the constraint in the original problem PoL with discretization. The last step to close the loop is to use an iterative procedure to derive an approximate solution to to The simplest way to understand this procedure is to view it as projected subgradient descent for the convex function
h: 7- A +.ymax
1
min (.B((m.p)DDDa.... In'd(u, ((),
which can be interpreted the objective PG with discretized constraint space and where the hard constraints have been replaced by a penalty similar to the hinge loss function, and where y controls the magnitude of the penalty. The projection step is used enforce the constraint 2 O. We show in Proposition that the minimizer of h(m) subject to the constraint 2 0 is an approximate solution to Paz
Proposition 9. Consider a step size 8² (w)) T. where t the mumber of iterations, C(p)) =
A and an iterative procedure ||ا| 7K3/2 - (r)), a penalty 7 = max, 20 alpeyey
(11 = O, and for <:::
( 8 + 1) = (m(() 5 ( vd(ps, (1 d(p, X()) <1})]
where X(s) E arg mill XeBlil))emm.. XeB(m.,))D(....... ()),(. (8)) X) and Il [x] = (max(x;, O))kε[ is the projection on the positive orthant. Define n(t) (1/t) Ex nss) the average iterate and scaled for 3(k) = v (KB(())( Then in(t) a feasible
version (t()) = r7(t) (1
{(p) 2 ((m) 7Vi
solution to Pet. with value most:
C(H)
B(4)) wi 7
-1
(Clm.1)) +
3(4)) Vt
C(p) if
3(p) 2 v
7(1) A <
1.
n
n
Putting it all together. We end this section by stating our main result, which a direct consequence of the previous propositions, and propose a computationally tractable algorithm in order compute an approximate solution to Par. With the more intricate dynamic programming scheme presented in Appendix E. its time complexity can be improved O(Kn)).
Theorem 2. Consider the algorithm which outputs rj(t) after iterations of the scheme described Proposition with n discretization points. At each step s S t, X(s) computed by solving PGL k') for all k & (H)) and all k E MMH)) [k*()) using the dynamic programming scheme of Proposition g This algorithu runs in time O ((33mnt) and space O(Krt) and yields (t(t),
feasible solution to toL with value at most:
C(H)
B(u) Ve
if C(p)
3(p)) 7
n(t) A <
2
< 1.
The parameters n and can be chosen by the learner. Since the time complexity grows linearly in nl, and the optimization error is proportional to 1/n + 1/VE, given time budget constraint nt one may choose 2/3 and = 2/3, which yields optimization error proportional to a -1/3
5 Local search strategies and peaked functions
In this section, we consider algorithms that primarily explore arms in (H,,, where we recall that ((H) is the set of all modes of μ and their neighbors. The proofs are deferred Appendix D
Local search. To analyze such algorithms within the Graves-Lai framework, we connect this
behavior to the properties of the corresponding sampling rate vector 77. Let (t) = Et 1{k(s)= =
k) denote the number of times arm & has been selected by up to round The asymptotic sampling
[[N. An algorithm performs local search rate for arm & E [K] is given by 7es lim supr I Th 0 for all lo & (p). This leads directly to the following definition.
8

---

Definition 1. Consider E (R*)) feasible solution to PGL We say that is local search strategy if and only if my. for all & N().. Further define Croe (m, (1) the optimal value of Par. restricted to the set of local search strategies.
The appeal of local search strategies stems from two key properties: they are provably optimal the unimodal case (m = 1), and are conceptually simpler than non-local strategies, which may explore all arms.
Suboptimality of local search strategies. Unfortunately, and rather counterintuitively, not only are local search strategies suboptimal, the performance gap between local and non-local strategies not upper bounded. More precisely. the ratio between the value of the best local strategy and the value of the best strategy can arbitrarily large. Local search strategies are suboptimal because for every mode k * k* (14) and every neighbor & of k, they must be able to check that μa > Me, requiring number of samples proportional to "u(ur,uz which can cause an arbitrarily large amount of regret the function is flat in the neighborhood of k. so that μa is very close to pt.
Theorem 3. Assume that (W() < K. Then the following bounds hold:
A
D de(ukr HC*
(mo pt) 2
E
and Cmm, 11)
Σ kE[K]
de(Hk Uk 5k)
(EM(M))(K*(M))
where 0g = ming,, 1ike mel > O. As a consequence, sup MEP performance ratio between local and non-local strategies is unbounded.
Croa(m.j4) C(m.p))
= t00, i.e., the
In particular, this result implies that the IMED-MB algorithm from [8. which uses local search strategy, cannot be asymptotically optimal, which contradicts the statement of their Theorem 2. This rigorously shown in Appendix D.2
Peaked reward functions. While in general local search strategies can be far from optimal, there exists a smaller subclass of reward functions on which they can be shown to be quasi-optimal, up to constant multiplicative factor. We call these reward functions peaked in the sense that they are not flat around their modes.
Definition A reward function μs E R.K is k-peaked and only if for all k E MM()) and all E neighbor of k we have dy (1t,, jx*) S sdl (dl( (14n, - 5x/2) and de(pe, S rde(pe, li - 6x/2).
In particular, when rewards are Gaussian, the condition above reduces simpler one: for all modes k. the gap between and its neighbors should be at least proportional to the gap between k and the optimal arm, so that indeed, the function cannot be flat around the modes.
Proposition 10. Consider Gaussian rewards with fixed variance. Then μ is k-peaked if and only if for all i E M(U) we have D& S 6 -1).
Proposition 11 shows that for k-peaked reward functions, there exists local search strategies that are a factor K. from optimal.
Proposition 11. Assume that j F... Then the following bounds hold:
Ax da da - 6x/2)
Ae de(ue 6x/2)
C p1) S
Σ
+ Σ Σ
kEM(H) (Ik- (1))
kEMIH) E((K,))
A
C(m,p)
E
1e*)
(EN(M))(K (1a)
and by corollary, if f is k-peaked, there exists local search strategies within a constant factor: Om. S K.
suPpeTm..e peaked (mm,p))
6 Numerical experiments
In this section, we conduct numerical experiments to demonstrate the benefit of properly exploiting the multimodal structure. To this end, we implement OSSB from [ and use approach solve

---

PCL At round t, OSSB samples as dictated by the solution (t) (t) to the Graves-Lai problem for the empirical estimate (i( of μs, which is given by (ix(1) Eis (M())) We compare the cumulative regret of two algorithms:
(.
Multimodal OSSB: the OSSB algorithm where the Graves-Lai problem is solved using our proposed method,
(iI) Classical OSSB: the OSSB algorithm for unstructured bandits, which serves as a baseline.
The pseudo-code of OSSB and further details regarding the experiment are deferred to Appendix A.I
G' is chosen as a fixed binary tree of height two (resulting in K = 7 arms). We consider instances μ F2 with rewards from arm lo [K] drawn from Gaussian distribution N 1). The mean rewards Pa are generated as a sum of exponential functions centered on the modes in M(z):
Σ (1+1)= exp (-pjk/o),
JEM(N)
where Pjk is the shortest path distance between nodes and in G. We choose M(u) (4, 6) and k* (μ²) = 6. The parameter a controls how peaked the reward function is: a small leads to sharp peaks with modes separate from their neighbors, whereas a large creates flatter modes.
We consider two instances: a = 0.5 (easy instance) and σ = 4 (hard instance). We run the experiment up horizon of T = 10, 000. To reduce the computational burden of solving Par. each round, we only update '7" (4) when / = 2 for l: E {0...., log, }-}- The cumulative regret is averaged 500 trials. The results presented in Figure where the shaded regions have radius one standard error. In both settings, multimodal OSSB exhibits superior performance over classical OSSB.
Multimedsl Classicall 555.8
Nutimosal
Claceral DESI
Curnuleiive Regret
Curuisstiv
Am
Time Step
Time Step
(a) 0.5
(b) 4
Figure 3: Cumulative regret as a function of the number of rounds.
Further experiments on the runtime of our dynamic programming approach are deferred to Appendices A.2
and E.8 The code used for the experiments is available at httttt:t//ggtttt com/ wi httm/wwlress /rev/
Mu
moda Bandits
7
Conclusion
We have considered stochastic multi- bandit with i.i.d. rewards and multimodal reward structure, and have proposed the first known computationally tractable algorithm to solve the Graves- Lai optimization problem, which we have shown is a requirement implement asymptotically optimal algorithms, as the performance ratio between local and non-local strategies can be arbitrarily large. We believe that an interesting direction for future work to characterize the minimal computational complexity necessary solve this problem in terms of the number of arms, modes and graph structure.
10

---

References
[1] Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. In Advances in Neural Information Processing Systems, 2017.
[2] Richard Combes and Alexandre Proutiere. Unimodal bandits: Regret lower bounds and optimal algorithms. Proceedings of the 31 International Conference on Machine Learning, 2014.
[3] Emile Contal. Statistical learning approaches for global optimization. PhD thesis, Université Paris Saclay (COmUE). 2016.
[4] Thibault Cuvelier, Richard Combes, and Eric Gourdin. Asymptotically optimal strategies for combinatorial semi-bandits in polynomial time. In ALT, 2021.
[5] Remy Degenne, Han Shao, and Wouter M. Koolen. Adaptive algorithms for stochastic bandits. In Proceedings of ICML, 2020.
[6] Aurelien Garivier and Olivier Cappe. The KL-UUBB algorithm for bounded stochastic bandits and beyond. In Proceedings of COLT, 2011.
[7] Todd L. Graves and Tze Leung Lai. Asymptotically efficient adaptive choice of control laws in controlled markov chains. SIAM Journal on Control and Optimization, 35(3):715 1997.
[8] Ulrich Herkenrath. The n-armed bandit with unimodal structure. Metrika, 30(1):195 190- 1983.
[9] Junya Honda and Akimichi Takemura. An asymptotically optimal bandit algorithm for bounded support models. Proceedings of COLT, 2010.
[10] Emilic Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In Proceedings of ALT, 2012.
[1]] Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Proceedings of COLT, pages 1141-1154, 2015.
[12] Dieter Kraft, A software package for sequential quadratic programming. Technical Report DFVLRFB 88-28, Deutsche Forschungs- und Versuchsanstalt für Luft- und Raunfahrt Institut für Dynamik der Flugsysteme, Köln, Deutschland. 1988.
[13] Tze Lung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.
[14] Holden Lee. MCMC algorithms for sampling from multimodal and changing distributions. PhD) thesis, Princeton University, 2019.
[15] Kanishka Misra, Eric M. Schwartz, and Jacob Abernethy. Dynamic online pricing with incomplete information using multiarmed bandit experiments. Marketing Science, 38(2):226- 252, 2019.
[16] Vivek Myers, Erdem Biyik, Nima Anari, and Dorsa Sadigh. Learning multimodal rewards from rankings. In Aleksandra Faust, David Hsu, and Gerhard Neumann, editors, Proceedings of the 5th Conference on Robot Learning, volume 164 of Proceedings of Machine Learning Research, pages 342-352, 08-11 Nov 2022.
[17] Hassan Saber. Structure Adaptation in Bandit Theory. PhD thesis, Université de Lille, 2022.
[18] Hassan Saber and Odalric-Ambrym Maillard. Bandits with multimodal structure. Reinforcement Learning Journal, 5:2400-2439, 2024.
[19] Hassan Saber, Pierre Ménard, and Odalric- Maillard. Indexed minimum empirical divergence for unimodal bandits. In Proceedings of NeurIPS, volume 34, pages 7346-7356, 2021.
[20] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.

---

[21] Cindy Trinh, Emilie Kaufmann, Claire Vernade, and Richard Combes. Solving bernoulli
rank-one bandits with unimodal thompson sampling. In Proceedings of ALT, 2020.
[22] Bart Van Parys and Negin Golrezaei. Optimal learning for structured bandits. Management Science, 2023.
[23] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weekesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C. Carey, îlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, lan Henriksen, E. A. Quintero. Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature Methods, 17(3):261-222, Mar 2020.
[24] Yining Wang, Boxiao Chen, and David Simchi-Levi. Multimodal dynamic pricing. Manage. Sci., 67(10))6136 6152, October 2021.
[25] Jia Yuan Yu and Shie Mannor. Unimodal bandits. In Proceedings of ICML. page 41 41-48, 2011.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We indeed provide in the paper the first known computationally tractable algorithm solve the Graves-Lai problem for multimodal bandits.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to 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: We state in the conclusion that interesting future work would be to characterize the minimal computational complexity required solve the Graves-Lai problem.
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 a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to 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.
12

---

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 fairness.
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 It acknowledged in the paper. The authors should use their best 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 proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions clearly stated in Section 3 and detailed proofs of all results are provided in the appendices.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if 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.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The dynamic programming procedure used is described fully in the main paper. Details on OSSB's 's implementation (along with the corresponding pseudo-code) and our experiments provided in Appendix
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility also be provided via detailed
13

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS 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 to reproduce that algorithm. (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 be 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 welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The code used for the experiments is available at htttps://githubb com/ wi wilrev/ / Mult imoda Bandits
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.. cc/
public: des CCodeSummeeseeeeee s aisionnolico 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 NeurIPS code and data submission guidelines (https cc/ //nips.cc/publcc/////ecc
http://ccppbiiicciieceeeeeeeee/e htlliic/ggiiss//ee/ /eddeeee/oodSuuuae Stt./ooooosmmmisionnnne wammiisssooooiioooo 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.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The specific instances considered are provided explicitly in the paper.
Guidelines:
14

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Empirical 95% confidence intervals are provided for the regret results. 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, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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.
is OK to report I-sigma error bars, but one 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 are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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 reproduce the experiments?
Question:
Answer: [Yes]
Justification: Hardware specifications are provided in Appendix A.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpl//ttwsss...ooo.....//op//pt
Answer: [Yes]
Justification: Our research does not involve human subjects or sensitive data, and we do not believe our research findings to have any potential negative societal impact.
15

---

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 sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is mostly theoretical, and consequently has no immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal 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 not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate 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 out 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 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 a 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 models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring 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 is 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
16

---

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: The code used is our own and the data synthetic.
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 a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperr curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
com/ dat aset s has
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's '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:
We introduce such asset.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model 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 anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
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 details about compensation (if any)?
Answer: [NA]
Justification:
We conduct no such experiment.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 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.
Institutional review board (IRB) approvals or equivalent for research with human subjects
17

---

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:
We conduct no such experiment.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 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 as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs not used non-standard component in this work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy /tsttp::/neuriieee wwt.///oeeeeence///OO0000 L.LM) for what should or should not be described.
18

---

A Experimental details
A.1 OSSB for multimodal bandits
As explained in Section B asymptotically optimal algorithms for structured bandits attempt sample + k-' (pi) a number of times Vi I o T) when 7 - oo, where v) is a solution to P&l The OSSB algorithm of [1] does so by sampling dictated by the solution to the Graves-Lai problem for the empirical estimate (t) of f4, updated at each round t. The pseudo-code of OSSB for multimodal bandits given in Algorithm
Algorithm 1 Optimal Sampling for Structured Bandits (OSSB)
(1) 0, (1) + Vk [K] (Initialization]
for = 1,..., -T do
Compute 77" (t) the solution Pcl for pt(t)
if E [K] (t) 2 (t) In then
k(()) < arg max PA (1) (Exploitation, ties broken arbitrarily) kE[K]
else
Na(t) [Exploration, ties broken arbitrarily) kE[R] Mh (n(())
k(t) + arg min
end if
Observe (k.(O,t
for k + k(t) do
(t + 1) + (t) (t 1) t (t)
end for
(t + 1) +- Xacu (tr
(1++
NR(1) (1 1) (1( +1
end for
We implement versions of OSSB. Each version is associated with a specific sampling strategy
n7 (t), which it aims follow round Let Å (f) max Pay (f) (t)(t). These strategies are given by:
the solution to PGl for (a(t), as computed by our algorithm, with the convention n (t) 0
if l: arg max (t) (Multimodal OSSB, Algorithm
(t)
1
0} (Classical OSSB, rates given by the Lai-Robbins
bound 131
The specific instances μ E F2 considered in the experiment of Section 6 are shown Figure
Peaked instance (a = 0.5)
Flat instance 4.0)
0.05
1.82
1
2
0.14
0.27
1.72
2.03
3
6
0.02
1.00
0.04
2.00
1.34
1.74
1.58
2.37
Figure 4: 2-modal reward instances on the binary tree G (K = 7, MM [4,6), k()) = 6).
19

---

In this specific experiment, instead of the penalized subgradient subroutine described in Proposition 9 we used the Sequential Least SQuares Programming (SLSQP) method from [2] and implemented in SciPy by 23 for faster convergence towards solution to Par. for each fi(t), and we only solve
PcL
when = 2 for k E {O...., logg Tj}. We used 100 discretization points.
A.2 Runtime experiment
In this experiment, evaluate the runtime of the algorithm of Theorem 2 with respect the number of arms K. We generate line graphs with varying numbers of arms K E 200, 25, 30, .... 70}, number of modes I (m)] = E 12,3, 4, 5}. for 100 discretization points and penalized subgradient descent. The reward instances are generated as in Section 6 with o 2. To ensure that they are always m-modal, the position of k* k*(() and of the other modes μ4 are chosen to be as spread out possible. We perform 5 trials per configuration (K, m.. Figure 5 displays the average runtime as function K for each value of on a log-log plot, as well the corresponding
100 iterations of
slopes obtained from log-log regression. The runtime exhibits an approximately quadratic growth with the number of arms, which aligns with the time complexity O ((2mm)d) stated Theorem 2
modes (siape: 2.09)
3 modes (slape: 2.16)
Average runtime (s)
modes (slope: 2.22)
modes (slape: 2.32)
2830
2x32
Number of ex
6:00
Figure 5: Runtime function of the number of arms.
All experiments were single desktop PC equipped with an AMD Ryzen 5800X 8-core/16- thread CPU @ 3.8 GHz, GB DDR4 RAM.
B Proofs of Section
Proof of Proposition 7 Applying Theorem in ① to the parameter Fsm yields that the Graves- Lai constant Cmm, pb) is the value of
minimize,, A subject to xEA(m.,1)
inf
TT d(d(u, A) and 17
with A(m, (X
(A)* + k} for k k*()). By Assumption ! dx 2x) = 0 holds if and only if pk dg. which concludes the proof.
F Fsmm de (MR, Ax)
C Proofs of Section 4
C.1 Proof of Proposition
Assume that (m,, 14) = 1=1 Z₁ where the Z, are disjoint convex sets. Denote by X(m) the set of independent sets of of size m, and let us lower bound its size. Consider the process in which we first select node œ1 [K]. and then for i 2, where N/ (zzy) 2, and its neighbors. Then (I1...., Fm is an independent and at step of the process has at least
select node o; E [K] in [K] \u (z)))(
G of size m,
[K] NO Σ [N(x)) (m(eg(()
20

---

choices, since [M(zy)] - deg(G) + 1 and i Σ m. Hence, the number of independent sets of G of size m is at least
[e(m)) 1 (K (deg(G) + 1)m)"" m!
For each independent set of size m, X X(m), define the vector μx E RR* such that 5 = 1(k e }} for k E [K] We can readily check that n. multimodal with m modes, and that its m modes are precisely the elements of X. Now consider another independent set of size m, X' E (m) and consider A x (3/4) + (1/4)x*** convex combination of μ x and μx For & X we have that A = 3/4 and 2 Σ 1/4 for any 1 that is a neighbor of k, and hence & is a mode of X. On the other hand, assume that there exists & E X' such that k is not neighbor of node in X. Then X X,X' = 1/4 and X x.X' = for any k that is a neighbor of so that k is a mode of X X Putting it together, this means that, for X X to have modes, one must make sure each element of X' is the neighbor of an element in X.
Consider X Zi for some i. For any X' UZz by convexity we must have X Zi so that X has m modes. By the above this means that all elements of X' must be neighbors of X, so ((m) U Z E (d) since X' has m elements and has at most deg(G))m neighbors. Since the Zi are disjoint,
m
4)K.m)
(deg(G)m) m
m! (K- - (dog(G) + 1)m)" $ [1(m)] = Σ 1=1
(m(m) U Z {U(,, m)
This yields the result: 4(K, 2
((deg(G)- (deg(G)m))
(K (deg(G) 1)m)
C.2 Proof of Proposition 3
By definition, for any À E (m,m, 14), we must have A > n², so that inf infxe 7 d( A) 2
de (Mk: v²)) Conversely, let > 0 and x u + (μ* + pa (e()), If (fIM(u) <,m, M(X))
M(U) U {k} ensures that [MM(F)) S m and in turn X E (m, p1). If E (()), either le is a mode of μ and M(X)) M(H), or k is neighbor of mode E and M(X²) M(p) ( \ (?).
In any case, [.M(2F] S m and in turn X E BA (m,, p.). Consequently, xnfxe (m..s) 7 d(d,, A) <
n d(ps, X=) de (MR, + e). Letting -> O yields the other side of the inequality. Finally, note that μ (n* px ( lim -0 X E By (m, pt). This concludes the proof.
C.3 Proof of Proposition
We first demonstrate the following intermediary result. Lemma 1. The closure of B& (m, (1) in TRKK given by
Fx = (A Fsm: de 1 Ae max dj. d 2 kr SE[K]
Proof. Consider (A') a sequence of elements of (y 11) with lime X' = X and let us prove that x E FR. For all t 2 O, have Xx-((m) (m) = =p. Furthermore, for all t 2 O, (At) = k. hence X > Ma-(w)) = 1²* so that X nr. Now, let i E M()*), which implies A > XP for all l neighbor of i. Hence, for all t large enough, i E M(X*). Repeating the same reasoning for all the modes of X for all large enough, M(A)) C M(X*), and [M(*))] < [M(()] I We have proven that x E FR. Conversely, let X Fe. Either d n² and X (a Bm,,, u), or Xj S 1x for all j. There are then two cases to distinguish.
(i If & is mode of X, we can write X = lim A' where X E BB u) is defined by
X = = + 1/t and X; = Aú for j + k.
(ii) If 1: not a mode of X, as X, S n* for j. this must mean that there exists a neighbor of & such that d >u= n²" Note further that l & (())) ensures E o k² (n). Then we can
21

---

write À = lim X' where X E (m,,, μu) is defined by X3 = μ² + 1/t for E {k, and 23 Xy otherwise.
In any case, we have shown that X E BR (m, 1c), which concludes the proof.
We now prove Proposition 4 By Assumption
A + 7Td(u X) is continuous, so that infxes (m. 77 d(H,, A) = inf (m, 1 d( X). Consider now X E Bx μ)) such that de μ² for some and let mine (Ae 1x)) the minimal amount by which entry of X larger than μ=" We will show that there exists X (m,, 11) such that 17 d(js, (() < n d(p, A)-
Consider graph G' = ([K], where (i, E E" and only (i,5) E E and X; = Xy. Consider C [K] the connected component of G" where l lies. Consider the minimal gap between two neigh- boring arms: min().) 1d=-dyl Consider X such that X = X; (min(e, 8)/2) [i E S}. As the nodes are modified by strictly less than 6, we have M(X) = M(2). As they are modified by strictly less than E, X₂ > 1=" turn, X (m, p.). Furthermore, d(u,, X) d(p, A) since for all k, AR- + du(us, Ax) strictly increasing whenever d > μ² 2 Maa. which implies that d(p, X) < n d(p,))
We may prove similarly that if A < μ. for some L, there exists A' E Bx μ1) such that n d(p, X) < 17 d(u, 2). This ensures that inf (mm.))) 17 d(p,, A) inf XeB, n d( A). Finally, as À n7 d(d(,,, X) is continuous the compact set B (m, ft), the infimum is attained. This concludes the proof.
C.4 Proof of Proposition 5
Consider 77 defined 7l- Te (e for all k + k* and where the value of MTk is arbitrary.
Let us check that v is feasible solution to Par. For any E Bmm. 14), there must exist * k (ta) such that A > >p+ and therefore v TT d(,,, A) 2 T (#x, A&) > ne (Ht, u²)) ) = 1. This shows that inf Xe B(m,zx) infxe
17 d(ps, A) 2 hence 77 is indeed a feasible solution to Par, so r must have higher
value than solution n7 of Par. As long as v = 0 when A = 0 (note that this choice does not impact the value of Par. we get
A de (p),
In A min S "7"
A ASTA
Σ A,
hence |17 S B(z) as announced.
C.5 Proof of Proposition 6
Consider i # h mode i M(X"), and define the minimal difference between i and its neighbors 5, mi) ! -31) For all 8' (-ō;, 6t), is noted that M(A*) MM(* (+)( and so A + ( E B% (m, μ1). Therefore, the function + nd(p=* x + (() must attain its minimum at 5' 0, which implies A μ4: Further consider & neighbor of and 5g |\ Xi1- For all 8' E [0, dz), it noted that M( + + c M(x*), so that X (+)) E (m, 11). Therefore, the function 8' + nd(p", x + d' (!) must attain its minimum at 8' O. which implies X 2 pe- Putting it together, we have proven that, if E M(X*), for all (f, E E we have ue S X < X = ps. and in turn M(1), which concludes the proof.
C.6 Proof of Proposition 7
Let us consider À minimizer of 17 d(p,, X) over (m, u)) We already know that À [p,, μ*] from Proposition Consider G the directed tree rooted and define À a rounding of À using the following recursive procedure: start the root Xς arg minfle A&l x E D(n, [1)} then for all choose
de argmin((e Spcol 1 D(n, 1), sgn(x )p(e) sgu(de Ap(e))
22

---

where p(() is the parent of l and sgn is the sign function. The idea is that, when rounding in this fashion, we both have the insurance that for any (i E E lie À S (1/n)(u* _u,) that, by p4) and we also have that sgn(>; Xe) = sgn(A; - so that M (A) = M()). In essence, we round À to ensure both small rounding error while leaving the set of modes unchanged. We further have
recursion over E: І|J X| Σ (I/n)diam((()("
Xe)
n (''d(u, x) 17 d(p, A) + 17 (d(u,, X) d(p, A)) - 17 d(p,, X) + 1 [dd X) d(p,, A)II2
S <n d(p, x) + B(n) A|I s n T d(p, X) +
Allm
$ 5 d(ps 2) + C(p)
with C(μ) diam (G)ammG))("" p.)) ) (p) ( using Assumption 2 the fact that ||ml BB1))) and the previous bound. This concludes the proof.
C.7 Proof of Proposition
We recall that consider the graph G* which is a directed tree rooted at k. Consider node E and its parent p()), assume that Ap()) is known, and we wish to minimize the value:
medelue, de) + Σ n;d
JED(()
which corresponds to 17 T d( A) restricted to and its descendants, subject to À E B (m, po). Then it suffices to optimize over de and A for j E D(e). Also, we may readily check that setting "Tk (1) = +00 is equivalent to enforcing the constraint (g= = jr. Of course, the sign of X - >p(0) important to ensure that the constraints are satisfied, Define fe(z, +1) the minimal value that can be obtained if selecting À = = Ap(t) and fe(2,-1, the minimal value that can be obtained if selecting A = S Ap(e). Consider de and Xp(e) fixed, and let us examine how one can select X, j E C(E) the children of to ensure that X E Bx, (m, (u) respected.
(i) First consider & M(H) U {R} \ (k'), so that & should not be a mode. If Ae S Xx(()) then & cannot be a mode anyways, so for each j E C(t) we have two choices: select X I Xg, which gives minimal value of minw5= (w, -1) (2,-11 select X, > de, which gives minimal value of min fyW +1) = (f The minimal value over these two choices is f2(2)
min(ff(z, -1), -1). +1)). Therefore,
fe( -1) = mede(us, + Σ 82(2) jEC(E)
(ii) de > >p(e)) since should not be a mode, one must make sure that there exists at least one child v C()) of such that d S Ae. and the value of X, for j E C(E) \ {u) can be chosen freely. Of course, if C(f) = 0 this is not possible and one has simply fe(z, +1) = too. If C(E) & 0 and E C(E), minff,t fo (2, +1). fo -1}} represents the minimal cost of choosing a value of X, such that de S An. By the same reasoning as before, the minimal obtainable value is therefore:
fe(z, = mede(ee,) +
Σ ff(2) + min 9x(2)
vEC(E)
jEC(E)
for (=(=)) min 1)) - [8);;, where we have minimized over the choice of V E C(P).
(iii) Now consider the case f M(1) U [k} (K'). Since l can either be mode or not a mode, regardless the sign of X - Ap(e). we have no constraints on the choice of X for j E C(f) and the minimal value that can be obtained is
fe(z,u) mede(pe, + Σ f1())
jEC(E)
for both 1 and u +1.
We have proven that fe indeed obeys the dynamic programming equations. Since & the root of the tree and we must have >; n², then fa( , u) is the value of PoL K" for any
23

---

C.8 Proof of Corollary 1
From the definition of Par. (k; K, k')
X n², Consider & + k and its parent p(() in Gh, and assume
that Xp() is known. There are two cases to consider:
(i If p(t) M(A) U {k)
\ (K', Ace) X)2(E) where (2) is the parent of p((), and
= arg minvec(p(() (2) is the node that induces the smallest cost when constrained.
we must have d 2 (e) to ensure that p(t) is not mode. There are two choices:
either select X7 > p(E) which yields value ( p(e)) +1) and dictates the choice XB
arg min p(1) fe(z, +1), otherwise select X = ppt)) which yields value felX 1).
Taking the minimal value among the two choices gives:
min Ace (1(2,+1) (pte)
if (2)) S Se(D 1)
if f (X (ee)) Se (e(X) -1) 1)
iii) Otherwise, there are constraints the value of Xj: either select X7 > Xp() which yields value Sł
and dictates the choice X E arg argmin:s> Je(z, +1), oth- erwise select d I X010) which yields value f f2() -1) and dictates the choice X arg min Se(z,-1), Taking the minimal value among the two choices gives:
arg m j00 f((2,+1) if f7 ((E) +1) s (X -1)
1
arg sigming5s0 fe(2,-1)
if if p()) +1) (x -1)
It is noted that storing the values of Te(z,u), [7(,, u) and f2(z) for f E [K], D(n, (1) and u E {-1, +1] requires memory ((nK) since [[n,, [o] = n. Furthermore, if f5(2, (z, u) and (z) for j E C(t), x D(n, 1)) and u E (-1,++1 +1}. have been computed, then one may compute Jz(z, w). [2 u) and [=) for Z E D(n, UI) and u E 1, +1} } in time ((n]C(E)) from the dynamic programming equations. Since ΣeE[K] ((() K 1. the complete procedure requires time O(nK). This completes the proof.
C.9 Proof of Proposition g
To ease the notation, denote
g(n. μ1 n))
min XET DD
(n d(j,, ))} and g(n p))
min AEB(mp)))
dnu, A)}.
Recall that ((()) n + 7 max (n, n, n2), 0] which is convex as sum of linear function, and maximum of linear functions, with subgradients:
A yd(H, () n. n) < 1] = e Qh(1))
for any such that g(n,, p4, n) = 17 d(p,, A). The norm of a subgradient upper bounded as
||l| - A 2 + 711d(1 ll < |||| + + 2 -p-) = E(H)
since
|d(,,)))12 V A)I11 S VKA(M)) A111 S K3/ (3)2 14))
Hence, h is Lipschitz continuous with Lipschitz constant E(H). Let n7" the minimizer of h over (R+)), K. and let us prove that g(n" p.n) n) 2 Any subgradient n7 must have positive entries so that:
0 A -d((p, (n d(p, X) s 1}
where is such that g(n", n) = 17¹ d( Å). In turn, since Ā E B(m, μ) there must exist
k o k² (2)) such that X 2 n² and hence:
AE L Inn d(ps Á) S 1] S 7dl (uk U²)
< 2
24

---

by definition of y. This implies that m7 nT d(p, A) 2 1 and so g(7",, p,,) 2 1. So 17" minimizes 17 A over the 77 such that g(7), fe, n) 2
We may now analyze the iterative scheme in itself. Since h is convex and Lipschitz continuous with Lipschitz constant ((u), and our iterative scheme is projected subgradient descent with step size 6, from [Lmmaa 14.1]:
I(T(()) Mnn') -
11 + 186(1)2)
+ 18((1)))
2
2t
VKB(H))(u) ((1)
vl
vi
where we used Proposition and setting 82 (p)) (e())²
to optimize the right hand side.
Let us now check that rt) is an approximate solution to PGL
From the above
(tt) TTA < h(7(t)) & h(n") + 3(pz) = 17
3(p) I [C(m. + 3(p)) Vt
VE
vt
using the definition of the above bound, the fact that ny" A is the minimum of nn A subject to g(7. 14, n) 2 1, 17 2 0 and the fact that C(m, 14) is the minimum of v A subject to g(n. 11) 2 1,
n 0. Scaling the above both sides gives bound the value of (t):
C(H)
(8(L) 7V
(Clm. 1)) 3(H))
nit) T
1
2
Vl
We now have to check that (t) is feasible solution the case @ < 1, so that:
PaL
Denote by Φ ( p4, n). Consider
7(t)
min (
n
A
min m
1 A on" A
where used the fact that g homogeneous, i.e. g(n, p4, n) & if and only if g/// ,r, n) 2 1. This implies
A l(T((()) - ((1))) + 8(1))
3(m)
on" A + {
A + = nj"
Vt
Vt
Rearranging the terms we get:
1 à 5 (((
Therefore, using Proposition 7
C(H)
1 C(H)
8(())
( 2 ((7(tt.
n
And once again using the homogeneity of we get
g( 14) s(((t)()()))))))))))))) n.) (1- C(H) 2
3((1)
21
7V7
which is the announced result and concludes the proof.
D Proofs of Section 5
D.1 Proof of Theorem
3
Consider (M),), k k*t (fz) mode of y and & the neighbor of k which is the closest to kt that
is arg mine, 1p4- mel- Define the parameter X + (n¹ - (1y)e(i)) (ee (4))(()) One may check that E B(m, 1a). For any feasible local search strategy n we have S 1) d(p, A) = ny (Hy, 21) + (ux, de) = myd v²) ) mmd (Mk. M - -ôx) dy (WA, p 6x) since 17
25

---

as j & (H)) and is local search strategy. Hence. A 2 de de( for any mode is and summing over modes get the announced result
A
Ak
Cloc (m, p1) N
E
du (UR, PA
6%)
(EM(())((
Now, since a multimodal bandit problem is also classical bandit problem, we always have
AB
C(m, 1o) S
Σ
de((es11))
KE(K
so that
Cmo 1e)
sup M.F. C(m,
+00
as there exists reward functions μ E Fm where 6ς is arbitrarily small while μr" - Ps remains
comparatively large for any k + k- (px), for instance consider where 14, = 1 if k k- (14),
j4k = 6 k E M( \ {k* ({1) and μa = 0 k & M(μ).. This function has exactly m modes and
5g- for any mode k + k- (p))..
D.2 Suboptimality of IMED-MB
We argue that IMED-MB cannot be asymptotically optimal for all instances μ E Fsm- contrary to the statement of Theorem 2 in [8]. Consider an instance f4 E Fm.. for which the optimal value for local search strategies is strictly greater than the value of P i.e. Cine(m, μ1) C(m, p1). Such an instance is guaranteed to exist by Theorem 3 Assume by contradiction that their Theorem holds.
Then, by their Proposition 1, IMED-MB asymptotically optimal, so that
lim sup R(p, s (Cmm, p.). Im(T)
T-xx0
Furthermore, by their Proposition and Theorem again, k + k*()) and The [[N,(T) we have 7 (=(.)rr) if k E (Ww),, and 7/ = 0 otherwise. In particular, n is a local search strategy (and IMED-MB is uniformly good), that its regret must verify
lim
In(T)
lim inf R(H,T) (m, T-000 In T
Combining these inequalities leads to:
R(u, T) In(T) < limsup
R(p T) T+000 In(T) < C(m, pl),
(m, p)) S lim inf
T-000
a contradiction.
D.3 Proof of Proposition 10
Consider mode and l one of its neighbors. For Gaussian rewards the conditions become (n* )² n(Ōz/ 2 and (μ² 14)2 x(u 0z/2 12) These conditions are equivalent to A S vKōz/2 and A S VK(At - A 62/2). This must be true for all neighbor of & and
should hold when A, A + ōR. therefore must have A ( 1)62- Hence, μ is r-peeeed
if and only if A & L T
1) for all k E M(u).
D.4 Proof of Proposition I1
By Proposition for E (44) \ (1)),, inf Xm 7) Td(( mada(pR n²), so for any n feasible solution Par. we must have mh 2 Ta Summing over N(H)) \ (k*(())) the
value of Pf. is lower bounded as
A de de(pe, 1*)
C(m, (4m,
Σ
(EN(
26

---

Now, consider the local search strategy defined as
max delmeme" (e 02 1
if E M(H) {K(
1 de(pz,0")) de 61112) if (ki E) E E and & E M(H)
max
0
otherwise.
Let check that v is feasible. Consider X E B(m, 14) attaining its maximum at l E [K] {kr (n)). J. On the one hand, if & (H),,, since 0 > 4r" we have n7 d( X) 2 na (u At) me (p p²) 2 1. On the other hand, if & (() there must exist least one j E M(H) such that j & M()), as otherwise À would have more than modes. In turn there must exist &
neighbor of such that X3 S λe. This implies that either X S P1j 6 < Mi and in that case n" d(,, X) Z n5d X3) 2 [1d] 6//2) 2 1, or be > Py 6,/2 > P4 and in that case n d(p, A) 2 Mede(pe, Xe) > mede(pe, 6,/2) 2 1. all cases we have rj d(p, X) 2 1 for all
A E Bm,, p), hence 17 is feasible. This concludes the proof.
E
An improved dynamic programming procedure
In this section, we describe a more complex, but more computationally efficient dynamic program than that presented in Section 3 which enables solving PGL more efficiently. Throughout this section we view G as the directed tree (k"(() (()) rooted at node k* (ft).
E.1 Dynamic programming variables
We describe dynamic programming procedure to solve the optimization problem
minimizex 17 d(μr, A) subject to E Upet (u) (n)Ba Bm 11)
(m,
(PaL)
where B& (m. (u) (m, p1) n ((n, 14)* (refer to Proposition 4 for the definition of B3 (m, p)). Consider A the optimal solution to this problem. Then there exists a node k & k- (p) such that Ag = ==" With a slight abuse of notation, we denote this node by ks (X*). We distinguish two cases.
Case 1. If k (A*) N(,), from Proposition the optimal solution X + (p* pa (x) and the optimal value is mada (*).
Case 2. If k (**) & M(2),, from Proposition
6 the modes of X must be located at M((*) M(H) U (R} \ (R'), where k E M(H) \ (1²())) is the mode of f that is not a mode of X"
Given node l of G, and flags (z,a, b. c) D(n, x 1,, x f0,1} x (0, 1} we de- fine hy(2, a, b, c) as the minimal value of ΣjED(euue)) Pydū(15) Aÿ) where M(A*) M(U)
(B*()*)> {K'} for some k' E EM(()) \ (l*(()),, under four constraints:
(i) >₂ =
(ii) If a = P.EEM(AN if 1, 1, maxvec(e) An 2 de, and if a = 2, Apce) 2 A (iii 1(**(A*) D() {{}}
(iv) 1[K D()) [()}
We further define A a, b) as the corresponding optimal solution. Recall that Gk* is tree rooted at 1:* (H1) and that in case 2, ke (1)) must be a mode of X* Putting the two cases together, the
optimal solution to Pa1 is
n 1++(0 (p' 14 (e(tt) (k* (n), (,,,,,",,,111 1,)
if The de. (Mt, v²) S (m) 0,1,, otherwise
X
where k- E arg minkeN(()) meda (pk. n²)).
E.2 Terminal conditions for leaves
First consider a leaf of G. Then five terminal conditions must be satisfied: (i) Since 1 requires min,gcte) X, 2 de, must have #
(ii If b then e + k-' (X*), that either & or l M(H)
27

---

(iii) If b- = then E = k**),,,
) so that a = and l & M(H) (iv) If c 0 then l + K', that either or & M(H)
(v) If = 1 then f = k', so that + 0 and l E M()) that
((2,0,,,c) nede(me, 2) + EvED(E) Rol au au, bu, Co) 4000
(f) (v) hold
otherwise.
E.3 Dynamic programming rules for internal nodes
Now consider internal node of G. We wish to compute the value of recursively using dynamic programming. We first write
he(z, (lz,a,,b.)) = nede(pe, +
Σ vEC(()
ho au, bo)
where (Ze, aps be Ce)xEC(E) obeys set of rules:
(i) If a 0 then E is mode of X, so Eu z for all E C(E), and a, 2, because A, dp X(())
(ii) if
then l has child with higher value, there must exist at least one C(C) with 2,
(iii) If = 0 then b, = 0 for all a E C(E). since if the subtree does not contain k" (X*), then none
of the subtrees of contain (X*)
(iv) I =
= and & E M())), then l = k: (A*), so that none of the subtrees of v contain (*(A),, i.e., b, 0 for all v E C(E).
(v) 6 = and either E {1,2} or f E M(μ), then Evec(e) by = 1, since if the subtree of & contains k- (X*), and 8 + (X*) then there must exist exactly one whose subtree contains k- (X*) (vi) If = 0 and & E MM then a = 0, since the subtree of & does not contain then & * Kt,
which gives / MM
(vii) If c = then C2 = for all v E C(f). since if the subtree of does not contain then the subtree of all v does not contain k'
(viii) If c = 1 then either = {1, 2} and 8 E M(1) and we have = k', which implies c, = 0 for there must exist exactly one whose subtree contains k so that EvED(e) Co
all E (()),
(ix) If 2 S = then 0g 2, otherwise a, E (0, 1}.
E.4 Recursive equations for internal nodes
Based on those rules we compute the value of he(2, b, recursively using dynamic programming. To do so we define the following auxiliary functions where, in Section 4.2 the minima are taken with the implicit constraint w E D(n, ()) p))
b2, = min min he(w, a, b, c). h1 (2, c) = min (w 2, b) w>a ac(01)
w<s
(),,,, min(h? (2, b, c), he(s, 2, (t(2,b,c) ba..
(2(2,,, |C(0)-1 min (2 b,
vEc(c)
82(51, (21,,, 10,1)2x0(0)
Σ (21,0, (s1, (2) for (51, 82) E z² vEC(F)
where it is noted that Xe(3), s2) 0 if min(s), 52) < 0.
We have he(z, b, too if any of the three conditions hold:
(i) a = 0, E M(μ) and b = 0
(ii) a 0, 0 g( and / μr*
( and
M(μ) and c 0.
Indeed, if and & g M(1) we must have { k>*))),, so that in turn b 1, and d = 1rt Also, af E [1,2] and é e M(a) then must have e = k', which imposes 1.
28

---

Otherwise, the value of he(2, b, e) is given by the following recursive equations, where by conven- tion, minimization over an empty set yields +oc:
he(2, b, c) medé(me; 2) + (b.1Ex
min
Σ =EC(E)
1 (z,
he(z, 1,b,), mede 2)+ +
min
min WEC(E)
{ (1 bur Gw) +
E
(2,
co)
vEC(E)
min = =ndee(me; + (bejE wEWi(=)
min
n (2, Dur; Cw) +
Σ
12(2, Dys cw)
vEC()),
h,(2,2,,,c) 2))
min (b.)EN(0.c-1((MMMM)))
{
Σ h5 bu: bol
wEC(()
with
Wx(z) = U00,)) arg min (2, h bz, =EC(()
so that [We()) < 4 and where we used the fact that
arg min ( bw Cwx) + wEC(()
Σ
16(2, co)
rEC(E),0rt
arg min& WEC(E)
N (2, Uw Cw) - -h bw (w) + Σ bus co)
VEC(()
arg min 12 bw cw) - ht bw (w)) E We(2) wEC(E)
E.5
Fast evaluation of recursive equations
We now propose an efficient strategy to compute the minimization problems in the recursive equations. For any function e, we can minimize Evec(e) (b.. cv) over (b, c) E Xe(s1, s2) in time and memory O(I((E)) for any (s1,5) {0, 1)2 using the following strategy. If ($1, 82) (0, 0), then trivially
{
Σ eEC(
Au(be,co) E (0,
min (b.c)ex2(0.00)
vEC(E)
If 82) = (1,
min (b,c)EX((1,0))
Σ
@o(bur
min
Σ
03}
be b.=1 =EC(()
vEC(C)
{ (1, - (0, + Σ 20,00,0)
min wEC(()
vEC(
and by symmetry, if (21,82) = (0,
min (b.1)
{ Σ (olbb =
min wEC(e) { (ow(0,1) Sew (0x,)))))-0000))
+ Σ
(0,0,)
VEC(()
vEC(E)
and finally, 82) = (1,
{
Σ
de (b (b), =olb) A.) Σ (0,0)
min (b,0)ERe(1,1)
vEC(()
vEC(()
with
A = min
dw (1,
wEC(()
{ (0u (1, - Dwn (0, 0) + Owg (0,1) Pen (0.0)
min
Wi ww (C(E))))))))...........)) yoy #w9
29

---

In all cases, one can compute the minimization in time (()( In particular A' can be computed by realizing that the only pairs (w, W2) that minimize the expression must be either the first or second smallest entry of (1, 0) (0, 0) and Φ (0, 1) (0,0,,), 0). We recall that, finding the first and second smallest entry of a vector can be done in time proportional to the vector size, by inspecting each entry at most twice.
E.6 Retrieving the optimal solution
Once the value of he(z, a, b, has been determined, we can retrieve the optimal solution (* (1)) 0, 1, 1) by retrieving the value of the flags (zī, ot, b2, ci) for all f. Consider node + k- (p)), once its flags (2z, az. by, c7) have been computed, we compute the flags of its children as follows.
(i) 0 0, then
arg min (b ((EMM)))) vEC(e)
{
15 (st, Σ
and
2 E arg min ho (z, 2, by ct).
(ii) If a3 1, then
(6%, vevee)
arg min (be))) wEWa(e))
min
h (2 bw Gw)
E
h5 col
vEC(E),U3
arg min (i (z
if v wa and (2t, bg) 12 by ct) e wt and hy (=2, b, (t) 1/( by (y if v A wi and h2 (2), (.) = h5 (g)
z/
2
arg min min (o (
2
if v & wa and h, ( (t) = -)(
arg min 2, ci)
if v A wi and (2t bzt, C,)) 15
where
w E arg arg min wcWi(=?)
(0 by c(m) ) (12, c
(iii) If az =2, then
(b,, Wueccn
arg min (b.))
{
Σ
(e, and
VEC(()
arg mingse; (in ho a, ct)
if hi (zt, by ct) h2222 by ot) if hy (2t, 2, (t) h5 ct) if hf (zt (b, = by,
2
arg min hp(2, 2,
Finally, at if 2 2 and at E arg mig (0.1) ho argmins can be stored during the forward pass (where compute each he(2, a, b, c)) and do not need to be recomputed.
a, bū ct) otherwise. In practice these
E.7
Computational complexity
Recall that E (p,,,) which is grid of size If h,, b) has been computed for all (z, a, b) and all v E C(E), then one can compute h2 (z, b, c). h, (z, b,c). (5 b). h (z, b, e). 1t(2, b, c) for all (z, a, b, c) and all C(C) in time (f)(C(E))). In turn, using the fast evaluation strategy explained above, one can compute he(2, a, b, c) for all (z, a, b) time ((n(C(E))). Therefore, the with this strategy O(n (((O)) = O(nK) since GL
total time and memory required to solve G is tree.
E.8 Runtime comparison in practice
The improved dynamic program (DP) runs in time O (K)), compared to O(K2mm) for the procedure described in Section 4.2 which we will refer to the original DP in what follows. In practice,
30

---

however, the improved DP may run slower than the original DP on tree instances with moderate values of K. To clarify when one should use each procedure, we report their average runtime over 50 trials specific tree instances, with uniformly sampled at random in [0, 1] l generated as in Section with m MM())] 3, = 2, and discretization parameter of 100. We pick Gaussian divergence: du AR. 12) (A& k&) /2 for each & E [K]. We perform two experiments:
(i) We measure runtime on random trees as the number of nodes K increases, with K e {100, 400, 700, 1000, 1300, 1600, 1900}.
(ii) We measure runtime on balanced d-ary trees (i.e., each node has d children) of a fixed height h 3. We vary the branching factor d E (2, 6, 8, 10, 12), which implicitly varies the number of nodes K from 15 to 1885.
The results are reported in Figure along with 95% confidence intervals using bootstrap. The left panel shows that for random trees, the original DP is faster on average up K 1000, after which the improved DP generally runs faster. The difference is more pronounced in the right panel, with the average runtime of the original DP increasing much faster with the branching factor d of the balanced tree.
Notably, the original DP exhibits higher runtime variance. This may be explained by implementa- tion trick we applied to reduce runtime: specifically, before running the complete dynamic program- ming subroutine for each k & (p), we check whether de (#4;, μ²) 2 minseN(w) mede 1²). this holds, the subroutine will not find a parameter with a smaller value than the trivial solution of Proposition 3 hence it is skipped. The number of calls to the subroutine is therefore highly instance-dependent.
00
40
Alponitm Orignaa moroved
20
10
1000
Bronching (5)
Figure 6: Average runtime of each dynamic program with respect to the number of nodes K or the branching factor d.
31


Reviews:
[{"review_id": "Nxlue9Seut", "reviewer": "Reviewer_jMyB", "summary": "This paper addresses the stochastic multi-armed bandit (MAB) problem under a multimodal reward structure, where the expected reward function has at most $m$ modes with respect to a known graph $G$. The key contribution is the first computationally tractable algorithm for solving the Graves-Lai optimization problem in this setting, which is essential for implementing asymptotically optimal bandit algorithms. The authors:\n\n1. Prove that local search strategies are suboptimal in general multimodal settings.\n2. Develop a dynamic programming and subgradient-based method to solve the Graves-Lai problem efficiently.\n3. Provide theoretical guarantees and empirical validation of their approach.", "questions": "Refer to the weaknesses.", "limitations": "Refer to the weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The problem is relevant.\n2. The contribution is significant. It's primarily driven by the mathematical analysis that seems robust. However, I did not check it in great detail.\n\n**Weaknesses:**\n\n1. Solving discretized subproblems using DP might be very expensive depending on the discretization parameter.\n2. The numerical experiments are convincing. But, they are limited to synthetic data on line graphs with Gaussian rewards. There is no exploration of performance on more complex graph structures (e.g., trees with varying degrees) or real-world-inspired settings. Can you include some real-world scenarios/datasets?\n3. The paper is dense and highly technical. Some sections (e.g., the dynamic programming recursion) could benefit from more intuitive explanations or diagrams. The notation is heavy and may be difficult for readers unfamiliar with structured bandits or Graves-Lai theory.", "was_revised": true, "final_justification": "Based on the rebuttal, I have decided to maintain my score.", "rebuttal": "Thank you for your positive review and your remarks. We address your concerns below.\n\n* **Cost of solving subproblems with DP**. In our opinion, the linear dependency in the discretization parameter of the runtime complexity of the algorithm is reasonable; more specifically, it scales as $O(K^2mnt)$, where $K$ is the number of arms, $m$ the number of modes, $n$ is the discretization parameter, and $t$ the iterations of subgradient descent per step (Theorem 2). \n\n* **Numerical experiments**. We will be able to perform additional experiments with more complex tree structures or reward distributions in the revised version. To more closely align with real-world scenarios, we propose to consider reward instances encountered in applications such as dynamic pricing (e.g. those in [15] and [24]).\n\n* **On the paper clarity**. Thank you for pointing out that some sections may be too dense and for your suggestions to improve clarity. To help build intuition, we propose to add a worked example of the DP procedure on a simple line graph, such as the one in Figure 1, and a diagram to visually illustrate the procedure.\n\n\n[15] Kanishka Misra, Eric M. Schwartz, and Jacob Abernethy. Dynamic online pricing with incomplete information using multiarmed bandit experiments. Marketing Science, 38(2):226–333 252, 2019\n\n[24] Yining Wang, Boxiao Chen, and David Simchi-Levi. Multimodal dynamic pricing. Manage. Sci., 67(10):6136–6152, October 2021"}, {"review_id": "nn0HRhqP4l", "reviewer": "Reviewer_PpQT", "summary": "This paper addresses stochastic multi-armed bandits where the expected reward function is multimodal with at most $m$ modes on a tree graph. The authors provide the first known computationally tractable algorithm for solving the Graves-Lai optimization problem in this setting, which enables asymptotically optimal algorithms. The key technical contribution is a sophisticated algorithm combining discretization, dynamic programming, and projected subgradient descent to navigate the non-convex constraint set. The paper also proves that local search strategies, used in prior work, can be arbitrarily suboptimal, establishing the necessity of solving the full Graves-Lai problem.", "questions": "1. The algorithm has time complexity $O(K^2mnt)$. How does it perform in practice for large $K$ (say, $K > 1000$)? Have you considered approximate versions that could scale better while maintaining theoretical guarantees? \n\n2. The DP decomposition leverages the acyclic nature of trees; cycles destroy the neat top-down factorisation used to solve the semi-infinite LP in $O(K^2)$.  For general graphs, even bounded-treewidth cases introduce exponentially many confusing parameters and break the current structural lemmas.  What are the main technical barriers to extending this to general graphs? Is the problem fundamentally harder, or is this mainly for technical convenience?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n- **Clear problem formulation**: Well-motivated extension of unimodal bandits with clean mathematical setup.\n- **Solid theoretical contribution**: First tractable algorithm for Graves-Lai optimization in multimodal bandits, solving an important open problem. This work proves that local search can be arbitrarily suboptimal, justifying the need for more sophisticated approaches. Then the creative combination of discretization, dynamic programming, and optimization technique handling the non-convex constraint set. Complete proofs with careful handling of technical details, including time-dependent learning rates. \n\n\n### Weaknesses:\n- **Limited experimental validation**: Only synthetic data on small instances; no comparison with IMED-MB or evaluation on real applications\n- **Computational concerns**: $O(K²mnt)$ complexity not thoroughly analyzed; unclear when the approach becomes impractical.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We appreciate that you considered our work clear, well-motivated, creative and solid theoretically. We address your questions/concerns below.\n\n* **Numerical experiments**. In the revised version, we propose to perform additional experiments that more closely align with real-world scenarios by considering reward instances encountered in applications such as dynamic pricing (e.g. those in [15] and [24])\n\n* **Time complexity**. On the synthetic example considered in our experiments, our algorithm ran on a laptop in about five minutes for $K=70$ arms, $m=2$ modes, $n=100$ discretization points and $t=100$ iterations of subgradient descent per step (Figure 2(a)). Given the quadratic dependency in $K$ of the runtime complexity, the algorithm would run in about a day for $K=1000$. \n\n  To reduce the runtime in practice, one may reduce the number of discretization points and/or the number of iterations of subgradient descent per step, but this comes at the cost at worsened guarantees, that are made explicit in our Theorem 2. Additionally, if it is known that the reward function is peaked, our Proposition 11 shows that a much simpler local search algorithm that disregards the non-trivial confusing parameters can be used, although it will be a constant factor from optimal.\n\n* **Tree assumption and generalization to general graphs**. As you correctly pointed out, our current procedure heavily relies on this structural assumption; without it, our dynamic programming scheme would not apply. We believe that achieving optimality without this assumption would require a more involved procedure. Although we were unable to prove this despite honest attempts, we believe that if the graph $G$ is not assumed to be a tree, then the Graves-Lai optimization problem would not be solvable in polynomial time in the worst case. Some intuition for this stems from Proposition 1, which shows that the set of confusing parameters has a highly complex structure.  \n\n\n[15] Kanishka Misra, Eric M. Schwartz, and Jacob Abernethy. Dynamic online pricing with incomplete information using multiarmed bandit experiments. Marketing Science, 38(2):226–333 252, 2019\n\n[24] Yining Wang, Boxiao Chen, and David Simchi-Levi. Multimodal dynamic pricing. Manage. Sci., 67(10):6136–6152, October 2021"}, {"review_id": "rYUzlhOwpI", "reviewer": "Reviewer_Wyp1", "summary": "This paper considers a multi armed bandit where the arm set is encoded by some graph $G$. An arm is a mode, if its expected reward is greater than all it's neighbors. For some $m>0$ the arm set is assumed to contain $m$ modes. The objective of the learner is to then minimise cumulative regret as in the standard multi armed bandit. The paper focuses on the asymptotic setting, that is as $T\\rightarrow \\infty$ Optimal algorithms exist, which require one to solve the Graves-Lai optimization problem, which can be computationally challenging in practice. In this paper, the authors propose a computationally tractable method of solving the  Graves-Lai optimization problem, in the case where the graph $G$ is assumed to be a tree. The authors then go on to demonstrate that local search algorithms, that is algorithms only exploring arms in the neighbourhood of the set of modes, cannot be optimal.", "questions": "As stated above, regarding the statement that the IMED-MB algorithm from [18 ] is assumed to be a local search algorithm, therefore invalidating the claim made in [18] that IMED-MB is asymptotically optimal. I do not see how this is the case, as the  IMED-MB algorithm has the potential to conduct second order exploration across it's running time, where it is able to explore arms outside the neighbourhood of the modes. I would be grateful to the authors if they could clarify this point. It would be helpful to formally define local search algorithms in the paper, and then explicitly show why IMED-MB is a local search algorithm. Even better, would be to highlight the mistake in the proof of theorem 2 in [18], although I appreciate this may be time consuming. \n\nIt would be interesting to consider more complex graphs in the experiments. Also, what was the motivation for the specific choice of $\\mu_k$ in the experiments?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "I have two main concerns with the paper. The first is that the assumption that the graph $G$ is a tree seems quite restrictive and reduces the problem to a very specific instance of multi modal bandits. Furthermore, the algorithm proposed by the authors is very complex. For me the combination of these two points reduces the contribution of the paper. The tree constraint is not required in [18], where the authors also propose a computationally tractable algorithm for multi modal bandits. \n\nThis brings me to my second concern, regarding the statement that the IMED-MB algorithm from [18 ] is assumed to be a local search algorithm, therefore invalidating the claim made in [18] that IMED-MB is asymptotically optimal. I do not see how this is the case, as the  IMED-MB algorithm has the potential to conduct second order exploration across it's running time, where it is able to explore arms outside the neighborhood of the modes. I would be grateful to the authors if they could clarify this point. It would be helpful to formally define local search algorithms in the paper, and then explicitly show why IMED-MB is a local search algorithm. Even better, would be to highlight the mistake in the proof of theorem 2 in [18] although I appreciate this may be time consuming. At the moment I have tentatively recommended to reject the paper, however, if the authors can clarify the above point I would be open to increasing my score.", "was_revised": true, "final_justification": "My main concern with this paper stemmed from my misunderstanding of IMED-MB algorithm, I now agree that it is indeed a local search strategy and thank the authors for taking the time to explain this to me.  As a result I am happy to raise my score. I share some of the other reviewers concerns that the theoretical contribution is limited. Also, reliance on the assumption of tree structure, without any justification, is a significant limitation. In my opinion, a proof supporting the authors intuition, that if the graph is not assumed to be a tree, then the Graves-Lai optimization problem would not be solvable in polynomial time, would greatly benefit the paper.", "rebuttal": "Thank you for your insightful remarks. We address your concerns below.\n\n* **Complexity of the algorithm and tree assumption**. We believe that the complexity of our procedure is unavoidable to achieve optimality, as solving the Graves-Lai problem in the multimodal case requires careful handling of non-trivial confusing parameters. As we claim in the paper, our results entail that the simpler IMED-MB algorithm from [18] cannot be optimal.\n    \n    The tree assumption is key to apply the dynamic programming procedure which enables us to solve the subproblems. We believe that achieving optimality without this assumption would require a more involved procedure. Although we were unable to prove this despite honest attempts, we believe that if the graph $G$ is not assumed to be a tree, then the Graves-Lai optimization problem would not be solvable in polynomial time in the worst case. Some intuition for this stems from Proposition 1, which shows that the set of confusing parameters has a highly complex structure.\n\n    Furthermore, we note that our results on local search strategies and peaked reward functions (Section 5) do not require the tree assumption. Thus, our Proposition 11 shows that for general graphs and peaked reward functions, one may use a simpler local search algorithm, at the cost of being a constant factor away from optimal.\n\n* **Comparison with IMED-MB.** Thank you for bringing up this concern. Let us first clarify our definition of a local search strategy. Informally, an algorithm follows a local search strategy if it asymptotically explores the arms outsides of the modes neighborhood $N(\\mu)$ a *sub-logarithmic* amount of time. More formally, letting $N_k(T)$ be the number of times arm $k$ is selected by some algorithm up to time $T$, we define $$\\eta_k=\\lim_{T \\to \\infty} \\frac{\\mathbb{E}[N_k(T)]}{\\log{T}}$$ (assuming that the limit exists for simplicity, otherwise consider $\\lim\\inf$ and $\\lim\\sup$) so that if $\\eta_k >0$, the algorithm asymptotically selects arm $k$ $\\eta_k\\log{T}+o(\\log{T})$ times. As stated in Definition 1, we say that the algorithm follows a local search strategy if $\\eta_k=0$ when $k \\notin N(\\mu)$. \n    \n    Although IMED-MB allows second-order exploration, it is claimed in Theorem 2 of [18] that $$\\lim_{T \\to \\infty} \\frac{\\mathbb{E}[N_k(T)]}{\\log{T}} \\le 0$$ for every arm $k$ outside of the neighborhood of the modes of $\\mu$. This means that IMED-MB falls under the umbrella of local search strategies. We refer to Appendix C.2, where this is explained in more detail. We will emphasize what $\\eta_k$ represents in our Definition 1 of local search strategies in the revised version of the paper.\n\n* **Choice of reward vector in the experiments**.  Our choice of $\\mu_k$ as a mixture of exponential functions allows us to easily generate a multimodal reward vector with a set of modes and an optimal arm chosen in advance. Tuning $\\sigma$ also allows us to control how \"peaked\" the reward vector is around its modes. Another possibility would have been to choose $\\mu_k$ as a mixture of Gaussian functions (by squaring the distance between arms $j$ and $k$ in the expression of $\\mu_k$), but this tends to create easier reward instances with very sharp peaks. We propose to perform additional experiments with more complex tree structures in the revised version."}, {"review_id": "mp6RIw7GBN", "reviewer": "Reviewer_KMjT", "summary": "This paper studies the problem of stochastic multi-armed multimodal bandit: the algorithm additionally knows a graph $G$, and the hidden vector $\\mu$ has at most $m$ modes with respect to this graph (where $\\mu_i$ is a mode if $\\mu_i > \\max_{\\text{$j$ adjacent to $i$ on $G$}} \\mu_j$). The paper proposes a tractable algorithm to compute the Graves-Lai optimization program with respect to the structured bandit problem, from which one can apply known algorithms to obtain asymptotically optimal regret bound for this problem.\n\nPrevious results on solving the Graves-Lai (GL) optimization program for related settings, such as unimodal, relied on local search. This paper showed that local search strategies cannot be used to solve the GL program in the multimodal settings, thus necessitating new algorithmic ideas. The authors showed some structural properties of the optimal solution for the program, thus enabling the calculation of the optimal solution using dynamic programming on a discretized grid, followed by a gradient descent to further approximate the solution. The authors also provided some experimental results to back up the claim that the new GL optimizer + OSSB indeed gives a significantly better regret, compared to previous results based on classical OSSB or using local search to solve the optimization program.", "questions": "**Questions**:\n1) I believe that Prop 3-6 holds without the tree assumption (from a quick skim through the proofs of them), while I agree that the dynamic programming step absolutely needs the fact that $G$ is a tree, so going beyond the tree case would require a new approach instead of DP. Do the authors have any proposal for such a technique that goes beyond the tree case, or can you show that in fact there is some hardness in solving such optimization problem under the general graph case?\n\n**Comments and Suggestions**:\n1) I believe the dynamic programming can be sped up significantly. From Prop 6, the modes of $\\lambda^*$ is exactly the modes of $\\mu$, but with one modes of $\\mu$ removed and one additional mode added (that is not in $N(\\mu)$). You then do a double for loop to choose these two modes (time complexity $O(Km)$) before doing the dynamic programming (time complexity $O(Kn)$). I believe you can simply fold the outer loops into the DP by introducing two flags in the DP state: whether you have chosen a mode of $\\mu$ to remove in the subtree, and whether you have chosen a new mode to be added in the subtree. This should free the DP of the outer two loops and give you an $O(Kn)$ DP (and an $O(Knt)$ algorithm overall).\n2) For completeness, I think the authors should still include a self-contained argument for Prop 1, maybe by simply stating the previous result and explaining why Prop 1 is a direct consequence of it.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n- The paper is well-written, and I believe the structural results on the optimal solution under this setting (as discussed in the paper) is important while also technically challenging.\n- The algorithm given by this paper seems to be reasonable fast (although I believe it can be sped up, see comments below), and I believe the experiments do back up their results that this new algorithm gives a considerably better regret bound, compared to previous results.\n\n**Weaknesses**:\n- The biggest weakness of this paper would be the assumption that $G$ is a tree. This is not an assumption found in previous multimodal references, and I am not entirely sure why the authors impose such an assumption other than technical difficulties of not imposing so.\n- I am also perplexed by the runtime plot. You shouldn't need a runtime plot to prove that your algorithm have some time complexity; it would have been better to include such a plot to compare your algorithm's runtime against previous results.", "was_revised": true, "final_justification": "I have read the rebuttals and decided to keep my score.", "rebuttal": "Many thanks for your positive words and valuable feedback. We address your concerns below.\n\n* **On the tree assumption**. As you pointed out, Propositions 3-6 do not require the tree assumption. We note that our results on local search strategies and peaked reward functions (Section 5) do not require the tree assumption either. It is however key to apply the dynamic programming procedure which enables us to solve the subproblems, and achieving optimality without this assumption would require a more involved procedure. Although we were unable to prove this despite honest attempts, we believe that if the graph $G$ is not assumed to be a tree, then the Graves-Lai optimization problem would not be solvable in polynomial time in the worst case. Some intuition for this stems from Proposition 1, which shows that the set of confusing parameters has a highly complex structure.\n\n* **Runtime plot**. We agree that the plot is not necessary to prove that our algorithm has a time complexity quadratic in the number of arms. We included it to give a better understanding of the runtime in practice on a standard laptop.\n\n* **Runtime speedup**. Thank you for this suggestion. We believe that this strategy would not work for our specific problem.  In our understanding, the core of your suggestion is to augment the DP state with two binary flags to track whether a new mode has already been added and a mode of $\\mu$ has already been removed. However, the values of the added and removed modes should also be remembered: the DP recursion must enforce mode constraints specific to which mode $k$ is being added and which mode $k'$ is being removed. Encoding these values in the states would multiply the number of states by $O(Km)$, thus recovering the\n$O(Km)$ enumeration cost we currently pay in the outer loops. Of course, if we have misinterpreted your argument, we would be grateful for any further details or clarification. \n\n* **Self-contained argument for Proposition 1**.  Proposition 1 follows from Theorem 1 in [1] by setting $\\Theta=F_{\\le m}$ and noting that if the relative entropy $d_k(\\mu_{k^{\\star}(\\mu)}, \\lambda_{k^{\\star}(\\mu)})=0$, then by our Assumption $1$, $\\mu_{k^{\\star}(\\mu)}=\\lambda_{k^{\\star}(\\mu)}$. We will include this argument for completeness in the revised version. \n\n[1] Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured\nstochastic bandits. In Advances in Neural Information Processing Systems, 2017.304"}]

Author rebuttal:

Meta-review: The paper presents a study on a stochastic multi-armed bandit variant in which the arms have an underlying tree graph structure with at most m modes (local maximums). The main contribution of the paper is to provide a polynomial-time algorithm to solve  the Graves-Lai optimization problem, which leads to an asymptotically optimal bandit algorithm.

The reviewers acknowledge the theoretical contribution of the paper, especially on the first computationally tractable solution for this setting. They also raise concerns, such as the graph has to be a tree graph and the experimental evaluation seems to be preliminary. The authors provided detailed responses, and the reviewers are in general satisfied with the authors' responses. In the end, all reviewers are positive toward the paper, but do not indicate very strong support. The paper is marginal to NeurIPS, but given the solid theoretical contribution, especially to encourage research on computationally tractable solutions for bandit algorithms, I believe the paper is worth to be published at NeurIPS. The authors should provide a thorough revision to address all reviewer concerns.

AC.
Decision: Accept (poster)