#  Variance-aware robust reinforcement learning with linear function
approximation under heavy-tailed rewards

Xiang Li School of Mathematical Sciences, Peking University; E-mail:
<EMAIL_ADDRESS>The work was done when Xiang Li was a visiting student in
the IVGS program at the Department of Statistical Sciences, University of
Toronto. Qiang Sun Department of Statistical Sciences, University of Toronto;
E-mail<EMAIL_ADDRESS>
###### Abstract

This paper presents two algorithms, AdaOFUL and VARA, for online sequential
decision-making in the presence of heavy-tailed rewards with only finite
variances. For linear stochastic bandits, we address the issue of heavy-tailed
rewards by modifying the adaptive Huber regression and proposing AdaOFUL.
AdaOFUL achieves a state-of-the-art regret bound of
$\widetilde{\mathcal{O}}\big{(}d\big{(}\sum_{t=1}^{T}\nu_{t}^{2}\big{)}^{1/2}+d\big{)}$
as if the rewards were uniformly bounded, where $\nu_{t}^{2}$ is the observed
conditional variance of the reward at round $t$, $d$ is the feature dimension,
and $\widetilde{\mathcal{O}}(\cdot)$ hides logarithmic dependence. Building
upon AdaOFUL, we propose VARA for linear MDPs, which achieves a tighter
variance-aware regret bound of
$\widetilde{\mathcal{O}}(d\sqrt{H\mathcal{G}^{*}K})$. Here, $H$ is the length
of episodes, $K$ is the number of episodes, and $\mathcal{G}^{*}$ is a smaller
instance-dependent quantity that can be bounded by other instance-dependent
quantities when additional structural conditions on the MDP are satisfied. Our
regret bound is superior to the current state-of-the-art bounds in three ways:
(1) it depends on a tighter instance-dependent quantity and has optimal
dependence on $d$ and $H$, (2) we can obtain further instance-dependent bounds
of $\mathcal{G}^{*}$ under additional structural conditions on the MDP, and
(3) our regret bound is valid even when rewards have only finite variances,
achieving a level of generality unmatched by previous works. Overall, our
modified adaptive Huber regression algorithm may serve as a useful building
block in the design of algorithms for online problems with heavy-tailed
rewards.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Heavy-tailed Stochastic Linear Bandit
    2. 2.2 Linear MDP with Heavy-tailed Rewards
  3. 3 Variance-aware Regret for Linear Bandits
    1. 3.1 Algorithm Description
    2. 3.2 Regret Analysis
  4. 4 Variance Aware Regret for Linear MDPs
    1. 4.1 High-level Algorithm Description
    2. 4.2 Detailed Algorithm Description
    3. 4.3 Regret Analysis
    4. 4.4 Other Instance-dependent Regrets
    5. 4.5 Space and Computational Complexities
  5. 5 Related Work
  6. 6 Conclusion
  7. A Variance Estimation for Value Functions
  8. B Proof for Section 3.2
    1. B.1 Proof of Theorem 3.1
    2. B.2 Proof of Theorem 3.2
    3. B.3 Proof of Lemma B.1
    4. B.4 Proof of Lemma B.2
    5. B.5 Proof of Lemma B.3
    6. B.6 Proof of Lemma B.4
  9. C Proof of Theorem 4.1
    1. C.1 High-Probability Events
    2. C.2 Regret Analysis
  10. D Proof of Theorem 4.2
  11. E Omitted lemmas in Section C
    1. E.1 Proof of Lemma C.1
    2. E.2 Proof of Lemma C.2
    3. E.3 Proof of Lemma E.1
    4. E.4 Proof of Lemma C.3
    5. E.5 Proof of Lemma C.4
    6. E.6 Proof of Lemma C.5
    7. E.7 Proof of Lemma C.6
    8. E.8 Proof of Lemma C.7
    9. E.9 Proof of Lemma C.8
    10. E.10 Proof of Lemma C.9
    11. E.11 Proof of Lemma C.10
      1. E.11.1 Proof of Lemma E.2
      2. E.11.2 Proof of Lemma E.3
      3. E.11.3 Proof of Lemma E.4
  12. F Auxiliary Lemmas
    1. F.1 Concentration Inequalities
    2. F.2 Elliptical Lemmas
    3. F.3 Function Class and Covering Number

##  1 Introduction

In reinforcement learning (RL), an agent interacts with an environment by
taking actions and receiving rewards. The goal of the agent is to learn a
policy that maximizes its expected cumulative reward over time. Since the
agent does not initially know the optimal policy, it needs to explore
different actions and learn from the feedback it receives (Sutton and Barto,
2018). Reinforcement learning has demonstrated remarkable empirical successes
in various applications, including robotics (Lillicrap et al., 2015), dialogue
systems (Li et al., 2016), and Go play (Silver et al., 2016). Despite its
empirical successes, the theoretical understanding of RL is still in its early
stages. An important theoretical goal is to characterize the regret of an
agent, defined as the difference between the cumulative reward obtained by the
agent and the cumulative reward that could have been obtained by following the
optimal policy from the beginning. In other words, regret measures the
suboptimality of the agent.

Regret analysis in reinforcement learning (RL) has mainly focused on tabular
Markov decision processes (MDPs) with finite and small state and action spaces
(Azar et al., 2017; Sidford et al., 2018; Dann et al., 2019; Yang and Wang,
2019; Tossou et al., 2019; Zhang et al., 2020; Zanette et al., 2020; He et
al., 2021b). However, many real-world applications have high-dimensional or
even infinite-dimensional state and action spaces, where function
approximation is necessary for computational tractability and better
generalization. Linear function approximation is a widely studied technique in
RL, particularly in the context of linear MDPs, where the value or policy
function can be parameterized linearly (Yang and Wang, 2020; Jin et al.,
2020b, a; Wagenmaker et al., 2022b; Zanette et al., 2020; Ayoub et al., 2020;
Zhou et al., 2021). In this linear setting, Jin et al. (2020b) presented the
first provable RL algorithm that achieves
$\widetilde{\mathcal{O}}(\sqrt{d^{3}H^{4}K})$ regret with $H$ being the
episode length and $K$ the number of episodes, which was then improved to the
optimal $\widetilde{\mathcal{O}}(\sqrt{d^{2}H^{3}K})$ regret by He et al.
(2022). Recently, there has been a shift in focus from designing algorithms
with worst-case regrets to those with variance-aware regrets (Pananjady and
Wainwright, 2020; Khamaru et al., 2021; Li et al., 2023; Yin and Wang, 2021;
Min et al., 2021). Variance-aware regrets depend on the variances of rewards
and value functions and provide stronger guarantees than worst-case bounds by
characterizing problem-dependent performances across different problem
instances.

However, the aforementioned works assume that rewards are either uniformly
bounded or sub-Gaussian, limiting their applicability to real-world problems
with heavy-tailed behaviors. For instance, stock returns in financial markets
(Cont, 2001; Hull, 2012), microarray data analysis (Posekany et al., 2011),
and advertiser values in online advertising (Arnosti et al., 2016) exhibit
heavy-tailed behaviors. To address this limitation, some researchers truncate
rewards to achieve sub-linear worst-case regret bounds for multi-arm bandits
(Bubeck et al., 2013), linear bandits (Medina and Yang, 2016; Shao et al.,
2018; Xue et al., 2021), and tabular MDPs (Zhuang and Sui, 2021) with finite
variances. However, these truncation-based methods have estimation errors that
depend on the absolute moments of observations, rather than their central
moments, and thus are non-diminishing in the noiseless case, indicating their
suboptimality.

##### Our contributions

This paper proposes new algorithms for achieving tight variance-aware regret
bounds that depend on the central moments instead of absolute moments, for
linear bandits and linear MDPs with heavy-tailed awards that have only finite
variances. We use the term “heavy-tailed rewards” throughout the paper to
refer to such rewards for simplicity. Our method is motivated by adaptive
Huber regression (Sun et al., 2020; Sun, 2021), which was originally proposed
for analyzing offline independently and identically distributed (i.i.d.) data.
It uses the (pseudo-) Huber loss to estimate the unknown coefficient with a
universal robustification parameter. We adapt this method for online bandits
and carefully choose different robustification parameters to handle non-i.i.d.
data. The resulting algorithm, called AdaOFUL (short for Adaptive Huber
regression based OFUL), achieves the state-of-the-art regret bound
$\widetilde{{\mathcal{O}}}\left(d\sqrt{\sum_{t\in[T]}\nu_{t}^{2}}+d\right)$
for linear bandits with heavy-tailed rewards, where $\nu_{t}^{2}$ is the
observed conditional variance of the random reward at step $t$ and $d$ is the
feature dimension. Such a variance-aware regret bound has only been obtained
in the literature of linear bandits with sub-Gaussian or uniformly bounded
rewards (Kirschner and Krause, 2018; Zhou and Gu, 2022). In contrast,
truncation-based methods are suboptimal due to their estimation errors that
depend on absolute moments instead of central moments. Our regret bound
depends on the central moments instead, and is thus tighter.

Building upon AdaOFUL, we then propose the Variance-Aware Regret via the
Adatptive Huber regression (VARA) algorithm for linear MDPs with heavy-tailed
rewards. Our algorithm improves upon state-of-the-art methods (Wagenmaker et
al., 2022a; Hu et al., 2022; He et al., 2022) by using finer variance
estimators, resulting in a regret bound of
$\widetilde{\mathcal{O}}(d\sqrt{H{\mathcal{G}}^{*}K})$, where $H$ is the
episode length and ${\mathcal{G}}^{*}$ is a variance-aware quantity bounded by
the sum of weighted per-step conditional variances. Our regret bound is
superior to the current state-of-the-art bounds in three ways. First, it
depends on a tighter instance-dependent quantity ${\mathcal{G}}^{*}$ and has
optimal dependence on $d$ and $H$. Second, assuming additional structural
conditions on the underlying MDP, we can obtain further instance-dependent
bounds of ${\mathcal{G}}^{*}$, including range-dependent and concentrability-
dependent bounds. Third, our regret bound
$\widetilde{\mathcal{O}}(d\sqrt{H{\mathcal{G}}^{*}K})$ is valid even when
rewards have only finite variances, which achieves a level of generality that
is unmatched by previous works.

Our findings indicate that heavy-tailed rewards do not pose a limitation for
developing online RL algorithms with linear function approximations that are
provably efficient. Our proposed modified adaptive Huber regression algorithm
can be used as a general approach to adapt existing online algorithms designed
for light-tailed rewards to handle heavy-tailed ones while maintaining tight
dependence on variance for regret bounds.

##### Outline

The rest of the paper proceeds as follows. Section 2 introduces the heavy-
tailed linear bandits and linear MDPs. We state our main results for heavy-
tailed linear bandits in Section 3 and for linear MDPs in Section 4. We review
related work in Section 5 and conclude in Section 6. All proofs are collected
in the appendix.

##### Notation

We use $\|\cdot\|$ to denote the $\ell_{2}$-norm in ${\mathbb{R}}^{d}$, and
$\mathrm{Ball}_{d}(B)$ the $\ell_{2}$-norm ball in ${\mathbb{R}}^{d}$ with
radius $B>0$. For a positive definite matrix ${\bm{H}}\in{\mathbb{R}}^{d\times
d}$, let $\|{\bm{x}}\|_{{\bm{H}}}=\sqrt{{\bm{x}}^{\top}{\bm{H}}{\bm{x}}}$ for
a vector ${\bm{x}}\in{\mathbb{R}}^{d}$. For two semidefinite positive matrices
${\bm{H}}_{1},{\bm{H}}_{2}$, we denote ${\bm{H}}_{1}\succeq{\bm{H}}_{2}$ if
${\bm{H}}_{2}-{\bm{H}}_{1}$ is semidefinite positive. For an integer
$K\in\mathbb{N}^{+}$, let $[K]:=\\{1,2,\cdots,K\\}$. For a set $\mathcal{A}$,
$|\mathcal{A}|$ denotes its cardinality. For real numbers $a\leq b$ and
$x\in{\mathbb{R}}$, we use $x_{[a,b]}:=\max\\{a,\min\\{x,b\\}\\}$ to denote
the projection of $x$ onto the closed interval $[a,b]$. SOTA is short for
state-of-the-art.

##  2 Preliminaries

In this section, we introduce both stochastic linear bandits and linear MDPs
with heavy-tailed rewards.

###  2.1 Heavy-tailed Stochastic Linear Bandit

Below, we define heavy-tailed stochastic linear bandits, where the mean-zero
random noises $\varepsilon_{t}$ have only bounded variances. We emphasize that
in linear bandits, data are collected in an adaptive manner, and therefore,
the distribution of $\varepsilon_{t}$ depends on ${\bm{\phi}}_{t}$. Moreover,
the choice of ${\bm{\phi}}_{t}$ depends on all past observations
${({\bm{\phi}}_{s},y_{s},\nu_{s})}_{s<t}$.

######  Definition 2.1 (Heavy-tailed stochastic linear bandit).

Let $\\{{\mathcal{D}}_{t}\\}_{t\geq 1}$ denote a fixed sequence of decision
sets and $\\{{\mathcal{F}}_{t}\\}_{t\geq 1}$ a filtration. At round $t$, the
agent chooses ${\bm{\phi}}_{t}\in{\mathcal{D}}_{t}$ and then observes the
reward $y_{t}$ and its conditional variance $\nu_{t}^{2}$. We assume
$y_{t}=\langle{\bm{\phi}}_{t},{\bm{\theta}}^{*}\rangle+\varepsilon_{t}$ where
${\bm{\theta}}^{*}\in{\mathbb{R}}^{d}$ is a vector unknown to the agent and
$\varepsilon_{t}\in{\mathbb{R}}$ is a martingale difference random noise such
that ${\mathbb{E}}[\varepsilon_{t}|{\mathcal{F}}_{t-1}]=0$ and
${\mathbb{E}}[\varepsilon_{t}^{2}|{\mathcal{F}}_{t-1}]=\nu_{t}^{2}$. Both
$\nu_{t}$ and ${\bm{\phi}}_{t}$ are ${\mathcal{F}}_{t-1}$-measurable and
$\|{\bm{\phi}}_{t}\|\leq L$. We assume $\|{\bm{\theta}}^{*}\|\leq B$ with $B$
known a priori. The agent aims to minimize the regret, formally defined as

$\mathrm{Reg}(T):=\sum_{t=1}^{T}\left[\sup_{{\bm{\phi}}\in{\mathcal{D}}_{t}}\langle{\bm{\phi}},{\bm{\theta}}^{*}\rangle-\langle{\bm{\phi}}_{t},{\bm{\theta}}^{*}\rangle\right].$
(2.1)

###  2.2 Linear MDP with Heavy-tailed Rewards

An episodic finite horizon MDP is denoted by a tuple
$\mathcal{M}=({\mathcal{S}},{\mathcal{A}},H,\\{r_{h}\\}_{h\in[H]},\\{{\mathbb{P}}_{h}\\}_{h\in[H]})$
where ${\mathcal{S}}$ is the state space, ${\mathcal{A}}$ the action space,
$H\in\mathbb{Z}^{+}$ the length of each episode,
${\mathbb{P}}_{h}:{\mathcal{S}}\times{\mathcal{A}}\to\Delta({\mathcal{S}})$
the transition probability function, and
$r_{h}:{\mathcal{S}}\times{\mathcal{A}}\to{\mathbb{R}}$ the expected reward
function. A linear MDP assumes that both the transition probability and the
expected reward are linear in a known state-action feature map
${\bm{\phi}}(\cdot,\cdot)\in{\mathbb{R}}^{d}$ (Bradtke and Barto, 1996; Melo
and Ribeiro, 2007; Yang and Wang, 2019; Jin et al., 2020b).

######  Definition 2.2 (Linear MDP).

$\mathcal{M}$ is called a time-inhomogeneous linear MDP, if there exist some
known feature map
${\bm{\phi}}(s,a):{\mathcal{S}}\times{\mathcal{A}}\to\mathrm{Ball}_{d}(1)$,
unknown signed measures
$\\{{\bm{\mu}}_{h}^{*}\\}_{h\in[H]}\subseteq{\mathbb{R}}^{d\times|{\mathcal{S}}|}$,
and unknown coefficients
$\\{{\bm{\theta}}_{h}^{*}\\}_{h\in[H]}\subseteq\mathrm{Ball}_{d}(W)$ such that

$r_{h}(s,a)=\langle{\bm{\phi}}(s,a),{\bm{\theta}}_{h}^{*}\rangle,{\mathbb{P}}_{h}(\cdot|s,a)=\langle{\bm{\phi}}(s,a),{\bm{\mu}}_{h}^{*}(\cdot)\rangle,$

for any $(s,a)\in{\mathcal{S}}\times{\mathcal{A}},~{}h\in[H],$ where
$\|{\bm{\mu}}_{h}^{*}({\mathcal{S}})\|:=\|\sum_{s\in{\mathcal{S}}}{\bm{\mu}}_{h}^{*}(s)\|\leq\sqrt{d}$
for all $h\in[H]$.

For a time-inhomogeneous MDP, we denote its deterministic and time-dependent
policy by $\pi=\\{\pi_{h}\\}_{h\in[H]}$. Let $\\{(s_{h},a_{h})\\}_{h\in[H]}$
be state-action pairs such that $a_{h}=\pi_{h}(s_{h})$ and
$s_{h+1}\sim{\mathbb{P}}_{h}(\cdot|s_{h},a_{h})$. Define the occupancy measure
for the policy $\pi$ at the $h$-th round by
$d_{h}^{\pi}(s,a)={\mathbb{P}}^{\pi}(s_{h}=s,a_{h}=a|s_{1})$ where
$(a_{1},s_{2},a_{2},\cdots,s_{h},a_{h})$ is a trajectory starting from $s_{1}$
and following the policy $\pi$. The state-action function
$Q_{h}^{\pi}(\cdot,\cdot)$ and value function $V_{h}^{\pi}(\cdot)$ at the
$h$-th round are defined as

$\displaystyle
Q_{h}^{\pi}(\cdot,\cdot)={\mathbb{E}}[\sum_{i=h}^{H}r_{i}(s_{i},a_{i})|(s_{h},a_{h})=(\cdot,\cdot)]$

and $V_{h}^{\pi}(\cdot)=\sum_{a\in{\mathcal{A}}}Q_{h}^{\pi}(\cdot,a)$
respectively. For any value function $V$, write

$[{\mathbb{P}}_{h}V](s,a)={\mathbb{E}}_{s^{\prime}\sim{\mathbb{P}}_{h}(\cdot|s,a)}V(s^{\prime}),~{}~{}~{}[{\mathbb{V}}_{h}V](s,a)=[{\mathbb{P}}_{h}V^{2}](s,a)-[{\mathbb{P}}_{h}V]^{2}(s,a).$

With a slight abuse of notation, let $[{\mathbb{P}}_{h}R_{h}](s,a)$ and
$[{\mathbb{V}}_{h}R_{h}](s,a)$ denote the expectation and variance of the
random reward $R_{h}(s,a)$ at the $h$-th round given state-action pair
$(s,a)$. We consider linear MDPs with heavy-tailed random rewards that satisfy
the following assumptions.

######  Assumption 2.1 (Realizable reward).

We assume that the following hold.

  1. 1.

For all $(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$ and $h\in[H]$, the random
reward $R_{h}(s,a)$ is independent of $s_{h+1}(s,a)$, where
$s_{h+1}(s,a)\sim{\mathbb{P}}_{h}(\cdot|s,a)$ represents the next state
transitioned from $(s,a)$ at the $h$-th round.

  2. 2.

There exists known feature maps
$\widetilde{{\bm{\phi}}}(s,a):{\mathcal{S}}\times{\mathcal{A}}\to\mathrm{Ball}_{d}(1)$
and unknown coefficients
$\\{{\bm{\psi}}_{h}^{*}\\}_{h\in[H]}\subseteq\mathrm{Ball}_{d}(W)$ so that
$[{\mathbb{P}}_{h}R_{h}^{2}](s,a)=\langle\widetilde{{\bm{\phi}}}(s,a),{\bm{\psi}}_{h}^{*}\rangle$
for all $(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$ and $h\in[H]$.

######  Assumption 2.2 (Bounded variance).

We assume that the following hold.

  1. 1.

There exist known constants $\sigma_{R},\sigma_{R^{2}}>0$ such that
$[{\mathbb{V}}_{h}R_{h}](s,a)\leq\sigma_{R}^{2}$ and
$[{\mathbb{V}}_{h}R_{h}^{2}](s,a)\leq\sigma_{R^{2}}^{2}$ for all
$(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$ and $h\in[H]$.

  2. 2.

For any policy $\pi$, we have
$0\leq{\mathbb{E}}R_{\pi}\leq\mathcal{{\mathcal{H}}}$ and $\operatorname{{\rm
Var}}(R_{\pi})\leq{\mathcal{V}}^{2}$ where
$R_{\pi}=\sum_{h=1}^{H}R_{h}(s_{h},a_{h})$ denotes the sum of random rewards
along the trajectory following $\pi$.

Assumption 2.1 assumes that the random reward at each round is independent of
future states and its second moment can be realized using a known feature map.
Under this assumption, linear MDPs can recover tabular MDPs by setting the
size of the state-action space as $d=|{\mathcal{S}}||{\mathcal{A}}|$ and using
the canonical basis
${\bm{\phi}}(s,a)=\widetilde{{\bm{\phi}}}(s,a)={\bm{e}}_{(s,a)}$ in
${\mathbb{R}}^{d}$. Assumption 2.2 places upper bounds on the means of the
cumulative rewards, as well as on the variances of the random rewards, the
squared random rewards, and the cumulative rewards. This assumption
generalizes the uniformly bounded reward assumption found in the literature,
which requires
$0\leq\sup_{(s,a)\in{\mathcal{S}}\times{\mathcal{A}}}\sup_{h\in[H]}R_{h}(s,a)\leq
1$. As far as we know, Assumption 2.2 is the weakest moment condition on
random rewards in the RL literature.

##### Learning protocol

Let ${\mathcal{F}}_{h,k}$ denote the $\sigma$-field generated by all random
variables up to, and including, the $h$-th round and $k$-th episode. At the
beginning of each episode $k$, the environment selects the initial state
$s_{1,k}$. The agent proposes a policy $\pi_{k}=\\{\pi_{h}^{k}\\}_{h\in[H]}$
based on the history up to the end of episode $k-1$, and then executes
$\pi_{k}$ to generate a new trajectory
$\\{(s_{h,k},a_{h,k},r_{h,k})\\}_{h\in[H]}$. Here
$a_{h,k}=\pi_{h}^{k}(s_{h,k}),r_{h,k}\sim R_{h}(s_{h,k},a_{h,k})$ and
$s_{h+1,k}\sim{\mathbb{P}}(\cdot|s_{h,k},a_{h,k})$. The agent aims to minimize
the cumulative regret over $K$ episodes, given by:

$\mathrm{Reg}(K):=\sum_{k=1}^{K}(V_{1}^{*}-V_{1}^{\pi_{k}})(s_{1,k}).$

##  3 Variance-aware Regret for Linear Bandits

In this section, we introduce the AdaOFUL algorithm for linear bandits and
demonstrate its ability to achieve state-of-the-art variance-aware regret even
when faced with heavy-tailed rewards, as though the rewards were uniformly
bounded.

###  3.1 Algorithm Description

This section presents the AdaOFUL algorithm for heavy-tailed linear bandits.
The AdaOFUL algorithm is given in Algorithm 1. AdaOFUL follows the principle
of Optimism in the Face of Uncertainty (OFU) (Abbasi-Yadkori et al., 2011) to
solve the heavy-tailed heterogeneous linear bandit problem. At each round $t$,
it maintains a confidence set

${\mathcal{C}}_{t-1}:=\left\\{{{\bm{\theta}}}\in\mathrm{Ball}_{d}(B):\|{{\bm{\theta}}}-{{\bm{\theta}}}_{t-1}\|_{{\bm{H}}_{t-1}}\leq\beta_{t-1}\right\\}$
(3.1)

such that ${\bm{\theta}}^{*}\in{\mathcal{C}}_{t}$ uniformly for all $t\geq 1$
with high probability when the exploration radius $\beta_{t-1}$ is properly
chosen. Unlike the standard OFUL algorithm (Abbasi-Yadkori et al., 2011) which
directly selects the most optimistic estimator $\widetilde{\bm{\theta}}_{t}$
to make an arm selection ${\bm{\phi}}_{t}$, AdaOFUL uses adaptive Huber
regression to compute a new estimator ${\bm{\theta}}_{t}$ that takes into
account the heavy-tailed rewards. The agent then selects the arm
${\bm{\phi}}_{t}$ that maximizes the inner product
$\langle{\bm{\phi}},{\bm{\theta}}\rangle$ with the new estimator
${\bm{\theta}}_{t}$. After playing the selected arm, the agent observes the
reward $y_{t}$ and its conditional variance $\nu_{t}$. The last step of round
$t$ updates the exploration radius $\beta_{t}$ and the shape matrix
${\bm{H}}_{t}$ for the confidence set construction in the next round.

Initialization :

${\bm{H}}_{0}=\lambda{\bm{I}},{\bm{\theta}}_{0}={\bm{0}},\beta_{0}=\sqrt{\lambda}B,c_{0}=\frac{1}{6\sqrt{3\log\frac{2T^{2}}{\delta}}},c_{1}=\frac{1}{42\cdot\log\frac{2T^{2}}{\delta}},\sigma_{\min}=\frac{1}{\sqrt{T}}$.

for  _$t=1$ to $T$_ do

2 Construct the confidence set ${\mathcal{C}}_{t-1}$ as in (3.1) Solve
$({\bm{\phi}}_{t},\cdot)=\mathop{\rm
argmax}_{{\bm{\phi}}\in{\mathcal{D}}_{t},{\bm{\theta}}\in{\mathcal{C}}_{t-1}}\langle{\bm{\phi}},{\bm{\theta}}\rangle$.
Play ${\bm{\phi}}_{t}$ and observe $(y_{t},\nu_{t})$. Set $\sigma_{t},w_{t}$
and $\tau_{t}$ according to (3.4) and record
$\\{\sigma_{s},w_{s},\tau_{s}:1\leq s\leq t\\}$. Compute ${\bm{\theta}}_{t}$
by minimizing (3.3). Define $\beta_{t}$ as in (3.5) and set
${\bm{H}}_{t}={\bm{H}}_{t-1}+\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\frac{{\bm{\phi}}_{t}^{\top}}{\sigma_{t}}$.

3 end for

Algorithm 1 Adaptive Huber regression based OFUL (AdaOFUL)

##### Pseudo-Huber regression

The pseudo-Huber loss (Hastie et al., 2009; Sun, 2021) is defined as

$\ell_{\tau}(x)=\tau(\sqrt{\tau^{2}+x^{2}}-\tau),$ (3.2)

which is a smooth approximation to the well-known Huber loss (Huber, 1964).
Similar to the Huber loss, the pseudo-Huber loss resembles a quadratic
function for small values of $|x|$ and is approximately linear when $x$ is
large in magnitude, making the loss strongly convex when close to the origin
and less sensitive to changes in the tails. The parameter $\tau$ controls the
balance between the quadratic and linear regions and is referred to as the
robustification parameter by Sun et al. (2020) in the case of the Huber loss.
Since the value of the robustification parameter needs to be adaptive to the
data for an optimal tradeoff between robustness and unbiasedness, we shall
also refer to the pseudo-Huber regression with a data-adaptive $\tau$ as
adaptive pseudo-Huber regression or simply adaptive Huber regression, in line
with (Sun et al., 2020).

To compute the pseudo-Huber estimator ${\bm{\theta}}_{t}$ for
${\bm{\theta}}^{*}$, given the history
$\\{({\bm{\phi}}_{s},y_{s},\nu_{s})\\}_{s\in[t]}$ up to time $t$, we solve the
following convex optimization problem (Sun, 2021):

$\displaystyle{{\bm{\theta}}}_{t}:=\mathop{\rm
argmin}_{{\bm{\theta}}\in\mathrm{Ball}_{d}(B)}L_{t}({{\bm{\theta}}})~{}\text{with}~{}L_{t}({{\bm{\theta}}}):=\frac{\lambda}{2}\|{\bm{\theta}}\|^{2}+\sum_{s=1}^{t}\ell_{\tau_{s}}\left(\frac{y_{s}-\langle{\bm{\phi}}_{s},{\bm{\theta}}\rangle}{\sigma_{s}}\right)$
(3.3)

where $\sigma_{t}$’s are surrogate conditional variances, and $\tau_{t}$’s are
the robustification parameters, given by:

$\sigma_{t}=\max\left\\{\nu_{t},\sigma_{\min},\frac{\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}}}{c_{0}},\frac{\sqrt{LB}\|{\bm{\phi}}_{t}\|^{\frac{1}{2}}_{{\bm{H}}_{t-1}^{-1}}}{c_{1}^{\frac{1}{4}}d^{\frac{1}{4}}}\right\\},w_{t}=\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{t-1}^{-1}},~{}\tau_{t}=\tau_{0}\frac{\sqrt{1+w_{t}^{2}}}{w_{t}},$
(3.4)

in which $\sigma_{\min}$ is a small positive constant to avoid singularity,
$\tau_{0}$ is a hyper-parameter, $w_{t}$’s are importance measures, $c_{0}$
and $c_{1}$ are specified in Algorithm 1, and $L$ and $B$ are constants
deinfed in Definition 2.1.

As shown in (3.4), the robustification parameter $\tau_{t}$ is set differently
for each data point $({\bm{\phi}}_{t},y_{t},\nu_{t})$ in the pseudo-Huber
regression. This is a significant departure from the case of i.i.d. data,
where all robustification parameters are typically set to the same value
$\tau$, as i.i.d. data are naturally weighted equally (Sun et al., 2020). In
linear bandits, the data is generated adaptively, where the choice of
${\bm{\phi}}_{t}$ can depend on all past observations. Since observations
collected in later rounds are less important as they are based on previous
observations and contribute less to the estimation accuracy, we assign greater
weight to earlier observations. To measure the importance of the $t$-th
observation, we use
$w_{t}=\left\|{\bm{\phi}}_{t}\right\|_{{\bm{H}}_{t-1}^{-1}}/\sigma_{t}$ as the
importance measure for the $t$-th observation and set
$\tau_{t}=\tau_{0}{\sqrt{1+w_{t}^{2}}}/{w_{t}}$ as the corresponding
robustification parameter.

When taking $\tau_{0}=\infty$, the optimization problem in (3.3) reduces to
weighted regularized least-squares, which has been proven to achieve worst-
case optimality for linear bandits with uniformly bounded or sub-Gaussian
rewards (Kirschner and Krause, 2018; Zhou and Gu, 2022). However, an
appropriate value of $\tau_{0}$ is necessary to balance robustness against
heavy-tailed rewards and asymptotic unbiasedness. In Corollary 3.1, we will
demonstrate that setting $\tau_{0}=\widetilde{\mathcal{O}}(\sqrt{d})$ is
sufficient to achieve the state-of-the-art regret bound.

Lastly, we choose
$\sigma_{t}\geq\sqrt{LB}{\|{\bm{\phi}}_{t}\|^{\frac{1}{2}}_{{\bm{H}}_{t-1}^{-1}}}/(c_{1}^{\frac{1}{4}}d^{\frac{1}{4}})$,
which implies $c_{1}d\geq{L^{2}B^{2}w_{t}^{2}}/({\sigma_{t}^{2}})$. This
condition is used to lower bound the Hessian matrix
$\nabla^{2}L_{T}({{\bm{\theta}}})$. For any
${{\bm{\theta}}}\in\mathrm{Ball}_{d}(B)$, we expect
$\nabla^{2}L_{T}({{\bm{\theta}}})\approx{\bm{H}}_{T}$ up to universal constant
factors to proceed with theoretical analysis. A direct computation yields
$\nabla^{2}L_{T}({{\bm{\theta}}})\preceq{\bm{H}}_{T}$, while for the other
direction we show
$\nabla^{2}L_{T}({{\bm{\theta}}})\succeq\left(c-\sup_{t\in[T]}\left|\frac{\langle{\bm{\phi}}_{t},{{\bm{\theta}}}^{*}-{{\bm{\theta}}}\rangle}{\tau_{t}\sigma_{t}}\right|^{2}\right){\bm{H}}_{T}$
for some universal constant $c>0$ with high probability. With the last
condition on $\sigma_{t}$, for any feasible solution
${{\bm{\theta}}}\in\mathrm{Ball}_{d}(B)$, the following quantity

$\displaystyle\left|\frac{\langle{\bm{\phi}}_{t},{{\bm{\theta}}}^{*}-{{\bm{\theta}}}\rangle}{\tau_{t}\sigma_{t}}\right|^{2}\leq\frac{\|{\bm{\phi}}_{t}\|^{2}\|{{\bm{\theta}}}^{*}-{{\bm{\theta}}}\|^{2}}{\tau_{t}^{2}\sigma_{t}^{2}}\leq\frac{4w_{t}^{2}L^{2}B^{2}}{\tau_{0}^{2}\sigma_{t}^{2}}\leq\frac{4c_{1}d}{\tau_{0}^{2}}$

can be sufficiently small provided that $\tau_{0}^{2}\gtrsim c_{1}d$.

###  3.2 Regret Analysis

We first validate that the optimism holds with high probability in Theorem 3.1
and then establish a high probability bound for the regret in Theorem 3.2.

######  Theorem 3.1.

Let $\kappa=d\cdot\log\left(1+{TL^{2}}/({d\lambda\sigma_{\min}^{2}})\right)$.
For the heavy-tailed linear bandit in Definition 2.1, if
$\tau_{0}\sqrt{\log({2T^{2}}/{\delta})}\geq\max\\{\sqrt{2\kappa},2\sqrt{d}LB\\}$,
then with probability at least $1-3\delta$, it holds that, for all $0\leq
t\leq T$,

$\|{\bm{\theta}}_{t}-{\bm{\theta}}^{*}\|_{{\bm{H}}_{t}}\leq\beta_{t},$

where

$\beta_{t}=32\bigg{(}\underbrace{\frac{\kappa}{\tau_{0}}}_{\text{bias
term}}+\underbrace{\vphantom{\left(\frac{a^{0.3}}{b}\right)}\sqrt{\kappa\log\frac{2t^{2}}{\delta}}}_{\text{variance
term}}+\underbrace{\vphantom{\left(\frac{a^{0.3}}{b}\right)}\tau_{0}\log\frac{2t^{2}}{\delta}}_{\text{range
term}}\bigg{)}+\underbrace{\vphantom{\left(\frac{a^{0.3}}{b}\right)}5\sqrt{\lambda}B}_{\text{ridge
term}}.$ (3.5)

Theorem 3.1 establishes that ${{\bm{\theta}}}^{*}$ is contained in the set
${\mathcal{C}}_{t}:=\left\\{{{\bm{\theta}}}\in\mathrm{Ball}_{d}(B):\|{{\bm{\theta}}}-{{\bm{\theta}}}_{t}\|_{{\bm{H}}_{t}}\leq\beta_{t}\right\\}$
for all $t\geq 0$ with high probability. It is proved by using Bernstein-type
concentration inequality for self-normalized vector-valued martingales with
additional care paid to deal with heavy-tailed rewards. To explain the source
of each term in (3.5), we first note that at a high level,
$\|{\bm{\theta}}_{t}-{\bm{\theta}}^{*}\|_{{\bm{H}}_{t}}\lesssim\|\nabla
L_{t}({{\bm{\theta}}}^{*})\|_{{\bm{H}}_{t}^{-1}}$. Following Zhou et al.
(2021), an iterative analysis yields that $\|\nabla
L_{t}({{\bm{\theta}}}^{*})\|_{{\bm{H}}_{t}^{-1}}^{2}=\sum_{t=1}^{T}(X_{t}+Y_{t})$
for two sequences of bounded random variables
$X_{t},Y_{t}\in{\mathcal{F}}_{t}$. To illustrate the proof idea, we explain
how to bound $\sum_{t=1}^{T}X_{t}$, since $\sum_{t=1}^{T}Y_{t}$ can be bounded
similarly. Here $\\{X_{t}\\}_{t\in[T]}$ is not a martingale difference
sequence but $\\{X_{t}-{\mathbb{E}}[X_{t}|{\mathcal{F}}_{t-1}]\\}_{t\in[T]}$
is. We apply a standard Bernstein inequality to provide an upper bound for
$\sum_{t=1}^{T}(X_{t}-{\mathbb{E}}[X_{t}|{\mathcal{F}}_{t-1}])$ that
contributes to the variance and range terms. Thanks to the different
robustification parameters $\tau_{t}$, we can control
$\sum_{t=1}^{T}{\mathbb{E}}[X_{t}|{\mathcal{F}}_{t-1}]$ deterministically
within ${\mathcal{O}}\left({\kappa^{2}}/{\tau_{0}^{2}}\right)$, resulting in
the bias term. Finally, the last ridge term $5\sqrt{\lambda}B$ exists because
we use ridge regression to ensure that the Hessian is always invertible.

######  Theorem 3.2.

Let $\sigma_{\min}={1}/{\sqrt{T}}$. Then with probability at least
$1-3\delta$, we have

$\mathrm{Reg}(T)\leq
2\beta_{T}\cdot\left[\sqrt{2\kappa}\cdot\sqrt{\sum_{t=1}^{T}\nu_{t}^{2}+1}+\frac{2L\kappa}{c_{0}^{2}\sqrt{\lambda}}+\frac{2LB\kappa}{\sqrt{c_{1}d}}\right]$

where $\beta_{T}$ is defined in (3.5), and
$c_{0},c_{1}=\widetilde{\mathcal{O}}(1)$ are positive constants given in
Algorithm 1.

Theorem 3.2 provides a regret bound in a general form that depends on
$\beta_{T}$. As shown in (3.4), $\beta_{t}$ is a hyperbolic function of the
robustification parameter $\tau_{0}$. Increasing $\tau_{0}$ decreases the bias
term ${\mathcal{O}}\left({\kappa}/{\tau_{0}}\right)$ while increasing the
range term ${\mathcal{O}}\left(\tau_{0}\log({2t^{2}}/{\delta})\right)$.
Therefore, choosing $\tau_{0}$ carefully is essential to achieve the optimal
trade-off between unbiasedness and robustness. Setting
$\tau_{0}=\widetilde{\mathcal{O}}(\sqrt{d})$ minimizes the right-hand side of
(3.5). This, combined with Theorem 3.2, yields the simplified regret bound
(3.6) in the following corollary.

######  Corollary 3.1.

Let
$\tau_{0}=\max\big{\\{}\sqrt{2\kappa},2\sqrt{d}\big{\\}}/\sqrt{\log({2T^{2}}/{\delta})}$
and $\lambda={d}/{B^{2}}$, then

$\displaystyle\beta_{T}\leq
64\left(2\sqrt{\kappa\log({2T^{2}}/{\delta})}+\sqrt{d\log({2T^{2}}/{\delta})}\right)+5\sqrt{d}.$

Consequently, the regret bound in Theorem 3.2 reduces to

$\mathrm{Reg}(T)=\widetilde{{\mathcal{O}}}\left(d\sqrt{\sum_{t\in[T]}\nu_{t}^{2}}+d\cdot\max\\{LB,1\\}\right),$
(3.6)

where $\widetilde{{\mathcal{O}}}(\cdot)$ hides constant factors and
logarithmic dependence on $T$.

Corollary 3.1 demonstrates that AdaOFUL achieves the state-of-the-art regret
bound in the presence of heavy-tailed rewards, comparable to the case where
rewards are uniformly bounded or sub-Gaussian. The regret upper bound in the
noiseless case reduces to $\widetilde{{\mathcal{O}}}(d)$, and in the noisy
case, it reduces to
$\widetilde{{\mathcal{O}}}\left(d\sqrt{\sum_{t\in[T]}\nu_{t}^{2}}\right)$. In
the worst case scenario where $\nu_{t}=\Theta(1)$ for all $t\geq 1$, the
regret bound reduces to $\widetilde{\mathcal{O}}(d\sqrt{T})$, which matches
the worst-case minimax lower bound (Dani et al., 2008). Hence, our variance-
aware regret bound (3.6) is tighter than the pessimistic worst-case bound
$\widetilde{\mathcal{O}}(d\sqrt{T})$ when $\sum_{t=1}^{T}\nu_{t}^{2}\ll T$. To
the best of our knowledge, such a variance-aware regret bound has only been
obtained in the literature for sub-Gaussian rewards (Kirschner and Krause,
2018) or uniformly bounded rewards (Zhou and Gu, 2022). We are the first to
provide a variance-aware regret bound for heavy-tailed stochastic linear
bandits.

##  4 Variance Aware Regret for Linear MDPs

###  4.1 High-level Algorithm Description

In this section, we present VARA, an algorithm collected in Algorithm 2, that
extends AdaOFUL to solve linear MDPs with heavy-tailed rewards. The VARA
algorithm is built on LSVI-UCB++(He et al., 2022), an algorithm proposed
recently to achieve minimax optimality for linear MDPs. LSVI-UCB++(He et al.,
2022) uses weighted ridge regression, where the weights depend on some proper
variance estimators $\sigma_{h,k}$’s. The variance estimation techniques in
LSVI-UCB++ can also be used to obtain variance-aware regrets. These techniques
include (i) separate variance estimation, (ii) monotonicity of value
functions, and (iii) rare-switching value function update.

We present a detailed algorithm description in the next subsection, focusing
on the differences between VARA and LSVI-UCB++ (He et al., 2022). To obtain
variance-aware regrets under heavy-tailed rewards, we made two improvements to
LSVI-UCB++. First, while LSVI-UCB++ assumes a deterministic, uniformly
bounded, and known reward function, we use AdaOFUL to estimate the parameters
${\bm{\theta}}_{h}^{*}$ and ${\bm{\psi}}_{h}^{*}$ for both the expected reward
functions and their second-order moments. This complicates the construction of
the variance estimators $\sigma_{h,k}$ and requires a more detailed analysis
of their impacts on the final regrets (see Lemma C.10). Second, previous works
use the Azuma-Hoeffding inequality to analyze the concentration effect in the
suboptimality gap, which leads to regret of
$\widetilde{\mathcal{O}}(\sqrt{K})$. Instead, we use a variance-aware
Bernstein inequality and produce a much tighter upper bound of
$\widetilde{\mathcal{O}}(1)$ for the concentration effect(see Lemma C.8). We
explain the analytical novelty in detail in Appendix C.2.

Require :

$K,H,{\mathcal{H}},{\mathcal{V}},W,\sigma_{R},\sigma_{R^{2}},\tau_{0},\widetilde{\tau}_{0}$.

Initialization :

${\bm{H}}_{h,0}=\widetilde{{\bm{H}}}_{h,0}=\lambda{\bm{I}},c_{0}=\frac{1}{6\sqrt{3\log\frac{2HK^{2}}{\delta}}},c_{1}=\frac{1}{42\cdot\frac{2HK^{2}}{\delta}},\lambda=\frac{1}{{\mathcal{H}}^{2}+W^{2}},k_{\mathrm{last}}=1$.

for  _episode $k=1$ to $K$ _ do

2 $\overline{V}_{H+1}^{k}(\cdot)=\underline{V}_{H+1}^{k}(\cdot)=0$ for  _round
$h=H$ to $1$ _ do

3 if  _there exists a stage $h^{\prime}\in[H]$ such that
$\mathrm{det}({\bm{H}}_{h^{\prime},k-1})\geq
2\mathrm{det}({\bm{H}}_{h^{\prime},k_{\mathrm{last}}-1})$_ then

4
$\widehat{Q}_{h}^{k}(\cdot,\cdot)=\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k-1}+{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k}\rangle+\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}}$.
$\widecheck{Q}_{h}^{k}(\cdot,\cdot)=\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k-1}+{\bm{\mu}}_{h,k-1}\underline{{\bm{V}}}_{h+1}^{k}\rangle-\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}}$.
$\overline{Q}_{h}^{k}(\cdot,\cdot)=\min\left\\{\widehat{Q}_{h}^{k}(\cdot,\cdot),\overline{Q}_{h}^{k-1}(\cdot,\cdot),{\mathcal{H}}\right\\}$,
$\underline{Q}_{h}^{k}(\cdot,\cdot)=\max\left\\{\widecheck{Q}_{h}^{k}(\cdot,\cdot),\underline{Q}_{h}^{k-1}(\cdot,\cdot),0\right\\}$.
Record the last updating episode $k_{\mathrm{last}}=k$.

5 else

6
$\overline{Q}_{h}^{k}(\cdot,\cdot)=\overline{Q}_{h}^{k-1}(\cdot,\cdot),\underline{Q}_{h}^{k}(\cdot,\cdot)=\underline{Q}_{h}^{k-1}(\cdot,\cdot)$.

7 end if

8
$\overline{V}_{h}^{k}(\cdot)=\max_{a}\overline{Q}_{h}^{k}(\cdot,a),\underline{V}_{h}^{k}(\cdot)=\max_{a}\underline{Q}_{h}^{k}(\cdot,a)$.
$\pi_{h}^{k}(\cdot)\in\mathop{\rm argmax}_{a}\overline{Q}_{h}^{k}(\cdot,a)$.

9 end for

10 Receive the initial state $s_{1,k}$. for  _round $h=1$ to $H$_ do

11 Play $a_{h,k}=\pi_{h}^{k}(s_{h,k})$ and observe $r_{h,k}\sim
R_{h}(s_{h,k},a_{h,k}),s_{h+1,k}\sim{\mathbb{P}}(\cdot|s_{h,k},a_{h,k})$.
Observe feature vectors ${\bm{\phi}}_{h,k}={\bm{\phi}}(s_{h,k},a_{h,k})$ and
$\widetilde{{\bm{\phi}}}_{h,k}=\widetilde{{\bm{\phi}}}(s_{h,k},a_{h,k})$. Set
the bonus as
$b_{h,k}=\max\\{{\|{\bm{\phi}}_{h,k}\|}_{{\bm{H}}_{h,k-1}^{-1}},{\|\widetilde{{\bm{\phi}}}_{h,k}\|}_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}\\}$.
Set the estimated variance $\sigma_{h,k}$ as in (4.5). Compute
${\bm{\mu}}_{h,k}$ via (4.2). Compute ${\bm{\theta}}_{h,k}$ via (4.1) with
$\tau_{h,k}=\tau_{0}\sqrt{1+w_{h,k}^{2}}/{w_{h,k}}$ and
$w_{h,k}=\sigma_{h,k}^{-1}\left\|{\bm{\phi}}_{h,k}\right\|_{{\bm{H}}_{h,k-1}^{-1}}$.
Compute ${\bm{\psi}}_{h,k}$ via (4.3) with
$\widetilde{\tau}_{h,k}=\widetilde{\tau}_{0}\sqrt{1+\widetilde{w}_{h,k}^{2}}/{\widetilde{w}_{h,k}}$
and
$\widetilde{w}_{h,k}=\sigma_{h,k}^{-1}\left\|\widetilde{{\bm{\phi}}}_{h,k}\right\|_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}$.
Update
${\bm{H}}_{h,k}={\bm{H}}_{h,k-1}+\sigma_{h,k}^{-2}{\bm{\phi}}_{h,k}{\bm{\phi}}_{h,k}^{\top}$
and
$\widetilde{{\bm{H}}}_{h,k}=\widetilde{{\bm{H}}}_{h,k-1}+\sigma_{h,k}^{-2}\widetilde{{\bm{\phi}}}_{h,k}\widetilde{{\bm{\phi}}}_{h,k}^{\top}$.

12 end for

13

14 end for

Algorithm 2 The VARA algorithm

###  4.2 Detailed Algorithm Description

For each episode $k$, we perform optimistic value iterations (Lines 3-11),
compute the greedy policy $\pi_{h}^{k}$ with respective to the pessimistic
value function $\overline{Q}_{h}^{k}$ (Line 12), and then execute it to
collect a new trajectory of data (Lines 16-17). The rest of Algorithm 2
updates maintained estimators, including the conditional variances
$\sigma_{h,k}^{2}$ (Line 19), the transition parameters ${\bm{\mu}}_{h,k}$
(Line 20), the reward parameters ${\bm{\theta}}_{h,k},{\bm{\psi}}_{h,k}$
(Lines 21-22), and the Hessian matrices
${\bm{H}}_{h,k},\widetilde{{\bm{H}}}_{h,k}$ (Line 23). In what follows, we
discuss in detail the key steps of Algorithm 2 in more detail.

##### Reward estimation

Since rewards are collected in an adaptive manner and have only finite second
moments, we use the same strategy adopted in AdaOFUL to estimate
${\bm{\theta}}_{h}^{*}$:

${{\bm{\theta}}}_{h,k}:=\mathop{\rm
argmin}_{{\bm{\theta}}\in\mathrm{Ball}_{d}(W)}\left\\{L_{h,k}^{(R)}({{\bm{\theta}}}):=\frac{\lambda}{2}\|{\bm{\theta}}\|^{2}+\sum_{j=1}^{k}\ell_{\tau_{h,j}}\left(\frac{r_{h,j}-\langle{\bm{\phi}}_{h,j},{\bm{\theta}}\rangle}{\sigma_{h,j}}\right)\right\\}.$
(4.1)

Following the spirit of Theorem 3.1, we set
$\tau_{0}=\widetilde{\mathcal{O}}(\sqrt{d})$ with its detailed expression
provided in (C.5) of the online supplement.

##### Transition estimation

Let ${\bm{\delta}}(s)\in{\mathbb{R}}^{|{\mathcal{S}}|}$ be a one-hot vector
that is zero everywhere except for the entry corresponding to the state $s$,
which is one. We define
${\bm{\varepsilon}}_{h,k}={\mathbb{P}}_{h}(\cdot|s_{h,k},a_{h,k})-{\bm{\delta}}(s_{h+1,k})$.
As ${\mathbb{E}}[{\bm{\varepsilon}}_{h,k}|{\mathcal{F}}_{h,k}]={\bm{0}}$,
${\bm{\delta}}(s_{h+1,k})$ is an unbiased estimator of
${\mathbb{P}}_{h}(\cdot|s_{h,k},a_{h,k})={\bm{\mu}}_{h}^{\top}{\bm{\phi}}(s_{h,k},a_{h,k})={\bm{\mu}}_{h}^{\top}{\bm{\phi}}_{h,k}$.
Thus, we can learn ${\bm{\mu}}_{h}$ by regressing ${\bm{\delta}}(s_{h+1,k})$
on ${\bm{\phi}}_{h,k}:=\mbox{\boldmath$\phi$\unboldmath}(s_{h,k},a_{h,k})$:

${\bm{\mu}}_{h,k}:=\mathop{\rm
argmin}_{{\bm{\mu}}\in{\mathbb{R}}^{d\times|{\mathcal{S}}|}}\left\\{L_{h,k}^{(P)}({\bm{\mu}}):=\frac{\lambda}{2}\|{\bm{\mu}}\|_{F}^{2}+\sum_{j=1}^{k}\left\|\frac{{\bm{\mu}}_{h}^{\top}{\bm{\phi}}_{h,k}-{\bm{\delta}}(s_{h+1,j})}{\sigma_{h,j}}\right\|^{2}\right\\}$
(4.2)

where $\|\cdot\|_{F}$ denotes the Frobenius norm. This problem admits a
closed-form solution given by
${\bm{\mu}}_{h,k}={\bm{H}}_{h,k}^{-1}\sum_{j=1}^{k}\sigma_{h,j}^{-2}{\bm{\phi}}_{h,j}{\bm{\delta}}(s_{h+1,j})^{\top}$.

##### Variance estimation for rewards

In linear MDPs, estimating the variance of the reward $R_{h}(s,a)$ is
straightforward. Since
${\mathbb{P}}_{h}R_{h}^{2}(s,a)=\langle\widetilde{{\bm{\phi}}}(s,a),{\bm{\psi}}_{h}^{*}\rangle$,
we estimate ${\bm{\psi}}_{h}^{*}$ by

${\bm{\psi}}_{h,k}:=\mathop{\rm
argmin}_{{\bm{\psi}}\in\mathrm{Ball}_{d}(W)}\left\\{L_{h,k}^{(R^{2})}({\bm{\psi}}):=\frac{\lambda}{2}\|{\bm{\psi}}\|^{2}+\sum_{j=1}^{k}\ell_{\widetilde{\tau}_{h,j}}\left(\frac{r_{h,j}^{2}-\langle\widetilde{{\bm{\phi}}}_{h,j},{\bm{\psi}}\rangle}{\sigma_{h,j}}\right)\right\\}$
(4.3)

where
$\widetilde{\tau}_{h,k}=\widetilde{\tau}_{0}\sqrt{1+\widetilde{w}_{h,k}^{2}}/\widetilde{w}_{h,k}$
is the corresponding robustification parameter and
$\widetilde{w}_{h,k}=\|\widetilde{{\bm{\phi}}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}$
is the importance weight. We then estimate
$[{\mathbb{V}}_{h}R_{h}](s_{h},a_{h})$ by

$[\widehat{\mathbb{V}}_{h}R_{h}](s_{h,k},a_{h,k})=\langle\widetilde{{\bm{\phi}}}_{h,k},{\bm{\psi}}_{h,k-1}\rangle-\left[\langle{\bm{\phi}}_{h,k},{{\bm{\theta}}}_{h,k-1}\rangle_{[0,{\mathcal{H}}]}\right]^{2}.$
(4.4)

##### Variance estimation

Inspired by Hu et al. (2022), we set the variance estimator $\sigma_{h,k}$ to
be

$\sigma_{h,k}^{2}=\max\left\\{\sigma_{\min}^{2},\,d^{3}H\cdot
E_{h,k},\,J_{h,k},\,c_{0}^{-2}b_{h,k}^{2},\,\left(\frac{W}{\sqrt{c_{1}d}}+{\mathcal{H}}d^{2.5}H\right)b_{h,k}\right\\}$
(4.5)

where $\sigma_{\min}$ is a small positive constant to avoid singularity,
$b_{h,k}=\max\\{{\|{\bm{\phi}}_{h,k}\|}_{{\bm{H}}_{h,k-1}^{-1}},{\|\widetilde{{\bm{\phi}}}_{h,k}\|}_{\widetilde{{\bm{H}}}_{h,k-1}^{-1}}\\}$
is the bonus term, $E_{h,k}$ and $J_{h,k}$ are defined as

$\displaystyle
J_{h,k}=[\widehat{\mathbb{V}}_{h,k}R_{h}+\widehat{\mathbb{V}}_{h,k}\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k})+R_{h,k}+U_{h,k},$
(4.6) $\displaystyle
E_{h,k}=\min\left\\{{\mathcal{H}}^{2},2{\mathcal{H}}\beta_{0}\cdot\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+{\mathcal{H}}\cdot\left[\widehat{\mathbb{P}}_{h,k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})\right](s_{h,k},a_{h,k})\right\\},$
(4.7)

in which
$\beta_{0}=\widetilde{\mathcal{O}}\left(\sigma_{\min}^{-1}{{\mathcal{H}}}\sqrt{d^{3}H}\right)$
is an initial exploration radius,
$\widehat{{\mathbb{P}}}_{h,k}(\cdot|s,a)={\bm{\mu}}_{h,k-1}^{\top}{\bm{\phi}}(s,a)$
is the empirical transition kernel at the $h$-th round and $k$-the episode,
$\widehat{\mathbb{V}}_{h}(\cdot)$ the empirical variance operator defined in
(4.4), and $R_{h,k},U_{h,k}$ are defined as

$\displaystyle
R_{h,k}:=\beta_{R^{2}}\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{k-1}}+2{\mathcal{H}}\beta_{R}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}},$
(4.8) $\displaystyle
U_{h,k}=\min\left\\{{\mathcal{V}}^{2},11{\mathcal{H}}\beta_{0}\cdot\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+4{\mathcal{H}}\cdot\widehat{\mathbb{P}}_{h,k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})\right\\},$
(4.9)

with
$\beta_{R}=\widetilde{\mathcal{O}}(\sqrt{d}),\beta_{R^{2}}=\widetilde{\mathcal{O}}\left(\sqrt{d}+\sqrt{d}\frac{\sigma_{R^{2}}}{\sigma_{\min}}\right)$
being two initial exploration radiuses. In Appendix A, we explain in detail
why $\sigma_{h,k}$’s are taken in the above way.

###  4.3 Regret Analysis

This section presents the statistical, space, and computational complexities
of Algorithm 2.

######  Theorem 4.1.

Consider a linear MDP satisfying Asumption 2.1 and 2.2. For any
$\delta\in(0,1)$, with probability at least $1-10\delta$, Algorithm 2 achieves

$\displaystyle\begin{split}&\sum_{k=1}^{K}(V_{1}^{*}-V_{1}^{\pi_{k}})(s_{1,k})=\widetilde{\mathcal{O}}\left(d\sqrt{HK{\mathcal{G}}^{*}}+Hd\sqrt{K}\sigma_{\min}\right)\\\
&+\widetilde{\mathcal{O}}\left(\frac{H^{2.5}d^{6}{\mathcal{H}}^{2}+Hd^{2}\sigma_{R^{2}}}{\sigma_{\min}}+H^{3}d^{5}{\mathcal{H}}+Hd\sigma_{R}+Hd^{2}\right),\end{split}$
(4.10)

where $\sigma_{\min}$ is a manually set lower bound for all variance
estimators $\sigma_{h,k}$’s,

${\mathcal{G}}^{*}=\min\left\\{\sum_{h=1}^{H}\sum_{(s,a)}\widetilde{d}_{h}^{K}(s,a)\cdot[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s,a),{\mathcal{V}}^{2}\right\\},$
(4.11)
$\widetilde{d}_{h}^{K}(s,a)=\frac{1}{K}\sum_{k=1}^{K}d_{h}^{\pi_{k}}(s,a),$
(4.12)

and
$d_{h}^{\pi_{k}}(s,a)={\mathbb{P}}^{\pi_{k}}(s_{h}=s,a_{h}=a|s_{0}=s_{1,k})$
is the probability of reaching $(s_{h,k},a_{h,k})=(s,a)$ at the $h$-th step
when the agent starts from $s_{1,k}$ and follows the policy $\pi_{k}$.

##### Trade-off by $\sigma_{\min}$

Theorem 4.1 reveals a trade-off that arises from the choice of
$\sigma_{\min}$. The second term in (4.10) is positively dependent on
$\sigma_{\min}$ due to the sum of bonuses
$\sum_{k=1}^{K}\sum_{h=1}^{H}b_{h,k}$, while the third term is negatively
dependent on $\sigma_{\min}$ due to the initial exploration radiuses
$\beta_{R^{2}},\beta_{0}$ being linearly dependent on ${1}/{\sigma_{\min}}$. A
larger $\sigma_{\min}$ leads to smaller initial exploration radiuses and
higher accuracies of the confidence sets used in variance estimation,
resulting in a decrease in regret. However, it also leads to larger
accumulated bonuses, which can be seen as a cost for exploration, and
increases regret. The choice of $\sigma_{\min}$ must balance these opposing
effects. Corollary 4.1 implies that choosing the optimal
$\sigma_{\min}^{*}=\sqrt{H^{1.5}d^{5}{\mathcal{H}}^{2}+d\sigma_{R^{2}}}\cdot
K^{-\frac{1}{4}}$ yields a regret barrier of
$\widetilde{\mathcal{O}}\left(Hd\cdot\sqrt{d^{5}{\mathcal{H}}^{2}+d\sigma_{R^{2}}}\cdot\sqrt[4]{K}\right)$.
When $K$ is sufficiently large, the regret bound in (4.13) can be further
simplified to
$\widetilde{\mathcal{O}}\left(d\sqrt{H{\mathcal{G}}^{*}K}\right)$. To the best
of our knowledge, Theorem 4.1 is the first to derive the variance-aware regret
for linear MDPs, especially with heavy-tailed rewards.

######  Corollary 4.1.

Under the same setting of Theorem 4.1, if we set
$\sigma_{\min}=\sqrt{H^{1.5}d^{5}{\mathcal{H}}^{2}+d\sigma_{R^{2}}}\cdot
K^{-\frac{1}{4}}$, the regret of VARA is bounded by

$\begin{gathered}\widetilde{\mathcal{O}}\left(d\sqrt{H{\mathcal{G}}^{*}K}+Hd\sqrt{d^{5}{\mathcal{H}}^{2}+d\sigma_{R^{2}}}\cdot\sqrt[4]{K}+H^{3}d^{5}{\mathcal{H}}+Hd\sigma_{R}+Hd^{2}\right).\end{gathered}$
(4.13)

##### Instance-dependent quantity ${\mathcal{G}}^{*}$

The quantity ${\mathcal{G}}^{*}$ is given by (4.11). Firstly, it is bounded
above by ${\mathcal{V}}^{2}$ in Assumption 2.2, which sets an upper bound on
the variance of the sum of random rewards received when following any policy.
Secondly, ${\mathcal{G}}^{*}$ is no greater than the sum of per-round
conditional variances
$[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s,a)$, weighted by an
averaged occupancy measure
$\widetilde{d}h^{K}(s,a):=\frac{1}{K}\sum{k=1}^{K}d_{h}^{\pi_{k}}(s,a)$. The
function $\widetilde{d}_{h}^{K}(\cdot,\cdot)$ introduces a probability measure
on ${\mathcal{S}}\times{\mathcal{A}}$ for any fixed $h\in[H]$, in accordance
with the definition of $d_{h}^{\pi}$.

###  4.4 Other Instance-dependent Regrets

Our variance-aware regret has two key features. Firstly, we do not require any
prior knowledge of ${\mathcal{G}}^{*}$ to achieve variance awareness.
Secondly, the additional conditions imposed on the MDP structure lead to other
instance-dependent regrets. In the following, we also impose Assumption 4.1
for a fair comparison with related work. However, we would like to emphasize
that all of our results are obtained in the presence of heavy-tailed rewards.

######  Assumption 4.1.

We assume uniformly bounded rewards where $0\leq R_{h}(s,a)\leq 1$ for all
$h\in[H]$ and $(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$.

##### Worst-case regret

Under Assumption 4.1, ${\mathcal{V}}^{2}=H^{2}$ according to the law of total
variance (Azar et al., 2013). Consequently, we can infer that
${\mathcal{G}}^{*}\leq H^{2}$, and the regret reduces to the minimax optimal
$\widetilde{\mathcal{O}}(dH\sqrt{HK})$ (He et al., 2022). The authors achieved
this regret by directly setting $\sigma_{\min}=1/H$, without taking into
account the trade-off introduced by $\sigma_{\min}$. Although this was
sufficient for their worst-case scenario, it was not suitable for our goal of
achieving variance awareness. If we also set $\sigma_{\min}=1/H$, the second
term in (4.10) becomes $d\sqrt{K}$, and we cannot determine the dominant term
between $d\sqrt{HK{\mathcal{G}}^{*}}$ and $d\sqrt{K}$. However, once we
balance the trade-off of $\sigma_{\min}$, the second term becomes much
smaller, making $\widetilde{\mathcal{O}}(d\sqrt{H{\mathcal{G}}^{*}K})$ the
dominant term.

##### Range-dependent regret

Let ${\mathcal{S}}_{s,a}$ be the set of immediate successor states after one
transition from state $s$ upon taking action $a$, which is also the support
set of ${\mathbb{P}}(\cdot|s,a)$. Define $\Phi_{\mathrm{succ}}$ as the maximum
value function range when restricted to the immediate successor states:

$\Phi_{\mathrm{succ}}:=\sup_{h\in[H]}\sup_{(s,a)}[\sup_{s^{\prime}\in{\mathcal{S}}_{s,a}}V_{h+1}^{*}(s^{\prime})-\inf_{s^{\prime}\in{\mathcal{S}}_{s,a}}V_{h+1}^{*}(s^{\prime})].$

Since the variance is upper bounded by one-fourth of the square range of a
random variable, we have

$\sup_{h\in[H]}\sup_{(s,a)}[{\mathbb{V}}_{h}V_{h+1}^{*}](s,a)\leq\frac{1}{4}\Phi_{\mathrm{succ}}^{2}~{}\text{and
thus}~{}{\mathcal{G}}^{*}\leq H(\sigma_{R}^{2}+\Phi_{\mathrm{succ}}^{2}).$

Therefore, our regret reduces to
$\widetilde{\mathcal{O}}\left(dH\sqrt{(\sigma_{R}^{2}+\Phi_{\mathrm{succ}}^{2})K}\right)$.
It is worth noting that similar range-dependent regrets have been derived for
tabular MDPs with bounded rewards (Bartlett and Tewari, 2009; Fruit et al.,
2018; Zanette and Brunskill, 2019), but to the best of our knowledge, we
obtain the first such result for linear MDPs with heavy-tailed rewards.

##### First-order regret

The first-order regret that scales proportionally to $V_{1}^{*}$, where
$V_{1}^{*}:=V_{1}^{*}(s_{1})$ is the value of the optimal value policy at the
initial state $s_{1}$, has been studied for tabular MDPs (Jin et al., 2020a)
and linear MDPs (Wagenmaker et al., 2022a).111They assume all episodes start
from the same initial state so that $s_{1,k}\equiv s_{1}$. However, our regret
can be easily extended to the setting where initial states are different, in
which case one should replace $V_{1}^{*}K$ with
$\sum_{k=1}^{K}V_{1}^{*}(s_{1,k})$ in the regret upper bound. However, under
Assumption 4.1, the corresponding instance-dependent quantity $H^{2}V_{1}^{*}$
can be much larger than ${\mathcal{G}}^{*}$. This is because

$\displaystyle{\mathcal{G}}^{*}$
$\displaystyle\leq\sum_{h=1}^{H}\sum_{(s,a)}\widetilde{d}_{h}^{k}(s,a)\cdot[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s,a)$
$\displaystyle\overset{(a)}{\leq}H\sum_{h=1}^{H}\sum_{(s,a)}\widetilde{d}_{h}^{k}(s,a)\cdot[r_{h}+{\mathbb{P}}_{h}V_{h+1}^{*}](s,a)$
$\displaystyle\overset{(b)}{\leq}H\sum_{h=1}^{H}\sum_{(s,a)}\widetilde{d}_{h}^{k}(s,a)\cdot
V_{h}^{*}(s)\overset{(c)}{\leq}H^{2}V_{1}^{*}$

where $(a)$ uses $0\leq R_{h}\leq 1$ and $0\leq V_{h+1}^{*}\leq H-1$ under
Assumption 4.1, $(b)$ uses the optimality condition
$V_{h}^{*}(s)=[r_{h}+{\mathbb{P}}_{h}V_{h+1}^{*}](s,a)$ for any
$(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$, and $(c)$ uses $V_{h+1}^{*}(s)\leq
V_{h}^{*}(s)$ for any $h\in[H]$ and $s\in{\mathcal{S}}$ and
$\sum_{a\in{\mathcal{S}}}\widetilde{d}_{h}^{k}(s_{1},a)=1$ since each episode
starts at a fixed state $s_{1}$. Moreover, even replacing $\mathcal{G}^{*}$
with the coarse upper bound $H^{2}V_{1}^{*}$, our regret bound becomes
$\widetilde{\mathcal{O}}(\sqrt{d^{2}H^{3}V_{1}^{*}K})$, which has a better
dependence on $d$ than $\widetilde{\mathcal{O}}(\sqrt{d^{3}H^{3}V_{1}^{*}K})$
in (Wagenmaker et al., 2022a).

##### Concentrability-dependent regret

Let $R_{\pi^{*}}$ denote the sum of random rewards collected in a trajectory
following the optimal policy $\pi^{*}$. It is straightforward to see that
$\operatorname{{\rm
Var}}(R_{\pi^{*}})=\sum_{h=1}^{H}\sum_{(s,a)}d_{h}^{\pi^{*}}(s,a)\cdot[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s,a)$.
Since
${\mathcal{G}}^{*}\leq\sup_{\pi}\sum_{h=1}^{H}\sum_{(s,a)}d_{h}^{\pi}(s,a)\cdot[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s,a)$,
we can show that ${\mathcal{G}}^{*}\leq C^{\dagger}\cdot\operatorname{{\rm
Var}}(R_{\pi^{*}})$ where $C^{\dagger}$ is a data coverage measure defined as

$C^{\dagger}:=\sup_{\pi}\frac{\sum_{h=1}^{H}\sum_{(s,a)}d_{h}^{\pi}(s,a)\cdot[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s,a)}{\sum_{h=1}^{H}\sum_{(s,a)}d_{h}^{\pi^{*}}(s,a)\cdot[{\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*}](s,a)}.$

Therefore, our regret reduces to
$\widetilde{\mathcal{O}}(d\sqrt{C^{\dagger}\operatorname{{\rm
Var}}(R_{\pi^{*}})HK})$ given $C^{\dagger}<\infty$. The $C^{\dagger}$ is a
counterpart of the generalized concentrability coefficient which quantifies
the effect of the distribution shift in offline RL (Chen and Jiang, 2019; Xie
et al., 2021; Cheng et al., 2022). Specifically, given a data distribution
$\mu=\\{\mu_{h}\\}_{h\in[H]}$, the generalized concentrability coefficient
$\mathfrak{C}_{\text{conc}}(\mu)$ for linear function approximation is defined
as

$\mathfrak{C}_{\text{conc}}(\mu):=\sup_{\mathrm{linear}\
Q}\sup_{\pi}\frac{\sum_{h=1}^{H}\sum_{(s,a)}d_{h}^{\pi}(s,a)\cdot[\mathbb{B}_{h}Q_{h}](s,a)}{\sum_{h=1}^{H}\sum_{(s,a)}\mu_{h}(s,a)\cdot[\mathbb{B}_{h}Q_{h}](s,a)},$

where $Q=\\{Q_{h}\\}_{h\in[H]}$ is any Q-value function that is linear in
features ${\bm{\phi}}$ and
$[\mathbb{B}_{h}Q_{h}](s,a):=[Q_{h}-r_{h}-{\mathbb{P}}_{h}V_{h+1}]^{2}(s,a)$
is the Bellman residual with
$V_{h+1}(\cdot)=\sup_{a\in{\mathcal{A}}}Q_{h+1}(\cdot,a)$ being the
corresponding value function.

###  4.5 Space and Computational Complexities

######  Theorem 4.2 (Space and computational complexity).

Solving a $H$-horizon finite MDP in $K$ episodes, VARA takes
${\mathcal{O}}(d^{3}H^{2}+d|{\mathcal{A}}|HK)$ space and has a running time of
$\widetilde{\mathcal{O}}(d^{4}|{\mathcal{A}}|H^{3}K+HK(d+H^{-3/4}d^{-3/2}K^{3/4}))$.

On one hand, VARA achieves the same space complexity as LSVI-UCB++, but is
slightly worse than the original LSVI-UCB (Jin et al., 2020b) that needs
${\mathcal{O}}(d^{2}H+d|{\mathcal{A}}|HK)$ space. This is because the
technique of monotone value function update requires remembering at most
$\widetilde{\mathcal{O}}(dH)$ latest value functions, incurring a slightly
worse dependence on $d$ and $H$. On the other hand, the computational
complexity of VARA
$\widetilde{\mathcal{O}}(d^{4}|{\mathcal{A}}|H^{3}K+HK(d+H^{-3/4}d^{-3/2}K^{3/4}))$
is slightly worse than LSVI-UCB++’s
$\widetilde{\mathcal{O}}(d^{4}|{\mathcal{A}}|H^{3}K)$ in terms of the
dependence on $K$. This is because the adaptive Huber regression estimator
does not have a closed-form solution, and we assume we use the Nesterov
accelerated method as a solver, which incurs a slightly larger computational
complexity. However, VARA’s computational complexity is better than LSVI-UCB’s
$\widetilde{\mathcal{O}}(d^{2}|{\mathcal{A}}|HK^{2})$ due to the rare-
switching mechanism.

##  5 Related Work

##### Heavy-tailed rewards in online decision making

On one hand, there exists a large body of work that studies heavy-tailed
feedbacks in multi-arm bandits, including deterministic (Vakili et al., 2013)
and non-deterministic settings (Bubeck et al., 2013; Carpentier and Valko,
2014; Lattimore, 2017; Bhatt et al., 2022). To handle heavy-tailed rewards,
robust mean estimation methods such as median of means and truncation have
been applied to linear bandits (Medina and Yang, 2016; Shao et al., 2018; Lu
et al., 2019; Xue et al., 2021), achieving the minimax optimal
$\widetilde{{\mathcal{O}}}(d\sqrt{T})$ regret. On the other hand, there is a
lack of RL algorithms designed to handle heavy-tailed rewards. One exception
is (Zhuang and Sui, 2021), which modifies UCRL2 and Q-Learning by using
truncated rewards and achieves minimax optimal regret in tabular MDPs.
However, none of these methods for linear bandits or MDPs provide variance-
aware regrets, even if variance information is available. Moreover, simple
truncation methods are not optimal in the noiseless setting.

##### Variance-aware regret for linear bandits

A weighted ridge regression-based algorithm proposed by Kirschner and Krause
(2018) achieves the same regret (3.6) by assuming each $\varepsilon_{t}$ is
$\nu_{t}$-sub-Gaussian. More recently, Zhou and Gu (2022) obtained the same
regret assuming each $\varepsilon_{t}$ is uniformly bounded and has finite
conditional variance $\nu_{t}^{2}$. In the case where the information of
conditional variances $\\{\nu_{t}\\}_{t\geq 0}$ is unknown, Zhang et al.
(2021) and Kim et al. (2021) achieved regret bounds that involve sub-optimal
dependence on $d$. All of these works consider light-tailed noises, which are
either sub-Gaussian or uniformly bounded.

##### Robust approach to instance-dependent bounds

Recent research explores the robust mean estimation approach to obtain
instance-dependent regrets, leveraging the observation that robust estimators
can achieve estimation errors that only depend on the noise scale. Such
estimators often have better theoretical guarantees than non-robust ones,
whose estimation errors additionally depend on the range of the problem noise.
For instance, Pananjady and Wainwright (2020) use the median-of-means
technique (Lecué and Lerasle, 2020) to achieve local minimax optimality that
depends on the standard deviations of the optimal value function and random
rewards for synchronous tabular MDPs. In linear bandits, Wagenmaker et al.
(2022a) use Catoni’s estimator (Catoni, 2012) to estimate the mean of
${\bm{v}}^{\top}{\bm{H}}_{T}^{-1}{\bm{\phi}}_{t}y_{t}/\sigma_{t}^{2}$ for a
fixed unit-norm vector ${\bm{v}}$. In contrast, we modify the adaptive Huber
regression to estimate ${\bm{\theta}}^{*}$ directly. This difference makes
their bounds depend on the second moments of $y_{t}$’s, while ours only relies
on their variances. Moreover, all of these works, except ours, still assume
light-tailed rewards.

##### Variance-aware quantity ${\mathcal{G}}^{*}$

In the context of online episodic MDPs, Zanette and Brunskill (2019) first
derived a variance-aware regret bound in the tabular setting with uniformly
bounded rewards. Their model-based algorithm, Euler, achieves a regret that
can be bounded by either $\widetilde{\mathcal{O}}(\sqrt{\mathbb{Q}^{S}AHK})$
or $\widetilde{\mathcal{O}}(\sqrt{{\mathcal{G}}^{2}SAK})$, where
$\mathbb{Q}^{*}=\max_{(s,a,h)}({\mathbb{V}}_{h}R_{h}+{\mathbb{V}}_{h}V_{h+1}^{*})(s,a)$
is the maximum per-round conditional variance and ${\mathcal{G}}$ is a
deterministic upper bound on the maximum attainable reward on a single
trajectory for any policy $\pi$, such that
$\sum_{h=1}^{H}R_{h}(s_{h},\pi(s_{h}))\leq{\mathcal{G}}$. One can show that
our instance-dependent quantity ${\mathcal{G}}^{*}$ is smaller than
$\min\\{H\mathbb{Q}^{*},{\mathcal{G}}^{2}\\}$ therein. Later, Jin et al.
(2020a) adopted a modified analysis of Euler to obtain the regret bound
$\widetilde{\mathcal{O}}(\sqrt{SAH^{3}V_{1}^{*}K})$ with
$V_{1}^{*}=V_{1}^{*}(s_{1})$.222Unlike our setting, they assume all initial
states are the same, denoted as $s_{1}$. Furthermore, the original regret
$\widetilde{\mathcal{O}}(\sqrt{SAH\cdot V_{1}^{*}K})$ by Jin et al. (2020a)
was derived for an MDP where the reward function equals to one
deterministically only at a single $(h,s)$ pair. In this way, they have $0\leq
V_{1}^{*}\leq 1$. To convert it in the considered setting where $0\leq
V_{1}^{*}\leq H$, an additional factor of $H$ should be multiplied to their
regret.  In linear MDPs, there are several recent works on obtaining regret
bounds for model-free algorithms. For example, Wagenmaker et al. (2022a)
proposed an optimistic algorithm with a regret bound that scales as
$\widetilde{{\mathcal{O}}}(\sqrt{d^{3}H^{3}V_{1}^{*}K})$. However, this
algorithm is computationally inefficient. A computationally efficient
alternative suffers from a slightly worse regret
$\widetilde{{\mathcal{O}}}(\sqrt{d^{4}H^{3}V_{1}^{*}K})$. All of these works
utilize the instance-dependent quantity $H^{2}V_{1}^{*}$ (assuming
${\mathcal{H}}=H$). However, as we argued, our proposed quantity
${\mathcal{G}}^{*}$ is smaller than $H^{2}V_{1}^{*}$, which implies that our
algorithm may achieve better performance than these previous works.

##### Other instance-dependent bounds

In the infinite-horizon setting, Pananjady and Wainwright (2020); Khamaru et
al. (2021); Li et al. (2023) provided variance-aware sample complexities for
Q-Learning and its variants in tabular MDPs, given a generative model that
produces independent samples for all state-action pairs in every round.
Variance-aware performance guarantees have also been established for offline
RL optimization (Yin and Wang, 2021), off-policy evaluation (Min et al.,
2021), stochastic approximation (Mou et al., 2020, 2022). Another approach to
instance-dependence bounds focuses on the minimum suboptimality gap, which is
the minimum gap between the best and second-best actions over all states (He
et al., 2021a; Wagenmaker et al., 2022c; Wagenmaker and Jamieson, 2022; Dong
and Ma, 2022). However, due to the differences in the settings, we cannot make
a meaningful comparison between these bounds and ours.

##  6 Conclusion

This paper introduces two new algorithms, AdaOFUL for linear bandits and VARA
for linear MDPs, both of which are modifications of the original adaptive
Huber regression and designed to handle online sequential decision-making.
With only the assumption of bounded reward variances, our algorithms achieve
either state-of-the-art or tighter variance-aware regrets. Additionally, in
linear MDPs, the instance-dependent quantity ${\mathcal{G}}^{*}$ can be
bounded by other instance-dependent quantities when additional structure
assumptions are available. Our modified adaptive Huber regression can be a
useful building block for algorithm design in online problems with heavy-
tailed rewards.

## References

  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In _Advances in Neural Information Processing Systems_ , volume 24, 2011.
  * Arnosti et al. (2016) Nick Arnosti, Marissa Beck, and Paul Milgrom.  Adverse selection and auction design for internet display advertising.  _American Economic Review_ , 106(10):2852–66, 2016.
  * Ayoub et al. (2020) Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang.  Model-based reinforcement learning with value-targeted regression.  In _International Conference on Machine Learning_ , pages 463–474. PMLR, 2020.
  * Azar et al. (2013) Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen.  Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.  _Machine Learning_ , 91(3):325–349, 2013.
  * 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_ , pages 263–272, 2017.
  * Bartlett and Tewari (2009) Peter Bartlett and Ambuj Tewari.  Regal: a regularization based algorithm for reinforcement learning in weakly communicating mdps.  In _Conference on Uncertainty in Artificial Intelligence_ , pages 35–42. AUAI Press, 2009.
  * Bhatt et al. (2022) Sujay Bhatt, Guanhua Fang, Ping Li, and Gennady Samorodnitsky.  Nearly optimal Catoni’s M-estimator for infinite variance.  In _International Conference on Machine Learning_ , pages 1925–1944, 2022.
  * Bradtke and Barto (1996) Steven J Bradtke and Andrew G Barto.  Linear least-squares algorithms for temporal difference learning.  _Machine Learning_ , 22(1):33–57, 1996.
  * Bubeck et al. (2013) Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi.  Bandits with heavy tail.  _IEEE Transactions on Information Theory_ , 59(11):7711–7717, 2013.
  * Bubeck et al. (2015) Sébastien Bubeck et al.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4):231–357, 2015.
  * Carpentier and Valko (2014) Alexandra Carpentier and Michal Valko.  Extreme bandits.  In _Advances in Neural Information Processing Systems_ , 2014.
  * Catoni (2012) Olivier Catoni.  Challenging the empirical mean and empirical variance: A deviation study.  _Annales de l’IHP Probabilités et statistiques_ , 48(4):1148–1185, 2012.
  * Chen and Jiang (2019) Jinglin Chen and Nan Jiang.  Information-theoretic considerations in batch reinforcement learning.  In _International Conference on Machine Learning_ , pages 1042–1051. PMLR, 2019.
  * Cheng et al. (2022) Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal.  Bellman-consistent pessimism for offline reinforcement learning.  In _International Conference on Machine Learning_ , volume 162, pages 3852–3878, 2022.
  * Cont (2001) Rama Cont.  Empirical properties of asset returns: Stylized facts and statistical issues.  _Quantitative Finance_ , 1(2):223, 2001.
  * Dani et al. (2008) Varsha Dani, Thomas P Hayes, and Sham M Kakade.  Stochastic linear optimization under bandit feedback.  2008\.
  * Dann et al. (2019) Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill.  Policy certificates: Towards accountable reinforcement learning.  In _International Conference on Machine Learning_ , pages 1507–1516, 2019.
  * Dong and Ma (2022) Kefan Dong and Tengyu Ma.  Asymptotic instance-optimal algorithms for interactive decision making.  _arXiv preprint arXiv:2206.02326_ , 2022.
  * Freedman (1975) David A Freedman.  On tail probabilities for martingales.  _The Annals of Probability_ , 3(1):100–118, 1975\.
  * Fruit et al. (2018) Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner.  Efficient bias-span-constrained exploration-exploitation in reinforcement learning.  In _International Conference on Machine Learning_ , pages 1578–1586, 2018.
  * Hastie et al. (2009) Trevor Hastie, Robert Tibshirani, and Jerome H Friedman.  _The Elements of Statistical Learning: Data Mining, Inference, and Prediction_.  Springer, 2009.
  * He et al. (2021a) Jiafan He, Dongruo Zhou, and Quanquan Gu.  Logarithmic regret for reinforcement learning with linear function approximation.  In _International Conference on Machine Learning_ , pages 4171–4180. PMLR, 2021a.
  * He et al. (2021b) Jiafan He, Dongruo Zhou, and Quanquan Gu.  Nearly minimax optimal reinforcement learning for discounted MDPs.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 22288–22300, 2021b.
  * He et al. (2022) Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu.  Nearly minimax optimal reinforcement learning for linear markov decision processes.  _arXiv preprint arXiv:2212.06132_ , 2022.
  * Hu et al. (2022) Pihe Hu, Yu Chen, and Longbo Huang.  Nearly minimax optimal reinforcement learning with linear function approximation.  In _International Conference on Machine Learning_ , pages 8971–9019, 2022.
  * Huber (1964) Peter J Huber.  Robust estimation of a location parameter.  _The Annals of Mathematical Statistics_ , pages 73–101, 1964.
  * Hull (2012) John Hull.  _Risk Management and Financial Institutions_.  John Wiley & Sons, 2012.
  * Jin et al. (2018) Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is Q-learning provably efficient?  In _Advances in Neural Information Processing Systems_ , volume 31, 2018.
  * Jin et al. (2020a) Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu.  Reward-free exploration for reinforcement learning.  In _International Conference on Machine Learning_ , pages 4870–4879. PMLR, 2020a.
  * Jin et al. (2020b) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pages 2137–2143, 2020b.
  * Khamaru et al. (2021) Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J Wainwright, and Michael I Jordan.  Is temporal difference learning optimal? An instance-dependent analysis.  _SIAM Journal on Mathematics of Data Science_ , 3(4):1013–1040, 2021.
  * Kim et al. (2021) Yeoneung Kim, Insoon Yang, and Kwang-Sung Jun.  Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps.  _arXiv preprint arXiv:2111.03289_ , 2021.
  * Kirschner and Krause (2018) Johannes Kirschner and Andreas Krause.  Information directed sampling and bandits with heteroscedastic noise.  In _Conference on Learning Theory_ , pages 358–384, 2018.
  * Lattimore (2017) Tor Lattimore.  A scale free algorithm for stochastic bandits with bounded kurtosis.  In _Advances in Neural Information Processing Systems_ , volume 30, 2017.
  * Lecué and Lerasle (2020) Guillaume Lecué and Matthieu Lerasle.  Robust machine learning by median-of-means: Theory and practice.  _The Annals of Statistics_ , 48(2):906–931, 2020\.
  * Li et al. (2021) Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejie Chi.  Is Q-learning minimax optimal? A tight sample complexity analysis.  _arXiv preprint arXiv:2102.06548_ , 2021.
  * Li et al. (2016) Jiwei Li, Will Monroe, Alan Ritter, Dan Jurafsky, Michel Galley, and Jianfeng Gao.  Deep reinforcement learning for dialogue generation.  In _Conference on Empirical Methods in Natural Language Processing_ , pages 1192–1202, 2016.
  * Li et al. (2023) Xiang Li, Wenhao Yang, Jiadong Liang, Zhihua Zhang, and Michael I Jordan.  A statistical analysis of Polyak-Ruppert averaged q-learning.  In _International Conference on Artificial Intelligence and Statistics_ , 2023.
  * Lillicrap et al. (2015) Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Lu et al. (2019) Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang.  Optimal algorithms for Lipschitz bandits with heavy-tailed rewards.  In _International Conference on Machine Learning_ , pages 4154–4163, 2019.
  * Medina and Yang (2016) Andres Munoz Medina and Scott Yang.  No-regret algorithms for heavy-tailed linear bandits.  In _International Conference on Machine Learning_ , pages 1642–1650, 2016.
  * Melo and Ribeiro (2007) Francisco S Melo and M Isabel Ribeiro.  Q-learning with linear function approximation.  In _International Conference on Computational Learning Theory_ , pages 308–322, 2007.
  * Min et al. (2021) Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu.  Variance-aware off-policy evaluation with linear function approximation.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 7598–7610, 2021.
  * Mou et al. (2020) Wenlong Mou, Chris Junchi Li, Martin J Wainwright, Peter L Bartlett, and Michael I Jordan.  On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration.  In _Conference on Learning Theory_ , pages 2947–2997, 2020.
  * Mou et al. (2022) Wenlong Mou, Koulik Khamaru, Martin J Wainwright, Peter L Bartlett, and Michael I Jordan.  Optimal variance-reduced stochastic approximation in banach spaces.  _arXiv preprint arXiv:2201.08518_ , 2022.
  * Pananjady and Wainwright (2020) Ashwin Pananjady and Martin J Wainwright.  Instance-dependent $\ell_{\infty}$ bounds for policy evaluation in tabular reinforcement learning.  _IEEE Transactions on Information Theory_ , 67(1):566–585, 2020.
  * Posekany et al. (2011) Alexandra Posekany, Klaus Felsenstein, and Peter Sykacek.  Biological assessment of robust noise models in microarray data analysis.  _Bioinformatics_ , 27(6):807–814, 2011.
  * Shao et al. (2018) Han Shao, Xiaotian Yu, Irwin King, and Michael R Lyu.  Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Sidford et al. (2018) Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye.  Near-optimal time and sample complexities for solving Markov decision processes with a generative model.  In _Advances in Neural Information Processing Systems_ , volume 31, pages 5192–5202, 2018.
  * Silver et al. (2016) David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of Go with deep neural networks and tree search.  _Nature_ , 529(7587):484–489, 2016.
  * Sun (2021) Qiang Sun.  Do we need to estimate the variance in robust mean estimation?  _arXiv preprint arXiv:2107.00118_ , 2021.
  * Sun et al. (2020) Qiang Sun, Wen-Xin Zhou, and Jianqing Fan.  Adaptive Huber regression.  _Journal of the American Statistical Association_ , 115(529):254–265, 2020.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement Learning: An Introduction_.  MIT Press, 2018.
  * Tossou et al. (2019) Aristide Tossou, Debabrota Basu, and Christos Dimitrakakis.  Near-optimal optimistic reinforcement learning using empirical bernstein inequalities.  _arXiv preprint arXiv:1905.12425_ , 2019.
  * Vakili et al. (2013) Sattar Vakili, Keqin Liu, and Qing Zhao.  Deterministic sequencing of exploration and exploitation for multi-armed bandit problems.  _IEEE Journal of Selected Topics in Signal Processing_ , 7(5):759–767, 2013.
  * Wagenmaker and Jamieson (2022) Andrew Wagenmaker and Kevin Jamieson.  Instance-dependent near-optimal policy identification in linear MDPs via online experiment design.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Wagenmaker et al. (2022a) Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson.  First-order regret in reinforcement learning with linear function approximation: A robust estimation approach.  In _International Conference on Machine Learning_ , pages 22384–22429. PMLR, 2022a.
  * Wagenmaker et al. (2022b) Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson.  Reward-free RL is no harder than reward-aware RL in linear Markov decision processes.  In _International Conference on Machine Learning_ , pages 22430–22456, 2022b.
  * Wagenmaker et al. (2022c) Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson.  Beyond no regret: Instance-dependent pac reinforcement learning.  In _Conference on Learning Theory_ , pages 358–418, 2022c.
  * Xie et al. (2021) Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal.  Bellman-consistent pessimism for offline reinforcement learning.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 6683–6694, 2021.
  * Xue et al. (2021) Bo Xue, Guanghui Wang, Yimu Wang, and Lijun Zhang.  Nearly optimal regret for stochastic linear bandits with heavy-tailed payoffs.  In _International Conference on International Joint Conferences on Artificial Intelligence_ , pages 2936–2942, 2021.
  * Yang and Wang (2019) Lin Yang and Mengdi Wang.  Sample-optimal parametric Q-learning using linearly additive features.  In _International Conference on Machine Learning_ , pages 6995–7004, 2019.
  * Yang and Wang (2020) Lin Yang and Mengdi Wang.  Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound.  In _International Conference on Machine Learning_ , pages 10746–10756. PMLR, 2020.
  * Yin and Wang (2021) Ming Yin and Yu-Xiang Wang.  Towards instance-optimal offline reinforcement learning with pessimism.  In _Advances in Neural Information Processing Systems_ , pages 4065–4078, 2021.
  * Zanette and Brunskill (2019) Andrea Zanette and Emma Brunskill.  Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.  In _International Conference on Machine Learning_ , pages 7304–7312. PMLR, 2019.
  * Zanette et al. (2020) Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent bellman error.  In _International Conference on Machine Learning_ , pages 10978–10989, 2020.
  * Zhang et al. (2020) Zihan Zhang, Yuan Zhou, and Xiangyang Ji.  Almost optimal model-free reinforcement learning via reference-advantage decomposition.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 15198–15207, 2020.
  * Zhang et al. (2021) Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du.  Improved variance-aware confidence sets for linear bandits and linear mixture MDP.  In _Advances in Neural Information Processing Systems_ , pages 4342–4355, 2021.
  * Zhou and Gu (2022) Dongruo Zhou and Quanquan Gu.  Computationally efficient horizon-free reinforcement learning for linear mixture mdps.  _arXiv preprint arXiv:2205.11507_ , 2022.
  * Zhou et al. (2021) Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari.  Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.  In _Conference on Learning Theory_ , pages 4532–4576, 2021.
  * Zhuang and Sui (2021) Vincent Zhuang and Yanan Sui.  No-regret reinforcement learning with heavy-tailed rewards.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3385–3393, 2021.

Appendix

##### Overview

In Appendix A, we explain the rationale behind the variance estimator used by
VARA. Appendix B contains proofs for Theorem 3.1 and 3.2 specifically for
linear bandits. The theoretical analysis for VARA is presented in Appendix C,
where we offer a proof sketch for Theorem 4.1, while all related technical
lemmas are deferred to Appendices E and F. We also highlight the differences
between our analysis and previous work. In Appendix D, we provide a proof for
Theorem 4.2 that analyzes the space and computational complexity of VARA.

##  Appendix A Variance Estimation for Value Functions

In order to achieve worst-case optimality, He et al. [2022] proposes two
important techniques we adopt in Algorithm 2.

The first is the monotonicity of value functions. Specifically, we aim to
enforce a decrease in $k$ for the actual optimistic value function
$\overline{Q}_{h}^{k}(\cdot,\cdot)$ and an increase in $k$ for the actual
pessimistic value function $\underline{Q}_{h}^{k}(\cdot,\cdot)$. This concept
is explained in detail below. In linear MDPs, we have
$[{\mathbb{P}}_{h}V_{h+1}](s,a)=\langle{\bm{\phi}}(s,a),{\bm{\mu}}_{h}^{*}{\bm{V}}_{h+1}\rangle$
for any value function $V=\\{V_{h}\\}_{h\in[H]}$ and
$[{\mathbb{P}}_{h}R_{h}](s,a)=\langle{\bm{\phi}}(s,a),{\bm{\theta}}_{h}^{*}\rangle$
for all $h\in[H]$. One crucial aspect of typical analysis (including ours) is
demonstrating the high probability of the following event outlined in Appendix
C.1. Specifically, for all $h\in[H]$ and $k\in[K]$, we need to establish that
the following equations hold simultaneously with high pribability:

$\displaystyle\begin{split}\|{\bm{\theta}}_{h,k}-{\bm{\theta}}_{h}^{*}\|_{{\bm{H}}_{h,k}}\leq\beta_{R}=\widetilde{\mathcal{O}}(\sqrt{d}),\\\
\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\overline{{\bm{V}}}_{h+1}^{k}\|_{{\bm{H}}_{h,k-1}}\leq\beta_{V}=\widetilde{\mathcal{O}}(\sqrt{d}),\\\
\|({\bm{\mu}}_{h,k-1}-{\bm{\mu}}_{h}^{*})\underline{{\bm{V}}}_{h+1}^{k}\|_{{\bm{H}}_{h,k-1}}\leq\beta_{V}=\widetilde{\mathcal{O}}(\sqrt{d}).\end{split}$
(A.1)

Conditional on the event that all inequalities in (A.1) hold, we can easily
verify that

$\displaystyle|\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k-1}\rangle-[{\mathbb{P}}_{h}R_{h}](\cdot,\cdot)|\leq\beta_{R}\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}},$
$\displaystyle|\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\mu}}_{h,k-1}{\bm{V}}_{h+1}\rangle-[{\mathbb{P}}_{h}V_{h+1}](\cdot,\cdot)|\leq\beta_{V}\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}}$

for both
${\bm{V}}_{h+1}\in\\{\underline{{\bm{V}}}_{h+1}^{k},\overline{{\bm{V}}}_{h+1}^{k}\\}$.
Therefore, we define the temporary optimistic value function by

$\widehat{Q}_{h}^{k}(\cdot,\cdot)=\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k-1}+{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k}\rangle+\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}},$

and the temporary pessimistic value function by

$\widecheck{Q}_{h}^{k}(\cdot,\cdot)=\langle{\bm{\phi}}(\cdot,\cdot),{\bm{\theta}}_{h,k-1}+{\bm{\mu}}_{h,k-1}\overline{{\bm{V}}}_{h+1}^{k}\rangle-\beta\|{\bm{\phi}}(\cdot,\cdot)\|_{{\bm{H}}_{h,k-1}^{-1}}$

where $\beta:=\beta_{R}+\beta_{V}=\widetilde{\mathcal{O}}(\sqrt{d})$. The
actual optimistic value function $\overline{Q}_{h}^{k}(\cdot,\cdot)$ is the
minimum function of history temporary optimistic value functions
$\widehat{Q}_{h}^{k}(\cdot,\cdot)$, and the actual pessimistic value function
$\underline{Q}_{h}^{k}(\cdot,\cdot)$ is the maximum function of history
temporary pessimistic value functions $\widecheck{Q}_{h}^{k}(\cdot,\cdot)$
(Line 7 in Algorithm 2). In this way, $\overline{Q}_{h}^{k}(\cdot,\cdot)$ is
always non-increasing in $k$ and $\underline{Q}_{h}^{k}(\cdot,\cdot)$ is
always non-decreasing in $k$.

The second is the rare-switching value function update, which updates the
value function only when the determinant of the covariance matrix
significantly exceeds the previous value (Line 6 in Algorithm 2). This
approach allows the complexity, as measured by the metric entropy, of the
function class to which $\overline{V}_{h}^{k}(\cdot)$ or
$\underline{V}_{h}^{k}(\cdot)$ belongs to be independent of $K$. Notably, the
metric entropy is linearly dependent on $\widetilde{\mathcal{O}}(dH)$.
Moreover, on the event (A.1), we can establish optimism and pessimism in Lemma
C.4, i.e., for all $k\in[K]$ and $h\in[H]$,

$\underline{V}_{h+1}^{k}(\cdot)\leq
V_{h+1}^{*}(\cdot)\leq\overline{V}_{h+1}^{k}(\cdot).$ (A.2)

Directly estimating the variance of the optimistic value function
$\overline{V}_{h+1}^{k}(\cdot)$ will encounter the dependence issue, which is
discussed in [Jin et al., 2020b] and will introduce an additional $\sqrt{d}$
factor in the regret due to the covering-based decoupling argument. To
eliminate this factor, after noting the inequality

$[{\mathbb{V}}_{h}\overline{V}_{h+1}^{k}](\cdot,\cdot)\leq
2[{\mathbb{V}}_{h}V_{h+1}^{*}](\cdot,\cdot)+2[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})](\cdot,\cdot),$

Hu et al. [2022] decompose the optimistic value function
$\overline{V}_{h+1}^{k}(\cdot)$ into the optimal value function
$V_{h+1}^{*}(\cdot)$ and the sub-optimality gap
$[\overline{V}_{h+1}^{k}-V_{h+1}^{*}](\cdot)$ and estimate their variances
$[{\mathbb{V}}_{h}V_{h+1}^{*}](\cdot,\cdot)$ and
$[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})](\cdot,\cdot)$
separately. The key insight is that: (i) as $V_{h+1}^{*}$ is deterministic,
there is no additional $\sqrt{d}$ dependence in estimating
$[{\mathbb{V}}_{h}V_{h+1}^{*}](\cdot,\cdot)$, and (ii) as
$\overline{V}_{h+1}^{k}$ gradually converges to $V_{h+1}^{*}$, though a
uniform argument is still used, the incurred $\sqrt{d}$ factor in the
estimation of $[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})]$ has
ignorable effects on the final regret. We now describe the way we estimate
these two variances.

  * •

For $[{\mathbb{V}}_{h}V_{h+1}^{*}](\cdot,\cdot)$, since $V_{h+1}^{*}$ is
unknown, a natural choice is to estimate it by the optimistic value function
$\overline{V}_{h+1}^{k}$. Hence, we estimate
$[{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})$ via

$[\widehat{\mathbb{V}}_{h,k}\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k}):=[\widehat{{\mathbb{P}}}_{h,k}(\overline{V}_{h+1}^{k})^{2}](s_{h,k},a_{h,k})_{[0,{\mathcal{H}}^{2}]}-\left[[\widehat{{\mathbb{P}}}_{h,k}\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k})_{[0,{\mathcal{H}}^{2}]}\right]^{2}.$
(A.3)

To measure estimation accuracy, we introduce an error term $U_{h,k}$ to
guarantee that with high probability,
$\left|[\widehat{\mathbb{V}}_{h,k}\overline{V}_{h+1}^{k}](s_{h,k},a_{h,k})-[{\mathbb{V}}_{h}V_{h+1}^{*}](s_{h,k},a_{h,k})\right|\leq
U_{h,k}$ holds uniformly over all $h,k$ where

$U_{h,k}=\min\left\\{{\mathcal{V}}^{2},11{\mathcal{H}}\beta_{0}\cdot\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+4{\mathcal{H}}\cdot\widehat{\mathbb{P}}_{h,k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})(s_{h,k},a_{h,k})\right\\}$
(4.9)

and
$\beta_{0}=\widetilde{\mathcal{O}}\left(\frac{{\mathcal{H}}}{\sigma_{\min}}\sqrt{d^{3}H}\right)$
is an exploration radius.

  * •

For $[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{k}-V_{h+1}^{*})](\cdot,\cdot)$, in
order to meet the measurability condition of a concentration inequality (Lemma
F.3), we require

$\sigma_{h,k}^{2}\geq d^{3}H\cdot\sup_{k\leq j\leq
K}[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{j}-V_{h+1}^{*})](s_{h,k},a_{h,k}).$
(A.4)

Note that $\sigma_{h,k}$ is ${\mathcal{F}}_{h,k}$-measurable while
$\overline{V}_{h+1}^{k}(\cdot)$ is ${\mathcal{F}}_{H,k-1}$-measurable. The
condition (A.4) essentially requires a ${\mathcal{F}}_{h,k}$-measurable upper
bound for
$[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{j}-V_{h+1}^{*})](s_{h,k},a_{h,k})$ even
if $j\geq k$. Fortunately, we have for any $k\leq j\leq K$,

$\displaystyle[{\mathbb{V}}_{h}(\overline{V}_{h+1}^{j}-V_{h+1}^{*})](s_{h,k},a_{h,k})$
$\displaystyle\leq[{\mathbb{P}}_{h}(\overline{V}_{h+1}^{j}-V_{h+1}^{*})^{2}](s_{h,k},a_{h,k})$
$\displaystyle\overset{(a)}{\leq}{\mathcal{H}}[{\mathbb{P}}_{h}(\overline{V}_{h+1}^{j}-V_{h+1}^{*})](s_{h,k},a_{h,k})$
$\displaystyle\overset{(b)}{\leq}{\mathcal{H}}[{\mathbb{P}}_{h}(\overline{V}_{h+1}^{j}-\underline{V}_{h+1}^{j})](s_{h,k},a_{h,k})$
$\displaystyle\overset{(c)}{\leq}{\mathcal{H}}[{\mathbb{P}}_{h}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})](s_{h,k},a_{h,k})$
(A.5)

where $(a)$ uses
$|\overline{V}_{h+1}^{j}-V_{h+1}^{*}|(\cdot)\leq{\mathcal{H}}$ and the
optimism of $\overline{V}_{h+1}^{j}(\cdot)$, $(b)$ follows from the pessimism
in (A.2), and $(c)$ uses the monotonicity of value functions. The RHS of (A.5)
is ${\mathcal{F}}_{h,k}$-measurable but intractable due to the population
expectation ${\mathbb{P}}_{h}(\cdot)$. By replacing ${\mathbb{P}}_{h}(\cdot)$
with the tractable $\widehat{\mathbb{P}}_{h,k}(\cdot)$, we introduce $E_{h,k}$
to overestimate the RHS of (A.5) where

$E_{h,k}=\min\left\\{{\mathcal{H}}^{2},2{\mathcal{H}}\beta_{0}\cdot\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}}+{\mathcal{H}}\cdot\left[\widehat{\mathbb{P}}_{h,k}(\overline{V}_{h+1}^{k}-\underline{V}_{h+1}^{k})\right](s_{h,k},a_{h,k})\right\\}.$
(4.7)

Hence, (A.4) is guaranteed by $\sigma_{h,k}^{2}\geq d^{3}H\cdot E_{h,k}$. The
extra $d^{3}H$ factor is introduced to offset the error caused by the covering
number argument.

##  Appendix B Proof for Section 3.2

###  B.1 Proof of Theorem 3.1

Let
$z_{t}({\bm{\theta}})=\frac{y_{t}-\langle{\bm{\phi}}_{t},{\bm{\theta}}\rangle}{\sigma_{t}}$
for simplicity. Notice that the gradient is given by

$\nabla
L_{T}({\bm{\theta}}):=\lambda{\bm{\theta}}-\sum_{t=1}^{T}\frac{\tau_{t}z_{t}({\bm{\theta}})}{\sqrt{\tau_{t}^{2}+z_{t}({\bm{\theta}})^{2}}}\frac{{\bm{\phi}}_{t}}{\sigma_{t}}.$

Our estimator is the solution of (3.3). By Proposition 1.3 in [Bubeck et al.,
2015], the first-order stationary condition of the constrained convex
optimization (3.3) implies that $\langle\nabla
L_{T}({\bm{\theta}}_{T}),{\bm{\theta}}_{T}-{\bm{\theta}}\rangle\leq 0$ for all
${\bm{\theta}}\in\mathrm{Ball}_{d}(B)$. More specifically, due to
$\|{\bm{\theta}}^{*}\|\leq B$, we have

$\langle\nabla
L_{T}({\bm{\theta}}_{T}),{\bm{\theta}}_{T}-{\bm{\theta}}^{*}\rangle\leq 0.$
(B.1)

By the convexity of $L_{T}(\cdot)$, it follows that

$\displaystyle 0\leq\langle{\bm{\theta}}_{T}-{\bm{\theta}}^{*},\nabla
L_{T}({\bm{\theta}}_{T})-\nabla L_{T}({\bm{\theta}}^{*})\rangle.$ (B.2)

In Lemma B.1, we show that with high probability and up to a constant factor,
$\nabla^{2}L_{T}({\bm{\theta}})$ is a good approximation of ${\bm{H}}_{T}$
uniformly for all $T\geq 1$ and $\|{\bm{\theta}}\|\leq B$. Its proof is
deferred to Section B.3. In the following, we will frequently mention a
quantity denoted by $\kappa$.

$\kappa:=d\log\left(1+\frac{TL^{2}}{d\lambda\sigma_{\min}^{2}}\right).$ (B.3)

######  Lemma B.1.

Assume ${\mathbb{E}}[z_{t}^{2}({\bm{\theta}}^{*})|{\mathcal{F}}_{t-1}]\leq
b^{2}$ for all $t\geq 1$. If we set

$\tau_{0}\sqrt{\log\frac{2T^{2}}{\delta}}\geq\max\\{\sqrt{2\kappa}b,2\sqrt{d}\\},$

with probability at least $1-2\delta$, we have that for all $T\geq 0$,

$\frac{1}{4}{\bm{H}}_{T}\preceq\nabla^{2}L_{T}({\bm{\theta}})\preceq{\bm{H}}_{T}\quad\text{for
any}\quad\|{\bm{\theta}}\|\leq B.$

By the mean value theorem for vector-valued functions, we have

$\nabla L_{T}(\widehat{{\bm{\theta}}}_{T})-\nabla
L_{T}({\bm{\theta}}^{*})=\int_{0}^{1}\nabla^{2}L_{T}((1-\eta){\bm{\theta}}^{*}+\eta\widehat{{\bm{\theta}}}_{T})\mathrm{d}\eta\cdot(\widehat{{\bm{\theta}}}_{T}-{\bm{\theta}}^{*}).$

Using Lemma B.1 and
$\|(1-\eta){\bm{\theta}}^{*}+\eta{{\bm{\theta}}}_{T})\|\leq B$ for all
$\eta\in[0,1]$, we have

$\frac{1}{4}\|{{\bm{\theta}}}_{T}-{\bm{\theta}}^{*}\|_{{\bm{H}}_{T}}^{2}\leq\langle{{\bm{\theta}}}_{T}-{\bm{\theta}}^{*},\nabla
L_{T}({{\bm{\theta}}}_{T})-\nabla L_{T}({\bm{\theta}}^{*})\rangle.$ (B.4)

By (B.4), (B.2) and (B.1), we have

$\displaystyle\frac{1}{4}\|{{\bm{\theta}}}_{T}-{\bm{\theta}}^{*}\|_{{\bm{H}}_{T}}^{2}$
$\displaystyle\leq\langle{\bm{\theta}}_{T}-{\bm{\theta}}^{*},\nabla
L_{T}({\bm{\theta}}_{T})-\nabla L_{T}({\bm{\theta}}^{*})\rangle$
$\displaystyle\leq\langle{\bm{\theta}}_{T}-{\bm{\theta}}^{*},-\nabla
L_{T}({\bm{\theta}}^{*})\rangle$
$\displaystyle\leq\|{{\bm{\theta}}}_{T}-{\bm{\theta}}^{*}\|_{{\bm{H}}_{T}}\|\nabla
L_{T}({\bm{\theta}}^{*})\|_{{\bm{H}}_{T}^{-1}}$

which implies that

$\|{{\bm{\theta}}}_{T}-{\bm{\theta}}^{*}\|_{{\bm{H}}_{T}}\leq 4\|\nabla
L_{T}({\bm{\theta}}^{*})\|_{{\bm{H}}_{T}^{-1}}.$ (B.5)

In the following, we are going to provide a high-probability bound for
$\|\nabla L_{\tau}({\bm{\theta}}^{*})\|_{{\bm{H}}_{T}^{-1}}$. In particular,
we have the following lemma whose proof is provided in Section B.4.

######  Lemma B.2.

Assume ${\mathbb{E}}[z_{t}^{2}({\bm{\theta}}^{*})|{\mathcal{F}}_{t-1}]\leq
b^{2}$ for all $t\geq 1$. With probability at least $1-\delta$, for all $T\geq
1$, it follows that

$\|\nabla L_{T}({\bm{\theta}}^{*})\|_{{\bm{H}}_{T}^{-1}}\leq
8\left[\frac{\kappa
b^{2}}{\tau_{0}}+b\sqrt{\kappa\log\frac{2T^{2}}{\delta}}+\tau_{0}\log\frac{2T^{2}}{\delta}\right]+\sqrt{\lambda}B$

where $\kappa$ is defined in (B.3).

Combing (B.5), Lemma B.1 and Lemma B.2, we know that if
$\tau_{0}\sqrt{\log\frac{2T^{2}}{\delta}}=\max\\{\sqrt{2\kappa}b,2\sqrt{d}\\}$,
with probability at least $1-2\delta$, we have that
$\|{{\bm{\theta}}}_{t}-{\bm{\theta}}^{*}\|_{{\bm{H}}_{t}}<\beta_{t}$ for all
$1\leq t\leq T$ where

$\beta_{t}=32\left[b\sqrt{\frac{\kappa}{2}\log\frac{2t^{2}}{\delta}}+b\sqrt{\kappa\log\frac{2t^{2}}{\delta}}+(\sqrt{2\kappa}b+2\sqrt{d})\sqrt{\log\frac{2t^{2}}{\delta}}\right]+4\sqrt{\lambda}B.$

It implies that ${\bm{\theta}}^{*}$ indeed locals in all constructed
confidence regimes, i.e., for all $1\leq t\leq T$,

${\bm{\theta}}^{*}\in{\mathcal{C}}_{t}=\left\\{{\bm{\theta}}\in\mathrm{Ball}_{d}(B):\|{\bm{\theta}}_{t}-{\bm{\theta}}\|_{{\bm{H}}_{t}}\leq\beta_{t}\right\\}.$

Notice that by the choice of $\beta_{0}$ and ${\bm{H}}_{0}$, we still have
${\bm{\theta}}^{*}\in{\mathcal{C}}_{0}$. Finally, $b=1$ in our case completes
the proof.

###  B.2 Proof of Theorem 3.2

Now, we turn to the regret (2.1). Recall that at iteration $t$, we set

$({\bm{\phi}}_{t},*)=\mathop{\rm
argmax}_{{\bm{\phi}}\in{\mathcal{D}}_{t},{{\bm{\theta}}}\in{\mathcal{C}}_{t-1}}\langle{\bm{\phi}},{{\bm{\theta}}}\rangle.$

Due to $\sup_{{\bm{\phi}}\in\cup_{t\geq
0}{\mathcal{D}}_{t}}|\langle{\bm{\phi}},{\bm{\theta}}^{*}\rangle|\leq R:=LB$,
it follows that

$\displaystyle\mathrm{Reg}(T)$
$\displaystyle:=\sum_{t=1}^{T}\left[\sup_{{\bm{\phi}}\in{\mathcal{D}}_{t}}\langle{\bm{\phi}},{\bm{\theta}}^{*}\rangle-\langle{\bm{\phi}}_{t},{\bm{\theta}}^{*}\rangle\right]$
$\displaystyle\leq\sum_{t=1}^{T}\left[\sup_{{\bm{\phi}}\in{\mathcal{D}}_{t},{{\bm{\theta}}}\in{\mathcal{C}}_{t-1}}\langle{\bm{\phi}},{\bm{\theta}}\rangle-\langle{\bm{\phi}}_{t},{\bm{\theta}}^{*}\rangle\right]$
$\displaystyle=\sum_{t=1}^{T}\left[\sup_{{{\bm{\theta}}}\in{\mathcal{C}}_{t-1}}\langle{\bm{\phi}}_{t},{\bm{\theta}}\rangle-\langle{\bm{\phi}}_{t},{\bm{\theta}}^{*}\rangle\right]$
$\displaystyle\leq\sum_{t=1}^{T}\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}({{\bm{\theta}}}_{t-1})}\cdot\sup_{{{\bm{\theta}}}\in{\mathcal{C}}_{t-1}}\|{{\bm{\theta}}}-{{\bm{\theta}}}^{*}\|_{{\bm{H}}_{t-1}}$

Notice that with probability $1-\delta$,
${{\bm{\theta}}}^{*}\in{\mathcal{C}}_{t}$ for all $t\geq 1$, i.e.,
$\|{{\bm{\theta}}}_{t}-{{\bm{\theta}}}^{*}\|_{{\bm{H}}_{t}}\leq\beta_{t}$.
Hence,

$\sup_{{{\bm{\theta}}}\in{\mathcal{C}}_{t}}\|{{\bm{\theta}}}-{{\bm{\theta}}}^{*}\|_{{\bm{H}}_{t}}\leq\sup_{{{\bm{\theta}}}\in{\mathcal{C}}_{t}}\|{{\bm{\theta}}}-{{\bm{\theta}}}_{t}\|_{{\bm{H}}_{t}}+\|{{\bm{\theta}}}_{t}-{{\bm{\theta}}}^{*}\|_{{\bm{H}}_{t}}\leq
2\beta_{t}.$

Notice that $\beta_{t}$ is increasing in $t$ and
$w_{t}=\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{t-1}^{-1}}$.
Therefore,

$\displaystyle\mathrm{Reg}(T)$ $\displaystyle\leq
2\beta_{T}\sum_{t=1}^{T}\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}}=2\beta_{T}\sum_{t=1}^{T}\sigma_{t}w_{t}=2\beta_{T}\sum_{t=1}^{T}\sigma_{t}\min\\{1,w_{t}\\}.$
(B.6)

The last equality uses $w_{t}\leq 1$ (which is due to
$\sigma_{t}\geq\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}}/c_{0}$ and $c_{0}\leq
1$). Notice that
$\|{\bm{\phi}}_{t}\|/\sigma_{t}\leq\|{\bm{\phi}}_{t}\|/\sigma_{\min}\leq
L/\sigma_{\min}$. Then by Lemma F.5,

$\sum_{t=1}^{T}\min\left\\{1,\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{t-1}^{-1}}^{2}\right\\}=\sum_{t=1}^{T}\min\left\\{1,w_{t}^{2}\right\\}\leq
2d\log\left(1+\frac{TL^{2}}{d\lambda\sigma_{\min}^{2}}\right)=2\kappa.$ (B.7)

Recall that

$\sigma_{t}=\max\left\\{\nu_{t},\sigma_{\min},\frac{\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}}}{c_{0}},\frac{\sqrt{LB}\|{\bm{\phi}}_{t}\|^{\frac{1}{2}}_{{\bm{H}}_{t-1}^{-1}}}{c_{1}^{\frac{1}{4}}d^{\frac{1}{4}}}\right\\}.$

According to what value $\sigma_{t}$ takes, we decompose $[T]$ into three sets
$[T]\subseteq\cup_{i=1}^{3}{\mathcal{J}}_{i}$ where

$\displaystyle{\mathcal{J}}_{1}=\\{t\in[T]:\sigma_{t}\in\\{\nu_{t},\sigma_{\min}\\}\\},$
$\displaystyle{\mathcal{J}}_{2}=\left\\{t\in[T]:\sigma_{t}=\frac{\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}}}{c_{0}}\right\\},$
$\displaystyle{\mathcal{J}}_{3}=\left\\{t\in[T]:\sigma_{t}=\sqrt{LB}\frac{\|{\bm{\phi}}_{t}\|^{\frac{1}{2}}_{{\bm{H}}_{t-1}^{-1}}}{c_{1}^{\frac{1}{4}}d^{\frac{1}{4}}}\right\\}.$

First, it follows that

$\displaystyle\sum_{t\in{\mathcal{J}}_{1}}\sigma_{t}\min\left\\{1,w_{t}\right\\}$
$\displaystyle\leq\sum_{t\in{\mathcal{J}}_{1}}\max\\{\nu_{t},\sigma_{\min}\\}\min\left\\{1,w_{t}\right\\}$
$\displaystyle\leq\sum_{t\in[T]}\max\\{\nu_{t},\sigma_{\min}\\}\min\left\\{1,w_{t}\right\\}$
$\displaystyle\overset{(a)}{\leq}\sqrt{\sum_{t\in[T]}(\nu_{t}^{2}+\sigma_{\min}^{2})}\sqrt{\sum_{t\in[T]}\min\left\\{1,w_{t}^{2}\right\\}}$
$\displaystyle\overset{(b)}{\leq}\sqrt{2\kappa}\cdot\sqrt{\sum_{t\in[T]}\nu_{t}^{2}+1}.$
(B.8)

Here $(a)$ holds due to Cauchy-Schwarz inequality and $(b)$ uses (B.7) and
$\sigma_{\min}=\frac{1}{\sqrt{T}}$.

Second, for any $t\in{\mathcal{J}}_{2}$, we have
$w_{t}=\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{t-1}^{-1}}=c_{0}\leq
1$. Therefore,

$\displaystyle\sum_{t\in{\mathcal{J}}_{2}}\sigma_{t}\min\left\\{1,w_{t}\right\\}$
$\displaystyle=\sum_{t\in{\mathcal{J}}_{2}}\sigma_{t}w_{t}=\frac{1}{c_{0}}\sum_{t\in{\mathcal{J}}_{2}}\sigma_{t}w_{t}^{2}\leq\frac{\sup_{t\in{\mathcal{J}}_{2}}\sigma_{t}}{c_{0}}\sum_{t\in{\mathcal{J}}_{2}}w_{t}^{2}$
$\displaystyle\leq\frac{\sup_{t\in[T]}\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}}}{c_{0}^{2}}\cdot\sum_{t\in{\mathcal{J}}_{2}}\min\\{1,w_{t}^{2}\\}$
$\displaystyle\leq\frac{\sup_{t\in[T]}\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}}}{c_{0}^{2}}\cdot\sum_{t\in[T]}\min\\{1,w_{t}^{2}\\}\leq\frac{2L\kappa}{c_{0}^{2}\sqrt{\lambda}}$
(B.9)

where the last inequality uses
$\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}}\leq\frac{1}{\sqrt{\lambda}}\|{\bm{\phi}}_{t}\|\leq\frac{L}{\sqrt{\lambda}}$
for all $t\geq 1$ and (B.7).

Finally, for any $t\in{\mathcal{J}}_{3}$, we have
$L^{2}B^{2}w_{t}^{2}=c_{1}d\sigma_{t}^{2}$ due to
$w_{t}^{2}=\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{t-1}^{-1}}^{2}$.
It implies
$\sigma_{t}=LBw_{t}/\sqrt{c_{1}d}=LB\min\\{1,w_{t}\\}/\sqrt{c_{1}d}$ with the
fact that $w_{t}\leq 1$. Therefore,

$\displaystyle\sum_{t\in{\mathcal{J}}_{3}}\sigma_{t}\min\left\\{1,w_{t}\right\\}=\frac{LB}{\sqrt{c_{1}d}}\cdot\sum_{t\in{\mathcal{J}}_{3}}\min\left\\{1,w_{t}^{2}\right\\}\leq\frac{LB}{\sqrt{c_{1}d}}\cdot\sum_{t\in[T]}\min\left\\{1,w_{t}^{2}\right\\}\leq\frac{2LB\kappa}{\sqrt{c_{1}d}}.$
(B.10)

Plugging (B.2), (B.2) and (B.10) into (B.6), we have

$\mathrm{Reg}(T)\leq
2\beta_{T}\left[\sqrt{2\kappa}\cdot\sqrt{\sum_{t\in[T]}\nu_{t}^{2}+1}+\frac{2L\kappa}{c_{0}^{2}\sqrt{\lambda}}+\frac{2LB\kappa}{\sqrt{c_{1}d}}\right].$

###  B.3 Proof of Lemma B.1

Recall that
$z_{t}({\bm{\theta}})=\frac{y_{t}-\langle{\bm{\phi}}_{t},{\bm{\theta}}\rangle}{\sigma_{t}}$.
Direct computation yields that

$\nabla^{2}L_{T}({\bm{\theta}})=\lambda{\bm{I}}+\sum_{t=1}^{T}\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}})}}\right)^{3}\frac{{\bm{\phi}}_{t}{\bm{\phi}}_{t}^{\top}}{\sigma_{t}^{2}}.$

Clearly, for any ${\bm{\theta}}\in{\mathbb{R}}^{d}$,

$\nabla^{2}L_{T}({\bm{\theta}})\preceq\lambda{\bm{I}}+\sum_{t=1}^{T}\frac{{\bm{\phi}}_{t}{\bm{\phi}}_{t}^{\top}}{\sigma_{t}^{2}}={\bm{H}}_{T}.$

For the other direction, we decompose it into four terms and analyze them
respectively.

$\displaystyle\begin{split}\nabla^{2}L_{T}({\bm{\theta}})&={\bm{H}}_{T}-\underbrace{\sum_{t=1}^{T}\left[1-\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right)^{3}\right]\frac{{\bm{\phi}}_{t}{\bm{\phi}}_{t}^{\top}}{\sigma_{t}^{2}}}_{{\bm{H}}_{1,T}}\\\
&\qquad+\underbrace{\sum_{t=1}^{T}\left[\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}})}}\right)^{3}-\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right)^{3}\right]\frac{{\bm{\phi}}_{t}{\bm{\phi}}_{t}^{\top}}{\sigma_{t}^{2}}}_{{\bm{H}}_{2,T}}.\end{split}$
(B.11)

where ${\mathbb{E}}_{t}[\cdot]={\mathbb{E}}[\cdot|{\mathcal{F}}_{t-1}]$ for
simplicity.

Since $\nu_{t},{\bm{\theta}}_{t-1}\in{\mathcal{F}}_{t-1}$, from Algorithm 1,
we have $\sigma_{t},w_{t},\tau_{t}\in{\mathcal{F}}_{t-1}$.

##### Analysis of ${\bm{H}}_{1,T}$

Notice that for any unit norm ${\bm{v}}\in{\mathbb{R}}^{d}$, it follows that

$\displaystyle{\bm{v}}^{\top}{\bm{H}}_{1,T}{\bm{v}}$
$\displaystyle=\sum_{t=1}^{T}\left[1-\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right)^{3}\right]\left\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{v}}\right\rangle^{2}$
$\displaystyle\leq
3\sum_{t=1}^{T}\left[1-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right]\left\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{v}}\right\rangle^{2}$
$\displaystyle\leq
3\sum_{t=1}^{T}\left[1-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right]\cdot\sup_{t\in[T]}\left\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{v}}\right\rangle^{2}$
$\displaystyle\leq
3\sum_{t=1}^{T}\left[1-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right]\cdot\sup_{t\in[T]}\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{T}^{-1}}^{2}\cdot{\bm{v}}^{\top}{\bm{H}}_{T}{\bm{v}}$
$\displaystyle\overset{(a)}{\leq}3\sum_{t=1}^{T}\left[1-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right]\cdot\sup_{t\in[T]}\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{t}^{-1}}^{2}\cdot{\bm{v}}^{\top}{\bm{H}}_{T}{\bm{v}}$
$\displaystyle\overset{(b)}{=}3\sum_{t=1}^{T}\left[1-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right]\cdot\sup_{t\in[T]}\frac{w_{t}^{2}}{1+w_{t}^{2}}\cdot{\bm{v}}^{\top}{\bm{H}}_{T}{\bm{v}},$

where $(a)$ uses ${\bm{H}}_{T}^{-1}\preceq{\bm{H}}_{t}^{-1}$ for all $t\in[T]$
and $(b)$ follows from

$\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{t}^{-1}}^{2}=\frac{{\bm{\phi}}_{t}^{\top}}{\sigma_{t}}\left({\bm{H}}_{t-1}^{-1}-\frac{{\bm{H}}_{t-1}^{-1}\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\frac{{\bm{\phi}}_{t}^{\top}}{\sigma_{t}}{\bm{H}}_{t-1}^{-1}}{1+\frac{{\bm{\phi}}_{t}^{\top}}{\sigma_{t}}{\bm{H}}_{t-1}^{-1}\frac{{\bm{\phi}}_{t}^{\top}}{\sigma_{t}}}\right)\frac{{\bm{\phi}}_{t}}{\sigma_{t}}=w_{t}^{2}-\frac{w_{t}^{4}}{1+w_{t}^{2}}=\frac{w_{t}^{2}}{1+w_{t}^{2}}.$

By the arbitrariness of ${\bm{v}}$, we know that

${\bm{H}}_{1,T}\preceq
3\sum_{t=1}^{T}\left[1-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right]\cdot\sup_{t\in[T]}\frac{w_{t}^{2}}{1+w_{t}^{2}}\cdot{\bm{H}}_{T}.$
(B.12)

Let
$X_{t}=1-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}$.
It is obvious that $0\leq X_{t}\leq 1$. We then focus on concentration of
$\sum_{t=1}^{T}X_{t}$. To that end, we need a variance-aware Bernstein
inequality Lemma F.2 for martingales. Lemma F.2 implies that with probability
at least $1-\frac{\delta}{T^{2}}$, we have

$\sum_{t=1}^{T}X_{t}\leq\sum_{t=1}^{T}{\mathbb{E}}_{t}X_{t}+3\sqrt{\sum_{t=1}^{T}\operatorname{{\rm
Var}}[X_{t}|{\mathcal{F}}_{t-1}]\cdot\log\frac{2KT^{2}}{\delta}}+5\log\frac{2KT^{2}}{\delta}$

where $K:=1+\lceil 2\log_{2}V\rceil$ and $V^{2}$ is an upper bound satisfying
$\sum_{t=1}^{T}{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}]\leq V^{2}$.

First notice that for any $t\geq 1$, we have

$\displaystyle\begin{split}{\mathbb{E}}_{t}X_{t}&=1-{\mathbb{E}}_{t}\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}={\mathbb{E}}_{t}\frac{z_{t}^{2}({{\bm{\theta}}^{*}})}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}(\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}+\tau_{t})}\\\
&\leq\frac{1}{2\tau_{t}^{2}}{\mathbb{E}}_{t}z_{t}^{2}({\bm{\theta}}^{*})\leq\frac{b^{2}}{2\tau_{t}^{2}}\leq\frac{b^{2}}{2\tau_{0}^{2}}\frac{w_{t}^{2}}{1+w_{t}^{2}}\end{split}$
(B.13)

which implies that

$\sum_{t=1}^{T}{\mathbb{E}}_{t}X_{t}\leq\frac{b^{2}}{2\tau_{0}^{2}}\frac{w_{t}^{2}}{1+w_{t}^{2}}\leq\frac{b^{2}}{2\tau_{0}^{2}}\sum_{t=1}^{T}\min\\{1,w_{t}^{2}\\}\leq\frac{\kappa
b^{2}}{\tau_{0}^{2}}$

where the last inequality uses Lemma F.5 and thus

$\sum_{t=1}^{T}\min\\{1,w_{t}^{2}\\}=\sum_{t=1}^{T}\min\left\\{1,\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{t-1}^{-1}}^{2}\right\\}\leq
2d\log\left(1+\frac{TL^{2}}{d\lambda\sigma_{\min}^{2}}\right)=2\kappa.$

Secondly, we have

$\displaystyle\operatorname{{\rm Var}}[X_{t}|{\mathcal{F}}_{t-1}]$
$\displaystyle\leq{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}]\leq{\mathbb{E}}_{t}\left(1-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right)^{2}\overset{(*)}{\leq}\frac{1}{4}\frac{{\mathbb{E}}_{t}z_{t}^{2}({\bm{\theta}}^{*})}{\tau_{t}^{2}}\leq\frac{b^{2}}{4\tau_{t}^{2}}$

where $(*)$ uses
$1-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\leq\frac{z_{t}^{2}({\bm{\theta}}^{*})}{2\tau_{t}\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}$
which is also used in (B.13). As a result, we have

$\sum_{t=1}^{T}\operatorname{{\rm
Var}}[X_{t}|{\mathcal{F}}_{t-1}]\leq\sum_{t=1}^{T}\frac{b^{2}}{4\tau_{t}^{2}}\leq\frac{b^{2}}{4\tau_{0}^{2}}\sum_{t=1}^{T}\frac{w_{t}^{2}}{1+w_{t}^{2}}\leq\frac{\kappa
b^{2}}{2\tau_{0}^{2}}.$

Once requiring $\tau_{0}^{2}\geq 2\kappa b^{2}$, we have
$\sum_{t=1}^{T}\operatorname{{\rm Var}}[X_{t}|{\mathcal{F}}_{t-1}]\leq 1$ and
thus we can set $V=1$ and obtain $K=1$. Putting them together, if
$\tau_{0}^{2}\geq\frac{2\kappa b^{2}}{\log\frac{2T^{2}}{\delta}}$, with
probability at least $1-\delta$, we have

$\displaystyle\sum_{t=1}^{T}X_{t}$ $\displaystyle\leq\frac{\kappa
b^{2}}{\tau_{0}^{2}}+\frac{3b}{\tau_{0}}\sqrt{\frac{\kappa\log\frac{2T^{2}}{\delta}}{2}}+5\log\frac{2T^{2}}{\delta}$
$\displaystyle\leq\frac{1}{2}\log\frac{2T^{2}}{\delta}+\frac{3}{2}\log\frac{2T^{2}}{\delta}+5\log\frac{2T^{2}}{\delta}$
$\displaystyle\leq 9\log\frac{2T^{2}}{\delta}=\frac{1}{12c_{0}^{2}}$ (B.14)

where the last equation is due to the definition of $c_{0}$. Finally, taking a
union bound for the last inequality from $T=1$ to $\infty$ and using the fact
that $\sum_{t=1}^{\infty}t^{-2}<2$, we have
$\sum_{t=1}^{T}X_{t}\leq\frac{1}{12c_{0}^{2}}$ for all $T\geq 1$ with
probability at least $1-2\delta$.

On the other hand, by the choice of $\sigma_{t}$, we have
$\sigma_{t}^{2}\geq\frac{1}{c_{0}^{2}}\cdot\|{\bm{\phi}}_{t}\|_{{\bm{H}}_{t-1}^{-1}}^{2}$,
which implies

$\sup_{t\in[T]}\frac{w_{t}^{2}}{1+w_{t}^{2}}\leq\sup_{t\in[T]}w_{t}^{2}\leq
c_{0}^{2}.$ (B.15)

Plugging (B.3) and (B.15) into (B.12), we have

${\bm{H}}_{1,T}\preceq\frac{1}{4}{\bm{H}}_{T}.$ (B.16)

##### Analysis of ${\bm{H}}_{2,T}$

We first notice that

$\displaystyle\left|\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}})}}\right)^{3}-\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right)^{3}\right|\leq
3\left|\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}})}}-\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right|$
$\displaystyle\qquad\leq\frac{3\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}})}\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\frac{|z_{t}^{2}({\bm{\theta}})-z_{t}^{2}({\bm{\theta}}^{*})|}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}})}+\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}.$
(B.17)

Notice that
$z_{t}({\bm{\theta}})=z_{t}({\bm{\theta}}^{*})+\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{\theta}}-{\bm{\theta}}^{*}\rangle$.
It then follow that for any $c>0$

$\displaystyle
z_{t}^{2}({\bm{\theta}})\leq\left(1+\frac{1}{c}\right)z_{t}^{2}({\bm{\theta}}^{*})+(1+c)\left\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{\theta}}-{\bm{\theta}}^{*}\right\rangle^{2};$
$\displaystyle
z_{t}^{2}({\bm{\theta}}^{*})\leq\left(1+\frac{1}{c}\right)z_{t}^{2}({\bm{\theta}})+(1+c)\left\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{\theta}}-{\bm{\theta}}^{*}\right\rangle^{2},$

By discussing which is larger between $z_{t}^{2}({\bm{\theta}})$ and
$z_{t}^{2}({\bm{\theta}}^{*})$, we have

$|z_{t}^{2}({\bm{\theta}})-z_{t}^{2}({\bm{\theta}}^{*})|\leq\frac{1}{c}\min\left\\{z_{t}^{2}({\bm{\theta}}),z_{t}^{2}({\bm{\theta}}^{*})\right\\}+\left(1+c\right)\left\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{\theta}}-{\bm{\theta}}^{*}\right\rangle^{2}.$
(B.18)

Plugging (B.18) into (B.3), we have that

$\displaystyle\left|\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}})}}\right)^{3}-\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+z_{t}^{2}({\bm{\theta}}^{*})}}\right)^{3}\right|$
$\displaystyle\qquad\leq\frac{3\tau_{t}}{\tau_{t}^{2}+\min\left\\{z_{t}^{2}({\bm{\theta}}),z_{t}^{2}({\bm{\theta}}^{*})\right\\}}\frac{\frac{1}{c}\min\left\\{z_{t}^{2}({\bm{\theta}}),z_{t}^{2}({\bm{\theta}}^{*})\right\\}}{2\sqrt{\tau_{t}^{2}+\min\left\\{z_{t}^{2}({\bm{\theta}}),z_{t}^{2}({\bm{\theta}}^{*})\right\\}}}+\frac{3(1+c)}{2\tau_{t}^{2}}\left\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{\theta}}-{\bm{\theta}}^{*}\right\rangle^{2}$
$\displaystyle\qquad\leq\frac{3}{2c}+\frac{3(1+c)}{2\tau_{t}^{2}}\left\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{\theta}}-{\bm{\theta}}^{*}\right\rangle^{2}\overset{(a)}{\leq}\frac{3}{2c}+\frac{6(1+c)}{\tau_{t}^{2}}\frac{L^{2}B^{2}}{\sigma_{t}^{2}}$
$\displaystyle\qquad\leq\frac{3}{2c}+\frac{6(1+c)}{\tau_{0}^{2}}\frac{w_{t}^{2}L^{2}B^{2}}{\sigma_{t}^{2}}\overset{(b)}{\leq}\frac{3}{2c}+\frac{6(1+c)c_{1}d}{\tau_{0}^{2}}$
(B.19)

where $(a)$ uses
$\left\langle\frac{{\bm{\phi}}_{t}}{\sigma_{t}},{\bm{\theta}}-{\bm{\theta}}^{*}\right\rangle\leq\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|\left(\|{\bm{\theta}}\|+\|{\bm{\theta}}^{*}\|\right)\leq\frac{2LB}{\sigma_{t}}$
due to $\left\|{\bm{\phi}}_{t}\right\|\leq L$ and
${\bm{\theta}},{\bm{\theta}}^{*}\in\mathrm{Ball}_{d}(B)$ and $(b)$ uses the
following result. By the definition of $\sigma_{t}$, we have
$\sigma_{t}\geq{\sqrt{LB}\|{\bm{\phi}}_{t}\|^{\frac{1}{2}}_{{\bm{H}}_{t-1}^{-1}}}/{c_{1}^{\frac{1}{4}}d^{\frac{1}{4}}}$
which implies $\sigma_{t}^{2}\geq\frac{w_{t}^{2}L^{2}B^{2}}{c_{1}d}$. As a
result of (B.3), by definition of ${\bm{H}}_{3,T}$, we have

$-\left(\frac{3}{2c}+\frac{6(1+c)c_{1}d}{\tau_{0}^{2}}\right)\sum_{t=1}^{T}\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\frac{{\bm{\phi}}_{t}^{\top}}{\sigma_{t}}\preceq{\bm{H}}_{2,T}$
(B.20)

##### Putting pieces together

Plugging (B.16) and (B.20) into (B.11), with probability at least $1-\delta$,
for any $T\geq 1$ and for all ${\bm{\theta}}\in\mathrm{Ball}_{d}(B)$, we have

$\displaystyle\nabla^{2}L_{T}({\bm{\theta}})$
$\displaystyle\succeq{\bm{H}}_{T}-\frac{1}{4}{\bm{H}}_{T}-\left(\frac{3}{2c}+\frac{6(1+c)c_{1}d}{\tau_{0}^{2}}\right)\sum_{t=1}^{T}\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\frac{{\bm{\phi}}_{t}^{\top}}{\sigma_{t}}$
$\displaystyle\succeq\frac{3\lambda}{4}{\bm{I}}+\left(1-\frac{1}{4}-\frac{3}{2c}-\frac{6(1+c)c_{1}d}{\tau_{0}^{2}}\right)\sum_{t=1}^{T}\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\frac{{\bm{\phi}}_{t}^{\top}}{\sigma_{t}}.$

Notice that $c_{1}=\frac{1}{42\cdot\frac{2T^{2}}{\delta}}$. If we set $c=6$
and
$\tau_{0}\sqrt{\frac{2T^{2}}{\delta}}\geq\max\\{\sqrt{2\kappa}b,2\sqrt{d}\\}$,
we have

$\max\left\\{\frac{3}{2c},\frac{6(1+c)c_{1}d}{\tau_{0}^{2}}\right\\}\leq\frac{1}{4}.$

As a result, we have

$\nabla^{2}L_{T}({\bm{\theta}})\succeq\frac{3\lambda}{4}{\bm{I}}+\frac{1}{4}\sum_{t=1}^{T}\frac{{\bm{\phi}}}{\sigma_{t}}\frac{{\bm{\phi}}^{\top}}{\sigma_{t}}\succeq\frac{1}{4}{\bm{H}}_{T}.$

###  B.4 Proof of Lemma B.2

For simplicity, we denote $z_{t}^{*}=z_{t}({\bm{\theta}}^{*})$ for short. By
triangle inequality, we have

$\displaystyle\|\nabla L_{T}({\bm{\theta}}^{*})\|_{{\bm{H}}_{T}^{-1}}$
$\displaystyle\leq\|\lambda{\bm{\theta}}^{*}\|_{{\bm{H}}_{T}^{-1}}+\left\|\sum_{t=1}^{T}\frac{\tau_{t}z_{t}^{*}}{\sqrt{\tau_{t}^{2}+(z_{t}^{*})^{2}}}\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{T}^{-1}}$
$\displaystyle\leq\|\lambda{\bm{\theta}}^{*}\|_{{\bm{H}}_{T}^{-1}}+\underbrace{\left\|\sum_{t=1}^{T}\frac{\tau_{t}z_{t}^{*}}{\sqrt{\tau_{t}^{2}+(z_{t}^{*})^{2}}}\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{T}^{-1}}}_{:={\bm{d}}_{T}}.$
(B.21)

##### For the residual term $\|\lambda{\bm{\theta}}^{*}\|_{{\bm{H}}_{T}^{-1}}$

Notice that ${\bm{H}}_{T}\succeq\lambda{\bm{I}}$ and thus
${\bm{H}}_{T}^{-1}\preceq\lambda^{-1}{\bm{I}}_{d}$. Therefore,
$\|\lambda{\bm{\theta}}^{*}\|_{{\bm{H}}_{T}^{-1}}\leq\sqrt{\lambda}B$.

##### For the self-normalized term $\|{\bm{d}}_{T}\|_{{\bm{H}}_{T}^{-1}}$

The fact that
${\bm{H}}_{T}={\bm{H}}_{T-1}+\frac{{\bm{\phi}}_{T}{\bm{\phi}}_{T}^{\top}}{\sigma_{T}^{2}}$
together with the Woodbury matrix identity implies that

${\bm{H}}_{T}^{-1}={\bm{H}}_{T-1}^{-1}-\frac{{\bm{H}}_{T-1}^{-1}{\bm{\phi}}_{T}{\bm{\phi}}_{T}^{\top}{\bm{H}}_{T-1}^{-1}}{\sigma_{T}^{2}(1+w_{T}^{2})}\quad\text{where}\quad
w_{T}^{2}:=\frac{{\bm{\phi}}_{T}^{\top}{\bm{H}}_{T-1}^{-1}{\bm{\phi}}_{T}}{\sigma_{T}^{2}}=\left\|\frac{{\bm{\phi}}_{T}}{\sigma_{T}}\right\|_{{\bm{H}}_{T-1}}^{2}.$
(B.22)

Clearly, $w_{T}$ is ${\mathcal{F}}_{T-1}$-measurable and thus is predictable.
By definition of ${\bm{d}}_{T}$ and (B.22),

$\displaystyle\|{\bm{d}}_{T}\|_{{\bm{H}}_{T}^{-1}}^{2}$
$\displaystyle=\left({\bm{d}}_{T-1}+\frac{{{\tau}}_{T}z_{T}^{*}}{\sqrt{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}}\frac{{\bm{\phi}}_{T}}{\sigma_{T}}\right)^{\top}{\bm{H}}_{T}^{-1}\left({\bm{d}}_{T-1}+\frac{{{\tau}}_{T}z_{T}^{*}}{\sqrt{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}}\frac{{\bm{\phi}}_{T}}{\sigma_{T}}\right)$
$\displaystyle=\|{\bm{d}}_{T-1}\|_{{\bm{H}}_{T-1}^{-1}}^{2}-\frac{1}{1+w_{T}^{2}}\left(\frac{{\bm{d}}_{T-1}^{\top}{\bm{H}}_{T-1}^{-1}{\bm{\phi}}_{T}}{\sigma_{T}}\right)^{2}$
$\displaystyle\qquad\qquad+\frac{2{{\tau}}_{T}z_{T}^{*}}{\sqrt{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}}\frac{{\bm{d}}_{T-1}^{\top}{\bm{H}}_{T}^{-1}{\bm{\phi}}_{T}}{\sigma_{T}}+\frac{\tau_{T}^{2}(z_{T}^{*})^{2}}{\tau_{T}^{2}+(z_{T}^{*})^{2}}\frac{{\bm{\phi}}_{T}^{\top}{\bm{H}}_{T}^{-1}{\bm{\phi}}_{T}}{\sigma_{T}^{2}}$
$\displaystyle\leq\|{\bm{d}}_{T-1}\|_{{\bm{H}}_{T-1}^{-1}}^{2}+\underbrace{\frac{2{{\tau}}_{T}z_{T}^{*}}{\sqrt{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}}\frac{{\bm{d}}_{T-1}^{\top}{\bm{H}}_{T}^{-1}{\bm{\phi}}_{T}}{\sigma_{T}}}_{I_{1}}+\underbrace{\frac{\tau_{T}^{2}(z_{T}^{*})^{2}}{\tau_{T}^{2}+(z_{T}^{*})^{2}}\frac{{\bm{\phi}}_{T}^{\top}{\bm{H}}_{T}^{-1}{\bm{\phi}}_{T}}{\sigma_{T}^{2}}}_{I_{2}}.$
(B.23)

For $I_{1}$, by (B.22), we have

$\displaystyle I_{1}$
$\displaystyle=\frac{2{{\tau}}_{T}z_{T}^{*}}{\sqrt{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}}\frac{1}{\sigma_{T}}{\bm{d}}_{T-1}^{\top}\left({\bm{H}}_{T-1}^{-1}-\frac{{\bm{H}}_{T-1}^{-1}{\bm{\phi}}_{T}{\bm{\phi}}_{T}^{\top}{\bm{H}}_{T-1}^{-1}}{\sigma_{T}^{2}(1+w_{T}^{2})}\right){\bm{\phi}}_{T}$
$\displaystyle=\frac{2{{\tau}}_{T}z_{T}^{*}}{\sqrt{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}}\frac{1}{1+w_{T}^{2}}\frac{{\bm{d}}_{T-1}^{\top}{\bm{H}}_{T-1}^{-1}{\bm{\phi}}_{T}}{\sigma_{T}}.$

For $I_{2}$, we have

$\displaystyle I_{2}$
$\displaystyle=\frac{{{\tau}}_{T}^{2}(z_{T}^{*})^{2}}{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}\frac{{\bm{\phi}}_{T}^{\top}{\bm{H}}_{T}^{-1}{\bm{\phi}}_{T}}{\sigma_{T}^{2}}$
$\displaystyle=\frac{{{\tau}}_{T}^{2}(z_{T}^{*})^{2}}{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}\frac{1}{\sigma_{T}^{2}}{\bm{\phi}}_{T}^{\top}\left({\bm{H}}_{T-1}^{-1}-\frac{{\bm{H}}_{T-1}^{-1}{\bm{\phi}}_{T}{\bm{\phi}}_{T}^{\top}{\bm{H}}_{T-1}^{-1}}{\sigma_{T}^{2}(1+w_{T}^{2})}\right){\bm{\phi}}_{T}$
$\displaystyle=\frac{{{\tau}}_{T}^{2}(z_{T}^{*})^{2}}{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}\left(w_{T}^{2}-\frac{w_{T}^{4}}{1+w_{T}^{2}}\right)$
$\displaystyle=\frac{{{\tau}}_{T}^{2}(z_{T}^{*})^{2}}{{{\tau}}_{T}^{2}+(z_{T}^{*})^{2}}\frac{w_{T}^{2}}{1+w_{T}^{2}}.$

Using the equations for $I_{1},I_{2}$ and iterating (B.4), we have

$\|{\bm{d}}_{T}\|_{{\bm{H}}_{T}^{-1}}^{2}\leq\sum_{t=1}^{T}\frac{{{\tau}}_{t}z_{t}^{*}}{\sqrt{{{\tau}}_{t}^{2}+(z_{t}^{*})^{2}}}\frac{2}{1+w_{t}^{2}}\frac{{\bm{d}}_{t-1}^{\top}{\bm{H}}_{t-1}^{-1}{\bm{\phi}}_{t}}{\sigma_{t}}+\sum_{t=1}^{T}\frac{{{\tau}}_{t}^{2}(z_{t}^{*})^{2}}{{{\tau}}_{t}^{2}+(z_{t}^{*})^{2}}\frac{w_{t}^{2}}{1+w_{t}^{2}}.$

Recall that

$\kappa=d\log\left(1+\frac{TL^{2}}{d\lambda\sigma_{\min}^{2}}\right).$

######  Lemma B.3.

Assume ${\mathbb{E}}[(z_{t}^{*})^{2}|{\mathcal{F}}_{t-1}]\leq b^{2}$ for all
$t\geq 1$. Let $A_{t}$ denotes the event where
$\|{\bm{d}}_{n}\|_{{\bm{H}}_{n}^{-1}}\leq\alpha_{n}$ for all $n\in[t]$. With
probability at least $1-\delta/2$, we have for all $T\geq 1$,

$\sum_{t=1}^{T}\frac{2\tau_{t}z_{t}^{*}{\bm{1}}_{A_{t-1}}}{(\tau_{t}^{2}+(z_{t}^{*})^{2})^{1/2}}\frac{1}{1+w_{t}^{2}}\frac{{\bm{d}}_{t-1}^{\top}{\bm{H}}_{t-1}^{-1}{\bm{\phi}}_{t}}{\sigma_{t}}\leq
4\max_{t\in[T]}\alpha_{t}\cdot\left[\frac{\kappa
b^{2}}{4\tau_{0}}+b\sqrt{\kappa\log\frac{2T^{2}}{\delta}}+\frac{2\tau_{0}}{3}\log\frac{2T^{2}}{\delta}\right].$

######  Lemma B.4.

Assume ${\mathbb{E}}[(z_{t}^{*})^{2}|{\mathcal{F}}_{t-1}]\leq b^{2}$ for all
$t\geq 1$. For a fixed $\tau\geq 0$, with probability at least $1-\delta/2$,
the follow inequality uniformly holds for all $T\geq 1$,

$\sum_{t=1}^{T}\frac{\tau_{t}^{2}(z_{t}^{*})^{2}}{\tau_{t}^{2}+(z_{t}^{*})^{2}}\frac{w_{t}^{2}}{1+w_{t}^{2}}\leq\left[\sqrt{2\kappa}b+\tau_{0}\sqrt{\log\frac{2T^{2}}{\delta}}\right]^{2}.$

For any $T\geq 1$, we define

$\alpha_{T}=8\left[\frac{\kappa
b^{2}}{\tau_{0}}+b\sqrt{\kappa\log\frac{2T^{2}}{\delta}}+\tau_{0}\log\frac{2T^{2}}{\delta}\right].$
(B.24)

As a result of Lemma B.3 and Lemma B.4, with probability at least $1-\delta$,
for all $T\geq 1$,

$\sum_{t=1}^{T}\frac{2\tau_{t}z_{t}^{*}{\bm{1}}_{A_{t-1}}}{\sqrt{\tau_{t}^{2}+(z_{t}^{*})^{2}}}\frac{1}{1+w_{t}^{2}}\frac{{\bm{d}}_{t-1}^{\top}{\bm{H}}_{t-1}^{-1}{\bm{\phi}}_{t}}{\sigma_{t}}\leq\frac{\alpha_{T}^{2}}{2}\quad\text{and}\quad\sum_{t=1}^{T}\frac{\tau_{t}^{2}(z_{t}^{*})^{2}}{\tau_{t}^{2}+(z_{t}^{*})^{2}}\frac{w_{t}^{2}}{1+w_{t}^{2}}\leq\frac{\alpha_{T}^{2}}{2}.$

We can conclude that all $\\{A_{t}\\}_{t\geq 0}$ is true and thus
$\|{\bm{d}}_{T}\|_{{\bm{H}}_{T}^{-1}}\leq\alpha_{T}$ for all $T\geq 1$.

###  B.5 Proof of Lemma B.3

###### Proof of Lemma B.3.

We will make use of the Freedman inequality Lemma F.1 to prove our result.
Recall that $\tau_{t}=\tau_{0}\frac{\sqrt{1+w_{t}^{2}}}{w_{t}}$. Set
$Y_{t}=\frac{\tau_{t}z_{t}^{*}}{\sqrt{\tau_{t}^{2}+(z_{t}^{*})^{2}}}\frac{2}{1+w_{t}^{2}}\frac{{\bm{d}}_{t-1}^{\top}{\bm{H}}_{t-1}^{-1}{\bm{\phi}}_{t}{\bm{1}}_{A_{t-1}}}{\sigma_{t}}$
with the event $A_{t-1}$ defined in the lemma. For simplicity, we denote
$X_{t}=Y_{t}-{\mathbb{E}}[Y_{t}|{\mathcal{F}}_{t-1}]$. Notice that

$\left|\frac{{\bm{d}}_{t-1}^{\top}{\bm{H}}_{t-1}^{-1}{\bm{\phi}}_{t}}{\sigma_{t}}\cdot{\bm{1}}_{A_{t-1}}\right|\leq\|{\bm{d}}_{t-1}{\bm{1}}_{A_{t-1}}\|_{{\bm{H}}_{t-1}^{-1}}\cdot\left\|\frac{{\bm{\phi}}_{t}}{\sigma_{t}}\right\|_{{\bm{H}}_{t-1}^{-1}}\leq\alpha_{t-1}w_{t}.$

As a result, we have

$|Y_{t}|\leq\tau_{t}\alpha_{t-1}\cdot\frac{2w_{t}}{1+w_{t}^{2}}\leq
2\tau_{0}\alpha_{t-1}\quad\text{and
thus}\quad|X_{t}|\leq|Y_{t}|+|{\mathbb{E}}[Y_{t}|{\mathcal{F}}_{t-1}]|\leq
4\tau_{0}\alpha_{t-1}.$

We also find that

$\displaystyle{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}]$
$\displaystyle\overset{(a)}{\leq}{\mathbb{E}}[Y_{t}^{2}|{\mathcal{F}}_{t-1}]={\mathbb{E}}\left[\left(\frac{2w_{t}}{1+w_{t}^{2}}\right)^{2}\|{\bm{d}}_{t-1}\|_{{\bm{H}}_{t-1}^{-1}}^{2}{\bm{1}}_{A_{t-1}}\frac{\tau_{t}^{2}(z_{t}^{*})^{2}}{\tau_{t}^{2}+(z_{t}^{*})^{2}}\bigg{|}{\mathcal{F}}_{t-1}\right]$
$\displaystyle\overset{(b)}{\leq}\left(\frac{2w_{t}}{1+w_{t}^{2}}\right)^{2}\alpha_{t-1}^{2}b^{2}\leq\min\\{1,2w_{t}\\}^{2}\alpha_{t-1}^{2}b^{2}\leq
4\min\\{1,w_{t}^{2}\\}\alpha_{t-1}^{2}b^{2}$

where $(a)$ uses ${\mathbb{E}}(X-{\mathbb{E}}X)^{2}\leq{\mathbb{E}}X^{2}$ for
any random variable $X$ and $(b)$ uses
${\mathbb{E}}[\varepsilon_{t}^{2}|{\mathcal{F}}_{t-1}]\leq
b^{2}\sigma_{t}^{2}$ due to
${\mathbb{E}}[(z_{t}^{*})^{2}|{\mathcal{F}}_{t-1}]\leq b^{2}$.

Notice that
$\|{\bm{\phi}}_{t}\|/\sigma_{t}\leq\|{\bm{\phi}}_{t}\|/\sigma_{\min}\leq
L/\sigma_{\min}$. Then by Lemma F.5, we have

$\sum_{t=1}^{T}\min\\{1,w_{t}^{2}\\}\leq
2d\log\left(1+\frac{TL^{2}}{d\lambda\sigma_{\min}^{2}}\right):=2\kappa.$
(B.25)

Hence, by (B.25),

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}]$
$\displaystyle\leq
4\sum_{t=1}^{T}\min\\{1,w_{t}^{2}\\}\alpha_{t-1}^{2}b^{2}\leq
4\max_{t\in[T]}\alpha_{t}^{2}\cdot\sum_{t=1}^{T}\min\\{1,w_{t}^{2}\\}b^{2}$
$\displaystyle\leq\max_{t\in[T]}\alpha_{t}^{2}\cdot
8db^{2}\log\left(1+\frac{TL^{2}}{d\lambda\sigma_{\min}^{2}}\right)\leq 8\kappa
b^{2}\cdot\max_{t\in[T]}\alpha_{t}^{2}.$

On the other hand, using ${\mathbb{E}}[z_{t}^{*}|{\mathcal{F}}_{t-1}]=0$ we
have

$\displaystyle\left|{\mathbb{E}}\left[\frac{\tau_{t}z_{t}^{*}}{\sqrt{\tau_{t}^{2}+(z_{t}^{*})^{2}}}\bigg{|}{\mathcal{F}}_{t-1}\right]\right|=\left|{\mathbb{E}}\left[\left(\frac{\tau_{t}}{\sqrt{\tau_{t}^{2}+(z_{t}^{*})^{2}}}-1\right)z_{t}^{*}\bigg{|}{\mathcal{F}}_{t-1}\right]\right|\leq{\mathbb{E}}\left[\frac{(z_{t}^{*})^{2}}{2\tau_{t}}\bigg{|}{\mathcal{F}}_{t-1}\right]\leq\frac{b^{2}}{2\tau_{t}}$

which implies

$\displaystyle\left|\sum_{t=1}^{T}{\mathbb{E}}[Y_{t}|{\mathcal{F}}_{t-1}]\right|$
$\displaystyle\leq\sum_{t=1}^{T}\frac{b^{2}}{2\tau_{t}}\frac{w_{t}}{1+w_{t}^{2}}\alpha_{t-1}\leq\frac{b^{2}}{2\tau_{0}}\sum_{t=1}^{T}\frac{w_{t}^{2}}{1+w_{t}^{2}}\alpha_{t-1}$
$\displaystyle\leq\sup_{t\in[T]}\alpha_{t}\cdot\frac{b^{2}}{2\tau}\sum_{t=1}^{T}\min\\{1,w_{t}^{2}\\}\leq\sup_{t\in[T]}\alpha_{t}\cdot\frac{\kappa
b^{2}}{\tau_{0}}.$

By Freedman inequality in Lemma F.1, it follows that for a given $T$ and
$\tau_{0}$, with probability $1-\frac{\delta}{2T^{2}}$,

$\displaystyle\sum_{t=1}^{T}Y_{t}$
$\displaystyle\leq\left|\sum_{t=1}^{T}{\mathbb{E}}[Y_{t}|{\mathcal{F}}_{t-1}]\right|+4\max_{t\in[T]}\alpha_{t}\cdot\left[b\sqrt{\kappa\log\frac{2T^{2}}{\delta}}+\frac{2\tau_{0}}{3}\log\frac{2T^{2}}{\delta}\right]$
$\displaystyle\leq 4\max_{t\in[T]}\alpha_{t}\cdot\left[\frac{\kappa
b^{2}}{4\tau_{0}}+b\sqrt{\kappa\log\frac{2T^{2}}{\delta}}+\frac{2\tau_{0}}{3}\log\frac{2T^{2}}{\delta}\right].$

Finally, taking a union bound for the last inequality from $T=1$ to $\infty$
and using the fact that $\sum_{t=1}^{\infty}t^{-2}<2$ complete the proof. ∎

###  B.6 Proof of Lemma B.4

###### Proof of Lemma B.4.

Set
$Y_{t}=\frac{\tau_{t}^{2}(z_{t}^{*})^{2}}{\tau_{t}^{2}+(z_{t}^{*})^{2}}\frac{w_{t}^{2}}{1+w_{t}^{2}}$
and $X_{t}=Y_{t}-{\mathbb{E}}[Y_{t}|{\mathcal{F}}_{t-1}]$. Recall that
$\tau_{t}=\tau_{0}\frac{\sqrt{1+w_{t}^{2}}}{w_{t}}$. Clearly, we have
$|Y_{t}|\leq\tau_{t}^{2}\frac{w_{t}^{2}}{1+w_{t}^{2}}\leq\tau_{0}^{2}$ and
thus
$|X_{t}|=|Y_{t}-{\mathbb{E}}[Y_{t}|{\mathcal{F}}_{t-1}]|\leq\max\\{|Y_{t}|,|{\mathbb{E}}[Y_{t}|{\mathcal{F}}_{t-1}]|\\}\leq\tau_{0}^{2}$.
We also find that

$\displaystyle{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}]$
$\displaystyle\overset{(a)}{\leq}{\mathbb{E}}[Y_{t}^{2}|{\mathcal{F}}_{t-1}]\leq\left(\frac{w_{t}^{2}}{1+w_{t}^{2}}\right)^{2}{\mathbb{E}}\left[\left(\frac{\tau_{t}^{2}(z_{t}^{*})^{2}}{\tau_{t}^{2}+(z_{t}^{*})^{2}}\right)^{2}\bigg{|}{\mathcal{F}}_{t-1}\right]$
$\displaystyle\leq\tau_{t}^{2}\left(\frac{w_{t}^{2}}{1+w_{t}^{2}}\right)^{2}{\mathbb{E}}\left[(z_{t}^{*})^{2}|{\mathcal{F}}_{t-1}\right]\overset{(b)}{\leq}\tau_{0}^{2}b^{2}\frac{w_{t}^{2}}{1+w_{t}^{2}}$

where $(a)$ uses ${\mathbb{E}}(X-{\mathbb{E}}X)^{2}\leq{\mathbb{E}}X^{2}$ for
any random variable $X$ and $(b)$ uses
${\mathbb{E}}[(z_{t}^{*})^{2}|{\mathcal{F}}_{t-1}]\leq b^{2}$ due to
${\mathbb{E}}[\varepsilon_{t}^{2}|{\mathcal{F}}_{t-1}]\leq b^{2}\nu_{t}^{2}$.
Hence, by (B.25), we have

$\sum_{t=1}^{T}{\mathbb{E}}[X_{t}^{2}|{\mathcal{F}}_{t-1}]\leq\tau_{0}^{2}b^{2}\sum_{t=1}^{T}\frac{w_{t}^{2}}{1+w_{t}^{2}}\leq\tau_{0}^{2}b^{2}\sum_{t=1}^{T}\min\\{1,w_{t}^{2}\\}\leq
2\kappa\tau_{0}^{2}b^{2}.$

On the other hand,

$\displaystyle\sum_{t=1}^{T}{\mathbb{E}}[Y_{t}|{\mathcal{F}}_{t-1}]$
$\displaystyle=\sum_{t=1}^{T}\frac{w_{t}^{2}}{1+w_{t}^{2}}{\mathbb{E}}\left[\frac{\tau_{t}^{2}(z_{t}^{*})^{2}}{\tau_{t}^{2}+(z_{t}^{*})^{2}}\bigg{|}{\mathcal{F}}_{t-1}\right]$
$\displaystyle\leq\sum_{t=1}^{T}\frac{w_{t}^{2}}{1+w_{t}^{2}}{\mathbb{E}}\left[(z_{t}^{*})^{2}|{\mathcal{F}}_{t-1}\right]\leq\sum_{t=1}^{T}\min\\{1,w_{t}^{2}\\}b^{2}\leq
2\kappa b^{2}.$

By Lemma F.1, it follows that with probability $1-\frac{\delta}{2T^{2}}$,

$\sum_{t=1}^{T}Y_{t}\leq\sum_{t=1}^{T}{\mathbb{E}}[Y_{t}|{\mathcal{F}}_{t-1}]+2\tau_{0}b\sqrt{\kappa\log\frac{2T^{2}}{\delta}}+\frac{2\tau_{0}^{2}}{3}\log\frac{2T^{2}}{\delta}$

for a given $T$ and $\tau_{0}$. Putting all pieces together, it follows that
with probability $1-\frac{\delta}{2T^{2}}$,

$\sum_{t=1}^{T}Y_{t}\leq\left[\sqrt{2\kappa}b+\tau_{0}\sqrt{\log\frac{2T^{2}}{\delta}}\right]^{2}.$

Finally, taking a union bound for the last inequality from $T=1$ to $\infty$
and using the fact that $\sum_{t=1}^{\infty}t^{-2}<2$ complete the proof.

∎

##  Appendix C Proof of Theorem 4.1

##### Measurability

Let ${\mathcal{F}}_{h,k}$ denote the $\sigma$-field generated by all random
variables up tp and including the $h$-th step and $k$-th episode. More
specifically, let $I_{h,k}=\\{(i,j):i\in[H],j\in[k-1]\ \text{or}\
i\in[h],j=k\\}$ denote the set of index pairs up to and including the $h$-th
step and $k$-th episode and then
${\mathcal{F}}_{h,k}=\sigma\left(\cup_{(i,j)\in
I_{h,k}}\left\\{s_{i,j},a_{i,j},r_{i,j}\right\\}\right).$ We make a convention
that ${\mathcal{F}}_{0,k}={\mathcal{F}}_{H,k-1}$. From our algorithm, we know
that (i) $Q_{h}^{k},V_{h}^{k},\pi_{h}^{k}\in{\mathcal{F}}_{H,k-1}$ for any
$Q\in\\{\overline{Q},\widehat{Q},\widecheck{Q},\underline{Q}\\}$ and
$V\in\\{\overline{V},\widehat{V},\widecheck{V},\underline{V}\\}$, and (ii)

${\bm{\mu}}_{h-1,k},{\bm{\theta}}_{h,k},{\bm{\psi}}_{h,k},\sigma_{h,k},U_{h,k},J_{h,k},E_{h,k},{\bm{\phi}}_{h,k},\widetilde{{\bm{\phi}}}_{h,k},w_{h,k},\widetilde{w}_{h,k},\tau_{h,k},\widetilde{\tau}_{h,k},{\bm{H}}_{h,k},\widetilde{{\bm{H}}}_{h,k}\in{\mathcal{F}}_{h,k}.$

###  C.1 High-Probability Events

Let $\kappa=d\log\left(1+\frac{K}{d\lambda\sigma_{\min}^{2}}\right)$. We first
introduce the following high-probability events.

  1. 1.

We define ${\mathcal{B}}_{R^{2}}$ as the event that the following inequalities
hold for all $h\in[H]$ and $k\in[K]\cup\\{0\\}$,

${\bm{\psi}}_{h}^{*}\in\widetilde{\mathcal{R}}_{h,k}:=\left\\{\|{\bm{\psi}}\|\leq
W:\|{\bm{\psi}}_{h,k}-{\bm{\psi}}\|_{\widetilde{{\bm{H}}}_{h,k}^{-1}}\leq\beta_{R^{2}}\right\\}$

where

$\beta_{R^{2}}=128\left(\frac{\sqrt{\kappa}\sigma_{R^{2}}}{\sigma_{\min}}+\sqrt{d}\right)\sqrt{\log\frac{2HK^{2}}{\delta}}+5\sqrt{\lambda}W.$

  2. 2.

We define ${\mathcal{B}}_{0}$ as the event that the following inequalities
hold for all $h\in[H]$ and $k\in[K]$,

$\displaystyle\max\left\\{\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\overline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}},\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})\underline{{\bm{V}}}_{h+1}^{k}\right\|_{{\bm{H}}_{h,k-1}}\right\\}\leq\beta_{0},$
$\displaystyle\left\|({\bm{\mu}}_{h}^{*}-{\bm{\mu}}_{h,k-1})[\overline{{\bm{V}}}_{h+1}^{k}]^{2}\right\|_{{\bm{H}}_{h,k-1}}\leq{\mathcal{H}}\beta_{0}$

where

$\displaystyle\beta_{0}=\frac{4{\mathcal{H}}}{\sigma_{\min}}\sqrt{d^{3}H\iota_{0}^{2}+\log\frac{2H}{\delta}}+3\sqrt{d\lambda}{\mathcal{H}}$
$\displaystyle\iota_{0}=\max\left\\{\log\left(1+\frac{8LK}{\lambda{\mathcal{H}}\sqrt{d}\sigma_{\min}^{2}}\right),\log\left(1+\frac{32B^{2}K^{2}}{\sqrt{d}\lambda^{3}{\mathcal{H}}^{2}\sigma_{\min}^{4}}\right),\log\left(1+\frac{K}{\lambda\sigma_{\min}^{2}}\right)\right\\}.$
(C.1)

Here we choose $B\geq 3(\beta_{R}+\beta_{V})$ and
$L=W+{\mathcal{H}}\sqrt{\frac{dK}{\lambda}}$.

  3. 3.

We define ${\mathcal{B}}_{R}$ as the event that the following inequalities
hold for all $h\in[H]$ and $k\in[K]\cup\\{0\\}$,

$\displaystyle{\bm{\theta}}_{h}^{*}\in{\mathcal{R}}_{h,k}:=\left\\{\|{\bm{\theta}}\|\leq
W:\|{\bm{\theta}}_{h,k}-{\bm{\theta}}_{h}^{*}\|_{{\bm{H}}_{h,k}}\leq\beta_{R}\right\\},$
$\displaystyle\left|[\widehat{\mathbb{V}}_{h}\widehat{R}_{h}-{\mathbb{V}}_{h}R_{h}](s_{h,k},a_{h,k})\right|\leq
R_{h,k}:=\beta_{R^{2}}\|\widetilde{{\bm{\phi}}}_{h,k}\|_{\widetilde{{\bm{H}}}_{h,k-1}^{k-1}}+2{\mathcal{H}}\beta_{R}\|{\bm{\phi}}_{h,k}\|_{{\bm{H}}_{h,k-1}^{-1}},$
(4.8)

where

$\displaystyle\beta_{R}=128(\sqrt{\kappa}+\sqrt{d})\sqrt{\log\frac{2HK^{2}}{\delta}}+5\sqrt{\lambda}W.$

  4. 4.

We define ${\mathcal{B}}_{h}$ as the event such that for all episode
$k\in[K]$, all stages $h\leq h^{\prime}\leq H$,

$\displaystyle\max\left\\{\left\|({\bm{\mu}}_{h^{\prime}}^{*}-{\bm{\mu}}_{h^{\prime},k-1})\overline{{\bm{V}}}_{h^{\prime}+1}^{k}\right\|_{{\bm{H}}_{h^{\prime},k-1}},\left\|({\bm{\mu}}_{h^{\prime}}^{*}-{\bm{\mu}}_{h^{\prime},k-1})\underline{{\bm{V}}}_{h^{\prime}+1}^{k}\right\|_{{\bm{H}}_{h^{\prime},k-1}}\right\\}\leq\beta_{V}$
(C.2)

where

$\displaystyle\beta_{V}={\mathcal{O}}\left(\sqrt{d}\iota_{1}^{2}+\sqrt{d\lambda}{\mathcal{H}}\right)$
$\displaystyle\iota_{1}=\max\left\\{\iota_{0},\log\frac{4HK^{2}}{\delta},\log\left(1+\frac{4L\sqrt{d^{3}H}}{\sigma_{\min}}\right),\log\left(1+\frac{8\sqrt{d^{7}}HB^{2}}{\lambda\sigma_{\min}^{2}}\right)\right\\}.$
(C.3)

For simplicity, we further define ${\mathcal{B}}_{V}:={\mathcal{B}}_{1}$.

Our ultimate goal is to show ${\mathcal{B}}_{V}$ holds with high probability,
a target used in previous work [Hu et al., 2022, He et al., 2022]. More
specifically, we first obtain coarse confidence sets for all parameters in the
sense that the confidence radius (that is $\beta_{R^{2}}$ and $\beta_{0}$) is