PRODuctive bandits: Importance Weighting No More
Authors: Julian Zimmert
Teodor Vanislavov Marinov
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandit Algorithms
Online Learning
Primary area: bandits
TL;DR: We analyze variants of the Prod algorithm and show that they enjoy optimal regret guarantees in the bandit setting.

Abstract: Prod is a seminal algorithm in full-information online learning, which has been conjectured to be fundamentally sub-optimal for multi-armed bandits.
By leveraging the interpretation of Prod as a first-order OMD approximation, we present the following surprising results:
1. Variants of Prod can obtain optimal regret for adversarial multi-armed bandits. 2. There exists a simple and (arguably) importance-weighting free variant with optimal rate. 
3. One can even achieve best-both-worlds guarantees with logarithmic regret in the stochastic regime.

The bandit algorithms in this work use simple arithmetic update rules without the need of solving optimization problems typical in prior work. Finally, the results directly improve the state of the art of incentive-compatible bandits.

PRODuctive bandits: Importance Weighting No More
Julian Zimmert Google Research z zimmert@google. com
Teodor V. Marinov Google Research tvmarinov@google... com
Abstract
Prod is a seminal algorithm in full-information online learning, which has been conjectured to be fundamentally sub-optimal for multi-armed bandits. By lever- aging the interpretation of Prod as first-order OMD approximation, we present the following surprising results: Variants of Prod can obtain optimal regret for adversarial multi-armed bandits. 2. There exists simple and (arguably) importance-wel importance-eeighinng free variant with optimal rate. 3. One can even achieve best-both-wool worlds guarantees with logarithmic regret in the stochastic regime.
The bandit algorithms in this work simple arithmetic update rules without the need of solving optimization problems typical in prior work. Finally, the results directly improve the state of the of incentive-compiin compattble bandits.
1 Introduction
The adversarial multi-armed bandit (MAB) problem is a seminal online learning problem with applications in experimental design, online advertisement and more [Thompson, 1933, Lai and Robbins, 1985, Auer et al., 2002a.b]. MABs are characterized by the limited feedback given to the learner in every round, the so-called bandit feedback, in which the learner only observes the loss of their selected action, unlike in the full information, also known as the experts, setting where the loss of all actions are provided as feedback.
The first nearly optimal algorithm for the adversarial MAB problem EXP3 [Auer et al., 2002b]. EXP3 is a direct adaptation of the Hedge algorithm [Littlestone and Warmuth, 1994, et al., 1997, Freund and Schapire, 1997] with importance weighting to handle partial bandit feed- back. Hedge and EXP3 are special versions of online mirror descent (OMD), where the Bregman divergence is the KI. divergence induced by the Negative entropy potential. The OMD view of online learning [Abernethy et al.. 2008] has lead to a wide range of MAB algorithms such as Tsallis- INF [Audibert and Bubeck, 2009] and Logbarrier [Agarwal et al., 2017], which enjoy improved regret guarantees. These guarantees can be attributed to regularizers more suited to the bandit feedback setting, compared to the negative entropy regularizer. downside of OMD is that usually the mirror descent update is not closed form and requires (approximately) solving optimization problems at every iteration.
Alternative full-information algorithms with simple arithmetic updates are Prod [Cesa- (Cesa-Bianchi et al., 2007, Even-Dar et al., 2008, Gaillard et al., 2014], which enjoys second order regret bounds and Multiplicative Weights Update (MWU) [Arora et al., 2012]. Prod is known to be closely related to Hedge, both of which are different generalizations of the weighted majority algorithm [Liutllstooee and Warmuth, 1994] to non- non-binary feedback.
More recently, Freeman al. [2020] studied incentive-compatible online learning, setting where experts are not necessarily truthful but make predictions strategically with regard to the agent's s algorithm. Motivated by deriving an algorithm where the incentives of experts align with the agent,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

they propose WSU which can be seen as an instance of Prod. Freeman et al. [2020] further introduce bandit adaptation WSU-UX, the first Prod algorithm for bandits. Unfortunately. WSU-UX only enjoys T regret guarantees. This is not merely an issue with their analysis as has been shown via lower bounds [Mortazavi et al., 2024] and leads to the conjecture that this might be fundamental separation between full full-information and bandits.
We make the following contributions for understanding Prod under bandit feedback:
1. We disprove the separation conjecture by providing simple modification of WSU-UX with nearly optimal ((v KT log( ()) regret guarantees.
2. We present Prod variant that does require importance weighting and yet enjoys
O (V/'T (T))) regret bounds.
3. We present Prod variant that achieves best of both worlds regret guarantees, i.c. it enjoys improved (T))g(T) regret bounds when the losses are stochastic, while maintaining worst- case (Ov (T) regret bounds.
Notation: For N E N, let [N] (1...., N). We use (:.:) denote the regular Euclidean scalar product and (A) to denote the probability simplex over a finite set is the standard Landau notation hiding numerical constants, while Ô omits polylogaritmic factors as well. The expectation always taken over randomness of the algorithm, losses and experts, while F- = R8- [..] where Fe is the filtration over all randomness up step t. I(EE denotes the indicator function function for the event E. For a convex differentiable function F, the Bregman divergence is defined by D (2 F(y) F(x) (y VF(z)).
2 Problem setting and related work
The adversarial bandit problem is formally defined as follows. In every round = 1...., T, an (oblivious) adversary selects loss & E 10 (it possible extend the loss range to [-1, ) unknown to the agent. The agent simultancously selects an expert A ~ Tr, E [[[K]) The agent incurs and observes the loss l,A,, but does not see the losses of other experts. The goal is to minimize the pseudo-regrer!
Reg
max KE[K]
Σ le.. les
max (EA((K])
Σ (TT u, Ex)
Popular families of algorithms for this problem setting include online mirror descent (OMD) and follow the regularized leader (FTRL). Typically the algorithms use unbiased loss estimates of the loss vector via importance weighting: &.,: 4. x.. I(A, = i). We note that other types of importance weighted estimators have been used in literature such the implicit exploration estimator Kocák et al. [2014), which has improved variance properties. The algorithms are defined by a twice-differentiable convex potential function F R R and learning rate schedule M/ the agent maintains distribution via
M++1 arg mig ( (T,
DF(T,, (T)
(OMD)
M++1 arg min min(K(((K))
TT, Σ i F(T),
(FTRL)
OMD optimizes locally given the last loss and, as we will show, is most closely related to Prod. FTRL on the other hand performs global optimization and generally considered superior for adaptive bounds with time-dependent learning rates. In some special cases, such as time-independerr learning rate with potentials that satisfy [[VF())] - oo on the border of the optimization set, both algorithms are equivalent. Common potentials in the bandit literature are given in Table I and we refer their respective Bregman divergences as DKL, Drs and DLB respectively. The negative entropy is the potential which defines Hedge and Exp-3 (and derivatives) [Littlestone and
For the rest of the paper refer pseudo-regret regret for simplicity.

---

Negentropy/KL divergence Di=1 Te,i (T..)
1/2-Tsallis Entropy
Logbarrier
F(T)
-2 -2 v "
(11,)
Table I: Common potential functions
Warmuth. 1994, Vovk, 1995, Freund and Schapire, 1997, Auer al., 2002b, Kocák et al., 2014]. The 1/2-Tsallis Entropy is the key to achieving optimal best-of-both-worldd regret guarantees as was first demonstrated by Zimmert and Seldin [2021]. The Logbarrier potential was used by Agarwal et al. [2017] to first solve the corralling of bandits problem and has found many applications in model-selection problems [Foster et al., 2020], regret bounds which depend on the properties of the loss sequence [Wei and Luo, 2018, Lee et al., 2020b,a] and various other bandit problems.
2.1 Prod family of algorithms
The original version of Prod [Cesa-Bianchi et al., 2007] maintains weights wt,, for each experts which are updated via w1+1.1 (1, (1 77(2,5) and the agent plays the policy tH, Wt,i- This framework has been extended to D-Prod [Even-Dar et al., 2008), which shifts the losses in the weight update by the loss of a fixed policy, and MI.-Prod [Gaillard et al., 2014] that shifts losses by the mean of the current policy (among other modifications). With a suitable shift in losses, one can ensure that the weights sum up to I and hence operate directly on the policy space. In its simplest form, this is
1 K
11,
Te+ = Te, 1/(,, de)),
A
Atyles (Vanilla-Prod/WSS)
We refer to this update as Vanilla-Prod to emphasize its connection to the Prod literature, however this algorithm is exactly WSU [Freeman et al., 2020] derived for incentive-compatible online learning. We consider any algorithm a variant of Prod if it performs product updates of the form Te+1,5 = (1, - n (le; A,),, where Lt are linear affine functions of the loss. From now assume the initial policy is Ty, = 1/K, and this holds for all algorithms presented in the paper. The appeal of Prod algorithms lies in their simple arithmetic update rule. A second motivation for using Prod updates is the mentioned c incentie-comppatbility.
always
2.2 Incentive-compatible online learning
In the incentive-compatibo online learning setting, introduced by Freeman et al. [2020], experts provide recommendations, for example a prediction of whether it will rain on the next day. Each expert has internal belief and the agent would like to receive each expert's 's true beliefs in order to learn to follow the best expert. In the simplest setting the experts make predictions about binary outcomes, with the i-th expert having (private) belief by, E [0, 1] about the f-th round outcome. The expert's 's belief is unknown to the agent and the expert only reports a prediction Pt.: E [0. 1] about the outcome. Based the expert predictions, {pt. [c[]] the agent makes a prediction based on p. = -E iP,, and incurs loss [(p,, E [0. 1] based on the realized outcome E {0. 1}. In the weather forecasting example the outcome is the indicator if rains the next day and the loss is C(p.. rx) = (r: p.)². In Freeman et al. [2020] the experts only care about maximizing the probability that they are selected which does not necessarily result in truthful reporting, that by, may differ from pt,5. The agent's ' goal of receiving the true beliefs, {bt, [ie[K], can be achieved by playing an incentive compatible strategy which will always prefer selecting an truthful expert, that the probability of 11+1,5 of selecting expert when the expert reports by may only decrease if the expert reports any other Pt,; instead, no matter how the remaining experts act throughout the game. This is made precise in Definition 2.1 of Freeman et al. [2020].
Freeman al. [2020] show that standard OMD and FTRL algorithms are in fact not incentive compat- ible even when the loss L is restricted to be proper that is (er,Ber((b)) [[p, r)] > (e.-Ber()) [C66, r)] for all p A b. It turns out that any update for 71+1 which is linear affine in the proper loss function will lead to incentive compatibility and so the Prod family will ensures that experts report their true believes in this setting, i.e. they are incentive comptiibe..maabblee.... The state of the art for incentive-coppatible bandits T regret and any improvement for Prod directly transfers to better rates for this setting as well.
3

---

Modifying WSU-UX for nearly optimal regret guarantees
We begin by presenting minimal modification of Algorithm WSU-UX which is sufficient for regret guarantee of the order O (VTTTI (o)()))
WSU-UX uses importance-weighhen updates and injects small uniform exploration.
7 K
l [AA = =) b,,5
t + (1 -
At Re,i
#t.5
K Σ
Te+i = Te,i - -n(l, Xz)),
d
(WSU-UX)
where is the mixture coefficient. The role of uniform exploration is to ensure that the policy updates are proper i.c T++1,1 E (0, 1). Freeman et al. [2020] uses the following key lemmas in their analysis, which hold for any sequence of losses l E [0, 1] For completeness we restate the results we use below.
Lemma (Lemma 4.1 [Freeman et al., 2020]). nf S 3. the WSU-UX weights ni and tt are valid probability distributions for all t [T].
Lemma (Lemma 4.3 [Freeman al., 2020)). For WSU-UX, the probability vectors { and loss estimators & satisfy the following second order-bound
ΣΣ
T
K
Σ 2e.1
T
log(K)
1.8
+
K
22 Tt.
11
1=1
where i" is the optimal expert/arm.
The bound Lemma almost the standard regret bound that appears in the analysis of Hedge, except for the term 17 Σi=1 P.,.. This term is the reason why prior work can not show regret bounds smaller than 3.3. Even after taking the expectation over the randomness of the agents actions, this term scales with with 1/TT, which is potentially unbounded. Alternatively this term can be written as ///""(n (where x* is the policy picking with probability and one could perform change of measure to [ this term is immediately controllable.
In fact, change of measure techniques for bandits are now well established [Foster et al., 2020, Luo et al., 2021] by introducing biases to the losses. Assume we construct bias to the losses & l 6g which satisfies the same regret guarantee, Reg, as the original loss sequence, then running an algorithm over the biased loss sequence &, which selects A, ~ गe ensures
E
le,.1 lejt-
= E
Ee.s + St,A, 8r,5"
1=1
= Reg + E
E
j [8
BA- (5r
chango of measure
We introduce now the following modification to the losses
Ee, ===la le.6 (1
bas
I[(A,
which corresponds to 8zs
nRes *e.5
This yields the change of measure term
K
E E/
(8r.g)
E N
[6r,y]
Σ
nlei
nk
BB
Aej
which is sufficient for controlling the term ΣT= Cg in Lemma 2.

---

Theorem 1. Running WSU-UX with the loss estimators in Equation I and nk guarantees the following regret bound
2 , , @(V (00(V/xxt )og(())
B(/bx()))
Σ EllAA - 5 KTC//KTI (K))
The proof of Theorem is deferred to Appendix B.
3.1 Intuition on biasing the update and the Prod family of algorithms
We provide an intuition in this section about why WSU-UX is not tight and why the bias we choose is able to correct the regret. The modern analysis of OMD (or FTRL) with divergence function D is follows the template
T
D(x*, ((t)) D( mT(
π 4
OMD
x², +
"1
D(T", )
DTTT", x
TT+1
OMD
OMD
OMD
bi)
+
D ( (++ TD
D D( m)M
n
7)
stability
where the inequality crucially relies on "t+1 being the 1-step OMD update to the previous policy. OMD algorithms like Hedge choose the policy that minimizes the per-step stability term in every round, which is what allows for the stability term to be bounded appropriately. If instead of playing oh an approximate policy ni s at uas is played, the template regret analysis can be changed by adding the terms
(D(TT - D(T",, omn
where #z+1 is now the 1-step OMD update from Te. When D is the KL. divergence and the approxi- mate policy ne is coming from the WSU-UX, this term contributes the undesirable nyfr,
We now explain how our loss biasing solves this issue. The Prod/WU update can be seen as a first order approximation to the Hedge update, that is
T
DMD
F4, exp(-n(le, Ae)) Te, m(le,s - Aτ)) Te,s
first onder
where X, a normalization factor. Tuning d such that Σ Tc+1, = recovers
To control the undesirable terms, we have make the approximation tighter. The loss- bass-biasing introduced the previous section acts as a correction which brings the Vanilla-Prod/WSUU update closer to the second order approximation of the Hedge update. Indeed, we have
Te, (1 (1-n(éd i-n(lee 2e)
of (les -20)3)
111 #z,i exxp(_n((ee, Xx))
second-orzler
-Tt (1 11-m((a n/(e, i Xe) (1 ! (Ce. - 21))):
2
and so our loss adjustment in Equation 1, & = l,, - Re), can be seen as a second order correction to the term 9² -(,,->x)² We cannot exactly correct the second order difference with linear update rules, which we address by slightly overcorrecting, i.e. biasing by a larger amount than the second order adjustments implies necessary. That is, the correction term we use is of the order / a instead of n R Fortunately, the regret analysis is not sensitive towards this as we have shown in Theorem
"This might look very dissimilar from the original Hedgc/EXP/MWWU analysis, but it is actually equivalent after accounting for the special form of the KL divergence.
5

---

Importance weighting free adversarial MAB with LB-Prod
While biased WSU-UX obtains optimal regret, it still has go through the extra complexity of injecting additional uniform exploration at a rate of to ensure proper updates and add bias to the losses. As mentioned in the introduction, prior work proposed other potential functions that have favourable properties for bandit feedback. Using the same linearization argument to derive Prod version based on the Logbarrier leads to surprisingly simple algorithm without loss biasing that is arguably importance weighting free. LB- ---Proo differs from WSU-UX by using the masked loss Le = (,, = i) instead of the importance weighted loss and -on-yymmetric normalization A
Tt.AA C.A.
Te Tr,i(1 m )e,i)),
Ae, Te, ΣØ T
(LB-Prod)
It is easy to confirm Ees - de, E [-1,1]] via TT, S (mī, A. 3/2
yielding proper updates for ?) < The following theorem shows that this simple algorithm rate optimal under the right tuning.
Theorem 2. For any sequence of losses & E []1,1] and any n 1, LB-Prod produces valid distributions Te A((K]) and its regret is bounded by
T
K log(T))
2n/L"
ElG,A, 12,-
7
1-
Tuning =
(
results in regret bound of O( log(T) for any T >>
K Klog(2), The
2T
proof of Theorem 2 is deferred to the end of the section.
4.1 Intuition of LB-Prod
As mentioned before, LB-Prod is the linear approximation OMD with Bregman divergence induced by the Logbarrier potential, that is DLB induced by the potential fuction F(x) = > log(æ;). The one-step Logbarrier OMD update of a policy n, with weiihing is known (see e.g. [Zimmert and Seldin, 2021]) to take the form
OMD
Te,
(1 17e,, Ax)) 1t+1i
+ ( Xx)
where A, is normalization constant that ensures x is probability distribution. If instead X is tuned so that KK 1t+1,i = the LB-Prod update is recovered. This can be be verified by setting Le, Te, and d = Ar. The curvature of the Logbarrier regularization is what ensures that the importance weighted loss É,, is always multiplied with its probability Tt,i, allowing to the algorithm on the masked non- weightetted loss sequence directly.
Additionally, the second order approximation is
OMD
(1, - ple Xx) + + - xx)3).
second-order
The additional undesirable terms, unlike the case for WSU-UX, will only contribute r/T regret not adjusted for as we show next.
4.2 Analysis of LB-Prod
The following technical lemma is proven in the appendix.
Lemma 3. For any timestep L and arm i, it holds
Ee Ae,x] Tti (Le,i ca) independent constant.
[.((Ce, - Mo.1) 2Trr
where O. [- is
In Section 3.1 we argued that one needs to bound the additional term 1) (Dr.nn mT+1)
DIT(TT, OND )) to reduce the analysis to standard OMD. While this term is nicely bounded for LB- Prod, it turns out that easier to directly bound the "prototype" of the stability term in Equation (2)
due to the fact that we have closed form expression of M++1-

---

Lemma 4. For any time E [T] and any u E [[[K]) it holds
2n
(Te - u, E,) + Et [1] Dr.n(u, T+41) - - "Dn(", S
The proof is an algebraic exercise and deferred to the supplementary material. Finally, we can prove the main regret guarantee.
Proof of Theorem 2.
To show that this algorithm outputs proper probability distributions, note that
K
K Σ Mt. MT
K
K
Tr.A, j=1 2k=1 iik
Σ T4415 =
+
l, Wts Σ 2=1
T1 = 1.
1=1
i=1
Additionally we have seen that l2., Ae,el 1, hence for any 17 1, the probability of any arm is strictly positive. For any comparator u", we define u² + ( u²), which satisfies
EL (u u², L) I 2. Using Lemma 4 and Equation (2), we obtain by the telescoping sum of Bregman terms
An/T < 1-n + ".-"""((Drnuu,, (I) Dra((, 1
4n/
K Klog(T)
E
Te u, lt)
1
4.3
The perturbation analysis
We outline alternative analysis that reuses established machinery and might be more accessible for some readers. Our analysis begins by viewing the Prod update as exact OMD update over perturbed loss sequence. Indeed, there sequence of perturbations {EaheetT) Et RR such that
nr,a(1 ple, - Ae)) = Te41.5
+ (le, E.A Ar)
The exact form of ct satisfies the following
( - Ax²²
[ =
C,, 1 (le, 2e)
Since Prod is exactly OMD over the sequence & 6t, we can decompose the regret as follows
E
Σ
u. .,) =E Σ T w -0) <1) + Σ (Te
ca) = RegoMD +O(nT).
The analysis is not entirely straightforward as the loss range for the OMD update becomes [-1 O(n), O(r)) because of the shift introduced by the perturbation of the losses, and this posses some additional difficulties.
Best of both worlds algorithms
In applications where the loss is potentially more benign, for example sampled i.i.d. from a fixed distribution over [0, 1] it is desirable to obtain faster rates in nice environments while preserving worst-case guarantees. Probably the simplest algorithm with this property is Tsallis-INF [Zimmert and Seldin, 2021], which FTRL with 1/2-Tsallis entropy and t). 1 1/vl learning rate.
5.1 TS-Prod
Recall the 1/2-Tsallis regularizer is = =K 2/T.. Unlike OMD, FTRL not canonically expressed as a 1-step update of the previous policy. Instead, the 1/2-Tsallis-INT policy is given with normalization constant A, (see [Zimmert and Seldin, 2021])
FILL 11,,
AA41 + TTe Σ
Laji
7

---

Recursively using this expression yields
-2
-2
11-1,
A1+1
The
1
Ar) Tels
1 v tua (le
Thht
2x)
1/t
miL t,i
where &:
and d As+1
ge m-1
Ar.
The first order approximation is
PIRI Ti,
21 (Le, -Ee/ TTT Xe)).
Ist-order
We ensure following the approximation expectation by directly biasing the losses with M/Ct// / T Additionally, one needs to perform second-order correction discussed in Section 3.1. We omit formal derivation, but notice that WSU-UX required /7/ Tt.s correction, while LB-Prod works without correction because the error is of order 7). As the intermediate potential between KL and Logbarrier, Tsallis-INF turns out to require correction of order n/ TT,i, which we tighten by an additional factor of (1 xe,s) necessary to ensure stochastic bounds.
With this, we are ready to present
L,, = les ME + +7(1 - me(e)
IlA =
T
1
A
E.
Te.
m/
1)77-1
i=
Te+1, Tt,
2np / -xx))
(TS-Prod)
Theorem 3. The regret of TS-Prod with 17.
VK+20 7 = 13 bounded by O(V KT + log(T))
2
the adversarial setting and by O Eifer
(Tg(T) A
in the stochastic setting.
5.2 Analysis of TS-Prod
We first show that the loss biasing is sufficient to ensure that the distribution is well defined.
Lemma 5. Ef is a non-incredd con-increasiig sequence, Th < VK(Gtt>) and n S 1 2 for all
then the update rule of PS-rrod is proper and satisfies nti (E. 2 for any arm and loss sequence at all time sleps.
Next present the moving parts of the analysis.
Drs(u, nx) Drs(u, T(+1)
E
(T
u. (x)
E
Te u. la Ee)
change meusuree
proto penalty
Drs(u, Te) Drs(u, Te+1)
+ Te u, Eo)
T)
proto-stability
The change of measure is by construction
T
K
change-of measure Σ
E
Te.i
us
1n (1-1))))))
(3)
Te,
We now bound the stability and penalty. Lemma 6. For any time such that ne, >> (E+ + 2) it holds
(Te- Eu,.u,E,f.)) EE
Drs(u, Tc+1)
Drs(u, me)
<
13 7/44
(1 Tes)
TJt
Tpp
2 / Tei
The tuning of Theorem 3 satisfies the conditions.

---

Lemma 7. The proto-penalty is bounded by
Drs(u, me) Drs T(t1)
Σ
n
Σ igi
2
Tea
Te
Tri
We are ready to prove the main regret guarantee.
Proof of Theorem 3. By Lemma 5 we have proper update rule. Using Lemma 6, equation (3), and Lemma yields
where we tuned ? 2
13 Tr T()) +
E
T u, Li)
S E
Σ E Te,
O(VT). The adversarial regret follows from Σ TT, S VK, & 5 & = For the stochastic regret, the proof follows standard arguments using the self self-bounding trick in Zimmert and Seldin [2021]. For details on the self- hoffdinnning trick see the supplementary material.
5.3 TS-Prod and stabilized OMD
Even though we derived TS-Prod from FTRL, it turns out that one can also interpret the update as an approximation of stabilized OMD proposed by Fang al. [2022]. In Appendix E, we formalize this connection and present slight variation of PS-Prod. We then analyse this variant via the perturbation technique described in Section 4.3. Our analysis also shows that the stabilized OMD algorithm induced by the 1/2-Tsallie entropy enjoys best-of-both worlds regret guarantees which to the best of our knowledge novel.
Discussion
We have provided an extensive study of incentive-compatible bandits. We have negatively resolved an open question of whether rreetive-comppttbilii as defined Freeman et al. [2020] is harder than regular bandits. Using linear approximations, partly with second order corrections, allows to recover results from well studied algorithms in the literature. We even obtain an algorithm with best- ud-both-world guarantees. Our algorithms conceptually simpler than existing bandit algorithms,, they update the probability distributions with basic arithmetic operations without the need to solve optimization problems.
Our successes make it likely that one can transfer even more sophisticated methods, such as first-order, second-order, path-norm bounds and online learning with graph feedback to this framework. We leave this investigation to future work.
References
Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, pages 263-274. Citeseer, 2008.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. In Conference Learning Theory, pages 12 38.8. PMLR, 2017.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta- algorithm and applications. Theory of computing, 811::211-644 2012.
Jean- Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In Conference Learning Theory, 2009.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 42(2-3), 2002a.
Peter Auer, Nicolò Cesa-Biande Biaa-Bincchi, Yoav Freund, and Robert E. Schapire, The nonstochastic multiarmed bandit problem. SIAM journal computing, 32(1), 2002b.

---

Nicolo Cesa-Bianchi, Yoav Freund, David Haussler. David P Helmbold, Robert E Schapire, and Manfred K Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):22-485. 1997.
Nicolo Cesa-Bianchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for predic- tion with expert advice. Machine Learning, 66(2):321-352, 2007.
Eyal Even-Dar, Michael Kearns, Yishay Mansour, and Jennifer Wortman. Regret to the best vs. regret to the average. Machine Learning, 72(1):21-37, 2008.
Huang Fang, Nicholas JA Harvey, Victor S Portella, and Michael P Friedlander. Online mirror descent and dual averaging: keeping pace in the dynamic case. The Journal of Machine Learning Research, 23(1):527 1-3308,, 2022.
Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecification in contextual bandits. Advances Neural Information Processing Systems, 33:1 1478-1 1489, 2020.
Rupert Freeman, David Pennock, Chara Podimata, and Jennifer Wortman Vaughan. No-regret and incentive-compatible online learning. In International Conference on Machine Learning, pages 3270-3279. PMLR, 2020.
Yoav Freund and Robert E Schapire. A decision-theoreticc generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
Pierre Gaillard. Gilles Stoltz, and Tim Van Erven. A second-order bound with excess losses. In Conference on Learning Theory, pages 176-196. PMLR, 2014.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Opti- mization, 203-4):557-325, 2016.
Tomáš Koeák, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by implicit explo- ration in bandit problems with side observations. Advances in Neural Information Processing Systems, 27, 2014.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1), 1985.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Chung-Wei Lee, Haipeng Luo, Chen-Yu Yu Wei, and Mengxiao Zhang. Bias no more: high- bogbbprobbabiltty data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 111111552215555 2020a.
Chung-Wes Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference on Learning Theory, pages 2516-2564 PMLR, 2020b.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-2) 261, 1994.
Haipeng Luo, Chen-Yu Wei, and Chung-Wei Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34:22931- 22942, 2021.
Ali Mortazavi, Junhao Lin, and Nishant Mehta. On the price of exact truthfulness incentive- compatible online learning with bandit feedback: a regret lower bound for wsu-ux. In International Conference on Artificial Intelligence and Statistics, pages 4681-4689. PMLR, 2024.
Shai Shwaar-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2), 2012.
William R Thompson. On the likelihood that one unknown probability exceeds another in view ooster the evidence of two samples. Biometrika, 25(3/4), 1933.
Vladimir Vovk. game of prediction with expert advice. Proceedings of the eighth annual conference on Computational learning theory, pages 51-60, 1995.
10

---

Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference on Learning Theory, 2018.
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-49 2021.
Contents
Introduction
2 Problem setting and related work
2.1 Prod family of algorithms
2.2
compaiie online learning
3
Modifying WSU-UX for nearly optimal regret guarantees
3.1
Intuition biasing the update and the Prod family of algorithms
Importance weighting free adversarial MAB with LB-Prod
4.1
Intuition of LB-Prod
4.2 Analysis of LB-Prod
4.3
The perturbation analysis
5
Best of both worlds algorithms
5.1
TS-Prod
5.2
Analysis of TS-Prod
5.3 TS-Prod and stabilized OMD
Discussion
A Background on FTRL and OMD
12
A.1 OMD analysis overview
12
A.2 FTRL analysis overview
12
Missing Proof Section 3
13
Missing Proofs Section 4
13
Missing Proofs Section 5.2
14
D.I Technical Lemmas
14
D.2 Minimal probability
15
D.3 Self-bounding trick
17
TS-Prod and stabilized OMD
17
E.1 Proof of Theorem 4
18

---

A Background on FTRL and OMD
We give brief overview of the template analysis for FTRL and OMD. For an extensive discussion and regret analysis of these two frameworks we refer the interested readers to Chapter 2 of Shalev-Shwar [2012], Chapter of Hazan al. [2016] or Chapter 28 of Lattimore and Szepesvári [2020].
A.1
OMD analysis overview
The OMD update
T++1 arg min min (n.mcl) (F(
(OMD)
can be written in two steps as
at+1 arg TERK ( (I. (T(T,T)
*++1 arg min (((((() DF(T, #t41),
where the first step is an unconstrained optimization over the linear loss time t together with regularization term given by the Bregman divergence induced by F, and the second step is the Bregman projection onto the probability simplex. Thie first step of the OMD update can be re-written as
VF(+++1)
(F(
Let F2 1. Since T++1 is the minimizer of the OMD update, and Dew is convex we have that
n.
Te+1 - n. Le) S (u Te- (F((++))) (F((m))
DF, Te) Dp. (u, (c+1) DF. (T(+1,
Further, it holds that
(Te T44, Es) = DF. (Te+1, Tt) + Dr, (Te, #e+1) DE, (fc-1, T411)
S Dr. ( Te) + Dr, (TT, #tt1).
Combining the two inequalities together we have that one step of the regret to any E A([K] is bounded as
(be, (e
uu)) u) S Dr. (u, m.) DF. TT+1) + (Te #141).
For a fixed step-size Y) = 17 the above telescopes to bound the regret as
Σ (4, u) Dr(u, mi) Dr(u, TT)
T-1 " Σ (e((ermet1))
1j
As long as F is twice differentiable, each of the terms can be bounded as Dr(Te, #441) x where F* is the Fenchel conjugate of F. Controlling [1 in OCO is usually done by assuming some boundedness the losses. In bandit literature controlling this term is slightly more involved and depends on the choice of F.
Onn (
When 7) is not constant, telescoping the above sum does not work and the analysis becomes much more involved. It is possible to construct sequences of losses for which the OMD update does not enjoy sub-linear regret for 7), J Fang et al. [2022] introduce stabilization term to the OMD update which overcomes this problem and show that this new version does enjoy the standard OMD regret guarantees.
A.2 FTRL analysis overview
The FTRL analysis follows similar ideas, however, the step regret is bounded
(l, u.) (Fi IA++))(R))(-L (Fr + IA(IR)) m
Dr --
12

---

where L, = -E lu and [ajK] is the characteristic function of AKK i.e,, (a(K( (T) 0 if
E A|K] and [a[K] (Λ) +oo otherwise. The term Dr- (-L,, - 11) can be thought of as the equivalent to (T, # in the OMD analysis. The term (F, + (<(()))(-----) (F
(a(K)))" needs to telescoped in an appropriate way. For more details we refer the reader to the penalty term bound of Zimmert and Seldin [2021].
B Missing Proof Section 3
Proof of Theorem I. WLOG we assume that T' > K. We begin with the bound from Lemma 2. The second and third term in the RHS of the inequality are bounded as is standard in the Exp3 analysis
T K
nTK I-7 S 2
T
Tea B
&
S
E
<
E
Te,
where Fi-1 is the filtration generated by the random play and randomness of the losses up to time t t- 1. We now consider the expectation of the LHS which evaluates to
K
T
T
K
T
K
T
El (e,)
E(l,,-]
=
E A
=
E Be
Bl(ex
i=1
1=1
1 #e.5
E
E
1
E
1,4
21/TK
K
#t.s
t=
Σ
Ble
Thus combining the bounds on the LHS and RHS we have
K
El deo,l - Bleaal log(K)
12
+ 41fTKK +1
E
1,
1]
E
"
t=1
To complete the proof only note that Σ Σ ElTT, - Σt= Blle,s,]
2T nKT.
C Missing Proofs Section 4
Proof of Lemma 3. The expectation of = ET =1) is obviously Nulei hence by the definition of Ati we have
Σ K Σ j=
m2
Egles- - Aed = Ted
lu
For the second part, we have
Σ5 T 22
Σ
Ee[(En >u) E. + E
Ta
Te
1+
tt
j=
k== T2x
<> k=
m
The proof is completed by noting
Ti5 Σ
Dj=1 2y
Tec Ej=1 Tij
T
5
ΣK
K
2
>>
3
Σ
3
b
k=
mike)
Tik
13

---

Proof of Lemma 4.
(Te u, Es) + Et. [1]
Dr.n(u, (e, 1)] - -1 - (r.(uu me)
K
Uj M1+11
U4 Ttii
Tetiá
(Te - t2) + E,
+ log
17
Te,t
Mettis
log (1 (1-n(les -der))
( u, 4x) + Ex
K
u.(Ce,t -1e,))
I (Te u, 4x) +
less + de,
(log(1 + x s x))
Te,s -n(e,, -
K
K
(le, - Ae.a)
S (TT - u, 4x) +
U4
Eel Eell,s - - +
Uk R2
Tei
Tta
1 -
2n
21
S (Te 2,) +
(44 (e,) - -ce) + 1 17
04
(Lemma 3)
1
i=1
D Missing Proofs Section 5.2
D.1 Technical Lemmas
Lemma 8.
x
min f(x) = min =E(0,1] 0E 1 - vI x 2
Proof. We first show that the optimal point is smaller than g. by looking at the derivative
f(x)) 3/2 x² (1 x)
2(1 x)²
For the enumerator, we have for all x 2 1:
3/2 2 (1-x)² 3V - Vz, V1-x} xx]
m2n 1)
Hence
min zE[0.1]
f(x)= min f(x) > min
V1- x =
xE(0.1/9)
xe(0.1/9]
Lemma 9. For any a, b 2 0 such that + b 2 1, it holds
a
b
2 V2.
vb
Va
Proof. We can assume w.l.o.g. that = 1 - b, otherwise scale both and down and reduce the objective. The resulting problem is symmetric with 1 as the unique minimizer resulting the statement.
z
D
14

---

D.2 Minimal probability
Lemma 10. Assume that wei > (Et + 1) holds all arms, then
E, (lei - No) - 13(1 T())
8T
Proof. Let le,; = -Te,fi, and Ar, Te, Note that Es E [-1,1]] by the condition on Tei and Ea 0 for + 1, by construction of the loss estimate. Hence
2
E, (Bes - )\xs)3
S Tzi
1
E i
IJ + Σ Tej
Tti Ttj
Bl
Id]
K
Σラ=
K
j=1 Bj
C Eite Ttg
2 + Tei Ejpi TTj
< Tu
CE/=1 mly) )2
(1 - (I-TH)? (2 jæt m1z) )2)) Tea T(s)
Σ
jots
Tf
TTa(1 - -es)
( (1 m() Ejfi mta
)2
where Rej
Mii I-m (1 THi) Ejjs #ij
We bound the two terms in the bracket separately, for the first term have
Tes)
1n
Ejets mtj 1)
Th (1 )T)² Σ jبHt
+ (1
Ted)
8
VA
(Lemma 8)
8
The second term is
=2 Tei (1 Tei) Eids 22
tta TTi) (2 ~3)
<
(T + (1 TT:) Σ Ei kzg
( + (1 Tes) à Σ jzز 
-2
mes m j#t #15)
T
tt Σ jグ mt
IA
(Lemma 9)
Lemma 11 (Lemma 5). & is non-increasing sequence, T) VK(E+ta7 and vit1 S n1((1
2 for all I, then the update rule of TSPP is well defined and satisfies we, > (Et + )) 1 for any arm and loss sequence at all time steps.
Proof. The proof follows by induction. At f = the statement is true by definition. Let the claim hold at time f, then the probability of an arm only decreases when lej A is positive. We look at the cases where A, = and A, + independently.
Case A, = i:
Te+1,i > Te, 1 2nh Fe.)e..)) -Tt, 21 (VTe,sle,i 7e(Es + 7 Te,))))
T1, (1- -2-m/) 2 + 2711
= (1 - -2m1/) (VmL.
4/2
+ (2 2 )rr
1 2
15

---

This is quadratic function in Te,s with minimizer (1-2mm)) (Ee + n8. hence the value lower
"
bounded by setting Te, (Ex + ?
T411 > (Et + 2 (1 2ym 2 (Ee +))) 2 (Ee+1 + 7
Case Ar + i:
14,1 = Te, - 2 mellEe + 7(11 T(,,,)))
Ee,Ary Te,di
Mτ, 2(Ee + 7) =
This is concave function (in xT,;) the minimizer is either at æe,i (G. 2) t,, 1. For the latter, have have T1,1 2 the minimum is obtained for the first case.
TH+ > (Ee + 2) 2 + K > (Ex + 7))
2mm²) 2 C2417
Lemma 12 (Lemma 6). For any time such that Tt, > (Ex + 2)) n it holds
(Te u, [e()) E2
Drs(uu (u, T(+1)
Drs(u, Te)
me Te,s)
(
1
Ui
Tti
7
T6-1
Te,
Proof of Lemma 6. { u, Be(ee]> + Et [nte Drs(u, mT-1)]
"i (Dssu,, xT))
=(x= u, [e(ee)> + Ee
Ui T2t1i
Te
1
(2 - 2\/TH)
Tl TT+1, 1=1
M) Trss
17t
(m= u, [e())
Mi
Wei
Te+ -11 :1)
17t /
(V
Tei
K
2n o Teil Xx)
= (x u. Eg(ce]> +
U1
E,
1
TI TT
1 21 TTi -xx)
Tti
2Th Veiillei -Xx) >a) no)-11)
Ex
T/ / Tei
K
Th (ea A1) + 21T Teilees A1)3
U
S <(T= - u, +
E,
7/ / Tei
21/1, / Tes (Bri - Ax)
Tui
-nvielller 2011
E2
Th Tee
K
Er (es de] + Aneuri Tes Ee (Cex xx)2]
< (TT u, E.(e,])
(w: Tei)
(Setting (Er + 7) 2 4)
13 U4
(1 Tea)
(Lemma 10)
Te
We now show that the requirements of Lemma 5 are satisfied with the tuning of Theorem 3. With m
VK+267' have Ct decreasing, 4 and 7 ensures that 1/:
K 26t v(K (6t)(K + 26t
26)
> 2, which is monotonically
1
Further we have
VK+26t
V VK(e++7) +7)=
1h
K 26l
26
4
=
5
1 1-4
K + 26(t + 1)
K + 26( + 1)
K + 26t
16

---

Proof of Lemma 7. Using nu = oo and Drs(u, 11
2 0
(u, Tt)
Drs(u, Te+1)
Σ
T
1
1
(us( T()
1/
9/2
76-11
t=1
1
1
(F(u) -
{u T,, VF(TTe))
1]t
1)-1
T
K
Thbtt
22(VTL.5 - vun)) - (ui Tes)
(2(
Tei
i=1
T
K
Σ
Th
Σ
2
[44
nti))
1=1
i=1
where the last inequality follows from
Σ
V Uh
2
12
y Tr,
D.3
Self-bounding trick
We now quickly describe how to apply the self-bounding trick from Zimmert and Seldin [2021]. Assume that we have a regret bound of the form
T
aTr, +
aas VI
1=1 Af
for some positive a and b. The above inequality implies
1
A, 31)
b
D Te,
Te,
Tti
Vl
3
Vi
3
For a fixed i the term
A
3
< Of
>
9o² A
and so the maximum regret from
Rud <
T
a
A
6a
Vt
Vi
A
t=1
t=1
Further the term
b
AiviT. 3
26 A
for
1
2 A
This implies
Vt
4
Σ
VES
b
Di
Tt.
S
A?
T
21
81
+
2b log(T) (T)
Vi
3
Vi
t
A
A
Combining the two bounds we have
T
Σ
Σ
1
log
a²
+
A
1=1 SAS
E TS-Prod and stabilized OMD
The TS-Prod update is linearization of the FTRL update as explained in Section 5.2. In this section we show a regret bound for the TS-Prod algorithm by linearizing the OMD update as we did for WSU-UX and LB-Prod. This comes with its own set of challenges. First, we believe that decreasing step-size the OMD update is important for achieving optimal regret bounds in the stochastic setting. Second, the vanilla OMD update with decreasing step-size might incur linear regret in the adversarial setting. This second issue is resolved by the stabilized OMD algorithms proposed by Fang et al. [2022]. TS-Prod turns out to be equivalent to the dual stabilized OMD algorithm of Fang et al. [2022]
17

---

and hence will inherit the adversarial regret guarantees. In the rest of the section we sketch the regret analysis for the stochastic setting and how we can reduce the regret analysis the adversarial setting to that of Fang et al. [2022].
Stabilizaaiin introduced by Fang et al. [2022] is the process of mixing the gradient mapping. (T.)), of the current iterate with the gradient mapping of the first iterate, VF(T1), in the mirror descent update in the dual space, where F(x) = - - 2/ This mixing turns out to be equivalent to the negative biasing losses in Equation TS-Prod by the & dependent terms.
The regret analysis begins by defining the perturbations {EE,s (er,heet)) so that
Tt,
1e+1;
(1 + M7+ V (L,, c,,)))²
(4)
that is Ce makes the update in Equation TS- -S-Prod equivalent to the 1 1/2-Tsallis mirror descent update. We note that the ez.i is only defined to assist with the regret analysis and it never needs to be computed for the actual update. The perturbations, εt,is are well controlled as we show next.
Lemma 13. For every E [T] E [K]. there exists ct,; such that Ct, S 4n / for all i and C,
Lemma allows us to proceed with the analysis for the stochastic and adversarial cases by using the standard regret decomposition into penalty and stability terms. In the stochastic case bound the two terms in the following way Lemma 14. For stochastic losses the penalty term is bounded in expectation by
I2
EEips met1.)
VK log(!)
E
(Eigi- Tet1.)
log(KT)
o
Vt
V8
Lemma 15. For stochastic losses the stability term bounded by
K
Te.
K
1 Te,))
The stochastic regret bound proof can now be completed by a careful self-bounding argument.
In the adversarial case we reduce the regret bound to that of Fang et al. [2022] in the following way. Let & F JA x-1 be potential defined by mixing the 1/2-T'allis potential together with the indicator function for the probability simplex. The update Algorithm 2 (Dual Stabilized OMD) can then be written as
ú = VQ(m)) - ne(ee + Et),
Dt+1 Xet0++1 (1 ())((
#++1 = (f++))
It turns out that this update is equivalent to the OMD update with respect to L., in Equation 4. This allows us to use the regret bound in Theorem 3 [Fang al., 2022]. Overall the regret of the perturbed OMD version is bounded as follows.
Theorem 4. The regret of the algorithm defined by the update Equation 4 is bounded by
log(T)
K Klog"(1/Amin) + K33/2
Σ SIS
A
Amin
in the stochastic case, where Amin is the smallest gap between the expected losses. Further the regret in the adversarial setting is bounded by O( (TKTT).
E.1 Proof of Theorem 4
Proof of Lemma 13. We work under the following assumption which is satisfied with the choice of n) and 7 by Lemma 5. Further, we going to work with the following slight modification of the
18

---

losses & in the update of TS-Troor P-oddd
me( (T,s)
I(As
17.E.
(1.3
V
Ttii
V
We quickly check that the variance with this definition of le is bounded by Lemma 10
7(1 -(,3))
I(A,
=i)
7
E
Ve,
Tei
Viee
4, 7(1 - Te
(Th,,)²
7(1 ( Te,e)
E,
2
Ce,i
Tti
V
Ae,
4,s 7(1 - Te.i)
(Th)))²
Ce,i 7(1 -Tt,i)
S E,
- 2
Teii
TH.s
v TT,
/
((E.s- (Ee + 7(11 Te.s)
I(A = i)
)
21
E,
VT,
Assumption 1. Assume that for all [T] E [K] it holds that In Te,beal S J.
Lemma 13. First for non-negative we show that E [0, This follows by observing that 1/(1 3/2r)² < 2x for E //6 and 1/(1 + z)² 2 2x for x: 2 0 so by the Intermediate Value theorem there exists an E [0. f] such that equality is obtained. Next, for < 0 for E = 0 we have 1/(1 z²² > + 2x for 0 and for 2/2 we have 1/(1 x z/2)² I 1 2x for [0, 1/4] and so we have
1 2 )
For the second part of the lemma using the Taylor expansion around of 1/(1 + 2²²² implies that
1
S1 111-21/74 2n/ 3
(1 11
and so
1 - 2 E) S - 2n + 3() +
21 S 3(1Vx()² =
20 3(1 + t))² =
E S 4n/
Stochastic bound. Let DT' (u, w) Drs(u, v) and let
Tt.
# (1 11 Cle Ee,s x,))2²
where A; = Lr,A. We note that T now the projection of #e+1 onto the simplex. Further by the 3-point rule for Bregman divergence we have that
(Te, (L, Te u) DT me) D..5 (u, #c+1) + D #t+1)
< DT m.) DT' (w, ((+1) + DT' (m,, #c+1).
Penalty term.
Lemma (Lemma 14). For stochastic losses the penalty term bounded as follows
E Eipp Me+1.)) ))
v K log(t)
B.DY'S (U, T441) (u, < 0
Vt
where (T = 1Drs(u, v) and ni Jt
1
19

---

Proof. for ex:
1
(u, Te+1) (u, (T+1) =-
71+1
1
1
1
)
1)
11+11
m1
T
K
TT412
71++1
==1
+ T41.
1/++1
7h
ViT+LL
1
1
Σ V T
16++1
iF1
(1
)
1
Tlc
1
77++1
me
From the update Equation 4 have
VK + Σ no nalteng + +.,i));
v M1+1,
which implies
(1 [T+1F))) }2
VK(11 / +1+1+111 ++
v /T+ 1, Σ Vallag + texi))
M1411,1
First we bound (1 - V )
2
2
Eier T1+1,
(1 (
1
Σ
Tetid
1 / Eigi Te+Li
ifi
2
Σ
In the stochastic case WLOG we can take Eile,--1 0, Vt [T].
We first control L,p. We have
Les-
M67(1 Te,*)
I(A, i*)
McE
bas
TT
TT,
Te,
The first term, l, KAmii) is O in expectation. The second term, used cancel out the contribution from the perturbation e,,- The third term is there to help with the adversarial setting analysis. Next, we decompose the fourth term as
me IA,=())
We.st)
will be
Te,""
K
VTr = - - = Te,
21=1
LJ
The first part of the above has a non-positive contribution to Le in expectation. The only non- negative contribution now comes from
TE + 7(1 -T, = 1) S VK(nc + + S 2/ Knn
Σ
3/2 π 1= t.j
i=1
20

---

and so we bound
K
7/8
5,
2n v Knn S Klo(())
Next we are going to bound [[(,,,-) using Lemma 10 together with Lemma 13:
13 Bl -T,i-)/ /TC.)
B(er,-] S /
51.5 1- s
2
This term exactly canceled out by
mey(1- 10(1I-a,." -). Me,
as 7
2. For the final bound we have
1
(1
M1+1
V
11411
27
E
Σ
Tetli
E
Σ
Tetlie
Σ
no (L.g + (2.0))
17++1
Tt
M1+1
)
a=1
2
E
Σ
Tet1s
+E
1
(1
v
g,
17++1
1/++1
Th.
Mhs (1 Ts.i")
+
E
1/s
-==1
27
E
Eifpr T(+1.)
VK log(t)
< 32
v8
Stability term. Recall that the stability term DF'((Te, way. We proceed do so as follows for any 2 4VK:
(m,, #t41). This term bounded a standard
Lemma 17 (Lemma 15). For stochastic losses the slability term is bounded as follows
(
nea) mw)+1) 1))
BID (Te, #+11) 50
Σ /
V
where 0 v) D.Drs(u,))
21

---

Proof. We have the following
K
1
D7 (me, Rot1)
V M++1, - -V,
(T++1, - Tt,s)
9/8
K
1
TT+1. - TT/ + Te, (e 1x))
1/t
1
v Tt+li
Th, + II+ITI te, Xe)
1+ TT, Ca,s ca,- X1) -1) Met1 + E,, 2x)
Tt,i
1
(nitIV/Ta + + de) + 21 me, + 6, - -21)²)
|t,
1he
M+ + + -1,2 Xx)
S 1 2x. for - 2
1+a
S 2m)
Ti (fe, + t,. Xx)2
where for the second to last inequality we only need to check 7/+ / - Ao) 2 - We have Th-1 / 2 and Lemma 13 implies
2 - B
|| -
We bound B[ 3/2 + C, Xx) < 2 2,2
3/2
2 "i,s (Be,5 >,)2 For the first term
we have
(
5/2 1,8
L
s
For the second term use Lemma 10 to get 1 Te,
3/2 (be,, X,) $ Eim Tr,
Self-bounding the regret for stochastic losses.
Theorem 4, stochastic losses. Combining the bound in Lemma 14 and Lemma 15 together with the adversarial bound we have that the total regret bounded as follows
/ K log(t)
))
Te
Te,a v K log(t)
+0
Σ
V Te
VT,
A;
Vt
Vt
+0 K3/2)
K In the above we bound the lower order term from the stability as Σ -i=1 Σ - - and decompose the regret into four parts. The first and second line correspond to the two terms from the penalty bound. Each of the two lines are decomposed into two terms. The first term is the result of the self-bounding trick and the second term the additional regret for the initial number of rounds before the self- fiff-bounding trick can be applied.
We repeatedly the following inequality 20 be S of which holds for a, 0. For the first line of the decomposition take To 8 K log" logg(////////// (K/Amor) where Amin is the smallest non-zero expected loss. We note that
Amin
log(8K log" (1/Ami))) A min V log(To) Amin 8log K/ Amin)
log( K)
log((1 Amin)
min
VTo
8log K/A)
8 log K/Amin)
2
22

---

R log'
for any Amin
If Amin
take To
The above implies
2024"
2024
mmon
that TT, (1
Tt, (
vR log(t) vt
and further Eijs Et=l me, log(t)
A
0 log (1 (1/Amin) ). The final regret bound is
Amin
(Tg(T)
K Klog2(14 (1/Amin) K3/22
+
A
Amin
Adversarial losses. We now present the argument for the regret bound in the adversarial setting.
Theorem adversarial losses. Let Ee,i = (le. 162(1-me.c)
I(Am=))
and X
We recall the 9--1
_/
V
Fe,s
update for Algorithm in Fang et al. [2022]
i1+1 VT((T+) mp-1
J++1 = Xe + (1 - V((
T++1 (i*((++)),
where the 1/2-Tsallis potential plus the indicator function for the probability simplex A A Since mi is uniform the second step of the update is equivalent to Dt+1 Xe0 Re-writing the first step the update we have
11-
Xe
+ mele, G,i)=
1
+ Meti 9.))
1/t
Vii
171
Te,
+ no ((eu-- 167(1 1 mess)
I(A, =1)
1
1
+ Es,
11t
---
v Te,a
+ ne nolle + Ae).
Since V is invariant under constant vector perturbations we finally have
T++1 V (f++1) = - (->m)- -m((e4 + VΦ (-1 [-v
mifrr + +
(I/ Te + mr (Le, + e2,)))²
Te.
(1 + me/ (Ta e)
And the update in Algorithm of Fang et al. [2022] equivalent to the perturbed OMD update which we have shown enjoys an optimistic regret guarantee. The regret guarantee the adversarial setting is recovered from Theorem in Fang et al. [2022]. In particular the theorem guarantees that the regret is bounded as
Df (VF(())) + + + KT.
Every term in the sum is bounded in the same way as the stability terms, that is (T,,, VF (VF()) ni(ee ++)) Σx,, 3/2 (/2 c.s). We "
the bound
the proof of Lemma 15 to complete proof of the adversarial bound and the proof of Theorem O
23

---

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: All results formalized in Theorems which we proof in the supplementary material additionally to selective proof outlines in the main body.
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 can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [NA]
Justification:
This is purely theoretical work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low 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 to 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
All assumptions are stated in the Theorem statements and the proof can be found the appendix.
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 a 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 or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of 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: [NA]
Justification: No experiments
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a 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 are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (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 to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer: [NA]
Justification:
No experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/ walpae//eeeuuumisiiiiiic...
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:
/ //nips. wttpccccppcccccceocc gwwc//gg///////eeeeeee /CodeSubmie / ssionnolll onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they 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 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: [NA]
Justification:
No experiments.
Guidelines:
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 be 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: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
26

---

It is OK to report 1-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 enrors 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 are out 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 to reproduce the experiments?
Question:
Answer: [NA]
Justification: No experiments.
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 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 make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /ttp///eerrp/.///ee cc http/plicc/ttiiccuueeeeeeoooeeee
Answer: [Yes]
Justification: Theoretical work without direct societal impact.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Theoretical work without societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or 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 to 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 to point out that improvement in the quality of generative models could be used to
27

---

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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal 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:
Theoretical work without experiments or data.
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 for 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
Are the creators 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?
Question:
Answer: [NA]
Justification: Theoretical work without existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
28

---

Answer: [NA]
Justification:
Theoretical work without new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 as details about compensation (if any)?
Answer: [NA]
Justification:
Theoretical work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Theoretical work.
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 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.
29


Reviews:
[{"review_id": "uVlaWi41gl", "reviewer": "Reviewer_Noj5", "summary": "The paper studies the multi-armed bandit (MAB) problem. The main focus is on the Prod algorithm, which is fundamentally considered to be sub-optimal for MAB settings. The authors challenge this conjecture by leveraging Prod's interpretation as a first-order Online Mirror Descent (OMD) approximation. They make following main contributions: first, they present variants of Prod that achieve optimal regret bounds for adversarial MABs. Second, they propose an algorithm that achieves best-of-both-worlds guarantees, showing logarithmic regret in the stochastic bandit setting. The authors emphasize the simplicity and efficiency of their approach, using arithmetic update rules instead of solving complex optimization problems. The paper systematically develops these ideas, starting from the problem definition and related work, moving through the theoretical analysis of the proposed modifications, and proof of their performance guarantees.", "questions": "Can you provide experimental results to illustrate the theoretical claims?\n\nHow does your algorithms compare with other algorithms in similar settings?", "limitations": "While the theoretical contributions are strong, the lack of empirical validation means that the practical effectiveness of the algorithms in environments remains to be seen.\n\nThe scope of the paper is restricted to multi-armed bandits, and the paper does not discuss the potential application of the proposed methods to other types of online learning problems.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper has following strengths:\n\n- The paper is well written and easy to understand\n- Authors provide a very good overview of the current literature related to the work presented in this paper\n- The paper challenges and disproves a long-standing conjecture about the sub-optimality of Prod in the context of MAB\n- Theoretical results appear to be correct", "weaknesses": "- One main weakness of the paper is that authors do not provide any experimental results. I highly encourage authors to provide experimental results to illustrate their theoretical claims\n\n- Another main weakness is that authors do not provide any comparison (discussion or results) with other algorithms that achieve optimal regret guarantees in similar bandit settings\n\n- Authors do not provide any discussion on real world applications of their algorithms\n\n- The focus of the paper is heavily theoretical, which might reduce its accessibility and usability for practitioners looking for direct application insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We address weaknesses and questions below:\n\nWeaknesses:\n\n--No experimental results: This is a purely theoretical paper. Our goal was to develop new variants of Prod which enjoy min-max optimal regret in the adversarial setting and instance-dependent optimal regret bounds in the stochastic setting.\n\n--Comparison with other algorithms: We are happy to include a clear discussion explaining that the algorithms are expected to perform very similarly to their FTRL/OMD counterparts (as seen from the regret bounds and the perturbation argument) but with the added benefit of having a closed form.\n\n--Real world application: The MAB problem is very well studied and there is a vast amount of literature on this topic which describes many real world applications. Our work proposes new, arguably simpler, algorithms for solving the MAB problem and as such has the same real world applications as prior MAB algorithms. For a good review of the MAB problem we point the reviewer to the Bandit Algorithms by Tor Lattimore and Csaba Szepesvari and Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems by Sébastien Bubeck, Nicolò Cesa-Bianchi\n\n--The focus of the paper is heavily theoretical: \nWhile our paper is indeed heavy in theory, we do not expect that it is less accessible to practitioners as our proposed algorithms are described well and easy to implement. We are happy to include complete pseudo-code in the appendix for our proposed algorithms. Further we plan to implement the suggestions of reviewer **r5go** to further improve the presentation\n\n\nQuestions:\n>Can you provide experimental results to illustrate the theoretical claims?\n\nAt this time we do not plan on conducting an empirical evaluation of our techniques.\n\n>How does your algorithms compare with other algorithms in similar settings?\n\nSee our comment regarding comparison with other algorithms.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "zYtQ6VqiK5", "reviewer": "Reviewer_rzG8", "summary": "This paper presents novel algorithms for the multi-armed bandit (MAB) problem that are shown to achieve optimal regret bounds even without relying on importance weighting. The authors introduce variants of the well-known Prod algorithm that are effective for both adversarial and stochastic settings, presenting significant improvements over existing state-of-the-art methods. Main contributions include disproving the conjecture that Prod-like algorithms are sub-optimal for bandits (that is, bandit feedback is shown not to be much harder than full information for algorithms in the Prod family), introducing a variant with nearly optimal regret, and achieving best-of-both-worlds guarantees with logarithmic regret in stochastic regimes.", "questions": "- For the stochastic regret guarantee of TS-Prod, do you require that the optimal arm is unique? If so, please be explicit about this assumption.\n- At lines 155-159, you state that an overcorrection is necessary. However, a correction term of order $\\\\eta/\\\\tilde{\\\\pi}\\_{t,i}$ instead of $\\\\eta\\\\ell\\_{t,i} / \\\\tilde{\\\\pi}\\_{t,i}$ could be one of the main factors that are preventing the achievement of first-order and second-order bounds. How much do you believe your current techniques for designing Prod-like algorithms prohibit achieving these guarantees?\n\nMinor comments/typos:\n- Line 7: “best-of-both-worlds” instead of “best-both-worlds”\n- Table 1: the first column is simply the negative entropy, and calling it “KL divergence” too might be confusing\n- Math display below line 130: the second equality should be an inequality if “Reg” is just an upper bound on the regret with the biased losses\n- Line 172: for example, $T > K \\\\log K$ should suffice in order to satisfy the condition $T > (K/2) \\\\log T$ (the latter is not an explicit condition on $T$).\n- Line 180: “be” instead of “be be”\n- Line 211: “poses” instead of “posses”\n- Line 214: “a fixed” instead of “a a fixed”\n- Line 227: in “intermediate potential between KL and Logbarrier”, negative entropy is the potential function (whose Bregman divergence is the KL)\n- Math display below line 360: $\\\\pi\\_{t,i}^2$ between parentheses after the first equality should be $\\\\pi\\_{t,i}$", "limitations": "The authors addressed potential limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The main results of achieving optimal regret bounds with variants of Prod and even optimal best-of-both-worlds guarantees are quite surprising and interesting. Even if the update rule of the proposed algorithm is extremely simple, this is shown to have a controlled effect on the regret via careful corrections.\nAdditionally, the paper is nicely structured and smoothly introduces the variants of Prod by providing intuitive reasoning behind their design.\n\nThe techniques adopted, together with the intuitions and the analogies provided, are also nontrivial and require a novel analysis template that has the potential to lead to simple algorithms with near-optimal guarantees for other online learning problems.", "weaknesses": "I have no major weaknesses to report. On a side note, having more details on the setting of incentive-compatible online learning would have been better, as it is a central motivation for this work. For instance, even just explicitly defining what a “proper scoring rule” is and more technical motivations as to why Prod-like algorithms are important in this setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We address weaknesses and questions below:\n\nWeaknesses:\n\n--More details on the setting of incentive-compatible online learning: We are happy to include more details for the incentive-compatible setting. We propose adding a quick overview which includes what constitutes a proper scoring rule together with extra motivation for why Prod algorithms are important for this setting in the main text and an extended discussion in the appendix. In fact a previous version of this work had a more careful discussion about the incentive-compatible framework and its motivation.\n\nQuestions:\n>For the stochastic regret guarantee of TS-Prod, do you require that the optimal arm is unique? If so, please be explicit about this assumption.\n\nYou are correct that our current analysis requires uniqueness of the optimal arm. We will state this explicitly. We expect that the techniques of Ito 2021 can be extended to our analysis which would allow for multiple optimal arms.\n\nIto, Shinji. \"Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds.\" Conference on Learning Theory. PMLR, 2021.\n\n>At lines 155-159, you state that an overcorrection is necessary...\n\nThis is a great question. The analysis for WSU-UX will also go through with the smaller bias of $\\eta \\ell_{t,i}/\\pi_{t,i}$. The reason we went with the larger bias is to keep the update linear in the losses which is important for the incentive compatible setting. However, we are not entirely sure if this is sufficient for small-loss bounds such as from Allenberg et al. 2006 (GREEN algorithm) because of the following. A quick calculation shows that the perturbation will contribute an additional term of $\\eta\\sum_{t=1}^T\\sum_{i=1}^K \\mathbb{E}[\\ell_{t,i}]$ instead of $\\eta TK$. We expect that the log-barrier based LB-Prod is a better candidate for second-order bounds or path bounds such as the ones derived in Wei and Luo 2018. or Ito 2021 as the algorithm does not introduce any perturbations.\n\nWe thank the reviewer for pointing out the typos and plan to implement the minor comment fixes as part of the final version of the paper.\n\nAllenberg, Chamy, et al. \"Hannan consistency in on-line learning in case of unbounded losses under partial monitoring.\" Algorithmic Learning Theory: 17th International Conference, ALT 2006, Barcelona, Spain, October 7-10, 2006. Proceedings 17. Springer Berlin Heidelberg, 2006.\n\nIto, Shinji. \"Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds.\" Conference on Learning Theory. PMLR, 2021.\n\nWei, Chen-Yu, and Haipeng Luo. \"More adaptive algorithms for adversarial bandits.\" Conference On Learning Theory. PMLR, 2018.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "4iRUREny3W", "reviewer": "Reviewer_zjT8", "summary": "Adversarial bandits have typically been solved through techniques such as online mirror descent or variants of multiplicative weight updates, but these might rely on some notion of importance-based weighting. To develop solutions free of such importance-weighting, the authors propose using the Prod algorithm, which serves as a simpler approximation of online mirror descent. Algorithms based on Prod can then be combined with Tsalis regularization to get a best-of-both-worlds guarantee, in both the adversarial and stochastic regimes.", "questions": "1. What is the benefit of using Prod/what is the rationale for studying this problem?", "limitations": "The paper lacks any limitations section. The authors write that the paper lacks a limitations section because it is \"purely theoretical work\", though I believe that limitations in the analysis or assumptions made should be pointed out even for theoretical work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. **Paper resolves open question** - As noted in the discussion in Section 6, the authors resolve an open question related to incentive compatibility and bandits posed by prior work. By resolving such a conjecture, they're able to provide a bridge between full-information and bandit settings. \n2. **Algorithm provides nice best-of-both-world guarantee** - Section 5 of the paper introduces an application of the Prod-based methodology using the Tsallis regularizer, and shows how this can achieve a best-of-both-worlds guarantee. While the connection with the previous sections, and the overall story of the paper, isn't super clear, the bounds proven in Section 5 provide some nice properties when using Prod.", "weaknesses": "1. **Unclear rationale behind using Prod** - Throughout the paper, the Prod algorithm is introduced and detailed, yet it is unclear why such an algorithm is necessary and the types of benefits brought upon by using such an algorithm. Early in the paper, the authors suggest that the simplicity of their update rules provides motivations for using Prod, but this motivation is not expanded upon, making it difficult to understand the motivation of the paper. \n2. **Unclear why importance weighting is undesirable** - Another rationale pointed out throughout the paper is that Prod can eliminate the need for performing importance weighting. However, it's unclear why such a property is desirable. The paper never details why we should eliminate importance weighting, and what the benefits are for algorithms that lack this. \n3. **Connection between Section 4 and 5 is unclear** - Section 4 of the paper details how Prod leads to a lack of importance weighting, while Section 5 details the best-of-both-worlds property with Prod. While both sections are interesting on their own, it is unclear how they each contribute to the main idea of the story. From my understanding, it seems to be the lack of a need to use importance weighting. In this case, it is not clear how Section 5 contributes to that story, and how Section 5 builds on the ideas from Section 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We address weaknesses and questions below:\n\nWeaknesses:\n--Unclear rationale behind using Prod: As we have already stated the Prod updates are simple and closed form, that is they do not require solving an optimization problem at every step. Prod type algorithms have been previously used for Online Learning problems but they were not known to be optimal in the partial information setting. As we have pointed out in the paper, there was even a conjecture that Prod style updates can not achieve the optimal min-max regret in the adversarial setting. We think that this alone makes Prod style algorithms interesting enough to study. Further, we are able to show the **first** importance weighting free algorithm for bandits which is also a very interesting contribution by itself. Finally, this specific type of Prod updates allows for solving the incentive compatible bandit problem studied by Freeman et al. 2020\n\n--Unclear why importance weighting is undesirable: The benefit is simple and we have already highlighted that in lines 161-162 in Section 4. To reiterate, importance weight free algorithms do not need to control the players probabilities in any way. Further, such algorithms will only have to deal with bounded losses.\n\n--Connection between Section 4 and 5 is unclear: The best-of-both worlds problem has been well motivated and studied, see *Sebastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits* and *Zimmert and Seldin. Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits*. Whenever a new bandit algorithm is introduced it is natural to ask if that algorithm will perform well in both stochastic and adversarial settings.\n\nQuestions:\n>What is the benefit of using Prod/what is the rationale for studying this problem?\n\nSee our answers above.\n\nLimitations:\n>The paper lacks any limitations section...\n\nFirst, we want to point out that we have stated all assumptions clearly. Second, we believe our theoretical results do not hide any limitations of the algorithms and are stated in a formal and sound way. We welcome any further feedback about what limitations we have failed to address in terms of our theory. The reviewer has given a score of 2 for the soundness of our results. We would like to address any soundness concerns and welcome any feedback on which part of our paper is not sound.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "tRYK92QNNY", "reviewer": "Reviewer_r5go", "summary": "This paper revisits the simple PROD-type algorithms, originally introduced by Cesa-Bianchi et al. in 2007 for online learning under full feedback, and does an excellent job in doing so. Specifically, the authors demonstrate that some version of these algorithms can achieve optimality even for the $K$-armed bandit problem. They show that three different types of prod algorithms can achieve optimality. Interestingly, one of these algorithms can be seen as the first multi-armed bandit algorithm that solves the problem and does not rely on importance weighting. Notably, one of these algorithms also enjoys best-of-both-worlds guarantees. As another significant corollary of their work, the paper refutes a conjecture by Freeman et al. (2020) about incentive-compatible multi-armed bandits being intrinsically more difficult than regular multi-armed bandits.", "questions": "Do you believe that your techniques can be applied to other problems, such as contextual/linear/combinatorial bandits, or to feedback graph and partial monitoring? Do you foresee any challenges in adapting these techniques beyond the domain of classic multi-armed bandits?", "limitations": "I believe that this category does not apply to a paper which is entirely theoretical.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "1) The paper provides valuable insights about how to generate PROD-type algorithms as first-order OMD approximation with biased losses of classic multi-armed bandits algorithms.\n2) The paper provides the first importance-weighting free algorithm to solve the multi-armed bandits problem.\n3) The paper solves (negatively) a conjecture about incentive-compatible multi-armed bandits being more difficult than ordinary multi-armed bandits.\n4) The paper provides a PROD-type algorithm that enjoys BOBW guarantees.", "weaknesses": "The presentation targets a specialized audience, assuming the reader is well-versed in template proofs of OMD (Online Mirror Descent) and FTRL (Follow-The-Regularized-Leader) algorithms, as well as techniques such as \"change of measure\".\nTo enhance accessibility for less experienced readers, consider adding dedicated appendices or providing precise references to relevant literature where these templates/definitions/techniques can be found. These additions can help guide readers through the nuances of the paper, broadening the potential audience of the paper, which I believe deserves to be broad.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We address weaknesses and questions below:\n\nWeaknesses:\n\n--The presentation targets a specialized audience: Thank you for the suggestion. We agree that the presentation in the main paper is quite technical. We are happy to add an appendix which describes the standard analysis of OMD and gives a quick overview of “change of measure” trick. Further, for a more thorough example of the change of measure trick we will point the reader to the works of *Dylan J. Foster, Claudio Gentile, Mehryar Mohri, Julian Zimmert. Adapting to Misspecification in Contextual Bandits* and *Haipeng Luo, Chen-Yu Wei, Chung-Wei Lee. Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses*.\n\nQuestions:\n> Do you believe that your techniques can be applied to other problems, such as contextual/linear/combinatorial bandits, or to feedback graph and partial monitoring? Do you foresee any challenges in adapting these techniques beyond the domain of classic multi-armed bandits?\n\nWith regards to the online learning with graph feedback setting we expect that the results will transfer over in a somewhat straightforward way, at least for the adversarial setting. With regards to the contextual/linear bandit setting it is perhaps possible to come up with a similar update for log-barrier type algorithms. One challenging aspect might be extending our results to small loss bounds due to the way we bias the rewards in WSU-UX, see also our response to reviewer **rzG8**.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "9229qHPc7F", "reviewer": "Reviewer_1VVH", "summary": "This paper first considers incentive-compatible online learning problem, which is first considered in [Freeman et al., 2020]. Specifically, the original WSU-UX algorithm only achieves $O(T^{2/3})$ regret shown in [Freeman et al., 2020]. By injecting a bias in the loss estimator constuction to the original WSU-UX algorithm, the authors achieve $O(\\sqrt{KT\\log K})$ regret for this problem. The added biases can be viewed as certain second-order approximation of the orginal exponential weight algorithm. Besides this algorithm, the authors also propose another algorithm which is still incentive-compatible and interestingly does not use the inverse propensity weighting. The authors show that the LB-Prod algorithm is similar to FTRL with log-barrier regularizer and also achieves $O(\\sqrt{KT\\log T})$ optimal regret. The authors also consider the Tsallis entropy variant of this Prod-type algorithm and achieve best-of-both-world guarantee for multi-armed bandits in adversarial and stochastic environments.", "questions": "- Can the authors explain more on what difficulties are if one uses OMD with Logbarrier and perturbation analysis to analyze LB-Prod?\n\n- Whether there is also an inverse-propensity-weighting-free version of Tsallis-Prod that achieves BOBW for adversarial MAB?\n\n- Can the authors explain more about how the added bias in the modification of WSU-UX algorithm is related to the second-order approximation of MWU? Does this similarity come from the algorithm dynamic or the analysis perspective?\n\n- Can the stochastic regret bound for Tsallis-Prod be improved to optimal?", "limitations": "See \"weakness\" and \"questions\".", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- This problem resolves an open problem proposed in [Freeman et al., 2020], achieving $O(\\sqrt{T})$-type regret guarantee for incentive-compatible online learning with bandit feedback. The proposed two Prod-type algorithms in the bandit feedback setting are very interesting to me. The relationship between LB-Prod and FTRL with log-barrier regularizer shown in the analysis is also new to me.\n\n- The proposed Tsallis variant of Prod algorithm is also interesting since most previous BOBW algorithm relies on the FTRL framework.", "weaknesses": "I do not find main weakness of this paper but I have some concerns on the results and some configurations of the algorithms.\n\n- While the authors argue that the added bias in the first algorithm is related to the second-order approximation of the exponential weight algorithm, I still have difficulty understanding why the bias is of this form.\n\n- In Section \"perturbation analysis\", the authors argue that there is an equivalence between LB-Prod and LB-FTRL with a shifted loss. I wonder whether the standard OMD analysis also works? This can make the relationship between LB-Prod and LB-FTRL clearer.\n\n- The BOBW regret for the stochastic environment is a bit away from the optimal due to the additional $K/\\Delta_{\\min}$ lower order term.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We address weaknesses and questions below:\n\nWeaknesses:\n\n--Difficulty understanding the form of the bias: The exponentiated weights/hedge algorithm update can be written as the first equality after line 149, where $\\lambda_t$ is the normalization factor which makes $\\pi_{t+1}$ a probability distribution. The second order approximation intuitively replaces the exponential by its second order Taylor expansion. That is we exactly write the exponential as a Taylor series and then just truncate to the quadratic term.\n\n--Section \"perturbation analysis\": We believe that the reviewer means there is an equivalence between LB-Prod and LB-OMD. There indeed is such an equivalence and one can use the standard OMD analysis, however, it would be on a perturbed version of the losses. It turns out we can control these perturbations so the analysis will go through. We analyze a version of TS-Prod precisely in this way in Appendix D.\n\n--BoBW regret: The lower order term $\\frac{K}{\\Delta_{\\min}}$ only shows up in the analysis for the algorithm presented in Appendix D and we believe this to be a shortcoming of our analysis. The term does not show up for the algorithm presented in Section 5 with regret bound in Theorem 3.\n\nQuestions:\n>Can the authors explain more on what difficulties are if one uses OMD with Logbarrier and perturbation analysis to analyze LB-Prod?\n\nThe analysis is not significantly more difficult. We refer the reviewer to Appendix D, Lemma 13 for an idea of how one can bound the perturbations. This lemma is stated for a variant of TS-Prod, however, a similar result can be derived for LB-Prod.\n\n>Whether there is also an inverse-propensity-weighting-free version of Tsallis-Prod that achieves BOBW for adversarial MAB?\n\nWe are not sure that this is possible. We have heavily used the form of the log-barrier potential update when deriving the result for LB-Prod.\n\n>Can the authors explain more about how the added bias in the modification of WSU-UX algorithm is related to the second-order approximation of MWU? Does this similarity come from the algorithm dynamic or the analysis perspective?\n\nSee our answer in the weaknesses part of the rebuttal.\n\n>Can the stochastic regret bound for Tsallis-Prod be improved to optimal?\n\nThe bound is already asymptotically optimal. We note that our analysis does not tackle the multiple best arms setting, however, we believe that the work of Ito 2021 can be used to derive regret bounds in this setting as well, see our response to reviewer *rzG8* as well. The only other sub-optimality of the presented bound in Theorem 3 is in terms of some constant scalar factors which could potentially be tightened.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their careful reviews and suggestions on how to improve our work. We address each of the comments regarding weaknesses and each of the questions separately under the respective reviewer.

Meta-review: This paper considers the bandit problem, specifically the Prod algorithm, which updates a constant share based on the loss function. Due to its linearity with respect to the loss function, it is incentive-compatible (e.g., [Freeman et al. 2020]) in the sense that minimizing the expected loss maximizes the weight in the next round. An existing algorithm called WSU-UX has a $T^{2/3}$ regret bound in the adversarial case, but this paper shows that a modified loss function can eventually lead to a $\sqrt{KT}$ bound as well as a rate-optimal stochastic bandit bound. All reviewers are positive about the paper. I recommend that the authors prepare the camera-ready version that incorporates reviewers' suggestions.
Decision: Accept (poster)