Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Authors: Chenlu Ye
Yujia Jin
Alekh Agarwal
Tong Zhang
Venue: ICML 2025 spotlightposter (2025)
Keywords: Heavy-tailed Rewards
Contextual bandits
Genenral function approximation
Primary area: theory->reinforcement_learning_and_planning

Abstract: Typical contextual bandit algorithms assume that the rewards at each round lie in some fixed range $[0, R]$, and their regret scales polynomially with this reward range $R$. However, many practical scenarios naturally involve heavy-tailed rewards or rewards where the worst-case range can be substantially larger than the variance. In this paper, we develop an algorithmic approach building on Catoni's estimator from robust statistics, and apply it to contextual bandits with general function approximation. When the variance of the reward at each round is known, we use a variance-weighted regression approach and establish a regret bound that depends only on the cumulative reward variance and logarithmically on the reward range $R$ as well as the number of rounds $T$. For the unknown-variance case, we further propose a careful peeling-based algorithm and remove the need for cumbersome variance estimation. With additional dependence on the fourth moment, our algorithm also enjoys a variance-based bound with logarithmic reward-range dependence. Moreover, we demonstrate the optimality of the leading-order term in our regret bound through a matching lower bound.

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Chenlu Ye! Yujia Jin
Alekh Agarwal 3
Tong Zhang
Abstract
some function class F available to the learner, this optimal regret scales as ORR/Tdr log NF), where R is the range of the rewards, T is the number of rounds, dz is complex- ity notion for F, such as the eluder dimension (Russo & Van Roy, 2013), and N5 is the covering number of F.
Typical contextual bandit algorithms assume that the rewards each round lie in some fixed range [0, R). and their regret scales polynomially with this reward range R. However, many practical scenarios naturally involve heavy-tailed rewards or rewards where the worst-case range can be substantially larger than the variance. In this pa- per, we develop an algorithmic approach building on Catoni's is estimator from robust statistics, and apply it to contextual bandits with general fune- tion approximation. When the variance of the reward at each round is known, we use a variance- weighted regression approach and establish a re- gret bound that depends only on the cumulative reward variance and logarithmically on the re- ward range R as well as the number of rounds T. For the unknown-variance case, we further propose careful peeling-based algorithm and remove the need for cumbersome variance esti- mation. With additional dependence on the fourth moment, our algorithm also enjoys a variance- based bound with logarithmic reward-range de- pendence. Moreover, we demonstrate the optimal- ity of the leading-order term in our regret bound through matching lower bound.
However, this worst-case behavior arises only when the rewards span their entire range [0, R] with a significant probability, a phenomenon not typical in practice. Even for common case of binary rewards in {0, R} for instance, the expected reward is often relatively close to 0 in com- mon click//o-click style recommendation settings with low clickthrough rates. Consequently, the expectation, variance and even higher moments of the reward are much smaller than the worst-case range. More generally, rewards with heavier tails naturally arise when considering waiting times in wireless communication networks (Nair et al., 2013), stock prices in financial markets (Cont, 2001; Hull, 201 2), or value returns for online ad advertising (Choi et al., 2020; Jebarajakirthy et al., 2021). ). In this paper, we study the de- sign of contextual bandit algorithms that can leverage such structures to have regret guarantees dependent polynomially on the reward variance, with only mild logarithmic scaling with the range parameter R.
Such variance-based regret bounds have received significant attention recently, under the topic of robustness to heavy- tailed rewards. Huang et al. (2024); Li & Sun (2024) study Huber regression and design weighte regression- based approaches for linear contextual bandits with known variance, and show that their algorithms achieve a variance- based / o?) regret bound, where d is the di- mension for the linear function, thus avoiding a dependence on range R. They also study Markov Decision Processes
1. Introduction
Minimax optimal regret bounds in the worst-case over prob- lem instances for contextual bandit learning are relatively well-understood in the literature, both using policy- based approaches in the agnostic case, and regression-baseer ap- proaches in the realizable case. A variety of algorithms attain these bounds in both settings, and the minimax opti- mality implies that the bounds are unimprovable in general. When the expected reward of each action is realizable using
Huang et al. (2024) consider a more general setting, where the 1 + e-th moment of the reward is upper bounded for some E (0, 1). and incur a dependence in terms of this moment along with additional poly(T") terms. Since our work only considers bounded variance, we present their result with (Li & Sun, 2024) together, as the two results are identical for the case of c = 1.
'Equal contribution Universitty of Illinois Sibana-Champaige 'OpenAI (Work done during an internship Google) Google Re- scarch Uniieersity of Illinois Urbana- Champaign. Correspondence to: Chenlu Ye <chenluy36 @ allinois.edu>.
DistUUC relies on a stonger assumption: estimating the full reward distribution rather than just the mean, and hence relies on stronger realizability on the function class to capture this distribution. In contrast, only assume realizability of the reward mean H.. Moreover, d, measures the complexity of a class of distributions. while de measures the complexity of a class of mean functions, thus the two notions are generally incomparable.
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Table Comparison between different algorithms for stochastic contextual bandits, where d denotes the dimension for linear function approximation, d,,, d capture the complexity of the function space F' used for reward estimation, I' is the number of rounds, o is the variance of the observed reward at round f, a a uniform bound on reward variance (or, S for all E (T)), R is the range of rewards, and Ny is the covering number for function class F. Ô omits terms logarithmic in T and R.
Algorithm
Function Type
Known Variances
Regret Bound
Weighted OFUL+ (Zhou & Gu, 2022)
Linear
(d Ener of + dR)
Hcavy-OFUL. (Huang et al., 2024)*
Linear
(d Exeto o7)
AdaOFUL (Li & Sun, 2024)
OLS (Pacchiano, 2024)
Non-linear
Ö(ovdr log NY + Rdy log Nr)
Catoni-OFUL (Theorem 3.4)
Non-linear
/
Ö( Eiero of dr log N5 ds log No)
SAVE (Zhao et al., 2023b)
Lincar
X
Öld Enemn of dR)
DisUUCB (Wang et al., 2024b)*
Non-linear
X
Ö(v ExElT of dr log No + Rdy log Nx)
Unknown-Variann OLS (Pacchiano, 2024)
Non-linear
x
Ö(dr v Ever of log No + Rdy log Nz)
VACB (Theorem 4.2)
Non-linear
x
Ö(ds v Exerry oi log Nx + dx (log N₂) 3/4)
(MDPs) with linear function approximation under heavy- tailed rewards with unknown variance, and use the linearity of both expected rewards and variances in linear MDPs to design a weighted regression algorithm relying on variance estimation. To the best of our knowledge, these works heav- ily rely the linear function structure and are hard to extend to the non-linear setting. The general question of designing a robust contextual bandit algorithm under the heavy- reward (or a reward with large range) for general function approximation is still lacking in the literature.
to Appendix A.2.
1.1. Additional Related Works
There is another line of literature targeting standard multi-armed bandit (MAB) setting with heavy-tailed re- wards (Huang et al., 2022; Chen et al., 2024; Genalti et al., 2024), where they obtain sharper gap-dependent bounds in the MAB setting. In the contextual setting with general func- tion approximation, however, one has lower bounds even in the linear setting with large action spaces (Lattimore, 2017). Consequently, the results are not directly compara- ble with ours. Regarding algorithms, we adopt the OFUL framework combined with weighted Catoni estimators and peeling techniques. In contrast, Huang et al. (2022) uses a skipping method based on Seen-ttt--Reulariieeed Leader, and Genalti al. (2024): Chen et al. (2024) design adaptive algorithms capable of handling unknown and unknown ment bounds. The remaining related works deferred to Appendix A.2.
different line of work called distributional RL estimates the full reward distribution (Wang et al., 2024b;a;c) under the unknown variance case to achieve variance-based re- gret bounds with general function approximation. However, their focus is on replacing the T- scaling with the cu- mulative variance and still incurs a polynomial dependence on R. Additionally, the distributional approach requires the stronger modeling assumption that the full reward distribu- tion, rather than just the expected reward is realizable.
There are some works considering the unknown variance case for contextual bandits without realizability conditions for the noise (Zhang et al., 2021; Kim et al., 2021; Zhao et al., 2023b; Pacchiano, 2024). Particularly, the most rele- vant ones to our work for the unknown-variane setting are Zhao et al. (2023b); Pacchiano (2024). Zhao et al. (2023b) develop a peeling approach for the unknown variance case without variance estimation in linear settings, and Pacchiano (2024) extend this technique general function approxima- tion. Nevertheless, all of these algorithms have an (dd) or RRd log Nz) term in the regret bound. We summarize the key results from the prior literature in Table 1 to better contextualize our results, and defer additional related works
1.2. Our contributions
This work considers different route for robustness to heavy- tailed rewards, building on the well-studied Catoni's 's mean estimator from the robust statistics literature. We design a contextual bandit (CB) algorithm that uses the Catoni mean as a robust device for constructing a regression error estimator for the excess loss, given some function class JF for predicting the expected reward. Using the variance- dependent concentration of the Catoni estimator, we conduct careful analysis of our algorithm and show that its regret scales as Ö(1 Eneer of dz log Nx d log Nz), when
2

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
the reward variance of is known at each round L.
known. The (pseudo-) regret is defined as
Since reward variance information is seldom available in practice, we refine our approach for cases with unknown variances by employing a multi-level uncertainty estimation for the expected rewards of a carefully chosen subset of actions. For this approach, we obtain regret guarantees dependent on the fourth moment of the reward, while still maintaining a logarithmic scaling in R. Formally, the regret scales as O(dr v Eierry of log Nf + dl )-)) Notably, our method does not rely on some other function class to help predict the per-round variance as a function. Instead, we estimate robust averaged variance quantity, and show that it approximates the averaged true variance up to logarithmic factors in R.
Rr= = E
Σ 1E[2]
max f* ffxx DEA:
To describe the structure of the general function class, we define the following (eluder dimension) quantities (Gentile et al., 2022; Russo & Van Roy, 2013) as Definition 2.2 (Eluder dimension (Gentile et al., 2022)). Given sequence of ordered actions X (2,, '.. .IT) E X1 X2 ... x dr and function class F, let the eluder coefficients be
(f1(z) f2(x))) 1022 fi.EET Eie (fi (ax)) f2(x;)) l0p
sup
Dy(2; ([-1, (--))) == D2 (T. 1; 1))
Overall, our results significantly improve the state-of-the- art in variance- aware regret guarantees, that are amenable to practical reward structures. We summarize our results relative to the most relevant prior literature in Table I.
Then we define the eluder dimension as:
111 dim(F, 0. min (1 ((-=)))
dim.,r (F))
X (T 11. dim o())
2. Preliminary
The weighted eluder coefficient D3 describes at each time step t. how much the in-sample error can bound the out-of- sample error. We can illustrate the eluder quantities with linear function approximation. If the function class F is embedded into linear mapping F = (0TØ(..) 0 E Rd. ||0||2 I B), and we define the covariance matrix Σ, ===Eitt EiEld 24 /oī, the weighted eluder coefficient can be simplified as
Notations. For any integer n, we use the short-hand nota- tion [n] = [l....,n}. n.. and define [in] = (21,.... F.J. We use Ô to omit terms logarithmic T and R. The compre- hensive table of notations is provided Appendix A.I.
We consider contextual bandit problem over T rounds of interactions between agent and the environment. At each round E [ the environment generates decision set X₂ E X' where each element x E X2 is a candidate action for the agent. After observing X₁ the agent plays an action 24 E Xr and observes the reward y/ = (x=) + 7/-- Particularly, this setting subsumes classic contextual bandit where an action de E A chosen upon observing context 2 at round t, since can always set X; {z+ x A}. We make the standard boundedness assumptions that
D3 o; 11-
((01-02) 02) (0)2)))()//000 Exete- 02) ((x:)/o.)² S
((z)
sup 6..0
E._1'
(1)
where the inequality applies Hence, the eluder coefficient reduces to how much a direc- tion is explored in the linear case.
inequality.
Imd S R, Ee, 0, Eng S o.
The summation of eluder coefficients over T time steps is the eluder dimension. The (weighted) eluder coefficients and the eluder dimension are broadly used in general func- tion approximation (Zhang, 2023b; Ye et al., 2023; Agarwal et al., 2023; Zhao et al., 2023a). For the linear case in d-dimensions, when all the o, [r- are 1, the (F) can be bounded in terms of d'log d (Zhang, 2023b; Agarwal et al., 2023). When the weights are larger than a, we can regard ø'(x) = o(z)/ā as the new feature representation and bound the dim,, (F) via the elliptical potential lemma (Abbasi-Yadkori Yadkori & Neu, 2014).
We assume access to function class JF X - 1- R] such that f* E F. For a function class F, we recall the standard definitions of e-cover and covering number (see e.g., Wainwright (2019); Zhang (2023a)) as follows.
Definition 2.1 (u-cover and covering number). Given function class F. for each v > 0, a v-cover of F with respect to Il denoted by C(F,v) satisfies that for any f E F. we can find f' E C(F, 2) such that [| - f'l I v. The e-covering number, denoted as N(v, the smallest cardinality of such a C(F.v).
3. Bandits with Known Variance
We assume that the function class F consists of bounded functions, that is, [f(z) I Ly for all f E F and r E X. The variances oe each time step are not necessarily
In this section, we present upper and lower bounds, when the per-round variance of each action is known the learner.
3

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
3.1. Lower Bound
Algorithm Catoni-OFUL.
Input: Parameter >> 0, and Be for each t (T].
We start with a minimax lower bound for the class of multi- armed bandit problems where the variance of each action's s reward is known to the learner.
for 101,2.... do
Pick action 2t = argmax, maxjen--1
Observe the reward ye:
Theorem 3.1. For any integer T > O, there exists a contextual bandit problem such that any π { will incur regret least R( / E o.), where for Varz, YT= and the expectation is jointly over any randomness in the environment as well as the algorithm.
Let = max (at, de: / (24: 11-))
Estimate fi in (3); Construct confidence set
Fr R==
(1E
Σ sE((]
0 ((a.)--(((u)) = }B²}
In other words, the theorem states that the regret of any contextual bandit algorithm scales with the square root of the sum of the variances of the rewards for its chosen actions. That is, rules out regret bound which scales solely as the variance of the reward of the optimal policy's is actions.
end for
parameter, for some constants a, A independent of Zz. For an appropriate e and any large enough I, with probability at least 1 - 28 we have uniformly for all 0 [a, A):
The detailed proof is deferred to Appendix B.I. The in- tuition is to construct two bandit instances, each with two arms (2) In the first instance, the arm In has a de- terministic reward while ø2 has higher expected reward, but with a large variance. In the second instance, 22 has smaller mean reward. Clearly, the optimal action 2 has variance of zero in the first instance, but any algorithm needs sufficiently many draws of 22 as well to distinguish between the two instances. In the sequel, we will present matching upper bound for our robust estimator.
0 @ + Eel) (wi 11)
(atonia(1Zi)ec - -p -
4 c
+
Ot
t¹
where tn contains log terms and is given in Appendix E.I.
This inequality differs from the prior concentration results for the Catoni estimator it is uniform for all 0 [a, A). In the sequel, we use this flexibility to choose 0 based on the samples. The formal version of the lemma and the proof are deferred to Appendix E.
3.2. Upper Bound for Known Variance
Catoni Estimator We first introduce Catoni estimator. This is a robust estimator proposed by Audibert & Catoni (201 [see also (Lugosi & Mendelson, 2019)) to estimate random variables with bounded variance and unbounded range. Following Lugosi & Mendelson (2019, section 2.2), to estimate t-1
A Aloorit By incorporating the Catoni estimator into the Optimism in the Face of Uncertainty Learning (OFUL)(AbbsiiYaddk)) Yadkooi et al., 2011), we propose the Catoni-OFUL approach in Algorithm Given failure prob- abilities and confidence parameters 3r the algorithm chooses the action 2t, with the highest optimistic reward by maximizing across all functions in confidence set F,, as in the standard OFUL approach.
-'En EZi, first define function
if 2 0, - log(1 r + x² /2) if < O.
log(1 x x2
(x)
Then for some parameter 0 > 0. Catonio ((Zz) (e(q) is the unique zero of the antisymmetric increasing function
The key difference lies in the construction of robust confi- dence set based on Catoni's mean estimator. We first define per-sample weight o, as the maximum of parameter a, the variance o, of the reward of 24, and uncertainty term based on the eluder coefficient D (I ((-1) 0--))).
[x: (Z))ee)))) = Σ (0((2. x)).
Then, we define a robust estimator of f*, given the data, as the solution to the following andle--point problem:
We first provide the following result about the concentration properties of the Catoni estimator, which we use in various places to prove why our design of confidence sets in the sequel algorithms.
1 Σ (x( f(x.)) iE[t]
fc argmin max Li(f. fer PEF
Lemma 3.2 (Informal). Let Z, be a random variable adapted to filtration the He with a uniform bound [zel S R,
21Catoni (f. ((Z+(f ('))))))))))))))
(3)
E GIZ.|H,-11 P.., Evete E (Z, p,) [Ha-1 < V for
where we use the notation f(( (f((((
some fixed V. Let J == 1-1 Eiet Ms Let E [a, A) be a
(()))))((((a)) - yı), ((6) scales as 0 ((Vlog(1/8) and

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
specified in Table 2, and the parameter Oclf: is also specified in Table 2.
function space and uses the uniform covering number. The novelty of the proof lies in the following two parts.
To understand this definition, we observe that fff is robust sample-base baspe estimator of the true excess risk:
Part I: Concentration of excess loss Recall that for any f.J' E F, we formulate the excess loss [=) to estimate the excess loss [f, f') in (4) under heavy- tailed noise. Here the conditional expectation of the vari- able Zz(f. f') is E|Z, = (f(x)) - (z)) I (xx)))/a? Since the standard Hoeffding's inequality leads to the error dependent on the uniform noise bound R. which can be extremely large in our setting, we can utilize the robustness of the Catoni estimator via Lemma 3.2 to obtain the following lemma.
R((,s))== 1
[x(((())) -x:)) - x)
/े B (M(as)- (xx))) 1
Σ
+ (f(x))))
v.)
(4)
Lemma 3.5. For all large enough time steps and two fixed S. S' E Fi-1, with proper choice of parameters a, Br and e, we have with probability at least - 8/N2.
where the expectation E& is taken with respect the noise T)-- Since I, is the only term that depends the heavy-tailed noise, it is approximated by the f-robust Catoni estimator Catonig ( f') (ete)) in f'), Then, we include all the f E Fi-1 that have small weighted squared loss to ft in the confidence set Fr.
L. 1¹) -
2
Σ E[Z.(f. s2) .E.
-
Remark 3.3. Since the min-max optimization in (3) can be hard to solve, we provide an alternative (Algorithm 3 in Appendix D), where we construct a candidate set first similar to the confidence set, and then choose an estimator from the candidates randomly. This approach can improve the optimization efficiency and ensure the same regret bound as Theorem 3.4. Similar results also apply to the unknown variance case in the next section.
$ 2 ) 3 where V'(f.f) = Eieto (((x)))((==)))
The values of the parameters are shown in Lemma B.2, and the proof is deferred to Appendix B.2. Importantly, 83 in the lemma above only has log It dependence.
Theorem 3.4 (Informal). Under Algorithmm I with appropri- ate choices of the parameters a, X, and 3, with probability 1 20, we can bound the regret by
Part II: Sharpness of the confidence set Next, we show that for our choice of 3r, the true function f E F, with high probability for t E [T] that are appropriately large. To prove this we define [f( = max Le), apply Lemma 3.5 with on both sides of the inequality to get the following result. Lemma 3.6. Under the conditions of Lemma 3.5, we have for all large enough t [T] with probability at least 1 8,
Rr (TT
Σ of dim Jr (F) log.N((..)) :E(T]
fe. and take minimum over f E F
+ b log N(, v) dim (.((
(f. 2 max { (vi(fe. -VV('. v. -8 82] MEF
The formal version of the theorem and appropriate choices of the hyperparameters are provided in Appendix B.2. The variance dependence in our theorem matches the lower bound in Theorem 3.1. Specifically, for the determinis- tic case where o, = 0 for all & E [T], the bound is re- duced Ö(og (FF v). dim (F)). and in the worst case where 0r = (11) for all E [T]. the bound be- comes Ö6, Tdim J. r (F) log u)). We note that the bound depends only polylogarithmically on R, improv- ing upon most prior results as observed in Table 1.
-)
where the maximizer for I' is Smaxx = 3 Li.
The proof is deferred to Appendix B.2. An analogous argu- ment also yields an upper bound Li(f*) S 3 /3, as shown in Appendix B.2. Furthermore, since fe is the minimizer of L-).), we have
Z - - 2 Vilfe.
3/,
which leads to f E Fr.
3.3. Proof Sketch
Ultimately, if the event f E F₂ for a large enough t hap- pens, the regret can be bounded by using the definition of 3, and the definition of the cluder dimension. Since this part is standard, we defer the details to Appendix B.2.
To illustrate the intuition clearly, we ignore the covering number in this subsection, and assume that the function space F is finite. The detailed proof considers an infinite
5

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Algorithm 2 Variance-Agnostic Catoni Bandit
respect to history information in V for any X,
1: Input: Parameter 7 > 0, =
I.
(10g((100666))
Di(x) = sup 1 v Vievs (f(x.) ('(x:)))
[f(e) [())]
2: Initialize the estimators for all layers: X' + 2- 86 +
2 [+1, Vo + 0 for all E L].
(5) At each time step t, starting from 1 L, if there ex- ists a decision E X with sufficiently large uncertainty D2( > 2-1, this decision will be chosen; otherwise, all the actions x E X2 that are far from the optimal reward max xex (z) are eliminated, and the remaining actions compose the decision set X!+1 at the next level. The pro- cess does not stop until (a) there exists an action with large uncertainty; (b) or the uncertainty of all the remaining de- cisions is small (D)))) S y for all X, X²). If case (a) happens, will construct the estimation for the current layer. Specifically, for each level l, the variance estimator Var, uses plug-in:
3: for ,TT
4: Observe X,, and initialize X2 Xz, + la.
5: while zı is not specified do
6: if (x) 1 y for all x E X² then
7: Choose Iz, fi-1 argmax 1 f(x))
8: Observe ye.
9: Break,
10:
else if (x)) < 2 for all x E X2 then
11:
Update X + (or E X I (=) >
xax fi-1 (x) - 2- 11
12:
else Choose 21 E X² such that Di(xt)) > 2 and observe
13:
Vt-
14:
Update we < ((
15:
Update the index sets: V/ < W U (1) and w
Vin1 for 1' # Optimize ft as in (7), and choose the confidence set F. defined (9).
Var, =:/Catonigg ( sew b1.
16:
(6)
17:
end
where the detailed choice of bonus B/. the parameter 0 and ('6) are provided in Table 3. Then, the function esti- mation follows Algorithm 1:
18:
Update 1 4-4 1++1 1.
19:
end while
20:
For 1 E [7.] s.t. V = V
J1 1 Fi FL
21:
end for
1 = argmin max L( fEF P'PL-1
Σ 18
1 - FZ - f(a)))
4. Bandits with Unknown Variance
+ +2Iaatoni (
(7)
In this section, we generalize to the case where the noise variance Eag for any i E (T] is unknown. In addition to the assumption that for any f E F, ll < Ly, and |l E [0, 1], the following condition for the noise vari- ance is required.
where
(x;)) (2,) y:)/ the parameter f') given Table 3. Essentially, the weight w; can substitute the per-round variance in nor- malizing the loss L/, as we will show in Lemma 4.5 that d Var, can be upper and lower bounded by the true variance Eiev; o2/ww up to additive and multiplicative constants.
Assumption 4.1. For each time step t E [T]. the noise Th satisfies that there exist positive constants on and c, such that E[n Fi] = O, Eni = of S of and Var[n?]F]] x
- Furthermore, since Var, appears in the Catoni-mean's 's con- centration (Lemma 3.2) for 1-1 i-'Eiew Eie (J),,'), we see that normalizing the losses with w; results in variance-aware concentration just like the known variance case.
Gn Var (Te Fr).
4.1. Algorithm
For the two parameters require knowledge of the cumula- tive variance, we substitute the true summation with the optimistic variance estimator Var,: one is (ff, defined above, and the other is B/. which is iteratively computed:
Since variances oa are unknown, traditional variance weight- ing techniques necessitate an accurate estimation for the noise variance at each time step (Huang et al., 2024: Li & Sun, 2024). To circumvent the complicated variance esti- mation, we adapt the SupLinUCB--typ (Chu et al., 2011) algorithm with adaptive variance-aware exploration from Zhao et al. (2023b) to propose Variance-Agnostic Catoni Bandit (VACB) in Algorithm 2, where we split the contexts {zee Jee)e into T. subsets according to their uncertainty. For each level E [L] let V denote the set of time indexes within [t] when the estimator update happens. Specifically, we use the following short-hand notation of uncertainty with
(5) = e = (c 2
Var + (66)2 A, + X))
(8)
where the specific value of 3 and A, is provided in Table 3, and A, is small term depending on the parameter v for the u-cover in Definition 2.1.
In summary, our algorithm needs to estimate only an ag- gregate variance instead of estimating the per-round vari-
6

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
ance exactly, as we would require for applying a variance- weighted directly in the agnostic setting. This requires access to another function class that can model variances, which we cleanly avoid. Finally, we define the confidence set
Proof Sketch The main challenges for the variance- agnostic algorithm are: (I) how to obtain the concentration inequalities when the weights are not based on the noise variance: (II) how to make accurate substitutions for the sum of variance Σie(g] of/w/ in the parameters; and (II) how to deal with the regret of each level I. The insight of solv- ing challenges (I) and (III) basically follows previous work (Zhao al., 2023b; Pacchiano, 2024), but for (II), because of the heavy-tailed setting, contribution is designing the robust Catoni variance estimator, and demonstrating the esti- mator almost has the same order as the true wverage-variane E; of /w/ up to constants with logarithmic dependence on the reward range R. We address these challenges in the following three parts, respectively.
Fi = {SEFLI: vew!
Σ 1 (f(x) f(a))) +12 s { wa
(9)
4.2. Analysis
Theorem 4.2 (Informal). Suppose that Assumption 4. holds. With appropriate choices y, d'(6), v and By if is large enough, with probability at least 36, we can bound the regret of Algorithm 2 by
Part I: Average variance bound for concentration In this part, we study the concentration of the excess loss for each level. For clearer illustration, we omit level / when there is no confusion and denote D; = (z.)) for short. Distinct from the known variance case where one directly takes the variance o, as weights to derive an upper bound for the variance of (f, f'), we start with an alternate bound in terms of the weights wy:
RT -ō -0(1 L,
Σ of log)((F 1/2 LETT]
(Fm
+ [.ydim,,(FF(00g ((F,))) u)) +0))
This theorem provides variance-dependen upper bound when variances are unknown, which matches the upper bound when variances are observed (Theorem 3.4) up slightly worse dependence on the eluder dimension. The higher order dimension term arises in the analysis of the peeling technique.
S Σ Var MariZ f')]
SEV
Σ
(f(a.) - (()))) - -vi)² x4]
iev.
(f(x;) - (f(x:)- (xx)) of wm
When compared to the upper bound Ö(d, Ö(d/Irer Eierry of
wm
(35T1/44 (Li & Sun, 2024) for the linear setting with di- mension d and unknown variance, our bound gets rid of the dependence on T which means that our bound is still optimal up to the dimension when the sum of variances is small: Σremr of of (T).. We give more intuition why our algorithm admits this sharper bound in the proof
When the variance is known, and w = o, as in Algorithm 1, the second term in the final inequality is uniformly equal to 1.
When the variance is unknown, we can no longer weight the variances, instead, we uniformly bound the first term and aggregate the second term as shown below:
sketch below, with details deferred to Appendix C.
(f(x:) f(x))))
Remark 4.3. We compare our results here with a con- temporary work (Jia et al., 2024). The main difference is that they assume that the noise is bounded such that rr E [0, I]. and we consider heavy-tailed rewards. Besides, although we both get variance- variance-dependen dependent bounds, the fo- cuses are distinct: they aim to obtain better regret bounds when the eluder dimension is larger than the number of actions, while we aim to obtain logarithmic dependence on the reward range. Hence, we develop algorithms based on the OFUL structure, while Jia et al. (2024) build on the SquareCB approach. Regardless of the dependence reward range, for the weak adversary with revealed vari- ance, our upper bound Õ(VA- df log N) is incomparable to theirs OVVAAlog N + dz log N). For the strong adver- sary. we both use the peeling technique and thus, our bound superior on the dependence of reward range.
S, < maax KEW;
DJ Σ 1
(f(TT) - (((x)))
< max Ew wp
+
w?
w
Uniform bound S 2- -,92
where the first inequality uses the definition of D,, and the uniform bound holds because Di/w; < 2- at level I from Algorithm 2. Also f E Fi implies that
Σ (f(x+)- - f(
(f(++) - fo 1 (x+ ))
52
w
vE(c-1)
(f' - f (x.
+
Σ
wm
re((-1]
<4.p_
7

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Here the first inequality applies the Cauchy-Schward in- equality, and the second inequality follows from the defini- tion of Fi-1.
Lemma 4.5, Under Algorithm 2 and the condition that f" Fi when 2 is large enough, have with probability at least 1 - 28 for all large enough E [T].
Therefore, by not requiring a uniform bound on the close- ness of the variances and the weights, we can successfully derive the concentration inequality for -
of < 2
Σ
Var
w
(10)
Lemma 4.4. Under Assumption 4.1 and Algorithm 2, we have E. Dz/we S 2-- P. w4 2 1. Then, a large enough E [T] and for any f.f f E Fi-1, with probability at least 8 8/TL,
Var,
3 S
(1(06)0 + +,) w
2 N
Part III: Bounding the regret for each level I. Con- ditioning the high-probability events, can show that for any time step E V/ the true optimal decision 27 = argmax (*)x remains in the candidate set X during the level-wise elimination in Algorithm 2, where is the level from which D; arises. By the definition of X/ we know that 24 cannot be far from xt, thus we can demonstrate the following lemma.
L((f.f' Ra( S 2 (i f') 1 Bi_
(Eiev, ot e//x))
+
Var, + A.)
Var
The more involved version of this lemma and the proof is presented in Appendix C.1. Note that the variance estima- tor Var, appears on the right-hand side of the inequality above because the parameter Of J') cannot be directly set in terms of Eiew, df/w?. and we instead use the sur- rogate Var, The Var, dependence will be eliminated af- ter demonstrating the close relationship between Var, and Eiev, ///w/ in the next part.
Lemma 4.6. Under Assumption 4.1 and Algorithm 2, if f E Fi and (10) hold for all large enough t,l, I, then, for all large enough and t V we have:
2 E X/,
and the regret at the 1-th level is bounded by
Part II: Accuracy of variance estimation. For any E (olx))///uss /wß. The conditional [4. let Vi(fi-)) = (ui (xx)) expectation of this term is
Σ -( S 2--1+331- 1
(EW)22001))
E[V.(fi-))=.)) (o + fo-
The details and the proof of the lemma are deferred to Ap- pendix C.I. Hence, it suffices to bound the size of W/ We get via (x(x)//r = 2-1 that
Then, by using Lemma 3.2 and using an argument similar to Part can control the concentration error
(D((z))2 w?
#Catonia ((V)..(((VVV ((V((fi=))
Σ B(V((f--))=..) KEW.
| 22
Σ IEVT.
2 (im,
Hence, it suffices to bound the gap between the variance and the expectation:
Ultimately, by combining the results above the choice of 3 in (8), we can obtain the bound for cach I. The final regret is obtained by summing the regret for level 1= l=,,..,
Σ ElVi(fe Σ
oe
1
(fx)
fi (2x)))
5. Conclusion
In this work, we consider contextual bandits under heavy- tailed rewards (rewards with a large range R) with general function approximation. The key novelty of our approach is the application of Catoni's mean estimator for non-linear settings based on the observation that excess loss estimation is the correct object to robustify. For the verrivvre case, the Catoni-OFUL. algorithm combines the adaptive Catoni estimator and the variance-weighted optimization. The algorithm enjoys a variance-based regret bound with only polynomial dependence on R. When the per-round variance is unknown, our proposed criincceaggossic Catoni
(fr)(())) - S (xx))²
+ - w/
m!
32
B2 < 5 21
w?
where the first inequality uses f E F,-1, the definition of D; and Dz/w; 2-
Recalling the definition (6) of Var,, we derive the following accuracy guarantee of this estimate compared with the true aggregated weighted variance:
8

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
bandit algorithm carefully peels the samples based their uncertainty and utilizes a plug-in estimator for the of variances. The algorithm also obtains variance-based bound depending on R logarithmically, but has a worse dependence on the eluder dimension. Improving this is left as future direction. We also provide lower bound to show that our regret bounds are optimal the leading-order term.
References
Abbasi- Yadkor,, Y. and Neu, G. Online learning in mdps with side information. arXiv preprint arXiv: 1406.6824 2014.
Abbasi- Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
For the future work, since the Catoni estimator is a gen- eral device from robust statistics, it might also be useful to investigate if it enables us to handle other forms of noise, such as adversarial corruption (He et al., 2022; Ye et al., 2023; 2024b). Additionally, while we obtain information- theoretic results in this paper, the algorithms are not easy to implement, both because Style algorithms are always tricky due the version space structure, and the function- dependent choice of B in the way we invoke the Catoni estimator makes things even harder. It would also be inter- esting to extend the results to general MDPs.
Agarwal, A., Jin, Y., and Zhang, T. VOQL: Towards optimal regret in model-free rl with nonlinear function approxima- tion. In The Thirty Sixth Annual Conference Learning Theory, pp. 987-1063. PMLR, 2023.
Towards
Audibert, J.-Y. and Catoni, O. Robust linear least squares regression. The Annals of Statistics, 39(5):2766-2794, 2011.
Bubeck, S., Cesa-Bianchi, N., and Lugosi, G. Bandits with heavy tail. IEEE Transactions Information Theory, 59 (11):7711-7711 2013.
Acknowledgments
This work was partially supported by NSF grant No. 2416897 and ONR grant No. N000142512318.
Chen, Y., Huang, J., Dai, Y., and Huang, L. uniinf: Best- si-booh-wooldd algorithm for parameter-free heavy-tailed mabs. arXiv preprint arXiv:2410.03284, 2024.
Impact Statement
Choi, H., Mela, C. F., Balseiro, S. R., and Leary, A. On- line display advertising markets: A literature review and future directions. Information Systems Research, (2): 556-575 2020.
This paper presents work with the goal of advancing the field of reinforcement learning with heavy-tailed rewards. The utilization of the Catoni estimator, the variance- variance-weighting technique, and the peeling approach under unknown vari- ances can make online-decision making robust heavy- tailed rewards and when the rewards have a large range. The work is primarily theoretical, with no immediate social consequences.
Chu, W., Li, L.., Reyzin, L.,, and Schapire, R. Contextual bandits with linear payoff' functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
Cont, R. Empirical properties of asset returns: stylized facts and statistical issues. Quantitative finance, 1(2):223, 2001.
Genalti, G., Marsigli, L., Gatti, N., and Metelli, A. M. (E. a)-adaptive regret minimization in heavy-tailed bandits. The Thirty Seventh Annual Conference on Learning Theory, pp. 1815-1915. PMLR, 2024.
Gentile, C., Wang, Z., and Zhang, T. Achieving minimax rates in pool-based batch active learning. In Interna- tional Conference on Machine Learning, pp. 7339-7367. PMLR, 2022.
He, J., Zhou, D., Zhang, T., and Gu, Q. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. Advances in neural information processing systems, 35:34614 346225, 2022.

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
He, J., Zhao, H., Zhou, D., and Gu, Q. Nearly minimax optimal reinforcement learning for linear markov deci- sion processes. In International Conference Machine Learning, Pp. 12790-12822 12822. PMLR, 2023.
Pacchiano, A. Second order bounds for contextual bandits with function approximation. arXiv preprint wrxiv:2409.1619, 2024.
Russo, D. and Van Roy, B. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
Huang. J., Dai, Y., and Huang, L. Adaptive best-of-both- worlds algorithm for heavy-tailed multi-armed bandits. In international conference on machine learning, pp. 9173- 9200. PMLR, 2022.
Shao, H., Yu, X., King, I., and Lyu, M. R. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. Advances in Neural Information Processing Systems, 31, 2018.
Huang. J.. Zhong, H., Wang. L., and Yang, L. Tack- ling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance- dependent regret bounds. Advances in Neural Information Processing Systems, 36, 2024.
Wagenmaker, A. J., Chen, Y., Simchowitz, M., Du, S., and Jamieson, K. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learn- ing, pp. 223899 PMLR, 2022.
Hull, J. Risk management and financial instituttinns, Web Site, volume 733. John Wiley & Sons, 2012.
Wainwright, M. J. High-dimensional statistics: A non- asymptotic viewpoint, volume 48, Cambridge University Press, 2019.
Jebarajakirthy, C., Maseeh, H. I., Morshed, Z. Shankar, A., Arli. D., and Pentecost, R. Mobile advertising: A systematic literature review and future research agenda. International Journal of Consumer Studies, (5(6):1258 1291, 2021.
Wang. K., Kallus, N., and Sun, W. The central role of the loss function in reinforcement learning. arXiv preprint arXiv:2409. 12799, 2024a.
Jaa, Z... Qian, J., Rakhlin, A., and Wei, C.-Y. How does variance shape the regret in contextual bandits? Advances in Neural Information Processing Systems, 37:83730- 83785, 2024.
Wang. K., Oertell, O., Agarwal, A., Kallus, N., and Sun, W. More benefits of being distributional: Second- order bounds for reinforcement learning. arXiv preprint arXiv:2402.071 198, 2024b.
Kim, Y., Yang, I., and Jun, K.-S. Improved regret analy- sis for variance- variaice-adaptive linear bandits and horizon-free linear mixture mdps. arXiv preprint arXiv:2111.03280 2021.
Wang. Z., Zhou, D., Lui, J., and Sun, W. Model- rl as a minimalist approach to horizon-free free and second-orded bounds. arXiv preprint trXiv:2408.08994 2024c.
Wei, C.-Y., Luo, H., and Agarwal, A. Taking a hint: How leverage loss predictors in contextual bandits? In Conference on Learning Theory, pp. 2020.
Lattimore, T. A scale free algorithm for stochastic bandits with bounded kurtosis. Advances in Neural Information Processing Systems, 30, 2017.
PMLR,
Li, X. and Sun, Q. Variance-aware decision making with linear function approximation under heavy-tailed rewards. Transactions Machine Learning Research, 2024.
Xue, B., Wang, G., Wang, Y., and Zhang, L. Nearly opti- mal regret for stochastic linear bandits with heavy-tailed payoffs. arXiv preprint a004v:2004. / 13465, 2020.
Lugosi, G. and Mendelson, S. Mean estimation and regres- sion under heavy-tailed distributions: A survey. Founda- tions of Computational Mathematics, 19(5):1145-11) 2019.
Ye, C., Xiong, W. Gu, Q., and Zhang, T. Corruption- robust algorithms with uncertainty weighting for nonlin- ear contextual bandits and markov decision processes. In International Conference on Machine Learning, pp. 39834-39863. PMLR, 2023.
Medina, A. M. and Yang. S. No-regret algorithms for heavy- tailed linear bandits. In International Conference on Machine Learning, pp. 1642-1650. PMLR, 2016.
Ye, C., He, J., Gu, Q., and Zhang, T. Towards robust model- based reinforcement learning against adversarial corrup- tion. arXiv preprint arXiv:2402. 08991, 2024a.
Nair, J., Wierman, A., and Zwart, B. The fundamentals of htavy- Properties, emergence, and identification. In Proceedings of the ACM conference on Measurement and modeling of computer systems, pp. 387-388, 2013.
Ye, C., Yang, R., Gu, Q., and Zhang, T. Corruption robust offline reinforcement learning with general function ap- proximation. Advances in Neural Information Processing Systems, 36, 2024b.
10

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Zhang, T. Mathematical Analysis of Machine Learning Algo-
rithms. Cambridge University Press, 2023a. URL ht:p: / //tongzhang wwwpannmmmo..moooooooeeeeoooo book html. in press, also available as http://tonnghanggmm.. 1t-book, html.
Zhang. T. Mathematical analysis of machine learning algo- rithms. Cambridge University Press, 2023b.
Zhang, Z.., Yang, J., Ji, X., and Du, Improved variance- aware confidence sets for linear bandits and linear mix- ture mdp. Advances in Neural Information Processing Systems, 34:4342-43555 2021.
Zhao, H., He, J., and Gu, Q. nearly optimal and low-switching algorithm for reinforcement learning with general function approximation. arXiv preprint arXiv:2311.15238. 2023a.
Zhao, H., He, J., Zhou, D., Zhang, T., and Gu, Q. Variance- dependent regret bounds for linear bandits and reinforce- ment learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference Learning The- ory, pp. 4977-5020. PMLR, 2023b.
Zhou, D. and Gu, Q. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint ar arXiv:2205.1 1507, 2022.
Zhou, D., Gu, Q. and Szepesvari, C. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532 4576. PMLR, 2021.

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
A. Notation Table and Additional Related Works
A.1. Notation Table
To improve the readability of this paper, we provide Tables 2 and for the notations used in this paper.
Notation
Description
n
(1,....n2)
R
The range for the noise Th, Vt E [T']
The variance for the noise
Ls
The range for any function f E JF
N
The e-covering number for the reward function class F
Dz(æ, o; 1111 1-11),
The eluder coefficients in Definition 2.2
D7 11- I-1))
dim(F F, o)
The eluder dimension in Definition 2.2
dim,,7 (F)
Catonia ( (2, (Ee)))
Catoni estimator defined in (2)
4 log
48R( R)r²
log (A/a)
min(1,a)ca
c(8)
O log RL RL,,
(N)()) v)/5)) 2x(0)
O. f
Eiet
1+(2010))
+2a
3,
The confidence radius, O Logg uF,
1/vT
a
A
((1) 0 O
0
Table 2. The Table Notations for the Known Variance Case.
A.2. Additional Related Works
Warihhee regression. Variance- Variance-weighted regression has been studied for light-tailed noises for both contextual bandits and Markov Decision Processes (MDPs) with linear and general function approximation. Specifically, Zhou et al. (2021); Zhou & Gu (2022) apply variance-weighted regression to obtain second-order bounds for linear contextual bandits under the known variance case. They also use the weighting technique for linear mixture MDPs under unknown variance case, where they assume that the variance can be realized by linear function class. Similar weighted regression also appears in MDPs with linear and general function approximation to achieve the optimal regret bound (Agarwal et al., 2023; He et al., 2023; Zhao et al., 2023a), and in the adversarial corruption settings make the algorithm robust to adversarial attacks (He et al., 2022; Ye et al., 2023; 2024b;a).
Heavy-tailed rewards in bandits and RL. The topic robustness to heavy-tailed rewards has received a considerable amount of attention recently. Bubeck et al. (2013) the first to study heavy-tailed rewards in multi-armed bandits. More generally, robust mean estimators (Lugosi & Mendelson, 2019) such as mean have been applied to linear contextual bandits (Medina & Yang, 2016; Shao et al., 2018; Xue et al., 2020; Huang et al., 2024: Li & Sun, 2024).
truncated mean and Catoni's
B. Proofs for the Known Variance Setting
B.1. Proof for the Lower Bound
Proof of Theorem 3.1. For any 0 < 1//.00 0/2 and R > v3, define three distributions
20.
w.p. atc
20.
w.p. a-C 2n a- w.p. 20
27 otc
Pr 01 + ) pt
2,R,
w.p. 20
P-
20
0, w.p. 1 (oto
(a (a-c)(1+222 2a
0,
w.p.
20
12

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Notation
Description
The union bound for of V [T]
Ca V
The union bound of the ratio: Var[n Fil S cy Var[n] The set of time steps when the update happens for level in Algorithm 2 The parameter in the uncertainty 2- 2f for / E [L]
X
I.
[ogg(1075 (1076' (())
(())
sup / (M.))/(()))))/t)
(2) + cqy + 434, + 2682
(4(20)) + on + L3 + ( (b1_1)3))~1
Av
((Poly(L,Rul)))
00110s loss (RL Gn A. N)NLT/6)
(()
f')
((68)
(Vrr
(8))²
The confidence radius, 28)0(((0)))2 21 Var, + 60c 60)2 21 + 124 + 2X
A,
e (L (6))00.sd L R p.225 + R² L + RLL
Table The Table of Notations for the Unknown Variance Case.
We have the means
No 01 + 0(1+ R-
= (a (
Po. = (a- c)(1 R²),,
and variance
V, = 0,
V+ (o + e) (1+ R1+ \
S 6602
(11)
Va (40 -1+
1)2() S 20
Thus, the rewards induced by the last distributions P Po. have large Lι norm (2o R2) and bounded variances. Furthermore, we have
KL(P 0s pt))
6
log
6
+
σ 6
log
σ --6
+ (1- (a c) [11+R' ()(1+))+)) +)²))
log
σ 0+ g-E
20
t
RoR²
o o+E
20
a+e R
S(1 + R-2) 20
log t+
+ (1 +1+ R-2) T+E
log
0+E
20 0 e
2
<4(1 + R
Fix a policy т. Now, we construct two 2-armed bandits and let the context space X' = 0. For the first bandit B1, the reward of the first arm (a1) ~ Po. and the reward of the second arm Rí (a2) ~ PT,.- Thus, the first arm a₃ is the optimal arm for Br For the second bandit, we have R2 ~ Pa. and R2(02) Pat. and the second arm the optimal arm for B₂ but with large variance. For 2, let P. denote the distribution generated by the bandit environment B,, and let E, denote the expectations under P.. Then, have
Tc. 2
Te
E [r] 2 PI (1) T/2)
Eg[Ry] (1) T/2). 2
Then, by Bretagnolle-Hune Huber inequality, we have
Te (P < P2(T(1)) > T/2)) > Te
E, [r] + E2 [r]]
>
eXP(-KL(P1, (P))).
We also have
4(1 R 2 E (2)
KL(Pi1|Pb) = (P. <
σ²
13

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Thus, have
Te
4(1 + R
3- [NT
E [TT] + [ 2
exp
r²
By choosing é
we have
T
E1 Rr) + Eg Rr
2
4e V
4(1
B
(2)
Since the variance accumulates only when the arm 22 is pulled,
E
E T of. -
T2 [2T En Σ (ar m2)
6
which implies that
max(E,[Rr]) 2 12 E1 Σot) of)
Symetrically, we can also get
[a 1 E2 Σの;)
B.2. Proof for Theorem 3.4
Theorem B.1 (Formal version of Theorem 3.4). Under Algorithm 1 with the parameter = 1/VT, X 0(1) RT and
3. = 10
(12)
with probability
25, we can bound the regret by
R7 0
Σ of dim Jz (F) logNN(F,)) (E(T]
log N(F, v) dim J (F))
Notations
In the following analysis, we use the short-hand notation for any f.f F
(f(x)) fxx)))
V))fff):
0²
(E(d)
Recall that we define the excess loss and expected loss; for any EF
LUGS)) = (f'( - f(x:)) (t0000///(
tE(t]
R((ff)) Σ
E, (f(xx) - fz(()))) -f()))))))))))))))))))))))))( ((2)))=22((())-=((())() y)]
iEid
= Σ
[f(xx)) - -1o-2//(aa-0((000oaa-------))--- (x.)))
14

---

Part I: Concentration of excess loss To begin with, we focus proving the concentration between Le f`) and Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
where we define
1 ( ((x)) - y;), 2(1,f)= = of
20(0)
0,(ff)== =
V (1 (2(00)) B +1) + t
T20R
((6)
log
8
We also the short-hand notation for the covering number N (U),
Re(f, f'). We first consider two fixed functions f. F.
Lemma B.2 (Formal Version of Lemma 3.5). For each time step 2 (6) and two fixed f. E Fe-1, we take 0= 1/v/T and = 1, we have with probability at least -8/N2,
() -R( f3) -2 - (F
Σ (f(z;) - ((==))((()))))))))))))))
o
sE|d
) 5v(0)
VA
- +
6 02_1
2
Proof. We first compute the expectation of Zz(f, f")
M4 1 (f(x.)
and bound the sum of variance by
Var (ff,
Σ E
04 (f(x.) (f=))) -1)
REiA
sE[(]
(f(x)) (ax))) Vo(f.f)).
xE(()
We can also bound (f, f') [a, A] by choosing
A = ((5)
((8)
Q
88131/022 + 2
Hence, given choice of a = 1/vT and = 1, we have
48R(1 + 2AR))²
720R2
minn1, (6/N2T) log(A/a)) $ log
log
8/N2T
Thus, for any time step
12 1266 622(8) 2 4.2(6) + 2
mnin(1,a)e2 (8/N2T) log( log(A/a))
48R(1 + 22
15

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
by using Lemma 3.2 with a 1/vT and 1, we have with probability at least 8/N2T,
1 (((m)) - ((a) (xx)))
Σ iE|
(0.(I.))(V(L.)))+++ - xE(1]
+ 40) +E
Oe(S.()
1 (f(::) + 40)
max iE[[] o
f') +
1 <.<(1.""'( 2x(6)
VB(++2)+ + (6)
+c,
(13)
where the last inequality uses the definition of the weight of 2 ((01),11D( and f,f" E Fi C 11 get for any i E [t]
(f( - (xx)))
S
Lg 0²
sup f-''Fi--
ffx)))
Σ kE(--1)
- (((t))
+
0
v /Ekefe-11 क5 (f
- S +1
Σ (f(xz)) - (1) +2 Σ
1/ ((- +1
4u(5)
RE( 1]
kE(i-1]
V ( +
$ 26)
where the second inequality uses the Cauchy-Schwann inequality, and the last inequality uses the definition of F,-1. Via the choice of
2c(0)
(I
(1+ (2((6))-1 1 ( +
we get the right-hand side of (13) is upper-bounded by
4(00/\ (1+
+ + +e
su(oy 1+ VA 2
+ 2((6) V V
+ +5())e
S + VA 1
2 VV(. 96:2 + 1 + 50(0)
1 2 -V00,)+
V 2
+ (6) + 5x) +
3
6 1111
which concludes the proof by taking the union bound over i [T).
Lemma B.3. For any f, f E F, there exist two for f', E Fo such that [|f - follzo S v. 11 - -folloo S v. Then, we have
90L 360L3,12(0)vol
(1/20111))))
04.2
1(0)05/2e112
16

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Proof. From the definitions of 2,0, f"), we have (,(, s2, (2L, R)/a2, and
1
fz( - Ze(fuz f.)l
(f(x)) f(=))))) - v.) ने -
0
1
1 vd) ने (Fo(tz)) [o(())) s(x))) ((t)a) -())
(f(x)) - - -
0
6.
a²
From the definitions f"),,f"), we get ff) S (6)/c and
(66)
(6))
10.(. - 0e(Ju, v
(fe)) - ((x))))
-
(6)
Σ
((((,)) - ((x))) (
sE(()
(6)
/8L
60
Combining the two inequalities above, we have
(2. R).
A
Σ
Ceff. I') Z.(e:
10.(f. - 0c(f..
a²
iE
(0) 6LF
62 + R) (())
VLgul
a²
60133
Ro)oeel a²c
Then, by invoking Lemma E.2, we deduce that
|Catonie. (1Z, (at
1 ff) 2L,
+ R2/a² A+ -0, (2LF
2A
(e)
V (()))
R(0) ot (
a²22
(02)25/22112
Then, it follows the analysis for any f. F which uses the uniform cover.
Lemma B.4. If we take O(1/L] R2)10, a= 1/VT, c 1, and & = =(( (141)) For any f,f' e F and
any 2 (6), with probability at least - 6,
((f.f) - (f,f, =2
iE[(]
1
2 Volf.f) +)
3
Proof. For any f E F, there exist two Svz S' E Fr such that ||ʃ - fulloo Sullo
Sv,lf" -fllo S.. v. by invoking Lemma
B.3 with a 1/VT, e = 1, we have
[Catonio,(F.)) (1 (eej)) (atonia,.uu.::)(22 ft)
+ 9OL o
s (06)))
A
((6)
17

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Additionally, we get
- Re(for
Σ (1(((()))) - m.) -R,(((((a.) 11) (a(([(()))) - - + (m) - -3))
S 12
Thus, by using Lemma 3.5 with union bound over fu. S' For we have with probability at least 8,
-
Tx(f.S") - Lx(Se, + L, Re(Ju, + fo) Ro(S.5)
< Le(for fc) - (a(fer))) [i] 18L1)72+++7 TTA.
< 1 VV + 16((6) (1+ (1)
+ 966 - 5(()) (:0)))=11111 + 18L + +TA.
B
< (VCC,,) +VCC,,))44,oT - (1
V1 )
96 962 (6)+ 50) +
1 1-1 +8L + TDc
2
$ (1 3
where the last inequality holds since B satisfies that
82 6 ( [10(00(1+
v 96: (8) 5u(5) + 24T + +TA
2
Part II: Sharpness of the confidence set
Lemma B.5 (Formal version of Lemma 3.6). we take e = 0(1/L]3R'T')) ==V/T, 1, and under Algorithum I
with 8, = (1 22/4)), have for all large enough [T] with probability at least 1 5,
2 L(ff)
23 Volf.. -
L(f) s BP.
where the maximizer for f is fmaxx = 35 + f..
Proof of Lemma 3.6. By invoking Lemma B.4 with taking minimum over f' E on the both sides of the inequality and f fe, we have with probability at least -
Lifi,f22 2
{R((fen))
1 - villf - }...
max PeF--1
max p'fi-1
which implies that
- V.''' --v -
1 ]8 - -(((x))33/00 f.
Lofi) > max
Meti-1
{--
Σ
8-) -
max
mm
iE|!
2 V.((fr
1 32
3
18

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
where the minimizer is faax = = + Je
Additionally, by using Lemma 3.5 with taking minimum over f F the both sides of the inequality and f f fr, we have with probability at least 1 - 5
{R(((r,)) ==) }
Te(
S
max F'Fr-1
{ -V((f. 1 Vilf. fr) + }
max -efi-1
3 tt
where the minimizer of f' f
Lemma B.6. If we take
[LLL)/RATIO) a 1=1//T, and under Algorithm I with 3r (1((6)(1+ + +1/4))
with probability at least 1 5, we have f Fr.
Proof. We use the notation [+( max [x, fr), and recall that
B2(fsf) = Σ
E. - ((x)
xE
Σ
E. [(f(x;) y)) + (z;)) - y:)² (f( -.)) - (f.) - -.
u
xE(()
E, [(f(x.) - -y0 - (f.) - -.)
[V((f Vi(f'
Since ft argminjesF... Le(f), we invoke Lemma B.5 to get
2 0 Lo(f)) Lo(ft) V1
- 89,
which means that
vo(fa))) iE
1 ((()) (x:))
Part III: Bounding the regret conditioning on good events. We now recall the definition that T == {t E [T] it 7 (6n,)), we further denote the good events E = (f* E FieFFi).
Proof of Theorem 3.4. Conditioning on both good events En, we use the notation f((x) = argmax argmax f(z) can bound the regret of E by
max (x) - (xx) meX;
< max f((x) (x) S f((1)) (x))
E,,;
1
(f((o)) - f(-1(1)) f(-(5))))))))) f +t
<
J?
1E|t-1]
< (.
2 Σ
1
(f(())) - f
+2 Σ
03 (Ma))) +1
1
07
vE(t-1]
iE/l-1]
< (0
Br-1,
19

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
where the second inequality follows from X argmax ZE,; ft( the second inequality the definition of uncertainty Dr-- and the last inequality holds due to f* fi-1 Fi-1.
Combining this with the range bound that | & I,g, the cumulative regret is bounded by
RT = Σ
(max f'(x) (x)))
ZEA;
12
& 2L, 7c (6) + 2L,
Σ 1-TET
min (0, o (1)-))/r-1
(14)
To finally bound the regret, we bound the second term in RHS of Ry expression in (14) respectively. These steps mainly follow Lemma 4.4 in (Zhou & Gu, 2022). We can decompose the terms by considering Ij {t Ti TT (Ft, oe; 1/e- (--1)) 2 }} and I2 = (t ET, TT).
For the first set, we bound its size naively by
L
S
min 11, (1, (2 Fz [(-1] -(-1)) (Fm,,r(F).
EEL
For the second set, we bound the summation of terms of interest contraining on Ia by
Σ σ. 38 1 +
(2a 0(-1))
IEIg
Σ
2. 18 + 2. (1
1E of a
Σ
Te 30 + A.
0p-1))
1 Aolón,,
( 16 1
(0
(0t + aa) B -D (1,, ((--))
Σ
32L (2L,,(0n..))) DJ. (-10)
LE[T
LE[T]
(4)
lo7 + az2) dimo, dimo. + 16L 2
max 3 dim (F).
(E[T]
1E(T]
Here for (i) we use the condition for each distinct set and for (ii) we use the definition of dim, for both terms.
inequality for the first term and
Consequently plugging these back in (14) and take supremum over : [x]] T, we conclude that with probability least 1- 26.
R = 100(L 10.--2260..) (66.T) + Lydima, (F) L3 ((ōn...) max B dima.r
1E[2"]
Σ 32_ (o} a2). Vdima.r(F)
L
KE/27
= Ly Log (F,
dim (F) + Ls
Σ of
dim (F) log N ((FF)
[E[T]
where for the last inequality we pick À a
a a= 1/VT and O(1T1/2RTT1))
20

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
C. Proofs for Unknown Variance
C.1. Proof of Theorem 4.2
Theorem C.1 (Formal Version of Theorem 4.2). Suppose that Assumption 4.1 holds. Under Algorithm 2 with ry Vlog log (oL + en + A. + +))LTT1)), T 2 14()(6))², with probability at least
1/(o,T and ('()) = B(v
1 36, we can bound the regret by
RT = Li Σ of log N(F, 1/2 dFF
LE[T]
+ (F v)) (v tzn)
Notations In the following analysis, we use the short-hand notation for any S.J EF
(f(x.) f((x))
:= = Σ
w
Recall that we define the excess loss and expected loss: for each E [T], I E [L]. and any f.f' eF
E(f,f)= = Σ ((x)))
( ((7
NEW;
f) Σ
E. [[f[a))--aa)-+=22(t))----fff---- v)]
Wi
NEW;
Σ UCta)-//aaa---aaaaa//////aaa-111
kEV; w
where we define
Z(S.)= 1 -f))))(( - v.).
0(0)
(((f.f))
22 2- ( + 2) Varr + (((, + +2
((6) ( log (OL c, + A. + x)NLT/8)
The proof is decomposed into four main parts. In the following parts, we will show that the following two events both hold with a high probability:
o0 < 2Vr,, for arle E [L], 2 1076/(88) }
Earr
Σ
NEW! wi
(15)
{ EF, for I E [L., 2 2 1076:((8)
Conn
We will prove the events hold conditioned on each other sequentially for t = e(), We also use the short-hand notation for the covering number N == N).
Part I: Concentration of excess loss First of all, we also need to prove the concentration of excess loss for each / E [4].
In the following lemma, for conciseness, we neglect level / in the concentration analysis. Later, we will apply the result for each E [...
21

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Lemma C.2 (Formal version of 4.4). Under Assumption 4.1, given (rg, Mr, we veld. we define for i E [1 - 11, Fi
E (men)((m)) - [=x=)))) ////////// /wf + x S B. and D; Su - [(())-((m))) suPielt] w. S. wi 21 1, (c(())² 2 (1og log
Suppose that
Ds
+ + A. N and p S
(0))
Then, for the time step such that the following event happens E = {1 2 4((((6)) of + 6(((8))2 } and any J. E Fe-1. if we take = p², with probability at least - 8/TL,,
Var
( Bh 6 6( (8)()))))22
(Eeeyo 03/w3)²
+ 56'(6)p² + Au.2) ))
[.(..) Be(f. 84 S S (2((,
1
1
2
+ Varr
3
Vare
(1 (1:1 fr-1 (2;))² iE(t)
+ (5) + c2)) +33,, + 2682, and Au, = O(1yv0t2 (1) + 13 0,26571 ). Viar = (4(20) n + co + 13 + 16p² 12)
where Var, = ICatoning Sar
Proof. At each time step t E [T], for two fixed f, f E Ft-1, we first compute the expectation of Zi(f, f') as
f²(f.f")
- ((())()) ((xx))
1
Additionally, we deduce that
(f(x.)) - fxxx)))
1f(x)) - 2z)))
(f(xi) - f(((1))2 +1)
<
sup
wi
E. Eieli- (xz) ((()))2/ +
|E|--1]
D3
(f(zi) - (1-1((1)))
(f(z)) (2)())))) + +
2
Σ
+2 2
Σ
7
w/f
w/
|E(t-1]
ZE(C-1] 1]
2 32 <4p² Pi-1
where the first inequality uses f, E F C Fi-1, the second inequality uses the definition of D, and the Cauchy-Schwarz inequality, and the last inequality follows from Di/w; S p and f E Fi-1. Thus, we bound the sum of variance by
Σ EE(t]
Var VarlZ
Σ E
1
(f(x;) - I' (x::)) - -1) x6
iE[c]
(f(x))
f2)))))
of
w
w?
iE({]
<4p2
o
w
xE(t)
Similarly, we can bound the sum of μ by
Σ E
J - ((=))))-(
*E[:]
(f'))) - (x,)))
(Vi(f, max iE|!
D2
max SVi(f.f')
Σ (f(()) - ((x)))
EE|!
|E[t-1]
SV.(F.f'
22

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
We also get the upper and lower bound of O((f.)):
((6)
('(6) = A.
0e(f.f)
S
VPBBB_I(Vare + vlf.f)) + è
Besides, by using Claim A.14 from Wagenmaker et al. (2022), we know that
Catonig ( fz=1 )EEA
S max 2 (y: f((x,))² #Elt, w;
s max (2n + (f(())) sE((]
- f((x)))))
2R + -413.
which indicates the lower bound of (,(J,f')
((6)
= a
(1(21+881)) 8L3) + (2) +,) 434, 22 p
Hence, given choice of = p², we have
48R(1 2AR))2
log
(8/N2TL) log(A/a)
min(1,
T4
(1)
A 2
< log
(P5/N2TL
14ARTT2
25//NTT ((T(2R² + 813) + (2) + (.) + 43A, + 26882) 0*) rt))
< log
< (
where the last inequality holds since
(d()))² 6(10g + A. + +N)NTT/55 B..))
Thus, since the following condition holds for time step
& t t2 2()( E 6(((8))2
Vare
we have
Σ Eielti d + +V(.ff") wa
t 2 4(((()))
+ +2log
48R(1 2AR)2²
(8/NPTL) log(A/a))
Var, V.(S.''
min(1,a)e2 ((((())))3((/N2TT
by combining the results above and using Lemma 3.2 with p² and the choice of (e ('), we have with probability at
23

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
least 1 L.
|Catonia, (Catooii..u.rr (.,,,,(((((((()
Σ (1(m))) - (x)))))))))) ((:i)
iE(t) i
Varl Varl (.(, f(] + Σ ((()f))) + 4(((6))
$ f'(
Σ
fl( +p²
VE[U
iE|9
(())
32
Σ
+ v.l...))
1 (Var, + V(( +
Wi
se|t]
+4((6)) 12.9_1 (Var, + Vo(f,f') +
Eien of/u?
< 40)
V Vara+ 2V VV((())) +4'(00)p²+ +2
V Vare
(Zieg) of/ of/w3)²
< B2
12 1-1 + 48((())))g
+ Var. + +VV((S,))
+5c((0)p²
Vara
(Eiego (aag)///ug o?/w?)²
$ V'(f.f'++ + 2 + (8)()))) 12
1
Var
+ +5)'
(16)
Var,
where the fourth inequality uses the Cauchy-Schie Sehwwr-Schwarz incquality and = O(1), and the last inequality holds due to the condition that p S 1/16)3/(6))
Then, for any f. E Fr-1, there exist two Jus S' Fu such that fulloo S v. 11 follo S v. Similar Lemma B.3, have
Catonig (() ((Z(Jur (e))))
S (= + 90L 0.25 = A
Additionally, we get
- -
Σ [.(([(x;;) - -1) (.,(((())))) y:) (.((((()))) - + (x((((( yx)
1E
10T.
Thus, by using (16) with union bound over for f' For we have with probability at least 8/TL.
((f.f') Re(s,f))
(' L,ffur f() + L.fo..)) R. f.) + Re(fo.f.) -R)(
< I.lJo, Rr(Sns 12) 2uL + +AA.,
(Eregg) of u?/w²??
$ (VC,,)) 0/ (8('()))3
+ Vare + +5(()))p + A..2
Var.
1 ((f.f' st.
4
where we define A 24 TA the last inequality holds due to the definition of 3r.
24

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Lemma C.3. Under the conditions of Lemma 4.4, assume that I Fi-1, and the estimator Sa is
= argmin max L(f.f))== ((())) + 2tCatoni a. (11 beea))
fEFi-1 Me5--1
iE(!!
Then, for the time step such that the following event happens
of wi Every 6((()))
&
12 4()(6)))
Vare
and all 1 E [L], if we take c = 2-21, with probability at least - 6/TL,
(zx) - fc(x)))
1 +X S
2 0/-1 + (8)()))))
(Zielg o7/ mw/p)
+ Vare
+56(0)) + +A022) +} B8.
w
Var,
Proof. Let Li(f)= maxp'FF f') and
(Eregy o?/
1 2 _ + 6 (8(())))
(81)²
+ Vara
+ 50((8)²² + Au22
Vare
Thus, by invoking Lemma 4.4 with taking minimum over f' E Ft-1 on the both sides of the inequality and f = fis we have with probability at least - 8
{ (a(fer)) - 1) [189
Le(fe)
max J-
(Vo(fe.))) - Vols, - - }
1
2 max f'Eli-1
{
3
(f((x)) (xx) (x;))) 2 -) (88}}
max
f'Et-11
2 iE(t
w/?
2 vo(ler
1 3 (8))
3
where we take f' f + f..
Additionally, by using Lemma 3.5 with taking minimum over f' E F on the both sides of the inequality and f f", we have with probability at least 8
Ie(F*) < max f'EF--1
{R((f, + Vi("", (1)
+ -)))))(0)))))))))) (8)8} 2
{
-Vi'f 1
/ Vi(("'
(898)
max f'EF-11
(B1),
where we take f ft.
Since ft = argmin (f),, we have
0 In(ft) 1((22 2
Vi((i,, (87)
2
3
which means that
+\==
Σ
1 (f((z))) - 2*(x)))
+ +r (8)) + ===
= 3..
o?
EE[!]
25

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Part II: Event Eht holds with high probability. In this part, focus on the relationship between the sum of true variance Evegy of/wž and the estimation Var, conditioned on Eoonv- Recall that we define the events E and conny in (15). First, we will show that event a conditioned on Etory holds with high probability.
First of all, we provide lemma for the v-cover.
Lemma C.4. For any f E F, there exist fo E Fe such that llf - fulloo S U. Then, we have
(1 ((x:))) :E(1)
(1 (V= su((z))) (E(11)
Catonior
Catonig
I 4( + 2L,) + +2
2/ (R +++22 ++22))u.
Proof. We have
1
(v/ - f(x;)) $ +8L7
and
(yi
fxx;))
1
(vi - fo(x:))
- ( f(x:)) f(x)) fo(x,))
w?
w
S uu( 44,)).
From the definitions Vare we get
Par (2(36T, cy + 20 + +6) S $1/6
Combining the two inequalities above, we have
1
Σ
(v: f(x;))²
(vi fo()))) wp
1
w?
s - u(R + 4Lg).
Then, by invoking Lemma E.2 with A = - 411) and taking p², deduce that
Catoning (12x(S, (') Catonie.(s..ff)) (LZ: be)))
+ 20 Var 2R + +877
22R + 4T,f)
<
.u(2 + 44)) +
(orr))
< 44R+ ((R+2L,)) 2 (R+ 2Ly)v.
Lemma C.5. Under the same condition as Lemma 4.4, and assuming that f E Fi-1 we use the Catoni estimator
((u f(-1(2,))2 sEg0
Vare(f)) = :Catoniog
where &yar (12(20? e + L3 + 16p² 1)-1)) and suppose that p I 1/(1076c(()) and B2 S 4320(c'(6)) E wa + 16 x 5660(/ (())))22((00)) + cg) + 120) + 264, + 4X, where Du is desined in Ta-
ble 3.
Then, for the time step such that the following event happens
Eveld w
& t 4(((
6(c(
Var,
26

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
we have with probability 1 26/TL
t
of
(fi
- 2 i=1
I
(6) + +G) + 43A. + 268A.
wi
where A. O(LFUT? + +,,112 + L 1233
LDL + VRLjUT).
Proof. For a fixed f E F, let
1 (yi f(x:))² 7 W
vi(S)
(of + (("(z)) s(xx)) + -(x())))(((
- f(x)))
=
We know that
[V(()) S R² + +882+ +202==0 R'
We can calculate the conditional mean of Z;:
mi(s) = -/ + (f(t))
1
and the sum of variance of Z,:
Σ Var[Vi([)]=
1
E [11 - o,) + 4n2 - [cx)))
W
0, (cn + +4(f"(x)) - f(x)))))
w
0,
(cn + 16p2. 1811),
where the second inequality holds since
? (f:)))) - f(xs)))
f(xz)) wi 1.f' Ekels-1l 1/4 (f(xs) ((x))) +x
(Σ
1
(f(xz) - (=xx))+++ +1)
sup
kE|l-1J ok
2p² 2 Σ
(f(z)) fz-( +2 kE|i-|]
Σ
L -
kE(r-1]
<4p²
(17)
where the second inequality uses the Cauchy-Schward inequality, and the last inequality uses the definition of F,-1. Then, we have
Σ (0
Σ (o + (f) f(x:))))
2 m
1=1
(x,)) - f(x))) KE(1]
+ VV(f, f*) max
wi
wp
VV((ff') 4p² B/-1.
1
where the first inequality uses the Cauchy-Schwarz innuuuua inequality, the last inequality holds due to Assumption 4.1 1.1 and (17).
27

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Then, since from Var (12(20 + cq + +1 16p2. ()--1))
-1
we have
Σ
Var[V[([] + 2(m=-i)
1=1
(20 cn 16pp) + V+((fff*) . of
S )
of
i=1
s (0 (ll7) 2 + on + 16p² + 1. ...3. 4p')
t
by the choice of (0) and the condition &, holds, we get
5t 6
(0 )
VarlV[(f)] + Σ (M (m==)))) 2 log (oTTL.).
==1
Therefore, we can apply Lemma 1 and with union bound over the covering set of Ft-1, which is denoted as F, to obtain with probability at least - 5/TLL L. for any ʃ E Fe-1.v
1 Σe Ee(()) + 1og(NTL/0)
Var((f) - mi(f) SPlir
Σ
Varl VarlV[(f)++
Ovr
1=1
2
+2 2 Log(NTL/0)
5Ovar
(20g) + Gn + 16p² + V.(J. 10-
(18)
Ovar
Then, for the estimator fi-1, there exists fu E Fi-1, such that 1 folloo S S. By invoking Lemma C.4, we have
(1= - f2-1( /EE0
(1 ( fo(x.))²
Catoniog
Catonio
SEj
s 4(R+ + 21,)) 2 + 2 (R+ (R+2T.,))s
Also, we can get
-m(fe-)) - m.(fo) S4LyOT.
Combining the results above and by the choice of Par we obtain that with probability at least 8,
Vare(fr-1)
Σ milfi-i)l
$ (arc(fe)
Σ
(T,6)))++++++++,,+00222 (R + uT
1=1
< Ovar
Σ
(20 + + + 16p) + VV((Ju, -V
+ 2 1(0)
+ A
Oi
1=1
+ 2 1'(8)
(20gg + on + 16 + (Vi(f--,,)')+ 4p2
+ Ae.3
Olver
where 4v,3 = 4(R + 2LT + 2/ (R + 2oy + +4LgUl. Further, we have
1 of Σ
Σ (i((fi-))
vi(fe-1,''),
w?
1=1
28

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
and
-f)))))))))))))))))))))))))))())
(x))))
vi(fe-1,f)) Σ
+
w/
wi
KE|t-1]
D.
5 +
w
<(1 + p²) ))
where the first inequality uses the definition of Dj and f Fi-1. Combining the results above and the value of Var (12(20) + Ci + 16p² ()))) leads to
Varr(fi) Σ
1
of
+ 2 ((0)
S Var
Σ
2 n
+ oq
+ + + (4 402
+ + + (1+ 0²)
w
Ovar
1
p²
9 +
TTTUT + (8)) + 64p + A,,3 3 + (1 + 12)
16
1=1
$
-
2
+ 67 (320(L((8))
+ 16 x 5660 (6)) + +,,) - 120x'6))p² + 26 v,2 + 42
4 1m1
L + A
2
of
+ 67 16 x 5660( (20 + c,) + 264.. + +42) + (2)()) + t.) - Au
$
2 =1
ii
s 2 < + 14) + c,) + 43A, + 268A,
where the second inequality uses p S 1, and the third inequality uses the value of B7_,, the last second inequalities holds since we know from p S 1/(1076c' (d)) that 67 4320(.' (6))) < 1/4, and the last inequality also holds due to
67 x 4 x 12 ( < 2, and we define A, 67 x 26A.. A. + & L.y (I, + I.J R2 (.8))005577333 + R. 0.25 + 1 OT + /RLyuT), which concludes the proof. There is fixable error. Now, change the plug-in in Var, from f. fi and change the analysis above, so now the upper and lower bound is reasonable.
Lemma C.6 (Formal version of Lemma 4.5). Recall the definition of the variance estimation (6):
Var, Var, 1 + 14'( c2) 434, + 268 where Var = (4(20t + Cqj + 1, + 2 + R3 1.2 + / RT) Then, conditioned on Eo when 2 2 1076i' (8) we have with probability at least 28 for all 12 14()
2144, 2- 1) and A. = O(L (A) + 1., +
Σ S Var, 3
Σ 2(144 +,, 43A, + 2682')
2
2
New!
NeW!
which implies that (1 Sta, holds.
Proof of Lemma 4.5. If we suppose that &, happens, since Et holds true, we can apply Lemma C.5 to each / e [L] satisfying that 2' > 1076:'(6) with p = 2 and obtain with probability 1 1-25,
Σ of
Var(()) (fi)
14c(())(20) + c.) + 434, -288
29

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
which indicates the desired result according to the definition of Var,-
Furthermore, we show that when t 2 14()'(6)) & holds true.
t ]4((()))==4(((0)>>>>> (()( of (())) Eient wi
+ 6(((6)))
Var,
o 2 Var..
where the second inequality uses Dievi
mi
Part III: Sharpness of the confidence set
Lemma C.7. Conditioned on Emr. if we take u = -=01///(((66)7))) c c 22- and take the confidence parameter as
(8):
(8)) = 28)) + 60c' 21 + 12 + 22
where A, = = ( + 133 L LI + RRL We have
+
(B))² < (320(((())))) 21
16 x 5660 2 226) + c,) 1202(()) 26A, + 4
ie w
Additionally, with probability at least 1 8. the following event occurs:
(10 {f E Fl, for I E [L], 2 2 10)
Proof. By invoking Lemma C.3 for with p 2-1, get with probability at least 1 8,
(f*)))) - (2.)))
+
( ( of/w???
(Eievy
$ 2 12 + 6( 48(((6)))2221
+ Var,) + 55((8)2 + +0022) + X.
(19)
Varg
Then, since Corollary C.6 implies that with probability at least - 28,
Σ
Var,
3
Σ
of + +2((141(6)(202 cr) + 434, + 2682')
(20)
2
NEW!
iev!
we get with probability at least
25,
Eiery of 0?/ww?)²
Var, S 5aa
Var,
Hence, we deduce that
(f+(z)))
-((a))) (2))))
+ +
m/
iEv!
1 (B/_1)² +6 0 (8(('(6))22-2155))))) 5c( 21 + +Au.2 X
< 2
< 2
(B )² + 1440(((6))22 Var,
2 + 30c + 66o.+t
< (8))
30

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
where the last inequality the definition of //. Moreover, define
B 16
cy) 12)2 21 + 264. + +4X,
and deduce from (20) that
2 -2)===280((())))² Var, 606 60)2 v, + 2X
(4320
5660( (6)) (00)))222144000))))) + +,) 432, + 2681 600((8)2 122 n.2 + 2X
<4320(((0))²² 21
B3
+
BB
2
2
2
KEV
-4320( 2/
16 x
+ c2) + 1202(6))2 21 + 264. +4x,
2
KE
where the last inequality holds since 2 (6).
Part IV: Bounding the regret conditioning on good events.
Recall the notation for the eluder coefficient for each layer
((())))(x)))
D{(+)=
sup S ViEw, Jef
+
Lemma C.8. Let 1, = [logg (1076'((0)) Under Assumption 4.1 and Algorithm 2. if (yy Etony happens, then, for all E [r, L}. & E V/y, and Xū argmax (1x E X1, and the regret at the 1-th level is bounded by
Σ
(f* - (*x))) 2-3 34 1
N NEW (44(0))))))))
Proof of Lemma 4.6. First according to Algorithm 2, we will prove that for all t e w/r, X3 E Xj by induction from l, to I where is the level from which ie arises, and note that Algorithm starts from level 4.
(B = o (V(6))22 21 Σ
of/wt +1'()))))22 (o 10+++ cn) A
iE
Assume that Xj E x for some in E [|,,1-1] and 2/0 exists. Since voo+1 exists only if D/ (x) 2- for all x//0
Then, denote X/a argmax zex2o fla (z) and deduce that
( fo (2))) 25 (zi) (x - |/m -f - (2 -
2 D.o (x )BL Dlo (x) 16
2 1o B1_11
where the second inequality uses X; argmax f*(,,, and the last inequality holds by using DIo (x;) S
2 2-1,, (2*")) < 2-b, Therefore, from the definition of x = {x E x plo fl))(x) 2 max 2 2- 3/ obtain that Xi xlo+1 Hence, via induction, prove that X; X
plo (2)(2)
Next, for the lo + 1 < since X;, X₁ E XY we know that
(21)
31

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
and
(xt) $2 (aa) (2)))22)) 2-1111
(22)
Thus, we derive that
(M(x)) f
- + - $2 142 +
- + ((xxs) - (x))
52 122 2-
1+1 2
1--
-2 1-
which implies that
Σ ( - Σ
2 2-13 13- B1-1
AE (2
1E
$2 143 3/- 11'r
Now, we provide the proof for the main theorem.
Proof of Theorem 4.2. Recall the definition of two good events
s 2Vr,, for E [L], 2' 1076 }
gt var
iEW!
{s E Fl, for I E [L), 2' 2 1076/(())
conv
By invoking Lemma C.7 and C.6, have
PP (C n E 2 1 -38.
In the remaining proof, we suppose that (1e n Etrr holds. Let I, be the minimum / [L] such that (c)()))², (c(((()) 48 (())).
2 2 m1x
We can decompose the regret into three parts
L Σ (()(()))()))))
R Σ Σ (f*( (*()))
+
Σ (((x))--'0
LEW,
where we use the short notation
X; = argmax ZER, I (x)) For the term J, we have
J 1.,
(D) (2:))
,21,L,2211
wi
TEWT.
2L 1.d.2,,,+immm,... (F) = Ö(L, log(N) dimi, (F)),
where the second inequality holds due 2 D.. (xz)/w we from Algorithm 2, and the last inequality follows from the fact that 2/. ((T))((()))))
32

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
For the term 1g, invoke Lemma 4.6 get
min {I, (D((2,))
12 x
Σ
3/2 ++3
I 8 Σ
3/2
2 Σ
w
12,+1
124
cEVT,
<84s
12
log N. dimi,r(F) + L, (log N)33/ dim (F)( + on) oni)
=
L1,
Σ (E[T]
of
where
the last
inequality
holds
since
we
know
from
Lemma
C.7
that
(6())
log (o Gy
A, + 2)NTT/8)
and
- 0 ((6))=- (16))
Σ
of/ + (1(6))8/22- + /Gr) + VA.)
For the term 13, we have
Σ
(tr) (
(E(T) 1
Σ
(E(T)) 4
=ō TO
T T,,
where the first inequality follows from the peeling rule that (zf( S for E (T] UiE V/, and the second inequality
uses the upper bound of 3/ and the y = T//2.
Combining all three terms leads us to the eventual result.
D. Another Algorithm: Construct Two Confidence Sets
In this section, we develop a substitution for the Catoni estimator by constructing another candidate set and picking one estimator out of the set instead of solving min-max optimization as (3). Additionally, for simplicity, we consider the finite function space F with cardinality in this section. By standard analysis for the union bound over the cover set, we extend the analysis to infinite function space with finite covering number in Appendix B.2 and C.I.
D.1. Known Variance
Notations. Recall the probability parameter follows:
8 +
8n,t = N(T + 1)"
6t Σ
8n11
(23)
nE(N
Note again we have EnE(N],eTT 8n, EierZy 8, S 6.
We also define the following logarithmic factor throughout the analysis that
/21 288 L3,
96R(1 + 22/e)22 min a2 22)
c
(6n,t)
log
log
dn
where for the last inequality we choose a = 1/VT, = and use the assumption that 2 Lg 2 1 without loss of generality.
33

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Algorithm 3 Catoni-OFUL with Candidate Set
Input: Parameter on and 3t for each t [T].
for 1=1,2....,T do
Pick action according to max f(z);
Observe the reward l/r
Let the weight oN max a, 4 2 11(2821-11,01-11))
Construct F, as defined (24) and pick any fe E F6;
Construct confidence set
F Fx:= (== JEF.
Σ iE|
(Maz)) {
S sBp..
end for
Suppose that for each E [T', the upper bound of the noise variance of is known. We now consider the following VOFUL algorithm tailored to this nonlinear function class setup. After specifying parameters dng and Be for E [7], and the weight
a, o. max a, 20 1110:
depending the variance and eluder coefficient Dy, we define the candidate set for the estimator
A { iEF
Σ -(w.)) + 21 Catoni (1.)) ,.))
1 33
min FEF SEid
(24)
where ZiJ,f) (1(oa))
f(x,)) y:) and
(8n.)
0,0,
Eieto Jे ((xx))((xr)) + Eiejo t. (s(z)) - ((x))) +
This candidate set selects robust estimations for the true function S*, and we will prove in the sequel that the f* belongs to F, Then, we choose any function fi from F; and further construct the confidence set F, with a small weighted square error. We will demonstrate that f E Ft. Based on the principle of optimism in the face of uncertainty, we choose the greedy function Jr Fe and the greedy action X, E Dr.
Theorem D.1. Under Algorithm with the parameter Sn,t = 5/N +1, (6n,t) = Vl0g (V21 288 12 /8m.)) and
8. (s((.. ((8(8.13* + 2. 13)) 1/2
+ +13V2x7/0 (BV22)/()(6mm.))
(25)
with probability
28, we can bound the regret by
Rr R-= = =Ō( log N dim T (F) + Lg
Σ of
1/2
/ii 1 vr
(F) -logg.
1E(M]
We now divide the argument into the following three parts. In the analysis, we omit (f.f') Z, and when there is no confusion.
Part I: With high probability 1 - 8, all the sets F, are non-empty for each i [Ō(I),
Lemma D.2. For any iteration t [T] 7 (6,,r) and the set F. constructed in (24), have with probability
least 1 8, O2e #
34

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Proof. It suffices show that for each I, have P( $ Fi) < òG. When S & Fr, there exists some f F such that
Σ E ( + 21- Catonia i
(M)))) (a.)) (f*
v):) kE(A)
1-77 (
which implies that
t Catonio
(1 (f*()))
(M(x))
-vi)
7
Die(d क7 (f) (xx)))
(E(())
2
Now we bound the probability that the above inequality happens. We use the notation for any f.f F
1 o; (f(x)) - (f((a)) yi), Z(f
which is short-notated as Zi when no confusion arises.
We apply Lemma E.1 to 2("","" The variable Z, has conditional mean 14, R.7 0, and sum of conditional variance
ΣE ( ((a)) (f:)) y1)
0,
iE({)
$ Σ o?
(x - (x:)))
kE[t]
v(f",f")
where the inequality uses the fact that E (f:(x;) y:)² = ou s oî. We can also bound by definition E [a, A] where
A i(ōne,a)ee and a 1(6m.11) /201 + e²
Thus, we have log
[88R(1+2AM)) min(L,a)e"6... 8n.. log(A/a)) < <312(6n.e.) given choice of 1/VT and 1, and thus for any iteration
(48R(1 + 2AR)
t 2 762 (6n...)) 2
+ (( 2 ( (8n.t.)) - 2og
min(1,a)e?5... log(A/a))
by choice of
" +iett 3 (ax) with probability least 1- Sn we have from
13 (6m())
V
Eiejo 2 ((()))))-aa)))
35

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Lemma 3.2 that
t. ((2tooio((Zz))ee))
V + Eiely (14 - -
s (1)
V + EiEmh (S((z)) - (xx))))++ + (2((6n)
(v
(
V+ + Σ
( 0,
iE(!)
+
(0)
V. (1+ iE|t o
max 2 ( ((6n,t.)) + 12((Ome,)e+6 +6
13/
41g D=(1:11-1100(-1)
13
V.
1+ max sElt] o?
Σ
(f((z)) ( +
kE|i-1] ok
(18)
x 13((om.ti)))
1+ VT
V +
13
33/4 (2² 1/4
2/2
(166) V
VÀ
V
+ 169
1 8
(6m,ar))
+ 13 13
4
(iw) 1. + Eielo
1 (f:) - (xx))
o?
2
18R(1+2AR) log(A/a)) S 362(6n:))); where we use (o) that va+b & Va + Vb. and the inequality that log min(La))
(i) the range assumption that |s()) I Iy.. choice of e = and definition of Da: (ii) the choice of oī 2 , D, -i- 1): oü -1)1))((n...))) and Va+b S Va + Vb, (iii) triangle inequality that Vab S + o where we let V, 169/ 2 (8), 2 and similarly 2/4/1//4 < ah c'b where we let V. (6n..)). and 13v2: and finally (iv) the definition of 3 in (25) so that 88 2 (13+ + 133) (6n,..) + (L
This implies that
Σ 05
+ 2t Catonig
(1z (())))(()))) - v.)
<
-- 32 4
1
I 8nn.
iELO
sE(t)
Thus taking a union bound on all / e and E [7),4 (2,,TT)) we can conclude that with probability at least 1 1-5 5 (where 8 = -nn[MMee(T 6n,z) for all iteration (6,,T) S t < T,, one has f e F, i.. (2 + 0.
Part II: With high probability 1, 6, F, for for all e [Ō.)). We first provide the following lemma.
Lemma D.3. For any function f F, let 2, = ,े (f) - (=))))) (f" (zx) y1) and 0 as defined in (24), we have
for any t 2 7 (5n.r) with probabiliyy 5n,t
B
t. Catonia (Zz, Z,) + Σ
<
Σ
(f(x)))-
sEId
Proof. In order to apply the concentration inequality in Lemma E.1, we first bound the following
Σ
[(Z, - u4) [
1
- ((x.))
$c(d)
E (t)
36

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
and further
Σ RE|O
Σ(m-
(14 1 -
1
Σ (M)))) S
Σ iE|!
2 (f(x)) - (x)))))
iE[(]
iE((]
Now by choice of 0-
V Eieta *े (f Eier ((())))))))) we will have with probability 1 - 8n,t, for
(66nt..))
any 2 (Ōn,T),) it holds that
t. Catonio (itonio((Zi)een) (Zi))e(0))
Σ iE(1]
(M))
Σ
(((a)) (1+ max 1E|1]
2 (f+(x:)) (f-(:)) ((bmss)) + 13((ōn,.)).
< 13
[E(
We now proceed to bound max 3 ( (xx))) we assume (50))) S 2 for any x E X, consequently we have
max 2 (f" - f*(x,))² S max [E 0
4hg (f())))'(==))))3
V ((=( f=,,)))
tE
o,
4hg (1
Σ
(M((x)) - (ax))) + A
max
E
oe
OR
kE(M
Σ
+
81(6m.e.)
RE/A
Σ
क (((x)))((M))) + 8
86(6m.e.))
REjA
where for the last inequality we use the fact that of 2 ( (111 )--1) by the choice of o.
Plugging this back we can conclude that
t. Catonig ((Z))ee)) +
Σ
(aa)))
13e(6n.t.))
iE({)
3/4
< 13
1+
VA
Σ
1 ( ((dmest)
13
Σ
(m(z))
((a)))
(P(6m 1/1
2v
iE'!!
(E
1 Σ
vA
1 Σ
(f)) (xx))) +2. 132 (6mm))) (1
1+
f(:)) + 13t (6m.())))))
8
8
EE/
= L. Catonio((24)seu) + + NE
( (f(
1
(M(x))
1
8
sEld
where for the last inequality we use the definition of 3, so that 33 > 8(8 13 13 + +2- 132 v Xu² (bm,t.)) This concludes the proof of lemma.
Corollary D.4. With high probability 1 - 5 where 8 = EmEEMMEE Sn,, we have f E Fo all E ( - 1] satisfying t 1 (B.
37

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Proof. We bound the probability by union bound argument. Let T == {1 [T 1] : 12 7 (6,,))) and 2 07 (f((x,) - (z.)) (xa) Vi), we have
P
FF) E P
ft ft= Σ
1 ( > Bt
nE[N
E E (f*(z:) - 1" (x:))) )² + 21
Catonia
(1Z))1e0)
2 -9
Σ nE[N],ET
P
Σ 3 (f"(x)) - (",)))) 89
Σ Eier de (f*(x)) - ('(x))) s 1 + 2t
Catonio (1Zi)1e1s)
+ : Eien de (f'(x))) - 8rh ( (x:1)) )
E nE(N],EE
P
Σ o (f*(z;) - ("xx))) > 3
Σ NE(NT,EET
P
t
Catonia (iZihee)) 7 Σ 1 (f*(z;) (a,)))
1 -
4 xc(1]
iE(1)
Σ
6at S
5n,t S 6.
nE NETNTI
nE(N)
Part III: Bounding the regret conditioning on good events. We now recall the definition that T = (1 E [T] 12
7 (f,,T)), we further denote the good events & = f( + }} and E' = [f" E Ft).
Proof of Theorem D.I. Conditioning on both good events & E',, we let f be the function maximizer in set Fi-1 we pick step and can bound the regret by
Rr Σn= rr=
Σ
- -f S 2L,
(7,,)) +2) + E (fr) fx()))
17/7
BETT
tITET
x 2I (Bn.T) +2) + Σ ( (zxe) + ( - Maxi)
-
I-IET
(v
$ -0(1)-2(0nn1)) + Σ
(
Σ
1
(
+ A
og
t-TET
kElt-11
(F(z) - 1z)( 2
Σ (E(t-1]
+1
oz
< (Lg + Σ
(VBRi+))
-IET
where we use (1) the definition of Da for each t E [T] and (ii) the definition of Fi-1 and that f"r f E Fi-1 conditioning on E and E'.
Combining this with the range bound that [0, 1] of each individual reward one may receive by assumption, one can conclude that
Ri (L, (2(6.))) + 2L,
Σ min (,,,D)(en J. - 11) /BB 1 IIT
(26)
To finally bound the regret, we bound the second term in RHS of Ry expression in (26) respectively. These steps
mainly follow Lemma 4.4 in (Zhou & Gu, 2022). We can decompose the terms by considering In = {t - e
T DT,,, og Fh- 1), (1) 2 1) and In = {t - 1 T
38

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
For the first set, bound its size naively by
Zi S Σ
min (1, D2, oz; ([=])111)+ o(-11)) S dim (F).
BEI,
For the second set, bound the summation of terms of interest contraining on I2 by
Σ v.v P +
tE22
Σ
/i B +X (2 01: (p-1)
5
1EIg,0:=of ara
Σ
σ.v 3 +
1E = 2122m00mmm))))// (2( p (1:1-11))))))11))
(
(o, aa) V 8 + Dx(1,, oi ((-11) + Σ 32L 32L,c(6nne.)) 83_ + x D3 [1) F/-11)
LE(T]
LE[T]
( [-1 + \) + a dima,r + 16L max v B + X d 1E|2]
TE(T]
Here for (i) we use the condition for each distinct set and for (ii) we use Cauchy-Schwarz inequality for the first term and the definition of dim, for both terms.
Consequently plugging these back in (26) and take supremum over x |a| we conclude that with probability least
1 1-26. 20,
Ry 0 (1, L, (66,T) + dim + Lg ((6ma,)) max
V B dima.T(F))
LE(T)
+I,s Σ
( (o? + a22) / ddima
1E|T]
= δ by h1
log N. dim + (F( + Ls
Σ of EE(T
/ /im 3 ((F) log
where for the last inequality we pick A =
D.2. Unknown Variance
We first choose the probability parameter as follows:
8 N(T + 1)L
5
8, :=
ΣV
5
(27)
T+1
[E
Note again we have Eterry 8c 8.
39

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Algorithm 4 Varionce-Agnostic Catoni Bandit with Candidate Set
1: Input: Parameter > 0, L = [loga(1 (1/7)), 4 [log2 (1076 (o))].
2: Initialize the estimators for all layers: X <- 2-21 36 +- 2-1+1, Va c- 0 for all / E [ T..
3: for t=I....,T
4: Observe X, and initialize X² + Xe 1 + 4.
5: while z2 is not specified do
6: (ax) S y for all E X then
7: Choose 2t, fi-1 < ,ea, (x)
8: Observe y/:-
9: Break.
else if (x) S 2- for all E X then
11: Update x²{1 - {a E X (x) 2 max (() - 2-1+1 1/
else
Choose 2, E X such that (x 2- and observe yee
14:
Update wy 2' (1)))
15:
Update the index sets: V + - {t) and v. + w for 1' f
Pick any 8t ft as (28), and choose the confidence set Ji defined (32).
end if
18:
Update 1 < 1
19:
end while
20: For 7 E [Z] s.t. V = V/_1. f1 + fL1 F. + Fl.
21:
end for
For each layer I E [L]. define Z; = (1(x;))) [fx:)) y:) and
1 (f(x.) - f(x:)) 2t Catoni (2. ,2) - (81)2
1
# = f f
min
(28)
feF Eiee!
w
(6m.))))
where O(
(29)
1 wy Eieoy
(f(x)) - M(ri)) Eiev; 2/ (1(z)) - -(aa)) +
and Catonia is the 0-robust mean estimator for Eiev #o2 (f(z))- - (f(zs) - ((s)) The confidence radius specified as
3 - (((()))) Var, + 2(6)2-21 + +x²)
(30)
where Var, should satisfy event End holds with high probability:
Var, Catonii oir (1 fl (x:)))
Stevs )eevs) 14( + cx) 268
(31)
Then, we can define the confidence set
F IEF: Σ iEV!
1 (((s)- A(xa))* (81)2 wp
(32)
The result provided in the following theorem, where the bound is basically the same as the one-confidence set case in Theorem 4.2.
40

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
Theorem D.5. Suppose that Assumption 4. holds. Under Algorithm 4 with 7 1/(L,T)/2), isT 14,2 14:2 (8n,T.)) with probability least 35, bound the regret by
Rr (L:
Σ AE(T]
of dim J (F) log N + Lg log N dim Ae rFF)
For the analysis, we now divide the argument into the following parts. For conciseness, we will omit the proofs similar to the previous analysis.
Lemma D.6. Under Assumption 4.1, given (Xi, ye, wi) wiee we define D Sups,'EF f
If
Dj S and Elarr = {Eie(4 mn? I 2ari) J holds true, then, for the time step t such that
suPie(t] wa
Exety 0?/wf wf
& = ((c((6.,t,1))
+ +((((6n)))))
Var
there exists some f fm E F such that with probability least 1 6.
1.3. - - wy
f(,))))((),)))
t. Catoni
w (f(a=)) f (
(( vc)
kE(t))
2
Proof. Now we bound the probability that the above inequality happens. We apply Lemma E. to
Z;
- ((:) y:).
which has conditional mean = 0, and sum of conditional variance bounded by
Var War[Z.(f.
Σ
(f(x;) (
yz) x
1E
(f(x)) - (x:)) of
w
w?
iE(c]
<4p²
8p² 37
Varg
sE[t]
Then, follow the proof steps of Lemma C.2, we can obtain that with probability least 1 -m,,, have from Corollary 3.2 that
t- ( (o)een)) < 2(0))2 + V.(SS))
2
Thus taking union bound on all f = f" F, conclude that with probability at least 1 8c,
[Catoni < 1(0))² V.(.J)
2
Lemma D.7. Conditioned on E.. for any iteration t E [T], satisfying &,, and any layer I E [L] and the set F. as constructed in (28), we have with probability at least 1 - 8, (eeeT) #
Proof. It suffices to show that for each and 1, we have PP & f!) s 8, When f & Fl. there exists some f ft E such that with probability least 1 1-8
1 (f(z,) (a,))) + 21- Catonia (1 (1 - (ax))) -w) iED! Σ Σ1 3 NEV!
< -11

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
which implies that
(1 ((a)- - m) SEV!
1(8)2 Eie ws
wa
1 (f(z,) (x,))
Catoni
2
Lemma D.6 implies that
- (((.)))(((x))) 2t Catonia (1 (f()) -Bi) kEjA
< <
P
Σ AE[O)
S Sn,t,
Thus taking union bound on all f = 1d E F and f [T], satisfying & we conclude that with probability at least 1 - (where 8 _EE(M)re dn,t,,) for all iteration 7c2 (ôn,TT)))) S t T, one has f E Fj,ie i.e. (ee11),2770660 r.), + 0. O
With probability at least 1 - 5, f E Fi for all t E [O(1) LE [L]. Corollary D.8. Suppose that Assumption 4.1 holds. With high probability where [LE(n) ón,t we have
Uke(T]=23((100))
{f" F1, for [L], 2 1076/'66)
Proof. Conditioned on gt. we can follow the proof for the known-variance setting and get
Ft.
For each [L], it remains to prove that Etdl holds true. Following similar analysis of Lemma C.6, we can show that conditioned on
(s" E F V [T], (7, (fn,T.)) -]]}
the event Et. holds with probability least 1 8.
Recall the value of 3/:
( =
+
V (6m.))))) 4
We can also demonstrate the relation between 3 and the sum of variance Σiew o in the following lemma via similar proofs with Lemma C.7.
Lemma D.9. Conditioned on Eu if we take the confidence parameter (8), We have
o²
(B) < (((())))
+ x²)
+
REV
Additionally, with probability at least 1 8, the following event occurs:
(ne := {f Fl, for [L], 2 (076''()))
Finally, following the proofs of Theorem D.1 and 4.2, obtain the result of Theorem D.5.
E. Auxiliary Proofs
E.1. Concentration Inequality for Catoni Estimator
Lemma E.1 (Concentration for Catoni estimator, cf. Lemma 13 (Wei et al., 2020)). Let Z₁ be random variable adapted
to filtration He, suppose [H pa Eiens IE (Z, 11)² 176-1] V for some fixed V. Let p == - Eiely p4: for
some fixed parameter 0 > O, we have for any 0 V + Eieng( -1)²) + log((10), with probability at least 25,
(v (V+ Eiejt) (mi -1)²)
log(1/))
-p
t
0t
42

---

Catoni Contextual Bandits are Robust to Heavy-tailed Rewards
We provide the following lemma used in proving Lemma 3.2
Lemma E.2 (Sensitivity of Catoni estimator, cf. Lemma A.13 of (Wagenmaker et al., 2022)). Consider some fixed
Z (Zi)e Z [Zi) satisfying [Z,| R. |2.] < for all i [t], and some fixed 0 > 0, 0 > Then, assuming that
Σ KE[A
012 2, + 3R0 - 0 s 18
m
=
will have
+ 2
2A
Catonio ((2:)et)))))))))) - Catonig -Catoni,((2 (12,)e())))))))
0 A+
02
Lemma E.3 (Formal version of Lemma 3.2). Let Ze be a random variable adapted to filtration He with uniform bound
IZel S R, H/ = p4 Eie IE (2, - n1)² | & V for some fixed V. Let j = Eiee p4. For any parameter
a, A] and given v 24R(1 + 2AR)?, i 2 02 + Eiegy - -m)) + 2 log( 48R(142AR) min(1,0)c*
(og(A/u)) with
probability at least 26,
0 0 E iElA] (4s (46- - =i)2)
400 6 Ot
Catonia ((2)))n()))))()))) i S
+
+
t
where
48R(1 + t
y 4log
min(1,a)e20 log log(A/a))
Proof of Lemma 3.2. For any 0, set
2² 22-uin(1aa)
1. we consider a A -0 (1= a (1 (1+x)) k)
21R(12A
[a, Al.j 2 0}, it is immediate to see |A| <
48R(1 2AR)) log(A/a) (A/a). Now for any 0 E A, we have by Lemma E.1 that with
min(1,a)c²
probability - 26/| we have for any 2 0 V Eiel( m1)²) + 2 2lo([AAl/))
0
(Hi- - R1))
2 log (og((A)188)
(Catoni(((Z)iee)) ((Z)) -il -
Thus by taking union bound over 0 A, we have with probability 1 - 28, for all 0 A, it holds that for any t t 8² (V++ Eveo (p= -))) + (llg((A)/)),,
Catonia((Zi)eer) - A 0 0(V @V Eieja (ps n)²) log (lA)(8))88)
0t
Thus, for any 0' E [a, A). we have there exists some 0 E A such that the above bound holds true and 0'-01 S S
min 2 24R
a-e² Now by triangle inequality we can conclude that for any A E [a, A].
Catonio p < |Catonia j7| |Catonia Catonia.
0u V E EvEry (Mi - xi)²)
2 llg((AA/5) 6
s
+
+ Aut
t
+ EiEjo (Mi: -p)))
log( (og((A)/8)
<
t
Ot.
where for the second inequality we use Lemma E.2.
43


Reviews:
[{"review_id": "HC14FlByNn", "reviewer": "Reviewer_24qD", "summary": "This paper introduces contextual bandit algorithms that are robust to heavy-tailed rewards by leveraging Catoni’s mean estimator from robust statistics. The authors propose two algorithms: Catoni-OFUL for the known-variance setting, and VACB, for the unknown-variance setting. Both algorithms achieve regret bounds that depend on the cumulative reward variance and scale only logarithmically with the reward range $R$, improving upon prior work that exhibits polynomial dependence on $R$. In the unknown-variance case, the authors avoid direct variance estimation by employing a peeling-based approach combined with a plug-in estimator derived from Catoni’s method. A matching lower bound is established in the known-variance setting, demonstrating the optimality of the leading-order term in the regret bound.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive suggestions!\n\n**Q1**: The challenges of solving the min-max optimization in Eq. (3) are acknowledged but not explored in depth. While Algorithm 3 is proposed as a more efficient alternative, the paper does not discuss its trade-offs in detail. For example, what are the theoretical or empirical pros and cons of this variant? Could a similar approach be extended to the unknown-variance setting?\n\n**A1**: Theoretically, the two algorithms have the same regret bound. Computationally, Algorithm 3 is more efficient since it picks one function from the constructed candidate set instead of solving a min-max optimization. Despite this advantage, we chose to present Algorithm 1 in the main text because it is simpler, clearer, and easier to explain, and its design is better aligned with OFUL-style algorithms which readers might find familiar.\n\nFor the extension to the unknown-variance case, Algorithm 3 can be extended to the unknown-variance case with similar techniques and obtain almost the same result. We will add the extension in the revision.\n\n**Q2**: There is no empirical evaluation in this paper. While acceptable for a theory-focused paper, a small experiment could have illustrated practical benefits of robustness. Nevertheless, the theoretical evaluation is comprehensive and grounded.\n\n**A2**: Our work primarily focuses on theoretical analysis, and serves as a first step to use the Catoni estimator for nonlinear function approximation. We provide rigorous proofs demonstrating that the weighted Catoni estimator is robust against heavy-tailed noise. Although the proposed theoretical algorithm is not computationally efficient, our analysis serves as a first step toward designing robust algorithms for general function class. We believe the Catoni estimator and the variance-aware weighting technique offer valuable insights for practical use. Developing an efficient, practical version of the algorithm is an important question for future work.\n\n**Q3**: In the linear reward setting with known variances, does Catoni-OFUL incur slightly worse regret compared to existing algorithms such as AdaOFUL (as shown in Row 2 of Table 1)? Could the authors clarify whether this is due to the generality of the function class or an artifact of the analysis?\n\n**A3**: The regret bounds match in the dominant term and are worse in $d$ for the non-dominant term. The reason for this difference is that the linear vector space allows a smaller variance-based weight for regression, with $d^{0.25}$ on the denominator according to Lemma B.1 and B.2 of Li, et. al. Their arguments do not generalize to the nonlinear structure, however, and we can only use $\\sqrt{\\log N\\cdot D_{F_{t-1}}}$ ($\\iota(\\delta)=\\Theta(\\sqrt{\\log N})$) in weights $\\bar \\sigma_t$ to balance the orders in Lemma B.2. The expense of using a larger weight is to get additional dependence on the non-dominating term (Lines 1013-1026). How to match this non-dominating term is an interesting direction for future work.\n\n**Q4**: Theorem 4.2 achieves a variance-dependent regret bound that matches the known-variance case (Theorem 3.4) up to a slightly worse dependence on the eluder dimension. Could the authors provide more insight into whether this additional dependence is intrinsic to the peeling-based approach, or whether it might be improved with a different algorithmic or analytical technique?\n\n**A4**:  This additional dependence comes from the peeling approach in general function approximation and also appears in [1,2]. The linear analysis for peeling in Zhao. et. al is restricted to the linear vector space structure and special form of uncertainty and thus can not be extended to nonlinear space. Hence, in our analysis Lines 332-337, we can only bound $\\frac{(f(x_i)-f'(x_i))^2}{w_i^2}$ by $2^{-2l}\\cdot\\beta_{t-1}^2$ thus leading to the worse order, while $\\|\\hat\\theta-\\theta_*\\|_{\\Sigma_t}$ is upper bounded by $2^{-2l}\\sum_i\\sigma_i^2/w_i^2$ without the additional order on d.\n\n\n[1] Pacchiano, A. Second order bounds for contextual\nbandits with function approximation, 2024.\n\n[2] Jia, Zeyu, et al. How Does Variance Shape the Regret in Contextual Bandits?. NeurIPS, 2024.", "claims_and_evidence": "Most of the claims are well-supported.\n1) Extensive comparisons (see Table 1) with existing algorithms highlight the advantages of the proposed methods in heavy-tailed reward settings.\n2) The concentration results for Catoni’s estimator are carefully stated and integrated into the analysis with appropriate rigor.\n3) The proof sketches and supporting lemmas provide a clear logical path from algorithm design to the stated regret bounds.\n\nOne minor concern: the challenges of solving the min-max optimization in Eq. (3) are acknowledged but not explored in depth. While Algorithm 3 is proposed as a more efficient alternative, the paper does not discuss its trade-offs in detail. For example, what are the theoretical or empirical pros and cons of this variant? Could a similar approach be extended to the unknown-variance setting?", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Overall, the proofs are technically sound based on the provided sketches and lemmas.\n\nFor the known-variance case:\nThe authors leverage a uniform concentration inequality (Lemma 3.2) for Catoni’s estimator. This result is a non-trivial extension of prior Catoni bounds and is central to constructing valid confidence sets.\n\nFor the unknown-variance case:\nThe authors show how to control variance-normalized excess loss without exact variances. Lemma 4.4 demonstrates that the plug-in estimator for the cumulative variance (based on Catoni’s method) remains accurate up to logarithmic factors. The authors then carefully control the contribution to regret from different uncertainty levels using a peeling argument.", "experimental_designs_or_analyses": "There is no empirical evaluation in this paper. While acceptable for a theory-focused paper, a small experiment could have illustrated practical benefits of robustness. Nevertheless, the theoretical evaluation is comprehensive and grounded.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "No major omissions.", "other_strengths_and_weaknesses": "Novel and principled use of Catoni estimator in a contextual bandit setting.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "1) In the linear reward setting with known variances, does Catoni-OFUL incur slightly worse regret compared to existing algorithms such as AdaOFUL (as shown in Row 2 of Table 1)? Could the authors clarify whether this is due to the generality of the function class or an artifact of the analysis?\n\n2) Theorem 4.2 achieves a variance-dependent regret bound that matches the known-variance case (Theorem 3.4) up to a slightly worse dependence on the eluder dimension. Could the authors provide more insight into whether this additional dependence is intrinsic to the peeling-based approach, or whether it might be improved with a different algorithmic or analytical technique?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3NGOSJktnd", "reviewer": "Reviewer_HA2Q", "summary": "In this work, the authors proposes a novel algorithm to tackle the contextual bandit problem in the presence of heavy-tailed noise assumptions. In particular, they assume that the variance of the noise is finite and deal with the scenario in which (i) the noise variance is known to the learner, improving existing literature bounds and (ii) the noise variance is unknown to the learner, obtaining nearly matching regret bounds.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your helpful advice!\n\n**Q1**: In heavy-tailed bandits, a dedicated sub-literature on adaptation to the unknown noise variance/1+epsilon moment exists [2,3,4]. I would be interested in knowing how this work relates to them: here, the focus is on the contextual scenario, but what happens if I cast these results to the unstructured MAB setting? Will they improve over the existing works?\n\n**A1**: We will cite [2,3,4] and include a discussion in the revised version. However, we want to highlight that our formulations and techniques differ significantly. Our work focuses on the contextual setting with general function approximation, whereas [2,3,4] consider the standard multi-armed bandit (MAB) setting. It is definitely possible to obtain sharper gap-dependent bounds in the MAB setting, but in the most general case, we can get $\\sigma\\sqrt{KT}$ bounds in the MAB literature, while one has $\\Omega(d\\sqrt{T})$ lower bounds even in the linear setting with large action spaces [1]. Consequently, the results are not directly comparable. We will add this discussion to the final version.\n\nRegarding algorithms, we adopt the OFUL framework combined with weighted Catoni estimators and peeling techniques. In contrast, [2] uses a skipping method based on Follow-the-Regularized-Leader, and [3,4] design adaptive algorithms capable of handling unknown $\\alpha$ and unknown moment bounds.\n\n**Q2**: there's a typo in Table 3, parameter $\\lambda^l$: prameter -> parameter.\n\n**A2**: Thanks for the correction. We will correct it in the revision.", "claims_and_evidence": "Yes, every claim is supported by a proof.", "methods_and_evaluation_criteria": "There is no experimental evaluation in the paper.", "theoretical_claims": "I went through some of the proofs. Each of them seems correct to me.", "experimental_designs_or_analyses": "There is no experimental evaluation in the paper.", "relation_to_broader_scientific_literature": "As the authors discuss, their results strictly improve the ones from previous literature, especially in the known variance scenario. Regarding the adaptation to variance, it is less clear what different assumptions were made by previous works. In this work, the authors make a reasonable fourth-moment assumption, which already exists in the bandit literature [1]. Moreover, in heavy-tailed bandits, a dedicated sub-literature on adaptation to the unknown noise variance/1+epsilon moment exists [2,3,4]. I would be interested in knowing how this work relates to them: here, the focus is on the contextual scenario, but what happens if I cast these results to the unstructured MAB setting? Will they improve over the existing works? \n\nReferences\n[1] LATTIMORE, Tor. A scale free algorithm for stochastic bandits with bounded kurtosis. Advances in Neural Information Processing Systems, 2017, 30.\n[2] HUANG, Jiatai; DAI, Yan; HUANG, Longbo. Adaptive best-of-both-worlds algorithm for heavy-tailed multi-armed bandits. In: international conference on machine learning. PMLR, 2022. p. 9173-9200.\n[3] GENALTI, Gianmarco, et al. $(ε, u) $-Adaptive Regret Minimization in Heavy-Tailed Bandits. In: The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024. p. 1882-1915.\n[4] CHEN, Yu, et al. uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs. arXiv preprint arXiv:2410.03284, 2024.", "essential_references_not_discussed": "All the essential and related literature on contextual MABs has been discussed. For some additional literature on adaptation to the noise variance in HT MABs see the previous box.", "other_strengths_and_weaknesses": "The paper is well-written, and the approach's strength is clear and provable. Authors make sure to compare with the existing literature and highlight the extent of their improvement. Moreover, the proofs seem correct.", "other_comments_or_suggestions": "there's a typo in Table 3, parameter $\\lambda^l$: prameter -> parameter.", "questions_for_authors": "I don't have any relevant question, except for the one already stated in the related works box.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7HrSCqFHro", "reviewer": "Reviewer_Cd7h", "summary": "This paper studied the setting of variance-aware contextual bandit (or second order bandit). Specifically, this paper aims to develop algorithms whose regret is upper bounded by the variance of noise. Suppose the noise is between $[-R, R]$, all previous literatures which also studied this question obtained regret bounds that have polynomial dependence on $R$. This paper adopts the Catoni estimator from the robust statistics literature, and develops an algorithm whose regret upper bound is only log dependent on $R$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive advice!\n\n**Q1**: The Jia, et. al. is also related to this paper. I suggest the authors provide a comparison to results therein.\n\n**A1**: We will cite their work and provide a comparison in the revision, and want to mention that Jia, et. al. is contemporary with our work. The main difference is that they assume that the noise is bounded such that $r_t\\in[0,1]$, and we consider heavy-tailed rewards. Besides, although we both get variance-dependent bounds, the focuses are distinct: they aim to obtain better regret bounds when the eluder dimension is larger than the number of actions, while we aim to obtain logarithmic dependence on the reward range. Regardless of the dependence on reward range, for the weak adversary with revealed variance, our upper bound $O(\\sqrt{\\Lambda\\cdot d_{elu} \\log N})$ is incomparable to theirs $O(\\sqrt{A\\Lambda \\log N} + d_{elu}\\log N)$. For the strong adversary, we both use the peeling technique and thus, our bound is superior on the dependence of reward range.\n\n**Q2**: The techniques used in this paper are not new. This paper is not the first paper that adopts the Catoni estimator in designing bandit algorithms.\n\n**A2**: Although the Catoni estimator has previously been applied in bandit problems, it has not yet been used with nonlinear function approximation, so we provide new methods and analysis.\n\nTo the best of our knowledge, our newly designed estimator in (3), which is based on excess risk, is the first one capable of handling heavy-tailed noise in a nonlinear function class. Other robust estimators, such as Huber regression and the median-of-means estimator (Lugosi and Mendelson, 2019), are limited to linear vector space structures.\n\nAdditionally, we introduce a novel analysis method to establish concentration results. Existing analyses for linear heavy-tailed bandits rely explicitly on linear structures and do not generalize to the nonlinear case considered here. Furthermore, for the unknown variance scenario, we employ a peeling technique, which allows our approach to avoid the need for approximating the noise variance using a function class.\n\n**Q3**: In the case where the variances are all known, the algorithm in the literature I referred above can achieve regret $\\sqrt{A*\\sum_{t=1}^T\\sigma_t^2*\\log|F|}+d_{elu}$. However, the setting therein requires the noise scale bounded by 1. Is it possible to improve your results so that the dominating term also scales with $\\sqrt{A*\\sum_{t=1}^T\\sigma_t^2*\\log|F|}$, while keeping the dependence on the scala of noise to be logarithmic?\n\n**A3**: That is an interesting question for future work. Currently, we develop algorithms based on the OFUL structure, while Jia et al. build on the SquareCB approach. It might be feasible to connect the concentration arguments in future work. We will add this discussion to the final version.\n\n**Q4**: In the current setup, the variance cannot depend on the action chosen. If the variance depends on the action chosen at each time step, will the results still work?\n\n**A4**:  We would like to claim that our regret bounds in both Theorem 3.4 and 4.2 depend on the variance $\\sigma_t$ of the chosen actions at each time step. $\\sigma_t$ is defined in Line 128 left and is the variance of the noise of chosen actions.\n\n**Typos**: We will correct them in the revision.\n\n**Suggestions**: Thanks for the suggestions. We will use a difference notation to avoid confusion.\n\n[1] Jia, Zeyu, et al. How Does Variance Shape the Regret in Contextual Bandits?. NeurIPS, 2024.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I checked the proofs for theoretical claims. All arguments seem to be correct, except from typos.", "experimental_designs_or_analyses": "No experiments in this paper.", "relation_to_broader_scientific_literature": "Previous literatures which studied the same problem all have regret bound polynomially depending on the noise scale, this paper developed an algorithm whose regret upper bound is only log dependent on the noise scale.", "essential_references_not_discussed": "The following reference is also related to this paper. I suggest the authors provide comparison to results therein.\n\n[1] Z Jia, J Qian, A Rakhlin, CY Wei \"How Does Variance Shape the Regret in Contextual Bandits?\"", "other_strengths_and_weaknesses": "Strength:\n1. The algorithm and analysis technique allows us to obtain a regret bound that only has logarithmic dependence on the noise scale. This provides a different perspective of variance-aware algorithms for contextual bandits.\n2. This paper is well-written, except for a few typos.\n\nWeakness:\n1. The techniques used in this paper are not new. This paper is not the first paper that adopts the Catoni estimator in designing bandit algorithms.", "other_comments_or_suggestions": "Typos:\n1. Line 272, in the left: $\\mathbb{E}[Z_i|x_i]$ to $\\mathbb{E}[Z_i(f, f')|x_i]$\n2. Line 754, right hand side: $E[\\frac{1}{\\bar{\\sigma}_i^2}...]$ to $E[\\frac{1}{\\bar{\\sigma}_i^4}...]$\n3. In the description of Lemma 3.6 (also Lemma B.5 and the proof therein): the minimizer $f'$ to the maximize $f'$\n\nSuggestions:\n1. I suggest the authors use a different notation in $L_t(f, f')$, since it is confusing to $L_f$", "questions_for_authors": "I have the following questions:\n1. In the case where the variances are all known, the algorithm in the literature I referred above can achieve regret $\\sqrt{A * \\sum_{t=1}^T \\sigma_t^2 * \\log|F|} + d_{elu}$. However, the setting therein requires the noise scale bounded by 1. Is it possible to improve your results so that the dominating term also scales with $\\sqrt{A * \\sum_{t=1}^T \\sigma_t^2 * \\log|F|}$, while keeping the dependence on the scala of noise to be logarithmic?\n2. In the current setup, the variance cannot depend on the action chosen. If the variance depends on the action chosen at each time step, will the results still work?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gZarGVC2JO", "reviewer": "Reviewer_PCY8", "summary": "This paper studies contextual bandits with heacy-tailed reward. If the variance is known, the authors use catoni estimator to achieve an near optimal regret upper bound. If the variance is unknown, but the variance of variance is bounded by variance times a constant factor, then the authors propose another method that first uses catoni estimator to estimate the variance, and then use one more catoni estimator based on the estimated variance. They prove that it also achieves a near optimal regret upper bound.\n\n=====After rebuttal=====\n\nI read the rebuttal. My score remains.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful suggestions.\n\n**Q1**: In Algorithm 1, choosing the action $x_t$ and estimating the $\\hat f_t$ can be inefficient.\n\n**A1**: The double oracle is a standard way for optimism in online RL and bandits with general function approximation [1,2,3]. In linear function approximation, we can compute bonus $b_t$ efficiently [4] and choose $x_t=argmax_{x\\in\\mathcal X_t} \\hat f_t(x) + b_t(x)$. However, there is no counterpart for general function approximation even when the reward range has a small bound. How to calculate the bonus efficiently is an open question even with bounded rewards.\n\n**Q2**: There is no experiments. Applicability?\n\n**A2**: Our work primarily focuses on theoretical analysis, and serves as a first step to use the Catoni estimator for nonlinear function approximation. We provide rigorous proofs demonstrating that the weighted Catoni estimator is robust against heavy-tailed noise. Although the proposed theoretical algorithm is not computationally efficient, our analysis serves as a first step toward designing robust algorithms for general function class. We believe the Catoni estimator and the variance-aware weighting technique offer valuable insights for practical use. Developing an efficient, practical version of the algorithm is a question for future work.\n\n**Q3**: In table 1, it seems that DistUCB has a better regret. Does footnote mean it has a larger $\\tilde d_F$ If the function class is restricted to Gaussian or exponential, what is the difference between $\\tilde d_F$ and $d_F$?\n\n**A3**: Note that DistUCB does not achieve a better regret bound due to its polynomial dependence on the reward range $R$. Moreover, the order on $\\tilde d_F$ is generally incomparable to $d_F$. DistUCB assumes **realizability of the reward distribution**, i.e. true reward distribution $r = R + \\epsilon$ belongs to the considered class of distributions. In contrast, we only assume realizability of the reward mean $R$. Therefore, the footnote indicates that their assumption is stronger than ours.\n\nAccording to Definition 5.2 in the DistUCB paper, $\\tilde d_F$ measures the complexity of a class of distributions, while $d_F$ measures the complexity of a class of mean functions. These two notions are incomparable. Even in the Gaussian case, the total variation distance between $N(f, v_f)$ and $N(g, v_g)$ is incomparable to $(f - g)^2$. Further, the noise distributions may be complicated and not even satisfy the realizability.\n\n**Q4**: Assumption 4.1, is it common to have a small c in practice?\n\n**A4**: The fourth moment bound is required in most prior works (e.g. Li, et. al. and Huang, et. al) that handle the unknown variance case. Our assumption $Var[\\eta^2] \\le c Var[\\eta]$ is equivalent to theirs when $Var[\\eta]$ is bounded. Additionally, bounded second and fourth moment is already a substantially weaker condition than a bounded range within $[0,1]$.\n\n**Q5**: In Theorem 3.1, the regret lower bound depends on the used policy.\n\n**A5**: The intuition is as follows. Consider two bandit problems, each with two arms. These two bandits differ only in the reward distribution of the second arm. In both bandits, the first arm has a zero variance, and the second arm has variance $\\sigma^2$. The maximum regret between these two instances depends on how often the second arm is chosen, which is given by $\\mathbb{E}\\sum_t \\sigma_t^2 / \\sigma^2$. Therefore, we obtain a lower bound directly related to the variances of the selected actions. The construction is not policy dependent, but a simple argument that there are two problem instances, and any algorithm incurs a large regret in one or the other.\n\n**Q6**: Why Eq. (4) holds? Do you miss a \"[ ]\"?\n\n**A6**: We miss a \"[ ]\" and will correct it in the revision.\n\n**Q7**: Why \"indirect\" estimator in (3)? What if we just let $\\hat f_t$  be that one with minimum $\\sum_iE[(f(x_i)-y_i)^2]$?\n\n**A7**: We have explained the intuition in Lines 203-219 right. Specifically, the reason is that directly solving\n$$\n\\mathrm{argmin}_f Catoni(\\{\\frac{1}{\\bar\\sigma_i^2}(f(x_i)-y_i)^2\\})\n$$\ndoes not work well. If we use the optimization above \n\nand use Lemma 3.2 with $Z_i=\\frac{1}{\\bar\\sigma_i^2}(f(x_i)-y_i)^2$ that is on second-order of noise, then, we need to deal with the fourth moment of noises in the analysis even for the known variant case since Lemma 3.2 needs bounded variance of $Z_i$. In our approach, the indirect estimator helps to cancel the higher order of $y_i$ and make the term $(f(x_i)-f'(x_i))(f(x_i)-y_i)$ easier to analyze.\n\n\n[1] Jin C, et. al. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. NeurIPS, 2021.\n\n[2] Liu Q, et al. When is partially observable reinforcement learning not scary?. COLT, 2022.\n\n[3] Agarwal A, et. al. VO $ Q $ L: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation. COLT, 2023.\n\n[4] Abbasi-Yadkori Y, et. al.. Improved algorithms for linear stochastic bandits. NeurIPS, 2011.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I do not check the detailed proofs in appendix.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "It could be helpful in real-world applications with heavy-tailed noises, for example, the waiting time in routing systems. But no such experiments are provided in the paper.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\n- The paper's algorithm do have better regret upper bounds when the variances of arms are limited.\n\n- The concentration for Catoni estimator is a novel contribution.\n\n\nWeaknesses:\n\n- In Algorithm 1, choosing the action $x_t$ and estimating the $\\hat{f}_t$ seem require to use a double-oracle, and can be inefficient. Even if Algorithm 3 do some improvement on estimating the $\\hat{f}_t$, it can still be inefficient when choosing $x_t$.\n\n- There is no experiments, and I am wondering the applicabiity of these results. \n\n- Some parts are not clear enough, please see questions below.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. In table 1, it seems that DistUCB has a better regret. In the footnote, it is explained that \"DistUCB needs to estimate full reward distribution\n rather than just the mean\", does it mean it will have a larger $ \\tilde{d}_F$? If the function class is restricted to Gaussian or exponential, what is the difference between $ \\tilde{d}_F$ and $ d_F$?\n\n2. In Assumption 4.1, it is assumed that $Var[\\eta^2] \\le cVar[\\eta]$. Is it common to have a small $c$ in practice? For example, if the noise distribution is exponential, this $c$ could be very large.\n\n3. In Theorem 3.1, the regret lower bound depends on $\\sigma_t$, which depends on $\\pi_t$, i.e., the used policy. This is a little strange. In my opinion, the regret lower bound should be independent with the used policy. Can you explain more about this?\n\n4. Why Eq. (4) holds? Do you miss a \"[ ]\"?\n\n5. I can understand why equation (3) makes sense. But why we need to use this kind of \"indirect\" estimator? What if we just let $\\hat{f}_t$ be that one with minimum $\\sum_i E[(f(x_i) - y_i)^2]$? Could you explain more about this?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides a novel use of Catoni estimator to adapt to variances in contextual bandits. While using Catoni estimator is not new in bandits, using it for nonlinear function approximation settings is new and it was done in nontrivial and interesting ways. This paper is well-written as well.

For the final version, please address comments from the reviewers including typos.
Decision: Accept (spotlight poster)