Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper tackles the challenge of learning an efficient representation for multi task reinforcement learning. The authors present a learning algorithm for multi-task RL with function approximation, low-rank multi task bilinear class. This algorithm incentivizes the the RL algorithm to improve sample efficiency by leveraging information from multiple tasks at the same time.
The authors provides a PAC bound showing that their algorithm is more efficient than learning each task separately.
strength_and_weaknesses: Strengths:

_ this paper tackles an important challenge multi task learning in reinforcement. As far as I know this paper present the first result for provably efficient multi task reinforcement learning with function approximation
_ the PAC bound for theorem 5.2 shows the benefit of multi task learning is that it is more efficient than learning the different tasks seperately

Weaknesses:

_ in the definition of low rank multi-task bilinear class the paper the features W still depend on m, in practice we often try to use a single representation to solve multiple MDPs / tasks. I understand that to provide a learning bound it is necessary to have more flexibility in the representation so each tasks can be solved using the shared representation. Nevertheless could you expand a bit on the relationship between you work and using a single representation for all tasks?
_ it would be useful to provide simple examples of the algorithm on a few simple tasks to assess its empirical performance. Moreover these experiments might highlight issues of the learning dynamics of multi-task reinforcement learning such as ray interference [1] 
_ the realizability asumption (assumption 5.2) seems reasonable to provide a theoretical result but it may not be verified in practice? Do you have an intuition on the performance of the proposed algorithm when this assumption is not verified?
_ the benefits of the proposed algorithm is only achieved when k << d. It would be useful to provide a sense of how often this condition is verified.

[1] Ray Interference: a Source of Plateaus in Deep Reinforcement Learning, Schaul et al., 2019
clarity,_quality,_novelty_and_reproducibility: The paper was overall well written however I found the notation used in the paper a bit hard to follow due to the numerous subscripts.
summary_of_the_review: This paper provides the first provably efficient multi task reinforcement learning algorithm. As such I think it improves our understanding of representation learning and multi task learning, for that reason I recommend accepting the paper.
Yet I recommend that the authors add a few sections with empirical results and discuss more the validity of the assumptions used in their proof.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the multi-task learning problem with representation learning. Specifically it proposes  online representation learning algorithms to capture the shared features in the different task-specific bilinear forms. Unfortunately, the proposed algorithms are not validated on any RL problem, simulated or real. 
strength_and_weaknesses: Strengths:
The proposed representation learning in low-rank multi-task bilinear task seems to be a very interesting idea. However, I do not feel confident to evaluate its novelty.

Weaknesses:
The proposed algorithms are not validated on any RL problem, simulated or real. For me this is mandatory. I suggest to include an experimental validation, even in a toy problem.
clarity,_quality,_novelty_and_reproducibility: Clarity:
The paper is well-written and the analysis of the related work is appropriate.

Novelty:
I do not feel confident to evaluate its novelty.

Reproducibility:
No validation of the proposed algorithm in any simulated or real problem, therefore, it is not easy to evaluate the reproducibility of the algorithm.
summary_of_the_review: The proposed representation learning in low-rank multi-task bilinear task seems to be a very interesting idea. However, the proposed algorithm is not validated in any RL problem. My opinion is that such a validation is mandatory.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper provides bounds on the multi-task sample complexity of reinforcement learning in bilinear classes (recently introduced by Du et al., generalizing several existing notions) when the Bellman errors of the tasks can be parameterized in terms of a small set of common features.
strength_and_weaknesses: The main strength is that the work extends the current state of the art in the theory of RL in large feature spaces by allowing multiple tasks to share features in a natural way. The work seems sound, and fairly general.

There are three main weaknesses: first, given that one has set out to consider multi-task + RL, the work has some flavor of "turning the crank," combining known approaches to feature sharing in multi-task learning with the techniques for analyzing RL from recent works. 

Second, from this perspective, the bounds obtained are surprisingly weak, in that they retain a high-order dependence on Md, the number of tasks times the ambient feature dimension. In this setting, I would expect a dependence on Mk with a lower-order dependence on d (that is independent of the number of tasks). No justification is provided for why such a bound may not be possible, leaving the impression that this bound is a "first stab."

Third, the approach relies on an ERM oracle. While this limitation is shared with many works in RL, some recent works on linear classes (e.g., Jin et al., Yang & Wang) do not require this. The work hints that an efficient algorithm might exist for these classes, but stops short of providing one. The work would have been much more compelling if such an algorithm had been described.
clarity,_quality,_novelty_and_reproducibility: Although the notation is a little overwhelming in the formulation of the ERM problem in particular, the work is reasonably straightforward and so it is reasonably clear. 

As mentioned above, the novelty seems to lie primarily in being the first to combine the two notions of bilinear classes of RL environments with feature-sharing multi-task learning. This is OK, but a bit limited. 

As far as quality goes, the work seems sound but (as mentioned above) obtains weaker results than I'd expect. Proofs are included and so reproducibility is not at issue.
summary_of_the_review: On the one hand, I believe that the bounds claimed have not appeared previously in the literature. On the other hand, there does not seem to be much technical novelty involved in obtaining these bounds. The bounds seem likely to be suboptimal and the method is not computationally efficient.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents progress towards a sample efficient, multi-task Reinforcement Learning (RL) algorithm. Some theoretical results are proven, but the bounds proven are weak with little novelty beyond the application to multi-task RL. The significance of this contribution could be improved by tighter bounds or empirical evaluation of a concrete algorithm. The authors acknowledge they are planning to add empirical results in future updates suggesting the work is still in progress. Overall, this appears to be an intermediate result in an important research direction. Hopefully the feedback from all reviewers will help to improve the authors' future work on this topic.
justification_for_why_not_higher_score: Theoretical results of questionable significance

Authors openly acknowledge ongoing empirical work suggesting work in progress not yet ready for publication
Decision: Reject