PRODuctive bandits: Importance Weighting No More

Authors: julian  zimmert
teodor v marinov
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 07:29:51

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.

Main paper: 
 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 is EXP3 [Auer et al., 2002b] . EXP3 is a direct adaptation of the Hedge algorithm [Littlestone and Warmuth, 1994 , Cesa-Bianchi et al., 1997 , Freund and Schapire, 1997] with importance weighting to handle partial bandit feedback. Hedge and EXP3 are special versions of online mirror descent (OMD), where the Bregman divergence is the KL 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. A 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-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 [Littlestone and Warmuth, 1994] to non-binary feedback.More recently, Freeman et al. [2020] studied incentive-compatible online learning, a setting where experts are not necessarily truthful but make predictions strategically with regard to the agent's algorithm. Motivated by deriving an algorithm where the incentives of experts align with the agent, they propose WSU which can be seen as an instance of Prod. Freeman et al. [2020] further introduce a bandit adaptation WSU-UX, the first Prod algorithm for bandits. Unfortunately, WSU-UX only enjoys T 2 3 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 a fundamental separation between full-information and bandits.We make the following contributions for understanding Prod under bandit feedback:1. We disprove the separation conjecture by providing a simple modification of WSU-UX with nearly optimal O( KT log(K)) regret guarantees. 2. We present a Prod variant that does not require importance weighting and yet enjoys O( KT log(T )) regret bounds.3. We present a Prod variant that achieves best of both worlds regret guarantees, i.e. it enjoys improved O(log(T )) regret bounds when the losses are stochastic, while maintaining worstcase O( √ KT ) regret bounds.Notation: For N ∈ N, let [N ] = {1, . . . , N }. We use •, • to denote the regular Euclidean scalar product and ∆(A) to denote the probability simplex over a finite set A. O is the standard Landau notation hiding numerical constants, while O omits polylogaritmic factors as well. The expectation E is always taken over all randomness of the algorithm, losses and experts, whileE t [•] = E[• |F t ],where F t is the filtration over all randomness up to step t. I(E) denotes the indicator function function for the event E. For a convex differentiable function F , the Bregman divergence is defined by D F (y, x) = F (y) -F (x) -y -x, ∇F (x) . 
problem setting and related work: 
 The adversarial bandit problem is formally defined as follows. In every round t = 1, . . . , T , an (oblivious) adversary selects a loss t ∈ [0, 1] K (it is possible to extend the loss range to [-1, 1] K ) unknown to the agent. The agent simultaneously selects an expert A t ∼ π t , π t ∈ ∆([K]). The agent incurs and observes the loss t,At , but does not see the losses of other experts. The goal is to minimize the pseudo-regret1 Reg = maxi∈[K] E T t=1 t,At -t,i = max u∈∆([K]) E T t=1 π t -u, t ,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: ˆ t,i = t,i πt,i I(A t = i). We note that other types of importance weighted estimators have been used in literature such as 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 K → R and a learning rate schedule η t , the agent maintains a distribution viaEQUATIONOMD optimizes locally given the last loss and, as we will show, is most closely related to Prod. FTRL on the other hand performs a global optimization and is generally considered superior for adaptive bounds with time-dependent learning rates. In some special cases, such as time-independent learning rate with potentials that satisfy ∇F (x) → ∞ on the border of the optimization set, both algorithms are equivalent. Common potentials in the bandit literature are given in Table 1 and we refer to their respective Bregman divergences as D KL , D T S and D LB respectively. The negative entropy is the potential which defines Hedge and Exp-3 (and derivatives) [Littlestone and Negentropy/KL divergence 1/2-Tsallis Entropy Logbarrier F (π)K i=1 π t,i log(π t,i ) -2 K i=1 √ π t,i - K i=1 log(π t,i) Table 1 : Common potential functions Warmuth, 1994 , Vovk, 1995 , Freund and Schapire, 1997 , Auer et al., 2002b , Kocák et al., 2014] . The 1/2-Tsallis Entropy is the key to achieving optimal best-of-both-worlds 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.The original version of Prod [Cesa-Bianchi et al., 2007 ] maintains weights w t,i for each experts which are updated via w t+1,i = w t,i (1 -η t,i ) and the agent plays the policy π t,i ∝ w t,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 ML-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 1 and hence operate directly on the policy space. In its simplest form, this isπ 1,i = 1 K , π t+1,i = π t,i (1 -η( t,i -λ t )) , λ t = K j=1 π t,j t,j . (Vanilla-Prod/WSU)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 π t+1,i = π t,i (1 -ηL t,i ( t ; A t )), where L t,i are linear affine functions of the loss. From now on we always assume the initial policy is π t,i = 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 incentive-compatibility.In the incentive-compatible 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 an internal belief and the agent would like to receive each expert'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 b t,i ∈ [0, 1] about the t-th round outcome. The expert's belief is unknown to the agent and the expert only reports a prediction p t,i ∈ [0, 1] about the outcome. Based on the expert predictions, {p t,i } i∈[K] the agent makes a prediction based on pt = K i=1 π t,i p t,i and incurs a loss L(p t , r t ) ∈ [0, 1] based on the realized outcome r t ∈ {0, 1}. In the weather forecasting example the outcome is the indicator if it rains the next day and the loss is L(p t , r t ) = (r t -pt ) 2 . 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 is b t,i may differ from p t,i . The agent's goal of receiving the true beliefs, {b t,i } i∈ [K] , can be achieved by playing an incentive compatible strategy which will always prefer selecting an truthful expert, that is the probability of π t+1,i of selecting expert i when the expert reports b t,i may only decrease if the expert reports any other p t,i 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 et al. [2020] show that standard OMD and FTRL algorithms are in fact not incentive compatible even when the loss L is restricted to be proper that isE r∼Bern(b) [L(p, r)] ≥ E r∼Bern(b) [L(b, r)]for all p = b. It turns out that any update for π t+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-compatible. The state of the art for incentive-compatible bandits is T 2 3 regret and any improvement for Prod directly transfers to better rates for this setting as well. 
modifying wsu-ux for nearly optimal regret guarantees: 
 We begin by presenting a minimal modification of Algorithm WSU-UX which is sufficient for a regret guarantee of the order O( KT log(K)).WSU-UX uses importance-weighted updates and injects a small uniform exploration.πt,i = γ K + (1 -γ)π t,i , A t ∼ πt,i , ˆ t,i = I(A t = i) t,i πt,i π t+1,i = π t,i (1 -η( ˆ t,i -λ t )) , λ t = K j=1 π t,j ˆ t,j , (WSU-UX)where γ is the mixture coefficient. The role of uniform exploration is to ensure that the policy updates are proper i.e. π t+1,i ∈ (0, 1). Freeman et al. [2020] uses the following key lemmas in their analysis, which hold for any sequence of losses t ∈ [0, 1] K . For completeness we restate the results we use below.Lemma 1 (Lemma 4.1 [Freeman et al., 2020] ). If ηK/γ ≤ 1 2 , the WSU-UX weights π t and πt are valid probability distributions for all t ∈ [T ]. Lemma 2 (Lemma 4.3 [Freeman et al., 2020] ). For WSU-UX, the probability vectors {π t } t∈[T ] and loss estimators ˆ t satisfy the following second order-boundT t=1 K i=1 π t,i ˆ t,i - T t=1 ˆ t,i ≤ log(K) η + η T t=1 ˆ 2 t,i + η T t=1 K i=1 π t,i ˆ 2 t,i ,where i is the optimal expert/arm.The bound in Lemma 2 is almost the standard regret bound that appears in the analysis of Hedge, except for the term η T t=1ˆ 2 t,i . This term is the reason why prior work can not show regret bounds smaller than T 2 3 . Even after taking the expectation over the randomness of the agents actions, this term scales with with 1/π t,i , which is potentially unbounded. Alternatively this term can be written as E j∼π t [η ˆ 2 tj ] (where π is the policy picking i with probability 1) and if one could perform a change of measure to E j∼πt t [η ˆ 2 tj ], 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 a bias to the losses ˜ t = t + δ t , which satisfies the same regret guarantee, Reg, as the original loss sequence, then running an algorithm over the biased loss sequence ˜ t which selects A t ∼ πt ensuresE T t=1 t,At -t,i = E T t=1 ˜ t,At -˜ t,i + δ t,At -δ t,i * = Reg + E    T t=1 (E j∼πt t [δ t,j ] -E j∼π t [δ t,j ] change of measure )    .We introduce now the following modification to the lossesEQUATIONwhich corresponds to δ ti = η ti πt,i . This yields the change of measure termE j∼πt t [δ t,j ] -E j∼π t [δ t,j ] = K i=1 η ti -E j∼π t η tj πtj ≤ ηK -E j∼π t [η ˆ 2 tj ] ,which is sufficient for controlling the term η T t=1ˆ 2 t,i in Lemma 2.Theorem 1. Running WSU-UX with the loss estimators in Equation 1 and γ = ηK 2 , η = Θ( log(K) KT ) guarantees the following regret boundT t=1 E[ t,At -t,i ] ≤ O( KT log(K)).The proof of Theorem 1 is deferred to Appendix B.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 a divergence function D is follows the template2 EQUATIONwhere the inequality crucially relies on π OMD 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 π OMD t an approximate policy π t ≈ π OMD t is played, the template regret analysis can be changed by adding the termsη -1 (D(π , π t+1 ) -D(π , π OMD t+1 )), where π OMD t+1 is now the 1-step OMD update from π t . When D is the KL divergence and the approximate policy π t is coming from the WSU-UX, this term contributes the undesirable η ˆ 2 t,i . We now explain how our loss biasing solves this issue. The Vanilla-Prod/WSU update can be seen as a first order approximation to the Hedge update, that isπ OMD t+1,i = π t,i exp(-η( ˆ t,i -λ t )) ≈ first-order π t,i (1 -η( ˆ t,i -λ t )) = π t,i ,where λ t is a normalization factor. Tuning λ t such that K i=1 π t+1,i = 1 recovers Vanilla-Prod/WSU. To control the undesirable terms, we have to make the approximation tighter. The loss-biasing introduced in the previous section acts as a correction which brings the Vanilla-Prod/WSU update closer to the second order approximation of the Hedge update. Indeed, we haveπ OMD t+1,i = π t,i exp(-η( ˆ t,i -λ t )) ≈ second-order π t,i 1 -η( ˆ t,i -λ t ) + η 2 2 ( ˆ t,i -λ t ) 2 = π t,i 1 -η( ˆ t,i -λ t ) 1 - η 2 ( ˆ t,i -λ t ) ,and so our loss adjustment in Equation 1, ˜ t,i = t,i (1 -η/π t,i ), can be seen as a second order correction to the term η 2 2 ( ˆ t,i -λ t ) 2 . 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 as necessary. That is, the correction term we use is of the order η/π t,i instead of η t,i /π t,i . Fortunately, the regret analysis is not sensitive towards this as we have shown in Theorem 1. 
importance weighting free adversarial mab with lb-prod: 
 While our biased WSU-UX obtains optimal regret, it still has to 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 a Prod version based on the Logbarrier leads to a surprisingly simple algorithm without loss biasing that is arguably importance weighting free. LB-Prod differs from WSU-UX by using the masked loss ˜ t,i = t,i I(A t = i) instead of the importance weighted loss and a non-symmetric normalization λ t,i :π t+1,i = π t,i (1 -η( ˜ t,i -λ t,i )), λ t,i = π t,i π t,At t,At K j=1 π 2 t,j . (LB-Prod) It is easy to confirm ˜ t,i -λ t,i ∈ [-1, 1] via π t,i π t,At ≤ (π 2 t,i + π 2 t,At)/2 yielding proper updates for η < 1. The following theorem shows that this simple algorithm is rate optimal under the right tuning. Theorem 2. For any sequence of losses t ∈ [-1, 1] K and any η < 1, LB-Prod produces valid distributions π t ∈ ∆([K]) and its regret is bounded byT t=1 E[ t,At -t,i ] ≤ 2 + K log(T ) η + 2ηT 1 -η . Tuning η = log(T )K 2T results in a regret bound of O( KT log(T )) for any T > K log(T ). The proof of Theorem 2 is deferred to the end of the section.As mentioned before, LB-Prod is the linear approximation of OMD with Bregman divergence induced by the Logbarrier potential, that is D LB induced by the potential fuctionF (x) = - K i=1 log(x i ).The one-step Logbarrier OMD update of a policy π t with importance-weighting is known (see e.g. [Zimmert and Seldin, 2021] ) to take the formπ OMD t+1,i = π t,i 1 + ηπ t,i ( ˆ t,i -λ t ) ≈ π t,i (1 -ηπ t,i ( ˆ t,i -λ t )) = π t+1,i ,where λ t is a normalization constant that ensures π OMD t is a probability distribution. If instead λ t is tuned so that K i=1 π t+1,i = 1, the LB-Prod update is recovered. This can be be verified by setting ˜ t,i = π t,i ˆ t,i and λ t,i = π t,i λ t . The curvature of the Logbarrier regularization is what ensures that the importance weighted loss ˆ t,i is always multiplied with its probability π t,i , allowing to run the algorithm on the masked non-weighted loss sequence directly.Additionally, the second order approximation isπ OMD t+1,i = π t,i 1 + ηπ t,i ( ˆ t,i -λ t ) ≈ second-order π t,i (1 -ηπ t,i ( ˆ t,i -λ t ) + η 2 π 2 t,i ( ˆ t,i -λ t ) 2 ) .The additional undesirable terms, unlike in the case for WSU-UX, will only contribute ηT regret if not adjusted for as we show next.The following technical lemma is proven in the appendix. Lemma 3. For any timestep t and arm i, it holdsE t [ ˜ t,i -λ t,i ] = π t,i ( t,i -c t ) , E t [( ˜ t,i -λ t,i ) 2 ] ≤ 2π t,i , where c t ∈ [-1, 1] is an arm independent constant.In Section 3.1 we argued that one needs to bound the additional term η -1 (D LB (π , π t+1 ) -D LB (π , π OMD t+1 )) to reduce the analysis to standard OMD. While this term is nicely bounded for LB-Prod, it turns out that it is easier to directly bound the "prototype" of the stability term in Equation ( 2) due to the fact that we have a closed form expression of π t+1 . Lemma 4. For any time t ∈ [T ] and any u ∈ ∆([K]), it holdsπ t -u, t + E t η -1 D LB (u, π t+1 ) -η -1 D LB (u, π t ) ≤ 2η 1 -η .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 thatK i=1 π t+1,i = K i=1 π t,i -ηπ t,At t,At + η K j=1 π t,At π 2 t,j K k=1 π 2 t,k t,At = K i=1 π t,i = • • • = K i=1 π 1,i = 1 .Additionally we have seen that | ˜ t,i -λ t,i | ≤ 1, hence for any η < 1, the probability of any arm is strictly positive. For any comparator u , we defineu = u + 1 T (π 1 -u ), which satisfies T t=1 u -u , t ≤ 2.Using Lemma 4 and Equation ( 2), we obtain by the telescoping sum of Bregman termsE T t=1 π t -u, t ≤ 4ηT 1 -η + η -1 E [D LB (u, π 1 ) -D LB (u, π T +1 )] ≤ 4ηT 1 -η + K log(T ) η .We outline an alternative analysis that reuses established machinery and might be more accessible for some readers. Our analysis begins by viewing the Prod update as an exact OMD update over a perturbed loss sequence. Indeed, there is a sequence of perturbations{ t } t∈[T ] , t ∈ R K , such that π OMD t+1 = π t,i 1 + ηπ t,i ( ˆ t,i -t,i -λ t ) = π t,i (1 -ηπ t,i ( ˆ t,i -λ t )) = π t+1,i .The exact form of t,i satisfies the followingt,i = ηπ t,i ( ˆ t,i -λ t ) 2 1 + ηπ t,i ( ˆ t,i -λ t ) , | E t [ t,i ]| = O(η) .Since Prod is exactly OMD over the sequence ˆ tt , we can decompose the regret as followsE t=1 π t -u, ˆ t = E t=1 π t -u, ˆ t -t + E t=1 π t -u, t = Reg OMD +O(ηT ) .The analysis is not entirely straightforward as the loss range for the OMD update becomes [-1 -O(η), 1 + O(η)] 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 a fixed distribution over [0, 1] K , 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 is FTRL with 1/2-Tsallis entropy and η t ∝ 1/ √ t learning rate.Recall the 1/2-Tsallis regularizer isF (x) = - K i=1 2 √ x i .Unlike OMD, FTRL is not canonically expressed as a 1-step update of the previous policy. Instead, the 1/2-Tsallis-INF policy is given with a normalization constant Λ t (see [Zimmert and Seldin, 2021] )π FTRL t+1,i = Λ t+1 + η t t s=1 ˆ s,i -2.Recursively using this expression yieldsπ FTRL t+1,i = Λ t+1 + η t η t-1 ( 1 π FTRL t,i -Λ t ) + η t ˆ t -2 = π FTRL t,i 1 + η t π FTRL t,i ( ˆ t - η t ξ t π FTRL t,i -λ t ) -2,where ξ t = 1 η 2 t -1 ηtηt-1 and λ t = Λ t+1 -ηt ηt-1 Λ t .The first order approximation isπ FTRL t+1,i ≈ 1st-order π FTRL t,i (1 -2η t π FTRL t,i ( ˆ t,i -ξ t / π FTRL t,i -λ t )) .We ensure following the approximation in expectation by directly biasing the losses with η t ξ t / √ π t,i .Additionally, one needs to perform a second-order correction as discussed in Section 3.1. We omit a formal derivation, but notice that WSU-UX required η/π t,i correction, while LB-Prod works without correction because the error is of order η. As the intermediate potential between KL and Logbarrier, Tsallis-INF turns out to require a correction of order η/ √ π t,i , which we tighten by an additional factor of (1 -π t,i ) necessary to ensure stochastic bounds.With this, we are ready to presentˆ t,i = t,i - η t (ξ t + γ(1 -π t,i ) √ π t,i I(A t = i) π t,i , λ t = K i=1 π 3 2 t,i ˆ t,i K j=1 π 3 2 t,j , ξ t = 1 η 2 t - 1 η t η t-1 , π t+1,i = π t,i (1 -2η t √ π t,i ( ˆ t,i -λ t )) . (TS-Prod) Theorem 3. The regret of TS-Prod with η t = 1 √ K+26t , γ = 13 2 is bounded by O( √ KT + K log(T ))in the adversarial setting and byO i =i log(T ) ∆iin the stochastic setting.We first show that the loss biasing is sufficient to ensure that the distribution is well defined. Lemma 5. If ξ t is a non-increasing sequence, η t < 2 √ K(ξt+γ) 2 and η 2 t+1 ≤ η 2 t (1 -2γη 2 t ) for all t, then the update rule of TS-Prod is proper and satisfies π t,i > (ξ t + γ) 2 η 2 t for any arm and loss sequence at all time steps.Next we present the moving parts of the analysis.T t=1 π t -u, t ] = T t=1 E π t -u, t -ˆ t change of measure + D T S (u, π t ) -D T S (u, π t+1 ) η t proto-penalty + π t -u, ˆ t - D T S (u, π t ) -D T S (u, π t+1 ) η t proto-stabilityThe change of measure is by construction change-of-measureEQUATIONWe now bound the stability and penalty. Lemma 6. For any time t such that π t,i > (ξ t + γ) 2 η 2 t , it holdsπ t -u, E t [ ˆ t ] + E t D T S (u, π t+1 ) η t - D T S (u, π t ) η t ≤ 13 2 η t u i √ π ti (1 -π ti ) .The tuning of Theorem 3 satisfies the conditions.Lemma 7. The proto-penalty is bounded byT t=1 D T S (u, π t ) -D T S (u, π t+1 ) η t ≤ T t=1 η t ξ t   i =i 2 √ π ti + K i=1 u i -π ti √ π ti  We are ready to prove the main regret guarantee.Proof of Theorem 3. By Lemma 5 we have a proper update rule. Using Lemma 6, equation ( 3), where we tuned γ = 13 2 and Lemma 7 yieldsE T t=1 π t -u, t ≤ E   T t=1 η t   K i=1 13 2 √ π t,i (1 -π ti ) + i =i ξ t √ π t,i     .The adversarial regret follows fromK i=1 √ π t,i ≤ √ K, ξ t ≤ 4, T t=1 η t = O( √ T ).For the stochastic regret, the proof follows standard arguments using the self-bounding trick as in Zimmert and Seldin [2021] . For details on the self-bounding trick see the supplementary material.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 et al. [2022] . In Appendix E, we formalize this connection and present a slight variation of TS-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-Tsallis entropy enjoys best-of-both worlds regret guarantees which to the best of our knowledge is novel. 
discussion: 
 We have provided an extensive study of incentive-compatible bandits. We have negatively resolved an open question of whether incentive-compatibility as defined in 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 bestof-both-world guarantees. Our algorithms are 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.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. We give a 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-Shwartz [2012], Chapter 5 of Hazan et al. [2016] or Chapter 28 of Lattimore and Szepesvári [2020] .The OMD updateπ t+1 = arg min π∈∆([K]) π, η t ˆ t -D F (π, π t ) (OMD)can be written in two steps asπt+1 = arg min π∈R K π, η t ˆ t -D F (π, π t ) π t+1 = arg min π∈∆([K]) D F (π, πt+1 ),where the first step is an unconstrained optimization over the linear loss at time t together with a 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∇F (π t+1 ) = ∇F (π t ) -η t ˆ t ,Let F t = 1 ηt . Since π t+1 is the minimizer of the OMD update, and D F w is convex we have thatπ t+1 -π, ˆ t ≤ u -π t+1 , ∇F t (π t+1 ) -∇F t (π t ) = D Ft (u, π t ) -D Ft (u, π t+1 ) -D Ft (π t+1 , πt ).Further, it holds thatπ t -π t+1 , ˆ t = D Ft (π t+1 , π t ) + D Ft (π t , πt+1 ) -D Ft (π t+1 , π t+1 ) ≤ D Ft (π t+1 , π t ) + D Ft (π t , πt+1 ).Combining the two inequalities together we have that one step of the regret to any u ∈ ∆([K]) is bounded asˆ t , π t -u ≤ D Ft (u, π t ) -D Ft (u, π t+1 ) + D Ft (π t , πt+1 ).For a fixed step-size η t = η the above telescopes to bound the regret asT t=1 ˆ t , π t -u ≤ D F (u, π 1 ) -D F (u, π T ) η + 1 η T -1 t=1 D F (π t , πt+1 ).As long as F is twice differentiable, each of the terms can be bounded asD F (π t , πt+1 ) ≤ O(η 2 ˆ t 2 ∇ 2 (F * )(wt) ), where F * is the Fenchel conjugate of F . Controlling ˆ t 2 ∇ 2 (F * )(wt)in OCO is usually done by assuming some boundedness of the losses. In bandit literature controlling this term is slightly more involved and depends on the choice of F . When η 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 η t = 1 √ t . Fang et al. [2022] introduce a stabilization term to the OMD update which overcomes this problem and show that this new version does enjoy the standard OMD regret guarantees.The FTRL analysis follows similar ideas, however, the one step regret is bounded asˆ t , π t -u ≤ (F t + I ∆([K]) ) * (-Lt-1 ) -(F t + I ∆([K]) ) * (-Lt ) + 1 η t D F * (-Lt , -Lt-1 ),where Lt = t-1 s=1ˆ t , andI ∆[K] is the characteristic function of ∆ [K] , i.e., I ∆[K] (π) = 0 if π ∈ ∆[K] and I ∆[K] (π) = +∞ otherwise. The term D F * (-Lt , -Lt-1) can be thought of as the equivalent to D F (π t , πt+1 ) in the OMD analysis. The term(F t + I ∆([K]) ) * (-Lt-1 ) -(F t + I ∆([K]) ) * (-Lt ) needs to be telescoped in an appropriate way. For more details we refer the reader to the penalty term bound of Zimmert and Seldin [2021] .Proof of Theorem 1. 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 t=1 K i=1 π t,i E[ ˆ 2 t,i |F t-1 ] ≤ ηT K 1 -γ ≤ 2ηT K, η T t=1 E[ ˆ 2 t,i * ] ≤ η T t=1 E ˜ 2 t,i * πt,i * ≤ η T t=1 E 2 t,i * πt,i * ,where F t-1 is the filtration generated by the random play and randomness of the losses up to time t -1. We now consider the expectation of the LHS which evaluates toT t=1 K i=1 E[π t,i ˆ t,i ] - T t=1 E[ ˆ t,i * ] = T t=1 K i=1 E[π t,i ˜ t,i ] - T t=1 E[ ˜ t,i * ] = T t=1 K i=1 E[π t,i t,i ] - T t=1 E[ t,i * ] + T t=1 E η t,i * πt,i - T t=1 K i=1 E ηπ t,i t,i πt,i ≥ η T t=1 E 2 t,i * πt,i -2ηT K + T t=1 K i=1 E[π t,i t,i ] - T t=1 E[ t,i * ].Thus combining the bounds on the LHS and RHS we haveT t=1 K i=1 E[π t,i t,i ] - T t=1 E[ t,i * ] ≤ log(K) η + 4ηT K + η T t=1 E 2 t,i * πt,i -η T t=1 E 2 t,i *πt,i .To complete the proof we only note thatT t=1 K i=1 E[π t,i t,i ] - T t=1 E[ t,At ] ≤ 2T γ = ηKT .Proof of Lemma 3. The expectation of ˜ ti = ti I(A t = i) is obviously π ti ti , hence by the definition of λ ti , we haveE t [ ˜ ti -λ ti ] = π ti ti - K j=1 π 2 tj tj K j=1 π 2 tj .For the second part, we haveE t [( ˜ ti -λ ti ) 2 ] ≤ E t [ ˜ 2 ti ] + E t [λ 2 ti ] = π ti    2 ti + π 2 ti K j=1 π 3 tj 2 tj K k=1 π 2 tk 2    ≤ π ti   1 + π ti K j=1 π 3 tj K k=1 π 2 tk 2    .The proof is completed by notingπ ti K j=1 π 3 tj K k=1 π 2 tk 2 ≤ π ti K j=1 π 3 tj K k=1 π 3 tk 4 3 = π ti K k=1 π 3 tk 1 3 ≤ 1 .Proof of Lemma 4. EQUATIONf (x) = min x∈[0,1] x 3 1 -x + √ 1 -x ≥ 8 9 .Proof. We first show that the optimal point is smaller than 1 9 , by looking at the derivativef (x) = 3 √ x -x 3 2 -(1 -x) 3 2 2(1 -x) 2 .For the enumerator, we have for all x ≥ 1 9 :3 √ x -x 3 2 -(1 -x) 3 2 > 3 √ x -max{ √ x, √ 1 -x} ≥ min{2 √ x, 3 √ x -1} ≥ 0 Hence min x∈[0,1] f (x) = min x∈[0,1/9] f (x) > min x∈[0,1/9] √ 1 -x = 8 9 . Lemma 9. For any a, b ≥ 0 such that a + b ≥ 1, it holds a √ b + b √ a ≥ √ 2 .Proof. We can assume w.l.o.g. that a = 1 -b, otherwise scale both a and b down and reduce the objective. The resulting problem is symmetric with a = 1 2 as the unique minimizer resulting in the statement.Lemma 10. Assume that π ti > (ξ t + γ) 2 η 2 t holds for all arms, thenE t ( ˆ ti -λ t ) 2 ≤ 13(1 -π ti ) 8π t,i .Proof. Let ˜ t,i = π t,i ˆ t,i and λ t,i = π t,i λ t . Note that ˜ ti ∈ [-1, 1] by the condition on π ti and ˜ ti = 0 for i = I t by construction of the loss estimate. HenceE t ( ˜ ti -λ ti ) 2 ≤ π ti   1 - π 3 2 ti K j=1 π 3 2 tj   2 E[ ˜ 2 ti |i = I t ] + j =i π tj   π ti √ π tj K j=1 π 3 2 tj   2 E[ ˜ 2 tj |j = I t ] ≤ π ti   ( j =i π 3 2 tj ) 2 + π ti j =i π 2 tj ( K j=1 π 3 2 tj ) 2   = π ti (1 -π ti )   (1 -π ti ) 2 ( j =i π 3 2 tj ) 2 + π ti (1 -π ti ) j =i π2 tj (π 3 2 ti + (1 -π ti ) 3 2 j =i π 3 2 tj ) 2   ,where πtj = πtj 1-πti . We bound the two terms in the bracket separately, for the first term we have  (1 -π ti ) j =i π 3 2 tj π 3 2 ti + (1 -π ti ) 3 2 j =i π 3 2 tj   2 ≤ (1 -π ti ) π 3 2 ti + (1 -π ti ) 3 2 2 ( j =i πtj = 1) ≤ 9 8 (Lemma 8)The second term isEQUATIONt ) for all t, then the update rule of TS-Prod is well defined and satisfies π t,i > (ξ t + γ) 2 η 2 t for any arm and loss sequence at all time steps.Proof. The proof follows by induction. At t = 1 the statement is true by definition. Let the claim hold at time t, then the probability of an arm only decreases when ˆ t,i -λ t is positive. We look at the cases where A t = i and A t = i independently.Case A t = i: π t+1,i > π t,i (1 -2η t √ π t,i ˆ t,i ) = π t,i -2η t √ π t,i t,i -η t (ξ t + γ(1 -π t,i )) > π t,i (1 -2γη 2 t ) -2η t √ π t,i + 2γη 2 t = (1 -2γη 2 t ) √ π t,i - η t 1 -2γη 2 t 2 + (2γ - 1 1 -2γη 2 t )η 2 tThis is a quadratic function in π t,i with minimizerη 2 t (1-2γη 2 t ) 2 < (ξ t + γ) 2 η 2 t , hence the value is lower bounded by setting π t,i to (ξ t + γ) 2 η 2 t π t+1,i > (ξ t + γ) 2 η 2 t (1 -2γη 2 t ) ≥ (ξ t + γ) 2 η 2 t+1 ≥ (ξ t+1 + γ) 2 η 2 t+1 Case A t = i: π t+1,i = π t,i -2η t π 3 2 t,i   η t ((ξ t + γ(1 -π t,At )) -t,At √ π t,At K j=1 π 3 2 tj   > π t,i -2(ξ t + γ)η 2 t π 3 2 t,i √ KThis is a concave function (in π t,i ) so the minimizer is at either at π t,i = (ξ t + γ) 2 η 2 t or at π t,i = 1. For the latter, we have have π t+1,i > 1 2 , so the minimum is obtained for the first case.π t+1,i > (ξ t + γ) 2 η 2 t -2(ξ t + γ) 4 η 5 t √ K > (ξ t + γ) 2 η 2 t (1 -2γη 2 t ) ≥ C 2 t+1 η 2 t+1 .Lemma 12 (Lemma 6). For any time t such that π t,i > (ξ t + γ) 2 η 2 t , it holdsπ t -u, E t [ t ] + E t D T S (u, π t+1 ) η t - D T S (u, π t ) η t ≤ K i=1 2η t √ π t,i (1 -π t,i ) - 1 η t - 1 η t-1 u i -π t,i √ π t,i .Proof of Lemma 6.EQUATIONWe now show that the requirements of Lemma 5 are satisfied with the tuning of Theorem 3. Withη t = 1 √ K+26t , we have c t = K + 26t -(K + 26t)(K + 26t -26) > 2 , which is monotonically decreasing. c t > 2 and γ = 13 2 ensures that η t = 1 √ K+26t < 2 √ K(ct+γ) 2 . Further we have η 2 t+1 η 2 t = K + 26t K + 26(t + 1) = 1 - 26 K + 26(t + 1) ≤ 1 - 4 K + 26t = 1 -4η 2 t . Proof of Lemma 7. Using η 0 = ∞ and D T S (u, Π T +1 ) ≥ 0 T t=1 D T S (u, π t ) -D T S (u, π t+1 ) η t ≤ T t=1 1 η t - 1 η t-1 D T S (u, π t ) = T t=1 1 η t - 1 η t-1 (F (u) -F (π t ) -u -π t , ∇F (π t ) ) = T t=1 K i=1 η t ξ t 2( √ π t,i - √ u t,i ) -(u i -π ti ) 1 √ π ti ≤ T t=1 η t ξ t   i =i 2 √ π t,i - K i=1 (u i -π ti ) 1 √ π ti   ,where the last inequality follows fromK i=1 √ u i ≥ 1 ≥ √ π t,i .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 formT t=1 i =i * π t,i ∆ i ≤ T t=1 i =i * aπ t,i + b √ π t,i √ t ,for some positive a and b. The above inequality implies1 3 T t=1 i =i * π t,i ∆ i ≤ T t=1 i =i * π t,i a √ t - ∆ i 3 + √ π t,i b √ t - ∆ i √ π t,i 3 .For a fixed i the terma √ t -∆i 3 ≤ 0 if t ≥ 9a 2 ∆ 2 iand so the maximum regret fromT t=1 π t,i a √ t - ∆ i 3 ≤ 9a 2 ∆ 2 i t=1 a √ t ≤ 6a 2 ∆ i . Further the term √ π t,i b √ t - ∆i √ πt,i 3 ≤ 2b 2 t∆i for t ≥ 4b 2 ∆ 2 i . This implies T t=1 √ π t,i b √ t - ∆ i √ π t,i 3 ≤ 4b 2 ∆ 2 i t=1 b √ t + T t=1 2b 2 ∆ i t ≤ 8b 2 ∆ i + 2b 2 log(T ) ∆ i .Combining the two bounds we haveT t=1 i =i * π t,i ∆ i ≤ O   i =i * b 2 log(T ) ∆ i + a 2 ∆ i   .The TS-Prod update is a 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 a decreasing step-size in 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] 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 in the adversarial setting to that of Fang et al. [2022] .Stabilization as introduced by Fang et al. [2022] is the process of mixing the gradient mapping, ∇F (π t ), of the current iterate with the gradient mapping of the first iterate, ∇F (π 1 ), in the mirror descent update in the dual space, where F (x) = -K i=1 2 √ x i . This mixing turns out to be equivalent to the negative biasing of losses in Equation TS-Prod by the ξ t dependent terms.The regret analysis begins by defining the perturbations { t,i } t∈[T ],i∈[K] so thatEQUATION)that is t,i makes the update in Equation TS-Prod equivalent to the 1/2-Tsallis mirror descent update. We note that the t,i is only defined to assist with the regret analysis and it never needs to be computed for the actual update. The perturbations, t,i , are well controlled as we show next.Lemma 13. For every t ∈ [T ], i ∈ [K], there exists t,i such that t,i ≤ 4η t √ π t,i L2 t,i for all i and t,i .Lemma 13 allows us to proceed with the analysis for the stochastic and adversarial cases by using the standard regret decomposition into a penalty and stability terms. In the stochastic case we can bound the two terms in the following way Lemma 14. For stochastic losses the penalty term is bounded in expectation byO E i =i * π t+1,i 2 √ K log(t) √ t + 1 √ t ∧ E i =i * π t+1,i 2 log(KT ) √ t .Lemma 15. For stochastic losses the stability term is bounded byO 1 √ t K i=1 √ π t,i (1 -π t,i ) + K √ π t,i t 2 + K t .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 + I ∆ K-1 be potential defined by mixing the 1/2-Tsallis potential together with the indicator function for the probability simplex. The update of Algorithm 2 (Dual Stabilized OMD) can then be written asŵt+1 = ∇Φ(π t ) -η t ( ˜ t + t ), ŷt+1 = χ t ŵt+1 + (1 -χ t )∇Φ(π 1 ), π t+1 = ∇Φ * (ŷ t+1 ).It turns out that this update is equivalent to the OMD update with respect to Lt,i in Equation 4. This allows us to use the regret bound in Theorem 3 [Fang et 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 in Equation 4 is bounded byO   i =i * log(T ) ∆ i + K log 2 (1/∆ min ) ∆ min + K 3/2  in the stochastic case, where ∆ min is the smallest gap between the expected losses. Further the regret in the adversarial setting is bounded by O( √ KT ).Proof of Lemma 13. We work under the following assumption which is satisfied with the choice of η t and γ by Lemma 5. Further, we are going to work with the following slight modification of the losses ˆ t in the update of TS-Prod:ˆ t,i = t,i - η t (γ(1 -π t,i ) √ π t,i I(A t = i) π t,i - η t ξ t √ π t,i .We quickly check that the variance with this definition of ˆ t is bounded by Lemma 10E t t,i - γ(1 -π t,i ) √ π t,i I(A t = i) π t,i - η t ξ t √ π t,i 2 = E t t,i - γ(1 -π t,i ) √ π t,i 2 1 π t,i + (η t ξ t ) 2 π t,i -2 t,i - γ(1 -π t,i ) √ π t,i η t ξ t √ π t,i ≤ E t t,i - γ(1 -π t,i ) √ π t,i 2 1 π t,i + (η t ξ t ) 2 π 2 t,i -2 t,i - γ(1 -π t,i ) √ π t,i η t ξ t √ π t,i = E t t,i - η t (ξ t + γ(1 -π t,i ) √ π t,i I(A t = i) π t,i 2 Assumption 1. Assume that for all t ∈ [T ], i ∈ [K] it holds that |η t π t,i Lt,i | ≤ 1 6 .Lemma 13. First for non-negative we show that ∈ [0, ]. This follows by observing that 1/(1 + 3/2x)2 ≤ 1 -2x for x ∈ [0, 1/6] and 1/(1 + x) 2 ≥ 1 -2x for x ≥ 0 so by the Intermediate Value theorem there exists an ∈ [0, ] such that equality is obtained. Next, for < 0 for = 0 we have1/(1 -x) 2 ≥ 1 + 2x for x ≥ 0 and for = /2 we have 1/(1 -x/2) 2 ≤ 1 -2x for x ∈ [0, 1/4] and so we have = [-| | 2 , | | 2 ].For the second part of the lemma using the Taylor expansion around 0 of 1/(1 + x) 2 implies that 1(1 + η √ π ˜ ) 2 ≤ 1 -2η √ π ˜ + 3(η √ π ˜ ) 2 ,and so1 -2η √ π( ˜ -) ≤ 1 -2η √ π ˜ + 3(η √ π ˜ ) 2 ⇐⇒ 2η √ π ≤ 3(η √ π ˜ ) 2 ⇐⇒ 2η √ π ≤ 3(η √ π( + )) 2 =⇒ ≤ 4η √ π 2 . Stochastic bound. Let D T S t (u, w) = 1 ηt D T S (u, v) and let πt+1,i = π t,i (1 + η t+1 √ π t,i ( ˆ t,i + t,i -λ t )) 2 ,where λ t = t,At . We note that π t+1 is now the projection of πt+1 onto the simplex. Further by the 3-point rule for Bregman divergence we have thatLt , π t -u = D T S t (u, π t ) -D T S t (u, πt+1 ) + D T S t (π t , πt+1 ) ≤ D T S t (u, π t ) -D T S t (u, π t+1 ) + D T S t (π t , πt+1 ).Penalty term. Lemma 16 (Lemma 14). For stochastic losses the penalty term is bounded as followsE[D T S t+1 (u, π t+1 ) -D T S t (u, π t+1 )] ≤ O E i =i * π t+1,i where D T S t (u, v) = 1 ηt D T S (u, v) and η t = 1 √ t .Proof. for u = e i * :D T S t+1 (u, π t+1 ) -D T S t (u, π t+1 ) = - 1 η t+1 - 1 η t + 1 η t+1 - 1 η t 1 √ π t+1,i * -1 + 1 η t+1 - 1 η t K i=1 √ π t+1,i = 1 η t+1 - 1 η t 1 - √ π t+1,i * + π t+1,i * √ π t+1,i * + 1 η t+1 - 1 η t i =i * √ π t+1,i = 1 η t+1 - 1 η t (1 - √ π t+1,i * ) 2 √ π t+1,i * + 1 η t+1 - 1 η t i =i * √ π t+1,i .From the update in Equation 4we have1 √ π t+1,i * = √ K + t s=1 η s ( Ls,i * + s,i * ), which implies (1 - √ π t+1,i * ) 2 √ π t+1,i * ≤ √ K(1 - √ π t+1,i * ) 2 + (1 - √ π t+1,i * ) 2 t s=1 η s ( Ls,i * + s,i * ) First we bound (1 - √ π t+1,i * ) 2 : (1 - √ π t+1,i * ) 2 =   1 -1 - i =i * π t+1,i   2 =   i =i * π t+1,i 1 + 1 -i =i * π t+1,i   2 ≤   i =i * π t+1,i   2 .In the stochastic case WLOG we can take E[ t,i * ] = 0, ∀t ∈ [T ]. We first control Lt,i * . We haveLt,i * = t,i * - η t γ(1 -π t,i * ) √ π t,i * I(A t = i * ) π t,i * - η t ξ t √ π t,i * - K i=1 π 3 2 t,i ˆ t,i K j=1 π 3 2 t,jThe first term, t,i * I(At=i * )π t,i * is 0 in expectation. The second term, - ηtγ(1-π t,i * ) √ π t,i * I(At=i * )π t,i * , will be used to cancel out the contribution from the perturbation t,i * . The third term is there to help with the adversarial setting analysis. Next, we decompose the fourth term asK i=1 π 3 2 t,i ˆ t,i K j=1 π 3 2 t,j = 1 K j=1 π 3/2 t,j K i=1 √ π t,i t,i I(A t = i) -η t γ(1 -π t,i )I(A t = i) -π t,i η t ξ t .The first part of the above has a non-positive contribution to Lt,i * in expectation. The only nonnegative contribution now comes from1 K j=1 π 3/2 t,j K i=1 η t (ξ t + γ(1 -π t,i ))I(A t = i) ≤ √ K(η t ξ t + η t γ) ≤ 2 √ Kη t γand so we boundt s=1 -η s K i=1 π 3 2 s,i ˆ s,i K j=1 π 3 2 s,j ≤ t s=1 2η s √ Kη s γ ≤ 64 √ K log(t).Next we are going to bound E[ t,i * ] using Lemma 10 together with Lemma 13:E[ t,i * ] ≤ E[η t √ π t,i * L2 t,i * ] ≤ 13 2 E[η t (1 -π t,i * )/ √ π t,i * ].This term is exactly canceled out byηtγ(1-π t,i * ) √ π t,i * as γ = 13 2 .For the final bound we haveE 1 η t+1 - 1 η t (1 - √ π t+1,i * ) 2 √ π t+1,i * ≤ 1 η t+1 - 1 η t E      i =i * π t+1,i   2    + 4 1 η t+1 - 1 η t E      i =i * π t+1,i   2 t s=1 η s ( Ls,i * + s,i * )    ≤ 1 η t+1 - 1 η t E      i =i * π t+1,i   2    + E   1 η t+1 - 1 η t (1 - √ π t+1,i * ) 2 t s=1 -η s K i=1 π 3 2 s,i ˆ s,i K j=1 π 3 2 s,j   + E t s=1 η s s,i * - γη s (1 -π s,i * ) √ π s,i * ≤ 32 E i =i * π t+1,i 2 √ K log(t) √ t .Stability term. Recall that the stability term is D T S t (π t , πt+1 ). This term is bounded in a standard way. We proceed to do so as follows for any t ≥ 4 √ K:Lemma 17 (Lemma 15). For stochastic losses the stability term is bounded as followsE[D T S t (π t , πt+1 )] ≤ O 1 √ t K i=1 √ π t,i (1 -π t,i ) + 1 t , where D T S t (u, v) = 1 ηt D T S (u, v).Proof. We have the following Self-bounding the regret for stochastic losses.D T S t (π t , πt+1 ) = 1 η t K i=1 2 √ π t+1,i -2 √ π t,i - 1 √ π t+1,i (π t+1,i -π t,i ) = 1 η t K i=1 √ πTheorem 4, stochastic losses. Combining the bound in Lemma 14 and Lemma 15 together with the adversarial bound we have that the total regret is bounded as follows+O   T t=T0 i =i * √ π t,i 1 √ t - √ π t,i ∆ i - √ K log(t) √ t + T0-1 t=1 π t,i √ K log(t) √ t   +O K 3/2In the above we bound the lower order term from the stability asT t=1 K i=1 γ 2 t √ π t,i = O(K 3/2 )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 is the additional regret for the initial number of rounds before the self-bounding trick can be applied.We repeatedly use the following inequality 2a √ x -bx ≤ a 2 b , which holds for a, b ≥ 0. For the first line of the decomposition we take T 0 = 8 K log 2 (K/∆min) ∆min , where ∆ min is the smallest non-zero expected loss. We note that √ K log(T 0 ) √ T 0 = ∆ min log(8K log and χ t = ηt ηt-1 We recall the update for Algorithm 2 in Fang et al. [2022] ŵt+1 = ∇Φ(π t ) -η t-1 ( ˜ t + t ), ŷt+1 = χ t ŵt+1 + (1 -χ t )∇Φ(π 1 ), π t+1 = ∇Φ * (ŷ t+1 ), where Φ is the 1/2-Tsallis potential plus the indicator function for the probability simplex ∆ K-1 . Since π 1 is uniform the second step of the update is equivalent to ŷt+1 = χ t ŵt+1 . Re-writing the first step of the update we have-ŷ t+1,i = χ t √ π t,i + η t ( ˜ t,i + t,i ) = 1 √ π t,i + η t+1 ( ˜ t,i + t,i ) -η t 1 η t - 1 η t-1 1 √ π t,i = 1 √ π t,i + η t t,i - η t γ(1 -π t,i ) √ π t,i I(A t = i) π t,i + t,i - 1 η t - 1 η t-1 1 √ π t,i = 1 √ π t,i+ η t ( ˆ t,i + λ t ).Since ∇Φ * is invariant under constant vector perturbations we finally haveπ t+1,i = ∇Φ * (ŷ t+1 ) i = ∇Φ * - 1 √ π t -η t ( ˆ t+1 + t ) = ∇Φ * - 1 √ π t -η t ( Lt+1 + t ) = 1(1/ √ π t,i + η t ( Lt,i + t,i )) 2 = π t,i(1 + η t √ π t,i ( Lt,i + t,i )) 2 .And so the update in Algorithm 2 of Fang et al. [2022] is equivalent to the perturbed OMD update which we have shown enjoys an optimistic regret guarantee. The regret guarantee in the adversarial setting is now recovered from Theorem 3 in Fang et al. [2022] . In particular the theorem guarantees that the regret is bounded as ). We can now use the bound in the proof of Lemma 15 to complete proof of the adversarial bound and the proof of Theorem 4.For the rest of the paper we refer to pseudo-regret as regret for simplicity.This might look very dissimilar from the original Hedge/EXP/MWU analysis, but it is actually equivalent after accounting for the special form of the KL divergence.√ K log(t) √ t , 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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

- 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

- Authors do not provide any discussion on real world applications of their algorithms

- The focus of the paper is heavily theoretical, which might reduce its accessibility and usability for practitioners looking for direct application insights.
questions: questions: Can you provide experimental results to illustrate the theoretical claims?

How does your algorithms compare with other algorithms in similar settings?
limitations: 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.

The 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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.
- 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?

Minor comments/typos:
- Line 7: “best-of-both-worlds” instead of “best-both-worlds”
- Table 1: the first column is simply the negative entropy, and calling it “KL divergence” too might be confusing
- 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
- 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$).
- Line 180: “be” instead of “be be”
- Line 211: “poses” instead of “posses”
- Line 214: “a fixed” instead of “a a fixed”
- Line 227: in “intermediate potential between KL and Logbarrier”, negative entropy is the potential function (whose Bregman divergence is the KL)
- Math display below line 360: $\\pi\_{t,i}^2$ between parentheses after the first equality should be $\\pi\_{t,i}$
limitations: limitations: The authors addressed potential limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 
2. **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. 
3. **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.
questions: questions: 1. What is the benefit of using Prod/what is the rationale for studying this problem?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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".
To 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.
questions: 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: limitations: I believe that this category does not apply to a paper which is entirely theoretical.
paper_summary: paper_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.
strength_weakness: strength_weakness: I do not find main weakness of this paper but I have some concerns on the results and some configurations of the algorithms.

- 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.

- 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.

- The BOBW regret for the stochastic environment is a bit away from the optimal due to the additional $K/\Delta_{\min}$ lower order term.
questions: questions: - Can the authors explain more on what difficulties are if one uses OMD with Logbarrier and perturbation analysis to analyze LB-Prod?

- Whether there is also an inverse-propensity-weighting-free version of Tsallis-Prod that achieves BOBW for adversarial MAB?

- 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?

- Can the stochastic regret bound for Tsallis-Prod be improved to optimal?
limitations: limitations: See "weakness" and "questions".

Comments: title: Thank you for the comments
comment: I thank the authors for answering my questions. I keep my original positive score.
I thank the authors for their response and I keep my positive score.
Thank you for the response. I will keep my score.
Thank you for your comments and information. A discussion of limitations would be helpful for practitioners aiming to leverage the algorithms from this paper. While I am still not convinced about the motivation for Prod updates, the rebuttal clarifies the connection between this and prior works, so I raise my score.