# TOWARDS DEPLOYMENT-EFFICIENT REINFORCEMENT LEARNING: LOWER BOUND AND OPTIMALITY

**Jiawei Huang[˚]:, Jinglin Chen:, Li Zhao;, Tao Qin;, Nan Jiang:, Tie-Yan Liu;**
: Department of Computer Science, University of Illinois at Urbana-Champaign
_{jiaweih, jinglinc, nanjiang}@illinois.edu_
; Microsoft Research Asia
_{lizo, taoqin, tyliu}@microsoft.com_

ABSTRACT

Deployment efficiency is an important criterion for many real-world applications
of reinforcement learning (RL). Despite the community’s increasing interest, there
lacks a formal theoretical formulation for the problem. In this paper, we propose
such a formulation for deployment-efficient RL (DE-RL) from an “optimization
with constraints” perspective: we are interested in exploring an MDP and obtaining a near-optimal policy within minimal deployment complexity, whereas in each
deployment the policy can sample a large batch of data. Using finite-horizon linear
MDPs as a concrete structural model, we reveal the fundamental limit in achieving
deployment efficiency by establishing information-theoretic lower bounds, and
provide algorithms that achieve the optimal deployment efficiency. Moreover, our
formulation for DE-RL is flexible and can serve as a building block for other practically relevant settings; we give “Safe DE-RL” and “Sample-Efficient DE-RL” as
two examples, which may be worth future investigation.

1 INTRODUCTION

In many real-world applications, deploying a new policy to replace the previous one is costly, while
generating a large batch of samples with an already deployed policy can be relatively fast and cheap.
For example, in recommendation systems (Afsar et al., 2021), education software (Bennane et al.,
2013), and healthcare (Yu et al., 2019), the new recommendation, teaching, or medical treatment
strategy must pass several internal tests to ensure safety and practicality before being deployed,
which can be time-consuming. On the other hand, the algorithm may be able to collect a large
amount of samples in a short period of time if the system serves a large population of users. Besides,
in robotics applications (Kober et al., 2013), deploying a new policy usually involves operations on
the hardware level, which requires non-negligible physical labor and long waiting periods, while
sampling trajectories is relatively less laborious. However, deployment efficiency was neglected
in most of existing RL literatures. Even for those few works considering this important criterion
(Bai et al., 2020; Gao et al., 2021; Matsushima et al., 2021), either their settings or methods have
limitations in the scenarios described above, or a formal mathematical formulation is missing. We
defer a detailed discussion of these related works to Section 1.1.

In order to close the gap between existing RL settings and real-world applications requiring high
deployment efficiency, our first contribution is to provide a formal definition and tractable objective
for Deployment-Efficient Reinforcement Learning (DE-RL) via an “optimization with constraints”
perspective. Roughly speaking, we are interested in minimizing the number of deployments K under
two constraints: (a) after deploying K times, the algorithm can return a near-optimal policy, and (b)
the number of trajectories collected in each deployment, denoted as N, is at the same level across
_K deployments, and it can be large but should still be polynomial in standard parameters. Similar_
to the notion of sample complexity in online RL, we will refer to K as deployment complexity.

˚Work done during the internship at Microsoft Research Asia.


-----

To provide a more quantitative understanding, we instantiate our DE-RL framework in finite-horizon
linear MDPs[1] (Jin et al., 2019) and develop the essential theory. The main questions we address are:

_Q1: What is the optimum of the deployment efficiency in our DE-RL setting?_
_Q2: Can we achieve the optimal deployment efficiency in our DE-RL setting?_

When answering these questions, we separately study algorithms with or without being constrained
to deploy deterministic policies each time. While deploying more general forms of policies can
be practical (e.g., randomized experiments on a population of users can be viewed as deploying a
mixture of deterministic policies), most previous theoretical works in related settings exclusively focused on upper and lower bounds for algorithms using deterministic policies (Jin et al., 2019; Wang
et al., 2020b; Gao et al., 2021). As we will show, the origin of the difficulty in optimizing deployment efficiency and the principle in algorithm design to achieve optimal deployment efficiency are
generally different in these two settings, and therefore, we believe both of them are of independent
interests.

As our second contribution, in Section 3, we answer Q1 by providing information-theoretic lower
bounds for the required number of deployments under the constraints of (a) and (b) in Def 2.1. We
establish ΩpdHq and ΩpHq lower bounds for algorithms with and without the constraints of deploying deterministic policies, respectively. Contrary to the impression given by previous empirical
works (Matsushima et al., 2021), even if we can deploy unrestricted policies, the minimal number

[r]
of deployments cannot be reduced to a constant without additional assumptions, which sheds light
on the fundamental limitation in achieving deployment efficiency. Besides, in the line of work on
“horizon-free RL” (e.g., Wang et al., 2020a), it is shown that RL problem is not significantly harder
than bandits (i.e., when H “ 1) when we consider sample complexity. In contrast, the H dependence in our lower bound reveals some fundamental hardness that is specific to long-horizon RL,
particularly in the deployment-efficient setting. [2] Such hardness results were originally conjectured
by Jiang & Agarwal (2018), but no hardness has been shown in sample-complexity settings.

After identifying the limitation of deployment efficiency, as our third contribution, we address Q2 by
proposing novel algorithms whose deployment efficiency match the lower bounds. In Section 4.1,
we propose an algorithm deploying deterministic policies, which is based on Least-Square Value
Iteration with reward bonus (Jin et al., 2019) and a layer-by-layer exploration strategy, and can return
an ε-optimal policy within OpdHq deployments. As part of its analysis, we prove Lemma 4.2 as a
technical contribution, which can be regarded as a batched finite-sample version of the well-known
“Elliptical Potential Lemma”(Carpentier et al., 2020) and may be of independent interest. Moreover,
our analysis based on Lemma 4.2 can be applied to the reward-free setting (Jin et al., 2020; Wang
et al., 2020b) and achieve the same optimal deployment efficiency. In Section 4.2, we focus on
algorithms which can deploy arbitrary policies. They are much more challenging because it requires
us to find a provably exploratory stochastic policy without interacting with the environment. To our
knowledge, Agarwal et al. (2020b) is the only work tackling a similar problem, but their algorithm is
model-based which relies on a strong assumption about the realizability of the true dynamics and a
sampling oracle that allows the agent to sample data from the model, and how to solve the problem in
linear MDPs without a model class is still an open problem. To overcome this challenge, we propose
a model-free layer-by-layer exploration algorithm based on a novel covariance matrix estimation
technique, and prove that it requires ΘpHq deployments to return an ε-optimal policy, which only
differs from the lower bound ΩpHq by a logarithmic factor. Although the per-deployment sample
complexity of our algorithm has dependence on a “reachability coefficient” (see Def. 4.3), similar
quantities also appear in related works (Zanette et al., 2020; Agarwal et al., 2020b; Modi et al., 2021)

[r]
and we conjecture that it is unavoidable and leave the investigation to future work.

Finally, thanks to the flexibility of our “optimization with constraints” perspective, our DE-RL setting can serve as a building block for more advanced and practically relevant settings where optimizing the number of deployments is an important consideration. In Appendix F, we propose
two potentially interesting settings: “Safe DE-RL” and “Sample-Efficient DE-RL”, by introducing
constraints regarding safety and sample efficiency, respectively.

1Although we focus on linear MDPs, the core idea can be extended to more general settings such as RL
with general function approximation (Kong et al., 2021).
2Although (Wang et al., 2020a) considered stationary MDP, as shown in our Corollary 3.3, the lower bounds
of deployment complexity is still related to H.


-----

1.1 CLOSELY RELATED WORKS

We defer the detailed discussion of previous literatures about pure online RL and pure offline RL
to Appendix A, and mainly focus on those literatures which considered deployment efficiency and
more related to us in this section.

To our knowledge, the term “deployment efficiency” was first coined by Matsushima et al. (2021),
but they did not provide a concrete mathematical formulation that is amendable to theoretical investigation. In existing theoretical works, low switching cost is a concept closely related to deployment
efficiency, and has been studied in both bandit (Esfandiari et al., 2020; Han et al., 2020; Gu et al.,
2021; Ruan et al., 2021) and RL settings (Bai et al., 2020; Gao et al., 2021; Kong et al., 2021).
Another related concept is concurrent RL, as proposed by Guo & Brunskill (2015). We highlight
the difference with them in two-folds from problem setting and techniques.

As for the problem setting, existing literature on low switching cost mainly focuses on sub-linear
regret guarantees, which does not directly implies a near-optimal policy after a number of policy
deployments[3]. Besides, low switching-cost RL algorithms (Bai et al., 2020; Gao et al., 2021; Kong
et al., 2021) rely on adaptive switching strategies (i.e., the interval between policy switching is not
fixed), which can be difficult to implement in practical scenarios. For example, in recommendation or education systems, once deployed, a policy usually needs to interact with the population of
users for a fair amount of time and generate a lot of data. Moreover, since policy preparation is
time-consuming (which is what motivates our work to begin with), it is practically difficult if not
impossible to change the policy immediately once collecting enough data for policy update, and it
will be a significant overhead compared to a short policy switch interval. Therefore, in applications
we target at, it is more reasonable to assume that the sample size in each deployment (i.e., between
policy switching) has the same order of magnitude and is large enough so that the overhead of policy
preparation can be ignored.

More importantly, on the technical side, previous theoretical works on low switching cost mostly use
deterministic policies in each deployment, which is easier to analyze. This issue also applies to the
work of Guo & Brunskill (2015) on concurrent PAC RL. However, if the agent can deploy stochastic
(and possibly non-Markov) policies (e.g., a mixture of deterministic policies), then intuitively—
and as reflected in our lower bounds—exploration can be done much more deployment-efficiently,
and we provide a stochastic policy algorithm that achieves an _OpHq deployment complexity and_
overcomes the ΩpdHq lower bounds for deterministic policy algorithms (Gao et al., 2021).

[r]

2 PRELIMINARIES

**Notation** Throughout our paper, for n P Z[`], we will denote rns “ t1, 2, ..., nu. r¨s denotes the
ceiling function. Unless otherwise specified, for vector x P R[d] and matrix X P R[d][ˆ][d], }x} denotes
the vector l2-norm of x and _X_ denotes the largest singular value of X. We will use standard
} }
big-oh notations Op¨q, Ωp¨q, Θp¨q, and notations such as _Op¨q to suppress logarithmic factors._

2.1 EPISODIC REINFORCEMENT LEARNING [r]

We consider an episodic Markov Decision Process denoted by M pS, A, H, P, rq, where S is the
state space, is the finite action space, H is the horizon length, and P _Ph_ _h_ 1 [and][ r][ “ t][r][h][u]h[H] 1
_A_ “ t u[H]“ “
denote the transition and the reward functions. At the beginning of each episode, the environment
will sample an initial state s1 from the initial state distribution d1. Then, for each time step h P rHs,
the agent selects an action ah, interacts with the environment, receives a reward rh _sh, ah_, and
transitions to the next state sh P A1. The episode will terminate once sH 1 is reached. p q
` `

A (Markov) policy πh at step h is a function mapping from ∆, where ∆ denotes
p¨q _S Ñ_ pAq pAq
the probability simplex over the action space. With a slight abuse of notation, when πh is a
p¨q
deterministic policy, we will assume πh : . A full (Markov) policy π _π1, π2, ..., πH_
p¨q _S Ñ A_ “ t u
specifies such a mapping for each time step. We use Vh[π][p][s][q][ and][ Q]h[π][p][s, a][q][ to denote the value function]

3Although the conversion from sub-linear regret to polynominal sample complexity is possible (“online-tobatch”), we show in Appendix A that to achieve accuracy ε after conversion, the number of deployments of
previous low-switching cost algorithms has dependence on ε, whereas our guarantee does not.


-----

and Q-function at step h P rHs, which are defined as:

_H_ _H_

_Vh[π][p][s][q “][ E][r]hÿ[1]“h_ _rh1psh1, ah1_ q|sh “ s, πs, _Q[π]h[p][s, a][q “][ E][r]hÿ[1]“h_ _rh1psh1, ah1_ q|sh “ s, ah “ a, πs

We also use Vh[˚][p¨q][ and][ Q]h[˚][p¨][,][ ¨q][ to denote the optimal value functions and use][ π][˚][ to denote the]
optimal policy that maximizes the expected return J _π_ : E _h_ 1 _[r][p][s][h][, a][h][q|][π][s][. In some occa-]_
p q “ r[ř][H]“
sions, we usefunction for disambiguation purposes. The optimal value functions and the optimal policy will be Vh[π][p][s][;][ r][q][ and][ Q]h[π][p][s, a][;][ r][q][ to denote the value functions with respect to][ r][ as the reward]
denoted by V [˚]ps; rq, Q[˚]ps, a; rq, πr[˚][, respectively.]

**Non-Markov Policies** While we focus on Markov policies in the above definition, some of our
results apply to or require more general forms of policies. For example, our lower bounds apply
to non-Markov policies that can depend on the history (e.g., 1 1 R... _h_ 1 _h_ 1
Rdeterministic Markov policies, which corresponds to choosing a deterministic policy from a given ˆ Sh Ñ A for deterministic policies); our algorithm for arbitrary policies deploys a mixture of S ˆ A ˆ ˆ S ´ ˆ A ´ ˆ
set at the initial state, and following that policy for the entire trajectory. This can be viewed as a
non-Markov stochastic policy.

2.2 LINEAR MDP SETTING

We mainly focus on the linear MDP (Jin et al., 2019) satisfying the following assumptions:

**Assumption A (Linear MDP Assumptions). An MDP M “ pS, A, H, P, rq is said to be a linear**
MDP with a feature map φ : S ˆ A Ñ R[d] if the following hold for any h P rHs:

-  There ares, a, s[1] _d unknown signed measures, Ph_ _s[1]_ _s, a_ _µh µsh[1] “ p, φ_ _s, aµ[p]h[1][q][, µ]._ _h[p][2][q][, ..., µ]h[p][d][q][q][ over][ S][ such that for any]_
p q P S ˆ A ˆ S p | q “ x p q p qy

-  There exists an unknown vector θh P R[d] such that for any ps, aq P S ˆA, rhps, aq “ xφps, aq, θhy.

Similar to Jin et al. (2019) and Wang et al. (2020b), without loss of generality, we assume for all
_s, a_ and h _H_, _φ_ _s, a_ 1, _µh_ ?d, and _θh_ ?d. In Section 3 we will
p q P S ˆ A P r s } p q} ď } } ď } } ď

refer to linear MDPs with stationary dynamics, which is a special case whenθ1 _θ2_ _. . ._ _θH_ . _µ1 “ µ2 “ . . . µH and_
“ “ “


2.3 A CONCRETE DEFINITION OF DE-RL

In the following, we introduce our formulation for DE-RL in linear MDPs. For discussions of
comparison to existing works, please refer to Section 1.1.

**Definition 2.1 (Deployment Complexity in Linear MDPs). We say that an algorithm has a deploy-**
ment complexity K in linear MDPs if the following holds: given an arbitrary linear MDP under
Assumption A, for arbitrary ε and 0 ă δ ă 1, the algorithm will return a policy πK after K deployments and collecting at most N trajectories in each deployment, under the following constraints:

(a) With probability 1 ´ δ, πK is ε-optimal, i.e. JpπKq ě maxπ Jpπq ´ ε.

(b) The sample size N is polynominal, i.e. N poly _d, H,_ [1]ε _[,][ log][ 1]δ_

a priori and cannot change adaptively from deployment to deployment. “ p [q][. Moreover,][ N][ should be fixed]

Under this definition, the goal of Deployment-Efficient RL is to design algorithms with provable
guarantees of low deployment complexity.

**Polynomial Size of N** We emphasize that the restriction of polynomially large N is crucial to our
formulation, and not including it can result in degenerate solutions. For example, if N is allowed to
be exponentially large, we can finish exploration in 1 deployment in the arbitrary policy setting, by
deploying a mixture of exponentially many policies that form an ε-net of the policy space. Alternatively, we can sample actions uniformly, and use importance sampling (Precup, 2000) to evaluate all
of them in an off-policy manner. None of these solutions are practically feasible and are excluded
by our restriction on N .


-----

3 LOWER BOUND FOR DEPLOYMENT COMPLEXITY IN RL

In this section, we provide information-theoretic lower bounds of the deployment complexity in our
DE-RL setting. We defer the lower bound construction and the proofs to Appendix B. As mentioned
in Section 2, we consider non-Markov policies when we refer to deterministic and stochastic policies
in this section, which strengthens our lower bounds as they apply to very general forms of policies.

We first study the algorithms which can only deploy deterministic policy at each deployment.
**Theorem 3.1. [Lower bound for deterministic policies, informal] For any d ě 4, H and any algo-**
_rithm ψ that can only deploy a deterministic policy at each deployment, there exists a linear MDP_
_M satisfying Assumption A, such that the deployment complexity of ψ in M is K “ ΩpdHq._

The basic idea of our construction and the proof is that, intuitively, a linear MDP with dimension
_d and horizon length H has ΩpdHq “independent directions”, while deterministic policies have_
limited exploration capacity and only reach Θp1q direction in each deployment, which result in
ΩpdHq deployments in the worst case.

In the next theorem, we will show that, even if the algorithm can use arbitrary exploration strategy
(e.g. maximizing entropy, adding reward bonus), without additional assumptions, the number of
deployments K still has to depend on H and may not be reduced to a constant when H is large.
**Theorem 3.2. [Lower bound for arbitrary policies, informal] For any d ě 4, H, N and any algo-**
_rithm ψ which can deploy arbitrary policies, there exists a linear MDP M satisfying Assumption A,_
_such that the deployment complexity of ψ in M is K_ Ω _H_ rlogd _NH_ s Ω _H_ _._
“ p { p q q “ p q

The origin of the difficulty can be illustrated by a recursive dilemma: in the worst case, if the agent

[r]

does not have enough information at layer h, then it cannot identify a good policy to explore till
layer h Ω logd _NH_ in 1 deployment, and so on and so forth. Given that we enforce N to
` p p qq
be polynomial, the agent can only push the “information boundary” forward by Ω logd _NH_
p p qq “
Ωp1q layers per deployment. In many real-world applications, such difficulty can indeed exist. For
example, in healthcare, the entire treatment is often divided into multiple stages. If the treatment in
stager _h is not effective, the patient may refuse to continue. This can result in insufficient samples_
for identifying a policy that performs well in stage h ` 1.

**Stationary vs. non-stationary dynamics** Since we consider non-stationary dynamics in Assump. A, one may suspect that the H-dependence in the lower bound is mainly due to such nonstationarity. We show that this is not quite the case, and the H-dependence still exists for stationary
dynamics. In fact, our lower bound for non-stationary dynamics directly imply one for stationary
dynamics: given a finite horizon non-stationary MDP _M “ pS, A, H,_ _P,_ _rq, we can construct a_
stationary MDP M “ pS, A, H, P, rq by expanding the state space to S “ _S ˆ rHs so that the_
new transition function P and reward function r are stationary across time steps. As a result, given[Ă] [r] [r] r
arbitrary d 4 and H 2, we can construct a hard non-stationary MDP instance[r] _M with dimen-_
ě ě
sion _d “ maxt4, d{Hu and horizon_ _h “ d{d[r] “ mintH, d{4u, and convert it to a stationary MDP_
_M with dimension d and horizon h_ _h_ min _H, d_ 4 _H. If there exists an algorithm which[Ă]_
“ “ t { u ď
can solve[r] _M in K deployments, then it can be used to solve[r]_ _M in no more than K deployments._
Therefore, the lower bounds for stationary MDPs can be extended from Theorems 3.1 and 3.2, as[r]
shown in the following corollary:

[Ă]
**Corollary 3.3 (Extension to Stationary MDPs). For stationary linear MDP with d ě 4 and H ě 2,**
_suppose N_ poly _d, H,_ [1]ε _[,][ log][ 1]δ_
“ p [q][, the lower bound of deployment complexity would be]min _d_ 4,H [ Ω][p][d][q][ for]

_deterministic policy algorithms, and Ωp_ rlogmaxttd{{H,4u NHu s [q “][ r]Ωpmintd, Huq for algorithms which

_can deploy arbitrary policies._

As we can see, the dependence on dimension and horizon will not be eliminated even if we make a
stronger assumption that the MDP is stationary. The intuition is that, although the transition function
is stationary, some states may not be reachable from the initial state distribution within a small
number of times, so the stationary MDP can effectively have a “layered” structure. For example, in
Atari games (Bellemare et al., 2013) (where many algorithms like DQN (Mnih et al., 2013) model
the environments as infinite-horizon discounted MDPs) such as Breakout, the agent cannot observe


-----

states where most of the bricks are knocked out at the initial stage of the trajectory. Therefore,
the agent still can only push forward the “information frontier” a few steps per deployment. That
said, it is possible reduce the deployment complexity lower bound in stationary MDPs by adding
more assumptions, such as the initial state distribution providing good coverage over the entire state
space, or all the states are reachable in the first few time steps. However, because these assumptions
do not always hold and may overly trivialize the exploration problem, we will not consider them
in our algorithm design. Besides, although our algorithms in the next section are designed for nonstationary MDPs, they can be extended to stationary MDPs by sharing covariance matrices, and we
believe the analyses can also be extended to match the lower bound in Corollary 3.3.

4 TOWARDS OPTIMAL DEPLOYMENT EFFICIENCY

In this section we provide algorithms with deployment-efficiency guarantees that nearly match the
lower bounds established in Section 3. Although our lower bound results in Section 3 consider nonMarkov policies, our algorithms in this section only use Markov policies (or a mixture of Markov
policies, in the arbitrary policy setting), which are simpler to implement and compute and are already
near-optimal in deployment efficiency.

**Inspiration from Lower Bounds: a Layer-by-Layer Exploration Strategy The linear depen-**
dence on H in the lower bounds implies a possibly deployment-efficient manner to explore, which
we call a layer-by-layer strategy: conditioning on sufficient exploration in previous h ´ 1 time
steps, we can use polypdq deployments to sufficiently explore the h-th time step, then we only need
_H ¨ polypdq deployments to explore the entire MDP. If we can reduce the deployment cost in each_
layer from polypdq to Θpdq or even Θp1q, then we can achieve the optimal deployment efficiency.
Besides, as another motivation, in Appendix C.4, we will briefly discuss the additional benefits of
the layer-by-layer strategy, which will be useful especially in “Safe DE-RL”. In Sections 4.1 and
4.2, we will introduce algorithms based on this idea and provide theoretical guarantees.

4.1 DEPLOYMENT-EFFICIENT RL WITH DETERMINISTIC POLICIES

**Algorithm 1: Layer-by-Layer Batch Exploration Strategy for Linear MDPs Given Reward Func-**
tion

**1 Inputfor some: Failure probability cβ** 0, total number of deployments δ ą 0, and target accuracy K, batch size ε ą 0, β N Ð, cβ ¨ dH logpdHδ[´][1]ε[´][1]q

**32 for h1 Ð k “ 1 1, 2, ..., K ą// hk denotes the layer to explore in iteration do** _k, for all k P rKas_

**4** _Q[k]hk_ 1[p¨][,][ ¨q Ð][ 0][ and][ V][ k]hk 1[p¨q “][ 0]
` `

**5** **for h “ hk, hk ´ 1, ...,N 1 do**

**6** Λ[k]h _τ_ 1 _n_ 1 _[φ]h[τn]_ _h_ _u[k]h[p¨][,][ ¨q Ð][ min][t][β]_ [¨] _φ_ _,_ Λ[k]h[q][´][1][φ][p¨][,][ ¨q][, H][u]

[Ð][ I] [`][ř][k][´]“[1] “ _N_ [p][φ][τn][q][J][,] p¨ ¨q[J]p

**7** _wh[k]_ _h[q][´][1][ ř]ř[k]τ_ [´][1]1 _n_ 1 _[φ]h[τn]_ _h_ 1[p][s][τn]h 1[q] b

**8** _Q[k]h[p¨][Ð p][,][ ¨q Ð][Λ][k][ min][tp][w]“h[k][q][J][φ]“[p¨][,][ ¨q `][ r][¨][ V][h][p¨][ k]`[,][ ¨q `][ u]`[k]h[p¨][,][ ¨q][, H][u][ and][ V][ k]h_ _h[p¨][, a][q]_

ř

**9** _πh[k][p¨q Ð][ arg max][a][P][A][ Q][k]h[p¨][, a][q]_ [p¨q “][ max][a][P][A][ Q][k]

**10** **end**

**11** Define π[k] _π1[k]_ 2 _[...][ ˝][ π]h[k]k_ _k[`][1:][H][s]_

**12** **for n “ 1, ..., N“** **do[˝][ π][k]** [˝][ unif][r][h]

**13** Receive initial state s[kn]1 _d1_
„

**1514** **endfor h “ 1, 2, ..., H do Take action a[kn]h** [Ð][ π]h[k][p][s][kn]h [q][ and observe][ s]h[kn]`1 [„][ P][h][p][s]h[k][, a][k]h[q][ ;]

**16** Compute ∆k [2]N[β] _Nn_ 1 _hhk_ 1 _φ_ _s[kn]h_ _[, a]h[kn]_ _h[q][´][1][φ][p][s][kn]h_ _[, a]h[kn]_
Ð “ “ p [q][J][p][Λ][k] [q][.]

**17** **if ∆k ě** _[εh]2H[k]_ **[then][ h]ř[k][`][1][ Ð]ř[ h][k][ ;]** b

**1819** **else ifelse h hk** _k “1_ _H h then returnk_ 1 ; _π[k]_ ;

**20 end** ` Ð `


-----

In this sub-section, we focus on the setting where each deployed policy is deterministic. In Alg 1,
we propose a provably deployment-efficient algorithm built on Least-Square Value Iteration with
UCB (Jin et al., 2019)[4] and the “layer-by-layer” strategy. Briefly speaking, at deployment k, we
focus on exploration in previous hk layers, and compute π1[k][, π]2[k][, ..., π]h[k]k [by running LSVI-UCB in]
an MDP truncated at step hk. After that, we deploy π[k] to collect N trajectories, and complete the
trajectory after time step hk with an arbitrary policy. (In the pseudocode we choose uniform, but the
choice is inconsequential.) In line 19, we compute ∆k with samples and use it to judge whether we
should move on to the next layer till all H layers have been explored. The theoretical guarantee is
listed below, and the missing proofs are deferred to Appendix C.
**Theorem 4.1 (Deployment Complexity). For arbitrary ε, δ** 0, and arbitrary cK 2, as long as

_N_ _c_ _cK [H]_ [4][cK]ε[2][ `][cK][1][d][3][cK] log[2][c][K] _[Hd]δε_ _cK1 ´1, where c is an absolute constant, by choosing ą_ ě
ě p [q]
´ ¯

_K_ _cKdH_ 1. (1)
“ `

_Algorithm 1 will terminate at iteration k ď K and return us a policy π[k], and with probability 1 ´ δ,_
Es1„d1 rV1[˚][p][s][1][q ´][ V][ π]1 _[k]_ ps1qs ď ε.

As an interesting observation, Eq (1) reflects the trade-off between the magnitude of K and N
when K is small. To see this, when we increase cK and keep it at the constant level, K definitely
increases while N will be lower because its dependence on d, H, ε, δ decreases. Moreover, the
benefit of increasing cK is only remarkable when cK is small (e.g. we have N “ OpH [9]d[6]ε[´][4]q if
_cK_ 2, while N _O_ _H_ [5]d[3][.][6]ε[´][2][.][4] if cK 6), and even for moderately large cK, the value of
“ “ p q “
_Nwhether the trade-off in Eq.1 is exact or not, and we leave it for the future work. quickly approaches the limit limcK_ Ñ8 N “ c _[H]ε[4][2][d][3]_ log[2]p _[Hd]δε_ [q][. It is still an open problem that]

Another key step in proving the deployment efficiency of Alg. 1 is Lem. 4.2 below. In fact, by
directly applying Lem. 4.2 to LSVI-UCB (Jin et al., 2019) with large batch sizes, we can achieve
_OpdHq deployment complexity in deterministic policy setting without exploring in a layer-by-layer_
manner. We defer the discussion and the additional benefit of layer-by-layer strategy to Appx. C.4.
**Lemma 4.2. [Batched Finite Sample Elliptical Potential Lemma] Consider a sequence of matrices**
**A0, AN** _, ..., A_ _K_ 1 _N_ R[d][ˆ][d] _with A0_ _Id_ _d and AkN_ **A** _k_ 1 _N_ Φk 1, where Φk 1
_kNt_ _k_ 1 _N_ 1 _[φ]p_ _[t][φ]´t[J]_ q[and] P[ max][t][ď][KN] “ ˆ “ p _k´_ q _K `_ _Tr´A[´]k[1]_ 1 _N_ [Φ][k][´]´[1][q ě] “
“p ´ q ` [}][φ][t][} ď][ 1][. We define:][ K][`][ :][“] P r s p p ´ q

_Nεř_ _._ _For arbitrary ε_ 1, and arbitrary cK 2, if K _c!_ _KdH_ ˇˇ 1, by choosing N
ă1 ě “ `ˇ ě

_c_ _c)K [Hd]ε[cK][cK]_ [log][c][K] [p][ Hd]ε _cK ´1, where c is an absolute constant independent with cK, d, H, ε, we_

[q]

_have´_ _cKd_ _K¯H._
|K[`]| ď ă {

**Extension to Reward-free setting** Based on the similar methodology, we can design algorithms
for reward-free setting (Wang et al., 2020b) and obtain OpdHq deployment complexity. We defer
the algorithms and proofs to Appx. D, and summarize the main result in Thm. D.4.

4.2 DEPLOYMENT-EFFICIENT RL WITH ARBITRARY POLICIES

From the discussion of lower bounds in Section 3, we know that in order to reduce the deployment
complexity from ΩpdHq to ΩpHq, we have to utilize stochastic (and possibly non-Markov) policies
and try to explore as many different directions as possible in each deployment (as opposed to 1
direction in Algorithm 1). The key challenge is to find a stochastic policy—before the deployment

[r]
starts—which can sufficiently explore d independent directions.

In Alg. 2, we overcome this difficulty by a new covariance matrix estimation method (Alg. 6 in
Appx. E). The basic idea is that, for arbitrary policy π [5], the covariance matrix Λ[π]h [:][“][ E][π][r][φφ][J][s][ can]

4In order to align with the algorithm in reward-free setting, slightly different from (Jin et al., 2019) but
similar to (Wang et al., 2020b), we run linear regression on PhVh instead of Qh.
5Here we mainly focus on evaluating deterministic policy or stochastic policy mixed from a finite number of
deterministic policies, because for the other stochastic policies, exactly computing the expectation over policy
distribution may be intractable.


-----

**Algorithm 2: Deployment-Efficient RL with Covariance Matrix Estimation**


**1 Input: Accuracy level ε; Iteration number imax; Resolution ε0; Reward r; Bonus coefficient β.**

**2 for h “ 1, 2, ..., H do**

**34** Initializefor i “ 1 π, 2h,, ..., i1 with an arbitrary deterministic policy ;max do Σh,1 “ 2I, Πh “ tu.

**5** Λ[π]h[h,i] Ð EstimateCovMatrixph, Dr1:h´1s, Σr1:h´[r]1s, πh,iq # Alg 6, Appx E

**6** Σp _h,i`1 “_ Σh,i ` Λ[π]h[h,i]

**87** **ifVrh,i Vh,i`1, ¯1πh,i[r] 3`ν1min[2] Ð[p][{] SolveOptQ[8][ then][ break ;]ph, Dr1:h´1s, Σr1:h´1s, β,** Σh,i`1, ε0q # Alg 5, Appx E

**109** **endΠh “ Π`** _h ď_ tπ¯h,i`1u [r]

**1112** Σforh “ n “ I, 1 D, 2h, ..., N “ tuŤ, do πh,mix :“ unifpΠhq

**13** Sample trajectories with πh,mix

**1514** **endΣh “ Σh ` φpsh,n, ah,nqφpsh,n, ah,nq[J],** _Dh “ Dh_ tsh,n, ah,n, rh,n, sh`1,nu

Ť

**16 end**

**17 return pπr Ð Alg 4pH, tD1, ..., DH** u, rq

be estimated element-wise by running policy evaluation for π with φiφj as a reward function, where
_i, j P rds and φi denotes the i-th component of vector φ._

However, a new challenge emerging is that, because the transition is stochastic, in order to guarantee
low evaluation error for all possible policies ¯πh,i`1, we need an union bound over all policies to be
evaluated, which is challenging if the policy class is infinite. To overcome this issue, we discretize
the value functions in Algorithm 5 (see Appendix E) to allow for a union bound over the policy
space: after computing the Q-function by LSVI-UCB, before converting it to a greedy policy, we
first project it to an ε0-net of the entire Q-function class. In this way, the number of policy candidates
is finite and the projection error can be controlled as long as ε0 is small enough.

Using the above techniques, in Lines 3-10, we repeatedly use Alg 6 to estimate the accumulative
covariance matrix Σh,i 1 and further eliminate uncertainty by calling Alg 5 to find a policy (ap`
proximately) maximizing uncertainty-based reward function _R :“ }φ}Σ[´]h,i[1]_ `1 [. For each][ h][ P r][H][s][,]
inductively conditioning on sufficient exploration in previous[r] _h_ 1 layers, the errors of Alg 6 and
´ r
Alg 5 will be small, and we will find a finite set of policies Π[r]h to cover all dimensions in layer h.
(This is similar to the notion of “policy cover” in Du et al. (2019); Agarwal et al. (2020a).) Then,
layer h can be explored sufficiently by deploying a uniform mixture of Π and choosing N large
enough (Lines 11-15). Also note that the algorithm does not use the reward information, and is
essentially a reward-free exploration algorithm. After exploring all H layers, we obtain a dataset
_D1, ..., DH_ and can use Alg 4 for planning with any given reward function r satisfying Assump. A
t u
to obtain a near-optimal policy.

**Deployment complexity guarantees** We first introduce a quantity denoted as νmin, which measures the reachability to each dimension in the linear MDP. In Appendix E.8, we will show that the
_νmin is no less than the “explorability” coefficient in Definition 2 of Zanette et al. (2020) and νmin[2]_
is also lower bounded by the maximum of the smallest singular value of matrix Eπrφφ[J]s.
**Definition 4.3 (Reachability Coefficient).**


Eπ _φ[J]h_ _[θ][q][2][s][ ;]_ _νmin_ min
rp “ _hPrHs_ _[ν][h][ .]_


_νh :_ min
“ _θ_ 1 [max]π
} }“


Now, we are ready to state the main theorem of this section, and defer the formal version and its
proofs to Appendix E. Our algorithm is effectively running reward-free exploration and therefore
our results hold for arbitrary linear reward functions.
**Theorem 4.4. [Informal] For arbitrary 0** _ε, δ_ 1, with proper choices of imax, ε0, β, we can

1 ă ă

_choose N “ polypd, H,_ [1]ε _[,][ log][ 1]δ_ _[,]_ _νmin_ [q][, such that, after][ K][ “][ H][ deployments, with probability][ 1][´][δ][,]


-----

_Algorithm 2 will collect a dataset D_ _D1, ..., DH_ _, and if we run Alg 4 with D and arbitrary_
_reward function satisfying Assump. A, we will obtain “ t_ _πur such that V1πr_ 1

[p] [p][s][1][;][ r][q ě][ V][ ˚][p][s][1][;][ r][q ´][ ε][.]

**Proof Sketch** Next, we briefly discuss the key steps of the proof. Since p _ε0 can be chosen to be_
very small, we will ignore the bias induced by ε0 when providing intuitions. Our proof is based on
the induction condition below. We first assume it holds after h ´ 1 deployments (which is true when
_h “ 1), and then we try to prove at the h-th deployment we can explore layer h well enough so that_
the condition holds for h.
**Condition 4.5. [Induction Condition] Suppose after h ´ 1 deployments, we have the following**
induction condition for some ξ ă 1{d, which will be determined later:

maxπ Eπr[ř][h]h[´]“1[1] _φpsh[, a]h[r]_ [q][J][Σ][´]h [1][φ][p][s]h[r] _[, a]h[r]_ [qs ď][ h]H[´][1] _[ξ.]_ (2)

b

r r r

The l.h.s. of Eq.(2) measures the uncertainty in previous h ´ 1 layers after exploration. As a result,
with high probability, the following estimations will be accurate:

Λ[π][h,i] Eπh,i _φ_ _sh, ah_ _φ_ _sh, ah_ _,_ _O_ _ξ_ _,_ (3)
}[p] ´ r p q p q[J]s}8 8 ď p q

where _,_ denotes the entry-wise maximum norm. This directly implies that:
} ¨ }8 8

}Σ[r] _h,i`1 ´ Σh,i`1s}8,8 ď i ¨ Opξq._

where Σh,i`1 :“ 2I ` _i[1]“1_ [E][π]h,i[1] [r][φ][p][s][h][, a][h][q][φ][p][s][h][, a][h][q][J][s][ is the target value for][ r]Σh,i`1 to approx
imate. Besides, recall that in Algorithm 5, we use _φ[J]Σ[r]_ [´]h,i[1] 1[φ][ as the reward function, and the]

[ř][i] `

induction condition also implies that: b

|Vh,i`1 ´ maxπ Eπr}φpsh, ahq}Σ[´]h,i[1] `1 [s| ď][O][p][ξ][q][.]

As a result, if ξ and the resolution ε0 are small enough, ¯πr _h,i_ 1 would gradually reduce the uncer`
tainty and Vh,i`1 (also maxπ Eπr}φpsh, ahq}Σ[´]h,i[1] `1 [s][) will decrease. However, the bias is at the level]

_O_ _ξ_, and therefore, no matter how small ξ is, as long as ξ 0, it is still possible that the policies
p q r ą
in Πh do not cover all directions if some directions are very difficult to reach, and the error due
to such a bias will be at the same level of the required accuracy in induction condition, i.e. Opξq.
This is exactly where the “reachability coefficient” νmin definition helps. The introduction of νmin
provides a threshold, and as long as ξ is small enough so that the bias is lower than the threshold,
each dimension will be reached with substantial probability when the breaking criterion in Line 9 is
satisfied. As a result, by deploying unif Πh and collecting a sufficiently large dataset, the induction
p q
condition will hold till layer H. Finally, combining the guarantee of Alg 4, we complete the proof.

5 CONCLUSION AND FUTURE WORK

In this paper, we propose a concrete theoretical formulation for DE-RL to fill the gap between existing RL literatures and real-world applications with deployment constraints. Based on our framework, we establish lower bounds for deployment complexity in linear MDPs, and provide novel
algorithms and techniques to achieve optimal deployment efficiency. Besides, our formulation is
flexible and can serve as building blocks for other practically relevant settings related to DE-RL. We
conclude the paper with two such examples, defer a more detailed discussion to Appendix F, and
leave the investigation to future work.

**Sample-Efficient DE-RL** In our basic formulation in Definition 2.1, we focus on minimizing the
deployment complexity K and put very mild constraints on the per-deployment sample complexity
_N_ . In practice, however, the latter is also an important consideration, and we may face additional
constraints on how large N can be, as they can be upper bounded by e.g. the number of customers
or patients our system is serving.

**Safe DE-RL** In real-world applications, safety is also an important criterion. The definition for
safety criterion in Safe DE-RL is still an open problem, but we believe it is an interesting setting
since it implies a trade-off between exploration and exploitation in deployment-efficient setting.


-----

ACKNOWLEDGEMENTS

JH’s research activities on this work were completed by December 2021 during his internship at
MSRA. NJ acknowledges funding support from ARL Cooperative Agreement W911NF-17-2-0196,
NSF IIS-2112471, and Adobe Data Science Research Award.

REFERENCES

Yasin Abbasi-yadkori, D´avid P´al, and Csaba Szepesv´ari. Improved algorithms for linear stochastic
bandits. In Advances in Neural Information Processing Systems, volume 24. Curran Associates,
Inc., 2011.

M Mehdi Afsar, Trafford Crump, and Behrouz Far. Reinforcement learning based recommender
systems: A survey. arXiv preprint arXiv:2101.06286, 2021.

Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pc-pg: Policy cover directed exploration for provable policy gradient learning. arXiv preprint arXiv:2007.08459, 2020a.

Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps, 2020b.

Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds for randomized
least-squares value iteration. In Proceedings of the AAAI Conference on Artificial Intelligence,
volume 35, pp. 6566–6573, 2021.

Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret
bounds. In Advances in Neural Information Processing Systems, pp. 1184–1194, 2017.

Andr´as Antos, Csaba Szepesv´ari, and R´emi Munos. Learning near-optimal policies with bellmanresidual minimization based fitted policy iteration and a single sample path. Machine Learning,
71(1):89–129, 2008.

M. G. Azar, Ian Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In
_ICML, 2017._

Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low
switching cost, 2020.

Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:
253–279, 2013.

Marc G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi
Munos. Unifying count-based exploration and intrinsic motivation, 2016.

Abdellah Bennane et al. Adaptive educational software by applying reinforcement learning. Infor_matics in Education-An International Journal, 12(1):13–27, 2013._

Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network
distillation, 2018.

Andres Campero, Roberta Raileanu, Heinrich K¨uttler, Joshua B Tenenbaum, Tim Rockt¨aschel,
and Edward Grefenstette. Learning with amigo: Adversarially motivated intrinsic goals. arXiv
_preprint arXiv:2006.12122, 2020._

Alexandra Carpentier, Claire Vernade, and Yasin Abbasi-Yadkori. The elliptical potential lemma
revisited, 2020.

Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning.
In International Conference on Machine Learning, pp. 1042–1051. PMLR, 2019.

Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E
Schapire. On oracle-efficient pac rl with rich observations. _Advances in neural information_
_processing systems, 31, 2018._


-----

Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford.
Provably efficient rl with rich observations via latent state decoding. In International Conference
_on Machine Learning, pp. 1665–1674. PMLR, 2019._

Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: a
new approach for hard-exploration problems. arXiv preprint arXiv:1901.10995, 2019.

Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for
batched bandits, 2020.

Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning,
2021.

Minbo Gao, Tianle Xie, Simon S. Du, and Lin F. Yang. A provably efficient algorithm for linear
markov decision process with low switching cost, 2021.

Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched
neural bandits, 2021.

Zhaohan Guo and Emma Brunskill. Concurrent pac rl. In Proceedings of the AAAI Conference on
_Artificial Intelligence, volume 29, 2015._

Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W. Glynn, and Yinyu Ye.
Sequential batch learning in finite-action linear contextual bandits, 2020.

Elad Hazan, Sham M. Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum
entropy exploration, 2019.

Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds
on planning horizon. In Conference On Learning Theory, pp. 3395–3398. PMLR, 2018.

Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In
_International Conference on Machine Learning, pp. 652–661. PMLR, 2016._

Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference
_on Machine Learning, pp. 1704–1713. PMLR, 2017a._

Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In Doina Precup and Yee Whye
Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70,
pp. 1704–1713, 2017b.

Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I. Jordan. Is q-learning provably efficient?, 2018.

Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement
learning with linear function approximation, 2019.

Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for
reinforcement learning, 2020.

Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl
problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems,
34, 2021a.

Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In
_International Conference on Machine Learning, pp. 5084–5096. PMLR, 2021b._

Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The
_International Journal of Robotics Research, 32(11):1238–1274, 2013._

Dingwen Kong, R. Salakhutdinov, Ruosong Wang, and Lin F. Yang. Online sub-sampling for reinforcement learning with general function approximation. ArXiv, abs/2106.07203, 2021.


-----

Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich
observations. Advances in Neural Information Processing Systems, 29:1840–1848, 2016.

Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline
reinforcement learning. arXiv preprint arXiv:2006.04779, 2020.

Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with
baseline bootstrapping. In International Conference on Machine Learning, pp. 3652–3661.
PMLR, 2019.

Jongmin Lee, Wonseok Jeon, Byung-Jun Lee, Joelle Pineau, and Kee-Eung Kim. Optidice:
Offline policy optimization via stationary distribution correction estimation. _arXiv preprint_
_arXiv:2106.10783, 2021._

Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinitehorizon off-policy estimation. arXiv preprint arXiv:1810.12429, 2018.

Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off-policy
reinforcement learning without great exploration. Advances in Neural Information Processing
_Systems, 33:1264–1274, 2020._

Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofir Nachum, and Shixiang Gu. Deploymentefficient reinforcement learning via model-based offline optimization. In International Confer_[ence on Learning Representations, 2021. URL https://openreview.net/forum?id=](https://openreview.net/forum?id=3hGNqpI4WS)_
[3hGNqpI4WS.](https://openreview.net/forum?id=3hGNqpI4WS)

Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In International confer_ence on machine learning, pp. 6961–6971. PMLR, 2020._

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. _arXiv preprint_
_arXiv:1312.5602, 2013._

Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free
representation learning and exploration in low-rank mdps. _arXiv preprint arXiv:2102.07035,_
2021.

Ted Moskovitz, Jack Parker-Holder, Aldo Pacchiano, Michael Arbel, and Michael I. Jordan. Tactical
optimism and pessimism for deep reinforcement learning, 2021.

R´emi Munos and Csaba Szepesv´ari. Finite-time bounds for fitted value iteration. Journal of Machine
_Learning Research, 9(5), 2008._

Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice:
Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02074, 2019.

Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine. Awac: Accelerating online reinforcement learning with offline datasets, 2021.

Karl Pertsch, Youngwoon Lee, and Joseph J Lim. Accelerating reinforcement learning with learned
skill priors. arXiv preprint arXiv:2010.11944, 2020.

Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department
_Faculty Publication Series, pp. 80, 2000._

Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distributional optimal design, 2021.

Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic
exploration. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger
(eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc.,
2013.


-----

Joel A. Tropp. An introduction to matrix concentration inequalities, 2015.

Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for offpolicy evaluation. In International Conference on Machine Learning, pp. 9659–9668. PMLR,
2020.

Ruosong Wang, Simon S. Du, Lin F. Yang, and Sham M. Kakade. Is long horizon reinforcement
learning more difficult than short horizon reinforcement learning?, 2020a.

Ruosong Wang, Simon S. Du, Lin F. Yang, and Ruslan Salakhutdinov. On reward-free reinforcement
learning with linear function approximation, 2020b.

Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang. Reinforcement learning with general
value function approximation: Provably efficient approach via bounded eluder dimension. arXiv
_preprint arXiv:2005.10804, 2020c._

Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent
pessimism for offline reinforcement learning. arXiv preprint arXiv:2106.06926, 2021a.

Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging
sample-efficient offline and online reinforcement learning, 2021b.

Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via
the regularized lagrangian. arXiv preprint arXiv:2007.03438, 2020.

Chao Yu, Jiming Liu, and Shamim Nemati. Reinforcement learning in healthcare: A survey. arXiv
_preprint arXiv:1908.08796, 2019._

Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea
Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. _arXiv preprint_
_arXiv:2005.13239, 2020._

Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement
learning without domain knowledge using value function bounds. In International Conference on
_Machine Learning, pp. 7304–7312. PMLR, 2019._

Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill. Provably efficient
reward-agnostic navigation with linear value iteration. arXiv preprint arXiv:2008.07737, 2020.

Tianjun Zhang, Paria Rashidinejad, Jiantao Jiao, Yuandong Tian, Joseph Gonzalez, and Stuart
Russell. Made: Exploration via maximizing deviation from explored regions. arXiv preprint
_arXiv:2106.10268, 2021._


-----

