Multi-User Reinforcement Learning with Low Rank Rewards
Authors: Dheeraj Mysore Nagaraj
Suhas S Kowshik
Praneeth Netrapalli
Naman Agarwal
Prateek Jain
Venue: Submitted to ICLR 2023 (2023)
Keywords: Low Rank Matrix Estimation
Collaborative Reinforcement Learning

Abstract:     In this work, we consider the problem of  collaborative multi-user reinforcement learning. In this setting there are multiple users with the same state-action space and transition probabilities but with different rewards. Under the assumption that the reward matrix of the $N$ users has a low-rank structure -- a standard and practically successful assumption in the offline collaborative filtering setting-- the question is can we design algorithms with significantly lower sample complexity  compared to the ones that learn the MDP individually for each user. Our main contribution is an algorithm which explores rewards collaboratively with $N$ user-specific MDPs and can learn rewards  efficiently in two key settings: tabular MDPs and linear MDPs. When $N$ is large and the rank is constant, the sample complexity per MDP depends logarithmically over the size of the state-space, which represents an exponential reduction (in the state-space size) when compared to the standard ``non-collaborative'' algorithms. 

Under review as a conference paper at ICLR 2023
MULTI-USER REINFORCEMENT LEARNING WITH Low RANK REWARDS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the problem of collaborative multi-user reinforcement learning. In this setting there are multiple users with the same state-action space and transition probabilities but with different rewards. Under the assumption that the reward ma- trix of the N users has a low-rank structure a standard and practically successful assumption in the offline collaborative filtering setting we design algorithms with significantly lower sample complexity compared to the ones that learn the MDP individually for each user. Our main contribution is an algorithm which ex- plores rewards collaboratively with N user-specific MDPs and can learn rewards efficiently in two key settings: tabular MDPs and linear MDPs. When N is large and the rank constant, the sample complexity per MDP depends logarithmically over the size of the state-space, which represents exponential reduction (in the state- size) when compared to the standard "non-collaborative" algorithms.
INTRODUCTION
Reinforcement learning has recently seen tremendous empirical and theoretical success Mnih et al. 2015); Sutton et al. (1992); Jin et al. (2020b); Gheshlaghi Azar et al. (2013); Dann & Brunskill 2015 Near optimal algorithms have been proposed to explore and learn given MDP with sample access to trajectories. In this work, we consider the problem of learning the optimal policies for mul- tiple MDPs collaboratively so that the total number of trajectories sampled per MDP is smaller than the number of trajectories required to learn them individually. This combines reinforcement learn- ing and collaborative filtering. We assume that the various users have the same transition matrices, but different rewards and the rewards have a low rank structure. Low rank assumption is popular in the collaborative filtering literature and has been deployed successfully in a variety of tasks Bell & Koren (007); Gleich & Lim (201) ); Hsich et al. (2012). This can be regarded as an instance of mu multi-task reinforcement, various versions of which have been considered in the literature Brunskill]
& Li 2013); D'Eramo et al. (2020); Teh et al. 2017) Hessel al. (2019).
Motivation Recently collaborative filtering has been studied in the online learning setting: Bresler & Karzand (021): & (2022), Here multiple bandit instances are simultaneously explored under low rank assumptions. In this work, we extend this setting to consider stateful modeling of such systems. In the context of e-commerce, this can allow the algorithm to discover temporal patterns like "User bought a Phone and hence they might be eventually interested in phone cover' or 'User last bought shoes many years ago which might be worn out by now, therefore recommend shoes'. Note that the fact that a user has bought a shoe changes their preferences (and hence the reward function). Our setting allows one to model such changes. While we assume that the users share the same transition matrix, this can be relaxed in practice by clustering users based on side information and modeling each cluster to have a common transition matrix. This approach has been successfully deployed in various multi-agent RL problems in practice, including in sensitive healthcare settings (see Mate et al. (2022) and reference therein).
Our Contributions a) Improved Sample Complexity: We introduce the setting of multi-user collab- orative reinforcement learning in the case of tabular and linear MDPs and provide sample efficient algorithms for both these scenarios without access to generative model. Under low rank assump- tion, the total sample complexity required to learn the near-optimal policies for every user scales as Ö(N + [S][ instead of (())) in the case of tabular MDPs and Ó(N + d) instead of O ((Nd)) in the case of linear MDPs.

---

Under review as a conference paper at ICLR 2023
b) Collaborative Exploration: In order to learn the rewards of all the users efficiently under low- rank assumptions, we need to deploy standard low rank matrix extimation/completon algorithms, which require specific kinds of linear measurements (See Section I.Ip. Without access to gener- ative model, the main challenge in this setting is to obtain these linear measurements by querying trajectories of carefully designed policies. We design such algorithms in Section 3
c) Functional Reward Maximization: In the case of linear MDPs, matrix completion is more chal- lenging since we observe measurements of the form ef e where O+ R& corresponding to the reward obtained by user i, with respect to an embedding v. Estimating O under low rank as- sumptions requires the distribution of & to have certain isotropy properties (see Section 6). Querying such measurements goes beyond the usual reward maximization and are related to mean- -feld limits of multi-agent reinforcement learning similar to the setting in Cammardella et al. (2020) where a
functional of the distribution of the states is optimized. We design procedure which can sample- efficiently estimate policies which lead to these isotropic measurements (Section (5)
d) Matrix Completion With Row- Linear Measurements: For the linear MDP setting, the low rank matrix estimation problem lies somewhere in between the matrix completion (Recht [011] Jain et al. 2013) and matrix estimation with restricted strong convexity (Negahban et al. 2009). We give a novel active learning based algorithm where we estimate O* row by row without any assumptions like incoherence. This is described in Section
1.1 RELATED WORKS
Related Settings: Multi-task Reinforcement learning has been studied empirically and theoretically
Brunskill & Li ) Taylor Stone (2009); D Eramo al. (2020) Teh et al. (2017): > Hessel al.
(2019): Sodhani et al. 2021). Modi et al. (2017) considers learning a sequence of MDPs with side information, where the parameters of the MDP varies smoothly with the context. (hahh et al. (2020) introduced the setting where the optimal Q function (s a), when represented as a S x A matrix has low rank. With a generative model, they obtain algorithms which makes use of this structure to obtain smaller sample complexity whenever the discount factor is bounded by constant. [Sam] itt al. p022) improves the results in this setting by considering additional assumptions like low rank transition kernels. Our setting is different in that we consider multiple users, but do not consider access to a generative model. In fact our main contribution is to efficiently obtain measurements conducive to matrix completion without generative model. Hu al. (2021) considers multi- task RL problem with linear function approximation similar to our setting, but with the assumption of low-rank Bellman closure, where the application of the Bellman operator retains the low rank structure. They obtain bound depending on the quantity N Vd instead of (N + d) like in our work. Lei & Li (2019) considers multi-user RL with low rank assumptions in an experimental context.
Low rank matrix estimation has been extensively studied in the statistics and ML community for decades in the context of supervised learning Candès & Tao (2010); Negahban & Wainwright (201T); Fazel (2002); Chen et al. (2019); Jain et al. [2013) [017]] [2013]20177
Low Rank Matrix Estimation:
Recht (2011) et al. (2020); Chi et al. (2019) in multi-user collaborative filtering settings. The basic question is to estimate a di x d2 matrix M given linear measurements (a:] My.) when the number of samples is much smaller than d1 x d2 using the assumption that M has low rank.
a) Matrix Completion: z; and ys are standard basis vectors. Typically x; and y! are picked uniformly at random and recovery guarantees are given whenever the matrix M is incoherent (Recht) 2011).
b) Matrix Estimation: x; and y/i are not restricted to be standard basis vectors. Typically, they are chosen i.i.d such that the restricted strong convexity holds (Negahban et al. 2009).
In this work, we consider MDPs associated with N users such that their reward matrix satisfies a low rank structure. For the case of tabular MDPs, we use the matrix completion setting and for the case of linear MDPs, our setting lies some where in between settings a) and b) as explained above.
1.2 NOTATION
By || we denote the Euclidean norm and by Cl...., Cs.... the standard basis vectors of the space R. for some m E N. Let S := {Ir E Id |||||| = 1}. Let By(r) == {a e Rd ||ж||| < r}. For any x n matrix A and set Ω C [n] by A we denote the sub-matrix of A where the columns
2

---

Under review as a conference paper at ICLR 2023
corresponding to Ω2 are deleted. By A(A), we denote the set of all Borel probability measures over the set A. In the sequel,
PROBLEM SETTING
We consider N users indexed by [M] each of them associated with horizon H MDP with the same state-space S, the same action space A and same transition matrices P = (Pi...., PH-1), where Ps (-18h; as) is probability measure over S, which gives the distribution of the state at time + given the action dh was taken in state 8n at time h. Each user has a different reward denoted by R2 (Bias.... RHa) where Ria- x user u by Ma := (S,A, R.). For the sake of simplicity, we will assume that the rewards are deterministic.
1]. Denote the MDP associated with the
We assume that all the MDPs start at random state S1 with the same distribution. Consider a policy II := (ITI.... TH) where Th ((A) x S + R+ is a kernel i.,, (-(ss)) gives the proba- bility distribution over actions given state at time h. By (SI.H, A1.r) we denote the trajectory (SI,A)) , (S2, A (Su, Ar) ) E S x A. By (SI.H, AI.11) ~ M(II) we mean the random tra- jectory under the policy II where As trajectory of the MDP under the policy II. Define the value function of M,, under policy as: V(I,,M,) = E(s.. Auw)=I E Ran (Sn, An). We will call a policy II, to be e optimal for M, if (Il,; M.) 2 supT VIII,
(-(-)Sa) and Sh+1 Pa An). That is, it is the
Our goal find optimal policies for every u [N] with as few samples as possible under low rank assumptions on the rewards Ruh.
Reward Free Exploration: The objective of reward free RL is explore MDP such that can obtain the optimal policy for every possible reward. After collecting K trajectories from the MDP sequentially (denoted by Dx), the algorithm outputs functions Il and V whose input is reward function R
(+-))) (bounded between [0. 1)) and the output policy (T( and its estimated value (R)) for this reward function. Denote the MDP with this reward function by Mr. Given 0 and 8 E j0, 1], we let K 8) to be such that whenever K 2 K (c, with probability at-least 5 we have:
nearly-optimal
a) sup& (VÍÍ - V (ii(R) S and b) Il is an optimal policy for MR for every R.
This setting was introduced in Jin et al. 2020a). In this work, we will use the reward free exploration algorithms in Zhang et al. (2020) for tabular MDPs and Wagenmaker et al. (022) for linear MDPs.
Tabular MDP Setting S and A are finite sets. Denote the reward ( a) by the N x [S||_A] matrix RA where R3 (u, (s, a)) Rha(s, a). We have the following low-rank assumption: Assumption (Tab) 1. The matrix R₁, has rank for some
(nin(N,(S||AA)
Linear MDP Setting Our definition is slightly different from the one in Jin et al. (2020b). this setting, we consider embeddings o S A - Rd, v S A + Rd such that [0(s, a)llı < 1, [|vs(s, ala & 1. We make the following assumptions:
1. There exists 0ir E Rdd, [10hul12 S vd such that Riuls, a) (fhou (sss, a)) and Ra, [0, 1].
2. There exist signed measures "ik....,,ay over the space S such that: Pa(-Is, = (a)(),))
We will assume that μ4; are such that || uaa (ds))({ a) (da)s)) [s]] < 1 and sup.. I [p (ds) S Cn- This is true whenever μan are probability measures. We consider different embeddings for transition (d) and reward (t) as the transition embeddings have a natural || structure since they give linear combinations of measure which make up PA (-|s, a). We denote the N x d matrix whose u-th row is 0T, to be θ₁ The low-rank assumption in this setting takes the following form:
Assumption (Lin) 1. The N x d matrix O₁ has rank r S min(N,
For the task of reward maximization in Linear MDPs, deterministic policies of the form nH (s) = argsup, (s, a), vi,)) (Ø(s, a), vf) suffice, for uh, 0% E IRd. We want to complete the matrix O
3

---

Under review as a conference paper at ICLR 2023
with data of the form (et, (Sh: An), A.)) To achieve matrix estimation, we need to query AS) such that the distribution of (5Sh, is 'nearly isotropic' (See Section 6). Such result of reward maximization policy of single agent
As) cannot necessarily be obtained and is related to mean-field limit of multi-agent RI (similar to the setting in Cammardella et al. (220)), and it could necessarily be randomized policy. However, the space of all possible policies can be very large and intractable. Therefore, we restrict our attention to policies given by some fixed policy space Q. With some abuse of notation, we define the total variation distance between two kernels as: TV( T == supses (V( T (-ls). We define distance over Q by Da(11 ,1((2)) = [и TV(T))
(1) Th (2) where 11 = (T h E [H]). We refer to Section A for additional discussion on the above observations, connections to multi-agent mean-field RL and construction of Q such that it contains all e-optimal policies for every possible linear reward.
3 THE ALGORITHM
Our algorithm proceeds in 4 phases. Note that since all the users our setting have the same transition probabilities, we can reward free RL (Phase 1) in distributed fashion over the users. Reward free exploration is useful in this setting since all users share the same MDP and the main unknown is the reward matrix. Reward free exploration can be done collectively by selecting random users instead of the same user, which reduces the per user complexity. This is then used two ways: 1) Collaboratively exploring the space in order complete the reward matrix (Phase 2) 2) Learning the optimal reward for every user once the reward matrix is known (Phase 4).
3.1 TABULAR MDP CASE:
Phase 1: Reward Free Exploration We run the reward free RL algorithm Zhang et al. (2020) for
KT E 2) = C |SI (1S++log(3)) polylog( (S] (LAA)) time steps by picking the MDP corresponding to a uniformly random user whenever the reward free RL algorithm queries trajectory. Let the output of the reward free RL algorithm be 1l and V.
2²
Phase 2: Querying the Reward Matrix this phase we query a 'uniform mask" with the parameter
p for the reward matrix RA using Algorithm [ For each (s.a) S A and h E [H] maintain a counter (s.)). for (s. E S x A and h E [H) initialized at 0. Given the 'active sets' g = (Gh (Sn)nen C S x and h E [H], we define the reward [( = (JI....;Jh) by
[s, a; 9) = (((s,a) E 9r)
(1)
We will denote this reward by J(::). Initialize active set g = (Gn)nE(H) such that Gn. S x A. We initialize the reward matrix Ra (u, a)) = *, where denotes unknown entry. This algo- rithm terminates when it detects that sufficient number of samples have been collected for matrix completion.
Phase 3: Reward Matrix Completion We receive G. and the partially observed matrix Rt for each h as the output of Algorithm By f we denote the sub-matrix where the columns corresponding to Gn are deleted. We use the nuclear norm minimization algorithm given in Recht (001 to recover p A for every h E [H].
from
Phase 4: Computing the Optimal Policy Phase 3 outputs the completed sub-matrix Sh where only the columns corresponding to | are recovered. We construct the recovered matrix RG by setting Eech = ne and N&gh O. We compute the optimal policy for each user using the rewards from Rs, via the output of the reward free RL, îi, from Phase 1.
3.2 LINEAR MDP CASE:
Phase Reward Free RL We run the reward free RL algorithm for Linear MDPs from Wagen- maker et al. (2022), with error and probability of failure 4.
à We use trajectories from random users
whenever trajectory is queried. Here, Ktd 8/4) C CdP/2 H (og
4

---

Under review as a conference paper at ICLR 2023
Output: Active sets G = (G)) Partially complete matrix RA
& - 0;
pe (( ñi (T;:)))
while 69 > do
U Unif (ni((
// Pick user uni uniformly at random
S1.H
s(t) A 1:11 R Mr, (119):
// Query trajectory
for E H do
if (S h (00)
(t))
E Gn and Ru, (5 A
then
1. 1 +
+T,, hs
( + +1;
// Increment count
Rn (S) (1))) R
// Fill Missing Entry
end
if h. ( = Np then
Gn 9h \ {(S) ))
);
// Remove element from Active Set
end
end t + 1+1;
ps t V([(:)));
IT - (T(()))
end
Algorithm 1: Uniform Mask Sampler for Tabular MDPs
Phase Querying Linear Measurements of the Reward Matrix We obtain policies whose tra- jectory data allows low rank matrix estimation of the reward matrix.
Step 1: For each time step h [M], want query obtain samples (s) a (1) such that (t)
Σ. d(s aa TT h to some subspace of Rdd by Qr.q denote the reward [[Q&(s, a)ll at time h and O otherwise. The termination condition ensures that we see enough data in all directions ø which allows to find collaborative exploration policy below.
( = I2I. This can be done by Algorithm 2 Given a projector Q
Using the observations given in Step 1, we compute the policy I which approximately satisfies the property given in Assumption 3 This procedure is described in Section
Step 2:
Phase 3: Estimating Low Rank Reward Matrix For this, we use the active learning procedure
given in Section 6 via row-wise linear measurements along with the policy MC, was computed in Phase
ii which
Phase 4: Computing the Optimal Policy Once the reward matrix O₁ have been reconstructed for every h in Phase 3, we use the output of reward free RL in order to compute the e optimal policy for each user.
4
MAIN RESULTS
4.1 TABULAR MDP:
The standard assumption for low rank matrix completion is that of incoherence, which ensures that the matrix is not too sparse so that sparse measurements are sufficient to learn it. The following definition used in Recht (20IT).
Definition 1. Given a dimensional sub-space of R2" we define the coherence of as:
u(U)) sup 1 1315
A Th n2 matrix M with singular value decomposition UEVT is called (Hos j1) coherent if:

---

Under review as a conference paper at ICLR 2023
Input: Total time T; Tolerance n lower isometry constant
Output: Uke, S(t+1ye for E [H 1]. t t [T]
1:
while h _ H 1 do
Q 1+=1;
NT )())))))
Ga,h + 0;
// Grammian initialized to
t 1;
while t T do
U² Unif([M])
// Pick uniformly random user
S1.HAAH ~ Mu, (i19):
// Obtain Trajectory
the (((S,,AA)))
S(h+1) t Sh+1
G + Ga.h + @
// Update Grammian
if 3y E
< x² then
- the eigenspace of Go with eigenvalues < R²2 R²I; ATP :
end
f < t+1
end
h < h +1
end
Algorithm 2: Well Conditioned Matrix Sampler
a) The coherence of the row and column spaces of are at-most pi b) The absolute value of every entry of UVT is bounded above by pu
Given a policy II, and Ω S S by PT we denote the probability that at time have (Sh, An) E Ω under the policy II. Assumption (Tab) Given the reward matrix Rg and Sr C x A, recall the notation for the sub-matrix RSth of Ry. If suuu (2)) have:
1. Rh is (Ho p1) incoherent.
2. 1 [S]
The incoherence assumption for RR makes sense since the set 52 cannot be easily reached with any policy with probability larger than In fact we can arrive at an optimal policy for the original reward by just setting the rewards at 52 to be 0. These can be thought of redundant states which do not matter for our RL model with any reward.
Theorem 1. Suppose Assumption (Tab)
hold.
Let the parameter P
C max((H).n))rrree N[STA
log? [S(lA) H.
for some large enough constant C. Assume that |S] and N are large enough such that p 1/2. Then, with probability at-least 1- 5, we can find an e optimal policy IL, for every user u E [N] whenever the total number of trajectories queried is:
C |2 ([S) + +lg(())
polylog( |S [1IAA))+ C'maxppi, PO) + (S|IA)) log² |
22
Remark 1. For large N, the number of trajectories queried per user is Ög log (IS((A4)) which is an exponential improvement in the state-space size dependence when compared to the minimax rate of (S! Dann & Brunskill 2015 Every phase in the algorithm has polynomial computational complexity in N, SS| and L. The probability is chosen such that p S|| (((([S](AA)+))) which is the number of free parameters required describe rank matrix.
c.

---

Under review as a conference paper at ICLR 2023
4.2 LINEAR MDP
Assumption (Lin) 2. There exists a > such that for every x E Sd-1, and every h E [H] there exists a policy 2i such that whenever SI.H. A I1.,h. (6 x) 27
The assumption above shows that hold for any 7, then (SSn An) does not have any component in some direction 3o with any policy. Thus, remove the sub-space spanned by 2 and make the embedding space Rd-1 time h.
obtain information about all directions. If this does
Assumption (Lin) 3. There exist S. such that for every h E [H], there exists a policy ITh. Q such that whenever SI.H, AI-H ~ M( we have:
inf E KKt (Sp, As))lvd Ed(a, ( An) 25 #ES4-1
The assumption above ensures that there exist measurements (S AA.) which are conducive to low rank matrix estimation as considered in Section 6
Assumption (Lin) 4. For any r there exists an y net for Q denoted by Qn such that log Qul & (og(
We refer to Section A where we justify this assumption. We first demonstrate that deterministic policies which are sufficient for reward maximization (as used in Jin et al. (2020b)) cannot be used set of stochastic policies is required. We then construct such policy classes with D O(dH log dH log log((AA)).
in this context,
Theorem 2. Suppose Assumptions (Lin) and hold and suppose e < 3. In Algorithm we set = CC,dH
log
C. H(d+() S76
and T C log de
Then, with probability least 1- ò, our algorithm finds optimal policy for every user
[N] with the total number of trajectories being bounded by: Tí + Tool + Tmmt-comp where:
C. Hid+ ()
To (d+log ())
d212 H log' log'())
C., ( + +D) log?
5y6
Tpol
Tmat=comp
C Hr(N+dlog N) log d
+ log log( log
CE
Remark Note that whenever N is large, we have the the sample complexity per user be ( This is much better than the dependence of odd in the minimax lower bounds for Linear MDPs [Wagenmaker et al.) 2022). While Phases and 2 of the algorithm have computational complexity which is polynomial in d and }. the optimization problems posed in Phase 3 and 4 are not neces- sarily polynomial time. We leave the computational aspects to future work. Notice that the sample complexity Ö(r(N + d)) corresponds to the number of free parameters required to describe a rank matrix.
OBTAINING POLICIES WITH GIVEN STATISTICS
In this section, we consider the Linear MDP setting and describe the sub-routine described in Step of Phase 2 of the algorithm where we compute a policy fi such that the law of @(S,, Aa) under this policy approximately satisfies the property given in Assumption This is required in order to use the guarantees for low matrix estimation in Phase 3, which is described Section 6 We first state a structural lemma which characterizes the law of S4+1, Ast1 under any policy II.
Lemma 1. Consider any policy II = (T.,..., 1, TH) to the MDP M. Let SHH,Ai M(I). Then any bounded, measurable function g A E, we have:
d
Eg(Sh+1: ARt1)
Σn, vi 1=1
g(s, J (dal))
Where := (Ee(Sh, es)

---

Under review as a conference paper at ICLR 2023
We want to estimate certain statisties under any policy using available data, obtained from the output of Algorithm 2 Notice that the output Algorithm 2 gives a sequence of ran- dom variables (ØK1, (t+ ((+m)):-... mn...... (ØuT, ((h-1)T) Id x S such that (s(4+1))E1l(0@))
(n)) and Go.t Σ @ne For any measurable function g :SAA- R RRd such that ||||| S and any randomized policy IT ( TH) we define:
IL
1. T)) = R ()r
2. Th+1 mh+1) = (u, ei) f (un(ds)Ta+ (dd s)g(s, a) when < H
3. Ff(TT) (0,
2/12
4. (II) = inf Mh. P1.... F(II, Ph.,,.,.... P) whenever >
Define ahe 01 G
S.h. V. We estimate these operators from data as follows:
1. (1) = Et= [(oe,, () (dal(11))
2. (9, 1 Et= one, ())
3. (III (0, T - 2/11
4. Ex (II) inf ph...... (III M1,,.,, Ph-1, whenever
Where, for h > 1 and V1, , Ph-1 E Ba(1), we have defined:
1. P(IT, ... 1h un) = FY (IT) Σ
2. F(II, V1, ...., Vh 1h-1 vn) = ETT (II)
d ンド (0,
Define a(),;;))= = (0, (s, a)) Vd Ed(z; v 8, a)) The output of our method is:
1. ft = arg suPT (m [0) inf ses (f
2. (MT..,,) sug PEB(I)
inf (1;=s))) m.) whenever h > 1, subject
to Eo.A ( < n70
3. Assign output: iic.c.h f
The idea behind this method is follows. First, using the output of algorithm 2 we construct (n v, mn), which approximates the functional Tg v. Ty) uniformly for every v, Th- This is shown in Lemma in the appendix. We will show in Theorem 3 that obtaining policies which can used with matrix completion routine reduces to picking a policy II = (TI....,,,) such that whenever SI.H, AL-H MMIII..), we must have: E Ennszes--1 S(S,, Aniz) 2 Ç. Now, we use Lemma [ to conclude that such a policy exists, then there exist 1/,..., 1h-1 such that Eø(S), such a policy approximately by optimizing using the estimates & instead of the exact functional T as described above.
M and inf i To. (; Ph, Th) 2 Since only have sample access, find
Theorem 3. We condition on the event Go.h 2 x2 for every [H]. Let K. Th To be such that for some small enough constants Co. c. > 0 and large enough constant C' > 0:
1. 11 CCannva-eaa V T; no co C.lvatdE)
C
2. K CCalVateajan Vog
C.ll + dHf log (g)
Recall the policy fis.h. Suppose the Assumption holds. Then, with probability at-least 1 - 5
4 we
obtain the policy f is such that whenever SI.H, AI.H M(iif.)) we have:
E
inf f(S,, Ani 8
8

---

Under review as a conference paper at ICLR 2023
This implies that (Sh, An)) satisfies B| (sh A)),
2v2'
Eb(Sh, An)
6 MATRIX ESTIMATION WITH ROW-WISE LINEAR MEASUREMENTS
In this section, we describe the active learning based low rank matrix estimation procedure. For an unknown rank matrix @ (corresponding to the reward matrix O in the definition of Linear MDPs) of dimensions N x d, we are allowed to query samples of the form (e,, 15, e ='²)p) for any i E [N] of our choice and & = (h(S,, AA) where SI:H, AI. ~ M(TMMC.A). for some input policy Ic This corresponds running the MDP corresponding user i, with the policy MI and observing the reward at time h, given by (ex, 0, v (Sn, Ax)). Our basic task is to estimate the matrix O' from these samples with high-prott probabiitt.....
v))
6.1 THE ESTIMATOR
Given any N x d matrix A, by A,, we denote its i-th row. Given K E N, and sequence of vectors V (Wis E IRd SE(NTAE())))
K LIA, V) = NK Σ Σ (A va))
We estimate O' row-wise using the following iterative procedure, where recover some rows of θ* into in each iteration and obtain the corresponding linear measurements of @*. Letting the set of unknown rows at iteration / to be 7 (with To = [N]). We draw a fresh sequence of vectors (T(() from some distribution, we then recover some rows T C I of O* and store them in θ.
1. Draw vi(O (v je(iK]ien we obtain 0z e. On
Vikk
2. Consider the loss function
L( 0², 1(0)
(O,, (1 0%
K, -- iET.-1
3. Find matrix θ with rank < such that L(e O³ (1())) 0.
4. Initialize T, +- 0.
5. For every E T.-1, draw K fresh samples using 3 .... ,,10 and compute ΣK (0,, ((t) -
2(0)
) 1 If EK (O,, - - > 0 then add i to I iie. I + I,fii..
6. End routine when I, = 0.
Suppose the are i.i.d random vectors such that there exist E such that for any E Rdd
||>||| = we have:
||al|| almost surely; E (V),)))2 2
Edaii <
Vd
dea
To give some intuition, the second condition above means that given any vector x, there some overlap between the random vector & and x, ensuring that every measurement gives some in- formation helping us complete the matrix. The third assumption covariance matrix. Then we have the following theorem whose proof is presented in Section
standard bound on the
Theorem 4. Assume that sup; ||0,1| || Co and that the distribution of th satisfies equation
(t)
Suppose K, K, = - log <E
+ log loxx)
With probability at-least 1- the algorithm
C2ga
terminates after log N iterations and the output satisfies θ = O Therefore, with probability
at-least 1 8, the sample complexity for estimation of e is:
log
C r(N + dlog log d + C
log log
8
5262
5262

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alckh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep. pp. 10-4, 2019.
Robert M Bell and Yehuda Koren. Scalable collaborative filtering with jointy derived neighborhood interpolation weights. In Seventh IEEE international conference on data mining (ICDM 2007), pp. 43-52. IEEE, 2007.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymp- totic theory of independence. Oxford university press, 2013.
Guy Bresler and Mina Karzand. Regret bounds and regimes of optimality for user-user and item- item collaborative filtering. IEEE Transactions on Information Theooy, 67(6) 2021.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. arXiv preprint arXiv:1309.688 6821, 2013.
Neil Cammardella, Ana Bušić, and Sean Meyn. Kullbackk-eibbe--guuartiii optimal control. arXiv preprint 000V:::0004007995 2020.
Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix com- pletion. IEEE Transactions on Information Theory, (155):2553-0880 2010.
Yuxin Chen, Jianqing Fan, Cong Ma, and Yuling Yan. Inference and uncertainty quantification for noisy matrix completion. Proceedings of the National Academy of Sciences, 116(46):22931- 22937, 2019.
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Under- standing statistical guarantees for convex relaxation via nonconvex optimization. SIAM journal on optimization, 30(4):3098-31211 2020.
Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factoriza-
tion: An overview. IEEE Transactions Signal Processing, 67(20):5239-526) 2019.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed -hrdiioiooon reinforcement
learning. Advances in Neural Information Processing Systems, 28, 2015.
Carlo D'Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, Jan Peters, et al. Sharing knowl- edge in multi-task deep reinforcement learning. In 8th International Conference on Learning Representations, pp. 1-11. OpenReview. net, 2020.
Devdatt P Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. BRICS Report Series, 3(25), 1996.
Maryam Fazel. Matrix rank minimization with applications. PhD thesis, PhD thesis, Stanford University, 2002.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3): 325-349, 2013.
David F Gleich and Lek-heng Lim. Rank aggregation via nuclear norm minimization. In Pro- ceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 60-68, 2011.
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojciech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 33, pp. 3796-3803, 2019.
Cho-Jui Hsieh, Sai-Yang Chiang, and Inderjit S Dhillon. Low rank modeling of signed networks. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 507-515, 2012.
10

---

Under review as a conference paper at ICLR 2023
Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learn- ing for linear bandits and linear rl. In International Conference on Machine Learning, pp. 4349- 4358. PMLR. 2021.
Prateek Jain and Soumyabrata Pal. Online low rank matrix completion. arXiv preprint arXiv:2209.03997, 2022.
Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alter- nating minimization. In Proceedings of the forty-fithh annual ACM symposium on Theory of computing, pp.
2013.
Prateek Jain, Purushottam Kar, et al. Non-convex optimization for machine learning. Foundations and Trends in Machine Learning, 1063-4):1423333, 2017.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference Machine Learning, pp. 4870-4879. 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.
Yu Lei and Wenjie Li. When collaborative filtering meets reinforcement learning, arXiv preprint arXiv:1902.007/1 2019.
Aditya Mate, Lovish Madaan, Aparna Taneja, Neha Madhiwalla, Shresth Verma, Gargi Singh, Apamn Hegde, Pradeep Varakantham, and Milind Tambe. Field study in deploying restless multi- armed bandits: Assisting non-profits in improving maternal and child health. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 12017-12025, 2022.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529 533, 2015.
Aditya Modi, Nan Jiang, Satinder Singh, and Ambuj Tewari. Markov decision processes with con- tinuous side information. arXiv preprint arXiv:1711.0555
2017.
Sahand Negahban and Martin J Wainwright. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. The Annals of Statistics, 1069))07691097, 201
Sahand Negahban, Bin Yu, Martin J Wainwright, and Pradeep Ravikumar. A unified framework for nigh-dimensional analysis of m-estimators with decomposable regularizers. Advances in neural information processing systems, 22. 2009.
Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
Tyler Sam, Yudong Chen, and Christina Lee Yu. Overcoming the long horizon barrier for sample- efficient reinforcement learning with latent low-rank structure. arXiv preprint wwxivv2206.03560 2022.
Devavrat Shah, Dogyoon Song, Zhi Xu, and Yuzhe Yang. Sample efficient reinforcement learning via low-rank matrix estimation. Advances in Neural Information Processing Systems, 33:12092- 12103, 2020.
Shagun Sodhani, Amy Zhang, and Joelle Pineau. Multi-task reinforcement learning with context- based representations. In International Conference on Machine Learning, pp. 9767-9779, PMLR, 2021.
Richard S Sutton, Andrew G Barto, and Ronald Williams. Reinforcement learning is direct adap- tive optimal control. IEEE control systems magazine, 12(2):19-22, 1992.
Matthew Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey. Journal of Machine Learning Research, 10(7), 2009.

---

Under review as a conference paper at ICLR 2023
Yee Teh, Victor Bapst, Wojeiech M Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. Advances in neural information processing systems, 30, 2017.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Andrew J Wagenmaker, Yifang Chen, Max Simehowitz, Simon Du, and Kevin Jamieson. Reward- free rl is harder than reward-aware rl in linear markov decision processes. In International Conference on Machine Learning, pp. 22430- 22456. PMLR, 2022.
Zihan Zhang, Simon S Du, and Xiangyang Ji. Nearly minimax optimal reward free reinforcement learning. arXiv preprint arXiv:2010.05901, 2020.
A MORE DISCUSSION REGARDING POLICY SPACE
A.1 NECESSITY OF RANDOMIZED POLICIES
We will first show that randomized policies might be necessary in such contexts with simple ex- ample and show that obtaining states which satisfy conditions like equation []goss beyond simple reward maximization. Suppose H 1, S {1} and A {I,..., d}. We consider the em- bedding (s, a) = Ca. Suppose we want to obtain a policy и such that whenever A1 ~ m, Amin (S2, A1 (1) T) is maximized (where Amiu denotes the minimum eigenvalue). This maximized when (dals) ) is chosen to the uniform distribution over A and the corresponding value is 1/d. Note that whenever и is deterministic policy we will have Amin whenever d > 1. This is in contrast to reward maximization problems where, under general conditions, a deterministic optimal policy exists (See Theorem 1.7 in Agarwal et al. (2019))
If fact, we can also show that the policy which minimizes necessarily be random.
[EE 1 _ ea must also
In the case of linear MDPs, we can find such a deterministic optimal policy (TI..... R as (s) argsup, (18(8, a), uft) + (Ø(s, a), v7)) (Tin et al.) (020b)) This reduces the problem to estimating the parameters uf, 2f even when the state-action space is an infinite set. However, when such policies
not guaranteed to exist, as in case of functional maximization required in
Section 6 the set of all policies can be intractably large. This the justification for picking a nice enough policy space denoted by Q
A.2 CONSTRUCTING POLICY SPACES
We consider any linear MDP satisfying the definition given in Section 2 and suppose A is finite.
We consider the set of all probability distributions TA (a s; u, exp( (o(( s, a), u) + (vi(s a), e))- u E (R)], We let our policy space be Q = (II
We consider QA = [a|sa u. u)
(MI,-... TH) T. E Q.).
Lemma 2. Consider the probability distribution over a finite set [[Al] give by pa(a) exp(Bx.))
for every E [[AA]] some Ia E R+ and 3 E IR+. For any > O and random variable A ~ Pa. we
must have:
P(za < supxa c) |A e/eexp--8e
And
Er 2 (sup xa
exp(-3e))
Lemma 3. Let (8, a) be the optimal action-value function for the MDP. Then the policy II
(T..... Th) given by ny (als) x exp(3Q7 (s, a)) is eH + H² [A| exp(-3e) sub-optimal for any
0
12

---

Under review as a conference paper at ICLR 2023
Proof. Consider the optimal value function defined by (s) sup, (s. Let (s, a) denote the optimal action value function under the policy IT and let V(s) { denote the value at state s with the policy II. Clearly, we have: QH(s,a) = Qn((s,a) = R(s. a). (s( 2 Q (s. a) uniformly. Then we have
Vx(+) 2 / Q% ( 11 ( - =) |A| exp( -1
2 sup (s, - c- A| exp( Bc) - -1 (s) - c c H|AA -Bc)
-1 (3)
In the second step, have invoked Lemma 2 In the last step, have used the fact Q7 [0, H] uniformly. Now, by the Bellman iteration, we have:
(s,) R 1 (s,
+ E l((a,a) (s'(s'
2 R (8, a) + Eg V/((')) - H A exp(-Bt) -1
= 1 a) - - H| expl -3c) -3c)-1) -1
(4)
Therefore, by induction, we conclude that (s(s) (s) eH |2 exp(-3E) Therefore, by the definition of the value function, we conclude the claim.
Now, by a simple extension of Proposition 2.3 Jin et al. 2020b), we conclude that the optimal Q7 function for any linear MDP can be written as:
(s, (1)(s, u(t) + (ó(s, vf))
Where ||, $ Vd and bo S HHC,- Observe that choosing E 2Hf
7 and ,3 2 1o (AI/m)
will ensure that the randomized policy II in the statement of Lemma 3 is 7 optimal. Therefore, we can take R = 2dHC, log(2H) Al/v) in the definition of Qn above and conclude that this includes every optimal policy for every MDP with embedding functions d, th We will now bound the covering number. Recall the definition of the distance Do(II, II2) supse[m]] TV(T)) (l) (
Therefore it is sufficient to obtain an cover for Qn (denoted by @...)) and then construct Q =
{II (Ti,.... TH): Th Qh E [W]] = -II Qu.y
Lemma 4, <[ss; u, v) be as defined in the beginning of this Subsection.
TV(T(-1s;;,)) w).
S (exp(21lu- u'112 + 21|p v' 2'llo0) 1)
Proof. Denote =(a|s;,,)) v) by T(a) and π =(als;e',')) by <aaa). Consider the correspond- ing partition functions denoted by Z == ΣeEA exp((v(s, a).u) + (o(s, a), o}) and Z' := Eaea exp((1((s a), u/) (d(s, a)))). We conclude that using Hölder's inequality for (u - ul, v))
and (v- v', d) that:
Z'
exp(-1l ||u u' - 110
llx))
S
< exp(llu w'112 + ||u v1))
7
u' 2'112 -21le v') < 7'(a)
exp(-2) 2
< exp(2||u u- u'12 2/12 v' oo)loo)
(5)
T(a)
TV(T,x*) 2/2
Σ (T) - ra)))
aEA
Σ
π(a)|1
{'
π(a)
aEA
(exp(2|lu u - ul 2 211u r'1lo0) - 1)
(6)
2
13

---

Under review as a conference paper at ICLR 2023
Using the lemma above, conclude that Qh., (Ia u, Ban/4(R)) whenever ? S 1. Here B (R) an v/4 net over (a( with respect to the norm ||2.. From the results in Vershynin (2018), can therefore take:
12..l [Baa/((R)2 < exp(Cdlogg Ca
Since we had Q, = I we conclude that:
log(1(%)) S odH (log d!l " + (ogglog(2H))4)))
A.3 RELATIONSHIP TO MEANFIELD LIMITS OF MULTI- RL
Consider the conditions given in equation for (S,, A,,) where S1-H,AI [lmat-comp,,, We refer to the proof of Theorem to show the following condition implies the conditions given in equation
inf (v An), An), (d(o 26 SES
Conversely, the conditions equation 2 implies the following:
5º5 (N.SS,,,),,) S 2
inf (b A.). x) 2\
Therefore, the problem of obtaining policy satisfying equation 2 reduces to finding a policy such that the functional inf, (S), An), ==\vvd (b An).z) x)² is maximized for some small enough 3 E Rt. Note that this functional maps the distribution of (S,,AA) (denoted by I (II)) obtained by applying some policy II real number. Let us denote this function by J.T Our objective now is to find a policy [[mat-comp. by solving the following optimization problem
arg sup (IT) neQ
This setup is similar to the mean field multi-agent control problem presented in Cammardella et al. (2020). To explicitly see the connection Multi-agent systems, consider n agents with the same MDP M and embedding functions é, tb. Each trajectory from this multi-agent system corresponds to jointly and running the MDP associated with each agent with the same policy independently. The collective reward of the system is given by J(Ln), where f', denotes the empirical distribution of state-actions of the agents at time h. Note that on the one hand, picking a policy IT, to maximize this reward is a reward maximization problem on the joint multi-agent system. And, for any fixed policy II, as n + 0o, (II) + (II) under reasonable assumptions on the state space via the law of large numbers and hence (f', (II) + (LI)) under continuity. Therefore the planning problem in equation is the same as the multi-agent planning problem described above in the limit
+ DO.
B ANALYSIS TABULAR MDPS
We will call the reward free RL procedure in Phase to be successful if it outputs the e optimal policy. This has probability atleast
B. ANALYSIS ALGORITHM
Lemma 5. Suppose < J. conditioned on the success of Phase 1, with probability at-least 1 exp(-cNpl AHH, Algorithm terminates after querying C)SN trajectories. (Gn)nelH) the active sets at the termination the algorithm. They satisfy:
H
sup
PM (g S 8
(9)
14

---

Under review as a conference paper at ICLR 2023
For any x b matrix R, let R be its partially observed version (that is, there exists set of indices S [a] x [b] such that Rig Rij if (i.j) I and Roj otherwise). We call random set of indices to have the distribution Uni [a], [b] is drawn uniformly at random such that [J|=m] m.
Lemma 6 (Modification: Mod1). Suppose we independently, modification of algorithm ! where on the "Query trajectory" step the trajectories are sampled from a fixed MDP M1 (but rewards are from the reward function corresponding Ut). Consider all the random variables that determine the trajectory of this algorithm: (v, fr, (S A Ri ), (Ua))). Then the joint distribution of this collection of random variables unchanged under the modification.
Proof. The proof follows from an induction argument on the time index t. We describe the key steps here. For the ease of notation, let T. - ( A R( Let XT (V, Ii, (Tr)sTT) Let Xy and T. denote the corresponding quantities under the modification. enough to show that finite dimensional marginals have the same joint distribution under the modification. In particular, we will show:
1. To To
2. Suppose XT - Xy. Then the Markov kernel &Tr+1 Xr is almost surely (under the com- mon distribution of Xx,, Xx) equal 11 Thus XT41 d 8244
The first statement is straightforward since, in the zeroth step, the distribution of fo9 not affected by the modification, and thus due to identical MDP transitions across users, the distribution of To preserved under modification. A similar argument proves the second statement. Roughly, given a realization of Xy the distribution of T++1 same as the distribution of Tr+1 given the same realization of Xy, due to the exact same reason presented for the first statement. A fully formal proof requires setting up appropriate proability spaces, random variables considered are all discrete, one can argue via PMFs as well.
omit it here. Furthermore, since the
Lemma 7. Suppose S 2- conditioned on the success of Phase I and termination of Algo- rithm for every E [H], the Algorithm 1 returns partially filled reward matrices Ri.. Con-
sider the sub-matrix Rgg. Let In S. [N] gh be the sub-set of observed indices for Ry- Let
Jnl9, Unif( No [N] GB). There exists a coupling between Jn, and In such that
P (J, S (. 2 |-||A exp(ccXpp
Proof. Let fix Gr and construct coupling between I, and Jn-
Consider any fixed, arbitrary permutations 0g over [N], for g gh. By (TT)), denote {(ag())g)) : (1.g) E I.).
Claim 1. Conditioned on Gn, (JI) has the same distribution as In.
Proof. Let (Ni a) E (xxA be a set of arbitrary permutations on [N]. From lemma it is enough prove the statement for the random variables under the modification described in that lemma (call this Mod1). Now consider a further modification (call it Mod2) where in every iteration t, we sample U,- Uni]([ for each horizon h we set Ú
(s())) ,A(")) (Ut), and then update
the entries of (U,0) h (s("), A (instead of Rs (U., (5 ( Next, we couple these two modifications by using same (V, IT) and the same set of U 's for both the modifications. Further, couple the MDP used in these modifications to be the same, single MDP.
Now an induction argument shows that the sequence of active sets obtained in these modifications are also identical for every time t; only the rows of RG where entries are filled change according to the set of permutations chosen.Thhe Thus, under the described coupling. Mod1 and Mod2 produce
15

---

Under review as a conference paper at ICLR 2023
identical trajectories (i.e., (S A A )) the columns of reward matrices are just permutations of each other described by the chosen set of permutations, and algorithm terminate at the same time in both these cases. However, the same induction argument also shows that for each and h, conditioned on Gh, trajectories (which is same in Modl and Mod2) until at beginning of iteration t, we have (Ut, (5 )) d (Ü (s )).
Therefore if In. I C [N] x gh denotes the subset of observed indices at termination (outside the active set), then In o (1a) = (())),)) (s,a)) (i, (s) 1x) and, conditioned on Gn. T I
Claim 2. At termination, conditioned on Gh, random sets 1 {(i,g) : (i,g) E 1n are jointly independent.
Proof. Again we work with the modification Modl described in lemma 6 For each (s, a) consider the collection of U,'s 's that are used populate the column (s, a) of matrix Rg in algorithm [ collection U(s.a)-
Call this
Remark 3. Since the columns of In have exactly Np entries, permutation invariance proved in the above claim implies that
For any set J [N] G.. define the count function (Ng)) such that Ny. = Ki [N] (i,g) J.--
We are now ready to give the coupling: given Gr. draw uniformly random, independent permutations og for g E G.. Draw (Ng) independent ag and to have the joint law of (N g)E8 Define:
Jn {(o,()) : Ng. (
i, (() Np. gh
Claim 3. The marginal distributions of Jn and In are respectively the distributions of Jn. and In-
Proof. First we will prove a general statement about ~ Unif(r, [N], [M]) Let X E {0, N with Xmm 1 iff (i, m) J.. Let (Nm) M be the count functions corresponding to J Jie. Nm E3 Xi, Let Y.. (X1.m= random vectors Y.. are jointly independent. Indeed, pick any E {0, 1 and (nI, mm). Let ym be the m'th column of v.
.N.m). We will argue that conditional on {Nm E [M]]. the
Then
Fi,m Pmm 1)
P z, Om (N,. nm
II
Σ
Σ 2,m
Zi,m
(MN)
The above can also be written as
Σ Fs.m = 14m )
P (Ym = b, Om (Nm = nmmll
= II
Σ 12m = r
(MN)
m
Let denote the all 1 vector in N.N. Note that 7m (012,, (.N.m) we see that
Marginalizing the above,
IP [m = Rmm
II
Σ Pym =
(MM)
m
Thus the conditional distribution can be expressed as
P
mm (Ym = }m Om (Nm = nmm} =
[1 Vm nm
1 m
nmm =
N mm
M
16

---

Under review as a conference paper at ICLR 2023
Since the (conditional) joint PMF factors, it is easy calculation to show the conditional indepen- dence i.e.,
Mm mm Vmn Mm {Nm = mm) -
IP
Ym
ymm
Om {NN 1mm
Furthermore, for any n1, am such that En Pem = T, marginalization shows
1 [[1 ym nm)
P Pm yml Om (Nm Rm }}
N
Let N_m = (N1, .. Nm Nm+1, ... ,NM), and similarly for n n-m-- Then IYm = Mm N-m = n Nn = nm]
P m yml Om {Nim nm [ P[N-m n-m m nm
Σm nm +
Um Am
P
P IN nml otherwise
The above factorization directly implies that Y,,, conditioned on Nm is uniformly distributed on its support {y 1 y= 3mm. and is independent of N Thus
mm (Ym = ym Om {Nm = nm
Ym = ym
Nm = 1mm
ym
Tm
Observation: The above calculations give another way to generate Y: first generate N,,... Na from the right distribution, and then conditioned on Nm generate each Yn uniformly such that 1 Y Nm-
Next we apply the ahove calculations and observation to J J,19, ~ Unif( Npig 2
[N]. g. For
uniformly random permutation on [.V,, the set {a(i) 1 S S k} is uniformly distributed on all k-sized subsets of [N]. In the statement of the claim the permutations are chosen independently for each E gC- Thus from the above observation, we have Jn Jn, conditioned on G
The claim about Jn follows directly from permutation invariance proved by claim
Claim 4. P(N > Npl9a) S exp(-coNp) for every y E gf
Proof. Throughout this proof, we will condition on the terminal active set Gr. We will show this using the results on concentration with negative regression property as established Proposition 29 in Dubhashi Ranjan (1996). N₂ >.V 1((i,)) g) J.). Now we will show that the collection X = ((2, g) Jn. for i [N], E G satisfy the negative regression property. By the definition of negative regression, we can conclude that the sub-collection (Xig)ie(N) () also satisfies this property for every Gb-
Y: for every L. The negative regression property is satisfied iff for every K₁, K₂ C [N] G such that K₃ n K₂ 0. and real valued function f(Xm m E K2) which is non-decrggiigg with respect to the partial order, we
Consider the partial order over binary vectors
Y iff X,
must have:
ol4:1 K2) [f( E K1) X1 41 4T K2]
17

---

Under review as a conference paper at ICLR 2023
be such that g is a non-increasing function in t with respect to the partial order. Note that in the case of uniform distribution in Jn, the distribution (Xm)me,, the uniform, permutation invariant distribution with constant sum almost surely. The sum being Nr Eiek, t. Therefore, whenever of 2 t for every I K2, we have the following stochastic dominance:
(Xm)mEX, Xx tivl K2
[(Xm)mEX, X1 tivl K2
Therefore, this coupling leads us to conclude that:
g(4 : K2)
E [f(Xm
X1 - E K2]
Σ E [f(X m K1) Xi = t/vl E K2)
g(t LE K2)
(10)
The second step follows from stochastic dominance. This implies that the function is non- increasing which establishes the negative regression property. Now, we consult Proposition 29 in Dubhashi & Ranjan (1996) to show that we can take Chernoff bounds on N₂ Eig(n Xig as
though X were i.i.d Ber(p). Therefore, from an application of Bernstein's 's inequality (Boucheron et al. 2013). we conclude the statement of the claim.
Now, Jn S I, if and only if N₂ I Np for every E Gf. Therefore, from the claim above, we have P(J, 1 2 | exp (-cgNp).
We are now ready to prove Theorem
Proof of Theorem 7 In order to establish the result, we need to show that with p as set the state- ment, the algorithm returns e optimal policies Il, for every user u E [N] with probability at-least 1-
The total sample complexity is the number of trajectories queried in Phase plus the num- ber of trajectories queried in Phase 2. Phase 1 queries KT (2:2) traecctories, which is
C ||)AA|H (1S)+ ) polylog( [SIIA[") by the results of ZZang et al. (020)) By Lemma 5 we
conclude that the sample complexity of phase is C(SIAAINH and with the value p given the statement of the theorem, this succeeds with probability at-least when conditioned on the success of Phase 1.
We will show that conditioned on the success of Phase 2, with probability at-least 4 the nuclear norm minimization algorithm of Recht (2011) successfully obtains R Indeed by Theorem 1 in Recht 2011 we see that whenever co-ordinates of ng corresponding to random indices drawn from Uni [N) are observed with C₁ max(pī po)r(N + log? | log( # ), the algorithm succeeds at recovering 12 with probability at-least we observe is
5 в
The number of co-ordinates
Np|SAl
Np
2 20, max(p) + ( log" 10% log( #
2
In the last step, we have used Assumption 2 to conclude that 1 2 the definition of large enough, must have:
|S||A|]
For the constant C in
2
Np g m S
2
Note that the results of Recht (2011) requires at-least observations be chosen uniformly random co-ordinates, but we do not obtain observations which are uniformly at uniformly random
co-ordinates. Here, we will the results of Lemma 7 Let Jn. be fictitious subset of co-ordinates
18

---

Under review as a conference paper at ICLR 2023
distributed Unif(m, (R) when conditioned on g.. If the observed co-ordinates are Jns then can successfully estimate the reward matrix R. with proability at-least 4 in this case. Now, SH
suppose that the actually observed co-ordinates are T, which is a strict super-set of Jn- Then we check that the matrix completion algorithm, which is based on constrained nuclear-norm minimiza- tion, still succeeds with observed co-ordinates corresponding to IA. whenever it succeeds with the observed co-ordinates correspond to Jh.
We now refer to the coupling in Lemma which shows that we can couple Jn. to the real distribution In such that J/. S IT. with probability at-least 5
SH When the constant C1 in the definition of p large enough, we conclude by invoking Lemma that: Jn, S 1 with probability at-least 877 Applying union bound for h [H] conclude that Phase succeeds with probability at-least when conditioned on the success of Phases and 2.
- &
Therefore, from the arguments above, we conclude that Phases 1,2 and succeed with probability
at-least 1-d å and give us the reward matrices 12 where the sets satisfy the following equation from Lemma 5
H PR (9 S
5e 8
sup
(II)
h=1
now remains to show that we obtain e optimal policies for each user after Phase 4. Note that whenever Phase succeeds,
compute e/4 optimal policies for every possible reward function bounded in [0, 1]. Since we do not know the rewards over the set Gh. we set it to zero as described in the algorithm to obtain RA It remains show that planning with R₁ and using it with the reward free RL algorithm gives us an optimal policy. Suppose II; is the optimal policy for user u and suppose II,, be the optimal policy for user under rewards Ra(u, (8, a)). Note that combined with the guarantees for the reward free RL, in order to complete the proof of the theorem, it is sufficient show that the policy II is 3c/4 optimal with respect to the actual rewards RA(u, (s. a)). Let Si.H: Ai. ~ M and S1.H, A1:H ~ M(I.).
E
Ru,u, (5% AR)) S E Σ
(u, (S, ( AA) (. + 1((S), E 9n)
H Ra (u, AR) + 1((5), AT) E 9v) = E >
H
H
Ru,u, (S), A;)) + Σ p (G))
k=1
h=1
h=1
5c
E
R2 (u,
h=1
5e
RA (u, (Sh, An)
H
5c
<
E
Ry (u, (Sh, An)
h
(12)
In the first step we have used the fact that the rewards uniformly bounded in [0, 1]. In the second
step, we have used the definition of Rd (u, (s,a)) R₂ (u, (s, ()) a) E g In the third step, have used the guarantee in equation 11 In the fourth step, have used the fact that Pi maximizes the reward R, In the fifth step, we have used the fact that RG (u, a)) 2 Ra (s, a))
uniformly. From the discussion above, this concludes the proof of the theorem.
19

---

Under review as a conference paper at ICLR 2023
C ANALYSIS LINEAR MDPS
Lemma 8. Suppose Assumption 2 holds. Let 6. > and 2 C de
(x-c)² log dx
With probability at-
q-c'
least 1 - H exp( - e) the output of Algorithm returns 6sh such that Ei=1 Onh th - x²2 for every h [H]
Proof of Theorem
2
By Theorem 1 in Wagenmaker et al. (022).. we take (e,6/4) =
CáH (d+Hog( 1) Cd log"()) Phase I succeeds with probability 1 6
4'
Note that this is the quantity T in the statement of the theorem. We now condition the success of Phase 1. The number of trajectories queried by Algorithm[2 (orrithh@@wichh which is given by HT = Too. By Lemma 8 we conclude that for the given values of T and K, this algorithm successfully outputs oie such that Go. ž I²I for every h [H]. with probability at-least 1 -
Now, condition on the success of Algorithm 2 By theorem 3 we conclude that with these conclude that with proabability at-least 1 4. with the values of the given parameters, for every h E [H]. the
procedure Step 2 of Phase outputs policy Îi such that whenever SI.H, A1:H M()fFA) the conditions in equation 2 is satisfied for the random vector (Sh,, As.) with Ç replaced by c/2. We then use the active learning based matrix completion procedure given in Section 0 where the vectors diyk are sample using the policy fT on the given user. By theorem we conclude that conditioned on the success of all the steps above, with probability each of the matrices 07 for h [H] with Tamt-comp number of samples.
1. we can exactly estimate
Upon the success of Phases 1, 2, 3 (which occurs with probability at-least by union bound), conclude that Phase 4 gives the optimal policy for each user E [MV] because of the guarantees of reward free RL.
D DEFERRED PROOFS
D.1 PROOF OF LEMMA 5
Proof. We suppose that the reward free RL in Phase succeeds and returns the optimal policy for every choice of rewards bounded in [0, 1]. The algorithm terminates whenever the active sets are such that
(((())
(13)
Note that by the definition of J(:9), the maximum value for the MDP with reward J(:]) is supn Σøm (G.). Since V is the output of the reward free RL algorithm, we conclude that
we have:
H
(((()) sup Σ
Pl
(G))
(14)
8
We conclude via equation 13 and equation 14 that equation 9 hoold, which establishes the second part of the theorem. We now consider the termination time.
Suppose g(t) is the sequence of active sets before termination at step (i.c, it satisfies ((T( > f). Recall fi, the output of the reward free RL algorithm. It follows from the guarantees for reward free RL that:
Σ pff (g(())
sup Σ ( h=1
Combining this with Equation equation 14 and the fact that V(T(:g()) 2. we conclude:
H
Σ
p
(g)
2
(15)
h=1
20

---

Under review as a conference paper at ICLR 2023
We consider the potential function with yе()) 0 and (p(( Eneim E(s,))exx T(()) h.(o,)) where T-( (,(x,,)
is the counter (s,(),a) inside Algorithm at the beginning of the step
Whenever g()) is such that (I > 2. we define N; := g + 1) pp() (i.e, before termination). Just for the sake of theoretical arguments, we define the fictious random variables N₁ Ber(g) i..dd after termination. Let J. (g(+), (( ( R Ul)) 8
Claim 5. The following relations hold:
1. E [N
2. E [N <
3. Ne] & H almost surely.
Proof. The inequalities are clear when ( is such that V(I(:(() S 5. Now consider the case
V(I(: 1- By definition, conditioned this event, we have almost surely:
N Σ ((())) A g ( (S ( +)
That is, we increment the (h.(s.a) only when we encounter an element of the active set such that the entry for this user has not been observed before. Observe that for any arbitrary (s, a) A
P [ (U,, (s) + , (s. Hu
R (s, a) = =
(16)
N
This is true since the law of 5%. A/ is independent of U, (since all users share the same MDP), when conditioned on F,. Now, the algorithm only fills the column corresponding (s, a) until the number of entries is smaller than Np S N We conclude that:
Hu R (h, (s, = * N - NN 2
This allows us to conclude P R (U,, = =* (5% AA = (s. 2 1/B and hence:
EN, = Σ
EI (1) h
(h ( ( (U,, (5) ((11)) =))
h=1
EI((S (1) ( (/00)
h=1
(17)
h=1
In the last step we have used equation
15
The bound [N < H almost surely follows from defini-
tion. Now note that E. [ HE
N, F.).
Claim 6. For any E N and some co O small enough, have:
P Σ N₂ <
ET
< expp(coof
16
21

---

Under review as a conference paper at ICLR 2023
N2 [R]
Proof. For
3 I
A 0, consider M,
+
(E [N: - No). Now consider:
AH
r-1
E Exp
M,) = E (exp((M,-1)) exp
exp
Σ
M₁
t=0
1=
7-2
APE N?
= E (e NN Fr-1] - AN))) exp
Σ
Me
exp
AH
1=0
< Exxp
XPE[NN_112 1,,-11
XII
exp
Σ
Mr
exp
2
N? p-1
X11
[F,-11
1=0
3
= Eexp
Mc)
(18)
t=0
In the first step we have used the fact that Ei=0 M, is F measurable and the towering property of conditional expectation. In the third step, have used the exponential moment bound given in Exercise 2.8.5 in Vershynin (2018), applied to Nr - EE [N[N--1 along with the fact that Nr [0, !I] almost surely. From equation 18] we conclude that E exxp(2. M,) < and thus applying the Chernoff bound, we conclude that for any 3 >
XE N
IP
- (B[NIF] N³) > 81 S cxp(-AA3
Now, using item 2 from Claim
conclude that
P
Σ
<
N₂ <
3-4AH 3-AH 1=U
Σ E [M]FF]]
I cxp(-AA3)
Now, using item I from Claim we note that EE [M and B CyCT for some small enough constant conclude:
1 2 or almost surely. Setting À = 411
IP
Σ 1=
N
CT
I exp(-
16
Let term denote the termination time for the algorithm. This is since sp(t) increasing in t, (P() < SpH) and strict inequality holds when 1 < Teem, For every < pe we have (P()) Σl= N₂ NyH|S [.A]. Therefore, have the following relationship between the events:
teeemm > r) C Σ N₂ Np|ST|A[H
Setting 16Np|S||A H
we have:
Per SP Σ N < Np\S||A|H
<cxp(-cNp(S(A4)
D.2 PROOF OF LEMMA g
Proof. By Remark 4.3 in Wagenmaker et al. (0022), we show that non-line non-linear rewards can be handled by the reward free RL algorithm in Phase long all the reward are uniformly bounded in [0. 1).
22

---

Under review as a conference paper at ICLR 2023
Let By, be the matrix I + Ag in Algorithm2aat step t for horizon h. Similarly, let the corresponding projection Q be Qth- Recall that Qu is the projection onto an eigenspace of Bun- Now, suppose Sy: AuH ~ Mu, (TTQc.)) ) as in the algorithm. Let Φb == (Sh, A4). Now, if Qth. of 0, then:
t Bin Φeh 2 4 Qtn Bth ou
I
= o/ Qth + 11
Quneen
1Qu
(19)
1+ k²
In the first step, we have used the fact that Qrh. is the projector to the eigenspace of B In the second step, we have used the fact that over the eigenspace corresponding to Qth. the eigenvalues of Bih are at-least 1+x2- 12z We now invoke Assumption in order to show that, along with the
guarantees of reward free RL in phase we conclude that:
[1[Qnounl1110 # 0, Ben] 27 -
(20)
Now, note by the fact that Quh a projector and that |1 S 1, we have:
E Oul || Qua * 0, Ban] S 11 + 0, Be!
(21)
Recall the Paley-Zygmund inequality which states that for any positive random variable Z, we must 22 2 1 (BZ)
have:
PPZZ
R2
RZ Therefore,
P
Dth Bid Den >
7-E 2(1 + x2)
Qi + O, Ben 2 P [QQuomlll
7-6
Qth + O, Ben
2
2 P
1Queeell > _ [112ehee
11 11 # 0, Ben]
Qu & 0, Ben
E [1Qrashe
12 Qin + 0, Bra]
2 4 E []] Qen
2
E
[1Qutouul1 1ith * 0, Ben
1th 0, Bcn
4
- E
(22)
4
In the first step, we have used equation 19 In the second step. we have used equation 20 In the third step, we have used the Paley-Zygmund inequality and the moment bound in equation 21
Define the stopping time = inf(t S Quh = 0} and = oo if the set in the RHS empty. Let = for E (0) UUNN be a sequence of i.i.d random variables with the law 2(1-x2) consider the sequence of random variables E, oT, 1 for and E, = = for
7-c Ber (27)) ). We
Now, we apply the matrix determinant lemma which states that det(B + uuT) = det
(B) det(B)(
+
ut u)) We note that B(i-jj= Bah + dun Therefore, whenever т, must have:
(et(B det(Bin) (1++)
(23)
Since || || < 1 almost surely, must have
Tr(Bin) = Σ fer, Bines) < dd
It is easy show that for any PSD matrix, A, if (r(A) a, then dAt(A) (2)d (since trace is the sum of the eigenvalues and the determinant is the product). Combining the equations above, we conclude that whenever < r, must have:
t+1+d
(1++)
d
#=0
23

---

Under review as a conference paper at ICLR 2023
Therefore, the event
(T> T) S ((+
II (1+ (1+ s
(24)
Claim 7.
T
(r-e)
P
II + E²) 2
1+
7-C
exp xxp(-cu((-00)
2(1 + 122)
Let and T 2 C da? (5-1)²
log dx q-c-
we have:
P [[
(T)+ta)d 2 ex-expl (-coT(7 -e))
Proof. Let Nr be the number of variables (Ei) such that E
2
Then, it is clear that
(1+ 2 (1 +
7-6 Nr.
2x
Therefore,
(--07)
7-E
(7 E)T
P
(1 5.) 2
1+
2 P
NT 2
2(1 + x2)
8
0
(7 - c)T
2 P Bin 7-9 2
2 1 - exp ( 0o T(7 - ))
(25)
Here Bin refers to the law of a binomial random variable. The first step follows from the fact that (1==(1+ 2 (1 + 2[ NNr almost surely. The second step follows from equation 22 which shows that conditioned on Qrh, BAh, the random variable 1 (E, 2 2((+ stochastically dominates Ber(2 (2 The last step follows from an application of Bernstein's 's inequality for binomial random variables.
Now, using equation 24 along with Claim
we conclude:
T
P(T > S) T+i+d d 2 (1
<exp(-coT(>- - c))
6=0
D.3 PROOF OF LEMMA I
Proof. By the definition of Linear MDP, we must have S,+1|Skr A ~ EE (0(S,, A₂), e))((()))
and A4+1|Sh+ Th+1 (-)Sm) Therefore, for any bounded, measurable function S A + RR
we must have:
Eg(S Apt1) = E E [S(++ Ant1)|Shr Anl]
E
(0(Sn. es) (dth-
Σ Vile (an(ss)mtzaddls)g((..d
(26)
24

---

Under review as a conference paper at ICLR 2023
D.4 PROOF OF LEMMA
Proof. It is clear from the assumption that E [ʃ 9(0(6+1)) a) (daa))) Lizilone ei) If ( ())s.)))
Note that
Oht Ohe
The Go
Σ
Ohe Goh
Ohe G
1=1
= GG,h =V
(27)
6,
Therefore,
Σ Σ axon / puoo-n(ds)mmddaassls...
E
(w,ei) / Hita-n(ds)mmddaassgss.... T (28)
(g:
Note that, conditioned (oE) Obe, (($(1+1)e: a) a) (dal (()))() independent random variables bounded above by a.t B. Therefore, applying the Kauma-Hoeffohin inequality, we con- clude:
P ( ((: - 8 (oi)err)) s 2 exp (-2B2
2B E, at
Now, observe that E, Enoha E. + whenever Ga. & n²T This concludes the proof.
D.5 PROOF OF LEMMA IQ
Proof. Notice that:
E (II E (IT') E (II) Ey
ET (IT') (EE
E (TT')
ET (II) ET (II') + |||| - 11ll
| / d(S,,a)m (da (S)) EE d(S1, a (da|S:))| ||, + 11 1/1l1
< sup |ø(s, a)|l TV( m1) + || Mill S TV(T., T1) + ||p| rilli (s.0)
(29)
In the first. second and third steps we have used the triangle inequality. In the last step. we have used the fact that for any bounded function, and any probability measures (4, v, we have If (x)) [())v(dx) S sup, (V(,..
Now consider:
||TT (11,, 1; 1T -; 1
< - - =/)
< ||
(0, T3)11
(30)
25

---

Under review as a conference paper at ICLR 2023
Now, observe that:
U3-1, - T5( -3-1 7))l, - Σ (uy-1 (0-- -1.1_ / ((5,))))0--(()))(((a))))
d
10--1 - - = 1 +j-1ll= i=1
(31)
Where we recall sup.,A.= f (ss, uu (ds) (daas)) l| S as given in the definition of Linear MDP. Using the Hahn-Jordan decomposition of a signed measure, we conclude:
[7 1),1: nT) -T 1/:1:
1 at) /| - - TT (dals))
& m/) & Culls-
(32)
Combining equation
30 equation 31 and equation 32 conclude:
[T (b) 1, my) - myyl - 7 ( -/)1: r/|l1
- | 21 + Culley- TV - m/) + | - 1/j-1l1z
(33)
Combining equation 29 and equation
33 we conclude the first inequality in the statement of the
lemma.
With reasoning very similar to that in equation 29
we have:
| (II) - (1r) (1r)) S (V(m m1) + 1 - rilli
(34)
Using similar reasoning as in equation
33
(o. v,)
Vy |11 (T 1/1 -
r
T
< ||ا
1111 +
Σ
( v/ GG +
Σ
1 TG
1
TV(
m/)
(35)
Now note that for any v E Rd, we have:
Σ v G 1055-100-11 s
T Σ
VTG PTG
vTG
G-1
TuTG-1
/ 121l2
(36)
Here, in the first step we have used the fact that whenever & E RK we must have ||]||| S / k In the third step, we have used the fact that DTh - G by definition. In the last step, we have used the fact that G 2 1. Plugging this into equation 35 we conclude:
||]||
( 13 1yll (0, 1/2 TT) 1/111
< | - -1 + V - - 1 + V T VV (my, m/)
(37)
Using this and the definition of we conclude the second inequality in the statement of the lemma. equation 44 and equation 45 follow from similar reasoning.
26

---

Under review as a conference paper at ICLR 2023
D.6 PROOF OF LEMMA
Proof. First consider the case h 1. Let g(s.a) = 6(s,a). In this case, (1)))Ba(1) [
EXI(II) < [[To(g: m Tolo: a Ill-- By equation 29 and equation 34 we conclude that X - To(os mi) and - To(o: mI) are 1-Lipschitz with respect to TV() and -1.
I (T((: - To m1)l =
[[To(g: Tolg: mi)ll + 2n
sup
sup
I= y EQn
We apply Lemma co-ordinate wise to the co-ordinates of & and union bound over Qy. have:
sup
To(g; Tolg: x1) 2n + d8) S dd2//eexp'
x*x²
(38)
EQ
Now, consider h > 1. Consider any net over (a(1). denoted by Bd., with respect to the norm I
We can take Ba., exp(Cd log(d/n)) (Vershynin 2018). Invoking Lemma 10 we conclude:
sup sup 1. (II) Euh (II( ue (1)
sup
IF.I,
F(II, vI..... vh)
Pi (Ba( nEC
F(II, PI.... ph +2 1 + V n/
sup E Ea, N
(39)
Now, by the triangle inequality, have:
vn) (I,,u.......
F(II, mx)l
< (T))) - To(d), ml)l Σ
(40)
Therefore, by invoking Lemma along with union bound over every component in the sum in equa- tion 40 and over the net in equation 39 we conclude that:
P sup
FI MN) - v1, . (I..,,,. > 3dh
Ps Pl un B n
< 2dh Qu Ban.
exp( exp(-=*x
(41)
Combining equation 39 and equation we conclude the second item the statement of the lemma.
The concentration of X, and X2 follow in a similar fashion, but here we consider 1) net even over x and use the Lipschitzness results given in Lemma 10 the fact that x + f(6; x) is 1 Lipschitz.
E PROOF OF THEOREM 3
Lemma 9. Suppose h E [H 1], and g S x A + IR be such that (g(s, a)l S B for every (s, (s)
For any policy Ti and any v such that [|v||2 S 1, we must have:
P (T(g) To mx), (ona)EtTT Go.n h x²1) 2exp
82,2
215"
27

---

Under review as a conference paper at ICLR 2023
Lemma 10. Let II = (T11..... ................................ TH), II' ( Tn) be policies in Q Conditioned the event
Go.h = I,,, the following hold:
[F U1, ................................ Ph.,,
F(IT, 14,, 1/-11 1/2
Σ C T M/11, 21113 - 22111 + TV((11, a1) + 21111 2/1l1
(42)
[F(II M,..,, Mh- M1)
1/2 ,., 1/
h Σ
$ SVZ T R
Σ TV(T, 11s e/]ll2 TV((TT
||
191l,
(43)
j=1
Suppose E 8d-1
( ,/)1
- 2vā Ed) (122 - 1/11 + TV(TT =/) + || 2'11211/11))
(44)
())) - -Ta(s(;2'),) ,T)1 2 (va+ Ed) (1|v 1/112 + TV(TT, m/)) + || - r1|12||u112)
(45)
Condition the event Go. x²T for every h [H]. Fix some n > and let Qn denote any nent over Q With probability at-least 1 - 8/4, the following hold simultaneously:
Lemma 11.
1.
sup sup (II - BY (II) < C d NE
d|Qal
log
+ Cn.
2. For h > 1:
sup sup (II) - (XI) I DEQ
CdH
log
[
+ Hdlog (
4)+c(1
R² nn
3. X1 = supm (F JE inf
t. (f(:zx))
TI) - infzess-1 [T(((i)),,
Xi C(vd+Ed)
Grll Vlog
+ dlogg (
+ +Cn(Vd+ Ed)
4. X2, == sup =EB(I) (I=
inf Th (=: - - (f (;:
XA < C(vd+ + Ed)
( b + d dog ( + Cn(Va Ed) Cp V T
log
Lemma 12. == (T....., T.). For any n) 2 0, and [H]. suppose EY S 17. Then, we have:
[R An) - w/12 5n
Proof. Let S1.H, A1: Therefore we conclude the lemma for the case h 1. Now let 1.
M(II). By Lemma
conclude that: Eo(Si, A1) (T(é,
Now, note that for j 1, we have: Eo(S,, A,) T (()) TT). There exists sequence ,/...., 11-1 such that
EII Σ
23 S n0
j=2
28

---

Under review as a conference paper at ICLR 2023
Letting Ei (II) 1h, (0. =: f/,, we have from the case h 1: [|Eo(S1,
1/1 S 7/-
R ||
-
$ Bo -,00,))))-)-- (0.
$ | - -
(46)
We have used equation 31 in the last step. Continuing recursively, we conclude the result
Proof of Theorem 3 We condition on the event described in Lemma 11 We suppose that k. 17 and yo are related in the statement of the theorem. We will apply these values whenever we invoke the concentration bounds obtained from Lemma 11 in all the inequalities below. First consider = 1.
f.H. Let Ii..1 (T ..... "..,, By item 3 in Lemma 11 have (with X1 defined in the lemma):
inf -((())).((*))) 2 sup inf T(((ia),m) X1 126 - X1 y neQzesa
ZESa
Similarly, we have:
inf T((f(:z), xES
2 inf xf zES
Combining the two displays above, we conclude the theorem for h = 1. Now consider h > 1. We will first show that the constraint Eu,b-1(Il) (II)
is feasible for some II E Q and some v.
Note that, for any policy II there exists a 1/1,..., Vh-1 E R' such that EØ(S), Aj) = whenever SI.H. Anи ~ M(II). For the choice V = Ph-1, we must have gn (II) = O. Now, by item and 2 of Lemma 11 we conclude that Év.b-1 < 7/0 Therefore this optimization is feasible.
Consider the solutions to the optimization problem given by & and f. Note again from Lemma that (()AA) < ( + 1/0 < 27/0- Now, applying Lemma 12 we conclude that
whenever SI:H, AIE M(ffAi
[B An-1) i|l: S 27o0
By a similar reasoning as the case h 1, we conclude:
inf T, (.h)) 3
-
Now, applying equation we conclude:
inf (SSSh; Aniw) inf
(J Bo 1) mf
xE84-1
xE84-1
inf Ta (f(a)) i, T
(. sup
(f Ep( (S An (1. (x(a),)),, i, a h
#E84-1
sES
C 30 2C, + (d) (11 An- 22
(47)
In the last step, we have used the lipschitzness bound for Tn given in Lemma 10 We will show that the conditions given equation 2 are satisfied for (S,,,, A,,) with parameters C/2 instead Ç.
(1 An)ll2 < almost surely follows from the definition of vh Now, (S((S, An, x) 2 &
for every Sd-1 implies (I, (Sh, An)) 2 z/a Using the definition of f(S,. An, z) (see Section 5) and the fact that (f, 2), Z as established above, conclude that for every Sd- we also have:
dςL(a, (SA, 2n)) < VdEl (S An) S
< (z, (SA, AW) S vāvE(a, (Sh, A,))
(48)
In the second step, we have used Jensen's 's inequality. From this, we conclude E(x, (S,, An)) गez for every E S and thence (r,(S,, (Sn, As) 1 ZE2-
<
29

---

Under review as a conference paper at ICLR 2023
F PROOF OF THEOREM 4
Let the unknown row set in the iteration in the matrix estimation procedure of Section 6.1 be
denoted by 4-1. For the analysis, we will use the convention that L, -0 if the procedure terminates
before the t-th iteration. Suppose K, is such that for every t S log N, we have: K-14-11 Z
We will then show that the event {|T I I - log N) n {ô, - 0 Vi E 1og ) has probability at-least 1 - 8. To show this, it is sufficient to consider the step t = 1 with Io- [N], K K, ( V and show that with probability
ar 1ltdr log d + +C 5²
logg( lox
log N' I I 2. TO
and é, Ø for every E 18. The result then follows from union bound. We will therefore establish the following structural lemma and prove the Theorem 4 The rest of the section is then dedicated to proving Lemma 13
Cir+ de
Lemma 13. Suppose the distribution of disk satisfies equation 2
Let K 2 (32)
N
log d Let ce.
(T) denote the set of all matrices A with rank most 2r such that L(A, v = 0. Let 1z (2)
{i E [ Di + 0}. With probability 1 -xxppxe2' 2 ()) we must have:
V(V)(A: I2(A)
10 f = 0
Proof of Theorem Let ④ be the rank r matrix found satisfying L(O O", v(()) 0. By
Lemma 13 we have that Iz(@ 00) N with probability at-least 1 log (by setting K = Ki
as in the statement of Theorem 4p. By Lemma 14 the probability that there exists an i E [N] such
that + * O and Σ (o., )ue) 0 0 is at most [ exp( exp(-cc2ç2X)) S 8. N for some
large constant c. From this we conclude that + = θ for every i If.
Lemma 14. Fix any é. Suppose the distribution of (WW))E)N)) satisfies equation Then, there exists small enough constant such that:
KC
"
P
3i s.t.
Oi vin) 03x
< |4| ex2(
32d
Proof. Consider the Paley-Zygmund inequality, which states that for any positive random variable Z,
E EZ)
P 2ZZ EZ
4E
Suppose i E I and denote r; : θ 0 By the properties of tha we have that E[T vtx)) > <|IDa|l and EE (T,, 12 < ||,;1 va
g²d
Applying the Paley-Zygmund inequality to the random variable (TT, v. we conclude the result in equation 52
6²E²
PP
KWVE r
2
(49)
2vd
Let
Po
=
222
Let
N(T,, V.))
ΣK
(1ebb TW)l zVa
Clearly,
Ek
(0,, vix)
2
< r
NT,,, V.). Therefore, we have:
4d
P
( vtae)
-03e
Kete- 32d
< P [[T, M.) < KCE"
(iin(,, s Kpo
<
(50)
30

---

Under review as a conference paper at ICLR 2023
Here Bin K, Po) denotes the binomial random variable. In the second step have used the fact that ,T,,, W2) is a sum of K independent Bernoulli random variables with probability of being 1 for each of them being at-least Pu <²5² In the last step, have used Sanov's theorem for large deviations. In the last step we have used Bernstein's inequality for concentration of sums of Bernoulli random variables (see [Boucheron et al. (2013)). The statement of the result then follows from a union bound argument over E.
F.1 PROOF OF LEMMA 13
Suppose I * 0, I S [N] be any fixed subset. By M(N, d, 1r)r, we denote the set of all N x d matrices with rank at-most 2r such that || > 0 for all E T. By BiN, d. I, 1,2r) we denote the set of all N d matrices with rank at-most 2r such that ||T whenever i
Lemma 15. Suppose d.I..) L(T, W MMN,d, 1,2r)
Then, I(A,W) 0 for every A
Proof. For every A M(N, 2, we construct I' such that:
A A
whenever T
(51)
otherwise
Now, by hypothesis, L(T, V > 0. This implies, there exists an i E / and k E K such that Kyae, Pa)l > O. This implies Ky/an, Ar) and thence we conclude that L(A, v) 0.
Lemma 16. Suppose I is such that ||T+l| for every E I. Suppose the distribution of (WW))E[N),EE(K) satisfy equation Then, there exists a small enough constant such that:
P (MTT,V
u 32Nd
S 3xp==Keep(-<<33
Proof. Consider the 2,
inequality, which states that for any positive random variable
(EZ)2
P P(Z 2 EZ
4E
Suppose i E I. By the properties of dia we have that [E| (T,, vuael 2 Va and (T, wn)) सेे
Applying the Paley-Zygmund inequality to the random variable dxa)), we conclude the result in equation 52
C
P KelSk D
(52)
2vd
Let Po = S2e2
Let N(T, v) Eier Eki 1 (160iss
2 Clearly, L(I, v) >
1dNK (T, V) almost surely. Therefore, we have:
P (L((T,))
( 32Nv/
< [(T,, T) < 111K505)
<P Bin([ po) < 11Kpp
< exp(-cpol [|])
(53)
Here Sin([7]K,,p) Po) denotes the binomial random variable. In the second step we have used the fact that (I, 1) is a sum of [ independent Bernoulli random variables with probability of being 1 for each of them being at-least Pu <²s² In the last step, have used Sanov's theorem for large deviations. the last step we have used Bernstein's incquality for concentration of sums of Bernoulli random variables (see Boucheron al. (2013)
31

---

Under review as a conference paper at ICLR 2023
Lemma 17. Suppose the distribution of ((M satisfy equation Cr(N+d)
Let [1]
N
There
10-
exist positive constants co. C, C such that whenever KN 2 C
log
we have:
CE'
inf V) < co + 2 (exp(- (EB(N,
Proof. It is sufficient to prove this result for I' E Bo d, 1r) S B(N, d, 1, 2r). which is the set of all matrices such that ||Till for every E and otherwise. Define [F]
N Σ ||T Suppose I E Bo,N, T, 2r) such that || 11,,22 < 9). Then,
N
N
L(T,V) NK
Σ
(T. 2
N
2 NK i=1
Σ
KT&, 3/x)) 21(TT - -,, Mll vaa)
(54)
L(C, v)
11. L(T, ạ) 2m
(55)
In the third step, we have used the fact that l/ ll s and the Cauchy-Schwarr inequality to imply KT, - Da vrxa)l S [[;; Till. Therefore, given any 17 net of Bo(N, d, 2r), denoted by Bo.., we
must have:
L(T, V/) 2 inf (e..
inf
L(T, v) 21
(56)
rEB.
We will now parametrize Bo(N, d, 2r) as follows:
Claim 8. Every I' E Bo(N, d, 2r) can be written as
Ete uaeu ifi E
T
(57)
0 otherwise
Where .1,..., U2r are orthonormal vectors in Rd and u; = E B2rr are such that [|ue]] = 1.
Proof. By the singular value decomposition, have: I WEVT for orthogonal matrices W, V and the singular value matrix Σ. Therefore, Fi Σr Wiyykuy Denoting u4k. := Wiakk note that r, = Σ Uk where U/ is the k-th column of V.
Now, it remains to show that ||u|l || 1. By normmato of ui...., U2r and the definition of I, have: ||
2r k= |usx 12- ||u
Therefore, we construct an nenet for (N,, d, 1,2r) as follows: consider any n/2-nnt over the sphere 12r-1, denoted by Sy (2r) with respect to the Euclidean norm. Similarly, consider any " net over the sphere sá-1, denoted by S (d). We draw (us)sess (r*)RE(pr) from the set 2/2r
2
Hi Sy (2r) [[be(2))
$ n (d) and take Bo.n to be the set of all fu,, v) of the form given in 2/2r
Claim
g
Claim 9. Bo,n is an n net for (N d 1,2r) with respect to the norm 11..2.
BBonl s exp 2dr log( Av2r +1) + +))
Proof of Claim 9 By construction, there exists Int E Bo., such that:
T BB,(N,d,1,2 Let (u,), (2k) be such that: Claim r; Σer Uhi Uk-
32

---

Under review as a conference paper at ICLR 2023
2r f;
dik Dk
with |/, 2ig1l - 2 and
110g
rill S
for every i E I and & E [2r].
2v
In order to show that
|
-f1l1,2, I 17, it is sufficient to show that [],; F'll s 17 for every i E [7].
2r ||r; r
2r
Uisk
Mikh Jon
+
Made (vx
0x)
A=1
k=1
Üisk
)ox/
Us (o% -txi1l
k=1
2r
2r
2r
(uik
Uzk)
Σ
Usk (0x - @b)]l -
+11 D
Uik (uk - 0x)
2
k=1
k=1
2r
2r
"
+
0x S
(58)
2
Therefore Bu,n is 17 net with respect to ||
1112,--- By Corollary 4.2.13 in Vershynin 2018
can pick: $ 5n (d) & (4v2r + 1)d and Sn (2r) s ( + 1)2r and conclude the bound on the
2/2r
2
cardinality of Bo.y"
By Lemma 16 a union bound,
5
P inf fe
L(F, 1))
< |Bonnl exp exp((=<2<11111
32Nd
S exp (2dr log( 1v2r + 1) + 2 log( 1) -
(59)
Therefore, whenever taking |/|
N 10
and St &
for some constant e₁ small enough, and
C(r+
combining equation 59 with equation large enough constant C, we have:
55 we conclude that whenever K
log for C2
inf L(T,V) V) < cn $ Sexp(-c(((NNK) (N.....
P
10 The number of such sets 7 at-most exp(e1 N) for some constant Ci 0. Therefore, applying Lemma 17 along with the union bound over all / such that |/| 2 TU we have: Corollary 1. Under the conditions of Lemma 17 we have:
Now, consider [7] 2
inf inf LTT,V) > 5222 ICN TeB(N.d,1.2.)
11 T0
with probability at-least 1 -xp(-o(({2NK)
33

---

Under review as a conference paper at ICLR 2023
We ready to prove Lemma 13
Proof of Lemmal 13
Combining Lemma 15 and Corollary
we conclude that with probability at-
least 1 exp( of (K).
) U ,,,, 0
ICIN M1 10
Note that if A E V(D) such that [1)( > N implies A E MMN, d, 1,2r) for some [4] > This allows to conclude the statement of the lemma.
N
13
34


Reviews:
[{"review_id": "woFqdu4LkqO", "reviewer": "Reviewer_d781", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 problem of multi-agent reinforcement learning under the structure of low-rank rewards. Specifically, multiple agents share the same transition distributions while having different rewards, which are assumed to be represented by a low-rank matrix. Both tabular and linear MDPs are investigated. \n\nThe main idea is first to use reward-free algorithms to estimate transition structure (which is the same across different agents); then input designed rewards to the reward-free output to obtain exploration policies that only interest in collecting rewards (which are constructed to have reward samples satisfying specific properties); at last, use low-rank matrix estimation techniques to obtain the reward matrices for all agents from the samples in the second step. \n\nThe main technical difficulties are in how to obtain proper reward samples and how to use these samples. For tabular MDP, the idea is to encourage explorations of important states (determined by the reward-free outputs) and use existing techniques to perform the matrix estimation. The design in linear MDP is more challenging (thus more complicated) where the authors propose a newly crafted matrix estimation algorithm and carefully design the sampling strategy in MDP to meet the required sample properties. \n\nWith the above techniques, sample complexity analyses are performed on both tabular and linear MDP settings. Compared with learning individually, the designs are shown to be effective in leveraging the low-rank structure to decrease the sample complexity.", "summary_of_the_review": "This work studies the problem of multi-agent RL, especially under the structure of low-rank rewards. Techniques are required from both RL and matrix analysis. On the RL side, for the shared transitions, reward-free explorations are first adopted, and later sample strategies are carefully constructed to obtain samples with certain properties. On the matrix analysis side, sampling requirements are first identified for the RL part and with these properties, existing techniques are adopted for the tabular setting while a new estimation technique is proposed for the linear setting. The combination of these techniques leads to performance improvements which are demonstrated theoretically. However, the presentation does not make me satisfied and I believe also does not fully demonstrate the techniques/results in this work as many key illustrations are missing, which leads to my recommendation.", "strength_and_weaknesses": "Strength:\n+ The consideration of low-rank structure is reasonable and I believe is an important direction to be explored in RL, especially to break the curse of multi-agent;\n+ This work nicely adopts existing techniques in reward-free explorations and matrix estimations, while also bringing new developments, especially in sampling strategies to guarantee specific sample properties and an extended matrix completion technique. The combination is inspiring;\n+ I am not very familiar with matrix completion, but the proposed techniques (i.e., how to maintain the isotropic property in samples and how to perform matrix estimation with row-wise linear measurements) may be of independent merits.\n\nWeakness:\nI am overall satisfied with the technical side of this work. However, I found the presentation not very clear. One potential reason may be that I am more from an RL background instead of matrices analysis. However, I believe it is still important to illustrate key intuitions clearly. Especially, many interesting designs are left unexplained (some even not mentioned explicitly). \n- For example, in the tabular setting, Algorithm 2 is designed to stop when rewards of important states are sufficiently collected, while the importance of states is measured by (in some sense) their \"achievability\" characterized by the value obtained from reward-free outputs. I believe this part is important; however, it is not mentioned in Sec. 3.1, instead in the analysis (i.e., beneath Assumption (Tab) 2), a connection between incoherence and the redundant states is discussed. \n- Similarly, for linear MDP, no verbal explanation other than the algorithm box (Alg. 2) illustrates how to perform Step 1 in Phase 2, which essentially designs rewards in unexplored directions for the reward-free outputs to explore more.\n- Also, the theoretical analysis part lacks certain illustrations. The two parts of Theorem 1 comes from reward-free exploration and reward query, respectively, while the choice of parameter p is also not intuitive (which seems to directly contribute to the second term). A similar illustration is also missing for linear MDP, as it is not explicitly mentioned the meaning of the three parts in the sample complexity.\n\nOther than the above concerns on clarity, I also have certain confusion about the intuition and statement of the results. Hopefully, the authors can help me clarify these questions:\n- Typically in RL studies, the main difficulty is to learn the transitions (thus many works even assume the rewards are known). However, in this work, the difficulty is in learning the rewards, as there are N agents with N different reward dynamics. Thus, for the results, the authors emphasize the regime of large N, which makes the cost for reward learning dominate. Then, the benefit seems to come from the shared transitions, as it does not depend on the identity of the agent. I am just wondering whether this is suitable/fair to compare with letting each agent learn individually and whether this is any more suitable baseline.\n- It is a bit hard for me to interpret the results in Theorems 1 and 2. Especially, in Theorem 1, when the first term has a stronger dependency on epsilon; however the authors emphasize the dependency on the second term. For example, when epsilon = 1/N, the first term is dominating. For Theorem 2, it is even more complicated with more parameters involved. Hopefully, the authors can provide a more formal and detailed discussion of the results.\n- I believe there should be works in matrix analysis handling noisy observations, and thus I am wondering whether this work can accommodate noisy rewards. If not, hopefully, the authors can illustrate the difficulties.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "n1oStI11R2", "reviewer": "Reviewer_r7Gm", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 focuses on multi-user reinforcement learning with low-rank rewards. This paper considers the problem where all the users play in the MDPs with the same dynamics but different reward functions. Exploiting the low-rank property of the reward matrix, the authors design two novel sampling algorithms for tabular and linear MDPs respectively. Combined with the designed matrix completion algorithm with row-wise linear measurements, the sampling algorithms are shown to enjoy low sample complexities.", "summary_of_the_review": "In summary, this paper presents interesting results on the collaborative multi-user reinforcement learning problem. Novel sampling algorithms are designed, and the improved sample complexities are derived. However, the presentation of the paper needs more improvements, and some technical issues remain to be solved.", "strength_and_weaknesses": "Strength:\n\nThis paper designs novel efficient algorithms for collaborative multi-user reinforcement learning with low-rank reward matrices. The improvements in sample complexities from $O(N|S| |A|)$ to $O(N+|S| |A|)$ and from $O(Nd^{2})$ to $O(N+d)$ are very interesting and important for the research in this field.\n\nWeaknesses:\n\nTechnical issues:\n1. Since the authors adopt the big O notation like $O(N+|S| |A|)$ in the paper, I assume that this paper concerns the regime where $N$ and $|S| |A|$ both increase to infinity. The authors need to clarify whether they allow $r$ also increases according to Assumption 1. If so, then the exponential improvement claimed in Remark 1 is suspectable, since $r$ can also scale linearly in  $|S| |A|$. If not, such exponential improvement is unfair, since Dann and Brunskill 2015 does not impose such strong low-rank assumption. A minor typo is that $O(N+|S| |A|)$ is not fully correct, and it should be $\\tilde{O}(N+|S| |A|)$ according to Theorem 1. \n\n2. In the proof of Theorem 1, the value of $p$ needs more clarification. Lemmas 5 and 7 require the condition that $p<1/2$, which is not a trivial condition according to the presented proof. Concretely, in the proof of Theorem 1, it is required that $m\\leq Np|\\mathcal{G}_{h}^{c}/2|$, i.e., p\\geq 2/(N|\\mathcal{G}_{h}^{c}/2|) C_{1}\\max(\\mu_{1}^{2},\\mu_{0})r(N+|\\mathcal{G}_{h}^{c}/2|)\\log^{2}|\\mathcal{G}_{h}^{c}/2|\\logH\\delta. You need more assumptions on $r$ or $\\mu_{1},\\mu_{0}$ even to guarantee that $p\\leq 1$. In such case, you can not let $C_{1}$ small enough, since it requires that $C_{1}$ is large enough in your proof.\n\n3. For the proof of Theorem 3, could the author explain how to prove the first inequality in (48)? It seems not a trivial claim.\n\n\nWriting issues:\n\n1. The writing of the proof contains some vague words, and it is very hard to understand. For example, claim 3 needs the definition of the so-called 'correct marginal distribution'. I guess 'correct' means that they have the same distributions as original $J_{h}$ and $I_{h}$.\n\n2. Please arrange the Appendix such that the statements of the proposition/lemma are before the proof of them. Otherwise, it is quite confusing with reading your deferred proofs part without the statement of what to prove.\n\n3. The writing of the main paper is poor. There are a lot of typos, e.g. it should be 'smaller than the number of' in the first paragraph of the introduction. Also, please first state the equation/theorem and then refer to it, e.g. on the top of page 9, the reference to equation 2 is confusing.\n\nI will be very happy to increase my scores if the authors resolve my technical concerns.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "hJ-tFgMRKN_", "reviewer": "Reviewer_HAK3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "In this work, the authors studied the problem of multi-user collaborative reinforcement learning under the assumption that the reward matrix is low-rank. They proposed a sample-efficient algorithm for tabular MDPs and linear MDPs by exploiting the low-rank structure to incorporate the techniques from matrix completion. In particular, they showed that the total sample complexity for every user scales as $O(N+|\\mathcal{S}||\\mathcal{A}|)$ instead of  $O(N|\\mathcal{S}||\\mathcal{A}|)$ in tabular MDPs and $O(N+d)$ instead of $O(Nd^2)$ in linear MDPs. This is a significant improvement. ", "summary_of_the_review": "\nAt first, I have to claim that I am not an expert on reinforcement learning and I don’t know the related latest results. According to my understanding of this paper and the cited papers, the authors applied the techniques from matrix completion to the multi-user reinforcement learning problem. The theoretical contributions of this work are rather solid and strong. However, the discussions of the assumptions and theoretical results compared to the existing results are missing. Then, the readers don’t well understand the significance of these results.\n\n\n\n$\\textbf{Typo}$: (1) In Algorithm 1, “compete” should be “complete”. \n(2) In Theorem 2, “Assumption” should be “Assumptions”. \n", "strength_and_weaknesses": "$\\textbf{Strength}$: (1) In this work, the authors incorporated the low-rank structure into the algorithm design and sample complexity analysis of the multi-user reinforcement learning. It is interesting to see a significant improvement in sample complexity by fully exploiting the low-rank structure in the reward matrix. This could motivate researchers by incorporating other structures into reinforcement learning. \n\n(2)  Generally, the paper is well-presented and easy to read. The main contributions are stated clearly.\n\n$\\textbf{Weaknesses}$: (1) There are many low-rank examples in collaborative filtering literature. However, it is rare to see examples of the low-rank reward matrix in reinforcement learning. It would be more convincing if the authors could provide some examples with explanations on the assumption that the reward matrix is low-rank in reinforcement learning. This is very important in clarifying the significance of this work.\n\n(2)  The notation is a little confusing in this paper. For example, what is the definition of $\\Delta$ in $\\Delta(A)$?  What is $da$ in $\\pi_h(da|s)$ on Page 3? \n\n(3) Some assumptions in the paper are not well presented and motivated. For example, Are there any interpretations of Assumption (Lin) 4? \n\n(4) It would be good if the authors could provide some instances of random vectors that satisfy the requirement in Eq. (2). \n\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "epFTgivqdw", "reviewer": "Reviewer_XKWe", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper focus on collaborative multi-agent RL. In this setting, all agents share the same state-action space and transition probabilities but may have with different rewards. In this setting, they introduce an assumption inspired from collaborative filtering, that the reward matrix of the N users have low rank. Given this assumption, they provide algorithms for efficient learning in two settings: tabular MDPs\nand linear MDPs. When the number of agents N is large and the rank is constant, the sample complexity per MDP depends logarithmically over the size of the state-space, which is exponentially better than the naive approach.", "summary_of_the_review": "An interesting theoretical paper on multi-agent RL. The practical applications of the proposed scheme are less clear.", "strength_and_weaknesses": "Strengths\n1) The paper is generally well written.\n1) The paper examines an interesting setting based on reasonable assumptions that may emerge in real applications.\n2) The paper combines a lot of ideas from various lines of literature (e.g., MDPs, low rank matrix completion, multi-agent mean-field RL). \n\n\nWeaknesses\n1) The results do not seem particularly surprising given the prior work.\n2) Although the authors try to incentivise the model via real world applications no effort is put into testing these ideas on an actual benchmark. \n\n\n\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "_dEQ3nL2_TD", "reviewer": "Reviewer_iGHL", "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": "The paper considers the offline RL setting under N user-specific MDPs. The author addresses the sample efficiency and the exploration of collaborative reward function. The solution assumes a low-rank structure between user reward functions and use the idea of collaborative filtering to reduce the required number of samples for each user MDP.\n\nA special problem definition:\n* Same state/action space and transition function across users;\n* Personalized reward function, assumed to be low-rank;\n* Goal: learn optimal policies for N user-specific MDPs\n* Goal2: improve sample efficiency. \n\nThe main intuition:\nWhen multiple user MDPs are collaboratively learned, the low-rank nature can derive a solution that can collaborate the learnings of MDPs and reduce the number of sample required for each user MDP.\n\nProposed algorithm:\n1. Reward free exploration: uniformly pick user MDP for a given trajectory and generate optimal policy function \\Pi(R) and its estimator V(\\Pi(R)).\n2. Query the reward matrix: use these functions to sample and collect user-wise rewards of state-action pairs or sample linear measurements\n3. Complete or estimate the reward matrix: recover the full matrix from the sampled records for each user; \n4. Computing optimal policy: find the optimal policy on the full matrix.\n\nContribution:\n* An RL algorithm with a proven sample efficiency boost.\n* An algorithm for efficient matrix completion for tabular MDP.\n* An algorithm for efficient policy sampling and estimation that satisfies given statistics.\n", "summary_of_the_review": "Overall, the paper is interesting and novel. It is important to leverage the low-rank property of reward function in RL. But the clarity is low and there is no experimental result. ", "strength_and_weaknesses": "Strength:\n\n1.The motivation of this paper is very interesting. The low-rank assumption is very common in recommendation settings.\n\n2.The theoretical result is sound and impressive.\n\nWeakness:\n\n1.The paper is not quite easy to follow. It is hard for people who are not familiar with reward free RL to get the main idea of the method.\n\n2.The paper makes the low-rank assumption, but they do not justify whether it is reasonable.\n\n3.The paper does not discuss it's limitation and conclude the paper.\n\n4.It would be better to have a experiment to validate the effectiveness over baselines, even in a tabular game.\n\n5.The collaborative MDP problem setting in the paper restrict the transition functions to be the same across MDPs, so it is equivalent to stating a single MDP with personalized reward function. The paper would have greater impact if it considers a more realistic setting where user transitions are non-deterministic and personalized as well.\n\n\nMinor issues:\n* Introduction, first paragraph, \"is smaller the number\" --> \"is smaller than the number\";\n* \n* Since you are borrowing the insight of collaborative filtering, in the motivating example, better briefly introduce the insight of your method. For example, stating that you can borrow the \"exploration of similar users and assume that similar users generate similar responses.\"\n* Problem setting, 2nd paragraph, \"A_h = \\pi_h(S_h)\" --> \"A_h \\sim \\pi_h(S_h)\"\n* Problem setting, \"linear MDP setting\" section, better state that \\phi represents transition embedding and \\psi represents reward embedding when first introduced. \n* Section 3.2, Phase 2 step 1, \"query obtain samples\" --> \"query/obtain samples\"?\n* An inconsistent notation: in problem setting you use e_i for different embedding dimensions, but in section 6 you state that i represents a user.\n\n\nQuestions to authors:\n* Main points mentioned in weakness;\n* Do you have explanation on why linear MDP has total complexity O(N+d)?\n* Should it be G_h in the last two lines of Algorithm 1 instead of G?", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject