Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning
Authors: Gen Li
Laixi Shi
Yuxin Chen
Yuantao Gu
Yuejie Chi
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: reinforcement learning
memory efficiency
model-free RL
episodic MDPs
variance reduction
exploration

Abstract: Achieving sample efficiency in online episodic reinforcement learning (RL) requires optimally balancing  exploration and exploitation. When it comes to a finite-horizon episodic Markov decision process with $S$ states, $A$ actions and horizon length $H$, substantial progress has been achieved towards characterizing the minimax-optimal regret, which scales on the order of $\sqrt{H^2SAT}$ (modulo log factors) with $T$ the total number of samples. While several competing solution paradigms have been proposed to minimize regret, they are either memory-inefficient, or fall short of optimality unless the sample size exceeds an enormous threshold (e.g., $S^6A^4 \,\mathrm{poly}(H)$ for existing model-free methods).

To overcome such a large sample size barrier to efficient RL, we design a novel model-free algorithm, with space complexity $O(SAH)$, that achieves near-optimal regret as soon as the sample size exceeds the order of $SA\,\mathrm{poly}(H)$. In terms of this sample size requirement (also referred to the initial burn-in cost), our method improves --- by at least a factor of $S^5A^3$ --- upon any prior memory-efficient algorithm that is asymptotically regret-optimal. Leveraging the recently introduced variance reduction strategy (also called {\em reference-advantage decomposition}), the proposed algorithm employs an {\em early-settled}  reference update rule, with the aid of two Q-learning sequences with upper and lower confidence bounds. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings that involve intricate exploration-exploitation trade-offs.

Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning
Gen Li' Princeton
Laixi Shit CMU
Yuxin Chen
Yuantao Gu Tsinghua
Yuejie Chit CMU
Princeton
Abstract
Achieving sample efficiency in online episodic reinforcement learning (RL) re- quires optimally balancing exploration and exploitation. When it comes a finite-horizon episodic Markov decision process with S states, A actions and horizon length H, substantial progress has been achieved towards characterizing the minimax-optimal regret, which scales on the order of VH2SAT (modulo log factors) with 7 the total number of samples. While several competing solu- tion paradigms have been proposed to minimize regret, they are either memory- inefficient, or fall short of optimality unless the sample size exceeds an enormous threshold (e.g., S A poly(H) for existing model-free methods).
To overcome such large sample size barrier to efficient RL, we design a novel model-free algorithm, with space complexity O(SAH), that achieves near-optimal regret as soon as the sample size exceeds the order of SA poly (H). terms this sample size requirement (also referred to the initial burn-in cost), our method improves - by least factor of 5 A upon any prior memory-e algorithm that is asymptotically regret-optimal. Leveraging the recently introduced variance reduction strategy (also called inference-advantenn decomposition), the proposed algorithm employs an early-seuled reference update rule, with the aid two Q-learning sequences with upper and lower confidence bounds. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings that involve intricate ppploration-epllittaee trade- offs.
Introduction
Contemporary reinforcement learning (RL) has to deal with unknown environments with unprece- dentedly large dimensionality. How make the best use of samples in the face of high-dimensional state/action space lies at the core modern RL practice. An ideal RL algorithm would learn to act favorably even when the number of available data samples scales sub-linearly in the ambient dimension of the model, i.e., the number of parameters needed to describe the transition dynamies of the environment. The challenge is further compounded when this task needs to be accomplished with limited memory.
Simultaneously achieving the desired sample and memory efficiency is particularly challenging when comes to online episodic RL scenarios. In contrast to the simulator setting that permits sampling of any state-action pair, agent in online episodic RL is only allowed draw sample trajectories by executing policy the unknown Markov decision process (MDP), where the initial states are pre-assigned and might even be chosen by an adversary. Careful deliberation needs to be undertaken when deciding what policies to allow for effective interaction with the unknown environment,
Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544, USA. Department Electrical Computer Engineering, Carnegie Mellon University, Pittshurgh, PA 15213,
USA.
Department of Electronic Engineering, Tsinghua University, Beijing 100084, China.
35th Conference Neural Information Processing Systems (NeurIPS 2021).

---

how to optimally balance exploitation and exploration, and how to process and store the collected information intelligently without causing redundancy.
1.1 Regret-optimal model-free RL? A sample size barrier
In order to evaluate and compare the effectiveness of RL algorithms in high dimension, recent body of works sought to develop a finite-sample theoretical framework to analyze the algorithms of interest, with the aim of delineating the dependency of algorithm performance on all salient problem parameters in a con-asymptotic fashion (Dann et al., 2017: Kakade, 2003). Such finite-sample guarantees are brought to bear towards understanding and tackling the challenges in the sample- starved regime commonly encountered in practice. To facilitate discussion, let us take a moment to summarize the state-of-the-art theory for episodic finite-horizon MDPs with non-stationary transition kernels, focusing on minimizing cumulative regret difference between the learned policy and the true optimal policy samples. Here and throughout, we denote by S, A, and H the size of the state space, the size of the action space, and the horizon length of the MDP, respectively, and let T represent the sample size. In addition, the immediate reward gained at each time step is assumed to lie between and 1.
a metric that quantifies the performance
with the fewest number of
Fundamental regret lower bound. Following the arguments in Jaksch et al. (2010); Auer et al. (2002), the recent works Jin et al. (2018); Domingues et al. (2021) developed fundamental lower bound on the expected total regret for this setting. Specifically, this lower bound claims that: no matter what algorithm to use, one can find an MDP such that the accumulated regret incurred by the algorithm necessarily exceeds the order of
(lower bound)
VI²SAT,
as long as T H2S This sublinear regret lower bound in turn imposes sampling limit if one wants to achieve E average regret.
Model-based RL. Moving beyond the lower bound, let us examine the effectiveness of model-based RL an approach that can be decoupled into a model estimation stage (i.e., estimating the transition kernel using available data) and subsequent stage of planning using the learned model (Jaksch et al., 2010; Azar et al., 2017; Efroni et al., 2019; Agrawal and Jia. 2017; Pacchiano et al., 2020). In order ensure sufficient degree of exploration, Zhang et al. (2020b) came up with an algorithm called MVP that blends masel- learning and the optimism principle, which achieves a regret bound Ö(VH²SAT) that nearly attains the lower bound (1) as T tends to infinity. Caution needs to be exercised, however, that existing theory does not guarantee the near optimality of this algorithm unless the sample size T surpasses
T2 AH*
a threshold that is significantly larger than the dimension of the underlying model. This threshold can also be understood the initial burn-in cost of the algorithm, namely, sampling burden needed for the algorithm to exhibit the desired performance. In addition, model-based algorithms typically require storing the estimated probability transition kernel, resulting in a space complexity that could be as high as O AH) (Azar et al., 2017: Zhang et al., 2020b).
Model-free RL. Another competing solution paradigm is the model-free approach, which circumvents the model estimation stage and attempts to learn the optimal values directly (Strehl et al., 2006; Jin al., 2018; Bai et al., 2019; Yang et al., 2021). In comparison to the model-based counterpart, the model-free approach holds the promise of low space complexity, as it eliminates the need of storing a full description of the model. In fact, in a number of previous works (e.g., Strehl et al. (2006); Jin al. (2018)), an algorithm is declared be model-free only if its space complexity is oS AH) regardless of the sample size T.
Memory-efficient model-free methods. Jin et al. (2018) proposed the first memory model- free algorithm - which an optimistic variant of classical Q-learning - that achieves a regret bound proportional to VT with a space complexity O(S AH). Compared to the lower bound (1), however, the regret bound in Jin et al. (2018) is off by a factor of vH and hence suboptimal for
1 'Given that a trivial upper bound on the regret T, one needs to impose a lower bound 2 HHSA order for (1) to be meaningful.
the standard notation (n) (g)(n) to indicate that (())//(n)) is bounded above by constant as n grows. The notation Ō(:) resembles O()) except that it hides any logarithmic scaling. The uotation f(n) o(g(r)) means that limn- (()) = 0.
'Here and throughout,
2

---

Range of sample sizes that attain optimal regret
Space complexity
Algorithm
Regret
UCB-VI
SH'SAT S
[S 2o) [S AH
SAAH
(Azar et al., 2017)
MVP
VH'SAT + HASA
SP AH
(Zhang et al., 2020b)
UCB-Q-Hoeffding
VH'SAT
SAH
(Jin al., 2018)
UCB-Q-Bernstein
VH'SAT A3
never
SAH
(Jin et al., 2018)
Beerstnn
VIPSAT + A3
never
SAH
(Bai et al., 2019)
UCB-Q-Advantage (Zhang et al., 2020c)
VH'SAT H
A ,0)
SAH
UCB-M-Q
VH3SAT HASA
[SAH 00)
S
(Menard et al., 2021)
R-EartySettled-Advaaaggg
VHSSAT + SA
[SAM 20)
SAH
(this work)
Lower bound
VH'SAT
n/a
n/a
(Domingues al., 2021)
Table 1: Comparisons between prior art and results for non-stationary episodic MDPs when T H The table includes the order of the regret bound, the range of sample sizes that achieve the optimal regret A(T) and the memory complexity, with all logarithmic factors omitted for simplicity of presentation. The red text highlights the suboptimal part of the respective algorithms.
problems with long horizon. This drawback has recently been overcome Zhang et al. (2020c) by leveraging the idea of variance reduction (or the so-called reference--dvaanne decomposition" for large enough T' While the resulting regret matches the information-theorete limit asymptotically, its optimality in the non-asymptotic regime is not guaranteed unless the sample size T exceeds (see Zhang et al. (2020c, Lemma 7))
T S6 A H
requirement that is even far stringent than the burn-in cost imposed by Azar et al. (2017).
A neemory-neeffcien "model-free" variant. The recent work Menard al. (2021) put forward novel sample-efficient variant Q-learning called UCB-M-Q. which relies on a carefully chosen momentum term for bias reduction. This algorithm is guaranteed to yield near-optimal regret
Ō O(HH'SAT) as soon as the sample size exceeds T > SApoly (H), which is remarkable improvement vis-à-vis previous regret-optimal methods (Azar al., 2017: Zhang et al., 2020c). Nevertheless, akin to the model-based approach, it comes at a price in terms of the space and computation complexities, the computation required OST)), both of which are larger by a factor of S than other model-free algorithms like Zhang et al. (2020c). In view of this memory inefficiency, UCB-M-Q falls short of fulfilling the definition of model-free algorithms in Strehl al. (2006); Jin et al. (2018). See Menard et al. (2021, Section 3.3) for more detailed discussions.
the space required to store all bias-value function is O(S
and
more complete summary of prior results can be found in Table 1.
1.2 A glimpse of our contributions
In brief, while it is encouraging to see that both model-based and model-free approaches allow for near-minimal regret as T tends to infinity, they are either memoor-inefficient, or require the sample size to exceed threshold substantially larger than the model dimensionality. In fact, no prior algorithms have been shown to be simultaneously regret-optimal and memory-effiiiet unless
T > 8 A Aopooly( (H))

---

which constitutes stringent sample size barrier constraining their utility in the sample-starved and memory-limited regime. The presence of this sample complexity barrier motivates one to pose natural question:
Is it possible to design an algoritim that accommodates significantly broader sample size range without compromising regret optimality and memory efficiency?
In this paper, answer this question affirmatively. by designing model-fres algorithm, dubbed as Q-EarlySettled-AAvve Advantage, that enjoys the following performance guarantee.
Theorem 1 (informal). The proposed Q- Q-EarlySetteed complexity (SSH)), achieves near near-optimal regrer (( as soon as the sample size exceeds T Σ S.A (H)
algorithm, which has space
The proof of this theorem can be found in the full version Li et al. (2021c). As can be seen from Table 1, the space complexity of the proposed algorithm is OSSHH) which is far more memory- efficient than both the model-based approach in Azar et al. (2017) and the UCB-M-Q algorithm in Menard et al. (2021) (both of these prior algorithms require S AH units of space). In addition, the sample size requirement? T 2 SA poly (H) of our algorithm improves - by factor of least S A upon that of any prior algorithm that is simultaneously regret-optimal and memory-efficient. In fact, this requirement is nearly sharp in terms of the dependency both S and A, and was previously achieved only by the UCB-M-Q algorithm at a price of a much higher storage burden.
Let us also briefly highlight the key ideas of our algorithm. As an optimistic variant of variance- reduced Q-learning, Q- Q-EarlySettled- -EarlySetleed-Avvattagee leverages the recently-introduece advantage decompositions for variance reduction (Zhang et al., 2020c). As a distinguishing feature from prior algorithms, we employ an early-stopped reference update rule, with the assistance of two Q-learning sequences that incorporate upper and lower confidence bounds, respectively. The design of our early-stopped variance reduction scheme, as well as its analysis framework, might be of independent interest to other settings that involve managing intricate exploration-explootaiio exploitation trade-offs.
reference-
1.3 Related works
We now take a moment to discuss a small sample of other related works; a more extensive discussion is deferred to the supplemental material.
When it comes to online episodic RL (so that a simulator is unavailable), regret analysis is the prevailing analysis paradigm employed to capture the trade-off between exploration and exploitation. A common theme is to augment the original model-free update rule (e.g., the Q-learning update rule) by an exploration bonus, which typically takes the form of, say, certain upper confidence bounds (UCBs) motivated by the bandit literature (Lai and Robbins, 1985; Auer and Ortner, 2010). In addition to the ones in Table 1 for episodic finite-horizon settings, sample-efficient model-free algorithms have been investigated for -ornite-horioonn MDPs as well (Dong et al., 2019; Zhang et al., 2020b,d; Jafarnia-Jahromi et al., 2020; Liu and Su, 2020; Yang et al., 2021).
The seminal idea of variance reduction was originally proposed to accelerate finite-sum stochastic optimization, e.g., Johnson and Zhang (2013): Gower et al. (2020); Nguyen et al. (2017). Thereafter, the variance reduction strategy has been imported to RL, which assists in improving the sample efficiency of RL algorithms in multiple contexts, including but not limited to policy evaluation (Du et al., 2017; Wai et al., 2019; Xu et al., 2019; Khamaru et al., 2020), RL with a generative model (Sidford et al., 201 8a,b; Wainwright, 2019b), asynchronous Q-learning (Li et al., 2020b), and offline RL (Yin et al., 2021).
2 Problem formulation
In this section, we formally describe the problem setting. Here and throughout, we denote by A(S)
the probability simplex over set S, and [M] = .I..... ,M} for any integer M 0.
represent a finite-horizon MDP, where S : (1,... S} is the state space of size S. A = 11,... A} is the action space of size A, H denotes the horizon length, and P, : S x A + (SS) (resp. ry :S AxA- + [0, 1)) represents the probability transition kernel (resp. reward function) at the h-th time step. 1 < h < H, respectively.
Basics of finite-horizon MDPs. Let M = (S, A, H, (PA 1= frr 11

---

More specifically, (- s. E A(S) stands for the transition probability vector from state at time step when action is taken, while (s, a) indicates the immediate reward received at time step for a state-action pair (s, a) (which is assumed to be deterministic and fall within the range [0, 1].. The MDP is said to be non-stationary when the PA 8 are not identical across 1 S h S H. A policy of an agent is represented by я {T h=1 with Ta S - A the action selection rule at time step h, so that (s)(s) (s) specifies which action to execute in state time step h. Throughout this paper, concentrate on deterministic policies.
Value functions, Q-functions, and Bellman equations. The value function VA (s) of a (determinis- tic) policy at step h is defined as the expected cumulative rewards received between time steps h and H when executing this policy from an initial state at time step h, namely,
V (s)
Σ Ere Te (st))
sh =
Pa
12h
where the expectation is taken over the randomness of the MDP trajectory {s; S H}.
The action-value function (a.k.a. the Q-function) Q% a) of a policy π at step h can be defined analogously except that the action at step h is fixed to be that is,
H
aT(s,a) = an(s
E
Σ
(e mo(se)) sn 5,
(3)
Sh PA (ss,))
Se+1 (s 1
In addition, we define (s) = ( 0 for any policy т and any state-action pair (s, a) S x A. By virtue of basic properties in dynamic programming (Bertsekas, 2017), the value function and the Q-function satisfy the following Bellman equation:
Qī(s, a) = rs(ss)) +
E
(V (s')..
(4)
A policy x* {- is said to be an optimal policy if it maximizes the value function simulta- neously for all states among all policies. The resulting optimal value function V =V1 1/ and optimal Q-functions Q* (Q satisfy
(s) = VIT (s) max Vi((s)
and (7 = (s, max (T,saa) a)
(5)
for any (s, a, h) E S x A [M]. is well known that the optimal policy always exists (Puterman, 2014), and satisfies the Bellman optimality equation:
V(s,a,h) E Ax
())
E (tPPa()
[V)++
(6)
Online episodic RL. This paper investigates the online episodic RL setting, where the agent is allowed to execute the MDP sequentially total number of K episodes each length H. This amounts to collecting
T K. samples
in total. More specifically, in each episode t: = 1,..., K, the agent is assigned an arbitrary initial state of (possibly by an adversary), and selects policy -² { >== learned based on the information
collected up to the (k- 1)-th episode. The k-th episode is then executed following the policy x and the dynamic of the MDP M, leading to a length- -I sample trajectory.
Goal: regret minimization. In order to evaluate the quality of the learned policies (n*)sss frequently used performance metric is the cumulative regret defined as follows:
K
Regret (T)
= Σ (VI( - (of)))
R=1
In words, the regret reflects the sub-optimality gaps between the values of the optimal policy and those of the learned policies aggregated over K episodes. A natural objective is thus to design sample-optimal algorithm, namely, algorithm whose resulting regret scales optimally in the sample size T. Accomplishing this goal requires carefully managing the trade-off between exploration and exploitation, which is particularly challenging in the sample-limite regime.
5

---

Notation. Before presenting our main results, we take moment to introduce some convenient notation to be used throughout the remainder this paper. For any vector x' E IRSA that constitutes certain quantities for all state-action pairs, we shall often use z(8, a) to denote the entry associated with the state-action pair (s, a), as long as it is clear from the context. We shall also let
Ph.s,a (t 8,a) R
abbreviate the transition probability vector given the (s, () pair at time step h. Additionally, we denote by e, the i-th standard basis vector, with the only non-zero element being in the i-th entry and equal to 1.
3
Algorithm and theoretical guarantees
In this section, we present the proposed algorithm called Q-EarlySetlled-AAwwala Advantaaee as well as the accompanying theory confirming its sample and memory efficiency.
3.1 Review: Q-learning with UCB exploration and reference advantage
This subsection briefly reviews the Q-learning algorithm with UCB exploration proposed in Jin et al. (2018), as well as variant that further exploits the idea of variance reduction (Zhang et al., 2020c). These two model-free algorithms inspire the algorithm design in the current paper.
Q-learning with UCB exploration (UCB-Q or UCB-Q-Hoeffding). Recall that the classical Q- learning algorithm has been proposed as a stochastic approximation scheme (Robbins and Monro, 1951) to solve the Bellman optimality equation (6), which consists of the following update rule (Watkins, 1989; Watkins and Dayan, 1992):
Qn(s, + (1- (s,(s, m n<r((s,0)+
Pr.saVnnt }
(9)
stochastic
Phia.a 1h
Here, Qn (resp. Vi,) indicates the running estimate of Q (resp. VR), vi is the (possibly iteration- varying) learning rate or stepsize, and Pr.s,aVt43 is stochastic estimate of Phas.Vnn (cf. (8)). For instance, one has available sample (s, a, s') transitioning from state at step h to s' step h + 1 under action a, then a stochastic estimate of PR.s.a Vh+1 can be taken as Vi+1(s'), which is unbiased in the sense that
[[Vi+1(5']] = Ph.s,a Vn+1-
To further encourage exploration, the algorithm proposed in Jin et al. (2018) which shall be abbreviated as UCB-Q or NUCB-Q-Heffdiigg hereafter augments the Q-learning update rule (9) in each episode via an additional exploration bonus:
UCB Qu (s, a) (1- ( (s, + (r) + Ph. A1+1 + bn).
(10)
The bonus term by is chosen to be certain upper confidence bound for (Ph...a Ph, V an exploration-effccien scheme that originated from the bandit literature (Lai and Robbins, 1985; Lat- timore and Szepesvári, 2020). The algorithm then proceeds to the next episode by seecuting/samplinn the MDP using a greedy policy w.r.t. the updated Q-estimate. These steps are repeated until the algorithm is terminated.
Q-learning with UCB exploration and reference advantage (UCB-Q LUCB-Q-Advanter Advaantag)) The regret bounds derived for UCB-Q (Jin et al., 2018), however, fall short of being optimal, as they are least a factor of /H away from the fundamental lower bound. In order further shave this /H factor, one strategy is to leverage the idea of variance reduction to accelerate convergence (Johnson and Zhang, 2013; Sidford et al., 2018b; Wainwright, 2019b; Li et al., 2020b). An instantiation of this idea for the regret setting is a variant of UCB-Q based on reference-and reference-advantagee decomposition, which was put forward in Zhang et al. (2020c) and shall be abbreviated as UCB-Q-Advantage throughout this paper.
To describe the key ideas of UCB UCB-Q-AAvantage, imagine that we are able to maintain a collection of reference values / (V/ ) k= which form reasonable estimates of V (V and become increasingly more accurate as the algorithm progresses. At each time step h, the algorithm adopts the following update rule
Q a) < (1 (1-n))a (1-n) + n of (r((s, a) + +Ph.s.a (V - V [A h+ (s. + b (11)
stochustic estimate of Pr (Vr- 1 v

---

Two ingredients of this update rule are worth noting.
Akin to the UCB-Q case, we can take Ph. (Vn+1 - (++1) to be the stochastic estimate (s'+ VR, 1 if we observe a sample transition (s, s') at time step h. If Vh+1 is fairly close to the reference Vi then this stochastic term can be less volatile than the stochastic term Ph. Va+1 in (10).
Additionally, the term Pr VR h++1 indicates an estimate of the one-step look-ahead value Pa PAV h+1
which shall be computed using a batch of samples. The variability of PA V/R h+11 can be well-controlled through the use of batch data, at the price of an increased sample size.
Accordingly, the exploration bonus term b is taken to be an upper confidence bound for the above- mentioned two terms combined. Given that the uncertainty of (11) largely stems from these two terms (which can both be much smaller than the variability in (10)), the incorporation of the reference term helps accelerate convergence.
3.2 The proposed algorithm: Q-EartySSetlee--Acaaatgg
As alluded to previously, however, the sample size required for mal regret needs to exceed large polynomial S A in the size of the state/action space. To overcome this sample complexity barrier, we come up with an improved variant called Q-EarlySettled- Advantage.
to achieve opti-
Motivation: early settlement of reference value. An important insight obtained from previous algorithm designs is that: in order to achieve low regret, is desirable to maintain an estimate of Q-function that (i) provides an optimistic view (namely, an over-estimate) of the truth Q", and (ii) mitigates the bias Q 2 Q* much possible. With two additional optimistic Q-estimates in hand- QucB based on UCB-Q, and reference Q - it is natural to combine them as follows to further reduce the bias without violating the optimism principle:
(*h, an) + min { (sA, an), Qu on), Qu(sn, }
(12)
This is precisely what conducted in UCB-Q JCB-Q-Advartn Advantagee However, while the estimate Q obtained with the aid of reference-ate ad vantagge decomposition provides great promise, fully realizing its potential in the cample-limited regime relies on the ability quickly settle on desirable "reference" during the initial stage of the algorithm. This leads us to a dilemma that requires careful thinking. On the one hand, the reference value RR needs to be updated in timely manner in order to better control the stochastic estimate of Pr. (V++1 VR 1). On the other hand, updating VR too frequently incurs an overly large sample size burden, as new samples need be accumulated whenever V is updated.
Built upon the above insights, it is advisable to prevent frequent updating of the reference value y In fact, it would be desirable to stop updating the reference value once point of sufficient quality denoted by / Rinal - has been obtained. Locking that (a) fewer samples will be wasted on estimating a drifting target Pr, V/R and (b) all ensuing samples can then be dedicated estimating the key quantity of interest Pa R.final
reasonable reference value early means
h+1
Remark I. Zhang et al. (2020c), the algorithm UCB-Q-Advantagg requires collecting Ö(S (H)) samples for each state before settling on the reference value, which inevitably contributes to the large burn-in cost.
The proposed that allows for early settlement of the reference value. A few key ingredients are as follows.
SeterySSeetlee-Adaatteeee algorithm. We now propose new model-free algorithm
An auxiliary sequence based on LCB. In addition to the two optimistic Q-estimates Q and QUC described previously, we intend to maintain another pessimistic estimate Q/. < Q using the subroutine update-Icb-q. based on lower confidence bounds (LCBs). We will also maintain the corresponding value function V/LCB which lower bounds VA+-
Termination rules for reference updates. With VLCB V% in place, the updates of the references (lines 15-18 of Algorithm 1) are designed to terminate when
(sn) I v/l LCC (sn) + (sA) + 1.
(13)
7

---

Algorithm 1: C-EaaryyStllee--Avanaag
Parameters: some universal constant c > 0 and probability failure E (0, 1); 2 Initialize Qu a), Q (s, (R a) + H: Vi((s), (T) + H; Q (s, a) t- 0:
VLCB(() < 0; (8, a) < 0; 1hh (s,0), a), o (s.0), 1. (s, (s, (s, a) + O: and (s) = True for all (s, a, fi) E S x [ for Episode
do
Set initial state 81 <- sf. for Step h to H do
Take action an (s.) arg max, (sh a), and draw 8/41 Pa(- (1(11.9 sh, an).
// sampling
(sh; an) <- N₁ (Sh, (p) + n: (sh. on). // update the counter
Th + H+1 // update the learning rate H+"
QUCB (sh, an) (sh,
update-ucb-q0>.
UCB-Q; Algorithm 2
10
Q (sh. ah) update-1cb-qQ1
LCB-Q; Algorithm 2
o (sh; ax) update-ucb-g--dvaattee () // estimate Qh Algorithm
/ update Q-estimates using all estimates in hand, and update value estimates
(sh,, an) + min ( an), Qu an), Qn a.))
12
13
Vil(s)) + max, Qn(sn, a).
h V. t max max, Q (8), a), V2 (sx))
14
/- update reference values
(sh) V)LB(ss)) > then
15
(sn) t Vi((s))
16
17
else if uret (sw) (x))= = True then VI (sn) f (sn),,
18
Uyer(sh) False.
Note that V keeps tracking the value of V₁, before it stops being updated. In effect, when the additional condition lines 15 is violated and thus (13) is satisfied, we claim that is unnecessary update the reference VR afterwards, since it is of sufficient quality (being close enough to the optimal value Vi+) and further drifting the reference does not appear beneficial. As we will make it rigorous shortly, this reference update rule is sufficient to ensure that IV, V S throughout the execution of the algorithm, which in turn suggests that the standard deviation of Ph. (Vh+1 VR 1) might be ((H) times smaller than that of Ph,s,aVhe (i.e., the stochastic term used in (9) of UCB-Q). This is key observation that helps shave the addition factor H in the regret bound UCB-Q.
Update rules for QUCB and QR The two optimistic Q-estimates QUCB and QR are updated using the subroutine apdate-ucb-g. (following the standard Q-learning with Hoeffding bonus (Jin et al., 2018)) and update- pordate-ub--at aaaavaaaaageeee.e respectively. Note that Q continues to be updated even after VR is no longer updated.
Q-learning with reference-advantage decomposition. The rest of this subsection is devoted to ex- plaining the subroutine reference-advantieeg decomposition similar to Zhang et al. (2020c). To facilitate the implementation, let us introduce the parameters associated with a reference value yR, which include six different components, i.e.,
which produces a Q-estimate QR based on the
[Ant (s, (s, pad (s, a), (s, 6f (s, (s.
(14)
for all (s, a, h) E S x [H]. Here uff (s, a) and of (s, a) estimate the running mean and 2nd pady(s, (s, and o ( (s. estimate the running (weighted) - [s) a): BR (s, a) aggregates the empirical
moment of the reference [R.VR [s, a); p
mean and 2nd moment of the advantage standard deviations of the reference and the advantage combined; and last but not least, 8f (s. a) is the temporal difference between (8, a) and its previous value.

---

Algorithm 2: Auxiliary functions
Function (etaate-ucb-(->
Qh QCBB (sh; ax) - (1-7n) ( an) (rn((n, (h
Ha 24z
Function update-lcb-qO::
(sh, ah) (1-7,)QH
2 C (sh, an) + nh (r(()) V -cb
13 242
Function ppddate-uc----ddvaatageee
/+ update the moment statistics of V,P
[ugh ohh ju " ( un) aydaate-momntte (); /+ update the accumulative bonus and bonus difference
[68, (sh, + update-bonust
oR t BB
+BR an) + (1 - 7h) (ilspaa + Cb 974
log EAT
/* update the Q-estimate based on referemce-advantaan decomposition Q an) +
*/
(1 7n 1Q an) + nm (rn((s) and + Vh+1($h+11) V (sn+1) + 14 (sh. an) + bR);
10
Function update-momente (): 2 (sh, an) + (1 1) (sh, an)
1.2 LVR h+i (sh+ // mean of reference
(sh, an) < (1 1o (sh, an) (VR (+t ( 2 moment of the reference
13
u and t (1 - (nt) (sh, an) + (Vi+1 (sh-)))) weighted
average the advantage
(sh, + (1 ( an) Th - VR h+i (sh+1))) weighted
2nd moment of the advantage
15
Function Sedate-bonus(C ():
Beext(sn an)
cb Vlog
log SAZ
(V of an) - (wnf an))² + VH V (sd
an) (aad (sh.on))² an))²)
17
(8 an)
Brexe (s), (nh)
BB an);
(sh, an)
Breat (sn. an).
As alluded to previously, the Q-function estimation follows the strategy (11) high level. Upon ob- serving sample transition (sh, ans 8h+1), we compute the following estimates update Q as).
The term Ph.s, (Vn+1 V/R ( is be Vh+1(sn-1) Vi (98+1), which is an unbiased stochastic estimate Ph.e,a (V4+1 VR 1)
The term [PAVR ( a) is estimated via 1h ref.R (cf. line 11). Given that this is estimated using all previous samples, we expect the variability of this term be well-controleed as the sample size increases (especially after /R is locked).
The exploration bonus ( a) is updated using (s,, an) and (sh, 4A) (cf. lines 7-8 of Algorithm 2), which is confidence bound accounting for both the reference and the advantage. Let also explain line 8 of Algorithm 2 bit. If we augment the notation by letting 6 6R.x+1 (s, a) and B BR (s, a) denote respectively b (s, a) and (s, a) after (s, a) is visited for the n-th time, then this line is designed to ensure that
R.n+1 The b
a) + B BR ( (s, a) RO Ri, (s,
With the above updates implemented properly, Q provides the advantage-basee update of the -fuucctoon time step h. according to the update rule (11).

---

3.3 Main results
Encouragingly, the proposed Q-EarilySetled-Adaaatag algorithm manages to achieve near- near-optimal regret even in the sample-limin limited and memory- regime, as formalized by the following theorem; the proof can be found in the full version Li et al. (2021c).
Theorem 2. Consider any 5 E (0, 1). and suppose that c > O is chosen to be a sufficiently large universal constant, Then there exists some absolute constant Co 0 such that Algorithm I achieves
Regret(T) S Co (v HoSATlog
SAT
SAT
+ 11 SA SAlog"
(15)
8
with probability at least 1
Theorem 2
delivers non-asymptotic characterization of the performance of our algorithm Q- SeiiySettlee-Addvatennn Several uppealing features of the algorithm are noteworthy.
Regret optimality. Our regret bound (15) simplifies
(T) s Ō(VH'SAT)
(16)
as long as the sample size T exceeds
T SA)o
(17)
This sublinear regret bound (16) is essentially optimal, as it coincides with the existing lower bound (1) modulo some logarithmic factor.
Sample complexity and substantially reduced burn-in cost. As interpretation of our theory (16), our algorithm attains average regret (i.e., 1 Regret(T) S with sample complexity
K
ō (SAH
Crucially, the burn-in cost (17) is significantly lower than that of the state-of-the-ard memory- efficient model-free free algorithm (Zhang et al., 2020c) (whose optimality is guaranteed only in the range T 2 5 A poly(H)).
Memory efficiency. Our algorithm, which is model-free in nature, achieves a low space complexity (SS This is basically un-improvable for the tabular case, since even storing the optimal Q-values alone takes O(SAH) units of space. In comparison, while Menard et al. (2021) also accommodates the sample size range (17), the algorithm proposed therein incurs a space complexity of O(S AH) that is S times higher than ours.
Computational complexity. An additional intriguing feature of our algorithm is its low computa- tional complexity. The runtime of Q-EartySeffled-AAvvaaaaa proportional to the time taken to read the samples. This matches the computational cost of the model-free algorithm UCB-Q proposed in Jin et al. (2018), and is considerably lower than that of the UCB-M-Q algorithm in Menard al. (2021) (which has a computational cost of least O(ST)).
is no larger than O which is
Discussion
In this paper, we have proposed a novel model-free RL algorithm, tailored to online episodic settings, that attains near-optimal regret O(VH2SAT) and near-minimal memory complexity O(SAH) once. Remarkably, the near-optimality of the algorithm comes into effect as soon as the sample size rises above O(SA A poly (F)), which significantly improves upon the sample size requirements (or burn-in cost) for any prior regret-optimal model-free algorithm (based on the definition of the model-free al algorithm in Jin et al. (2018)). We hope that the method and analysis framework developed herein might inspire further studies regarding how to overcome sample size barriers in other important settings, including model-based RI. (Azar al., 2017), RI. for discounted horite MDPs (Zhang et al., 2020b), and the case with low- cowcomplyy function approximation (Jin et al., 2020; Du al., 2020; Li al., 2021b), name just few. Additionally, sample size range not yet optimal in terms of its dependency on the horizon length H. How to tighten this dependency is an important topic that is left for future investigation.
10

---

Acknowledgements
Shi and Y. Chi supported in part by the grants ONR N00014-19-1-2400 NSF CCF-2106778. CCF-20079 I and DMS-2134052 Y. Chen is supported in part by the grants AFOSR YIP award 199550-19-100330 ONR N00014-19-1-2120 ARO YIP award W91 1NNF20011-009) ARO W911NF- 18-1-0303, NSF CCF-2106733 CCF-1107661, IIS- 1900140 and IIS-2100158, and the Princeton SEAS Innovation Award. Part of this work was done while Y. Chen was visiting the Simons Institute for the Theory of Computing. Y. Gu is supported in part by the grant NSFC-61971266.
References
Agarwal, A., Kakade, S., and Yang, L., F. (2020). Model-based reinforcement learning with a generative model is minimax optimal. Conference Learning Theory, pages 67-83.
Agrawal, S. and Jia, R. (2017). Posterior sampling for reinforcement learning: worst-case regret bounds. arXiv preprint 17Xivv/705.0777
Auer, P. Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1))48-77)
Auer, P. and Ortner, R. (2010). UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, 61(1-2):55-65.
Azar, M. G., Kappen, H. J., Ghavamzadeh, M., and Munos, R. (2011). Speedy Q-learning In Advances in neural information processing systems, pages 2411-2419.
Azar, M. G., Munos, R., and Kappen, H. J. (2013). Minimax PAC bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91(3):325-349)
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Leurning- Volume 70, pages JMLR. org.
Bai, Y., Xie, T., Jiang, N., and Wang, Y.-X. (2019). Provably efficient q-learning with low switching cost. In Advances in Neural Information Processing Systems, pages 8002-8011.
Bartlett, and Tewari, A. (2009). Regal: a regularization based algorithm for reinforcement learning in weakly communicating MDPs. In Uncertainty in Artificial Intelligence: Proceedings of the 25th Conference, pages 35 15-42.44 AUAI Press.
Beck, C. L. and Srikant, R. (2012). Error bounds for constant step-size Q-learning. Systems & control letters, 12012):20331120
Bertsekas, D. (2017). Dynamic programming and optimal control (4th edition). Athena Scientific.
Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, (2020). Finite-sample analysis of stochastic approximation using smooth convex envelopes. arXiv preprint arXiv:2002.00874,
Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2021). A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants. arXiv preprint arxiv:2102.01567.
Dann, C., Lattimore, T., and Brunskill, F. (2017). Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. arXiv preprint 1rX3v:1703.07710.
Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M. (2021). Episodic reinforcement learning in finite MDPs: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR.
Dong, K., Wang, Y., Chen, X., and Wang, L. (2019). Q-learning with UCB exploration is sample efficient for fifinite-horizon MDP. arXiv preprint arXiv:1901.0931
Du, S. S., Chen, J., Li, L., Xiao, I.., and Zhou, D. (2017). Stochastic variance reduction methods for policy evaluation. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1049-1058. JMLR. org.

---

Du, S. S., Kakade, S. M., Wang, R., and Yang, L. F. (2020). Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations.
Du, S. S., Luo. Y., Wang. R., and Zhang, H. (2019). Provably efficient Q-learning with function approximation via distribution shift error checking oracle. In Advances Neural Information Processing Systems, pages 8058-8068.
Efroni, Y., Merlis, N., Ghavamzadeh, M., and Mannor, S. (2019). Tight regret bounds for model-base reinforcement learning with greedy policies. arXiv preprini arXiv: (905v 1527.
Even-Dar, E. and Mansour, Y. (2003). Learning rates for Q-learning. Journal of machine learning Research, 5(Dec):1-25.
Fan, J., Wang, Z. Xie, Y., and Yang, Z. (2019). A theoretical analysis of deep Q-learning. arXiv e-prints, pages a901.
Gower, R. M., Schmidt, M., Bach, F., and Richtárik, P. (2020). Variance-reduced methods for machine learning. Proceedings of the IEEE, 108( (08((1))1968-11))
He, J., Zhou, D., and Gu, Q. (2020). Nearly minimax optimal reinforcement learning for discounted MDPs. arXiv preprint arXiv:2010.00587.
Jaakkola, T., Jordan, M. I., and Singh, S. P. (1994). Convergence of stochastic iterative dynamic programming algorithms, In Advances in neural information processing systems, pages 703-710.
Jafamnia-Jahromi, M., Wei, C.-Y., Jain, R., and Luo, H. (2020). A model-free learning algorithm for infinite-horizon average-reward MDPs with near-optimal regret. arXiv preprint arXiv:2006.0m 043344
Jaksch, T., Ortner, R., and Auer, P. (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(.).
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863 4873.
Jin, C., Yang, Z.., Wang, Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR.
Johnson, R. and Zhang, (2013). Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pages 315-323.
Kakade, S. (2003). On the sample complexity of reinforcement learning. Phl) thesis, University of London.
Khamaru, K., Pananjady, A., Ruan, F., Wainwright, M. J., and Jordan, M. I. (2020). Is temporal difference learning optimal? instance-dependent analysis. arXiv preprint arXiv:2003.07337.
Lai, L. and Robbins, H. (1985), Asymptotically efficient adaptive allocation rules. Advances in applied mathematies, 6(1):4-22.
Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
Li, G., Cai, C., Chen, Y., Gu, Y., Wei, Y., and Chi, Y. (2021a). Is Q-learning minimax optimal? a tight sample complexity analysis. arXiv preprint arXiv: 102.06548.
Li, G., Chen, Y., Chi, Y., Gu, Y., and Wei, Y. (2021b). Sample-efficient reinforcement learning is feasible for linearly realizable MDPs with limited revisiting. accepted to Neural Information Processing Systems (NeurIPS).
Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, Y. (2021c). Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. arXiv preprint arXiv:21 10.04645.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020a). Breaking the sample size barrier in model-based reinforcement learning with generative model. In Advances in Neural Information Processing Systems, volume 33.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020b). Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. Advances in Neural Information Processing Systems (NeurIPS).
12

---

Liu, S. and Su, H. (2020). ryrrereet for non-episodic reinforcement learning. arXiv:2002.05/38.
Menard, P., Domingues, O. D., Shang, X., and Valko, M. (2021). UCB momentum Q-learning: Correcting the bias without forgetting, arXiv preprint arXiv:2103.01312.
Murphy, S. (2005). A generalization error for Q-learning. Journal of Machine Learning Research, 6:1073-1097.
Nguyen, L. M., Liu, J., Scheinberg, K., and Takáč, M. (2017). SARAH: novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2-13-200 2-21. PMLR.
Osband. I. and Van Roy, B. (2016). On lower bounds for regret reinforcement learning. arXiv preprint
Pacchiano, A., Ball, P., Parker-Holder, J., Choromanski, K., and Roberts. S. (2020). On optimism in model- based reinforcement learning. arXiv preprint arXiv:2006.1
Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
Qu, G. and Wierman, A. (2020). Finite-time analysis of asynchronous stochastic approximation and Q-learning. Conference on Learning Theory, pages 3185-3205.
Robbins, H. and Monro, S. (1951). A stochastic approximation method. The annuls of mathematical statistics, pages 400-407.
Sidford, A., Wang. M., Wu, X., Yang, L., and Ye, Y. (2018a). Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Advances in Neural Information Processing Systems, pages 5186-5196.
Sidford, A., Wang, M., Wu, X., and Ye, Y. (2018b). Variance reduced value iteration and faster algorithms for solving Markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770-787, SIAM.
Strehl, A. L., Li, L., Wicwiora, E., Langford, J., and Littman, M. L. (2006). PAC model-free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning. pages 1-18888.
Szepesvári, C. (1997). The asymptotic convergence-rate of Q-learning. In NIPS, volume 10, pages 1064-1070. Citeseer.
Tsitsiklis, J. N. (1994). Asynchronous stochastic approximation and Q-learning. Machine learning, 16(3):85-2022.
Wai, H.-T., Hong, M., Yang, Z., Wang, Z., and Tang, K. (2019). Variance reduced policy evaluation with smooth function approximation. Advances in Neural Information Processing Systems, 32:5784- 5795.
Wainwright, M. J. (2019a). Stochastic approximation with cone-contractive operators: Sharp lx bounds for Q-learning. arXiv preprint 1rX.v:1905.06255.
Wainwright, M. J. (2019b). Variance-reduced Q-learning minimax optimal. arXiv preprint 14X.077906.04697.
Wang, B., Yan, Y., and Fan, J. (2021). Sample-efficient reinforcement learning for linearly- parameterized MDPs with a generative model. urXiv preprint arXiv:2105.14016
Watkins, C. J. and Dayan, P. (1992). Q-learning. Machine learning, 8(3-4):779-292.
Watkins, J. (1989). Learning from delayed rewards. PhD thesis, King's College, University of Cambridge.
Weng, B., Xiong, H., Zhao, L., Liang Y., and Zhang, W. (2020). Momentum Q-learning with finite-sample convergence guarantee. arXiv preprint ar11v.0007.14118
13

---

Xiong, H.. Zhao, L., Liang, Y., and Zhang, W. (2020). Finite- Finite-time analysis for double Q-learning. Advances in Neural Information Processing Systems, 33.
Xu, T., Wang, Z., Zhou, Y., and Liang, Y. (2019). Reanalysis of variance reduced temporal difference learning. International Conference on Learning Representations.
Yang, K., Yang, I.., and Du, S. (2021). Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576-1584, PMLR.
Yin, M., Bai, Y., and Wang, Y.X. (2021). Near-optimal offline reinforcement learning via double variance reduction. arXiv preprint arXiv:2102.01748
Zanette, A. and Brunskill, E. (2019). Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning pages 7304-7312. PMLR.
Zhang, K., Kakade, S., Basar, T., and Yang, L. (2020a). Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33.
Zhang, Z., Ji, X., and Du, S. (2020b). Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. arXiv preprint vrXiv:2009.13500
Zhang. Z., Zhou, Y., and Ji, X. (2020c). Almost optimal model-free reinforcement learning via reference-advanter decomposition. Advances in Neural Information Processing Systems, 33.
Zhang, Z., Zhou, Y., and Ji, X. (2020d). Model-free reinforcement learning: from clipped pscudo-
regret to sample complexity. arXiv preprint arXiv:2006.003864
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contribu- tions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or a URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)?
[N/A]
(c) Did you report error bars (e.g., with respect to random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' 're us-
ing/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable informa- tion or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
14

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "zvKOnfuLVQ", "reviewer": "Reviewer_hUgT", "summary": "This paper proposes a new memory-efficient model-free algorithm for online episodic RL that achieves near-optimal regret with improved sample size requirement. It exploits reference-advantage decomposition for variance reduction and a double estimator for bias reduction to achieve the improvement.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "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": "", "main_review": "This work significantly improves the sample complexity barrier for memory-efficient RL algorithms. The use of double estimator to mitigate bias is very interesting and novel as far as I know, and can have implication for other studies.\n\nThe paper is very well written and easy to follow. The authors explain the key ideas and intuition of related work and the construction clearly. The theoretical derivations seem correct, though I didn't fully check them all in the supplementary materials.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Considering the specific setting this paper focuses on, the derivation looks solid and I don't see obvious limitations of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "XqeCB9gX4-l", "reviewer": "Reviewer_AG59", "summary": "This paper addresses the problem of designing a memory-efficient and sample-efficient algorithm for episodic MDPs with smaller initial warm-up phase. The paper proposes a new model-free algorithm \"UCB-Q-Double-Advantage\" that extends the optimistic Q-learning and the reference-advantage decomposition for variance reduction using two reference-advantage functions, i.e. the updated reference-advantage function and the old reference-advantage function. Use of these two functions with a well-curated update rule leads to near-optimal regret with SAH^2 warm-up actions, O(SAH) memory complexity, \\tilde{O}(optimal x H) sample complexity, and O(T) time complexity. The final performance is O(H) worse than optimal in terms of sample and warm-up complexities.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "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": "", "main_review": "Originality: \nThe observations following Equation 13 and its role in reducing updates of the advantage function is original and impactful. Also, the idea of using new and old reference-advantage functions as a proxy of checking the update condition derived from Eq 13 is quite interesting and effective.\n\nQuality:\n+ The paper proposes a new algorithm that juggles with warmup and sample complexities as well as space and time complexities quite efficiently with a simple (implementation wise) trick of using a new and an updated reference-advantage function. The proposed trick and its effective use opens up future developments.\n\n- The paper has two main issues. Firstly, though it explains the algorithm and the contributions in light of related work pretty well, the proof technique is never summarised intuitively and briefly. This poses hardness in pointing reasons of limitations and improvements in the proof structure. Secondly, the paper never really implements the algorithm and show its applicability. Such an implementation always increase its usability and testability by readers and practitioners. But this a common issue of most of the papers in this category.\n\n\nClarity:\n+ In general, the paper presentation is good. The contribution of the paper with respect to the existing literature is well posed in the introduction itself. Also, the formulation of the problem and the existing tricks in literature on which the paper is built are well explained and recognised. The intuition of early settlement and Eqn 13 is also well understood. \n\n- The only problem is that the proof technique is not clear in the main paper. The reader keeps on wondering why the presented intuition exactly improves the warmup or sample complexities. A brief summary of the flow of proof as in App. B.3 along with the points where it deviates from the nearest relative, i.e. UCB-Q-Advantage, will be interesting and insightful. it may also help to understand why still the sample and warmup complexities are suboptimal by H.\n\nSignificance:\nThe paper proposes an effective algorithm design technique that improves performance: the warm-up and sample complexities, and effectiveness: the space and time complexities, of existing algorithms (except UCBMQ, which has better performance but S times more space and time complexities). The use of double advantage functions and their effectiveness may invoke future research in designing more efficient and deployable RL algorithms.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. The final performance is O(H) worse than optimal in terms of sample and warm-up complexities. It would be helpful for future developments if authors include a comment on why is it so and whether there is any part of the proof that they think can be improved.\n2. The algorithm is in general presented intuitively but the proof technique is not clear in the main paper. The reader keeps on wondering why the presented intuition exactly improves the bound. Is it only the number of reference function updates or is it more than that? If the first is true, then how much than single advantage function?\n3. Another point is that authors mentioned similar and even better warm-up complexity and regret is achieved by UCB-M-Q as \"at a price of a higher storage burden\". The statement seems a bit loose, and as if it is fundamentally necessary to have such larger space complexity to achieve UCB-M-Q's improvements. Explaining whether it is authors intuition or only a way of presenting the result or they think it is fundamental by construction will make the argument rigorous.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "5u5XXFETLiL", "reviewer": "Reviewer_fvnk", "summary": "This paper proposes a modified model-free reinforcement learning algorithm for time-inhomogeneous tabular MDP, in which it presents the novel technique of *Double Advantage*. It achieves nearly optimal regret and more importantly, the required sample size of being nearly optimal is significantly smaller than previous works if we require the algorithm to also be space-efficient.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "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": "", "main_review": "Overall, I consider the technique of *Double Advantage* developed by this paper is novel in the sense that using two reference value functions circumvents the need of using the unknown $V^\\star_h$. Meanwhile, the whole paper is also well-written with lots of intuitive explanation and clear proof sketch in the appendix.\n\nHowever, I feel hesitant about the significance of its result. In particular, an improvement of space complexity in order of $O(S)$ does not look so valuable compared to a sacrifice of sample complexity in order of $O\\left(H^4\\right)$.\n\nQuestions:\n- How does the choice of constant \"1\" affects the final result in Line 13 of Algorithm 1?\n- Is there any more direct intuitive explanation on why the updating rule (13) at the bottom of page 6 decreases the necessary sample size of being optimal?\n- At line 221, it says that as long as $V^{\\mathsf{R}}_h(s_h)<V^\\star_h(s_h)+2$ is satisfied, there will not be any further updates for $V^{\\mathsf{R}}_h$. Does this imply that $V^{\\mathsf{R}}_h$ decreases monotonically (through *update-ucb-q-advantage*) as episode index $k$ increases? That is, will we have $V^{\\mathsf{R}}_h(s_h)\\ge V^\\star_h(s_h)+2$ in future?\n- Although the problem formulation and analysis assumes a time-inhomogeneous MDP, the algorithm itself seems to be applicable for time-homogeneous MDP also. Is there any intuition on how it will perform on a time-homogeneous MDP?\n- Does the sample complexity dependency on $S$ and $A$ more important than $H$?\n\nSuggestions on writing:\n- $W_h^{\\mathsf{R}_i}$ appears without initialization in Algorithm 1.\n- It seems better to give a precise mathematical definition of $B^{\\mathsf{R}}_h(s, a)$.\n- It is probably better to roughly describe in the main text about how you use two reference value functions to avoid the need of using $V^\\star_h$, the part of *step 3* in Section B.3.\n\n---\n\nScore increased after rebuttal.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations of their work in Section 4 by presenting them as potential future works. The potential negative social impact is not addressed, which is not so needed for a purely theoretical analysis on tabular MDPs.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

Following the rebuttal, the reviewers reached a consensus to positively evaluate the contribution.



Decision: Accept (Spotlight)