Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work tackles the challenges of lifelong reinforcement learning. In particular, authors propose an algorithm (UCBvld) for solving sequential contextual Markov decision processes with linear representation which (1) guarantees sublinear regret with (2) a sublinear number of planning calls, even when the sequence of tasks and the initial states are chosen adversarially. 

UCBvld has its foundation in LSVI-UCB, with an added distillation step based on a convex quadratically constrained quadratic program defined on a set of representative task contexts (assumed to be known). 
strength_and_weaknesses: Strengths

* Though quite dense, the work is presented in a digestible way. I found the background, the method and the theoretical part of paper clearly organised and concise. 
* The problem studied is important and relevant, authors have identified gap in the field of RL (theoritical lifelong RL) and provided ideas and tools to start addressing it. 

Weaknesses
* My main concern is that authors have not conveyed if or how the contributions of the work will extend beyond the limited case of linear environment under the completeness assumption. I appreciate that extensions to the non linear case / with fewer assumptions might not be possible yet, but then a discussion around how we expect the performance to be impacted would be necessary (experiments on non synthetic environments could help to show that).
* The reason for my previous point is that I did not grasp from reading the paper what kind of environments fall into these constraints in practice, so I don't see how it could be applicable. I do not have a strong enough understanding of how reasonable is the completeness-style assumption.
* The experiment section needs more information. What are the environments? A comparison with another lifelong RL baseline should also be included to be convince readers of UCBlvd's benefits.


Minor:
* page 5 CMDP appears without being defined 
* page 6, $\boldsymbol S_{++}^d $ is not defined
* page 6, "the algoriTheorem"?

clarity,_quality,_novelty_and_reproducibility: The writing is clear and well structured. 

I did not check all proofs in the supplementary material, the theoretical analysis in the main text appears sound.

The work's originality is limited in that it builds on an existing method to extend it to the lifelong case.

I believe the experiments should be reproducible with the given material. 
summary_of_the_review: The paper tackles an important gap in the RL literature. However, it seems to be of very limited applicability, without any direction for future extension provided.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies lifelong reinforcement learning with different tasks. In particular, the paper proposes a new algorithm that is both sample-efficient and computation-efficient. The underlying models are variants of linear MDPs, which are widely studied by the reinforcement learning theory community.
strength_and_weaknesses: Strength: The paper proposes a novel algorithm which is both sample-efficient and computation-efficient in theory. The computation-efficiency seems appealing and insightful, but some more detailed analysis might be helpful for people to fully understand the contribution. In particular, the paper decreases the $K^2$-cost of planning call to $log(K)$ by skipping planning in the case that no sufficient new information is obtained.

Weakness: 1) The sample-efficiency of the algorithm has very limited insight given previous works. 2) It will be more clear for the readers to understand the contribution of the paper if the paper can explicitly analyze how much computation cost is reduced, rather than just from the reduction of planning calls. In deed, the new algorithm still require to calculate a new covariance matrix in each iteration. When re-planning is triggered, it requires solving a QCQP, which is not required in Algorithm 1. 3) It is not very clear how strong the cross product structure in Assumption 3 is. Does it includes the case where there is only finite number of possible $w$?
clarity,_quality,_novelty_and_reproducibility: The result is novel to my best knowledge.
summary_of_the_review: The reviewer believes that paper is a little below the acceptance threshold. It will be helpful if the reviewers' concerns mentioned above can be resolved in the author's responses.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies **lifelong** reinforcement learning with linear function approximation. In a typical RL setup, the reward function depends only on the state-action pair. The **lifelong** component of this works comes from the assumption that the reward function is dependent on the state-action pair $(s, a)$ in addition to a task context variable, denoted $w$. It is assumed that the agent observes $w$ directly but $w$ is allowed to change from one episode to the next. The paper also addresses how to reduce the number of planning calls in the lifelong learning context.

Overall the contributions, to me, seem two-fold:
1. Introduces the lifelong RL setup and Lifelong-LSVI, a naive baseline in the lifelong learning problem.
2. Identifies two assumptions under which a low-switching cost algorithm is possible for lifelong RL. The authors justified the assumption using a toy example (see Example 1).
strength_and_weaknesses: Strength
- The setting is novel and is relevant to RL practitioners.
- Experimental results are able to show that UCBlvd enjoys roughly the same regret while requiring far less calls to the planning subroutine. 

Weaknesses
- The assumption that the reward functions for all tasks are known beforehand is a strong one. In the lifelone learning environment described here, the only source of uncertainty lies in the transition kernel, making the setting close to a single-agent single-task RL problem, which has been thoroughly examined in the linear MDP setting. While Example 1 offers a good intuitive justification, it would be great if the authors could offer more justification for the setting they assume, perhaps in the appendix, similar to the discussion immediately after Assumption 2.

------- Post rebuttal update --------
My concerns have been addressed by the authors and I have adjusted my score accordingly.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and relatively easy to follow.

The algorithms proposed in the paper are limited in terms of novelty. Particularly, the main algorithm UCBlvd is close to existing low switching cost RL algorithms. The key contributions of UCBlvd, to me, seem to be Assumptions 2 and 3, which jointly identify problem settings under which this kind of low switching cost algorithm is feasible.

The proofs are reproducible. However, code used to generate Figure 1 is not included in the submission and cannot be verified easily. Nevertheless, the plot is inline with existing results and exhibits expected behavior.

The results in the paper are correct and justified theoretically.
summary_of_the_review: Overall, the paper introduces a novel setting for linear MDP. The authors are able to derive conditions under which low switching cost RL algorithms work. The extra assumptions needed to enable low switching cost RL is unique to the setting and is a novel contribution from the authors. Unfortunately, the mathematical model for lifelong RL seems overly reductionist at this moment and further explanation and justification would be appreciated.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper may most accurately be summarized as giving polynomial-time algorithms that obtain sublinear regret in linear contextual MDPs when the transition and Q-functions are linear in the state-action features and the context, and that only need to re-solve the MDP logarithmically many times w.r.t. the number of tasks.

More concretely, the contextual MDP has a fixed dynamics (independent of the context), but reward functions that vary with a side "context" w that is known to the learner. The learner interacts with this MDP for K episodes of horizon H. The main assumption is that the transition kernel and Q-function are linear in some known basis functions. A similar assumption was used previously to obtain a polynomial time algorithm for such MDPs sans context; so this paper is essentially extending that line of work to include context.
strength_and_weaknesses: The main strengths of the paper are
1. It considers the computational cost in this online setting, which is usually ignored (e.g., in bandits) but would indeed be prohibitively substantial here using existing methods.
2. There is some technical novelty in the design and analysis of the test for the need to recompute the solution towards the above.
3. There are some experiments, albeit on synthetic tasks, so the method is potentially useable in practice.

The main weaknesses are
1. Technically, apart from the analysis of the number of re-solves, it seems to be a straightforward extension of the previous works on the non-contextual MDPs, e.g., Yang & Wang 2019.
2. The individual planning calls are now more expensive, as they have to solve a QCQP rather than a linear program.
3. The synthetic experiments don't give a sense of how the algorithm would perform in a real-world setting.
clarity,_quality,_novelty_and_reproducibility: The clarity is reasonable, at least for someone familiar with prior work in the area. Reproducibility doesn't seem to be much of a concern, based on the supplemental material anyway. I believe the work is technically sound.

So the main question is novelty. As mentioned above, there is some modest novelty in this work: the emphasis on the number of times the MDP needs to be re-solved and means to control this. So it's reasonably novel, but not a breakthrough.
summary_of_the_review: I think there's enough of a contribution to warrant accepting this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The reviewers like the paper but they are not excited about it. They see it as a well-executed work (nicely written, interesting setting, reasonable theory, and simple experiments to show that the proposed method is potentially useable in practice), but with somewhat limited novelty (seems to be a straightforward extension of the existing results). What they particularly like is that the authors take the computational cost into account and design and analyse a test (for the need to recompute the solution) that decreases the quadratic planning call to logarithmic. 
justification_for_why_not_higher_score: The novelty of the work is somewhat limited (seems to be a straightforward extension of the previous works). 
justification_for_why_not_lower_score: It is a well-executed work, nicely written, interesting setting, reasonable theory with some technical novelty, and some synthetic experiments to show that the method has potential in practice.
Decision: Accept: poster