Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
Year: 2021

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 ⇧ that may not contain any nearoptimal 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 e O (H4dK3d log |⇧|)/"2 where H is the length of episodes, K is the number of actions and " > 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.

text: (H4dK3d log |⇧|)/"2 where H is the length of
episodes, K is the number of actions and " > 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.

heading: 1 Introduction
text: 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 et al., 2018], AlphaStar’s victory over top-ranked professional players in StarCraft [Vinyals et al., 2019], or practical self-driving cars. These applications all correspond to the setting of rich observations, where the state space is very large and where observations may be images, text or audio data. In contrast, most provably efficient RL algorithms are still limited to the classical tabular setting where the state space is 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 a realizability and a low-rank assumption [Krishnamurthy et al., 2016, Jiang et al., 2017, Dann et 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 a low-rank transition matrix [Jin and Luo, 2019], a low Bellman rank [Jiang et al., 2017], Wittness rank [Sun et al., 2019], Eluder dimension [Osband and Van Roy, 2014], Bellman-Eluder dimension [Jin et al., 2021], or bilinear classes [Du et al., 2021]. 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.
35th Conference on Neural Information Processing Systems (NeurIPS 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 development 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, independently 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 assumptions, 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 policy. Specifically, we study agnostic Reinforcement Learning (RL) with a fixed policy class ⇧ in the episodic MDPs with rich observations. Provably sample-efficient algorithms for agnostic RL would be highly desirable but it is still unknown to what degree learning is 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 a sample complexity upper bound of O(|⇧|/"2). Kearns et al. [2000] also showed that an upper bound of (KH log |⇧|)/"2 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 a lower bound on the sample complexity of the form min{|⇧|,KH}/"2 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 in the class ⇧, and is assumed to be small.
• We provide a uniform exploration-based algorithm that can find an "-sub-optimal policy w.r.t. the policy class ⇧ after collecting O((HK/d)4d log(d|⇧|)/"2) samples in the MDP. This bound shows that one can achieve a sample complexity that is polynomial in both H and log |⇧|, 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 O(d)-length paths for a 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 ⌦ (H/d)d/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 on the rank.
• Finally, we seek to improve upon the Hd term and provide an adaptive algorithm that admits a 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, it 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 reinforcement 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.

heading: 2 Problem Setup
text: We consider an episodic Markov decision process with episode length H 2 N, observation space X and action space A := {1, . . . ,K}. For ease of exposition, we assume that the observation space X is finite (albeit extremely large), but our results can be readily extended to countably infinite and possibly uncountably infinite observation spaces. Each episode is a sequence ((x1, a1, r1), (x2, a2, r2), . . . , (xH , aH , rH)) 2 (X ⇥A⇥ R)H , where the initial observation x0 is drawn from the initial distribution µ0 2 (X ), the actions are generated by the learning agent and all the following observations are sampled from the transition kernel xh+1 ⇠ T (·|xh, ah) 2 (X ) that depends on the previous observation and action. Finally, the rewards rh are drawn from a subGaussian distribution with mean r(xh, ah) where r : X ⇥ A 7! [0, 1]. The learning agent does not know the transition kernel T , the initial distribution µ0, or the reward function r.
In our setting, the agent is given a policy class ⇧ ✓ {X 7! (A)} consisting of policies that map observations to distributions over the actions A. For any policy ⇡ 2 ⇧, we denote by T⇡ 2 RX⇥X , the transition matrix induced by ⇡, i.e., for any x, x0 2 X ,
[T⇡](x0,x) = Ea⇠⇡(x) T (x0 | x, a).
Assumption 1 (Low-rank transition). There exists d 2 N such that rank(T⇡)  d for all ⇡ 2 ⇧.
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 ⇡ = ( ⇡1 , . . . , ⇡d ) > 2 Cd to denote the eigenvalues of the transition matrix T⇡ with rank at most d. Without any loss of generality, assume that | ⇡1 | | ⇡2 | . . . | ⇡d |.
We denote by P⇡ 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⇡h := E⇡[r(xh, ah)]. (1)
The value function of ⇡ at time h is given by V ⇡h (x) = E ⇡ hPH h0=h r(xh0 , ah0) | xh0 = x i . Further, when using V ⇡ without a time index and arguments, we mean the value or expected H-step return:
V ⇡ := E[V ⇡0 (x0)] = E⇡ h HX
h=1
r(xh, ah) i = HX
h=1
R⇡h, (2)
the value function averaged over initial observations.
Learning objective. The goal of the learner is to return a policy e⇡, after interacting with the MDP for n episodes of length H , such that the value of the returned policy is as close as possible to the value of the best policy in ⇧, that is,
V e⇡ max ⇡2⇧ V ⇡ ",
where the error " is a small as possible and may depend on n, the policy class ⇧ and the MDP.

heading: 3 Related work
text: 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 in designing RL algorithms with general function approximation [Jiang et al., 2017, Dann et al., 2018, Sun et al., 2019, Du et al., 2019a, Wang et al., 2020, Du et al., 2021]. In particular, Jiang et al. [2017] introduced the notion of Bellman rank, a 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 algorithms by Sun et al. [2019]. While these algorithms work across a variety of problem settings, their sample complexity scales with log(|F|). Furthermore, these algorithms also require the optimal value function f⇤ to be realized in F . In our work, we do not
assume that the learner has access to a value function class F . In fact, given a value function class F , we can construct the policy class ⇧F that corresponds to greedy policies induced by the class F . However, given just a policy class ⇧, one cannot construct a value function class, without additional knowledge of the underlying dynamics.
Our Assumption 1 implies that for any policy ⇡ 2 ⇧, the transition dynamics exhibits a low-rank decomposition with dimension d, that is T⇡(x0|x) = h ⇡(x), ⇡(x0)i, for some d-dimensional feature maps ⇡, ⇡ : X 7! Rd. 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 et al., 2021a]. The works most closely related to 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 . 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 ⇡, ⇡ nor has access to a realizable function class for them, and thus these methods are not applicable.
Several of the works mentioned above recognize the issue of a strict realizability assumption and provide results only when the function class contains a 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 ⇧, independent of how close the best return in the class max⇡2⇧ 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 a good but not necessarily optimal policy. Finally, there are a 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. AbbasiYadkori et al. [2013] assumes that the the agent fully observed the current transition kernel and reward instead of just a sample from it, or the provided bound [Azar et al., 2013] scales linearly with the size of the policy class, instead of logarithmically.

heading: 4 Upper bound
text: In this section, we describe our main algorithm for finding a policy that is close to the best-inclass in ⇧. This algorithm presented in Algorithm 1, is an instance of policy search with uniform exploration. Specifically, we first collect a dataset D of n episodes by picking actions uniformly at random and subsequently use those episodes to estimate the value of each policy in ⇧. The algorithm then simply returns the policy e⇡ with the highest estimated value. Our main technical innovation is a new estimation procedure for policy values in 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 ⌦( p
KH). 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 estimated 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 b 2 Cd by solving the optimization problem (4), where the coefficient ↵k( ) are the sum of degree k monomials:
↵k( ) = X
x2{0,1}d s.t. kxk1=k
x11 x2 2 . . . xd d . (3)
After estimating b , ValEstimate then predicts the expected rewards for all future time steps for the policy ⇡ by unfolding the autoregression model whose coefficients are given by ↵k(b ). The estimate for the value of the given policy ⇡, denoted by eV ⇡ , is then computed as the sum of the predicted expected rewards for H steps.
Finally, Algorithm 1 returns the policy e⇡ whose estimated value function is highest amongst all the policies in ⇧. The following theorem characterizes the performance guarantee for the policy e⇡ returned by our algorithm.
Algorithm 1 Policy search algorithm Input: horizon H , rank d, number of episodes n, finite policy class ⇧
1: Collect the dataset D = {(xth, a t h, r t h) H h=1} n t=1 of n trajectories by drawing actions from
Uniform(A). 2: for policy ⇡ 2 ⇧ do 3: Estimate eV ⇡ by calling ValEstimate(H, d,D,⇡). 4: Return: policy e⇡ with best estimated value, i.e. e⇡ 2 argmax⇡2⇧ eV ⇡ .
Algorithm 2 Value estimation by autoregressive extrapolation 1: function VALESTIMATE(H, d,D,⇡): 2: for time step h = 1, . . . , 3d do 3: Estimate expected rewards by importance sampling
bRh = 1
n
nX
t=1
rth Y
h0h
K ⇡(xth0) = a t h0
4: Estimate eigenvalues of the autoregression by solving the optimization problem:
(b , b ) argmin 2Cd, 2R
s.t. | k|  1 for k = 1, . . . , d (4)
and
dX
k=1
( 1) k+1↵k( ) bRh k bRh  for h = d+ 1, . . . , 3d
5: Predict eRh as:
eRh = (
bRh for 1  h  dPd k=1( 1) k+1 ↵k(b ) eRh k for d+ 1  h  H . (5)
6: return: Estimate of the value eV = PH
h=1 eRh.
Theorem 1 (Main Theorem). For a given 2 (0, 1), d-rank MDP, horizon H d and a finite policy class ⇧, after collecting n episodes, Algorithm 1 returns a policy e⇡ that with probability at least 1 admits the following guarantee:
V e⇡ max ⇡2⇧
V ⇡ O ⇣ d3 · ⇣H d
⌘2d r
K3d log(6⇧d/ )
n
⌘ .
Theorem 1 implies that Algorithm 1 can find an "-optimal policy with probability 1 as long as the number of samples n satisfies
n = ⌦ ⇣⇣H
d ⌘4dK3d log(6d|⇧|/ ) "2 ⌘ .
The key idea used in ValEstimate, is that for any policy ⇡ for which rank(T⇡)  d, the expected rewards satisfy an auto-regression of order d. The following lemma formalize this idea. Lemma 1 (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 d+ 1, the expected reward for policy ⇡ at time
step h, denoted by R⇡h , satisfies the auto-regression
R⇡h = dX
k=1
( 1) k+1↵k( ⇡ )R⇡h k, (6)
where ⇡ 2 Cd denotes the set of eigenvalues of the matrix T⇡ , and ↵k( ⇡) is as defined in (3).
We defer the proof of Lemma 1 to Appendix C.1. The proof uses the fact that for any policy ⇡ 2 ⇧, the distribution over observations at time step h is given by µ⇡h = (T ⇡ ) hµ0, where µ0 denotes the distribution over the observation space at initialization. If rank(T⇡)  d, an application of the Cayley-Hamilton theorem implies that we can write (T⇡)h as a linear combination of ((T⇡)h 1, . . . , (T⇡)h d). This implies that µ⇡h , and thus the expected rewards R ⇡ h , satisfy an autoregression of order d. While the expected rewards R⇡h satisfy an auto-regression for every policy ⇡, note that we cannot hope for a similar relation between the instantaneous rewards rh(s⇡h,⇡(sh)) observed when taking actions according to ⇡.
The following result shows that we can simultaneously estimate the expected rewards for the first 3d steps for every policy ⇡ 2 ⇧. 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/K3d episodes in D where the actions taken during the first 3d time steps matches the predictions of ⇡ on those observations. We compute bR⇡h as the empirical average of the hth step reward in the corresponding n/K3d episodes that match with ⇡ for the first 3d steps. Lemma 2 (Importance sampling). For any 2 (0, 1), with probability at least 1 , for any policy ⇡ 2 ⇧ and time step h 2 [3d], the estimates bR⇡h computed using importance sampling satisfy the error bound
| bR⇡h R⇡h|  r 2K3d log(6d|⇧|/ )
n +
2K3d log(6d|⇧|/ )
n .
For a given policy ⇡, if we had access to the expected rewards {R⇡1 , . . . , R⇡d}, we could have solved for the coefficients ↵k( ) exactly. However, we only have access to the empirical estimates { bR1, . . . , bRd} of the expected rewards, and thus we compute the coefficients ↵k(b ) by solving the optimization problem in (4). We predict the future expected rewards by extrapolating using ↵k(b ). The following lemma bounds the error propagated due to this mismatch in our estimation.
Lemma 3 (Error propagation bound). Let , b 2 Cd be such that max{| 1|, |b 1|}  1. Further, with the initial values R1, . . . , Rd and eR1, . . . , eRd, let the sequence {Rh} and { eRh} be given by
Rh = dX
k=1
( 1) k+1↵k( )Rh k and eRh =
dX
k=1
( 1) k+1↵k(b ) eRh k,
where the coefficients ↵k( ) and ↵k(b ) are define as in (3). Then, for all h 3d+ 1,
| eRh Rh|  2d · ⇣ 16eh
d ⌘2d · max h03d |Rh0 eRh0 |.
We defer the proof of Lemma 3 to Appendix C.3. The proof of Theorem 1 follows from combining the above three technical results. Lemma 1 suggests that for any policy ⇡ 2 ⇧ for which rank(T⇡)  d, the expected per step rewards satisfy an auto-regression of order at most d. The error 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 ⇡ 2 ⇧, the estimated value eV ⇡ is close to the true value V ⇡ . Specifically, the estimation error in the value of every policy in ⇡ is bounded by eO((H/d)2d p K3d log(|⇧|)/n). Thus, when n = eO((H/d)4dK3d/"2), we have that |eV ⇡ V ⇡|  " for every policy ⇡ 2 ⇧ simultaneously. This implies that the returned policy , that maximize the estimated value eV ⇡ , is 2" sub-optimal w.r.t. the best policy in ⇧. We defer full details of the proof of Theorem 1 to Appendix C.5.

heading: 5 Lower Bound
text: After presenting an algorithm with sample-complexity bound of eO((H/d)2dK3d/"2), we now show through a lower-bound that the dependency on H and d cannot be improved significantly: Theorem 2 (Lower bound). Let " 2 (0, 1/26), 2 (0, 1/2), d 4, K = 2 and H 219d. There exists a policy class of size (H/d)d and a family of MDPs with rank at most ⇥(d), finite observation space, horizon H 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 "- optimal policy, with probability at least 1 , for every MDP in this family has to collect at least
⌦
⇣ 1
H"2 ⇣ H 41d ⌘d/2 log ⇣ 1 2 ⌘⌘ .
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)d is unavoidable, even when a realizable policy class with ⇡⇤ 2 ⇧ and moderate size log |⇧| = d log(H/d) is given to the learner. We now provide a brief description of the problem class used in the proof of our lower bound but defer details of our construction and the proof to Appendix E.
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 et al., 2016, Du et al., 2019b], where the algorithm only receives positive feedback after playing a certain sequence of actions. Modelling a combination lock typically requires KH states in MDPs and ⇥(H) latent states in POMDP. In contrast, our contextual version of a combination lock uses a low-rank MDP with very large observation space but where the transition dynamics are governed by ⇥(d)⌧ H 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/H to the right. As long as it 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 + ". If at any time before reaching state (d, g), it chooses a bad action (red edges), then it moves to the lower chain where it eventually has a 1/2 chance of receiving a reward of 1.
If the latent states s 2 S were directly observable, an "-optimal policy could be learned with O(dH/"2) samples. However, in the latent state s, the agent only receives an observation drawn uniformly from a large set Xs. The sets {Xs}s2S form a partition of the entire observation space X and there is a mapping : X 7! S that identifies the latent state for each observation. Each MDP M⇡⇤, in our problem class is parameterized by the mapping and a policy ⇡⇤ 2 ⇧. The class of policies ⇧ can be arbitrary as long as each pair of policies differ on at least a constant fraction of X . In MDP M⇡⇤, , only the action ⇡⇤(x) is a good action (blue action) and allows the agent to
stay in the top latent state chain. Thus, finding the ⇥(")-best policy in ⇧ for M⇡⇤, is equivalent to identifying ⇡⇤.
Importantly, our problem class contains MDP M⇡⇤, for every possible ⇡⇤ 2 ⇧ and latent state mapping . We pick the number of observations large enough so that observations become uninformative and it is virtually impossible for a learner to learn . Instead it can only hope to learn ⇡⇤ by identifying the bias " in the rewards. We can show that this requires number of samples that are not much smaller than collecting ⇥(1/"2 ln(1/ )) episodes with each of the (H/d)d policies in ⇧.
While the lower bound in Theorem 2 does not have a dependence on log(|⇧|). The simple observation that the contextual bandit problem can be seen as an instance of our setup where d = 1, implies that some dependence on log(|⇧|) is necessary based on standard contextual bandit lower bounds [Lattimore and Szepesvári, 2020]. However, getting a lower bound of the form ⌦(Hd log(|⇧|)) is 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 to a generative model.

heading: 6 Adaptive algorithms
text: In Section 4, the algorithm introduced benefits from the guarantee provided by Theorem 1, which is near optimal in the worst case as 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 to 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 a more favorable property.

heading: 6.1 Adaptivitity to the eigenspectrum
text: Our adaptive algorithm, presented in Algorithm 3 in Appendix D.3, is a policy search algorithm similar to Algorithm 1 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 a policy ⇡, it first estimates the expected rewards for the first 3d time steps. Then, AdaValEstimate computes the autoregression coefficients ↵k(b ), 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 ↵k(b ) are computed. Specifically, using := 2d4d p (8K3d log(6d|⇧|)/ )/n, the procedure AdaValEstimate computes the coefficients b by solving the optimization problem
b argmin 2Cd
dY
k=2
H 1X
h=0
| k| h
s.t. 1 = 1, | k|  1 for 2  k  d,
and
dX
k=1
( 1) k+1↵k( ) bRh k bRh  for d+ 1  h  3d.
The above modification to the computation of b allows our error propagation bound to adapt to , 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 are bounded away from 1. The policy e⇡, returned by Algorithm 3, thus enjoys the following adaptive performance guarantee. Theorem 3 (Adaptive upper bound). For a given 2 (0, 1), d-rank MDP, horizon H and a finite policy class ⇧, after collecting n episodes, Algorithm 3 returns a policy e⇡ that with probability at least 1 admits the following guarantee:
V e⇡ max ⇡2⇧ V ⇡ O
✓ dH2(16e)2d ·max
⇡02⇧
dY
k=2
⇣H 1X
j=0
| ⇡ 0 k | j ⌘2 r K3d log(6⇧d/ )
n
◆ ,
Proof of Theorem 3 follows along the lines of the proof of Theorem 1 where we replace the error propagation bound (in Lemma 3) by a similar bound that adapts to the eigenspectrum of the transition matrix T⇡ . We defer the proof details to appendix Appendix D.3. Note that for any | k|  1 and thus PH 1 h=0 | k| h  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 a low rank MDP problem in which the adaptive bound above could be much better than the worst case upper bound in Theorem 1. Corollary 1 (Well mixing MDP). Given 2 (0, 1), horizon H and a finite policy class ⇧. Let M be a d-rank MDP such that the second largest eigenvalue of the transition matrix T⇡ satisfies | ⇡2 |  1 for every policy ⇡ 2 ⇧. Then, after collecting n episodes, our adaptive algorithm returns a policy e⇡ that with probability at least 1 admits the following guarantee:
V e⇡ max ⇡2⇧
V ⇡ eO ⇣⇣K ⌘2d 1 p n ⌘ ,
where the eO hides polynomial factors of d,H, log(1/ ) and multiplicative constants.
We next show through a lower bound that the adaptive upper bound in Theorem 3 cannot be improved further. We defer the proof details to Appendix E.3. Theorem 4 (Adaptive lower bound). Let " 2 (0, 1/16), 2 (0, 1/2), d 4 and ( i)i2[d] 2 [0, 1]d satisfy
d2d . dY
i=1
1
1 i . exp(H) and
dX
i=1
1
1 i 
H
4 ln(4d) .
Then, there is a realizable policy class and a family of MDPs with rank at most ⇥(d), finite observation space, horizon H and two actions such that: For each i 2 [d], policy ⇡ and MDP M in this class, there is an eigenvalue of the induced transition matrix T⇡M in [ i/2, i]. Furthermore, any algorithm that returns, with probability at least 1 an "-optimal policy for any MDP in this family, has to collect at least
⌦
⇣ 1
"2dd
vuut dY
i=1
1
1 i log(1/2 )
⌘
episodes in expectation in 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 ⇧ 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 d 2 [H], we compute an optimal policy e⇡d assuming that the rank d⇤ = d. Then, for each d 2 [H], we estimate the value function for the policy e⇡d by drawing n/2H fresh trajectories using that policy. Finally, we return the policy e⇡ from the set {e⇡d}d2[H] with the highest estimated value. The returned policy e⇡ satisfies, with probability at least 1 ,
V e⇡ max ⇡2⇧
V ⇡ eO ⇣⇣H
d⇤
⌘2d⇤ r
(8K)3d⇤ log(|⇧|/ )
n
⌘ .
We defer full details of the analysis to the Appendix.

heading: 7 Conclusion
text: We presented a new analysis of reinforcement learning with rich observations in the agnostic setting, under the low rank MDP assumption. We gave both a 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 is 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.

heading: Acknowledgements
text: AS was an intern at Google Research, NYC for the duration of the work. KS acknowledges support 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-1815893, a Google Faculty Fellowship, an NSERC Discovery Grant, and a University of Waterloo startup grant.

Review summaries:
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.

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.

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.