Provably efficient multi-task Reinforcement Learning in large state spaces
Authors: Baihe Huang
Jason D. Lee
Zhaoran Wang
Zhuoran Yang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Reinforcement Learning
Multi-task Learning
Function Approximation
Sample Effficiency

Abstract: We study multi-task Reinforcement Learning where shared knowledge among different environments is distilled to enable scalable generalization to a variety of problem instances. In the context of general function approximation, Markov Decision Process (MDP) with low Bilinear rank encapsulates a wide range of structural conditions that permit polynomial sample complexity in large state spaces, where the Bellman errors are related to bilinear forms of features with low intrinsic dimensions. To achieve multi-task learning in MDPs, we propose online representation learning algorithms to capture the shared features in the different task-specific bilinear forms. We show that in the presence of low-rank structures in the features of the bilinear forms, the algorithms benefit from sample complexity improvements compared to single-task learning. Therefore, we achieve the first sample efficient multi-task reinforcement learning algorithm with general function approximation.

Under review as a conference paper at ICLR 2023
PROVABLY EFFICIENT MULTI-TASK REINFORCEMENT LEARNING IN LARGE STATE SPACES
Anonymous authors Paper under double-blind review
ABSTRACT
We study multi-task Reinforcement Learning where shared knowledge among different environments is distilled to enable scalable generalization to variety of problem instances. In the context of general function approximation, Markov Decision Process (MDP) with low Bilinear rank encapsulates wide range of structural conditions that permit polynomial sample complexity in large state spaces, where the Bellman errors are related to bilinear forms of features wi 'th low intrinsic dimensions. To achieve multi-task learning in MDPs, we propose online representation learning algorithms to capture the shared features the different task-specific bilinear forms. We show that in the presence of low-rank structures in the features of the bilinear forms, the algorithms benefit from sample complexity improvements compared to single-task learning. Therefore, achieve the first sample efficient multi-task reinforcement learning algorithm with general function approximation.
INTRODUCTION
The ability capture informative representations that generalize among multiple tasks has become significant in various machine learning applications Li et al. (2014); Tsiakas et al. (2016); Baevski al. (2019); D' D'Ermmo al. (2019); Kubota al. (2020); Liu al. (2019b). In the context of multi- task learning Caruana >; Baxter (2000); Yu et al. (2005), this ability is highly desirable and becomes vital learn with fewer amount of samples than learning each single task individually.
Representation learning [Bengio et al. (2013) is powerful approach for achieving such sample efficiency improvement.
This paper considers representation learning in Multitask Reinforcement Learning, an important class of meta Reinforcement Learning (meta-RL) Wang al.] (2016);; |Finn al. (2017); Ritter et al.) (2018). Reinforcement learning (RL) is sequential decision-making problem where an agent aims to learn the optimal decisions by interacting with an unknown environment (Sutton Barto (2018). Empowered by representation learning with deep neural networks LeCun et al. (2015); Goodfellow ct all (2016). RL has achieved tremendous success in various real woold applications, such as Go Silver al. (2016), Atari Mnih al.) (2033), Dota2 Berner et al. (2019), Texas Holdém poker Moravčík et (2017). and autonomous driving Shalev-Shwarte et al. (016)). Therefore, the benefit of using representation learning to extract joint feature embedding from different but related tasks emerged as an essential problem to investigate.
Specifically, this paper studies the problem of learning multiple RL problems jointly with the help of representation learning. Although multi-task learning in online-decision making problems has received increasing research interest Lazaric & Ghavamzadehl (2010); Mutti et al. (2021); Maurer et al. (2016); Qin et al. (2021); Yang et al. (2021); 1 et al. (0211) most existing works focus on tabular linear models. Indeed, how general function approximations extrapolate across huge state spaces remains largely open problem itself. Recently, Bilinear class Du et al. (202T) proposes a promising structural framework of generalization reinforcement learning through the use of function approximation. Bilinear class postulates that the Bellman error can be related to a bilinear form depending on the hypothesis and captures nearly all existing function approximation models, e.g.
Jin et al. (2020a); Zanette al. (2020); Yang & Wang (2020); Diang et al. (2017); Sun et al. (2019); Kakade et al. (2020); Agarwal et al. (2020). However, in the presence of shared information in the bilinear forms across multiple tasks, the Bilin-UCB proposed in Du et al. (221) is not able adapt

---

We conclude with discussions of further Under review as a conference paper at ICLR 2023
to such knowledge and challenges abound in adopting representation learning to find nearly-optimal policies with limited data.
In this paper, we give the first sample efficient algorithm of multi-task RL with general function appreximation through the usage of representation learning in Bilinear class. In particular, to study representation learning, we propose Low-rank Multi-task Bilinear class a structural framework that permits generalization both within and across tasks in multi-task RL. Specifically, such a model class specifies M MDP instances, where M > 0 is fixed integer and each one belongs to the Bilinear class Du et al. (2021). i.e., the Bellman error admits a low-rank factorization in Rd. Since our multi-task setting have M MDP instances, there are M different features maps specified by the definition of Bilinear class, each corresponding to one MDP task and taking values in R. We additionally assume that these M features maps, when packed together as a matrix-valued mapping in IR M has rank h < d. In other words, in Low-rank Multi-task Bilinear class, the bilinear form of each task possesses low-dimensional task specifee feature and a shared representation.
Under this setting, it is desirable that the RL algorithm utilize the intrinsic low-dimensional structure to achieve an improved sample efficiency compared to solving each task separately. To this end, under the online setting where the agent learn from its past experiences without knowing the model, we design a sample efficient algorithm that provably finds ncarly-optimal policies for all tasks. Our algorithm is based the principle of Optimism in the Face of Uncertainty (OFU) which constructs an confidence region that contains the true hypothesis based on the historical data across the M tasks, and then update the policy according to the most optimistic hypothesis within the confidence region. In particular, here the hypothesis can denote the true transition models or optimal value functions of these M tasks. When constructing the confidence region, we explicitly utilize the low-dimensional structure by joint learning the task-specific features and shared representation via Empirical Risk Minimization (ERM) with mulli-task data.
Moreover, as for planning, we find the hypothesis in the confidence region which leads to the highest aggregated value in these M tasks. In the analysis. we show a concentration result where the estimation noise can be embedded into low dimension space and thus prove that our algorithm is able to find nearly-optimal policies within limited samples. Concretely, compared to learning each task separately using Bilin-UCB Du et al. (2021), an algorithm designed for Bilinear class without utilizing the shared representation, our algorithm enjoys a (d/k) improvement in the sample efficiency whenever the feature classes small. To our best knowledge, work seems to propose the first provably sample efficient multi-task RL algorithm with general function approximation.
Notations Let d denote the d-dimensional space and kaxk denote the space of d-by-k matrices in I.. The inner product of two vectors x, y E IRd is denoted as (a. For sets A A., define Ax A @ .... @ A a1.0 denote the vector (a1, ................................ an)) Also let (aw)wen denote the tuple consisting of a. where comes from a countable set Ω. For variables ....... Uk. we denote by Ui.k the k-tuple (EI...., Uk).
{(a1.-. ..,) : agg E Ag, E [n]]- Given scalars "1.-.. ,a, let On,
Roadmap In Section 2 we introduce the basic problem setup and notations. In Section we introduce Low-rank Multi-task Bilinear class-a framework that captures shared information in bilinear class. Next, we display the main algorithm of learning Low-rank Multi-task Bilinear class models, empowered by representation learning and optimism principle in decision making, in Section 4 We show the main thcoretical result in Section S and the overview of techniques in Section 6 A couples of examples are given in Section A directions.
1.1 RELATED WORK
General function approximation in Reinforcement Learning Theoretical understanding of the sample complexity of RL. with general function approximation seems relatively scarce. In recent
years, there has been a surge of theoretical insights on linear function approximation and non-linear function approximations Jin et al. (2020b c); Wang et al. (2021); Zanette et al. (2020): Agarwal et al.
22000) Kakade et al. (2020); Wen & Van Roy (011 > Dann et al. (2018): ; Du et al. (2019); Dong
et al. 2020); Liu et al. [2019a); Wang al. (2020a); Dong al. (20211 b Zhou et al. (2020): Yang
ct al. 2020); et al. (2021a): Du et al. (2011) Among them, Bilinear class Du et al.
202T 18 one
of the most general framework.
2

---

Under review as a conference paper at ICLR 2023
Multi-task learning and Meta learning Meta Learning Thrun & Pratt (0012) and multi- representation learning |aaruaaa (1997) are important tools for capturing shared knowledge across tasks and achieving generalization to new task. Theoretical analysis dated back to [Baxter (2000);
Maurer (2005): Yu et al. (2005). Maurer et al. ( Amit & Meir (2018); y) Konobeev et al. (2000)
consider generalization errors averaged over the meta distribution under the assumption of shared
distribution for sampling the source tasks. Recently, Du et al. (2020); Tripuraneni et al. (2020b a);
Chua al. (202T) consider the diversity of task distributions and establish risk bounds based on learning shared representation across tasks and transferring to new tasks.
Multi-task bandit and RI. In multi-task bandit and RL. problems, theoretical analysis often postu-
lates the existence of low-rank of sparsity structures in the representation Lazaric & Ghavamzadeh
(2010); Brunskill & Li (2013); Calandriello al. (201 4); Mutti et al. (202];: Maurer et al. (2016);
D'Eramo et al. (019)); Arora et al. (2020); ; Qin et al. (2021) Yang et al, )) Hu et al. (022))
The most related works are Hu et al. (2021 D Yang et al. (2021) where the benefits of representation
learning of linear bandits and linear MDPs are studied. However, it remains open whether multi-task
RL can benefit from representation learning via general function approximation.
PRELIMINARIES
We consider learning a set of M problem instances
) P = (Mm (Sm; Am. (Pm,, hmml T'm 1m,1)
where each Mm denotes an episodic Markov Decision Process (MDP) in which S, denotes the state space, Am denotes the action set, H denotes the number of time steps in each episode, {IP m. H hh=1 denotes the transition kernel, rm denotes the reward function, and $m,1 denotes the fixed initial state. We assume T. E (0, 1) without loss of generality.
For MDP Mm let T denote the expectation under {P m, }H 1==1" A (deterministic) policy 7m is H To interact with Mms the agent length-H H sequence of functions Tm = (Tm,h : Smn b+ Am J h=1-
starts at fixed initial state $m,1 and at each time step h E [H]. it takes action 0m,h ~ km.h, receives reward Th (Sm,,h dm,x) and transits to 8m.h+1 ~ IP(-|sm,ht am,n). Let E denote the expectation under MDP Mm and taking policy Tm- We use Om, (sm,h: am,h, &m, 8m,h+11 at h-th time step MDP Mm. Given a policy Tmm we define the value function V V (s) as the expected sum of reward under policy Tm starting from sm,h = 5 at time step h:
to denote the history
H
Virin (s) = E.
Σ
I'm I'm (sm, am, (m,e))smm Smm.
Similarly, we define the Q-function Qiih a) as the the expected sum of reward taking action a in state 8m = and then following km,h:
Tur 0 (8,
Em
T'm (8m,ts am.)))mm = 8, Um,h
The Bellman operator Tmnh applied to Quuuction Q S. Am + IR. is defined via (Q) a) == Fm,, a) + Bg (.--P...---ld (-1s,a) [max Q(8/, aa))-
There exists an optimal policy गr that gives the optimal value function for all states, i.c. V sup, VT (s) holds for all h E [[]] and E Sm. Therefore Qhin. satisfies the following Bellman optimality equations for all Sm. Am and [H]:
T a) = Tm,
The agent aims at using fewer samples to find set of policies (m I such that
(51) V " (s1) Se
holds with probability at least 1 8. In the following, we define the filtration H, to be the o-fiedd induced by all the random variables up round I.
3

---

Under review as a conference paper at ICLR 2023
3 MULTI-TASK BILINEAR CLASS
In general function approximation, a hypothesis class denoted by Ç is applied to address the set P of M problem instances. Here, each hypothesis g information of both task-specific information of all M problem instances and the shared knowledge across tasks. For example, in model-based RL, 9 may denote the transition models of the M tasks, that is, (Pm, M.H
function approximation that captures the
m=1,/=1 Whereas in model-free RI., ! can be the optimal value functions of the M M
tasks, i.c., { m. mmm.m==, m=1.-=1 Using the notion of hypothesis g E G. we aim to cover a large class of MDP models studied under the function approximation setting. We will introduce concrete examples in Section A
Under our setting, each hypothesis E is associated with Q-functions {Qm.h.a('. (m()) and value functions (Vm,h.. (al.)))m)))))))))) me([M))e((() in the .M tasks such that Vm,h.()) = max, @m,h. holds for all m [M] and h E [M].
Bilinear class Du et al. 22221) is general framework that allows generalization in RL for a wide range of function approximators. In the following, we develop the low-rank multi-task bilinear framework so that it permits generalization in meta-RL across different tasks. The key intuition behind this framework is that captures the common representation via low-rank structures in the features of task-specific bilinear forms.
Definition 3.1 (Low-rank Multi-task Bilinear class). We say the following tuple
(9, {Mi Am, P Pm, I'm Sm,1) (m))))))eMMM.)....
multi-task Bilinear class with rank if there exists g" E G such that Qm,ha = Q and
Vm...g Vr hold for all m E [M]. h E [H]. and there exist functions W 9 + Rd mm, - RR. Bj, 9 Baxk and X G + Rd (d >> k) such that for each g G, m E [M] and h [H]:
1. The features W m.h possess low rank structures:
W m,, (g) Bi (g) (g).
2. We can upper bound the expected Bellman error as follows:
12 o (sm, am,.)) Tm, (Sm,hs am,)) V $ (( W (g") X (g)})
t
Here Tm.g, (8) = arg max. am a) is the optimal policy in MDP Mm under hypoth- esis g.
3. For any f E 9 there exist policy Test m (f) and discrepancy measure f g) that can be used for estimating (Vm, Bz(g) - Vm,, (gr ) (g))))) X,,,(())) for any E G. such that:
E
0m, Am.. rosess mm (Omm Mo
(W (W - W (g (g") ) (f)),
where Om,h (Sm,h: hm 8m,4+1).
Remark 3.2. A few remarks are in order. First, when d = k and M = 1, we recover the Bilinear class introduced in Du et (02T). Thus, our model can be viewed as an multi-task extension of Bilinear class with shared low-dimensions either be model-based function approximation or value-based function approximation, as in either case the Q-functions Qm,h.g and the value functions Vm,,.gg are well defined. Third, the common representation (-) captures the knowledge shared in all problem instances and enables multi-task learning with fewer samples. Finally, the discrepancy measure f ( .) can be computed for all hypothesis g, an important property that facilitates data reusage as explained below. Examples of I Low-rank Multi-task Bilinear class can be found in below and in Appendix A
representation. Second, here the hypothesis class G can
4

---

Under review as a conference paper at ICLR 2023
To understand this framework, first notice that the expected Bellman errors of the following forms
J.ck hm, (Sm, am,h) T'm.h (sm,hs 0m,h)
V b., (Sm,
serve upper bounds for the sub-optimality of policies #m.gg- Thus the Eq. indicates that the sub-optimality of policies Tm.9 can be controlled if the feature W m. (g) is close to the feature W " corresponding to the best-in-class function approximator g" Eq. (3) further establishes the connection between the error W ( W" mm (g and the discrepancy measure h, f (0m,h g). One important observation information sharing among the function class through the feature
X m, (f): given samples from a single function approximator f, the quantity
B ao
1 I Be Fe (f) (f.
can be estimated for all G. This thus allows for data reusage for each on-policy samples in our algorithm.
Eq. ① postulates that the features W W... (o) share low-dimension structure. Note that this structure is not fixed for all function approximator be a function of g. This allows for much generality in multi-task RL models. We will show that the low-rank multi-task bilinear class cover many existing function approximation models in multi- task setting. As compared with a great number of multi-task/meta RL algorithms that use a single representation to solve multiple tasks, our function approximators allow for more generality and therefore handles more structural conditions of multi-task RL such as those studied in Yang et al. (202T) and Hu al. (202T). Moreover, our algorithm reduces to using a single representation for the feature W in many special cases, for example when the feature "n A is trivial. In this sense, our algorithm can be seen as encompassing the method of using a single feature for multiple tasks.
in fact, the common representation Ba may also
Now we give an example of low-rank multi-task bilinear framework. This example shows that the proposed framework captures the linear mixture model Modi et al. (2020) in multi-task RL where the mixing coefficients of different tasks lie in the same low-dimension space. First, recall the definition of Linear Mixture Model in the following.
Definition 3.3 (Linear Mixture Model). MDP M (S, (Pa) 81) linear mixture model there exist known feature maps Φ S x AAASS Rd and + A + Rd and unknown 07 Rd h E [H] such that
Pa(s, = (0h, (bs a, 8))) (x(8,a) = (0h (b(8
It is known that linear mixture model is Bilinear class with hypothesis g = .i.....,0)) and
(g(g) = En, [bb(n, an) + Σ
a(sn, an an, s')nzzgss))) (n(9) Op.
s'ES
The discrepancy measure can chosen
(o g) = (0h, ((S,, an) + Σ vi(sn, V')V,LL, (V4+1, + rh)
and the estimation policies can be chosen as Reat(f) .Ty. We consider learning the special case of Low-rank Multi-task Bilinear class where each MDP Mm is linear mixture model with
(s, s') -68 (m, a, s')), "m, (fm (s,
and there exist V E R Bi E Raxk such that 6%. = BRy"n for all E [H,m E [M]. Then we let g = (Um,h, Br BB)ne(()) and use the (fixed) features Um, = Um,h, Br(g) = Br, Notice that each (Vm, Bn [e] will define the expectation Km... (via Pm, (s, a, 8') = (0m,, Pm (8, a, s²)) with Om, BpPm,n). Thus we can set the feature class X' induced by G in which the feature X m, (g) can be computed for each g G follows:
Xm, (g)
Em Tm.g (Sm, am,h)
Σ S'mS..
Om (mm am,hs s') V').., h4, ( (5'))
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Representation Learning in Low-rank Multi-task Bilinear class
Input: V.B.K'
for L 4 ,,...,7' do
Find (d)) as the solution of the optimization problem in Eq. (4
For vh E [H] m E [M,], sample no times from 0m,1:h-1 ~ mm,g(t) Om,h ~ est and create
datasets (11) end for
m,k"
Let to + maxxe(T) Em=1 V Vi (81)
Return T- ( (tt)
4 REPRESENTATION LEARNING IN LOW-RANK MULTI-TASK BILINEAR CLASS
In this section present the main algorithm to learn Low-rank Multi-task Bilinear class. First, define in the following the feature classes to capture A B% X m.h for m E [M] h E [H].
Definition 4.1 (Function approximations). We define feature class V V1 @
VH where Vi, C {v: G + [2) | J&M, Ah E [d], representation class B = Bi @ .0. 2 By where B, C BB :9 +
Bdxky, }. and feature class X X1 @ @ Xu where Xn C (X G + L wh E [H]
Here we assume that function classes V. B, and X' completely captures the mappings specified the multi-task Bilinear class. Therefore, given expressive V, B, X as inputs, we can learn the representations U1:M,1: V, B1-H B, M.HH. E X to approximate Uf.MI::1- XiM, by minimizing some proper loss function.
Based on this assumption, propose algorithm based on the OFU principle while leveraging representation learning to improve sample efficiency. The procedure is shown in Algorithm I In particular, in the /-th iteration, an (optimistic) hypothesis g( E is computed using Upper Confidence Bound (UCB) by finding hypothesis that achieves the highest total value in these M tasks. Specifically, consider the following constrained optimization problem:
Σ PPL
arg
gEg(O
which maximizes the sum of candidate value functions L. (8m.1) subject to the constraint that the hypothesis g( belongs to the confidence set g(t), As we will show the proof, g(9) contains the true hypothesis 9" for all E [7] with high probability. Thus, by solving (4) the sum of value upper bound of that of g".
functions of (t) serves
The key issue now is how the contidence set chosen. BiLin-UCB, the confidence set chosen to contain all hypotheses that possess small values in the average of discrepancy measures across the available batch data. Since the discrepancy measures serve as unbiased estimates for the bilinear forms which upper bound the Bellman error, this confidence set essentially finds all hypotheses with low Bellman error. However, this approach fails to exploit the shared information among tasks. Instead,
make use of the feature classes V. B, X' and learn the common representation (Bn hE( by Empirical Risk Minimization (ERM). For each hypothesis E G and E [H], let (uim B(s)
xx()) x 3) be the solution of the following optimization problem:
(Umm, 1300) x(0) ((s)))
(2)
arg min BL B...
E ( (s, - (Bn(g)mm,n(g) Bn X (n
Notice that g(s) depends on g and in the rest of this paper we use ÿ for simplicity of notation. With features (1ig), B(s) x(9) 1) the confidence set g(9) is then given as the collection of all possible hypothesis g such that the sum of squares of the bilinear forms across the available batch data is not

---

Under review as a conference paper at ICLR 2023
greater than pre-defined parameter R²: t-1 M ggg
g( -g9E
ΣΣ (0)
(,, xx (1())))) (o)))))) 1122
(5)
Due to the definition of (Vim,, B/() X b- 9). the bilinear form
(B)
(9) 9) (g) (9) (g) - B (ī)um, m.h (g), (x)xx(())) ((( m.h (g(
approximates (Wi,A (g) - WM (0) X contains all the hypothesis in which the sum of ((W", m.h (g) - W Wm,n (g"), i ()) over all history data and tasks is upper bounded by R We will show that this can be used quantify the Bellman error the candidate action-value functions under the corresponding greedy policy, which then can be related the sub-optimality of the corresponding greedy policy in the true environment. The width parameter R² can be enlarged to handle the cases where realizability assumption is not strictly satisfied. Since ERM is robust misspecification, optimism is still guaranteed and the analysis follows similarly. The resulting algorithm would thus have sub-optimality depending additively on the misspecification error.
for all E G. Therefore the confidence set g
This confidence set captures the shared information (-)() across tasks and contains all hypothesis with low Bellman errors within smaller Rt, Algorithm | then samples trajectories according to the greedy policies of the chosen hypothesis ( and the estimation policy Test and augments the available batch data with (()) m. h E [4], [M].
We note that the main computation workload of Algorithm that Algorithm [ oracle-efficient with access to an ERM oracle. In general, Line pertains to difficult optimization problem over the set of candidate function approximators g(+) Although no
I iss the ERM step Line 3 This means
efficient algorithms are currently known to solve this problem, we note that for certain instances of the bilinear class (e.g.. Yang et al. (2021)) where G is parameterized by variables in Euclidean space, computationally efficient gradient-bart based algorithms may exist to solve Line
MAIN THEORY
This section presents the theoretical analysis of Algorithm that the feature classes are all bounded.
I
Without loss of generality, assume
Definition 5.1. Assume || ( [B)x Vn, Bj, E B,, X,,k E X₁ and g E GG h [H) m E [M]. Here Cw, Cx E R.
Cw and | (g)ll2 Cx hold for all um.h
Next, it is important to consider the expressiveness of function classes V. V,B,A X. The following assumption common the theory of reinforcement learning Jin et al. (2220b) Wang et al. (20206) : Jin et al. (021b); Du et al. (2021).
Assumption 5.2 (Rcalizability). Assume g" e G and LLMMH E V, Bis E B, B,XiM.I E EX
Now we present the theory for Algorithm
Theorem 5.3. Set T' Md + MC² and
HT
R² = (M log( MMn Cx) log(
1)/ n/no-
8
With probability 1 8 the algorithm outputs a of policies 7 Mo
such that
V (o)) (s1) S O(HR).
The total number of trajectories used Algorithm 7 is upper bounded by OTHHTng) Therefore, with probability at least 1 6, Algorithm is able to use
H 2 (2 Mk + log(1 |
2

---

Under review as a conference paper at ICLR 2023
rraeectories find of policies { MEEMM such that
M
M
(
(81)
M (81) S
(6)
m.
m=1
m=1
Notice that if we use Bilin-UCB to learn each single task individually, then the total number of trajectories to achieve the above guarantee is H² d (og([C)/8) Indeed, to achieve Eq. (6. the average
sub-optimality of each task should be (ee/M). Using Bilin-UCB, achieving Vn (31) mm (81) S
c/M costs O H M di (og((51/0)/e3) samples for each task. Thus the total number of trajectories H d log( 91
is
via learning each task individually.
Therefore, Theorem 5.3 improves the sample complexity learning Low-rank Multi-task Bilinear class given small sizes of expressive feature classes V, B, X' for example, log(l-X)) < Md.
In general, the dependence on d can not be reduced since we estimate d-by-k matrix for shared representation. Furthermore, we believe that without further assumption, polynomial improvement w.r.t M impossible because the learner has to learn the task-specific features " R for all m E [M].
For an important special case known Linear Mixture Model (Definition 3.3 we have the following result via plugging | = |B] = 1, | = [9] into Theorem 5.3
Corollary 5.4. Consider Low-rank Multi-task Bilinear class where each MDP Mm linear mixture model with Pm,n(s, a, s') (6" (s, o, s')), (m,)(s,a) = (6% m_ (m(ssar a)) and there
exist Vm k B% Rddk such that mm,h Vm, for all [f], [M]. Let
x N(R c M @N(Ra
where (KK (e) denotes the e-covering of I² and N ((R Under Assumption 5.2 there exists algorithm that with probability at least ô finds set of policies {Tm (me[m(])) such that
.)) denotes the e-covering of Raxk
Σ
Vil (s1)
Σ
Var S
using
H HdM + kd) log(1/e0))
o
22
trajectories.
Remark 5.5. Using Bilin-UCK to learn each task individually, it takes O (HHM3 log(1/6) c-) trajectories to learn a set of policies {Tmm } such that
M
M
Σ
M (s1)
(s1) Sc. m=1
Σ
Therefore, Algorithm acchieees sample complexity improvement comparing to single-task learning. Without further assumption, polynomial improvement w.r.t M appears impossible because the learner has to learn the task-specific features Um,A E & for all E [M] with ((M**) sample complexity in total. The main benefit multi-task learning in this case is to reduce the dependence on the ambient dimension to k.
TECHNIQUE OVERVIEW
This section gives overview of the analysis and the main techniques. Owing optimism principle and the construction of confidence set via representation learning, the proof of Theorem |53 will crucially depend the following three observations:
8

---

Under review as a conference paper at ICLR 2023
Risk bounds for representation learning. Since the discrepancy measures unbiased estimations of bilinear forms, i.c.
E -ith f (mm.h Tart b. (Om, g)] = (W (9) - W (9") Xm),)
the solutions (u (u L. (00 x(0) l.m g of ERM will be able to concentrate to the population mean,
i.e.
(1)) (2) _ ( (7) X ())))) (B (0) BA " " x x (g)
This means that Algorithm has approximately captured the correct bilinear forms. Thus g essentially finds all hypothesis g such that (( ( (g ) ( X ( small.
Regret decomposition associated to the bilinear forms. One key property of Bilinear class is the upper bound of Bellman error as follow:
Em Om, wow. 1:1 m, (s Um,))) Tm, (Sm, am,)) Vm,nn (5m.hta)))))))
( (g) W W (9 )
Furthermore, we know that the sub-optimality of the greedy policy of candidate hypothesis can be decomposed into the sum of Bellman errors across time steps. Therefore, we show the following upper bound
M
M
M
(511
Σ m==1
V. (51)
S
"m, X, (mnaa()))
m=1
Coverage condition of features X (-).(()). Owing to the previous two observations, the issue left is to upper bound (1)
(, (g) - B (g" (""""""",, ) (g"), ), X a (g))] for some = =g(²) by the quantity ((B,())) (9) (g(gg) ) (g"), ) X
()))) Using Hölder's inequality, it suffices that
Σ. X (T) (g))) possess sufficient coverage condition of X k,, (g) for all m [M]. Setting T = ((Md) we will confirm this via elliptical potential lemma.
The proof of Theorem 5.3 is then established based on the above three observations. Since the second and third steps are natural extensions of the analysis of Bilin-UCB, the technical bulk is then to build risk bounds for representation learning. Specifically, we define the following failure event:
Definition 6.1. Define & as the event that there exist
[T] and
[H] such that
M
ΣΣ (BB) - "om (i
m=1m=1
(B (g) (3) (g)
B m. 1 x (9) (r())) RD.
(
We will show that [P]]] < 1- 8 with the choice of R in Algorithm The key step is embedding the estimation noise into low dimensional space R and achieve improved concentration.
7 CONCLUSION
This paper considers learning multiple RL problems jointly with representation learning. A structural framework proposed that permits generalization across tasks general function approximation. A sample efficient algorithm is designed based representation with ERM and optimistic principle where the confidence sets are constructed based on learned features. Theoretical analysis is displayed that the algorithm finds nearly-optimal policies within limited samples. Several examples discussed and sample complexity improvements are illustrated.
Given the success of representation learning in multi-tase task RL, it is interesting future direction to study transfer learning for quickly adapting prior knowledge to a new, unseen task with limited data and computational power.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2331 2320, 2011.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. arXiv preprint arXiv:2006. 10814, 2020.
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In International Conference Machine Learning, pp- 205-214, 2018.
Sanjeev Arora, Simon S Du, Sham Kakade, Yuping Luo, and Nikunj Saunshi. Provable representation learning for imitation learning via bi-level optimization. arXiv preprint arXiv:2002.10544, 2020.
Alexei Baevski, Sergey Edunov adn Yinhan Liu, Luke Zettlemoyer, and Michael Auli. Cloze-driven pretraining of self-attentioon networks. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)), pp. 5360-5369 2019.
Jonathan Baxter, model of inductive bias learning. Journal of artificial intelligence research, pp. 12: 149-198, 2000.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. In JEEE transactions on pattern analysis and machine intelligence, volume 35, pp. 1798-1828, 2013.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, and Chris Hesse. Dota with large seale deep reinforcement learning. arXiv preprint 191.:191,.066600 2019.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. In Proceedings of the Twenty Ninth Conference on Uncertainty in Artificial Intelligence (UAI-13), pp. 122-131, 131, 2013.
Daniele Calandriello, Alessandro Lazaric, and Marcello Restelli. Sparse multi-task reinforcement learning. In Neural Information Processing Systems, 2014.
Rich Caruana. Multitask learning. In Machine learning, pp. 28(1):41-75, 1997.
Kurtland Chua, Qi Lei, and Jason D. Lee. How fine-tuning allows for effective meta-learning arXiv preprint 11Xi:22055.0221,, 2021.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. On oracle-efficient PAC-RL with rich observations. In Advances Neural Information Processing Systems, 2018.
Carlo Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters. Sharing knowledge in multi-task deep reinforcement learning. In International Conference on Learning Representa- fions, 2019.
Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou / Vi-regret for learning in Markov decision processes with function approximation and low Bellman rank. In Conference on Learning Theory. pp. 1554-1557. PMLR, 2020.
Kefan Dong. Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. arXiv preprint arXiv:2102.04168 2021.
Simon S Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RI. with rich observations via latent state decoding. In International Conference on Machine Learning, pp. 1665-1674. 2019.
Simon Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:20022.0444 2020.
10

---

Under review as a conference paper at ICLR 2023
Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in In Proceedings of the 38 th International Conference Machine Learning, 2021.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 1126-1135, 2017.
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low Bellman rank are PAC-leamable. In Proceedings of the 34th International Conference on Machine Learning, pp. 7704-113, 2017.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pp. 4860-4869, PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020b.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143, 2020c.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. arXiv preprint arXiv:2100.00885,, 202
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and effice-efficient algorithms. arXiv preprint arXiv:2102.008775 2021b.
Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Information theoretic regret bounds for online nonlinear control. arXiv preprint arXiv:2006. 124666 2020.
Mikhail Konobeev, Iija Kuzborskij. and Csaba Szepesvári. optimality of meta-learning in fixed design regression with weighted biased regularization. arXiv preprint arXiv:2011.00344 2020.
Alyssa Kubota, Emma IC Peterson, Vaishali Rajendren, Hadas Gazss-Gazit, and Laurel D Rick Jessie. Synthesizing social robot behaviors for personalized neurorchabilitation and beyond. In Proceedings of the 2020 ACM/IEEE International Conference on Human-Rohe Interaction, pp. 121-130, 2020.
Alessandro Lazaric and Mohammad Ghavamzadeh. Bayesian multi-task reinforcement learning. In Proceedings of the 27th International Conference on Machine Learning, pp. 599-606, 2010.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
Jayy Li, Hongyan Zhang, Liangpei Zhang, Xin Huang. and Lefei Zhang. Joint collaborative representation with multitask learning for hyperspectral image classification. IEEE Tronsactions on Geoscience and Remote Sensing, pp. 5923-5936, 2014.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/trust region policy optimization attains globally optimal policy. arXiv preprint arXiv: 1906. 10306, 2019a.
Xiaodong Liu, Pengcheng He, Weizhu Chen, and Jianfeng Gao. Multi-task deep neural networks for natural language understanding. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 4487-4496, 2019b.

---

Under review as a conference paper at ICLR 2023
Andreas Maurer. Algorithmic stability and meta-learning In Journal of Machine Learning Research, pp. 967- 994, 2005.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, pp. 1-32, 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learningep reinforcement learning. arXiv preprint arXiv:1312.5602. 2013.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, 2020.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-57) 2017.
Mirco Mutti, Mattia Mancassola, and Marcello Restelli. Unsupervised reinforeement learning in multiple environments. In Association for the Advancement of Artificial Intelligence, 2021.
Yuzhen Qin, Tommaso Menara, Samet Oymak, ShiNung Ching, and Fabio Pasqualetti. Non-stationary representation learning in sequential linear bandits. In ICML 2021 Workshop on Reinforcement Learning Theory, 2021.
Samuel Ritter, Jane Wang, Zeb Kurth-Nelson Siddhant Jayakumar, Charles Blundell, Razvan Pascanu, and Matthew Botvinick. Been there, done that: Meta-learning with episodic recall. Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 4354-4363 2018.
Shai Shalev-Shwartz. Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv: 2016.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, loannis Antonoglou, Veda Panneershelvam, and Mare Lanctot. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pp. 2898-2933, 2019.
Richard S Sutton and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
Sebastian Thrun and Lorien Pratt. Learning to Learn. Springer Science & Business Media, 2012.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory transfer learning: The importance of task diversity. In Advances in Neural Information Processing Systems, 2020a.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. Provable meta-learning of linear representations. arXiv preprint arXiv:2002. 1684, 2020b.
Konstantinos Tsiakas, Cheryl Abellanoza, and Fillia Makedon. Interactive learning and adaptation for robot assisted therapy for people with dementia. In Proceedings of the 9th ACM International Conference Pervasive Technologies Related to Assistive Environments, pp. 1-4, 2016.
Jane X Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel 7. Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning to reinforcement learn. arXiv 2016.
preprint
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.00 150, 2020a.
Ruosong Wang. Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learning with general value function approximation. Advances in Neural Information Processing Systems, 2020b.
12

---

Under review as a conference paper at ICLR 2023
Yining Wang, Ruosong Wang, Simon S. Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. In Internationnl Conference on Learning Representations, 2021.
Zheng Wen and Benjamin Van Roy. Efficient reinforcement learning in deterministic systems with
value function generalization. Mathematics of Operations Research, 42(3):762-782, 2017.
Jiaqi Yang, Wei Hu, Jason D. Lee, and Simon S. Du. Impact of representation learning in linear bandits. In International Conference on Learning Representations, 2021.
Lin Yang and Mengdi Wang. Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. International Conference Machine Learning. 2020.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. Provably efficient rein- forcement learning with kernel and neural function approximations, In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 13903-13916. Curran Associates, Inc., 2020.
Kai Yu, Volker Tresp, and Anton Schwaighofer. Learning gaussian processes from multiple tasks. In Proceedings of the 22nd International Conference on Machine Learning, 2005.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, 2020.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. Proceedings of the 37th International Conference on Machine Learning, 2020.
13


Reviews:
[{"review_id": "x-szwaYWb9", "reviewer": "Reviewer_C4vX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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.", "strength_and_weaknesses": "Strengths:\nThe 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.\n\nWeaknesses:\nThe 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9t_h4ZfB6z", "reviewer": "Reviewer_k93P", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\nThe authors provides a PAC bound showing that their algorithm is more efficient than learning each task separately.", "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.\nYet I recommend that the authors add a few sections with empirical results and discuss more the validity of the assumptions used in their proof.", "strength_and_weaknesses": "Strengths:\n\n_ 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\n_ 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\n\nWeaknesses:\n\n_ 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?\n_ 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] \n_ 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?\n_ 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.\n\n[1] Ray Interference: a Source of Plateaus in Deep Reinforcement Learning, Schaul et al., 2019", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0kRAMeubJC", "reviewer": "Reviewer_7kqp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "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.\n\nThere 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. \n\nSecond, 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.\"\n\nThird, 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject