High Probability Bounds for Cross-Learning Contextual Bandits with Unknown Context Distributions

## Abstract

Abstract Motivated by applications in online bidding and sleeping bandits, we examine the problem of contextual bandits with cross learning, where the learner observes the loss associated with the action across all possible contexts, not just the current round’s context. Our focus is on a setting where losses are chosen adversarially, and contexts are sampled i.i.d. from a specific distribution. This problem was first studied by Balseiro et al. ( 2019 ) , who proposed an algorithm that achieves near-optimal regret under the assumption that the context distribution is known in advance. However, this assumption is often unrealistic.
To address this issue, Schneider and Zimmert ( 2023 ) recently proposed a new algorithm that achieves nearly optimal expected regret. It is well-known that expected regret can be significantly weaker than high-probability bounds. In this paper, we present a novel, in-depth analysis of their algorithm and demonstrate that it actually achieves near-optimal regret with high probability .
There are steps in the original analysis by Schneider and Zimmert ( 2023 ) that lead only to an expected bound by nature. In our analysis, we introduce several new insights. Specifically, we make extensive use of the weak dependency structure between different epochs, which was overlooked in previous analyses. Additionally, standard martingale inequalities are not directly applicable, so we refine martingale inequalities to complete our analysis.

## 1 introduction

In the contextual bandits problem, a learner repeatedly observes a context, chooses an action, and incurs a loss specific to that action. The goal of the learner is to minimize the cumulative loss over the time horizon. The contextual bandits problem is a fundamental problem in online learning having broad applications in fields like online advertising, personalized recommendations, and clinical trials (Li et al., ; Kale et al., ; Villar et al., ).

We consider the cross-learning contextual bandits problem. In this setting, the learner not only observes the loss for the current action under the current context, but also observes the loss for the current action under all other contexts. This problem models many interesting scenarios. One such example is the problem of learning to bid in first-price auctions. In this problem the context is the bidder’s private value for the item, while the action is the bid. The cross-learning structure comes from the fact that the bidder can deduce the utility of the bid under all contexts (i.e., the utility of the bid under different private valuations for the item). Other examples include multi-armed bandits with exogenous costs, dynamic pricing with variable costs, and learning to play in Bayesian games (Balseiro et al., ).

Technically, the most interesting setting for the cross-learning contextual bandits problem is when the losses are chosen adversarially but the contexts are i.i.d. samples from an unknown distribution $\nu$. Recently, Schneider and Zimmert () gave an algorithm achieving nearly optimal $\tilde{O}(\sqrt{KT})$ regret in this scenario.

Schneider and Zimmert () designed a sophisticated algorithm that operates over multiple epochs to achieve near-optimal regret. A key technique in their analysis is to sidestep high-probability bounds and instead focus on bounding the expected summation to improve their results. As a consequence, their analysis only provides a bound that holds in expectation. It is not immediately clear whether this is due to limitations in the analysis or if the algorithm is inherently suboptimal. In any case, if we aim for a high-probability bound, fundamentally new insights are required.

In this paper, we show that the algorithm indeed achieves nearly optimal $\tilde{O}(\sqrt{KT})$ regret with high-probability by conducting a more in-depth analysis. Our analysis introduces several new insights. In particular, we exploit the weak dependency structure between different epochs, which was overlooked in previous work. One difficulty of doing so is that standard martingale inequalities are not directly applicable, so we refine martingale inequalities to complete our analysis.

### 1.1 Related Works

The cross-learning contextual bandits problem was first proposed in Balseiro et al. (). They achieve the nearly optimal $\tilde{O}(\sqrt{KT})$ regret under two scenarios: (1) when both losses and contexts are stochastic, and (2) when losses are adversarial and contexts are stochastic with a known distribution. When losses are adversarial and contexts are stochastic with an unknown distribution, they only achieve the suboptimal $\tilde{O}(K^{1/3}T^{2/3})$ regret. More recently, Schneider and Zimmert () gave a new algorithm that achieves the nearly optimal $\tilde{O}(\sqrt{KT})$ regret in expectation under adversarial losses and stochastic contexts with an unknown distribution.

An important application of the cross-learning contextual bandits problem, which is also the primary motivation for proposing this problem in Balseiro et al. (), is to solve the problem of learning to bid in first-price auctions.
In this problem the context is the bidder’s private value for the item, while the action is the bid. The cross learning structure comes from the fact that the bidder can deduce the utility of the bid under all contexts (i.e., the utility of the bid under different private valuations for the item).

Balseiro et al. () used the cross-learning contextual bandits problem to model the bidding problem and obtained an $O(T^{3/4})$ regret bound for bidders with an unknown value distribution participating in adversarial first-price auctions, where the only feedback is whether the bidder wins the auction. Later, many works studied different settings of the bidding in first price auctions problem. For example, Han et al. () considered the problem with censored feedback, where each bidder observes the winning bid. Han et al. () considered the scenario when the value is also adversarial. Ai et al. (); Wang et al. () considered the problem under budget constraints. In all these scenarios, the cross learning structure between different values is an essential component of the analysis.

Another interesting application of the cross-learning contextual bandits problem is the sleeping bandits problem (Kleinberg et al., ; Neu and Valko, ; Kale et al., ; Saha et al., ). In this problem, a certain set of arms is unavailable in each round. The sleeping bandits problem is motivated by instances like some items might go out of stock in retail stores or on a certain day some websites could be down. When losses are adversarial and availabilities are stochastic, previous work either requires exponential computing time (Kleinberg et al., ; Neu and Valko, ) or results in suboptimal regret (Kale et al., ; Saha et al., ). The first computationally efficient algorithm with optimal regret $\tilde{O}(\sqrt{KT})$ is proposed in Schneider and Zimmert () by modeling the problem as a cross-learning contextual bandit.

We also note that handling unknown context distributions is a common and challenging problem across various contextual bandit problems. For example, in the adversarial linear contextual bandits problem (Neu and Olkhovskaya, ), the linear MDP problem (Dai et al., ), and the oracle-based adversarial contextual bandits problem (Syrgkanis et al., ), existing algorithms often rely on knowledge of the context distribution. Removing the reliance on knowledge of the context distribution is typically non-trivial (Liu et al., ; Dai et al., ).

## 2 Preliminaries

### 2.1 Problem Statement

We study a contextual $K$-armed bandit problem over $T$ rounds, with contexts belonging to the set $[C]$. At the beginning of the problem, an oblivious adversary selects a sequence of losses $\ell_{t,c}(k)\in[0,1]$ for every round $t\in[T]$, every context $c\in[C]$, and every arm $k\in[K]$. In each round $t$, we begin by sampling a context $c_{t}\sim\nu$ i.i.d. from an unknown distribution $\nu$ over $[C]$, and we reveal this context to the learner. Based on this context, the learner selects an arm $a_{t}\in[K]$ to play. The adversary then reveals the function $\ell_{t,c}(a_{t})$, and the learner suffers loss $\ell_{t,c_{t}}\left(a_{t}\right)$. Notably, the learner observes the loss for every context $c\in[C]$, but only for the arm $a_{t}$ they actually played.

We aim to design learning algorithms that minimize regret. Fix a policy $\pi:[C]\rightarrow[K]$. With a slight abuse of notation, we also denote $\pi_{c}=e_{k}\in\Delta([K])$ for each $c\in[C]$. The (unexpected) regret with respect to policy $\pi$ is

$$ $\operatorname{\mathrm{Reg}}(\pi)=\sum_{t=1}^{T}\ell_{t,c_{t}}(a_{t})-\ell_{t,c _{t}}(\pi_{c_{t}}).$ $$

We aim to upper bound this quantity (for an arbitrary policy $\pi$).

Schneider and Zimmert () designed an algorithm that achieves an expected regret bound of

$$ $\mathbb{E}\left[\operatorname{\mathrm{Reg}}(\pi)\right]\leq\tilde{O}(\sqrt{KT})$ $$

for any policy $\pi$.
We will show that the algorithm in Schneider and Zimmert () actually provides a high-probability regret bound. That is, we will prove the following result.

###### Theorem 1 .

For $\iota=2\log(8KT)$, $L=\sqrt{\frac{\iota KT}{\log(K)}}=\widetilde{\Theta}(\sqrt{KT})$, $\gamma=\frac{16\iota}{L}=\widetilde{\Theta}(1/\sqrt{KT})$, and $\eta=\frac{\gamma}{2(2L\gamma+\iota)}=\widetilde{\Theta}(1/\sqrt{KT})$, the algorithm in Schneider and Zimmert () yields a regret bound of $\operatorname{\mathrm{Reg}}(\pi)=\widetilde{\Theta}(\sqrt{KT})$ with high probability for any policy $\pi$.

###### Theorem 1 .

### 2.2 Existing Analysis

The algorithm proposed in Schneider and Zimmert () is an EXP3-type algorithm.
Similar to the well-known EXP3 algorithm, at each round $t$, the algorithm generates a distribution using an FTRL subroutine

$$ $p_{t,c}=\operatorname*{arg\,min}_{p\in\Delta([K])}\left\langle p,\sum_{s=1}^{t -1}\hat{\ell}_{s,c}\right\rangle-\frac{1}{\eta}F(p)$ $$

for each context $c$, where $F(p)=\sum_{i=1}^{K}p_{i}\log(p_{i})$ is the unnormalized negative entropy, $\eta$ is a learning rate, and $\hat{\ell}$ are loss estimates to be defined later.
The algorithm then essentially samples the action $a_{t}$ to be played in round $t$ from distribution $p_{t,c_{t}}$.

The key novelty in Schneider and Zimmert () lies in the construction of the loss estimates $\hat{\ell}$.
An intuitive construction is defined as follows:

$$ $\hat{\ell}_{t,c}(a)=\frac{\ell_{t,c}(a)}{\mathbb{E}_{c\sim\nu}[p_{t,c}(a)]} \operatorname{\mathbbm{1}}(a_{t}=a).$ $$

That is, it uses the classic importance-weighted estimator with $\mathbb{E}_{c\sim\nu}[p_{t,c}(a)]$ as the importance.
A straightforward analysis shows that this estimator yields a regret bound of $\tilde{O}(\sqrt{KT})$.
However, the denominator term $\mathbb{E}_{c\sim\nu}[p_{t,c}(a)]$ is uncomputable because we do not know the distribution of contexts $\nu$.
One may attempt to circumvent this issue by replacing the expected importance $\mathbb{E}_{c\sim\nu}[p_{t,c}(a)]$ with the empirical importance $\frac{1}{t}\sum_{s=1}^{t}p_{t,c_{s}}(a)$.
It is not hard to see that whether we achieve the desired $\tilde{O}(\sqrt{KT})$ regret depends on how well the empirical importance weight $\frac{1}{\frac{1}{t}\sum_{s=1}^{t}p_{t,c_{s}}(a)}$ concentrates around the expected importance weight $\frac{1}{\mathbb{E}_{c\sim\nu}[p_{t,c}(a)]}$.
However, the empirical importance weight $\frac{1}{\frac{1}{t}\sum_{s=1}^{t}p_{t,c_{s}}(a)}$ may not concentrate well around the expected importance weight $\frac{1}{\mathbb{E}_{c\sim\nu}[p_{t,c}(a)]}$.
This is because the probability vector $p_{t,c}$ is not independent of the previous contexts $c_{s}$, which makes standard concentration inequalities inapplicable.

To address this difficulty, Schneider and Zimmert () divides the time horizon into epochs of equal length $L$.
At the end of each epoch $e$, the algorithm stores the FTRL distribution at the current time $t=eL$ in a new distribution $s_{e}$; that is, it takes $s_{e,c}(a)=p_{t,c}(a)$ for each context $c$ and each arm $a$.
The algorithm further decouples the distribution played by the algorithm and the distribution used to estimate the loss vector.
For each time $t$ in epoch $e+2$, the algorithm observes the loss $\ell_{t,c}(a)$ for each arm $a$ and context $c$ with probability $f_{e}(a)\triangleq\mathbb{E}_{c\sim\nu}[s_{e,c}(a)/2]$.
The algorithm then estimates the expected importance $f_{e}(a)$ using an empirical importance $\hat{f}_{e}(a)$ constructing solely from contexts in epoch $e+1$.
Finally, the algorithm constructs $\hat{\ell}_{t,c}(a)$ as an importance-weighted estimator with $\hat{f}_{e}(a)$ serving as the importance.

The empirical importance weight $\frac{1}{\hat{f}_{e}(a)}$ concentrates around the expected importance weight $\frac{1}{f_{e}(a)}$ because the algorithm only uses samples from epoch $e+1$ to construct the estimator, and these samples are independent of the estimand $\frac{1}{f_{e}(a)}$.
However, since the algorithm uses samples from only a single epoch rather than the entire time horizon, the concentration $|\frac{1}{\hat{f}_{e}(a)}-\frac{1}{f_{e}(a)}|$ is not tight enough.
To achieve the desired $\tilde{O}(\sqrt{KT})$ regret under a not tight enough concentration, Schneider and Zimmert () bounds only the expected bias of importance estimator $\mathbb{E}[\frac{1}{\hat{f}_{e}(a)}-\frac{1}{f_{e}(k)}]$ rather than providing a high-probability bias bound.
Bounding only the expected bias gives a small enough bound, however, they can achieve a bound only on the expected regret from a bound on the expected bias.

### 2.3 Our Techniques

We overcome this difficulty and show that their algorithm actually achieves a high-probability bound.
Our key observation is that different epochs in their algorithm are only weakly dependent on each other.
Thus, the bias $\frac{1}{\hat{f}_{e}(a)}-\frac{1}{f_{e}(a)}$ for each epoch $e$ is also only weakly dependent on each other.
Therefore, although we cannot establish a small enough bound for the bias of a single epoch $\frac{1}{f_{ek}}-\frac{1}{\widehat{f}_{ek}}$, we can give a small enough bound for the cumulative bias across all epochs $\sum_{e}\frac{1}{f_{ek}}-\frac{1}{\widehat{f}_{ek}}$.
We then use the bound on the cumulative bias to bound the cumulative regret.

In addition to utilizing the weak dependency structure between different epochs, we also address two further technical difficulties to establish our result.
The first difficulty is that the existing regret decomposition is too crude to yield a high-probability bound.
Schneider and Zimmert () establish an $\tilde{O}(\sqrt{KT})$ expected regret by decomposing the regret into different parts and bounding each part separately. Although their decomposition gives an $\tilde{O}(\sqrt{KT})$ expected regret bound, it is too crude to derive a tight high-probability regret bound, even after utilizing the weak dependency structure.
We carefully rearrange the regret decomposition to address this difficulty.

Secondly, we cannot simply apply standard martingale concentration inequalities to $\sum_{e}\frac{1}{f_{ek}}-\frac{1}{\widehat{f}_{ek}}$ to bound its deviation.
The main problem is that the random variable $\frac{1}{f_{ek}}-\frac{1}{\widehat{f}_{ek}}$ is not almost surely bounded by a constant, which makes standard martingale concentration inequalities inapplicable.
We introduce a surrogate sequence of random variables as a bridge to address this problem.
We bound the sum over the surrogate sequence, and show that the sum over the real sequence is equal to the surrogate sequence with high probability.

## 3 Main Analysis

### 3.1 The Algorithm in Schneider and Zimmert (2023)

In this subsection, we briefly recall the algorithm proposed in Schneider and Zimmert () for the sake of completeness. Readers familar with Schneider and Zimmert () can skip this subsection safely.

In each round $t$, the algorithm generates a distribution from an FTRL subroutine:

$$ $p_{t,c}=\operatorname*{arg\,min}_{p\in\Delta([K])}\left\langle p,\sum_{s=1}^{t -1}\hat{\ell}_{s,c}\right\rangle-\frac{1}{\eta}F(p)$ $$

for each context $c$, where $F(p)=\sum_{i=1}^{K}p_{i}\log(p_{i})$ is the unnormalized negative entropy, $\eta$ is the learning rate, and $\hat{\ell}$ are loss estimates to be defined later.
The algorithm will not sample the action $a_{t}$ played in round t directly from $p_{t}$ but from a distribution $q_{t}$ to be defined later.

To construct loss estimates $\hat{\ell}$, the algorithm divides the time horizon into epochs of equal length $L$. We let $\mathcal{T}_{e}$ to denote the set of rounds in the $e$-th epoch. At the end of each epoch, the algorithm takes a single snapshot of the underlying FTRL distribution $p_{t}$ for each context and arm. That is, the algorithm takes

$$ $s_{e+2,c}(a)=p_{eL,c}(a),\text{ where }s_{1,c}(a)=s_{2,c}(a)=\begin{cases} \frac{1}{\left|\mathcal{A}_{c}\right|}&\text{ if }a\in\mathcal{A}_{c}\\ 0&\text{ otherwise.}\end{cases}$ $$

For each round $t\in\operatorname{\mathcal{T}_{e}}$, the algorithm observes the loss function of arm $a$ with probability $f_{e}(a)=\mathbb{E}_{c\sim\nu}\left[s_{e,c}(a)/2\right]$. This is guaranteed by
the following rejection sampling procedure: we first play an arm according to the distribution

$$ $q_{t,c_{t}}=\begin{cases}p_{t,c_{t}}&\text{ if }\forall a\in[K]:p_{t,c_{t}}(a) \geq s_{e,c_{t}}(a)/2\\ s_{e,c_{t}}&\text{ otherwise.}\end{cases}$ $$

After playing arm $a$ according to $q_{t,c_{t}}$, the learner samples a Bernoulli random variable $S_{t}$ with probability $\frac{s_{e,c_{t}}(a)}{2q_{t,c_{t}}(a)}$. If $S_{t}=0$, the learner ignores the feedback from this round; otherwise, they use this loss.

The only remaining unspecified part is how to construct the loss estimates. We group all
timesteps into consecutive pairs of two. In each pair of consecutive timesteps, we sample from the same distribution and randomly use one to calculate a loss estimate and the other to estimate the sampling frequency. To be precise, let $\mathcal{T}_{e}^{f}$ denote the timesteps selected for estimating the sampling frequency and $\mathcal{T}_{e}^{\ell}$ denote the timesteps used to estimate the losses. Then we define

$$ $\widehat{f}_{e}(a)=\frac{1}{\left|\mathcal{T}_{e-1}^{f}\right|}\sum_{t\in \mathcal{T}_{e-1}^{f}}\frac{s_{e,c_{t}}(a)}{2}$ $$

which is an unbiased estimator of $f_{e}(a)$. The loss estimators are defined as follows:

$$ $\widehat{\ell}_{t}(a)=\frac{2\ell_{t}(a)}{\widehat{f}_{e}(a)+\frac{3}{2}\gamma }\operatorname{\mathbbm{1}}\left(A_{t}=a\wedge S_{t}\wedge t\in\mathcal{T}_{e} ^{\ell}\right)$ $$

where $\gamma$ is a confidence parameter to be specified later.

Figure: Algorithm 1 The algorithm for the cross-learning problem in Schneider and Zimmert ()

### 3.2 Overview of Our Analysis

In this subsection, we briefly overview our proof of Theorem 1. The full proof can be found in the appendix.

Denote the set of all timesteps used to estimate the frequency as $\operatorname{\mathcal{T}^{f}}$ and denote the set of all timesteps used to estimate the losses as $\operatorname{\mathcal{T}^{\ell}}$. For each $t\in\operatorname{\mathcal{T}_{e}}$, we define $\widetilde{\ell}_{t,c}(a)=\frac{2\ell_{t,c}(a)}{f_{e}(a)+\gamma}\operatorname{
\mathbbm{1}}\left(A_{t}=a\wedge S_{t}\wedge t\in\mathcal{T}_{e}^{\ell}\right)$. We decompose regret $\operatorname{\mathrm{Reg}}(\pi)=\sum_{t=1}^{T}\ell_{t,c_{t}}(a_{t})-\ell_{t,c
_{t}}(\pi_{c_{t}})$ as follows:

$$ $\displaystyle\operatorname{\mathrm{Reg}}(\pi)$ $\displaystyle=\underbrace{\sum_{t=1}^{T}\left(\ell_{t,c_{t}}(a_{t})-\ell_{t,c_ {t}}(\pi_{c_{t}})\right)-2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\left( \ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}(\pi_{c_{t}})\right)}_{\operatorname{ \mathbf{bias}}_{1}}$ $\displaystyle+$ $\displaystyle\underbrace{2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\left( \ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}(\pi_{c_{t}})-\sum_{c}\Pr(c)\langle p_{t,c }-\pi_{c},\ell_{t,c}\rangle\right)}_{\operatorname{\mathbf{bias}}_{2}}$ $\displaystyle+$ $\displaystyle\underbrace{2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c} \Pr(c)\langle p_{t,c}-\pi_{c},\hat{\ell}_{t,c}\rangle}_{\textbf{ftrl}}+ \underbrace{2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\ell_{t,c}-\tilde{\ell}_{t,c}\right\rangle}_{\operatorname{ \mathbf{bias}}_{3}}$ $\displaystyle+$ $\displaystyle\underbrace{2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c} \Pr(c)\left\langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\right\rangle}_{ \operatorname{\mathbf{bias}}_{4}}+\underbrace{2\sum_{t\in\operatorname{ \mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle\pi_{c},\hat{\ell}_{t,c}-\ell_{t ,c}\right\rangle}_{\operatorname{\mathbf{bias}}_{5}}.$ $$

Our decomposition is different from the decomposition in Schneider and Zimmert (), this difference is essential for deriving a high-probability bound. The key difference lies in the term $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle\pi_{c},
\hat{\ell}_{t,c}-\tilde{\ell}_{t,c}\right\rangle$ in the $\operatorname{\mathbf{bias}}_{2}$ term of Schneider and Zimmert (), which becomes $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle\pi_{c},
\hat{\ell}_{t,c}-\ell_{t,c}\right\rangle$ in the $\operatorname{\mathbf{bias}}_{5}$ term here. This difference saves a $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle\pi_{c},
\tilde{\ell}_{t,c}-\ell_{t,c}\right\rangle$ term, which is crucial for deriving a high-probability bound.

In our decomposition, the $\operatorname{\mathbf{bias}}_{1}$ term refers to the bias introduced by replacing the regret over the entire time horizon with that over $\operatorname{\mathcal{T}^{\ell}}$, and the $\operatorname{\mathbf{bias}}_{2}$ term refers to the bias introduced by replacing regret with its linearization. Both of these terms are not hard to bound using standard concentration inequalities.
Furthermore, the ftrl and $\operatorname{\mathbf{bias}}_{3}$ terms are standard in the analysis of high-probability bounds for bandit algorithms. These two terms are not hard to bound using techniqes from EXP3-IX (Neu, ) and Schneider and Zimmert ().

The terms of interest to bound are $\operatorname{\mathbf{bias}}_{4}$ and $\operatorname{\mathbf{bias}}_{5}$. These two terms can be bounded using similar methods. Here we give a sketch of the analysis of the $\operatorname{\mathbf{bias}}_{5}$ term. Details can be found in the appendix.

To bound $\operatorname{\mathbf{bias}}_{5}$, we define a filtration $\{\operatorname{\mathcal{H}}_{t}\}_{t}$ such that the $\sigma$-algebra
$\operatorname{\mathcal{H}}_{t}$ for each time step $t$ is generated by all randomness before time $t$. Next, we decompose $\operatorname{\mathbf{bias}}_{5}$ as

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle\pi_{c},\hat{\ell}_{t,c}-\ell_{t,c}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \hat{\ell}_{t,c}(\pi_{c})-\ell_{t,c}(\pi_{c})\right)$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t- 1}\right]-\ell_{t,c}(\pi_{c})\right)$ $\displaystyle+\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right).$ $$

In this decomposition, the two terms correspond to different components of the bias of the estimator $\hat{\ell}_{t,c}$. The first term $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left(\mathbb{E}
\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]-
\ell_{t,c}(\pi_{c})\right)$ corresponds to the bias introduced by constructing the importance estimator $\hat{f}_{e}(a)$. The second term $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left(\hat{\ell}_{t,
c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{
\mathcal{H}}_{t-1}\right]\right)$ corresponds to the bias introduced from the randomness in sampling $a_{t}$ from $q_{t}$.
Once again, the analyses of these two terms follow the same principle. We briefly introduce the analysis of the first term for the sake of simplicity. Details can be found in the appendix.

To bound the first term $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left(\mathbb{E}
\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]-
\ell_{t,c}(\pi_{c})\right)$, we will use the key observation mentioned at the beginning of this section: different epochs in Algorithm 1 are only weakly dependent on each other. To use this observation rigorously, we introduce an important technical tool.
With a slight abuse of notation, we define a filtration $\left\{\operatorname{\mathcal{H}}_{e}\right\}_{e}$, in which for each epoch $e$, the $\sigma$-algebra $\operatorname{\mathcal{H}}_{e}$ is generated by all randomness in epochs $1,\dots,e-1$ and the randomness in $\operatorname{\mathcal{T}_{e}^{\ell}}$. That is, the $\sigma$-algebra $\operatorname{\mathcal{H}}_{e}$ is generated precisely by the context $c_{t}$, the random seed used in sampling $a_{t}\sim q_{t,c_{t}}$, and the random seed used in sampling $S_{t}\sim\mathcal{B}\left(\frac{s_{e,c_{t}}(a_{t})}{2q_{t,c_{t}}(a_{t})}\right)$ for $t\leq(e-1)L$ and $t\in\operatorname{\mathcal{T}_{e}^{\ell}}$.
Note that for each epoch $e$, the $\sigma$-algebra $\operatorname{\mathcal{H}}_{e}$ excludes the randomness in $\operatorname{\mathcal{T}_{e}^{f}}$. This exclusion is crucial for characterizing the weak dependence structure between epochs.

Given this filtration, we consider the cumulative bias in each epoch. For each epoch $e$, we define a random variable

$$ $\operatorname{\mathrm{Bias5}}_{e}\triangleq\sum_{t\in\operatorname{\mathcal{T} _{e}^{\ell}}}\sum_{c}\Pr(c)\left(\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big {|}\operatorname{\mathcal{H}}_{t-1}\right]-\ell_{t,c}(\pi_{c})\right).$ $$

Then the first term $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left(\mathbb{E}
\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]-
\ell_{t,c}(\pi_{c})\right)$ is exactly $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}$.
Our key observation is that, not only

$$ $\mathbb{E}\left[\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c) \left(\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H }}_{t-1}\right]-\ell_{t,c}(\pi_{c})\right)\right]\leq 0$ $$

as shown in  Schneider and Zimmert (), but also

$$ $\sum_{e}\mathbb{E}\left[\operatorname{\mathrm{Bias5}}_{e}|\operatorname{ \mathcal{H}}_{e}\right]\sim-\sum_{e}\frac{\gamma}{f_{e}(\pi_{c})+\gamma}.$ $$

This key observation improves the inequality in  Schneider and Zimmert () in two ways.
Firstly, our bound holds for conditional expectations across epochs, which opens the door to applying martingale concentration inequalities across epochs.
Secondly, our new decomposition improves the upper bound from 0 0 to $-\sum_{e}\frac{\gamma}{f_{e}(\pi_{c})+\gamma}$. This improvement is essential for deriving a high probability bound.

Given the new bound $\sum_{e}\mathbb{E}\left[\operatorname{\mathrm{Bias5}}_{e}|\operatorname{
\mathcal{H}}_{e}\right]\sim-\sum_{e}\frac{\gamma}{f_{e}(\pi_{c})+\gamma}$, we only need to bound the deviation $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}-\mathbb{E}\left[\operatorname{
\mathrm{Bias5}}_{e}|\operatorname{\mathcal{H}}_{e}\right]$ to get an upper bound on $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}$.
However, we cannot directly apply standard martingale concentration inequalities to $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}-\mathbb{E}\left[\operatorname{
\mathrm{Bias5}}_{e}|\operatorname{\mathcal{H}}_{e}\right]$.
This is because we need to assume that the random variable $|\operatorname{\mathrm{Bias5}}_{e}|\leq 2L$ almost surely to get a tight enough concentration bound when applying standard martingale concentration inequalities.
However, this is not the case. The random variable $\operatorname{\mathrm{Bias5}}_{e}$ exceeds the constant $2L$ with a small but positive probability. This unboundness prevents us from getting a tight enough concentration bound when applying standard martingale concentration inequalities.

To overcome this problem, we consider the indicator function

$$ $F_{e}\triangleq\operatorname{\mathbbm{1}}\left(\forall a,\left|\widehat{f}_{e} (a)-f_{e}(a)\right|\leq 2\max\left\{\sqrt{\frac{f_{e}(a)\iota}{L}},\frac{\iota }{L}\right\}\right)$ $$

defined in  Schneider and Zimmert ().
We show that we also have $\sum_{e}\mathbb{E}\left[\operatorname{\mathrm{Bias5}}_{e}F_{e}|\operatorname{
\mathcal{H}}_{e}\right]\sim-\sum_{e}\frac{\gamma}{f_{e}(\pi_{c})+\gamma}$ and that the random variable $|\operatorname{\mathrm{Bias5}}_{e}F_{e}|\leq 2L$ almost surely.
Thus, we can use standard martingale concentration inequalities to get a tight enough concentration bound on $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}F_{e}-\mathbb{E}\left[\operatorname{
\mathrm{Bias5}}_{e}F_{e}|\operatorname{\mathcal{H}}_{e}\right]$ and further bound $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}F_{e}$.
Finally, we have that $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}F_{e}=\sum_{e}\operatorname{\mathrm{
Bias5}}_{e}$ with high probability.
Thus, a high probability bound on $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}F_{e}$ transfers to a high probability bound on $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}$.

## 4 Conclusions

We reanalyze the algorithm proposed by Schneider and Zimmert () and show that it actually achieves near-optimal regret with *high probability* for the cross-learning contextual bandits problem when the losses are chosen adversarially but the contexts are i.i.d. sampled from an unknown distribution. Our key technique is utilizing the weak dependency structure between different epochs for an algorithm executing over multiple epochs. It is of interest to investigate that whether this techniques is applicable for deriving high probability bounds for algorithms executing over multiple epochs in other problems.

## Appendix A Useful Lemmas

###### Lemma 1 (Freedman’s Inequality) .

Fix any $\lambda>0$ and $\delta\in(0,1)$. Let $X_{t}$ be a random process with respect to a filtration $\mathcal{F}_{t}$ such that $\mu_{t}=\mathbb{E}\left[X_{t}\mid\mathcal{F}_{t-1}\right]$ and $V_{t}=\mathbb{E}\left[X_{t}^{2}\mid\mathcal{F}_{t-1}\right]$, and satisfying $\lambda X_{t}\leq 1$. Then, with probability at least $1-\delta$, we have for all $t$,

$$ $\sum_{s=1}^{t}X_{s}-\mu_{s}\leq\lambda\sum_{s=1}^{t}V_{s}+\frac{\log(1/\delta) }{\lambda}.$ $$

The next lemma is about the following family of indicator functions.

###### Definition 1 .

For each epoch $e$, we define the following two indicator functions:

$$ $F_{e}\triangleq\operatorname{\mathbbm{1}}\left(\forall a,\left|\widehat{f}_{e} (a)-f_{e}(a)\right|\leq 2\max\left\{\sqrt{\frac{f_{e}(a)\iota}{L}},\frac{\iota }{L}\right\}\right)$ $$

and

$$ $L_{e}\triangleq\operatorname{\mathbbm{1}}\left(\max_{c\in[C],a\in[K]}\sum_{t \in\mathcal{T}_{e}}\tilde{\ell}_{t,c}(a)\leq L+\frac{\iota}{\gamma}\right).$ $$

We further define the following indicator function:

$$ $G=\prod_{e=1}^{T/L}F_{e}L_{e}.$ $$

###### Lemma 2 (Lemma 6 and Lemma 7, Schneider and Zimmert ( 2023 ) ) .

For any epoch $e$, the event $F_{e}$ holds with probability at least $1-2K\exp(-\iota)$, and the event $L_{e}$ holds with probability at least $1-K\exp(-\iota)$. Furthermore, the event $G$ holds with probability at least $1-3K(T/L)\exp(-\iota).$

###### Lemma 3 (Lemma 8, Schneider and Zimmert ( 2023 ) ) .

Let $\gamma\geq\frac{4\iota}{L}$, then under event $F_{e}$, we have that

$$ $\frac{1}{2}\leq\frac{f_{e}(a)+\gamma}{\hat{f}_{e}(a)+\frac{3}{2}\gamma}\leq 2.$ $$

The next lemma is about the following auxiliary probability vector.

###### Definition 2 .

For each epoch $e$ and each time step $t\in\mathcal{T}_{e}$, we define

$$ $\widetilde{p}_{t,c}\triangleq\operatorname*{arg\,min}_{p\in\Delta([K])}\left \langle p,\sum_{e^{\prime}=1}^{e-1}\sum_{s\in\mathcal{T}_{e^{\prime}}}\widehat {\ell}_{sc}+\sum_{t^{\prime}\in\mathcal{T}_{e},t^{\prime}<t}\tilde{\ell}_{t^{ \prime}c}\right\rangle-\eta^{-1}F(p)$ $$

where $F(p)=\sum_{i=1}^{K}p_{i}\log(p_{i})$ is the unnormalized negative entropy.

It is easy to see that $\widetilde{p}_{t,c}\propto s_{e+1,c}\circ\exp\left(-\eta\sum_{t^{\prime}\in
\mathcal{T}_{e},t^{\prime}<t}\tilde{\ell}_{t^{\prime}c}\right).$

###### Lemma 4 (Lemma 9, Schneider and Zimmert ( 2023 ) ) .

If $\gamma\geq\frac{4\iota}{L}$ and $\eta\leq\frac{\log(2)}{5L}$, then under event $G$, we have for all $t\in\mathcal{T}_{e},a\in[K],c\in[C]$ simultaneously

$$ $\displaystyle 2s_{e,c}(a)\geq p_{t,c}(a)\geq s_{e,c}(a)/2\qquad\text{and} \qquad 2s_{e,c}(a)\geq\tilde{p}_{t,c}(a)\geq s_{e,c}(a)/2\,.$ $$

This implies that

$$ $\displaystyle\mathbb{E}_{c\sim\nu}[p_{t,c}(a)]\leq 4f_{e}(a)\qquad\text{and} \qquad\mathbb{E}_{c\sim\nu}[\tilde{p}_{t,c}(a)]\leq 4f_{e}(a)\,.$ $$

In addition, this implies that $q_{t}=p_{t}$ for all $t\in\mathcal{T}_{e}$.

###### Definition 3 .

We define $p_{t}(a)\triangleq\mathbb{E}_{c\sim\nu}[p_{t,c}(a)]$ and $\tilde{p}_{t}(a)\triangleq\mathbb{E}_{c\sim\nu}[\tilde{p}_{t,c}(a)]$ for each time step $t$ and each arm $a$.

###### Lemma 5 (Lemma 10, Schneider and Zimmert ( 2023 ) ) .

If $\gamma\geq\frac{16\iota}{L}$ and $\exp(-\iota)\leq\frac{\gamma}{8K}$, then

$$ $-\frac{\gamma}{f_{e}(a)}\leq\mathbb{E}\left[\frac{f_{e}\left(a\right)-\hat{f}_ {e}\left(a\right)-\frac{1}{2}\gamma}{\hat{f}_{e}\left(a\right)+\frac{3}{2} \gamma}F_{e}\Big{|}\operatorname{\mathcal{H}}_{e-1}\right]\leq 0.$ $$

###### Lemma 6 .

For any $\eta\leq\frac{\gamma}{2(2L\gamma+\iota)},\gamma\geq\frac{16\iota}{L},\iota\geq
\log(8K/\gamma)$, we have

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} -\widetilde{p}_{t,c},\tilde{\ell}_{t,c}-\widehat{\ell}_{t,c}\right\rangle G \leq\frac{98KT\iota}{L}+\frac{\gamma^{2}LKT}{\iota}.$ $$

###### Proof.

The proof of Lemma 6 is contained in the analysis of the $\operatorname{\mathbf{bias}}_{3}$ term in Schneider and Zimmert ().
∎

###### Lemma 7 .

Decomposing all time steps into consecutive pairs, specifically, decomposing $\{1,2,\dots,T\}$ into $\{(1,2),(3,4),(5,6),\dots,(t-1,t),\dots,(T-1,T)\}$.
Constructing a surrogate loss sequence $\{\tilde{\ell}_{s}\}_{s=1}^{\frac{T}{2}}$ such that for each surrogate time step $s$ the loss vector $\tilde{\ell}_{s}$ is uniformly sampled from the pair of true loss vector $(\ell_{2s-1},\ell_{2s})$. Denote the time step sampled from the pair $(2s-1,2s)$ as $s_{\ell}$.
For any constant $\delta\in(0,1)$ and any bandit algorithm such that in each pair of time steps $(t-1,t)$, the algorithm takes actions $a_{t-1}$ and $a_{t}$ from the same distribution $p_{t-1}=p_{t}$, we have

$$ $\sum_{t=1}^{T}\left(\ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}(\pi_{c_{t}})\right) \leq 2\sum_{s=1}^{\frac{T}{2}}\left(\tilde{\ell}_{s,c_{s_{\ell}}}(a_{s_{\ell}} )-\tilde{\ell}_{s,c_{s_{\ell}}}(\pi_{c_{s_{\ell}}})\right)+2\sqrt{T\log(\frac{ 1}{\delta})}$ $$

with probability at least $1-\delta$.

###### Proof of lemma 7 .

Consider the sequence of random variable $\{Y_{s}\}_{s=1}^{\frac{T}{2}}$ such that

$$ $\displaystyle Y_{s}=$ $\displaystyle\ell_{2s-1,c_{2s-1}}(a_{2s-1})-\ell_{2s-1,c_{2s-1}}(\pi_{c_{2s-1}})$ $\displaystyle+\ell_{2s,c_{2s}}(a_{2s})-\ell_{2s,c_{2s}}(\pi_{c_{2s}})$ $\displaystyle-2\left(\tilde{\ell}_{s,c_{s_{\ell}}}(a_{s_{\ell}})-\tilde{\ell}_ {s,c_{s_{\ell}}}(\pi_{c_{s_{\ell}}})\right).$ $$

Consider the filtration $\{\tilde{H}_{s}\}_{s=1}^{\frac{T}{2}}$ such that for each $s$ the $\sigma$-field $\tilde{H}_{s}$ is generated by the randomness within $c_{t}$ and $a_{t}$ for $t\leq 2s$ and the randomness within sampling from pair $(2\tau-1,2\tau)$ for each $\tau\leq s$.
It is easy to see that the sequence$\{Y_{s}\}_{s=1}^{\frac{T}{2}}$ forms a martingale difference sequence adapted to the filtration $\{\tilde{H}_{s}\}_{s=1}^{\frac{T}{2}}$. Moreover, it is also easy to see that $|Y_{s}|\leq 2$. Using Azuma-Hoeffding’s inequality, for any constant $\delta\in(0,1)$, we have

$$ $\sum_{s=1}^{\frac{T}{2}}Y_{s}\leq 2\sqrt{T\log(\frac{1}{\delta})}$ $$

with probability at least $1-\delta$.
This completes the proof of the lemma.
∎

###### Lemma 1 (Freedman’s Inequality) .

###### Definition 1 .

###### Lemma 2 (Lemma 6 and Lemma 7, Schneider and Zimmert ( 2023 ) ) .

###### Lemma 3 (Lemma 8, Schneider and Zimmert ( 2023 ) ) .

###### Definition 2 .

###### Lemma 4 (Lemma 9, Schneider and Zimmert ( 2023 ) ) .

###### Definition 3 .

###### Lemma 5 (Lemma 10, Schneider and Zimmert ( 2023 ) ) .

###### Lemma 6 .

###### Proof.

###### Lemma 7 .

###### Proof of lemma 7 .

## Appendix B Detailed Proof of Theorem 1

### B.1 Decomposition

As we mentioned in Section 3.2, we decompose the regret as

$$ $\displaystyle\operatorname{\mathrm{Reg}}(\pi)$ $\displaystyle=\underbrace{\sum_{t=1}^{T}\ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}( \pi_{c_{t}})-2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\ell_{t,c_{t}}(a_{t} )-\ell_{t,c_{t}}(\pi_{c_{t}})}_{\operatorname{\mathbf{bias}}_{1}}$ $\displaystyle+$ $\displaystyle\underbrace{2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\left( \ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}(\pi_{c_{t}})-\sum_{c}\Pr(c)\langle p_{t,c }-\pi_{c},\ell_{t,c}\rangle\right)}_{\operatorname{\mathbf{bias}}_{2}}$ $\displaystyle+$ $\displaystyle\underbrace{2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c} \Pr(c)\langle p_{t,c}-\pi_{c},\hat{\ell}_{t,c}\rangle}_{\textbf{ftrl}}+ \underbrace{2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\ell_{t,c}-\tilde{\ell}_{t,c}\right\rangle}_{\operatorname{ \mathbf{bias}}_{3}}$ $\displaystyle+$ $\displaystyle\underbrace{2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c} \Pr(c)\left\langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\right\rangle}_{ \operatorname{\mathbf{bias}}_{4}}+\underbrace{2\sum_{t\in\operatorname{ \mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle\pi_{c},\hat{\ell}_{t,c}-\ell_{t ,c}\right\rangle}_{\operatorname{\mathbf{bias}}_{5}}.$ $$

We bound these terms one by one.

The $\operatorname{\mathbf{bias}}_{1}$, $\operatorname{\mathbf{bias}}_{2}$, ftrl, and $\operatorname{\mathbf{bias}}_{3}$ terms are not hard to bound. The terms of interest to bound are $\operatorname{\mathbf{bias}}_{4}$ ans $\operatorname{\mathbf{bias}}_{5}$. We first bound these two terms. In these two terms, the $\operatorname{\mathbf{bias}}_{5}$ term is the one easier to bound. We first bound $\operatorname{\mathbf{bias}}_{5}$ to provide some intuition for our readers.

### B.2 Upper Bounding 𝐛𝐢𝐚𝐬 5 subscript 𝐛𝐢𝐚𝐬 5 \operatorname{\mathbf{bias}}_{5} bold_bias start_POSTSUBSCRIPT 5 end_POSTSUBSCRIPT

We first bound the fifth term $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle\pi_{c},
\hat{\ell}_{t,c}-\ell_{t,c}\right\rangle$.
We decompose the fifth term into two components:

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle\pi_{c},\hat{\ell}_{t,c}-\ell_{t,c}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \hat{\ell}_{t,c}(\pi_{c})-\ell_{t,c}(\pi_{c})\right)$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t- 1}\right]-\ell_{t,c}(\pi_{c})\right)$ $\displaystyle+\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right).$ $$

We bound these two components separately.

For each epoch $e$, we define a random variable

$$ $\operatorname{\mathrm{Bias5}}_{e}\triangleq\sum_{t\in\operatorname{\mathcal{T} _{e}^{\ell}}}\sum_{c}\Pr(c)\left(\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big {|}\operatorname{\mathcal{H}}_{t-1}\right]-\ell_{t,c}(\pi_{c})\right).$ $$

We rewrite the term $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left(\mathbb{E}
\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]-
\ell_{t,c}(\pi_{c})\right)$ as $\sum_{e=1}^{T/L}\operatorname{\mathrm{Bias5}}_{e}$.
Recall our key observation: different epochs are only weakly dependent on each other. We bound the summation over epochs $\sum_{e=1}^{T/L}\operatorname{\mathrm{Bias5}}_{e}$ by leveraging the weak dependence structure between $\left\{\operatorname{\mathrm{Bias5}}_{e}\right\}_{e}$.

The sequence of random variables $\{\operatorname{\mathrm{Bias5}}_{e}\}_{e}$ has
the following properties:

- 1.
For each epoch $e$, the random variable $\operatorname{\mathrm{Bias5}}_{e}$ is measurable under $\sigma$-algebra $\operatorname{\mathcal{H}}_{e}$.
- 2.
For each epoch $e$, we have
$\displaystyle\mathbb{E}\left[\operatorname{\mathrm{Bias5}}_{e}\cdot F_{e}\big{
|}\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle=$
$\displaystyle\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}
\ell_{t,c}(\pi_{c})\mathbb{E}\left[\left(\frac{f_{e}(\pi_{c})}{\hat{f}_{e}(\pi
_{c})+\frac{3}{2}\gamma}-1\right)F_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}
\right].$
We further have
$\displaystyle\mathbb{E}\left[\left(\frac{f_{e}(\pi_{c})}{\hat{f}_{e}(\pi_{c})+
\frac{3}{2}\gamma}-1\right)F_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left(\frac{f_{e}(\pi_{c})}{\hat{f}_{e}(\pi_{c})+
\frac{3}{2}\gamma}-\frac{f_{e}(\pi_{c})}{f_{e}(\pi_{c})+\gamma}+\frac{f_{e}(
\pi_{c})}{f_{e}(\pi_{c})+\gamma}-1\right)F_{e}\big{|}\operatorname{\mathcal{H}
}_{e-1}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\frac{f_{e}(\pi_{c})}{f_{e}(\pi_{c})+\gamma}\frac
{\left(f_{e}(\pi_{c})-\hat{f}_{e}(\pi_{c})-\frac{1}{2}\gamma\right)}{\hat{f}_{
e}(\pi_{c})+\frac{3}{2}\gamma}F_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}
\right]-\frac{\gamma}{f_{e}(\pi_{c})+\gamma}\mathbb{E}\left[F_{e}\big{|}
\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle\leq$
$\displaystyle-\frac{\gamma}{f_{e}(\pi_{c})+\gamma}\mathbb{E}\left[F_{e}\big{|}
\operatorname{\mathcal{H}}_{e-1}\right]$
(Lemma 5)
$\displaystyle\leq$
$\displaystyle-\frac{\gamma}{f_{e}(\pi_{c})+\gamma}\left(1-2K\exp(-\iota)\right).$
(Lemma 2)
Thus we have
$\displaystyle\mathbb{E}\left[\operatorname{\mathrm{Bias5}}_{e}\cdot F_{e}\big{
|}\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle\leq$
$\displaystyle-\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}
\ell_{t,c}(\pi_{c})\frac{\gamma}{f_{e}(\pi_{c})+\gamma}\left(1-2K\exp(-\iota)
\right).$
- 3.
For each epoch $e$, we have
$\displaystyle\operatorname{\mathrm{Bias5}}_{e}F_{e}$
$\displaystyle\leq\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}
}\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t
-1}\right]F_{e}$
$\displaystyle=\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}
\ell_{t,c}(\pi_{c})\frac{f_{e}(\pi_{c})}{\hat{f}_{e}(\pi_{c})+\frac{3}{2}
\gamma}F_{e}$
$\displaystyle\leq\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}
}\ell_{t,c}(\pi_{c})\frac{2f_{e}(\pi_{c})}{f_{e}(\pi_{c})+\gamma}$
(Lemma 3)
$\displaystyle\leq 2L=\frac{32\iota}{\gamma}.$
- 4.
For each epoch $e$, we have
$\displaystyle\mathbb{E}\left[(\operatorname{\mathrm{Bias5}}_{e}F_{e})^{2}\big{
|}\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left(\sum_{c}\Pr(c)\sum_{t\in\operatorname{
\mathcal{T}_{e}^{\ell}}}\ell_{t,c}(\pi_{c})\frac{f_{e}(\pi_{c})-\hat{f}_{e}(
\pi_{c})-\frac{3}{2}\gamma}{\hat{f}_{e}(\pi_{c})+\frac{3}{2}\gamma}F_{e}\right
)^{2}\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle\leq\sum_{c}\Pr(c)\mathbb{E}\left[\left(\sum_{t\in\operatorname{
\mathcal{T}_{e}^{\ell}}}\ell_{t,c}(\pi_{c})\frac{f_{e}(\pi_{c})-\hat{f}_{e}(
\pi_{c})-\frac{3}{2}\gamma}{\hat{f}_{e}(\pi_{c})+\frac{3}{2}\gamma}F_{e}\right
)^{2}\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle=\sum_{c}\Pr(c)(\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}
\ell_{t,c})^{2}\mathbb{E}\left[\left(\frac{f_{e}(\pi_{c})-\hat{f}_{e}(\pi_{c})
-\frac{3}{2}\gamma}{\hat{f}_{e}(\pi_{c})+\frac{3}{2}\gamma}F_{e}\right)^{2}
\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle\leq L\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell
}}}\ell_{t,c}\mathbb{E}\left[\left(\frac{f_{e}(\pi_{c})-\hat{f}_{e}(\pi_{c})-
\frac{3}{2}\gamma}{\hat{f}_{e}(\pi_{c})+\frac{3}{2}\gamma}F_{e}\right)^{2}\big
{|}\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle\leq 4L\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{
\ell}}}\ell_{t,c}\mathbb{E}\left[\left(\frac{f_{e}(\pi_{c})-\hat{f}_{e}(\pi_{c
})-\frac{3}{2}\gamma}{f_{e}(\pi_{c})+\gamma}F_{e}\right)^{2}\big{|}
\operatorname{\mathcal{H}}_{e-1}\right]$
(Lemma 3)
$\displaystyle\leq\sum_{c}\Pr(c)\frac{4L}{(f_{e}(\pi_{c})+\gamma)^{2}}\sum_{t
\in\operatorname{\mathcal{T}_{e}^{\ell}}}\ell_{t,c}(\pi_{c})\mathbb{E}\left[
\left(f_{e}(\pi_{c})-\hat{f}_{e}(\pi_{c})-\frac{3}{2}\gamma\right)^{2}\big{|}
\operatorname{\mathcal{H}}_{e-1}\right]$
$\displaystyle=\sum_{c}\Pr(c)\frac{4L}{(f_{e}(\pi_{c})+\gamma)^{2}}\sum_{t\in
\operatorname{\mathcal{T}_{e}^{\ell}}}\ell_{t,c}(\pi_{c})\left(\mathbb{E}\left
[\left(f_{e}(\pi_{c})-\hat{f}_{e}(\pi_{c})\right)^{2}\big{|}\operatorname{
\mathcal{H}}_{e-1}\right]+\frac{9}{4}\gamma^{2}\right)$
$\displaystyle\leq\sum_{c}\Pr(c)\frac{4L}{(f_{e}(\pi_{c})+\gamma)^{2}}\sum_{t
\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{t\in\operatorname{\mathcal{T}_{
e}^{\ell}}}\ell_{t,c}(\pi_{c})\left(\frac{f_{e}(\pi_{c})}{L}+\frac{9}{4}\gamma
^{2}\right)$
$\displaystyle\leq 4\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell
}}}\ell_{t,c}(\pi_{c})\left(\frac{1}{f_{e}(\pi_{c})+\gamma}+\frac{9L\gamma}{4(
f_{e}(\pi_{c})+\frac{3}{2}\gamma)}\right)$
$\displaystyle\leq 4\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell
}}}\ell_{t,c}(\pi_{c})\frac{36\iota}{f_{e}(\pi_{c})+\gamma}.$

Given these properties, we use Freedman’s inequality to get that for any $0<\lambda<\frac{\gamma}{32\iota}$, with probability at least $1-\delta$, we have

$$ $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}F_{e}-\mathbb{E}[\operatorname{ \mathrm{Bias5}}_{e}F_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}]\leq 4\lambda \sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\ell_{t,c}(\pi_{ c})\frac{36\iota}{f_{e}(\pi_{c})+\frac{3}{2}\gamma}+\frac{\log(1/\delta)}{ \lambda}.$ $$

We further have that event $\{\sum_{e}\operatorname{\mathrm{Bias5}}_{e}F_{e}=\sum_{e}\operatorname{\mathrm
{Bias5}}_{e}\}$ holds if event $G$ holds.
Combining these two facts, we get that the inequality

$$ $\sum_{e}\operatorname{\mathrm{Bias5}}_{e}-\mathbb{E}[\operatorname{\mathrm{ Bias5}}_{e}F_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}]\leq 4\lambda\sum_{c} \Pr(c)\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\ell_{t,c}(\pi_{c})\frac {36\iota}{f_{e}(\pi_{c})+\gamma}+\frac{\log(1/\delta)}{\lambda}$ $$

holds with probability at least $\Pr(G)-\delta$.

We now bound the second component

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left(\hat{\ell}_{t, c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{ \mathcal{H}}_{t-1}\right]\right).$ $$

The second term $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left(\hat{\ell}_{t,
c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{
\mathcal{H}}_{t-1}\right]\right)$ has the following properties:

- 1.
The sequence of random variables $\left\{\sum_{c}\Pr(c)\left(\hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell
}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right)\right\}_
{t\in\operatorname{\mathcal{T}^{\ell}}}$ forms a martingale difference sequence with respect to the tfiltration $\{\operatorname{\mathcal{H}}_{t}\}_{t}$.
- 2.
Each random variable $\sum_{c}\Pr(c)\left(\hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}
(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right)$ satisfies $\left|\sum_{c}\Pr(c)\left(\hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}
_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right)\right|
\leq\frac{1}{\gamma}$.
- 3.
Each random variable $\sum_{c}\Pr(c)\left(\hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}
(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right)$ satisfies
$\displaystyle\mathrm{Var}\left[\sum_{c}\Pr(c)\hat{\ell}_{t,c}(\pi_{c})\big{|}
\operatorname{\mathcal{H}}_{t-1}\right]$
$\displaystyle\leq\sum_{c}\Pr(c)\mathrm{Var}\left[\hat{\ell}_{t,c}(\pi_{c})\big
{|}\operatorname{\mathcal{H}}_{t-1}\right]$
$\displaystyle=\sum_{c}\Pr(c)\frac{f_{e}(\pi_{c})-f^{2}_{e}(\pi_{c})}{\left(
\hat{f}_{e}(\pi_{c})+\frac{3}{2}\gamma\right)^{2}}l_{t,c}(\pi_{c})^{2}$
$\displaystyle\leq\sum_{c}\Pr(c)\frac{f_{e}(\pi_{c})}{\left(\hat{f}_{e}(\pi_{c}
)+\frac{3}{2}\gamma\right)^{2}}l_{t,c}(\pi_{c}).$

Applying Freedman’s inequality to the sequence of random variables $\left\{\sum_{c}\Pr(c)\left(\hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell
}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right)\right\}_
{t\in\operatorname{\mathcal{T}^{\ell}}}$ , we get that for each $\delta\in(0,1)$ and each $0<\lambda<\gamma$, with probability at least $1-\delta$, we have

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right)$ $\displaystyle\leq$ $\displaystyle\lambda\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c) \frac{f_{e}(\pi_{c})}{\left(\hat{f}_{e}(\pi_{c})+\frac{3}{2}\gamma\right)^{2}} l_{t,c}(\pi_{c})+\frac{1}{\lambda}\log(\frac{1}{\delta}).$ $$

By assuming that event $G$ holds, we further get that with probability at least $\Pr(G)-\delta$, the following inequality holds:

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right)$ $\displaystyle\leq$ $\displaystyle 4\lambda\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr( c)\frac{f_{e}(\pi_{c})}{\left(f_{e}(\pi_{c})+\gamma\right)^{2}}l_{t,c}(\pi_{c} )+\frac{1}{\lambda}\log(\frac{1}{\delta}).$ ( Lemma 3 ) $$

Combining all previous inequalities, we get that for any $0<\lambda_{1}<\frac{\gamma}{32\iota}$ and $0<\lambda_{2}<\gamma$ , the following inequality holds with probability at least $\Pr(G)-2\delta$:

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle\pi_{c},\hat{\ell}_{t,c}-\ell_{t,c}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|}\operatorname{\mathcal{H}}_{t- 1}\right]-\ell_{t,c}(\pi_{c})\right)$ $\displaystyle+\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right)$ $\displaystyle=$ $\displaystyle\sum_{e}\operatorname{\mathrm{Bias5}}_{e}-\mathbb{E}[ \operatorname{\mathrm{Bias5}}_{e}F_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}]$ $\displaystyle+\sum_{e}\mathbb{E}\left[\operatorname{\mathrm{Bias5}}_{e}F_{e} \big{|}\operatorname{\mathcal{H}}_{e-1}\right]$ $\displaystyle+\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left( \hat{\ell}_{t,c}(\pi_{c})-\mathbb{E}\left[\hat{\ell}_{t,c}(\pi_{c})\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right)$ $\displaystyle\leq$ $\displaystyle 4\lambda_{1}\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}^{ \ell}}}\ell_{t,c}(\pi_{c})\frac{36\iota}{f_{e}(\pi_{c})+\gamma}+\frac{\log(1/ \delta)}{\lambda_{1}}$ $\displaystyle-\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\ell_{ t,c}(\pi_{c})\frac{\gamma}{f_{e}(\pi_{c})+\gamma}\left(1-2K\exp(-\iota)\right)$ $\displaystyle+4\lambda_{2}\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c} \Pr(c)\frac{f_{e}(\pi_{c})}{\left(f_{e}(\pi_{c})+\gamma\right)^{2}}l_{t,c}(\pi _{c})+\frac{1}{\lambda_{2}}\log(\frac{1}{\delta}).$ $$

Note that in the previous analysis, we combined two good events each happening with probability at least $\Pr(G)-\delta$. The combined good event happens with probability $\Pr(G)-2\delta$ rather than the vanilla union bound $1-2(1-\Pr(G)+\delta)$. This is because, in both events, the $\Pr(G)$ term comes from assuming event $G$ happens. Thus, in the combined event, we can simply assume event $G$ happens and count the corresponding bad event $G^{c}$ only once. We will use this small trick repeatedly in the following analysis.

We pick $\lambda_{1}=\frac{\gamma}{8\cdot 36\iota}$ and $\lambda_{2}=\frac{\gamma}{8}$ to get that the following inequality holds with probability at least $\Pr(G)-2\delta$:

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle\pi_{c},\hat{\ell}_{t,c}-\ell_{t,c}\right\rangle$ $\displaystyle\leq$ $\displaystyle 4\lambda_{1}\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}^{ \ell}}}\ell_{t,c}(\pi_{c})\frac{36\iota}{f_{e}(\pi_{c})+\gamma}+\frac{\log(1/ \delta)}{\lambda_{1}}$ $\displaystyle-\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\ell_{ t,c}(\pi_{c})\frac{\gamma}{f_{e}(\pi_{c})+\gamma}\left(1-2K\exp(-\iota)\right)$ $\displaystyle+4\lambda_{2}\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c} \Pr(c)\frac{f_{e}(\pi_{c})}{\left(f_{e}(\pi_{c})+\gamma\right)^{2}}l_{t,c}(\pi _{c})+\frac{1}{\lambda_{2}}\log(\frac{1}{\delta})$ $\displaystyle=$ $\displaystyle(\frac{8\cdot 36\iota}{\gamma}+\frac{8}{\gamma})\log(1/\delta)+ \sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\ell_{t,c}(\pi_{c}) \frac{\gamma}{f_{e}(\pi_{c})+\gamma}2K\exp(-\iota)$ $\displaystyle\leq$ $\displaystyle(\frac{8\cdot 36\iota}{\gamma}+\frac{8}{\gamma})\log(1/\delta)+KT \exp(-\iota).$ $$

### B.3 Upper Bounding 𝐛𝐢𝐚𝐬 4 subscript 𝐛𝐢𝐚𝐬 4 \operatorname{\mathbf{bias}}_{4} bold_bias start_POSTSUBSCRIPT 4 end_POSTSUBSCRIPT

We then bound the forth term $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c}
,\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\right\rangle$. Similar to the previous analysis, we decompose it as follows:

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right\rangle$ $\displaystyle+\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{ \ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right] \right\rangle.$ $$

We bound these two components separately.

Similar to the previous anlaysis, we decompose the first component

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{ \mathcal{H}}_{t-1}\right]\right\rangle$ $$

as

$$ $\sum_{e}\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right\rangle.$ $$

For each epoch $e$ we define a random variable

$$ $\operatorname{\mathrm{Bias4}}_{e}\triangleq\sum_{t\in\operatorname{\mathcal{T} _{e}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{ t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle.$ $$

We need to bound $\sum_{e}\operatorname{\mathrm{Bias4}}_{e}$.

We decompose $\sum_{e}\operatorname{\mathrm{Bias4}}_{e}$ as $\sum_{e}\operatorname{\mathrm{Bias4}}F_{e}L_{e}+\sum_{e}\operatorname{\mathrm{
Bias4}}_{e}(1-F_{e}L_{e})$.
As usual we have that $\sum_{e}\operatorname{\mathrm{Bias4}}_{e}(1-F_{e}L_{e})=0$ whenever event $G$ holds.
Thus we can focus on bounding $\sum_{e}\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}$.
Firstly we bound

$$ $\sum_{e}\mathbb{E}\left[\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}\big{|} \operatorname{\mathcal{H}}_{e-1}\right].$ $$

We have

$$ $\displaystyle\sum_{e}\mathbb{E}\left[\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{ e}\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$ $\displaystyle=$ $\displaystyle\sum_{e}\mathbb{E}\left[\sum_{t\in\operatorname{\mathcal{T}_{e}^{ \ell}}}\sum_{c}\Pr(c)\left\langle\tilde{p}_{t,c},\mathbb{E}\left[\tilde{\ell}_ {t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right \rangle F_{e}L_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$ $\displaystyle+\sum_{e}\mathbb{E}\left[\sum_{t\in\operatorname{\mathcal{T}_{e}^ {\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c}-\tilde{p}_{t,c},\mathbb{E}\left[ \tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1} \right]\right\rangle F_{e}L_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}\right].$ $$

By Lemma 6, the latter term

$$ $\sum_{e}\mathbb{E}\left[\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{ c}\Pr(c)\left\langle p_{t,c}-\tilde{p}_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c }-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle F _{e}L_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$ $$

is bounded by $\frac{98KT\iota}{L}+\frac{\gamma^{2}LKT}{\iota}.$
Furthermore, condition on $\operatorname{\mathcal{H}}_{e-1}$, the indicator function $F_{e}$ is effected only by randomness within time steps $t\in\operatorname{\mathcal{T}_{e}^{f}}$, thus the indicator function $F_{e}$ is conditional independent with the probability vector $\tilde{p}_{t,c}$.
We have

$$ $\displaystyle\sum_{e}\mathbb{E}\left[\sum_{t\in\operatorname{\mathcal{T}_{e}^{ \ell}}}\sum_{c}\Pr(c)\left\langle\tilde{p}_{t,c},\mathbb{E}\left[\tilde{\ell}_ {t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right \rangle F_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$ $\displaystyle=$ $\displaystyle\sum_{e}\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{c} \Pr(c)\left\langle\mathbb{E}\left[\tilde{p}_{t,c}\big{|}\operatorname{\mathcal {H}}_{e-1}\right],\mathbb{E}\left[(\tilde{\ell}_{t,c}-\hat{\ell}_{t,c})F_{e} \big{|}\operatorname{\mathcal{H}}_{e-1}\right]\right\rangle$ $\displaystyle\leq$ $\displaystyle\sum_{e}\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{c} \Pr(c)\sum_{a}\frac{\tilde{p}_{t,c}(a)\gamma}{f_{e}(a)}.$ ( Lemma 5 ) $$

By Lemma 4, whenever event $G$ holds, the ratio $\frac{\tilde{p}_{t,c}(a)}{f_{e}(a)}\leq 4.$ Thus we have

$$ $\sum_{e}\mathbb{E}\left[\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{ c}\Pr(c)\left\langle\tilde{p}_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{ \ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle F_{e} \big{|}\operatorname{\mathcal{H}}_{e-1}\right]\leq 4\gamma KT$ $$

whenever event $G$ holds.

We further have $\left|\left\langle\tilde{p}_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell
}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle\right|\leq
\frac{1}{\gamma}$.
Thus we have

$$ $\displaystyle\sum_{e}\mathbb{E}\left[\sum_{t\in\operatorname{\mathcal{T}_{e}^{ \ell}}}\sum_{c}\Pr(c)\left\langle\tilde{p}_{t,c},\mathbb{E}\left[\tilde{\ell}_ {t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right \rangle F_{e}(L_{e}-1)\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$ $\displaystyle\leq$ $\displaystyle\sum_{e}\mathbb{E}\left[\sum_{t\in\operatorname{\mathcal{T}_{e}^{ \ell}}}\sum_{c}\Pr(c)\frac{1}{\gamma}F_{e}(L_{e}-1)\big{|}\operatorname{ \mathcal{H}}_{e-1}\right]$ $\displaystyle\leq$ $\displaystyle\frac{1}{\gamma}\sum_{e}\mathbb{E}\left[\sum_{t\in\operatorname{ \mathcal{T}_{e}^{\ell}}}\sum_{c}\Pr(c)\left|L_{e}-1\right|\big{|}\operatorname {\mathcal{H}}_{e-1}\right]$ $\displaystyle\leq$ $\displaystyle\frac{K\exp(-\iota)T}{\gamma}.$ ( Lemma 2 ) $$

Thus we have

$$ $\displaystyle\sum_{e}\mathbb{E}\left[\sum_{t\in\operatorname{\mathcal{T}_{e}^{ \ell}}}\sum_{c}\Pr(c)\left\langle\tilde{p}_{t,c},\mathbb{E}\left[\tilde{\ell}_ {t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right \rangle F_{e}L_{e}\big{|}\operatorname{\mathcal{H}}_{e-1}\right]$ $\displaystyle\leq$ $\displaystyle 4\gamma KT+\frac{K\exp(-\iota)T}{\gamma}$ $$

whenever event $G$ holds.

Thus we have

$$ $\sum_{e}\mathbb{E}\left[\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}\big{|} \operatorname{\mathcal{H}}_{e-1}\right]\leq 4K\gamma T+\frac{K\exp(-\iota)T}{ \gamma}+\frac{98KT\iota}{L}+\frac{\gamma^{2}LKT}{\iota}$ $$

whenever event $G$ holds.

We then only need to bound the concentration term

$$ $\sum_{e}\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}-\mathbb{E}\left[ \operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}\big{|}\operatorname{\mathcal{H}}_{ e-1}\right].$ $$

For each random variable $\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}$, we have

$$ $\displaystyle\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{c}\Pr(c) \left\langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{| }\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle F_{e}L_{e}$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{c}\Pr(c) \sum_{a}p_{t,c}(a)f_{e}(a)\ell_{t,c}(a)\left(\frac{1}{f_{e}(a)+\gamma}-\frac{1 }{\hat{f}_{e}(a)+\frac{3}{2}\gamma}\right)F_{e}L_{e}$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{c}\Pr(c) \sum_{a}\tilde{p}_{t,c}(a)f_{e}(a)\ell_{t,c}(a)\frac{\hat{f}_{e}(a)-f_{e}(a)+ \frac{1}{2}\gamma}{(f_{e}(a)+\gamma)(\hat{f}_{e}(a)+\frac{3}{2}\gamma)}F_{e}L_ {e}.$ $$

Thus we have

$$ $\displaystyle\left|\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}\right|$ $\displaystyle\leq$ $\displaystyle\left|\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{c}\Pr (c)\sum_{a}\tilde{p}_{t,c}(a)f_{e}(a)\ell_{t,c}(a)\frac{\hat{f}_{e}(a)-f_{e}(a )+\frac{1}{2}\gamma}{(f_{e}(a)+\gamma)(\hat{f}_{e}(a)+\frac{3}{2}\gamma)} \right|F_{e}L_{e}$ $\displaystyle\leq$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{a}\tilde{p} _{t}(a)\left|\frac{\hat{f}_{e}(a)-f_{e}(a)+\frac{1}{2}\gamma}{\hat{f}_{e}(a)+ \frac{3}{2}\gamma}\right|F_{e}L_{e}$ $\displaystyle\leq$ $\displaystyle 8\sum_{t\in\operatorname{\mathcal{T}_{e}^{\ell}}}\sum_{a}\max \left\{\sqrt{\frac{f_{e}(a)\iota}{L}},\frac{\iota}{L}\right\}$ $\displaystyle\leq$ $\displaystyle 8L(\sqrt{\frac{K\iota}{L}}+\frac{K\iota}{L})$ $\displaystyle=$ $\displaystyle 8(\sqrt{KL\iota}+K\iota).$ $$

Applying Azuma-Hoeffding’s inequality to

$$ $\sum_{e}\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}-\mathbb{E}\left[ \operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}\big{|}\operatorname{\mathcal{H}}_{ e-1}\right],$ $$

we get that for any $\delta>0$, with probability at least $1-\delta$, we have

$$ $\displaystyle\sum_{e}\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}-\mathbb{E} \left[\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}\big{|}\operatorname{\mathcal {H}}_{e-1}\right]$ $\displaystyle\leq$ $\displaystyle 8(\sqrt{KL\iota}+K\iota)\sqrt{2\frac{T}{L}\log(\frac{\delta}{2})}$ $\displaystyle=$ $\displaystyle 8\left(\sqrt{2KT\iota\log(\frac{\delta}{2})}+\sqrt{2\frac{TK^{2} }{L}\iota\log(\frac{\delta}{2})}\right).$ $$

Thus we have

$$ $\displaystyle\sum_{e}\operatorname{\mathrm{Bias4}}_{e}F_{e}L_{e}$ $\displaystyle\leq$ $\displaystyle 4K\gamma T+\frac{K\exp(-\iota)T}{\gamma}+\frac{98KT\iota}{L}+ \frac{\gamma^{2}LKT}{\iota}$ $\displaystyle+8\left(\sqrt{2KT\iota\log(\frac{\delta}{2})}+\sqrt{2\frac{TK^{2} }{L}\iota\log(\frac{\delta}{2})}\right).$ $$

with probability at least $\Pr(G)-\delta$.

We then bound the second term

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{ \ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle.$ $$

For each time step $t\in\operatorname{\mathcal{T}_{e}^{\ell}}$, we define an indicator function

$$ $J_{t}\triangleq\operatorname{\mathbbm{1}}\left(\forall a,\tilde{p}_{t}(a)\leq 4 f_{e}(a)\right).$ $$

By Lemma 4, event $G$ implies $J_{t}$.

Similar to previous analysis, we decompose the first term as

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{ \ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{ \ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right] \right\rangle F_{e}J_{t}$ $\displaystyle+\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{ \ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right] \right\rangle(1-F_{e}J_{t}).$ $$

Since the auxiliary probability vector $\tilde{p}_{t,c}$ is determined at time $t-1$, the indicator function $J_{t}$ is also determined at time $t-1$.
Furthermore, the indicator function $F_{e}$ is determined at epoch $e-1$.
Thus the product of indicator functions $F_{e}J_{t}$ is measurable under filtration $\operatorname{\mathcal{H}}_{t-1}$. We have

$$ $\displaystyle\mathbb{E}\left[\sum_{c}\Pr(c)\left\langle p_{t,c},\tilde{\ell}_{ t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{ |}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle F_{e}J_{t}\big{|} \operatorname{\mathcal{H}}_{t-1}\right]$ $\displaystyle=$ $\displaystyle F_{e}J_{t}\mathbb{E}\left[\sum_{c}\Pr(c)\left\langle p_{t,c},( \tilde{\ell}_{t,c}-\hat{\ell}_{t,c})-\mathbb{E}\left[(\tilde{\ell}_{t,c}-\hat{ \ell}_{t,c})\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle\big{|} \operatorname{\mathcal{H}}_{t-1}\right]$ $\displaystyle=$ $\displaystyle 0.$ $$

Thus the sequence of random variables

$$ $\left\{\sum_{c}\Pr(c)\left\langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}- \mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{ \mathcal{H}}_{t-1}\right]\right\rangle F_{e}J_{t}\right\}_{t\in\operatorname{ \mathcal{T}^{\ell}}}$ $$

forms a martingale difference sequence under the filtration $\{\operatorname{\mathcal{H}}_{t}\}_{t}$.

We further have that the term

$$ $\sum_{c}\Pr(c)\left\langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb {E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_ {t-1}\right]\right\rangle F_{e}J_{t}$ $$

satisfies

$$ $\displaystyle\left|\sum_{c}\Pr(c)\left\langle p_{t,c},\tilde{\ell}_{t,c}-\hat{ \ell}_{t,c}-\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right\rangle\right|F_{e}J_{t}$ $\displaystyle\leq$ $\displaystyle\left|\sum_{c}\Pr(c)\sum_{a}p_{t,c}(a)\ell_{t,c}(a)\left(\frac{ \operatorname{\mathbbm{1}}(a_{t}=a)}{f_{e}(a)+\gamma}-\frac{f_{e}(a)}{f_{e}(a) +\gamma}\right)\right|F_{e}J_{t}$ $\displaystyle+\left|\sum_{c}\Pr(c)\sum_{a}p_{t,c}(a)\ell_{t,c}(a)\left(\frac{ \operatorname{\mathbbm{1}}(a_{t}=a)}{\hat{f}_{e}(a)+\frac{3}{2}\gamma}-\frac{f _{e}(a)}{\hat{f}_{e}(a)+\frac{3}{2}\gamma}\right)\right|F_{e}J_{t}$ $\displaystyle\leq$ $\displaystyle\sum_{c}\Pr(c)p_{t,c}(a_{t})\frac{\ell_{t,c}(a_{t})}{f_{e}(a_{t}) +\gamma}F_{e}J_{t}$ $\displaystyle+\sum_{c}\Pr(c)\sum_{a}p_{t,c}(a)\ell_{t,c}(a)\frac{f_{e}(a)}{f_{ e}(a)+\gamma}F_{e}J_{t}$ $\displaystyle+\sum_{c}\Pr(c)p_{t,c}(a_{t})\frac{\ell_{t,c}(a_{t})}{\hat{f}_{e} (a_{t})+\frac{3}{2}\gamma}F_{e}J_{t}$ $\displaystyle+\sum_{c}\Pr(c)\sum_{a}p_{t,c}(a)\ell_{t,c}(a)\frac{f_{e}(a)}{ \hat{f}_{e}(a)+\frac{3}{2}\gamma}F_{e}J_{t}$ $\displaystyle\leq$ $\displaystyle\left(\frac{p_{t}(a_{t})}{f_{e}(a_{t})+\gamma}+1+\frac{p_{t}(a_{t })}{\hat{f}_{e}(a_{t})+\frac{3}{2}\gamma}+\sum_{a}p_{t}(a)\frac{f_{e}(a)}{\hat {f}_{e}(a)+\frac{3}{2}\gamma}\right)F_{e}J_{t}$ $\displaystyle\leq$ $\displaystyle 4+1+8+2=15.$ ( Lemma 3 ) $$

Applying Azuma-Hoeffding’s inequality to the sequnece of random variables

$$ $\left\{\sum_{c}\Pr(c)\left\langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}- \mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{ \mathcal{H}}_{t-1}\right]\right\rangle F_{e}J_{t}\right\}_{t\in\operatorname{ \mathcal{T}^{\ell}}},$ $$

we get that for any $\delta>0$,
the inequality

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{ \ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle F_{e}J_ {t}\leq 15\sqrt{T\log(\frac{1}{\delta})}$ $$

holds with probability at least $1-\delta$.

On the other hand, note that event $G$ implies event $F_{e}J_{t}$, we get that

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{ \ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle(1-F_{e} J_{t})=0$ $$

whenever event $G$ holds. Thus we get that for any $\delta>0$, inequality

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{ \ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle\leq 15 \sqrt{T\log(\frac{1}{\delta})}$ $$

holds with probability at least $\Pr(G)-2\delta$.

Combining previous results, we get that the following inequality holds with probability at least $\Pr(G)-2\delta$:

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right\rangle$ $\displaystyle+\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\tilde{\ell}_{t,c}-\hat{\ell}_{t,c}-\mathbb{E}\left[\tilde{ \ell}_{t,c}-\hat{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\right\rangle$ $\displaystyle\leq$ $\displaystyle 4K\gamma T+\frac{K\exp(-\iota)T}{\gamma}+\frac{98KT\iota}{L}+ \frac{\gamma^{2}LKT}{\iota}$ $\displaystyle+8\left(\sqrt{2KT\iota\log(\frac{\delta}{2})}+\sqrt{2\frac{TK^{2} }{L}\iota\log(\frac{\delta}{2})}\right)$ $\displaystyle+15\sqrt{T\log(\frac{1}{\delta})}.$ $$

### B.4 Upper Bounding Remaining Terms

The remaining terms are the $\operatorname{\mathbf{bias}}_{1}$, $\operatorname{\mathbf{bias}}_{2}$, ftrl, and $\operatorname{\mathbf{bias}}_{3}$ terms. These terms are not hard to bound using techniques in standard EXP3-IX analysis (Neu, ). We write down these analyses in the sake of completeness.

#### B.4.1 Upper Bounding 𝐛𝐢𝐚𝐬 1 subscript 𝐛𝐢𝐚𝐬 1 \operatorname{\mathbf{bias}}_{1} bold_bias start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT

Applying Lemma 7 on the loss sequence used in calculating loss estimates, we get that

$$ $\sum_{t=1}^{T}\ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}(\pi_{c_{t}})-2\sum_{t\in \operatorname{\mathcal{T}^{\ell}}}\ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}(\pi_{c_ {t}})\leq 2\sqrt{T\log(\frac{1}{\delta})}.$ $$

#### B.4.2 Upper Bounding 𝐛𝐢𝐚𝐬 2 subscript 𝐛𝐢𝐚𝐬 2 \operatorname{\mathbf{bias}}_{2} bold_bias start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT

Here we bound the $\operatorname{\mathbf{bias}}_{2}$ term

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\left(\ell_{t,c_{t}}(a_{t})-\ell_{ t,c_{t}}(\pi_{c_{t}})-\sum_{c}\Pr(c)\langle p_{t,c}-\pi_{c},\ell_{t,c}\rangle \right).$ $$

Whenever event $G$ holds, we have $q_{t}=p_{t}$. Thus we assume event $G$ holds and replace the $\operatorname{\mathbf{bias}}_{2}$ term by

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\left(\ell_{t,c_{t}}(a_{t})-\ell_{ t,c_{t}}(\pi_{c_{t}})-\sum_{c}\Pr(c)\langle q_{t,c}-\pi_{c},\ell_{t,c}\rangle \right).$ $$

The new term have the following properties:

- •
The sequence of random variables
$\left\{\ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}(\pi_{c_{t}})-\sum_{c}\Pr(c)\langle
q
_{t,c}-\pi_{c},\ell_{t,c}\rangle\right\}_{t\in\operatorname{\mathcal{T}^{\ell}}}$
adapts to the filtration $\left\{\operatorname{\mathcal{H}}_{t}\right\}_{t\in\operatorname{\mathcal{T}^{
\ell}}}$.
- •
The sequence of random variables satisfies
$\mathbb{E}\left[\ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}(\pi_{c_{t}})-\sum_{c}\Pr(
c)\langle q_{t,c}-\pi_{c},\ell_{t,c}\rangle\big{|}\operatorname{\mathcal{H}}_{
t-1}\right]=0.$
- •
Each random variable satisfies $\ell_{t,c_{t}}(a_{t})-\ell_{t,c_{t}}(\pi_{c_{t}})-\sum_{c}\Pr(c)\langle q_{t,c
}-\pi_{c},\ell_{t,c}\rangle\in[-2,2]$.

By applying Azuma-Hoeffding inequality, we get that for any $\delta\in(0,1)$, the following inequality holds with probability at least $1-\delta$:

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\left(\ell_{t,c_{t}}( a_{t})-\ell_{t,c_{t}}(\pi_{c_{t}})-\sum_{c}\Pr(c)\langle q_{t,c}-\pi_{c},\ell_ {t,c}\rangle\right)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{T\log(\frac{1}{\delta})}$ $$

Thus the following inequality holds with probabiity at least $\Pr(G)-\delta$:

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\left(\ell_{t,c_{t}}(a_{t})-\ell_{ t,c_{t}}(\pi_{c_{t}})-\sum_{c}\Pr(c)\langle p_{t,c}-\pi_{c},\ell_{t,c}\rangle \right)\leq 2\sqrt{T\log(\frac{1}{\delta})}.$ $$

#### B.4.3 Upper Bounding ftrl

Here we bound the ftrl term

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\langle p_{t,c}-\pi_ {c},\hat{\ell}_{t,c}\rangle.$ $$

By the standard analysis of FTRL algorithms, the ftrl term satisfies

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\langle p _{t,c}-\pi_{c},\hat{\ell}_{t,c}\rangle$ $\displaystyle\leq$ $\displaystyle\sum_{c}\Pr(c)\left(\frac{1}{\eta}\log K+\frac{\eta}{2}\sum_{t\in \operatorname{\mathcal{T}^{\ell}}}\left\langle p_{t,c},\hat{\ell}^{2}_{t,c} \right\rangle\right).$ $$

Here $\hat{\ell}_{t,c}^{2}$ denotes the vector formed by squaring each component of $\hat{\ell}_{t,c}$.

By Lemma 3, under event $G$, we have $\hat{\ell}_{t,c}\leq 2\tilde{\ell}_{t,c}$. Thus assuming event $G$ holds, we can focus on upper bounding

$$ $\sum_{c}\Pr(c)\left(\frac{1}{\eta}\log K+2\eta\sum_{t\in\operatorname{\mathcal {T}^{\ell}}}\left\langle p_{t,c},\tilde{\ell}^{2}_{t,c}\right\rangle\right).$ $$

It suffices to upper bound $\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\left\langle p_{t,c}
,\tilde{\ell}^{2}_{t,c}\right\rangle.$ We have

$$ $\displaystyle\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\left \langle p_{t,c},\tilde{\ell}^{2}_{t,c}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}p_{t,c} (a_{t})\tilde{\ell}^{2}_{t,c}(a_{t})$ $\displaystyle=$ $\displaystyle\sum_{c}\Pr(c)\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}p_{t,c} (a_{t})\frac{\ell^{2}_{t,c}(a_{t})}{\left(f_{e}(a_{t})+\gamma\right)^{2}}$ $\displaystyle\leq$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)p_{t,c} (a_{t})\frac{1}{\left(f_{e}(a_{t})+\gamma\right)^{2}}$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\frac{p_{t}(a_{t})}{ \left(f_{e}(a_{t})+\gamma\right)^{2}}.$ $$

By Lemma 4, under event $G$, we have

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\frac{p_{t}(a_{t})}{\left(f_{e}(a_ {t})+\gamma\right)^{2}}\leq 2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\frac {1}{f_{e}(a_{t})+\gamma}.$ $$

We then focus on upper bounding $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\frac{1}{f_{e}(a_{t})+\gamma}.$

We have

- •
The sum of conditional expectations $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\mathbb{E}\left[\frac{1}{f_{e}(a_{
t})+\gamma}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]\leq KT.$
- •
Each term $\frac{1}{f_{e}(a_{t})+\gamma}\leq\frac{1}{\gamma}.$
- •
The sum of conditional quadratic expectations
$\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\mathbb{E}\left[\left
(\frac{1}{f_{e}(a_{t})+\gamma}\right)^{2}\big{|}\operatorname{\mathcal{H}}_{t-
1}\right]$
$\displaystyle=$
$\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{a}\frac{f_{e}(a
)}{\left(f_{e}(a)+\gamma\right)^{2}}$
$\displaystyle\leq$
$\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{a}\frac{1}{f_{e
}(a)+\gamma}.$

By Freedman’s inequality, we have that for any $\lambda\in(0,\gamma]$ and any $\delta\in(0,1)$, the following inequality holds with probability at least $1-\delta$:

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\frac{1}{f_{e}(a_{t})+\gamma}\leq \lambda\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{a}\frac{1}{f_{e}(a)+ \gamma}+\frac{1}{\lambda}\log(\frac{1}{\delta})+KT.$ $$

We pick $\lambda=\gamma$ to get that

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\frac{1}{f_{e}(a_{t})+\gamma}\leq 2 KT+\frac{1}{\gamma}\log(\frac{1}{\delta})$ $$

with probability at least $1-\delta$.

Substituting this inequality back, we get that the folowing inequality holds with probability at least $\Pr(G)-\delta$:

$$ $\displaystyle\sum_{c}\Pr(c)\left(\frac{1}{\eta}\log K+\frac{\eta}{2}\sum_{t\in \operatorname{\mathcal{T}^{\ell}}}\left\langle p_{t,c},\hat{\ell}^{2}_{t,c} \right\rangle\right)$ $\displaystyle\leq$ $\displaystyle\frac{1}{\eta}\log K+4\eta\sum_{t\in\operatorname{\mathcal{T}^{ \ell}}}\frac{1}{f_{e}(a_{t})+\gamma}$ $\displaystyle\leq$ $\displaystyle\frac{1}{\eta}\log K+4\eta\left(2KT+\frac{1}{\gamma}\log(\frac{1} {\delta})\right).$ $$

#### B.4.4 Upper Bounding 𝐛𝐢𝐚𝐬 3 subscript 𝐛𝐢𝐚𝐬 3 \operatorname{\mathbf{bias}}_{3} bold_bias start_POSTSUBSCRIPT 3 end_POSTSUBSCRIPT

Here we bound the $\operatorname{\mathbf{bias}}_{3}$ term

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\ell_{t,c}-\tilde{\ell}_{t,c}\right\rangle.$ $$

We decompose it as

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\ell_{t,c}-\tilde{\ell}_{t,c}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\ell_{t,c}-\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right\rangle$ $\displaystyle+\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|}\operatorname{ \mathcal{H}}_{t-1}\right]-\tilde{\ell}_{t,c}\right\rangle.$ $$

The first component satisfies

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\ell_{t,c}-\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|} \operatorname{\mathcal{H}}_{t-1}\right]\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\sum_{a }p_{t,c}(a)\ell_{t,c}(a)\frac{\gamma}{f_{e}(a)+\gamma}$ $\displaystyle\leq$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{a}p_{t}(a)\frac {\gamma}{f_{e}(a)+\gamma}.$ $$

Assuming event $G$ holds, we have

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{a}p_{t}(a)\frac {\gamma}{f_{e}(a)+\gamma}$ $\displaystyle\leq$ $\displaystyle 2\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{a}\gamma\leq 2 KT\gamma.$ ( Lemma 4 ) $$

We then bound the second component $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c}
,\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}
\right]-\tilde{\ell}_{t,c}\right\rangle.$
For each time step $t\in\operatorname{\mathcal{T}^{\ell}}$, we define an indicator function

$$ $L_{t}\triangleq\operatorname{\mathbbm{1}}\left(\forall a,p_{t}(a)\leq 4f_{e}(a )\right).$ $$

By Lemma 4, event $G$ implies event $L_{t}$.
Thus we have

$$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|}\operatorname{ \mathcal{H}}_{t-1}\right]-\tilde{\ell}_{t,c}\right\rangle$ $\displaystyle=$ $\displaystyle\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left \langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|}\operatorname{ \mathcal{H}}_{t-1}\right]-\tilde{\ell}_{t,c}\right\rangle L_{t}.$ $$

under event $G$. We then assume event $G$ holds and focus on upper bounding

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1} \right]-\tilde{\ell}_{t,c}\right\rangle L_{t}.$ $$

Since the probability vector $p_{t,c}$ is determined at time $t-1$, the indicator function $L_{t}$ is also determined at time $t-1$. Thus the summand random variable

$$ $\sum_{c}\Pr(c)\left\langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|} \operatorname{\mathcal{H}}_{t-1}\right]-\tilde{\ell}_{t,c}\right\rangle L_{t}$ $$

satisfies

$$ $\displaystyle\mathbb{E}\left[\sum_{c}\Pr(c)\left\langle p_{t,c},\mathbb{E} \left[\tilde{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]-\tilde{ \ell}_{t,c}\right\rangle L_{t}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\sum_{c}\Pr(c)\left\langle p_{t,c},\mathbb{E} \left[\tilde{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1}\right]-\tilde{ \ell}_{t,c}\right\rangle\big{|}\operatorname{\mathcal{H}}_{t-1}\right]L_{t}$ $\displaystyle=$ $\displaystyle 0.$ $$

Thus the sequence of random varialbes

$$ $\left\{\sum_{c}\Pr(c)\left\langle p_{t,c},\mathbb{E}\left[\tilde{\ell}_{t,c} \big{|}\operatorname{\mathcal{H}}_{t-1}\right]-\tilde{\ell}_{t,c}\right\rangle L _{t}\right\}_{t\in\operatorname{\mathcal{T}^{\ell}}}$ $$

forms a martingale difference sequence with respect to the filtration $\{\operatorname{\mathcal{H}}_{t}\}_{t\in\operatorname{\mathcal{T}^{\ell}}}$.

The summand random variable further satisfies

$$ $\displaystyle\sum_{c}\Pr(c)\left\langle p_{t,c},\tilde{\ell}_{t,c}\right \rangle L_{t}$ $\displaystyle=$ $\displaystyle\sum_{c}\Pr(c)p_{t,c}(a_{t})\frac{\ell_{t,c}(a_{t})}{f_{e}(a_{t}) +\gamma}L_{t}$ $\displaystyle\leq$ $\displaystyle\sum_{c}\Pr(c)p_{t,c}(a_{t})\frac{1}{f_{e}(a_{t})+\gamma}L_{t}$ $\displaystyle=$ $\displaystyle\frac{p_{t}(a_{t})}{f_{e}(a_{t})+\gamma}L_{t}$ $\displaystyle\leq$ $\displaystyle 4.$ $$

Then by Azuma-Hoeffding inequality, the following inequality holds with probability at least $1-\delta$:

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1} \right]-\tilde{\ell}_{t,c}\right\rangle L_{t}\leq 4\sqrt{T\log(\frac{1}{\delta })}.$ $$

Thus we have

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\mathbb{E}\left[\tilde{\ell}_{t,c}\big{|}\operatorname{\mathcal{H}}_{t-1} \right]-\tilde{\ell}_{t,c}\right\rangle\leq 4\sqrt{T\log(\frac{1}{\delta})}$ $$

with probability at least $\Pr(G)-\delta$.

Combining the first component and the second component, we get that

$$ $\sum_{t\in\operatorname{\mathcal{T}^{\ell}}}\sum_{c}\Pr(c)\left\langle p_{t,c} ,\ell_{t,c}-\tilde{\ell}_{t,c}\right\rangle\leq 4\sqrt{T\log(\frac{1}{\delta}) }+2KT\gamma$ $$

with probability at least $\Pr(G)-\delta$.

### B.5 Combining the pieces

Combining all previous arguments, we get that

$$ $\displaystyle\operatorname{\mathrm{Reg}}(\pi)$ $\displaystyle\leq$ $\displaystyle 2\sqrt{T\log(\frac{1}{\delta})}$ $\displaystyle+$ $\displaystyle 4\sqrt{T\log(\frac{1}{\delta})}$ $\displaystyle+$ $\displaystyle 2\frac{1}{\eta}\log K+8\eta\left(2KT+\frac{1}{\gamma}\log(\frac{ 1}{\delta})\right)$ $\displaystyle+$ $\displaystyle 8\sqrt{T\log(\frac{1}{\delta})}+4KT\gamma$ $\displaystyle+$ $\displaystyle 8K\gamma T+2\frac{K\exp(-\iota)T}{\gamma}+2\frac{98KT\iota}{L}+2 \frac{\gamma^{2}LKT}{\iota}$ $\displaystyle+$ $\displaystyle 16\left(\sqrt{2KT\iota\log(\frac{\delta}{2})}+2\sqrt{2\frac{TK^{ 2}}{L}\iota\log(\frac{\delta}{2})}\right)$ $\displaystyle+$ $\displaystyle 30\sqrt{T\log(\frac{1}{\delta})}$ $\displaystyle+$ $\displaystyle 2(\frac{8\cdot 36\iota}{\gamma}+2\frac{8}{\gamma})\log(1/\delta) +2KT\exp(-\iota)$ $$

with probability at least $\Pr(G)-8\delta$.

Taking $\iota=2\log(8KT)$, $L=\sqrt{\frac{\iota KT}{\log(K)}}=\widetilde{\Theta}(\sqrt{KT})$, $\gamma=\frac{16\iota}{L}=\widetilde{\Theta}(1/\sqrt{KT})$, and $\eta=\frac{\gamma}{2(2L\gamma+\iota)}=\widetilde{\Theta}(1/\sqrt{KT})$, it is easy to see that $\operatorname{\mathrm{Reg}}(\pi)=\widetilde{\Theta}(\sqrt{KT}\log\frac{1}{
\delta})$ with probability at least $1-\frac{1}{KT}-8\delta$ for any policy $\pi$ and any $\delta\in(0,1)$.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 1
questions: 1. What is the intuition behind the algorithm?
2. How the indicator function $F_e$ resolves the unbounded martingale inequalties?
soundness: 2
strengths: 1. The paper clearly presents the challenging point with detailed technical expressions and the novelty of the analysis.
summary: The paper proposes an algorithm that achieves high probability regret bound (which is stronger than the expected regret bound) for the cross-learning contextual bandits under unknown context distribution by developing refined martingale inequalities.
weaknesses: 1. The explanation is only focused on technical side without the explanation of the algorithm. I suggest authors to spend more time including more explanations and organizing the paper.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: While the result is good, I am uncertain about its significance because neither the problem nor the algorithm proposed are new. There are no extensions of this result, no experiments. I am not sure if this is standalone result is significant enough to be published at a premier conference.
soundness: 3
strengths: The paper proposes a new look at an existing problem and provides a completely novel analysis in their work. The ideas and techniques proposed are completely new and can be of independent interest. This is particularly true for the martingale concentration result.
summary: This paper addresses the challenge of achieving high-probability regret bounds in the adversarial contextual bandit framework, where the learner encounters varying contexts and must minimize cumulative loss over time. The focus is on "cross-learning" contextual bandits, where learners can observe losses for all possible contexts, not just the current one. 

Results leverage weak dependencies between epochs and refine existing martingale inequalities, by exploiting interdependencies in observations. This analysis ultimately shows that the algorithm is effective in adversarial settings, even with unknown context distributions.
weaknesses: See questions.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: please see weaknesses
soundness: 4
strengths: - The paper proves a high probability lower bound which is stronger than the in expectation bound in the literature.
- The analysis uses a nice observation that the different epochs in the algorithm are only weakly dependent which enables to prove a small bound for the cumulative bias across all epochs
- While standard martingale inequalities cannot directly upper bound the cumulative bias, a novel technique is proposed to address this
summary: The paper studies cross learning in contextual adversarial linear bandits where the learner observes the losses of all contexts in each round. Recent work in Schneider et al. proposed an algorithm with a regret upper bound only in expectation. The paper studies the same algorithm and proves that the regret upper bound holds with high probability.
weaknesses: Can the reduction in [1] be used to map the multi-context to a single context problem? The technique is proposed for non-adversarial losses, however, the action set map from distributional to fixed should not be affected by that.
I understand that the paper only focuses on analyzing an existing algorithm. However, a comparison with such technique in the related work is needed to justify the use of such algorithm or suggest alternative techniques to address the problem.

[1] "Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: - Should the definition of regret on page 3 be reversed? As in, you are subtracting the loss of the best arm with the loss of a policy, which should be a negative value (if with positive regret). This would change the decomposition of the regret on page 5 as well, but it seems nothing would affect the correctness.
- I think the full algorithm description of the algorithm in SZ [NeurIPS’23] (or some simpler version of the description) could be shown much earlier in the paper. This would be helpful for readers who are not familiar with the previous algorithm.
- Also, stating the main theorem in a preliminary section looks very non-standard to me. I’m not letting this affect my score, but please consider re-organizing this.
- The meaning of 'with high probability' was never explained in the paper -- as in, it could mean with probability $1-1/K$ or with probability $0.99$. I think your bound gives the former, and this should be stated explicitly.
soundness: 4
strengths: In general, my opinion of this paper is positive. The paper appears to require a great deal of background to be able to parse. Despite this, I believe the paper did reasonably well in terms of explaining the existing work and its techniques. Getting high probability bounds in adversarial bandits usually requires some neat observations and technical steps. Although I’m not able to follow all the steps in the short time frame, I do think the paper contains some nice technical observations and ideas.
summary: The paper studied adversarial context bandits in a special setting where the losses of arm $a_i$ could be observed under all contexts when the algorithm plays arm $a_i$. The goal, like in classical adversarial bandit problems, is to minimize the regret compared to the loss of the best arm in hindsight. The paper focuses on the setting where the loss sequence is adversarial and the context is stochastic with an unknown distribution. A recent work of SZ [NeurIPS’23] designed an algorithm with *expected* regret of $\tilde{O}(\sqrt{KT})$ in this setting, where $K$ is the number of arms. This paper conducted a renewed analysis of the algorithm in SZ  [NeurIPS’23], and the main result is that the algorithm could actually achieve $\tilde{O}(\sqrt{KT})$ with high probability.

The main technique of the paper is heavily influenced by the previous work of SZ [NeurIPS’23]. In a nutshell, the low-regret guarantee of the algorithm crucially relies on the concentration of unbiased estimation of $E_{c}[\ell_{t,c}(a)]$. Here, we cannot exactly compute the quantity since the distribution of the context is unknown. The key idea of SZ [NeurIPS’23] is to commit two steps for each EXP3 step and use one of them to estimate the distribution of the context. On top of that, this paper further utilized the weak dependency between epochs, and derived a martingale argument to get high-probability regret.
weaknesses: Although I'm mostly supportive, I think I couldn’t strongly champion the paper due to the following reasons:
- The scope of contribution: although the paper does contain some neat technical observations, the contribution appears to be somehow incremental. After all, this is a new analysis of an existing algorithm, and the new analysis is not something that improves the previous bound (but instead is to get a high-probability bound). Again, I do acknowledge that such contributions are non-trivial. However, I do not think it’s enough for me to champion the paper.
- If the paper is going to be mainly accepted due to the techniques: then, I do not think the paper contains a substantial amount of new ideas. I appreciate the technical observations, and I agree that the steps are non-trivial. However, if the conceptual message is not as strong, and the merits of the paper mainly lie in the techniques, then the bar would inevitably be higher. 
- For a conference like ICLR, the lack of experiments could be an issue. I am *not* letting this affect my score since I often advocate learning theory papers. However, I do want to raise this point since it is common for ML conferences to ask for experiments.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: - (1) Is the concept class $C$ a finite set? If so, what is the reason for assuming a finite concept class $C$? Practically speaking, the contextual information would be like a vector in a compact set, as it is very unlikely to see two identical users.
- (2) Where is the variable in Theorem 1 that characterizes the property of $C$? How does this variable appear in the bound proved in this submission?
- (3) Could you please provide more evidence or further discussion of the applicability of the technique developed here so that we can better appreciate its potential?
soundness: 3
strengths: - The submission points out the difficulty that prevents the previous work from achieving a bound with high probability (lines 167–176).
- Identify the weak dependency between epochs (line 386).
- Devise a new technique to solve the unbounded issue induced by the weak dependency (the treatment for the Bias5e them in lines 395–411).
summary: The submission studies contextual bandits with cross learning. Previously, the existing regret bound held in expectation. The submission refines the regret analysis so that the regret bound holds with high probability. The main contribution is to show how the weak dependency structure can be exploited to solve a concentration difficulty in the previous analysis.
weaknesses: - (1) Section 3.2 contains several subtopics, such as the regret decomposition, the discussion of each decomposed term, and the analysis strategy for the challenging term. A better editorial layout would improve the readability.
- (2) The sentence “Notably, …” in line 111 is confusing. It seems unrealistic to be able to observe the loss for every context $c$. It also does not match the algorithm’s (Algorithm 1) behavior.

Meta-review: This paper explores adversarial context bandits, specifically focusing on a scenario where the losses of each arm are observable under all contexts when the algorithm selects that arm. The objective is to minimize regret by comparing the algorithm's performance to the best arm in hindsight, similar to classical adversarial bandit problems. The study examines a setting where the loss sequence is adversarial and the context is stochastic with an unknown distribution.

A prior work by SZ (NeurIPS'23) introduced an algorithm that achieved expected regret in this setting, where the number of arms was a factor. The main contribution of this paper is a refined analysis of the SZ algorithm, demonstrating that it can achieve a much lower regret with high probability. The paper builds on SZ's approach, which hinges on the concentration of unbiased estimation of the loss, despite the unknown context distribution. SZ's key idea involves a two-step process for each EXP3 step, with one step dedicated to estimating the context distribution. This paper extends SZ's method by leveraging weak dependencies between epochs and incorporating a martingale argument to achieve high-probability regret bounds.

The paper provides a new analysis of an existing algorithm, focusing on obtaining high-probability regret bounds. While the technical observations are non-trivial, the contribution is incremental, as it does not improve prior bounds or introduce substantial new ideas. Reviewers highlighted that the paper's primary merits lie in its techniques, which, while appreciated, may not meet the bar for ICLR without a stronger conceptual message. Additionally, concerns were raised about the lack of experimental validation, unconventional organization (e.g., the placement of the main theorem in the preliminary section), and unclear definitions (e.g., "with high probability"). Although these issues do not compromise correctness, they detract from the paper’s clarity and impact, leading to hesitations about its suitability for acceptance. Based on the common consensus, therefore, I would recommend that the authors submit to the next suitable venue to address all the concerns once all the necessary modifications are incorporated.

Decision: Reject