Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection
Authors: Matteo Papini
Andrea Tirinzoni
Aldo Pacchiano
Marcello Restelli
Alessandro Lazaric
Matteo Pirotta
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
regret minimization
exploration
problem-dependent analysis
representation selection

Abstract: We study the role of the representation of state-action value functions in regret minimization in finite-horizon Markov Decision Processes (MDPs) with linear structure. We first derive a necessary condition on the representation, called universally spanning optimal features (UNISOFT), to achieve constant regret in any MDP with linear reward function. This result encompasses the well-known settings of low-rank MDPs and, more generally, zero inherent Bellman error (also known as the Bellman closure assumption). We then demonstrate that this condition is also sufficient for these classes of problems by deriving a constant regret bound for two optimistic algorithms (LSVI-UCB and ELEANOR). Finally, we propose an algorithm for representation selection and we prove that it achieves constant regret when one of the given representations, or a suitable combination of them, satisfies the UNISOFT condition.

Reinforcement Learning in Linear MDPs:
Constant Regret and Representation Selection
Matteo Papini Universitat Pompeu Fabra matteo. patteeoopppiii@uppt edu
Andrea Tirinzoni
INRIA Lille
andrea. iiarraa.trrizzoniinniii...
Aldo Pacchiano" Microsoft Research opacchiano@miiccoooff.ooo com
Marcello Restilli
Alessandro Lazaric
Politecnico di Milano
Facebook Al Research
lazaric@fb. com
Matteo Pirotta
Facebook Al Research
pirottaffb.com com
Abstract
We study the role of the representation of state-action value functions in regret minimization in finite-horizon Markov Decision Processes (MDPs) with linear structure. We first derive necessary condition on the representation, called universally spanning optimal features (UNISOFT), to achieve constant regret in any MDP with linear reward function. This result encompasses the well-known settings of low-rank MDPs and, more generally, zero inherent Bellman error (also known as the Bellman closure assumption). We then demonstrate that this condition also sufficient for these classes of problems by deriving constant regret bound for two optimistic algorithms (LSSVI-UC and ELEENNOR.. Finally, we propose an algorithm for representation selection and prove that it achieves constant regret when one the given representations, or a suitable combination them, satisfies the UNISOFT condition.
Introduction
The ability of an agent to learn an informative mapping from complex observations to a succinet representation is of the essential factors for the success of machine learning in fields such as computer vision, language modeling, and more broadly in deep learning [Bengio et al., 2013]. In supervised learning, it is well understood that "good" representation one that allows accurately fit any target function of interest (e.g., correctly classify a set of objects in an image). In Reinforcement Learning (RL), this concept more subtle, it can be applied different aspects of the problem, such as the optimal value function or the optimal policy. Furthermore, recent works have shown that realizability (e.g.. being able to represent the optimal value function) is not sufficient condition for solving an RL problem, as the sample complexity using realizable representations is exponential in the worst case [c.g.. Weisz al., 2021]. As such, desirable property "good" representation in RI. is to enable learning near-optimal policy with a polynomial sample complexity (or similarly sublinear regret bound).
Several works have focused on online learning - considering sample complexity or regret min- imization and identified sufficient assumptions for efficient learning. Standard examples
Work done while at Facebook Al Research.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

tabular Markov Decision Processes (MDPs) [e.g., Jaksch et al., 2010, Azar et al., 2012, 2017], low or zero inherent Bellman error [e.g., Jin al., 2020. Zanette et al., 2020b,a, Jin et al., 2021] and linear mixture MDPs [e.g., Yang and Wang. 2019, Ayoub et al., 2020, Zhang et al., 2021]. While, in these settings, the representation is provided as input to the algorithm, an alternative scenario is to learn such representations. In this case, research has focused either on the problem of online representation selection for regret minimization [e.g., Ortner et al., 2014, 2019, Lee et al., 2021] or, more recently, on the sample complexity of online representation learning [e.g., Du et al., 2019, Agarwal et al., 2020, Modi et al., 2. Refer to App. A for more details. While this literature has focused on finding a representation enabling learning near-optimal policy with sublinear regret polynomial sample complexity, there may be several of such "good" representations with significantly different learning performance and existing approaches one. Intuitively, we would like to find representations that require the minimum level of exploration to solve the task. For example, representations that would allow the algorithm to stop exploring after a finite time and play only optimal actions forever (i.e., achieving constant regret), if they exist. This aspect of representation learning was recently studied by Hao et al. [2020], Papini et al. [2021] in contextual linear bandits, where they showed that certain representations display non-trivial properties that enable much better learning performance. While it is well-known that properties such as dimensionality and norm of the features have an impact on the learning performance, Hao et al. [2020], Papini al. [2021] proved that it possible to achieve constant regret (i.e., not scaling with the number of learning steps) if a certain (necessary and sufficient) condition on the features associated with the optimal actions is satisfied. To the best of our knowledge, the impact of similar properties on RL algorithms and how to find such representations is largely unexplored.
not guaranteed to find the most efficient
Contributions. In this paper, we investigate the concept of "good" representations in the context of regret minimization in finite-horizon MDPs with linear structure. In particular, we consider the settings of zero inherent Bellman error (also referred to as Bellman closure) [Zanette al., 2020b] and low-rank structure [e.g., Jin et al., 2020]. Similarly to the bandit case [Hao et al., 2020, Papini al., 2021], we study the impact of representations on the learning process. Our contributions are both fundamental and algorithmic. 1) We provide necessary condition (called UNISOFT) for representation to enable constant regret in any problem with linear reward parametrization. Notably, this result encompasses MDPs with zero inherent Bellman error, and linear mixture MDPs with linearly parametrized rewards. Intuitively, the condition generalizes a similar condition for linear contextual bandits and it requires that the features observed along trajectories generated by the optimal actions provide information on the whole feature space (see Asm. 4). 2) We provide the first constant regrer bound for MDPs for both ELEANOR [Zanette et al., 2020b] and LSVI-UCH [Jin et al., 2020] when the UNISOFT condition is satisfied. As a consequence, we show that good representations are not only necessary but also sufficient for constant regret in MDPs with zero inherent Bellman error or low-rank assumptions. 3) We develop an algorithm, called LSVI-LEADER, for representation selection in low-rank MDPs. We prove that in low-rank MDPs, LSVI-LEADER suffers the regret of the best representation without knowing it in advance. Furthermore, LSVI-LEADER achieves constant regret even when only suitable combination of the representations satisfies the UNISOFT condition despite none of them being "good". This is indeed possible thanks to its ability to select a different representation for each stage, state, and action.
2 Preliminaries
We consider a time-inhomogeneon finite-horizon Markov decision process (MDP) M (S,A, H, (rr ) (px (p)) where S is the state space and A is the action space, H is the length of the episode, }rx} and (px) } are reward functions and state-transition probability mea- sures, and y is the initial state distribution. We denote by r a) the expected reward of pair (s, a) E S x A at stage h. We assume that S is a measurable space with a possibly infinite number of elements and A is finite set. A policy
(T...... TH) E II is a sequence of decision rules Th : S + A. For every h E [M] = [1,.... .....,, H} and (s, a) E S x A, we define the value functions
of policy π as
H
(s,s = (s + Ex
Σ Li=++
(s, (s,
where the expectation is over probability measures induced by the policy and the MDP over state- action sequences of length H h. Under certain regularity conditions [e.g.. Bertsekas and Shreve,

---

2004], there always exists an optimal policy ग² whose value functions are defined by V (s) (s) sup, V (s) and Q7 (s,a) == Q% (s, a) = sup,, (s. The optimal Bellman equation (and Bellman operator L,) at stage E [M] is defined as:
(s, La L (s, ( a) + E (s, max Q 1i+1('',
The value iteration algorithm (a.k.a. backward induction) computes Q" Q" by applying the Bellman equations starting from stage H down to 1, with + = by definition for any and т. The optimal policy simply the greedy policy w.n.t Q": T = argmax Q7 (s,().)) a).
In online learning, the agent interacts with an unknown MDP in a sequence of K episodes. At each episode kt the agent observes initial state s¹. it selects a policy Tk, it collects the samples observed along a trajectory obtained by executing Tg. it updates the policy, and reiterates over the next episode. We evaluate the performance of learning agent through the regret: R(K) := EkS (+t - (s
Linear Representation. When the state space is large or continuous, value functions are often described through a parametric representation. A standard approach is to use linear representations of the state-action function (s a) = Φn (s, a) On. where dh S x A Rd is time-inhomoogneous feature map and 0n E Id is an unknown parameter vector. 2 In this paper, we consider MDPs satisfying Bellman closure (i.e., zero Inherent Bellman Error) [Zanette et al., 2020b] or low-rank assumptions (e.g.. Yang and Wang, 2019, Jin et al., 2020].
Assumption (Bellman Closure). Define the set of bounded value function 2n = (Qu On E On Qn a) du (8, a) O0, v(s,a)) a)} and the associated parameter space On = {0, E Rdd [on(s, a) 0nl S D). An MDP has zero Inherent Bellman Error (IBE) if
Vh E [H].
inf 1Qu, 11 0. Qu+1EQr4 Q
sup
This definition implies that the optimal value function is realizable as Qi E Qn. Furthermore, the function space Q is closed under the Bellman operator, i.e., for all Q++1 E Q L, E Q.. Under this assumption, value- Ailleeiteration--e based algorithms are guaranteed to converge to the optimal policy in the limit of samples and iterations [Munos and Szepesvári, 2008]. In the context of regret minimization, Zanette et al. [2020b] proposed a model-free algorithm, called ELEANOR, that achieves sublinear regret under the Bellman closure assumption, but at the cost of computational intractability.' The design a tractable algorithm for regret minimization under low IBE assumption is still open question in the literature.
Assumption (Low-Rank MDP). Let θ₁ = R.d, then an MDP has low-rank structure if Ys, a, h,s an(s,a) = (s T) On, Pn(s'|s, (s, a) on (s, (n(s')
where 1hh : :S Rd. Then, for any policy x E II, 30g E Or such that Q7, a) = Φn(s, a) T) We
assume ||0n]]g < Vd. ll Je (ss))ssss))))))))) I Vdlluulo and ([on(s, a)ll I 1, for any s, a, h, and
function : S R.
This assumption is strictly stronger than Bellman closure [Zanette et al., 2020b] and it implies the value function of any policy is linear in the features. Furthermore, under Asm. sublinear regret is achievable using, e.g., LSVI-UCB [Jin et al., 2020], a tractable algorithm for low-rank MDPs. He al. [2020] have recently established a mrollem-depender logarithmic regret bound for LSVI-UCB under a strictly-positiv minimum gap. The minimum positive gap provides a natural measure of the difficulty of an MDP.
Assumption 3. The suboptimality gap of taking action a in state s at stage h is defined as:
An(s, a) = (s) (%
We assume the minimum positive gap Amin = min, o, (1 a) An (s, (s,a) > 03 is well defined and that the optimal action unique, i.e., argmax, (s, a))
for any E S, h E [H].
It is possible to extend the setting to different feature dimensions {dr,) )=
'ELEANOR works under the weaker assumption of low IBE. Jin et al. [2021] considered the more general case of low Bellman Eluder dimension. Their algorithm reduces to ELEANOR in the case of low IBE.
3

---

Algorithm
Problem- Dependenn Logarithmic
Constant with UNISOFT
Minimax
(setting)
(this work)
ELEANOR
D(vdHHT) (Zanette et al., 2020b]
dl 24
log!/2
d 12
N/A
Amin A
822 m A
(Bellman Closure)
(Thm. 8)
LSVI-UCB
Ō ((T [Jin et al., 2020]
0 d log2 (T))
d H Anin
log
a H
min
0. miin 27p
(low-ronk: MDPs)
[He ct al., 2020]
(Thm. 9)
((Vd=IT=T)
dR 22 Amin
Lower Bound
N/A
[Zhou et al., 2020, Remark 5.8]
[He et al., 2020]
Table I:
Regret comparisons of ELEANOR and LSVI-UCB, For ELEANOR, we consider the special case of Bellman closure.
In Tab. I, we summarize existing bounds in the two settings. Another structural assumption that has gained popularity in the literature the linear-mixture structure [Jia et al., 2020, Ayoub et al., 2020, Zhou et al., 2020], where the transition function admits form Pa (s'|s, a) = ( (s|ss, a) On. No structural requirement is made on the reward, which is typically assumed to be known. As a consequence, the value function may not be linearly representable. However, the fact the reward is known and that it is possible to directly learn the parameters 6₁ of the transition function allow to achieve sublinear regret (even logarithmic) through model-based algorithms. While in this paper mostly focus on Asm. and 2, in Sect. 3.1 we show that our condition is necessary for constant regret also for linear-mixture MDPs with unknown linear reward.
3 Constant Regret for Linear MDPs
In this section, we introduce UNISOFT, a necessary condition for constant regret in any MDP with linear rewards. We show that this condition is also sufficient in MDPs with Bellman closure. Assumption 4. A feature map is UNISOFT (Universally Spanning Optimal FeaTures) for an MDP if it satisfies Asm. 1 or 2, and for all h E [H] the following holds:
> o)} span Span(oi (i((s) Vs, (h(s) 0). > span (o a) V(s 37 11: (s,
where (T((s) = E[1 {sa- }} |M, m] is the occupancy measure of a policy pī(s,a) = Ph(s)1 [s](s) = a), (s) :- P% (s), and (s) == (1 (s)
Intuitively, features that are observed by only playing optimal actions must provide information on the whole space of reachable features at each stage h. We notice that Asm. 4 reduces to the HLS property for contextual bandits considered by Hao et al. [2020], Papini et al. [2021]. The key difference is that, in RL, the reachability of a state plays a fundamental role. For example, features of states that are not reachable by any policy are irrelevant, while features of optimal actions in states that are not reachable by the optimal policy (i.e., 66 (s) in state with P (s) 0) do not contribute to the span of optimal features since they can only be reached by acting sub-optimally. In RI., a related structural assumption to Asm. 4 is the "uniformly excited feature" assumption used by Abbasi- Yadkori et al. [2019, Asm. A4] for average reward problems. Their assumption is strictly stronger than ours since requires that all policies generate an occupancy measure under which the features span all directions uniformly well. Such an assumption can be related to the ergodicity assumption for tabular MDPs, which is known to be restrictive. Another related quantity is the "explorability" coefficient introduced by Zanette et al. [2020c]. This term represents how explorative (in the feature space) are the optimal policies of the tasks compatible with the MDP, i.e., considering any possible parameter 9, E θ₁, exploration where the objective is to learn a near optimal
This coefficient is important in reward policy for any task, which is revealed only once learning has completed. In our setting, we focus only on the properties of the optimal policy for the single task we aim to solve.
It is interesting to look into Asm. 4 from an alternative perspective. Denote by 0 S An.1 .... ... An the eigenvalues of the matrix A := E.-ry [ (z) [s) and by X min > 0, E [d] the minimum positive eigenvalue. We notice that when the features non-redundant (i.e., (s,

---

spans ID) and the UNISOFT assumption holds, then X = A1,1 > 0. As we will see, the minimum positive eigenvalue X plays fundamental role in the constant regret bound, together with the minimum gap min- We provide examples of UNISOFT and Non-UNISOFT representations in App. G, as well as their impact on the learning process.
=
3.1 UNISOFT is Necessary for Constant Regret
The following theorem shows that the UNISOFT condition is necessary to achieve constant regret in large class of MDPs.
Theorem 5. Let M be any MDP with finite states, arbitrary dynamics p. linear rewards (i.e., (x = ob (x, a)T (n) with Gaussian (0, 1) noise, unique optimal policy x², and where condition UNISOFT (Asm. 4) is not satisfied. Let M be the set of MDPs with same dynamics as M but different reward parameters {0n heem. Then, there exists no algorithm that suffers sub-linear regret in all MDPs in M while suffering constant regret in M.
Thm. 5 states that in MDPs with linear reward, the UNISOFT condition is necessary to achieve constant regret for any "provably efficient" algorithm. Notably, this result does not put any restriction on the transition model, which can be arbitrary and known. This means that as soon the reward is linear and unknown to the learning agent, the UNISOFT condition is necessary to attain constant regret. This result applies to low-rank MDPs, finear-mixture MDPs with unknown linear rewards, and MDPs with Bellman closure (Bellman closure implies linear rewards, see Prop. 2 by Zanette et al. [2020b]).
Proof sketch of Theorem 5. The key intuition behind the proof is that an algorithm achieving a constant regret must select sub-optimal actions only finite number of times. Nonetheless, in order to learn the optimal policy, all features associated with suboptimal actions should be explored enough. Since UNISOFT does not hold, this cannot happen by executing the optimal policy alone and requires selecting suboptimal policies for long enough, thus preventing constant regret.
More formally, we call an algorithm "provably efficient" if it suffers sub-linear regret on the given class of MDPs M. Formally, we use the following definition, which is standard prove problem- dependent lower bounds [e.g., Simchowitz and Jamieson, 2019, Xu et al., 2021].
Definition (a-consistency). Let a E (0, 1), then an algorithm A is a-consistent on class of MDPs M if. for each M E MM and K 2 1, there exists constant CM (independent from K) such that EA [R(K)) S KM.4
The following lemma is the key result for proving Thm. and it might be of independent interest. It shows that any consistent algorithm must explore sufficiently all relevant directions in the feature space to discriminate any sub-opti sub-optimal policy from the optimal one. The proof (reported in App. C) leverages techniques for deriving asymptotic lower bounds for linear contextual bandits [e.g.. Lattimore and Szepesvari, 2017, Hao et al., 2020, Tirinzoni et al., 2020].
Lemma 7. Let M. be as in Thm. 5 and A be any a-consistent algorithm on M. For any π E II, denote by V. : Es,a 0% (s, a) jo a) its expected features stage h and A A(T) V1 V/2 its sub-optimality gap. Then, for any 11 with ((TT) > O and [H].
A(T)²
sum (o))
K-000
2 a)
where 1 = " and A/K Dk (s on (s Tt)T.
We now proceed by contradiction: suppose that A suffers constant expected regret on M even though the MDP does not satisfy the UNISOFT condition. Then, since plays sub-optimal actions only finite number of times, it is possible to show that, for each h E [H], there exists positive constant AM > 0
such that EA, [A]] < A + AM where A = K KΣ s:pp $1, (s)o (s)T. Furthermore, since UNISOFT does not hold, there exists stage h E [M] and sub-optimal policy æ (i.e., with A 0)
"In practice, all existing antovably-efficieen algorithms we are interested in are included in this class and cM is polynomial all problem-dependent quantities (e.g.. d, H). For instance, LSVI-UCB and ELEANOR are 1/2-consistent on the class of low-rank and Bellman-closure MDPs, where they enjoy worst-case Ō(v K) regret bounds (with cM being O(v and H*) respectively).
5

---

such that the vector 7 - V does not belong to span (0% (s) (s) > 0}. Then, since such space is exactly the one spanned by all the eigenvectors of A associated with non-zero eigenvalue, there exists positive constant e (independent of K) such that 4 Villaa +A 2 //M--
+A
Combining these steps with Lem. 7, we obtain
( 2(1 a)
lim Simpuplogh (ogssppoo))]] M [ +n
lim supplg(()) (K): K
K-o
AM
which clearly a contradiction. Therefore, A cannot suffer constant regret in M while suffering sub-linear regret in all other MDPs in M, and our claim follows.
3.2 UNISOFT is Sufficient for Constant Regret
While the UNISOFT condition is necessary for achieving constant regret in a large class of MDPs, in the following, we prove that ELEANOR and LSVI-UCB attain constant regret when the UNISOFT assumption holds, thus implying that it is sufficient condition MDPs with low-rank and Bellman closure structure.
Theorem 8. Consider an MDP and a representation {Øn heea satisfying the Bellman closure (Asm. 1) and UNISOFT assumptions (Asm. 4). Under Asm, 3, with probability at least 1 36, ELEANOR suffers a constant regret
R(K) S H log 8
where HR and is the last episode ELEANOR suffers non-zero regret. Furthermore, S max F
dif 16 where X4 == min; { > O.
Alternatively, we can prove the following result for LSVI-UCB.
Theorem 9. Consider an MDP and representation {or heeW satisfying the low-rank (Asm. 2) and UNISOFT assumptions (Asm. 4). Under Asm. 3, with probability - 35, LSVI-UCB suffers constant regret
R(K) & H
log (dH2R/0).
Amin
where is the last episode LSVI-UCB suffers non-zero regret and is upper-bounded as where X4 := ming (X, > O.
max d²z
A X
In both cases, is polynomial in all the -ebeededde terms and independent of the number of episodes K (see Lem. 21 and 20). As a result, ELEANOR and LSVI-UCB achieves a constant regret that only depends on "static" MDP and representation characteristics, thus indicating that after a finite time the agent only executes the optimal policy. Notice also that the bounds should be read as minimum between the constant regret and the minimax regret O(V which may be tighter for small K. The main difference between the two previous bounds is that for ELEANÓR we build on the anytime minimax regret bound, while for LSVI-UCB, we derive a more refined constant-regret guarantee by building on its problem-dependent bound of He et al. [2020]. Unfortunately. limiting factor for applying the analysis in [He et al., 2020] seems to be the fact that ELEANOR is not optimistic at each stage f but rather only at the first stage. As such, whether ELEANOR can achieve problem-dependent logarithmic regret based on local gaps that can be leverage to improve our analysis an open question the literature.
Combined proof sketch of Thm. 8 and Thm. 9. We provide general proof sketch that can be instantiated to both ELEANOR and I.VV-UUC. The purpose to illustrate what properties an algorithm must have to exploit good representations, and how this leads to constant regret. Consider a learnable feature map {Øn ] and an algorithm with the following propertics:
(a) Greedy w.r.t. Q-function estimate: +)(s)) arg max (Q" (s, a)}.
'ELEANOR and L.SVI-UCB are defined up to regularization parameter À that we set to " 'Here < hides logarithmic terms in X+, H. and d, but not in K.

---

(b) Global optimism: (s) 2 (s) where, for all 1, we set (i()) max EA (s, a)}.
(c) Almost local optimism: vh > 1, 3Ch 2 S.t. (x a) + CnBr [ (n)ss, a)n Q7 a).
(d) Confidence set: let A = (8), a Jon (sh+ ) + XI and Br E R be logarithmic in
then (( V (s - 23 | a ( (1a))) + IE (e (
V (+)
V (
These properties are verified by ELEANOR [Zanette et al., 2020b, App. CJ and LSVI-UCB [Jin et al., 2020, Lem. B.4, B.5]. Note that for LSVI-UCB condition (c) is trivially verified since the algorithm is optimistic at each stage (Cn, = 0). On the other hand, ELEANOR is only guaranteed to be optimistic at the first stage, and (c) is thus important (C)- 2). First, to establish an any-time regret bound, either worst-case or problem-dependent, We call this g(k) and prove that R(k) I g(k) S (Vk)) for any A with probability 26.
existing techniques
Next, we show that, under Asm. 4, the eigenvalues of the design matrix grow almost linearly, making the confidence intervals decrease at 1/ Vk rate. From some algebra and a martingale argument,
A-1 = KΛд + AI Amin (k) Ö(Vk),
(2)
where A₁ = T (+) (8) (.) The UNISOFT property ensures that the linear term is nonzero in relevant directions, while the regret bound of the algorithm makes the penalty term sublinear. Then, we show that, for any reachable (s,a),
k -- Ō(Vk) (KY) - ((VK))3/2
Bx (llnn(s, (1) SB
Ö(k-
(3)
where X is the minimum nonzero eigenvalue of AA- From (3), see that X plays fun- damental role in the rate decrease. Finally, we show that, under the gap assumption, these uniformly-decreasing confidence intervals allow learning the optimal policy in finite time. From the Bellman equations, we have that
H1 Σ 1=1
( VI (5
Exe
An(sh, a8) ot )
(4)
while from (a)-(d), for any reachable state,
(s (s)) s 2
Σ Ba (sor(s al)) (sh
+ Ia 11 (17
The second term (with 1A>1) accounts for the almost-optimism of ELEANOR. while it is zero in LSVI-UCB due to the stage-wise optimism. Then, for every E [H]. we can use (3) to control the feature norms. Thus, there exists episode K4, independent of K satisfying
Kh 8 log 2dm 11/0) g(kh)
An(s, (n (s)) S 3m (2+ (2+1==h>Ch)) (KR 8 / log (ddn,, H/8) ((rr)))3/2
Amin+
(5)
By definition of minimum gap, then (x = 0 for k> Kh. Then, for k: > R m=xx (NA J. (**) V (s+) = 0. But this means the algorithm only accumulates regret up
that is,
R(K)= R(x) (z) 0(1) for all K > R. This holds with probability
35, also taking into
account the martingale argument from (2). Note that {NA) by definition monotone for LSVI-UCB. The final bounds are then obtained by instantiating the specific values of 3g and g(k) for the two algorithms analyzed.
Representation Selection in Low-Rank MDPs
In Sec. 3, we have highlighted the benefits that UNISOFT representation brings to optimistic algorithms MDPs with Bellman closure and low rank structure. this section, we take one step further and investigate the representation selection problem. Since ELEANOR is a computationally
7

---

Algorithm 1: LSVI-LEADER
Input: Representations (2: [e)] confidence values (3x [a(]K]
for L,...; K
Receive the initial state of for h ..... do
AEG) M Einr (
and Vi
wh(() = ANG) Ei=1 (1) (sh,
(a of max Q (a Vi [N]
(s) = min
H, Himinge ( (s,a) 3 |oh 0011
for h I..... H do Execute action of (shh) =- argmax as)..a) a)
intractable algorithm, we build on LSVI-UCB and low-rank MDPs (Asm. 2) and we introduce LSVI-LEADER (Alg. 1), an algorithm that adaptively selects representations in given set.
Given a set of N representations {ΦA}EE[N] satisfying Asm. 2, where & =10 hel#a each stage h E [H] of episode & E [K], LSVI-LEADER solves N different regression problems to compute an optimistic value function for each representation. Then, the final estimate (s, a) is taken as the minimum across these different optimistic value functions. Notably, this implies that LSVI-LEADER implicitly combines representations, in the sense that the selected representations (i.e., those with tightest optimism) might vary for different stages. This is exploited in the following result, which shows that constant regret is achievable even none of the given representations globally UNISOFT.
Theorem 10. Given an MDP M and a set of representations [ satisfying the low-rank assumption (Asm. 2), let Z be the set of H representations obtained by combining those in (R)bEiN) across different stages.' Then, with probability at least 1 26, LSVI-LEADER suffers at most a regret
R(K) min R(K, (Bx3), sE2
where R(K, z, 32) is either the worst-case regret bound of LSVI-UCB [Jin et al., 2020] or the muablem-dependen one [He et al., 2020] when the algorithm is executed with representation and confidence values 3x x dH /Nlogg2 (2dg Hk/5). Moreover, if Z contains UNISOFT representation 2", then LSVI-LEADER achieves constant regret with problem-dependent values of 2" (see Thm. 9).
This result shows that LSVI-LEADER adapts the best representation automatically, i.c., without any prior knowledge about the properties of the representations. In particular, it shows a problem- dependent (or worst-case) bound when there is no UNISOFT representation, while it attains constant regret when representation, potentially mixed through stages, is UNISOFT. This is similar to what was obtained by Papini al. [2021] for linear contextual bandits. Indeed, LSVI-LEADER reduces to their algorithm in the case H = 1. While the cost of representation selection is only logarithmic in linear bandits, the cost becomes polynomial (i.e., VN in the worst-case bound and N in the problem-dependent one) in RL. This due to the structure induced by the Bellman equation, which requires a cover argument over N functions (more details in the proof sketch). Note that for H = 1, the analysis can be refined to obtain a log(N) dependence, due to the lack propagation through stages, and recover the result in [Papini et al., 2021]. We refer the read to App. G for numerical validation.
Proof sketch of Thm. 10. The proof relies the following important result, which extends Lem. B.4 of Jin et al. [2020] and shows that the deviation between the optimistic value function computed by LSVI-LEADER and the true one scales with the minimum confidence interval across the different representations. Formally, with probability 1 - 26, for any π E II, s E S,a E A, E
"Note that any combination of features in Φ is learnable, since each representation is learnable in the low-rank MDP sense.

---

[ [ - (s) s 23, min as)
1o (AA + (s.))((s
( (
JE[N]
As in [Jin al., 2020], the derivation of this result combines the well-known self-normalized martingale bound in [Abbasi- Yabkoii-Yakkori et al., 2011] with a covering argument over the space of possible optimistic value functions. In our setting. the structure of such function space requires us to build N different covers, one for each different representation. This, in turn, requires the confidence values 3y to be inflated by an extra factor V w.r.t. learning with single representation.
The generality of this result allows worst-case regret bound of Jin et al. [2020] and the cooblem-dependent one of He et al. [2020]. To this, note that the regret decompositions in both of these two papers rely on an upper bound to (**) V (s%) as a function of the fixed representation used by LSVI-UCB (see the proof of Theorem 3.1 of Jin al. [2020] and Lemma 6.2 of He et al. [2020]). Then, fix any E and call 2/, JE[[M-- Moreover, by definition of low-rank structure, since each $ induces low-rank MDP, their combination does too. Thus, z is learnable. Then, instantiating the concentration bound stated above for policy x², state sy. action o stage h, and by upper bounding the minimum with the representation selected in Zh, we get
easily derive, for any fixed representation
Z, both the
its features at stage h. Note that 2/ E (o0h)
(s VITA ( < 23 || (sh, a (ll0 + (x
Vi+i(s') - V (s))
From here, one can carry out exactly the same proofs of Jin et al. [2020] and He et al. [2020], thus obtaining the same regret bound that LSVI-UCB enjoys when executed with the fixed representation E Z and confidence values { ke|K]. Hence, conclude that the regret of LSVI-LEADER is upper bounded by the minimum of these regret bounds for all representations & E Z, thus proving the first result. To obtain the second result, simply notice that, if 2* E Z is UNISOFT, then we can use the refined analysis for LSVI-UCB of Thm. 9 to show that R(K, 2", (333) is upper bounded by a constant independent of K, hence proving constant regret for LSVI-LEADER.
4.1 Representation Selection under a Mixing Condition
We show that the LSVI-LEADER algorithm not only is able to select the best representation among set of viable representations, and to combine representations for the different stages, but also stitch representations together across states and actions. With this in mind we introduce the notion of mixed ensemble representations.
Definition 11. Consider MDP M and a set of representations { JEEN satisfying the low- rank assumption (Asm. 2). The collection of feature maps ( is UNISOFT-min if for all s, E S x And h E [H]. there exists j such that ( span of (s))) o).
We show that when presented with UNISOFT-mixing family of representations, LSVI-LEADER is able to successfully combine these and obtain a regret guarantee that may be better than what is achievable by running LSVI-UCB using any of these representations in isolation.
Theorem 12. Consider MDP M and set of representations { (DiJEEN] satisfying the low- rank (Asm. 2) and UNISOFT-mixin assumptions. If Amin > 0 (Asm. 3), then with probubility at least 36, there exist constant K maax, [ independent from K such that the regret of LSVI-LEADER after K episodes is at most:
R(K) S min R(F, (3+)),
ZE2
where Z, and 3g are defined as in Thm. 10.
Under the UNISOFT- representation for each stage h but rather to mixing multiple representations. In fact, it may select different representation in different regions of the state- icatinaction space. This is the main difference w.r.t Thm. 10, where constant regret is shown when there exists a representation =* that is UNISOFT, and the value depends on the minimum positive eigenvalue of =f,- In the case of UNISOFT-mixing depends on properties of a combination of representations at stage h. We provide characterization of R4 in the full proof in App. E.
condition, LSVI-LEADER may not converge to selecting a single

---

Conclusions
We investigated the properties that make a representation efficient for online learning MDPs with Bellman closure. We introduced UNISOFT, a necessary and sufficient condition to achieve constant regret bound in this class of MDPs. We demonstrate that existing optimistic algorithms are able to adapt to the structure of the problem and achieve constant regret. Furthermore, we introduce an algorithm able to achieve constant regret by mixing representations across states, actions and stages in the case of low-rank MDPs. An interesting direction raised by our paper is whether it is representation learning, rather than
possible to leverage the UNISOFT structure for probably selection. Another direction can be to leverage these insights to drive the design of auxiliary losses for representation learning, for example deep RL.
References
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, pages 2312-2320, 2011.
Yasin Abbasi- Yadkori, Peter I.. Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvári, and Gellért Weisz. POLITEX: regret bounds for policy iteration using expert prediction. In JCMI, volume 97
of Proceedings of Machine Learning Research, pages 3692-3702. PMLR, 2019.
Alekh Agarwal, Sham M. Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: structural complexity and representation learning of low rank mdps. In NeurlPS, 2020.
Alex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In /CML, volume 119 of Proceedings of Machine Learning Research, pages 464. PMLR, 2020.
Mohammad Gheshlaghi Azar, Rémi Munos, and Bert Kappen. On the sample complexity of reinforcement learning with a generative model. In ICML. icml.ce / Omnipress, 2012.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In ICML, volume 70 of Proceedings of Machine Learning Research, pages 263-272. PMLR, 2017.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Trans. Pattern Anal. Mach. Intell., 35(8):1798 1828, August 2013. ISSN 0162-8828. doi: 10. 0..109//PAM1.2013.500 URL : /tttt::://ooioor/////// 1109/TPAMI 2013.50. 50.
Dimitir P Bertsekas and Steven Shreve. Stochastic optimal control: the discrete-time case. 2004.
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.
Simon S. Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudík, and John Langford. Provably efficient RL with rich observations via latent state decoding. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 1665-1674. PMLR, 2019.
Botao Hao, Tor Lattimore, and Csaba Szepesvári. Adaptive exploration in linear contextual bandit. In AISTATS, volume 108 of Proceedings of Machine Learning Research, pages 3536-3545. PMLR, 2020.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. CoRR, abs/201 1556,, 2020.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. J. Mach. Learn. Res., 11:1563-1600, 2010.
Zeyu Jia, Lin Yang, Csaba Szepesvári, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. L4DC, volume 120 of Proceedings of Machine Learning Research, pages 666-686. PMLR, 2020.
10

---

Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. COLT, volume 125 of Proceedings of Machine Learning Research, pages 2137-2143. PMLR, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. CoRR, abs/2102.00815. 2021.
Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite-armed linear bandits. In Artificial Intellignnce and Statistics, pages 728-737. PMLR, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Jonathan N. Lee, Aldo Pacchiano, Vidya Muthukumar, Weihao Kong, and Emma Brunskill. Online model selection for reinforcement learning with function approximation. In AISTATS, volume 130 of Proceedings of Machine Learning Research, pages
PMLR, 2021.
Rui Lu, Gao Huang, and Simon S. Du. On the power of multitask representation learning in linear MDP. CoRR, 0t/p22000008053, 2021.
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pages 1928-1937. JMLR.org, 2016.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. CoRR, abs/2102.07035, 2021.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. J. Mach. Learn. Res., 9:815-857, 2008
Ronald Ortner, Odalric-Ambyyn Maillard, and Daniil Ryabko. Selecting near-optimal approximate state representations in reinforcement learning. In ALT, volume 8776 of Lecture Notes in Computer Science, pages 140-154. Springer, 2014.
Ronald Ortner, Matteo Pirotta, Alessandro Lazaric, Ronan Fruit, and Odalric-Ambrym Maillard. Regret bounds for learning state representations in reinforcement learning. In NeurIPS, pages 12717-12727, 2019.
Mattco Papini, Andrea Tirinzoni, Marcello Restelli, Alessandro Lazaric, and Mattco Pirotta. Leverag- ing good representations in linear contextual bandits. CoRR, abs/2104.03781, 2021.
Antonin Raffin. RI baselines3 zoo.
htt.://.....ooo/aaa/////aaaaaaaa zo0, 2020.
Antonin Raffin, Ashley Hill, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, and Noah httpittub..cmm/DRRR///ttaaaallaa
Dormann. Stable baselines3.
2019.
Max Simchowitz and Kevin G. Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In NeurlPS, pages 1151-1160, 2019.
Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. Advances in Neural Information Processing Systems, 33, 2020.
Joel A. Tropp. User-frient User-friendly tail bounds for sums of random matrices. Found. Comput. Math., 12(4): 389-434, 2012.
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with realiallee optimal action-value functions. In ALT, volume 132 of Proceedings of Machine Learning Research, pages 1237-1264. PMLR, 2021.
Haike Xu, Tengyu Ma, and Simon S. Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. CORR, abs/2102.04692. 2021.
Lin F. Yang and Mengdi Wang. Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. CoRR, abs/1905. 10389, 2019.

---

Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized squares value iteration. In AISTATS, volume 108 of Proceedings of Machine Learning Research, pages 1954-1964. PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel J. Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 10978-10989, PMLR, 2020b.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. In NeurIPS, 2020c.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S. Du. Variance-aware confidence set: Variance- dependent bound for linear bandits and horizon-free bound for linear mixture MDP. CoRR, abs/2101.127455, 2021.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvári. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. CoRR, abs/2012.08507,, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See conclusions (Sec. 5).
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Due to its theoretical nature, we see no ethical or immediate societal consequence of our work
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results....
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [No] We perform simple numerical simulations to support our theoretical findings. The provided pseudo- code and experimental protocol is sufficient to reproduce our results.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A] See answer 3.(a)
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' roe're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
12

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "wbqr6MCTBJ9", "reviewer": "Reviewer_WqxU", "summary": "The paper investigates the necessary and sufficient properties required by the state-action representation in an MDP which lead to a constant regret in the online learning setting. Building up on the recent results on 'good' representations in stochastic linear bandits, the authors present a nice extension of the results to the MDP setting in the low inherent Bellman error and low-rank MDP case.\nIt is shown that the UniSOFt condition, that the features of any reachable state in the given MDP are spanned by the features of states reachable by the optimal policy, is necessary and sufficient for achieving constant regret. In addition to the unisoft condition, the authors also need to make a minimum gap assumption between the Q* values of optimal vs sub-optimal actions. For the sufficiency result, modifications of the analysis of LSVI-UCB and ELEANOR are shown to exhibit constant regret under the two assumptions. Lastly, the authors also show that if there are multiple admissible features available to the agent, the algorithm LSVI-LEADER can utilize the unisoft property if present in any of the candidates or is mixed across the candidate features.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is nicely written and presents a clean and thorough analysis. The work strongly builds upon the recent results by Papini et al on constant regret and representation selection in stochastic linear bandits wherein a full-rank assumption is used on the context distribution's covariance under the optimal policy. In this paper, firstly the assumption is distilled down to a spanning assumption on any feature reachable in the given MDP and is further indexed by the set of all policies to account for the time dependence. The main challenge in the analysis is to account for the episodic structure of the MDP with multiple timesteps which now depends more on the chosen policies instead of the one-step nature of the bandit problem. Other than that, the techniques are quite \n\nThe key representation property that the paper studies is the property that the features of any state reachable by any policy in the given MDP lie in the subspace spanned by the features seen via the optimal policy. When using this assumption with a minimum gap assumption, it is shown that the no algorithm can guarantee sub-linear regret on a family of MDPs and incur only constant regret on the given instance unless the UNISOFT condition is satisfied. The MDPs in the family all have the same transition dynamics but have different reward parameters. The proof uses a careful analysis of the properties of the feature covariance matrix and expected feature vector for the agent's sequence of policies and the optimal policy and relates it with the value gap of a policy wrt the optimal policy. Using the minimum gap assumption, it is then shown that the constant regret assumption for a given MDP can be used to upper bound the eigenvalues of the expected feature matrix seen by the agent over any $K$ episodes. However, for the results to go through, the authors need to assume that the state space is finite. This is not mentioned in the main text and seems quite important for the narrative of the paper.\n\nThe sufficiency results for LSVI-UCB and ELEANOR are quite easy to follow and are discussed well in the paper. In my run through, I couldn't find any errors in the derivations. However, one major aspect which is missing in the paper is a thorough discussion of the nature of the regret bounds which one might get with these assumptions. The UNISOFT assumption if taken into context for any tabular MDP is essentially saying that the constant regret result can be shown when the optimal policy visits each state with a minimum probability and the achievable regret would depend on the minimum visitation probability over all states ($\\lambda^+$). Now, though this regret bound doesn't depend on the number of episodes and is thus constant in the MDP parameters, it feels a bit unsatisfactory as this can be exponentially large in the horizon of the MDP. If one is willing to account for such exponential dependencies, it is important to explicitly describe the nature of each term appearing in the regret bound. The authors do mention that for smaller values of $K$, the usual $O(\\sqrt{K})$ regret bounds might be much tighter but I think a discussion about this would be extremely important. Also, the finiteness of the state space is also something which needs to be discussed in this context as the necessity result only applies with that assumption.\n\nRepresentation selection: As mentioned before, with the analysis of the previous theorems in the paper, the selection result is quite easy to follow. I feel that the mixing condition should be discussed more in detail with theorem 10 being a short note as the dependence of $\\tilde{\\kappa}$ is a bit more subtle when compared to the simpler selection result. \n\nConcluding: Noting the details about finiteness of the state space, dependence on MDP parameters and the clarity of the result in the selection section, I'll give a weak accept rating to this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is primarily a theoretical one and therefore doesn't have any immediate societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "nUh4YRgjQE7", "reviewer": "Reviewer_tEY1", "summary": "The authors study the constant regret bound in low-rank MDP setting [Jin et al., 2020] and zero inherent Bellman error setting [Zanette et al., 2020b]. On the upper bound side, this paper shows that ELEANOR and LSVI-UCB have constant regret bounds under the gap assumption (assumption 3) and UNISOFT assumption (assumption 4) respectively. On the lower bound side, UNISOFT is shown to be a necessary assumption for the constant regret. In addition, given a set of good representations $\\Phi$, the new proposed LSVI-LEADER algorithm suffers a constant regret which scales with $|\\Phi|$.", "questions": "", "limitations": "", "rating": 5, "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": "The main motivation and contribution of this work is to extend the constant regret bounds (Hao et al. [2020], Papini et al. [2021]) to the MDP settings. I believe the question is interesting and the results are new to me. The paper has a good structure and is easy to follow. The proof looks good from a quick overview. I have some detailed comments as below:\n\n1.\tThe constant regret bounds are quite interesting results. The intuition is the algorithm will learn a lot each time when it makes an error due to the gap assumption. So eventually the algorithm could learn the environment accurately enough to obtain a near-optimal policy. Again, by the gap assumption, this near-optimal policy would be the optimal policy.\n2.\tFor the representation selection part, though the regret bounds are constant, I wouldn’t say they are desired. Since the feature class could be quite large and exponential in general, we usually only want a polylog($|\\Phi|$) bound. However, the cost in this paper would be $|\\sqrt \\Phi|$.\n3.\tThe LSVI-LEADER doesn’t seem to be computationally efficient since it enumerates the whole feature class, and the optimization problem for finding min over $\\phi\\in\\Phi$ for the $\\overline Q$ seems to be hard. I suggest the authors to add related discussions in the subsequent version.\n4.\tIn the representation selection part, only low-rank MDPs are investigated, and the reason mentioned in the paper is that the authors want to focus on the computationally tractable algorithm LSVI-UCB. However, as discussed in the last bullet, the LSVI-LEADER doesn’t appear to be computationally efficient as well. Therefore, I think this argument is not very convincing to me. Have you thought about representation selection extension for ELEANOR? If so, what is the difficulty?\n5.\tThis paper only focuses on the exact realizable case, but the original LSVI-UCB and ELEANOR can both handle approximate setting. Do the constant regret bounds also hold for the approximately case?\n6.\tMaybe I’m missing something, can the authors explain why span(u_i) = span(\\phi_j) in Line 857?\n7.\tIn line 23, the discussion about realizability is not very clear. The exponential sample complexity refers to the exponential blow up in the approximation error. However, in the exact realizable case, we will not suffer from the exponential sample complexity or regret bounds. If you allow an additive term to be sqrt d larger than the approximation error, then actually poly results are achievable.\n8.\tLine 110, “it implies the realizability of any value function” is not very clear. I think the point here is for any value function, its Bellman backup is linear in the feature. \n9.\tI find the term learnability/learnable quite confusing. In the footnote on page 1, learnable representation broadly refers to the representation where finding near-optimal policy is a learnable problem. However, it might let people think the representation is able to be learnt by the algorithm. \n10.\tThe constant $c_M$ in line 182 is not clear. It would be better to mention what parameters are treated as constant and included in $c_M$.\n11.\tLine 327 . is missing before “With”.\n\n\nPost rebuttal:\nThanks the authors for addressing my questions.\n\nAfter the long discussions and reading other reviews, I intend to degrade my score to 5.\n\nI appreciate the constant regret result in the known feature case. The Unisoft assumption seems to be reasonable because the authors provide a necessary result.\n\nI also have several major concerns about this paper. (i) This paper makes an assumption that the optimal policy is unique (as acknowledged by the authors). And this assumption is much stronger than the gap assumption. (ii) The constant regret bound hides many crucial factors. For example, the factor could be exponentially small, which makes the constant regret bound exponentially large. I'm not that satisfied with the constant bound if it scales exponential with standard parameters. I think to get a meaningful polynomial constant regret bound, the authors need to make additional assumptions. (iii) Similar as (ii), the constant regret bound in feature selection case scales polynomial with the number of features, while we usually just want to pay log in this factor. In this sense, I don't feel the algorithm is doing \"representation selection\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "Rv6-xQs4d4F", "reviewer": "Reviewer_aaaf", "summary": "The authors study representation learning on either MDPs with low Bellman error or low-rank MDPs in this paper. They prove that a condition on the representation feature called UNISOFT is both necessary and sufficient for the algorithm to achieve a constant regret. They also show that a newly proposed LSVI-LEADER algorithm is able to pick up the best or mixed-best features from candidates with provable sample complexity guarantee. Finally, they prove that under the UNISOFT condition, LSVI-LEADER is able to achieve a constant regret, just as the vanilla RL setting. ", "questions": "", "limitations": "", "rating": 5, "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": "To my best knowledge, this is the first work that studies the regret guarantee for representation learning. The UNISOFT condition is a nice extension of a similar condition in linear bandits literature. However, I still have some comments and questions about the current version of this work, and I hope the authors can reply to me in detail. \n\nIn line 38, you say that previous works [Du et al., 2019, Agarwal et al., 2020, Modi et al., 2021] only study the learnable representations and do not study their sample complexity or regret. That really confuses me since Modi et al. clearly stated the sample complexity for their algorithm to find a near-optimal value function or policy (See their Theorem 3 or Corollary 4). Besides, since both Modi et al. and this work focus on the low-rank MDP setting and they all have sample complexity or regret guarantee, I think it is natural to ask which result is better by considering either their assumptions or complexity guarantee. I may not be able to tell whether the contribution of this work is significant without a detailed comparison between this work and Modi et al.\n\n\nIn Theorem 10, you imply that LSVI-LEADER suffers a regret that depends on the confidence value $\\beta_k \\sim O(\\sqrt{N})$, where $N$ is the number of the representation candidates. Since the final regret depends on $\\beta_k$ polynomially, it then indicates that the regret of LSVI-LEADER also depends on $N$ polynomially. That seems like a much worse dependence on $N$ compared with that in Modi et al., where the dependence is only logarithmic. Besides, it seems that such a regret in Theorem 10 can also be achieved by considering the following vanilla algorithm: we first compute $\\tilde R(K, z, \\beta_k)$ for each $z \\in Z$, then we pick up the $z$ with the smallest $\\tilde R(K, z, \\beta_k)$ and run LSVI-UCB on it for $K$ episodes. If that is true, then what is the point for us to use LSVI-LEADER if we want to minimize the regret?\n\nMeanwhile, it is hard to judge the technical contribution of this work. It seems that the tools in this work to analyze the performance of ELEANOR or LSVI-UCB are quite standard, and most of them are from previous Zanette et al., Jin et al., and He et al.. The most marvelous technical contribution part is the proposed UNISOFT condition, while itself also originates from the previous linear bandits work. I do not want to criticize its originality, since maybe for this specific problem, the adopted approach, although standard, is the only available approach. However, I truly want to see the technical challenges you faced when you solve this problem, since they are crucial especially for a pure theoretical paper. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They discussed the limitations. I do not see any negative societal impact on this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this work, the authors theoretically study representation learning on MDPs with low Bellman error and low-rank MDPs. The main concerns from the reviewers are about the polynomial dependence on $N$ in the main results and the lack of detailed comparisons with the existing works. We suggest that the authors can further improve their theoretical analysis and add more detailed discussions in their next version.  
Decision: Accept (Poster)