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 P% (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 θ₁, This coefficient is important in reward wwward-freede exploration where the objective is to learn a near optimal 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 (a) 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(]
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": "_gp6kuKqP4P", "reviewer": "Reviewer_rJnu", "summary": "This paper studies representation learning in reinforcement learning. The authors prove that the proposed UNI-SOFT assumption is sufficient and necessary for achieving the constant regret bound for a single representation. The authors also propose an algorithm to select the representation to achieve the constant regret bound when any single representation cannot achieve this.", "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 paper is overall well organized and easy to follow. Despite the aforementioned contributions, there're still several drawbacks in this paper. \n\nFirst, given the previous logarithmic regret bound given by [He et. al, 2020] and the constant regret bound for linear contextual bandit given by [Papini et. al, 2021], the constant regret bound for linear MDP is somewhat easy to obtain. In detail, as the authors show in line 153, the UNI-SOFT assumption is similar to the HLS condition in [Papini et. al, 2021]. They both show that the representation from the optimal action can provide rich information on the whole space of representation. Given this similarity, the proof of the constant regret bound is quite similar with [Papini et. al, 2021]\n\nSecond, regarding the representation selection part, the authors acknowledge in line 294 that there's a $\\sqrt{N}$ inflation in the confidence radius $\\beta$. However, this additional $\\sqrt{N}$ is crucial for representation learning. According to [He et. al, 2020], this additional $\\sqrt{N}$ factor will lead to an additional $N$ dependency on the final regret bound. This additional $N$ dependency will make the result infeasible when the representation candidate set is large.\n\nTherefore, due to the drawbacks mentioned above, especially the crucial additional $N$ factor in regret bound for representation selection, I would like to suggest marginally reject this paper.\n\n[1] Papini, Matteo, et al. \"Leveraging good representations in linear contextual bandits.\" International Conference on Machine Learning. PMLR, 2021.\n\n[2] He, Jiafan, Dongruo Zhou, and Quanquan Gu. \"Logarithmic regret for reinforcement learning with linear function approximation.\" International Conference on Machine Learning. PMLR, 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact of this work found. Here's my suggestions\n\nIt is still not clear to me how to verify the UNI-SOFT condition. It would help readers understand the performance of the representation learning algorithm by adding some experiments.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "ZiPG6aIFSDA", "reviewer": "Reviewer_nyW6", "summary": "This paper introduces the “UNISOFT” assumption which roughly states that the features for the state-action pairs visited by the optimal policy must span the entire feature space. A lower bound is given which shows that the assumption is necessary to achieve constant regret, and upper bounds are given which establish that the LSVI-UCB and ELEANOR algorithms achieve constant regret when UNISOFT holds (but also with a gap condition as well as their respective linear MDP and low IBE assumptions). The authors also analyze the representation selection problem (where a candidate set of features is given) and propose the LSVI-LEADER algorithm which has regret as small as that of the best feature, and in particular constant regret if any of those features is UNISOFT.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "From a technical standpoint this seems like a strong paper with interesting technical contributions towards the problem of low-regret algorithms for linear function approximation (although under strong assumptions). For this reason I am recommending acceptance (albeit a weak one for now for reasons that I will be discussing shortly). \n\nThe proofs are neat and mostly seem to check out, although I did not check them in great detail. I particularly enjoyed the lower bound (Theorem 5 and Lemma 7). I think the upper bound results would also be strengthened by emphasizing that, with UNISOFT, constant regret is achieved for any algorithm that falls under the very standard form of “optimism + elliptical confidence bounds”. \n\nThere are a number of confusing or potentially concerning points, however. The main claim is that UNISOFT gives constant regret, but it is very unclear from the stated bounds (Theorems 8 and 9) how the regret is independent of K. In particular the bounds scale with \\bar{\\kappa} (defined in the text as “the last episode where ELEANOR suffers non-zero regret”), which I would be very surprised to learn is independent of K. In particular If ELEANOR suffered non-zero regret for a number of episodes independent of K then surely ELEANOR would also have constant regret? (e.g.  an easy bound would be Regret <= \\bar{\\kappa} * H). The text states “As expected, \\bar{\\kappa} is independent of the number of episodes K” as if it were evident, so it is possible that I am missing something obvious here. Either way, I think some clarification on the K-independence of this bound is in order. Examining the proof for this is not illuminating either — the K-independence comes from Eqn (3) of the sketch (or Eqn (28) of the full proof), and it is not clear how the authors arrive at these crucial inequalities (the <= \\Delta_min bound). Can the authors elaborate on this? \n\nAnother technical concern is about the lower bound. The text after Theorem 5 states that the class of MDPs given in the Theorem statement (i.e. with linear rewards and arbitrary dynamics) subsumes low-rank MDPs, linear-mixture MDPs, and MDPs with Bellman closure. The last of these claims is untrue — linear rewards alone do not guarantee Bellman closure as far as I can tell (due to the max over actions being inside the expectation, the update T(q) can not be written as a single linear function). If this is indeed not true then the lower bound does not actually show that UNISOFT is necessary for constant regret in Bellman-closed MDP-feature-map pairs, so the results are not as strong as they claim. On a related note: the Bellman optimality equation which is given in the Preliminaries section is incorrectly stated (!)\n\nThere are some writing concerns which I also think should be addressed. The intro sets up an unclear dichotomy between “good” representations and “learnable” representations. These terms aren’t defined very well (except circularly), and the rest of the paper uses this language in a technical sense (cf. Assumption 4). If we take the meaning expressed in Assumption 4 as the technical definition then it seems that learnable features are defined exactly as the features of Low-Rank MDPs or features with low Bellman Error, which seems like a restrictive definition for such a general idea. Furthermore, if a “good” representation is one that is realizable and a “learnable” definition is as above then one of these definitions is a strict subset of the other one. In summary I do not think this dichotomy adds anything and just confuses the narrative, and I would advise revising this section of the paper. On a more minor note, there is an inconsistency in the text about whether the term “linear MDP” is used (as in the title) or “low-rank MDP” (as in Assumption 2). I think the UNISOFT condition should also be loosely introduced in the setup of the paper, rather than saying “good” in the abstract.\n\nLastly, a question for the authors: why does unisoft need to assume a unique optimal action? Does this come into the proof somewhere?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned above: I think certain technical points should be clarified and/or corrected and the writing should be improved in several places. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "WBAFxUJXomN", "reviewer": "Reviewer_Nzqf", "summary": "The paper considers problem dependent bounds for finite horizon MDP. The problem dependent regret bound do not have a logarithmic term of time, which is the key innovation as compared to the prior works. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper gives the first results where log(T) factor could be removed in problem dependent setup of MDPs. Even though the result is new, the usefulness of the result is unclear. Since there is already a \\sqrt{T} term for the regret, saving O(\\log T) has a negligible performance improvement in realistic setup. The paper also lacks any numerical result to explain the use of this result in practice. The key novelty in the proof also needs better explanation. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Swm5VDcjNbz", "reviewer": "Reviewer_UvSm", "summary": "In this paper, the authors study conditions for achieving constant regret in RL with linear function approximation. They show that under a condition called UNISOFT, which says that features of state-actions pairs that can be reached by the optimal policy has the same span as features of state-action pairs that can be reached by any policy, constant regret is achievable if additional representational condition (completeness or linear MDP) holds. The authors also show that LSVI-LEADER (a modified version of LSVI-UCB), when given a set of N different representations, can adapt to the best representation automatically and achieve a regret bound that is upper bound by that of the best representation. Therefore, LSVI-LEADER achieves constant regret if any of the given representation satisfies UNISOFT. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies conditions that permit constant regret in RL with linear function approximation. The UNISOFT condition is intuitive, and the authors prove that such a condition is necessary for achieving constant regret bound. Moreover, if additional representation conditions that permit sample-efficient RL with linear function approximation hold, UNISOFT is also sufficient for achieving constant regret. Therefore, the authors give an almost complete characterization of conditions that permit constant regret in the linear function approximation setting.\n\nThe authors then discuss how to select a representation that satisfies UNISOFT in linear MDPs. In particular, they propose an algorithm that receives M different representations as input and show that the regret of the algorithm is upper bounded by that of the best representation. Therefore, if any of the given M representation satisfies UNISOFT, the algorithm achieves constant regret. Algorithmically, the idea is to solve M different linear regression problems that share the same set of targets, and set the estimated Q value to be the smallest one among all the M predictions. The algorithm itself is a generalization of the one in Papini et al. which works in the bandit setting. However, it should be noted that the representation condition used here is rather strong: it requires the transition probabilities to be linear with respect to all the given M representations, which could be restrictive. \n\nIn summer, this paper studies an interesting question. The authors give an almost complete characterization of conditions that permit constant regret in the linear function approximation setting. The authors also discuss how to automatically utilize a set of representation which potentially contains one representation that satisfies UNISOFT. This paper is also well written. Overall, this is a good paper and therefore I recommend acceptance.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "see main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies "fine-grained" properties of linear representations in reinforcement learning, in particular when such a representation can admit constant regret guarantees, going beyond the worst case bounds of \sqrt{T}-type. The paper also consider a representation selection setting, where one representation among a class admits a constant-regret bound. 

The paper is a natural generalization of recent work on fine-grained representation properties in the linear bandits literature, but we believe it is a noteworthy contribution, so we are recommending that the paper is accepted to the conference. 

A couple of comments that I have for the final version:
- It is worthwhile to clarify the difference between the representation selection setting considered in this paper, and the ones in e.g., FLAMBE, MOFFLE, and the paper of Hao et al., on sparse linear RL. I feel the two settings are quite different, and it is worth clarifying this for readers and potential new contributors to the area. To me, the main differences are: in this paper all representations satisfy realizability/linear-MDP assumptions, so all of them can yield \sqrt{T}-type regret, while one can potentially yield a much better guarantee. In the aforementioned work, only one representation can even yield \sqrt{T}-type regret, while the others are essentially useless. In particular, the assumptions here are quite a bit stronger, but of course the result is also stronger. 
- On a technical level, it would be helpful to explain how the proofs here differ from the analogous results in linear bandits. What technical novelty should a reader expect here? 
- Lastly, please include any details from the discussion with the reviewers into the final manuscript. In particular the empirical evaluation would be nice to add. 
Decision: Accept (Poster)