Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Under the assumptions of 1) The reward function is lipschitz continuous w.r.t the context and 2) maximum distance between two contexts, this paper proposes an algorithm "Rollin" to learn an optimal policy for the final context and show that it can be achieved in polynomial iteration complexity instead of exponential. The empirical results were shown on a toy domain.
strength_and_weaknesses: Strengths:
The paper provides novel polynomial time iteration complexity and sample complexity bounds for learning a single-task given a curriculum of contexts. 

Weaknesses:
1) Throughout the paper, the authors carry the tone of learning a single-task policy by recasting it as a multi-task problem. (e.g, "In this work, we provide a theoretical framework that reformulates a single-task RL problem as a multi-task RL problem defined by a curriculum.." in the abstract) But, the proposed algorithm "Rollin" assumes that the curriculum (contexts) are given as input. 
2) The assumption of having a curriculum that satisfies the assumptions 3.1 and 3.2 is a very strong assumption. In most algorithms involving goal-conditioned RL or curriculum learning, such a curriculum is not provided. 
3) They also assume that the optimal policy for the initial context is known.
4) The empirical results are shown on a very simple toy domain.
5) There are multiple grammatical errors / typos throughout the paper.
clarity,_quality,_novelty_and_reproducibility: See above
summary_of_the_review: As listed in the weaknesses, this paper makes very strong assumptions that makes the proposed algorithm impractical to use. The authors should come up with an algorithm to automatically generate the curriculum of contexts. In its current form, I recommend the paper as a weak reject.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a theoretically-motivated framework that reformulates a single-task RL problem as a multi-task RL problem defined by a curriculum for computationally-efficient policy learning. Their framework and other baseline are demonstrated in a goal-reaching task with a Mujoco dynamical system. The results show improved learning performance compared to traditional methods. 
strength_and_weaknesses: Strengths:
- A novel approach for efficient RL policy learning.
- Algothrim seems sound with theoretical backing.
- Experiments demonstrate that the proposed approach leads to better performance. 

Weaknesses
- The experiment section is relatively weak. It is unclear how the proposed approach will scale to other Mujoco robots, such as Swimmer and Humanoid. 
- Is the idea of a warm start to policy learning also applicable across different environments? For instance, using parameters from u-maze to some other maze environment could aid in investigating that.

clarity,_quality,_novelty_and_reproducibility: The presented approach is novel, with results demonstrating improved performance over prior methods.

summary_of_the_review: Overall, the presented approach is novel with theoretical support. Experiments demonstrate better performance than the prior methods. However, test cases with different dynamical systems and investigation on the applicability of the proposed approach in speeding up learning across different environments can further strengthen the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes ROLLIN, and algorithm to reduce the complexity of learning an optimal policy in a sequence of contextual MDPs, i.e. a set of MDPs sharing everything but the reward function in this work. The main idea of the paper is that if the two contexts are close enough, we can modify the initial state distribution in a way to reduce the total computational complexity of a policy gradient method.

strength_and_weaknesses: 
### Strengths

* The paper proposes a neat way to reduce sample efficiency in the setting providing the theoretical proof (I did not check all the derivations in the appendix).

### Weaknesses

* The paper chooses a non-standard way of evaluating the algorithm, i.e., providing the learning progress value instead of the policy returns. As far as I understand, we have an ordered set of MDPs, and we are eventually interested in solving the target one. I believe, the chosen evaluation protocol favours the proposed method, and I would like to see the comparison: curriculum vs baseline on the target task only.
* The proposed algorithm requires knowing the optimal parameters for the first MDP in the set. If I get it correctly, if we remove this quite limiting assumption, we will get the exponential complexity again, though it will still be reduced by the consequent application of ROLLIN.
* The paper misses important connection to the related work, which is more empirical, but very similar in spirit:
    * REvolveR: Continuous Evolutionary Models for Robot-to-robot Policy Transfer, ICML 2022
    * Curriculum Learning with a Progression Function, Bassich et al.
In addition, I think the paper misleads the reader by its title. Usually, by multitask RL, we mean a single model being able to solve multiple tasks at once, whereas this paper looks at the linear curriculum with a single target task.

clarity,_quality,_novelty_and_reproducibility: ### Clarity

The paper is mostly clearly written, but it assumes knowing a lot of context from the reader. Some of the concepts used in the introduction
 get defined only later in the 'Preliminaries' section. 

### Quality

I am not a theoretical RL researcher, but the theoretical part looks of high quality to me. My concerns about the assumption on knowing the optimal policy for the first MDP are outlined in the 'weaknesses' section. As for the empirical part, I am concerned with the reported metric, as I also mentioned in the 'weaknesses'

### Novelty

The theoretical part is novel to the best of my knowledge. Empirical part has some missing related works as I pointed out in the 'weaknesses'.

### Reproducibility

The appendix contains detailed pseudocode and the hyper parameters to reproduce the experiments.

summary_of_the_review: My current recommendation 'below acceptance' is mostly caused by the empirical evaluation protocol weaknesses. I am ready to increase the score if my concerns from the 'weaknesses' are addressed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary:

This paper presents a theoretically-motivated framework that reformulates a single-task RL problem as a multi-task RL problem defined by a curriculum for computationally-efficient policy learning. The algorithm has theoretical guarantees under the assumptions of 1) The reward function is lipschitz continuous w.r.t the context and 2) maximum distance between two contexts. The proposed algorithm "Rollin" learn an optimal policy for the final context and the paper shows that it can be achieved in polynomial iteration complexity instead of exponential. The empirical results were shown on some toy environments. During the rebuttal phase, new experiments on mujuco have been added.

Strength:
- A novel approach for efficient RL policy learning with theoretical guarantees.
- Experiments demonstrate that the proposed approach leads to better performance.

Weakness:
- curriculum (contexts) are assumed to be given as input.
- there are multiple grammatical errors/typos throughout the paper.
- the metareview could not verify the theoretical guarantees. Perhaps these are also typos. In Theorem 4.1 and 4.3, why are the complexity bounds presented as $\Omega(\cdot)$? Are these lower bounds? If these are lower bounds, then the theorems do not provide guarantees. 


justification_for_why_not_higher_score: The paper indeed provides an interesting approach to learning a single task with a multi-task approach. Yet the theory provided does not seem to be valid as it requires strong assumptions, and the theorems only provide complexity lower bounds (not upper bounds). Some reviewers also believe the contribution (even if correct) is not significant enough.
Decision: Reject