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 multitask representation learning with *general* function class in contextual bandits and MDP setting. In this setting, the goal is to learn a shared representation function that maps the state (or context) and action to a $k$-dimensional vector that allows the value function to be expressed as a linear function of this representation. They proposed an algorithm, Generalized Functional Upper Confidence Bound (GFUCB) which adapts UCB for a general function class in multitask setting and prove a regret bound for both the contextual bandits setting and multitask episodic RL setting with M related tasks (sharing common state and action space). Experiments were conducted in the non-linear neural network bandits setting based on the MNIST dataset to demonstrate that their GFUCB algorithm indeed outperforms naive epsilon greedy on a single task and scales to a larger number of tasks (i.e. lower cumulative regret with more tasks). 
strengths_and_weaknesses: **Originality**: The paper presents the first provably sample efficient (with regret bound) algorithm for general function class representation learning in contextual bandits and linear MDPs. The authors clearly positioned their contributions in the background of prior works, which either studied multitask representation learning in linear representation functions or assumed prior known representation functions, or only studied single task setting when tackling general function class value approximation for bandits and MDPs. 

**Quality**: The paper appears to be technically sound. The definitions and assumptions for the main results are given leading up to the algorithm and regret bound. The empirical experiments however only tackle the bandits setting, but not an MDP setting. 

**Clarity**: While the paper is fairly dense in mathematical notations, overall the paper is adequately well-written. The intuitive interpretation of several theoretical results was helpful. 

**Significance**: Given the abundant interest in multitask deep RL settings, this theoretical result is a step towards a deeper (pun intended) understanding in the community. The analysis in this paper and the resulting algorithm can give further inspiration for principled approaches in designing more practical algorithms with deep neural networks as well. 
questions: 1. While the focus is on the theoretical analysis in this paper, one possible improvement that can further strengthen the paper is providing also a proof of concept experiment for a linear MDP. Perhaps it can be built off the MNIST dataset as well (such as translating certain digits to their designated spot in each of the multitask instantiation), or a grid world fed as an image into a CNN. 
2. A suggestion: it will be helpful if you summarize the practical approximations to Algorithm 1 in the Experiment section 6.2 as a separate “Algorithm 3” to show the correspondence between the original GFUCB algorithm and the practical instantiation (with running gradient descent for the optimization step, etc.). 

limitations: The authors did not explicitly discuss the limitations of their work beyond stating the assumptions for the analysis. One observation noted in the appendix was that while the eluder dimensions of neural networks can be exponentially large, in practice (as shown in their experiment), the UCB bonus term still shrinks as the number of training samples increases. Thus specific interplay of using neural networks as the function class and its generalization / interpolation behavior is up for future study for this problem setting. 

As a mainly theory paper, the authors specified “N/A” for potential negative societal impact. Perhaps we can still speculate on potential harmful uses of highly efficient multitask RL training algorithms leading to an agent capable of very large number of tasks.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The authors consider multitasks reinforcement learning where generalized representations function among the tasks and task-specific parameters will be estimated sequentially in order to minimize cumulative regret. Previous works only focus on either linear function class or single-task which limits their applicability. Inspired by them, the authors employ eluder dimension to handle the concept of general function class and treat the problem as linear MDP (as well as linear contextual bandit). In the end, they provide proof-of-concept experiments to evaluate the benefit of shared representation among tasks 
strengths_and_weaknesses: Strength:
This work extends the results in [14] from linear representation class to the general class with the tools provided from [25]. Their upper bound (Thm 1 and 2) explain the cost for learning representations function, O(\sqrt{MdTlog N(\Phi)}), will be sublinear in M, hence this huge cost (compared to learning \theta_i for each task) will be mitigated by jointly learning multiple tasks.

Weakness:
1. It is a not surprising combination of previous works, where most relevant techniques can be found in [14] and [25]. i.e., [14] designed and analysised  the same style algorithms for learning linear representation for multitasks in linear bandits and RL; [25] (and [31]) demostrated the construction of confidence bound for general class. Although I have quickly checked the proofs and believe the correcness of the main theorems (there are many inequalities and stataments that I have to guess the reason behind them, hope the authors can improve their writing), it is unclear what this work contributes.

2. Provable but intractable. The main difference between this work and [14] should be the representation extractor and confidence set (Line 202, 208 and 262 in this work and definition 1 in [14]). As mentioned by the authors (line 39), it is relatively easy to construct in linear class but hard in general. I expected the authors show how they construct the confidence set (*), but it is disappointing they used CNN as the representation extractor rather than solving line 202 and 262. It is mainly because the algorithms presented in this work suffer intractable computational cost, hence this makes us hard to derive any useful insight from their theorems to the practice.
questions: Firstly, I suggest the authors put a table to highlight the distinction from a single task to multiple tasks as well as from linear class to general class. As I mentioned in Weakness 1, I don't see the significant contribution made by this work. If the authors can convince me that challenges from previous works to this one are nontrivial, I will consider increasing my score. 

Secondly, I hope the author can connect the experiment to your theorems. For example, N(\Phi, \alpha) apparently is the main feature distinct from [14], but how can I see its influence shown in the experiment? Can the authors please point out in the rebuttal?
limitations: I don't see any potential negative social impact from their work and the authors address limitations properly.
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: The paper extends regret analysis for multi-task linear MDPs and bandit problems when a shared representation that is unknown to the agent is used across tasks. A general representation function class $\Phi$ and value function approximation class $\mathcal{L} \circ \Phi$ that is linear in $\Phi$ is used. To enable analysis in this setting, the eluder dimension of Russo et al. (2013) is adopted and $\mathcal{L} \circ \Phi$ is assumed to have bounded eluder dimension. In this setting, the paper provides novel regret bounds for a UCB algorithm for multi-task bandits and linear MDPs. In the bandit case for linear representation class, the paper states that the bound recovers the best known bound as a special case. For linear MDPs, the bound extends known bounds for the single task setting and achieves improved sample complexity over a naive baseline that does not share representations across tasks. An empirical analysis is provided as a sanity check to demonstrate reduced cumulative regret over time with increasing number of tasks.
strengths_and_weaknesses: Strengths:
- To the best of my knowledge, the paper is the first to characterize how sample complexity is improved in the multi-task MDP setting when shared structure is assumed for MDPs with low inherent Bellman error (IBE).
- The fact that the previous known bound of [14] is recovered as a special case for multi-task bandits is convincing regarding the sharpness of the bounds.

Weaknesses:
- Low IBE (Assumption 2.1) for all tasks strikes me as a potentially strong assumption. It would have been interesting to see how the algorithm behaves when a small subset of tasks do not have low IBE. How robust would the algorithm be in that case? If cumulative regret indeed grows linearly in the worst-case IBE as predicted by Thm. 2, this might be a shortcoming of the algorithm.
- The mathematical extension of regret bounds from single task to the multi-task setting seems somewhat straightforward. Nevertheless, shared representation structure is a key differentiator.
questions: Minor suggestions (typos, etc.):
- L318: "boarder" should be "border"
- Maybe capitalize section headers 3.2 and 3.3.

limitations: I was unable to find discussion of limitations of the algorithm/analysis in the text.
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 proves the first near-optimal regret analysis for multitask bandits and MDPs with a general function class representation learning. Different from previous literature, this paper consider general representation function that is not known to the algorithm. The algorithms follow the well-known optimism-in-face-of-uncertainty design. The effectiveness of the algorithm for bandits is validated on MINIST dataset.
strengths_and_weaknesses: Strengths:

The paper adds to the line of works that try to understand the benefits of multitask representation learning on sequential decision-making problems. As far as I know, it is the first paper to consider the unknown representation function beyond linear class. The paper is well-written and easy to follow. The proofs are complete.

Weakness:

My concern is that the contribution of this paper is highly incremental. Benefits of the similar form have been extensively discussed in the literature though it is a relatively new setting in this paper. I briefly went through the proofs. The paper makes very limited technical contributions. If there is any significant technical contribution, I suggest the authors point it out in the main text. The paper discussed both bandit and MDP settings, while the experiments are only conducted for bandits problems. It would be good to discuss the practice algorithm for MDP as well. 

It would be interesting to discuss the worst-case generalization performance for a learned representation, which seems to be a more interesting problem for multitask RL.




questions: Line 70: it would be better to point it out that this result is for contextual bandit setting.
Assumption 2.1: there is a typo.
Line 280: How is the performance boosted by $Md$? Should it be $\sqrt{Md}$?
limitations: I believe the main limitation of the proposed algorithms is that they are not practical. Discussing a practical algorithm for MDP case would be interesting.
review_title: null

Meta-review: metareview: This paper investigates the problem of multitask representation learning with general function class in contextual bandits and MDPs. The assumption is that functions of interest (e.g. the average reward in the bandit setting) share, among various tasks, a common representation. For example, in contextual bandits, this representation corresponds to that used in contextual linear bandits but where the feature maps are the same for the various tasks. Here we need to learn this feature map along with the remaining parameters. Compared to previous works, see Hu et al., the possible feature maps are not linear but belong to some given functional space. The authors propose GFUCB, an algorithm that extend the idea of UCB to this setting (the confidence intervals of UCB are replaced by a subset of likely functions). The authors derive regret upper bounds for their algorithms. These bounds illustrate the gains achieved leveraging the information gathered across tasks. 

The paper received 4 informative and insightful reviews. On the positive side, the paper is the first to give regret upper bounds for these kind of RL problems with representation learning. All reviewers further acknowledge the importance of this learning problems in practice. 

On the less positive side, reviewers have raised some concerns and have suggested ways to improve the manuscript. 
Among the concern, is the intractability of implementing the algorithm in practice. For example, the authors do not comment on how to compute $\hat{f}_t$ and (*) in practice. These quantities are at the core of the algorithm. We could say that an Oracle will solve these problems, but the authors could try to explain what kind of optimization problem we are facing and if there is a chance to solve it. This intractability limits the interest of the paper. 
Some reviewers were also concerned about the novelty of the approach (combining techniques from [14] and [25]). The paper is judged incremental. I believe that the authors have done more than just combining techniques, but the paper is very unclear about the technical novelty. The authors do not explain any intuition behind the proofs. The latter are actually, in my view, extremely hard to follow and to check. The presentation has to be significantly improved before we are able to really assess the contributions. In their rebuttal, the authors try to explain the novelty of their approach; all these arguments should be clear and apparent in the paper.



confidence: Less certain
Decision: Accept