Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality
Authors: Jiawei Huang
Jinglin Chen
Li Zhao
Tao Qin
Nan Jiang
Tie-Yan Liu
Venue: ICLR 2022 Spotlight (2022)
Keywords: reinforcement learning theory
deployment efficiency
linear MDP

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 \emph{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.

Published as a conference paper at ICLR 2022
TOWARDS DEPLOYMENT-EFIICENN REINFORCEMENT LEARNING: LOWER BOUND AND OPTIMALITY
Jiawei Huang"t, Jinglin Cheni, Li Zhaot, Tao Qint, Nan Jiangt, Tie- Yan Liuž
i Department of Computer Science, University of Illinois at Sibana-Champalr {jiaweih, jingline, nanjiang) weeiiiiiniiss.... $ Microsoft Research Asia
{lizo, taoqin, tyllu]emicrosoft..cm
ABSTRACT
Deployment efficiency is an important criterion for many real-world applications of reinforcement learning (RL). Despite the community' 's increasing interest, there lacks formal theoretical formulation for the problem. In this paper, we propose such a formulation for deployment-effice effficcceee RI. (DE-RL) from an "optimization with constraints" perspective: we are interested in exploring an MDP and obtain- ing a near-optimal policy within minimal deployment complexity, whereas in each deployment the policy can sample 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 -theorettc lower bounds, and provide algorithms that achieve the optimal deployment efficiency. Moreover, our formulation for DE-RL is flexible and serve as building block for other prac- tically relevant settings; we give "Safe DE-RL" and "Sample-Efficit" Efficient DE-RL" as two examples, which may be worth future investigation.
INTRODUCTION
In many real-world applications, deploying new policy to replace the previous one is costly, while generating 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 al.) 2013). and healthcare (Yu et al. 2019). the new recommendation, teaching, or medical treatment strategy must pass several internal tests 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 short period of time if the system serves 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. 2202]) either their settings or methods have limitations the scenarios described above, or a formal mathematical formulation is missing. We defer detailed discussion of these related works to Section [.]
In order to close the gap between existing RL settings and real-world applications requiring high deployment efficiency, first contribution is to provide formal definition and tractable objective for Reployment-Efficccen Reinforcement Learning (DE-RL) via an "optimization with constraints" perspective. Roughly speaking,
interested in minimizing the number of deployments K under two constraints: (a) after deploying K times, the algorithm can return a near-optimal policy, and (b) the number of trajectories collected in each deployment, denoted 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 K as deployment complexity.
Work done during the internship at Microsoft Research Asia.

---

Published as a conference paper at ICLR 2022
To provide more quantitative understanding, we instantiate our DE-RL framework in finite-horizer linear MDP M (Jin et al. 2019) and develop the essential theory. The main questions we address are:
Q1: What is the optimum of the deployment efficiency in our DE-RL setling?
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 fo- cused on upper and lower bounds for algorithms using deterministic policies (Jin et al. 2019) Wang] ett al., 22020b; Gao et al., (021). As we will show, the origin of the difficulty in optimizing deploy- ment 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 we answer QI by providing information seformationnthhoortiic lower bounds for the required number of deployments under the constraints of (a) and (b) in Def 2.1 We establish Q(dH) and ((H)) lower bounds for algorithms with and without the constraints of de- ploying deterministic policies, respectively. Contrary to the impression given by previous empirical works (Matsushima et al.) [202]) 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-fre" RI. (e.g.. [Wang et al., 2020a), it is shown that RL. problem not significantly harder than bandits (i.e., when H 1) when consider sample complexity. In contrast, the H depen- dence in our lower bound reveals some fundamental hardness that is specific to long-horizon RL, particularly in the deployment-effccientt setting. Such hardness results were originally conjectured by [iann & 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. propose an algorithm deploying deterministic policies, which is based on Least-Square Value Iteration with reward bonus (Jin et al. 2219)) and layer-by-layer exploration strategy, and can return an e-optimal policy within O(d)) deployments. As part of its analysis, we prove Lemma 4.2 as technical contribution, which can be regarded as batched finite-sample version of the well-known "Elliptical Potential Lemma" (Carpentte et 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 jet 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 similar problem, but their algorithm is madel-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 model-free layer-by-layer exploration algorithm based on novel covariance matrix estimation technique, and prove that it requires O(Hl (H) deployments to return an e-optimal policy, which only differs from the lower bound (((H) 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 al. 2020 Agarwal et al. 2020b; Modi 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, DE-RL set- ting can serve as a building block for more advanced and practically relevant settings where op- timizing the number of deployments is an important consideration. In Appendix [F] we propose two potentially interesting settings: "Safe DE-RL" and "Sample-Etticien DE-RL", by introducing constraints regarding safety and sample efficiency, respectively.
Although we focus linear MDPs, the core idea can be extended to more general settings such RI. with general function approximation (Kong et al. (022).
Athhough WWang et al. (2020a) considered stationary MDP, as shown in our Corollary 3.3 the lower bounds of deployment complexity still related to H.
2

---

Published as a conference paper at ICLR 2022
1.1 CLOSELY RELATED WORKS
We defer the detailed discussion of previous literatures about pure online RL and pure offline RL 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 inves- tigation. In existing theoretical works, low switching cost is concept closely related to deployment
efficiency, and has been studied in both bandit (Esfandiari et al.] 2020 Han et al.] [220]] Gu et al.)
2021 Ruan et al.] 2021) and RL settings (Bai et al. 2020; Gao al. 2021; Kong et al. 2021)
Another related concept is concurrent RL, as proposed by Guo & Brunskill 20155). We highlight
the difference with them in two-folds from problem setting and techniques.
As for the problem setting, existing literature low switching cost mainly focuses on sub-linear regret guarantees, which does not directly implies a near-optimal policy after a number of policy deployments" 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 recommenda- tion or education systems, once deployed, a policy usually needs to interact with the population of users for 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 change the policy immediately once collecting enough data for policy update, and 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 casier 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 reflected in our lower bounds- exploration can be done much more deployment--fficiientyy and we provide stochastic policy algorithm that achieves an Ö(H) deployment complexity and overcomes the (2(HH lower bounds for deterministic policy algorithms (Gao et al. 2021).
2 PRELIMINARIES
|-] denotes the ceiling function. Unless otherwise specified, for vector x E Rd and matrix X e Rdxd ||||| denotes the vector 12 norm of x and |X| denotes the largest singular value of X. We will use standard big-oh notations (()), 0()), and notations such as Ö(-) to suppress logarithmic factors.
Notation Throughout our paper, for Zt, we will denote [n] {1, n... nn..................
2.1 EPISODIC REINFORCEMENT LEARNING
We consider an episodic Markov Decision Process denoted by H..... where S is the state space, A is the finite action space, H is the horizon length. and P (Pr) and r {rx denote the transition and the reward functions. At the beginning of each episode, the environment will sample an initial state $ from the initial state distribution dj. Then, for each time step h [M], the agent selects an action пд E A, interacts with the environment, receives a reward (n(,,, an),, and transitions to the next state 11 The episode will terminate once H is reached.
(Markov) policy nn at step a function mapping from - A(A), where A(A) denotes the probability simplex over the action space. With a slight abuse of notation, when (T(+) is deterministic policy, we will assume (.)-) + A. A full (Markov) policy т = {TI, :2, TH specifies such mapping for each time step. We use V (s) and (s, a) denote the value function
Although the conversion from sub- linear regret to polynominal sample complexity is possible ("online-to- batch"), "). we show in Appendix A that to achieve accuracy after conversion, the number of deployments of previous low-switching cost algorihhms has dependence on E, whereas our guarantce does not.
3

---

Published as a conference paper at ICLR 2022
and Q-function at step h [H]. which are defined as:
(s)
E
Σ
The (sw an) aw) n] (s,
E Σ
The (sw, 8, Oh a, n
W-hh
w-h
We also use (-) and (+ to denote the optimal value functions and use x² denote the optimal policy that maximizes the expected return J(x) = E|Σn- r(sh, an)[ In some occa- sions, we use V rs; and (7 r) denote the value functions with respect to the reward function for disambiguation purposes. The optimal value functions and the optimal policy will be denoted by V (*(ss;) r), (* a)); n.. respectively.
Non-Markov Policies While focus 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 the history (e.g.. S₁ A R... x S x AA-1 x x S₁ - A for deterministic policies); our algorithm for arbitrary policies deploys a mixture of deterministic Markov policies, which corresponds to choosing deterministic policy from given set at the initial state, and following that policy for the entire trajectory. This can be viewed as non-Markov stochastic policy.
2.2 LINEAR MDP SETTING
We mainly focus the linear MDP (Jin et al. 2019) satisfying the following assumptions:
Assumption A (Linear MDP Assumptions). An MDP ,M- = (S. A. H, P. is said to be linear MDP with feature map @ A Rd if the following hold for any h [H]:
There are unknown signed measures ph = (u) uh ...., urx))) (1))) over such that for any 65) E 8 x A S, P, (uu(5') o(s a))
There exists an unknown vector 0g E I&d such that for any (s, a) E Sx..r = (0(8, O))
Similar to Jin al. 2019) and Wang al. (2020b). without loss of generality, we assume for all (s. a) S and [H] [ a)l < |a Vd. and ||O,]| vd. In Section we will
refer to linear MDPs with stationary dynamics, which is a special case when P2 MH and 0g.
0, 02
2.3 CONCRETE DEFINITION OF DE-RL
In the following, we introduce formulation for DE-RL in linear MDPs. For discussions of comparison to existing works, please refer to Section T.1
Definition 2.1 (Deployment Complexity in Linear MDPs), We say that an algorithm has a deploy- ment complexity K in linear MDPs if the following holds: given arbitrary linear MDP under Assumption| A for arbitrary E and < < 1, the algorithm will return a policy オ after K deploy- ments and collecting at most N trajectories in each deployment, under the following constraints:
(a) With probability 6, ग is E-optimal, i.e. J(TK) > max, J(x) -E
(b) The sample size N is polynominal, i.e. N poly(d, H, 1 log })) Moreover, N should be fixed a priori and cannot change adaptively from deployment to deployment.
Under this definition, the goal of Deployment-Eficee Efficieen 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 can result degenerate solutions. For example, be exponentially large, we can finish exploration in deployment in the arbitrary policy setting, by deploying a mixture exponentially many policies that form an e-net of the policy space. Alterna- tively, we sample actions uniformly, and use importance sampling (Precup) 2000) to evaluate all of them in an off off-policy manner. None these solutions are practically feasible and are excluded by restriction on N.
is allowed to

---

Published as a conference paper at ICLR 2022
3 LOWER BOUND FOR DEPLOYMENT COMPLEXITY IN RL
In this section, we provide information-theore 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[]] we consider non-Markov policies when we refer to deterministic and stochastic policies in this section, which strengthens our lower bounds as they apply 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 e 4, H and any algo- rithm db that can only deploy deterministic policy at each deployment, there exists a linear MDP M satisfying Assumption such that the deployment complexity of 1o in M is K ((dH).
The basic idea of our construction and the proof is that, intuitively, a linear MDP with dimension and horizon length H has ((dH) "independent directions", while deterministic policies have limited exploration capacity and only reach (1) direction in each deployment, which result in MddH) 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 depend on H and may not be reduced to a constant when H large.
Theorem 3.2. [Lower bound for arbitrary policies, informal] For any d 3 4, H, N and any algo- rithm V which can deploy arbitrary policies, there exists a linear MDP M satisfying Assumption A such that the deployment complexity of 1p in M is K = (N = (H))
The origin of the difficulty can be illustrated by 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 till layer h + 22log (N H)) 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 (log, = ((1) 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 + I.
Stationary vs. non-stationary dynamics Since we consider non-stationary dynamics in As- sump. A one may suspect that the H H-dependence in the lower bound is mainly due to such non- stationarity. We show that this is not quite the case, and the H 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 AŠ,
we can construct a
stationary MDP M- = A, H, P,r) by expanding the state space to S = S x [H] so that the new transition function P and reward function r are stationary across time steps. As a result, given arbitrary d > and H > 2. we can construct a hard non-stationary MDP instance M with dimen- sion d = max 4, d/ H) and horizon h = d/d = min H, d/43, and convert it to a stationary MDP M with dimension d and horizon h = h = min{ H, d/4} < H. If there exists an algorithm which can solve M in K deployments, then it can be used to solve M in 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 3 4 and H > 2, suppose N poly (d, H, L. log })), the lower bound of deployment complexity would be (i for deterministic policy algorithms, and Q Togmas(a/H... 4) NHT) 50(mind, H)) for algorithms which can deploy arbitrary policies.
min(d/4,HH
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 "layered" structure. For example, in Atari games (Bellemare et al. 2013) (where many algorithms like DQN (Mnih et al.) (013)) model the environments as
discounted MDPs) such as Breakout, the agent cannot observe
5

---

Published as a conference paper at ICLR 2022
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, all the states 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 the next section are designed for non- stationary MDPs, they can be extended to stationary MDPs by sharing covariance matrices, and we believe the analyses can also be extended match the lower bound in Corollary 3.3
4 TOWARDS OPTIMAL DEPLOYMENT EFFICIENCY
In this section we provide algorithms with deployment-efffciennyy guarantees that nearly match the lower bounds established in Section 3 Although our lower bound results in Section consider non- Markov policies,
algorithms in this section only use Markov policies (or a mixture of Markov policies, in the arbitrary policy setting), which are simpler to implement and compute and are already near-optimal in deployment efficiency.
Inspiration from Lower Bounds: a Layer-by-Layer Exploration Strategy The linear depen- dence H in the lower bounds implies possibly deployment-efficien manner to explore, which we call a layer-by-layer strategy: conditioning on sufficient exploration in previous h time steps,
poly(d) deployments to sufficiently explore the h-th time step, then we only need H -poly(d) deployments to explore the entire MDP. If we can reduce the deployment cost in each layer from poly(d) (dd) even ( then 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-laye strategy, which will be useful especially in "Safe DE-RL". In Sections 4.1 and we will introduce algorithms based on this idea and provide theoretical guarantees.
4.1 EEPLOYMENT-EPFICIEN RL WITH DETERMINISTIC POLICIES
Algorithm 1: Layer- Batch Exploration Strategy for Linear MDPs Given Reward Func-
tion
Input: Failure probability d O, and target accuracy > 0, 3 < c3 dog/loo(d(dd--e-)) for some C3 > 0, total number of deployments K, batch size N, h1
// h4 denotes the layer explore in iteration ks for all is e [K]
for k = 1, ..., K do
-- (
and V +-(+)
los
for = hR, hA I,..., do
A - 1 -- Y.
of (oR"),
uf((,)) - min
-b((, H)
wh < (At) Σ EN 8thh Vhl (
()(-)) (w o(;)) + rn(,)) + u (.,,H, and vi(()) max Q,(: ())
x arg maxoFd (
end
Define * मt mb.... The unif[mtt1:91 11
12
for n 1,.... N do
Receive initial state A d1 for 1 1, 1,2,.., .,.,, H do Take action aATh (+((T) and observe stm Pa at)
end
Compute AS - 28 - E v Vo(st a (At) ( a.
16
N
Ar & chg then hx+1 < hx: 2H
17
else if h4g = H then return x² else h < hy + 1:
18
19
20
end

---

Published as a conference paper at ICLR 2022
In this sub-section, we focus the setting where each deployed policy is deterministic. In Alg we propose a provably deployment-efficient algorithm built on Least-Square Value Iteration with UCB (Jin et al., 2019 and the "layer-by-layer" strategy. Briefly speaking, deployment k. focus on exploration in previous hNg layers, and compute कÝ, =r,,.. o by running LSVI-UCB in an MDP truncated at step hus After that, we deploy x² to collect N trajectories, and complete the trajectory after time step hig with an arbitrary policy. (In the pseudocode we choose uniform, but the choice is inconsequential) In line 19, compute A& with samples and use it to judge whether should move on to the next layer till all И 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 E, 6 > 0, and arbitrary Og 3 2, as long as Hd de
N 3
CK
H** dack g4o8
log
2CX
where c. is an absolute constant, by choosing
K cgdH + 1.
(1)
Algorithm 7 will terminate at iteration k & K and return us a policy n², and with probability 1 1-6; E, (s) VF" (s1)] & 8.
As an interesting observation, Eq IT) reflects the trade-off between the magnitude of K and N when K is small. To see this, when we increase eк and keep it at the constant level, K definitely increases while N will be lower because its dependence on d, H,&, 5 decreases. Moreover, the benefit of increasing сg is only remarkable when cg small (e.g. we have N d" if CK- = 2, while N = - 2.44 if cg- = 6), and even for moderately large ck. the value of N quickly approaches the limit limex- -x0 N c R log"( Hd ). It is still an open problem that óc
whether the trade-off in Eq is exact or not, and we leave it for the future work.
Another key step in proving the deployment efficiency of Alg. [ is Lem. 4.2 below. In fact, by directly applying Lem. 4.2 to LSVI-UCB (Jin et al. 2019) with large batch sizes, we can achieve O(di)) deployment complexity in deterministic policy setting without exploring in layer-by-layer manner. We defer the discussion and the additional benefit of layer-by-laye strategy to Appx. C.4
Lemma 4.2. [Batched Finite Sample Elliptical Potential Lemma] Consider a sequence of matrices Ag, AN, AN.... ..... (IIN) E Raxd with Au Iaxd and ARN (k-1)) 1JJN + Tx-11 where ib-1
IKN (t=(k-1)N+ 1)N+1 T and max4sKN | < We define: K+ == k [K]] TT(A 1K-1)N $ Dk-1)
Ne]. For arbitrary e < 1, and arbitrary eg 3 if K cR 1, by choosing N >
decK
6x where e is an absolute constant independent with CK, d, H,E, we HO*K log xx ( (Hd) EC
have IC+| & ckd < K/H.
Extension to Reward-free setting Based the similar methodology, we can design algorithms for reward-free setting (Wang et al. 2020b) and obtain OddH) deployment complexity. We defer the algorithms and proots Appx. and summarize the main result in Thm. D.4
4.2 DEPLOYMENT- RL WITH ARBITRARY POLICIES
From the discussion of lower bounds in Section 3 we know that in order to reduce the deployment complexity from ((dH) to ε2( H)) 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 direction in Algorithm Tp. The key challenge is to find a stochastic aalic--bffrre the deployment starts which can sufficiently explore d independent directions.
In Alg. we overcome this difficulty by new covariance matrix estimation method (Alg. in 5 the covariance matrix A E, Loo can
Appx. The basic idea is that, for arbitrary policy π
'In order align with the algorithm in reward-free setting, slightly different from JJin al. 2019 but similar (Wang et al. (020b)), we run linear regression P, Vn instead of Qn.
'Here we mainly focus on evaluating deterministic policy or stochastic policy mixed from finite number of deterministic policies, because for the other stochastic policies, exactly computing the expectation over policy distribution may be intractable.
7

---

Published as a conference paper at ICLR 2022
Algorithm 2: Depployment--ffiieen RL with Covariance Matrix Estimation
Input: Accuracy level E; Iteration number ámax; Resolution En; Reward r; Bonus coefficient |3. for h = 1,2, H do
Initialize Th,1 with an arbitrary deterministic policy Σn. 21, II O}-
for i 1, ,,,,,..,,, fmax do A EstimateCovMatrii((. [1:h-1] [1:h- Th.s) # Alg
Appx
Ep.441 = p0 +
h the
Vi,i41, #h,4+1 SolveOptQ(h,, Piu.- 2(1:b- B, En, Alg if Vh,+++ & 32 min then break;
Appx
T. 1 U(Tr,i+1))
10
end
Σn I, Dr, {}. mh.mix := un)f(II,) for n = 2... N........ do
11
12
18
Sample trajectories with Th,mix Σn Σn 6lsn, an. ( an Dn = Dr. as ap, Thans 8h+1,)
14
15
end
end
17
return ी, - H, DHİ.r)
be estimated element-wise by running policy evaluation for a with Φ.05 as a reward function, where i E [d] and o; denotes the i-th component of vector ø.
However, a new challenge emerging that, because the transition is stochastic, in order to guarantee low evaluation error for all possible policies #4,++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 (see Appendix E to allow for a union bound over the policy space: after computing the Q-function by L.VI-UCB, before converting it to greedy policy, we first project it en-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 En is small enough.
Using the above techniques, in Lines 10 we repeatedly use Alg 6 to estimate the accumulative covariance matrix En,i+1 and further climinate uncertainty by calling Alg to find policy (ap- proximately) maximizing uncertainty-bant
reward function = || p..4. For each It E [H]. layers, the errors of Alg 6 and
inductively conditioning on sufficient exploration previous
Alg 5 will be small, and we will find finite set of policies II, 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 uniform mixture of II and choosing N large enough (Lines 15. 15). Also note that the algorithm does not use the reward information, and is essentially reward-free exploration algorithm. After exploring all H layers, we obtain dataset [D,,... } and can use A for planning with any given reward function satisfying Assump A obtain near-optimal policy.
Deployment complexity guarantees We first introduce a quantity denoted as Vmnnn which mea- sures the reachability to each dimension in the linear MDP. In Appendix E.8 will show that the Pinin is no less than the "cxplorability" coefficient in Definition 2 of Zanette et al. (2020) and v2... is also lower bounded by the maximum of the smallest singular value of matrix Ex [o0 Definition 4.3 (Reachability Coefficient).
Uh min max [0|-1
EE [ [)
Pmin
min Un he he(
Now, are ready state the main theorem of this section, and defer the formal version and its proofs to Appendix [ Our algorithm effectively running reward-free exploration and therefore our results hold for arbitrary linear reward functions.
Theorem 4.4. [Informal] For arbitrary < E,6 < 1, with proper choices of imaxs Eg. 3. we can choose N poly(d, (d, H, log 1 such that, after K deployments, with probability 5,
Viin
8

---

Published as a conference paper at ICLR 2022
Algorithm will collect dataset D (Di,..., DH), and if we run Alg 4 with D and arbitrary reward function satisfying Assump. A we will obtain म, such that (s1;)) (f(it)))
Proof Sketch Next, we briefly discuss the key steps of the proof. Since eu can be chosen to be very small, we will ignore the bias induced by Eo when providing intuitions. Our proof is based on the induction condition below. We first assume it holds after h - deployments (which is true when 1), and then we try to prove at the h-th deployment we can explore layer 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
V (67 : oz) T (x77, (z), & -
(2)
The lh.s. of Eq. measures the uncertainty in previous h layers after exploration. As result, with high probability, the following estimations will be accurate:
A Thii [o( Sh, On (ls), an)) 11 & O(E),
(3)
where |100,00 denotes the entry-wise maximum norm. This directly implies that:
[ Enstilllan & O())..)
where Σn,++1 = 21 E/= ET,, [ an) (s) an) 7 is the target value for Σ to approx-
imate. Besides, recall that Algorithm we use Vo V h as the reward function, and the induction condition also implies that:
[V max (1 an) (n)ss, 9n <O(E).
As a result, if & and the resolution Eo are small enough, Rn,s+1 would gradually reduce the uncer- tainty and Vh,+41 (also max, E,, []] ((s,, an) S + 1) will decrease. However, the bias is at the level O(S), and therefore, in II, do not cover all directions if some directions are very difficult to reach, and the error due to such bias will be the same level of the required accuracy in induction condition, i.c. O This is exactly where the "reachability coefficient" Umii definition helps. The introduction of Mmin provides threshold, and long as & is small enough that the bias is lower than the threshold, each dimension will be reached with substantial probability when the breaking criterion in Line is satisfied. As result, by deploying unif (II,) and collecting sufficiently large dataset, the induction condition will hold till layer H. Finally, combining the guarantee of Alg we complete the proof.
matter how small & is, as long as & > 0, it is still possible that the policies
5 CONCLUSION AND FUTURE WORK
In this paper, we propose a concrete theoretical formulation for DE-RL to fill the gap between ex- isting RL literatures and real-worle applications with deployment constraints. Based our frame- work, we establish lower bounds for deployment complexity in linear MDPs, and provide novel algorithms and techniques 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 the per-deployment sample complexity N. In practice, however, the latter 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.
In real-world applications, safety is also important criterion. The definition for safety criterion in Safe DE-RL L. is still an open problem, but we believe it is an interesting setting since it implies trade-off between exploration and exploitation in deployment-efficient setting.
Safe DE-RL

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
JH's research activities on this work were completed by December 2021 during his internship at MSRA. NJ acknowledges funding support from ARL Cooperative Agreement W911NF-17-2-019,, NSF 124711, and Adobe Data Science Research Award.
REFERENCES
Yasin Abbasi-yadkori,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, Curran Associates, Inc., 2011.
M Mehdi Afsar, Trafford Crump, and Behrouz Far. Reinforcement learning based recommender systems: A survey. arXiv preprint arXiv:2101.06288 2021.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Po-pg: Policy cover directed explo- ration for provable policy gradient learning. arXiv preprint arXi::2007.08459) 2020a.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complex- ity and representation learning of low rank mdps, 2020b.
Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds for randomized least-squares value iteration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6566 6663,6573,20 2021.
Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, pp. 1184-1 1994, 2017.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89-129, 2008.
M. G. Azar, Ian Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In ICML, 2017.
Yu Bai, Tengyang Xie, Nan liang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost, 2020.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal Artificial Intelligence Rexearch, 47: 253-279, 2013.
Marc G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation, 2016.
Abdellah Bennane al. Adaptive educational software by applying reinforcement learning. Infor- matics in Education-An International Journal, 12(1):13-27, 2013.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation, 2018.
Andres Campero, Roberta Raileanu, Heinrich Küttler, Joshua B Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with amigo: Adversarially motivated intrinsic goals. arXiv preprint arXiv:2006. 12122, 2020.
Alexandra Carpentier, Claire Vernade, and Yasin Abbasi-Yadkori. The elliptical potential lemma revisited, 2020.
Jinglin Chen and Nan Jiang. information-thcoredt considerations in batch reinforcement learning.
In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient pac rl with rich observations. Advances in neural information processing systems, 31, 2018.
10

---

Published as a conference paper at ICLR 2022
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning. pp. 1665-1674. PMLR, 2019.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Go-explore: new approach for bard-exploration problems. arXiv preprint 1nXiv:191.119900 2019.
Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for batched bandits, 2020.
Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning, 2021.
Minbo Gao, Tianle Xie, Simon Du, and Lin F. Yang. A provably efficient algorithm for linear markov decision process with low switching cost, 2021.
Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched neural bandits, 2021.
Zhaohan Guo and Emma Brunskill. Concurrent pac rl. In Proceedings of the AAAI Conference Artificial Intelligence, volume 29, 2015.
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W. Glynn, and Yinyu Ye. Sequential batch learning in finite-action linear contextual bandits, 2020.
Elad Hazan, Sham M. Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration, 2019.
Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, pp. -398.. PMLR, 2018.
Nan Jiang and Lihong Li. Doubly robust off- value evaluation for reinforcement learning. In International Conference on Machine Learning, pp. 652-661. PMLR, 2016.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low bellman rank are pac-leamnabe. In International Conference on Machine Learning, pp. 1704-1713. PMLR, 2017a.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal. John Langford, and Robert E. Schapire. Contex- tual decision processes with low Bellman rank are PAC-learnable. Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70, pp. 1704-1713, 2017b.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I. Jordan. Is q-learning provably effi- cient?, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation, 2019.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances Neural Information Processing Systems, 34, 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021b.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(1 12(18))23881174 2013.
Dingwen Kong, R. Salakhutdinov, Ruosong Wang, and Lin E. Yang. Online sub-sampling for rein- forcement learning with general function approximation. ArXiv, abs/2106.07203, 2021.

---

Published as a conference paper at ICLR 2022
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 10118840-844, 2016.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. arXiv preprint arXiv:2006. 2020.
Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. In International Conference on Machine Learning, pp. 3652-3661. PMLR, 2019.
Jongmin Lee, Wonseok Jeon, Byung-Jun Lee, Joelle Pineau, and Kee-Eung Kim. Optidice: Offline policy optimization via stationary distribution correction estimation. arXiv preprint arXiv:2/06. 10783, 2021.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. arXiv preprint 1rXiv:1810.12422 2018.
Yao Liu, Adith Swaminathan, Alckh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Advances in Neural Information Processing Systems, 33:1264 1274, 2020.
Tatsuya Matsushima, Hiroki Furuta, Yutaka Matsuo, Ofrr Nachum, and Shixiang Gu. Deployment- efficient reinforcement learning via model-based offline optimization. In International Confer- ence on Learning Representations, 2021. URL httph::/ httt:::://penneviisse net www.:/rrumffotmooo.o forum? ?id=
3hGNopI4WS
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state ab- straction and provably efficient rich-observation reinforcement learning. In International confer- ence on machine learming, pp. 6961-6971. PMLR, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07035, 2021.
Ted Moskovitz, Jack Parker-Holder, Aldo Pacchiano, Michael Arbel, and Michael I. Jordan. Tactical optimism and pessimism for deep reinforcement learning. 2021.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 95), 2008.
Ofir Nachum, Bo Dai, Ily Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:19/2.02074, 2019.
Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine. Awac: Accelerating online rein-
forcement learning with offline datasets, 2021.
Karl Pertsch, Youngwoon Lee, and Joseph Lim. Accelerating reinforcement learning with learned skill priors. arXiv preprint vrXiv:2010.11944 2020.
Doina Precup. Eligibility traces for off- off-policy policy evaluation. Computer Science Department Faculty Publication Series, pp- 80, 2000.
Yufei Ruan, Jiaqi Yang, and Yuan Zhou. Linear bandits with limited adaptivity and learning distri- butional optimal design, 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
12

---

Published as a conference paper at ICLR 2022
Joel A. Tropp. An introduction matrix concentration inequalities, 2015.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off- policy evaluation. In International Conference on Machine Learning, pp. 9659-9668, PMLR, 2020.
Ruosong Wang, Simon S. Du, Lin Yang, and Sham M. Kakade. long horizon reinforcement learning more difficult than short horizon reinforcement learning?, 2020a.
Ruosong Wang, Simon S. Du, Lin F. Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear function approximation, 2020b.
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. arXiv preprint arXiv:2005.10804 2020c.
Tengyang Xie, Ching- An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. dellman-consistee pessimism for offline reinforcement learning. arXiv preprint vrXiv:2106.06922 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning, 2021b.
Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via the regularized lagrangian. arXiv preprint Siti::2007.04436 2020.
Chao Yu, Jiming Liu, and Shamim Nemati. Reinforcement learning in healthcare: A survey, arXiv
preprint arXiv:/908. 087966 2019.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. arXiv preprint 2rXiv:2005.132339 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning. pp. 7304-7312. PMLR, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. arXiv preprint arXiv:2008.07733 07733, 2020.
Tianjun Zhang, Paria Rashidinejad, Jiantao Jiao, Yuandong Tian, Joseph Gonzalez, and Stuart Russell. Made: Exploration via maximizing deviation from explored regions. arXiv preprint arXiv:2106. 10268, 2021.
13


Reviews:
[{"review_id": "yH5bl4apMG", "reviewer": "Reviewer_sYkB", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ The paper is well motivated and timely, it considers the problem of minimizing cycles of interaction of an agent with the environment which still learning near-optimal policies.\n+ The authors prove a novel lower bound on the deployment complexity in the linear MDP setting and show that this is achievable.\n+ A framework of optimization with constraints is proposed to prove the above results; the applications of safe and sample-efficient RL are highlighted in this context.\n\nWeaknesses:\n+ No practical realizations of the theoretical results are demonstrated.", "summary_of_the_paper": "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. ", "summary_of_the_review": "The paper makes novel theoretical contributions to the challenge of deployment costs in practical RL algorithms. The problem is well motivated, well written and good fit for the venue.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "kTWnsHkTk7", "reviewer": "Reviewer_Ckdx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n-- Deployment-efficiency is an impactful research area.\n\n-- The derivations and algorithms are novel, and provide insights that may be useful to future theoretical or empirical works.\n\n-- The writing is clear and easy to understand.\n\n-- I did not look over the proofs carefully, but I found no issue with what I skimmed through.\n\n\nWeaknesses/Questions:\n\n-- I may have missed this, but it would help if you had some discussion comparing your sample & deployment complexity results to existing complexity results in the literature. For example, it is interesting to note that the sample complexity per deployment (N) in your Thm 4.1 is always at least as large as the sample complexity for finding an epsilon-opt policy (ignoring deployments) from Jin et al. 2019. These sorts of remarks help illuminate the sample complexity trade-offs introduced by the deployment-efficiency constraint.\n\n-- In Section 4.1, I don't fully understand the sentence \"To see this, when we increase...\" Is there a typographical error here? It seems K and RHS of Eq 1 both refer to the same expression.\n\n-- In Section 4.2, can you clarify what you mean by \"uniform mixture of Pi\"? It is not clear if you are uniformly mixing over Pi at each state, or sampling a policy from Pi at the beginning of each trajectory. If it is the latter, then I feel it is debatable whether this should count as a single deployment.\n\n-- The work is wholly theoretical in nature. While I understand that there is limited space, some sort of empirical demonstration would be nice.", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, this paper provides a significant contribution to the field. I found the theoretical results insightful and, although the present submission contains no empirical results, I believe the derivations may inspire future more practical algorithms.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "X9KkbAbkjX2", "reviewer": "Reviewer_iHZz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies deployment efficient RL from the theoretical perspective. It shows when MDP is linear, the lower bound of deployment complexity for deterministic policy and arbitrary policy is $\\tilde{\\Omega}(dH)$ and $\\Omega(H)$ respectively, and Layer-by-Layer Batch Exploration Strategy for linear MDPs and Deployment-Efficient RL with Covariance Matrix Estimation can achieve this deployment complexity. Those results are new and answer the questions that are left by [Gao et al.] (where global switching cost is considered). I believe this result is of great importance to the RL community.\n\nWeakness: Theorem 4.1 has exponent $c_K$ in it, where $c_K$ can be any arbitrary constant. Could you choose a specific constant $c_K$ so that the bound gives you the best trade-off between $N$ and $K$? say the total sample complexity $N\\cdot K$ to be small?\n\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper provides a solid study in deployment efficient RL from the theoretical perspective. Therefore, I choose acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "CVTzYnjQb63", "reviewer": "Reviewer_5FHN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- DE-RL is an interesting framework, reasonably motivated by real-world challenges. \n\n- The lower bounds are reasonable and proofs are clear. The scenarios considered by the lower bounds are sufficiently general and the paper does a great job illustrating the intuition behind the bounds. The authors also commented on converting the nonstationary lower bounds into stationary lower bounds, showing that the deployment cost is somewhat inherent to MDPs rather inherent to nonstationary tasks. \n\n- The motivations behind the algorithms' construction are clearly stated and the authors have shown the connection between this paper and existing literature.\n\n- Assumptions for proving the upperbounds are reasonable and does not appear to be stronger than existing literature.\n\n- Additional results in the appendix are comprehensive and clearly stated.\n\nWeaknesses:\n\n- Nitpick: Definition 2.1 could be improved by requiring $K$ to be on the same order of magnitude as the lower bound. In its current form, it would appear that a smaller $K$, in terms of constant terms, is more deployment efficient than existing algorithms. Allowing for $K$'s that match the lower bound up to constant factors would eliminate such potential ambiguity.", "summary_of_the_paper": "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.\n\nIn section 3, the authors provide a lower bound for the task, under both deterministic and stochastic policies.\n\nIn 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.", "summary_of_the_review": "The paper introduces a new framework, DE-RL, and provides lower bounds under different settings. By drawing inspiration from reward-free and provably efficient RL, the paper provides efficient algorithms for the task.\n\nThe setting is interesting and motivated by real-world concerns.The results are comprehensive and reasonable, with clearly explained proof in the appendix.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors’ present a precise definition of deployment efficient RL, where each new update of the policy may be costly, and theoretically analyze this for finite-horizon linear MDPs. The authors include an information-theoretic lower bound for the number of deployments required. The reviewers found this an important setting of interest and appreciated the theoretical contributions. The authors’ carefully addressed the raised points and also addressed questions about deployment complexity and sample complexity in their revised work. One weakness of the paper is that it does not provide empirical results and the linear MDP assumption, while quite popular in theoretical RL over the last few years, is quite restrictive. However,the paper still provides a very interesting theoretical contribution for an important topic and I recommend acceptance.
Decision: Accept (Spotlight)