Bandit Learning with General Function Classes: Heteroscedastic Noise and Variance-dependent Regret Bounds
Authors: Heyang Zhao
Dongruo Zhou
Jiafan He
Quanquan Gu
Venue: Submitted to ICLR 2023 (2023)

Abstract: We consider learning a stochastic bandit model, where the reward function belongs to a general class of uniformly bounded functions, and the additive noise can be heteroscedastic. Our model captures contextual linear bandits and generalized linear bandits as special cases. While previous works (Kirschner and Krause, 2018; Zhou et al., 2021) based on weighted ridge regression can deal with linear bandits with heteroscedastic noise, they are not directly applicable to our general model due to the curse of nonlinearity. In order to tackle this problem, we propose a \emph{multi-level learning} framework for the general bandit model. The core idea of our framework is to partition the observed data into different levels according to the variance of their respective reward and perform online learning at each level collaboratively. Under our framework, we first design an algorithm that constructs the variance-aware confidence set based on empirical risk minimization and prove a variance-dependent regret bound. For generalized linear bandits, we further propose an algorithm based on follow-the-regularized-leader (FTRL) subroutine and online-to-confidence-set conversion, which can achieve a tighter variance-dependent regret under certain conditions.

Under review as a conference paper at ICLR 2023
BANDIT LEARNING WITH GENERAL FUNCTION CLASSES: HETEROSCEDASTIC NOISE AND VARIANCE- DEPENDENT REGRET BOUNDS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider learning a stochastic bandit model, where the reward function be- longs general class of uniformly bounded functions, and the additive noise can be heteroscedastic, Our model captures contextual linear bandits and general- ized linear bandits as special cases. While previous works (Kirschner & Krause 2018 Zhou et al.] ( based on weighted ridge regression can deal with linear bandits with heteroscedastic noise, they are not directly applicable to our general model due to the curse nonlinearity. In order to tackle this problem, we pro- pose a multi-level learning framework for the general bandit model. The core idea of our framework is to partition the observed data into different levels ac- cording to the variance of their respective reward and perform online learning each level collaboratively. Under our framework, we first design algorithm that constructs the variance-aware confidence set based on empirical risk minimiza- tion and prove a variance ceriance-dependent regret bound. For generalized linear bandits, we further propose an algorithm based on gellow-te-regullaiiee-leeee subroutine and online-to-cuee co-confidencc-set conversion, which can achieve tighter veriance-deepndent regret under certain conditions.
(FTRL)
INTRODUCTION
Over the past decade, stochastic bandit algorithms have found wide variety of applications in online advertising, website optimization, recommendation system and many other tasks (Li et al,, 2010 McInerney et al.) 2018). In the model of stochastic bandits, at each round, an agent selects an action and observes a noisy evaluation the reward function for the chosen action, aiming to maximize the sum of the received rewards. A general reward function governs the reward of each action from the eligible action set.
A common assumption used in stochastic bandit problems is that the observation noise is condition- ally independent and satisfies a uniform tail bound. In real-world applications, however, the variance of observation noise is likely to be dependent the evaluation point (chosen action) (Kirschner & Krause (018).. Moreover, due to the dynamic environment in reality, the variance of each action may also be different each round. This motivates the studies of bandit problems with heteroscedastic noise. For example, Kirschner & Krause (2018) introduced the heteroscedastic noise setting where the noise distribution is allowed depend the evaluation point. They proposed weighted least squares to estimate the unknown reward function more accurately in the setting where the under- lying reward function linear or lies in a separable Hilbert space (Section 5, Kirschner & Krause 2018).
In this paper, we consider a general setting, where the unknown reward function belongs known general function class FF with bounded eluder dimension (Russo & Van Roy 2013). This captures multi-armed bandits, linear contextual bandits (Abbasi- Yadkori et al. [201]) and generalized linear bandits (Filippi et al.) 2010) simultaneously. Since weighted least squares highly depends on the linearity of the function class, we propose a multi-level learning framework for our general setting. The underlying idea of the framework is partition the observed data into various levels according to the variance of the noise. The agent then estimates the reward function at each level independently and then exploit all the levels when selecting action each round.

---

Under review as a conference paper at ICLR 2023
While previous work by Kirschner & Krause (2018) considered Lub-Gaussian noise with nonuniform variance proxies, we only assume nonuniform variances of noise (Zhou et al. 2021 Zhang et al.) 202I), which brings new challenge of exploiting the variance information of the noise to obtain tighter variance-aware confidence sets.
Under our malti-level learning framework, first design an algorithm based empirical risk minimization and Optimism-in-the -attte--acc--o--neettaill dependent regret bound. For special class of bandits namely generalized linear bandits with het- eroscedastic noise, we further propose an algorithm using follow-the-regullriieeeee an online regression subroutine and adopting the technique of online-to- ceaee-tooooofieeceeeeeeee conversion (Abbasi- Yadkori et al.) 2012 Jun et al., 2017). This algorithm achieves provaly tighter regret bound when the range of the reward function is relatively wide compared to the magnitude of noise.
(OFU) principle, and prove a variance-
(FTRL) as
Our main contributions are summarized as follows:
We develop a new framework called multi-level regression, which can be applied to heteroscedas- tic bandits, even when the reward function class does not lie in separable Hilbert space.
Under our framework, we design tighter variance-aware upper confidence bounds for bandits with general reward functions, and propose an bandit learning algorithm based on empirical risk minimzation. We show that our algorithm enjoys variance-dependent regret upper bounds which be regarded as strict extension of previous algorithms which obtain variance-dependent regret bounds on simpler bandit models (Zhou et al.) 2021 Zhang et al. 2021).
For generalized linear bandits (Filippi al. 2010 Jun al. 2017), which is special case of our model class, we further propose an algorithm based on milie-to-coofideecesss conversion. We first prove variance-dependent regret bound for www.-tt-rregllaized--eeeeeee
(FTRL) for the online regression problem derived from generalized linear function class, and then convert the online learning regret bound the bandit learning confidence set. We show that our algorithm can achieve tighter regret bound for generalized linear bandits.
As by-product, our regret bound for FTRL improves the late-of-theear regret result ( R²) obtained by stochastic online linear regression Ouhamma et al. 2021) (do max) (omitting the terms without dependence on d), where d is the dimension of contexts, R is the upper bound of the nub-Gaussian norm of the noises at each step, and max is the upper bound of the variances of the noises.
Table I: A summary of our regret results and previous results under different settings.
Function Class
Algorithm
Regret
Efficiency
Unknown VAR
Linear
Weighted OFUL.
δ (dvJ RVAT)
Computationally efficient
Zhou el al.
2021
Linear
VOFUL
δ (d..5 RR)
Inefficient
Zhang et al. 2021
MI. ERM
Olydinm [N.) / dimæ log( RTT
Oracle
General
(This work)
efficient
ML + GLOC
Ō dVJ (KAB RTVTT)
Computationally efficient
G-Lin
(This work)
Refer Section for the definitions of dimg, J and R. Section the definitions of K, A, B. We write general function class with eluder dimension dim g as 'General and generalized linear function class as 'G-Lin" for short. Oracle efficiency refers the computational efficiency given regression oracle (i.c., empirical risk minimization) for the involved function class and an optimization oracle which maximizes the reward function f(x) for a fixed under some constraint set of f.
Notation. We use lower letters denote scalars, and lower and upper case bold face letters to denote vectors and matrices respectively. We denote by [n] the set [I.....71] For a vector E Id and matrix Σ E gdxd positive semi-definite matrix, we denote by ||x||2 the vector's Euclidean norm and define ||x|| Vx Σx. For two positive sequences }a, and {b,}} with 2, ... write an O(b,) if there exists absolute constant C > 0 such that on Cb, holds for all n 2 1 and write a, S2(b,) if there exists an absolute constant C > such that a, Ch₁ holds for all n 1. Let NVF, a, |l>>) denote the a-covering number of F in the
2

---

Under review as a conference paper at ICLR 2023
sup-norm || -1ae.
If there is no ambiguity, we may write MVF a, || |lac) Na for short. We use Õ.) further hide the polylogarithmie factors other than log-covering numbers.
2 RELATED WORK
Learning with heteroscedastic noise. Heteroscedastic noise has been studied in many different
settings such as active learning Antos al. (010), regression (Aitken 1936 Goldberg al. 1997,
Chaudhuri et al. 2017 Kersting et al. 22007] principle component analysis (Hong et al., 2016 2018)
and Bayesian optimization (Assael et al. 2014). However, only few works have considered het- eroscedastic noise in bandit settings. Cowan et al. (2015) considered variant of multi-armed bandits where the noise at each round is a Gaussian random variable with unknown variance, Kirschner & Krause (2018) is the first to formally introduce the concept of stochastic bandits with heteroscedas- tic noise. In their model, the variance of the noise at each round is a function of the evaluation point 2t, Pt p(az), and they further assume that the noise is pr-sub-Gaussian Gaussian. Pt can either be observed at time t or either be estimated from the obsevations. [hoo et al. (2021) considered linear bandits with heteroscedastic noise and generalized the heteroscedastic noise setting in Kirschner & Krause (0118) in the sense that they no longer assume the noise to be --ssub-Gaussian but only requires the variance of noise to be upper bounded by 3 and the variances are arbitrarily decided by the environment. which is not necessarily a function of the evaluation point. In the same setting as in Zhou al.] (2021). )) Zhang et al.) (2021) further considered a strictly harder setting where the noise has unknown variance. They proposed an algorithm which can deal with unknown variance through a computationally inefficient clip technique. Our work basically considers the noise setting proposed by Zhou et al. (2021) and further generalizes their setting to bandits with general function classes. We will consider to extend it to the harder setting as Zhang et al. (202I) as future work.
Bandits with known function classes. Moving beyond multi-armed bandits, there have been significant theoretical advances on stochastic bandits with function approximation. Among them, there is huge body of literature
linear bandit problems where the reward function is assumed to be a linear function of the feature vectors attached to the actions (Dani et al.) 2008 Abbasi- Yadkori eet al. 2011 Chu et al., 2011 Li al. 2019; 2021b). Generalizing the restrictive linear rewards, there has also been a flurry of studies on generalized linear bandit problems (Filippi et al.) 2010 Jun
al. 2017 Li al. 2017 Kveton al. 2020).
As for stochastic bandits with general function classes, the seminal work by Russo & Van Roy (2013) introduced the notion of eluder dimension measure the complexity of the function class and provided a general UCB-like algorithm that works for any given class of reward functions with bounded eluder dimension. They further proved a regret upper bound of order (ddimm log.N TT) for their proposed algorithm where dimg is the eluder dimension and log stands for the log- covering number of the funciton class. Linear bandits and generalized linear bandit problems can be seen as special cases as their proposed general model.
co-eeeeededeeeeeettt conversion. Abbasi-Yadkori al. (2012) may be the first one to intro- duce the technique that takes in an online learning subroutine and turns the output of it into a con- fidence set at each round. While Abbasi- et al. (2012) considered applying this technique in linear bandits, Jun et al. (2017) generalized and introduced the previous approach to Generalized Linear Online-to-Cen to-confidence-eee Conversion (GLOC) and applied it to generalized linear bandits.
Online regression for linear functions. Online linear regression has long been studied in the setting where the response variables (or labels) are bounded and chosen by adversary (Bartlett let al. | [esa--Baanhh et al.] 1996) Kivinen & Warmuth] 1997] Littlestone et al.] 1991] Malek & Bartlett 2018), mention a few. A recent work (Ouhamma et al., 2021) considers the stochastic setting where the response variables are unbounded and revealed by the environment with additional random noise on the true labels. Ouhamma et al. (202T) discussed the limitations of online learning
algorithms in the adversarial setting and further advocates for the need of complementary analyses for existing algorithms under stochastic unbounded setting.
MULTI-LEVEL LEARNING FRAMEWORK
We introduce the Multi-level learning framework in this section.
3

---

estima- Under review as a conference paper at ICLR 2023
3.1 PRELIMINARIES
General function class Following (Russo& & Van Roy 2013),
introduce the e-dependence and eluder dimension notion, which are used to measure the complexity of general function class F.
Definition 3.1 (e-dependence, Russo & Van 2013). An action a E A is c-dependent on actions {a1,02- 02, ,a,} } E A with respect to F if any pair of functions f. E F satisfying > (f(a;) f(a;))² < 22 also satisfies f(a) - F(a) S c.
Further, a is c-independent of {ai,'.. ,.n) with
respect to F if a is not e-dependent on {a1. , ,0n).
Definition 3.2 (eluder dimension, Russo & Van Roy 2013). The e-cluder dimension dimg(F, is the length d of the longest sequence of elements A such that, for some é' 2 c, every element is é' e'-independent of its predecessors.
In this work focus general function class F with bounded eluder dimension, and we consider generalized linear function class as a special case. We would like to point out that the function class with small eluder dimension is strictly larger than linear and generalized linear bandits (Li et al.
2021ap, while neural networks with ReL.U activation do not have a small eluder dimension (their eluder dimension has exponential dependence on the input dimension) (Dong al. 2021 We leave it as future work to consider even more general function classes.
Definition 3.3 (width). Let ()(a) = sup LJF (T(a) - _(a)). For an action set Á C A, we use (A( to denote a (a).
To deal with infinite continuous action sets, we make the following assumption that the reward function class is known in advance by the agent. Notice that for the finite multi-armed bandit case, can choose FF as the set that includes all the eligible functions.
Assumption 3.4 (Known Reward Function Class). The unknown reward function f" belongs an accessible function class F = [Jo A - R E 6).
Bandit models We consider a heteroscedastic variant of the classic stochastic bandit problem with general function classes. At each round t [2] (T' e N), the agent observes decision set D, A which is chosen by the environment. The agent then selects an action a, E Dr and observes reward r together with corresponding variance upper bound of- We assume that rt f" + 6 where f A + R is an underlying real-valued reward function which is unknown to the learner and q is a random noise. We make the following assumption on G,-
Assumption 3.5. For each t, e, satisfies that é, (aiaa, Eist11 a R-sub-Gaussian random variable (R > σi) and Elez/a1a; 61a-1] 0, E[e/ 61:111 S of == of (a1:, 7411)
where or can be either constant random variable dependent on a1a and 71:--1-
Remark 3.6. o, can be seen either given information from the environment, tor of the noise variance at 1-th round based on all past observations, as discussed in the in- formation directed sampling bandit (Kirschner & Krausel 2018). For instance, consider bandit problem with two-point action distribution, where the variance of an action can be es- timated through the estimation of the mean of the action. Similar estimation procedure has been studied in Lattimore et al.) (2015). The details are in Appendix C We can further con- sider the MDP setting. With a confidence set P that includes the true transition dynamic, the conditional variances of the value functions V at state s and action a can be estimated by sup PEP EEres p(s]s, (s) - [Eves
EE'ssp(s')s, p(s'|s, (s') So the variances of value functions can be efficiently estimated for the MDP setting.
For simplicity, let J = Σ of This assumption on is a slightly generalized version of that in Zhou et al. (202T) the sense that the noise is not necessarily bounded by R. The goal of the agent is to minimize the following cumulative regret:
Regret (T) : IE f (a+)).
(3.1)
where the optimal action of round E [7] is defined as at argmax 8 (a).
4

---

Under review as a conference paper at ICLR 2023
Algorithm ML² with OFU principle
1: Input: T.A, F. R, 0.
2: Initialize: Set L < [log2 R/0| and Ci,1 f F, Vi for all I e [4].
3: for 1= do
4: Observes Dr.
5: Choose action = De mi] ma, f(a).
6:
Observe stochastic reward ry and of.
7:
Find le such that 2/++ 2 max(o o;) 2 2
8: Update V f Vr,, U {t} and V f vr for all I E [4])
9: Update C(+1,1 according to V1+1, through regression subroutine (e.g., Algorithm 2)
10:
end for
3.2 MULTI-LEVEL LEARNING FRAMEWORK
Existing approach. To tackle the heteroscedastic bandit problem, for the case where the F the linear function class (i.c., f(a) 0 a) for some 0* Rd), weighted linear regression framework (Kirschner & Krause 2018 Zhou et 200T) has been proposed. Generally speaking, at each round / E [7]. weighted linear regression constructs a confidence set Ce based on the empirical risk minimizarion (ERM) for all previous observed actions a, and rewards as follows:
0. + argmin A| + Exe(t) (a( a.) r.)², C. + {0 E. n. (=-((, (0), S 9.),
agRd
where We is the weight, and 3r, À are some parameters to be specified. w, is selected in the order of the inverse of the variance of round to let the variance of the rescaled reward Vigl' upper bounded by 1. Therefore, after the weighting step, one can regard the heteroscedastic bandits prob- lem homoscedastic bandits problem and apply existing theoretical results to it. To deal with the general function case, a direct attempt is to replace the (0, a) appearing in above construction rules with (a). However, such an approach requires that F close under the linear mapping, which does not hold for general function class F.
Multi-level Learning framework (ML To deal with the nonlinearity issue, we propose a novel framework 2 in Algorithm [ At the core of our design the idea of partitioning the observed data into several levels and 'packing' data with similar variance upper bounds into the same level as shown in line 7-8 of Algorithm [ Note that we use small real number 7 to ensure that the number of levels is bounded. Specifically, for any two data belong to the same level with variaces larger than o, their variance will be at most twice larger than the other. Next in line 9, our framework estimate f according the data points in 1 Since the variances of the data in the same level are nearly the same, we let algorithms that work for homoscedastic bandit problem run the data in the same level. Particularlly, we the Empirical risk minimization (ERM) algorithm as described in Algorithm power of using Algorithm 4 as the regression subroutine. Then in line the agent makes of T, confidence sets simultancously to select an action based on the tentimiim-iittte-ffee cetecc--o-uucertainn (OFU) principle over all L levels. More specifically, the algorithm chooses the action opmimisticly according to each confidence set but inclines to select the confidence set with the most pessimistic evaluation. In the following sections, we will consider several different settings to show the power of ML..
calls subroutine
2 for Sections 4 and 5 In Section (6) we show the
4 WARMUP: NOISE WITH ADDITIONAL SUB-GAUSSIAN ASSUMPTION
We first consider a simplified variant of our problem, where each noise also Lub-Gaussian. Assumption 4.1 SSub-Gaussianity of noise). Et is conditionally g--sub-Gaussian on 01:ts 61:t-1-
Such a sub-Gaussian assumption on noise has been considered by Kirschner & Krause (2018). Next we show the regret upper bound for ML2 with ERM. For simplicity, in the following results, let dimg denote dimg (F, 1/T
Theorem 4.2 (Gap-independent regret bound for bandits with heteroscedastie sub- Suppose Assumption 3.4
noise).
an4 and 4.1 hold and [f) < C for all a e A. For all t E [T]. E [L] and 8 E (0, 1), 0, if we apply Algorithm 2 as subroutine of Algorithm [ (in line 9) and set
5

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Empirical risk minimization (ERM) for partitioned data
Input: Level time and set of data points 11+1d
2: Compute Je+1,1 + argmin EvEVIALA (f(ag) - -ra)²
{ f F.E (f(a.) funlilas) S Bersa
Return C++1.
Br, as the square root of
8(2 -7) 1o0( + 4ta (c+ (22+2 (0 + 1)L/6))
(4.1)
where No = W[ a, ) and L = [log, R/ol (recall the definition of L in Algorithm with probability at least the regret for the first I rounds is bounded follows:
then
+ RTgret(T) < L 2C dimg L + 8/ 2L (o)
+4 L oV 2 2oglog((TTTT + 1))//8/
Corollary 4.3. Let the same conditions in Theorem 4.2 hold. Set a T and dimg' [log(2N../00)TT))
Then with probability at least 8, when T is large enough, the regret for the first T rounds is bounded (T) Ō (Vdim= log(No T-,, 21 Iloo))
Remark 4.4. Our result strictly tighter than the Ō R dimg (F, Ixx regret
achieved by Russo & Van Roy 2013) since J/ = Σ of < RTT. In the worst case, when 01 Or R, our result degrades their result. Our improvement regret is due to the utilization of variance information. When the variance information is provided or can be estimated, our algorithm can achieve better regrets for bandits with general function classes studied in this paper, while existing algorithms cannot.
Remark 4.5, When restricted to linear contextual bandits with dimension d, since log Log.N((,TT,,
(1xo) = (d), dimg = (dd (Russo & Van Roy 2013), our result can be written as (dvJ)) which matches the result of using weighted linear ridge regression for heteroscedastic linear bandit under our assumptions on noise (Kirschner & Krause 2018 Zhou et al. 2021
We also provide a gap-dependent regret bound for general function class setting in section D gen- eralizing the previous gap-dependent regret bound in linear bandits (Abbasi- Yadkori et al. 2011
GENERAL RESULTS FOR BANDITS WITH HETEROSCEDASTIC NOISE
In this section, we consider the original setting introduced Section 3
without Assumption 4.1 In
the following subsections, we will show that Algorithm 2 still works with refined value of B.
5.1 VARIANCE-AWER AWARE CONFIDENCE SET
In this genral setting, directly applying the confidence set used in the previous work (Russo & Van Roy, 2013) gives no improvement since our confidence sets C.,1 do not adopt the variance information. We show in the following theorem that our new designed Cr,, with new confidence radius 3 still ensures that the confidence set is large enough to contain f* with high probability, and exploits the variance information at the same time.
Theorem 5.1 Wariance-depender confidence sets). Suppose that (f) < C for all a e A. For any > 0 and & (0, 1/2), if we set Be, as the square root of
12Cat + 4a/tt + 8/3 (
16- log
where R= R R2/2 4t / Na = N(F, a, lloo): then f E Ct with probability at least 1 - 28 for any fixed I,
Remark 5.2. With small a, we have 3r11 0(22' log Na + Co N.). Compared with
the corresponding previous result Ö(R² log N.) Russo & Van Roy 2013 Ayoub et al. 2020 our confidence set is tighter when C is relatively small compared to R.

---

Under review as a conference paper at ICLR 2023
5.2 REGRET UPPER BOUNDS FOR ML WITH ERM
We derive general results with the variance- confidences sets described in the last subsec- tion. In this part, we write dim (F, T-1) as dimæ for short.
Theorem 5.3 (Gap-independent regret bound for bandits with heteroscedastic noise). Suppose As- sumption holds and (a) I for all a E A. For all E [T) [L] and E (0, 1). a > 0, 8 > 0, if we apply Algorithm as a subroutine of Algorithm [ line 9) and set Sr,1 as the square root of 12d + 4aRt + 8/3 R log (2 + 16- a)) 1 ( where I. = [log2 R/o), (with slight abuse of notation), then with probability least 1 26, the regret for the first T rounds is bounded as follows:
No M(F a. [loo) and R = Ry 2og(log(4"
Regret (T) - VI (2v T + +1) + 1v (log 7 1)av RT
8 + +// dimmellogT T + 1og, + (odimeooo T 1og(2N, T
Corollary 5.4. Assume R = Q(1). Let the same conditions as in Theorem 5.3 hold. Set
T-2,0 = Then with probability at least -, when T large enough, the regret for the first T rounds is bounded as Regret(T) = Ô ( ( log N. + /R log N. Remark 5.5. Compared with the result shown in Corollary
the additional term of order Ō( O(ydini dimg log N₂ RT) is due to larger confidence set by the absence Assumption 4.1
Remark 5.6. When restricted to heteroscedastie linear contextual bandits of dimension d, our regret bound can be written as Ö(d/J + /R With a slightly more restricted assumption on noise, Zhou et al. (2021) achieved result of order O(d'J + RVdT). Our result is appealing when the Sub-Gaussian parameter of noise is much larger than (or the range of the reward function, equivalently). When R is small, our result becomes sub-optimal due to the property of our variance- aware confidence set.
We also provide gap-dependent regret bound in Appendix D
6 TIGHTER BOUNDS FOR GENERALIZED LINEAR BANDITS
Our general result shown in Theorem 5.3 has an additional term of order Ō dimg log RT) which makes the result sub-optimal when R is close the range of the reward function. In this section, we consider a special case, generalized linear bandits with heteroscedastic noise. We show how to get rid of the Ó(vdimg log N. term in the upper bound of the regret, and achieve better result when R relatively small close the bound of the reward function.
6.1 GENERALIZED LINEAR BANDITS
Following Filippi et al. 20100; Jun et al. (017)). we consider the generalized linear function class defined as follows.
Assumption 6.1 (Generalized linear function class). Action set A and θ in Assumption 3.4 are subsets of Rdd There exists a known link function h, such that Va E A and So E Jo h(0T a). Let f fer Assume that ||0*||2 < B, supac.A ||a|| < A.
To make the problem tractable, we need the following assumption on h. Assumption 6.2 (Assumption 1, Jun et al. 2017). h is K-Lipschitz on [-A B, A B] and con- tinuously differentiable (-A B, A B). Furthermore, inf inf M((2) for some K 0.
Next we propose the follow- followw-he-regulliizze--ledd (FTRL) framework (Shalev-Shwartz & Singer 2007 Xiao 2010 Hazan 2019) in Algorithm 3 which is the key component of our final algo- rithm. Note that when dealing with bandit setting, we maintain an independent process executing Algorithm 3 for each variance level instead of feeding all the data points into single FTRL online learner. Here we number the data points with t 1, 2, ... for simplicity with a slight abuse of notation. In Algorithm we will use loss function and regularized function o. is defined as

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Follow The Regularized Leader (FTRL)
Input: F, F.R. R.
2: for t 2 1 do
3: Output 0₂ <- argmingeR ((0) - l(o ag Ts).
4: Observe Tt
5:
end for
(0)) - c- 1011 where is constant which will be specified later in Theorem 6.5 To align with our Assumption 6.1] select the loss function follows, following Jun al. (2017):
Assumption 6.3 (Loss function, Jun et al. 2017). The loss function Algorithm is selected as
follows: ((2,r) -re m(2), (,) ( a,, va), where m(z) satisfies m' m'(z) h(2).
6.2 VARIANCE- DEPNNEEN REGRET FOR FTRL
Before proposing our final algorithm for generalized linear bandits, first propose variance- dependent complexity result for FTRL, since it is already nontrivial and reveals some interesting properties about our setting. We define notion of regrer of online regression. named by reg. as follows. The concept of regret of online regression has been introduced in the previous work (Abbasi-Yadkori et al. 2012: Jun et al. 2017). In detail, it used characterize the complexity for FTRL to learn the generalized linear function.
Definition 6.4. Let reg, = E' ((a 0,, Et ((a) O'a 00000,0 r')).
Our definition of regret for online regression is slightly different that in prior works (Abbasi- Yadkori jtt al. 2012: Jun et al.) 2017). Here 0* is choosen to be the true parameter for the handit model, Abbkoi-Yadkori while 0 often chosen as arg inf oee l, (0) in Abbasi- Yadkori et al. (2012); [un al. (2017) From the perspective of online learning, the algorithms and the corresponding analyses are usually introduced for either the realizable setting where there exists an underlying 0* that incurs zero loss, or the adversarial setting where the bounded label rs in each round can be arbitrarily chosen by the adversary. As result, the previous approaches by Abbasi- Yabkoi-Yadkori Yadkori al.] (2012); Jun et al.
(217)) do not exploit the 'stochastic' property of the labels. Provided that the labels are sequentially generated with additional stochastic noise, our definition is more reasonable and natural. recent work focusing on stochastic online linear regression also discussed the limitation of adversarial setting (Section 2.2, Ouhamma et al. 202I).
Next we propose bound for reg, which adopts the variance information.
Theorem 6.5 (Regret of FTRL). Set d(0) 2> [//n and assume that all the data points fed into the algorithm are of noise variance bounded by diaxe then with probability at least 1 35, Vt 1, the regret of Algrithm for the first i rounds is bounded as follows:
R2 log" (4t2 18) + mixx doog 1+ 2K
tAk?
reg.
4dK²
K
K
(017)) analyzed the online learning regret for the same function class and loss function with our setting. Their result yields reg, in the order of Ö 1² d). Our result improves their result in two aspects. First, R is strictly larger than maax since a R-sub-Gaussian random variable is definitely of variance lower than R², Second, when we consider cases where the bound of reward functions (i.e., KAB) is extremely large compared to R, their result becomes Ō(K² A B'd/s), which has an additional linear dependence on d.
Remark 6.6. Jun et al.
K 1. Our result degrades to Õ(A² + R + _ This is essentially a regret upper bound for stochastic online linear regression with square loss. Recently Ouhamma et al. (021) studied this stochastic setting and managed to get rid of the d3A2 term in classic result for online linear regression considering adversarial set- ting. Ouhamma et al. (202)) derived a high probability regret bound of Ö( d2) after omitting the o(log(7)²) terms (Theorem 3.3, Ouhamma al. 2021 Unlike their result, our result does not suffer from the quadratic dependence on d, and our result depends on of d rather than R²d Therefore, our result is better than that in Ouhamma et al. (202T) when d is large. We also notice that the discussion in Sec. 3.3 in Ouhamma el al. (2021 yields an improved expected regret of or- der ORR² lo T + R2 log T log log )), but the first term dominates the regret in the asymptotic sense, i.e., only when T is very large (T 2 (log 7)
Remark 6.7. Consider a special case where
8

---

Under review as a conference paper at ICLR 2023
Algorithm 4 GLOC with multi-level FTRL learners
1: Initialize: Vo, < AI for all / E [L].
2: while input t, 4:: a,, T2 do
3: Set Or. following Algorithm where Ocd, arginingeR+ x(0) E Eeea {(0 rs)
4: Find t' = max Vtl.
5: Update Ven. + Ve,,, 4 + aea, 21,4, -aT 0r...
6: Compute oe,ie Vil. Σ EeEVenIA Za,4e as)
7: Define Cr.,, + {0 E Rdd 10 0 V. S 3..)
8: Define Ct.1 + 11-1,1 for all I [-)
9: Return Ct,1 + (So E F F E C.,)) for all E [Z]].
10:
end while
6.3 REGRET BOUND OF ALGORITHM WITH GLOOC
With our new technical tool presented in the last subsection, we now show our final algorithm for the generalized linear bandit setting. We propose our algorithm in Algorithm Generally speaking, Algorithm is multi-level version of the generalized linear mniin-toocooffdence-see conversion (GLOC) algorithm proposed bunun al. (2017), equipped with FTRL.
we maintain L FTRL online learners in parallel. Under our framework, single learner only receives data with similar variances of noise. As result, the variance-dependent result shown in Theorem 6.5 to derive a tighter regret bound for generalized linear bandits with heteroscedastic noises.
As shown in Algorithm 4
make of
Theorem 6.8 (Regret bound for generalized linear bandits, informal). Suppose that Assumption 6.1 and 6.2 hold for the known reward function class F. If apply Algorithm 4 as subroutine of Algorthmm (in line and set 3r,1 to
B²
26
22
tAk² 4dK3
1+
R² log K²
2 (4t + 12
dlog
1 +
+ AB²
R²
x²
for all t E [T].EE E [L], where L = [log, R/ - = R/ Vd, then with probability - 48, the regret of Algorithm for the first T rounds is bounded as follows:
K dvJ
K K
Regret (T) =
(K
AB VT
Remark 6.9. In the worst case, i.e. 01 =... oT R, our result degraded Ö(K RdyT +
K2 (3ABB/T//e /x), which still improves the δ (K(KAB+ R)dvT/n) (K(KAB+B)o/T//) result provided by Jun (017).
Remark 6.10. Applying the regret bound in Corollary 5.4 in generalized linear bandits, we obtain a regret bound of [(dJJJ + dv dvRT)/K) for the case where K A and R = 2(1). Our bound here improved the general result when R = o(d).
Remark 6.11. When restricted to the heteroscedastic linear bandits by setting k = 1, our result becomes Ō (R+ A BV +dVJ). which is the same as the Ö (RVdT + dvJ) regret
in Zhou al. 1022 when R ((AB).
7 CONCLUSION AND FUTURE WORK
In this work we study heteroscedastic stochastic bandits problem for a general reward function class. We propose multi-level regression framework ML" to deal with the heteroscedastic noises. Under three different settings with additional assumptions on the noise and the function class, we study the performance of ML and propose corresponding ceaance-depndden regret bounds, which strictly improves previous algorithms for homoscedastie bandit setting. We leave to study the optimal regret bound of heteroscedastic stochastic bandits for general reward function class for future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 22:2312-2320, 2011. 2011.
Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. Online-to-confidenee-stt conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pp. PMLR, 2012.
Alexander C Aitken. Iv-onn least squares and linear combination of observations. Proceedings of the Royal Society of Edinburgh, 55:42-48, 1936.
András Antos, Varun Grover, and Csaba Szepesvari. Active learning in heteroscedastic noise. Theor. Comput, Sci., 411:2712-2728, 2010.
John-Alexander M Assael, Ziyu Wang, Bobak Shahriari, and Nando de Freitas. Heteroscedastic treed bayesian optimisation. arXiv preprint arXiv:/410.7172 2014.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Peter L Bartlett, Wouter M Koolen, Alan Malek, Eiji Takimoto, and Manfred K Warmuth. Minimax fixed-design linear regression. In Conference on Learning Theory, pp. 226-239. PMLR, 2015.
Nicolo Cesa-Biame Bianchi, Philip M Long, and Manfred K Warmuth. Worst-case quadratic loss bounds for prediction using linear functions and gradient descent. IEEE Transactions on Neural Net- works, 7(3):004-619, 1996.
Kamalika Chaudhuri, Prateek Jain, and Nagarajan Natarajan. Active heteroscedastic regression. In International Conference on Machine Learning, 2017.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208 214. JMLR Workshop and Conference Proceedings, 2011.
Wesley Cowan, Junya Honda, and Michael N Katehakis. Normal bandits of unknown means and variances: Asymptotic optimality, finite horizon regret bounds, and solution an open problem. arXiv preprint arXiv: 1504.05823 2015.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 2008.
Kefan Dong, Jiaqi Yang. and Tengyu Ma. Provable model-based nonlinear bandit and reinforce- ment learning: Shelve optimism, embrace virtual curvature. Advances in Neural Information Processing Systems, 34:26168-26188 2021.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In NIPS, volume 23, pp. 586-594, 2010.
David A Freedman. On tail probabilities for martingales. the Annals of Probubility, pp. 100-118. 1975.
Paul W Goldberg, Christopher KI Williams, and Christopher M Bishop. Regression with input- dependent noise: A gaussian process treatment. Advances in neural information processing sys- tems, 10:493 1997.
Elad Hazan. Introduction to online convex optimization. arXiv preprint arXiv:1009.02277, 2019.
David Hong, Laura Balzano, and Jeffrey A Fessler. Towards a theoretical analysis of pea for het- croscedastic data. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 496-503. IEEE, 2016.
10

---

Under review as a conference paper at ICLR 2023
David Hong. Jeffrey A Fessler, and Laura Balzano. Optimally weighted pea for high- nigh-dimensional heteroscedastic data, arXiv preprint arXiv:1810.12862 2018.
Kwang-Sung Jun, Aniruddaa Bhargava, Robert Nowak, and Rebecca Willett. Scalable generalized linear bandits: online computation and hashing. In Proceedings of the 31st International Confer- ence on Neural Information Processing Systems, pp. 98-108, 2017.
Kristian Kersting, Christian Plagemann, Patrick Pfaff, and Wolfram Burgard. Most likely het- eroscedastic gaussian process regression. In Proceedings of the 24th international conference on Machine learning, pp. 393-400, 2007.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with het- eroscedastic noise. In Conference On Learning Theory, pp. 358-384. PMLR, 2018.
Jyrki Kivinen and Manfred K Warmuth. Exponentiated gradient versus gradient descent for linear predictors. information and computation, 132(1):1-63 1997.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In International Confer- ence on Artificial Intelligence and Statistics, pp. 2066-2076. PMLR, 2020.
Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Linear multi-resource allocation with semi- bandit feedback. Advances Neural Information Processing Systems, 28, 2015.
Gene Li, Pritish Kamath, Dylan Foster, and Nathan Srebro. Eluder dimension and generalized rank. arXiv preprini arXiv: 104.09000 2021a.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contex- tual bandits. In International Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
Yingkai Li, Yining Wang. and Yuan Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pp. 2173-2174. PMLR, 2019.
Yingkai Li, Yining Wang, Xi Chen, and Yuan Zhou. Tight regret bounds for infinite-armed linear contextual bandits. In International Conference Artificial Intelligence and Statistics, pp. 370- 378. PMLR, 2021b.
Nicholas Littlstonee Philip M Long, and Manfred K Warmuth. On-line learning of linear functions. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pp. 465-475, 1991.
Alan Malek and Peter L Bartlett. Horizon-independent minimax linear regression. Advances in Neural Information Processing Systems, 31:5259-5268. 2018.
James McInerney, Benjamin Lacker, Samantha Hansen, Karl Higley, Hugues Bouchard, Alois Gru- son, and Rishabh Mehrotra. Explore, exploit, and explain: personalizing explainable recommen- dations with bandits. Proceedings of the 12th ACM Conference on Recommender Systems, 2018. 88
Reda Ouhamma, Odalric-Ambryn Maillard, Vianney Perchet, al. Stochastic online linear regres- sion: the forward algorithm to replace ridge. Advances in Neural Information Processing Systems, 34, 2021.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, pp. 2256-2264. Citeseer, 2013.
Shai Shalev-Shwarte and Yoram Singer. A primal-dual perspective of online learning algorithms. Machine Learning, -5-2) 2007.
Lin Xiao. Dual averaging methods for regularized stochasicc learning and online optimization. 2010.

---

Under review as a conference paper at ICLR 2023
GLOC-ONS
320
ML2
230
220
regret
150-
130
50-
1002
2000
number of rounds
Figure 1: Cumulative regret comparison between ML and GLOC on synthetic data.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Variance-aware confidence set: Variance- dependent bound for linear bandits and horizon-free bound for linear mixture mdp. arXiv preprini arXiv:2101.12745. 2021.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference Learning Theory, pp. 4532 4576. PMLR, 2021.
A EXPERIMENTS
In this section, we conduct some experiments of the proposed ML2+FTRL algorithm for generalized linear bandits. We compare our results with GLOC proposed by Jun et al. (201)) For each trial, the dimension of 0* is set to 20, and 0 is sampled uniformly from round, the action set of cardinality 100, where each action is uniformly sampled from [-1, 1] and normalized to have unit & norm. The link function is set to be the sigmoid function h(2) = T4e-r. The variance upper bound at each round is uniformly sampled from [0, 0.75). To simulate the variance bounded condition considered in this paper, reward is not sampled from Bernoulli distribution. Instead, at each round I, we sample random variable e/ from Poisson distribution, i.e.. é (ofs(af) and e/ min Rt where R is e E[e]]. With this construction, it is not hard to see that satisfies Assumption 3.5 with Lub-Gaussian parameter R. We plot the cumulative regret of ML2 and GLOC Figure We can see that by adapting the multi-level and variance-aware scheme, our MI. algorithm outperforms the previous GLOC algorithm by a large margin.
1/d, /1/d/a. At each
10. Our zero-mean noise e, computed by
B PROOF SKECTCH OF THEOREM 5.3
Proof Sketch. We prove the result by showing the validity of the confidence sets and bounding the sum of single-step regret incurred by each variance level. Step Construction of confidence sets We first show that the construction of Cr, is big enough to contain f with high probability. Recall the definition of Ct, as follows
C..1 + {SEA) Σ [fa.)] (
Rulaa.) Br,
(B.1)
SEW..
Thus, only suffices to show that fr satisfies the inequality in B. According to our ERM sub- routine, we have
Σ (fan(a))- +2 Σ eall" ((..).)
SEV
BEV..
Σ (ha((as-Tr))
Σ
(f*(as) - -ra)² 50. 0.
AEV
SEW.,
12

---

Under review as a conference paper at ICLR 2023
where the inequality holds since fa, is the function which minimizes the cumulative squared loss (f++1,(a,) at level I, i.c., E.eo,, (f(az) r.) Therefore, to bound Ln - (a.))² suffices to bound the absolute value of v.. -a,) Since f suffers from the mea- -
surability issue, we use the concentration of self-normalized process with an a-cover discretization argument bound this term, which can finally show that f satisfies (B.I). Step 2: Regret decom- position With the confidence sets corresponding to different variance levels constructed in Step 1, we decompose the final regret in the following way:
Regret (T) S Σ Σ
(((a)))((a)))
[E[L] LE
s Σ
Σ
max Mas) - 5 (ar)
SEC,,
1E[T] LEVT+1.
$ Σ
Σ
(a.)
(B.2)
[E[L] 1EWT+L
where the second inequality holds due to the optimism principle for arm selection, the last one holds due to the definition of width wc, we,, (a) == maxffc,, f(a) - min f(a) and the fact that f E C.., from Step 1. Step 3: Bounding the sum of widths From Step 2, the last step to bound the regret is to bound the summation of the width wc.,, (at). According to the definition of eluder dimension, we can further bound (a)) in terms of the eluder dimension of F and the value of (See Lemma E.3 E for more details). According to the decomposition, we can first bound the regret at
each level by a O(2' / term (omitting the dependencies on d, R and σ) and then naturally
bound the total regret by Lemma E.3 and the Cauchy Schwartz inequality. The full proof is given in Section F
C EXAMPLE: VARIANCE-DEPENDENT REGRET BOUNDS FOR BERNOULLI BANDITS
In this section, we consider the following specific Bernoulli multi-armed bandits with general func- tion approximation, where the observed reward r, incurred by action ag is subject to the following Bernoulli distribution:
r f== + + (1)f
with probability (a,) f 1/2. (C.1) otherwise
It is easy to see that the noise e, satisfies R = (af < 1/6 and of = As discussed in Remark 3.6, we can use estimators of variance Algorithm D instead of the true variance at each round.
The following corollary is an illustration on how to apply Algorithm when variance information is not accessible but can be estimated through past observation.
Corollary C.1. Let the same conditions as in Theorem 5.3 hold. Set a = T 1. At each round, set of (a.) to min(1, + 2/5² Wc..,, (ut)) where (²(()) = 1/fr)((a)) 1/(1 Fre. (a.)). Then with probability at least 1 - ō, when T is large enough, the regret of Algo- rithm for the first T rounds is bounded Regret(T) Öl diimm log No, Σt= Var[r.] + E --3 dimg log Na + 1/2 /dimg log N.T).
Proof. We suppose the event described in Theorem 5.1 holds and the conditions of Theorem 5.3 hold without the given variance at each round.
At each round 6, we can upper bound the variance of := (at) ( by making use of C., and
frr returned by Algorithm 2 Specifically, estimate Var(r.] of (af 1/(1- (a,)))
as 1/fr. (a.) - 1/(1 - Feu. (a:)) and bound the gap between 03 and Var[rx]:
(0x()x) Var[r=]l < [1/fe, (ax) - (a)" + fen(ar))
1/(1- (a)))))
13

---

Under review as a conference paper at ICLR 2023
$ 2 (as) (ac)
S 2/ wor,, (ax)-
(C.2)
where the first inequality follows from the distribution of reward, and the last inequality holds ac- cording to Theorem 5.1
Therefore, is valid to replace of by ( 2/5² we.., (at)3 in Algorithm
Similar to the proof of Theorem 5.3 we have
J
min + 2/5 wc..,, (0t)}
min(1, Var[ri] + +4/5² we,.,, (ar)
Var[re] 4/62. [E(L] NEWT+I
(a,.(as)
Var[ny] 4//22. L (1/T+ 43r VdT
where the first equality follows from the definition of J, the first inequality follows from C.2 the last inequality holds due to Lemma E.2
Hence of order Ö
Var[r:] 1/E3 v Vll N.T).
According to Theorem 5.3 the regret bound of Algorithm | for this Bernoulli bandit problem is of order
3/4 ō(y dimg log No I Var[n]] + 1/5 -dim g (log No) 3/4 + v=- dim log NaT)
s ( log N₂ ET Var[r.] + g-3 ding log Na + - / log NaT).
This completes the proof.
D GAP-DEPENDENT REGRET BOUNDS
In this section, we provide gap-dependent regret bounds for Algorithm I with various subroutines.
Denote A, as the smallest gap between the reward of an optimal action and the reward of a sub- optimal action:
A min (a) aEDr,agD;
(D.1)
where Dj argmax (a). Let be the smallest gap in all the rounds: A == minsery A..
Theorem D.1 (Gap-dependent regret bound for bandits with heteroscedastic sub-Gaussian noise).
Suppose Assumption 3.4 and 4.1 and [a)) S for all a E A. Let m = maX4e/z1 de and suppose max σ. If we apply Algorithm 2 as subroutine of Algorithm [ (in line 9) and set 3,, as the same value in Theorem 4.2 then with probability at least
the regret of Algorithm for
the first T rounds is bounded as follows:
A (4dimg C² + +1/T) + 16 LTaC
Regret (T'r 1
dimg T + 1)
A
L 128 A max 1og(2N../6)) dimg + 1) + 32
L
Taomax log L/ dimg T + 1).
Corollary D.2. Let the same conditions as in Theorem D.I hold. Set = 7-2 Then with proba- bility at least 8, when T' is large enough, the regret for the first T rounds is bounded as follows:
Regret (T) = Ō
dimg log (og( l(=)))
A
14

---

Under review as a conference paper at ICLR 2023
Remark D.3. Corollary D.2 immediately suggests an Ö(R² dimg log(N /o///a)))/ gap- dependent regret by the fact maxx = O()) which provides a novel instance-depene destance-dependent bound for the original problem considered by Russo & Van Roy (2013). To our knowledge, this is the first result of its kind for the general bandit model.
Remark D.4. When restricted linear contextual bandits with dimension d. our result reduces to Ol d² //), which matches the previous result derived in Abbasi- Yadkori et al. 2011)
Theorem D.5 (Gap-dependent regret bound for bandits with heteroscedastic noise, informal). Sup- pose Assumption 3.4 holds and (a)l I 1 for all a E .A. Let maax e (suppose dimg (f,ng(F1/7T) If we apply Algorithm 2 as a subroutine Algorithm [ (in
T mmax > σ) and
line 9) and set 3t.1 the same value in Theorem [.3] then with probability at least 1 26, the regret
of Algorithm] [ for the first 7 rounds is bounded as follows:
R O maa d log Na + d log No.
(T) Ō
A
A
if ' is large enough and we set a T
Remark D.6. Similar to Remark 5.5 compared with the regret in Corollary D.2. the regret in The-
orem D.5 has an additional term that depends on R.
E PROOFS FROM SECTION 4
Lemma E.1 (Proposition 3, Russo & Van Roy 2013). If, 2 0lt E N) is nondecreasing sequence
and F, = FEF: E!=1 (fi(a.) - s(ax)) 1 3? then
[187 (wr)(ar) > 2)5
+1
dime(F,e)
2
for all T E N and >> 0.
Lemma E.2 (Lemma 2. Russo & Van Roy 2013). If (B, 2 0lt E N) is nondecreasing sequence
and F = { FEF: E:=l (fila.) - f(.s)) s B? then
Σ
WF. (ax)
1 7 wF(A) (F 43T (iie//,TTFFF)
1=1
for all T e N.
Instead of using the previous approach that bounds the sum widths, we take another approach to bound the sum of squared widths, which further provide novel gap-dependent result later.
Lemma E.3 (Bounding the sum of the square of widths). If (8, 2 0/l E N) is a nondecreasing
sequence and F, = { { F: It=1 (fila)) - -((a)) s 3 then
Σ w (a.) dim (F,nm(FF///T))3lL + 1 4 din (im T +
for all T' E N.
Proof. Following a similar approach as Russo & Van Roy 2013 we reorder the set {wi, (at)
to fuz hee[T) such that w1 2 W2 2 wy.
Let T' = max (t E [T]. we 2 }. By Lemma E.1
4
t < (w: 5)
+1)
dimg(F,
(E.1)
15

---

Under review as a conference paper at ICLR 2023
for any 8 E (0.e). Taking 5 -> O, we have
4 dim ø (F, wt) dim (F, w.)
w
(E.2)
Hence,
T
T
(4))
Σ
i
(E.3)
T Σ
< ddinn(F,1/T)) +1/7+
(F
4.8 dim (F,
S (f +1/++
t t- -im (.mm(F,114 (F,1/T)
(F
s dd + 1/T 4 dim (F,, 1/T) + 1),
where the first inequality holds due Σirro 2 S 1/T under our definition of T", the second inequality follows from (E.2). the third inequality is derived by taking the integral.
With Assumption 4.1 we can directly apply the previous result confidence by replacing the Sob-Gaussiantty Y parameter by 2 σ. Previous result by Russo & Van Roy (2013) achieved a confidence set of radius Ō O7 log N. + at + n))) Ayoub et al. (2020) later provides result of the same order with improvement in terms of smaller constants.
Lemma E.4 (Theorem Ayoub al. 2020). Suppose that [f*((a) s CC for all E A. For any >>>>>>>> 0, if we set
1/2
Br, = 1(2 . log((N. + 41a(C + (22421 7) 1lggo(4((++1)///))
(E.4)
then with probability at least 1 - 8, for all t 2 1,1E [L, f E C21-
Theorem E.5 (Restatement of Theorem 4.2 Suppose Assumptions 3.4 and 4.1 hold and (a) <
C' for all E A. For all E [ [L] and 6 (0, 1), a 0, > 0, we apply Algorithm as subroutine of Algorithm (in line 9) and set 3r, as the square root of
8(2 .)) log + 4lar(C + (2t+1 log(AU( 1)L/
where N,, = WF a, ) and L, = logg R/oo (recall the definition of L in Algorithm then with probability at least 6, the regret for the first 7 rounds is bounded follows:
Regrot(T) < L + 2C dim L + 8 21 dim + + p 1/2
4 dimg a C + 2R (
Proof. For simplicity, let dim
With probability at least 1 - 8, we have
Regret(()) Σ
(P(0)) (a.)))
(E.5)
Σ (aa())) - (a
L) teWr11
Σ Σ
max f(as) 8 (ai)
fEC..
[E(L] JEWT+1.
16

---

Under review as a conference paper at ICLR 2023
2 Σ TE(1)
1+20 + 4 d
$ L + 2CdL +2
Fr,d Mr+1.b [E(2.]
(E.6)
where the first equality holds by the definition in (3.1 the second equality holds since Pr+1, forms a partition of [T]. the first incquality holds due to Lemma E..4 the second inequality follows from Lemma E.3 the third inequality obtained by applying Cauchy-Schwand inequality.
Then we continue to bound Lu-
1o
L
B7.d
[E(L] LEVI+IA
Ld
8(2/+1 7)² 1o8((2N.1/
[E(T. 1EWT+11
VLd
Σ
Σ
4Ta(C + (1
[E[L] LEW++1
S Vdd
Σ
Σ
8(21+1 + 28 2R/log( + 1)L
[E[L] LEVT+LI
VLd
32(0) + 240p:////000/0///////////////111 +1)) 1)L//))
32Ld(J + TT) log 2v Ldd
+
(E.7)
where the first inequality follows from the definition of 3r.,, the third inequality holds due to the fact that
vI E [L], VT+LJ 2' = 2'7 < 2 max = 44 1(7 + af),
fourth inequality follows from the definition of J.
Substituting
E.7
into
E.6
we obtain
Regret S 2CdL + 8/2Ld(J
+ +T Lo9
+ 4v Ld C 2R log (T + 1)8/8
which completes the proof.
Theorem E.6 (Restatement of Theorem D.I. Suppose Assumptions 3.4 and 4.1 hold and (a) <
C for all (in line 9) and set Br, as the same value in Theorem 4.2 then with probability at least 1 5, the regret of Algorithm [ for the first T rounds bounded as Tollows:
Let maxx = max Øt. we apply Algorithm as subroutine of Algorithm
L
LTaC A
Regret(T) < (4dimg C2 11/T) + 16
dimg +
A
L
+ 128
22
dimm man log(2N. (lo T
A
T
+ 32
Tao max (og(872L/8) dimg T 1).
A
Proof. For simplicity, let dim (iim(FF,1/2
17

---

Under review as a conference paper at ICLR 2023
Suppose the event described in Lemma E.4 holds. With probability at least 1 - 6,
(egret(T)
T
Σ (((a))
Σ
Σ (f"(a))- - -
Σ
E (f*(a)) (a(a))) /A
LE|L]
tEV++1l
Σ
Σ
max f(a)) M(a)) /A
SEC.
LE|L]
LEVT+
Σ
w (D,)
[E[L]
1EV7+11
Σ
(AdC² + 1/T + dlogg T' + 1))
LE[4]
(4dC² + 1/T)
A
L d'llog 1) (320 max log(2N + 4T' 22CCC+/V22 2n log(AT(T + A
where the first equality follows from the definition in (3.1). the second equality holds by the fact that 11 E [L] forms partition of [T]. the first inequality holds due to the definition of A in
Subsection 3.1 the second inequality follows from Lemma E.4] the fourth inequality holds due to
Lemma E.3 and the last inequality derived by directly substituting the value of ßT.
F PROOFS FROM SECTION 5
Lemma F.1 (Freedman 1975). Let M, o > 0 be fixed constants. Let {x;}]=> be stochastic process, {G.), be filtration so that for all in], x; is G-measurable, while most surely [[x,(/;-1] O, |ay] S M and
Σ B(x u..
Then, for any > O, with probability 1 5, for all i [m].
z4 S v 20 logo2(2t)/8) + 2/3 M (2g((2///))
Lemma F22 Suppose a, b 2 0.
& + b. v. then x² 2b² + 2a.
Proof. By solving the root of quadratic polynomial ((x) == x² - b-x b-x-aa a, obtain max(21, x2}
(b + vb² + 42) Hence, we have S (b+ v + 4a)/22 provided that q(x) S Then we further have
2² < 1 b+
(b+ 12 12 + 4a
< 2 (b2 + +0 + 4a) < 26 + 2a.
(FII)
4
Theorem E.3 (Restatement of Theorem 5.1 Suppose that (f* S C for all a A. For any 0 and 8 E (0, 1/2), if we set Br,1 the square root of
a2Cat + 4oRt +
CRlog(2N,
2/0) 16. (2) 12 /6)
3
18

---

Under review as a conference paper at ICLR 2023
where
R= = 2og/log(4tt (5)
then f E Cr.t for with probability least 1 28 for any fixed
Proof.
By simple calculation, for all F have
Σ (f(a.) (a.))) +2 Σ
(a.) - f(a,)l
Σ f(a))
Σ
(r, f (as)).
SEW
SEV,
I(f)
(F.2)
By sub- Sub-Gaussianity of et we have
T 1, max 15a51
leal
P(lesl 2 RV2log((42/8)) S Σ
8/(28²) S
+21
221
(F33
For simplicity, let event Esus = {vt 1, maxigesulll Ry 2///log((4)) 2
Let ((a)) C FF be an a-cover of F in lloo. From the definition of Fe,1, we have
Σ (fer(a.) - f*(aa)) +2 Σ - ((,(a)) I(fe.) s 0. SEVL
(F:4)
SEVLE
Let g grg Ilfe,1 x0
We then bound the gap [gg) I(f..) under event ExubGs
T(g) -(f())
Σ (g(as) (a,))) (fra(aa))
- (a,)) +2 Σ ((fe,(a))) -((a))
SEV.11
seVe
Σ (g(as) - Pe. + - - (ax)) + 2 Σ aRy 2 2log(11 (1))(4)2))) s.W..1
+ Pe,((a))
sE We,1
< 4Cat + 2all 2 log(412/0)t.
(F.5)
Fix an ʃ E F. Applying Freedman's inequality (Lemma FT with probability at least 1 - 5, we have
Σ SEW.1
6 I(Esns))((((a)) - f(aw)) 2 -2/3R 2 log(( 4t (
2 12
Σ (f(a.) - (a.)) logg(1/)))))))
SEV.i
(F.6)
for all
Using union bound on all the f e ((a) and ESuba, we further obtain that
Σ (as) - f(aa)}
SEV.r
2
R 2log((47/0)Cloo/22...
1212++10)2og(22N.12)) Σ (f(a.) (a.)))
3
SEVi
(F.7
for all f E ((a) with probability at least 25.
19

---

Under review as a conference paper at ICLR 2023
Substituting E.7
into the definition of I(f), we have that for g, it holds for probability least 1-28
that
4Cat + 2aR log 4f////// I(g)
(F.8)
4
2
Ry log( (o/go(11////C/o(222N00
(F.9)
3
8 (2 1og(2N21))))))
E
(g(as) (a.))²
(F.10)
SEV.N
(g(a.) - fa
(F.11)
Me,
where the first inequality is obtained by substituting (1.5) and F4
into the inequality below
[(a) - [(g) T(f,,) + ((e.))
the second inequality follows from the definition of (ff) and F.7
Using Lemma F.2 we can deduce that
Σ (g(as) ('(a))) < 8Cat + 4a RC 1
16 1og(2N22
Then we can complete the proof by bounding the gap between (o(as) (aa))) and
Exer,, Enev,, f²(a)))
Σ (Fellas) - f (a(a))
Σ - (a.))
SE
SEV
Σ (glas) (a.))²
Σ (Feglas) - (ax))
SEV
SEV.N
< 12Cat + 4aR 2 log 41 18)t
RC /CV2 22gg 1ogg(122/// /8) log(2N,
3
log + 16 log log
Theorem F.4 (Restatement of Theorem 5.3 Suppose Assumption 3.4 holds and (a) < for
all E A. For all T E [L] and E 1) 0, J > 0. if we apply Algorithm subroutine of Algorithm (in line 9) and set Br, as the square root of
8
12al + 4aRu +
R Rlo((2N,(L1/))) + 16 (2++1 1og(22,11111)
3
where N. = WN[F |. lloo) and R R log logg (.8) (with slight abuse of notation), then with probability at least 26, the regret for the first T rounds is bounded as follows:
8
Regret(T) S 4v ddiimgloog] 1)av 3+ RT + 2/
dime T + 1)Rlog((N (2
+ 16 1o TT TT² + VI (2
dim T +1)
Proof. For simplicity, let = dim (F,1))
Based on Theorem 5.1 for any fixed I, we have f Ct2, with probability 1-26/ Applying union bound on all E [L], we have f E Ca, for all t, with probability at least 1 - 26.
Then we further obtain, with probability least 28,
Regret(T) = Σ (faat))((a)))
20

---

Under review as a conference paper at ICLR 2023
Σ
E
TE[L]JEWT+H)
Σ
E
max f(ar) -{(aa)
fECIa
[E[L] tEWT+1.
Σ
Σ
max f(ai) f((ai) (EC..
1
V
[E[L]
1EVTI1.
$ VL.
" (D,)
[E(L
S VL.
V 1
4d + 1/T 4 d(og T 4 + 1))
[EL)
where the first equality follows from the definition in [3.]p the second equality holds by the fact that 1T+ [L]) forms a partition of [T', the second inequality follows from Cauchy-Schwarz
inequality and Definition in (3.3), the third inequality follows from Lemma E.3
Following the definition of Br, we further calculate
Regret(T) S VT. (2V0T+1) + VL.
Σ
Σ
6122Ho8log(22,
1)
(E(L)eEVTOI
+ 22v Ld(log I' + 1)T 12aT + 4aRT + 3 (22
< VI (2V + + + 1)av RT
8 [d(llgg T 1
+
+2
3
+ v
Ldd(lgg T' 1) 1
256(a + x*)
< VL dT +1) + 4v Lo + 1)av 3 RT
8 3
+ 2 Ld(log T 1)
+ 16 Ld(log T 1) 1/
where the first inequality holds by the definition of 3r,1 and the fact that V < Va + vb for a, >> O, the second inequality follows from the definition of lt the third inequality follows from the definition J.
Theorem F.5 (Formal version of Theorem D.5 Suppose Assumption 3.4 holds and (a) <
for all E A. Let Tmax max ae and d dimm(F,1/7) 1/T). If we apply Algorithm as a subroutine of Algorithm T (in line 9) and set 3r, as the same value in Theorem 5.3 then with probability least 1 28, the regret of Algorithm for the first T rounds bounded follows:
L (4d (4d 1/T)
LaT
32 L
Regret(T) (T)
d(logT T + 1) + 4R) + Rd(log T + 1) log.N 3 A
A
L 2 + 256
A max d(log T + 1) log(2N,,
Proof. For simplicity, let d = dim
Basically following the previous approach in Theorem D.I with probability 1 26, we have
T
Regret(T) = Σ -(())-((aa))
21

---

Under review as a conference paper at ICLR 2023
Σ
E
(a())))((uu)))
|E TEV++
Σ E
tEW+TH
Σ Σ
max f(ar) ((a))) /
FEC,
[E[L] 1EVT+I
(D,) (D,)
[. 1ENT111
44 1/T + 457 d T ++1 1))
[E[L]
L
(4d + 1/T)
+ 4 L d(log T + +1) [2aT + 4aRT + 3
22, + 640 max 2 L/6)
A
+ 1/T) + LaT
32 L
A d(log T + 1) 4R) + Rd(log 1)
3 A
L max d(log 1) log(oN,, (og(22,,7T./6),
+ 256
where the first equality holds by the definition in (3.1). the second equality holds by the fact that MT41. (I [L]) forms partition of [7], the first inequality follows from the definition of A in D.II, the third inequality follows from Definition (3.3). the fourth inequality holds by Lemma the fifth inequality follows from the definition of ST.--
G PROOFS FROM SECTION 6
Lemma G.1. Let reg, == E.= ((aT0rr)) -E ((aT0r,r)) probability least 1 8,
Following Algorithm
with
8R2 log log(4t²/0)
Σ (o. - reg, +
(G.1)
x²
for all / 1. We denote the corresponding event by E1.
Proof.
(aTT0r)) Σ O', s=1
reg,
8=1
8 (")
(aa TT, 0", .r.)a. -0.-0")
(a 0, - a, 02
2
K c.a (0, 0*)
マタ aa 0, - a 2
where the first equality follows from Definition 6.4 the second equality holds by Taylor series
expansion and & is point between a. and a. 0², the first inequality follows from Assumption
6.2 and Assumption 6.3
Further obtain
T (0, -0))² < Σ a (0, -0)) + reg.
s=1
22

---

Under review as a conference paper at ICLR 2023
2 R 2 2 a [
2
(0. 02)) log(2/0)
-re:
with probability 1 - 5, where the second inequality follows from the sub-Gaussianity of Eg.
Applying Lemma
we obtain that with probability at least 5,
Σ a 0²))² v reg,
8 nz
n² log(2/0).
Applying union bound on all t 2 1, we have with probability at least 6,
8 R2 log (t2 (8)
(a (0. 01)
reg: + x
(G.2)
for all 2 1.
Lemma G.2 (Lemma 11, Abbasi- Yadkori et al. 2011). For any X > 0 and sequence {xL ) C R
for & E (0, .., 1, ,T), define Z. = AI + Σx xi=1 x,x,". Then, provided that ||xe|12 I M for all
t E [T], we have
dd TM2
Σ min (1, | 1,,11
log
dA
Lemma G.3. For any 0 and sequence {x+]== C Rd for E {0,1, 10,1, ,T. define Z,
AI Ei= xxx Then, provided that ||x||22 I M for all E [T], we have
T
dd + TM2
X
1
S 2d
dA
Proof. Applying matrix inversion lemma,
2.-
Z
X2
T
Z x,X, 2
X
+ x Z
||X|
113
1+
||x: 2
min 1, ||xe|| 1|2
dx + TM2
2d
dA where the second equality follows from matrix inversion lemma, the second inequality holds by
Lemma G.2 Lemma G.4. Let
R2 Σ,
a; a
K
T max
max Ts.
f21
Suppose R. is upper bound of maxigose lcol- simultaneously for all t 2 that
Then with probability at least 5, it holds
Tmax Ri
tAk²
2 (omax + n?)) log(21//0) 18).
2
|
dlog
1+
4dK2 log(2(2/0))
+
K
3x
23

---

Under review as a conference paper at ICLR 2023
Proof. To bound the sum of variance of each term, caulculate
Var [
B|c31l ||a
Ble al x2
E
# 4K
B|c
Ri ||a I1
R2
LAn? 4dk²
d log
1+
max 2K
where the second inequality follows from the definition of Er, the third inequality holds by Lemma
G.2
Also note that
max -((e)) ||a |a=l|s;- S 1
5(oo R
Ki
since Eg = 4²
I+ ka, a.
Then apply Freedman's 's inequality, which gives for arbitrary 2 1,
Σ ( E(23) |a_ Ea.- S
Tmax Rs
dlog (1+ 4dK²
LAk²
log(1/6) + 2/3 (o + +T.) log(1 log(1/5)
1 (22
K
with probability at least 8.
Applying a union bound on all 2 I, we have with probability at least 1 6,
muax Rr
tAk?
2 (o" (o + Ri log (og(2t")) 18)
Σ C
E E((3))
| x-
S
d'log
1+
log(2t2
(2t2)//8) +
K
4dK²
3x
(G.3)
since
2 < 8.
Theorem G.5 (Restatement of Theorem 6.5). If we set s(0) 2*
1011 and assume that all the data points fed into the algorithm are of noise variance bounded by o then with probability at least 1 36, vt 2 1, the regret of Algrithm 3 for the first t rounds is bounded as follows:
B2
9
R² log (4t. (412/5) max dlog 1
tAk?
reg,
K
4dK²
Proof. For simplicity, let (,) E1=1
s=1 ((0 T (g r.) + +(0) and loss; (0) (, ((0).
Suppose event ε,, event Exana == 11 2 1, maxi |ea| < R 2 log( log(4(2/2)) (4(2/)) and the event de- scribed in Lemma G.4 (denoted by E2) simultaneously hold in the following proof.
By wub-uuussiiae Gaussianity of e, we have
3t 1, max |eal (22l0g(()/8) <
P(les 2 R 2 llg
< Σ 8/(2s²) < 8.
IS
(G.4)
Hence, PPESSb))) 2 8. Applying Lemma P(E O E (3 2 35 by union bound.
G.1 and Lemma
G.4
have that
From the update rule of Algorithm we calculate
Σ ((a 0., TT))
Σ ((a) 0r m.)
24

---

Under review as a conference paper at ICLR 2023
(0.5 1000s=1 [(a]
r.]] (0s+)+1(0++1) ((a loss (00)
(0.) - - x(0)) + +(0) (++1(0++1) (0")
<
max EEG
(0))
+
Σ 8=1
- Loti -o,) (0++1))
(G.5)
where the first equality follows from the definition of loss, the second equality holds by the definition of L. the first inequality holds since (0+1() minøeR* (0).
Then we continue to bound I1.
11 =
(0.) - (0+1())+1)
0L.+1
(0.). 0,11 0, -0.) - - -0,) -O,) (0) 10:41-00.. -0,) 00
(h((,, 0z) - r3) (a., Ox+1 - -.)) - -(0++1 - -O.) H (0)
(h(a, 0.) rrr)21 11) (05)
(h(a T 0.) -h(a, (0)]0))) 1 (111 (05)
+
2
|a H (0L)
2 s=1
2 s=1
a 1 [a] 0, 000'²²
a. (1)) (0))
(G.6)
H (0))
2
where the second equality holds due to Taylor Expansion, (Let H be the Hessian matrix and 0C, O' (R,)), the third equality follows from the fact that 00 (0.) 0 and 0C 50 (0.) + -0-
0E(0 a..r.) (0.)the first inequality obtained by solving the quadratic function with respect to 0 0,, the second inequality follows from (a+ (a+bb) b)2 < 2a² + 20
From the definition of H. we calculate
H
H (0)
VaL+tl
(G.7)
00
à
(h(a, 0) (r)) -a, Voń
(G.8)
00
K2
a, a. =...
(G.9)
k
From Lemma G.
4 reg, +
8R²
log log(412 (4t2/8)
K
x²
4K2
1
2R
reg, K22
log 41 18).
(G.10)
kk
We bound Ig by decomposing it into its expected value and a zero-mean term.
13 <
2 a
+
(e) E(e3)) a H (
H
(0))
25

---

Under review as a conference paper at ICLR 2023
0
a I|
+ Σ
(ce - B[e=]) || 1|
==1
< 2 max doog
1
LAx²
+ Σ (e -E(ea) ||a 1
(G.11)
4dh2
where the second inequality follows from G.9). the third inequality holds by Lemma G.3
Substituting (G.11) and (G.10) into (..6), we have
R²
log(4t² /6) + max dlog 1+
LAn²
1
1 - 2 reg, +
+
1.
(G.12)
k
4dkk2
2
Applying Lemma G.4 to bound Ia we calculate
mmaxR Rs
tAk²
2
I4 S
dlog
1
1og(21200)
(maxx + Rij log(21?/0)
K
4d
3x
mmax R K
L.k2
1
2d
1+ 4dK2
log(4t²/ + 2/3 (omuxx +112 +21121og(A1" (0)4//0)) logg(tt) /6)
k
Fmax R K
LAk2
log(41") (8) + 2Rt
2d
1
log 2 (41215),
(G.13)
4dK²
k
where the second inequality holds due to event Esuda, the third inequality follows from Fmax R. Substituting
(G.13) into (G.12) we have
R²
m dlog 1
LAx?
h S reg. +
log(4t2 (2(441//) +
2
4dk²
maxx R
t.Ax 4dK2
R²
2d 1
log(41
18)
log (4t² 14t²(1+²) 18)
2K
k
1 reg.
2R
log 2
(4t² (5)//5)
max dlog
1+ 4dK²
LAR?
2
K
tAk?
1
max dlog
1
R2 log"
(0(2(441))) (412/8)
2x
Adl2
4x
9
0 max dlog
LAn? 1 4dK²
reg,
R² log 1or2((11///))
(4///8) +
(G.14)
2
4x
K
Substituting the upper bound of /, above to G.5)
3 m
1 tAk?
reg. - 2 max (d(0)
+ reg
+ 4x
R2 logg(4#* /0) +
dlog
2
2
4d
B2
9
R² log (412/5) + 3 - d
tAk²
1+ 4dK3
(G.15)
2k
from which we can further complete the proof by the arbitrariness of t.
In the following lemma, formally introduce the conversion from online learning regret to confi- dence set in our setting. For simplicity in analysis, we omit the level subscript and suppose all the data is fed into the same level.
Lemma G.6. Suppose we feed loss function {L.(0)) 1==1 into single online learner B. Assume that B has an online learning (OL) regret bound reg,: Vt 1.
(.(O.) - e, (0)) < reg.-
(G.16)
26

---

Under review as a conference paper at ICLR 2023
Define X, as the design matrix consisting of a1," at least 1 - 45,
at, 2, = 12,,,-. ,2]. Then, with probability
v4 2 1, 10- 0.ll S
1
4 + R
reg
8R? R²
log (4f + AB² - -12:112-0
0, xx
x1) (G.17)
G. we can prove this lemma by following nearly the same proof for Theorem 1 in Jun et al. (2117). (We can set 8 in their proof to be 1 + Arg, + 8.z² Lemma G.I.
Proof. With Lemma
x² log (4f//) according to
Lemma G.7. For all f, with 2, and X, defined as in Lemma
G.8
have
2z 12 0 x Zt 2 0.
Proof. After ridge regression, 0: V, x, 24 where V == AI + X, X,.
Then we have
1ze - 0,X, 2, = ||r11 V x Zz
T
X
= =11zr11 ze x, V x, Zt
(G.18)
We consider
AI A X, X - Ix Xx, 1
(G.19)
X,
From Schur complement theorem, have
I (I+ -,,V, X
(G.20)
Then we can complete the proof by substituting G.20 into G.18.
Lemma G.8 Varraance-eependent confidence set for generalized linear bandits). Suppose that As- hold. For any E (0, 1/4), if we set
sumption 6.1
6.2 6.3
32 B²
26
12(1+17722
tAk?
Br,1
R log LA)2 12
dlog
1+
+ AB3
x²
4dK²
(G.21)
then with probability at least
46, we have 0 E Ct. for all 12 1,1 [4].
Proof. For any E [4]. with probability at least 1- - r.
8R²2
|10 11. 1 - reg.. +
x² log L/6) + XB2
making use of Lemma G.8 and Lemma G.7
and
From Theorem 6.5 with probability at least 3 we can
K2
R² logo (4t + +3 2²
tAk?
dlog
1+
(G.22)
K
2x
K
4dK2
By Union Bound, with probability 48, for all / E [Z].
32 B²
18 n2
22(1+11
LAR²
|00
-0u.11
51+
R² log 2 (4/) +
d dlog
11
k²
n²
4dk²
8R
log (41² L/8)
XB2
x2
32 B²
26
1)1++1)
tAk? 4dK²
R² log" (4t L/8) 12
dlog
1
+ +AB
x2
x²
27

---

Under review as a conference paper at ICLR 2023
Theorem G.9. Suppose that Assumptions 6.1 and 6.2 hold for the known reward function class F. as a subroutine of Algorithm we apply Algorithm 4
(in line 9) and set Be,1 to
X2 x²
26 K²
2 R² log (4t L/8) + 12
22
doog
I+
tAk²
AB
x²
4dK²
for all E [T), 11 R/Vd, then with probability 46, the regret of Algorithm for the first T rounds is bounded as follows:
Regret(1) = =T) =0(4)
- (T
K (K AB+ + R) dT
Proof.
Regret(7) = Σ
Mxx,, 0¹) -x(x, 0*)
[E[T]
< K
(x,-00 0- x, x²00))
TT(T]
K
max
x x 0¹
DENiE(2)Ci-11
(E(T]
K
Σ
max (ECLI
x, 0 x 0"
TEVT
K
Σ
min 2AB Xx |x V 02
max
|00
022l
Ec...11
1EVT44.
< 2K
Σ
Σ
min (2 [ 1.. AB).
(G.23)
[E[L] LE
where the first equality holds by the definition in (31 the first inequality follows from Assumption the second inequality holds by Lemma G.8
6.2
For an arbitrary / E [4], let I (1) {t E VT+IA |x A h. $1} and Iz(() = 1T-1,
[x [xxllv=1 AB) S BT,1 Σ min [
212
Σ
min(1 | /xxxlllvi..
IEI,
3r
[min(1, ||x
)
EEI.
dA + TA?
/
(G.24)
dA where the second inequality holds by Cauchy-Schwardt inequality, the third inequality follows from
Lemma G.2 Similarly, calculate
Σ min
AB)
S AB Σ
min ||
IEI
TEI.
< AB
[min(1, ||x 1
d) + TA2
< AB 2 2/U log
(G.25)
dA
28

---

Under review as a conference paper at ICLR 2023
Substituting G.24 and (G.25) into G.23 obtain
dA + TA²
Regret - 2K
(AB + v Br.1) 2 v r+1.
dd
[E[L]
AA + TAA2
< 2K
2(AB + (B log
dA
iE(L]
dd + TA?
dd + TA?
S 4KVL
AT log
Brad T logg
Yd
dA
[E[L]
4V2AKB
d T
S <4KVL
1+
+ Rlog 4T L/6) L/0) + VAB + AB
K
dA
dA + TA2
tAk²
4KVL
12
log (2+1
log
1+
d'
4dK3
iE[L]
4vZAKB
dλ TA2
$ 4KVL
1
+ Rlog(447 (elog(4T"L/8)) L/6) + VAB + AB
ddT
dTlog
log
K
dA
dA + T
tAk² 1+
+ AK
Loog
log
Σ [E[T]
12
12
4dK²
R²
LEVTI
4V2AKB
dd + TA2
S4KVL
+
Rlog 4T L/0) + VAB + AB
dI ddTlog log
K
dA
dA + T
LAR² 1+
AK
Loog
log
Σ
48
(o +
dA
4dK2
KE|Ti
1+ 4V2AKB
dd T'A
S <AKVL
+ K
Rlog Rlog(44 (/8) + VBB + AB |
dTTlo
K
dA
dA + TA2
LAR² 4dK2
24 d Loo
log 1
VJ+FT
dA
where the second inequality holds due Cauchy-Sehwarz inequality, the fourth inequality fol- lows from the definition of Se,,, the sixth inequality holds since 4 in Algorithm | satisfies 2 < max(o,, F. the last inequality follows from the definition of
29


Reviews:
[{"review_id": "vM99MJdoks", "reviewer": "Reviewer_npEC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This work considers the bandits' problem with general function classes and heteroscedastic noise. Under the assumption that the variance of the noise is simultaneously given with a reward after each round, they give the first variance-aware regret bound in terms of Eluder dimension. Their main technical innovation is to propose a multi-level learning framework that partition the historical data into several layers according to the given variance and applies base bandits algorithms on that. Besides the result on general function classes, they further give results on generalized linear functions under this \"multi-level\" framework. By using the generalized linear online-to-confidence-set conversion (GLOC) algorithm proposed by Jun et al. (2017), equipped with FTRL, they show that the results under such function classes can be further improved by $\\widetilde{O}\\left(\\sqrt{\\operatorname{dim}_E \\log N_\\alpha R T}\\right)$", "summary_of_the_review": "The results are solid and clear. My only concern is their techniques are a bit incremental and their known variance assumptions make those techniques even easier. But I am willing to raise my score if there are some technical novelties that I missed.", "strength_and_weaknesses": "Strength: Their results are solid. Their proposed \"multi-level\" framework has some novelty.\n\nWeakness:  The known variance assumptions largely reduce the difficulty of the whole problem. With this info and given the previous VOFUL algorithm which also considers the multi-level variance, this idea seems not very surprising to me. Furthermore, its generalized linear function results also seem a bit incremental. (Their first improvement that change R to $\\sigma_\\text{max}$ seems very direct given the variance is known. Their further improvement on d is not clear to me how significant it is...)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "in25siZ3nqe", "reviewer": "Reviewer_pkxU", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper considers the problem of general functions from a general function class under a bandit feedback model. Specifically, this work considers the setup of heteroscedastic noise where in the noise varies with different actions, possibly depending on the action taken by the learner. Under this scenario, the authors proposes a new algorithm that can leverage the heteroscedasticity of the noise and incurs a regret bound dependent on it, allowing it to take advantage of low noise regimes. The authors also propose a variant for the generalized linear bandit model and establish its regret performance.", "summary_of_the_review": "As mentioned above, I am not convinced about the contribution being novel enough, which is why I am giving the paper a score of 3.", "strength_and_weaknesses": "Strengths:\n- The paper considers an important problem with real applications and has proposed several algorithm to tackle the challenges of heteroscedastic noise that offer improved performance over existing ones.\n\nWeaknesses:\nIn additional to the comments about novelty in the next section, I have following questions/comments.\n- The algorithm assumes availability of $\\sigma_t$ from the environment which is different from estimating it. Can the authors support the feasibility of such an assumption by perhaps an actual application?\n- In Sec. 5. it says, \"In this section, we consider the original setting introduced in Section 3 without Assumption 4.1.\", where Assumption 4.1 is the assumption sub-Gaussianity on the noise. However, in proof of theorem 5.1, sub-Gaussianity of noise plays an important role and the result of this theorem is used throughout the section. Can the authors please explain this inconsistency?\n- While I understand that the main contributions of this work are theoretical in nature, I feel it is important to provide empirical evidence, especially while submitting it to a conference like ICLR. I am also interested in seeing the practical performance of these algorithms because of their similarity to Sup-family of algorithms (see next section) which are known to perform poorly in practice. Having some simulations might provide better insight into the algorithm performance and its ability to leverage heteroscedastic noise.\n- As a minor comment, I think the exposition would benefit by adding some more intuition about the algorithms while describing them.\n- Typos: provaly -> provably (pg 2, second paragraph), variaces -> variances (pg 5, last paragraph before Sec. 4).\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "cpQ9l0yUSxj", "reviewer": "Reviewer_gqkL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "This paper considers a stochastic bandit model where the reward function belongs to a class of uniformly bounded functions and the additive noise can be heteroscedastic. A multi-level learning framework is proposed to tackle this general bandit model where this paper designs an algorithm to construct the variance-aware confidence set. For generalized linear bandits, FTRL is introduced to achieve a tighter regret.  \n", "summary_of_the_review": "Overall, I think that the studied model in this paper is well-motivated. The introduced variance-dependent regret and FTRL in the extended model are interesting and with sound analysis. Therefore, I recommend “weak accept”.\n", "strength_and_weaknesses": "Strength: This paper is well written. The proposed model extends the previous generalized linear ones with sound theoretical results.\n\nWeakness: No experimental results are provided to support the theoretical results.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "56068ObR1tk", "reviewer": "Reviewer_Hrpw", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper studied bandits with general function class and heteroscedastic noise. A variance-dependent regret bound is derived.", "summary_of_the_review": "This paper is a bit incremental since it combined eluder dimension approach with variance aware confidence set. Several limitations:\n \n1. Eluder dimension provided little new information beyond linear. \n2. The algorithm is not computationally efficient with non-linear function approximation.\n3. The author should carefully discuss technical novelty beyond existing works since this is a pure theory paper. \n", "strength_and_weaknesses": "Extending linear model to nonlinear model with provable guarantee is an important topic in bandits problems. However, the approach of using eluder dimension is a bit incremental. There is no much technical novelty as far as I know. \n \n1. It is well known that only linear and generalized linear models have bounded eluder dimension, and the eluder dimension of one-layer neural network has exponential dependency on d. Using the Eluder dimension does not provide much more insights than linear models. So it is unclear to me how \"general\" the function class is.\n \n2. The efficiency column of Table 1 is very misleading. It is also well known that UCB based on eluder dimension is computationally-inefficient for non-linear function class. I do not think an empirical risk minimization oracle is enough. If we look at line 5 in Algorithm 1, you need an optimization oracle to find f. This is a much stronger oracle. \n \n3. Most techniques and algorithmic designs seem to be used before (variance-aware algorithm, multi-level partition scheme of the observed data). This restricted the technical novelty of the paper.\n \nLinear Contextual Bandits with Adversarial Corruptions, NeurIPS 2021. \nNearly minimax optimal reinforcement learning for linear mixture markov decision processes. COLT 2021.\n \nExtending the UCB-style algorithm from linear case to non-linear case using Eluder dimension also has been used in multiple papers before. \n \nReinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension. NeurIPS 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject