Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning

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 √ H2SAT (modulo log factors) with T the total number of samples. While several competing solution paradigms have been proposed to minimize regret, they are either memoryinefficient, or fall short of optimality unless the sample size exceeds an enormous threshold (e.g., SA 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 SApoly(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 SA — upon any prior memory-efficient algorithm that is asymptotically regret-optimal. Leveraging the recently introduced variance reduction strategy (also called reference-advantage decomposition), the proposed algorithm employs an 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 tradeoffs.

text: √ H2SAT (modulo
log factors) with T the total number of samples. While several competing solution paradigms have been proposed to minimize regret, they are either memoryinefficient, or fall short of optimality unless the sample size exceeds an enormous threshold (e.g., S6A4 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 SApoly(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 S5A3 — upon any prior memory-efficient algorithm that is asymptotically regret-optimal. Leveraging the recently introduced variance reduction strategy (also called reference-advantage decomposition), the proposed algorithm employs an 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 tradeoffs.

heading: 1 Introduction
text: Contemporary reinforcement learning (RL) has to deal with unknown environments with unprecedentedly large dimensionality. How to make the best use of samples in the face of high-dimensional state/action space lies at the core of 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 dynamics 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 it comes to online episodic RL scenarios. In contrast to the simulator setting that permits sampling of any state-action pair, an agent in online episodic RL is only allowed to draw sample trajectories by executing a policy in 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 use to allow for effective interaction with the unknown environment, ∗Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544, USA. †Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA. ‡Department of Electronic Engineering, Tsinghua University, Beijing 100084, China.
35th Conference on 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.

heading: 1.1 Regret-optimal model-free RL? A sample size barrier
text: In order to evaluate and compare the effectiveness of RL algorithms in high dimension, a 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 non-asymptotic fashion (Dann et al., 2017; Kakade, 2003). Such finite-sample guarantees are brought to bear towards understanding and tackling the challenges in the samplestarved 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 — a metric that quantifies the performance difference between the learned policy and the true optimal policy — with the fewest number of 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 0 and 1.
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 a 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) √ H2SAT , (1)
as long as T ≥ H2SA.4 This sublinear regret lower bound in turn imposes a sampling limit if one wants to achieve ε 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 a 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 to ensure a sufficient degree of exploration, Zhang et al. (2020b) came up with an algorithm called MVP that blends model-based learning and the optimism principle, which achieves a regret bound5 Õ (√ H2SAT ) 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 T ≥ S3AH4, a threshold that is significantly larger than the dimension of the underlying model. This threshold can also be understood as the initial burn-in cost of the algorithm, namely, a 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(S2AH) (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 et 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 et al. (2018)), an algorithm is declared to be model-free only if its space complexity is o(S2AH) regardless of the sample size T .
• Memory-efficient model-free methods. Jin et al. (2018) proposed the first memory-efficient modelfree algorithm — which is an optimistic variant of classical Q-learning — that achieves a regret bound proportional to √ T with a space complexity O(SAH). Compared to the lower bound (1),
however, the regret bound in Jin et al. (2018) is off by a factor of √ H and hence suboptimal for
4Given that a trivial upper bound on the regret is T , one needs to impose a lower bound T ≥ H2SA in order for (1) to be meaningful.
5Here and throughout, we use the standard notation f(n) = O(g(n)) to indicate that f(n)/g(n) is bounded above by a constant as n grows. The notation Õ(·) resembles O(·) except that it hides any logarithmic scaling. The notation f(n) = o(g(n)) means that limn→∞ f(n)/g(n) = 0.
the optimal regret Õ(
√
H2SAT ), 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 in Zhang et al. (2020c) by leveraging the idea of variance reduction (or the so-called “reference-advantage decomposition”) for large enough T . While the resulting regret matches the information-theoretic 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 ≥ S6A4H28, a requirement that is even far more stringent than the burn-in cost imposed by Azar et al. (2017).
• A memory-inefficient “model-free” variant. The recent work Menard et al. (2021) put forward a novel sample-efficient variant of 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̃ (√ H2SAT ) as soon as the sample size exceeds T ≥ SApoly(H), which is a remarkable
improvement vis-à-vis previous regret-optimal methods (Azar et 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, as the space required to store all bias-value function is O(S2AH) and the computation required is O(ST ), 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 et al. (2006); Jin et al. (2018). See Menard et al. (2021, Section 3.3) for more detailed discussions.
A more complete summary of prior results can be found in Table 1.

heading: 1.2 A glimpse of our contributions
text: 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 memory-inefficient, or require the sample size to exceed a threshold substantially larger than the model dimensionality. In fact, no prior algorithms have been shown to be simultaneously regret-optimal and memory-efficient unless
T ≥ S6A4 poly(H),
which constitutes a 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 a natural question:

heading: Is it possible to design an algorithm that accommodates a significantly broader
text: sample size range without compromising regret optimality and memory efficiency?
In this paper, we answer this question affirmatively, by designing a new model-free algorithm, dubbed as Q-EarlySettled-Advantage, that enjoys the following performance guarantee. Theorem 1 (informal). The proposed Q-EarlySettled-Advantage algorithm, which has a space complexityO(SAH), achieves near-optimal regret Õ (√ H2SAT ) as soon as the sample size exceeds
T ≥ SApoly(H).
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 O(SAH), which is far more memoryefficient 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 S2AH units of space). In addition, the sample size requirement T ≥ SApoly(H) of our algorithm improves — by a factor of at least S5A3 — 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 on 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 variancereduced Q-learning, Q-EarlySettled-Advantage leverages the recently-introduced referenceadvantage 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-exploitation trade-offs.

heading: 1.3 Related works
text: 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 infinite-horizon 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., 2018a,b; Wainwright, 2019b), asynchronous Q-learning (Li et al., 2020b), and offline RL (Yin et al., 2021).

heading: 2 Problem formulation
text: In this section, we formally describe the problem setting. Here and throughout, we denote by ∆(S) the probability simplex over a set S, and [M ] := {1, · · · ,M} for any integer M > 0.
Basics of finite-horizon MDPs. LetM = (S,A, H, {Ph}Hh=1, {rh}Hh=1) represent a finite-horizon MDP, where S := {1, · · ·S} is the state space of size S, A := {1, · · · , A} is the action space of size A, H denotes the horizon length, and Ph : S ×A → ∆(S) (resp. rh : S ×A → [0, 1]) represents the probability transition kernel (resp. reward function) at the h-th time step, 1 ≤ h ≤ H , respectively.
More specifically, Ph(· | s, a) ∈ ∆(S) stands for the transition probability vector from state s at time step h when action a is taken, while rh(s, a) indicates the immediate reward received at time step h 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 Ph’s are not identical across 1 ≤ h ≤ H . A policy of an agent is represented by π = {πh}Hh=1 with πh : S → A the action selection rule at time step h, so that πh(s) specifies which action to execute in state s at time step h. Throughout this paper, we concentrate on deterministic policies.
Value functions, Q-functions, and Bellman equations. The value function V πh (s) of a (deterministic) 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 s at time step h, namely,
V πh (s) := E st+1∼Pt(·|st,πt(st)), t≥h [ H∑ t=h rt ( st, πt(st) ) ∣∣∣ sh = s] , (2) where the expectation is taken over the randomness of the MDP trajectory {st | h ≤ t ≤ H}. The action-value function (a.k.a. the Q-function) Qπh(s, a) of a policy π at step h can be defined analogously except that the action at step h is fixed to be a, that is,
Qπh(s, a) := rh(s, a) + E sh+1∼Ph(·|s,a),
st+1∼Pt(·|st,πt(st)), t>h
[ H∑
t=h+1
rt ( st, πt(st) ) ∣∣∣ sh = s, ah = a] . (3) In addition, we define V πH+1(s) = Q π H+1(s, a) = 0 for any policy π and any state-action pair (s, a) ∈ S ×A. By virtue of basic properties in dynamic programming (Bertsekas, 2017), the value function and the Q-function satisfy the following Bellman equation:
Qπh(s, a) = rh(s, a) + E s′∼Ph(·|s,a)
[ V πh+1(s ′) ] . (4)
A policy π? = {π?h}Hh=1 is said to be an optimal policy if it maximizes the value function simultaneously for all states among all policies. The resulting optimal value function V ? = {V ?h }Hh=1 and optimal Q-functions Q? = {Q?h}Hh=1 satisfy
V ?h (s) = V π?
h (s) = max π
V πh (s) and Q ? h(s, a) = Q
π? h (s, a) = max π Qπh(s, a) (5)
for any (s, a, h) ∈ S ×A× [H]. It is well known that the optimal policy always exists (Puterman, 2014), and satisfies the Bellman optimality equation:
∀(s, a, h) ∈ S ×A× [H] : Q?h(s, a) = rh(s, a) + E s′∼Ph(·|s,a)
[ V ?h+1(s ′) ] . (6)
Online episodic RL. This paper investigates the online episodic RL setting, where the agent is allowed to execute the MDP sequentially in a total number of K episodes each of length H . This amounts to collecting T = KH samples in total. More specifically, in each episode k = 1, . . . ,K, the agent is assigned an arbitrary initial state sk1 (possibly by an adversary), and selects a policy π
k = {πkh}Hh=1 learned based on the information collected up to the (k − 1)-th episode. The k-th episode is then executed following the policy πk and the dynamic of the MDPM, leading to a length-H sample trajectory.
Goal: regret minimization. In order to evaluate the quality of the learned policies {πk}1≤k≤K , a frequently used performance metric is the cumulative regret defined as follows:
Regret(T ) := K∑ k=1 ( V ?1 (s k 1)− V π k 1 (s k 1) ) . (7)
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 a sample-optimal algorithm, namely, an 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-limited regime.
Notation. Before presenting our main results, we take a moment to introduce some convenient notation to be used throughout the remainder of this paper. For any vector x ∈ RSA that constitutes certain quantities for all state-action pairs, we shall often use x(s, 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 = Ph(· | s, a) ∈ R1×S (8) abbreviate the transition probability vector given the (s, a) pair at time step h. Additionally, we denote by ei the i-th standard basis vector, with the only non-zero element being in the i-th entry and equal to 1.

heading: 3 Algorithm and theoretical guarantees
text: In this section, we present the proposed algorithm called Q-EarlySettled-Advantage, as well as the accompanying theory confirming its sample and memory efficiency.

heading: 3.1 Review: Q-learning with UCB exploration and reference advantage
text: This subsection briefly reviews the Q-learning algorithm with UCB exploration proposed in Jin et al. (2018), as well as a 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 Qlearning 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):
Qh(s, a)← (1− η)Qh(s, a) + η { rh(s, a) + P̂h,s,aVh+1︸ ︷︷ ︸
stochastic estimate of Ph,s,aVh+1
} . (9)
Here, Qh (resp. Vh) indicates the running estimate of Q?h (resp. V ? h ), η is the (possibly iterationvarying) learning rate or stepsize, and P̂h,s,aVh+1 is a stochastic estimate of Ph,s,aVh+1 (cf. (8)). For instance, if one has available a sample (s, a, s′) transitioning from state s at step h to s′ at step h+ 1 under action a, then a stochastic estimate of Ph,s,aVh+1 can be taken as Vh+1(s′), which is unbiased in the sense that
E [ Vh+1(s ′) ]
= Ph,s,aVh+1. To further encourage exploration, the algorithm proposed in Jin et al. (2018) — which shall be abbreviated as UCB-Q or UCB-Q-Hoeffding hereafter — augments the Q-learning update rule (9) in each episode via an additional exploration bonus:
QUCBh (s, a)← (1− η)QUCBh (s, a) + η { rh(s, a) + P̂h,s,aVh+1 + bh } . (10)
The bonus term bh ≥ 0 is chosen to be a certain upper confidence bound for (P̂h,s,a − Ph,s,a)Vh+1, an exploration-efficient scheme that originated from the bandit literature (Lai and Robbins, 1985; Lattimore and Szepesvári, 2020). The algorithm then proceeds to the next episode by executing/sampling 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-Advantage). The regret bounds derived for UCB-Q (Jin et al., 2018), however, fall short of being optimal, as they are at least a factor of √ H away from the fundamental lower bound. In order to 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-advantage 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-Q-Advantage, imagine that we are able to maintain a collection of reference values V R = {V Rh }Hh=1, which form reasonable estimates of V ? = {V ?h }Hh=1 and become increasingly more accurate as the algorithm progresses. At each time step h, the algorithm adopts the following update rule
QRh(s, a)← (1− η)QRh(s, a) + η { rh(s, a) +P̂h,s,a ( Vh+1 − V Rh+1 )︸ ︷︷ ︸ stochastic estimate of Ph,s,a ( Vh+1−V Rh+1 )+ [ P̂hV Rh+1 ] (s, a) + bRh } . (11)
Two ingredients of this update rule are worth noting. • Akin to the UCB-Q case, we can take P̂h,s,a ( Vh+1−V Rh+1 ) to be the stochastic estimate Vh+1(s′)−
V Rh+1(s ′) if we observe a sample transition (s, a, s′) at time step h. If Vh+1 is fairly close to the reference V Rh+1, then this stochastic term can be less volatile than the stochastic term P̂h,s,aVh+1 in (10).
• Additionally, the term P̂hV Rh+1 indicates an estimate of the one-step look-ahead value PhV R h+1,
which shall be computed using a batch of samples. The variability of P̂hV Rh+1 can be well-controlled through the use of batch data, at the price of an increased sample size.
Accordingly, the exploration bonus term bRh is taken to be an upper confidence bound for the abovementioned 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-EarlySettled-Advantage
As alluded to previously, however, the sample size required for UCB-Q-Advantage to achieve optimal regret needs to exceed a large polynomial S6A4 in the size of the state/action space. To overcome this sample complexity barrier, we come up with an improved variant called Q-EarlySettledAdvantage.
Motivation: early settlement of a reference value. An important insight obtained from previous algorithm designs is that: in order to achieve low regret, it 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−Q? as much as possible. With two additional optimistic Q-estimates in hand — QUCBh based on UCB-Q, and a reference Q R h — it is natural to combine them as follows to further reduce the bias without violating the optimism principle:
Qh(sh, ah)← min { QRh(sh, ah), Q UCB h (sh, ah), Qh(sh, ah) } . (12)
This is precisely what is conducted in UCB-Q-Advantage. However, while the estimate QRh obtained with the aid of reference-advantage decomposition provides great promise, fully realizing its potential in the sample-limited regime relies on the ability to quickly settle on a 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 V R needs to be updated in a timely manner in order to better control the stochastic estimate of Ph,s,a ( Vh+1 − V Rh+1 ) . On the other hand, updating V R too frequently incurs an overly large sample size burden, as new samples need to be accumulated whenever V R is updated.
Built upon the above insights, it is advisable to prevent frequent updating of the reference value V R. In fact, it would be desirable to stop updating the reference value once a point of sufficient quality — denoted by V R,final — has been obtained. Locking on a reasonable reference value early on means that (a) fewer samples will be wasted on estimating a drifting target PhV Rh+1, and (b) all ensuing samples can then be dedicated to estimating the key quantity of interest PhV R,final h+1 .
Remark 1. In Zhang et al. (2020c), the algorithm UCB-Q-Advantage requires collecting Õ ( SAH6 ) samples for each state before settling on the reference value, which inevitably contributes to the large burn-in cost.
The proposed Q-EarlySettled-Advantage algorithm. We now propose a new model-free algorithm that allows for early settlement of the reference value. A few key ingredients are as follows.
• An auxiliary sequence based on LCB. In addition to the two optimistic Q-estimates QRh and Q UCB h
described previously, we intend to maintain another pessimistic estimate QLCBh ≤ Q?h using the subroutine update-lcb-q, based on lower confidence bounds (LCBs). We will also maintain the corresponding value function V LCBh , which lower bounds V ? h .
• Termination rules for reference updates. With V LCBh ≤ V ?h in place, the updates of the references (lines 15-18 of Algorithm 1) are designed to terminate when
Vh(sh) ≤ V LCBh (sh) + 1 ≤ V ?h (sh) + 1. (13)
Algorithm 1: Q-EarlySettled-Advantage 1 Parameters: some universal constant cb > 0 and probability of failure δ ∈ (0, 1); 2 Initialize Qh(s, a), QUCBh (s, a), QRh(s, a)← H; Vh(s), V Rh (s)← H; QLCBh (s, a)← 0;
V LCBh (s)← 0; Nh(s, a)← 0; µrefh (s, a), σ ref h (s, a), µ adv h (s, a), σ adv h (s, a), δ R h(s, a), B R h(s, a)← 0; and uref(s) = True for all
(s, a, h) ∈ S ×A× [H]. 3 for Episode k = 1 to K do 4 Set initial state s1 ← sk1 . 5 for Step h = 1 to H do 6 Take action ah = πkh(sh) = arg maxaQh(sh, a), and draw sh+1 ∼ Ph(· | sh, ah). // sampling 7 Nh(sh, ah)← Nh(sh, ah) + 1; n← Nh(sh, ah). // update the counter 8 ηn ← H+1H+n . // update the learning rate 9 QUCBh (sh, ah)← update-ucb-q(). // run UCB-Q; see Algorithm 2
10 QLCBh (sh, ah)← update-lcb-q(). // run LCB-Q; see Algorithm 2 11 QRh(sh, ah)← update-ucb-q-advantage(). // estimate QRh; see Algorithm 2
/* update Q-estimates using all estimates in hand, and update value estimates */ 12 Qh(sh, ah)← min { QRh(sh, ah), Q UCB h (sh, ah), Qh(sh, ah) } . 13 Vh(sh)← maxaQh(sh, a). 14 V LCBh (sh)← max { maxaQ LCB h (sh, a), V LCB h (sh) } . /* update reference values */ 15 if Vh(sh)− V LCBh (sh) > 1 then 16 V Rh (sh)← Vh(sh). 17 else if uref(sh) = True then 18 V Rh (sh)← Vh(sh), uref(sh) = False.
Note that V Rh keeps tracking the value of Vh before it stops being updated. In effect, when the additional condition in lines 15 is violated and thus (13) is satisfied, we claim that it is unnecessary to update the reference V Rh afterwards, since it is of sufficient quality (being close enough to the optimal value V ?h ) 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 |Vh − V Rh | ≤ 2 throughout the execution of the algorithm, which in turn suggests that the standard deviation of P̂h,s,a(Vh+1 − V Rh+1) might be O(H) times smaller than that of P̂h,s,aVh+1 (i.e., the stochastic term used in (9) of UCB-Q). This is a key observation that helps shave the addition factor H in the regret bound of UCB-Q.
• Update rules for QUCBh and Q R h. The two optimistic Q-estimates Q UCB h and Q R h are updated using
the subroutine update-ucb-q (following the standard Q-learning with Hoeffding bonus (Jin et al., 2018)) and update-ucb-q-advantage, respectively. Note that QRh continues to be updated even after V Rh is no longer updated.
Q-learning with reference-advantage decomposition. The rest of this subsection is devoted to explaining the subroutine update-ucb-q-advantage, which produces a Q-estimate QR based on the reference-advantage decomposition similar to Zhang et al. (2020c). To facilitate the implementation, let us introduce the parameters associated with a reference value V R, which include six different components, i.e., [
µrefh (s, a), σ ref h (s, a), µ adv h (s, a), σ adv h (s, a), δ R h(s, a), B R h(s, a)
] , (14)
for all (s, a, h) ∈ S × A × [H]. Here µrefh (s, a) and σrefh (s, a) estimate the running mean and 2nd moment of the reference [ PhV R h+1 ] (s, a); µadvh (s, a) and σ adv h (s, a) estimate the running (weighted)
mean and 2nd moment of the advantage [ Ph(Vh+1−V Rh+1) ] (s, a); BRh(s, a) aggregates the empirical standard deviations of the reference and the advantage combined; and last but not least, δRh(s, a) is the temporal difference between BRh(s, a) and its previous value.
Algorithm 2: Auxiliary functions 1 Function update-ucb-q():
2 QUCBh (sh, ah)← (1−ηn)QUCBh (sh, ah)+ηn ( rh(sh, ah)+Vh+1(sh+1)+cb √ H3 log SATδ n ) .
3 Function update-lcb-q(): 4 QLCBh (sh, ah)← (1−ηn)QLCBh (sh, ah)+ηn ( rh(sh, ah)+V LCB h+1 (sh+1)−cb √ H3 log SATδ n ) .
5 Function update-ucb-q-advantage(): /* update the moment statistics of V Rh */ 6 [µrefh , σ ref h , µ adv h , σ adv h ](sh, ah)← update-moments(); /* update the accumulative bonus and bonus difference */ 7 [δRh , B R h ](sh, ah)← update-bonus(); 8 bRh ← BRh(sh, ah) + (1− ηn) δRh(sh,ah) ηn + cb H2 log SATδ n3/4
; /* update the Q-estimate based on reference-advantage decomposition */
9 QRh(sh, ah)← (1− ηn)QRh(sh, ah) + ηn ( rh(sh, ah) + Vh+1(sh+1)− V Rh+1(sh+1) + µrefh (sh, ah) + bRh ) ;
10 Function update-moments(): 11 µrefh (sh, ah)← (1− 1n )µ ref h (sh, ah) + 1 nV R h+1(sh+1); // mean of the reference 12 σrefh (sh, ah)← (1− 1n )σ ref h (sh, ah) + 1 n ( V Rh+1(sh+1) )2 ; // 2nd moment of the reference 13 µadvh (sh, ah)← (1− ηn)µadvh (sh, ah) + ηn ( Vh+1(sh+1)− V Rh+1(sh+1) ) ; // weighted
average of the advantage 14 σadvh (sh, ah)← (1− ηn)σadvh (sh, ah) + ηn ( Vh+1(sh+1)− V Rh+1(sh+1) )2 . // weighted
2nd moment of the advantage
15 Function update-bonus(): 16 Bnexth (sh, ah)←
cb
√ log SATδ
n (√ σrefh (sh, ah)− ( µrefh (sh, ah) )2 + √ H √ σadvh (sh, ah)− ( µadvh (sh, ah) )2 ) ;
17 δRh(sh, ah)← Bnexth (sh, ah)−BRh(sh, ah); 18 BRh(sh, ah)← Bnexth (sh, ah).
As alluded to previously, the Q-function estimation follows the strategy (11) at a high level. Upon observing a sample transition (sh, ah, sh+1), we compute the following estimates to update QR(sh, ah). • The term P̂h,s,a ( Vh+1 − V Rh+1 ) is set to be Vh+1(sh+1) − V Rh+1(sh+1), which is an unbiased
stochastic estimate of Ph,s,a ( Vh+1 − V Rh+1 ) .
• The term [ PhV R h+1 ] (s, a) is estimated via µref,Rh (cf. line 11). Given that this is estimated using all
previous samples, we expect the variability of this term to be well-controlled as the sample size increases (especially after V R is locked).
• The exploration bonus bRh(s, a) is updated using B R h(sh, ah) and δ R h(sh, ah) (cf. lines 7-8 of
Algorithm 2), which is a confidence bound accounting for both the reference and the advantage. Let us also explain line 8 of Algorithm 2 a bit. If we augment the notation by letting bR,n+1h (s, a) and BR,n+1h (s, a) denote respectively b R h(s, a) and B R h(s, a) after (s, a) is visited for the n-th time, then this line is designed to ensure that
ηnb R,n+1 h (s, a) + (1− ηn)B R,n h (s, a) ≈ B R,n+1 h (s, a).
With the above updates implemented properly, QRh provides the advantage-based update of the Q-function at time step h, according to the update rule (11).

heading: 3.3 Main results
text: Encouragingly, the proposed Q-EarlySettled-Advantage algorithm manages to achieve near-optimal regret even in the sample-limited and memory-limited regime, as formalized by the following theorem; the proof can be found in the full version Li et al. (2021c). Theorem 2. Consider any δ ∈ (0, 1), and suppose that cb > 0 is chosen to be a sufficiently large universal constant. Then there exists some absolute constant C0 > 0 such that Algorithm 1 achieves
Regret(T ) ≤ C0 (√ H2SAT log4 SAT
δ +H6SA log3
SAT
δ
) (15)
with probability at least 1− δ.
Theorem 2 delivers a non-asymptotic characterization of the performance of our algorithm QEarlySettled-Advantage. Several appealing features of the algorithm are noteworthy.
• Regret optimality. Our regret bound (15) simplifies to Regret(T ) ≤ Õ (√ H2SAT ) (16)
as long as the sample size T exceeds
T ≥ SApoly(H). (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 an interpretation of our theory (16), our algorithm attains ε average regret (i.e., 1KRegret(T ) ≤ ε) with a sample complexity
Õ (SAH4
ε2
) .
Crucially, the burn-in cost (17) is significantly lower than that of the state-of-the-art memoryefficient model-free algorithm (Zhang et al., 2020c) (whose optimality is guaranteed only in the range T ≥ S6A4 poly(H)).
• Memory efficiency. Our algorithm, which is model-free in nature, achieves a low space complexity O(SAH). 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(S2AH) that is S times higher than ours.
• Computational complexity. An additional intriguing feature of our algorithm is its low computational complexity. The runtime of Q-EarlySettled-Advantage is no larger than O(T ), which is 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 et al. (2021) (which has a computational cost of at least O(ST )).

heading: 4 Discussion
text: In this paper, we have proposed a novel model-free RL algorithm, tailored to online episodic settings, that attains near-optimal regret Õ( √ H2SAT ) and near-minimal memory complexity O(SAH) at once. Remarkably, the near-optimality of the algorithm comes into effect as soon as the sample size rises above O(SApoly(H)), 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 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 RL (Azar et al., 2017), RL for discounted infinite-horizon MDPs (Zhang et al., 2020b), and the case with low-complexity function approximation (Jin et al., 2020; Du et al., 2020; Li et al., 2021b), to name just a few. Additionally, our sample size range is 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.

heading: Acknowledgements
text: L. Shi and Y. Chi are supported in part by the grants ONR N00014-19-1-2404, NSF CCF-2106778, CCF-2007911 and DMS-2134080. Y. Chen is supported in part by the grants AFOSR YIP award FA9550-19-1-0030, ONR N00014-19-1-2120, ARO YIP award W911NF-20-1-0097, ARO W911NF18-1-0303, NSF CCF-2106739, CCF-1907661, 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.

Review summaries:
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.