Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition

## Abstract

Abstract We study the gap-dependent bounds of two important algorithms for on-policy Q 𝑄 Q italic_Q -learning for finite-horizon episodic tabular Markov Decision Processes (MDPs): UCB-Advantage (Zhang et al. 2020) and Q-EarlySettled-Advantage (Li et al. 2021). UCB-Advantage and Q-EarlySettled-Advantage improve upon the results based on Hoeffding-type bonuses and achieve the almost optimal T 𝑇 \sqrt{T} square-root start_ARG italic_T end_ARG -type regret bound in the worst-case scenario, where T 𝑇 T italic_T is the total number of steps. However, the benign structures of the MDPs such as a strictly positive suboptimality gap can significantly improve the regret. While gap-dependent regret bounds have been obtained for Q 𝑄 Q italic_Q -learning with Hoeffding-type bonuses, it remains an open question to establish gap-dependent regret bounds for Q 𝑄 Q italic_Q -learning using variance estimators in their bonuses and reference-advantage decomposition for variance reduction. We develop a novel error decomposition
framework to prove gap-dependent regret bounds of UCB-Advantage and Q-EarlySettled-Advantage that are logarithmic in T 𝑇 T italic_T and improve upon existing ones for Q 𝑄 Q italic_Q -learning algorithms. Moreover, we establish the gap-dependent bound for the policy switching cost of UCB-Advantage and improve that under the worst-case MDPs. To our knowledge, this paper presents the first gap-dependent regret analysis for Q 𝑄 Q italic_Q -learning using variance estimators and reference-advantage decomposition and also provides the first gap-dependent analysis on policy switching cost for Q 𝑄 Q italic_Q -learning.

## 1 Introduction

Reinforcement Learning (RL) (Sutton & Barto, ) is a subfield of machine learning focused on sequential decision-making. Often modeled as a Markov Decision Process (MDP), RL tries to obtain an optimal policy through sequential interactions with the environment. It finds applications in various fields, such as games (Silver et al., , , ; Vinyals et al., ), robotics (Kober et al., ; Gu et al., ), and autonomous driving (Yurtsever et al., ).

In this paper, we focus on the on-policy RL tailored for episodic tabular MDPs with inhomogeneous transition kernels. Specifically, the agent interacts with an episodic MDP consisting of $S$ states, $A$ actions, and $H$ steps per episode. The regret information bound for any MDP above and any learning algorithm with $K$ episodes is $O(\sqrt{H^{2}SAT})$ where $T=KH$ denotes the total number of steps (Jin et al., ). Multiple RL algorithms in the literature (e.g. Zhang et al. (); Li et al. (); Zhang et al. ()) have reached a near-optimal $\sqrt{T}$-type regret that matches the information bound up to logarithmic factors, which acts as a worst-case guarantee.

In practice, RL algorithms often perform better than their worst-case guarantees, as such guarantees can be significantly improved under MDPs with benign structures (Zanette & Brunskill, ). This motivates the problem-dependent analysis for algorithms that exploit the benign MDPs (e.g., Wagenmaker et al. (); Zhou et al. (); Zhang et al. ()). One of the benign structures is based on the dependency on the positive suboptimality gap: for every state, the best action outperforms others by a margin. It is important because nearly all non-degenerate environments with finite action sets satisfy some sub-optimality gap conditions (Yang et al., ). Recently, Simchowitz & Jamieson () proved the $\log T$-type regret if there exists a strictly positive suboptimality gap. Since then, the gap-dependent regret analysis has been widely studied, for example, Dann et al. (); Yang et al. (); Xu et al. (); Wang et al. (); He et al. (), etc.

Model-free RL algorithms, the focus of this paper, are also called $Q$-learning algorithms and directly learn the optimal action value function ($Q$-function) and state value function ($V$-function) to optimize the policy. It is widely used in practice due to its easy implementation (Jin et al., ) and the lower memory requirement that scales linearly in $S$ while that for model-based algorithms scales quadratically. However, the literature on gap-dependent analysis for $Q$-learning is quite sparse. Yang et al. () studied the gap-dependent regret of the Q-Hoeffding algorithm (Jin et al., ), the first model-free algorithm with a worst-case $\sqrt{T}$-type regret in the literature, and presented the first $\log T$-type regret bound for model-free algorithms:

$$ $O\left(\frac{H^{6}SA\log(SAT)}{\Delta_{\textnormal{min}}}\right).$ (1) $$

where $\Delta_{\textnormal{min}}$ is defined as the minimum nonzero suboptimality gap for all the state-action-step triples.

Xu et al. () proposed the multi-step bootstrapping algorithm and showed the same dependency on the minimum gap as Yang et al. ().
Both papers used the simple Hoeffding-type bonuses for explorations in the algorithm design. However, their analysis frameworks based on Hoeffding-type bonuses cannot be directly applied to study two important $Q$-learning algorithms that improve the regrets of Jin et al. () and achieve the almost optimal worst-case regret: UCB-Advantage (Zhang et al., ) and Q-EarlySettled-Advantage (Li et al., ). In particular, UCB-Advantage and Q-EarlySettled-Advantage use variance estimators in their bonuses and reference-advantage decomposition for variance reduction. It remains an important open question whether such techniques can improve gap-dependent regret:

Is it possible to establish a potentially improved gap-dependent regret bound for $Q$-learning using variance estimators in the bonuses and reference-advantage decomposition?

This is a challenging task due to several non-trivial difficulties. In particular, bounding the weighted sum of the errors of the estimated $Q$-functions is necessary to establish the gap-dependent regret bounds for UCB-Advantage and Q-EarlySettled-Advantage, which is very difficult as it involves the estimated reference and advantage functions and the bonuses that include variance estimators for both functions. However, the analysis framework of Xu et al. () for their non-optimism algorithm cannot bound the weighted sum of such errors, and the analysis frameworks in all optimism-based model-free algorithms including Jin et al. (); Zhang et al. (); Li et al. (); Yang et al. () can only bound the weighted sum under the simple Hoeffding-type bonus.

Besides the regret, the policy switching cost is also an important evaluation criterion for on-policy RL, especially in applications with restrictions on policy switching such as compiler optimization (Ashouri et al., ), hardware placements (Mirhoseini et al., ), database optimization (Krishnan et al., ), and material discovery (Nguyen et al., ). Under the worst-case MDPs, Bai et al. () modified the algorithms in Jin et al. () to reach a switching cost of $O(H^{3}SA\log T)$, and UCB-Advantage (Zhang et al., ) reached an improved switching cost of $O(H^{2}SA\log T)$ due to the stage design in $Q$-function update, both improving upon the cost of $\Theta(K)$ for regular $Q$-learning algorithms (e.g. Jin et al. ()). To our knowledge, none of the existing works study gap-dependent switching costs for $Q$-learning algorithms, which remains open.

Summary of our contributions. In this paper, we give an affirmative answer to the open questions above by establishing gap-dependent regret bound for UCB-Advantage (Zhang et al., ) and Q-EarlySettled-Advantage (Li et al., ) as well as a gap-dependent policy switching cost for UCB-Advantage. For $Q$-learning, this paper provides the first gap-dependent regret analysis with both variance estimators and variance reduction and the first gap-dependent policy switching cost.

Our detailed contributions are summarized as follows.

- •
Improved Gap-Dependent Regret. Denote $\mathbb{Q}^{\star}\in[0,H^{2}]$ as the *maximum conditional variance* for the MDP and $\beta\in(0,H]$ as the hyper-parameter to settle the reference function. We prove that UCB-Advantage guarantees a gap-dependent expected regret of
$O\left(\frac{\left(\mathbb{Q}^{\star}+\beta^{2}H\right)H^{3}SA\log(SAT)}{
\Delta_{\textnormal{min}}}+\frac{H^{8}S^{2}A\log(SAT)\log(T)}{\beta^{2}}\right),$
(2)
and
Q-EarlySettled-Advantage guarantees a gap-dependent expected regret of
$O\left(\frac{\left(\mathbb{Q}^{\star}+\beta^{2}H\right)H^{3}SA\log(SAT)}{
\Delta_{\textnormal{min}}}+\frac{H^{7}SA\log^{2}(SAT)}{\beta}\right).$
(3)
These results are logarithmic in $T$ and better than the worst-case $\sqrt{T}$-type regret in Zhang et al. (); Li et al. (). They also have a common gap-dependent term $\tilde{O}((\mathbb{Q}^{\star}+\beta^{2}H)H^{3}SA)/\Delta_{\textnormal{min}})$ where $\tilde{O}(\cdot)$ hides logarithmic factors. The other term in either Equation 2 or Equation 3 is gap-free. Our result is also better than Equation 1 for Yang et al. (); Xu et al. () in the following ways. (a) Under the worst-case $\mathbb{Q}^{\star}=\Theta(H^{2})$ and setting $\beta=O(1/\sqrt{H})$ as in Zhang et al. () or $\beta=O(1)$ as in Li et al. (), $\tilde{O}\left(\left(\mathbb{Q}^{\star}+\beta^{2}H\right)H^{3}SA)/\Delta_{
\textnormal{min}}\right)$ becomes $\tilde{O}(H^{5}SA/\Delta_{\textnormal{min}})$, which is better than Equation 1 by a factor of $H$. (b) Under the best variance $\mathbb{Q}^{\star}=0$ which will happen when the MDP is deterministic, our regret in Equation 3 can linearly depend on $\tilde{O}(\Delta_{\textnormal{min}}^{-1/3})$, which is intrinsically better than the dependency on $\Delta_{\textnormal{min}}^{-1}$ in Equation 1. (c) Since our gap-free terms also logarithmically depend on $T$, they are smaller than Equation 1 when $\Delta_{\textnormal{min}}$ is sufficiently small.
- •
Gap-Dependent Policy Switching Cost. We can prove that for any $\delta\in(0,1)$, with probability at least $1-\delta$, the policy switching cost for UCB-Advantage is at most
$O\left(H|D_{\textnormal{opt}}|\log\left(\frac{T}{H|D_{\textnormal{opt}}|}+1
\right)+H|D_{\textnormal{opt}}^{c}|\log\left(\frac{H^{4}SA^{\frac{1}{2}}\log(
\frac{SAT}{\delta})}{\beta\sqrt{|D_{\textnormal{opt}}^{c}|}\Delta_{\textnormal
{min}}}\right)\right).$
(4)
Here, $D_{\textnormal{opt}}$ is a subset of all state-action-step triples and represents all triples such that the action is optimal.
$D_{\textnormal{opt}}^{c}$ is its
complement, and $|\cdot|$ gives the cardinality of the set. In Equation 4, the first term logarithmically depends on $T$, and the second one logarithmically depends on $\Delta_{\textnormal{min}}$ and $\log T$. Thus, we compare the first term with the worst-case costs $O(H^{3}SA\log T)$ in Bai et al. () and $O(H^{2}SA\log T)$
in Zhang et al. (). Ours is better since $|D_{\textnormal{opt}}|<HSA$ for non-degenerate MDPs. Specifically, when each state has a unique optimal action so that $|D_{\textnormal{opt}}|=HS$, Equation 4 implies the improvement by a factor of $A$ compared to $O(H^{2}SA\log T)$. This improvement is significant in applications with a large action space (e.g. recommender system (Covington et al., ) and text-based games (Bellemare et al., )). Readers can find other examples in (Dulac-Arnold et al., , Section 2.3).
- •
Technical Novelty and Contributions.
For gap-dependent regret analysis, we develop an error decomposition framework that separates errors in reference estimations, advantage estimations, and reference settling. This helps bound the weighted sums mentioned above. We creatively handle the separated terms in the following way. (a) We relate the empirical errors and the bonus for reference estimations to $\mathbb{Q}^{\star}$ to avoid using their upper bounds $\Theta(H^{2})$. This leverages the variance estimators. (b) When trying to bound the errors in reference and advantage estimations, we tackle the non-martingale difficulty, originating from the settled reference functions that depend on the whole learning process, with our novel surrogate reference functions so that the empirical estimations become martingale sums. To the best of our knowledge, we are the first to construct martingale surrogates in the literature for $Q$-learning using reference-advantage decomposition.
For the gap-dependent policy switching cost, we explore the unbalanced number of visits to states paired with optimal or suboptimal actions, which leads to the two terms in Equation 4.

Organization. The rest of this paper is organized as follows. Section 2 reviews related works on on-policy RL, suboptimality gap, variance reduction, and other problem-dependent performance. Section 3 presents the preliminaries and main results concerning the gap-dependent regrets and gap-dependent policy switching cost. Section 4 includes a few concluding remarks. Algorithm details are provided in the appendix, and the complete proofs are given in the supplementary materials.

## 2 Related Works

On-policy RL for finite-horizon tabular MDPs with worst-case regret. There are mainly two types of algorithms for reinforcement learning: model-based and model-free learning. Model-based algorithms learn a model from past experience and make decisions based on this model, while model-free algorithms only maintain a group of value functions and take the induced optimal actions. Due to these differences, model-free algorithms are usually more space-efficient and time-efficient compared to model-based algorithms. However, model-based algorithms may achieve better learning performance by leveraging the learned model.

Next, we discuss the literature on model-based and model-free algorithms for finite-horizon tabular MDPs with worst-case regret. Auer et al. (), Agrawal & Jia (), Azar et al. (), Kakade et al. (), Agarwal et al. (), Dann et al. (), Zanette & Brunskill (),Zhang et al. (),Zhou et al. () and Zhang et al. () worked on model-based algorithms. Notably, Zhang et al. () provided an algorithm that achieves a regret of $\tilde{O}(\min\{\sqrt{SAH^{2}T},T\})$, which matches the information lower bound. Jin et al. (), Yang et al. (), Zhang et al. (), Li et al. () and Ménard et al. () worked on model-free algorithms. The latter three have introduced algorithms that achieve minimax regret of $\tilde{O}(\sqrt{SAH^{2}T})$, and recently, Zheng et al. (, ) extended their results to federated $Q$-learning.

Suboptimality Gap. When there is a strictly positive suboptimality gap, it is possible to achieve logarithmic regret
bounds. In RL, earlier work obtained asymptotic logarithmic regret bounds Auer & Ortner (); Tewari & Bartlett ().
Recently, non-asymptotic logarithmic regret bounds were obtained (Jaksch et al. (); Ok et al. (); Simchowitz & Jamieson (); He et al. (). Specifically, Jaksch et al. () developed a model-based algorithm, and their bound depends on the policy gap instead of the action gap studied in this paper. Ok et al. () derived problem-specific logarithmic type lower bounds for both structured and unstructured MDPs. Simchowitz & Jamieson () extended the model-based algorithm by Zanette & Brunskill () and obtained logarithmic regret bounds. Logarithmic regret bounds are obtained in linear function approximation settings He et al. ().

For model free algorithm, Yang et al. () showed that the optimistic Q-learning algorithm by Jin et al. () enjoyed a logarithmic regret $O(\frac{H^{6}SAT}{\Delta_{\textnormal{min}}})$, which was subsequently refined by Xu et al. (). In their work, Xu et al. () introduced the Adaptive Multi-step Bootstrap model-free algorithm.

Most recently, there are also some instance-dependent works using suboptimality gap (Jonsson et al., ; Tirinzoni et al., ; Al Marjani et al., ; Dann et al., ; Wagenmaker et al., ; Wang et al., ; Nguyen-Tang et al., ).

Variance reduction in RL. The reference-advantage decomposition used in Zhang et al. () and Li et al. () is a technique of variance reduction that was originally proposed for finite-sum stochastic optimization (see e.g. Gower et al. (); Johnson & Zhang (); Nguyen et al. ()). Later on, model-free RL algorithms also used variance reduction to improve the sample efficiency. For example, it was used in learning with generative models Sidford et al. (, ); Wainwright (), policy evaluation Du et al. (); Khamaru et al. (); Wai et al. (); Xu et al. (), offline RL Shi et al. (); Yin et al. (), and $Q$-learning Li et al. (); Zhang et al. (); Li et al. (); Yan et al. ().

RL with low switching cost. Research in RL with low switching costs aims to minimize the number of policy switches while maintaining comparable regret bounds to fully adaptive counterparts. Bai et al. () first introduced the problem of RL with low-switching cost and proposed a $Q$-learning algorithm with lazy updates, achieving $\tilde{O}(SAH^{3}\log T)$ switching costs. This work was advanced by Zhang et al. (), which improved the regret upper bound and the switching cost. Additionally, Wang et al. () studied RL under the adaptivity constraint. Recently, Qiao et al. () proposed a model-based algorithm with $\tilde{O}(\log\log T)$ switching costs.

Other problem-dependent performance.
In practice, RL algorithms often perform far more appealingly than what their worst-case performance
guarantees would suggest. This motivates a recent line of works that investigate optimal performance in
various problem-dependent settings (Fruit et al., ; Jin et al., ; Talebi & Maillard, ; Wagenmaker et al., ; Zhao et al., ; Zhou et al., ).

## 3 Main results

This section presents the preliminaries in Subsection 3.1, the gap-dependent regret for UCB-Advantage and Q-EarlySettled-Advantage in Subsection 3.2 and the gap-dependent policy switching cost for UCB-Advantage in Subsection 3.3.

### 3.1 Preliminaries

We first introduce the mathematical model and background on Markov Decision Processes. Throughout this paper, we assume that $0/0=0$. For any $C\in\mathbb{N}$, we use $[C]$ to denote the set $\{1,2,\ldots C\}$. We use $\mathbb{I}[x]$ to denote the indicator function, which equals 1 when the event $x$ is true and 0 otherwise.

Tabular episodic Markov decision process (MDP).
A tabular episodic MDP is denoted as $\mathcal{M}:=(\mathcal{S},\mathcal{A},H,\mathbb{P},r)$, where $\mathcal{S}$ is the set of states with $|\mathcal{S}|=S,\mathcal{A}$ is the set of actions with $|\mathcal{A}|=A$, $H$ is the number of steps in each episode, $\mathbb{P}:=\{\mathbb{P}_{h}\}_{h=1}^{H}$ is the transition kernel so that $\mathbb{P}_{h}(\cdot\mid s,a)$ characterizes the distribution over the next state given the state action pair $(s,a)$ at step $h$, and $r:=\{r_{h}\}_{h=1}^{H}$ is the collection of reward functions. We assume that $r_{h}(s,a)\in[0,1]$ is a deterministic function of $(s,a)$, while the results can be easily extended to random rewards.

In each episode, an initial state $s_{1}$ is selected arbitrarily by an adversary. Then, at each step $h\in[H]$, an agent observes a state $s_{h}\in\mathcal{S}$, picks an action $a_{h}\in\mathcal{A}$, receives the reward $r_{h}=r_{h}(s_{h},a_{h})$ and then transits to the next state $s_{h+1}$.
The episode ends when an absorbing state $s_{H+1}$ is reached. Later on, for ease of presentation, when we describe $s,a,h$ along with “any, each, all" or “$\forall$", we will omit the sets $\mathcal{S},\mathcal{A},[H]$. We denote
$\mathbb{P}_{s,a,h}f=\mathbb{E}_{s_{h+1}\sim\mathbb{P}_{h}(\cdot|s,a)}(f(s_{h+1
})|s_{h}=s,a_{h}=a)$, $\mathbb{V}_{s,a,h}f=\mathbb{P}_{s,a,h}f^{2}-(\mathbb{P}_{s,a,h}f)^{2}$ and $\mathbbm{1}_{s}f=f(s),\forall(s,a,h)$
for any function $f:\mathcal{S}\rightarrow\mathbb{R}$.

Policies, state value functions, and action value functions.
A policy $\pi$ is a collection of $H$ functions $\left\{\pi_{h}:\mathcal{S}\rightarrow\Delta^{\mathcal{A}}\right\}_{h\in[H]}$, where $\Delta^{\mathcal{A}}$ is the set of probability distributions over $\mathcal{A}$. A policy is deterministic if for any $s\in\mathcal{S}$, $\pi_{h}(s)$ concentrates all the probability mass on an action $a\in\mathcal{A}$. In this case, we denote $\pi_{h}(s)=a$. We use $V_{h}^{\pi}:\mathcal{S}\rightarrow\mathbb{R}$ to denote the state value function at step $h$ under policy $\pi$. Mathematically, $V_{h}^{\pi}(s):=\sum_{h^{\prime}=h}^{H}\mathbb{E}_{(s_{h^{\prime}},a_{h^{
\prime}})\sim(\mathbb{P},\pi)}\left[r_{h^{\prime}}(s_{h^{\prime}},a_{h^{\prime
}})\left.\right|s_{h}=s\right].$ We also use $Q_{h}^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ to denote the action value function at step $h$, i.e.,
$Q_{h}^{\pi}(s,a):=r_{h}(s,a)+\sum_{h^{\prime}=h+1}^{H}\mathbb{E}_{(s_{h^{
\prime}},a_{h^{\prime}})\sim\left(\mathbb{P},\pi\right)}\left[r_{h^{\prime}}(s
_{h^{\prime}},a_{h^{\prime}})\left.\right|s_{h}=s,a_{h}=a\right].$
Azar et al. () proved that there always exists an optimal policy $\pi^{\star}$ that achieves the optimal value $V_{h}^{\star}(s)=\sup_{\pi}V_{h}^{\pi}(s)=V_{h}^{\pi^{*}}(s)$ for all $s\in\mathcal{S}$ and $h\in[H]$. The Bellman equation and
the Bellman optimality equation is

$$ $\left\{\begin{array}[]{ l }{V_{h}^{\pi}(s)=\mathbb{E}_{a^{\prime}\sim\pi_{h}(s )}[Q_{h}^{\pi}(s,a^{\prime})}]\\ {Q_{h}^{\pi}(s,a):=r_{h}(s,a)+\mathbb{P}_{s,a,h}V_{h+1}^{\pi}}\\ {V_{H+1}^{\pi}(s)=0,\forall(s,a,h)}\end{array}\text{ and }\left\{\begin{array} []{l}V_{h}^{\star}(s)=\max_{a^{\prime}\in\mathcal{A}}Q_{h}^{\star}(s,a^{\prime })\\ Q_{h}^{\star}(s,a):=r_{h}(s,a)+\mathbb{P}_{s,a,h}V_{h+1}^{\star}\\ V_{H+1}^{\star}(s)=0,\forall(s,a,h).\end{array}\right.\right.$ (5) $$

For any learning problem with $K$ episodes, let $\pi^{k}$ be the policy adopted in the $k$-th episode, and $s_{1}^{k}$ be the corresponding initial state. The regret over $T=HK$ steps is

$$ $\mbox{Regret}(T):=\sum_{k=1}^{K}\left(V_{1}^{\star}(s_{1}^{k})-V_{1}^{\pi^{k}} (s_{1}^{k})\right).$ $$

Later, when we mention the episode index $k$ with “any, each, all" or “$\forall$", we will omit the set $[K]$.

Suboptimality Gap. For any given MDP, we can provide the following formal definition.

###### Definition 3.1 .

For any $(s,a,h)$, the suboptimality gap is defined as
$\Delta_{h}(s,a):=V_{h}^{\star}(s)-Q_{h}^{\star}(s,a)$.

Equation 5 implies that $\Delta_{h}(s,a)\geq 0,\forall(s,a,h)$. Then it is natural to define the minimum gap, which is the minimum non-zero suboptimality gap with regard to all $(s,a,h)$.

###### Definition 3.2 .

We define the minimum gap as $\Delta_{\textnormal{min}}:=\inf\{\Delta_{h}(s,a):\Delta_{h}(s,a)>0,(s,a,h)\in
\mathcal{S}\times\mathcal{A}\times[H]\}.$

We remark that if $\{\Delta_{h}(s,a):\Delta_{h}(s,a)>0,(s,a,h)\in\mathcal{S}\times\mathcal{A}
\times[H]\}=\phi$, then for any state, all actions are optimal, leading to a degenerate MDP. Therefore, for the rest of the paper, we assume that the set is nonempty and $\Delta_{\textnormal{min}}>0$. Definitions 3.1 and 3.2 and the non-degeneration are standard in the literature on gap-dependent analysis (e.g. Simchowitz & Jamieson (); Xu et al. ()).

Maximum Conditional Variance. This quantity is formally defined as follows.

###### Definition 3.3 .

We define the maximum conditional variance as $\mathbb{Q}^{\star}:=\max_{s,a,h}\{\mathbb{V}_{s,a,h}(V_{h+1}^{\star})\}.$

Under our MDP with deterministic reward, Definition 3.3 coincides with that in (Zanette & Brunskill, ) which performed variance-dependent regret analysis.

Policy Switching Cost. We provide the following definition for any algorithm with $K>1$ episodes.

###### Definition 3.4 .

The policy switching cost for $K$ episodes is defined as

$$ $N_{\textnormal{switch}}:=\sum_{k=1}^{K-1}\tilde{N}_{\textnormal{switch}}(\pi_{ k+1},\pi_{k}).$ $$

Here, the $\tilde{N}_{\textnormal{switch}}(\pi,\pi^{\prime}):=\sum_{s\in\mathcal{S}}\sum_
{h=1}^{H}\mathbb{I}[\pi_{h}(s)\neq\pi^{\prime}_{h}(s)]$ represents the local switching cost for any policies $\pi$ and $\pi^{\prime}$.

This definition is also used in Bai et al. () and Zhang et al. ().

###### Definition 3.1 .

###### Definition 3.2 .

###### Definition 3.3 .

###### Definition 3.4 .

### 3.2 Gap-dependent Regrets

UCB-Advantage (Zhang et al., ) is the first model-free algorithm that reaches an almost optimal worst-case regret, which is also reached by Q-EarlySettled-Advantage (Li et al., ). Both algorithms are optimism-based, use upper confidence bounds (UCB) for exploration, and employ variance estimators and reference-advantage decomposition. UCB-Advantage settles the reference function at each $(s,h)$ by comparing the number of visits to a threshold that relies on a hyper-parameter $\beta\in(0,\beta]$. For readers’ convenience, we provide UCB-Advantage without any modification in Appendix A: Algorithm details of UCB-Advantage.

Theorem 3.1 provide the expected regret upper bound of UCB-Advantage.

###### Theorem 3.1 .

For UCB-Advantage (Algorithm 1 in Appendix A: Algorithm details of UCB-Advantage) with $\beta\in(0,H]$, $\mathbb{E}[\textnormal{Regret}(T)]$ is upper bounded by Equation 2.

Q-EarlySettled-Advantage improved the burn-in cost of Zhang et al. () for reaching the almost-optimal worst-case regret by using both estimated upper and lower confidence bounds for $V^{\star}_{h}$ to settle the reference function. In this paper, we slightly modify its reference settling condition. At the end of $k$-th episode, for any $(s,h),$ the algorithm holds $V_{h}^{k+1}(s),V_{h}^{\textnormal{LCB},k+1}(s)$, the estimated upper and lower bounds for $V_{h}^{\star}(s)$, respectively. When $|V_{h}^{k+1}(s)-V_{h}^{\textnormal{LCB},k+1}(s)|\leq\beta$ holds for the first time, it settles the reference function value $V_{h}^{{\textnormal{R}}}(s)$ as $V_{h}^{k+1}(s)$. Li et al. () set $\beta=1$ for worst-case MDPs. Our paper treats $\beta$ as a hyper-parameter within $(0,H]$ to allow better control over the learning process. Algorithms 2 and 3 provide our refined version. For the rest of this paper, we still call it Q-EarlySettled-Advantage without special notice.

Theorem 3.2 provide the expected regret upper bound of Q-EarlySettled-Advantage.

###### Theorem 3.2 .

For Q-EarlySettled-Advantage (Algorithms 2 and 3 in Appendix B: Algorithm details of Q-EarlySettled-Advantage) with $\beta\in(0,H]$, $\mathbb{E}[\textnormal{Regret}(T)]$ is upper bounded by Equation 3.

Next, we compare the results of both theorems with the worst-case regrets in Zhang et al. (); Li et al. () and the gap-dependent regrets in Yang et al. (); Xu et al. ().

Comparisons with Zhang et al. (); Li et al. (). Since the regrets showed in Equations 2 and 3 are logarithmic in $T$, they are better than the worst-case regret $\tilde{O}(\sqrt{H^{2}SAT})$. In addition, our results imply new guidance on setting the hyper-parameter $\beta$ for the gap-dependent regret, which is different from $\beta=1/\sqrt{H}$ in Zhang et al. ()and $\beta=1$ in Li et al. (), respectively. When $\mathbb{Q}^{\star}=0$ which will happen when the MDP is deterministic, if we set $\beta=\tilde{\Theta}(H(S\Delta_{\textnormal{min}})^{1/4})$ for UCB-Advantage and $\beta=\tilde{\Theta}(H\Delta_{\textnormal{min}}^{1/3})$, the gap-dependent regrets will linearly depend on $\Delta_{\textnormal{min}}^{-1/2}$ and $\Delta_{\textnormal{min}}^{-1/3}$, respectively. This provides new guidance on setting $\beta$ when we have prior knowledge about $\Delta_{\textnormal{min}}$. When $0<\mathbb{Q}^{\star}\leq H^{2}$, the best available gap-dependent regret becomes $\tilde{\Theta}(\mathbb{Q}^{\star}H^{2}SA)$ which holds when $\beta\leq\sqrt{\mathbb{Q}^{\star}/H}$. Knowing that the gap-free terms in Equations 2 and 3 monotonically decrease in $\beta$, we will recommend setting $\beta=\tilde{O}(\sqrt{\mathbb{Q}^{\star}/H})$ if prior knowledge on $\mathbb{Q}^{\star}$ is available.

Comparisons with Yang et al. (); Xu et al. (). The gap-dependent regret for Yang et al. () is provided in Equation 1. For the multi-step bootstrapping in Xu et al. (), their regret bound contains a term

$$ $O\left(\sum_{h=1}^{H}\sum_{s\in\mathcal{S}}\left(\sum_{a\neq\pi_{h}^{\star}(s) }\frac{H^{5}}{\Delta_{h}(s,a)}\right)\log(SAT)\right).$ (6) $$

In MDPs where $\Delta_{h}(s,a)=\Theta(\Delta_{\textnormal{min}})$ for $\Theta(HSA)$ state-action-step triples (e.g. the example in (Xu et al., , Theorem 1.3)), their regret reduces to Equation 1.

Next, we compare Equations 2 and 3 with Equation 1. Under the worst-case variance $\mathbb{Q}^{\star}=\Theta(H^{2})$ and letting $\beta$ be $\Theta(1/\sqrt{H})$ or $\Theta(1)$ which are the recommendations in Zhang et al. (); Li et al. () respectively for the worst-case MDPs, the common gap-dependent term Equations 2 and 3 becomes $\tilde{O}(H^{5}SA/\Delta_{\textnormal{min}})$, which is better than Equation 1 by a factor of $H$. Under the best variance $\mathbb{Q}^{\star}=0$, the gap-dependent term becomes $\tilde{O}(\beta^{2}H^{4}SA/\Delta_{\textnormal{min}})$, which is better than Equation 1 for any $\beta\in(0,H]$. In addition, our best possible gap-dependent regret that is sublinear in $\Delta_{\textnormal{min}}^{-1}$ is also intrinsically better. Here, we remark that the proof in Yang et al. (); Xu et al. () cannot benefit from $\mathbb{Q}^{\star}=0$ due to their use of Hoeffding-type bonuses.

We also comment on the gap-free terms in Equations 2 and 3. They are dominated by the gap-dependent term as long as $\Delta_{\textnormal{min}}\leq\tilde{O}(\mbox{poly}((HSA)^{-1},\beta))$ for some polynomial $\mbox{poly}(\cdot)$. In addition, the gap-free term in Equation 3 is linear in $S$, which is better than that for Equation 2 thanks to Q-EarlySettled-Advantage algorithm. It utilizes both upper confidence bounds and lower confidence bounds for $V$-functions to settle the reference function.

###### Theorem 3.1 .

###### Theorem 3.2 .

### 3.3 Gap-Dependent Policy Switching Cost for UCB-Advantage

Different from Q-EarlySettled-Advantage, UCB-Advantage uses the stage design for updating the estimated $Q$-function. For each $(s,a,h)$, Zhang et al. () divided the visits into consecutive stages with the stage size increasing exponentially. It updates the estimated $Q$-function only at the end of each stage so that the policy switches infrequently. Theorem 3.3 provides the policy switching cost for UCB-Advantage

###### Theorem 3.3 .

For UCB-Advantage (Algorithm 1 in Appendix A: Algorithm details of UCB-Advantage) with $\beta\in(0,H]$ and any $\delta\in(0,1)$, with probability at least $1-\delta$, $N_{\textnormal{switch}}$ is upper bounded by Equation 4. Here, $D_{\textnormal{opt}}=\{(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]|a=\pi_{
h}^{\star}(s)\}$, and $D_{\textnormal{opt}}^{c}=(\mathcal{S}\times\mathcal{A}\times[H])\backslash D_{
\textnormal{opt}}$.

Comparisons with existing works. The first term in Equation 4 logarithmically depends on $T$ and the second one logarithmically depends on $1/\Delta_{\textnormal{min}}$ and $\log T$. Next, we compare our result with $O(H^{2}SA\log T)$ in Zhang et al. (), which is the best available switching cost for model-free methods in the literature. For the first term in Equation 4, knowing that $|D_{\textnormal{opt}}|<HSA$ for all non-degenerated MDPs where there exists at least one state such that not all actions are optimal, the coefficient is better than Equation 4. Specifically, if each state has a unique optimal action so that $|D_{\textnormal{opt}}|=SH$, Equation 4 becomes

$$ $O\left(H^{2}S\log\left(\frac{T}{H^{2}S}+1\right)+H^{2}SA\log\left(\frac{H^{ \frac{7}{2}}S^{\frac{1}{2}}\log(\frac{SAT}{\delta})}{\beta\Delta_{\textnormal{ min}}}\right)\right)$ $$

where coefficient in the first term is better than Equation 4 by a factor of $A$.

For the second term in Equation 4, when the total steps are sufficiently large such that $T=\tilde{\Omega}\left(\mbox{poly}\left(SAH,(\beta\Delta_{\textnormal{min}})^{-
1}\right)\right)$ for some polynomial $\mbox{poly}(\cdot)$, it is also better than $O(H^{2}SA\log T)$.

Key Ideas of the Proof.
The proof of Theorem 2 in Zhang et al. () implies

$$ $N_{\textnormal{switch}}\leq\sum_{s,a,h}4H\log\left(\frac{N_{h}^{K+1}(s,a)}{2H} +1\right)$ $$

where $N_{h}^{K+1}(s,a)$ is upper bounded by the total number of visits to $(s,a,h)$. Under their worst-case MDP and noticing that $\sum_{s,a,h}N_{h}^{K+1}(s,a)\leq T$, Zhang et al. () further proved their bound $O(H^{2}SA\log T)$ by applying Jensen’s inequality. In our gap-dependent analysis, it can be shown that with high probability, $\sum_{(s,a,h)\in D_{\textnormal{opt}}^{c}}N_{h}^{K+1}(s,a)\leq\tilde{O}\left(
\frac{H^{6}SA}{\Delta_{\textnormal{min}}}+\frac{H^{8}S^{2}A}{\beta^{2}}\right)$, which is much smaller than $T$ when $T$ is sufficiently large. This implies the discrepancy among the number of visits to state-action-step triples with optimal or suboptimal actions. Accordingly, we prove the bound in Equation 4 by using Jensen’s inequality separately for triples with optimal or suboptimal actions.

###### Theorem 3.3 .

## 4 Conclusion

In this paper, we have presented the first gap-dependent regret analysis for $Q$-learning using reference-advantage decomposition and also provided the first gap-dependent analysis on the policy switching cost of $Q$-learning, which answers two important open questions. Our novel error decomposition approach and construction of surrogate reference functions can be used in other problems using reference-advantage decomposition such as the offline $Q$-learning and stochastic learning.

## Appendix A: Algorithm details of UCB-Advantage

The UCB-Advantage algorithm, first introduced in Zhang et al. (), achieves the information-theoretic bound on regret up to logarithmic factors, using a model-free algorithm. The key innovation of the algorithm lies in its combination of UCB exploration (Jin et al., ) with a newly introduced reference-advantage decomposition for updating $Q$-estimates.

Before discussing the algorithm in detail, we will first review the special stage design used in the algorithm. For any triple $(s,a,h)$, we divide the samples received for the triple into consecutive stages. Define $e_{1}=H$ and $e_{i+1}=\left\lfloor(1+\frac{1}{H})e_{i}\right\rfloor$ for all $i\geq 1$, standing for the length of the stages. We also let $\mathcal{L}:=\{\sum_{i=1}^{j}e_{i}|j=1,2,3,\ldots\}$ be the set of indices marking the ends of the stages.

We note that the definition of stages is with respect to the triple $(s,a,h)$. For any fixed pair of $k$ and $h$, let $(s_{h}^{k},a_{h}^{k})$ be the state-action pair at the $h$-th step during the $k$-th episode of the algorithm. We say that $(k,h)$ falls in the $j$-th stage of $(s,a,h)$ if and only if $(s,a)=(s_{h}^{k},a_{h}^{k})$ and the total visit number of $(s_{h}^{k},a_{h}^{k})$ after the $k$-th episode is in $(\sum_{i=1}^{j-1}e_{i},\sum_{i=1}^{j}e_{i}]$.

Now we introduce the stage-based update framework. For any $(s,a,h)$ triple, we update $Q_{h}(s,a)$ when the total visit number of $(s,a,h)$ reaches the end of the current stage (in other words, the total visit number occurs in $\mathcal{L}$). For $k$-th episode at the end of a given stage, the $Q$-estimate $Q_{h}^{1,k+1}(s_{h}^{k},a_{h}^{k})$ learned from UCB is updated to:

$$ $Q_{h}^{1,k+1}(s_{h}^{k},a_{h}^{k})=r_{h}^{k}(s_{h}^{k},a_{h}^{k})+\frac{1}{{ \check{n}}_{h}^{k}}\sum_{i=1}^{{\check{n}}_{h}^{k}}V_{h+1}^{k^{{\check{l}_{i}} }}(s_{h+1}^{{\check{l}_{i}}})+2\sqrt{\frac{H^{2}\iota}{{\check{n}}_{h}^{k}}}.$ (7) $$

Here we define ${\check{n}}_{h}^{k}={\check{n}}_{h}^{k}(s^{k}_{h},a^{k}_{h})$ be the number of visits to $(s_{h}^{k},a_{h}^{k},h)$ during the stage immediately before the stage of $k$-th episode and ${\check{l}_{i}}=\check{l}_{h,k}^{i}$ denotes the index of the $i$-th episode among the ${\check{n}}_{h}^{k}$ episodes. $V_{h}^{k}(s)$ is the $V$-estimate at the end of the episode $k-1$ with the initial value $V_{h}^{1}(s)=H$. The term $2\sqrt{\frac{H^{2}\iota}{{\check{n}}_{h}^{k}}}$ represents the exploration bonus for ${\check{n}}_{h}^{k}$-th visit, where $\iota=\log(\frac{2}{p})$ with $p\in(0,1)$ being failure probability.

The other estimate, denoted by $Q_{h}^{2,k+1}(s_{h}^{k},a_{h}^{k})$, uses the reference-advantage decomposition technique. For $k$-th episode at the end of a given stage, it is updated to:

$$ $Q_{h}^{2,k+1}(s_{h}^{k},a_{h}^{k})=r_{h}^{k}(s_{h}^{k},a_{h}^{k})+\frac{1}{n_{ h}^{k}}\sum_{i=1}^{n_{h}^{k}}V_{h+1}^{{\textnormal{ref}},k^{l_{i}}}(s_{h+1}^{l _{i}})+\frac{1}{{\check{n}}_{h}^{k}}\sum_{i=1}^{{\check{n}}_{h}^{k}}\left(V_{h +1}^{k^{{\check{l}_{i}}}}-V_{h+1}^{{\textnormal{ref}},k^{{\check{l}_{i}}}} \right)(s_{h+1}^{{\check{l}_{i}}})+b_{h}^{k+1}(s_{h}^{k},a_{h}^{k}).$ (8) $$

Here we define $n_{h}^{k}=n_{h}^{k}(s^{k}_{h},a^{k}_{h})$ be the number of visits to $(s_{h}^{k},a_{h}^{k},h)$ prior to the stage of $(k)$-th episode and $l_{i}=l_{h,{k}}^{i}$ denotes the index of $i$-th episode among the $n_{h}^{k}$ episodes.

In Equation 8, $V_{h}^{{\textnormal{ref}},k}(s)$ is the reference function learned at the end of episode $k-1$.

We expect that for any $s\in\mathcal{S}$, sufficiently large $k$ and some given $\beta\in(0,H]$, it holds $|V_{h}^{{\textnormal{ref}},k}(s)-V_{h}^{\star}(s)|\leq\beta$. In this case, for $s_{h+1}^{k^{n}}\sim\mathbb{P}_{h}(\cdot|s_{h}^{k^{n}},a_{h}^{k^{n}})$, the variance of the advantage term $V_{h+1}^{k^{{\check{l}_{i}}}}(s_{h+1}^{k^{n}})-V_{h+1}^{{\textnormal{ref}},k^{
{\check{l}_{i}}}}(s_{h+1}^{k^{{\check{l}_{i}}}})$, is bounded by $\beta^{2}$, which can be less volatile than the stochastic term $V_{h+1}^{k^{{\check{l}_{i}}}}(s_{h+1}^{k^{{\check{l}_{i}}}})$, whose variance can be $H^{2}$. Meanwhile, the reference term $\sum_{i=1}^{n_{h}^{k}}V_{h+1}^{{\textnormal{ref}},k^{l_{i}}}(s_{h+1}^{k^{l_{i}
}})/n_{h}^{k}$ use a batch of historical visits to $(s_{h}^{k},a_{h}^{k},h)$, which can lower the variance as the increase of the sample size $n_{h}^{k}$. Accordingly, the exploration bonus term $b_{h}^{k+1}$ is taken to be an upper confidence bound for the above-mentioned two terms combined.

With these $Q$-estimates, we can update the final $Q$-estimate as follows:

$$ $Q_{h}^{k+1}(s_{h}^{k},a_{h}^{k})=\min\{Q_{h}^{1,k+1}(s_{h}^{k},a_{h}^{k}),Q_{h }^{2,k+1}(s_{h}^{k},a_{h}^{k}),Q_{h}^{k}(s_{h}^{k},a_{h}^{k})\}.$ (9) $$

We also incorporate $Q_{h}^{k}(s_{h}^{k},a_{h}^{k})$ here to keep the monotonicity of the update. Then we can learn $V_{h}^{k+1}(s_{h}^{k})$ by a greedy policy with respect to the $Q$-estimates $V_{h}^{k+1}(s_{h}^{k})=\max_{a}Q_{h}^{k+1}(s_{h}^{k},a)$.
If the number of visits to the state-step pair $(s,h)$ first exceeds $N_{0}=O(\frac{SAH^{5}\iota}{\beta^{2}})$ at $k$-th episode, then we learn the final reference function $V_{h}^{{\textnormal{REF}}}(s)=V_{h}^{k+1}(s)$. For the reader’s convenience, we have also provided the detailed algorithm below.

Figure: Algorithm 1 UCB-Advantage

The accumulators in the algorithm are updated as follows.

$$ $\displaystyle\check{\mu}:=\check{\mu}_{h}(s_{h},a_{h})\xleftarrow{+}V_{h+1}(s_ {h+1})-V^{\text{ref}}_{h+1}(s_{h+1});\quad\check{v}:=\check{v}_{h}(s_{h},a_{h} )\xleftarrow{+}V_{h+1}(s_{h+1});$ (10) $\displaystyle\check{\sigma}:=\check{\sigma}_{h}(s_{h},a_{h})\xleftarrow{+} \left(V_{h+1}(s_{h+1})-V^{\text{ref}}_{h+1}(s_{h+1})\right)^{2};$ (11) $$

Meanwhile, the following two types of global accumulators are used for the samples in all stages

$$ $\displaystyle\mu^{\text{ref}}:=\mu^{\text{ref}}_{h}(s_{h},a_{h})\leftarrow V^{ \text{ref}}_{h+1}(s_{h+1});\quad\sigma^{\text{ref}}:=\sigma^{\text{ref}}(s_{h} ,a_{h})\leftarrow\left(V^{\text{ref}}_{h+1}(s_{h+1})\right)^{2}.$ (12) $$

We use $\mu^{\text{ref},k}_{h}$, $\sigma^{\text{ref},k}_{h}$, $\check{\mu}_{h}^{k}$, $\check{v}_{h}^{k}$, $\check{\sigma}_{h}^{k}$, $b_{h}^{k}$ to denote respectively the values of $\mu^{\text{ref}}$, $\sigma^{\text{ref}}$, $\check{\mu}$, $\check{v}$, $\check{\sigma}$, $b$ at step $h$ by the start of the $k$-th episode.

## Appendix B: Algorithm details of Q-EarlySettled-Advantage

Let us briefly introduce the refined algorithm, which is similar to the original version in Li et al. (). Before diving into the algorithm itself, we will first discuss the key auxiliary functions used for estimating the $Q$-value functions. For any $\delta\in[0,1]$, let $\iota=\log(\frac{SAT}{\delta})$.

In the algorithm, $\mu_{h}^{{\textnormal{ref}}}$ and $\sigma_{h}^{{\textnormal{ref}}}$ are updated to represent the current mean and second moment of the reference function. $\mu_{h}^{{\textnormal{adv}}}$ and $\sigma_{h}^{{\textnormal{adv}}}$ are updated to be the current weighted mean and weighted second moment of the reference function with weight to be the learning rate $\eta_{n}=\frac{H+1}{H+n}$. $b_{h}^{{\textnormal{R}}}$ is the exploration bonus for Q-EarlySettled-Advantage. With these updated functions, we can then discuss the Q-EarlySettled-Advantage algorithm.

Figure: Algorithm 2 Auxiliary functions

Figure: Algorithm 3 Refined Q-EarlySettled-Advantage

At the beginning of the $k$-th episode, we can obtain $V$-estimate $V_{h}^{k}(s)$, the reference function $V_{h}^{{\textnormal{R}},k}(s)$ and the policy $\pi^{k}$ from the previous episode $k-1$ and select an initial state $s_{1}^{k}$ (For the first episode, we randomly choose a policy $\pi^{1}$ and $V_{h}^{1}(s)=V_{h}^{{\textnormal{R}},1}=H$). At step $h\in[H]$, we can process the trajectory with $a_{h}^{k}=\pi_{h}^{k}(s_{h}^{k})$ and $s_{h+1}^{k}\sim\mathbb{P}_{h}(\cdot|s_{h}^{k},a_{h}^{k})$. Now we need to update the estimates of both $Q$-value and $V$-value functions at the end of $k$-th episode. In the algorithm, the estimate learned from the UCB by the end of $k$-th episode, denoted as $Q_{h}^{\textnormal{UCB},k+1}$, is updated to:

$$ $Q_{h}^{\textnormal{UCB},k+1}=r_{h}^{k}(s_{h}^{k},a_{h}^{k})+\sum_{n=1}^{N_{h}^ {k}}\eta_{n}^{N_{h}^{k}}\left(V_{h+1}^{k^{n}}(s_{h+1}^{k^{n}})+c_{b}\sqrt{ \frac{H^{3}\iota}{n}}\right)$ (13) $$

Here we define $N^{k}_{h}=N^{k}_{h}(s^{k}_{h},a^{k}_{h})$ as the number of times that the state-action pair $(s^{k}_{h},a^{k}_{h})$ has been visited at step $h$ at the beginning of the $k$-th episode and $k^{n}=k^{n}_{h}(s^{k}_{h},a^{k}_{h})$ denotes the index of the episode in which the state-action pair $(s^{k}_{h},a^{k}_{h})$ is visited for the $n$-th time at step $h$. The term $c_{b}\sqrt{\frac{H^{3}\iota}{n}}$ represents the exploration bonus for $n$-th visit, where $c_{b}>0$ is a sufficiently large constant.

Another $Q$-estimate obtained from LCB at the end of $k$-th episode, denoted as $Q_{h}^{\textnormal{LCB},k+1}$, is updated similarly to $Q_{h}^{\textnormal{UCB},k+1}$, but with the exploration bonus subtracted instead.

The last estimate of $Q$-value function, denoted as $Q_{h}^{{\textnormal{R}},k+1}$, uses reference-advantage decomposition techniques. At the end of $k$-th episode, $Q_{h}^{{\textnormal{R}},k+1}$ is updated to:

$$ $Q_{h}^{{\textnormal{R}},k+1}=r_{h}^{k}(s_{h}^{k},a_{h}^{k})+\sum_{n=1}^{N_{h}^ {k}}\eta_{n}^{N_{h}^{k}}\Big{(}V_{h+1}^{k^{n}}(s_{h+1}^{k^{n}})-V_{h+1}^{{ \textnormal{R}},k^{n}}(s_{h+1}^{k^{n}})+\frac{\sum_{i=1}^{n}V_{h+1}^{{ \textnormal{R}},k^{i}}(s_{h+1}^{k^{i}})}{n}+b_{h}^{{\textnormal{R}},k^{n}+1} \Big{)}.$ (14) $$

In Equation 14, $V_{h}^{{\textnormal{R}},k}(s)$ is the reference function learned at the end of episode $k-1$. The key idea of the reference-advantage decomposition is that we expect to maintain a collection of reference values $\{V_{h}^{{\textnormal{R}},k}(s)\}_{s,k,h}$, which form reasonable estimates of $\{V_{h}^{\star}(s)\}_{s,h}$ and become increasingly more accurate as the algorithm progresses. It means for any $s\in\mathcal{S}$, sufficiently large $k$ and some given $\beta\in(0,H]$, it holds $|V_{h}^{{\textnormal{R}},k}(s)-V_{h}^{\star}(s)|\leq\beta$. In this case, for $s_{h+1}^{k^{n}}\sim\mathbb{P}_{h}(\cdot|s_{h}^{k^{n}},a_{h}^{k^{n}})$, the variance of the advantage term $V_{h+1}^{k^{n}}(s_{h+1}^{k^{n}})-V_{h+1}^{{\textnormal{R}},k^{n}}(s_{h+1}^{k^{
{\check{l}_{i}}}})$, is bounded by $\beta^{2}$, which can be less volatile than the stochastic term $V_{h+1}^{k^{n}}(s_{h+1}^{k^{n}})$. Meanwhile, the reference term $\sum_{i=1}^{n}V_{h+1}^{{\textnormal{R}},k^{i}}(s_{h+1}^{k^{i}})/n$ use a batch of historical visits to $(s_{h}^{k},a_{h}^{k},h)$, which can lower the variance as the increase of the sample size $n$. Accordingly, the exploration bonus term $b_{h}^{{\textnormal{R}},k^{n}+1}$ is taken to be an upper confidence bound for the above-mentioned two terms combined. Given that the uncertainty of Equation 14 largely stems from the advantage and the reference terms (which can both be much smaller than the variability in Equation 13), the incorporation of the reference function helps accelerate convergence and lower the regret upper bound.

With two additional Q-estimates in hand — $Q_{h}^{\textnormal{UCB},k+1}$ learned from UCB and $Q_{h}^{{\textnormal{R}},k+1}$ obtained from the reference-advantage decomposition, it is natural to combine them as follows to further reduce the bias without violating the optimism principle:

$$ $Q_{h}^{k+1}(s_{h}^{k},a_{h}^{k})=\min\{Q_{h}^{\textnormal{UCB},k+1}(s_{h}^{k}, a_{h}^{k}),Q_{h}^{{\textnormal{R}},k+1}(s_{h}^{k},a_{h}^{k}),Q_{h}^{k}(s_{h}^{ k},a_{h}^{k})\}.$ (15) $$

We also incorporate $Q_{h}^{k}(s_{h}^{k},a_{h}^{k})$ here to keep the monotonicity of the update. Then we can learn $V_{h}^{k+1}(s_{h}^{k},a_{h}^{k})$ and $V_{h}^{\textnormal{LCB},k+1}(s_{h}^{k},a_{h}^{k})$ by a greedy policy with respect to these $Q$-estimates:

$$ $V_{h}^{k+1}(s_{h}^{k})=\max_{a}Q_{h}^{k+1}(s_{h}^{k},a)\textnormal{, }V_{h}^{ \text{LCB},k+1}(s_{h}^{k})=\max\left\{\max_{a}Q_{h}^{\text{LCB},k+1}(s_{h}^{k} ,a),V_{h}^{\text{LCB},k}(s_{h}^{k})\right\}.$ $$

In the algorithm, $V_{h}^{\text{LCB},k}(s)$ is used as lower bound estimates of $V_{h}^{\star}(s)$. We learn the final value $V_{h}^{{\textnormal{R}}}(s)$ of the reference function for the state-step pair $(s,h)$ when the condition $V_{h}^{k}(s)-V_{h}^{\text{LCB},k}(s)\leq\beta$ holds for the first time.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: Is it possible to demonstrate how close the provided regret upper bounds are to optimality? Are there gap-dependent regret lower bounds?
soundness: 3
strengths: - Improved gap-dependent regret upper bounds for learning finite-horizon episodic MDPs are provided.
- The guarantees are obtained by analyzing some existing near-optimal algorithms for learning finite-horizon episodic MDPs.
- The regret analysis based on decomposing the errors into reference estimations, advantage estimations, and reference settling seems technically novel.
summary: This paper establishes improved gap-dependent upper bounds on finite-horizon episodic Markov decision processes (MDPs). There already exists a gap-dependent upper bound of $\tilde O( \Delta_{\min}^{-1} H^6 SA)$. To provide improved guarantees, the paper analyzes two algorithms with variance-aware regret-analysis, UCB-Advantage due to Zhang et al. 2020 and Q-EarlySettled-Advantage due to Li et al. 2021. The paper proves that both algorithms admit regret upper bounds of $\tilde O( \Delta_{\min}^{-1} H^5 SA)$.
weaknesses: -

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: I would like to better understand the level of technical contribution of this paper.
Why are surrogate reference functions needed in your analyses but not those of the previous works (Zhang et al 2020, Li et al 2021)?
Could you provide more discussion on exactly how the error/regret decomposition differs from previous work and why it is novel/what issues are being solved?

Could you provide more comparison and discussion of related work which is model-based and tries to achieve similar goals (gap and variance dependent guarantees)?
soundness: 3
strengths: The regret bounds achieved by the paper improve upon those of prior works.

The gap-dependent analysis of the switching cost is new, and I think it is interesting to expand gap-dependent analyses beyond the regret performance metric.

I am somewhat unclear on the level of technical contribution of the paper (see questions), but it seems like the analysis techniques may be useful for future work involving reference-advantage decomposition algorithmic ideas.
summary: The paper provides gap-dependent regret bounds for Q-learning-like algorithms which use variance estimation/also achieve variance dependent regret. They also provide an algorithm with a gap-dependent policy switching cost. The algorithms used (or small variations) appear in prior work. The authors describe a novel error decomposition and a surrogate reference function technique (which assists in the application of concentration inequalities) as main analytical contributions.
weaknesses: The proof sketch is not very easy to follow and does not seem very useful for an initial read of the paper. This is especially due to the fact that the statements of the algorithms are only provided in the appendix and many forward references are made. I think it would be more helpful if the algorithms (or maybe just one) were provided in the main body of the text and the proof sketch were shortened to focus on higher-level steps and main differences compared to prior works.

The contribution appears to be somewhat limited, since it is a re-analysis of existing algorithms and the level of technical contribution of the analysis is not fully clear to me (see questions below). It is very common in RL for the analysis of the same/similar algorithms to be gradually refined, but then I think it is very important that the authors do a good job highlighting the analytical improvements.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Since the hyperparameter $\beta$ plays a more important bound-dependent role in the gap-dependent bound compared to that of the worst-case bound. Is there an adaptive way of updating the hyperparameter \beta? Say initialize \beta to be sufficiently large at the beginning while decreasing it gradually as the estimates get more accurate.
soundness: 3
strengths: The analysis of "gap-dependent bound + reference-based algorithm" is novel and of interest to the RL theory study. 

The proof sketch is clearly written. I checked some technical parts of the paper, and they are correct to me. 

The technique of introducing an auxiliary "surrogate reference function" via cut-off based on optimal value function and $\beta$ to avoid non-martingale if using the last step reference function is new to gap-dependent bound.
summary: The paper analyzes the UCB-Advantage algorithm and a slightly modified version of the Q-EarlySettled-Advantage algorithms and provides the gap-dependent regret bounds and switching-cost bounds for them. Those two algorithms are worst-case optimal algorithms via references. Similarly, the gap-dependent regret bounds of such algorithms provided in this paper are better than the gap-dependent bounds of the algorithms without references in the literature. Discussions on the choice of hyperparameter $\beta$ and sketch of the proofs are clearly presented. For switching cost, analysis by separating the impact of the optimal and suboptimal actions is provided, so that the multiplicative factor before the leading order log(T) only depends on the tuples with optimal actions.
weaknesses: I did not see major weaknesses in the paper. Here are some minor/barely ones. 

In the discussion "Comparisons with Zhang et al. (2020); Li et al. (2021" after Theorem 3.3. The claim of better than worst-case since one is log(T) and the other is sqrt{T} is not quite fair. Either say it is asymptotic/for sufficiently large T, or discuss whether the proposed gap-dependent bounds can degrade to the worst-case bound naturally. The latter is worth investigating, but I do not see an immediate solution to this.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. In line 310, there is a typo fo$Q_h^k-Q_h^k$. 

2. In line 313, it seems questionable that the first term in G3 does not diminish to zero, while the regret should converge to zero as the episode k becomes sufficiently large.

3. Lemma B.3 seems incorrect when $\check{n}(s,a)=1$ immediately after a reset to 0.

4. The $N(s,a)$ in Algorithm 1 should be $n(s,a)$.
soundness: 3
strengths: 1. The author first proposes a novel algorithm that achieves a variance-aware regret bound with respect to the minimal sub-optimality gap.

2. The author also proposes an instance-dependent policy-switching cost for the UCB-Advantage algorithm, which could be of independent interest.

3. When variance is low (e.g., in deterministic transitions), the regret exhibits improved dependency on the minimal sub-optimality gap.
summary: This work studies the instance-dependent regret guarantee in tabular Markov Decision Processes. The author focuses on the minimal sub-optimality gap structure and provides a logarithmic regret guarantee for two existing algorithms: UCB-Advantage and Q-EarlySettled-Advantage. Compared with previous instance-dependent guarantees, this work achieves a variance-aware regret bound that improves by a factor of H even under maximum variance. Additionally, when variance is low (e.g., deterministic transitions), the regret demonstrates improved dependency on the minimal sub-optimality gap. Furthermore, the author also proposes a gap-dependent policy-switching cost for the UCB-Advantage algorithm.
weaknesses: The main weakness is that the improvement in this work over existing results appears too limited.

1. As discussed in line 264, the instance-dependent regret bound depends on the point-wise sub-optimality gap. In comparison, this work relies on the minimal sub-optimality gap across all state-action pairs. In most situations, the sub-optimality gap varies significantly across different state-action pairs, leading to a weaker performance in the regret guarantee presented in this work.

2. For the instance-dependent guarantee with zero variance, this work achieves a sub-linear dependency on the sub-optimality gap. However, a similar result already exists without relying on the minimal sub-optimality gap assumption [1]. Compared with previous results, this work demonstrates worse dependency on the episode length H and the sub-optimality gap.
[1] Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments

3. Regarding the gap-dependent policy-switching cost, the claim in line 136 appears incorrect. When the optimal action set is small, the dominant term in equation (4) becomes the second term, resulting in an improvement of only 
log T rather than a factor of A, which is minor.

4. Regarding technical novelty, the author claims the introduction of a surrogate reference function; however, the importance of this reference function is not clearly explained in section 3.2. It would be helpful to further highlight its effect in the proof sketch.

Meta-review: This submission studies gap-dependent bounds and policy switching cost for Q learning algorithms which use variance estimation. 

This paper gives novel gap-dependent variance-aware regret bounds, and provides an algorithm with a gap-dependent policy switching cost. These theoretical contributions could be of interest to the RL theory community. The reviewers also voted unanimously for acceptance.

Decision: Accept (Spotlight)