Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs
Authors: Dongruo Zhou
Quanquan Gu
Venue: NeurIPS 2022 Accept (2022)

Abstract: Recent studies have shown that episodic reinforcement learning (RL) is not more difficult than bandits, even with a long planning horizon and unknown state transitions. However, these results are limited to either tabular Markov decision processes (MDPs) or computationally inefficient algorithms for linear mixture MDPs. In this paper, we propose the first computationally efficient horizon-free algorithm for linear mixture MDPs, which achieves the optimal $\tilde O(d\sqrt{K} +d^2)$ regret up to logarithmic factors. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic, where the weight is both \emph{variance-aware} and \emph{uncertainty-aware}. When applying our weighted least square estimator to heterogeneous linear bandits, we can obtain an $\tilde O(d\sqrt{\sum_{k=1}^K \sigma_k^2} +d)$ regret in the first $K$ rounds, where $d$ is the dimension of the context and $\sigma_k^2$ is the variance of the reward in the $k$-th round. This also improves upon the best known algorithms in this setting when $\sigma_k^2$'s are known.

Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs
Dongruo Zhou
Quanquan Gu
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 drzhou@cs ucla.
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 qguêcs ucla.edu
Abstract
Recent studies have shown that episodic reinforcement learning (RL) is not more difficult than contextual bandits, even with long planning horizon and unknown state transitions. However, these results are limited to either tabular Markov decision processes (MDPs) computationally inefficient algorithms for linear mixture MDPs. In this paper, we propose the first computationally efficient horizon- free algorithm for linear mixture MDPs, which achieves the optimal Ó(d K + d²) regret up to logarithmic factors. Our algorithm adapts weighted least square estimator for the unknown transitional dynamic, where the weight is both variance- aware and uncertainty-aware When applying our weighted least square estimator
to heterogeneous linear bandits, we can obtain an Ö(d Ek= of + d) regret the first K rounds, where is the dimension the context and of the variance of the reward in the k-th round. This also improves upon the best-known algorithms in this setting when of are known.
Introduction
How to design efficient algorithms central problem for reinforcement learning (RL). Here, the efficiency includes both statistical efficiency, which requires the RL algorithm enjoy low regret/polynomial sample complexity for finding the near-optimal policy, and computational efficiency, which expects the RL algorithm have polynomial running time. When restricting to episodic RL with total reward upper bounded by 1 a longstanding question whether episodic RL statistically and computationally more difficult than contextual bandits (Jiang and Agarwal 2018), since episodic RL can be seen as an extension of contextual bandits to have a long planning horizon and unknown state transition. For tabular RL, this questions has been fully resolved by line of works (Wang et al., 2020; Zhang et al.) 2021b Li al. 2022 Zhang et al.) 2022), which propose various horizon- algorithms. Here say algorithm is horizon-free if its regret/sample complexity has at most polylogarithmic dependence on the planning horizon H. In particular, (Zhang et al., 2021b) proposed the first computationally efficient algorithm for tabular RL whose regret enjoys polylogarithmic dependence on the planning horizon, and (Zhang et al. 2022) further removed the polylogarithmic dependence on the planning horizon.
For RL with function upproximation to deal with large state space, space,ZZhang et al. (2021c): Kim et al. (202T) have made some progress towards horizon-free RI. for class of MDPs called lineur mixture MDPs (Jia et al. 2020 Ayoub et al.) 2020 Zhou et al., 2021a). whose transition dynamic can be represented as linear combination of d basic transition models. More specifically, Zhang al.
'eee Assumption 3.1 for detailed description.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

2021c) proposed a VARLin algorithm for linear mixture MDPs with D(dt5 + d") regret for the first episodes, and al. (202T) proposed VARLin2 algorithm with an improved regret O(dvK K + ). However, neither algorithm is computationally efficient, because both of them need to work with nonconvex confidence sets and do not provide polynomial-time algorithm to solve the maximization problem over these sets.
So the following question remains open:
Can we design computationally efficient horizon-free RL algorithms when function approximation is employed?
In this paper, we answer the above question affirmatively for linear function approximation by proposing the first computationally efficient horizon-free RL algorithm for linear mixture MDPs. Our contributions are summarized as follows.
As a warm-up, we consider the heterogeneous linear bandits where the variances of rewards in each round are different. Such setting can be regarded as a special case of linear mixture MDPs. We propose a computationally efficient algorithm WeightedOFUL + and prove that in the first
K Krrounds, the regret of WeightedOFUL is Öld// > of + dR - d), where of is the variance of the reward in the k-th round and R is the magnitude of the reward noise. Our regret is variance- aware, i.e., it only depends the summation of variances and does not have v K term. This directly improves the Õdd Σ of
vdK + d) regret achieved by Zhou al. (021a).
For linear mixture MDPs, when the total reward for each episode is upper bounded by 1, we propose a HF-UCRL-VTR algorithm and show that has an ÖddvK + d') regret for the first K episodes, where d is the number of basis transition dynamic. Our "T-UURL-VTRR" is computationally efficient, horizon-free and near-optimal, as it matches the regret lower bound proved in our paper up logarithmic factors. Our regret is strictly better than the regret attained in previous works Zhou et al. [2221a] Zhang et al. 2021c Kim et al. 2021).
At the core of both WeightedOFUL" + and HF-UUCLL-TRR is carefully designed weighted linear regression estimator, whose weight is both variance-aware and uncertainty-awars contrast to previous weighted linear regression estimator that is only variance-aware (Zhou et al. 2021a). For linear mixture MDPs, we further propose HOME that constructs the -nncunccnntttanntty... aware weights for high-order moments of the value function, which is pivotal to obtain horizon-free regret for linear mixture MDPs.
For better comparison between results and previous results, summarize these results in Table It is evident that our results improve upon all previous results in the respective settings
Notation. We use lower case letters to denote scalars, and use lower and upper case bold face letters to denote vectors and matrices respectively. We denote by [n] the set (1.....n). by [M] the set {0, {O...., n 13. For vector x Rd and positive semi-definite matrix Σ gdxd we denote by ||x||2 the vector's 's Euclidean norm and define ||x|| = vx Σx. For x, E R let x @ y be the Hadamard (componentwise) product of x and y. For two positive sequences {a,) } and {6,} with n = 1,2,... we write on = (b,,.) if there exists an absolute constant C > 0 such that an S Cbp holds for all n 2 and write 0n l(b,)) if there exists absolute constant C > such that an 2 Cb, holds for all n 2 We use Ō(-) to further hide the polylogarithnic factors. We use 1(-) to denote the indicator function. For a, b E R satisfying S b, we use [ denote the truncation function 1fa < < b} + frr < a) + b 1xx b}.
2 Related work
In this section, we will review prior works that are most relevant to ours.
"The only exception is that for heterogeneous linear bandits, our algorithm needs to know the noise variance. while Zhang et al. (2021c); Kim et al. (2021) do not. But their algorithms are computationally inefficient. We plan extend algorithm deal with unknown variance the future work.

---

Table 1: Comparisons of regrets for linear bandits and linear mixture MDPs.
Computationally Efficient?
Algorithm
Regret
Assumption
OFUL
Ō(dVK)
Yes
AbbmiiYalkorii et al
WerghtedOr UL
Old Σ of + Vdk + +d)
Known variance
Yes
Zhou 2021a
VOFU
O 2k=1 of d
K
Unknown variance
No
Zhang et al.
c021c
VOFUL2
.2
O E of +P
Unknown variance
No
(Kim al.
2021
WeightedO
Ōldy Ekm o2 + +d)
Known variance
Yes
(Thcorem
4.1
UCRL-VIT VTR
Homogeneous,
O(dVH*K) OV KK H d
Yes
Σn rh S Inhomogeneous, Σn nh < I Homogeneous, Σn rh S Homogeneous, Σn rh $ Homogeneous, >n Th S
ca al.
2020 Ayoub ot
3000
UCRL-VIT VTR
Yes
Zhou
2021a
VARL 1
O(RSS/ +
No
Zhang et al.
2021c
VARL
L12
Ō(dVK + +)
No
Kim et al.
2021
HF-UCRL-VE VTR
Ö(dVK + +d)
Yes
(Theorem 5.1)
Lower bound
((dVK)
(Theorem 5.3
Heterogeneous linear bandits. Linear bandits have been studied for long time. Most of existing works focus the homogeneous linear bandits where the noise distributions at different round are identical (Auer 2002; Chu et al.] 201TT: Li et al.] 2010 Dani et al. 2008; Abbasi- Yadkori et al. 2011 Li et al., 2019a b). Recently, series of works focus the heterogeneous linear bandits where the noise distribution changes over time. [Lttimore et al. (2015) assumed that the noise distribution is Bernoulli and proposed an algorithm with an O(dy K) regret. Kirschner and Krause (2018) assumed that the noise k-th round is Ee-sub--auusiaa and they proposed a weighted ridge
regression- begression-based based algorithm with an Öldy Ekm of) regret. A recent line of works assume the variance of the noise k-th round bounded by of. Under this assumption, Zhang et al. 2021c
proposed a VOFUL algorithm with an Odt VIR 2 + d²) regret. Kim et al. 20021 proposed
VOFUL22 algorithm with Ö V Ek=1 of d2) regret. Both VOFUL and VOFUL22 do need to know the variance information. However, they are computationally inefficient since they need to work with nonconvex confidence sets defined by a series of second-order constraints, and do propose polynomial-tin
algorithm to solve the maximization problem over these sets. With the variance information, Zhou et al. (2021a) proposed a computationally efficient WeightedOFUL
with Odd Σ Ek=1 of
vdk d) regret. Our work under the same assumptions as Zhou et al. (2021a) and improves the regret for linear bandits.
Horizon-free tabular RL. RL is widely believed to be harder than contextual bandits problem due to its long planning horizon and the unknown state transitions. For tabular RL, under the assumption that the total reward obtained by any policy is upper bounded by 1, Jiang and Agarwal (2018)
conjectured that any algorithm find an e-optimal policy needs to have polynomial dependence on the planning horizon H in the sample complexity. Such conjecture was firstly refuted by Wang et al. (2020) by proposing horizon-free algorithm with an complexity that depends on H polylogarithmicall,, where e is the target sub-optimality the policy, S is the state space and A is the action space. Zhang et al. (2021b) proposed a near-optimal algorithm with improved regret O ((V + | [A] polyyoo (H) and sample complexity. Similar
polyyoog
(oolyloog(H)) ()) sample
3

---

regret/sample complexity guarantees with a polylogarithmic H dependence have also been established under different RL settings (Zhang et al. 2020; Ren et al.) 2021; Tarbouriech et al.) 202T). Recently Li et al. 2202 ;: Zhang et al. (2022) further proposed algorithms with #1-independent regret/sample complexity guarantees. However, all the above works are limited to tabular RI.. Our work proposes an algorithm with regret bound that depends on H polylogaritmmcally for linear mixture MDPs, which extends these horizon- free tabular RL algorithms.
RL with linear function approximation. Recent years have witnessed a trend on RL with linear
function approximation (e.g., Jiang al. [017]] Dann et al. 2018 Yang and Wang 2019a Jin et al.
2020; Wang et al., 2019 Du et al. 2019] Sun et al.
2019
Zanette et al. 2020a b Weisz et al. [2020]
Yang and Wang 2019b Modi et al. 2020 Jia al. 2020 Ayoub et al. |020 Zhou et al., 2021b). All
these works assume that the MDP enjoys some linear representation and propose different statistical
and computational complexities which depend on the dimension of the linear representation. Among these assumptions, our work falls into the category of linear mixture MDP which assumes that the transition dynamic can be represented as linear combination of several basis transition probability functions (Yang and Wang 2019b; Modi et al. 2020 Jia al.) 2020; Ayoub al.
2020; Zhou et al., on the episode horizon H (Yang and Wang 2019b; Modi et al. 2020 Jia et al.
2021b). Previous algorithms for linear mixture MDPs either suffer from a polynomial dependence
2020; Ayoub et al.)
2020; Zhou et al., 2021b; Cai et al. 2019 He et al. [0021] Zhou et al. 202 la or do not have a
computationally efficient implementation (Zhang et al. 2021c Kim et al. 202 the best of both worlds for the first time.
Our work achieves
3 Preliminaries
3.1 Heterogeneous linear bandits
We consider the same heterogeneous linear bandits as studied in Zhou et al. 2021 Let (Dx j- be decision sets that fixed. At each round k the agent selects an action a& É Da satisfying ||a || S A, then receives a reward F4 provided by the environment. Specifically, r& is generated by Tk = (0", ag) + Ek. where 0" E Rd is an unknown vector, and Eg is a random noise satisfying
Vk. lex| S R, E| <1=--]] = 0, Ele laikk <1 - o
where os is an upper bound of the variance of the noise eg that are observable to the agent. We assume that σg is (a1:ks (1.t-1)- The agent aims to minimize the pseudo-regret defined as follows:
Regret(K) (K) = E(aa 0*) (ak, 0²)], where a argmax(a, 0*).
aED;
km
3.2 Episodic reinforcement learning
We also study RL with linear function approximation for episodic linear mixture MDPs. We introduce the necessary definitions of MDPs here. The reader refer to Puterman (2014) for more details.
Episodic MDP. We denote a homogeneous, episodic MDP by a tuple M (S, A, H,,, where S is the state space and A is the action space, H is the length of the episode, r : S x A [0, is the deterministic reward function, and P is the transition probability function. For the sake of simplicity, we restrict ourselves to countable state space and finite action space. A policy collection of H functions, where each of them maps a state s to an action a.
(m,, [ is
Value function and regret. For (s, a) E S x A, we define the action-value function Q77 a) and (state) value function VA (s) as follows:
H
r(sw, ane) = =, 8M ~ P(-|sk-11, (1,90-1,000-1)) (1), an Th (hr(s )
@7(8, a) = E
(x) (s),, V =0
The optimal value function (-) and the optimal action-value function ()(())) are defined by (s) sup, Vi (s) and (s, -sup, Q% (s, a), respectively. For any function V : S - R.

---

we introduce the following shorthands to denote the conditional variance of V at P())s.a):
[PV a) = (,,,a()),,a)) (s'), [VV](s, a) = [PV) -
where V stands for the function whose value at is (s). Using this notation, the Bellman equations for policy æ and the Bellman optimality equation can be written as
(% a) r(s, a) + (Pls,) a), (%,s as) + (s)
The goal is to minimize the K -eepiodee regret defined as follows:
K
Regret(K) (K)
Σ (VT - VT (st)).
In this paper, we focus on proving high probability bounds on the regret Regret( ()).
In this work we make the following assumptions. The first assumption assumes that for any policy, the accumulated reward of an episode is upper bounded by which has been considered in previous works (Krishnamurthy et al., 2016 Jiang and Agarwal, 2018). The accumulated reward assumption ensures that the only factor that can affect the final statistical complexity the planning difficulty brought by the episode length, rather than the scale of the reward.
Assumption 3.1 (Bounded total reward). For any policy æ, let {sh, ah 1H be any states and actions h==
satisfying a₁ (5%)) and $/41 P(-]s), a,). Then we have 0 S Σ r(sh, an.) S 1.
Next assumption assumes that the transition dynamic enjoys a linearized representation w.r.t. some feature mapping. We define the linear mixture MDPs (Jia et al. 2020 Ayoub et al. 2020 Zhou et al. 2021b) as follows.
Assumption 3.2 (Linear mixture MDP). M is an episodic B-bounded linear mixture MDP, such that there exists a vector 0" E IRd and Φ(1 -) such that (S''sss ss a) = (ø(s'|s: is. a). 0*)) for any state-action- next-state triplet (s, a, s') E x A S. Meanwhile, ||0 1l2 I B and for any bounded function
V S + [0, I] and any tuple (s, a) E S A, we have
[ a)l2 S 1, where Φv(8 = Σ ((
SES
Lastly, for any V : S [0, 1]. Φv can be calculated efficiently within O time.
Remark 3.3. key property linear mixture MDP is that for any function V S - E and any state-action pair (s, a). the conditional expectation of V over P(-[s, a) is linear function of 0*, i.c. [PV] a) = (Øv a). 0*). Meanwhile, the conditional variance of V over P(-|s, a) a quadratic function of 0" i.e., [VV] (s. = (Φv= 0), (sv (3)]3
Remark 3.4. For general class of d, ( S A + Rd can be computed efficiently + I can be computed efficiently. For instance, ((s'1s,a) a) e,',a,a |IAHAA and (f (issss.a a) = (ss') ) @ (ss, where $ are two sub feature functions. More discussions are referred to Zhou et al. (2021a).
for any (8, a) E S A
4 Computationally efficient variance-aware linear bandits
In this section, we propose our algorithm WeightedOFULL" in Algorithm for the heterogeneous linear bandits introduced in Section 3.1 WeightedOFUL + adopts the weighted ridge regression estimator used by WeightedOFUL (Zhou et al. 2021a). but uses refined weight. first computes weighted estimate of 6*, denoted by 0x, based on previous contexts and rewards, where the weights ōe are computed by the noise variance σkk Then WeightedOFUL constructs the confidence set of 0*, denoted by Cg, estimates the reward (a, 0) for 0 E Cx. and selects the arm that maximizes the estimated reward optimistically. The selection rule of ag is identical to selecting the best arm w.r.t. to their upper confidence bound, i.e., a& <- argmax (a, 0&) + &allalls.- (Li et al. 2010). WeightedOFUL.* constructs of as the maximization of the variance, a constant, and the uncertainty || as defined in (). Note that Zhou et al. (021a) proposed a variance-aware weight Tg max a} for heterogeneous linear bandits. T The additional uncertainty term in weight
5

---

Algorithm 1 WeightedOFUL"
Require: Regularization parameter À > 0, and B, an upper bound on the m--norm of 0", confidence
radius Ss. variance parameters a,
1: Σ < AI, b <- 0, 0 +- 0, 31 VBB
2: for k == ......... K do
3: Let C2 - (0: |
1 02) - B.]. observe De
4: Set (ak, 0₂) s argmax DeD (a.
5:
Observe (Tk: ok), 0k
f- max 71kkkl 1/2 [
(4.1)
6: Σx+1 + Ex + a,a /0 1et1 by t Oct1 Extt
7: end for
enables us to build tighter confidence set C2 since the uncertainty of arms can be leveraged by tighter Bernstein- type concentration inequality (See Section 4.1 for details). Meanwhile, notice that He et al. (2022) proposed a pure uncertainty-awen weight 0₁ max(a, 7 y/|ax (-1) to
deal with the corruption contextual linear bandits, which serves different purpose compared to setting (there is no corruption in our bandit model).
The following theorem gives the regret bound WeightedOFUL".
Theorem 4.1. Let 0 < 8 < 1. Suppose that for all h: 2 1 and all DR. (a, 0*) E [-1,1],
|001|2 < B and (3x x21 are
B2 12 dloog1
11)2//)
+ 30 (ogg((((og(()"//)) [1) +
(4.2)
Then with probability at least 1 - 8, the regret of WeightedOFUL" + is bounded by
Regret(K) 4di + 4d7 + 43x Ek Ka² Vdi,
(4.3)
where , = log(1 + K A /A//(dAa' (d)a²)). Moreover, setting a = 1/VK, 12/2 /d// and X = d/B²
yields high probability regret Regret K) Ö(dy Σ of + dR + d).
Remark 4.2. Treating A as a constant, the regret of WeightedOFUL becomes OOd Ek=1 +
It strictly outperforms the Öldy E of + V dk + d) regret achieved in Zhou et al. 2021a)
Compared with the 0 V EK of dd) regret by VOFUL (Zhang et al. 2021c and the Ö V VE + d)) regret by VOFUL2 (im et al. 2021), the regret of WeightedOFUL has better dependence on d, and WeightedOFUL" is computationally efficient. It is worth noting that both VOFUL and VOFUL2 do not need know the variance of while our algorithm does.
Whether there exists algorithm that achieve the Ö(d/I Ek=1 of VdK d') regret without knowing the variance information remains open problem.
4.1 Proof sketch
We give proof sketch of Theorem 4.1 along with two key lemmas that are pivotal to obtaín the improved regret. To begin with, we first show that 0" belongs to confidence balls centering at 0 with radius 3x. This can be proved by the following lemma, which is an improved version of the Bernstein- -type self-normalized martingale inequality proposed by Zhou et al. (2021a).
Lemma 4.3. Let ) == be filtration, and {xt: Mis hez1 be stochastic process such that x Rd is G. -e-mauuurablee and 7k IR is Ga+11 measrrable.. Let A,E 0, n² gd For & > 1, let

---

9k = (x)) + and suppose that 17, also satisfy
[[m = 0, Elvi Gial - o², |mal S R. |xxll2 S L.
(4.4)
For 2 1, let 24 = A1 Σ x by
Vixi, Me = Zx bb. and
8 do + (d)) log (log R/e) + 1))2
(32 + 1)k² /8)
max isisk
{1aal min (L, ||x lzz }} + 6 6log((2(1og((//)) 1)k² 18)c.
Then, for any 8 < we have with probability least that,
A 2 1, E xma S 3k. ll - 1e" llze S Bk + VAllp0
Note that 02 can be regarded as 14-1 in Lemma 4.3 with R/72, X au/Ok. yh - =k/ōkk V): / Zn Σx+1 and f 0" With the help of the weight ds, the variance of yn is upper bounded by 1 (since og σ%2) and lmx min ||x 1
lex/l a S 1/0 R/y² (since o. 2 - Therefore, by Lemma 4.3 w.h.p. 0 E C.. Following the standard procedure to bound the regret of the optimistic algorithm (Abbasi- Yadkori et al. 2011). we have
Regret( K)
Σ (ah ak, 0-) 2
min 1| s.
(4.5)
Next lemma gives an upper bound of 44.5
Lemma 4.4. Let (ak, 32 be sequence of non-negative numbers, a, 0, (ax)21 Rd and |ax l| H A. Let {ōx and {Ex 1x21 be (recursively) defined as follows: Σg = AI,
Vk 2 σx max a, 7 aas ( EK41 Ex a
Let / = log(1 + A (d2/(()a2))) Then we have
min {1, Be falllllss S 2de + 2 max Σ
3 2vdi kE[K]
Σ
3 (o + a2).
1=1
k=
By Lemma 4.4 the regret of WeightedOOFL can be bounded by
Regret(K)) Ö(d vdšx /V o2 ka² + vo+2))
(4.6)
with 3x- Ö(Vo+ + VXB), which finishes the proof.
Here we compare the regret of WeightedOFUL* and the regret of WeightedOFUL Zhou et al. 2021a) (which chooses the weight o = max(ok, a.) to see where the improvement comes from. In particular, Zhou et al. 2021a) proved the regret of WeightedOFUL.
follows
Regret(K) K)) = Ō(d + vdzg
ΣK Ka²)
(4.7)
with 34 = o(và R/a + VBB. At the first glance, both (4.6) and 4.7 have a Ka² term. However, thanks to the design of ã and Lemma 4.3 the K term in (4.6) can be shaved by choosing small enough a, while this term in (4.7 cannot be shaved due to the existence of R/a term in Za
Computationally efficient horizon-free RL for linear mixture MDPs
In this section, we propose a horizon-free RL algorithm HF-UCRL-VTR* Algorithm We leave the discussion of the computational complexity of HF-UCRLLVTRR* to Appendix B
HF-UCRI-VTRR follows the value targeted regression (VTR) framework proposed by Jia al. 2020); Ayoub et al. (2000) to learn the linear mixture MDP. In detail, following the observation in
7

---

Algorithm 2 HF-UCRL-VTR"
Require: Regularization parameter an upper bound of the norm of 0", confidence radius (3x)22 level M, variance parameters a, 7, [M] = ,O,...,A,, M -13 1: For E [M], set 1..m <- O. E0,H+1, +- AI, bo, +- O. Set V1,++1(+) <
2: for 1...., ; K do
3: for h = H
do
Set (. - (r(.)) + OV (v... By Exp ov (..)) 10.11
4:
5: Set k (-) -- argmax Qu,((,a)
6: Set V., + maNNEA Qu.)(;a))
7:
end for
8:
Receive st. For m E [M], set En.i, f Ex-1,H+im
9:
for h = I....,,H H do
10: Take action a + T receive shit1 P((lsh a at)).
11:
For m E [M]. denote @, = Øven (fi).
Set {ō MEE Algorithm 3 3 Ok Ok h. En. fammmettn meM BR. a,
12:
13:
For [M], set I,, Ekhm + H k. o k.
14: For m [M]. set bRA+I.m + Da + ΦR n. k,b 1 1
15: end for
For m E [M], set Em t Et, Da + 1,, Ox+1on + 2 k,tlm batt.
end for
VTR estimates O" by solving regression problem predictors/comtexts Φk,4.0 @ven++ (sf, ) and responses Ve,A+1 ( Specifically, HF-UCRL-VTR* takes the estimate 0k.0 as the solution to the following weighted regression problem:
Remark 3.3
0 argmin
11
k- ンj=1 Σ [ (sh+z1(hh1)))// /o).
(5.1)
6ERd
where J,h, is the upper bound of the conditional variance [VVe.t+1lss at)) Such weighted regression scheme has been adapted by UCRL-VTR in Zhou et al. (2021a). With 2x HF-UCRL-VTR" then constructs the optimistic estimates Qu. (resp. VV.N) of the optimal value functions 07 (resp. ViA and takes actions optimistically. Note that Ok.o is updated at the end of each episode. We highlight several improved algorithm designs of HF-UCRL-VTR** compared UCRL-VTR as follows.
Improved weighted linear regression estimator. HF-UCRL-VTR' sets 0jA.,0 similar to the weight used in WeightedOFUL" Assuming that the conditional variance [VV2, 1 (s f, at) can be computed for any value function and state action pair (s,a), then the weight can be set as
2
kko = max (VV a a², PI
2 k, ok.ooll2h
where Ek.h. the weighted sample covariance matrix of Φk,h,o o up to k-th episode and h-th stage. However, the true variance is not accessible since P(-|s, a) is unknown. Therefore, UF-UURL-VTR replaces [VVR, (s att with its estimate [V V...oVk... Vk ( af) and error bound Ex,A,O satisfy- ing [V Ve, (s ag) ) + FR,A. 2 [VV 1 (s) h at) with high probability. Thanks to the fact that
[VVi, [6 af) is quadratic function of 0* illustrated in Remark 3.3
[V VR 1 at)
can be estimated as follows:
W VR.oV,,4+](55 a =
(((c))=((((a))))) [( )n. [..1 - ( 0 o..1
(5.2)
where 0g.1 is the solution to some regression problem over predictors/contexts ΦK,A.1 Φv (s) af) and responses (=
Higher-order moment regression. To obtain a better estimate, is natural to set θR,1 the solution to the weighted regression problem on 0K,,,1 and 2 (5%+z) with weight h Here k 1 is

---

Algorithm 3 High-order moment estimator (HOME)
Require: Features
(oI.hh, mejA vector estimators Ekyh.m: Lk.m M confidence radius Re. 0,
(Ox.m) OR.m)meTarrj me[a
covariance matrix
1: for m O....... M do
2: Set [V V2 (o af) f (...mmm1, On [0.1] [1 h. 1/2 $2 [12] + min {1,3x] 5
On m) [0.1]
3: Set Es,h.m + min {1,23r Σ k.m
3-1/2 1/2
2n mm 112]
k.
4: Set F.m.m max (V k. m V2 k (5 a + Ek.h,m 72
2 k.n.
1/2
Sb A.
5: end for
6: Set o 6.A.M- max (1, , y2
Σ
-112 1/2 K. 1
Ensure: (ōk,h,m)me
constructed in a similar way to KKA.O o. which relies on the conditional variance 2V2441l ) By repeating this process, we recursively estimate the conditional 2 -th moment of V by its variance, which is the conditional 2 -th moment of V4 high-order recursive estimation has been used in Li et al. (2020) and later in Zhang et al. (2021b to achieve horizon- -free regret/sample complexity guarantees. Similar recursive analysis also appeared in Lattimore and Hutter (2012).
worth noting that the idea of
The estimated conditional moment kV Vi 1 a relies on 0x.+1 and 2R.m. and (0x.t.m+1,0 m1)) serves as the estimate of the higher nigher-moment (VV2 (s) a The detailed
constructions for the high-order moment estimator are summarized in Algorithm
We provide the regret bound for HF-UCRL-VTTR* here.
Theorem 5.1. Set M log log For any d > O, set 13a as
3. (f
1)A211/0)
+ 30 10 + /0)/// VAB,
(5.3)
then with probability at least 1 (2M - the regret of Algorithm is bounded by
Reg < 12(8de + 43 //d K V M () + 864 max (3 M 2 2 [ (/loog(1/)) + 32 max{23 2dd, VCH VK,
where 6 = log(1 + KH/ (dHa))))))) Ç = Alog(4log(KH)//)
Moreover, setting a = /d/(KH), 1/d and À d B yields a high-probability regret Regret(K) Ö(dV ++ldk+dd)) +
Remark 5.2. The regret of HF-UCRL-VTR* is strictly better than that of VOFUL ( +d) Zhang et al. (2021c), and it matches the regret of VOFUL2 (Kim et al. 2021 More importantly, HF-UCRL-VTR is computationally efficient, while there is no efficient implementation of VO- FUL/VOFUL2.
Next theorem provides the regret lower bound and suggests that the regret obtained by HF-UCRL-VTR* is near-optimal. The lower bound is proved by constructing hard-instances of linear mixture MDPs following Zhou et al. (0021b Zhang et al. (2021a).
Theorem 5.3. Let B Then for any algorithm, when 2 max (3d2 (d 1)/(122(BB - 1))}- there exists B- bounded linear mixture MDP satisfying Assumptions 3.1 and 3.2 such that its expected regret E[[Rgreet( K)) is lower bounded by dyk/ K/(16/3).
Remark 5.4. When specialized to tabular MDPs where d = |S| LAI. HF-UCRL-VTR yields horizon-free regret ((IS/2|AAVV + (A))) Although the regret does match the near-optimal result Õ(v S||A| + LA)) Zhang et al. 2021b). it is not surprising since HF-UCRL-VE is designed for more general MDP class. We leave the design of algorithms that achieve near-optimal regret for both linear mixture MDPs and tabular MDPs simultancously as future work.
We conduct some numerical experiments to suggest the validity of HF- in Appendix A

---

Conclusion
this work, we propose a new weighted linear regression estimator that adapts variance-umcertaine aware weights, which can be applied to both hetcrogeneous linear bandits and linear mixture MDPs.
For heterogeneous linear bandits, our WeightedOFUL" algorithm achieves O(dy E + regret in the first K rounds. For linear mixture MDPs, HF-UCRL-VTR algorithm achieves the near-optimal Odd/K K + d²) regret. Both of our algorithms are computationally efficient and yield the state-of-the-arr regret results.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments. DZ and QG are partially supported by the National Science Foundation CAREER Award 1906169 and the Sloan Research Fellowship. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
ABBASI- YADKOR,, Y., PÁL, D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems.
AUER, P. (2002). Using confidence bounds for exploitation-expllration trade-offs. Journal of Machine Learning Research 397-422.
AYOUB, A., JIA, Z., SZEPESVARI, C., WANG, M. and YANG, L. F. (2020). Model-based reinforce- ment learning with value-targeted regression. arXiv preprint arxtv:2006.01007
AZUMA, K. (1967). Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series 19 357-367.
CAI, Q.. YANG, Z., JIN, C. and WANG, Z. (2019). Provably efficient exploration in policy optimization. arXiv preprini urXiv:
CHU, W., LI, L., REYZIN, L. and SCHAPIRE, R. (2011), Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics.
DANI, V., HAYES, T. P. and KAKADE, S. M. (2008). Stochastic linear optimization under bandit feedback. In Conference on Learning Theory.
DANN, C., JIANG, N., KRISHNAMURTHY, A., AGARWAL, A., LANGFORD, and SCHAPIRE, R. E. (2018). On oracle-efficient pac rl with rich observations. In Advances in neural information processing systems.
DU, S. S., KAKADE, S. M.. WANG, R. and YANG, L. F. (2019). Is a good representation sufficient for sample efficient reinforcement learning? International Conference on Learning Representations.
DZHAPARIDZE, and VAN ZANTEN, (2001). On bernstein-type inequalities for martingales. Stochastic processes and their applications 93 109-117.
FAN, X., GRAMA, I. and LIU, Q. (2017). Martingale inequalities of type dzhaparidze and van zanten. Statistics 51 1200-1213.
HE, J., ZHOU, D. and Gu, Q. (2021). Logarithmic regret reinforcement learning with linear function approximation. In International Conference on Machine Learning. PMLR.
HE, J.. ZHOU D., ZHANG, and GU, Q. (2022). Nearly optimal algorithms for linear contextual bandits with ad adversarial corruptions. arXiv preprint 22Xi::2205.06811
10

---

JIA, Z., YANG, L., SZEPESVARI, C. and WANG, M. (2020). Model- reinforcement learning with value-targeted regression. L4DC.
JIANG, N. and AGARWAL, A. (2018). Open problem: The dependence of sample complexity lower bounds planning horizon. In Conference On Learning Theory. PMLR.
JIANG, N., KRISHNAMURTHY A., AGARWAI, A., LANGFORD, J. and SCHAPIRE, R. E. (2017). Contextual decision processes with low Bellman rank are PAC-Icarnble. In Proceedings of the 34th International Conference on Machine Learning- Coarning-Volume 70, JMLR. org.
JIN, C., ALLEN-ZHU, Z., BUBECK, S. and JORDAN, M. I. (2018). Is Q-learnigg provably efficient? In Advances in Neural Information Processing Systems.
JIN, C., YANG, Z., WANG, Z. and JORDAN, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory.
KIM, Y., YANG, I. and JUN, K.-S. (2021). Improved regret analysis for ariince-addppivv linear bandits and horizon-free linear mixture mdps. arXiv preprint arXiv:2111.03289)
KIRSCHNER, and KRAUSE, A. (2018). Information directed sampling and bandits with het- eroscedastic noise. In Conference On Learming Theory.
KRISHNAMURTHY, A., AGARWAL, A. and LANGFORD, J. (2016). Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems 29.
LATTIMORE, T., CRAMMER, K. and SZEPESV ÁRI, C. (2015). Linear multi-resource allocation with semi-bandit feedback. Advances in Neural Information Processing Systems.
LATTIMORE, and HUTTER, M. (2012). PAC bounds for discounted MDPs. In International Conference on Algorithmic Learning Theory. Springer.
LI, G., WEI, Y., CHI, Y., GU, Y. and CHEN, Y. (2020). Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances neural information processing systems 33 12861-12871
LI, L., CHU, W., LANGFORD, J. and SCHAPIRE, R. E. (2010). A contextual-bandit approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web.
LI, Y., WANG, R. and YANG, L. F. (2022). Settling the horizon--ependencee of sample complexity in reinforcement learning. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE.
LI, Y., WANG, Y. and ZHOU, Y. (2019a). Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory.
LI, Y., WANG, Y. and ZHOU, Y. (2019b). Tight regret bounds for infinite-armed linear contextual bandits. arXiv preprint
MODI, A., JIANG, N., TEWARI, A. and SINGH, S. (2020). Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics. PMLR.
PUTERMAN, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
REN, T., LI, J., DAI, B., DU, S. S. and SANGHAVI, S. (2021). Nearly horizon-fiee offline reinforcement learning. Advances neural information processing systems 34.
STREHI., A. and LITTMAN, I.. (2008). An analysis of model-based interval estimation for Markov decision processes. Journal of Computer and System Sciences 74 13311
SUN, W. JIANG, N., KRISHNAMURTHY, A., AGARWAL, A. and LANGFORD, J. (2019). Model- based RI. in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on Learning Theory. PMLR.

---

TARBOURIECH, J., ZHOU, R., DU, S. S., PIROTTA, M., VALKO, M. and LAZARIC, A. (2021). Stochastic shortest path: Minimax, parameter-free and towards horizon- regret. Advances in Neural Information Processing Systems 34.
WANG, R., DU, S. S., YANG, L. F. and KAKADE, S. M. (2020). Is long horizon reinforcement learning more difficult than short horizon reinforcement learning? arXiv preprini arXiv:2005.005:
WANG, Y., WANG, R., DU, S. S. and KRISHNAMURTHY, A. (2019). Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:1912.041: 19111.11.36....
WEISZ, G., AMORTILA, and SZEPESVÁRI, C. (2020). Exponential lower bounds for planning in MDPs with linearly-rcalizablle optimal action-value functions. arXiv preprint arXiv:2010.01374.
YANG, L. and WANG, M. (2019a). Sample-optinal parametric Q-learning using linearly additive features. In International Conference on Machine Learning.
YANG, L. F. and WANG, M. (2019b). Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. arXiv preprint arXiv: /905. 1038.
ZANETTE, A., BRANDFONBRENER, D., BRUNSKILL, E.,, PIROTTA, M. and LAZARIC, A. (2020a). Frequentist regret bounds for randomized least-squares value iteration. International Conference on Artificial Intelligence and Statistics.
ZANETTE, A., LAZARIC, A., KOCHENDERFER, M. and BRUNSKILL, E. (2020b). Learning near optimal policies with low inherent Bellman error. arXiv preprint arXiv:2003.00153
ZHANG, W., ZHOU, D. and Gu, Q. (2021a). Reward-fres model-based reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems 34.
ZHANG, Z., DU, S. S. and J1, X. (2020). Nearly minimax optimal reward-free reinforcement learning. arXiv preprint arXiv:2010.05901.
ZHANG, Z., J1, X. and Du, S. (2021b). Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference Learning Theory. PMLR.
ZHANG, Z., J1, X. and Du, S. S. (2022). Horizon-free reinforeement learning in polynomial time: the power of stationary policies. arXiv preprint arXiv:2203.1294
ZHANG, Z., YANG, J., J1, X. and Du, S. S. (2021c). Improved variance-awarc aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems 34.
ZHANG, Z., ZHOU, Y. and J1, X. (2021d). Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. In International Conference on Machine Learning. PMLR.
ZHOU, D., GU, Q. and SZEPESVARI, C. (2021a). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR.
ZHOU, D., HE, J. and GU, Q. (2021b). Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning. PMLR.
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] Our paper proposes a computational efficient and horizon- free RL algorithm for linear mixture MDPs.
(b) Did you describe the limitations of your work? [Yes] See Remark 4.2
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump-
tions and
(b) Did you include complete proof' of all theoretical results? [Yes] See Appendix and
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(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]
4. If you using cxisting assets (c.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(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're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "yZjVa6YHtyB", "reviewer": "Reviewer_xqq7", "summary": "This paper gives the first computationally efficient horizon-free algorithm for linear mixture MDPs, which achieves the optimal $O(d\\sqrt{K} + d^2)$ regret up to logarithmic factors. Their technique can also be applied to heterogeneous linear bandits and achieve $d\\sqrt{\\sum_{k=1}^K\\sigma_k^2} + d$ regret when the reward variance $\\sigma_k^2$ is known.", "questions": "Can this technique be applied to linear MDP and achieve horizon-free regret?", "limitations": "Nothing necessary stands out.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper solves a very important open problem in RL with linear function approximation: getting horizon-free regret bound efficiently. The developed techniques can potentially be applied to many other problems and improved current results. The algorithm also has a simple structure and thus easy to implement and extend. Discussions on related work and implications of results are thorough and well presented. \n\nGiven that the algorithm is simple enough, it would be beneficial to also perform experiments to verify the theoretical gain.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vSF0pzbocv", "reviewer": "Reviewer_yBHw", "summary": "This paper extends the previous work [1], by proposing a novel variance-aware and uncertainty-aware weight in the weighted least square regression to provide an improved analysis on the heterogeneous linear bandits and linear mixture MDPs, that can be computational efficient for linear mixture MDPs and for the case when we have an upper bound of the noise scale in heterogeneous linear bandits. The key observation is that, by introducing the additional uncertainty aware terms in the weight, we can have much tighter confidence set when $\\sigma_k$ is small and $K$ is large, as illustrated in Lemma 4.3 and Line 213-216.\n\n[1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. \"Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.\" Conference on Learning Theory. PMLR, 2021.\n", "questions": "* This paper is in general good. Mainly I hope the authors provide more intuition and discussion on Lemma 4.3, especially how it compares with the self-normalized martingale concentration inequality in [1]. It may not be so simple for the potential audience to understand the motivation.\n\n* Additional Minor Issues:\n* * Please check the input of the algorithm. Some hyperparameters should appear in the input part (e.g. $\\alpha$ and $\\gamma$ in Algorithm 1).\n* * It would be better if the authors can make some additional discussions on the work without the assumption of known variance. As far as I know, unlike the authors claim in Line 84-87, both Zhang et al. and Kim et al. do not require an upper bound of $\\sigma_k^2$. And to deal with this issue, they need to work on the noise concentration and use some peeling techniques to construct the confidence set. I hope the authors make this distinction clear.\n\n[1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. \"Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.\" Conference on Learning Theory. PMLR, 2021.\n", "limitations": "This paper is on the theory side and does not need to address the societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n* Simple but clear theoretical results.\n* Well-written in general.\n\n### Weaknesses:\n* The authors do not provide so much intuition on the key results (Lemma 4.3). I think it deserves much more discussion.\n* A minor concern: the part other than Lemma 4.3 is not technically significant.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "b7LJSpS3NgV", "reviewer": "Reviewer_XjDu", "summary": "This paper proposed a computationally efficient horizon-free RL algorithm.", "questions": "1. If the cumulative reward is bounded by H, will the bound still be independent of H? ", "limitations": "no", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The writing needs improvements and the notation is a bit heavy. The contribution is not very significant. UCRL-VTR itself is not computationally-efficient beyond linear case, as pointet out in \"Model-Based Reinforcement Learning with Value-Targeted\nRegression\".\n\nI feel the algorithm used in this paper does not show significant improvement over the one in \"Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.\" The weighted OFUL+UCRL VTR is almost the same. The improvement of regret bound for linear bandit is not huge since dsqrt{sum sigma_i^2} term is the leading term. \n\nThe main trick to obtain horizon-free bound seems to be cumulative rewards bounding by [0, 1] + variance-aware confidence interval. This is known before and this paper seems to offer no new message in my mind. \n\nI think Algorithm 2 heavily relies on linear mixture MDP assumption. That means you assume the complicated environment enjoys a quite simplified parametric form. If your algorithm is general but you use linear mixture MDP as a sanity check, that's fine. But the algorithm now is designed for linear mixture MDPs.\n\nSince the paper claims the major contribution is computational-wise, I feel some simple experiments are needed. It is unclear what's the empirical performance since it is not built on any algorithm that is widely empirically evaluated. It will be good to observe what's the meaning of horizon free on existing benchmarks. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "QZdINLxhI_9", "reviewer": "Reviewer_Z3Fm", "summary": "This paper studies the problem of Episodic Linear Mixture MDPs, where the transition model is a linear combination of $d$ valid MDP transition models. The MDP has a countable set of states and a finite set of actions, and the cumulative reward in each episode is not larger than $1$. The agent interacts with the MDP for $K$ epsidoes, and the planning horizon is $H$ for each episode. As a warm-up, this paper gives an algorithm WeightedOFUL$^+$ for heterogeneous linear bandits. It is computationally efficient and achieves a state-of-the-art $\\tilde{O}(d \\sqrt{\\sum_{k=1}^K \\sigma_k^2} + d)$ regret, where $\\sigma_k$ is the variance of noise in episode $k$ (assumed to be known). The main result is a computationally efficient algorithm, HF-UCRL-VTR$^+$, for Linear Mixture MDPs. It achieves a $\\tilde{O}(d \\sqrt{K} + d)$ regret, matching the lower-bound given in this paper.", "questions": "None.", "limitations": "None.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper improves upon previous results of Linear MABs and Linear Mixture MDPs by giving computational efficient algorithms with matching state-of-the-art regrets. For Linear Mixture MDP, this paper also provides a tight lower-bound.\n2. This paper is clearly written. The comparison between different works is straightforward.\n3. This work is significant because it nearly closes the problem of Linear Mixture MDP.\n\n\nWeaknesses:\n1. WeightedOFUL$^+$ needs knowledge of $\\sigma_k$, which is in general not practical, otherwise, it would degenerate into $d\\sqrt{K}$.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept