Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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. 
main_review: Strengths:
+ 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.
+ The authors prove a novel lower bound on the deployment complexity in the linear MDP setting and show that this is achievable.
+ 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.

Weaknesses:
+ No practical realizations of the theoretical results are demonstrated.
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

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.
main_review: Strengths:

- DE-RL is an interesting framework, reasonably motivated by real-world challenges. 

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

- The motivations behind the algorithms' construction are clearly stated and the authors have shown the connection between this paper and existing literature.

- Assumptions for proving the upperbounds are reasonable and does not appear to be stronger than existing literature.

- Additional results in the appendix are comprehensive and clearly stated.

Weaknesses:

- 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_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.

The setting is interesting and motivated by real-world concerns.The results are comprehensive and reasonable, with clearly explained proof in the appendix.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
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.

Weakness: 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?



summary_of_the_review: This paper provides a solid study in deployment efficient RL from the theoretical perspective. Therefore, I choose acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: Strengths:

-- Deployment-efficiency is an impactful research area.

-- The derivations and algorithms are novel, and provide insights that may be useful to future theoretical or empirical works.

-- The writing is clear and easy to understand.

-- I did not look over the proofs carefully, but I found no issue with what I skimmed through.


Weaknesses/Questions:

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

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

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

-- 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_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.
review_title: null

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)