Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time
Authors: Xiang Ji
Gen Li
Venue: NeurIPS 2023 poster (2023)
Keywords: reinforcement learning theory
regret minimization
minimax optimality
TL;DR: We proposed the first model-free algorithm that can achieve minimax regret optimality in the infinite-horizon discounted setting, with the additional benefit of low burn-in time.

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

Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time
Xiang Ji Princeton
Gen Li f CUHK
Abstract
A crucial problem in reinforcement learning is learning the optimal policy. We study this tabular unfnite-horizon discounted Markov decision processes under the online setting. The existing algorithms either fail to achieve regret optimality have to incur a high memory and computational cost. In addition, existing optimal algorithms all require a long burn-in time in order to achieve optimal sample efficiency, i.c., their optimality is not guaranteed unless sample size surpasses high threshold. We address both open problems by introducing model-frce algorithm that employs variance reduction and a novel technique that switches the execution policy in a llw-yet-adapptie manner. This is the first regret-optimal model-free free algorithm in the discounted setting, with the additional benefit of a low burn-in time.
1 Introduction
In reinforcement learning (RL), crucial task is find the optimal policy that maximizes its expected cumulative reward in any given environment with unknown dynamics. An immense body of literature is dedicated finding algorithms that solve this task with few samples as possible, which is the prime goal under this task. Ideally, one hopes to find an algorithm with theoretical guarantee of optimal sample efficiency. At the same time, this task might be accompanied with additional requirements such as low space complexity and computational cost, as it is common that the state and action spaces exhibit high dimensions in modern applications. The combination of these various goals and requirements presents an important yet challenging problem in algorithm design.
The task of searching for optimal policy has been well-studied by existing work in the generative setting (33 34,
21 []. This fundamental setting allows the freedom of querying samples at any state-action pair. In contrast, it is more realistic but difficult to consider the same task in the online setting, in which samples can only be collected along trajectories generated from executing a policy in the unknown Markov decision process (MDP). Solving this task with optimal sample efficiency requires a careful balance between exploration and exploitation, especially when coupled with other goals such as memory and computational efficiency.
MDPs can be divided into two types: the episodic snite-horizon MDPs and the definite-horizon MDPs. Although these two types of MDPs can be approached in similar ways under the generative setting, there a clear dichotomy between them in the online setting. In an episodic MDP, sample trajectories only defined in fixed-length episodes, so samples are collected in episodes, and reset to an arbitrary initial state occurs at the end of every online episode. Its transition kernel is usually assumed to be non-stationary stationary over time, and the online sample collection process amounts to drawing a single infinitely long sample trajectory with no reset. These differences render most optimal algorithms for episodic
time. In contrast, the transition kernel of an affiite-horizon MDP stays
Depaatment Electrical and Computer Engineering, Princeton University. Princeton, NJ 08544, USA. Department of Statistics, The Chinese University of Hong Kong, Hong Kong, China.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

MDPs suboptimal when applied to mufinitehhorizon MDPs. Without reset and non-stationarity, the high dependency between consecutive trajectory steps in the unfinitehhorize setting presents a new challenge over the episodic setting. In this work, we consider the infinite-horizon discounted MDPs, which is widely used practice but still has some fundamental questions unanswered in theory.
1.1 Sample Efficiency in Infinite-Horizon MDPs
To evaluate the sample efficiency of online RL algorithms, natural and aicely-accepted metric is the cumulative regret. It captures the performance difference between the optimal policy and the learned policy of an algorithm over its online interactions with a given MDP. The notion of cumulative regret was first introduced in the handit literature and later adopted in the RL literature 2 [5]. It is profusely used in the online episodic RL literature. Such works aim to prove regret guarantees for algorithms and provide analyses that characterize such regret guarantees in terms of all problem parameters such state space, action space and sample size in non-asymptotic fashion. A cumulative regret guarantee can also suggest the sample complexity needed to reach a certain level of average regret.
In the online infinite-horizenn setting, many works study different metric called the sample complexity of exploration, first introduced in [17]. In essence, given a target accuracy level e, this metric characterizes the total number of e-suboptimal steps committed by algorithm over infinitely- long trajectory in the MDP. While this is indicative of the sample efficiency of an algorithm, the focus of this metric is very different from that of cumulative regret, as it only reflects the total number of failures but does not distinguish their sizes. As 24 12 point out, even an optimal guarantee on very suboptimal guarantee on the
the sample complexity of exploration can only be converted cumulative regret. To obtain a more quantitative characterization of the total volume of failures in the regime of finite samples, some works have turned to studying cumulative regret guarantees for algorithms.
It was not until recently that some works [24 51: 12 18] begin to research into the problem of cumulative regret minimization in infinite-horie horizon discounted MDPs. Among them, [31] focus on linear MDPs while others study tabular MDPs. In this work, we study the regret minimization problem in the tabular case. Hereafter and throughout, we denote the size of the state space, the size of the action space and the discount factor of the problem MDP with S, A and y, respectively, and let T denote the sample size.
1.2 Model-Based and Model-Free Methods
Since modern RL applications are often large-scale, algorithms with low space complexity and computational complexity are much desired. This renders the distinction between model-based algorithms and model-free algorithms particularly important. The procedure of model-based method includes a model estimation stage that involves estimating the transition kernel and a subsequent planning stage that searches the optimal policy in the learned model. Thus, O A) space is required to store the estimated model. This is unfavorable when the state space is large and memory constraint present. Additionally, updating the transition kernel estimate brings large computational burden. In comparison, model-free methods do not learn the entire model and thus can run with o(S² A) space. Notably, most value- based methods such as Q-learning only require storage of an estimated Q-function, which can take little as ((SA) memory. In the anfinite-horizon discounted setting, although UCBVI-y in [2] can achieve optimal regret, its model-based nature exacts a O(S A) memory and computational cost; conversely, the algorithms in 24 and [8 are model-free but have suboptimal regret guarantee.
1.3 Burn-in Cost in Regret-Optimal RL
Naturally, one aims develop algorithms that find the optimal policy with the fewest number of samples. In regards to regret, this motivates numerous works to work towards algorithms with minimax-optimal cumulative regret. However, the job not done once such an algorithm found. As can be seen in the episodic RL literature, algorithms that achieve optimal regret as sample size tends towards infinity can still have different performance in the regime when T is limited. Specifically, for every existing algorithm, there exists a certain sample size threshold such that regret suboptimal before T exceeds Such threshold is commonly referred to as the initial burn-in time of the algorithm. Therefore, it is of great interest to find algorithm with low burn-in time so that it

---

Sample complexity of exploration
Cumulative Regret
Range of T with optimal regret
Space complexity
Algorithm Delayed Q-learning
35
(1-7)at
84
$$ASTE
(1-2)
never
SA
R-Max
(1-7)e²
A
S
(1-21
never
Sa
UCB-Q
(1-1)'e²
SA
(1-7)3
never
SA
MoRmax
[36]
(1-7)922
8.4
85A3T3
(1-3)3
never
S²A
UCRL
sa
SŠAST
S A
120
(1-7)'e
(1-y)8
UCB-multisaage
S4
83A3T1
49
(1-2) 22
(1->)
never
SA
UCB-mullistage-an
[49
[1 (1-7)
SA
STATTI
(1-7)3
never
SA
M
18
N/A
KV
(8* (S"+ (1-2)*
never
SA
Double Q-learning
14
N/A
(1-2)
SAT
never
SA
UCBVI-
N/A
SAT
9a [1-3]4 00
S²A
12
(1-7)3
Q SlowSwitch-Ach
(This work)
N/A
V
(1-7)
SAT
SA (1-7)17,00
SA
Lower bound
20 12
S4 (1
SAT (1-y)a
N/A
N/A
Table 1: A comparison between our results and existing work in the online infinite-horizon discounted setting. Logarithmic factors are omitted for clearer presentation. The second column shows the sample complexity when the target accuracy is sufficiently small. The third column shows the regret when sample size T is sufficiently large (beyond the burn-in period). The algorithms in the first seven rows only have sample complexity results in their original works; their regret bounds are derived from their respective sample complexity bounds and presented in this table for completeness. Details about the conversions can be found in [12]. The fourth column lists the sample size range in which regret optimality can attained, which shows the burn-in time. We would like point out that the results in [12 24] are under slightly different regret definitions from the regret definition in [18] and this work. fact, their regret metric can be more lenient, and our algorithm can also SAT
achieve OlV [1-7]3)
optimal regret under it. This further discussed in Remark and Appendix B
can still attain optimal regret the sample-starved regime. Such effort has been made by 21 in the generative setting and by 23 26 in the online episodic setting. Yet, this important issue has been addressed in the infinite-horizon setting, as optimal algorithms all suffer long burn-in times.
Specifically, while UCBVI-y in 12 achieves state-of-the-art regret guarantee of Ö(
SAT (1-7)3
which they prove minimax-optima their theory does not guarantee optimality unless the samples size T becomes as large as
A3
T T
(1 (1-7)4
'UCB-muliistgge adv achieves optimal sample complexity only in the high-accuracy regime when - A-2 11)1--))4,, This similar to burm-in threshold in that the optimal guarantec cannot be achieved unless a specific range.
"The regret analysis for MAIN assumes ergodicity parameter
UCBVI-- achieves optimal regret for T' > (1-7)a
A²AA
only if the MDP satisfies SA 1

---

This threshold can be prohibitively large when S and A are huge, which is true in most applications. Thus, this makes reducing these factors the burn-in cost particularly important. For instance, 5-by-5 tic-tac-toe has state space of size 325. While this is manageable number in modern machine learning, any higher power of may cause computational difficulties; in contrast, the horizon of this game is much smaller-no no more than 25. Since no lower bound precludes regret optimality for 2 (I-7)². one might hope to design an algorithm with smaller 5 and A factors in the burn-in cost so that it can achieve optimality even in the sample-starved regime.
1.4 Summary of Contributions
While is encouraging to see recent works have shown that in the discounted setting, model- free methods can provide nearly optimal guarantees on sample complexity of exploration and that model-based methods can provide nearly optimal finite-sample regret guarantees, there still lacks model-free approach that can attain regret optimality. In the orthogonal direction, there is still vacancy for algorithms that can attain optimal regret for a broader sample size range, i.., with fewer samples than 8 A²
[oly[I->]
In fact, summarize these two lingering theoretical questions follows:
Is there an algorithm that can achieve minimax regret optimality with low space complexity and computational complexity in the infinit-hhorizn -hrizon discounted setting, even when sample size limited?
We answer this question affirmatively with new algorithm Q-SlowSwitch-AGe Adv, which uses variance reduction and a novel adaptive switching technique. It is the first model-free algorithm that achieves optimal regret the infinite-horizon discounted setting. This result can be summarized as follows:
Theorem (informal). For any sample size poly(l->)}
SA
Q-SlowSwitch-Adi is guaranteed to with space complexity O(SA) and computa-
achieve near-optimal cumulative regret Ö (V tional complexity O(T)).
SAT (1-7)3
A formal theorem is presented in Section 4 its proof can be found in the full version 14. We also
provide a complete summary of related prior results in Table T A discussion about the additional related work is deferred to Appendix A
Problem Formulation
Let us specify the problem we aim to study in this section. Throughout this paper, we let A(X) denote the probability simplex over any set X. We also introduce the notation [m] := f1,2, m] for positive integer m.
2.1 Infinite-Horzoon Discounted Markov Decision Process
We consider an infinite-horizon discounted Markov decision process (MDP) represented with (S,A,7, P.r). Notably, we consider a tabular one, in which = (1.,,......) denotes the state space with size S and A = {1, ... ..) .A} denotes the action space with size A. P. : x A ASS) denotes the probability transition kernel in that P(-|s, a) E A(S) is the transition probability vector from state
S when action E A is taken. S x A [0, 1] denotes the reward function, which is assumed to be deterministic this work. Specifically, r(s, a) is the immediate reward for taking action a E A state S. Lastly, y denotes the discount factor for the reward, which makes T-7 the effective horizon.
1
(stationary) policy и S - A(A) specifies a rule for action selection in that (-1s)) E A(A) the action selection probability vector at state S. We overload this notation by letting (s)) denote the action policy π takes at state s. Given a policy æ, the Q-function of π is defined as
(T(s))) : E
(r( Σ 0
8o = =,

---

in which 8:41 P(-(st,ai) fort 0 and ~ ((1(s) fort 2 1. Moreover, the value function of π defined as
8
(*) E
2 rr((,,
80 80=88
in which $1+1 P(-)st, ae) and a, ~ (T-(st) for 2 The Q-function and value function satisfy an equation, called the Bellman equation 66
Q" (0 - r(s, a) D PP(),, [V*
(1)
A policy x² is called an optimal policy if it maximizes the value function for all states simultaneously. The optimal value function and optimal Q-function can be defined as
(*(s) == max V* V" (*) (8)
"
(s, max Q (s, (s,
which satisfy
(*(s) = V and Q'(s,))= (s,a)
for any optimal policy n². The optimal policy always exists and satisfies the Bellman optimality equation 30
Q" (s.a) rss, a) + +BB. P(Ha.)))
max a'EA
max (
= a) + PB (8)).
(2)
2.2 Online Learning in Infinite-Horizon MDP
We consider the online
setting, in which the agent is permitted to execute a total of T' steps sequentially in the MDP. More specifically, the agent starts from arbitrary (and possibly adversarial) initial state 81. At each step E [T]. the agent at state computes policy Tr, takes action a, based Te (-)ss),, receives reward r(st, ax), and transitions state 8141 in the following step. At the end of execution, the agent generates a trajectory (s1, a1, T1, $2, 02 T2, aT, rT), which amounts samples.
2.3 Problem: Regret Minimization
As a standard metric to evaluate the performance the aforementioned agent over finite number of T steps, the cumulative regret with respect to the sequence of stationary policies {T, I7 learned by the algorithm defined as follows:
T
Regret (T) = Σ (*(()) (()s)))"(ssss)) (s.))
(3)
Verbally, the regret measures the cumulative suboptimality between the optimal policy and the execution policy T, at each step throughout the T-step online interaction process. Naturally, one aims minimize this regret by finding algorithm whose regret scales optimally in T. This would require a strategic balance between exploration and exploitation, which can be difficult when sample size 7' is small.
Remark 1. In the infinite-horizon setting, many prior works 12 2 consider slightly different regret definitions with respect to con-stationary policies. Specifically, at each along the trajectory, this different regret metric compares the optimal value function V*(s)) against the expected cumulative reward of running the -tasttaionnay policy { starting from st. By doing this, it is effectively evaluating the cumulative reward difference between the stationary optimal policy and a non-stationary algorithm. While there exists no formal conversion between the regret defined in this way and the one in 3 it is expected to smaller and thus more easily controlled than (3), because the execution policy improves over time. In addition, can show our algorithm also achieves the same level of
5

---

Algorithm 1: Q-SlowSwitch--Ad
Initialize: a(s,a), Q Jazy (s,a), Q(s, a), (s, (s, a), (s(s, t a), ((, a) + 0: D - dict();
(ss, a) -
Vs), ( (8) T QLCB (s,
ne a), ot (8, a), ady (8, a), o (s. a), BR (8, a), 88 (s, t 0: u wwitch
False;
u= (5) < True; H I- li = log SAT
2
for 1. 7 do
Take action a,
TT (s:) arg max, Quary a), and draw s(+1 P(- at): (st, az) t Nss, at) + + + (st, at); Update the counter
H+l. # Update the learning rate
5
Ta - H+n
(UCB((s, a:) update-q-uch(); # Compute the UCB. See Algorithm
QLCB (5)) update-q-leb(); Compute the LCB, See Algorithm
Q" at) - update---reefreecc((:: # Compute the reference value. See Algorithm
Q(sr, (1) - minn(" at), QUCB (s), ax);;
10
V(s) max. Q(s,,(())))) a);;
VLCB t mmxx QLCB a), VLCB(s:)
12
((s at) t -52, a+) + QM (5) - Q(s;, at). # Track the staleness of current policy swicch True then
13
14
Q Qlazy + update-q-lazy();
Update execution policy's 's Q-function (switch policy)
15
D dict();
Reset the buffer
switch t- Falsc;
16
17
Di(s), at) + Q(s(.(())) az). # Add the new transition and Q entry to the buffer ."" Switch policy when the staleness tracker large""" """
18
19
ir 0 a.) > I-y then
20
Qu a1) f- Q(s,,
# Save the current Q entry for staleness determination later switch <- True; # Signal to switch policy at the following step (ss,, an) +- 0: # Reset the staleness tracker
21
V VLCB (st) > 3 then
(((s) V(s)), ur (s²) True;
24
else if u rf (st) -True then
(s.) V(se), re(((s) (s:) = False. # Update the reference only certain conditions
26
regret under this different definition with an analysis specifically tailored to our algorithm, which deferred to Appendix B Furthermore, since the transition kernel in the infinite-horizon setting is invariant over time and the optimal policy itself is also stationary, it is more natural to compare the optimal policy to a stationary policy, e.g., the policy T deployed by the algorithm at each step, as in (3). Before this work, this has also been recently studied in 44 [8].
Notation. Given any vector x E SA that represents function x: S A + R, we use æ(s, a) to denote the entry corresponding the state-action pair (s) We also denote the probability transition vector at (8, a) with
P... = P(: 8, E RRXS
that is, given any V E RRS Ps.aV= E (V')). For two vectors x, y E R.A.A we override notation S y to mean that æ(s,a) a) S y( in every dimension (8,
3 Algorithm
In this section, we present our algorithm Q-SlowSwitch-AAv and some relevant discussion.

---

Algorithm 2: Auxiliary functions
Function update-q-ucbee
QUCB (St, a;) 1m,, (st + t/ (r(8), (V(+++1) + cby (1-ラ)リ
3 Function update-q-lcb():
QLCB (s,, (1 1/. )
QLCB (st, az) 7m (T((, + coy パータা
Function update-q-lazy ():
for every a(),a), D do Qlazy t 9.
# Update execution policy with the buffer
Function update-q-rrffrreceed
[u (' 4x) t update-moments():
[ĀR (8t, 0+) <- updlatereference-bonus|]
BR t- (st, + (1 - 1//m) (ec.
10
(1/441-))3
7n
Q at) +
11
(1 - mm (s:, at) + (r(s), az) + (V($++1) - (st+1) + (st, + BR).
12 Function update-momente ():
1o (st, ax) f (1 - ) (5t, at) + (8++1)) # Running mean of the reference
13
gre (st, at) t (1 1
n ) (st, at) + (V (R((s(11))
# *Running 2nd moment of the
14
reference
(s az) (1 The ady az) + nm (V(s+41) (R((5+2)); Running mean of
15
the advantage
gidv a.) + mn o a.) + Tn (V(s441) (R(4))))) ? # Running 2nd
moment of the advantage
Function (itiateerefference-bmuuos())
18
Buext (st, at) <
c (otet(s) az) - (1rel (st, az)) - (ady - (yeady (uaady (st,
8 ae) t- Buext (sts az)
B (86,
19
BR at) x- Buext (ot, az).
3.1 Review: Q-Learning with UCB and reference advantage
First, we make brief review of the Q-Jearning with UCB method proposed in [15] referred as UCB-Q hereafter, and its variance-reducce variant UCBB--AAvvantage, later introduced in [48]. The Q-function updates in Q-SlowSwitch-Ady are inspired by these two methods.
Q-learning with UCB The original Q-learning 41 40 is a fixed-point iteration based on a
stochastic approximation of the Bellman optimality equation 2 It uses greedy policy with respect to its estimate of Q", whose update rule can be summarized as:
Q(s.a)
(L-)))(ssaa)
(r(s, a) +PP..V)
(5)
Above, Q (resp. V) is the running estimate of Q* (resp. V`); 17 E (0, 1] is the (possibly varying) learning rate; P.,a V stochastic approximation P..oV (cf. 4D. Commonly, V(s') is used for P..a V in (5) as an unbiased estimate of P.a. V, when sample of state transition from (s, a), namely (s, a, s'), available.
However, as [15] point out, using (5) naïvely suffers from great regret suboptimality, for it rules out the state-acte antionction pairs with high value but few observations. To promote the exploration of such state-action pairs, UCB-Q Q appends (5) with an exploration bonus. Its update rule can be written as:
QUCB
(1 - UCB
(s,
+ 7 (r(ss a) PP.. V VV+0 +6).
(6)
To encourage exploration, the bonus b 2 0 is designed to maintain an upper confidence bound (UCB)
on (P... P,.)V, which in turn keeps UCB (s, a) as "optimistie" overestimate of Q' a).
7

---

Q-learning with UCB and reference advantage The regret guarantee for UCB-Q is still shy of being optimal. In order to attain optimality, one can turn the celebrated idea of variance reduction [16 23 37 which decomposes the stochastic approximation target into two parts: low-variance reference estimated with batches of samples and a low-magnitude advantage estimated with every new sample. In this spirit, [48] introduce UCB-Q-Advanter
based on UCB-Q and
a reference-advantage decomposition. Specifically, given a reference V that is maintained as an approximation for V*, the update rule of UCB Q- Q-Avaantage reads:
(= - (1 n)Q (s, + ( + ((P..a (V VB) + PVB(s,,)) + +B))
(7)
This idea of more details:
7 is used in subroutine ueefae---reeerrenco) of our algorithm. Let us discuss it in
Given a transition sample (s, a, s'), we can take V(s') (s') as an unbiased estimate of the advantage (V - VR). The magnitude of V - VR is small when V and VR are close. This engenders smaller stochastic volatility, compared to P
from UCB-Q.
The reference estimate PVR is stochastic approximation of PVR, In our algorithm, the auxiliary estimate ب yr (cf. Line of of Algorithmp 2 is used as the estimate for PVR, Specifi- cally, 2=0 (s, a) is running mean of Ps,a VR based on the samples from all past visitations of (s, a). contrast to the advantage, which computed every time a new sample arrives, the reference is computed with batch of samples and thus more stable. In sacrifice, the reference is only updated intermittently and not as up-to-date as the advantage.
The exploration bonus JR is computed from the auxiliary estimates in Lid to serve as an upper confidence bound on the aggregation of the aforementioned reference and advantage. Specifically, for each (s, a), 1ea (s.a) a) and o- (s,a) a) are the running mean and 2nd moment of the reference [PVR[(s, a) respectively; f pady (s. a) and gadv (s. a)) are the running mean and 2nd moment of the advantage [P(V- VR) (s, a) respectively; B (s,, a) combines the empirical standard deviations of the reference and the advantage; 58, a) is the temporal difference between BR a) and its previous value. (s,, a) can be computed from these estimates as a
average of ( a). Thanks to the low variability of the reference PVR, we can obtain more accurate, milder overestimation in the upper confidence bound for faster overall convergence.
3.2 Review: Early settlement of reference value
Given the optimistic overestimates QUCB and Q", it is natural to design an update rule of our Q-function estimate as the minimum of the estimate itself and these two overestimates (Line (f Algorithm []. This makes our Q-function estimate monotonically decrease without violating the optimistic principle Q 2 Q*, which effectively enables us to lessen the overestimation in Q over time until it converges to Q". In fact, this is precisely the update rule in UCB-Q-Ade Q-Avaanaag [48). Nevertheless, we need to equip our algorithm with additional features to strive for regret optimality.
23 introduced way to update the reference with higher sample efficiency in the finite-horizon setting. As they noted, it is critical to update the reference V in a smart fashion so as to balance the tradeoff between its synchronization with V and the volatility that results from too many stochastic updates. Concretely, the reference VR needs to be updated in a timely manner from V so that the magnitude of Pa,((V VB) can be kept low desired, but the updates cannot be too frequent either,
because the stochasticity or variance in (V, a) could be high as that in Pr.a V of (6) and thus lead to suboptimality if it is not carefully controlled. To resolve this dilemma, we can update R. until it becomes sufficiently close to V and fix its value thereafter.
To this end, we maintain a "pessimistic" underestimate QLCB (resp. VLCB) of Q* (resp. V*) in the algorithm, which are computed from the lower confidence bound for Q' (resp. V*). This can provide us with an upper bound on VRR V*, which will be used to determine when the update of the reference /R should be stopped.
In particular, the if-else block in Line 23 to 26 is designed to keep the reference V synchronized with V for each state respectively and terminate the update once
(ss) LLCB
+3 5 V +3.
(8)
8

---

This can guarantee VV - |R| I 6 sthroughout the execution of the algorithm. As a result, the standard deviation of Ps.a (V VR) ) is guaranteed to be (1),, which can be Ol - 011ng) times smaller than the
standard deviation of P V in 2 This can lead smaller 1-q factor in the final regret guarantee.
3.3 Adaptive low-switching greedy policy
Although these aforementioned designs from the of our estimate Q. they are still insufficient to attain regret optimality in the infinite-horizon setting. Since data collection takes place policy can inflict a long-lasting volatility on the future trajectory and slow down the convergence. This is precisely the difficulty of the infinite-horizon setting over the finite-horizon one. The need to control the trajectory variability motivates us to design a novel adaptive switching technique.
literature help increase the accuracy
single trajectory with no reset, drastic changes in the execution
Recall in UCB-Q and UCB-Q-Advantage. the execution policy is greedy with respect the estimate Q. i... (5)) = arg max, ((,,, a). Every time Q gets updated, what the algorithm effectively does is to make an estimate of Q with the samples generated by Ty. Such Q is only estimated and updated once before the execution policy is switched to T++1- This seems insufficient from a stochastic fixed-point iteration perspective, so we seek update it more and learn each Q better before switching to a new policy.
To tackle this issue, we make the execution policy greedy to Qlaxy, which is updated lazily yet adaptively in Q-SlowSwitch-Adw Specifically, for every (s, a), we use 0(s, a) (cf. Line 12 in Algorithm 2 to keep track of the cumulative difference between the current Q(s, a) and Q a), the latter of which is defined to be the value of Q(s, a) last time Qlary is updated immediately after visiting (s, a). Whenever (ss, a) exceeds r
_ indicating Qlaay (s,a) and the execution policy has
become outdated with respect to the current Q(s, a), we reset ((s, a) and set switch True, which will direct the algorithm to update the entire function Qlaay in the following step. update-q-lazyO updates Qlaay with the samples from D, which is dictionary that serves as a buffer to store all the new sample transitions and their latest estimates since the last update of Qlazy,
In contrast, conventional low-switching algorithms update the execution policy on a predetermined, exponentially phased schedule [8).8). While trajectory stability is attained with these algorithms, as time goes on, it takes them exponentially longer to update policy, making them oblivious to recent large updates in the estimated Q-function. This would lead to suboptimal regret in the infinite-horizon setting, as continual choices of suboptimal actions will keep a lasting effect on future trajectory in the absence of trajectory reset. This issue is overcome in our algorithm by ignoring minor changes in function Q yet still being adaptive to substantial changes in any state-action pair.
Main Results
Our model-free algorithm Q-SlowSwitch-Adv can achieve optimal regret with short burn-in time. Its theoretical guarantee can be summarized in the following theorem.
Theorem Choose any å E 1). Suppose log S and c chosen to be a sufficiently large Then with probability at least 1 - ö, Algorithm achieves
universal constant in Algorithm !
(11
SAT
SA
Regret S Co
(1-7)3 (1 78 +
(9)
for an absolute constant Co >
To prove this theorem, we need to use recursive error decomposition scheme different from the existing work. The stationary nature of the infinite-horioon setting gives rise to several error terms unique to the infinite-horizon setting, and our novel switching technique is crucial at controlling them optimally. The proof provided in the full version 14 Now let us highlight a few key properties of our algorithm.

---

Optimal regret with low burn-in. Q-SlowSwitch-Ady achieves optimal regret modulo some logarithmic factor as soon as the sample size T exceeds
SA
(10)
poly(1 - 7)
This burn-in threshold is significantly lower than the poly(1-7)
A
threshold in 12 when SA >
1-7
In other words, in the regime of (10), the regret of Q- 2-SlowSWitch-AAr is guaranteed to satisfy
SAT
(T) σ
(11)
(1 71
which matches the lower bound in Table 1
Sample complexity. As corollary of Theorem [ can be seen that Q-SlowSwitch-Ady attains e-average regret (i.e. F (Tgret((T)) S for any fixed 7') with sample complexity
o (
SA
(1- (11-73862
(12)
This is lower than the sample complexity of the model-free algorithm in [24]. which is Ō( 8.
(1-
Moreover, 12 holds true for any desired accuracy 6 E (0, (--)"") This a broader range than the ones in 12 49, which involve higher order of S and A and only allow their algorithms to attain their respective optimal sample complexity in the high-precision regime.
Space complexity. Q-SlowSwitch-AGe a model-free algorithm that keeps few estimates of the Q-function during execution, so its memory cost is low O(SA). This is not improvable in the tabular setting, since it requires ((SA) units of space to store the optimal policy. In contrast, the model-based UCBVI- in [12 stores estimate of the probability transition kernel and thus incurs higher memory cost of A)
Computational complexity. The computational cost of D-SlowSwitch-Adv is only O(T). This is on the same order as reading samples along the 7 T'length executed trajectory and is thus unimprovable. In comparison, our algorithm has considerably lower computational cost than the in (12), which requires A(S"AT) operations overall.
Discussion
This work has introduced a model-free algorithm that achieves optimal regret in infinite-horizon discounted MDPs, which reduces the space and computational complexity requirement for regret optimality in the existing work. It also achieves optimal sample efficiency with short burn-in time compared to other algorithms, including [12] 49). Moreover, our algorithm has demonstrated the importance of switching policies slowly in infinite-horizon MDPs and introduced novel technique might be of additional interest to future work. While our burn-in threshold is considerably reduced and A, still has nontrivial suboptimality the effective horizon T- which is a price we pay for using the reference investigate how to further improve the effective horizon factors in the burn-in cost.
with respect to the order
referenceeadvvnttage advantage technique. It is open for future work to
Acknowledgements
The authors are very grateful to Yuxin Chen for helpful advice as well as suggesting the direction. X. was supported in part by the NSF grants 1907661 and 2014279.
References
[1] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020.
10

---

[2] Peter Auer and Ronald Ortner. Online regret bounds for a new reinforcement learning algorithm. Proceedings 1st Austrian Cognitive Vision Workshop (ACVW 2005), pages 35-42, 2005.
[3] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn,, 23:33 236, may 2002. ISSN 0885-6125. URL https 7/doi. 10. 1023 A: 1013689704522
[4] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[5] 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.
[6] Dimitri P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 3rd edition, 2005.
[7] Ronen I. Brafman and Moshe Tennenholtz. R-max- a general polynomial time algorithm for near-optimal reinforcement learning. J. Mach. Learn. Res., 3(null):213 231, mar 2003. ISSN 1532-4435. doi: 10. 10.116//152233337655088333 URL natttps//ddoi.org/100 163244303765208377
[8] Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang. Q-learning with ucb exploration sample efficient for infinite-horizon mdp. arXiv preprint /rXiv:/901.093/) 2019.
(9] Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning. pages 1049-1058. PMLR, 2017.
[10] Minbo Gao, Tianle Xie, Simon Du, and Lin F Yang. provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint arXiv:2101.00494, 2021.
[11] Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang. Stabilized svrg: Simple variance reduction for nonconvex optimization. Conference on learning theory, pages 1394-1448. PMLR, 2019.
[12] Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps. Advances in Neural Information Processing Systems, 34:22288-22300 2021.
[13] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. J. Mach. Learn. Res., 11:1563-1600 Aug 2010. ISSN 1532-4435.
[14] Xiang Ji and Gen Li. Regret-optimal model-free reinforcement learning for discounted mdps with short burn-in time. arXiv preprini arXiv:2305. 15546, 2023.
[15] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning Provably Efficient? arXiv e-prints, art. 180.::18....3765, July 2018
[16] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive vari- ance reduction. In Proceedings of the 26th International Conference on Neural Information Processing Systems, NIPS' 13, pages 315-323, Red Hook, NY, USA, 2013. Curran Associates Inc.
[17] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
[18] Ian A Kash, Lev Reyzin, and Zishun Yu. Slowly changing adversarial bandit algorithms are provably efficient for discounted mdps. arXiv preprint arXiv:2205. 09056, 2022.
[19] Michael Kearns and Satinder Singh. Unite-ssamle convergence rates for q-learning and indirect algorithms. In Proceedings of the 1998 Conference on Advances in Neural Information Processing Systems II, pages 996-1002, Cambridge, MA, USA, 1999. MIT Press.
[20] Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. International Conference on Algorithmic Learning Theory, pages 320-334. Springer, 2012.

---

[21] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural information processing systems, 33: 12811-128122 2020.
[22] Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity of asyn- chronous q-learning: Sharper analysis and variance reduction. Advances in neural information processing systems, 33:7031-7043, 2020.
[23] 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,
17776, 2021.
[24] Shuang Liu and Hao Su. Regret bounds for discounted mdps. arXiv preprint arXiv:2002.05118. 2020.
[25] Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance- reduced) policy gradient and natural policy gradient methods. Advances Neural Information Processing Systems, 33:7624-7636, 2020.
[26] Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momen- tum q-learning: Correcting the bias without forgetting. In International Conference on Machine Learning, pages 7609-7618, 8. PMLR, 2021.
[27] 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, pages 2613-2621. PMLR, 2017.
[28] Aldo Pacchiano, Philip Ball, Jack
Krzysztof Choromanski, and Stephen Roberts. On optimism in model- reinforcement learning. arXiv preprint arXiv:2006, /911,, 2020.
[29] Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In International conference on machine learning, pages 4026-4044000 4035. PMLR, 2018
[30] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779.
[31] Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog (t) switching cost. arXiv preprint 2XXXi:2222.0638.3 2022.
[32] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint urXiv:2202. 13890, 2022.
[33] Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving discounted markov decision process with a generative model. 2018
arXiv preprint
[34] Aaron Sidford, Mengdi Wang. Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms,, pages 770-787. SIAM, 2018.
[35] Alexander I.. Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L. Littman. Pac model-free reinforcement lcarning. In Proceedings of the 23rd International Conference on Machine Learning, ICML '06, pages 881-888, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933832.
[36] Istvan Szita and Csaba Szepesvari. Masel-based reinforcement learning with nearly tight exploration complexity bounds. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, pages 1031-1038, Madison, WI, USA, 2010. Omnipress. ISBN 978 9781605589077.
[37] Martin Wainwright. Variance-reduced q-learning is minimax optimal. arXiv preprint arXiv:1906.044 04697, 2019.
12

---

[38] Mengdi Wang. Randomized linear programming solves the discounted markov decision problem nearly-linear (sometimes sublinear) running time. arXiv preprint 2Xiv:1704.01862 2017.
[39] Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems, 34:13524- 13536, 2021.
[40] C. J. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, King's College, Oxford, 1989.
[41] Christopher C. H. Watkins and Peter Dayan. Q-learning. Machine Learning, 8(3):299-222. 1992. doi: 10. 10.00///F00999298.
[42] Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057-2075 2014.
[43] Tengyu Xu, Zhe Wang, Zhou, and Yingbin Liang. Reanalysis variance reduced temporal difference learning, arXiv preprint arXiv:2001.01820 2020.
[44] Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous q-leaming. arXiv preprint arXiv:2203.0736. 2022.
[45] Kunhe Yang, Lin Yang, and Simon Du Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576-1584. PMLR, 2021.
[46] 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.
[47] Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari, Mengdi Wang, et al. On the convergence and sample efficiency of variance-reduced policy gradient method. Advances Neural Information Processing Systems, 34:2228-222 2240, 2021.
[48] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learn- ingvia reference-advantage decomposition. Advances in Neural Information Processing Systems, 18:15198-15207 2020.
[49] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. In International Conference on Machine Learning, pages 12653- 12662. PMLR, 2021.
[50] Zihan Zhang, Yuhang Jiang, Yuan Zhou, and Xiangyang Near-optimal regret bounds for multi-batch reinforcement learning. arXiv preprint arXiv:2210.08238 2022.
[51] Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning. pages 12793-1220 12802. PMLR, 2021.
13

---

A Related Work
In this section, we take moment discuss the related work beyond those in Table
Regret analysis for online episodic RL In the online episodic setting, regret is the predominant choice of metric for demonstrating the sample efficiency of a method 45
was the first to introduce a model- based method that can achieve near-optimal regret guarantee, but the model-based nature of their method induces high space complexity and burn-in time. On the other hand, model-free methods are proposed in [], which are motivated by Q-lcarning and thus enjoy low space complexity. However, these methods cannot guarantee optimal regret. It was not until 48 that proposed the first model-free method with optimal regret guarantee UCB-Q-Advantage Q-Advantage, but incurs large burn-in time of 5 H where H is the horizon of the episodic MDP. In addition, 26 proposed UCB-M-Q, a Q-learning variant with momentum, which can achieve optimal regret with low burn-in time, but it requires the storage of all momentum bias and thus incurs high memory cost. Recently, [23] propose Q-learning variant with variance reduction that achieves optimal regret with AH) space complexity and S Apoly (H) burn-in threshold the same time. Table in (23 provides a more detailed comparison of related work from the online episodic RL literature.
Sample complexity for infinite-horizon RL In the mnrinit-hooiizon setting, there exist other sample efficiency metrics besides sample complexity of exploration. Initially, [19] considered the sample complexity needed find e-approximate optimal policy. The same definition is also considered in 38 34 33) 21). Later, 37 studied the sample complexity needed to find an c-approximate optimal Q-function. Note that all of these works assume the generative setting. Indeed, limitation of these aforementioned sample complexity definitions is that they only measure the performance of the final output policy and do reflect the online regret during learning. Thus, existing works that study the online setting consider sample complexity of exploration and cumulative regret instead.
Variance reduction in RL The idea of variance reduction was first introduced to accelerate stochastic finite-sum optimization by [16], which is followed by a rich literature (4 ( [1]. Later,
for better sample efficiency in RL, it is applied to policy gradient methods [25
47
29
well
as value-based methods in various problems including generative setting RI. 33
policy
evaluation 9 43 asynchronous Q-learning 22 44
and offline RL 446 32
Low-switching algorithms Since our algorithm includes a novel feature that switches the execution policy slowly, make review of the low-switching approaches in RL. The idea of changing the exccution policy infrequently during learning was first introduced by [3] as an approach to minimize regret in the multi-armed bandit problem. [5] adapted this idea to tabular RL and formalized the switching cost as a secondary metric that an algorithm can minimize. To reduce the number of policy switches and thus the switching cost, their algorithm updates the policy in geometrically longer intervals. Similar techniques can be found in [48), whose algorithm can achieve regret optimality while maintaining low switching cost. Later, [10 39] introduced a new low- switswichhig approach in linear MDPs by switching policies when the estimated covariance matrix gets significant update. All these methods guarantee a Ollog 7') switching cost. The switching cost guarantee was later improved to Olog log 7') by the algorithms proposed in 50
B A Discussion about Different Regret Metrics
As have discussed carlier, multiple metrics exist in the existing literature for evaluating the online
performance of an RL algorithm in the -hoiittee setting. In fact, [1] and [24] both use a respectively different regret metric from the one in this work and [18]. An argument showing the
equivalence between the regret metric in [24 and the one in [12 is discussed in Appendix A.2 of
[12. For this reason and the fact that the regret guarantee in 22 is not minimax-optinal, we focus
on the relation between our theoretical guarantee in Theorem and the regret metric from [2 in this section.
Recall that the goal of RL to learn the optimal policy through online interactions with the environ- ment (and there always exists stationary optimal policy), so the regret metric we consider in this
14

---

work is
Regret(T) -V(r)))) (
(13)
where ne is the stationary policy that the algorithm uses to take action ds step The non-stationary regret metric considered in is
T
Re (T) =
(*((s) - ((ms)
(14)
1=1
Here, (x=)) واك p'r(#; (8,) 60 = s]. which the expected cumulative future reward of the non-stationary algorithm starting from time t.
In fact, similar difference can also be observed in the literature focused on sample complexity of compares the optimal value function V*(s:) against V (sz).
exploration. Notably, the metric in 49
while the metric in works such as 35
compares against ((=;)=-(())) (8t).
There is formal equivalence between the two regret metrics in general, despite the intuition we have provided in Remark [ that RegretNs(IT) (T") should be smaller than Regret(T) for any improving algorithm. However, we can show that the specific algorithm Q-SlowSwitch-AAd (Algorithm I
(1-7)3) regret under the regret metric defined in [22 which matches the lower bound in 12 and is thus optimal for this metric as well.
achieves Ö(V SAT
Before the analysis, let us first define notation. Let f and be two real-valued functions that take == (S, Y, 3)) as arguments. there exists a universal constant C > 0 such that f(X) S Cg(X) for any instantiation of X, denote this with the notation f(X) 2 9(x).
Let us define
T (1SISTT:: #441)
(15)
which is the of time indices that the execution policy switches in the following step, and
Th (1 S 1 T: 1+ h E T for some 0 < h < H}.
(16)
which is the set of time indices that the execution policy switches in any of the following H steps. First, notice
Σ ((m;)32.ss))
Σ
ETTN
1=
h
TT
Ar ((854))00+0)
Σ
Ar(otts 1-9
4TTH
i=0
1=0
H
H
H - E''r(ss
E
r ( a(ti)
+
1
T
k=1
2=0
1=0
Tlog T
(17)
(1 7)3'
where the second line holds when H 2 inequality. Similarly, we have
log I-7. and the last line makes use of the Azuma- Hoeff-no
T Tlog T
Σ TH
V*((s))
Extr(544i 2
(
(18)
since π. TT4i for 0 S i < H and & Th.
15

---

Putting 17 and 18
together leads to
T
Regret(T) Regret (T)
Σ
(s)) (sc) ((s))ia)st))
[=1
log
77 log T
+
(19)
(1 - 7)3
(1 7)2
by noticing that EIETH (V*t(8)) v( (s)))
2
TH
2
log (1- (1-7)=
1-7
Since our algorithm low-switching and [T] S Ō 34 (SA))/4T)1 the two regret metrics
the difference between [9] dominated by the upper bound on the regret itself. Thus, given our result SAT
(1-7)9/3
(1 (1-2)%/
from Theorem that Regrot(T) I Ō(v (1-7)T>, ). we can conclude Regret S Ō(V (1-7)²
SAT
for our algorithm Q-SlowSwitch-Ade switching cost is dominated by the regret itself, e.g., when the switching cost is o(vT).
fact, this conversion holds as long as the algorithm's
16


Reviews:
[{"review_id": "YECczxk8N2", "reviewer": "Reviewer_zms9", "summary": "The paper studies online learning in tabular infinite horizon MDPs, and proposes a model free algorithm that obtains (nearly) minimax optimal regret with space complexity $SA$, and such that the number of time steps needed to reach the minimax-optimality regime is $O(SA/(1-\\gamma)^{13})$.\nPrior art achieving minimax optimal regret required space complexity $S^2 A$ and $O(S^3A^2/(1-\\gamma)^{4})$ time steps to reach the optimal regime.\nIt should be noted the definition of regret used here is not the same as that of prior art.", "questions": "- Is there a more formal treatment of the two regret definitions? It would be helpful to make a more educated decision here; the improvement would have been marginal even if the objectives considered were the same, and when taking into account it may not even be an actual improvement --- the contribution seems questionable.\n- It seems like the approach given here borrowed most of the algorithm from the finite horizon case [54] and then employs a slow switching strategy to essentially reduce the infinite horizon problem to a finite horizon one, thereby gaining in the $SA$ factors but loosing in the horizon. This also seems to be the source of the different regret definition. The presentation does not make this entirely clear however, is this more or less the case?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The paper proposes a new approach to learning infinite horizon MDPs.\n* The paper (perhaps) advances state of the art in online learning infinite horizon tabular MDPs.", "weaknesses": "- It is hard to say this work directly improves [14] because the objective considered is not the same. It would be helpful if a more formal discussion of this point was provided by the authors. For the same reason it is also unclear if the lower bound (also from [14]) applies. Given, this, the way the results are presented in the table are misleading.\n- The improvement is rather incremental, shaving off a factor of $O(SA)$ (at the cost of an extra $(1-\\gamma)^4$) from the lower order (non $T$ dependent) term. In addition, the algorithm is complicated and presentation does not make it particularly easy to understand.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate you taking the time to provide this valuable review! Let us provide responses to your comments and questions as follows. \n\n> It is hard to say this work directly improves [14] ...\n\n> Is there a more formal treatment of the two regret definitions? It would be helpful to make a more educated decision here.\n\nThis is a good question. While there is no discussion about this difference in the existing literature, let us provide some more explanation of the relationship between the two regret definitions here, in addition to our brief discussion in Section 2.3. The difference lies in the quantity being compared against the optimal value function at every step $t$. In the definition we used (also in [55,19]), (i) it is the expected cumulative reward of the execution policy $\\pi_t$ at time $t$, i.e., $V^{\\pi_t}(s) := E[\\sum_{i=0}^\\infty \\gamma^i r(s_i, \\pi_{t}(s_i)) | s_0=s]$. Note that $\\pi_t$ is a stationary policy. In the other definition (of [14]), (ii) it is the expected cumulative future reward of the algorithm since time $t$. This can be viewed as the value function of the non-stationary policy $\\\\{\\pi_j\\\\}\\_{j=t}^\\infty$, i.e., $V^{\\\\{\\pi_j\\\\}\\_{j=t}^\\infty}(s) := E[\\sum_{i=0}^\\infty \\gamma^i r(s_i, \\pi_{t+i}(s_i)) | s_0=s]$. When the execution policy $\\pi_t$ is becoming more and more optimal over the course of execution, which is expected given the theoretical results from [14] and our paper, it is clear that $V^{\\\\{\\pi_j\\\\}\\_{j=t}^\\infty}$ of (ii) should be larger than $V^{\\pi_t}$ of (i). This makes the regret $V^{\\star}(s_t) - V^{\\\\{\\pi_j\\\\}\\_{j=t}^\\infty}(s_t)$ defined with (ii) smaller than the regret $V^{\\star}(s_t) - V^{\\pi_t}(s_t)$ defined with (i), so it can be seen that the regret with (ii) is a more lenient metric than (i), which means an algorithm that can achieve certain guarantee under regret (i) should also be able to achieve the same guarantee under regret (ii). Thus, this means our , and the lower bound under our regret (i) is at least the one for (ii). But overall, this difference is not big enough to change the order of regret bounds, and we included [14] in our table for completeness. We can be clearer about the relationship between these two definitions and its implications when we revise the paper.\n\n>  The improvement would have been marginal even if the objectives considered were the same, and when taking into account it may not even be an actual improvement --- the contribution seems questionable.\n\n> The improvement is rather incremental, shaving off a factor of $O(SA)$ ...\n\nOur burn-in improvement can have a huge effect when the state-action space is immense, which is what usually happens in practice and what this paper is focused on. We will revise our paper to make this limitation clearer. It is also important to note that the burn-in cost is not the only contribution we make; our algorithm is also the first model-free algorithm to achieve minimax regret optimality $\\widetilde{O}(\\sqrt{\\frac{SAT}{(1-\\gamma)^3}})$. Compared to the state-of-the-art result in [14], we reduced the space complexity from $O(S^2A)$ to $O(SA)$ and the computational complexity from $O(S^2AT)$ to $O(T)$.\n\n> It seems like the approach given here borrowed most of the algorithm from the finite horizon case [54] ...\n\n> In addition, the algorithm is complicated and presentation does not make it particularly easy to understand.\n\nWe indeed used the reference-advantage idea from [54] and was clear about this in Section 3. To be precise, there is a difference between how we control the reference update $V^{\\mathrm{R}}$, as our approach uses an additional lower confidence bound estimate to control the reference better. On the other hand, we are unsure how the slow-switching technique could “reduce the infinite horizon problem to a finite horizon one”. Our switching follows an adaptive schedule rather than a fixed one, so it doesn’t seem anything can be reduced to a finite horizon. In addition, our algorithm switches slowly, at a rate of once every $O(\\sqrt{T})$ steps on average, and it would not make sense to consider a reduction to a finite-horizon MDP with horizon $O(\\sqrt{T})$.\n\nLet us also underscore the nontrivial difference between the finite-horizon setting and infinite-horizon discounted setting when it comes to *online* regret minimization. These two settings give rise to different problem structures, which has been long recognized in the existing literature and also been briefly pointed out in our introduction. In the infinite-horizon setting, we optimize regret over one single trajectory, and there is always dependence between any pair of time steps along the trajectory. Such dependence can cause statistical difficulties and give rise to an infinitely expansive structure in the error decomposition. In contrast, the finite-horizon setting resets the trajectory every $H$ steps, so any statistical dependence lasts for at most $H$ steps. Neither of the two settings can be reduced to the other under online regret minimization.\n\nFor this reason, there is little resemblance between our analysis and the one in [54]. If we apply the analysis from [54] naively to the infinite-horizon setting, it will not converge. The two proofs diverge from the very beginning: while [54] manipulate the regret into a clipped pseudo-regret and expand it for further decomposition, we decompose the regret directly and cope with the infinite expansion problem (unique to finite-horizon) with a recursion-style algebraic manipulation (Appendix D). \n\nAs for the presentation of the algorithm, while the technicality might be involved, everything can be summarized into three key ideas: UCB, variance reduction and the adaptive slow-switching technique, which are detailed in Section 3. We will be happy to clarify if you have any specific question about the algorithm.\n\nPlease let us know if you have any further questions and we will be happy to answer. Thanks again!"}, {"review_id": "TO3FRZA90e", "reviewer": "Reviewer_wb6F", "summary": "The paper provides a version of Q-learning algorithm with Bernstein bonuses and control variate that allows or the correct (in terms of the dependence upon state and action space sizes $S$ and $A$) second-order term in the regret bound. This allows for an algorithm with the provably shorter burn-in period (again in terms of $S$ and $A$). This result for discounted MDPs is, to the best of my knowledge, novel.", "questions": "I suggest the authors to add explicitly a paragraph when discussing the techniqus currently used to obtain the second-order term in the regret whch is optimal either in terms of episode length $H$ (resp. $1-\\gamma$ factor), or $S$ and $A$ factors. I would also suggest to add explicit comments on why the current technique in the paper is not suitable to get the second-order term, which is optimal also in terms of the $1-\\gamma$ factor. With this discussion added, I can increase my score by $1$ point.", "limitations": "The paper is theoretical and I do not expect any negative societal impact of the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a valuable contribution to the theory of model-free algorithms for solving MDPs with finite state- action spaces. The suggested idea of incorporating Berstein style bonuses with the UCB-advantage type of control variates is appealing and novel in the discounted MDP setting.", "weaknesses": "Actually, I would also like to ask the authors why not considering submitting to a journal. The proof appendix is massive and it is obviously not possible to check all the technical details properly due to a very limited time for reviewing period.\n\nMinor issues and comments:\n1. The example concerning the Go game (lines 94-98) is spectacular, yet with $|S| = 3^{161}$ the linear dependence on $S$ is clearly as bad as $S^2$. I understand the author's willingness to explain the motivation beyond improving the dependence of the second-order term upon $S$ and $A#, yet I suggest to come up with a slightly less ambitious example;\n2. I would also suggest removing \"outstanding\" in line 108: it is clearly a matter of taste;", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate you taking the time to provide this valuable review! We also thank the reviewer for suggesting submission to a journal. We submitted it to this conference because we believed our paper can be seen by more people here and thus maximize its impact and contribution to the community. In addition, NeurIPS does not seem to discourage submissions with long proofs. But ultimately, this discussion is really beyond the scope of what we should discuss during rebuttal.\n\n> The example concerning the Go game (lines 94-98) is spectacular, yet with $|S| = 3^{161}$ the linear dependence on $S$ is clearly as bad as $S^2$. I understand the author's willingness to explain the motivation beyond improving the dependence of the second-order term upon $S$ and $A$, yet I suggest to come up with a slightly less ambitious example;\n\nThis is a good point. Instead of Go, we can also take tic-tac-toe as an example. The state space for a 5x5 game is $3^{25}$. While it is feasible to store the Q-function in memory, anything on the order of $|\\mathcal{S}|^2$ can be difficult. We will include this example in the final version of our paper when explaining the importance of finding a model-free approach.\n\n> I would also suggest removing \"outstanding\" in line 108: it is clearly a matter of taste;\n\nThank you for the suggestion! We will remove that in the final version as you suggested.\n\n> I suggest the authors to add explicitly a paragraph when discussing the techniques currently used to obtain the second-order term in the regret which is optimal either in terms of episode length $H$ (resp. $1-\\gamma$ factor), or $S$ and $A$ factors. I would also suggest to add explicit comments on why the current technique in the paper is not suitable to get the second-order term, which is optimal also in terms of the $1-\\gamma$ factor. With this discussion added, I can increase my score by 1 point.\n\nWe really appreciate your willingness to raise the score. It is certainly a good question. We weren’t able to discuss much about it in our initial submission due to the page limit, but we can certainly add this explanation in the final version, which will allow for an additional page. \n\nLet us first explain why our algorithm has a burn-in with high $\\frac{1}{1-\\gamma}$ dependence. This comes from our use of the reference-advantage technique. In fact, similarly large factors of $1/(1−\\gamma)$ can also be observed in the burn-in terms of other reference-advantage methods [1,2,3]. Mathematically, this can be attributed to the use of Cauchy-Schwarz in the analysis to balance the factors of $1/(1−\\gamma)$ and $T$. For example, we need to manipulate a term like $T^{1/4}/(1−\\gamma)^{13/4}$ into $\\sqrt{T/(1−\\gamma)^{3}} + 1/(1−\\gamma)^{6}$ so that the $T$-dependent term can have the optimal $1/(1−\\gamma)$ dependence at the expense of a larger burn-in term. Such uses of Cauchy-Schwarz can quickly amplify the power of $1/(1−\\gamma)$ in the burn-in term. Note that terms like $T^{1/4}/(1−\\gamma)^{13/4}$ are a result of the reference-advantage technique (e.g., higher-order variance terms like $(P-\\widehat{P}) (V - V^{\\mathrm{R}})$). As to obtaining a burn-in with optimal dependence on $1/(1−\\gamma)$, it is not clear if any existing algorithm can achieve this yet, not even UCBVI-$\\gamma$ in [4]. It is a good future direction to study how to lower the $1/(1−\\gamma)$ factors in the burn-in term when using reference-advantage algorithms.\n\nAs to how we are able to achieve a linear dependence with $SA$ in the burn-in cost, the main reason is the model-free nature of our algorithm. Since we only estimate the Q-function, which only has $SA$ entries, it is natural to see we can start making meaningful estimations as soon as samples exceed $\\frac{SA}{\\mathrm{poly}(1-\\gamma)}$. The variance reduction and adaptive slow-switching techniques we used are also important, as they ensure the dominant term in the regret is optimal without introducing extra $SA$ factors in the burn-in term. \n\n[1] Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, Y. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762–17776, 2021.\n\n[2] Zhang, Z., Zhou, Y., and Ji, X. Almost optimal model-free reinforcement learning via reference-advantage decomposition.\nAdvances in Neural Information Processing Systems, 33:15198–15207, 2020.\n\n[3] Zhang, Z., Zhou, Y., and Ji, X. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. In International Conference on Machine Learning, pp. 12653–12662. PMLR, 2021.\n\n[4] Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for discounted mdps. Advances in Neural Information Processing Systems, 34:22288–22300, 2021.\n\nIn the very end, we just want to gently point out that getting an $SA$ dependence in the burn-in or second-order term is only one of our contributions. The other, perhaps more important, contribution is that our algorithm is the first model-free algorithm that achieves minimax-optimal regret $\\widetilde{O}(\\sqrt{\\frac{SAT}{(1-\\gamma)^3}})$. Compared to the state-of-the-art result in [4], we reduced the space complexity from $O(S^2A)$ to $O(SA)$ and the computational complexity from $O(S^2AT)$ to $O(T)$.\n\nPlease let us know if you have any further questions and we will be happy to answer. Thanks again!"}, {"review_id": "x5xVnnEKD0", "reviewer": "Reviewer_an4o", "summary": "This paper studies discounted infinite-horizon MDPs. The authors propose an online algorithm that attains optimal (i.e., least) regret with finite-sample performance guarantees. ", "questions": "1. Some numerical experiments in the main body would be great.\n2. Assumptions on the probability distribution for the algorithm to achieve the optimal regret and finite-sample performance guarantees should be made explicitly and crystal clear.", "limitations": "Lack of numerical illustration, but not a deal-break.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Optimal regret & finite-sample performance guarantees", "weaknesses": "Lack of numerical illustration, but not a deal-break.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really thank you for taking the time to provide this valuable review as well as your approval of our paper! Let us provide responses to your questions as follows. \n\nThank you for raising the point about numerical experiments and illustration. Our original goal is to resolve a longstanding theoretical optimality gap, but we agree that how an algorithm performs empirically can also be important. We will try to find an RL environment that can best demonstrate our point and conduct some experiments for the final version of our paper, since the rebuttal period is short. \n\n> Assumptions on the probability distribution for the algorithm to achieve the optimal regret and finite-sample performance guarantees should be made explicitly and crystal clear.\n\nThank you for raising this question. We did not make any assumption on the probability distribution. With a number $\\delta$ decided, if we run the algorithm for $T$ steps (with no assumption), then Equation (9) in Theorem 1 holds with probability at least $1-\\delta$. The transitions in the online trajectory is the only source of randomness in this problem, and no assumption is made about them. \n\nPlease let us know if you have any further questions. Thanks again!"}, {"review_id": "gS8g15wjg1", "reviewer": "Reviewer_Th7P", "summary": "This paper studied infinite discounted tabular Markov decision process (MDP). The authors proposed a model-free algorithm: Q-SlowSwitch-Adv that achieves optimal regret with low burn-in cost, low space complexity and low computational cost. They introduce an innovative technique that changes the execution policy in a slow, adaptive manner, and employ variance reduction to enhance efficiency.", "questions": "Could the authors elaborate on the methodology used to reduce the burn-in cost? Specifically, is this reduction achieved through refined theoretical analysis, novel algorithm design, or a combination of both?", "limitations": "1. The paper's main limitation is the lack of empirical evidence to support the proposed method. Performance comparisons against classic algorithms would have made the theoretical claims more credible.\n\n2. Given the high level of complexity involved in real-world RL problems, the generalizability of the proposed method is not addressed. Therefore, it is unclear how the proposed algorithm will perform in more complex scenarios such as function approximation.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The major novelty of this work lies in the solution to achieve optimal regret using model-free algorithm for discounted tabular MDP.\n2. The property of the low burn-in cost seems interesting and I believe that the low computation cost and low space complexity could be good contributions, enhancing the feasibility of implementing reinforcement learning in real-world scenarios.\n3. The design of a slow, adaptive execution policy-switching technique is novel.\n", "weaknesses": "1. The paper lacks empirical evidence to substantiate the theoretical claims and the efficacy of the proposed algorithm, especially for the 'low' burn-in cost.\n2. The reason why the proposed algorithm can reduce the burn-in cost is not clear, please see the Question part for more details.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate you taking the time to provide this valuable review! Let us provide responses to your comments and questions as follows. \n\n> The paper lacks empirical evidence to substantiate the theoretical claims and the efficacy of the proposed algorithm, especially for the 'low' burn-in cost.\n\nThank you for raising the point about empirical experiments. Our original goal is to resolve a longstanding theoretical optimality gap, but we agree that how an algorithm performs empirically can also be important. We will try to find an RL environment that can best demonstrate our point and conduct some experiments for the final version of our paper, since the rebuttal period is short. \n\n> Could the authors elaborate on the methodology used to reduce the burn-in cost? Specifically, is this reduction achieved through refined theoretical analysis, novel algorithm design, or a combination of both?\n\nThis is a good question. This reduction can be mostly attributed to the algorithm. The model-free nature of our algorithm is a factor of this reduction. Since we only estimate the Q-function, which only has $SA$ entries, it is natural to see we can start making meaningful estimations as soon as samples exceed $\\frac{SA}{\\mathrm{poly}(1-\\gamma)}$. The variance reduction technique and the novel adaptive slow-switching technique we used are also important. These techniques as well as their tight analysis ensure the dominant term in the regret is optimal without introducing extra $SA$ factors in the burn-in term. \n\n> Given the high level of complexity involved in real-world RL problems, the generalizability of the proposed method is not addressed. Therefore, it is unclear how the proposed algorithm will perform in more complex scenarios such as function approximation.\n\nOur result can provide some insights into more complex settings, such as how regret should scale with respect to each problem parameter and the fact that we need to control variance and policy switching carefully for optimality. While the general idea of our adaptive slow-switching technique is applicable to general function approximation, it is not obvious how it should be implemented exactly for that setting (the variance reduction idea we used has existed for a long time but does not have a general function approximation implementation yet). This is beyond the scope of this work and is a good question for future work to answer. \n\nPlease let us know if you have any further questions and we will be happy to answer. Thanks again!"}, {"review_id": "tVcIk9RAjx", "reviewer": "Reviewer_pMQU", "summary": "The paper proposes a nearly optimal model-free algorithm in discounted tabular MDPs which has a shorter burn-in time than previous works and provides valid theoretical guarantees.\n", "questions": "1. The author discusses the impact of large state-action spaces on burn-in time several times. It is reasonable to expect that tabular MDPs with large state-action spaces are generally more challenging to learn, leading to longer burn-in times. However, the paper lacks a lower bound for the minimum burn-in time, although it does match the well-known lower bound on the dominant term (or variance term). It would be valuable for the author to address this gap and provide insights into the possible smallest burn-in time.\n\n2. Lemma 10 presents a rough estimate for $\\sum_{t=1}^T (V_{t-1}\\left(s_t\\right)-V^{\\pi_t}\\left(s_t\\right))$, which is subsequently utilized multiple times in the proof of Lemma 7 (e.g., in (153), (228), (229)). Instead of using this crude bound repeatedly, it seems to be more advantageous to bound the regret without this rough estimate. I mean to maintain the dependence of $\\sum_{t=1}^T (V_{t-1}\\left(s_t\\right)-V^{\\pi_t}\\left(s_t\\right))$ while analyzing intermediate terms in Lemma 4 and then to use Proposition 1 to disentangle this dependence at the end. By using this alternative argument, it may be possible to eliminate the need for the crude bound entirely. Additionally, it is worth investigating if this alternative argument can enhance the dependence of $(1-\\gamma)^{-1}$ on the burn-in time.\n\n3. It is notable that the regret of UCBVI-$\\gamma$ exhibits a more favorable dependence on $(1-\\gamma)^{-1}$ compared to the algorithm proposed in this work. It would greatly enhance the paper if the author could provide a discussion on the reasons behind this superiority. Understanding the factors contributing to better dependence would provide valuable insights into the comparative performance of the two algorithms and contribute to a deeper understanding of their respective strengths and weaknesses.\n\n\n\n\n", "limitations": "Please see the questinos.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well motivated, trying to shorten the burn-in time and obtain a more sample-efficient model-free tabular MDP algorithm.\n\nThe writing is awesome. The detailed comparison with previous algorithms is highly appreciated.  \n\nThe proof seems correct with many previous techniques organically integrated together. I must say the author should be an expert on the related techniques and proof arguments.\n\nTo achieve a tighter burn-in time, it seems vital to update the reference advantage at an appropriate frequency and learn the Q-value of the current policy more accurately. To tackle the issue, the author proposes two new components. The first is the lazy update for the Q-value function which the greedy policy is generated; the other is an adaptive low-switching mechanism to determine what is the time to perform such an update. Both components might inspire future works.", "weaknesses": "If I must point out some weaknesses, I think that the proof contains too many instances where the author didn’t include brackets when utilizing the summation symbol $\\sum$, such as in (46)-(48). \n\nThe frequency of these omissions is quite high, making it difficult to enumerate them here.  I think it is important that all brackets are appropriately included for clarity and correctness.\n\nI have some questions about the results and the theoretical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate you taking the time to provide this valuable review! Let us provide responses to your comments and questions as follows. \n\n> If I must point out some weaknesses, I think that the proof contains too many instances where the author didn’t include brackets when utilizing the summation symbol $\\sum$, such as in (46)-(48). \nThe frequency of these omissions is quite high, making it difficult to enumerate them here. I think it is important that all brackets are appropriately included for clarity and correctness.\n\nThank you for the suggestion! We will correct these in the final version of our paper. \n\n> The author discusses the impact of large state-action spaces on burn-in time several times. It is reasonable to expect that tabular MDPs with large state-action spaces are generally more challenging to learn, leading to longer burn-in times. However, the paper lacks a lower bound for the minimum burn-in time, although it does match the well-known lower bound on the dominant term (or variance term). It would be valuable for the author to address this gap and provide insights into the possible smallest burn-in time.\n\nThis is a good question. We had some discussion about what the lower bound suggests about burn-in cost in our introduction (towards the end of Section 1.3). In short, the current lower bound does not rule out the possibility of having a burn-in term as small as $\\frac{SA}{(1-\\gamma)^2}$. However, it is possible that this lower bound is not tight, so this can be a good open question for future work. We will add more discussion about this gap and the reason for our suboptimal $(1-\\gamma)^{-1}$ dependence in the burn-in when we revise the paper.\n\n> Lemma 10 presents a rough estimate for $\\sum_{t=1}^T (V_{t-1}(s_{t}) - V^{\\pi_t}(s_t))$, which is subsequently utilized multiple times in the proof of Lemma 7 (e.g., in (153), (228), (229)). Instead of using this crude bound repeatedly, it seems to be more advantageous to bound the regret without this rough estimate. I mean to maintain the dependence of $\\sum_{t=1}^T (V_{t-1}(s_{t}) - V^{\\pi_t}(s_t))$ while analyzing intermediate terms in Lemma 4 and then to use Proposition 1 to disentangle this dependence at the end. By using this alternative argument, it may be possible to eliminate the need for the crude bound entirely. Additionally, it is worth investigating if this alternative argument can enhance the dependence of $(1-\\gamma)^{-1}$ on the burn-in time.\n\nThis is a very good observation. To be precise, (153) is the proof of Lemma 10 and not an invocation of the lemma, so we can focus on the other instances. We use Lemma 10 at these places because we want to replace $\\sum_{t=1}^T (V_{t-1}(s_{t}) - V^{\\pi_t}(s_t))$ with a simple upper bound without having to carry it around in the following analysis. Even if we carried $\\sum_{t=1}^T (V_{t-1}(s_{t}) - V^{\\pi_t}(s_t))$ all the way to the end without invoking Lemma 10 as you suggested, the burn-in cost would still have the current $(1-\\gamma)^{-1}$ dependence. The invocations of Lemma 10 are only for clarity.\n\nTake (228) for a concrete example. (228) is an intermediate step to obtain the inequality in (216). Despite the use of Lemma 10, the $\\log T$ term in (216) is only on the order of $(1-\\gamma)^{-3}$. This is dominated by the $\\log T$ term in (217), which is on the order of $(1-\\gamma)^{-13/4}$, and this term in (217) is not a result of Lemma 10. Note that both (216) and (217) are part of $\\mathcal{R}_1$, so using Lemma 10 or not does not affect the burn-in component of $\\mathcal{R}_1$ or the final burn-in term. \n\n> It is notable that the regret of UCBVI-$\\gamma$ exhibits a more favorable dependence on $(1-\\gamma)^{-1}$ compared to the algorithm proposed in this work. It would greatly enhance the paper if the author could provide a discussion on the reasons behind this superiority. Understanding the factors contributing to better dependence would provide valuable insights into the comparative performance of the two algorithms and contribute to a deeper understanding of their respective strengths and weaknesses.\n\nThis is also a good question. The reason why UCBVI-$\\gamma$ has a lower $(1-\\gamma)^{-1}$ dependence in the burn-in than ours is not so much what they did in their algorithm as what we did in ours that gives rise to a high $(1-\\gamma)^{-1}$ dependence. To be specific, the high $(1-\\gamma)^{-1}$ dependence comes from our use of the reference-advantage technique. In fact, similarly large factors of $1/(1−\\gamma)$ can also be observed in the burn-in terms of other reference-advantage methods [1,2,3]. Mathematically, this can be attributed to the use of Cauchy-Schwarz in the analysis to balance the factors of $1/(1−\\gamma)$ and $T$. For example, we need to manipulate a term like $T^{1/4}/(1−\\gamma)^{13/4}$ into $\\sqrt{T/(1−\\gamma)^{3}} + 1/(1−\\gamma)^{6}$ so that the $T$-dependent term can have the optimal $1/(1−\\gamma)$ dependence at the expense of a larger burn-in term. Such uses of Cauchy-Schwarz can quickly amplify the power of $1/(1−\\gamma)$ in the burn-in term. Note that terms like $T^{1/4}/(1−\\gamma)^{13/4}$ are a result of the reference-advantage technique (e.g., higher-order variance terms like $(P-\\widehat{P}) (V - V^{\\mathrm{R}})$). \n\n[1] Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, Y. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762–17776, 2021.\n\n[2] Zhang, Z., Zhou, Y., and Ji, X. Almost optimal model-free reinforcement learning via reference-advantage decomposition.\nAdvances in Neural Information Processing Systems, 33:15198–15207, 2020.\n\n[3] Zhang, Z., Zhou, Y., and Ji, X. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. In International Conference on Machine Learning, pp. 12653–12662. PMLR, 2021.\n\nPlease let us know if you have any further questions and we will be happy to answer. Thanks again!"}]

Author rebuttal:

Meta-review: The paper studies regret minimization in discounted infinite-horizon Markov Decision Processes. 
The paper presents a minimax optimal algorithm for this setting that improves previous results from two different aspects:
1. Improved space complexity of $O(SA)$ and computational complexity of $O(T)$.
2. Improved additive constant in the regret bound, so that the regret would be dominated by the asymptotic rate from an earlier stage in the interaction ('short burn-in time').

After a long discussion with the authors about the regret measures used in the paper and their relation to previously used measures, all reviewers have agreed that the above contributions are sufficient for the paper to be accepted. 

The authors are encouraged to modify the paper to include the relation between the different regret measures (as was promised during the discussions).
Decision: Accept (poster)