Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs
Authors: Yeoneung Kim
Insoon Yang
Kwang-Sung Jun
Venue: NeurIPS 2022 Accept (2022)
Keywords: linear bandits
MDP

Abstract:   In online learning problems, exploiting low variance plays an important role in obtaining tight performance guarantees yet is challenging because variances are often not known a priori.
  Recently, considerable progress has been made by Zhang et al. (2021) where they obtain a variance-adaptive regret bound for linear bandits without knowledge of the variances and a horizon-free regret bound for linear mixture Markov decision processes (MDPs).
  In this paper, we present novel analyses that improve their regret bounds significantly.
  For linear bandits, we achieve $\tilde O(\min\{d\sqrt{K}, d^{1.5}\sqrt{\sum_{k=1}^K \sigma_k^2}\} + d^2)$ where $d$ is the dimension of the features, $K$ is the time horizon, and $\sigma_k^2$ is the noise variance at time step $k$, and $\tilde O$ ignores polylogarithmic dependence, which is a factor of $d^3$ improvement.
  For linear mixture MDPs with the assumption of maximum cumulative reward in an episode being in $[0,1]$, we achieve a horizon-free regret bound of $\tilde O(d \sqrt{K} + d^2)$ where $d$ is the number of base models and $K$ is the number of episodes.
  This is a factor of $d^{3.5}$ improvement in the leading term and $d^7$ in the lower order term.
  Our analysis critically relies on a novel peeling-based regret analysis that leverages the elliptical potential `count' lemma. 

Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs
Yeoneung Kim" Gachon University yeoneungogachon. ac kr
Insoon Yang Scoul National University insoonyangdsnu. ac kr
Kwang-Sung Jun University of Arizona kjunθcs arizona. edu
Abstract
In online learning problems, exploiting low variance plays an important role obtaining tight performance guarantees yet is challenging because variances often not known a priori. Recently, considerable progress has been made by Zhang al. (2021) where they obtain variance-adaptive adaptive regret bound for linear bandits without knowledge of the variances and a horizon-free regret bound for linear mixture Markov decision processes (MDPs). In this paper, present novel analyses that improve their regret bounds significantly. For linear bandits,
we achieve Ó(min ad//Kdl .d..5 VER- of)) + d²) where d is the dimension of the features, K is the time horizon, and of the noise variance time step k, and Ô ignores polylogarithmic dependence, which factor of d3 improvement. For linear mixture MDPs with the assumption of maximum cumulative reward in an episode being in [0.1]. we achieve horizon-free regret bound of Ö(dv K d)) where is the number of base models and K is the number of episodes. This is a factor of 8 improvement in the leading term and d' in the lower order term. Our analysis critically relics on novel peeling-based regret analysis that leverages the elliptical potential 'count" lemma.
Introduction
In online learning, variance often plays important role in achieving low regret bounds. For example, for the prediction with expert advice problem, Hazan and Kale [1] proposed an algorithm that achieves regret bound of O(VVARk) where VAR is suitably-defined variance of the loss function up to time step K, without knowing VAR ahead of time. The implication that when the given sequence of loss functions has small variance, previously known regret bound O(VK). For multi-armed bandits, Audibert et al. ( proposed algorithm that achieves regret bounds that depends on the variances of the arms, which means that, again, the regret bound becomes smaller the variances become smaller.
can perform much better than the
is thus natural to obtain similar variance-adaptive bounds for other problems. For example, in d- dimensional stochastic contextual bandit problems, the optimal worst-case regret bound is (addK) where Ô hides polylogarithmic dependencies and o² a uniform upper bound on the noise variance. Following the developments in other online learning problems. it natural ask if can develop a similar variance-adaptive regret bound. The recent work by Zhang et al. [31] has provided an
affirmative answer. Their algorithm called VOFUL achieves a regret bound of ( //EK of +d) where of is the (unknown) noise variance at time step This implies that, indeed, possible
* Work done while Scoul National University.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to adapt to the variance and suffer much lower regret. Furthermore, they show that similar variance-adaptive analysis can be used to solve linear mixture Markov decision processes (MDPs) with the unit cumulative rewards assumption:
(I)
where rf is the reward received at episode k and horizon h. They show regret bound of Ö(d'. d²), which does not depend on the planning horizon length H up to polylogarithmic factors. We elaborate more on the linear bandit and linear mixture MDP problems in Section _
However, the regret rates of these problems have a large gap between the known lower and the upper bounds. For example, in linear bandits, it is well-known that the regret bound has to be (2dv ((dvK) [6].
which rejects the possibility of obtaining od Ex= ot) yet the best upper bound obtained so far is Odd V o Thus, the gap is a factor of d which is quite large.
In this paper, we reduce such gaps significantly by obtaining much tighter regret upper bounds. Specifically, we show that slight variation of VOFUL [31] for linear bandits has a regret bound of O(min/d/K, d EEE1))) without knowledge of the variances. This reduces the gap between the upper and lower bounds to only vid for the leading term in the regret. Furthermore, we employ a similar technique to show that the algorithm VARLin [3I for linear mixture MDPs with unit cumulative rewards has a regret bound of Ó(dv ((dKK+d")) +d²). At the heart of our analysis is a direct peeling of the instantaneous regret terms using an elliptical potential 'count' lemma (EPC). EPC bounds, given g 0, how many times | V 2 happens from time ls 1 to where V Σ xga
Our lemma is an improved and generalized version of [6, Exercise 19.3], which was originally used for improving the regret bound of linear bandit algorithms. We provide the proofs of our main results for linear bandits and linear mixture MDPs in Section 3 and Section respectively. Finally, we conclude the paper with exciting future directions.
Related work. There are numerous works on linear bandit problems such as 66 17] where the information of variance is not used. On the other hand, variance can be exploited to obtain better regret [2]. Recently, works by [3 33] proposed ways to infuse the variance information in the regret analysis which improves the standard regret bound. Reinforcement learning with linear function approximation has been widely studied to develop efficient learning methods that work for large state-action space (27 26
28 To our knowledge, all aforementioned works derived a regret bound that depends on the planning horizon H polynomially. It was Zhang et al. 31 who first remove the polynomial dependence of H in the linear mixture MDP problem, achieving bound of O(d algorithm in fact achieves significantly better bound of Ö(dv + dd). Note that these results assume the unit cumulative rewards assumption ( and tine-homogeneous transition models. In similar setup where Tb, e [0, with time-inhomogeneous transition models, Zhou et al. [3 achieve the H
14 23 24
25 29
15 21 10
dº). In contrast, our analysis shows that their
regret Ö(Vd'H + dH + d' H + d H²) and show a lower bound of 3/2))) These problem setups are incompatible the setup of [3 and ours.
Problem Definition
Notations. We denote d-dimensional &2 ball by (R) = fx S R) and define (R)
similarly for the & ball. Let [N] == (1, T,...... N] for N N. Given E R and e IR, we define the clipping operator as follows (take 0/0 0):
(x) min ||l.22 2-
T
(2)
Linear bandits. The linear bandit problem has the following protocol. At time step k. the learner observes an arm set X s (1). chooses an arm 2gg Xx. pulls it. The learner then receives a stochastic reward rı = x1 0 + < where 0* e (B)(1) is an unknown parameter and 6 is zero-mean stochastic noise. Following [1I, we assume that (i) Vk e [K], Irxl < [- 2 11
almost surely, (ii) [[ex[Fx] 0 where Fg o ( E1, .... Ek-1, and (iii B [[ = o

---

Note that the bound on [rk] implies that [cx] S 1 almost surely. Our goal is to minimize the regret R.K Eksl 2 x'6' 0* -000
Linear mixture MDPs. We consider an episodic Markov Decision Process (MDP) with a tuple (S, A, d,,(s,)). P( a), K, H)) where S is the state space, A is the action space, r: x A + [0.
the reward function, P(s"(s,a) is the planning horizon. A policy defined
the transition probability, K is the number of episodes, and H
{ S ((AA) h-1 where ((A) is set of all distributions over A. For each episode é [K]. the learner chooses a policy n², and then the environment executes x² on the MDP by successively following o m// (s%) and $ P(-ss, o)). the episode. The Then, the learner observes the rewards {rī [0,1]) k.A and moves key modeling assumption of linear mixture MDPs is that the transition probability P is a linear combination of known set of models {P'), namely, P = Σ 02 P where 0" (1) is an unknown parameter. We follow [31] and make the following assumptions:
The reward at each time step h and episode k is r = r( af) for some known function r:S x A - [0, 1].
Unit cumulative rewards: E r E [0. 1] for any policy n
For a policy n, (s) maxae 0%, (s. a) where (7(ss,) a) r(ss a) + RgmP((),o) (s') and
(s) := O. Denoting (*1 V/2 (s1) and (*1s)) V (s1), goal is to minimize the regret
K R
(s
3 Variance-Adaptive Linear Bandits
In this section, show that VOFUL of Zhang et al. 31] has tighter regret bound than what was reported their work. Our version of VOFUL, which we call VOFUL2, has a slightly different confidence set for case of exposition. Specifically, e (2) rather than over an c-net of (2) (but we do use an c-net for the proof of the confidence set).
use confidence set that works for every
The full pseudocode can be found in Algorithm VOFUL2 follows the standard optimism- based arm selection 3 1. Let e, (0) x0.0 and (0)
(0)) With L and defined in Algorithm
we define our confidence set after time steps as
O2 n $
where
O
0 B²():
Σ (ITN)) ( (0)
(00) Vp 1B((2)
and the clipping operator (z), is defined in (2) The role of clipping is two-fold: (i) it allows us to factor out Σ== (0) by Σ. (xTn), (0) s ( (0) and (ii) the lower order term is reduced to the order of f Both properties are critical in obtaining auriance-adaping regret bounds as discussed [1 The true parameter contained in our confidence set with high probability as follows.
Lemma 1. (Confidence set) Let L, and be given as those in Algorithm 7 Then,
P(E1 == (Ak E [K].0* A* E ex)) 2 5
In fact, in our algorithm, we use the confidence set of n at time step k for technical reason. VOFUL22 has the following regret bound.
Theorem 1. VOFUL2 satisfies, with probability at least 25,
K
R
of ln(11)) a mm(110))
3

---

Algorithm VOFUL2
1: Initialize: L = v 1og2( [)] where c 1251n((1222")<<10)) and ď òse E-
2: for k= 1,2,..., K do
3: Observe a decision set 2 S (B:(1).
4: Compute the optimistic arm as following: zy: arg ma max x'0 where θ, is
defined in (
5: Receive a reward rk-
6: end for
where Ô hides poly-logarithmic dependence on {d, K, E of In(1/6).
Note that one can also show that VOFUL2 can be slightly modified to achieve the regret bound of Ô (min {d/R K In(1/8), d V Ex of (n(/6)) of In(1/6)). thus being no worse than OFUL. We postpone the proof of this to Section A.4 to avoid clutter.
Properties of the confidence sets and implications on the regret. Before presenting the proof of Theorem we provide some key properties of our confidence set (Lemma 3 and the intuition behind regret bound. First, let us describe a few preliminaries. Define
2-
W Wi = 2 (
x
Let 0g be the maximizer of the optimization problem at line of Algorithm and define f4 = 0 8" For brevity, shorthand of
2-
W == Wek-- =
Σ
1
|rT Iz
Finally, we need define the following event regarding the concentration of the empirical variance around the true variance:
& Ea vk [K], Σ (0))
(K()
80
4log(
e=1
s=1
which is true with high probability as follows. Lemma 2. We have TPE2) 2 5
Proof. The proof is direct consequence of Lemma 13in in appendix.
Let la be the integer such that x zi,14 (2- 2- f 2-2-(+1 and define A₃ == E o². Lemma states the properties of our confidence set.
below
Lemma 3. Suppose the events & and Eg are true. Then, for any with Eg e.
(i) For some absolute constant C1.
l [uxliaan $2 V128A 11 11.2 3 c,2 (VA--11
(ii) There exists an absolute constant 02 such that ziu S 02l 02llza|l (VAr-1i+
The key difference between Lemma and the results of Zhang et al. [1 is that we use the norm notations, although the norm involves rather complicated matrix Wr,--- This opens up possibilities of analyzing the regret of VOFUL.2 with existing tools such as applying Cauchy-Schwarz inequality and the elliptical potential lemma (15 16). In particular, Lemma ( seems useful because if had such a result with W replaced by V--1 AI + I F.a. then we would have, ignoring the additive term f.
a aLuu |
Σ o3
mml

---

Together with the optimism and the standard elliptical potential lemma (see Section 3.1 for details), this leads
Rk Tall S 02
S 02. O(dloog(()))))) Σ m=1
Σ oz
Since is linear in d. we would get the regret bounded by the order of d V E of roughly speaking. However, the discrepancy between WLA1-1 and V is not trivial to resolve, especially due to the fact that Lemma F has 14 on both left and the right hand side. That is, μ4 is the key quantity that we need understand, but we are bounding Tk/kk function of pt- The novelty of our analysis of regret is exactly at relating W to Va-1 via novel peeling-batt based analysis, which we present below.
3.1 Proof of Theorem 1
Throughout the proof, we condition & and &2 where each one is true with probability at least 1 5. shown in Lemma D and respectively. For our regret analysis, it is critical to Lemma below, which we call the elliptical 'count' lemma. This lemma is a generalization of Lattimore and Szepesvári [16] Exercise 19.3], which was originally used therein to improve the dependence of the range of the expected rewards in the regret bound. Similar lemmas have been used in parallel studies
12 22. In particular, He et [12] employ a lemma similar to elliptical potential count and peeling technique for the regret analysis for the linear MDP as well, which we compare in detail in Section C due to space constraint. We remark that a similar strategy appears in disguise in Russo and Van Roy
220 Proposition 3] as well.
Lemma 4. (Elliptical potential count) Let Fi,..., I& IRd be a sequence of vectors with |æall2 X for all E [Re]. Let V₁ TT Eh Tgw, for some T > O. Let J S [1] be the set of indices where [x 1- q. Then,
2 M In(1 + dln
2/e X²
ln(1+g)
+
As the name explains, the lemma above bounds how many times | can go above given value q > O, which is different from existing elliptical potential lemmas that bound the sum of [ We start by the
Let 0% be the 0 that maximizes the optimization problem at line of Algorithm I usual optimism- based bounds: due to E,, we have
K
K
Rd
Σ
(max( 0" x)))))= naXi
Σ max x 10--100) 0-)
Σ 10 -8) Σ xf/u
k-1
1=11
We now take peeling based regret analysis that is quite different from existing analysis techniques:
K
Rk
Σ k=1
x (Ox 8*) 52
2- 2+2
Σ E e (2 (2-2 2,2-2- 2-1)1
E
k=1
where L is defined in Algorithm D Given E and k let nA,E be such that max,:ksesK..... f.-t [xT (2-etn, 2- 2-f-n+1] if such satisfies
1. Otherwise, set n& 0, which means max K.. 12 2- 2-ttme1 with n O. We then define Ge {s E [K-1] la n,,t n n) and let Ge, [k]===]]] = Ge, n [k]] Then,
K
Σ
{ p e (2-27 2.22
-
E144-4 E
1=1
7 aeGe.m
Letting Venn,-11 == 2- Evec n|k-1] F. a comparison between two matrices W and is given as follows for every e {k,...,") K):
b-1 We,-- 2
2-
2-
Σ
l^
Is 2 I+
Σ
In
I.T
rTpual
2 2-etnil
SeGeal
2 c- cc22 V
(4)
5

---

For E Ge 1nnnd u arg max w.s.s Meb we have
2- [lak//ul s l e.k. (Hw) Mu Wen
$ 2 we (mw) lalllwe 1(aa)
(u 2 k)
Lin V2 ( ())
$ cv 2d b
4 and Lemma 30
Consequently, |
Vo
2 c
2
AAciti"
Thus, using Lemma 4 with T= 2
| |ax Mi 2 2 2-
Σ Σ
1sl+>
E
Σ n koGee
VAKi+1
B= GekeG
s Σ 2
Age+ t)d (1 of (V AR(+
$ c22 (v AAi+ c)dln (1 c4' c1'cc1 (VAki+)))
where we use the fact that 1/ 1//n(1 q) 1 c/q for an absolute constant e if q bounded by an absolute constant. Finally,
K aiu s $2-KK K + Σ E- (VAKi+ (x (1 o4 ((Ax+t)))
=2 cl. A (1 es4 (VA
We choose L = 1 [ogg (K) which leads RK sc so(VAk-iV dlu² ck2 (1+ck (VAR-i(+))). This concludes the proof.
4 Linear Mixture MDP
As linear bandits and linear mixture MDPs have quite similar nature, bring the techniques in our analysis of VOFUL2 to improve the regret bound of VARLin of Zhang et al. [3]] A key feature of linear mixture MDP setting is that one can estimate the upper bound of the variance quadratic function of 6 while linear bandits do not have a structural assumption on the variance. Thanks such a structural property, we obtain slightly better dependence on the dimension d. The confidence set derived for our proposed algorithm is slightly different from that of VARLin as ours is defined with Vμ e (2) rather than an c-net. Our version of VARLin, which we call VARLin2, described in Algorithm
it is
2 Given sy, and an let us define Pat.af, f,
[V (s')] and ..... ohiat (V"T))"")T and let T., and 5 be given as define Algorithm 2
(Vit1) Ey-P -....
Jkhh == [P] P (V&
h+1
Let C (0) 0 o (V for (u, [K]x [H], {0, .,.,, L} where is defined in Algorithm
We construct our confidence set
O := n iun
m.
(5)
m-O ve[L]] #c[c]]
where we define ..f below, based the data collected up episode k First, let
1k.h m == max (0
m++1 Tggh
(0 (0"=khh xggh)²) )²
Be
and Thi = ((V, u) ([k] x [H]) U ({k) x [h]] : n. e (2-2,21-11) (1))
We naturally define T.m. mm.1+1 {(0, u) Tei n. S 2- 2-13.. With i defined in Algorithm 2
define
@mii 0c B((
Σ
(x TT e (0)

---

Algorithm 2 VARLin2
1: Initialize: L = logg HK| + 1, (l((((2 Sset.
2: for k 1.2. 2............. ... Kdo do
3: for h H
do
4: For each (s, a) S x A. define Q (s,a) min a)+ max Σi 0.P 5.a h+l where k defined in Lemma
5:
For each state V (s) m (s)
6:
end for
7:
for h I.... H do
8: Choose d arg max O (sh: (sh. a).
9: Observe reward r and the next state 8h+1'
10: end for
11:
end for
Σ (or 11 No 4.22% ,,,,, Vu (2))
(6)
(w.))eTTii.
We show that the confidence set correct w.h.p. in the following lemma.
Lemma 5, (Confidence set for MDP) PP(K [ - (²) 2 6.
The consequence is that the values computed in VarLin2 is optimistic with high probability due to the following property:
Lemma 6. For every k 2 1, 8 e O = wh, 8, a: (s, 2 2 (s,
Now with the confidence defined above state our main result.
Theorem 2. With probability least 1-5,
RK K
O(d K Klod//Koo (1/6) + df log((16))
where Ô hides poly-logarithniie dependence on {d, K, H. (n(/8)))
4.1 Proof Theorem 2
The main idea of the proof is to infuse peeling- based argument together with elliptical potential count lemma to both the planning horizon and episode. Noting that the regret of the predicted can expect reduce the total regret using this
variance is controlled by the variance of variance, information, as done in [3I] We begin by introducing relevant quantities that are parallel with those in linear bandits. Let first introduce the following lemma.
Lemma 7. Let II...., E Rdd be sequence of vectors with [xa|22 X for all t E [T]. Let =I= Et N.D... Lei 0 To TI < block formed by (T-11+1..... ..) for all i (0. Let anc(t) be the 'anchor' of I, the last time step of the i-th block such that the (i+ 1)-th block contains I.: anc(t) max { i (O...., =), < t). Let O. Define [T] to be the set of indices such that || V-11 r|| 12:z is true for the first and(t)
T T where marks the last time step of the i-th
time in the block containing t. Then,
2 ||| In(r)
2/e X2 In(r) X²)
dln 1+
To keep track of pprizee- index pairs concisely, we use a flat index 1 E [T] where 7 HK. Specifically, an episode & and horizon h corresponds to the flat index t = - h. Let t(k, h)) (k- 1)H Let k(t) and h(t) be the mapping from its corresponding episode and horizon index respectively so that & = k(t(k, h)) and h(t(k, h)). By taking in Lemma ass t(k; H), have that anc(t) := t(t (1 H). We define T.M (t(K',h') (k', h!) T and μ4," == (())))())) Similarly, define a;"h etc., by replacing the subscript k. h with t. Hereafter, any appearance of subscript k. h can replaced with such that = t(k:, h) without changing the meaning.

---

Given m. l and h, we define k.h as the integer & such that (x ) PKg (2-2 2-222+1-2221 where MEA Vi 0* and 0t arg m&X 110' xp-11 (0' xt (²))) For simplicity, we abbreviate em by Define W.m.. (1):= 2 +.+EEaTTh ExeT (I^ (aTT)T ml xs (ar")² and introduce a shorthand Wanc(e) = Wane(t) (4²")) as before. With the definition above we have the following:
" 1 2+
Σ
((TT) (x0"))
(2=") pr 114
eE7T.C) anc(()
We now show the key result of the confidence set of Varl.in2 that parallels L for bandits.
Lemma 8. Fix m e .o...., L and i [L]. Let t Th Then, with == E7"
ll th Mu womse $
CM max V2 V2-1)
where cM > is an absolute constant.
What is different from the linear bandit problem is that do not update 0 until the planning horizon over and an additional layer for peeling is imposed on variance. In [31], the authors introduce an indicator I to characterize episode -horizon pairs for which growth of the norm of μ with respect to We is controlled by the norm with respect to W aanc(()) with d² growth rate, i.e.,
h = 1 Hlleell s 4(d 2)) 2 [ulllmmeeee
where t t(k: h)) Our novelty novelty lies in being able replace 4(d+ 2) above by a constant rate r that set to 2 later (modulo some differences due to technical reasons). To distinguish we denote such set by TR See B.3 for the definition of Ik,h and the proof of the following lemma.
Lemma 9. Σ E Tk.h 1k. 0 (m(r)) log(dH de /nn(())) for O.
Note here that once we fix such as 2, the bound can be replaced by Odd (dH We now the following regret decomposition due to [3I] which just come from replacing IN by Ig.h-
Lemma 10. (Zhang et al. (37)) Rk S Regı + Regz + Regz =EK
(JI, II.DOI) where Regi Vk
ot Vk V () ΣK (Eh-1 V
Ex
RR, Reg, = En, (V. (s - rh Pog.aa, of h+l JR,h. and Rega
-V. (s4)).
Let am == Ih La, and define Rms Mm as
Rm = Σ (#F,h) Mkg MME and Mm == (Vh+)))) ((hin(s))t)) Ik.h.
h
We have that Reg: = Mo and Reg, S Ro since
(* - r(s,)) Ps.a Vi
S max x 3eE,
To proceed, we first note that En. (Jr,h - (R.,+1) 1 and Reg, are bounded by (dH and
O(VK K log( (og(1))) respectively from Lemma and Lemma 16 Since Reg, + Reg, 5 Rg Mo. remains to find bound on Ry + My. This, however, involves solving series of recursive inequalities. We leave the details in the appendix and provide a high-level description below.
Let us begin with Lemma 15 in the appendix that shows
| (MmM1-11 d+ 2 + Ro) log(1/)) +og(1//))
(7)
where the RHS is function of VMm=1 and VRg. Taking Proposition combining it with the relation from Zhang et al. 31 Eq. (57)) showing
[ below for granted and
Σ EmENTE Mm + Oddog" ((dllog(HHK)) h.h
2 (K Ro)) + Rm-1 + 2R
2 one arrives at Pm I ((d12//(MM 2 K improvement obtain via peeling- by [31] has d and d in place of d'/2 and d above.
())= Rm-1 2Rm + d). This bound the key peeling-based based regret analysis. Specifically, the bound on Rm obtained

---

We first show how our regret bound helps in obtaining the stated regret bound and then present Proposition[] Noting that both R,, and Mr are trivially bounded by НK, one can solve the series of inequalities on Rm and |m to obtain a bound on Ro:
Ru s Ō( (d 1og(1/6) + v ((K+ Ro) log(1/)))
(8)
Solving for Ro, we obtain Rg s Ō log(1/8) Vd K (log()))))))))) One can now plug in Ro to the bound 7 and obtain bound on |Mol in a similar way follows, which concludes the proof:
|Mo s Ó(dv K logg((10)) + d² log(1/6)).
We now show the key proposition that allows et al. 31. d was derived while we propose the following.
improve the bound Rm, In the paper by Zhang
Proposition 1. Let ME, T LR. Then, we have
Rm s O(d log 2.3 (HK)
V
(1+ Σ
llog(dd) + (HK)
k
Proof.
Define Tmiil = {tE (TTT (IIT) nr E (2-2- 2. 22-22-,2-21--1 21-
and split the time steps T by
Tm&&l1) te Tmiil :||m
SCMV 2- and Tmaile)) := T (.m.ee))...
wmie anc(a)
Having defined Ln, with r= 2, we also denote fmiile))) := (mm.te))) n fee [T] 4e 111 Now we decompose R'm as
Rm Σ (x) [T[T]
(xT)
Σ Σ (37 " 1T Σ Σ (TT")"
Fix m, i and l and focus on mme ( F
for z 1, 2. Hereafter, we omit the superscripts
and subscripts of im, to avoid clutter, unless there need. Note that for LE (()),- and b such that & < be (1))
2
2-
W Wanc(1)
(Hnc)))(H)) (1b)= 1 Σ (1
2
Σ
(1
2-
MeTmA.
2 I n-1
Σ IuZZ
c2 v(
anc(t)
For the same I, letting b arg max nave loTuull
2-t+n s |xTToo s x llll (ma) |40l (mlllwaanss(n) (an)))
S V 2m Ire [e (vil).y)) I1 (an)))(a))
S SCVFV2" Lel ( V2-h
(by
This implies that [[zell [ 2 2 20th -2
Thus,
f |Tay Σ Σ
Σ x 2 Σ 1
|Ti Σ 12
te
te)(1)
teT
n=0 tefel
1 1/ 1 2 2-26+n
-
| Σ Σ
22-1
n-O tef
[ L Σ 1 10 2 1-2
2-24+n
c2
n-0 n=
(T()) (0ll Ti1)an)

---

r2-% 2-2e+n
r2
c2
[ Σ
dln
1t 2 2-2e-n2-2
c drlT In (1 + cr(8t)
se
dr(L+ nf"))e (1 (1+ cre8f)
1e7
where we use the fact that [- 2- S 0( Evetor )²", which straightforward by the definition.
The summation over 7(2) can be handled in similar way and the details of the proof is provided in Section B.7 our appendix.
5
Conclusion
In this work, we have made significant improvements in the regret upper bounds for linear bandits and linear mixture MDPs by employing novel peeling-based regret analysis based on the elliptical potential count lemma. Our study opens up numerous future research directions. First, the optimal regret rates still identified for these problems. It would be interesting close the gap between the upper and lower bound. Second, our algorithms are not computationally tractable. We believe computationally tractable algorithms, even the price of increased regret, may lead to practical algorithms. Finally, characterizing suriance-dependerr uncertainty in the linear regression setting without prior knowledge of variances is an interesting statistical problem on its own. Identifying novel estimators for it and proving their optimal coverage would be interesting.
Acknowledgments and Disclosure of Funding
The authors thank Liyu Chen for finding error in earlier version. Insoon Yang is supported in part by the National Research Foundation of Korea WAUT202ORICICIO090
the Information and Communications Technology Planning and Evaluation (IIP) grants (MSIT2022-0-00112 MSIT2022- 0-00480), and Samsung Electronics. Kwang-Sune Jun is supported by Data Science Academy and Research Innovation & Impact at University of Arizona.
References
[1] Y. Abbasi-Yadkori, Pal, and Szepesvari. Improved Algorithms for Linear Stochastic Bandits. In Advances in Neural Information Processing Systems (NeurIPS), pages 1-19, 2011.
[2] J.-Y. Audibert, R. Munos, and C. Szepesvari. Use of variance estimation in the multi-armed bandit problem. NeurlPS Workshop On-line Trading of Exploration and Exploitation Workshop, 2006.
[3] Auer. Using Confidence Bounds for Exploitation-Exxlorraion Trade-offs. Journal of Machine Learning Research, 3:397-422, 2002.
[4] Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The Nonstochastic Multiarmed Bandit Problem. SIAM J. Compur., 32(1):48-77, 2003.
[5] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[6] V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic Linear Optimization under Bandit Feedback. Proceedings of the Conference on Learning Theory (COLT), pages 355-366, 2008
[7] C. Dann, N. Jiang, A. Krishnamurthy, A. Agarwal, Langford, and R. E. Schapire. On Oracle- Efficient PAC RL with Rich Observations. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[8] S. S. Du, Y. Luo, R. Wang, and H. Zhang. Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle. In Advonces in Neural Information Processing Systems (NeurIPS), pages
2019.
10

---

[9] S. S. Du, D. Lee, G. Mahajan, and R. Wang. Agnostic q-learning with function approximation in deterministic systems: Near-optimal bounds on approximation error and sample complexity. Advances in Neural Information Processing Systems, 33, 2020.
[10] F. Feng, R. Wang. W. Yin, S. S. Du, and L. Yang. Provably Efficient Exploration for Reinforce- ment Learning Using Unsupervised Learning In Advances in Neural Information Processing Systems (NeurIPS), pages 22492-22504, 2020.
[11] E. Hazan and S. Kale. Extracting certainty from uncertainty: Regret bounded by variation in costs. Machine Learning, 80(2):165-188, 2010.
[12] He, D. Zhou, and Q. Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171-4180 4180. PMLR, 2021.
[13] N. Jiang, A. Krishnamurthy, A. Agarwal, Langford, and R. E. Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference Machine Learning, pages 1704-1713. PMLR, 2017.
[14) C. Jin, Z. Yang. Z. Wang, and M. Jordan. Provably efficient reinforcement learninn with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
[15] A. Krishnamurthy, A. Agarwal, and J. Langford. Pac reinforcement learning with rich observa- tions. In Advances Neural Information Processing Systems (NeurIPS), 2016.
[16] T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[17] Y. Li, Y. Wang, and Y. Zhou. Nearly Minimax- Optimall Regret for Linearly Parameterized Bandits. In Proceedings of the Conference on Learning Theory (COLT), pages 2173-2174, 2019.
[18] D. Misra, M. Henaff, Krishnamurthy, and Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), pages 6961-6971. PMLR, 2020.
[19] D. Pollard. Empirical processes: theory and applications. NSF-CBMS regional conference series in probability and statistics, pages i-86. JSTOR, 1990.
[20] D. Russo and B. Van Roy. Eluder dimension and the sample complexity of optimistic exploration.
In Advances in Neural Information Processing Systems (NeurIPS), pages 2256-2264, 2013.
[21] W. Sun, N. Jiang, A. Krishnamurthy, A. Agarwal, and J. Langford. Model- in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Proceedings of the Conference on Learning Theory (COLT), pages 2898-2933. PMLR, 2019.
[22] A. Wagenmaker, Y. Chen, M. Simchowitz, S. Du, and K. Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pages 22384-22429. PMLR, 2022.
[23] R. Wang, S. S. Du, L.. Yang, and R. R. Salakhutdinov. On Reward-Free Reinforcement Learning with Linear Function Approximation. In Advances in Neural Information Processing Systems (NeurIPS), pages 17816-17826, 2020.
[24] R. Wang, R. Salakhutdinov, and L. F. Yang. Provably Efficient Reinforcement Learning with General Value Function Approximation. CORR, abs/2005.1, 2020.
[25] Y. Wang, R. Wang, S. S. Du, and A. Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. In International Conference on Learning Representutions (ICLR), 2020.
[26] Z. Wen and B. Van Roy. Efficient exploration and value function generalization in deterministic systems. Advances in Neural Information Processing Systems, 26, 2013.
[27] I.. Yang and M. Wang. Sample-optimal parametric q-learning using linearly additive features.
In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
11

---

[28] L. Yang and M. Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
[29] A. Zanette, A. Lazaric, M. Kochenderfer, and E. Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference Machine Learning, pages 10978-10989. PMLR, 2020.
[30] Zhang, X. Ji, and Du. reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon. In Conference Learning Theory, pages 4528-4531 PMLR, 2021.
[31] Z. Zhang, J. Yang, X. Ji, and S. S. Du. Variance-Aware Confidence Set: Variance-Dependee Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[32] Z. Zhang. Y. Zhou, and X. Ji. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. In International Conference on Machine Learning, pages 12653-12662. PMLR, 2021.
[33] D. Zhou, Q. Gu, and C. Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] There is no negative impacts, to our knowledge.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material
URLY? [N/A]
(b) Did you specify the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments 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, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new 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 as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're
using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

(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 to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "kBinYK4TXDm", "reviewer": "Reviewer_49qM", "summary": "This paper revisits the problem for linear bandits and linear mixture MDPs from Zhang et al. (2021). The authors follow their notion of variance-adaptive regret bound and provide novel analysis to improve such bound. In particular, for the linear bandits setting, the current work improves Zhang et al.’s result by a factor of $O(d^3)$ in the leading regrets. For the linear mixture MDPs, the improvement is a factor of $O(d^{3.5})$. The key of the analysis is a novel peeling-based regret analysis that leverages the elliptical potential ‘count’ lemma, which could be of independent interest to other related problems.", "questions": "Please justify or comment on the two weaknesses mentioned in the above Strengths And Weaknesses part. I would like to raise up my score if the authors can solve my concerns.\n", "limitations": "The authors mentioned the limitations of computational issues but does not provide explicit solutions, see my comments in the Strengths And Weaknesses part. And there is no potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The authors made solid theoretical contributions to the literature. The current work significantly improves previous works’ regret bounds, and the techniques are applicable to both linear bandits and linear mixture MDPs. From my perspective, the peeling techniques and the elliptical potential count lemma can be applied to a wider scope beyond the aforementioned linear bandits and linear mixture MDPs.\n\n2. The technical analysis is sound and the writing is easy to follow.\n\nWeakness\n\n1. My main concern is about the practical usage of the current variance-adaptive algorithm. The confidence interval used in Eq. (3) seems quite complicated. I cannot see the clear landscape of this confidence interval. I wonder how to find the action $x_k$ given such a “conceptual” interval. It could be better if the authors could elaborate more on the landscape of the optimization problem using Eq. (3) as the feasible set of $\\theta$. For example, the author could explain under what conditions or in what special cases this interval could be efficiently used. Another way is to show some plausible heuristics to calculate line 4 of the VOFUL2, like optimizing $\\theta$ and $x_k$ alternately.\n\n2. The current work does not include any empirical evaluations for their algorithm and the contribution is purely theoretical. I guess it is due to the same reason as mentioned above that line 4 of VOFUL2 does not have efficient solutions.\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": "a_VqTtlMfPf", "reviewer": "Reviewer_dtVb", "summary": "This paper studies variance-adaptive linear bandits and linear mixture MDPs. This paper improves significantly upon regret bounds obtained in the previous work by Zhang et al. (2021). To achieve this, they improved the structure of the confidence set in the previous work by removing the $\\epsilon$-net construction in the previous work, and they improved the analyses of the previous work by replacing the complicated volumetric-based argument in the previous work by a simple argument based on their novel elliptical potential \"count\" lemma.\nThe improvement on the confidence set and the novel elliptical potential \"count\" lemma are technically solid.", "questions": "\n1. Why do the main text and the appendix have different bibliography? This looks not common.\n2. Line 406-408 looks strange. Did you forget to delete them? \n3. Line 411: there is \"KJ\" in the text. Will it break double-blind?", "limitations": "1. The proof roadmap for both linear bandits and linear mixture MDP largely follows upon the previous work, which might limit the novelty of this paper. However, the confidence set  might not be able to become a standalone paper, so I think it inevitable to have this limitation.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n1. The regret bound is significantly improved upon the previous work.\n2. The analyses is largely simplified upon the previous work, which paves the way for the novel convidence set to be applied to broader theoretical applications. \n3. The novel elliptical potential \"count\" lemma would be of broarder interest to the bandit learning community. \n3. The bound for linear mixture MDP is near-optimal up to log factors.\n\nWeakness:\n1. The bound for linear bandits is $\\sqrt d$ away from being tight.\n2. The confidence set is still too complicated to be applied in practice, and optimizing in the confidence set cannot be done in polynomial time.\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": "MItoiZLpzUU", "reviewer": "Reviewer_8K2h", "summary": "This work focused on the linear bandit and linear mixture MDPs. The author proposes a novel variance-dependent algorithm, VOFUL2, for the linear bandit, which improved the regret with a factor of $d^{3}$. For linear mixture MDP, the author also proposes the VARLin 2 algorithm with a horizon-free regret guarantee, which improved the previous results with a factor of $d^{3.5}$.", "questions": "My main concern is the following:\n1. It seems strange that the dependence of dimension d in linear Mixture MDP is better than the linear bandit problem. For both variance-dependent results in Zhang et al. (2021) and Zhou et al. (2021), the dependence on dimension d in MDP is no worse than the linear bandit problem, and the variance-dependent result can only help to reduce the H-factor with the help of total variance. Is there some problem with the result in linear Mixture MDP, or the result in the linear bandit can be improved? It is better if the author could provide more explanation about this difference. I may increase my score if the author can solve this main concern.\n\nZhang Z, Yang J, Ji X, et al. Variance-aware confidence set: Variance-dependent bound for linear bandits and horizon-free bound for linear mixture MDP\n\nZhou D, Gu Q, Szepesvari C. Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes.\n\nOther comments:\n1. For the Markov decision process, Zhang et al. (2021) first propose the horizon-free result and show learning MDP is not more complicated than the bandits. It is better if the author can comment on it and compare the result of VARLin 2 with it since both achieve a horizon-free regret guarantee.\n\nZhang Z, Ji X, Du S. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of the horizon\n\n2. For the RL with linear function approximation, He el. Al 2021 also provides a potential elliptical count and uses the peeling technique to analyze linear MDP and Mixture MDP. Therefore, it is better if the author can comment on it before the Lemma 4 (elliptical potential count) and the peeling-based proof.\n\nHe J, Zhou D, Gu Q. Logarithmic regret for reinforcement learning with linear function approximation.\n\n3. For the unit cumulative rewards (Line 9), since the reward $r_h^k$ depends on the random variable $s_h^k,a_h^k$, it is better if the author can define it more clear. For example, should the expected cumulative reward be smaller than 1, almost smaller than 1, or always smaller than 1?\n\n4. In Line 77, the reward $|r_k|\\leq 1$ can not implies that $|\\epsilon_k|\\leq 1$ almostly, since the mean of reward $|r_k|$ is not 0.\n\n5. In the attachment, some comments such as \"KJ: add the details to the proof\" should be removed.", "limitations": "This paper provides theoretical guarantees for learning linear bandit and linear mixture MDP. There is no negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The VOFUL2 Algorithm improved previous results in unknown-variance linear bandit and reduced the gap to only $\\sqrt{d}$.\n2. The VARLin2 Algorithm obtains a horizon-free regret guarantee for linear mixture MDP, and the result is near-optimal with the dimension d.\n\nWeakness:\n1. The VOFUL2 and VARLin2 algorithms are not novel; they are part following the VOFUL and VARLin 2 algorithms in Zhang et al. (2021). \n\nZhang Z, Yang J, Ji X, et al. Variance-aware confidence set: Variance-dependent bound for linear bandits and horizon-free bound for linear mixture MDP\n\n2. VOFUL2 and VARLin2 also inherited the disadvantages of computing inefficiently. In addition, without the $\\epsilon$-net structure, the VOFUL2 algorithm needs to consider the intersection of the infinite confidence set, which is much more complicated than the original VOFUL algorithm.\n\n3. The Lemma 4 (elliptical potential count) is not new. This Lemma and also the corresponding peeling technique in linear mixture MDPs appears in the proof of Lemmas B.3-B.5 (He el. al 2021) previously.\n\nHe J, Zhou D, Gu Q. Logarithmic regret for reinforcement learning with linear function approximation.\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