Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
Year: 2022

Abstract:
This paper presents new 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 r Oppolypdq b 1` řK k“1 σ 2 kq data-dependent regret bound, where d is the feature dimension, K is the number of rounds, and σ k is the 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 no explicit polynomial dependency on K. When variances are small, this bound can be significantly smaller than the r Θ `

text: • For linear bandits, we obtain an rOppolypdq b
1` řK k“1 σ 2 kq data-dependent
regret bound, where d is the feature dimension, K is the number of rounds, and σ2k is the 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 no explicit polynomial dependency on K. When variances are small, this bound can be significantly smaller than the rΘ ` d ? K ˘ worst-case regret bound. • For linear mixture MDPs, we obtain an rOppolypd, logHq ? Kq 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 logarithmically 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) 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.

heading: 1 Introduction
text: 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 rΘpd ? Kq [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.2 However, oftentimes the worst-case analysis is overly pessimistic, and
˚Equal contribution. 2We follow the reinforcement learning convention to use K to denote the total number of rounds / episodes.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
it is possible to obtain data-dependent bound that is substantially smaller than rOpd ? Kq in benign scenarios.
One direction to study is the variance magnitude. As a motivating example, in linear bandits, if there is no noise (variance is 0), one only needs to pay at most d regret to identify the best action because d samples are sufficient to recover the underlying linear coefficients (in general position). This constant-type regret bound is much smaller than the ? K-type regret bound in the worst case where the variance magnitude is a lower bounded constant. Therefore, a natural question is:
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 ? K-type bound?
In RL, exploiting the variance information is also important. For tabular RL, 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 rOppolylogpHq ˆ p ? SAK ` S2Aqq 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-type 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 et al., 2020, Jin et 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 robotics and queuing systems. We refer readers to Ayoub et al. [2020] for more discussions.
For this linear mixture MDP setting, previous works can obtain regret bounds in the form rOppolypd,Hq ? Kq, 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 to obtain an rOppolypd, logHq ? Kq regret bound for linear mixture MDP?

heading: 1.1 Our Contributions
text: In this paper, we develop new, variance-aware confidence sets for linear bandits and linear mixture MDP and answer the above two questions affirmatively.
Linear Bandits. For linear bandits, we obtain an rOppolypdq b
1` řK k“1 σ 2 kq regret bound, where
σ2k 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 no explicit polynomial dependency on K. When the variance is very small so that σ2k ! 1, this bound is substantially smaller than the worst-case rΘpd ? Kq bound. Furthermore, this regret bound naturally interpolates between the worst-case ? K-type bound and the noiseless-case constant-type bound.
Linear Mixture MDP. For linear mixture MDP, we obtain the desired rOppolypd, logHq ? Kq 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 logarithmically with the planning horizon
3 rOp¨q hides logarithmic factors. Sometimes we write out polylogH explicitly to emphasize the logarithmic dependency on H . 4This 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 3 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 importantly, our result conveys the positive conceptual message for RL: it is possible to simultaneously overcome the two central challenges in RL, large state-action space and long planning horizon.

heading: 1.2 Main Difficulties and Technical Innovations
text: 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 a 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 et al. [2021] also designed an variance-dependent confidence set for logistic bandits. However in their problem the rewards are Bernoulli and the variance is a function of the mean.
We give a simple example to illustrate their limitations. Consider the case where the variance is always σ2 ! 1. Let px1, y1q , . . . , pxk´1, yk´1q be the samples collected before the k-th round. Their confidence set at the k-th round is Θk “ tθ|||θ ´ θ̂k||Λk´1 ď Cpσ ? d ` 1 ` λ1{2qu (See In Equation (4.3) of Zhou et al. [2020a] and Theorem 1 of Faury et al. [2020]). where Λk´1 “ řk´1 τ“1 xτx J τ ` λI is the un-normalized covariance matrix , θ̂k “ Λ´1k´1 řk´1 τ“1 yτxτ is the estimated linear coefficients by least squares, λ is a regularization parameter and C is a constant. Consider the case d “ 1 and xk “ a
1{K for k “ 1, . . . ,K. Their regret bound is roughly K ÿ
k“1 pσ ? d` 1` λ1{2q}xk}Λ´1k ě p1` λ 1{2q K ÿ i“1 }xk}Λ´1k ě p1` λ 1{2q c K 1` λ ě ? K,
which is much larger than our bound, O `? Kσ2 ` 1 ˘
when σ is very small. For more detailed discussion, please refer to Appendix B.
Below we describe our main techniques.
Elimination with Peeling. Instead of using least squares and upper-confidence-bound (UCB), we use an elimination approach. More precisely, for the underlying linear coefficients θ˚ P Rd, we build a confidence interval for pθ˚qJ µ for every µ in an -net of the d-dimensional unit ball, and we eliminate θ P Rd if θJµ fails to fall in the confidence interval of pθ˚qJµ 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 to obtain a tight regret bound for the example above. The new confidence region provides a tighter estimation for θ˚, 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 et al. [2008] any more. Instead, we propose a more general lemma below, which provides a bound of potential for a general class of convex functions though with a worse dependency on d than the bound in the elliptical potential lemma. We believe this lemma can be applied to other problems as well. Lemma 1 (Generalized Quadratic Potential Lemma). Let fpxq ě 0 be a convex function over R such that fpxqx2 ď fpyq y2 ď 1 and fpxq ě fpyq if x
2 ě y2 ą 0. Let Bp1q denote the d-dimensional unit ball. Fix ` P p0, 1s. For any x1,x2, . . . ,xt P Bp1q and µ1,µ2, . . . ,µt P Bp1q, we have that
t ÿ i“1 min
#
fpxiµiq ři´1 j“1 fpxjµiq ` `2 , 1
+
ď Opd4 logpdt{`qq.
Note that by choosing fpxq “ x2 and µi “ xiΛ ´1 i
}xiΛ´1i } with Λi “
ři´1 j“1 xjx J j ` `I, Lemma 1 reduces
to the classical elliptic potential lemma [Dani et al., 2008]. Our proof consists of two major parts.
We first establish a symmetric version of Equation (??) using rearrangement inequality, and then bound the number of times the energy for some µ (i.e.,
ři j“1 fpxjµq ` l2) doubles. The full proof
is deferred to Appendix C.
For linear mixture MDP, we propose another technique to further reduce the dependency on d.
Recursion-based 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 θ˚. Furthermore, the higher moments are polynomial functions of θ˚. 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.

heading: 2 Related Work
text: 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 et al., 2011, Li et al., 2019a,b]. For infinite-actioned linear bandits, the minimax regret bound is rΘpd ? Kq. 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 a 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.
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 a polynomial dependency on the planning horizon H , except works that assume the environment is deterministic [Wen and Van Roy, 2013, Du et al., 2020b].
This paper studies the linear mixture MDP setting [Ayoub et al., 2020, Zhou et 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 rOpdH2 ? Kq regret in the timeinhomogeneous model.5 Our algorithm improves the H-dependency from polypHq to polylogpHq, at the cost of a 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 et al., 2019, Zhang et 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
5The time-inhomogeneous model refers to the setting where the transition probability can vary at different levels, and the time-homogeneous model refers to the setting where the transition probability is the same at different levels. Roughly speaking, the model complexity of the time-inhomogeneous model is H times larger than that of the time-homogeneous model. In general, it is straightforward to tightly extend a result for the time-homogeneous model to the time-inhomogeneous model by extending the state-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 rOp ? dK ` d b
řK i“1 σ 2 i q regret bound, while we prove an rOpd4.5
b
řK i“1 σ 2 i ` d5q
regret bound. Our bound has a worse dependency on d, but in the regime where K 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 rOp ? d2H ` dH2 ? K`d2H2`d3Hq bound for the time-inhomogeneous model, while we prove an rOpd4.5 ? K ` d5q ˆ polylogpHq bound for the time-homogeneous model. Their bound has a better dependency on d than ours and is near-optimal in the regime K “ Ω ppoly pd,Hqq and H “ Opdq. On the other hand, we have an exponentially better dependency on H in the time-homogeneous model. Indeed, obtaining a regret bound that is logarithmic in H (in the time-homogeneous model) was raised as an open question in their paper [Zhou et al., 2020a, Remark 5.5].
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 ? K-free 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 in 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 6 for more discussions.

heading: 3 Preliminaries
text: Notations. We use Bdpprq “ tx P Rd : ‖x‖p ď ru to denote the d-dimensional `p-ball of radius r, so Bp1q “ Bd2p1q For any set S Ď Rd, we use BS to denote its boundary. For N P N, we define rN s “ t1, . . . , Nu. One important operation used in our algorithms and analyses is clipping. Given ` ą 0 and u P R, we define
clippu, `q “ mint|u|, `u ¨ u |u|
for u ‰ 0 and clipp0, `q “ 0. For any two vectors u,v, to save notations, we use uv “ uJv to denote their inner product when no ambiguity.
Linear Bandits. We useK to denote the number of rounds in the linear bandits. At each round k “ 1, . . . ,K, the algorithm is first given the context set Ak Ď Bd2p1q, then the algorithm chooses an action xk P Ak and receives the noisy reward rk “ xkθ˚`εk,where θ˚ P Bd2p1q is the unknown underlying linear coefficients and εk is the random noise. We define Fk “ σpx1, ε1, . . . ,xk, εk,xk`1q. We assume that |rk| ď 1 and that the noise εk satisfies Erεk | Fks “ 0 and Erε2k | Fks “ σ2k. The goal is to learn θ˚ and minimize the cumulative expected regret ErRKs, where
RK “ K ÿ
k“1 rmax xPAk xθ˚ ´ xkθ˚s.
Remark 1. Here we assume the reward is uniformly bounded (|rk| ď 1) instead of 1-sub-Gaussian commonly used in the literature only for the ease of presentation, because in RL, it is standard to assume bounded reward. Note if the noise is 1-sub-Gaussian, our algorithm also applies with only an O plogKq 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 OplogKq.
Episodic MDP and Linear Mixture MDP. We use a tuple pS,A, r, P,K,Hq to define an episodic finite-horizon MDP. Here, S is its state space, A is its action space, r : S ˆAÑ r0, 1s is its reward function, P ps1 | s, aq is the transition probability from the state-action pair ps, aq to the new state s1, K is the number of episodes, and H is the planning horizon of each episode. Without the loss of generality, we assume a fixed initial state s1. A sequence of functions π “ tπh : S Ñ 4pAquHh“1 is an policy, where 4pAq denotes the set of all possible distributions over A.
At each episode k “ 1, . . . ,K, the algorithm outputs a policy πk, which is then executed on the MDP by akh „ πkhpskhq, skh`1 „ P p¨ | skh, akhq. We let rkh “ rpskh, akhq be the reward at time step h in
Algorithm 1 VOFUL: Variance-Aware Optimism in the Face of Uncertainty for Linear Bandits 1: Initialize: `i “ 22´i, ι “ 16d ln dKδ , L2 “ rlog2Ks,Λ2 “ t1, 2, . . . , L2 ` 1u, Θ1 “ B d 2p1q,
Let B be an K´3-net of Bd2p2q with size not larger than p 4K q 3d
2: for k “ 1, 2, . . . ,K do 3: Optimistic Action Selection: 4: Observe context set Ak Ď Bd2p1q 5: Compute xk Ð arg maxxPAk maxθPΘk xθ, choose action xk 6: Receive feedback yk 7: Construct Confidence Set: 8: For each θ P Bd2p1q, define kpθq “ yk ´ xkθ, ηkpθq “ p kpθqq2. 9: Define confidence set Θk`1 “ Ş
jPΛ2 Θ j k`1, where
Θjk`1 “ " θ P Bd2p1q : ∣∣∣∣∣ kÿ v“1 clipjpxvµq vpθq ∣∣∣∣∣ ď g f f e k ÿ v“1 clip2j pxvµqηvpθqι` `jι,@µ P B * (1)
and clipjp¨q “ clipp¨, `jq. 10: end for
episode k. Importantly, we assume the transition model P p¨ | ¨, ¨q is time-homogeneous, which is necessary to bypass the polypHq dependency. We assume that the reward function is known, which is standard in the theoretical RL literature to simplify the presentation [Modi et al., 2020, Ayoub et al., 2020]. We let π˚ to denote the optimal policy which achieves the maximum reward in expectation.
We make the following regularity assumption on the rewards: the sum of reward, řH h“1 rh, in each episode is bounded by 1.
Assumption 2 (Non-uniform reward). řH h“1 r k h ď 1 almost surely for any policy πk.
This assumption is much weaker than the common assumption where the reward at each time step is bounded by 1{H (uniform reward) because Assumption 2 allows one spiky reward as large as Ω p1q. See more discussions about this reward scaling in Jiang and Agarwal [2018], Wang et al. [2020a], Zhang et al. [2020a].
For any policy π, we define its H-step V -function and Q-function as
V πh psq “ max aPA Qπhps, aq
where Qπhps, aq “ rps, aq ` Es1„P p¨|s,aqV πh`1ps1q for h “ 1, . . . ,H
where we set VH`1 “ 0. For simplicity, we also denote V πps1q “ V π1 ps1q and V ˚ps1q “ V π ˚ps1q.
A linear mixture MDP is an episodic MDP with the extra assumption that its transition model is an unknown linear combination of a known set of models. Specifically, there is an unknown parameter θ˚ P Bd1p1q, such that P “ řd i“1 θ ˚ i Pi where based models P1, . . . , Pd are given. The goal is to learn θ˚ and minimize the cumulative expected regret ErRKs, where
RK “ k ÿ
k“1 rV ˚ps1q ´ V kps1qs.

heading: 4 Algorithm and Theory for Linear Bandits
text: In this section, we introduce our algorithm for linear bandits and analyze its regret. The pseudocode is listed in Algorithm 1. The following theorem shows our algorithm achieves the desired variance-dependent regret bound. The full proof is deferred to Section D.
Theorem 3. The expected regret of Algorithm 1 is bounded by ErRKs ď rOpd4.5 b řK k“1 σ 2 k ` d5q.
This theorem shows our algorithm’s regret has no explicit polynomial dependency on the number of rounds K. In the worst-case where the variance is Ω p1q, our bound becomes rO ` d4.5 ? K ` d5 ˘
, which has a 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 op1q, our bound can be much smaller. In particular, in 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.

heading: 4.1 Main Algorithm
text: Now we describe our algorithm. Similar to many other linear bandit algorithms, the algorithm maintains confidence sets tΘkukě1 for the underlying parameter θ˚, and then choose the action greedily according to the confidence set.
To relax the known variance assumption, we 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 was used in existing works [Zhou et al., 2020b, Faury et al., 2020].
Theorem 4. Let tFiuni“0 be a filtration. Let tXiuni“1 be a sequence of real-valued random variables such that Xi is Fi-measurable. We assume that ErXi | Fi´1s “ 0 and that |Xi| ď b almost surely. For δ ă e´1, we have
Pr
»
– ∣∣∣∣∣ nÿ i“1 Xi ∣∣∣∣∣ ď 8 g f f e n ÿ i“1 X2i ln 1 δ ` 16b ln 1 δ fi fl ě 1´ 6δ log2 n. (2)
Importantly, this inequality controls the deviation via the empirical variance, which is X2i and can be computed once Xi 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 to designing a 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 is 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., 2011], or the weighted one [Zhou et al., 2020a].
We drop the least square estimators and instead, we take a testing-based approach, as done in Equation (1). To illustrate the idea, we first ignore the clipjp¨q operation and `j terms. We define the noise function kpθq and the variance function ηkpθq (Line 8 of Algorithm 1). Note that kpθ˚q “ εk and ηkpθ˚q “ ε2k, so we have the following fact: if θ “ θ˚, then Equation (2) would be true if we replace Xk “ wkpµq kpθq and X2k “ w2kpµqηkpθq with high probability, where twkpµqu is a proper sequence of weights depending on the test direction µ. Our approach uses the fact in the opposite direction: if weighted wkpµq kpθq, w2kpµqηkpθq satisfies Equation (2) for all possible test directions µ in an K´3-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-based algorithm: if there exists some test direction µ such that Equation (2) fails for Xk “ wkpµq kpθq and X2k “ w2kpµqηkpθq, then we eliminate θ from the confidence set permanently.
Given the test direction µ, following the least square estimation, wkpµq is set to be xkµ. However, with wkpµq “ xkµ, the right-hand-side of Equation (2) is at least b ě max1ďkďn |wkpµq| “ max1ďkďn |xkµ|, which might be dominant compared with řn k“1 w 2 kpµqηkpθq (See Appendix B for a toy example). To address this problem, we consider to peel wkpµq for various thresholds of difference level. More precisely, we construct confidence regions respectively with wjkpµq “ clipjpxkµq, where lj “ 22´j for j “ 1, 2, . . . , rlog2Ks. 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 information [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 an rOp ? Kq term.

heading: 4.2 Proof Sketch of Theorem 3
text: Now we explain how our confidence set enables us to obtain a variance-dependent regret bound. We define θk “ arg maxθPΘk xkpθ ´ θ ˚q and µk “ θk ´ θ˚. Then our goal is to bound the regret ř
k xkµk. Our main idea is to consider txku, tµku as two sequences of vectors. We decouple the complicated dependency between txku and tµku by a union bound over the net B (defined in Line 1 of Algorithm 1). To bound the regret, we implicitly divide all rounds k P rKs into norm layers based on log2 |xkµk| in the analysis. 6 Within each layer, we apply Equation (1) to obtain the relations between µk and tx1, . . . ,xk´1u, 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-independent term in Bernstein inequalities ( a ř
X2i ą „ b in Theorem 4), which resolves the variance-independent 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.e., the events where θ˚ R Θk for some k P rKs) is properly bounded (see Lemma 18). Assuming the successful events happen, we have that θ˚ P Θk for all k P rKs. Then we obtain that.
RK :“ K ÿ
k“1
ˆ
max xPAk
θ˚ ´ xkθ˚ ˙ ď K ÿ
k“1 max
xPAk,θPΘk xkpθk ´ θ˚q ď
K ÿ k“1 xkpθk ´ θ˚q “ K ÿ k“1 xkµk.
Next we divide the time steps rKs into L2 ` 1 disjoint subsets tKjuL2`1j“1 according to the magnitude of xkµk. More precisely, for for 1 ď j ď L2 we assign k to Kj iff xkµk P plj{2, ljs, and for j “ L2 ` 1, we assign k to Kj iff xkµk ď ll2`1{2. Define
Φjkpµq “ k´1 ÿ
v“1 clipjpxvµqxvµ` `2j , Ψ j kpµq “
k´1 ÿ v“1 clip2j pxvµqηvpθ˚q. (3)
By the definition of Θk in (1), we have that (see Claim 20)
K ÿ k“1 xkµk ď 1` L2 ÿ j“1 ÿ kPKj
xkµk ˆ 3 b Ψjkpµkqι` b řk´1 v“1 2clip 2 j pxvµkqpxvµkq2ι` 3`jι
Φjkpµkq . (4)
Continuing the computation, we have that
L2 ÿ
j“1
ÿ
kPKj
xkµk
b
řk´1 v“1 2clip 2 j pxvµkqpxvµkq2ι
Φjkpµkq
ď 1 2
L2 ÿ
j“1
ÿ
kPKj
xkµk ` L2 ÿ
j“1
ÿ
kPKj
xkµkI "
b
řk´1 v“1 2clip 2 j pxvµkqpxvµkq2ι
Φjkpµkq ą 1 2
*
ď 1 2
L2 ÿ
j“1
ÿ
kPKj
xkµk ` L2 ÿ
j“1
ÿ
kPKj
xkµk 4ljι
Φjkpµkq (5)
ď 1 2
L2 ÿ
j“1
ÿ
kPKj
xkµk `Opd4|Λ2|ι log3pdKqq, (6)
6This cannot be done explicitly in the algorithm, since it would re-couple the two sequences.
Algorithm 2 VARLin: Variance-Aware RL with Linear Function Approximation 1: Initialize: `i “ 22´i, ι “ 16d ln dHKδ , L0 “ rlog2KHs, L1 “ L2 “ r5 log2pHKq ` 3s,Λ0 “ t0, 1, , . . . , L0u,Λ1 “ t1, . . . , L1u,Λ2 “ t1, . . . , L2u. B be an pHKq´3-net of Bd1p2q with size no larger than p 4HK q
3d. Θ1 “ Bd1p1q. 2: for k “ 1, 2, . . . ,K do 3: Optimistic Planning: 4: for h “ H,H ´ 1, . . . , 1 do 5: For each ps, aq P S ˆA, let Qkhps, aq “ mint1, rps, aq `maxθPΘk řd i“1 θiP i s,aV k h`1u. 6: For each s P S, let V kh psq “ maxaPAQkhps, aq. 7: end for 8: for h “ 1, 2, . . . ,H do 9: Choose action akh Ð arg maxaPAQkhpskh, aq, observe the next state skh`1.
10: end for 11: Construct Confidence Set: 12: For m P Λ0, h P rHs, define the input xmk,h “ rP 1skh,akhpV k h`1q2 m , . . . , P d skh,a k h pV kh`1q2 msJ. 13: For m P Λ0, h P rHs, define the variance estimate ηmk,h “ maxθPΘktθx m`1 k,h ´ pθxmk,hq2u. 14: Denote mv,upθq “ θxmv,u ´ pV vu`1psvu`1qq2 m
for m P Λ0, u P rHs, v P rk ´ 1s 15: Define T m,ik`1 “ tpv, uq P rks ˆ rHs : ηmv,u P p`i`1, `isu, T m,L1`1 k`1 “ tpv, uq P rks ˆ rHs : ηmv,u ď `L1`1u. 16: Define the confidence ball Θk`1 “ Ş m,i,j Θ m,i,j k`1 , where
Θm,i,jk`1 “ # θ P Bd1p1q : ∣∣∣∣∣∣ ÿ
pv,uqPT m,ik
clipjpxmv,uµq mv,upθq ∣∣∣∣∣∣ ď4 d ÿ
pv,uqPTm,ik
clip2j pxmv,uµqηmv,uι` 4`jι,@µ P B +
(7)
and clipjp¨q “ clipp¨, `jq 17: end for
where (5) is by the fact that
b
řk´1 v“1 2clip 2 j pxvµkqpxvµkq2ι
Φjkpµkq ą 12 implies that
4ljι
Φjkpµkq ą 1, and (6) follows
by Lemma 17. By (4) and (6), we have that
K ÿ k“1 xkµk ď 12 L2 ÿ j“1 ÿ kPKj xkµk ˆ
b
Ψjkpµkqι
Φjkpµkq ` Õpd5q
ď L2 ÿ
j“1
ÿ
kPKj
12xkµk`j
Φjkpµkq
g f
f
e
K ÿ k“1 ηkpθ˚qι` Õpd5q ď Opd4|Λ2| log3pdKqq
g f
f
e
´ ln 1
δ `
K ÿ k“1 σ2k ¯ ι` Õpd5q,
where the last inequality uses Lemma 17. Therefore, the regret bound is Õ ˆ d4.5 b
řK k“1 σ 2 k ` d5
˙
.
See Section D for the full proof.

heading: 5 Algorithm and Theory for Linear Mixture MDP
text: We introduce our algorithm and the regret bound for linear mixture MDP. Its pseudo-code is listed in Algorithm 2 and its regret bound is stated below. The proof is deferred to Section E.
Theorem 5. The expected regret of Algorithm 2 is bounded by ErRKs ď rO ` d4.5 ? K ` d9 ˘ .
Before describing our algorithm, we introduce some additional notations. In this section, we assume that, unless explicitly stated, the variables m, i, j, k, h iterate over the sets Λ0,Λ1,Λ2, rKs, rHs, respectively. See Line 1 of Algorithm 2 for the definitions of these sets. For example, at Line 16 of Algorithm 2, we have Ş
m,i,j Θ m,i,j k`1 “ Ş mPΛ0,iPΛ1,jPΛ2 Θ m,i,j k`1 .
The starting point of our algorithm design is from Zhang et al. [2020a], in which the authors obtained a nearly horizon-free regret bound in tabular MDP. A natural idea is to combine their proof with our results for linear bandits and obtain a 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 Θk is updated at a per-round level, in that Θk is built using all rounds prior to k; while for the RL setting, the confidence set Θk could only be updated at 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 in a gap between the confidence set built using data prior to episode k, and that built using data prior to time step pk, hq. Fortunately, we are able to resolve this issue. In Lemma 22, we show that we can relate these two confidence intervals, except for Õpdq “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 rOpd6.5 ? Kq. To further reduce the horizon-free regret bound to Õpd4.5 ? Kq, 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 no 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 a quadratic function of θ˚. Therefore, we can use the peeling technique on the variance magnitude to reduce the regret (comparing Equation (30) and Equation (43) in appendix). We note that one can also apply this step to linear bandits if the variance can 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 (x2), and the regret of variance predictions can be bounded by the variance of variance, namely the 4-th moment. Still, a peeling step on 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 to use this idea: we estimate 2-th, 4-th, 8-th, . . . , OplogKHq-th moments. The index m is used for moments, and Λ0 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.

heading: 6 Discussions
text: By incorporating the variance information in the confidence set construction, we derive the first variance-dependent 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 is our bounds rely on the convex potential lemma (Lemma 17), which is rOpd4q. In analogous to the elliptical potential lemma in [Abbasi-Yadkori et al., 2011], we believe that this bound can be improved to rOpdq. 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 elimination-based 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 et al., 2019, Du et al., 2021, Jin et al., 2021].

heading: Acknowledgement
text: Simon S. Du gratefully acknowledges funding from NSF Award’s IIS-2110170 and DMS-2134106.

Review summaries:
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.

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. 

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.