Eluder dimension: localise it!
Authors: Alireza Bakhtiari
Alex Ayoub
Samuel McLaughlin Robertson
David Janz
Csaba Szepesvari
Venue: NeurIPS 2025 spotlight ()
Keywords: eluder dimension
bandits
reinforcement learning
Primary area: theory

Abstract: We establish a lower bound on the eluder dimension in generalised linear model classes, showing that standard eluder dimension-based analysis cannot lead to first-order regret bounds. To address this, we introduce a localisation method for the eluder dimension; our analysis immediately recovers and improves on classic results for Bernoulli bandits, and allows for the first genuine first-order bounds for finite-horizon reinforcement learning tasks with bounded cumulative returns.

Eluder dimension: localise it!
Alireza Bakhtiari University of Alberta
Alex Ayoub University of Alberta aayoubQualberta. ca
Samuel Robertson University of Alberta
baakhtia@ualbertaa ca
amrobert@ualbertar ca
David Janz University Oxford david. jandsttats ac. uk
Csaba Szepesvári University of Alberta szepesva@ualberta. ca
Abstract
We establish a lower bound on the eluder dimension generalised linear model classes, showing that standard eluder dimension-based analysis cannot lead to first-order regret bounds. To address this, we introduce a localisation method for the eluder dimension; our analysis immediately recovers and improves classic results for Bernoulli bandits, and allows for the first genuine finst-order bounds for finite-horizon reinforcement learning tasks with bounded cumulative returns.
Introduction
We study decision-making problems where the regret admits first-order (small-cost) bound of the form
Rs S (nn(a, IIn +
with r7(a,) the optimal mean per-round cost and I,, I, instance and model dependent complexities.
The challenge in obtaining first-order bounds in how we measure the complexity of the task. The (global) eluder dimension (Russo and Van Roy, 2013) provide worst-case guarantees, but, as we shall argue, it ignores the local structure of the problem: analyses based on the global eluder dimension often introduce factor in In that scales like a per- step worst-case information/curratuur parameter (denoted s),, which cancels out m)(a,) ) and destroys first-order gains. This subtle issue is present in much of the previous work on first-order bounds.
standard complexity measure used to
reiteiionnrestrretinng We show that by localising the eluder dimension restricting it to a small neighbourhood of the optimal model-these terms be moved into the lower-order I', term. This tightens the link between exploration and the actual difficulty of the instance and yields genuinely first-order bounds.
Our contributions may be summarised as follows:
1. Localised f eieuuderr dimension. We define localised fe-eluder dimension (in the sense of Liu et al., 2022) over a small-excess-lor neighbourhood, which avoids the ş dependency in the classic generalised linear bandit setting (Filippi al., 2010; Faury et al., 2020).
2. Necessity of localisation. We prove lower bounds showing that the global é and fz-eluder dimensions (Russo and Van Roy, 2013; Liu al., 2022) must scale with in the generalised linear setting, and that this negates small-cost or variance-dependent improvements.
3. Stochastic bandits. We propose a version-space optimistic algorithm, É-UCB, which takes a loss and builds confidence sets for the cost function. Under (a) bounded loss, (b) Bernstein variance condition, and (c) triangle condition (Foster and Krishnamurthy. 2021), f-UCB achieves small-cost bound using analysis based on our localised eluder dimension.
4. Reinforcement learning. We extend our method to online RL, giving l- E-GOLF, and obtain the first x-free first-order regret bound for finite-horizon RL with bounded rewards/costs.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.1 Related work
Small-cost in bandits. Adversarial small-cost bounds are known (Neu, 2015; Allen- et al., 2018; Foster and Krishnamurthy, 2021; Ito et al., 2020; Olkhovskaya et al., 2023). However, adversarial algorithms are often conservative stochastic regimes (Lattimore and Szepesvári. 2020, Ch. 18) and do not transfer cleanly to reinforcement learning, where optimism (Lai and Robbins, 1985) remains central for low regret (Ayoub et al., 2020; Weisz al., 2023; Wu et al., 2025; Moulin et al., 2025).
In stochastic bandits, first-order bounds typically assume distributional knowledge (e.g., noise/cost models) (Abeille et al., 2021; Faury al., 2022; Janz et al., 2024; Liu et al., 2024; Lee et al., 2024). We consider stochastic bandits with function approximation and wnknown bounded cost distributions, aligning with adversarial-style uncertainty but in stochastic environment.
Small-cost in reinforcement learning. Online first-order bounds have been shown by Wang et al. (2023) with the (strong) distributional Bellman completeness assumption. This assumption then removed by Ayoub et al. (2024). but in the offline setting: Wang et al. (2024) extended this result back to the online setting. However, by relying the global eluder dimension, Wang al. (2023, 2024) suffer a (hidden) k-dependence in the leading term that undermines first-order gains.
bounds help when the optimal reward is small (Jin et al., 2020; Wagenmaker et al., 2022); this is very different from the cost-firstordder guarantees we target (our results actually hold for both small-cost and small-reward settings). Small- cost results have been previously shown in structured settings such as tabular Markov decision processes (Lee et al., 2020) and Emear-quadratie regulators (Kakade al., 2020).
cost-firstoordrr
Instance-optimad exploration. Pure-exploration studies instance-dependee sample complexity, with notable works including policy-difference estimation for tabular reinforcement learning (Narang et al., 2024) and PEDEL for linear function approximation (Wagenmaker and Jamieson, 2022). The algorithm-agnostic lower bounds of AI-Marjani et al. (2022) show that PEDEL is near instance- optimal for tabular MDPs. These works are complementary to our regret-focused results.
Background on generalised linear models & loss functions
We collect the notation and standing assumptions for generalised linear models (GLMs) and losses used throughout. Fix a dimension d E N., and let A, e C Rd be closed sets. Let U C R be a closed interval and let μ U + [0. 1] be increasing. The GLM class with link μ and parameter set θ is
GL, θ) {a + pl(a, 0j): a R 0 E O (a, 0) E EU}.
We also consider losses É: [0, x [0, 1 + R. where l(y, f) evaluates prediction á against an outcome y. The next assumption records the structural conditions on (A, θ μu, E) used in our analysis; the final condition is satisfied when É is the negative log-likelihood of the GLM associated with μ.
Assumption 1. We make the following assumptions:
AC B
(action set bound)
(38 >0 0)
θ C SB
(parameter set bound)
(V(a,)) 0) E Ax 0)
(a,0) E U
(valid domain)
(AI. 0, Yu, v' EU)
In(u) - -uul)) S T.uu - w/1
(T--Lipschitz link)
(3M > 1, Vu E U*) (31 k <0)
[i(n)] S Mii(u)
(M-self-concordaal link)
K 2 sup 1//((u)
(link derivative lower bound)
nett
(Ay E 10. 11, Vu U)
8gl(y. (())) p(u) y -y
(link and loss are compatible)
Remark 1. The requirement that M, K 2 1 in Assumption is there solely to simplify our bounds.
Examples of loss and link combinations that satisfy our assumptions include the log-loss with the sigmoid link function and the Poisson loss with the exponential link function:
Example 1. The los-loss function (v. p) = y log p (1 - -y) log(1 - -)) together with the sigmoid
link function px: S-S,S) S. S]= -> [0, 1] given by u + 11(1 + e e-") satisfies Assumption I with I, 1/4,
M = 1 and k 5

---

Algorithm the Ł-UCB bandit algorithm
input loss function e, model nonnegative, nondecreasing confidence widths (3e)221 for time-step t E N do let Fi be the subset of the model given by
t-1 EAY..AA))) & inf JEr i=1
t-1 Σ ((Y.,(AA)) +
F F== 1=IIER:
IEF:
compute an optimistic function fo Fe and action A, that satisfy fx(A)) f(a), V(f.a) FxAA
and play action A, end for
Example 2. The Poisson loss function (y.pp) p y log p together with the exponential link function pp: [-S,0] > [0, 1] given by u u+ e" satisfies Assumption with L M and k = es.
Bandits with bounded costs and the (-UCB algorithm
Our bandit setting comprises set of actions A and corresponding set of action oetion-dependent cost distributions P = [Pa: a E A} supported on the interval [o, 1] (we will write supp P for the support of measure P). At each round N learner selects action A, A and receives cost Y, ~ PA,- We measure the learner's performance over n E N+ rounds by the n-step regret
/ UPa(dy) and a, E arg min n7a). dEA
Rn = Σ ((A)) - n(a.) where 17: 7:a+
The learner may base its choice of A, on the past observations A1, Y, A Y any extra randomness independent of the observations (say, for tie-breaking), and prior knowledge the form of model class: set F of functions A - [0, 1] known contain n). The key assumptions here Assumption (Bounded costs). We have UsEA supp Pa C [0,
Assumption (Realisability). We have that r) E E.F.
Algorithm Our algorithm, 2-UCB (Algorithm 1) is an implementation of optimism with empirical risk minimisation--ase confidence intervals.
At each time-step t E N+. the algorithm constructs a confidence set F, for r) composed functions in F for which the empirical risk under the loss function L: (0, 1] [0, R does not exceed that of the empirical risk minimiser by more than fe, where (3:) is woolemm-dpendent nonnegative, nondecreasing sequence of confidence widths. The algorithm then computes optimistic function- action pair (fr. At) E F, x A such that
fe(At) S f(a), V(f.)) EF
and plays A.. Optimising over F, is difficult without further assumptions. In Appendix detail a standard convex relaxation of this optimisation problem applicable to self-concordant models.
The crucial component to the f-UCB algorithm obtaining small-cost adaptivity is the right choice of the loss function f used to construct the confidence intervals (and well-chosen confidence widths, based on the loss function and model class), Our requirements will be stated in the form of an assumption on the offset versions the loss functions, and their expectations, which are defined thus:
Definition 1. Let F be model class and &: [o. 1] x [o, 1] + R. loss function. For each f E F, we define the excess loss ; : [0, 1] A R and expected excess loss f R2
(y a) = f(y, (a)) (a)) and 8,(()) = 5. al(.a)dPa
We will write &(F) :,p;: f F) and ((F)
{ f e F} for the respective loss classes.
3

---

Let A: [0,1] x [0. + R4 be the triangular discrimination function given by
-) otherwise.
A(0,0) 0 and (p, 9)
+
Assumption 4 (Loss function assumptions). There exist constants 6, > 0 such that for all (f.a) F x A. letting Y ~ Pa. the following three bounds hold:
los(Y, a)) S b a.s.
(bounded loss)
Var par S cFf(a), A(S(a), S (9)(1))
(variance condition) (triangle condition)
The first two conditions in Assumption 4, boundedness and the variance condition, allow for Bernstein-type concentration on the excess loss class. The triangle condition is used in the regret decomposition to move from fast concentration to small-cost bounds. The conditions in Assumption implicitly depend 1), and thus ought to hold uniformly for all 17 E FF. Recall our two losses:
Log-loss satisfies the triangle condition with 7 = 2 (Proposition 20); for any f E F such that ||مy bl 6, yy satisfies the variance condition with
+ 4 (Proposition 16).
Poisson loss satisfies the triangle condition with = 5 (Proposition 21); for any f E F such that || S yy satisfies the variance condition with 6+ (Proposition 17).
The squared loss function fails to satisfy the triangle condition; Theorem 2 of Foster and Krish- namurthy (2021) shows that squared loss cannot lead to the small-cost bounds seek.
4 The localised eluder dimension & first-order regret bounds for bandits
We define the (global) L fleludeer dimension of Liu et al. (2022) as follows; we will henceforth refer to this quantity the eluder dimension, forgoing the l quantifier. Definition (Bluder dimension). Let 2 be a set and be a class of real-valued functions on 2, and let (21, -2,-..-. in) be a length sequence in 2. We define the following:
1. We say x E Z is e-independent of with respect to vi if there exists a e E such that Σ (+x))
and (x)) > E.
2. We say that is E-eluder sequence with respect to v if for all S z is s-independent 21...., with respect to V.
3. The e-eluder dimension dimelua (e; V) of V the length n the longest w-eluder sequence with respect to V for any w 2
Remark 2. The el-edr dimension at scale E of a function class is equivalent to the & fi-eluder dimension of the function class {z + x2)) 1 E Vi at scale e². We think of the ( ei-luderr dimension as loss-agnostic, whereas of the lz-eluder dimension as baking in the squared loss.
Our upcoming regret bound will require the choice of a localised model class F F. and will depend on through the following two quantities:
1. The eluder dimension of (FF),, the expected excess loss class induced by the localised model class.
2. The number of time-steps N+ for which the optimistic function ft is not within the localised set F
The localised eluder dimension will feature in the leading term; by taking F' small, we can make it independent of k. Taking F' small may increase the second term, the number of optimistic functions falling outside of FF. but this contributes to the regret an additive term only.
Theorem 1 (Regret bound for f-UCB in bandits). Fix E (0, 1), E N bandit instance P. model class F and loss function f. Suppose that (P,F, satisfy Assumptions' 1 1/n- i/n-covering number of (F)) with respect to the uniform metric, and for each E N let
Let N₂, denote the
3 = 15(b + c) hre(N where h, = log +t..

---

Let F C. F. and denote by dn the 1/n-eluder dimension of (FF). Define
In = 7(1 (d, + +]6 + 4d,, log(1 + xb)).
Suppose a learner uses Algorithm 1, L-UCB, over the course of n-many interactions with P. with model class F. loss function and confidence widths (3:)(21- Then, with probability at least 6,
Rn S 33/nn((,) 6T, + card S J1 F
The proof of Theorem is located Appendix D.
Remark 3. The localised model class F' does not need to chosen to run the algorithm. The regret of the algorithu scales automatically with the best possible choice of F' The localised eluder dimension does not need to be computed to run the algorithm; is an analysis-only quantity.
Remark The covering number Nn, featuring in the confidence widths (3t)121 does not depend on K; the confidence widths themselves thus do not bring in any k dependence.
4.1 Why localisation matters: eluder dimension lower bound for generalised linear models
The dependence the s-eluder dimension of (FF) will be our focus; this be thought of as measuring the number of times we are 'surprised' at the scale e > 0, in that there was a model E F' with low expected excess loss on past inputs that has high expected excess loss on some unseen action. The following lower bound shows that it is vital to only consider 'surprises' near a..
Theorem 2 (GLM & éiceluder dimension lower bound). Let (p, E) satisfy the last four properties of Assumption 1 (link L-Lipschitz, M ---eeff-ooncordant,, link-derivative lower bound, and link fink-loss compatibility). Fix S 2 4/M and assume that [-5,0] 0] CU. Write
ji(0)
R
00,
= min[[[]],d
2/1(-S/2)
Then, there exist A C B and θ c SB such that (A, θ, E) satisfy Assumption 1 and for every S (2M²) the eluder dimension of the expected excess-loss class (FF) with = GLM(p, satisfies
d-1
exp min (6
log(R)²
dim (E; ((F))
4b
16 8SM2 + 4log
for a sequence of actions taking values A.
The proof of Theorem 2 is given in Appendix G.
The quantity > can be thought of the ratio of the information gain in the middle of the parameter set and that at large step in the negative direction; in common GLMs, R = K.
Corollary 3. Consider the setting of Theorem 2 with the log-loss lx and the sigmoid link function μun)= = 1/(1 ") Then, M = 1 and ja(0) 1/4. Therefore, for S > 4, d 2 2 and any & S 1/8, the e-eluder dimension of (GLLM(,, Q)) exceeds d-1 (b/3300) where b min [ 1).
4b
The corollary follows by substituting the relevant quantities into Theorem 2; the proof is omitted.
To understand the implications of Theorem 2, consider the setting of logistic bandits in the usual low-information regime, where 0.) x SS; think clickthrough rates in online advertising, where even the best adverts rarely get clicked on. Then r7(a,) RJ i((a",000 R exp(-S), which suggests that our regret should be excellent; but at the same time = exp(S), and thus the eluder dimension scales as exp(S). completely cancelling out the benefit of the (a,)) small-cost term. This results in bound that fails to truly adapt to the problem instance. We now show how localisation helps.
4.2 Regret upper bound with localisation for the generalised linear model setting
We now instantiate Theorem I for generalised linear models; see Appendix F.3 for the relevant proofs.
Consider the GLM setting. For any f. let 0, O be such that fr(-) p((:; 0.)). For any 0, let
e' (0 O: Va A, (a 0 0.) 5r}
5

---

be the r-localised set of parameters and define the corresponding raapoddiing-llllllli r-localised model class
F((r) = (u((-,)) 0 ('()).
The eluder dimension of (r)) can be upper- upper-bounded bounded function of as follows:
Proposition Let Assumption 1 hold. Then, there exists universal constant C such that for any r > O, the e-eluder dimension of (FF((r)) (r)) is bounded as
dimetud (e; (FF( & cd L Lexp(r-M)ee).
+
In the above bound, taking S we end up with an e dependence, which is an upper bound on (up constant factors; the upper bound is tight in the logistic setting). However, localising /M neighbourhood, we instead obtain bound for the e-eluder dimension of o (F((1))) of
dimatua tb (FF & Cdlog(1 + L²
Localisation thus allows for first-order bounds where the effect of ji(a)) is not overshadowed by The cost this 1/M-localisation terms of the additive term in the regret is bounded as follows: Proposition Under Assumption I, on the high-probabilityy event of Theorem 1, for any n E N
card (1 n: ((,, 0. 0.)l 1/M3 S 64dxM22 9n log (1 (64/3) M
That this additive term depends is to be expected: all algorithms for generalised linear models without x in the leading term have such an additive dependence (Abeille et al., 2021). (Note, our bound depends the sequence A1..... An rather than holding for all actions this is fine.)
Using the bounds of Propositions 4 and 5, we obtain the following specialisation of Theorem 1:
Proposition (Regret for {-UCB with the logistic model). Let 8 (0, S 0 and N Consider the setting of Theorem 1, with the model class J = GLM(H, θ) where plu) = 1/(1+e-")) and the logistic loss function Ex. Consider running t-UCB with confidence widths (8))N given by
Bt= 5/2 + 60(2S + lo + 8Sn) + log(h./6)].
h4 = c log(1 + tt.
Then, for constant C' 0, with probability least 6, the resulting regret satisfies the bound
Rn S CC/nm(a.)dd log(1 + Sn) + Cd3,, [log(1 + Sn))² + 2 doog(1 + [xn]]
The same result of Proposition also holds, up to constant factors, for the Poisson model; each log-loss specific result used in the proof of Proposition has a Poisson equivalent in Appendix C.
Observe that the regret bound of Proposition 6 holds Importantly, we do not assume that the rewards are generated by a generalised linear model. However, much of the literature does make that assumption, make comparisons in that setting.
Assumptions 1 to 3 are met.
4.3 Discussion in the logistic bandit & maximum likelihood estimation settings
The maximum likelihood estimation (MLE) setting is the well-studied setting where the costs are sampled from known generalised linear model (one might also call this 'well-specified" setting).
special case the MLE setting with bounded rewards is the logistic bandit setting. Here, 7) given by a generalised linear model with the sigmoid link function and the responses are given by
Y ~ ((rrnoull(r)(AA)))) for each E N
In this setting, the leading term in the regret bound of Proposition 6 nearly matches the lower bound given by Abeille et al. (2021), which states that there exists a C > 0 such that
R2 2 Cdv/no(a.) where v(a.) (1 r)(a.))
Likewise, Proposition 6 almost matches the upper bounds of Faury et al. (2022) for their logistic- bandit-specific algorithm, which guarantee that for some > 0, with probability at least - 6,
Rn CSd CSd log(n//)) + CS dx(log(n/8))).

---

The suboptimality of Proposition 6 here is in that it depends on n7(a.), providing only small-cost bound, rather than on 8² (a.); the latter allows for a simultaneous small-cost and small-reward bound. This is because Proposition 6 only assumes that the triangle condition is met one side of the reward interval, and so only allows for small-cost bounds; strengthening the assumption to be two-sided (which is satisfied by the logistic model) would allow us to recover the v(a.). (We do not do this, as it would rule out, for example, the Poisson GLM, which only gives small-cost bounds.)
Interestingly, while Faury et al. (2022) only consider the logistic bandit setting, their analysis actually shows a regret bound for the wider bounded reward setting. The distinction between our work and that of Faury et al. (2022) is that where we use an analysis-on oonly localisation technique to move x to an additive term, Faury al. (2022) use an explicit algorithmic warm-up uu procedure to do this. That is, they run an approximation of an optimal design at the start of interaction, until their confidence sets have shrunk to a neighbourhood of the true parameter (on the good event where the confidence sets do indeed contain the true parameter). The change from algorithmic localisation to analysis-only localisation vital for the upcoming reinforcement learning setting where, because we do not have random access stale-action pairs, the solving of optimal design is not feasible.
The works of Lee et al. (2024) and Emmenegger et al. (2024) also do away with the warm-up employed in Faury et al. (2022), using techniques based on likelihood ratios. However, they rely on their likelihood ratios forming a martingale, which restricts the results the MLE setting.
Remark 5 (Bernoulissaioon.. Any algorithm that yields first-order regret for the logistic setting can be used to obtain first-order regret for the bounded reward setting using Bernoullisation, The trick is thus: for each time-step E N4, upon observing Y, [0, 11, we sample
Y! Bernoulli(Y.)
and feed Y to the algorithm A. Since the conditional means of Y, and Y! the same, first- order properties are preserved. Bernoullisation, however, destroys any second-order adaptivity of the algorithm. Indeed, consider the case where the (Yt)ten, Then, running empirical loss minimisation with the log-loss on (Yi)tEN, converges to 1/2 after single observation, but running the same procedure on the corresponding sequence (Y(),e,, of independent Bernoulli(1/2) random variables leads an 1211// abxolute error in the estimate.
equal 1/2 almost surely.
First-order regret bounds for online reinforcement learning
We consider the episodic reinforcement learning setting with horizon H E N,. Let M (S,A, c. P. 81) be a Markov decision process (MDP) with states S, actions A, a cost function (cI. ... CHH) with C+: S x A [0, 1]. deterministic starting state 81 E S, and transition kernel p= (P) (PI...., PH) with Pa mapping from S x A to probability measures over S.
The learner interacts with the MDP M for N episodes. At the start of each episode t E [n]] the learner specifies deterministic policy मं = ( :fr)), where .ी. S - A for each h E [H]. We allow the policy x¹ to depend on the states, actions and costs observed prior to the start of the tth episode, but not on the cost function c or the dynamics P, as these are assumed to be unknown.
The learner's 's aim will be to minimise the expected cumulative cost incurred over the episodes. To formalise this, let og be the value function of policy æ in M, given by
(s) =E, Σ cS,, (S:)) Sh
for each E S, where E. S s] denotes the expectation with respect the states Sh...., ., SH induced by following the policy π in the MDP M starting at S₁ = s. Then, letting vi. := 0% (h [H], the ne-eisode regret is given by
Rn (( -
Faury et al. (2022) also propose an online data data-rejection procedure that can be used instead of a warm-up. This is, however, again, algorithmic tool, in contrast to analysis-only approach.
7

---

Algorithm 2 The Ł-GOLF algorithm
input loss function e, models F and nonnegative confidence widths (3,),
for episode t E N do for each h E [ let
:-1
(1
( (h))
and let F be the subset of F given by
F FEF: (f S inf C (fh+1, + 3r, Ah the [m]]
gEth
compute an optimistic function
fr
arg min fi Ty (s1))
fEF
and play the policy x² = n greedy with respect to end for
where vi (h E [H]) is the optimal value function, defined formally just after Eq. (1).
The key assumption that our learner will be allowed to exploit is the following: Assumption 5. Costs are nonnegative and sum to at most one over each episode.
5.1 Preliminaries on Q-tunctions, Bellman optimality operators and greedy policies
Let Q be the of all maps Sx A [0, 1 For E Q, we write qu for the map (s, + ()(s, (entry h of q(s, a)), and we write &² for the function S + [0, 1] defined by
(8)) min yn (8,a). for all a E S and E [M]. asA
For convenience, we may augment each with 9H+1 = O, to reflect the standard boundary condition. We let T Q denote the Bellman optimality operator for the MDP M, given by
T:q+et ct / / dP,
/P,
where, with slight abuse of notation, the integral is to be understood as with respect to the product P = P1 x... PH. We define the optimal action-value function q" for M to be the element of Q satisfying
Tq 9" and define the value function v* for M to be 2² = gra
(1)
For any function 9 E Q. we write Λ" for the policy greedy with respect to q. defined by
(s) E arg min (s(ss)) a) for all E S and h E [H).
aEA
5.2 The f-GOLF algorithm, model and loss assumptions & regret bound
Our Ł-GOLF algorithm (Algorithm 2) an extension of é-UCB to the episodic online reinforcement learning setting, generalising the GOLF algorithm of Jin et al. (2021) to arbitrary loss functions (GOLF is recovered by taking E to be the squared loss). The algorithm requires the specification of loss function E: [0, 1 + R, confidence widths (B<)se(n) and function classes G,F C Q. The model F contains candidate functions for estimating q², and the model G contains candidates for estimating Tf for E F. We will use the following two assumptions of Antos et al. (2008):
Assumption 6 (Realisability). We assume that q" F.
Assumption 7 (Generalised completeness). We assume that TF C. G.

---

The algorithm proceeds to, in each episode t E N.. construct confidence set F C F containing action-valle functions that are close satisfying the Bellman optimality condition f f= f on the data observed thus far, with errors penalised according to l. It then selects an optimistic function I' F, and plays the policy x² = n' greedy with respect to f". Our analysis will use the following: Definition 3. For any Q, h E [H], S x A and s' E S, we let
v (5, + (cx(x) (h+)(s')
be the response under the model f. For (f.g) E G. we define the excess Bellman loss function (x, s') = ( (z, s'), 9h (x)) - E(v) (z, (Tf))(())))
and the expected excess Bellman loss function
xx) (x,,
We write () and (F, for the classes of excess and expected excess Bellman losses.
Our assumptions on the loss function here mirror those the bandit setting:
Assumption 8 (RL loss function assumptions). There exist constants b, 7 such that for all
(J,9) F x G, E [M]. x E x A. S (r) the following hold:
"x, s a.s.
(RL boundedness)
Var o (z. 8*) S (x)) (T
(RL variance condition)
Tpp (x).
(RL triangle condition)
Our main result is captured by the following theorem. Note, the eluder complexity defined therein is equivalent to an E version of the Bellman eluder dimension of Jin al. (2021).
Theorem 7. Fix E 1), E N., MDP M, model classes F and 9 and loss function É. Suppose that (M,F,9, G,E) satisfy Assumptions 6 8. Let ht = E + log(1 1) for each & E [n), let Nv, be the 1/n-covering number of the function class & (FF,9) with respect to the uniform metric. and let
Be = 5/2 + 15(b + c) log(N,
t t E
Let F C. F, and define Z to be the of functions (8 A) + R mapping
H x H Σ
fo (Ia) ph
for some f E F
Let Py denote the state-action occupancy measure (S x A)" induced by the interconnection of M and the policy greedy with respect to f E FF, and let V be the family of functionals on Z mapping
2 2+ zdP, for each f E F
Let du denote the 1/n-eluder dimension of V. Define
In (1==((1= (dn, + 1)b d, log(1 + nb)).
Suppose a learner uses Algorithm 2, E-GOLF, over the course of n-many episodes with M, with model classes F and G. loss function &l and confidence widths (BE)LEN
Then, with probability at least the learner's 's regret is bounded as
Rm S3 3 (s) 6HT,, + cardft S n: S FEFF
Theorem is established Appendix E. For context, the closest results ours are those of Wang et al. (2023, 2024) for online RL. Both provide a small-cost regret bound scaling with the Bellman eluder dimension; however, without our notion of localised dimension, their regret bound scales with in the leading term for logistic linear models. This entirely offsets any benefit of their small-cost analysis; the bound is not truly instance-adaptive. Moreover, Wang et (2023) assumes that the distributional Bellman operator (Bellemare et al., 2017) lies in their model class, an assumption that significantly stronger than our Assumption 7 (as discussed Ayoub al., 2024). argument for extending the results from costs to rewards was given in Ayoub et al. (2025).

---

Conclusion
We have shown that standard eluder dimension analysis inherently fails achieve first-order regret bounds in generalised linear model settings. By introducing the localised & f-ellderr dimension, we overcome this limitation, removing problematic worst-case dependencies and achieving genuinely adaptive, first-order regret bounds. Our refined analysis recovers and sharpens classical results in Bernoulli bandit scenarios and demonstrates clear practical advantages through the (-UCB algorithm.
Moreover, our localisation approach successfully extends to via the Ł-GOLF algorithm, providing the first genuine first-order regret bounds in this setting. This highlights the crucial role of localisation techniques in developing instance-adaptive algorithms, opening promising avenues for further exploration in broader learning contexts.
reinforcement learning
Acknowledgements
Alex Ayoub gratefully acknowledges funding from Netflix. Csaba Szepesvári gratefully acknowledges funding from the Canada CIFAR AI Chairs Program, Amii, NSERC and Netflix.
References
M. Abeille, L. Faury and C. Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, 2021.
Z. Allen-Zhu, S. Bubeck and Y. Li. Make the minority great again: First-order regret bound for contextual bandits. In International Conference on Machine Learning, 2018.
A. Antos, C. Szepesvári and R. Munos. Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 2008
A. Ayoub, Z. Jia, C. Szepesvári, M. Wang and L. Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, 2020.
A. Ayoub, D. Szepesvári, A. Bakhtiari, C. Szepesvári and D. Schuurmans. Rectifying Regression in Reinforcement Learning. In Reinforcement Learning Conference, 2025.
A. Ayoub, K. Wang, V. Liu, S. Robertson, Mclnemey, D. Liang, N. Kallus and C. Szepesvári. Switching the Loss Reduces the Cost in Batch Reinforcement Learning. In International Conference on Machine Learning, 2024.
M. G. Bellemare, W. Dabney and R. Munos. A distributional perspective on reinforcement learning. In International Conference on Machine Learning, 2017.
S. Boucheron, G. Lugosi and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
S. Dong, T. Ma and B. Van Roy. On the performance of Thompson sampling on logistic bandits. In Conference on Learning Theory, 2019.
S. S. Du, S. M. Kakade, R. Wang and L. Yang. a Good Representation Sufficient for Sample Efficient Reinforcement Learning? In International Conference on Learning Representations, 2020.
N. Emmenegger, M. Mutny and A. Krause. Likelihood ratio confidence sets for sequential decision- making. Advances in Neural Information Processing Systems, 2024.
T. Erven, P. Grünwald, M. D. Reid and R. C. Williamson. Mixability in Statistical Learning. In Advances in Neural Information Processing Systems, 2012.
L. Faury, M. Abeille, C. Calauzènes and O. Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, 2020.
I. Faury, M. Abeille, K.-S. Jun and C. Calauzènes. Jointly Efficient and Optimal Algorithms for Logistic Bandits. In International Conference on Artificial Intelligence and Statistics, 2022.
10

---

S. Filippi, O. Cappe. A. Garivier and C. Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems. 2010.
D. J. Foster and A. Krishnamurthy, Efficient first-order contextual bandits: prediction, allocation, and triangular discrimination. Advances in Neural Information Processing Systems, 2021.
S. Ito, S. Hirahara, T. Soma and Y. Yoshida. Tight first-and second-order regret bounds for adversarial linear bandits. Advances in Neural Information Processing Systems, 2020.
D. Janz, S. Liu, A. Ayoub and C. Szepesvári. Exploration via linearly perturbed loss minimisation. In International Conference on Artificial Intelligence and Statistics, 2024.
C. Jin, A. Krishnamurthy, M. Simchowitz and T. Yu. Reward-free exploration for reinforcement learning, In International Conference on Machine Learning, 2020.
C. Jin, Q. Liu and S. Miryoosefi. Bellman eluder dimension: rich classes of RL problems, and sample-efficien algorithms. Advances in Neural Information Processing Systems, 2021.
S. Kakade, A. Krishnamurthy, K. Lowrey, M. Ohnishi and W. Sun. Information theoretic regret bounds for online nonlinear control. In Advances in Neural Information Processing Systems, 2020.
T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 1985.
T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
C.-W. Lee, H. Luo, C.-Y. Wei and M. Zhang. Bias no more: High-probability data-dependent regret bounds for adversarial bandits and MDPs. In Advances in Neural Information Processing Systems, 2020.
Lee, S.-Y. Yun and K.-S. Jun. A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits. In Conference on Neural Information Processing Systems, 2024.
Q. Liu, A. Chung, C. Szepesvári and C. Jin. When is partially observable reinforcement learning not scary? In Conference on Learning Theory, 2022.
Liu, A. Ayoub, F. Sentenac, X. Tan and Szepesvári. Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits. In Advances in Neural Information Processing Systems, 2024.
A. Al-Marjani, A. Tirinzoni and Kaufmann. Towards instance-optimality in online PAC reinforce- ment learning. In Advances in Neural Information Processing Systems, 2022.
A. Moulin, G. Neu and L. Viano. Optimistically Optimistic Exploration for Provably Efficient Horizon Reinforcement and Imitation Learning. In Conference on Learning Theory, 2025.
A. Narang, A. Wagenmaker, L. Ratliff and K. G. Jamieson. Sample complexity reduction via policy difference estimation in tabular reinforcement learning. In Advances in Neural Information Processing Systems, 2024.
G. Neu. First-order regret bounds for combinatorial semi-bandits. In Conference Learning Theory, 2015.
J. Olkhovskaya, J. Mayo, T. van Erven, G. Neu and C.-Y. Wei. First- and Second-Order Bounds for Adversarial Linear Contextual Bandits. In Advances in Neural Information Processing Systems, 2023.
Y. Polyanskiy and Y. Wu, Information Theory: From Coding to Learning. Cambridge University Press, 2025.
D. Russo and B. Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, 2013.
T. Sun and Q Tran-Dinh. Generalized self-concordant functions: a recipe for Newton-type methods. Mathematical Programming, 2019.

---

R. Vershynin. High digenssiien probabiliry: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
A. Wagenmaker and K. G. Jamieson. Instance-dependent near-optimal policy identification in linear MDPs via online experiment design. In Advances in Neural Information Processing Systems, 2022.
A. J. Wagenmaker, Y. Chen, M. Simchowitz, S. Du and K. Jamieson. First-order regret in reinforce- ment learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, 2022.
K. Wang, N. Kallus and W. Sun. The central role of the loss function in reinforcement learning. arXiv preprint arXiv:2409. 12799, 2024.
K. Wang, K. Zhou, R. Wu, N. Kallus and W. Sun. The benefits of being distributional: Small-loss bounds for reinforcement learning. In Advances in Neural Information Processing Systems, 2023.
G. Weisz, A. György and C. Szepesvári. Online RL in Linearly q" RRealizzae MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore. In Advances in Neural Information Processing Systems, 2023.
J. Whitehouse, 7. S. Wu and A. Ramdas. Time-uniform self-normalized concentration for vector- valued processes. arXiv preprint arXiv:2310.09100, 2023.
R. Wu, A. Sekhari, A. Krishnamurthy and W. Sun. Computationally efficient RL under linear Bellman completeness for deterministic dynamics. International Conference on Learning Representations, 2025.
12

---

Appendices
Self-concordance & convex relaxation
14
B A uniform Bernstein concentration inequality
15
Analysis of the log-loss and Poisson loss functions
17
C.1 Establishing the variance condition
17
C.2 Establishing the triangle condition
18
Proof of the cost-sensitive regret bound in the bandit setting, Theorem
20
E Proof of RL cost-sensitive regret bound, Theorem 7
23
On self-concordant GLMs with compatible losses
27
F.1 Boundedness of excess losses & covering number bound
27
F2 Rogue steps bound and the localised eluder dimension
................................
28
F3 Regret bound for Ł-UCB with the logistic model
G Proof of lower bound on the eluder dimension in GLMs, Theorem 2
32
13

---

A Self-concordance & convex relaxation
Take a parametric model class == [fo: 0 } where & R is convex parameter set satisfying |00|| I 5 for all 0 E O for some S> 0. Let C R. For any (y, a) be given by 0 > fo))). Consider the following coffrooncod assumption.
A. let (g.aa) Rd
R
Assumption 9 (Seff-concordance of losses). Assume that for all a E y x A, lg is convex and thrice differentiable. Moreover, assume that there exists an M 0 such that for all z E E A, O (the interior of the convex set θ) and u, E R.,,
(0),, MM
where (0) E Raxd denotes the third directional derivative of Eg at in the direction evaluated at 8, and (0) E Rddd is a matrix of the second order partial derivatives of lg evaluated at 9.
In particular, the generalised linear models introduced in Example and Example self-concordant (Faury et al., 2020; Lee et al., 2024). As shown in Janz et al. (2024), Assumption equivalent to requiring that [i(x)) I M jı(x) for all æ in the domain of μ., which holds for these GLMs. Moreover, recent result by Liu et al. (2024) shows that many GLMs satisfy Assumption 9.
M 1
Let (0) = Σ ((Y;, fo(A.) be the empirical risk for a parameter E @ on the first t - 1
observations, and 0, θ be an ERM. Consider the confidence sets of the form
e 10 θ: (,) (..) S Be), 3r > 0, & NN.
These can be enclosed within ellipsoid as follows. Theorem 8, Under Assumption 9, for all t N+,
O C (0 O: 10 0.1 S 221++5M)8.)
We provide a proof for completeness, but this result is well known (see, for example, Lee et al., 2024).
Lemma 9 (Proposition 10 of Sun and Tran-Dinh (2019)). Let g(x) exp(a)) For any 0, 0' O
under Assumption 9,
M 0'))2) 110 0' o' S -. (.(') 0¹)
S S - 0'))2) 22) 110 0'
Proof Theorem 8. From Lemma 9, and observing that since O2 is ERM and θ is convex, (VL,(0.), 0 - 0z) is nonnegative for any 0 O, we have that for any 0 E O,
M 0.112) |10 0. 0. S -
-
Using that exp(x)=a-1 - whenever S 0, bounding ||0 - 0.112 S 28 and staring the result
z²
a little ought to convince the reader of the veracity of the claim.
14

---

B A uniform Bernstein concentration inequality
The following uniform Bernstein inequality, proven over the course of this section, will be needed prove both the bandit and the reinforcement learning regret bounds. It is the use of this incquality that necessitates the variance condition and boundedness condition for the excess loss classes.
Theorem 10 (Uniform Bernstein inequality). Let Z be set, (Zz); be Z-valued process adapted to a filtration (Fe),, and & set of real-valued functions on Z. Assume that:
1. For some b > 0, for all ip ④, t E N+, [B(((Z) Fr-1] (2,2) S b.
2. For some > 0, for all ip & and I N_. Var(pp(Z)) Fr-1) S (El Fr-1].
Let (0, 1), E E> and let N be the E-covering number of 4 in the uniform metric. For any E No, define
B(n, 0,, N) 5ng
15(b (og((
where hn e log(1 + n). Then, with probability at least for all y and n E N+.
Elp(Z)) Fr-1] 2
Σ ((,) + 28
To prove Theorem 10, will need the following definitions and results:
Definition (CGF-like). We say twice differentiable function &/ [0, Amax) + R.+ is CGF-like if strictly convex, (0) v (0) 0 and (0) exists.
Definition 5 (sub-& process). Let F be filtration, v [0, Amax) + R4 be CGF-like function and let (St), and (Vt)r. be respectively R-valued and R4-vulued F-adapted processes. We say that (Se, Vi). is a sub-uá process if, for every X [0, Amax), there exists an F-adapted supermartingale L(A) such that
M,(A) == eXS (AjVV) < L,A) almost surely for all t 0.
Definition 6 (Sub-gamma process). We say that a random process (Se, Vt), is sub-gamma with parameter 0 > 0 if it is sub-a/ for the CGF-like function uh: 10,) R4+ mapping À + -x-
X²
Theorem 11 (Sub-gamma concentration). For a sub- uub-gamma process (S,, Vt), with parameter c > and any 0 and d E (0, 1), with probability least 1- 6, for all 2 1,
S, < 4v V2 log( (, + 11(c+ + p) log(H1/8)) where H; log(1 + Velp²) te.
Theorem 11 is consequence of Theorem 3.1 of Whitehouse et al. (2023); we will prove it shortly.
Proposition 12. Let F be a filtration and let X be martingale with respect to F, satisfying X. < E[X,
F. Fr-1] + for all E N Then, for
S = Σ X, E F--1l and V1 Σ Var(X, |
iml
the process (S,, Vi)tEN, sub sub-gamma with parameter b/3.
Proof of Proposition 12. If the random variables X (Xe)sen are independent, the result follows directly from Theorem 2010 (Bernstein's inequality) in Boucheron et al. (2013) combined with the discussion immediately after Corollary 2.11 therein. For the martingale result, use the tower property of the conditional expectation to extend the independent case.
Proof of Theorem 10. We will write E,-1 and Var.-1 1 to denote F, -ron-condiiional expectation and variance operators, respectively. Now let (<)) C o be a uniform E-cover of with cardinality N. Then for any &p & there exists some & E (E)), such that for any n E N
E. (Y()) ((Y.)) < 2ne + Σ E. (X)) (Y,)
15

---

Now observe that for any & E (()), from Proposition 12 and our assumptions on D we have that
Σ E, E - (()), Σ Var;-1 ((x))
rEN,
is sub-gamma process with parameter 6/3. Applying Theorem 11 with and confidence parameter 8/N, and taking union bound over the N functions in ((e), we conclude that with probability at least 1 - 6,
446
Σ E, 100) ((6)) S 4, Var, (Y)) log((N,.)))) +
Oog(Nhn/0)
3
where we have upper bounded the H,, therein, defined as in Theorem 11, by hn + log(1 + n). Next, by the variance condition and Young's 's inequality,
E. ( Sclog(Nhn/O))
2
We arrive at the desired result by bounding E,-1 S + combinnn this with the previous inequalities and bounding the constants slightly for convenience.
We now prove Theorem 11, which an application of the following result:
Theorem 13 (Theorem 3.1, Whitehouse et al. (2023)). Let (St, Vi)120 be sub-ip process for CGF-like function &b [0, c) - R+ satisfying limxte (A) = cc. Let > 1, 3 > 0, ó E (0, 1)
and let h RR + R+ be an increasing function such that > MEN 1/h(k) S Define the function Eg R + RR by
(œ(v) - log (1ok.c
(VVS) (
+ log (
where, for breviry, we have suppressed the dependence of Eg on (a, 5, h). Then
( (s(i)) ) < 88
P 3120: S. (V. (1)))-
a
V.
where 3 is the convex conjugate of vh.
Proof of Theorem 11. The result follows from applying Theorem 13 to our sub-gamma process with
= e, 3 = p² and h(k) = (k + e)2, and bounding the result crudely. In particular, for our choices of a and h, we have the bound
e0 (V.) log(log(p VV, 1) e)² log 1/5 < log(((og( + +) log(H./8))
Now, since for our choice of th, (1) = 2 + Ic, the bound from Theorem 13 can be further bounded
(V. (V
a V. ( (o()))
20 ()) (2) ecl
22/e(V. log H1 (ecloo s 22 H1/ + 2(v ce) (og(H,
where the final inequality that for a, > 0, vavb Va+b Va vb and that since log(Ht, (l)/)) 2 Vlog(Hl./5) < lo)(Hl:/o).
16

---

C Analysis of the log-loss and Poisson loss functions
For convenience, restate loss function conditions:
Assumption 4 (Loss function assumptions). There exist constants b, 7 >> such that for all (J,a) E F x A, letting Y ~ Pa. the following three bounds hold:
aY) I a.s.
(bounded loss)
Va I cpf(a), A(f(a), (())) & (P)(a).
(variance condition)
(triangle condition)
We now establish that the variance condition and triangle condition hold for the log-loss excess loss class @x induced by the loss function εx and the Poisson loss excess loss class Dp induced by Cp.
C.1
Establishing the variance condition
For our proof of the variance condition, we will assume that all yp E 4x U pp satisfy the pointwise bound
1 b.
This being satisfied relies on the choice of the model class F. In Appendix F.1, we will verify that for a compatible GL.M with parameter norm > O, the boundedness condition holds with = 45.
To establish the variance condition, we will use the following result of Erven et al. (2012), and in particular special case stated and proven immediately afterwards.
Lemma 14 (Lemma 10, Erven et al. (2012)). Let g(x) = (e" x - 1)/2² for x # 0 and g = 1/2.
and let X be random variable satisfying |X| S. b. Then, for all t 0, there exists a C. 2 9 such that
{ Ee xx) GIEX2
EX
Lemma 15. Suppose that X a random variable satisfying
1. Boundedness: |X| < < oo; and
2. Stochastic mixability: Elexp(-X/2) I 1.
Then, Var < +b+ 4)EX.
Proof of Lemma 15. Applying Lemma 14, with 1/2, obtain that there exists C 2 ((--((/)) such that
C
EX² > g( g(-B/2) EX²
EX 2(1 Ee x/3) + Ex² 2 2
2
2
The result follows by using the numerical inequality 9(x) 2 1/(2 z) that holds for all æ S 0; that EX² 2 Var for every random variable with a finite variance; and rearranging.
We are now ready prove the variance condition for the log-loss and Poisson loss functions. Proposition 16 (Log-loss variance condition). Every y E 4x uniformly bounded by b satisfies the variance condition with constant e = + 4.
Proof. The result follows from Lemma 15 combined with that every & E 4x is stochastically mixable, which we establish now. Observe that every to E Φx is of the form
((a) log TT(a)
s(a) 1-9
ply. a) log
17(a)
for some E F. Therefore, for fixed a, letting Y Pa with E (a)), we have
y
-
f(a)
f(a)
Eexp(_<((V.o/22 E
17(a)
i 77a)
Y
[(a)
1 E
s(a) 1
(aa)
2
1- (a))
where the inequality follows by the application of AM-GM.

---

Proposition 17 (Poisson loss variance condition). Every E Dp uniformly bounded by b > 0 satisfies the variance condition with b+
Proof. We establish that for every y 4p. 2, is stochastically mixable. The result then follows
from Lemma 15, after looking at how each side of the variance condition scales with the change o ++ 2p. Observe that every yp E @p is of the form
f(a)
y
av, -(r(a) f(a)) log
17(a)
for some E F. Thus, for a fixed a, letting ~ Pa with E|y] = n((a), we have
(I(a)
Eexp(-<(YY,a) = exp(n(a) cxp((((
f(a)) E
(((a)
Now, noting that for any x and E [0, 1]. by convexity, x.' S xy y.
f(a) n(a))
'
< f(a) Y
E
+1 - B|Y = 1+ 1 f(a) - ((a) z (xp([(a)-1(a))
((a
(1+ E" for all r E R)
Combining with the previous display, have that
<
C.2 Establishing the triangle condition
To establish the triangle condition, first sandwich A with easier-to-work-with quantity: Lemma 18. For any p. q [0, 1..
(vp Va < (p. 9) - ~
Proof. If p. q 0 the statement is trivial. Assume that one of p and is nonzero. Using the algebraic identity (a (a b) a² 6², we have
(Vp+ V (VD-v)) (p (p- 9)²
Rearranging the above display gives the lower bound:
(vp - (p 9)²
(p 9)²
S
(p.q).
(vp va)
p+q
For the upper bound, note that
(p 9) p +
(p 9)² (/D q42
A q)
2
2(V2 2
We will also need the following relation between the squared Hellinger distance and Bellbackk-eiblee divergence, which appears Equation 7.33 in Polyanskiy and Wu (2025).
Proposition 19. For any measures P, Q on the same measurable space with densities p and with respect to some common dominating measure
KL(QIP) 2 log, e H2(P,Q) where H) (o00P):=/WW-- -V d..
We are now ready to prove that the log-loss and Poisson loss functions satisfy the triangle condition. Proposition 20 (Log-loss triangle condition). The expected excess log-loss class &x satisfies the triangle condition with constant 2/ log.(e).
18

---

Proof. Let Q, P be Bernoulli distributions with parameters E [0, 1] and E (0, respectively, and recall that
(), = (Vp Va + (V1 p v 2)2
and that
= 2 + (1 q) log 1
-
Using Lemma 18, the definition of H² and Proposition 19, we have that
(p),)) 2(v7- V s 2 P) (2/ log2 (L)
We conclude by observing that for any random variable Y E [0, 1] with mean y
( E Y log +1 Y) 1 KL(Q))))
p
Proposition 21 (Poisson loss triangle condition). The expected excess Poisson loss class Pp satisfies the triangle condition with constant 7 = 4v/e/ logz(e).
Proof. Let Q, P. be Poisson distributions with parameters q, E [0, 1] and p (0, 1] respectively, and recall that
H) expl-eexp(-VV (V)) and KL(QIIP) = p q 1lo ! p
Observe that for all x E 10, we have the numerical inequality
1-e x
(2)
Hence,
A(p,g) S 2((DD- v4)2
(Lemma 18)
44ve(1 - expl- (opp-(V0-- /21)
(Eq. (2))
=4Velf(Q,
(definition of H²)
4Ve KL(
(Proposition 19)
logz(e)
Now, observe that for any random variable Y E [0, 1] with EY q
E((p(Y,p) (x(Y,))) = E q Y log g
[L
p
19

---

D Proof of the cost-sensitive regret bound in the bandit setting, Theorem 1
Recall the following assumptions, and the statement of Theorem which we shall now prove. Assumption 2 (Bounded costs). We have A Pa C [0,
Assumption (Realisabilityy. We have that 1) E F.F.
Definition 1. Let FF be model class and & [0, 1] x [0. 1] + R. loss function. For each f F, we define the excess loss yp; [0, 1] x + R and expected excess loss V - R. as
Py(y, a) = (()) ((y)((a) and Gz(a)= = ps(l,a)Paa.
We will write $(F) f,p; f E F) and ((F) (Fy: f E F) for the respective loss classes. Assumption 4 (Loss function assumptions). There exist constants b, > O such that for all (J,a) E x A, letting Y ~ Pa. the following three bounds hold:
(o,((, a)l S bb..s.
(bounded loss)
(Y, Var (Y S cFf(a).
(variance condition)
(af (()) S (9)(a).
(triangle condition)
Theorem 1 (Regret bound for Ł-UCB in bandits). Fix 10. E N+ bandit instance P. model class F and loss function Suppose that (P,F, satisfy Assumptions to 4. Let N,, denote the 1/n-covering number of (F) with respect to the uniform metric, and for each E N let
3: = 5/2 + (5 + c) Log(N, where = e t).
Let F F, and denote by d, the 1 1/n-eluder dimension of ((F)). Define T = 71 + (dn, + 1)b 4d log(1 + +b))..
Suppose a learner uses Algorithm 1, LUUC, over the course of n-many interactions with P. with model class F. loss function and confidence widths (3.)e21- Then, with probability least 6,
Rn S m//n(a,)T, + 6T, + card (t S n: ft F').
Proof of Theorem 1. Our proof will rely on Theorem 10, the uniform Bernstein inequality established Appendix B.
Validity of confidence sequence Let F be the filtration given by F, = o YI..... Ar. Y,, A for each E N. We apply our uniform Bernstein inequality (Theorem 10) to the F-adapted process (Y,, Ad)EN, with the function class & = { f F} and the choice s = 1/n (the two requirements in Theorem 10 are satisfied due the boundedness and variance condition parts of Assumption 4). From this, we conclude the first part of the following proposition:
Proposition 22. There exists an event & satisfying P(Es) 2 whereon, for all F and t e N
Σ ((() 2 Σ 4, (Y, A.) + 23,
(3)
Moreover, on Es,
7e E n Fe. IEN+
Proof. The second conclusion of Proposition 22, that on Es, 1) E Fr, is not immediate. For this, observe that the left-hand side of Eq. (3) is nonnegative (as ensured by the triangle condition of Assumption 4), we conclude that on Es, for all E N
0 S inf Σ (Y,, jEr
A,)
((Y..)(A))) < inf Σ ((,,)(AA)) + Bc. JEr
Comparing the right-hand side of the above implication with the form of our confidence set F, yields the second conclusion.
20

---

Per-step regref bound Bounding the per-step regret will use the following simple inequality for the triangle discrimination, based on an inequality of Ayoub al. (2024).
Lemma 23. For x, y, 2 > 0 with y S 2, we have that x S 3v (1 v) 62)x.))) v).
Lemma 24 (Ayoub et al. (2024)). For 2, 2 0, I 3r + (ar,
Proof of Lemma 23. Observe that
h-2Wa-y y
(by assumption) (defn. A y))
I V + VV ( y)
$ 4r A y) (zz
(Lemma 24)
- 2 x3 Ø 8) + AZ 8)
(4)
Hence, applying Young's 's inequality, we obtain the inequality
x - 2 ( A c
- + 3A +
which yields that x < 6Zx v) + 22; using this and Eq. (4) gives
2/ 64 y) 22) (xx v) + Azx
We finish by applying va Va+b< 5 vā
vb for a, b 2 0 the above, and bounding constants.
We now apply Lemma 23 to bound per-step regret. For this, note that on Es, for any E N4, by definition of the pair (fi, Ar) and since 17 E Fr, we have
fx(A,) S (Ar)..
Hence, may apply Lemma 23 with 7) y fa(A,) and ((a,) obtain the bound + (A():(A)), m(A)))
= nAA) na(a)) S 33)
(5)
Regret decomposition Let I, (t (n n: fe
F`) and observe that the maximal per-step regret bounded by 1, by Assumption 2. Thus, for any N
R Σ S
Σ ri + card([n] \ 4.)
IET,
Using Eq. (5), Cauchy-Schward and that card I, S we have that on Es.
Σn
rs
3
mn(aa) Σ ((A) + Σ (((()) BETn
TET.
Bounding the triangles
The result will be complete once we establish that for all n E N
Σ A(f((A)), n(A:)) Tn.
To this end, we first use the triangle condition of Assumption 4 to obtain
Σ A(f((A)), (AA)) S Σ (A)) TET.
TET.
Now, consider carefully the following proposition from Liu et al. (2022), and the lemma thereafter, which shall allow apply the proposition to bound the above sum:
Proposition 25 (Proposition 21, Liu et al. (2022)). Let X be a set and v a set real-alued on X. Suppose that the functions in Vi uniformly bounded by some B > 0. Let 1h...... Vn be sequence in and Iı,... In a sequence in X, such that for some 3 > 0, for all S n. ve(x.)) S 3. Then, for all w > and S n.
Σ vi(a,) (d 1)B + d3 log(1 + B/w) tw
where d is the w-Eluder dimension of V.
21

---

Proposition 26. On the event Eg of Proposition 22, we have that for all t E N
9r, (A.) S 43c
With Proposition 26, for any E N+, we may apply Proposition 25 with 3 := 43nr = 1/n, and with the upper bound from Assumption 4, conclude that on Es.
Y E 7(d,, + 1)6 4d, log(1 nb) + nn
tE
This concludes the proof Theorem 1.
Proof of Proposition 26. On &g, for any t E N
Σ
(1,)
p. (A.)
(by the triangle condition, & is nonnegative)
i
1=1
2 2
94 94, (Y, A.) - Be
(on Eg Eq. (3) holds)
2
((A.)((A))
E(Y,, (A.)) +Bs
2
Σ
((Y),)(AA)
inf jer
Σ
(Yy f(A:)) Be
(on &s, 17 E Fi)
< 48,.
(fi E F and the definition of Fi)
22

---

E Proof of RL cost-sensitive regret bound, Theorem 7
Recall the following assumptions, and the statement of Theorem which we shall now prove. Assumption 5. Costs nonnegative and sum at most Assumption (Realisabilityy. We assume that q² F.F.
each episode.
Assumption (Generalised completeness). We assume that TJ C Definition 3. For any Q, HI, E A and s' S, we let
uh: (x, + (cx(2) (s'))
be the response under the model f. For (5.9) E F G. we define the excess Bellman loss function
" ( (z, 9n)) ( s') (T5)(z))
and the expected excess Bellman loss function
(x) = 4 o ddP(
We write (FF,9) and 9) for the classes of excess and expected excess Bellman losses.
Assumption 8 (RL loss function assumptions). There exist constants b, c, > such that for all
(J.g) E G. [H]. 8 A. S Pa (x), the following hold: F
(p, S') s bas..
(RL boundedness)
Var 2/ (x, (z.S') 8*) S cp/i (z). ((fa(t). S Tp!. (z).
(RL variance condition)
(RL triangle condition)
Theorem 7. Fix ò E (0, E N+, MDP M, model classes F and G and loss function &. Suppose that (M, satisfy Assumptions 6 8. Let h4 = + log(1 + t) for each [n), let N,, be the 1/n-covering number of the function class (FF,9) () with respect to the uniform metric, and let
5/2 + 15(b + c) log(Nnhr/8)), L LEN+.
Let F C. F. and define Z to be the set of functions (S A)" + R mapping
Ph 6o5 (xx)
for some f F
P=
Let Py denote the state-action occupancy measure (S x A)" induced by the interconnection of M and the policy greedy with respect to f E F, and let W be the family of functionals on Z mapping
/ zdP, for each f E F'
2 2
Let dn denote the 1/n-eluder dimension of V. Define
=n=7(1+ (dn + 1)b dn log(1 + nb)).
Suppose a learner uses Algorithmm E-GOLF, over the course of n-many episodes with M, with model classes F and G. loss function & and confidence widths (32).EN..
Then, with probability at least
8, the learner's 's regret is bounded
Rn < 3 (s)) 6HH,, cardft n: f
Within the upcoming proofs, we will use the shorthand
x
Proof of Theorem 7. Our proof will rely on Theorem 10, the uniform Bernstein inequality of Ap- pendix B. The structure of the proof is broadly the same that of our bandit result, Theorem 1.
23

---

Validity of the confidence sequence For each h E [H], let FA = -FF))ENN_ be the filtration given by
F = o s X X for each & E N.
Now for each h [H], we apply uniform Bernstein inequality (Theorem 10) the F₁, Pn-adepted process ((X), 1)EEN with the function class 4, { (f.g) (Fx g)) and with 1/n.
From this, we conclude the first part of the following proposition:
Proposition 27. There exists an event Eg satisfying P(Es) 2 1- whereon, for all (f.g) E (FUg)² t t N+ and h E [H]
Σ Pk od
(X))
2 Σ
f Ph
(X,, S 23r.
(6)
Moreover, on Eg,
q- F t5n
Proof. The second conclusion of Proposition 27, that on Es, q" E DiEN_ is not immediate. For that, fix some [H]. Now, observe that the left-hand side of Eq. (6) is nonnegative (as ensured by the RL triangle condition of Assumption 8). Hence, on &g. for all t E N+.
0 < inf gEg
o 2 S Br: Ph
which implies that
Eeluh (X), St 1) (Tq)),
S inf gEd
Σ
Uo S1 + Sr.
Comparing the above inequality with the form of our confidence set F. yields that Es, we have that 9* E Nisn Ft, as desired.
Let In = ft < n: fo E F}} and observe that the maximal per-step regret is bounded by 1, by Assumption 5. Then,
E(((S)) -(S)))-((3) vi
- u(()) card([n] Ln).
IET.
We bound only the regret on episodes t E In- For this, we observe that on 8 9" E Fi (Propos- ition 27). Thus, we can apply our inequality on the triangular discrimination, Lemma 23, with x v((()). - ((())).==(((6 (Si) and z (S)), to obtain
Σ - S Σ (v/ +6 Σ A (c((S))) I.
tel.
teLn
Lemma 28 (Contraction Lemma). Let f E F, and let म := n5 and v = v.. Then,
(()) < h=1
E. (UAA(X))
where Ex denotes the expectation over the state-action pairs (X H policy n in the MDP M.
resulting from following the
We prove Lemma 28 presently. Now, let E,,, denote the expectation over trajectories generated by n' in M, with dummy integration variables (X and let A == (TF)(
24

---

Observe that
Σ ((((s))rr((())))(())) - Σ
(i
tETn.
2
(i(()) A +
Σ
E Den
(Lemma 28)
LEI, h=1
IEIn
1=1
H
H Aeh CCauchy-Schwarpe card I, S n)
S 3
(SI) Σ
E
A + 6H
Σ
E
NET, A=1
tET, h=
Now, from the triangle condition, we have that
ΣΣ E S
STEEEN LET,
E E
of' (x1),
(7)
tETn
and it remains to upper bound the right-hand side by our complexity measure T. For this, consider the following result that bounds the cumulative expected excess risk past observations.
Lemma 29. On Es, for all E N4, E [H).
(Xi) Σ 4h of (X²) S 43:.
Proof. By Proposition 27, Es.
Σ of (X)) s > ph (X) Sh41) 23,.
Now, let g" denote an element of G attaining the infimum in the definition of F (for convenience. suppose that this exists; otherwise, the argument goes through by introducing an approximate minimiser). Then.
Ef Σ vh (X), Sh41) (X,,
Sh+).
Σ Shan))
(X), 1) (xx))
Sh
(using that fr F and the definition of g" and Ft) Σ (X,, S (X Ely" (X)
(using the definition of gf as the empirical risk minimiser over and that TF G)
This completes the proof of Lemma 29.
Combining the result in the thus established Lemma 29 with the usual cluder dimension argument of Proposition 25, with 1/n and the upper bound b from Assumption 8, we obtain that T,, is indeed an upper bound on the right-hand side of (7).
We now move prove the contraction lemma, Lemma 28. We will need the following simple result, which follows from the joint convexity of (a, y) + fry for x,, y 2 0.
Lemma 30. For I, y 2 0, the map (I, v) + (Vz / is jointly convex in its arguments.
25

---

Proof of Lemma 28. Let for each h E [H], let μu, denote the joint distribution of (Sh, (Sr)) when following the policy и, and let I-I1p,, denote the L2 (Pn) norm.
To start with, by Lemma 18, we have that
(S, ((1)). Us (Si)) = 2l viilpa
We shall shortly establish the inequality
(4h [m]) lIv Vuallma IIV Vifillm +1lvsh+1 Uh+ 1pnes
(8)
where we interpret
[ /HH+I|MNTT = 0. Unrolling this over h = 1,.... H, we obtain
H
IIV - Vill S
> IIV fullaa
h=1
The result follows from applying the other side of Lemma 18 to the terms above. We now establish Eq. (8). Fix h E [H]. By the triangle inequality,
I Vun lan. S llv VTflllm IIV Veallm. The first term is of the form want. For the second term, have
IIVThh Ven 1pm =
= ||1
(00++(nndeeg (nnidP())
|/ M
V/ (atidP())
Sl dP()
Mb
(Ve,a, 0. vc+ S lva vb)
$ ll futi - 00++ilmmat
(Jensen's 's justified by Lemma 30)
This establishes Eq. (8), and with it the lemma.
26

---

On self-concordant GLMs with compatible losses
We restate compatible GLM assumption for convenience.
Assumption 1. We make the following assumplions:
A C BB
(action set bound)
23800)
C SB;
(parameter set bound)
(v(a, 0) E A 0)
(a, EU
(valid domain)
(3L > 0, Yu, u' EU)
lu(u) - -m(u') S Llu-ai - ='
LL (L-Lipschitz link)
(3M 2 1, Vu 400
[i(μ)] I Mij(u)
AMf-self-coonee link)
51 5
x2 sup 1/jí(u) uEti
(link derivative lower bound)
(Vy E [0, 11, Vu U)
u(w)) u(u) - y
(link and loss are compatible)
In this section, we prove that the following hold under Assumption 1:
1. the excess loss class (FF is uniformly bounded and admits rather small uniform cover
2. that for a suitable localised model class F C F, the number of rogue steps under our f-UCB algorithm is bounded
3. the localised expected excess loss class (FF)) has a small eluder dimension
These results combined with Theorem yield Proposition 6. We will use the following lemma repeatedly.
Lemma 31. Fix some (y, E [0, 1] B and let h(O) - ely, e(y,u((a,0))), Let 0,0' e Rd and write (tt) = t0 + (1 t)6'. Then,
(a(0())dt-aah(01) h(0) 100') [( ash(0(1))dt = 0,h(0') + 2 S (1 1)0Ph(((4))dd
where
0.h(O(1)) (u((a, () 0 0'), and (L(((()) = (a((a, (aa) 0'),0 0¹)
Proof sketch. The proof follows from the fundamental theorem of calculus for the first equality, and then Taylor expansion followed by another application of the fundamental theorem of calculus for the second equality. The absolute continuity requisite for the fundamental theorem of calculus is ensured by the L-Lipschitz continuity of the link function for the first application, and by the second derivative of the loss being bounded, which may be seen from its form, combined with L being an upper bound on ju()) for all u E U
F1 Boundedness of exeess losses & covering number bound
We first establish the boundedness of the excess risk class with 6 = 48, which is implied from the following proposition together with our realisability assumption:
Lemma 32. Let (9, (,,A, p, E) be compatible according Assumption 1. Then, for all 0,0' e O and (y,a) E [0.1] x A.
|e 0)) Ely. (((a
2|10- - 0'll < 45.
Proof. Let 0(1) 10 (1 1)0' and note that for any (v, [0, x A, by Lemma 31,
((),,u((a, 0))) - E(y. p((a, 03))- - L (u((a, ((t))) () 0 8')
(u((a,0(1)) v)de 1(a, 0 0')1
2|10 0'11
27

---

Now we establish a bound on the corresponding uniform covering number:
Proposition 33. Under Assumption I, the E-covering number of ((GLM(H4, Q)) with respect to the uniform norm is upper bounded by (1 + 8S/e)".
Proof. Write F = GLM(H, θ). Let 0. E θ be such that r7(a) = u((aa, 0.)) (such parameter exists by Assumption 3, realisability) and define the map p: + (FF as that taking each 0 E θ to the map
(y, + f(y, pl 8))) - Ely, m(a)).
Observe that (FF p()), and that since for any 0g, 01 O,
(lp(0o) p(01))l = sup (v.e)E(o.1IxA
[e u( bo)) e(y, 01))
we have by Lemma 32 that / 2-Lipschitz as a map from (9, (1.11-11) - (C(F)),l-lle) Now, Cef2 is an e/2-cover of (SB3) I1-)12), then by said 2-Lipschitzness, p(C=/2) is an e-external-cover of (+F), ll.))o)). Finally, the 2-norm e e/4-covering number of SBş is an upper bound on the e/ e/2-covering number of @ (Vershynin, 2018, Exercise 4.2.9), and the former quantity is at most (1 + 85/e)/ (Vershynin, 2018, Corollary 4.2.13).
F.2 Rogue steps bound and the localised eluder dimension
In the following, we associate with each function fe selected by the f-UCB algorithm parameter 0, E θ such that f+(-) = m((: 0,)), and localise the GLM to the function class
F [u(( 0)): O'} for O' {0 O: Va A, 0 0.) s 1/M3.
By realisability, we can write any & E ((GLM(H, θ)) in the form
p(a) - f (() u((x, 0. =: ()a, for some 0,0, e SB
Lemma 34. For any 0 Rd,, letting 0(1) 10 + (1 1..0 1 [0, 1}, have that
1 1e 0 where a(a.0) ( (1 ()(((a,((t))))
p(a. 0) 2
Moreover, there exists real number ((a, 0) E (()) [0, 1]} such that
jd((a, 0)) a(a
Proof. By Lemma 31, for any (y, a) E [0, 1] x B
1 ((,, 0))) - E(v, pl 0.))) (a((a, 0.)) (a, 0 0.) za(a ()(a -0-00)) 0.), 0.)
2
Integrating both sides with respect to Pa (dy) and noting that, by our realisability assumption, fPya(dy) = p((a, 0,)), which leads to the first term dropping out, we obtain
f fly.
Ely, (ly. = - 2 0.1la(a,0))cc
For the second result, repeat the argument with the Lagrange form of the remainder.
F.2.1 Proof of bound on the number of rogue steps, Proposition
We will use the following extension of exercise 19.3 in Lattimore and Szepesvári (2020).
Lemma 35 (Lemma 2 of Janz et al. (2024)). Fix X, > 0. Let 01 a2 03 E Rd be sequence of vectors with ||ae||2 < 1 for all i. > 1. Define Vi(A) XI + Σ = a:a.. Then the number of times that [|u [oolll: (A) 2 T upper bounded by
3d
A Alog(1 + 7-)) -
1
log
1+
log( (1 22)
28

---

Proposition 5. Under Assumption 1, on the high-probate probbabbiyy event of Theorem 1, for any E N
card(t n: (Ac, 0g 0.)l 1/M} S 64dsMM2 3n log (1 (44
Proof of Proposition 5. For any 2 and 0 R define the positive semidefinite matrices
V((A) Σ A + T and G((O,)) = Σ (A,, A 1=1
where a is defined as Lemma 34. Then, using that by Lemma 34, for any 0 E O there exists a Ç E R satisfying [c]
such that a(A,, 8) pl(). we have that for all O, from the definition
of к in Assumption 1,
Vi(0) 3 (0, 0). Now suppose t E N is such that 1/M S K(,, 0, 0.) Then,
1/M S ((A,, 02 0-)1
$ |eeell 10: 0+1lva_1(A)
(Cauchy-Schwarc) (Section F.2.1)
S ||Aellı= VAl10, 0. D.llG.-1(0.N))
By the triangle inequality and then using Proposition 26, we have that on the good event &g (as defined in Proposition 22).
102- 0~ 0.l1G...00.. & 1|0, - 0 0ell...(0..0)) + VAJ0, 0.1 x 2(VB. SVA).
Hence, taking 1/(S2x). the number of times that 1/M |AA,, 0, 0.3l on Eg is no greater than the number of times that
2M 2M(VK8L+ 1) I || |Adly,
We lower bound x² by = 1/(8M + 1)) and apply Lemma 35 together with the bound log(1 y) 3/(4y), twice (which holds because 1/16), to obtain that the count in question is no greater than
4d
64 R² M
log
1+
s 64dkM2 log 1+
y
Ay
Finally, observe that 8, < 8n for any S
F.2.2 Proof of the upper bound on the eluder dimension bound, Proposition
The following proposition is a special case of proposition 8 of Sun and Tran-Dinh (2019). The lemma thereafter is simple numerical inequality that will come in handy.
Proposition 36. Let U [0. 1] be M M-seeffconcorlant link function. Then, for any u E U satisfying (u - u'l S c, ((u) < exp(cM (u))).
Lemma 37. Suppose that 1, x 2 1, b 2 and a² S bx + 1. Then,
x log(1 + b/ log b/lo(()))loo(().
Proof of Lemma 37. Let f(x) = a" and g(x) = br + 1. Since is convex and is affine, they intersect no more than two points. Since they intersect f(x) Σ g(x) is of the form [0. y) for some 2 O. Now, let y' log(1 b/ log(a))/ log(a). Then, quick calculation shows that f(y') > g(v'). Thus, y/ y.
have that the set of x satisfying
Proposition 4. Let Assumption 1 hold. Then, there exists universal constant C > 0 such that for any r, 0, the e-eluder dimension of (FF((r) is bounded as
dimelua(E; (+F((r))) < C'dep((eeM)) log(1 + S² L Lexp(rM))/s)
29

---

Proof of Proposition 4. Let 01....:00 and i1....... O2 be witness to the eluder dimension in question, in that they satisfy
.............
Σ f(a; 0,) and ((ae, 02) 2
for some w 2 & and all _ k, where the e-eluder dimension. Also, for any X 2 0, define the positive semidefinite matrix
Ha-1 = Σ ia 0.))a,a + XT 1=1
For each i & t k, use Lemma 34 to construct real number ç.. on the interval connecting (a,, B1) and (a,, 0.) that satisfies ju((s,)) a(a,, 0c). Now, by Section 4.2 for all i S k, 15,t - (a,, 0-11 S (as 02 8.)l sr, have by Proposition 36 that, for all i < S exp(-rM)) 0_)) & (((.,)) S exp(r 8.)) Hence, using Lemma 34 and Eq. (9), we have the bound
(9)
Σ ((a;, 2
10: - ---1
2 cxx((rM)
1=1
Taking x = w/(25?), this gives
110 - 0 0-112 011 S 10: - 0- 0. + A110 - 0-11
2c 4XS²
22((ex((rM) + 1).
(10)
Now, letting x4 ju((ar, 02)) /a we have that
w S p(a,,00 01)
(definition of w, a,. 02)
(as, O₁ 00)
(definition of Çr,t)
2 exp(rMM
is(ar, (.))(ar. 02 0,)²
(Eq. (9))
2 exp(rMM
- 0. 12 ju((ar, 0.)) 1 11 10:0)110000000
(Cauchy-Schwarz)
w (xxp(rM))cxx((raa
1)][ (1)))00)))
(Eq. (10))
Whence, we conclude that for all < k.
||ar=| = 2 exp( exp(-rM)(exp(rM) + +1)-1 c.
Using this lower bound and the matrix determinant lemma, we have
det Ha(A) x II
||x
| Ii (a)) 14(1 +c)
On the other hand, using the AM-GM inequality and that || the upper bound
< L, we have
det (A) (tr(HH((A))
KL
x+
d
d
Putting the two incqualities together yields the inequality
k:
(1 + c)a <
dx +
Now, applying Lemma 37 with a = 1 x k/d and b = L/> = 252 we obtain
2
< log
/og(1 + c) < de 2rM log(1 + 25 2 /w),
2rM
w log(1
where the second inequality follows by substituting in the definition of e and using that e + e²) 2x for x 2 0. Since the above bound is decreasing with 2 E, it is maximised at
30

---

F.3 Regret bound for E-UCB with the logistic model
Proposition (Regret for f-UCB with the logistic model). Ler (0,1). S 0 and E N Consider the setting of Theorem 1, with the model class F = GLM(H, Q where puu) = 1/(1+e and the logistic loss function Ex. Consider running E-UCB with confidence widths (5, (8t)EN given by
B = 5/2 + 60(2S + [) [o + 8Sn) + log(ha/6)},
h = e
Then, for a constant 0, with probability at least 6, the resulting regret satisfies the bound
Rn S C' / (dn(aa).3, log(1 Sn) + Cd3,, [log(( + Sn))² + 20 dlog(1 + [xn]]
Proof. By Proposition 16, + 4: by Lemma 32, 4S; by Proposition 33, N, I (1 85n)
Combined with Theorem 1, these results yield the confidence widths
5 B 2 60(25 1) (ogg 85n) log(h,/8)]
Recall that for the logistic model, L= 1/4, M = x = 3e and, by Proposition 20, = 2 2og (e). We consider the localised class (1), for which, by Proposition 4 and the discussion immediately thereafter, for some C > 0, the 1 eluder dimension satisfies
dn S Cdlog(1 + Sn).
This yields that for some C' O,
In S Cdd + Sn))2
Moreover, by Proposition 5, for some C" > 0,
card(l S n: Ja E (1)) S 2
2' d3n log(1 3x))
Combining these estimates with the upper bound for regret given by Theorem 1, we obtain the claimed result.
31

---

G Proof of lower bound on the eluder dimension in GLMs, Theorem
This section establishes our lower bound on the eluder dimension for generalised linear models. The construction is based on the technique of Dong et al. (2019).
Theorem 2 (GLM & feeludeer dimension lower bound), Let (p, E) satisfy the last four properties of Assumption I (link L--Lipschtzz M-self-conncorant, link-derivative lower bound, and link-loss compatibility). Fix 2 4/M and assume that [-5,0] CU. Write
ii(0)
E (0,
min([S),
2/((-S/2)
Then, there exist A B& and c. SB such that (A, O, μ. E) satisfy Assumption 1 and for every S ((00)(2M²)) the eluder dimension of the expected excess-lows class ((F) with F = GLM(G, Q) satisfie
d-1
b 16 8SM + log(R)
log(R)²
dimelna(E; ((F))
exp
min
4b
for a sequence of actions taking values in A.
Our proof will use the following lemma, given as Lemma A.I in Du et al. (2020).
Lemma 38 Nohnson-Lindenstraul packing lemma). For any integer D Z and any parameter
< E (0, 1), there exists finite set Φ C SD-1:- := {a E R ||0||2 = 1} with b 2 Lexp(Dç² /8) and
1z,, 1) S for all distinct x. Φ
Proof of Theorem 2. Let Ç E (0, 1). For N exp((bc /8)] let 21,..., EN R satisfy ||a;|| = 1
for S N and [x,, xzy) S ( for i S with i + (such vectors exist by Lemma 38).
Let e ed denote the basis vectors of Rd. Let blocks that fit into the d - dimensions spanned by 62, ......... ea. Let E; R + Rd insert E R into the coordinates of the ith such block; that is, for E [m].
[(d 1)/b] be the number of length b
E((u)= = Σ
11E1+((-1)6+
8=1
Define the optimal parameter vector 0, 2- 1/2 such that n7(a) pu(a, 0.)). We take θ consisting of 0, and the vectors
0, = 0, + 2 (E,
(i,j) E [m] x [N].
take the arm-set A to consist the vectors
0_ + 1/2 (z,,),
(i,j) E [m] [N].
ai
With this construction, have the following properties:
(asy, 0.) SS22
V(i,j) E [m] x [N]
(aij, 01z)
v(i,j) E [m] [N]
(az))0z)) S/22
Vi, E [m] with #
(aij 0ag) [-(S/2) ()S//))
v(i.)) [m] [N] and all j' [N]
For each (i,j) [m] [N]. let Pij ((F) denote the expected excess loss comparing Og against 0,: 5 (a) = ((u((a, (a, 0.) (a, 0,)))) ((p((a 0.)) p (a))))))
Consider the sequence of actions (a:;) given by
01.1. 41,N. 02 42,N am.1. Om..N
(11)
where we index by enumerating [m] x [N] in lexicographic order. We will show that for choice of Ç E (0, 1), (ai) is an w-eluder sequence for ((0))(2M²)), and lower bound the resulting
32

---

sequence length n.M (which depends on (). We will take (gt:: (1.5) E [m] x [M] as the witnessing
functions: step (i.j) function Fi certifies that the sequence (aiz) ) is w-eluder.
Large deviation at new action. Let (u) = (1(((5577) -/2), ((u)). Observe that
5/2) p( - - (/2) =0, f(-5/2) = (K(-522)
by the link and loss compatibility properties in Assumption 1. By Taylor's expansion with integral remainder, around 5/2,, noting that f(- = 0, we have
(yy(ar)) f(0) - f(-5/22 [ (1 - t)(s))) + () dt
= f((-/22 + [(1- (1-t)( (L)2))5 (- + +) dt
= (5/2)² 1 (1 - t)js (-2 + +12 dt.
By Proposition 36, we have the bound
i (- + ( 2 ii()) exp (- MS t))
Combined with the previous display, writing MS this bound gives that
(ag()))) 2 (5)2) /.8' (1 ()- (-a(1 - t)) dt (4
M (L exp(-a)(1+a)) a)) j4(0)
2M2
where the final inequality uses that a (since we assumed 2 4/M), and that x + + 1-e is increasing on (0, x)).
Small cumulative deviation. At index (i,5), the cumulative deviation is
ΣΣ
(ate) + Σ (iy(a))) E=1
E E=1
t=
where we used that A i, :.. O. Now, by the self-concordance lower bound of Lemma
applied to the one-dimensional function + ( SS/)) u(4)) we obtain that for any l j.
(ey(are) - S/2) exp
M
and there are at most N S (xp /8) such terms in the sum. Therefore,
ju(- (1-5/2) exp(42//8+
Piy(as)) S
M
This sum is upper bounded by /(00/ = w whenever
b + MC5/2 log R.
Using & S, it suffices that S(2/8 8 MÇS/2 < log R, or equivalently that
8 8log R
2 4MC
50.
S
This implies that we require Ç to be in the interval
0 0<< (V ( +2/S) - M).
Length of eluder sequence. With Ç chosen to be the largest feasible and using |x| 2 x/2 for x 2 1, we get
log(
N 2 exp(b<2/8) 2 min exp(b/8), exp 8SM + 4 log(R)
2 and m 2 (d- - 126( Hence, dimalua ((F)) 2 mN, which is lower bounded by the stated quantity.
33

---

34

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an import- ant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
35

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
36

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines thttps://nipge cc/pu blic/ Swwidee/CoeeSubbeeeeeeee
wwwsssssioiiiiyii for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips.co.. wwtppblic/gguiiiiecccceoooocccce http//uwde///eee CCodeSubmiieeeeeee hotooiiigguddeesodeeeubbiiiiiiii commisssione wwwsssssiisiooioeeeee seionnolccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confid- ence intervals, or statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
37

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : //neurriss... cc cc/ppubbitt/thhiiccciiddll11111
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
38

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswithcode com/ dataasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
39

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
40

---

Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
41


Reviews:
[{"review_id": "KTGtnF8eKa", "reviewer": "Reviewer_1B4q", "summary": "This paper aims at overcoming a key limitation in standard regret analysis in standard regret analysis for generalized linear models, where traditional methods fail to achieve first-order regret bounds due to worst-case dependencies. The authors incorporate a new concept called the localized ℓ₁-eluder dimension, enabling sharper, instance-dependent regret bounds. The proposed method improves upon classical results for Bernoulli bandits and extends to reinforcement learning, delivering the first true first-order regret bounds in finite-horizon RL. The findings highlight how localization techniques can unlock more adaptive algorithms, paving the way for further advances in learning theory.", "questions": "1.\tWhile the localized eluder dimension eliminates k-dependence, Proposition 4.4 shows rogue steps still depend on the parameter k. Could k still significantly impact performance in extreme cases (e.g., very large k)?\n2.\tHow should key hyperparameters like localization radius r be chosen? Are there adaptive methods to set r?\n3.\tWhile 2D bandit experiments demonstrate advantages, would similar improvements hold for higher-dimensional RL tasks?\n4.\tHave you considered comparisons with non-eluder dimension methods?\n5.\tCould the authors provide some experimental results on RL benchmarks? Should the authors make the computational complexity of the proposed method?", "limitations": "Here the two suggestions for the authors: (i) The theoretical analysis currently focuses on bounded-cost scenarios. The authors should discuss whether/how the method could generalize to unbounded reward settings. (ii) Computational complexity of the localized eluder dimension calculation isn't analyzed. Some discussion of practical scalability would strengthen the work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1.\tThe paper makes significant theoretical contributions, with rigorous proofs supporting the proposed method in manuscript and appendix.\n2.\tThe approach is well-suited for online RL tasks, eliminating the need for impractical exploration mechanisms required by prior methods.\n\nWeaknesses:\n1.\tWhile the theoretical analysis is thorough, the paper lacks sufficient experimental validation (e.g., RL benchmarks or real-world datasets).\n2.\tThe computational efficiency of the method, especially in high-dimensional state-action spaces, remains unexplored.\n3.\tThe writing could be improved for clarity and style. For instance, the title uses inconsistent capitalization (e.g., \"Localise It!\")", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their reading and helpful suggestions.\n\n**Number of rogue steps.** The number of rogue steps appears only additively in the regret bound of Theorem 4.1 and is therefore a second-order term. Hence, even when $\\kappa$ is large, its effect remains negligible for sufficiently long horizons.\n\n**Choice of localization radius r.** The radius r is used solely in the analysis and does not need to be specified for the algorithm. For example, setting r=1/M, where M is the self-concordance parameter, ensures that the localized eluder dimension is bounded, as as well as the number of rogue steps, as stated in Proposition 4.3 and Proposition 4.4.\n\n**Experimental scope.** Since the main focus of our work is the theoretical analysis of optimistic algorithms (i.e., eluder dimension) rather than proposing new algorithms, we focus on a comprehensive theoretical treatment of adaptive algorithms for decision making. However, given the reviewers’ interest, we will consider adding a synthetic experimental section in the final version.\n\n**Non eluder methods.** Small-cost regret bounds exist in specific settings (e.g., logistic bandits) without using the eluder dimension. However, the eluder dimension remains a popular complexity measure in bandits and RL and as we show, when applied naively it prevents achieving small-cost bounds. Our contribution introduces localization to overcome this limitation, bringing eluder-based analysis closer to the behavior seen in specialized non-eluder approaches.\n\n**Computational efficiency.** Appendix C.5 describes an ellipsoidal relaxation of our confidence set (with a $2(1+SM)$ blowup), which reduces the computational complexity to that of LinUCB—a standard approach in the bandit literature. In practice, LinUCB requires solving a joint optimization over the parameter $\\theta$ and action $a$, where $\\theta$ lies in an ellipse. This optimization is computationally efficient for many common action sets, including finite sets, polytopes, and various other convex sets.\n\n**Unbounded costs.** While we do not provide a formal analysis for unbounded costs in this paper, we believe that our techniques could extend to settings with sub-Gamma costs (or other standard tail assumptions). We leave a detailed treatment of this extension as an interesting direction for future work.\n\n**Eluder dimension computation.** The localised eluder dimension is a purely analytic tool used to prove tighter regret bounds, and is not needed to run the $\\ell$-UCB algorithm. Thus, there is no need to compute it."}, {"review_id": "mZ6gGCdjLY", "reviewer": "Reviewer_5GDg", "summary": "The argument in the paper (both the bandit and RL case) proceeds as:\n\n1. There is a pathological information constant $\\kappa$ that nullifies the benefit of small cost regret bounds in prior work.\n\n2. But actually, we should be able to do with a much smaller constant so the above is not a \"real effect,\" but an artifact of the worst-case nature of the previous analysis.\n\n3. To make this tighter, the authors replace with the local constant $\\kappa$ but then need to pay an additional term for mis-approximating the actual \\kappa constant.. and we are guaranteed that this is generally bounded for good algorithms that eventually hang out in a ball around the true \\eta.", "questions": "See weaknesses above", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I thank the authors for the interesting paper and I enjoyed reading it.\n\n\n### Strengths\n\n**Significance and Originality** The authors identify an important problem in the prior theoretical RL literature and come up with a nice way to tighten the bound and make it genuinely instance-dependent.\n\n**Quality** The mathematical presentation is technically sound.\n\n\n### Weaknesses\n\n**Literature** The authors overall do a good job of situating the paper. However, they do not comprehensively cover the related area of instance-dependent guarantees in RL that use experiment design-based approaches. Some relevant papers to compare with:\n\nhttps://arxiv.org/abs/2207.02575\nhttps://arxiv.org/abs/2406.06856\nhttps://arxiv.org/abs/2311.05638 \n\nI would be curious to understand how the bound the authors obtain relate to the upper and lower bounds in this line of work, since it seems that the experiment-design style of analysis does not suffer from the limitations that the authors aim to address.\n\n**Writing** While the technical results are nice, some improvements in the writing could definitely help the central insights shine through more; currently, the insights are hidden inside a lot of exposition. For instance, a couple things that would be good to do:\n\n- Have a concrete and easy-to-understand motivating example in the beginning which shows why the information gain factor easily blows up. And make more explicit what sorts of instances this effect is predominant in.\n\n- Highlight the additional technical challenges for the RL case as compared to the bandit case. And highlight this result more as the strongest result of the paper. It could be good to state this inside a theorem environment even if the statement is informal.", "was_revised": true, "final_justification": "My concerns were mostly addressed by the rebuttal. However, I think it is important that the authors provide further intuition about when the constant $\\kappa$ blows up, so that the paper is more interpretable and intuitively appreciable.", "rebuttal": "We appreciate the reviewer’s reading of our work and their helpful suggestions.\n\n**Experimental design-based approaches.** We thank the reviewer for highlighting these relevant papers on experimental design–based approaches. We will include them in the related works section of the final version.\n\n**Comparison with similar results.** Perhaps the explanation in Section 4.1 helps clarify this point. Our analysis removes the need for an explicit warm-up phase, which can be thought of as a forced experimental design step. Instead, we introduce the localized eluder dimension and handle the \"experimental design\" aspect analytically rather than algorithmically. Thus, our method achieves comparably strong instance-dependent regret bounds without requiring a warm-up, naturally generalizing beyond bandit settings to reinforcement learning scenarios where explicit warm-ups or optimal-design methods are less feasible.\n\n**Writing and examples.** We appreciate the feedback and will work to better highlight the importance of the results in the final version. Regarding the motivating example, we would like to mention that the current example (“clickthrough rates in online advertising,” lines 164–169) is intended to address this point and provide an intuitive illustration. Nevertheless, we agree it would be helpful to further clarify why the information-gain factor can easily blow up, and we will make these scenarios more explicit in the final version.\n\n**Reinforcement learning.** The RL result is indeed the most interesting; we will use the extra space afforded by the camera ready to include it in the main paper. We will also revisit the story-telling to emphasise the RL result more. Thank you for this feedback."}, {"review_id": "V5GXda4UeU", "reviewer": "Reviewer_9PY3", "summary": "This paper investigates the limitations of the standard eluder dimension in achieving first-order regret bounds for GLMs in online decision-making. The authors show that exisiting eluder-based approaches inherently suffer from dependence on a global worst-case complexity term \\kappa, which cancels out potential gains in small-cost settings. To address this, they propose a localized \\ell_1-eluder dimension that captures the complexity near the optimal predictor. They use this refined measure to derive genuinely first-order, instance-adaptive regret bounds in both stochastic bandits and finite-horizon RL, instantiated via new algorithms (\\ell-UCB and \\ell-GOLF). Theoretical results show improved guarantees over prior work without requiring warm-up phases or likelihood assumptions.", "questions": "How restrictive is triangle condition in practice? Are there other loss functions beyond log and Poisson loss that satisfy it?\n\nCould your framework be extended to misspecified setting?\n\nDo you envision the localized loss-based analysis extending to more general function classes, like RKHS or NNs?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper identifies and rigorously proves a key limitation in prior work using global eluder dimensions and proposes a novel and solid fix.\n\nThe paper achieves the first true first-order bounds in episodic MDP under bounded cost, improving over existing works which suffer from \\kappa-dependent regret.\n\nThe work applies to both stochastic bandit and online RL settings,with insights that may extend to other model classes and loss structures.\n\nWeaknesses:\n\nThe paper is entirely theoretical. While this is acceptable given the depth of the contribution, even a small synthetic experiment would help illustrate the practical gains from localization.\n\nThe regret bounds rely on specific assumptions about the loss function (e.g. triangle condition), realizability and self-concordance. These may not hold in broader settings thus it would be helpful to know how sensitive the results are to violations of these assumptions.\n\nOptimization over localized confidence sets can be intractable in general, and the paper only briefly references convex relaxations without discussing implementation feasibility.", "was_revised": true, "final_justification": "The rebuttal explains the necessity of the assumptions in their main theorem and admits to add synthetic experiments, so I deicide to keep the same score.", "rebuttal": "We appreciate the reviewer’s time and thoughtful feedback on our work.\n\n**Broader Settings.** Perhaps the situation would be more clear if we go through the role of each assumptions. \n1. Self-concordance: This is a property of the loss function. Since the loss function is chosen by the algorithm designer, one can select a loss that is self-concordant. Many commonly used losses (e.g., logistic and Poisson and many more [1]) satisfy this property. Importantly, self-concordance is not required for our main theoretical result—it is rather used to compare with existing results in specilized settings such as logistic bandits, and to achieve computational efficiency through ellipsoidal relaxtion of the confidence set.\n2. Triangle condition: This condition seems essential for achieving small-cost bounds. For example, the squared loss does not satisfy the triangle condition, and we know that small-cost regret bounds are not achievable with it (see [2]).\n3. Realizability: This is a true modeling assumption. Removing it entirely is challenging; however, one could restate our results in terms of a “best-in-class” comparator and derive the corresponding regret bounds. The analysis of such misspecified settings would be possible but is beyond the scope of this paper.\n\n**Computational efficiency.** Appendix C.5 describes an ellipsoidal relaxation of our confidence set (with a $2(1+SM)$ blowup), which reduces the computational complexity to that of LinUCB—a standard approach in the bandit literature. In practice, LinUCB requires solving a joint optimization over the parameter $\\theta$ and action $a$, where $\\theta$ lies in an ellipse. This optimization is computationally efficient for many common action sets, including finite sets, polytopes, and various other convex sets.\n\n**Experimental scope.** Since the main focus of our work is the theoretical analysis of optimistic algorithms (i.e., eluder dimension) rather than proposing new algorithms, we focus on a comprehensive theorectial treatment of adaptive algorithms for decision making. However, given the reviewers’ interest, we will consider adding a synthetic experimental section in the final version.\n\n**General function classes.** Yes, our analysis indeed naturally extend to general function classes. One should only provide the necessary \"supervised learning\" fast rate guarantees (See, e.g., [3] for the RKHS case).\n\n[1] Liu, Shuai, et al. \"Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits.\"\n\n[2] D. J. Foster and A. Krishnamurthy. \"Efficient first-order contextual bandits: prediction, allocation, and triangular discrimination.\"\n\n[3] Akhavan, Arya, et al. \"Bernstein-type dimension-free concentration for self-normalised martingales.\""}, {"review_id": "2l65DA9jd9", "reviewer": "Reviewer_tRDf", "summary": "The paper proposed a localized $\\ell_1$-eluder dimension that can handle the limitation of the standard eluder dimension in the regret bound of the decision-making problem. The authors first give a lower bound of a small-cost bound by using global eluder dimension in generalised bandits to show that the drawback of global eluder dimension can not match the best known upper bound. Based on this motivation,the authors provided UCB-based algorithms for both Bernoulli bandits and online RL problems and established the adaptive, first-order regret bounds based on their localization approach.", "questions": "1. The set of functions $\\mathcal{F}$ is bounded and positive. Can it extend to negative or unbounded?\n2. Could you give some remarks on the last term in the result of Theorem 4.1, $\\mathrm{card}${$ t \\leq n : f_t \\notin \\mathcal{F}' $}? Is it normal in previous related work?\n3. In line 172, the sentence seems incomplete. $\\mathcal{F}^{\\prime}(r)=$ {$\\mu(\\langle\\cdot, \\theta\\rangle): \\theta \\in \\Theta^{\\prime}(r)$}  for what?\n4. The lower bound in Theorem 4.2 is for the Eluder dimension. Is it possible to provide the lower bound for the regret bound? Or any evidence to show how good your regret upper bound is?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper provided solid theoretical contributions and fundamental insights. It is good to first provide Theorem 4.2 as evidence to show the disadvantages of the previous method and then introduce localised eluder dimension to show how localization helps it, which is also conceptually meaningful.\n2. The writing is good. And it is good to give some function examples to Assumption 2.1. And the authors give some sufficient comparisons with previous related work, such as section 4.1.\n3. The paper studied both bandits and RL problems under this method, which shows the efficiency of the method and its potential to be used in more problems, such as RLHF.\n\nWeaknesses:\nThe paper lacks experimental results. And it is unclear how to use the localised eluder dimension in practice. I understand the main contribution is on the theoretical side, but some empirical results would show the practical benefits of localisation.", "was_revised": true, "final_justification": "I appreciate the author's response to improve my understanding of tightness. And my concerns are solved by the authors' rebuttal. The paper provided solid and interesting theoretical contributions, as other reviewers also mentioned. But it lacks experimental results, thus I would like to keep my score.", "rebuttal": "We thank the reviewer for their careful read and helpful suggestions.\n \n**Localized eluder dimension.** The localised eluder dimension is a purely analytic tool used to prove tighter regret bounds, and is not needed to run the $\\ell$-UCB algorithm. Thus, there is no need to compute it. \n\n**The function class $\\mathcal{F}$.** The set of functions F do not need to be bounded or positive. The losses however need to be bounded, with known bounds. Hell will freeze over before the requirement that the losses are bounded from below (with a known bound) is removed: this is a feature of every small cost bound in the literature. And by the time this lower bound is known, we might as well offset by the lower bound and say that the loss is nonnegative. The assumption of an upper bound is not necessary: it can be replaced by, for example, the assumption that the right (upper) tail of the losses satisfies a moment condition (e.g. is subgaussian) for any choice of states/actions.\n\n**The number of rogue steps and tightness.** The number of rogue steps (the card{} term) appears only additively and therefore is second order term— negligible for sufficiently large n (the horizon). Similar additive terms also appear in previous works on logistic bandits (which is an special case of our analysis), making this behavior consistent with existing literature (see, e.g., [1]). When specialized to the generalized linear bandit setting our regret bound matches the best bounds for the problem-specific algorithms, and indeed matches the lower bound of [1].\n\n**Experimental scope.** Since the main focus of our work is the theoretical analysis of optimistic algorithms (i.e., eluder dimension) rather than proposing new algorithms, we focus on a comprehensive theoretical treatment of adaptive algorithms for decision making. However, given the reviewers’ interest, we will consider adding a synthetic experimental section in the final version.\n\n[1] Abeille, Marc, et al. \"Instance-wise minimax-optimal algorithms for logistic bandits.\""}]

Author rebuttal:

Meta-review: This submission studies genuinely first-order, instance-adaptive regret for generalized linear models and finite-horizon reinforcement learning. The authors identify why global eluder-dimension analyses are bottlenecked by a worst-case information constant and formalize this limitation with a lower-bound argument. They then introduce a localized eluder dimension that focuses analysis near the optimal predictor and instantiate it with UCB-style algorithms for bandits and an episodic RL counterpart, yielding first-order bounds without a warm-up phase and with an additive rogue-step term that remains second order. The paper also presents an ellipsoidal relaxation that reduces the optimization burden to a LinUCB-like routine and clarifies when the global worst-case constant can become large; reviewers found the theory careful and the extension from bandits to RL a notable strength.

While the problem is important and the contribution is well motivated, the work remains entirely theoretical: there are no RL benchmarks or broader empirical studies to illustrate finite-sample behavior. Some assumptions (triangle condition, realizability, and self-concordance used for efficiency) may limit applicability; the rebuttal helpfully scoped their roles, but a discussion of robustness to mild violations would improve practicality. 

Recommendation: Accept. The paper pinpoints a real limitation of global eluder analyses and offers a principled localization remedy that delivers first-order bounds for both bandits and episodic RL.
Decision: Accept (spotlight)