TOWARDS DEPLOYMENT-EFFICIENT REINFORCEMENT LEARNING: LOWER BOUND AND OPTIMALITY
Year: 2022

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.

text: 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.

heading: 1 INTRODUCTION
text: 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 deploymentsK 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 MDPs1 (Jin et al., 2019) and develop the essential theory. The main questions we address are:

heading: Q1: What is the optimum of the deployment efficiency in our DE-RL setting?
text: 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 rΩ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 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 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 rΩ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) 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 .

heading: 1.1 CLOSELY RELATED WORKS
text: 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 deployments3. 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 rOpHq deployment complexity and overcomes the ΩpdHq lower bounds for deterministic policy algorithms (Gao et al., 2021).

heading: 2 PRELIMINARIES
text: 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 Rd and matrix X P Rdˆ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 rOp¨q to suppress logarithmic factors.

heading: 2.1 EPISODIC REINFORCEMENT LEARNING
text: We consider an episodic Markov Decision Process denoted by MpS,A, H, P, rq, where S is the state space, A is the finite action space,H is the horizon length, and P “ tPhuHh“1 and r “ trhuHh“1 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 P A, interacts with the environment, receives a reward rhpsh, ahq, and transitions to the next state sh`1. The episode will terminate once sH`1 is reached.
A (Markov) policy πhp¨q at step h is a function mapping from S Ñ ∆pAq, where ∆pAq denotes the probability simplex over the action space. With a slight abuse of notation, when πhp¨q is a deterministic policy, we will assume πhp¨q : S Ñ A. A full (Markov) policy π “ tπ1, π2, ..., πHu specifies such a mapping for each time step. We use V πh psq andQπhps, aq 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:
V πh psq “ Er H ÿ
h1“h rh1psh1 , ah1q|sh “ s, πs, Qπhps, aq “ Er
H ÿ
h1“h rh1psh1 , ah1q|sh “ s, ah “ a, πs
We also use V ˚h p¨q and Q˚hp¨, ¨q to denote the optimal value functions and use π˚ to denote the optimal policy that maximizes the expected return Jpπq :“ Er
řH h“1 rpsh, ahq|πs. In some occa-
sions, we use V πh ps; rq and Qπhps, a; rq to denote the value functions with respect to r as the reward function for disambiguation purposes. The optimal value functions and the optimal policy will be 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., S1 ˆ A1 ˆ R... ˆ Sh´1 ˆ Ah´1 ˆ R ˆ Sh Ñ A for deterministic policies); our algorithm for arbitrary policies deploys a mixture of deterministic Markov policies, which corresponds to choosing a deterministic policy from a given set at the initial state, and following that policy for the entire trajectory. This can be viewed as a non-Markov stochastic policy.

heading: 2.2 LINEAR MDP SETTING
text: 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Ñ Rd if the following hold for any h P rHs:
• There are d unknown signed measures µh “ pµp1qh , µ p2q h , ..., µ pdq h q over S such that for any
ps, a, s1q P S ˆAˆ S, Phps1|s, aq “ xµhps1q, φps, aqy. • There exists an unknown vector θh P Rd 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 ps, aq P S ˆ A and h P rHs, }φps, aq} ď 1, }µh} ď ? d, and }θh} ď ? d. In Section 3 we will refer to linear MDPs with stationary dynamics, which is a special case when µ1 “ µ2 “ . . . µH and θ1 “ θ2 “ . . . “ θH .

heading: 2.3 A CONCRETE DEFINITION OF DE-RL
text: 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 deployment 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 “ polypd,H, 1ε , log 1 δ q. Moreover, N should be fixed
a priori and cannot change adaptively from deployment to deployment.
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 .

heading: 3 LOWER BOUND FOR DEPLOYMENT COMPLEXITY IN RL
text: 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 algorithm ψ 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 algorithm ψ which can deploy arbitrary policies, there exists a linear MDP M satisfying Assumption A, such that the deployment complexity of ψ in M is K “ ΩpH{rlogdpNHqsq “ rΩpHq.
The origin of the difficulty can be illustrated by a recursive dilemma: in the worst case, if the agent does not have enough information at layer h, then it cannot identify a good policy to explore layer h ` ΩplogdpNHqq in 1 deployment, and so on and so forth. Given that we enforce N to be polynomial, the agent can only push the “information boundary” forward by ΩplogdpNHqq “ rΩ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 stage 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 “ p rS,A, H, rP , rq, we can construct a stationary MDP M “ pS,A, H, P, rq by expanding the state space to S “ rS ˆ rHs so that the new transition function P and reward function r are stationary across time steps. As a result, given arbitrary d ě 4 and H ě 2, we can construct a hard non-stationary MDP instance ĂM with dimension rd “ maxt4, d{Hu and horizon rh “ d{rd “ mintH, d{4u, and convert it to a stationary MDP M with dimension d and horizon h “ rh “ mintH, d{4u ď H . If there exists an algorithm which can solve M in K deployments, then it can be used to solve Ă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 shown in the following corollary: Corollary 3.3 (Extension to Stationary MDPs). For stationary linear MDP with d ě 4 and H ě 2, suppose N “ polypd,H, 1ε , log 1 δ q, the lower bound of deployment complexity would be Ωpdq for deterministic policy algorithms, and Ωp mintd{4,Hurlogmaxtd{H,4uNHs 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.

heading: 4 TOWARDS OPTIMAL DEPLOYMENT EFFICIENCY
text: 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 dependence 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.

heading: 4.1 DEPLOYMENT-EFFICIENT RL WITH DETERMINISTIC POLICIES
text: Algorithm 1: Layer-by-Layer Batch Exploration Strategy for Linear MDPs Given Reward Function
1 Input: Failure probability δ ą 0, and target accuracy ε ą 0, β Ð cβ ¨ dH a logpdHδ´1ε´1q for some cβ ą 0, total number of deployments K, batch size N , 2 h1 Ð 1 // hk denotes the layer to explore in iteration k, for all k P rKs 3 for k “ 1, 2, ...,K do 4 Qkhk`1p¨, ¨q Ð 0 and V k hk`1p¨q “ 0 5 for h “ hk, hk ´ 1, ..., 1 do 6 Λkh Ð I` řk τ“1 řN n“1 φ τn h pφτnh qJ, ukhp¨, ¨q Ð mintβ ¨ b
φp¨, ¨qJpΛkhq´1φp¨, ¨q, Hu 7 wkh Ð pΛkhq´1 řk´1 τ“1 řN n“1 φ τn h ¨ V kh`1psτnh`1q 8 Qkhp¨, ¨q Ð mintpwkhqJφp¨, ¨q ` rhp¨, ¨q ` ukhp¨, ¨q, Hu and V kh p¨q “ maxaPAQkhp¨, aq 9 πkhp¨q Ð arg maxaPAQkhp¨, aq
10 end 11 Define πk “ πk1 ˝ πk2 ... ˝ πkhk ˝ unifrhk`1:Hs 12 for n “ 1, ..., N do 13 Receive initial state skn1 „ d1 14 for h “ 1, 2, ...,H do Take action aknh Ð πkhpsknh q and observe sknh`1 „ Phpskh, akhq ; 15 end
16 Compute ∆k Ð 2βN řN n“1 řhk h“1
b
φpsknh , aknh qJpΛkhq´1φpsknh , aknh q. 17 if ∆k ě εhk2H then hk`1 Ð hk ; 18 else if hk “ H then return πk ; 19 else hk`1 Ð hk ` 1 ; 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 πk1 , π k 2 , ..., π k hk
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 H4cK`1d3cK ε2cK log2cK pHdδε q ¯ 1 cK´1 , where c is an absolute constant, by choosing
K “ cKdH ` 1. (1)
Algorithm 1 will terminate at iteration k ď K and return us a policy πk, and with probability 1´ δ, Es1„d1rV ˚1 ps1q ´ V π k 1 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 “ OpH9d6ε´4q if cK “ 2, while N “ OpH5d3.6ε´2.4q if cK “ 6), and even for moderately large cK , the value of N quickly approaches the limit limcKÑ8N “ cH 4d3 ε2 log 2pHdδε q.
Another key step in proving the deployment efficiency of Algorithm 1 is Lemma 4.2 below. In Appendix C, we will discuss the possibility of applying this technique to LSVI-UCB (Jin et al., 2019) with large batch sizes, and the additional benefit of our layer-by-layer strategy. Lemma 4.2. [Finite Sample Elliptical Potential Lemma] Consider a sequence of matrices A0,AN , ...,ApK´1qN P Rdˆd with A0 “ Idˆd and AkN “ Apk´1qN ` Φk´1, where Φk´1 “ řkN t“pk´1qN`1 φtφ J t and maxtďKN }φt} ď 1. We define: K` :“ ! k P rKs ˇ ˇ ˇ TrpA´1pk´1qNΦk´1q ě Nε ) . For arbitrary ε ă 1, and arbitrary cK ě 2, if K “ cKdH ` 1, by choosing N ě
c ´ cK HdcK εcK log cK pHdε q ¯ 1 cK´1 , where c is an absolute constant independent with cK , d,H, ε, we have |K`| ď cKd ă K{H.
Extension to Reward-free setting Based on the similar methodology, we can design algorithms for reward-free setting (Wang et al., 2020b) and obtain guarantees for deployment complexity based on Lemma 4.2. We defer the algorithms and proofs to Appendix D, and summarize the main result in Theorem D.4

heading: 4.2 DEPLOYMENT-EFFICIENT RL WITH ARBITRARY POLICIES
text: From the discussion of lower bounds in Section 3, we know that in order to reduce the deployment complexity from ΩpdHq to rΩ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 starts—which can sufficiently explore d independent directions.
In Algorithm 2, we overcome this difficulty by a new covariance matrix estimation method (Algorithm 6 in Appendix E). The basic idea is that, for arbitrary policy π 5, the covariance matrix Λπh :“ Eπrφpsh, ahqφpsh, ahqJs can be estimated element-wise by running policy evaluation for
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 determnistic 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 3 Initialize πh,1 with an arbitrary deterministic policy ; rΣh,1 “ 2I , Πh “ tu. 4 for i “ 1, 2, ..., imax do 5 pΛ
πh,i h Ð EstimateCovMatrixph,Dr1:h´1s,Σr1:h´1s, πh,iq # Alg 6, Appx E
6 rΣh,i`1 “ rΣh,i ` pΛ πh,i h 7 Vh,i`1, π̄h,i`1 Ð SolveOptQph,Dr1:h´1s,Σr1:h´1s, β, rΣh,i`1, ε0q # Alg 5, Appx E 8 if Vh,i`1 ď 3ν2min{8 then break ; 9 Πh “ Πh Ť
tπ̄h,i`1u 10 end 11 Σh “ I , Dh “ tu, πh,mix :“ unifpΠhq 12 for n “ 1, 2, ..., N do 13 Sample trajectories with πh,mix 14 Σh “ Σh ` φpsh,n, ah,nqφpsh,n, ah,nqJ, Dh “ Dh Ť
tsh,n, ah,n, rh,n, sh`1,nu 15 end 16 end 17 return pπr Ð Alg 4pH, tD1, ..., DHu, rq
π with φipsh, ahqφjpsh, ahq as a reward function, where i, j P rds and φip¨, ¨q denotes the i-th component of vector φp¨, ¨q. 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 rΣh,i`1 and further eliminate uncertainty by calling Alg 5 to find a policy (approximately) maximizing uncertainty-based reward function rR :“ }φ}
rΣ´1h,i`1 . For each h P rHs,
inductively conditioning on sufficient exploration in previous h ´ 1 layers, the errors of Alg 6 and Alg 5 will be small, and we will find a finite set of policies Π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 tD1, ..., DHu and can use Alg 4 for planning with any given reward function r satisfying Assump. A 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 ν2min is also lower bounded by the maximum of the smallest singular value of matrix EπrφφJs. Definition 4.3 (Reachability Coefficient).
νh :“ min }θ}“1 max π
b
EπrpφJh θq2s ; νmin “ min hPrHs νh .
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 chooseN “ polypd,H, 1ε , log 1 δ , 1 νmin q, such that, afterK “ H deployments, with probability 1´δ,
Algorithm 2 will collect a dataset D “ tD1, ..., DHu, and if we run Alg 4 with D and arbitrary reward function satisfying Assump. A, we will obtain pπr such that V pπr1 ps1; rq ě V ˚1 ps1; rq ´ ε.
Proof Sketch Next, we briefly discuss the key steps of the proof. Since ε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´1
rh“1
b
φps rh, arhqJΣ ´1 rh φps rh, arhqs ď h´1 H ξ. (2)
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:
}pΛπh,i ´ Eπh,irφpsh, ahqφpsh, ahqJs}8,8 ď Opξq, (3)
where } ¨ }8,8 denotes the entry-wise maximum norm. This directly implies that:
}rΣh,i`1 ´ Σh,i`1s}8,8 ď i ¨Opξq.
where Σh,i`1 :“ 2I ` ři i1“1 Eπh,i1 rφpsh, ahqφpsh, ahq Js is the target value for rΣh,i`1 to approximate. Besides, recall that in Algorithm 5, we use b
φJrΣ´1h,i`1φ as the reward function, and the induction condition also implies that:
|Vh,i`1 ´max π Eπr}φpsh, ahq}rΣ´1h,i`1s| ďOpξq.
As a result, if ξ and the resolution ε0 are small enough, π̄h,i`1 would gradually reduce the uncertainty and Vh,i`1 (also maxπ Eπr}φpsh, ahq}rΣ´1h,i`1s) will decrease. However, the bias is at the level Opξq, and therefore, no matter how small ξ is, as long as ξ ą 0, it is still possible that the policies 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 unifpΠhq and collecting a sufficiently large dataset, the induction condition will hold till layer H . Finally, combining the guarantee of Alg 4, we complete the proof.

heading: 5 CONCLUSION AND FUTURE WORK
text: 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.

heading: ACKNOWLEDGEMENTS
text: 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.

heading: A EXTENDED RELATED WORK
text: Online RL Online RL is a paradigm focusing on the challenge of strategic exploration. On the theoretical side, based on the “Optimism in Face of Uncertainty”(OFU) principle or posterior sampling techniques, many provable algorithms have been developed for tabular MDPs (Jin et al., 2018; Azar et al., 2017; Zanette & Brunskill, 2019; Agrawal & Jia, 2017; Agrawal et al., 2021), linear MDPs (Jin et al., 2019; Agarwal et al., 2020a), general function approximation (Wang et al., 2020c; Russo & Van Roy, 2013), or MDPs with structural assumptions (Jiang et al., 2017b; Du et al., 2019). Moreover, there is another stream of work studying how to guide exploration by utilizing state occupancy (Hazan et al., 2019; Zhang et al., 2021). Beyond the learning in MDPs with pre-specified reward function, recently, Jin et al. (2020); Wang et al. (2020b); Zanette et al. (2020) provide algorithms for exploration in the scenarios where multiple reward functions are of interest. On the practical side, there are empirical algorithms such as intrinsically-motivated exploration (Bellemare et al., 2016; Campero et al., 2020), exploration with hand-crafted reward bonus (RND) (Burda et al., 2018), and other more sophisticated strategies (Ecoffet et al., 2019). However, all of these exploration methods do not take deployment efficiency into consideration, and will fail to sufficiently explore the MDP and learn near-optimal policies in DE-RL setting where the number of deployments is very limited.
Offline RL Different from the online setting, where the agents are encouraged to explore rarely visited states to identify the optimal policy, the pure offline RL setting serves as a framework for utilizing historical data to learn a good policy without further interacting with the environment. Therefore, the core problem of offline RL is the performance guarantee of the deployed policy, which motivated multiple importance-sampling based off-policy policy evaluation and optimization methods (Jiang & Li, 2016; Liu et al., 2018; Uehara et al., 2020; Yang et al., 2020; Nachum et al., 2019; Lee et al., 2021), and the “Pessimism in Face of Uncertainty” framework (Liu et al., 2020; Kumar et al., 2020; Fujimoto & Gu, 2021; Yu et al., 2020; Jin et al., 2021b; Xie et al., 2021a) in contrast with OFU in online exploration setting. However, as suggested in Matsushima et al. (2021), pure offline RL can be regarded as constraining the total number of deployments to be 1.
Bridging Online and Offline RL; Trade-off between Pessimism and Optimism As pointed out by Xie et al. (2021b); Matsushima et al. (2021), there is a clear gap between existing online and offline RL settings, and some efforts have been made towards bridging them. For example, Nair et al. (2021); Pertsch et al. (2020); Bai et al. (2020) studied how to leverage pre-collected offline datasets to learn a good prior to accelerate the online learning process. Moskovitz et al. (2021) proposed a learning framework which can switch between optimism and pessimism by modeling the selection as a bandit problem. None of these works give provable guarantees in our deployment-efficiency setting.
Conversion from Linear Regret in Gao et al. (2021) to Sample Complexity Gao et al. (2021) proposed an algorithm with the following guarantee: after interacting with the environments for rK times (we use rK to distinguish with K in our setting), there exists a constant c such that the algorithm’s regret is
ĂK ÿ k“1 V ˚ps1q ´ V πkps1q “ c ¨ a d3H4 rK ¨ ι “ c ¨ ? d3H3T ¨ ι
where we denote T “ rKH , and use ι to refer to the log terms. Besides, in π1, ..., πK there are only OpdH log rKq policy switching. As discussed in Section 3.1 by Jin et al. (2018), such a result can be convert to a PAC guarantee that, by uniformly randomly select a policy π from π1, ..., πK , with probability at least 2/3, we should have:
V ˚ps1q ´ V πps1q “ rOp c d3H5
T q “ rOp
d
d3H4
rK q
In order to make sure the upper bound in the r.h.s. will be ε, we need:
rK “ d 3H4
ε2
and the required policy switching would be:
OpdH log rKq “ OpdH log dH ε q
In contrast with our results in Section 4.1, there is an additional logarithmic dependence on d,H and ε. Moreover, since their algorithm only deploys deterministic policies, their deployment complexity has to depend on d, which is much higher than our stochastic policy algorithms in Section 4.2 when d is large.
Investigation on Trade-off between Sample Complexity and Deployment Complexity In Table 1, we compare our algorithms and previous online RL works which did not consider deployment efficiency to shed light on the trade-off between sample and deployment complexities. Besides algorithms that are specialized to linear MDPs, we also include results such as Zanette et al. (2020), which studied a more general linear approximation setting and can be adapted to our setting. As stated in Def. 2 of Zanette et al. (2020), they also rely on some reachability assumption. To avoid ambiguity, we use rνmin to refer to their reachability coefficient (as discussed in Appx E.8, rνmin is no larger than and can be much smaller than our νmin). Because they also assume that ε ď rOprνmin{ ? dq (see Thm 4.1 in their paper), their results have an implicit dependence on rν´2min. In addition, by using the class of linear functions w.r.t. φ, Q-type OLIVE (Jiang et al., 2017a; Jin et al., 2021a) has rOpd 3H6
ε2 q sample complexity and OpdH logp1{εqq deployment complexity. Its deployment complexity is close to our deterministic algorithm, but with additional dependence on ε. We also want to highlight that OLIVE is known to be computationally intractable (Dann et al., 2018), while our algorithms are computationally efficient. With the given feature φ in linear MDPs and additional reachability assumption (not comparable to us), we can use a simplified version of MOFFLE (Modi et al., 2021) by skipping their LearnRep subroutine. Though this version of MOFFLE is computationally efficient and its deployment complexity does not depend on ε, it has much worse sample complexity (ηmin is their reachability coefficient) and deployment complexity. On the other hand, PCID (Du et al., 2019) and HOMER (Misra et al., 2020) achieve H deployment
complexity in block MDPs. However, block MDPs are more restricted than linear MDPs and these algorithms have worse sample and computational complexities.
It is worth to note that all our algorithms achieve the optimal dependence on ε (i.e., ε´2) in sample complexity. For algorithms that deploy deterministic policies, we can see that our algorithm has higher dependence on d and H in the sample complexity in both reward-known and reward-free setting, while our deployment complexity is much lower. Our stochastic policy algorithm (last row) is naturally a reward-free algorithm. Comparing with Wang et al. (2020b) and Zanette et al. (2020), our sample complexity has higher dependence on d and the reachability coefficient νmin, while our algorithm achieves the optimal deployment complexity and better dependence on H .

heading: B ON THE LOWER BOUND OF DEPLOYMENT-EFFICIENT REINFORCEMENT LEARNING

heading: B.1 A HARD MDP INSTANCE TEMPLATE
text: In this sub-section, we first introduce a hard MDP template that is used in further proofs. As shown in Figure 1, we construct a tabular MDP (which is a special case of linear MDP) where the horizon length is H`1 and in each layer except the first one, there are d`2 states and 2d`1 different state action pairs. The initial state is fixed as s0 and there are d` 2 different actions. It is easy to see that we can represent the MDP by linear features with at most 2d` 1 dimensions, and construct reward and transition function satisfying Assumption A. As a result, it is a linear MDP with dimension 2d ` 1 and horizon length H ` 1. Since there is only a constant-level blow up of dimension, the dimension of these MDPs is still Θpdq, and we will directly use d instead of Θpdq in the rest of the proof. The states in each layer h ě 1 can be divided into three groups and we introduce them one-by-one in the following.
Group 1: Absorbing States (Green Color) The first group G1h “ tu1h, u2hu consists of two absorbing states u1h and u 2 h, which can only take one action at each state ā 1 h and ā 2 h and transit to u1h`1 and u 2 h`1 with probability 1, respectively. The reward function is defined as rhpu1h, ā1hq “ rhpu2h, ā2hq “ 0.5 for all h ď H ´ 2 and rHpu1H , ā1Hq “ 0.0, rHpu2H , ā2Hq “ 1.0.
Group 2: Core States (Red Color) The second group G2h “ ts˚hu only contains one state, which we call it core state and denote it as s˚h. For example, in Figure 1, we have s ˚ 1 “ sd1, s˚2 “ s12 and s˚3 “ s23. In the “core state”, the agent can take d actions ra1h,ra2h, . . . ,radh and transit deterministically to s1h`1, s 2 h`1, . . . , s d h`1. Besides, the reward function is rhps˚h,raihq “ 0.5 for all i P rds.
Group 3: Normal States (Blue Color) The third group G3h “ tsih|i P rds, sih ‰ s˚hu is what we call “normal states”, and each state sih P G3h can only take one action raih and will transit randomly to one of the absorbing states in the next layer, i.e. G1h`1. Besides, the reward function is rhpsih,raihq “ 0.5 for arbitrary sih P G3h, and the transition function is P pu1h`1|sih,raihq “ P pu1h`1|sih,raihq “ 0.5, except for a state action pair s# :“ si#h# , a # :“ ai#h# at layer h # P rH ´ 1s with index i#, such that s# R G2h# and P pu 1 h`1|si # h# , a i# h#q “ 0.5 ´ ε and P pu 2 h`1|si # h# , a i#
h#q “ 0.5 ` ε. In the following, we will call s#, a# the “optimal state” and “optimal action” in this MDP. Note that the “optimal state” can not be the core state.
We will use Mph#, i#, Icore “ ti1, i2, ..., iHuq with ih# ‰ i# to denote the MDP whose optimal state is at layer h# and indexed by i#, and the core states in each layer are si1h , s i2 h , ..., s iH H . As we can see, the only optimal policy should be the one which can generate the following sequence of states before transiting to absorb states at layer h# ` 1:
s0, s i1 1 , s i2 2 , ..., s i h#´1 h#´1 , s i# h#
and the optimal value function would be 12H`ε. In order to achieve ε-optimal policy, the algorithm should identify si #
h# , which is the main origin of the difficulty in exploration. Remark B.1 (Markov v.s. Non-Markov Policies). As we can see, the core states in each layer are the only states with #actions ą 1, and for each core state, there exists and only exists one
deterministic path (a sequence of states, actions and rewards) from initial state to it, which implies that for arbitrary non-Markov policy, there exists an equivalent Markov policy. Therefore, in the rest of the proofs in this section, we only focus on Markov policies.

heading: B.2 LOWER BOUND FOR ALGORITHMS WHICH CAN DEPLOY DETERMINISTIC POLICIES ONLY
text: In the following, we will state the formal version of the lower bound theorem for deterministic policy setting and its proof. The intuition of the proof is that we can construct a hard instance, which can be regarded as a ΩpdHq multi-arm bandit problem, and we will show that in expectation the algorithm need to “pull ΩpdHq arms” before identifying the optimal one. Theorem B.2 (Lower bound for number of deployments in deterministic policy setting). For the linear MDP problem with dimension d and horizon H , given arbitrary algorithm ψ (ψ can be deterministic or stochastic), which can only deploy a deterministic policy but can collect arbitrary
number of samples in each deployment, there exists a MDP problem where the optimal deterministic policy π˚ is ε better than all the other deterministic policies, but the estimate policy pπ (which is also a deterministic policy) of the best policy output by ψ after K deployments must have P pπ˚ ‰ pπq ě 1{10 unless the number of deployments K ą pd´ 1qpH ´ 1q{2 “ ΩpdHq.
Proof. First of all, we introduce how we construct hard instances.
Construction of Hard Instances We consider a set of MDPs M̄, where for each MDP in that set, the core states (red color) in each layer are fixed to be s11, s 1 2, ..., s 1 H´1 and the only optimal states which has different probability to transit to absorbing states are randomly selected from pd´1qpH´ 1q normal states (blue color). Easy to see that, |M̄| “ pd´ 1qpH ´ 1q. Because of the different position of optimal states, the optimal policies for each MDP in M̄ (i.e. the policy which can transit from s0 to optimal state) is different. We will use π1, π2, ..., πpd´1qpH´1q to refer to those different policies and use Mπi with 1 ď i ď pd ´ 1qpH ´ 1q to denote the MDP in M̄ where πi is the optimal policy. For convenience, we will use M0 to denote the MDP where all the normal states have equal probability to transit to different absorbing states, i.e., all states are optimal states. Based on the introduction above, we define M :“ M̄ Ť
tM0u and use the MDPs in M as hard instances.
Lower Bound for Average Failure Probability Next, we try to lower bound the average failure probability, which works as a lower bound for the maximal failure probability among MDPs in M. Since any randomized algorithm is just a distribution over deterministic ones, and it therefore suffices to only consider deterministic algorithms ψ (Krishnamurthy et al., 2016).
Given an arbitrary algorithm ψ and k P rKs, we use ψpkq to denote the policy taken by ψ at the k-th deployment (which is a random variable). Besides, we denote ψpK ` 1q as the output policy. For arbitrary k P rKs, we use PMπi ,ψpψpkq “ πjq with 1 ď i, j ď pd ´ 1qpH ´ 1q to denote the probability that ψ takes policy πj at deployment k when running ψ onMπi , and use PMπi ,ψpψpK` 1q “ πiq to denote the probability that the algorithm ψ returns policy πi as optimal arm after running with K deployments under MDP Mπi . We are interested in providing an upper bound for the expected success rate:
Pψ,M„Mpsuccessq :“ 1 |M|P psuccess in M0q ` 1 |M|
|M̄| ÿ i“1 PMπi ,ψpψpK ` 1q “ πiq
“ 1|M| ` 1 |M|
|M̄| ÿ i“1 PMπi ,ψpψpK ` 1q “ πiq,
where we assume that all the policies in M0 are optimal policies.
In the following, we use Ek,πi to denote the event that the policy πi has been deployed at least once in the first k deployments and PMπj ,ψp¨q to denote the probability of an event when running algorithm ψ under MDP Mπj .
Next, we prove that, for arbitrary Mπi ,
PMπi ,ψpE A k,πiq “ PM0,ψpE A k,πiq @k P rK ` 1s. (4)
First of all, it holds for k “ 1, because at the beginning ψ has’t observe any data, and all its possible behavior should be the same in both M0 and Mi, and therefore PMπi ,ψpE A 1,πiq “ PM0,ψpE A 1,πiq. Next, we do induction. Suppose we already know it holds for 1, 2, ..., k, then consider the case for k ` 1. Because ψ behave the same if the pre-collected episodes are the same, which is the only information it will use for decision, we should have:
PMπi ,ψpψpk ` 1q “ πi X E A k,πiq “
ÿ
τPψpk`1q“πiXEAk,πi
PMπi ,ψpτq
“ ÿ
τPψpk`1q“πiXEAk,πi
PM0,ψpτq
“PM0,ψpψpk ` 1q “ πi X EAk,πiq. (5)
The second equality is due to each trajectory τ P ψpk ` 1q “ πi X EAk,πi has the same probability under M0 and Mi by the construction. Notice that in this induction step, we only consider the trajectory with first pk` 1qN episodes because define the whole sample space and event only based on the first pk ` 1qN episodes. This implies that,
PMπi ,ψpE A k`1,πiq “PMπi ,ψpE A k,πiq ´ PMπi ,ψpψpk ` 1q “ πi X E A k,πiq
“PM0,ψpEAk,πiq ´ PM0,ψpψpk ` 1q “ πi X E A k,πiq “PM0,ψpEAk`1,πiq.
Now we are ready to bound the failure rate. Suppose K ă pd´ 1qpH ´ 1q{2 ă |M|{2, we have:
1
|M|
|M̄| ÿ
i“1
` PMπi ,ψpψpK ` 1q “ πiq ´ PM0,ψpψpK ` 1q “ πiq ˘
“ 1|M|
|M̄| ÿ
i“1
´ PMπi ,ψpψpK ` 1q “ πi X EK`1,πiq ´ PM0,ψpψpK ` 1q “ πi X EK`1,πiq ¯
` 1|M|
|M̄| ÿ
i“1
´
PMπi ,ψpψpK ` 1q “ πi X E A K`1,πiq ´ PM0,ψpψpK ` 1q “ πi X E A K`1,πiq
¯
“ 1|M|
|M̄| ÿ i“1 PMπi ,ψpEK`1,πiq ´ PMπi ,ψpψpK ` 1q “ πi|EK`1,πiq ´ PM0,ψpψpK ` 1q “ πi|EK`1,πiq ¯
(Eq.(5) and P pAXBq “ P pBqP pA|Bq)
ď 1|M|
|M̄| ÿ i“1 PMπi ,ψpEK`1,πiq
(PMπi ,ψpψpK ` 1q “ πi|EK`1,πiq ´ PM0,ψpψpK ` 1q “ πi|EK`1,πiq ď 1)
“ 1|M|
|M̄| ÿ i“1 PM0,ψpEK`1,πiq ( Eq. (4))
ď K|M|
where the last step is because:
1
|M|
|M̄| ÿ i“1 PM0,ψpEK`1,πiq
“ 1|M|
|M̄| ÿ i“1 EM0,ψr1tπi is selectedus
ď 1|M|
|M̄| ÿ i“1 EM0,ψr K`1 ÿ k“1 1tπi is selected at deployment kus
“ 1|M|EM0,ψr K`1 ÿ
k“1
|M̄| ÿ i“1 1tπi is selected at deployment kus
“K ` 1|M| (ψ deploy deterministic policy each time)
ď1 2
(Deployment time K ă |M|{2)
As a result,
1 |M| ` 1 |M|
|M̄| ÿ i“1 PMπi ,ψpψpK ` 1q “ πiq ď 1 |M| ` 1 |M| |M̄| ÿ i“1 PM0,ψpψpK ` 1q “ πiq ` 1 2 ď 2|M| ` 1 2 .
As long as d,H ě 3, we have |M| “ pd ´ 1qpH ´ 1q ` 1 ě 5 the failure rate will be higher than 1{10, which finishes the proof. ˝

heading: B.3 PROOF FOR LOWER BOUND IN ARBITRARY SETTING
text: In the following, we provide a formal statement of the lower bound theorem for the arbitrary policy setting and its proof.
Theorem B.3 (Lower bound for number of deployments in arbitrary setting). For the linear MDP problem with given dimension d ě 2 and horizon H ě 3, N “ polypd,H, 1ε , log 1 δ q, and arbitrary given algorithm ψ. Unless the number of deployments K ą H´22rlogdNHs “ ΩpH{ logdpNHqq “ rΩpHq, for any ε, there exists an MDP such that the output policy is not ε-optimal with probability at least 12e . Here ψ can be deterministic or stochastic. The algorithm can deploy arbitrary policy but can only collect N “ polypd,H, 1ε , log 1 δ q samples in each deployment.
Proof. Since any randomized algorithm is just a distribution over deterministic ones, it suffices to only consider deterministic algorithms ψ in the following proof (Krishnamurthy et al., 2016). The crucial part here is notice that a deployment means we have a fixed distribution (occupancy) over the state space and such distribution only depends on the prior information.
Construction of Hard Instances We have dH´2 ˆ d instances by enumerating the location of core state from level 1 to H ´ 2 and the optimal normal state at level H ´ 1. We assign spi`1q%dH´1 as the core state at level H ´ 1 if siH´1 is the optimal state. Notice that for this hard instance class, we only consider the case that the optimal state is in level H ´ 1. We use M to denote this hard instance class.
We make a few claims and later prove these claims and the theorem. We will use the notation Eipjq to denote the event that at least one state at level j is reached by the i-th deployment. Also we notice that in all the discussion an event is just a set of trajectories. For all related discussion, the state at level L does not include the state in the absorbing chain. In addition, we will use PM,ψ to denote the distribution of trajectories when executing algorithm ψ and uniformly taking an instance from the hard instance class.
Claim 1. Assume L ď H ´ 2. Then for any deterministic algorithm ψ, we have
PM,ψpE1pLqq ď N
dL´1 .
Claim 2. Assume L` L1 ď H ´ 2. We have that for any deterministic algorithm ψ,
PM,ψpEAkpL1 ` Lqq ě p1´ N dL´1 qP pEAk´1pL1qq.
Proof of Claim 1 By the nature of the deterministic algorithm, we know that for any deterministic algorithm ψ, the deployment is the same at the first time for all instances. The reason is that the agent hasn’t observed anything, so the deployed policy has to be the same.
Let ppi, j, hq denote the probability of the first deployment policy to choose action j at node i at level h under the first deployment policy. We know that ppi, j, hq for ψ is the same under all instances. Note that there is a one to one correspondence between an MDP in the hard instance class and the specified locations of core states in the layer 1, . . . ,H ´ 2 and the optimal state at level H ´ 1. Therefore, we can use pi1, . . . , iH´2, sH´1q to denote any instance in the hard instance class, where i1, . . . , iH´2 refers to the location of the core states and sH´1 refers to the location of the optimal state. From the construction, we know that for instance pi1, . . . , iH´2, sH´1q, to arrive at level sL
at level L, the path as to be s0, i1, . . . , iL´1, sL. Therefore the probability of a trajectory sampled from ψ to reach state sL is
pps0, i1, 0qppi1, i2, 1q . . . ppiL´2, iL´1, L´ 2qppiL´1, sL, L´ 1q. Here we use ppiL´1, sL, L ´ 1q denotes the probability of taking action at iL´1 to transit to sL and similarly for others. In the deployment, ψ draws N episodes, so the probability of executing ψ to reach any state sL at level L during the first deployment is no more than Npps0, i1, 0qppi1, i2, 1q . . . ppiL´2, iL´1, L´ 2qppiL´1, sL, L´ 1q. Calculating the sum over i1, . . . , iL´1 and sL gives us
ÿ
i1,i2,...,iL´1,sL
Npps0, i1, 0qppi1, i2, 1q . . . ppiL´2, iL´1, L´ 2qppiL´1, sL, L´ 1q
“N ÿ
i1
pps0, i1, 0q ÿ
i2
ppi1, i2, 1q . . . ÿ
iL´2
ppiL´3, iL´2, L´ 3q ÿ
iL´1
ppiL´2, iL´1, L´ 2q ÿ
sL
ppiL´1, sL, L´ 1q
“N ÿ
i1
pps0, i1, 0q ÿ
i2
ppi1, i2, 1q . . . ÿ
iL´2
ppiL´3, iL´2, L´ 3q ÿ
iL´1
ppiL´2, iL´1, L´ 2q
“N ÿ
i1
pps0, i1, 0q ÿ
i2
ppi1, i2, 1q . . . ÿ
iL´2
ppiL´3, iL´2, L´ 3q
“ . . . “N. (6)
Therefore we have the following equation about PM,ψpE1pLqq PM,ψpE1pLqq
“ 1|M| ÿ
iL,...,iH´2,sH´1
ÿ
i1,...,iL´1
PI“pi1,...,iH´1,sH´1q,ψpE1pLqq
ď 1 dH´1
ÿ
iL,...,iH´2,sH´1
ÿ
i1,...,iL´1,sL
Npps0, i1, 0qppi1, i2, 1q . . . ppiL´2, iL´1, L´ 2qppiL´1, sL, L´ 1q
“ 1 dH´1
ÿ
iL,...,iH´2,sH´1
N
“ N dL´1 .
Proof of Claim 2 Let τ denote any possible concatenation of the first kN episodes we get in the first k deployments. In this claim, it suffices to consider the kN episodes because the event EkpL1`LqXEAk´1pL1q only depends on the first kN episodes. Therefore the sample space and the event will be defined on any trajectory with kN episodes. For any τ , we know that ψ will output the k-th deployment policy solely based on the τ r0, k ´ 1s and this map is deterministic (we use τ ri, js to denote the iN ` 1 to jN episodes in τ ). In other words, ψ will map τ r0, k ´ 1s to a fixed policy ψpτ r0, k ´ 1sq to deploy at the k-th time. We have the following equation for any I PM
PI,ψpEkpL1 ` Lq X EAk´1pL1qq
“ ÿ
τPEkpL1`LqXEAk´1pL1q
PI,ψpτq
“ ÿ
τPEkpL1`LqXEAk´1pL1q
PI,ψpτ r0, k ´ 1sqPI,ψpτr0,k´1sqpτ rk ´ 1, ksq
“ ÿ
τ :τr0,k´1sPEAk´1pL1q,τ 1:τ 1r0,k´1s“τr0,k´1s and τ 1rk´1,ks hit level L 1 ` L
PI,ψpτ r0, k ´ 1sqPI,ψpτr0,k´1sqpτ 1rk ´ 1, ksq
“ ÿ
τ :τr0,k´1sPEAk´1pL1q
PI,ψpτ r0, k ´ 1sq ÿ
τ 1:τ 1r0,k´1s“τr0,k´1s and τ 1rk´1,ks hit level L1 ` L
PI,ψpτr0,k´1sqpτ 1rk ´ 1, ksq
Notice that this equality does not generally hold for probability distribution PM,ψ .
Then we fix τ r0, k ´ 1s, such that τ r0, k ´ 1s P EAk´1pL1q. We also fix pi1, . . . , iL1´1q, piL1`L, . . . , iH´2, sH´1q and consider two instances I1 “ pi1, . . . , iL1´1, i1L1 , . . . , i1L1`L´1, iL1`L, . . . , iH´2, sH´1q and I2 “ pi1, . . . , iL1´1, i2L1 , . . . , i2L1`L´1, iL1`L, . . . , iH´2, sH´1q. Therefore, we have that PI1,ψpτ r0, k ´ 1sq “ PI2,ψpτ r0, k ´ 1sq (from the construction of I1, I2 and the property of deterministic algorithm ψ). We use Ipi1, . . . , iL1´1, iL1`L, . . . , iH´2, sH´1q to denote the instance class that has fixed pi1, . . . , iL1´1q, piL1`L, . . . , iH´2, sH´1q, but different piL1 , . . . iL1`L´1q. In addition, we use Ipi1, . . . , iL1´1q to denote the instance class that has fixed pi1, . . . , iL1´1q, but different piL1 , . . . iL1`L´1q and piL1`L, . . . , iH´2, sH´1q. Since we have already fixed τ r0, k ´ 1s P EAk´1pL1q here, ψpτ r0, k ´ 1sq is also fixed (for all I P Ipi1, . . . , iL1´1, iL1`L, . . . , iH´2, sH´1q). Also notice that we are considering the probability of N episodes τ 1rk´1 : ks. Therefore, we can follow Claim 1 and define ppi, j, hq for 0 ď h ď L1`L´1, which represents the probability of choosing action j at node i at level h under the k-th deployment policy. In the k-th deployment, ψ draws N episodes, so the probability of executing ψ to reach any state sL1`L at level L1 ` L under instance I “ pi1, . . . , iH´2, sH´1q is
Npps0, i1, 0qppi1, i2, 1q . . . ppiL1`L´2, iL1`L´1, L1 ` L´ 2qppiL1`L´1, sL1`L, L1 ` L´ 1q ďNppiL1´1, iL1 , L1 ´ 1q . . . ppiL1`L´2, iL1`L´1, L1 ` L´ 2qppiL1`L´1, sL1`L, L1 ` L´ 1q.
Following the same step in Eq (6) by summing over iL1 , . . . , iL1`L´1 and sL1`L gives us ÿ
IPIpi1,...,iL1´1,iL1`L,...,iH´2,sH´1q
ÿ
τ 1:τ 1r0,k´1s“τr0,k´1s and τ 1rk´1,ks hit level L1 ` L
PI,ψpτr0,k´1sqpτ 1rk ´ 1, ksq
ďN.
Now, we sum over all possible piL1`L, . . . , iH´2, sH´1q and take the average. For any fixed τ r0, k´ 1s P EAk´1pL1q we have
1
|Ipi1, . . . , iL1´1q| ÿ
IPIpi1,...,iL1´1q
ÿ
τ 1:τ 1r0,k´1s“τr0,k´1s and τ 1rk´1,ks hit level L1 ` L
PI,ψpτr0,k´1sqpτ rk ´ 1, ksq
“ 1|Ipi1, . . . , iL1´1q| ÿ
iL1`L,...,iH´2,sH´1
ÿ
IPIpi1,...,iL1´1,iL1`L,...,iH´2,sH´1q ÿ
τ 1:τ 1r0,k´1s“τr0,k´1s and τ 1rk´1,ks hit level L1 ` L
PI,ψpτr0,k´1sqpτ rk ´ 1, ksq
ď 1|Ipi1, . . . , iL1´1q| ÿ
iL1`L,...,iH´2,sH´1
N
“d H´L1´L
dH´L1 N
“ 1 dL N.
Moreover, summing over all τ r0, k ´ 1s P EAk´1pL1q, gives us i1, . . . , iL1´1
PM,ψpEkpL1 ` Lq X EAk´1pL1qq
“ 1|M| ÿ
i1,...,iL1´1
ÿ
IPIpi1,...,iL1´1q
ÿ
τr0,k´1sPEAk´1pL1q
PI,ψpτ r0, k ´ 1sq
ÿ
τ 1:τ 1r0,k´1s“τr0,k´1s and τ 1rk´1,ks hit level L1 ` L
PI,ψpτr0,k´1sqpτ 1rk ´ 1, ksq
“ 1|M| ÿ
τr0,k´1sPEAk´1pL1q
ÿ
i1,...,iL1´1
Pi1,...,iL1´1,ψpτ r0, k ´ 1sq
ÿ
IPIpi1,...,iL1´1q
ÿ
τ 1:τ 1r0,k´1s“τr0,k´1s and τ 1rk´1,ks hit level L1 ` L
PI,ψpτr0,k´1sqpτ 1rk ´ 1, ksq
ď 1|M| ÿ
τr0,k´1sPEAk´1pL1q
ÿ
i1,...,iL1´1
Pi1,...,iL1´1,ψpτ r0, k ´ 1sq|Ipi1, . . . , iL1´1q| N
dL
“N dL |Ipi1, . . . , iL1´1q| |M| ÿ
τr0,k´1sPEAk´1pL1q
ÿ
i1,...,iL1´1
Pi1,...,iL1´1,ψpτ r0, k ´ 1sq
“N dL
ÿ
τr0,k´1sPEAk´1pL1q
PM,ψpτ r0, k ´ 1sq
“N dL PM,ψpEAk´1pL1qq.
In the second equality, we use Pi1,...,iL1´1,ψ because for any fixed τ r0, k ´ 1s P E A k´1pL1q and all I P Ipi1, . . . , iL1´1q, Pi1,...,iL1´1,ψ pτ r0, k ´ 1sq are the same.
Finally, we have
PM,ψpEAkpL1 ` Lqq ě PM,ψpEAkpL1 ` Lq X EAk´1pL1qq “ PM,ψpEAk´1pL1qq ´ PM,ψpEkpL1 ` Lq X EAk´1pL1qq
ě p1´ N dL qP pEAk´1pL1qq
ě p1´ N dL´1 qP pEAk´1pL1qq.
Proof of the Theorem If KL ď H ´ 2, then applying Claim 2 for K ´ 1 times and applying Claim 1 tells us
PM,ψpEAKpKLqq “PM,ψpEAKppK ´ 1qL` Lqq ě p1´ N dL´1 qP pEAK´1ppK ´ 1qLqq
ě . . . ě p1´ N dL´1 qK´1P pEA1pLqq ě p1´ N dL´1 qK .
We can set L “ rlogdNHs` 1 and K ď H´22rlogdNHs . Then for H ě 3, we get KL ď H ´ 2 and
PM,ψpdoes not hit any state at level H ´ 2q ě p1´ N
drlogdNHs q
H´2 2rlogd NHs
ě p1´ N NH q H´2 2rlogd NHs ě p1´ 1 H qH ě 1 e .
Let event F denote the event (a set of length KN episodes trajectories) that any state at level H ´ 2 is not hit. Then we have PM,ψpF q ě 1 ´ 1e . We use Ipi1, . . . , iH´2q to denote the instance class that has fixed core states pi1, . . . , iH´2q but different optimal states sH´1. Consider any fixed τ P F . Similar as the proof in the prior claims, by the property of deterministic algorithm, we can define ppi, j, hq for h “ H ´ 2, which represents the probability of the output policy ψτ pK ` 1q under trajectory τ to choose action j at node i at level H ´ 2. Then we have
ÿ
I“pi1,...,iH´2,sH´1qPIpi1,...,iH´2q PI,ψpψτ pK ` 1q chooses optimal state)
“ ÿ
I“pi1,...,iH´2,sH´1qPIpi1,...,iH´2q PI,ψppψτ pK ` 1qqpiH´2q “ sH´1q
“ ÿ
I“pi1,...,iH´2,sH´1qPIpi1,...,iH´2q ppiH´2, sH´1, H ´ 2q
“ ÿ
sH´1
ppiH´2, sH´1, H ´ 2q
“1.
Summing over τ P F gives us ÿ
I“pi1,...,iH´2,sH´1qPIpi1,...,iH´2q PI,ψpF X the output policy chooses optimal stateq
“ ÿ
I“pi1,...,iH´2,sH´1qPIpi1,...,iH´2q
ÿ τPF PI,ψpτqPI,ψpψτ pK ` 1q chooses optimal state)
“ ÿ
I“pi1,...,iH´2,sH´1qPIpi1,...,iH´2q
ÿ τPF Pi1,...,iH´2,ψpτqPI,ψpψτ pK ` 1q chooses optimal state)
“ ÿ
τPF Pi1,...,iH´2,ψpτq
ÿ
I“pi1,...,iH´2,sH´1qPIpi1,...,iH´2q PI,ψpψτ pK ` 1q chooses optimal state)
“ ÿ
τPF Pi1,...,iH´2,ψpτq
“Pi1,...,iH´2,ψpF q.
In the second equality, we notice that for all instance I P I “ pi1, . . . , iH´2, sH´1q, PI,ψpτq are the same, so this probability distribution essentially depends on i1, . . . , iH´2. In the third inequality, we change the order of the summation.
Finally, summing over i1, . . . , iH´2 and taking average yields that
PM,ψpF X the output policy chooses optimal stateq
“ 1 dH´1
ÿ
i1,...,iH´2
ÿ
I“pi1,...,iH´2,sH´1qPIpi1,...,iH´2q PI,ψpF X the output policy chooses optimal stateq
“ 1 dH´1
ÿ
i1,...,iH´2
Pi1,...,iH´2,ψpF q
“ 1 dH´1
ÿ
i1,...,iH´2
1
d
ÿ
sH´1
PI“pi1,...,iH´2,sH´1q,ψpF q
(PI,ψpF q does not depend on the optimal state)
“1 d PM,ψpF q
Therefore, we get the probability of not choosing the optimal state is
PM,ψp the output policy does not choose the optimal stateq ěPM,ψpF X the output policy does not choose the optimal stateq “PM,ψpF q ´ PM,ψpF X the output policy chooses the optimal stateq
“d´ 1 d PM,ψpF q ě1 2 ¨ 1 e .
From the construction, we know that any policy that does not choose optimal state (thus also does not choose the optimal action associated with the optimal state) is ε sub-optimal. This implies that with probability at least 12e , the output policy is at least ε sub-optimal. ˝

heading: C DEPLOYMENT-EFFICIENT RL WITH DETERMINISTIC POLICIES AND GIVEN REWARD FUNCTION

heading: C.1 ADDITIONAL NOTATIONS
text: In the appendix, we will frequently consider the MDP truncated at rh ď H , and we will use:
V πh ps|rhq “ Er rh ÿ
h1“h rh1psh1 , ah1q|sh “ s, πs, Qπhps, a|rhq “ Er
rh ÿ
h1“h rh1psh1 , ah1q|sh “ s, ah “ a, πs
to denote the value function in truncated MDP for arbitrary h ď rh, and also extend the definition in Section 2 to V ˚h p¨|rhq, Q˚hp¨, ¨|rhq, π˚|rh for optimal policy setting and V ˚ h p¨, r|rhq, Q˚hp¨, ¨, r|rhq, π˚r|h for reward-free setting.

heading: C.2 AUXILIARY LEMMA
text: Lemma C.1 (Elliptical Potential Lemma; Lemma 26 of Agarwal et al. (2020b)). Consider a sequence of d ˆ d positive semi-definite matrices X1, ..., XT with maxt TrpXtq ď 1 and define M0 “ λI, ...,Mt “Mt´1 `Xt. Then
T ÿ t“1 TrpXtM´1t´1q ď p1` 1{λqd logp1` T {dq.
Lemma C.2 (Abbasi-yadkori et al. (2011)). Suppose A,B P Rdˆd are two positive definite matrices satisfying A ľ B, then for any x P Rd, we have:
}x}2A ď }x}2B detpAq detpBq .
Next, we prove a lemma to bridge between trace and determinant, which is crucial to prove our key technique in Lemma 4.2. Lemma C.3. [Bridge between Trace and Determinant] Consider a sequence of matrices A0,AN , ...,ApK´1qN with A0 “ I and AkN “ Apk´1qN ` Φk´1, where Φk´1 “ řkN t“pk´1qN`1 φtφ J t . We have
TrpA´1pk´1qNΦk´1q ď detpAkN q
detpApk´1qN q log detpAkN q detpApk´1qN q .
Proof. Consider a more general case, given matrix Y ľ I , we have the following inequality
TrpI´Y´1q ď log detpYq ď TrpY ´ Iq.
By replacing Y with I`A´1X in the above inequality, we have:
TrppA`Xq´1Xq “TrppI`A´1Xq´1pA´1Xqq “ TrppI`A´1Xq´1pI`A´1X´ Iq “TrpI´ pI`A´1Xq´1q
ď log detpI`A´1Xq “ log detpA`Xq detpAq .
By assigning A “ Apk´1qN and X “ Φk´1, and applying Lemma C.2, we have:
TrpA´1pk´1qNΦk´1q “ kN ÿ
t“pk´1qN`1 }φt}2A´1pk´1qN
ď kN ÿ
t“pk´1qN`1 }φt}2A´1kN detAkN detpApk´1qN q
“TrpA´1kNΦk´1q detAkN
detpApk´1qN q
ď detAkN detpApk´1qN q log detAkN detpApk´1qN q
which finished the proof. ˝ Lemma 4.2. [Finite Sample Elliptical Potential Lemma] Consider a sequence of matrices A0,AN , ...,ApK´1qN P Rdˆd with A0 “ Idˆd and AkN “ Apk´1qN ` Φk´1, where Φk´1 “ řkN t“pk´1qN`1 φtφ J t and maxtďKN }φt} ď 1. We define: K` :“ ! k P rKs ˇ ˇ ˇ TrpA´1pk´1qNΦk´1q ě Nε ) . For arbitrary ε ă 1, and arbitrary cK ě 2, if K “ cKdH ` 1, by choosing N ě
c ´ cK HdcK εcK log cK pHdε q ¯ 1 cK´1 , where c is an absolute constant independent with cK , d,H, ε, we have |K`| ď cKd ă K{H.
Proof. Suppose we have TrpA´1pk´1qNΦk´1q ě Nε, by applying Lemma C.3 we must have:
Nε ď detpAkN q detpApk´1qN q log detpAkN q detpApk´1qN q ď detpAkN q detpApk´1qN q logpdetpAkN qq
ďd detpAkN q detpApk´1qN q logp1`KN{dq (detpAq ď pTrpAq{dqd)
which implies that,
Nε d logp1`KN{dq ď detpAkN q
detpApk´1qN q
Therefore,
|K`| log Nε d logp1`KN{dq ď ÿ
kPK log detpAkN q detpApk´1qN q ď K ÿ k“1 log detpAkN q detpApk´1qN q
“ log detpAKN q detpA0q ď d logp1`KN{dq
which implies that, conditioning on N ě dε logp1`KN{dq, we have:
|K`| ď d logp1`KN{dq logp Nεd logp1`KN{dq q
Now, we are interested in find the mimimum N , under the constraint that |K`| ď cKd. To solve this problem, we first choose an arbitrary p ď cK , and find a N such that,
logp1`KN{dq logp Nεd logp1`KN{dq q ď p
In order to guarantee the above, we need:
Nε ě d logp1`KN{dq, p Nε d logp1`KN{dq q p ě 1`KN{d
The first constraint can be satisfied easily with N ě c1 dε log dH ε for some constant c1. Since usually KN{d ą 1, the second constraint can be directly satisfied if:
p Nε d logp1`KN{dq q p ě 2KN{d
Recall K “ cKdH ` 1, it can be satisfied by choosing
N ě c2 ´ cK Hdp εp logppHd ε q ¯ 1 p´1
(7)
where c2 is an absolute constant. Therefore, we can find an absolute number c such that,
N “ c ´ cK Hdp εp logppHd ε q ¯ 1 p´1 ě maxtc1 d ε logpd ε q, c2 ´ cK Hdp εp logppHd ε q ¯ 1 p´1 u
to make sure that
|K`| ď pd
Since in Eq.(7), it’s required that 1{pp ´ 1q ă 8, we should constraint that p ą 1 and therefore, cK ě 2. Because the dependence of d,H, 1ε , log dH ε are decreasing as p increases, by assigning p “ cK and 1 ă p ď cK , N will be minimized when p “ cK . Then, we finished the proof. ˝

heading: C.3 ANALYSIS FOR ALGORITHMS
text: Next, we will use the above lemma to bound the difference between JpπKq and Jpπ˚q. We first prove a lemma similar to Lemma B.3 in (Jin et al., 2019) and Lemma A.1 in (Wang et al., 2020b). Lemma C.4 (Concentration Lemma). We use E1 to denote the event that, when running Algorithm 1, the following inequality holds for all k P rKs and h P rhks and arbitrary V kh`1 occurs in Alg 1.
›
›
›
k´1 ÿ
τ“1
N ÿ n“1 φτnh ´ V kh`1psτnh`1q ´ ÿ s1PS Phps1|sτnh , aτnh qV kh`1ps1q ¯ › › › pΛkhq´1 ď c ¨ dH a logpdKNH{δq
Under Assumption A, there exists some absolute constant c ě 0, such that P pE1q ě 1´ δ{2.
Proof. The proof is almost identical to Lemma B.3 in (Jin et al., 2019), so we omit it here. The only difference is that we have an inner summation from n “ 1 to N and we truncate the horizon at hk in iteration k. ˝ Lemma C.5 (Overestimation). On the event E1 in Lemma C.4, which holds with probability 1´δ{2, for all k P rKs and n P rN s,
V ˚1 pskn1 |hkq ď V k1 pskn1 q
where recall that V k1 is the function computed at iteration k in Alg.1 and V ˚ 1 p¨|hkq “ Er řhk h“1 rhpsh, ahq|π˚r1:hkss denote the optimal value function in the MDP truncated at layer hk and π˚r1:hks is the optimal policy in the truncated MDP.
Besides, we also have:
Es1„d1rV ˚1 ps1|hkq ´ V πkps1|hkqs ď 2βEs1,a1,...,shk ,ahk„πk r hk ÿ
h“1 }φpsh, ahq}pΛkhq´1s
Proof. First of all, by applying Lemma C.4 above, after a similar discussion to the proof of Lemma 3.1 in (Wang et al., 2020b), we can show that
|φps, aqJwkh ´ ÿ s1PS Phps1|s, aqV kh`1ps1q| ď β}φps, aq}pΛkhq´1 , @s P S, a P A, h P rhks
and the overestimation
V ˚h ps|hkq ď V kh psq, @s P S, h P rhks
As a result,
Es1„d1rV ˚1 ps1|hkq ´ V πkps1|hkqs ďEs1„d1rV k1 ps1q ´ V πkps1|hkqs “Es1„d1,a1„πk rQk1ps1, a1q ´Qπkps1, a1|hkqs “Es1„d1,a1„πk rmintpwk1 qJφps1, a1q ` r1ps1, a1q ` uk1ps1, a1q, Hu ´ r1ps1, a1q ´ ÿ
s2PS P1ps2|s1, a1qV πk2 ps2|hkqqs
“Es1„d1,a1„πk rmintpwk1 qJφps1, a1q, H ´ r1ps1, a1q ´ uk1ps1, a1qu ´ ÿ s2PS P1ps2|s1, a1qV k2 ps2qs
` Es1„d1,a1„πk r ÿ s2PS P1ps2|s1, a1qV k2 ps2q ´ ÿ s2PS P1ps2|s1, a1qV πk2 ps2|hkqqs ` Es„µruk1ps1, a1qs
ďEs1„d1,a1„πk r ÿ s2PS P1ps2|s1, a1qV k2 ps2q ´ ÿ s2PS P1ps2|s1, a1qV πk2 ps2|hkqqs ` 2Es„µruk1ps1, a1qs
“Es1„d1,a1,s2,a2„πk rV k2 ps2q ´ V πk 2 ps2|hkqs ` 2Es„µruk1ps1, a1qs ď...
ď2Es1„d1,a1,...,shk ,ahk„πk r hk ÿ
h“1 ukhpsh, ahqs
ď2βEs1„d1,a1,...,shk ,ahk„πk r hk ÿ
h“1 }φpsh, ahq}pΛkhq´1s
where in the second inequality, we use the following fact
mintpwk1 qJφps1, a1q, H ´ r1ps1, a1q ´ uk1ps1, a1qu ´ ÿ s2PS P1ps2|s1, a1qV k2 ps2q
“mintpwk1 qJφps1, a1q ´ ÿ s2PS P1ps2|s1, a1qV k2 ps2q, H ´ rk1 ps1, a1q ´ uk1ps1, a1q ´ ÿ s2PS P1ps2|s1, a1qV k2 ps2qu
ďmintβ}φps1, a1q}pΛk1 q´1 , Hu “ u k 1ps1, a1q
˝
Now we are ready to prove the following theorem restated from Theorem 4.1 in a more detailed version, where we include the guarantees during the execution of the algorithm.
Theorem C.6. [Deployment Complexity] For arbitrary ε, δ ą 0, and arbitrary cK ě 2, as long as N ě c ´ cK H4cK`1d3cK ε2cK log2cK pHdδε q ¯ 1
cK´1 , where c is an absolute constant and independent with cK , d,H, ε, δ, by choosing
K “ cKdH ` 1. (8)
Algorithm 1 will terminate at iteration kH ď K and return us a policy πkH , and with probability 1´ δ, (1) Es1„d1rV ˚1 ps1q ´ V π kH
1 ps1qs ď ε. (2) for each h P rH ´ 1s, there exists an iteration kh, such that hkh “ h but hkh`1 “ h`1, and πkh is an ε-optimal policy for the MDP truncated at step h;
Proof. As stated in the theorem, we use kh to denote the number of deployment after which the algorithm switch the exploration from layer h to layer h ` 1, i.e. hkh “ h and hkh`1 “ h ` 1. According to the definition and the algorithm, we must have ∆kh ď εhkh 2H , and for arbitrary kh´1 ` 1 ď k ď kh ´ 1, ∆k ě εhk2H (if kh´1 ` 1 ą kh ´ 1, then it means ∆kh´1`1 is small enough and the algorithm directly switch the exploration to the next layer, and we can skip the discussion below ). Therefore, for arbitrary kh´1 ` 1 ď k ď kh ´ 1, during the k-th deployment, there exists h P rhks, such that,
ε 2H ď ∆k hk ď 2β N
N ÿ n“1 }φpsknh , aknh q}pΛkhq´1 ď 2β
g f
f
e
1
N
N ÿ n“1 }φpsknh , aknh q}2pΛkhq´1
where the second inequality is because the average is less than the maximum. The above implies that
1
N
N ÿ n“1 }φpsknh , aknh q}2pΛkhq´1 “ 1 N Tr ´ pΛkhq´1 ´ N ÿ n“1 φpsknh , aknh qφpsknh , aknh qJ ¯¯ ě ε 2 16H2β2 (9)
According to Lemma 4.2, there exists constant c, c1, such that by choosing N according to Eq.(10) below, the event in Eq.(9) will not happen more than dcK times at each layer h P rhks.
N ě c ´ cK H4cK`1d3cK
ε2cK log2cK pHd εδ q ¯ 1 cK´1 ě c1 ´ cK H2cK`1dcKβ2cK ε2cK logcK pHdβ ε q ¯ 1 cK´1
(10)
Recall that ε ă 1 and the covariance matrices in each layer is initialized by Idˆd. Therefore, at the first deployment, although the computation of π1 does not consider the layers h ě 2, Eq.(9) happens in each layer h P rHs. We use ζpk, jq to denote the total number of times events in Eq.(9) happens for layer j previous to deployment k, as a result,
kh ď h ÿ
j“1 ζpkh, jq ´ ph´ 1q ` h ď cKdh` 1, @h P rHs
where we minus h ´ 1 because such event must happen at the first deployment for each h P rHs and we should remove the repeated computation; and we add another h back is because there are h times we waste the samples (i.e. for those k such that ∆k ă εhk2H ). Therefore, we must have kH ď cKdH ` 1 “ K. Moreover, because at iteration k “ kh, we have ∆kh ď ε{2, according to Hoeffding inequality, with probability 1´ δ{2, for each deployment k, we must have:
Es1,a1,...,shk ,ahk„πk r2β hk ÿ
h“1 }φpsh, ahq}pΛkhq´1s ď ∆k ` 2βH
c
1 2N logpK δ q (11)
Therefore, by choosing
N ě 8β 2H2 ε2 logpK δ q “ Opd 2H4 ε2 log2pK δ qq (12)
we must have,
Es1,a1,...,sh,ah„πkh r2β h ÿ
h1“1 }φpsh1 , ah1q}pΛk h1 q ´1s ď ∆kh `
ε 2 “ ε, @h P rHs
Therefore, after a combination of Eq.(10) and Eq.(12), we can conclude that, for arbitrary cK ě 2 , there exists absolute constant c, such that by choosing
N ě c ´ cK H4cK`1d3cK
ε2cK log2cK pHd εδ q ¯
1 cK´1
the algorithm will stop at kH ď K, and with probability 1 ´ δ (on the event of E1 in C.4 and the Hoeffding inequality above), we must have:
Es1„d1rV ˚1 ps1q ´ V πkps1qs ď Es1,a1,...,shk ,ahk„πk`1r2β hk ÿ
h“1 }φpsh, ahq}pΛkhq´1s ď ε
and an additional benefits that for each h P rH´1s, πkh is an ε-optimal policy at the MDP truncated at h step, or equivalently,
Es1„d1rV ˚1 ps1|hq ´ V πkh 1 ps1|hqs ď ε. (13)
˝

heading: C.4 ADDITIONAL SAFETY GUARANTEE BROUGHT WITH LAYER-BY-LAYER STRATEGY
text: The layer-by-layer strategy brings another advantage that, if we finish the exploration of the first h layers, based on the samples collected so far, we can obtain a policy pπ|h, which is an ε-optimal in the MDP truncated at step h, or equivalently:
Jpπ˚q ´ Jppπ|hq ě H ´ h`Opεq, @h P rHs
We formally state these guarantees in Theorem C.6 (a detailed version of Theorem 4.1), Theorem D.4 and Theorem E.9 (the formal version of Theorem 4.4). Such a property may be valuable in certain application scenarios. For example, in “Safe DE-RL”, which we will discuss in Appendix F, pπ|h can be used as the pessimistic policy in Algorithm 7 and guarantee the monotonic policy improvement criterion. Besides, in some real-world settings, we may hope to maintain a sub-optimal but gradually improving policy before we complete the execution of the entire algorithm.
If we replace Line 7-8 in LSVI-UCB (Algorithm 1) in Jin et al. (2019) with Line 13-18 in our Algorithm 1, the similar analysis can be done based on Lemma 4.2, and the same ΘpdHq deployment complexity can be derived. However, the direct extension based on LSVI-UCB does not have the above safety guarantee. It is only guaranteed to return a near-optimal policy after K “ ΘpdHq deployments, but if we interrupt the algorithm after some k ă K deployments, there is no guarantee about what the best possible policy would be based on the data collected so far.

heading: D REWARD-FREE DEPLOYMENT-EFFICIENT RL WITH DETERMINISTIC POLICIES

heading: D.1 ALGORITHM
text: Similar to other algorithms in reward-free setting (Wang et al., 2020b; Jin et al., 2020), our algorithm includes an “Exploration Phase” to uniformly explore the entire MDP, and a “Planning Phase” to return near-optimal policy given an arbitrary reward function. The crucial part is to collect a wellcovered dataset in the online “exploration phase”, which is sufficient for the batch RL algorithm (Antos et al., 2008; Munos & Szepesvári, 2008; Chen & Jiang, 2019) in the offline “planning phase” to work.
Our algorithm in Alg.3 and Alg.4 is based on (Wang et al., 2020b) and the layer-by-layer strategy. The main difference with Algorithm 1 is in two-folds. First, similar to (Wang et al., 2020b), we replace the reward function with 1{H of the bonus term. Secondly, we use a smaller threshold for ∆k comparing with Algorithm 1.

heading: D.2 ANALYSIS FOR ALG 3 AND ALG 4
text: We first show a lemma adapted from Lemma C.4 for Alg 3. Since the proof is similar, we omit it here. Lemma D.1 (Concentration for DE-RL in Reward-Free Setting). We use E2 to denote the event that, when running Algorithm 3, the following inequality holds for all k P rKs and h P rhks and all V “ V kh`1 occurs in Alg 3 or V “ Vh occurs in Alg 4:
›
›
›
k´1 ÿ
τ“1
N ÿ n“1 φτnh ´ V psτnh`1q ´ ÿ s1PS Phps1|sτnh , aτnh qV ps1q ¯ › › › pΛkhq´1 ď c ¨ dH a logpdKNH{δq
Under Assumption A, there exists some absolute constant c ě 0, such that P pE2q ě 1´ δ{2.
Proof. The proof is almost identical to Lemma 3.1 in (Wang et al., 2020b), so we omit it here. The only difference is that we have an inner summation from n “ 1 to N and we truncate the horizon at hk in iteration k. ˝
Next, we prove a lemma simlar to Lemma C.5 based on Lemma D.1. Lemma D.2 (Overestimation). On the event E2 in Lemma D.1, which holds with probability 1´δ{2, in Algorithm 3, for all k P rKs and n P rN s,
V ˚1 pskn1 , rk|hkq ď V k1 pskn1 q and
Es1„d1rV ˚1 ps, rk|hkqs ď Es1„d1rV k1 psqs ď p2H ` 1qEs1„d1rV πkps, rk|hkqs
Proof. We first prove the overestimation inequality.
Algorithm 3: Reward-Free DE-RL with Deterministic Policies in Linear MDPs: Exploration Phase
1 Input: Failure probability δ ą 0, and target accuracy ε ą 0, β Ð cβ ¨ dH a logpdHδ´1ε´1q for some cβ ą 0, total number of deployments K, batch size N 2 Initialize h1 “ 1 3 D1 “ tu, D2 “ tu, ..., DH “ tu 4 for k “ 1, 2, ...,K do 5 Qkhk`1p¨, ¨q Ð 0 and V k hk`1p¨q “ 0 6 for h “ hk, hk ´ 1, ..., 1 do 7 Λkh Ð I ` řk τ“1 řN n“1 φ τn h pφτnh qJ 8 ukhp¨, ¨q Ð mintβ ¨ b
φp¨, ¨qJpΛkhq´1φp¨, ¨q, Hu 9 Define the exploration-driven reward function rkhp¨, ¨q Ð ukhp¨, ¨q{H
10 wkh Ð pΛkhq´1 řk´1 τ“1 řN n“1 φ τn h ¨ V kh`1psτnh`1q 11 Qkhp¨, ¨q Ð mintpwkhqJφp¨, ¨q ` rkhp¨, ¨q ` ukhp¨, ¨q, Hu and V kh p¨q “ maxaPAQkhp¨, aq 12 πkhp¨q Ð arg maxaPAQkhp¨, aq 13 end 14 Define πk “ πk1 ˝ πk2 ˝ ...πkhk ˝ unifrhk`1:Hs 15 for n “ 1, ..., N do 16 Receive initial state skn1 „ d1 17 for h “ 1, 2, ...,H do 18 Take action aknh Ð πkpsknh q and observe sknh`1 „ Phpskh, akhq 19 Dh “ Dh Ť
tpsknh , aknh qu 20 end 21 end
22 Compute ∆k Ð 2βN řN n“1 řhk h“1
b
φpsknh , aknh qJpΛkhq´1φpsknh , aknh q. 23 if ∆k ă εhkp4H`2qH then 24 if hk “ H then return D “ tD1, D2, ..., DHu ; 25 else hk Ð hk ` 1 ; 26 end 27 end
Algorithm 4: Reward-Free DE-RL with Deterministic Policies in Linear MDPs: Planning Phase
1 Input: Horizon length rh; Dataset D “ tpsknh , aknh qk,n,hPrKsˆrNsˆrrhsu, reward function r “ trhuhPrrhs 2 Q rh`1p¨, ¨q Ð 0 and Vrh`1p¨q Ð 0 3 for h “ rh,rh´ 1, ..., 1 do 4 Λh Ð I ` řK τ“1 řN n“1 φpsτnh , aτnh qφpsτnh , aτnh qJ 5 Let uplanh p¨, ¨q Ð mintβ a
φp¨, ¨qJpΛhq´1φp¨, ¨q,rhu 6 wh Ð pΛhq´1 řK τ“1 φpsτnh , aτnh q ¨ Vh`1psτnh`1, aq 7 Qhp¨, ¨q Ð mintwJh φp¨, ¨q ` rhp¨, ¨q ` u plan h p¨, ¨q,rhu and Vhp¨q “ maxaPAQhp¨, aq 8 πhp¨q Ð arg maxaPAQhp¨, aq 9 end
10 return πr|rh “ tπhuhPrrhs, pV1p¨, r|rhq :“ V1p¨q
Overestimation First of all, similar to the proof of Lemma 3.1 in (Wang et al., 2020b), on the event of E2 defined in Lemma C.4, which holds with probability 1´ δ{2, we have: |φps, aqJwkh ´ ÿ
s1PS Phps1|s, aqV kh`1ps1q| ď β ¨ }φps, aq}pΛkhq´1 , @s, a P S ˆA, k P rKs, h P rhks
(14)
Then, we can use induction to show the overestimation. For h “ hk ` 1, we have:
0 “ V ˚hk`1ps, r k|hkq ď V khk`1psq “ 0, @s P S
Suppose for some h P rhks, we have
V ˚h`1ps, rk|hkq ď V kh`1psq, @s P S
Then, @s P S, we have
V ˚h ps, rk|hkq “maxa pr k hps, aq `
ÿ
s1PS Phps1|s, aqV ˚h`1ps1, rk|hkqq
ďmax a prkhps, aq `
ÿ
s1PS Phps1|s, aqV kh`1ps1qq, H
ďmintmax a prkhps, aq ` φps, aqJwkh ` β}φps, aq}pΛkhq´1q, Hu
“max a mintrkhps, aq ` φps, aqJwkh ` β}φps, aq}pΛkhq´1 , Hu
“V kh psq
where in the last inequality, we apply Eq.(14).
Relationship between V k1 p¨q and V πkp¨, rkq
Es1„d1rV k1 ps1q ´ V πkps1, rk|hkqs “Es1„d1,a1„πk rQk1ps1, a1q ´Qπkps1, a1, rk|hkqs “Es1„d1,a1„πk rmintpwk1 qJφps1, a1q ` rk1 ps1, a1q ` uk1ps1, a1q, Hu
´ rk1 ps1, a1q ´ ÿ s2PS P1ps2|s1, a1qV πk2 ps2, rk|hkqqs
ďEs1„d1,a1„πk rmintpwk1 qJφps1, a1q, H ´ rk1 ps1, a1q ´ uk1ps1, a1qu ´ ÿ s2PS P1ps2|s1, a1qV k2 ps2qs
` Es1„d1,a1„πk r ÿ s2PS P1ps2|s1, a1qV k2 ps2q ´ ÿ s2PS P1ps2|s1, a1qV πk2 ps2, rk|hkqqs ` Es„d1ruk1ps1, a1qs
ďEs1„d1,a1„πk r ÿ s1PS P1ps2|s1, a1qV k2 ps2q ´ ÿ s2PS P1ps2|s1, a1qV πk2 ps2, rk|hkqqs ` 2Es„d1ruk1ps1, a1qs
“Es1„d1,a1,s2,a2„πk rV k2 ps2q ´ V πk 2 ps2, rk|hkqs ` 2Es„d1ruk1ps1, a1qs ď...
ď2Es1„d1,a1,...,shk ,ahk„πk r H ÿ
h“1 ukhpsh, ahqs
“2HEs1„d1rV πkps, rk|hkqs
where in the first inequality, we add and subtract ř s2PS P1ps2|s1, a1qV k 2 ps2q, and in the second inequality, we use the following fact
mintpwk1 qJφps1, a1q, H ´ rk1 ps1, a1q ´ uk1ps1, a1qu ´ ÿ s2PS P1ps2|s1, a1qV k2 ps2q
“mintpwk1 qJφps1, a1q ´ ÿ s2PS P1ps2|s1, a1qV k2 ps2q, H ´ rk1 ps1, a1q ´ uk1ps1, a1q ´ ÿ s2PS P1ps2|s1, a1qV k2 ps2qu
ďmintβ}φps1, a1q}pΛk1 q´1 , Hu “ u k 1ps1, a1q
˝
Next, we provide some analysis for Algorithm 4, which will help us to understand what we want to do in Algorithm 3
Lemma D.3. On the event E2 in Lemma D.1, which holds with probability 1 ´ δ{2, if we assign rh “ hk in Algorithm 4 and assign D to be the samples collected till deployment k, i.e. D “ tpsknh , aknh qk,n,hPrKsˆrNsˆrhksu, then for arbitrary reward function r satisfying the linear Assumption A, the policy πr|rh returned by Alg 4 would satisfy:
Es1„d1rV π˚ r|rh 1 ps1, r|rhq ´ V π r|rh 1 ps1, r|rhqs ď 2HEs1„d1rV π˚ rplan|rh 1 ps1, rplan|rhqs (15)
where rplan :“ uplan{rh.
Proof. By applying the similar technique in the analysis of Es1„d1rV k1 ps1q ´ V πkps1, rk|rhqs in Lemma D.2 after replacing rk with r, we have:
Es1„d1rV π˚ r|rh 1 ps1, r|rhq ´ V π r|rh 1 ps1, r|rhqs ďEs1„d1rpV1ps1, r|rhq ´ V π r|rh 1 ps1, r|rhqs ď 2Es1„d1rV π r|rh 1 ps1, uplanqs
where pV1 denotes the value function returned by Alg 4 Besides,
2Es1„d1rV π r|rh 1 ps1, uplanqs “2rhEs1„d1rV π r|rh 1 ps1, rplan|rhqs ď 2HEs1„d1rV π˚ rplan|rh 1 ps1, rplan|rhqs
then, we finish the proof. ˝
From Eq.(15) in Lemma D.3, we can see that, after exploring with Algorithm 3, the sub-optimality gap between π˚ and π returned by Alg.4 can be bounded by the value of the optimal policy w.r.t. rK , which we will further bound in the next theorem.
Now we are ready to prove the main theorem.
Theorem D.4. For arbitrary ε, δ ą 0, by assigning K “ cKdH ` 1 for some cK ě 2, as long as
N ě c ´ cK H6cK`1d3cK
ε2cK log2cK pHd δε q ¯
1 cK´1 )
(16)
where c is an absolute constant and independent with cK , d,H, ε, δ, then, Alg 3 will terminate at iteration kH ď K and return us a dataset D “ tD1, D2, ..., DHu, such that given arbitrary reward function r satisfying Assumption A, by running Alg 4 with D and r, with probability 1 ´ δ, we can obtain a policy πr satisfying Es„d1rV ˚1 ps, rq ´ V πps, rqs ď ε. Moreover, for each h P rH ´ 1s, there exists iteration kh, such that hkh “ h but hkh`1 “ h ` 1, and if we run Alg 4 with the reward function r and the dataset Alg 3 has collected till k “ kh, we can obtain a policy πr|h, which is an ε-optimal policy for MDP truncated at step h.
Proof. The proof is similar to Theorem 4.1. As stated in theorem, we use kh to denote the number of deployment when the algorithm switch the exploration from layer h to layer h` 1, i.e. hkh “ h and hkh`1 “ h` 1. According to the definition and the algorithm, we must have ∆kh ď εhkh p4H`2qH , and for arbitrary kh´1 ` 1 ď k ď kh ´ 1, we must have ∆k ě εhkp4H`2qH (if kh´1 ` 1 ą kh ´ 1, then it means ∆kh´1`1 is small enough and the algorithm directly switch the exploration to the next layer, and we can skip the discussion below). Therefore, for arbitrary kh´1 ` 1 ď k ď kh ´ 1, during the k-th deployment, there exists h P rhks, such that,
ε p4H ` 2qH ď ∆k hk ď 2β N
N ÿ n“1 }φpsknh , aknh q}pΛkhq´1 ď 2β
g f
f
e
1
N
N ÿ n“1 }φpsknh , aknh q}2pΛkhq´1
which implies that
1
N
N ÿ n“1 }φpsknh , aknh q}2pΛkhq´1 ě
ε2
16H2p2H ` 1q2β2 (17)
According to Lemma 4.2, there exists an absolute constant c, for arbitrary ε ă 1, by choosing N according to Eq.(18) below, the events in Eq.(17) will not happen more than cKd times at each layer h P rHs.
N ě c ´ cK H6cK`1d3cK
ε2cK log2cK pHd εδ q ¯ 1 cK´1 (18)
We use ζpk, jq to denote the total number of times Eq.(9) happens for layer j till deployment kh. With a similar discussion as Theorem 4.1, we have:
kh ď h ÿ
j“1 ζpkh, jq ´ ph´ 1q ` h ď cKdh` 1, @h P rHs
Moreover, we must have ∆kh ď ε4H`2 for each h P rHs, and according to Hoeffding inequality, with probability 1´ δ{2, for each step k, we must have
Es1,a1,...,sh,ah„πkh r2β h ÿ
h1“1 }φpsh1 , ah1q}pΛk h1 q ´1s ď ∆kh ` 2βH
c
1 2N logpK δ q
Therefore, by choosing
N ě 8β 2H2p2H ` 1q2 ε2 logpK δ q “ Opd 2H6 ε2 log2pK δ qq (19)
we have,
Es1,a1,...,sh,ah„πkh r2β h ÿ
h1“1 }φpsh1 , ah1q}pΛk h1 q ´1s ď ∆kh `
ε 4H ` 2 “ ε 2H ` 1
For arbitrary h P rHs, in Algorithm 4, if we assign rh “ h and D “ tpsknh , aknh qk,n,hPrkhsˆrNsˆrhsu, note that rplan “ rkh , by applying Lemma D.2 and Lemma D.3 we have:
Es1„d1rV π˚ r|rh 1 ps1, r|rhq ´ V π r|rh 1 ps1, r|rhqs ď 2HEs1„d1rV π˚ rplan|rh
1 ps1, rplan|rhqs “2HEs1„d1rV ˚1 ps1, rkh |hqs ď 2Hp2H ` 1qEs1„d1rV πkh ps1, rkh |hqs
“p2H ` 1qEs1,a1,...,sh,ah„πkh r2β h ÿ
h1“1 }φpsh1 , ah1q}pΛk h1 q ´1s ď ε
Therefore, after a combination of Eq.(18) and Eq.(19), we can conclude that, for arbitrary cK ě 2 , there exists absolute constant c, such that by choosing
N ě c ´ cK H6cK`1d3cK
ε2cK log2cK pHd δε q ¯
1 cK´1
Alg 3 will terminate at kH ď K, and with probability 1 ´ δ (on the event in Lemma D.1 and Hoeffding inequality above), for each h P rHs, if we feed Alg 4 with rh “ h, D “ tpsknh , aknh qk,n,hPrkhsˆrNsˆrhsu and arbitrary linear reward function r, the policy πr|h returned by Alg 4 should satisfy:
Es1„d1rV πr|h 1 ps1, r|hqs ě Es1„d1rV
π˚ r|h
1 ps1, r|hqs ´ ε
˝

heading: E DE-RL WITH ARBITRARY DEPLOYED POLICIES
text: In the proof for this section, without loss of generality, we assume the initial state is fixed, which will makes the notation and derivation simpler without trivialize the results. For the case where initial state is sampled from some fixed distribution, our algorithms and results can be extended simply by considering the concentration error related to the initial state distribution.
Algorithm 5: SolveOptQ 1 Input: Time step h; Dataset in previous steps tD1, ..., Dh´1u; Unregularized Covariance
Matrices tΣ1, ...Σh´1u; Bonus factor β; Matrix to construct reward function ΣR; Discretize resolution ε0 ď 12dpN`1q
2 Rp¨, ¨q Ð a φp¨, ¨qJp2I ` ΣRq´1φp¨, ¨q 3 Zh Ð Discretizationpp2I ` ΣRq´1, ε0 2 4d q, R̄p¨, ¨q Ð a
φp¨, ¨qJZhφp¨, ¨q 4 Qhp¨, ¨q “ Rp¨, ¨q, Vhp¨q “ maxaQhp¨, aq, Q̄hp¨, ¨q “ R̄p¨, ¨q, V̄hp¨q “ maxa Q̄hp¨, aq 5 π̄hp¨q “ arg maxa Q̄hp¨, aq 6 for rh “ h´ 1, ..., 1 do 7 w
rh Ð Σ ´1 rh ř ps rh ,a rh ,s rh`1qPDrh φps rh, arhq ¨ Vrh`1psrh`1q 8 u
rh :“ βrφp¨, ¨q JΣ´1 rh φp¨, ¨qs1{2
9 Q rhp¨, ¨q Ð mintw J rh φp¨, ¨q ` u rh, 1u, Vrhp¨q Ð maxaQrhp¨, aq 10 w̄
rh Ð Discretizationpwrh, ε0 2d q, Zrh Ð Discretizationpβ 2Σ´1 rh , ε0
2
4d q 11 ū
rh :“ rφp¨, ¨q JZ rhφp¨, ¨qs 1{2
12 Q̄ rhp¨, ¨q Ð mintw̄ J rh φp¨, ¨q ` ū rh, 1u, V̄rhp¨q Ð maxa Q̄rhp¨, aq 13 π̄
rhp¨q Ð arg maxa Q̄rhp¨, aq 14 end 15 return V1ps1q, π̄ :“ π̄1 ˝ π̄2 ˝ ...π̄h
Algorithm 6: EstimateCovMatrix 1 Input: Time step h; Dataset in previous steps tD1, ..., Dh´1u; Covariance Matrices tΣ1, ...Σh´1u; Deterministic Policy to evaluate π̄ “ tπ̄1, π̄2, ..., π̄hu 2 Initialize a zero matrix rΛπh “ O 3 for i “ 1, 2, ..., d do 4 for j “ i, i` 1, ..., d do 5 Define rRij , such that, rRijh p¨, ¨q “ 1`φip¨,¨qφjp¨,¨q 2 and rR ij rh “ 0 for all rh P rh´ 1s; 6 pQπ̄hp¨, ¨q “ rR ij h p¨, ¨q, pV π̄h p¨q “ pQπ̄hp¨, π̄hp¨qq 7 for rh “ h´ 1, ..., 1 do 8 pwπ̄
rh Ð Σ´1 rh ř ps rh ,a rh ,s rh`1qPDrh φpst, atq ¨ pV π̄ rh`1 ps rh`1q 9 pQπ̄
rh p¨, ¨q Ð mint rRij rh p¨, ¨q ` p pwπ̄ rh qJφp¨, ¨q, 1u
10 pV π̄ rh p¨q “ pQπ̄ rh p¨, π̄ rhp¨qq 11 end 12 prΛπ̄
rh qij Ð pV π̄1 ps1q; prΛπ̄ rh qji Ð pV π̄1 ps1q
13 end 14 end 15 pΛπ̄
rh “ 2prΛπ̄ rh q ´ 1
16 return pΛπ̄ rh

heading: E.1 ALGORITHMS
text: We first introduce the definition for Discretization function:
Definition E.1 (Discretization function). Given vector w “ pw1, w2, ..., wdqJ P Rd or matrix Σ “ pΣijqi,jPrds P Rdˆd as input, we have:
Discretizationpw, ε0q “ pε0r w1 ε0 s, ε0r w2 ε0 s, ..., ε0r wd ε0 sq, DiscretizationpΣ, ε0q “ pε0r Σij ε0 sqi,jPrds
where r¨s is the ceiling function.
In Algorithm 6, we are trying to estimate the expected covariance matrix under policy π̄ by policy evaluation. The basic idea is that, the expected covariance matrix can be represented by:
Esh,ah„π̄rφpsh, ahqφpsh, ahqJs “ ` Eπ̄rφipsh, ahqφjpsh, ahqs ˘ ij “ ` V π̄ps1, Rijq ˘ ij
where we use paijqij to denote a matrix whose element indexed by i in row and j in column is aij . In another word, the element in the covariance matrix indexed by ij is equal to the value function of policy π̄ with Rijh psh, ahq :“ φipsh, ahqφjpsh, ahq as reward function at the last layer (and use zero reward in previous layers), where φi denotes the i-th elements of vector φ. Because the techniques rely on the reward is non-negative and bounded in r0, 1s, by leveraging the fact that |φip¨, ¨q| ď }φp¨, ¨q} ď 1, we shift and scale Rij to obtain rRij and use it for policy evaluation. In Alg 5, we maintance two Q functions Qh and Q̄h. The learning of Qh is based on LSVI-UCB, while Q̄h is a “discretized version” for Qh computed by discretizing wh, β2Σ´1h (or Σ ´1 R at layer h) elementwisely with resolution ε0, and Q̄h will be used to compute π̄h for deployment. The main reason why we discretize Qh is to make sure the number of greedy policies π̄ is bounded, so that we can use union bound and upper bound the error when using Alg6 to estimate the covariance matrix. In Section E.5, we will analyze the error resulting from discretization, and we will upper bound the estimation error Algorithm 6.
E.2 FUNCTION CLASSES AND ε0-COVER
We first introduce some useful function classes and their ε0-cover.
Notation for Value Function Classes and Policy Classes We first introduce some new notations for value and policy classes. Similar to Eq.(6) in (Jin et al., 2019), we define the greedy value function class
V˚L,B “ tV p¨q|V p¨q “ max a
mintφp¨, aqJw ` b φp¨, aqJΣφp¨, aq, 1u, }w} ď L, }Σ} ď Bu
and the Q function class:
QL,B “ tQp¨, ¨q|Qp¨, ¨q “ mintφp¨, ¨qJw ` b φp¨, ¨qJΣφp¨, ¨q, 1u, }w} ď L, }Σ} ď Bu
Besides, suppose we have a deterministic policy class Π with finite candidates (i.e. |Π| ď 8), we use VL,B ˆΠ to denote:
VL,B ˆΠ “ tV p¨q|V p¨q “ mintφp¨, πp¨qqJw ` b φp¨, πp¨qqJΣφp¨, πp¨qq, 1u, }w} ď L, }Σ} ď B, π P Πu
Recall that in Alg.6, we will use a special reward function, and we need to consider it in the union bound. We denote:
Vφ ˆΠ “ tV |V p¨q “ 1` φip¨, πp¨qqφjp¨, πp¨qq
2 , i, j P rds, π P Πu
and easy to check |Vφ ˆΠ| “ d2|Π|. Moreover, if we have a Q function class Q, we will use ΠQ to denote the class of greedy policies induced from Q, i.e.
ΠQ :“ tπp¨q “ arg maxQp¨, aq|Q P Qu.
Discretization with Resolution ε0 In the following, we will use Cw,L,ε0 to denote the ε0-cover for w P Rd with }w} ď L, concretely,
Cw,L,ε0 “ tw|| wi ε0 | P rr L ε0 ss,@i P rdsu
where r¨s is the ceiling function. Similarly, we will use CΣ,B,ε0 to denote the ε0-cover for matrix Σ P Rdˆd with maxi,j |Σij | ď B
CΣ,B,ε0 “ tΣ|| Σij ε0 | P rrB ε0 ss,@i, j P rdsu.
Easy to check that:
log |Cw,L,ε0 | ď d log 2L
ε0 , log |CΣ,B,ε0 | ď d2 log
2B
ε0
Recall the definition of Discretize function in Def. E.1, easy to check that:
}Discretizepw, ε0q ´ w} ď dε0, }DiscretizepΣ, ε0q ´ Σ} ď }DiscretizepΣ, ε0q ´ Σ}F ď dε0
ε0-cover Before we introduce our notations for ε0-net, we first show a useful lemma:
Lemma E.2. For arbitrary w,Σ, denote w̄ “ Discretizepw, ε02d q and Σ̄ “ DiscretizepΣ, ε0
2
4d q. Consider the following two functions and their greedy policies, where }φp¨, ¨q} ď 1
Qps, aq “ mintwJφp¨, aq ` b
φp¨, aqJΣφp¨, aq, 1u, π “ arg max a Qps, aq
Q̄ps, aq “ mintw̄Jφp¨, aq ` b
φp¨, aqJΣ̄φp¨, aq, 1u, π̄ “ arg max a Q̄ps, aq
then we have:
|Qps, πpsqq ´Qps, π̄psqq| ď 2ε0, @s P S, }Q´ Q̄}8 ď ε0, sup
s |max a Qp¨, aq ´max a Q̄p¨, aq| ď ε0
Proof. After similar derivation as Eq.(28) in (Jin et al., 2019), we can show that
sup s |max a Qp¨, aq ´max a Q̄p¨, aq| ď}Q´ Q̄}8
ď sup s,a
ˇ
ˇ ˇ wJφp¨, ¨q `
b φp¨, ¨qJΣφp¨, ¨q ´ w̄Jφp¨, ¨q ´ b φp¨, ¨qJΣ̄φp¨, ¨q ˇ ˇ
ˇ
ď}w ´ w̄} ` b }Σ´ Σ̄}F ď d ε0 2d ` c d ε02 4d ď ε0
Because π and π̄ are greedy policies, we have:
0 ďQps, πpsqq ´Qps, π̄psqq ď Qps, πpsqq ´ Q̄ps, πpsqq ` Q̄ps, π̄psqq ´Qps, π̄psqq
ď2}Q´ Q̄}8 ď 2ε0. ˝
Now, we consider the following Q function class and V function class,
Q̄L,B,ε0 :“ tQ|Qp¨, ¨q “ mintwJφp¨, ¨q ` b
φp¨, ¨qJΣφp¨, ¨q, 1u, w P Cw,L, ε02d ,Σ P CΣ,dB, ε024d u
V̄˚L,B,ε0 :“ tV |V p¨q “ maxa mintw Jφp¨, aq `
b
φp¨, aqJΣφp¨, aq, 1u, w P Cw,L, ε02d ,Σ P CΣ,dB, ε024d u
based on Lemma E.2, and another important fact that maxi,j |aij | ď }A}F ď d}A}, we know that Q̄L,B,ε0 is an ε0-cover of QL,B , i.e. for arbitrary Q P QL,B , there exists Q̄ P Q̄L,B,ε0 , such that }Q´ Q̄} ď ε0. Similarly, V̄˚L,B,ε0 is also an ε0-cover of V ˚ L,B .
Besides, we will use ΠQ̄L,B,ε0 to denote the collection of greedy policy induced from elements in Q̄L,B,ε0 .
We also define V̄L,B,ε0 ˆΠ, which is an ε0 cover for VL,B ˆΠ.
V̄L,B,ε0 ˆΠ :“ tV |V p¨q “ mintφp¨, πp¨qqJw ` b
φp¨, πp¨qqJΣφp¨, πp¨qq, 1u, w P Cw,L, ε02d ,Σ P CΣ,dB, ε024d , π P Πu
Obviously, |V̄L,B,ε0 ˆΠ| “ |Π| ¨ |Cw,L, ε02d | ¨ |CΣ,dB, ε024d |.
Besides, because Vφ ˆΠ is already a finite set, it is an ε0-cover of itself.

heading: E.3 CONSTRAINTS IN ADVANCE
text: Induction Condition Related to Accumulative Error Recall the induction condition in 4.5, and we restate it here. 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´1
rh“1
b
φps rh, arhqJΣ ´1 rh φps rh, arhqs ď h´1 H ξ. (2)
Constraints for the Validity of the Algorithm Besides, in order to make sure the algorithm can run successfully, we add the following constaints:
ΣR ľ´ 1
2 I (20)
Z rh ľ0, @rh P rh´ 1s (21) I ľZh ľ 0 (22)
where constraint (22) for Zh is to make sure the reward R̄ locates in r0, 1s interval.
Recall the definition of Σ rh “ I ` řN n“1 φpsrh, arhqφpsrh, arhq J, therefore,
σminpβ2Σ´1 rh q “ β2{σmaxpΣrhq ě
β2
1`N According to Lemma E.11, to make sure Z
rh ľ 0, we need the following constraint on ε0
d ε0
2
4d ď β
2
pN ` 1q (23)
which is equivalent to ε0 ď β{ ? N ` 1.
As for Zh, the constraint is equivalent to:
2I ` ΣR ľ p1` ε0
2
4 qI, p2I ` ΣRq´1 ľ
ε0 2
4 I
and can be rewritten to
I ` ΣR ľ ε0
2
4 I,
4
ε02 I ľ 2I ` ΣR (24)

heading: E.4 CONCENTRATION BOUND
text: Based on the notations above, we are already to claim that: Claim 3. By choosing L “ ? dN,B “ β2 ` dε0 for some ε0 ď 1{d, during the running of Algorithm 2
• In Alg 5, for each h P rHs and rh P rhs, and the Q̄ rh and π̄rh generated while running the
algorithm, we must have Q̄ rh P Q̄L,B,ε0 and π̄rh P ΠQ̄L,B,ε0 . Besides, Qrh P QL,B and V rh P V ˚ L,B
• In Alg 6, for all rh P rhs, we have π̄ rh P ΠQ̄L,B,ε0 , and for arbitrary value function pV π̄ rh
generated in it, we have pV π̄ rh P pVL,B ˆΠQ̄L,B,ε0 q Y pVφ ˆΠQ̄L,B,ε0 q and therefore, there exists V P pV̄L,B,ε0 ˆΠQ̄L,B,ε0 q Y pVφ ˆΠQ̄L,B,ε0 q such that }V ´ pV π̄ rh } ď ε0
Proof. Algorithm 5: First we bound the norm of the weights wh in Algorithm 5. For arbitrary v P Rd and }v} “ 1, we have:
|vJw rh| “|vΣ ´1 rh
ÿ
ps rh ,a rh ,s rh`1qPDrh
φps rh, arhqVrh`1psrh`1q| ď |vΣ ´1 rh
ÿ
ps rh ,a rh ,s rh`1qPDrh
φps rh, arhq|
ď d | ÿ
ps rh ,a rh ,s rh`1qPDrh
vJΣ´1 rh v||
ÿ
ps rh ,a rh ,s rh`1qPDrh
φps rh, arhqJΣ ´1 rh φps rh, arhq|
ď}v} b
d|D rh| “ }v}
? dN
therefore, }w rh} ď
? dN . Besides, according to Lemma E.11 and constraint (24), we have:
}β2Σ´1 rh } ď β2, }Z rh} ď}β 2Σ´1 rh } ` dε0 ď β2 ` dε0 @h P rh´ 1s
}p2I ` ΣRq´1} ď 1, }Zh} ď}p2I ` ΣRq´1} ` dε0 ď 1` dε0
Recall B “ β2 ` dε0 and β ą 1, the claim about Alg 5 is true. Algorithm 6: The discussion about the value range of pwπ̄
rh is similar to above. Therefore, all the
value functions occurred in the previous h´ 1 layers would belong to VL,B ˆΠ, except that the last layer should belong to Vφ ˆ Π. Besides, since Alg 6 is only used to estimate the policies returned by Alg 5, we should have Π “ ΠQ̄L,B,ε0 . As a result, the claim for Alg 6 is correct. ˝
Recall Lemma D.4 from (Jin et al., 2019), which holds for arbitrary V with covering number Nε0 and sups |V psq| ď H . Next, we state a slightly generalized version by replacing sups |V psq| ď H with sups |V psq| ď 1, since in our Alg. 5 and Alg. 6 Vmax “ 1. This is also the main reason why we only need the coefficient of the bonus term β “ rOpdq instead of rOpdHq in Alg. 5 so that we can achieve better dependence on H . Lemma E.3 ((Revised) Lemma D.4 in (Jin et al., 2019)). Let tsτu8τ“1, be a stochastic process on state space S with corresponding filtration tFτu8τ“1. Let tφτu8τ“0 be an Rd-valued stochastic process where φτ P Fτ´1 and }φτ } ď 1. Let Λt “ λI ` řt τ“1 φτφ J τ . Then for any δ ą 0, with probability at least 1´ δ, for all t ě 0, and any V P V so that sups |V psq| ď 1, we have: ›
›
›
t ÿ τ“1 φτtV psτ q ´ ErV pxτ q|Fτ´1su › › › 2 Λ´1t ď 4rd 2 log t` λ λ ` log Nε0 δ s ` 8t 2ε0 2 λ
where Nε0 is the ε0-covering number of V w.r.t. the distance distpV, V 1q “ sups |V psq ´ V psq1|
Now we are ready to prove the main concentration result for Algorithm 2: Theorem E.4. Consider value function class V :“ V˚L,B Y pVL,B ˆΠQ̄L,B,ε0 q Y pVφ ˆΠQ̄L,B,ε0 q with L “ 1, B “ β2 ` dε0. According to Claim 3, V covers all possible value functions occurs when running Alg 2. We use E to denote the even that the following inequality holds for arbitrary V P V and arbitrary k P rKs “ rHs, h P rHs:
›
›
›
k´1 ÿ
τ“1
N ÿ n“1 φτnh ´ V psτn rh`1q ´ ÿ s1PS Phps1|sτnh , aτnh qV ps1q ¯ › › › pΣhq´1 ď c ¨ d a logpdNβH{ε0δq
As long as
ε0 ď 1{N (25)
there exists some constant c, such that P pEq ě 1´ δ{2.
Proof. We consider the value function class:
V :“ V˚L,B Y pVL,B ˆΠQ̄L,B,ε0 q Y pVφ ˆΠQ̄L,B,ε0 q
and we have an ε0-cover for it, which we denote as:
Vε0 :“ V̄˚L,B,ε0 Y pV̄L,B,ε0 ˆΠQ̄L,B,ε0 q Y pVφ ˆΠQ̄L,B,ε0 q
Besides, there exists c1 ą 0, s.t.
log |Vε0 | ď log |Vφ ˆΠQ̄L,B,ε0 | ` log |V̄ ˚ L,B,ε0 | ` log |V̄L,B,ε0 ˆΠQ̄L,B,ε0 |
ď log |Vφ ˆ Q̄L,B,ε0 | ` log |V̄˚L,B,ε0 | ` log |V̄L,B,ε0 ˆ Q̄L,B,ε0 |
ďc1d2 log dHNβ ε0
By plugging into Lemma E.3 and considering the union bound over k P rKs and h P rHs (note that K “ H), we have with probability 1´ δ{2,
›
›
›
k´1 ÿ
τ“1
N ÿ n“1 φτnh ´ V psτn rh`1q ´ ÿ s1PS Phps1|sτnh , aτnh qV ps1q ¯ › › › 2 pΛkhq´1 ď c2d2 log dHNβ ε0δ ` 8N2ε02
When ε0 ď 1N , the first term will dominate, and there must exists c such that ›
›
›
k´1 ÿ
τ“1
N ÿ n“1 φτnh ´ V psτn rh`1q ´ ÿ s1PS Phps1|sτnh , aτnh qV ps1q ¯ › › › pΛkhq´1 ď c ¨ d a logpdNβH{ε0δq
˝

heading: E.5 BIAS ANALYSIS
text: Lemma E.5 (Overestimation in Alg 5). Suppose we choose
β “ c1βd c log dHN
ε0δ (26)
for some cβ ą 0. During the running of Alg 2, on the condition 4.5 and on the event of E in Theorem E.4, which holds with probability 1´ δ{2, for arbitrary h P rHs and rh ď h´ 1, the parameter w rh and value function V
rh`1 occurs in Algorithm 5 should satisfy:
|φps, aqJw rh ´
ÿ
s1PS P rhps 1|s, aqV rh`1ps 1q| ď β}φps, aq}Σ´1 rh
and
V ˚ rh psq ď V rhpsq ď V ˚ rh psq ` Eπr
h ÿ
h1“rh
β}φpsh1 , ah1q}Σ´1 h1 s ď V ˚ rh psq ` βξ
Proof. The proof is mainly based on Theorem E.4, and the steps are similar to Lemma B.3 in (Jin et al., 2019) and Lemma 3.1 in (Wang et al., 2020b) and we omit here. ˝ Lemma E.6 (Bias Accumulation in Alg 5). On the induction condition 4.5 and on the events in Theorem E.4 which holds with probability 1´ δ{2, if
ε0 ď βξ
2H (27)
in Algorithm 5, for arbitrary R̄ generated, we have:
V ˚1 ps1; R̄q ´ V π̄1 ps1; R̄q ď 3βξ
where recall that we use V πps; R̄q to denote the value function with R̄ as reward function.
Proof. We will use πhp¨q :“ arg maxaQhp¨, aq to denote the optimal policy w.r.t. the Q function without discretization, although we do not deploy it in practice. According to Lemma E.2, we should have maxs,h |Qhps, πpsqq ´Qhps, π̄psqq| ď 2ε0 for arbitrary h P rhs. Recall that π̄ “ π̄1 ˝ π̄2... ˝ π̄h V ˚1 ps1q ´ V π̄1 ps1q ď V1ps1q ´ V π̄1 ps1q (Lemma E.5; Overestimation) “Q1ps1, π1ps1qq ´Qπ̄1 ps1, π̄1ps1qq ď Q1ps1, π̄1ps1qq ´Qπ̄1 ps1, π̄1ps1qq ` 2ε0 (Lemma E.2) “Es1„d1,a1„π̄1rmintφps1, a1qwJ1 ` u1ps1, a1q, Hu ´ P2V2ps1, a1q ` P2V2ps1, a1q ´ P2V π̄2 ps1, a1qs ` 2ε0 ďEs1„d1,a1„π̄1,s2„P2p¨|s1,a1qrV2ps2q ´ V π̄ 2 ps2qs ` 2βEs1„d1,a1„π̄1r}φps1, a1q}Σ´11 s ` 2ε0 ď...
ď2βEs1„d1,a1,s2,...,sh´1,ah´1„π̄r h´1 ÿ
rh“1
}φps rh, arhq}Σ´1
rh
s ` 2ph´ 1qε0 ` Esh,ah„π̄rVhpshq ´ V π̄h pshqs
ď2βξ ` 2hε0 ď 3βξ (Condition 4.5) ˝
Lemma E.7 (Bias of Linear Regression in Alg 6). During the running of Alg 2, on the event of E in Theorem E.4, which holds with probability 1´δ{2, for arbitrary h P rHs,rh P rh´1s, and arbitrary π, pwπ
rh and pV π rh`1 occurs in Alg 6, we have:
|φps, aqJ pwπh ´ ÿ s1PS Phps1|s, aqpV π rh`1ps 1q| ď β}φps, aq}Σ´1h
where β is the same as Lemma E.5.
The proofs for the above Lemma is based on Theorem E.4 and Claim 3 and is similar to Lemma 3.1 in (Wang et al., 2020b), so we omit it here. Lemma E.8 (Policy Evaluation Error in Alg 6). During the running of Algorithm 2, on the events of E in Theorem E.4, which holds with probability 1´δ{2, and on the induction condition in 4.5, for arbitrary h P rHs and i, j P rds, and arbitrary policy π and their evaluation results pV π Algorithm 6, we have:
|V πps1; rRijq ´ pV π1 ps1q| ď βξ
where we use rRij to denote the reward function used in Algorithm 6.
Proof. As a result of Lemma.E.7 , for arbitrary rRij , we have:
|pV π1 ps1q ´ V π1 ps1; rRijq| “| pQπ1 ps1, a1q ´Qπ1 ps1, a1; rRijq|
“|φps1, a1qJ pwπ1 ´ ÿ
s2
Phps2|s1, a1qV πps2; rRijq|
ď|φps1, a1qJ pwπ1 ´ ÿ
s2
Phps2|s1, a1qpV π2 ps2q| ` Eπ|pV π2 ps2q ´Qπ2 ps2, πps2q; rRijq|
ďβ}φps1, a1q}Σ´11 ` Es2 |V πps2q ´Qπ2 ps2, πps2q; rRijq|
...
ďβEs1,a1,...,sh´1,ah´1„πr h´1 ÿ
t“1 }φpst, atq}Σ´1t s
ďβ h´ 1 H ξ ď βξ
˝

heading: E.6 MAIN THEOREM AND PROOF
text: Now, we restate Theorem 4.4 in a formal version below: Theorem E.9 (Formal Version of Theorem 4.4). For arbitrary 0 ă ε, δ ă 1, there exists absolute constants ci, cβ and cN , such that by choosing
imax “ ci d
ν4min log
d
νmin , β “ cβd
c
log dH
εδνmin ,
N “ c ´ H2d3 ε2ν2min ` H 2d7 ν14min ¯ log2 dH εδνmin , ε0 “ 1 N .
with probability 1 ´ δ, after K “ H deployments, by running Alg 4 with the collected dataset D “ tD1, ..., DHu and arbitrary r satisfying the linear assumption in A (in Line of Algorithm 2), we will obtain a policy pπ such that V π1 ps1; rq ě V π ˚ 1 ps1; rq ´ ε.
As additional guarantees, after h deployments, by running Alg 4 with the collected dataset tD1, D2..., Dhu and reward function r, we will obtain a policy π|h which is ε-optimal in the MDP truncated at step h.
Proof. We will use Σh,i :“ 2I ` ři´1 j“1 Eπj rφpsh, ahqφpsh, ahqJs to denote the matrix which rΣh,i approximates in Alg. 2, and use Rh,i :“ b
φp¨, ¨qJΣ´1h,iφp¨, ¨q to denote the reward function used in Alg 5 if the covariance matrix estimation is perfect (i.e. rΣh,i “ Σh,i). The proof consists of three steps. In step 1, we try to show that the inner loop of Alg 2 will terminate and Πh will contain a set of exploratory policies. In step 2, we will analyze the samples generated by a mixture of policies in Πh. In the last step, we determine the choice of hyper-parameters and fill the gaps of pre-assumed constraints and induction conditions.
Step 1: Exploration Ability for Policies in Πh In the inner loop (line 5 - 12) in Algorithm 2, our goal is to find a set of policies Πh, such that if the algorithm stops at iteration i, the following uncertainty measure is as small as possible
V ˚h,i`1ps1;Rh,iq :“ maxπ Eπr}φpsh, ahq}Σ´1h,is (28)
To achieve this goal, we repeatedly use Alg 6 to estimate the covariance matrix of the policy and append it to rΣh,i as an approximation of Σh,i, and use Alg 5 to find a near-optimal policy to maximizing the uncertainty-based reward function rR, by sampling trajectories with which we can reduce the uncertainty Q˚h,i in Eq.(28).
First, we take a look at the estimation error of the accumulative covariance matrix when running Algorithm 2. On the conditions in Lemma E.8, we can bound the elementwise estimation error of Σh,i:
|prΣh,iqjk ´ pΣh,iqjk| ď i ¨ βξ, @j, k P rds As a result of Lemma E.11, we have:
| rRh,ipsh, ahq ´Rh,ipsh, ahq| “| b φJrΣ´1h,iφ´ b φJΣ´1h,iφ|
ď
d
i ¨ dβξ 1´ i ¨ dβξ ď
d
imaxdβξ
1´ imaxdβξ
ďν 2 min
8 (29)
where the last but two step is because we at most repeat it imax iterations at each layer h, and we introduce the following constraint for ξ during the derivation, to make sure the bias is small and all the iterms occurs in the derivation is well defined:
ξ ď ν 4 min
32imaxdβ (30)
Next, we want to find a good choice of imax to make sure Vh,i`1 will not always be large and the for-loop will break for some i ď imax. We first provide an upper bound for Vh,i`1:
Vh,i`1ps1q ďV πh,i`1ps1; rRh,iq ` βξ (Lemma E.5) ďV π̄h,i`1ps1; rRh,iq ` 4βξ (V π ´ V π̄ ď V ˚ ´ V π̄; Lemma E.6)
ďV π̄h,i`1ps1;Rh,iq ` 4βξ ` ν2min
8 (bias of reward)
ďV π̄h,i`1ps1;Rh,iq ` ν2min
4 (Constraints on ξ in Eq.(30))
Next, we try to show that V π̄h,i`1ps1;Rh,iq can not always be large. According to Elliptical Potential Lemma in Lemma C.1, we have:
imax ÿ i“1 V π̄h,i`1ps1;Rh,iq “ imax ÿ i“1 Eπ̄h,i`1r}φpsh, ahq}Σ´1h,is
ď imax ÿ
i“1
c
Eπ̄h,i`1r}φpsh, ahq}2Σ´1h,i s
ď
g f
f eimax
imax ÿ i“1 Eπ̄h,i`1r}φpsh, ahq}2Σ´1h,i s
“
g f
f eimax
imax ÿ i“1 TrpEπ̄h,i`1rφpsh, ahqφpsh, ahqJsΣ´1h,iq
ď a 2imaxd logp1` imax{dq
where in the last step, we use the definition of Σh,i. Therefore,
min i V π̄h,i`1ps1;Rh,iq ď
1
imax
imax ÿ i“1 V π̄h,i`1ps1;Rh,iq ď
d
2 d logp1` imax{dq
imax
In order to guarantee mini V π̄h,i`1ps1;Rh,iq ď ν2min{8, we require: d
2 d logp1` imax{dq
imax ď ν2min{8
which can be satisfied by:
imax “ ci d
ν4min log
d
νmin (31)
for some absolute constant ci.
Combining the above results, we can conclude that the inner loop in Alg 2 will break at some i ă imax, such that Vh,i`1 ď 3ν2min{8, and guarantee that:
max π Eπr}φpsh, ahq}Σ´1h,is :“V ˚ h,i`1ps1;Rh,iq
ďV ˚h,i`1ps1; rRh,iq ` ν2min
8 (reward estimation error Eq.(29))
ďVh,i`1ps1q ` ν2min
8 (Overestimation in Lemma E.5)
ďV π̄h,i`1ps1;Rh,iq ` ν2min 4 ` ν 2 min 8 ďν 2 min
2
Step 2: Policy Deployment and Concentration Error For uniform mixture policy πh,mix :“ UnifpΠhq, by applying Lemma E.13, Lemma E.14 and the results above, we must have:
max π
Eπr b φpsh, ahqJpI `NEπh,mixrφφJsq´1φpsh, ahqs
“max π Eπr
d
φpsh, ahqJpI ` N
|Πh| |Πh|Eπh,mixrφφJsq´1φpsh, ahqs
ď
d
2
1`N{|Πh| max π
Eπr b φpsh, ahqJpI ` |Πh|Eπh,mixrφφJsq´1φpsh, ahqs
ď
d
1
1`N{imax νmin ď
c
imax N νmin
and this is the motivation of breaking criterion in Line 8 in Alg 2.
In the following, we will use Σ´h :“ Σh ´ I “ řN n“1 φpsh,nah,nqφpsh,n, ah,nqJ to denote the matrix of sampled feature without regularization terms, according to Lemma E.10, with probability 1´ δ{2, we have:
} 1 N σmaxpNEπh,mixrφφJs ´ Σ´h q} ď 4? N log 8dH δ , @h P rHs
Follow the same steps in the proof of Lemma E.14, we know that
σminpNEπh,mixrφφJsq “ N |Πh| σminp|Πh|Eπh,mixrφφJsq ě N |Πh| ě N imax .
As a result,
min x:}x}“1 xJΣhx “ min x:}x}“1 xJpI `NEπh,mixrφφJsqx` xJpNEπh,mixrφφJs ´ Σ´h qx
ěσminpI `NEπh,mixrφφJsq ´ σmaxpNEπh,mixrφφJs ´ Σ´h q
ě1` p N 2imax
´ 4 ? N log 8dH
δ q
which implies that, as long as
N ě 16i2max log 2 8dH
δ (32)
we have
σmaxpΣ´1h q ď 1
1`N{2imax ´ ? N log 8dHδ
ď 4imax N
Therefore, for arbitrary π, we have:
|Eπr b φpsh, ahqJpI `NEπh,mixrφφJsq´1φpsh, ahqs ´ Eπr b φpsh, ahqJpΣhq´1φpsh, ahqs|
ďEπr b |φpsh, ahqJpI `NEπh,mixrφφJsq´1φpsh, ahq ´ φpsh, ahqJpΣhq´1φpsh, ahq|s
ďEπr c |φpsh, ahqJ ´ pI `NEπh,mixrφφJsq´1 ´ pΣhq´1 ¯ φpsh, ahq|s
“Eπr b |φpsh, ahqJpI `NEπh,mixrφφJsq´1 ` NEπh,mixrφφJs ´ Σ´h ˘ pΣhq´1φpsh, ahq|s
ď c
σmaxppI `NEπh,mixrφφJsq´1q 4imax N σmaxpNEπh,mixrφφJs ´ Σ´h q
ď
d
1 1`N{imax 16imax? N log 8d δ (imaxEπh,mixrφφJs ľ |Πh|Eπh,mixrφφJs ľ 1)
ď4imax N3{4
c
log 8dH
δ
As a result,
max π
Eπr b φpsh, ahqJpΣhq´1φpsh, ahqs
ďmax π
Eπr b φpsh, ahqJpI `NEπh,mixrφφJsq´1φpsh, ahqs ` 4imax N3{4
c
log 8dH
δ
ď c
imax N νmin ` 4imax N3{4
c
log 8dH
δ
In order to make sure the induction conditions holds, we need c
imax N νmin ` 4imax N3{4
c
log 8dH
δ ď ξ{H
As long as we tighten the constraint in 32 to:
N ě 256 i 2 max
ν4min log2
8dH δ “ rOp d
2
ν12min q (33)
the induction conditions can be satisfied when
2
c
imax N νmin ď ξ{2H
or equivalently,
N ě 16H 2ν2minimax ξ2 “ Op H 2d ξ2ν2min q
Step 3: Determine Hyper-parameters
(1) Resolution ε0 Recall that we still have a constraint for Zh in (24)
I ` ΣR ľ ε0
2
4 I,
4
ε02 I ľ 2I ` ΣR
Since we already determined imax in Eq.(31), also recall our constraints on ξ in (30) the above constraints for ε0 can be satisfied as long as:
ε0 ď c 1
imax (34)
Combining all the constraints of ε0, including (23), (25), (27) and (34), we conclude that:
ε0 ď mint 1
N , β? N ` 1 , 1? imax , βξ H u “ 1 N
(2) Induction error ξ Besides the constraint in (30), we need another one to make sure the quality of the final output policy. By applying Lemma D.3 for planning algorithm Alg. 2, if the induction condition (4.5) holds till h P rHs, Alg. 4 will return us a policy pπ such that:
V ˚ ´ V π ď 2βmax π
Eπr H ÿ
rh“1
}φps rh, arhq}Σ´1
rh
s ď 2βξ
To make sure V ˚ ´ V pπ ď ε, we require ξ ď ε2β , which implies that
ξ ď mint ν 4 min 32imaxdβ , ε 2β u
Choice of N and β Since ε0 “ 1N , by plugging it into Eq.(26), we may choose β to be:
β “ c2βd c log dHN
δ
Now, we are ready to compute N . When ξ “ ε2β ď ν4min 32imaxdβ , we have:
N “ Op H 2d ξ2ν2min q “ Op H 2d3 ε2ν2min q log dH
εδνmin and otherwise, we have:
N “ Op H 2d ξ2ν2min q “ OpH 2d7 ν14min q log dH
εδνmin Combining the additional constraint to control the concentration error in Eq.(33), the total number of complexity would at the level:
N ě c ´ H2d3 ε2ν2min ` H 2d7 ν14min ¯ log2 dH
εδνmin and therefore,
β “ cβd c log dH
δενmin for some cβ .
Near-Optimal Guarantee Under the events in Theorem E.4, considering the failure rate of concentration inequality in Step 2, we can conclude that the induction condition holds for h P rHs with probability 1´ δ. Combining our discussion about choice of ξ above, the probability that Alg 2 will return us an ε-optimal policy would be 1´ δ. The additional guarantee in Theorem E.9 can be directly obtained by considering the induction condition at layer h P rHs. ˝

heading: E.7 TECHNICAL LEMMA
text: Lemma E.10 (Matrix Bernstein Theorem (Theorem 6.1.1 in (Tropp, 2015))). Consider a finite sequence tSku of independent, random matrices with common dimension d1 ˆ d2. Assume that
ESk “ 0 and }Sk} ď L for each index k Introduce the random matrix
Z “ ÿ
k
Sk
Let vpZq be the matrix variance statistic of the sum: vpZq “maxt}EpZZ˚q}, }EpZ˚Zq}u
“maxt} ÿ
k
EpSkS˚kq}, } ÿ
k
EpS˚kSkq}u
Then,
E}Z} ď a 2vpZq logpd1 ` d2q ` 1
3 L logpd1 ` d2q

heading: Furthermore, for all t ě 0
text: Pt}Z} ě tu ď pd1 ` d2q exp ´ ´t2{2 vpZq ` Lt{3 ¯
Lemma E.11 (Matrix Perturbation). Given a positive definite matrix A ą I and ∆ satisfying |∆ij | ď ε ă 1{d, define matrix A` “ A ` ∆, then for arbitrary φ P Rd with }φ} ď 1, we have:
A` ą 0, |φJpA` ´Aqφ| ď dε, |φJpA´1` ´A´1qφ| ď dε
1´ dε which implies that
}A`} ď }A} ` }∆} ď }A} ` }∆}F ď }A} ` dε, }A´1` } ě }A´1} ´ dε
1´ dε

heading: Moreover,
text: |}φ}A´1` ´ }φ}A´1 | ď b |}φ}2 A´1` ´ }φ}2 A´1 | ď
c
dε
1´ dε
Proof. First of all, easy to see that σmaxp∆q ď }∆}F ď dε
and therefore we have σminpA`q “ min
x:}x}“1 xJAx` xJ∆x ą 1´ dε ą 0.
where we use σmin and σmax to denote the smallest and the largest sigular value, respectively, and use } ¨ }F to refer to the Frobenius norm. Therefore, |φJpA` ´Aqφ| “ |φJ∆φ| ď dε and
|φJpA´1` ´A´1qφ| “ |φJA´1` pA` ´AqA´1φ| ď σmaxpA´1` qσmaxpA` ´AqσmaxpA´1q ď dε 1´ dε Moreover,
|}φ}A´1` ´ }φ}A´1 | ď b |}φ}A´1` ´ }φ}A´1 | ¨ |}φ}A´1` ` }φ}A´1 | “ b |φJpA´1` ´A´1qφ| ď c dε
1´ dε ˝
Next, we will try to prove that, with a proper choice ofN , Algorithm 2 will explore layer h to satisfy the recursive induction condition. Lemma E.12 (Random Matrix Estimation Error). Denote Λπh “ EπrφφJs. Based on the same induction condition 2, we have:
|}φ}pΛπq´1 ´ }φ}ppΛπq´1 | ď c dε
1´ dε , @}φ} ď 1
Proof. Based on Lemma E.8, we have:
|Λπij ´ pΛπij | ď h´ 1 H ε ď ε
and as a result of Lemma E.11, we finish the proof. ˝ Lemma E.13. Given a matrix A ľ λI with λ ą 0, and φ satisfies }φ} ď 1, then we have:
φJpcI ` nAq´1φ ď λ` c λn` cφ JpcI `Aq´1φ, @n ą 1, c ą 0
Proof. Because A ľ λI , we have
cI ` nA “cI ` cpn´ 1q λ` c A` pn´ cpn´ 1q λ` c qA ľ ´ 1` λpn´ 1q λ` c ¯ cI ` pn´ cpn´ 1q λ` c qA
“λn` c λ` c ´ cI `A ¯
Therefore,
φJpcI ` nAq´1φ ď λ` c λn` cφ JpcI `Aqφ
˝ Lemma E.14. Given a matrix A ľ 0, suppose maxπ Eπr}φ}pcI`Aq´1s ď rε ď ν2min{p2 ? cq, where c ą 0 is a constant, where νmin is defined in Definition 4.3, we have:
max π
Eπr}φ}pcI`nAq´1s ď
d
c` 1? cpc` nqrε
Proof. Because }φ}pcI`Aq´1 ď }φ}pcIq´1 ď 1{ ? c, we must have:
max π TrppcI `Aq´1EπrφφJsq “ max π Eπr}φ}2pcI`Aq´1s ď 1? c max π Eπr}φ}pcI`Aq´1s ď rε? c
Consider the SVD of A “ UJΣU with Σ “ pσiiqi“1,...,d and U “ ru1, u2..., uds, then we have:
@π, rε? c ě TrppcI `Aq´1EπrφφJsq “ TrppcI ` Σq´1UJEπrφφJsUq “
d ÿ
i“1
Eπr|φJui|2s c` σii .
According to the Definition 4.3, we have:
rε? c ě maxπ Eπr|φ Jui|2s c` σii ě ν 2 min c` σii , @i P rds
which implies that
σii ě ? cν2min rε ´ c ě c, @i P rds
By applying Lemma E.13 and assign λ “ c, we have:
max π Eπr}φ}pcI`nAq´1s ď max π
b
Eπr}φ}2pcI`nAq´1s ď maxπ
c
2c
c` cnEπr}φ} 2 pcI`Aq´1s ď
d
2? cp1` nqrε
˝

heading: E.8 MORE ABOUT OUR REACHABILITY COEFFICIENT
text: Recall the definition of reachability coefficient in (Zanette et al., 2020) is:
min hPrHs min }θ}“1 max π |EπrφhsJθ|
Easy to see that, for arbitrary θ with }θ} “ 1, we have
max π
b
EπrpφJh θq2s ě maxπ Eπr|φ J h θ|s ě max π |EπrφJh θs|
Therefore,
νmin “ min hPrHs νh “ min hPrHs min }θ}“1 max π
b
EπrpφJh θq2s ě min hPrHs min }θ}“1 max π |EπrφJh θs|
Besides, according to the min-max theorem, νh is also lower bounded by b
maxπ σminpEπrφhφJh sq, to see this,
max π σminpEπrφhφJh sq “ max π min }θ}“1 θJEπrφhφJh sθ “ max π min }θ}“1 EπrpφJθq2s ď min }θ}“1 max π EπrpφJθq2s
In fact, the value of maxπ σminpEπrφhφJh sq is also related to the ”Well-Explored Dataset” assumption in many previous literature in offline setting (Jin et al., 2021b), where it is assumed that there exists a behavior policy such that the minimum singular value of the covariance matrix is lower bounded. Therefore, we can conclude that our reachability coefficient νmin is also lower bounded by, e.g. c in Corollary 4.6 in (Jin et al., 2021b).

heading: F EXTENDED DEPLOYMENT-EFFICIENT RL SETTING

heading: F.1 SAMPLE-EFFICIENT DE-RL
text: In applications such as recommendation systems, the value of N cannot exceed the number of users our system serves during a period of time. Therefore, as an interesting extension to our framework, we can revise the constraint (b) in Definition 2.1 and explicitly assign an upper bound for N . Concretely, we may consider the following alternatives: (b’) The sample size N ď dc1Hc2ε´c3 logc4 dHεδ , where c1, c2, c3, c4 ą 0 are some constant fixed according to the real situation. Under these revised constraints, the lower bound for K may be different.
In fact, given constraints in the form of N ď N0, our results in Section 4 already implies an upper bound for K, since we can emulate 1 deployment of our algorithm that uses a large N ą N0 by deploying the same policy for rN{N0s times. However, this may result in sub-optimal deployment complexity since we are not adaptively updating our policy within those N{N0 deployments. It would be an interesting open problem to identify the fine-grained trade-off between K and N0 in such a setting.

heading: F.2 SAFE DE-RL
text: Monotonic Policy Improvement Constraint In many applications, improvement of service quality after policy update is highly desired, and can be incorporated in our formulation by adding an additional constraint into Def 2.1:
pcq Jpπi`1q ě Jpπiq ´ ε. (35) Because we require the deployed policy has substantial probability to visit unfamiliar states so that the agent can identify the near-optimal policy as shown in Def 2.1-(a), we relax the strict policy improvement with an small budget term ε ą 0 for exploration.
Trade-off between Pessimism and Optimism The balance between satisfying two contradictory constraints: (a) and (c), implies that a proper algorithm should leverage both pessimism and optimism in face of uncertainty. In Algorithm 7, we propose a simple but effective mixture policy srategy, where we treat pessimistic and optimistic algorithm as black boxes and mix the learned policies with a coefficient α. One key property of the mixed policy is that:
Algorithm 7: Mixture Policy Strategy 1 for k=1,2,...,K do 2 D “ tD1, D2, ..., Dku 3 πk,pessim Ð PessimismBased OfflineAlgorithmpDq 4 πk,optim Ð OptimismBased BatchExplorationStrategypDq 5 // Mix policy in trajectory level, i.e. w.p. 1´ α, τ „ πpessim; w.p. α, τ „ πoptim 6 πk Ð p1´ αqπk,pessim ` απk,optim 7 Dk “ tτn „ πk,@n P rN su 8 end
Property F.1 (Policy improvement for mixture policy).
Jpπkq ´ Jpπk´1q ě Jpπk,pessimq ´ Jpπk´1q ´Opαq (36)
As a result, as long as the offline algorithm (which we treat as a black box here) has some policy improvement guarantee, such as (Kumar et al., 2020; Liu et al., 2020; Laroche et al., 2019), then Eq.(36) implies a substantial policy improvement if α is chosen appropraitely. Besides, if we use Algorithms in Section 4.1 or 4.2, and collecting rN “ ΘpN{αq samples, the guarantees in Theorem 4.1 and Theorem 4.4 can be extended correspondingly. Therefore, Alg 7 will return us a near-optimal policy after K deployments while satisfying the safety constraint (c) in (35).

Review summaries:
The authors consider the problem of deployment complexity in reinforcement learning problems, where we want to reduce the number of cycles an agent is typically deployed for interacting with the environment. In the context of a linear MDP, the authors prove an information theoretic lower bound. Further, they also propose algorithms which achieve this optimal deployment efficiency. 

The paper focuses on the theoretical properties of Deployment Efficient Reinforcement Learning, DE-RL, focusing on linear MDPs. Deployment complexity is defined as the number of times that a different policy is selected to collect data, and an algorithm is said to be deployment efficient if the number of deployments is as small as possible and the number of trajectories per iteration is polynomial.  In section 3, the authors provide a lower bound for the task, under both deterministic and stochastic policies.  In section 4, the authors provide detailed algorithms for DE-RL, as well as relevant upper bounds. In the deterministic case the upperbound matches lower bound up to constant factors, and in the stochastic case the upperbound matches the lower bound *up to log factors* and as long as $\nu_{\textrm{min}}$ is bounded.

This paper studies deployment-efficient reinforcement learning and provides a theoretical perspective. In this setting, this paper provides lower bounds and upper bounds respectively for determinisitc policies and arbitrary policies when the MDPs have linear structures. The deployment complexity is near-optimal.

The paper presents a theoretical perspective on deployment efficiency in linear MDPs. The paper formalizes the notion of deployment complexity and presents an information-theoretic lower bound for worst-case deployment complexity of any algorithm, identifying horizon as the main bottleneck for deployment efficiency (in addition to feature dimension when restricting to deterministic policies). The paper then presents two algorithms (for deterministic or stochastic policies) matching the lower bounds.