Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the benefit of joint representation learning in the presence of multiple reinforcement learning tasks. The authors introduce an algorithm called REFUEL that in the presence of $T$ tasks with a shared representation it is able to learn an ensemble of almost optimal policies in a number of trajectory samples that would be necessary if training each of these $T$ tasks independently. The benefits are only seen when $T = \Omega(\frac{K}{d^5})$ where $K$ is the number of actions (although the authors do not explicitly mention this). 

These results are in line with a flurry of results in the literature that show the benefit of learning multiple tasks simultaneously in the presence of joint structures. This fact is communicated in the submissions' related work section. The authors then ask the question of wether representation learning can be beneficial in the setting where the learner is to encounter a test task. To show results for this setting the authors introduce strong coverage and reachability assumptions, and also require to assume the point wise TV is upper bounded by a constant multiple of the expected TV of all states sampled under the uniform distribution as well as a `linear dependence' relationship between target and source tasks. Moreover, they also require the learned features during training to satisfy a minimum eigenvalue assumption (over an unspecified measure $\rho$). Combined these assumptions allow the authors to derive guarantees for downstream offline RL. 


 
strengths_and_weaknesses: Strengths. The setting of multitask representation learning is very interesting and relevant to the community. In particular, studying the problem of downstream offline RL and representational transfer is very exciting. The first part of this work provides expected results for the multi task setting and a well executed algorithm and set of results. Although not super surprising it is a welcome addition to the literature. 

Weaknesses: the paper has a couple of typos and undefined variables ($K$, $\rho$). To date I don't know what $\rho$ is in Assumption 6. Although the setup of section 5 is interesting, the results presented require a series of strong assumptions that make the reader believe these are there just to make the results work. It would be beneficial if some work had been put in place to stress test these assumptions (in the form of for example lower bound arguments) and make the reader know which of these are necessary or which ones are just a device to make the proofs go through without further effort. 
questions: I would like to hear some clarification from the authors about the weaknesses described above. 
limitations: This work does not pose any negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a representation learning algorithm for multi-task reinforcement learning under low-rank MDPs assumption (transition kernels have a low-rank decomposition in the form of $P^t(s’|s, a) = \langle \phi(s’), \mu^t(s, a)\rangle$ where the feature of the next state $s’$ is shared across tasks $t \in [T]$). The algorithm adopts the step-by-step exploration approach from FLAMBE (Agarwal et al., 2020), uses the reward bonus from REP-UCB (Uehara et al., 2021), and extend their single-task analyses to the multi-task setting. The authors showed that jointly learning the representation for multiple tasks is more sample efficient than learning each individual task independently, as long as the number of tasks is large enough. The authors also show that the sample complexity of learning a new task in an offline setting using the learned representation can be reduced under mild assumptions on the similarity of the new task to the pre-training tasks.
strengths_and_weaknesses: Strengths:
- The proposed representation learning for multi-task reinforcement learning setting is novel and the proposed algorithm is shown to provide provable sample complexity benefits when the number of tasks is high (with the number only dependent on the number of actions and the low-rank dimension). 
- Although I did not check the proof carefully, the theoretical results look reasonable. 

Weaknesses:
- Algorithmic-wise the proposed algorithm has limited innovation — 1) for the online setting (Algorithm 1), most components are directly from two prior works (FLAMBE and REP-UCB) with relatively straightforward modifications to make them amenable to the multi-task setting; 2) for the offline setting (Algorithm 2), the algorithm is an one-step version of LSVI-UCB. 
- Assumption 4 in the downstream offline RL seems quite strong. It states that the point-wise (for a certain pair of $s, a$) TV distance of two transition kernels is bounded by the average (over the entire support of $S \times A$) TV distance of these two kernels multiplied by a constant. If $C_R$ were to depend on $S$ and $A$, it could be as big as $S \times A$, in which case would not give sample efficiency benefits in the end over the baseline REP-LCB.

questions: - It would be also interesting to see if the pre-trained representation would also benefit online learning of the new task $T+1$ (the paper studied offline learning of new task). Are there some challenges that might hinder such analysis?
- It would be helpful to highlight more on how the proof techniques used in this work are different from the prior work at the end of Section 4.2. The authors listed the new technical pieces that were introduced but I did not have a good understanding on how much different they are from the prior methods. 
limitations: The authors have adequately addressed the limitations of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper theoretically characterize the benefit of representation learning under the low-rank Markov decision process (MDP) model. The framework under consideration is a reward-free upstream and reward-known downstream task, where all tasks share the same feature function $\phi∗$ but might differ in $\mu$. The downstream offline RL, consists of a new task sharing the same representation as the
upstream tasks given an offline dataset, and the goal is to find a near-optimal policy.
The authors propose a new theoretical algorithm `REFUEL` (REward Free mUltitask rEpresentation Learning) and theoretically show that a shared transferrable representation of low rank MDPs can be learned efficiently. They provide various theoretical results on representation uncertainty measure, sample complexity, and  upper bound on both the sample complexity and the suboptimality gap of downstream offline RL with the help of the learned representation.
strengths_and_weaknesses: The authors proceed with the algorithm design as follows:

### Joint MLE-based Modeling Learning:
The agent passes all previously collected data to estimate the low-rank components $\phi^n, \mu^{n,1} ... \mu^{n,t}$ simultaneously via the MLE oracle on the joint distribution of these random variables. In practice In practice, the representations $\Phi$, $\Psi$ are properly parameterized and learned by neural networks. Next, for each task t, the agent uses the learned embeddings to update the estimated transition kernel $\hat{P}^{(n,t)}$.

### Pseudo Cumulative Value Function Construction for Exploration
The agent first uses the representation estimator $\hat{\phi}^n$ to update the empirical covariance matrix $\hat{U}^{(n,t)}$. The Pseudo Cumulative Value Function (PCV) is then established as an uncertainty measure that captures the difference between the estimated and ground truth model.

In downstream RL, the agent is given a new target task $T + 1$ under MDP $M^{T+1}$ and aims to find a near-optimal policy for $i$. . The downstream task is assumed to share the same representation as
the upstream tasks, and hence the agent can adopt the representation learned from the upstream to
expedite its learning.

Finally, the joint learning and decision making among all tasks involved in the four main components differ from single-task RL algorithms, and enable it to exploit the shared representation across the source tasks to improve the sample efficiency.

To ensure that the feature learned in upstream can still work well in downstream tasks, upstream and
downstream MDPs should have certain connections. `Assumption 2` (Reachability) provides the assumptions made  on transition kernels to build such connections. 

## Strengths
- Good coverage of theoretical results and the overall problem of learning joint representation in the context of multi-task RL is important for the community.
- Theoretical results on sample complexity : sample complexity upper bound for REFUEL and then compare multitask result with that of single-task RL.
- The theoretical results throughout the paper seems sound.

## Weaknesses
- This paper only provides theoretical results without empirical results
- There might be missing connection to related work to other MDP frameworks learning decomposed representations
- The assumptions and upper bounds do not hold in the case where oracle representation is not available and the case where these need to be approximated using function approximation



questions: 
- In terms of the polynomial efficiency of REFUEL, in Proposition 3, it is shown that the summation of the PCVs over all iterations is sublinear with respect to the total number $N_u$ of iterations, assuming 
exploration policy is derived by an oracle. How does this results change in practice when this assumption of existance of an oracle is violated?

- Is  there any theoretical connection between this framework to frameworks such as Successor Features (SFs) where the the representation is decomposed to the dynamics $\phi$ and $w$ representing the task-specific features? In general I have not seen such connection to be made in the majority of related work in  low-rank MDP and Block MDP literature. Is there a difference between this setting of low-rank MDP which is stricly more general than linear MDPs which assume representation is known a priori ?
limitations: - For the analysis to hold, there is dependency on the assumptions that connect the upstream and downstream MDPs. In practice this can be very restrictive in the space of designing multiple tasks.
- The analysis relies on the existance of an oracle for learning the joint distribution via MLE for the representation and during the policy exploration.
review_title: null

Meta-review: metareview: The reviewers are largely in consensus that the questions posed in the paper are extremely relevant today and, while somewhat unsurprising, the paper provides solid value by establishing "provable benefit", including algorithms with novel components and numerous analysis tools that look attractive for re-use by future researchers in this emerging domain. 

The AC is surprised that not even a toy set of experiments was deemed necessary to validate the predicted multi-task performance in practice. However, the reviewers have all believed in the value of the theory alone, and I appreciate the setup of a large enough multi-task set would require significant work, though I hope this is pursued soon and often in future work.
confidence: Less certain
Decision: Accept