Horizon-Free Regret for Linear Markov Decision Processes
Authors: Zihan Zhang
Jason D. Lee
Yuxin Chen
Simon Shaolei Du
Venue: ICLR 2024 poster (2024)
Keywords: Linear MDP; horizon-free
regret analysis
Primary area: learning theory
TL;DR: We present an algorithm to achieve regret bound of \tilde{O}(poly(d)\sqrt{K}) for the horizon-free linear MDP problem.

Abstract: A recent line of works showed regret bounds in reinforcement learning (RL) can be (nearly) independent of planning horizon, a.k.a. the horizon-free bounds. However, these regret bounds only apply to settings where a polynomial dependency on the size of transition model is allowed, such as tabular Markov Decision Process (MDP) and linear mixture MDP. We give the first horizon-free bound for the popular linear MDP setting where the size of the transition model can be exponentially large or even uncountable.  In contrast to prior works which explicitly estimate the transition model and compute the inhomogeneous value functions at different time steps, we directly estimate the value functions and confidence sets.  We obtain the horizon-free bound by: (1) maintaining multiple weighted least square estimators for the value functions; and (2) a structural lemma which shows the maximal total variation of the inhomogeneous value functions is bounded by a polynomial factor of the feature dimension.

Published as a conference paper at ICLR 2024
HORIZON-FREE REGRET FOR LINEAR MARKOV DECISION PROCESSES
Zihan Zhang
Jason D. Lee"
Yuxin Chen
Simon S. Du
ABSTRACT
A recent line of works showed regret bounds in reinforcement learning (RL) can be (nearly) independent of planning horizon, a.k.a. the horizon-free bounds. However, these regret bounds only apply settings where polynomial dependency the size of transition model is allowed, such as tabular Markov Decision Process (MDP) and linear mixture MDP. We give the first horizon-free bound for the popular linear MDP setting where the size of the transition model can be exponentially large or even uncountable.
contrast to prior works which explicitly estimate the transition model and compute the inhomogeneous value functions at different time steps, we directly estimate the value functions and confidence sets. We obtain the Norizon-free bound by: (1) maintaining multiple weighted least square estimators for the value functions; and (2) a structural lemma which shows the maximal total variation of the inhomogeneous value functions is bounded by polynomial factor the feature dimension.
INTRODUCTION
In reinforcement learning (RI.), an agent learns interact with unknown environment by ob- serving the current states and taking actions sequentially. The goal the agent to maximize the accumulative reward. In RL, the sample complexity describes the number of samples needed to learn a near-optimal policy.
has been shown that the sample complexity needs scale with the state-action space for the tabular Markov Decision Process (MDP) (Domingues et al. (02T). When the state-action space is large, function approximation is often used generalize across states and actions. One popular model linear MDP where the transition model is assumed to be low-rank (Yang & WWang, 2019) Jin et al.
2020b). We denote by the rank (or feature dimension) and the sample complexity will depend on instead of the size of the state-action space.
However, there remains gap between our theoretical understanding of tabular MDPs and linear MDPs. For tabular MDPs, line of works give horizon-free bounds, i.e., the sample complexity can be (nearly) independent the planning horizon (Wang et al., 2020 ZZhan et al.) 2021a). More recently, the horizon-free free bounds were also obtained in linear mixture MDP where the underlying MDP could presented by linear combination of d known MDPs (Ayoub et al. 2020
Modi et al.
2020
Jia et al. 2020 A natural theoretical question is:
Can we obtain horizon-free regret bounds for linear MDPs?
One major technical challenge in obtaining horizon-fiit free bounds that the value function is inho- mogeneous, i.e., for MDP with planning horizon H. the optimal value functions for each time step (V,) h= can vary across h = 1,... H. For tabular MDPs and linear mixture MDPs, one can resolve this challenge by first estimating the transition kernel and then computing the value function based on the learned model. The sample complexity will then scale with the size of the transition
Electrical and Computer (225478, (asooleeeeee @eeeeprrnnceeee incetonn edu. I Department of Statistics and Data Science, University of Pennsylvania; email:
Department
Engineering, Princeton University; email:
yuxi yuxinc@wharee ww@.whartennn...m wnc.wharccn.uuennncoo www.n. edu.
Paul G. Allen School of Computer Science and Engineering, University of Washington; email: ssduêcs. washi innssn.ggto.ndd.

---

Published as a conference paper at ICLR 2024
kernel, which is homogeneous and does not depend H. For tabular MDPs and linear mixture MDPs, the dependence on the model size is allowed Unfortunately, this approach cannot be readily applied to handle linear MDPs because the model size of linear MDP scales with the size of the state space, which can be exponentially large or even uncountable.
Contributions. In this paper, we answer the above question affirmatively by establishing regret bound of ((poly(d) (K) for linear MDPs. Formally we have the result below.
Theorem Choose Reward Confidence as VOFUL (see Algorithm D. For any MDP satisfying the rotal-bounder reward assumption (Assumption 7 and linear MDP assumption (see Assumption 2. then with probability 1 6, the regret of Algorithm is bounded by O(d5.s VK + ds.5), where logarithmic factors of (d, (, 1/6) are hidden by the (+) parameter.
By virtue of Theorem I we show that linear MDP has sample-complexin with only logy-iggaii dependence on H. Although the proposed algorithm (Algorithm D is inefficient in computation, we believe our method provides intuitions to remove the horizon dependence in the view of statistical efficiency.
In terms of technical innovations, design novel method to share the samples to solve different linear bandit problems. Since the optimal value functions are not homogeneous, we need to learn H different linear bandit problems using the same dataset. We first show that it suffices to bound the regret for each single bandit problem, and then bound the maximal total variance by bounding the variation of the optimal value function. See Section 3 for more details. Due space limitation, we postpone the full proof of Theorem to Appendix B
1.1 RELATED WORKS
Tabular MDPs.
There has been a long list of algorithms proposed for episodic tabular MDPs (c.g..
Kearns & Singh/ 22022; ; Brafman & Tennenholtz (2003); Kakade (2003); Agrawal & Jia 2017); Azar
et al. (211)) 7 Jin et al. (2018) Zhang et al. (2020); Wang et al. (2020); Uin et al. (2020a); Zhang et al.
(202
al. (202bb el (023); Zhang et al. (2022)) For finite-horizon inhomogeneous MDPs with
the immediate reward at each step bounded by I/H, Azar et al. (017); Zhang et al. (2200) Zanette
& Brunskill 2019 Li et al. 2222bb) achieved asymptotically minimax-optimal regret ((VSAH (ignoring lower order terms), where SA is the size of state-action space, / is the planning horizon. and K is the number of episodes. Motivated by conjecture raised by Diang & Agarwal (018)), Waag jet al. (2020) developed for time fime-homogeneous MDPs with total rewards in any episode bounded above by the first sample complexity upper bound that exhibits only logarithmic dependence on the horizon H, which was later on improved by Zhang et al. (2021a) to yield a near-optimal regret bound of Ö(VSAK + A). Subsequently, Li et al. (021c)) Zhang et al. (2022) proved that even the poly-logarithe logarithmic horizon dependency in the sample complexity can be removed, albeit at the price of suboptimal scaling with SA.
Contextual linear bandits. The linear bandit problem has been extensively studied in past decades (Auer 2002 Dani et al. 2008 Chu et al., 2011
Yadkori et al. 2011). For linear bandits with infinite arms, the minimax regret bound of O is achieved by OFUL Aabbasi-Yadkoo jet al. 201T), where d is the feature dimension and K the number of rounds. With regards to variance-aware algorithms. ZZhan al. 202Tbb; Kim al. (202)) proposed VOFUL (VOFUL+)
M of + poly(d)). in the absence of the knowledge of (ax ) (with ox the conditional variance of the noise in the k-th round). By Zhou et al. (2021) 1 Zhou & Gu Gul2222 obtained similar regret bounds with improved dependence on d. Another work (Faury et al.) (020) proposed a Bernstein-style confidence set for the logistic bandit problem, also assuming availability of the noise variances.
to achieve a variance-dependdeee regret bound of (poly(dd) V
assuming prior knowledge of (ax ) 1
RL with linear function approximation. It has been an important problem in the RI. community to determine the generalization capability of linear function approximation (Tang et al. 2017 Dann
et al.
2018
Yang & Wang 2019 Jin et al. 2020b Wang et al. 2019; Sun et al. 2019
Zanette
For linear mixture MDP, the model size scales linearly with the feature dimension.
2

---

Published as a conference paper at ICLR 2024
et al. 2020; Weisz al. 2020 Li et al. 202 la Ayoub et al. 2020 Zhang al. 2021b Kim et al. 2022 Zhou et al. 2021: Zhou & Gu 2022 He et al., 2022). Several model assumptions have been proposed and exploited to capture the underlying dynamics via linear functions. For example, Jiang et al. (017) investigated low Bellman-rank, which described the algebraic dimension between the decision process and value-function approximator. Another setting proposed and studied by Jia et al. (2020); Ayoub et al. (220)); Modi et al.] (2020) is that of linear mixture MDPs, which postulates that the underlying dynamics is linear combination of d known environments. Focusing on linear mixture MDPs. Zhang et al. (2021b) proposed the first sample-efficient algorithm to achieve horizon-free (poly (d) / K) regret, and later on Kim et al. (022) obtained better d-dependency in the regret bound; further, recent study Zhou & Gul (2022) designed a variance- & uncertainty exploration bonus with weighted least-square regression, achieving near-optimal regret bounds with computation efficiency. Another recent strand of research Yang & Wang (2019); Jin et al. (020b); ;
He et al. (2022); Agarwal et all (2022) studied the setting of linear MDPs, where the transition kernel and reward function are assumed to be linear functions of several known low-dimensional feature
vectors. Take episodic inhomogeneous linear MDPs for example: when the feature dimension is d
and the immediate reward in each step is bounded above by 1/H, :Jin et al. 2020b) established the
regret bound of Ö(V H²K), whereas the follow-up works He et al. (2022) Agarwal et al. (2022)
improved the regret (d) remained unclear whether and when horizon-free solutions are plausible in linear MDPs, in the hope of accommodating scenarios with exceedingly large H.
2
PRELIMINARIES
In this section, we present the basics of MDPs and the learning process, and introduce our key assumptions. Throughout the paper, A(X) denotes the set of probability distributions over the set X.
Episodic MDPs. A finite-horizon episodic MDP can be represented by tuple where S denotes the state space containing S states, A is the action space containing A different actions, R: S x A + A(0,, 1]) indicates the reward distribution, P S x A + A(S) represents the probability transition kernel, K stands for the total number of sample episodes that can be collected, and H is the planning horizon. In particular, P is assumed throughout to be time-homogeneous, which is necessary to enable nearly horizon-free regret bounds; in light of this assumption, we denote by P... P(- 8, a) A(S) the transition probability from state to state s' while taking action a. The reward distribution R is also assumed to be tone-homogeneous, so that the immediate reweard state-action pair (s, a) at any step is drawn from R(s, a) with mean E(,,R(s.)) [r'] r(s, a).
H),
Moreover, deterministic and possibly non-stationary policy π = {mA : S + A] describes an action selection strategy, with TA specifying the action chosen in state at step h.
At each sample episode, the learner starts from an initial state 81: for each step = 1,.., H, the learner observes the current state Sh takes action a₁ accordingly, receives an immediate reward Th R(s), ax), and then the environment transits to the next state $h+1 in accordance with P( az). When the actions are selected based policy π, we can define the Q-function and the value function at step h respectively as follows:
H Σ W
H Σ Lh==h
(7(3,a) = E.
Th
(sh) an) (s) and = EST
Th
8h =
for any (s. E S x A, where R.(.) denotes the expectation following i.e., we execute ard The (SWr for all h R H (resp. h S H/ S H) in the definition of QJ, (resp. V The optimal Q-function and value function at step h can then be defined respectively
() max Q7 a) and V (s) = max VTT (8), V(s,a) E A.
These functions satisfy the Bellman optimality condition in the sense that VT((s) max, Q7 (s, Vs E S, and Q (s, a) r(s, a) + Be
V(s, e
The learning process. The learning process entails collection of K sample episodes. At each episode = 1, 2.... K, a policy n² is selected carefully based on the samples collected in the previous k- episodes; the learner then starts from given initial state sf and executes x² to collect
3

---

Published as a conference paper at ICLR 2024
the k--th episode {( ai. ( hsNsss where sh ab and r denote respectively the state, action and immediate reward at step h of this episode. The learning performance is measured by the total regret
Regret (K) = Σ (vi VT
VT (st)
and our ultimate goal is to design a learning algorithm that minimizes the above regret ①
Key assumptions. We now introduce two key assumptions imposed throughout this paper, which play a crucial role in determining the minimal regret. The first assumption is imposed upon the rewards, requiring the aggregate reward any episode to be bounded above by 1 almost surely.
Assumption 1 (Bounded total rewards). In any episode, we assume that Σ th S holds almost surely regardless of the policy in
Compared to the common assumption where the immediate reward at each step is bounded by 1 1/H, Assumption is much weaker in that it allows the rewards to be spiky (e.g., allow the immediate reward at one step to be on the order of with the remaining ones being small). The interested reader referred to Jiang Agarwal (2018) for more discussions about the above reward assumption.
The second assumption postulates that the transition kernel and the reward function reside within some known low-dimensional subspace, a scenario commonly referred to as a linear MDP.
Assumption 2 (Linear MDP (Jin et al. (0200)). Let B represent the unit & ball in R4, and let {Ø(s, a) (s.)ESxA C be a set of known knownfeature vectors such that maxs.a | ll S 1. Assume that there exist a reward parameter 0, E Rd and a transition kernel parameter E Rxdx such that
r(s,a) a) (6(s,a),0,)
V(s,a) E S
(2a)
P(: (1,8),a) = p a),
V(s,a) E ESXA
(2b)
||0/1l2 S Va.
(2c)
|| [pTTll22 S vd.
Ve E R obeying ||v|lso S 1.
(2d)
In words, Assumption 2 requires both the reward function and the transition kernel to be linear combinations of a set of d-dimensional feature vectors, which enables effective dimension reduction as long as d < SA.
In comparison, another line of works Dia et al. 2020 Ayoub et al. 2020 Modi et al. 2020 focus on the setting of linear mixture MDP below. Assumption 3 (Linear Mixture MDP). Let {(r,, Pi) be group of known reward-transitin pairs. Assume that there exists a kernel parameter E Rd such that
r(s,a) 0))(s,
(ss,aeSSx)
(3a)
p()18,a) = Σ a,
((s,))
(3b)
iml
|001 1.
(3c)
Roughly speaking, Assumption requires that the underlying reward-transition pair is a linear combination of d known reward-transitoon pairs. Recent work Zhou & Gu (202)) achieved a near- tight horizon-regret bound in this setting with a computational efficient algorithm. However, we emphasize that learning a linear MDP fundamentally harder than learning a linear mixture MDP. The reason is that the only unknown parameter in linear mixture MDP problem is the hidden kernel which has at most d dimensions. So it is possible to learn to fully express the transition model. While in linear MDP, the dimension of unknown parameter μ scales linearly in the number of states, where it is impossible to recover the transition model. To address this problem, previous works on linear MDP try learn the transition kernel in some certain direction, e.g., μ for some certain v E S This approach faces a fundamental problem in sharing samples among difference layers. We refer Section 3 for more discussion.
4

---

Published as a conference paper at ICLR 2024
Algorithm Main Algorithm
Input: Number episodes K, horizon feature dimension d, confidence parameter
2: Initialization: + 1/11f, + 1/(KH)* a + 150d / log ((KH))))
3: for k = ......... do
4: D + fsh s F
5: Connstruct the confidence region for the transition kernel.
6: for EEEEE We do
7:
(0), (U),, (o), t HF Estimator
8:
(v, + -vvo (A +c;
9:
end for
10:
4t
S 6f (u. Φ), VO 2.0E W.}
11:
// Construct the confidence region for the reward function.
12:
* -Reward- - Conf fonnieence
(f0 /V (] frk -aga [[l
// Optimistic planning.
14: (n², 1.8))= t arg max agek max, En G= Th j 0];
15: n² be the optimal policy w.r.t. the reward parameter as 6 and transition parameter as nM:;
Play n² in the k-th episode;
17: end for
Algorithm Estimator
1: Input: group of samples D {si, ai, s value function R=;
2: Initialization: + 1/H?, a + 150d/logg (ogg(((()//))) di + a(s,, sis n, et
1/(KH)*
3: of + 4;
4: for 2,3.... do
5: A,- < Σ Ug 0i /
6:
6, Ei=l (3's))
ve, 0, + A
7: b + i-1 o(s
01, 01-1 + b
oy
8: of x 1. 0-- (Ø] 01-1) 1) + 160 Φ. (As-1) 10s + 46,;
9: end for
10: 0 0- A Un. 0 + A Un. A t- Ani
11: Return: (0,0.)):
Notation. Let us introduce several notation to be used throughout. First, we use to abbreviate
12g(2/5). For any E Id and A Rddd we define the weighted norm ||>||| vx Az. Let [N] denote the set 21, N) for a positive integer N. Define B(x) = (0 Rd |0|| S x) and let B = B1) be the unit ball. For two vectors u, with the same dimension, we say 2 (resp. S v) iff u is elementwise no smaller (resp. larger) than v. For a random variable X, we use Var(X) to denote its variance. For any probability vector p E A(S) and any
[ul]ssss E S.S we denote by V(p,v) v) p (u²) (p u²2 the associated variance, where v² = [uf]ssiss denotes the entrywise square of v. Let obt abbreviate dis aft)) for any proper (h, k). Also, we say (h',k' h k'H < h kH. Let Ft denote the a-algebra generated by {o at Jav ((v.)) We employ E[- p.. 0] to denote the expectation when the underlying linear MDP is generated by the transition kernel parameter f and the reward parameter (cf. Moreover, let & denote the set of all possible features. Without loss of generality, we assume O is convex
(h, k) iff

---

Published as a conference paper at ICLR 2024
3 TECHNIQUE OVERVIEW
In this section, we first discuss the hardness of horizon-free bounds for linear MDP, and then introduce the high-level ideas of our approach. To simplify presentation, we focus on the regret incurred by learning the unknown transition dynamics.
3.1 TECHNICAL CHALLENGE
Least-square regression in the linear MDP problem. Jim al. (020ch proposed the first ef-
ficient algorithm (LSVI-UCB) for the linear MDP problem. In this method. for each h E [H]. the learner maintains an estimation of V and constructs optimistic estimators of Qa () = r(s, + P.T Va+1. Since the reward is assumed to be known, it suffices to estimate P Vh+1 = (d(s, a)) " T VA+I. By defining 0h-1 = / TT VV+I, can estimate (ø(s, a)) 0n++ with least-square regression because all state-action pairs share the same kernel 0x+1. This task is basically the same as linear bandit problem, except for that additional factors are needed due uniform bound over all possible choices Vi+1-
To obtain horizon-free regret bound, a common approach is design estimators for P.T. Vh+1 with smaller confidence intervals. In this way, we can choose smaller bonus to keep the optimism, and the regret also reduced since the leading term in the regret is the sum of bonuses.
Recent work Zhou & Gu 2022) made progress in this direction by designing variance- aware estimators for the linear regression problem. Roughly speaking, given a groups of samples {Φ., 0; 1;);
such that (i) 2; = o. f 4, Vi [n]: (ii) B[c, -11 (9) = and E( {
of vi E [n], with the method in Zhou & Gu 2022). the width of the confidence interval of Φ is roughly
δ (polyidVoTA-1o)
(4)
where AI En=
T and À some proper regularization parameter (See Lemma in of
Appendix Aj.
Main technical challenge: Variance-aware estimators coupled with inhomogeneous value functions. While the transition kernel is assumed to be time-homogeneous, the value function and the policy be time-inhomogenene across different steps. Although the confidence width in 4 seems nice, it poses additional difficulty to bound the sum of bonuses due to time-inhonngeneouss value functions.
Below we give more technical details to elucidate this technical challenge. To simplify the problem, assume that the learner is informed of both the reward function and the optimal value function (V, he[[H- Note that the arguments below can be extended to accommodate unknown (V. he[H] well by means of proper exploitation of the linear MDP structure and discretization method (i.e., applying a union bound over all possible optimal value functions over a suitably discretized set).
Let 0g = 1 Vi+1- Then it reduces learning H contextual bandit problems with hidden parameter as {07) To remove the polynomial factors of H, is natural to share samples over different layers. That is, we need to use all the samples along the trajectory {sw, , owe S144 = estimate the value of T07--
To solve the h-th linear bandit problem, following 4 we could get regret bound of Regret, (K)
Ô EK K
/ ( (A
oh
Here (² AI Σ
H H
M=1
o (o
(o))
with
(1) as an upper bound for the variance V(P oy aty resulting regret bound roughly
aty, v) for E RR. Taking sum over h,
min
V (T))
(A* -))
(5)

---

Published as a conference paper at ICLR 2024
We remark that if V is homogeneous in h, i... there exists V such that V V for any h [H] we could use Cauchy's inequality to bound 5 by !
K Σ
min
Σ (o)))))) (6)
k=1
Noting that
H A (
(ox
(V+))
can further the elliptical potential lemma (Lemma 6 to bound the first term in @ and the
total variance lemma for MDPs to bound the second term in 6h. As a result, we can easily bound (5) by (d)olyd))KK)
However, the arguments above cannot work when Vi depends on h. In such cases, the first term in would be
min (
(8)
To invoke elliptical potential lemma, need A (V++((V++)) (²(+++)) Ei== (o (V which does not hold since of (Vi+1) # o (Vi+1).
In comparison, for tabular MDP, the variance aware bonus has a simple form of /(Paaa,V Vi-1)
N
so that one can invoke Cauchy's 's inequality to bound the sum of bonuses; for linear mixture MDP, because there is only one kernel parameter and one information matrix, it suffices analyze like and
3.2 OUR METHODS
In high-level idea, by noting that the main obstacle is the time-inhoomogeneous value function, aim to prove that the value function {VA H could be divided into several groups such that in each group, the value functions are similar each other measured by the variance.
Technique 1: uniform upper bound for the variances. We consider using a uniform upper
bound (o = max (n) (o (Vi+1))² to replace (a (Vi+1))² when computing A (V(V)))) That
k- is, by setting A * AI k m1 Σd=
Kie (o
$ A (Vit1) for any E {H], we can bound (5)
as below:
K
min
(o)) (A 11
K
(d))) (At))
min
1=1
oo//o (44
ΣΣ (ok)²
k=
With the elliptical potential lemma (Lemma
6 we have that
K
H
Σ
min
(A (xt)))))) -O(a))
A=1
1=1l
Here omit lower order

---

Published as a conference paper at ICLR 2024
So it suffices to deal with Σ K== H (ot). . For simplicity, we assume that (o)) is exactly ((Pat.a ahatt v) and consider to bound Ei=1 Exm1 maxwe(m] V(Pat . ak. vi++ a) ((v)) which
Noting that V(Ps.as v) could be written Φ(s, (0()2)) (Ø(s,
is linear function of the matrix as) (s) Φ(s.a)
we can bound
o (s,a))
Ek= Ek= max V(Pag at Vi(+1) by 2(d + 1)² ma Σ Eh= op
with a useful technical lemma (See Lemma 5
As a result, it suffices to bound Σ E V(Pat of. +1 for each h' E [H]. However, because
+1 can vary significantly when h is closed to H. E Ei= V(Ps aha v might be large in the worst case. We consider the toy example below.
Example 1. Fix some e 0. Let S == {si; 82, 83, 2). A fai, u2). Let Pa Pai.a Psg.a1 [ 6.2 -,,,,,,, C,C,0] r(s1, = r(82, 01) = Psj.ag Pss.az = 00,0, 0, 1] r(81, (2) r(82, = 0, Per.0s Pag.a2 [0,0,0, 0, 0, 1] r($3, r(s3, 02) 1, Pz.0: P2,02 10, and r(z, (2)
In this toy example, we have two frequent states {si, s2). one transient state {53} with reward 1 and one ending state z with no reward. The transition dynamics {51, 82} ] is the same, but one can get reward _ in one step by taking action 02 at s1. Suppose H >> 1 and h < 2' then the optimal action for {s1, }22} at the h-th step should be 01. and Vi (s1) ~ Ví, (s2) = 1. On the other hand, it is easy to observe Vi (s1) = and Vi (2) = 0. Let the imitial state be $1. Following the optimal policy, we
have E
Σ V(P vi) = (02 >> 1 when choosing small enough.
Technique 2: bounding the total variation. Direct computation shows that for 1 I hi < h2 S
[1].
K h2 ΣΣ
Pa Vi+1) = Ö(K + K(h22 - h1 + 1) - Vo441
(10)
k=
Let 4, = IV - 1lo. It is easy to observe that 4, 1 4+1 for 1 I h S H since the Bellman operator T is a contraction i.e., [[T(11 12) I || 221loo for any U1 R.S.
Σx wy So obtain 4n < H-M+1 For tabular MDP, it is easy to bound Σb=14 4 < S since | Vi s (V)((s) - Vn+i(s)). As a generalization to linear MDP, by Lemma we have that
H-1
H-1 Σイン
H-1
Σ
o 4 (Vh+1 - Vn+2) S max 2do deS
Σ
p (Vh+1 - V/+2)) - 2d.
(11)
h=1
As a result, 1
< H-h+1
Technique 3: doubling segments. By choosing h 4
H +1 and h2 H1 in 10 for h' E [1i, h2].
K ha
Vi41) Ō(K + K(ha - hi + 1) Vi+ [1xx)) Ö(Kd).
k=1d=hı
This inspires to divide [H] several segments [H] U,H4 with Hi (M|H H S h
21-1
H 2' and HioRy 1)+1 {H) Consequently, for any and h E H4, using [0 and the fact that
2d 2 i 5 - - ΣK EnEn, V(Pst.ag Vi++1) = Ö(Kd).
Note that we only bound Ek Elar (M)++ maxNEH; EnER. V(P a V which does not
imply any bound for max Σk_ IH V(P.g Vi+1). Recall that our initial target is to
We assume (og is integer without loss of generality.
8

---

Published as a conference paper at ICLR 2024
E (A 1]- natural idea to group h E Hi for each to avoid the term maxNEil Ek=1 2h=1 V(P Vi In other words, we turn bound EK= min (ENER, / (d)) (V/+1)) -10 1 for each i separately. More precisely, for fixed
bound Ex= min
k=
i, we let (2 = maxsEn, fof% (V (v++))) and A A EV=l ENEH,
With the
(
arguments above, we have that
Σ (A
NEH;
K
min
Σ (01/00)/00)
(at)2 + Ö(d)
k=1
NEWS
k= kEH
Ö(VKdt).
(12)
ALGORITHM
In this section, introduce Algorithm T The algorithm is based model-climination. At each episode k = 1, ,, we maintain utth as confidence region of μ and @* as confidence region for f,. Then
select the optimistic transition model and reward function from 4t O and then
execute the corresponding optimal policy. The key step is how to construct 2t Inspired by recent work Zhou & Gu (2022), we consider the weighted least square regression to estimate the value function and corresponding variance, which is presented in Algorithm 2 Zhang et al. (221b) to construct the confidence region for 0,.
We also borrow VOFUL in
Recall that B(2vd) 10 R |0000 2vdj. For fixed > O, there exists an e-net B, (2Vd) w.r.t. Los for d(2 such that [B. (2Vd) S (((4vd/e)"). By Assumption 2 for any v E R such that ||o| S 1, holds that || uil2 S Vd. Therefore, for any MDP such that Assumption and holds, its optimal value function is in the set
W = {o E R
30 E ((2vV), u(s) = max/min(maas (s,0)),1))00 E
Define We { 0 E 1 (.(2Vd) v(s) max ( a,,, Vs E $} For 1..10... .0) is O1))-iipschtzz
fixed 0 B(2vd) and E S, the function max [min (max, o T 1. continuous w.r.t Lxx norm, As a result, W. is an e-net w.r.t Lo norm of W. Besides, the size of W. is bounded by [W& = (((vV//c)))
Confidence region for the transition kernel. Fix group of sequential samples {or) and value function v W. Fix o & and let 0(v) = nr We aim to construct confidence interval from ø j v, and then eliminate all the transition kernels jí which fails to satisfy the confidence interval for some v and To obtain variance-aware confidence interval, we need to compute the variance to feed the weight least-square estimator in Zhou & Gu (2022). For this purpose, for the i-th variance V V(né, v)), we construct of such that o? 2 V(us, v) and the error of Vuup, e) is well controlled. To compute oz. need to estimate of 0(x²) and o, O(v) using the first i 1-th samples. which requires the knowledge of (Hur,, x²) for i' < i 1. To address this problem, Zhou & Gu (2022) recursively estimated the 2mmtth order momentum for m 1, 2, .....
In comparison, by the fact that V(uo,, ,²) < 4V v) (see Lemma we can use 4o as an upper bound for (Hup,, v2).
Confidence region for the reward parameter. To estimate the reward parameter 6,, we invoke VOFUL in Zhang et al. (2021b). We remark that the randomness in reward is independent of the randomness in transition dynamics, so that learning the transition dynamic does not help to estimate the variance of reward. More precisely, the variance of R(s, a) could be a non-linear function in ő(s, a), while the variance of Vi (s') with s' ~ P(-ls, a) must be linear function in ő(s, a). In Appendix[[ we present VOFUL and summarize some useful properties to bound the error due to uncertainty of reward parameter.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
Y. Chen is supported in part by the Alfred P. Sloan Research Fellowship, the Google Research Scholar 19-00-99--0000 and FA9550-22-1-0198. the ONR grant N00014-22- 1 1-2354, and the NSF grants CCF-2221009 and CCF- 1907611. JDL acknowledges support of the ARO under MURI Award 191INF-11-1 the Sloan Research Fellowship, NSF CCF 2002272, NSF IIS 2107304, NSF CIF 2212262, ONR Young Investigator Award, and NSF CAREER Award 2144994, SSD acknowledges the support of NSF IIS 2110170, NSFDMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF CCF 2019844, NSF IIS 2229881.
Award, the AFOSR grants
REFERENCES
Yasin Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Alekh Agarwal, Yujia Jin, and Tong Zhang. Vo q I: Towards optimal regret in model-free with nonlinear function approximation. arXiv preprint arXiv:22/2.06069) 2022.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, pp. 1184-1194, 2017
Peter Auer. Using confidence bounds for exploitation-exploraiion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value- value-targed targeted regression. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. Proceedings of the 34th International Conference on Machine Learning, pp- 263-272, 2017.
Ronen I. Brafman and Moshe Tennenholtz. R-max general polynomial time algorithm for near-optimal reinforcement learning, J. Mach. Learn. Res., ((0c)):213-31,, March 2003. ISSN 1532-4435.
Liyu Chen, Mehdi Jafarnia-Jahrmma Rahul Jain, and Haipeng Luo. Implicit finite-horizon approxima- tion and efficient optimal algorithms for stochastic shortest path. Advances Neural Information Processing Systems, 34, 2021.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings the Fourteenth International Conference Artificial Intelligence and Statistics, pp. 208-20 214. JMLR Workshop and Conference Proceedings, 2011.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. On oracle-efficient PAC-RL with rich observations. In Advances Neural Information Processing Systems, 2018.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufimann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pp. 578-598. PMLR, 2021.
Louis Faury, Marc Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pp. 3052-3060. PMLR, 2020.
Jiafan Hc, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. arXiv preprint arXiv:2212.06/.32 2022.
10

---

Published as a conference paper at ICLR 2024
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pp. 666-686. PMLR, 2020.
Nan Jiang and Alekh Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, pp. 1195--398, 2018.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low Bellman rank are PAC-learnabl. In Proceedings of the 34th International Conference Machine Learning, pp- 1704-1713, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? In Advances Neural Information Processing Systems, pp. 4863-4873, 2018.
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. International Conference on Machine Learning, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory. pp. 2137-2143, 2020b.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020c.
Sham M Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of London London, England, 2003.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49(2-3):209-23 2002.
Yconeung Kim, Insoon Yang, and Kwang- Lrang-Sung Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing 2022.
Systems,
Gen Li, Yuxin Chen, Yuejie Chi, Yuantao Gu, and Yuting Wei. Sample-efficient reinforcement learning is feasible for linearly realizable MDPs with limited revisiting. Advances in Neural Information Processing Systems, 14:16671-16688 2021a.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021b.
Gen Li, Yuling Yan, Yuxin Chen, and Jianqing Fan. Minimax-optimal reward-agnostic exploration in reinforcement learning. arXiv preprint arXiv:2304.0722 07278, 2023.
Yuanzhi Li, Ruosong Wang, and Lin F Yang. Settling the horizon- -deeendenee of sample complexity in reinforcement learning. In JEEE Symposium on Foundations of Computer Science, 2021c
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. International Conference on Artificial Intelligence and Statistics, pp. 2010-2020. PMLR, 2020.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free 2019.
approaches. Conference on Learning Theory, pp.
Ruosong Wang. Simon S Du, Lin F Yang, and Sham M Kakade. Is long horizon reinforcement learning more difficult than short horizon reinforcement learning? In Advances in Neural Information Processing Systems, 2020.
Yining Wang. Ruosong Wang. Simon S Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv: 992.04/32 36, 2019.
11

---

Published as a conference paper at ICLR 2024
Gellert Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with 2020.
optimal action-value functions. arXiv preprint arXiv:2010.01374.
Lin Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004, 2019.
Andrea Zanette and Emma Brunskill. Tighter problem-depence regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, 2020.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantaee decomposition. In Advances in Neural Information Processing Systems, 2020.
Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse horizon. In Conference on Learning Theory, pp- 4528 4531. PMLR, 2021a.
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. In Advances in Neural Information Processing Systems, 2021b.
Zihan Zhang, Xiangyang Ji, and Simon Du. Horizon-fiee free reinforcement learning in polynomial time: the power of stationary policies. In Conference on Learning Theory, pp. 3858-3904. PMLR, 2022.
Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint arXiv:2205. 1107, 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory, pp. 4532 4572-4576. PMLR, 2021.
12


Reviews:
[{"review_id": "j7gKkCLp0f", "reviewer": "Reviewer_nnTm", "summary": "The authors propose a novel algorithm for reinforcement learning (RL) in linear Markov Decision Processes (MDPs). The key feature of the presented algorithm is horizon-free regret bounds, that means that the regret of the algorithm scales only polylogarithmically with a problem horizon.", "questions": "Here I would like to present questions to proofs and additionally indicate misprints that I found. I would like to increase my score if all the clarifications regarding proofs will be given.\n\nQuestions regarding Lemma 4:\n\n- Why it holds $f(l-y)/y^{d-1} ≤ f(l-x)/x^{d-1}$?\n- Is there any references that will show why (16) hold?\n\nLemma 11:\n\n- Possible misprint: After an inequality (a) there is missed square over $v$ in variance and also there should be $v^2(s^k_{h+1})$ in the second term (not $v^2(s^k_h)$);\n- Definition of $\\bar v(s)$ is not clearly written: is it  $\\bar v(s) = \\max_{a} P_{s,a} v?\n- It is not clear why (c) holds because it is not easily understandable why the presented $\\bar v$ maximizes $v(s^k_{h+1})$, or I did not understand the definition of $\\bar v$.\n- Why (d) holds? What is a constant $c$?\n\nMisprints and undefined or confusing notation.\n\n- eq. (8) — V^* without h\n- Equations (9) and (13) — missed square in \\bar \\sigma^k_h in the second multiplier after Cauchy-Schwartz inequality;\n- After equation (9) it claims that \\sigma^k_h is variance, whereas before $\\sigma^k_h$ was a square root of variance, it is very confusing;\n- After eq. (10) — $l^*$ in the beginning and after l without *;\n- After definition of $W_{\\epsilon}$: w.r.t. should be with points not commas;\n- Proof of Lemma 5: $O$ is not defined;\n- After equation (28): use of Var as variance whereas usually it was denoted by $\\mathbb{V}$, and after it confusing claim $\\sigma^k_h(v) \\geq Var$.\n- After equation (29) — no brackets around $i$ in the inequality $\\bar \\Lambda^k_i \\leq \\Lambda^k(\\bar V^k_{h+1})$.\n- After equation (30) — forgotten subscript $(i)$ in the definition of $\\bar \\Lambda^k$ and it is not clear why $\\bar \\Lambda^k + \\sum_{h=1}^H … = \\bar \\Lambda^{k+1}$.\n- Equation (43) — tilde in not over $O$ but over all the expression;\n- Last parargraph of page 21: underfined norm type $\\Vert \\bar v - v \\Vert_i$;\n- Lemma 12 — missed norm type in the statement (is it $\\ell_2$ norm or $\\ell_\\infty$ as it used later?).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The first algorithm for linear MDPs that attains nearly horizon-free regret bounds;\n- Very detailed discussion on novelties of the proposed approach;", "weaknesses": "- Algorithm is computationally unfeasible: it requires to optimize over the confidence region of all models of linear MDPs, that is unfeasible in MDPs with infinite number of states;\n- Proof of Lemma 11 is unclear for me, see section Questions;", "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": "", "extra_scores": {}}, {"review_id": "FQf5Gm0d7h", "reviewer": "Reviewer_anFv", "summary": "The paper provides the first horizon-free bound for linear MDP. The corresponding algorithm is also novel since this algorithm estimates the value function and corresponding uncertainty directly instead of estimating the transition probability.", "questions": "1. I wonder whether this algorithm is numerically efficient.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This is the first bound for the linear MDP problem.\n\n2. The approach is novel and interesting.", "weaknesses": "1. It would be better to have some numerical illustrations to see whether the given algorithm has better numerical performances.", "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": "", "extra_scores": {}}, {"review_id": "5iosyRk4Pg", "reviewer": "Reviewer_p2b6", "summary": "This paper considers a regret bound of linear MDP that has a mild dependency on the horizon $H$. The main results are emphasized in the Thm 1 (2nd page). The transition kernel is uniform over timesteps, the Q function is discountless, and the time horizon H is fixed. The challenge here is the optimal action may depend on the remaining time (i.e., should the model explore more or not), which is reflected in the index $h$ in $Q_h$, $V_h$. The process is sequential; before the beginning of each episode k, we declare policy $\\pi^k$ to play it and observe rewards, and evaluation is based on online measure (regret). Assumptions are that 1: bounded total rewards, 2: linear transition kernel (dim: $S \\times d$) and rewards (dim: $d$) with constant scale per feature. Assumption 3 states that the transition and reward share parameter \\theta (dim: $d$).\n\nThe contribution of this paper is to show horizon-free regret (the regret of subpolynomial dependence on H) for MDP under assumption 2 (compared with similar results with assumption 3 by Zhou and Gu 2022). The paper proposed an algorithm (Algs 1--3 combined) to show this regret. The algorithm seems to be computationally inefficient given it defines some quantities that depend on v (a real variable with bounded norm). While the contribution of this paper is written in the paper and it seems fine, I do not consider the paper to be well-written and ready for publication. Since I am not convinced of the correctness of the claim, I lean to be negative on the paper, but I do not have a strong position . I have several questions in the corresponding section for the sake of clarity.", "questions": "My largest question is about Algorithm 1. If I understand correctly, these algorithms require optimization over continuous space. First, $\\mathcal{W}(\\epsilon)$ is not defined in this paper; similar quantities such as $\\mathcal{W}$ and $\\mathcal{W}_\\epsilon$ are defined twice, so I assume these are equivalent. Lines 6--9 in Alg1 loops over $v \\in \\mathcal{W}(\\epsilon)$, which, defines quantities $(\\hat{\\theta}, \\tilde{\\theta}, \\Lambda^k(v), b^k(v, \\phi))$ as a function of $v$. $\\mathcal{U}^k$ is also optimized on the space of $v$.\n* $\\tilde{\\theta}(v)$ is not used in the line 10 of Alg 1 and after?\n\nOn assumption 2: Is assumption (2d) standard? It seems that the number of unknown parameter $\\mu \\in \\mathbb{R}^{\\mathcal{S}\\times d}$ can be arbitrarily large and it is highly nontrivial to have regret bound that does not depend on the size of $\\mathcal{S}$.\n\nOn the similarity with the (contextual) linear bandit problem. The linear bandit problem is where $x$ is disclosed (contextual is $x$ is $x(t)$) and reward is $r(t) = x^\\top \\theta$ where $\\theta$ is an unknown quantity. In the MDP of this paper, transition has uncertainty and the uncertainty on the reward $r(t)$ w.r.t. transition kernel is much more involved.\n\nThe following are rather minor opinions:\n* VOFUL: Is it by any means related to OFUL? If I understand correctly, OFUL (e.g., Abbasi-Yadkori et al. 2011) is an algorithm for online bandit algorithm whereas Alg 3 is for the uniform confidence bound (also referred as self-normalized bound or martingale bound).\n* Typos. Many periods are missing, for examples:\n> p2: See Section 3 for more details. Due to space limitation, we postpone the full proof of Theorem 1 to Appendix B\n> p6: That is, we need to use all the samples along the trajectory...\n> p7: Fix some eps>0 \n\n* Lines 5, 11, 13 in Alg 1 are comments and can be used some special characters for indicating that, such as $//$", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* The paper considers interesting question whether linear MDP is learnable with horizon-free sample complexity. The paper considers the setting where $\\theta_r, \\mu$ are unknown, which is surely interesting to the community. \n* Sections 1--2 are well-written, except for related work section where many papers are cited without specific connection, but overall, nice.", "weaknesses": "* The algorithm is computationally inefficient with respect to $v$, so the algorithm here is more conceptual than practical.\n* The structure of the paper can be improved. It seems the structure follows Zhou & Gu (2022), but the demonstration of \"technical challenge for 3.5 pages without demonstrating algorithm (the algorithm is introduced after that) does not make much sense. At least, this 3.5 pages does not help the reader to be convinced of the results more than 1-page summary.\n* There are many typos, which makes it hard for the reader to be convinced of the results.", "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": "", "extra_scores": {}}, {"review_id": "c5NVks7RjP", "reviewer": "Reviewer_pF7R", "summary": "This paper introduces an algorithm for linear MDPs that achieves a regret bound independent of the horizon length ($H$). It specifically analyzes regret by grouping indices with the same maximal total variance for the optimal value function, allowing value functions within the same group, even if values are inhomogeneous, to share samples. Despite its computational inefficiency, this work addresses the research question of whether it's possible to obtain a horizon-independent regret bound in linear MDPs, extending the prior research on horizon-free regret analysis in linear mixture MDPs.", "questions": "- While the set of all possible features $\\Phi$ is not precisely defined, if we define it as $\\Phi:=  \\\\{ \\phi(s,a) : (s,a) \\in \\mathcal{S} \\times \\mathcal{A} \\\\}$, then the convexity of $\\Phi$ implies that for all $\\phi_1, \\phi_2 \\in \\Phi$ and \\lambda \\in [0,1], $\\lambda \\phi_1 + (1 - \\lambda) \\phi_2 \\in \\Phi$. This appears to be a highly restrictive assumption. It would be beneficial to explicitly mention this assumption as a Key assumption like Assumption 1-3 if it is essential, especially considering it is not utilized in existing linear MDP literature (e.g., Jin et al. 2020b).\n\n- On page 7, could you please provide an explanation for the statement, \"$\\mathbb{V}(P_{s,a}, v) = \\phi(s,a)^\\top (\\theta(v^2)) - (\\phi(s,a)^\\top \\theta(v))^2$\" being described as a linear function of the matrix ?\n\n- Could you clarify how the last inequality in equation (11) holds?\n\n- Typo?: It seems that while $l_h^*$ is defined below equation (10), $l_h$ is not defined. Please provide a definition for $l_h$.\n\n- What is the meaning of \"size of transition model\"?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "In a linear MDP (simply assuming a known reward function), by setting $\\theta^\\*\\_h = \\mu^\\top V^*\\_{h+1}$ for the transition kernel parameter $\\mu$, since the action value for each state-action pair is given by $Q^*_h(s,a) = r(s,a) + \\phi(s,a)^\\top \\theta^*_h$, hence finding the optimal action at h-step is the same as solving a linear bandit problem. Based on this perspective it seems like an interesting approach to group $H$ bandit problems and share samples to get a $H$-independent regret bound.", "weaknesses": "- While the analysis of horizon-free regret in linear MDPs, as an extension of the algorithm for linear mixture MDPs, is intriguing, the technical novelty in this paper seems somewhat limited. As mentioned in related work, Zhang et al. (2021b) initially proposed a horizon-free algorithm for linear mixture MDPs, and Zhou & Gu (2022) introduced a computationally efficient horizon-free algorithm. Although it is acknowledged that Linear MDPs become fundamentally more challenging as the dimension of unknown parameters grows with the increasing state space, given that the order of regret bound for minimax algorithms with $H$ dependence in both linear MDPs and linear mixture MDPs is the same (Hu et al., 2023), it is regrettable that this paper only presents a computationally inefficient algorithm despite the existence of computationally efficient $H$-free regret bounds in linear mixture MDPs.\n\n(Hu et al., “Nearly minimax optimal reinforcement learning with linear function approximation”, ICML 2022)\n\n- Providing a slightly clearer explanation of the method in the main text would be beneficial. For instance, as mentioned in Technique 3, calculating an upper bound for $\\max\\_{h' \\in [H]} \\sum\\_{k=1}^K \\sum\\_{h=1}^H \\mathbb{V} (P\\_{s^k\\_h, a^k\\_h}, V^*\\_{h'+1})$ is required, but it was stated that a bound for $ \\sum\\_{k=1}^K \\sum\\_{i=1}^{\\log\\_2 H +1} \\max\\_{h' \\in [H\\_i]} \\sum\\_{h \\in H\\_i} \\mathbb{V} (P\\_{s^k\\_h, a^k\\_h}, V^*\\_{h+1})$ was given. A more explicit explanation of how these two bounds are connected would enhance clarity.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)