Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition
Authors: Zhong Zheng
Haochen Zhang
Lingzhou Xue
Venue: ICLR 2025 Spotlight (2025)
Keywords: Reinforcement Learning
Q-Learning
Regret
Primary area: reinforcement learning
TL;DR: This paper analyzes the gap-dependent regrets and policy switching costs of two Q-Learning algorithms with variance reduction.

Abstract: We study the gap-dependent bounds of two important algorithms for on-policy $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} $\sqrt{T}$-type regret bound in the worst-case scenario, where $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$-learning with Hoeffding-type bonuses, it remains an open question to establish gap-dependent regret bounds for $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$ and improve upon existing ones for $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$-learning using variance estimators and reference-advantage decomposition and also provides the first gap-dependent analysis on policy switching cost for $Q$-learning.

Published as a conference paper at ICLR 2025
GAP-DEPENDENT BOUNDS FOR Q-LEARNING USING INTERENCE-ADVANAAA DECOMPOSITION
Zhong Zheng, Haochen Zhang & Lingzhou Xue
Department of Statistics The Pennsylvania State University
State College, PA, 16802, USA {zvz5337, hgz Lzxue @psu. edu
ABSTRACT
We study the gap-dependent bounds of two important algorithms for on-policy Q- learning for finite-horizon episodic tabular Markov Decision Processes (MDPs): UCB-Advantage (Zhang et 2020) and Q-EarlySettled-Ane Advantage (Li et al. 2021). UCB- CCB-Advantage and Q-EarlySettled-AAvanee based on Hoeffding-type bonuses and achieve the almost optimal VT-type regret bound in the worst-case scenario, where is the total number of steps. How- ever, the benign structures of the MDPs such strictly positive suboptimality gap can significantly improve the regret. While gap-dependent regret bounds have been obtained for Q-learning with Hoeffding- bonuses, it remains open question to establish gap-dependent regret bounds for Q-learning using variance estimators their bonuses and reference-advantage decomposition for variance reduction. We develop a novel eтror decomposition framework to prove gap- dependent regret bounds of UCB-Advantage and D-EarlySetteed-Advaane are logarithmic in T and improve upon existing ones for Q-learning algorithms. Moreover, we establish the gap-dependent bound for the policy switching cost of UCB-Ad UCB-Advantage and improve that under the worst-case MDPs. To knowl- edge, this paper presents the first gap-dependent regret analysis for Q-learning using variance estimators and dffrence-advantaad decomposition and also pro- vides the first gap-dependent analysis on policy switching cost for Q-learning.
improve upon the results
that
INTRODUCTION
Reinforcement Learning (RL) (Sutton & Barto 2018 is subfield of machine learning focused on sequential decision-making, Often modeled as 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. 2016 2017, 2018) Vinyals et al. (019)). robotics (Kober al. 2013) Gu et al. 2017). and autonomous driving (Yurtsever et al.] 2020)..
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 5 states, A actions, and Hf steps per episode. The regret information bound for any MDP above and any learning algorithm with K episodes is O(HH2SAT) where T KH denotes the total number of steps (Jin et al.) 2018). Multiple RI. algorithms in the literature (e.g. Zhhnn et al. (2020); Li et al. 22021); Zhang et al. (2024)) have reached a near-optimal vTT-type regret that matches the information bound up logarithmic factors, which acts worst-case guarantee.
In practice, RI. algorithms often perform better than their worst-case guarantees, as such guaran- tees be significantly improved under MDPs with benign structures (Zanette Brunskill 2019) This motivates the problem-dependent analysis for algorithms that exploit the benign MDPs (c.g.. Wagenmaker al. (2022a); Zhou al. (2023): ZZhang et al. (2024)). One of the benign structures based on the dependency the positive suboptimality gap: for every state, the best action outper- forms others by a margin. It important because nearly all non -en-neeeeee environments with finite
*7. Zheng and H. Zhang co-first authors. I.. Xue the corresponding author.

---

Published as a conference paper at ICLR 2025
action sets satisfy some sub-optimality gap conditions (Yang al., 2021) Recently, [Simchowitz & Jamieson (2019) 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. 2021 Yang et al. 202T); Xu et al. (202T): Wang et al. 2 He et al. (2021), etc.
Model-free RL algorithms, the focus of this paper, are also called Q-learning algorithms and di- rectly learn the optimal action value function (Q-function) and state value function (V (V-function) to optimize the policy. It is widely used in practice due to its easy implementation (Jin et al. (0118) and the lower memory requirement that scales linearly in S while that for model-based algorithms scales quadratically. However, the literature on eap-dependent analysis for Q-learning is quite sparse. Yang et al.] (2021) studied the eap-dependent regret of the MCB-Hoeffding algorithm (Jin et al. 2018), the first model-free algorithm with a worst-case -tyyeee regret in the literature, and presented the first log Ttypee regret bound for model-free algorithms:
H S.A (Alog(SATT)
(1)
A
where Amin is defined as the minimum nonzero suboptimality gap for all the state-action-step triples.
Xu et al. (2021) proposed the multi-step bootstrapping algorithm and showed the same dependency on the minimum gap as Yang et al. (202T). 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. (2018) and achieve the almost optimal worst-case regret: UCB-Advantage (Zhang et al. 2020) and EarllySttteed-Adaaaae and Q-EarrySettled-Adiin Advantage use variance estimators in their bonuses and aeierennce-dvvntaaee de- composition for variance reduction. It remains an important open question whether such techniques can improve gap-dependent regret:
(Li et al. 2021). In particular, UCB-Advantage
Is it possible to establish potentially improved gap-dependent regret bound for Q-learning using variance estimators the bonuses and cnference-advantenn 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 UCD-Advat and Q-EarlySettled-AAvaale
which is very difficult as 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. (202T) for their non-optimism algo- rithm cannot bound the weighted sum of such errors, and the analysis frameworks in all optimism- based model-free algorithms including Jin et al. 2018); Zhang et al. (2020); Li et al. (2021): Yang al. (022I) can only bound the weighted sum under the simple Hoeftding-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., (2018), hardware placements (Mirhoseini et al. 2017), database optimization (Krish- nan et al. (2018), and material discovery (Nguyen et al. 2019). Under the worst-case MDPs, Bai et al. 2019) modified the algorithms Jnn et al. (2018) to reach switching cost of O O(H log 7", and UCB-Advantage (Zhang et al. 2020) reached an improved switching cost of O log T) due to the stage design in QQ-unccion update, both improving upon the cost of ((K) for regular Q-learning algorithms (e.g. Jiin et al. (2018). To our knowledge, none of existing works study gap-dependent switching cost for Q-learning algorithms, leaving this an open question..
Summary of our contributions. this paper, we give an affirmative answer to the open questions above by establishing gap-dependent regret bound for UCB-Advantage ZZhag al.) (020)) and BaallySetted-AAvaante
(Li et al.] 202I) 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 follows.
Improved Gap-Dependent Regret. Denote Q" E [o, H as the maximum conditional variance for the MDP and (0, H) the hyper-parameter settle the reference function. We prove that
2

---

Published as a conference paper at ICLR 2025
UCB- (CB-Advantage guarantees gap-dependent expected regret of H A log(S (og(SAA)) AT) (T)
o (100
(0- 32 H (SA()
(2)
A min
and (-EarlySetleed-AAvannee guarantees a gap-dependent expected regret of
of (Q [00 B1 log(AATT
Ho (SATT)
A A
These results are logarithmic in T and better than the worst-case vT regret in
Zhang et al. (2020); Li et al. (20TT) They also have a common gap-dependent term S min where (()) 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
((Q* + 32 H)
et al. 202T : Xu et al. (2021) in the following ways. (a) Under the worst-case Q
and setting B = O(1/VH H) as in Zhang et al. (2020) or 3 Q(1) as in Li et al. 2021
((Q* + H) (ASA)/Amm becomes
which is better than Equation by
a factor of H. (b) Under the best variance Q* 0 which will happen when the MDP is deter-
ministic, our regret in Equation (3) can linearly depend on Ó which is intrinsically better
than the dependency on Ami in Equation I (c) Since our gap-free terms also logarithmically
depend on T, they are smaller than Equation I when Amia is sufficiently small.
Gap-Dependent Policy Switching Cost. We can prove that for any (0, 1), with probability
at least 1 - ò, the policy switching cost for UCB-AuC ACB-Advantage is at most
of H Depul log
T Dup
+1) + H| log
H H log(
SAT 8
(4)
//12 VIDD
Amin
Here, Dopt is a subset of all state-action-stey triples and represents all triples such that the ac- tion is optimal. De is its complement, and gives the cardinality of the set. Next, we compare Equation (4) with the worst-case cost of O ( S log T) in Bai al. 2019)) and O 2 log T) in Zhang et al. (2020). Since Dopll < H SAA for non-degenerate MDPs, our first term in Equa- tion 44) better than the worst-case cost. Specifically, when each state has a unique optimal action so that |Doull HS, it implies the improvement by removing a factor of A compared with O(H2SA log T). This improvement is significant in applications with a large action space (e.g. recommender systems (Covington et al. 2016) and text-based games (Bellemare al. 2013)). )) For the second term where D opl < HSA in Equation 44), we also improve log to log log T. and the significance of such improvement pointed out by Qiao et al. 2002): Zhang et al. (022b).
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 Q to avoid using their upper bounds @(H²). 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
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
PRELIMINARIES
Throughout this paper, for any C' E N, we use [C] to denote the set 21. C). We use [[xx] to denote the indicator function, which equals when the event is true and 0 otherwise.
3

---

Published as a conference paper at ICLR 2025
Tabular episodic Markoy decision process (MDP). A tabular episodic MDP is denoted as M (S, A, H, F.P.Pr r), where S is the set of states with S = S, A is the set of actions with |A| = A, H is the number of steps in each episode, P {Px / is the transition kernel so that Pa( 8, s.a) characterizes the distribution over the next state given the state action pair (s, at step h, and r= (ra) are the deterministic reward functions with rh (s, a) [0. 1].
In each episode, an initial state 81 is selected arbitrarily by an adversary. Then, at each step h E [H] an agent observes state 8p E S, picks an action dn E A,, receives the reward rh Th (8h, ap.) and then transits to the next state 864-1- The episode ends when an absorbing state 8 is reached.
Later on, for ease of presentation, when we describe s, a. h, along with "any, each, all" or "V", we will omit the sets S, A. [H), [K]. We denote Ps = Es, 11 (f(5)+1) 1s = S, on a), V V = h. f (IP ())² and L,f = f(),, V(s, a, h) for any function f 8 + ER
Policies, state value functions, and action value functions. A policy x a collection of H func- tions/ {TH S - A [ where A is the set of probability distributions over A. A policy is deterministic if for any $ E S, TT concentrates all the probability mass on an action a E AA. In this case, we denote TT a. We use V S + R to denote the state value function at step h under policy т. Mathematically, (s) == En h' [s )-P((,)))) [Tw aN) sp. = s]. We also use Q7 S A R to denote the state-action value function at step h. i.e. Q7 a) := (s, a)
(sw axx Sh. = an = a]. Azar et al. 2017) proved that there al- ways exists an optimal policy 't that achieves the optimal value (+) = sup, (s) V (s) for all s S and h E [H]. The Bellman equation and the Bellman optimality equation are
En'=++1 B(r
Vī = (s)) (s) (s. == (5, a) + Ps,a, Vaat and (s. == (s, a) + P a. Vht ( 0, V(s, h).
(s) = max (s,
(5)
V (s) 0, assa,h))
For any problem with K episodes, let n² be the policy adopted in the k-th episode, and s be the corresponding initial state. The regret over T = H steps is RTg := Σ (Vi VT (st).
Suboptimality Gap. For any given MDP, we can provide the following formal definition.
Definition 2.1. For any (s, a, h). the suboptimality gap is defined as An (s, a) == (s(s) (s,
Equation 55) implies that (s a) 2 0, V(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 2.2. We define the minimum gap as Amin- == (s, (s > O, V(s, h)}-
We remark that if (s, a) : (s, > O, V(s, a, h)} 6. then all actions are optimal, leading
to degenerate MDP. Therefore, we assume that the set is nonempty and Amin > 0. Definitions 2.1
and 2.2 and the non-degeneration are standard in the literature on gap-dependent analysis (e.g. Sim-
chowitz & Jamieson 2019); Xu et al. (2020); Yang et al. (002)) Zhang et al. (222)).
Maximum Conditional Variance. This quantity is formally defined as follows.
Definition 2.3. We define the maximum conditional variance as Q" := max, a { aV (V (Vitt)).
Under our MDP with deterministic reward, Definition 2.3 coincides with that in Zanette & Brun- skill 2019) which performed variance-dependent regret analysis.
Policy Switching Cost. We provide the following definition for any algorithm with K > 1 episodes. Definition 2.4. The policy switching cost for K episodes is defined as Nuwitch
EK-1 ( Here, the sswineh(TT x') == Eses [TT()) # n (+)] represents the local switching cost for any policies and n².
This definition is also used in Bai et al. (0019) and Zhang et al, (0020).
MAIN RESULTS
This section presents the gap-dependent regret for UCB Udv-ndvat and --EarlySetleddAAvaattaee in Subsection 3. and the gap-dependent policy switching cost for -CB-Advattage in Subsection
3.3
We highlight new technical tool for the gap-dependent regret bound in Subsection 3.2
4

---

Published as a conference paper at ICLR 2025
3.1 GAP-DEPENDENT REGRETS
UCB-Advantage (Zhang al. 2020) is the first model-free algorithm that reaches almost opti- mal worst-case regret, which is also reached by LeeySStteed-AAvattaaae (Li et al. 2021). Both algorithms optimism-basede use upper confidence bounds (UCB) for exploration, and employ variance estimators and seference-advantage decomposition. UCB-Advantage settles the reference function each (s, ft) by comparing the number of visits threshold that relies on a hyper- parameter 3 E (0, H). For readers' convenience, we provide UCB-Advantage without any modifi- cation Algorithm of Appendix D.I
Theorem 3.1 provides the expected regret upper bound of UCB- ACB-Addantage.
Theorem 3.1. For UCB-Advantage (Algorithm in Appendix D.1 with 3 E (0, H), E[Regret(T)] is upper bounded by Equation
SeillySeetle-AAvantaa improved the burn-in cost of Zhang et al. (2220) for reaching the almost- optimal worst-case regret by using both estimated upper and lower confidence bounds for V 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*++((s)
VLCB,++ (s), the estimated
upper and lower bounds for Vi((s (+), respectively. When [V | (s) V VICB.+1 (8) S holds for the first time, it settles the reference function value (s) as (s). Li et al. (2021) set / = for worst-case MDPs. Our paper treats / hyper-parameter within (0, HJ to allow better control
over the learning process. Algorithms 2 and provide our refined version. For the rest of this paper, we still call it Q-EarlySettled Aatesttteeeeeedaaaaagaaee without special notice.
Theorem 3.2 provides the expected regret upper bound of Q-EarlySetlled
Theorem 3.2. For SaantySettled-Addvnaage (Algorithms and in Appendix F.1 with 3 (0, H). [[Regret(T)] is upper bounded by Equation 33.
The proof sketch of Theorem 3.2 is presented in Section explain our technical contributions. The
complete proofs of Theorems 3.1 and 3.2 are provided in Appendix and Appendix respectively.
Next, we compare the results of both theorems with the worst-case regrets in Zhang et al. (2020)
jt al. 202T) and the gap-dependent regrets Yang et al. (202T): Xu et al. (2021).
Comparisons with Zhang et al. (2020); Li et al. (2021). Since the regrets showed in Equa- tions 2 and (3) are logarithmic in T, they are better than the worst-case regret Ö(V
when T > (poly((HSA, A ())) where poly(-) represents some polynomial. In addition, results imply new guidance on setting the hyper-parameter ,3 for the gap-dependent regret, which different from | = 1/ VHH H in Zhang et al. (2020) and = in Li et al. (2021), respectively. When @* = which happens when the MDP is deterministic, if we set | θ (S(SAm 1/1) for UCB-Advantage and /3 @(HA the gap-dependent regrets will linearly depend on -112
1/2 and
A -1/3 1/3 min rrsspectively. This provides new guidance on setting 3 when we have prior knowledge about Amin- When 0 Q+ < H2, the best available gap-dependent regret becomes e H² which holds when B < / /H. Knowing that the gap-free terms in Equations 22) and monotonically decrease in 8, we will recommend setting 3 = Ö Q* (H) if prior knowledge on Q available.
Comparisons with Yang et al. (2021); : Xu et al. (202)). The gap-dependent regret for Yang et al. 2021 is provided in Equation For Xu et al. (2021) their regret bound given by:
ΣΣ
Σ
Zumul Amin
+ SA
HJ log(K)
(6)
An(s,a)
1=l (s)
where Zmul s, (h,,, = 0Λ 2 (s) 1} and Ztt (s) (alAx,s, 0}. In MDPs where (s(s, a) ((Amin) for e (SS)) state-action-ster triples (e.g. the example in Xu et al. 2021 Theorem 1.3)) or there are (A) optimal actions for each state-step pair (s, h), their regret
reduces Equation I.. which is worse than ours.
5

---

Published as a conference paper at ICLR 2025
Next, compare Equations and (3) with Equation 1 Under the worst-case variance ( and letting 3 be ((1/VH) @(1) which are the recommendations in Zhang et al. 202T respectively for the worst-case MDPs, the common gap-dependent term 2 and (3) becomes Ó SA/Amil which is better than Equation (1) by a factor of H. Under the best variance Q* = 0, the gap-dependent term becomes Ō H A Amin). which is better than Equation ① for any ,3 (0, Hr]. In addition, our best possible gap rap-dependent regret that is sublinear in A Am also intrinsically better. Here, remark that the proof in Yang et al. 2021);
@+
2020
ct al.
Equations
Xu et al. ) cannot benefit from Q = 0 due to their use of Hoeffding-type bonuses.
We also comment the gap-free terms in Equations (2) and (3). They dominated by the gap- dependent term long as Anin ((poly(HHSA)) 13)) 3)) for some polynomial poly(-). In addition,
the sup-free term in Equation (3) is linear in S, which better than that for Equation (2) thanks to the special design of MEEarlySetleed-Avvattae and lower confidence bounds for V /ffunctionss to settle the reference function.
algorithm. It utilizes both upper confidence bounds
3.2 OUR TECHNICAL TOOL: SURROGATE REFERENCE FUNCTIONS
We develop new technical tool in the proofs of both Theorems 3.1 and 3.2 the surrogate refer- ence functions. In this subsection, we explain it with the notations in the proof of Theorem 3.2 (Appendix [F.T] for Q-EarlySettled-AAwwe Advantaage while all the ideas also apply to UCB-Advantage. A more detailed proof sketch will be provided in the next section. For comprehensive explanation of we refer readers to Appendix [.
Q-EarlySettled-Advann
Before introducing the surrogate reference function, provide a brief overview of the key steps of Q-EarlySettled-Adwee Advalttgee Denote the estimated Q-function, the estimated V-function, and the reference function before the start of episode as Qf (s, a). (s), V-R, (s) and episode & as {(sh, ) Let N (s, a) be the number of visits to (s, o, h) before the start of episode k. Let No be short for N (sf af) and k" be the episode index for the n-th visit to (s) a h). While remaining unchanged for the unvisited triples, the estimated Q-function is updated on the visited ones:
R.k+ t (sh, a min( UCR, UCR,,++ (s at)), 2h ++1 (sh, (a,.a)).. Q% (sh, a he [H].
Here, Q UUB represents the Hoeffding-type estimation similar to Jin et al. 2018).. and advantage type estimation as follows:
Qh (sh at) represents the reference- seference-advantage
M++1 Nk11 mn
g (sh. ah) = (5 an
h++ (V
-VR.A"
RRAA"
No 11 h+1 + VN+1 + (8)
In Equation V A+1
RR 1+1
represents the running estimation of the advantage funetion, and
j that sum to nonnegative weights for the reference function. RAA++1 is the cumulative bonus that dominates the variances in the two weighted sums. Next, the estimated V-function and the reference function are also updated. For any (s, ht), when some reference settling condition related 3 triggered at the end of episode k, the reference function will be settled, which means that R.KK (s) Vi + (s)
(1h N%
j ..11 are the corresponding nonnegative weights that sum to 1. {up N N
for any k' > k 1. Thus, we call V +R,K+1 the reference function after the last episode as the settled reference function. SanrlySStteee-Adaaanet guarantees that for any (h, k) E [H] x [K]
Vi(( max Q% ()((s) arg max (s,
and
Qi S < Q < H. < V S VRA+I VRA < H, V/ S V/ < R.A.
(10)
Equations 9 and (TO) indicate that DarllSSttlled-Adaam updates the policy according to an upper bound Q of Qi.
is an optimism- based method that
Next, we introduce our surrogate reference functions v. They are defined as follows:
iyR,*(( (s) max (s), min (V. B, (s))), (s,),,
R.A
(11)

---

Published as a conference paper at ICLR 2025
We use the word "surrogate" because the algorithm does not rely it, and R- differs from the actual settled reference function V kR,,+1 V is determined before episode k. In addition, Equa- tion 10 implies that
Vi (8)
S P. (s) min (V) + B. R. (s) (s)) V(s,h,
(12)
and Lemmal F.5 in Appendix F2 shows that with high probability, & (s) coincides with the settled reference value Vil. (R.K+1
(s) after the settling condition is triggered.
Next, we discuss the usage of p. our error decompositions. Our proof relies on relating the regret to multiple groups of estimation emoor sums that take the form Σ M. Q1) ax)-
Here f ie nonnegative weights and i is the group index. Bounding the weighted sum via con-
trolling each individual (Q) - -2,, Q7) (s af)) by recursion on h a common technique for model-free optimism taasm algorithms, and it is also used by all of Yang et al. (202I); Zhang et al.
(2020) Li
iet al. (2021) Yang et al. (202I) used it on sup-deeendent regret analysis and Zhang et al. 2020
et al. 2021 used it to control the reference settling errors Ex=1 (V, R.K
(s )
However,
their techniques are only limited to the Hoeffding-typs update, where the errors generated in the re-
cursion take the simple form of Ö(v H3 /N)) where No is short for NN (s); aa)) When analyzing
the reference-advanterd type update, we face a more complicated error (Equation (14) in Section involving reference and advantage estimations, as well as bonuses with variance estimators.
Motivated by the structure of reference-advantagee decomposition, we decompose the estima- tion eтror into several components, focusing on the following four main terms: 91 := No No In=1 17n (P (aat
A" ski (V/B, Vi+t); G2 :2==> Uh No N
(1.gm. P P.t., V.R."" G3 fill
En (um 7/ No ) at V.RA" + + Un (V V. (*h+t1) and the bonus term 94- The first three terms correspond advantage estimation error, reference estimation error, and ref- erence settling error, respectively. Here, we creatively use the surrogate R.R.A as it is determined before the start of episode k. Thus, 91, 92 are martingale sums and can be controlled by concentra- tion incqualities. G3 corresponds to the reference settling error and can also be well-controlled given the settling conditions and properties of v- (s). G4 is controlled using the same idea of bounding G1, G2, Ga. h++1 is crucial to this process and cannot be replaced by the actual settled reference FR,K+1 used in Zhang et al. 2020y; Li et al. (2021). This is because VR.K+1 depends hi1
No
function h++1 on the whole learning process and causes non- non-martigalee issue in controlling G1. G2 and G3. To the best of our knowledge, we are the first to introduce the novel construction of reference surro- gates for reference-advantage advantage decomposition, which is of independent interest for future research on off-poll policy and offline methods.
3.3 GAP-DEPENDENT POLICY SWITCHING COST FOR UCB-ADVANTAGE
Different from SaaryySetled-Advaatte UCB-Advantage uses the stage design for updating the estimated Q-function. For each (x, a, h). Zhang et al. (0020) 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-Ad Advanaagee and the proof is provided in Appendix B
Theorem 3.3. For UCB-Advantaee (Algorithm | in Appendix D.I with B E (0. H and any 8 E
(0, 1), with probability at least - 5. Ngwitch is upper bounded by Equation (4) Here, Dopt = {(s, h) E S x A x [H] a (s)),,, where (s) {a arg max ()(s,a')); and De (S x A Dapi-
Comparisons with existing works. The first term in Equation (4) logarithmically depends on T and the second one logarithmically depends on 1/Amin and log T. Next, we compare our result with O T)) in Zhang et al. (2020). which is the best available policy switching cost for model- free methods in the literature. For the first term in Equation (4), knowing that [Doul 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 ( Specifically, if each state has unique optimal action so
7

---

Published as a conference paper at ICLR 2025
that |Dopl SH, Equation becomes O O S T'
12s + H log
(Hăs log 88
AAmi
where the coefficient in the first term outperforms that in Zhang al. (2020) by factor of A.
For the second term in Equation
4 when the total steps are sufficiently large such that T =
á (poly (SH, (34min) for some polynomial poly(-), is also better than O(H2SA log T)
Key Ideas of the Proof. The proof of Theorem 2 in Zhang et al. (2020) implies Nswithh S
Ex,.,h 4H log der their worst-case MDP and noticing that Exa,, No (s. N a) T, Zhang al. (2000) further proved their bound O(H2 T) by applying Jensen's 's inequality. In our gap-dependent anal- ysis, Equation (79) in Appendix shows that with high probability, E(s,,,)) -V, NK++ (s, s
+1] +1). where Noh N +s, a) is the total number of visits to (s, a)). Un-
2H
# 8 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 suboptimal ac- tions. Accordingly, we prove the bound in Equation by using Jensen's 's inequality separately for triples with optimal suboptimal actions.
Ö( SA
Auis
4 PROOF SKETCH OF THEOREM
This section provides a proof sketch to outline the key steps for proving Theorem 3.2 on the gap- dependent regret of Settllydetledddaaatta and explain our technical contributions. The key steps for proving Theorem 3.1 are similar except for different bounds reference settling error and gap-free regret terms. For space consideration, the proofs Theorem 3.1 are given in Appendix D
Notations.
First, introduce the weights used in the algorithm. Let nn N E N+. denote vi8
H4n For
and vo I (1 mh). For integers 1 S n S N, we also denote ni = No II (1 ne), and u. ΣN n//i. When N > O, they sat- isfy no -E nh EN uxy. For simplicity later, we the notations B Nē No 1(0 and Eeg = En un f*"""" pk"((""n)) for any functions I :S - R and INE un
ph 8 IR with &s N+, respectively. Similarly, we denote T Em Thn No [(shit)) and 1 B = En Uha No fk (sh We also denote Io = ΣnE, un P. Pot, af
Nº
pret p
No DNY, Un
P.t af se .P - The
No
P.t a Jel and Prak " = >NA In P
No
In what follows, we present the proof sketch of Theorem 3.2
Step I: Bounding Q Qi via decomposition and the surrogate reference function. The update of the estimated Q-function in Equations and (8) guarantees that
(
a 70 No H + ( ) + Endy (V/ RR,"" + Beet RRA""
+ R2..k
(13)
Here, Rhik is the cumulative bonus provided in Equation (98) in Appendix F.3.2 Together with No
@h at) rs(s a (1 To )TP af Vitz by Equation (5) and Bady (V
V.R.A" S
Eady h41 -.R.") implied by Equation 12). have
(Qt: - (s ah) S no No H RR ( V + Eret VRA - Vi+ =: G h41
Denote Vraer VRR. Vi then:
G Taudly (V/ Vitt)) (Payly Baudy ) h+1
vo + (Bret ph, )
V.R.E" + Rh.
Rhik 0 (14)
Here, k 0 Equation (96) in Appendix
= Hno No
R,A"
h+1 (RAAA") ) + (Fre D.R,"" - pady h+1 Equation (95) and h+1
F.3.1
show that for all (k, h) simultaneously, with high probability,
(IPady Brady p2adv,8" -Bady 1 h+1
<0(v
<0 <0
(V
H3² N
(BRR
PR. R.AAA 5 s0 (1/
Q + g2
N
NE
H
(15)
8

---

Published as a conference paper at ICLR 2025
Equation 15) corresponds to controlling 91 and G2, as discussed in Section 3.2 and holds because our surrogate reference function adapts to the learning process. To bound the bonus Rh.,, we also use the surrogate function i.R.K_ Equation (103) in Appendix F3.2 shows that for all (k, h) simulta- neously, with high probability
R =ō (V (10*+ + H /(N + HV HWL/NN)
(16)
where U En h+1 - V/R.A") (sh+ Equations 14) to 16 imply
(Qh (sh a I Bady (Viti Vitti) + (V (0+ + H H*
else (17)
where RALE = Ô 0010 H H
Fief h,k (VR411
TyR.K"-10 1 + (PRR) 1/441" - P 1 +
Remark 1: We use Q" in Equation 166 instead of its upper bound ( thanks to the variance estimator (line 16 of Algorithm 2 in Appendix F.I) used
(eEarlySetledd-Avaatte algorithm.
Step 2: Bounding the Weighted Sum. For any given h
[H] and non-negative weights
{wnn, J...j.,,,EEE ].]K]] we denote ||o|ooon = max Wh.k and ||w]|,, Eke[K] Wh,s- We also re-
cursively define wA, (h) for any h 5 h1' < HH E [K] as follows:
No.
(h) Wh,ki Wh+11,
>>
whyk & (h)mm
No I Vl. [K], ASh < H.
(18)
k=1n=1
Equation
18 implies the mapping from (wnnJa.K to {wN, (w)))(()) (h)) is linear. Let
[[w oc, Av' ma why (h) and [[w(H))l., Exe(K] wwy (h)). Then Equation (106 and
Equation 107 in Appendix (.4.)showws shows that
[1)(lo)o,, S (1 + 1/ 1/H)
(w))]l S [W)(h)l vh > h. (19)
Next, we bound the weighted sum I - (s az)) In Equation 17 where we take summations with regard to k on both sides and apply the standard summation rearrangement technique given in Appendix F.4.1 to the first term Degly ( 1h41 1)++), we have Ek=Thh (ht (2) S E Wh)La(h)
(sh +
EK_ Wh, (6 (V(@* + H32)/NK + HP(N)) 8) + Ek' Wh. Wh. Philk Recurring it with regard
to h h + ...., H. we have
Σ (Q) (sh oft S Re +
>>> Σ
whi A R
(20)
k= M1
where R. = Σ k= Σ#= WN W ( ((++++0++))) H33) + (NV)) 3/4). From Equation (19
and Lemma Appendix F2 follows that
R. S H + B²H v SA SAlWIbm,, HSA (
(21)
Step 3: Integrating Multiple Weighted Sums. Next, we consider multiple groups of weights. We
split the interval [Amin: H into N disjoint intervals I, : (2i-1Amin 2' "Amiin for E [N
and
IN = [2 min: H). Here, N = [log, (H/Amin)] For any given i E [N] and h E [H]. we
denote whik = [Q] ( a
(0) E I Then we have [|,, = max w h.k S and
2 Aiinl 11,,6
w 2 O @h) af) S 2 A miil
(22)
where || 11,6 EkE[K] Whikk Noticing that Σn Exm
(2)
K
Wh.k (Q)
( at)
>K (Q (st att Amin] where clip[æ|0] x1i 2 8). Equation (2
further implies
N
c (5) a Aminl = θ Σ
2'
Amin
min ||ا| 112,1
(23)

---

Published as a conference paper at ICLR 2025
Letting WA. whik in Equation (0) and applying Equations
21
and 22 we have
K
H
01 | 11. + 82 (1) 2' min (k0 I1 S δ
wh W le (h)
R
(24)
Here, 01 H2SA + 3,H 02 (SA) The weight (ww)(())) is defined recursively
by Equation
18)
with (/.c(h) = -hi,-- Solving this inequality (see Equation
112 ), we have
(Q" + +8² SAH?
H'SA
K
H
(2)
( 11, S
M/
44-1 min
(2 Amin)
2 Amin
This further implies
(Q+ (Q+ SAH?
H*SA
K H Σ
Σ 2' Ainn ( I1n 50
Wh & & B1)
(25)
Amin
A
min
k= -i
where (h) = EE Wh' (h). Noticing that @h, (h)
I( - (7) at) 2 Amin together
with the linearity showed in Equation (18)
Equation (99 implies WN (h) I O(1) for any h I
h < H. Thus, Σk- Σ Wh. (h) Ralse" with high probability,
O -m (2(ck)). Appendix R.5.2 shows that
ΣΣ
Σ
else
OAH3))
(26)
Summarizing Equations (3). 25 and (26) and noticing that H H SA/A min S $OBB215AA/
Amin +
HASA/B+ S//B) that follows from the AM-GM inequality, we have
clipl(Qft (5 a Aminl = Ō(SAII + H) min +
SA/3).
(27)
Remark 2: Integrating groups of sums is first introduced in Yang et al. (022 and also applied in Li ct al. (2021). It leads to regret dependency on 1/Amin instcad of 1/ A that will appear if we do not
use integration. We extend this method in handling Rac that only appears in our proof: we apply the upper bound in Equation (26) after the integration instead of Equation (24) before the integration.
This helps us remove the dependency on Amin in the second term in Equation (2
Remark 3: Equation (26p can be interpreted as bounding the reference settling errors, which is SertyySeeeee-dvvaaaaee UCB-Advantage and Q- --EarlSSetled-AAe ettteettelee mainly differ the reference settling policy, which results in different bounds for reference settling error and the gap-free regret terms in Equations and (3) the details in Appendix F.5.2
related to R2 and the reference settling design
We show
Step 4: Bounding the Expected Regret. By Equation (sh at) = (s/h 2 V. (sh). Thus, (sh aft) = (s)p[V/(()))) - (* aH) Amin] I clip[(Qft - (s att) Amin], V(k,)).
Equation (4) of Yang al. (021)) shows that E (Regret(K) D Σ# (a att then
E (Regret(K)) s E
clipi(Qi - (s a Amin]
(28)
==11=1
Using the definition of expectation (see Equation 123) in Appendix F.6 which connects Equa-
tion 27 to Equation (28).. we can derive the gap-dependent regret bound presented in Theorem 3.2
CONCLUSION
In this paper, we have presented the first gap-dependent regret analysis for Q-learning using eeference-advantire 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 decom- position approach and construction of surrogate reference functions can be used in other problems using inference-advantaee decomposition such the offline Q-learnig and stochastic learning.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENT
The work of Z. Zheng. H. Zhang, and L. Xue was supported by the U.S. National Science Founda- tion under the grants DMS-181 1552, DMS-1953189 and CCF-2007823 and by the U.S. National Institutes of Health under the grant IR0IGM152812.
REFERENCES
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with gener- ative model minimax optimal. In Conference on Learning Theory, pp. 67-83, PMLR, 2020.
Shipra Agrawal and Randy Jia, Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. Advances in Neural Information Processing Systems, 34:25852- 25864, 2021.
Amir H Ashouri, William Killian, John Cavazos, Gianluca Palermo, and Cristina Silvano. A survey on compiler autotuning using machine learning, ACM Computing Surveys (CSUR), 51(5):1-42, 2018.
Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. In Advances in Neural Information Processing Systems 19, pp. 49-56. MIT Press, 2007.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in Neural Information Processing Systems, 21, 2008
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017,
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In Proceedings of the 10th ACM Conference on Recommender Systems, pp. 191-198, 2016.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards account- able reinforcement learning. In International Conference on Machine Learning, pp. 1507-1516. PMLR, 2019.
Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value- function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34:1-12, 2021.
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. International Conference on Machine Learning, pp. 1049-1058. PMLR, 2017.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span-constrrinee exploration-explootttii in reinforcement learning. In International Conference on Machine Learning, pp. 1578-1586, PMLR, 2018.
Robert Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for machine learning. Proceedings of the IEEE, 108111):96881188) 2020.
Shixiang Gu, Ethan Holly. Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE International Confer- on Robotics and Automation (ICRA), pp. 3389-3336. IEEF, 2017.

---

Published as a conference paper at ICLR 2025
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning. pp. 4171-4180. PMLR. 2021.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi
cient? Advances in Neural Information Processing Systems, 31, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference Machine Learning, pp. 4870-4879. PMLR, 2020.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in Neural Information Processing Systems, 26, 2013.
Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33:1253-1261 2020.
Sham Kakade, Mengdi Wang, and Lin F Yang. Variance reduction methods for sublinear reinforce- ment learning. arXiv preprint arXiv: 080. 882.00184, 2018.
Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J Wainwright, and Michael Jordan. Is temporal difference learning optimal? an instance-dependent analysis. SIAM Journal on Mathe- matics of Data Science, 3(4):1013-1040, 2021.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, 32((1): (((1)):228-112) 1274, 2013.
Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein, and Ion Stoica. Learning to optimize join queries with deep reinforcement learning. arXiv preprint
2018.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction. Advances in Neural Information Processing Systems, 33:7031-7043, 2020.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762-17776. 2021.
Shicheng Liu and Minghui Zhu. Distributed inverse constrained reinforcement learning for multi- agent systems. Advances in Neural Information Processing Systems, 35:33444 -34466,, 2022.
Shicheng Liu and Minghui Zhu. Meta inverse constrained reinforcement learning: Convergence guarantee and generalization analysis. In The Twelfth International Conference on Learning Rep- resentations, 2023.
Shicheng Liu and Minghui Zhu. Learning multi-agent behaviors from distributed and streaming demonstrations. Advances in Neural Information Processing Systems, 36, 2024.
Shicheng Liu and Minghui Zhu. In-trajectory inverse reinforcement learning: Learn incrementally before an ongoing trajectory terminates. In The Thirly-eighth Annual Conference on Neural In- formation Processing Systems, 2025.
AA Marjani and Alexandre Proutiere. Best policy identification in discounted mdps: Problem- specific sample complexity. arXiv preprint arXiv:2009.1340: 2020.
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momen- tum g-learning: Correcting the bias without forgetting. In International Conference on Machine Learming, pp. 7609-7618. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2025
Azalia Mirhoseini, Hieu Pham, Quoe V Le, Benoit Steiner, Rasmus Larsen, Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi, Samy Bengio, and Jeff Dean. Device placement optimization with reinforcement learning. In International Conference Machine Learning, pp. 2430-2439, PMLR, 2017.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pp. 2613-26211 PMLR, 2017.
Phuoc Nguyen, Truyen Tran, Sunil Gupta, Santu Rana, Matthew Barnett, and Svetha Venkatesh. Incomplete conditional density estimation for fast materials discovery. In Proceedings of the 2019 SIAM International Conference on Data Mining, pp. 549-557. SIAM, 2019.
Thanh Nguyen-Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance- dependent bounds for offline reinforcement learning with linear function approximation, Pro- ceedings of the AAAI Conference Artificial Intelligence, volume 37, pp. 9310-9311 2023.
Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforcement
learning. Advances in Neural Information Processing Systems, 31, 2018
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficien reinforcement learning with loglog switching cost. In International Conference Machine Learning, pp. 18031-18061. PMLR, 2022.
Guanren Qiao, Guiliang Liu, Pascal Poupart, and Zhiqiang Xu. Multi-modal inverse constrained reinforcement learning from a mixture of demonstrations. Advances in Neural Information Pro- cessing Systems, 36, 2024.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. In International Conference Machine Learning, pp. 19967-20025. PMLR, 2022.
Aaron Sidford, Mengdi Wang. Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. Advances Neural Information Processing Systems, 31, 2018.
Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. Naval Research Logisties (NRL), 70(5):423- 442, 2023.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484-48, 2016.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint 17X1v:1712.01815 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419)) (1:411191111 140- 1144, 2018
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Sutton and A Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance- regret bounds for undis-
counted reinforcement learning in mdps. In Algorithmic Learning Theory, pp. 770-805. PMLR, 2018.
13

---

Published as a conference paper at ICLR 2025
Ambuj Tewari and Peter Bartlett. Optimistic linear programming gives logarithmic regret for irre- ducible mdps. In Advances in Neural Information Processing Systems 20: Proceedings of the 2007 Conference, pp. 1505-1512. Neural Information Processing Systems (NIPS) Foundation, 2008.
Andrea Tirinzoni, Aymen Al Marjani, and Emilie Kaufmann. Near instance-optimal pac reinforce- ment learning for deterministic mdps. Advances in neural information processing systems, 35: 1785-8798, 2022.
Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann. Optimistic pac reinforcement learn- ing: the instance-dependent view. In International Conference on Algorithmic Learning Theory, pp. 1460-1480. PMLR, 2023.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czameekki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):50-3544 2019.
Andrew Wagenmaker and Kevin G Jamieson. Instance-dependent near-optimal policy identification in linear mdps via online experiment design. Advances in Neural Information Processing Systems, 35:5968 5981, 2022.
Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. First- order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pp. 22384-22429, PMLR, 2022a.
Andrew Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance- dependent pac reinforcement learning. In Conference Learning Theory, pp. 358 418. PMLR, 2022b.
Hoi-To Wai, Mingyi Hong, Zhuoran Yang, Zhaoran Wang, and Kexin Tang. Variance reduced policy evaluation with smooth function approximation. Advances in Neural Information Processing Systems, 32, 2019.
Martin J Wainwright. 19Xiv 04697, 2019.
Variance-reduced y-learning is minimax optimal.
arXiv preprint
Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Pro- cessing Systems, 34: 1ee111354313333 2021.
Xinqi Wang, Qiwen Cui, and Simon S Du. On gap-dependent bounds for offline reinforcement learning, Advances in Neural Information Processing Systems, 35:14865-14877, 2022.
Haike Xu, Tengyu Ma, and Simon Du Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. In Conference on Learning Theory, pp. 4438 4472. PMLR, 2021.
Tengyu Xu, Zhe Wang, Yi Zhou, and Yingbin Liang. Reanalysis of variance reduced temporal difference learning. In International Conference on Learning Representations, 2020.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous q-learning. IEEE Transactions Information Theory, 2023.
Kunhe Yang, Lin Yang, and Simon Du Q-learning with logarithmic regret. In International Con- ference on Artificial Intelligence and Statistics, pp. 1576-1584. PMLR, 2021.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double
variance reduction. Advances in Neural Information Processing Systems, 34:7677-7688, 2021.
Ekim Yurtsever, Jacob Lambert, Alexander Carballo, and Kazuya Takeda. A survey of autonomous driving: Common practices and emerging technologies. IEEE Access, 8:58443-58469) 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-depentee regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
14

---

Published as a conference paper at ICLR 2025
Siliang Zeng, Chenliang Li, Alfredo Garcia, and Mingyi Hong. inforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 35:10122- 10135, 2022.
inverse
Haochen Zhang, Zhong Zheng, and Lingzhou Xue. Gap-dependent bounds for federated q-learning. arXiv preprinl arXiv:2502.02859, 2025.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33: 15198-15207, 2020.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pp-
4528 4531. PMLR, 2021a.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. In International Conference on Machine Learning, pp. 12653-12662. PMLR, 2021b.
Zihan Zhang, Xiangyang Ji, and Simon Du. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference on Learning Theory, pp. 3858-3904. PMLR, 2022a.
Zihan Zhang, Yuhang Jiang, Yuan Zhou, and Xiangyang Ji. Near-optimal regret bounds for multi- batch reinforcement learning. Advances in Neural Information Processing Systems, 35:24586- 24596, 2022b.
Zihan Zhang. Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. arXiv preprint arXiv:2307. 13586, 2023.
Zihan Zhang, Yuxin Chen, Jason Lee, and Simon Du. Settling the sample complexity of online reinforcement learning. In The Thirty Seventh Annual Conference on Learning Theory, pp. 5213- 5219. PMLR, 2024.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4977-5020. PMLR, 2023.
Zhong Zheng, Fengyu Gao, Lingzhou Xue, and Jing Yang. Federated q-learning: Linear regret speedup with low communication cost. In The Twelfth International Conference on Learning Representations, 2024a.
Zhong Zheng, Haochen Zhang, and Lingzhou Xue. Federated q-learning with reference-advantage decomposition: Almost optimal regret and logarithmic communication cost. arXiv preprint woXiv:2405.18795 2024b.
Runlong Zhou, Zhang Zihan, and Simon Shaolei Du. Sharp variance-dependent bounds in reinforce- ment learning: Best of both worlds in stochastic and deterministic environments. In International Conference on Machine Learning, pp. 42878 42914. PMLR, 2023.
15

---

Published as a conference paper at ICLR 2025
In the appendix, Appendix A reviews related works. Appendix merical experiments. Appendix [ include some useful lemmas. Appendix D Appendix and Appendix
B presents the results of our nu-
Eppendix/Fproovdess Piprvvides the proof for Theorem 3.1 Theorem 3.3 and Theorem respectively.
A RELATED WORK
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 algorithms. Model- based algorithms leam 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 opti- mal actions. Due 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 model-based and model-free algorithms for finite-horizon tabular MDPs with worst-case regret. Auer et al. (2008). Agrawal & Jia (2017) ) Azar al. (2017), Kakade et al. (2018). Agarwal et al. (2020), Dann et al. (2019), Zanette & Brunskill (2ang) et al. (2021a) Zhou et al. (2023) and Zhang al. (2023) worked on model-based algorithms. Notably, Zhang et al. 2023) provided an algorithm that achieves a regret of Ó(min v SAM!T, (T), which matches the information lower bound. Jin et al. (2018). Yang et al. (2021). Zhang al. (2020).
Li et al. (202)) and Ménard et al. (2021) work on model-free algorithms. The latter three have
introduced algorithms that achieve minimax regret of ((VSATT))
Suboptimality Gap. When there is strictly positive suboptimality gap, it is possible achieve logarithmic regret bounds. In RL, earlier work obtained asymptotic logarithmic regret bounds Auer & Ortner (2077); Tewari & Bartlett (2008). Recently, non-asymptotic logarithmic regret bounds were obtained (Jaksch et (2010) Ok et al. (2018): [Simchowitz & Jamieson (2019); He et al.) (02T]. Specifically,, Jaksch et al. (2010) developed model-based algorithm. and their bound de- pends on the policy gap instead of the action gap studied in this paper. Ok et al. (018)) derived problem-specific logarithmic type lower bounds for both structured and unstructured MDPs. (Sim- chowitz & Jamieson (2019) extended the model- based algorithm proposed by Zanette & Brunskill (2019) and obtained logarithmic regret bounds. Logarithmic regret bounds are also derived in linear function approximation settings (He et al. (021). Additionally, "gguye-TTang et al. (2023) provides a gap-dependent regret bounds for offline RL with linear funciton approximation.
Specifically, for model free algorithm, Yang et al. (2021) showed that the optimistic Q-learning algorithm by Jin al. (2018) enjoyed a logarithmic regret O #*SAT), which was subsequently refined by Xu al. (2021). In their work, Xu al. (2021) introduced the Adaptive Multi-step Bootstrap (AMB) algorithm.
There are also some other works focusing on gap-dependent sample complexity bounds (Jonsson et al.
2020 Marjani & Proutiere (2000] Al Marjani et al.) 2021 Tirinzoni et al., [022 Wagenmaker al.
2022b Wagenmaker & Jamieson 2022 Wang et al. [022 Tirinzoni et al. 2023).
Variance reduction in RL. The reference-advantage decomposition used in Zhang et al. (2020)
and Li et al. (2021) is a technique of variance reduction that was originally proposed for finite-sum
stochastic optimization (Gower et al., 2020; Johnson & Zhang, 2013) Nguyen et al. (017). Later on, model-free RI. algorithms also used variance reduction to improve the sample efficieccy. For
example, it was used in learning with generative models (Sidford et al., 2018 2023) Wainwright
2019), policy evaluation (Du et al. 2017 Khamaru et al.) [2021] Wai et al. 2019 Xu et al. 2020)
offline RL (Shi et al. 2022, Yin et al. (021), and Qlleaannig (Li et al. 2020 Zhang et al. 2020
Li
et al. 2021 Yan et al. 2023 Zheng et al. 2024b).
RL with low switching cost. Research in RL with low switching cost aims to minimize the number
of policy switches while maintaining comparable regret bounds to fully adaptive counterparts, [ai
et al. (019)) was the first introduce the problem of RL. with low-switching cost and proposed Q-learning algorithm with lazy updates that achieves low switching cost of OSSAH3 log T) This work was advanced by Zhanag et al. (2020), which improved the regret upper bound and the switching cost. Additionally, Wang al. (2021) studied RL under the adaptivity constraint. Recently, Qiao al. 2022) proposed model-based algorithm with switching cost of Ölog log T).
16

---

Published as a conference paper at ICLR 2025
Other problem-dependent performance. In practice, RL algorithms often outperform what their worst-case performance guarantees would suggest. This motivates a recent line of works that in- vestigate optimal performance in various
settings (Fruit et al. 2018 Jin et al.
2020
Talebi & Maillard 2018: Wagenmaker et al. 2022a /Zhao et al. 2023 Zhou et al. 2023).
B NUMERICAL EXPERIMENTS
In this section, we conduct experiment All the experiments are conducted in synthetic envi- ronment to demonstrate the better gap-dependent regret of ACB-Advantage and Q-EarlySettled- Advantage compared to other two model-free algorithms: AMB (Xu et al. 202I). We will consider two different scales of experiments across two cases: a general MDP and deterministic MDP.
(Jin et al.] (018) and
We first set = 5, S = 3, and A = 2. The reward rn(s, a) for each (s, a, ht) generated independently and uniformly at random from [0, 1]. For general MDP, PA(- 8, is generated on the 5--dimensional simplex independently and uniformly at random for (s, a, h). For deterministic MDP, (- 8, a. is randomly generated vector with only one element equal to and all others equal to 0 for each (s, a, h). Under the given MDP, we generate x 10" episodes. For each episode, randomly choose the initial state uniformly from the states. For all four algorithms, we set = and the hyper-parameter e = v2 in the Hoeffding- type bonus. Here, e₁ represents the undefined constant in the bonus terms of the UCB-Hoeffding and AMB algorithms, as well as the multipliers in the bonus expressions in line 10 of Algorithm T (UCB-Advantage)) and lines 2 and 4 of Algorithm 2 (Q-Early (etalyySetteddAAvvaatte)))) In both the UCB-Advantage and Q-EarlySettled- Advantage algorithms, we set the hyper-parameter c2 variance estimators of the advantage-type bonus, corresponding to the undefined constant in the second term of line in Algorithm and line 16 in Algorithm [ Additionally, we set C3 = which is the multiplier in the last term of line 9 in Algorithm I and the last term of line 8 in Algorithm 2 0.05.
where e2 denotes the constant in the
For Acv--ddantage, we set No = 200, and for Q-EarlySettled- -et-tteee-d--vaaageee.. Advantage, we set
To show error bars, we collect 10 sample paths for all algorithms under the same MDP environment and show the relationship between Regret(T)/ log( K + 1) and the total number of episodes in Figure [ For both panels, the solid line represents the median of the 10 sample paths, while the shaded area shows the 10th and 90th percentiles.
2000
7500
UCB Houfiding
UCB Hostiding
UEB-Adeeraage
Acvartaee
EartySetteed Advantage
400
EartyScitidd Advantage
AMB
2000
300
200
500
100-
s020n
19dnoon
150000
100000
100000
25000n
apisectes
(a) Regret of General MDPs
(b) Regret of Deterministic MDPs
Figure 1: Numerical comparison of regrets with H = 5, S = 3, and A = 2
We also conduct a larger scale experiment with = 10, S 5, and = 5 for 3 x 1 episodes in both types of MDPs. With all other settings unchanged, the result is shown in the following Figure
All the experiments are run a server with Intel Xeon 25-2650v4 (2.2GHz) and 100 cores. Each replica- tion is limited to single core and 4GB RAM. The total execution time is less than 2 hours. The code for the numerical experiments included in the supplementary materials along with the submission.
17

---

Published as a conference paper at ICLR 2025
400000
UCB-loending
UCB Hoefiling
ICh-Adanttage
UCB Acvertage
EarlySett oc Advencage AMS
Barlysoti os Advartage
AMB
300000
600000
300002
200000
200002
0.5
1.5
2.5
3.0
0.0
0.5
1.5
2.5
Tocal number of eptsodes
Total number of sodes K
(a) Regret of General MDPs
(b) Regret of Deterministic MDPs
Figure 2: Numerical comparison of regrets with H 10, S 5, and A =
From the two figures, we observe that both UCB-Advantage and --EaalySettee-AAdvamee enjoy lower regret compared UCB- (CB-Hoeffding and AMB. The y-axis represents Regret(T)) log(/ 1), and we note that the curves for ACCB-Advattge and Q-FaarlySetled-AAdaanie lines as becomes sufficiently large. This suggests that the regret for these two algorithms grows logarithmically with K. In particular, Q-EarlySettled- soiitedd-Avvanntaee Advantage achieves even lower regret than UCB-Advantage when K' large. These features are consistent with our theoretical results.
approach horizontal
We also conduct an experiment to evaluate the policy switching cost of the UCB-Ade UCB-Advantage algo- rithm for (H, S, A) (5,3, 3, 2) and (10, 5, 5) with the same experimental settings. The results are presented in the following figures:
20.0
Seitcing CostrWkgir+3)
15.0
king CooiTMogiX
12.5
7.5
0.0
S0000
300000
150000
200000
230000
300000
50000
100000
150000
200000
230000 300000
number episodes
Total number episades
(a) Policy Switching Cost of General MDPs
(b) Policy Switching Cost Deterministic MDPs
Figure 3: Policy switching cost of UCB-Ad Advantage algorithm with = 5, 3, and = 2
250
Switching DottrNoakte. 11
200
Swiching CootTNNgI
100
0.0
0.5
1.5 Total number of opisodes K
1.0
2.5
3.0
Tokel nummer epploddes
(a) Policy Switching Cost of General MDPs
Policy Switching Cost of Deterministic MDPs
Figure 4: Policy switching cost of UCB- UCB-Advantgge algorithm with H 10. 5 5, and A
18

---

Published as a conference paper at ICLR 2025
In these two figures, the y-axis represents the ratio of policy switching cost log( K + 1). We note that all these four curves approach horizontal lines as K becomes sufficiently large, which is consistent with our logarithmic policy switching cost shown in Equation (4)
C GENERAL LEMMAS
Lemma C.I. (Azuma- (Azuma-Hoefiding Inequality). Suppose {X&] a martingale and |Xx X S Ck. vk E N+, almost surely. Then for any positive integers N and any positive real number e, it holds that:
2²
P(NN Xo 2 20) exp
2 2
N
k=
c
and
P P[ Xol 2 c) exp
2
k= Ck
N
Lemma C.2. (Lemma 10 in Zhang al. 2022a)). Let X1. X2,..
be sequence of random vari-
ables taking value in [0.4]. Define Fs = o (x1,X2, X2..... Xx) and Yv = x[x2 FR for k 2 1. For any O, we have that
n
a
IP
n.
Xg 2 3
Σ
Yk + log 56
k=1
k=1
and
P
3n,
Yk 3
Xx + 1og(1/))
8.
Lemma C.3. (Lemma 11 in Zhang al. (2021b). Let (Mu)ag0 be martingale such that Mo and Mn Mn-il II S for some e > O and any 2 1. Let
Var, = Σ
[M& Mk-1)
A=1
for n 2 0, where Fx = MR). Then for any positive integer and any c, Ō > 0, we have
(1)
1
2cln ())
nn22
TP
MMa 2 2 2ar,, In
2/ In
2 (oog
+
D PROOF OF THEOREM 3.1
D.1 ALGORITHM DETAILS
The UCB-Advantage algorithm, first introduced in Zhang et al. (2020). achieves the information theoretic bound on regret up to logarithmic factors, using a model-free algorithm. The key inno- vation of the algorithm lies in its combination of UCB exploration (Jin et al. 2018) with a newly introduced reference-advantage 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, ft), we divide the samples received for the triple into consecutive stages. Define e₁ and e [[1 + 1 )e, for all > standing for the length of the stages. We also let L = 11 = 1, 2, } 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 l and h, let (sf,, a 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), at) and the total visit
number of (s/, af) after the k-th episode is in D Gi, Ei ei).
19

---

Published as a conference paper at ICLR 2025
Now introduce the boage-baed update framework. For any (s, a, h) triple, update (s. a) when the total visit number of (s, a, h) reaches the end of the current stage. For k-th episode at the end of a given stage, the Q-estimate Q (shh a learned from UCB is updated to:
(sh, = - a,) +
Σ
vitl (8/+11) + FOV
H n%
(29)
Here we define n = nit al))) as the number of visits to (sh ag. ht) during the stage immediately before the current stage of (k, h) and L = 1h,+ denotes the index of the i-th episode among the n episodes. (s() is the Veestimate at the end of the episode k with the initial value (2) H.
represents the exploration bonus for n% + visit, where is a sufficiently The term CI ax.
large constant and commonly used in Hoeffding-type updates (Jin et al. (2018); et (202T): ;; Zheng et al. (2024a)).
( with p E (0. 1) being the failure probability. This type of bonus is
The other estimate, denoted by @ af),, uses the reference- addantace decomposition tech- nique. For k-th episode at the end of a given stage, it is updated to:
A+1
a++1
(
k+1 n
vretk' h+1
(5
(5
K+1 Th
(v ==1
V+11
(b aft). (30)
==1
Here we define n = ( a be the number of visits to (s% ag h) prior to the stage of (k, h)
and 1 = 1/, denotes the index i-th episode among the n episodes.
In Equation (30). Veet.((s (s) is the reference function learned at the end of episode 1. We expect that for any E S, sufficiently large k and some given 3 E (0, H), it holds |V (8) V (+) s B.
With these Qestimmates, we can update the final Q-estimate as follows:
2 (st a miin
) 02,+t at),, Q (5%) a
(31)
We also incorporate Q (s a here to keep the mononicity of the update. After updating the Q-estimate, we can learn (s+t by greedy policy with respect to the Q-estimates, i.e.,
vk+1 (5)) max, Q++ (s a). If the number of visits the state-step pair (s, h) first exceeds No O / ) at k-th episode, then we update the final reference function ()(t((s)) to V++1 (s).
For the reader's 's convenience, we have also provided the detailed algorithm below.
Algorithm UCB-Advantage
1: Initialize: set all accumulators to 0; for all (s, hs) E 8 x Ax [H) set Qn(s,)) a), Vh((s)
H - h 1; V (8) +- H;;
2: for episodes +- 1, 2,..., K do
3: observe $1;
4: for 1 1,2,..... H do
5: Take action a₁ + arg max, Qu(sn, a), and observe 81+1-
6: Update the accumulators by = (s an + 1, = nn (s an) - 1,
7:
and Equation 32. Equation (33 Equation
8:
if n. E L. then
9:
b + 2/
+ 02
4/6 (a/n]a
Hi
He +
n3/4
3/4
3/4/4 6374
b + ci H2
11:
(sh an) t- min ond ) 6 ((()s)) + max. Qu(sk,a)) a);
n + brrrh(h, an) + p
# + b,
12:
13:
nu (8h, an), (n,,,, an), on (Sh, an), 5n (8h, an) +- 0;
14:
end
15:
end mn. a) No then (sn) Vh((s))
if E.
16:
17:
end for
18:
end for
20

---

Published as a conference paper at ICLR 2025
In the algorithm, c1, C2: C3 > 0 are sufficiently large constant. The Stage-wise accumulators in the algorithm are updated as follows.
á = (Sh, ap) I Vn+1(5n-1)- - Vn-1 (sx+1)) ú: (5 an) & Vh+1 (5+1())+1;;
(32)
= (s an) $ (Va+1(sh+1) vist (sn+t))
(33)
Meanwhile, the following two global accumulators are used for the samples in all stages
N=t := 1 11h an.) &= Vis (8++1); aTd == o (sh; an) & (Virt (8h+1))
(34)
We use Uh by the start of the k-thh episode.
uielk Th j.h. ihg oht by, to denote respectively the values of nt otd p. o, b at step
UCB- Advantage assumes that the reward is known after the visit to the triple (s, fi), which is common in RL settings. When the reward is unknown after the visit to the triple, inverse reinforce-
ment learning (Zeng al., 2022 Liu & Zhu 2022 2023 2024 Qiao et al. 2024 Liu & Zhu 2025)
provides a bi-level learning structure to help leam the reward.
D.2 KEY LEMMAS
Before proceeding the proof, we will first establish several key lemmas. In the algorithm, define 1 log(2/p) with E (0, 1) being the failure probability.
Lemma D.1. Using ((s, a, h, k) as the simplified notation for for'(ss a, h, k) Sx [H] [[]] For
Vss, a, h, k), let No (s) = E. (s, a), (s) = [[Nk < No] and define the surrogate function
as fr (8) max (V. min
+ V, (.ref((()))) {+))}. Then we have the following conclusions:
(a) (Proposition 4 in Zhang et al. (020)). With probability at least 1 (4H2T1 + 12T)p, the following event holds:
E = (s, S Q (s, S (%,s,
(s.
hs,
(b) (Corollary 6 in Zhang et al. 2020 following event holds:
With probability at least 1 (4H2T4 + 13T)p, the
& = (
N (s) 2 No = (8) S prelk
S (z) + + ESX [H] x [K]}-
(c) With probability at least 1 Hp. the following event holds:
K
K
kk ( t wh E mm1
Eg
Σ
P a
h+1 <3 3
k=1
Especially, X
(8) =0
(d) With probability at least SATp, the following event holds:
811t1 - P.a.)) h+1
Vitta)
2r
E
S
3,
((s,,,
(8,
n (s)
(e) With probability at least SAT2p, the following event holds:
- Pa.a,
Vi+t
20+h
+ 4Ht
Es-
sht1
$2
Yss
nti (8,,a)
n (s,
a)
n (
(f) With probability at least 1 - SAT2p, the following event holds:
(Drettts
1
- Paaan
Vitti)
2r iik a) a(s,a,h,k)
Eg
<B
i (8,
21

---

Published as a conference paper at ICLR 2025
(g) With probability at least 1 SATp, the following event holds:
(Vi++122
2
E
S H2
v(s,,,,,,
(s)
a)
(h) With probability at least
SATp, the following event holds:
Pa.o.))
Vi+
2
Es
'hi1
H
V(8 ((,,,,
(8,
n (s)
Proof. We only need prove (c) to (e).
(c) By using Lemma C.2 with 1 = and 8 p and considering all possible values of h E [A],
we can prove this conclusion.
(d) From the definition of k (s), we know that for any it E [K]:
(s) S ( S (i) + 3.
(35)
Then the sequence
(vretl - Viru1) JENI
1
P saai
K11
is a martingale sequence with
(1 - P. Fo...))
(viffi Vit+1) )|
| S
Then according to Azuma-Houue Hoeffding incquality, for any p E (0, 1), with probability at least 1 p, it holds for given (s, a) N+ that:
- .P....))
(vretl - Vi+t1) 1
2,3 n
For any all (s, a, h, k) E x Ax [H x [K]. we have (s, a) E [+] Considering all the possible combinations (s, a. h. n) E Sx [
T
with probability at least 1 SATT,, H
H
it holds simultaneously for all (s, a k) E S
x
x [K] that:
Paan))
(rreft: Vi+1.) S V
282
n (s,a a)
(s,
(c) The sequence
1 sits Paiaa)) Vieta }
JEN
is a martingale sequence with
( 1 1 -Pean)) Vh S H.
Using Lemma C.3 with c H, H2 and ā = 2. for given (s, a) n E (T)
with
probability at least
(log₂ (n) + 1)p 2 1 - Tp, we have:
2Qth
4H
Σ i=1
- .o.aan) Vittl
S 2
+
+h+1
n
n
22

---

Published as a conference paper at ICLR 2025
Considering all the possible combinations (s, a, n) SxAx x [ with probability at least SATT p. it holds simultancously for all (s, h E ES x A [H] x [K] that:
2Q
4HL
-Paaah))
Vh+1
2 (8)
+
n (s,
(s,a))
( The sequence
(preftl
Vit1)
1 sx+1
P.
SEN-
is martingale sequence with
(1
( 14 S
- -Psaa)
(vzetl:
Vi
S 3.
Then according to Azuma- Hoeffding inequality, for any p (0. 1), with probability least 1 it holds for given ni a) n E N that:
1 ñ2
- (...at))
(Vrasi:
-Vit1)
S
2,3%,
n2.
1=1
For any all ks, E S Ax x [M] x [K]. we have (8, a) E I Considering
all the possible combinations (8, h, k) S x A x [H] x [K] and (s, E ]
with probability at least SAT AAT/HHp /Hp 2 SAT it holds simultaneously for all
(s, a, h, k) E x A x [H] x [K] that:
(vroth. Vitta) $ <\ ())()
2
psaan
4 S1+t
a)) a)
g
The sequence
s/ps - -Paan)) (Viitz)
+EN+
is a martingale sequence with
(2 - -Pea,)) (Vi+1)² < 122
Then according to Azuma- Hoea--Hoffdiing inequality, with probability at least p, it holds for given n (s, = n that:
1
- - -P..a.)) (Vi+1)2 S H2 2
Σ
1
Considering all the possible combinations (s, a, h n) E Axx at least -ATTp, holds simultaneously for all (8, h kb)
H x
with probability
E S A
x
H x [K]
that:
11
Peaa.))) (Vita)²
S 5H22
n (s, a
ski1
n (s,
(h) The sequence
Σ (1))) - Paaan) Vieti }
JEN-
is martingale sequence with
(1 -Paai)) Vit S H.
23

---

Published as a conference paper at ICLR 2025
Then according to Azuma- Azema-Hoeficing inequality, with probability at least p, it holds for given n (s, as) = n that:
1
a
2t n
-Ps,a.)) G11
Vi+t1
S
72
Considering all the possible combinations (s, a, h, n) E SxAx H x [. with probability
at least - SATTp. it holds simultaneously for all (s, a, h, k) S A x [H] [K]
that:
21
1 +h
Ps.a,)) Vitta
S H
n (s
(x
From this lemma, we know that the event Ni= & holds with probability at least -0HH
Next, we will discuss the relationship among the V-estimate V (s). the reference function V (s), the surrogate function V (s) and the final value VR (s) of the reference function.
Lemma D.2. Under the event & n Eg in Lemma D.1 we have the following conclusions:
(a) kret (s) = min VR (s) + 3, Vi (s)}
(b) & Veell (s) RREF (s) - H (s).
(c) 0 & Vyeli Veret (s) < (s).
(d) &t (s) V. V-REF(S) (s)
< ())
Proof.
(a) Under the event Er in Lemma
D.1
we have i (s) 2 ()((s) 2 (s). Therefore,
min (V) 3, & (s)} (s).
According the definition of p (s), have
kr (s) = min V. (s) + 3, Vn (s)).
(b) For any (s, h, k) E x H x [K]:
If (s) 2 No. then (s) 0. In this case, the reference function yrelk (s) is updated to its final value (s) and then y (s) vi y (s) 0 (
Since the reference function is non-increasing and If N < No. then { Vref. (s) VREE (s) < = (s).
yiut (8) H, we have S V
Combining these two cases, we can prove the conclusion (b).
(c) For any (s, h, k) E S [ X [K]:
If (s) 2 Ng. then (+) = Under the event Eg Lemma D.I we have v (s) S (s) + 3. Therefore, it holds that k (s) frrf, (s) by (a). In this case, Vr (8) pret (s) If (s)(s) < No. then ()(
H
Since the reference function is non-increasing and Via (8) H. we have S veref((s) (s) ( (s) < H.
Combining these two cases, we can prove the conclusion (c).
(d) For any (s. E x [H] x [K]
If ( 2 No. then () = O. In this case, the reference function Vief. (s) is updated to its final value (.RE Under the event &g in Lemma D.I we have (REE((s h (reff( S
VA (s) + B. In this case, we know (oref,((s) (s) V.el
/REE (s). Therefore, holds
that ( (s) VREE (s) = = H (s).
If (s)(s < No. then (s) = 1. Since the reference function is non-increasing and
vref (s) H. have 0 < /EEF (s) Viel (s) H and 0 & S Vref, (s) s
24

---

Published as a conference paper at ICLR 2025
H. Therefore, it holds that ( (s) V Combining these two cases, prove the conclusion (d).
VREF(S
(
Lemma D.3. For any (s,a, ESx x [H] [K] such that ni (s, a) # 0, it holds that:
(s, a) (8,0) a)
I 4H
Proof. For (s, a) + O, there exists j E 2 such that (s, a) = ej and n (8, = Ei= e,. We
will use the mathematical induction to prove that for any j N+. Ei=r I 4H.
For j = 1, Σ.m a = < 4H.
If D < 4H, then for j E N+ and j 2 2, we have 4-1
ej -- (11 +
cj-1
|
Cj-1,
H
2H
which implies:
E =1
E es
Σ
E
4H
11
1 +
S 4H.
Cj
ej
(1
28
eej-
1+ 2H
Therefore, we finish the proof.
Lemma D.4. For any non-negative weight sequence (wh,k and (0, 1), it holds that:
Mm (sk a
+ 0]
2 [
n aa330
1 a
and
K Wh.n (s aft
# 0]
22+0 Ho
(SA||W]l ||olll
n (0% a0
1 a
Here, ||wlloc, max (wn, and 1,1112,1 EK Wh.
For = 1, we huve the following conclusions:
1m (s) ah) + 0]
< 2SA log()))
( ah)
and
(st att + K
< 4SAH log)).
( at)
Proof.
Wh. a
[I (n (st,, att) +
wh. (h 00 (5h5 (s)
nk (s at)
(x
6,0
(s,0)
(36)
as)
k=1
Here we let Wh,a wh.tI|n(ss,a) # 0, (s (f
a
(s, and (x(s,a) ΣK
Then (8) S ||o]|oo, and Σn, (s Σx Wh.A ||||| 1,--
25

---

Published as a conference paper at ICLR 2025
whe when the weights Because ni a) is nondecreasing for S S K, given the term Ex=1 (8, a) concentrates on former terms, we can obtain the largest value. For a given state-action pair (s,a) and
N4. according to the stage design, the set {k: (x, Σi=ees has most ej+1 - (1 + # ye elements. Thus, the upper bound for the sum of the coefficients of (s, = Ei=1 Et in Equation (3 is given by (1 + }eyllwlloo..-
Let:
h:
1
ellwelooa < kk
Because Ej+1 S (1 + / ley for any j N4. we have
ko eyllolooo < <en(s,)):
==2
and thus
1
1 H
Σ Sellwllo S
Σ j=l
1 +
ej ejllw|loo, + Σ eylloooonn < 2cn(s,a).
(37)
Therefore, back Equation (36), by concentrating the weight to the terms with (s, =Ein Ei j E {1, (1,2.... J. for any given state-action pair (s, E S x A, we have:
K
(1+ Wesllwoloon
1 H
1+
|
Σ
(38)
a))
(E-res) es
Ei= Ei
a
k=1
3=1
For any 0 < < x and a E (0, 1), we have:
y xa
1 1 y)-a)
a
For any j N+, let x = Ei= and y=
E
eú then we have:
I-a
ej
Σ
Ei
c2
E1=
a
Sum the above inequality from to ko then it holds that:
to
1
ko
1-o
2ch (s, a) ||w| bo.h
1-a
1-a
Cj
The last inequality is because of Equation 37.. Applying this inequality Equation 38). we have:
K
22-a
S |
(s)
as)
Using this inequality in Equation (36). we have:
Wh.n I[n a) + 0]
22-a
22-a |||l Ec((s,a)>-a
<
n ( at)
1
1-a
8.a
The last inequality holds due to Hölder's 's inequality, as Es,o Cn (s) 1- < (SA)"|Wll]
By Lemma
D.3 it is easy to prove prove the second conclusion:
Wh. In (s) a + 0]
22+0 H
(SA 1w0l
( 30
1-a
The case of a 1 is proved in Lemma 11 of Zhang al. 2020
26

---

Published as a conference paper at ICLR 2025
Lemma D.5. For any non-negative functions {X S - R | k E [K], h E [H]} and any h E [H), we have that
K I [n a4 + 0
nk
K
X S (T)
nhish ag)
1+1
1=1
I [ at) # 0]
Σ
x h+1 S
(1+ 1
Σ
X 1+
H)
Here, X = ffror any k E [K] and & E.
Proof. For the first conclusion,
I ( ott) #0
Σ
K
Di=l
i+
T n a5) # 0]
( a4)
( a4)
1=1
k=1
nk
K
X1+11
1 [4: = i o% # #0]
( xt)
K
1 = j. n (5 a # #0]
X/ (39)
n/ (5 a%)
For given episode k according to the definition of 4. En 1 [4 j. n2 (s ag)) * 0] 1 if and only if (s), att) = (s) a)) and (j. h) falls in the stage before that (k. h) falls in. As result, if the (ke h) belongs to stage t of (sh af. h), we have n (5% og) = E G and the set (k : Enh [4 = j, n att + 0] = 1} has at most e, elements, Then it holds that:
K
14 = j, n att +
3 teC E c
S :log(() (40)
n (5h a/))
LEC C
Here, C = Uj 11 < > ST N+ J. The second inequality is because e, S (1 + )e
and then for any p [et]. E eepp 3 ez. Then we finish the proof of the first conclusion. For the second conclusion,
1-1
I (+) + 0
K
K
x
Σ
#0
1 of)
h+1
( att
1=1
1=1
nk
X1+1
.1 [1 at) #0]
n k at)
k=
K
I
14 = j. a + #0]
X/ (41)
(5% att)
For a given episode k, according to the definition of L. Σ1h 1 [T+ = j. nit (8% att) + 0] 1 if and only if (sh, a = (5/, af) and (j.h) falls in the previous stage of that (k, h) falls in. As a result, in the stage of h),, the number of visits (s), ar h) is n a and the set
{k: Enh II [7, = j. n + 0] = 1} has at most (1 + ) (s at) elements. Then it holds that:
1 = 5. + 0]
1
S1 +
(42)
at)
H
Therefore, we prove the second conclusion.
27

---

Published as a conference paper at ICLR 2025
D.3 PROOF SKETCH OF THEOREM 3.1
Next, we will begin to prove Theorem 3.1 under ni=1E &.. Let X = (S, A, H.T.). The notation
f(x) & g(X) means that there exists universal constant C1 > such that f(x) S Cig(X).
Step I: Bounding the term 0 Qi By Equation (30) and Bellman Optimality Equation (5) it
holds that:
(his aht ( a
E (v24, v (0lit2)
vreffe (0h+t)
S 1 [nf * 0]
6h ( af)
1 (5/2 a.))
(6/ ./))
+I[nf 0] H P Vi++
Di=l (v h+1 V. ($lita)
n
== Viril (5
SI 00
(sh att)
no ( o%)))
(5
+ TI [mn] = 0] H - [n # 0] P Pa Vi+t1
II 0] H + I [mt + 0] (G1 + (5h (b))
+ [n + 0] (G2 + Gs))
The second inequality is because viotl (s/+1)
2 V (s/T(s/111)) In the last equality we use
II ( a = 0] = I i (sh, aa) = =0]. Here
Σ
vrrofd h+11
(s - P. Pottaa h++
G
(* at)
f1 P. Priaat
(VAtT Vitta)
11=1
1/111/
G2 =
n Di=1
(htt (5/ n (s a²i
Vi++i (shi.))
Gg =
The upper bounds of G₁, G2 and b/2 is given in Appendix D.4 Combining the three upper bounds Equation (3). Equation (57) and Equation (62). the following inequality holds:
(Gs
H
(Q-
32
(Qt (5) af x I [ + 0]
G3 +
+ [nt # o]
v
+ ykk
n (5),
(43)
Here, for any ht E [H] and & [K], 1 is defined as:
HT [n 0] + I [ 0
Y
Σ H 1 11
+ PPP Papaaag Na + v HTT (st ( att)
n (sftes )
Tn # 0] n (st o
n
Σ 1
(P
P
Whirs + (ot ( 11
1=1
where
T N
(
k. =
Σ
- (ooth(
i=1
and
F (s at. = Σ
(vreth
(s (11444))
1.
pretll (o
1=1
28

---

Published as a conference paper at ICLR 2025
Step 2: Bounding the weighted sum. For any given h and non-negative constants (wn,t)n [x) denote ||w]loc,h ma] wh,k and || = EKE[K] Wh.k. We also recursively define whr,e(h)) (h)
for any h' H.kE E [K], E [K] as follows:
ii 114, = j. # 0 n ,
(h) = Whi WN+1,s(1)
wh/ & (h)
(44)
By Equation 42
it is easy to show that
(b)( & (1)())) [w) & (1+1/H]]w(())]) Ah' h, (45)
where
K
[k))))lls, = wax $ 1, [k)())l
wo wh).
Now given the weight (wi,e has we will bound the weighted sum Ek wh, (5) at). Summing Equation (43) from to K with the weight (Wn, H&s we have:
K
Wh. (sh ah) - (s ))
K
what I [nn + +0 G3 + Σ
I [[
#0]
(Q++ 1 ah)
+1 [ + 0]
H
whit
n ( a
k=1
1=1
whi
K
$
Σ (1)
- (0)+)))41)) + v(* + (2H) A ||m||| bc. lkwll,
H (SAIl)l))))) (w0l) + Σ W.
(46)
K In the last inequality, the upper bound of Ek=1 Whl [ + 0] G3 given in Appendix D.5 The
upper bounds of the middle two terms is given by Lemma D.4 with a = - and a a.
Recurring Equation (46) for h, + 1.... H, since Q (s. = QH+ a) = 0, we have:
Σ ah. (hi (hh
H K
I H 1Q- + 3HHH)A/llllo + # (o + Σ Σ ww a (h)
(47)
where whe (h) is defined Equation 44
Step 3: Integrating multiple weighted sums. For any N [log2(H] (H//mm/)mi Amin)) E [N]. l [K] and the given E [H] let:
1i (Q a Qū oft E 1pn-1Amin 2" Amin)]
and
I ($ oft) - (st. 12 A HI]
We also denote
K < 1, (m)) 11,,6 = Σ
| so. = maxwilk (n)
(n)
k
29

---

Published as a conference paper at ICLR 2025
For < 1/' < H and any n E [N], the weight {Wir,&R & can be defined recursively by Equation (44)
(n)
K
= i. + 0]
who (1) (h)
(m) (n) whis wh 1. (h)
Whe
( atp))
Therefore, for any j E [K], it holds that:
N W
K
144 j. #0 n ( a%
(h)
Whe (h)
i=
k=
n=
By mathematical induction on h E [h, H], it is straightforward to prove that for any j E [K],
N
h'-h
1
w (1) -
1 +
<3,
(48)
H
given that for any [K]
I14 = j. + 0]
S +1+
n (5h. (%/))
H
by Equation (42) and Σ k.j (h) = n. Whis S 1 for h²
(n)
Applying the weight (1)))) 1 Equation 47 for any n E [N]. it holds that:
K
(
) (hh,
h.k
k=1
x (H) H (S.A)3 110
Σ
W=
On the other hand, according to the definition of (n)
wh,k"
whik (oh at Q7 ak)) 2 2n 2=n=1Amin|lu
Therefore, we obtain the following inequality:
2n Din--Amilleer (m
(1) 11,6
H K
H (0- BHH 11,4 H H'' (w0
Σ Σ
(h)Y
(49)
M=h k=1
Then at least one of the following three inequalities holds:
2 min
( S H1 /(0- (Q+ + (3H) A||wo(n)) 11)
2 Amin (x) 11. S H (SAt) ( (1(w(()) (1,,))
2n A 1 & Σ
(n)
(h)Y
k=1
Solving this three inequalities, we know that:
(n) 11. 50 max (O** + H2 SAH?,
S4
Eish ΣK whe (1))7) ))
H
4n-212 min
(2n-1 Amin)
2n Amin
(Q+ + (2HHH) SAH?, 4n-2A2 2in
H 3 SAc
Σ# Ek=
w R (h)
(n)
0
(2 Amin)
2 Amin
30

---

Published as a conference paper at ICLR 2025
By Equation 48
have:
K
(a)
( Σ
Σ
Wh W
de (h)
(n)
Y 33 Σ Σ
Therefore,
N
(Q" + BB) SAH?L
H '' SA (Amin)
H K
2" Aminlwe! Il. So
Yk
(50)
A min
#==1 k=1
From Appendix D.6 we know =n'=1 Σ k= h'' can be bounded by 0 "² s² Aclog(T) Therefore, back to Equation (50) it holds that:
B²
Q (2 SAH?,
H#SA (Amin)
H As log(T)
2 Amin (0 1 11, 50
Amin
$a
10* + B SAH
H As
0
(51)
Amin
32
The last inequality is because:
SAc
3HHSAA +
H'SA
H'SA B
(Q + BBH SAH?,
HJ SAg
<
(Amin)
Amin
A
B2
Step 4: Bounding the expected gap-dependent regret. Let (40SAH2T*) then E =
n & holds with probability at least
1 and S log(S Therefore, by Equation (8). we
T
have:
E (Regret(K)) = E
clipl(Q): (3) )
Amin]
K
E
clipl(Q (7) at) Amin]
P(E)
K
H
+ E
clipl(X)
(s) a
Amin] g0
PP(E))
7m1
1 11,, T
2n Amin (m)
TH
h=
( 52+ (A
(Tg)
Amin
The last inequality is by Equation 51
The third inequality is because
K
C - (s a A Amin]
(n) h.k
(sh
k=1
N
K
N h Σ
2" A Amial (1)) I
min
n=1
==1
D.4 BOUNDING THE TERM Q Q
D.4.1 BOUNDING THE TERM G1
We can split G1 into four terms:
Ln (yret (s/ P.t. Kaagt N++1
REEF
G1.1 + GG22 + G1,3 + G1,4
(52)
n ( at)
31

---

Published as a conference paper at ICLR 2025
where
(1
P P2k )
(vr4f
V/+1"
G1,1
n (s abj)
i=
- -
Vi+ta
21
n2 (5/ a.t
Em
(Il
Petiet Vit+i
%/11
G1.3
n (5% a.t)
and
Dm IP 2t ataatt (iraal
V.EEE
G1
n alt)
According to (c) in Lemma D.2 we have:
Em
14 + +oz Ahin
G1,1 S
(oh. a/)
Under the event & in Lemma D.I we can bound G1,2
2c
G1,2 S B1
V
( a
Under the event &, in Lemma D.1 we can bound G1,3;
20
4HL
G1,3 S 2/
(s o
n (shh o
The upper bound of G1,4 is given by (b) in Lemma D.2
Σ 1h
HP of h+1
Lisl
G1, S
n ( a
Combining these four upper bounds together, can bound G1:
Σ H 1 Sh11
+ +tttt.aa... Nit1
(Q+ + 82)e
He
G1
(5h a%)
V ( at)
n of
(53)
D.4.2 BOUNDING THE TERM G2
We can split the term of G2 into two terms:
[(VAF
v h+1
+ (Drotth Viita)
E
P P.gaag
G2
(54)
n (sh aa)
According to (d) in Lemma D.2 we can bound the first term in Equation
54
Σ
P aaa
h+1
frref.
h-1
H
P.
(55)
n (st at) The upper bound for the second term in Equation (54) is given by the event Es in Lemma D.I
(s a
P Psaah
Vitt1
282
g
(56)
(s,a)
(s,
The last inequality because of Lemma D.3 Applying Equation (55) and Equation (56) to Equa- tion 54). we have:
nt i=1
P Pakaafi
1
82H
G2 E
(57)
(5
a4))
32

---

Published as a conference paper at ICLR 2025
D.4.3 BOUNDING THE TERM ( a
According to the definition of by (sh af) in Appendix D.I
we have
ref.k
H
Hc
H
H
(sh agh S V
+
(58)
(m
(#t))
where 1/2 ref,k o/oti /nf (1/2 //2t)22 and upp
/ (1
Since W (o%+2) 2 Viti (0/iz2). ). it holds that
(ott (ott) (5(0
1 + 12 n n ap)
ng (
n/ (8% 0%)
t,
hh
where:
( )²
(olit2) (1no4((077+t))
E
h+1
I
n2t. (sh ab)
and
En
(oltte)) ht1
Exe n
iil voot (s/i
ph.k
( at)
n (s at))
Next we want to bound both 1lt and 1hi
Σ
(vroti, (sh+t)
Vyoth (shit2)
v (5h+1)
Ilik
n (5t ab) V++l (5)
* im
(vretll (s/it2)
2H
2 at)
(59)
(sh; a7))
( ak))
where
( /
Virll (s) Vratl (s)
For the second term 1 A because of Cauchy's 's Inequality, we have:
Σ
nk i
voref ( (5//=1)
Σnd pretto (shi ax(o)
1
(s att)
where:
Σ x D
(s
Vitt (st
EnA Vk Vi ((())aaa))
Ed Ponter (sfn (
ph.k
2,1
and
2
I'hh, Vie (oft att (att
E
Viizastion)
kh.k
2,2
n (5/, (ti))att)
Σn
( (
En Vitzi(sitii not (s att
2
n ( of)
33

---

Published as a conference paper at ICLR 2025
Since Vit1(19+4 - 1 (8h+1) S Vi+ Vi+t((h++2) + B, it holds that:
Σnh Vi+ (6/2tt))
End vroti (s (1f a/)
h+1 (5/ - 1/- (5/ +
(5
Σn' 11+220//41) nef (sh. af)
Σnhh Vidll (6/1t2) (5 a
< /4+1 1 (0h-1) Vh+ Vitn
S 23.
Using this inequality, have 1, s 4/32. Moreover, according the definition of Q", it holds
12 k
Q" S 12.2
[P (PPAR.tt. (Vi+t))
( (Fag.ag.n Vitta)
(1 - P ot Vitta
E Viita (5 ( a//)
+ P.st.aga a Vieta
*ht1
( at))
Ei
[1 ship
Pet (Vh+1)²
+
n (0% (5h2 aa)))
P Pot (3 ahp
Vh+1
Die1
1
Pat.aae (Vitz)²
<
2H
1=
94+1
+
8hit1
nt ( at))
< H2
The last inequality because the event & and the event &g in Lemma D.I Therefore, we have
h.kk
S Q + H
a
By combining the upper bound of Ih. in Equation
59 along with those of rh and Thes we have:
k
HT (5%, af ( at)
(Q+ + 89),
H
(60)
( a4)
n a
Using the first inequality of inequality (80) in Zhang et al. (2020), we have:
x
(wazs (sh+42) - -ixcti (x (ohtz)) + ( (Dretii (sh Viin (ini((/tt)) (ohbz1)
11 i=1
* (Drath (shtt) Vitt (
1
32
+
7
1=1
and thus
nt -
(vretf (s/i
vretl (sh
32c
1
82 n
v ( atte
h
+
I
+
n
n
(61)
where I&t (s ab)) = Ein (vroth
(1rtt (slitz) - vntth (6/ (o(ttz))
The last inequality by Lemma
D.3
and 0 - vrefi (s/+t1) vrotl (sh (slitz) S H.
Applying Equation (60) and Equation
61 to Equation
58
we have:
HT (s aft (s at)) nt axp
(Q- + +32
H
HÍ (ot aft)e + He
(5) at) S
n ( af)
n ( at)))
(62)
34

---

Published as a conference paper at ICLR 2025
D.5 REARRANGE THE WEIGHTED SUM OF G3
Similar to Equation it holds that:
K
K
Ax Di=1
(ott(o/ht)) - Vitti (
Σ
Wh
pip + 0] G3
Whl
+
K
R ==1
I 1 = j, j, +
(v (Vhti(0het)) (Vita((
Whik
7 a/
/=1
K
K
Σ nx
I [4 j. n. 0
-i=1
(Ph+1 - -hi+t) 2 2
Whih
n ( axt
/=1
(63)
K
Σ
wh+
(64)
j=1
D.6 BOUNDING THE TERM Σ 2k=1 VB
K
K
Y
0]
H
1m1
K
k # 0]
nk H
+ F #Fothrzznn) ) Nhsu + v HT ( ogg.ee
Σ
n (5 axte)
i=1
nk H
i + 0] (sh a
Patratin +1., 11 Nhits v HIg (sh, Hi
k=
(65)
In this equation,
K
H
K
(sh = 0) H = ΣΣ
1
(s, = (s,
a (s, S SAA.A.
h/ml km
R= 8.a
A=1
(66)
By Lemma D.4
we have the following inequalities:
K I K + 0] The ( a
Hi S (A
(67)
According to Lemma D.5 we have:
K
m * 0] (
K
Σ k=
Σ
H(1
+ + )e 2/441 S 3H log T
Σ
(1
2 + Pst
Pa )
#41
im1
(68)
and
K
I | #
an
K
Σ
P (Pegaggiie+
+1
1 N/111 S
2H
P Pagnagin + 12 A
n (s/ at,))
1=1
(69)
35

---

Published as a conference paper at ICLR 2025
Let ko(s) = maxfk k S K, K (1 < <No}. When there is ambiguity, use ky for short.
Note that
K
K
Σ
Σ
T ++ No] = Σ T [ < Noo. = s]
k=1
k=1
k=1
1 [ I
s, 0,- = =a] (70)
Let (ko; h + 1) be in the j(s, a, hh state of (s, a, h). Because No > H, we know j(s, > 1.
Then we have No h'+1 (s, = E e₁ and thus
kg
[hi+11 = 8, o = a] < to (s, N (0, (1+ 1 H e ) S 3N (s.)
Σ
(71)
Applying this inequality to Equation 70
we have
K
N
(sh
3N h- (s, (s, 3 Noo $ S3SNo.
(72)
8.0
Under the event &g in Lemma
D.I. it also holds that:
K
K
X + S 10SNo P *y of is Ni Σ
(73)
k=1
Applying Equation 72 and Equation following two inequalities holds:
73 to Equation (68 and Equation 69
respectively, then the
H
H 1 s/:4s
+ -P Pattraty /r A/1t2 S log(T),
(74)
n k=1
(
M=1
1=1
and
K
H (Petiogtnn + +1. N 1h+11 S 122
(75)
M=1k=1 R (sh o
S//41
Meanwhile, according Lemma D.2
we have:
(s ofte)
Σ
(noti (5
v (s) (2) S H >
(5 - (sh, otc).
Then it holds that:
K
Th (s)
K
(s))
nhe ( ah))
n (st aht)
Σ
Vo a)T [(sk] aft = (8,a)) a)]
jEC D es
s.a
X log T
1 (s, a)l [(s)) at:) (s, ai]
< logT
SA Σ (s, a)I [(s) at) = (s, a)).
(76)
8,0
Here, C= [j= H < E/= e TT. The second inequality is by Equation (40) and the mononicity of Oz (s, a). The last inequality is by Cauchy's 's inequality. To continue, note that:
Σ 2 (s) { (s,a)] S
H
Mhr ($/+4)) S VHSNo-
36

---

Published as a conference paper at ICLR 2025
The last inequality is by Equation
Together with Equation 76 it holds:
"
K
11 ( d
Σ
2 11 (og()) (T) v ANge.
(77)
( al)
W=1k==
Since ( s 1h
(of &
a and 4HT (sh, ab)) 2 n (sh alp) by Lemma D.3 it holds:
H K
(o (oheratte nh (o at)
Slog log((T) V ANot.
(78)
Applying the inequalities Equation and Equation (78) to Equation 65
666. Equation 67
Equation (74). Equation 75 Equation 77
SAH since No = 0 8
we have:
52 Ao log(T)
Σ
Y 00
32
M=1 1=1
PROOF OF THEOREM 3.3
Proof. For 5 (0, let + 40SA/2T74 then log( O ((SA)) Now with probability
least 1 8, N E, holds. Next, we will prove Theorem 3.3 under the event Ni &
From the proof of Theorem Zhang al. 2020), we have:
WK++1 a)
+1)
N switch
I
4H log
2H
s,a
Next for any (8, a, h) E S x x [M]. we will bound the term N (s,a). Let AA a=
arg max Q% (s, a') ), which is the set optimal actions for state-step pair (s, h). For a & (s), have (s a) > 0 and then (s, > Amin- For any h E [H], let set Dy. be all triples of (s, a, h) such that a & (s). Dr {(s, a, h)la & A5)))).
We also let the set D U Dr and the set Dom {(8, a, h)la E A,))). Then we have [D] + |Dopel = SAH. Since for every state-step pair (s, h), there exists at least one optimal action. Therefore we know |Dopl 2 SH and then 0 < [D] SA(H - 1).
If for given (b, k) [H] x [k]. (ot at h) E DR. we have An(sh, > Amin- Then it holds that:
sh a Q7 d V/A (s (h 2 An aN 2 Amin-
The first inequality is because V/2 2 (s). Therefore, we have [(sh,aa)) = (s, a)) = T(( ah h) E Da)
Σ
(s.a,
< 1 [1h aft) (%% att > Amin]
Σ (n) hikk
n=1
and then
H Σ
H N (s,
Σ
Σ
Σ Σ
Iu(sh (s,
(D.D.))DD
hml (i.o
(s.a.))ED
H
H Σ
(aa 112.
Whi
n=1
By Equation 51 know:
A ΣΣ
(Q* (2 SAH3,
H$ Ao log(T)
Σ
N/K K (s,
Σ
(n)
50
82 32Amin
D
min
(79)
37

---

Published as a conference paper at ICLR 2025
Therefore we have:
N-+ +
(s, a)
Newitch S
Σ
4H log
h
+1
2H
s,a,h
N (s,
())
N N (s,
Σ
4H log
+1
+
E
4H log
+1) 2H
(80)
2H
(s,
(s
2n En | 111,
T
< 4H(SA - (Dopl)) log
1+
+ 4-4H Dapil log
2H Dopil +
2F (SAH (Dpul)
(Q" + HH
H Ao log(T)
$ 0 H(SAH (Dopll log
(SAH - Dup A
BSAAH - -Dop Amin
Dopll + +1))
+ H Dopil log
(81)
The first inequality is because of Jensen's Inequality. The last inequality is by Equation 511 Since Q+ s 2 and B < H, then we have:
(Q' 3 SA..
SA BP(SAH - Dp 12
(SAH oDp 1
By Amin H, we also have:
S² As log(T)
H log
(S Dopel) 1 Ain min
BP(SAH
DDopll (Pop)))A. 1
For 8 E 1), let p GOS AH then log(²) Ollog( ميد ))- Applying the above two
5
inequalities Equation (81)
with probability least 1 8, we have it holds that:
52 Au (Tg)
K Dopll
+ +1)
N Swwtthh 00
H(SAH - (Dopl)
+ H| log
B2 Dapil A min
H HAAA
K Doppl
+ +1))
=0
H(SAH -Doppll log
+ H Dopt log
(SAH |Dopi] Amiin
HH*SA log( )
K DDopl
D log
+ H Depul log
+
B. DE Amnn
Especially, if the optimal policy is deterministic and unique, which means Dapil SH, then the policy switching cost upper bounded by:
H² S2
Hăsk log( SAT 8
)
K H S
+1)
3 3mmin
HS
F PROOF OF THEOREM 3.2
ALGORITHM DETAILS
Before continuing, briefly introduce the refined -.EarlySetteed-Advanttee algorithm, which is similar to the original version in Li et al. (202I). We will first discuss the key auxiliary functions used for estimating the Q-value functions. For any 8 E [0, 1], let log( SAT
The algorithm updates yel and of represent the current mean and second moment of the refer- ence function. adadv and oddv denotes the current weighted mean and weighted second moment of
38

---

Published as a conference paper at ICLR 2025
the reference function with weight be the learning rate 7/, M+n" B% is the exploration bonus. Then we present the details of (-FarlyySetled-Advvnaaa algorithm below.
#+1
Algorithm Auxiliary functions
1: function UPDATE-UCB-Q
2:
(sh an) (1 7m ( ah) nn (n( V1+1 + cby
3: function UPDATE-LCB-Q
(sh, + (1 17n (sh, The (Ta(s)) + VLL co 110c
4:
5: function CEOATT-UCC-ADVANTTAA
6:
[ngh , uga oh
add (8); UPDATE-MOMENTE
7:
[8k Bh (sh: ah)) UPDATE-BONUS,
bR (sn, (4)) (1 mm)) Blln
H²...
8:
Cb n374
on
9:
(sh, an)) - (1 7h (1)) an)
+ha (r% an) + Vi+41(8H11) - 1 + (sh, an) + 18))
function UPDATE-MOMENTS
11:
(sh, an) &- (1 1) 1 an) + L 1 (
12:
(sn, an) + (1 2)) of an) ) + (V h+1 ( (8)+1))
13:
uighy (sh, an) + (1 Inn u (sho ag.
+ Th (V++1(9
h+ h++ (su+2));
14:
ond an) t (1 mm) o (shy ap) + 1m (V++(S8+1)
VR (s
15:
function UPDATE-BONUS
16:
Basa (Shy ax)
/ V oo (sn, (sh,an) (117 on)) v HHH oo ( (sh,an)
(uu (sns an))
17:
6% (s): 0h) = (sn, an) - BR (sh, an);
18:
B on) < Breck (sn, a.).
Algorithm Refined Q-EarlySettled-AAvaateee
1: Parameters: Some universal constant > O and probability of failure 5 E (0,
2: Initialize (s, a), QUCB,1 (s, Q (s) H, (L...1(s,)) 0; (s), + H: a).
(s, a), / (s, a), off a). ph (s, a), on
aod (s, (s, (s) 0
and w/ (s) True, for all (s, a, h) S SSXx Ax [[]].
3: for Episode à: = 1 to K do
4: Set initial state sf < sf:
5: for Step h
to do (s arg max, ( a), and draw shit1 Pu(-lott, at):
6:
Take action a
7:
(s a + Nº. (s a + +1;n + No: (s af);
Q (st at) UPDATE-UCB-Q.
8:
9:
Lh I (s
a + UPDATE-LCB-Q.
2 R. (s a - UPDATE-UCB-ADVAATIAG
10:
Q (s
a - min[QRR RKk+ (st at),, Q UCB,++1
at), db)
12:
1
VA (s - maxa O (s a);
LCB.
(s + max maxx LLCB. (sh a). VLCB.K (s
13:
if y (st) V.C.B. (s)) B then
14:
V kR (s) VAl (sh)
else k ) True then
17:
V RRk+ k+ (st) + y (s un
8+1 (s False.
39

---

Published as a conference paper at ICLR 2025
At the beginning of the k-th episode, can obtain V-estimate Vh the reference function V/R. (s) and the policy x² from the previous episode k and select a initial state s (For the first episode, we randomly choose a policy π² and 7
VR,1 H). At step h E [H], we can process the trajectory with of. =T ( and s ~ (- (a)aaa)).. Now we need to update the estimates of both Q-value and V-value functions the end of k-th episode. In the algorithm, the QUCR,++ updated to:
estimate learned from the UCB by the end of k-th episode, denoted as Qh
N4+1
Q QCB = r k) +
Σ
NE "m
(Viti(hhen) + co
H
(82)
Here we define No. = No (sf. ag) been visited at step h at the beginning of the k-th episode and k" = ( f/f a%) denotes the index of the episode in which the state-action pair (s% a is visited for the ri-hh time at step h. The term cb
as the number of times that the state-action pair (s) a%) has
represents the exploration bonus for n-th visit, where c 0 is sufficiently large constant. n
Another Q-estimate obtained from LCB at the end of k-tth episode, denoted as LCC,,++1 is updated similarly to Qh A++1, but with the exploration bonus subtracted instead.
The last estimate of Q-value function, denoted as 2h R uses refereecce-d decomposition techniques. At the end of k-th episode, gR.h+1 is updated to:
2 RKk+1 = (s )
N++1
Σ Not!
U..." (vir" (V h+1 (sh+1)+ E
VR h+1
(5
+ +bt
(83)
In Equation 83 V R. the reference function learned the end of episode 1. The key idea
of the iiderence-advantage decomposition is that we expect to maintain a collection of reference values {V>R.*( (s)} k. which form reasonable estimates of (V)(s) and become increasingly more accurate as the algorithm progresses. It means for any s E S, sufficiently large k and some given 3 E (0, HJ. it holds [V R. (s) (y((s) B.
With two additional Q-estimates in hand QUBBA++1 learned from UCB and Rh obtained from the inference-advanttan decomposition, we can update Q (s/,
a as follows:
2 o = min( UCB.K+ (s7, at),, QR R. (sh, att, 2%i(s, aN))-
(84)
We also incorporate Q (s at) here to keep the monotonicity of the update. Then we can learn (s v
a and V.LBB,t1 (sf a by greedy policy with respect to these Qeestimates:
V k (s max 1 a). (LCB,++1s$ max max QL (l.CB,bt(s a), V (
In the algorithm, v.I.B..(s) serves as lower bound of (s). We determine the final value YRRKK K+1
(1)((++)s)) (s) of the reference function for the state-step pair (s, h) when the condition V%
VLCB.& (s) < 3 is met for the first time. h
F.2 AUXILIARY LEMMAS
As can be easily verified, have
1,
if 0, 0,
Σ
(85)
if
n=1
Lemma F.I. For any integer N > O, the following properties hold:
for all
< < 1, 2
(86)
No
n2
Na
n=
40

---

Published as a conference paper at ICLR 2025
N
2H N
2H
1
max ISnSN
NN S
Uh
N
Σ N=
-
(87)
N
H
R=1
Proof. It is proved in Appendix B Li et al.
2021
Let u. = = 1 Lemma F.2. Using (ss a, h, k) as the simplified notation for Vs, a, h, k) E Axxxx {H] [K] and (s, h k) as the simplified notation for V(8,0, h k) E S x [H] x [K]. Then we have the following conclusions:
a Then according to Equation (86). we know uz S N for any S N EN
(a) (Lemma 2 of Li et al. 2021 With probability at least 5, the following event holds:
= f (7 s Q
+++ (s, a) & (s, (s) < (s) s V (s), as,a,h,
(b) (Lemmaa of Li et al. 202
With probability at least 8, the following event holds:
gLCBk (s, (s S as) V/ V.C.B.k S VR (s), V(s, a, h and
&
H K
SA.
(his a - O. (sh
for any E (0, H
22
h=1k=1
(c) (Paraphrased from Lemma of et al. (021 With probability at least 1 1-8, the following event holds:
V/(()) (s) (s)) 2. and
Eg
H
SA
(V -V V) T[(V/
V B
(s,
B
(d) With probability at least 1 5, the following event holds:
Es
U
NO (I.., IP -Pa,a.)) (VR+1 Viitt) S 2
N/ ((,,a,
2,3
(e) With probability at least 1 8. the following event holds:
N
Eg
N (1
-Pa.a)) Vhit1 S S8( ()
@+e
+ 16 () (ss
Hi
hi1
1=1
(
With probability at least the following event holds:
N
Eg
NĀ Mn
(Pan.A-
1.g7.)
Vi(11) S 2
(/(ssa)' V(s,ahh,))
8
(g) With probability at least
the following event holds:
P Peliatt { - VLCB, ( (s++z))] [ VLCB, ) > $}} (5/
Ex
H
K
3
(vh
V)LCBi) (s [ 1 VLCB. ( > $ + H
A=1
41

---

Published as a conference paper at ICLR 2025
Proof.
(c) The proof is adapted from the proof of Equation (146) in Li al. (2021). with the
substitution of (V2 V V)
(s
by (Vg h A (s B.
(d) From the definition of f (s), we know that for any & E [K]:
(5) (s) S (s) +
(88)
Then the sequence
Σ u (1 shis Poiai)) (hti - Viiti)
SEN
is martingale sequence with
|u
[1
a Poca.))
(vRrs
Vi+11
2B
N
Then according to Azuma- Huuua-Hoff inequality, for any 5 E (0. 1), with probability at least SAT. it holds for given (s, a) = N E N+ that:
E thi1 Pesait) (Vi+t Vitt1) s 2
2 N
For any all E Ax [M] x [K], we have (s, E [ Considering all the possible combinations (s, a, h. N) E A H [T) with probability least 1 6, it holds simultancously for all (s,a, E
x [K] that:
N
N (1 ohis
- Pssa.))
(VRR1
Vh+1) s V
2,32,
(s.
1=1
(c) The sequence
Σ uu" (1 P -Paaat)) Vinti J jEN,
is a martingale sequence with
au (1 1: IP P...a)) Vh+t1 $
2H
N
Using Lemma C.3 with
2H e² and d being 3AT2, for any given (s,a)) N e N
5
[T/H), with probability at least 2(loge (NV) + 1AAT
SAT, we have:
JuN (1 Min - -P..a.) Vi+t1 S S8
Q+4 H N
16
N
For any all (s, a, h, SSXAX [M] x [K], we have ( a) E [ Considering all the possible combinations (s, a, h, N) E S x A H
T with probability at least 1 - 6,
x
H
it holds simultancously for all (s, a, h, E S x
x [K]:
(1 (1 - PPaaa) Vi++1 S 8/ (s. + 16 H aht
Q+
(s.
(f) The sequence
Σ nh (Pr.ah 1o ( (DRA" Vinte)
JEN+
42

---

Published as a conference paper at ICLR 2025
is martingale sequence with
Th (Pe,ah- - -.
S 'n 3.
*
4+1
Then according to Azuma- azuma-Hoeffdding inequality and Equation (87) for any d E (0, 1), with probability at least SA7. it holds for given (s, N E N that:
Σ Tm (Pea.h
1 ) (VR-L
8 He
Vi+t)
- 2
N
For any all (s, h, R) ES Ax [ [K] we have (s, [i. Considering all the possible combinations (s, a, h, N) E S x A H x
with probability at least 1 - 6, [K] that:
it holds simultaneously for all (s,a, E 2xx
N
No (Psahh - 2k )
Vi+t1 1
B (s,
h+1
(g) This conclusion is directly proved by Lemma C.2 with H.
Lemma E3. For any non-negative weight sequence {Wh, hn and a E (0, 1). holds that:
K Whet
ab)a S 1- (SA) 1l0l,,
Here, ||w]lo,, = max (wnnk) } and [Wll = EE Wh.k-
&
For a = 1, we have the following conclusions:
N (sh, att SSAlog(T),
Proof.
K
(a.a)
Wh.k
(h.
(89)
N (s j
joc
5,0
Here k=(s, a) is the episode index of the i-th visits to (s, a, h). Let cn = ΣN (s.a)
and then we have Ea. (s a) = Σkm Wh, = || Given the term Σk=1 weights (s,a) concentrates on former terms, we can obtain the largest value. Let
W Whallaa)) 2a
when the
cn (n, a) ||w|lo..1
kis,ah
and da,a,h = en Cs, a) - (ks,a,h 1)
Then we have:
Wh.k
knaah
|
dy,,n
+
Nk. &
z0
ko
8,8
Ralanh-1
;l-a 11-1a
dr
||w| bo.h
+
1-a a
ka
s,a,h
8,0
kwlloo, (kis,a.h
- 11)2-a
de
Σ
1-a
La
[iks,a,h 1)|lw// oc0 1-a
dsah
Σ
a
8,8
[kis,,,
1) ||][ [b]
de
(90)
cn(s,a)a
8,0
43

---

Published as a conference paper at ICLR 2025
Here the last inequality is because ks.a,b Wolchh 2 c)( The second inequality is because for any < < x and a E (0, 1), we have:
1
xa 1 (1 (x1-a-y
-y
Then, let and y it holds that:
(it-a- (i-1)--0)
jn
a
Also let x = (x a) and = (ks,,,, - 1)]kwllo0,, we have:
dy Ch (8, a)a
[Kka,r, (aaa--1]lllla 1)llwllooh1
1 a
1-
Applying this inequality to Equation
90 we have:
K
Wh.k (
(n(s, 1-a
1
[SAA|//ll (o,, " Iwlli
1-a
1 1-
2,0
The last inequality is by Hölder's inequality, as Esa (s) - (SA) |w-l| For 1, it holds that:
K
N (s.a)
(log(N) (8, + 1) s Solog
(
Lemma F.4. For any non-negative functions we have that
(x S - E [K], h E [H] and any h E [A].
Σ
Σ
No
X S lTg(T)
X
Un
K.
(
K
Σ
Uh
No
h+t1
S
1+
x
X
H
Here, X H+1
0 for any ls E [K] and S.
Proof. For the first conclusion, we have
K
N (ch
K
No
K
Nē Un
X
Un
No
x
h++1
Σ 1=1
IlK"" =
k= n=
K
K
=
Σ
Un
NJ. (Rtte = أ X2+1-
(91)
j=1
k= n
Here T [k" = 5] = i and only (5%, af)) = (s ah) - k and n = N a²) >
Then
have:
K
Nk
K
N Σ
No Un
T =
No No++
I (s/. .g) af)) s
" Nit1
S log
(92)
1=1
k=j+1
No.
The last inequality is because for any N E N4 and i [N], us Equation 9T.. we finish the proof of the first conclusion. For the second conclusion, it holds:
3.- Applying Equation (92 to
K
K
N
K
N Jn
h+1
Un
Nk
x
I[K" = Jl
k=
n=1
K
K
Ny.
R.t =51 =51) X
mn
(93)
j=1
k= n=1
44

---

Published as a conference paper at ICLR 2025
According to the definition of k", [Ik = = 1 if and only if (5% a/))
(sh a k and
n N% (s/2 a.))) Then by Equation (87) in Lemma F.1 we have:
k N [k" =
K
I (5) at) = (sh ati
Σ
o Ng
S 1
H (94)
1
1-1+1
t= N
Applying Equation (94) to Lemma F.T we have proven the second conclusion.
Lemma F.S. For any h E [H] and k E [K], we have the following two conclusions:
(+) VLCB.k(s) (s) S B. then h+1 v. (s) V.R.A Viti(s) (s) h+1 (s).
1f V (s) > B. then we have:
S R.k. (R44(()) S V (s) - -V (s),
and
IR (s) Va+l VR.K+1 (8)l S (6+ VN+1 VLCBB((s).
Proof.
If for given ls E [K], VK h+1 (8) - V (s) S B, then there exists 1y E [K] such
that:
k = min k: Vh+ (8)
VLCBK (8) S $
h+1
Then according the algorithm, we have (s) = True, or it is contradictory to the minimality of l1. Therefore, in this case we have:
V R. (s) = vi (s) R. (s) = tk (s) S V
L.CBA (8) +B (s) +
h+1
h+1
and
v.R.k (s) (s) = RR (s) = V (s) 2 (s).
According to the definition of V (6), we have / (8) = R. (8) = V VRK++(ss) Thus
(s).
Vi+1 (s)
V.CB.
(s) I 3 the sufficient condition of V.Rkk (s) h (s) N+1 (s). h+1
Moreover, if A+1 (8) - VICBA (s) > B, according to the algorithm, we have V. (s) = h+1
V (s) and then 0 S h+ (s) h+1 (s) I V vh+t(()
PR.
VLCB.A(s) (s).
A+1
In this case, we also have vICB (s) < (st S V. RRK+I (5) S VR = V (s)
and then V-LCB. (s) I (8) S RR (s) S (s) = V (s). These two inequalities
imply that R.R.A (s) V v. (s)l S 1 (s) LLCBA((s) (s).
F.3 STEP 1: BOUNDING Q% - Qi.
F.3.1 BOUNDING THE EMPIRICAL ESTIMATION ERRORS
By Eg in Lemma F2 we have:
No mia
[pady
logoy V-adv
No
(Pog.of.1 1.p2.)) (vRRA* - Viita) S2
N/ att
(95)
By Ea in Lemma F2 holds that:
No.
(gxel
1P.,)) ) (DR.A" -Vht1) = Σ
us
No. (1 -
-P
-.t.oti.n) (FRR,' -Vi+1) S2
2 N (11,)
sh41
i=1
45

---

Published as a conference paper at ICLR 2025
By Eg in Lemma F2
holds that:
N Σ
(Bref - -h,,))
No U
(L - P
Q+
H
Vh++1
Vitta S 8/
+ 16
N ( (x)
N (H a%
==1
Therefore, combining these two inequalities, have:
Leg -PIn. )
+++ 3 ( ah)
H (s af)
ht1 &
(96)
F.3.2 BOUNDING THE BONUS
Since the term in the last inequality Lemma in Li et al. (021) can be easily improved to 6, can paraphrase the equation (87) and equation (88) of Li al. (2021) to the following form:
R.R b
B
R.Kk" (sh ah) +
BR. +1
(sh ag) +
Cb H
(97)
n3/1
The
Tn
This taken collectively with the definition of The allows us to expand
N
R
+1
Tn
hh
N
N
mi) (11-1)
N
N
Tn
II i=++1
(1
BRA
(sh, att + nm
BR (sh.
cb
n
in
H22
Th
n=1
n=1
No
N²k
R.R.A.
+1
+ C6
1/m
2
(98)
3//44
==1
Then with BR.
BR.k and Equation 86
Lemma R1 holds that
R. H²,
Rh.k
(99)
h
(s at)
Similar to equation (158) of Li et al.
2021
we have:
h (sh, att) - (14 auti. (s att)
No. Nt
(Viz (oht
(v
VRR (sh
n= Un
S 23
(sh.
(5 a/t
(100)
RR" Equation 1000 is because 1/4" -V.RA- (s S 23 by & in Lemma F2 and 1. Meanwhile, since R, h+1 ( (
No
N
<
h+1 (sh 2 Vhti (sh" it also holds that
RRR
(sh (s att - ph (sh aña )² ref,k T
ref,
J + Ju.k (K at:)
(h at)
where:
((VRAT h+1
(VRA"
h+1 (sf 2
N/ at))
and
Σ
(RR.. (oftt1)
No DR, (s (5tt,
NN a%)
46

---

Published as a conference paper at ICLR 2025
Next want to bound both J and Ju.
ΣN' (vi+i (sh+t) + V.R.A"
h+1 (oh+1)) (RR.A" (sh -.R.A (sh+t1)
gh.b
N (5%) a/t
No En 2H
(v (0k+t) - V.R.A (2
(sh. at)
Therefore, we have
JkiKk z 2 (sh, att No (o% ax))
(101)
where
N Σ
VRR
R (oh+t)
Viti (+htt))
For the second term J2 because of Cauchy's Inequality, we have:
(sht))) Ee Vi (ohTa) N1
Σ
PR h+1
2(J2,1 + 12221
la.k
(5 0%)
where:
2
In
V.R h+l
(sh+2) - (ott2(0h+1)) + Σ Vis V
E GR,6"
Ae1 (ohtt)) N7 (3H.aa
(5 a4))
and
2
N E
V (o
E Nh Vil ( N
J
(s ab)
2
Em (Vi+1 (sh+1))²
Ena No
Vis Viti (sh
(s af)
(o a%)
Since Vit (s/+1) S D.R (s
1 Vhn (sh+1)) ) B, it holds that:
D No Vila (sh21)
V.R."" DE h+l (sh
RRR 1411 (sRtt)
(o +
(s a
(R af)
DM Nº ( at)
Viti (sh
En DRR"" (shit1) (1 at)
< V-R.A h+1 (s
Viita
+
I 28.
Therefore, applying this inequality to J/L we have J S 432, Moreover, according to equation (165) oi Li al. (222), the following inequality holds:
J
Q* 2
N & a
Combining the upper bounds of J Equation 101 jh.k and Jr.2" we have:
ref.k (st at) - (wh
ref. (sh att))
/
H att
0++ Hoi
(s), att
() at)
N at)
(8 of)
(102)
47

---

Published as a conference paper at ICLR 2025
Back to the definition of B & holds:
in Algorithm combining Equation (100) and Equation (102)
h ref,k (sh (s att)
Mn ref.k (sh (aaaa)
hh adv,k (sh
(un adv. ( att)
B S sovy
+ C6 H
No (oh. aij
No (8k.
( a ( a
(Q+ +32
H²² N (sh, at)
(s ax)
Then by Equation 99 we have
HM ab) 0
(Q* 3-11)x (sh ah)
H NH x
R
(103)
(
Applying Equation 95
Equation
96
Equation
103 to Equation
14
it holds that:
(Q* + B2 ( a
H2.
(Qh (7) a s Ex (V Vo+i +
+ Rh..
(104)
( az)
Here
(sh, at)
R 1/0 No H h (VR.." f-R.A")
(peet
DRR h++1
Hr. No a
F.4 STEP 2: BOUNDING THE WEIGHTED SUM
F.4.1
REARRANGING THE SUMMATION
K
N
Wh.k ( (Vhr1 Vitt)
NE
(Veri(hhtt)) - (itt(oh+t))
Wh,
Jom n=1
N
No. T =3] -Vhn
Wh.k7/o
wh. No. T
(oh+1 -Qi+i) (s
A=1
K
(h)
( - Qi aht2))
1=1
(105)
Here, for any j E [K]
K N
No whe
Wh+1,5 (h) =
n 5]
k= n=
The inequality is because 2/ (8 (1t1))
Viln ($) Qi+t ( of S (itz(5//11)
F.4.2 PROOF OF EQUATION 20
By Equation 944, for h < < and any j E [K], holds that:
K No.
ww (h) < [[0(h]]boo,r>>
ΣΣ
nn
N
I = 1 s (1+
и (o)
(106)
k= n=1
48

---

Published as a conference paper at ICLR 2025
It also holds that:
K
N |,(bi)]l,,
ww (h)
Wh.k
(107)
Combining Equation can be bounded by
104 with Equation 105 the weighted sum Σkmn wh. (5) a
wh, v (sh - (h(s
K
(Q+ (Q" BHH (5 att
H
Wh+1 (1) (i+1)
+
Whik
(V
(NZ)
k=1
K
1,+ - Qh+1)(s 1. 10 + ll
k=1
HSAlSSl |wlli,
Wh. R
(108)
The last inequality is by Lemma h, h + 1..... H. since 2 and Equation (107). we have
F33
with a 1 and 3- Recurring Equation 108 with regard to 2 1++1(8 (s, a) = 0 and the weight relationship Equation (106)
(s,
K
Wh. W (O1 Q7hh
H wh & (h) Rb'.k
2 H (Q' ( (SAAA]] boo,k) 3
+
k= h =
(109)
F.5 STEP 3: INTEGRATING MULTIPLE WEIGHTED SUMS
F.5. PROOF OF EQUATION 25
For any N = [loga H/ Ami)) 1. E [N], k E [K] and the given h E [H], let:
wh2 I [ (s), ) Q (sh a E [2i-1] Amin 2' min))
and
(N) I [Qt (shh, at:) Q (sh, at:) 12 Amin, H]] Wh.k
Then
K
| boc, = max $ 1, (10000 11. h k
h
For any given i E [N] and h < W/ < H, the weight b can be defined recursively by Equation (88. Therefore, for any j E [K]. it holds that:
(h) (h)
Σ 2
I*II = =]] Th
No
Here for any i [N]. wh (h)
wh straightforward to prove that for any j [K].
Then by mathematical induction on h [h, H], it is
N
1 W-h
Σ
(h) =
1+
H < 3,
(110)
49

---

Published as a conference paper at ICLR 2025
given that for any [K]
K
NJ.
T [K = 5) S + 1
JJn
H 1
k=1 n=1
by Equation (94) and Ex= Wh (h) = - Wh
(6)
Applying the weight (a ha to Equation 109). since ||ا( 1oo,k S 1, then for any E [M]. it holds:
Σ
(1) whe (sh, at) Q7 a))
H (Q* (
(Q" H
+ (SA)) ( + (h)
On the other hand, according to the definition of wh have
K whice
(s a Q1 at) 2 2' "mminlw("))laa
Therefore, since ( boo, I 1, we obtain the following inequality for any E [N]:
2 A (10 I.M S H V (Q+
+
BHH)A
Inne ( ((c
K
H
(h)
(111)
M=
Then at least one of the following three inequalities holds:
2 A Ainal
11, ~ H /000 (32H)))aluu()1
2 1000
H² ((( (11,0)))
K
H
2 (mink 11.
S
wh wh (h) ( M.
1=
M=h
Solving this three inequalities, we know that:
(Q' + (2H) SAH2,
H'SA
Σk E#=n w (h)
|1000 1.b
50
max
1 min
(2i-1
2 *min
(Q* + B) SAH?t
HA
K
ΣH
Mivh WH' (t)BB
0
(2 A
min)
2;-1 Amin
(112)
By Equation 110
we have:
N
K
H
H
N
H
ΣΣΣ A
( clsc
Σ
(6)
(h)
RMC
<3
R
#=
Using this inequality, we have
N
(0' (Q'+ SAH2,
HASA
H Σ
K
2 A min (0) 11,b 50
Mii else
(113)
A Amin
(mii))
Am
50

---

Published as a conference paper at ICLR 2025
F.5.2 PROOF OF EQUATION 26 AND EQUATION 27
Next will bound the term Σn= =n==1
R where
2k==
H
No H E
(vR44T
(.R.A") h411)
V.R ' h141
-PR R.R.A h4111
Hc
%o
+
No
No.
According to equation (149) of Li et
(2021) we have:
H K
No
H < HASAS
H (osAlog(T))
(114)
B
h==1 k=1
By Lemma F4
we have
Fief " k
(.R.A" log T
Σ
Σ
RR.j
(N(41) (oh++1)
(115)
M=1
M=1j=1
By Lemma F.5
the following inequality holds:
vRJ
(8h)42 -VR-4 - (8042(8/+4))
M=1j=1
H
K
H
(1
LLCB (5) (5/42) VLCB. (s (sh44))) (5/4))
(5/
B S B
(s/41)
M==jj=
The last inequality is by Eg in Lemma
F22
Applying this inequality to Equation
115). it holds that:
"
K
1 log())
Sref bi,k
VR
V.R.A")
(116)
B
For the third term in ph',k because Σ == Un
No.
Σ
n=
Th
No.
then
pref
DRR
DRR -Pa
12 N+1
N
Un
No.
T...
(V-RAA" RR,K+1
Σ
nn
No.
P
hr4
RRRK+1
V/411
N
<
No Un
P.
de
DR.E" #+1 - VN+1
Σ
Un
No
DR.a"
N441
V/+1
By Lemma E4
we have:
"
M
K RR.
Nt IP
1.R VR.++1
X log(T))
IP
h441
R+R
h/41
M= k=1 n=l
#/ #=1j=
j=
and
K
ΣΣΣ W=lk=In=l
Mn M
$ al de
RR, K+1 h41
h411
P
rk akk
[.R.j.
K+
W
1=1
Combining these two inequalities, we have:
Σ
D.R.A" ht'
(.R.A))
S log(T')
Σ
Σ
p
[R.j
RR
(117)
#=lk=1
M=1j=1
51

---

Published as a conference paper at ICLR 2025
According to Lemma F3
the following inequality holds:
Rrna de W (6
N+1 (6)/+1)
P of {V/ ) (1/v
(V [h
( (5)
8
}
H SA
B
Wm
The last inequality is because of the events Eg and & in Lemma we have:
Together with Equation 1117
H SA log(T))
Σ
pre Mi
DRR
Ipady V.R,A" k++1
(118)
M=lk==
Now we move to the fourth term Rack By Lemma
R.5 we have:
No.
T (sh and
VR
(8h41)
N41 (oh++))
N
VLCB (sW++)
VA (++ VLCBA" (0h+41) 8
A 1 (s/r )
Then it holds that:
K
V (s a4h))
K
N (5/ a
(x,))
1b (s, a)ll [SN (s, a))
n
log T Σ
$ K (s) [(sh. a)
$ log
SA Σ
K (s, a)ll [s ah.) = (s.
(119)
8,a
The second inequality is because of the mononicity of 4 (s, a). The last inequality is by Cauchy- Schwartz inequality. To continue, note that:
2 (s, a)l [(s at:) = (s, a)]
H
v
(st 1
V.CTAA (s (1) -I Vv V (5h
VILCR (st (w++1) > {3
k=1
H1
H
Vik ( - VITRR (s/ (of++1) TI (+ - VI (5h > [
M=1k=1
H7SAL 9
The first inequality uses Cauchy-Schward inequality and the last inequality is by Eg in Lemma Together with Equation (119) it holds:
F2
K
HW (sh dhi)
H'SAlog(T))
S
(120)
Nok (H
/B
52

---

Published as a conference paper at ICLR 2025
By Lemma R33 with have:
Hi No (s x
S (oggg
(121)
By summing Equation (114). Equation 116 Equation I18.
Equation
120
and Equation
2
since B E (0, H]. we can conclude that:
H
K
Rh*k k else
H A (Tg
2
R=1
Then we have
(Q" + H) SAH
H
Aoggog())
Σ clipl(Qh - (7) a Aminl =0
Amin
(Amin)
(Q* + B) SAH?&
S
00
(122)
Amin
The last inequality is because
S
8²
SA
SA?
A min)
Amin
B
by AM-GM inequality.
F.6 STEP 4: BOUNDING THE EXPECTED GAP-DEPENDEN REGRET
By Equation g). (h ) (s 2 (s Thus, for any episode-step pair (ki, h)
(s &e a cliplV; (s ( a Amial I clipl( Q7) a Aminl-
By Equation (4) in Yang et al. (2021). we have E (Regret( = E D Em= An m4t which further implies
K Σ
E (Regret(K)) s
clipl(Q) - Q7) a
Aminl
Finally, let 1. and = n & with & in Lemma F2 Then the event holds with probability least -
77
# and we also have:
K
E (Regret( < E
clipl(Q) @h) at)
A
E IP(E)
Am
K
"
+ E
clip
@i)
Amin]
ge P(E9)
(Q* H SA
H²SA
+1--7 HT
00
+
Amin
B
(Q' 8 H
S²
(123)
A min
B
The last inequality is because under the event E, we have proved that
(Q' B2 H
S"
Σ clip((Ct (s) a
Amin 5
A Amin
B
by Equation 112) and under the event 8
K #
clip(())
( akt Aminl S HT.
53


Reviews:
[{"review_id": "9j7csRvwjj", "reviewer": "Reviewer_sZn1", "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)$.", "questions": "Is it possible to demonstrate how close the provided regret upper bounds are to optimality? Are there gap-dependent regret lower bounds?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Improved gap-dependent regret upper bounds for learning finite-horizon episodic MDPs are provided.\n- The guarantees are obtained by analyzing some existing near-optimal algorithms for learning finite-horizon episodic MDPs.\n- The regret analysis based on decomposing the errors into reference estimations, advantage estimations, and reference settling seems technically novel.", "weaknesses": "-", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Wp8TyFWZm5", "reviewer": "Reviewer_8zvK", "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.", "questions": "I would like to better understand the level of technical contribution of this paper.\nWhy are surrogate reference functions needed in your analyses but not those of the previous works (Zhang et al 2020, Li et al 2021)?\nCould 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?\n\nCould you provide more comparison and discussion of related work which is model-based and tries to achieve similar goals (gap and variance dependent guarantees)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The regret bounds achieved by the paper improve upon those of prior works.\n\nThe 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.\n\nI 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.", "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BFRZgOW3j6", "reviewer": "Reviewer_mKwy", "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.", "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.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The analysis of \"gap-dependent bound + reference-based algorithm\" is novel and of interest to the RL theory study. \n\nThe proof sketch is clearly written. I checked some technical parts of the paper, and they are correct to me. \n\nThe 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.", "weaknesses": "I did not see major weaknesses in the paper. Here are some minor/barely ones. \n\nIn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0hlGrRAPvs", "reviewer": "Reviewer_Djdi", "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.", "questions": "1. In line 310, there is a typo fo$Q_h^k-Q_h^k$. \n\n2. 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.\n\n3. Lemma B.3 seems incorrect when $\\check{n}(s,a)=1$ immediately after a reset to 0.\n\n4. The $N(s,a)$ in Algorithm 1 should be $n(s,a)$.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 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.\n\n2. The author also proposes an instance-dependent policy-switching cost for the UCB-Advantage algorithm, which could be of independent interest.\n\n3. When variance is low (e.g., in deterministic transitions), the regret exhibits improved dependency on the minimal sub-optimality gap.", "weaknesses": "The main weakness is that the improvement in this work over existing results appears too limited.\n\n1. 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.\n\n2. 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.\n[1] Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments\n\n3. 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 \nlog T rather than a factor of A, which is minor.\n\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)