Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
Authors: Ayush Sekhari
Christoph Dann
Mehryar Mohri
Yishay Mansour
Karthik Sridharan
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Sample complexity
Agnostic learning
low rank MDP
RL theory

Abstract: There have been many recent advances on provably efficient Reinforcement Learning (RL) in problems with rich observation spaces. However, all these works share a strong realizability assumption about the optimal value function of the true MDP. Such realizability assumptions are often too strong to hold in practice. In this work, we consider the more realistic setting of agnostic RL with rich observation spaces and a fixed class of policies $\Pi$ that may not contain any near-optimal policy. We provide an algorithm for this setting whose error is bounded in terms of the rank $d$ of the underlying MDP.  Specifically, our algorithm enjoys a sample complexity bound of $\widetilde{O}\left((H^{4d} K^{3d} \log |\Pi|)/\epsilon^2\right)$ where $H$ is the length of episodes, $K$ is the number of actions and $\epsilon>0$ is the desired sub-optimality.  We also provide a nearly matching lower bound for this agnostic setting that shows that the exponential dependence on rank is unavoidable, without further assumptions. 

Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
Christoph Dann Google Research
Yishay Mansour
Mehryar Mohri
Google Research & Tel Aviv University mansour.. wwwhyyyggssaaa.a........mmmmmm.m com
Google & Courant Institute mohri@google. com
cdann@cdann.ne net
Ayush Sekhari
Karthik Sridharan Cornell University ks999@corne11.c edu
Cornell University as36630corme11.c edu
Abstract
There have been many recent advances on provably efficient Reinforcement Learning (RL) in problems with rich observation spaces. However, all these works share strong realizability assumption about the optimal value function of the true MDP. Such realizability assumptions are often too strong to hold in practice. In this work, we consider the more realistic setting servation spaces and a fixed class of policies II that may not contain any near- optimal policy. We provide an algorithm for this setting whose error is bounded in terms of the rank d of the underlying MDP. Specifically, our algorithm enjoys a sample complexity bound of Ô (H 3d log [T]))=²) where H is the length of episodes, K the number of actions and ε > is the desired sub-optimality. We also provide nearly matching lower bound for this agnostic setting that shows that the exponential dependence on rank is unavoidable, without further assump- tions.
agnostic RL with rich ob-
Introduction
Reinforcement Learning (RL) has achieved several remarkable empirical successes in the last decade, which include playing Atari 2600 video games at superhuman levels [Mnih et al., 2015], AlphaGo or AlphaGo Zero surpassing champions in Go [Silver al., 2018], AlphaStar's victory over top-ranked professional players in StarCraft [Vinyals et al., 2019], practical self-driving cars. These applications correspond the setting of rich observations, where the state space very large and where observations may be images, text audio data. In contrast, most provably efficient RI. algorithms are still limited to the classical tabular setting where the state space small [Kearns and Singh, 2002, Brafman and Tennenholtz, 2002, Azar et al., 2017, Dann et al., 2019] and do not scale to the rich observation setting.
To derive guarantees for large state spaces, much of the existing work in RL theory relies on realizability and a low-rank assumption [Krishnamurthy et al., 2016, Jiang al., 2017, Dann al., 2018, Du et al., 2019a, Misra et al., 2020, Agarwal et al., 2020a]. Different notions of rank have been adopted in the literature, including that of low-rank transition matrix [Jin and Luo, 2019], a low Bellman rank [Jiang et al., 2017], Wittness rank [Sun et al., 2019], Fluder dimension [Osband and Van Roy, 2014], Bellman-Fllue These studies also show that learning without any such structural assumptions requires a sample size that grows exponentially in the time horizon of the MDP [Dann and Brunskill, 2015, Krishnamurthy et al., 2016, Du et al., 2019b]. The choice of the most suitable and most general notion of rank is the topic of much active research in RL theory.
dimension [Jin al., 2021], or bilinear classes [Du et al., 2021].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In comparison, the realizability assumption has received much less attention. This is the strong premise that the optimal value function belongs to the class of functions considered. which typically does not hold in practice. In many applications, the optimal value function Q* is highly complex and we cannot hope to accurately approximate it in the absence of some strong domain knowledge. Can we relax the realizability assumption in RL?
Value-function realizability can be viewed as the analogue of the PAC-realizability assumption in classical statistical learning theory. That assumption rarely holds, which has motivated the de- velopment and analysis of numerous algorithms for the agnostic PAC learnability model. Those algorithms provably learn to predict as well as the best predictor in the given function class, in- dependently of whether the Bayes predictor belongs to the class. The counterparts of such results in reinforcement learning are mostly unavailable, which prompts the following question: Can we derive a theory of agnostic reinforcement learning?
Here, we precisely initiate that study. In this agnostic setting, we adopt common structural assump- tions, e.g. small rank of the transition matrix, but seek to learn to perform as well as the best policy in the given policy class, independently of how close this class represents the Bellman-optimal pol- icy. Specifically. we study agnostic Reinforcement Learning (RL) with fixed policy class II in the episodic MDPs with rich observations. Provably sample-efficient algorithms for agnostic RL would be highly desirable but it is still unknown what degree learning possible in this setting. Our work provides new insights about learnability with structural assumptions in the absence of (approximate) realizability in RL.
Agnostic RL. without any additional structural assumptions has been considered in the past. By evaluating each policy in the class individually, one can easily obtain sample complexity upper bound of O(III)=²)) Kearns et al. [2000] also showed that an upper bound of (K H log /s is possible, where K is the number of actions and H is the time horizon. However, as discussed in prior work such as |Krishnamurthy et al., 2016]. bounds of this form are rather unsatisfactory as one of them admits a linear dependence on the size of the function class, which is prohibitively large, and the other one admits an exponential dependence on the length of the episodes H, which is typically long. Using existing constructions, one can derive lower bound on the sample complexity of the form min [I] Kn "/=² in the rich observation setting. This further justifies our adoption of rank as a natural structural assumption.
Our Contributions: The following highlights our main technical contributions, where d is the rank of the state transition matrix induced by any policy the class II, and is assumed to be small.
We provide a uniform exploration based algorithm that can find an e-sub-optimal policy w.r.t the policy class II after collecting ((HK//d) log(d][T))/=) samples in the MDP. This bound shows that one achieve sample complexity that is polynomial in both H and log [II], while being exponential in rank d only (which we assume is small).
In addition to the sample complexity bound obtained here, the algorithmic techniques itself might be of independent interest and useful beyond this work. The algorithm is based on showing that for every policy, the expected rewards follows an autoregressive model of degree d. Thus obtaining samples of Odd-length paths for policy we show that one can extrapolate expected rewards for the entire episode.
We complement this upper bound with a sample complexity lower bound of Q (((H/d)4/2 2/2 /=²) (when K = 2). thereby showing that the HO(d) term in the upper bound is unavoidable. The lower bound also highlights which structures in the policy class induce the HO(d) terms thus shedding light on what structural assumptions could help alleviate the exponential dependence the rank.
Finally, we seek to improve upon the Hd term and provide an adaptive algorithm that admits sample complexity that depends on the eigenspectrum of the transition matrix of the MDP; while in the worst case that bound matches the above one, provides a significantly better guarantee when the eigenspectrum is more favorable.
However, we view the main benefit of our work to be the initiation of the study of agnostic rein- forcement learning and the presentation of an in-depth analysis of a natural structural assumption within that setting. This can form the basis for future research in this domain with alternative and perhaps more favorable rank-type assumptions.
2

---

2 Problem Setup
We consider an episodic Markov decision process with episode length H E N, observation space X' and action space A := fI...., K}. For ease of exposition, we assume that the observa- tion space X' is finite (albeit extremely large), but our results can be readily extended to count- ably infinite and possibly uncountably infinite observation spaces. Each episode is sequence ((Ti,a1,T) ri); (22, 02. r2),.... (HH aH, rH)) (X' A x IR) where the initial observation zo is drawn from the initial distribution μio E (2)), the actions are generated by the learning agent and all the following observations are sampled from the transition kernel Th+1 ~ T(- og) E A(X) that depends on the previous observation and action. Finally, the rewards Th drawn from sub- Gaussian distribution with mean r r(z,, an)) where r: X x A + [o, 1]. The learning agent does not know the transition kernel T, the initial distribution (An, or the reward function
In our setting, the agent given a policy class II S (X Hy ((A)) consisting of policies that map observations to distributions over the actions A. For any policy E II, we denote by T E xxxx the transition matrix induced by π,, i.e., for any x, x' E X
[T (a' = BawT(z) T(x' |x,a).
Assumption (Low-rank transition). There exists E N such that rank( S d for all a E II.
For the main part of the paper, we assume that the learner knows the value of d, but later extend our results to the case where d is unknown. We define X = "f.....,Ay E Cd to denote the eigenvalues of the transition matrix T with rank at most d. Without any loss of generality, assume that |Aq Z A 2... 2 l.
We denote by lx the distribution over episodes when following policy л and by E" its expectation. We call the expected rewards obtained at time h by policy æ expected policy rewards:
R E" (r(nn, an)].
The value function of x at time is given by (x) = E Σn r(ww, axe) xw = x Further, when using 4 without time index and arguments, we mean the value or expected H H-step return:
11
H1 Σ R%
Σ (r( an)]
v (zo)) E
Aml
the value function averaged over initial observations.
Learning objective. The goal of the learner is to return policy म. after interacting with the MDP for n episodes length H. such that the value of the returned policy is as close as possible to the value of the best policy in II, that is,
V
max V E,
TEll
where the error e is a small as possible and may depend on n, the policy class IT and the MDP.
3 Related work
We give a brief overview of the most closely related works here, and defer a more detailed discussion to Appendix A.
Recently there has been great interest designing RL algorithms with general function approxima- tion [Jiang et al., 2017, Dann et al., 2018, Sun et al., 2019, Du et al., 2019a, Wang et al., 2020, Du al., 2021]. particular, Jiang al. [2017] introduced the notion of Bellman rank, measure of complexity that depends on the underlying environment and the value function class F, and provide statistically efficient algorithms for learning problems for which Bellman rank is bounded. This was later extended to model-based based algorithms by Sun et al. [2019]. While these algorithms work across a variety of problem settings, their sample complexity scales with log([Fl). Furthermore, these al- gorithms also require the optimal value function f to be realized in F. In our work, we do not
3

---

assume that the learner has access to value function class F. In fact, given a value function class F. we can construct the policy class II, that corresponds to greedy policies induced by the class F. However, given just policy class IT, one cannot construct value function class, without additional knowledge of the underlying dynamics.
Our Assumption I implies that for any policy π E 11, the transition dynamics exhibits a low-rank decomposition with dimension that is T (x'1(²) feature maps o², vb X' +-R* R Low rank MDPs and linear transition models have recently gained a lot of attention in the RL literature [Yang and Wang. 2020, Jin et al., 2020, Modi et al., 2020, Wang al., 20] The works most closely related our setup are those of Jin et al. [2020] and Yang and Wang [2020], who give algorithms to find an optimal policy in low rank MDPs with known feature maps Φb. Similarly, the other algorithms also assume that the learner either observes the feature ((x), or the feature (x)). Agarwal et al. [2020a] and Modi et al. [2021] learn under weaker assumptions and only assume that the learner has access to a function class that realizes Φ. However, in our setup, the learner neither observes the features ,²,1/" nor has access to realizable function class for them, and thus these methods are not applicable.
(0)( +0 (x')), for some d-dimensional
Several of the works mentioned above recogmize the issue of a strict realizability assumption and provide results only when the function class contains good approximation to the optimal value function of model. However, the goal in our agnostic setting is more ambitious. We would like to find a policy that can compete with the best policy in the given class II, independent of how close the best return in the class max V is to the return of the optimal policy V= for that MDP.
There have also been several approaches for provably efficient RL with non-parametric function classes [Yang et al., 2020, Long et al.. 2021, Shah et al., 2020]. However, these approaches still aim to learn the optimal value function and their regret necessarily scales with the complexity of the optimal value function in the RKHS which can be very high. Instead, in our agnostic setting we would like to be able to quickly identify the best policy from the given policy class with low complexity containing good but not necessarily optimal policy. Finally, there are few prior works in agnostic RL that directly compete against a policy class [Abbasi-Yadkori et al., 2013, Azar et al., 2013]. However, they either make strong assumptions on the feedback model, e.g. Abbasi- Yadkori et al. [2013] assumes that the the agent fully observed the current transition kernel and reward instead of just sample from it, or the provided bound [Azar et al., 2013] scales linearly with the size of the policy class, instead of logarithmically.
4 Upper bound
In this section, describe main algorithm for finding policy that is close to the best-in- class in IT. This algorithm presented in Algorithm 1, is an instance of policy search with uniform exploration. Specifically, we first collect dataset 'D of n episodes by picking actions uniformly at random and subsequently use those episodes to estimate the value of each policy in IT. The algorithm then simply returns the policy से with the highest estimated value.
Our main technical innovation is a new estimation procedure for policy values Algorithm 2 that leverages the low-rank structure of the transition matrix. A straightforward way to estimate the policy value is to take the sum of the rewards on average across all episodes where all actions are consistent with the policy [Kearns et al., 2000]. Unfortunately, this rejection sampling approach yields an error of ((VKH)) Instead, our procedure only estimates the expected policy rewards for the first 3d steps. Specifically, when invoked with a given policy т, ValEstimate estimates the expected rewards for that policy by considering the subset of trajectories in D where π agrees with the chosen action till the first 3d steps, and by averaging the observed rewards in those trajectories. ValEstimate then predicts the future expected rewards for that policy by extrapolating these 3d esti- mated expected rewards. The prediction is computed by recognizing that the expected rewards for any policy π satisfy an autoregressive relation of order d as shown in Lemma 1.
In order to find the coefficients of this autoregression, ValEstimate computes À Cd by solving the optimization problem (4), where the coefficient ax are the sum of degree k monomials:
ag(A)
Σ
... X
Zd
(3)
xE10,13 a. |

---

After estimating X, ValEstimate then predicts the expected rewards for all future time steps for the policy by unfolding the autoregression model whose coefficients are given by an (A). The estimate for the value the given policy x, denoted by V is then computed as the sum of the predicted expected rewards for H steps.
Finally, Algorithm 1 returns the policy गे whose estimated value function is highest amongst all the policies in II. The following theorem characterizes the performance guarantee for the policy f returned by our algorithm.
Algorithm Policy search algorithm
Input: horizon H. rank d, number of episodes n, finite policy class II
1: Collect the dataset DD {(4), o whil) of trajectories by drawing actions from Uniform(A).
2: for policy E do
3: Estimate V by calling ValEstimate(H,c (m
4: Return: policy with best estimated value, i.e. argmax V*.
Algorithm Value estimation by autoregressive extrapolation
1: function VALESTIMATE(H, d, D. TT:
2:
for time step h 1..... ,, do
3:
Estimate expected rewards by importance sampling
R
II
(KI(T()))) = d
Wsh
4: Estimate eigenvalues of the autoregression by solving the optimization problem:
(),
argmin XECK,AER
s.t.
|
1
for 1....,d
(4)
and
Σ ( Rn SA
for h d + 1, ......3d
5: Predict RA as:
for 1sh d Ra. (-1) (- for d+1shsm
Rr
(5)
return: Estimate of the value V = = Rh.
6:
Theorem (Main Theorem). For given 8 E (0, 1), d-rank MDP, horizon H 2 and a firite policy class II, after collecting episodes, Algorithm relurns policy that with probability at least 1 admits the following guarantee:
-
(
H 2d K3d log (og((I)///)
V Z max V
xell
7
Theorem implies that Algorithm can find an e-optimal policy with probability - 8 as long as the number of samples satisfies
- 2 ((((1)
H dd K 1og(6)(111/8)
g2
The key idea used in ValEstimate, is that for any policy æ for which rank(T*) S d, the expected rewards satisfy an auto-regression of order d. The following lemma formalize this idea.
Lemma (Autoregression on expected rewards). Let be any policy for which the transition matrix T has rank at most d. Then, for any time step h 2 d 1, the expected reward for policy at time
5

---

step h, denoted by Ri satisfies the auto auto-regression
d
R
as (-11)+taau
(6)
where X E Cd denotes the set of eigenvalues of the matrix T", and ai is as defined in (3).
We defer the proof of Lemma 1 to Appendix C.I. The proof uses the fact that for any policy E II. the distribution over observations time step h is given by P4 (T*)") no. where no denotes the distribution over the observation space at initialization. If rank(T*)) S d, an applica- tion of the Cayley-Hamilton Hamilton theorem implies that we can write (1 as a linear combination of ((T")--1..... (T*) )a-d) This implies that 1% and thus the expected rewards R2, satisfy an auto- regression of order d. While the expected rewards Rt satisfy an auto-regression for every policy π, note that we cannot hope for similar relation between the instantaneous rewards rn (8% o (8))) observed when taking actions according to
The following result shows that we can simultancously estimate the expected rewards for the first 3d steps for every policy π E II. Let D be a dataset of n episodes in the MDP collected by drawing actions uniformly at random from A. Then, for any policy и, there are approximately n/ K episodes in D where the actions taken during the first 3d time steps matches the predictions of on those observations. We compute R the empirical average of the hth step reward in the corresponding n K3dd episodes that match with for the first 3d steps.
Lemma (Importance sampling). For any â E (0, 1), with probability at least 1 1 8. for any policy II and time step h E [3d], the estimates RT,, computed using importance sampling satisfy the error bound
3K 16
3d log /6)
R RT S
11
n
For given policy n, if we had access to the expected rewards [R] R ). we could have solved for the coefficients (A) exactly. However, we only have access to the empirical estimates {Ri,... ] of the expected rewards, and thus we compute the coefficients on (*) by solving the optimization problem in (4). We predict the future expected rewards by extrapolating using ag (A). The following lemma bounds the error propagated due to this mismatch in our estimation.
Lemma 3 (Error propagation bound). Let X, E Cd be such that max([Arl, [Ayl] s 1. Further, with the initial values Ri...., Ra and Ri.... Rd. let the sequence {Ra} and {Rr} be given by
d
d R = 1-1)) (a (R)
Rh
and
1=1
k=1
where the coefficients or (A) and ark (2) are define as in (3). Then, for all h 2 3d
16eh 2d
R Ral S 2d
R Rwrl
max h 33d
We defer the proof of Lemma to Appendix C.3. The proof of Theorem follows from com- bining the above three technical results. Lemma 1 suggests that for any policy E II for which rT") 5 d, the expected per step rewards satisfy an auto-regression of order at most d. The enror propagation bound in Lemma 3 and the bound on the estimation of the expected rewards for the first 3d steps given in Lemma 3 implies that, for every policy æ II, the estimated value fa close to the true value V Specificallyy, the estimation error in the value of every policy in a is bounded by Ö(H/dd2² " 3K3d log([[]))/) Thus, when n = Õ((H/d) /d (rddd3d// we have that IV= V < e for every policy и simultaneously. This implies that the returned policy that maximize the estimated value Va, is 2g sub-optimal w.r.t. the best policy in IT. We defer full details of the proof of Theorem 1 to Appendix C.5.

---

1-p
1-p
1-p
0.5
1,9
2, g
d-1, 9
d
+
0.5
1-p
1-p
1-p
1-p
1-p
1-p
0.5
1,b
P
2, b
d-1, b
d, b
1-p
1-p
1-p
Figure 1: Latent state construction: contextual combination lock. As long as the agent follows
actions of x "bluue arrows), the agent remains in good states (i,g) and receives Bernoulli11 reward but otherwise transits to bad states (i, b) and receives Bernoulli(1/2) reward.
Lower Bound
After presenting an algorithm with sample-complexity bound of (H /e"). we now show through a lower-bound that the dependency H and d cannot be improved significantly:
Theorem 2 (Lower bound). Let e 1/,6), 8 (0, 1/2), d 4, K 2 and H > 219d.
There exists a policy class of size (d) and family of MDPs with rank at most O(d), finite observation space. horizon and two actions such that the optimal policy for each MDP in the family is contained in the policy class and the following holds: Any algorithm that returns an e- optimal policy, with probability at least for every MDP in this family has to collect least
2 H
d/2
log
41d
25
episodes in expectation in some MDP in this family.
The above lower bound shows that an exponential dependency on d in the form of (H/d)² is un- avoidable, even when realizable policy class with x* and moderate size log [I[] log (H/d) is given to the learner. We now provide brief description of the problem class used in the proof of our lower bound but defer details of our construction and the proof Appendix
The Markov decision processes in the proof of our lower bound bear some similarity to the so-called combination lock constructions used in prior works [Krishnamurthy al., 2016, Du al., 2019b], where the algorithm only receives positive feedback after playing a certain sequence of actions. Modelling a combination lock typically requires K- states in MDPs and ((H) latent states in POMDP. In contrast, our contextual version of combination lock uses a low-rank MDP with very large observation space but where the transition dynamics are governed by ( & hidden states (and thus the rank is (d)). The latent state structure is shown in Figure 1. The agent starts at the top left latent state and always progresses with probability p d/ to the right. As long as chooses good actions (blue edges), it progresses in the top chain where it will eventually reach state (d, g) with constant probability and receive a reward of 1 with probability 1/2 + E. If at any time before reaching state (d, g). it chooses bad action (red edges), then it moves to the lower chain where eventually has a 1/2 chance of receiving a reward 1.
If the latent states s S were directly observable, an e-optimal policy could be learned with O(dH/e²) samples. However, in the latent state s, the agent only receives an observation drawn uniformly from a large set X,, The sets (X, ) form partition of the entire observation space X' and there a mapping Φ: X' + S that identifies Ma in our problem class is parameterized by the mapping ő and a policy n" TI. The class of policies can arbitrary as long as each pair of policies differ on at least a constant fraction of X. In MDP M de only the action πt" r²()) good action (blue action) and allows the agent to
latent state for each observation. Each MDP
7

---

stay in the top latent state chain. Thus, finding the (EE)- policy in II for Mx-.d is equivalent to identifying '."
Importantly, our problem class contains MDP M for every possible x¹ E IT and latent state mapping Ø. We pick the number of observations large enough that observations become uninfor- mative and it is virtually impossible for a learner to learn ø. Instead it can only hope to learn æ by identifying the bias e in the rewards. We can show that this requires number of samples that not much smaller than collecting (11/E2In(1 (n(1 episodes with each of the (H/d)* policies in IT.
While the lower bound in Theorem 2 does not have a dependence on log([I1)). The simple observa- tion that the contextual bandit problem can be seen as an instance our setup where d 1, implies that some dependence on log([ is necessary based on standard contextual bandit lower bounds [Lattimore and Szepesvári, 2020]. However, getting a lower bound of the form S2 [(H1log([I) (I)( an interesting question, which we leave open for future work. Finally, while the provided lower bound is constructed using an MDP with two actions, it can easily be extended to incorporate multiple actions, and when the learner has access a generative model.
Adaptive algorithms
In Section 4, the algorithm introduced benefits from the guarantee provided by Theorem 1, which is near optimal in the worst case the lower bound construction shows. However, in cases where the transition matrix induced by the policy class all have nicer eigenspectra, one could expect to have an improved sample complexity. Ideally, the algorithm should automatically adapt more favorable eigenspectra. This is precisely what we describe in this section. We give an adaptive algorithm whose sample complexity improves when the eigenspectrum of transition matrices induced by the policy class admits more favorable property.
6.1 Adaptivitity to the eigenspectrum
Our adaptive algorithm, presented in Algorithm 3 in Appendix D.3, is policy search algorithm similar Algorithm where, instead of invoking the procedure ValEstimate, we compute the value function for every policy ı by invoking the procedure AdaValEstimate given in Appendix D.3.
AdaValEstimate follows along the lines of ValEstimate. When invoked for policy it first esti- mates the expected rewards for the first 3d time steps. Then, AdaValEstimate computes the auto- regression coefficients Or (A). and uses them to predict the expected rewards for all future time steps by extrapolating. The major difference between ValEstimate and AdaValEstimate is the way the coefficients ag (A) are computed. Specifically, using A == 2d4 (883d log (d [1)/))/n the procedure AdaValEstimate computes the coefficients À by solving the optimization problem
H II
Ā +- argmin xecd
s.t. A = 11/ Σ (eel*) h=0
for 2 < k S d,
1=
and
(x (11))ttaa(2)8Bhnooao_a (2) SA
1) k+1
for d + 1 1 h < 3d.
The above modification to the computation of X allows error propagation bound to adapt to X, which defines the coefficients of autoregression for the expected rewards in policy я (given in Lemma 1). The propagated error would be small if the coordinates of À bounded away from 1. The policy म. returned by Algorithm 3, thus enjoys the following adaptive performance guarantee.
Theorem 3 (Adaptive upper bound). For a given å E (0,1). d-rank MDP, horizon H and a finite policy class II, after collecting episodes, Algorithm 3 returns a policy that with probability at least 1 - 8 admits the following guarantee:
o (16e)2) max Σ
H
D ))
3d log(611d/))
V max T
NEll
n'Ell
n
0=0
8

---

Proof of Theorem 3 follows along the lines of the proof of Theorem where we replace the enror propagation bound (in Lemma 3) by a similar bound that adapts to the eigenspectrum of the transi- tion matrix T We defer the proof details to appendix Appendix D.3. Note that for any | S and thus Ih=o Da-' < H. Using this fact in Theorem 3 recovers the result of Theorem 1, albeit upto a multiplicative factor of 22d In the following, we provide an example of low rank MDP problem in which the adaptive bound above could be much better than the worst case upper bound Theorem
Corollary (Well mixing MDP). Given E (0, 1), horizon H and a finite policy class II. Let M. be a d-rank MDP such that the second largest eigenvalue of the transition matrix T satisfies [a]] & - for every policy æ E II. Then, after collecting n episodes, our adaptive algorithm returns a policy that with probability least 8 admits the following guarantee:
V max V - (0(( well
K
2d 1
Vn
where the Ô hides polynomial of d, H. log(1/6) and multiplicative constants.
We next show through a lower bound that the adaptive upper bound in Theorem 3 cannot be im- proved further. We defer the proof details to Appendix E.3.
Theorem (Adaptive lower bound). Let e E (0, 1/6), E 10,1 d 2 4 and (Ad)eta E [0, 1j satisfy
d
d2d II
1 1- S HX)(H)
and
Σ - 4 4n(44)
H
Then, there is realizable policy class and a family of MDPs with rank most ((d), finite obser- vation space, horizon H and two actions such that: For each i E [d], policy π and MDP M in this class, there an eigenvalue of the induced transition matrix T's in [2./2, dd}. Furthermore, any algorithm that returns, with probability at least 1 1- 8 an s-optimal policy for any MDP in this family, has to collect least
1
log( (2((1
22
A
episodes expectation some MDP in this family.
Adaptivity to rank. In Appendix D.4, we also provide an adaptive algorithm that can find the best policy in the class II without knowing the value of the rank parameter d' Our adaptive algorithm, given in Algorithm 5, follows from standard techniques in the model selection literature. For every E [1]] we compute optimal policy H. assuming that the rank d' d. Then, for each d E [H], we estimate the value function for the policy 7a by drawing n n/2ff fresh trajectories using that policy. Finally, return the policy से from the (Ta) with the highest estimated value. The returned policy से satisfies, with probability at least 8,
H max V ((H #Ell
20"
(8K)ad log (81((11188)
V
d+
n
We defer full details of the analysis to the Appendix.
7 Conclusion
We presented a new analysis of reinforcement learning with rich observations in the agnostic setting, under the low rank MDP assumption. We gave both non-adaptive and an adaptive algorithm for learning a quasi-optimal policy in this scenario, which we showed to benefit from guarantees that are only polynomial in the horizon and the number of actions, and only logarithmic in the size of the policy class considered. While our bound is exponential in the MDP rank, we give nearly matching lower bounds proving that that dependency unavoidable. The agnostic setting is a more realistic setting that has received less attention in the literature. We view this work as initiating the study of this general setting under workable assumptions and believe that many other algorithmic and theoretical aspects of such scenarios need to be studied further.

---

Acknowledgements
AS was an intern Google Research, NYC for the duration of the work. KS acknowledges sup- port from NSF CAREER Award 1750575. YM has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grant number 993/17) and the Yandex Initiative for Machine Learning at Tel Aviv University.
Funding Transparency Statement
Funding in direct support of this work: NSF CAREER Award 1750575, NSF-CCF-1815892 Google Faculty Fellowship, an NSERC Discovery Grant, and a University of Waterloo startup grant.
References
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 8187540):529-533 2015.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanetot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self- celf-play. Science, 362(6419):11400 1144, 2018.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czameeki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-33) 2019.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning polynomial time. Ma- 2002.
chine learning, 49(2-3):209
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning, Journal of Machine Learning Research, 3(0ct):213-23 2002.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pages 263-272, 2017.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. International Conference on Machine Learning, 2019.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, pages 1840-1848, 2016.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire, Con- textual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1704-1713, JMLR. org, 2017.
Christoph Dann, Nan Jiang, Akshay Krishnamurthy. Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient pac with rich observations. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural In- formation Processing Systems, volume 31, 2018
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674. PMLR, 2019a.
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state ab- straction and provably efficient rich-observation reinforcement learning, In International confer- ence on machine learning, pages 6961-6971 PMLR, 2020.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complex- ity and representation learning of low rank mdps. Advances Neural Information Processing Systems, 33, 2020a.
10

---

Tiancheng Jin and Haipeng Luo. Learning adversarial markov decision processes with bandit feed- back and unknown transition. arXiv preprint arXiv:1912.01192, 2019.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pages 2898 2933. PMLR, 2019.
lan Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, pages 1466-1474, 1474, 2014.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and samplc-efficient algorithms. arXiv preprint arXiv:2102.00815, 2021.
Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and
Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. arXiv preprint arXiv:2103. 10897, 2021.
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed- horizon reinforcement learning. In Advances in Neural Information Processing Systems, pages 2818-2822 2015.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv:1910.00 03011,,,,, 2019b.
Michael Kearns, Yishay Mansour, and Andrew Y Ng. Approximate planning in large pomdps via reusable trajectories. In Advances in Neural Information Processing Systems, pages 1001-1007 2000.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10756. PMLR, 2020.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
Yining Wang, Ruosong Wang. Simon Shaolei Du and Akshay Krishnamurthy, Optimism in rein- forcement learning with generalized linear function approximation. In International Conference on Learning Representations, 2021a.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07035, 2021.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan. On function approx- imation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.0422 0402224462. 2020.
Jihao Long, Jiequn Han, et al. An 12 analysis of reinforcement learning in high dimensions with kernel and neural network approximation. arXiv preprint arXiv:2104.07794 2021.
Devavrat Shah, Dogyoon Song, Zhi Xu, and Yuzhe Yang. Sample efficient reinforcement learning via low-rank matrix estimation. arXiv preprint 1xXiv:2006.06135. 2020.
Yasin Abbasi- Yadkori, Peter L Bartlett, and Csaba Szepesvári. Online learning in markov de- cision processes with adversarially chosen transition probability distributions. arXiv preprint arXiv: 3055, 2013.
Mohammad Gheshlaghi Azar, Alessandro Lazaric, and Emma Brunskill. Regret bounds for rein- forcement learning with policy advice. In Joint European Conference on Machine Learning and
11

---

Knowledge Discovery in Databases, pages 97-112. Springer, 2013.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement 2010.
learning, Journal of Machine Learning Research,
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In International Conference on Algorithmic Learning Theory, pages 320-334. Springer, 2012.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems,
14, 2001.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
Sergey Levine and Vladlen Koltun. Guided policy search. In International conference on machine learning, pages 1-9. PMLR, 2013.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradi- ent methods: Optimality, approximation, and distribution shift. arXiv preprint arXiv: N0xii://08.000 00261, 2019.
Yasin Abbasi- Yadkor, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning, pages 3692-3702. PMLR, 2019.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint 1906::9006001700 2019.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of )eruue) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33, 2020.
Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pc-pg: Policy cover directed explo- ration for provable policy gradient learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 13399-13412. Curran Associates, Inc., 2020b.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. arXiv preprint 1111v:1810 2018.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. arXiv preprint arXiv: 19Xiv::900.00 0000004733, 2019.
Ruosong Wang, Dean Foster, and Sham M. Kakade. What are the statistical limits of offline (rl} with linear function approximation? In International Conference Learning Representations, b021b.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be expo- nentially harder than online rl. arXiv preprini arXiv:2012.08005. 2020.
Gellert Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR, 2021.
J Segercrantz. Improving the cayley- hamilton equation for low-rank transformations. The American mathematical monthly, 99 99(1)22 44, 1992.
DJ Hartfiel. Tracking in matrix systems. Linear algebra and its applications, 165:233-2555 2-033,250,11 1992.
12

---

Darald Hartfiel. Dense sets of diagonalizable matrices. Proceedings the American Mathematical Society, 12366::669-1672, 1995.
Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
Pascal Massart. Concentration inequalities and model selection. Springer, 2007.
Aurélien Garivier, Pierre Ménard, and Gilles Stoltz. Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 44(2):377-399, 2019.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598, PMLR, 2021.
13


Reviews:
[{"review_id": "fbkhOp2Ule", "reviewer": "Reviewer_KWkQ", "summary": "This paper studies RL with rich observation and low rank structure. It designs an algorithm that can work without the realizability assumption. The algorithm is guaranteed to find a good policy within a number of samples exponential in rank $d$. An almost matching lower bound is also provided.", "questions": "", "limitations": "", "rating": 7, "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": "This paper is well written and easy to follow. The key idea is cute. The most interesting point to me is they put no assumption on the policy class and they don’t assume access to any feature representation of the underlying low rank structure. The exponential dependence is also well justified. \n\n\nQuestions:\n\nDo you think the factor $K^d$ in the upper bound is necessary? The reason I am asking this question is that in linear MDPs, the optimal sample complexity doesn’t depend on $K$. Although the assumption in this paper is strictly weaker than linear MDPs, I am still curious if it’s possible to avoid this dependence or prove it’s indeed unavoidable. \n\nIs the optimization problem in (4) computationally hard in general?\n\nWhy the sample complexity doesn't depend on the magnitude of the eigenvalues? Is it hided in the $\\mathcal{O}$-notation or you simply assume it's upper bounded by some constant? If so, please write it as an assumption or state the dependence explicitly in the theorem. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretical. I am not aware of any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "aCyhIelc_SO", "reviewer": "Reviewer_KBFp", "summary": "This paper firstly discusses the possibility of RL without assuming optimal value function realizability in a rich observation setting. Relying on a uniform low-rank assumption, a novel algorithm is proposed to return a near-sub-optimal policy and the sample complexity scales polynomially in log(|\\Pi|) and H while exponentially in d, which is further proved to be necessary.", "questions": "", "limitations": "", "rating": 8, "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": "This paper discusses an interesting but less-studied question and provides systematic answers (sufficient, necessary, and improved sufficient results). I appreciate its technical novelty, theoretical completeness, and well-structured writing. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "QkOeGu9AB16", "reviewer": "Reviewer_uoih", "summary": "This paper studies RL with linear function approximation when transition is low rank, but the features are unknown. The goal is to compete against a policy class that may not contain any near-optimal policy. The paper proposes an algorithm based on autoregression and shows a sample complexity bound that is exponential in the rank; a corresponding lower bound suggests that this dependence is unavoidable.", "questions": "", "limitations": "", "rating": 7, "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": "This paper studies the setting where: (1) only realizability under unknown features (factorizations) is assumed; (2) only an agnostic policy class is given. Compared to existing work on linear function approximation RL (e.g. [Agarwal et al. 2020]), the assumption made in this paper is among the weakest and least restrictive. It is then perhaps not surprising that the final bounds have an exponential dependence on $d$, which is further showed to be necessary. Overall I think the results and approach in this paper are novel and would be very interesting to RL theory community.\n\nThe basic algorithmic idea is to collect samples via uniform exploration for the first $3d$ time steps, and then evaluate each policy via autoregression. This framework of data collection-evaluating all policies is a bit similar to some prior work (e.g. [Wang et al. 2020]), but the key innovation is using autoregression relations for policy evaluation, which is a nice way to exploit linearity when the feature/factorization is unknown.\n\nI have quickly checked the analysis in this paper and have found no issues with correctness. Also most of my questions have been well addressed by the discussions. I only have two small questions for the authors:\n\n- Can $3d$ (i.e. the number of steps performing uniform exploration) be shortened to $2d$ or perhaps $d$? It would be nice if the exponents can be closer to that of the lower bound.\n\n- Does the lower bound still hold if we have access to a generative model?\n\n----\n\nMinor comments/typos:\n\n- In Lemma 13: Should it be assumed that $|\\lambda_i|<1$ for all $i\\in [d]$ in the statement? Otherwise $\\hat\\lambda=\\lambda$ may not be feasible.\n- In the proof of Theorem 1, should it be mentioned that all eigenvalues of $T^\\pi$ have magnitude $\\le 1$ when evoking Lemma 13? It just seems a bit odd to me if the proof works without using the fact.\n- In Lemma 11: is $\\lambda_k$ supposed to be $\\lambda_d$?\n- On Line 803 and 819: should references to Definition 2 be Definition 3?\n- Line 847, Eq. (21): should $\\lambda$ be $\\hat\\lambda$?\n- Line 293: Should $K$ it be $H$?\n- Line 293: Probably should be $1+\\lambda+...+\\lambda^{H-1}$.\n\n-----\n\nReferences:\n\n[Agarwal et al. 2020] Flambe: Structural complexity and representation learning of low rank mdps.\n\n[Wang et al. 2020] Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretical and do not present foreseeable negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "K2TVPp7vzZB", "reviewer": "Reviewer_e1Ge", "summary": "The paper studies reinforcement learning in low-rank MDPs under an agnostic perspective, where the agent does not assume realizability of the optimal value function in some given functional space but rather has to find a near-optimal policy in a given policy class. For this problem, the authors propose a policy search algorithm based on uniform exploration and careful estimation of the expected returns of each policy. They derive an upper bound on its sample complexity for computing an \\epsilon-optimal (within the class) policy that scales logarithmically with the number of policies but exponentially in the MDP rank. They further show a lower bound which confirms that this exponential dependence is unavoidable in the worst-case. Finally, they propose a variant of this algorithm that enjoys a more adaptive sample complexity scaling with the eigenvalues of the true transitions matrices.", "questions": "", "limitations": "", "rating": 7, "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": "Significance, novelty, and relevance\n---\n\nThe paper considers a relevant problem, agnostic RL in MDPs with low-rank structure. While recently there have been many works on both low-rank MDPs and on dealing with misspecified models (i.e., non-realizable function classes), to my knowledge the perspective studied in this paper is novel. I found this contribution interesting and significant. In particular, I appreciated that the authors derived lower bounds which provide good insights into the complexity of this setting. While the proposed algorithm is not very exciting (it is simply an instance of uniform exploration), I found quite interesting the way expected returns are estimated by leveraging the low-rank structure. Overall I think that this work is a good starting point for studying this setting and tend to vote for acceptance.\n \n\nRelation with prior work\n---\n\nTo my knowledge, relevant prior works are discussed.\n\nIt might be good to also discuss [1], where the authors consider a fixed policy class and the goal is to compete with the best-in-class policy as in this agnostic setting. In that case, the MDP is assumed to be adversarially generated and the authors still show guarantees that scale with \\log|\\Pi|. Another paper with a similar aim is [2].\n\n[1] Abbasi-Yadkori, Yasin, Peter L. Bartlett, and Csaba Szepesvári. \"Online learning in Markov decision processes with adversarially chosen transition probability distributions.\" arXiv preprint arXiv:1303.3055 (2013).\n\n[2] Azar, Mohammad Gheshlaghi, Alessandro Lazaric, and Emma Brunskill. \"Regret bounds for reinforcement learning with policy advice.\" Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, Berlin, Heidelberg, 2013.\n\n\nClarity of writing\n---\n\nI found the paper very well-written and easy to read. I think the authors did a good job in providing intuition behind all results, in motivating their design choices, and in sketching the proofs. The paper seems mostly self-contained, except maybe for Section 6 which requires going back and forth from the appendix.\n\n\nDetailed comments/questions\n---\n\n1. I was wondering how the agnostic setting studied here compares to the one of linear (low-rank) MDPs with misspecification (the one studied by the papers mentioned in Section 3). In the latter setting, not only the value functions become non-realizable under the given linear function class, but the MDP itself is no longer describable by a linear model, and hence it is no longer low-rank, since it is assumed linear only up to a (possibly small) non-linear perturbation. Here, instead, while the agent is agnostic to the representation of the optimal value function, the MDP is still describable by a low-rank model and the agent can leverage such structure. How do the two settings compare? Can we say that one is more general than the other? Or easier than the other?\n\n2. Related to the previous point, the second-last paragraph of Section 3 mentions that the setting studied in this paper is more ambitious. I am not sure that I fully understand why. It seems to me that competing with the optimal policy of the given MDP under a non-realizability assumption (as in the works mentioned there) is more challenging than competing with the best policy in a given class. \n\n3. A possible limitation of the proposed algorithm is that it needs to enumerate all policies in the given class in order to estimate their returns, which is very inefficient when the number of policies is large. Related question: any idea on how to deal with infinite/continuous policy spaces?\n\n4. One limitation of the lower bound (Theorem 2) is that it does not show what is the optimal dependence on K in the worst-case. The upper bound suffers a dependence of K^d, which I guess is due to importance sampling with a uniform exploration policy. Do you believe that it would be possible to extend the lower bound to more than 2 actions and show that such dependence is unavoidable in the worst-case?\n\n5. Regarding uniform exploration, is there anything better you can do without changing the analysis much? For instance, if the final purpose is to estimate the return of the policies in \\Pi only, can you take, e.g., a mixture of these for exploration? For instance, if no policy in \\Pi plays a certain action in a given state, do we still need to explore that action?\n\nMinor:\n- line 106: h should be h' in r()\n- line 133: an optimal policy\n- equation below line 180: is that \\Omega() of that factor?\n- I would suggest moving Alg. 1 and 2 to page 4, closer to where they are described to ease readability\n- are the policies in \\Pi stochastic or deterministic? Sec. 2 mentions stochastic, but the importance sampling estimator in Alg. 2 is for deterministic\n- (5) in Alg. 2: why not using the estimator \\hat{R} for all stages up to 3d instead of d? Lemma 2 gives concentration for all of them\n- line 240: figure 2 should be figure 1\n- line 279: predict", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the limitations of their algorithm and leave their solution to future work. I do not see any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of learning near-optimal policies in low-rank MDPs and arbitrary policy classes, and proposes an algorithm with nontrivial guarantees in this setting, constituting one of the first theoretical guarantees in any agnostic learning scenario within the context of reinforcement learning. This is a problem of significant interest, and the reviewers all agreed that the paper provides some interesting technical innovations and clearly advances the state of the art in the area.

Overall, this is an excellent paper that clearly deserves to be published at the conference.
Decision: Accept (Spotlight)