How Does Variance Shape the Regret in Contextual Bandits?
Authors: Zeyu Jia
Jian Qian
Alexander Rakhlin
Chen-Yu Wei
Venue: NeurIPS 2024 poster (2024)
Keywords: contextual bandit
regret analysis
Primary area: bandits
TL;DR: We study realizable contextual bandits with general function approximation, and derive near-optimal variance-dependent bounds that demonstrate the role of eluder dimension in this case.

Abstract: We consider realizable contextual bandits with general function approximation, investigating how small reward variance can lead to better-than-minimax regret bounds.  Unlike in minimax regret bounds, we show that the eluder dimension 
$d_{\text{elu}}$$-$a measure of the complexity of the function class$-$plays a crucial role in variance-dependent bounds. We consider two types of adversary: 

(1) Weak adversary: The adversary sets the reward variance before observing the learner's action. In this setting, we prove that a regret of $\Omega( \sqrt{ \min (A, d_{\text{elu}}) \Lambda } + d_{\text{elu}} )$ is unavoidable when $d_{\text{elu}} \leq \sqrt{A T}$, where $A$ is the number of actions, $T$ is the total number of rounds, and $\Lambda$ is the total variance over $T$ rounds. For the $A\leq d_{\text{elu}}$ regime, we derive a nearly matching upper bound $\tilde{O}( \sqrt{ A\Lambda } + d_{\text{elu} } )$ for the special case where the variance is revealed at the beginning of each round.  

(2) Strong adversary: The adversary sets the reward variance after observing the learner's action. We show that a regret of $\Omega( \sqrt{ d_{\text{elu}} \Lambda } + d_{\text{elu}} )$ is unavoidable when $\sqrt{ d_{\text{elu}} \Lambda } + d_{\text{elu}} \leq \sqrt{A T}$. In this setting, we provide an upper bound of order $\tilde{O}( d_{\text{elu}}\sqrt{ \Lambda } + d_{\text{elu}} )$.

Furthermore, we examine the setting where the function class additionally provides distributional information of the reward, as studied by Wang et al. (2024). We demonstrate that the regret bound 
$\tilde{O}(\sqrt{d_{\text{elu}} \Lambda} + d_{\text{elu}})$ established in their work is unimprovable when $\sqrt{d_{\text{elu}} \Lambda} + d_{\text{elu}}\leq \sqrt{AT}$. However, with a slightly different definition of the total variance and with the assumption that the reward follows a Gaussian distribution, one can achieve a regret of $\tilde{O}(\sqrt{A\Lambda} + d_{\text{elu}})$.

How Does Variance Shape the Regret in Contextual Bandits?
Zeyu Jia Massachusetts Institute of Technology zyj i a@mit. edu
Jian Qian Massachusetts Institute of Technology j jianqian@mit edu
Alexander Rakhlin
Chen-Y Wei
Massachusetts Institute of Technology rakhl inmmit edu
University of Virginia chenyu www.wwiriiiia.eee... edu
Abstract
We consider realizable contextual bandits with general function approximation, investigating how small reward variance can lead to better-than-minimax regret bounds. Unlike in minimax regret bounds, we show that the eluder dimension detu measure the complexity of the function class-plays a crucial role variance-dependent bounds. We consider two types of adversary:
Weak adversary: The adversary sets the reward variance before observing the learner's action. In this setting, we prove that a regret of S2( ///m////AAA [A, detu + detu) is unavoidable when detu I / AT, where A is the number of actions, T is the total number of rounds, and is the total variance over T rounds. For the A < delu regime, we derive nearly matching upper bound Ó AAA + detu) for the special case where the variance is revealed at the beginning of each round.
The adversary sets the reward variance after observing the learner's action. We show that regret of ((vd(aa))) dehiA detu) is unavoidable when VeetuA + detu I VAT. In this setting, provide an upper bound of order Ö(deaVA detu).
Strong adversary:
Furthermore, we examine the setting where the function class additionally provides distributional information of the reward, as studied by Wang et al. (2024). We demonstrate that the regret bound Ó detAA delu) established in their work is unimprovable when Vd detu I VAT. However, with a slightly different definition of the total variance and with the assumption that the reward follows a Gaussian distribution, one can achieve a regret of ((v AA detu).
Introduction
We consider the contextual bandit problem that models repeated interactions between the learner and the environment. In each round, the learner chooses action based on the received context, and observes the reward of the chosen action. Algorithms designed to achieve minimax regret guarantees under variety of statistical assumptions and computational models have been extensively studied (Auer et al., 2002; Dudik et al., 2011; Agarwal et al., 2012, 2014; Foster and Rakhlin, 2020; Xu and Zeevi, 2020; Simchi-Levi and Xu, 2022; Zhang. 2022).
However, these algorithms often fail to leverage the potentially benign nature the environment. In this work, refine the regret bound by considering the variance of the reward. Such variance- dependent regret bounds, also known as second-order regret bounds, have been primarily studied under linear function approximation (Zhang al., 2021; Kim al., 2022; Zhao al., 2023). Notably,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Zhao et al. (2023) first established a near- optrmml O(dvA + d) regret bound for linear contextual bandits, where d represents the feature dimension and A the sum of the reward variances.
For contextual bandits with general function approximation, the recent work by Wang et al. (2024) obtained second-order bound assuming access model class containing distributional information about the reward. They showed a regret bound of /dela log [M + deta log [M]), where [.M] is the size of the model class, and dein = dein (MM) is its eluder dimension. As noted in Wang et al. (2024), the dependence on delu is undesirable, and when the number of actions A is much smaller than delu- this bound can potentially be improved. This conjecture is supported by Foster and Rakhlin (2020), who showed that the upper bound Al [F + A log (FI is achievable regardless of the eluder dimension, where T Σ A is the number of rounds, and [F] the size of the function class containing mean reward information. It is tempting to conjecture that the regret can smoothly scale with A, resulting in a bound of O / /AA log F + Alog [F.). Such prriance-dependerr regret bounds that replace the dependence on the number of rounds T' by the total variance A have been shown in multi-armed bandits (Audibert et al., 2009). linear bandits (Ito and Takemura, 2023), and linear contextual bandits (Zhao al., 2023).
In this paper, we show, surprisingly, that the aforementioned conjecture is not true in general. Specifically, for any A and any detu I VAT, one can construct a problem instance with lower bound 22( m A, detu + delu) with log [F] = Olog 7) and (Flu(F) = detu- This rules out the possibility of achieving Ø(AAA log [F] + A Alg (FI) for all A because we can always make detu- VT, resulting in lower bound 92( VAT even with A O. Our primary goal is to design algorithms that achieve the near-optimal regret bound Ö /min (A, detu A log [F] + detu log [FI).
The lower bound v //nin A, dehu JAA + delu indicates that the complexity of contextual bandits arises from two parts. The first part accounts for local estimation of the true function, where the complexity due to the variance of the reward and the local structure of the function set around the ground truth function / E F. This results in the term /minn (A, detu A, with the leading coefficient min (A, d corresponding to the decision decision-estimation coefficient (Foster et al., 2021). The second part accounts for global search for the true function, in which the complexity is due a more global structure of the function set and can be quantified by the disagreement among the functions. The complexity of this part scales with detu: even when A 2. The contribution of the global part is usually overshadowed by the local part when only considering regret bounds with constant variance. Our work highlights its role by studying the variance- variance-depender dependent bound. The fundamental role of disagreement is also discussed in Foster et al. (2020) for gap-dependent bounds. Specifically, they also showed that when trying to obtain the gap-dependent bound that has logarithmic dependence on T. the complexity must scale with some disagreement measure over the function class, instead of just the number of actions.
The previous work by Wei al. (2020) also derived set of results for general contextual bandits showing that the tight accond-orde regret bound is strictly larger than merely replacing the T in the minimax bound by the second-order error. They consider the more general agnostic setting but the tight regret bounds are only established for the [F] = 1 case. Their result for |F] > can be applied to our setting, though only gives highly sub-optimal bounds. Overall, our work refines theirs the realizable setting.
When preparing our camera-ready version, the concurrent work of Pacchiano (2024), which studied exactly the same problem as ours, was posted on arXiv. We provide a comparison with their work in Section 3.4. More related works are discussed in Appendix A.
2 Preliminaries
A contextual bandit problem consists of a context space X, an action space A. the total number of rounds T and a class of functions F C [0, x|xxA, At round t, the learner observes a context x, E X, then makes decision a, A based the current context 2e and history, and observes reward rt- We assume that these rewards rt are given by
T f + Et:
where f : X' x A - [0, 1] is some function unknown to the learner, and e, are independent zero- mean random variables with variance of such that r E [0, 1]. We denote A = ΣT= The learner
We assume bounded noise for simplicity. The extension to L-sub-Gausste noise straightforward
2

---

aims to optimize the total expected regret Rr, defined as
RT
max
(" 8 (xr, aEA
We make the following realizability assumption: Assumption 2.1 (Function Realizability). Assume that f in Eq. (1) satisfies f E F.
We finish this section with the definition eluder dimension:
Definition 2.1 (Eluder Dimension (Russo and Van Roy, 2014)), For function class F defined on
space 2, we define the eluder dimension of F at scale a 2 0, denoted by det( (F; ) as the length of the longest sequence of tuples (21, f1. f(), .... (Zm; Jms fm) 2 x F x F such that there exists or 2 a making the following hold for all 1,.,, m.
((ile)) -(ll)))((((s)))) S ag, and [f((zi) - f((zz)) > ag. jEi
Throughout the paper, if a not specified, we take the default value a 1/T². We also omit the dependence on F when it is clear from the context.
Results Overview
We describe our three settings in the following three subsections and summarize the results in Table 1. In the following, F denotes the function class that only contains reward mean information, and M model class that contains reward distribution information.
3.1 Weak Adversary Case with Variance Revealing (Section 4)
First, we consider the case where the adversary is weak. This means that the variance only depends on the history up round / 1, which aligns with the standard "adaptive adversary" assumption. For this case, we show that for any A and d, one can find an instance of contextual problem problem with | < VAT, such that the regret is at least
Ω (Vmint A, detu min (delu: VAT))
For upper bounds in the weak adversary case, focus the regime A S detu S VAT, where the lower bound can be written Ω 2(VAA + deuu)? While our ultimate goal is to obtain nearly matching upper bound Ō AAAAAAL log [F[ + detu log [F)) we have not achieved it yet full generality, In Section 4, we provide an algorithm which operates under the assumption that the variance a, is revealed the learner at the beginning of round and show that it achieves the matching upper bound. An initial attempt to remove this assumption is discussed in Section 7, where we show that when 0, E {0, 1} for all and o, revealed to the learner at the end round f, the matching upper bound can also be achieved.
3.2 Strong Adversary Case (Section
Next, consider the case where the adversary is strong. This means the adversary can decide oa after seeing the action as chosen by the learner at round t. this case, the lower bound becomes
Ω (min dedeu + detu, VAT))
The difference with Eq. (2) that the scaling in front of A changes from min (A, d to detu- This shows the even more crucial role of eluder dimension in the strong adversary case. For this setting, we give an upper bound of (deru / log |Fi + detu log [F), which is off from the lower bound by Vdeta factor along with other logarithmic factors.
A < dem < VAT is more challenging and clusive regime, and we focus our study here. When dem VAT. we can use SquareCB (Foster and Rakhlin, 2020) to achieve the tight bound VAT: when det < A. use the algorithm in Section 5 to get deta / A det.. which is tight up /deu factor.
3

---

Table 1: Results overview. delu refers to either (F) or (et( depending the settings. In Section and Section 5, == Σi= In Section Ave == Σ max, aM (2,, a)² and As := Σi= aM- (Ix, az)², where M E M is the underlying true model, and x a)² is the reward variance for (a, a) predicted by model M.
Notice:
For simplicity, this table only considers the case A s delu- and all lower bounds should be further taken minimum with VAT.
Upper bound (omitting log T factors)
Lower bound
Weak adversary + revealing de (Section 4)
V log [F] + detu log [F]
VAA + delu (Theorem 4.1)
(Corollary 4.1)
Strong adversary (Section 5)
delu / A log [F + detu log [F]
Vdeua + detu (Theorem 5.1)
(Theorem 5.2)
Learning with model class
AAoo log M + deta log |M
VAA + det (Theorem 6.2)
(Section 6)
for Gaussian noise (Theorem 6.1)
Learning with model class (Section 6)
v /eluAo log M + deta log [M
v VdduuA + detu (Theorem 6.3)
(Wang et al. (2024))
3.3 Learning with a Model Class (Section 6)
In Section 6, we assume that the function class provides information on the distribution of the reward rather than just the mean. Such function class is usually called a model class. More precisely, the learner is provided with a model class M that includes the true model M E M so that MM' a) specifies reward distribution for the context-action pair (I, a). Compared to the scenario studied in Section 4. here we do not require variance to be revealed to the learner. This becomes possible because with a model class, the learner can now obtain variance information (though not precise) through the context. Under the assumption that the noise is Gaussian, we provide an O( log [M| + detu log (M]) upper bound where Ax E. max, dM az), and matching lower bound, where aM (x. a) the reward variance for the context-action pair (2r a) predicted by M E .M.
The work of Wang et al. (2024) also studied second-order contextual bandits with a model class. They use A, Ee Ar (Ii,, )² i.e., the reward variance of the chosen actions, as the variance measure. They obtain Ō( Ao log [M + detu log [Ml) upper bound. We show a nearly matching lower bound (mmin ( Ae + delu. VAT)), similar to the lower bound for the strong adversary case studied in Section 5. The lower bound indicates that, in general, the bound of Wang al. (2024) cannot be improved even when A < delu-
3.4 Comparison with Pacchiano (2024)
The work of Pacchiano (2024) also studied variance-dependen bounds for realizable contextual bandits. They also consider two settings, which can be mapped to those in our Section and Section 5, respectively. For the weak adversary setting with revealed 0z (Section 4), they give upper bound of O(v log [FI + detu log [F)), which is incomparable to O(VAN AA log [Fl + detu log (FI). However, a full picture of this setting can be obtained by combining their upper bound and our upper bound and the lower bound in Eq. (2). For the strong adversary setting (Section 5), they derive exactly the same upper bound as in our Theorem 5.2. Our work makes additional contribution in the lower bounds and the extension to the distributional setting (Section 6).
4 Weak Adversary Case with Variance Revealing
In this section, we consider cases where the variance of at round / is given to the learner at the beginning of round together with the context Zt.
3 Although Pacchiano (2024) presents this result by assuming = a for some known a,, it is straightiorward extend it to the case where de are different but revealed before each round, just like in our Section 4.3.

---

4.1 Lower Bound
The regret lower bound is shown with identical and known variance. The construction is similar to those in Wei al. (2020). Concretely, we have the following theorem.
Theorem 4.1 (Main lower bound). For any integer d, A 2, any positive real number and time T > O, there exists a context space X' and a contextual bandit problem F C (X' x A ++ R with eluder dimension (0) I d, action set A with |A| S A, and variance 0t a for all t [T] such that any algorithm will suffer a regret at least S 0( min d)T + -min(,, VAT)).
[0. 1].
Proof sketch. The full proof is deferred to Appendix C. The two parts in the lower bound came from the following two different hardness: (1) The first part of the lower bound with 92 oz2 min A. d) is a natural lower bound with variance a due to estimation of the mean values. (2) For the second part, we consider the following function class. In this function class, there is "good" action that serves as the default choice with a reward of 1/2 for all contexts. For each of the other A - 1 "bad" actions, for each context, there is one function that obtains reward of but obtains 0 for all the other contexts. When d < VAT, this function class forces the learner to guess for each context which action choose. So even if the reward is deterministic, i.e., variance o O, any learner would have to suffer a regret scaling with the number of contexts times the number of actions, which in total coincide with the eluder dimension. When d 2 VAT, the learner can simply commit to the "good" action and suffer v AT but no better than this. This lower bound is rather surprising for the following consequences: (I) The most significant implication from this lower bound is that improving the minimax regret bound with the knowledge of the variance is only possible if d < VAT. (2) Even when d < VAT, any learner would have to pay for the eluder dimension as a lower-order term. These are non-trivial because the second-order bounds are usually obtained from changing Hoeffding concentration to Bernstein concentration which usually only scales the regret bounds by a. This lower bound shows that the second-order contextual bandit is not one of the usual cases. In the next section, we will match this lower bound from the upper bound side by combining several algorithmic techniques.
4.2 Upper Bound with Known and Fixed Variance
Motivated by the lower bound in Theorem 4.1, we wonder whether there is an algorithm which can achieve matching upper bound of Ō O(V0² (,, d)T + min(d, VATH), if the learner is provided with information of variance at the beginning of each round. In this subsection, we answer this question affirmly. To begin with, we consider the case when all the variance are identical, i.c.
σ1 02 = oT = a, and a is given to the learner. Later (Section 4.3), we will discuss how to generalize this result to the case with nonidentical variances across different rounds.
We assume that r; I (xt,, ax) + e, E [0, 1] and Var(er) S of for every 1 S L < T. Our results can be easily extended to subgaussian random noise (at the cost of a log factor) since for such variables, with probability at least 8, eel < C CV (VVoo((/))) for a constant C.
4.2.1 Algorithm and Analysis for Identical Variance
We first consider the case with identical variance, i.e. of = 02 for all [T]. We propose Algorithm and show that has regret upper bound O(v log [F + detu log| [F). The algorithm is adapted from SquareCB of Foster and Rakhlin (2020), but additionally maintains confidence function set, and has mechanisms to learn faster when the functions the confidence set has larger disagreement. It has the following elements:
1. Restricting action set (Line 4) At the beginning of round (Line 4), the learner restricts the action set to Ar, which only includes those actions that is the best action of some functions in the function class F.. If we assume that f is always in the function class Fe, by doing this we remove the unnecessary possibility of choosing actions that can never be the best action.
2. Checking disagreement (Line 5-Line 7) The next step of the algorithm is to check whether there is an action in A such that two functions in the function class have large value differences (Line 6). We called such actions "discriminative actions". Roughly speaking, are seeking an action a E A, such that
ff E Fr.
If a) - -(
5

---

Algorithm VarCB (Variance-aware Contextual Bandits)
Input: E [0, 11, [/AT, 1].
1: Let L log 602 and A 11VI.
[FIT
and Fi F. o²
2: for 1...... do
3: Receive context Zt.
4: Define At = {a E A: Af Ft, max (z),
5: Define
-
(((a) sup S.F'F v m= w/ (-(((rr, - fx,,
E.
(4)
6:
if maxaEA (a) > A then
7:
Choose action ag = arg max A.A, (a) and receive rt-
8:
else
9:
Call online regression oracle (Algorithm 4) with input (Fe, xx) and obtain ft. a) (pick arbitrary maximizer if there are multiple).
10:
Let b: arg m fc(#e,
11:
Draw a₁ ~ Pt and receive Tt, where
a E A A., a E A \ {br), if = bt.
Pe(a)=
(inverse gap weighting)
Dela') A -
Define Wi = min {
(1
12:
( s((aiVi)) and update the confidence set:
Fit1 {EFF:
Σ
Wy (f(rr, l ax)) 102L
(5)
where fi41 = mig
wy a))
(6)
fEFt T=1
If such an action exists, then the learner chooses this action at round l. By selecting such an action that discriminate disagreed functions, the function set Fr can more quickly shrink. To prevent this action to incur overly large regret, it is important to perform Step (Restricting action set). The regret incurred rounds choosing discriminative actions of order (d log [F))
Inverse gap weighting (Line 8-Line 11) At round t, if there no diseriminative action, then the learner performs inverse gap weighting in the SquareCB algorithm (Foster and Rakhlin (2020)). Inverse gap weighting requires the learner have access to an online regression oracle that generates online estimations Je and ensures that the estimation error (Je(F,, ax) f-* (x,, az))² is small. In the original SquareCB, the requirement for the online regression oracle is
Rsq E(i(an -r) (( - rr)² S log Fl,
(F&R's condition)
which only allows for / /TT log [F regret bound that does not meet our goal. To improve this, we design an online regression oracle that ensures
Rsq
Σ (f((z), 2z) 2 TETION
Σ (1) - 25 (o² + Log [F,, (our condition)
EE TETiaw
where Tiaw is the set of rounds that we run inverse gap weighting (i.e., entering the else case in Line 8), and Á is upper bound for max max [ a) (" a)], i.e., the maximum disagreement among the function set J, for the context 2;. Thanks to Step 2, we only run inverse gap weighting when S A o². Thus, with the refined Riq guarantee and standard squareCB arguments, get regret bound of order / AT log F for the rounds in Tiew-

---

The way to achieve "(our condition)" is an interesting part of our algorithm. A standard way to ensure F&R's condition is by aggregating over the function set through exponential weights. Exponential weights ensures Raq (log [FI/n) long as the functions to be aggregated are 77mixable. Thus, in order to show Req = O log [F), we need to argue 1) 92(1/²². However, because the potential range of Tr is [o. IJ even though the variance a² and and the disagreement A are both much smaller than 1, the best mixability coefficient 1) we can show for squared loss still (1)).
To address this, we resort to the use of the Prod algorithm Dessa-Bianchi and Lugosi, 2006) with a properly chosen surrogate loss to perform aggregation. This algorithm has different second-order approximation for the loss compared to the exponential weight algorithm, which is crucial in obtaining the desired bound. The regret analysis is also no longer through mixability. Our online regression oracle is provided in Algorithm 4 in Appendix D. We remark without giving details that in the linear case, such a guarantee can also be obtained through Online Newton Step (Hazan et al., 2007).
4. Updating function set (Line 12) After finishing selecting the action dz for round I, the learner updates the confidence function set Fr prepare for the next round. The construction of the confidence set utilizes the idea of weighted regression that has been widely used in previous variance- aware or corruption-robut
contextual bandit or RL algorithms (He et al., 2022; Zhao al., 2023; Ye et al., 2023; Agarwal et al., 2023). This has the effect of controlling the relative importance of different samples and is crucial in controlling the regret incurred in Step 2.
By putting these building blocks together, we arrive at Algorithm 1. The regret of Algorithm is described in Theorem 4.2, whose proof is deferred to Appendix D.
Theorem 4.2. Algorithm I ensures with probubility at least 1 - 6,
Σ (max S (x1, a) - (1t, =6 (V log (1F1/5) + deta log ((F1/6)) aEd
AT
Comparison with AdaCB of Foster et al. (2020) Our VarCB (Algorithm 1) shares some sim- ilarities with the AdaCB algorithm from Foster et al. (2020), which aims achieve a Ó( d log [-F] regret bound. Here, d is a disagreement coefficient of F, which takes the same role as our delu- and GAP represents the minimal reward gap between the best and second-best decisions. Specifically, both algorithms include step to remove irrelevant actions (our Step 1). The action selection rule of AdaCB also depends on the amount of disagreement over the function class, which superficially related to the if-else separation in VarCB. However, we find that the case separations in the two algorithms do not have clear correspondence to each other, possibly due to the different objectives of the two algorithms. Also, the two algorithms operate under quite different settings: AdaCB works in the setting where the contexts are i.i.d., while VarCB allows for adversarial contexts. On the other hand, AdaCB is parameter-fiee frree, but VarCB requires the information of a. Developing a more unified version for these two better- better-thann-eee than--tnimammmaaa algorithms is an interesting future direction.
GAP
4.3 Algorithm and Analysis for Heteroscedastic Noise
Next, we will discuss how to generalize our algorithm heteroscedastic case, i.c. when the noise of different rounds are different. Based on the values of the variance, we classify each round into the following (log (AT) 1) sets: if 0, [0, l. classify t into T; for 2 s < log i.e. if or falls into the i-th intervals in the following,
AT classify t into To, and for o, (2'-1 l
(7) we classify / into T. For each set T, we maintain an algorithm A of Algorithm in parallel, At the beginning at round i, when observing that & E Tr, only S is updated, while of remains the same for j # i. According to Theorem 4.2, we have for any 0 < log T,
En = 10, }. Σ ( 1. Σg = ( A..
Elog(AT) = (1/2,
(max f" (z), 1 (2(2,, a.)) =6 aEA
2' AT
log F + dein log (F1)
TT
we can bound the total regret by
(og(AT)
Σ δ (VATT)- (
(
T
(2'
log F deta log (F1)
=
Σ
of log F + deta log (F]
==1
7

---

Algorithm 2 Algorithm for Heteroscedastic Noise
Input:
Initialize instances o of VarCB (Algorithm with o ÄT for 0 Si log (AT).
2: for /= 1 : do
3: Receive o, E [0, 1), and suppose that o; E Σ, where Σ, is defined in Eq. (7).
4: Receive context zt, and inject into algorithm of. to obtain action dz-
5: Play action aj and update algorithm d/.
The formal algorithm for heteroscedastic cases is given in Algorithm 2, and we have the following corollary the second-order regret bound of Algorithm 2.
Corollary 4.1. The output a of Algorithm 2 in rount t satisfies that with probability at least 1 6,
(v
Σ (max ( = aEA
A Σ ==1
of
log (FF1) + detu log((F1/5)
The proof of Corollary 4.1 is given in Section E.
Strong Adversary Case
In this section, we consider the case where the adversary decides the variance o after seeing the action a, chosen by the learner. We provide regret lower and upper bounds matching up factor of Velu and other logarithmic factors. More importantly, the minimax regret bounds differ with the weak adversary case (Section 4) as discussed in Section 3.2, demonstrating the even more crucial role of eluder dimension in this case.
Regret lower bound In this strong adversary case, we first show that the adversary's power is en- hanced in terms of the achievable minimax regret bounds. Concretely, we have the following theorem.
Theorem 5.1. For any integer d, A,T 2 2 and any positive real number A E [o. T). there exists context space X, contextual bandit problem F C (X x A - RR) with eluder dimension detal 0) = d and action set A = [A] and an adversarial sequence of variances of...., of with Et. of < A such that any algorithm will suffer regret at least Mmin VdA d, VATT).
The above theorem shows that the regret is at least (mmin VdA d, VAT)) where even with log |F| Olog T). Recall that the bound in the weak adversary case (Section 4) can be written Q(min / min(A, d}AA d, v VA The power of the strong adversary is exactly the higher complexity d in the term compared to min{ A, d} in the weak adversary case. Now, we proceed to provide a matching upper bound up to factor of vd.
(F)
Regret upper bound For the strong adversary case, we adopt an optimism-based approach. In particular, we generalize the SAVE algorithm by Zhao al. (2023), which achieves the tight Ö(dVA + d) bound for linear contextual bandits. We call the algorithm VarUCB and display it in Algorithm 5 of Appendix F. The algorithm combines the idea of weighted regression and multi-layer structure of SupLinUCB (Chu et al. (201 1)) and refined variance-aware confidence set. Since this algorithm is a rather direct extension of Zhao et al. (2023)'s algorithm from the linear case to the non-linear case, we omit the detailed discussion on and refer the readers to Zhao et al. (2023). Notice that for this algorithm, we do not need o, to be revealed to the learner as in Section 4. In fact, we do not even need to know A. We have the following theorem for its regret guarantee.
Theorem 5.2. When facing the strong adversary, Algoritium 5 guarantees a regret bound of (deli / log FF + deta log FF) with probability at least 1 - 5. where ((.) hides log(T'6) factors.
The proof is provided in Appendix F. Notice that when specializing Theorem 5.2 the linear setting, the bound becomes Ó(V + d²) since log | = (dd) which does not recover the bound of Zhao et al. (2023). Indeed, our analysis deviates from that of Zhao et al. (2023) due to the generality of non-linear function approximation.
an interesting future direction to see whether our bound can be improved. We mention in passing that the work by Wang al. (2024) obtained
8

---

Algorithm 3 DistVarCB (Distributional Variance-aware Contextual Bandits)
1: Let Mi M, Mi = [M ΣMEM M, and L = O(log(-M(T/0).
2: for f == .,..., do
3: Receive context Zt-
4:
if IM,, M E M,, and E A such that (M, a), M2,, 1/2 then
5:
Let 4 = and pull az = arg max, M..M, Dj (Mx, a), (z).
6: else
7:
Let 4 2 and pull a₂ Pi where
P: = arg min max Bawp max fM - fas(F),)) - (Far( Sas, (2e, a))² PEA(A) MEM,
(2r,
8:
Receive rt-
9: Let Me+1 Mr E.E (M as), Ms MM ax)) - T.).
EMEEM 9c(M)M where (M) x II. M(r, Fz. a.).
Let M++1 EMEMeN' (i(M)
VdA log M + d [M] upper bound where d = detu (M). However, the algorithm relies on having access model class. We study such a setting in our next section.
Learning with a Model Class
Distributional setup In this section, we consider the case where the learner is given model class M C ((X' x A) + (TR) where each model M M maps any context-action pair to gaussian distribution, i.e., for any E X x A,
M(x, =
(Z, a)),
where (I, a) and am (z, a) are the mean and variance of the distribution M a). We assume that all the expected rewards and variances are bounded by [0, 1]. Recall, at round f, the reward is given by ra [xx, az) + q.. We further assume throughout this section that e, is Gaussian with variance o* (x,,a)) (since Gaussian is unbounded, we drop the assumption тą E [0. 1] that made in Section 2). Thus, the distribution of rt follows true model M where M (I,
(f ( (x.
Assumption 6.1 (Model Realizability). Assume M E.
For this setup, it is useful to consider the Hellinger counterpart of the cluder dimension.
Definition 6.1 (Hellinger Eluder Dimension). For the model class M defined on the space Z (that is
M C (2 - (R)), we define the Hellinger eluder dimension of M at scale a 2 as dH (a) be the length of the longest sequence of tuples (=1, M1. My),.., ..., (Zms M M and org 2 such that for all = L,,,, m, functions Mi M² MM,
D((M og. and Di(()(()) > 2 ag.
Algorithm Similar to Algorithm 1, we present Algorithm tailored for the distributional case. At each round f, upon receiving the context T,, the algorithm first checks if there exists an action such that two models within the localized model class M₁ exhibit a significant divergence on the context-action pair It, measured by the squared Hellinger distance (Line 4). If such a difference is detected, the learner selects the action associated with the greatest divergence (Line 5). Conversely, no action causes substantial divergence between models, the learner runs a variant of SquareCB (Foster and Rakhlin, 2020), employing adaptive variances to ensure low regret (Line 7). The major differences between Algorithm and Algorithm that the latter measures the "disagreement" in terms of the squared Hellinger distance.

---

Regret upper bound We obtain the following distributional version regret bound for Algorithm 3. Theorem 6.1. For d = d/dl(///T) (/VT), the outpua at of Algorithm 3 satisfies with probability at least 1-
Ry= Ro=ō A OV=E
T' 2 (21) log([MM/6)) dlog((MM/5))
where Rg. (21) maX Rg-- (ze, a).
A similar upper bound for more general distributional case is obtained by Wang et al. (2024) in the form of Ō ((VdE== J.. the dependence
log [M] + loo [M]). In the leading term, our bound replaced by the number of actions A which is significantly smaller than in many cases of interest (e.g. linear, generalized linear). However, as a tradeoff, our bound also suffers a larger cumulative variance term. This tradeoff is necessary as we show in the following lower bound results that both our upper bound and their upper bound are optimal, i.e., matching lower bounds exist. Thus our result at one end of the Pareto frontier.
Regret lower bounds We present the matching lower bound for our result as follows, which is essentially rewrite of Theorem 4.1.
Theorem 6.2. For any integer d, A,T 2, any positive real number a E 10, 1l. there exists a context space X and a contextual bandit gaussian model class M C (X x A - ARR) with Hellinger eluder dimension d't, (0) S d, action set A = [A], and variances FM (I, a) S for all M E M, x, E X X A such that any algorithm will suffer regret at least @ min( djT + min(d, v VATH).
Now we present the matching lower bound for the upper bound from Wang et al. (2024).
Theorem 6.3. For any integer A, 2 2 and any positive real number
[0, TJ, there exists
context space X, a contextual bandit gaussian model class M C (X' x A + A AR)) with Hellinger eluder dimension di (0) S d and action set A = [A] and the variances _t= TM TM- a,)² S A such that any algorithmm will suffer regret least (min (VdA + d,, V AA
The lower bound obtained by Theorem 6.3 is an adaptation from Theorem 5.1 that crucially relies on the fact that the adversary can choose the variance according the action at.
7 Open Questions
Removing the revealing assumption in the weak adversary setting The assumption we made in Section that the variance revealed at the beginning of each round is rather restrictive, and ideally we would like to remove such an assumption. As a first step, we wonder whether the same regret bound Ó / AA + detu) is achievable if the variance d, is revealed at the end of round t. We answer this question affirmatively for the special case where a, E {0, 1]. More details can be found in Appendix H. How to extend this result to general values of a. is interesting open question. Handling the case where a is never revealed is even more challenging but is the ultimate goal.
Removing the Gaussian noise assumption in the distributional setting Our Theorem 6. heavily relies on the assumption that the noise is Gaussian. We wonder whether such assumption can be relaxed or completely lifted. For example, can we obtain the same bound if the noise at round is just dM- (I2, az) -ub uub-Gausiinn? What if it is just bounded noise with variance 2 ax)?
Acknowledgement
We thank Dylan Foster for helpful discussions. We acknowledge support from ARO through award 1911NFF21-- from the DOE through award DE-SC0022199, and from NSF through award DMS-2031883.
References
Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, and Robert Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19-26. PMLR, 2012.
10

---

Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1648-1646, 2014.
Alekh Agarwal, Yujia Jin, and Tong Zhang. Vo q I: Towards optimal regret in model-free r1 with nonlinear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pages 987-1063, PMLR, 2023.
Zeyuan Allen-Zhu, Sébastien Bubeck, and Yuanzhi Li. Make the minority great again: First-order regret bound for contextual bandits. In International Conference on Machine Learning, pages PMLR, 2018.
Jean-Yven Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-explorration tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876-102.
2009.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1))48-77, 2002.
Nicolo Resa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Nicolo BisaaBiannchi, Yishay Mansour, and Gilles Stoltz. Improved second-order bounds for predic- tion with expert advice. Machine Learning, 66:321-352, 2007.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 214. JMLR Workshop and Conference Proceedings, 2011.
Yan Dai, Ruosong Wang, and Simon Shaolei Du Variance-aware sparse linear bandits. In The Eleventh International Conference on Learning Representations, 2023.
Chris Dann, Chen- Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In The Thirty Sixth Annual Conference on Learning Theory, pages 5503-5570. PMLR, 2023.
Qiwei Di, Tao Jin, Yue Wu, Heyang Zhao, Farzad Farnoud, and Quanquan Gu. Variance-awarr regret bounds for stochastic contextual ducling bandits. In The Twelfth International Conference on Learning Representations, 2024.
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang, Efficient optimal learning for contextual bandits. In Proceedings of the Twenty-Sevenle Conference on Uncertainty Artificial Intelligence, pages 169-178. 2011.
Dylan Foster and Alexander Rakhlin. Beyond ueb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
Dylan J Foster and Akshay Krishnamurthy. Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. Advances in Neural Information Processing Systems, 34: 18907-18919, 2021.
Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance destence-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective. arXiv preprint arXi::2010.03104 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint 11Xiv:2112.13487 2021.
Dylan J Foster, Yanjun Han, Jian Qian, and Alexander Rakhlin. Online estimation via offline estimation: An information-thherrticc framework. Advances in Neural Information Processing Systems, 2024.
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
11

---

Elad Hazan and Satyen Kale. Better algorithms for benign bandits. Journal of Machine Learning Research, 12(4). 2011.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169-192, 2007.
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear
contextual bandits with adversarial corruptions. Advances in neural information processing systems, 35:34614-34625, 2022.
Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference on Learning Theory, pages 2552-255 2583. PMLR, 2021.
Shinji Ito and Kei Takemura. Best-of-three-wond linear bandit algorithm with variance-adaptive regret bounds. The Thirty Sixth Annual Conference on Learning Theory, pages 2653-2677. PMLR, 2023.
Yeoneung Kim, Insoon Yang, and Awang-Sung Jun. Improved regret analysis for auriance-adaptive linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing Systems, 35:1060-1072 2022.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Aldo Pacchiano. Second order bounds for contextual bandits with function approximation. arXiv preprint XrXi:22409. 11119979991119,, 2024.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221 2014.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 1933)1 2022.
Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-aware regret bounds for undis- counted reinforcement learning in mdps. In Algorithmic Learning Theory, pages 770-805. PMLR, 2018.
Vladimir Vovk. A game of prediction with expert advice. Proceedings of the eighth annual conference on Computational learning theory, pages 51-60, 1995.
Kaiwen Wang, Kevin Zhou, Runzhe Wu, Nathan Kallus, and Wen Sun. The benefits of being distributional: Small-loss bounds for reinforcement learning. Advances in Neural Information Processing Systems, 36, 2023.
Kaiwen Wang, Owen Oertell, Alekh Agarwal, Nathan Kallus, and Wen Sun. More benefits of being distributional: Second-order bounds for reinforcement learning. In International Conference on Machine Learning. 2024.
Chen-Yu Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1263-1291. PMLR, 2018
Chen-Yu Wei, Haipeng Luo, and Alekh Agarwal. Taking hint: How leverage loss predictors in contextual bandits? In Conference on Learning Theory, pages 3583-3634. PMLR, 2020.
Yunbei Xu and Assaf Zeevi. Upper counterfactual confidecce bounds: a new optimism principle for contextual bandits. arXiv preprint arXiv:2007.07887. 2020.
Chenlu Ye, Wei Xiong, Quanquan Gu, and Tong Zhang- Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. International Conference Machine Learning, pages 39834-39863, PMLR, 2023.
12

---

Andrea Zanette and Emma Brunskill. Tighter probemm-depended regret bounds in reinforcement learning without domain knowledge using value function bounds, In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834 857, 2022.
Zihan Zhang. Jiaqi Yang, Xiangyang Ji, and Simon S Du Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342-4355, 2021.
Zihan Zhang, Jason D Lee, Yuxin Chen, and Simon S Du. Horizon-free regret for linear markov decision processes. International Conference on Learning Representations, 2024.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang. and Quanquan Gu. Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory, pages 4977-5020. PMLR, 2023.
Runlong Zhou, Ruosong Wang, and Simon Shaolei Du Horizon-free and variance- dependent reinforcement learning for latent markoy decision processes. In International Conference Machine Learning, pages 42698 42723.. PMLR, 2023.
Julian Zimmert and Tor Lattimore. Return of the bias: Almost minimax optimal high probability bounds for adversarial linear bandits. In Conference on Learning Theory, pages 3285-3312. PMLR, 2022.
13

---

Appendices
Related Work
15
B Technical Tools
15
Omitted Proofs Section 4.1
16
D Omitted Proofs in Section 4.2
19
D.1 Analysis of the Online Regression Oracle
19
D.2 Proof of Theorem 4.2
22
E Omitted Proofs in Section 4.3
29
Algorithm for the Strong Adversary Case and Omitted Proofs in Section 5
F.1
Upper Bound
31
F.2 Lower Bound
36
Omitted Proofs Section
38
H Upper Bound with Zero-One Variance (Section 7)
43
14

---

A Related Work
In this section, we review the literature in bandits/RL that obtains second-order regret bounds or other datee/instance-deeeedeen regret bounds.
Tabular/linear bandits and MDPs Second-order regret bounds for bandits have been extensively studied in non-contextual (fixed action set) settings, such stochastic multi-armed bandits (Audibert et al., 2009), adversarial multi-armed bandits (Wei and Luo, 2018; 8; Ito, 2021), and adversarial linear bandits (Hazan and Kale, 2011; Ito and Takemura, 2023). Key techniques in this line of work include replacing Hoeffding-stylee concentration bounds with Bernstein-style ones in value estimation, and using optimistic mirror descent (Rakhlin and Sridharan, 2013) to achieve variance reduction. Extending beyond non-contextual settings, a series of recent works (Zhang et al., 2021; Kim et al., 2022; Zhao et al., 2023) have focused on obtaining tight variance- dependent bounds for linear contextual bandits. The techniques developed for variance prriance-depeneen regret bounds in bandits have been extended MDPs, leading either variance-dependent or horizon-free bounds (Talebi and Maillard, 2018: Zanette and Brunskill, 2019; Zhang et al., 2021; Kim et al., 2022; Zhao et al., 2023; Zhou et al., 2023; Zhang et al., 2024). Additionally, other settings such as dueling bandits (Di et al., 2024) and sparse linear bandits (Dai et al., 2023) have been explored.
General contextual bandits For contextual bandits with general policy or function classes, second- order bounds have been explored in both agnostic settings (Wei al., 2020) and realizable settings (Wang et al., 2024). Wei et al. (2020) focused on the case where the number of actions is small. They demonstrated that, unlike in multi-armed or linear bandits. the tight second-order bound for general contextual bandits is more complex than simply replacing the zeroth-order term T in the minimax bound with the second-order measure, which aligns with findings. For instance, even if the second-order error & is (1), they showed that the regret could still grow with ((TT//). On the other hand, Wang et al. (2024) focused on the case where the model class that provides distributional information for the reward has small eluder dimension. In contrast the small action regime, their bounds smoothly scale with the second-orde measure.
Other instance-dependent bounds in general contextual bandits Beyond second-order bounds, other works have focused on other data-dependent or instance-dependent bounds. For example, Allen-Zhu al. (2018), Foster and Krishnamurthy (2021), ), and Wang et al. (2023) studied first-order (small-loss) bounds for general contextual bandits and MDPs, in which the goal is to make the regret scale with VL*, where L* is the cumulative loss of the best policy. These bounds are generally achievable with specialized algorithms. For general contextual bandits, gap-dependent bounds that exhibit logarithmic dependence on 7 have been derived by Foster et al. (2020) and Dann et al. (2023) for realizable and agnostic settings, respectively. Notably, the algorithm of Foster al. (2020) has some similarity with our main algorithm, which we discuss further in the main text.
B Technical Tools
Lemma B.1. For any 0 S 1/2 and S /2, define
220, with proba. 1/2,
ate [20, with proba. 20
[20, with proba. atc
P. 10, with proba. 1/2,
p+
P-
10 with proba. 2a
a-c
10 with proba. 20
Denote by ho, ht o the means of the three distributions respectively. We have
ha J, h =0 + e, and h =0 -c
Let Vo. dee VoL be the variance of the three distributions respectively. We have
Vo. V+ 502
Furthermore,
402
DKL (Po, Pote))
(ote)
Gz
Proof.
DKL (Po, ||
0-6 -
log
+
0 +c
log
+
20
+e
20
15

---

c
0 +
c
log
20
2e
log
+
0
0
2e
4e2
o²
Lemma B.2. For any two gaussian distributions N (11, σ1) and and (u2,, 02), if log 01 log 02 > 3. then
(W) 2 2
Proof of Lemma B.2. Without loss of generality, assume 0s divergence between two gaussian distributions writes
E0 > 802. The Hellinger
20102 Di(N(mi. =
exp ( (1I u222
of + +
4(07 + 0z2)
20102
2
of + 02
201/02
2
2 2
(01/02)2 +1
Lemma B.3 (Lemma 4.2 of Wang et al. (2024)). For any distribution PP and Q on any space X such that D (F, Q) < 3. we have for any function h X - R,
[h] - Eq[h]] s 2 (Vary (h) + Varg Q)
Lemma B.4 (Lemma A.11 11 of Foster et al. (2021)). For any distribution P and Q on any space X, we have for any function h X + [0, RJ).
Ep [h] - B-[h]| s (2)(E((N)+ (b) Q)
In particular,
Ep 3Rq(n] + 4RD (T, Q)
Lemma B.5 (Strengthened Freedman's 's inequality (Theorem 9 of Zimmert and Lattimore (2022))). Let X1, Ny...., Xy be a martingale difference sequence with a filtration F1 C F2 S ... such that F.] < oo almost surely. Then with probability least 5,
E[X, F and E X
2 max (max(UU, VT} (UT)
2 max (UT, VVT)
Σ X, < 3/
Vr log
2UT log
6
where Vyr = ΣL= E
F.) and Up max(1, 11 maxte(r) X,I).
C Omitted Proofs in Section 4.1
Lemma C.I (Theorem 15.2 of Lattimore and Szepesvári (2020)). For any integer A 2 2, any positive real number
[0, 1), and time T > there exists context space X and a contextual bandit problem F c (X' x A + IR) with action set A = [A], (F; = A, and variances S a for all t E [T] such that any algorithu will suffer regret least A()
16

---

Proof of Lemma C.1. Without loss of generality assume < 1/2. Fix the algorithm. The first lower bound construction follows the standard MAB lower bound. Let the context space X 0 and the function class
F (-((()) = (o
iie --- + 1)),
where the gap & will be specified later with the constraint S 2a. Let P.. Pt.e. and Pa. defined as in Lemma B.I. For any functiin f F. suppose the environment such that if f(i) = σ o t - then the reward distribution is Po. P Pe. respectively. Any environment and algorithm give rise to the distribution of history. Let IP; denote the distribution generated by the environment following fa F together with the algorithm and expectations under P, will be denoted by E, Let (a) -'= 1(a a) where ar is the action taken time step for & [T]. Let
8" arg min E (N)
1>1
Since Σx= (i) = T, it holds that E, (NT(P T/ 1). For the two environments induced by fi and fir we have
1).
Ts
and 2 (Nr((1) > T/2) Ts
E [ 2 (1) < T/2)
2
2
Then, by Bretagnolle-Huber inequality, we have
Te
E, [Rr] + E. [Rr] 2 (P (NT(11) < T/2) P. (NT((1 T/2))
2
Te
2
Dep P:))..
4
Then by the chain rule KL divergence and Lemma B.1, we have
4T
(PI Pp.) = EE [ [NT( (Poc P.tt) - -A-18 (A-1)a2
Thus have
Ts
4T
E, [RT] + E,,- [RT]
exp (
4
(A l)0²
Then by choosing
E 1)02 we have
max 2 2(Vo2AT)
Lemma C.2. For any integer N, N,A. 2 2, there exists context space X and a deterministic (o, for all E (T) contextual bandit problem F. C (X A R) with action set A [A] and
datu N(A 1) such that any algorithm will suffer regrel al least Mmin (T (T/N /N, ANJ).
(E(AA) with the space of contexts X' = (,( ...)) and the set of actions A = [4]. For any i E [N].j E [A-1], the function (() defined as the following: For í E [N] and j E [A - 1).
Proof of Lemma C.2. Consider the function class F = () U (f(.))
(z .. = 1,
pa (x, k) =0, 0,
Vk E [A 1J (i). Vr + 10
(z,) Ax 2'
1
Vz.
Meanwhile
((0) (x, 0,
Var and Vj [A- 1]
((0 A) = 2'
Vz.
17

---

The eluder dimension of this function class is N(A - 1) since f(..) is uniquely identified by its value on (z( We assume that 2, is uniformly randomly chosen from N, and = f (2,, az). That is, 02 = 0 for all E [7].
Fix any algorithm. Denote by Pu the probability distribution when f = f( and Ey the expectation under Po. For any E [ [A 1), denote by ((.) the probability distribution when f = f(6)
and ((t,) the expectation under P(s.))- Let Nr((,) = Σ 1[x = x00), ae = j|. Then the adversary decides f. based on the following rule: if there exists E [N],] E [A - 1] such that
1
Eo [Nr -
(8)
100
then let f. = f(.i). If no j satisfies this, let f. = f()) If f. f(0), then we have
Ey Eo[Rr] Z 2 [E(N]JELA-11
1 Bu
Σ (1.1)
N(A 1 1)
min Ey (i. 2.j
N(A 1)
2
200
On the other hand, if f. = f(b then we have
99
Po(NT(i,)) = 0)
100"
Then by Lemma B.4, we have
Po(Nr(i,,) = 0) I 3P (o.) Then by Lemma D.2 of Foster et al. (2024), we have
0) + 4D (Fo))
Dj (Po. (()) S (i..)r
Altogether, we can obtain
(N.))
= (Po(Nr(i.)) 0) 28Eo|N 2 1/6.
This in turn implies that
T
T 2N (o.)(N
T 12N
E(G,)) [Rr] 2 (u,)
[2t = - Σ 1=1
2
=
Combining the lower bounds for Bg Rr and (n, finishes the proof.
Proof of Theorem 4.1. A T and d > T, by Lemma C.2 with N 1, we have lower bound ((T). Below, we assume min [A, d) <
In order to prove the lower bound, we only need to show that for any fixed d, A, a, T such that min(A, d} < T, there exists two classes where one has lower bound 0(v022 min (A, dfT) and the other has lower bound Qmmin((, VAT)).
If A < d, then we invoke Lemma C.1 obtain the lower bound of o2 Else if d A. can again invoke Lemma C.1 with the action set [d] and then expand the action set with dummy actions with all 0 rewards to obtain the lower bound of ((Vo2dT) In all, we have shown that there is a lower bound of 02 min(A,d]T).
If < (which implies d T since we assume min(A, d} < T), then we invoke Lemma C.2 with N 1 with action set AA be [d] plus A - d dummy actions. Then we get lower bound of Q(min [T, dT) (dd). Next, consider the case d 2 A. If d & VAT, then we invoke Lemma C.2 with N d/A and obtain lower bound of Q 2(min(AT/dd /d, d)}) M(d). Else we have d > VAT (which implies T 2 since we assume min(A,d) < T). Then we consider the hard case from Lemma C.2 with N = VT/A then the function class has Hellinger eluder dimension /AT. Embedding this function class into more complex model class with a larger Hellinger eluder dimension, can obtain the lower bound of Q( A(VAT). In all, we have shown that there is lower bound of (min v AT)
Consequently, have shown lower bound of (2 min(A, d. min VAT)).
18

---

Algorithm 4 Prod-based online regression oracle
Input: Parameter 7). Contextual Bandit Oracle gives function class F, C F, action class A and context dy at round t. Contextual Bandit algorithm which takes online regression oracle and returns action.
1: Let qi (f) = 1/17, for every function f E Fi.
2: for 1= ... do
3: Generate
(e( Σ (a()s SEF.
4: Output (f((z,,)) a E At), and feed to Contextual Bandit algorithm to receive de Ar.
5: Call Contextual Bandit oracle to get Fi+1 and 7++1-
6: Calculate
Eef) = (af(r ar) fel2,, (t) -r))
(10)
7: and
all n(((())
(+1(f)) Efefun
Ef Fet1.
(11)
D
Omitted Proofs in Section 4.2
D.1
Analysis of Online Regression Oracle
Lemma D.1 Desa-Bianchi et al. (2007)). Fix some positive parameter > 0. Suppose we have function sets F1 F2 ) .... Fr, and functions & F, R satisfies that (]) S 1 for any
f E Fr. The prediction rule
(1 11-n--n (1)
f Fe Ft. f Fr.
(e(s) =
Eeen, (1-6((-
0
ensures for any 8 Fr,
Σ 1=1
Σ (f(()())))
T Σ t=1
4())
log F
+11 left)²2
T
JEF
Proof. Define w/ (ʃ) = IT - (()( and W. = EsEr, we())
W. log
ΣYET, wi())
log
W,-1 ΣSErL Wt w(-1(f)
Σ)Er, WT W
< log
Ejen, Wi-1(s)
( log
Σ (e(f)((nFlafi) ml((f))
JEJ,
ii log
Σ a(NG()
1
SEF.
(xit)
(F))())
FEJ.
where in (i) use the definition of qt, in (di) the fact that ΣtEr, q(()) and in (Hit use the inequality log(1 x) S x for any x 1. Therefore,
Σ (()4()) 1= FEN
Wo log
17 WT
19

---

(0)
log F
log WT (f*)
log
[F]
1 T
log(1 - n((((f)))
17
17
t=1
log
[F
mf(l)) - -177)(())))
17
"
log
[F +
Σ t=1
((f)) + Σ ((fr))
7
where in (i) we the fact that Wo |F| and Wr wr (f*) for any s E Fr, and in (ii) use the fact that n)(((S*)] S and also the inequality log - x) 2 x x² for any |ac| S 2.
Lemma D.2. Suppose for any I E &. E A. E F, we always have f(x, a) E [0, 11. the reward E [0, 1] and for any f.f f E Fi we always have
max (f(z, a) ( ax), a
aeA:
Then for the output ft according to Algorithm 4, we have with probability at least 1 - 6,
T
)( rr,²²
E(M(s)) rz)² S 16(0² + Δ) log (1F1/8).
t=1
Proof. We first notice that with our choice of 11 [[++A] for any f Fr we have
2Á
n&(() S 2n)f(xz, a.) - fe(f,, az)l < 2n max If at) - (2t,
<
P'Et
1(0² + Á)
2
where é, is defined in Eq. (10). According to Lemma D.I, we have
ΣΣ (((E(())))
T
log
+ > E002
1=1 JEN
1=1
By the definition of fü in Eq. (9) and E, in Eq. (10), we have
Σ (())(())2((f((()))) rr) FEF
Σ
(f) -(((x)))))))) 0.
JEF
Next, we observe that
(f)( E((F*) = (t) - ro)² (felxe, ac) -f (x2,
which implies
Σ (f((za, rra}² - -
T
- ((()) -(((erraa))) - (xte
log F + 4n
T
T
EiPP (fr((e, - a.)).
(12)
t=1
We notice that
-f) ?(f*)= [[U))=)(((aaa)-F>aa))))) (x)
20

---

is a martingale difference sequence, and we further have |(((f*) - 4 and
Var, (ar,(4,(f*))) - 4(fe(1r; 0z) - (2,, az)) (,)) 'B,((r+ (x, 4(f((Ir; - (I a1)
(x,, ()) az)) az))
"B,((r= (
Hence according to Freedman inequality (Freedman, 1975), we have with probability 1 - 6,
T Σ &1P 2
Σ (()())) (M) log 2 4-2 log
1=1
Σ (Felze, (1),, 0009222-$21100 log 5 + 2 4 log
s 21
T
Σ (Je(zs, - (Mr, ( 12 log 8¹
where in the second inequality we use the fact that [f(( a.) inequality we use the AM-GM inequality. Hence, with our choice of r 1(0²+A) we have
- - (z,, ax) - Å, and in the last
T
Σ (f((z))))) - - (x) -r))
1=1
log [F]
+ +4n > Eftt/² - T
T
(fe(ee; ff (x))))))
x 1
t=1
t=1
S 4(002 2 + Å) log FF + 12 2222log
log 8
F
S 16(0² + -) log
where in the last inequality we use the fact that Á < 1.
Lemma D.3. Suppose for any I E
E., we always have f(r, a) E [0, 1], the reward
r. E [0, 1] and for any f, I' E Fo we always have
max (f(z f'( S
aEA:
Then for the output fo according to Algorithm 4, we have with probability at least 1 d,
T
Σ E p((o)(f((mna)) (z(2 s 4 (2)F1/8).
+
aEA
Proof. We use F, denote the filtration constructed by F, a a1st, r1:1). And we let
M₁ (fe( rT)² ( r
Then we have |M| < 2Â. According to (Foster and Rakhlin, 2020, Lemma 1, Lemma 4), we have with probability at least 10--/1 8/2,
2 Σ Σ (((a)(f((zaaa) - (I), <2 Σ ()) (z) - + 16Â log
5
1=1 AEA
Next, according to Lemma D.2, we have with probability at least 1-8/2,
[2[FF
- Σ (1i( - rx)² (f* (at, ar) - rz)2) < 16(0² + Á)
21

---

Hence we obtain that with probability at least - 8,
E
p((a)((((2saa) - (22, 48(0² + + (2|F1/8).
DEA
D.2 Proof of Theorem 4.2
For simplicity, we define the following sets based on Algorithm I:
T = { [T], 'if" condition in Line 6 holds in Algorithm 1}, and To [TT
(13)
We first show that with high probability, the true model f E Fi, where F, is defined in Eq. (5) in Algorithm 1.
Lemma D.4. When the function class Fe iteratively defined in Eq. (5), with probability at least 1 have f E for any 1 S t T.
Proof. We will prove the result by induction on For 1, since Fi and according to Assumption 2.1 we have f E Fi. Next, we will assume that f F and attempt to prove f E Fr. Since v, = (Tr,, 07) + er for any r S 1, we have
Wy (felor a,) f'(x, ax)
Σ Wy (Je(Er, -r7)² Σ wr (f)
+ 2 w (r((((T::a) (x+; (x+,
2
Σ w (f((,,(( - (x,,
where the last inequality uses the definition that is the minimizer of Σ w/ (+(((xxra)) r2) in (6).
We notice that w- - (x,,, de,, is martingale difference sequence, and since |w, S
g2.
1srst-1 [w=((f(E,, (2), 02
max
T (wr(f((r (fe(() (r) - (2T, < πe¹
According to the Strengthened Freeman's Inequality (Lemma B.5), and noticing that EE,- = o² for any 1 < S t -- 1, with probability at least for any f E F.
w. e, E, (f((z,, 0.) - (x),
F
(x ()) log F
3
Σ
(f(z,))))))))) (x
+ 2 max
[
da²
15r5(-1
502
T=1
< 3
Σ
Wy (fr(((r,, - (xr, sup -f
rSt-1
22

---

(1)
3
my (Je(t,) a,, sup
Σ
wy wo ()((((a))))) - (x)))
rst-1
#=1
$ 5
W ([((((T; (I,,, (4))2, L
2
Wi (Je(IT, (M (+)) +51L,
where in (i) we use the fact that Wr S 1/82 for any 7 according to the definition of w, in Algorithm 1 and using the definition & 1FTT 0a in (ii) we use the fact that
E (s(Js(Tss -- (x,, a.)) (f+( (T
WF
according the definition of w, in Algorithm since fr, Fr by induction hypothesis, and finally in (iii) we use AM-GM inequality. And this proves the induction hypothesis of f E Fr.
Therefore, we obtain that with probability least 1- for any IT Fe
The following lemma is useful result of Eluder dimension.
Lemma D.5. For any X 2 0 and E (0, 11. we have
T
(f(z,, ar) f((z,,
Σ min {
sup J.F'F aT E (f ( ('(x)
S detu(a) (A log
Proof. This proof follows Lemma 5.1 of Ye et al. (2023). Create bins, and call them Bı,.... Br Each bin is empty the beginning. Below we will add elements in (1,2..... T} to the bins.
Suppose that {1, 2.... - have been assigned to their bins, To assign t to a bin, we find the smallest n E [2'] such that "3e 2 or, (Ix, ae) is e-independent the elements in B, with respect to F.." We let n,, to be the we found, and put element i into bin Ba
By the procedure above, we can conclude that for each t, "Ve 2 a. (Iz, az) is e-dependent on all of [By...,Bry Bm.-1} with respect to F,." Next, we show that this necessitates the following: for any F.
ff S a² +
(((e,,))) (7) E The - Tm1
This is because if otherwise, then there exists f.l' E F, and bin Bn E (BI... ...,, Bre which (Iz, at) e-dependent on 2 a, but
(f(xe, ar) (x(, > Σ (((E,)))) (x)r
TEB.
Choose
{ max max [f(r, -'1 a.
TEB
Clearly, (x - f( a, )I E for all Bn, but f(z), (1 adl > a, contradicting
that (zt, as) is e-dependent on B, Ve 2 1/VT.
We obtain that
(f(2,, a1) f1 a)))
1
sup f.FEF, aT + (f( ar) ) - 1- (2(r
nu
23

---

Let [Bi]..... |r] be the size of the bins after all elements are added. By the eluder dimension definition (Definition 2.1), we know [Bal I dat((a) for all n. Therefore, have
(f(z,, ar) f((r, E. 1 +
min X,
sup
( (r),
Σ
Σ
n =n n-1
(a)
I Adelu(a) +
n-
s (d) + detu (elu(a)) log T.
Lemma D.6. Suppose we have positive number B such that for any E [T]. wi E [0, B). Then for any À 2 0, we have
We Wr 01) f((,,, ar))
Σ min X, sup
f.f'F,
Σ W- (- (f(T), - (+)))
S 3datu (1/ (A) + log T) (og(BT).
Proof. We define T; { [T] 2 S we S 2 for any 1 S s log(BT). and To = (t [T) wi E 00, 1/T]). Then we have
T C LOO(BB/A))T
Additionally, we notice that for any s log(BT) and l E Tr, we have
We we(f(xr, ar) - f' a1))
1+ Σ w (f( a7) (T a7))
wi wi(f az) - 8 (I,, 0t))
1+ LIT, w wf - (1, a2))
(1)
(f(z,, at) f (1),
22 2 1/(2//T) + EreTure
- f((x,
(1) < 2 1/B + EF (f a7) f'((",, a7))²
(f(r) 1- (1),
where in (i) we use the fact that for any E Tú, w, 12'-1/T,22' /T, 2TT2 and in (ii) use the fact
that PTTT"s S B. According to Lemma D.5, we have for any Si S (Bg(
(f at) - at)) S.PEF. 1/B E - a))) }
Σ min X, TET.
S detu ddtu(//BB) + log (Ta))
(A,
S ddan log T).
Next we notice that for those i To. we have we S 1/T, which implies that
Σ EET.
X, sup FRE, 1 Erer W (f - 1000---'-aa f' aT))
wi(l(xe, az) (' uz))
2 1/7
min
T
we wr(S(ar - (
min X, sup
f. 1 - WT (f (f 0,) ft (I,, o2))
1=1
< 2deu L/VBT)(A + log T') log( BT) + 1 < 3d LLV + log?) log(BT).
24

---

Next, we present lemma bounding the single-step regret in terms of It defined in Eq. (4) in Algorithm Lemma D.7. Suppose f E Firor any 1 STST. For any 1 S t S T we have
(z,, - (x,,, ax) s 21vL max (a
max aeA:
a
Proof. In the following, assume f F, always holds. Let
a arg max max f(r, a).
aEA. SEF/
Then we have
max a.A,
f (xt,, a) - (2),a1)
(4)
$ max f(Iz, at - f az)
TEF,
max f(z,, (00)) fEF,
min ) + min fIx,, a..)) SeF.
max ( 01) + max f(1), - f (2t,
JEF.
feF.
JEF.
max max (f(z; (1 a)l + min f(z,, d(bb)
max f(z,, az) Eef.
1.f'Et aEA,
fet
(1))
< 2 max max a) - (z), E.f'FF
(111)
a) Erer We (f((f 0,) a,))
21 max max I.EEPLEAA
VL.
E Here in (i) the fact that f E Fi, and in (ii) we first use the definition of A, in Line 4 of Algorithm that there exists f E Fi such that at = max.e. f1 a), which implies
min f a.e) S f (ob) f f' a.) FEF
max fIz, oz). JEF,
In (iit) the definition of Eq. (5) that for any f.f' E F.,
1
W wr(((zr,a)) - az),) < + 102L S 103L.
Our next lemma provides an upper bound to the expectation of regret for rounds falling into TT.
Lemma D.8. Suppose f E for any 1 1 < T. We have
d
Σ (max f' (x,, -f (z aEA
deunl)
A
TE
where we use Ô to hide constants and factors of log (2AA.
Proof. We first define M log AVT and 8 21 and recall the definition of g, in Eq, (4).
If(z) a.) - f' (1))
(a))))
sup f.F'F,
Σ wi (f a,) f' 1)2
In the following, when with no ambiguity, we write ft ((t). Since for any ʃ E F. we have [(x,, a) E [0, 1]. we have [gi] S Also notice that for any Tı, we have gr 2 A according to Algorithm 1.
25

---

We further define subsets Tikk, T12h C [T) for every h = A 2" with = 0, 1,
M - 1 as
1
TIk - [1: h s s 2h} n
Uz = ( ::u:
1
and Tian - [t h h g s 24 n
t : wi +
0²
Since A S gt S for t Tı, we have
M-1
M-1 U THE U T1 1=0
T
(14)
1=0
Next, we h, we analyze Tish and Ti2a separately. For those Tikoo we have:
Σ
(max (" - (x))
dEA.
[s a1) - (xx,
Σ min
1,3 max f.f'F
V Eret wt (f(x), - (1,,,, az))
tETuI
(at)
Σ
min (1,81,
(38)
[1 23hh)
where in (i) we use Lemma D.7 and the fact that [f" fxx a')l S 1 for any action a, a' E A. in (ii) we the definition of ge in Eq. (4) and the simplification Ot = ge (a,).. and in (ih) use the definition of Tie that for any & E Tiik we always have gr. S 2h. Next, we bound the cardinality of each Tiks
Tinl
(
Σ
(g: 2 13 { W: σ²
1
DET
(40)
min (h, ge (wu 1/2
11
Σ BETT
(168
h
min
[wigt
h tET
(wv) σ V TTunl
h2 ( wig?
Σ TE
min
h
(
/ Trunk
Σ min
122 o²'
we we(S ar) 8' a.))
sup S.PEF
h
I E Wr (f((( (f ar) - -
TET
(vi)
(x=
12 log
T o²
h 3/t ddei
log + o²
where in (i) we use the definition of Tisss in (ii) we merely use the inequality that 1g 2 h) < min(g. h) for any h 2 in (iii) we use the the fact that I[w; 1/0²) S Vwia since Schwarz inequality, in (v) we use the definition of in Eq. (4), and finanly in (vi) we use Lemma D.6 with À = h²//² and also E (0, 1/A.. Therefore, we obtain that
We S 1/0² always holds, in (iv) we use
33(0ll0g h2
oo2log + +1)ds dotu
T
ITual $3
log
VT
o²
which implies
Σ (max fd (12, f (2), aeA,
26

---

o
oollog +
T
s min (63h, 3)
detn
log
h
T
6,80 log
T
+3)
detu
log
h
VT
0
126o log TVL +3)
T
detu
log
h
02
Next, we will deal with those in Tiza. Similar to the proof for Tik. for any fixed h we have
Σ (max aeA, (" a) ( ax)) S min 2
(15)
LET12h
And we can upper bound the cardinality of Ti2a as
[T22l
Σ
[m
1 2 h1 wt +
11
1ETi2a
1
11 Wi # gzl
Σ
min
(h, g
h
teTiah
(8)
If at) (x),
1 I Iwu wi * o²
min
h sup f.f'FF V Σ1-1 w- (f - ('(,
tET12h
(it)
W. (z., ar) a+)
min h, VL sup
SPEER 1+ Σ1=1 w/ (f(zz, a,) (zr,
tETiZA
(bi1) 3
(xT) (VIlog T h) log
delu
h
02 (2)
where in (i) we use the definition of in Eq. (4), in (ii) we use the definition of that when We # 3/0", we always have
I+ wr (F(T(rr, f((xT, 17))
W1
min f.P'T
[S(x), a.) a
and (tii) according to Lemma D.6 and the fact that w, [0, 1/02]. Therefore, according to Eq. (15), we obtain that
Σ (max (*1,, I (Fa,, min (1,231))) (T Tiza
rEA,
Tiza
s (6.3 T +3) delu
σ
log
VT
T
(126L log T + 33 deta
log
Finally, recalling Eq. (14), if we sum the regret obtained above over h, we obtain
Σ (max I ("((,, f (x)) aeA.
M
max ( ((xr YEEA
Σ
max (" -M(x,
0=0
IET (ETII(a
(ET
M-1
deta delute detu log I
(2'
(using det 2 deta(1/T2) from Section and the fact that (ata(a) is decreasing in a)
27

---

- ( (f-dduvzz + daul). A
Finally, we provide lemma which upper bounds the expectation of regret for rounds falling into T2-
Lemma D.9. Suppose that for any E [T], we have S E Ft. With 11VVI, we have with probability least 6,
[4/F]
3 3log (2)
2 5
Σ (max f (x), -f (111) s 16 (02 + A)Tlog 1ET2
Proof. We let oz = arg max, S (1t, a). According to (Foster and Rakhlin, 2020, Lemma 3), we have
24 Σ ((la)(((mn - f" & aEA
+
Σ
pe(a) -( (T(,),)))
?
aEA
Summing this inequality up for all E T2, obtain
ΣΣ Pola)(f - ax) TA
Σ Σ p((a)(f((s(aa)) - (f))))
7
RET2
tEA
We notice that for any / T2, have
If a) (x),
sup max f.E' REA
SA.
VI+ W
W. (f(:,, - (T);
According to the definition of Fú, for any f. Fi.
Σ
1021,
which implies that for any f.f F..
f(z,, a) f'( AVI+ 102L < Á.
max aEA
Hence according to Lemma D.2, with probability at least - 8/2, we have
Σ Σ (a ( < 48(0² Á) [4[F]
t=1 aEA
Further noticing that [Tal least 1 - 5/22,
< T, with choice 7
4(A (A+a2)) 1(Ato))log(([11)) we have with probability at
AT
ΣΣn (x,, - 100---(aa (x), s 4 A)T log TE aEA
4|F]
8
Finally, since we always have < ft at) (1 a) S 1, according to Bernstein inequality we have with probability at least 1 - 6/2,
Σ (1" - 8t (x), 1ET2
-E E Ce(a))( - (xz, a))
LETa
Σ ΣEploli ((la)(((anaatt ft a)) log (2) + 2loog aET
2 (/
2 V
28

---

+ 3log (2) (
$ ΣΣ E (Z)))( - (2), REA
ff (z,, + 3og 2
(7)
E p((a)(f(zx RET2 REA
where in the second inequality we use the AM-GM inequality and in the last inequality we use the fact that (T(, - (21, a) S Therefore, we obtain that with probability least 1 8,
pr(a) oz) - (*t, log (2) 8 LET2
Σ (17 - (3t, 2
Σ Σ
$ 16 (02 A)T [|]F]
2
+ log
Proof of Theorem 4.2. Lemma D.4 and Lemma D.8 gives that with probability at least - 6/2 we have
(max (21, a) (x2, =Ō ( ( aEA
Σ
+ dduul))
A
ET
Additionally, according Lemma D.9, have with probability least 1 - 88/2
Σ
(max I (Ix, a) f ((ra,))) s 16 (o2 + ÅyTL + 3T. aEA
TET2
Hence when A = o² 22/(11VD)) (so Á = o²), with probability at least - ô, we have
Σ (max f - (x( aEA
-
1E/2
Σ (max ( - (rt Σ (max ("( -5 (x11
aEA
aEA
LET
LETs
Ô (VoRATL + L.
2 Then noticing that L = log
0²8 and that AT 1 finishes the proof.
E Omitted Proofs in Section 4.3
In this section, we will prove Corollary 4.1.
Proof of Corollary 4.1. Based the variance of at round t, Algorithm classify rounds into "o. ... Tio T- We will bound the regret of rounds T, separately.
According to Algorithm 2, for E Ta with S S log(AT), we always have 1/T7 S or S ATAAT. Hence, according to Theorem 4.2, with probability at least 1 - 5/ log( AT), we have
(max I' (z), (", a.)) (z)) = aEA LE
(VATTI) (2)(())))) ( log
[F
deta log
))
[F 0
We further observe that for s < log(lo)))))))) of > /AT which implies that
[Til (2 (AT))² Σ oz.
TE
And for 0, we have
[T||- (2' <T (AT)² <
AT
29

---

Therefore, with probability at least 5, we have
T
max aEA
(" a) f (x), ai))
t=1
(OR(AT)
F
[
Σ
AlTil (2'((())2) log
+ detu log
1=0
(AT))
[F
[F
Σ
A
a log
+ detu log
E
TET:
logí log(AT)
[F
[
log(AZ))
A
of log
+ deta log
8
LET:
T
of log (1F1) + detu log
A
6
where in (1) Cauchy-Sene Seach--Schwwrz inequality.
30

---

Algorithm 5 VarUCB
Define: L =
Fo Fo
2: Define: K _ [lo 7. Let 11 = 0 for =, 1,2...., K, K+ +
3: for tort= = 1, 2.... do
4: Define confidence set:
Fi 7
f 1=1E22 SE vk & JEVe,t
Σ
(F([(Er; (x)( Plkk Pii)) j)
where
Jr, = arg min fEJ TEV.
Σ ar) - -r=)² -r+)²
(16)
110.2-4 2- V
V Ereri wZ(r= (L,((Er,=)))21 12 if & K and 2 > 80L
BI,k=
if v K and 2 < 80L
5: Receive Tt, and define At = Ea Bf arg mag (xx,
6: Define
If a) - (x),
9t.k
max S.f'F,, 2 24-2h Erev., WZ ar) (2,
7: Let k be the smallest h E [K] such that Aax (t, 2 2
(Let k = + if such hy does not exist)
arg a. It,,, (a)
if K
8: Play a, arg ma max f()
and receive Tt.
otherwise'
9: Define 9t = 9t. (a.). Let ue = 2- / if k,
< K and Wy = 1 k, = K + Update 1/+11, Ve,, (t) and 1itkk V for k + ke-
10:
Algorithm for the Strong Adversary Case and Omitted Proofs in Section
F1
Upper Bound
In this section, we introduce and analyze Algorithm 5, an algorithm that achieves (detu v log [F] detu log FF) regret bound against strong adversary.
Algorithm 5 is an extension of the SAVE algorithm (Zhao et al., 2023) from linear function approxi- mation to general function approximation. The algorithm maintains K + = O(log T') bins denoted 1] (i.e., every time index < t
as { ( k 1.2..... K + 1, which forms partition of falls into exactly one of these bins). Each bin & can form a confidence function set like in standard LinUCB using samples in L The overall confidence set F, is the intersection of the confidence sets individual bins (Line 4).
Upon receiving the context Ie, the learner form an active action set that contains plausible actions (Line 5). The next step decide which bin & should go to. This is done by leveraging the uncertainty measure (a) for bin & and action a (Line 6), which measures how uncertain the reward action is, given prior samples in bin k. The measure (a) corresponds to the quantity ||a| usually seen in linear contextual bandits, where Σ,,e is the covariance matrix formed by the samples in Vr,A- The algorithm finds the smallest & such that there exists an action with relative large uncertainty (a) 2 2 (Line 7). The learner would then choose this action in order to gain relatively large shrinking bin k's confidence (Line 8), and put time in bin k. The sample at time assigned a weight We that is inversely proportional to the uncertainty measure (Line 9). This ensures that the importance of the samples within each bin is more balanced.
Before proving the main theorem Theorem 5.2, we first establish lemmas Lemma F. --Lemma F.5.
31

---

Lemma F.1. Suppose that f E Fi-1. Then with probability at least 8/T, for all k E [K] we have
Σ w (L) - $ 20.22-2 Te
Σ
w L
LE
Proof. Since T, = (2 a+) + we have
Σ
w a+) -f(())
Σ
w (+) -rt)²
Σ
wa (I,, -(r))
L.Vi
TEVe,
+2 2 Σ (F) -f - -f
reVur
2
Σ
w (f - (
(17)
TE
where the last inequality is by the optimality of ft,k given in Eq. (16). According to the strengthened Freeman's Inequality (Lemma B.5), with L C (1 for some large enough universal constant C (specified in Line of Algorithm 5), the last expression in Eq. (17) can be further bounded by
(foo((ee((TT)a))) (x+, + max (f - -xT, TEV.
Σ
reVe,
Σ ((oo(((((UTTaa)) -
ar a+), + max wr (e.t) (xT, a+)
reWe,
rEW.
(wo S 1 because 9r -t,ki (as) 2 2 ke for ls E [K], and leal s 1)
max ( (T) 5 (177 rEW.
Σ TEV...
wLofL+
(18)
for all & with probability at least 5/T by union bound over k and fr..-
For any Me by the definition of w, (Line 9 of Algorithm 5), have w- fr, (I,, (r),,a7)= - (xT,
2 //r 1f,, ar) (1T,, (x));a))
- / 2- E.EV., w2(f(Ir; - (xx:
= 2 min S,
(e (7) (2T,
[[(T) ['((T,
< 2 22 + Σ
w (f (x,,
SEV,
(f F C. Fy by assumption)
Combining this and Eq. (18), we get
Σ
(f.,(((Fr: ar) - --t (x),
TEW.k
(1
< -
max reV.
2 2-2h 2k 2
Σ
Σ WLOLL+L
SEV
TEV.
32

---

(1
I 2
12 12-2
L2+
L2+
Σ a( - -f
Σ
wFO w
TEVIS
Solving the inequality yields
Σ
(f(f( (z) ax,, 10.20-20 2-
Σ
o +
1,
TEVIN
Lemma F.2. Suppose that f Fi-1. Then for all [K] satisfying 22 S0L, we have with probability at least - 8/T,
Σ T
o.o 88 Σ w² (rrr-reesee (e)((r) +44,
58
TEVL.
Σ
Wey (r, (ex(err
22 Σ o L.
TEV.N
TEVe
Proof. With L, = C' F1T/88)) for some large enough universal constant C, we have
Σ
0 2 Σ w.e. +L
(Freedman's 's inequality)
L,
w (r+ or)) +4 Σ
w (f f (x)) +
< 4
TEVi,
< 4 Σ
w (r+ (e.(()r)))) 4
Σ
who L + L?
+L
T
TEW
(by Lemma F.I)
< Σ w² (r- (+)( + 21
1
Σ
o.
2
TeWL,
TEW.
Rearranging gives the first inequality. For the second inequality, note that we have
Σ ?m (rr fin(er)a)))
<
Σ w (r, f (xTra,)))
(by the optimality of fr.
TEV
< 2
0²O²² L.
(Freedman's 's inequality)
7EV..
Lemma F33, With probability at least 1- f* E For all
Proof. We prove by induction. Assume that f Fi-1- Then for all & E [K] such that 2 > 80L, by Lemma F. and Lemma F.2, with probability at least 5/T,
Σ ( - T
(xr, 2)) - 10.2 -00 10.2-22- 2k
Σ TEVLA
wo + L2
< 110 2-26
Σ wx (rr - (+)) 41?
TEWi,
33

---

For E [K] such that 2 < 80L, we bound trivially
Σ " (f (xT, | B
(WT S 1)
T.W.
In both cases, we have f E Fi by the definition of Fe. By induction, we conclude that with probability least 1 - 6, E F, for a.
Lemma F4. For l E [K), we have | I 0
Proof. For such that E [K], by the definition of wy we have
welf(rr ar) - (x1,
1 = ndt wigh = 2%
max SPEF 2 2h L + Erer... (f( a+) - f1 a2))
Thus,
Wel If (2e, a.) fl( at)l
MT+1A
Σ
min 1, 2 f.f'Et+ / L2 + Exer.,
max
ar) ) - -f ((or,
tEVT+1A
w ut) - (((,
= 22
min 2
S. 2 2-2h 222
max
Ereve, wf a7) (ITT;
1EVT+IK
- ((22k dola).
(by Lemma D.5)
Lemma F.5. For t such that 22(k;-1) 2 80L, we have
2h, f (xt, a) (x, at) - 200 --k (VAL + LL).
max
aeA:
Proof.
(" a) (x
aEA,
max [1e, (40b) ("1 ax) JEA,
(define uaeb = arg max maxzeF (()),))
max f(z,, (ubb) FEFi
min f(I,, dbbb) FeF
min f(I,, dleb) feF,
-mxx f ac) + max f(re, 1f (z)
feFi
JEF,
2 max [f(I, a) (1( + min f(x,, Heb) T.f'EF,oEA
max f(
IEF.
IEF.
x2 2 max max [( a) ('(
f.
(iz)
15 a) ( (x(t,))))
S 2 max max
1.f'EF.OEA 2- Erev.o w (F( ('(x), V5
2/5- max St.k, 31 aEA:
< 2v55 2- -i+t Be,k--1
(by the definition of k2)
225 k1+ 10 2 kkt1
wf(rr (I,, (. o1 L
TEVIANE11
(by the definition of 3r,s)
200 -222
Σ
WLo2L L
(by Lemma F.2)
34

---

< 200 (2
VAL /AI +2 2- 1..
(w, S 1)
(19)
Here, in (i) we use the definition of A, that there exists I' E Fi such that a, maxaeA 8 (21, a), which implies
min IEFt
fx, ( - (2, (4 S f ar) S max f(r, az).
JEF,
In (ti) we use the fact that for S, E Fr, K and 22 80L, we have
2 2k 22 + Σ (f(r,,)))) - (2 (z),
$ 81 +
Σ
Σ
(+)) (rsaarr
TEVe,
TEVe,
(by the definition of (r,k))
5,3,
(by the fact that f E F,)
Proof of Theorem 5.2. Without loss of generality, assume 22K 2 80L, which is equivalent to T 2 ((lo(((F)TT))). Notice that [T] U WT+1A
Bound the regret in VT-1,K+1- Notice that by assumption, for E VT+1,K41, we have 22(k--1) 22k 2 SOL. Thus, by Lemma F.5.
Σ
max f (xt, - -(((x,, < 2000 2- (VAL+ L)) aE
o T T x (AL+ = =0(1).
Bound the regret in 1T+1 with 2 2 S0L.
By Lemma F.5,
max f( -f( AEEA:
< 200 ITIAA 2-28
2B (VAL + L)
KE KEV
< Ô detu VAI+L.))
(by Lemma F.4)
= detu V A log |F + deta log 151)
Bound the regret in VT+i. with 22k < S0L.
Σ
max max (( - (x))
$ MT+LK
WEA;
< ① (22 delu)
(by Lemma F.4)
< O(dtoe))
Ô (detu log [F]).
Combining all parts proves the desired bound.
35

---

F.2 Lower Bound
Lemma F.6. For any integer A. 2 2, N CVTJA and positive number A > ANjo with some e S 1, there exists a context space X, contextual bandit problem F C (X x A + R. with eluder dimension deeu (F, 0) N(A 1) and action set A = [A), and adversarially assigned variances such that any algorithm will suffer at least M(min (vN AA, VAT)).
of.... ......,,.. . that Ei=1 of
Proof of Lemma F.6. E [2N/T,1] 1] be parameter to be decided later. Consider the function class F { U { (fth)) (E(M)EE(AA1] with the space of contexts X' {x(1)) ,.... xNN) and the set of actions A = [A]. For any E [N], j [A - 1), the function f(.)) is defined the following:
For E [N] and j E [A 1],
1
(x .j]
+ E,
2
(r,
or vk [A 11 (i). Vx + x
-
2
(x,) 2'
1
Yx.
Meanwhile
(x, = - 5, Vr and Vj E [A -
2
1 A) 2'
Vx.
The eluder dimension of this function class is N(A - 1) since f(hd) is uniquely identified by its value on (z(*), We assume that o, is uniformly randomly chosen from X, and r. a)) e0t, where
(O, 1) and og is defined in the following way. Fix the algorithm. Let Nz(ij) Σ 1(x,-
(z))) a, = j) for any X and the action b. The adversary assigns
or 1 (a, j, (e... S 1/E²),
that is, it assigns variance when the algorithm chooses action and the context-action pair Te, b are played for more than 1/e² times.
Fix any algorithm. Denote by Po the probability distribution when f* = f()) and Eg the expectation under Pu. For any E [N]. j [A 1], denote by ((.,)) the probability distribution when f (f.))
and (a,) the expectation under P(.,))- Then the adversary decides Sa based on the following rule: there exists E [N], [A 1] such that
1
Ep N (1.j) <
(20)
1000
then let ʃ. = ((.)) If no i satisfies this, let S. = (()
If f = f()), then we have
N(A-1 -11 1)
Ep Rr 2 g. Eo
Σ
Nr(i,)) 2 -NN(A- - 1)
min (oN (
1000s
[E|M]EE(A-1]
On the other hand, if f. = f(id), then we have
Po (NT(i.)) <
1
999
1000
Then by Lemma B.4, we have
po (i. < =2)
1 s 3P.s
(1, 21) +
4AD PT..)))
36

---

Then by Lemma D.2 of Foster et al. (2024), we have
7
(Po,, & 7Eo (NT(i, (1/E2)1 .45² = 250
Altogether, we can obtain
1 Pi Nr < 2² z 1( Po (r((,)) < (/8 28/250 2 21/6.
This in turn, implies that with the choice =² z 2N/T, that
B [TT] 2 e Bag Σ [s. =00
Nr((2 ,)i
28 8. (T 2)2 (is((N(()))
(T
Nr(i,)
1 Te
12N
Thus if v VAT AAA,, then we set v /NAA. We have & due to the assumption that A 2 AN/c. Then we verify
Σ
o
-, N(A- A.
Furthermore, VT ANAA implies TE/N AN/e, and thus
AN
Te
AN
sup [E(UU|[
E, 2 Ω min
((VNNA).
S N
Otherwise if VTT < AAA, then we have T/N S A and we set N / A/T. We have e S due to the assumption that S ceTT/A Then we verify
T
Σ o. Σ
1(
(163) ( S..
Finally, we have the lower bounds
LAN TE
: N 1) ((VAT))
sup
[. 2 Ω min
Overall, we have proven that
AN Te)) 1) 2 Ce(min(VNAAL VAT)).
sup (e(oU[[N]
E,[RT] 2 2 min
Proof of Theorem 5.1.
We first deal with some corner cases:
Case 1: If A T and d > T, then by Lemma C.2 with = 1, we have lower bound of ((T)).
Case 2: If A > T, d < T, and d > A, then by Lemma C.2 with N = and the number of actions in Lemma C.2 set to d, we have lower bound of ((d).
Case 3: If >> T, d < T, and d < A, then by Lemma C.I with the number of actions in Lemma C.1
set to d, we have lower bound of Ω ((dd)).
Case 4: If A < T. d > T. then by Lemma C.2 with N TT/A, we have a lower bound of ((VAT).
Case 5: < T, T. A, and d 2 then by Lemma C.2 with N and the number of actions in Lemma C.2 set to be d, we have lower bound of ②(d).
37

---

Case 6: A < T, d T, S A, and d > A, then by Lemma C.1 with the number of actions in Lemma C.1 set to be d, we have lower bound of (2 dd).
Now, we consider our main cases where A, d S and A. We consider the following two subcases:
Subcase 1: If d 2 ((vdA) or d 2 ((VAT), then we invoke Lemma C.2 with N min min(d/A, /T/A) and obtain a lower bound of (mmi VAT)) 2 Qmmin (vdA + d, v ATT)..
Subcase 2: If < ev dA and d < eVAT AT for a small enough constant 0 < < 1. Then we invoke Lemma F.6 with N d/A and obtain a lower bound of [{(min (omin((vd + d, VAT)).
Thus, conclude proof.
G
Omitted Proofs in Section 6
We revise the proof of Lemma 3 of Foster and Rakhlin (2020) to show the following guarantee. Lemma G.1. We have for any t E [T],
JM, inf max Eawp max fM a') - fM (x), a) -fm PEA(A) MEM.
A (1c)
x
(xc.
?
where M, (x2) = suPaEA RM, (IL, a).
Proof of Lemma G.1. Fix E [T]. Letq E A(A) be the policy such that
1
q(stt;a) X+ 7/00//0 M. (It. 0) (maxa'eA SM, (a),,a) fM, (21, a))
where À is such that EnEA g( a) = 1. We show that such À exists and À E (0, A]. Let
I(A)= = EaEA Xt7/a3,
A fM, (=(,a))-a fM,, aa) Then we have h(A) is monotonically decreasing with h(0) and h(A) < 1. Thus there exists À E (0, such that h(A) that corresponds to q(z,, a).
We first separate the regret with respect to any fixed M into four parts the following
Eawy max fM( a') far( [3]
= Bang max S ( d') SM, (Xe,, a)] + Eang (xt; a) - S'n, (1e, a)]l
+ (fMa(zt, faa (z),aa)) + (fM max fra (oe, (21)
where a* E arg max fas (2i, Firstly, by the definition of q, we have
max.'A SM, (Ie, SM, (It,
Bang max (Mr, d') - S (2t, wi]
Σ
X 7/0 (2t, a) (maxx'e SM. (xi, a') SMs. (x a))
aEA
R. (#t, a)
Ao (Ix)
S
(22)
aEA
Secondly, by the AM-GM inequality, we have
2 (fM a) (xr, a))
Bang (1t, a) - SM, (2t,
2
23, (Fi,
Tie (I),
0i (xx)
Eang
(23)
7
38

---

Thirdly, again by the AM-GM inequality and the definition of q. we have
fas( a²) - San, (x), a") (fM (xr, a²) ) SM, (x),
(2),
RM, (12;
7g(2,, a*)
+ 1/0//30 (I), (maxored SAA (Ie, (2,,
RM (20,, a*)
7
Ao (xt)
max a'EA
[.. (x S'r (3r,
(24)
7
Plug the inequality (22), (23), and (24) in the equality (21) to obtain the desired bound of
E Bang max fM( - (aa( (fAN a) - SM, (2), a))² Ao (rr)
x
M. (Fe, a)
7
Lemma G.2. Whenever I, and M MM we have for any action a E [A],
.. (It; S oi, (re, a) S o3 (xt,
Proof. Since for any M, M' E M, and E A, one has D (z,, a), M (Ie, & 1/2. Thus by Lemma B.2, we have that a (Ze, a) S a (2r, a).
Then since M is in M, and Mj mixture of models in Mr we have by the total variaene law 2M (Zi, a) S min or a) S o (Ie a) S max p a) S a. (It, a). MEM:
MEMs
Lemma G.3. Whenever 1, and M Mr, we have for any action a E A
Is (11, a) - SM. (2'4 a)) S Vohn. (me, (M (ar, a), (M(
Proof. Since M is M, and M, is mixture of models in Mr, have for any action E [A],
Di (MMM*aaa (I) Mz & max
DH (M(M"(r,, a), M(x, a)) $ 1/2.
MEM,
Then by Lemma B.3, we have that
far (Ie, a) - fa4 (I1, a (Zr, + (a Then by Lemma G.2, we have
Ifa- (Ie, a) fan, a)l S (ohr + (,
S Voh a)2 a), M, (2,,
Lemma G.4. The regrets accumalated on rounds where I, 2 are bounded with probability least
1 - 8 by
T
T 2 (xt) log((M)/8)
reg, 144 = S
A
where 23 (xx)
suPae Jr (Ie, a) and reg, Hanps mmaxo' far (ar, a') far (I), a)].
39

---

Proof. Let Es|-] == E[- Hil where He is the history up to time t. By Lemma G.1 and Lemma G.3,
whenever 4, 2 and M E Mr, we have
( (max far (201, a') far- (B1, 1M eMa]
Eg(reg, (7, M E M.)]
Bawps
(JM- () (ae, 10M E Mi))
A (x1)
a)
7
Ao (21)
2 >Baar
Me(are, a)) 1(M Mi)) +
?
Then by summation over / E [7], we have
M E reg, 11, = 2 E MM)
t=1
Mr (I+)
T
+7
Σ
Bump, [PR(M a), M1 a)) 1(M* E M.)]
Then by Lemma A.15 of Foster et al. (2021), we have that with probability at least - 8/2.
T
Σ
Eacp
(I,,
1(M E EM.I] s log(2)MM188)
1=1
T
Then by the choice of y
A
Σ
M. (ggg//og(2[M//0) we have with probability at least 1 8/2,
T Σ
(xt)
1=1
+ 7
Kanpi DHH(M Me(sa,a)) - 1M E M.)]
7
1=1
T
Mi (are) 1og(2)MM/88)
hr (x²) (og(2)
where the second inequality is by Lemma G.2. We also have by Lemma A.3 of Foster et al. (2021) that with probability at least - 8/4, for all E [T].
Σ Di az), Mc(2., a.)) s
3 Σ EE Eawp, [D] (Z' M,, a))] 1log(8T/0).
2
By union bound, this implies with probability at least 36/4, for all & [7]. M e M, Again by Lemma A.3 of Foster et al. (2021), we have with probability at least 1 - 6/4, for all f E [T'
Σ reg, reg, 1(4, = M E Mi)
B. 1(4 = M, e M,)] + 4 logg 188(8888)
Thus by the union bound, with probability at least 1 - ò, we have
T
T
reg, 11, 2) Σ
Σ
reg, 1 1l. = 2, Mi)
t=1
T
S
o h (Ix) log(LM)/8).
40

---

Lemma G.5. For any X 2 0 and a > O, we have
T
(M 0z), M (xt,
min X, sup
dolu(a) (A log T).
M.MEM. RT + --1 Dj (M (M a7), (x,,
Proof. The proof follows similarly from the proof of Lemma D.5 by replacing the square divergence with squared Hellinger distance.
Lemma G.6. The regrets accumalated on rounds where I are bounded by
T
reg 11=11
dth (a) + log(LM(1//6) log T
for any > O.
Proof. For any t [T] and M, M' E Mr, we have
Σ (M)
M Di (Mr, M (wo,) ) s S4L. (25)
< 2 Σ (M (+(T, +
T
Thus let Σ 11 = 1) = Ti and we have
rege (4= 3 11+=10 Tí.
Thus we have for any a 2 0,
Ti
1
sup M.M,
(z, (M,, (,) a.)) 2 2
1=11
1
<
2
min
V2
sup M.M.M.
ai)
1,=1
Du Du(M(a at), M (1)e
< 2 Σ
min
sup M.M'EM.
V + 4L
22
1==1
1aT +
E aM)
where the last inequality is by (25). Furthermore, by Cauchy-Schweer inequality, we have
Dn(M at), M (xt,
min
sup E.M,
Va²T + 4T.
22
1aT++ + Σ MM(
D (xe, ac), M'(x.,
<
/Ti Ti
Σ
min
sup 2' M.M'EM,
(a2T + 4L)
4=1
2T + Σ (
ar), M (IT
S V 71 dH (1) (a²T+ log
41

---

where the last inequality is by Lemma G.5. Altogether, we have
T S V Ti d dio (a) (a²T + 4 log
Reorganizing the above inequality, we obtain the desired bound.
Proof of Theorem 6.1. The proof forward by combing Lemma G.6 and Lemma G.4, i.e. with probability at least - 6.
T Σ 1=1
RT E
R- (2i)
log(I + + log((MM[T/6) log
Then, by choosing a = 1/VT, we obtain the desired bound.
Proof of Theorem 6.2. The proof of this theorem is essentially the same as that of Theorem 4.1. Recall that in Theorem 4.1 we construct hard instance for function class F that only contain reward mean information, but the reward has a fixed variance upper bound o3 < o². What we do here is simply embed this instance in model class M where for every model, every context, and every action, the reward distribution a Gaussian with mean as in F and variance a², Notice that can change the distribution Po., and P+ in Lemma B.1 to Ao e, o²) and N(o e, o²),
o,c respectively, which still gives us DKL (Pr,, Ptte)
20 o² This allows us to prove the same bound as in Lemma C.I. Furthermore, the eluder dimension (MM 0) defined through the Hellinger distance between models remain the same the eluder dimension (Jiu 0) defined through the mean difference in the constructions of Lemma C.I and Lemma C.2. Overall, the lower bounds in Lemma C.1 and Lemma C.2 are still applicable after we change the reward distribution from Bernoulli-style distributions to Gaussian distributions, and change the distance measure from mean difference to Hellinger distance. The arguments in Theorem 4.1 thus allow prove the same lower bound in the case here.
(2c) 2e
Lemma G.7. For any integer A,T N S T/A and positive number A ANje, there exists a context space X, a contextual bandit model class M C (X x A A(R)) with eluder dimension elu that 7' of < A such that any algorithm will suffer at least Q(min v VN NA, JA
dH (M. 0) = [(A - 1) and action set A= = [A], and adversarially assigned variances oi..... o7
Proof of Lemma G.7. This lower bound is based on modification of Lemma F.6. Concretely, we illustrate here how to embed the hard case from Lemma F.6 to an equivalent model class in the distributional case.
One can add information into the context for the hard case constructed in Lemma F.6. Concretely, we don't enlarge the function class, but for each context æ, the new context space will have A corresponding contexts (x, Si.. where the second argument will be used to record the number of pulls to each action a under context æ. The function value under these contexts will be the same as under the original context. The adversarial thus can choose in the new context space (Iz, N₂ (z,, 1)..,, N2 (Z,, A)) to embed the hard case from Lemma F.6. The Hellinger eluder dimension is twice the cluder dimension because there are two types of variances corresponding to each original context. Thus, we obtain the desired bound.
Proof of Theorem 6.3.
This proof follows a similar argument with Theorem 5.1, with only embedding the function classes to model classes. Again, change the Bemoulli-styled distributions in the construction of Theorem 5,
42

---

to Gaussian distributions, The only other more crucial difference lies in the Subclass at the end. We first deal with some corner cases:
Case 1: If A T and d > T, then by Lemma C.2 with N 1, we have lower bound of I2Z').
Case 2: If A > T, < T. and > A, then by Lemma C.2 with N and the number of actions in
Lemma C.2 set to d, we have lower bound of ((d)..
Case 3: If A > T, d < T, and d < A, then by Lemma C.I with the number of actions in Lemma C.I
set to d, we have lower bound of 92( ((vdA).
Case 4: If A T. d T. then by Lemma C.2 with N VT/A, we have a lower bound of AT)
Case 5: If A < T, d < T, d < A, and d 2 A then by Lemma C.2 with N and the number of actions in Lemma C.2 set be we have lower bound of (d))..
T, d < A, and d > A, then by Lemma C.1 with the number of actions in Lemma C.I set to be d, we have lower bound of (AVdA).
Case 6: If A T,
Now, we consider our main cases where A, d S and 2 A. We consider the following two subcases:
Subcase 1: If d 2 ((VdA) or d 2 ((VAT), then we invoke Lemma C.2 with N min(d/A, A/A, TTAA and obtain a lower bound of (mmin v VAT)) 2 M(min( + v VAT)).
dA and d AV for small enough constant c 0. Then we invoke Lemma G.7 and obtain lower bound of (mmnn VdA d, VAT)).
Subcase
Thus, we conclude our proof.
H Upper Bound with Zero-One Variance (Section 7)
In this section, we consider the setting where 0 or 1, and not reveal to the learner at the beginning of each round. The algorithm is displayed in Algorithm 6. We have the following theorem.
Theorem H.1. With the choice of v
we have the upper bound on the expected regrer of log 1og|
SA
Algorithm 6
B| = O (Alog) [F]
T 1+
of
+ A(del, + log [FI)
[=1
We will prove upper bounds for regret of rounds with a, 0 and a; separately. First we bound regret of rounds with ae =1
Lemma H.1. With /
8A log Vlogi2 the oulput actions ae at each round in Algorithm 6 satisfies
T
T 1
(((t,,a)-((aa) Σ I| = 1] max (* - [xx, (()) s 4 $
2A log [F|
Σ o
aEd
Proof. Based on the inverse-gap weighting update rule Eq. (26), similar to (Foster and Rakhlin, 2020, Lemma 3), we have
T
E
ll. = 1] (*(ar, a) (((ax,
43

---

Algorithm 6 Variance Sensitive SquareCB for Zero-One Noise
Input: 2
1: Let Fi
2: for do
3: Receive 2y, and calculate A, = fa E A: Fr. a) = arg max f(z,, a)}.
4: Sample action o, ~ Pr. and receive or and rt, where
for a E An for of A..
Pe(a)= 1100=1000 At
of(mux ( falaaa))
(26)
0
5: Calculate Le()) for all f E as
(f(Ir, 07) - -r+)2
T+(f) Σ
0²
7=1
where for those a, = 0, we define (f(a, )-r,,²
O (I, a;) = and oo otherwise.
6:
Calculate ()) to be
e-1(1)
(41(f) = e hi()))
7:
Calculate fe+1 to be
f4+ -
FEF
8:
if ou = 0 then
9:
Update Fi+1 (f E Fr, (() = =r).
10:
else
Let F(+1 = Fi.
T
T
< E
Σ (=1
1|, = 1]
2A
+
1
1+
Σ
o3
(f((z),))) - -f
A + TV
A
=1
For the first term, we have analysis
No: = 1].
o
2
A A+ 1+ E
==1
where the first inequality uses the fact that 0; E {0, } and when a; have
1+ 03
52 V 1+ 11 oz
V o?) For the second term, we have
03 (fe(z), (x))
1 Σ (f((z) - 1 (xIt
Σ of log F
where the last line is according to the analysis of Vovk's aggregating algorithm (Vovk, 1995; Cesa- Bianchi and Lugosi, 2006).
44

---

Above all, with 7 = /
844
log F
we get
T
1lo [[ (" a) ax),
2A
log [F
T
+
1+
?
4
1=1
T
1/
2A log [F|
1+
Σ
o
1=1
The following a useful lemma regarding Eluder dimension. Lemma H.2. We define
1 T
Z: = S f' E such that (f(x,, f
(27)
Then we have
Σ Ilo 0] S delalt/T).
Proof. This lemma follows directly according the definition of Eluder dimension (L/T)) in Definition 2.1, and the fact that all functions in Fr must agree on the previous samples where 0, 0.
With this lemma, we are ready bound the regret of rounds with oe
Lemma H.3. With = v
[Fl the output actions a at each round in Algorithm 6 satisfies
8A log Fl
Σ max Ho, = (2, (1x, -0 - (VVAIo))
Σ of |
[F]
A(del log [FI)
Proof. In this proof, we focus on the case 0; 0. We first notice that for rounds o, 0, always have f (zt, at) Tt. Hence f' E F; for every E [T]. We define
aj = arg max f a).
aEA
At round 1, we let b = arg max DEA fe a), and we define B, C At as
B, a E Ar (e) fe a)
2 T
(28)
For rounds with o, = 0, based on Jt. we divide such rounds into two cases, which we denote as Ti and Tz.
(a) There exists E B, and Fe, such that (z) fe(2,, 1/r.
(b) For all f E F, and B,, we have (f,, - fc(x,, a) < 1/T.
Regret in TT. For those t Tı, first we notice that for any E B,, according to Eq. (26) we have
1
(a(a)= A A+7 + E (3((((x,,b)) b.) - fe(xe, 2
>
A + 1 Excr 03 2/T
7.A'
45

---

where in the last inequality we use the fact that
27v 1 + Eese 2TVT 2 8A/ log FF
6A.
VT
Therefore, according to the definition of Ti that there exists some E Br and f Fr such that (f(;, a) - [1,, a)l 2 1/7, for any i Ti with probability at least 1/7A we will sample an action a, such that Z, = 1 (Ze is defined in Eq. (27)). Therefore, we have
E
(I,, a7) - f (xe: oz))
LET
Ze 0] 1/(7A)
Σ Z, 08 S 77ddau(\/))
S
It E Til
S
7AE
where the last inequality uses Lemma H.2.
Regret in E To with az E Bi. For those E T2, to facilitate the analysis we define
14, a) (f(z,, a) r1)² (f* a) - -r,)²
1i E E
of
and
Σ Eultoo
p. log
Σ exp FEF
(29)
Then we have
expl
_-=1 1s Fgz 0z))
(f) = Eger exp(
le Nay as))
which implies that
Σjer exp
Σの 1 2s,
E Tb 1-1
Φ.] -E
log
Exerexp exp (-
1-1 - Iol
-E
log
E=(f)exp(-ee(f-t
JEF
-P((a)) log
[a(f)exp((u(fffm.c)
feF
-Pt((a log
Σ a() -
FEF
=Pi(aa)) log
1- Σ {(())[[((ss at) # $ (x)
FEF
2 p(((at) Σ (()))[((z)))) # f at)].
(30)
fEF
Hence we have
Σ pr(a) (
ff (x)
REB,
Σ (i(a) (f - f((a,, at) + f(( - (x), + aEB.
2
T
46

---

(
Σ pi(a) (f f((z,, - + T
REB
pe(at)
3
PP(aa))
Σ
a(l) 8 (ree ai) +
p((af)
FEF
PP(aa))
Σ ((())T((z, + (2, az)) +
Pr(at)
fEF
(114)
T
3 T
S
A
+ of
Σ
t=1
where in (i) we use the fact that according to the definition of B, in Eq. (28),
2
ft a) fi( a,) 2 fo( be) fo( at)
T
T
and (ii) uses the definition of To that for any a B, and f Fr we always have Ift (2),
f (2(2)))) 1/1, and (tit) uses Eq. (30) and also the fact that
p:(at)
A 1 E.er (f(((( f((e ++ oi
Suming this up for every t E T2, we obtain that
E
Σ LITS
Mae E (2)(5"(111, Manaa)))
T
3 T T
A 1 1+
Σ of
1
E
- Φ11
+
[=1
t=1
T
A +
Σ
o
log F +
where in the last inequality we use the definition of 4 in Eq. (29) that 4u = log [F] and
exp Σ 1000 (
T > log
0.
Regret in t E To with a, & B.. Next, for at & Bi, according to the definition of At, there exists a function / E F, such that f(,,, ax) 2 f(xr, a') for any a' E A. This implies that
(4)) S flz,, b.) +
fi( & fa b.)
f(z,, ax) T
where in (i) we use the definition of B, in Eq. (28), and in (ii) we use the definition of To that for any E Fr, (f b,) (a, b,)l < 1/r. Therefore, in those rounds with o. 0, Ta and a & B,. we always have Zr = 1 (Z, is defined in Eq. (27)), which implies that
E
Σ Ila & (z),, - (x),
S
Σ l 0 dduu(1/T),
LIETa
where the last inequality uses Lemma H.2.
47

---

Finally we combined these these bounds in T1 and T2 together, and obtain that
E
1[or (x1, (xs,
E
Σ (M())))) - (x))
+E
(( - (x),
LETI
LET2
7Adeu((//)) + E
Σ
Nu B2] (Ir, - (are,
LIET
+ E
Σ LiET2
Iia & B2] (f" (x), - (oad)-f((aaa (x),
T A (
< (Adsto(//2) +
1
log F + (2/r) oī
t=1
With our choice of y = v
34 log [F|
we have
(o -VVAlog
E
1o, (f(, -x) =0
[F] of
Σ t=1
A(detu + log (F)
1=1
Finally, combining the regret bound for rounds with oe and o, = 0 together, we can prove Theorem H.1.
Proof Theorem H.1. We decompose the regret
(()) (x() (())aa))
RT
max aEA
T
Σ
10, = 0] max f* (It, f"
+
Σ
1l. = 1]
max f" ("( a) - f (21, (x))
aEA
laEA
1=1
1=1
According to Lemma H.1, we have
T [|. Imxx (((, -f M(ch =0 (VADoS (
T
E
[F|
1+ Σ oo
aed
1=1
and according to Lemma H.3, we have
(oVADog [F] Σ of A(dal log (FT) )
Σ 1o. 00] max (" a) I (are, ai)
(
Summing these two together, we obtain that
E R2 =0 (V/Aog F Σ of A(dew + log (F])
48

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provvdddd proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA]" is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: The main claims made in the abstract and introductio accurately reflect the paper's contributions and scope. The claims are validated by detailed proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
49

---

Answer: [Yes].
Justification:
The paper discuss the limitations of the work in the discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-ted system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes].
Justification:
The paper provides detailed assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
50

---

Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA].
Justification:
This is a theoretical paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ct aablicc/guide//ddddelliisss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not
51

---

including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results, See the NeurIPS code and data submission guidelines (https: wtsps.cccppbblc.... wwtec//ggiie/eeeeeeeee /eoeeSu/ ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA].
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula. call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
52

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of emrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA].
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurt:: httpa////eaarre..ccpppppa/tcttcc cc/puullcc/.hhiisssudlddllll
Answer: [Yes].
Justification: The research conducted in the paper conforms, every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is a theoretical work. There is no societal impact the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
53

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA].
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification:
This paper does not existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
54

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/aatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification:
This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: This paper does not involve crowdsourcing research with human subjects.
55

---

Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
56


Reviews:
[{"review_id": "rBOH54dclA", "reviewer": "Reviewer_aAKW", "summary": "This paper studies the problem of obtaining variance-aware regret bounds for realizable contextual bandits with general function approximation. They show that, despite intuition suggested by prior works, there is an unavoidable dependence on the Eluder dimension in getting variance-aware bounds. They investigate several different settings (depending on the strength of the adversary's environment design and the agent's knowledge of distributional assumptions) and show minimax lower bounds each involving the Eluder dimension. They also provide matching regret upper bounds under various assumptions on knowledge of distributions or variances.", "questions": "Please refer to strengths and weaknesses above.", "limitations": "No braoder impact concerns.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The problem is well-motivated, the surrounding literature is well-explained, and the authors take care to explain why the main message is surprising, while also explaining the intuition for the unavoidable dependence on Eluder dimension.\n* The algorithms and needed modifications are well-explained with authors taking care to make simplifying assumptions to enhance presentation and understanding.\n* Along the way, some new technicalities had to be developed such as employing a square regression oracle with variance-based regret employing a more complicated action selection scheme based on checking discerning actions.", "weaknesses": "* The main weakness is that the only upper bound results matching the lower bounds require some knowledge of the variance at every single round or under a stronger model class assumption (which then involves picking up a dependence on the size of the model class of variances).\n* There could be more discussion of other function classes beyond the generic finite regressor class ${\\cal F}$. For instance, how do the lower bounds and results here about variance-based bounds and Eluder dimension compare with the understanding for linear function classes, high-dimensional classes (like those mentioned for SquareCB in Foster and Rakhlin, 2020), neural network, or non-parametric classes? Do the lower bounds hold in greater generality?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for providing these useful feedback and questions.\n\nAnswers to Weaknesses:\n-  *The main weakness is that the only upper bound results matching the lower bounds require some knowledge of the variance at every single round or under a stronger model class assumption (which then involves picking up a dependence on the size of the model class of variances).*\n\nWe obtained matched upper bound and lower bound for the variance-aware cases in our paper. For agnostic variance cases, we have both upper bound and lower bound with only a factor of $\\sqrt{d_{\\mathrm{elu}}}$ between them. Even with this gap, the dependence over the variances $\\sqrt{\\sum_{t=1}^T \\sigma_t^2}$ is tight, and our bounds are sufficient to show the separation between variance aware and agnostic variance cases.\n\n-  *There could be more discussion of other function classes beyond the generic finite regressor class \n. For instance, how do the lower bounds and results here about variance-based bounds and Eluder dimension compare with the understanding for linear function classes, high-dimensional classes (like those mentioned for SquareCB in Foster and Rakhlin, 2020), neural network, or non-parametric classes? Do the lower bounds hold in greater generality?*\n\nEven though we did not discuss about infinite function class in our paper. But our algorithms and theoretical guarantee can generalize to infinite function classes. For example, for linear classes, using the similar structure of Algorithm 1 in our paper and some proper regression oracle for linear class similar as the one in Foster and Rakhlin (2021), we can obtain an upper bound of $\\tilde{\\mathcal{O}}(\\sqrt{dA\\sum_{t=1}^T\\sigma_t^2})$. For generalized linear classes, we can get an upper bound of $\\tilde{\\mathcal{O}}(\\sqrt{T\\sum_{t=1}^T\\sigma_t^2})$. And for other classes including neural networks and nonparametric class, we can get similar variance-dependent bound as long as there are some proper variance-aware regression oracles.\n\nAs for the lower bound part, since our lower bound is constructive, i.e. we show that there exists a function class $F$ which achieves the lower bound, we do not know how we can generalize our results to other function classes. But to obtain an instance-dependent lower bound for all possible function class is an interesting future research direction.", "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": "", "extra_scores": {}}, {"review_id": "hU6nR5fE0Z", "reviewer": "Reviewer_W3F3", "summary": "This paper studies contextual bandits with general function approximation, emphasizing the impact of variance information. It proves lower bounds dependent on the Eluder dimension and variance information in both strong and weak adversary settings. It also proposes algorithms for both cases. When the adversary is weak, the proved regret upper bound is optimal, otherwise, there is a $\\sqrt{d}$ gap from optimal. The paper also studies the learning problem when the function class contains the distributional information and provides optimal regret bound.", "questions": "1. Is it possible to prove a variance-dependent upper bound with $d_{elu}$ dependence in the first term of Theorem 4.2?\n2. What difficulty did you meet when trying to recover Zhao et al. (2023)’s result for unknown variance?", "limitations": "The limitations and societal impact of this work have been addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper studies contextual bandits with general function approximation. The proved lower bound dependent on the Eluder dimension and variance information is very novel.\n2. The paper provides a comprehensive analysis for different settings, e.g, weak/strong adversaries, and distributional settings. The proved results are insightful and optimal in most cases.\n3. The presentation is very clear, including comparison with previous works.", "weaknesses": "1. In the known variance section, this paper only focuses on a regime where $A \\le d_{elu} \\le \\sqrt{AT}$. The case $d_{elu} \\le A$ is also very important, especially when the action set is large and function approximation benefits. In such cases, the proved upper bound and lower bound do not match, so the contribution in this section is a bit overclaimed. (matching upper bound when variance is known)\n2. Some missing related works.\nMore works on variance-dependent results of heteroscedastic bandits:\n\n[1] Zhou et al. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes, Colt 2021\n\n[2] Zhou and Gu. Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs Neurips 2022\n\n[3] Zhao et al. Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits\n\n3. This description of \"checking disagreement\" (Line 166) is not very accurate. A similar definition of equation (4) has been used in previous works as weights ([4] [5]), bonus functions ([6][7]), and selection rules ([8][9]). I suggest adding more discussions on this.\n \n[4] Agarwal et al. Vo q l: Towards optimal regret in model-free rl with nonlinear function approximation. Colt 2023\n\n[5] Ye et al.  Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. ICML2023\n\n[6] Di et al. Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning, ICLR 2024\n\n[7] Huang et al. Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximation AISTATS\n\n[8] Gentile et al. Fast Rates in Pool-Based Batch Active Learning ICML 2024\n\n[9] Zhao et al. A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation\n\n4. Some minor errors: Line 12 worst case over what? \n\nIn the proof of Lemma E.5, there is an abusive use of $\\epsilon$, it represents both the Gaussian noise and a changeable parameter for $\\sigma$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for providing these useful feedback and questions.\n\nAnswers to Weaknesses:\n- *Mismatch upper and lower bound for large action space cases*\n\nWe have such results for cases where $d_{\\mathrm{elu}} < A$ (an upper bound $\\tilde{\\mathcal{O}}(d_{\\mathrm{elu}}\\sqrt{T\\sigma^2\\log|\\mathcal{F}|})$). Please view Theorem 5.2 in our paper for more details. We admit that this upper bound does not match the provided lower bounds, and we will change our presentation accordingly in the next version.\n\n- *Some missing related works. More works on variance-dependent results of heteroscedastic bandits:*\n\nThanks for pointing out these related references. We will add them in the next version of our paper.\n\n- *This description of \"checking disagreement\" (Line 166) is not very accurate. A similar definition of equation (4) has been used in previous works as weights ([4] [5]), bonus functions ([6][7]), and selection rules ([8][9]). I suggest adding more discussions on this.*\n\nHere 'check agreement' means checking whether there exists an action where two functions in the function set deviated a lot. Thanks for pointing out these references. We will add them in the next version of our paper.\n\n- *Some minor errors: Line 12 worst case over what?*\n\nThese are words meant to be deleted. We will delete them in our next version.\n\nAnswers to Questions: \n- *Is it possible to prove a variance-dependent upper bound with dependence in the first term of Theorem 4.2?*\n\nYes, we can obtain such an upper bound: $\\tilde{\\mathcal{O}}(d_{\\mathrm{elu}}\\sqrt{T\\sigma^2\\log|\\mathcal{F}|})$, which serves as a special case of Theorem 5.2 in our paper.\n\n- *What difficulty did you meet when trying to recover Zhao et al. (2023)’s result for unknown variance?*\n\nThe main difficulty we met is that we are dealing with bandit with function approximation in our paper, compared to the setting of linear bandit in Zhao et al. (2023). Technically, to prove our results, we are required to apply the general Freedman's inequality, rather than the Freedman's inequality specialized for linear setting.", "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": "", "extra_scores": {}}, {"review_id": "KTFgGCFT3O", "reviewer": "Reviewer_u4Bf", "summary": "This paper considers contextual bandits with function approximation, and studies the influence of the variance information on the regret bound. It studies three regimes: weak adversary where the variance is revealed before each time step; strong adversary where the variance depends on the chosen action at each time step; and learning with a model class where the reward follows a Gaussian distribution with the mean and the variance depending on the context and the arm. By incorporating the variance, both the upper and lower bounds of the regret are refined, subject to some gaps in some scenarios.", "questions": "- Can the authors summarize the main technical novelty used in the paper?\n- Concerning the third case, learning with the model class, the authors indicate that the variance information is not required as input in line 105. Does it mean that the variance, given the model, the context and the action, the variance $\\sigma_{M_t}^2(x_t,a)$ is revealed, as presented in line 7 in Algorithm 3? If we only assume that the variance is unknown but it only depends on the context and the arm, can the algorithm be modified such that it can work with estimating the variance on the fly, like [1]?\n- The  lower bound result Theorem 6.2 is obtained via instances with the same variance. While the lower bound is indeed a minimax lower bound, as this paper is considering the role of the variance, is it possible to derive a lower bound for the case where the variances are heterogeneous?\n\n[1] Jourdan, M., Rémy, D., & Emilie, K. Dealing with unknown variances in best-arm identification. International Conference on Algorithmic Learning Theory. PMLR. 2023.", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The proposed problem is interesting and the result also answers the conjecture that $\\tilde{O}(\\sqrt{A\\Lambda \\log|\\mathcal{F}|}+A\\log |\\mathcal{F}|)$  is not true, when we incorporate the variance into the algorithm design. The eluder dimension plays an important role in this bound and has been used to characterize the bounds.\n- The paper studies three different cases and provides sufficient insights in this line of problems. While there are some gaps between the upper and lower bounds, the discussions are thorough and can lead to further research.", "weaknesses": "See the questions section", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- *Can the authors summarize the main technical novelty used in the paper?*\n\nWe have the following technical contributions. \n\n1. Algorithm design through checking disagreement: Our algorithms in Sec 4 and Sec 6 decide whether to use inverse gap weighting based on the degree of disagreement in the function confidence set. Such a design is, to our knowledge, crucial to obtain the tight bound and not seen in previous work. The analysis framework for this algorithm is also new. \n\n2. Refined online regression oracle: The choice of the online regression oracle (i.e., Prod) in Sec 4 and its associated analysis are non-trivial. The usefulness of such an online regression oracle has not been discovered before. \n\n3. In Sec 6, we adapt the inverse-gap weighting technique to learning from model class. This was mentioned as a future work by [Wang et al., 2024]. In this case, we identified the Gaussian-noise condition under which tight bound can be obtained without revealing variance. We believe this is an important step towards resolving the general case. \n\n4. In Sec 6, we identify the important difference between the achievable bounds using $\\sum_{t=1}^T \n\\sigma(x_t,a_t)^2$ and $\\sum_{t=1}^T \\max_a \\sigma(x_t,a)^2$ as the total variance measure. This answers the open questions in [Wang et al., 2024]. Similarly, in Sec 4 and 5, we identify the difference between the achievable bounds under strong and weak adversary. \n\n\n\n\n- *Concerning the third case, learning with the model class, the authors indicate that the variance information is not required as input in line 105. Does it mean that the variance, given the model, the context and the action, the variance $\\sigma_{M_t}^2(x_t,a)$ is revealed, as presented in line 7 in Algorithm 3?*\n\nYes, the variance will be revealed.\n\n- *If we only assume that the variance is unknown but it only depends on the context and the arm, can the algorithm be modified such that it can work with estimating the variance on the fly, like [1]?*\n\nIt would be hard to estimate in general. For instance, if the context space is super huge and no context is repeated twice, then since there is no model class, then there is no way to generalize the variance information since each time, the variance can be arbitrary. So, estimation of the variance on the fly is not possible. On the other hand, if the context space is small, estimating the variance might be possible, but we suspect that would render the regret bound depending on the size of the context space. \n\n- *The lower bound result Theorem 6.2 is obtained via instances with the same variance. While the lower bound is indeed a minimax lower bound, as this paper is considering the role of the variance, is it possible to derive a lower bound for the case where the variances are heterogeneous?*\n\nThanks for your suggestion. Our lower bounds can be adapted to any collection of variances (with no ordering) through the following trick. The idea is that for any given collection of variance, we can divide the variances with doubling scales into $\\log T$ categories. For the scale with the largest cumulative variance, we put the variances of this scale to all appear first and apply our lower bound to these steps. By pigeonhole principle, our lower bound is worsened by a rate of at most $\\log T$. Currently, our lower bounds do not extend to cases where the sequence of variance is given. It is an interesting direction for future research.\n\n[1] Jourdan, M., Rémy, D., & Emilie, K. Dealing with unknown variances in best-arm identification. International Conference on Algorithmic Learning Theory. PMLR. 2023.", "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": "", "extra_scores": {}}, {"review_id": "RO4ZagShfy", "reviewer": "Reviewer_CuA6", "summary": "*** In line 12 there is a comment with acronyms of one of the authors, for the AC's consideration if it is a desk reject ***\n\nThe paper studies the setting of adversarial contextual MAB under the assumption of access to a realizable general function class for approximating the context-dependent rewards.\nThe authors prove both upper and lower regret bounds, that are variance dependent, i.e., dependent on the cumulative data variance rather than on $T$ which is the number of episodes. The authors present the regent bounds in three different settings (1) for strong adversary, (2) for weak adversary, (3) where learning from function class.\nIn all the cases, their bounds are also dependent on the Eluder dimension. They present a matching lower bound for each setting.\nThe presented algorithm is adapted from SquareCB of Foster and Rakhlin (2020), but additionally maintains a confidence function set, to learn faster when the functions in the confidence set have larger disagreement.", "questions": "1.\tPlease provide a specific comparison of your results with the known variance-dependent bounds in previous literature.\n\n2.\tWhat do you mean by $d_{elu}(0)$ ? For my understanding, the Eluder dimension is meaningful only for $\\alpha \\in (0,1] $.\n\n3.\tPlease refer to the weaknesses.", "limitations": "Mentioned in the \"Weaknesses\" section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tVariance-dependent regret bound is an interesting benchmark in RL. An application of it to contextual bandits is nice and worth the community's attention. \n2.\tThe work is extensive – the authors fully analyze three different settings, and prove both upper and lower bounds.", "weaknesses": "1.\tThe related literature review is unclear.  In the presented previous results, there should be a clear separation between variance-dependent bounds and minimax regret bounds. \n\n2.\tThe difference between the three settings is unclear to me. I would expect the authors to use the accepted terms, i.e., oblivious and adaptive adversary. Moreover, to be comparable to previous literature, I think the most interesting case is strong adversary + learning from function class.\n\n3.\tI do not see why the eluder diminution is necessary in all the bounds. It would be appreciated if the authors could provide an intuitive explanation.\n\n4.\tIt seems that the work over a confidence set of functions implies a running time complexity of $|F|$ that is not discussed. \n\n5.\tThe paper seems to be written at the last minute, as there are comments left inside the paper. See for additional example line 185 \"(our contribution)\".\n\n6.\tThe use of the Hellinger-Eluder dimension is given without any justification or an appropriate citation of previous works. The classic Eluder dimension introduced by Russo and Van-Roy is defined with respect to the $\\ell_2$ norm only. If the authors are using other versions of it, they have to cite related work, if such exists, or justify the used guarantees themselves.  In this case, [1] presents a version of the Eluder dimension to bounded metrics, that also holds to the squared Hellinger distance.\n\n\n[1] Eluder-based regret for stochastic contextual MDPs, Levy et al. 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for providing these useful feedback and questions.\n\nWeakness: \n\n- *Unclear related work.*\n\nWe will improve the related work section based on the suggestion.\n\n- *Difference between the three settings.*\n\nThe separation between strong and weak adversary is different from that between oblivious and adaptive adversary. The terms 'strong' and 'weak' come from literature studying adversarial corruption in contextual bandits (e.g., He et al., 2022). In our case, 'strong adversary' decides the variance after seeing the decision of the learner, while 'weak adversary' decides it before. The separation between 'function class' and `model class' has been studied in previous works like [Wang et al., 2024]. The latter provides  the full distributional information given context and decision, while the former only the mean. \n\n[He et al., 2022] Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions. \n\n*The most interesting case is strong adversary + learning from function class.*\n\nWe argue that weak adversary and learning from model class are also of interest. In particular, as we showed, against weak adversary, one may obtain a better regret bound. Also, with a model class, the learner is able to generalize the learned knowledge beyond the 'mean' domain, which is the main consideration in the field of 'distributional RL.' The benefit of learning with a model class is also discussed in, e.g., [Wang et al., 2023, 2024]. \n\n- *Why the eluder dimension is necessary in all the bounds?*\n\nSome intuition has been mentioned in Line 41-54. While in the non-contextual case (e.g., multi-armed bandits), eluder dimension is not necessary, it is necessary in the contextual case as we showed. Consider the case where the function set size |F| >> 2 and the action number A=2. Suppose that the ground truth function $f^\\star$ always chooses the better action under every context. Every time, the adversary chooses the context so that one of the functions choose an action that disagrees with all other $|F|-1$ functions' choices. This way, to figure out $f^\\star$, the regret must scale with some ``disagreement coefficient'' of $|F|$, instead of just $A$. The eluder dimension takes the role of the disagreement coefficient. \n\n- *Running time O(|F|) not discussed.*\n\nWe will clarify this in our revision. Indeed, in this work, we only focus on the statistical complexity but not the computational complexity. \n\n- *Comments left inside the paper. Additional example: line 185 \"(our contribution)\".*\n\nWe are sorry for the mistake. The label ``(our contribution)'' is actually not a mistake. It refers to the equation right below Line 179. \n\n- *The use of the Hellinger-Eluder dimension is given without any justification or an appropriate citation of previous works. The classic Eluder dimension introduced by Russo and Van-Roy is defined with respect to the norm only. If the authors are using other versions of it, they have to cite related work, if such exists, or justify the used guarantees themselves. In this case, [1] presents a version of the Eluder dimension to bounded metrics, that also holds to the squared Hellinger distance.*\n\n The use of the Hellinger-Eluder dimension is given without any justification or an appropriate citation of previous works. The classic Eluder dimension introduced by Russo and Van-Roy is defined with respect to the $\\ell_2$norm only. If the authors are using other versions of it, they have to cite related work, if such exists, or justify the used guarantees themselves. In this case, [1] presents a version of the Eluder dimension to bounded metrics, that also holds to the squared Hellinger distance.\n\n\nThanks for bringing to our attention the missing citation. Our motivation is the same as [1] to generalize the eluder dimension to general divergence.\n\n[1] Eluder-based regret for stochastic contextual MDPs, Levy et al. 2024.\n\n\nQuestion:\n- *Please provide a specific comparison of your results with the known variance-dependent bounds in previous literature.*\n\nPrevious work on variance-dependent contextual bandits mostly focused on linear contextual bandits (see Zhao et al., 2023 and the related work therein).  Literature on variance-dependent contextual bandits with general function approximation is scarce. [Wang et al., 2024] studied the setting same as our Section 6. Their result is listed in our Table 1. While they conjectured that their bound could be improved, we disproved it by showing a matching lower bound. The work of [Wei et al., 2020] also investigated second-order bounds for contextual bandits, but they focused on the agnostic setting (while we focused on the realizable setting). Though their algorithm can be applied to our setting, the regret is highly sub-optimal. In general, their result is incomparable to ours. \n\n- *What does $d_{\\mathrm{elu}}(0)$ mean?*\n\nIn fact, $d_{\\mathrm{elu}}(\\alpha)$ remains meaningful when $\\alpha=0$ (see our Definition 2.1, and simply set $\\alpha=0$). For example, a $d$-dimensional linear function class has $d_{\\mathrm{elu}}(0)=d$.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper makes a solid contribution to the important problem of adapting to the variance in contextual bandits.
Decision: Accept (poster)