Second Order Bounds for Contextual Bandits with Function Approximation
Authors: Aldo Pacchiano
Venue: ICLR 2025 Poster (2025)
Keywords: theory
contextual bandits
variance aware
second order
bandits
Primary area: learning theory
TL;DR: We derive second order bounds for contextual bandits with adversarial contexts and function approximation

Abstract: Many works have developed no-regret algorithms for contextual bandits with function approximation, where the mean rewards over context-action pairs belong to a function class $\mathcal{F}$. Although there are many approaches to this problem, algorithms based on the principle of optimism, such as optimistic least squares have gained in importance. It can be shown the regret of this algorithm scales as $\widetilde{\mathcal{O}}\left(\sqrt{d_{\mathrm{eluder}}(\mathcal{F}) \log(\mathcal{F}) T }\right)$ where $d_{\mathrm{eluder}}(\mathcal{F})$ is a statistical measure of the complexity of the function class $\mathcal{F}$ known as eluder dimension.  Unfortunately, even if the variance of the measurement noise of the rewards at time $t$ equals $\sigma_t^2$ and these are close to zero, the optimistic least squares algorithm’s regret scales with $\sqrt{T}$. In this work we are the first to develop algorithms that satisfy regret bounds for contextual bandits with function approximation of the form $\widetilde{\mathcal{O}}\left( \sigma \sqrt{\log(\mathcal{F})d_{\mathrm{eluder}}(\mathcal{F}) T } + d_{\mathrm{eluder}}(\mathcal{F}) \cdot \log(|\mathcal{F}|)\right) $ when the variances are unknown and satisfy $\sigma_t^2 = \sigma$ for all $t$ and $\widetilde{\mathcal{O}}\left( d_{\mathrm{eluder}}(\mathcal{F})\sqrt{\log(\mathcal{F})\sum_{t=1}^T \sigma_t^2  } + d_{\mathrm{eluder}}(\mathcal{F}) \cdot \log(|\mathcal{F}|)\right) $  when the variances change every time-step. These bounds generalize existing techniques for deriving second order bounds in contextual linear problems.

Published as a conference paper at ICLR 2025
SECOND ORDER BOUNDS FOR CONTEXTUAL BANDITS WITH FUNCTION APPROXIMATION
Aldo Pacchiano
Boston University and Broad Institute of MIT and Harvard
ABSTRACT
Many works have developed no-regret algorithms for contextual bandits with function approximation, where the mean rewards over context-action pairs be- long to function class F. Although there are many approaches to this prob- lem, algorithms based on the principle of optimism, such as optimistic least squares have gained in importance. The regret of optimistic least squares scales as Ô (Vdeluder(F) log(F)T) where (eluder(F)) is statistical measure of the complexity of the function class known as eluder dimension. Un- fortunately, even if the variance of the measurement noise of the rewards at time 1 equals of and these are close to zero, the optimistic least squares al- gorithm's 's regret scales with vT. In this work we are the first to develop algorithms that satisfy regret bounds for contextual bandits with function ap- proximation of the form Ö (oVlog(F)ddludee (FiludderFFFFFF (F]T + deluder (F) log([F() when the variances are unknown and satisfy of = a for all t and δ deluder F)g/og((F)) E of deluder (F) Iog((FF) when the variances change every time-step. These bounds generalize existing techniques for deriving second order bounds in contextual linear problems.
INTRODUCTION
Modern decision decision-making making algorithms have achieved impressive success in many important problem domains, including robotics Kober al.) (2013): Lillicrap al. (2015), gaih Mnih et al. (2015); Silver al. (2016), dialogue systems Li et al. 2016), and online personalization Agarwal al. (2016); Tewari & Murphy (0177). Problems in these domains are characterized by the interactive nature of the data collection process. For example, to train a robotic agent perform desired behavior in an unseen environment, the agent is required to interact with the environment in way that empowers
learn about the world, while at the same time learning how to best achieve its objectives. Many models of sequential interaction have been proposed the literature to capture scenarios such as this. Perhaps the most basic one is the multi-armed bandit model TTompson (1933); Lai & Robbins (1985) Auer et al. (2002a); Lattimore & Szepesvári] (2020), where it is assumed learner has access K N arms (actions), such that when playing any of these results in a random reward. Typically, the learner's objective is to select actions, and observe rewards in order to learn which arm produces the highest mean reward value. Algorithms for the
bandit model can be used to solve problems such selecting treatment that in expectation over the population achieves the best expected success.
Deploying an algorithm designed for the multi-armed bandit setting may be suboptimal for applica- tions where personalized policies are desirable, for example, when we would like to design a treatment regime that maximizes the expected success rate conditioned situation arises in many different scenarios, from medical trials Villar et al. (2015); Aziz et al. (2021), to education Erraqabi et al. (2016), and recommendation systems Li et al. 2010 In many of these decision decision-making scenarios, it is often advantageous to consider contextual information when making decisions. This recognition has sparked a growing interest in studying adaptive learning algorithms
individual's characteristics. This

---

Published as a conference paper at ICLR 2025
in the setting of contextual bandits Langford & Zhang 2007); (2013) and reinforcement learning (RL) Sutton (1992).
Li et al. (0110); Agrawal & Goyal
In the contextual bandit model. learner interacts with the world in sequential manner. At the start of round & E N the learner receives a context z E X, for example in the form of user or patient features. The learner then selects an action to play O₂ E AA, representing for example medical treatment, and then observes a reward r, E IR that depends on the context Ty, the action or and may be random. For example Fr may be the random binary outcome of medical treatment de on specific patient zz. The study of contextual bandit scenarios has produced a rich literature. Many aspects of the contextual bandit model have been explored, such as regret bounds under adversarial rewards Auer et al. (2002b); Lattimore & Szepesvári (2020); Neu & Olkhovskaya (2020), learning with offline data Dudik et al.) (2012), the development of statistical complexity measures that characterize learnability in this model Russo & Van Roy| 2013)); Foster et al. (202T) and others.
The focus of many works, including this one is to flesh out the consequences of different modeling assumptions governing the relationship between the context, the action and the reward For example by developing algorithms for scenarios where the reward is a linear function of a linear function of an embedding of the context and action pair Auer (2002); [Rusmevichientong & T Tiitsiklis (2010);
Chu et al. (20TT): Abbasi- Yadkori et al. (2011). This has lead to algorithms such as OFUL that can be used to derive bounds for contextual bandit problems with linear rewards [Abbasi- Yadkori et al.)
(201T). Other works have considered scenarios that go beyond the linear case, where it is assumed the reward function over context action pair Ft, az is realized by an unknown function f. belonging to a known function class F (which can be more complex than linear). Various adaptive learning procedures compatible with generic function approximation have been proposed for contextual bandit problems. Among these, we highlight two significant methods relevant to our discussion; the Optimistic Least Squares algorithm introduced by Russo & Van Roy (2013) and the SquareCB algorithm introduced by /ooteer& & Rakhlin (2020). Both of these methods offer guarantees for cumulative regret. Specifically, the cumulative regret of Optimistic Least Squares scales with factors
O(V deluudor (F) log(( [F)),, while the cumulative regret of Square CB scales O (VI-A) log( log(
where A is the set of actions. The eluder dimension (detuder) is a statistical complexity measure introduced by Russo & Van Roy (2013). that enables deriving guarantees for adaptive learning algorithms based on the principle of optimism in contextual bandits and reinforcement learning
et al. 2022);; Jin et al. (222];; y Osband & Van Roy (2014); Chan et al. (2021).
The design of algorithms that can handle rich function approximation scenarios represents a great leap towards making the assumptions governing contextual bandit models more realistic and the algorithms more practical. The concerns addressed by this line of research are focused on the nature of the mean reward function. Nonetheless, they have left open the study of the dependence on the noise & = rt- - (x a.). Intuitively, as the conditional variance of & decreases, the value of re contains more information about the reward function f.. Algorithms that leverage the scale of the variance to achieve sharp regret bounds are said to satisfy a variance aware or second order bound.
Different works have considered this research direction and developed variance-dependent bounds for linear and contextual linear bandits Kirschner & Krause (2018); Zhou et al.) (2021): ): Kim et al. (2022); Zhao et al. (2023): Xu et al. (2024). In summary, the sharpest bounds for contextual linear bandits are achieved by the SAVE Algorithm in Zhao et al. (2023) and scale (up to logarithmic factors) as
a 12 where of is the conditional variance of & the time measurement noise.
In the context of function approximation, second order bounds for contextual bandits have been developed in Zhao al. (202)) under the assumption that the value of the conditional variances o is observed. This restrictive assumption has been lifted in more recent work Wang et al. (2024b a) under a stronger distributional realizability assumption. In Wang et al. (0024bja) the authors assume realizability of the noise distribution, that is, the existence of function class that fits not only the mean rewards as a function of context- pairs, but also the measurement noise. This is a somewhat restrictive assumption since it effectively reduces the set of problems that can be solved to parametric scenarios where the distributional class of the noise is known; something that in practical settings typically means simple scenarios such as gaussian or bernoulli noise.
We formally introduce this quantity in Section Here we simpler notation to avoid confusion.
2

---

Published as a conference paper at ICLR 2025
A recent work Jia al. (2024), published while our paper was under review, removes the assumptions made in Wang et al. (2024b a). Here a summary of their results. When the variances o, are revealed with the contexts, they show that for some function classes, any algorithm must incur regret of ? ( //mnn(|nA,, deluder) A + min (deluderr VIA(T)), where A = - o². They also propose an algorithm with an upper bound of O (VIAJA log((F)) + deluder log( (F)). In this setting, our deluder log((F)) (see Theorem 3.5 for the special case where all variances are equal). For the setting where variances not revealed with di and may depend on the action or, or.Dia et al. (2024) derives the lower bound Ω min VVeeluder + deluder, V VATT For the unknown fixeanvriance case, our bounds match
techniques from Section 3 yield refined bound of O ( /deluder-Alog((
their lower bound (see Theorem 4.6). They also present an algorithm achieving an upper bound of
O deluder log(((F)) detuder log( ( which matches our result Theorem 4.10
Contributions. In this work we present second order bounds for contextual bandit problems under a mean reward realizability assumption. The techniques we develop are inspired by previous works on variance aware linear bandits such as Zhao et al. (2023), and rely on uncertainty filtered multi-scale least squares procedure. We are able to make the connection to general function approximation by refining existing techniques prove eluder dimension regret bounds such those presented in Russo & Van Roy (2013); Chan et al. (202T); )): Pacchiano et al. (202)). These techniques should be easily extended to the setting of reinforcement learning and beyond, thus unlocking important area of research. The sharpest bounds we develop this work (satisfied by the same algorithm) have
the form O deluder v [F) ET of deluder log((Fl) when we allow different conditional
variances during time-steps, and O lov/deluder log([F])) deluder log((F)) when o, = a for all Although it is likely our bounds not the sharpest in the case of different variances, since eluder dimension bounds as in Russo & Van Roy (2013) suggest the dominating term in the optimal
bound should scale as O V deludder log((FF) ΣT= of
we believe sharper analysis based on our
ideas might be sufficient to prove such result.
2 PROBLEM DEFINITION
In this section we consider the scenario contextual bandits, where at time t the learner receives a context v, X' belonging a context X,, decides to take action a, E AA and observes reward of the form rt such that E, [rx] functions with domain X' A (see Assumption 2.1). Throughout this section we use the notation = f. (z,, 0²) + & so that the conditional expectation of & satisfies E.[šs] = 0. Throughout this work we will use the notation of (ar, denote the time conditional variance of the noise.
[-(r,, ax) where it is assumed that f- E F for J a known class of
We'll assume the random variables are bounded by known parameter B > O with probability one.
The objetive of this work is to design algorithms with sublinear regret. Regret is a measure of performance defined in the realizable contextual scenario studied this work as the cumulative difference between the best expected reward the learner may have achieved at each of the contexts it interacted with and the expected reward of the actions played.
Regret(T) (T)
Σ max fa fa a) fa(z,, az)
The objective is to design algorithms with regret scaling sublinearly with the time horizon T, Assumption 2.1 (Realizability). There exists (known) function class F X x A - RR such that [,[re] f- (xs, at) for all & N. Assumption 2.2 (Boundedness). There exists (known) constant B > 0 such that Irel, [Sl B and max (f a)l & B and max (f [1, a) - (z a) < B for all f. E and all
i ee N.
3

---

Published as a conference paper at ICLR 2025
The sample complexity analysis of our algorithms will rely a combinatorial notion of statistical complexity a scalar function class known as Eluder Dimension Russo & Van Roy (013)). We reproduce the necessary definitions here for completeness.
Definition 2.1, (c (c-dependence) Let 9 be a scalar function class with domain and > 0. An element Z is d-deenddent
2 w.E.. 9 if any pair of functions 9.9 E g satisfying v [)=1(9(()) {(2)))² & also satisfies g(=) - g'(2 e-independent of (Z1.--. 2n w.r.t G if is not dedepedeent on ,
(=1,"',,,,)
c. Furthermore,
2 is
Definition 2.2. (c-eluder) The E- non monotone eluder dimension dejuder (G, E) of G the length of the longest sequence of elements in Z such that every element is iiddepeendn of its predecessors. Moreover, we define the c- e-eluder dimension (gluder(g,c (.GG..... c) as deluder (eluder(G,c) = maxe's detuder c).
In order to introduce our methods we require some notation. The uncertainty radius function is mapping w : X x x P(F) + R defined as,
w(x, a, g) max f(x, (x f.feg
for I E X, E The quantity w(x, a, 9) equals the maximum fluctuations in value for the function class G when evaluated in context æ E X' and action E A. Throughout this work we will use the notation [(A, B.... ; C) denote the sigma algebra generated by the random variables
A, B.... B.B.......
In this work we design the first algorithm for contextual bandits with function approximation that satisfies a variance dependent regret bound. In this work we extend the optimistic least squares algorithm for contextual bandits with function approximation Russo Van Roy (013). Our main result (simplified) states that,
Theorem 2.1 (Simplified). Let 8 (0, 1). There exists an algorithm that achieves regret rate of.
(T) & θ daluder (x.4),
Σ of log (1F1/8) + Bdeluder
F
log( log( F1/0)
for all T E N with probability at least
5. Where Ö(.) hides logarithmic dependencies.
SECOND ORDER OPTIMISTIC LEAST SQUARES WITH KNOWN VARIANCE
In this section introduce algorithm that satisfies second order regret bounds. Algorithm I takes as input a variance upper bound 0² such that of & o², and achieves a regret bound of order
Regret(T) & O (ov/ deluded B/T)T log FFF) + detuder (T.
This is a warm-up example that will be sharpened in section 4.2 to the case where the variance is unknown where uncertainty filtered least squares procedure that satisfies sharper bounds than the unfiltered ordinary least squares guarantees. For complete discussion of estimation bounds for least squares, and their use in the optimistic least squares algorithm from Russo & Van Roy (2013) see Appendix B Since o² < this bound could be much smaller than the regret bound for Optimistic Least Squares (Algorithm 3 described in Theorem B.4 that scale as Ola V( detuder (F, B/T log (T)(/))))) In this section we work under the following assumption that we relax in section
achieve regret bounds of the same order. This algorithm is based
Assumption 3.1 (Known Variance Upper Bound). There exists (known) constant o such that or & o² for all t N.
Given a data stream {(1g, ae, re) where rz fx az) & for f. F such that & is condi- tionally zero mean, a sequence of subsets of G, ... 92 = 9 = such that G, is a function of ((xe, dg, re) }=)) and f. G. for all i E N. Given 7 0 define an uncertainty filtered least squares objective that takes a filtering parameter r > 0 and defines a least squares regression function computed only over datapoints whose uncertainty radius is smaller than T,
ff = argmin Σ (f(æ,, 0z) - -r)) 1(w(xe ar, Gr) feg,
<T)
(1)
1-1
4

---

Published as a conference paper at ICLR 2025
The uncertainty filtering procedure will allow prove least squares guarantee with dependence on the variance and also on a vanishing low order term that scales with rB. We'll use the notation
Be 8, (0,0,, Ø²) (4min(7B, (3) 166 Log(t)
denote the confidence radius function, in this case function of 8 and ō². Algorithm shows the pseudo-code for our Second Order Optimistic Algorithm.
Algorithm Second Order Optimistic Least Squares
1: Input: function class F, variance upper bound o².
2: Set the initial confidence set Go F.
3: for t 1, do
4: Compute regression function for each threshold level TV
for i E {0} o [+:] where B 2
q: = [log(()
ft argmin (f(rr rε) ( ae, 9e) < ET) fec.-1 f-1
5: Compute threshold confidence sets for all ie (0) [gd].
(e(T)) =
(2)
[ { |EEF
f(x,,))-(xxx,aa)) -(tt 1((as, a (T,,,,,07)) } gc-((T))
6: where 0, 2(1+1)2
7: Compute G, = G--1 n (n--0(((T))
8: Receive context Zt.
9: Compute Ue( a) maxfes, f(1, a) for all a A.
10: play a, argmax UelIt, a) and receive r fx(x, a.) + &
11: end for
Notice that by definition in Algorithm| the confidence sets satisfy Gr S Ge for all & l. order to state our results we'll Il define sequence of events {E such that & corresponds to the event that f. E G--1 and therefore f. E Gr for all &
The following proposition characterizes the error of the filtered least squares estimator fī when &, holds.
Proposition 3.1. /Variance Dependent Least Squares] Let N, 0 and If G2 for all & 1 - 1 and & holds then
P
Σ
- fa(x), 1 (ww(x, ag, Ge) &T) (,(T,,,0)), & > P(E))) )
(3)
The proof of Proposition result from Proposition 3.1 For a given r > 0, estimator fī achieves a sharper bound than the ordinary least squares estimator because the low order term in the portion of the analysis that requires the use of Freedman's 's inequality (see lemma A.1 that has magnitude scaling with the error of fí on historial points can be upper bounded by instead of scaling with B. This results in second order term scaling with min(rB, B²) instead of B² as reflected by the definition of 3r 8, a.).
be found in Appendix C It follows the structure of the least squares
In contrast with the results of Lemma B.1 the confidence radius of the r-uncertainty filtered least squares estimator depends on a variance upper bound whereas uncertainty radius Lemma B. doesn't. Proposition 3.1 provides us with variance aware least squares guarantee. If the uncer- tainty threshold T is small, the historical least squares сиrоr captured by cquation 3 scales with ²² (o)(t and does not depend on the scale of B. Algorithm [ leverages these confidence sets design a variance aware second order optimistic least squares algorithm. The basis of the regret analysis for Algorithm[ is the validity of the confidence sets G, and therefore the estimators U1 a,) being optimistic.

---

Published as a conference paper at ICLR 2025
Lemma 3.2. The confidence intervals are valid so that f. E for all t E N and optimism holds, maX.EA ()),,a) & Ue(zz: az) with probability at least 6 for all N.
The proof of Proposition 3.2 can be found in Appendix From
denote by & the event described in Lemma 3.2 where all the confidence intervals are valid. order to relate the regret to the cluder dimension of F, we develop sharpened version of Lemma B.3 to bound the uncertainty widths over the context-action pairs played by Algorithm
of the Lemma B.3 3 guarantees insufficient to yield the desired result because this result is unable leverage any dependence on the scale of the widths in the definition of the confidence sets. This is sufficient to show regret bound as it is evident by following the same logic in the analysis of the optimistic least squares (Theorem B.4p. In order to prove this result, we need to first bound the number of context-action pairs with large uncertainty radius.
Lemma 3.3. If Algorithm 7 is run with input variance upper bound a > O, & is satisfied and (9t) ( the sequence of confidence sets produced by Algorithm then for all N and T 3 Tgr
Σ (wllr, aes Ge) > T) < doluder (F,T) (o4Blo((1)F10))
64a² ( (og(T( +1)
Lemma
can be used to show the following sharpened version of Lemma
B.3
Lemma 3.4. If & holds, then for all T N the uncertainty widths of context-action pairs from
Algorithm 7 satisfy.
Σ w(1,, at, 91) O (0 (F,
+ Bdeluder (B,TT) B/T) log( log(T(F1/8))
The proof of this result is based on integration argument that leverages the inequality in Lemma 3.3 Algorithm| satisfies the following regret bound,
Theorem 3.5. If ó (0, ) is the input to Algorithm 7 satisfies.
Regret(T) < O (av detuder (F, B/T) log(T) + B deluder for all N with probability at least 5.
The proof of this Theorem can be found in Appendix D
4 CONTEXTUAL BANDITS WITH UNKNOWN VARIANCE
In the case where the variance is not known our contextual bandit algorithms work by estimating the cumulative variance up to constant multiplicative accuracy and use this estimator build confidence sets as in Algorithms 3 and In section 4.1 we describe how to successfully estimate the cumulative variance in contextual bandit problems, in section 4.2 we show how to adapt a version of Algorithm [ to the case of single unknown variance and finally in section 4.3 we introduce Algorithm 2 that
satisfies regret guarantee whose dominating term scales with deluder low order term with deluder log(I
Σ of. and the
4.1 VARIANCE ESTIMATION IN CONTEXTUAL BANDIT PROBLEMS
In this section discuss methods for estimating the variance in contextual bandit problems. Our estimator the cumulative least squares error of a sequence of (biased) estimators. Given context- action pairs and reward information {(I,, az, rx) } 1 and filtering process b (b))/=1 of bernoulli random variables be E 1) such that by is Σ(z,, an, bi, r1, FE-1, ag by T2-1 1,, Lt, 0x)-
rz))
measurable. Let fhr be the "filtered" least squares estimator:
Jb. argmin JEF
be (f(re, az) - 22
filtered least squares estimator satisfies least squares bound similar Lemma B.1

---

Published as a conference paper at ICLR 2025
Lemma 4.1. Ler (0, e (ze,
f-1 be sequence of context-action pairs and and (re)
be a sequence of values satisfying Tą = f. at) + Ee where f. F and the & are conditionally zero mean. Let {be)i=ibe a filtering process of Bernoulli random variables be {0,1] ] such that by is
(( 00,1,,1,1,111 a1,b,, It-1, ag-1, - re-1: 0z)) measurable. Let fr. = argmin feF E be (f( - r2)² be the "filtered" least squares estimator. If Assumption 2.2 holds then,
Σ Ee be (f.(2e, f (x))
< 6B² log(2)
and
Σ be (fr (xe, f- fe( - &
log(2/F10))
with probability at least 1 1- 8.
Based on the definitions above we will consider the following cumulative variance estimator for filtered context, action, reward process:
Wbb Σ be (re fP (IFe,,)))²
We now prove this estimator achieves small error. Lemma 4.2. Let 8 (0, 1) be probability parameter. If Assumption 2.2 holds,
2 Whb 11B² 11
Whb & bw.b 48B² 4 llg(
with probability at least 1 5 where W.b. = E be o².
Using the union bound (by setting ő = 2 in Lemma we can write an anytime guarantee for the variance estimators W.br).
Corollary 4.3. Let 8' E (0, 1), (1z, ae, re) be a sequence of context-action and rewards triplets such that fr = fa(xx,, ar) + Es where fo E and the & are conditionally zero mean. Let (be) 1t-1 be a filtering process of Bernoulli random variables be E {0,1) such that by is E(x1, bj T1, It-1, ag-1, bt-1. Ie, ae) -measurable and f.b. argmin Ei=1 be (f(ze, ae) - rz) be the "filtered" least squares estimator, If Assumption holds there exists universal constant C' > 0 such that the cumulative variance estimator W Ei=1 be (re f.b (xz, oz)) satisfies.
whb - C. BB (loog(()//88) 11/8/+++( & Wh & 2W + C. B² log(t(FF118)
3
with probability at least 1 8' for all t N.
The proof of Corollary 4.3 can be found in Appendix E.I
4.2 UNKNOWN- VARIANCE VARRANN-VVRIANCE
GUARANTEES FOR ALGORITHM II
Although Algorithm D was formulated under the assumption of a known variance upper bound in this section we show is possible to combine the variance estimation procedure we propose here with Algorithm [ A simple and immediate consequence of Corollary 4.3 is,
Corollary 4.4. Let 8' E 10, Under the assumptions of Corollary
4.3 Ifor = o for all t N and
define Nr: Ex=1by be then,
bWb: C. BBlog(( 0²
2Wb. Nb.
C. B² (og(111)/))))
+
3.bb
Nb.
Nb.
with probability at least 1 - 8' for all t N. Where C > O is the same universal constant as in Corollary 4.3
7

---

Published as a conference paper at ICLR 2025
Let {be) be the trivial filtering process defined by setting b for l Σ t 1 that Nb. t-1 and define the variance upper-bound estimator sequence of B and o
th min (0t 1-1 C-B ) for all > Corollary 4.4 implies that
M C. log(t)F1//8) & 30 + 3C BB log 1 F1/8))
(5)
1-1
1-1
t
for all i N with probability at least 1 1 8'
We'll analyze a version of Algorithm where the confidence sets Ge(T)) are computed using confi- in equation
dence radii equal to Be (T: 21141y2
With these parameter choices, we show
result equivalent to Lemma 3.2
Corollary 4.5. Let ó (0, 1). 8f is the input to Algorithm 7 and of estimators are computed by
setting 8' 8/2, then the confidence intervals are valid so that J. E G. for all Le N and optimism holds, maX,e. f. a) & U2(Ze, az) with probability at least 1 8 for all t N.
The proof of this result follows by simple union bound between the result of Lemma 3.2 and the
inequality x² & G.. Let & denote the event described in Corollary 4.5 This version of Algorithm satisfies the following guarantees,
Theorem 4.6. Let ā 1). 6f 2 is the input to Algorithml I and o estimators are computed by setting 8' 6/2. If ot a for all N the regret of Algorithm with modified confidence set sizes satisfies,
(Tg & O (ov Bo
(og( + Bdeluder B/B) (og)) log(T(F1/8)
for all T N with probability at least - 8.
The proof of Theorem 4.6ccan can be found in Appendix R.2
4.3 UNKNOWN- VARIANCE DEPENDENT LEAST SQUARES REGRESSION
We borrow the setting of Section 3 with few modifications. Given a data stream ((ze, ag, re) JeN where r3 [xe, (e)) + & for f. F such that & is conditionally zero mean, a sequence of subsets
of G S ..... G2 S 9i = F such that G/ is a function of {x az, re) 1e)) and f. Gj for all t e N. Given 7 0 we define an uncertainty-filet filtered least squares objective,
((222)]
argmii fEG. 8-1
Σ
- (w(xe, ae, 92) E (r,
(6)
in the following, for any T we'll use the notation by to denote the filtering random variables by I (w(E,, ae, 9 (r, 2r)). Similarly, we denote by by- (b
We develop result equivalent to Lemma B.T and Proposition 3.1 to characterize the confidence sets. Just like in Section 3 we write our result in terms of sequence of events {E110, such that E corresponds to the event That f. E G/-11 and therefore f. E Gr for all l" f - so that & S E for all L.
Proposition 4.7. Let (0, 1) and O. Let (E be sequence of events such that E E and E E Let ((T227] be result of solving the uncertainty-filter least-squares objective from equa- tion Additionally let w.b be the filtered estimator of the cumulative variances defined by equation when setting by = 1 (w(ze, ag, G. (T,27)) and Whb == Σi=1 oî 1 (w(xe, at, G) E (T, (T,2T]). There exist universal constants C,C' > 0 such that the events W.(T) defined for any as
(21, oz) - f((z 1 [ as, Ge) (T,2T])
< C'r w.: log (151/5) + C'rBlog (11118)
8

---

Published as a conference paper at ICLR 2025
Algorithm 2 Unknown-Variantn Second Order Optimistic Least Squares
1: Input: probability parameter å (0, 1), function class F.
2: Set the initial confidence set 9 .F.
3: for t= 2. ... do
4: Compute regression function for each threshold level 2: for i [qel where qi [log(t)]
[-1
f argmin feg
(f(r,, 2 (w(a az, 92) E (Ta, T--1))
5: Estimate the sum the filtered variances for all threshold levels т; for i [qt]-
w.ir Σ (w(re, ae, ae E (Te, T-1)) (re- - s( 1 (1re
6: Compute threshold confidence sets for all i [gc].
(..T.) FEF: Σ (T)))))) - ((x,,)))) 1wo (r, ET) V'T.W,"" log (2/21)71/8)
+C'T,B (2/7111/88 (6-1(T))
where C² is the constant from Proposition 4.7
7: Compute g = -/-1 n ((())
8: Receive context Zt.
9:
Compute Ur(22, a) = max f(2,, a) for all a A.
play a, argmax U1(Te, a) and receive rt fa at) Ec.
11: end for
and
Cr/Ww w, log (111118) B'rBlog (171/8) & c' = w log (1)115) d" B (1F1/8)
satisfy the bound P(ε (WA(T))))
3 22
The proof of Proposition 4.7 can be found Appendix E.3 Similar to Corollary B.2 and Proposi- tion 4.7 we derive the following anytime guarantee for the confidence sets, and show that optimism holds
then Lemma 4.8. Let E (0, 1). When the confidence sets Gi S are defined as in Algorithm 2 f. E Gj so that max f-(2z,)) a) & Ue(I,, az) (optimism holds), and for all i E [q.].
G((T)) { f S.t. Σ
( (xe, az) - f()e, 1ww(xe, ae, Ge) (T;, 27,1) &
c C'Ty log (2(1+ 1)2t(//))) c" T; log (21+(/1//8) }.
(7)
with probability least 1 for all t N. Where O" is the same universal constant as in Proposition 4.7
The proof of Lemma 4.8 can be found in Appendix E.3 Define E' as the event outlined in Lemma 4.8 such that f. E G/, optimism holds, and inequality holds for all i E [q:] and all f E N. This event satisfies P (E') > 1 1 5. The proof of the regret guarantees of Algorithm 2 will follow a similar template as in the previous sections; establishing optimism and then bounding the sum of the uncertainty widths over the context-action pairs played by the algorithm. In order to execute this proof strategy need way relate the of the uncertainty widths to the definition of
can

---

Published as a conference paper at ICLR 2025
the confidence sets and by doing with the true cumulative sum of variances. We do this via the following Lemma.
Lemma 4.9. If ([ the sequence confidence sets produced by Algorithm ? there exists universal constant C such that when E! is satisfied,
1 (w oe, Gi) 2T,)) &
Č ( (F,Ts)
Ō. B dalnder (.)))
W log (IT(F1/6)
log (iT)) + Ō deluder (F, Ts)
Ti
for all Te N and [gr].
The proof of Lemma 4.9 can be found in Appendix F Finally, we can combine the result above with an optimism argument to prove the following regret bound for Algorithm 2
Theorem 4.10. Ler T N. 8 (0, 1) and q log(T)). The regret of Algorithm satisfies.
Regret(T) (T)
B F, log log(T)
<0 doluder
F. F:T)
of
lTg(T) log (T) Bdetuder
simultaneously for all T e N with probability at least
6.
Proof Sketch. The proof of Theorem 4.10 relies on observation that when El holds, optimism implies
T
Regret(T)
w(x ar, G.).
The sum of widths can be upper bounded as,
T B
w(t de, 9)) <
Σ 1 (wizr, au fi) (Ti, (rr)))
24
Finally Lemma 4.9 can be used to finish the proof.
5 CONCLUSION
In this work we have introduced second order bounds for contextual bandits with function approxima- tion. These bounds improve on existing results such as Wang al. (2024b) because they only require realizability assumption on the mean reward values of each context-action pair. We introduce two types of algorithm, one that achieves what we believe is sharp dependence on the complexity of the underlying reward class measured by the eluder dimension when all the measurement noise variances are the same and unknown, and a second one that in the case of changing noise variances achieves a bound that scales with the square root of the sum of these variances but scales linearly in the eluder dimension. In future version of this writeup we will strive to update our results to achieve a sharper dependence the eluder dimension scaling with its square root. We hope the techniques developed in this manuscript can be easily used to develop second order algorithms with function approximation in other related learning models such reinforcement learning. These techniques distill, simplify and present in a didactic manner many of the ideas developed for the variance aware literature linear contextual bandit problems in works such as Kirschner & Krause (2018): Zhou et al.] (20T)) D: Kim et al, y022): Zhao et al. 2203); Xu et al. (2024) and transports them to the setting of function approximation. Although we did not cover this in our work, an interesting avenue of future research remains to understand when can we design second order bounds for algorithms based on the inverse gap weighting technique that forms the basis the SquareCB algorithm from Foster & Rakhlin (2020).
have
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24:2312-222 2-2200, 2011.
Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pp. 1638-1646. PMLR, 2014.
Alekh Agarwal, Sarah Bird, Markus Cozowicz, Luong Hoang, John Langford, Stephen Lee, Jiaji Li, Dan Melamed, Gal Oshri, Oswaldo Ribas, et al. Making contextual decisions with low technical debt. arXiv preprint 1606: 1606.0366, 03966, 2016.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference machine learning, pp. 127-135. PMLR, 2013.
Auer, N. Cesa-Bianche and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 57:235-256, 2002a.
Peter Auer. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(())48-777 2002b.
Maryam Aziz, Emilie Kaufmann, and
Riviere. On multi-armes bandit designs for dose-finding trials. Journal of Machine Learning Research, 22(14):1-38, 2021.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 19-26. JMLR Workshop and Conference Proceedings, 2011.
Jeffrey Chan, Aldo Pacchiano, Nilesh Tripuraneni, Yun S Song, Peter Bartlett, and Michael Jordan. Parallelizing contextual bandits. arXiv preprint arXiv:2 10590, 2021.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Miroslav Dudik, Dumitru Erhan, John Langford, and Lihong Li. Samplc-effieient nonstationary policy evaluation for contextual bandits. arXiv preprint arXiv:1210.4862, 2012.
Akram Erraqabi, Alessandro Lazaric, Michal Valko, Emma Brunskill, and Yun-En Liu. Rewards and errors in multi-arm bandits for interactive education. In Challenges in Machine Learning: Gaming and Education workshop at Neural Information Processing Systems, 2016.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199-3210. PMER, 2020.
Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:21 12. 13487, 2021.
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pp. 100-118, 1975.
Steven Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-Uniform. Non- parametric, Nonasymptotic Confidence Sequences. The Annals of Statistics, 1955):005--1080, 2021.
Zeyu Jia, Jian Qian, Alexander Rakhlin, and Chen Yu Wei. How does variance shape the regret in contextual bandits? Advances in Neural Information Processing Systems, 37:83730-83788 2024.

---

Published as a conference paper at ICLR 2025
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 34:13406-1341 13418. 2021.
Yeoneung Kim, Insoon Yang, and Kwang-Sung Saang-Sungaaa Jun. Improved regret analysis for variance- addativv linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing Systems, 35: 0670-107,, 2022.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with het- eroscedastic noise. In Conference On Learning Theory, pp. PMLR, 2018.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research,
2013.
T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.
John Langford and Tong Zhang. The epoch- algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96-1, 2007.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Gene Li, Pritish Kamath, Dylan Foster, and Nati Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 35:23737-23750, 2022.
Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky. Deep reinforce- ment learning for dialogue generation. arXiv preprint arXiv:1606.01541 2016.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670 2010.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint 1rXiv:1509 02971,, 2015.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. nature, 5 518(7540):529-533 2015.
Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. In Conference on Learning Theory, pp. 3049-3068. PMLR, 2020.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Aldo Pacchiano, Jonathan Lee, and Emma Brunskill. Experiment planning with function approxima- tion. Advances in Neural Information Processing Systems, 36, 2024.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35, 2010.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances Neural Information Processing Systems, 26, 2013.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484-489, 2016.
Richard S Sutton. Introduction: The challenge of reinforcement learning. In Reinforcement Learning, pp. 1-3. Springer, 1992.
Ambuj Tewari and Susan Murphy. From ads to interventions: Contextual bandits mobile health. Mobile Health: Sensors, Analytic Methods, and Applications, pp. 495-517, 2017.
12

---

Published as a conference paper at ICLR 2025
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-2555 -944, 1933.
Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
Kaiwen Wang, Nathan Kallus, and Wen Sun. The central role of the loss function in reinforcement learning. arXiv preprint arXiv:2409. 12799, 2024a.
Kaiwen Wang, Owen Ocrtell, Alckh Agarwal, Nathan Kallus, and Wen Sun. More benefits of being distributional: Second-order bounds for reinforcement learning. arXiv preprint arXiv:4402.07/98. 2024b.
Ruitu Xu, Yifei Min, and Tianhao Wang. Noisc-adaptive thompson sampling for linear contextual bandits. Advances in Neural Information Processing Systems, 36, 2024.
Heyang Zhao, Dongruo Zhou, Jiafan He, and Quanquan Gu. Bandit learning with general function classes: Heteroscedastic noise and variance-dependent regret bounds. openreview, 2022.
Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Variance seriance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference Learning Theory, pp. 4977-5020. PMLR, 2023.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532-4576.. PMLR, 2021.
13

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
Problem Definition
Second Order Optimistic Least Squares with Known Variance
Contextual Bandits with Unknown Variance
Variance Estimation Contextual Bandit Problems
4.2
Unknown- Variance Guarantees for Algorithm
4.3
Vnkiowe-Variance Dependent Least Squares Regression
5
Conclusion
10
Supporting Results
14
Optimistic Least Squares
17
Proofs of Section B
18
Proofs of Section 3
20
Proofs of Section
22
Proofs of Section
22
Proofs of Section
24
3 Proofs of Section
26
Eluder Lemmas
A
SUPPORTING RESULTS
Our results relies the following variant of Bernstein inequality for martingales, Freedman's '
inequality [Freedman (1975), as stated in e.g., Agarwal et al. (2014); Beygelzimer et al. (201T).
Lemma A.1 (Simplified Freedman's 's inequality). Let Z1, ...; Zr be bounded martingale difference sequence with /Zel < R. For any 8' e (0, 1), and n (0, 1/ R),, with probability at least -
log(1/8")
[z[ Σ
(8)
1-1
2-1
where Exi-] the conditional expectation Pinduced by conditioning on Z1, Zt--1
L Lemma A.2 (Anytime Freedman). Let 72) be a bounded martingale difference sequence with
7 & for all N. For any 8' E (0, 1), and 17 E (0, 1/ R), there exists universal constant C such that for all e N simultaneously with probability at least 1 8'.
Clog(1/8))
Σ 2.
(9)
where Ex[-] is the conditional expectation induced by conditioning Zı, Ze-1-
We will this notation denote conditional expectations throughout this work.
14

---

Published as a conference paper at ICLR 2025
Proof. This result follows from Lemma A.1 implies that with probability at least dz.
Fix time-index t and define 5, 12/2.
8'
Lemma A.1
log( (1/o))
Ze
Bz [22] < 11
"
8-1
8-1
A union bound implies that with probability at least 1
Σl= 6c 2
8', 121 18")
log(
Σ
Ze
E 17
E2 7
t=1
C'log(t/8")
E2
1
holds for all e N. Inequality (1) holds because (gg(1122//0 = (log(t8")).
Lemma A.3 (Uniform empirical Bernstein bound). In the terminology Howard et al. (2021) let S, = E Y; be a sub-up process with parameter e >> and variance process Wt. Then with probability least 8 for all t
1.41nin 2 max
We
5.2 +
S. & 1 max
8
W2
1 1))
5.2 8
+ 0.41c 1.4
2
max
In
m
where m >> 0 arbitrary but fixed.
As corollary of Lemma A.3 we can show the following,
Lemma A.4 (Freedman). Suppose {X1)22 an adapted process with |X,] & b. Let
Ee Var, where Var, = [x]]]] - -R][x,] For any E (0, 1), with probability at least
Σ - Ee 1 Vn
12 2/
6b In 12
for all a N simultaneously.
Proof. We are ready to use Lemma A.3 (ithh e b). Let S; = Σi_1 X, and W, Ei_1 Varz(Xe).
Let's set m = b². It follows that with probability 1 1- for all t teN
1.41n (2 max [12
We 1))
5.2
St 1.44/ max( b2)
In
W. b
))
5.2
+ 0.41b
1.4
2
max
In
Wr T22
1)
6
21 max W,, 62)
2
In
2
max
In
W.
1))
+ 21 2 max
+
In
ba
3
2 maxx / W., A) + bA3
$ S2W + 2bA, + bA?
22 2WW, 334?
15

---

Published as a conference paper at ICLR 2025
where A. = v 2 2n In (2 (max 8 1))) In 8 Inequality (t) follows because A > 1. By
identifying V, Wr conclude that for any 8 e (0, 1) and teN
IP
Σ Xe = 2v 3bA &
Where A, 2n (2 (max (6, 1))) + In j.
Since V & the with probability 1,
V 8a t
And therefore 21 In m2mxx( $ 1)) & 2 In In 2/ implying.
12
A
2ln
Thus
12 2t
12 2t
I
4
Vn
A + 6b In
<
8
Since V, & St the result follows.
Proposition A.S. Let 8' E (0, 3 (0, 1] and (Z,)z_ be an adapted sequence satisfying
0 & Z4 & B for all l E N. It follows that,
2B logllo///// (1/8")
2B log( 1/8")
(1 (1- 3)
Zt & (1+
E.[Z]]
B
with probability at least
28'.
Proof. Consider the martingale difference sequence X; Zi - -E,[Z,]. Notice that [X,] < B. Using the inequality of Lemma A.1 we obtain for all 1) E (0, 1/B²).
log(1/8")
"
log( 1/88)
2m Ba
E [z
1
with probability at least 1 8'. Inequality (i) holds because [x]] & B & 2B²E, for
8 all i E N. Setting 7 2B and substituting En X
E 7x
Eg %ee)
2B 2 log
Σ 2e + 3)
Σ Es [e]]
(10)
with probability at least 1 - 8'. Now consider the martingale difference sequence X = E[2,] - Z.
and notice that XX1 & B², Using the inequality of Lemma A.1 we obtain for all v E (0, 1/²),
[x((X)) + log l1g(1/8))
X < 1
log( (1/8")
2n
E, [
"
Settingn
@ and substituting Σ
X
Σ D6_1
Z
Ze have,
2B2
16

---

Published as a conference paper at ICLR 2025
2B log (
(1 - (3
Σ Z
Σ
Ze +
(11)
with probability at least - 8'. Combining Equations 10 and and using union bound yields the desired result.
B OPTIMISTIC LEAST SQUARES
The algorithms we propose in this work are based on the optimism principle. This simple yet powerful algorithmic idea the basis of celebrated algorithm for contextual bandits with function approximation known Optimistic Least Squares. Algorithm 3 presents the pseudo-code of the Optimistic Least Squares algorithm.
Algorithm 3 Optimistic Least Squares
1: Input: Function class F, confidence radius functions {3 [0.100. R
2: for == 1, ... do
3: Compute least squares regression
Se argmin JEr
(f( - -re)².
(12)
4: Compute confidence set
G: fEF: Σ (filze; f(2) Bc(0)
5: Receive context Tt-
6: Compute Ue(21, a) max f(2,, a) for all a A.
7: play a, argmax Uf(ze, a) and receive r. fa( ar) Ec.
8: end for
To derive bound for the optimistic least squares algorithm, we require guarantees for the confidence sets. This is captured by the following Lemma.
Lemma B.1. [LS guarantee] Let 8 E (0, 1), {e,, ) be sequence of context-action pairs and and {ri) 1 be a sequence of reward values satisfying Ti fa(21, at) + & where f. F and & conditionally zero mean. Let ft = arg min E 1 (s(x,, 0z) re)² 2 be the least squares fit. If Assumption 2.2 holds then there is a constant C> 0 such that,
Σ (Felae,a)) - fx
3c(()
with probability at least 1 5 for all e N where 3r(5) = 4CB² log(t: ( (F1/8).
The proof of Lemma B. can be found in Section C
This result allows provides us with the tools to
justify the choice of confidence sets in Algorithm
A simple corollary is,
Corollary B.2. Let 8 E (0,1) and Br(ō) = 4CB² log(t (F1/5) as defined in Lemma B.1 The confidence sets Gr satisfy f. Gt for all N simultaneously with probability at least Moreover, this property holds, Uz(2, a.) > maX a) for all N.
The proof of this result can be found Appendix In order to relate the scale of these confidence sets with the algorithm's regret we need to tie these values the statistical capacity of the function class F. This can be captured by its eluder dimension (see Definition 2.2). This is done via Lemma a standard result that is crucial in showing upper bound for the optimistic least squares algorithm
17

---

Published as a conference paper at ICLR 2025
regret. This result is version of Lemma 3 from (Chan et al. 2021 presented Lemma 4.3 in (Pacchiano et al. 2024) which we reproduce here for readability.
Lemma B.3. Let F be a function class satisfying Assumption 2.2 and with c-eluder dimension deluder( (F,e). For all I e N and any dataset sequence (Di h for D1 D and D, {(0,, at) M=
of context-action pairs, the following inequality on the sum of the uncertainty radii holds,
Σ wa Ce. De) & <0 min BT, BT. B((6) deluder ( + Bdellder [F, F.B(T)
Lemmas B. and B.3 can be used to prove Algorithm satisfies the following regret guarantee,
Theorem B.4. The regret of the Optimistic Least Squares (Algorithm) 3) with input values 5 (0. 1)
and () 4CB² log(t)F(/5) satisfies,
Regret(T)) < O BB deluder (F, B/T) T (og()))1/0) Bdejuder (F,
with probability at least 5 for all T N simultaneously.
The proof of this result can be found in Appendix C Thus the dominating term the regret bound (the term growing at /T rate) for optimistic least squares scales with the square root of the uncertainty radius, in this case given by the function (5) 4CB² log( T Fl defined in Lemma B.1 Unfortunately, this introduces an unavoidable dependence on B. Thus, the dominating term of our regret bound has scale controlled by B instead of the variances {o2) 12-1 This dependence comes up because the proof of Lemma B.T relies on Freedman's 's inequality (Lemma A. I in Appendix (A) that exhibits unavoidable dependence In the following section we show a way to bypass this issue by introducing a multi-bucket regression approach that has vanishing dependence on the low order terms.
the scale of the random variables in the low order terms.
C PROOFS OF SECTION
Lemma B.1. [LS guarantee] Let å E (0,1), {Te, 0t)[=1 be a sequence of context-action pairs and and (ri)11 be a sequence of reward values satisfying Tr f.(21, at) + & where f. F and & conditionally zero mean. Let ft = arg minje. Σ (f at) re)² be the least squares fit. If Assumption 2.2 holds then there is a constant C' > 0 such that,
Σ (1llre (=(xe, az)) (,(()
with probability at least for all te where Be(8) = 4CB² (tg(t: (F1/8).
Proof. Substituting ri ff f=(e,, ae) + Ee into the definition of fe we obtain the following inequalities,
Σ
(f) rE)² -) - rx)² Σ
substituting again the definition of re on the left hand side the inequality above and rearranging terms yields,
Σ -((e az)) <
Σ & (fa(ze, f((
(13)
We now focus bounding the RHS of equation
For any F let z (fa(ze, ar) f(x,, az)). The sequence Z, forms a martingale difference sequence such that
13
Ee 2 ) = o3 (f(ze, - f. a²) and Assumption 2.2 implies |z/| & B² for all
L N.
18

---

Published as a conference paper at ICLR 2025
We use Freedman inequality (see for example Lemma A.2 in Appendix A and show that with probability least 1 8' for e
to bound this term
Σ ot (f(me, uz) Sa (x2e C'log(t/0')
& (J(æe, az) (a ar)) &
"
(f(e) fx(1, 4CB log(t/"..
Where inequality (1) follows from setting T and noting that or & B for all Finally, setting 8 D and considering union bound over all f E F we conclude that,
Σ F (J+(xe,, fe az)) (fi(z), - (r)re 4CB² log(t (F1/8)
Plugging this inequality into equation 13 and rearranging terms yields,
(f(( az) - f((x) < 4CB2 loCtt (F1/8).
Corollary B.2. Let E (0.1) and Be(5) 4CB2 1og2 (F1/6) as defined in Lemma B. The confidence sets Gr satisfy fa Ge for all N simultaneously with probability least Moreover, this property holds, U2(1, at) i maxoe [x a) for all te N.
Proof. Lemma B.T implies that f. E 9r all E N simultaneously with probability at least When this occurs, the following sequence of inequalities is satisfied.
fa a) max f(z,, a) Uz( & Uz( fegt
a A. Thus holds that max (x), a) & (1(()))))
Theorem B.4. The regret of the Optimistic Least Squares (Algorithm 3 with input values 8 (0, and B,(6) = 42' log(t[Fl/8) satisfies,
Regret(T) O (BV detuder (F, B/T) (l/0) Bdeluder (F,
with probability al least for all T N simultaneously.
Proof. Lemma implies the event & where f. E Ge for all e N occurs with probability at least
1 1- 5. The analysis of the regret of Algorithm follows the typical analysis for optimistic algorithms,
Regret
max f. - asA
Uclæe, or) fa(z),
Ma a.) (,(2)
max f(xt, at) 8 (x), 1.feg.
Σ w(r oz, Gi)
o Bdellder (F,B/T) + /Br(0) (F, B/T) T)
19

---

Published as a conference paper at ICLR 2025
where fe is the function that achieves the argmax in the definition of U, over imput context 2
Inequality (2) holds because when holds, f. E 9 and ft E 9, for all t E N. Inequality (ti) is a
variation of Lemma 3 in (Chan et al. 202T (see a simplified version in Lemma B.3 from Appendix F))
Substituting (r( 4CB4 log
F10) finalizes the result.
D PROOFS OF SECTION 3
Proposition 3.1. |Variance Dependent Least Squares] Lett N,r 2 0 a > 0. 1f 1f & 8² for all Ett- and & holds then
(fi (oz, az) - (( < B,(T,,, & > ((E))) 8. (3)
Proof. Given
F consider martingale difference sequence Z/ for Ee N defined as,
z (J( (=() ( ae 9e) 7) 1( Ge) &
First let's see that
/ & min V
To see this we recognize two cases, first when / / 9e in which case 2 0. When f Gt, we
also recognize two cases. When (W ar, G.) < r) = 0 the random variable z = 0. When fe E Ge. and wrre, ae; Ge) & r. follows that [f ae) fx()) т. Finally since [&el B
we conclude |z < Bi)
The conditional variance of the martingale difference sequence/Z/] can be upper bounded as
Varr(Z/) = Ez((Z
of(f(ze ae) (z) 9e) <) 1(f 9c) σ2 (f ae) f. 0z) ( at 91) < r) 1( Ge)
where inequality (i) follows because of of & 02.
We now invoke Lemma A.1 applied the martingale difference sequence (4/)-t In this case R 7 BB and we'll set 7) B. # Thus,
z min(rB, B²) + 2
(f((z),))) - ax) ac, & 1(f +
(min(7B,15* 172) l/)(
(f(a, - fa(xe, az) 2 az, Ge) <T) 1( Ge) + (min((7, B²) + 472) log([Fl/88)
(14)
with probability least [ A union bound implies the same inequality holds for all f F
simultancously with probability at least 1 1-3. 8. Let's call this event We have just shown that P(B) > 5. In particular when holds, inequality 14 is also satisfied for f = ff. When & holds fī G--1 then 1(f7 Ge) =1 for al al t and therefore,
Σ Z = Σ (JT(xe, - f-(xr, & 1(w(re, ar, 91) & T).
(15)
'This is where the definition of Gc-1 an intersection of all previous confidence sets is important. The intersection ensures that for any J the minmmizer of the filtered least squares is achieved at an fo for which the inidicator 1f Ge) true for all 8 & 1.
20

---

Published as a conference paper at ICLR 2025
We proceed by subtituting the definition rt (xz, at) in equation and noting that when & holds f. 9--1, so that fi, the minimizer of the uncertainty filtered least squares loss satisfies,
(IT( (x) Ex)² (w(a,, 0e, Ge)
(w(we az, 9c) 7)
expanding the left hand side of the inequality above and rearranging terms yields,
(1s, - fa(xe, 1(w(xe, ae Gi) <T 2 Σ (fT fa Ee 1ww(x, ae, 9e) < <T)
(16)
To bound the right hand side of the inequality above plug inequality 14 and equality 15 into equation 16 we conclude that when B n & holds,
(JI (Tee - f((re, az)) 1e Ge) TT) 2 Σ (1 (alooae)--((aaaa (x(e, Ee [ww(r, ae, 96) 7) E
Σ
(f( fa ae))² (w ae Ge) T) + (2min(7B, + 883) log(1F1/0)
rearranging terms we conclude that when B n & is satisfied,
(f2, (x(e (w0 az, Ge) & r) & (4min(rB, B²) 1672) log(1Fl/1)
with probability at least P(B n E,) > F(E,) 8. This finalizes the result.
Proposition D.1 (Intersection Result), Let A, B, C be three sets such that, P(An B) > P(A) 81. P(An C) P(A) 82
then ((A n B > ((A) - 81 82.
Proof. Notice that P(An n B) > P(A) 81 is equivalent P(A(B) 81. Similarly IP(A o C)
((A) 62 is equivalent to P C) & 62. Therefore,
PA CJ) < P(AB) + P(A.C) & 61 + 82.
Finally, this equivalent to the statement P(AnBoO) > P(A) 81 - 82.
Lemma 3.2. The confidence intervals are valid so that f. E for all I. e N and optimism holds, max fa(ze, & Ue(x(, az) with probability least 1 for all N.
Proof. Applying the results of Proposition settingtng : and σ we conclude that when & holds,
1(+11/ T = T, for i (1, [og(t)]
8
f. fEF: (fl (ze, at) f(ee, ac)) 1 ar 91) TT) & To. 4(i + 1)222
with probability at least P(E,)= 2(+11)2 Recall that
(.(T.)) (((T)) FEF: ((m))((FF)
5 Σ - f(Ie (( at, Ge) < <T) $ 3 To 4(i + ). }
Thus, we conclude that f. e G((T.) with probability at least IPEE)) 5
11 Proposition
D.I and
union bound over all i (0) [qd] we conclude that f. G, for all & N with probability
21

---

Published as a conference paper at ICLR 2025
least PE P( >
5 And therefore P(E P(E,)
6
Finally, since P(E1) 1 conclude that
2:2
2/2
Optimism is immediate consequence of the previous result. When f. 9r, it follows that f.( & max f(z,, a') Ue(xe, a,) for any a A. And therefore maX f. (Z a) < ())
Theorem 3.5. If (0, 1) is the input to Algorithm 7 satisfies,
Regret(T) & O (ov deluder B/T log(T) + B (enntee(FFBBB)))o((())o//(// for all N with probability at least 8.
Proof. The analysis of the regret of Algorithmmoolllo the typical analysis for optimistic algorithms.
When & holds,
Regret(T) (
w(r ars Ge)
(1) O (ov ( deluddo (F/T) log(()//1))) B (F, B/T) (og
Where inequality (i) is consequence of conditioning on & and Lemma 3.2 where optimism holds and follows the same logic as the proof Theorem B.4 The last inequality (fi) follows from Lemma 3.4
We finish the proof by noting that IPEE) d-
E PROOFS OF SECTION 4
In this section we list the proof' of Section These are split in two subsections. In Section E.1 we present the proofs of Section Section
we present the proofs of Section
E. PROOFS OF SECTION
Lemma 4.1. ô (0,1), te N. (22, f-1 be sequence of context-action pairs and and (ra)t=)
be a sequence of values satisfying T2 f. az) ) + &e where f. F and the & are conditionally zero mean. Let {be)i= a filtering process of Bernoulli random variables by {0, 1} such that by is
bi,,,,,,,,,11.. It-1, a--1, 1, 2: a..0a..)mema -measurable. Let f. = argmin fer Ei=1 be
(f(xe, rz)² be the "filtered" least squares estimator. If A'Assumption 2.2 holds then,
Σ E be (f.(zz, f (1))
< 6B3 log((2g
and
Σ bb -
( (a(ee, < 8B2 log(2[F1/0)
with probability at least 1 1-
Proof. Substituting ye = fa f= az) + &e into the definition of fe we obtain the following inequalities,
be If ar) ve)² Σ be- (fr(ze, ve)²
Σ
be
E
substituting again the definition of ye on the left hand side of the inequality above and rearranging terms yields.
Σ be (1e,((s) ar) - fa(x,, az)) <
Σ E be (((eee - -b (xe, at)
(17)
8-1
22

---

of be (E) (ae, az))² and Assumption 2.2 implies | B for Published as a conference paper at ICLR 2025
We now focus bounding the RHS of equation 17 For any f F let Z Ee be (fa ar) - f(ze, at)). The sequence Ze forms a martingale difference sequence such that
2
Ee
2
all E N.
We can use a two sided version of Freedman inequality (see for example Lemma A. in Appendix A to bound this term and show that with probability at least 8
Σ of be (f(xz, f=( log(2/0")
Σ Ee be (f(xe, - f.(xs,
mn-
"
be (f(xz, fo (x)) + 4B² 1og(2/0").
Where inequality (i) follows from setting 1 बा and noting that o2 & B² for all l. Finally, setting 8' Eo and considering union bound over all f E F we conclude that,
be (I-(12, as) - -. (1e, (x2, ar))
Σ be (1e, as) - Sa( ael) 2 +4B² 1og(
$ 4
(18)
Plugging this incquality into equation 13dand and rearranging terms yields,
be (1+h (12, - f. (1e, ae)) log(2)/F1)))
(19)
Moreover, combining equations
18 and
Σ Ee be (I- as) SP (1)) & 6B² log (og(2
Lemma 4.2. Let 8 E 10, be a probability parameter. !f Assumption 2.2 holds.
2 whb 11 log( (og(4))1/)) Wib bw 48 11/(4
with probability at least 1 5 where w E be oz
Proof. This result follows the same template of the proof of Lemma B.I which we reproduce here. Substituting re f.(xe, az) + &e in the definition of Whb,
Wob
be (fa(xe, + & f:b (x1,, at))²
by (Ja(xe, - 1. (xe, az)) + 2 by . Ee (Ja(ze 1 (xe, az)) + by E.
Applying Lemma
we conclude that,
wh. log44
be & w + 20B² log log(4)FF/0).
(20)
with probability at least --//2. Using Proposition A.5 setting B 1/2 and B = B² and Zr by E.
b of - 4B2 1og(2))) <
by
Σ by of + 4B2 log(2/0)
(21)
1-1
23

---

Published as a conference paper at ICLR 2025
with probability at least
8/2. Combining equations 20 and 21 with union bound we conclude,
8 3
-. - log
B 1og(2/8)
& by & ww
1o0 10g(2/0)
with probability at least 8. Thus,
2 W 11B² (0)(
be oî < <2W, 4888 log(4[FF/0)
3
with probability at least 1 8-8.
Corollary 4.3. Let 8' E (0, 1), fxe, ag rel(=1 be sequence of
and rewards triplets
such that re = fa ag) + Ee where J. F and the &e are conditionally zero mean. Lef {be) 1 be a filtering process of Bernoulli random variables by E {0, such that by is Exx,, a1 by T1,
It- ar-1, b 1,- Iz. ag) (e)-mmasurable and l.b. = argmin Ei br (frr,, 0z) - rz) be the "filtered" least squares estimator, Assupptiin 2. holds there exists universal constant C > 0 such
that the cumulative variance estimator Wib.
be (re -/ (xz, az))² satisfies.
f1
W.b - C. B² (og(()))))))) & Whb & 2W + C. B² log(t(F1188)
with probability at least 1 8' for all i e N.
Proof. Applying Lemma 4.1 with 8 8' inequality,
and applying union bound over all E N yields the 2
2
Whb 11B" log(88)) < W < 2w + 48B² (11
3
finally, 48 (log(8((]]))) = θ (1(F1/8)) yields the desired result.
E.2 PROOFS OF SECTION 4.2
Theorem 4.6. Let d E (), 1f is the input to Algorithm 7 and o estimators are computed by
setting 8' 8/2. 1f or = a for all the regret of Algorithm with modified confulence set sizes satisfies,
Regret(T) & O (0v detuder (F, B/T) (/g + Bdoluder (F,B/T) (F,T log (Tg log(T)
for all T E N with probability at least - 8.
Proof. The analysis of the regret of Agorithm[foolowww the typical analysis for optimistic algorithms.
When & holds optimism implies,
Regret
Σ w( at Gc)
In order to bound the right hand side of the inequality above, we split [log(T)) epochs Tj such that T, [25-1 1, min(2?, (2,,7)) T)].
T
[log(2)]
Σ
(xx, ac Gi) &
w(x,, ar, G.)
T5
24

---

Published as a conference paper at ICLR 2025
We proceed to bound the sums LIET, w(ar, de, some j E [[og(T)), it follows that f E Ge then for each threshold level E (0) [qc]
de, 91) for all epochs T, When & holds, and e Ty for
(e) (((x (w[ee, az 96) ri) ReTzn[t-1]
Σ
(zt, - at)) (ww(xe, ae, 9e) $ T,)
8
3
To 2 1)a of
8
B
To 2(i 1)2
2 minn(T))
(4 B, B²)
167 160mmn 1og(1[F1/8)
B log ( (FF/0 log (og(1FF1/8)
O min(r; B²) + o²
t @² min(T,)
where the last inequality follows from noting
that
equation
implies
02 B² 16)
Thus the same argument as in the proof of Lemma 3.3 implies that when holds, for r > mmax((s))
Σ 1wwa ac, Gc) > r) & deluder (F,7) T5
(log(T)/1/0)
a² log(T)F110)
B log" (T(F1/8)
+ +1))
72
72 max (Tz)
in particular, for each T
Σ (=min(T5)
1(w(x, ae. 9v) () < (dchador(FF))
( B [log(T]F111)
o² log(T)FF1/
B log 2 (T (T(F188)
T
T2 - min Ty) + 1)
(22)
For the remainder of the argument we will mimic the proof Lemma d deluder (F, B) and Wi w(re, ae; Ge). We will first order the sequence order, as Wh ... Wor. We have,
3.4
We'll use the notation (wr ) in descending
max(T,)
max(T,)
max(T,) Σ
max(T,) Σ
Σ
Wi
Σ
W/
wh, 1(
B T
Wh 1
B T
(-min(T))
t-min( (T)
t (T)
min
(T,)
ma Σ (T))
B T
Wi, (
>
T
Applying inequality 22 setting F Wi, T
we have that,
t - min(T,) (T,) + +1
(ww Ge) > Wa.)
t (yyin(TT)
B Blog(T]FF//) Wi,
o² log((T) T F1/))
B log (T(FI/0)
O deluner(FF (F,
w
w min(T,) 1)
Therefore,
0²
t - min((n) (T)) + +150
max
Wi,
w V deluder (F, B/B
B o²
< 0
(o max
Wki
w/
25

---

Published as a conference paper at ICLR 2025
Thus, for all T, it follows that,
B
detuder (F, B/TT) log (og())F1100)
Wi, & 0
log( t- min(T,) + +
+
-- mmi(ii()))))))))>)) +
Finally, use this formula over all t Ty for any given j,
0 (Bdeludoec (F,
Σ
wi x0
(o)( log ov (F, (7
finally, summing over all j e [log(7)] we conclude,
T
[log(T)
Wi $ O
Σ
+ oN (F, (Tg
< O
+ oo deluder (F, 1.BB/T)oog((11///111
E.3 PROOFS OF SECTION 4.3
Proposition 4.7. Let ô E (0, 1) and > O. Let (EA/2) be sequence of events such that E Eg...
and E. S E, Let f( f(5.27) be result of solving the uncertainty-
reast-squares objective from equa-
6 Additionally let W. be the filtered estimator of the cumulative variances defined by equation 4 when setling by = (w( ag, 9i) (T, (r,2r] and Wh: == X of 1 (w(x1, oz, 91) E (T, 2r)) There exist universal constants C, C' > O such that the events Wx(T) defined for any
(x az) f.(1e, 1W az, Go) (T,
< C'T w.B. log (f(F1/8) + C'r (1(F1/6)
and Cnrlw log (117118) C'rBlog (115118) & c" d"' W. log (115188) c" 7B BBoog (117118)
satisfy the bound P(E o (M)(T)))))
8
20
Proof. Given f F we consider martingale difference sequence Z/ for & e N defined as,
z = (f(xe, ar) - fa(a,, az)) 1(wlxe, ar, 9 E (r, 2r]) 1(f E 9 &
First let's see that
/ & min(2r B2) V.eN.
To see this we recognize two cases, first when ʃ # 9 in which case zz = 0. When f E G/-- we also recognize two cases. When (ww ae, G/) E (r, 2r]) 0 the random variable 2 0. When f E G/ and w(re, ac. 9)) & 2r, it follows that ag) - f. ax)] | & 2r. Finally since [Ee & B we conclude / & min B²).
The conditional variance of the martingale difference sequence (Z/)e ) is upper bounded
Var, (2/)) = [=(
of 01) - fa(x2, ae)) ( (waar, G) (r,27)) 1( 9
4r2011 03) ( 27]) 1 9
26

---

Published as a conference paper at ICLR 2025
where inequality (i) holds because (f(z - f. az)) [w ae, ()
(T,27l)
1(f
( x 4 Let 6 422
We now invoke Lemma A.4 applied to the martingale difference sequence
(Z/)- ). We conclude that,
(w(x,, ae, 93) [T,2T)) 1(f 9 In 12 2n
12 In 2t'
Σ z 8T
Σ of
+12 In
8,
(23)
8 with probability at least [AT for all t' e N. A union bound implies the same inequality holds
for t' and for all f E F simultaneously with probability at least &z. Let's call this event
Be so that P (B,) 1 1-6 8. We have just shown that P(B,) > 1- 8c. In particular when B, holds, incquality 23 is also satisfied for and f = -(-,2t) When E holds we have ff f((,2r) E G then 1(
9 for all < 1 and therefore,
| (a), Sa fx(22, Er 1waaar, az, 96) (T, (r,)
(24)
We proceed by subtituting the definition of ry = f. (ze, az) + &e in equation and noting that when E holds f. G6-1. that ft p(r.2rl the minimizer of the uncertainty-filltt filtered empirical least squares loss satisfies,
(1 - (xx, - Eb) 1[w(re, ar, G2) E 2T]] & Σ (ww(t, ar, 9r,9%) E (T, 2T])
expanding the left hand side of the inequality above and rearranging terms yields,
( uz) f-(se, az)) 2 [w((re; ur, ") (r,)r)
1-1
(1:200 ae) 1000---(aa f- ai) . Ee (ww(xe, ae, 9) (r, (r, (25)
To bound the right hand side of the inequality above we plug inequality equation 25 to conclude that when B, E holds,
23 (setting t' t) into
L-1
(2n, fx((e, 1(w(o,, (3) (r, $2
1r (x), f.(22, Ee 1ww(xr G) (r, 2r])
167
Σ
oz (w(x as, 93) E (F, .In 12 In
F=1
12.F In 21
24r B In
&
We will call Corollary 4.3 setting 8' = 8 and the filtering indicator variables equal to bj = 1 (w(xe, az, (/ (7, 2r Let's call C, denote the event that
2 W by -C- log( whb
of (w as, ( (T, & 2W +C.B² log(t') F1/6
(26)
'This is where the definition of G. as an intersection of all contidence sets becomes important. The intersection ensures that for any the minimizer of the filtered least squares is achieved at ff for which the inidicator 1f Ge) true for all é & 1.
27

---

Published as a conference paper at ICLR 2025
for all t' e N (and in particular true for t' 1) that P (C,) 1 - 8c. We conclude that for any t N when B, n C. n Eg
(17 (1e, oz) - (=(o,, at))² 1( az, 93 E (T, & / (aw
+C Ba 1og(1171/8)
In 12 In 2
8
24TBIn In 12
5z
0
(TV W log (t(F1/8) +B log (1[F1/6.)
(v
C'Tv/ W log (1F1/88 + C' B log (1(F1/8.)
for some universal constant C > 0 (independent t). Similarly, as a consequence of the LHS of equation 26, for all when B, n C. n E holds,
C'T wh log (115118 C'T log (1F7166 & & <C'TV
TN V
whb log (111/0) + C TB log (ILF188)
for some universal constant C" > (independent of t). We finalize the result by noting that 3
Be B C & = Wi(r) n & and that P(B, o C. E > TP(E))
25: PP(E))
222 and therefore
that P(W)(T) o E) 2 PP(B o C. o E) > P(ε)) 25, = P(E)) 2F Finally, this implies P(Ê o (WL(T))) < 2
Lemma 4.8. Let d E (0, 1). When the confidence sets Gi = F are defined as in Algorithm 2 then f. K. G. so that max fo (x,, a) & Up(x2, as) (optimism holds), and for all i E [q..
(((T)) = (1 E s.t. Σ
( (xe, az) - f(ae, a1) [W[(T,, ae, Ge) E (Ti, 27:]) &
C' T' W. log (2(1 + 11)1(1//))) + C" T. TB log (2621 }.
with probability at least for all t N. Where C" > is the same universal constant as in Proposition 4.7
Proof. Applying Proposition 4.7 with E - E Ti and 2 we conclude that for any [gd].
the event We(T:) satisfies P( ((()((TT) n E7) & क,य A union bound over all i E [4t]. we conclude
that events 3 satisfy,
8
P (( o E & P((M((())) o 8 & 2t
(27)
Notice that when We(T,) Ef holds, f. E ((((T) for i E [9d] And therefore when (Nie(ac) Wi(ss) n
E holds, f. S/ Thus, (Oie(.)) Wi(Ti) n E s E
Define a sequence of events V, as Vo- = Ω (the whole sample space such that PP(V)) 1), V2 Oe (e(aa). Notice that by definition Vi 2 1/2
Notice that f. E 9 = so that ((E) = 1. This combined with (ele()))e(TT)) o g S E
implies nf_n (e((T) = E so that V, S E+₁ for a.
Applying Proposition 4.7 with ε V1-1. r rj and 8 212 we conclude that for any i e [q.] the event W,(T)) satisfies (T)) o Me-1) & मनィ.. A union bound over all E [q.]. we conclude
that events (7s))))) satisfy,
28

---

Published as a conference paper at ICLR 2025
P (((i)) o V--1 & Σ (((M(((:))) o V--1) &
(28)
212
Since V [(Nie(u)) Wi((:)) V-11 u Wi(ss))
Ve-1] we conclude that
8
P (()) > P ((Ove((a)Mi(r))) o Vi-1) - P(V-1) ((nea)))P(( Vy-1) > P(V
2f
(29)
Since P(V)) 1, unrolling incquality 29 implies that for any N,
m
5
IP (Vm) IP (mm's Vmn') > 1
Σ
28
[-1
Thus, taking the limit
we
conclude that 12 V4
holds
with probability at least
lim (1 (1-
-
5 22
8.
Since n 2 ni=z Ve, we also conclude that of holds with probability at least (when Or-1 V. holds).
Thus we conclude that for all i [4]]
C. log (214(/118) + C'T,Bloog (217{
& CC W log (2P11110)) + c" T log (211(F1/6).
(30)
and f. 9 is satisfied for all t N simultaneously with probability at least 1 - 6. Optimism holds because when fa G% (=(x;,a) max [(x,,a) U2(r,, 0z) for all and therefore m La ()) U1( or). Moreover when inequality 30 satisfied,
(((T,) = FFE..t Σ
( (x1, - f(x,, (()) (w(T ae, 9e) E (T,, 27.]) &
C'T.V w/ C'T///.b log (217)/710) + Blog (21t()F1/0) }
fffeFst. Σ ( (x), az) - f(x) [wwax, ae, Ge) e (T, 2r;1) <
c' C'T/W log (2/1 + c" T,Blog (2/2t(F1/0) }.
This finalizes the proof.
Theorem 4.10. Ler T N, E (0,1) and q log(T"). The regret of Algorithm 2 satisfies.
Regret(7 (T)
deluder
F.
F.
B
Σ
T
log(T) log (T)F)/6) Bdeluder
F
B T
log (T) log(T[F1/))
simultaneously for all T e N with probability at least - 8.
Let's condition on g'. When this event holds, optimism ensures the pseudo-regret can be upper bounded by the sum of the widths
Proof.
Regret(T)
w (xe, az G()-
29

---

Wh T Published as a conference paper at ICLR 2025
This is the same argument in the proof of Theorem 3.5
Recall that T2 8. In order to bound the RHS of this inequality, we use the fact that wax ac. F) $ B for all t E N.
T
B B
B
w ( U1, 91) &
Σ
1
w( (w 9i)
29
2
2
2
1=1
T. B
9
Σ
1
(w( (4) E (Tr, 2T.l) 2Ts
29
T
B
+2
Σ
Ti
1 (w(ze) a 94) (Te, 2Til)
29
Lemma 4.9
implies that when El holds,
T
9
T
w(x an 9/
+
Σ
Ti
Σ
(w ar 9iD (Te, 2Til)
29
B
2
Σ
Ö- dedludee((F, Ti)
log ((1 + F1/8+
29
Ti
Č. B
detuder (T)
log ((i+ 1)T(F1/0) + Ō. detuder (F, Ti))
Ti
T
+ 20
Σ (deluder(FF V W log ((i + 1)))
29
B deluder(FFF (F, log ((i+ 1)7( + Tydeluder (F, Ti))
T B 2edetuder
(r
B
W by log ((a + 118)+
i=1
B log ((g 1)T(F1/6)
(31)
Notice that,
W log ((g + 1)8)
b
9
v q log ((g 1)T()1/0)
Σ
W
bij
Σ of
glog ((g F1/()
(32)
where inequality (1) holds because Σ /2, E V4 2 for 21, 24 > Plugging inequal- ity 32 into 31 and using the fact that q log(T)) we conclude that
30

---

Published as a conference paper at ICLR 2025
Bts at, 01) & B++ 2c 2ddeude
(i
B
Σ o
log(T) (log((T) 1)T(+1/8)+
B F.T
B
20 Bdeluder
(T) (og((log([)) 1)T/F//0) + 2 Bdeludr
F.T
B
T
B
0 detuder
T
Σ
of
log(T) log (TFF1/6) Bdeluder
F, (iT) log(T) log (og(T]/F/())
Using the fact that P(E') > 1 finalizes the proof.
F ELUDER LEMMAS
In this section we have compiled all Lemmas that deal with eluder dimension arguments. Lemma 4.9. If [g is the sequence of confidence sets produced by Algorithm ! there exists universal constant C such that when E' is satisfied,
(wi Ges Gi) (T,, 2T.)) &
Ö doludder (F, for all T' E N and e [gr].
log (iT(F1/5) + δ- B datuder (F,
bi Wh
log (iT)))/8) + Ō detuder (F, 73)
ni
T
Proof. For simplicity we'll use the notation = deluder F, FT))
Define 2 {e T s.t. w(ze, ag, Ge) E (T,, 2T.]}.
And in order to refer each of its compo-
nent indices let's write I [TT.2
{er. ((t with l2.... (1
Let N E No (0). We'll start by showing that if [I(r d(N + 1) then there exists an index I [m and pair of functions f( 1(2) Gen such that f( (r ae - 1 al (T, and + non-empty disjoint subsets ",,...,S..., S (ly such that,
1
s!2)
Σ (11, - 1!2) (16, +?
EESy
To prove this result, let's start building the sequence Si,... 3v41 by setting 3, = l, for all
1. 1.... . 11. Let's look at m = N 2....... [Z (7.)) Consider a pair of functions f("l pl2)
km Gim.
such that ((1) (xm, am) - 112) ar TG. If |
(2) > T? for all j = 1, ... N +
Fm
the result follows. Otherwise there exists at least one j such that (((1) (2) s 7.- Thus, we can add e, to 3y-
Finally, by construction, the 3, sets satisfy the definition of eluder ry-independence and therefore they must satisfy |Sy| & d for all j.
This means the process of expanding the sets (5 must "fail" at most after all 3, have elements. Thus 1 d(N + 1) guarantees this will occur.
31

---

Published as a conference paper at ICLR 2025
As have shown, if |Z4 | d(N N + 1), there exists an index [ $1.... SN+1 = {egismm and f.m (2) e Gé.. such that,
disjoint subsets
(N + (1+1)
Σ
1 I 3, & 115
S(( (0,)
(33)
JE[++1]
On the other hand, since
f( Bi S 9%m. (T:), we have that if Ex holds Lemma 4.8 implies.
fm-1
sêm
2
Σ
Imm (111220) (12, as) 1 (oee, az)) (wr ae, 91) [Ti, 27.))
18,35=1
E C
VV\ Whin.. log (216m(F116) CBT,Boog
c T. W log (2PT)771)) C" T; log (27T(F1188
for j {1, Where inequality (i) holds because in & T and because W: is monotonic w.r.t. I for all i E (0) o [g] (recall W. 20 of (w(xz, ae, 92) E [T, 21;))). Therefore when g holds,
1 1 (1,) & 22)5( Sull 2115 _(, (e,) (6,)7-T'
< whi log (2PT) + C T log (2(7)
(34)
For simplicity within the context of this proof let's use the notation
(T( = C" C²
W by
T log (2:71)F1/0) + C' 7BBlog (2/21)71/6).
Thus combining inequalities
33 and 34 we conclude that if N > max (3r
1, 0)
then
7f
T, + 1) 43r 8) and therefore we would incur in a contradiction because
45r(T,0) & (N + 1)7² 15
12 (1 & 48r(T,,
This implies
48r((T;0) 0) ,0 +
27
m d
max
,0)
77
43,(T,,0) 8)
< d
+1
T?
AdC
AdC" B
V W log (212T(F1/8)
log (2: + d
Ti
To
= (Faluder(F,T)) Ti)
B deluder (F Ti)
w log (IT(F1/8) +
log (iT)) + deluder (F, Ts)
T
Since we have shown this result for an arbitrary Te and to prove the result we have only used that T'ss N the result follows.
Lemma 3.3. If Algorithm 7 run with input variance upper bound 0. E is satisfied and (G) is the sequence of confidence sets produced by Algorithm then all T E N and 2 Tgr
[w((re ar (.) > T) & 3 detuder (F,T) (64 (o4
+ 646² log (T Fl(5) +1)
72
32

---

Published as a conference paper at ICLR 2025
Proof. bound.
For simplicity we'll 'll use the notation d = (Fluder(FF,)) r). We'll start by showing the following
Σ (w, at, e (T,27)) < d 64CBlog( log(
64Co² log (T(()
+ +1)
x²
Define z [4 < s.t. w(xe, ae, Ge) E (T, 27]}. And in order to refer to each of its component
indices let's write I 2((-2r] = f41.... ... 4zppaa) } with 4 < l2 ... < l 224
Let N E No u (0). We'll start by showing that if |z) > d(N + 1) then there exists an index [ and a pair of functions 1l.1 s( gr, such that 16.2 (ze,, 0r,) - 1 (2e, ag)) E (T,27)
and N + non-empty disjoint subsets $1, ,NN1 S {E)j such that,
(1)
(2)
Σ E
(Ee, - 1 (1ee, an) > 72.
To prove this result, let's start building the sequence , by setting 3, = , for all j = 1, N 1. Let's look at N 2..... |z| 2. Consider pair of functions 1( ((() Gr... such that (xm am) 11 (sre.. ae...) If 1
(1) stn S. > 72 for all j 1, N 11
12, the result follows. Otherwise there exists at least one such that | Sen 023, < Thus, we can add 6m to 3z.
Finally, by construction, the Sj sets satisfy the definition of eluder -indepeeneence and therefore they must satisfy |Š,| & d for all j.
This means the process of expanding the sets (3 must 'fail' at most after all 3g have elements. Thus when |z| > d(N + 1) guarantees this will occur. Let ? argmin(j s.t. T3 > 27} be the smallest index in the input thresholds for Algorithm I
such that 7; > 2r. Notice that 47 > T..
As we have shown, if | d(N + 1), there exists an index i [ and 12 ! such that,
(2) Ge,
(N+1)72
Σ 15 - 11013, < E15h
((2)
24z 2(
(35)
je[N+1]
On the other hand, since ( 1! Ge. Ge. (T:). we have that
1 = (1 & T s.t. w(xe, Ge) < ET
satisfics 21 < I(77 and therefore,
f/ 2 al 2003 < <15 - 12
+ n18))
(36)
Proposition 3.1 implies
1 - 1
(2)
< 21/5(
11 11
2 0 + +2(l,(())
- (2))
-1(22)
1
1 2
< 43c, (T)
x ())
4- (4 (4min( (T,B, B²) + 160 (og(T(F1/6)
< 4- (4T, B + 16 2) (l/(7
< 64 (TB + 0z) log ( F(6))
when & holds.
33

---

Published as a conference paper at ICLR 2025
Thus combining inequalities
35 and 36 we conclude that if > max
(
1, 0)
then
72
IN + 1) > ( 8) and therefore we would incur in a contradiction because
431 8) E (N + 1)7 < 15h ft. 1 I
< 443r(T, 8).
This implies
(.3T(T7:)) 72
I
max
.0 )
+1
4BT(T;,
+1
72
(4
64 log( (TF(1))1/)) +1)
(37)
x²
Recall that 7j 2- Observe that 1 [[T.To
/
sit1 1(1305-11 We will apply the result
TT equation 37 to each of these quantities and focus on bounding Σ 1/r2055 1] Equation 37 along
with the inequality detuder (F, Tz) d (Fl, for all j < i implies can focus (F
controlling Σ i++ and pi+1
We proceed bound these terms.
7
1
2
2 (2
2
2
2
1)
Tj
To
TO
70
T++1
1=0
similarly
.+1
3+1
(22
Σ
1
1
2
4
2
4
-
220+11
z
2
J-1
7
T0
j=1
T0
j-0
70
3
37
7
i+1
Finally, since r & 7 we have
T+41
2
2
and
$
7z.
Combining these results we conclude that,
(44 64a² log(T)F1/8) +1)
< 3.
72
the result follows
Lemma 3.4. If & holds, then for all T N the uncertainty widths of context-action pairs from Algorithm satisfy.
T
w (x ar, G.) & <0 deledede B/T (TT + (F,
(og(
Proof. For simplicity we'll use the notation d deluder B) and wi w(re, az Ge). We will first order the sequence {w, 17 in descending order, as W; .... W/y. We have,
B wi 1 (wi, > ]
Σ wi, 1(wi, & - )
B B+
B T Wi, 1w
Wt
Wi.
34

---

Published as a conference paper at ICLR 2025
Applying Lemma 3.3
by setting 7 we 7 we have that,
B
T
(w( ae, (e) > wi.)
64C (11
64Co² log (1(11/8)
(eluder(FFws) (F,)
+
-1
Wi. (4CBlogg (T) F1/))
64Co log (T[F)/8)
3 deluder (/I)
+1)
Wi,
W
64CB log (oC FF
64Co² log (T F1
6 deluder (F, B/T))
W1
w
where the removal of the +1 term in step (i) follows because Wi, > B/T. Therefore,
B o²
I 768C detuder (F, B/T) log(T]F1/0) max
Wi, w
This inequality can be used to produce bound for wi, when Wi, > B/T.
B t o vi <
768C doluder (F, B/T) (og(T)FV0))
Wi, 768C deluder (F, B/T) ([g(7))1/6)
t
Since ΣT 1 & (Tg
and
T we have that
B Wi, 1(w, T
1536CBddlnden Bedaudeer FF, B/T) log(T) log(T)F1/8) + ov 1536C detuder (F, B/T) (og(7)F1/0)T
35


Reviews:
[{"review_id": "AHF7guSXbu", "reviewer": "Reviewer_QJSj", "summary": "The paper proposes variance-aware algorithms for contextual bandits with function approximation, with only mean reward realizability assumption for known and unknown variances of noise.", "questions": "1. Could the authors give an overview for the main contribution of the paper?\n2. How the estimation of $\\sigma^2_t$ is possible, especially for the unknown variance?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Solving for varying variance over time period is practical and may yield tighter regret bound in some cases.\n2. The analysis of the variance and the truncated loss has novelty.", "weaknesses": "1. The organization of the paper is hard to follow. The theorems and colloraries are hard to follow since there is no intuitive explanation on the terms (e.g., $\\mathcal{G}_t^\\prime(\\tau_i)$, $\\tilde{\\mathcal{E}_t^\\prime}$ ). It is confusing whether the result mentions either $\\sigma_t=\\sigma$ case or not.  I suggest the authors move the $\\sigma_t =\\sigma$ case to appendix to clearly see the results.\n2. Typos:\n\nIn line 163 $\\mathcal{X} \\times \\mathcal{X} .. $ should be $\\mathcal{X} \\times \\mathcal{A} .. $.\n\nIn Algorithm 1 line 5, $f_t^{\\tau}$ should be $f_t^{\\tau_i}\n\nIn eq. (5), $\\widehat{\\sigma}_t$ should be $\\widehat{\\sigma}_t^2$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ddnEu3sTJM", "reviewer": "Reviewer_Fdz3", "summary": "This paper introduces new regret bounds for contextual bandit problems with function approximation, assuming the realizability condition. The authors build on the framework of optimistic algorithms for contextual bandits, and they also propose new algorithms with improved regret bounds that adapt to the variance of the measurement noise under the eluder dimension.", "questions": "- There is no direct comparison with prior work is provided, making it difficult to clearly assess the improvements or distinctions of these results relative to existing bounds in the literature.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The authors present a study of contextual bandits with function approximation by developing algorithms with variance-dependent regret bounds, marking the first instance of such bounds in this setting. \n- These results improve upon existing bounds by requiring only a realizability assumption on the mean reward function, avoiding stronger, often impractical assumptions on measurement noise.\n- The paper proposes two algorithms with distinct performance guarantees. Algorithm 1 is designed for cases with uniform but unknown measurement noise variance across time steps. This algorithm achieves a sharp dependence on the complexity of the reward function class, measured by the eluder dimension. Algorithm 2 is tailored for scenarios with variable noise variances. Its regret bound scales with the square root of the cumulative noise variance but linearly with the eluder dimension, providing an efficient approach for non-uniform noise settings.", "weaknesses": "However, several aspects of the paper’s presentation and empirical support could be improved:\n- The authors did not include empirical experiments or numerical results to validate the theoretical bounds. This leaves the practical effectiveness of the algorithms untested.\n- The theoretical content is densely packed, with lemmas presented consecutively without sufficient exposition, making it challenging to follow the logical flow of arguments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RHG5GCDa58", "reviewer": "Reviewer_PCBb", "summary": "In this paper, the authors studied the variance-dependent regret bound for contextual bandits with function approximation. They focus on scenarios where the reward function has a bounded eluder dimension. The analysis begins by considering the case where the variance is known. The authors introduce an optimistic least squares approach with multiple layers, where each layer maintains a confidence set using only data points with correspondingly small uncertainty. Combined with a routine that estimates the cumulative variance, they demonstrate that the algorithm can be adapted to the case with unknown variance. This algorithm matches the performance of the linear bandit case with unknown variance. Finally, with a modified filtering method that selects data points where the variance falls within a certain range, they show that their algorithm can be generalized to scenarios where the unknown variance changes.", "questions": "1. Do you think the current regret bound for changed variance is tight?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper studied a variance-dependent regret bound for contextual bandits, which I think is an interesting problem to study.\n\n2. The paper is generally well-written, and the proof appears to be correct.\n\n3. Their regret bound for contextual bandits with unchanged unknown variance matches the results for linear bandits. I think this is a valuable addition to the literature and may have further theoretical impacts.", "weaknesses": "1. Given the variance-dependent regret bound for linear bandits in the literature, it is not surprising that one can obtain a variance-dependent regret bound under general function approximation. Moreover, there is still a $\\sqrt{d}$ factor gap in the general case where variance changes are allowed, compared to the linear setting. I would suggest that the authors highlight the obstacle to removing this gap in the main content.\n\n2. The approach in this paper adapts [Zhao et al., 2023] to the general function approximation case. I would suggest that the authors highlight the technical challenges and the key difference in a specific subsection or paragraph.\n\n3. I am not sure whether the regret bound under changed variance is a significant setting on its own; it appears somewhat artificial. By contrast, the linear bandit case holds practical implications, as demonstrated by [Zhao et al., 2023], where their algorithm is applied to linear mixture MDPs as an example. It would be great to provide motivating examples or potential applications for the changed variance setting.\n\nZhao, Heyang, et al. \"Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dm713f8YBa", "reviewer": "Reviewer_1bL1", "summary": "This work studies the contextual bandit problem under general function approximation with finite eluder dimension. The author proposes a novel algorithm based on the uncertainty-filtered multi-scale least squares procedure and achieves a variance-aware regret guarantee for general function approximation without requiring knowledge of the conditional variance. The regret for the homogeneous case seems near-optimal when reduced to the linear function class, while the regret for inhomogeneous variance has an additional dependency on $\\sqrt{d}$.", "questions": "1. Previous algorithms that achieved second-order regret with homogeneous variance typically relied on a weighted estimator, using either uncertainty weighting [1] or variance weighting [2]. It is interesting to explore how the proposed algorithm can achieve second-order regret without employing any weighting mechanisms, which could be of independent interest.\n\n[1] Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency.\n\n[2] Nearly minimax optimal reinforcement learning for linear mixture markov decision processes\n\n2. For the variance $\\sigma_t$, should it be fixed, or can it be a random variable that depends on the selection of the action?\n\n3. In Line 171, the claim regarding the first algorithm seems incorrect. As mentioned by the author in Line 99, second-order bounds for contextual bandits were already developed in Zhao et al. (2022).\n\n4. For the contextual bandit problem, recently, a new work [3] achieved second-order regret for the dueling bandit case. It would be helpful if the paper provided some discussion on it.\n\n[3] Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1. This work provides the first algorithm with a variance-aware regret guarantee for general function approximation without requiring knowledge of the conditional variance.\n\n2. The second-order regret for the homogeneous case seems near-optimal when reduced to the linear function class.\n\n3. The author proposes a novel uncertainty-filtered multi-scale least squares method, which could be of independent interest.", "weaknesses": "1. Some parts of the presentation are highly confusing, making it difficult to follow.\n\n(1) In Line 264, there is no Propositional 3.2, and Appendix C discusses an existing algorithm with a Hoeffding-type confidence set.\n\n(2) In Line 279, what is the definition of the event E?\n\n(3) In Line 299, what is Algorithm 3?\n\n2. Regarding the regret guarantee, there is a lack of comparison with previous results, making it hard to assess the contribution of the theoretical findings. To my knowledge, the regret for the homogeneous case seems near-optimal when reduced to the linear function class, while the regret for inhomogeneous variance has an additional dependency on $\\sqrt{d}$ . However, more commentary on this point is needed. Additionally, it would be beneficial to compare the regret to that of previous algorithms for general function approximation.\n\n3. The algorithm is highly inefficient. While calculating (threshold) confidence sets is a widely used technique in RL with general function approximation, this work further relies on calculating the intersection of the confidence sets and performing optimization over the intersected confidence set. This may be intractable when the confidence sets are not convex.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)