Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
Authors: Zihan Zhang
Jiaqi Yang
Xiangyang Ji
Simon Shaolei Du
Venue: NeurIPS 2021 Poster (2021)
Keywords: linear bandits
linear function approximation
regret minimization
reinforcement learning theory

Abstract: This paper presents new \emph{variance-aware} confidence sets for linear bandits and linear mixture Markov Decision Processes (MDPs).
With the new confidence sets, we obtain the follow regret bounds:

For linear bandits, we obtain an $\widetilde{O}(\mathrm{poly}(d)\sqrt{1 + \sum_{k=1}^{K}\sigma_k^2})$ data-dependent regret bound, where $d$ is the feature dimension, $K$ is the number of rounds, and $\sigma_k^2$ is the \emph{unknown} variance of the reward at the $k$-th round. This is the first regret bound that only scales with the variance and the dimension but \emph{no explicit polynomial dependency on $K$}.
When variances are small, this bound can be significantly smaller than the $\widetilde{\Theta}\left(d\sqrt{K}\right)$ worst-case regret bound.
For linear mixture MDPs, we obtain an $\widetilde{O}(\mathrm{poly}(d, \log H)\sqrt{K})$ regret bound, where $d$ is the number of base models, $K$ is the number of episodes, and $H$ is the planning horizon. 
This is the first regret bound that only scales \emph{logarithmically} with $H$ in the reinforcement learning with linear function approximation setting, thus \emph{exponentially improving} existing results, and resolving an open problem in \citep{zhou2020nearly}.

We develop three technical ideas that may be of independent interest:
1) applications of the peeling technique to both the input norm and the variance magnitude, 2) a recursion-based estimator for the variance, and 3) a new convex potential lemma that generalizes the seminal elliptical potential lemma.

Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
Zihan Zhang Tsinghua University
Jiaqi Yang" Tsinghua University y (agg)q110gmaaa com
Aihan-zhl7n 2ha7@mails tsinghua. edu. en
Xiangyang Ji Tsinghua University
Simon S. Du University of Washington asduBcs www.wwwwtw..eeeeeeooo
xyji@tsinghhn edu.cn
Abstract
This paper presents variance-aware confidence sets for linear bandits and linear mixture Markov Decision Processes (MDPs). With the new confidence sets, we obtain the follow regret bounds:
For linear bandits, we obtain an (poolydd)) E of) data-dependent regret bound, where is the feature dimension, K is the number of rounds, and of the unknown variance of the reward the k-th round. This is the first regret bound that only scales with the variance and the dimension but no explicit polynomial dependency on K. When variances are small, this bound can be significantly smaller than the θ (dyK) worst-case regret bound.
For linear mixture MDPs, we obtain an (poly(dd log H)vK) regret bound, where d is the number of base models, K is the number of episodes, and H is the planning horizon. This is the first regret bound that only scales logarithmnicaly with H in the reinforcement learning with linear function approximation setting, thus exponentially improving existing results, and resolving an open problem in [Zhou et al., 2020a].
We develop three technical ideas that may be of independent interest: 1) applica- tions of the peeling technique to both the input norm and the variance magnitude, 2) recursion-based estimator for the variance, and 3) a new convex potential lemma that generalizes the seminal elliptical potential lemma.
Introduction
In sequential decision-making problems such as bandits and reinforcement learning (RL), the agent chooses an action based on the current state, with the goal to maximize the total reward. When the state-action space is large, function approximation is often used for generalization. One of the most fundamental and widely used methods is linear function approximation.
For (infinite-actioned) linear bandits, the minimax-optimal regret bound is ((d [Dani et al., 2008, Abbasi- Yadkori et al., 2011], where d is the feature dimension and K is the number of total rounds played by the agent. However, oftentimes the worst-case analysis is overly pessimistic, and
Equal contribution.
We follow the reinforcement learning convention to use K to denote the total number of rounds / episodes.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

it is possible to obtain data data-dependent bound that is substantially smaller than ((dvK) in benign scenarios.
One direction to study is the variance magnitude. As a motivating example, in linear bandits, there is noise (variance is 0); one only needs pay most d regret to identify the best action because d samples are sufficient to recover the underlying linear coefficients (in general position). v vK-type regret bound in the worst case where the variance magnitude is lower bounded constant. Therefore, natural question is:
This constant-type regret bound is much smaller than the
Can we design an algorithm that adapts to the variance magnitude, and its regret degrades gracefully from the benign noiseless constant-type bound to the worst-case v Ktypee bound?
In RI., exploiting the variance information also important. For tabular RI, one needs to utilize the variance information, e.g., Bernstein-type exploration bonus to achieve the minimax optimal regret [Azar et al., 2017, Zanette and Brunskill, 2019, Zhang et al., 2020c.a, Menard et al., 2021, Dann et al., 2019]. For example, the recently proposed MVP algorithm [Zhang et al., 2020a], enjoys an Opooyyog H) (VSAK S A)) regret bound, where S is the number of states, A is the number of actions, H is the planning horizon, and K is the total number of episodes. 34 Notably, this regret bound only scales logarithmically with H. On the other hand, without using the variance information, e.g., using Hoeffding-tyr bonus instead of Bernstein-type bonus, algorithms would suffer a regret that scales polynomially with H [Azar et al., 2017].
Going beyond tabular RL, a recent line of work studied RL with linear function approximation with different assumptions [Yang and Wang, 2019, Modi al., 2020, Jin al., 2020, Ayoub et al., 2020, Zhou et al., 2020a, Modi et al., 2020]. Our paper studies the linear mixture Markov Decision Process (MDP) setting [Modi et al., 2020, Ayoub et al., 2020, Zhou et al., 2020a], where the transition probability can be represented by a linear function of some features or base models. This model-based assumption is motivated by problems in roboties and queuing systems. We refer readers Ayoub et al. [2020) for more discussions.
For this linear mixture MDP setting, previous works can obtain regret bounds in the form (pooyydd H)KK), where d is the number of base models. While these bounds do not scale with SA, they scale polynomially with H, because the algorithms in previous works do not use the variance information. In practice, H is often large, and even a polynomial dependency on H may not be acceptable. Therefore, a natural question is
Can we design an algorithm that exploits the variance information obtain an (poly(d, log H) H))K) regret bound for linear mixture MDP?
1.1 Our Contributions
In this paper, we develop new, variance-aware confidence sets for linear bandits and linear mixture MDP and answer the above two questions affirmatively.
oz) regret bound, where of is the unknown variance at the k-th round. To our knowledge, this is the first bound that solely depends on the variance and the feature dimension, and has explicit polynomial dependency on K. When the variance is very small so that of < 1, this bound is substantially smaller than the worst-case θ(dvK) K) bound. Furthermore, this regret bound naturally interpolates between the worst-case / K Kttype bound and the noiscless-case constant-type bound.
Linear Bandits. For linear bandits, we obtain an ((polydd) + Σk_
Linear Mixture MDP For linear mixture MDP, we obtain the desired (poly(d, log H) K) regret bound. This is the first regret bound in RL with function approximation that 1) does not scale with the size of the state-action space, and 2) only scales logarithuiicaly with the planning horizon
OÕ(.) hides logarithmic factors. Sometimes we write out polylog H explicitly emphasize the logarithmic dependency on H.
'This bound holds for setting where the transition is homogeneous and the total reward is bounded by 1. We focus on this setting in this paper. See Section 2 and for more discussions.

---

H. Therefore, we exponentially improve existing results on RL with linear function approximation in term of the H dependency, and resolve an open problem in [Zhou et al., 2020a]. More importantl. our result conveys the positive conceptual message for RI: it is possible to simultaneously overcome the two central challenges in RI., large state-action space and long planning horizon.
1.2 Main Difficulties and Technical Innovations
We first describe limitations of existing works why they cannot achieve the desired regret bounds described above.
Limitations of Existing Variance-Aware Confidence Sets Faury et al. [2020], Zhou et al. [2020a] applied Bernstein-style inequalities to construct confidence sets of the least square estimator for linear bandits. However, their methods can not be applied directly to obtain the desired data-dependent regret bound. Abeille al. [2021] also designed an variance-dependent confidence for logistic bandits. However in their problem the rewards are Bernoulli and the variance is function of the mean.
We give a simple example to illustrate their limitations. Consider the case where the variance is always a² 1. Let (1) ..... (2% M/--1) be the samples collected before the k-th round. Their confidence set the k-th round is O₂ = {Øllle BellAz- & C(ovd + 1 X/2333 (See In Equation (4.3) of Zhou et al. [2020a] and Theorem of Faury et al. [2020]). where A&-1 = E==1 2 XI is the un-normalized covariance matrix, O2 A - リーæ, is the estimated linear coefficients by least squares, À is a regularization parameter and C is a constant. Consider the case d d=1 and 24 = V1/K for le = 1....,
......K. K. Their regret bound is roughly
K
(ovd+1 +
X M A5r > (1+A12
x B 2 (1+
N
I 2 V
when is very small. For more detailed which is much larger than our bound, 0 (vKo²+) +1) discussion, please refer to Appendix
Below we describe our main techniques.
Elimination with Peeling. Instead of using least squares and upper-confidence-bouut (UCB), use an elimination approach. More precisely, for the underlying linear coefficients 0* e Rd, we build confidence interval for (0%) T fz. for every in an e-net of the d-dimensional unit ball, and we eliminate 0 dd if 0 fa fails to fall in the confidence interval of (0*)* T f for some μ. To build the confidence intervals, we use 1) an empirical Bernstein inequality (cf. Theorem 4) and 2) the peeling technique to both the input norm and the variance magnitude. As will be clear in the proof (cf. Section D), this peeling step is crucial obtain a tight regret bound for the example above. The new confidence region provides a tighter estimation for 0*, which helps address the drawback in least squares.
Generalization of the Elliptical Potential Lemma. Since we use the peeling technique which comes with a clipping operation, we cannot use the seminal elliptic potential lemma Dani al. [2008] any more. Instead, we propose more general lemma below, which provides a bound of potential for a general class of convex functions though with a worse dependency on than the bound in the elliptical potential lemma. We believe this lemma can be applied to other problems as well.
Lemma (Generalized Quadratic Potential Lemma). Let f(x) & be a convex function over R and f(x) > f(v) if > y² > 0. Let B(I) denote the d-dimensional unit ball. Fix l (0, 11. For any x1, P2.......... ... 3e (1) and pl, P2..... pe B(1), we have that f(z.))))
such that f(x) f(y)
1 /
min
1 < Odd log(dt/()).
E f( + 62
Note that by choosing f(x) 2 and μ.
ÉI, Lemma I reduces to the classical elliptic potential lemma [Dani et al., 2008]. Our proof consists of two major parts.
æ,A;1 with A, = ビ
3

---

We first establish a symmetric version of Equation (??) using rearrangement inequality, and then bound the number of times the energy for some (i.e., مー f( + (2) doubles. The full proof is deferred to Appendix C.
For linear mixture MDP, we propose another technique further reduce the dependency on d.
Recursion- Variance Estimation. In linear bandits, generally it is not possible to estimate the variance because the variance at each round can arbitrarily different. On the other hand, for linear mixture MDP, the variance is a quadratic function of the underlying coefficient 0". Furthermore, the higher moments are polynomial functions of 0" Utilizing this rich structure and leveraging the recursion idea in previous analyses on tabular RL [Lattimore and Hutter, 2012, Li et al., 2020, Zhang et al., 2020a], we explicitly estimate the variance and higher moments to further reduce the regret. See Section 5 for more explanations.
2 Related Work
Linear Bandits. There is a line of theoretical analyses of linear bandits problems [Auer et al., 2002, Dani et al., 2008, Chu et al., 2011, Abbasi-Yadkori infinite-actioned linear bandits, the minimax regret bound is @(dvK). and recent works tried to give fine-grained instance-dependent bounds [Katz-Samuels et al., 2020, Jedra and Proutiere, 2020]. For multi-armed bandits, Audibert et al. [2006] showed by exploiting the variance information, one can improve the regret bound. For linear bandits, only a few work studied how to use the variance information. Faury et al. [2020] studied logistic bandit problem with adaptivity to the variance of noise, where Bernstein-style confidence set was proposed. However, they assume the variance is known and cannot attain the desired variance-dependent bound due to the example we gave above. Linear bandits can be also seen as a simplified version of RL with linear function approximation, where the planning horizon degenerates to H = 1.
Yadkori et al., 2011, Li et al., 2019a,b]. For
RL with Linear Function Approximation. Recently, it is a central topic in the theoretical RL community to figure out the necessary and sufficient conditions that permit efficient learning in RL with large state-action space [Wen and Van Roy, 2013, Jiang et al., 2017, Yang and Wang, 2019, 2020, Du et al., 2019b, 2020a, 2019a, 2020b, Jiang et al., 2017, Feng et al., 2020, Sun et al., 2019, Dann et al., 2018, Krishnamurthy et al., 2016, Misra et al., 2019, Ayoub et al., 2020, Zanette et al., 2020, Wang et al., 2019, 2020c,b, Jin et al., 2020, Weisz et al., 2020, Modi et al., 2020, Shariff and Szepesvári, 2020, Jin et al., 2020, Cai et al., 2019, He et al., 2020, Zhou et al., 2020a]. However, to our knowledge, all existing regret upper bounds have polynomial dependency on the planning horizon H, except works that assume the environment deterministic [Wen and Van Roy, 2013, Du et al., 2020b].
This paper studies the linear mixture MDP setting [Ayoub al., 2020, Zhou al., 2020b,a, Modi et al., 2020], which assumes the underlying transition is a linear combination of some known base models. Ayoub et al. [2020] gave an algorithm, UCRL-VTR, with an Ö(dH2 regret in the time- inhomogeneous model. Our algorithm improves the H -edependyncy from poly ()) to polylog(H1). (H), at the cost of worse dependency on d.
Variance Information in Tabular MDP. The use of the variance information in tabular MDP was first proposed by Lattimore and Hutter [2012] in the discounted MDP setting, and was later adopted in the episodic MDP setting [Azar et al., 2017, Jin et al., 2018, Zanette and Brunskill, 2019, Dann al., 2019, Zhang al., 2020a,b). This technique is crucial to tighten the dependency on H.
Concurrent Work by Zhou et al. [2020a]. While preparing this draft, we noticed a concurrent work by Zhou et al. [2020a], who also studied how to use the variance information for linear
'The fime-inhomogeneeuus model refers to the setting where the transition probability can vary different levels, and the time-homogeneous model refers the setting where the transition probability is the same different levels. Roughly speaking, the model complexity of the time- inee-nnooooouuusss model times larger than that of the time-homogene homogeneous model. In general, it is straightforward to tightly extend a result for the time-home homoehoogeeneuus model to the time- inhommonnooeeoou model by extending the sate-action space [Jin et al., 2018, Footnote 2). but not vice versa.

---

bandits and linear mixture MDPs. We first compare their results with ours. For linear bandits, they proved an Ö(vdK- dv E d of regret bound. Our bound has a worse dependency on d, but in the regime where is very large and the sum of the variances is small, our bound is stronger. Furthermore, they assumed the variance is known while we do not need this assumption. For linear mixture MDP, they proved an O(vd'H- + dH²vK + H² + d H) bound for the aam--iiomooeeeouus model, while we prove an O + d polylog( H) bound for the time- sime-hoogeeneou model. Their bound has better dependency on d than ours and is near-optimal in the regime On the other hand, we have an exponentially better dependency on H in the time-homogeneous model. Indeed, obtaining regret bound that is logarithmic in H (in the honn--ooogenuuss model) was raised as open question in their paper [Zhou et al., 2020a, Remark 5.5].
regret bound, while we prove S
V V of + dd)
(poly (d, H)) and H O(d).
Next, we compare the algorithms and the analyses. The algorithms in the two papers are very different in nature: ours are based on elimination while theirs are based on least squares and UCB. We note that, for linear bandits, their current analysis cannot give a v -frree bound because there is a term that scales inversely with the variance. This can be seen by plugging the first line of their (B.25) to their (B.23). For the same reason, they cannot give a horizon-free bound the time-homogeneous linear mixture MDP. In sharp contrast, our analysis does not have the term depending on the inverse of the variance. On the other hand, their algorithms are computationally efficient (given certain computation oracles), but our algorithms are not because ours are elimination-based See Section for more discussions.
3 Preliminaries
Notations. We use By(r)) fo e TRd ||>1| & r) denote the d-dimensional 6y-ball of radius r, so B(1) = (1) For any set = Rd, we use ôS to denote its boundary. For N e N, we define [N] (1,.... N). One important operation used in our algorithms and analyses is clipping. Given
0 and u e I., we define
u
clip(u, E) = min [u].
21
for u # O and clip(0, E) = O. For any two vectors u, to save notations, we use uv = u v to denote their inner product when no ambiguity.
Linear Bandits. We use K to denote the number of rounds in the linear bandits. At each round k: =
1...., ; K, the algorithm is first given the context set A, (1),),, then the algorithm chooses action 2t E Ag and receives the noisy reward r x +Ek, where 0* e (1) is the unknown underlying linear coefficients and EY is the random noise. We define Fx = a (11 EL.... Dy. Ek Ix+1). We
assume that |rx| & and that the noise EK satisfies R[Ex F& O and R[E Fu] o. The goal
is to learn 0* and minimize the cumulative expected regret E [ where
max x0* - -x20*) DE
Here we assume the reward is uniformly bounded ([rkl & 1) instead of commonty used in the literature only for the ease of presentation, because in RL, standard to assume bounded reward. Note if the noise is 1-sub- Suu--Gaussinn, our algorithm also applies with only an O (log K) overhead because a problem with 1-sub- Gaussian noise can be reduced to that with uniformly bounded noise by clipping the noise with a threshold Oloog K).
Remark 1.
We tuple (S, A. r. P. K, H) to define episodic finite-horizon MDP. Here, S is its state space, A is its action space, r S x A [0. 1] is its reward function, P(s' s, a) is the transition probability from the state-action pair (s, a) to the new state s'. K is the number of episodes, and И is the planning horizon of each episode. Without the loss of generality, we assume a fixed initial state $1. sequence of functions π {mT : {(A)) is an policy, where ((A) denotes the set of all possible distributions over A.
Episodic MDP and Linear Mixture MDP.
At each episode = 1,...... K, the algorithm outputs a policy =* which is then executed on the MDP by af ( s/ P(. s d.). We let r = r(sf, aft) be the reward at time step h in
5

---

Algorithm VOFUL: Variance-Aware Optimism in the Face of Uncertainty for Linear Bandits
1: Initialize: & = 22-i, 16d In of L2 [log2 K1,Ag, A2 = {1, L2 + 13, 6, =B:(1) (1),
Let B be an -et of (2) with size not larger than (x) )3)
2: for =........; K do
3: Optimistic Action Selection:
4: Observe context set Aμ S (1)
5: Compute < arg w5.A, maxØce, æ0, choose action
6: Receive feedback 1/s
7: Construct Confidence Set:
8: For each 0 (1), define cx(0) = yk x2O, (0) - (c)(
9: Define confidence set Ox+1 = NieAo Ø where
0 k+1 = {0= (1)
Σ clip, (E)H)))(() & ci V (1)
and clip,()) clip(-,eg)
10: end for
episode Importantly, we assume the transition model P(- (:-)) time-homogeneous, which is
necessary to bypass the poly (ff) dependency. We assume that the reward function is known, which standard in the theoretical RL literature to simplify the presentation [Modi al., 2020, Ayoub et al., 2020]. We let N denote the optimal policy which achieves the maximum reward in expectation.
We make the following regularity assumption on the rewards: the sum of reward, Σ The in each episode is bounded by 1.
Assumption 2 (Non-uniform reward). Σ t < 1 almost surely for any policy nt
This assumption is much weaker than the common assumption where the reward each time step is bounded by I/H (uniform reward) because Assumption 2 allows one spiky reward as large as Q (1). See more discussions about this reward scaling in Jiang and Agarwal [2018], Wang et al. [2020a]. Zhang et al. [2020a].
For any policy π, define its H-step V-function and Q-function
(s) max Q (8, a) A
where (7, a) = r(s, a) + Ee-P()sa) (i+)('') for h 1,..., H
where we set VH+1 0. For simplicity, also denote V (si) (si and (*(s)) V* (s1).
linear mixture MDP an episodic MDP with the extra assumption that its transition model an unknown linear combination of known set of models. Specifically, there is unknown parameter 0* e (T),), such that P > 8r P, where based models Pı...., Pa are given. The goal is to learn 0* and minimize the cumulative expected regret E[ where
[ - v
4 Algorithm and Theory for Linear Bandits
In this section, we introduce our algorithm for linear bandits and analyze its regret. The pseudo- code is listed in Algorithm 1. The following theorem shows our algorithm achieves the desired soriance-depende regret bound. The full proof is deferred to Section D.
Theorem 3. The expected regret of Algorithm is bounded by E[ O(dts /
DK of dd).
This theorem shows our algorithm's 's regret has no explicit polynomial dependency on the number of rounds K. the worst-case where the variance (1), our bound becomes Ô (21.. + d²), which has worse dependency on d compared with the minimax optimal algorithms [Dani et al.,

---

2008, Abbasi- Yadkori et al., 2011]. However, in the benign case where the variance is o(1), our bound can be much smaller. In particular, the noiseless case, our bound is a constant-type regret bound, up to logarithmic factors. One future direction is to design an algorithm that is minimax optimal in the worst-case but also adapts to the variance magnitude like ours.
4.1
Main Algorithm
Now we describe our algorithm. Similar to many other linear bandit algorithms, the algorithm maintains confidence sets [0)) for the underlying parameter 0², and then choose the action greedily according to the confidence set.
To relax the known variance assumption, use the following empirical Bernstein inequality that depends on the empirical variance, in contrast to the Bernstein inequality that depends on the true variance, which
used in existing works [Zhou et al., 2020b, Faury et al., 2020].
Theorem 4. Let {Fi)i oo be a filtration. Let ( be a sequence of real-valued random variables
such that X; is F--measurable. We assume that E[X; Fs-1]= 0 and that [X,] < b almost surely. For < e we have
Pr
Σ
X
E
Σ + x In 5
16b1n
> 1 11-666 66 -61ggg n.
(2)
Importantly, this inequality controls the deviation via the empirical variance, which is X2 and can be computed once X; is known. Note some previously proved inequalities require certain independence assumptions and thus cannot be directly applied to martingales [Maurer and Pontil, 2009, Peel et al., 2013], so they cannot be used for solving our linear bandits problem. The proof of the theorem is deferred to Appendix D.2.
More effort is devoted designing confidence set that fully exploits the variance information. Note Theorem 4 is for real-valued random variables, and it remains unclear how to generalize it to the linear regression setting, which crucial for building confidence sets for linear bandits. Previous works built up their confidence sets based on analyzing the ordinary ridged least square estimator [Dani et al., 2008, Abbasi- Yadkori et al., 201 I], or the weighted one [Zhou et al., 2020a].
We drop the least square estimators and instead, we take a Besting-basedd approach, as done in Equation (1). To illustrate the idea, we first ignore the clip,(.) operation and É, terms. We define the noise function (0) and the variance function πı (0) (Line of Algorithm 1). Note that Ex (x(0)) Ek and (0*) = so we have the following fact: if 0 = 0*, then Equation (2) would be true if we replace X₃ = wy. (p)))))) (0) and X2 (H)
with high probability, where {w]{(p)} is a proper sequence of weights depending on the test direction μ.. Our approach uses the fact in the opposite (()
direction: if weighted wa (14)ez ex (0), L m (0) satisfies Equation (2) for all possible test directions I in an K -net of the d-dimensional unit ball, then we put into the confidence set.
Remark 2. One can also view the algorithm as an elimination-bass algorithm: if there exists some test direction μ such that Equation (2) fails for X = wu(p)es(0 (0) and X2 = w (1) () (0), then we eliminate 0 from the confidence set permanently.
Given the test direction Ja, following the least square estimation, (x((1)) is set to be æapa. However,
with wx(H4) = x& ft. the right-hand-side of Equation (2) is at least > max [wx (14) = maxisken [0), which might be dominant compared with Σx=1 w (1))) (See Appendix B for a toy example). To address this problem, we consider to peel (14) for various thresholds of difference level. More precisely, we construct confidence regions respectively with w clip, (2: 1u), where 1, 22-j for j ....... [log2 K1. At last, we define the final confidence region as the intersections of all these confidence regions.
Remark 3. Note that existing confidence sets in Equation (1) either do not exploit variance informa- tion [Dani et al., 2008, Abbasi- Yadkori et al., 2011], or require the variance to be known and do not fully exploit the variance information [Zhou et al., 2020a, Faury et al., 2020] as their regret bounds still have Õ( K) term.
7

---

4.2 Proof Sketch of Theorem 3
Now we explain how our confidence set enables us to obtain a cerrance-dependent regret bound. We define 0g arg max 2x (0- )*) and μ4g 02 0* Then our goal is to bound the regret En 2t Our main idea is to consider { { as two sequences of vectors. We decouple the complicated dependency between {a*} and { by a union bound over the net B (defined in Line I of Algorithm 1). To bound the regret, we implicitly divide all rounds i e [K] into norm layers based on log2 | in the analysis. Within each layer, we apply Equation (1) to obtain the relations between μl and (æ1,.... 11= which would self-normalize the growth of the two sequences, ensuring that their in-layer total sum is properly bounded. Since we have logarithmically many layers, the total regret is then properly bounded. We highlight that our norm peeling technique ensures that the variance-dependent term dominates the other variance-inddeendeett term in Bernstein inequalities (v Σ X? > in Theorem 4), which resolves the variance-inddeendentt term in the final regret bound obtained by Zhou et al. [2020a].
We start the analysis by proving that the probability of failure events (i.c., the events where 0* Ox for some k E [K]] is properly bounded (see Lemma 18). Assuming the successful events happen, we have that 8t e O2 for all & [K]. Then we obtain that.
K (Op 0*) = Σ M.
97
max 0
x=00*
max xx(0 0*) & 0E0
Next we divide the time steps [K] into L2 + disjoint subsets (Kr 12t1 according to the magnitude
of Fz More precisely, for for & j & L2 we assign k to Ky iff 2xpl E (1//,,4), and for
j = L2 + 1, we assign & to Kg iff Jx 12211/2 Define
(1)
Σ (a.)) fj
Vg(M))
Σ (1
(3)
By the definition of O₁ in (1), we have that (see Claim 20)
L2 Σ
3 V (Mx))
v - *k 1 (2. + 36yt
-
T&llk & 1+
Σ
Jkllk
(4)
(14s)
ke
Continuing the computation, we have that
k 2clip? (2 (Zu
(144)
keKC
2 2clip (x) (Z)
1)
xx
2 1 ket,
2
1=1 kek,
1 L2
La
41,c KKlli
3b
(5)
T (11a)
1ー
keR,
1 Σ
O(d (dK))
(6)
kE
'This cannot be done explicitly in the algorithm, since it would re-couple the sequences.
8

---

Algorithm 2 VARLin: Aware RL with Linear Function Approximation
1: Initialize: & 2 16d
AHK
Lo [log2 KH), L1 = L2 = ( + 3/, Ao =
0
[0,1,..... Lo).A, A1 = (1..... .......,]].. I,],Ag A2
(1....,IA B be an (HK) 3-nttt of By(2) with size
no larger than HK
3dd 0, = (1).).
2: for k 2,.....: K do
3: Optimistic Planning:
4: for h H, H 1...., do
5: For each (s, E S x A, let (s, min(1, max Σ 0, O;Pi V 1
3,
6: For each 8 E S, let Vi (s) max ())
7:
end for
8: for f 2. H.H do
9: Choose action af arg ma 0 ( a). observe the next state s sh+1'
10: end for
Construct Confidence Set:
12:
For m E Au, h e [H, define the input Ti, = [P
si ht11
(V -m Pd (V (1 12m
oo o h+1
13:
For Ao, h [ define the variance estimate T/in = maxpee, (0x
k
(0x k, 2
14:
Denote Ez (0) = Ow?, - -VV++ WV (s=+1))²² for m An, u [
[
15:
Define T.m ((1, u) [K] [H] no (f(+1, ld)) k+1 Tmmlatt
{(v, u)
[M] [H]
(1)+))-
16: Define the confidence ball Ox+1 = Am, Ouf where
0 e B((1)
Σ
(a
k+1
(v.))TT..
$
Σ
(a (apt + 4ezr, V
(7)
(o.a)eTT
and (lip,() clip(-, Eg
17: end for
where (5) is by the fact that y V (a by Lemma 17. By (4) and (6), we have that
41gr 2/2 implies that
1, and (6) follows
(1()))
oy (mr)
1/2
((()))) O(dg)
Eklls & 12
Σ
(k(m)))
1-1 ke
12
me(0))= Ō(d)) < O(d* (ad log (dK))
(In
1
Σ of u Ō(d²),
K
kek,
where the last inequality uses Lemma 17. Therefore, the regret bound is Ô ( D of + d=
See Section D for the full proof.
5 Algorithm and Theory for Linear Mixture MDP
We introduce our algorithm and the regret bound for linear mixture MDP. Its pseudo-code is listed in Algorithm and its regret bound is stated below. The proof is deferred to Section E.
Theorem 5. The expected regret of Algorithm is bounded by E[ < Ô (d d9).
Before describing our algorithm, we introduce some additional notations. In this section, we assume that, unless explicitly stated, the variables m, j.j.k, k. iterate over the sets Au, A1, A2, [K]. H], respectively. See Line of Algorithm 2 for the definitions of these sets. For example, at Line 16 of @ mm......
Algorithm 2, we have Ama Om.i. AmeeooiiAA.aa

---

gap between The starting point of our algorithm design is from Zhang et al. [2020a], in which the authors obtained a nearly horizon-free -ree regret bound in tabular MDP. A natural idea is combine their proof with our results for linear bandits and obtain nearly horizon-free regret bound for linear mixture MDP.
Note that, however, there is one caveat for such direct combination: in Section 4, the confidence set O₂ is updated at per-round level, in that θ₂ is built using all rounds prior to k; while for the RL setting, the confidence set O₂ could only be updated a per-episode level and use all time steps prior to episode k. Were it updated at a per-time-step level, severe dependency issues would prevent us from bounding the regret properly. Such discrepancy in update frequency results the confidence set built using data prior to episode k, and that built using data prior to time step (k, h). Fortunately, we are able to resolve this issue. In Lemma 22, we show that we can relate these two confidence intervals, except for ((d) "bad" episodes. Therefore, we could adapt the analysis in Zhang et al. [2020a] only for the not "bad" episodes, and we bound the regret by 1 for the "bad" episodes. The resulting regret bound should be (KK..
To further reduce the horizon-free free regret bound to Ö VK), we present another novel technique. We first note an important advantage of the linear mixture MDP setting over the linear bandit setting: in the latter setting, we cannot estimate the variance because there is structure on the variance among different actions; while in the former setting, we could estimate an upper bound of the variance, because the variance is quadratic function of 0* Therefore, can use the peeling technique the variance magnitude to reduce the regret (comparing Equation (30) and Equation (43) in appendix). We note that can also apply this step linear bandits if the variance be estimated.
Along the way, we also need to bound the gap between estimated variance and true variance, which can be seen as the "regret of variance predictions." Using the same idea, we can build a confidence set using the variance sequence (x²), and the regret of variance predictions can be bounded by the variance of variance, namely the 4-th moment. Still, peeling step the 4-th moment is required to bound the regret of variance predictions, we need to bound the gap between estimated 4-th moment and true 4-th moment, which requires predicting 8-th moment, We continue use this idea: estimate 2-th, 4-th, 8-th, .... Ollog K KH)--t moments. The index m is used for moments, and Ag is the index set reserved for moments. We note that the proof in [Zhang et al., 2020a] also depends on the higher moments. The main difference is here we estimate these higher moments explicitly.
6 Discussions
By incorporating the variance information in the confidence set construction, we derive the first variance-dependere regret bound for linear bandits and the nearly horizon-free regret bound for linear mixture MDP. Below we discuss limitations of our work and some future directions.
One drawback of our result is that our dependency on d is large. The main reason our bounds rely on the convex potential lemma (Lemma 17), which is Ödd)). In analogous to the elliptical potential lemma in [Abbasi- Yadkori et al., 201 I], we believe that this bound can be improved to Ö(d). This improvement will directly reduce the dependencies on d in our bounds.
Another drawback is that our method is not computationally efficient. This is a common issue in climination-bass algorithms. We note that the issue of computational tractability is common in sequential decision-making problems [Zhang and Ji, 2019, Wang et al., 2020a, Bartlett and Tewari, 2012, Zanette et al., 2020, Krishnamurthy et al., 2016, Jiang et al., 2017, Sun et al., 2019, Jin et al., 2021, Du et al., 2021, Dong et al., 2020]. We leave it as a future direction to design computationally efficient algorithms that enjoy variance-dependent bounds for settinsg considered in this paper.
Lastly, in this paper, we only study linear function approximation. It would be interesting to generalize the ideas in this paper to other settings with function approximation schemes [Yang and Wang. 2019, Jin et al., 2020, Zanette et al., 2020, Wang et al.. 2020c, Russo and Van Roy, 2013, Jiang et al., 2017, Sun al., 2019, Du et al., 2021, Jin al., 2021].
Acknowledgement
Simon S. Du gratefully acknowledges funding from NSF Award's IIS-2110170 and DMS- DMS-2134106.
10

---

References
Yasin Abbasi-Yadies Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:23 12-2300, 2011.
Marc Abeille, Louis Faury, and Clément Calauzênes. Instance-wise Mannimax-optimma algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691-3699. PMLR, 2021.
Jean- Audibert, Rémi Munos, and Csaba Szepesvari. Use of variance estimation in the multi- armed bandit problem. 2006.
Peter Auer, Nicolò Cesa- masa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal Computing. 32(1):48-77, 2002.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value- sarleet regression. In Proceedings of the 37th International Conference Machine Learning, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning, pages 263-272, 2017.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):357-377, 1967.
Peter L Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint 1205v21205.26611 2,,,2,66,,,11.. 2012.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. arXiv preprint arXiv: 1911v:1912.05880, 2019.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214, 2011.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In Conference on Learning Theory, 2008
Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. On oracle-effciint PAC-RL with rich observations. In Advances Neural Information Processing Systems, 2018.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountabll reinforcement learning. In Proceedings of the 36th International Conference Machine Learning, pages 1507-1516, 2019.
Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou. Root-n-regret for learning in Markov decision processes with function approximation and low Bellman rank. In Conference on Learning Theory, pages 1554 1557. PMLR, 2020.
Simon S Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674, 2019a.
Simon S Du, Yuping Luo, Ruosong Wang, and Hanrui Zhang. Provably efficient Q-learning with func- tion approximation via distribution shift error checking oracle. In Advances in Neural Information Processing Systems, pages
2019b.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? In International Conference on Learning Representations, 2020a.
11

---

Simon S Du, Jason D Lee, Gaurav Mahajan, and Ruosong Wang. Agnostic Q-learning with func- tion approximation in deterministic systems: Tight bounds on approximation error and sample complexity. Advances in Neural Information Processing Systems, 2020b.
Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. arXiv preprint arXiv:2103. 100.9 2021.
Louis Faury, Marc Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference Machine Learning, pages 3052-3060. PMLR, 2020.
Fei Feng, Ruosong Wang, Wotao Yin, Simon S Du, and Lin F Yang. Provably efficient exploration for RL with unsupervised learning. arXiv preprint arXiv:2003.06880 2020.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. arXiv preprint arXiv:201 2020.
Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 33, 2020.
Nan Jiang and Alekh Agarwal. Open problem:
The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, pages 3395-3398, 2018.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Con- textual decision processes with low Bellman rank are PAC-leamable. In Proceedings of the 34th International Conference on Machine Learning, pages 1704-1713, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-44454 4873,4873310 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman Eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. arXiv preprint 1x2iv:2122.00800 2021.
Julian Katz-Samuels, Lalit Jain, Kevin G Jamieson, al. An empirical process approach the union bound: Practical algorithms for combinatorial and linear bandits. Advances in Neural Information Processing Systems, 33, 2020.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, pages 1840-1848, 2016.
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In International Conference on Algorithmic Learning Theory, pages 320-334. Springer, 2012.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. In Advances in Neural Information Processing Systems, 2020.
Yingkai Li, Yining Wang, and Yuan Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pages 2173-2174, 2019a.
Yingkai Li, Yining Wang, and Yuan Zhou. Tight regret bounds for infinite-armed linear contextual bandits. arXiv preprint arXiv:1905. 05tt::9900.013555 2019b.
Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variance penaliza- tion. In Conference Learning Theory, 2009.
Pierre Menard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momentum q-learning: Correcting the bias without forgetting. arXiv preprint arXiv:2103.01312. 2011.
12

---

Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. abstraction and provably efficient rich-observation reinforcement learning. arXiv preprint 11X1v:1911.05815, 2019.
Kinematic state
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2020.
Thomas Peel, Sandrine Anthoine, and Liva Ralaivola. Empirical bernstein inequality for martingales: Application to online learning. 2013.
Dan Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, pages
2013.
Roshan Shariff and Csaba Szepesvári. Efficient planning in large mdps with weak linear function approximation. arXiv preprint arXiv:2007.06184, 2020.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference Learning Theory, pages 2898-2933 2019.
Ruosong Wang. Simon S Du, Lin F Yang, and Sham M Kakade. long horizon reinforcement learning more difficult than short horizon reinforcement learning? In Advances in Neural Information Processing Systems, 2020a.
Ruosong Wang. Simon S Du, Lin F Yang. and Ruslan Salakhutdinov. On reward- freerd-free reinforcement learning with linear function approximation. In Advances in Neural Information Processing Systems, 2020b.
Ruosong Wang. Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learning with general value function approximation. Advances in Neural Information Processing Systems, 2020c.
Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv: 1912.011 2019.
Gellert Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with rinearly-realizbble optimal action-value functions. arXiv preprint arXiv:2010.01374. 2020.
Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deterministic systems. In Advances in Neural Information Processing Systems, pages 3021-3029, 2013.
Lin Yang and Mengdi Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004, 2019.
Lin Yang and Mengdi Wang. Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. International Conference on Machine Learning, 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, 2020.
Zihan Zhang and Xiangyang Ji. Regret minimization for reinforcement learning by evaluating the optimal bias function. In Advances in Neural Information Processing Systems, pages 2823-2832, 2019.
Zihan Zhang, Xiangyang Ji, and Simon Du. reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. arXiv preprint arXiv:2009. 13503, 2020a.
13

---

Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning
via reference-advanteee decomposition. In Advances Neural Information Processing Systems, 2020b.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. arXiv preprint arXiv:2006 03864, 2020c.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax o for linear mixture markov decision processes. arXiv preprint arXiv:2012.088507 2020a.
reinforcement learning
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcemmet renen learning for discounted mdps with feature mapping. arXiv preprint 2rxiv:2206.1336633 2000b.
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] We discuss the limitations in Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work is theoretical so the boarder impact does not apply.
(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] We present the main assumption in Section 3.
(b) Did you include complete proofs of all theoretical results? [Yes] We present the proofs Appendix.
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 as a URL)? [N/A] We have no experiments.
(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 to 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 (e.g., type of GPUs, internal cluster, or 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] We do not use existing models.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] This work is inrelevent with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "V-83XDCLzh", "reviewer": "Reviewer_hw6t", "summary": "This paper discusses an interesting topic, the variance awareness approach in online learning and decision making (e.g., bandit and linear MDP).  Two algorithms VOFUL (Variance-awareness OFUL) and VARLin (Variance-awareness RL with linear model) are proposed. By adaptive shrink the feasible parameter set \\Theta_{k} based on the estimated variance, the authors theoretically show the regrets upper  bounds as \\tilde{O}(poly(d)\\sqrt{1+\\sum_{k}\\sigma^2_k} and \\tilde{O}(ploy(d,log H)\\sqrt{K}) for bandits and linear MDP respectively. Moreover, several technical ideas that may be of independent interest are proposed: the peeling technique to both the input norm and the variance magnitude, 2) a recursion-based estimator for the variance, and 3) a new convex potential lemma that generalizes the seminal elliptical potential lemma.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper proposed two new noise awareness OFUL type algorithms, VOFUL and  VARLin for the linear bandit and linear RL respectively. Both Algorithms first estimate the error terms, use them to shrink the parameter‘s feasible set \\Theta, and finally run the unpenalized regression. For linear bandit, the proposed algorithm reaches O(poly(d)\\sqrt{1+\\sum_{k}\\sigma^2_k}) data-dependent upper bound, where k is the time step. For linear RL, O(poly(d,\\log H)\\sqrt{K}) bound is achieved, where H is the planning horizon. This result improves the dependence in H from linear to logarithmic compared to the literature, e.g., Zhou et al. [2020a]. Moreover, several technical results that may be of independent interest are proposed.\n\nQuality:  The proposed model reaches promising H dependence for linear RL settings. This novel result improves the literature. However, for the linear bandit case, I’m a little bit concerned about the author's claim on \"no explicit dependence on K\". In fact, if the variance \\sigma_k is a constant over time, the bound in this paper becomes O(poly(d)\\sqrt{1+k\\sigma^2}), which contains the k dependence as long as sigma is not  0. Moreover, in Theorem 1 and Theorem 2 in [1], the O(poly(d)\\sigma\\sqrt{K}) dependence has already be achieved. Based on the current draft, the author's claim on the bandit may not be well supported.\n\nClarity: The presentation of this paper is ok but it can be certainly further improved. For example, the authors present two algorithms with relatively complex structures, more discussions or remarks on how those algorithms work, and why they allow gaining better regret bound will be helpful.\n\nSignificance: This paper discusses an interesting question that we may use adaptive procedures with noise awareness to gain better regrets. In general, it is an exciting idea since in the real world the online problems involving distribution drifting are very common. If we can adaptively tune the algorithm instead of always assuming the worst-case parameters to ensure convergence, the numerical performance can be very promising. The regrets bound for linear RL is new and improves the results in the literature. However, I'm a little bit doubt about the novelty claim  \"no explicit dependence on K\" in bandit settings and the authors may need to make further justification. Moreover, the d dependence is at least d^4.5, which is significantly higher than O(d\\sqrt{T}) or O(\\sqrt{dT}) bounds in the bandit literature.\n\n\n[1] Li, Lihong, Yu Lu, and Dengyong Zhou. \"Provably optimal algorithms for generalized linear contextual bandits.\" International Conference on Machine Learning. PMLR, 2017.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1) Line 83-91, the example is kind of written in a misleading way. Since we require sigma^2<<1 and d = 1, how does the first inequality on Line 89 go through? \n\n2) Since the major contribution of this paper is on regrets in theory, it ok to have a huge computation cost to run the algorithms. And in section 6, the authors also discuss the computation issue and argue that many statistically efficient algorithms are computationally inefficient.   It would be better to add some discussions in the main paper to point out some modifications on the algorithm to improve the computation efficiency. \n\n**After engaging in the discussion, I think the paper discusses an interesting topic and contains non-trivial results. The authors have already addressed my questions. Therefore, I would like to change my score to accept this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "LrvypxSb8o", "reviewer": "Reviewer_mxmq", "summary": "This paper proposes a new bandit and MDP algorithms for minimizing regret. The bandit algorithm enjoys a variance dependent bound, and the MDP algorithm (linear mixture) enjoys a horizon independent regret bound. The main technical novelty is a novel confidence set construction and a new convex potential lemma. The bandit regret bound has a worse scaling with dimensionality than the standard algorithms but can be significantly smaller depending on the variances.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n[main review]\n\nOriginality 5/5: the solution is very novel.\n\nQuality 4/5: \n\nClarity 4/5: The paper is mostly clear.\n\nSignificance 4/5: Although the algorithms are not computationally tractable, showing that such a variance dependent bound is possible is quite important.\n\nThere is a lot to think about the solution in this paper, and I did enjoy reading and thinking about this problem closely. My understanding is that the clipping is achieving some sort of robust estimator so that the confidence bound effectively does not have the usual Berstein-style lower-order term. The difference from something like Cantoni estimator is that  there is no explicit estimator that is constructed. \n\nIt would be helpful to compare with other variance dependent confidence sets. Here are two main differences from \"Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits\" by Abeille, Faury, and Calauzenes:\n\n* Abeille et al. use the model where the mean reward is $\\mu(x\\theta)$ rather than $x\\theta$.\n* Abeille's reward model is Bernoulli, so the rewards are necessarily binary. Constructing confidence bounds is EASIER for this Bernoulli case because the variance is a function of the mean. The authors are discussing something more general where the variance can be arbitrarily small (and always not larger than the variance of the Bernoulli case, when the rewards are scaled to [0,1]).\n\nAdding comparison to logistic bandits may clarify the main point of the paper clearly.\n\nA related comment on L236 : actually, Abeille et al. show a regret bound of $\\sqrt{\\sigma_*^2 K}$ where $\\sigma^2$ is the variance of the best arm (of course, they assume a fixed arm set). This is worth being discussed.\n\nFor Theorem 3, it seems like the effect of epsilon-net is not analyzed? For example, Eq (33) is not true for $\\theta_k$ because there is no guarantee that \\mu_k is exactly one of the members in $\\mathcal{B}$, no?\n\nOne main question that bothers me is the form of the confidence set. Do the authors think the current confidence set is tight? It is not clear to me whether the loose factor on the dimensionality comes from the confidence set construction or from the analysis (including the new potential lemma). I would really like to have some more understanding on this.\n\nAlso, if we do not have the issue of the lower order term from the Bernstein inequality, can we achieve $d\\sqrt{\\sum_k \\sigma_k^2}$ easily? Just trying to see what is the source of looseness.. \n\nRemark 1: I am curious to know details about this. When you clip the subgaussian noise, there is bias that gets introduced (because after clipping it is not zero-mean anymore), and this cumulates and may hinder tight concentration bounds. That is, one cannot treat clipped subgaussian noise as if it was a bounded noise. How would you handle this? \n\n[minor comments]\n\n* L86: Faury et al. is not related to this the discussion here as it assumes the logistic model and it will have a different definition of  $\\Lambda_{k-1}$.\n* L118: \"underlying 1 coefficient θ^*\" => I did not understand what that \"1\" stands for.\n* L109: the notation B_2^d(1) is used before being defined (L177)\n* The proof of Theorem 4 appears in a weird way. Section D.2 is a large section, and the proof of Theorem 4 appears at a random location of L725. It was hard to navigate through. (or, did you mean to say 'proof of theorem 3' for the section D.2?)\n* display after 553: 2/delta should be 4/delta?\n* L582: the closing parenthesis } is in a wrong location.\n* Q on section B: L486 and L591 should have $\\\\|\\theta^* - \\hat\\theta\\\\|_{\\Lambda_K}$ rather than $|\\theta^* - \\hat\\theta|$\n* notation mismatch: L185 says r_k is the reward but in the algorithm 1 y_k is the reward.\n* The display after L741: I think there must be some typos here as it does not lead to (34). I've confirmed that (34) is correct, though.\n\n----\n\n**after rebuttal**\n\nI am satisfied with the rebuttal. Thanks for sharing your thoughts on various questions I have raised. Please spend some time on clarifying, fixing typos, and making it complete (e.g., analyzing the effects from the $\\epsilon$-net). It will make your great work even greater.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "JGZa3PpxHD-", "reviewer": "Reviewer_hVCh", "summary": "This paper studies the regret bound of linear bandits and linear mixture MDP problems. The authors develop algorithms with variance-aware confidence sets and achieve a data-dependent regret bound.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n1. For linear bandits, the regret bound only scales with the variance and the dimension. If the variances are very small, the bound can be significantly smaller than $\\sqrt{K}$, where $K$ is the number of rounds.\n\n2. For the linear mixture MDP in the linear approximation settings, this work introduces an algorithm that is only scaling logarithmically with the horizon $H$, which is important when $H$ is relatively large.\n    \n3. The algorithms do not need the information of the true variance.\n  \n4. The reviewer thinks that the technical ideas developed in the paper would probably be of interest to the community.\n\nWeaknesses\n\n1. Is it possible to remove the assumption $\\sum_h^H r_h \\le 1$ (Assumption 2) that is not required in work [1]? This assumption is not generally true in practice. Without this assumption, we have $\\sum_h^H r_h \\le H$, and then the regret bound may depend more on $H$ than the current result. The reviewer thinks that the difference between the result in the paper and the result in [1] should be mentioned. \n\n2. Although this work's strength is in its theoretical development, however, the supplemental material is badly structured, which is difficult to follow. The reviewer thinks that a proof roadmap should be given. Also, the titles are misleading. For example, in the proof of Theorem 4 in the supplemental material, Line 722-724, it says that Theorem 3 is proved. And in Line 725, some proof jumps in without any reference.\n    \n3. The algorithms presented are computationally inefficient as mentioned in the discussion part of the paper. The reviewer thinks that the computational complexity should be analyzed with more detail.\n\nOther comments:\n\n1. Page 2 Line 40: The reviewer suggests that the full name of ``MVP'' be presented.\n\n2. Page 5 Line 189-193 Remark 1: Does $T$ represent the number of rounds? The notation is confusing since $K$ is used for the number of rounds in the rest of the paper.\n\n\n[1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. \"Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.\" arXiv preprint arXiv:2012.08507 (2020).\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "8ScR5zc16jK", "reviewer": "Reviewer_SrYX", "summary": "This paper proposes a new design of the confidence set in the linear bandit problem and linear mixture RL problem. The new confidence set leads to a different regret bound, that has worse dependence on the dimension but only logarithmic dependence on the horizon length. This new design of confidence sets is the main contribution, which composes the convex potential lemma and the peeling argument.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "A good paper that presents new ways to construct variance-aware confidence sets. The peeling argument is interesting, along with the convex potential lemma. The results have logarithmic dependence on the horizon, which is strong. Although the $d^{4.5}$ dependence is not favorable and it looks not easy to reduce the dependence from the convex potential lemma. I only carefully checked the proof for the linear bandit part. There is no obvious technical bug. But I would suggest the authors re-organize the proof to make the structure more clear. Currently, the proof of some lemma is delayed into later sections, while others are shown directly after the statement of the lemma.\n\nFor the clarity of the presentation, I suggest the authors write a more detailed proof sketch for the bandit problem, as it already contains most contributions of this work. It would help a lot to show the reader how the confidence sets are constructed from the idea of dividing norm layers.  \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors clearly state the limitations of the current method and discuss the possible extensions or improvements.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of adapting to noise variance in linear bandits and reinforcement learning (linear mixture MDPs). The reviewers agree that the main technical result in the paper (a new confidence set construction which is adaptive to variance) is interesting and highly non-trivial. This is a timely result, and I am confident this technique will find broader use. In addition, there are many interesting directions (e.g., improving computational efficiency) for future work.

While the reviewers felt that the paper is generally well-written, the authors are encouraged to incorporate their suggestions to improve the clarity and organization of the main body and appendix.
Decision: Accept (Poster)