Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes LSVI-UCB-Batch and LSVI-UCB-RareSwitch algorithms which can satisfy adaptivity constraints, i.e., the number of policy changes during learning is small. The authors proved regret bounds showing that with a small number of switches, the algorithms can achieve same regret bound as LSVI-UCB.
main_review: Pros:

I think this paper is very well-written and easy to follow. The results are rigorously presented. I did not check the proofs but the results seem to be correct and aligned with prior works.

Cons:

I think the novelty of the algorithm design is relatively limited. The LSVI-UCB-Batch is essentially the same as LSVI-UCB with the only difference being that the policy is updated every K/B episodes rather than every episode. The determinant based criterion in LSVI-UCB-RareSwitch also appeared in several prior works.

The theory only applies to line MDP which is a bit limited in my opinion. But I understand that the recent line of work on provably efficient RL needs such assumption, especially for value-iteration type of algorithms.

Minor:

Line 10 in Algorithm 1: superscript “+” is not defined, similar thing for Algorithm 2.

Line 222:  “In detail, when B = T, LSVI-UCB-Batch degenerates to LSVI-UCB”: should it be T or K? I think by definition B cannot be larger than K. Similar things in lines 233-234.
limitations_and_societal_impact: I did not see many discussions on the limitations of this work. I did not see any negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed two algorithms for reinforcement learning with linear function approximation under adaptivity constraints.
main_review: Strengths:
This papers proves upper bounds on the regret in both the batch learning model and rare policy switch model, which illustrates a trade-off between the regret and global switching cost. It also shows a lower bound in the batch learning model. 

Weakness / comments:
1. It seems that the upper bound in [1] is a special case of Theorem 5.1 when the dependency of regret on $T$ is $\sqrt{T}$. But the paper does not explain whether this difference of theoretical results comes from the design of the algorithm or the proof techniques. A clearer and complete comparison between [1] and the current paper would be helpful. 

2. The lower bound in Theorem 4.2 assumes $B\geq(d-1)H/2$, while in order to make the upper bound in Theorem 4.1 on the order of $\widetilde{O}(\sqrt{d^3H^3T})$, it is required that $B=\Omega(\sqrt{T/dH})$. Does this mean the upper bound and lower bound only match when $T=O(d^3H^3)$? If it does, how restrictive is this condition?

[1] Gao, Minbo, et al. "A provably efficient algorithm for linear markov decision process with low switching cost." arXiv preprint arXiv:2101.00494 (2021).
limitations_and_societal_impact: This is a theoretical paper, and I think there is no potential negative social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers sample-efficient RL in linear MDPs under adaptivity constraints, that is, the number of policy switches during the algorithm execution is constrained to be low. The paper considers two types of adaptivity constraint: the batch learning model (in which the switching schedule is predetermined), and the rare policy switch model (in which the switching schedule can be adaptive). The main contributions of this paper are low-regret algorithms for linear MDPs in both versions of low switching models.
main_review: This paper is an extension of the previous works on low switching cost learning in bandits and tabular MDPs. I think overall the results make good contributions to the literature and contain some interesting theoretical insights. The algorithms for both switching models are fairly clean (the Batch learning model just uses a delayed Q update; the Rare Policy Switch model uses an adaptive switching criterion that depends on the determinant of the cumulative feature covariance matrix). These are analogous to (and not exactly the same as) the per-state exponential switching schedule of Bai et al. 2019 for tabular MDPs. 

Furthermore the paper has a small numerical experiment section, which I do appreciate as for an RL theory paper. The particular experiments here show that the low switching cost algorithms do achieve sublinear regret. I wonder if the authors could check whether the avg regret scales as $O(1/\sqrt{T})$? (e.g. by looking at slope on log scale)?

My only concern is that the results sound a bit incremental --- I wonder in what sense are the techniques new and different from existing analysis on low switching cost? E.g. by looking at Lemmas A.1, A.2 I get the feeling that the consequence of delayed update here in linear MDP is easier to analyze than in tabular cases, because of the global switching schedule (so that there is only $b_k$, not something like $b_k(s, a)$). Maybe Lemma A.3 and Lemma B.3 may be the key non-trivial ones that allow the result? Could the authors discuss some of the intuitions about these Lemmas and in particular which parts are new? For example, how Lemma B.3 compares with the per-state exponential scheduling in existing low switching cost algorithms for tabular MDPs. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies linear mdp under two adaptivity models: rare policy switch model and batch learning model. They achieve the same regret as the fully adaptivity setting (LSVI-UCB) with much less number of policy switches ( e.g., in the rare policy switch model, it is $dH \log T$ vs $T$)
main_review: **Strong points** 
-	A new result of a sample efficient linear RL with limited adaptivity that seems more comprehensive (as it studies batch learning model as well) than the concurrent work Gao et al. 2021. It also encompasses a result in Gao et al. 2021. 
- This is a complete study with two proposed algorithms and corresponding regret analysis, and lower bound analysis. 

**Weak points**
-	The approach and analysis are quite simple as they adopt from Abbasi-Yadkori et al. 2021, Jin et al. 2020 that I am not sure if there is any new technical idea.  For example, Algorithm 2 in the present paper is the same as the algorithm in Figure 3 in Abbasi-Yadkori et al. 2021 except that the former is for linear MDP and the latter is for linear bandits. 

**Minor comments**
-	Fig 1: the colours for B=50 and B=15 are difficult to distinguish. Moreover, it would be nice to have a baseline line there to give the readers an idea of how much regret is “bad”.  The current experimental result shows that LSVI-UCB-Batch and LSVI-UCB-RareSwtich underperform their full adaptivity counterpart LSVI-UCB. Without a baseline, it could be difficult to know if such a gap is substaintial. Moreover, line 312, the authors say that LSVI-UCB-Batch achieves the similar regret as LSVI-UCB, but Fig 1.(a) does not indicate so. 

- The current experiment only shows two configurations (B=15,50 and eta=4,8) for each proposed algorithm. It would be an addition if the results for more configurations are presented to show the trade-offs between regret and adaptivity level. 

**Questions**: 
-	Line 88-91: “Our goal is to design efficient RL algorithms under a switching cost budge B while their goal is to achieve the optimal rate in terms of T”: How are these two goals different? 
-	I would like the authors to comment on the difference between Algorithm 2 of this paper and Algorithm 1 of Gao et al. 2021, and compare their advantages/efficiency in solving the adaptivity constraint problem. 


limitations_and_societal_impact: The authors have adequately addressed the limitations and social impact of their work.
review_title: null

Meta-review: This paper proposes LSVI-UCB-Batch and LSVI-UCB-RareSwitch algorithms which can satisfy adaptivity constraints, i.e., the number of policy changes during learning is small. The authors proved regret bounds showing that with a small number of switches, the algorithms can achieve same regret bound as LSVI-UCB. There is a consensus that the paper should be accepted. 
Decision: Accept (Poster)