A crucial problem in reinforcement learning is learning the optimal policy. We study this in tabular infinite-horizon discounted Markov decision processes under the online setting. The existing algorithms either fail to achieve regret optimality or have to incur a high memory and computational cost. In addition, existing optimal algorithms all require a long burn-in time in order to achieve optimal sample efficiency, i.e., their optimality is not guaranteed unless sample size surpasses a high threshold. We address both open problems by introducing a model-free algorithm that employs variance reduction and a novel technique that switches the execution policy in a slow-yet-adaptive manner. This is the first regret-optimal model-free algorithm in the discounted setting, with the additional benefit of a low burn-in time.

§ INTRODUCTION

In reinforcement learning (RL), a crucial task is to find the optimal policy that maximizes its expected cumulative reward in any given environment with unknown dynamics. An immense body of literature is dedicated to finding algorithms that solve this task with as few samples as possible, which is the prime goal under this task. Ideally, one hopes to find an algorithm with a theoretical guarantee of optimal sample efficiency. At the same time, this task might be accompanied with additional requirements such as low space complexity and computational cost, as it is common that the state and action spaces exhibit high dimensions in modern applications. The combination of these various goals and requirements presents an important yet challenging problem in algorithm design.

The task of searching for optimal policy has been well-studied by existing work in the generative setting [35, 36, 24, 1]. This fundamental setting allows the freedom of querying samples at any state-action pair. In contrast, it is more realistic but difficult to consider the same task in the online setting, in which samples can only be collected along trajectories generated from executing a policy in the unknown Markov decision process (MDP). Solving this task with optimal sample efficiency requires a careful balance between exploration and exploitation, especially when coupled with other goals such as memory and computational efficiency.

MDPs can be divided into two types: the episodic finite-horizon MDPs and the infinite-horizon MDPs. Although these two types of MDPs can be approached in similar ways under the generative setting, there is a clear dichotomy between them in the online setting. In an episodic MDP, sample trajectories are only defined in fixed-length episodes, so samples are collected in episodes, and a reset to an arbitrary initial state occurs at the end of every online episode. Its transition kernel is usually assumed to be non-stationary over time. In contrast, the transition kernel of an infinite-horizon MDP stays stationary over time, and the online sample collection process amounts to drawing a single infinitely long sample trajectory with no reset. These differences render most optimal algorithms for episodic MDPs suboptimal when applied to infinite-horizon MDPs. Without reset and non-stationarity, the high dependency between consecutive trajectory steps in the infinite-horizon setting presents a new challenge over the episodic setting. In this work, we consider the infinite-horizon discounted MDPs, which is widely used in practice but still has some fundamental questions unanswered in theory.

§.§ Sample Efficiency in Infinite-Horizon MDPs

To evaluate the sample efficiency of online RL algorithms, a natural and widely-accepted metric is the cumulative regret. It captures the performance difference between the optimal policy and the learned policy of an algorithm over its online interactions with a given MDP. The notion of cumulative regret was first introduced in the bandit literature and later adopted in the RL literature [3, 16]. It is profusely used in the online episodic RL literature. Such works aim to prove regret guarantees for algorithms and provide analyses that characterize such regret guarantees in terms of all problem parameters such as state space, action space and sample size in a non-asymptotic fashion. A cumulative regret guarantee can also suggest the sample complexity needed to reach a certain level of average regret.

In the online infinite-horizon setting, many works study a different metric called the sample complexity of exploration, first introduced in 18. In essence, given a target accuracy level $\epsilon$, this metric characterizes the total number of $\epsilon$-suboptimal steps committed by an algorithm over an infinitely-long trajectory in the MDP. While this is indicative of the sample efficiency of an algorithm, the focus of this metric is very different from that of cumulative regret, as it only reflects the total number of failures but does not distinguish their sizes. As 26, 14 point out, even an optimal guarantee on the sample complexity of exploration can only be converted to a very suboptimal guarantee on the cumulative regret. To obtain a more quantitative characterization of the total volume of failures in the regime of finite samples, some works have turned to studying cumulative regret guarantees for algorithms.

It was not until recently that some works [26, 57, 14, 19] begin to research into the problem of cumulative regret minimization in infinite-horizon discounted MDPs. Among them, 57 focus on linear MDPs while others study tabular MDPs. In this work, we study the regret minimization problem in the tabular case. Hereafter and throughout, we denote the size of the state space, the size of the action space and the discount factor of the problem MDP with $S$, $A$ and $\gamma$, respectively, and let $T$ denote the sample size.

§.§ Model-Based and Model-Free Methods

Since modern RL applications are often large-scale, algorithms with low space complexity and computational complexity are much desired. This renders the distinction between model-based algorithms and model-free algorithms particularly important. The procedure of a model-based method includes a model estimation stage that involves estimating the transition kernel and a subsequent planning stage that searches the optimal policy in the learned model. Thus, $O(S^2A)$ space is required to store the estimated model. This is unfavorable when the state space is large and a memory constraint is present. Additionally, updating the transition kernel estimate brings a large computational burden. In comparison, model-free methods do not learn the entire model and thus can run with $o(S^2A)$ space. Notably, most value-based methods such as Q-learning only require storage of an estimated Q-function, which can take as little as $O(SA)$ memory. In the infinite-horizon discounted setting, although UCBVI-$\gamma$ in 14 can achieve optimal regret, its model-based nature exacts a $O(S^2A)$ memory and computational cost; conversely, the algorithms in 26 and 19 are model-free but have suboptimal regret guarantee.

Algorithm     Sample complexity
of exploration     Cumulative
Regret     Range of $T$
with optimality     Space

Delayed Q-learning     2*$\frac{SA}{(1-\gamma)^8 \epsilon^4}$     2*$\frac{S^{\frac{1}{5}}A^{\frac{1}{5}}T^{\frac{4}{5}}}{(1-\gamma)^{\frac{9}{5}}}$     2*never     2*$SA$

[38]

R-Max     2*$\frac{S^2A}{(1-\gamma)^6 \epsilon^3}$     2*$\frac{S^{\frac{1}{2}}A^{\frac{1}{4}}T^{\frac{3}{4}}}{(1-\gamma)^{\frac{7}{4}}}$     2*never     2*$S^2A$

[8]

UCB-Q     2*$\frac{SA}{(1-\gamma)^7 \epsilon^2}$     2*$\frac{S^{\frac{1}{3}}A^{\frac{1}{3}}T^{\frac{2}{3}}}{(1-\gamma)^{\frac{8}{3}}}$     2*never     2*$SA$

[9]

MoRmax     2*$\frac{SA}{(1-\gamma)^6 \epsilon^2}$     2*$\frac{S^{\frac{1}{3}}A^{\frac{1}{3}}T^{\frac{2}{3}}}{(1-\gamma)^{\frac{7}{3}}}$     2*never     2*$S^2A$

[39]

UCRL     2*$\frac{S^2A}{(1-\gamma)^3 \epsilon^2}$     2*$\frac{S^{\frac{2}{3}}A^{\frac{1}{3}}T^{\frac{2}{3}}}{(1-\gamma)^{\frac{4}{3}}}$     2*never     2*$S^2A$

[21]

UCB-multistage     2*$\frac{SA}{(1-\gamma)^{\frac{11}{2}} \epsilon^2}$     2*$\frac{S^{\frac{1}{3}}A^{\frac{1}{3}}T^{\frac{2}{3}}}{(1-\gamma)^{\frac{13}{6}}}$     2*never     2*$SA$

[56]

UCB-multistage-adv     2*$\frac{SA}{(1-\gamma)^3 \epsilon^2}$     2*$\frac{S^{\frac{1}{3}}A^{\frac{1}{3}}T^{\frac{2}{3}}}{(1-\gamma)^{\frac{4}{3}}}$     2*never     2*$SA$

[56]

MAIN     2*N/A     2*$\kappa\sqrt{\frac{(S^4+S^2A^2)T}{(1-\gamma)^8}}$     2*never     2*$SA$

[19]

Double Q-learning     2*N/A     2*$\sqrt{\frac{SAT}{(1-\gamma)^5}}$     2*never     2*$SA$

[26]

UCBVI-$\gamma$     2*N/A     2*$\sqrt{\frac{SAT}{(1-\gamma)^3}}$     2*$\Big[\frac{S^3A^2}{(1-\gamma)^4}, \infty\Big)$ $^\dagger$     2*$S^2A$

[14]

2*N/A     2*$\sqrt{\frac{SAT}{(1-\gamma)^3}}$     2*$\Big[\frac{SA}{(1-\gamma)^{13}}, \infty\Big)$     2*$SA$

(This work)

Lower bound     3*$\frac{SA}{(1-\gamma)^3 \epsilon^2}$     3*$\sqrt{\frac{SAT}{(1-\gamma)^3}}$     3*N/A     3*N/A

A comparison between our results and existing work in the online infinite-horizon discounted setting. Logarithmic factors are omitted for clearer presentation. The second column shows the sample complexity when the target accuracy $\epsilon$ is sufficiently small. The third column shows the regret when sample size $T$ is sufficiently large (beyond the burn-in period). The algorithms in the first seven rows only have sample complexity results in their original works; their regret bounds are derived from their respective sample complexity bounds and presented in this table for completeness. Details about the conversions can be found in 14. Note that UCB-multistage-adv achieves optimal sample complexity only in the high-accuracy regime when $\epsilon \le S^{-2}A^{-2}(1-\gamma)^{14}$. This is similar to a burn-in threshold in that the optimal guarantee cannot be achieved unless in a specific range. The fourth column lists the sample size range in which regret optimality can be attained, which shows the burn-in time. We would like to point out that the results in 14, 26 are under slightly different regret definitions from the regret definition in 19 and this work. In fact, their regret metric can be more lenient, and our algorithm can also achieve $\widetilde{O}(\sqrt{\frac{SAT}{(1-\gamma)^3}})$ optimal regret under it. This is further discussed in Remark <ref> and Appendix <ref>. Lastly, note that 19 assume an ergodicity parameter $\kappa$. $^\dagger$ UCBVI-$\gamma$ achieves optimal regret for $T \ge \frac{S^3A^2}{(1-\gamma)^4}$ only if the MDP satisfies $SA \ge \frac{1}{1-\gamma}$.

§.§ Burn-in Cost in Regret-Optimal RL

Naturally, one aims to develop algorithms that find the optimal policy with the fewest number of samples. In regards to regret, this motivates numerous works to work towards algorithms with minimax-optimal cumulative regret. However, the job is not done once such an algorithm is found. As can be seen in the episodic RL literature, algorithms that achieve optimal regret as sample size $T$ tends towards infinity can still have different performance in the regime when $T$ is limited. Specifically, for every existing algorithm, there exists a certain sample size threshold such that regret is suboptimal before $T$ exceeds it. Such threshold is commonly referred to as the initial burn-in time of the algorithm. Therefore, it is of great interest to find an algorithm with low burn-in time so that it can still attain optimal regret in the sample-starved regime. Such effort has been made by 24, 1 in the generative setting and by 23, 28 in the online episodic setting. Yet, this important issue has not been addressed in the infinite-horizon setting, as optimal algorithms all suffer long burn-in times.

Specifically, while UCBVI-$\gamma$ in 14 achieves a state-of-the-art regret guarantee of $\widetilde{O}\Big(\sqrt{\frac{SAT}{(1-\gamma)^3}}\Big)$, which they prove minimax-optimal, their theory does not guarantee optimality unless the samples size $T$ becomes as large as

\begin{equation*}
T \ge \frac{S^3A^2}{(1-\gamma)^4}.
\end{equation*}

This threshold can be prohibitively large when $S$ and $A$ are huge, which is true in most applications. For instance, a 5-by-5 tic-tac-toe has a state space of size $3^{25}$. While this is a manageable number in modern machine learning, any higher power of it may cause computational difficulties; in contrast, the horizon of this game is much smaller—no more than $25$. The issue exacerbates in more complex applications such as the game of Go [37]; thus, reducing the $S$ and $A$ factors in the burn-in cost is particularly important. Since no lower bound precludes regret optimality for $T \ge \frac{SA}{(1-\gamma)^4}$, one might hope to design an algorithm with smaller $S$ and $A$ factors in the burn-in cost so that it can achieve optimality even in the sample-starved regime.

§.§ Summary of Contributions

While it is encouraging to see recent works have shown that in the discounted setting, model-free methods can provide nearly optimal guarantees on sample complexity of exploration and that model-based methods can provide nearly optimal finite-sample regret guarantees, there still lacks a model-free approach that can attain regret optimality. In the orthogonal direction, there is still a vacancy for algorithms that can attain optimal regret for a broader sample size range, i.e., with fewer samples than $\frac{S^3A^2}{\poly(1-\gamma)}$.

In fact, we can summarize these two lingering theoretical questions as follows:

Is there an algorithm that can achieve minimax regret optimality with low space complexity and computational complexity in the infinite-horizon discounted setting, even when sample size is limited?

We answer this question affirmatively with a new algorithm , which uses variance reduction and a novel adaptive switching technique. It is the first model-free algorithm that achieves optimal regret in the infinite-horizon discounted setting. This result can be summarized as follows:

For any sample size $T \ge \frac{SA}{\poly(1-\gamma)}$, is guaranteed to achieve near-optimal cumulative regret $\widetilde{O}\left(\sqrt{\frac{SAT}{(1-\gamma)^3}}\right)$ with space complexity $O(SA)$ and computational complexity $O(T)$.

A formal theorem is presented in Section <ref>. We also provide a complete summary of related prior results in Table <ref>.

§.§ Related work

Now, let us take a moment to discuss the related work beyond those in Table <ref>.

Regret analysis for online episodic RL In the online episodic setting, regret is the predominant choice of metric for demonstrating the sample efficiency of a method [51, 30, 15]. 4 was the first to introduce a model-based method that can achieve near-optimal regret guarantee, but the model-based nature of their method induces a high space complexity and burn-in time. On the other hand, model-free methods are proposed in 16, 6, which are motivated by Q-learning and thus enjoy a low space complexity. However, these methods cannot guarantee optimal regret. It was not until 55 that proposed the first model-free method with optimal regret guarantee UCB-Q-Advantage, but it incurs a large burn-in time of $S^6A^4H^{28}$, where $H$ is the horizon of the episodic MDP. In addition, 28 proposed UCB-M-Q, a Q-learning variant with momentum, which can achieve optimal regret with low burn-in time, but it requires the storage of all momentum bias and thus incurs high memory cost. Recently, 23 propose a Q-learning variant with variance reduction that achieves optimal regret with $O(SAH)$ space complexity and $SA\poly(H)$ burn-in threshold at the same time. Table 1 in 23 provides a more detailed comparison of related work from the online episodic RL literature.

Sample complexity for infinite-horizon RL In the infinite-horizon setting, there exist other sample efficiency metrics besides sample complexity of exploration. Initially, 20 considered the sample complexity needed to find an $\epsilon$-approximate optimal policy. The same definition is also considered in 44, 36, 35, 24. Later, 43 studied the sample complexity needed to find an $\epsilon$-approximate optimal Q-function. Note that all of these works assume the generative setting. Indeed, a limitation of these aforementioned sample complexity definitions is that they only measure the performance of the final output policy and do not reflect the online regret during learning. Thus, existing works that study the online setting consider sample complexity of exploration and cumulative regret instead.

Variance reduction in RL The idea of variance reduction was first introduced to accelerate stochastic finite-sum optimization by 17, which is followed by a rich literature [48, 29, 13]. Later, for better sample efficiency in RL, it is applied to policy gradient methods [27, 53, 31] as well as value-based methods in various problems including generative setting RL [35, 36, 43], policy evaluation [10, 49], asynchronous Q-learning [25, 50] and offline RL [52, 34].

Low-switching algorithms Since our algorithm includes a novel feature that switches the execution policy slowly, we make a review of the low-switching approaches in RL. The idea of changing the execution policy infrequently during learning was first introduced by 2 as an approach to minimize regret in the multi-armed bandit problem. 6 adapted this idea to tabular RL and formalized the switching cost as a secondary metric that an algorithm can minimize. To reduce the number of policy switches and thus the switching cost, their algorithm updates the policy in geometrically longer intervals. Similar techniques can be found in 55, whose algorithm can achieve regret optimality while maintaining low switching cost. Later, 12, 45 introduced a new low-switching approach in linear MDPs by switching policies when the estimated covariance matrix gets a significant update. All these methods guarantee a $O(\log T)$ switching cost. The switching cost guarantee was later improved to $O(\log\log T)$ by the algorithms proposed in 33, 54.

§ PROBLEM FORMULATION

Let us specify the problem we aim to study in this section. Throughout this paper, we let $\Delta(\cX)$ denote the probability simplex over any set $\cX$. We also introduce the notation $[m] := \{1,2,\cdots, m\}$ for a positive integer $m$.

§.§ Infinite-Horizon Discounted Markov Decision Process

We consider an infinite-horizon discounted Markov decision process (MDP) represented with $(\cS, \cA, \gamma, P, r)$. Notably, we consider a tabular one, in which $\cS := \{1, 2, \cdots, S\}$ denotes the state space with size $S$ and $\cA := \{1, 2, \cdots, A\}$ denotes the action space with size $A$. $P:\cS\times \cA \to \Delta(\cS)$ denotes the probability transition kernel in that $P(\cdot | s,a) \in \Delta(\cS)$ is the transition probability vector from state $s \in \cS$ when action $a \in \cA$ is taken. $r: \cS \times \cA \to [0,1]$ denotes the reward function, which is assumed to be deterministic in this work. Specifically, $r(s,a)$ is the immediate reward for taking action $a\in \cA$ at state $s \in \cS$. Lastly, $\gamma$ denotes the discount factor for the reward, which makes $\frac{1}{1-\gamma}$ the effective horizon.

A (stationary) policy $\pi: \cS\to\Delta(\cA)$ specifies a rule for action selection in that $\pi(\cdot | s) \in \Delta(\cA)$ is the action selection probability vector at state $s \in \cS$. We overload this notation by letting $\pi(s)$ denote the action policy $\pi$ takes at state $s$. Given a policy $\pi$, the Q-function of $\pi$ is defined as

\begin{align*}
Q^\pi(s,a) := \EE\left[\sum_{t=0}^{\infty} \gamma^t r(s_{t}, a_{t}) ~\Big|~ s_0 = s, a_0 = a\right],
\end{align*}

in which $s_{t+1}\sim P(\cdot | s_{t},a_{t})$ for $t \ge 0$ and $a_{t}\sim\pi(\cdot | s_t)$ for $t \ge 1$. Moreover, the value function of $\pi$ is defined as

\begin{align*}
V^\pi(s) := \EE\left[\sum_{t=0}^{\infty} \gamma^t r(s_{t}, a_{t}) ~\Big|~ s_0 = s\right],
\end{align*}

in which $s_{t+1}\sim P(\cdot | s_{t},a_{t})$ and $a_{t}\sim\pi(\cdot | s_t)$ for $t \ge 0$. The Q-function and value function satisfy an equation, called the Bellman equation [7]:

\begin{equation}\label{eq:bellman}
Q^\pi(s,a) = r(s,a) + \gamma \EE_{s'\sim P(\cdot|s,a)}\left[V^\pi(s')\right].
\end{equation}

A policy $\pi^\star$ is called an optimal policy if it maximizes the value function for all states simultaneously. The optimal value function and optimal Q-function can be defined as

\begin{align*}
V^\star(s) &:= \max_{\pi} V^\pi(s) = V^{\pi^\star}(s) \\
Q^\star(s,a) &:= \max_{\pi} Q^\pi(s,a) = Q^{\pi^\star}(s,a),
\end{align*}

which satisfy

\begin{align*}
V^\star(s) = V^{\pi^\star}(s) \quad \text{and} \quad
Q^\star(s,a) = Q^{\pi^\star}(s,a)
\end{align*}

for any optimal policy $\pi^\star$. The optimal policy always exists and satisfies the Bellman optimality equation [32]:

\begin{align}\label{eq:bellman-opt}
Q^{\pi^\star}(s,a) &= r(s,a) + \gamma \EE_{s'\sim P(\cdot|s,a)}\left[\max_{a'\in\cA}Q^{\pi^\star}(s',a')\right] \notag\\
&= r(s,a) + \gamma \EE_{s'\sim P(\cdot|s,a)}\left[V^{\star}(s')\right].
\end{align}

§.§ Online Learning in an Infinite-Horizon MDP

We consider the online (single-trajectory) setting, in which the agent is permitted to execute a total of $T$ steps sequentially in the MDP. More specifically, the agent starts from an arbitrary (and possibly adversarial) initial state $s_1$. At each step $t \in [T]$, the agent at state $s_t$ computes policy $\pi_t$, takes action $a_t$ based on $\pi_t(\cdot|s_t)$, receives reward $r(s_t,a_t)$, and transitions to state $s_{t+1}$ in the following step. At the end of execution, the agent generates a trajectory $(s_1,a_1,r_1, s_2,a_2,r_2, \cdots,s_T,a_T,r_T)$, which amounts to $T$ samples.

§.§ Problem: Regret Minimization

As a standard metric to evaluate the performance of the aforementioned agent over a finite number of $T$ steps, the cumulative regret with respect to the sequence of stationary policies $\{\pi_t\}_{t=1}^T$ learned by the algorithm is defined as follows:

\begin{equation}\label{eq:regret}
\Regret(T) := \sum_{t=1}^T \Big( V^\star(s_t) - V^{\pi_t}(s_t)\Big).
\end{equation}

Verbally, the regret measures the cumulative suboptimality between the optimal policy and each learned policy $\pi_t$ throughout the $T$-step online interaction process. Naturally, one aims to minimize this regret by finding an algorithm whose regret scales optimally in $T$. This would require a strategic balance between exploration and exploitation, which can be difficult when sample size $T$ is small.

In the infinite-horizon setting, many prior works [14, 26] consider slightly different regret definitions with respect to non-stationary policies. Specifically, at each $s_t$ along the trajectory, this different regret metric compares the optimal value function $V^{\star}(s_t)$ against the expected cumulative reward of running the non-stationary policy $\{\pi_k\}_{k=t}^\infty$ starting from $s_t$. By doing this, it is effectively evaluating the cumulative reward difference between the stationary optimal policy and a non-stationary algorithm. While there exists no formal conversion between the regret defined in this way and the one in (<ref>), it is expected to be smaller and thus more easily controlled than (<ref>), because the execution policy $\pi_t$ improves over time. In addition, we can show our algorithm also achieves the same level of regret under this different definition with an analysis specifically tailored to our algorithm, which is deferred to Appendix <ref>. Furthermore, since the transition kernel in the infinite-horizon setting is invariant over time and the optimal policy itself is also stationary, it is more natural to compare the optimal policy to a stationary policy, e.g., the policy $\pi_t$ deployed by the algorithm at each step, as in (<ref>). Before this work, this has also been recently studied in 56, 19.

Notation. Given any vector $x\in\RR^{SA}$ that represents a function $x:\cS\times\cA\to\RR$, we use $x(s,a)$ to denote the entry corresponding to the state-action pair $(s,a)$. We also denote the probability transition vector at $(s,a)$ with

\begin{equation}\label{eq:P-def}
P_{s,a} = P(\cdot~|~s,a)\in \RR^{1\times S},
\end{equation}

that is, given any $V\in \RR^S$, $P_{s,a}V = \EE_{s'\sim P(\cdot|s,a)}[V(s')]$. For two vectors $x,y\in\RR^{SA}$, we override the notation $x \le y$ to mean that $x(s,a) \le y(s,a)$ in every dimension $(s,a)$.

§ ALGORITHM

In this section, we present our algorithm and some relevant discussion.

§.§ Review: Q-Learning with UCB and reference advantage

First, we make a brief review of the Q-learning with UCB method proposed in 16, referred to as UCB-Q hereafter, and its variance-reduced variant UCB-Q-Advantage, later introduced in 55. The Q-function updates in are inspired by these two methods.

Q-learning with UCB

The original Q-learning [47, 46] is a fixed-point iteration based on a stochastic approximation of the Bellman optimality equation (<ref>). It uses a greedy policy with respect to its estimate of $Q^\star$, whose update rule can be summarized as:

\begin{equation}
Q(s, a) \leftarrow (1 - \eta)Q(s, a) + \eta\left(r(s, a) + \gamma\widehat{P}_{s,a} V\right). \label{eq:Q-update}
\end{equation}

Above, $Q$ (resp. $V$) is the running estimate of $Q^\star$ (resp. $V^\star$); $\eta \in (0,1]$ is the (possibly varying) learning rate; $\widehat{P}_{s,a} V$ is a stochastic approximation of $P_{s,a} V$ (cf. (<ref>)). Commonly, $V(s')$ is used for $\widehat{P}_{s,a} V$ in (<ref>) as an unbiased estimate of $P_{s,a} V$, when a sample of state transition from $(s,a)$, namely $(s,a,s')$, is available.

However, as 16 point out, using (<ref>) naïvely suffers from great regret suboptimality, for it rules out the state-action pairs with high value but few observations. To promote the exploration of such state-action pairs, UCB-Q appends (<ref>) with an exploration bonus. Its update rule can be written as:

\begin{align}
Q^\UCB(s, a) &\leftarrow (1 - \eta)Q^\UCB(s, a) + \eta\Big(r(s, a) + \gamma\widehat{P}_{s,a} V + b\Big). \label{eq:UCB-Q-update}
\end{align}

To encourage exploration, the bonus $b \ge 0$ is designed to maintain an upper confidence bound (UCB) on $(\widehat{P}_{s,a} - P_{s,a}) V$, which in turn keeps $Q^\UCB(s, a)$ as an “optimistic” overestimate of $Q^\star(s,a)$.

Q-learning with UCB and reference advantage

The regret guarantee for UCB-Q is still shy of being optimal. In order to attain optimality, one can turn to the celebrated idea of variance reduction [17, 23, 36, 43], which decomposes the stochastic approximation target into two parts: a low-variance reference estimated with batches of samples and a low-magnitude advantage estimated with every new sample. In this spirit, 55 introduce UCB-Q-Advantage based on UCB-Q and a reference-advantage decomposition. Specifically, given a reference $V^\rref$ that is maintained as an approximation for $V^\star$, the update rule of UCB-Q-Advantage reads:

\begin{align}
Q^\rref(s, a) &\leftarrow (1 - \eta)Q^\rref(s, a) + \eta\Big(r(s, a) + \gamma\big(\widehat{P}_{s,a} \left(V - V^\rref \right) + \widehat{PV^\rref}(s,a)\big)  + b^{\rref}\Big). \label{eq:UCB-Q-Adv-update}
\end{align}

Let us discuss the update rule (<ref>) in more details:

* Given a transition sample $(s,a,s')$, we can take $V(s') - V^\rref(s')$ as an unbiased estimate of the advantage $P_{s,a} (V - V^\rref )$. Note that the magnitude of $V - V^\rref$ is small when $V$ and $V^\rref$ are close. This engenders smaller stochastic volatility, compared to $\widehat{P}_{s,a} V$ in (<ref>) from UCB-Q.

* The reference estimate $\widehat{PV^\rref}$ is a stochastic approximation of $PV^\rref$. In our algorithm, the auxiliary estimate $\mu^\re$ (cf. Line <ref> of Algorithm <ref>) is used as the estimate for $PV^\rref$. Specifically, $\mu^\re(s,a)$ is a running mean of $P_{s,a}V^\rref$ based on the samples from all past visitations of $(s,a)$. In contrast to the advantage, which is computed every time a new sample arrives, the reference is computed with a batch of samples and thus more stable. In sacrifice, the reference is only updated intermittently and not as up-to-date as the advantage.

The exploration bonus $b^{\rref}$ is computed from the auxiliary estimates in Line <ref> and <ref> to serve as an upper confidence bound on the aggregation of the aforementioned reference and advantage. Specifically, for each $(s,a)$, $\mu^\re(s,a)$ and $\sigma^\re(s,a)$ are the running mean and $2$nd moment of the reference $[PV^\rref](s,a)$ respectively; $\mu^\adv(s,a)$ and $\sigma^\adv(s,a)$ are the running mean and $2$nd moment of the advantage $[P(V - V^\rref)](s,a)$ respectively; $B^\rref(s,a)$ combines the empirical standard deviations of the reference and the advantage; $\delta^\rref(s,a)$ is the temporal difference between $B^\rref(s,a)$ and its previous value. $b^{\rref}(s,a)$ can be computed from these estimates as a temporally-weighted average of $B^\rref(s,a)$. Thanks to the low variability of the reference $PV^\rref$, we can obtain a more accurate, milder overestimation in the upper confidence bound for faster overall convergence.

Initialize: $\forall (s,a)$, $\Qlazy(s,a),Q(s,a),Q^\UCB(s,a),Q^\rref(s,a), \QM(s,a) \leftarrow \frac{1}{1-\gamma}$; $N(s,a) \leftarrow 0$; $V(s), V^{\rref}(s) \leftarrow \frac{1}{1-\gamma}$; $Q^{\mathrm{LCB}}(s,a), \qdiff(s,a) \leftarrow 0$; $\qset \leftarrow \dict()$; $\mu^{\re}(s,a), \sigma^{\re}(s,a), \mu^{\adv}(s,a), \sigma^{\adv}(s,a), B^{\rref}(s,a),$ $\delta^{\rref}(s,a) \leftarrow 0$; $u^{\mathrm{switch}} \leftarrow \mathrm{False}$; $u^{\re}(s) \leftarrow \mathrm{True}$; $H = \lceil\frac{2}{1-\gamma} \rceil$; $\iota = \log\frac{SAT}{\delta}$.

$t = 1, \cdots, T$
Take action $a_t = \pi_{t}(s_t) = \arg \max_a Q^{\mathrm{lazy}}(s_t, a)$, and draw $s_{t+1} \sim P(\cdot | s_t, a_t)$;

$N(s_t, a_t) \leftarrow N(s_t, a_t) + 1$; $n \leftarrow N(s_t, a_t)$;   # Update the counter

$\eta_n \leftarrow \frac{H+1}{H+n}$;   # Update the learning rate

$Q^{\mathrm{UCB}}(s_t, a_t) \leftarrow \textbf{update-q-ucb}()$;   # Compute the UCB. See Algorithm <ref>

$Q^{\mathrm{LCB}}(s_t, a_t) \leftarrow \textbf{update-q-lcb}()$;   # Compute the LCB. See Algorithm <ref>

$Q^{\mathrm{R}}(s_t, a_t) \leftarrow \textbf{update-q-reference}()$;   # Compute the reference value. See Algorithm <ref>

$Q(s_t, a_t) \leftarrow \min \{Q^{\mathrm{R}}(s_t, a_t), Q^{\mathrm{UCB}}(s_t, a_t), Q(s_t, a_t)\}$;

$V(s_t) \leftarrow \max_a Q(s_t, a)$;

$V^{\mathrm{LCB}}(s_t) \leftarrow \max\{\max_a Q^{\mathrm{LCB}}(s_t, a), V^{\mathrm{LCB}}(s_t)\}$;

$\qdiff(s_t,a_t) \leftarrow \qdiff(s_t,a_t) + \QM(s_t, a_t) - Q(s_t, a_t)$.   # Track the staleness of current policy

$u^{\mathrm{switch}} = \mathrm{True}$
$\Qlazy \leftarrow \textbf{update-q-lazy}()$;   # Update execution policy's Q-function (switch policy)

$\qset \leftarrow \dict()$;   # Reset the buffer

$u^{\mathrm{switch}} \leftarrow \mathrm{False}$;

$\qset[(s_t, a_t)] \leftarrow Q(s_t, a_t)$.   # Add the new transition and $Q$ entry to the buffer

"""Switch policy when the staleness tracker is large"""

$\qdiff(s_t,a_t) > \frac{1}{1-\gamma}$
$\QM(s_t, a_t) \leftarrow Q(s_t,a_t)$;   # Save the current $Q$ entry for staleness determination later

$u^{\mathrm{switch}} \leftarrow \mathrm{True}$;   # Signal to switch policy at the following step

$\qdiff(s_t,a_t) \leftarrow 0$;   # Reset the staleness tracker

$V(s_{t}) - V^{\mathrm{LCB}}(s_{t}) > 3$
$V^{\mathrm{R}}(s_{t}) \leftarrow V(s_{t})$, $u^{\mathrm{ref}}(s_{t}) = \mathrm{True}$;

$u^{\mathrm{ref}}(s_{t}) = \mathrm{True}$
$V^{\mathrm{R}}(s_{t}) \leftarrow V(s_{t})$, $u^{\mathrm{ref}}(s_{t}) = \mathrm{False}$.    # Update the reference only on certain conditions

Auxiliary functions

$Q^{\mathrm{UCB}}(s_t, a_t) \leftarrow (1 - \eta_n)Q^{\mathrm{UCB}}(s_t, a_t) + \eta_n\Big(r(s_t, a_t) + \gamma V(s_{t+1}) + c_b\sqrt{\frac{\iota}{(1-\gamma)^3n}}\Big).$

$Q^{\mathrm{LCB}}(s_t, a_t) \leftarrow (1 - \eta_n)Q^{\mathrm{LCB}}(s_t, a_t) + \eta_n\Big(r(s_t, a_t) + \gamma V^{\mathrm{LCB}}(s_{t+1}) - c_b\sqrt{\frac{\iota}{(1-\gamma)^3n}}\Big).$

for every $((s,a), q) \in \qset$ do $\Qlazy(s,a) \leftarrow q$.   # Update execution policy with the buffer

$[\mu^{\mathrm{ref}}, \sigma^{\mathrm{ref}}](s_t, a_t) \leftarrow \textbf{update-moments}()$;

$[\delta^{\mathrm{R}}, B^{\mathrm{R}}](s_t, a_t) \leftarrow \textbf{update-reference-bonus}()$;

$b^{\mathrm{R}} \leftarrow B^{\mathrm{R}}(s_t, a_t) + (1 - \eta_n)\frac{\delta^{\mathrm{R}}(s_t, a_t)}{\eta_n} + c_b\frac{\iota^2}{n^{3/4}(1-\gamma)^2}$;

$Q^{\mathrm{R}}(s_t, a_t) \leftarrow (1 - \eta_n)Q^{\mathrm{R}}(s_t, a_t) + \eta_n\left(r(s_t, a_t) + \gamma \left(V(s_{t+1}) - V^{\mathrm{R}}(s_{t+1}) + \mu^{\mathrm{ref}}(s_t, a_t)\right) + b^{\mathrm{R}}\right)$.

$\mu^{\mathrm{ref}}(s_t, a_t) \leftarrow (1 - \frac{1}{n})\mu^{\mathrm{ref}}(s_t, a_t) + \frac{1}{n}V^{\mathrm{R}}(s_{t+1})$;   # Running average of the reference

$\sigma^{\mathrm{ref}}(s_t, a_t) \leftarrow (1 - \frac{1}{n})\sigma^{\mathrm{ref}}(s_t, a_t) + \frac{1}{n}\left(V^{\mathrm{R}}(s_{t+1})\right)^2$;   # Running $2^{\text{nd}}$ moment of the reference

$\mu^{\mathrm{adv}}(s_t, a_t) \leftarrow (1 - \eta_n)\mu^{\mathrm{adv}}(s_t, a_t) + \eta_n \left(V(s_{t+1}) - V^{\mathrm{R}}(s_{t+1})\right)$;   # Running average of the advantage

$\sigma^{\mathrm{adv}}(s_t, a_t) \leftarrow (1 - \eta_n)\sigma^{\mathrm{adv}}(s_t, a_t) + \eta_n \left(V(s_{t+1}) - V^{\mathrm{R}}(s_{t+1})\right)^2$. # Running $2^{\text{nd}}$ moment of the advantage

$B^{\mathrm{next}}(s_t, a_t) \leftarrow c_b\sqrt{\frac{\iota}{n}}\left(\sqrt{\sigma^{\mathrm{ref}}(s_t, a_t) - \left(\mu^{\mathrm{ref}}(s_t, a_t)\right)^2} + \frac{1}{\sqrt{1-\gamma}}\sqrt{\sigma^{\mathrm{adv}}(s_t, a_t) - \left(\mu^{\mathrm{adv}}(s_t, a_t)\right)^2}\right)$;

$\delta^{\mathrm{R}}(s_t, a_t) \leftarrow B^{\mathrm{next}}(s_t, a_t) - B^{\mathrm{R}}(s_t, a_t)$;

$B^{\mathrm{R}}(s_t, a_t) \leftarrow B^{\mathrm{next}}(s_t, a_t)$.

§.§ Review: Early settlement of reference value

Given the optimistic overestimates $Q^\UCB$ and $Q^\rref$, it is natural to design an update rule of our Q-function estimate as the minimum of the estimate itself and these two overestimates (Line <ref> of Algorithm <ref>). This makes our Q-function estimate monotonically decrease without violating the optimistic principle $Q \ge Q^\star$, which effectively enables us to lessen the overestimation in $Q$ over time until it converges to $Q^\star$. In fact, this is precisely the update rule in UCB-Q-Advantage [55]. Nevertheless, we need to equip our algorithm with additional features to strive for regret optimality.

23 introduced a way to update the reference with higher sample efficiency in the finite-horizon setting. As they noted, it is critical to update the reference $V^\rref$ in a smart fashion so as to balance the tradeoff between its synchronization with $V$ and the volatility that results from too many stochastic updates. Concretely, the reference $V^\rref$ needs to be updated in a timely manner from $V$ so that the magnitude of $\widehat{P}_{s,a} (V - V^\rref )$ can be kept low as desired, but the updates cannot be too frequent either, because the stochasticity or variance in $\widehat{PV^\rref}(s,a)$ could be as high as that in $\widehat{P}_{s,a} V$ of (<ref>) and thus lead to suboptimality if it is not carefully controlled. To resolve this dilemma, we can update $V^\rref$ until it becomes sufficiently close to $V^\star$ and fix its value thereafter.

To this end, we maintain a “pessimistic” underestimate $Q^\LCB$ (resp. $V^\LCB$) of $Q^\star$ (resp. $V^\star$) in the algorithm, which are computed from the lower confidence bound for $Q^\star$ (resp. $V^\star$). This can provide us with an upper bound on $V^\rref - V^\star$, which will be used to determine when the update of the reference $V^\rref$ should be stopped.

In particular, the if-else block in Line <ref> to <ref> is designed to keep the reference $V^\rref$ synchronized with $V$ for each state $s$ respectively and terminate the update once

\begin{equation}
V(s) \le V^\LCB + 3 \le V^\star + 3.
\end{equation}

This can guarantee $|V - V^\rref| \le 6$ throughout the execution of the algorithm. As a result, the standard deviation of $\widehat{P}_{s,a} (V - V^\rref )$ is guaranteed to be $O(1)$, which can be $O(\frac{1}{1-\gamma})$ times smaller than the standard deviation of $\widehat{P}_{s,a} V$ in (<ref>). This can lead to smaller $\frac{1}{1-\gamma}$ factor in the final regret guarantee.

§.§ Adaptive low-switching greedy policy

Although these aforementioned designs from the finite-horizon literature help increase the accuracy of our estimate $Q$, they are still insufficient to attain regret optimality in the infinite-horizon setting. Since data collection takes place over a single trajectory with no reset, drastic changes in the execution policy can inflict a long-lasting volatility on the future trajectory and slow down the convergence. This is precisely the difficulty of the infinite-horizon setting over the finite-horizon one. The need to control the trajectory variability motivates us to design a novel adaptive switching technique.

Recall in UCB-Q and UCB-Q-Advantage, the execution policy is greedy with respect to the estimate $Q$, i.e., $\pi_t(s_t) = \arg\max_a Q(s_t,a)$. Every time $Q$ gets updated, what the algorithm effectively does is to make an estimate of $Q^{\pi_t}$ with the samples generated by $\pi_t$. Such $Q^{\pi_t}$ is only estimated and updated once before the execution policy is switched to $\pi_{t+1}$. This seems insufficient from a stochastic fixed-point iteration perspective, so we seek to update it more and learn each $Q^{\pi_t}$ better before switching to a new policy.

To tackle this issue, we make the execution policy $\pi_t$ greedy to $\Qlazy$, which is updated lazily yet adaptively in . Specifically, for every $(s,a)$, we use $\qdiff(s,a)$ (cf. Line <ref> in Algorithm <ref>) to keep track of the cumulative difference between the current $Q(s,a)$ and $\QM(s,a)$, the latter of which is defined to be the value of $Q(s,a)$ last time $\Qlazy$ is updated immediately after visiting $(s,a)$. Whenever $\qdiff(s,a)$ exceeds $\frac{1}{1-\gamma}$, indicating $\Qlazy(s,a)$ and the execution policy has become outdated with respect to the current $Q(s,a)$, we reset $\qdiff(s,a)$ and set $u^{\mathrm{switch}}$ to True, which will direct the algorithm to update the entire function $\Qlazy$ in the following step. update-q-lazy() updates $\Qlazy$ with the samples from $\qset$, which is a dictionary that serves as a buffer to store all the new sample transitions and their latest estimates since the last update of $\Qlazy$.

In contrast, conventional low-switching algorithms update the execution policy on a predetermined, exponentially phased schedule [6, 55]. While trajectory stability is attained with these algorithms, as time goes on, it takes them exponentially longer to update policy, making them oblivious to recent large updates in the estimated Q-function. This would lead to suboptimal regret in the infinite-horizon setting, as continual choices of suboptimal actions will keep a lasting effect on future trajectory in the absence of trajectory reset. This issue is overcome in our algorithm by ignoring minor changes in function $Q$ yet still being adaptive to substantial changes in any state-action pair.

§ MAIN RESULTS

Our model-free algorithm can achieve optimal regret with short burn-in time. Its theoretical guarantee can be summarized in the following theorem.

Choose any $\delta \in (0,1)$. Suppose that $c_b$ is chosen to be a sufficiently large universal constant in Algorithm <ref> and let $\iota := \log\frac{SAT}{\delta}$. Then there exists an absolute constant $C_0 > 0$ such that Algorithm <ref> achieves

\begin{equation}\label{eq:thm-result}
\Regret(T) \leq C_0\left(\sqrt{\frac{SAT\iota^3}{(1-\gamma)^3}} + \frac{SA\iota^{\frac{7}{2}}}{(1-\gamma)^8}\right)
\end{equation}

with probability at least $1-\delta$.

The proof of Theorem <ref> is deferred to Appendix <ref>, in which we use a recursive error decomposition scheme different from the existing work. The stationary nature of the infinite-horizon setting gives rise to several error terms unique to the infinite-horizon setting, and our novel switching technique is crucial at controlling them optimally (Lemma <ref>). We will present a proof overview for Theorem <ref> in Section <ref>. Now let us highlight a few key properties of our algorithm.

Optimal regret with low burn-in. achieves optimal regret modulo some logarithmic factor as soon as the sample size $T$ exceeds

\begin{equation}
T \ge \frac{SA}{\poly(1-\gamma)}. \label{eq:optimal-sample-range}
\end{equation}

This burn-in threshold is significantly lower than the $\frac{S^3A^2}{\poly(1-\gamma)}$ threshold in 14 when $SA \gg \frac{1}{1-\gamma}$. In other words, in the regime of (<ref>), the regret of is guaranteed to satisfy

\begin{align}
\Regret(T) \leq \widetilde{O}\left(\sqrt{\frac{SAT}{(1-\gamma)^3}}\right),
\end{align}

which matches the lower bound in Table <ref>.

Sample complexity. As a corollary of Theorem <ref>, it can be seen that attains $\epsilon$-average regret (i.e. $\frac{1}{T}\Regret(T) \le \epsilon$ for any fixed $T$) with sample complexity

\begin{equation}
\widetilde{O}\left(\frac{SA}{(1-\gamma)^3\epsilon^2}\right). \label{eq:optimal-sample-comp}
\end{equation}

This is lower than the sample complexity of the model-free algorithm in 26, which is $\widetilde{O}\big(\frac{SA}{(1-\gamma)^5\epsilon^2}\big)$. Moreover, (<ref>) holds true for any desired accuracy $\epsilon\in\big(0,\frac{(1-\gamma)^{13}}{SA}\big]$. This is a broader range than the ones in 14, 56, which involve higher order of $S$ and $A$ and only allow their algorithms to attain their respective optimal sample complexity in the high-precision regime.

Space complexity. is a model-free algorithm that keeps a few estimates of the Q-function during execution, so its memory cost is as low as $O(SA)$. This is not improvable in the tabular setting, since it requires $O(SA)$ units of space to store the optimal policy. In contrast, the model-based UCBVI-$\gamma$ in [14] stores an estimate of the probability transition kernel and thus incurs a higher memory cost of $O(S^2A)$.

Computational complexity. The computational cost of is only $O(T)$. This is on the same order as reading samples along the $T$-length executed trajectory and is thus unimprovable. In comparison, our algorithm has a considerably lower computational cost than the one in 14, which requires $O(ST)$ operations overall.

§ ANALYSIS OVERVIEW

In this section, we present an overview for the proof of Theorem
<ref>. Let us first introduce some additional notation that is used in this proof overview.

§.§ Additional notation

We let $P_t\in \{0,1\}^{1\times S}$ denote the empirical transition at time step $t$, namely,

\begin{equation}\label{eq:Pt-def}
P_t(s) = \mathds{1}\left[s = s_{t+1}\right].
\end{equation}

Under this notation, given any value function $V\in [0,1]^S$, $P_t V = V(s_{t+1})$.

In addition, let $f$ and $g$ be two real-valued functions that take $\cX := (S,A,\gamma,T,\frac{1}{\delta})$ as arguments. If there exists a universal constant $C > 0$ such that $f(\cX) \le Cg(\cX)$ for any instantiation of $\cX$, we can denote this with the notation $f(\cX) \lesssim g(\cX)$. In addition, $g(\cX) \gtrsim f(\cX)$ is defined as an equivalent way of writing $f(\cX) \lesssim g(\cX)$. We can write $f(\cX) \asymp g(\cX)$ if and if only both $f(\cX) \lesssim g(\cX)$ and $f(\cX) \gtrsim g(\cX)$ are true.

§.§ Proof overview for Theorem <ref>

Towards an upper bound on the regret of , we first need to introduce a few lemmas that summarize some crucial properties of the estimates in the algorithm. They serve as important building blocks in our proof of Theorem <ref>.

In our algorithm, we keep an optimistic estimate $Q$ (resp. $V$) of the optimal function $Q^\star$ (resp. $V^\star$) to encourage exploration of less-observed state-action pairs. This can be summarized in the following lemma, whose proof can be found in Appendix <ref>.

Let $\delta \in (0,1)$. Suppose that $c_b$ is chosen to be a sufficiently large universal constant in Algorithm <ref>. With probability at least $1 - \delta$,

\begin{equation*}\label{eq:Q-monotonicity}
Q_t(s,a) \ge Q^\star(s,a) \qquad \text{and} \qquad V_t(s) \ge V^\star(s)
\end{equation*}

for all $(t,s,a)\in [T]\times \cS \times \cA$ simultaneously.

We can prove a similar lemma for the pessimistic estimate $Q^\LCB$ (resp. $V^\LCB$) of the optimal function $Q^\star$ (resp. $V^\star$). As an implication of the simultaneous usage of optimism and pessimism, we can prove that $V$ and $V^\LCB$ are mostly close to each other throughout the algorithm execution, i.e. (<ref>). This result will be used to characterize the behavior of the reference $V^\rref$ in the remaining of the proof, as the reference $V^\rref$ is controlled based on the size of $V(s_t) - V^\LCB(s_t)$ in our algorithm. The proof of this lemma can be found in Appendix <ref>.

Let $\delta \in (0,1)$. Suppose that $c_b$ is chosen to be a sufficiently large universal constant in Algorithm <ref>. With probability at least $1 - \delta$,

\begin{equation}
\label{eq:Q-lcb-monotonicity}
Q^{\mathrm{LCB}}_t(s, a) \le Q^{\star}(s, a)
\qquad \text{and} \qquad
V^{\mathrm{LCB}}_t(s) \le V^{\star}(s)
\end{equation}

for all $(t,s,a)\in [T]\times \cS \times \cA$ simultaneously, and

\begin{align}
\label{eq:main-lemma}
&\sum_{t=1}^T \mathds{1}\left(V_{t}(s_{t+1}) - V_{t}^{\LCB}(s_{t+1})>3\right) \lesssim \frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{9/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^5}\log \frac{SAT}{\delta} \notag\\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^3}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}.
\end{align}

The following lemma summarizes the important properties of the reference $V^\rref$ in our algorithm. This precisely reflects the discussion about the variance reduction technique in Section <ref>: the reference $V^\rref$ is kept sufficiently close to our running estimate $V$ at all times, but it changes in a stable manner throughout the execution to avoid volatility. The proof can be found in Appendix <ref>.

Let $\delta \in (0,1)$. Suppose that $c_b$ is chosen to be a sufficiently large universal constant in Algorithm <ref>. With probability at least $1 - \delta$,

\begin{equation}
\label{eq:VR-V-proximity}
\left| V_{t}(s) - V^{\rref}_{t}(s) \right| \le 6
\end{equation}

for all $(t, s) \in [T] \times \cS$, and

\begin{align}  \label{eq:VR_lazy}
&\quad \ \sum_{t=1}^T \big(V^{\rref}_{t}(s_{t+1}) - V^{\rref}_{T}(s_{t+1})\big)  \nonumber \\
&\leq \frac{S}{1-\gamma} + \sum_{t=1}^T \Big(V_{t}(s_{t+1}) - V^{\mathrm{LCB}}_{t}(s_{t+1}) \Big) \ind\Big(V_{t}(s_{t+1}) - V^{\mathrm{LCB}}_{t}(s_{t+1}) > 3\Big) \\
&\lesssim \frac{\left(SA\right)^{3/4}T^{1/4}}{(1-\gamma)^{13/4}}\left(\log\frac{SAT}{\delta}\right)^{5/4} + \frac{SA}{(1-\gamma)^6}\log \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})}\big).
\end{align}

The preceding lemmas allow us to quantify the closeness of our Q-function estimate $Q_t$ and $Q^\star$ over the execution trajectory. It reflects the “cumulative” accuracy of our estimate $Q_t$ over the entire trajectory and is an important step towards the final upper bound on the regret. This can be summarized with the lemma below, whose proof can be found in Appendix <ref>.

Fix $\delta \in (0,1)$. Suppose that $c_b$ is chosen to be a sufficiently large universal constant in Algorithm <ref>. Then there exists some absolute constant $C_1 > 0$ such that

\begin{align}
&\sum_{t=1}^T \big(Q_t(s_{t},a_{t}) - Q^\star(s_{t},a_{t})\big) \leq \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^T\big(V_t(s_{t+1}) - V^\star(s_{t+1})\big)
+ C_1\Bigg(\sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} \notag\\
&\quad \qquad + \frac{SA}{(1-\gamma)^7}\log^{7/2} \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg)
\end{align}

with probability at least $1 - \delta$.

Equipped with all these preceding lemmas, we can decompose the regret as follows

\begin{align}\label{eq:sketch-regret-decomp1}
\mathrm{Regret}(T) &\le \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&\le \sum_{t=1}^T\bigg(\frac{\gamma(3-\gamma)}{2}\big(V^\star(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\big) + Q_{t}(s_t, a_t) - Q^\star(s_t, a_t) + \zeta_t\bigg),
\end{align}

in which

\begin{equation*}
\zeta_t := \underbrace{V_{t-1}(s_t) - Q_t(s_t,a_t)}_{\zeta_{t,1}} + \underbrace{\gamma\left(P_{s_t,a_t} - P_t\right)\left(V^\star - V^{\pi_t}\right)}_{\zeta_{t,2}} + \underbrace{\gamma\left(V^{\pi_{t+1}}(s_{t+1}) - V^{\pi_t}(s_{t+1})\right)}_{\zeta_{t,3}}.
\end{equation*}

To proceed, we need to find an upper bound on $\sum_{t=1}^T \zeta_t$. We treat the three terms in $\zeta_t$ separately. $\zeta_{t,2}$ is a higher-order noise term that can be bounded with concentration inequalities, in particular, Lemma <ref> and the Azuma-Hoeffding inequality (Theorem <ref>). The proof can be found in Appendix <ref>.

On the other hand, $\zeta_{t,1}$ and $\zeta_{t,3}$ are two types of error terms unique to the infinite-horizon discounted setting. There exists a tradeoff between $\zeta_{t,1}$ and $\zeta_{t,3}$. Specifically, the sum of $\zeta_{t,3}$'s is governed by the total number of policy switches over the $T$ steps, whereas the sum of $\zeta_{t,1}$'s grows with the staleness of the executed action $a_t$ (i.e., the staleness of the execution policy $\pi_t$) at each step. In order to attain the optimal regret, we balance this tradeoff carefully with the use of our adaptive switching technique, which controls both the sum of $\zeta_{t,1}$'s and the sum of $\zeta_{t,3}$'s at $O(\sqrt{\frac{T}{1-\gamma}})$. It is necessary to control the sum of $\zeta_{t,1}$'s and $\zeta_{t,3}$'s at this order of magnitude. Indeed, this is precisely why the existing techniques mentioned in Section <ref> that switch the execution policy on a predetermined, exponentially phased schedule [6, 55] would fail to attain regret optimality in the infinite-horizon setting. These existing techniques would reduce the sum of $\zeta_{t,3}$'s to $O(\frac{\log T}{(1-\gamma)^2})$ because they switch much less frequently than our algorithm; however, this causes the sum of $\zeta_{t,1}$'s to grow beyond the necessary $O(\sqrt{\frac{T}{1-\gamma}})$, which renders the overall regret larger than the optimal $O(\sqrt{\frac{T}{(1-\gamma)^3}})$.

Overall, the upper bound on $\sum_{t=1}^T \zeta_t$ for our algorithm can be summarized in the following lemma, with its proof provided in Appendix <ref>.

Fix $\delta \in (0,1)$. Suppose that $c_b$ is chosen to be a sufficiently large universal constant in Algorithm <ref>. Then there exists some absolute constant $C_2 > 0$ such that $\zeta_t$ defined in (<ref>) satisfies

\begin{align*}
\sum_{t=1}^T\zeta_t &\leq C_2\Bigg(\sqrt{\frac{SAT}{1-\gamma}\log\frac{SAT}{\delta}} + \frac{SA\log^2\frac{SAT}{\delta}}{(1-\gamma)^{5/2}} + \sqrt{\frac{SA\log^2 T}{1-\gamma}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad + \sqrt{\frac{SA\log\frac{T}{\delta}}{1-\gamma} \sum_{t=1}^{T}\big(V^{\star}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg)
\end{align*}

with probability at least $1 - \delta$.

Finally, we can invoke Lemma <ref> on (<ref>) and reorganize the terms, which turns the inequality into a recursion about $\sum_{t=1}^T V_{t-1}(s_t) - V^{\pi_t}(s_t)$. Then, we can solve for $\sum_{t=1}^T V_{t-1}(s_t) - V^{\pi_t}(s_t)$ in the inequality to arrive at the final upper bound on $\mathrm{Regret}(T)$.

This concludes the proof overview for Theorem <ref>. We defer the actual proof of Theorem <ref> to Appendix <ref>.

§ DISCUSSION

This work has introduced a model-free algorithm that achieves optimal regret in infinite-horizon discounted MDPs, which reduces the space and computational complexity requirement for regret optimality in the existing work. It also achieves optimal sample efficiency with a short burn-in time compared to other algorithms, including 14, 56. Moreover, our algorithm has demonstrated the importance of switching policies slowly in infinite-horizon MDPs and introduced a novel technique might be of additional interest to future work. While our burn-in threshold is considerably reduced with respect to the order of $S$ and $A$, it is not yet optimal in the effective horizon $\frac{1}{1-\gamma}$. This gap between our result and the lower bound is open for future work to investigate.

§ ACKNOWLEDGEMENTS

The authors are very grateful to Yuxin Chen for helpful advice as well as suggesting the direction. X. Ji was supported in part by the NSF grants 1907661 and 2014279.

[1]
Agarwal, A., Kakade, S., and Yang, L. F. (2020).
Model-based reinforcement learning with a generative model is minimax
In Conference on Learning Theory, pages 67–83. PMLR.

[2]
Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002).
Finite-time analysis of the multiarmed bandit problem.
Mach. Learn., 47(2-3):235–236.

[3]
Auer, P. and Ortner, R. (2005).
Online regret bounds for a new reinforcement learning algorithm.
Proceedings 1st Austrian Cognitive Vision Workshop (ACVW 2005),
pages 35–42.

[4]
Azar, M. G., Osband, I., and Munos, R. (2017).
Minimax regret bounds for reinforcement learning.
In International Conference on Machine Learning, pages
263–272. PMLR.

[5]
Azuma, K. (2018).
Weighted sums of certain dependent random variables.
Tohoku Mathematical Journal, 19:357–367.

[6]
Bai, Y., Xie, T., Jiang, N., and Wang, Y.-X. (2019).
Provably efficient q-learning with low switching cost.
Advances in Neural Information Processing Systems, 32.

[7]
Bertsekas, D. P. (2005).
Dynamic Programming and Optimal Control.
Athena Scientific, 3rd edition.

[8]
Brafman, R. I. and Tennenholtz, M. (2003).
R-max - a general polynomial time algorithm for near-optimal
reinforcement learning.
J. Mach. Learn. Res., 3(null):213–231.

[9]
Dong, K., Wang, Y., Chen, X., and Wang, L. (2019).
Q-learning with ucb exploration is sample efficient for
infinite-horizon mdp.
arXiv preprint arXiv:1901.09311.

[10]
Du, S. S., Chen, J., Li, L., Xiao, L., and Zhou, D. (2017).
Stochastic variance reduction methods for policy evaluation.
In International Conference on Machine Learning, pages
1049–1058. PMLR.

[11]
Freedman, D. (1975).
On tail probabilities for martingales.
the Annals of Probability, pages 100–118.

[12]
Gao, M., Xie, T., Du, S. S., and Yang, L. F. (2021).
A provably efficient algorithm for linear markov decision process
with low switching cost.
arXiv preprint arXiv:2101.00494.

[13]
Ge, R., Li, Z., Wang, W., and Wang, X. (2019).
Stabilized svrg: Simple variance reduction for nonconvex
In Conference on learning theory, pages 1394–1448. PMLR.

[14]
He, J., Zhou, D., and Gu, Q. (2021).
Nearly minimax optimal reinforcement learning for discounted mdps.
Advances in Neural Information Processing Systems,

[15]
Jaksch, T., Ortner, R., and Auer, P. (2010).
Near-optimal regret bounds for reinforcement learning.
J. Mach. Learn. Res., 11:1563–1600.

[16]
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018).
Is Q-learning Provably Efficient?
arXiv e-prints, page arXiv:1807.03765.

[17]
Johnson, R. and Zhang, T. (2013).
Accelerating stochastic gradient descent using predictive variance
In Proceedings of the 26th International Conference on Neural
Information Processing Systems, NIPS'13, pages 315–323, Red Hook, NY, USA.
Curran Associates Inc.

[18]
Kakade, S. M. (2003).
On the sample complexity of reinforcement learning.
University of London, University College London (United Kingdom).

[19]
Kash, I. A., Reyzin, L., and Yu, Z. (2022).
Slowly changing adversarial bandit algorithms are provably efficient
for discounted mdps.
arXiv preprint arXiv:2205.09056.

[20]
Kearns, M. and Singh, S. (1999).
Finite-sample convergence rates for q-learning and indirect
In Proceedings of the 1998 Conference on Advances in Neural
Information Processing Systems II, pages 996–1002, Cambridge, MA, USA. MIT

[21]
Lattimore, T. and Hutter, M. (2012).
Pac bounds for discounted mdps.
In International Conference on Algorithmic Learning Theory,
pages 320–334. Springer.

[22]
Li, G., Shi, L., Chen, Y., and Chi, Y. (2021).
Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning.
arXiv e-prints, page arXiv:2110.04645.

[23]
Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, Y. (2021).
Breaking the sample complexity barrier to regret-optimal model-free
reinforcement learning.
Advances in Neural Information Processing Systems,

[24]
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020a).
Breaking the sample size barrier in model-based reinforcement
learning with a generative model.
Advances in neural information processing systems,

[25]
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020b).
Sample complexity of asynchronous q-learning: Sharper analysis and
variance reduction.
Advances in neural information processing systems,

[26]
Liu, S. and Su, H. (2020).
Regret bounds for discounted mdps.
arXiv preprint arXiv:2002.05138.

[27]
Liu, Y., Zhang, K., Basar, T., and Yin, W. (2020).
An improved analysis of (variance-reduced) policy gradient and
natural policy gradient methods.
Advances in Neural Information Processing Systems,

[28]
Ménard, P., Domingues, O. D., Shang, X., and Valko, M. (2021).
Ucb momentum q-learning: Correcting the bias without forgetting.
In International Conference on Machine Learning, pages
7609–7618. PMLR.

[29]
Nguyen, L. M., Liu, J., Scheinberg, K., and Takáč, M. (2017).
Sarah: A novel method for machine learning problems using stochastic
recursive gradient.
In International Conference on Machine Learning, pages
2613–2621. PMLR.

[30]
Pacchiano, A., Ball, P., Parker-Holder, J., Choromanski, K., and Roberts, S.
On optimism in model-based reinforcement learning.
arXiv preprint arXiv:2006.11911.

[31]
Papini, M., Binaghi, D., Canonaco, G., Pirotta, M., and Restelli, M. (2018).
Stochastic variance-reduced policy gradient.
In International conference on machine learning, pages
4026–4035. PMLR.

[32]
Puterman, M. L. (1994).
Markov Decision Processes: Discrete Stochastic Dynamic
John Wiley & Sons, Inc., USA, 1st edition.

[33]
Qiao, D., Yin, M., Min, M., and Wang, Y.-X. (2022).
Sample-efficient reinforcement learning with loglog (t) switching
arXiv preprint arXiv:2202.06385.

[34]
Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. (2022).
Pessimistic q-learning for offline reinforcement learning: Towards
optimal sample complexity.
arXiv preprint arXiv:2202.13890.

[35]
Sidford, A., Wang, M., Wu, X., Yang, L. F., and Ye, Y. (2018a).
Near-optimal time and sample complexities for solving discounted
markov decision process with a generative model.
arXiv preprint arXiv:1806.01492.

[36]
Sidford, A., Wang, M., Wu, X., and Ye, Y. (2018b).
Variance reduced value iteration and faster algorithms for solving
markov decision processes.
In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 770–787. SIAM.

[37]
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche,
G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M.,
Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I.,
Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D.
Mastering the game of Go with deep neural networks and tree search.
Nature, 529(7587):484–489.

[38]
Strehl, A. L., Li, L., Wiewiora, E., Langford, J., and Littman, M. L. (2006).
Pac model-free reinforcement learning.
In Proceedings of the 23rd International Conference on Machine
Learning, ICML '06, pages 881–888, New York, NY, USA. Association for
Computing Machinery.

[39]
Szita, I. and Szepesvari, C. (2010).
Model-based reinforcement learning with nearly tight exploration
complexity bounds.
In Proceedings of the 27th International Conference on
International Conference on Machine Learning, ICML'10, pages 1031–1038,
Madison, WI, USA. Omnipress.

[40]
Tao, T. (2012).
Topics in Random Matrix Theory.
Graduate studies in mathematics. American Mathematical Soc.

[41]
Tropp, J. (2011).
Freedman's inequality for matrix martingales.
Electronic Communications in Probability, 16:262–270.

[42]
Vershynin, R. (2018).
High-Dimensional Probability: An Introduction with Applications
in Data Science, volume 47.
Cambridge University Press.

[43]
Wainwright, M. J. (2019).
Variance-reduced $ q $-learning is minimax optimal.
arXiv preprint arXiv:1906.04697.

[44]
Wang, M. (2017).
Randomized linear programming solves the discounted markov decision
problem in nearly-linear (sometimes sublinear) running time.
arXiv preprint arXiv:1704.01869.

[45]
Wang, T., Zhou, D., and Gu, Q. (2021).
Provably efficient reinforcement learning with linear function
approximation under adaptivity constraints.
Advances in Neural Information Processing Systems,

[46]
Watkins, C. J. C. H. (1989).
Learning from Delayed Rewards.
PhD thesis, King's College, Oxford.

[47]
Watkins, C. J. C. H. and Dayan, P. (1992).
Machine Learning, 8(3):279–292.

[48]
Xiao, L. and Zhang, T. (2014).
A proximal stochastic gradient method with progressive variance
SIAM Journal on Optimization, 24(4):2057–2075.

[49]
Xu, T., Wang, Z., Zhou, Y., and Liang, Y. (2020).
Reanalysis of variance reduced temporal difference learning.
arXiv preprint arXiv:2001.01898.

[50]
Yan, Y., Li, G., Chen, Y., and Fan, J. (2022).
The efficacy of pessimism in asynchronous q-learning.
arXiv preprint arXiv:2203.07368.

[51]
Yang, K., Yang, L., and Du, S. (2021).
Q-learning with logarithmic regret.
In International Conference on Artificial Intelligence and
Statistics, pages 1576–1584. PMLR.

[52]
Yin, M., Bai, Y., and Wang, Y.-X. (2021).
Near-optimal offline reinforcement learning via double variance
Advances in neural information processing systems,

[53]
Zhang, J., Ni, C., Szepesvari, C., Wang, M., et al. (2021a).
On the convergence and sample efficiency of variance-reduced policy
gradient method.
Advances in Neural Information Processing Systems,

[54]
Zhang, Z., Jiang, Y., Zhou, Y., and Ji, X. (2022).
Near-optimal regret bounds for multi-batch reinforcement learning.
arXiv preprint arXiv:2210.08238.

[55]
Zhang, Z., Zhou, Y., and Ji, X. (2020).
Almost optimal model-free reinforcement learningvia
reference-advantage decomposition.
Advances in Neural Information Processing Systems,

[56]
Zhang, Z., Zhou, Y., and Ji, X. (2021b).
Model-free reinforcement learning: from clipped pseudo-regret to
sample complexity.
In International Conference on Machine Learning, pages
12653–12662. PMLR.

[57]
Zhou, D., He, J., and Gu, Q. (2021).
Provably efficient reinforcement learning for discounted mdps with
feature mapping.
In International Conference on Machine Learning, pages
12793–12802. PMLR.

§ A DISCUSSION ABOUT DIFFERENT REGRET METRICS

As we have discussed earlier, multiple metrics exist in the existing literature for evaluating the online performance of an RL algorithm in the infinite-horizon setting. In fact, [14] and [26] both use a respectively different regret metric from the one in this work and [19]. An argument showing the equivalence between the regret metric in [26] and the one in [14] is discussed in Appendix A.2 of [14]. For this reason and the fact that the regret guarantee in [26] is not minimax-optimal, we focus on the relation between our theoretical guarantee in Theorem <ref> and the regret metric from [14] in this section.

Recall that the goal of RL is to learn the optimal policy through online interactions with the environment (and there always exists a stationary optimal policy), so the regret metric we consider in this work is

\begin{equation}\label{eq:regret-again}
\Regret(T) := \sum_{t=1}^T \Big( V^\star(s_t) - V^{\pi_t}(s_t)\Big),
\end{equation}

where $\pi_t$ is the stationary policy that the algorithm uses to take action $a_t$ at step $t$.

The non-stationary regret metric considered in [14] is

\begin{equation}\label{eq:regret-other}
\Regret_{\mathrm{NS}}(T) := \sum_{t=1}^T \Big( V^\star(s_t) - V^{\{\pi_j\}_{j=t}^{\infty}}(s_t)\Big).
\end{equation}

Here, $V^{\{\pi_j\}_{j=t}^{\infty}}(s) := \EE\left[\sum_{i=0}^\infty \gamma^i r(s_i, \pi_{t+i}(s_i)) ~\vert~ s_0=s\right]$, which is the expected cumulative future reward of the non-stationary algorithm starting from time $t$.

In fact, similar difference can also be observed in the literature focused on sample complexity of exploration. Notably, the metric in [56] compares the optimal value function $V^\star(s_t)$ against $V^{\pi_t}(s_t)$, while the metric in works such as [38, 9] compares against $V^{\{\pi_j\}_{j=t}^{\infty}}(s_t)$.

There is no formal equivalence between the two regret metrics in general, despite the intuition we have provided in Remark <ref> that $\Regret_{\mathrm{NS}}(T)$ should be smaller than $\Regret(T)$ for any improving algorithm. However, we can show that the specific algorithm (Algorithm <ref>) achieves $\widetilde{O}(\sqrt{\frac{SAT}{(1-\gamma)^3}})$ regret under the regret metric defined in [14], which matches the lower bound in [14] and is thus optimal for this metric as well.

Before the analysis, let us first define a notation. Let $f$ and $g$ be two real-valued functions that take $\cX := (S,A,\gamma,T,\frac{1}{\delta})$ as arguments. If there exists a universal constant $C > 0$ such that $f(\cX) \le Cg(\cX)$ for any instantiation of $\cX$, we can denote this with the notation $f(\cX) \lesssim g(\cX)$.

Let us define

\begin{align}
\mathcal{T} = \{1 \le t \le T : \pi_t \ne \pi_{t+1}\},
\end{align}

which is the set of time indices that the execution policy switches in the following step, and

\begin{align}
\mathcal{T}_H = \{1 \le t \le T : t + h \in \mathcal{T}\text{ for some }0 \le h \le H\},
\end{align}

which is the set of time indices that the execution policy switches in any of the following $H$ steps.

First, notice

\begin{align}
&\quad\ \bigg|\sum_{t \notin \mathcal{T}_H} \Big(V^{\{\pi_j\}_{j=t}^\infty}(s_t) - \sum_{i = 0}^H \gamma^i r(s_{t+i}, a_{t+i})\Big)\bigg| \notag\\
&\le \bigg|\sum_{t \notin \mathcal{T}_H} \Big(\mathbb{E}\Big[\sum_{i = 0}^H \gamma^i r(s_{t+i}, a_{t+i})\Big] - \sum_{i = 0}^H \gamma^i r(s_{t+i}, a_{t+i})\Big)\bigg| + \frac{\gamma^HT}{1 - \gamma} \notag\\
&\le \sum_{k = 1}^{H}\bigg|\sum_{t = jH + k \notin \mathcal{T}_H} \Big(\mathbb{E}\Big[\sum_{i = 0}^H \gamma^i r(s_{t+i}, a_{t+i})\Big] - \sum_{i = 0}^H \gamma^i r(s_{t+i}, a_{t+i})\Big)\bigg| + \frac{1}{T} \notag\\
&\lesssim \sqrt{\frac{T\log^3 T}{(1-\gamma)^3}}, \label{eq:regret-diff-1}
\end{align}

where the second line holds when $H \gtrsim \frac{\log T}{1-\gamma}$, and the last line makes use of the Azuma-Hoeffding inequality.

Similarly, we have

\begin{align}
\bigg|\sum_{t \notin \mathcal{T}_H} \Big(V^{\pi_t}(s_t) - \sum_{i = 0}^H \gamma^i r(s_{t+i}, a_{t+i})\Big)\bigg|
\lesssim \sqrt{\frac{T\log^3 T}{(1-\gamma)^3}} \label{eq:regret-diff-2}
\end{align}

since $\pi_t = \pi_{t+i}$ for $0 \le i \le H$ and $t \notin \mathcal{T}_H$.

Putting (<ref>) and (<ref>) together leads to

\begin{align}
\big|\Regret(T) - \Regret_{\mathrm{NS}}(T)\big|
&= \left|\sum_{t=1}^T \big(V^{\pi_t}_t(s_t) - V^{\{\pi_j\}_{j=t}^\infty}(s_t)\big)\right| \notag\\
&\lesssim \sqrt{\frac{T\log^3 T}{(1-\gamma)^3}} + \frac{|\mathcal{T}|\log T}{(1-\gamma)^2} \label{eq:regret-diff-3}
\end{align}

by noticing that $\Big|\sum_{t \in \mathcal{T}_H} \big(V^{\pi_t}(s_t) - V^{\{\pi_j\}_{j=t}^\infty}(s_t)\big)\Big| \lesssim \frac{|\mathcal{T}_H|}{1-\gamma} \lesssim \frac{|\mathcal{T}|\log T}{(1-\gamma)^2}$.

Since our algorithm is low-switching and $|\mathcal{T}| \le \widetilde{O}(\frac{SA}{(1-\gamma)^{9/2}}+\frac{(SA)^{3/4}T^{1/4}}{(1-\gamma)^{5/4}})$, the difference between the two regret metrics (<ref>) is dominated by the upper bound on the regret itself. Thus, given our result from Theorem <ref> that $\Regret(T) \le \widetilde{O}(\sqrt{\frac{SAT}{(1-\gamma)^3}})$, we can conclude $\Regret_{\mathrm{NS}}(T) \le \widetilde{O}(\sqrt{\frac{SAT}{(1-\gamma)^3}})$ for our algorithm . In fact, this conversion holds as long as the algorithm's switching cost is dominated by the regret itself, e.g., when the switching cost is $o(\sqrt{T})$.

§ AN ALTERNATIVE PRESENTATION OF ALGORITHM <REF>

We present a rewritten version of Algorithm <ref> in Algorithm <ref>, which specifies the time step index of all iterates for easier identification in later analysis.

(a rewrite of Algorithm <ref> that specifies dependency on $t$)
Initialize: For all $(s,a)$, $Q_1(s,a), Q^{\mathrm{UCB}}_1(s,a), Q^{\mathrm{R}}_1(s,a) \leftarrow \frac{1}{1-\gamma}$; $Q^{\mathrm{LCB}}_1(s,a) \leftarrow 0$; $N_0(s,a) \leftarrow 0$; $V_1(s) \leftarrow V^{\mathrm{R}}_1(s) = \frac{1}{1-\gamma}$; $\mu^{\mathrm{ref}}_1(s,a), \sigma^{\mathrm{ref}}_1(s,a), \mu^{\mathrm{adv}}_1(s,a), \sigma^{\mathrm{adv}}_1(s,a), \delta^{\mathrm{R}}_1(s,a), B^{\mathrm{R}}_1(s,a) \leftarrow 0$, $\qdiff_1(s,a) \leftarrow 0$; $M_1(s,a) \leftarrow 1$; $u^{\mathrm{ref}}_1(s) \leftarrow \mathrm{True}$; $Z_0, Z_1 \leftarrow 1$; $H = \lceil\frac{2}{1-\gamma} \rceil$; $\iota = \log\frac{SAT}{\delta}$.

$t = 1, \cdots, T$
Take action $a_t = \pi_{t}(s_t) = \arg \max_a Q_{Z_{t-1}}(s_t, a)$, and draw $s_{t+1} \sim P(\cdot|s_t, a_t)$.

$N_{t}(s_t, a_t) \leftarrow N_{t-1}(s_t, a_t) + 1$; $N_{t}(s, a) \leftarrow N_{t-1}(s, a)$ for all $(s,a) \neq (s_t, a_t)$; $n \leftarrow N_{t}(s_t, a_t)$.

$\eta_n \leftarrow \frac{H+1}{H+n}$.

$Q^{\mathrm{UCB}}_{t+1}(s_t, a_t) \leftarrow \textbf{update-ucb-q}()$; $Q^{\mathrm{UCB}}_{t+1}(s, a) \leftarrow Q^{\mathrm{UCB}}_{t}(s, a)$ for all $(s,a) \neq (s_t, a_t)$.

$Q^{\mathrm{LCB}}_{t+1}(s_t, a_t) \leftarrow \textbf{update-lcb-q}()$; $Q^{\mathrm{LCB}}_{t+1}(s, a) \leftarrow Q^{\mathrm{LCB}}_{t}(s, a)$ for all $(s,a) \neq (s_t, a_t)$.

$Q^{\mathrm{R}}_{t+1}(s_t, a_t) \leftarrow \textbf{update-ucb-q-advantage}()$; $Q^{\mathrm{R}}_{t+1}(s, a) \leftarrow Q^{\mathrm{R}}_{t}(s, a)$ for all $(s,a) \neq (s_t, a_t)$.

$Q_{t+1}(s_t, a_t) \leftarrow \min \{Q^{\mathrm{R}}_{t+1}(s_t, a_t), Q^{\mathrm{UCB}}_{t+1}(s_t, a_t), Q_t(s_t, a_t)\}$; $Q_{t+1}(s, a) \leftarrow Q_{t}(s, a)$ for all $(s,a) \neq (s_t, a_t)$.

$V_{t+1}(s_t) \leftarrow \max_a Q_{t+1}(s_t, a)$; $V_{t+1}(s) \leftarrow V_{t}(s)$ for all $s \neq s_t$.

$V^{\mathrm{LCB}}_{t+1}(s_t) \leftarrow \max\{\max_a Q^{\mathrm{LCB}}_{t+1}(s_t, a), V^{\mathrm{LCB}}_{t}(s_t)\}$; $V^{\mathrm{LCB}}_{t+1}(s) \leftarrow V^{\mathrm{LCB}}_{t}(s)$ for all $s \neq s_t$.

$\qdiff_{t}(s_t,a_t) + Q_{M_{t}(s_t, a_t)}(s_t, a_t) - Q_{t+1}(s_t, a_t) > \frac{1}{1-\gamma}$
$M_{t+1}(s_t, a_t) \leftarrow t+1$;

$Z_{t+1} \leftarrow t+1$;

$\qdiff_{t+1}(s_t,a_t) \leftarrow 0$; $\qdiff_{t+1}(s, a) \leftarrow \qdiff_{t}(s, a)$ for all $(s,a) \neq (s_t, a_t)$;

$Z_{t+1} \leftarrow Z_t$;

$M_{t+1}(s_t, a_t) \leftarrow M_{t}(s_t, a_t)$;

$\qdiff_{t+1}(s_t,a_t) \leftarrow \qdiff_{t}(s_t,a_t) + Q_{M_{t}}(s_t, a_t) - Q_{t+1}(s_t, a_t)$; $\qdiff_{t+1}(s, a) \leftarrow \qdiff_{t}(s, a)$ for all $(s,a) \neq (s_t, a_t)$.

$V_{t+1}(s_{t}) - V^{\mathrm{LCB}}_{t+1}(s_{t}) > 3$
$V^{\mathrm{R}}_{t+1}(s_{t}) \leftarrow V_{t+1}(s_{t})$, $u^{\mathrm{ref}}_{t+1}(s_{t}) = \mathrm{True}$;

$u^{\mathrm{ref}}_{t}(s_{t}) = \mathrm{True}$
$V^{\mathrm{R}}_{t+1}(s_{t}) \leftarrow V_{t+1}(s_{t})$, $u^{\mathrm{ref}}_{t+1}(s_{t}) = \mathrm{False}$.

§ SUPPORTING LEMMAS

§.§ Additional Notation

For any vector $V\in\RR^n$, we denote its $\ell_\infty$-norm with $\norm{V}_{\infty}$, with $\norm{V}_{\infty} := \max_{i\in[n]} \left|V_i\right|$. We also denote its $\ell_1$-norm with $\norm{V}_{1}$, with $\norm{V}_{1} := \sum_{i=1}^n \left|V_i\right|$. Similarly, we can overload this notation for matrices: for any matrix $P\in\RR^{m\times n}$, we denote its $\ell_1$-norm with $\norm{P}_{1}$, with $\norm{P}_{1} := \max_{i\in[m]}\sum_{i=1}^n \left|P_i\right|$.

In addition, for any given vector $V \in \mathbb{R}^{S}$, let us define the variance parameter with respect to $P_{s,a}$ as follows:

\begin{equation} \label{eq:var-def}
\Var_{s, a}(V) := \mathbb{E}_{s' \sim P_{s,a}} \left [\left(V(s') -  P_{s, a}V \right)^2\right]
= P_{s,a} \left(V^{ 2}\right) - \left(P_{s,a}V \right)^2.
\end{equation}

In our analysis, we let $[\mu_t^\re, \sigma_t^\re, \mu_t^\adv, \sigma_t^\adv, \delta_t^\rref, B_t^\rref, b_t^\rref, B_t^\mathrm{next}]$ denote the value of $[\mu^\re, \sigma^\re, \mu^\adv, \sigma^\adv, \delta^\rref, B^\rref, b^\rref, B^\mathrm{next}]$ in Algorithm <ref> at the beginning of Step $t$. This is similar to the time indices in Algorithm <ref>.

Occasionally, we let the notation $t_n(s,a)$ denote the step index when $(s,a)$ is visited for the $n$-th time, i.e., when $N_t(s_t,a_t) = N_t(s,a) = n$. In addition, $t_n(s,a)$ might be abbreviated to $t_n$ when $(s,a)$ is clear from the context. This will be specified again in the later analysis when such notation is used.

§.§ Learning Rate Lemma and Its Proof

Let $\eta_n$ be as defined in Algorithm <ref>. For any integers $N\ge 0$ and $n\ge 1$, define

\begin{equation}\label{eq:learning-rate-def2}
\eta_0^N := \begin{cases}\prod_{i=1}^N(1-\eta_i)=0, \quad &\text{if }N>0;\\ 1, \quad &\text{if }N=0\end{cases}\quad \text{and}\quad \eta_n^N := \begin{cases}\eta_n\prod_{i=n+1}^N(1-\eta_i), \quad &\text{if }N>n;\\ \eta_n, \quad &\text{if }N=n;\\ 0, \quad &\text{if }N<n.\end{cases}
\end{equation}

Let $\eta_n^N$ be as defined in (<ref>). One has

\begin{equation}
\sum_{n=1}^N\eta_n^N := \begin{cases}1, \quad &\text{if }N>0;\\ 0, \quad &\text{if }N=0.\end{cases} \label{eq:learning-rate1}
\end{equation}

Moreover, for any integer $N > 0$, the following properties are true:

\begin{equation}
\frac{1}{N^a} \le \sum_{n=1}^N\frac{\eta_n^N}{n^a} \le \frac{2}{N^a}, \quad \text{for all } \frac{1}{2} \le a \le 1, \label{eq:learning-rate2}
\end{equation}

\begin{align}
\max_{1\le n \le N}\eta_n^N &\le \frac{6}{(1-\gamma)N}\label{eq:learning-rate3}\\
\sum_{n=1}^N\left(\eta_n^N\right)^2 &\le \frac{6}{(1-\gamma)N}. \label{eq:learning-rate4}
\end{align}

In addition, for any integer $n \ge 0$, one has

\begin{equation}
\sum_{N=n}^\infty\eta_n^N \le 1 + \frac{1-\gamma}{2}. \label{eq:learning-rate5}
\end{equation}

We can directly invoke Lemma 1 of [23] with $H = \lceil\frac{2}{1-\gamma}\rceil$. Note that the proofs of (<ref>) and (<ref>) do not depend on $H$, so (20) and (21a) from [23] are directly applicable.

(21b) from [23] gives $\max_{1\le n \le N}\eta_n^N \le \frac{2H}{N}$ and $\sum_{n=1}^N\left(\eta_n^N\right)^2 \le \frac{2H}{N}$. (<ref>) and (<ref>) can be obtained by the fact $2\lceil\frac{2}{1-\gamma}\rceil \le 2\left(\frac{2}{1-\gamma}+1\right) \le \frac{6}{1-\gamma}$, where the last step is obtained by $2\le \frac{2}{1-\gamma}$.

Lastly, from (21b) in [23], we can write $\sum_{N=n}^\infty\eta_n^N \le 1 + \frac{1}{\lceil\frac{1-\gamma}{2}\rceil}$, which immediately leads to (<ref>).

§.§ Proposition <ref> and Its Proof

For $x,y,z \in \RR$, if

\begin{equation}
z^2 \le xz + y, \label{eq:algebraic-lem-cond}
\end{equation}

this implies

\begin{equation}
z^2 \le x^2 + 2y. \label{eq:algebraic-lem-stat}
\end{equation}

Beginning with (<ref>), we can write

\begin{align}
z^2 \le xz + y &\iff z^2 - xz \le y \notag\\
&\iff z^2 - xz + \frac{1}{4}x^2 \le y + \frac{1}{4}x^2 \notag\\
&\iff \left(z - \frac{x}{2}\right)^2 \le y + \frac{1}{4}x^2\label{eq:algebraic1}
\end{align}

On the other hand,

\begin{align}
z^2 = (z - \frac{x}{2} + \frac{x}{2})^2 \overset{(\mathrm{i})}{\le} 2(z - \frac{x}{2})^2 + 2\left(\frac{x}{2}\right)^2 \overset{(\mathrm{ii})}{\le} 2y + \frac{1}{2}x^2 + 2\cdot\frac{x^2}{4} = 2y + x^2,
\end{align}

in which (i) is by the algebraic facts $2ab \le a^2 + b^2$ and $(a+b)^2 \le 2a^2 + 2b^2$; (ii) is by (<ref>).

§.§ Concentration Lemmas

Since we cope with quantities with Markovian nature in RL, let us introduce two established results about the concentration of martingale sequences. The first one is the Azuma-Hoeffding inequality [5, 42], which can be stated as follows:

Consider a filtration $\cF_0\subset \cF_1 \subset \cF_2 \subset \cdots$,
and let $\mathbb{E}_{i}$ stand for the expectation conditioned
on $\mathcal{F}_i$. Suppose that $Y_{n}=\sum_{i=1}^{n}X_{i}\in\mathbb{R}$,
where $\{X_{i}\}$ is a real-valued scalar sequence obeying

$$\left|X_{i}\right|\leq R\qquad\text{and}\qquad\mathbb{E}_{i-1} \big[X_{i}\big]=0\quad\quad\quad\text{for all }i\ge 1$$

for some $R<\infty$.
Then with probability at least $1-\delta$,

\begin{equation}
\left|Y_{n}\right|\leq \sqrt{R^2n\log\frac{1}{\delta}}.\label{eq:hoeffding}
\end{equation}

The other concentration result is Freedman's inequality [11, 41], which characterizes the concentration in a more specific way with variance. We state a version of it taken from Theorem 3 of [22].

Consider a filtration $\cF_0\subset \cF_1 \subset \cF_2 \subset \cdots$,
and let $\mathbb{E}_{i}$ stand for the expectation conditioned
on $\mathcal{F}_i$. Suppose that $Y_{n}=\sum_{i=1}^{n}X_{i}\in\mathbb{R}$,
where $\{X_{i}\}$ is a real-valued scalar sequence obeying

$$\left|X_{i}\right|\leq R\qquad\text{and}\qquad\mathbb{E}_{i-1} \big[X_{i}\big]=0\quad\quad\quad\text{for all }i\ge 1$$

for some $R<\infty$. Moreover, define

and suppose that $W_{n}\leq\sigma^{2}$ holds deterministically for some given $\sigma^2<\infty$.
Then for any positive integer $m \geq1$, with probability at least $1-\delta$,

\begin{equation}
\left|Y_{n}\right|\leq\sqrt{8\max\Big\{ W_{n},\frac{\sigma^{2}}{2^{m}}\Big\}\log\frac{2m}{\delta}}+\frac{4}{3}R\log\frac{2m}{\delta}.\label{eq:Freedman}
\end{equation}

In the following, we introduce two more concentration results based on Freedman's inequality to handle some quantities of specific types during the execution of our algorithm. Our concentration results are adapted from Lemma 7 and 8 in 22, which handle the finite-horizon setting.

For any $(s,a,N)\in \cS\times \cA\times [T]$, let $\left\{ W_{i} \in \mathbb{R}^S \mid 1\leq i\leq T \right\}$ and $\left\{u_i(s,a,N)\in \mathbb{R} \mid 1\leq i\leq T\right\}$ be a collection of vectors and scalars, respectively, and suppose that both obey the following properties:

* For any $i \in [T]$, $W_{i}$ is fully determined by the samples collected up to the end of the $(i-1)$-th step;

* For any $i \in [T]$, $\norm{W_i}_{\infty}\leq C_\mathrm{w}$ and $W_i \geq 0$ deterministically;

* For any $i \in [T]$, $u_i(s, a,N)$ is fully determined by the samples collected up to the end of the $(i-1)$-th step and a given positive integer $N\in [T]$;

* For any $i \in [T]$, $0\leq u_i(s, a, N) \leq C_{\mathrm{u}}$ deterministically;

* Given any $N_t(s,a) \in [T]$ and sequence $\{t_n(s,a) \in [T] \mid 1 \le n \le N_t(s,a)\}$, $0\leq \sum_{n=1}^{N_t(s,a)} u_{t_n(s,a)}(s,a, N) \leq 2$ deterministically.

In addition, define the sequence

\begin{align}
X_i (s,a,N) &:= u_i(s,a, N) \left(P_{i} - P_{s,a}\right) W_{i}
\ind\left\{ (s_i, a_i) = (s,a)\right\},
\qquad \text{for}\ 1\leq i\leq T.
\end{align}

Let $\delta \in (0,1)$. With probability at least $1-\delta$,

\begin{align}
&\quad\ \left|\sum_{i=1}^t X_i(s,a,N) \right| \notag\\
& \lesssim \sqrt{C_{\mathrm{u}}\log^{2}\frac{SAT}{\delta}}\sqrt{\sum_{n=1}^{N_{t}(s,a)}u_{t_{n}(s,a)}(s,a,N)\Var_{s,a}\left(W_{t_{n}(s,a)}\right)}+\left(C_{\mathrm{u}}C_{\mathrm{w}}+\sqrt{\frac{C_{\mathrm{u}}}{N}}C_{\mathrm{w}}\right)\log^{2}\frac{SAT}{\delta}
\end{align}

for all $(t, s, a, N) \in [T] \times \cS \times \cA \times [T]$ simultaneously.

In this proof, we apply Freedman's inequality (Theorem <ref>) for an upper bound on $\sum_{i=1}^t X_i(s,a,N)$. We begin by verifying whether the conditions of Freedman's inequality are satisfied.

First, we verify that $X_i(s,a,N)$ is deterministically bounded:

\begin{align}
\left| X_i(s,a,N) \right| &\le u_i(s,a,N) \left|\left( P_{i} - P_{s,a} \right) W_{i} \right| \leq u_i(s,a,N) \left(\norm{P_{i}}_1 + \norm{P_{s,a}}_1 \right) \norm{W_i}_{\infty}
\leq 2C_\mathrm{w} C_\mathrm{u}, \label{eq:freedman-app1-1}
\end{align}

in which we use the assumptions $\norm{W_i}_{\infty} \leq C_{\mathrm{w}}$ and $0 \le u_i(s,a,N) \le C_{\mathrm{u}}$ as well as $\norm{P_{i}}_1 = \norm{P_{s,a}}_1=1$.

Then, we can also verify that

\begin{align}
\EE_{i-1}\left[ X_i(s,a,N) \right] = u_i(s,a,N) \EE_{i-1}\left[\left( P_{i} - P_{s,a} \right)\ind\left\{ (s_i, a_i) = (s,a)\right\}\right] W_{i} = 0,
\end{align}

because $u_i(s, a,N)$ and $W_i$ are deterministic when conditioned on the $(i-1)$-th step.

With the conditions verified, we give a bound on the second moment of $X_i(s,a,N)$ before invoking Freedman's inequality:

\begin{align}
\sum_{i=1}^{t}\EE_{i-1}\left[\left|X_i(s,a,N)\right|^{2}\right] &= \sum_{i=1}^{t}\left(u_{i}(s,a, N)\right)^{2} \mathds{1}\left\{(s_{i},a_{i})=(s,a)\right\}
\EE_{i-1}\left[\left|(P_{i}-P_{s,a})W_{i}\right|^{2}\right] \notag\\
&= \sum_{n=1}^{N_{t}(s,a)}\left(u_{t_{n}(s,a)}(s,a,N)\right)^{2}\Var_{s,a}\left(W_{t_{n}(s,a)}\right) \notag\\
&\le C_{\mathrm{u}}\left(\sum_{n=1}^{N_{t}(s,a)}u_{t_{n}(s,a)}(s,a,N)\right)\Var_{s,a}\left(W_{t_{n}(s,a)}\right) \label{eq:freedman-app1-2}\\
&\le C_{\mathrm{u}}\left(\sum_{n=1}^{N_{t}(s,a)}u_{t_{n}(s,a)}(s,a,N)\right)\norm{W_{t_{n}(s,a)}}_{\infty}^{2}\notag\\
&\le 2C_{\mathrm{u}}C_{\mathrm{w}}^{2}, \label{eq:freedman-app1-3}
\end{align}

in which we use the assumptions $\norm{W_i}_{\infty} \leq C_{\mathrm{w}}$ and $0 \le u_i(s,a,N) \le C_{\mathrm{u}}$ as well as $0\leq \sum_{n=1}^{N_t(s,a)} u_{t_n(s,a)}(s,a,N) \leq 2$.

Finally, with (<ref>), (<ref>) and (<ref>) established, we can invoke Freedman's inequality (Theorem <ref>) with $m=\lceil \log_2 N \rceil$ and take the union bound over all possible $(t, s, a, N) \in [T] \times \cS \times \cA \times [T]$. This can lead to the desired result: with probability at least $1- \delta$,

\begin{align}
&\quad \ \left|\sum_{i=1}^{t}X_{i}(s,a,N)\right| \notag\\
&\lesssim \sqrt{\max\left\{ C_{\mathrm{u}}\sum_{n=1}^{N_{t}(s,a)}u_{t_{n}(s,a)}(s,a,N)\Var_{s,a}\left(W_{t_{n}(s,a)}\right),\frac{C_{\mathrm{u}}C_{\mathrm{w}}^{2}}{N}\right\}\log\frac{SAT^{2}\log N}{\delta}} + C_{\mathrm{u}}C_{\mathrm{w}}\log\frac{SAT^{2}\log N_t}{\delta} \notag\\
&\lesssim \sqrt{C_{\mathrm{u}}\log^{2}\frac{SAT}{\delta}}\sqrt{\sum_{n=1}^{N_{t}(s,a)}u_{t_{n}(s,a)}(s,a,N)\Var_{s,a}\left(W_{t_{n}(s,a)}\right)}+\left(C_{\mathrm{u}}C_{\mathrm{w}} + \sqrt{\frac{C_{\mathrm{u}}}{N}}C_{\mathrm{w}}\right)\log^{2}\frac{SAT}{\delta}\notag
\end{align}

for all $(t, s, a, N) \in [T] \times \cS \times \cA \times [T]$ simultaneously.

Let $\big\{ N(s,a) \in [T] \mid (s,a)\in \cS\times \cA\big\}$ be a collection of positive integers. For any $(s,a)\in \cS\times \cA$, let $\left\{ W_{i} \in \mathbb{R}^S \mid 1\leq i\leq T \right\}$ and $\left\{u_i(s_i,a_i)\in \mathbb{R} \mid 1\leq i\leq T\right\}$ be a collection of vectors and scalars, respectively, and suppose that both obey the following properties:

* For any $i \in [T]$, $W_{i}$ is fully determined by the samples collected up to the end of the $(i-1)$-th step;

* For any $i \in [T]$, $\norm{W_i}_{\infty}\leq C_\mathrm{w}$ and $W_i \geq 0$ deterministically;

* For any $i \in [T]$, $u_i(s_i, a_i)$ is fully determined by the integer $N(s_i, a_i)$ and all samples collected up to the end of the $(i-1)$-th step;

* For any $i \in [T]$, $0\leq u_i(s_i, a_i) \leq C_{\mathrm{u}}$ deterministically.

In addition, define the sequences

\begin{align}
X_{i} &:= u_i(s_i,a_i)\big(P_{i} - P_{s_i,a_i}\big) W_{i},
\qquad &\text{for}\ 1\leq i\leq T,\\
Y_{i} &:= \big(P_{i} - P_{s_i,a_i}\big) W_{i},\qquad &\text{for}\ 1\leq i\leq T.
\end{align}

Let $\delta \in (0,1)$. With probability at least $1-\delta$,

\begin{align}
\left|\sum_{i=1}^{T}X_{i}\right| & \lesssim\sqrt{C_{\mathrm{u}}^{2}\sum_{i=1}^{T}\EE_{i-1}\left[\left|(P_{i}-P_{s_{i},a_{i}})W_{i}\right|^{2}\right]\log\frac{T^{SA}}{\delta}}+C_{\mathrm{u}}C_{\mathrm{w}}\log\frac{T^{SA}}{\delta} \notag\\
&\lesssim \sqrt{C_{\mathrm{u}}^{2}C_{\mathrm{w}}\sum_{i=1}^{T}\EE_{i-1}\left[P_{i}W_{i}\right]\log\frac{T^{SA}}{\delta}}+C_{\mathrm{u}}C_{\mathrm{w}}\log\frac{T^{SA}}{\delta} \notag\\
\left|\sum_{i=1}^{T}Y_{i}\right| &\lesssim \sqrt{TC_{\mathrm{w}}^{2}\log\frac{1}{\delta}}+C_{\mathrm{w}}\log\frac{1}{\delta}\notag
\end{align}

for all possible collections $\{N(s,a) \in [T] \mid (s,a) \in \cS\times \cA\}$ simultaneously.

In this proof, we apply Freedman's inequality (Theorem <ref>) for an upper bound on $\sum_{i=1}^T X_i$ and $\sum_{i=1}^T Y_i$ respectively.

We begin by focusing on $X_i$ and verifying whether the conditions of Freedman's inequality are satisfied. We keep $\left\{N(s,a) \in [T] \mid (s,a)\in \cS\times \cA\right\}$ fixed when checking the conditions. First, we verify that $X_i$ is deterministically bounded:

\begin{align}
\left| X_i \right| &\le u_i(s_i,a_i) \left|\left( P_{i} - P_{s_i,a_i} \right) W_{i} \right| \leq u_i(s_i,a_i) \left(\norm{P_{i}}_1 + \norm{P_{s_i,a_i}}_1 \right) \norm{W_i}_{\infty}
\leq 2C_\mathrm{w} C_\mathrm{u}, \label{eq:freedman-app2-1}
\end{align}

in which we use the assumptions $\norm{W_i}_{\infty} \leq C_{\mathrm{w}}$ and $0 \le u_i(s_i,a_i) \le C_{\mathrm{u}}$ as well as $\norm{P_{i}}_1 = \norm{P_{s_i,a_i}}_1=1$.

Then, since $u_i(s_i,a_i)$ is deterministic when conditioned on the $(i-1)$-th step and $N(s_i,a_i)$, we can also verify that

\begin{align}
\EE_{i-1}\left[ X_i \right] = u_i(s_i,a_i) \EE_{i-1}\left[\left( P_{i} - P_{s_i,a_i} \right)\right]W_i = 0,
\end{align}

because $W_i$ is deterministic when conditioned on the $(i-1)$-th step. Note that $a_i$ is determined by $Q_{j}$ for some $j < i$, which is deterministic when conditioned on the $(i-1)$-th step, so $\EE_{i-1}\left[P_{i} - P_{s_i,a_i}\right] = 0$.

With the conditions verified, we give a bound on the second moment of $X_i$ before invoking Freedman's inequality:

\begin{align}
\sum_{i=1}^{T}\EE_{i-1}\left[\left|X_i\right|^{2}\right] &= \sum_{i=1}^{T}\left(u_{i}(s_i,a_i)\right)^{2} \EE_{i-1}\left[\left|(P_{i}-P_{s,a})W_{i}\right|^{2}\right] \notag\\
& \overset{(\mathrm{i})}{\le} C_{\mathrm{u}}^{2}\sum_{i=1}^{T}\EE_{i-1}\left[\left|(P_{i}-P_{s_{i},a_{i}})W_{i}\right|^{2}\right] \label{eq:freedman-app2-3}\\
& \le C_{\mathrm{u}}^{2}\sum_{i=1}^{T}\EE_{i-1}\left[\left|P_{i}W_{i}\right|^{2}\right]\notag\\
& \overset{(\mathrm{ii})}{=} C_{\mathrm{u}}^{2}\sum_{i=1}^{T}\EE_{i-1}\left[P_{i}(W_{i})^{2}\right]\notag\\
& \overset{(\mathrm{iii})}{\le}C_{\mathrm{u}}^{2}\sum_{i=1}^{T}\norm{W_i}_{\infty}\EE_{i-1}\left[P_{i}W_{i}\right] \notag\\
& \overset{(\mathrm{iv})}{\le}C_{\mathrm{u}}^{2}C_{\mathrm{w}}\sum_{i=1}^{T}\EE_{i-1}\left[P_{i}W_{i}\right] \label{eq:freedman-app2-4}\\
& \leq C_{\mathrm{u}}^{2}C_{\mathrm{w}}\sum_{i=1}^{T} \norm{W_i}_{\infty} \notag\\
& \overset{\mathrm{(v)}}{\le} TC_{\mathrm{u}}^{2}C_{\mathrm{w}}^2. \label{eq:freedman-app2-5}
\end{align}

In the series of equalities and inequalities above, (i) is due to the assumption $0 \leq u_i(s_i,a_i) \leq C_{\mathrm{u}}$. (ii) is due to $P_i$ is a canonical basis vector. (iii) is due to the non-negativity of $W_i$. (iv) and (v) are obtained using $\norm{W_i}_{\infty} \le C_{\mathrm{w}}$.

Finally, with (<ref>), (<ref>) and (<ref>) established, we can invoke Freedman's inequality (Theorem <ref>) with $m=\lceil \log_2 N \rceil$ and take the union bound over all possible collections $\{N(s,a) \in [T] \mid (s,a)\in \cS\times \cA\}$, which has at most $T^{SA}$ possibilities. This can lead to the desired result: with probability at least $1- \delta$,

\begin{align*}
\left|\sum_{i=1}^{T}X_{i}\right| & \lesssim \sqrt{\max\left\{ C_{\mathrm{u}}^{2}\sum_{i=1}^{T}\EE_{i-1}\left[ \left|(P_{i}-P_{s_{i},a_{i}})W_{i}\right|^{2}\right],\frac{TC_{\mathrm{u}}^{2}C_{\mathrm{w}}^{2}}{2^{m}}\right\} \log\frac{T^{SA}\log T}{\delta}} + C_{\mathrm{u}}C_{\mathrm{w}}\log\frac{T^{SA}\log T}{\delta}\\
&\lesssim \sqrt{C_{\mathrm{u}}^{2}\sum_{i=1}^{T}\EE_{i-1}\left[\left|(P_{i}-P_{s_{i},a_{i}})W_{i}\right|^{2}\right]\log\frac{T^{SA}}{\delta}} + C_{\mathrm{u}}C_{\mathrm{w}}\log\frac{T^{SA}}{\delta}\\
&\lesssim\sqrt{C_{\mathrm{u}}^{2}C_{\mathrm{w}}\sum_{i=1}^{T}\EE_{i-1}\left[P_{i}W_{i}\right]\log\frac{T^{SA}}{\delta}} + C_{\mathrm{u}}C_{\mathrm{w}}\log\frac{T^{SA}}{\delta}
\end{align*}

for all possible collections $\{N(s,a) \in [T] \mid (s,a)\in \cS\times \cA\}$ simultaneously.

On the other hand, we can bound $\left|\sum_{i=1}^T Y_{i}\right|$ with a simple application of Freedman's inequality. After checking the conditions for $X_i$, we can readily see

\begin{align*}
\left|Y_i\right| \le 2C_{\mathrm{w}}, \\
\sum_{i=1}^{T}\EE_{i-1}\left[\left|Y_{i}\right|^{2}\right] \le T C_{\mathrm{w}}^2.
\end{align*}

We can invoke Freedman's inequality (Theorem <ref>) with $m=1$ to arrive at

\begin{align}
\left|\sum_{i=1}^{T} Y_{i} \right| \lesssim \sqrt{T C_{\mathrm{w}}^{2} \log\frac{1}{\delta}} + C_{\mathrm{w}} \log\frac{1}{\delta}
\end{align}

with probability at least $1-\delta$.

§ PROOF OF THEOREM <REF>

For an upper bound on the cumulative regret, we begin our analysis with a decomposition of the regret. By the optimistic property of our value function estimates in Lemma <ref>, we can

\begin{equation}
\mathrm{Regret}(T) = \sum_{t=1}^T \big(V^\star(s_t) - V^{\pi_t}(s_t)\big) \le \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big).
\end{equation}

In the inequality, since $V_0(s)$ is undefined in our algorithm, we can simply let $V_0(s) = \frac{1}{1-\gamma}$ for all $s\in \cS$.

Onward, we can focus on finding an upper bound on $V_{t-1}(s_t) - V^{\pi_t}(s_t)$. To this end, we further decompose $V_{t-1}(s_t) - V^{\pi_t}(s_t)$ into  three component terms and bound each of them respectively. The decomposition is as follows:

\begin{align}
&\quad\ V_{t-1}(s_t) - V^{\pi_t}(s_t) \notag\\
&\overset{(\mathrm{i})}{=} V_{t-1}(s_t) - Q^{\pi_t}(s_t, a_t) \notag\\
&= V_{t-1}(s_t) - Q^\star(s_t, a_t) + Q^\star(s_t, a_t) - Q^{\pi_t}(s_t, a_t) \notag\\
&\overset{(\mathrm{ii})}{=} V_{t-1}(s_t) - Q^\star(s_t, a_t) + \gamma P_{s_t,a_t}\left(V^\star - V^{\pi_t}\right) \notag\\
&\overset{(\mathrm{iii})}{=} V_{t-1}(s_t) - Q^\star(s_t, a_t) + \gamma \left(P_{s_t,a_t} - P_t\right)\left(V^\star - V^{\pi_{t}}\right) + \gamma \left(V^\star(s_{t+1}) - V^{\pi_t}(s_{t+1})\right) \notag\\
&\overset{(\mathrm{iv})}{=} \gamma\left(V^\star(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right) + Q_{t}(s_t, a_t) - Q^\star(s_t, a_t) + \zeta_t \notag\\
&\overset{(\mathrm{v})}{\leq} \frac{\gamma(3-\gamma)}{2}\left(V^\star(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right) + Q_{t}(s_t, a_t) - Q^\star(s_t, a_t) + \zeta_t. \label{eq:regret-decomp1}
\end{align}

In the series of equalities above, (i) is because $\pi_t(s_t) = a_t$ in Algorithm <ref>. (ii) is by the Bellman equation (<ref>) and Bellman optimality equation (<ref>). (iii) is because by the definition in (<ref>), $P_t(V^\star - V^{\pi_t}) = V^\star(s_{t+1}) - V^{\pi_t}(s_{t+1})$. In (iv), we group a few component terms into a newly-defined term

\begin{equation}\label{eq:zeta-def}
\zeta_t := V_{t-1}(s_t) - Q_t(s_t,a_t) + \gamma\left(P_{s_t,a_t} - P_t\right)\left(V^\star - V^{\pi_t}\right) + \gamma\left(V^{\pi_{t+1}}(s_{t+1}) - V^{\pi_t}(s_{t+1})\right).
\end{equation}

Lastly, (v) is due to $\gamma \le \frac{\gamma(3-\gamma)}{2}$.

The regret can be further manipulated with an upper bound on $Q_{t}(s_t, a_t) - Q^\star(s_t, a_t)$ via the application of Lemma <ref>. Such manipulation leads to a recursion on $V_{t-1}(s_t) - V^{\pi_t}(s_t)$. Rearranging (<ref>), we obtain a recursion as follows:

\begin{align}
&\quad \left(1 - \frac{\gamma(3-\gamma)}{2}\right)\sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&= \sum_{t=1}^T\left(V_{t-1}(s_t) - V^{\pi_t}(s_t)\right) - \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^T\left(V_{t-1}(s_t) - V^{\pi_t}(s_t)\right) \notag\\
&\overset{(\mathrm{i})}{\le} \sum_{t=1}^T\left(V_{t-1}(s_t) - V^{\pi_t}(s_t)\right) - \frac{\gamma(3-\gamma)}{2}\sum_{t=2}^T\left(V_{t-1}(s_t) - V^{\pi_t}(s_t)\right) \notag\\
&= \sum_{t=1}^T\left(V_{t-1}(s_t) - V^{\pi_t}(s_t)\right) - \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^{T-1}\left(V_{t}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right) \notag\\
&\overset{(\mathrm{ii})}{\le} \sum_{t=1}^T\bigg(\frac{\gamma(3-\gamma)}{2}\left(V^\star(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right) + Q_{t}(s_t, a_t) - Q^\star(s_t, a_t) + \zeta_t\bigg) - \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^{T-1}\left(V_{t}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right) \notag\\
&\overset{(\mathrm{iii})}{\le} C_1\left(\sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^7}\log^{7/2} \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\right) \notag\\ & \qquad + \sum_{t=1}^T\bigg(\frac{\gamma(3-\gamma)}{2}\left(V_t(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right) + \zeta_t\bigg) - \frac{\gamma(3-\gamma)}{2}\sum_{t=1}^{T-1}\left(V_{t}(s_{t+1}) - V^{\pi_{t+1}}(s_{t+1})\right) \notag\\
&= C_1\left(\sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^7}\log^{7/2} \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\right) \notag\\ & \qquad + \frac{\gamma(3-\gamma)}{2}\left(V^\star(s_{T+1}) - V^{\pi_{T+1}}(s_{T+1})\right) + \sum_{t=1}^T \zeta_t \notag\\
&\overset{(\mathrm{iv})}{\le} C_1\left(\sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^7}\log^{7/2} \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})}\big)\right) \notag\\ & \qquad + \frac{3}{2(1-\gamma)} + \sum_{t=1}^T \zeta_t \notag\\
&\lesssim \sqrt{\frac{SAT}{1-\gamma}\log^{3}\frac{SAT}{\delta}} + \frac{SA}{(1-\gamma)^7}\log^{7/2} \frac{SAT}{\delta} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^5}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} + \sum_{t=1}^T\zeta_t. \label{eq:regret-decomp2}
\end{align}

Above, (i) is because by the optimistic property in Lemma <ref>, $V_{t-1}(s_t) \ge V^\star(s_t) \ge V^{\pi_t}(s_t) \ge 0$ and thus $V_{t-1}(s_t) - V^{\pi_t}(s_t) \ge 0$. (ii) is obtained by replacing $\left(V_{t-1}(s_t) - V^{\pi_t}(s_t)\right)$ with (<ref>). (iii) is obtained by invoking Lemma <ref> to replace $\sum_{t=1}^T \big(Q_t(s_{t},a_{t}) - Q^\star(s_{t},a_{t})\big)$. (iv) is due to $V^\star(s_{T+1}) - V^{\pi_{T+1}}(s_{T+1}) \le \frac{1}{1-\gamma}$ and $\gamma\in(0,1)$.

Note $0 < 1 - \frac{\gamma(3-\gamma)}{2} < 1$ since $\gamma\in(0,1)$. Dividing (<ref>) by $1 - \frac{\gamma(3-\gamma)}{2}$, we have

\begin{align}
& \quad\ \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&\lesssim \sqrt{\frac{SAT\log^{3}\frac{SAT}{\delta}}{(1-\gamma)^3}} + \frac{SA\log^{7/2} \frac{SAT}{\delta}}{(1-\gamma)^8} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^7}\sum_{t=1}^T \big(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\big)} + \frac{1}{1-\gamma}\sum_{t=1}^T\zeta_t, \label{eq:regret-decomp3}
\end{align}

in which the additional $\frac{1}{1-\gamma}$ factor is due to the fact $1 - \frac{\gamma(3-\gamma)}{2} \ge \frac{1-\gamma}{2}$.

We continue by invoking Lemma <ref> on (<ref>), which allows us to write (<ref>) as

\begin{align}
& \quad\ \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&\leq C_3\Bigg(\sqrt{\frac{SAT\log^3\frac{SAT}{\delta}}{(1-\gamma)^3}} + \frac{SA\log^{7/2} \frac{SAT}{\delta}}{(1-\gamma)^8} + \sqrt{\frac{SA\log^2 T}{(1-\gamma)^7}\sum_{t=1}^T\left(V_{t-1}(s_{t}) - V^{\pi_{t}}(s_{t})\right)} \notag\\ & \qquad + \sqrt{\frac{SA\log\frac{T}{\delta}}{(1-\gamma)^3} \sum_{t=1}^{T}\big(V^{\star}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg) \label{eq:regret-decomp4}
\end{align}

for some absolute constant $C_3 > 0$.

Finally, some algebraic manipulation on (<ref>) can lead to the desired result in Theorem <ref>. In particular, we can use Proposition <ref>, which is an algebraic fact about quadratic inequalities like (<ref>). The proof of Proposition <ref> is provided in Appendix <ref>.

Specifically, we can invoke Proposition <ref> on (<ref>) with

\begin{align*}
x &:= C_3\log T\sqrt{\frac{SA}{(1-\gamma)^7}},\\
y &:= C_3\Bigg(\sqrt{\frac{SAT\log^3\frac{SAT}{\delta}}{(1-\gamma)^3}} + \frac{SA\log^{7/2} \frac{SAT}{\delta}}{(1-\gamma)^8} + \sqrt{\frac{SA\log\frac{T}{\delta}}{(1-\gamma)^3} \sum_{t=1}^{T}\big(V^{\star}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg),\\
z &:= \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big)
\end{align*}

in (<ref>). (<ref>) in Proposition <ref> would give

\begin{align}
& \quad\ \sum_{t=1}^T \big(V^\star(s_t) - V^{\pi_t}(s_t)\big) \notag\\
& \leq \sum_{t=1}^T \big(V_{t-1}(s_t) - V^{\pi_t}(s_t)\big) \notag\\
&\leq 2C_3\sqrt{\frac{SAT\log^3\frac{SAT}{\delta}}{(1-\gamma)^3}} + (2C_3 + C_3^2)\frac{SA\log^{7/2}\frac{SAT}{\delta}}{(1-\gamma)^8} + 2C_3\sqrt{\frac{SA\log\frac{T}{\delta}}{(1-\gamma)^3} \sum_{t=1}^{T}\big(V^{\star}(s_{t}) - V^{\pi_{t}}(s_{t})\big)}\Bigg). \label{eq:regret-decomp5}
\end{align}

We apply Proposition <ref> once again on (<ref>) by letting

\begin{align*}
x &:= 2C_3\sqrt{\frac{SA\log\frac{T}{\delta}}{(1-\gamma)^3}},\\
y &:= 2C_3\sqrt{\frac{SAT\log^3\frac{SAT}{\delta}}{(1-\gamma)^3}} + (2C_3 + C_3^2)\frac{SA\log^{7/2}\frac{SAT}{\delta}}{(1-\gamma)^8},\\
z &:= \sum_{t=1}^T \big(V^\star(s_t) - V^{\pi_t}(s_t)\big)
\end{align*}

in (<ref>). (<ref>) would give

\begin{equation}
\Regret(T) = \sum_{t=1}^T \big(V^\star(s_t) - V^{\pi_t}(s_t)\big) \lesssim \sqrt{\frac{SAT\log^3\frac{SAT}{\delta}}{(1-\gamma)^3}} + \frac{SA\log^{7/2}\frac{SAT}{\delta}}{(1-\gamma)^8} \label{eq:regret-decomp-final}
\end{equation}

with probability at least $1-\delta$, which is as claimed in Theorem <ref>.

§ PROOF OF LEMMA <REF>

We can prove this lemma by induction.

For the base case, it is clear that $Q_1(s,a) = \frac{1}{1-\gamma} \ge Q^\star(s,a)$ for all $(s,a)\in \cS\times\cA$. For the inductive step, assuming the inductive hypothesis $Q_{t}(s,a) \ge Q^\star(s,a)$ all the way up to $t$ for all $(s,a)\in \cS\times\cA$, we need to prove $Q_{t+1}(s,a) \ge Q^\star(s,a)$. To this end, given any $t \in [T]$ and the inductive hypothesis at the $t$-th step, it suffices to prove for all $(s,a) \in \cS \times \cA$,

\begin{equation}\label{eq:Q-monotonicity-intermediate}
\min\{Q^{\UCB}_{t+1}(s, a), Q^{\mathrm{R}}_{t+1}(s, a)\} \ge Q^\star(s,a).
\end{equation}

To prove (<ref>), we need to examine the two arguments of the $\min$ function separately and prove

\begin{equation}\label{eq:QUCB-monotonicity}
Q^{\UCB}_{t+1}(s, a) \ge Q^\star(s,a).
\end{equation}

\begin{equation}\label{eq:QR-monotonicity}
Q^{\mathrm{R}}_{t+1}(s, a) \ge Q^\star(s,a).
\end{equation}

respectively. In the proof of (<ref>), we will use the abbreviation $N := N_t(s,a)$ for notational simplicity. In this notation, we can see that $(s,a) := (s_{t_N}, a_{t_N})$.

$\bullet$ Proof of (<ref>): First, let us prove the optimism of $Q^{\UCB}$ in (<ref>).

Let $b_n := c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3 n}}$. We rewrite the subroutine update-q-ucb() in Line <ref> of Algorithm <ref>:

\begin{equation*}
Q^{\UCB}_{t+1}(s, a) = Q^{\UCB}_{t_N+1}(s, a) = (1 - \eta_N)Q^{\UCB}_{t_N}(s, a) + \eta_{N}\left(r(s, a) + \gamma V_{t_N}(s_{t_N+1}) + b_N\right).
\end{equation*}

This recursive relation can be expanded as

\begin{equation}
Q^{\UCB}_{t+1}(s, a) = \eta_0^N Q^{\UCB}_{1}(s, a) + \sum_{n=1}^N \eta_n^N \big(r(s, a) + \gamma V_{t_n}(s_{t_n+1}) + b_n\big), \label{eq:QUCB}
\end{equation}

in which $\eta_0^N$ and $\eta_n^N$ are defined in Lemma <ref>.

Using (<ref>), we have

\begin{align}\label{eq:Q_UCB-Q*}
&\quad Q^{\UCB}_{t+1}(s, a) - Q^\star(s, a) \nonumber\\
&= \eta_0^N \left(Q^{\UCB}_{1}(s, a) - Q^\star(s, a)\right) + \sum_{n=1}^N \eta_n^N \big(r(s, a) + \gamma V_{t_n}(s_{t_n+1}) + b_n - Q^\star(s, a)\big) \nonumber\\
&= \eta_0^N \left(Q^{\UCB}_{1}(s, a) - Q^\star(s, a)\right) + \sum_{n=1}^N \eta_n^N \Big(\gamma\big(V_{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\big) + \gamma\left(P_{t_n} - P_{s,a}\right)V^\star + b_n\Big),
\end{align}

where the last step is by $Q^\star(s,a) = r(s,a) + \gamma P_{s,a} V^\star$ and $V^\star(s_{t_n+1}) = P_{t_n}V^\star$.

We can invoke Lemma 4.3 from 16, which relies on Azuma-Hoeffding inequality, with only notational modification and obtain with probability at least $1-\delta$,

\begin{equation}\label{eq:Jin-Hoeffding}
\left|\sum_{n=1}^N\eta_n^N\gamma\left(P_{t_n} - P_{s,a}\right)V^\star\right| \le c_b\sqrt{\frac{\log\frac{SAT}{\delta}}{(1-\gamma)^3N}}\sum_{n=1}^N\eta_n^N \le \sum_{n=1}^N\eta_n^N b_n,
\end{equation}

for all $(N,s,a) \in [T] \times \cS \times \cA$. This allows us to conclude that with probability at least $1-\delta$,

\begin{align*}
&\quad Q^{\UCB}_{t+1}(s, a) - Q^\star(s, a)\\
&\ge \eta_0^N \left(Q^{\UCB}_{1}(s, a) - Q^\star(s, a)\right) + \sum_{n=1}^N \eta_n^N \Big(\gamma\big(V_{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\big) + \gamma\left(P_{t_n} - P_{s,a}\right)V^\star + b_n\Big)\\
&\ge \eta_0^N \left(Q^{\UCB}_{1}(s, a) - Q^\star(s, a)\right) + \sum_{n=1}^N \eta_n^N \gamma\big(V_{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\big)\\
&\ge \sum_{n=1}^N \eta_n^N \gamma\big(V_{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\big),
\end{align*}

where the last step is because $Q^{\UCB}_{1}(s,a) = \frac{1}{1-\gamma} \ge Q^\star(s,a)$.

Therefore, we can prove (<ref>)

\begin{equation*}
Q^{\UCB}_{t+1}(s, a) - Q^\star(s, a) \ge \sum_{n=1}^N \eta_n^N \gamma\big(V_{t_n}(s_{t_n+1}) - V^\star(s_{t_n+1})\big) \ge 0,
\end{equation*}

where the last inequality is a result of the inductive hypothesis: $V_t(s) \ge Q_t(s, \pi^\star(s)) \ge Q^\star(s, \pi^\star(s)) = V^\star(s)$, for all $(t,s,a)\in [T]\times \cS \times \cA$.

$\bullet$ Proof of (<ref>): Next, let us prove the optimism of $Q^{\rref}$ in (<ref>). Since only $Q_{t+1}^{\rref}(s_t,a_t)$ is updated at the $t$-th step with all other entries of $Q_{t}^{\rref}$ fixed, it suffices to check

\begin{equation}
Q^{\rref}_{t+1}(s_t,a_t) \ge Q^{\star}(s_t,a_t). \label{eq:optimism-induction-step}
\end{equation}

In the proof of (<ref>), we will use the abbreviation $N_t := N_t(s_t,a_t)$ and $t_n := t_n(s_t,a_t)$ for notational simplicity.

Step 1: decomposing $Q^{\rref}_t(s_t,a_t) - Q^{\star}(s_t,a_t)$.

According to the update rule of $Q_t^\rref$ in Line <ref> of Algorithm <ref>, we have

\begin{align*}
&\quad\ Q_{t+1}^{\rref}(s_t,a_t) \\
& = Q^{\rref}_{t_{N_t}+1}(s_t,a_t) \\
&=(1-\eta_{N_t})Q^{\rref}_{t_{N_t}}(s_t,a_t) +\eta_{N_t}\left\{ r(s_t,a_t)+\gamma \left(V_{t_{N_t}}(s_{t_{N_t}+1})-V^{\rref}_{t_{N_t}}(s_{t_{N_t}+1})+\mu^{\re}_{t_{N_t}+1}(s_t,a_t)\right)+b^{\rref}_{t_{N_t}+1}\right\} \\
& = (1-\eta_{N_t})Q^{\rref}_{t_{N_t-1}+1}(s_t,a_t) +\eta_{N_t}\left\{ r(s_t,a_t)+\gamma \left(V_{t_{N_t}}(s_{t_{N_t}+1})-V^{\rref}_{t_{N_t}}(s_{t_{N_t}+1})+\mu^{\re}_{t_{N_t}+1}(s_t,a_t)\right)+b^{\rref}_{t_{N_t}+1}\right\},
\end{align*}

in which the first and last step follow from the fact $t_N = t_{N_t} = t$. Expanding this recursively, we have

\begin{align}
& = \eta_0^{N_t} Q_1^{\rref}(s_t, a_t)   \notag \\
& \qquad + \sum_{n = 1}^{N_t} \eta_n^{N_t} \left\{ r(s_t,a_t) + \gamma\left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1}) + \mu^{\re}_{t_{n}+1}(s_t,a_t)\right) + b^{\rref}_{t_{n}+1} \right\}.
\label{eq:Q_R-decompose}
\end{align}

On the other hand, since $\eta_0^{N_t} + \sum_{n = 1}^{N_t} \eta_n^{N_t} = 1$ by (<ref>), we can write $Q^{\star} (s_t,a_t)$ as a sum weighted by $\{\eta^{N_t}_n\}_{n=0}^{N_t}$. This leads to

\begin{align}\label{eq:Q_R-Q*-decompose}
& Q_{t+1}^{\rref}(s_t,a_t) - Q^{\star} (s_t,a_t) = \eta_0^{N_t} \left(Q_1^{\rref}(s_t, a_t) - Q^{\star} (s_t,a_t)\right) \notag \\
& \qquad + \sum_{n = 1}^{N_t} \eta_n^{N_t} \left\{ r(s_t,a_t) + \gamma\left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1}) + \mu^{\re}_{t_{n}+1}(s_t,a_t)\right) + b^{\rref}_{t_{n}+1} - Q^{\star} (s_t,a_t)\right\}.
\end{align}

Moreover, to further expand (<ref>), we can invoke the definition of $\mu^{\re}$ (which is a moving average of $V^{\rref}$) and expand $Q^{\star}(s_t,a_t)$ using the Bellman optimality equation (cf. (<ref>)), which gives:

\begin{align}
&\quad\ r(s_t,a_t) + \gamma\left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1}) + \mu^{\re}_{t_{n}+1}(s_t,a_t)\right) + b^{\rref}_{t_{n}+1} - Q^{\star} (s_t,a_t)\nonumber\\
&= \gamma\left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})+\frac{\sum_{i=1}^{n}V^{\rref}_{t_i}(s_{t_i+1})}{n}-P_{s_t,a_t}V^{\star}\right)+b^{\rref}_{t_{n}+1} \label{eq:Q_R-Q*-decompose1}\\
&= \gamma\left(P_{t_n}\left\{V_{t_n} - V^{\rref}_{t_n}\right\}+\frac{\sum_{i=1}^{n}P_{t_n}V^{\rref}_{t_i}}{n}-P_{s_t,a_t}V^{\star}\right)+b^{\rref}_{t_{n}+1}\nonumber\\
&= \gamma\left(P_{s_t,a_t}\left\{V_{t_n} - V^{\rref}_{t_n}\right\}+\frac{\sum_{i=1}^{n}P_{s_t,a_t}V^{\rref}_{t_i}}{n}-P_{s_t,a_t}V^{\star}\right)+b^{\rref}_{t_{n}+1} + \xi_{t_n}\nonumber\\
&= \gamma P_{s_t,a_t}\left(V_{t_n} - V^\star +\frac{\sum_{i=1}^{n}V^{\rref}_{t_i} - V^{\rref}_{t_n}}{n}\right)+b^{\rref}_{t_{n}+1} + \xi_{t_n},\label{eq:Q_R-Q*-decompose2}
\end{align}

in which we group the higher-order terms into a newly-defined term

\begin{equation}
\xi_{t_n} :=  \gamma\big(P_{t_n} - P_{s_t,a_t} \big)\big(V_{t_n} - V^{\rref}_{t_n} \big) +  \frac{\gamma}{n}\sum_{i=1}^n \big( P_{t_n} - P_{s_t,a_t} \big) V^{\rref}_{t_i}.
\label{eq:xi-def}
\end{equation}

Combining (<ref>) and (<ref>) leads to the following decomposition

\begin{align}
&\quad\ Q^{\rref}_t(s_t,a_t) - Q^{\star}(s_t,a_t)\notag\\
&= \eta^{N_t}_0 \left(Q^{\rref}_1(s_t,a_t) - Q^{\star}(s_t,a_t)\right) + \sum_{n = 1}^{N_t} \eta^{N_t}_n \left\{\gamma P_{s_t,a_t}\left(V_{t_n} - V^\star +\frac{\sum_{i=1}^{n}V^{\rref}_{t_i} - V^{\rref}_{t_n}}{n}\right)+b^{\rref}_{t_{n}+1} + \xi_{t_n}\right\}.
\label{eq:QR-Q*-final}
\end{align}

Finally, we can notice that several terms in (<ref>) can be dropped:

* Our initialization satisfies $Q^{\rref}_1(s,a) - Q^{\star}(s,a) \geq 0$ for all $(s,a) \in \cS\times\cA$.

* The inductive hypothesis implies that for any $n$ such that $1 \leq t_n \leq t$, one has $V_{t_n}\geq V^{\star}$.

* For all $0 \leq i \leq n$ and any $s\in \cS$, one has

\begin{equation}
V^{\rref}_{t_i}(s) - V^{\rref}_{t_n}(s) \geq 0,
\label{eq:VRti-VRtn}
\end{equation}

because $V^{\rref}_t(s)$ is updated with $V_t(s)$ and $V_t(s)$ is non-increasing by its update rule.

Thus, (<ref>) can be lower-bounded as follows:

\begin{equation}
Q^{\rref}_t(s_t,a_t) - Q^{\star}(s_t,a_t)
\geq \sum_{n = 1}^{N_t} \eta^{N_t}_n \left(b^{\rref}_{t_{n}+1} + \xi_{t_n}\right).
\label{eq:QR-Q-LB}
\end{equation}

To establish the desired result of optimism, it remains to show the right-hand side of (<ref>) is non-negative. In particular, it suffices for us to show

\begin{equation}
\left|\sum_{n = 1}^{N_t} \eta^{N_t}_n \xi_{t_n} \right| \le
\sum_{n = 1}^{N_t} \eta^{N_t}_n b^{\rref}_{t_{n}+1}.
\label{eq:claim-sum-eta-sum-b}
\end{equation}

To justify (<ref>), we will examine the two quantities that compose $\xi_{t_n}$. Let us denote them as $I_1$ and $I_2$ respectively:

\begin{align}
I_1 &:=  \gamma\sum_{n=1}^{N_t} \eta_n^{N_t} \left(P_{t_n} - P_{s_t,a_t} \right)\left(V_{t_n} - V^{\rref}_{t_n} \right),  \label{eq:I1-def} \\
I_2 &:= \gamma\sum_{n=1}^{N_t} \frac{1}{n} \eta_n^{N_t} \sum_{i=1}^n \left( P_{t_n} - P_{s_t,a_t} \right) V^{\rref}_{t_i}. \label{eq:I2-def}
\end{align}

In the following, we will bound $I_1$ and $I_2$ with Lemma <ref>, which is a result of Freedman's inequality.

Step 2: controlling $I_1$.

We can invoke Lemma <ref> to control the term $I_1$ defined in (<ref>).

We begin by constructing the necessary notation and verify the conditions for Lemma <ref>. Consider any $N \in [T]$. Let

\begin{align}
W_i := V_{i} - V^{\rref}_{i}
\qquad \text{and} \qquad
u_i(s,a, N) := \eta_{N_i(s,a)}^N \geq 0. \label{I1-def1}
\end{align}

Clearly, $W_i$ is deterministic at the end of the $(i-1)$-th step. Note that $N_i(s,a)$ is also deterministic at the end of the $(i-1)$-th step, because $s_t$ and $Q_{Z_{t-1}}$ (and thus $a_t$) are already deterministic at the end of the $(i-1)$-th step. Moreover, we define an upper bound $C_{\mathrm{w}}$ as follows:

\begin{align}
\norm{W_i}_\infty \leq \norm{V^{\rref}_{i}}_{\infty} + \norm{V_i}_{\infty} \leq \frac{2}{1-\gamma} =: C_{\mathrm{w}}. \label{I1-cw}
\end{align}

In addition, using (<ref>) and (<ref>) in Lemma <ref>, we have

\begin{align*}
\eta_{N_{i}(s,a)}^{N} \leq\frac{6}{N(1-\gamma)} ,\qquad &\text{if }1\le N_{i}(s,a)\le N;\\
\eta_{N_{i}(s,a)}^{N} = 0, \qquad &\text{if }N_{i}(s,a)>N,
\end{align*}

which in turn allows us to define an upper bound $C_{\mathrm{u}}$:

\begin{align}
\max_{N, s, a\in [T] \times \cS\times \cA} \eta_{N_{i}(s,a)}^{N} \leq \frac{6}{N(1-\gamma)} =: C_{\mathrm{u}}. \label{I1-cu}
\end{align}

Lastly, we can verify

\begin{align}
0 \leq \sum_{n=1}^N u_{t_n(s,a)}(s,a, N) = \sum_{n=1}^N \eta_{n}^N \leq 1 \label{eq:I1-cond-u}
\end{align}

holds for all $(N,s,a) \in [T] \times \cS\times \cA$.

Hence, we can apply Lemma <ref> with (<ref>), (<ref>), (<ref>) and $(N,s,a)=(N_t,s_t, a_t)$ and conclude with probability at least $1-\delta$,

\begin{align}
|I_1| &= \left|\gamma\sum_{n=1}^{N_t} \eta_n^{N_t} \left(P_{t_n} - P_{s_t,a_t} \right)\left(V_{t_n} - V^{\rref}_{t_n} \right)\right| = \gamma\left|\sum_{i=1}^t X_i(s_t,a_t, N_t)\right| \nonumber\\
&\lesssim \sqrt{C_{\mathrm{u}}\log^{2}\frac{SAT}{\delta}}\sqrt{\sum_{n=1}^{N_{t}}u_{t_{n}}(s_t,a_t,N)\Var_{s_t, a_t}\left(W_{t_{n}(s_t, a_t)}\right)}+\left(C_{\mathrm{u}}C_{\mathrm{w}}+\sqrt{\frac{C_{\mathrm{u}}}{N}}C_{\mathrm{w}}\right)\log^{2}\frac{SAT}{\delta}\nonumber\\
&\lesssim \sqrt{\frac{1}{N_t(1-\gamma)}\log^{2}\frac{SAT}{\delta}}\sqrt{\sum_{n=1}^{N_{t}}\eta^{N_t}_n \Var_{s_t, a_t}\left(V_{t_n} - V^{\rref}_{t_n}\right)} + \frac{\log^2\frac{SAT}{\delta}}{N_t(1-\gamma)^2} \label{eq:I1-1}\\
&\lesssim \sqrt{\frac{1}{N_t(1-\gamma)}\log^2\frac{SAT}{\delta}}\sqrt{{\sigma}^{\adv}_{t_{N_t}+1}(s_t,a_t) - \left({\mu}^{\adv}_{t_{N_t}+1}(s_t,a_t) \right)^2} + \frac{\log^2\frac{SAT}{\delta}}{(N_t)^{3/4}(1-\gamma)^2}.
\label{eq:I1-2}
\end{align}

Above, the last inequality (<ref>) requires additional work to establish. Its proof is deferred to Appendix <ref> to streamline the presentation.

Step 3: controlling $I_2$.

Next, we turn to controlling the term $I_2$ defined in (<ref>), which can be rearranged as

\begin{align}
I_2 = \gamma\sum_{n=1}^{N_t} \frac{1}{n} \eta_n^{N_t} \sum_{i=1}^n \left( P_{t_n} - P_{s_t,a_t} \right) V^{\rref}_{t_i}
= \gamma\sum_{n=1}^{N_t} \left( \sum_{n = i}^{N_t} \frac{\eta^{N_t}_n}{n} \right)\left( P_{t_n} - P_{s_t,a_t} \right) V^{\rref}_{t_i}.
\end{align}

In the following, we control $I_2$ by invoking Lemma <ref> again. Consider any $N\in[T]$. We abuse the notation by letting

\begin{align}
W_i := V^{\rref}_{i}
\qquad \text{and} \qquad
u_i(s,a, N) := \sum_{n=N_i(s,a)}^N \frac{\eta_n^N}{n} \geq 0. \label{I2-def1}
\end{align}

Moreover, define

\begin{align}
\norm{W_i}_\infty \leq \norm{V^{\rref}_{i}}_\infty \leq \frac{1}{1-\gamma} := C_{\mathrm{w}} \label{I2-cw}
\end{align}

and by (<ref>) in Lemma <ref>, we have

\begin{align}
\sum_{n=N_i(s,a)}^N \frac{\eta_n^N}{n} \leq \sum_{n = 1}^{N} \frac{\eta^{N}_n}{n} \le \frac{2}{N} := C_{\mathrm{u}}, \label{I2-cu}
\end{align}

which immediately implies:

\begin{align}
0 \leq \sum_{n=1}^N u_{t_n(s,a)}(s,a, N) \leq \sum_{n=1}^{N}\frac{2}{N}\leq 2.
\end{align}

Overall, the conditions for Lemma <ref> are satisfied. Therefore, we can apply Lemma <ref> with (<ref>), (<ref>), (<ref>) and $(N,s,a)=(N_t,s_t, a_t)$ and conclude with probability at least $1-\delta$,

\begin{align}
| I_2 | &= \left|\gamma\sum_{n=1}^{N_t} \left( \sum_{n = i}^{N_t} \frac{\eta^{N_t}_n}{n} \right) \sum_{i=1}^n \left( P_{t_n} - P_{s_t,a_t} \right) V^{\rref}_{t_i}\right| = \gamma\left|\sum_{i=1}^t X_i(s_t,a_t,N_t)\right|\nonumber\\
&\lesssim \sqrt{C_{\mathrm{u}}\log^{2}\frac{SAT}{\delta}}\sqrt{\sum_{n=1}^{N_{t}}u_{t_{n}}(s_t,a_t,N)\Var_{s_t,a_t}\left(W_{t_{n}(s_t,a_t)}\right)}+\left(C_{\mathrm{u}}C_{\mathrm{w}}+\sqrt{\frac{C_{\mathrm{u}}}{N}}C_{\mathrm{w}}\right)\log^{2}\frac{SAT}{\delta}\nonumber\\
&\lesssim \sqrt{\frac{1}{N_t}\log^2\frac{SAT}{\delta}}\sqrt{\frac{1}{N_t}\sum_{n = 1}^{N_t} \Var_{s_t,a_t}\left(W_{t_{n}(s_t,a_t)}\right)} + \frac{1}{N_t(1-\gamma)} \log^2\frac{SAT}{\delta} \label{eq:I2-1}\\
&\lesssim \sqrt{\frac{1}{N_t}\log^2\frac{SAT}{\delta}}\sqrt{ \sigma^{\re}_{t_{N_t}+1}(s_t,a_t) - \left(\mu^{\re}_{t_{N_t}+1}(s_t,a_t) \right)^2} + \frac{ \log^2\frac{SAT}{\delta}}{(N_t)^{3/4}(1-\gamma)}
\label{eq:I2-2}
\end{align}

Above, the last inequality (<ref>) requires additional work to establish. Its proof is deferred to Appendix <ref> to streamline the presentation.

Step 4: combining $I_1$ and $I_2$.

Summing up the results in (<ref>) and (<ref>), we can find an upper bound on $\left|\sum_{n = 1}^{N_t} \eta^{N_t}_n \xi_{t_n} \right|$ as follows:

\begin{align}
&\quad\ \left|\sum_{n = 1}^{N_t} \eta^{N_t}_n \xi_{t_n} \right| \leq |I_1| +|I_2| \notag\\
&\lesssim \sqrt{\frac{1}{N_t(1-\gamma)}\log^2\frac{SAT}{\delta}}\sqrt{{\sigma}^{\adv}_{t_{N_t}+1}(s_t,a_t) - \left({\mu}^{\adv}_{t_{N_t}+1}(s_t,a_t) \right)^2} \notag\\
&\qquad + \sqrt{\frac{1}{N_t}\log^2\frac{SAT}{\delta}}\sqrt{ \sigma^{\re}_{t_{N_t}+1}(s_t,a_t) - \left(\mu^{\re}_{t_{N_t}+1}(s_t,a_t) \right)^2} + \frac{\log^2\frac{SAT}{\delta}}{(N_t)^{3/4}(1-\gamma)^2} \nonumber \\
& \leq B^{\rref}_{t_{N_t}+1}(s_t,a_t) + c_b \frac{\log^2\frac{SAT}{\delta}}{(N_t)^{3/4}(1-\gamma)^2}
\label{eq:xi-sum}
\end{align}

for some sufficiently large absolute constant $c_b>0$. The last step follows from the definition of $B^{\rref}_{t_{N_t}+1}(s_t,a_t)$ in Line <ref> and <ref> of Algorithm <ref>.

With $\left|\sum_{n = 1}^{N_t} \eta^{N_t}_n \xi_{t_{n}}\right|$ dealt with, we still need to make some manipulation on $\sum_{n = 1}^{N_t} \eta^{N_t}_n b^{\rref}_{t_{n}+1}$ in order to establish (<ref>). We do so by leveraging the following relation, which can be reasoned from the definitions of $b^{\rref}_{t_{n}+1}$ and $\delta^{\rref}_{t_{n}+1}$ in Line <ref> and <ref> of Algorithm <ref>:

\begin{equation}
b^{\rref}_{t_{n}+1} =\Big(1-\frac{1}{\eta_{n}}\Big)B_{t_n}^{\rref}(s_{t},a_{t})
\label{eq:b-delta-identity}
\end{equation}

by the fact $-\frac{1-\eta_n}{\eta_n}=1-\frac{1}{\eta_n}$.

Using (<ref>) and the definition of $\eta_n^N$ in (<ref>), we have

\begin{align}
&\quad\ \sum_{n = 1}^{N_t} \eta^{N_t}_n b^{\rref}_{t_{n}+1} \nonumber \\
&=\sum_{n = 1}^{N_t} \eta_n \prod_{i = n+1}^{N_t}(1-\eta_i) \left( \left(1-\frac{1}{\eta_n}\right) B_{t_n}^{\rref}(s_{t},a_{t})
+\frac{1}{\eta_{n}}B_{t_n+1}^{\rref}(s_t,a_t) \right) + c_b \sum_{n=1}^{N_t}\frac{ \eta_n^{N_t} }{n^{3/4}(1-\gamma)^2}  \log^2\frac{SAT}{\delta}\nonumber \\
&= \sum_{n = 1}^{N_t}  \prod_{i = n+1}^{N_t}(1-\eta_i) \left( -\left(1-\eta_n\right) B_{t_n}^{\rref}(s_{t},a_{t})
+ B_{t_n+1}^{\rref}(s_t,a_t) \right) + c_b \sum_{n=1}^{N_t}\frac{ \eta_n^{N_t} }{n^{3/4}(1-\gamma)^2}  \log^2\frac{SAT}{\delta}\nonumber \\
&= \sum_{n = 1}^{N_t}  \left(\prod_{i = n+1}^{N_t}(1-\eta_i) B_{t_n+1}^{\rref}(s_{t},a_{t})
- \prod_{i = n}^{N_t}(1-\eta_i)B_{t_n}^{\rref}(s_t,a_t) \right) + c_b \sum_{n=1}^{N_t}\frac{ \eta_n^{N_t} }{n^{3/4}(1-\gamma)^2}  \log^2\frac{SAT}{\delta}\nonumber \\
&\overset{\mathrm{(i)}}{=} \sum_{n = 1}^{N_t} \prod_{i = n+1}^{N_t}(1-\eta_i) B_{t_n+1}^{\rref}(s_{t},a_{t})
- \sum_{n = 2}^{N_t} \prod_{i = n}^{N_t}(1-\eta_i)B_{t_n}^{\rref}(s_t,a_t) + c_b \sum_{n=1}^{N_t}\frac{ \eta_n^{N_t} }{n^{3/4}(1-\gamma)^2}  \log^2\frac{SAT}{\delta}\nonumber \\
&\overset{\mathrm{(ii)}}{=} \sum_{n = 1}^{N_t} \prod_{i = n+1}^{N_t}(1-\eta_i) B_{t_n+1}^{\rref}(s_{t},a_{t})
- \sum_{n = 1}^{N_t-1} \prod_{i = n+1}^{N_t}(1-\eta_i)B_{t_n+1}^{\rref}(s_t,a_t) + c_b \sum_{n=1}^{N_t}\frac{ \eta_n^{N_t} }{n^{3/4}(1-\gamma)^2}  \log^2\frac{SAT}{\delta}\nonumber \\
&= B^{\rref}_{t_{N_t}+1}(s_t,a_t)  + c_b \sum_{n=1}^{N_t}\frac{ \eta_n^{N_t} }{n^{3/4}(1-\gamma)^2}  \log^2\frac{SAT}{\delta}.
\label{eq:eta-b-sum-id}
\end{align}

Above, (i) is due to $B^{\rref}_{t_1}(s_t,a_t) = 0$. (ii) can be obtained as follows:

\begin{align*}
\sum_{n = 2}^{N_t} \prod_{i = n}^{N_t}(1-\eta_i)B_{t_n}^{\rref}(s_t,a_t) & = \sum_{n = 1}^{N_t-1} \prod_{i = n+1}^{N_t}(1-\eta_i)B_{t_{n+1}}^{\rref}(s_t,a_t) = \sum_{n = 1}^{N_t-1} \prod_{i = n+1}^{N_t}(1-\eta_i)B_{t_n+1}^{\rref}(s_t,a_t),
\end{align*}

in which the summation is re-indexed over the first equality by replacing $n$ with $n+1$, and the second equality is true because the state-action pair
$(s_t,a_t)$ has not been visited between the $(t_n +1)$-th step and the $(t_{n+1} - 1)$-th step.

Furthermore, (<ref>) allows us to conclude

\begin{equation}
B^{\rref}_{t_{N_t}+1}(s_t,a_t) + c_b\frac{\log^2\frac{SAT}{\delta}}{(N_t)^{3/4}(1-\gamma)^2} \le \sum_{n = 1}^{N_t} \eta^{N_t}_n b^{\rref}_{t_{n}+1} \le B^{\rref}_{t_{N_t}+1}(s_t,a_t) + 2c_b\frac{\log^2\frac{SAT}{\delta}}{(N_t)^{3/4}(1-\gamma)^2},
\label{eq:eta-b-sum-squeeze}
\end{equation}

because (<ref>) of Lemma <ref> implies

\begin{equation*}
\frac{1}{(N_t)^{3/4}} \le \sum_{n = 1}^{N_t} \frac{\eta^{N_t}_n}{n^{3/4}} \le \frac{2}{(N_t)^{3/4}}.
\end{equation*}

Bringing (<ref>) into (<ref>) gives

\begin{equation}
\left|\sum_{n = 1}^{N_t} \eta^{N_t}_n \xi_{t_n} \right|
\le B^{\rref}_{t_{N_t}+1}(s_t,a_t) + c_b \frac{\log^2\frac{SAT}{\delta}}{(N_h^k)^{3/4}(1-\gamma)^2}  \le \sum_{n = 1}^{N_t} \eta^{N_t}_n b^{\rref}_{t_{n}+1}
\end{equation}

as claimed in (<ref>).

Finally, by proving (<ref>), we have proven the induction step (<ref>) and thus concluded the proof of $Q_t(s, a) \ge Q^\star(s, a)$.

To prove the optimism in $V_t$, given (<ref>), we can easily see from $V_t$'s update rule that for all $(t,s,a)\in [T]\times \cS \times \cA$,

\begin{equation*}
V_t(s) \ge Q_t(s, \pi^\star(s)) \ge Q^\star(s, \pi^\star(s)) = V^\star(s).
\end{equation*}

§.§ Proof of Inequality (<ref>)

As it turns out, it suffices to examine the following term in order to prove (<ref>):

\begin{align}
I_3 := \sum_{n = 1}^{N_t} \eta^{N_t}_n\Var_{s_t,a_t}\left(V_{t_n} - {V}^{\rref}_{t_n}\right) - {\sigma}^{\adv}_{t_{N_t}+1}(s_t,a_t) + \left({\mu}^{\adv}_{t_{N_t}+1}(s_t,a_t) \right)^2.
\label{eq:I3-def}
\end{align}

In this section, we would like to show an upper bound on $I_3$.

Before we proceed, recall that the update rules of $\mu^{\adv}_{t_{n+1}}$ and ${\sigma}^{\adv}_{t_{n+1}}$ in Line <ref> and <ref> of Algorithm <ref> are

\begin{align*}
\mu^{\adv}_{t_{n+1}}(s_t,a_t) &= \mu^{\adv}_{t_n+1}(s_t,a_t)
= (1-\eta_n)\mu^{\adv}_{t_n}(s_t,a_t) + \eta_n \left( V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1}) \right) ,\\
\sigma^{\adv}_{t_{n+1}}(s_t,a_t) &= \sigma^{\adv}_{t_n+1}(s_t,a_t)
= (1-\eta_n)\sigma^{\adv}_{t_n}(s_t,a_t) + \eta_n \left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1}) \right)^2.
\end{align*}

We can expand these equations recursively and write

\begin{align}
\mu^{\adv}_{t_{N_{t}}+1}(s_t,a_t) & = \sum_{n=1}^{N_{t}}\eta_{n}^{N_{t}}\left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})\right) = \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right), \label{eq:I3-1.1}\\
{\sigma}^{\adv}_{t_{N_{t}}+1}(s_t,a_t) & = \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(V_{t_n}(s_{t_n+1}) - V^{\rref}_{t_n}(s_{t_n+1})\right)^{2}= \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)^{2}. \label{eq:I3-1.2}
\end{align}

Noting that $\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}=1$, we can use Jensen's inequality and reason from (<ref>) and (<ref>) that:

\begin{align}\label{eq:I3-2}
{\sigma}^{\adv}_{t_{N_{t}}+1}(s_t,a_t) \geq \left(\mu^{\adv}_{t_{N_{t}}+1}(s_t,a_t)\right)^2.
\end{align}

Recall by the definition of variance in (<ref>), we have

\begin{equation*}
\Var_{s_t,a_t}\left(V_{t_n} - {V}^{\rref}_{t_n} \right)
= P_{s_t,a_t} \left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)^{2} - \left(P_{s_t,a_t} \left(V_{t_{n}}-{V}^{\rref}_{t_n} \right) \right)^2.
\end{equation*}

Bringing this into (<ref>), we can decompose $I_3$ as follows

\begin{align}
I_3 & = \sum_{n = 1}^{N_t} \eta^{N_t}_n P_{s_t,a_t} \left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)^{2} - \sum_{n = 1}^{N_t} \eta^{N_t}_n P_{t_n} \left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)^{2} \nonumber \\
&\qquad \qquad+ \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right)^2  - \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{s_t,a_t} \left(V_{t_{n}}-{V}^{\rref}_{t_n} \right) \right)^2\nonumber \\
& \le  \underbrace{ \left|\sum_{n = 1}^{N_t} \eta^{N_t}_n \left(P_{s_t,a_t} - P_{t_n} \right)\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)^{2}\right| }_{:= I_{3,1}}  \nonumber \\
&\qquad \qquad+ \underbrace{\left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right)^2  - \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{s_t,a_t} \left(V_{t_{n}}-{V}^{\rref}_{t_n} \right) \right)^2}_{:= I_{3,2}} .
\label{eq:I3-3}
\end{align}

It remains to control $I_{3,1}$ and $I_{3,2}$ in (<ref>) separately.

Step 1: controlling $I_{3,1}$.

Now, let us control the term $I_{3,1}$ defined in (<ref>) by invoking Lemma <ref>. Consider any $N\in[T]$. We set

\begin{align}
W_i := \left(V_{i} - {V}^{\rref}_{i} \right)^{ 2}
\qquad \text{and} \qquad
u_i(s,a, N) := \eta_{N_i(s,a)}^N.
\label{I31-def1}
\end{align}

Moreover, define

\begin{align}
\norm{W_i}_\infty \leq  \left( \norm{ V^{\rref}_{i} }_{\infty} + \norm{V_{i}}_\infty \right)^2
\leq \frac{4}{(1-\gamma)^2}:= C_{\mathrm{w}}, \label{I31-cw}
\end{align}

and same as (<ref>), we have

\begin{align}
\max_{N, s, a\in [T] \times \cS\times \cA} \eta_{N_{i}(s,a)}^{N} \leq \frac{8}{N(1-\gamma)} := C_{\mathrm{u}}. \label{I31-cu}
\end{align}

Clearly, we can verify

\begin{align}
0 \leq \sum_{n=1}^N u_{t_n(s,a)}(s,a, N) = \sum_{n=1}^N \eta_{n}^N \leq 1
\end{align}

holds for all $(N,s,a) \in [T] \times \cS\times \cA$, and the conditions for Lemma <ref> are satisfied.

Therefore, with $(N,s,a)=(N_t,s_t, a_t)$, we can apply Lemma <ref> with (<ref>), (<ref>) and (<ref>) to conclude with probability at least $1-\delta$,

\begin{align}
|I_{3,1}| &= \left|\sum_{n = 1}^{{N_t}} \eta_n^{N_t} \left(P_{t_n}-P_{s_t,a_t} \right)\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)^2\right| \notag\\
&= \left|\sum_{i=1}^t X_i(s_t,a_t,N_t)\right| \notag\\
&\lesssim \sqrt{C_{\mathrm{u}} \log^2\frac{SAT}{\delta}}\sqrt{\sum_{n = 1}^{N_t} u_{t_n}(s_t,a_t, N_t) \Var_{s_t,a_t} \left(W_{t_n} \right)} + \left(C_{\mathrm{u}} C_{\mathrm{w}} + \sqrt{\frac{C_{\mathrm{u}}}{N}} C_{\mathrm{w}}\right) \log^2\frac{SAT}{\delta} \nonumber \\
& \lesssim \sqrt{\frac{1}{N_t(1-\gamma)}\log^2\frac{SAT}{\delta}}\sqrt{\sum_{n = 1}^{N_t} \eta^{N_t}_n \Var_{s_t,a_t}\left(\left(V_{t_n} - {V}^{\rref}_{t_n} \right)^2\right) } + \frac{\log^2\frac{SAT}{\delta}}{N_t(1-\gamma)^3} \nonumber \\
&\lesssim \sqrt{\frac{1}{N_t(1-\gamma)^5}\log^2\frac{SAT}{\delta}} + \frac{1}{N_t(1-\gamma)^3}\log^2\frac{SAT}{\delta}, \label{eq:I31-final}
\end{align}

in which the last step follows from $\sum_{n = 1}^{N_t} \eta^{N_t}_n \leq 1$ and $\Var_{s_t,a_t}\left(\left(V_{t_n} - {V}^{\rref}_{t_n} \right)^2\right) \leq \norm{\left(V_{t_n} - {V}^{\rref}_{t_n}  \right)^{4}}_\infty
\leq \frac{16}{(1-\gamma)^4}$.

Step 2: controlling $I_{3,2}$. We can use Jensen's inequality and write $I_{3,2}$ as

\begin{align}
I_{3,2} &= \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right)^2 - \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{s_t,a_t}\big(V_{t_{n}}-{V}^{\rref}_{t_n}\big)\right)^2 \notag\\
&\le \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right)^2 - \left\{\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\right\} \left\{ \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{s_t,a_t}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right)^2\right\} \notag\\
&\le \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right)^2 - \left(\sum_{n=1}^{{N_{t}}}\left(\eta_{n}^{N_{t}}\right)^{1/2} \left(\eta_{n}^{N_{t}}\right)^{1/2}P_{s_t,a_t}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right)^2 \notag\\
&= \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{t_{n}}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right)^2  - \left(\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}P_{s_t,a_t}\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right)^2 \notag\\
&\le \left\{\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{t_{n}} - P_{s_t,a_t}\right)\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right\} \left\{\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{t_{n}} + P_{s_t,a_t}\right)\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right\}. \label{eq:I32-1}
\end{align}

With this upper bound on $I_{3,2}$, we now aim to show

\begin{equation} \label{eq:I32-WTS}
I_{3,2} \leq C_{3,2} \left( \sqrt{\frac{1}{N_t(1-\gamma)^5}\log^2\frac{SAT}{\delta}} + \frac{1}{N_t(1-\gamma)^3}\log^2\frac{SAT}{\delta}\right),
\end{equation}

for some universal constant $C_{3,2}>0$.

Since (<ref>) is trivially true if $I_{3,2}\leq 0$, it suffices to consider the case where $I_{3,2}> 0$ only. To proceed, notice that the first factor in the product in (<ref>) is exactly $I_1$ in (<ref>), which can be bounded with our previous result (<ref>):

\begin{align}
&\lesssim \sqrt{\frac{1}{N_t(1-\gamma)}\log^{2}\frac{SAT}{\delta}}\sqrt{\sum_{n=1}^{N_{t}}\eta^{N_t}_n \Var_{s,a}\left(V_{t_n} - V^{\rref}_{t_n}\right)} + \frac{\log^2\frac{SAT}{\delta}}{N_t(1-\gamma)^2}\nonumber\\
&\overset{\mathrm{(i)}}{\lesssim} \sqrt{\frac{1}{N_t(1-\gamma)^3}\log^2\frac{SAT}{\delta}}\sqrt{\sum_{n = 1}^{N_t} \eta^{N_t}_n  } + \frac{\log^2\frac{SAT}{\delta}}{N_t(1-\gamma)^2} \nonumber \\
&\overset{\mathrm{(ii)}}{\lesssim} \sqrt{\frac{1}{N_t(1-\gamma)^3}\log^2\frac{SAT}{\delta}} + \frac{1}{N_t(1-\gamma)^2}\log^2\frac{SAT}{\delta}
\label{eq:I32-1.1}
\end{align}

with probability at least $1-\delta$. Above, (i) arises from
$\Var_{s,a}\big(V_{t_n} - V^{\rref}_{t_n}\big)
\leq \norm{\left(V_{t_n} - V^{\rref}_{t_n}\right)^{2}}_\infty \leq \frac{4}{(1-\gamma)^2}$ and (ii) is true due to $\sum_{n = 1}^{N_t} \eta^{N_t}_n \leq 1$.

On the other hand, the second factor in the product in (<ref>) can be simply bounded as follows:

\begin{align}
\left|\sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}}\left(P_{t_{n}} + P_{s_t,a_t}\right)\left(V_{t_{n}}-{V}^{\rref}_{t_n}\right)\right|  \le \sum_{n=1}^{{N_{t}}}\eta_{n}^{N_{t}} \left( \norm{P_{t_n}}_1 + \norm{P_{s_t,a_t}}_1 \right) \norm{V_{t_{n}}-{V}^{\rref}_{t_n}}_{\infty} \leq \frac{2}{1-\gamma},
\label{eq:I32-1.2}
\end{align}

in which we use the elementary facts $\sum_{n = 1}^{N_t} \eta^{N_t}_n \leq 1$, $\norm{V_{t_{n}}-{V}^{\rref}_{t_n}}_{\infty} \leq \frac{1}{1-\gamma}$ and $\norm{P_{t_n}}_1 = \norm{P_{s_t,a_t}}_1=1$.

Substituting (<ref>) and (<ref>) back into (<ref>), we can obtain the desired bound (<ref>) for the case $I_{3,2}>0$.
Combined this with the trivial case of $I_{3,2}\le 0$, we have established (<ref>).

Step 3: combining the preceding bounds.

Let us bring the bounds (<ref>) and (<ref>) into (<ref>). This gives

\begin{align*}
I_3 \leq |I_{3,1}| + I_{3,2}
\leq C_{3,3}\left\{ \sqrt{\frac{1}{N_t(1-\gamma)^5}\log^2\frac{SAT}{\delta}} + \frac{1}{N_t(1-\gamma)^3}\log^2\frac{SAT}{\delta}\right\}
\end{align*}

for some absolute constant $C_{3,3}>0$. Writing $I_3$ with its definition in (<ref>), rearranging the inequality results, and taking square root on both sides, we have

\begin{align*}
\left\{\sum_{n = 1}^{N_t} \eta^{N_t}_n\Var_{s_t,a_t}\left(V_{t_n} - {V}^{\rref}_{t_n}\right)\right\}^{1/2} &\leq \left\{ {\sigma}^{\adv}_{t_{N_t}+1}(s_t,a_t) - \left({\mu}^{\adv}_{t_{N_t}+1}(s_t,a_t) \right)^2\right\}^{1/2}\\
& \quad + \sqrt{C_{3,3}} \left(\sqrt{\frac{1}{N_t(1-\gamma)^5}\log^2\frac{SAT}{\delta}} + \frac{1}{N_t(1-\gamma)^3}\log^2\frac{SAT}{\delta}\right)^{1/2}\\
&\leq \left\{ {\sigma}^{\adv}_{t_{N_t}+1}(s_t,a_t) - \left({\mu}^{\adv}_{t_{N_t}+1}(s_t,a_t) \right)^2\right\}^{1/2}\\
& \quad + \frac{1}{\left(N_{t}\right)^{1/4}(1-\gamma)^{5/4}}\log^{1/2}\frac{SAT}{\delta}+\frac{1}{\left(N_t\right)^{1/2}(1-\gamma)^{3/2}}\log\frac{SAT}{\delta}.
\end{align*}

in which we also use the result of (<ref>).