uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs

## Abstract

Abstract In this paper, we present a novel algorithm, uniINF , for the Heavy-Tailed Multi-Armed Bandits (HTMAB) problem, demonstrating robustness and adaptability in both stochastic and adversarial environments. Unlike the stochastic MAB setting where loss distributions are stationary with time, our study extends to the adversarial setup, where losses are generated from heavy-tailed distributions that depend on both arms and time. Our novel algorithm uniINF enjoys the so-called Best-of-Both-Worlds (BoBW) property, performing optimally in both stochastic and adversarial environments without knowing the exact environment type. Moreover, our algorithm also possesses a Parameter-Free feature, i.e. , it operates without the need of knowing the heavy-tail parameters ( σ , α ) 𝜎 𝛼 (\sigma,\alpha) ( italic_σ , italic_α ) a-priori.
To be precise, uniINF ensures nearly-optimal regret in both stochastic and adversarial environments, matching the corresponding lower bounds when ( σ , α ) 𝜎 𝛼 (\sigma,\alpha) ( italic_σ , italic_α ) is known (up to logarithmic factors). To our knowledge, uniINF is the first parameter-free algorithm to achieve the BoBW property for the heavy-tailed MAB problem. Technically, we develop innovative techniques to achieve BoBW guarantees for Parameter-Free HTMABs, including a refined analysis for the dynamics of log-barrier, an auto-balancing learning rate scheduling scheme, an adaptive skipping-clipping loss tuning technique, and a stopping-time analysis for logarithmic regret.

## 1 Introduction

Multi-Armed Bandits (MAB) problem serves as a solid theoretical formulation for addressing the exploration-exploitation trade-off inherent in online learning. Existing research in this area often assumes sub-Gaussian loss (or reward) distributions (Lattimore and Szepesvári,, ) or even bounded ones (Auer et al.,, ). However, recent empirical evidences revealed that Heavy-Tailed (HT) distributions appear frequently in realistic tasks such as network routing (Liebeherr et al.,, ), algorithm portfolio selection (Gagliolo and Schmidhuber,, ), and online deep learning (Zhang et al.,, ). Such observations underscore the importance of developing MAB solutions that are robust to heavy-tailed distributions.

In this paper, we consider the Heavy-Tailed Multi-Armed Bandits (HTMAB) proposed by Bubeck et al., (). In this scenario, the loss distributions associated with each arm do not allow bounded variances but instead have their $\alpha$-th moment bounded by some constant $\sigma^{\alpha}$, where $\alpha\in(1,2]$ and $\sigma\geq 0$ are predetermined constants. Mathematically, we assume $\mathbb{E}[\lvert\ell_{i}\rvert^{\alpha}]\leq\sigma^{\alpha}$ for every arm $i$. Although numerous existing HTMAB algorithms operated under the assumption that the parameters $\sigma$ and $\alpha$ are known (Bubeck et al.,, ; Yu et al.,, ; Wei and Srivastava,, ), real-world applications often present limited knowledge of the true environmental parameters. Thus we propose to explore the scenario where the algorithm lacks any prior information about the parameters. This setup, a variant of classical HTMABs, is referred to as the Parameter-Free HTMAB problem.

In addition to whether $\sigma$ and $\alpha$ are known, there is yet another separation that distinguishes our setup from the classical one.
In bandit learning literature, there are typically two types of environments, stochastic ones and adversarial ones.
In the former type, the loss distributions are always stationary, i.e., they depend solely on the arm and not on time. Conversely, in adversarial environments, the losses can change arbitrarily, as-if manipulated by an adversary aiming to fail our algorithm.

When the environments can be potentially adversarial,
a desirable property for bandit algorithms is called Best-of-Both-Worlds (BoBW), as proposed by Bubeck and Slivkins, (). A BoBW algorithm behaves well in both stochastic and adversarial environments without knowing whether stochasticity is satisfied. More specifically, while ensuring near-optimal regret in adversarial environments, the algorithmic performance in a stochastic environment should automatically be boosted, ideally matching the optimal performance of those algorithms specially crafted for stochastic environments.

In practical applications of machine learning and decision-making, acquiring prior knowledge about the environment is often a considerable challenge (Talaei Khoei and Kaabouch,, ). This is not only regarding the distribution properties of rewards or losses, which may not conform to idealized assumptions such as sub-Gaussian or bounded behaviors, but also about the stochastic or adversarial settings the agent palying in. Such environments necessitate robust solutions that can adapt without prior distributional knowledge. Therefore, the development of a BoBW algorithm that operates effectively without this prior information – termed a parameter-free HTMAB algorithm – is not just a theoretical interest but a practical necessity.

Various previous work has made strides in enhancing the robustness and applicability of HTMAB algorithms. For instance, Huang et al., () pioneered the development of the first BoBW algorithm for the HTMAB problem, albeit requiring prior knowledge of the heavy-tail parameters $(\alpha,\sigma)$ to achieve near-optimal regret guarantees. Genalti et al., () proposed an Upper Confidence Bound (UCB) based parameter-free HTMAB algorithm, specifically designed for stochastic environments. Both algorithms’ regret adheres to the instance-dependent and instance-independent lower bounds established by Bubeck et al., ().
Though excited progress has been made, the following important question still stays open, which further eliminates the need of prior knowledge about the environment:

Can we design a BoBW algorithm for the Parameter-Free HTMAB problem?

Addressing parameter-free HTMABs in both adversarial and stochastic environments presents notable difficulties:
i) although UCB-type algorithms well estimate the underlying loss distribution and provide both optimal instance-dependent and independent regret guarantees, they are incapable of adversarial environments where loss distributions are time-dependent;
ii) heavy-tailed losses can be potentially very negative, which makes many famous algorithmic frameworks, including Follow-the-Regularized-Leader (FTRL), Online Mirror Descent (OMD), or Follow-the-Perturbed-Leader (FTPL) fall short unless meticulously designed; and
iii) while it was shown that FTRL with $\beta$-Tsallis entropy regularizer can enjoy best-of-both-worlds guarantees, attaining optimal regret requires an exact match between $\beta$ and $\nicefrac{{1}}{{\alpha}}$ — which is impossible without knowing $\alpha$ in advance.

Our contribution.
In this paper, we answer this open question affirmatively by designing a single algorithm uniINF that enjoys both Parameter-Free and BoBW properties — that is, it i) does not require any prior knowledge of the environment, e.g., $\alpha$ or $\sigma$, and ii) its performance when deployed in an adversarial environment nearly matches the universal instance-independent lower bound given by Bubeck et al., (), and it attains the instance-dependent lower bound in stochastic environments as well.
For more details, we summarize the advantages of our algorithm in Table 1. Our research directly contributes to enhancing the robustness and applicability of bandit algorithms in a variety of unpredictable and non-ideal conditions.
Our main contributions are three-fold:

- •
We develop a novel BoBW algorithm uniINF (see Algorithm 1) for the Parameter-Free HTMAB problem. Without any prior knowledge about the heavy-tail shape-and-scale parameters $(\alpha,\sigma)$, uniINF can achieve nearly optimal regret upper bound automatically under both adversarial and stochastic environments (see Table 1 or Theorem 3 for more details).
- •
We contribute several innovative algorithmic components in designing the algorithm uniINF, including a refined analysis for Follow-the-Regularized-Leader (FTRL) with log-barrier regularizers (refined log-barrier analysis in short; see Section 4.1), an auto-balancing learning rate scheduling scheme (see Section 4.2), and an adaptive skipping-clipping loss tuning technique (see Section 4.3).
- •
To derive the desired BoBW property, we develop novel analytical techniques as well. These include a refined approach to control the Bregman divergence term via calculating partial derivatives and invoking the intermediate value theorem (see Section 5.2) and a stopping-time analysis for achieving $\operatorname{\mathcal{O}}(\log T)$ regret in stochastic environments (see Section 5.4).

**Table 1: Overview of Related Works For Heavy-Tailed MABs**
| Algorithm (^1^11$\bm{\alpha}$-Free? and $\bm{\sigma}$-Free? denotes whether the algorithm is parameter-free w.r.t. $\alpha$ and $\sigma$, respectively. Env. includes the environments that the algorithm can work; if one algorithm can work in both stochastic and adversarial environments, then we mark this column by green. Regret describes the algorithmic guarantees, usually (if applicable) instance-dependent ones above instance-independent ones. Opt? means whether the algorithm matches the instance-dependent lower bound by Bubeck et al., () up to constant factors, or the instance-independent lower bound up to logarithmic factors.) | $\bm{\alpha}$-Free? | $\bm{\sigma}$-Free? | Env. | Regret | Opt? |
| --- | --- | --- | --- | --- | --- |
| Lower Bound<br>[3pt](Bubeck et al.,, ) | — | — | — | $\Omega\left(\sum_{i\neq i^{\ast}}(\frac{\sigma^{\alpha}}{\Delta_{i}})^{\frac{1<br>}{\alpha-1}}\log T\right)$ | — |
| \cdashline5-5 | $\Omega\left(\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{\alpha}}}\right)$ |  |  |  |  |
| RobustUCB<br>[3pt](Bubeck et al.,, ) | ✗ | ✗ | Only Stoc. | $\operatorname{\mathcal{O}}\left(\sum_{i\neq i^{\ast}}(\frac{\sigma^{\alpha}}{<br>\Delta_{i}})^{\frac{1}{\alpha-1}}\log T\right)$ | ✓ |
| \cdashline5-6 | $\operatorname{\widetilde{\mathcal{O}}}\left(\sigma K^{1-\nicefrac{{1}}{{\alpha<br>}}}T^{\nicefrac{{1}}{{\alpha}}}\right)$ | ✓ |  |  |  |
| Robust MOSS<br>[3pt](Wei and Srivastava,, ) | ✗ | ✗ | Only Stoc. | $\operatorname{\mathcal{O}}\left(\sum_{i\neq i^{\ast}}(\frac{\sigma^{\alpha}}{<br>\Delta_{i}})^{\frac{1}{\alpha-1}}\log(\frac{T}{K}(\frac{\sigma^{\alpha}}{<br>\Delta_{i}^{\alpha}})^{\frac{1}{\alpha-1}})\right)$ | (^2^2footnotemark: 2) ✓ (^3^33Up to $\log(\sigma^{\alpha})$ and $\log(1/\Delta_{i}^{\alpha})$ factors.) |
| \cdashline5-6 | $\operatorname{\mathcal{O}}\left(\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{<br>\nicefrac{{1}}{{\alpha}}}\right)$ | ✓ |  |  |  |
| APE^2<br>[3pt] (Lee et al.,, ) | ✗ | ✓ | Only Stoc. | ${\mathcal{O}}\left(e^{\sigma}+\sum_{i\neq i^{\ast}}(\frac{1}{\Delta_{i}})^{<br>\frac{1}{\alpha-1}}(T\Delta_{i}^{\frac{\alpha}{\alpha-1}}\log K)^{\frac{\alpha<br>}{(\alpha-1)\log K}}\right)$ | ✗ |
| \cdashline5-6 | $\operatorname{\widetilde{\mathcal{O}}}\left(\exp(\sigma^{\nicefrac{{1}}{{<br>\alpha}}})K^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{\alpha}}}\right)$ | ✗ |  |  |  |
| HTINF<br>[3pt](Huang et al.,, ) | ✗ | ✗ | Stoc. | $\operatorname{\mathcal{O}}\left(\sum_{i\neq i^{\ast}}(\frac{\sigma^{\alpha}}{<br>\Delta_{i}})^{\frac{1}{\alpha-1}}\log T\right)$ | ✓ |
| \cdashline4-6 | Adv. | $\operatorname{\mathcal{O}}\left(\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{<br>\nicefrac{{1}}{{\alpha}}}\right)$ | ✓ |  |  |
| OptHTINF<br>[3pt](Huang et al.,, ) | ✓ | ✓ | Stoc. | $\operatorname{\mathcal{O}}\left(\sum_{i\neq i^{\ast}}(\frac{\sigma^{2\alpha}}{<br>\Delta_{i}^{3-\alpha}})^{\frac{1}{\alpha-1}}\log T\right)$ | ✗ |
| \cdashline4-6 | Adv. | $\operatorname{\mathcal{O}}\left(\sigma^{\alpha}K^{\frac{\alpha-1}{2}}T^{\frac{<br>3-\alpha}{2}}\right)$ | ✗ |  |  |
| AdaTINF<br>[3pt] (Huang et al.,, ) | ✓ | ✓ | Only Adv. | $\operatorname{\mathcal{O}}\left(\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{<br>\nicefrac{{1}}{{\alpha}}}\right)$ | ✓ |
| AdaR-UCB<br>[3pt](Genalti et al.,, ) | ✓ | ✓ | Only Stoc. | $\operatorname{\mathcal{O}}\left(\sum_{i\neq i^{\ast}}(\frac{\sigma^{\alpha}}{<br>\Delta_{i}})^{\frac{1}{\alpha-1}}\log T\right)$ | ✓ |
| \cdashline5-6 | $\operatorname{\widetilde{\mathcal{O}}}\left(\sigma K^{1-\nicefrac{{1}}{{\alpha<br>}}}T^{\nicefrac{{1}}{{\alpha}}}\right)$ | ✓ |  |  |  |
| uniINF<br>[3pt](Ours) | ✓ | ✓ | Stoc. | $\operatorname{\mathcal{O}}\left(K(\frac{\sigma^{\alpha}}{\Delta_{\min}})^{<br>\frac{1}{\alpha-1}}\log T\cdot\log\frac{\sigma^{\alpha}}{\Delta_{\min}}\right)$ | (^4^4footnotemark: 4) ✓ (^5^55Up to $\log(\sigma^{\alpha})$ and $\log(1/\Delta_{\min})$ factors when all $\Delta_{i}$’s are similar to the dominant sub-optimal gap $\Delta_{\min}$.) |
| \cdashline4-6 | Adv. | $\operatorname{\widetilde{\mathcal{O}}}\left(\sigma K^{1-\nicefrac{{1}}{{\alpha<br>}}}T^{\nicefrac{{1}}{{\alpha}}}\right)$ | ✓ |  |  |

## 2 Related Work

#### Heavy-Tailed Multi-Armed Bandits.

HTMABs were introduced by Bubeck et al., (), who gave both instance-dependent and instance-independent lower and upper bounds under stochastic assumptions. Various efforts have been devoted in this area since then. To exemplify,
Wei and Srivastava, () removed a sub-optimal $(\log T)^{1-1/\alpha}$ factor in the instance-independent upper bound;
Yu et al., () developed a pure exploration algorithm for HTMABs;
Medina and Yang, (), Kang and Kim, (), and Xue et al., () considered the linear HTMAB problem; and Dorn et al., () specifically investigated the case where the heavy-tailed reward distributions are presumed to be symmetric. Nevertheless, all these works focused on stochastic environments and required the prior knowledge of heavy-tail parameters $(\alpha,\sigma)$. In contrast, this paper focuses on both-of-both-worlds algorithms in parameter-free HTMABs, which means i) the loss distributions can possibly be non-stationary, and ii) the true heavy-tail parameters $(\alpha,\sigma)$ remain unknown.

#### Best-of-Both-Worlds Algorithms.

Bubeck and Slivkins, () pioneered the study of Best-of-Both-Worlds bandit algorithms, and was followed by various improvements including EXP3-based approaches (Seldin and Slivkins,, ; Seldin and Lugosi,, ), FTPL-based approaches (Honda et al.,, ; Lee et al.,, ), and FTRL-based approaches (Wei and Luo,, ; Zimmert and Seldin,, ; Jin et al.,, ). When the loss distribution can be heavy-tailed, Huang et al., () gave an algorithm HTINF that achieves best-of-both-worlds property under the known-$(\alpha,\sigma)$ assumption. Unfortunately, without access to these true parameters, their alternative algorithm OptHTINF failed to achieve near-optimal regret guarantees in either adversarial or stochastic environments.

#### Parameter-Free HTMABs.

Another line of research aimed at getting rid of the prior knowledge of $\alpha$ or $\sigma$, which we call Parameter-Free HTMABs. Along this line, Kagrecha et al., () presented the GSR method to identify the optimal arm in HTMAB without any prior knowledge. In terms of regret minimization, Lee et al., () and Lee and Lim, () considered the case when $\sigma$ is unknown. Genalti et al., () were the first to achieve the parameter-free property while maintaining near-optimal regret. However, all these algorithms fail in adversarial environments – not to mention the best-of-both-worlds property which requires optimality in both stochastic and adversarial environments.

## 3 Preliminaries: Heavy-Tailed Multi-Armed Bandits

#### Notations.

For an integer $n\geq 1$, $[n]$ denotes the set $\{1,2,\ldots,n\}$.
For a finite set $\mathcal{X}$, $\Delta(\mathcal{X})$ denotes the set of probability distributions over $\mathcal{X}$, often also referred to as the simplex over $\mathcal{X}$. We also use $\Delta^{[K]}:=\Delta([K])$ to denote the simplex over $[K]$.
We use $\operatorname{\mathcal{O}}$ to hide all constant factors, and use $\operatorname{\widetilde{\mathcal{O}}}$ to additionally suppress all logarithmic factors.
We usually use bold letters ${\bm{x}}$ to denote a vector, while $x_{i}$ denotes an entry of the vector. Unless mentioned explicitly, $\log(x)$ denotes the natural logarithm of $x$. Throughout the text, we will use $\{\mathcal{F}_{t}\}_{t=0}^{T}$ to denote the natural filtration, i.e., $\mathcal{F}_{t}$ represents the $\sigma$-algebra generated by all random observations made during the first $t$ time-slots.

Multi-Armed Bandits (MAB) is an interactive game between a player and an environment that lasts for a finite number of
$T>0$ rounds.
In each round $t\in[T]$, the player can choose an action from $K>0$ arms, denoted by $i_{t}\in[K]$.
Meanwhile, a $K$-dimensional loss vector $\bm{\ell}_{t}\in\mathbb{R}^{K}$ is generated by the environment from distribution $\bm{\nu}_{t}$, simultaneously without observing $i_{t}$.
The player then suffers a loss of $\ell_{t,i_{t}}$ and observe this loss (but not the whole loss vector $\bm{\ell}_{t}$).
The player’s objective is to minimize the expected total loss, or equivalently, minimize the following (pseudo-)regret:

$$ $\mathcal{R}_{T}:=\max_{i\in[K]}\mathbb{E}\left[\sum_{t=1}^{T}\ell_{t,i_{t}}- \sum_{t=1}^{T}\ell_{t,i}\right],$ (1) $$

where the expectation is taken w.r.t. the randomness when the player decides the action $i_{t}$ and the environment generates the loss $\bm{\ell}_{t}$. We use $i^{\ast}=\mathrm{argmin}_{i}\mathbb{E}\left[\sum_{t=1}^{T}\ell_{t,i}\right]$ to denote the optimal arm.

In Heavy-Tailed MABs (HTMAB), for every $t\in[T]$ and $i\in[K]$, the loss is independently sampled from some heavy-tailed distribution $\nu_{t,i}$ in the sense that $\mathbb{E}_{\ell\sim\nu_{t,i}}[\lvert\ell\rvert^{\alpha}]\leq\sigma^{\alpha}$, where $\alpha\in(1,2]$ and $\sigma\geq 0$ are some pre-determined but unknown constants.
A Best-of-Both-Worlds (BoBW) algorithm is one that behaves well in both stochastic and adversarial environments (Bubeck and Slivkins,, ), where stochastic environments are those with time-homogeneous $\{\bm{\nu}_{t}\}_{t\in[T]}$ (i.e., $\nu_{t,i}=\nu_{1,i}$ for every $t\in[T]$ and $i\in[K]$) and adversarial environments are those where $\nu_{t,i}$’s can depend on both $t$ and $i$. However, we do not allow the loss distributions to depend on the player’s previous actions.(^6^66Called oblivious adversary model (Bubeck and Slivkins,, ; Wei and Luo,, ; Zimmert and Seldin,, ).)

Before concluding this section, we make the following essential assumption. As shown in (Genalti et al.,, , Theorems 2 & 3), without Assumption 1, there does not exist HTMAB algorithms that can match the worst-case regret guarantees (Bubeck et al.,, ) without knowing either $\alpha$ or $\sigma$.

###### Assumption 1 (Truncated Non-Negative Loss (Huang et al.,, 2022 , Assumption 3.6) ) .

There exits an optimal arm $i^{\ast}\in[K]$ such that $\ell_{t,i^{\ast}}$ is truncated non-negative for all $t\in[T]$, where a random variable $X$ is called truncated non-negative if $\mathbb{E}[X\cdot\mathbbm{1}[|X|>M]]\geq 0$ for any $M\geq 0$.

Additionally, we make the following assumption for stochastic cases. Assumption 2 is common for algorithms utilizing self-bounding analyses, especially those with BoBW properties (Gaillard et al.,, ; Luo and Schapire,, ; Wei and Luo,, ; Zimmert and Seldin,, ; Ito et al.,, ).

###### Assumption 2 (Unique Best Arm) .

In stochastic setups, if we denote the mean of distribution $\nu_{1,i}$ as $\mu_{i}\coloneqq\mathbb{E}_{\ell\sim\nu_{1,i}}[\ell]$ for all $i\in[K]$, then there exists a unique best arm $i^{\ast}\in[K]$ such that $\Delta_{i}\coloneqq\mu_{i}-\mu_{i^{\ast}}>0$ for all $i\neq i^{\ast}$. That is, the minimum gap $\Delta_{\min}\coloneqq\min_{i\neq i^{\ast}}\Delta_{i}$ is positive.

###### Assumption 1 (Truncated Non-Negative Loss (Huang et al.,, 2022 , Assumption 3.6) ) .

###### Assumption 2 (Unique Best Arm) .

## 4 The BoBW HTMAB Algorithm uniINF

In this section, we introduce our novel algorithm uniINF (Algorithm 1) for parameter-free HTMABs achieving BoBW.
To tackle the adversarial environment, we adopt the famous Follow-the-Regularized-Leader (FTRL) framework instead the statistics-based approach. Moreover, we utilize the log-barrier regularizer to derive the logarithmic regret bound in stochastic setting. In the rest of this section, we introduce the main novel components in uniINF, including the refined log-barrier analysis (see Section 4.1), the auto-balancing learning rate scheduling scheme (see Section 4.2), and the adaptive skipping-clipping loss tuning technique (see Section 4.3).

Figure: Algorithm 1 uniINF: the universal INF-type algorithm for Parameter-Free HTMAB

### 4.1 Refined Log-Barrier Analysis

We adopt the log-barrier regularizer $\Psi_{t}({\bm{x}}):=-S_{t}\sum_{i=1}^{K}\log x_{i}$ in Equation 2 where $S_{t}^{-1}$ is the learning rate in round $t$. While log-barrier regularizers were commonly used in the literature for data-adaptive bounds such as small-loss bounds (Foster et al.,, ), path-length bounds (Wei and Luo,, ), and second-order bounds (Ito,, ), this paper introduces novel analysis illustrating that log-barrier regularizers also provide environment-adaptivity for both stochastic and adversarial settings.

Precisely, it is known that log-barrier applied to a loss sequence $\{\bm{c}_{t}\}_{t=1}^{T}$ ensures $\sum_{t=1}^{T}\langle\bm{x}_{t}-\bm{y},\bm{c}_{t}\rangle\lesssim\sum_{t=1}^{T}
((S_{t+1}-S_{t})K\log T+\textsc{Div}_{t})$ where $\textsc{Div}_{t}\leq S_{t}^{-1}\sum_{i=1}^{K}{\color[rgb]{0,0.5,0}x_{t,i}^{2}}
c_{t,i}^{2}$ for non-negative $\bm{c}_{t}$’s (Foster et al.,, , Lemma 16)
and $\textsc{Div}_{t}\leq S_{t}^{-1}\sum_{i=1}^{K}{\color[rgb]{0,0.5,0}x_{t,i}}c_{t
,i}^{2}$ for general $\bm{c}_{t}$’s (Dai et al.,, , Lemma 3.1).
In comparison, our Lemmas 4 and 5 focus on the case where $S_{t}$ is adequately large compared to $\lVert\bm{c}_{t}\rVert_{\infty}$ and give a refined version of $\textsc{Div}_{t}\leq S_{t}^{-1}\sum_{i=1}^{K}{\color[rgb]{0,0.5,0}x_{t,i}^{2}(
1-x_{t,i})^{2}}c_{t,i}^{2}$, which means

$$ $\sum_{t=1}^{T}\langle\bm{x}_{t}-\bm{y},\bm{c}_{t}\rangle\lesssim\sum_{t=1}^{T} (S_{t+1}-S_{t})K\log T+\sum_{t=1}^{T}S_{t}^{-1}\sum_{i=1}^{K}{\color[rgb]{ 0,0.5,0}x_{t,i}^{2}(1-x_{t,i})^{2}}c_{t,i}^{2}.$ (5) $$

The extra $(1-x_{t,i})^{2}$ terms are essential to exclude the optimal arm $i^{\ast}\in[K]$ — a nice property that leads to best-of-both-worlds guarantees (Zimmert and Seldin,, ; ).
To give more technical details on why we need this $(1-x_{t,i})^{2}$, in Section 5.1, we will decompose the regret into skipping error $\sum_{t=1}^{T}(\ell_{t,i_{t}}-\ell_{t,i_{t}}^{{\text{skip}}})\mathbbm{1}[i_{t}
\neq i^{\ast}]$ and main regret which is roughly $\sum_{t=1}^{T}\langle\bm{x}_{t}-\bm{y},\bm{\ell}^{{\text{skip}}}_{t}\rangle$.
The skipping errors already include the indicator $\mathbbm{1}[i_{t}\neq i^{\ast}]$, so the exclusion of $i^{\ast}$ is automatic. However, for the main regret, we must manually introduce some $(1-x_{t,i})$ to exclude $i^{\ast}$ — which means the previous bounds mentioned above do not apply, while our novel Equation 5 is instead helpful.

### 4.2 Auto-Balancing Learning Rate Scheduling Scheme

The design of the learning rate $S_{t}$ in our algorithm Algorithm 1 is specified in Equation 4 as $S_{t+1}^{2}=S_{t}^{2}+(\ell_{t,i_{t}}^{\text{clip}})^{2}\cdot(1-x_{t,i_{t}})^{
2}\cdot(K\log T)^{-1}$. The idea is to balance a Bregman divergence term $\textsc{Div}_{t}$ and a $\Psi$-shifting term $\textsc{Shift}_{t}$ that arise in our regret analysis (roughly corresponding to the terms on the RHS of Equation 5). They allow the following upper bounds as we will include as Lemmas 5 and 9:

$$ $\underbrace{\textsc{Div}_{t}\leq\operatorname{\mathcal{O}}\left(S_{t}^{-1} \left(\ell_{t,i_{t}}^{\text{clip}}\right)^{2}(1-x_{t,i_{t}})^{2}\right)}_{ \text{Bregman Divergence}},\quad\underbrace{\textsc{Shift}_{t}\leq{\mathcal{O} }\left((S_{t+1}-S_{t})\cdot K\log T\right)}_{\text{$\Psi$-Shifting}}.$ (6) $$

Thus, to make $\textsc{Div}_{t}$ roughly the same as $\textsc{Shift}_{t}$, it suffices to ensure $(S_{t+1}-S_{t})S_{t}\approx(\ell_{t,i_{t}}^{\text{clip}})^{2}(1-x_{t,i_{t}})^{
2}\cdot(K\log T)^{-1}$. Our definition of $S_{t}$ in Equation 4 follows since $(S_{t+1}-S_{t})S_{t}\approx S_{t+1}^{2}-S_{t}^{2}$.

### 4.3 Adaptive Skipping-Clipping Loss Tuning Technique

For heavy-tailed losses, a unique challenge is that $\mathbb{E}[\ell^{2}_{t,i_{t}}]$, the squared incurred loss appearing in the Bregman divergence term (as shown in Equation 6), does not allow a straightforward upper bound as we only have $\mathbb{E}[\lvert\ell_{t,i_{t}}\rvert^{\alpha}]\leq\sigma^{\alpha}$. A previous workaround is deploying a skipping technique that replaces large loss with 0 0 (Huang et al.,, ). This technique forbids a sudden increase in the divergence term and thus eases the balance between $\textsc{Div}_{t}$ and $\textsc{Shift}_{t}$.
However, this skipping is not a free lunch: if we skipped too much, the increase of $S_{t}$ will be slow, which makes the skipping threshold $C_{t,i}$ grow slowly as well — therefore, we end up skipping even more and incurring tremendous skipping error! This eventually stops us from establishing instance-dependent guarantees in stochastic setups.

To address this limitation, we develop an adaptive skipping-clipping technique. The idea is to ensure that every loss will influence the learning process — imagine that the green $\ell_{t,i_{t}}^{\text{clip}}$ in Equation 4 is replaced by $\ell_{t,i_{t}}^{\text{skip}}$, then $S_{t}$ will not change if the current $\ell_{t,i_{t}}$ is large, which risks the algorithm from doing nothing if happening repeatedly.
Instead, our clipping technique induces an adequate reaction upon observing a large loss, which both prevents the learning rate $S_{t}$ from having a drastic change and ensures the growth of $S_{t}$ is not too slow. Specifically, from Equation 4, if we skip the loss $\ell_{t,i_{t}}$, we must have $S_{t+1}=\Theta(1+(K\log T)^{-1})S_{t}$. This is crucial for our stopping-time analysis in Section 5.2.

While clipping is used to tune $S_{t}$, we use the skipped loss $\bm{\ell}^{\text{skip}}_{t}$ (more specifically, its importance-weighted version $\widetilde{\bm{\ell}}_{t}$) to decide the action $\bm{x}_{t}$ in the FTRL update Equation 2.
Utilizing the truncated non-negativity assumption (Assumption 1), we can exclude one arm when controlling the skipping error, as already seen in Equation 5. We shall present more details in Section 5.4.

## 5 Main Results

The main guarantee of our uniINF (Algorithm 1) is presented in Theorem 3 below, which states that uniINF achieves both optimal minimax regret for adversarial cases (up to logarithmic factors) and near-optimal instance-dependent regret for stochastic cases.

###### Theorem 3 (Main Guarantee) .

Under the adversarial environments, uniINF (Algorithm 1) achieves

$$ $\displaystyle{\mathcal{R}}_{T}=\widetilde{{\mathcal{O}}}\left(\sigma K^{1- \nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{\alpha}}}\right).$ $$

Moreover, for the stochastic environments, uniINF (Algorithm 1) guarantees

$$ ${\mathcal{R}}_{T}={\mathcal{O}}\left(K\left(\frac{\sigma^{\alpha}}{\Delta_{ \min}}\right)^{\frac{1}{\alpha-1}}\log T\cdot\log\frac{\sigma^{\alpha}}{\Delta _{\min}}\right).$ $$

The formal proof of this theorem is provided in Appendix D. As shown in Table 1, our uniINF automatically achieves nearly optimal instance-dependent and instance-independent regret guarantees in stochastic and adversarial environments, respectively. Specifically, under stochastic settings, uniINF achieves the regret upper bound ${\mathcal{O}}\left(K\left(\nicefrac{{\sigma^{\alpha}}}{{\Delta_{\min}}}\right)
^{\nicefrac{{1}}{{\alpha-1}}}\log T\cdot\log\nicefrac{{\sigma^{\alpha}}}{{
\Delta_{\min}}}\right)$.
Compared to the instance-dependent lower bound $\Omega\left(\sum_{i\neq i^{\ast}}(\nicefrac{{\sigma^{\alpha}}}{{\Delta_{i}}})^
{\nicefrac{{1}}{{\alpha-1}}}\log T\right)$ given by Bubeck et al., (), our result matches the lower bound up to logarithmic factors $\log\nicefrac{{\sigma^{\alpha}}}{{\Delta_{\min}}}$ which is independent of $T$ when all $\Delta_{i}$’s are similar to the dominant sub-optimal gap $\Delta_{\min}$.
For adversarial environments, our algorithm achieves an $\widetilde{{\mathcal{O}}}\left(\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{
\nicefrac{{1}}{{\alpha}}}\right)$ regret, which matches the instance-independent lower bound $\Omega\left(\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{\alpha}}}\right)$ given in Bubeck et al., () up to logarithmic terms. Therefore, the regret guarantees of uniINF are nearly-optimal in both stochastic and adversarial environments .

###### Theorem 3 (Main Guarantee) .

### 5.1 Regret Decomposition

In Sections 5.1, 5.2, 5.3, and 5.4, we sketch the proof of our BoBW result in Theorem 3.
To begin with, we decompose the regret $\mathcal{R}_{T}$ into a few terms and handle each of them separately. Denoting ${\bm{y}}\in\mathbb{R}^{K}$ as the one-hot vector on the optimal action $i^{\ast}\in[K]$, i.e., $y_{i}:=\mathbbm{1}[i=i^{\ast}]$, we know from Equation 1 that

$$ $\displaystyle{\mathcal{R}}_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\langle{\bm{x}}_{ t}-{\bm{y}},{\bm{\ell}}_{t}\rangle\right].$ $$

As the log-barrier regularizer $\Psi_{t}$ is prohibitively large when close to the boundary of $\Delta^{[K]}$, we instead consider the adjusted benchmark $\widetilde{{\bm{y}}}$ defined as $\widetilde{y}_{i}:=\begin{cases}\frac{1}{T}&i\neq i^{\ast}\\
1-\frac{K-1}{T}&i=i^{\ast}\end{cases}$ and rewrite ${\mathcal{R}}_{T}$ as

$$ $\displaystyle{\mathcal{R}}_{T}=\underbrace{\mathbb{E}\left[\sum_{t=1}^{T} \langle\widetilde{\bm{y}}-{\bm{y}},{\bm{\ell}}^{\text{skip}}_{t}\rangle\right] }_{\textsc{I. Benchmark Calibration Error}}+\underbrace{\mathbb{E}\left[\sum_{ t=1}^{T}\langle{\bm{x}}_{t}-\widetilde{\bm{y}},{\bm{\ell}}^{\text{skip}}_{t} \rangle\right]}_{\textsc{II. Main Regret}}+\underbrace{\mathbb{E}\left[\sum_{t =1}^{T}\langle{\bm{x}}_{t}-{\bm{y}},{\bm{\ell}}_{t}-{\bm{\ell}}^{\text{skip}}_ {t}\rangle\right]}_{\textsc{III. Skipping Error}}.$ (7) $$

We now go over each term one by one.

Term I. Benchmark Calibration Error.
As in a typical log-barrier analysis (Wei and Luo,, ; Ito,, ), the Benchmark Calibration Error is not the dominant term. This is because

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\langle\widetilde{\bm{y}}-{\bm{y}}, {\bm{\ell}}^{\text{skip}}_{t}\rangle\right]\leq\sum_{t=1}^{T}\frac{K-1}{T} \mathbb{E}[|\ell^{\text{skip}}_{t,i_{t}}|]\leq\sum_{t=1}^{T}\frac{K-1}{T} \mathbb{E}[|\ell_{t,i_{t}}|]\leq\sigma K,$ $$

which is independent from $T$. Therefore, the key is analyzing the other two terms.

Term II. Main Regret.
By FTRL regret decomposition (see Lemma 29 in the appendix; it is an extension of the classical FTRL bounds (Lattimore and Szepesvári,, , Theorem 28.5)), we have

$$ $\displaystyle\quad\textsc{Main Regret}=\mathbb{E}\left[\sum_{t=1}^{T}\langle{ \bm{x}}_{t}-\widetilde{\bm{y}},{\bm{\ell}}^{\text{skip}}_{t}\rangle\right]= \mathbb{E}\left[\sum_{t=1}^{T}\langle{\bm{x}}_{t}-\widetilde{\bm{y}}, \widetilde{{\bm{\ell}}}_{t}\rangle\right]$ $\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}[D_{\Psi_{t}}({\bm{x}}_{t},{\bm{z}}_{ t})]+\sum_{t=0}^{T-1}\mathbb{E}\left[\left(\Psi_{t+1}(\widetilde{\bm{y}})-\Psi _{t}(\widetilde{\bm{y}})\right)-\left(\Psi_{t+1}({\bm{x}}_{t+1})-\Psi_{t}({\bm {x}}_{t+1})\right)\right],$ $$

where $D_{\Psi_{t}}(\bm{y},\bm{x})=\Psi_{t}(\bm{y})-\Psi_{t}(\bm{x})-\langle\nabla
\Psi_{t}(\bm{x}),\bm{y}-\bm{x}\rangle$ is the Bregman divergence induced by the $t$-th regularizer $\Psi_{t}$, and ${\bm{z}}_{t}$ denotes the posterior optimal estimation in episode $t$, namely

$$ $\displaystyle{\bm{z}}_{t}:=\operatorname*{argmin}_{{\bm{z}}\in\Delta^{[K]}} \left(\sum_{s=1}^{t}\langle\widetilde{{\bm{\ell}}}_{s},{\bm{z}}\rangle+\Psi_{t }({\bm{z}})\right).$ (8) $$

For simplicity, we use the abbreviation $\textsc{Div}_{t}:=D_{\Psi_{t}}({\bm{x}}_{t},{\bm{z}}_{t})$ for the Bregman divergence between ${\bm{x}}_{t}$ and ${\bm{z}}_{t}$ under regularizer $\Psi_{t}$, and let $\textsc{Shift}_{t}:=\left[\left(\Psi_{t+1}(\widetilde{\bm{y}})-\Psi_{t}(
\widetilde{\bm{y}})\right)-\left(\Psi_{t+1}({\bm{x}}_{t+1})-\Psi_{t}({\bm{x}}_
{t+1})\right)\right]$ be the $\Psi$-shifting term. Then, we can reduce the analysis of main regret to bounding the sum of Bregman divergence term $\mathbb{E}[\textsc{Div}_{t}]$ and $\Psi$-shifting term $\mathbb{E}[\textsc{Shift}_{t}]$.

Term III. Skipping Error.
To control the skipping error, we define $\textsc{SkipErr}_{t}:=\ell_{t,i_{t}}-\ell_{t,i_{t}}^{\text{skip}}=\ell_{t,i_{t
}}\mathbbm{1}[\lvert\ell_{t,i_{t}}\rvert\geq C_{t,i_{t}}]$ as the loss incurred by the skipping operation at episode $t$. Then we have

$$ $\displaystyle\langle{\bm{x}}_{t}-{\bm{y}},{\bm{\ell}}_{t}-{\bm{\ell}}_{t}^{ \text{skip}}\rangle$ $\displaystyle=\sum_{i\in[K]}(x_{t,i}-y_{i})\cdot(\ell_{t,i}-\ell_{t,i}^{\text{ skip}})$ $\displaystyle\leq\sum_{i\neq i^{\ast}}x_{t,i}\cdot\left|\ell_{t,i}-\ell^{\text {skip}}_{t,i}\right|+(x_{t,i^{\ast}}-1)\cdot\left(\ell_{t,i^{\ast}}-\ell_{t,i^ {\ast}}^{\text{skip}}\right)$ $\displaystyle=\mathbb{E}\left[\lvert\textsc{SkipErr}_{t}\rvert\cdot\mathbbm{1} [i_{t}\neq i^{\ast}]\mid\mathcal{F}_{t-1}\right]+(x_{t,i^{\ast}}-1)\cdot\left( \ell_{t,i^{\ast}}-\ell_{t,i^{\ast}}^{\text{skip}}\right).$ $$

Notice that the factor $(x_{t,i^{\ast}}-1)$ in the second term is negative and ${\mathcal{F}}_{t-1}$-measurable, and we have

$$ $\displaystyle\mathbb{E}\left[\ell_{t,i^{\ast}}-\ell_{t,i^{\ast}}^{\text{skip}} \middle|\mathcal{F}_{t-1}\right]$ $\displaystyle=\mathbb{E}\left[\mathbbm{1}[\lvert\ell_{t,i^{\ast}}\rvert\geq C_ {t,i^{\ast}}]\cdot\ell_{t,i^{\ast}}\right]\geq 0,$ $$

where the inequality is due to the truncated non-negative assumption (Assumption 1) of the optimal arm $i^{\ast}$. Therefore, we have $\mathbb{E}[(x_{t,i^{\ast}}-1)\cdot(\ell_{t,i^{\ast}}-\ell_{t,i^{\ast}}^{\text{
skip}})\mid\mathcal{F}_{t-1}]\leq 0$ and thus

$$ $\displaystyle\mathbb{E}[\langle{\bm{x}}_{t}-{\bm{y}},{\bm{\ell}}_{t}-{\bm{\ell }}_{t}^{\text{skip}}\rangle\mid\mathcal{F}_{t-1}]$ $\displaystyle\leq\mathbb{E}[\lvert\textsc{SkipErr}_{t}\rvert\cdot\mathbbm{1}[i _{t}\neq i^{\ast}]\mid\mathcal{F}_{t-1}],$ (9) $$

which gives an approach to control the skipping error by the sum of skipping losses $\textsc{SkipErr}_{t}$’s where we pick a sub-optimal arm $i_{t}\neq i^{\ast}$. Formally, we give the following inequality:

$$ $\displaystyle\textsc{Skipping Error}\leq\mathbb{E}\left[\sum_{t=1}^{T}\lvert \textsc{SkipErr}_{t}\rvert\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\right].$ $$

To summarize, the regret ${\mathcal{R}}_{T}$ decomposes into the sum of Bregman divergence terms $\mathbb{E}[\textsc{Div}_{t}]$, the $\Psi$-shifting terms $\mathbb{E}[\textsc{Shift}_{t}]$, and the sub-optimal skipping losses $\mathbb{E}[|\textsc{SkipErr}_{t}|\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]]$, namely

$$ $\displaystyle{\mathcal{R}}_{T}\leq\underbrace{\mathbb{E}\left[\sum_{t=1}^{T} \textsc{Div}_{t}\right]}_{\textsc{Bregman Divergence Terms}}+\underbrace{ \mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]}_{\textsc{$\Psi$- Shifting Terms}}+\underbrace{\mathbb{E}\left[\sum_{t=1}^{T}|\textsc{SkipErr}_{ t}|\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\right]}_{\textsc{Sub-Optimal Skipping Losses}}+\sigma K.$ (10) $$

In Sections 5.2, 5.3, and 5.4, we analyze these three key items and introduce our novel analytical techniques for both adversarial and stochastic cases. Specifically, we bound the Bregman divergence terms in Section 5.2 (all formal proofs in Appendix A), the $\Psi$-shifting terms in Section 5.3 (all formal proofs in Appendix B), and the skipping error terms in Section 5.4 (all formal proofs in Appendix C). Afterwards, to get our Theorem 3, putting Theorems 7, 10, and 13 together gives the adversarial guarantee, while the stochastic guarantee follows from a combination of Theorems 8, 11, and 14.

### 5.2 Analyzing Bregman Divergence Terms

From the log-barrier regularizer defined in Equation 2, we can explicitly write out $\textsc{Div}_{t}$ as

$$ $\displaystyle\textsc{Div}_{t}$ $\displaystyle=D_{\Psi_{t}}(\bm{x}_{t},\bm{z}_{t})=S_{t}\sum_{i\in[K]}\left(- \log\frac{x_{t,i}}{z_{t,i}}+\frac{x_{t,i}}{z_{t,i}}-1\right).$ $$

To simplify notations, we define $w_{t,i}:=\frac{x_{t,i}}{z_{t,i}}-1$, which gives $\textsc{Div}_{t}=S_{t}\sum_{i=1}^{K}(w_{t,i}-\log(w_{t,i}+1))$. Therefore, one natural idea is to utilize the inequality $x-\log(x+1)\leq x^{2}$ for $x\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$. To do so, we need to conclude $-\nicefrac{{1}}{{2}}\leq w_{t,i}\leq\nicefrac{{1}}{{2}}$. We develop a novel technical tool to depict ${\bm{z}}_{t}$ and provide an important technical lemma which says ${\bm{z}}_{t}$ is multiplicatively close to ${\bm{x}}_{t}$:

###### Lemma 4 ( ${\bm{z}}_{t}$ is Multiplicatively Close to ${\bm{x}}_{t}$ ) .

$\frac{1}{2}x_{t,i}\leq z_{t,i}\leq 2x_{t,i}$ for every $t\in[T]$ and $i\in[K]$.

Lemma 4 implies $w_{t,i}\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$. Hence $\textsc{Div}_{t}=S_{t}\sum_{t=1}^{K}(w_{t,i}-\log(w_{t,i}+1))\leq S_{t}\sum_{t
=1}^{K}w_{t,i}^{2}$.
Conditioning on the natural filtration ${\mathcal{F}}_{t-1}$, $w_{t,i}$ is fully determined by feedback $\widetilde{{\bm{\ell}}}_{t}$ in episode $t$, which allows us to give a precise depiction of $w_{t,i}$ via calculating the partial derivative ${\partial w_{t,i}}/{\partial\widetilde{\ell}_{t,j}}$ and invoking the intermediate value theorem. The detailed procedure is included as Lemma 16 in the appendix, which further results in the following lemma on the Bregman divergence term $\textsc{Div}_{t}$.

###### Lemma 5 (Upper Bound of $\textsc{Div}_{t}$ ) .

For every $t\in[T]$, we can bound $\textsc{Div}_{t}$ as

$$ $\textsc{Div}_{t}={\mathcal{O}}\left(S_{t}^{-1}(\ell^{\text{skip}}_{t,i_{t}})^{ 2}(1-x_{t,i_{t}})^{2}\right),\quad\sum_{\tau=1}^{t}\textsc{Div}_{\tau}={ \mathcal{O}}\left(S_{t+1}\cdot K\log T\right).$ $$

Compared to previous bounds on $\textsc{Div}_{t}$, Lemma 5 contains an $(1-x_{t,i_{t}})^{2}$ that is crucial for our instance-dependent bound and serves as a main technical contribution, as we sketched in Section 4.1.

###### Lemma 4 ( 𝒛 t subscript 𝒛 𝑡 {\bm{z}}_{t} bold_italic_z start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT is Multiplicatively Close to 𝒙 t subscript 𝒙 𝑡 {\bm{x}}_{t} bold_italic_x start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT ) .

###### Lemma 5 (Upper Bound of Div t subscript Div 𝑡 \textsc{Div}_{t} Div start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT ) .

#### Adversarial Cases.

By definition of $S_{t}$ in Equation 4, we can bound $S_{T+1}$ as in the following lemma.

###### Lemma 6 (Upper Bound for $S_{T+1}$ ) .

The expectation of $S_{T+1}$ can be bounded by

$$ $\displaystyle\mathbb{E}[S_{T+1}]\leq 2\cdot\sigma(K\log T)^{-\nicefrac{{1}}{{ \alpha}}}T^{\nicefrac{{1}}{{\alpha}}}.$ (11) $$

Combining this upper-bound on $\mathbb{E}[S_{T+1}]$ with Lemma 5, we can control the expected sum of Bregman divergence terms $\mathbb{E}[\sum_{t=1}^{T}\textsc{Div}_{t}]$ in adversarial environments, as stated in the following theorem.

###### Theorem 7 (Adversarial Bounds for Bregman Divergence Terms) .

In adversarial environments, the sum of Bregman divergence terms can be bounded by

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]=\widetilde{ {\mathcal{O}}}\left(\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{ \alpha}}}\right).$ $$

###### Lemma 6 (Upper Bound for S T + 1 subscript 𝑆 𝑇 1 S_{T+1} italic_S start_POSTSUBSCRIPT italic_T + 1 end_POSTSUBSCRIPT ) .

###### Theorem 7 (Adversarial Bounds for Bregman Divergence Terms) .

#### Stochastic Cases.

For $\operatorname{\mathcal{O}}(\log T)$ bounds, we opt for the first statement of Lemma 5. By definition of $\ell_{t,i_{t}}^{\text{skip}}$, we immediately have $|\ell_{t,i_{t}}^{\text{skip}}|\leq C_{t,i_{t}}=\operatorname{\mathcal{O}}(S_{t
}(1-x_{t,i_{t}})^{-1})$. Further using $\mathbb{E}[\lvert\ell_{t,i_{t}}\rvert^{\alpha}]\leq\sigma^{\alpha}$, we have $\mathbb{E}[\textsc{Div}_{t}\mid\mathcal{F}_{t-1}]={\mathcal{O}}(S_{t}^{1-
\alpha}\sigma^{\alpha}(1-x_{t,i^{\ast}}))$ (formalized as Lemma 20 in the appendix).

We can now perform a stopping-time argument for the sum of Bregman divergence terms in stochastic cases. Briefly, we pick a fixed constant $M>0$. The expected sum of $\textsc{Div}_{t}$’s on those $\{t\mid S_{t}\geq M\}$ is then within $\operatorname{\mathcal{O}}(M^{1-\alpha}\cdot T)$ according to Lemma 5. On the other hand, we claim that the sum of $\textsc{Div}_{t}$’s on those $\{t\mid S_{t}<M\}$ can also be well controlled because $\mathbb{E}[\textsc{Div}_{t}\mid\mathcal{F}_{t-1}]={\mathcal{O}}(\mathbb{E}[S_{
t}^{1-\alpha}\sigma^{\alpha}(1-x_{t,i^{\ast}})\mid{\mathcal{F}}_{t-1}])$.
The detailed analysis is presented in Section A.6, and we summarize it as follows. Therefore, the sum of Bregman divergences in stochastic environments is also well-controlled.

###### Theorem 8 (Stochastic Bounds for Bregman Divergence Terms) .

In stochastic settings, the sum of Bregman divergence terms can be bounded by

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]={\mathcal{O }}\left(K\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{\min}^{-\frac{1}{\alpha-1}} \log T+\frac{{\mathcal{R}}_{T}}{4}\right).$ $$

###### Theorem 8 (Stochastic Bounds for Bregman Divergence Terms) .

### 5.3 Analyzing Ψ Ψ \Psi roman_Ψ -Shifting Terms

Since our choice of $\{S_{t}\}_{t\in[T]}$ is non-decreasing, the $\Psi$-shifting term $\Psi_{t+1}({\bm{x}})-\Psi_{t}({\bm{x}})\geq 0$ trivially holds for any ${\bm{x}}\in\Delta^{[K]}$. We get the following lemma by algebraic manipulations.

###### Lemma 9 (Upper Bound of $\textsc{Shift}_{t}$ ) .

For every $t\geq 0$, we can bound $\textsc{Shift}_{t}$ as

$$ $\displaystyle\textsc{Shift}_{t}={\mathcal{O}}\left(S_{t}^{-1}(\ell^{{\text{ clip}}}_{t,i_{t}})^{2}(1-x_{t,i_{t}})^{2}\right),\quad\sum_{\tau=0}^{t}\textsc {Shift}_{\tau}={\mathcal{O}}\left(S_{t+1}\cdot K\log T\right).$ $$

Similarly, Lemma 9 also contains a useful $(1-x_{t,i_{t}})^{2}$ term — in fact, the two bounds in Lemma 9 are extremely similar to those in Lemma 5 and thus allow analogous analyses. This is actually an expected phenomenon, thanks to our auto-balancing learning rates introduced in Section 4.2.

###### Lemma 9 (Upper Bound of Shift t subscript Shift 𝑡 \textsc{Shift}_{t} Shift start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT ) .

#### Adversarial Cases.

Again, we utilize the $\mathbb{E}[S_{T+1}]$ bound in Lemma 6 and get the following theorem.

###### Theorem 10 (Adversarial Bounds for $\Psi$ -Shifting Terms) .

In adversarial environments, the expectation of the sum of $\Psi$-shifting terms can be bounded by

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]\leq \mathbb{E}[S_{T+1}\cdot(K\log T)]=\widetilde{{\mathcal{O}}}\left(\sigma K^{1- \nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{\alpha}}}\right).$ $$

###### Theorem 10 (Adversarial Bounds for Ψ Ψ \Psi roman_Ψ -Shifting Terms) .

#### Stochastic Cases.

Still similar to $\textsc{Div}_{t}$’s, we condition on ${\mathcal{F}}_{t-1}$ and utilize $\lvert\ell_{t,i_{t}}^{{\text{clip}}}\rvert\leq C_{t,i_{t}}$ to get $\mathbb{E}\left[\textsc{Shift}_{t}\mid{\mathcal{F}}_{t-1}\right]={\mathcal{O}}
(S_{t}^{1-\alpha}\sigma^{\alpha}(1-x_{t,i^{\ast}}))$ (formalized as Lemma 24 in the appendix). Thus, for stochastic environments, a stopping-time argument similar to that of $\textsc{Div}_{t}$ yields Theorem 11.

###### Theorem 11 (Stochastic Bounds for $\Psi$ -shifting Terms) .

In stochastic environments, the sum of $\Psi$-shifting terms can be bounded by

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]={ \mathcal{O}}\left(K\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{\min}^{-\frac{1}{ \alpha-1}}\log T+\frac{{\mathcal{R}}_{T}}{4}\right).$ $$

###### Theorem 11 (Stochastic Bounds for Ψ Ψ \Psi roman_Ψ -shifting Terms) .

### 5.4 Analyzing Sub-Optimal Skipping Losses

This section controls the sub-optimal skipping losses when we pick a sub-optimal arm $i_{t}\neq i^{\ast}$, i.e.,

$$ $\sum_{t=1}^{T}\lvert\textsc{SkipErr}_{t}\cdot\mathbbm{1}[i_{t}\neq i^{\ast}] \rvert=\sum_{t=1}^{T}\lvert\ell_{t,i_{t}}-\ell^{\text{skip}}_{t,i_{t}}\rvert \cdot\mathbbm{1}[i_{t}\neq i^{\ast}]=\sum_{t=1}^{T}\lvert\ell_{t,i_{t}}\rvert \cdot\mathbbm{1}[\lvert\ell_{t,i_{t}}\rvert\geq C_{t,i_{t}}]\cdot\mathbbm{1}[i _{t}\neq i^{\ast}].$ $$

For skipping errors, we need a more dedicated stopping-time analysis in both adversarial and stochastic cases.
Different from previous sections, it is now non-trivial to bound the sum of $\textsc{SkipErr}_{t}$’s on those $\{t\mid S_{t}<M\}$ where $M$ is the stopping-time threshold. However, a key observation is that whenever we encounter a non-zero $\textsc{SkipErr}_{t}$, $S_{t+1}$ will be $\Omega(1)$-times larger than $S_{t}$, thanks to the adaptive skipping-clipping technique. Thus the number of non-zero $\textsc{SkipErr}_{t}$’s before $S_{t}$ reaching $M$ is small.
Equipped with this observation, we derive the following lemma, whose formal proof is included in Section C.1.

###### Lemma 12 (Stopping-Time Argument for Skipping Losses) .

Given a stopping-time threshold $M$, the total skipping loss on those $t$’s with $i_{t}\neq i^{\ast}$ is bounded by

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}|\textsc{SkipErr}_{t}|\cdot\mathbbm {1}[i_{t}\neq i^{\ast}]\right]\leq M\left(\frac{\sigma^{\alpha}}{M^{\alpha}} \mathbb{E}\left[\sum_{t=1}^{T}\mathbbm{1}[i_{t}\neq i^{\ast}]\right]+2\cdot \frac{\log M}{\log\left(1+\frac{1}{16K\log T}\right)}+1\right).$ $$

Equipped with this novel stopping-time analysis, it only remains to pick a proper threshold $M$ for Lemma 12. It turns out that for adversarial and stochastic cases, we have to pick different $M$’s. Specifically, we achieve the following two theorems, whose proofs are in Sections C.2 and C.3.

###### Theorem 13 (Adversarial Bounds for Skipping Losses) .

By setting adversarial stopping-time threshold $M^{\text{adv}}:=\sigma(K\log T)^{-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{
\alpha}}}$, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}|\textsc{SkipErr}_{t}|\cdot\mathbbm {1}[i_{t}\neq i^{\ast}]\right]$ $\displaystyle=\widetilde{{\mathcal{O}}}\left(\sigma K^{1-\nicefrac{{1}}{{ \alpha}}}T^{\nicefrac{{1}}{{\alpha}}}\right).$ $$

###### Theorem 14 (Stochastic Bounds for Skipping Losses) .

By setting stochastic stopping-time threshold $M^{\text{sto}}:=4^{\frac{1}{\alpha-1}}\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{
\min}^{-\frac{1}{\alpha-1}}$, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}|\textsc{SkipErr}_{t}|\cdot\mathbbm {1}[i_{t}\neq i^{\ast}]\right]={\mathcal{O}}\left(K\log T\cdot\sigma^{\frac{ \alpha}{\alpha-1}}\Delta_{\min}^{-\frac{1}{\alpha-1}}\cdot\log(\sigma^{\alpha} /\Delta_{\min})+\frac{{\mathcal{R}}_{T}}{4}\right).$ $$

###### Lemma 12 (Stopping-Time Argument for Skipping Losses) .

###### Theorem 13 (Adversarial Bounds for Skipping Losses) .

###### Theorem 14 (Stochastic Bounds for Skipping Losses) .

## 6 Conclusion

This paper designs the first algorithm for Parameter-Free HTMABs that enjoys the Best-of-Both-Worlds property. Specifically, our algorithm, uniINF, simultaneously achieves near-optimal instance-independent and instance-dependent bounds in adversarial and stochastic environments, respectively. uniINF incorporates several innovative algorithmic components, such as i) refined log-barrier analysis, ii) auto-balancing learning rates, and iii) adaptive skipping-clipping loss tuning. Analytically, we also introduce meticulous techniques including iv) analyzing Bregman divergence via partial derivatives and intermediate value theorem and v) stopping-time analysis for logarithmic regret. We expect many of these techniques to be of independent interest. In terms of limitations, uniINF does suffer from some extra logarithmic factors; it’s dependency on the gaps $\{\Delta_{i}^{-1}\}_{i\neq i^{\ast}}$ is also improvable when some of the gaps are much smaller than the other. We leave these for future investigation.

## Appendix A Bregman Divergence Terms: Omitted Proofs in Section 5.2

In this section, we present the omitted proofs in Section 5.2, the analyses for the Bregman divergence term $\textsc{Div}_{t}=D_{\Psi_{t}}(\bm{x}_{t},\bm{z}_{t})=\Psi_{t}({\bm{x}}_{t})-
\Psi_{t}({\bm{z}}_{t})-\langle\nabla\Psi_{t}({\bm{z}}_{t}),{\bm{x}}_{t}-{\bm{z
}}_{t}\rangle$ where ${\bm{x}}_{t},{\bm{z}}_{t}$ are defined as

$$ $\displaystyle{\bm{x}}_{t}:=\operatorname*{argmin}_{{\bm{x}}\in\Delta^{[K]}} \langle{\bm{L}}_{t-1},{\bm{x}}\rangle+\Psi_{t}({\bm{x}}),$ $\displaystyle{\bm{z}}_{t}:=\operatorname*{argmin}_{{\bm{z}}\in\Delta^{[K]}} \langle{\bm{L}}_{t},{\bm{z}}\rangle+\Psi_{t}({\bm{z}}),$ $$

and ${\bm{L}}_{t}$ is defined as the cumulative loss

$$ $\displaystyle{\bm{L}}_{t}=\sum_{s=1}^{t}\widetilde{{\bm{\ell}}}_{s},\quad \widetilde{\ell}_{s,i}=\frac{\ell_{t,i}^{{\text{skip}}}}{x_{t,i}}\cdot\mathbbm {1}[i=i_{t}].$ $$

By KKT conditions, there exist two unique multipliers $Z_{t}$ and $\widetilde{Z}_{t}$ such that

$$ $\displaystyle x_{t,i}=\frac{S_{t}}{L_{t-1,i}-Z_{t}},\quad z_{t,i}=\frac{S_{t}} {L_{t,i}-\widetilde{Z}_{t}},\quad\forall i\in[K].$ $$

We highlight that $Z_{t}$ is fixed conditioning on ${\mathcal{F}}_{t-1}$, while $\widetilde{Z}_{t}$ is fully determined by $\widetilde{{\bm{\ell}}}_{t}$.

### A.1 z t , i subscript 𝑧 𝑡 𝑖 z_{t,i} italic_z start_POSTSUBSCRIPT italic_t , italic_i end_POSTSUBSCRIPT is Multiplicatively Close to x t , i subscript 𝑥 𝑡 𝑖 x_{t,i} italic_x start_POSTSUBSCRIPT italic_t , italic_i end_POSTSUBSCRIPT : Proof of Lemma 4

Lemma 4 investigates the relationship between $x_{t,i}$ and $z_{t,i}$. By previous discussion, the key of the proof is carefully studied the multipliers $Z_{t}$ and $\widetilde{Z}_{t}$.

###### Lemma 15 (Restatement of Lemma 4 ) .

For every $t\in[T]$ and $i\in[K]$, we have

$$ $\displaystyle\frac{1}{2}x_{t,i}\leq z_{t,i}\leq 2x_{t,i}.$ $$

###### Proof.

Positive Loss.
Below we first consider $\widetilde{\ell}_{t,i_{t}}>0$, the other case $\widetilde{\ell}_{t,i_{t}}<0$ can be verified similarly, and the $\widetilde{\ell}_{t,i_{t}}=0$ case is trivial. We prove this lemma for left and right sides, respectively.

The left side $\frac{1}{2}x_{t,i}\leq z_{t,i}$:
According to the KKT conditions, given $S_{t}$ and $L_{t-1}$ ($L_{t}$), the goal of computing $x_{t}$ ($z_{t}$) can be reduced to find a scalar multiplier $Z_{t}$ ($\widetilde{Z}_{t}$), such that we have

$$ $\displaystyle\sum_{i=1}^{K}x_{t,i}(Z_{t})=1$ $$

and

$$ $\displaystyle\sum_{i=1}^{K}z_{t,i}(\widetilde{Z}_{t})=1$ $$

where

$$ $\displaystyle x_{t,i}(\lambda)=\frac{S_{t}}{L_{t-1,i}-\lambda},\quad z_{t,i}( \lambda)=\frac{S_{t}}{L_{t,i}-\lambda}=\frac{S_{t}}{L_{t-1,i}+\widetilde{\ell} _{t,i}-\lambda}.$ (12) $$

Note that each $z_{t,i}(\lambda)$ is an increasing function of $\lambda$ on $(-\infty,L_{t,i}]$. Since $\widetilde{\ell}_{t,i_{t}}>0$, it is easy to see that $z_{t,i_{t}}(Z_{t})<x_{t,i_{t}}$. Thus in order to satisfy the sum-to-one constraint, we must have $\widetilde{Z}_{t}>Z_{t}$ and $\widetilde{Z}_{t}-Z_{t}<\widetilde{\ell}_{t,i_{t}}$. Moreover, we have $z_{t,i_{t}}<x_{t,i_{t}}$ and $z_{t,i}>x_{t,i}$ for all $i\neq i_{t}$. Therefore, we only need to prove that $z_{t,i_{t}}\geq\frac{1}{2}x_{t,i_{t}}$. Thanks to the monotonicity of $z_{t,i}(\lambda)$, it suffices to find a multiplier $\overline{Z}_{t}$ such that

$$ $\displaystyle z_{t,i_{t}}(\overline{Z}_{t})$ $\displaystyle\geq\frac{x_{t,i_{t}}}{2},$ (13) $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})$ $\displaystyle\leq 1.$ (14) $$

With the above two conditions hold, we can conclude that $\widetilde{Z}_{t}\geq\overline{Z}_{t}$, i.e., $\overline{Z}_{t}$ is a lower-bound for the actual multiplier $\widetilde{Z}_{t}$ making $z_{t}\in\Delta$, and thus $z_{t,i_{t}}=z_{t,i_{t}}(\widetilde{Z}_{t})\geq z_{t,i_{t}}(\overline{Z}_{t})
\geq\frac{x_{t,i_{t}}}{2}$.

For our purpose, we will choose $\overline{Z}_{t}$ as follows

$$ $\displaystyle\overline{Z}_{t}=\begin{cases}Z_{t}&\text{if }x_{t,i_{t}}<\frac{1 }{2},\\ \text{the unique solution to }z_{t,i_{t}}(\lambda)=\frac{x_{t,i_{t}}}{2}&\text {if }x_{t,i_{t}}\geq\frac{1}{2}.\end{cases}$ $$

We will verify Equation 13 and Equation 14 for both cases. For the condition Equation 13, when $x_{t,i_{t}}\geq\frac{1}{2}$, it automatically holds by definition of $\overline{Z}_{t}$. When $x_{t,i_{t}}<\frac{1}{2}$, we have $S_{t}=4C_{t,i_{t}}\cdot(1-x_{t,i_{t}})\geq 2\ell^{\text{skip}}_{t,i_{t}}$. Therefore,

$$ $\displaystyle\frac{S_{t}}{L_{t,i_{t}}-\overline{Z}_{t}}$ $\displaystyle=\frac{S_{t}}{L_{t-1,i_{t}}+\frac{\ell^{\text{skip}}_{t,i_{t}}}{x _{t,i_{t}}}-Z_{t}}$ $\displaystyle\geq\frac{S_{t}}{L_{t-1,i_{t}}+\frac{S_{t}}{2x_{t,i_{t}}}-Z_{t}}$ $\displaystyle=\frac{S_{t}}{(L_{t-1,i_{t}}-Z_{t})\cdot(1+\frac{S_{t}}{2x_{t,i_{ t}}(L_{t-1,i_{t}}-Z_{t})})}$ $\displaystyle=x_{t,i_{t}}\cdot\left({1+\frac{1}{2x_{t,i_{t}}}\cdot x_{t,i_{t}} }\right)^{-1}$ $\displaystyle=\frac{2}{3}x_{t,i_{t}}$ $\displaystyle\geq\frac{1}{2}x_{t,i_{t}}.$ $$

Thus, we have $\frac{S_{t}}{L_{t,i_{t}}-\overline{Z}_{t}}\geq\frac{x_{t,i_{t}}}{2}$ holds regardless $x_{t,i_{t}}\geq 1/2$ or not.

Then, we verify the other statement Equation 14. When $x_{t,i_{t}}<\frac{1}{2}$, we have

$$ $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})$ $\displaystyle=z_{t,i_{t}}(Z_{t})+\sum_{i\neq i_{t}}z_{t,i}(Z_{t})$ $\displaystyle=z_{t,i_{t}}(Z_{t})+\sum_{i\neq i_{t}}x_{t,i}$ $\displaystyle<x_{t,i_{t}}+\sum_{i\neq i_{t}}x_{t,i}=1.$ $$

For the other case $x_{t,i_{t}}\geq\frac{1}{2}$. It turns out that the definition of $\overline{Z}_{t}$, i.e., $z_{t,i_{t}}(\overline{Z}_{t})=\frac{x_{t,i_{t}}}{2}$, solves to

$$ $\displaystyle\overline{Z}_{t}$ $\displaystyle=-\frac{2S_{t}}{x_{t,i_{t}}}+L_{t-1,i_{t}}+\frac{\ell^{\text{skip }}_{t,i_{t}}}{x_{t,i_{t}}}$ $\displaystyle\leq Z_{t}-\frac{S_{t}}{x_{t,i_{t}}}+\frac{C_{t,i_{t}}}{x_{t,i_{t }}}$ $\displaystyle\leq Z_{t}-\frac{S_{t}}{x_{t,i_{t}}}+\frac{S_{t}}{4x^{2}_{t,i_{t} }(1-x_{t,i_{t}})}$ $\displaystyle=Z_{t}+\frac{S_{t}(1-4x_{t,i_{t}}(1-x_{t,i_{t}}))}{4x^{2}_{t,i_{t }}(1-x_{t,i_{t}})}$ $\displaystyle=Z_{t}+\frac{S_{t}(2x_{t,i_{t}}-1)^{2}}{4x^{2}_{t,i_{t}}(1-x_{t,i _{t}})}$ $$

where the first inequality holds by the definition of $x_{t,i_{t}}$ in Equation 12 and $0<\ell^{\text{skip}}_{t,i_{t}}\leq C_{t,i_{t}}=\frac{S_{t}}{4(1-x_{t,i_{t}})}
\leq\frac{S_{t}}{4x_{t,i_{t}}(1-x_{t,i_{t}})}$. For all $i\neq i_{t}$, we then have

$$ $\displaystyle\frac{S_{t}}{L_{t,i}-\overline{Z}_{t}}$ $\displaystyle=\frac{S_{t}}{L_{t-1,i}-\overline{Z}_{t}}$ $\displaystyle\leq\frac{S_{t}}{L_{t-1,i}-Z_{t}-\frac{S_{t}(2x_{t,i_{t}}-1)^{2}} {4x^{2}_{t,i_{t}}(1-x_{t,i_{t}})}}$ $\displaystyle=\frac{S_{t}}{(L_{t-1,i}-Z_{t})\cdot\left(1-\frac{S_{t}(2x_{t,i_{ t}}-1)^{2}}{(L_{t-1,i}-Z_{t})4x^{2}_{t,i_{t}}(1-x_{t,i_{t}})}\right)}$ $\displaystyle=x_{t,i}\cdot\left(1-x_{t,i}\frac{(2x_{t,i_{t}}-1)^{2}}{4x^{2}_{t ,i_{t}}(1-x_{t,i_{t}})}\right)^{-1}$ $$

Since we have $x_{t,i}\leq\sum_{i\neq i_{t}}x_{t,i}=1-x_{t,i_{t}}$, then

$$ $\displaystyle z_{t,i}(\overline{Z}_{t})=\frac{S_{t}}{L_{t,i}-\overline{Z}_{t}}$ $\displaystyle\leq x_{t,i}\cdot\left(1-\frac{1-4x_{t,i_{t}}+4x_{t,i_{t}}^{2}}{4 x_{t,i_{t}}^{2}}\right)^{-1}=x_{t,i}\cdot\frac{4x_{t,i_{t}}^{2}}{4x_{t,i_{t}}- 1}.$ (15) $$

Therefore, we have

$$ $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})$ $\displaystyle\overset{(a)}{\leq}\frac{1}{2}x_{t,i_{t}}+\frac{4x_{t,i_{t}}^{2}} {4x_{t,i_{t}}-1}\sum_{i\neq i_{t}}x_{t,i}$ $\displaystyle=\frac{1}{2}x_{t,i_{t}}+\frac{4x_{t,i_{t}}^{2}}{4x_{t,i_{t}}-1}(1 -x_{t,i_{t}})$ $\displaystyle\overset{(b)}{\leq}\frac{1}{2}x_{t,i_{t}}+4x_{t,i_{t}}^{2}(1-x_{t ,i_{t}})$ $\displaystyle\overset{(c)}{\leq}1,$ $$

where step $(a)$ is obtained by applying Equation 15 to $i\neq i_{t}$ and $z_{t,i_{t}}(\overline{Z}_{t})=x_{t,i_{t}}/2$; step $(b)$ is due to $x_{t,i_{t}}\geq\nicefrac{{1}}{{2}}$; step $(c)$ is due to the fact that $x\mapsto\nicefrac{{x}}{{2}}+4x^{2}(1-x)$ has a maximum value less than $1$.
Then, we have already verified Equation 14, which finishes the proof of $z_{t,i_{t}}\geq{x_{t,i_{t}}}/2$.

The right side $z_{t,i}\leq 2x_{t,i}$.
We then show that $z_{t,i}\leq 2x_{t,i}$ holds for all $i\in[K]$. The main idea is similar to what we have done in the argument for the left-side inequality, we will find some $\overline{Z}_{t}$ under which we can verify that

$$ $\displaystyle z_{t,i}(\overline{Z}_{t})$ $\displaystyle\leq 2x_{t,i}\quad\forall i\neq i_{t},$ (16) $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})$ $\displaystyle\geq 1.$ (17) $$

We can then claim that this $\overline{Z}_{t}$ is indeed an upper-bound of the actual multiplier $\widetilde{Z}_{t}$.

Let $j^{*}=\operatorname*{argmax}_{j\neq i_{t}}x_{t,j}$, we just take $\overline{Z}_{t}$ to be the unique solution to $z_{t,j^{*}}(\lambda)=2x_{t,j^{*}}$, which solves to

$$ $\displaystyle\overline{Z}_{t}=Z_{t}+\frac{S_{t}}{2x_{t,j^{*}}}.$ $$

One can verify that

$$ $\displaystyle z_{t,j^{*}}(\overline{Z}_{t})$ $\displaystyle=\frac{S_{t}}{(L_{t-1,j^{*}}-Z_{t})\cdot\left(1-\frac{S_{t}}{(L_{ t-1,j^{*}}-Z_{t})\cdot 2x_{t,j^{*}}}\right)}$ $\displaystyle=x_{t,j^{*}}\left(1-\frac{x_{t,j^{*}}}{2x_{t,j^{*}}}\right)^{-1}$ $\displaystyle=2x_{t,j^{*}}.$ $$

For $i\in[K]\setminus\{i_{t},j^{*}\}$, it is easy to see that

$$ $\displaystyle z_{t,i}(\overline{Z}_{t})$ $\displaystyle=\frac{S_{t}}{L_{t-1,i}-Z_{t}-\frac{S_{t}}{2x_{t,j^{*}}}}$ $\displaystyle=\frac{S_{t}}{(L_{t-1,i}-Z_{t})\cdot\left(1-\frac{S_{t}}{2x_{t,j^ {*}}(L_{t-1,i}-Z_{t})}\right)}$ $\displaystyle=x_{t,i}\left(1-\frac{x_{t,i}}{2x_{t,j^{*}}}\right)^{-1}$ $\displaystyle\leq 2x_{t,i}.$ $$

Hence Equation 16 holds. In order to verify Equation 17, note that

$$ $\displaystyle\widetilde{\ell}_{t,i_{t}}$ $\displaystyle\leq\frac{C_{t,i_{t}}}{x_{t,i_{t}}}\leq\frac{S_{t}}{4x_{t,i_{t}}( 1-x_{t,i_{t}})}.$ $$

When $x_{t,i_{t}}\geq 1/2$, we have

$$ $\displaystyle\widetilde{\ell}_{t,i_{t}}$ $\displaystyle\leq\frac{S_{t}}{4\cdot\frac{1}{2}\cdot\sum_{j\neq i_{t}}x_{t,j}}$ $\displaystyle\leq\frac{S_{t}}{2x_{t,j^{*}}}$ $\displaystyle=\overline{Z}_{t}-Z_{t}.$ $$

Therefore, we have

$$ $\displaystyle z_{t,i_{t}}(\overline{Z}_{t})=\frac{S_{t}}{L_{t,i_{t}}-\overline {Z}_{t}}\geq\frac{S_{t}}{L_{t-1,i_{t}}+\overline{Z}_{t}-Z_{t}-\overline{Z}_{t} }=x_{t,i_{t}}.$ $$

Therefore,

$$ $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})$ $\displaystyle=z_{t,i_{t}}(\overline{Z}_{t})+\sum_{i\neq i_{t}}z_{t,i}( \overline{Z}_{t})$ (18) $\displaystyle\geq z_{t,i_{t}}(\overline{Z}_{t})+\sum_{i\neq i_{t}}z_{t,i}(Z_{t})$ $\displaystyle\geq x_{t,i_{t}}+\sum_{i\neq i_{t}}x_{t,i}=1.$ $$

On the other hand, when $x_{t,i_{t}}<1/2$, we have

$$ $\displaystyle\widetilde{\ell}_{t,i_{t}}\leq\frac{S_{t}}{4x_{t,i_{t}}(1-x_{t,i_ {t}})}\leq\frac{S_{t}}{4x_{t,i_{t}}\cdot\frac{1}{2}}=\frac{S_{t}}{2x_{t,i_{t}}}.$ $$

If $x_{t,i_{t}}\geq x_{t,j^{*}}$, we have $\widetilde{\ell}_{t,i_{t}}\leq S_{t}/(2x_{t,j^{*}})=\overline{Z}_{t}-Z_{t}$. Then we can apply the same analysis as Equation 18. Hence the only remaining case is $x_{t,i_{t}}<1/2$ and $x_{t,i_{t}}<x_{t,j^{*}}$, where we have

$$ $\displaystyle z_{t,j^{*}}(\overline{Z}_{t})-x_{t,j^{*}}=x_{t,j^{*}}>x_{t,i_{t} }>x_{t,i_{t}}-z_{t,i_{t}}(\overline{Z}_{t}).$ (19) $$

Therefore, we have

$$ $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})-1$ $\displaystyle=\left[z_{t,j^{*}}(\overline{Z}_{t})-x_{t,j^{*}}\right]+\left[z_{ t,i_{t}}(\overline{Z}_{t})-x_{t,i_{t}}\right]+\sum_{i\neq i_{t},j^{*}}z_{t,i}( \overline{Z}_{t})-x_{t,i}$ $\displaystyle>\sum_{i\neq i_{t},j^{*}}z_{t,i}(\overline{Z}_{t})-x_{t,i}$ $\displaystyle\geq 0$ $$

hence $\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})>1$.
In all, we show that $\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})\geq 1$, and we are done.

Negative Loss.
The proof of case $\widetilde{\ell}_{t,i}<0$ is very similar. In this case, we have $z_{t,i_{t}}(Z_{t})>x_{t,i_{t}}$, which shows that $\sum_{i\in[K]}z_{t,i}(Z_{t})>1$. Therefore, we have $\widetilde{Z}_{t}<Z_{t}$, which implies $z_{t,i}<x_{t,i}$ for $i\neq i_{t}$ and $z_{t,i_{t}}>x_{t,i_{t}}$. Therefore, we only need to verify that $z_{t,i_{t}}\leq 2x_{t,i_{t}}$ and $z_{t,i}\geq\frac{1}{2}x_{t,i}$ for $i\neq i_{t}$. We apply similar proof process as above statement.

For the first inequality, we just need to verify that there exists a multiplier $\overline{Z}_{t}$ such that

$$ $\displaystyle z_{t,i_{t}}(\overline{Z}_{t})$ $\displaystyle\leq 2x_{t,i_{t}},$ (20) $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})$ $\displaystyle\geq 1.$ (21) $$

We set $\overline{Z}_{t}$ as the unique solution to $z_{t,i_{t}}(\lambda)=2x_{t,i_{t}}$. Then we have

$$ $\displaystyle\overline{Z}_{t}$ $\displaystyle=-\frac{S_{t}}{2x_{t,i_{t}}}+L_{t-1,i_{t}}+\widetilde{\ell}_{t,i_ {t}}$ $\displaystyle=-\frac{S_{t}}{x_{t,i_{t}}}+\frac{S_{t}}{2x_{t,i_{t}}}+L_{t-1,i_{ t}}+\frac{\ell^{\text{skip}}_{t,i_{t}}}{x_{t,i_{t}}}$ $\displaystyle\geq Z_{t}+\frac{S_{t}}{2x_{t,i_{t}}}-\frac{C_{t,i_{t}}}{x_{t,i_{ t}}}$ $\displaystyle=Z_{t}+\frac{S_{t}}{2x_{t,i_{t}}}-\frac{S_{t}}{4x_{t,i_{t}}(1-x_{ t,i_{t}})}$ $\displaystyle=Z_{t}-\frac{S_{t}(2x_{t,i_{t}}-1)}{4x_{t,i_{t}}(1-x_{t,i_{t}})}$ $$

If $x_{t,i_{t}}\leq 1/2$, we have $\overline{Z}_{t}\geq Z_{t}$. Therefore,

$$ $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})\geq z_{t,i_{t}}(\overline {Z}_{t})+\sum_{i\neq i_{t}}z_{t,i}(Z_{t})=2x_{t,i_{t}}+\sum_{i\neq i_{t}}x_{t, i}\geq 1.$ $$

For the other case, if $x_{t,i_{t}}>1/2$, we have for any $i\neq i_{t}$

$$ $\displaystyle z_{t,i}(\overline{Z}_{t})$ $\displaystyle\geq\frac{S_{t}}{L_{t-1,i}-Z_{t}+\frac{S_{t}(2x_{t,i_{t}}-1)}{4x_ {t,i_{t}}(1-x_{t,i_{t}})}}$ $\displaystyle=x_{t,i}\cdot\left(1+x_{t,i}\cdot\frac{2x_{t,i_{t}}-1}{4x_{t,i_{t }}(1-x_{t,i_{t}})}\right)^{-1}$ $\displaystyle\geq x_{t,i}\cdot\left(1+\frac{2x_{t,i_{t}}-1}{4x_{t,i_{t}}} \right)^{-1}$ $\displaystyle=x_{t,i}\cdot\frac{4x_{t,i_{t}}}{6x_{t,i_{t}}-1},$ $$

where the second inequality holds by $2x_{t,i_{t}}-1>0$ and $x_{t,i}\leq 1-x_{t,i_{t}}$. Therefore, we have

$$ $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})\geq 2x_{t,i_{t}}+\sum_{i \neq i_{t}}x_{t,i}\cdot\frac{4x_{t,i_{t}}}{6x_{t,i_{t}}-1}=2x_{t,i_{t}}+\frac{ 4x_{t,i_{t}}(1-x_{t,i_{t}})}{6x_{t,i_{t}}-1}\geq 1.$ $$

For the second inequality, we need to verify that there exists a multiplier $\overline{Z}_{t}$ such that

$$ $\displaystyle z_{t,i}(\overline{Z}_{t})$ $\displaystyle\geq\frac{1}{2}x_{t,i}\quad\forall i\neq i_{t},$ (22) $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})$ $\displaystyle\leq 1.$ (23) $$

Let $j^{*}=\operatorname*{argmax}_{j\neq i_{t}}x_{t,j}$. Then we set $\overline{Z}_{t}$ as

$$ $\displaystyle\overline{Z}_{t}=Z_{t}-\frac{S_{t}}{x_{t,j^{*}}}.$ $$

Hence, we have for any $i\neq i_{t}$,

$$ $\displaystyle z_{t,i}\left(\overline{Z}_{t}\right)$ $\displaystyle=\frac{S_{t}}{(L_{t-1,i}-Z_{t})\cdot\left(1+\frac{S_{t}}{(L_{t-1, i}-Z_{t})x_{t,j^{*}}}\right)}$ $\displaystyle=x_{t,i}\cdot\left(1+\frac{x_{t,i}}{x_{t,j^{*}}}\right)^{-1}$ $\displaystyle\geq x_{t,i}\cdot\frac{1}{2},$ $$

where the inequality holds by $x_{t,j^{*}}>x_{t,i}$. Therefore, we have

$$ $z_{t,i}(\overline{Z}_{t})\geq\frac{1}{2}x_{t,i}.$ $$

Then we verity Equation 23. Since we have $\overline{Z}_{t}\leq Z_{t}$, then $z_{t,i}(\overline{Z}_{t})\leq x_{t,i}$ for any $i\neq i_{t}$. Thus we only need to prove $z_{t,i_{t}}(\overline{Z}_{t})\leq x_{t,i_{t}}$. Notice that

$$ $\displaystyle z_{t,i_{t}}(\overline{Z}_{t})=\frac{S_{t}}{L_{t-1,i_{t}}-Z_{t}+ \widetilde{\ell}_{t,i_{t}}+\frac{S_{t}}{x_{t,j^{*}}}}\leq\frac{S_{t}}{L_{t-1,i _{t}}-Z_{t}+\frac{S_{t}}{x_{t,j^{*}}}-\frac{S_{t}}{4x_{t,i_{t}}(1-x_{t,i_{t}}) }},$ $$

where the inequality is due to $\widetilde{\ell}_{t,i_{t}}=\ell^{\text{skip}}_{t,i_{t}}/x_{t,i_{t}}\geq-C_{t,i
_{t}}/x_{t,i_{t}}$ and the definition of $C_{t,i_{t}}$ in Equation 3. If we have $x_{t,i_{t}}\geq 1/2$, then

$$ $\displaystyle\frac{S_{t}}{x_{t,j^{*}}}-\frac{S_{t}}{4x_{t,i_{t}}(1-x_{t,i_{t}})}$ $\displaystyle\geq\frac{S_{t}}{x_{t,j^{*}}}-\frac{S_{t}}{2(1-x_{t,i_{t}})}$ $\displaystyle=\frac{S_{t}}{x_{t,j^{*}}}-\frac{S_{t}}{2\sum_{j\neq i_{t}}x_{t,j}}$ $\displaystyle\geq\frac{S_{t}}{x_{t,j^{*}}}-\frac{S_{t}}{2x_{t,j^{*}}}$ $\displaystyle\geq 0.$ $$

Therefore, we have $z_{t,i_{t}}(\overline{Z}_{t})\leq x_{t,i_{t}}$, which implies that $\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})\leq\sum_{i\in[K]}x_{t,i}=1$. For the case when $x_{t,i_{t}}<1/2$, we also have

$$ $\displaystyle\frac{S_{t}}{x_{t,j^{*}}}-\frac{S_{t}}{4x_{t,i_{t}}(1-x_{t,i_{t}})}$ $\displaystyle\geq\frac{S_{t}}{x_{t,j^{*}}}-\frac{S_{t}}{2x_{t,i_{t}}}.$ $$

If $x_{t,j^{*}}\leq 2x_{t,i_{t}}$, we still have $z_{t,i_{t}}(\overline{Z}_{t})\leq x_{t,i_{t}}$. Otherwise, for $x_{t,j^{*}}>2x_{t,i_{t}}$, we can write

$$ $\displaystyle z_{t,i_{t}}(\overline{Z}_{t})$ $\displaystyle=\frac{S_{t}}{L_{t-1,i_{t}}-Z_{t}+\widetilde{\ell}_{t,i_{t}}+ \frac{S_{t}}{x_{t,j^{*}}}}$ $\displaystyle\leq\frac{S_{t}}{L_{t-1,i_{t}}-Z_{t}+\frac{S_{t}}{x_{t,j^{*}}}- \frac{S_{t}}{4x_{t,i_{t}}(1-x_{t,i_{t}})}}$ $\displaystyle=x_{t,i_{t}}\cdot\left(1+\frac{x_{t,i_{t}}}{x_{t,j^{*}}}-\frac{1} {4(1-x_{t,i_{t}})}\right)^{-1}$ $$

Notice that here $x_{t,i_{t}}\in[0,1/2]$, which implies that $1+\frac{x_{t,i_{t}}}{x_{t,j^{*}}}-\frac{1}{4(1-x_{t,i_{t}})}\geq 1/2$. Therefore, we have

$$ $\displaystyle z_{t,i_{t}}(\overline{Z}_{t})\leq 2x_{t,i_{t}}\leq\frac{1}{2}x_{ t,j^{*}}+x_{t,i_{t}}.$ $$

Since $z_{t,j^{*}}(\overline{Z}_{t})=\frac{1}{2}x_{t,j^{*}}$, we have

$$ $\displaystyle\sum_{i\in[K]}z_{t,i}(\overline{Z}_{t})\leq\sum_{i\in[K]\setminus \{i_{t},j^{*}\}}x_{t,i}+\frac{1}{2}x_{t,j^{*}}+\frac{1}{2}x_{t,j^{*}}+x_{t,i_{ t}}=1.$ $$

In all, we conclude Equation 23 and prove this lemma.
∎

###### Lemma 15 (Restatement of Lemma 4 ) .

###### Proof.

### A.2 Calculating w t , i subscript 𝑤 𝑡 𝑖 w_{t,i} italic_w start_POSTSUBSCRIPT italic_t , italic_i end_POSTSUBSCRIPT via Partial Derivatives

By inspecting the partial derivatives of the multiplier $\widetilde{Z}_{t}$ with respect to the feedback vector $\widetilde{\bm{\ell}}_{t}$, we can derive the following lemmas on $w_{t,i}$.

###### Lemma 16 .

We have

$$ $\displaystyle w_{t,i}=\widetilde{\ell}_{t,i_{t}}\cdot\frac{x_{t,i}}{S_{t}} \cdot\left(\mathbbm{1}[i=i_{t}]-\frac{{\zeta_{t,i_{t}}^{2}}}{\sum_{k\in[K]}{ \zeta_{t,k}^{2}}}\right),$ $$

where

$$ $\displaystyle\zeta_{t}:=\operatorname*{argmin}_{{\bm{z}}\in\Delta}\langle{\bm{ L}}_{t-1}+\lambda\widetilde{\ell}_{t},{\bm{z}}\rangle+\Psi_{t}({\bm{z}}).$ $$

Here $\lambda$ is some constant ranged from $(0,1)$, implicitly determined by $\widetilde{\ell}_{t}$.

###### Proof.

Notice that conditioning on the time step before $t-1$, $z_{t,i}$ only depends on $\widetilde{\ell}_{t,i}$. Then we denote

$$ $\displaystyle\widetilde{Z}^{\prime}_{t,i}(\theta):=\left.\frac{\partial \widetilde{Z}_{t}}{\partial\widetilde{\ell}_{t,i}}\right|_{\widetilde{{\bm{ \ell}}}_{t}=\theta{\bm{e}}_{i}},$ $$

where ${\bm{e}}_{i}$ is the unit vector supported at the $i$-th coordinate, and $\theta$ is a scalar.

Notice that

$$ $\displaystyle\sum_{j\in[K]}z_{t,j}=\sum_{j\in[K]}\frac{S_{t}}{L_{t,j}- \widetilde{Z}_{t}}=1,$ (24) $$

Then partially derivate $\widetilde{\ell}_{t,i}$ on both sides of Equation 24, we get

$$ $\displaystyle\sum_{j\in[K]}-\frac{S_{t}}{(\ell_{t,j}-\widetilde{Z}_{t})^{2}} \cdot(\mathbbm{1}[j=i]-\widetilde{Z}^{\prime}_{t,i})=-\frac{z_{t,i}^{2}}{S_{t} }+\widetilde{Z}_{t,i}^{\text{skip}}\sum_{j\in[K]}\frac{z_{t,j}^{2}}{S_{t}}=0,$ $$

which solves to

$$ $\displaystyle\widetilde{Z}^{\prime}_{t,i}=\frac{z_{t,i}^{2}}{\sum_{j\in[K]}{z_ {t,j}^{2}}}.$ $$

Similarly, we denote

$$ $\displaystyle z^{\prime}_{t,ij}(\theta):=\left.\frac{\partial z_{t,i}}{ \partial\widetilde{\ell}_{t,j}}\right|_{\widetilde{\bm{\ell}}_{t}=\theta{\bm{e }}_{j}}$ $$

Then according to the chain rule, we have

$$ $\displaystyle z^{\prime}_{t,ij}=\frac{z_{t,i}^{2}}{S_{t}}\cdot\left(z_{t,j}^{2 }/\left(\sum_{k\in[K]}{x_{t,k}^{2}}\right)-\mathbbm{1}[i=j]\right).$ $$

We denote

$$ $\displaystyle w^{\prime}_{t,ij}(\theta)$ $\displaystyle:=\left.\frac{\partial w_{t,i}}{\partial\widetilde{\ell}_{t,j}} \right|_{\widetilde{\bm{\ell}}_{t}=\theta{\bm{e}}_{j}}.$ $$

Recall that $w_{t,i}=\frac{x_{t,i}}{S_{t}}(\widetilde{\ell}_{t,i}-(\widetilde{Z}_{t}-Z_{t}))$, hence

$$ $\displaystyle w^{\prime}_{t,ij}$ $\displaystyle=\frac{x_{t,i}}{S_{t}}\cdot\left(\mathbbm{1}[i=j]-\left(\frac{z_{ t,j}^{2}}{S_{t}}\right)/\left(\sum_{k\in[K]}\frac{z_{t,k}^{2}}{S_{t}}\right)\right)$ $\displaystyle=\frac{x_{t,i}}{S_{t}}\cdot\left(\mathbbm{1}[i=j]-\left({z_{t,j}^ {2}}\right)/\left(\sum_{k\in[K]}{z_{t,k}^{2}}\right)\right).$ $$

Thus according to the intermediate value theorem, we have

$$ $\displaystyle w_{t,i}=\widetilde{\ell}_{t,i_{t}}\cdot\frac{x_{t,i}}{S_{t}} \cdot\left(\mathbbm{1}[i=i_{t}]-\frac{{\zeta_{t,i_{t}}^{2}}}{\sum_{k\in[K]}{ \zeta_{t,k}^{2}}}\right),$ $$

where

$$ $\displaystyle\zeta_{t}:=\operatorname*{argmin}_{{\bm{z}}\in\Delta^{[K]}} \langle{\bm{L}}_{t-1}+\lambda\widetilde{\ell}_{t},{\bm{z}}\rangle+\Psi_{t}({ \bm{z}}),$ $$

and $\lambda$ is some constant ranged from $(0,1)$, implicitly determined by $\widetilde{\ell}_{t}$. Furthermore, Lemma 4 guarantees that

$$ $\displaystyle x_{t,i}/2\leq\zeta_{t,i}\leq 2x_{t,i}\quad\forall i\in[K].$ (25) $$

∎

###### Lemma 16 .

###### Proof.

### A.3 Bregman Divergence before Expectation: Proof of Lemma 5

###### Lemma 17 (Formal version of Lemma 5 ) .

We have

$$ $\textsc{Div}_{t}\leq 2048\cdot S_{t}^{-1}(\ell^{\text{skip}}_{t,i_{t}})^{2}(1- x_{t,i_{t}})^{2}.$ $$

Therefore, the expectation of the Bregman Divergence term $\textsc{Div}_{t}$ can be bounded by

$$ $\displaystyle\mathbb{E}[\textsc{Div}_{t}\mid{\mathcal{F}}_{t-1}]\leq 2048\sum_ {i\in[K]}S_{t}^{-1}\mathbb{E}[(\ell^{\text{skip}}_{t,i})^{2}\mid{\mathcal{F}}_ {t-1}]x_{t,i}(1-x_{t,i})^{2}.$ $$

Moreover, for any ${\mathcal{T}}\in[T]$, we can bound the sum of Bregman divergence term by

$$ $\displaystyle\sum_{t=1}^{\mathcal{T}}\textsc{Div}_{t}$ $\displaystyle\leq 4096\cdot S_{{\mathcal{T}}+1}K\log T.$ $$

###### Proof.

Recall the definition of $w_{t,i}$, we have

$$ $\displaystyle\textsc{Div}_{t}$ $\displaystyle=\sum_{i\in[K]}S_{t}(w_{t,i}-\log(1+w_{t,i}))$ $$

By Lemma 4, we have $w_{t,i}=x_{t,i}/z_{t,i}-1\in[-1/2,1/2]$. Therefore, since $x-\log(1+x)\leq x^{2}$, we have

$$ $\displaystyle\textsc{Div}_{t}\leq\sum_{i\in[K]}S_{t}\cdot\left(\mathbbm{1}[i=i _{t}]w_{t,i}^{2}+\mathbbm{1}[i\neq i_{t}]w_{t,i}^{2}\right).$ (26) $$

By Lemma 16, we have

$$ $\displaystyle w_{t,i}=\widetilde{\ell}_{t,i_{t}}\cdot\frac{x_{t,i}}{S_{t}} \cdot\left(\mathbbm{1}[i=i_{t}]-\frac{{\zeta_{t,i_{t}}^{2}}}{\sum_{k\in[K]}{ \zeta_{t,k}^{2}}}\right),$ $$

and $\zeta_{t,i}$ satisfying $x_{t,i}/2\leq\zeta_{t,i}\leq 2x_{t,i}$ by Equation 25.
Then, for $i\neq i_{t}$, we have

$$ $\displaystyle w_{t,i}$ $\displaystyle=-\ell^{\text{skip}}_{t,i_{t}}\cdot\frac{x_{t,i}}{S_{t}}\cdot \frac{\zeta_{t,i_{t}}}{\sum_{k\in[K]}{\zeta_{t,k}^{2}}},$ $\displaystyle w_{t,i}^{2}$ $\displaystyle=(\ell_{t,i_{t}}^{\text{skip}})^{2}\cdot\frac{x_{t,i}^{2}}{S_{t}^ {2}}\cdot\frac{\zeta_{t,i_{t}}^{2}}{\left(\sum_{k\in[K]}{\zeta_{t,k}^{2}} \right)^{2}}\leq 16\cdot(\ell_{t,i_{t}}^{\text{skip}})^{2}\cdot\frac{x_{t,i}^{ 2}}{S_{t}^{2}}\cdot\frac{x_{t,i_{t}}^{2}}{\left(\sum_{k\in[K]}{x_{t,k}^{2}} \right)^{2}}.$ $$

And for $i=i_{t}$,

$$ $\displaystyle w_{t,i_{t}}$ $\displaystyle=\ell^{\text{skip}}_{t,i_{t}}\cdot\frac{1}{S_{t}}\cdot\frac{\sum_ {j\neq i_{t}}\zeta_{t,j}^{2}}{\sum_{k\in[K]}{\zeta_{t,k}^{2}}},$ $\displaystyle w_{t,i_{t}}^{2}$ $\displaystyle=(\ell_{t,i_{t}}^{\text{skip}})^{2}\cdot\frac{1}{S_{t}^{2}}\cdot \frac{\left(\sum_{j\neq i_{t}}{\zeta_{t,j}^{2}}\right)^{2}}{\left(\sum_{k\in[K ]}{\zeta_{t,k}^{2}}\right)^{2}}\leq 256\cdot(\ell_{t,i_{t}}^{\text{skip}})^{2} \cdot\frac{1}{S_{t}^{2}}\cdot\frac{\left(\sum_{j\neq i_{t}}{x_{t,j}^{2}}\right )^{2}}{\left(\sum_{k\in[K]}{x_{t,k}^{2}}\right)^{2}}.$ $$

Therefore, we have

$$ $\displaystyle\sum_{i\in[K]}S_{t}\cdot\left(\mathbbm{1}[i=i_{t}]w_{t,i}^{2}+ \mathbbm{1}[i\neq i_{t}]w_{t,i}^{2}\right)$ (27) $\displaystyle\leq 256\cdot(\ell_{t,i_{t}}^{{\text{skip}}})^{2}\cdot S_{t}^{-1} \cdot\left(\frac{\left(\sum_{j\neq i_{t}}{x_{t,j}^{2}}\right)^{2}}{\left(\sum_ {k\in[K]}{x_{t,k}^{2}}\right)^{2}}+\sum_{i\neq i_{t}}\frac{x_{t,i}^{2}\cdot x_ {t,i_{t}}^{2}}{\left(\sum_{k\in[K]}{x_{t,k}^{2}}\right)^{2}}\right)$ $$

Notice that

$$ $\displaystyle\frac{\left(\sum_{j\neq i_{t}}{x_{t,j}^{2}}\right)^{2}}{\left( \sum_{k\in[K]}{x_{t,k}^{2}}\right)^{2}}+\sum_{i\neq i_{t}}\frac{x_{t,i}^{2} \cdot x_{t,i_{t}}^{2}}{\left(\sum_{k\in[K]}{x_{t,k}^{2}}\right)^{2}}=\left(1- \frac{x_{t,i_{t}}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\right)^{2}+\frac{\sum_{i\neq i _{t}}x_{t,i}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\cdot\frac{x_{t,i_{t}}^{2}}{\sum_{ k\in[K]}x_{t,k}^{2}}.$ $$

For $x_{t,i_{t}}\leq 1/2$, we have $4(1-x_{t,i_{t}})^{2}\geq 1$. Then we have

$$ $\displaystyle\left(1-\frac{x_{t,i_{t}}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\right)^ {2}+\frac{\sum_{i\neq i_{t}}x_{t,i}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\cdot\frac{ x_{t,i_{t}}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\leq 1+1\cdot 1\leq 8(1-x_{t,i_{t}} )^{2}.$ (28) $$

For $x_{t,i_{t}}\geq 1/2$, we denote

$$ $\displaystyle\widetilde{x}_{t,i}:=\frac{x^{2}_{t,i}}{\sum_{k\in[K]}x^{2}_{t,k} },\quad\forall i\in[K],$ $$

which satisfies $\widetilde{x}_{t,i}\leq x_{t,i}^{2}/x_{t,i_{t}}^{2}\leq 4x_{t,i}^{2}$ for every $i\in[K]$. Since $x_{t,i_{t}}\geq 1/2$, we also have $1/2\leq x_{t,i_{t}}\leq\widetilde{x}_{t,i_{t}}\leq 1$. Therefore,

$$ $\displaystyle\left(1-\frac{x_{t,i_{t}}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\right)^ {2}+\frac{\sum_{i\neq i_{t}}x_{t,i}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\cdot\frac{ x_{t,i_{t}}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}$ $\displaystyle=(1-\widetilde{x}_{t,i_{t}})^{2}+\widetilde{x}_{t,i_{t}}\sum_{i \neq i_{t}}\widetilde{x}_{t,i}$ (29) $\displaystyle\leq(1-x_{t,i_{t}})^{2}+\sum_{i\neq i_{t}}4x_{t,i}^{2}$ $\displaystyle\leq(1-x_{t,i_{t}})^{2}+4\left(\sum_{i\neq i_{t}}x_{t,i}\right)^{2}$ $\displaystyle\leq 5(1-x_{t,i_{t}})^{2}$ $$

Combine these cases, we get

$$ $\displaystyle\textsc{Div}_{t}$ $\displaystyle\leq\sum_{i\in[K]}S_{t}\cdot\left(\mathbbm{1}[i=i_{t}]w_{t,i}^{2} +\mathbbm{1}[i\neq i_{t}]w_{t,i}^{2}\right)$ $\displaystyle\leq 256\cdot(\ell_{t,i_{t}}^{{\text{skip}}})^{2}\cdot S_{t}^{-1} \cdot\left(\left(1-\frac{x_{t,i_{t}}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\right)^{2 }+\frac{\sum_{i\neq i_{t}}x_{t,i}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\cdot\frac{x_ {t,i_{t}}^{2}}{\sum_{k\in[K]}x_{t,k}^{2}}\right)$ $\displaystyle\leq 2048\cdot(\ell_{t,i_{t}}^{{\text{skip}}})^{2}\cdot S_{t}^{-1 }\cdot(1-x_{t,i_{t}})^{2},$ $$

where the first inequality is due to Equation 26, the second inequality is due to Equation 27, and the last inequality is due to Equation 28 for $x_{t,i_{t}}\leq 1/2$ and Equation 29 for $x_{t,i_{t}}\geq 1/2$.

Moreover, taking expectation conditioning on ${\mathcal{F}}_{t-1}$, we directly imply

$$ $\displaystyle\mathbb{E}[\textsc{Div}_{t}\mid{\mathcal{F}}_{t-1}]\leq 2048\sum_ {i\in[K]}S_{t}^{-1}\mathbb{E}[(\ell^{\text{skip}}_{t,i})^{2}\mid{\mathcal{F}}_ {t-1}]x_{t,i}(1-x_{t,i})^{2}.$ $$

Consider the sum of $\textsc{Div}_{t}$, we can write

$$ $\displaystyle\sum_{t=1}^{\mathcal{T}}\textsc{Div}_{t}\leq 2048\sum_{t=1}^{ \mathcal{T}}S_{t}^{-1}\cdot(\ell^{\text{skip}}_{t,i_{t}})^{2}\cdot(1-x_{t,i_{t }})^{2}.$ $$

Notice that by definition of $S_{t+1}$ in Equation 4, we have

$$ $\displaystyle(K\log T)\cdot(S_{t+1}^{2}-S_{t}^{2})=\left(\ell^{\text{clip}}_{t ,i_{t}}\right)^{2}\cdot(1-x_{t,i_{t}})^{2}.$ $$

Moreover, since $|\ell^{\text{clip}}_{t,i_{t}}|$ is controlled by $C_{t,i_{t}}$, we have

$$ $\displaystyle S_{t+1}^{2}\leq S_{t}^{2}+C_{t,i_{t}}^{2}(1-x_{t,i_{t}})^{2} \cdot(K\log T)^{-1}=S_{t}^{2}\left(1+(4K\log T)^{-1}\right)\leq 2S_{t}^{2},$ (30) $$

where the first inequlity is due to $|\ell^{\text{clip}}_{t,i_{t}}|\leq C_{t,i_{t}}$ and the definition of $C_{t,i_{t}}$ in Equation 3, and the second inequlity holds by $T\geq 2$.
Therefore, as $\lvert\ell_{t,i_{t}}^{\text{skip}}\rvert\leq\lvert\ell_{t,i_{t}}^{\text{clip}}\rvert$ trivially, we have

$$ $\displaystyle\sum_{t=1}^{\mathcal{T}}\textsc{Div}_{t}$ $\displaystyle\leq 2048\sum_{t=1}^{T}S_{t}^{-1}\cdot(\ell^{\text{clip}}_{t,i_{t }})^{2}\left(1-{x}_{t,i_{t}}\right)^{2}$ $\displaystyle\leq 2048\cdot K\log T\sum_{t=1}^{\mathcal{T}}\frac{S_{t+1}^{2}-S _{t}^{2}}{S_{t}}$ $\displaystyle=2048\cdot K\log T\sum_{t=1}^{\mathcal{T}}\frac{(S_{t+1}+S_{t})(S _{t+1}-S_{t})}{S_{t}}$ $\displaystyle\leq 2048(1+\sqrt{2})K\log T\sum_{t=1}^{\mathcal{T}}S_{t+1}-S_{t}$ $\displaystyle=4096\cdot S_{{\mathcal{T}}+1}K\log T,$ $$

where the first ineuqality is by Lemma 5 and $|\ell_{t,i_{t}}^{\text{skip}}|\leq|\ell_{t,i_{t}}^{\text{clip}}|$, the second inequality is due to the definition of $S_{t+1}$ in Equation 4 and $|\ell_{t,i_{t}}^{\text{skip}}|\leq|\ell_{t,i_{t}}^{\text{clip}}|$, and the last inequality is due to the $S_{t+1}\leq\sqrt{2}S_{t}$ by Equation 30.
∎

###### Lemma 17 (Formal version of Lemma 5 ) .

###### Proof.

### A.4 Bounding the Expectation of Learning Rate S T + 1 subscript 𝑆 𝑇 1 S_{T+1} italic_S start_POSTSUBSCRIPT italic_T + 1 end_POSTSUBSCRIPT : Proof of Lemma 6

Recall the definition of $S_{t}$ in Equation 31, we have

$$ $\displaystyle S_{T+1}$ $\displaystyle=\sqrt{4+\sum_{t=1}^{T}(\ell_{t,i_{t}}^{\text{clip}})^{2}\cdot(1- x_{t,i_{t}})^{2}\cdot(K\log T)^{-1}}$ $\displaystyle\leq\sqrt{4+\sum_{t=1}^{T}(\ell_{t,i_{t}}^{\text{clip}})^{2}\cdot (K\log T)^{-1}}.$ $$

Therefore, to control $\mathbb{E}[S_{T+1}]$, it suffices to control $\mathbb{E}[S]$ where $S$ is defined as follows:

$$ $\displaystyle S:=\sqrt{4+\sum_{t=1}^{T}(\ell_{t,i_{t}}^{\text{clip}})^{2}\cdot (K\log T)^{-1}}.$ (31) $$

The formal proof of Lemma 6 which bounds $\mathbb{E}[S_{T+1}]$ is given below.

###### Lemma 18 (Restatement of Lemma 6 ) .

We have

$$ $\displaystyle\mathbb{E}[S_{T+1}]\leq 2\cdot\sigma(K\log T)^{-\frac{1}{\alpha}} T^{\frac{1}{\alpha}}.$ (32) $$

###### Proof.

By clipping operation, we have

$$ $\displaystyle|\ell^{\text{clip}}_{t,i_{t}}|\leq C_{t,i_{t}}=S_{t}\cdot\frac{1} {4(1-x_{t,i_{t}})}\leq S_{t}\leq S_{T+1}\leq S.$ $$

Therefore, we know

$$ $\displaystyle 4+\sum_{t=1}^{T}(\ell^{\text{clip}}_{t,i_{t}})^{2}\cdot(K\log T) ^{-1}\leq\frac{1}{4}\sum_{t=1}^{T}|\ell_{t,i_{t}}|^{\alpha}\cdot S^{2-\alpha} \cdot(K\log T)^{-1},$ $$

where the inequality is given by $S^{2}\geq 16$, $|\ell^{\text{clip}}_{t,i_{t}}|\leq S$ and $|\ell^{\text{clip}}_{t,i_{t}}|\leq|\ell_{t,i_{t}}|$. Hence,

$$ $\displaystyle S^{\alpha}\leq\frac{4}{3}(K\log T)^{-1}\sum_{t=1}^{T}\lvert\ell_ {t,i_{t}}\rvert^{\alpha}.$ $$

Take expectation on both sides and use the convexity of mapping $x\mapsto x^{\alpha}$. We get

$$ $\displaystyle\mathbb{E}[S]$ $\displaystyle\leq\left(\frac{4}{3}\right)^{1/\alpha}(K\log T)^{-1/\alpha}\cdot \sigma\cdot T^{1/\alpha}$ $\displaystyle\leq 2(K\log T)^{-1/\alpha}\cdot\sigma\cdot T^{1/\alpha}.$ $$

The conclusion follows from the fact that $S_{T+1}\leq S$.
∎

###### Lemma 18 (Restatement of Lemma 6 ) .

###### Proof.

### A.5 Adversarial Bounds for Bregman Divergence Terms: Proof of Theorem 7

Equipped with Lemma 6, we can verify the main result (Theorem 7) for Bregman divergence terms in adversarial case.

###### Theorem 19 (Formal version of Theorem 7 ) .

We have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]$ $\displaystyle\leq 8192\cdot\sigma K^{1-1/\alpha}T^{1/\alpha}(\log T)^{1-1/\alpha}$ $$

###### Proof.

By Lemma 17 and Lemma 6, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]$ $\displaystyle\leq 4096\cdot\mathbb{E}[S_{T+1}]\cdot K\log T$ $\displaystyle\leq 8192\cdot\sigma K^{1-1/\alpha}T^{1/\alpha}(\log T)^{1-1/ \alpha}.$ $$

Ignoring the logarithmic terms, we will get $\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]\leq\widetilde{{\mathcal{
O}}}(\sigma K^{1-1/\alpha}T^{1/\alpha})$.
∎

###### Theorem 19 (Formal version of Theorem 7 ) .

###### Proof.

### A.6 Stochastic Bounds for Bregman Divergence Terms: Proof of Theorem 8

We first calculate the expectation of a single Bregman divergence term $\mathbb{E}[\textsc{Div}_{t}\mid\mathcal{F}_{t-1}]$.

###### Lemma 20 .

Conditioning on ${\mathcal{F}}_{t-1}$, the expectation of Bregman divergence term $\textsc{Div}_{t}$ can be bounded by

$$ $\displaystyle\mathbb{E}[\textsc{Div}_{t}\mid{\mathcal{F}}_{t-1}]\leq 4096\cdot S _{t}^{1-\alpha}\sigma^{\alpha}(1-x_{t,i^{\ast}}).$ $$

###### Proof.

From Lemma 17, we have

$$ $\displaystyle\mathbb{E}[\textsc{Div}_{t}\mid{\mathcal{F}}_{t-1}]$ $\displaystyle\leq 2048\cdot S_{t}^{-1}\mathbb{E}\left[((\ell_{t,i_{t}}^{\text{ skip}})^{2}(1-x_{t,i_{t}})^{2}\mid{\mathcal{F}}_{t-1}\right]$ (33) $\displaystyle\leq 2048\cdot S_{t}^{-1}\mathbb{E}\left[(\ell^{\text{clip}}_{t,i _{t}})^{2}(1-x_{t,i_{t}})^{2}\mid{\mathcal{F}}_{t-1}\right]$ (34) $$

By definition of $C_{t,i_{t}}$ in Equation 3, we have

$$ $\displaystyle\mathbb{E}[\textsc{Div}_{t}\mid{\mathcal{F}}_{t-1}]$ $\displaystyle\leq 2048\cdot S_{t}^{-1}\mathbb{E}\left[C_{t,i_{t}}^{2-\alpha}(1 -x_{t,i_{t}})^{2-\alpha}|\ell_{t,i_{t}}|^{\alpha}(1-x_{t,i_{t}})^{\alpha}\right]$ $\displaystyle\leq 2048\cdot\frac{S_{t}^{1-\alpha}}{4^{2-\alpha}}\sigma^{\alpha }\mathbb{E}[(1-x_{t,i_{t}})^{\alpha}\mid{\mathcal{F}}_{t-1}]$ $\displaystyle\leq 2048\cdot{S_{t}^{1-\alpha}}\sigma^{\alpha}\sum_{i\in[K]}x_{t ,i}(1-x_{t,i})^{\alpha}$ $$

Notice that

$$ $\displaystyle\sum_{i\in[K]}x_{t,i}(1-x_{t,i})^{\alpha}$ $\displaystyle\leq\sum_{i\neq i^{\ast}}x_{t,i}+x_{t,i^{\ast}}(1-x_{t,i^{\ast}})$ $\displaystyle=(1-x_{t,i^{\ast}})+x_{t,i^{\ast}}(1-x_{t,i^{\ast}})$ $\displaystyle\leq 2(1-x_{t,i^{\ast}})$ $$

Therefore, we have

$$ $\displaystyle\mathbb{E}[\textsc{Div}_{t}\mid{\mathcal{F}}_{t-1}]\leq 4096\cdot S _{t}^{1-\alpha}\sigma^{\alpha}(1-x_{t,i^{\ast}}).$ $$

∎

Then we bound the sum of Bregman divergence in stochastic case by the stopping time argument.

###### Theorem 21 (Formal version of Theorem 8 ) .

In stochastic settings, the sum of Bregman divergence terms can be bounded by

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]$ $\displaystyle\leq 8192\cdot 16384^{\frac{1}{\alpha-1}}\cdot K\Delta_{\min}^{- \frac{1}{\alpha-1}}\sigma^{\frac{\alpha}{\alpha-1}}\log T+\frac{1}{4}{\mathcal {R}}_{T}.$ $$

###### Proof.

We first consider a stopping threshold $M_{1}$

$$ $\displaystyle M_{1}:=\inf\left\{s>0:4096\cdot s^{1-\alpha}\sigma^{\alpha}\leq \Delta_{\min}/4\right\}$ (35) $$

Then, define the stopping time ${\mathcal{T}}_{1}$ as

$$ $\displaystyle{\mathcal{T}}_{1}:=\inf\left\{t\geq 1:S_{t}\geq M_{1}\right\} \wedge(T+1).$ $$

Since we have $S_{t+1}\leq(1+(4K\log T)^{-1})S_{t}\leq 2S_{t}$ by Equation 30, we have $S_{{\mathcal{T}}_{1}}\leq 2M_{1}$. Then by Lemma 17, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{{\mathcal{T}}-1}\textsc{Div}_{t} \right]\leq 4096\cdot\mathbb{E}\left[S_{{\mathcal{T}}_{1}}\cdot(K\log T)\right ]\leq 8192\cdot M_{1}\cdot K\log T.$ $$

Therefore, by Lemma 20,

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]$ $\displaystyle=\mathbb{E}\left[\sum_{t=1}^{{\mathcal{T}}_{1}-1}\textsc{Div}_{t} \right]+\mathbb{E}\left[\sum_{t={\mathcal{T}}_{1}}^{T}\mathbb{E}[\textsc{Div}_ {t}\mid{\mathcal{F}}_{t-1}]\right]$ $\displaystyle\leq 8192\cdot M_{1}\cdot K\log T+\mathbb{E}\left[\sum_{t={ \mathcal{T}}_{1}}^{T}4096\cdot\mathbb{E}[\sigma^{\alpha}S_{t}^{1-\alpha}(1-x_{ t,i^{\ast}})\mid{\mathcal{F}}_{t-1}]\right]$ $\displaystyle\leq 8192\cdot M_{1}\cdot K\log T+\mathbb{E}\left[\sum_{t={ \mathcal{T}}_{1}}^{T}4096\cdot M_{1}^{1-\alpha}\sigma^{\alpha}(1-x_{t,i^{\ast} })\right],$ $$

where the last inequality is due to $S_{t}\geq M$ for $t\geq{\mathcal{T}}_{1}$ and $1-\alpha<0$. Therefore, by definition of $M_{1}$, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]$ $\displaystyle\leq 8192\cdot\frac{\Delta_{\min}^{-\frac{1}{\alpha-1}}}{(4\cdot 4 096)^{-\frac{1}{\alpha-1}}}\cdot\sigma^{\frac{\alpha}{\alpha-1}}\cdot K\log T+ \frac{\Delta_{\min}}{4}\mathbb{E}\left[\sum_{t={\mathcal{T}}_{1}}^{T}(1-x_{t,i ^{\ast}})\right]$ $\displaystyle\leq 8192\cdot 16384^{\frac{1}{\alpha-1}}\Delta_{\min}^{-\frac{1} {\alpha-1}}\cdot\sigma^{\frac{\alpha}{\alpha-1}}\cdot K\log T+\frac{1}{4}{ \mathcal{R}}_{T},$ $$

where the first inequality is due to the definition of $M_{1}$ in Equation 35 and the second inequality is due to ${\mathcal{R}}_{T}\geq\mathbb{E}[\Delta_{\min}\sum_{t=1}^{T}1-x_{t,i^{\ast}}]$ in stochastic case.
∎

###### Lemma 20 .

###### Proof.

###### Theorem 21 (Formal version of Theorem 8 ) .

###### Proof.

## Appendix B Ψ Ψ \Psi roman_Ψ -Shifting Terms: Omitted Proofs in Section 5.3

### B.1 Ψ Ψ \Psi roman_Ψ -Shifting Terms before Expectation: Proof of Lemma 9

First we give the formal version of Lemma 9.

###### Lemma 22 (Formal version of Lemma 9 ) .

We have for any $t\in[T]$,

$$ $\displaystyle\textsc{Shift}_{t}$ $\displaystyle\leq\sum_{i\in[K]}(S_{t+1}-S_{t})(-\log(\widetilde{y}_{i}))\leq \frac{1}{2}S_{t}^{-1}(\ell^{{\text{clip}}}_{t,i_{t}})^{2}(1-x_{t,i_{t}})^{2}.$ $$

Moreover, for any ${\mathcal{T}}\in[T-1]$, we have

$$ $\displaystyle\sum_{t=0}^{\mathcal{T}}\textsc{Shift}_{t}\leq S_{{\mathcal{T}}+1 }\cdot K\log T$ $$

###### Proof.

By definition of $\Psi_{t}$ in Equation 2, we have

$$ $\displaystyle\textsc{Shift}_{t}$ $\displaystyle=(\Psi_{t+1}(\widetilde{{\bm{y}}})-\Psi_{t}(\widetilde{{\bm{y}}}) )-(\Psi_{t+1}({\bm{x}}_{t+1})-\Psi_{t}({\bm{x}}_{t+1}))$ $\displaystyle\leq\sum_{i\in[K]}(S_{t+1}-S_{t})(-\log(\widetilde{y}_{i}))$ $\displaystyle\leq(K\log T)\cdot\frac{S^{2}_{t+1}-S_{t}^{2}}{S_{t+1}+S_{t}}$ $\displaystyle\leq\frac{1}{2}S_{t}^{-1}{(\ell_{t,i_{t}}^{\text{clip}})^{2}(1-x_ {t,i_{t}})^{2}},$ $$

where the first inequality is by $\Psi_{t+1}({\bm{x}})\geq\Psi_{t}({\bm{x}})$, the second inequality is due to the definition of $\widetilde{{\bm{y}}}$, and the third inequality holds by $S_{t+1}\geq S_{t}$.
Moreover, for any ${\mathcal{T}}\in[T-1]$, we also have

$$ $\displaystyle\sum_{t=0}^{\mathcal{T}}\textsc{Shift}_{t}$ $\displaystyle=\sum_{t=0}^{\mathcal{T}}(\Psi_{t+1}(\widetilde{\bm{y}})-\Psi_{t} (\widetilde{\bm{y}}))-(\Psi_{t+1}({\bm{x}}_{t})-\Psi_{t}({\bm{x}}_{t}))$ $\displaystyle\leq\sum_{t=0}^{\mathcal{T}}(S_{t+1}-S_{t})\cdot K\log T$ $\displaystyle=S_{{\mathcal{T}}+1}\cdot K\log T.$ $$

∎

###### Lemma 22 (Formal version of Lemma 9 ) .

###### Proof.

### B.2 Adversarial Bounds for Ψ Ψ \Psi roman_Ψ -Shifting Terms: Proof of Theorem 10

In adversarial case, we have already bounded the expectation of $\mathbb{E}[S_{T+1}]$ in Section A.5. Therefore, we have the following lemma.

###### Theorem 23 (Formal version of Theorem 10 ) .

The expectation of the sum of $\Psi$-shifting terms can be bounded by

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]\leq 2 \cdot\sigma K^{1-1/\alpha}T^{1/\alpha}(\log T)^{1-1/\alpha}.$ $$

###### Proof.

By Lemma 22, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]\leq \mathbb{E}[S_{T}]\cdot K\log T\leq\mathbb{E}[S_{T+1}]\cdot K\log T.$ $$

Notice that Lemma 6 gives the bound of $\mathbb{E}[S_{T+1}]$. Therefore, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]\leq 2 \cdot\sigma K^{1-1/\alpha}T^{1/\alpha}(\log T)^{1-1/\alpha}.$ $$

∎

###### Theorem 23 (Formal version of Theorem 10 ) .

###### Proof.

### B.3 Stochastic Bounds for Ψ Ψ \Psi roman_Ψ -Shifting Terms: Proof of Theorem 11

Again, we start with a single-step bound on $\textsc{Shift}_{t}$.

###### Lemma 24 .

Conditioning on ${\mathcal{F}}_{t-1}$ for any $t\in[T-1]$, we have

$$ $\displaystyle\mathbb{E}[\textsc{Shift}_{t}\mid{\mathcal{F}}_{t-1}]\leq S_{t}^{ 1-\alpha}\sigma^{\alpha}(1-x_{t,i^{\ast}})$ $$

###### Proof.

According to Lemma 22, we have

$$ $\displaystyle\mathbb{E}[\textsc{Shift}_{t}\mid{\mathcal{F}}_{t-1}]\leq\frac{1} {2}S_{t}^{-1}\mathbb{E}\left[\ell^{{\text{clip}}}_{t,i_{t}}(1-x_{t,i_{t}})^{2} \middle|{\mathcal{F}}_{t-1}\right].$ $$

By definition of $C_{t,i_{t}}$ in Equation 3, we have

$$ $\displaystyle\mathbb{E}[\textsc{Shift}_{t}\mid{\mathcal{F}}_{t-1}]$ $\displaystyle\leq\frac{1}{2}S_{t}^{-1}\cdot\mathbb{E}\left[C_{t,i_{t}}^{2- \alpha}(1-x_{t,i_{t}})^{2-\alpha}|\ell_{t,i_{t}}|^{\alpha}(1-x_{t,i_{t}})^{ \alpha}\mid{\mathcal{F}}_{t-1}\right]$ $\displaystyle\leq\frac{S_{t}^{1-\alpha}}{2\cdot 4^{2-\alpha}}\sigma^{\alpha} \mathbb{E}[(1-x_{t,i_{t}})^{\alpha}\mid{\mathcal{F}}_{t-1}]$ $\displaystyle\leq\frac{1}{2}S_{t}^{1-\alpha}\sigma^{\alpha}\sum_{i\in[K]}x_{t, i}(1-x_{t,i})^{\alpha}$ $$

By similar method used in the proof of Lemma 20, we further have

$$ $\displaystyle\sum_{i\in[K]}x_{t,i}(1-x_{t,i})^{\alpha}\leq\sum_{i\neq i^{\ast} }x_{t,i}+x_{t,i^{\ast}}(1-x_{t,i^{\ast}})\leq 2(1-x_{t,i^{\ast}}).$ $$

Therefore, we have

$$ $\displaystyle\mathbb{E}[\textsc{Shift}_{t}\mid{\mathcal{F}}_{t-1}]\leq S_{t}^{ 1-\alpha}\sigma^{\alpha}(1-x_{t,i^{\ast}})$ $$

∎

###### Theorem 25 (Formal version of Theorem 11 ) .

We can bound the sum of $\Psi$-shifting terms by the following inequality.

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]\leq 2K \sigma^{\frac{\alpha}{\alpha-1}}\Delta_{\min}^{-\frac{1}{\alpha-1}}\log T+ \frac{1}{4}{\mathcal{R}}_{T}$ $$

###### Proof.

Similar to the proof in Theorem 21, we consider a stopping threshold $M_{2}$ defined as follows

$$ $\displaystyle M_{2}:=\inf\left\{s>0:s^{1-\alpha}\sigma^{\alpha}\leq\Delta_{ \min}/4\right\}.$ $$

Then we similarly define the stopping time ${\mathcal{T}}_{2}$ as

$$ $\displaystyle{\mathcal{T}}_{2}:=\inf\left\{t\geq 1:S_{t}\geq M_{2}\right\} \wedge T.$ $$

Therefore, we have $S_{{\mathcal{T}}}\leq 2S_{{\mathcal{T}}-1}\leq 2M_{2}$. Then by Lemma 22, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{{\mathcal{T}}_{2}}\textsc{Shift}_{t} \right]\leq\mathbb{E}[S_{{\mathcal{T}}_{2}+1}]\cdot K\log T\leq 2M_{2}\cdot K\log T$ $$

Therefore, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]$ $\displaystyle=\mathbb{E}\left[\sum_{t=0}^{{\mathcal{T}}_{2}-1}\textsc{Shift}_{ t}\right]+\mathbb{E}\left[\sum_{t={\mathcal{T}}_{2}}^{T-1}\mathbb{E}[\textsc{ Shift}_{t}\mid{\mathcal{F}}_{t-1}]\right]$ $\displaystyle\leq 2M_{2}\cdot K\log T+\mathbb{E}\left[\sum_{t={\mathcal{T}}_{2 }}^{T-1}\sigma^{\alpha}\mathbb{E}[S_{t}^{1-\alpha}(1-x_{t,i^{\ast}})\mid{ \mathcal{F}}_{t-1}]\right]$ $\displaystyle\leq 2M_{2}\cdot K\log T+\mathbb{E}\left[\sum_{t={\mathcal{T}}_{2 }}^{T-1}\sigma^{\alpha}M_{2}^{1-\alpha}\mathbb{E}[(1-x_{t,i^{\ast}})\mid{ \mathcal{F}}_{t-1}]\right]$ $$

where the first inequality holds by Lemma 24 and the second inequality is due to $S_{t}\geq M_{2}$ for $t\geq{\mathcal{T}}_{2}$ and $1-\alpha<0$. Notice that ${\mathcal{R}}_{T}\geq\mathbb{E}[\sum_{t=1}^{T}\Delta_{\min}(1-x_{t,i^{\ast}})]$. We can combine the definition of $M_{2}$ and get

$$ $\displaystyle\mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]\leq 2 \cdot{\Delta_{\min}^{-\frac{1}{\alpha-1}}}\sigma^{\frac{\alpha}{\alpha-1}} \cdot K\log T+\frac{1}{4}{\mathcal{R}}_{T}$ $$

∎

###### Lemma 24 .

###### Proof.

###### Theorem 25 (Formal version of Theorem 11 ) .

###### Proof.

## Appendix C Skipping Loss Terms: Omitted Proofs in Section 5.4

### C.1 Constant Clipping Threshold Argument: Proof of Lemma 12

###### Proof of Lemma 12 .

For a given clipping threshold constant $M$, we first perform clipping operation $\operatorname{Clip}(\ell_{t,i_{t}},M)$, which gives a universal clipping error

$$ $\textsc{SkipErr}_{t}^{\text{Univ}}(M):=\begin{cases}\ell_{t,i_{t}}-M&\ell_{t,i _{t}}>M\\ 0&-M\leq\ell_{t,i_{t}}\leq M\\ \ell_{t,i_{t}}+M&\ell_{t,i_{t}}<-M\end{cases}.$ $$

If $C_{t,i_{t}}\geq M$, then this clipping is ineffective. Otherwise, we get the following action-dependent clipping error

$$ $\textsc{SkipErr}_{t}^{\text{ActDep}}(M):=\begin{cases}\textsc{SkipErr}_{t}- \textsc{SkipErr}_{t}^{\text{Univ}}&C_{t,i_{t}}<M\\ 0&C_{t,i_{t}}\geq M\end{cases}.$ $$

Therefore, we directly have $|\textsc{SkipErr}_{t}|\leq|\textsc{SkipErr}_{t}^{\text{Univ}}(M)|+|\textsc{
SkipErr}_{t}^{\text{ActDep}}(M)|$. Another important observation is that if $\textsc{SkipErr}_{t}^{\text{ActDep}}(M)\neq 0$, we have $S_{t}\leq M$, $(\ell^{{\text{clip}}}_{t,i_{t}})^{2}=C_{t,i_{t}}^{2}$, and $|\textsc{SkipErr}_{t}^{\text{ActDep}}(M)|\leq M$, which implies that

$$ $\displaystyle S_{t+1}^{2}=S_{t}^{2}+C_{t,i_{t}}^{2}\cdot(1-x_{t,i_{t}})^{2} \cdot(K\log T)^{-1}=S_{t}^{2}\left(1+(16K\log T)^{-1}\right).$ $$

Thus the number of occurrences of non-zero $\textsc{SkipErr}_{t}^{\text{ActDep}}(M)$’s is upper-bounded by $\lceil\log_{\sqrt{1+(K\log T)^{-1}/4}}M\rceil$. Then we can bound the sum of the sub-optimal skipping loss by

$$ $\displaystyle\quad\mathbb{E}\left[\sum_{t=1}^{T}|\textsc{SkipErr}_{t}|\cdot \mathbbm{1}[i_{t}\neq i^{\ast}]\right]$ $\displaystyle\leq\mathbb{E}\left[\sum_{t=1}^{T}|\textsc{SkipErr}_{t}^{\text{ Univ}}(M)|\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\right]+\mathbb{E}\left[\sum_{t= 1}^{T}|\textsc{SkipErr}_{t}^{\text{ActDep}}(M)|\right]$ $\displaystyle\leq\mathbb{E}\left[\sum_{t=1}^{T}|\ell_{t,i_{t}}|\cdot\mathbbm{1 }[|\ell_{t,i_{t}}\geq M]\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\right]+M\cdot \mathbb{E}[\log_{\sqrt{1+(16K\log T)^{-1}}}M]+M$ $\displaystyle\leq\sigma^{\alpha}M^{1-\alpha}\mathbb{E}\left[\sum_{t=1}^{T} \mathbbm{1}[i_{t}\neq i^{\ast}]\right]+2M\cdot\frac{\log M}{\log(1+(16K\log T) ^{-1})}+M.$ $$

∎

###### Proof of Lemma 12 .

### C.2 Adversarial Bounds for Skipping Losses: Proof of Theorem 13

###### Theorem 26 (Formal version of Theorem 13 ) .

By setting $M^{\text{adv}}:=\sigma(K\log T)^{-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{
\alpha}}}$, we have

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}|\textsc{SkipErr}_{t}|\cdot\mathbbm {1}[i_{t}\neq i^{\ast}]\right]$ $\displaystyle\leq\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{\alpha}\cdot\left(( \log T)^{1-\nicefrac{{1}}{{\alpha}}}+\frac{2}{\alpha}(\log T)^{2-\nicefrac{{1} }{{\alpha}}}+2\log\sigma-\frac{2}{\alpha}\log K-\frac{2}{\alpha}\log\log T\right)$ $$

###### Proof.

Notice that we have $2x\geq\log(1+x^{-1})$ holding for $x\geq 1$. Therefore,

$$ $\displaystyle\quad\mathbb{E}\left[\sum_{t=1}^{T}\lvert\textsc{SkipErr}_{t} \cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\rvert\right]$ $\displaystyle\leq\sigma^{\alpha}(M^{adv})^{1-\alpha}\mathbb{E}\left[\sum_{t=1} ^{T}\mathbbm{1}[i_{t}\neq i^{\ast}]\right]+2M^{adv}\cdot\log M^{adv}\cdot K \log T.$ $$

By the expression of $M^{adv}$, we have

$$ $\displaystyle\quad\mathbb{E}\left[\sum_{t=1}^{T}\lvert\textsc{SkipErr}_{t} \cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\rvert\right]$ $\displaystyle\leq\sigma(K\log T)^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}} {{\alpha}}}+16\cdot\sigma(K\log T)^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1 }}{{\alpha}}}\cdot\log\left(\sigma(K\log T)^{-\nicefrac{{1}}{{\alpha}}}T^{ \nicefrac{{1}}{{\alpha}}}\right)$ $\displaystyle=\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{\alpha}} }\cdot\left((\log T)^{1-\nicefrac{{1}}{{\alpha}}}+\frac{2}{\alpha}(\log T)^{2- \nicefrac{{1}}{{\alpha}}}+2\log\sigma-\frac{2}{\alpha}\log K-\frac{2}{\alpha} \log\log T\right).$ $$

∎

###### Theorem 26 (Formal version of Theorem 13 ) .

###### Proof.

### C.3 Stochastic Bounds for Skipping Losses: Proof of Theorem 14

###### Theorem 27 (Formal version of Theorem 14 ) .

By setting $M^{\text{sto}}:=4^{\frac{1}{\alpha-1}}\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{
\min}^{-\frac{1}{\alpha-1}}$, we have

$$ $\displaystyle\quad\mathbb{E}\left[\sum_{t=1}^{T}|\textsc{SkipErr}_{t}|\cdot \mathbbm{1}[i_{t}\neq i^{\ast}]\right]$ $\displaystyle\leq\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{\min}^{-\frac{1}{ \alpha-1}}\cdot K\log T\cdot\frac{4^{\frac{1}{\alpha-1}}}{\alpha-1}\left(2\log 4 +\alpha\log\sigma+\log(1/\Delta_{\min})\right)+\frac{1}{4}{\mathcal{R}}_{T}.$ $$

###### Proof.

Since we set the constant in stochastic case as $M^{\text{sto}}:=4^{\frac{1}{\alpha-1}}\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{
\min}^{-\frac{1}{\alpha-1}}$, then by $2x\geq\log(1+x^{-1}),\forall x\geq 1$, we have

$$ $\displaystyle\quad\mathbb{E}\left[\sum_{t=1}^{T}\lvert\textsc{SkipErr}_{t} \cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\rvert\right]$ $\displaystyle\leq\sigma^{\alpha}(M^{\text{sto}})^{1-\alpha}\mathbb{E}\left[ \sum_{t=1}^{T}\mathbbm{1}[i_{t}\neq i^{\ast}]\right]+2M^{\text{sto}}\cdot\log M ^{\text{sto}}\cdot K\log T$ $\displaystyle=\frac{1}{4}\Delta_{\min}\mathbb{E}\left[\sum_{t=1}^{T}\mathbbm{1 }[i_{t}\neq i^{\ast}]\right]+\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{\min}^{- \frac{1}{\alpha-1}}\cdot K\log T\cdot\frac{4^{\frac{1}{\alpha-1}}}{\alpha-1} \left(2\log 4+\alpha\log\sigma+\log(1/\Delta_{\min})\right)$ $$

Since we have

$$ $\displaystyle{\mathcal{R}}_{T}\geq\mathbb{E}\left[\sum_{t=1}^{T}\Delta_{\min} \mathbbm{1}[i_{t}\neq i^{\ast}]\right],$ $$

which shows that

$$ $\displaystyle\quad\mathbb{E}\left[\sum_{t=1}^{T}\lvert\textsc{SkipErr}_{t} \cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\rvert\right]$ $\displaystyle\leq\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{\min}^{-\frac{1}{ \alpha-1}}\cdot K\log T\cdot\frac{4^{\frac{1}{\alpha-1}}}{\alpha-1}\left(2\log 4 +\alpha\log\sigma+\log(1/\Delta_{\min})\right)+\frac{1}{4}{\mathcal{R}}_{T}.$ $$

∎

###### Theorem 27 (Formal version of Theorem 14 ) .

###### Proof.

## Appendix D Main Theorem: Proof of Theorem 3

In this section, we prove the main theorem. Here we present the formal version of our main result.

###### Theorem 28 (Formal version of Theorem 3 ) .

For Algorithm 1, under the adversarial settings, we have

$$ $\displaystyle{\mathcal{R}}_{T}$ $\displaystyle\leq\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{\alpha}\cdot\left(819 5(\log T)^{1-\nicefrac{{1}}{{\alpha}}}+\frac{2}{\alpha}(\log T)^{2-\nicefrac{{ 1}}{{\alpha}}}+2\log\sigma-\frac{2}{\alpha}\log K-\frac{2}{\alpha}\log\log T \right)+\sigma K$ $\displaystyle=\widetilde{{\mathcal{O}}}\left(\sigma K^{1-\nicefrac{{1}}{{ \alpha}}}T^{\nicefrac{{1}}{{\alpha}}}\right).$ $$

Moreover, for the stochastic settings, we have

$$ $\displaystyle{\mathcal{R}}_{T}$ $\displaystyle\leq 4\cdot K\left(\frac{\sigma^{\alpha}}{\Delta_{\min}}\right)^{ \frac{1}{\alpha-1}}\log T\cdot\left(8192\cdot 16384^{\frac{1}{\alpha-1}}+2+ \frac{4^{\frac{1}{\alpha-1}}}{\alpha-1}\left(2\log 4+\log\left(\frac{\sigma^{ \alpha}}{\Delta_{\min}}\right)\right)\right)$ $\displaystyle={\mathcal{O}}\left(K\left(\frac{\sigma^{\alpha}}{\Delta_{\min}} \right)^{\frac{1}{\alpha-1}}\log T\cdot\log\frac{\sigma^{\alpha}}{\Delta_{\min }}\right).$ $$

###### Proof.

We denote ${\bm{y}}\in\mathbb{R}^{K}$ as the one-hot vector on the optimal action $i^{\ast}\in[K]$, i.e., $y_{i}:=\mathbbm{1}[i=i^{\ast}]$. By definition of $\mathcal{R}_{T}$ in Equation 1, we have

$$ $\displaystyle{\mathcal{R}}_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\langle{\bm{x}}_{ t}-{\bm{y}},{\bm{\ell}}_{t}\rangle\right].$ $$

Consider the adjusted benchmark $\widetilde{{\bm{y}}}$ where

$$ $\widetilde{y}_{i}:=\begin{cases}\frac{1}{T}&i\neq i^{\ast}\\ 1-\frac{K-1}{T}&i=i^{\ast}\end{cases}.$ $$

By standard regret decomposition in FTRL-based MAB algorithm analyses, we have

$$ $\displaystyle{\mathcal{R}}_{T}=\underbrace{\mathbb{E}\left[\sum_{t=1}^{T} \langle\widetilde{\bm{y}}-{\bm{y}},{\bm{\ell}}^{\text{skip}}_{t}\rangle\right] }_{\textsc{Benchmark Calibration Error}}+\underbrace{\mathbb{E}\left[\sum_{t=1 }^{T}\langle{\bm{x}}_{t}-\widetilde{\bm{y}},{\bm{\ell}}^{\text{skip}}_{t} \rangle\right]}_{\textsc{Main Regret}}+\underbrace{\mathbb{E}\left[\sum_{t=1}^ {T}\langle{\bm{x}}_{t}-{\bm{y}},{\bm{\ell}}_{t}-{\bm{\ell}}^{\text{skip}}_{t} \rangle\right]}_{\textsc{Skipping Error}}.$ (36) $$

As in a typical log-barrier analysis, the Benchmark Calibration Error is not the dominant term. This is because we have, by definitions of ${\bm{y}}$ and $\widetilde{{\bm{y}}}$,

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\langle\widetilde{\bm{y}}-{\bm{y}}, {\bm{\ell}}^{\text{skip}}_{t}\rangle\right]\leq\sum_{t=1}^{T}\frac{K-1}{T} \mathbb{E}[|\ell^{\text{skip}}_{t,i_{t}}|]\leq\sum_{t=1}^{T}\frac{K-1}{T} \mathbb{E}[|\ell_{t,i_{t}}|]\leq\sigma K,$ $$

which is independent from $T$. Therefore, the key is analyzing the other two terms.

By the FTRL decomposition in Lemma 29, we have

$$ $\displaystyle\quad\textsc{Main Regret}=\mathbb{E}\left[\sum_{t=1}^{T}\langle{ \bm{x}}_{t}-\widetilde{\bm{y}},{\bm{\ell}}^{\text{skip}}_{t}\rangle\right]= \mathbb{E}\left[\sum_{t=1}^{T}\langle{\bm{x}}_{t}-\widetilde{\bm{y}}, \widetilde{{\bm{\ell}}}_{t}\rangle\right]$ $\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}[D_{\Psi_{t}}({\bm{x}}_{t},{\bm{z}}_{ t})]+\sum_{t=0}^{T-1}\mathbb{E}\left[\left(\Psi_{t+1}(\widetilde{\bm{y}})-\Psi _{t}(\widetilde{\bm{y}})\right)-\left(\Psi_{t+1}({\bm{x}}_{t+1})-\Psi_{t}({\bm {x}}_{t+1})\right)\right],$ $$

where

$$ $D_{\Psi_{t}}(\bm{y},\bm{x})=\Psi_{t}(\bm{y})-\Psi_{t}(\bm{x})-\langle\nabla \Psi_{t}(\bm{x}),\bm{y}-\bm{x}\rangle,$ $$

given the Bregman divergence induced by the $t$-th regularizer $\Psi_{t}$, and ${\bm{z}}_{t}$ denotes the posterior optimal estimation in episode $t$, namely

$$ $\displaystyle{\bm{z}}_{t}:=\operatorname*{argmin}_{{\bm{z}}\in\Delta^{[K]}} \left(\sum_{s=1}^{t}\langle\widetilde{{\bm{\ell}}}_{s},{\bm{z}}\rangle+\Psi_{t }({\bm{z}})\right).$ $$

As mentioned in Section 5, we denote $\textsc{Div}_{t}:=D_{\Psi_{t}}({\bm{x}}_{t},{\bm{z}}_{t})$ for the Bregman divergence between ${\bm{x}}_{t}$ and ${\bm{z}}_{t}$ under regularizer $\Psi_{t}$, $\textsc{Shift}_{t}:=\left[\left(\Psi_{t+1}(\widetilde{\bm{y}})-\Psi_{t}(
\widetilde{\bm{y}})\right)-\left(\Psi_{t+1}({\bm{x}}_{t+1})-\Psi_{t}({\bm{x}}_
{t+1})\right)\right]$ be the $\Psi$-shifting term, and $\textsc{SkipErr}_{t}:=\ell_{t,i_{t}}-\ell_{t,i_{t}}^{\text{skip}}=\ell_{t,i_{t
}}\mathbbm{1}[\lvert\ell_{t,i_{t}}\rvert\geq C_{t,i_{t}}]$ be the sub-optimal skipping losses. Then, we can reduce the analysis of main regret to bounding the sum of Bregman divergence term $\mathbb{E}[\textsc{Div}_{t}]$ and $\Psi$-shifting term $\mathbb{E}[\textsc{Shift}_{t}]$. Moreover, for sub-optimal skipping losses, we have

$$ $\displaystyle\langle{\bm{x}}_{t}-{\bm{y}},{\bm{\ell}}_{t}-{\bm{\ell}}_{t}^{ \text{skip}}\rangle$ $\displaystyle=\sum_{i\in[K]}(x_{t,i}-y_{i})\cdot(\ell_{t,i}-\ell_{t,i}^{\text{ skip}})$ $\displaystyle\leq\sum_{i\neq i^{\ast}}x_{t,i}\cdot\left|\ell_{t,i}-\ell^{\text {skip}}_{t,i}\right|+(x_{t,i^{\ast}}-1)\cdot\left(\ell_{t,i^{\ast}}-\ell_{t,i^ {\ast}}^{\text{skip}}\right)$ $\displaystyle=\mathbb{E}\left[\lvert\textsc{SkipErr}_{t}\rvert\cdot\mathbbm{1} [i_{t}\neq i^{\ast}]\mid\mathcal{F}_{t-1}\right]+(x_{t,i^{\ast}}-1)\cdot\left( \ell_{t,i^{\ast}}-\ell_{t,i^{\ast}}^{\text{skip}}\right).$ $$

Notice that the factor $(x_{t,i^{\ast}}-1)$ in the second term is negative and ${\mathcal{F}}_{t-1}$-measurable. Then we have

$$ $\displaystyle\mathbb{E}\left[\ell_{t,i^{\ast}}-\ell_{t,i^{\ast}}^{\text{skip}} \middle|\mathcal{F}_{t-1}\right]$ $\displaystyle=\mathbb{E}\left[\mathbbm{1}[\lvert\ell_{t,i^{\ast}}\rvert\geq C_ {t,i^{\ast}}]\cdot\ell_{t,i^{\ast}}\right]\geq 0,$ $$

where the inequality is due to the truncated non-negative assumption (Assumption 1) of the optimal arm $i^{\ast}$. Therefore, we have $\mathbb{E}[(x_{t,i^{\ast}}-1)\cdot(\ell_{t,i^{\ast}}-\ell_{t,i^{\ast}}^{\text{
skip}})\mid\mathcal{F}_{t-1}]\leq 0$ and thus

$$ $\displaystyle\mathbb{E}[\langle{\bm{x}}_{t}-{\bm{y}},{\bm{\ell}}_{t}-{\bm{\ell }}_{t}^{\text{skip}}\rangle\mid\mathcal{F}_{t-1}]$ $\displaystyle\leq\mathbb{E}[\lvert\textsc{SkipErr}_{t}\rvert\cdot\mathbbm{1}[i _{t}\neq i^{\ast}]\mid\mathcal{F}_{t-1}],$ $$

which gives an approach to control the skipping error by the sum of skipping losses $\textsc{SkipErr}_{t}$’s where we pick a sub-optimal arm $i_{t}\neq i^{\ast}$. Formally, we give the following inequality:

$$ $\displaystyle\textsc{Skipping Error}\leq\mathbb{E}\left[\sum_{t=1}^{T}\lvert \textsc{SkipErr}_{t}\rvert\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\right].$ $$

To summarize, the regret ${\mathcal{R}}_{T}$ decomposes into the sum of Bregman divergence terms $\mathbb{E}[\textsc{Div}_{t}]$, the $\Psi$-shifting terms $\mathbb{E}[\textsc{Shift}_{t}]$, and the sub-optimal skipping losses $\mathbb{E}[|\textsc{SkipErr}_{t}|\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]]$, namely

$$ $\displaystyle{\mathcal{R}}_{T}\leq\underbrace{\mathbb{E}\left[\sum_{t=1}^{T} \textsc{Div}_{t}\right]}_{\textsc{Bregman Divergence Terms}}+\underbrace{ \mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]}_{\textsc{$\Psi$- Shifting Terms}}+\underbrace{\mathbb{E}\left[\sum_{t=1}^{T}|\textsc{SkipErr}_{ t}|\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\right]}_{\textsc{Sub-optimal Skipping Losses}}+\sigma K.$ $$

We discuss the regret upper bound under adversarial and stochastic environments separately.

Adversarial Cases. According to Theorems 19, 23, and 26, we have

$$ $\displaystyle{\mathcal{R}}_{T}$ $\displaystyle\leq{\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]}+{ \mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]}+{\mathbb{E}\left[ \sum_{t=1}^{T}|\textsc{SkipErr}_{t}|\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\right ]}+\sigma K$ $\displaystyle\leq 8192\cdot\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{ 1}}{{\alpha}}}(\log T)^{1-\nicefrac{{1}}{{\alpha}}}+2\cdot\sigma K^{1- \nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{\alpha}}}(\log T)^{1-\nicefrac{{1} }{{\alpha}}}$ $\displaystyle\quad+\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{ \alpha}}}\cdot\left((\log T)^{1-\nicefrac{{1}}{{\alpha}}}+\frac{2}{\alpha}( \log T)^{2-\nicefrac{{1}}{{\alpha}}}+2\log\sigma-\frac{2}{\alpha}\log K-\frac{ 2}{\alpha}\log\log T\right)+\sigma K$ $\displaystyle=\sigma K^{1-\nicefrac{{1}}{{\alpha}}}T^{\nicefrac{{1}}{{\alpha}} }\cdot\left(8195(\log T)^{1-\nicefrac{{1}}{{\alpha}}}+\frac{2}{\alpha}(\log T) ^{2-\nicefrac{{1}}{{\alpha}}}+2\log\sigma-\frac{2}{\alpha}\log K-\frac{2}{ \alpha}\log\log T\right)+\sigma K.$ $$

Stochastic Cases. According to Theorems 21, 25, and 27, we have

$$ $\displaystyle{\mathcal{R}}_{T}$ $\displaystyle\leq{\mathbb{E}\left[\sum_{t=1}^{T}\textsc{Div}_{t}\right]}+{ \mathbb{E}\left[\sum_{t=0}^{T-1}\textsc{Shift}_{t}\right]}+{\mathbb{E}\left[ \sum_{t=1}^{T}|\textsc{SkipErr}_{t}|\cdot\mathbbm{1}[i_{t}\neq i^{\ast}]\right ]}+\sigma K$ $\displaystyle\leq 8192\cdot 16384^{\frac{1}{\alpha-1}}\cdot K\Delta_{\min}^{- \frac{1}{\alpha-1}}\sigma^{\frac{\alpha}{\alpha-1}}\log T+\frac{1}{4}{\mathcal {R}}_{T}$ $\displaystyle\quad+2K\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{\min}^{-\frac{1}{ \alpha-1}}\log T+\frac{1}{4}{\mathcal{R}}_{T}$ $\displaystyle\quad+\sigma^{\frac{\alpha}{\alpha-1}}\Delta_{\min}^{-\frac{1}{ \alpha-1}}\cdot K\log T\cdot\frac{4^{\frac{1}{\alpha-1}}}{\alpha-1}\left(2\log 4 +\alpha\log\sigma+\log(1/\Delta_{\min})\right)+\frac{1}{4}{\mathcal{R}}_{T}+\sigma K$ $\displaystyle\leq K\left(\frac{\sigma^{\alpha}}{\Delta_{\min}}\right)^{\frac{1 }{\alpha-1}}\log T\cdot\left(8192\cdot 16384^{\frac{1}{\alpha-1}}+2+\frac{4^{ \frac{1}{\alpha-1}}}{\alpha-1}\left(2\log 4+\log\left(\frac{\sigma^{\alpha}}{ \Delta_{\min}}\right)\right)\right)+\frac{3}{4}{\mathcal{R}}_{T},$ $$

which implies that

$$ $\displaystyle{\mathcal{R}}_{T}\leq 4\cdot K\left(\frac{\sigma^{\alpha}}{\Delta _{\min}}\right)^{\frac{1}{\alpha-1}}\log T\cdot\left(8192\cdot 16384^{\frac{1} {\alpha-1}}+2+\frac{4^{\frac{1}{\alpha-1}}}{\alpha-1}\left(2\log 4+\log\left( \frac{\sigma^{\alpha}}{\Delta_{\min}}\right)\right)\right).$ $$

Therefore, we finish the proof, which shows the BoBW property of Algorithm 1.
∎

The following lemma characterizes the FTRL regret decomposition, which is the extension of the classical FTRL bound (Lattimore and Szepesvári,, , Theorem 28.5). also gave a similar result, but we include a full proof here for the sake of completeness.

###### Lemma 29 (FTRL Regret Decomposition) .

In uniINF (Algorithm 1), we have (set $S_{0}=0$ for simplicity),

$$ $\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\langle{\bm{x}}_{t}-\widetilde{{\bm {y}}},\widetilde{\bm{\ell}}_{t}\rangle\right]\leq\sum_{t=1}^{T}\mathbb{E}[D_{ \Psi_{t}}({\bm{x}}_{t},{\bm{z}}_{t})]+\mathbb{E}[(\Psi_{t}(\widetilde{{\bm{y}} })-\Psi_{t-1}(\widetilde{{\bm{y}}}))-(\Psi_{t}({\bm{x}}_{t})-\Psi_{t-1}({\bm{x }}_{t}))],$ $$

where $D_{\Psi_{t}}$ is the Bregman divergence induced by $\Psi_{t}$, and ${\bm{z}}_{t}$ is given by

$$ $\displaystyle{\bm{z}}_{t}:=\operatorname*{argmin}_{{\bm{z}}\in\Delta^{[K]}} \left(\sum_{s=1}^{t}\langle\widetilde{{\bm{\ell}}}_{s},{\bm{z}}\rangle+\Psi_{t }({\bm{z}})\right).$ $$

###### Proof.

We denote ${\bm{L}}_{t}:=\sum_{s=1}^{t}\widetilde{\bm{\ell}}_{s}$. Denote $f^{*}:\mathbb{R}^{k}\to\mathbb{R}$ as the Frenchel conjugate of function $f:\mathbb{R}^{K}\to\mathbb{R}$, where

$$ $\displaystyle f^{*}({\bm{y}}):=\sup_{{\bm{x}}\in\mathbb{R}^{K}}\left\{\langle{ \bm{y}},{\bm{x}}\rangle-f({\bm{x}})\right\}.$ $$

Moreover, denote $\overline{f}:\mathbb{R}^{K}\to\mathbb{R}$ as the restriction of $f:\mathbb{R}^{K}\to\mathbb{R}$ on $\Delta^{[K]}$, i.e,

$$ $\displaystyle\overline{f}({\bm{x}})=\begin{cases}f({\bm{x}}),&{\bm{x}}\in \Delta^{[K]}\\ \infty,&{\bm{x}}\notin\Delta^{[K]}\end{cases}.$ $$

Therefore, by definition, we have

$$ $\displaystyle{\bm{z}}_{t}=\nabla\overline{\Psi}^{*}_{t}(-{\bm{L}}_{t}),\quad{ \bm{x}}_{t}=\nabla\overline{\Psi}^{*}_{t}(-{\bm{L}}_{t-1}).$ $$

Then recall the properties of Bregman divergence, we have

$$ $\displaystyle D_{\Psi_{t}}({\bm{x}}_{t},{\bm{z}}_{t})=D_{\Psi_{t}}(\nabla \overline{\Psi}^{*}_{t}(-{\bm{L}}_{t-1}),\nabla\overline{\Psi}^{*}_{t}(-{\bm{L }}_{t}))=D_{\overline{\Psi}_{t}^{*}}(-{\bm{L}}_{t},-{\bm{L}}_{t-1}).$ $$

Therefore, we have

$$ $\displaystyle\sum_{t=1}^{T}\langle{\bm{x}}_{t}-\widetilde{{\bm{y}}},\widetilde {\bm{\ell}}_{t}\rangle$ $\displaystyle=\langle\widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\sum_{t=1}^{T} \langle{\bm{x}}_{t},-\widetilde{\bm{\ell}}_{t}\rangle$ $\displaystyle=\sum_{t=1}^{T}\left(\overline{\Psi}^{*}_{t}(-{\bm{L}}_{t})- \overline{\Psi}^{*}_{t}(-{\bm{L}}_{t-1})-\langle\nabla\overline{\Psi}^{*}_{t}( -{\bm{L}}_{t-1}),-{\bm{L}}_{t}+{\bm{L}}_{t-1}\rangle\right)$ $\displaystyle\quad+\langle\widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\sum_{t=1} ^{T}\left(\overline{\Psi}^{*}_{t}(-{\bm{L}}_{t})-\overline{\Psi}_{t}^{*}(-{\bm {L}}_{t-1})\right)$ $\displaystyle=\sum_{t=1}^{T}D_{\overline{\Psi}_{t}^{*}}(-{\bm{L}}_{t},-{\bm{L} }_{t-1})+\langle\widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\sum_{t=1}^{T}\left( \overline{\Psi}^{*}_{t}(-{\bm{L}}_{t})-\overline{\Psi}_{t}^{*}(-{\bm{L}}_{t-1} )\right)$ $\displaystyle=\sum_{t=1}^{T}D_{\Psi_{t}}({\bm{x}}_{t},{\bm{z}}_{t})+\langle \widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\sum_{t=1}^{T}\left(\overline{\Psi}^ {*}_{t}(-{\bm{L}}_{t})-\overline{\Psi}_{t}^{*}(-{\bm{L}}_{t-1})\right).$ $$

For the second and third terms, we have

$$ $\displaystyle\quad\langle\widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\sum_{t=1}^ {T}\left(\overline{\Psi}^{*}_{t}(-{\bm{L}}_{t})-\overline{\Psi}_{t}^{*}(-{\bm{ L}}_{t-1})\right)$ $\displaystyle=\langle\widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\sum_{t=1}^{T} \left(\overline{\Psi}^{*}_{t}(-{\bm{L}}_{t})-\langle{\bm{x}}_{t},-{\bm{L}}_{t- 1}\rangle+\Psi_{t}({\bm{x}}_{t})\right)$ $\displaystyle=\langle\widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\sum_{t=1}^{T} \left(\sup_{{\bm{x}}\in\Delta^{[K]}}\left\{\langle{\bm{x}},-{\bm{L}}_{t} \rangle-\Psi_{t}({\bm{x}})\right\}-\langle{\bm{x}}_{t},-{\bm{L}}_{t-1}\rangle+ \Psi_{t}({\bm{x}}_{t})\right)$ $\displaystyle\leq\langle\widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\sum_{t=1}^{ T-1}\left(\langle{\bm{x}}_{t+1},-{\bm{L}}_{t}\rangle-\Psi_{t}({\bm{x}}_{t+1})- \langle{\bm{x}}_{t},-{\bm{L}}_{t-1}\rangle+\Psi_{t}({\bm{x}}_{t})\right)$ $\displaystyle\quad-\sup_{{\bm{x}}\in\Delta^{[K]}}\left\{\langle{\bm{x}},-{\bm{ L}}_{T}\rangle-\Psi_{T}({\bm{x}})\right\}+\langle{\bm{x}}_{T},-{\bm{L}}_{T-1} \rangle-\Psi_{T}({\bm{x}}_{T})$ $\displaystyle=\langle\widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\sum_{t=1}^{T} \left(\Psi_{t}({\bm{x}}_{t})-\Psi_{t-1}({\bm{x}}_{t})\right)-\sup_{{\bm{x}}\in \Delta^{[K]}}\left\{\langle{\bm{x}},-{\bm{L}}_{T}\rangle-\Psi_{T}({\bm{x}})\right\}$ $\displaystyle=\langle\widetilde{{\bm{y}}},-{\bm{L}}_{T}\rangle-\Psi_{T}( \widetilde{{\bm{y}}})-\sup_{{\bm{x}}\in\Delta^{[K]}}\left\{\langle{\bm{x}},-{ \bm{L}}_{T}\rangle-\Psi_{T}({\bm{x}})\right\}+\Psi_{T}(\widetilde{{\bm{y}}})- \sum_{t=1}^{T}\left(\Psi_{t}({\bm{x}}_{t})-\Psi_{t-1}({\bm{x}}_{t})\right)$ $\displaystyle\leq\sum_{t=1}^{T}(\Psi_{t}(\widetilde{{\bm{y}}})-\Psi_{t-1}( \widetilde{{\bm{y}}}))-\sum_{t=1}^{T}\left(\Psi_{t}({\bm{x}}_{t})-\Psi_{t-1}({ \bm{x}}_{t})\right),$ $$

which finishes the proof.
∎

###### Theorem 28 (Formal version of Theorem 3 ) .

###### Proof.

###### Lemma 29 (FTRL Regret Decomposition) .

###### Proof.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: When $\alpha, \sigma$ known, it is trivial to use regular FTRL based algorithm to achieves (nearly) optimal worst-case regret for adversarial bandit problems with potentially heavy-tailed losses (fix the clipping bound $[-r,r]$ with $r=\sigma T^{1/\alpha}K^{-1/\alpha}$ and use Theorem 4 in [6]). When $\alpha, \sigma$ are unknown, intuitively, it suffices to use the adaptive clipping bound according to the empirical estimation of $\alpha, \sigma$ (Line 6 of ALG 1). Is the high-level idea of the algorithm in this paper the one I described?


References: 
[1] Putta, Sudeep Raja, and Shipra Agrawal. "Scale-free adversarial multi armed bandits." International Conference on Algorithmic Learning Theory. PMLR, 2022.

[2] Chen, Mingyu, and Xuezhou Zhang. "Scale-free Adversarial Reinforcement Learning." arXiv preprint arXiv:2403.00930 (2024).

[3] Chen, Mingyu, and Xuezhou Zhang. "Improved Algorithms for Adversarial Bandits with Unbounded Losses." arXiv preprint arXiv:2310.01756 (2023).

[4] Huang, Jiatai, Yan Dai, and Longbo Huang. "Banker online mirror descent: A universal approach for delayed online bandit learning." International Conference on Machine Learning. PMLR, 2023.

[5] Hadiji, Hédi, and Gilles Stoltz. "Adaptation to the range in k-armed bandits." Journal of Machine Learning Research 24.13 (2023): 1-33.

[6] Wei, Chen-Yu, and Haipeng Luo. "More adaptive algorithms for adversarial bandits." Conference On Learning Theory. PMLR, 2018.
soundness: 3
strengths: 1. The paper is well written. The theoretical results and proof appear to be correct.
2. The paper achieves worst-case BoBW optimal regret for HTMAB, which improves previous results proposed in [Huang 2022].
summary: The paper studies Heavy-Tailed MultiArmed Bandits (HTMAB) problem. The main contribution of the paper is to design an optimal algorithm that achieves both Best of-Both-Worlds (BoBW) and Parameter-free properties for HTMAB, where BoBW means that the algorithm performs optimally in both stochastic and adversarial environments and Parameter-free means that the algorithm do not need to know the the heavy-tail parameters in advance.
weaknesses: 1. The paper should include the comparisons with previous scale-free MAB works, e.g. [1-5]. Specifically, the algorithm structure proposed in the paper seems very close to the one proposed in [3], which also uses the clipping/skipping technique and inf regularization. The differences should be further clarified.
2. Assumption 1 is a bit weird. I can understand why it is unavoidable, but I suggest that the authors can give the best (not worst-case optimal) upper bounds we can get without this assumption.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: - How do applications justify the adversarial HTMAB? Can you please provide some examples?

- I think it would be interesting to highlight the trade-off between ADAR-UCB and UniInf more. How is the best-of-both-worlds property related to the extra factor in the stochastic setting's regret bound? Does your algorithm require extra round-robin turns (as in Adar-UCB)?

- Do you know what the optimal performance would be without the truncated non-negativity assumption? Are there any known lower bounds for the problem without this assumption?

- It would be interesting to understand if alternative (and possibly weaker) assumptions can lead to the same performances (I would like to point out that Theorems 2 and 3 from Genalti et al. don't necessarily imply that this specific assumption is required, but rather that without any assumptions such performances are unattainable).
soundness: 3
strengths: The paper is written, and it provides an exhaustive review of the existing literature.

The contribution is clear, and it is well highlighted which open question the paper addresses.

The paper also presents some nice technical contributions in the algorithm and in the proofs.
summary: The paper addresses the heavy-tailed MAB problem, a variant of the stochastic bandit problem where rewards are sampled from distributions having potentially infinite variance. The main contribution of this work is to provide an algorithm with tight regret guarantees in both the stochastic and adversarial HTMAB problem. While the performance in the stochastic setting is worse (not in terms of T) than existing algorithms (e.g. AdarUCB), the algorithm simultaneously deals with the two settings and is tight in both the instance-dependent and independent sense.
weaknesses: Overall, the contribution is limited when it comes to applications since adversarial HTMABs are uncommon in the real world and the literature. Instead, in the purely stochastic setting, the algorithm does slightly worse than AdaRUCB by a factor of  $\log \frac{\sigma^\alpha}{\Delta_{min}}$ (Genalti et al.)

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. If $(\sigma, \alpha)$ is known a priori, can we eliminate Assumption 1? What are the main technical difficulties when eliminating Assumption 1 in the case of known $(\sigma, \alpha)$?
2. In the previous work [10], the Tsallis entropy regularizer is used while the log-barrier regularizer is used in this work. Is it because the magnitude of the loss estimates in this work is larger than the magnitude of the loss estimates in [10]?

[10] Huang et al. Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed
Bandits. ICML, 22.
soundness: 3
strengths: 1. **Technical innovations**: The proposed algorithm and its analysis incorporate new ingredients including a new skipping and clipping scheme of the loss estimates and a stopping time argument to bound the stability terms and the skipping errors, which seem to be technically valuable and might be of independent interest.
2. **Writing**: Generally, this work is well written.
summary: This work establishes the first parameter-free algorithm for heavy-tailed multi-armed bandits (MABs) with best-of-both-worlds (BOBW) properties. This algorithm does not require prior knowledge of heavy-tail parameters $(\sigma, \alpha)$ and simultaneously obtains the (nearly) optimal regret in both the stochastic and adversarial environments.
weaknesses: 1. **More comparisons with existing literature**: Most parts of the presentation in this work are clear. However, I would like to suggest the authors provide more discussions and comparisons with the techniques in existing literature. For instance, the exclusion of the optimal arm $i^\ast$ in Eq. (5) when using the log-barrier regularizer is also achieved by [1,2]. I am not very sure whether there are additional technical nuances between the exclusion of the optimal arm in Eq. (5) of this work and those in [1,2]. For the data-dependent learning rates, several works have also leveraged them to achieve BOBW results in various online learning problems (say, [2,3,4,5,6,7]). Besides, when bounding the stability term of OMD/FTRL, a key property required is to ensure the multiplicative stability of the update of the prediction. In this work, such a property is guaranteed by Lemma 4. However, it seems not appropriate to call such a lemma “novel” as on Line 423, since it has also appeared in previous works when using the log-barrier regularizer (say, Lemma 9 in [8]; Lemma 12 in [9]).

[1] Ito. Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds. COLT, 21.

[2] Ito. Hybrid Regret Bounds for Combinatorial Semi-Bandits and Adversarial Linear Bandits. NeurIPS, 21.

[3] Ito et al. Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs. NeurIPS, 22.

[4] Tsuchiya et al. Best-of-Both-Worlds Algorithms for Partial Monitoring. ALT, 23.

[5] Ito et al. Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds. COLT, 23.

[6] Kong et al. Best-of-three-worlds analysis for linear bandits with follow-the-regularized-leader algorithm. COLT, 23.

[7] Ito et al. Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds. COLT, 24.

[8] Lee et al. A closer look at small-loss bounds for bandits with graph feedback. COLT, 20.

[9] Jin et al. Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition. NeurIPS, 20.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. To my understanding, this paper claims to develop a new analysis for $DIV_t$ (also named stability term) when using log-barrier, and introduces an extra $(1-x_{t,i})^2$ factor in the bound, which is the key to get self-bounding property and BOBW. However, I don't quite understand what it means by “$S_t$ is adequately large compared to $||c_t||_{\infty}$”. I tried to find a formal lemma or theorem statement for this new bound (with exactly the same form) on $DIV_t$ term but I failed. Could the authors help explain this? Under what conditions does this new bound hold?

2. What’s the difficulty to get the refined gap dependency? From the appendix, I feel that in both DIV term and SHIFT term, we cannot achieve that. Could the authors elaborate more on that (from the analysis perspective)? Is it because the regularizer is log-barrier rather than Tsallis entropy?

Post rebuttal ===============================

I'm increasing the score from 6 to 8.
soundness: 3
strengths: The parameter-free BOBW bound in HTMAB is a quite strong guarantee, and to achieve this, several technical innovations are proposed.
summary: This paper studies parameter-free best-of-both-worlds (BOBW) for HT-MABs, where 1) HT means that the loss distributions can be unbounded but have $\\alpha$-th moment bounded by $\\sigma^{\\alpha}$, for some $\\sigma>0, \\alpha\in(1,2]$; 2) BOBW means that one single algorithm can enjoy logarithmic gap-dependent regret in the stochastic environment (loss distributions are fixed over time) and worst-case optimal regret in adversarial environment (loss distributions change over time), without knowing in advance whether the environment is sto. or not; 3) parameter-free means that the algorithm doesn’t now the value of $\\sigma>0, \\alpha\in(1,2]$, but can ensure the regret guarantee as if they were known.

An algorithm called uniINF is proposed, which ensures $\\tilde{O}(\\frac{K}{(\\Delta_{\\text{min}})^{\\frac{1}{\\alpha-1}}}) $ (expected pseudo-)regret in sto. env. (which is optimal up to log terms and the gap dependency), and near-optimal regret in adv. env. (which is optimal up to log terms) when the loss distributions of the optimal arm satisfy the truncated non-negative assumption (Assumption 1). This is the first parameter-free BOBW result in HTMAB. Previous results approach that in one single env. only (either sto. or adv.).

Technically, this is achieved by several components, including 1) iterative and adaptive learning rate scheduling; 2) adaptive clipping/skipping; 3) refined analysis for log-barrier regularizer.
weaknesses: I’m not happy with how Assumption 1 is justified. From Line 193 to 195, it says that "we make the following **essential** assumption. As shown in (Genalti et al., 2024, Theorems 2 & 3), without Assumption 1, there does not exist HTMAB algorithms that can … without knowing either $\\alpha$ or $\\sigma$." However, this statement could be misleading based on my understanding on (Genalti et al., 2024).

The negative result shown in (Genalti et al., 2024) is that, it’s impossible for one single algorithm to match the lower bound in (Bubeck et al., 2013) for all unknown $\\sigma>0$ or $\\alpha\\in(1,2]$. However, I don’t think it has been characterized that how weak the needed assumption to be "parameter-free" in HTMAB. In fact, in the conclusion part of (Genalti et al., 2024), it even says that "investigating the role of the truncated non-positivity assumption, especially, whether weaker assumptions can be formulated."

Therefore, I would urge the authors to refine the statements related to Assumption 1, as currently it may leave the impression that Assumption 1 is a necessary condition for "parameter-free", which as of now it’s still unclear yet.

Meta-review: This paper proposes a best-of-both-worlds algorithm for the heavy-tailed multi-armed bandit problem, which achieves optimal performance in both stochastic and adversarial environments. A significant strength of the proposed algorithm is its adaptability to the (unknown) heavy-tail parameter. However, its limitations include the regret upper bound in the stochastic setting depending solely on the minimum gap $\Delta_{\min}$ rather than the individual gaps $(\Delta_i)$, and the requirement of the truncated-non-negativity assumption (Assumption 1). Regarding the latter point, the authors have appropriately justified its necessity by referencing the lower bound established in prior work [Genalti et al., 2024]. The authors have adequately addressed the reviewers' concerns and questions. Given the consensus among the reviewers to accept the paper, I support its acceptance.

Additionally, there are areas for improvement as follows:
* The current text in Lines 213-253 may give the impression that this paper is the first to demonstrate the best-of-both-worlds property using log-barrier regularization in FTRL. However, previous studies, such as (Wei & Luo, 2018) and (Ito, 2021b), have also shown that the best-of-both-worlds property can be achieved using log-barrier regularization. It would be better to revise the description to avoid potential misunderstandings.
> While log-barrier regularizers were commonly used in the literature for data-adaptive bounds such as small-loss bounds (Foster et al., 2016), path-length bounds (Wei & Luo, 2018), and second-order bounds (Ito, 2021b), this paper introduces novel analysis illustrating that log-barrier regularizers also provide environment-adaptivity for both stochastic and adversarial settings.
* Regarding Assumption 2, while it is true that this assumption is common in prior work, it may also be worth mentioning that Tsallis-INF (Zimmert & Seldin, 2019) and its extensions do not require this assumption; The analysis of Tsallis-INF is provided in (Ito, 2021b), and its extension is presented in (Jin et al., 2023).

Decision: Accept (Spotlight)