We develop a model selection approach to tackle reinforcement learning with adversarial corruption in both transition and reward. For finite-horizon tabular MDPs, without prior knowledge on the total amount of corruption, our algorithm achieves a regret bound of $\otil\big(\min\{\frac{1}{\Delta}, \sqrt{T}\}+C\big)$ where $T$ is the number of episodes, $C$ is the total amount of corruption, and $\Delta$ is the reward gap between the best and the second-best policy. This is the first worst-case optimal bound achieved without knowledge of $C$, improving previous results of [Lykouris et al., 2021, Chen et al., 2021, Wu et al., 2021]. For finite-horizon linear MDPs, we develop a computationally efficient algorithm with a regret bound of $\otil(\sqrt{(1+C)T})$, and another computationally inefficient one with $\otil(\sqrt{T}+C)$, improving the result of [Lykouris et al., 2021] and answering an open question by [Zhang et al., 2021]. Finally, our model selection framework can be easily applied to other settings including linear bandits, linear contextual bandits, and MDPs with general function approximation, leading to several improved or new results.

§ INTRODUCTION

Reinforcement learning (RL) studies how an agent learns to behave in an unknown environment with reward feedback. The environment is often modeled as a Markov decision process (MDP). In the standard setting, the MDP is assumed to be static, i.e., the state transition kernel and the instantaneous reward function remain fixed over time. Under this assumption, numerous computationally and statistically efficient algorithms with strong theoretical guarantees have been developed [Jaksch et al., 2010, Lattimore and Hutter, 2012, Dann and Brunskill, 2015, Azar et al., 2017, Jin et al., 2018, Jin et al., 2020]. However, these guarantees might break completely if the transition or the reward is corrupted by an adversary, even if the corruption is limited to a small fraction of rounds.

To model adversarial corruptions in MDPs, a framework called adversarial MDP has been extensively studied. In adversarial MDPs, the adversary is allowed to choose the reward function arbitrarily in every round, while keeping the transition kernel fixed [Neu et al., 2010, Neu et al., 2010, Dick et al., 2014, Rosenberg and Mansour, 2019, Rosenberg and Mansour, 2021, Jin et al., 2020, Neu and Olkhovskaya, 2020, Lee et al., 2020, Chen and Luo, 2021, He et al., 2021, Luo et al., 2021]. Under this framework, strong sub-linear regret bounds can be established, which almost match the bounds for the fixed reward case. Notably, [Jin and Luo, 2020, Jin et al., 2021] developed algorithms that achieve near-minimax regret bound in the adversarial reward case, while
preserving refined instance-dependent bounds in the static case, showing that adversarial reward can be handled almost without price.

The situation becomes very different when the transition kernel can also be corrupted. It is first shown by [Abbasi-Yadkori et al., 2013] that achieving sub-linear regret in this setting is computationally hard, and recently enhanced by [Tian et al., 2021] showing that it is even information-theoretically hard. To establish meaningful guarantees, previous work aims to achieve a regret bound that smoothly degrades with the amount of corruption, and thus the learner can still behave well when only a small fraction of data is corrupted. When the total amount corruption is given as a prior knowledge to the learner, [Wu et al., 2021] designed an algorithm with a regret upper bound that scales optimally with the amount of corruption. However, this kind of prior knowledge is rarely available in practice. When the total amount of corruption is unknown, efforts were made by [Lykouris et al., 2021, Chen et al., 2021, Cheung et al., 2020, Wei and Luo, 2021, Zhang et al., 2021] to obtain similar guarantees. Unfortunately, all their bounds scale sub-optimally in the amount of corruption. Therefore, the following question remains open:
When both reward and transition can be corrupted, how can the learner achieve a regret bound that has optimal dependence on the unknown amount of corruption?
We address this open problem by designing an efficient algorithm with the desired worst-case optimal bound. Specifically, in tabular MDPs, our regret bound scales with $\sqrt{T}+C$ where $T$ is the number of rounds and $C$ is the total amount of corruption (omitting dependencies on other quantities). This matches the lower bound by [Wu et al., 2021]. In contrast, the bounds obtained by [Lykouris et al., 2021] and [Chen et al., 2021] are $(1+C)\sqrt{T}+C^2$ and $\sqrt{T}+C^2$ respectively, which are non-vacuous only when $C\leq \sqrt{T}$, a rather limited case. The bounds obtained by [Cheung et al., 2020, Wei and Luo, 2021, Zhang et al., 2021] are $(1+C)^{\nicefrac{1}{4}}T^{\nicefrac{3}{4}}$, $\sqrt{T} + C^{\nicefrac{1}{3}}T^{\nicefrac{2}{3}}$, and $\sqrt{(1+C)T}$ respectively. Although these bounds are meaningful for all $C
\leq T$, the dependence on $C$ is multiplicative to $T$, which is undesirable.

For tabular MDPs, we further show that the bound can be improved to $\min\{\frac{1}{\Delta}, \sqrt{T}\} + C$, where $\Delta$ is the gap between the expected reward of the best and the second-best policies. This kind of refined instance-dependent regret bound is also established by [Lykouris et al., 2021] and [Chen et al., 2021]. The bound of [Lykouris et al., 2021] is $(1+C)\min\{\gap, \sqrt{T}\} + C^2$ for some gap-complexity $\gap\leq \frac{1}{\Delta}$, while [Chen et al., 2021] obtained $\min\{\frac{1}{\Delta}, \sqrt{T}\}+C^2$. It is left as an open question whether the best-of-all-world bound $\min\{\gap, \sqrt{T}\} + C$ is achievable.

Our method is based on the framework of model selection [Agarwal et al., 2017, Foster et al., 2019, Arora et al., 2021, Abbasi-Yadkori et al., 2020, Pacchiano et al., 2020, Pacchiano et al., 2020]. In model selection problems, the learner is given a set of base algorithms, each with an underlying model or assumption for the world. However, the learner does not know in advance which model fits the real world the best. The goal of the learner is to be comparable to the best base algorithm in hindsight. In our case, a model of the world corresponds to a hypothetical amount of corruption $C$; for a given $C$, there are algorithms with near-optimal bounds (e.g., [Wu et al., 2021]) that can serve as base algorithms. Therefore, the problem of handling unknown corruption can be cast as a model selection problem. To get the bound of $\sqrt{T}+C$, we adopt the idea of regret balancing similar to those of [Abbasi-Yadkori et al., 2020, Pacchiano et al., 2020], while to get $\min\{\frac{1}{\Delta}, \sqrt{T}\}+C$, we develop another novel two-model selection algorithm to achieve the goal (see sec: gap bound).

Extensions to linear and general function approximation Our model selection framework can be readily extended to the cases of linear contextual bandits and linear MDPs.

However, in app: non-robust, we demonstrate that even with at most $C$ corrupted rounds, a straightforward extension of standard algorithms (i.e., OFUL [Abbasi-Yadkori et al., 2011], LSVI-UCB [Jin et al., 2020]) results in an overall regret of $\Omega(\sqrt{CT})$, a sharp contrast with the $\order(\sqrt{T}+C)$ bound in tabular MDPs. We find that the $\order(\sqrt{T}+C)$ bound can indeed be achieved efficiently in the non-contextual case (i.e., linear bandits with a fixed action set) by using the Phased Elimination (PE) approach developed by [Lattimore et al., 2020, Bogunovic et al., 2021].
We achieve the same bounds for linear contextual bandits and linear MDPs, but we resort to the idea of [Zhang et al., 2021], who deal with linear models through a sophisticated and computationally inefficient clipping technique. Note that the original purpose of [Zhang et al., 2021] is to get a variance-reduced bound for linear contextual bandits and a horizon-free bound for linear mixture MDPs, which are very different from our goal here. Their idea being applicable to improve robustness against corruption is surprising and of independent interest. The fact that additive dependence on $C$ is possible under linear settings (though computationally inefficient) partially answers an open question by [Zhang et al., 2021].

We further extend our framework to general function approximation settings. We consider the class of MDPs that have low Bellman-eluder dimension [Jin et al., 2021], and derive a corruption-robust version of their algorithm (GOLF). The algorithm achieves a regret bound of $\order(\sqrt{(1+C)T})$. Whether the bound of $\order(\sqrt{T}+C)$ is possible is left as an open problem.

In tab: table of bounds, we compare our bounds with those in previous works (omitting dependencies other than $C$ and $T$). Note that $C^\textsf{r}$ is best interpreted as $\sqrt{CT}$ in the notation of prior work. More thorough comparisons to the related works are provided in app: related work, and more precise bounds (including dependencies other than $C$ and $T$) are provided in app: base algorithms.

$\ineff$ indicates computationally inefficient algorithms. $\gap$ is the  defined in [Simchowitz and Jamieson, 2019]; $\Delta$ is the gap between the expected reward of the best and second-best policy. It holds that  $\gap\leq \frac{1}{\Delta}$. $C^{\textsf{a}}=\sum_t c_t$ and $C^{\textsf{r}}=\sqrt{T\sum_t c_t^2}$, where $c_t$ is the amount of corruption in round $t$. By definition, $C^{\textsf{a}}\leq C^{\textsf{r}}\leq \min\{\sqrt{C^{\textsf{a}} T}, T\max_{t} c_t\}$.  $C^{\textsf{a}}$ is the standard notion of corruption in the literature.

$^\dagger$: The bound reported in [Jin et al., 2021] is $\min\{\gap + \sqrt{\gap C^{\textsf{a}}}, \sqrt{T}\}$ under a different definition of regret.

$^\sharp$: Linearized corruption restricts that the corruption on action $a$ equals to $c^\top a$ for some vector $c$ shared among all actions.

Setting     Algorithm     $\Reg(T)$ in $\otil(\cdot)$     Restrictions

4*Tabular MDP     [Lykouris et al., 2021]     $(1+C^{\am})\min\{\gap, \sqrt{T}\} + (C^\am)^2$

[Chen et al., 2021]     $\min\{\frac{1}{\Delta}, \sqrt{T}\}+ (C^{\am})^2$     $\ineff$

[Jin et al., 2021]$^\dagger$
$\min\{\gap, \sqrt{T}\} + C^\am$

0.9only for corruption

0.9in reward

+ UCBVI    $\min\{\frac{1}{\Delta}, \sqrt{T}\}+ C^{\am}$

5*Linear bandit
[Li et al., 2019]     $\frac{1}{\Delta^2} + \frac{C^\am}{\Delta}$

[Bogunovic et al., 2020]     $(1+C^\am)  \sqrt{T}$

[Bogunovic et al., 2021]     $\sqrt{T} + (C^\am)^2$

[Lee et al., 2021]     $\min\{\frac{1}{\Delta}, \sqrt{T}\} + C^\am$

0.9only for linearized

+ PE     $\min\{\frac{1}{\Delta}, \sqrt{T}\} + C^\am$

3*Linear contextual
bandit     [Foster et al., 2020]     $\sqrt{T} + C^\rms$

+ OFUL   $\sqrt{T} + C^\rms$

+ VOFUL    $\sqrt{T} + C^\am$     $\ineff$

4*Linear MDP     [Lykouris et al., 2021]     $\sqrt{T} + (C^{\am})^2\sqrt{T}$

[Wei and Luo, 2021]     $\sqrt{T} + (C^{\am})^{\nicefrac{1}{3}}T^{\nicefrac{2}{3}}$

+ LSVI-UCB    $\sqrt{T} + C^\rms$

+ VARLin    $\sqrt{T} + C^\am$     $\ineff$

Low BE-dimension     + GOLF    $\sqrt{T}+C^\rms$     $\ineff$

§ PROBLEM SETTING

We consider a general decision making framework that covers a wide range of problems. We first describe the uncorrupted setting. The learner is given a policy set $\Pi$ and a context set $\calX$. Ahead of time, the environment decides a context-to-expected-reward mapping $\mu^\pi: \calX \rightarrow [0,1]$ for all $\pi\in\Pi$, which are hidden from the learner. In each round $t=1,\ldots, T$, the environment first arbitrarily generates a context $x_t\in\calX$, and generates a noisy reward $r^\pi_t\in[0,1]$ for all $\pi$ such that $\E[r^\pi_t] = \mu^\pi(x_t)$. The context $x_t$ is revealed to the learner. Then the learner chooses a policy $\pi_t$, and receives $r_t\triangleq r_t^{\pi_t}$. The goal of the learner is to minimize the regret defined as

\begin{align}
\Reg(T) = \max_{\pi\in \Pi} \sum_{t=1}^T \big(\mu^{\pi}(x_t) - \mu^{\pi_t}(x_t)\big).  \label{eq: pseudo}
\end{align}

In the corrupted setting, the protocol is similar, but in each round $t$, an adversary can change the context-to-expected-reward mapping from $\mu^\pi(\cdot)$ to $\mu_t^{\pi}(\cdot)$. Then $r_t^{\pi}$ is drawn such that $\E[r_t^{\pi}]=\mu^\pi_t(x_t)$. We assume that $\mu_t^{\pi}(x_t)$ and $r^{\pi}_t$ still lie in $[0,1]$.  As before, the learner observes $x_t$, chooses $\pi_t$, and receives $r_t=r_t^{\pi_t}$. The goal of the learner remains to minimize the regret defined in eq: pseudo (notice that it is defined through the uncorrupted $\mu$).
The adversary we consider falls into the category of an adaptive adversary, an adversary that can decide the corruption in round $t$ based on the history up to round $t-1$.

We consider the realizable setting, where the following assumption holds:

There exists a policy $\pistar\in\Pi$ such that $\mu^{\pistar}(x_t)\geq \mu^\pi(x_t)$ for all $t$ and all $\pi\in\Pi$.

Below, we instantiate this framework to linear (contextual) bandits and episodic MDPs. For each setting, we define a suitable quantity $c_t$ to measure the amount of corruption in round $t$. It always holds that $\max_{\pi\in\Pi}|\mu^{\pi}(x_t) - \mu_t^{\pi}(x_t)|\leq c_t$, but $c_t$ might be strictly larger than $\max_{\pi\in\Pi}|\mu^{\pi}(x_t) - \mu_t^{\pi}(x_t)|$ in some cases.

Linear contextual bandits
In linear contextual bandits, the policy set can be identified as a bounded parameter set $\calW\subset \mathbb{R}^d$ in which the true underlying parameter $w^\star$ lies, and the “context” can be identified as the “action set” in each round. In the uncorrupted setting, in each round $t$, the environment first generates an action set $\calA_t\subset \mathbb{R}^d$ (the context). Then each policy $w\in\calW$ is associated with an action $a^w(\calA_t)=\argmax_{a\in\calA_t}\inner{w, a}$. The expected reward of policy $w$ under context $\calA_t$ is then given by $\mu^{w}(\calA_t)=\inner{w^\star, a^w(\calA_t)}\in[0,1]$ for all $w$.
Clearly, $w^\star$ is a policy that satisfies assum: realizable.

In the corrupted setting, for any $t$ and $w$, the adversary can choose $\mu_t^w(\cdot)$ to be an arbitrary mapping from $\calA_t$ to $[0,1]$, and $r^w_t$ is generated such that $\E[r^w_t]=\mu^w(\calA_t)$ and $r^w_t\in[0,1]$. We define $c_t=\max_{w\in\calW}|\mu^w(\calA_t) - \mu^{w}_t(\calA_t)|$.

Linear bandits  Linear bandits can be viewed as a special case of linear contextual bandits with a fixed action set $\calA_t=\calA$ for all $t$. In this case, since every policy chooses the same action in every round, a more direct formulation is to identify the policy set as the action set $\calA$ and ignore the context. The expect reward of policy/action $a\in\calA$ is given by $\mu^a=\inner{w^\star, a}\in[0,1]$ for some unknown $w^\star$. Note that the action $\argmax_{a}\inner{w^\star, a}$ satisfies assum: realizable. In the corrupted setting, $\mu_t^a$ can be set to an arbitrary value in $[0,1]$, and $r_t^a$ is generated such that $\E[r_t^a]=\mu_t^a$ and $r_t^a\in[0,1]$. We define $c_t=\max_{a\in\calA}|\mu^a-\mu_t^a|$.

Episodic Markov decision processes
An episodic MDP is associated with a state space $\calS$, an action space $\calA$, a number of layers $H$, a transition kernel $p: \calS\times \calA\rightarrow \Delta_{\calS}$, and a reward function $\sigma: \calS\times \calA\rightarrow [0,\frac{1}{H}]$. A policy $\pi=\{\pi_h: \calS\rightarrow \calA, \ h= 1, 2, \ldots, H\}$ consists of mappings $\calS\rightarrow \calA$ for each layer that specifies which action it takes in each state in that layer. The context is identified as the “initial state.”

In the uncorrupted setting, in each round $t$, the environment arbitrarily generates an initial state $s_{t,1}\in \calS$ (the context). Then the learner decides a policy $\pi_t=\{\pi_{t,h}\}_{h=1}^H$, and interacts with the environment for $H$ steps starting from $s_{t,1}$. On the $h$-th step, she chooses an action $a_{t,h}=\pi_{t,h}(s_{t,h})$, observes a noisy reward $\sigma_{t,h}\in[0,\frac{1}{H}]$ with $\E[\sigma_{t,h}]=\sigma(s_{t,h}, a_{t,h})$, and transitions to the next state $s_{t,h+1}\sim p(\cdot|s_{t,h}, a_{t,h})$.[Our setting is a scaled version of the standard episodic MDP setting where all rewards are scaled by $1/H$. This scaling does not affect the difficulty of the problem but allows us to unify the presentation with our other settings.] The round ends right after the learner transitions to state $s_{t,H+1}$. With this procedure, the expected reward of policy $\pi$ given the initial state $s$ can be represented as

\begin{align}
\mu^\pi(s) = \E\left[\sum_{h=1}^H \sigma(s_h, a_h)~\bigg|~s_1=s, \  a_h=\pi_h(s_h),\  s_{h+1}\sim p(\cdot|s_h, a_h),\ \ \forall h=1, \ldots, H \right],   \label{eq: V function}
\end{align}

and $r_t^\pi$ is a realized reward of policy $\pi$ in round $t$, which satisfies $\E[r_t^\pi]=\mu^{\pi}(s_{t,1})$.

In the corrupted setting, in round $t$, we allow the adversary to change $p$ and $\sigma$ to $\pt$ and $\sigma_t$ respectively. The corrupted expected value $\mu^\pi_t(s)$ is defined similarly to eq: V function but with $p$ and $\sigma$ replaced by $p_t$ and $\sigma_t$. We assume that after corruption, $\sigma_{t,h}$ (whose expectation is $\sigma_t(s_{t,h}, a_{t,h})$) still lies in $[0,\frac{1}{H}]$.

To measure the amount of corruption in round $t$, we define the Bellman operators $\calT: \mathbb{R}^{\calS}\rightarrow \mathbb{R}^{\calS\times \calA}$ under the uncorrupted MDP and $\calT_t$ under the corrupted MDP as
(\calT V)(s,a) \triangleq \sigma(s,a) + \E_{s'\sim p(\cdot|s,a)}[V(s')]$ and $(\calTt V)(s,a) \triangleq \sigma_t(s,a) + \E_{s'\sim \pt(\cdot|s,a)}[V(s')]
for $V\in \mathbb{R}^\calS$.

Then the amount of corruption in round $t$ is defined as
$c_t \triangleq H \cdot \sup_{s,a} \sup_{V\in [0,1]^\calS} \left|(\calT V - \calTt V)(s,a)\right|$.

Additional note on corruption In all the above settings, we assume that the corruption is bounded. It holds that $c_{t}\leq c_{\max}$ for some $c_{\max}$ in all $t$. For linear (contextual) bandits, we can set $c_{\max}=1$, while for episodic MDPs, we can set $c_{\max}=2H$. While we assume bounded corruption to keep the exposition clean, our algorithm can actually handle more general scenarios. For example, for linear contextual bandits, we can handle the case where $\mu^{\pi}(\cdot)\in[0,1]$, but $\mu^{\pi}_t(\cdot)$ can be arbitrary, and $r^{\pi}_t - \mu^{\pi}_t(x_t)$ is zero-mean and 1-sub-Gaussian.
For this case, since $r^{\pi}_t - \mu^{\pi}_t(x_t)$ is bounded between $\pm c'\log(1/\delta)$ for some absolute constant $c'$ with high probability (i.e., with probability $1-\order(\delta)$), if we receive a reward $r_t$ that is outside $[-c'\log(1/\delta), 1+c'\log(1/\delta)]$, then with high probability it is caused by corruption. The learner only needs to project the reward back to this range. This essentially reduces the problem to bounded corruption case.

Other notations We use $[u, v]$ to denote $\{u, u+1, \ldots, v\}$, and $[u]$ to denote $\{1, 2, \ldots, u\}$. The notations $\otil(\cdot), \widetilde{\Theta}(\cdot)$ hide poly-logarithmic factors.

§.§ Two Ways to Compute Aggregated Corruption

In previous works of corruption-robust RL, the total corruption is defined as $C=\sum_{t=1}^T c_t$, where $c_t$ is the per-round corruption defined above. In  sec: intro and app: related work, we also adopt this definition when comparing with previous works. However, to unify the analysis under different settings, we introduce another notion of total regret defined as  $\sqrt{T\sum_{t=1}^T c_t^2}$ . To distinguish them, we denote $C^\am = \sum_{t=1}^T c_t$ and $C^\rms=\sqrt{T\sum_{t=1}^T c_t^2}$ , for that $C^\am$ is $T$ times the arithmetic mean of $c_t$'s, while $C^\rms$ is $T$ times the root mean square of $c_t$'s.

By defining $C^{\rms}$, we are able to recover the bounds in the “model misspecification” literature, in which the regret bound is often expressed through $T\max_t c_t$, which is an upper bound of $C^\rms$ (see tab: table of bounds and app: related work for more details).
We further define
$C_t^{\am} \triangleq \sum_{\tau=1}^t c_\tau$ and $C^{\rms}_t \triangleq \sqrt{t\sum_{\tau=1}^t c_\tau^2}$ .

§ GAP-INDEPENDENT BOUNDS VIA MODEL SELECTION

In this section, we develop a general corruption-robust algorithm based on model selection. The regret bound we achieve is of order $\otil(\sqrt{T}+C)$, where $C$ is either $C^\am$ or $C^\rms$ (see tab: table of bounds for the choices in different settings). Model selection approaches rely on a meta algorithm learning over a set of base algorithms. We first specify the properties that each base algorithm should satisfy:

[base algorithm, with either $C_t\triangleq C_t^\am$ or $C_t\triangleq C_t^\rms$]
$\alg$ is an algorithm that takes as input a time horizon $T$, a confidence level $\delta$, and a hypothetical corruption level $\thres$. ensures the following: with probability at least $1-\delta$, for all $t\leq T$ such that $C_{t}\leq \thres$, it holds that

\begin{align*}
\sum_{\tau=1}^t(r_\tau^{\pistar}-r_\tau) \leq \calR(t,\thres)
\end{align*}

for some function $\calR(t,\theta)$.

Without loss of generality, we assume that $\calR(t,\theta)$ is non-decreasing in both $t$ and $\theta$, and that $\calR(t,\theta)\geq \thres$.

If a base algorithm satisfies assum: regret with $C_t\triangleq C_t^\am$, we call it a base algorithm, while if $C_t\triangleq C_t^\rms$, we call it a .
Base algorithms are essentially corruption-robust algorithms that require the prior knowledge of the total corruption. Therefore, the algorithms developed by <cit.> or Wu et al., 2021 can be readily used as our base algorithms.
For example, for tabular MDPs, a variant of the UCBVI algorithm [Azar et al., 2017] satisfies assum: regret with $C_t\triangleq C_t^\am$ and $\calR(t,\thres)=\poly(H, \log(SAT/\delta))(\sqrt{SAt} + S^2A + SA\thres)$; for linear MDPs, a variant of the LSVI-UCB algorithm [Jin et al., 2020] satisfies assum: regret with $C_t\triangleq C_t^\rms$ and $\calR(t, \thres)=\poly(H, \log(dT/\delta))(\sqrt{d^3 t} + d\thres)$. More examples are provided in app: base algorithms.

A base algorithm with a higher hypothetical corruption level $\thres$ is more robust, but incurs more regret overhead. In contrast, base algorithms with lower hypothetical corruption level introduce less overhead, but have higher possibility of mis-specifying the amount of corruption. When the true total corruption is unknown, just running a single base algorithm with a fixed $\thres$ is risky either way.

The idea of our algorithm is to simultaneously run multiple base algorithms (in each round, sample one of the base algorithms and execute it), each with a different hypothesis on the total amount of corruption.
This idea is also used by [Lykouris et al., 2021]. Intuitively, if two base algorithms have a valid hypothesis for the total corruption (i.e., their hypotheses upper bound the true total corruption), then the one with smaller hypothesis should learn faster than the larger one because its hypothesis is closer to the true value, and incurs less overhead.  Therefore, if at some point we find that the average performance of a base algorithm with a smaller hypothesis is significantly worse than that of a larger one, it is an evidence that the former has mis-specified the amount of corruption. If this happens, we simply stop running this base algorithm.

There are two key questions to be answered. First, what distribution should we use to select among the base algorithms? Second, given this distribution, how should we detect mis-specification of the amount of corruption by comparing the performance of base algorithms? In sec: single epoch analysis, we answer the second question. The first question will be addressed in sec: elimination alg and sec: gap bound slightly differently depending on our target regret bound.

IfElseIfElseifelse ifelseend if
Base Algorithms run Simultaneously with mIs-specification Check ()

input:  base algorithm $\alg$ satisfying assum: regret,  $L\in [T]$,  $k\in [k_{\max}]$ where $k_{\max} \triangleq \lceil \log_2 (c_{\max}L) \rceil$,   $\delta\in(0,1)$,
and a distribution $\alpha=(\alpha_k ,\alpha_{k+1}, \ldots, \alpha_{k_{\max}})$ satisfying:

\begin{align*}
\alpha_k \geq \alpha_{k+1} \geq \cdots \geq \alpha_{k_{\max}} > 0 \qquad \text{and}\qquad \sum_{i=k}^{k_{\max}} \alpha_i = 1.
\end{align*}

$i=k, \ldots, k_{\max}$ Initiate an instance of $\alg$ with inputs $T, \delta$,
and $\thres$ chosen as below:

\begin{align}
\thres_i\triangleq
\begin{cases}
1.25\cdot\alpha_i2^{i}+21c_{\max}\log(T/\delta)  &\text{if $\alg$ is \typea}\\
1.25\cdot\alpha_i2^{i} + 8c_{\max}\sqrt{\alpha_i L\log(T/\delta)} + 21 c_{\max}\log(T/\delta) &\text{if $\alg$ is \typer}
\end{cases}
\label{eq: choice of thres}
\end{align}

(We call this instance $\alg_i$.)

$t=1,\ldots, L$
Random pick an sub-algorithm $i_t\sim \alpha$,
receive the context $x_t$, and use $\alg_{i_t}$ to output $\pi_t$.

Execute $\pi_t$, receive feedback, and perform  update on $\alg_{i_t}$.

Define $N_{t,i}\triangleq \sum_{\tau=1}^t \one[i_\tau=i]$, $R_{t,i}\triangleq \sum_{\tau=1}^t \one[i_\tau=i]r_\tau$.

$\exists i,j\in[k, k_{\max}]$, $i<j$, such that

\begin{align}
\frac{R_{t,i}}{\alpha_i} +   \frac{\calR(N_{t,i}, \thres_i)}{\alpha_i} < \frac{R_{t,j}}{\alpha_j} - 8\left(\sqrt{\frac{t\log(T/\delta)}{\alpha_j}} + \frac{\log(T/\delta)+ \thres_j}{\alpha_j}\right),    \label{eq: terminate condition 1}
\end{align}

return true.

§.§ Single Epoch Algorithm

In this section, we analyze (alg: regret balancing all), a building block of our final algorithms. In , the distribution over base algorithms is fixed and given as an input ($\alpha$ in alg: regret balancing all). Other inputs include: a length parameter $L$ that specifies the maximum number of rounds (the algorithm might terminate before finishing all $L$ rounds though) and an index $k\in [k_{\max}]$ ($k_{\max}$ is defined in alg: regret balancing all)
that specifies the smallest index of base algorithms (the base algorithms are indexed by $k, k+1, \ldots, k_{\max}$).

Below, we sometimes unify the statements for the two definitions of total corruption (see sec: two ways). The notations $(C, C_t)$ refer to $(C^\am, C_t^\am)$ if the base algorithm is , and refer to $(C^\rms, C_t^\rms)$ if it is . We will explicitly write the superscripts if we have to distinguish them.

The base algorithm with index $i\in[k, k_{\max}]$ (denoted as $\alg_i$) hypothesizes that the total corruption $C$ is upper bounded by $2^i$.

We say $\alg_i$ is well-specified at round $t$ if $C_t\leq 2^i$; otherwise we say it is mis-specified at round $t$.  Naively, we might want to set the $\thres$ parameter of $\alg_i$ to $2^i$. However, we can actually set it to be smaller to reduce the overhead, as explained below.

Since each base algorithm is sub-sampled according to the distribution $\alpha$, the total corruption experienced by $\alg_i$ in $[1,t]$ is only roughly $\sum_{\tau\leq t} \alpha_i c_\tau\leq \alpha_i C^\am$ or $\sqrt{(\alpha_i t)\sum_{\tau\leq t} \alpha_i c_\tau^2}\leq \alpha_i C^{\rms}$ (for and base algorithms respectively). This means that $\alg_i$, which hypothesizes a total corruption of $2^i$, only needs to set the $\thres$ parameter in assum: regret to roughly $\alpha_i2^i$, instead of $2^i$. Our choice of $\thres_i$ in eq: choice of thres is slightly larger than $\alpha_i 2^i$ to accommodate the randomness in the sampling procedure.

Besides performing sampling over base algorithms, also compares the performance any two base algorithms using eq: terminate condition 1.
If all base algorithms hypothesize large enough corruption, then all of them enjoy the regret bound specified in assum: regret in the subset of rounds they are executed. In this case, we can show that with high probability, the termination condition eq: terminate condition 1 will not hold. This is formalized in lem: istar = k case.

With probability at least $1-\order(k_{\max}\delta)$,
the termination condition eq: terminate condition 1 of the algorithm, does not hold in any round $t$, such that $C_{t}\leq 2^k$.

In other words, eq: terminate condition 1 is triggered only when $C_t > 2^k$, i.e., $\alg_k$ is mis-specified at round $t$. Once this happens, the algorithm terminates.

Checking condition eq: terminate condition 1 essentially ensures that the quantity $\frac{R_{t,i}}{\alpha_i}$ of all base algorithms remain close. Notice that at all $t$, there is always a well-specified base algorithm $i^\star$ with $C_t\leq 2^{i^\star}$ which enjoys the regret guarantee of assum: regret. Therefore, $\frac{R_{t,i^\star}}{\alpha_{i^\star}}$ is not too low, and thus, testing condition eq: terminate condition 1 prevents $\frac{R_{t,i}}{\alpha_i}$ of any $i$ from falling too low. This directly controls the performance of every base algorithms before termination. The following lemma bounds the learner's cumulative regret at termination.

Let $L_0\leq L$ be the round at which terminates, and let $i^\star$ be the smallest $i\in[k, k_{\max}]$ such that $C_{L_0}\leq 2^{i}$. Then with probability at least $1-\order(k_{\max}\delta)$,

\begin{align*}
\sum_{t=1}^{L_0} (r_{t}^{\pi^\star} - r_t) \leq \sum_{i=k}^{k_{\max}} \calR(N_{L_0,i}, \thres_i) + \otil\left(\one\left[i^\star > k\right]\left(\sqrt{\frac{L_0}{\alpha_{i^\star}}} + \frac{\calR(N_{L_0,i^\star}, \theta_{i^\star})}{\alpha_{i^\star}}\right)\right).
\end{align*}

where $N_{L_0, i}$ is the total number of rounds $\alg_i$ was played.

§.§ Corruption-robust Algorithms with $\sqrt{T}+C^{\textsf{a}}$ or $\sqrt{T}+C^{\textsf{r}}$ Bounds

Next, we use to build a corruption-robust algorithm with a regret bound of either $\sqrt{T}+C^\am$ or $\sqrt{T}+C^{\rms}$ without prior knowledge of $C^\am$ or $C^\rms$. The algorithm is called and presented in alg: meta alg. We consider base algorithms with the following concrete form of $\calR(t,\thres)$:

\begin{align}
\calR(t,\thres) = \sqrt{\beta_1 t} + \beta_2 \theta + \beta_3  \label{eq: typeone}
\end{align}

for some $\beta_1, \beta_2, \beta_3 \geq 1$. starts with $k=k_{\init}$ (defined in alg: meta alg) and runs with inputs $k$ and $L=T$ and the following choice of $\{\alpha_i\}_{i=k}^{k_{\max}}$:

\begin{align}
\alpha_i =
\begin{cases}
2^{k-i-1}  &\text{for\ } i>k, \\
1-\sum_{i=k+1}^{k_{\max}}\alpha_i &\text{for\ } i=k.
\end{cases}  \label{eq: type 2 alpha}
\end{align}

Whenever the subroutine terminates before $T$, we eliminate the $\alg_k$ and start a new instance of with $k$ increased by $1$ (see the for-loop in ). This is because as indicated by lem: istar = k case, early termination implies that $\alg_k$ mis-specifies the amount of corruption.

Notice that $2^{k_{\init}}$ is roughly of order $\sqrt{T}$, i.e., we start from assuming that the total amount of corruption is $\sqrt{T}$. This is because we only target the worst-case regret rate of $\sqrt{T}+C$ here, so refinements for smaller corruption levels $C\leq \sqrt{T}$ do not improve the asymptotic bound. Our choice of $\alpha_i$ makes $\alpha_i 2^i\approx 2^k$ for all $i$, and this further keeps the magnitudes of $\calR(N_{t,i}, \thres_i)$ of all $i$'s  roughly the same. This conforms with the regret balancing principle by [Abbasi-Yadkori et al., 2020, Pacchiano et al., 2020], as well as the sub-sampling idea of [Lykouris et al., 2021]. This makes the bound of the model selection algorithm only worse than the best base algorithm by a factor of $\order(k_{\max})=\otil(1)$ if all base algorithms are well-specified.

In the following theorem, we show guarantees of for both $C\triangleq C^\am$ and $C\triangleq C^\rms$. The proof essentially plugs the choices of parameters into lem: general regret, and sum the regret over epochs.

COrruption-robustness through Balancing and Elimination ()
input: base algorithm $\alg$ satisfying assum: regret with the form specified in eq: typeone.

define: $Z\triangleq c_{\max}$ if $\alg$ is , and $Z\triangleq c_{\max}\sqrt{T}$ if $\alg$ is .

$k_{\init}\triangleq \max\left\{ \left\lceil \log_2  \frac{\sqrt{\beta_1 T} + \beta_2 Z + \beta_3}{\beta_2} \right\rceil, \ 0\right\}$ with $\beta_1, \beta_2, \beta_3$ defined in eq: typeone.

$k=k_{\init}, \ldots$
Run with input $k$ and $L=T$, and $\{\alpha_i\}_{i=k}^{k_{\max}}$ specified in eq: type 2 alpha, until it terminates or the total number of rounds reaches $T$.

If $\alg$ satisfies assum: regret and $\calR(t,\thres)$ in the form of eq: typeone, then with $\alpha_i$'s specified in eq: type 2 alpha, guarantees with probability at least $1-\order(k_{\max}\delta)$ that

\begin{align*}
\Reg(T) = \otil\left(\sqrt{\beta_1 T} + \beta_2 (C^\am+Z) + \beta_3 \right),
\end{align*}

where $Z=c_{\max}$ if $C\triangleq C^\am$ and $Z=c_{\max}\sqrt{T}$ if $C\triangleq C^{\rms}$.

§ GAP-DEPENDENT BOUNDS

In this section, the goal is to get instance-dependent bounds similar to those in [Lykouris et al., 2021, Chen et al., 2021].
There are extra assumptions to be made in this section. First, we only deal with the case without contexts, i.e., the following assumption holds:

Assume that $\mu^\pi(x_t)=\mu^\pi$.

This covers linear bandits and MDPs with a fixed initial state. In fact, our approach can handle a slightly more general case where the context is i.i.d. generated in the uncorrupted case, and the non-iid-ness of the context distribution is considered as corruption (in contrast, in sec: main alg, the non-iid-ness of contexts is not considered as corruption).
Besides, our bound depends on the sub-optimality gap defined in the following:

There exists a policy $\pistar\in\Pi$ such that for all $\pi\in \Pi\backslash\{\pistar\}$, $\mu^{\pi} \leq \mu^{\pistar} - \Delta$.

This gap assumption is in fact stronger than that made by [Chen et al., 2021]. In [Chen et al., 2021], $\Delta:= \min_{\pi:~\Delta_{\pi}>0}\Delta_\pi$ where $\Delta_\pi=\mu^{\pistar}-\mu^\pi$. Their definition keeps $\Delta>0$ when there are multiple optimal policies, while our assum: gap forces $\Delta=0$ if there are two optimal policies with the same expected reward. This kind of stronger gap assumption is similar to those in [Lee et al., 2021, Jin et al., 2021].
Finally, we only focus on the case with $C=C^\am$ throughout this section. [When $C=C^\rms$, our approach produces a regret term of $c_{\max}\sqrt{T}$ as in thm: form 1 regret, spoiling the gap-dependent bound. ]

Gap-bound enhanced ()
$k_{\init}=\max\left\{\left\lceil \log_2\frac{\sqrt{\beta_1} + \beta_2c_{\max} + \beta_3 }{\beta_2} \right\rceil, \ \ 0\right\}$,   $\beta_4 =10^4\left(2\beta_1 + 42\beta_2c_{\max}\log(T/\delta) + 2\beta_3\right)$.

$k=k_{\init}, \ldots$

Let $L$ be the smallest integer such that $\sqrt{\beta_4 L} \geq \beta_2 2^k$.

$L > T$break
Run with input $k$ and $L$, and $\{\alpha_i\}_{i=k}^{k_{\max}}$ specified in eq: type 2 alpha until it terminates or the number of rounds reaches $T$.
Let $o$ be its output, and let $\hatpi$ be the policy that is executed the most number of times by the base algorithm $\alg_k$.

Run with $L, \hatpi, \calB_{\hatpi}$, until it terminates or the number of rounds reaches $T$.

Run in the remaining rounds.

§.§ Algorithm Overview

Our algorithm (alg: meta alg gap) consists of three phases where the first two phases are executed interleavingly. In (line: phaseone start-line: phaseone end in ), we run with a base algorithm that satisfies assum: regret with the following gap-dependent bound:

\begin{align}
\calR(t, \thres) = \min\left\{\sqrt{\beta_1 t}, \ \frac{\beta_1}{\Delta}\right\}+ \beta_2 \thres + \beta_3 \label{eq: typetwo}
\end{align}

for some $\beta_1, \beta_2, \beta_3$ satisfying $\beta_1\geq 16\log(T/\delta)$, $\beta_2\geq 1$, $\beta_3\geq 10\sqrt{\beta_1\log(T/\delta)}$.

In every for-loop of $k$, if in returns true, the algorithm proceeds to (line: phasetwo end in ). In we execute (alg: corral). is a specially designed two-model selection algorithm that dynamically chooses between two instances. One of the them is $\hatpi$, a candidate optimal policy identified in (defined in line: phaseone end of ); the other is an algorithm with $\hatpi$ as input (we call this algorithm $\calB_{\hatpi}$).
We assume  that $\calB_{\hatpi}$ has the following property:

$\calB_{\hatpi}$ is a corruption-robust algorithm over the policy set $\Pi\backslash\{\hatpi\}$ without the prior knowledge of total corruption. In other words, when running alone, in every round $t$, it chooses a policy $\pi_t\in\Pi\backslash\{\hatpi\}$ and receives $r_t$ with $\E[r_t]=\mu_t^{\pi_t}$. It ensures the following for all $t$ with probability at least $1-\delta$:

\begin{align}
\max_{\pi\in \Pi\backslash\{\hatpi\}}\sum_{\tau=1}^t \left(r^\pi_\tau - r_\tau\right) \leq \calR_{\calB}(t,C_t) \triangleq \sqrt{\beta_1 t} + \beta_2 C_t + \beta_3.     \label{eq: guarantee of B}\\[-10pt]
\nonumber
\end{align}

Notice that in sec: elimination alg we have already developed a corruption-robust algorithm , whose guarantee is already in the form of eq: guarantee of B, albeit over the original policy set $\Pi$ (see thm: form 1 regret). In app: leave one out, we describe how to implement $\calB_{\hatpi}$ through running on a modified MDP.

The in might end earlier than time $T$. This happens only when $\frac{1}{\Delta}+C$ is larger than the order of $2^k$.
In this case, the algorithm goes back to with $k$ increased by $1$. When $2^k$ grows to the order of $\sqrt{T}$ (implying that $\sqrt{T}\gtrsim \frac{1}{\Delta}+C$), we instead proceed to and simply run in the remaining rounds (line: L>T condition of ).

The regret guarantee of is summarized by the following theorem.

ensures that (with $\beta_4$ defined in alg: meta alg gap)

\begin{align*}
\Reg(T) = \otil\left(\min\left\{\sqrt{\beta_4 T}, \ \frac{\beta_4}{\Delta}\right\} + \beta_2 C + \beta_4 \right).
\end{align*}

thm: gap bound thm gives the first $\min\{\frac{1}{\Delta}, \sqrt{T}\}+C$ bound in the literature of corrupted MDPs without the knowledge of $C$.

To show thm: gap bound thm, we establish some key lemmas for and in sec: phaseone and sec: two-armed alg respectively. The complete proof of thm: gap bound thm is given in app: omitted proof for gap bound. Note that within the sub-routines and , we re-index the time so that they both start from $t=1$ for convenience.

§.§ of

In we run with base algorithms that achieve gap-dependent bounds eq: typetwo. The regret bound of under general choices of $\calR(t, \thres)$ and $\alpha_i$ is already derived in lem: general regret. Here, we apply it with the new form of $\calR(t, \thres)$ in eq: typetwo, and the new choice of $\alpha_i$ as below:

\begin{align}
\alpha_i =
\begin{cases}
\min\left\{ \frac{\sqrt{\beta_1 L}/\beta_2 + 2^k}{2^i} ,\ \frac{1}{2(k_{\max}-k)}\right\}  &\text{for\ } i>k \\
1-\sum_{i=k+1}^{k_{\max}}\alpha_i &\text{for\ } i=k
\end{cases} \label{eq: alpha for gap bound}
\end{align}

The regret bound of under such choices of parameters is summarized as the following:

Let $L_0\leq L$ be the round at which terminates. If $\calR(t,\thres)$ is in the form of eq: typetwo, and $\alpha_i$'s follow eq: alpha for gap bound, then with high probability, guarantees

\begin{align*}
\sum_{t=1}^{L_0}(r^{\pistar}_t - r_t) = \otil\left(\sqrt{\beta_1 L_0} + \beta_2 C_{L_0} + \beta_2 c_{\max} + \beta_3\right).
\end{align*}

We see that even though our base algorithms achieve a gap-dependent bound (eq: typetwo), the advantage is not reflected on the final bound of (as can be seen in lem: form 1 regret with gap, we still do not achieve a gap-dependent bound).
This is due to the fundamental limitation of general model selection problems [Pacchiano et al., 2020].
Therefore, lem: form 1 regret with gap does not seem to give any advantage over thm: form 1 regret.
However, the hidden advantage of using base algorithms with gap-dependent bounds is that if a base algorithm well-specifies the total corruption, it will quicker concentrate on the best policy. This enables the learner to identify the best policy faster. This is formalized in lem: execute most times.

Suppose that we run with base algorithms satisfying eq: typetwo. Let $L_0\leq L$ be the round at which terminates.
$32\left( \frac{\beta_4}{\Delta} + \beta_2 C_{L_0} \right)\leq \beta_2 2^{k} \leq \sqrt{\beta_4 L}$,
then with probability at least $1-\order(\delta)$, $L_0=L$, and the following holds:

\begin{align}
\sum_{t=1}^{L}\one[i_t=k]\one[\pi_t=\pi^\star] > \frac{1}{2}\sum_{t=1}^{L}\one[i_t=k]. \label{eq: execute most times}
\end{align}

lem: execute most times ensures that if $ 2^k\gtrsim \frac{1}{\Delta}+C$, by looking at which policy is most frequently executed by $\alg_k$, the learner can correctly identify the best policy $\hatpi=\pistar$ with high probability (by eq: execute most times and the definition of $\hatpi$ in ).

§.§ of

In , we execute , which is a model selection algorithm between $\hatpi$ and $\calB_{\hatpi}$. The high-level goal is to make the learner concentrate on executing $\hatpi$ until the end of $T$ rounds if $\hatpi=\pistar$ and $\frac{1}{\Delta} + C$ is relatively small, and otherwise terminate the algorithm quickly before incurring too much regret. It proceeds in epochs of varying length, indexed with $j$. The quantity $\hatDelta_j$ is an estimator of the gap between the average performance of $\hatpi$ and $\calB_{\hatpi}$ at the beginning of epoch $j$; $M_j$ is the maximum possible length of epoch $j$, and $p_j$ is the probability that the learner chooses $\calB_{\hatpi}$ in epoch $j$. The learner constantly monitors the difference between the average performance of $\hatpi$ and $\calB_{\hatpi}$ (line: detection start-line: detection end in ). Whenever she finds that their performance gap is actually much smaller or larger than $\hatDelta_j$ (i.e., if eq: checkk 1 or eq: checkk 2 holds), she updates $\hatDelta_j, M_j$, and $p_j$, and restarts a new epoch. If at any time $\hatDelta_j$ becomes smaller than $\hatDelta_1$, or $j$ grows larger than $3\log^2 T$, she terminates $\twomodel$. We establish the following two key lemmas.

Let $T_0$ be the last round of , then with probability at least $1-\order(\delta)$,

\begin{align*}
\sum_{t=1}^{T_0}(r_t^{\pistar} - r_t) =\otil\left( \sqrt{\beta_4 L} + \beta_2 C_{T_0}+\beta_4\right).
\end{align*}

Let $T_0$ be last round of . If $\hatpi=\pi^*$ and $\sqrt{\beta_4 L}\geq 16\left(\frac{\beta_4}{\Delta}+\beta_2 C_{T_0}\right)$, then with probability at least $1-\order(\delta)$, it is terminated because the number of rounds reaches $T$.

We combine lem: form 1 regret with gap-lem: no end to prove thm: gap bound thm in app: omitted proof for gap bound.

($L$,  $\hatpi$, $\calB_{\hatpi}$)

$\hatDelta_1\leftarrow \min\Big\{\sqrt{\frac{\beta_4}{L}}, 1\Big\}$ ,   $M_1\leftarrow \frac{\beta_4}{\hatDelta_1^2}$ ,  $t\leftarrow 1$.       ($\beta_4$ defined in alg: meta alg gap)

$j=1, 2, \ldots, (3\log^2 T)$
$t_j\leftarrow t$,
$p_j\leftarrow  \frac{\beta_4}{2M_j\hatDelta_j^2}$,  and re-initialize $\calB_{\hatpi}$.

$t\leq t_j + M_j-1$
$Y_t\leftarrow \text{Bernoulli}\left(p_j\right)$.

Execute $\calBpi$ for one round and update $\calBpi$

Execute $\hatpi$ for one round

$t\leftarrow t+1$

Let $\Rht_0 = \frac{1}{1-p_j}\sum_{\tau=t_j}^{t-1}r_\tau \one[Y_\tau=0]$,   $\Rht_1 = \frac{1}{p_j}\sum_{\tau=t_j}^{t-1}r_\tau \one[Y_\tau=1]$.

if                 _0 ≤_1 +  1/2 (t-t_j) _j - 5/p_j_(p_j(t-t_j), p_j√(β_1 L)/β_2)

then  _j+1←1/1.25_j  and break

if      _0 ≥_1 + 3 M_j_j +  8√(β_1 L)

then   _j+1 ←1.25_j   and break

$\hatDelta_{j+1}< \hatDelta_1$return

M_j+1←2(t-t_j) + β_4/_j+1^2

§ APPLICATIONS TO DIFFERENT SETTINGS

In app: base algorithms, we give examples of the base algorithms whose regret bound is of the form eq: typeone or eq: typetwo.
For tabular MDPs, we directly use the Robust UCBVI algorithm by [Lykouris et al., 2021] as our base algorithm (app: robust MVP). For linear bandit, we adopt the Robust Phased Elimination algorithm developed by [Bogunovic et al., 2021], and additionally prove a gap-dependent bound for it (app: robust phased elim). For linear contextual bandits and linear MDPs, we modify the OFUL/LSVI-UCB algorithm to make them robust to corruption (app: robust OFUL). Then we extend the VOFUL/VARLin algorithms by [Zhang et al., 2021], further improving the dependence on $C$ over the OFUL/LSVI-UCB approach (app: robust VOFUL). Finally, we derive a corruption-robust variant of the GOLF algorithm by [Jin et al., 2021] for the general function approximation setting (app: robust golf).

§ CONCLUSIONS AND FUTURE WORK

In this work, we develop a general model selection framework to deal with corruption in bandits and reinforcement learning. In the tabular MDP setting, without knowing the total corruption, our result is the first to achieve a worst-case optimal bound. This resolves open problems raised by [Lykouris et al., 2021, Chen et al., 2021, Wu et al., 2021].  A general framework to obtain refined gap-dependent bounds is also developed. In linear bandits, linear contextual bandits, and linear MDPs, our bounds also improve those of previous works in various ways.

However, our result is not the end of the story. There are many remaining open problems to be investigated in the future:

* For the tabular setting, our gap complexity measure is larger than those in [Simchowitz and Jamieson, 2019, Lykouris et al., 2021, Jin et al., 2021]. It is an important future direction to further improve our gap-dependent bound without sacrificing the worst-case dependence on $T$ or $C$.

* For linear contextual bandits and linear MDPs, a regret bound with additive dependence on $C^\am$ is only achieved through computationally inefficient algorithms (i.e., the variants of VOFUL and VARLin). These algorithms also have a bad dependence on the feature dimension $d$. Can we address these computational and statistical issues?

* In the model mis-specification literature, [Agarwal et al., 2020, Zanette et al., 2021] defines a new notion of local model mis-specification for the state aggregation scenario. It is much smaller and more favorable than the notion of model mis-specification defined in [Jin et al., 2020, Zanette et al., 2020]. Is there any counterpart for the corruption setting? If there is, how can we achieve robustness under such notion without prior knowledge?

The authors would like to thank Liyu Chen and Thodoris Lykouris for helpful discussions.

[Abbasi-Yadkori et al., 2011]
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.
Improved algorithms for linear stochastic bandits.
In Conference on Neural Information Processing Systems, 2011.

[Abbasi-Yadkori et al., 2013]
Yasin Abbasi-Yadkori, Peter L Bartlett, and Csaba Szepesvári.
Online learning in markov decision processes with adversarially
chosen transition probability distributions.
In Conference on Neural Information Processing Systems, 2013.

[Abbasi-Yadkori et al., 2020]
Yasin Abbasi-Yadkori, Aldo Pacchiano, and My Phan.
Regret balancing for bandit and rl model selection.
In Conference on Neural Information Processing Systems, 2020.

[Agarwal et al., 2017]
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire.
Corralling a band of bandit algorithms.
In Conference on Learning Theory, 2017.

[Agarwal et al., 2020]
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun.
Pc-pg: Policy cover directed exploration for provable policy gradient
In Conference on Neural Information Processing Systems,

[Agarwal et al., 2020]
Alekh Agarwal, Nan Jiang, Sham M. Kakade, and Wen Sun.
Reinforcement learning: Theory and algorithms.

[Arora et al., 2021]
Raman Arora, Teodor Vanislavov Marinov, and Mehryar Mohri.
Corralling stochastic bandit algorithms.
In International Conference on Artificial Intelligence and
Statistics, 2021.

[Auer and Chiang, 2016]
Peter Auer and Chao-Kai Chiang.
An algorithm with nearly optimal pseudo-regret for both stochastic
and adversarial bandits.
In Conference on Learning Theory, 2016.

[Awasthi et al., 2020]
Pranjal Awasthi, Sreenivas Gollapudi, Kostas Kollias, and Apaar Sadhwani.
Online learning under adversarial corruptions.
<https://openreview.net/forum?id=gBpYGXH9J7F>, 2020.

[Azar et al., 2017]
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.
Minimax regret bounds for reinforcement learning.
In International Conference on Machine Learning, 2017.

[Beygelzimer et al., 2011]
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire.
Contextual bandit algorithms with supervised learning guarantees.
In International Conference on Artificial Intelligence and
Statistics, 2011.

[Bhatia et al., 2017]
Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar.
Consistent robust regression.
In Conference on Neural Information Processing Systems, 2017.

[Bogunovic et al., 2020]
Ilija Bogunovic, Andreas Krause, and Jonathan Scarlett.
Corruption-tolerant gaussian process bandit optimization.
In International Conference on Artificial Intelligence and
Statistics, 2020.

[Bogunovic et al., 2021]
Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett.
Stochastic linear bandits robust to adversarial attacks.
In International Conference on Artificial Intelligence and
Statistics, 2021.

[Bubeck and Slivkins, 2012]
Sébastien Bubeck and Aleksandrs Slivkins.
The best of both worlds: Stochastic and adversarial bandits.
In Conference on Learning Theory, 2012.

[Chen and Luo, 2021]
Liyu Chen and Haipeng Luo.
Finding the stochastic shortest path with low regret: The adversarial
cost and unknown transition case.
In International Conference on Machine Learning, 2021.

[Chen et al., 2021]
Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau.
Online and distribution-free robustness: Regression and contextual
bandits with huber contamination.
In Symposium on Foundations of Computer Science,

[Chen et al., 2021]
Yifang Chen, Simon S. Du, and Kevin Jamieson.
Improved corruption robust algorithms for episodic reinforcement
In International Conference on Machine Learning,

[Cheung et al., 2020]
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu.
Reinforcement learning for non-stationary markov decision processes:
The blessing of (more) optimism.
In International Conference on Machine Learning, 2020.

[Cutkosky et al., 2021]
Ashok Cutkosky, Christoph Dann, Abhimanyu Das, Claudio Gentile, Aldo Pacchiano,
and Manish Purohit.
Dynamic balancing for model selection in bandits and rl.
In International Conference on Machine Learning, 2021.

[Dann and Brunskill, 2015]
Christoph Dann and Emma Brunskill.
Sample complexity of episodic fixed-horizon reinforcement learning.
In Conference on Neural Information Processing Systems, 2015.

[Dann et al., 2020]
Christoph Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, and Karthik
Reinforcement learning with feedback graphs.
In Conference on Neural Information Processing Systems, 2020.

[Diakonikolas et al., 2019]
Ilias Diakonikolas, Weihao Kong, and Alistair Stewart.
Efficient algorithms and lower bounds for robust linear regression.
ACM-SIAM Symposium on Discrete Algorithms, 2019.

[Dick et al., 2014]
Travis Dick, Andras Gyorgy, and Csaba Szepesvari.
Online learning in markov decision processes with changing cost
In International Conference on Machine Learning, 2014.

[Du et al., 2020]
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang.
Is a good representation sufficient for sample efficient
reinforcement learning?
In International Conference on Learning Representations, 2020.

[Foster et al., 2019]
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo.
Model selection for contextual bandits.
In Conference on Neural Information Processing Systems, 2019.

[Foster et al., 2020]
Dylan J Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert.
Adapting to misspecification in contextual bandits.
In Conference on Neural Information Processing Systems, 2020.

[Gupta et al., 2019]
Anupam Gupta, Tomer Koren, and Kunal Talwar.
Better algorithms for stochastic bandits with adversarial
In Conference on Learning Theory, 2019.

[He et al., 2021]
Jiafan He, Dongruo Zhou, and Quanquan Gu.
Nearly optimal regret for learning adversarial mdps with linear
function approximation.
arXiv preprint arXiv:2102.08940, 2021.

[Ito, 2021]
Shinji Ito.
Parameter-free multi-armed bandit algorithms with hybrid
data-dependent regret bounds.
In Conference on Learning Theory, 2021.

[Jaksch et al., 2010]
Thomas Jaksch, Ronald Ortner, and Peter Auer.
Near-optimal regret bounds for reinforcement learning.
Journal of Machine Learning Research, 2010.

[Jiang et al., 2017]
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E
Contextual decision processes with low bellman rank are
In International Conference on Machine Learning, 2017.

[Jin et al., 2018]
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.
Is q-learning provably efficient?
In Conference on Neural Information Processing Systems, 2018.

[Jin et al., 2020]
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu.
Learning adversarial markov decision processes with bandit feedback
and unknown transition.
In International Conference on Machine Learning,

[Jin et al., 2020]
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.
Provably efficient reinforcement learning with linear function
In Conference on Learning Theory, 2020b.

[Jin et al., 2021]
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi.
Bellman eluder dimension: New rich classes of rl problems, and
sample-efficient algorithms.
In Conference on Neural Information Processing Systems,

[Jin and Luo, 2020]
Tiancheng Jin and Haipeng Luo.
Simultaneously learning stochastic and adversarial episodic mdps with
known transition.
In Conference on Neural Information Processing Systems, 2020.

[Jin et al., 2021]
Tiancheng Jin, Longbo Huang, and Haipeng Luo.
The best of both worlds: stochastic and adversarial episodic mdps
with unknown transition.
In Conference on Neural Information Processing Systems,

[Lattimore and Hutter, 2012]
Tor Lattimore and Marcus Hutter.
Pac bounds for discounted mdps.
In International Conference on Algorithmic Learning Theory,

[Lattimore et al., 2020]
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz.
Learning with good feature representations in bandits and in rl with
a generative model.
In International Conference on Machine Learning, 2020.

[Lee et al., 2020]
Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, and Mengxiao Zhang.
Bias no more: high-probability data-dependent regret bounds for
adversarial bandits and mdps.
In Conference on Neural Information Processing Systems, 2020.

[Lee et al., 2021]
Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, Mengxiao Zhang, and Xiaojin Zhang.
Achieving near instance-optimality and minimax-optimality in
stochastic and adversarial linear bandits simultaneously.
In International Conference on Machine Learning, 2021.

[Li et al., 2019]
Yingkai Li, Edmund Y Lou, and Liren Shan.
Stochastic linear optimization with adversarial corruption.
arXiv preprint arXiv:1909.02109, 2019.

[Luo et al., 2021]
Haipeng Luo, Chen-Yu Wei, and Chung-Wei Lee.
Policy optimization in adversarial mdps: Improved exploration via
dilated bonuses.
In Conference on Neural Information Processing Systems, 2021.

[Lykouris et al., 2018]
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme.
Stochastic bandits robust to adversarial corruptions.
In ACM SIGACT Symposium on Theory of Computing, 2018.

[Lykouris et al., 2021]
Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun.
Corruption robust exploration in episodic reinforcement learning.
In Conference on Learning Theory, 2021.

[Neu and Olkhovskaya, 2020]
Gergely Neu and Julia Olkhovskaya.
Online learning in mdps with linear function approximation and bandit
arXiv preprint arXiv:2007.01612, 2020.

[Neu et al., 2010]
Gergely Neu, András György, Csaba Szepesvári, and András Antos.
Online markov decision processes under bandit feedback.
In Conference on Neural Information Processing Systems,

[Neu et al., 2010]
Gergely Neu, András György, Csaba Szepesvári, et al.
The online loop-free stochastic shortest-path problem.
In Conference on Learning Theory, 2010b.

[Pacchiano et al., 2020]
Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett.
Regret bound balancing and elimination for model selection in bandits
and rl.
arXiv preprint arXiv:2012.13045, 2020a.

[Pacchiano et al., 2020]
Aldo Pacchiano, My Phan, Yasin Abbasi-Yadkori, Anup Rao, Julian Zimmert, Tor
Lattimore, and Csaba Szepesvari.
Model selection in contextual stochastic bandit problems.
In Conference on Neural Information Processing Systems,

[Rosenberg and Mansour, 2019]
Aviv Rosenberg and Yishay Mansour.
Online convex optimization in adversarial markov decision processes.
In International Conference on Machine Learning, 2019.

[Rosenberg and Mansour, 2021]
Aviv Rosenberg and Yishay Mansour.
Stochastic shortest path with adversarially changing costs.
In AAAI Conference on Artificial Intelligence, 2021.

[Seldin and Lugosi, 2017]
Yevgeny Seldin and Gábor Lugosi.
An improved parametrization and analysis of the exp3++ algorithm for
stochastic and adversarial bandits.
In Conference on Learning Theory, 2017.

[Seldin and Slivkins, 2014]
Yevgeny Seldin and Aleksandrs Slivkins.
One practical algorithm for both stochastic and adversarial bandits.
In International Conference on Machine Learning, 2014.

[Simchowitz and Jamieson, 2019]
Max Simchowitz and Kevin G Jamieson.
Non-asymptotic gap-dependent regret bounds for tabular mdps.
In Conference on Neural Information Processing Systems, 2019.

[Takemura et al., 2021]
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga,
Naonori Kakimura, and Ken-ichi Kawarabayashi.
A parameter-free algorithm for misspecified linear contextual
In International Conference on Artificial Intelligence and
Statistics, 2021.

[Tian et al., 2021]
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra.
Online learning in unknown markov games.
In International Conference on Machine Learning, 2021.

[Wang et al., 2020]
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang.
Reinforcement learning with general value function approximation:
Provably efficient approach via bounded eluder dimension.
In Conference on Neural Information Processing Systems, 2020.

[Wei and Luo, 2018]
Chen-Yu Wei and Haipeng Luo.
More adaptive algorithms for adversarial bandits.
In Conference On Learning Theory, 2018.

[Wei and Luo, 2021]
Chen-Yu Wei and Haipeng Luo.
Non-stationary reinforcement learning without prior knowledge: An
optimal black-box approach.
In Conference on Learning Theory, 2021.

[Wu et al., 2021]
Tianhao Wu, Yunchang Yang, Simon Du, and Liwei Wang.
On reinforcement learning with adversarial corruption and its
application to block mdp.
In International Conference on Machine Learning, 2021.

[Wu, 2016]
Yihong Wu.
Lecture 14: Packing, covering, and consequences on minimax risk.
<http://www.stat.yale.edu/ yw562/teaching/598/lec14.pdf>, 2016.

[Zanette et al., 2020]
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.
Learning near optimal policies with low inherent bellman error.
In Internation Conference on Machine Learning, 2020.

[Zanette et al., 2021]
Andrea Zanette, Ching-An Cheng, and Alekh Agarwal.
Cautiously optimistic policy optimization and exploration with linear
function approximation.
In Conference on Learning Theory, 2021.

[Zhang et al., 2021]
Xuezhou Zhang, Yiding Chen, Jerry Zhu, and Wen Sun.
Corruption-robust offline reinforcement learning.
arXiv preprint arXiv:2106.06630, 2021a.

[Zhang et al., 2021]
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun.
Robust policy gradient against strong data corruption.
In International Conference on Machine Learning,

[Zhang et al., 2021]
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S. Du.
Variance-aware confidence set: Variance-dependent bound for linear
bandits and horizon-free bound for linear mixture mdp.
In Conference on Neural Information Processing Systems,

[Zimmert and Seldin, 2019]
Julian Zimmert and Yevgeny Seldin.
An optimal algorithm for stochastic and adversarial bandits.
In International Conference on Artificial Intelligence and
Statistics, 2019.

[Zimmert et al., 2019]
Julian Zimmert, Haipeng Luo, and Chen-Yu Wei.
Beating stochastic and adversarial semi-bandits optimally and
In International Conference on Machine Learning, 2019.

§ RELATED WORK

Corruption-robust bandit/RL have been studied under various setting, and have many other closely related topics, as we discuss below.

Corrupted multi-armed bandits and tabular MDPs Corruption-robust multi-armed bandits have been studied by [Lykouris et al., 2018, Gupta et al., 2019, Zimmert and Seldin, 2019] through three representative approaches. Interestingly, these three approaches have all been extended to the tabular MDP case by [Lykouris et al., 2021, Chen et al., 2021, Jin et al., 2021] respectively. However, the extensions by [Lykouris et al., 2021, Chen et al., 2021] produce a new $+C^2$ term in the regret bound, largely limiting the use case of their algorithms. Besides, the computational complexity of [Chen et al., 2021]'s algorithm scales with the number of policies, which is exponentially high. On the other hand, [Jin et al., 2021] successfully achieves a near-optimal bound, but requires that the transition remains uncorrupted.

Corrupted linear bandits  [Li et al., 2019] and [Bogunovic et al., 2020] extend the ideas of  [Gupta et al., 2019] and [Lykouris et al., 2018] to linear bandits and Gaussian bandits respectively. Their regret bounds both have multiplicative dependence on $C$. [Bogunovic et al., 2021] considers a stronger corruption model where the adversary can observe the action in the current round. Their bound $\sqrt{T}+C^2$ additively depends on $C$, but can only tolerate $C\leq \sqrt{T}$.[In the stronger adversary setting consider by [Bogunovic et al., 2021], however, the $C^2$ dependence is unavoidable. ] Recently, [Lee et al., 2021] established the first upper bound that has optimal dependence on the amount of corruption as well as a refined gap-dependent bound. However, their algorithm only handles a restricted form of corruption – the corruption injected to action $a$ must be in the form of $a^\top c$ for some vector $c$ shared among all actions. In our work, we are able to get a similar bound but without this strong assumption.

Corrupted MDPs with linear function approximation
[Lykouris et al., 2021] studies corrupted linear MDPs and gets a bound of order $C^2\sqrt{T}$, which only tolerates $C\leq T^{\nicefrac{1}{4}}$. [Zhang et al., 2021] leverages the intrinsic robustness of policy gradient and tools in robust statistics to achieve an improved bound $\sqrt{(1+C)T}$ when the feature space has a bounded relative condition number.
[Zhang et al., 2021] further studies offline RL in linear MDPs, showing that if the offline data has wide coverage, then there is an algorithm that can output a $\order(\sqrt{\nicefrac{1}{T}}+\nicefrac{C}{T})$-optimal policy after seeing $T$ samples with $C$ of them corrupted. Although this result indicates that $+C$ penalty in regret might be possible, their result heavily relies on the coverage assumption and does not apply to our setting.

Robust statistics The goal of robust statistics is to design estimators of some unknown quantity that are robust to data corruption. In several recent works, computationally efficient and highly robust estimators for linear regression that tolerate a constant fraction of data corruption have been designed [Bhatia et al., 2017, Diakonikolas et al., 2019, Chen et al., 2021]. However, such strong guarantees usually require additional assumptions on the data generation process or the corruption process. Robust statistics has been used in corruption-robust RL under special cases. For example, [Zhang et al., 2021, Zhang et al., 2021] achieve robustness in MDPs with certain exploratory properties, and [Awasthi et al., 2020] handles the case where the corrupted rounds are i.i.d. generated.

Model mis-specification  The notion of corruption we consider subsumes the notion of model mis-specification studied in many previous works [Jiang et al., 2017, Du et al., 2020, Jin et al., 2020, Zanette et al., 2020, Lattimore et al., 2020, Wang et al., 2020]. These works assume that the model class can only approximate the true world up to an order of $\order(\epsilon)$, and they establish regret bounds that have an additive $\order(\epsilon T)$ penalty. Clearly, one
can also view the difference between the model and the true world as corruption, and as shown in tab: table of bounds, all our bounds (both $\sqrt{T}+C^\am$ and $\sqrt{T}+C^{\rms}$) recover the $\order(\sqrt{T} + \epsilon T)$ bound in the mis-specification case. While many previous works assume a known $\epsilon$, there are also works dealing with the case of unknown $\epsilon$ [Takemura et al., 2021, Foster et al., 2020, Pacchiano et al., 2020].

Best-of-both-world bounds  The best-of-both-world problem was studied by [Bubeck and Slivkins, 2012, Seldin and Slivkins, 2014, Auer and Chiang, 2016, Seldin and Lugosi, 2017, Wei and Luo, 2018, Zimmert and Seldin, 2019, Zimmert et al., 2019, Jin and Luo, 2020, Ito, 2021, Jin et al., 2021, Lee et al., 2021] for various settings including multi-armed bandits, combinatorial semi-bandits, linear bandits, and tabular MDPs. The goal of this line of work is to have a single algorithm that achieves a $\otil(\sqrt{T})$ regret bound when the reward is adversarial and $\order(\log T)$ when the reward is stochastic, without knowing the type of reward in advance. Compared to our setting, their regret bound is always sub-linear in $T$ against a fixed policy, while ours is linear in the amount of corruption. However, their results usually rely on stronger structural assumptions than the corrupted setting we consider (e.g., the fixed transition assumption for MDPs or the linearized corruption assumption for linear bandits).

Non-stationary RL Non-stationary RL is another line of research that deals with non-static reward and transition [Cheung et al., 2020, Wei and Luo, 2021]. In non-stationary RL, the difficulty of the problem is usually quantified by the number of times the reward or transition changes, or their fine-grained amount of variation. The corruption setting can be viewed as a special case of it, so existing algorithms for the latter can be readily applied. However, since non-stationary RL is more general, this reduction only leads to sub-optimal regret bounds. For example, the tight bound $\sqrt{T}+B^{\nicefrac{1}{3}}T^{\nicefrac{2}{3}}$ obtained in [Wei and Luo, 2021], where $B$ is the overall variation, only translates to a sub-optimal bound $\sqrt{T}+C^{\nicefrac{1}{3}}T^{\nicefrac{2}{3}}$ in the corruption setting.

Model selection
Our approach is closely related to the regret balancing technique developed by [Abbasi-Yadkori et al., 2020, Pacchiano et al., 2020, Cutkosky et al., 2021]. [Pacchiano et al., 2020, Cutkosky et al., 2021] have applied regret balancing to tackle model mis-specification, but it remains unclear whether it also handles the more general corruption setting, where the adversary chooses which rounds to corrupt.
Existing techniques which choose base learners deterministically can only use a regret bound that includes the total corruption budget $\theta$ which leads to loose guarantees. Instead, our randomized choice allows us to scale regret bounds of base learners as $\alpha_i \theta$, where $\alpha_i$ is the probability of being selected. While [Pacchiano et al., 2020, Cutkosky et al., 2021] also provide a version of their algorithm with a randomized learner choice for the special case of linear stochastic bandits with adversarial contexts, they resort to a weaker elimination test that requires additional information from base learners. Our work shows that this is indeed unnecessary by pairing a randomized learner selection with a simple elimination test. This may be of interest beyond the corruption setting.

In our work, we also develop a special model selection algorithm that achieves a gap-dependent bound that is better than $\sqrt{T}$. This kind of better-than-$\sqrt{T}$ bound is rare in the literature of model selection, and even proven to be impossible for general cases [Pacchiano et al., 2020]. To our best knowledge, the only work on model selection that breaks the $\sqrt{T}$ barrier is [Arora et al., 2021], who considers a stationary multi-armed bandit setting where every base algorithm learns over a subset of arms, and the best arm is only controlled by one of the base algorithms.

However, their stochastic bandit setting is less challenging than our adversarial/corrupted RL setting, so their techniques cannot be directly applied. We hope that our technique can also hint about how to achieve better-than-$\sqrt{T}$ bounds in more general model selection problems.

§ THE NON-ROBUSTNESS OF LEAST SQUARE REGRESSION

In this section, we show that for linear contextual bandits with non-i.i.d. contexts, the most natural extension from the standard OFUL algorithm to a corruption-robust version results in a regret bound of $\Omega(\sqrt{C^\am T})$, even if $C^\am$ is known. See sec: problem setting for the definition of the linear contextual bandit framework that we consider. Recall that in the standard OFUL algorithm [Abbasi-Yadkori et al., 2011], the learner constructs a confidence set for the underlying parameter:

\begin{align}
\calW_t = \left\{ w~:~ \|w-\widehat{w}_t\|_{\Lambda_t}^{2}\leq \iota_t \right\} \label{eq: confidence OFUL}
\end{align}

for some $\iota_t > 0$, where

\begin{align*}
\Lambda_t = \lambda I + \sum_{\tau=1}^{t-1}a_\tau a_\tau^\top, \qquad \widehat{w}_t = \Lambda_t^{-1}\left(\sum_{\tau=1}^{t-1}a_\tau r_\tau\right)
\end{align*}

for some hyper-parameter $\lambda>0$ ($a_\tau$ is the action taken at round $\tau$, and $r_\tau$ is the reward received at round $t$). The action chosen at round $t$ is

\begin{align}
a_t = \argmax_{a\in\calA_t} \max_{w\in\calW_t} a^\top w.   \label{eq: action OFUL}
\end{align}

To make this algorithm robust to corruption, a natural modification is to widen the confidence set eq: confidence OFUL. That is, the confidence set is changed to

\begin{align}
\calW_t = \left\{ w~:~ \|w-\widehat{w}_t\|_{\Lambda_t}^{2}\leq \iota_t' \right\} \label{eq: robust OFUL conf set}
\end{align}

for some $\iota_t' > \iota_t$. The definition of $\iota_t'$ may involve the knowledge of $C^\am$. Below we show a regret lower bound for this class of algorithms.

We consider the following example for $d=1$. The action set in each round is the following:

\begin{align*}
\calA_t = \begin{cases}
\{-1, 1\}   &\text{if } 1\leq t\leq C \\
\{-\epsilon, \epsilon\} &\text{if } t>C
\end{cases}
\end{align*}

for some $C\in \mathbb{N}$.
The true underlying parameter is $w^\star=1$, but in rounds $1, 2, \ldots, C$, the rewards are generated using $w'=-1$. We assume that there is no noise, i.e., $r_t=a_t w'$ for $t\in[1,C]$ and $r_t=a_t w^\star$ for $t>C$.

In this case, the confidence set eq: robust OFUL conf set can be written as

\begin{align}
\calW_t = \left\{w~:~ (w-\widehat{w}_t)^2 \leq \frac{\iota_t'}{\Lambda_t}\right\} \label{eq: confidence 1d}
\end{align}

where $\Lambda_t = \lambda + \sum_{\tau=1}^{t-1}a_\tau^2$ and

\begin{align*}
\widehat{w}_t &= \frac{1}{\Lambda_t} \sum_{\tau=1}^{t-1}a_\tau r_\tau.
\end{align*}

By the reward generation process and the definition of action sets, we have that

\begin{align*}
\sum_{\tau=1}^{t-1}a_\tau r_\tau
&=  \sum_{\tau=1}^{t-1}  a_\tau \left(\one[\tau\leq C]a_\tau  w' + \one[\tau >C] a_\tau w^\star\right) \\
\begin{cases}
(t-1)w'=-t+1   &\text{if } t\leq C\\
Cw' + (t-1-C)\epsilon^2 w^\star  = -C + (t-1-C)\epsilon^2 &\text{if } t> C
\end{cases}
\end{align*}

Therefore, $\widehat{w}_t<0$ for $2\leq t \leq C\left(1+\frac{1}{\epsilon^2}\right)$. Since the confidence set $\calW_t$ (eq: confidence 1d) is symmetric around $\widehat{w}_t$, by the action selection rule eq: action OFUL, when  $\widehat{w}_t<0$, the learner will choose action $-1$ if $t\leq C$, and $-\epsilon$ if $t>C$.

Therefore, the learner will choose sub-optimal actions in $2\leq t \leq C\left(1+\frac{1}{\epsilon^2}\right)$, and the regret is of order

\begin{align*}
&\sum_{t=2}^{C} w^\star(1-(-1)) + \sum_{t=C+1}^{\min\{C(1+\nicefrac{1}{\epsilon^2)}, T\}}w^\star(\epsilon-(-\epsilon))
\\
&=(C-1)\times 2 + \min\left\{\frac{C}{\epsilon^2}, T-C\right\}\times 2\epsilon = \Theta\left(C+\min\left\{\frac{C}{\epsilon}, \epsilon T\right\}\right).
\end{align*}

By picking $\epsilon=\sqrt{\frac{C}{T}}$, we see that the regret is at least of order $\sqrt{CT}$. Finally, notice that in the example we construct $C^\am=\Theta(C)$, hence proving our claim.

§ CONCENTRATION INEQUALITIES

Let $\calF_0\subset \calF_1 \subset\cdots \subset \calF_{n}$ be a filtration, and $X_1, \ldots, X_n$ be real random variables such that $X_i$ is $\calF_i$-measurable, $\E[X_i|\calF_{i-1}]=0$, $|X_i|\leq b$, and $\sum_{i=1}^n \E[X_i^2|\calF_{i-1}]\leq V$ for some fixed $b\geq 0$ and $V\geq 0$. Then with probability at least $1-\delta$,

\begin{align*}
\sum_{i=1}^n X_i \leq 2\sqrt{V\log(1/\delta)} + b\log(1/\delta).
\end{align*}

Let $\calF_0\subset \calF_1 \subset\cdots \subset \calF_{n}$ be a filtration, and $X_1, \ldots, X_n$ be real random variables such that $X_i$ is $\calF_i$-measurable, $\E[X_i|\calF_{i-1}]=0$, $|X_i|\leq b$, for some fixed $b\geq 0$. Let $V_n = \sum_{i=1}^n \E[X_i^2|\calF_{i-1}]$. Then with probability at least $1-\delta$,

\begin{align*}
\sum_{i=1}^n X_i \leq 2\sqrt{V_n\log(n/\delta)} + 3b\log(n/\delta).
\end{align*}

Let $\calF_0\subset \calF_1 \subset\cdots \subset \calF_{n}$ be a filtration, and $X_1, \ldots, X_n$ be real random variables such that $X_i$ is $\calF_i$-measurable, $\E[X_i|\calF_{i-1}]=0$, $|X_i|\leq b$, for some fixed $b\geq 0$. Let $\widehat{\mu}_n=\frac{1}{n}\sum_{i=1}^n X_i$ and $\widehat{V}_n = \sum_{i=1}^n (X_i - \widehat{\mu}_n)^2$. Then with probability at least $1-3\delta$,

\begin{align*}
\sum_{i=1}^n X_i\leq 2\sqrt{2\widehat{V}_n \log(n/\delta)} + 11b\log(n/\delta).
\end{align*}

By Azuma's inequality, with probability at least $1-\delta$,

\begin{align}
\left|\widehat{\mu}_n\right|
= \left| \frac{1}{n}\sum_{i=1}^n X_i \right| \leq b\sqrt{\frac{2\log(2/\delta)}{n}}.     \label{eq: using Azuma}
\end{align}

Let $V_n=\sum_{i=1}^n \E[X_i^2|\calF_{i-1}]$. Then with probability $1-2\delta$, we have

\begin{align*}
&V_n - \sum_{i=1}^n \left(X_i - \widehat{\mu}_n\right)^2 \\
&= \left(V_n - \sum_{i=1}^n X_i^2\right) + n\widehat{\mu}_n^2 \\
&\leq 2\sqrt{\sum_{i=1}^n \E[X_i^4|\calF_{i-1}] \log(n/\delta)} + 3b^2\log(n/\delta) + 2b^2\log(2/\delta)   \tag{using \pref{lem: freedman} with  $X_i'=\E[X_i^2|\calF_{i-1}]-X_i^2$ and \pref{eq: using Azuma}} \\
&\leq 2b\sqrt{ V_n \log(n/\delta)} + 5b^2\log(n/\delta) \\
&\leq \frac{1}{2}V_n + 7b^2\log(n/\delta).   \tag{AM-GM}
\end{align*}

Rearranging the inequality above and using the definition of $\widehat{V}_n$, we get

\begin{align}
V_n \leq 2\widehat{V}_n + 14b^2 \log(n/\delta). \label{eq: Vn and hatVn}
\end{align}

Using lem: freedman again, we have that with probability at least $1-3\delta$,

\begin{align*}
\sum_{i=1}^n X_i
&\leq 2\sqrt{V_n\log(n/\delta)} + 3b\log(n/\delta),   \tag{w.p. $\geq 1-\delta$} \\
&\leq 2\sqrt{2\widehat{V}_n\log(n/\delta) + 14b^2\log^2(n/\delta)} + 3b\log(n/\delta)  \tag{\pref{eq: Vn and hatVn} holds w.p. $\geq 1-2\delta$ }\\
&\leq 2\sqrt{2\widehat{V}_n\log(n/\delta)} + 11b\log(n/\delta). \tag{$\sqrt{a+b}\leq \sqrt{a}+\sqrt{b}$}
\end{align*}

Let $\calF_0\subset \calF_1 \subset\cdots \subset \calF_{T}$ be a filtration, and $X_1, \ldots, X_T$ be real random variables such that $X_t$ is $\calF_t$-measurable, $\E[X_t|\calF_{t-1}]=0$, $|X_t|\leq b$, for some fixed $b\geq 0$. Let $z_t\sim \text{Bernoulli}(\alpha)$ be an i.i.d. random variable independent of all other variables, and let $0\leq y_t\leq b$ be a deterministic scalar given $\calF_{t-1}$.  Then with probability at least $1-\delta$, the following holds for all $\calI=[t_1, t_2]\subseteq [1, T]$:

\begin{align*}
\left|\sum_{t\in\calI}y_t(z_t-\alpha)\right| \leq \min\left\{4\sqrt{\alpha\sum_{t\in\calI} y_t^2 \log(T/\delta)} + 9b\log(T/\delta)
, \ \ \ \frac{1}{4}\alpha \sum_{t\in\calI}y_t + 21b\log(T/\delta)\right\}.
\end{align*}

Fixing an interval $\calI\in[1, T]$, we apply lem: freedman with $X_t=y_t(z_t-\alpha)$. Then we get that with probability at least $1-2\delta'$,

\begin{align*}
\left|\sum_{t\in\calI} y_t(z_t-\alpha)\right|
&\leq 2\sqrt{\sum_{t\in\calI} y_t^2\E_t[(z_t-\alpha)^2] \log(T/\delta')} + 3b\log(T/\delta')   \tag{define $\E_t[\cdot]=\E[\cdot|\calF_{t-1}]$} \\
&\leq 2\sqrt{\alpha\sum_{t\in\calI} y_t^2 \log(T/\delta')} + 3b\log(T/\delta')   \tag{$\E_t[(z_t-\alpha)^2]=\alpha(1-\alpha)^2+(1-\alpha)\alpha^2\leq \alpha$} \\
&\leq 2\sqrt{b\log(T/\delta')}\sqrt{\alpha\sum_{t\in\calI} y_t } + 3b\log(T/\delta')  \tag{$|y_t|\leq b$} \\
&\leq \frac{1}{4}\alpha\sum_{t\in\calI} y_t + 7b\log(T/\delta')   \tag{AM-GM}
\end{align*}

Notice that there are $\frac{T(T-1)}{2}$ different $\calI$'s, so we pick $\delta'=\frac{\delta}{T(T-1)}$, and take an union bound over $\calI$'s. This gives the desired bound.

§ OMITTED PROOFS IN SEC: MAIN ALG

We start with some extra notations to be used in this section.

For any time $t$, base algorithm $i$, and policy $\pi$, define
$C_{t,i}^{\am}\triangleq \sum_{\tau=1}^t \one[i_\tau=i]c_\tau$ and $C^{\rms}_{t,i}\triangleq \sqrt{\left(\sum_{\tau=1}^t \one[i_\tau=i]\right)\left(\sum_{\tau=1}^t  \one[i_\tau=i]c_\tau^2\right)}$ . Similarly, when we write $C_{t,i}$ to indicate either $C_{t,i}^\am$ or $C_{t,i}^\rms$, depending on the type of base algorithms we use.

For any time $t$, base algorithm $i$, and policy $\pi$, define $R_{t,i}^\pi=\sum_{\tau=1}^t \one[i_\tau=i] r_{\tau}^\pi$ .

Next, we prove some lemmas to be used in the later analysis.

In (alg: regret balancing all), for any fixed $i$, with probability at least $1-2\delta$, the following holds for all $t$:

\begin{align*}
\frac{3}{4}\alpha_i t - 21\log(T/\delta)\leq N_{t,i} \leq \frac{5}{4}\alpha_i t + 21\log(T/\delta).
\end{align*}

This is by directly applying lem: aux0 with $y_t=1$ and $\alpha=\alpha_i$

For any fixed $i$, with probability at least $1-3\delta$, the following holds for all $t$:

\begin{align*}
C^\am_{t,i} &\leq 1.25\alpha_i C_t^\am+21c_{\max}\log(T/\delta), \\
C^\rms_{t,i} &\leq 1.25\alpha_i C^\rms_t + 8c_{\max} \sqrt{\alpha_i t\log(T/\delta)} + 21c_{\max}\log(T/\delta).
\end{align*}

We prove the lemma for $(C_{t,i}, C)=(C^\am_{t,i}, C^\am)$ and $(C_{t,i}, C)=(C^\rms_{t,i}, C^\rms)$
cases separately.

Case 1.$(C_{t,i}, C)=(C^\am_{t,i}, C^\am)$.
\begin{align*}
C_{t,i} = \sum_{\tau=1}^t c_\tau\one[i_\tau=i] \leq \frac{5}{4}\alpha_i C +  21c_{\max}\log(T/\delta). \tag{holds w.p. $\geq 1-\delta$ by \pref{lem: aux0} with $y_\tau=c_\tau$, $z_\tau=\one[i_\tau=i]$}
\end{align*}

Case 2.$(C_{t,i}, C)=(C^\rms_{t,i}, C^\rms)$.
\begin{align*}
C_{t,i} &= \sqrt{\left(\sum_{\tau=1}^t\one[i_\tau=i]\right)\left(\sum_{\tau=1}^t\one[i_\tau=i]c_\tau^2\right)}\\
&\leq \sqrt{\left(\frac{5}{4}\alpha_i t +  21\log(T/\delta)\right)\left(\frac{5}{4}\alpha_i\sum_{\tau=1}^t c_\tau^2 + 21c_{\max}^2\log(T/\delta)\right)}  \tag{holds w.p. $\geq 1-2\delta$ by \pref{lem: aux0} with $y_\tau=1$ and $y_\tau=c_\tau^2$} \\
&\leq \sqrt{\frac{25}{16}\alpha_i^2 t \sum_{\tau=1}^t c_\tau^2 + 52.5\alpha_i tc_{\max}^2\log(T/\delta) +  21^2c_{\max}^2\log^2(T/\delta)}   \\
&\leq \frac{5}{4}\alpha_i \sqrt{t\sum_{\tau=1}^t c_\tau^2} + 8c_{\max}\sqrt{\alpha_i t\log(T/\delta)} + 21c_{\max}\log(T/\delta) \tag{$\sqrt{a+b+c}\leq \sqrt{a}+\sqrt{b}+\sqrt{c}$} \\
&= \frac{5}{4}\alpha_i C + 8c_{\max}\sqrt{\alpha_i t\log(T/\delta)} + 21 c_{\max}\log(T/\delta).
\end{align*}

For any $i$, with probability at least $1-\order(\delta)$, the following holds for all $t$ such that $C_t\leq 2^i$:

\begin{align*}
R_{t,i}^{\pistar} - R_{t,i} \leq \calR(N_{t,i}, \theta_i).
\end{align*}

The total amount of corruption experienced by $\alg_i$ up to round $t$ is $C_{t,i}$, whose upper bound is given in lem: aux1 for both types of base algorithms. Comparing the upper bounds of $C_{t,i}$ with our choice of $\theta_i$ in eq: choice of thres, we see that for a fixed $i$, under the condition $C_t \leq 2^i$, we have $C_{t,i}\leq \theta_i$ with probability $1-\order(\delta)$. In other words, the condition specified in assum: regret is satisfied for $\alg_i$ in the rounds that it is executed. Therefore, by the regret bound in assum: regret, we have

\begin{align*}
R_{t,i}^{\pistar} - R_{t,i}  = \sum_{\tau=1}^t (r^{\pistar}_\tau - r_\tau)\one[i_\tau=i] \leq \calR(N_{t,i}, \theta_i).
\end{align*}

For any fixed $i$, with probability at least $1-\delta$, the following holds for all $t$:

\begin{align*}
\left|\frac{1}{\alpha_i}R^{\pistar}_{t,i} - \sum_{\tau=1}^t r^{\pistar}_{t,i}\right|
\leq 2\sqrt{\frac{t\log(T/\delta)}{\alpha_i}} + \frac{\log(T/\delta)}{\alpha_i}.
\end{align*}

By lem: beygel freedman, for a fixed $i$, with probability $1-\delta$, for all $t$,

\begin{align*}
\left|\frac{1}{\alpha_i}R^{\pistar}_{t,i} - \sum_{\tau=1}^t r^{\pistar}_{t,i}\right|
%&=  \left|\frac{1}{\alpha_i t}\sum_{\tau=1}^t \one[i_\tau=i]R_\tau^\pi -\frac{1}{\alpha_j t}\sum_{\tau=1}^t \one[i_\tau=j]R_\tau^\pi \right|  \nonumber \\
&= \left| \sum_{\tau=1}^t \left(\frac{\one[i_\tau=i]}{\alpha_i} - 1\right)r^{\pistar}_\tau \right|
\leq 2\sqrt{\frac{t\log(T/\delta)}{\alpha_i}} + \frac{\log(T/\delta)}{\alpha_i}.
\end{align*}

of lem: istar = k case.
Notice that $C_t\leq 2^k$ implies that $C_t\leq 2^i$ for all $i\in[k, k_{\max}]$.

Notice that

\begin{align}
R_{t,i} - R_{t,i}^{\pi^\star}
&= \sum_{\tau=1}^t \one[i_\tau=i](r_\tau - r_\tau^{\pi^\star})  \nonumber  \\
&= \sum_{\tau=1}^t \one[i_\tau=i]\left( r_\tau - \mu^{\pi_\tau}(x_\tau) + \underbrace{\mu^{\pi_\tau}(x_\tau) - \mu^{\pi^\star}(x_\tau)}_{\leq 0 \text{ (by \pref{assum: realizable})}}  + \mu^{\pi^\star}(x_\tau)  - r_\tau^{\pistar}\right)  \nonumber\\
&\leq \sum_{\tau=1}^t \one[i_\tau=i]\left(r_\tau - \mu^{\pi_\tau}_\tau(x_\tau) + \mu_\tau^{\pistar}(x_\tau) - r^{\pistar}_\tau\right) + 2C^{\am}_{t,i} \tag{$|\mu_\tau^{\pi}(x_\tau)-\mu^{\pi}(x_\tau)|\leq c_\tau$ for all $\pi$ and $\tau$} \\
&\leq 2\sqrt{2\alpha_i t\log(T/\delta)} + 6\log(T/\delta) + 2C_{t,i} %\left(\frac{4C^\am}{t} + \frac{8c_{\max}}{\alpha_i t}\right)\log(T/\delta)
\tag{by \pref{lem: freedman} with an union bound over $t$, and that $C^\am_{t,i}\leq C^{\rms}_{t,i}$}  \\
&\leq 2\sqrt{2\alpha_i t\log(T/\delta)} + 6\log(T/\delta) + 2\thres_i.   \tag{$C_{t,i}\leq \thres_i$ with high probability by \pref{lem: aux1}} \\
&  \label{eq: keyy eq 2}
\end{align}

Combining lem: easy lemma 1 and lem: easy lemma 2, we see that the performance of $\alg_i$ admits the following lower bound with probability at least $1-\order(\delta)$:

\begin{align}
\frac{R_{t,i}}{\alpha_i} \geq \frac{R^{\pistar}_{t,i} - \calR(N_{t,i}, \thres_i)}{\alpha_i} \geq \sum_{\tau=1}^t r_\tau^{\pistar} - \frac{\calR(N_{t,i}, \thres_i)}{\alpha_i} - 2\sqrt{\frac{t\log(T/\delta)}{\alpha_i}} - \frac{\log(T/\delta)}{\alpha_i}.  \label{eq: lower eq}
\end{align}

Combining eq: keyy eq 2 and lem: easy lemma 2, we also have the following with probability at least $1-\order(\delta)$:

\begin{align}
\frac{R_{t,i}}{\alpha_i} &\leq
\frac{R_{t,i}^{\pistar}}{\alpha_i} + 3\sqrt{\frac{t\log(T/\delta)}{\alpha_i}} + \frac{6\log(T/\delta) + 2\thres_i}{\alpha_i} \nonumber
\\
&\leq \sum_{\tau=1}^t r_\tau^{\pistar} + 5\sqrt{\frac{t\log(T/\delta)}{\alpha_i}} + \frac{7\log(T/\delta)+ 2\thres_i}{\alpha_i}. \label{eq: upper eq}
\end{align}

The bounds eq: lower eq and eq: upper eq together with an union bound over $i$'s indicate that the following holds for all $i, j\in[k, k_{\max}]$ with probability $1-\order(k_{\max}\delta)$:

\begin{align*}
\frac{R_{t,i}}{\alpha_i} +  \frac{\calR(N_{t,i}, \thres_i)}{\alpha_i} + 2\sqrt{\frac{t\log(T/\delta)}{\alpha_i}} + \frac{\log(T/\delta)}{\alpha_i}
\geq \sum_{\tau=1}^t r_\tau^{\pistar}  \geq \frac{R_{t,j}}{\alpha_j} -  5\sqrt{\frac{t\log(T/\delta)}{\alpha_j}} - \frac{7\log(T/\delta)+ 2\thres_j}{\alpha_j}.
\end{align*}

Further combined with the fact that $\alpha_i\geq \alpha_j$ since $i\leq j$, the last inequality implies that the termination condition eq: terminate condition 1 will not hold.

of lem: general regret.

\begin{align}
\sum_{t=1}^{L_0}\left(r_{t}^{\pi^\star} - r_t\right) \leq 1+ \sum_{i=k}^{k_{\max}} \sum_{t=1}^{L_0-1}\left(r_{t}^{\pi^\star} - r_t\right)\one[i_t=i] = 1 + \sum_{i=k}^{k_{\max}}  \left(R_{L_0-1,i}^{\pi^\star} - R_{L_0-1,i}\right). \label{eq: deompose}
\end{align}

For $i\geq i^\star$, since the corruption level is well-specified, by lem: easy lemma 1, with probability at least $1-\order(\delta)$,

\begin{align}
R_{L_0-1,i}^{\pi^\star} - R_{L_0-1,i} \leq \calR(N_{L_0-1,i},\thres_i). \label{eq: well specified case}
\end{align}

For $i<i^\star$,  with probability $1-\order(\delta)$,

\begin{align}
\frac{R_{L_0-1, i}}{\alpha_i}
&\geq \frac{R_{L_0-1, i^\star}}{\alpha_{i^\star}} - \frac{\calR(N_{L_0-1,i},\thres_i)}{\alpha_i} - \order\left(\sqrt{\frac{(L_0-1)\log(T/\delta)}{\alpha_{i^\star} }} + \frac{\thres_{i^\star} + \log(T/\delta) }{\alpha_{i^\star}}\right)   \tag{by the termination condition \pref{eq: terminate condition 1}} \\
&\geq \frac{R_{L_0-1, i^\star}^{\pi^\star}}{\alpha_{i^\star}} - \frac{\calR(N_{L_0-1,i},\thres_i)}{\alpha_i } - \otil\left(\sqrt{\frac{L_0}{\alpha_{i^\star}}} + \frac{\calR(N_{L_0-1,i^\star},\theta_{i^\star})}{\alpha_{i^\star}}\right) \tag{by \pref{lem: easy lemma 1} and that $\calR(\cdot, \theta)\geq \theta$} \\
&\geq \frac{R_{L_0-1, i}^{\pi^\star}}{\alpha_{i^\star}} - \frac{\calR(N_{L_0-1,i},\thres_i)}{\alpha_i} - \otil\left(\sqrt{\frac{L_0}{\alpha_{i^\star}}} + \frac{\calR(N_{L_0-1,i},\theta_{i^\star})}{\alpha_{i^\star}}\right) \label{eq: i < istar case}
\end{align}

where the last inequality is because by lem: easy lemma 2 we have

\begin{align*}
\left|\frac{1}{\alpha_i}R^{\pi^\star}_{L_0-1,i} - \frac{1}{\alpha_{i^\star}}R^{\pi^\star}_{L_0-1,i^\star}\right|\leq \otil\left(\sqrt{\frac{L_0}{\alpha_i}} + \frac{1}{\alpha_i} + \sqrt{\frac{L_0}{\alpha_{i^\star}}} + \frac{1}{\alpha_{i^\star}}\right) = \otil\left( \sqrt{\frac{L_0}{\alpha_{i^\star}}} + \frac{1}{\alpha_{i^\star}}\right).
\end{align*}

Combining eq: i < istar case with eq: deompose and eq: well specified case and an union bound over $i$'s, we get that with probability at least $1-\order(k_{\max}\delta)$,

\begin{align}
&\sum_{t=1}^{L_0}\left(r_{t}^{\pi^\star} - r_t\right) \nonumber \\
&\leq 1+\sum_{i=k}^{k_{\max}} \calR(N_{L_0-1, i}, \thres_i) + \sum_{i<i^\star} \alpha_{i} \times \otil\left(\sqrt{\frac{L_0}{\alpha_{i^\star}}} +  \frac{\calR(N_{L_0-1,i^\star},\theta_{i^\star})}{\alpha_{i^\star}}\right)  \nonumber  \\
&\leq 1+\sum_{i=k}^{k_{\max}} \calR(N_{L_0-1, i}, \thres_i) + \otil\left( \one[i^\star > k] \left(\sqrt{\frac{L_0}{\alpha_{i^\star}}} + \frac{\calR(N_{L_0-1,i^\star},\theta_{i^\star})}{\alpha_{i^\star}}\right)\right)  \label{eq: combine regret meta}
%&= \otil\left(L\frac{\calR(N_{T_0-1,i^\star},\tilde C)}{N_{T_0-1,i^\star}}\right) \\
%&=\otil\left(L\frac{\calR(\frac{\tilde C}{C} L,\tilde C)}{\frac{\tilde C}{C} L}\right) \\
%&= \otil\left(\calR(L,C)\right)\,.
\end{align}

where in the last inequality we use $\sum_{i<i^\star}\alpha_i\leq 1$.

of thm: form 1 regret.
Recall that we define

\begin{align*}
Z = \begin{cases}
c_{\max}   &\text{if $\alg$ is \typea},\\
c_{\max}\sqrt{T}  &\text{if $\alg$ is \typer}.
\end{cases}
\end{align*}

Let $i^\star$ be the smallest $i\in[k, k_{\max}]$ such that $C\leq 2^i$.
By lem: general regret and by the choice of $\thres_i$ in eq: choice of thres, with probability at least $1-\order(k_{\max}\delta)$, the regret within an epoch is upper bounded by

\begin{align*}
&\otil\left(\sum_{i=k }^{k_{\max}}\left( \sqrt{\beta_1  \alpha_i T } + \beta_2 \alpha_i 2^i + \beta_2 Z + \beta_3\right) + \one[k<i^\star]\left(\sqrt{\frac{T}{\alpha_{i^\star}}} +  \frac{\sqrt{\beta_1\alpha_{i^\star}T}+ \beta_2 \alpha_{i^\star}2^{i^\star} + \beta_2 Z +  \beta_3}{\alpha_{i^\star}} \right) \right) \\
&= \otil\left( \sqrt{\beta_1 T} + \beta_2 2^k + \beta_2z + \beta_3 + \one[k<i^\star]\left(\sqrt{\frac{\beta_1 T}{\alpha_{i^\star}}} + \beta_2 2^{i^\star} + \frac{ \beta_2z + \beta_3}{\alpha_{i^\star}}\right)  \right)  \tag{$\alpha_i 2^i\leq 2^k$ by the choice of $\alpha_i$} \\
&= \otil\left( \sqrt{\beta_1 T} + \beta_2 (2^k + 2^{i^\star})  + \beta_2 Z  + \beta_3 + \sqrt{\frac{\beta_1 T\cdot 2^{i^\star}}{2^k}} + \frac{(\beta_2 Z  + \beta_3)  2^{i^\star}}{2^k} \right) \tag{by the choice of $\alpha_{i^\star}$}\\
&= \otil\left( \sqrt{\beta_1 T} + \beta_2 (2^k + 2^{i^\star}) + \beta_2 Z  + \beta_3 + \beta_2 2^{i^\star} + \frac{\beta_1 T}{\beta_2 2^k} + \beta_2 2^{i^\star}\times \frac{ \beta_2 Z  + \beta_3}{\beta_2 2^k}\right)   \tag{AM-GM}\\
&= \otil\left(\sqrt{\beta_1 T} + \beta_2 (2^k + 2^{i^\star}) + \beta_2 Z  + \beta_3 \right).  \tag{using $\beta_2 2^k\geq \sqrt{\beta_1 T} + \beta_2 Z + \beta_3$ by the choice of $k_{\init}$}
\end{align*}

Notice that in we start from $k=k_{\init}$. If $k_{\init}\geq i^\star$, then by lem: istar = k case, the algorithm will run with $k=k_{\init}$ throughout all $T$ rounds. On the other hand, if $k_{\init} < i^\star$, the $k$ used in might increase from $k_{\init}$. However, if $k=i^\star$ is ever reached, again by lem: istar = k case, the learner will use this $k$ throughout the rest of the steps. In short, the $k$'s used in are upper bounded by $\max\{k_{\init}, i^\star\}$ with high probability. Since there are at most $\order(k_{\max})$ epochs, the overall regret is upper bounded by

\begin{align*}
&\order(k_{\max}) \times \otil\left(\sqrt{\beta_1 T} + \beta_2 (2^{\max\{k_{\init}, i^\star\}} + 2^{i^\star}) + \beta_2 Z + \beta_3 \right) = \otil\left(\sqrt{\beta_1 T} + \beta_2 (C + Z) + \beta_3\right)
\end{align*}

with probability at least $1-\order(k_{\max}^2\delta)$
Considering the difference definitions of $Z$ for and base algorithms finishes the proof.

§ OMITTED PROOFS IN SEC: PHASEONE

of lem: form 1 regret with gap.
By lem: general regret,
\begin{align*}
&\sum_{t=1}^{L_0}(r^{\pistar}_t - r_t) \\
&\leq  \sum_{i=k}^{k_{\max}} \left(\min\left\{\sqrt{\beta_1 N_{L_0,i}  }, \ \frac{\beta_1}{\Delta}\right\} + \beta_2 \alpha_i 2^i + \beta_2 c_{\max} + \beta_3 \right) \\
&\qquad \qquad  + \otil\left( \sqrt{\frac{L}{\alpha_{i^\star}}} + \frac{\min\left\{ \sqrt{\beta_1 N_{L_0,i^\star}}, \frac{\beta_1}{\Delta}\right\} + \beta_2 \alpha_{i^\star}2^{i^\star} + \beta_2 c_{\max} + \beta_3}{\alpha_{i^\star}} \right)\\
&\leq \otil\left(\sqrt{\beta_1 L} + \beta_2 (2^k + 2^{i^\star}) + \frac{\beta_2 c_{\max} + \beta_3}{\alpha_{i^\star}} + \sqrt{\frac{L}{\alpha_{i^\star}}} + \frac{\sqrt{\beta_1 N_{L_0, i^\star}}}{\alpha_{i^\star}} \right)  \tag{by the definition of $\alpha_i$, $\alpha_i 2^i=\order(2^k + \sqrt{\beta_1 L}/\beta_2)$} \\
&= \otil\left(\beta_2 (2^k + 2^{i^\star}) + \frac{\sqrt{\beta_1} + \beta_2 c_{\max} + \beta_3}{\alpha_{i^\star}} + \sqrt{\frac{\beta_1 L}{\alpha_{i^\star}}} \right) \tag{using $N_{L_0, i^\star}=\otil\left(\alpha_{i^\star}L_0 + 1\right)$ by \pref{lem: relate N and alpha}} \\
&= \otil\left( \beta_2(2^k + 2^{i^\star}) + \left(\sqrt{\beta_1} + \beta_2 c_{\max} + \beta_3\right)\left(1 + \frac{2^{i^\star}}{\frac{\sqrt{\beta_1L}}{\beta_2} + 2^k}\right) + \sqrt{\beta_1 L\left(1 + \frac{2^{i^\star}}{\frac{\sqrt{\beta_1L}}{\beta_2} + 2^k}\right)}  \right)   \tag{by the definition of $\alpha_{i^\star}$} \\
&= \otil\left( \beta_2(2^k + 2^{i^\star}) + \left(\sqrt{\beta_1} + \beta_2 c_{\max} + \beta_3\right)\left(1 + \frac{\beta_2 2^{i^\star}}{\beta_2 2^k}\right) + \sqrt{\beta_1 L\left(1 + \frac{\beta_2 2^{i^\star}}{\sqrt{\beta_1L}}\right)}  \right) \\
&= \otil\left( \sqrt{\beta_1 L} + \beta_2 2^{i^\star} + \beta_2 c_{\max} + \beta_3 +  \sqrt{\sqrt{\beta_1 L} \times \beta_2 2^{i^\star}} \right)    \tag{$\beta_2 2^k\geq \beta_22^{k_{\init}}\geq \sqrt{\beta_1} + \beta_2c_{\max} + \beta_3$ and $\beta_2 2^k\leq \sqrt{\beta_1 L}$ as chosen in \gapalgname}  \\
&=\otil\left( \sqrt{\beta_1 L} + \beta_2 C_{L_0} + \beta_2 c_{\max} + \beta_3 \right).  \tag{AM-GM and $2^{i^\star}=\order(\max\{C_{L_0}, 2^k\})$ by the definition of $i^\star$ in \pref{lem: general regret}}
\end{align*}

of lem: execute most times.
Since $2^k\geq 32C_{L_0} \geq 32C_t$ for all $t$ during execution, by lem: istar = k case, with probability at least $1-\order(k_{\max}\delta)$, eq: terminate condition 1 will not hold. Therefore, will finish all $L$ steps (thus $L_0=L$) and return true.
By lem: easy lemma 1, we have that for $\alg_k$, with probability $1-\order(\delta)$,

\begin{align*}
&\sum_{t=1}^L (r_t^{\pi^*} - r_{t})\one[i_t=k] \\
&\leq  \frac{\beta_1}{\Delta} + \beta_2 \thres_k + \beta_3 \\
&\leq  \frac{\beta_1}{\Delta} + \beta_2 \left(\frac{5}{4}\times 2^{k} + 21c_{\max}\log(T/\delta)\right) + \beta_3 \tag{by the definition of $\thres_k$} \\
&\leq \frac{2\beta_4}{\Delta} + \frac{5}{4}\beta_22^k. \tag{by the definition of $\beta_4$ and that $\Delta\leq 1$}
%&\leq  \frac{\beta_1}{\Delta} + 21\beta_2 c_{\max}\log(T/\delta) + \beta_3 + 80\left(\frac{\beta_1}{\Delta}+\beta_2 C + \beta_2 c_{\max}\log(T/\delta) + \beta_3\right) \\
%&\leq \frac{\beta_1}{\Delta}+\beta_2 C + \beta_2 c_{\max}\log(T/\delta) + \beta_3.
\end{align*}

On the other hand,

\begin{align*}
&\sum_{t=1}^L (r_t^{\pi^*} - r_{t})\one[i_t=k] \\
&\geq \sum_{t=1}^L (\mu^{\pi^*} - \mu^{\pi_t})\one[i_t=k] + \sum_{t=1}^L \left(r_t^{\pistar} - \mu_t^{\pistar}(x_t)+ \mu_t^{\pi_t}(x_t)-r_t^{\pi_t}\right)\one[i_t=k] - 2\sum_{t=1}^L  \max_{\pi}|\mu^\pi-\mu_t^\pi|\\
&\geq \Delta \left(\sum_{t=1}^L\one[\pi_t\neq \pi^*]\one[i_t=k]\right) - 8\sqrt{\sum_{t=1}^L \one[\pi_t\neq \pi^*]\one[i_t=k]\log(T/\delta)} - 18\log(T/\delta) - 2C_L \tag{by \pref{lem: aux0} with $y_t=\one[i_t=k]\one[\pi_t\neq \pi^\star]$, $X_t=r_t^{\pistar} - \mu_t^{\pistar}(x_t)+ \mu_t^{\pi_t}(x_t)-r_t^{\pi_t}$}\\
&\geq \frac{3}{4}\Delta \left(\sum_{t=1}^L\one[\pi_t\neq \pi^*]\one[i_t=k]\right) - \frac{34\log(T/\delta)}{\Delta} - 2C_L. \tag{AM-GM and that $\Delta\leq 1$}
\end{align*}

Combining the two inequalities above, and using that $\beta_1\geq 5\log(T/\delta), \beta_2 \geq 1, \beta_3\geq 5\log(T/\delta)$, we get

\begin{align}
&\sum_{t=1}^L  \one[\pi_t\neq \pi^*]\one[i_t=k] \nonumber \\
&\leq \frac{4}{3\Delta}\left( \frac{2\beta_4}{\Delta} + \frac{5}{4}\beta_2 2^{k} + \frac{34\log(T/\delta)}{\Delta} + 2C_L\right) \nonumber
\\
&\leq  \frac{4}{3\Delta}\left( \frac{2\beta_4}{\Delta} + \frac{7\beta_4}{\Delta} + 2C_L\right) + \frac{5}{3\Delta}\beta_22^k \tag{$\beta_4\geq \beta_1\geq 5\log(T/\delta)$} \\
&\leq \frac{4}{3\Delta}\beta_2 2^k + \frac{5}{3\Delta}\beta_2 2^k   \tag{by the condition specified in the lemma and that $L=L_0$}\\
&=   \frac{3\beta_2 2^k}{\Delta}.  \label{eq: upper bound alg k}
\end{align}

We also have

\begin{align}
&\sum_{t=1}^L \one[i_t=k] \nonumber \\
&\geq  \frac{3}{4}\alpha_k L - 21\log(T/\delta) \tag{by \pref{lem: relate N and alpha}} \nonumber \\
&\geq \frac{3}{8} \frac{(\beta_2 2^{k})^2}{\beta_4} - 5\beta_3   \tag{$\alpha_k\geq \frac{1}{2}$ and $\sqrt{\beta_4 L}\geq \beta_2 2^k$ and $\beta_3 \geq 5\log(T/\delta)$}  \nonumber \\
&\geq \frac{12\beta_2 2^k}{\Delta} - \beta_2 2^k   \tag{ $\beta_2 2^k \geq \frac{32\beta_4}{\Delta}\geq 32\beta_3$ by the condition specified in the lemma}\\
&\geq \frac{11\beta_2 2^k}{\Delta}. \tag{$\Delta\leq 1$} \\
%&\geq \frac{384\cdot(\beta_2 2^{j^\star})^2}{\beta_1} - 21\log(T/\delta)   \tag{$k=j^\star+5$} \\
%&\geq \frac{384}{\beta_1}\left( \frac{\beta_1}{\Delta} + \beta_2 C + \beta_2 c_{\max}\log(T/\delta) + \beta_3\right)^2 - 21\log(T/\delta)  \tag{by the definition of $j^\star$} \\
%&\geq 384\left( \frac{\beta_1}{\Delta^2} + \frac{2(\beta_2 C + \beta_2 c_{\max}\log(T/\delta)+\beta_3)}{\Delta} \right). \tag{using $\beta_3^2\geq \beta_1\log(T/\delta)$}\\
&\label{eq: lower bound alg k}
\end{align}

Combining eq: upper bound alg k and eq: lower bound alg k proves the lemma.

§ OMITTED PROOFS IN SEC: TWO-ARMED ALG

For , we define the following notations:

Let $\calE_j$ be the set of rounds in epoch $j$, i.e., $\calE_j\triangleq [t_j, t_{j+1}-1]$. Let $\calE_j'$ be the set of rounds in epoch $j$ except for the last round, i.e., $\calE_j'\triangleq [t_j, t_{j+1}-2]$ (might be empty if $t_{j+1}= t_j+1$).

Let $\calI\subseteq \calE_j$ be any interval in epoch $j$. Define
_, 0 ≜∑_t∈ [Y_t=0],            _, 1  ≜∑_t∈ [Y_t=1],

_, 0 ≜1/1-p_j ∑_t∈ [Y_t=0]r_t,            _, 1 ≜1/p_j ∑_t∈ [Y_t=1]r_t,

_, 0^π≜1/1-p_j ∑_t∈ [Y_t=0]r_t^π,            _, 1^π≜1/p_j ∑_t∈ [Y_t=1]r_t^π.

With abuse of notations, define $C_{\calI}\triangleq \sum_{\tau\in\calI}c_\tau$ (recall that we also define $C_t=\sum_{\tau=1}^t c_\tau$).

$\Theta_j\triangleq \frac{5}{4}p_jC_{\calE_j} + 21c_{\max}\log(T/\delta)$.

Below, we first establish some basic lemmas:

Let $\calR(t,\theta)=\sqrt{\beta_1 t} + \beta_2\thres + \beta_3$ with $\beta_3\geq 10\sqrt{\beta_1\log(T/\delta)}$. Then with probability at least $1-\order(\delta)$, the following holds for all $\calI=[t_j, t]\subseteq \calE_j$ and any $\theta\geq 0$:

\begin{align*}
\frac{1}{2}\calR(p_j |\calI|, \theta) \leq \calR(\Nht_{\calI,1}, \theta)\leq \frac{3}{2}\calR(p_j |\calI|, \theta).
\end{align*}

With probability at least $1-\order(\delta)$,

\begin{align*}
\calR(\Nht_{\calI,1}, \theta)
&= \sqrt{\beta_1  \Nht_{\calI,1}} + \beta_2\theta + \beta_3 \\
&\leq \sqrt{\frac{5}{4}\beta_1  p_j |\calI| + 21\beta_1 \log(T/\delta)} + \beta_2\theta + \beta_3   \tag{by the same argument as \pref{lem: relate N and alpha}} \\
&\leq \frac{3}{2}\sqrt{\beta_1 p_j |\calI|} + \beta_2\theta + 5\sqrt{\beta_1\log(T/\delta)} + \beta_3   \\
&\leq \frac{3}{2}\calR(p_j |\calI|, \theta). \tag{$\beta_3\geq 10\sqrt{\beta_1\log(T/\delta)}$} \\
\end{align*}

If $p_j |\calI|\geq 42\log(T/\delta)$, then

\begin{align*}
\calR(\Nht_{\calI,1}, \theta)
&= \sqrt{\beta_1  \Nht_{\calI,1}} + \beta_2\theta + \beta_3 \\
&\geq \sqrt{\frac{3}{4}\beta_1  p_j |\calI| - 21\beta_1 \log(T/\delta)} + \beta_2\theta + \beta_3 \tag{by the same argument as \pref{lem: relate N and alpha}}  \\
&\geq \frac{1}{2}\sqrt{\beta_1 p_j |\calI|} + \beta_2\theta + \beta_3 \\
&\geq \frac{1}{2}\calR(p_j |\calI|, \theta);
\end{align*}

otherwise, we have $p_j |\calI|< 42\log(T/\delta)$ and

\begin{align*}
\calR(\Nht_{\calI,1},\theta)
&\geq \beta_2\theta + \beta_3 \\
&\geq 5\sqrt{\beta_1 \log(T/\delta)} + \beta_2\theta + \frac{1}{2}\beta_3 \tag{$\beta_3\geq 10\sqrt{\beta_1\log(T/\delta)}$} \\
&\geq 5\sqrt{\beta_1 \times \frac{1}{42}p_j |\calI|} + \beta_2\theta + \frac{1}{2}\beta_3 \\
&\geq \frac{1}{2}\calR(p_j |\calI|, \theta).
\end{align*}

With probability at least $1-\order(\delta)$, for all interval $\calI=[t_j, t]\subseteq \calE_j$,

\begin{align}
\left|\Rht_{\calI,1} - |\calI| \mu^{\pi'} \right|
&\leq  \frac{3}{p_j}\calR_\calB\left(p_j|\calI|, \Theta_j\right),
\label{eq: inequ1} \\
\left|\Rht_{\calI,0} -  |\calI|\mu^{\hatpi}\right| &\leq 4\sqrt{|\calI|\log(1/\delta)} + 4\log(T/\delta) + C_\calI \leq \frac{1}{p_j}\calR_\calB(p_j |\calI|, \Theta_j).  \label{eq: inequ2}
\end{align}

where $\pi'=\argmax_{\pi'\in\Pi\backslash\{\hatpi\}}\mu^{\pi'}$.

By the same argument as lem: aux1, the corruption experienced by $\calB_{\hatpi}$ in $\calI$ is upper bounded by $\Theta_j$.  By the regret guarantee of $\calB_{\hatpi}$, we have with probability at least $1-\order(\delta)$,

\begin{align*}
\Rht_{\calI,1}
&\geq \Rht_{\calI,1}^{\pi'} - \frac{1}{p_j}\calR_\calB\left(\Nht_{\calI,1}, \Theta_j\right) \\
&\geq \sum_{t\in\calI} \mu^{\pi'}_t - 2\sqrt{\frac{2|\calI|\log(T/\delta)}{p_j}} - \frac{2\log(T/\delta)}{p_j} - \frac{2}{p_j} \calR_\calB\left(p_j|\calI|, \Theta_j\right)  \tag{by \pref{lem: beygel freedman} with a union bound over $|\calI|$ and \pref{lem: connecting Regret}} \\
&\geq |\calI| \mu^{\pi'} - C_{\calI} - 2\sqrt{\frac{2|\calI|\log(T/\delta)}{p_j}} - \frac{2\log(T/\delta)}{p_j} - \frac{2}{p_j} \calR_\calB\left(p_j|\calI|, \Theta_j\right) \\
&\geq |\calI|\mu^{\pi'} - \frac{3}{p_j}\calR_\calB\left(p_j|\calI|, \Theta_j\right).  \tag{by the assumption $\beta_1\geq 8\log(T/\delta), \beta_2 \geq 1, \beta_3\geq 5\log(T/\delta)$}
%&\geq |\calI| \mu^{\pi'} - \sqrt{\frac{|\calI|\log(T/\delta)}{p_j}} - \frac{1}{p_j} \left(\sqrt{\beta_1 p_j |\calI|}  + \beta_2  \left(3p_{j}C + 4c_{\max}\right)\log(T/\delta) + \beta_3 + \sqrt{\beta_1 \log(T/\delta)}\right)
%&2\sqrt{\frac{\beta_1|\calI|}{p_j}} - 3\beta_2 C \log(1/\delta) - \frac{2\beta_2 \log(1/\delta)}{p_j}
\end{align*}

Again by lem: beygel freedman with a union bound over $|\calI|$, we also have with probability $1-\order(\delta)$,

\begin{align*}
\Rht_{\calI,1}
&\leq \sum_{t\in\calI} \mu_t^{\pi'} + 2\sqrt{\frac{2|\calI|\log(T/\delta)}{p_j}} + \frac{2\log(T/\delta)}{p_j} \\
&\leq |\calI| \mu^{\pi'} + 2\sqrt{\frac{2|\calI|\log(T/\delta)}{p_j}} + \frac{2\log(T/\delta)}{p_j} + C_\calI\\
&\leq |\calI| \mu^{\pi'} + \frac{1}{p_j}\calR_\calB\left(p_j|\calI|, \Theta_j\right).  %\tag{by \pref{corr: connecting Regret}}
%&\lesssim V^{\pi'} + \frac{1}{8}\hatDelta +  \sqrt{\frac{2\beta_1}{|\calE_j|}} + \frac{2\beta_2 C}{|\calE_j|}  \tag{by the same calculation as above}
\end{align*}

Combining them, we get eq: inequ1. The first inequality in eq: inequ2 can be obtained by lem: beygel freedman with the fact that $1-p_j\geq \frac{1}{2}$ and $\left|\sum_{t\in\calI}\big(\mu_t^{\pi'} - \mu^{\pi'}\big)\right|\leq C_\calI$; the second inequality in eq: inequ2 can be obtained using the assumptions on $\beta_1, \beta_2, \beta_3$.

For all $j$, $\hatDelta_j\leq 1$.

When $j=1$, $\hatDelta_1\leq 1$ by definition. Assume that $j+1\geq 2$ is the first $j$ such that $\hatDelta_{j+1} > 1$. By the way we update $\hatDelta_j$, it must be that $\hatDelta_{j}\geq \frac{1}{1.25}$ and that at the end of epoch $j$, eq: checkk 2 is triggered.

However, notice that in eq: checkk 2, the left-hand side $\Rht_0 = \frac{1}{1-p_j}\sum_{\tau=t_{j}}^t r_\tau\one[Y_\tau=0]\leq \frac{1}{1-p_j}M_{j}\leq 2M_j$ since $p_j=\frac{\beta_4}{2M_j\hatDelta_j^2}\leq \frac{1}{2}$ by eq: doubling epoch length, but the right-hand side of eq: checkk 2 involves a term $3M_j\hatDelta_j\geq 3M_j\times \frac{1}{1.25} > 2M_j$. Therefore, eq: checkk 2 is impossible to be triggered at this $j$, contradicting our assumption.

With probability at least $1-\order(\delta)$, for all interval $\calI=[t_j, t]\subseteq \calE_j$,

\begin{align*}
\frac{1}{p_j}\calR_{\calB}\left(\Nht_{\calI, 1}, \Theta_j\right)\leq \frac{2}{p_j}\calR_{\calB}\left(p_j|\calI|, \Theta_j+ \frac{p_j\sqrt{\beta_1 L}}{\beta_2}\right) \leq 0.02M_j\hatDelta_j + 2.5\beta_2 C_{\calE_j}\log(T/\delta) +  2\sqrt{\beta_1 L}.
\end{align*}

\begin{align*}
&\frac{1}{p_j}\calR_{\calB}\left(\Nht_{\calI, 1}, \Theta_j\right)\\
&\leq  \frac{2}{p_j}\calR_\calB\left(p_j|\calI|, \Theta_j + \frac{p_j\sqrt{\beta_1 L}}{\beta_2}\right) \tag{by \pref{lem: connecting Regret}}\\
&= 2\left(\sqrt{\frac{\beta_1|\calI|}{p_j}} + \frac{\beta_2\Theta_j}{p_j} + \frac{\beta_3}{p_j}\right) + 2\sqrt{\beta_1 L} \\
&\leq 2\left( \sqrt{\frac{2\beta_1}{\beta_4}|\calI|M_j}\hatDelta_j + \frac{5}{4}\beta_2C_{\calE_j} + \frac{21\beta_2 c_{\max}\log(T/\delta)+\beta_3}{\beta_4}\times 2 M_j\hatDelta_j^2 \right) + 2\sqrt{\beta_1 L} \\
%&\qquad \qquad \qquad \quad + 2\left(\sqrt{\beta_1 |\calE_j|} + \beta_2\Theta_j + \beta_3\right) \\
&\leq 0.02M_j\hatDelta_j + 2.5 \beta_2 C_{\calE_j} +  2\sqrt{\beta_1 L}.   \tag{by the definition of $\beta_4$ and that $\hatDelta_j\leq 1$ by \pref{lem: delta smaller than 1}}
\end{align*}

of lem: corral regret 1.
Let $T_0$ be the round at which terminates. In the following proof, we assume that the high-probability events defined in previous lemmas hold.

Case 1. $\hatpi\neq \pistar$.

\begin{align*}
&\sum_{t\in\calE_j'} (r_t^{\pi^\star} - r_t) \\
&= (1-p_j)\left(\Rht^{\pistar}_{\calE_j',0} - \Rht^{\hatpi}_{\calE_j',0}\right) + p_j\left(\Rht^{\pistar}_{\calE_j',1} - \Rht_{\calE_j',1}\right) \\
&\leq (1-p_j)\left(\Rht^{\pistar}_{\calE_j',1} - \Rht_{\calE_j',0}\right) + (1-p_j)\left(2\sqrt{\frac{2|\calE_j'|\log(T/\delta)}{p_j}} + \frac{2\log(T/\delta)}{p_j}\right) + p_j\left(\Rht^{\pistar}_{\calE_j',1} - \Rht_{\calE_j',1}\right)   \tag{when $Y_t=0$ we execute $\hatpi$, and by \pref{lem: beygel freedman}} \\
&\leq (1-p_j)\left(\Rht_{\calE_j',1} - \Rht_{\calE_j',0}\right) + \frac{1}{p_j}\calR_\calB\left(p_j|\calE_j'|, 0\right) + \left(\Rht^{\pistar}_{\calE_j',1} - \Rht_{\calE_j',1}\right)  \tag{by the assumptions on $\beta_1, \beta_3$}  \\
&\leq \frac{5}{p_j}\calR_\calB\left(p_j|\calE_j'|,  \frac{p_j\sqrt{\beta_1 L}}{\beta_2}\right) - \frac{1}{2}|\calE_j'|\hatDelta_j + \frac{1}{p_j}\calR_\calB\left(p_j|\calE_j'|, 0\right) + \frac{1}{p_j}\calR_\calB\left(\Nht_{\calE_j', 1}, \Theta_j\right)    \tag{by \pref{eq: checkk 1}, and \pref{assum: corruption robust sub routine} with the assumption that $\pi^\star\in \Pi\backslash \{\hatpi\}$}\\
&\leq \frac{8}{p_j}\calR_\calB\left(p_j|\calE_j'|, \Theta_j + \frac{p_j\sqrt{\beta_1 L}}{\beta_2}\right) - \frac{1}{2}|\calE_j|\hatDelta_j   \tag{by \pref{lem: connecting Regret}} \\
&\leq 0.16M_j\hatDelta_j + 20\beta_2 C_{\calE_j} + 16\sqrt{\beta_1 L} - 0.5|\calE_j|\hatDelta_j.   \tag{by \pref{lem: magic lemma}}
\end{align*}

For $j\geq 2$, the last expression is further upper bounded by

\begin{align*}
&\left(0.32 |\calE_{j-1}| + \frac{\beta_4}{\hatDelta_j^2}\right)\hatDelta_j + 20\beta_2 C_{\calE_j} + 16\sqrt{\beta_1 L} - 0.5|\calE_j|\hatDelta_j   \tag{by the definition of $M_j$} \\
&\leq \frac{\beta_4}{\hatDelta_j} + 20\beta_2 C_{\calE_j} + 16\sqrt{\beta_1 L} + 0.4|\calE_{j-1}|\hatDelta_{j-1} - 0.5|\calE_j|\hatDelta_j    \tag{$\hatDelta_{j}\leq 1.25\hatDelta_{j-1}$}\\
&\leq \otil\left(\sqrt{\beta_4 L} + \beta_2 C_{\calE_j}+\beta_4\right) + 0.4|\calE_{j-1}|\hatDelta_{j-1} - 0.5|\calE_j|\hatDelta_j; \tag{$\hatDelta_j\geq \hatDelta_1=\min\Big\{\sqrt{\frac{\beta_4}{L}}, 1\Big\}$}
\end{align*}

for $j=1$, it is upper bounded by

\begin{align*}
\frac{0.16\beta_4}{\hatDelta_1} + 20\beta_2 C_{\calE_1} + 16\sqrt{\beta_1 L} - 0.5|\calE_1|\hatDelta_1  = \otil\left(\sqrt{\beta_4 L} + \beta_2 C_{\calE_1} + \beta_4\right) - 0.5|\calE_1|\hatDelta_1.
\end{align*}

Summing up the above bound over $j$ (and noticing that the number of epochs is upper bounded by $3\log^2 T$), we see that

\begin{align*}
&\sum_{t=1}^{T_0} (r_t^{\pi^\star} - r_t) \\
&\leq \otil\left(\sqrt{\beta_4 L} + \beta_2 C_{\calE_1}+ \beta_4\right) - 0.5|\calE_1|\hatDelta_1 + \sum_{j=2}^{3\log^2 T} \left(\otil\left(\sqrt{\beta_4 L} + \beta_2 C_{\calE_j}+ \beta_4\right) + 0.4|\calE_{j-1}|\hatDelta_{j-1} - 0.5|\calE_j|\hatDelta_j\right)  \\
& = \otil\left(\sqrt{\beta_4 L} + \beta_2 C_{T_0}+ \beta_4\right).
\end{align*}

Case 2. $\hatpi= \pistar$.

\begin{align*}
\sum_{t\in\calE_j'}\left( r^{\pistar}_t- r_t \right)
&= p_j\left(\Rht_{t,1}^{\pistar} - \Rht_{t,1}\right) \\
&\leq  p_j\left(\Rht_{t,0}^{\pistar} - \Rht_{t,1}\right) +  \otil\left( \sqrt{p_j|\calE_j'|} + 1\right) \tag{\pref{lem: beygel freedman}} \\
&\leq p_j\left(\Rht_{t,0} - \Rht_{t,1}\right) +  \otil\left( \sqrt{p_jM_j} + 1\right)  \tag{since $\hatpi=\pistar$}\\
&\leq \otil\left( p_j M_j\hatDelta_j + \sqrt{\beta_1 L} + \sqrt{p_j M_j} \right)   \tag{by \pref{eq: checkk 2}}\\
&\leq \otil\left(\frac{\beta_4}{\hatDelta_j} + \sqrt{\beta_1 L}\right)    \tag{by the definition of $p_j$}\\
&= \otil\left(\sqrt{\beta_4 L} + \beta_4 \right).  \tag{$\hatDelta_j\geq \hatDelta_1=\min\Big\{\sqrt{\frac{\beta_4}{L}}, 1\Big\}$}
\end{align*}

Similarly, summing over epochs and using the fact that the number of epochs is upper bounded by $\order(\log^2 T)$ we get the desired bound.

of lem: no end.

The condition in the lemma implies $\Delta\geq 16\sqrt{\frac{\beta_4}{L}} = 16\hatDelta_1$.
Below we prove by induction that $\Delta\geq \hatDelta_j$ for all $j$. This holds for $j=1$. Notice that $\hatDelta_j$ only increases when the second break condition eq: checkk 2 holds.
If eq: checkk 2 holds, we have

\begin{align*}
&= |\calE_j|(\mu^{\pi^*} -\mu^{\pi'})\\
&\geq \Rht_{\calE_j, 0} - \Rht_{\calE_j, 1} - \frac{4}{p_j}\calR_\calB\left(\Nht_{\calE_j,1}, \Theta_j\right) \tag{\pref{lem: concentra}} \\
&\geq 3M_j\hatDelta_j + 9\sqrt{\beta_1 L}  - 4\left(0.02M_j\hatDelta_j + 2.5\beta_2 C_{\calE_j} +  2\sqrt{\beta_1 L}\right).  \tag{by \pref{eq: checkk 2} and \pref{lem: magic lemma}} \\
%&\geq 2M_j\hatDelta_j + \sqrt{\beta_1 L} -   \left(0.5\sqrt{\beta_1L} + 0.5M_j\hatDelta_j + 8\beta_2 C\right)   \tag{by the same calculation as in \pref{eq: calculation 2}, \pref{eq: calculation 1} (up to constants)}\\
&\geq 2.5 M_j\hatDelta_j. \tag{by the condition specified in the lemma, we have $\sqrt{\beta_1 L}\geq 10\beta_2 C_{\calE_j}$}
\end{align*}

Because $|\calE_j|\leq M_j$, we have $\hatDelta_j\leq \frac{1}{2.5}\Delta$. Therefore, after the update, $\hatDelta_{j+1}=1.25\hatDelta_j\leq \Delta$ still holds.

Next, we show that the first break condition eq: checkk 1 will not hold with high probability: at any time $t$ within epoch $j$,

\begin{align*}
&\Rht_{[t_j, t-1], 0} - \Rht_{[t_j, t-1],1} - \frac{1}{2}(t-t_j)\hatDelta_j\\
&= \left(\Rht_{[t_j,t-1],0} - (t-t_j) \mu^{\pi^*}\right) +  (t-t_j)\left(\mu^{\pi^*} - \mu^{\pi'} - \frac{1}{2}\hatDelta_j\right) + \left((t-t_j) \mu^{\pi'} - \Rht_{[t_j, t],1}\right)  \\
&\geq  -  \frac{4}{p_j}\calR_\calB\left(p_j(t-t_j), p_j C_{\calE_j}\right) + (t-t_j)\left(\Delta - \frac{1}{2} \hatDelta_j\right) \tag{\pref{lem: concentra}}\\
&\geq  -  \frac{4}{p_j}\calR_\calB\left(p_j(t-t_j), \frac{p_j\sqrt{\beta_1 L}}{\beta_2} \right). \tag{$\beta_2 C_{\calE_j}\leq \sqrt{\beta_1 L}$ as assummed in the lemma; $\Delta \geq \hatDelta_j$ for all $j$ as we just showed above}
\end{align*}

Therefore, the first break condition will not be triggered. Overall, with high probability, $\hatDelta_j$ is non-decreasing with $j$.

Under this high-probability event, since $\hatDelta_j$ never decreases, the number of times $\hatDelta_j$ increases is upper bounded by $\log_{1.25}\frac{\Delta}{\hatDelta_1}\leq \log_{1.25}\sqrt{\frac{L}{\beta_4}}\leq \frac{1}{2}\log_{1.25} T\leq 2\log_2 T$. Furthermore, between two times $\hatDelta_j$ increases, since eq: checkk 1 and eq: checkk 2 are not triggered, the epoch length is at least two times the previous one (by eq: doubling epoch length). Therefore, between two times $\hatDelta_j$ increases, the number of epochs is upper bounded by $\log_2 T$.  Overall, the total number of epochs is upper bounded by $2\log_2 T\times \log_2 T=2\log^2 T$. Since we allow the maximum number of epochs to be $3\log^2 T$ in alg: corral, it will not end before the number of rounds reaches $T$.

of thm: gap bound thm.

Let $L^\star$ be the smallest $L$ such that

\begin{align*}
32\left(\frac{\beta_4}{\Delta} + \beta_2 C \right)\leq \sqrt{\beta_4 L}.
\end{align*}

In the for-loops where the learner uses $L\leq L^\star$, by lem: form 1 regret with gap and lem: corral regret 1, the sum of regret in and is upper bounded by

\begin{align*}
\otil\left(\sqrt{\beta_4 L} + \beta_2 C + \beta_4\right) = \otil\left(\sqrt{\beta_4 L^\star} + \beta_2 C + \beta_4\right) = \otil\left(\frac{\beta_4}{\Delta} + \beta_2 C \right).
\end{align*}

In the for-loop where the learner first time uses $L > L^\star$, we have

\begin{align*}
\beta_2 2^k \geq \sqrt{\beta_4(L-1)}\geq \sqrt{\beta_4 L^\star} \geq 32\left(\frac{\beta_4}{\Delta} + \beta_2 C  \right)
\end{align*}

where the first inequality is by the choice of $L$ in . By lem: execute most times, with probability at least $1-\order(\delta)$,  $\hatpi=\pistar$. Further by lem: no end, with high probability, will continue until the total number of rounds reaches $T$. In this case, using lem: form 1 regret with gap and lem: corral regret 1, we can still bound the regret in the remaining steps by

\begin{align*}
\otil\left(\sqrt{\beta_4 L} + \beta_2 C + \beta_4\right) = \otil\left(\sqrt{\beta_4 L^\star} + \beta_2 C + \beta_4\right) = \otil\left(\frac{\beta_4}{\Delta} + \beta_2 C\right).
\end{align*}

By the discussions above, we also see that with high probability, in all for-loops, the learner uses $L < 2L^\star$ (because the algorithm will be locked in Phase 2 when the first time $L>L^\star$ happens). Therefore, by the condition of starting , can only be reached when $L^\star=\Omega(T)$. In this case, the regret incurred in , by thm: form 1 regret, is upper bounded by

\begin{align*}
\otil\left(\sqrt{\beta_1 T} + \beta_2 C + \beta_3\right) = \otil\left( \sqrt{\beta_1 L^\star} + \beta_2 C + \beta_3 \right) = \otil\left(\frac{\beta_4}{\Delta} + \beta_2 C + \beta_4\right) = \otil\left(\frac{\beta_4}{\Delta} + \beta_2 C\right).
\end{align*}

Overall, after summing the regret in all phases and using the fact that the for-loop only repeat $\otil(1)$ times, we see that the total regret can be upper bounded by $\otil\left(\frac{\beta_4}{\Delta} + \beta_2 C\right)$. To show that the algorithm also simultaneously guarantees a bound of $\otil\left(\sqrt{\beta_4 T} + \beta_2 C + \beta_4\right)$, simply bound the regret in all phases by $\otil\left(\sqrt{\beta_4 L} + \beta_2 C + \beta_4\right)=\otil\left(\sqrt{\beta_4 T} + \beta_2 C + \beta_4\right)$.

§ THE IMPLEMENTATION OF THE LEAVE-ONE-POLICY-OUT MDP

We consider a tabular MDP $\calM=(\calS, \calA, r, p, H)$ with a fixed initial state $s_1\in\calS$. Let $\Pi_\calM$ denote the set of all deterministic policies in $\calM$.
Now, given a deterministic policy $\hatpi\in\Pi_\calM$, our goal is to construct another MDP $\calM'$, such that the policy set of $\calM'$ includes all policies in $\calM$ except for $\hatpi$, and that for any $\pi\in \Pi_\calM\backslash\{\hatpi\}$, the expected reward in $\calM$ and $\calM'$ is the same.

MDP $\calM'$ has state space $\{s_0\} \cup \mathcal S \times \mathcal S$ and horizon $H+1$. In $\calM'$, the agent starts in the initial state $s_0$ and takes one of $S$ actions which makes it transition to one of $S$ copies of the original MDP $\calM$. The $s$-th copy of $\calM$ is denoted by $\calM_s$ and is identical to $\calM$ except that the agent is not allowed to take the actions prescribed by $\widehat \pi$ in  state $s$.

Note that we can obtain samples for $\calM'$ by playing in $\calM$, and that

\begin{align}
\max_{\pi\in \Pi_{\calM'} }\mu^\pi_{\calM'} = \max_{\pi\in \Pi_\calM \setminus \{\hatpi\}} \mu^\pi_{\calM}   \label{eq: desired identity}
\end{align}

where $\mu_{\calM}^{\pi}$ denotes the expected reward of policy $\pi$ under MDP $\calM$. To see this, simply notice that for any $\pi\in\Pi_\calM \setminus \{\hatpi\}$ which differs from $\pistar$ on state $s$, one can find a policy $\pi'\in\Pi_{\calM'}$ that first goes to $\calM_s$ in $\calM'$ in the first step, and then follow $\pi$ in the rest of the steps.  This policy $\pi'$ gives the same expected reward as $\pi$. Conversely, for any $\pi'\in\Pi_{\calM'}$, there is a policy $\pi\in\Pi_{\calM}\setminus\{\hatpi\}$ which simply equals to $\pi'$ on its $2$ to $H+1$ steps. This $\pi$ gives the same expected reward as $\pi'$.

Although $\calM'$ has $S^2+1$ states, and the total number of actions is $(SA-1)\times S + S$ (where $SA-1$ is the total number of actions in each copy of $\calM$, and the additional $S$ is the number of actions on $s_0$), running UCBVI on $\calM'$ can in fact yield the  same gap-independent bound as running it in $\calM$ if we share the samples among different copies of $\calM$. To see this in the uncorrupted case, notice that in the analysis of the UCBVI algorithm (see, e.g., [Azar et al., 2017], or Chapter 7 of [Agarwal et al., 2020]), the regret bound is a sum of terms of the form $\sum_{t}\sum_h\frac{\poly(S, A, H)}{\sqrt{n_t(s^t_h,a^t_h)}}$ or $\sum_{t}\sum_h\frac{\poly(S, A, H)}{n_t(s^t_h,a^t_h)}$. When the samples of the $S$ copies of $\calM$ are shared, these sum will only scale with the original number of states and actions.
This can also be proved formally through the use of feedback graphs [Dann et al., 2020].
In the corrupted case, the amount of corruption (i.e., $c_t=H\cdot \sup_{s,a,V}|(\calT V - \calT_t V)(s,a)|$) remains the same in $\calM$ and in $\calM'$.
Therefore, the overall regret bound in $\calM'$ under corruption remains the same order as that in $\calM$.

§ BASE ALGORITHMS

In this section, we describe and analyze the base algorithms for all settings considered in tab:my_label. At the end of each subsection, we calculate the precise regret bounds achieved by our approaches and compare them with those in previous works to complement tab:my_label. The proofs are sometimes brief since they mostly follow standard analysis appeared in previous works. More details can be found in the references.

§.§ Robust UCBVI for tabular MDPs

A Robust UCBVI algorithm is presented by Lykouris et al., 2021 in their Appendix B. We translate it to our setting (i.e., our trajectory reward is bounded in $[0, 1]$, and our definition of $C^\am$ already includes an $H$ factor). The resulting algorithm essentially runs the standard UCBVI algorithm [Azar et al., 2017] with enlarged bonuses

\begin{align*}
b_t(s,a) = \min\left\{2\sqrt{\frac{2\ln(64SAHT^2/\delta)}{n_t(s,a)}} + \frac{C^\am}{n_t(s,a)}, \ \ 1\right\}
\end{align*}

where $n_t(s,a)$ is the number of visits to $(s,a)$ before episode $t$, and $C^\am$ is a given upper bound of the total corruption. This algorithm achieves the following bound (c.f. Eq. (B.1) in Lykouris et al., 2021):

\begin{align}
\sum_{\tau=1}^t \left(V_1^\star(s^t_1) - V_1^{\pi_t}(s^t_1)\right) \leq  \poly(H)\times\otil\left(\min\left\{\textsf{GapComplexity}, \sqrt{SAt}\right\} + S^2A + C^\am SA\right). \label{eq: Lykouris bound UCBVI}
\end{align}

Furthermore, by their definition of  (with proper scaling for our setting), it holds that $\textsf{GapComplexity}\leq \frac{SA}{\textsf{gap}_{\min}}\leq \frac{SA}{\Delta}$, where $\textsf{gap}_{\min}\triangleq \min_{s,a\neq \pistar_h(s),h}\left(V^\star_h(s) - Q^\star_h(s,a)\right)$ and the second inequality is by the performance difference lemma,

\begin{align*}
\Delta = \min_{\pi\neq \pistar}\Delta_{\pi}
&=\min_{\pi\neq \pistar}\E\left[\sum_{h,s,a} \Pr[s_h=s](V_h^\star(s)-Q^\star_h(s,a))~\bigg|~\pi\right]\\
&\leq \min_{h,s,a\neq \pistar_h(s)} \E\left[ \Pr[s_h=s](V_h^\star(s)-Q_h^\star(s,a))~\big|~\pi: \pi_h(s')=\pistar_h(s') \forall s'\neq s, \pi_h(s)=a\right] \tag{Let $\pi$ be the policy that only differs from $\pistar$ on state $s$ at level $h$} \\
&\leq \textsf{gap}_{\min}.
\end{align*}

Below we use these facts to derive our bound.

For finite-horizon tabular MDPs, $\algname$ with Robust UCBVI as the base algorithm guarantees $\Reg(T)=\otil\left(\textup{poly}(H)\times \left(\sqrt{SAT} + S^2A + SAC^\am\right)\right)$; with Robust UCBVI guarantees $\Reg(T)=\otil\left(\textup{poly}(H)\times \left(\min\left\{\frac{S^2A}{\Delta}, \sqrt{S^2AT}\right\} + S^2A + SAC^\am\right)\right)$.

By eq: Lykouris bound UCBVI and Azuma's inequality, we have

\begin{align*}
\sum_{\tau=1}^t \left(r_\tau^{\pistar} - r_\tau\right) \leq \poly(H)\times \otil\left( \sqrt{SAt} + S^2A +  SAC^\am\right),
\end{align*}

which satisfies eq: typeone with $\beta_1=\widetilde{\Theta}(\poly(H) SA)$, $\beta_2=\widetilde{\Theta}(\poly(H)SA)$, $\beta_3=\widetilde{\Theta}(\poly(H)S^2A)$. Applying thm: form 1 regret with these parameters we get the bound for .

Let $N_t^{\neq \pistar}=\sum_{\tau=1}^t \one[\pi_\tau\neq \pistar]$ be the number of times the learner chooses sub-optimal policies. Using eq: Lykouris bound UCBVI and noticing that the left-hand side of it is lower bounded by $N_t^{\neq \pistar}\Delta$, we get

\begin{align*}
N_t^{\neq \pistar}\Delta \leq
\poly(H)\times \otil\left(\frac{SA}{\Delta} + S^2 A + SAC^\am\right).
\end{align*}

Therefore, by Azuma's inequality, we have with probability $1-\order(\delta)$,

\begin{align*}
\sum_{\tau=1}^t (r^{\pistar}_\tau - r_\tau) &\leq  \poly(H)\times\otil\left(\min\left\{\frac{SA}{\Delta}, \sqrt{SAt}\right\} + S^2A + C^\am SA + \sqrt{N_t^{\neq\pistar}}\right)\\
&\leq  \poly(H)\times\otil\left(\min\left\{\frac{SA}{\Delta}, \sqrt{SAt}\right\} + S^2A + C^\am SA \right).
\end{align*}

This satisfies eq: typetwo with $\beta_1=\widetilde{\Theta}(\poly(H) SA)$, $\beta_2=\widetilde{\Theta}(\poly(H)SA)$, $\beta_3=\widetilde{\Theta}(\poly(H)S^2A)$ (therefore, $\beta_4=\widetilde{\Theta}(\poly(H)S^2A)$). Applying thm: gap bound thm with these parameters we get the bound for .

Comparison with previous bounds  For corrupted tabular MDPs, the bound of [Lykouris et al., 2021] is $\poly(H)\times \otil\left( (1+C^\am)\min\left\{\textsf{GapComplexity}, \sqrt{SAT}\right\} + S^2AC^\am + SA(C^\am)^2 \right)$; the bound of [Chen et al., 2021] is $\poly(H)\times \otil\left( \min\left\{\frac{S^2A^{\nicefrac{3}{2}}}{\Delta}, \sqrt{S^4A^3T}\right\} + S^2 A^2 C^{\am} + (C^{\am})^2\right)$; the bound of [Jin et al., 2021] is $\poly(H)\times \otil\left(\min\left\{\textsf{GapComplexity}, \sqrt{S^2A^2 T}\right\} + C^{\am}\right)$ (under the uncorrupted transition assumption).

$\calL=\{2,4, 8, \ldots\}$

$t=1, \ldots, T$
$h=1, \ldots, H$
Observe $s^t_h$, take $a^t_h=Q_h(s^t_h,a)$, and receive $r^t_h$.

$n(s^t_h, a^t_h, s^t_{h+1})\leftarrow n(s^t_h, a^t_h, s^t_{h+1}) +1$

$n(s^t_h, a^t_h)\leftarrow n(s^t_h, a^t_h)+1$

$m(s^t_h, a^t_h)\leftarrow m(s^t_h, a^t_h) + r^t_h$

$n(s^t_h, a^t_h)\in \calL$
$\textsc{flag}\leftarrow \textbf{true}$

$\tildep(\cdot|s,a)\leftarrow n(s,a,s')/n(s,a)$ and $\tilder(s,a)\leftarrow m(s,a)/n(s,a)$

$h=H,\ldots, 1$

\begin{align*}
b_h(s,a)&\triangleq c_1\sqrt{\frac{\mathbb{V}(\tildep, V_{h+1})}{n(s,a)}} + c_2\sqrt{\frac{\tilder(s,a)}{n(s,a)}} + \frac{c_3(1+C)}{n(s,a)}\\
Q_h(s,a) &\leftarrow \min\left\{\tilder(s,a) + \E_{s'\sim \tildep(\cdot|s,a)} V_{h+1} + b_h(s,a), \ \ \ 1\right\} \\
V_h(s) &\leftarrow \max_a Q_h(s,a)
\end{align*}

\begin{align*}
\|P_{s,a}V^\star_{h+1} - \widetilde{P}_{s,a}V^\star_{h+1}\|_1
&\leq 2\sqrt{\frac{\mathbb{V}(\widetilde{P}_{s,a}, V_{h+1}^\star)\iota}{n^k(s,a)}} + \frac{14\iota}{3n^k(s,a)} + \frac{2C}{n^k(s,a)}  \\
\|r(s,a) - \tilder(s,a)\|_1
&\leq 2\sqrt{\frac{2\tilder(s,a)\iota}{n^k(s,a)}} + \frac{28\iota}{3n^k(s,a)} + \frac{2C}{n^k(s,a)}
\end{align*}

\begin{align*}
&\left|P_{s,a}V^\star_{h+1} - \widetilde{P}_{s,a}V^\star_{h+1}\right| \\
&= \frac{1}{n_t(s,a)}\left|\sum_{\tau=1}^{t-1}\sum_{h=1}^H \sum_{s'} \one[(s^\tau_h, a^\tau_h)=(s,a)](p(s'|s,a) - \one[s^{\tau}_{h+1}=s'])V^\star(s')\right| \\
&\leq \frac{1}{n_t(s,a)} \left|\sum_{\tau=1}^{t-1}\sum_{h=1}^H \sum_{s'} \one[(s^\tau_h, a^\tau_h)=(s,a)](p_\tau(s'|s,a) - \one[s^{\tau}_{h+1}=s'])V^\star(s')\right| + \frac{C}{n_t(s,a)} \\
&\leq \frac{1}{n_t(s,a)} \sqrt{\sum_{\tau=1}^{t-1}\sum_{h=1}^H \one[(s^\tau_h, a^\tau_h)=(s,a)] \mathbb{V}(\widetilde{P}_{s,a}, V^\star)} +  \frac{C}{n_t(s,a)}
\end{align*}

The concentration does not follow directly from Zhang et al, because $p_{\tau}(s'|s,a)-\one[s^\tau_{h+1}=s']$ are not i.i.d. .

\begin{align*}
&\left|  r(s,a) - \widetilde{r}(s,a) \right| \\
&= \frac{1}{n_t(s,a)} \left| \sum_{\tau=1}^{t-1}\sum_{h=1}^H \sum_{s'}\one[(s^\tau_h, a^\tau_h)=(s,a)]\left(r(s,a)-r^\tau_h\right) \right| \\
&\leq \frac{1}{n_t(s,a)} \left| \sum_{\tau=1}^{t-1}\sum_{h=1}^H \sum_{s'}\one[(s^\tau_h, a^\tau_h)=(s,a)]\left(r_\tau(s,a)-r^\tau_h\right) \right| + \frac{C}{n_t(s,a)} \\
&\leq \frac{1}{n_t(s,a)}\sqrt{\sum_{\tau=1}^{t-1}\sum_{h=1}^H r_\tau(s,a)^2 } + \frac{C}{n_t(s,a)}.
\end{align*}

$Q^t_h(s,a)\geq Q^\star_h(s,a)$ for all $s,a$ with high probability.

Define the function:

\begin{align*}
f(p, v, n, \thres, \iota) = pv + \max\left\{\overline{c}_1\sqrt{\frac{\mathbb{V}(p,v)\iota}{n}}, \frac{\overline{c}_2\iota}{n}, \frac{\overline{c}_3\thres}{n}\right\}
\end{align*}

Then $f(p, v, n, \thres, \iota)$ is non-decreasing in $v(s)$.

\begin{align*}
&Q^t_h(s,a) \\
&= \min\left\{\widetilde{r}(s,a) + \widetilde{P}_{s,a}V^t_{h+1} + b^t_h(s,a),\ \ 1  \right\} \\
&\geq \min\left\{\widetilde{r}(s,a) +  \widetilde{P}_{s,a}V^t_{h+1} + \max\left\{\overline{c}_1 \sqrt{\frac{\mathbb{V}(\widetilde{P}_{s,a}, V^t_{h+1})}{n(s,a)}}, \frac{\overline{c}_2}{n(s,a)}  \right\}+ \frac{\overline{c}_3\thres}{n(s,a)},\ \ 1  \right\} \\
&\geq  \min\left\{\widetilde{r}(s,a) +  \widetilde{P}_{s,a}V^\star_{h+1} + \max\left\{\overline{c}_1 \sqrt{\frac{\mathbb{V}(\widetilde{P}_{s,a}, V^\star_{h+1})}{n(s,a)}}, \frac{\overline{c}_2}{n(s,a)}  \right\}+ \frac{\overline{c}_3\thres}{n(s,a)},\ \ 1  \right\}  \\
&\geq \min\left\{r(s,a) +  P_{s,a}V^\star_{h+1} \ \ 1  \right\} \\
&= Q^\star_h(s,a).
\end{align*}

\begin{align*}
Q^t_h(s,a) - r(s,a) - P_{s,a}V^t_{h+1} \leq  \sqrt{\frac{\mathbb{V}(P_{s,a}, V^\star_{h+1})}{n^t(s,a)}} + \sqrt{\frac{S\mathbb{V}(P_{s,a}, V^t_{h+1}-V^\star_{h+1})}{n^t(s,a)}} + \frac{S + \thres}{n^t(s,a)}.
\end{align*}

The proof of this lemma follows Lemma 4 of <cit.>.

\begin{align*}
\text{Regret}\leq \sum_{t=1}^T \sum_{h=1}^H  \beta^t_h(s^t_h, a^t_h)  + \otil\left(\sqrt{K}\right).
\end{align*}

\begin{align*}
M&\triangleq \sum_{t=1}^T \sum_{h=1}^H  \beta^t_h(s^t_h, a^t_h), \quad
M' \triangleq \sum_{t=1}^T \sum_{h=1}^H \mathbb{V}(P_{s^t_h, a^t_h}, V^t_{h+1}) + S \sum_{t=1}^T\sum_{h=1}^H  \mathbb{V}(P_{s^t_h, a^t_h}, V^t_{h+1}-V^\star_{h+1})
\end{align*}

The following two inequalities hold:

\begin{align*}
M&\leq \otil\left(\sqrt{SA M'} + \sqrt{SAT} + CSA + S^2A\right) \\
M'&\leq  \otil\left(T + SM + SA\right)
\end{align*}

Once the inequalities are proven, then we have

\begin{align*}
M &\leq \sqrt{SAT} + \sqrt{S^2A M} + CSA + S^2A \\
&\leq \sqrt{SAT} + \frac{1}{2}M + CSA + 2S^2A   \tag{Am-GM}
\end{align*}

implying the inequality we want to prove.

The first inequality follows from the analysis in Section 6.3.3 of <cit.>, except that adding an additional $\frac{\thres}{n^t(s,a)}$ term to the upper bound of $\beta^t_h(s,a)$.

The second inequality follows from Lemma 6 and 7 in <cit.> (see also Lemma 7 and 8 in [Wu et al., 2021]).

§.§ Robust Phased Elimination for linear bandits

Robust Phased Elimination
input: $C^\am$

define: $m_0=4d([\log\log d]_+ + 18)$

initialize: $\calA_0\leftarrow \calA$

$k=0, 1, 2, \ldots$
Let $m_k=2^{k-1}m_0$.

Compute $\zeta_k: \calA_k\rightarrow [0,1]$ such that

\begin{align*}
\max_{a\in\calA_k} \|a\|_{\Gamma(\zeta_k)^{-1}}\leq 2d  \quad \text{and} \quad   |\text{supp}(\zeta_k)|\leq m_0
\end{align*}

where $\Gamma(\zeta_k) = \sum_{a \in \calA_k} \zeta_k(a) a a^\top$.

\begin{align*}
u_k(a) = \begin{cases}
0 &\text{if}~\zeta_k(a)=0 \\
\left\lceil m_k\max\{\zeta_k(a), \frac{1}{m_0}\} \right\rceil &\text{otherwise}
\end{cases}
\end{align*}

Draw each action $a\in\calA_k$ exactly $u_k(a)$ times, and get action-reward pairs $(a_\tau, r_\tau)_{\tau=1}^{u_k}$, where $u_k=\sum_{a\in\calA_k}u_k(a)$.

Estimate parameter:

\begin{align*}
w_k = \Gamma_k^{-1} \sum_{\tau=1}^{u_k}a_\tau r_\tau, \qquad \text{where\ } \Gamma_k = \sum_{a\in\calA_k} u_k(a)aa^\top.
\end{align*}

Update the active set

\begin{align*}
\calA_{k+1}\leftarrow \left\{ a\in \calA_k~:~ \max_{a'\in\calA_k} w_k^\top (a'-a) \leq 4d\sqrt{\frac{1}{m_k}\log(T/\delta)} +  \frac{4 \sqrt{2d}m_0}{m_k}C^{\am}\right\}.
\end{align*}

The Robust Phased Elimination (alg: robust phased elimination) is exactly the Algorithm 1 of [Bogunovic et al., 2021] with the choice of parameters specified in their Theorem 1 (i.e., $\nu=\frac{1}{m_0}$ in their notations). Its gap-independent bound is shown below:

With probability at least $1-\order(\delta)$, Robust Phased Elimination ensures

\begin{align*}
\sum_{\tau=1}^t (r_\tau^{a^\star}-r_\tau)  = \otil\left(d\sqrt{t \log(T/\delta)} + C^{\am}d^{\nicefrac{3}{2}}\log T\right).
\end{align*}

By Theorem 1 of [Bogunovic et al., 2021], we have

\begin{align*}
\sum_{\tau=1}^t (\mu^{a^\star} - \mu^{a_t}) = \otil\left(\sqrt{dt \log(T|\calA|/\delta)} + C^{\am}d^{\nicefrac{3}{2}}\log T\right) = \otil\left(d\sqrt{t \log(T/\delta)} + C^{\am}d^{\nicefrac{3}{2}}\log T\right)
\end{align*}