Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits
Authors: Shuai Liu
Alex Ayoub
Flore Sentenac
Xiaoqi Tan
Csaba Szepesvari
Venue: NeurIPS 2024 poster (2024)
Keywords: bandits
generalized linear models
natural exponential families
self-concordance.
Primary area: bandits

Abstract: We prove that single-parameter natural exponential families with subexponential tails are self-concordant with polynomial-sized parameters. For subgaussian natural exponential families we establish an exact characterization of the growth rate of the self-concordance parameter. Applying these findings to bandits allows us to fill gaps in the literature: We show that optimistic algorithms for generalized linear bandits enjoy regret bounds that are both second-order (scale with the variance of the optimal arm's reward distribution) and free of an exponential dependence on the bound of the problem parameter in the leading term. To the best of our knowledge, ours is the first regret bound for generalized linear bandits with subexponential tails, broadening the class of problems to include Poisson, exponential and gamma bandits.

Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits
Shuai Liu University of Alberta shaailiu7250gmal.. com
Alex Ayoub University of Alberta aayoub@ualberta.cm ca
Flore Sentenac
Xiaoqi Tan University of Alberta xiaoqi. tantualberta.co ca
Csaba Szepesvári University of Alberta
HEC Paris sentenacChec.frr fr
csaba. wwwpessarrigaail..coom
Abstract
We prove that
natural exponential families with subexponential tails are self-concordant with polynomial-sine parameters. For subgaussian natural exponential families establish an exact characterization of the growth rate of the self-concordance parameter. Applying these findings to bandits allows us to fill gaps in the literature: We show that optimistic algorithms for generalized linear bandits enjoy regret bounds that are both second-order (scale with the variance the optimal arm 's reward distribution) and free of an exponential dependence the bound of the problem parameter in the leading term. To the best our knowledge, ours is the first regret bound for generalized linear bandits with subexponentic tails, broadening the class of problems to include Poisson, exponential and gamma bandits.
1 Introduction
Single-parameter natural exponential families (NEFs) [Mor82] abound in statistical applications [MN89; Bro86; WJ08; MI.09.. In this paper we study properties of NEFs and in doing so we make two main contributions:
1. We study how tail properties of the base distribution of NEF impose limits on the NER: if the base distribution is subexponential (subgaussian), we show that the NEF is self- concordant with stretch factor that grows inverse quadratically (respectively, linearly)
2. In generalized linear bandits whose reward distributions follow a NEF with subexponential base distribution. we show how this new result can be utilized to derive novel second order regret bound whose leading term is free of exponential dependencies on the problem parameter the first such result for this setting.
The class of distributions our results extend to includes: normal, Poisson, exponential, gamma and negative binomial distributions. Our findings partially address conjectures on whether generalized linear models with unbounded targets are self concordant [Bac10; Fau+20]. This significantly generalizes the case when the targets are assumed be bounded! [Mar+19; OB21: Rus+21] and thus extends the applicability of the results therein.
This assumption does not hold for distributions with unbounded support such as: normal, Poisson, exponen- tial, gamma and negative binomial distributions.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Self- ceff-concordace in NEFs turns out to be useful for both optimization and statistical estimation. The self-concordance property controls the remainder term, or approximation error, of NEF's second- order Taylor expansion. This is useful in designing and analyzing both estimation and optimization methods. Historically the seff-concordance property was first found to be useful for optimization [NN89; NTT08; ST19] and later for statistical estimation [Bac 10; Mar+19; OB21; BFR23]. In this paper, we will employ the self-concordance property in bandit problems [LS20] where it helps with controlling the error terms related to estimation.
Generalized linear bandits (GLBs) [Fil+10] has emerged as a standard framework for studying the role that nonlinear function approximation plays in decision making problems. Earlier works on GLBs (or its special case of of logistic bandits) [Fil+10; LLZ17; SPL23] naively approximates the nonlinear function with a linear first order Taylor expansion. This approach ends up paying a price in the leading term of the regret bound that is exponential in the size of the true underlying parameter. In logistic bandits, [Fau+20] were the first to exploit the self-concordance property of the Bernoulli distribution in order to get regret bounds free of an exponential dependence on the size of the problem parameter in the leading term. [Fau+20] use self-concordance to get tighter second order Taylor expansion that better captures the curvature of the sigmoid function. Employing improved self-concordant analysis, [AFC2I] get second-order regret bounds for logistic bandits and [Jan+24] extend these results to GLBs, under the assumption that the underlying reward distributions are self- colf-concordant. We build upon this line of research and fill gap in the bandit literature by designing and analyzing algorithms for GLBs with subexponential reward distributions. To the best of the authors' knowledge. our work considers the most general setting in the sense that all the previous works on GLBBs considered subgaussian or bounded reward distributions while ours consider suhexponential ones. For subgaussian rewards, these works [Fil+ 10; Jun+21; 1; SPL233; Rus+21] still depend on K. Note that [Rus+21], also employs self-concordance in GLBs but they assume bounded reward and focuses on addressing con-stationarity of the environment. In addition, their bounds also scale with x in the leading term, which can be exponentially large for logistic bandits. [Jan+24] consider a similar setting ours. They assume the moment generating function of the base distribution Q is defined over the entire real line. This implies that Q does not have a tail as heavy as an exponential distribution hence less general than our setting. A concurrent work [LYJ24] develops novel confidence sets for self-concordant GLBs to improve the theoretical bounds while we prove that all GLBs with light-tailed base distribution are self-concordant. An interesting future direction would be applying their techniques to improve the bandit result of our work. [Saw+24] considers GLBs with bounded reward, which is known to be self-concordant, in a regime that only a limited number of decision policy updates is available.
The paper is organized as follows: key properties relevant to our analysis. Section 3 demonstrates the self-concordance property of subexponential (subgaussian) NEFs, with a quadratic (respectively. linear) growth rate of the stretch factor. Additionally, we establish the tightness of the linear growth rate for subgaussian NEFs. In Section 4 we apply these findings to subexponential GLBs and derive novel second-order regret bounds devoid of exponential dependencies on the problem parameter in the leading term. Proofs omitted from the main text are provided in the appendix, except for those of well-known results, which are referenced accordingly.
In Section we introduce single-paramens NEFs and review
2 Preliminaries
In this section we first introduce the notation we will use. We then introduce natural exponential families, review some of their basic properties and illustrate the concepts introduced by means of an example.
2.1 Notation
For real-valued differentiable function defined over an open interval, we use f, f and j to denote the first, second and third derivative of f. The set of reals is denoted by I, the set of nonnegative reals by R.. For set C IR, we denote interior by lt, For real numbers a, b, we use a A and a V b to denote the minfa, b) and max b). respectively. With ø logical expression, T(())- = 1 & evaluates to true and [Ø] = O, otherwise. We use ʃ S g to indicate that و dominates f up to constant factor over their common domain. For S C R. H. we let S + x denote the set

---

fs=r: : S). A distribution over the reals is centered if it has zero mean. We use P() to denote the probability measure over the probability space that holds our random variables and we let E to denote the expectation corresponding to this measure. By Y ~ Q we mean that the distribution of Y, a random variable, Q.
S
2.2 Single-parameter NEFs
In this section we give our definitions for the NEF. We only consider single-parameter natural exponential families when the base distribution is defined over the reals. We follow the approach of the beautifully written monograph of [Bro86] that the reader is also referred to for any statements made about NEFs with no proofs.
Given probability distribution Q over I. let Mq : R. + R2 {+oo} denote its moment generating function (MGF):
(u cxp(uy)Q(dy),
E R.
We will find convenient to also use the logarithm of the moment generating function, which is known its cumulant generating function (CGF). We denote this by ui RR + [+oo). Thus, *)((u) = log (u)..
Let Mq = {u R: Mo(u) < oo} denote the domain of Mo (and, thus the domain of thq). As it is well-known, thg convex and hence Uq always an interval (which, trivially, always contains 0). For subset of Ug. denoted by 4 C Uq. we call Q = (Qu)aeu a natural exponential family (NEF)
generated by Q where for any u 21 have
Qu(dy) = MQ(u) exp (sp(u))Q(dy).
It follows that Qu is also probability distribution the reals for any U by definition. An equivalent, useful form for Qu is Qu(yy) = cxp(uy ((d()))((dy). In applications, u denotes an unknown parameter that is be estimated based observations from Qu. Thus, U/ allows one to express extra restrictions on the admissible parameters beyond the limits imposed by Q. We call U the parameter space, and Ug the natural parameter space.
The distributions Q, Qu and parameter u are referred to as the base distribution, the (exponentially) silted (base) distribution and the tilting parameter. An NEF is said to be regular when Ue is open. It is casy to see that for any u, uo E UQ. Qu = (Qu.) where the distribution on the right-hand side stands for the tilt of Quo with parameter space, in a regular NEF, one can always assume that 0 E UG. In fact, the same can be assumed for the parameter set, as long as U is nonempty. I is an interval then 40 = 0 means that is is a singleton: An uninteresting
ug- As such, up to constant shift of the parameter
if we want model host of non-identical distributions.
In regular family, an equivalent way to parameterize NEF is using the mean function (ef. Theorem 3.6, page 74, of [Bro86]), pQ UQ + R, which is defined
pQ(U) = =f (dyy = I exp((uy) uy) Quy)
MQ(u)
Since Qo = Q, clearly, (0) is just the mean of Q. To minimize clutter, when Q is clear from the context, we will write μ instead of pQ. To illustrate the developments so far, we consider the example when the base distribution is an exponential distribution.
For X > O, let Q be an exponential distribution with parameter X: Q(dy) By 2 - As is well known, the MGF of Q takes the form otherwise. Thus, Uq = {u E TR MQ(u) < <0)
Example 1 (Exponential distributions).
A_ MQ(u)= x-u when u < X and MQ(u) (-o0, A). The mean function takes the form of
muu)= 0000 by byexp(-Xyp (xxp(=xx)xxp(uu)dy exp(uy)dy MQ(u)
-- s.
In what follows, we will need the following proposition to relate the central moments of Q., to the derivatives of vi the CGF.
3

---

Proposition 2. Let Ls be non-empry. Then, &Q is infinitely differentiable on Ug. Furthermore, the first three derivatives of to at E Ug give the first moment, second and third central moments of Qu
In the context of Example 1, Proposition 2 gives that (')(2) = log log(A - u) when u < A. Then, (1) x- agreeing with earlier computation.
3 Self-concordance of NEFs
This section contains the first set of main results of this paper. We start by giving our definition of self-concordance of NEFs, followed by study of when this property is satisfied. We include result that shows how ceff-concordance allows one to derive tail properties of members of the family from that of the base distribution.
In general, the magnitude of higher order derivative of real function can be bounded in terms of a lower order derivative of the function, the function is said to be self-concordant [ST19]. This property useful for studying how fast the function changes with its argument, as well as for deriving bounds how well the function can be approximated by low order polynomials [NN94; Nes04; ST19J. In the context of single-parameter natural exponential families, we propose the following natural definition:
Definition 1 (Self-concordant NEF). Let Q (Qu)ueu be NEF with parameter set U C C and some base distribution Q. We say that Q self-concordant if there exists a nonnegative valued function I 1u + R2 such that
(i(u)] S (()) for all u ueu.
(1)
Any function r: ::u + R. that satisfies Eq. (1) is called a stretch function of the NEF.
This definition takes inspiration from the works of [Bac ST19; Fau+20] and [Jan+24] who define an analogous property (cf. Assumption 2 of [Jan+24]). By Proposition 2, we know that ju(u) is the variance of Qu, while ju() is the third central moment. Hence, juu) is nonnegative, which explains why there is no absolute value on the right-hand side of Eq. (1).
According our definition, require that the (absolute value) of the second derivative of ju is bounded by the first derivative, up to the "stretch factor" T(u). Clearly, provided that ja is positive over 24, wewf-concordaneee is equivalent to stating that I TQ(u)= = |ل(اق| is finite valued over U. When ji())= = 0 for some u U4 one can show that Qu must be Dirac distribution and hence so does Q (Q and Q,, share their support). In this case, we also have jä = O and hence any nonnegative valued function is a valid stretch-function. In particular, ToQ = 0 is also a valid stretch function.
A(a)
It turns out that studying self-conccrdance property of distributions in detail can turn out much finer bounds than naively bounding jí and jı separately.
Example (Avoiding exponential dependencies). Consider a NEF Q with base distribution Q, Bernoulli distribution with parameter 1/2, we have Ug = R. u(u) Ite and thus jt = yu(1 μ)),
j ji(1 - 24).. Hence Q is I o--seff-concorlan with I')(u) < for all u u RR This is an example where naively bounding l'q, by bounding the numerator and denominator separately over [-er s] for s >> 0 gives a quantity of size e", which lags far behind the constant we obtained with a direct calculation, or what we can get from the result Section 3.2, which show a scaling of order ((s).
As opposed to earlier literature where self self-come is used [NN94: Bac 10; ST19], we allow non-constant stretch- r. As it turns out, this is necessary if LI Ug is to be allowed:
Example (Non-constam, stretch factor). Consider a NEF Q with base distribution Q. For Q an exponential distribution with parameter À >> O, Q is ceff-concordant over U UQ (- A) with 2 l'q(u) X-o u < X. Indeed, a simple calculation gives that for u < X ju(u) (A u) - and ((u)) 2(A ----u] u) -3, and so (((l))/((u) 2/(2 u).
As was shown above, for the NEF built on the exponential distribution with parameter X, there is no constant stretch factor that makes the NEF self-concordant over the entirety of the natural parameter space. The main result of the next section shows that a non-constant stretch factor with growth similar

---

to the exponential always exists provided that the base distribution is subexponential." As it turns out, the growth of the stretch factor plays an important role applications: Among other things, allows us to conclude that the tilted distributions are subexponential, as captured by the next result, which is a slightly generalized version of an analogous result of [Jan+24]:
Lemma 5 (From seff-concore to light tails). Let Q (Qu)ueu be NEF which is self- concordant with stretch functioon r U - 4 where U is subinterval of = (a, b). Then, for any 1 U,
te. (s) - su((u) + j(u) for all s (o n (a inf u, b s (2)
where K suPnEu ((u).
Note that when LI is a strict subset of Ug. 0 E (a--infl bn supp(() and thus the result is nontrivial as long K oc. To interpret this result, recall that centered distribution Q is called subexponential with nonnegative parameters (v,a) if
#o(()) S 2222/2,
for all |s| S 1/a
(ef. Definition 2.7 [Wai19]. A consequence of this is that the mean of n independent random variables drawn from Q, with high probability, will be in zero-centered interval of length O( 0(v22/n+ L.). Here, the first term describes a "subgaussian" behavior, while the second a "pure subexponential" an behavior. Assume for simplicity that a -6 and in supll. From Eq. (2) it follows that Qu. when centered, is subexponential with parameters v² = 2 twice the variance of Qu. and min /
/ K, b sup In particular, term in the confidence interval (the term 1/(an)), but not the leading term, which is governed by the variance of Qu. It follows that understanding how fast I can grow its argument approaches the boundary of Ug is thus important, although its impact only appears in a low-order term.
see that the growth of I impacts the lower-order
We now turn to our first main result that shows that the growth of T is at most inverse polynomial provided that the base distribution itself subexponential.
3.1 Self-concordance with a subexponential base
We start with recalling equivalent definitions of subexponential distributions, which will be useful to interpret our results. In particular, according to Theorem 2.13 of [Wai19], given a zero-mean distribution Q over the reals, the following are equivalent:
Q is subexponential;
The MGF of Q is defined in an open neighborhood of zero;
(iii) For some positive constants C, 0, IP[[| 2 t) < C exp((cct) where Y ~ Q.
will be useful have quantitative version of this statement. For this, we separate the left and the right tails (as in some application they have different behaviors, which we may care about). The quantitative result for the right-tail tail as follows (the result for the left-tail omitted; it follows by symmetry):
Proposition 6. Let C1. C1, > 0, Y ~ Q and assume that EY = If
P(Y 2 f) C1 exp(-cit) for all 2 0
then for any 0 < c1, (A < 1+ c Furthermore, for any e > 0 such that MΩ(c) < co.
CiX²
F(Y: 2 t) < MQ(c)e holds for all t2 0.
The first part is nontrivial; the second follows easily from Chernoff's method. The proof is given in Appendix B.
Let
- EX satisfies Eq. (3) where X ~Q}
Herre follows the terminology used the concentration of measure literature where these distributions are also knowns as subgamma distributions [BLM13; Ver18; Wai19], or light-tailed distributions. This is to be contrasted to the use of the same term in the theory of heavy-tailed distributions, where subexponential refers to much larger class of distributions [GK98].
5

---

In words, Enghht is the class of distributions over the reals whose right-tail displays an exponential decay governed with the rate parameter oi 0 and scaling constant C₁ 0. Similarly, we let (C1, C1) be the class of distributions Q over the reals such that for X ~ Q. Y TXX- X satisfies Eq. (3). With this notation, the first part of the previous proposition is equivalent to that Q E Enghh( C1) is centered then Mq stays below the function À + 1 + ( -x (0, In particular, this means that Ug contains c1)
G over the interval
With this, we are ready to present our theorem that establishes the self-concordance property of NEFs with subexponential tails.
Theorem 7. Let Q E Enght(es, C1) n (o,, C2) for some positive constants C₁ C₁, i= 1, Then, the NEF Q = (Qu)ueu is self-concordant, Moreover, the function 1'; U + R2 defined by
2
2
2eC1c1
c1
G,,C,,02,9,,00 if0 u <cq
1--
T(u)=
22c
1
ub
+ GolCC. (2)
- <
ezt
is a stretch function for the NEF Q where Go M2, mi, m2) is a polynomial whose coefficients depend on Q.
The exact expression of Go can be found in Eq. (8). Let Q be NEF with base distribution Q when Q is zero-mean Laplace distribution with variance 2X In this case, can choose C1 C2 = 1/>,
= = 1/2.. The actual stretch function is Qw) (T/A- (TAA- 3x Thus, the above theorem gives the correct behavior in that both the stretch function from the theorem and the actual stretch function QQ blow up with the inverse of the distance to the boundaries of Ug. except that the actual growth scales linearly with the inverse distance, while the theorem gives quadratic scaling. It remains an open problem to see whether this quadratic order can be improved.
8x"|ul
The following corollary is an immediate result of Lemma 5 and Theorem 7 (Appendix C.3), but can also be proved directly from the definitions (and we include direct proof as part of the proof of Theorem 7).
Corollary 8 (Distributions in regular NEFs are subexponential). Let u E Ug Then Qu is subexpo- nential both on left and right.
Because of this result, there is essentially no loss in generality in only considering the subexponential case when working with NEFs. In particular, self-concordance in NEFs is "almost free".
Proof sketch for Theorem 7 arguments used to extend the result to all cases can be found in Appendix C. By Proposition 2, bounding the stretch function of NEF amounts to showing
We sketch here the result for p(0)= i(0) > 0 and
0. The
Tw(u)= f [v (((v))(())]) (Q < <T(w),
J - (()))
where the division by Var(Qu) f - (² is justified by Lemma 12. We split the proof of that upper bound into two steps: controlling the variance and the absolute third moment.
Step 1: Controlling the variance Since ja(0)= = Var(Q) > 0, there exists a Q-dependent constant
n >> 0 and an interval [-b,- C RR s.t. Q(1 -a)) 2 n (Lemma 16). With this observation, we can show (Lemma 17):
-ub
(u)) 2 a²n MQ(u)*
Thus, the second moment decreases at most exponentially with the parameter u.
Step 2: Controlling the absolute third central moment First, we use classical result on moments of random variables (see the proof of ii for prop.2.5.2 in [Ver18]):
f l u(u)) /
13
32 3/ p(u)) 2 t)dt +
32 3PP(1Y - p(u)) 2 t)dt
3
[ 3P2P(1X - m(u)] 2 t)dt,
Bj(u))
(5)

---

where Y ~ Qu and B is constant to be optimized. It should remain small enough for the first term blow up. On the other hand, should be large enough for the second term divided by the lower bound obtained on ju(u) remain controlled.
To upper bound the second term in Eq. (5), start by showing that the right tail of the tilted distribution Qu is also subexponential (Lemmaa 18):
Qu((1, X Mo(u)
(cr ujj
for 0 a c1
(6)
G a-u
Following this lemma, we get an upper bound on plu) (Lemma 20):
0 S p(u) S
for 0 uuc.
(7)
In the proof, we bound separately the positive and negative values in the second term of Eq. (5):
| 32 3f - (())) 2 t)dt
3P 2 plu) + t)dt + PP S u(u) - t)dt.
We give here the sketch of proof on the bound of as the proof for bounding 2 is nearly identical. From plugging Eq. (6), we get:
31 (a - u)(++((w)) dt.
Me(u) Ci
u
By choosing B 2
ub + -n
some algebra gives:
c
u2bb
MQ(u)
C7
2
Setting B ~
01 c2 gives similar bound on Chaining the bounds on and with
Eq. (5) and Lemma 17 finishes the proof.
3.2 Self-concordance with subgaussian base
In this section refine the previous result for NEFs by considering the case when the base distribution is subgaussian. Let > O. Recall that centered distribution Q is o-subgaussian if for all R, MQ(u) S ex 2 (or, equivalently, (u) o²u²/² /2 for any E R). A non-centered distribution is o-subgaussian, if is subgaussian after centering. Similarly to the subexponential case, one can show that centered distribution Q is subgaussian if and only if for some C >>>>>>>> 0, it holds that for any 2 0, X 2 t) < C cxp(-t2 (27 where X Q (cf. Proposition 2.5.2 of [Ver18]).
Our promised result is as follows:
Theorem 9. Let Q be subgaussian. Then, the NEF Q = (Qw)wER is self-concordant and I'q(u) O(Iu)), IR.
As turns out, the linear growth exhibited in the previous result is tight for NEFs with subgaussian base distribution:
Theorem 10. There exists distribution Q that subgaussian such that lim sup [q(u)/u 0.
Again, this shows that even we stay with subgaussian distributions, it would be limiting to only consider NEFs that are self-concordant with a bounded (or constant) stretch function over their natural parameter space.
As for the quantitative relation between the parameters, it can be shown ([RH23)) that if for all u e R. (w) & o /2 then P([X) < 2exp(- /(20"). and if P[X 2 () 2xxp(_-'//CC (20(--(20)")) then for all u R. (u) s "0."
7

---

Generalized Linear Bandits
In this section apply the seff-concordance property of subexponential NET' in order to derive novel confidence sets and regret bounds for subexponential generalized linear bandits. To our knowledge, these are the first such results for parametric bandits with subexponential rewards.
4.1 Bandit model
Following Filippi, Cappe, Garivier, and Szepesvári [Fil+10], we consider stochastic generalized linear bandit (GLB) models 9 specified by a tuple (X,, 2), where X R is a non-empty arm set, @ C Rd is non-empty set potential parameters, both closed for convenience, Q (Qu)eekg is a NEF with base distribution Q. Without the loss of generality we assume that X' is compact subset of the Euclidean unit ball of IRd.
In each round & E N+ the learner selects and plays an arm X, E X. As a response, they receive reward Y, sampled from the distribution QxTe,, where 0. E Rd is parameter of the bandit environment, which is initially unknown to the learner. The learner's goal is to maximize its total expected reward. The GLB is well-posed when
u = fx 2 9) u
holds, which we assume from now on. The condition that U C Uu simply ensures that the reward distributions Qa-- y are defined regardless of the value of (x, 0) X x O. We require the stronger condition U C E4g to exclude the boundaries of the interval Ug. This way we avoid pathologies that arise when parameter reaches the boundary of Ug (e.g.. when is the exponential distribution with parameter X, the mean and variance of Qu grow unbounded as u approaches from below).
The expected reward in round t given that the learner plays X, is E|,, X,] = pXX, The performance the learner will be assessed by their pseudo regret R(T), which is total cumulative shortfall of the mean reward of the arms the learner chose relative to optimal choice:
R(T) Σ (.x - (.)
Here, F, E arg max [4(xT is the arm that results in the best possible expected reward in round. For simplicity, we assume that such an arm exists. We establish guarantees of our algorithm for a subclass of GLBs, captured by the following assumption:
Assumption 1 (Subexponential base). The base distribution Q is subexponential both on the left and the right. particular, Q Erigh((C1, C1) n Eugp(e2, C2) for some c, C, (1=1,1) 1,2) positive numbers. Furthermore, -C2 < inf S supll= < and C1, C2 are known to the learner.
Note that in well-posed GL.B, un < infll S supll < supll.. In light of this, the assumption just stated boils down to whether 0 Uÿ. which, as discussed, free when Ug # 0. Indeed, when 0 Ug holds, inf UQ
< supllo and one can always find positive values cı, c2 such that inf -22 infu S supll ci supllg. Then, from Proposition and some extra calculation
conclude that the Q (ci e ex Mo(ci)) e MQ(-c2)). Since it is assumed that the learner has access to Q, we see that Assumption can be satisfied whenever 0 Uz. which we think is rather mild assumption. We will also for the sake of simplicity assume that the learner has access to So = sup 0| O). S2 infU, S sup2/. These values will be used in setting the parameters of the algorithm. Note that it is not critical that the learner knows these exact values; appropriate bounds suffice. We also assume that the learner given access to an upper bound on the worst-case variance over the parameter space Ut:
Assumption (Bounded Variance). The learner is given L such that supneu p(u) S L..
Note that since the GLB is well-posed, supwew (u)) < is automatically satisfied. Also, there is no loss of generality in assuming L 2 1. A crude upper bound on supaeu ji(u) is Cie/(c S1) Cze/ (02 + S2)3, this assumption is implicd by the previous one.
8

---

4.2 The OFU-GLB algorithm and its regret
Just like the previous works [Fil+10; 10; LLZ17; Fau+20] which considered special cases of the general- ized linear bandit problem, our algorithm follows the "optimism in the face of uncertainty" principle. In each time step, the algorithm constructs a confidence set C, based on past information, that contains the unknown parameter 0, with a controlled probability. Next, the algorithm chooses parameter ir, in the confidence set Ct, and an underlying action X; E X' such that the mean reward underlying X and 0g is as large as plausibly possible. Since μu is guaranteed to be an increasing function (recall that ju()) is the variance of Qu and is hence nonnegative), it suffices to find the maximizer of x: T where (xx, 0) X O. We call our algorithm, shown in Algorithm 1, OFU-GLB (Optimism in the Face of Uncertainty in Generalized Linear Bandits). The main novelty here is that our bandit model makes minimal assumptions.
Algorithm 1 The OFU-GLB Algorithm
Require: GLB instance 9 = (X' 1,,,0,0 Q) for t = 1,2.... do
Construct C2 ② based ((x,, Ys)) and g
Compute (X,, 0t) E arg (x.0xx) x:
Select arm X, and receive reward Y; ~ QXTO.
end for
The confidence set is based on ideas from the work of Janz, Liu, Ayoub, and Szepesvári [Jan+24]. Note that this paper analyzed a randomized method for those GLBs where Uq = IR and sup I Tq(u) < Co. The assumption that Ug IR is restrictive, as it does not allow many common distributions (e.g.. the exponential distribution). Thanks Theorem 7, under our assumptions, suP [u < co follows. Then, appropriate confidence set can be constructed based on Lemma 5, which also extended the corresponding result of Janz, Liu, Ayoub, and Szepesvári [Jan+24]. While the confidence set construction is based on the ideas of Janz, Liu, Ayoub, and Szepesvári [Jan+24], the main steps of the analysis are taken from [AFC21] who analyzed logistic bandits, which are I-self-concordant Our result follows by carefully modifying the proof of [Jan+24] and carefully propagating both the effect of replacing their confidence set with a different one, and the effect of supuete I'q(u) > 1.
This leads the main result on GLBs:
Theorem 11 (Regret upper bound of OFU-GLB). Let ô E (0, 1] and I a positive integer and consider
well-posed GLB model G = (X, θ, 2) and assume that Assumptions I and 2 hold. For 0, O, let k(0.)= m and let Regret(T, 0.) stand for the T -round regret of OFU-GLB when it interacts with GLB specified by 9.. Then, with an appropriate construction of Cr, for any Og Q it holds that with probability at least 6,
Regret - - + +doa(.))
where Ō(.) hides polylogarithmic factors in T, d, L, 1/5 and constants that depend on the base distribution Q.
This result extends the class of distributions for which OFU algorithms with parametric models achieve sublinear regret. Previous results in the literature [Fil+10; APSI1; LLZ17; Fau+20; Jun+21; Jan+24] assume that the base distribution is a natural exponential family with subgaussian tail and prove that the OFU algorithm enjoys sublinear regret. Thus, Theorem 11 extends the class of distributions for which optimistic algorithms enjoy sublinear regret to any natural exponential family with subexponential base distribution.
An essential quality of the result is that makes the dependence of the regret on the instance 0. explicit. Recalling that in a NEF, (u) is the variance of the tilted distribution Qu. we see that the leading term (shown as the first term on the right-hand side of the last display) scales with the variance of the optimal arm's 's reward distribution. In queuing theory, the service times of agents (actions) in an environment are often modeled as exponentially distributed random variables [GN67]. When aiming to minnmize service times (maximize negative reward) with exponential bandit model (with mean function (ax) = -1/2), the variance of the optimal arm's 's service time lower bounds that of the other arms. Furthermore, the dependence
term that is inversely proportional to the optimal variance,

---

is pushed to second order term. In logistic bandits, K can be exponentially large in the size of the parameter set Sg and thus much attention has been focused on mitigating its effect [Fau+20;; Jun+21; Jan+24). Our regret bound also matches the lower bound in logistic bandits given by [AFC21], thus our analysis is tight for this special case.
Conclusions and Future Work
The main contribution of this work establishes that all subexponential NEFs are self-concordant with a polynomial-sizee stretch factor. We then applied this finding and derived regret bounds for subexponential GLBs that scale with the variance of the optimal arm's reward, which is the smallest variance amongst all arm's rewards in problems such as: minimizing service times [GN67] minimizing insurance claim severity (dollars lost per claim) [GKT16].
Our findings also have implications when performing maximum likelihood estimation with subexpo- nential NEFs, which includes rich family of generalized linear models (GLMs). Since the log loss NEF is the sum of linear function and the NEF's CGF, the GLM's loss is self-concordant the sense of (say) [Bac14] whenever the NEF is self-concordant. While this is outside of the scope of our paper, it follows that this family of GLMs enjoy: (t) fast rates of convergence to the minimizer for regularized empirical risk minimization [Mar+19], (ii) fast rates for averaged stochastic gradient descent [Bacl 14] and (iit) fast rates for constrained optimization with first-order methods [Dvu+20), without restrictive conditions bounded responses, which previous works had assume to achieve these results.
One interesting direction for future work would be either deriving matching lower bound on stretch function for subexponential NEFs or tighter analysis that matches the lower bound for subgaussian NEFs. Another potential avenue for future work would be in extending our results to other exponential families, beyond NEFs.
Acknowledgments and Disclosure of Funding
The authors would like to thank Iosif Pinelis for his helpful insights work and Samuel Robertson for reviewing and earlier version of this manuscript. Shuai Liu would like to acknowledge Alireza Bakhtiari for helpful discussions. Csaba Szepesvári also gratefully acknowledges funding from the Canada CIFAR AI Chairs Program, Amii and NSERC.
10

---

References
[AFC21] Mare Abeille, Louis Faury, and Clément Calauzênes. "Instance-wed wise minimax -pptimal algorithms for logistic bandits". In: International Conference Artificial Intelligence and Statistics (AISTATS). 2021.
[APSI]]
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. "Improved algorithms for linear stochastic bandits". In: Advances in neural information processing systems (NeurIPS) (2011).
[Bac10]
Francis Bach. "Self-concordant analysis for logistic regression", In: Electronic Journal of Statistics (2010).
[Bac14]
Francis Bach. "Adaptivity of averaged stochastic gradient descent to local strong con- vexity for logistic regression". In: The Journal of Machine Learning Research (JMLR) (2014).
[BFR23]
Blair Bilodeau, Dylan J Foster, and Daniel M Roy. "Minimax rates for conditional density estimation via empirical entropy". In: The Annals of Statistics (2023).
[BLM13]
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
[Bro86]
Lawrence D. Brown. "Fundamentalss of statistical exponential families with applications in statistical decision theory". In: Lecture Notes-Monograph Series ( (1986).
[Dvu+20]
Pavel Dvurechensky, Petr Ostroukhov, Kamil Safin, Shimrit Shtern, and Mathias Staudigl. "Self-concordant analysis of Frank-Wan Wolfe algorithms". In: International Conference on Machine Learning (ICML). 2020.
[Fau+20]
Louis Faury, Marc Abeille, Clement Calauzenes, and Olivier Fercoq. "Improved opti- mistic algorithms for logistic bandits". In: International Conference on Machine Learning (ICML). 2020.
[Fil+10] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. "Parametric bandits: The generalized linear case". In: Advances in Neural Information Processing Systems (NeurIPS). 2010.
[GK98]
Charles M Goldie and Claudia Klüppelberg. "Subexponential distributions". In: A practi- cal guide to heavy tails: Statistical techniques and applications. Birkhauser Boston Inc., Aug. 1998, pp. 435-459.
[GKT16]
M. Goldburd, A. Khare, and D. Tevet. Generalized linear models for insurance rating. Casualty Actuarial Society, 2016.
[GN67]
William J. Gordon and Gordon F. Newell. "Closed queuing systems with exponential servers". In: Operations Research (1967).
[Jan+24] David Janz, Shuai Liu, Alex Ayoub, and Csaba Szepesvári. "Exploration via linearly perturbed loss minimisation". In: International Conference on Artificial Intelligence and Statistics (AISTATS). 2024.
[Jun+21] Kwang-Sung Jun, Lalit Jain, Blake Mason, and Houssam Nassif. "Improved confidence bounds for the linear logistic model and applications to bandits". In: International Conference on Machine Leurning (ICML). 2021.
[LLZ17]
Lihong Li, Yu Lu, and Dengyong Zhou. "Provably optimal algorithms for generalized linear contextual bandits". In: International Conference on Machine Learning (ICML). 2017.
[LS20]
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[LYJ24]
Junghyun Lee, Ye-Young Yun, and Kwang-Sune Jun. "A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits". In: Advances in Neural Information Processing Systems (NeurIPS). 2024.
[Mar+19] Ulysse Martcau-Ferey, Dmitrii Ostrovskii, Francis Bach, and Alessandro Rudi. "Be- yond least-squares: Fast rates for regularized empirical risk minimization through self- concordance".. In: Conference on Learning Theory (COLT). 2019.
[ML09]]
Carl N. Morris and Kari F. Lock. "Unifying the named natural exponential families and their relatives". In: The American Statistician (2009).
[MN89]
P. McCullagh and J. A. Nelder. Generalized linear models. Chapman & Hall / CRC, 1989.

---

[Mor82] Carl N. Morris. "Natural exponential families with quadratic variance functions". In: The
Annals of Statisties (1982).
[Nes04]
Yurii Nesterov. Introductryy Lectures on Convex Optimizatiin A Basic Course. Springer, 2004.
[NN89]
Yurii. Nesterov and A. Nemirovski. Self-concordant functions and polynomial-time methods in convex programming. USSR Academy of Sciences, Central Economic & Mathematic Institute, 1989.
[NN94]
Nesterov and A. Nemirovski. Interior point polynomial algorithms in convex progrum- ming. Society for Industrial and Applied Mathematics, 1994.
[NT08]
Arkadi S Nemirovski and Michael Todd. "Interior-point methods for optimization", In:
Acta Numerica (2008).
[OB21]
Dmitrii M. Ostrovskii and Francis Bach. 'Finite-sample analysis of M-estimators using self-comcordance" In: Electronic Journal of Statistics (2021).
[RH23]
Philippe Rigollet and Jan-Christian Hütter. Iligh-Dimensional Statistics. 2023. arXiv: 2310. 19244 [math. ST].
[Rus+21]
Yoan Russac, Louis Faury, Olivier Cappé, and Aurélien Garivier. "Self-concordant analysis of generalized linear bandits with forgetting". In: International Conference on Artificial Intelligence and Statistics (AISTATS). 2021.
[Saw+24]
Ayush Sawarni, Nirjhar Das, Siddharth Barman, and Gaurav Sinha. "Generalized Linear Bandits with Limited Adaptivity". In: (2024). arXiv: 2404. 06831 [cs LG].
[SPL23]
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. "Dueling RL: Reinforcement learning with trajectory preferences". In: International Conference on Artificial Intelligence and Statistics (AISTATS). 2023.
[ST19]
Tianxiao Sun and Quoe Tran-Dinh. "Generalized self-concordant functions: A recipe for Newton-type methods". In: Mathematical Programming (2019).
[Ver18]
Roman Vershynin. figh-dimensional probability: An introduction with applications in data science. Cambridge university press, 2018.
[Wai19]
Martin J. Wainwright. Highhddmenssioal statistics: A non-asymptotic viewpoint. Cam- bridge University Press, 2019.
[WJ08]
Martin Wainwright and Michael Jordan, Graphical models, exponential fumiliie,,, and variational inference. Now Publishers, Inc., 2008.
12

---

A Extra notation
The following extra notation will be used in the appendix: For vector x E Rd. we let ||>||| denote its norm and for positive definite matrix IRdxd, we use ||a]|ar Vo"" Mæ to denote its M-weighter mn-nrmm.
B On subexponential (or "light tailed") distributions
first prove Proposition 6, which we repeat for convenience of the reader:
Proposition 6. Let c1, C > 0, Y Q and assume that EE 0. If
PPY 2 8) Ci exp(-cit) for all 2
then for any 0 < X <. c1 (A)= 1+ C₁ cx(a-)) Furthermore, for any c > 0 such that MQ(c) < co,
P(Y S (c(c)e-et holds for all / ' 0.
We follow the proof of Theorem 2.13 from the book of Wainwright [Wai19].
Proof. We start with the second part. For this let t 2 0. Then, by Chernoff's method, we have
P(Y 2 1) = Elec*|e Je Mo(c)e
The first part requires more work. Let us start by bounding the p-th moment of the positive part of Y,
which we denote by Y+ (hence, Y+ max(Y,0). 0)) We have
B|
P(Y 2 u)du
p
P(Y+ 2 t)t8 dt
(change of variables with t²)
=p
P(Y 2 dt
(for t > 0. (Y+ 2 t ( t})
$ Cip
c coilpp1 dt
(assumption on Y)
Cip
I & Jo
c oun du
(change of variables with v = c1
CiPT(P 1)
(definition of the I function)
&
C マ p!
(property of the I' function)
Now let 0 < X < ct. Since Y < Y., have MQ(A) = EllAAY S B[e Hence, by the
power-series expansion of the exponential, we get
MQ(A) < E AV+]
VP
=1
x
p!.
2=2
1 P
$1+C Σ
9
p=2
A
$1+G
11 -9
We note passing that since < cr 1 + 1 -ー
5 C1 - That Eq. (3) implies that
MQ(A) S 1 + C1,²Ax also be obtained by refining the proof of Theorem 2.13 from the book of Wainwright [Wai19].
13

---

C Proof of Theorem 7
For the convenience of the reader restate the theorem be proven:
Theorem 7. Let Q E Engh C1) ( for some positive constants C₁ = 1, 2. Then, the NEF (Qu)ueu is self-concordant, Moreover, the function : - R defined by
2eCic1
ub
+ Go(C1, C1,
if0 < <
I(u)
2
22
+ Go(C2. 02,
if c2 <uco,
oxt
is stretch function for the NEF Q, where Go(MI, M2, my, m²) is polynomial whose coefficients depend on Q.
Note that the function as defined above is non-decreasing on UN and non-increasing on U
The actual form of Gq is as follows: let b, 17 > 0 be such that Q(I + p(0), -a + and -a < Then,
3 b 2 a²n
204
m3m,,M9 M3 + 81M + 9M2m
682
GM M2, m. m2)
(8)
m M
m2
We note in passing that these values are not controlled by the tail behavior of the base distribution Q.
This can be seen, for example, by considering (dy) (1 n)[(yy 2 0)e dyy + ne pe=" (dy). Tedious calculation shows that lim I'q (u) (b(b) as b + co. And because Q E Eright (1, 1) (ic 1), this shows that the tail behavior of Q is indeed insufficient to control the behavior of I'Q.
We will prove this result in three parts: (i) Var(Q) 0 (id) Var(Q)
and 21 (0, (iii) Var(Q) and 4 = (-c2,0) 0). The result follows from combining these cases.
The main work is to prove the result for U c1), which is done in Proposition 13. Case (iii) handled by "reflection around the origin" (Corollary 14). Case (i) is handled Lemma 12 by showing that Qqq = if Var(Q) = 0.
We start with case (i), the degenerate case when the variance of Q is zero Lemma 12. If Var(Q) = O then UQ R. Qu = Q for all u E R, and l = 0. If Var(Q) > 0 then j is strictly positive over the entire set Ug-
Proof. If Var = 0, then Q is Dirac on some {u}. Then for all E R, MQ(u)= = exp(ue) < oo hence 4Q = log Mo is supported on R and
Molu) exp(ur) =1 i
Qu(A)
otherwise.
Hence Qu = Q and Q = (Qu)uER is trivially self-concordant with the stretch function defined to be To= =Q=0. 0.
For the second part, by Proposition 2, we have that juu) fly p(u))²Q.
0. We
will show ju(u) # 0 by contradiction. Assume there exists un E Ug such that ju(uo) = f
(( (dy) then it follows that Qno (dy) Dirac on {u(un)), which implies for all
E (TR)
{ (Q(
{u(uo)) g A
Q(A) =MQ(u)) Quo (A)
to
otherwise
where B(R) denotes the Borel sets on R. Then it follows that Q(dy) is also Dirac on IR which contradicts that Var(Q)= >
Consider now the case when Var(Q) > 0. By the result just stated j is bounded away from zero over U& and hence it is safe then to define T with the ratio [A(=)].
p(x)
[i(w)]
[u) i(u))
u ug.
14

---

Thus, in order to show our result, it suffices to show loQ S I with the function I' as stated in the theorem. Thus, we will study Lq.. First, notice that for all E Ug by Proposition 2,
- (()))( Iq(u)= f(y - (()))((Q(Q(())))) [ (
Let us now state the results that concerned with cases (ii) and (iit) mentionned above. For case (ii), i.e., when U = [0, c1) we have the following result:
Proposition 13. Let Q E (c1 C1) n (cen C2) and U = [0, c1). Define :: : + R+ by
ub
|u/6
204 + 6u
81C₂ + 9C2u26² (u + c2)
T(u)=
200
+
2
C1
+ 11
a²n1
2
ub
S 2
200
+
+ Go(CC, (2),
C1
where cu = C1 01 ec Then,for for appropriate values of 1), a, b> O that depend on the base distribution Q. we have Q - I over U.
For case (ili), i.e, when U = (-C2, OJ, we have the following result:
Corollary 14. Les Q E Eci C1) n (cg C2) and U = (-cz, 0). Define r ::44 + R+ by
3
1
Jubb
lu|b
1
204 + Gu212
81C1 + 999 u02 (lul c3)
T(n)=
200
+
+ a²n
2
C2
|u|
C2
C1 |u]
o
3
bubb
<
2cu
+
+ GQQ(Cz C1,
2
C2
jul
C2
ju
where cu = C2 02 e. Then,for for appropriate values of 17, b >> O that depend on the base distribution Q, we have l'Q S I u.
C.1 Proof of Proposition 13
The key idea is to convert ji-) and ja(-) to third and second central moments respectively by Proposition 2 and bound the third central moment in terms of the second central moment (variance).
We start by an elementary observation that says that the seff-concordance properties of a NEF do not change when the base distribution is shifted by constant:
Lemma 15. Let Y Q, E R and define Q+o be the distribution of Y + Then, UQ Ultt
MQ+ (u) = we Mu(u) for all R. and I'Q l'qte (here, take U UQ = Ug++).
Proof. By definition MQ(u) = Ee"Y and (M) = (e++))) Hence,
(u) (Y++ "" e MQ(u).
This shows that Ut Mo+ and that the desired relationship between Mo and Mo- hold. Now, from the definition that the CGF is the logarithm of the MGF, follows that v = ue +e (o( Hence, Vh रे and viott Liq. which implies that Ioq -q-..
Thanks to this result, from a bound on the self-concordance function of centered distributions, we can deduce a bound on the self-concordance function of the non-centered ones.
We thus first work on establishing the bound when Q is centered.
Since the theorem statement holds trivially when the variance Var(Q) of is zero, we will also assume with no loss generality in some the results below that Q has positive variance.
Lemma 16. Take distribution Q with zero mean and positive variance. Then, there exist nj > 0 and 0 < < b distribution dependent constants such that Q[[-b, -al) 2 n.
15

---

Proof. Since ja(0) = Var(Q) > O, there exists > 0 and > 0 such that > a. As
- Q((-00 -z])) 0, we can find some > 0
(((-00,-0) - 2
This implies:
([1bb-al) N -
The lemma thus holds with a and 6 described above, and 1 2.
Lemma 17. Take distribution with zero mean and positive variance. With n7, a, b in Lemma 16. for all u E Mg it holds that
ub
iuu)= 2 a²n MQ(u)
Proof. For b described in Lemma 16, have:
[ (y u(w)) 2
(v - u(u)))
(y =(())² exp(uyy
Q(dy).
MΦ(u)
exp(-ub) ub)
[ Q(dy).
MQ(u)
a'e-ut
Mo(u)"
The first inequality holds as (y 2²)))² non-negative; the second as y(u) increases with u; third as - < -a ((0), (0) 0 and 2 0; and the last one by Lemma 16.
For the upper bound, we present lemmas that bound the (upper and lower) tails of Qu and the mean u(u).
Lemma 18. Take Q E Ecigto(Ci, Ci) centered distribution. Then, for all 0 S a < ei and / 2 0, we have
Qu ((t, +oo)) < Cie 1e1-u MQ(u)
(1
u
C1
Proof. The inequality is trivially satisfied when 0. Indeed, in this case Q Qo. MQ which together with Q E Eright (C1, C1) implies the inequality.
Let us now assume that 0 < C1. Let v 0 be constant to be chosen later. Then have that
(Q())Qu((ttoo)) =
enVQ(dy)
++(k-1je
Q
14kv
u((+ku+e) tto Q(dy)
H+kr
u(t+kk+uu Ci
Oie ai(to))
k=
-e (01 (3t av
e (c) ujkk
km0
16

---

We choose == 1/u > 0. Then can be upper bounded by
(Q(,))Q(((,o3))) oo)) x Cie (a--jj
A=
= e
(c1-
c
I Cce.e-la-uu
1
u
C1
where in the last inequality, we used the fact that for all x 0, c
Remark 1. For Q centered exponential distribution Exp(c) with rate parameter c, the moment
generating function is MQ(u) = - c-w' On the other hand, Qult, oo) e (e-wu So Lemma 18 is order tight in its dependency on c- u. Lemma 19. Take Q E Eien(e2, C2) centered distribution. Then, for all u. u 2 0, we have
Qu ((-o0, MM(u)
C2e C2e (wwte))
Proof. We again separate the 0 case. When = 0, Q Qo. MQ and the inequality is equivalent to Q E Eten (c2, C2).
Consider now u > 0. Then,
Ma(u)Qu (0000((1000)) (1-00--)).
Qu)Q(dy);
[' Q(dy),
Se uu
SCge -up-euter -ut-est
Lemma 20. Take Q E Erggh((1, C1) with zero mean and positive variance. Define co C1 C1 e. Then, for all 0 I u < C1, it holds that
== ==x(0)= S u(u) S co
Proof. For 0, p(0)= 0 which satisfies the inequality. We now consider 0 < c1. We have
Qu ((v. +oo)) dy - S Qu (0-000,-1)) dy
puu)=
Qu ((y, +00)) dy.
By Lemma 18, this implies:
p(u) s
Cee
(a--
C1
dt
MQ(u)
ci -
Cie
C1
1
(y(u)
C1 1
C1 - u
CiC
MQ(u)
C1 u
By Jensen's inequality, Mq (u) Egle"X|
> e"BolY)
1, finishing the proof.
17

---

Proof of Proposition 13. As noted beforehand, since the statement holds trivially when the variance of Q is zero, we assume is positive. By our discussion beforehand, we also assume first that Q is centered, so p(()) = 0.
Let Y Qu- Take B 0 constant to be optimized later. We have
/ ly plu)l Qu(dy)
32 P (|Y p(u) 2 dt,
362 (|Y - x(na 2 2) dt
31 P(Y - ulu)l 2 1) dt.
(1)
The following bound holds:
i1 S3B / LP -m(u] 2 () dl,
3B
ju(u).
We also have:
400
(ii) <
312 PP (V pp(u)= 1)dl di
PY S - u(u))) di
(ii.a)
(12
Set B = 2cg
+
wh
+
ub
and B'
2co
1
Then we can upper bound (ii, a)
c1-
w4-22
c1-8
using Lemma 18.
(ii,a) < co
312 c (cr - ()(++)())
(Q(u)
B
Cn
31 e (cr u)) dt
(u(u)
Che ub
3t
(01 (o1-u)(t-
L.
- dt
(4(
C1
Qhe -ue ub
1
000
ub
3
t+
e (c1-u)) dt
Mq(u)
C1
u
6cge ub
1
ub
2 +
(c uit dt
MQ(u)
Ci
B'
Ci
u
6cbe ua mb
000
ub
2e
(c) u)t
u)t
dt +
- (cs
u)t dt
(Q)
m3
u
JB
v
(iii,)
(165,b)
18

---

where in the third inequality we used the fact that (a + 6 - 2a² + -2b for
all a, E R and that
B' < B
ub cr-
We now bound (iii, a). We have that (e(ci u) = 2c0
and
(ilt,a) a)
13 (1
(B'(c) w) 1]2 1) _
2
B ( (B'(c - uu) + 1)2
(c1 u)4
(a u)
(B'(cc - -ui]² -1)]²+1)
$ (c)
u)a
200
(4-²)
4
+1
(
u)
C1
u
16c
2ro
4
-200 1-
(cl
u)
(c)
- u)
16
o
c0
260
+ 4
1
c0
c - ))
(a-w))
1
200 6I-1
6
c
32
(x 2x < 2 and
I'e 2x s 0.5 for all x 2 0.)
Similarly, for (iii, b), we have that
2
u222
(iii, b)
(er (ca-u)te u)ddt
01 1 B'
(c1 - u)?
2,212
e
BB'(c--u)
(a u)3
C1
20²
200 (T-t)
(c) u)1
2u218
Co
-20((c)-
200
6
cj
Ci 1 U
u u2
0.5 for all x 2 0.)
o/
Putting the result together, (ii, a) can be upper bounded
(ii, a) - 6abe ub
32
2
2²
+
+
MQ(u) e e-u MQ(u)
c0
(204 + Gu2b2
By Lemma 20, B 2 ulu) +
ub catu'
Hence By Lemma 19 we have:
(ii < C2
to0
(u4eo(()))))- dt,
Mo(u)
Oze-wr
C2e (I+te))(-u(u)) - ) dl,
MQ(u)
B
902e -ub
100
(p ( u(u)² + ( ub )² + C2
2) ") e (utrr))
MQ(u)
BBuu(u)-1tt
We now focus on
+oo
ub 2 (w+oo)) dt
Le (u+oa))
u(u)2e (u+oo)) ((u))e-(u+oo)))e 1t u(w) u 02
B- B-p(u)=
ub
2b B (B-p(u)-
nb utog
0402
(1
(Ke
(6v,e)
19

---

By definition of B, we have that B pu(u)
ub utez
c a1-
B". We then have that
(iv,a) <
Pe-lutt)ddtt
B"
e (ute()ter)
(BB 02) + +1² +1)
(u 0g))
2 (w+o))
2e B"
(B + +22) 11)
(u + 02)3
4e - (u+oz)
(B" +1) +1
(u + 02)3
4
(B (B" + 0z)] + =BBB(u+)z)
uu + 02)
8
(u + 02)
For (iv,b) note that B" 2 p(u) by Lemma 20 and we have that
(iv, u(u)² (w+ea)
B
B"(ute))
(u 02)
(u
+ 02))²2
8² (u+es)
(u + 02)
(u + o2)3
For (iv, c),
u²b²
(iv, <
e (u+r2))
(u + 02)
B"
1212
BB"(ute))
(u + )2
C2
22b2
(u+ 02)3
Putting bounds on a), (iv, b) and (iv, c) together, we have that
(ii b) S 9C2e uub 9 221
e-u 81C2 + 23
Mạ(u) (u+ 02) S MQ(u) (u 02)
Combining the bounds on (ii, a) and (ii, b) with Lemma 17 we get:
(ii) S
204 6u2b2
81C₂ + 902u2b2
iuu) ann o
(u
2
Chaining the result with the bound on together as well as the choice that B 220
a--
+
we obtain
uteg
ji(u)
3
1
ub
1
204 + 6u
810 + 9C2
200
+
+
i(())
2
C1
C1
2
a²1
c
(u+ 02)
3
ub
ub
204 + be71
81C2 + 92
<
2cp
+
+
2
C1
C1
02
a²n
(a1 C1 -)
=Go(Cr.Cuer.c))
20

---

Let us now study the case (0) * O. and -a < O. With Q- the centered version of Q, this gives - ( (l-b, -al) 17. We have just shown that for all u ();
Let a, b, > 0 be such that Q( (((),, -a (())))
1
2
ub
+ ub
I TQ-uco) (u)
2co
+ c2)
C1
u
C1 u
u + 02
By Lemma 15, we have I
Q
mio)
Qq. hence:
3
1
ub
ub
[Q(u) -
2c0
+
+ C2,(C,C2,,
C1
u
C1
u 02
C.2 Proof of Corollary 14
Lemma 21. Let Y ~ Q, and Q let be the distribution of -Y. Then Uq = -Uq- and for any E Ug. we have
To(u) (-)(
Proof. Recall that if Q has zero variance, lQ= = 0 and hence the statement is trivial. Otherwise, for Ug. (u) 1 (w)l/vQ((u) Now, for E R.
M (v) = Bie(- 1) = MQ(-v).
Hence, Uq -Mo- and for any E Ug. (1) = 1/-00/110 (-r). Taking derivatives of both sides,
cQ(v) = -
( viq-(-t);
()(v) - (-o)
which immediately implies the statement, noting that the variance of Q is positive if and only if the variance Q is positive.
Proof of Corollary 14. Assume that Q E (Ci C1) n (c2, C2). Since the statement holds trivially when Var(Q) = O, assume Var(Q) > 0. Then, Q E (rggh C2) n (ci C1). We then get the stated result by applying Proposition 13, combined with Lemma 21. To be more specific, for all u E (-c2, 0J. from these two results it follows that
TQ(u)= To- (-u)
1
2
bu
204
6u262
81C1 + 9C
200
+
+
C2
12
02
[2]
C1
+ 11
a²n
a
(u + (1
1
lu|b
204
bogb2
81C
9C 152 ci
2cp
b
02
1u
C2
a²n
c
where = C2
C.3 Proof of Corollary 8
Let Q be a regular NEF with base distribution Q. By definition, this means that Ug is an open interval. Take any Ug. There exist some >> 0 s.t. Mo(u e), MQ + e) < xo. We also have:
/
MQ(u +)
exp(ex))xp((x))) exp(uy)
(QQ()
(e.
21

---

Similarly, (-c(
Molu-e) Mę(u)
By Proposition 6, this implies Qu Eiet
MMlu-r) Me(a) .6)
Mofa-e)
Eright
MQ(u) .
D Self concordance for subgaussian base distributions
For the convenience the reader we restate the theorems to be proven.
Theorem 9. Let Q be subgaussian. Then, the NEF Q (QW)uER is self-concordant and TQ(u) O(ul),, IR.
Theorem 10. There exists distribution Q that is subgaussian such that lim sup (')) 0.
We start by introducing some notations reminiscent of the ones used for subexponential distributions. Recall that a centered distribution Q is subgaussian if and only if for some c, C' > 0, it holds that
at 2
P[| 2 1) < C expp(
for all 2 0
(10)
where ~ Q. Let
C) X EX satisfies Eq. (10), where X ~ Q}.
This definition is very close to that of Ergght In words, G is the class of distributions over the reals whose left and right-tail display a subgaussian decay governed with the rate parameter c 0 and scaling constant C O.
For the interested reader, also report here without proof some classical results the quantitative relation between the MGF and the tail bounds of subgaussian distributions. Details can be found in the textbook [RH23].
Proposition ([H22)). Ifror all u E (RM S 222 then P([X s 22xp((((22(2 and if ([X] 2 t) < exxp( (20?)) then for all u E R. MQ(u) s to'n
D.1 Proof of Theorem 9
Lemma 12 still holds for Q a subgaussian distribution, hence the theorem holds trivially for A(0)= 0. Lemma 15 can also be applied for Q subgaussian distribution. Thus, as in the proof for
subexponential distributions, the first step is to show the result when p(0) and ji()) 0.
Note that the lower bound on ju(u) of Lemma 17 still holds when ju(0) > We turn to upper bounding ly (u The following Lemmas are first steps in that direction.
Lemma 23, Take Q G(c C`) a centered distribution. For all u 2 0 and & 2 ( + 1) a + we
have:
e,
Qu ((t, +00)) x
e-
Mo(u)*
where e = CC !
22

---

Proof. We have
Qn (lt,
enuQ(dy),
(th+)
euIQ(dy)
(uttk-l1) plthti
Q(dy),
l+b
k=0
eu Q (lt + k; +00)),
k=
-سيييي -
<
(1I)
k=
The first inequality holds as u 2 0, the second by subgaussianity assumption. Ast (2 + 1) u + 4 we have S f and:
t² 2 1 +1) ut
4t
4 (t 1)u.
(12)
2
This implies u(t 1) S t top of ft. Then
u k) S C (12 + kt) - (t+ (t+
4
4
Reinjecting in Eq. (11), we get:
400
Mo(u)Qu (0,)+0)) S0'
Σe
c(t+2)
<Ce
k=0
42
<Ce
1+
e
dr
0
<C
22
Lemma 24. Take Q E (c, C) centered distribution. For all u, 2 O, we have:
C ut at
Qu (1-00, (()) s
MQ(u)
Proof. We have that
Mo(u)Qu ((])),-))) 1 e Qu)())))
Se uut
Q(dy),
<Ce -ut-at ct2
(13)
where the last inequality holds by subgaussianity of Q.
23

---

Lemma 25. Take Q E G(c, C) centered distribution. For all u 2 0 the following holds:
- + u + + Cze du2
= ==)(0) S uQ(u) -
where E3
v Vc
E1
Proof. We have:
/
dy dy- S Qu ((-00x0))) dy
pd())
Qu ((y, +00)) (cy))
-
Qu (yy.+ tool)
0
4
4 =+ +
+
((2t))ate
Qu (uu, dy.
By Lemma 23, this implies:
muw)== -
+1
u
4
e too
ord dy
c
MΦ(u)
(S+1)utz
((t))(()))) ((+t))ut))
4
Eie
ap dy
+1
u +
e
dy
MΦ(u)
4 +
e c-
(
+1
a
+
dy.
c
Mạ(u)
By Jensen's 's inequality, MQ(u) = Eoleuy 2 e"RaiM Noting that f0= e
- dy
S
v
terminates the proof.
Proof of Theorem 9. As previously noted, we first show the result when (d and ji(0) 0. We start with u > 0, then by Lemma 21 will extend the bound to < 0.
Take 0 and B > 0 constant be optimized later. We have:
/ Y ( , Quldy)
32 P (\Y (n( 2 t) dt,
B
S
31 (|Y - um(()) 2
31 3/ - pe(")) 2 f)
(
The first equality classical result on the relationship between moments and tails of r.v., see for instance Exercise 1.2.3 of [Ver18). The following bound holds:
(i) <3B
LP (IY mQ(u)) 2 1) dl,
3B
2 uQ(u).
(14)
We also have:
+00
(it)
P(Y - (u( 2 2) di +
31 P (V S - (Q) dt.
(6.b)
Set B = uQ(u)= + (
+ 1) a + 4 b, where was defined Lemma
B> +1+
by Lemma 23, we have:
24

---

+00
(ii,a) a) -
31
pu ((1, +o0)) dl,
B
Ci
a²
$ MQ(u)
32 5 dt.
B
= 3ē,
4.00
dB+00 (B + +t)²
dt,
MQ(u)
6E aB?
(B3 + +te ml
dt,
dt,
MΦ(u)
2 ( e
+00 o
(B² +
dt,
MQ(u)
6ei
V
(B2
(B²
+
2 cB²
MQ(u)
where the first equality holds as for any a > 0, using integration by part we have that
at dt 2a
(15)
Denote B' = B - uq((u) (: (1+1)um
+ b. By Lemma 24 we have:
(i - / +00
312 C2
c((l--o((u)- st--gg(w)? dt,
MΔ(u)
B
3C, too
(Q+)) E -ut a² dl,
MQ(u) B
3t2e -t2 to0
(1+ (L+ e 3222) ddl,
JB.
32 -bu bu
tt
(1+ B' + +uoll)) e- dd
di,
MQ(u)
5
6L 4 -bu bb
2
too
(12 B²) E x dl,
22
MQ(u)
6 6L -bu bu
( |
1
e d dl
MQ(u)
c
6e Hu
to0
+ B2
CzE 2t2
dt.
MQ(u)
where in the second line we use change of variable; third line we use the fact that B' > _u b. hence e -ut < e BBu e -ub for all t 2 B'; fourth line change of variable and the fact that -(a + b)2 < -a² 1² for all a, b 0; fifth line the fact that (a b)²² 2a² 2b for all a, b R: sixth line Eq. (15); and seventh line B' > =..
Combining the bounds on (ii, a) and (ii, with Lemma 17 we get:
(ii)
6
C2 + B²) E 122 + (2+ 1B E-
c0a +ub
<
a
As B > Lu + b. we have
cBa -
+
ub
2 1u² This implies
(ii)
6(Ea + Ca)
2 + BB2 e -
<
nq(u)=
a²n
25

---

With Equation 14, we get
TQ(u)= 1
6(Cs + Es) (2
B²
e u²² +
3B
a²n
2
By Lemma 25, uQ(u)= S ( + 1) + _ Cz. which implies:
4 +1
B s 2
+ +b+ Ez.
c
c
For any constants wi, W2 > 0, we have wi u² -uussa
S
u. u. This implies that for u > 0:
Ven
( = O(u).
Note that if Q E G(c. C), with Q the distribution of -Y, Y ~ Q, we have Q E [(c, By
Lemma 21, that implies:
rQ(-u) Te- O(u)
Ou))
Therefore, for u E R:
I (w = O(24).
As, by Lemma 12, IqQ constant for p(0) remains now only show the theorem if ((0) # and (a()= > 0. We have just shown
I Q wos (u) = O(lu)),
with Q-a(0) the centered version of Q. by Lemma 15, we have l'Q l'q-nco). Hence, for any Q E ((c, C):
(u = O(ll))
D.2 Proof for Theorem
We construct distribution Q s.t. for any > 0, we can find some u > s with
['v (()) Qu Jv ((u)))Qu(())
0.038u.
Let Q the base measure be
Q(dy)
Σ 121
prózi (dy);
(16)
with
Ci eexp(-49) p. exp(-= -3 41-1) if is odd,
if is even,
(17)
where C₁ is a normalizing constant. By definition, we have that Qu(dy) = Ei>1 g:dzi (dy) where
Maluj exp(u2") exp(-49)
C
if l: is even
[M)(u) exp(u2t) exp(-3 4h-1) 0k
(18)
A: is odd.
BY - for positive even number large enough and u = 2i+1, By B[Y-u(m))
We are going to inspect definition, we have that Qu (dy) Eizi g:dge (dy) where
C.
exp exp(2'+ (2++++1) exp(-44t)
if l is even,
4
Ma(u)
G
exp(2++k+1) exp(p -3 x 4h-1)
if l: odd.
(19)
26

---

First, we remark a few simple equalities and inequalities that will prove useful in the subsequent computations.
Not that (U==2² -U=20 = -Mo(u)
C1 et,, hence:
P P(U = 21+1)
- e -3x1'-1'
(20)
PUU = 21)
4
This implies:
4
PUU 2-) S 5'
(21)
and, combining with Equation Eq. (19),
P (U 2/)
2 -10 -4
if is even,
(22)
P (U 2
2e2 -3x4/-1-41
if j is odd.
From this last equation we get upper bound:
P (U = 2 F 2
S
(23)
The two next Lemma combined show that for any even 2 4, 1.24 x 2' S p(u)) S 1.26 2¹.
Lemma 26. Let i 2 4 be an even number and 2 For random variable U Qu(dy), it holds that:
u(u)= > 1.24 x 2'.
(24)
Proof. Consider j < i even. By Eq. (23),
P (U = 21)
< e 2 3344-1-44
P (U 2
Denote f1()) 1++++1-33 3 4 4', The monotonicity of the right hand side, efi the same as fi()). Take derivative of (j), we have that
НО) 2 2 In - 3 4'- 1n4 = 2 (2 In 3 x 2 In 4) 2 In 4(2 3 x 2 Since i > j we have that f1 2 0 for j [0, Hence the right hand side increases with as j S i we have that
P (U 22)
Se -3x1
(25)
P (U = 2
This implies:
(U <
Ejei PU (UU=()) =20)
< (i 1)e -1e-1)e-3x1-
3x1--2
- 0.001.
(26)
P (U = 2 PUU= 2')
We now prove the lower bound on the mean.
p(u)= IP 2 = 2') + 2PU > 21+1)
-PU = 2 = 2') + 2' (PUU < <2 P(U = 2t) PPU = 2(+
22' + (2 2 P(U = 2 - 2P <1)
[PU = 2
P(U < 2')
=2' + 22'((U 21)
P(U 21)
IPU 21)
L [L_ -0.01 0.001 IP(U 2¹)
22' 2
>1.2 x 2
where the fourth line holds because of Eqs. (20) and (26).
27

---

Lemma 27. Let be positive even number and = 2 For random variable U ~ Qu(dy), it holds that:
r(u) S 1.26- 2
(27)
Proof. By Eq. (23), for any 2 i + 2, we have:
P (U 2
S -xa = 12----((xx0 13x22" --x2
-3x40-1-2---
P(U = 2
5e-1'-21~1
(28)
This implies:
Pa (U 2))
Σ 1iit1
20
Se Σ
22-11-1
1
2 e
20
e-.
PUU 2
jiit1
j=4
We turn bounding
Ej= 220-21 :
Σ
26 -2/-1 2
2- e 2/-1
2 e 2²
=2
1=1
1=1
1=3
2
2 22 dr,
= 2
dyy. y In 2
ye
2
e ln2'
where the second inequality holds as -- is decreasing for >> 0. Hence, for any i 2 2:
Σ 81+1
2 Pu (U= 2
2 4' < 2'.
(29)
P(U 21)
e 111
100
We are now ready to upper bound Pu:
Nu - 2' < 2") + = =2) 2 = 2(+1) +
Σ 2P((U = 22)
j>i+1
22'P(U 2
PPU 2
+ +1+ 2
P(U = P(U=2ith 2
1
Σ
2
Pa (U=
2 P(U 2
P(U 2t)
2
P(U= 2
jbit1
2 (1 2 x 0.001 + +1+
1
1
2 100
1.26 2
where we get the third inequality from Eqs. (20), (21), (26) and (29).
28

---

Proof Theorem 10. Let U ~ Qu where u = 2 for i 2 4 an even number. We first derive an
upper bound on the variance EE[U p(u))²] < B(U
E 2 PPU < <2) + 2 P(U = 2) + 22it2 PPU = 2-
2U = 2
gبit1
P(U < 2 P(U 2
+ +1+ 4 P(U = 1
P(U = 2')
s P(U 2
2
P(U 2))
2
P(U 2
j>i+
$2 2 4 5 0.112+1+14
2 -25-1
(30)
2 j2it1
where the last inequality is obtained from Eqs. (20), (21), (26) and (28).
We inspect the infinite series in the above inequality Note that 2 2/-1 is decreasing for 2 1.
Σ
2211-211
3
4
Pe-2
13141
522
100
< 4
4 E
-2"
dx
00
4
! dy
J
y yln
12
In 2
For all 2 1, it follows that
e 4
12
5 0.02.
22r
In2
c²
Plugging into Equation 30, we have:
((U-)(n))²? S 1.7 x 2
(31)
On the other hand, by Lemmas 26 and 27, we have that
0.74 2
if 2 2
Alarg 0.26 2
if =
U U- U-u(u)2 2
Amedium
if < 2 -126 2
Anmall
Then we can lower bound the third central moment EU - [uu)l3)
BI(U- - u(w)) 2 P(U 2 ) + PUU = A + +P < A2
= [1 P(-P(U--1)) = 2 - PUU < <2')] A Sarge + P(U = 2 + +P(U < 2
(0.74- -PU PUU (0) 2))3 (0.26 2 PPU < <0) 2 + (1.26
P(U
> (2 [0.743 -..6..7779.066))--
- 0.8 x 0.001 +.0749)
M 0.063
where the third inequality holds by Eqs. (21) and (26). Combining this last bound with Eq. (31), we obtain:
[ m(u))3]
0.065
2 0.038u.
E - p()))2]
1.7
29

---

E Bandit algorithm
In this section, we present our analysis of Algorithm The section organized as follows. In Appendix 1, we detail how we construct the confidence set. The proof that 0, lies in the confi- dence set with high probability will be presented only in Appendix E.4 so that we can continue in Appendix E.2 with the proof of the main result. Theorem 29, bounding the regret. This result differs from Theorem by providing additional detail about the choice of the parameters in the algorithm. The proof presented in Appendix E.2 requires number of technical lemmas that are presented the proof develops. The proofs these are postponed to subsequent sections. Before proof of these, devote the next section (Appendix E.3) to technical results on consequences of self-concordancc which will be useful for the rest the proofs. This is followed in Appendix E.4 by the proof that the confidence set constructed indeed has the required coverage. The next section (Appendix E.5) is devoted to proving Lemma 30 ("ellipsoidal diameter bound on the confidence set"), which is one of the two key results required for the proof of the main regret bound (besides the result the coverage of the confidence set). A self- bofddionn property seff-concordance functions (Lemma 31), which is the second main ingredient of the regret bound proof is shown in Appendix E. Finally, for completeness, we present the (well known) elliptical potential lemma (stated here as Lemma 38) in Appendix E.7.
E.1 Constructing the confidence set
The confidence set construction is based first obtaining the parameter vector 0.. This parameter vector is chosen be the minimizer of the regularized negative log-likelihood function: 0, arg minggrs C(0; Dz) where D, =(X,, Y. [=1 is the data available in step and
C(0,Dr, = 11012 Σ log q XY:
(32)
where À >>> is tuning parameter (to be chosen later) and g(y; u)
dQ (y) is the density of Qu zQ
with respect Q at y E IR. It should be clear from the definitions that g is well-defined. The purpose of regularization is to ensure that the loss function has a unique optimizer even in the data poor regime.
For the construction the confidence set will be useful to derive an equivalent expression for the loss L. For this, first note that the density g satisfies q(y; u) exp(yu 1h (u)). Plugging this into the definition of L, we get
( -
A +
1=1
As it is well known, vi is convex function of its argument (Theorem 1.13 of [Bro86]) and hence 0 C(0; D) is strictly convex provided that 0.
For the confidence set construction we will need the non-constant part of the gradient of C(: Dz). which we denote by gt- We will also need the curvature of L(;;D,), which we denote by H, These are
(e) Σ m(X 0O that VoL(O,D,) -g.())))))))))))))))))))))
Σ X,Y,
and
H,(0) V2C(0,D,) XI xXXxX
The minimizer& 0, = arg maX C(O; A) has the property that
AC(0; (C,))
0.
09
30

---

This implies that
ge(0.) Σ
X,Y; =.
With this, we can introduce our confidence set construction, which is based on the work of [Jan+24].
For E (0, 1), let
(0,) 0 A
|o.100 se(O:) (0)
S sx((0)]
(33)
where for M to be chosen later (in Lemma 28),
2dM
TL
Ar 1V
log
ee/1 ee1++
v1
(34)
So
1
4Md
LT. v1/8
71(6) AT
+ +00
+
log
ev
for all t [7].
(35)
2M
vdr
Here, S. = sup 0 }.. as defined in the main body of the paper. In the algorithm we then choose C, to be C, (0:) with fixed value of 8 E [0, 1] that bounds the failure probability of the algorithm. The following lemma, whose proof is postponed to Appendix E.4, as mentioned beforehand, shows that the confidence sets 0z21Cy (0.) have coverage 6:
Lemma 28. Assumptions and 2 hold and choose M 2 max( log(2), 1/(1 1/(, + S2)) in Eqs. (34) and (35), where I' is any stretch function for (Qu) (S,2.5. and K suPs [(u). Then, for the confidence set defined in Eq. (33) and for all 8 (0,
IP(V 1,0, (O))) - 6.
Note that Theorem 7 and Assumption guarantees the existence of stretch function I' mentioned in the theorem.
In the remainder of this section, we will fix I' to one such stretch function.
In general, here, one wants to use the smallest such stretch function (i.e., r == =Q)) When IoQ is not available, in the lack of a better choice for the choice worked out Theorem can be used.
E.2 Proof of regret upper bound
Let Eg be the event that Eg {0. E C₂ which by Lemma 28 holds with probability at least
1 8. For the next theorem, recall that Sy = supace ||@]] and S = =upll, S2 inf
Theorem 29. Let E (0, and a positive integer and consider a well-posed GLB model g = (X, S, and assume that Assumptions 1 and 2 hold. Then, by setting C, C³ (0)).. for any
0, O with probability least 5, the regret Regret of Algorithm when it interacts with
the GLB instance specified by 8, can be upper bounded by.
LT dd
Regret (T) < {8crr(8) di( ( L/A) 1+
T
+ 2 ( KN log(A +T/d)
LT dA
+ 32c² (6) Kd(1 + I./)) log 1
where c == (1 + (K -22) and
K sup T(u).
(36)
31

---

Proof. We first consider the case that the base distribution has variance, which implies that Q is Dirac. As discussed beforehand, and as it is easy to see it, this case Ug = R. Qu Q for any E R. Hence, all arms have the same payoff and all algorithm incur zero regret. In the rest of this proof, we assume that Var(Q) > O. Since uu(-) (-)(.) is infinitely differentiable (Proposition 2), we can perform a second-order Taylor expansion on the regret
T
Regret (T) =
Σ
10 0x) - (xxx 0+)
Σ i (.) -x.)
0. ((E - Xx)) xx))
RT(T)
R2(T)
where & is between X, 0, and x, for t E [T]. On event Es. by definition of Xx, 0g (in Algorithm 1), it holds that u, X 0t. Observe that (8) (Eq. (35)) increasing in t, we have that (8) I (5) for all t [T]. Then we can bound R1 (T) as follows
(i(T)= Σ ((XT0.)6 -
Σ iux, ((),0.) (0. 00))
$
M Σ pxx x1), (0.)) - -..lH.(0.)
where the last inequality is due to Cauchy-Schward Schwarz. Since 0g and 6, are the confidence set on Eg. are able bound ||o, 0, (r. by the following lemma that exploits the properties of confidence set as well as self-concordant functions. This lemma a variation of proposition of Abeille, Faury, and Calauzènes [AFC21] where they show the result for logistic function that is 1-self-concordant.
Lemma 30 (C: (0:) has small ellipsoidal diameters). Under Assumptions and for all 01. 0g C (0)), follows that
100 02llH.(0.) 101 02llH,(02) S 2(1 2K (S1 (8).
where K is defined in Eq. (36).
By Lemma 30, we can upper bound R₁ (T) to
R1 (T) < (xx, 0.) (x) 2(1+2KK - (2))
Denote A, = / MX, 0,)X, and we have that H,().) = Σt= A.A, + AZ as well as ||Ae]| < VL L where the second inequality is because WLOG assume L > 1 in Assumption 2, We can
32

---

bound R1 (T) in the terms of A..
T
(1(T) S + ((1+2K((5) - (2)))r(0)
(xx 0.)11 2.0
to. V (.(XTO.)
$ 2 2K((1 (2))r((1)
(X (X 0.)1lxII :(0.)
Σ (XTT0. 0.)
(Cauchy-Schwar)
2(1 2K( S2))m((0)
|| A | AAll11-000
Σ Ox)00)
\
LT dd
< 4(1 + 2K(S Sa))m(l)) a(1 + L/A) log
1
Σ ixX 0-)
0+)
where in the last step we elliptical potential lemma of Abbasi-Yadkone Pál, and Szepesvári [APS1I], which, for easy of reference, we give in Lemma 38. We now start to bound (T))). For convenience, we throw away the factor of 1/2.
(T (())((.. xx) 0.)²
(X)) (0. - -0)))
(X 2x 0, 0, 0.)
Σ ((s)) [|x 110 - 0.1121((0.)
< 2K - -52) Σ ((E) (x,.122
where in the last inequality we use Lemma 30. By definition of self-concordant function, we have
that ii{;)) < (EE)) Since & is between x. 0, and X, 0.. Note that I' defined in Theorem 7 is
increasing on [0, c1) and decreasing on (-c2, 0), which gives us I(E.) S r(X, 0.) vTxx. 0.) < K.
Let V, XI + Σ ==1 X,X,T We hence have
R2(T) 4(1 + (S -2)) Σ
$ 44(1 2K(S (2)) KL
Xx, (X1112,1(0)
(i(-) S (Assumption 2))
54(1 2K(S -
Σ 1xll
(0.) 3 xV,
< 4((1+ + 2K(S ()) Llo((A + +d/d). Putting the bound (T) and (T) together, have that (egret(T) = R₁ (T) + (T)
(Lemma 38)
LT 1+
4(1 + 2K(S, (1)))((0) d(1 d(1+ log
(((TTO.)
dx
+ 4(1 + 2K(S -
K log( + T/d).
(37)
We mimic the trick used in Janz, Liu, Ayoub, and Szepesvári [Jan+24] bound v ET= ((7
0.)
which was originally proposed by Abeille, Faury, and Calauzènes [AFC21]. We present the following lemma that is abstracted out from Claim 14 of Janz, Liu, Ayoub, and Szepesvári [Jan+24].
33

---

Lemma 31 (Self-bounding property of self-concordance functions). Let V = [a. bJ, closed, nonempty interval over the reals, f a real valued function defined over an interval of the reals that twice continuously differentiable over V such that for some r - If(v) - (() holds for all V. Assume that - sup ((v) co. Furthermore, assume that either identically zero over V, or f is positive valued over V. For positive integer, let {ar)i=1 C V. Then,
a Σ flad s snf(b) + Σ f(6) f((a).
n
[S2, Sil and I restricted to [a, bl. Then, all the conditions of the lemma are satisfied by our choice of r. Furthermore, A suPoe[S..TTo. l(v) K < t00. Hence, all the conditions of the lemma are verified. Hence,
We apply this lemma with f μ4, la, b] 1S
Σ OxX Ti(xIO.) + KRegret(T)
$ VTi(aTO.) + v (Regret(TT)
(38)
Plug Eq. (38) into Eq. (37),
LT [+ dx
Regret(T) < 4(1 + 2K (2))Tr(0)) L/A) log
T
+ +4(1 + 2K(S -
+
LT 4(1 + 2K(S) Se))r(()) Kd(l + (1+
/ /Regret(T).
dd
Let
LT dA
A 4(1 + 2K(SS - (2))r((0) Kd(1 L 1+
1+ LT
B = 4(1 + ( - S2)) (0)) (1
T
dA
+ 4(1 2K(Si Sz)) 1,2 //dd),
we can write out the inequality
Regret(T) (T) - A/RRegrt + B.
Solving it have that
Regret (T) 2A² 2B.
Plugging in the definition of A and back.
RTg < 8(1 + (K; (2))TT(8) (000--/((SSS////OOO//C//CE------
[1
LT
T
ds
8(1 + 2K(S1 (r)) L2 + T/d)
LT dA
32(1 + 2K(S (2)) Kd L/A) log 1+
E.3 Seff-concordance control
this section we provide technical results about self-concordant functions which play important roles
in confidence set construction and controlling the regret of Algorithm 1. Sppecifically, Corollary 33 and Lemma are used to show Lemma 30, one of the key lemmas we use the proof of Theorem 29. Lemma 5 is used to justify the confidence set contains 0, with high probability (Lemma 28).
34

---

The next lemma shows that for self-concordant NEFs, ji is a smooth function of its argument. The lemma is essentially the same as Lemma 3 from Janz, Liu, Ayoub, and Szepesvári [Jan+24] (itself based on a result of Sun and Tran-Dinh [ST19]) and is updated only to match our definitions of self-concordance, which is refinement of that used by Janz, Liu, Ayoub, and Szepesvári [Jan+24]. The proof (based on the proof of similar result of Sun and Tran-Dinh [ST19]) is included for the convenience the reader.
Lemma 32 <Self-concordance to smoothness). Let be an interval over the reals, μs a real valued function defined over an interval of the reals that is twice continuously differentiable over such that for some I + Rt, [īb(u)] S [())j(u)) holds for all u E U. Assume that K = supneu ['(u) < Assume that either ji is identically zero over U, is is positive valued over U. Then, for any u, u' EU,
ju(x') S ((uu)kluuul)
An immediate corollary of this lemma is that self-concordance of a NEF implies that the variance function, ft, of the NEF smooth:
Corollary 33 -Selocconeeee to smoothness). Let Q = (Qu) be self-concordant with stretch
function F P: l + Rt, where U is an interval and assume K = supneu [uu) < oc. Then for any u, u' U.
(M'') S ((u)e
Note that the inequality is well-posed since u, u' E Ug. and is known to be differentiable over Ug and, by the definition of self-concordance, U c Ug.
Proof. This result follows from Lemma 32 once we notice that the variance function of NEF is such that if ju)) = 0 for any u E 24, then ju is identically zero over U. Indeed, ju() 0, then Qu is a Dirac distribution and so is Qu for any u E U.
Proof of Lemma 32. When ji is identically zero over U. the statement is trivial. Hence, consider now the case when ja is positive valued over U:
A(u) > 0
for all
v EEu.
(39)
pal) < K K|w u'). To show this, define (01) = ju(u + t(u' w)) so that 6(0) = ju()) and (01) p(u'). Since Ug is an interval with non-empty interior, ((t) is well-defined for all E [0, 1]. Furthermore, by Eq. (39) and since 2 is an interval, we have that <(t) for all [O, 1]. Consider now the map
Then, it suffices to show that In A(u')
In o(t) where E [0, 1]. The derivative of this map exist and continuous over (0, 1). and in particular, & In (())
d(t)
by the chain rule. Indeed, the derivative of & exists and is continuous over (0, 1). because the same holds for ja by the properties of NEFs, and as we just diseussed, & is positive over [o, 1] and is continuous. Now, by the fundamental theorem of calculus applied to to
dee
d In (tt) and by the monotonicity of integrals, de
(u(') In In (uu)
o(1)
/.'
d d'in((t) dt
/ dl o(t)
dt.
(40)
(0)
dt
dt
It remains to bound the integrand in the rightmost expression. For this, discussed earlier we have
d In ((t)
o'(()
o'(() (tt)
(41)
dt
o(t)
To bound the ratio on the right, we again use the chain rule and calculate
J (t) (ā(u + t(u' u))llu' - ul S K ju(u
t(u' u)) lu' u/,
where the inequality follows by the definition of K by definition of self-concordant function, we have that for all u E U4 [ā(x]] & K j.)). Now, the result follows since we have shown that the integrand
upper bounded by K [u u'| and thus f.
a d(t) di S K|u -
w'/.
d8
35

---

We continue with two results, both of which use the lemma just proved. The first result gives a lower bound for the integral remainder term when Taylor's theorem is used to approximate μ.. The second result gives a quadratic upper bound on the CGF of Qu. and will be the basis for constructing our confidence set.
Lemma 34. Let = (Qu) be self-concordant with stretch function I :u + R4 where U is an interval, and assume K = supuez [(u) < oc. Then for any u, u' E u,
js(u) Lo juu + t(ul - uu)dtt 2 + Klu - ue|
Proof. By Corollary 33, it follows that
iuuu + t(v' - u)) 2 ju(u) exp( w/).
Integrating both sides between and gives us
S iuu + -u))
) ii(u) / exp(- Ki/p' u/)dv
exp( Sxpp-KK' Ktt u/' ul)
id(u)
K| ul
exp( - K|u' 21)
= id(u)
K //'u 2
((u))
1+ K|u
where the last inequality follows from the elementary inequality (1-e-))/z 2 1/(1+z) that holds for all x 2 O.
We are now ready to prove Lemma 5. As noted beforehand, we adopt this lemma from the work of Janz, Liu, Ayoub, and Szepesvári [Jan+24]. In particular, is an adaptation of their Lemma which was proved for distributions where Ug = R. Here, we deal with the case when Ug is possibly strict subset of IR.
Lemma 5 (From self-concordance light tails). Let Q (Qu)ueu be a NEF which is self- concordant with stretch functtion 1 + R where U is subinterval Uf (a, b). Then, for any U.
the (s) S su(u)= + 3² si for all s ( inf b- ssupl), (2)
where K suPneu I(u).
Proof. Let u E Ld Hence, by our assumption on 24, E Uq. Now let s E R. Then,
uhe. (s) = log / (xp(sy)Qu((e = log
Ma(u) / (exp(sy) (xppss))xx((w))((ds))
= uhQ + 8) - viQ(w)
Hence, vi (s) is finite valued whenever u u s E Uq. Assume that this holds and in fact u 5 E Ug. Since u, 8 E UG. the is twice continuously differentiable over an open interval containing u and Then, by Taylor's theorem there exists & in the closed interval between and such that
s² 2 (E(E)
uQ(u + s) ( sup(u) +
Since dंq = μ and de ش (cf. Proposition 2) we get
82
vo(u+ s) -v)(uu) = sp(u)= +
2 (M())
36

---

Now, by Corollary 33, we have that
(b(E) S iu()) clu-- S id(u)e S <2j(u),
where the final inequality follows when |s| S log(2)/ K. Putting things together, it follows that |s| I log(2)/K K and Ug= {u} then
vQ. v (u + 8) - -vQ(u) S su(u) + +
For S C R. R. let S + = {s r : S}. Since is arbitrary point in U, the above conditions on s will be satisfied if |s| S loo(2)) K and 8 E Z Nuculs u. Now, from Ug = (a, we have Z = =neur(a - u, - u) = (supreu a - u, inf - u) = (a inf b supl),.
finishing the proof.
From the calculation at the end of the proof it follows that the statement of the lemma is non-vacuous if for Ug (a, b). a inf U 0 < b- supll which is equivalent to that inf and supll b. which is always satisfied when U is strict subset of Ug.
E.4 Confidence set construction
We now turn proving Lemma 28 which is concerned with showing that the confidence sets C² contain the true parameter 0, with probability 1 - ö. The proof is essentially the same as that of Lemma 4 of [Jan+24]. We will need the following result, which is taken verbatim from the paper of Janz, Liu, Ayoub, and Szepesvári [Jan+24].
Proposition 35 (Theorem of [Jan+24J), Fix X, > O. Let (Xt)seN+ be Bg-valued random sequence, (Y))ee+ real valued random sequence and (ut) be a nonnegative valued random sequence. Let F = (Fe)LeN be a filtration such that (i) (ettett is E E-prediccablle and (ii) (Y))ent are F-adapted. Let
[- and assume that the following condition holds:
Elexp((ex) Ft-1] & exp(svv-1) for all |s| S1S11 1/M and I E N
Then, for H. = E' 4/-1 1x Al and S,
and 5 > 0.
VA
2M
det (H.( d/2
2M d'lo((2)
P 31 EEEN |Seeli 2
+
log
+
< 5.
2M
VX
5
We now turn to proving Lemma 28. For the convenience of the reader, we start by recalling the
definition of the confidence sets C. involved (cf. Eq. (33)). Recall that 02 S2 S x 0 s S < <1
for r E X' and 0 E O. For 8 E (0, 1], we have
(0,) e (9((0)-
S xx(0)
H. (0)
where
7e(0) = /xT
1
+ So
+
4Md
log
ey evi1+
tL v v1
for all 1 [7),
2M
Vdr
d
2dM
TL ev
A7 = 1 1V
log
v 1/6
So
d
and recall that So = supage ||||| or upper bound on this quantity, and M is specified in the next result:
Lemma 28. Let Assumptions I and 2 hold and choose M 2 max log (2), 1/(4 1/),,1/(c) + S2)) in Eqs. (34) and (35), where I is any stretch function for (Qm) [es and K sup Susus, [(u). Then, for the confidence set defined in Eq. (33) and for all 8 E (0,1).
P(Vt 2 1,0, Ci -
37

---

Proof. From definition it follows that A. E O. Now we prove that with probability at least 1 5, it holds that (0.) ge (o))) I (6) for all f 2 1. The proof goes through by using Proposition 35 and we now match the conditions of Proposition 35, By Assumption I, we have that (Xe)teNt is Big- valued random sequence. Let F o(X1, Y,.,,, filtration F = (Fi)LeN. Then by definition, (Xx)) are F-predictable and (Y)) are F-adapted. Note that (xX 0.) [| for all i E [n]. Let e; = Y, - This gives (Ee) are also F-adapted and the following identity follows by definition
1, Xx)) for t 2 Consider the
ge - (0.) = Σ s + X0
i=1
= + AB.,
where S, = Eie E;X; Let
4/- = - 0.). Now we would like to apply Lemma 5 to show that, for |s| S M, it follows that E(exp(sse)) exp (
(42)
Applying the definition of e, it follows that
E (exp((EE)) Fr-1l = Elexppsyy sp(X, F.
= exp(-sspfff (x.p0sss(xx6)))))),.. EY) a.s.,
where the last equality is because X, - Since, by definition, the distribution of Y given Fr-1 is Qx.* 9., we have that
Elexp(se,)) = exp( sop(-ssiae (X, ( 8.))1
= cxp( su (x, 0.)) e QxTa (dy)
= exp( - s/l (x 0.) + vOXTO, (8))
exp(-spul
I exp(s (XX 0.)).
where the last inequality is because [s| < M implies that |- log 2/ log 2/K] (ug (2)) n (43 S1) so Lemma is applicable (it is applied with (Qu)ue(sa.Si) and T as chosen in the statement). Then, Eq. (42) follows by noting that U:-1 (XX 0.).
Lastly as defined above, H, corresponds to (O.). Taking the no-n weighted by H, and applying triangle inequality,
(0)) (e ((()))laa;" I 1|Soll (e.)) 1110-1l,, S || (slll,," + VAS.,
where the last inequality follows by H, (0.) = X I. By Proposition 35, with probability at least 1 5, it follows that for all t 1,
I.
V A
2M
del
2M
SS H, (0.) <
+ V
log
d log()).
2M
8
VÁ
We now bound (lt Let A;
Vi( 0.)X, for all i E [t] then (2,) can be written
as
H.(O.) = + Σ A.A.T
By Assumption 2, it holds that (XX 0.) < VL. thus ||Arl2 S VL < for i [t]. Eq. (20.9)
(Note of section 20.2) in [1S22]] gives
IT.
det (et((H((0))/ [
Xd
The stated result follows by chaining all the inequalities together and noting that
1
2Md
tL
)
2M
(8) 2
vā
So
1 log
1 Ad)
+ log (1/))
for all
t e [7].
2M
V
VT
(43)
38

---

E,5
Proof of Lemma 30
The following two lemmas (Lemmas and 37) are variations of Claim and Claim 3 of Janz, Liu, Ayoub, and Szepesvári [Ja+244]. The difference is that Janz. Liu, Ayoub, and Szepesvári [Jan+24] show them for all 01, 82 IR because the MGF Mo therein is finite on R. In our setting, there could be x E X for some & O such that Ma(a 0) oc, hence we show it within the parameter e.
Lemma 36. For all 11, 02 G it follows that
(c(01) (02) = (2) 02).
In particular, we have that
(19)(0)) - ge ge(02)lla; " = 10, - -02llc.(0,,00)
Proof. The "In particular" part follows from definition of 22- no-m weighted by (T, 82). We now prove gr (01) (e2) G,(0,, (2) 02). By definition of the difference quotient a(:)). +), we have that
uuu) uln') = alu, n')(u n¹).
(44)
Writing out the expression of g:(0)) (02) gives
(c( (02) = Σ [ 01) 1xx7 B2)) + - -02)
[a(x) X1, 02)x (01 02))xx =((01 02)
(Eq. (44))
Σ al a(X 01, x, 02) X:x7 (0) 02) A(01 02)
02) - 82)
Lemma 37. Under Assumptions and for all 01, 02 E A it follows that
Ge(O1, 02) ł (1+ + 2K (S1 - (5)) (.(),)
(45)
G,(01,02) 2 (1 + 2K (S1 - (51) -,))-1H,((0.))
(46)
where is defined in Eq. (36).
Proof. Since fo 0: X, O} Si by Assumption 1, we have
(T To) 0) I E X, e) S K.
By Lemma 34, have that for all x E X,
a(x 01, T0, TT) 2 (1 + K| T (01 B2) -2)1)~(((a 01) 2 (1 2K (S1 S2))
0z). (T)).
Then the following holds
Σ
a axx 01, X, X (1+ (1+2K 2K (S1 105-5, 52) -2)) Σ ((xxx))X,
Gc 02) (1 2K (81 -2)) ((1))
where the last inequality follows by (1 + 2K (S1 Sz)) < The proof of Eq. (46) follows by substituting Oj with fg.
Lemma 30 (C& (Ô.) has small ellipsoidal diameters). Under Assumptions I and for all 0,, 02 Ci (Q.), it follows that
10, 02 (..)) |00 - 02)lH,(02) S 2(11 2K (S) (2))):(0),
where K is defined in Eq. (36).
39

---

Proof. We first prove the statement for ||0] - 02)l By Lemma 37, we have that
|10, 0211 V(1+ + (8) 52)) ||0 02 02lc..00.000 0z)
V[1 (1++22 2K (S1 - 52)) (e)))))(())) - -g((8)) (,)
(Lemma 36)
(11 2K (S1 S2)) (l9)(0))) (,(0))ll;; (e1.e) + (l))(0,) 9e(02)lla)' (0..2))
Note that 01, 02 C2 (0.) by hypothesis, then Lemma 37 and the definition of C2 (0.) gives that
( (.,))))))))))) l.. ((0,,0) S ((1 + 2K - (9))) (9.( g.( (0.))
S (1++2 281 (81- (2))
(l.) ge (x(02) (81.00) S ((1 +K (Si - 52) (0.( - 9: 9e (222))la)
S < + 2K (S1 - (2)):(0).
Chaining all the inequalities together finishes the proof. The proof for the statement for ||01 02 m (0g) follows similarly by substituting 01 with 02.
E.6 Proof of self-hounding property of self-concordance functions: Lemma 31
As mentioned beforehand, the following lemma is abstracted out from Claim 14 of Janz, Liu, Ayoub, and Szepesvári [Jan+24]:
Lemma 31 (Self-bounding property of self-concordance functions). Let V = [a, b). closed, nonempty interval over the reals, f real valued function defined an interval of the reals
that is twice continuously differentiable over V such that for some I V [f(v) S f())
holds for all V. Assume that A (PPVEII(U) co. Furthermore, assume that either is
identically zero over V, or f is positive valued over V. For n a positive integer, let {at)==1 V. Then,
Σ f(ad) S nn(() + Σ f(6) f(ae).
t=1
Proof. We have
Σ (a - b) //" j(b + v(a, - b)) de
Σ ((a)) = Σ j(b) +
1=1
1=1
(at (a--b) {/ f(b v(at b)) de
$ <nf(b)+ Σ
Σ (b a,) // jib+oola - -b)) du
<nf(b) +
(a, S b and triangle inequality)
1=1
"
/' l(b v(ar - 6)) (6 + v(a. - 6)) du
2nf(b) + Σ (b - ax)
(Lemma 32)
1=1
-n((b) Σ (b a.) ['' Aj (b v(a: - 6)) du
< <nf(b)+ K Σ ((b) f(at).
(fundamental theorem of calculus)
finishing the proof.
40

---

E.7 Auxiliary Lemma
Lemma 38 (Elliptical potential lemma). Fix X, O. Let faeti=) be a sequence in AB and let Vi + 01410 for each N. Then, for all N
Vo AI. Define V4+1
al [ 2d max {1,
Aa
nAa2
log 1 dA
Proof. See, e.g., Lemma 19.4 of Lattimore and Szepesvári [LS20].
Numerical Simulations
In this section, we report our results on numerical simulations. We run our algorithm on exponential bandits. The setting is as follows. The base distribution is an exponential distribution with parameter where the probability density function can be written as
f(x; T(x: e)Axxp(->xx)
For each arm X. the reward distribution is an exponential distribution with parameter À x 0,, where we ensure that supsex x O. < X, as illustrated by Example The number of arms | and X' _ TR22, the max variance of the reward distributions among all arms is 0.25 and supzex 1//((x 0.) 100. We run our algorithms with theory suggested parameters for 60 runs where each run has horizon 5000. To be more specific on the parameters, we list them here:
1. The failure probability 8 0.05.
2. The regularizer set to be 2.
3. The confidence width (6 A) is set according Eq. (43).
Here are the results of the experiments. Fig. I we plot the average regret along with standard
OLM logox" 9051+1
lggresrett
200
130
100
0
1900
2000
3000
40CD
5000
borizon
log(horizan)
Figure 1: Average of 60 runs
Figure The log-log plot of OFU-GLM
deviation. From the plot we can see that the regret attained seems be sublinear. In Fig. we display the log-log plot where the x-axis is log (horizon) and the y-axis is log(regret). The slope gradually approaches to 0.5, i.e., the growth rate of regret approaches to VT which confirms our theoretical bound.
41

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and/or introduction clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. The claims made should match theoretical and experimental results, and reflect how much the results be expected generalize to other settings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We do not have lower bound.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are 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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
42

---

Answer: [Yes]
Justification:
We provide detailed assumptions and very detailed proofs in the appendix.
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 or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix 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 of whether the code and data are provided or not)?
Answer: [NA]
Justification:
We do not have experiments.
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 be necessary to either make it 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 to 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.
specific model and empirical evaluation, may
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 new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
43

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
We do have experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. wwtpcc/cppwlcgggiicccoeeooo
/CodeSubmia ssionolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
We do have experiments.
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 provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
We do not have experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
44

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors 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 enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
We do not have experiments.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https http::::///uurr/ http///eerrippeeeeee cttppbbccc/..hhcccccueeeeeeeeela
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
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: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
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.
45

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
46

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
47


Reviews:
[{"review_id": "uR25pCUoNy", "reviewer": "Reviewer_Ca74", "summary": "The paper investigates the self-concordance properties of single-parameter natural exponential families (NEFs) with subexponential tails. It provides two main contributions: first, it demonstrates that NEFs with subexponential tails are self-concordant with polynomial-sized parameters, and second, it applies these findings to generalized linear bandits (GLBs). The authors derive novel second-order regret bounds for GLBs that are free of exponential dependence on the problem parameters. This result extends the applicability of optimistic algorithms for GLBs to reward distributions such as Poisson, exponential, and gamma.", "questions": "- Do the authors believe it possible to lift prior knowledge on parameters such as $S_0$, $L$, $c_1$, and $c_2$ in designing efficient algorithms for GLBs with NEF rewards?", "limitations": "The authors addressed potential limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The results on the self-concordance property of NEFs are definitely interesting and general, going beyond its application to GLBs. They can be interesting to many other problem settings (as mentioned by the authors themselves).\n- Not only do the authors provide an algorithm for GLBs, but it guarantees a second-order regret bound. This is particularly desirable to achieve better data adaptivity.\n- The results are presented in a clear manner, with clear definitions and helpful examples.", "weaknesses": "- It appears that the algorithmic results in this work tightly rely on the knowledge of some parameters of the NEF. Parameter-free results are quite important and have become relevant, especially in the past few years.\n- The paper could benefit from a slightly more detailed comparative analysis with existing methods, highlighting the advantages and potential trade-offs of the proposed approach in various scenarios, and how these prior results would fit in the setting considered in this work.\n- The papers could benefit from experimental results, although it is very clear that this is a theoretical paper.\n\nMinor details:\n- Many references have \"et al.\" instead of the full list of authors. This should be fixed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing our manuscript and we are delighted at your appraisal of our work. A question was asked “Do the authors believe it possible to lift prior knowledge on parameters such as $S_0$, $L$, $c_1$ and $c_2$ in designing efficient algorithms for GLBs with NEF rewards?”\n\nTo the best of the authors’ knowledge, existing parameter free algorithms on multi-armed bandits (linear bandits) still require the knowledge of subexponential (subgaussian) parameters or the upper bound of the reward [1], [2], [3]. Hence the knowledge of subexponential parameters (i.e., $c_1$, $c_2$) may be still needed. The knowledge of $S_0$ can be lifted as the information we need about $S_0$ can be provided by $S_1$ and $S_2$. Judging from the present work on parameter-free bandit algorithms [3], the knowledge of $S_1$ and $S_2$ cannot be lifted as [3] designs their confidence set using the upper bound of the true underlying model parameter $\\theta_\\star$ which plays a similar role to $S_1$ and $S_2$ in our work. The knowledge of $L$ can be lifted as it is worst-case polynomial in $\\max(1/(c_1-S_1), 1/(c_2-S_2))$. This bound is oftentimes pessimistic hence we leave the dependency on $L$ in the bound and knowing a tighter bound on the variance definitely helps in the performance. Hence, removing dependencies on knowledge of subexponential/subgaussian parameter and knowledge of the bound of the parameter norm, $S$, are promising directions for future research and remain open in the bandit literature. \n\nWe now address concerns in the weakness section.\n+ For more detailed comparative analysis, we can compare our bandit algorithm with subgaussian base distribution and we will be happy to add it to the camera ready version of the manuscript (assuming the paper gets accepted). Specifically, we will point out the setting in this work is the most general in the sense that we consider GLBs with subexponential rewards while all the previous work we know of consider bounded rewards or subgaussian rewards. For subgaussian rewards, we will emphasize that [4,5,6,7] still depend on $\\kappa$. Russac et al [7], also employs self-concordance in GLBs but they assume bounded reward and focuses on addressing non-stationarity of the environment – their bounds also scale with $\\kappa$ in the leading term, which can be exponentially large for logistic bandits. Janz et al [8], consider a similar setting to ours. They assume the moment generating function of the base distribution $Q$ is defined over the entire real line. This implies that $Q$ does not have a tail as heavy as an exponential distribution hence less general than our setting.\n+ For experiments, we provided some results in the global rebuttal.\n+ For the minor details, thank you for drawing our attention to the formatting of our references! This will be addressed in future versions of our submission. \n\n\n[1]. Shinji Ito (2021). “Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds”. In COLT 2021\\\n[2]. Yifang Chen, Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei. “A new algorithm for non-stationary contextual bandits: efficient, optimal and parameter-free.” In COLT 2019\\\n[3]. Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi. “A parameter-free algorithm for misspecified linear contextual bandits.” In AISTATS 2021\\\n[4]. Sarah Filippi, Olivier Cappe, Aurélien Garivier, Csaba Szepesvári. Parametric bandits: The generalized linear case. In NeurIPS 2010.\\\n[5]. Kwang-Sung Jun, Lalit Jain, Blake Mason, Houssam Nassif. Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits. In ICML 2021.\\\n[6]. Aadirupa Saha, Aldo Pacchiano, Jonathan Lee. Dueling RL: Reinforcement Learning with Trajectory Preferences. In AISTATS 2023\\\n[7]. Yoan Russac, Louis Faury, Olivier Cappé, Aurélien Garivier. Self-Concordant Analysis of Generalized Linear Bandits with Forgetting. In AISTATS 2021.\\\n[8]. David Janz, Shuai Liu, Alex Ayoub and Csaba Szepesvari. “Exploration via linearly perturbed loss minimisation.” In AISTATS 2024.\\", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cWQjbR2lfI", "reviewer": "Reviewer_n2uQ", "summary": "The authors prove that any single-parameter natural exponential family (NEF) with subexponential (subgaussian) base distribution is self-concordant with a stretch factor that grows inverse quadratically (linearly).", "questions": "- Can the regret analyses be extended to changing arm-set case, i.e., the arm-set $\\mathcal{X}_t$ varies across $t \\in [T]$?\n-", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Clearly and well-written\n- An important theoretical contribution in establishing that self-concordance for exponential tilting comes for free, which has numerous applications in statistics and bandits (as alluded to in the Conclusion). Surprisingly, the proof consists of some concentration results combined with clever integral/infinite sum manipulations.\n- For the subgaussian, the authors established that the linear growth is tight by establishing a lower bound, which is technically quite interesting.\n- First $d\\sqrt{T/\\kappa_\\star}$ type regret that holds for a wide range of generalized linear bandits, well beyond logistic bandits", "weaknesses": "- The confidence set for the OFU-GLB is nonconvex, and thus, the current algorithm is computationally intractable. There has been some progress on achieving convex confidence sets that are also statistically (regret-wise) tight -- see, e.g., [1,2]. It would be nice to write the confidence set in a convex form, as it is repeatedly alluded to during the authors' proof.\n- With the convex confidence set, it would be nice to see some numerical experiments, especially the exponential bandits.\n- The norm parameters $S_0, S_1, S_2$ were introduced but never kept track of. The dependencies on these norm parameters have been a subject of study on their own [2,3] and are known to perform well [2]. It would be nice to have those dependencies appearing in the main text as well.\n- Most of the discussions regarding the proof of regret analyses are relegated to the Appendix. From my perspective (heavily biased towards bandits community), the techniques used there are arguably a bit more interesting. I would really like to see the technical contributions made in the main text's Section 4, especially the self-concordance control lemmas used (Appendix E.3) and Lemma 31 and more.\n\n\n**Comments**\n- It would be nice to include some discussions regarding [3], which provides the first $d\\sqrt{T/\\kappa_\\star}$-type regret for *bounded* generalized linear bandits but still goes beyond logistic bandits.\n- For each theorem statement, if not already done so, I would like to see a direct (hyper)ref to the Appendix containing its proof\n- Typo: \"Lemma ??\" in pg. 24\n\n[1] https://proceedings.mlr.press/v130/abeille21a.html\n\n[2] https://proceedings.mlr.press/v238/lee24d.html\n\n[3] https://arxiv.org/abs/2404.06831", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and suggestions and we really appreciate them! \nFor the weakness section:\n+ We agree that the convex relaxation technique from Abeille et al [1], can be applied to our case. We adapted the proof from Abeille et al [1] and are able to apply the convex relaxation to our confidence sets as well. This was a good suggestion and thus will be added to the future version of our manuscript. \n+ We conducted some numerical experiments on exponential bandit (as suggested by the reviewer) to verify our theoretical contributions. The results are available in the global rebuttal.\n+ We will make the dependency on $S_0$, $S_1$ and $S_2$ explicit in the regret bound. Thank you for drawing our attention to this issue. \n+ The techniques in section 4 follow similarly to Abeille et al [1]. Lemma 32 is borrowed from proposition 8 of Sun and Tran Dinh [2], where we tailored the technique into our specific setting. Similar use of self-concordance is also present in [1,3].\n\nFor the comment section:\n+ We will be happy to discuss [4] in the final version. Their arm elimination technique and adaptation of rare switching are relevant. It is also nice to see that their empirical performance can surpass the performance of ECOLog, which, according to our experience, is quite competitive.\n+ We will be happy to add hyperlinks to the appendix about the proofs of each statement.\n+ Thanks for pointing out the typo. It was meant to be the lower bound on $\\dot\\mu()$, i.e., lemma 17.\n\nFor the question section: Yes, our regret guarantee still holds for changing arm-sets as long as  $S_2\\le x^T\\theta\\le S_1$ holds for all $x\\in \\mathcal X_t$ , $\\theta\\in \\Theta$ and $t\\in [T]$. Our proof technique makes no use of the stationarity of the arm set and its inclusion was solely to facilitate a more streamlined exposition. \n\n[1]. Marc Abeille, Louis Faury, Clement Calauzenes. “Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits.” In International Conference on Artificial Intelligence and Statistics (2021).\n\n[2]. Tianxiao Sun and Quoc Tran-Dinh. “Generalized self-concordant functions: a recipe for Newton-type methods.” In Mathematical Programming 178 (2017): 145 - 213.\n\n[3]. David Janz, Shuai Liu, Alex Ayoub and Csaba Szepesvari. “Exploration via linearly perturbed loss minimisation.” In International Conference on Artificial Intelligence and Statistics (2024).\n\n[4]. ​​Ayush Sawarni, Nirjhar Das, Siddharth Barman, Gaurav Sinha. \"Generalized Linear Bandits with Limited Adaptivity.\" ICML 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorists.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GhiZLA82Vx", "reviewer": "Reviewer_ySJz", "summary": "This paper discusses Generalized Linear Bandits (GLB) under the self-concordance assumption. The study successfully relaxes the limitations of existing work with an OFU-type algorithm, providing mathematically solid theories for GLB within the self-concordance family. However, the presentation could be significantly improved, and the paper's style does not align well with the venue.", "questions": "This paper talks about \"being free of exponential dependency\". I would like to see what the term means in detail. Also, why \"being free of exponential dependency\" is important in analyses and applications?", "limitations": "This paper discusses the single-parameter natural exponential family. But, I believe that this family is not comprehensive enough to include most applications in the real world.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "This paper has a sound theoretical foundation with the relaxation of some assumptions in the existing literature.", "weaknesses": "The first section should provide a comprehensive overview of the study. The core concept of \"self-concordance\" is introduced abruptly and is not well-explained. The literature review is incomplete. Specifically, the differences between this study and the existing literature, such as [Rus+21], are not thoroughly discussed. As a result, the contribution of this study is unclear. The paper dedicates the first seven pages to the theoretical foundation and introduces the model and algorithm thereafter. Due to space constraints, these are not fully illustrated, and the paper lacks experimental results. This organization is not well-suited to this venue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to clarify a misunderstanding of our work that we do not “discuss GLB under the self-concordance assumption”. What is true that our work goes beyond this: we aim to remove this assumption for GLBs with subexponential base distribution. \n\nNow we would like to address concerns pointed out in the weakness section. \n+ Due to the space limitation, we are unable to provide a thorough explanation for self-concordant functions but we would like to kindly remind the reviewer that references of its origin are provided in line 127 and we introduce its use in machine learning & optimization from line 28 to 46. In the future versions of our manuscript, we plan on using the extra page to flesh out the exposition around self-concordance as well strengthening the section on related works. \n+ There is a huge body of related work, so we are incapable of summarizing them all thoroughly due to the lack of space (which we think is a common practice, in the exploding field we are in). All the related works that we know of are at least mentioned. On the issue of why [Rus+21] is not discussed in detailed. The main contribution in this paper is working out how to act in a non-stationary setting. Since we only consider the stationary setting, their contribution is irrelevant from the perspective of our paper (they avoid any difficulty that we face by assuming bounded rewards). Finally, the regret bound in [Rus+21] scales with $\\kappa$ (which can be exponentially large in the dimension $d$, [8]) and is not second order (meaning the bounds does not scale with the optimal arm’s variance); the stronger earlier relevant papers are all discussed in our paper; we'd be happy to add more relevant works if needed and did the reviewer have any other suggestions.\n+ We would like to note that our writing style naturally flows from theory to algorithms, as appreciated by reviewers Ca74 and n2uQ. The contribution of this work is to show that GLBs with subexponential base distribution possess self-concordance property. It is a result that could be interesting on its own and the application of it could go beyond GLBs as detailed in section 5. We select GLBs as a demonstration of how the self-concordance property of subexponential NEFs can be applied to address open problems in the bandit literature. Our results naturally extend the analysis techniques presented in [9]. This motivates the organization of our paper.\n\nySjz asks the question about being free of exponential dependency. This originally comes from the very first work on GLBs [1] where the confidence width (and as a result, the regret bound) suffers from a dependency on $\\kappa$ that is in worst case exponential in the norm of true underlying parameter $\\theta_\\star$, creating a significant gap between theoretical and empirical results. To explain why resolving exponential dependency is important, we would like to remind ySjz that algorithms with exponential dependency in relevant parameters are considered as inefficient and unpractical as the resource demands increase very rapidly with input size. Transferring this notion into decision making, or specifically bandit algorithms, algorithms with regret scaling exponentially with relevant parameters are considered to make inefficient use of samples. As is pointed out in [8], which studies an instance of GLB -  logistic bandit: *“$\\kappa$ can be prohibitively large, which drastically worsens the regret guarantees as well as the practical performances of the algorithms.”* (paragraph **Limitations**) and *“Even for reasonable values of $S$, this has a disastrous impact on the regret bounds”* (section 2). Removing this exponential dependency enables us to align the theoretical bound of UCB-type algorithms on GLBs with its empirical performance. To the best of the authors’ knowledge, there is no previous work resolving this exponential dependency for the whole class of GLBs with subexponential base distribution.\n\nWe would like to address the concern about the applicability of the work. We are confused by the reviewer’s claim that natural exponential families are “not comprehensive enough to include most applications in the real world”. We interpret this sentence as asking whether NEFs enjoy revenue generating applications in the real work, which they do. To give a concrete example, consider Poisson regression, which is widely used when dealing with count data, e.g. number of insurance claims or Uber's surge pricing model.\n \nAs for the theoretical nature of the work, we would like to point out that many important Neurips publications are theoretical in nature. Here is a non-exhaustive list of Neurips publications dedicated fully to theory without experimental results\n[2, 3, 4] and all of them are cited over 300 times. Here are works accepted last year that dedicate themselves fully to theory without experimental results [5,6,7].\nWe also conducted some numerical experiments. The results are available in the global rebuttal.\n\n[1]. Filippi et al. Parametric bandits: The generalized linear case. In NeurIPS 2010\\\n[2]. Jin et al. Is q-learning provably efficient? In NeurIPS 2018\\\n[3]. Kakade et al. On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization. In NeurIPS 2008\\\n[4]. Antos et al. Fitted q-iteration in continuous action-space MDPs. In NeurIPS 2007\\\n[5]. Liu et al. Optimistic natural policy gradient: a simple efficient policy optimization framework for online rl. In NeurIPS 2023\\\n[6]. Yuan et al. Optimal extragradient-based algorithms for stochastic variational inequalities with separable structure. In NeurIPS, 2023\\\n[7]. Foster et al. Model-free reinforcement learning with the decision-estimation coefficient. In NeurIPS 2023\\\n[8]. Faury et al. Improved Optimistic Algorithms for Logistic Bandits. In ICML 2020\\\n[9]. Abeille et al. “Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits.” In AISTATS 2021\\", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank you all for the time and effort spent in reviewing our manuscript! We are glad that the reviewers appreciate our theoretical contributions on NEFs (reviewer Ca74 & reviewer n2uQ), our contributions to the bandit literature on second-order regret guarantee for GLBs with subexponential rewards (reviewer Ca74 & reviewer n2uQ) and our writing style (reviewer Ca74 & reviewer n2uQ). A general concern was raised about the lack of experiments and we understand the concern and conducted some experiments -- as a sanity check of our theoretical results. The setting of the experiment is as follows. We will be happy to use the extra space in the paper for including a little more thorough experimental verification of our theoretical results.
+ We conduct experiment on exponential bandits, i.e., the base distribution is an exponential distribution and as a result the reward distributions are also exponential.
+ The dimension $d$ of the true underlying parameter $\theta_\star$ is $d=2$
+ The number of arms $|\mathcal X|=20$. 
+ The maximum variance is $0.25$, i.e., for all $t\ge 1$, $\max_{x\in \mathcal X}\mathrm{Var}[Y_t|X_t=x]=0.25$ . 
+ The experiment consists of 60 runs with a horizon of 5000. 
+ The failure probability $\delta$ is set to be 0.05.
+ The regularizer is set to be $\lambda=2$ and $\gamma_t(\delta)$ to be the theory suggested value below line 922:
$$\gamma_t(\delta) = \sqrt{\lambda}\left(\frac{1}{2M}+S_0\right)+\frac{2Md}{\sqrt{\lambda}}\left(1+\frac{1}{2}\log\left(1+\frac{tL}{\lambda d}\right)\right)+\frac{2M}{\sqrt\lambda}\log(1/\delta)$$
The results are available in the pdf attached. Here are some explanations:
+ The first figure displays the mean regret along with standard deviation. The regret attained appears to be "sublinear". 
+ The second figure is a log-log plot to display the growth rate of the regret. The slope gradually approaches 0.5, i.e., the growth rate of regret approaches to $\sqrt T$, which confirms our theoretical bound.

Meta-review: This paper provides a general study of self-concordance in NEF, with applications to regret bounds for generalized linear bandits. Compared to previous works, which primarily focus on the logistic bandit, the paper generalizes the family of distributions for which self-concordance holds.

Overall the paper was well written. I agree with the reviewers that additional discussion and experiments comparing with the existing literature would be enlightening in the camera ready. In addition, highlighting some of the proof techniques in the main text. The authors may also want to discuss a concurrent work (https://arxiv.org/pdf/2407.13977) and highlight some of the differences.
Decision: Accept (poster)