Adversarial Bandits Against Arbitrary Strategies
Authors: Jung-hun Kim
Se-Young Yun
Venue: Accepted by TMLR ()

Abstract: We study the adversarial bandit problem against arbitrary strategies, where the difficulty is captured by an unknown parameter $S$, which is the number of switches in the best arm in hindsight. To handle this problem, we adopt the master-base framework using the online mirror descent method (OMD). We first provide a master-base algorithm with simple OMD, achieving $\tilde{O}(S^{1/2}K^{1/3}T^{2/3})$, in which $T^{2/3}$ comes from the variance of loss estimators. To mitigate the impact of the variance, we propose using adaptive learning rates for OMD and achieve $\tilde{O}(\min\{\sqrt{SKT\rho},S\sqrt{KT}\})$, where $\rho$ is a variance term for loss estimators.

Published in Transactions on Machine Learning Research (10/2025)
Adversarial Bandits Against Arbitrary Strategies
Jung-hun Kim
junghhnn Bensue.
CREST, ENSAE, IP Paris PairPlay joint team, France
Se- Young Yun
yunseyoung@haist.oc.
KAIST AI, South Korea
Reviewed OpenReview: https: https://openrevieeu net/ permuo id= :d=a40rOhBuCs
openreview.
Abstract
We study the adversarial bandit problem against arbitrary strategies, where the difficulty is captured by an unknown parameter S, which is the number of switches in the best arm in hindsight. To handle this problem, we adopt the master- framework using the online mirror descent method (OMD). We first provide a master-base algorithm with simple OMD, which T2/s comes from the variance of loss estimators. To
achieving ((St/2 22/37/233 mitigate the impact of the variance, we propose using adaptive learning rates for OMD and where p is variance term for loss estimators.
achieve
1 Introduction
The bandit problem is a fundamental framework in sequential decision-making that addresses the exploration- exploitation trade-off. At each time step, an agent selects an action (referred to as an arm) and observes a corresponding reward or loss. In applications such as recommendation systems, arms may represent items presented to users, and user preferences can evolve over time. This dynamic nature can be modeled by allowing the identity of the best arm to change, leading the notion of switching best arms.
To capture such evolving environments, it is natural to consider performance against changing sequence of optimal arms rather than single fixed one. The problem of competing against switching arms has been extensively studied. In the expert setting with full-information feedback "Cesa-Bianchi et al. 1997], several algorithms (Danicly et al.) 2015 Jun et al. 2017] have been developed that achieve a ncar-optimal regret bound Ö(VST) for 5-switch regret (formally defined later), without requiring prior knowledge of the number of switches S. Tn contrast, the bandit setting presents a greater challenge, as the agent only observes the feedback for the selected arm rather than the full loss vector, making the problem significantly harder than in the full-information case.
In the stochastic bandit setting where each arm's reward distribution may change over time, commonly referred to as the non-stationary bandit problem, several studies have addressed the challenge of switching environments (Garivier Moulines 2008 Auer et al. 2019 Russac et al., 2019 Suk & Kpotufe 2022
Notably, Auer et al. (2019) and [uk & Kpotufe (2022) achieved near-optimal regret bounds of O(VSKT) without requiring prior knowledge the number of switches S. However, these methods rely on stochastic assumptions and are not applicable in the adversarial setting, where losses can be chosen arbitrarily. For the adversarial bandit setting, EXP3.S algorithm (Auer et al., 2002) achieves regret bound of Ö(VSKT), but assumes that S is known in advance. When S is unknown, the Bandit-over--oan -oin---ovr--Baiiit (BOB) approach has been proposed, achieving a regret bound of Ō(VSKT + T3/4) (Cheung et al. 2019: Foster et al. 2020). More recently, Luo et al. (2022) studied the problem of switching adversarial linear bandits and achieved a regret of O(vdST) under the assumption that S known.
In this paper, we study adversarial bandit problems against arbitrarily switching arms. Crucially, we allow the number of switches S to be unknown to the agent, thereby targeting arbitrary strategies without prior

---

Published in Transactions on Machine Learning Research (10/2025)
knowledge of their complexity. To address this setting, adopt the master-bast base framework combined with the online mirror descent (OMD) method, inspired by Agarwal et al. (2017); Pacchiano et al. (0020 Luo et al. 2022]. We begin by analyzing a master-base algorithm that employs OMD with negative entropy regularizer, and show that it achieves a regret bound of 0(S1/211//793))
However, this approach relies on a fixed learning rate, which limits its ability to adapt to the variance of the loss estimators, leading to a suboptimal regret term proportional 72/3.
Building on this analysis, we propose using adaptive learning rates within the OMD framework to bet- ter control the variance of loss estimators. This refinement leads to an improved regret bound of (minn
with respect to T. where captures the variance associated with a comparator strategy. Crucially, rather than employing the standard negative entropy regularizer, we adopt log-barrier regularizer, which enables tighter control over worst-case scenarios in terms of the variance term p.
2 Problem Statement
We now formalize the problem sctting. Let == [K] denote the set of K arms, and let L E [0. 1] be the = loss vector at time I, where (a) denotes the loss incurred by arm a E [K] at time t. The environment is adversarial, generating an arbitrary sequence of loss vectors 4 .p. E [0, 1]x over a time horizon of T rounds. At each round E [T], the agent selects an arm 0; E [K] and observes only the loss 4(ae)) of the chosen arm. Our goal to minimize the S-switeh regret, which measures the performance gap between the agent and the best sequence of actions that switches arms at most limes.
Formally, let f2.,,2....., KT) E [K] denote sequence of comparator actions. For positive integer S < T, define the set of sequences with at most S switches as
Bs KE [K]T
[K]
Σ
1m + [x+t) SS
Then, the S-switch regret is defined by
RT( max REBS
Σ [(c(a))] - 4(k)).
We consider the setting where the number of switches S is unknown to the agent (i.e., not provided in advance). Our goal is to design algorithms that perform well against any sequence of actions, without relying on prior knowledge of S. This requires the development of universal algorithms that achieve tight regret. bounds uniformly over all values of S E [T 1], where S characterizes the hardness of the problem [Auer et al. 2002). Notably, this setting generalizes non-stationary stochastic bandit problems in which the switching parameter unknown (Auer et al. 2019 Chen et al. 2019).
3 Algorithms and Regret Analysis
To address the problem of adversarial bandits with an unknown switching budget S, we propose algorithms based on the master- base framework combined with the online mirror descent (OMD) method.
3.1 Master-Bass Base Framework
In the master-base framework, master algorithm selects one among several base algorithms at each round, and the selected base then chooses an arm to play. Since the true switch parameter S is not known in advance, we instantiate each base algorithn with a different candidate value of S from a predefined set.
Let H. denote the set of candidate values for S, defined as:
H (To, T Tog
Tog
T}.
2

---

Published in Transactions on Machine Learning Research (10/2025)
Each base is associated with candidate h E H. and tunes its learning rate accordingly. Let H | O(log?) 7' be the number of base algorithms. When there is no ambiguity, we refer to base instantiated with parameter & E H. simply as base h. Define h² E H as the largest candidate not exceeding the true (unknown) value of S: ht = max(h H. h 5). By construction, this ensures
e sh
which guarantees that ht provides a near-optimal approximation of S.
3.2 Online Mirror Descent (OMD)
We now present the Online Mirror Descent (OMD) method (Laltimore Szepesvárj 2020), which serves as the fundamental update rule for the master and each base algorithm in our framework. OMD generalizes classic online gradient descent by incorporating ficxible geometry through regularizer.
Let F Rd - R. be convex and differentiable regularizer function. This regularizer defines the Bregman divergence between two points p. q E Rd:
(VF())))
In context, the decision variable is probability distribution Ps over d arms, i.c., Pt E Pa where Pa denotes the d-dimensional probability simplex. At each round t, given loss vector E IR OMD computes the next distribution by solving the following optimization problem:
Po+1 arg min
(D.1) Dr(p.P))
(1)
pEPa
This formulation reflects the trade-off between exploiting current loss information (via the linear term) and staying close to the previous distribution (via the Bregman divergence).
In practice, the update of equation is often implemented in two steps for computational convenience:
{ (I.. + Dp(D.P)).
Po+1 arg min
pERd
Pr+1 arg min Dp(p.Pr+1)
PEPs
Here, the first slep performs an unconstrained update in the dual space defined by F, while the second step projects the intermediate point back onto the simplex, ensuring that the updated distribution is a valid probability vector. The choice of regularizer F' determines the specific algorithm instance; it typically includes a learning rate parameter that controls the step size and will be specified in subsequent sections.
Finally, in the bandit setting, since the learner does not observe the full loss vector l but only the loss of the selected arm, the true loss must be replaced with an appropriate unbiased estimator. This ensures that OMD remains applicable even with partial feedback.
3.3 Master-Base OMD
We employ OMD framework with a hierarchical structure consisting of a master and multiple bases. We first present simple Master-Base OMD algorithm (Algorithm D that employs the negative entropy regularizer:
F,(()) = (1/n) Σ log(()))() -p))), 1=1
where p E Rd, p(i) denotes the i-index entry for p. and y is a learning rate. This regularizer is commonly used adversarial bandit algorithms, including the well-known EXP3 algorithm (Auer et al. 2002).
In Algorithm D at each round t, the master algorithm selects base h, E H. according to probability distribution pt- The selected base by then chooses
a, [K] using its internal distribution Pt.
3

---

Published in Transactions on Machine Learning Research (10/2025)
and observes the incurred loss 4(a)). From this partial feedback, construct unbiased estimators: (1))) estimates the loss for each base h E H, and (a(a) estimates the loss for each arm E [K] under base h. Using these estimators, the algorithm updates both the master distribution P++1 and each base's distribution Pt+1, via OMD.
To control variance in the estimator (ç(h)= = (h (h). we define the master's update domain as This clipping ensures that each base is
clipped probability simplex Pūt Pa [a, 11 for some selected with non-negligible probability, preventing high variance in the importance-weightted loss estimates. Within this domain, the update of pc+1 is then computed using the negative entropy regularizer with learning rate
Each base E H maintains its own arm selection distribution PrA- The update for this distribution is also based on the negative entropy regularizer but with a learning rate that adapts to the candidate switch parameter h:
h/22
{(h) = K1/372/5
This choice of E(h) helps base h adapt to environments with up to h switches in the best arm sequence. The domain for updating Pt, is Pxx Px n [8, 1jK for B > 0. Unlike a, which controls variance in master-level estimation, 3 acts as a regularization mechanism to stabilize learning under the switching best arms in hindsight.
Algorithm Master-base OMD
Input: T, K, H.
Initialization: a = K1/3 Pi,x 1/K for h E H and a [K].
3 1/(T) 1/VTH, g(h) = 1/2 N1/2/(X//7T11)) pI(M) = 1/H,
for 1..., do
Seleet base and arm:
Draw h4 probabilities {pi(k))Ee.
Draw 0t,b; probabilities (pt, [a]]]
Pull = ar,,, and Receive ((ar,))) E [0, 1].
Obtain loss estimators:
((h)) = 4(0c,))) and 44(h) for h E (hr). (h()
H,,, (ar,n.) P,,,, (a.,..) and Ci,, (a) 0 for h E H/(he),
Update distributions:
P+11 arg minpepy Pi, (p, () + DF, P:)
P1+1 = arg min pepg (p. ((,b) + Dreus (p, Pr.)) for all h E H
end for
Now we provide regret bound for the algorithm in the following theorem.
Theorem 3.1. For any switch number
[T 1}, Algoritlum achieves a regret bound of
Rs(T) = 0(5
Proof Skelch. Here, we provide proof sketch, and the full version is provided in Appendix A.1
In our proof, we decompose the regret into two parts: one the regret from the master selecting a base at each time, and the other the regret from the base selecting an arm at each time. Let t, be the time when the s-th switch of the best arm happens and (s+1 T, 1. Also let 1 tg Ts. For any t, for

---

Published in Transactions on Machine Learning Research (10/2025)
all S], the S-switch regret can be expressed as
l++1-1 -1
Rs(T)
E
(aaa)
-
min E
le(kss
t=1
==0
t=
T Σ Bl(a,
T Σ [c(aent)]]]
T
441-1 -1
Σ E (a
min Σ
(2)
8 k.E
in which the first two terms are closely related with the regret from the master algorithu against the near optimal base ht, and the remaining terms related with the regret from ht base algorithm against the best arms in hindsight. We note that the algorithm does not need to know ht in prior and ht is brought here only for regret analysis.
Regret from the near-optimal base. First we provide a bound for the following regret from base ht:
s
f-1-1
Σ E [4((a))))
Σ
min K
Σ 4(kk),
where the first term is the loss from the basc and the second one is the loss from the optimal arm in hindsight. 26+1-1 ((k) and ej denole the unit vector with 1 at j-index and at the rest of
Let ky = arg minke[K] Ees, K indices. Then, we have
Σ B [(b2]] S 3T,(K 1) max E
Σ (Pe.. p. p
pEpO
where the first term in the last inequality is obtained from the clipped domain P and the second term is obtained from the unbiased estimator (", such that x, [ = E[4[F-1]] where Fi-1 denotes the natural filtration generated by the history up to round 1. We can observe that the clipped domain controls the distance between the initial distribution at t, and the best arm unit vector for the time steps over [t,, 1]. Let
PL+1AT = arg min (p. K,,))) + Deant (p. Pt..))
PERK
Then, by solving the optimization problem, for all & E [K] we can obtain
1et (k) Pr,nt (x)p (k)).
For the second term of the last inequality in equation 3 we have for any p E Pk:
1-41-1
Σ
(P. ps (1 & DEgan, (p. Pt,,,t +
Σ
Dr (Pr, Pc+1,)))
(4)
The first term is for the initial point diameter at time ly and the second term is for the divergence of the updated policy, Using the definition of the Bregman divergence and the fact that Pt (k) 2 8, the initial point diameter term can be shown to be bounded as follows:
DF (t,. log(1/3)
(5)
E(ht)
Next, for the updated policy divergence term, using PL41 (k) = Pt,tt (k) " (k)) for all lo E [K]. we have
E(h))KT
E Drcat, (P .et.,.t
(6)
2a
5

---

Published in Transactions on Machine Learning Research (10/2025)
Then from equation
8 equation
equation
5
and equation 6 by summing up [S]. we have
8
4+111
lekk)) s BT(K - 1) (log(1/3)
E(ht) + 5(h)) KTT
Σ
E [[((ae11]]]
min [
(7)
2a
==0
1=
Next, we provide bound for the following regret from the master:
T
Σ I. [1(CLt)))
Let Pi+1 = arg min "ER" (p. ()) + Dr. (P. Pt) and ea, denote the unit vector with 1 at base h-index and 0 at the rest of H - indices. For ease of presentation, we define (h) L((a,,)) Then, we have
Σ E [e(aon)))) - [e(a,,)))]] s aaT(H -
max E PEP
Σ (p. p. 4
(8)
Regret from the master. For bounding the second term in equation use the following: for any p E Pn
which arises from the master,
T
Σ
Pt p. 4 S F((p) - F((P:) +
Σ Dr, (Pr. P.+1).
(9)
1=1
From equation g and equation 9
we have
T
Σ (a(,)))
Σ ((),
T
- aT' 1) + max E
( - F.(p)) +
Σ
Dr, (P+ P141)
PEPR
t=1
S aT - 1) + log(H)
nTH
(10)
2
Overall Regret. Therefore, putting equation 2
equation 7
and equation 10
altogether, we have
T Rs(T) Σ E (a,)) Σ
8
T
min 1sk
Σ
le(ks)
==0
t=T
SoTH + log(H))
TTH
S Slog(1/B) ((T))T
+
+ 3TKK 1)+
"
2
E(hi)
2xx
= =0(55/222/3
where (133/( B 1/KKT), = 1/VTH, E(ht) // (X213//333/333) ht O(S), and H- log(T). This completes the proof.
Compared to the prior parameter-free algorithm based on the Bandit-over-Bandi (BOB) approach (Cheung et al. 2019), which incurs suboptimal dependence the time horizon T, specifically, regret term of order 7/4 our algorithm achieves a tighter regret bound in terms of T. In particular, when T = k44. Algorithm achieves a tighter regret bound than that of BOB.
However, the regret bound achieved by Algorithm 1 remains of order O(T2/3), rather than the optimal O(VT), due to the high variance in the loss estimators. This variance ariscs from the double sampling process first selecting base, then an arm at each round. To address this issue, we next propose an improved algorithm that leverages adaptive learning rates to better control the variance of the estimators.

---

Published in Transactions on Machine Learning Research (10/2025)
3.4 Master-Bass OMD with Adaptive Learning Rates
We now propose Algorithm 2 which incorporates adaplive learning rales to better control the variance of the loss estimators. We begin by describing the base algorithm. Each base employs the negative entropy regularizer, but with a timo-varying adaptíve learning rate (eh),, defined as:
1 E log p(i)). (((h)
(e,()(()))
where p Rd is probability distribution over arms. The learning rate (h) is dynamically adjusted each round & based on the variance of the loss estimators, and is given by:
(( = (k)()))
where (h) is variance threshold term that will be defined later. This formulation ensures that when the variance of the estimators is small, a larger learning rate is used allowing for more aggressive updates while high variance nalurally leads to more conservalive updates. Notably, this adaplive base algorithm is effec- tively combined with the master employing log-bay barrier regularization to control the regret due to variance, resulting oquation 15 which introduces novel integration of adaptive learning and log- barrierrer regular- ization for variance control.
For the master algorithm, inspired by the approach in Agarwal et al. (2017). employ log-barrier regularizer with increasing learning rates. This design introduces a negative bias term that effectively offsets the variance arising from the base algorithms, particularly by addressing the worst-case scenario in terms of the variance threshold (e(t)). The log-barrier regularizer is defined as:
d log p(i) Gn (p) Σ
Mc (i(
where E Pa is the master distribution, and 7 = ( (d))) denotes the vector of learning rates at time We describe the learning rate update procedures for both the master and the base algorithms in Algorithm 2 all other components remain identical to those Algorithm [ The variance of the loss estimator (h) 14 1,(a(_,,))((444 = hh/pe+1 (h) for base h is given by 1/Pt+1 (h). this variance excoods the threshold p. (h), i.e., 1/PL+1 (h) > pc(h), the master increases the learning rate as: Mh41 (h) = (y)(h)) for some fixed 7 > 1. Simultaneously, the variance threshold is updated to: ptt1 (h) 2/Pr41 which is also used to adaptively tune the basc learning rate (h) as described carlier. If the variance does not exceed the threshold, both (hh))) and Pe(h) remain unchanged from the previous time step.
In the following theorem, we provide a regret bound of Algorithm 2 Theorem 3.2. For any switch ramber [T 1] and any p z ElpT (ht)), Algorithm 2 achieves regret bound of
Rs(T) = min (
/SKTT, /SKTp,SVKT]
Proof Sketch. Here, we provide a proof sketch, and the full version provided in Appendix A.2 As in the Theorem 3.11] we decompose the regret into two parts: one the regret from the master selecting a base each time, and the other is the regret from the base selecting arm at each time. Let t, be the time when the 3-th switch of the best arm happens and fs+1 all s E S), the S-switch regret can be expressed as
T. to 1. Also let t2+1 to T.. For any t, for
T
s Σ
1
Rs(7) = E (a())
Σ
-
min
Σ le(ks)
[KE(
1=1
==0
==
T
(+11-
Σ 1=1
E Ue (ar,
Σ [(((oentt]]
Σ E [a
Σ
min
Σ ((k.)).
(11)
k.E[K]
1=1
t=

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm 2 Master-base OMD with adaptive learning rates
Input: T, K, H.
Initialization: a = 1/ = 1/(TK), 7 = C 7= n= P1 = 2H, m1)))))))))))))))))) = P1 = 1/H,
P1,A 1/K for h E H and a [K].
for t= - ...., do
Select base and arm:
Draw h ~ probabilities (p((k))EH.
Draw 0thbe probabilities (pt,s, [a][]]
Pull 0r = dr,,, and Receive (((a,,,)) E [0, 1].
Update loss estimators:
(e(ae,re) and (((h) O for h E { (((h)) pr(l)))
M,,, (ar,h, Ps,n, (ar,,)
(,(h)) and ( = for E H/(h), [K]/(am).)
Update distributions:
Po+1 arg pe (p, 4) + Dam (p.P.)
P141.1 arg min PEP (p. (m)) + Dre,cn (p. PL,n) for h H
Update learning rates:
For h E H
If
Pe+ilh] (h),, then
2 (h) p. (h) (h) (h). Else, (h+1(h) = (h)),, (h) = (h).
end for
Regret from the near-optimal base.
First we provide a bound for the following regret from base ht,
From equation 3
can obtain
4-1-1
64111
Σ
B[((ar,)-)]
Σ
ST,
S
E
Σ t=t.
(Pe.
(12)
pEpd
Then for the second term of the last inequality in equation 12 Lemma 3.3. For any E Pk we can show that
we provide the following lemma.
f-1-1
KTpr(ht)
T, 2
SK pr pr
E
Prctt
pi E
2 2lgg
+
hi
Then from equation and Lemma 3.3
we have
T T+t1-1
KT
Σ E [c(aa.)))]
Σ
min Igk
4(ke)
- -1) + 25 loggg(1/3)
TSKpr(hl)
hl
1=1
t=
(13)
Regret from the master. Next, we provide bound for the regret from the master in the following:
H log(T)) E E( 500 t=1
pr(ht) 40y log T aT - 1).
+ Tn) (
EE
(14)
"
The negative bias term in equation 14 derived from the log-barrier regularizer and increasing learning rates ny (h). This term is critical to bound the worst case regret which will be shown soon. Also, H log(T) is obtained from H log(1 (HH)))/ considering the clipped domain.
8

---

Published in Transactions on Machine Learning Research (10/2025)
Overall Regret.
Then, putting equation 11
equation 13 and equation 14 altogether, we have
T
g
T-1-1
((kk))) - Ō ( ( (SsTTr(mi)
- EE VT( 400 (0vHlog(T)
Rs(T)= [ll(a
Σ
min Isk.
(15)
K
==0
Then, we can obtain
(T) (min (
where D(SVKT) is obtained from the worst case of pr The worst case can be found by considering a maximum value the concave bound of the last equality equation 15 with variable pr(h") ) > 0 such that pr(ht) (SS). This concludes the proof.
We now provide comparison of regret bounds with an existing approach. our regret bound depends on p. which captures the variance of the loss estimators (h") over the time horizon [T]. While the bound is vartance-dependentt, it is noteworthy that in the worst case, it is always upper bounded by ((SVKT). Importantly, Algorithm 2 achieves tight dependence of ((VT) in the regret bound, in contrast to Algo- rithm and BOB (Cheung et al. 2019 Foster et al., 2020), which incur suboptimal 722/3 and T3/4 term, respectively. Therefore, when T is sufficiently large, Algorithm 2 yields a strictly better regret guarantee than Algorithm and BOB. We also note that the variance term p is commonly observed Luo al. (2022) but we control the worst case without information of using an adaptive learning rate.
Remark 3.4. Since incorporate pe(h) into the adaptive learning rate for each base h Ex(h) ph))T,((h), we can optimize the regret bound to depend Notably, this adaptive base algorithm is effectively combined with the master employing log-barrier regu- larization Agarwal et al. (2017) to control the regret due to variance, resulting /Spr(hl) - PT (ht). This integration is the main reason why Algorillo 2 can achieve a order of VT, even in the worst case, without the knowledge of S.
v Vpr(h)), as demonstrated in Lemma 3.3.
Remark 3.5. Our algorithms are designed to perform well across different regimes, particularly with re- while
spect to T and S. To recall the regret bounds, Algorithm achieves a regret of 0(5)/2 Algorithm 2 achieves Ómiin VSKTp, SVKT)). This indicates that Algorithm 1 is advantageous when S is large, whereas Algorillem is preferable for larger T due to ils use of an adaplive learning rale that accounts for the voriance of the loss estimator.
Remark 3.6 (Implementation). For implementation of our algoritlmss, we briefly describe how to update the policy P. using OMD. Let [a) denole loss estimator for (s(a) for action [d] and E [T'. For the negative-entropy regularizer, by solving the optimization in equation 1 (see Lattimore & Szepesvári we obtain
2020
exp
-1) 1 (T)())
pr(a)
EsEl exp -17 (
For the log-barrier regularizer, the solution is pi(a) = (n ( +) -)-1, where Z is the normalization constont ensuring Eg (r(a) 1 Luo et al. 2022). When the feasible set is the clipped simplex pefd {p E Da: p(a) 2 e/d] for 0 < < computationally simple way to enforce feasibility is to mìx with the uniform distribution:
(a(a) + (1-c)p(a)) + c/d for all E [d].
This "uniform-minne trick, following Auer et al. (2002), guarantees pt E pp//d to ensure a bounded vari- ance of the loss estimator. We emphasize that this is an implementation convenience rather than the exact Bregman projection onlo pe/d, rigorous regrel analysis under this specific implementation is left for fulure work.
Remark 3.7. The regret bounds in Theorems 3. and 3.2 also eztend to non-stationary stochastic bandit problems with unknown switching parameters, where the reward distributions may change over time. This generalization possible because the adversarial bandit setting encompasses the stochastic setting as a special case.
9

---

Published in Transactions on Machine Learning Research (10/2025)
4 Conclusion
In this paper, studied the adversarial bandit problem with S-switch regret, where the agent competes against any sequence of arms that switches at most S times, without prior knowledge of S. To address this challenge, we proposed two algorithms based on the master-base framework integrated with the Online Mirror Descent (OMD) method.
First, we introduced Algorithm | which employs a simple OMD updale with a fixed learning rale and achieves a regret bound of Algorithm which incorporates adaptive learning rates to control the variance of the loss estimators.
To further improve performance with respect I, we proposed This leads to an improved regret bound of estimators associated with the near-optimal base,
where captures the variance of the
Acknowledgements
We thank the Action Editor and the reviewers for their constructive and insightfull feedback. J. Kim acknowl- edges the support of ANR through the PEPR IA FOUNDRY project A.NR-23-PELA-0000) and the Doom project (ANR-23-CF233-00) as well as the ERC through the Ocean project (BRCC2202-5G--OCFAN 101071601).
References
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert Schapire. Corralling band of bandit algorithms. In Conference Learning Theory, pp. 12-38. PMLR, 2017.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48 77, 2002.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory, pp. 138-158, 2019.
Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred K Warmuth. How use expert advice. Journal of the ACM (JACM), 44(3): 1997.
Yifang Chen, Chung-Wai Wei Lee, Haipeng Luo, and Chen- Yu Wei. A new algorithm for non-stationary con- textual bandits: Efficient, optimal and parameter-freo. In Conference on Learning Theory, pp. 696-726.
PMLR, 2019.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Learning to optimize under non-stationarity. The 22nd International Conference Artificial Intelligence and Statistics, pp. 1079-1087, 2019.
Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In International Conference on Machine Learning, pp. 1405-1411, 2015.
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Open problem: Model selection for contextual bandits. In Conference on Learning Theory, pp. 3842 3846. PMLR, 2020.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for non-stationary bandit, problems, 2008.
Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Artificial Intelligence and Statistics, pp. 943 951. PMLR, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Haipeng Luo, Mengxiao Zhang, Peng Zhao, and Zhi-Hua Zhou. Corralling larger band of bandits: A case study switching regret for linear bandits. Xrxiv preprint arXiv:2202.06151, 2022.
10

---

Published in Transactions on Machine Learning Research (10/2025)
Aldo Pacchiano, My Phan, Yasin Abbasi- Yadkkr,, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. arxiv preprint or 2d:2003.01704, 2020.
Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary environments. In Advances in Neural Information Processing Systems, pp. 12017-12026, 2019.
Joe Suk and Samory Kpotufe. Tracking most significant arm switches in bandits. In Conference on Learning Theory, pp. 2160 2182. PMLR, 2022.
A
Appendix
A.1 Proof of Theorem 3.1
Let la be the time when the s-th switch of the best arm happens and 1s+1 - 1 = T, 4 = 1. Also let
fs+1 - to = Tg. For any to for all E S], the S-switch regret can be expressed as
4+--1
Rs(T) = Σ E (a())) - Σ
min Σ le(ks))
E
f+-11
Σ E Bl(ann
- Σ [e(aen))))]
Σ E [m(a)))]
min Σ
Σ ((kk)) t=t.
(16)
K.E(K]
in which the first two terms are closely related with the regret from the master algorithm against the near optimal base ht, and the remaining terms are related with the regret from ht base algorithm against the best arms in hindsight. We note that the algorithm does not need to know ht in prior and ht brought here only for regret analysis.
First provide bound for the following regret from base ht:
T
le-1-1
E [[(aa,N1]]]
Σ
min k.
4(ss).
kKE(K]
t=t,
Let kg arg minke[]] Ees, (kk) and ejæ denote the unit vector with 1 j-index and at the rest of K indices. Then, have
(((a,)))))) - (k(k))))
Σ tst,
(Pent - Cky ex.
f-11-1
S max E pEp
Σ (p
eky Ki
Σ
(p p.4)
< (K.(K- 1) max E
Σ
(Pe. P, (ii
(17)
pEp
where the first term the last inequality obtained from the clipped domain P and the second term is obtained from the unbiased estimator E such that E[t B[4[F.-]] where Fi- denotes the natural filtration generated by the history up to round 1 1. We observe that the clipped domain
11

---

Published in Transactions on Machine Learning Research (10/2025)
controls the distance between the initial distribution at t, and the best arm unit vector for the time steps over [1,,4+1 1]. Let
PE+IAI
arg ( (,, ( + Drsat (p. PL,N)).
PERK
Then, by solving the optimization problem, for all [K] we can obtain
P (k) Pc, (k) exp( (epp-=((1) (000(-E(MMM,r (k)).
For the second term of the last inequality in equation 17 we provide lemma in the following.
Lemma A.1 (Theorem 28.4 and Eq. 28.11 in Lattimore Szepesvári (0200). For any p P have
PL. p. s Drgat, (p, P(,,)))
Draant (Pent P(41.))
Proof. For completeness, provide proof for this lemma. Fix any p Pk. By the first-order optimality condition of the unconstrained mirror-descent step,
(T V VFgOn)((PELLN) (Pe+1,)) VFECN)(PLL)) p- PEtLNN) 2 O.
This gives
(P+LIAt P. (,,,, S ( (VPean)(PeHua))) (Peat)(Pratt) Pot1.)))
Using the definition of Bregman divergence,
(V Fggan
PI+1M)) = Dreat, (p.Pt.t)--Dpp (p, P1+11))) -DF Fecnt (pe+1.0, Pc,b))
we obtain
(P41,,t p, W S Decent, (p.Pr,tt) - DE Decnt, (p.P.+1.N)) - Decntt (Pe41,0,,P,.t)) (18)
We now decompose
(pr.tt p. p.(" (Pr,ht Pe4I, (P:tI.--...
- ).
Combining with equation yields
(Pi.a- P, M.a) S (Prttt PP41 Mnat Dreat (P.,1))sP...)) DFEW (p. Pr,t)) DF (p, 1et,11))))
(19)
Recall the unconstrained mirror step
P = arg min u)) + Decatt (u, Pe a
By the first-order optimality condition,
En + Pe (P V Pe(no)(Pr.a)) 0.
(20)
Taking the inner product of equation (P.M PL41, K
20 with Ptbt Pi+1.t yields
(PE. PLtLAt V (P,K)) V. (Penr))))))))))))
(21)
From the above, by using the definition of Bregman divergences, we have
(p Pet1,tt, 1 (Pi,tt - Pi41,tt, (Fgan)(PENtt) VFgUn)
DFeatt (Pe41,t .P,at) + DF Fecn, (Pr,t, P.+1,1)) Drewn 1, (P--1AttPPPaatt
S Dreat, (Pe41,ht + Decat (ett,)))
(22)
12

---

Published in Transactions on Machine Learning Research (10/2025)
Then from equation 19 and equation 22 we have
(Pr (,,) I DF Fecnt (c,t)) Daunt (p.P.41,)) + Dr Fect, (Pi,t Pct1,6)).
Summing over to...., to+1 - gives telescoping series in the middle terms:
1 (Lit Ds w. S seat, (p, Pt..ht) Peatt (t.t Σ
Desat (Pi,tt P141,6)).
Since De (o.Pe+t,tt) 2 by the nonnegativity of Bregman divergences, the term can be safely dropped. Therefore,
4
Σ
(Pe.t - p. k,,) S Decntt (p.P..N)) +
DF (PAA..P-MM))
which concludes the proof.
In Lemma A.1 the first term is for the initial point diameter at time t, and the second term is for the divergence of the updated policy. Using the definition of the Bregman divergence and the fact that Pt,,tt (k) 2 3, the initial point diameter term can be shown to be bounded as follows:
1
Dr (p. Pt,ttt) S
Σ
p(k)/oo (k))
E(hi)
ME[[K]
log(1/3)
(23)
<(hT)
Next, for the updated policy divergence term, using Pct1,N1 (k) = Pe,tt exp(= (000--g(())) (1:) for all &s E [K].
we have
Dreatty (Pr,tt PenLAt]
E
PeatyPeas (1)) (oxp( (cxp(-E(h)))),, (x:) + E(h)) (Kt)
E
[E(h))
Pe.tt (N)) (162)
E
E(ht)
E(hT)KT.
E
(24)
2pt(h))
2a
where the first inequality comes from exp(-x) S 1 x²/2 / for all x 2 O, the second inequality comes from | (k)² Pi,tt (k),,p(h")) < 1/(p( PP,, (k)), and the last inequality is obtained from (c(h)) 2 a from the clipped domain. We can observe that the clipped domain controls the variance of estimators. Then
from equation 17 Lemma A.1 equation 23 and equation 24 by summing up over [S], we have
$
611-1
Slog(1/3) E(ht)
+ {(h))
min K,E[K]
Σ /=
l(kk)) S (T(K - 1)+ -T)
(25)
2a
Next, we provide bound for the following regret from the master:
T
E [e((ae))))]
Σ E [[(a,,)t))
13

---

Published in Transactions on Machine Learning Research (10/2025)
Let Pi+1 arg PER" (p. [1) Dr,, (p. Pı) and Cn, denote the unit vector with 1 at base h-index and 0 the rest of H 1 indices. For ease of presentation, we define (h) = le (a(,,)) for [M]] Then, we have
E [e((a)h)) [((aghtt]]
IE (pp H, 4>]
Ent H 4) + Σ (p. p.4))
max PEP
T
I aT - 1) + max E
Σ (p. - p,
(26)
PEP
For bounding the second term in equation 26
we use the following lemma.
Lemma A.2 (Theorem 28.4 and Eq. 28. in Lattimore Szepesvári (0200). ) For any p E Pi we have
E
Σ
Pt p, bb)
< E
Dr, (P. Dr.
Dr, (P.: (PoPPt
Proof. For completeness, provide proof for this lemma. Fix any p Pg- By the first-order optimality condition of the unconstrained mirror-descent step,
(1 (P,())))) VFr(P:), p P--p--pp- -P-1) 20
This gives
P p.4) & (VF((P+1)) - VF,(pi); - -P-+1).
Using the three-point identity for Bregman divergences,
(VF,(P--)) (F,(P:), p P+t1) Dr, (p.p.) Dr, (p.P.t)) Dr, (Pe+1.P)),
we oblain
(p++1 - p, S Dr, (p.Pt) - Dr, (c.) - Dr, (Pe+1,)))))
(27)
We now decompose
(p: P--p, p,()) = (p: - P141, + (pit1 - -,,
Combining with equation 27 yields
- (p- < (p: P++1, DE, (p++1.P)) Dr, (p. p:) DF, Pt+1)
(28)
Recall the unconstrained mirror step
p arg min (K, (4,u) + Dr, (u.p)).
By the first-order optimality condition,
+ VFF (P, 0.
(29)
Taking the inner product of equation
29 with Pt Pt+1 yields
(p. P1+1. 4) (p. - Pi+1, (F, (P.())))))
(30)
From the above, by using the definition of Bregman divergences, we have
(p: P1t1. 13) (p. - Pit1, (F,(P:) (F,((++1)
DDF, DF Pt) Dr, (pr, DF, (pr+1: P.+1)
< DE, (pt+1. Pt) Dr, P:41).
(31)
14

---

Published in Transactions on Machine Learning Research (10/2025)
Then from equation 28 and equation 31 we have
(p. p.4) (p.pe) DE, (p. Pc+1) DE, (Pe. P(+1).
Summing over t = I,.... T gives telescoping series in the middle terms:
T
Σ
pr p. < (r,(p.))) Dr, (p. Dr, (pc.Pett).
Since Pr.(p,PT+)) 2 0 by the nonnegativity of Bregman divergences, the term can be safely dropped. Therefore,
Σ Pt p, S (p. +
Dr, (pe. Pc-1),
t=1
which concludes the proof with E T (=1 (p: p, 41 = E E (pr p.
From equation 26 and Lemma A.2 we have
T Σ
(a(,t))))))
E [((()))))
T
$ aT - -1) 1)+ + max E
Dr, (p.pi) +
Σ t=1
Dr, (pr, Pita))
pEPn
S aH - + log(H)
nTH
(32)
2
where the last inequality is obtained from the fact that
DF, (p. = 1 Σ
p(h) log( p(h)) (h)
log H)
11 he(m)
and from
E
Σ 1=1
DF, (p., P(+1)
=E (1/m)
Σ Σ p((t)(exp(-n(())) + (27((1))
1=1 he[H]
!
(h))
7TH
2
2
t=1
AE(M)
Therefore, putting equation
16 equation
25 and equation 32
altogether, we have
T
5
T--1-1
Rs(T) Σ E (ar))
Σ
min ISkSs
Σ l(kk)
S=0
T=
STT + log(H) H)
1TH 2
S Slog(1/B)
E(h))T
+
+ ST 1) +
7
E(hl)
2x
=
where //33/T1//3//33 8 1/KT)), n 1/VTH, E(ht) (0t)1//(x3/33//3))) ht =((S). and H log(T)). This concludes the proof.
15

---

Published in Transactions on Machine Learning Research (10/2025)
A.2 Proof of Theorem 3.2
Let is be the time when the s-th switch of the best happens and 1s+1
T, to 1. Also let
fs+1 to To. For any to for all S], the S-switch regret can be expressed
f-1-1
Rs(T) =
Σ E
[a)a)
-
Σ
min
Σ
le(ke)
ELE
1=1
Am
T
T
641-1
=
Σ
E (e(a,,))))
Σ [c((aaat]]
Σ
E Be (a
min - -
Σ tmt,
le(kss)
(33)
k.E[K]
==0
in which the first two terms are closely related with the regret from the master algorithm against the near optimal base h! and the remaining terms related with the regret from ht base algorithm against the best arms in hindsight.
First we provide bound for the following regret from base ht From equation 17 we can obtain
641-1
Tx41
Σ E [[(a))))]]
min k
Σ
4(kss) S BT,K + max PEP
Σ
(Pe - p, (.t
(34)
Then for the second term of the last inequality in equation Lemma A.3 (Restatement of Lemma 3.3 For any E Px we can show that
we provide a following lemma.
6+11
(Tpr(h)) ht
T.
SK pr (ht)
E (Pnn p. mi1) < E 2l0g(1/3))
+
2
T
Proof. For ease of presentation, define the negative entropy regularizer without learning rate
K
F(p) = Σ log p()))
and define learning rate Sohh)) = xc. From the first-order optimality condition for 1 and using the definition the Bregman divergence,
P1t1. P. (.
$ (itt) (p PELIAT. VF((+41,))) - VF((.,))
Ec(ti) (De(p.PeNt) Dr(p. PEpI,))) Dr(PetLnts Pr.t))
(35)
Also, we have
(P.M - P141. ('
(PEN PELLA VF(P..)) V (F(++111))
E((1T)
1
(Dr(PELLM) Pant) + Dr(PENt, P(.L,)) - Dr (P Pc41m))
(((F))
1
(Dr(PeLLMS PLNT) + Dr(Pans P()L,)))-
(36)
16

---

Published in Transactions on Machine Learning Research (10/2025)
Then, we can obtain
411-1
Σ
p. ( S
Σ
(Pent Pe-I,Nt:
61121
Σ
(Dr(p,Pett) - DD((: P(41,1))
DF (P
Ee(ht)
t=
1111-1
811-1
Σ
(Pent
P +
Σ DD(P.PeNt)
1
E((1T)
(
1=
10,+1
611-1
DF (p. Pranh)) 11
Dr(p, Pho
DF (P(
(httt
Ee(ht)
111-1
f-1-1
(PeM P (it 1og(118))
Σ
Ee(ht)
Se-1(hi)
10,+1
let1-1
DF(p, Pty,ni) 11))
Dr(p, Pt. i.11)
Σ
DF (P(ttti, Pa,)))
(n,th)
Ee(ht)
t
1og(1/3)
4-1-1
DrlPaniPPtaL Ec(ht)
2
+
(hh)
KT pr = (1)
b11-1
Dr(Pe,tt P1+1.11)
+
(37)
h
Ee(ht)
where the first incquality is obtained from equation 35 the second last inequality obtained from Dy(p. P..At) < log(1/3) and 1/Ec(ht) 2 1/tr-1(ht) from non-dccreasing pe(ht), and the last incquality is obtained from equation 36 (r (p. S log(1/3), and (ht) 2 (r')) for s E [2] from non-decreasing (ht).
For the second term in the last inequality in equation 37 using Pet1, (k) Pe,tt (k) Sep(-E(ht)) (k)) for
all k E [K], have
E
Dr Dr (P P Po-1
l - t= 1=1
K
E
1
(cxp(=E(hh))())
(hi)
-1 E6hh
f+t1-1 K
(e(ht)
E
Pe Pe (k) (x:)2
2
bm Am
(ht)
E
(ht)
f K
Σ
E
2
1= k=1
1 K
i
het (ctt)
E
2
KT
1 k=1
ht E.
[PT
(12)1/22
<T.
(38)
T
2
17

---

Published in Transactions on Machine Learning Research (10/2025)
where the first incquality comes from exp(-z) -1-x+ for all x 2 the second inequality comes from BlV (b)² Pr, pk),,t(h")) (h])] s (P)e(h))) (k)), and the third inequality is obtained from 1/pi(h)) pr(ht)
0
Then from equation
34 and Lemma
A.3
wc have
T
T
Σ E [(((a))))]]
Σ
min
(k(ss)
Isk, SK
t=f.
KTpp(htt ht
1
25 log loggoo1//) (1/B)) S 1)+
+ TSKpr(ht)
(39)
2
Next, we provide a bound for the regret from the master in the following lemma. Lemma A.4 (Lemma 13 in Agarwal et al. (2017)).
E [a(,ha)))) - Σ E (4( 0 Hlog(() + Inn
pr(ht) 40n log T
- E
+aT(H - 1).
17
Proof. For ease of presentation, define (1h = 1 (ar,t) for h E [H]. Then
E (P,
Cbt, 4>
T
T
< max E pEP H
Σ p
ext H. 1.) + > Pt - p, 2,)
1=1
< aT - 1) + max E pEPo it
> Pt p, 4
(40)
aT ( - 1)
max E pEP
Pt p, (,)
(41)
Bounding the mirror-descent term. We next bound E E (Pr - p. 4 using the OMD analysis of Agarwal et al. (2017 Lemma 13). The master update
P+t = arg min { (p, () + Don, (p, p.) PEP9
where -M I standard mirror-descent. inequality, for any p E Pa
h= nichy p(h) log and Do is the corresponding Bregman divergence. Applying the
H
(p. pe-p.ho -. b)) s Do., (p.p.) DG., (p. P+41 +
Σ
p.)
(42)
Summing over 1,...... T gives
H
Σ (p. p.4) < Don (p.P.) Dam, (p. Pet1))
Σ
Σ n (h)))
(43)
Bounding the potential differences. We first control the telescoping term in equation 13 Since
18

---

Published in Transactions on Machine Learning Research (10/2025)
DGm (++)) 2 0 and the learning rates (h)h) are nondecreasing in for each h, we have
T Dam (D.P:)- Dan (D. (ct1) < Dam (p.Pi)
T-1 H
+
(x( h
p(h) (t+I
(44)
(e+1
where h(y) y --1- logy 0 is the log-barrier Bregman core. For the initial term, using that Gm is (scaled) negative entropy the clipped simplex Pa with 1/(HH), obtain the standard bound
o H (Hoo)11a)) o( H log T "
max DG. (P.Pi) PEPA
(45)
7
pa ( Pc()). then (h) Pe- and 1h-1(h) (h) mc(h) with y = e 2/loo while otherwise 1 Th (h). As
Adaptive-rate gain (negative correction). By the adaptive schodule in Algorithm 2 if 1
in AAarral et al. 2017 Lemma 13), this implies that whenever the coordinate ht is assigned too little probability, the factor (141((tt) me(htt) is negative of order - 11/(1llog T), and it multiplics the nonnegative
barrier increment h p(hl) yields
where h(y) = y log(y). Aggregating these events over t= 1,....
pt41(ht)
pr pr(h))
ΣΣ
h
p(h) (())(A)
(((A)) 1 (
(46)
40 log
where (T(! is the final density parameter maintained by the schedule. Combining equation 44 Ptt we obtain
equation
45
and equation 46 and for
T
H HlggT)
pr(ht) 40 T
DGn (p.P.) DGn (p. (p.P.t)) $ O
(47)
Bounding the variance term. It remains bound Σt= Σ ne P (())) Recall that ((h) e (h)]) and only the sampled coordinate be nonzero. Since each increase least doubles the density pe(h) and pc(h) < 2TH from (h) 2 = 1/TTH, the number of entire updates for each h is at most C (HT) for a constant C > 0. This implies that (h) S (h) I Ci log(2HT) S ne for a constant
C2 > 0. Therefore
Σ po ((h < (hr(h) = O(Tn).
(48)
Putting the pieces together. Apply equation 47 and equation
48 to equation
43
then maximize over
p E Pg and lake expectations. Combining with equation 41 yields
T Σ Bll(aa)) - EB(h(aem))
T s o log ) + O(TT) - E
pT(h!)
+ aT(H- -
40 loglog'
which is the desired bound.
The negative bias term Lemma A.4 derived from the log-barricr regularizer and incrcasing learning rates (h). This term is critical to bound the worst case regret which will be shown soon. Also, H Iog(T) /n is obtained from H log(1/ (HH)))/ considering the clipped domain. Then, putting equation 33 and Lemmas A.3
19

---

Published in Transactions on Machine Learning Research (10/2025)
and A.4 altogether, we have
T
T
Rs(T)
Σ
R [l((a:)]
-
Σ
min 1skss
Σ
(ks)
s=0
t=I.
H logg T
pr(ttt
0
+T' -
11
40n log T
aT - 1) + (T(K
KTpr(h")
+
25 1og(1/8))
2V SKT
h7
PT(
= = (R
-B
(49)
40VH log(T))
where a = 1/(TH), 8 1/(TK), n /H/T, H1 log((),, and at = OSS). Then we can obtain
Rs(T)= = (min (SKTT
where Ö(Sv KT) is obtained from the worst case of (h!).. The worst case can be found by considering a maximum value the concave bound of the last equality equation 49 with variable pr(h²) > 0 such that pr(ht) Ō(S). This concludes the proof.
20


Reviews:
[{"review_id": "zUnfz6p2Lz", "reviewer": "Reviewer_zzRq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pro:\n1. The paper roughly looks good and has some new result.\n2. Comparison to some existing paper is discussed.\n\nCon:\n1. What is the analytical challenge here? Please highlight it.\n1. Adversarial bandit is an interesting topic, while still, further emphasis of the contribution of this work is appreciated.\n1. how far is the derived upper bound away from the lower bound?\n1. Is an adaptive adversary considered here?\n1. What is the value of $rho$? How does it depend on $S$? Some discussion on value of $rho$, at least in special case would benefit the implication of superiority of the new result. Otherwise, it is not clear whether the proposed algorithm is better.\n1.  Numerial experiments are appreciated.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work focus on the adversarial bandit and design an algorithm whose regret depends on the number of best-arm switches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the 'Con' part in the previous session.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tctQeqs5Nu", "reviewer": "Reviewer_TF1V", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nAlthough I have not verified every detail of the proof, it appears sound and supports the claimed theoretical results.\n\nWeaknesses:\n\n1. I find the presentation somewhat unclear, partly due to inconsistent notation. For example, the learning rate $\\eta$ is sometimes defined as a function of $h$, other times as a function of both $t$ and $h$, treated as a constant, or at times denoted by $\\xi$. This inconsistency in notation makes it difficult to get the precise meaning in different parts of the paper. Moreover, the proof sketch jumps directly into the mathematical analysis without providing any intuitive explanation, which makes it less helpful for understanding.\n\n2. The presentation of the algorithm lacks explanation. For example, in Section 3.4, why can $\\rho_t$ be viewed as a variance term?  Why does the learning rate depend on $\\rho_t$? Many of these algorithmic design choices appear to be based on Agarwal et al. (2017), but without clear explanations, readers unfamiliar with that work may find it difficult to follow. As a result, the presentation is not very self-contained. Another issue is in Lemma A.4, which directly refers to Lemma 13 in Agarwal et al. (2017) without providing a proof. It would be preferable to include a proof using the notation and framework established in this paper to maintain consistency and improve accessibility for readers.\n\n3. The proposed algorithm seems quite relevant to Agarwal et al. (2017) and Luo et al. (2022). To me, I feel that it’s a direct application of the master algorithm proposed in Agarwal et al. (2017) to various base-algorithms with different hyperparameters $h$, as a conjecture of the unknown $S$. I believe the paper would benefit from a more thorough discussion and a detailed comparison with these works.\n\n4. (Some minor issues) equation (13): There should not be a summation over $S$. Lemma 3.3 is exactly the same as Lemma A.3.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies adversarial bandit against arbitrary strategies. Compared with the classical setting, the comparator policy can switch at most $S$ times, and the difficulty lies in that the parameter $S$ is unknown to the agent. To address this problem, this paper employs a master-based framework with the online mirror descent (OMD) algorithm. Two parallel results are provided: an $O(T^{2/3})$ regret with a fixed learning rate, and an $O(T^{1/2})$ regret with an adaptive one.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The algorithm description and proof sketch part should be polished.\n\n2. A detailed discussion on related works.", "broader_impact_concerns": "The paper could serve as an interesting supplementary contribution to the bandit literature, particularly in the study of adversarial bandits. The author may consider adding a Broader Impact Statement to clarify the potential implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XV3xbBnDGf", "reviewer": "Reviewer_6gDh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n----------------\n\n1.\tThe paper is written well overall with a clear exposition, including: description of existing results, main ideas in the present work etc.\n\n2.\tThe switched setting in bandit problems is notably challenging, and when S is unknown, the regret bound improves upon the results of (Luo et al. 2022). The idea of using the master-base framework along with the OMD method seems to exist in the literature, but using it for this particular problem is non-trivial. The work would be of interest for researchers working in online learning, as it provides improved regret bounds for adversarial bandits with switched arms.\n\nWeaknesses\n---------------------\n\n1.\tThere are two methods derived, but it would be helpful to explicitly mention the regimes of S, K and T in which the regret bound of Alg. 1 is worse (or better?) than Alg. 2. It seems from the expressions of the regret bounds that no one method is strictly better in general. There is some discussion in this regard on page 8, but it seems to only discuss w.r.t T.\n\n2.\tIn terms of the proof techniques themselves, it would be good to discuss clearly somewhere how it compares to existing proofs for these problems. This would also help the reader understand about the additional novelty in this respect.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the adversarial bandit problem where the learner’s performance is measured against the best “S-switched” sequence of arms in hindsight, for some switching parameter S. Existing results for this problem usually assumed S to be known, however the focus of the paper is for the setting where S is unknown. In this setup, two results are shown. Firstly, an algorithm based on the master-base framework and the online mirror descent (with fixed learning rate) is derived, and for which regret bounds are obtained. Secondly, an improved version of this algorithm is obtained (with adaptive learning rate) for which improved regret bounds w.r.t T are obtained.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Apart from addressing the points raised under \"weaknesses\" above, I think it might be helpful to provide a table upfront with an outline of the regret bounds for the switched setting. This would make it easier to compare the existing bounds with those in this paper.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)