How Does Variance Shape the Regret in Contextual Bandits?

Authors: zeyu  jia
jian  qian
alexander  rakhlin
chen-yu  wei
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:04:26

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}})$.

Main paper: 
 introduction: 
 We consider the contextual bandit problem that models repeated interactions between the learner and the environment. In each round, the learner chooses an action based on the received context, and observes the reward of the chosen action. Algorithms designed to achieve minimax regret guarantees under a variety of statistical assumptions and computational models have been extensively studied (Auer et al., 2002; Dudik et al., 2011; Agarwal et al., 2012 Agarwal et al., , 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 of the environment. In this work, we refine the regret bound by considering the variance of the reward. Such variancedependent regret bounds, also known as second-order regret bounds, have been primarily studied under linear function approximation (Zhang et al., 2021; Kim et al., 2022; Zhao et al., 2023) . Notably, 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Zhao et al. (2023) first established a near-optimal Õ(d √ Λ + d) regret bound for linear contextual bandits, where d represents the feature dimension and Λ the sum of the reward variances.For contextual bandits with general function approximation, the recent work by Wang et al. (2024) obtained a second-order bound assuming access to a model class containing distributional information about the reward. They showed a regret bound of Õ( d elu Λ log |M| + d elu log |M|), where |M| is the size of the model class, and d elu = d elu (M) is its eluder dimension. As noted in Wang et al. (2024) , the dependence on d elu is undesirable, and when the number of actions A is much smaller than d elu , this bound can potentially be improved. This conjecture is supported by Foster and Rakhlin (2020) , who showed that the upper bound Õ( AT log |F| + A log |F|) is achievable regardless of the eluder dimension, where T ≥ Λ is the number of rounds, and |F| is the size of the function class containing mean reward information. It is tempting to conjecture that the regret can smoothly scale with Λ, resulting in a bound of Õ( AΛ log |F| + A log |F|). Such variance-dependent regret bounds that replace the dependence on the number of rounds T by the total variance Λ have been shown in multi-armed bandits (Audibert et al., 2009) , linear bandits (Ito and Takemura, 2023) , and linear contextual bandits (Zhao et al., 2023) .In this paper, we show, surprisingly, that the aforementioned conjecture is not true in general. Specifically, for any A and any d elu ≤ √ AT , one can construct a problem instance with lower bound Ω( min{A, d elu }Λ + d elu ) with log |F| = O(log T ) and d elu (F) = d elu . This rules out the possibility of achieving Õ( AΛ log |F| + A log |F|) for all A because we can always make d elu = √ AT , resulting in a lower bound Ω( √ AT ) even with Λ = 0. Our primary goal is to design algorithms that achieve the near-optimal regret bound Õ( min{A, d elu }Λ log |F| + d elu log |F|).The lower bound min{A, d elu }Λ + d elu 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 is due to the variance of the reward and the local structure of the function set around the ground truth function f ⋆ ∈ F. This results in the term min{A, d elu }Λ, with the leading coefficient min{A, d elu } corresponding to the decision-estimation coefficient (Foster et al., 2021) . The second part accounts for global search for the true function, in which the complexity is due to 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 d elu , 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-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 et al. (2020) also derived a set of results for general contextual bandits showing that the tight second-order 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| > 1 can be applied to our setting, though it only gives highly sub-optimal bounds. Overall, our work refines theirs in 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. 
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 ⊂ [0, 1] X ×A . At round t, the learner observes a context x t ∈ X , then makes a decision a t ∈ A based on the current context x t and history, and observes a reward r t . We assume that these rewards r t are given byEQUATIONwhere f ⋆ : X × A → [0, 1] is some function unknown to the learner, and ϵ t are independent zeromean random variables with variance σ 2 t such that r t ∈ [0, 1]. 1 We denote Λ = T t=1 σ2 t . The learner aims to optimize the total expected regret R T , defined asR T = T t=1 Å max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t ) ã .We make the following realizability assumption:Assumption 2.1 (Function Realizability). Assume that f ⋆ in Eq. (1) satisfies f ⋆ ∈ F.We finish this section with the definition of eluder dimension:Definition 2.1 (Eluder Dimension (Russo and Van Roy, 2014) ). For function class F defined on space Z, we define the eluder dimension of F at scale α ≥ 0, denoted by d elu (F; α), as the length of the longest sequence of tuples (z 1 , f 1 , f ′ 1 ), ..., (z m , f m , f ′ m ) ∈ Z × F × F such that there exists α 0 ≥ α making the following hold for all i = 1, .., m:j<i (f i (z j ) -f ′ i (z j )) 2 ≤ α 2 0 , and |f i (z i ) -f ′ i (z i )| > α 0 .Throughout the paper, if α is not specified, we take the default value α = 1 /T 2 . 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 the 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 σ t only depends on the history up to round t -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 |F| ≤ √ AT , such that the regret is at leastEQUATIONFor upper bounds in the weak adversary case, we focus on the regime A ≤ d elu ≤ √ AT , where the lower bound can be written as Ω( √ AΛ + d elu ). 2 While our ultimate goal is to obtain a nearly matching upper bound Õ( AΛ log |F| + d elu log |F|), we have not achieved it yet in full generality. In Section 4, we provide an algorithm which operates under the assumption that the variance σ t is revealed to the learner at the beginning of round t, 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 σ t ∈ {0, 1} for all t and σ t is revealed to the learner at the end of round t, the matching upper bound can also be achieved.Next, we consider the case where the adversary is strong. This means the adversary can decide σ t after seeing the action a t chosen by the learner at round t. In this case, the lower bound becomesEQUATIONThe difference with Eq. ( 2) is that the scaling in front of Λ changes from min{A, d elu } to d elu . This shows the even more crucial role of eluder dimension in the strong adversary case. For this setting, we give an upper bound of Õ(d elu Λ log |F| + d elu log |F|), which is off from the lower bound by a √ d elu factor along with other logarithmic factors. In Section 6, we assume that the function class provides information on the distribution of the reward rather than just the mean. Such a 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 ⋆ ∈ M so that M ⋆ (x, a) specifies reward distribution for the context-action pair (x, 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 Õ( AΛ ∞ log |M| + d elu log |M|) upper bound where Λ ∞ = t max a σ M ⋆ (x t , a) 2 , and a matching lower bound, where σ M (x, a) is the reward variance for the context-action pair (x, a) predicted by M ∈ M. Wang et al. (2024) also studied second-order contextual bandits with a model class. They use Λ • = t σ M ⋆ (x t , a t ) 2 , i.e., the reward variance of the chosen actions, as the variance measure. They obtain Õ( d elu Λ • log |M| + d elu log |M|) upper bound. We show a nearly matching lower bound Ω(min{√ d elu Λ • + d elu , √ AT }), 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 et al. (2024) cannot be improved even when A < d elu .The work of Pacchiano (2024) also studied variance-dependent bounds for realizable contextual bandits. They also consider two settings, which can be mapped to those in our Section 4 and Section 5, respectively. For the weak adversary setting with revealed σ t (Section 4), they give an upper bound of Õ(d elu Λ log |F| + d elu log |F|), 3 which is incomparable to our Õ( AΛ log |F| + d elu log |F|).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). 
weak adversary case with variance revealing: 
 In this section, we consider cases where the variance σ 2 t at round t is given to the learner at the beginning of round t together with the context x t .The regret lower bound is shown with identical and known variance. The construction is similar to those in Wei et al. (2020) . Concretely, we have the following theorem.Theorem 4.1 (Main lower bound). For any integer d, A ≥ 2, any positive real number σ ∈ [0, 1], and time T > 0, there exists a context space X and a contextual bandit problem F ⊂ (X × A → R) with eluder dimension d elu (0) ≤ d, action set A with |A| ≤ A, and variance σ t ≤ σ for all t ∈ [T ] such that any algorithm will suffer a regret at least Ω( σ 2 min{A, d}T + min{d, √ AT }).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 Ω( σ 2 min{A, d}T ) is a natural lower bound with variance σ due to estimation of the mean values.(2) For the second part, we consider the following function class. In this function class, there is a "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 a reward of 1 but obtains 0 for all the other contexts. When d < √ AT , this function class forces the learner to guess for each context which action to choose. So even if the reward is deterministic, i.e., variance σ = 0, 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 ≥AT , the learner can simply commit to the "good" action and sufferAT but no better than this. This lower bound is rather surprising for the following consequences: (1) 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 <AT .(2) Even when d < √ AT , 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 σ. 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.Motivated by the lower bound in Theorem 4.1, we wonder whether there is an algorithm which can achieve a matching upper bound of Õ( σ 2 min{A, d}T + min{d,AT }), 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.e.σ 1 = σ 2 = • • • = σ T = σ,and σ 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 t = f ⋆ (x t , a t ) + ϵ t ∈ [0, 1] and Var(ϵ t ) ≤ σ 2 t for every 1 ≤ t ≤ T . Our results can be easily extended to subgaussian random noise (at the cost of a log T factor) since for such variables, with probability at least 1 -δ, |ϵ t | ≤ C log(1/δ) for a constant C.We first consider the case with identical variance, i.e. σ 2 t = σ 2 for all t ∈ [T ]. We propose Algorithm 1, and show that it has regret upper bound Õ( σ 2 AT log |F| + d elu log |F|). The algorithm is adapted from SquareCB of Foster and Rakhlin (2020) , but additionally maintains a confidence function set, and has mechanisms to learn faster when the functions in the confidence set has larger disagreement. It has the following elements:1. Restricting action set (Line 4) At the beginning of round t (Line 4), the learner restricts the action set to A t , which only includes those actions that is the best action of some functions in the function class F t . If we assume that f ⋆ is always in the function class F t , by doing this we remove the unnecessary possibility of choosing actions that can never be the best action.Checking disagreement (Line 5-Line 7) The next step of the algorithm is to check whether there is an action in A t such that two functions in the function class have large value differences (Line 6). We called such actions "discriminative actions". Roughly speaking, we are seeking an action a ∈ A t such that∃f, f ′ ∈ F t , |f (x t , a) -f ′ (x t , a)| ≳ ∆ ≈ σ 2 .Algorithm 1 VarCB (Variance-aware Contextual Bandits)EQUATIONif max a∈At g t (a) ≥ ∆ then 7:Choose action a t = arg max a∈At g t (a) and receive r t .8:else 9:Call online regression oracle (Algorithm 4) with input (F t , x t ) and obtain f t .10:Let b t = arg max a∈At f t (x t , a) (pick an arbitrary maximizer if there are multiple).11:Draw a t ∼ p t and receive r t , wherep t (a) =      0 if a ∈ A \ A t , 1 |At|+γ(ft(xt,bt)-ft(xt,a)) if a ∈ A t \ {b t }, 1 -a ′ ̸ =a p t (a ′ ) if a = b t .(inverse gap weighting)12:Definew t = min 1 σ 2 , 1 gt(at) √L and update the confidence set:EQUATIONwhere ft+1 = arg minEQUATION)If such an action exists, then the learner chooses this action at round t. By selecting such an action that can discriminate disagreed functions, the function set F t can more quickly shrink. To prevent this action to incur overly large regret, it is important to perform Step 1 (Restricting action set). The regret incurred in rounds choosing discriminative actions is of order Õ(d elu log |F|).3. Inverse gap weighting (Line 8-Line 11) At round t, if there is no discriminative action, then the learner performs inverse gap weighting as in the SquareCB algorithm (Foster and Rakhlin (2020) ).Inverse gap weighting requires the learner to have access to an online regression oracle that generates online estimations f t and ensures that the estimation error t (f t (x t , a t ) -f ⋆ (x t , a t )) 2 is small. In the original SquareCB, the requirement for the online regression oracle isR sq = T t=1 (f t (x t , a t ) -r t ) 2 - T t=1 (f ⋆ (x t , a t ) -r t ) 2 ≲ log |F|, (F&R's condition)which only allows for a AT log |F| regret bound that does not meet our goal. To improve this, we design an online regression oracle that ensuresR sq = t∈T IGW (f t (x t , a t ) -r t ) 2 - t∈T IGW (f ⋆ (x t , a t ) -r t ) 2 ≲ (σ 2 + ∆) log |F|, (our condition)where T IGW is the set of rounds that we run inverse gap weighting (i.e., entering the else case in Line 8), and ∆ is an upper bound for max a∈At max f,f ′ ∈Ft |f (x t , a) -f ′ (x t , a)|, i.e., the maximum disagreement among the function set F t for the context x t . Thanks to Step 2, we only run inverse gap weighting when ∆ ≲ ∆ ≈ σ 2 . Thus, with the refined R sq guarantee and standard squareCB arguments, we can get a regret bound of order σ AT log |F| for the rounds in T IGW .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 R sq = O(log |F|/η) as long as the functions to be aggregated are η-mixable. Thus, in order to show R sq = O(σ 2 log |F|), we need to argue η = Ω(1/σ 2 ). However, because the potential range of r t is [0, 1] even though the variance σ 2 and and the disagreement ∆ are both much smaller than 1, the best mixability coefficient η we can show for squared loss is still Θ(1).To address this, we resort to the use of the Prod algorithm (Cesa-Bianchi and Lugosi, 2006) with a properly chosen surrogate loss to perform aggregation. This algorithm has a 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 a t for round t, the learner updates the confidence function set F t to prepare for the next round. The construction of the confidence set utilizes the idea of weighted regression that has been widely used in previous varianceaware or corruption-robust contextual bandit or RL algorithms (He et al., 2022; Zhao et 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 1 is described in Theorem 4.2, whose proof is deferred to Appendix D.Theorem 4.2. Algorithm 1 ensures with probability at least 1 -δ,T t=1 (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) = Õ » σ 2 AT log (|F|/δ) + d elu log (|F|/δ) .Comparison with AdaCB of Foster et al. (2020) Our VarCB (Algorithm 1) shares some similarities with the AdaCB algorithm from Foster et al. (2020) , which aims to achieve a Õ( d log |F | GAP ) regret bound. Here, d is a disagreement coefficient of F, which takes the same role as our d elu , and GAP represents the minimal reward gap between the best and second-best decisions. Specifically, both algorithms include a 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 is superficially related to the if-else separation in VarCB. However, we find that the case separations in the two algorithms do not have a 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-free, but VarCB requires the information of σ. Developing a more unified version for these two better-than-minimax algorithms is an interesting future direction.Next, we will discuss how to generalize our algorithm to heteroscedastic case, i.e. 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 σ t ∈ [0, 1 AT ], we classify t into T 0 , and for σ t ∈ ( 2 i-1 AT , 2 i AT ], we classify t into T i for 2 ≤ i ≤ log(AT ), i.e., if σ t falls into the i-th intervals in the following,EQUATIONwe classify t into T i . For each set T i , we maintain an algorithm A i of Algorithm 1 in parallel. At the beginning at round t, when observing that t ∈ T i , only A i is updated, while A j remains the same for j ̸ = i. According to Theorem 4.2, we have for any0 ≤ i ≤ log T , t∈[Ti] (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) = Õ Ç… A|T i | • Ä 2 i AT ä 2 log |F| + d elu log |F| å ,we can bound the total regret bylog(AT ) i=1 Õ Ç… A|T i | • Ä 2 i AT ä 2 log |F| + d elu log |F| å = Õ Ñ Ã A T i=1 σ 2 i log |F| + d elu log |F| é .Algorithm 2 Algorithm for Heteroscedastic Noise Input: 1: Initialize instances A i of VarCB (Algorithm 1) with σ = 2 i AT for 0 ≤ i ≤ log(AT ). 2: for t = 1 : T do 3:Receive σ t ∈ [0, 1], and suppose that σ t ∈ Σ i , where Σ i is defined in Eq. ( 7).Receive context x t , and inject x t into algorithm A i . to obtain action a t .Play action a t and update algorithm A i .The formal algorithm for heteroscedastic cases is given in Algorithm 2, and we have the following corollary on the second-order regret bound of Algorithm 2.Corollary 4.1. The output a t of Algorithm 2 in rount t satisfies that with probability at least 1 -δ,T t=1 (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) = Õ Ñ Ã A T i=1 σ 2 i log(|F|/δ) + d elu log(|F|/δ) é .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 σ t after seeing the action a t chosen by the learner. We provide regret lower and upper bounds matching up to a factor of √ d elu 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 enhanced in terms of the achievable minimax regret bounds. Concretely, we have the following theorem.Theorem 5.1. For any integer d, A, T ≥ 2 and any positive real number Λ ∈ [0, T ], there exists a context space X , a contextual bandit problem F ⊂ (X × A → R) with eluder dimension d elu (F, 0) = d and action set A = [A] and an adversarial sequence of variances σ 2 1 , . . . , σ 2 T with T t=1 σ 2 t ≤ Λ such that any algorithm will suffer a regret at least Ω(min{√ dΛ + d, √ AT }).The above theorem shows that the regret is at least Ω(min{√ dΛ + d, √ AT }) where d = d elu (F) even with log |F| = O(log T ).Recall that the bound in the weak adversary case (Section 4) can be written as Ω(min{ min{A, d}Λ + d,AT }). 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 a factor of √ d.Regret upper bound For the strong adversary case, we adopt an optimism-based approach. In particular, we generalize the SAVE algorithm by Zhao et al. (2023) , which achieves the tight Õ(d √ Λ + 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. (2011) ) 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 it and refer the readers to Zhao et al. (2023) . Notice that for this algorithm, we do not need σ t to be revealed to the learner as in Section 4. In fact, we do not even need to know Λ. We have the following theorem for its regret guarantee. The proof is provided in Appendix F. Notice that when specializing Theorem 5.2 to the linear setting, the bound becomes Õ(√ d 3 Λ + d 2 ) since log |F| = Θ(d), 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. It is an interesting future direction to see whether our bound can be improved. We mention in passing that the work by Wang et al. (2024) obtained Algorithm 3 DistVarCB (Distributional Variance-aware Contextual Bandits)1: Let M 1 = M, M 1 = 1 |M| M ∈M M , and L = Θ(log(|M|T /δ)). 2: for t = 1, . . . , T do 3: Receive context x t . 4: if ∃M, M ′ ∈ M t and a ∈ A such that D 2 H (M (x t , a), M ′ (x t , a)) ≥ 1/2 then 5: Let I t = 1 and pull a t = arg max a max M,M ′ ∈Mt D 2 H (M (x t , a), M ′ (x t , a)).6: else 7:Let I t = 2 and pull a t ∼ p t wherep t = arg min p∈∆(A) max M ∈Mt E a∼p ñ max a ′ f M (x t , a ′ ) -f M (x t , a) -γ (f M (x t , a) -f Mt (x t , a)) 2 σ 2 Mt (x t , a)ô .Receive r t .9:Let M t+1 = M t ∩ ¶ M : t s=1 D 2 H (M (x s , a s ), M s (x s , a s )) ≤ L © . 10: Let M t+1 = M ∈M t+1 qt(M )M M ∈M t+1 qt(M ) , where q t (M ) ∝ t s=1 M (r s |x s , a s ).dΛ log |M|+d log |M| upper bound where d = d elu (M). However, the algorithm relies on having access to a model class. We study such a setting in our next section.6 Learning with a Model Class Distributional setup In this section, we consider the case where the learner is given a model classM ⊂ ((X × A) → ∆(R))where each model M ∈ M maps any context-action pair to a gaussian distribution, i.e., for any x, a ∈ X × A,M (x, a) = N (f M (x, a), σ M (x, a)),where f M (x, a) and σ M (x, a) are the mean and variance of the distribution M (x, a). We assume that all the expected rewards and variances are bounded by [0, 1]. Recall, at round t, the reward is given by r t = f ⋆ (x t , a t ) + ϵ t . We further assume throughout this section that ϵ t is Gaussian with variance σ ⋆ (x t , a t ) (since Gaussian is unbounded, we drop the assumption r t ∈ [0, 1] that we made in Section 2). Thus, the distribution of r t follows a true modelM ⋆ where M ⋆ (x, a) = N (f ⋆ (x, a), σ ⋆ (x, a)). Assumption 6.1 (Model Realizability). Assume M ⋆ ∈ M.For this setup, it is useful to consider the Hellinger counterpart of the eluder dimension. Definition 6.1 (Hellinger Eluder Dimension). For the model class M defined on the space Z (that is M ⊂ (Z → ∆(R)), we define the Hellinger eluder dimension of M at scale α ≥ 0 as d H elu (α) be the length of the longest sequence of tuples(z 1 , M 1 , M ′ 1 ), ..., (z m , M m , M ′ m ) and α 0 ≥ α such that for all i = 1, .., m, functions M i , M ′ i ∈ M, j<i D 2 H (M i (z j ), M ′ i (z j )) ≤ α 2 0 , and D 2 H (M i (z i ), M ′ i (z i )) > α 2 0 .Algorithm Similar to Algorithm 1, we present Algorithm 3 tailored for the distributional case. At each round t, upon receiving the context x t , the algorithm first checks if there exists an action a such that two models within the localized model class M t exhibit a significant divergence on the context-action pair x t , a 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, if 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 1 and Algorithm 3 is that the latter measures the "disagreement" in terms of the squared Hellinger distance.We obtain the following distributional version regret bound for Algorithm 3.Theorem 6.1.For d = d H elu ( 1 / √ T ), the output a t of Algorithm 3 satisfies with probability at least 1 -δ, R T = ÕÇ… A T t=1 σ 2 M ⋆ (x t ) • log(|M|/δ) + d log(|M|/δ) å ,where a) . A similar upper bound for a more general distributional case is obtained by Wang et al. (2024) in theσ 2 M ⋆ (x t ) = max a∈A σ 2 M ⋆ (x t ,form of Õ » d T t=1 σ 2 M ⋆ (x t , a t ) • log |M| + d log |M| .In the leading term, our bound replaced the dependence of d by the number of actions A which is significantly smaller than A 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 is at one end of the Pareto frontier.We present the matching lower bound for our result as follows, which is essentially a rewrite of Theorem 4.1. Theorem 6.2. For any integer d, A, T ≥ 2, any positive real number σ ∈ [0, 1], there exists a context space X and a contextual bandit gaussian model classM ⊂ (X ×A → ∆(R)) with Hellinger eluder dimension d H elu (0) ≤ d, action set A = [A],and variances σ M (x, a) ≤ σ for all M ∈ M, x, a ∈ X × A such that any algorithm will suffer a regret at least Ω( σ 2 min{A, d}T + min{d, √ AT }).Now we present the matching lower bound for the upper bound from Wang et al. (2024) . T t=1 σ M ⋆ (x t , a t )2 ≤ Λ such that any algorithm will suffer a regret at least Ω(min{√ dΛ + d, √ AT }).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 to the action a t . 
open questions: 
 Removing the revealing σ t assumption in the weak adversary setting The assumption we made in Section 4 that the variance is 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 Õ(√ AΛ + d elu )is achievable if the variance σ t is revealed at the end of round t. We answer this question affirmatively for the special case where σ t ∈ {0, 1}. More details can be found in Appendix H. How to extend this result to general values of σ t is an interesting open question. Handling the case where σ t is never revealed is even more challenging but is the ultimate goal.Removing the Gaussian noise assumption in the distributional setting Our Theorem 6.1 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 t is just σ A Related WorkM ⋆ (x t , a t )-sub-Gaussian? What if it is just a bounded noise with variance σ 2 M ⋆ (x t ,In this section, we review the literature in bandits/RL that obtains second-order regret bounds or other data-/instance-dependent 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 as stochastic multi-armed bandits (Audibert et al., 2009) , adversarial multi-armed bandits (Wei and Luo, 2018; Ito, 2021) , and adversarial linear bandits (Hazan and Kale, 2011; Ito and Takemura, 2023) . Key techniques in this line of work include replacing Hoeffding-style 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-dependent regret bounds in bandits have been extended to MDPs, leading to 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, secondorder bounds have been explored in both agnostic settings (Wei et 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 our findings. For instance, even if the second-order error E is O(1), they showed that the regret could still grow with Ω(T 1 /4 ). 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 to the small action regime, their bounds smoothly scale with the second-order 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 et 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 √ L ⋆ , 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 T have been derived by Foster et al. (2020) and Dann et al. (2023) for realizable and agnostic settings, respectively. Notably, the algorithm of Foster et al. (2020) has some similarity with our main algorithm, which we discuss further in the main text.Lemma B.1. For any 0 ≤ σ ≤ 1/2 and 0 ≤ ε ≤ σ/2, defineP σ = ® 2σ, with proba. 1/2, 0, with proba. 1/2, P + σ,ϵ = ® 2σ, with proba. σ+ϵ 2σ , 0, with proba. σ-ϵ 2σ , P - σ,ϵ = ® 2σ, with proba. σ-ϵ 2σ , 0, with proba. σ+ϵ 2σ . Denote by h σ , h + σ,ϵ , h - σ,ϵthe means of the three distributions respectively. We haveh σ = σ, h + σ,ϵ = σ + ϵ, and h - σ,ϵ = σ -ϵ. Let V σ , V + σ,ϵ , V - σ,ϵbe the variance of the three distributions respectively. We haveV σ , V + σ,ϵ , V - σ,ϵ ≤ σ 2 . Furthermore, D KL P - σ,ϵ ∥ P + σ,ϵ ≤ 4ϵ 2 σ 2 .Proof.D KL P - σ,ϵ ∥ P + σ,ϵ = σ -ϵ 2σ log σ -ϵ σ + ϵ + σ + ϵ 2σ log σ + ϵ σ -ϵ = ϵ 2σ log Å σ + ϵ σ -ϵ ã 2 = ϵ σ log Å 1 + 2ϵ σ -ϵ ã ≤ ϵ σ • 2ϵ σ -ϵ ≤ 4ϵ 2 σ 2 .Lemma B.2. For any two gaussian distributions N (µ 1 , σ 1 ) andN (µ 2 , σ 2 ), if | log σ 1 -log σ 2 | > 3, then D 2 H (N (µ 1 , σ 1 ), N (µ 2 , σ 2 )) ≥ 1 2 .Proof of Lemma B.2. Without loss of generality, assume σ 1 > e 3 σ 2 > 8σ 2 . The Hellinger divergence between two gaussian distributions writes Wang et al. (2024) ). For any distribution P and Q on any space X such that D 2 H (P, Q) ≤ 1 2 , we have for any function h : X → R,D 2 H (N (µ 1 , σ 1 ), N (µ 2 , σ 2 )) = 1 - 2σ 1 σ 2 σ 2 1 + σ 2 2 exp Å - (µ 1 -µ 2 ) 2 4(σ 2 1 + σ 2 2 ) ã ≥ 1 - 2σ 1 σ 2 σ 2 1 + σ 2 2 ≥ 1 - 2σ 1 /σ 2 (σ 1 /σ 2 ) 2 + 1 ≥ 1 2 . Lemma B.3 (Lemma 4.2 of|E P [h] -E Q [h]| ≤ 2 » (Var P (h) + Var Q (h))D 2 H (P, Q).Lemma B.4 (Lemma A.11 of Foster et al. (2021) ). For any distribution P and Q on any space X , we have for any function h : X → [0, R],|E P [h] -E Q [h]| ≤ » 2R(E P (h) + E Q (h))D 2 H (P, Q). In particular, E P [h] ≤ 3E Q [h] + 4RD 2 H (P, Q).Lemma B.5 (Strengthened Freedman's inequality (Theorem 9 of Zimmert and Lattimore (2022))).Let X 1 , X 2 , . . . , X T be a martingale difference sequence with a filtrationF 1 ⊆ F 2 ⊆ • • • such that E[X t |F t ] = 0 and E[|X t | | F t ] < ∞ almost surely. Then with probability at least 1 -δ, T t=1 X t ≤ 3 V T log Ç 2 max{U T , √ V T } δ å + 2U T log Ç 2 max{U T , √ V T } δ å , where V T = T t=1 E[X 2 t | F t ] and U T = max{1, max t∈[T ] |X t |}.C Omitted Proofs in Section 4.1Lemma C.1 (Theorem 15.2 of Lattimore and Szepesvári (2020)). For any integer A ≥ 2, any positive real number σ ∈ [0, 1], and time T > 0, there exists a context space X and a contextual bandit problem F ⊂ (X × A → R) with action set A = [A], d elu (F; 0) = A, and variances σ t ≤ σ for all t ∈ [T ] such that any algorithm will suffer a regret at least Ω(√ σ 2 AT ).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 = ∅ and the function classF = {f i (•) = (σ + ε)1(• = i) + σ1(• = 1) | i ∈ {2, 3, . . . , A}} ∪ {f 1 (•) = (σ -ε)1(• = i) + σ1(• = 1)},where the gap ε will be specified later with the constraint ε ≤ 2σ. Let P σ , P + σ,ϵ , and P - σ,ϵ be defined as in Lemma B.1. For any function f ∈ F, suppose the environment is such that if f (i) = σ, σ +ϵ, σ -ϵ, then the reward distribution is P σ , P + σ,ϵ , P - σ,ϵ respectively. Any environment and algorithm give rise to the distribution of history. Let P i denote the distribution generated by the environment following f i ∈ F together with the algorithm and expectations under P i will be denoted by E i . Let N T (a) = T t=1 1(a t = a) where a t is the action taken at time stept for t ∈ [T ]. Let i ⋆ = arg min j>1 E 1 [N T (j)]. Since A i=1 N T (i) = T , it holds that E 1 [N T (i ⋆ )] ≤ T /(A -1).For the two environments induced by f 1 and f i ⋆ , we haveE 1 [R T ] ≥ P 1 (N T (1) ≤ T /2) • T ε 2 and E i ⋆ [R T ] ≥ P i ⋆ (N T (1) > T /2) • T ε 2 .Then, by Bretagnolle-Huber inequality, we haveE 1 [R T ] + E i ⋆ [R T ] ≥ T ε 2 (P 1 (N T (1) ≤ T /2) + P i ⋆ (N T (1) > T /2)) ≥ T ε 4 exp(-D KL (P 1 ∥ P i ⋆ )).Then by the chain rule of KL divergence and Lemma B.1, we haveD KL (P 1 ∥ P i ⋆ ) = E 1 [N T (i ⋆ )]D KL P - σ,ϵ ∥ P + σ,ϵ ≤ 4T ε 2 (A -1)σ 2 .E 1 [R T ] + E i ⋆ [R T ] ≥ T ε 4 exp Å - 4T ε 2 (A -1)σ 2 ã .Then by choosing ε = (A -1)σ 2 /4T , we havemax i {E i [R T ]} ≥ Ω( √ σ 2 AT ).Lemma C.2. For any integer N, A, T ≥ 2, there exists a context space X and a deterministic(σ t = 0 for all t ∈ [T ]) contextual bandit problem F ⊂ (X × A → R) with action set A = [A] and d elu (F; 0) = N (A -1) such that any algorithm will suffer a regret at least Ω(min{T /N, AN }).Proof of Lemma C.2. Consider the function classF = {f (0) } ∪ f (i,j) i∈[N ],j∈[A-1] with the space of contexts X = {x (1) , . . . , x (N ) } and the set of actions A = [A]. For any i ∈ [N ], j ∈ [A -1], the function f (i,j) is defined as the following: For i ∈ [N ] and j ∈ [A -1], f (i,j) (x (i) , j) = 1, f (i,j) (x, k) = 0, ∀x ̸ = x (i) or ∀k ∈ [A -1] \ {j}. f (i,j) (x, A) = 1 2 , ∀x.Meanwhilef (0) (x, j) = 0, ∀x and ∀j ∈ [A -1] f (0) (x, A) = 1 2 , ∀x.The eluder dimension of this function class is N (A -1) since f (i,j) is uniquely identified by its value on (x (i) , j). We assume that x t is uniformly randomly chosen from X , andr t = f ⋆ (x t , a t ). That is, σ t = 0 for all t ∈ [T ].Fix any algorithm. Denote by P 0 the probability distribution when f ⋆ = f (0) and E 0 the expectation under P 0 . For any i ∈ [N ], j ∈ [A -1], denote by P (i,j) the probability distribution when f ⋆ = f (i,j) and E (i,j) the expectation underP (i,j) . Let N T (i, j) = T t=1 1[x t = x (i) , a t = j].Then the adversary decides f ⋆ based on the following rule: if there exists i ∈[N ], j ∈ [A -1] such that E 0 [N T (i, j)] ≤ 1 100 (8) then let f ⋆ = f (i,j) . If no i, j satisfies this, let f ⋆ = f (0) . If f ⋆ = f (0) , then we have E 0 [R T ] ≥ 1 2 E 0   i∈[N ],j∈[A-1] N T (i, j)   ≥ N (A -1) 2 • min i,j E 0 [N T (i, j)] ≥ N (A -1) 200 .On the other hand, if f ⋆ = f (i,j) , then we haveP 0 (N T (i, j) = 0) ≥ 99 100 .Then by Lemma B.4, we have P 0 (N T (i, j) = 0) ≤ 3P (i,j) (N T (i, j) = 0) + 4DP (i,j) (N T (i, j) = 0) ≥ 1 3 (P 0 (N T (i, j) = 0) -28E 0 [N T (i, j)]) ≥ 1/6.This in turn implies thatE (i,j) [R T ] ≥ 1 2 E (i,j) T t=1 1[x t = x (i) ] -N T (i, j) ≥ T 2N • P (i,j) (N T (i, j) = 0) ≥ T 12N .Combining the lower bounds for E 0 [R T ] and E (i,j) [R T ] finishes the proof.Proof of Theorem 4.1. If A > T and d > T , by Lemma C.2 with N = 1, we have lower bound Ω(T ). Below, we assume min{A, d} ≤ T .In order to prove the lower bound, we only need to show that for any fixed d, A, σ, T such that min{A, d} ≤ T , there exists two classes where one has lower bound Ω( σ 2 min{A, d}T ) and the other has lower bound Ω(min{d,√ AT }).If A ≤ d, then we invoke Lemma C.1 to obtain the lower bound of Ω( √ σ 2 AT ). Else if d ≤ A, we 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 Ω( √ σ 2 dT ). In all, we have shown that there is a lower bound of Ω( σ 2 min{A, d}T ). EQUATIONOutput {f t (x t , a) : a ∈ A t }, and feed to Contextual Bandit algorithm to receive a t ∈ A t .Call Contextual Bandit oracle to get F t+1 and x t+1 .6:EQUATIONand 2007)). Fix some positive parameter η > 0. Suppose we have function setsEQUATIONF 1 ⊃ F 2 ⊃ • • • ⊃ F T , and functions ℓ t : F t → R satisfies that η|ℓ t (f )| ≤ 1 2 for any f ∈ F t . The prediction rule q t (f ) = t-1 τ =1 (1-ηℓτ (f )) g∈F t t-1 τ =1 (1-ηℓτ (g)) f ∈ F t , 0 f ̸ ∈ F t , ensures for any f ⋆ ∈ F T , T t=1 Ñ f ∈Ft q t (f )ℓ t (f ) é - T t=1 ℓ t (f ⋆ ) ≤ log |F| η + η T t=1 ℓ t (f ⋆ ) 2 . Proof. Define w t (f ) = t τ =1 (1 -ηℓ τ (f )) and W t = f ∈Ft w t (f ). log W t W t-1 = log f ∈Ft w t (f ) f ∈Ft-1 w t-1 (f ) ≤ log f ∈Ft w t-1 (f )(1 -ηℓ t (f )) f ∈Ft w t-1 (f ) (i) = log Ñ f ∈Ft q t (f )(1 -ηℓ t (f )) é (ii) = log Ñ 1 -η f ∈Ft q t (f )ℓ t (f ) é (iii) = -η f ∈Ft q t (f )ℓ t (f ),where in (i) we use the definition of q t , in (ii) we use the fact that f ∈Ft q t (f ) = 1, and in (iii) we use the inequality log(1 -x) ≤ -x for any x < 1. Therefore,T t=1 f ∈Ft q t (f )ℓ t (f ) ≤ 1 η log W 0 W T (i) ≤ log |F| η - 1 η log w T (f ⋆ ) = log |F| η - 1 η T t=1 log(1 -ηℓ t (f ⋆ )) (ii) ≤ log |F| η - 1 η T t=1 (-ηℓ t (f ⋆ ) -η 2 ℓ t (f ⋆ ) 2 ) = log |F| η + T t=1 ℓ t (f ⋆ ) + η T t=1 ℓ t (f ⋆ ) 2 ,where in (i) we use the fact that W 0 = |F| and W T ≥ w T (f ⋆ ) for any f ⋆ ∈ F t , and in (ii) we use the fact that η|ℓ t (f ⋆ )| ≤ 1 2 and also the inequality log(1 -x) ≥ -x -x 2 for any |x| ≤ 1 2 .Lemma D.2. Suppose for any x ∈ X , a ∈ A, f ∈ F, we always have f (x, a) ∈ [0, 1], the reward r t ∈ [0, 1] and for any f, f ′ ∈ F t , we always havemax a∈At |f (x t , a) -f ′ (x t , a)| ≤ ∆.Then for the output f t according to Algorithm 4, we have with probability at least 1 -δ,T t=1 (f t (x t , a t ) -r t ) 2 - T t=1 (f ⋆ (x t , a t ) -r t ) 2 ≤ 16(σ 2 + ∆) log (|F|/δ) .Proof. We first notice that with our choice of η = 1 4(σ 2 + ∆) , for any f ∈ F t we haveη| lt (f )| ≤ 2η|f (x t , a t ) -f t (x t , a t )| ≤ 2η max f ′ ∈Ft |f (x t , a t ) -f ′ (x t , a t )| ≤ 2 ∆ 4(σ 2 + ∆) ≤ 1 2where lt is defined in Eq. ( 10). According to Lemma D.1, we haveT t=1 f ∈Ft q t (f ) lt (f ) - T t=1 lt (f ⋆ ) ≤ log |F| η + η T t=1 lt (f ⋆ ) 2 ,By the definition of f t in Eq. ( 9) and lt in Eq. ( 10), we haveEQUATION)We notice thatlt (f ⋆ ) = 2(f t (x t , a t ) -f ⋆ (x t , a t ))(r t -f ⋆ (x t , a t ))is a martingale difference sequence, and we further have| lt (f ⋆ ) 2 | ≤ 4 ∆2 and Var t ( lt (f ⋆ ) 2 ) ≤ 4(f t (x t , a t ) -f ⋆ (x t , a t )) 4 E t [(r t -f ⋆ (x t , a t )) 4 ] ≤ 4(f t (x t , a t ) -f ⋆ (x t , a t )) 4 E t [(r t -f ⋆ (x t , a t )) 2 ] = 4(f t (x t , a t ) -f ⋆ (x t , a t )) 4 σ 2 .Hence according to Freedman inequality (Freedman, 1975), we have with probability 1 -δ,T t=1 lt (f ⋆ ) 2 ≤ 2 Ã T t=1 4(f t (x t , a t ) -f ⋆ (x t , a t )) 4 σ 2 log 1 δ + 2 • 4 ∆2 log 1 δ ≤ 2 Ã T t=1 (f t (x t , a t ) -f ⋆ (x t , a t )) 2 σ 2 • 4 ∆2 log 1 δ + 2 • 4 ∆2 log 1 δ ≤ T t=1 (f t (x t , a t ) -f ⋆ (x t , a t )) 2 σ 2 + 12 ∆2 log 1 δ ,where in the second inequality we use the fact that |f t (x t , a t ) -f ⋆ (x t , a t )| ≤ ∆, and in the last inequality we use the AM-GM inequality. Hence, with our choice of η = 1 4(σ 2 + ∆) , we haveT t=1 (f t (x t , a t ) -r t ) 2 -(f ⋆ (x t , a t ) -r t ) 2 ≤ log |F| η + 4η T t=1 lt (f ⋆ ) 2 - T t=1 (f t (x t , a t ) -f ⋆ (x t , a t )) 2 ≤ 4(σ 2 + ∆) log |F| + 12 ∆2 log 1 δ ≤ 16(σ 2 + ∆) log |F| δwhere in the last inequality we use the fact that ∆ ≤ 1.Lemma D.3. Suppose for any x ∈ X , a ∈ A, f ∈ F, we always have f (x, a) ∈ [0, 1], the reward r t ∈ [0, 1] and for any f, f ′ ∈ F t , we always havemax a∈At |f (x t , a) -f ′ (x t , a)| ≤ ∆.Then for the output f t according to Algorithm 4, we have with probability at least 1 -δ,T t=1 a∈A p t (a)(f t (x t , a) -f ⋆ (x t , a)) 2 ≤ 48(σ 2 + ∆) log (2|F|/δ) .Proof. We use F t denote the filtration constructed by F t = σ(x 1:t , a 1:t , r 1:t ). And we letM t = (f t (x t , a t ) -r t ) 2 -(f ⋆ (x t , a t ) -r t ) 2 .Then we have |M t | ≤ 2 ∆. According to (Foster and Rakhlin, 2020 , Lemma 1, Lemma 4), we have with probability at least 1 -δ/2, T t=1 a∈Ap t (a)(f t (x t , a) -f ⋆ (x t , a)) 2 ≤ 2 T t=1 (f t (x t , a t ) -r t ) 2 -(f ⋆ (x t , a t ) -r t ) 2 + 16 ∆ log Å 2 δ ã .Next, according to Lemma D.2, we have with probability at least 1 -δ/2, T t=1(f t (x t , a t ) -r t ) 2 -(f ⋆ (x t , a t ) -r t ) 2 ≤ 16(σ 2 + ∆) log Å 2|F| δ ã .Hence we obtain that with probability at least 1 -δ,T t=1 a∈A p t (a)(f t (x t , a) -f ⋆ (x t , a)) 2 ≤ 48(σ 2 + ∆) log (2|F|/δ) . D.2 Proof of Theorem 4.2For simplicity, we define the following sets based on Algorithm 1:T 1 = {t ∈ [T ],'if' condition in Line 6 holds in Algorithm 1}, andEQUATION)We first show that with high probability, the true model f ⋆ ∈ F t , where F t is defined in Eq. ( 5) in Algorithm 1.Lemma D.4. When the function class F t iteratively defined in Eq. ( 5), with probability at least 1 -δ, we have f ⋆ ∈ F t for any 1 ≤ t ≤ T .Proof. We will prove the result by induction on t. For t = 1, since F 1 = F and according to Assumption 2.1 we have f ⋆ ∈ F 1 . Next, we will assume that f ⋆ ∈ F t-1 and attempt to provef ⋆ ∈ F t . Since r τ = f ⋆ (x τ , a τ ) + ϵ t for any 1 ≤ τ ≤ t -1, we have t-1 τ =1 w τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 = t-1 τ =1 w τ (f t (x τ , a τ ) -r τ ) 2 - t-1 τ =1 w τ (f ⋆ (x τ , a τ ) -r τ ) 2 + 2 t-1 τ =1 w τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ ))(r τ -f ⋆ (x τ , a τ )) ≤ 2 t-1 τ =1 w τ ϵ τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ )),where the last inequality uses the definition that f t is the minimizer oft-1 τ =1 w τ (f (x τ , a τ ) -r τ ) 2 in (6).We notice that w τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ ))ϵ τ is a martingale difference sequence, and since|w τ | ≤ 1 σ 2 , max 1≤τ ≤t-1 |w τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ ))ϵ τ | ≤ 1 σ 2 , t-1 τ =1 (w τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ ))ϵ τ |) 2 ≤ T σ 4 .According to the Strengthened Freeman's Inequality (Lemma B.5), and noticing thatE τ -1 [ϵ 2 τ ] = σ 2 for any 1 ≤ τ ≤ t -1, with probability at least 1 -δ T , for any f ∈ F, t-1 τ =1 w τ ϵ τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ )) ≤ 3 Ã t-1 τ =1 w 2 τ σ 2 (f t (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 log |F|T 2 δσ 2 + 2 max 1≤τ ≤t-1 |w τ ϵ τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ ))| log |F|T 2 δσ 2 (i) ≤ 3 Ã t-1 τ =1 w τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ ) 2 L + 2 sup τ ≤t-1 w τ |f t (x τ , a τ ) -f ⋆ (x τ , a τ )|L (ii) ≤ 3 Ã t-1 τ =1 w τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 L + 2 sup τ ≤t-1 Ã L + τ -1 s=1 w s (f t (x s , a s ) -f ⋆ (x s , a s )) 2 L ≤ 5 Ã t-1 τ =1 w τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 L + L (iii) ≤ 1 2 t-1 τ =1 w τ (f t (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 + 51L,where in (i) we use the fact that w τ ≤ 1 /σ 2 for any τ according to the definition of w τ in Algorithm 1 and using the definition L ≜ |F |T 2 δσ 2 , in (ii) we use the fact thatw τ ≤ » 1 + τ -1 s=1 w s (f s (x s , a s ) -f ⋆ (x s , a s )) 2 |f τ (x τ , a τ ) -f ⋆ (x τ , a τ )| √ Laccording to the definition of w τ in Algorithm 1 since f τ , f ⋆ ∈ F τ by induction hypothesis, and finally in (iii) we use AM-GM inequality. And this proves the induction hypothesis of f ⋆ ∈ F t .Therefore, we obtain that with probability at least 1 -δ for any1 ≤ t ≤ T , f ⋆ ∈ F t .The following lemma is a useful result of Eluder dimension.Lemma D.5. For any λ ≥ 0 and α ∈ (0, 1], we haveT t=1 min ® λ, sup f,f ′ ∈Ft (f (x t , a t ) -f ′ (x t , a t )) 2 α 2 T + t-1 τ =1 (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ´≤ d elu (α) (λ + log T ) .Proof. This proof follows Lemma 5.1 of Ye et al. (2023) . Create T bins, and call them B 1 , . . . , B T . Each bin is empty at the beginning. Below we will add elements in {1, 2, . . . , T } to the bins.Suppose that {1, 2, . . . , t -1} have been assigned to their bins. To assign t to a bin, we find the smallest n ∈ [T ] such that "∃ϵ ≥ α, (x t , a t ) is ϵ-independent to the elements in B n with respect to F t ." We let n t to be the n we found, and put element i into bin B ni .By the procedure above, we can conclude that for each t, "∀ϵ ≥ α, (x t , a t ) is ϵ-dependent on all of {B 1 , . . . , B nt-1 } with respect to F t ." Next, we show that this necessitates the following: for anyf, f ′ ∈ F t , (f (x t , a t ) -f ′ (x t , a t )) 2 ≤ α 2 + 1 n t -1 t-1 τ =1 (f (x τ , a τ ) -f ′ (x τ , a τ )) 2This is because if otherwise, then there exists f, f ′ ∈ F t and a binB n ∈ {B 1 , . . . , B nt-1 } which (x t , a t ) is ϵ-dependent on ∀ϵ ≥ α, but (f (x t , a t ) -f ′ (x t , a t )) 2 > α 2 + τ ∈Bn (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 . Choose ξ = max ß max τ ∈Bn |f (x τ , a τ ) -f ′ (x τ , a τ )|, α ™ ≥ α. Clearly, |f (x τ , a τ ) -f ′ (x τ , a τ )| ≤ ξ for all τ ∈ B n , but |f (x t , a t ) -f ′ (x t , a t )| > α, contradicting that (x t , a t ) is ϵ-dependent on B n ∀ϵ ≥ 1 / √ T .We obtain thatsup f,f ′ ∈Ft (f (x t , a t ) -f ′ (x t , a t )) 2 α 2 T + t-1 τ =1 (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ≤ 1 n t -1 .Let |B 1 |, . . . , |B T | be the size of the bins after all elements are added. By the eluder dimension definition (Definition 2.1), we know |B n | ≤ d elu (α) for all n. Therefore, we haveT t=1 min ® λ, sup f,f ′ ∈Ft (f (x t , a t ) -f ′ (x t , a t )) 2 1 + t-1 τ =1 (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 = t:nt=1 λ + T n=2 t:nt=n 1 n -1 ≤ λd elu (α) + T n=2 d elu (α) n -1 ≤ λd elu (α) + d elu (α) log T.Lemma D.6. Suppose we have positive number B such that for any t ∈ [T ], w t ∈ [0, B]. Then for any λ ≥ 0, we haveT t=1 min ® λ, sup f,f ′ ∈Ft w t (f (x t , a t ) -f ′ (x t , a t )) 2 1 + t-1 τ =1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ≤ 3d elu (1/ √ BT )(λ + log T ) log(BT ).Proof. We define setT i = {t ∈ [T ] : 2 i-1 /T ≤ w t ≤ 2 i /T } for any 1 ≤ i ≤ log(BT ). and T 0 = {t ∈ [T ] : w t ∈ [0, 1/T ]}. Then we have [T ] ⊂ ∪ log(B/A) i=1 T i .Additionally, we notice that for any 1 ≤ i ≤ log(BT ) and t ∈ T i , we havew t (f (x t , a t ) -f ′ (x t , a t )) 2 1 + t-1 τ =1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ≤ w t (f (x t , a t ) -f ′ (x t , a t )) 2 1 + t∈Ti w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 (i) ≤ 2 • (f (x t , a t ) -f ′ (x t , a t )) 2 1/(2 i /T ) + τ ∈Ti,τ <t (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 (ii) ≤ 2 • (f (x t , a t ) -f ′ (x t , a t )) 2 1/B + τ ∈Ti,τ <t (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ,where in (i) we use the fact that for any τ ∈ T i , w τ ∈ [2 i-1 /T, 2 i /T ], and in (ii) we use the fact that 2 i /T ≤ B. According to Lemma D.5, we have for any1 ≤ i ≤ log(BT ). t∈Ti min ® λ, sup f,f ′ ∈Ft (f (x t , a t ) -f ′ (x t , a t )) 2 1/B + τ ∈Ti,τ <t (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ´≤ d elu (1/ √ BT )(λ + log |T i |) ≤ d elu (1/ √ BT )(λ + log T ).Next we notice that for those t ∈ T 0 , we have w t ≤ 1/T , which implies thatt∈Ti min ® λ, sup f,f ′ ∈Ft w t (f (x t , a t ) -f ′ (x t , a t )) 2 1 + τ <t w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ´≤ T • 1/T = 1. T i=1 min ® λ, sup f,f ′ ∈Ft w t (f (x t , a t ) -f ′ (x t , a t )) 2 1 + t-1 τ =1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ≤ 2d elu (1/ √ BT )(λ + log T ) log(BT ) + 1 ≤ 3d elu (1/ √ BT )(λ + log T ) log(BT ).Next, we present a lemma bounding the single-step regret in terms of g t defined in Eq. ( 4) in Algorithm 1.Lemma D.7. Suppose f ⋆ ∈ F t for any 1 ≤ t ≤ T . For any 1 ≤ t ≤ T we havemax a∈At f ⋆ (x t , a) -f ⋆ (x t , a t ) ≤ 21 √ L • max a g t (a)Proof. In the following, we assume f ⋆ ∈ F t always holds. Leta ucb t = arg max a∈At max f ∈Ft f (x t , a).Then we havemax a∈At f ⋆ (x t , a) -f ⋆ (x t , a t ) (i) ≤ max f ∈Ft f (x t , a ucb t ) -f ⋆ (x t , a t ) = max f ∈Ft f (x t , a ucb t ) -min f ∈Ft f (x t , a ucb t ) + min f ∈Ft f (x t , a ucb t ) -max f ∈Ft f (x t , a t ) + max f ∈Ft f (x t , a t ) -f ⋆ (x t , a t ) ≤ 2 max f,f ′ ∈Ft max a∈At |f (x t , a) -f ′ (x t , a)| + min f ∈Ft f (x t , a ucb t ) -max f ∈Ft f (x t , a t ) (ii) ≤ 2 max f,f ′ ∈Ft max a∈At |f (x t , a) -f ′ (x t , a)| (iii) ≤ 21 max f,f ′ ∈Ft max a∈At |f (x t , a) -f ′ (x t , a)| » 1 + τ <t w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 × √ L.Here in (i) we use the fact that f ⋆ ∈ F t , and in (ii) we first use the definition of A t in Line 4 of Algorithm 1 that there exists f ′ ∈ F t such that a t = max a∈A f ′ (x t , a), which impliesmin f ∈Ft f (x t , a ucb t ) ≤ f ′ (x t , a ucb t ) ≤ f ′ (x t , a t ) ≤ max f ∈Ft f (x t , a t ).In (iii) we use the definition of Eq. ( 5) that for any f, f ′ ∈ F t ,1 + τ <t w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ≤ 1 + 102L ≤ 103L.Our next lemma provides an upper bound to the expectation of regret for rounds falling into T 1 .Lemma D.8. Suppose f ⋆ ∈ F t for any 1 ≤ t ≤ T . We havet∈T1 (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) ≤ Õ Ç σ 2 d elu √ L ∆ + d elu L å ,where we use Õ to hide constants and factors of log T σ∆ . Proof. We first define M = log 1 ∆ √T and β = 21 √ L and recall the definition of g t in Eq. (4).g t (a t ) = sup f,f ′ ∈Ft |f (x t , a t ) -f ′ (x t , a t )| » 1 + t-1 τ =1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 .In the following, when with no ambiguity, we write g t = g t (a t ). Since for any f ∈ F, we have f (x, a) ∈ [0, 1], we have |g t | ≤ 1. Also notice that for any t ∈ T 1 , we have g t ≥ ∆ according to Algorithm 1.We further define subsetsT 11h , T 12h ⊂ [T ] for every h = ∆ • 2 i with i = 0, 1, 2, • • • , M -1 as T 11h ≜ T 1 ∩ {t : h ≤ g t ≤ 2h} ∩ ß t : w t = 1 σ 2 ™ ,andT 12h ≜ T 1 ∩ {t : h ≤ g t ≤ 2h} ∩ ß t : w t ̸ = 1 σ 2 ™ .Since ∆ ≤ g t ≤ 1 for t ∈ T 1 , we haveEQUATIONNext, we fix h, we analyze T 11h and T 12h separately. For those t ∈ T 11h , we have:t∈T 11h (max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t )) (i) ≤ t∈T 11h min    1, β max f,f ′ ∈Ft |f (x t , a t ) -f ′ (x t , a t )| » 1 + τ <t w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2    (ii) = t∈T 11h min{1, βg t } (iii) ≤ min{1, 2βh}|T 11h |,where in (i) we use Lemma D.7 and the fact that |f ⋆ (x, a) -f ⋆ (x, a ′ )| ≤ 1 for any action a, a ′ ∈ A, in (ii) we use the definition of g t in Eq. ( 4) and the simplification g t := g t (a t ), and in (iii) we use the definition of T 11h that for any t ∈ T 11h we always have g t ≤ 2h. Next, we bound the cardinality of each T 11h :|T 11h | (i) ≤ t∈T 11h I {g t ≥ h} I ß w t = 1 σ 2 ™ (ii) ≤ 1 h t∈T 11h min {h, g t } I ß w t = 1 σ 2 ™ (iii) ≤ σ h t∈T11 min ß h σ , √ w t g t ™ (iv) ≤ σ h » |T 11h | Ã t∈T 11h min ß h 2 σ 2 , w t g 2 t ™ (v) = σ h » |T 11h | Ã t∈T 11h min ® h 2 σ 2 , sup f,f ′ ∈Ft w t (f (x t , a t ) -f ′ (x t , a t )) 2 1 + τ ≤t-1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 (vi) ≤ σ h 3|T 11h |d elu Å σ √ T ã Å log T + h 2 σ 2 ã log Å T σ 2 ãwhere in (i) we use the definition of T 11h , in (ii) we merely use the inequality that I{g ≥ h} ≤ 1 h min{g, h} for any g, h ≥ 0, in (iii) we use the the fact that I{w t = 1/σ 2 } ≤ √ w t σ since w t ≤ 1/σ 2 always holds, in (iv) we use Cauchy-Schwarz inequality, in (v) we use the definition of g t in Eq. ( 4), and finanly in (vi) we use Lemma D.6 with λ = h 2 /σ 2 and also w t ∈ [0, 1 /σ 2 ]. Therefore, we obtain that|T 11h | ≤ 3 Å σ 2 log T h 2 + 1 ã d elu Å σ √ T ã log Å T σ 2 ã , which implies t∈T 11h (max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t )) ≤ min {6βh, 3} Å σ 2 log T h 2 + 1 ã d elu Å σ √ T ã log Å T σ 2 ã ≤ Å 6βσ 2 log T h + 3 ã d elu Å σ √ T ã log Å T σ 2 ã ≤ Ç 126σ 2 log T √ L h + 3 å d elu Å σ √ T ã log Å T σ 2 ã .Next, we will deal with those t in T 12h . Similar to the proof for T 11h , for any fixed h we haveEQUATIONAnd we can upper bound the cardinality of T 12h as|T 12h | = t∈T 12h I {g t ≥ h} I ß w t ̸ = 1 σ 2 ™ ≤ 1 h t∈T 12h min {h, g t } I ß w t ̸ = 1 σ 2 ™ (i) = 1 h t∈T 12h min    h, sup f,f ′ ∈Ft |f (x t , a t ) -f ′ (x t , a t )| » 1 + t-1 τ =1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2    I ß w t ̸ = 1 σ 2 ™ (ii) ≤ 1 h t∈T 12h min ® h, √ L sup f,f ′ ∈Ft w t (f (x t , a t ) -f ′ (x t , a t )) 2 1 + t-1 τ =1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 (iii) ≤ 3 h d elu Å σ √ T ã Ä√ L log T + h ä log Å T σ 2 ã ,where in (i) we use the definition of g t in Eq. ( 4), in (ii) we use the definition of w t that when w t ̸ = 1 /σ 2 , we always havew t = min f,f ′ ∈Ft » 1 + t-1 τ =1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 |f (x t , a t ) -f ′ (x t , a t )| √ L ,and (iii) is according to Lemma D.6 and the fact thatw t ∈ [0, 1 /σ 2 ].Therefore, according to Eq. ( 15), we obtain thatt∈T 12h (max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t )) ≤ min{1, 2βh}|T 12h | ≤ Ä 6β √ L log T + 3 ä d elu Å σ √ T ã log Å T σ 2 ã = (126L log T + 3) d elu Å σ √ T ã log Å T σ 2 ã .Finally, recalling Eq. ( 14), if we sum the regret obtained above over h, we obtaint∈T1 (max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t )) = M -1 i=0   t∈T 11(2 i ∆) Å max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t ) ã + t∈T 12(2 i ∆) Å max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t ) ã   ≲ M -1 i=0 ñ d elu σ 2 √ L (2 i ∆) + d elu + d elu L + d elu ô log Å T σ ã (using d elu ≜ d elu ( 1 /T 2 ) from Section 2 and the fact that d elu (α) is decreasing in α) = Õ Ç σ 2 d elu √ L ∆ + d elu L å .Finally, we provide a lemma which upper bounds the expectation of regret for rounds falling into T 2 .Lemma D.9. Suppose that for any t ∈ [T ], we havef ⋆ ∈ F t . With ∆ = 11∆ √ L, we have with probability at least 1 -δ, t∈T2 (max a f ⋆ (x t , a) -f ⋆ (x t , a t )) ≤ 16 (σ 2 + ∆)T log Å 4|F| δ ã + 3 log Å 2 δ ã .Proof. We let a ⋆ t = arg max a f ⋆ (x t , a). According to (Foster and Rakhlin, 2020 , Lemma 3), we havea∈A p t (a)(f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a)) ≤ 2A γ + γ 4 a∈A p t (a) (f t (x t , a) -f ⋆ (x t , a)) 2Summing this inequality up for all t ∈ T 2 , we obtaint∈T2 a∈A p t (a)(f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a)) ≤ 2A|T 2 | γ + γ 4 t∈T2 a∈A p t (a)(f t (x t , a t ) -f ⋆ (x t , a)) 2 .We notice that for any t ∈ T 2 , we havesup f,f ′ ∈Ft max a∈A |f (x t , a) -f ′ (x t , a)| » 1 + t-1 τ =1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ≤ ∆.According to the definition ofF t , for any f, f ′ ∈ F t , t-1 τ =1 w τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ≤ 102L, which implies that for any f, f ′ ∈ F t , max a∈A |f (x t , a) -f ′ (x t , a)| ≤ ∆ √ 1 + 102L ≤ ∆.Hence according to Lemma D.2, with probability at least 1 -δ/2, we haveT t=1 a∈A p t (a)(f t (x t , a) -f ⋆ (x t , a)) 2 ≤ 48(σ 2 + ∆) Å 4|F| δ ã . Further noticing that |T 2 | ≤ T , with choice γ = AT 4( ∆+σ 2 ) log(|F |/δ) , we have with probability at least 1 -δ/2, t∈T2 a∈A p t (a)(f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a)) ≤ 48(σ 2 + ∆)T log Å 4|F| δ ã .Finally, since we always have 0 ≤ f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a) ≤ 1, according to Bernstein inequality we have with probability at least1 -δ/2, t∈T2 (f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a t )) - t∈T2 a∈A p t (a)(f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a)) ≤ 2 t∈T2 a∈A p t (a)(f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a)) 2 log Å 2 δ ã + 2 log Å 2 δ ã ≤ t∈T2 a∈A p t (a)(f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a)) 2 + 3 log Å 2 δ ã ≤ t∈T2 a∈A p t (a)(f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a)) + 3 log Å 2 δ ã ,where in the second inequality we use the AM-GM inequality and in the last inequality we use the fact that 0 ≤ f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a) ≤ 1. Therefore, we obtain that with probability at least 1 -δ,t∈T2 (f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a t )) ≤ 2 t∈T2 a∈A p t (a)(f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a)) + 3 log Å 2 δ ã ≤ 16 (σ 2 + ∆)T log Å 4|F| δ ã + 3 log Å 2 δ ã .Proof of Theorem 4.2. Lemma D.4 and Lemma D.8 gives that with probability at least 1 -δ/2 we havet∈T1 (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) = Õ Ç σ 2 d elu √ L ∆ + d elu L å .Additionally, according to Lemma D.9, we have with probability at least 1 -δ/2 t∈T2 (maxa∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) ≤ 16 » (σ 2 + ∆)T L + 3L.Hence when ∆ = σ 2 /(11√ L) (so ∆ = σ 2 ), with probability at least 1 -δ, we havet∈[T ] (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) = t∈T1 (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) + t∈T2 (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) = Õ Ä√ σ 2 AT L + d elu L ä .Then noticing that L = log |F |T 2 σ 2 δ and that σ ≥ 1 AT finishes the proof.In this section, we will prove Corollary 4.1.Proof of Corollary 4.1. Based on the variance σ 2 t at round t, Algorithm 2 classify rounds into T 0 , • • • , T log T . We will bound the regret of rounds in T i separately.According to Algorithm 2, for t ∈ T i with 0 ≤ i ≤ log(AT ), we always have 1 /AT ≤ σ t ≤ 2 i /AT . Hence, according to Theorem 4.2, with probability at least 1 -δ/ log(AT ), we havet∈[Ti] (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) = Õ A|T i | • (2 i /(AT )) 2 log Å |F| δ ã + d elu log Å |F| δ ã .We further observe that for 1 ≤ i ≤ log(AT ), σ t ≥ 2 i-1 /AT , which implies that|T i | • (2 i /(AT )) 2 ≤ 4 t∈Ti σ 2 t .And for i = 0, we have|T i | • (2 i /(AT )) 2 ≤ T • 1 (AT ) 2 ≤ 1 AT .Therefore, with probability at least 1 -δ, we haveT t=1 (max a∈A f ⋆ (x t , a) -f ⋆ (x t , a t )) = Õ Ñ log(AT ) i=0 A|T i | • (2 i /(AT )) 2 log Å |F| δ ã + d elu log Å |F| δ ã é = Õ Ñ log(AT ) i=1 Ã A t∈Ti σ 2 t log Å |F| δ ã + d elu log Å |F| δ ã é (i) = Õ Ñ Ã log(AT ) • log(AT ) i=1 A t∈Ti σ 2 t log Å |F| δ ã + d elu log Å |F| δ ã é = Õ Ñ Ã A T t=1 σ 2 t log Å |F| δ ã + d elu log Å |F| δ ã é ,where in (i) we use Cauchy-Schwarz inequality.Algorithm 5 VarUCB 1: Define:L = Θ(log(|F|T /δ)), F 0 = F. 2: Define: K ≜ ⌈log T ⌉. Let Ψ 1,k = ∅ for k = 1, 2, . . . , K, K + 1. 3: for t = 1, 2, . . . do 4:Define confidence set:EQUATION)β t,k = 10 • 2 -k τ ∈Ψ t,k w 2 τ (r τ -ft,k (x τ , a τ )) 2 L + L 2 if k ≤ K and 2 2k ≥ 80L |Ψ t,k | if k ≤ K and 2 2k < 80L 5:Receive x t , and defineA t = {a ∈ A : ∃f ∈ F t : a ∈ arg max a ′ ∈A f (x t , a ′ )}. 6: Define g t,k (a) = max f,f ′ ∈Ft |f (x t , a) -f ′ (x t , a)| » 2 -2k L 2 + τ ∈Ψ t,k w 2 τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 . 7: Let k t be the smallest k ∈ [K] such that max a∈At g t,k (a) ≥ 2 -k . (Let k t = K + 1 if such k t does not exist) 8: Play a t = ® arg max a∈At g t,kt (a) if k ≤ K arg max a∈At max f ∈Ft f (x t , a) otherwise, and receive r t . 9:Define g t = g t,kt (a t ). Let w t = 2 -kt /g t if k t ≤ K and w t = 1 if k t = K + 1. 10: Update Ψ t+1,kt ← Ψ t,kt ∪ {t} and Ψ t+1,k ← Ψ t,k for k ̸ = k t .F Algorithm for the Strong Adversary Case and Omitted Proofs in Section 5In this section, we introduce and analyze Algorithm 5, an algorithm that achieves Õ(d elu Λ log |F| + d elu log |F|) regret bound against strong adversary.Algorithm 5 is an extension of the SAVE algorithm (Zhao et al., 2023) from linear function approximation to general function approximation. The algorithm maintains K + 1 = Θ(log T ) bins denoted as {Ψ t,k }, k = 1, 2, . . . , K + 1, which forms a partition of [t -1] (i.e., every time index τ < t falls into exactly one of these bins). Each bin k can form a confidence function set like in standard LinUCB using samples in Ψ t,k . The overall confidence set F t is the intersection of the confidence sets of individual bins (Line 4).Upon receiving the context x t , the learner form an active action set that contains plausible actions (Line 5). The next step is to decide which bin t should go to. This is done by leveraging the uncertainty measure g t,k (a) for bin k and action a (Line 6), which measures how uncertain the reward of action a is, given prior samples in bin k. The measure g t,k (a) corresponds to the quantity ∥a∥ Σ -1 t,k usually seen in linear contextual bandits, where Σ t,k is the covariance matrix formed by the samples in Ψ t,k . The algorithm finds the smallest k such that there exists an action with relative large uncertainty g t,k (a) ≥ 2 -k (Line 7). The learner would then choose this action in order to gain relatively large shrinking in bin k's confidence set (Line 8), and put time t in bin k. The sample at time t is assigned a weight w t 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.1-Lemma F.5. Lemma F.1. Suppose that f ⋆ ∈ F t-1 . Then with probability at least 1 -δ/T , for all k ∈ [K] we haveτ ∈Ψ t,k w 2 τ ( ft,k (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 ≤ 10 • 2 -2k Ñ τ ∈Ψ t,k w 2 τ σ 2 τ L + L 2 é .Proof. Since r τ = f * (x τ , a τ ) + ϵ t , we haveEQUATIONwhere 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 log(|F|T /δ) for some large enough universal constant C (specified in Line 1 of Algorithm 5), the last expression in Eq. ( 17) can be further bounded byEQUATIONfor all k with probability at least 1 -δ/T by a union bound over k and ft,k .For any τ ∈ Ψ t,k , by the definition of w τ (Line 9 of Algorithm 5), we havew τ | ft,k (x τ , a τ ) -f ⋆ (x τ , a τ )| ≤ 2 -k /g τ • | ft,k (x τ , a τ ) -f ⋆ (x τ , a τ )| = 2 -k min f,f ′ ∈Fτ » 2 -2k L 2 + s∈Ψ τ,k w 2 s (f (x s , a s ) -f ′ (x s , a s )) 2 |f (x τ , a τ ) -f ′ (x τ , a τ )| • | ft,k (x τ , a τ ) -f ⋆ (x τ , a τ )| ≤ 2 -k 2 -2k L 2 + s∈Ψ τ,k w 2 s ( ft,k (x s , a s ) -f ⋆ (x s , a s )) 2 . (f ⋆ , ft,k ∈ F t-1 ⊂ F τ by assumption)Combining this and Eq. ( 18), we getτ ∈Ψ t,k w 2 τ ( ft,k (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 ≤ 2 -k Ñ max τ ∈Ψ t,k 2 -2k L 2 + s∈Ψ τ,k w 2 s ( ft,k (x s , a s ) -f ⋆ (x s , a s )) 2 é Ñ τ ∈Ψ t,k w 2 τ σ 2 τ L + L é ≤ 2 -k Ñ 2 -2k L 2 + τ ∈Ψ t,k w 2 τ ( ft,k (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 é Ñ τ ∈Ψ t,k w 2 τ σ 2 τ L + L é .Solving the inequality yieldsτ ∈Ψ t,k w 2 τ ( ft,k (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 ≤ 10 • 2 -2k Ñ τ ∈Ψ t,k w 2 τ σ 2 τ L + L 2 é . Lemma F.2. Suppose that f ⋆ ∈ F t-1 . Then for all k ∈ [K] satisfying 2 2k ≥ 80L, we have with probability at least 1 -δ/T , τ ∈Ψ t,k w 2 τ σ 2 τ ≤ 8 τ ∈Ψ t,k w 2 τ Ä r τ -ft,k (x τ , a τ ) ä 2 + 4L, τ ∈Ψ t,k w 2 τ Ä r τ -ft,k (x τ , a τ ) ä 2 ≤ 2 τ ∈Ψ t,k w 2 τ σ 2 τ + L.Proof. With L = C log(|F|T /δ) for some large enough universal constant C, we haveτ ∈Ψ t,k w 2 τ σ 2 τ ≤ 2 τ ∈Ψ t,k w 2 τ ϵ 2 τ + L (Freedman's inequality) ≤ 4 τ ∈Ψ t,k w 2 τ Ä r τ -ft,k (x τ , a τ ) ä 2 + 4 τ ∈Ψ t,k w 2 τ Ä ft,k (x τ , a τ ) -f ⋆ (x τ , a τ ) ä 2 + L ≤ 4 τ ∈Ψ t,k w 2 τ Ä r τ -ft,k (x τ , a τ ) ä 2 + 40 • 2 -2k Ñ τ ∈Ψ t,k w 2 τ σ 2 τ L + L 2 é + L (by Lemma F.1) ≤ 4 τ ∈Ψ t,k w 2 τ Ä r τ -ft,k (x τ , a τ ) ä 2 + 2L + 1 2 τ ∈Ψ t,k w 2 τ σ 2 τ .Rearranging gives the first inequality. For the second inequality, note that we haveτ ∈Ψ t,k w 2 τ Ä r τ -ft,k (x τ , a τ ) ä 2 ≤ τ ∈Ψ t,k w 2 τ (r τ -f ⋆ (x τ , a τ )) 2 (by the optimality of ft,k ) ≤ 2 τ ∈Ψ t,k w 2 τ σ 2 τ + L. (Freedman's inequality) Lemma F.3. With probability at least 1 -δ, f ⋆ ∈ F t for all t.Proof. We prove by induction. Assume that f ⋆ ∈ F t-1 . Then for all k ∈ [K] such that 2 2k ≥ 80L, by Lemma F.1 and Lemma F.2, with probability at least 1 -δ/T ,τ ∈Ψ t,k w 2 τ ( ft,k (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 ≤ 10 • 2 -2k Ñ τ ∈Ψ t,k w 2 τ σ 2 τ L + L 2 é ≤ 10 • 2 -2k Ñ 8 τ ∈Ψ t,k w 2 τ Ä r τ -ft,k (x τ , a τ ) ä 2 L + 4L 2 é ≤ β 2 t,k . For k ∈ [K] such that 2 2k < 80L, we bound trivially τ ∈Ψ t,k w 2 τ ( ft,k (x τ , a τ ) -f ⋆ (x τ , a τ )) 2 ≤ |Ψ t,k | = β 2 t,k . (w τ ≤ 1)In both cases, we have f ⋆ ∈ F t by the definition of F t . By induction, we conclude that with probability at least 1 -δ, f ⋆ ∈ F t for all t.Lemma F.4.For k ∈ [K], we have |Ψ T +1,k | ≤ Õ(2 2k d elu ).Proof. For t such that k t ∈ [K], by the definition of w t we have1 = 2 kt w t g t = 2 kt max f,f ′ ∈Ft w t |f (x t , a t ) -f ′ (x t , a t )| » 2 -2kt L 2 + τ ∈Ψ t,k t w 2 τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 .Thus,|Ψ T +1,k | = t∈Ψ T +1,k min    1, 2 k max f,f ′ ∈Ft w t |f (x t , a t ) -f ′ (x t , a t )| » 2 -2k L 2 + τ ∈Ψ t,k w 2 τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2    2 = 2 2k t∈Ψ T +1,k min ® 2 -2k , max f,f ′ ∈Ft w 2 t (f (x t , a t ) -f ′ (x t , a t )) 2 2 -2k L 2 + τ ∈Ψ t,k w 2 τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ≤ Õ(2 2k d elu ).(by Lemma D.5) Lemma F.5. For t such that 2 2(kt-1) ≥ 80L, we havemax a∈At f ⋆ (x t , a) -f ⋆ (x t , a t ) ≤ 200 • 2 -2kt Ä√ ΛL + L ä .Proof.max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t ) ≤ max f ∈Ft f (x t , a ucb t ) -f ⋆ (x t , a t ) (define a ucb t = arg max a∈At max f ∈Ft f (x t , a)) = max f ∈Ft f (x t , a ucb t ) -min f ∈Ft f (x t , a ucb t ) + min f ∈Ft f (x t , a ucb t ) -max f ∈Ft f (x t , a t ) + max f ∈Ft f (x t , a t ) -f ⋆ (x t , a t ) ≤ 2 max f,f ′ ∈Ft max a∈At |f (x t , a) -f ′ (x t , a)| + min f ∈Ft f (x t , a ucb t ) -max f ∈Ft f (x t , a t ) (i) ≤ 2 max f,f ′ ∈Ft max a∈At |f (x t , a) -f ′ (x t , a)| (ii) ≤ 2 max f,f ′ ∈Ft max a∈At |f (x t , a) -f ′ (x t , a)| » 2 -2kt+2 L 2 + τ ∈Ψ t,k t -1 w 2 τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 × √ 5β t,kt-1 = 2 √ 5 • max a∈At g t,kt-1 (a)β t,kt-1 ≤ 2 √ 5 • 2 -kt+1 β t,kt-1 (by the definition of k t ) ≤ 2 √ 5 • 2 -kt+1 • 10 • 2 -kt+1 τ ∈Ψ t,k t -1 w 2 τ (r τ -ft,kt-1 (x τ , a τ )) 2 L + L 2(by the definition of β t,k )EQUATIONHere, in (i) we use the definition of A t that there exists f ′ ∈ F t such that a t = max a∈A f ′ (x t , a), which impliesmin f ∈Ft f (x t , a ucb t ) ≤ f ′ (x t , a ucb t ) ≤ f ′ (x t , a t ) ≤ max f ∈Ft f (x t , a t ).In (ii) we use the fact that for f, f ′ ∈ F t , k ≤ K and 2 2k ≥ 80L, we have2 -2k L 2 + τ ∈Ψ t,k w 2 τ (f (x τ , a τ ) -f ′ (x τ , a τ )) 2 ≤ β 2 t,k + 2 τ ∈Ψ t,k w 2 τ (f (x τ , a τ ) -ft,k (x τ , a τ )) 2 + 2 τ ∈Ψ t,k w 2 τ (f ′ (x τ , a τ ) -ft,k (x τ , a τ )) 2(by the definition of β t,k )≤ 5β 2 t,k . (by the fact that f, f ′ ∈ F t )Proof of Theorem 5.2. Without loss of generality, assume 2 2K ≥ 80L, which is equivalent toT 2 ≥ Θ(log(|F|T /δ)). Notice that [T ] = K+1 k=1 Ψ T +1,k .Bound the regret in Ψ T +1,K+1 . Notice that by assumption, for t ∈ Ψ T +1,K+1 , we have 2 2(kt-1) = 2 2K ≥ 80L. Thus, by Lemma F.5,t∈Ψ T +1,K+1 Å max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t ) ã ≤ 200|Ψ T +1,K+1 | • 2 -2(K+1) Ä√ ΛL + L ä ≤ O Å T × 1 T 2 × (ΛL + L) ã = O(1).Bound the regret in Ψ T +1,k with 2 2k ≥ 80L. By Lemma F.5,t∈Ψ T +1,k Å max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t ) ã ≤ 200|Ψ T +1,k | • 2 -2k Ä√ ΛL + L ä ≤ Õ Ä d elu Ä√ ΛL + L ää (by Lemma F.4) = Õ d elu » Λ log |F| + d elu log |F| . Bound the regret in Ψ T +1,k with 2 2k < 80L. t∈Ψ T +1,k Å max a∈At f ⋆ (x t , a) -f ⋆ (x t , a t ) ã ≤ |Ψ T +1,k | ≤ Õ 2 2k d elu (by Lemma F.4) ≤ Õ(d elu L) = Õ (d elu log |F|) .Combining all parts proves the desired bound.Lemma F.6. For any integer A, T ≥ 2, N ≤ c T /A and positive number Λ > AN/c with some c ≤ 1, there exists a context space X , a contextual bandit problem F ⊂ (X × A → R) with eluder dimension d elu (F, 0) = N (A -1) and action set A = [A], and adversarially assigned variances σ 2 1 , . . . , σ 2 T that T t=1 σ 2 t ≤ Λ such that any algorithm will suffer at least Ω(min{√ N AΛ, √ AT }).Proof of Lemma F.6. Let ε 2 ∈ [2N/T, 1] be a parameter to be decided later. Consider the function classF = {f (0) } ∪ f (i,j) i∈[N ],j∈[A-1]with the space of contexts X = {x (1) , . . . , x (N ) } and the set of actions A = [A]. For any i ∈ [N ], j ∈ [A -1], the function f (i,j) is defined as the following:For i ∈ [N ] and j ∈ [A -1], f (i,j) (x (i) , j) = 1 2 + ε, f (i,j) (x, k) = 1 2 -ε, ∀x ̸ = x (i) or ∀k ∈ [A -1] \ {j}. f (i,j) (x, A) = 1 2 , ∀x.Meanwhilef (0) (x, j) = 1 2 -ε, ∀x and ∀j ∈ [A -1] f (0) (x, A) = 1 2 , ∀x.The eluder dimension of this function class is N (A -1) since f (i,j) is uniquely identified by its value on (x (i) , j).We assume that x t is uniformly randomly chosen from X , and r t = f ⋆ (x t , a t ) + ϵσ t , where ϵ ∼ N (0, 1) and σ t is defined in the following way. Fix the algorithm. Let N t (i, j) = t s=1 1(x s =x (i) , a s = j) for any x ∈ X and the action b. The adversary assignsσ t = 1(a t = j, N t (x t , j) ≤ 1/ε 2 ),that is, it assigns variance 1 when the algorithm chooses action b and the context-action pair x t , b are not played for more than 1/ε 2 times.Fix any algorithm. Denote by P 0 the probability distribution when f ⋆ = f (0) and E 0 the expectation under P 0 . For any i ∈ [N ], j ∈ [A -1], denote by P (i,j) the probability distribution when f ⋆ = f (i,j) and E (i,j) the expectation under P (i,j) . Then the adversary decides f ⋆ based on the following rule: if there exists i ∈[N ], j ∈ [A -1] such that E 0 [N T (i, j)] ≤ 1 1000ε 2 (20) then let f ⋆ = f (i,j) . If no i, j satisfies this, let f ⋆ = f (0) . If f ⋆ = f (0) , then we have E 0 [R T ] ≥ ε • E 0   i∈[N ],j∈[A-1] N T (i, j)   ≥ εN (A -1) • min i,j E 0 [N T (i, j)] ≥ N (A -1) 1000ε .On the other hand, if f ⋆ = f (i,j) , then we haveP 0 Å N T (i, j) < 1 ε 2 ã ≥ 999 1000 .Then by Lemma B.4, we haveP 0 Å N T (i, j) < 1 ε 2 ã ≤ 3P i,j Å N T (i, j) < 1 ε 2 ã + 4D 2 H (P 0 , P i,j ).Then by Lemma D.2 of Foster et al. (2024) , we haveD 2 H (P 0 , P i,j ) ≤ 7E 0 N T (i, j) ∧ (1/ε 2 ) • 4ε 2 ≤ 7 250.Altogether, we can obtainP i,j Å N T (i, j) < 1 ε 2 ã ≥ 1 3 Å P 0 Å N T (i, j) < 1 ε 2 ã -28/250 ã ≥ 1/6.This in turn, implies that with the choice ε 2 ≥ 2N/T , thatE i,j [R T ] ≥ ε • E i,j T t=1 1[x t = x (i) ] -N T (x (i) , j) ≥ ε • Å T N - 1 ε 2 ã P i,j Å N T (i, j) < 1 ε 2 ã ≥ T ε 12N .Thus if √ AT > √ N AΛ, then we set ε = N A/Λ. We have ε ≤ 1 due to the assumption that Λ ≥ AN/c. Then we verifyT t=1 σ 2 t = T t=1 1(x t = x (i) , a t = j, N t (i, j) ≤ 1/ε 2 ) ≤ N (A -1)/ε 2 ≤ Λ.Furthermore,√ AT > √ N AΛ implies T ε/N > AN/ε, and thus sup i∈{0}∪[N ] E i [R T ] ≥ Ω Å min ß AN ε , T ε N ™ã ≥ AN ε = Ω( √ N AΛ).Otherwise if √ AT < √ N AΛ, then we have T /N ≤ Λ and we set ε = N A/T . We have ε ≤ 1 due to the assumption that N ≤ c T /A. Then we verifyT t=1 σ 2 t = T t=1 1(x t = x (i) , a t = j, N t (i, j) ≤ 1/ε 2 ) ≤ N (A -1)/ε 2 ≤ T /N ≤ Λ.Finally, we have the lower boundssup i∈{0}∪[N ] E i [R T ] ≥ Ω Å min ß AN ε , T ε N ™ã ≥ Ω( √ AT ).Overall, we have proven thatsup i∈{0}∪[N ] E i [R T ] ≥ Ω Å min ß AN ε , T ε N ™ã ≥ Ω(min{ √ N AΛ, √ AT }).Proof of Theorem 5.1.We first deal with some corner cases: √ dΛ + d, √ AT }).Thus, we conclude our proof.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 ∈ [T ],infp∈∆(A) max M ∈Mt E a∼p ñ max a ′ f M (x t , a ′ ) -f M (x t , a) -γ (f M (x t , a) -f Mt (x t , a)) 2 σ 2 Mt (x t , a) ô ≲ Aσ 2 Mt (x t ) γ ,whereσ 2 Mt (x t ) = sup a∈A σ 2 Mt (x t , a). Proof of Lemma G.1. Fix t ∈ [T ]. Let q ∈ ∆(A) be the policy such that q(x t , a) = 1 λ + γ/σ 2 Mt (x t , a) • (max a ′ ∈A f Mt (x t , a ′ ) -f Mt (x t , a)),where λ is such that a∈A q(x t , a) = 1. We show that such λ exists and λ ∈ (0, A]. Let h(λ) = a∈A (xt,a)) . Then we have h(λ) is monotonically decreasing with h(0) = ∞ and h(A) < 1. Thus there exists λ ∈ (0, A] such that h(λ) = 1 that corresponds to q(x t , a).1 λ+γ/σ 2 M t (xt,a)•(max a ′ ∈A f M t (xt,a ′ )-f M tWe first separate the regret with respect to any fixed M into four parts as the followingEQUATION)where a ⋆ ∈ arg max a∈A f M ⋆ (x t , a). Firstly, by the definition of q, we haveEQUATION)Secondly, by the AM-GM inequality, we haveEQUATIONThirdly, again by the AM-GM inequality and the definition of q, we haveEQUATIONPlug the inequality ( 22), ( 23), and (24) in the equality ( 21) to obtain the desired bound ofE a∼q ñ max a ′ f M (x t , a ′ ) -f M (x t , a) -γ (f M (x t , a) -f Mt (x t , a)) 2 σ 2 Mt (x t , a) ô ≲ Aσ 2 Mt (x t ) γLemma G.2. Whenever I t = 2 and M ⋆ ∈ M t , we have for any action a ∈ [A],σ 2 M ⋆ (x t , a) ≲ σ 2 Mt (x t , a) ≲ σ 2 M ⋆ (x t , a).Proof. Since for any M, M ′ ∈ M t and a ∈ A, one has D 2 H (M (x t , a), M ′ (x t , a)) ≤ 1/2. Thus by Lemma B.2, we have that σ M (x t , a) ≲ σ M ′ (x t , a).Then since M ⋆ is in M t and M t is a mixture of models in M t , we have by the total variacne lawσ 2 M ⋆ (x t , a) ≲ min M ∈Mt σ 2 M (x t , a) ≲ σ 2 Mt (x t , a) ≲ max M ∈Mt σ 2 M (x t , a) ≲ σ 2 M ⋆ (x t , a).Lemma G.3. Whenever I t = 2 and M ⋆ ∈ M t , we have for any action a ∈ A|f M ⋆ (x t , a) -f Mt (x t , a)| ≲ » σ 2 Mt (x t , a) 2 D 2 H (M (x t , a), M t (x t , a)).Proof. Since M ⋆ is in M t and M t is a mixture of models in M t , we have for any action a ∈ [A],D 2 H (M ⋆ (x t , a), M t (x t , a)) ≤ max M ∈Mt D 2 H (M ⋆ (x t , a), M (x t , a)) ≤ 1/2.Then by Lemma B.3, we have that|f M ⋆ (x t , a) -f Mt (x t , a)| ≲ » (σ 2 M ⋆ (x t , a) + σ 2 Mt (x t , a))D 2 H (M (x t , a), M t (x t , a)).Then by Lemma G.2, we have|f M ⋆ (x t , a) -f Mt (x t , a)| ≲ » (σ 2 M ⋆ (x t , a) + σ 2 Mt (x t , a))D 2 H (M (x t , a), M t (x t , a)) ≲ » σ 2 Mt (x t , a) 2 D 2 H (M (x t , a), M t (x t , a)).Lemma G.4. The regrets accumalated on rounds where I t = 2 are bounded with probability at least 1 -δ byT t=1 reg t 1(I t = 2) ≲ Ã A T t=1 σ 2 M ⋆ (x t ) • log(|M|/δ),whereσ 2 M ⋆ (x t ) = sup a∈A σ 2 M ⋆ (x t , a) and reg t = E a∼pt [max a ′ f M ⋆ (x t , a ′ ) -f M ⋆ (x t , a)]. Proof. Let E t [•] := E[• | H t ]where H t is the history up to time t. By Lemma G.1 and Lemma G.3, whenever I t = 2 and M ⋆ ∈ M t , we haveE t [reg t 1(I t = 2, M ⋆ ∈ M t )] = E a∼pt max a ′ f M ⋆ (x t , a ′ ) -f M ⋆ (x t , a) • 1(M ⋆ ∈ M t ) ≤ γE a∼pt ñ (f M ⋆ (x t , a) -f Mt (x t , a)) 2 σ 2 Mt (x t , a) • 1(M ⋆ ∈ M t ) ô + Aσ 2 Mt (x t ) γ ≲ γE a∼pt D 2 H (M ⋆ (x t , a), M t (x t , a)) • 1(M ⋆ ∈ M t ) + Aσ 2 Mt (x t ) γ .Then by summation over t ∈ [T ], we haveT t=1 E t [reg t 1(I t = 2, M ⋆ ∈ M t )] ≲ A T t=1 σ 2 Mt (x t ) γ + γ • T t=1 E a∼pt D 2 H (M ⋆ (x t , a), M t (x t , a)) • 1(M ⋆ ∈ M t ) .Then by Lemma A.15 of Foster et al. (2021) , we have that with probability at least 1 -δ/2, T t=1E a∼pt D 2 H (M ⋆ (x t , a), M t (x t , a)) • 1(M ⋆ ∈ M t ) ≤ log(2|M|/δ).Then by the choice of γ = A T t=1 σ 2 Mt (x t )/ log(2|M|/δ), we have with probability at least 1 -δ/2,A T t=1 σ 2 Mt (x t ) γ + γ • T t=1 E a∼pt D 2 H (M ⋆ (x t , a), M t (x t , a)) • 1(M ⋆ ∈ M t ) ≲ Ã A T t=1 σ 2 Mt (x t ) • log(2|M|/δ) ≲ Ã A T t=1 σ 2 M ⋆ (x t ) • log(2|M|/δ),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 1 -δ/4, for all t ∈ [T ], T t=1 reg t 1(I t = 2, M ⋆ ∈ M t ) ≤ 3 2 T t=1 E t [reg t 1(I t = 2, M ⋆ ∈ M t )] + 4 log(8/δ).Thus by the union bound , with probability at least 1 -δ, we haveT t=1 reg t 1(I t = 2) = T t=1 reg t 1(I t = 2, M ⋆ ∈ M t ) ≲ Ã A T t=1 σ 2 M ⋆ (x t ) • log(|M|/δ).Lemma G.5. For any λ ≥ 0 and α > 0, we haveT t=1 min ® λ, sup M,M ′ ∈Mt D 2 H (M (x t , a t ), M ′ (x t , a t )) α 2 T + t-1 τ =1 D 2 H (M (x τ , a τ ), M ′ (x τ , a τ )) ´≤ d H elu (α) (λ + log T ) .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 t = 1 are bounded byT t=1 reg t 1(I t = 1) ≲ d H elu (α) α 2 T + log(|M|T /δ) log T,for any α > 0.Proof. For any t ∈ [T ] and M, M ′ ∈ M t , we haveEQUATION)Thus let T t=1 1(I t = 1) = T 1 and we haveT t=1 reg t 1(I t = 1) ≤ T t=1 1(I t = 1) = T 1 .Thus we have for any α ≥ 0,T 1 = It=1 1 ® sup M,M ′ ∈Mt D 2 H (M (x t , a t ), M ′ (x t , a t )) ≥ 1 2 ≤ √ 2 It=1 min ® 1 √ 2 , sup M,M ′ ∈Mt D H (M (x t , a t ), M ′ (x t , a t )) ≤ √ 2 It=1 min          1 √ 2 , sup M,M ′ ∈Mt D H (M (x t , a t ), M ′ (x t , a t )) α 2 T + t-1 τ =1 D 2 H (M (x τ , a τ ), M ′ (x τ , a τ )) • α 2 T + 4L          ,where the last inequality is by (25). Furthermore, by Cauchy-Schwarz inequality, we haveIt=1 min          1 √ 2 , sup M,M ′ ∈Mt D H (M (x t , a t ), M ′ (x t , a t )) α 2 T + t-1 τ =1 D 2 H (M (x τ , a τ ), M ′ (x τ , a τ )) • α 2 T + 4L          ≤ T 1 oe It=1 min        1 2 , sup M,M ′ ∈Mt D 2 H (M (x t , a t ), M ′ (x t , a t )) α 2 T + t-1 τ =1 D 2 H (M (x τ , a τ ), M ′ (x τ , a τ )) • (α 2 T + 4L)        ≤ » T 1 • d H elu (α)(1/2 + (α 2 T + 4L) log T ),where the last inequality is by Lemma G.5. Altogether, we haveT 1 ≲ » T 1 • d H elu (α)(1/2 + (α 2 T + 4L) log T ).Reorganizing the above inequality, we obtain the desired bound.Proof of Theorem 6.1. The proof is straight-forward by combing Lemma G.6 and Lemma G.4, i.e., with probability at least 1 -δ,R T ≲ Ã A T t=1 σ 2 M ⋆ (x t ) • log(|M|/δ) + d H elu (α) α 2 T + log(|M|T /δ) log T.Then, by choosing α = 1/ √ T , 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 a hard instance for a function class F that only contain reward mean information, but the reward has a fixed variance upper bound σ 2 t ≤ σ 2 . What we do here is simply embed this instance in a model class M where for every model, every context, and every action, the reward distribution is a Gaussian with mean as in F and variance σ 2 . Notice that we can change the distribution P - σ,ϵ and P + σ,ϵ in Lemma B.1 to N (σ -ϵ, σ 2 ) and N (σ + ϵ, σ 2 ), respectively, which still gives usD KL P - σ,ϵ ∥ P + σ,ϵ ≤ (2ϵ) 2 2σ 2 = 2ϵ 2 σ 2 .This allows us to prove the same bound as in Lemma C.1. Furthermore, the eluder dimension d H elu (M, 0) defined through the Hellinger distance between models remain the same as the eluder dimension d elu (F, 0) defined through the mean difference in the constructions of Lemma C.1 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 us to prove the same lower bound in the case here.Lemma G.7. For any integer A, T ≥ 2, N ≤ c T /A and positive number Λ > AN/c, there exists a context space X , a contextual bandit model class M ⊂ (X × A → ∆(R)) with eluder dimension d H elu (M, 0) = N (A -1) and action set A = [A], and adversarially assigned variances σ 2 1 , . . . , σ 2 T that T t=1 σ 2 t ≤ Λ such that any algorithm will suffer at least Ω(min{√ N AΛ, √ AT }).Proof of Lemma G.7. This lower bound is based on a 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 x, the new context space will have T A corresponding contexts (x, j 1 , ..., j A ) 1≤j1,...,j A ≤T , where the second argument will be used to record the number of pulls to each action a under context x. 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 (x t , N t (x t , 1), ..., N t (x t , A)) to embed the hard case from Lemma F.6. The Hellinger eluder dimension is twice the eluder dimension because there are two types of variances corresponding to each original context. Thus, we obtain the desired bound.Proof of Theorem 6.3. √ dΛ + d, √ AT }).Thus, we conclude our proof.H Upper Bound with Zero-One Variance (Section 7)In this section, we consider the setting where σ t = 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. E[R T ] = O Ñ Ã A log |F| 1 + T t=1 σ 2 t + A(d elu + log |F|)é .We will prove upper bounds for regret of rounds with σ t = 0 and σ t = 1 separately. First we bound the regret of rounds with σ t = 1.Lemma H.1. With γ = » 8A log |F | , the output actions a t at each round in Algorithm 6 satisfiesT t=1 I[σ t = 1] Å max a∈A f ⋆ (x t , a) -f (x t , a t ) ã ≤ 4 Ã 2A log |F| • 1 + T t=1 σ 2 t .Proof. Based on the inverse-gap weighting update rule Eq. ( 26), similar to (Foster and Rakhlin, 2020, Lemma 3), we haveE T t=1 I[σ t = 1](max a f ⋆ (x t , a) -f ⋆ (x t , a t ))Algorithm 6 Variance Sensitive SquareCB for Zero-One Noise Input: γ. 1: Let F 1 ← F. 2: for t = 1 : T do 3:Receive x t , and calculate A t = {a ∈ A : ∃f ∈ F t , f (x t , a) = arg max a∈A f (x t , a)}.Sample action a t ∼ p t and receive σ t and r t , whereEQUATIONCalculate L t (f ) for all f ∈ F asL t (f ) = t τ =1 (f (x τ , a τ ) -r τ ) 2 σ 2 τ ,where for those σ τ = 0, we define(f (xτ ,aτ )-rτ ) 2 σ 2 τ = 0 if f (x τ , a τ ) = r τ and ∞ otherwise. 6:Calculate q t (f ) to beq t+1 (f ) = e -Lt(f )g∈F e -Lt(g) .Calculate f t+1 to bef t+1 = f ∈F q t+1 (f ) • f. 8: if σ 0 = 0 then 9: Update F t+1 = {f ∈ F t , f (x t , a t ) = r t }. 10: else 11: Let F t+1 = F t . ≤ E   T t=1 I[σ t = 1] • 2A A + γ » 1 + t-1 s=1 σ 2 s   + γ 4 E   T t=1 Ã 1 + t-1 s=1 σ 2 s • (f t (x t , a t ) -f ⋆ (x t , a t )) 2   .For the first term, we have analysisT t=1 I[σ t = 1]• 1 A + γ » 1 + t-1 s=1 σ 2 s ≤ 2 γ T t=1 ÑÃ 1 + t s=1 σ 2 s - Ã 1 + t-1 s=1 σ 2 s é = 2 γ Ã 1 + T s=1 σ 2 s ,where the first inequality uses the fact that σ t ∈ {0, 1} and when σ t = 1 we have1 √ 1+ t-1 s=1 σ 2 s = 1 √ t s=1 σ 2 s ≤ 2 » 1 + t s=1 σ 2 s - » 1 + t-1 s=1 σ 2 s .For the second term, we haveT t=1 Ã 1 + t-1 s=1 σ 2 s • (f t (x t , a t ) -f ⋆ (x t , a t )) 2 ≤ Ã 1 + T t=1 σ 2 t • T t=1 (f t (x t , a t ) -f ⋆ (x t , a t )) 2 ≤ Ã 1 + T t=1 σ 2 t • log |F|,where the last line is according to the analysis of Vovk's aggregating algorithm (Vovk, 1995; Cesa-Bianchi and Lugosi, 2006) .Above all, with γ = » 8A log |F | , we getE T t=1 I[σ t = 1](max a f ⋆ (x t , a) -f ⋆ (x t , a t )) ≤ Å 2A γ + γ log |F| 4 ã Ã 1 + T t=1 σ 2 t = 4 Ã 2A log |F| • 1 + T t=1 σ 2 t .The following is a useful lemma regarding Eluder dimension.Lemma H.2. We defineEQUATION)Then we haveT t=1 I[σ t = 0]Z t ≤ d elu ( 1 /T ).Proof. This lemma follows directly according to the definition of Eluder dimension d elu (1/T ) in Definition 2.1, and the fact that all functions in F t must agree on the previous samples where σ s = 0.With this lemma, we are ready to bound the regret of rounds with σ t = 0. [σ t = 0](f ⋆ (x t , a) -f ⋆ (x t , a t )) = O Ñ Ã A log |F| T t=1 σ 2 t + A(d elu + log |F|) é .Proof. In this proof, we focus on the case σ t = 0. We first notice that for rounds σ t = 0, we always have f * (x t , a t ) = r t . Hence f * ∈ F t for every t ∈ [T ]. We define a * t = arg max a∈A f * (x t , a).At round t, we let b t = arg max a∈A f t (x t , a), and we define B t ⊂ A t asEQUATION)For rounds with σ t = 0, based on x t , f t , we divide such rounds into two cases, which we denote as T 1 and T 2 .(a) There exists a ∈ B t and f ∈ F t , such that |f (x t , a) -f t (x t , a)| ≥ 1 /T .(b) For all f ∈ F t and a ∈ B t , we have |f (x t , a) -f t (x t , a)| ≤ 1 /T .Regret in t ∈ T 1 . For those t ∈ T 1 , first we notice that for any a ∈ B t , according to Eq. ( 26) we have p t (a) = 1A + γ » 1 + s<t σ 2 s (f t (x t , b t ) -f t (x t , a)) ≥ 1 A + γ » 1 + s<t σ 2 s • 2/T ≥ 1 7A ,where in the last inequality we use the fact that2γ » 1 + s<t σ 2 s T ≤ 2γ √ T T = 2 8A/ log |F| √ T ≤ 6A.Therefore, according to the definition of T 1 that there exists some a ∈ B t and f ∈ F t such that |f (x t , a) -f t (x t , a)| ≥ 1/T , for any t ∈ T 1 with probability at least 1 /7A we will sample an action a t such that Z t = 1 (Z t is defined in Eq. ( 27)). Therefore, we haveE t∈T1 (f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a t )) ≤ E T t=1 I[t ∈ T 1 ] ≤ E T t=1 Z t I[σ t = 0] 1/(7A) = 7AE T t=1 Z t I[σ t = 0] ≤ 7Ad elu ( 1 /T ),where the last inequality uses Lemma H.2.Regret in t ∈ T 2 with a t ∈ B t . For those t ∈ T 2 , to facilitate the analysis we definel t (f, x t , a) = (f (x t , a) -r t ) 2 -(f ⋆ (x t , a) -r t ) 2 σ 2 t ∀t ∈ [T ],andEQUATIONThen we have q t (f ) = exp(- ≤ Ñ A + γ Ã 1 + T t=1 σ 2 t é • E[Φ t-1 -Φ t ] + 3 T ,where in (i) we use the fact that according to the definition of B t in Eq. ( 28),f t (x t , a) -f t (x t , a ⋆ t ) ≥ f t (x t , b t ) -f t (x t , a ⋆ t ) - 2 T ≥ - 2 T ,and (ii) uses the definition of T 2 that for any a ∈ B t and f ∈ F t we always have |f t (x t , a)f ⋆ (x t , a)| ≤ 1 /T , and (iii) uses Eq. ( 30) and also the fact thatp t (a ⋆ t ) = 1 A + γ » 1 + s<t σ 2 s (f t (x t , b t ) -f (x t , a ⋆ t )) ≥ 1 A + γ » 1 + T t=1 σ 2 t .Suming this up for every t ∈ T 2 , we obtain thatE t∈T2 I[a t ∈ B 2 ](f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a t )) ≤ Ñ A + γ Ã 1 + T t=1 σ 2 t é • 1 + T t=1 E[Φ t-1 -Φ t ] + 3 T • T ≤ Ñ A + γ Ã 1 + T t=1 σ 2 t é log |F| + 3,where in the last inequality we use the definition of Φ t in Eq. ( 29) that Φ 0 = log |F| andΦ T ≥ log exp - T s=1 l s (f ⋆ , x s , a s ) = 0.Regret in t ∈ T 2 with a t / ∈ B t . Next, for a t ̸ ∈ B t , according to the definition of A t , there exists a function f ∈ F t such that f (x t , a t ) ≥ f (x t , a ′ ) for any a ′ ∈ A. This implies that f t (x t , a t )(i) ≤ f t (x t , b t ) - 2 T (ii) ≤ f (x t , b t ) + 1 T - 2 T = f (x t , a t ) - 1 T ,where in (i) we use the definition of B t in Eq. ( 28), and in (ii) we use the definition of T 2 that for any f ∈ F t , |f (x t , b t ) -f t (x t , b t )| ≤ 1 /T . Therefore, in those rounds with σ t = 0, t ∈ T 2 and a ̸ ∈ B t , we always have Z t = 1 (Z t is defined in Eq. ( 27)), which implies thatE t∈T2 I[a t ̸ ∈ B 2 ] (f ⋆ (x t , a ⋆ t ) -f ⋆ (x t , a t )) ≤ E T t=1 I[σ t = 0]Z t ≤ d elu ( 1 /T ),where the last inequality uses Lemma H.2.Finally we combined these these bounds in T 1 and T 2 together, and obtain that Finally, combining the regret bound for rounds with σ t = 1 and σ t = 0 together, we can prove Theorem H.1.Proof of Theorem H.1. We decompose the regret Summing these two together, we obtain thatE[R T ] = O Ñ Ã A log |F| T t=1 σ 2 t + A(d elu + log |F|)é .• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 a 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 or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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, or 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 a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] .Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use 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 a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.We assume bounded noise for simplicity. The extension to 1-sub-Gaussian noise is straightforward.A ≤ delu ≤ √AT is a more challenging and elusive regime, and we focus our study here. When delu > √ AT , we can use SquareCB(Foster and Rakhlin, 2020) to achieve the tight bound √ AT ; when delu < A, we can use the algorithm in Section 5 to get delu √ Λ + delu, which is tight up to a √ delu factor.Although Pacchiano (2024) presents this result by assuming σt = σ for some known σ, it is straightforward to extend it to the case where σt are different but revealed before each round, just like in our Section4.3. 
 
 Appendix:  


Decision: This paper makes a solid contribution to the important problem of adapting to the variance in contextual bandits.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * 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).
* 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?
questions: questions: Please refer to strengths and weaknesses above.
limitations: limitations: No braoder impact concerns.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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)
2. Some missing related works.
More works on variance-dependent results of heteroscedastic bandits:

[1] Zhou et al. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes, Colt 2021

[2] Zhou and Gu. Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs Neurips 2022

[3] Zhao et al. Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits

3. 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.
 
[4] Agarwal et al. Vo q l: Towards optimal regret in model-free rl with nonlinear function approximation. Colt 2023

[5] Ye et al.  Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. ICML2023

[6] Di et al. Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning, ICLR 2024

[7] Huang et al. Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximation AISTATS

[8] Gentile et al. Fast Rates in Pool-Based Batch Active Learning ICML 2024

[9] Zhao et al. A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation

4. Some minor errors: Line 12 worst case over what? 

In 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$.
questions: questions: 1. Is it possible to prove a variance-dependent upper bound with $d_{elu}$ dependence in the first term of Theorem 4.2?
2. What difficulty did you meet when trying to recover Zhao et al. (2023)’s result for unknown variance?
limitations: limitations: The limitations and societal impact of this work have been addressed.
paper_summary: paper_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.
strength_weakness: strength_weakness: See the questions section
questions: questions: - Can the authors summarize the main technical novelty used in the paper?
- 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]?
- 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?

[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: limitations: None
paper_summary: paper_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 ***

The 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.
The 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.
In all the cases, their bounds are also dependent on the Eluder dimension. They present a matching lower bound for each setting.
The 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.
strength_weakness: strength_weakness: 1.	The related literature review is unclear.  In the presented previous results, there should be a clear separation between variance-dependent bounds and minimax regret bounds. 

2.	The 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.

3.	I 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.

4.	It seems that the work over a confidence set of functions implies a running time complexity of $|F|$ that is not discussed. 

5.	The 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)".

6.	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.


[1] Eluder-based regret for stochastic contextual MDPs, Levy et al. 2024.
questions: questions: 1.	Please provide a specific comparison of your results with the known variance-dependent bounds in previous literature.

2.	What do you mean by $d_{elu}(0)$ ? For my understanding, the Eluder dimension is meaningful only for $\alpha \in (0,1] $.

3.	Please refer to the weaknesses.
limitations: limitations: Mentioned in the "Weaknesses" section.

Comments: comment: Thank the reviewer for their response! I do not any further questions.
Thanks for the feedback. First, we agree that the assumption in Section 4 that variance being revealed is not ideal, and our ultimate goal is to remove it (some initial attempts have been made in Appendix G). At the current stage, however, this assumption is necessary for our technique, and we hope that the our technique could inspire future work that obtains variance-agnostic result.  

Still, there are cases where the learner is able to obtain variance information / variance estimation before making decisions, and the use of our algorithm can be justified. 

For example, our algorithm works well for the case where the variance is upper bounded by a fixed quantity in all rounds, and the variance is much smaller than the reward range. This could simulate recommendation systems where the reward comes from user rating. Let's say the range of the rating is 0 to 10, but the user feedback has some noise and it is modeled to be within (mean - 1.5, mean + 1.5). In this case, the sigma in our algorithm can be chosen as 3/10, which significantly improve the existing regret bound by variance-unaware algorithms (e.g., SquareCB). 

It is also possible that the learner can perform context-aware variance estimation, and plug it into our algorithm. For example, in clinical trials, the context may include information like the type of the drug and the age of the patient. We could create a finite number of categories for these contexts, and estimate the variance for each of them using historical data. This way, we can obtain variance estimation for given contexts before making decisions, and then apply our algorithm.
Thank you for the response. It seems the strong adversary case actually covers the unknown variance situation so the results of the paper are stronger than I initially thought, even though there is higher dependence on $d$. As such, I am satisfied by the discussion and raise my score.
Thanks for your useful responses. I will keep my score.
Thank the authors for their response! Please consider incorporating the discussions of lower bound under the heterogeneous variances scenario into their manuscript.

Regarding the question that the variances are revealed, I still believe this setup might be strong. I understand that when the context space is large, the estimation of the variance may not be possible. From another point of view, this indicates the knowledge of the variance is unavoidable in this work. Therefore, can the authors give practical scenarios where the variance information is given to justify their setup?
I thank the authors for their response and have no further questions.
We provide a further explanation below for $d_{elu}(0)$. 

Our definition of eluder dimension (Definition 2.1) follows that in Russo and Van Roy (2014). See their Definition 3 and 4. Note that their $\epsilon$ is our $\alpha$. 

By the definitions, $d_{elu}(0)$ is well-defined as long as the concept of ``$0$-dependent'' is well-defined (see Russo and Van Roy's Definition 3). By their Definition 3, an action $a$ is $0$-dependent with respect to $\mathcal{F}$ on $\{a_1, \ldots, a_n\}$ if any pairs $f, \tilde{f}\in \mathcal{F}$ satisfying $f(a_i)=\tilde{f}(a_i)$ for all $i\in\{1,2,\ldots, n\}$ also satisfies $f(a)=\tilde{f}(a)$.  

Take the $d$-dimensional linear function class as an example, i.e., $\mathcal{F}$ consists of functions of the form $f_\theta(a)=\theta^\top a$. We demonstrate it through $d=4$. Below we show that $a=(2,3,4,0)$ is $0$-dependent on $\{a_1, a_2, a_3\}$ where $a_1=(1,0,0,0)$, $a_2=(0,1,0,0)$, and $a_3=(0,0,1,0)$. To verify this, assume that $f=f_\theta$ and $\tilde{f} = f_{\tilde{\theta}}$ agree on $\{a_1, a_2, a_3\}$, i.e., $\theta^\top a_i = \tilde{\theta}^\top a_i$ for all $i=1,2,3$. By our choices of $a_1, a_2, a_3$, it must be that $\theta_i = \tilde{\theta}_i$ for all $i=1,2,3$. This further implies $\theta^\top a = \tilde{\theta}^\top a$. We thus have shown that $a$ is $0$-dependent on $\{a_1, a_2, a_3\}$. 

It can be verified that for any finite function class $\mathcal{F}$, $d_{elu}(0)\leq |\mathcal{F}|$ always holds, though it is possible for some infinite function class to have $d_{elu}(0)=\infty$. 

Note that by the definition of eluder dimension, $d_{elu}(\alpha)$ is decreasing with $\alpha$. That is the reason why we choose to state with $d_{elu}(0)$ in Theorem 4.1, 6.2, and 6.3. In these lower bounds, our construction ensures $d_{elu}(0)\leq d$, which implies $d_{elu}(\alpha)\leq d$ for all $\alpha\geq 0$. This ensures that our lower bound simultaneously hold for any choice of $\alpha$. 


[Russo and Vay Roy, 2014] Eluder Dimension and the Sample Complexity of Optimistic Exploration. (link: https://web.stanford.edu/~bvr/pubs/Eluder.pdf).
I thank the authors for their response.
Not sure I understand their response related to the question about $d_{eluder}(0)$. As far as I understand the Eluder dimension, $\alpha$ should be an error parameter. Are you using $1-\alpha$? Would be happy if the authors could elaborate more.
Besides that I have no further questions.