Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits

Authors: shuai  liu
alex  ayoub
flore  sentenac
xiaoqi  tan
csaba  szepesvári
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 20:28:12

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.

Main paper: 
 introduction: 
 Single-parameter natural exponential families (NEFs) [Mor82] abound in statistical applications [MN89; Bro86; WJ08; ML09] . 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 a NEF impose limits on the NEF:if the base distribution is subexponential (subgaussian), we show that the NEF is selfconcordant with a 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 a 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 to be bounded1 [Mar+19; OB21; Rus+21] and thus extends the applicability of the results therein.Self-concordance 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 a NEF's secondorder Taylor expansion. This is useful in designing and analyzing both estimation and optimization methods. Historically the self-concordance property was first found to be useful for optimization [NN89; NT08; ST19] and later for statistical estimation [Bac10; 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 a tighter second order Taylor expansion that better captures the curvature of the sigmoid function. Employing improved self-concordant analysis, [AFC21] 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-concordant. We build upon this line of research and fill a 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 GLBs considered subgaussian or bounded reward distributions while ours consider subexponential ones. For subgaussian rewards, these works [Fil+10; Jun+21; SPL23; Rus+21] still depend on κ. Note that [Rus+21] , also employs self-concordance in GLBs but they assume bounded reward and focuses on addressing non-stationarity of the environment. In addition, their bounds also scale with κ in the leading term, which can be exponentially large for logistic bandits.[Jan+24] 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. 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: In Section 2, we introduce single-parameter NEFs and review 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. 
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.For a real-valued differentiable function f defined over an open interval, we use ḟ , f and ... f to denote the first, second and third derivative of f . The set of reals is denoted by R, the set of nonnegative reals by R + . For a set U ⊆ R, we denote its interior by U • . For real numbers a, b, we use a ∧ b and a ∨ b to denote the min{a, b} and max{a, b}, respectively. With ϕ a logical expression, I{ϕ} = 1 if ϕ evaluates to true and I{ϕ} = 0, otherwise. We use f ≲ g to indicate that g dominates f up to a constant factor over their common domain. For S ⊆ R, x ∈ R, we let S ± x denote the set {s ± x : s ∈ 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, is Q.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 a probability distribution Q over R let M Q : R → R + ∪ {+∞} denote its moment generating function (MGF):M Q (u) = exp(uy)Q(dy) , u ∈ R .We will find it convenient to also use the logarithm of the moment generating function, which is known as its cumulant generating function (CGF). We denote this by ψ Q : R → R ∪ {+∞}. Thus,ψ Q (u) = log M Q (u).Let U Q = {u ∈ R : M Q (u) < ∞} denote the domain of M Q (and, thus the domain of ψ Q ). As it is well-known, ψ Q is convex and hence U Q is always an interval (which, trivially, always contains 0). For a subset of U Q , denoted by U ⊆ U Q , we call Q = (Q u ) u∈U a natural exponential family (NEF) generated by Q where for any u ∈ U we haveQ u (dy) = 1 M Q (u) exp(uy)Q(dy) .It follows that Q u is also a probability distribution over the reals for any u ∈ U by definition. An equivalent, useful form forQ u is Q u (dy) = exp(uy -ψ Q (u))Q(dy).In applications, u denotes an unknown parameter that is to be estimated based on observations from Q u . 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 U Q the natural parameter space.The distributions Q, Q u and parameter u are referred to as the base distribution, the (exponentially) tilted (base) distribution and the tilting parameter. An NEF is said to be regular whenU Q is open. It is easy to see that for any u, u 0 ∈ U Q , Q u = (Q u0 ) u-u0, where the distribution on the right-hand side stands for the tilt of Q u0 with parameter u -u 0 . As such, up to a constant shift of the parameter space, in a regular NEF, one can always assume that 0 ∈ U • Q . In fact, the same can be assumed for the parameter set, as long as U • is nonempty. If U is an interval then U • = ∅ means that U is a singleton: An uninteresting case if we want to model a host of non-identical distributions.In a regular family, an equivalent way to parameterize a NEF is using the mean function (cf. Theorem 3.6, page 74, of [Bro86] ),µ Q : U Q → R, which is defined as µ Q (u) = y Q u (dy) = y exp(uy)Q(dy) M Q (u) . Since Q 0 = Q, clearly, µ Q (0) is just the mean of Q.To minimize clutter, when Q is clear from the context, we will write µ instead of µ Q . To illustrate the developments so far, we consider the example when the base distribution is an exponential distribution.Example 1 (Exponential distributions). For λ > 0, let Q be an exponential distribution with parameter λ: Q(dy) = I{y ≥ 0}λe -λy dy. As is well known, the MGF of Q takes the formM Q (u) = λ λ-u when u < λ and M Q (u) = ∞ otherwise. Thus, U Q = {u ∈ R : M Q (u) < ∞} = (-∞, λ). The mean function takes the form of µ(u) = ∞ 0 λy exp(-λy) exp(uy)dy M Q (u) = 1 λ -u , u < λ .In what follows, we will need the following proposition to relate the central moments of Q u to the derivatives of ψ q , the CGF.Proposition 2. Let U • Q be non-empty. Then, ψ Q is infinitely differentiable on U • Q . Furthermore, the first three derivatives of ψ Q at u ∈ U Q give the first moment, second and third central moments of Q u .In the context of Example 1, Proposition 2 gives that ψ Q (u) = log(λ) -log(λ -u) when u < λ. Then, ψQ (u) = 1 λ-u , agreeing with our earlier computation. 
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 a study of when this property is satisfied. We include a result that shows how self-concordance allows one to derive tail properties of members of the family from that of the base distribution.In general, if the magnitude of a higher order derivative of a 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 is useful for studying how fast the function changes with its argument, as well as for deriving useful bounds on how well the function can be approximated by low order polynomials [NN94; Nes04; ST19]. In the context of single-parameter natural exponential families, we propose the following natural definition:EQUATIONAny function Γ : U → R + that satisfies Eq. (1) is called a stretch function of the NEF.This definition takes inspiration from the works of [Bac10; ST19; Fau+20] and [Jan+24] who define an analogous property (cf. Assumption 2 of [Jan+24] ). By Proposition 2, we know that μ(u) is the variance of Q u , while μ(u) is the third central moment. Hence, μ(u) is nonnegative, which explains why there is no absolute value on the right-hand side of Eq. (1).According to our definition, we require that the (absolute value) of the second derivative of µ is bounded by the first derivative, up to the "stretch factor" Γ(u). Clearly, provided that μ is positive over U, self-concordance is equivalent to stating that Γ Q (u) . = |μ(u)| μ(u) is finite valued over U. When μ(u) = 0 for some u ∈ U, one can show that Q u must be a Dirac distribution and hence so does Q (Q and Q u share their support). In this case, we also have μ ≡ 0 and hence any nonnegative valued function is a valid stretch-function. In particular, Γ Q ≡ 0 is also a valid stretch function.It turns out that studying self-concordance property of distributions in detail can turn out much finer bounds than naively bounding μ and μ separately. Example 3 (Avoiding exponential dependencies). Consider a NEF Q with base distribution Q, a Bernoulli distribution with parameter 1/2, we haveU Q = R, µ(u) = 1 1+e -u and thus μ = µ(1 -µ), μ = μ(1 -2µ). Hence Q is Γ Q -self-concordant with Γ Q (u) ≤ 1 for all u ∈ R. This is an example where naively bounding Γ Q , by bounding the numerator and denominator separately over [-s, s] for s > 0 gives a quantity of size e s , which lags far behind the constant we obtained with a direct calculation, or what we can get from the result in Section 3.2, which show a scaling of order O(s).As opposed to earlier literature where self-concordance is used [NN94; Bac10; ST19], we allow a non-constant stretch-factor Γ. As it turns out, this is necessary ifU = U • Q is to be allowed: Example 4 (Non-constant stretch factor). Consider a NEF Q with base distribution Q. For Q an exponential distribution with parameter λ > 0, Q is self-concordant over U = U Q = (-∞, λ) with Γ Q (u) = 2λ-u , u < λ. Indeed, a simple calculation gives that for u < λ, μ(u) = (λ -u) -2 and μ(u) = 2(λ -u) -3 , and so |μ(u)|/ μ(u) = 2/(λ -u).As was shown above, for the NEF built on the exponential distribution with parameter λ, 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.2 As it turns out, the growth of the stretch factor plays an important role in applications: Among other things, it 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 self-concordance to light tails). Let Q = (Q u ) u∈U be a NEF which is selfconcordant with stretch function Γ :U → R + where U is a subinterval of U • Q = (a, b). Then, for any u ∈ U, ψ Qu (s) ≤ sµ(u) + s 2 μ(u) for all s ∈ [-log(2)/K, log(2)/K] ∩ (a -inf U, b -sup U) , (2)where K = sup u∈U Γ(u).U is a strict subset of U • Q , 0 ∈ (a-inf U, b-sup U)and thus the result is nontrivial as long as K < ∞. To interpret this result, recall that a centered distribution Q is called subexponential with nonnegative parameters (ν, α) ifψ Q (s) ≤ s 2 ν 2 /2 , for all |s| ≤ 1/α (cf. 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 an zero-centered interval of length O( ν 2 /n + 1 αn ). Here, the first term describes a "subgaussian" behavior, while the second a "pure subexponential" behavior. Assume for simplicity that a = -b and inf U = -sup U. From Eq. (2) it follows that Q u , when centered, is subexponential with parameters ν 2 = 2 μ(u), twice the variance of Q u , and α = min(log(2)/K, b -sup U). In particular, we see that the growth of Γ impacts the lower-order term in the confidence interval (the term 1/(αn)), but not the leading term, which is governed by the variance of Q u . It follows that understanding how fast Γ can grow as its argument approaches the boundary of U Q is thus important, although its impact only appears in a low-order term.We now turn to our first main result that shows that the growth of Γ is at most inverse polynomial provided that the base distribution itself is subexponential.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:(i) Q is subexponential; (ii) The MGF of Q is defined in an open neighborhood of zero; (iii) For some positive constants C, c > 0, P(|Y | ≥ t) ≤ C exp(-ct) where Y ∼ Q.It will be useful to have a 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 is as follows (the result for the left-tail is omitted; it follows by symmetry):Proposition 6. Let c 1 , C 1 , c > 0, Y ∼ Q and assume that EY = 0. If P(Y ≥ t) ≤ C 1 exp(-c 1 t) for all t ≥ 0 (3) then for any 0 ≤ λ < c 1 , M Q (λ) < 1+ C1λ 2 c1(c1-λ) . Furthermore, for any c > 0 such that M Q (c) < ∞, P(Y ≥ t) ≤ M Q (c)e -ct holds for all t ≥ 0.The first part is nontrivial; the second follows easily from Chernoff's method. The proof is given in Appendix B.E right (c 1 , C 1 ) = {Q : Y = X -EX satisfies Eq. (3) where X ∼ Q} .In words, E right is the class of distributions over the reals whose right-tail displays an exponential decay governed with the rate parameter c 1 > 0 and scaling constant C 1 > 0. Similarly, we let E left (c 1 , C 1 ) be the class of distributions Q over the reals such that for X ∼ Q, Y = EX -X satisfies Eq. (3). With this notation, the first part of the previous proposition is equivalent to that ifQ ∈ E right (c 1 , C 1 ) is centered then M Q stays below the function λ → 1 + C1λ 2 c1(c1-λ) over the interval [0, c 1 ). In particular, this means that U Q contains [0, c 1 ).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 right (c 1 , C 1 ) ∩ E left (c 2 , C 2 ) for some positive constants c i , C i , i = 1, 2. Then, the NEF Q = (Q u ) u∈U is self-concordant. Moreover, the function Γ : U → R + defined by Γ(u) =        3 2 2eC 1 c 1 1 c1-u 2 + ub c1-u + G Q (C 1 , C 2 , c 1 , c 2 ) if 0 ≤ u < c 1 3 2 2ec 2 C 2 1 c2+u 2 + -ub c2+u + G Q (C 2 , C 1 , c 2 , c 1 ) if -c 2 < u < 0, is a stretch function for the NEF Q, where G Q (M 1 , M 2 , m 1 , m 2 ) is a polynomial whose coefficients depend on Q.The exact expression of G Q can be found in Eq. ( 8). Let Q be a NEF with base distribution Q when Q is a zero-mean Laplace distribution with variance 2λ 2 . In this case, we can choosec 1 = c 2 = 1/λ, C 1 = C 2 = 1/2. The actual stretch function is Γ Q (u) = 8λ 2 |u|(1/λ-u)(1/λ+u)(3λ 4 u 2 +λ 2 ) . Thus, the above theorem gives the correct behavior in that both the stretch function from the theorem and the actual stretch function Γ Q blow up with the inverse of the distance to the boundaries of U Q , except that the actual growth scales linearly with the inverse distance, while the theorem gives a quadratic scaling. It remains an open problem to see whether this quadratic order can be improved.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 a direct proof as part of the proof of Theorem 7). Corollary 8 (Distributions in regular NEFs are subexponential). Let u ∈ U • Q . Then Q u is subexponential 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 We sketch here the result for µ(0) = 0, μ(0) > 0 and u ≥ 0. The arguments used to extend the result to all cases can be found in Appendix C. By Proposition 2, bounding the stretch function of a NEF amounts to showingΓ Q (u) := |(y -µ(u))| 3 Q u (dy) (y -µ(u)) 2 Q u (dy) ≤ Γ(u),where the division by Var(Q u ) = (y -µ(u)) 2 Q(dy) 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 μ(0) = Var(Q) > 0, there exists a Q-dependent constant η > 0 and an interval [-b, -a] ⊂ R <0 s.t. Q([-b, -a]) ≥ η (Lemma 16). With this observation, we can show (Lemma 17):EQUATIONThus, the second moment decreases at most exponentially with the parameter u.Step 2: Controlling the absolute third central moment First, we use a classical result on moments of random variables (see the proof of i ⇒ ii for prop.2.5.2 in [Ver18] ):EQUATIONwhere Y ∼ Q u and B is a constant to be optimized. It should remain small enough for the first term not to blow up. On the other hand, it should be large enough for the second term divided by the lower bound obtained on μ(u) to remain controlled.To upper bound the second term in Eq. (5), we start by showing that the right tail of the tilted distribution Q u is also subexponential (Lemma 18):EQUATIONFollowing this lemma, we get an upper bound on µ(u) (Lemma 20):EQUATIONIn the proof, we bound separately the positive and negative values in the second term of Eq. ( 5):∞ B 3t 2 P(|Y -µ(u)| ≥ t)dt = ∞ B 3t 2 P(Y ≥ µ(u) + t)dt ♠ + ∞ B 3t 2 P(Y ≤ µ(u) -t)dt ♡ .We give here the sketch of proof on the bound of ♠ as the proof for bounding ♡ is nearly identical.From plugging in Eq. ( 6), we get:♠ ≲ 1 M Q (u) 1 c 1 -u ∞ B 3t 2 e -(c1-u)(t+µ(u)) dt. By choosing B ≳ ub c1-u + 1 c1-u 2, some algebra gives:♠ ≲ e -ub M Q (u) 1 + u 2 b 2 c 3 1 C 3 1 . Setting B ≳ 1 c1-u 2 + ubc2+u gives a similar bound on ♡. Chaining the bounds on ♠ and ♡ with Eq. ( 5) and Lemma 17 finishes the proof. □In this section we refine the previous result for NEFs by considering the case when the base distribution is subgaussian.Let σ > 0. Recall that a centered distribution Q is σ-subgaussian if for all u ∈ R, M Q (u) ≤ e σ 2 u 2 /2 (or, equivalently, ψ Q (u) ≤ σ 2 u 2 /2 for any u ∈ R). A non-centered distribution is σ-subgaussian, if it is subgaussian after centering.Similarly to the subexponential case, one can show that a centered distribution Q is subgaussian if and only if for some τ, C > 0, it holds that for any t ≥ 0,P(|X| ≥ t) ≤ C exp(-t 2 /(2τ 2 )) where X ∼ Q (cf. Proposition 2.5.2 of [Ver18]). 3Our promised result is as follows:Theorem 9. Let Q be subgaussian. Then, the NEF Q = (Q u ) u∈R is self-concordant and Γ Q (u) = O(|u|), u ∈ R.As it turns out, the linear growth exhibited in the previous result is tight for NEFs with a subgaussian base distribution: Theorem 10. There exists a distribution Q that is subgaussian such that lim sup u→∞ Γ Q (u)/u > 0.Again, this shows that even if 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.3 As for the quantitative relation between the parameters, it can be shown ( [RH23] ) that if for all u ∈ R,MQ(u) ≤ e σ 2 u 2 /2 , then P(|X| ≥ t) ≤ 2 exp(-t 2 /(2σ 2 ), and if P(|X| ≥ t) ≤ 2 exp(-t 2 /(2σ 2 )), then for all u ∈ R, MQ(u) ≤ e 4σ 2 u 2 .4 Generalized Linear BanditsIn this section we apply the self-concordance property of subexponential NEFs 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. 
bandit model: 
 Following Filippi, Cappe, Garivier, and Szepesvári [Fil+10] , we consider stochastic generalized linear bandit (GLB) models G specified by a tuple (X , Θ, Q), where X ⊆ R d is a non-empty arm set, Θ ⊆ R d is a non-empty set of potential parameters, both closed for convenience,Q = (Q u ) u∈U Q is a NEF with base distribution Q.Without the loss of generality we assume that X is a compact subset of the Euclidean unit ball of R d .In each round t ∈ N + , the learner selects and plays an arm X t ∈ X . As a response, they receive a reward Y t sampled from the distribution Q X ⊤ t θ⋆ , where θ ⋆ ∈ R d is a 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 whenU . = {x ⊤ θ : x ∈ X , θ ∈ Θ} ⊆ U • Qholds, which we assume from now on. The condition that U ⊆ U Q simply ensures that the reward distributions Q x ⊤ θ are defined regardless of the value of (x, θ) ∈ X × Θ. We require the stronger condition U ⊆ U • Q to exclude the boundaries of the interval U Q . This way we avoid pathologies that arise when a parameter reaches the boundary of U Q (e.g., when Q is the exponential distribution with parameter λ, the mean and variance of Q u grow unbounded as u approaches λ from below).The expected reward in round t given that the learner playsX t is E[Y t |X t ] = µ(X ⊤ t θ ⋆ ).The performance of the learner will be assessed by their pseudo regret R(T ), which is the total cumulative shortfall of the mean reward of the arms the learner chose relative to optimal choice:R(T ) = T t=1 µ(x ⊤ ⋆ θ ⋆ ) -µ(X ⊤ t θ ⋆ ) .Here, x ⋆ ∈ arg max x∈X µ(x ⊤ θ ⋆ ) is the arm that results in the best possible expected reward in a 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. In particular,Q ∈ E right (c 1 , C 1 ) ∩ E left (c 2 , C 2 ) for some c i , C i (i = 1, 2) positive numbers. Furthermore, -c 2 < inf U ≤ sup U < c 1 and c 1 , c 2 are known to the learner. Note that in a well-posed GLB, inf U Q < inf U ≤ sup U < sup U Q .In light of this, the assumption just stated boils down to whether 0 ∈ U • Q , which, as discussed, is free whenU • Q ̸ = ∅. Indeed, when 0 ∈ U • Q holds, inf U Q < 0 < sup U Q and one can always find positive values c 1 , c 2 such that inf U Q < -c 2 < inf U ≤ sup U < c 1 < sup U Q . Then, from Proposition 6 and some extra calculation one can conclude that the Q ∈ E right (c 1 , e -c1EX M Q (c 1 )) ∩ E left (c 2 , e -c2EX M Q (-c 2 )).Since it is assumed that the learner has access to Q, we see that Assumption 1 can be satisfied whenever 0 ∈ U • Q , which we think is a rather mild assumption. We will also for the sake of simplicity assume that the learner has access to S 0 = sup{∥θ∥ : θ ∈ Θ}, S 2 = inf U, S 1 = sup U. 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 is given access to an upper bound on the worst-case variance over the parameter space U:Assumption 2 (Bounded Variance). The learner is given L ≥ 1 such that sup u∈U μ(u) ≤ L.Note that since the GLB is well-posed, sup u∈U μ(u) < ∞ is automatically satisfied. Also, there is no loss of generality in assuming L ≥ 1. A crude upper bound on sup u∈U μ(u) is C 1 e/(c 1 -S 1 ) 3 ∨ C 2 e/(c 2 + S 2 ) 3 , so this assumption is implied by the previous one.Just like the previous works [Fil+10; LLZ17; Fau+20] which considered special cases of the generalized 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 t , based on past information, that contains the unknown parameter θ ⋆ with a controlled probability. Next, the algorithm chooses a parameter θ t , in the confidence set C t , and an underlying action X t ∈ X such that the mean reward underlying X t and θ t is as large as plausibly possible. Since µ = µ Q is guaranteed to be an increasing function (recall that μ(u) is the variance of Q u and is hence nonnegative), it suffices to find the maximizer of x ⊤ θ where (x, θ) ∈ X × Θ. 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.Require: GLB instance G = (X , Θ, Q) for t = 1, 2, . . . do Construct C t ⊂ Θ based on ((X s , Y s )) s<t and G Compute (X t , θ t ) ∈ arg max (x,θ)∈X ×Ct x ⊤ θ Select arm X t and receive reward Y t ∼ Q X ⊤ t θ⋆ end forThe 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 whereU Q = R and sup u∈U Γ Q (u) < ∞.The assumption that U Q = R is restrictive, as it does not allow many common distributions (e.g., the exponential distribution). Thanks to Theorem 7, under our assumptions,sup u∈U Γ Q (u) < ∞ follows.Then, an 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 1-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 ofsup u∈U Γ Q (u) > 1.This leads to the main result on GLBs: Theorem 11 (Regret upper bound of OFU-GLB). Let δ ∈ (0, 1] and T a positive integer and consider a well-posed GLB model G = (X , Θ, Q) and assume that Assumptions 1 and 2 hold. Forθ ⋆ ∈ Θ, let κ(θ ⋆ ) = 1 μ(x ⊤⋆ θ⋆) and let Regret(T, θ ⋆ ) stand for the T -round regret of OFU-GLB when it interacts with a GLB specified by θ ⋆ . Then, with an appropriate construction of C t , for any θ ⋆ ∈ Θ, it holds that with probability at least 1 -δ,Regret(T ) = Õ d μ(x ⊤ ⋆ θ ⋆ )T + dκ(θ ⋆ ) ,where Õ(•) hides polylogarithmic factors in T, d, L, 1/δ 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; APS11; LLZ17; Fau+20; Jun+21; Jan+24] all 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 it makes the dependence of the regret on the instance θ ⋆ explicit. Recalling that in a NEF, μ(u) is the variance of the tilted distribution Q u , 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 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 minimize service times (maximize negative reward) with an exponential bandit model (with mean function µ(x) = -1/x), the variance of the optimal arm's service time lower bounds that of the other arms. Furthermore, the dependence on κ, a term that is inversely proportional to the optimal variance, is pushed to a second order term. In logistic bandits, κ can be exponentially large in the size of the parameter set S 0 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-sized 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] or minimizing insurance claim severity (dollars lost per claim) [GKT16] .Our findings also have implications when performing maximum likelihood estimation with subexponential NEFs, which includes a rich family of generalized linear models (GLMs). Since the log loss in a NEF is the sum of a linear function and the NEF's CGF, the GLM's loss is self-concordant in 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: (i) fast rates of convergence to the minimizer for regularized empirical risk minimization [Mar+19] , (ii) fast rates for averaged stochastic gradient descent [Bac14] and (iii) fast rates for constrained optimization with first-order methods [Dvu+20] , without restrictive conditions on bounded responses, which previous works had to assume to achieve these results.One interesting direction for future work would be either deriving a matching lower bound on the 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. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA]Justification: The paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: The following extra notation will be used in the appendix: For vector x ∈ R d , we let ∥x∥ denote its ℓ 2 -norm and for positive definite matrix M ∈ R d×d , we use ∥x∥ M = √ x ⊤ M x to denote its M -weighted ℓ 2 -norm.We first prove Proposition 6, which we repeat for the convenience of the reader:Proposition 6. Let c 1 , C 1 , c > 0, Y ∼ Q and assume that EY = 0. If P(Y ≥ t) ≤ C 1 exp(-c 1 t)for all t ≥ 0 (3)then for any 0 ≤ λ < c 1 , M Q (λ) < 1+ C1λ 2 c1(c1-λ) . Furthermore, for any c > 0 such that M Q (c) < ∞, P(Y ≥ t) ≤ M Q (c)e -ct holds for all t ≥ 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 ≥ 0, c > 0. Then, by Chernoff's method, we haveP(Y ≥ t) ≤ E[e cX ]e -ct = M Q (c)e -ct .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)). We haveE[Y p + ] = ∞ 0 P(Y p + ≥ u)du = p ∞ 0 P(Y + ≥ t)t p-1 dt (change of variables with u = t p ) = p ∞ 0 P(Y ≥ t)t p-1 dt (for t > 0, {Y + ≥ t} = {Y ≥ t}) ≤ C 1 p ∞ 0 e -c1t t p-1 dt (assumption on Y ) ≤ C 1 p c p 1 ∞ 0 e -u u p-1 du (change of variables with u = c 1 t) = C 1 p c p 1 Γ(p -1) (definition of the Γ function) = C 1 c p 1 p! (property of the Γ function) Now let 0 ≤ λ < c 1 . Since Y ≤ Y + , we have M Q (λ) = E[e λY ] ≤ E[e λY+ ].Hence, by the power-series expansion of the exponential, we getM Q (λ) ≤ E e λY+ = 1 + ∞ p=2 λ p E Y p + p! ≤ 1 + C 1 ∞ p=2 λ c 1 p ≤ 1 + C 1 λ c 1 λ c 1 -λ .We note in passing that since λ < c 1 ,1 + C 1 λ c1 λ c1-λ ≤ 1 + C 1 λ c1-λ . That Eq. (3) implies that M Q (λ) ≤ 1 + C 1 λ c1-λcan also be obtained by refining the proof of Theorem 2.13 from the book of Wainwright [Wai19] .For the convenience of the reader we restate the theorem to be proven:Theorem 7. Let Q ∈ E right (c 1 , C 1 ) ∩ E left (c 2 , C 2 ) for some positive constants c i , C i , i = 1, 2. Then, the NEF Q = (Q u ) u∈U is self-concordant. Moreover, the function Γ : U → R + defined by Γ(u) =        3 2 2eC 1 c 1 1 c1-u 2 + ub c1-u + G Q (C 1 , C 2 , c 1 , c 2 ) if 0 ≤ u < c 1 3 2 2ec 2 C 2 1 c2+u 2 + -ub c2+u + G Q (C 2 , C 1 , c 2 , c 1 ) if -c 2 < u < 0, is a stretch function for the NEF Q, where G Q (M 1 , M 2 , m 1 , m 2) is a polynomial whose coefficients depend on Q.Note that the function Γ as defined above is non-decreasing on U ∩ R + and non-increasing on U ∩ R -.The actual form of G Q is as follows: let a, b, η > 0 be such that Q([-b + µ(0), -a + µ(0)]) > η and -a < 0. Then,G Q (M 1 , M 2 , m 1 , m 2 ) = 3 2 b + 1 a 2 η 204 e 3 m 3 1 M 3 1 + 6b 2 e 3 m 1 M 3 + 81M 2 + 9M 2 m 2 1 b 2 m 3 2 (8)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 Q(dy) = (1 -η)I(y ≥ 0)e -y dy + ηe -b δ {-b} (dy).u→-∞ Γ Q (u) = Ω(b) as b → ∞. And because Q ∈ E right (1, 1) ∩ E left (1, 1), this shows that the tail behavior of Q is indeed insufficient to control the behavior of Γ Q .We will prove this result in three parts:(i) Var(Q) = 0 (ii) Var(Q) > 0 and U = [0, c 1 ), (iii) Var(Q) > 0 and U = (-c 2 , 0].The result follows from combining these cases.The main work is to prove the result for U = [0, c 1 ), which is done in Proposition 13. Case (iii) is handled by "reflection around the origin" (Corollary 14). Case (i) is handled in Lemma 12 by showing thatΓ Q ≡ 0 if Var(Q) = 0.We start with case (i), the degenerate case when the variance of Q is zero.Lemma 12. If Var(Q) = 0 then U Q = R, Q u = Q for all u ∈ R, and Γ Q ≡ 0. If Var(Q) > 0 then μ is strictly positive over the entire set U • Q . Proof. If Var(Q) = 0, then Q is a Dirac on some {v}. Then for all u ∈ R, M Q (u) = exp(uv) < ∞ hence ψ Q = log M Q is supported on R and Q u (A) = 1 M Q (u) exp(uv) = 1 if v ∈ A 0 otherwise. Hence Q u = Q and Q = (Q u ) u∈R is trivially self-concordant with the stretch function defined to be Γ Q ≡ 0.For the second part, by Proposition 2, we have that μ(u) = (y -µ(u)) 2 Q u (dy) ≥ 0. We will show μ(u) ̸ = 0 by contradiction. Assume there existsu 0 ∈ U • Q such that μ(u 0 ) = (y - µ(u 0 )) 2 Q u0 (dy) = 0, then it follows that Q u0 (dy) is a Dirac on {µ(u 0 )}, which implies for all A ∈ B(R) Q(A) = M Q (u 0 ) • Q u0 (A) = M Q (u 0 ) {µ(u 0 )} ̸ ⊆ A 0 otherwisewhere B(R) denotes the Borel sets on R. Then it follows that Q(dy) is also a Dirac on R, which contradicts that Var(Q) > 0.Consider now the case when Var(Q) > 0. By the result just stated μ is bounded away from zero over U • Q and hence it is safe then to define Γ Q with the ratio |μ(u)| μ(u) :Γ Q (u) = |μ(u)| μ(u) , u ∈ U • Q .Thus, in order to show our result, it suffices to show Γ Q ≤ Γ with the function Γ as stated in the theorem. Thus, we will study Γ Q . First, notice that for all u ∈ U • Q , by Proposition 2,Γ Q (u) = | (y -µ(u)) 3 Q u (dy)| (y -µ(u)) 2 Q u (dy) ≤ |y -µ(u)| 3 Q u (dy) |y -µ(u)| 2 Q u (Let us now state the results that are concerned with cases (ii) and (iii) mentionned above. For case (ii), i.e., when U = [0, c 1 ) we have the following result:Proposition 13. Let Q ∈ E right (c 1 , C 1 ) ∩ E left (c 2 , C 2 ) and U = [0, c 1 ). Define Γ : U → R + by Γ(u) = 3 2 2c 0 1 c 1 -u 2 + ub c 1 -u + |u|b c 1 + |u| + 1 a 2 η 204 + 6u 2 b 2 c 3 0 + 81C 2 + 9C 2 u 2 b 2 (u + c 2 ) 3 ≤ 3 2 2c 0 1 c 1 -u 2 + ub c 1 -u + G Q (C 1 , C 2 , c 1 , c 2 ) ,wherec 0 = C 1 • c 1 • e.Then, for appropriate values of η, a, b > 0 that depend on the base distributionQ, we have Γ Q ≤ Γ over U.For case (iii), i.e., when U = (-c 2 , 0], we have the following result:Corollary 14. Let Q ∈ E right (c 1 , C 1 ) ∩ E left (c 2 , C 2 ) and U = (-c 2 , 0]. Define Γ : U → R + by Γ(u) = 3 2 2c 0 1 c 2 -|u| 2 + |u|b c 2 -|u| + |u|b c 1 + |u| + 1 a 2 η 204 + 6u 2 b 2 c 3 0 + 81C 1 + 9C 1 u 2 b 2 (|u| + c 1 ) 3 ≤ 3 2 2c 0 1 c 2 -|u| 2 + |u|b c 2 -|u| + G Q (C 2 , C 1 , c 2 , c 1 ),where c 0 = C 2 • c 2 • e.Then, for appropriate values of η, a, b > 0 that depend on the base distribution Q, we have Γ Q ≤ Γ over U.The key idea is to convert μ(•) and μ(•) 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 self-concordance properties of a NEF do not change when the base distribution is shifted by a constant:Lemma 15. Let Y ∼ Q, c ∈ R and define Q +c to be the distribution of Y + c. Then, U Q = U Q +c , M Q+c (u) = e -uc M Q (u) for all u ∈ R, and Γ Q = Γ Q +c (here, we take U = U Q = U Q +c ). Proof. By definition M Q (u) = Ee uY and M Q +c (u) = Ee u(Y +c). Hence,M Q +c (u) = Ee u(Y +c) = e uc Ee uY = e uc M Q (u) .This shows that U Q = U Q +c and that the desired relationship between M Q and M Q +c hold. Now, from the definition that the CGF is the logarithm of the MGF, it follows thatψ Q +c (u) = uc + ψ Q (u).Hence, ψQ +c = ψQ and ψQ +c = ψQ , which implies thatΓ Q = Γ Q +c .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 Q is zero, we will also assume with no loss of generality in some of the results below that Q has positive variance. Lemma 16. Take a distribution Q with zero mean and positive variance. Then, there exist η > 0 and 0 < a ≤ b distribution dependent constants such that Q([-b, -a]) ≥ η.Proof. Since μ(0) = Var(Q) > 0, there exists a > 0 and α > 0 such that Q((-∞, -a])) > α. Aslim x→0 Q((-∞, -x])) = 0, we can find some b > 0 s.t. Q ((-∞, -b]) ≤ α 2 .This implies:Q ([-b, -a]) ≥ α 2 .The lemma thus holds with a and b described above, and η = α 2 . Lemma 17. Take a distribution Q with zero mean and positive variance. With η, a, b as in Lemma 16, for all u ∈ U • Q , it holds thatμ(u) ≥ a 2 η e -ub M Q (u) .Proof. For a, b described in Lemma 16, we have:R (y -µ(u)) 2 Q u (dy) ≥ -a -b (y -µ(u)) 2 Q u (dy), ≥ -a -b (y -µ(0)) 2 exp(uy) M Q (u) Q(dy), ≥ a 2 exp(-ub) M Q (u) -a -b Q(dy), ≥ a 2 e -ub M Q (u) η.The first inequality holds as (y -µ(u)) 2 is non-negative; the second as µ(u) increases with u; the third as -b ≤ -a < µ(0), µ(0) = 0 and u ≥ 0; and the last one by Lemma 16.For the upper bound, we present lemmas that bound the (upper and lower) tails of Q u and the mean µ(u).Lemma 18. Take Q ∈ E right (c 1 , C 1 ) a centered distribution. Then, for all 0 ≤ u < c 1 and t ≥ 0, we haveQ u ((t, +∞)) ≤ C 1 e M Q (u) e -(c1-u)t 1 + u c 1 -u .Proof. The inequality is trivially satisfied when u = 0. Indeed, in this caseQ = Q 0 , M Q (0) = 1, which together with Q ∈ E right (c 1 , C 1 ) implies the inequality.Let us now assume that 0 < u < c 1 . Let v > 0 be a constant to be chosen later. Then we have thatM Q (u)Q u ((t, ∞)) = ∞ t e uy Q(dy) = ∞ k=0 t+(k+1)v t+kv e uy Q(dy) ≤ ∞ k=0 e u(t+kv+v) +∞ t+kv Q(dy) ≤ ∞ k=0 e u(t+kv+v) C 1 e -c1(t+kv) = C 1 e -(c1-u)t e uv ∞ k=0e -(c1-u)vk .We choose v = 1/u > 0. Then M Q (u)Q u ((t, ∞)) can be upper bounded byM Q (u)Q u ((t, ∞)) ≤ C 1 e • e -(c1-u)t ∞ k=0 e -c 1 -u u k = C 1 e • e -(c1-u)t 1 1 -e -c 1 -u u ≤ C 1 e • e -(c1-u)t 1 + u c 1 -u ,where in the last inequality, we used the fact that for all x > 0, e x e x -1 ≤ 1 + 1 x .Remark 1. For Q a centered exponential distribution Exp(c) with rate parameter c, the moment generating function isM Q (u) = e -u c c c-u . On the other hand, Q u (t, ∞) = e -u c e -(c-u)t. So Lemma 18 is order tight in its dependency on c -u.Lemma 19. Take Q ∈ E left (c 2 , C 2 ) a centered distribution. Then, for all u, t ≥ 0, we haveQ u ((-∞, -t)) ≤ 1 M Q (u)C 2 e -(u+c2)t .Proof. We again separate the u = 0 case. When u = 0,Q = Q 0 , M Q (0) = 1 and the inequality is equivalent to Q ∈ E left (c 2 , C 2 ).Consider now u > 0. Then,M Q (u)Q u ((-∞, -t)) = -t -∞ e uy Q(dy), ≤e -ut -t -∞ Q(dy),≤C 2 e -ut-c2t .Lemma 20. Take Q ∈ E right (c 1 , C 1 ) with zero mean and positive variance. Definec 0 = c 1 • C 1 • e.Then, for all 0 ≤ u < c 1 , it holds that0 = µ(0) ≤ µ(u) ≤ c 0 1 c 1 -u 2 .Proof. For u = 0, µ(0) = 0 which satisfies the inequality. We now consider 0 < u < c 1 . We haveµ(u) = +∞ 0 Q u ((y, +∞)) dy - 0 -∞ Q u ((-∞, -y)) dy ≤ +∞ 0 Q u ((y, +∞)) dy.By Lemma 18, this implies:µ(u) ≤ C 1 e M Q (u) ∞ 0 e -(c1-u)t c 1 c 1 -u dt = C 1 e M Q (u) c 1 c 1 -u 1 c 1 -u = c 1 C 1 e M Q (u) 1 c 1 -u 2 . By Jensen's inequality, M Q (u) = E Q [e uY ] ≥ e uE Q [Y ] = 1, finishing the proof.Proof of Proposition 13. As noted beforehand, since the statement holds trivially when the variance of Q is zero, we assume it is positive. By our discussion beforehand, we also assume first that Q is centered, so µ(0) = 0.Let Y ∼ Q u . Take B > 0 a constant to be optimized later. We haveEQUATION.The following bound holds:EQUATIONWe also have:(ii) ≤ +∞ B 3t 2 P (Y -µ(u) ≥ t) dt (ii,a) + +∞ B 3t 2 P (Y ≤ -(t -µ(u))) dt (ii,b).Set B = 2c 0 1 c1-u 2 + ub c1-u + ub u+c2 and B ′ = 2c 0 1 c1-u 2. Then we can upper bound (ii, a) using Lemma 18.(ii, a) ≤ c 0 M Q (u) 1 c 1 -u ∞ B 3t 2 e -(c1-u)(t+µ(u)) dt ≤ c 0 M Q (u) 1 c 1 -u ∞ B 3t 2 e -(c1-u)t dt ≤ c 0 e -ub M Q (u) 1 c 1 -u ∞ B 3t 2 e -(c1-u)(t-ub c 1 -u ) dt = c 0 e -ub M Q (u) 1 c 1 -u ∞ B-ub c 1 -u 3 t + ub c 1 -u 2 e -(c1-u)t dt ≤ 6c 0 e -ub M Q (u) 1 c 1 -u ∞ B ′ t 2 + ub c 1 -u 2 e -(c1-u)t dt = 6c 0 e -ub M Q (u)      1 c 1 -u ∞ B ′ t 2 e -(c1-u)t dt (iii,a) + 1 c 1 -u ∞ B ′ ub c 1 -u 2 e -(c1-u)t dt (iii,b)     where in the third inequality we used the fact that (a + b) 2 ≤ 2a 2 + 2b 2 for all a, b ∈ R and that B ′ < B -ub c1-u . We now bound (iii, a). We have thatB ′ (c 1 -u) = 2c 0 1 c1-u and (iii, a) = 1 (c 1 -u) 4 e -B ′ (c1-u) [B ′ (c 1 -u) + 1] 2 + 1 ≤ 2 (c 1 -u) 4 e -B ′ (c1-u) (B ′ (c 1 -u) + 1) 2 ≤ 4 (c 1 -u) 4 e -B ′ (c1-u) [B ′ (c 1 -u)] 2 + 1 = 4 (c 1 -u) 4 e -2c0 1 c 1 -u 4c 2 0 1 c 1 -u 2 + 1 = 16c 2 0 (c 1 -u) 6 e -2c0 1 c 1 -u + 4 (c 1 -u) 4 e -2c0 1 c 1 -u ≤ 16 • c 2 0 • 1 c 6 0 c 0 1 c 1 -u 6 • e -2c0 1 c 1 -u + 4 • 1 c 4 0 c 0 1 c 1 -u 4 • e -2c0 1 c 1 -u ≤ 32 c 4 0 + 2 c 4 0 (x 6 e -2x ≤ 2 and x 4 e -2x ≤ 0.5 for all x ≥ 0.)Similarly, for (iii, b), we have that(iii, b) ≤ 2 c 1 -u ∞ B ′ u 2 b 2 (c 1 -u) 2 e -(c1-u)t dt = 2u 2 b 2 (c 1 -u) 3 e -B ′ (c1-u) c 1 -u ≤ 2u 2 b 2 (c 1 -u) 4 e -2c0 1 c 1 -u ≤ 2u 2 b 2 c 4 0 c 0 c 1 -u 4 e -2c0 1 c 1 -u ≤ u 2 b 2 c 4 0 (x 4 e -2x ≤ 0.5 for all x ≥ 0.)Putting the result together, (ii, a) can be upper bounded as(ii, a) ≤ 6c 0 e -ub M Q (u) 32 c 4 0 + 2 c 4 0 + u 2 b 2 c 4 0 ≤ e -ub M Q (u) 204 + 6u 2 b 2 c 3 0 .By Lemma 20, B ≥ µ(u) + ub c2+u . Hence By Lemma 19 we have: t 2 e -(u+c2)t dt (iv,a)(ii, b) ≤ C 2 M Q (u) +∞ B 3t 2 C 2 e -(u+c2)(t-µ(u)) dt, ≤ C 2 e -ub M Q (u) +∞ B 3t 2 C 2 e -(u+c2)(t-µ(u)-ub u+c 2 ) dt, ≤ 9C 2 e -ub M Q (u) +∞ B-µ(u)-ub u+c 2 t 2 + µ(u) 2 + ub u + c 2 2 e -(u+c2)t dt.+ +∞ B-µ(u)-ub u+c 2 µ(u) 2 e -(u+c2)t dt (iv,b) + ∞ B-µ(u)-ub u+c 2 ub u + c 2 2 e -(u+c2)t dt (iv,c).B -µ(u) -ub u+c2 ≥ c 0 1 c1-u 2 =: B ′′ . We then have that (iv, a) ≤ +∞ B ′′ t 2 e -(u+c2)t dt ≤ e -B ′′ (u+c2) (u + c 2 ) 3 ((B ′′ (u + c 2 ) + 1) 2 + 1) ≤ 2e -B ′′ (u+c2) (u + c 2 ) 3 (B ′′ (u + c 2 ) + 1) 2 ≤ 4e -B ′′ (u+c2) (u + c 2 ) 3 ([B ′′ (u + c 2 )] 2 + 1) ≤ 4 (u + c 2 ) 3 e -B ′′ (u+c2) [B ′′ (u + c 2 )] 2 + e -B ′′ (u+c2) ≤ 8 (u + c 2 ) 3For (iv, b), note that B ′′ ≥ µ(u) by Lemma 20 and we have that(iv, b) ≤ µ(u) 2 ∞ B ′′ e -(u+c2)t dt ≤ B ′′ 2 (u + c 2 ) e -B ′′ (u+c2) ≤ 1 (u + c 2 ) 3 (B ′′ (u + c 2 )) 2 e -B ′′ (u+c2) ≤ 1 (u + c 2 ) 3 . For (iv, c), (iv, c) ≤ u 2 b 2 (u + c 2 ) 2 ∞ B ′′ e -(u+c2)t dt ≤ u 2 b 2 (u + c 2 ) 2 1 u + c 2 e -B ′′ (u+c2) ≤ u 2 b 2 (u + c 2 ) 3 .Putting bounds on (iv, a), (iv, b) and (iv, c) together, we have that(ii, b) ≤ 9C 2 e -ub M Q (u) 9 + u 2 b 2 (u + c 2 ) 3 ≤ e -ub M Q (u) 81C 2 + 9C 2 u 2 b 2 (u + c 2 ) 3Combining the bounds on (ii, a) and (ii, b) with Lemma 17 we get:(ii) μ(u) ≤ 1 a 2 η 204 + 6u 2 b 2 c 3 0 + 81C 2 + 9C 2 u 2 b 2 (u + c 2 ) 3 .Chaining the result with the bound on (i) together as well as the choice that B = 2c 01 c1-u 2 + ub c1-u + ub u+c2 , we obtain μ(u) μ(u) ≤ 3 2 2c 0 1 c 1 -u 2 + ub c 1 -u + 3 2 b + 1 a 2 η 204 + 6u 2 b 2 c 3 0 + 81C 2 + 9C 2 u 2 b 2 (u + c 2 ) 3 ≤ 3 2 2c 0 1 c 1 -u 2 + ub c 1 -u + ub u + c 2 + 1 a 2 η 204 + 6c 2 1 b 2 (c 1 • C 1 • e) 3 + 81C 2 + 9C 2 c 2 1 b 2 c 3 2 =G Q (C1,C2,c1,c2).Let us now study the case µ Q (0) ̸ = 0. Let a, b, η > 0 be such that Q([-b + µ(0), -a + µ(0)]) > η and -a < 0. With Q -µ(0) the centered version of Q, this gives Q -µ(0) ([-b, -a]) > η. We have just shown that for all u ∈ [0; c 1 ),:Γ Q -µ(0) (u) ≤ 3 2 2c 0 1 c 1 -u 2 + ub c 1 -u + ub u + c 2 + G Q (C 1 , C 2 , c 1 , c 2 ).By Lemma 15, we have Γ Q -µ(0) = Γ Q , hence:Γ Q (u) ≤ 3 2 2c 0 1 c 1 -u 2 + ub c 1 -u + ub u + c 2 + G Q (C 1 , C 2 , c 1 , c 2 ).Lemma 21. Let Y ∼ Q, and Q -let be the distribution of -Y . ThenU Q = -U Q -and for any u ∈ U • Q , we have Γ Q (u) = Γ Q -(-u).Proof. Recall that if Q has zero variance, Γ Q ≡ 0 and hence the statement is trivial. Otherwise, foru ∈ U • Q , Γ Q (u) = | ... ψ Q (u)|/ ψQ (u). Now, for v ∈ R, M Q -(v) = E[e (-Y )v ] = E[e (-v)Y ] = M Q (-v) . Hence, U Q = -U Q -and for any v ∈ U Q , ψ Q (v) = ψ Q -(-v). Taking derivatives of both sides, ψQ (v) = -ψQ -(-v) , ψQ (v) = ψQ -(-v) , ... ψ Q (v) = - ... ψ Q -(-v) , which immediately implies the statement, noting that the variance of Q is positive if and only if the variance of Q -is positive.Proof of Corollary 14. Assume that Q ∈ E right (c 1 , C 1 ) ∩ E left (c 2 , C 2 ). Since the statement holds trivially when Var(Q) = 0, assume Var(Q) > 0. Then, Q -∈ E right (c 2 , C 2 ) ∩ E right (c 1 , C 1 ). We then get the stated result by applying Proposition 13, combined with Lemma 21. To be more specific, for all u ∈ (-c 2 , 0], from these two results it follows thatΓ Q (u) = Γ Q -(-u) ≤ 3 2 2c 0 1 c 2 -|u| 2 + |u|b c 2 -|u| + |u| c 1 + |u| b + 1 a 2 η 204 + 6u 2 b 2 c 3 0 + 81C 1 + 9C 1 u 2 b 2 (u + c 1 ) 3 ≤ 3 2 2c 0 1 c 2 -|u| 2 + |u|b c 2 -|u| + b + 1 a 2 η 204 + 6c 2 2 b 2 c 3 0 + 81C 1 + 9C 1 c 2 2 b 2 c 3 1 , where c 0 = C 2 • c 2 • e.Let Q be a regular NEF with base distribution Q. By definition, this means thatU Q is an open interval. Take any u ∈ U • Q . There exist some ϵ > 0 s.t. M Q (u -ϵ), M Q (u + ϵ) < ∞.We also have:M Q (u + ϵ) = exp(ϵu) exp(uy)Q(dy) = exp(ϵu)M Q (u)Q u (dy) = M Q (u)M Qu (ϵ). Similarly, M Qu (-ϵ) = M Q (u-ϵ) M Q (u) . By Proposition 6, this implies Q u ∈ E left M Q (u-ϵ) M Q (u) , ϵ ∩ E right M Q (u+ϵ) M Q (u) , ϵ .For the convenience of the reader we restate the theorems to be proven.Theorem 9. Let Q be subgaussian. Then, the NEF Q = (Q u ) u∈R is self-concordant and Γ Q (u) = O(|u|), u ∈ R.Theorem 10. There exists a distribution Q that is subgaussian such that lim sup u→∞ Γ Q (u)/u > 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 thatP(|X| ≥ t) ≤ C exp(- ct 2 2 ) for all t ≥ 0 (10)where 10), where X ∼ Q} .X ∼ Q. Let G(c, C) = {Q : Y = X -EX satisfies Eq. (This definition is very close to that of E right . 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 > 0.For the interested reader, we also report here without proof some classical results on the quantitative relation between the M GF and the tail bounds of subgaussian distributions. Details can be found in the textbook [RH23] .). If for all u ∈ R,M Q (u) ≤ e σ 2 u 2 /2 , then P(|X| ≥ t) ≤ 2 exp(-t 2 /(2σ 2 ), and if P(|X| ≥ t) ≤ 2 exp(-t 2 /(2σ 2 )), then for all u ∈ R, M Q (u) ≤ e 4σ 2 u 2 .Lemma 12 still holds for Q a subgaussian distribution, hence the theorem holds trivially for μ(0) = 0. Lemma 15 can also be applied for Q a subgaussian distribution. Thus, as in the proof for subexponential distributions, the first step is to show the result when µ(0) = 0 and μ(0) > 0.Note that the lower bound on μ(u) of Lemma 17 still holds when μ(0) > 0. We turn to upper bounding |y -µ(u)| 3 Q u (dy). The following Lemmas are first steps in that direction.Lemma 23. Take Q ∈ G(c, C) a centered distribution. For all u ≥ 0 and t ≥ 4 c + 1 u + 4 c , we have:Q u ((t, +∞)) ≤ C 1 M Q (u) e -ct 2 4 ,whereC 1 = C 1 + π c .Proof. We have .M Q (u)Q u ((t, +∞)) =(11)The first inequality holds as u ≥ 0, the second by subgaussianity assumption. As t ≥ 4 c + 1 u + 4 c , we have u ≤ c 4 t and:EQUATION)This implies u(t + 1) ≤ c 4 t 2 on top of u ≤ c 4 t. Thenu(t + 1 + k) ≤ c 4 t 2 + kt ≤ c 4 (t + k) 2 .Reinjecting in Eq. ( 11), we get:M Q (u)Q u ((t, +∞)) ≤C +∞ k=0 e -c(t+k) 2 4 , ≤Ce -ct 2 4 +∞ k=0 e -ck 2 4 . ≤Ce -ct 2 4 1 + ∞ 0 e -cx 2 4 dx ≤C 1 + π c e -ct 2 4 .Lemma 24. Take Q ∈ G(c, C) a centered distribution. For all u, t ≥ 0, we have:Q u ((-∞, -t)) ≤ C M Q (u) e -ut-ct 2 2 .Proof. We have thatEQUATION)where the last inequality holds by subgaussianity of Q.Lemma 25. Take Q ∈ G(c, C) a centered distribution. For all u ≥ 0 the following holds:0 = µ(0) ≤ µ Q (u) ≤ 4 c + 1 u + 4 c + C 3 e -4u 2 c ,whereC 3 = √ π √ c C 1 .Proof. We have:µ(u) = +∞ 0 Q u ((y, +∞)) dy - 0 -∞ Q u ((-∞, -y)) dy ≤ +∞ 0 Q u ((y, +∞)) dy ≤ 4 c + 1 u + 4 c + +∞ ( 4 c +1)u+ 4 c Q u ((y, +∞)) dy.By Lemma 23, this implies:µ(u) ≤ 4 c + 1 u + 4 c + C 1 M Q (u) +∞ ( 4 c +1)u+ 4 c e -cy 2 4 dy ≤ 4 c + 1 u + 4 c + C 1 e -c (( 4 c +1 ) u+ 4 c ) 2 4 M Q (u) +∞ 0 e -cy 2 4 dy ≤ 4 c + 1 u + 4 c + C 1 M Q (u) e -4u 2 c +∞ 0 e -cy 2 4 dy. By Jensen's inequality, M Q (u) = E Q [e uY ] ≥ e uE Q [Y ] = 1. Noting that +∞ 0 e -cy 2 4 dy ≤ √ π √ cterminates the proof.Proof of Theorem 9. As previously noted, we first show the result when µ(0) = 0 and μ(0) > 0. We start with u > 0, then by Lemma 21 will extend the bound to u < 0.Take u > 0 and B > 0 a constant to be optimized later. We have:|Y -µ Q (u)| 3 Q u (dy) = +∞ 0 3t 2 P (|Y -µ Q (u)| ≥ t) dt, ≤ B 0 3t 2 P (|Y -µ Q (u)| ≥ t) dt (i) + +∞ B 3t 2 P (|Y -µ Q (u)| ≥ t) dt (ii).The first equality is a 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:EQUATION)We also have:(ii) ≤ +∞ B 3t 2 P (Y -µ Q (u) ≥ t) dt (ii,a) + +∞ B 3t 2 P (Y ≤ -(t -µ Q (u))) dt (ii,b).Set B = µ Q (u) + 4 c + 1 u + 4 c + b, where b was defined in Lemma 17. As B ≥ 4 c + 1 u + 4 c , by Lemma 23, we have:(ii, a) ≤ +∞ B 3t 2 Q u ((t, +∞)) dt, ≤ C 1 M Q (u) +∞ B 3t 2 e -ct 2 4 dt, ≤ 3C 1 M Q (u) +∞ 0 (B + t) 2 e -c(B+t) 2 4 dt, ≤ 6C 1 e -cB 2 4 M Q (u) +∞ 0 (B 2 + t 2 )e -ct 2 4 dt, = 6C 1 e -cB 2 4 M Q (u) (B 2 + 2 c ) +∞ 0 e -ct 2 4 dt, = 6C 1 M Q (u) π c (B 2 + 2 c )e -cB 2 4 .where the first equality holds as for any a > 0, using integration by part we have thatEQUATION) Denote B ′ = B -µ Q (u) = 4 c + 1 u + 4 c + b.By Lemma 24 we have:(ii, b) ≤ +∞ B 3t 2 C 2 M Q (u) e -u(t-µ Q (u))-c(t-µ Q (u)) 2 2 dt, = 3C 2 M Q (u) +∞ B ′ (t + µ Q (u)) 2 e -ut-ct 2 2 dt, ≤ 3C 2 e -4 c u 2 -bu M Q (u) +∞ B ′ (t + µ Q (u)) 2 e -ct 2 2 dt, ≤ 3C 2 e -4 c u 2 -bu M Q (u) e -c(B ′ ) 2 2 +∞ 0 (t + B ′ + µ Q (u)) 2 e -ct 2 2 dt, ≤ 6C 2 e -4 c u 2 -bu M Q (u) e -c(B ′ ) 2 2 +∞ 0 t 2 + B 2 e -ct 2 2 dt, ≤ 6C 2 e -4 c u 2 -bu M Q (u) e -c(B ′ ) 2 2 1 c + B 2 +∞ 0 e -ct 2 2 dt, ≤ 6e -12 c u 2 -bu M Q (u) 1 c + B 2 +∞ 0 C 2 e -ct 2 2 dt C4 .where in the second line we use change of variable; third line we use the fact that B ′ > 4 c u + b, hence e -ut ≤ e -B ′ u ≤ e -(ii) μQ (u) ≤ 6 a 2 η C 4 1 c + B 2 e -12 c u 2 + C 3 2 c + B 2 e -cB 2 4 +ub . As B ≥ 4 c u + b, we have cB 2 4 + ub ≥ 4 c u 2 . This implies (ii) μQ (u) ≤ 6(C 3 + C 4 ) a 2 η 2 c + B 2 e -4 c u 2 .With Equation 14, we getΓ Q (u) ≤ 6(C 3 + C 4 ) a 2 η 2 c + B 2 e -4 c u 2 + 3B 2 . By Lemma 25, µ Q (u) ≤ 4 c + 1 u + 4 c + C 3 , which implies : B ≤ 2 4 c + 1 u + 8 c + b + C 3 .For any constants w 1 , w 2 > 0, we have w 1 u 2 e -w2u 2 ≤ w1 √ w2 u. This implies that for u > 0:Γ Q (u) = O(u). Note that if Q ∈ G(c, C), with Q -the distribution of -Y , Y ∼ Q, we have Q -∈ G(c, C).By Lemma 21, that implies:Γ Q (-u) = Γ Q -(u) = O(u).Therefore, for u ∈ R:Γ Q (u) = O(|u|).As, by Lemma 12, Γ Q is constant for μ(0) = 0, it remains now only to show the theorem if µ(0) ̸ = 0 and μ(0) > 0. We have just shownΓ Q -µ(0) (u) = O(|u|), with Q -µ(0) the centered version of Q. by Lemma 15, we have Γ Q = Γ Q -µ(0) . Hence, for any Q ∈ G(c, C): Γ Q (u) = O(|u|).We construct a distribution Q s.t. for any s > 0, we can find some u > s with :EQUATIONwithEQUATIONwhere C 1 is a normalizing constant. By definition, we have that Q u (dy) = i≥1 q i δ 2 i (dy) whereEQUATIONWe are going to inspect|E[(Y -µ(u)) 3 ]| E[(Y -µ(u)) 2 ]for i a positive even number large enough and u = 2 i+1 . By definition, we have that Q u (dy) = i≥1 q i δ 2 i (dy) whereEQUATIONFirst, we remark a few simple equalities and inequalities that will prove useful in the subsequent computations.Not that P U = 2 i = C1 M Q (u) e 4 i , hence:EQUATIONThis implies:EQUATIONand, combining with Equation Eq. ( 19),EQUATION)From this last equation we get upper bound:EQUATION)The two next Lemma combined show that for any even i ≥ 4, 1.24× 2 i ≤ µ(u) ≤ 1.26 × 2 i .Lemma 26. Let i ≥ 4 be an even number and u = 2 i+1 . For random variable U ∼ Q u (dy), it holds that:EQUATIONProof. Consider j < i, j even. By Eq. ( 23),P U = 2 j P (U = 2 i ) ≤ e 2 i+j+1 -3×4 j-1 -4 i .Denote f 1 (j) = 2 i+j+1 -3 × 4 j-1 -4 i . The monotonicity of the right hand side, e f1(j) , is the same as f 1 (j). Take derivative of f 1 (j), we have thatf ′ 1 (j) = 2 j • 2 i+1 ln 2 -3 × 4 j-1 ln 4 = 2 j (2 i+1 ln 2 -3 × 2 j-2 ln 4) = 2 j ln 4(2 i -3 × 2 j-2 ). Since i > j we have that f ′ 1 (j) ≥ 0 for j ∈ [0, i].Hence the right hand side increases with j, as j ≤ i -1, we have thatEQUATION)This implies:EQUATIONWe now prove the lower bound on the mean.µ(u) ≥2 i+1 P(U = 2 i+1 ) + 2 i P(U = 2 i ) + 2 i P(U > 2 i+1 ) =2 i+1 P(U = 2 i+1 ) + 2 i P(U = 2 i ) + 2 i (1 -P(U < 2 i ) -P(U = 2 i ) -P(U = 2 i+1 )) ≥2 i + 2 i+1 -2 i P(U = 2 i+1 ) -2 i P(U < 2 i ) =2 i + 2 i P(U = 2 i ) P(U = 2 i+1 ) P(U = 2 i ) - P(U < 2 i ) P(U = 2 i ) ≥2 i + 2 i 1 4 -0.001 P(U = 2 i ) ≥1.24 × 2 i ,where the fourth line holds because of Eqs. ( 20) and (26).Lemma 27. Let i be a positive even number and u = 2 i+1 . For random variable U ∼ Q u (dy), it holds that:EQUATIONProof. By Eq. ( 23), for any j ≥ i + 2, we have:EQUATION)This implies:j>i+1 2 j P u U = 2 j P (U = 2 i ) ≤ e -4 i j>i+1 2 j e -2 j-1 ≤   ∞ j=4 2 j e -2 j-1   e -4 i .We turn to bounding∞ j=4 2 j e -2 j-1 : ∞ j=4 2 j e -2 j-1 = 2 ∞ j=4 2 j-1 e -2 j-1 = 2 ∞ j=3 2 j e -2 j , ≤ 2 ∞ 2 2 x e -2 x dx, = 2 ∞ 2 1 y ln 2 ye -y dy, = 2 e 4 ln 2,where the second inequality holds as 2 x e -2 x is decreasing for x > 0. Hence, for any i ≥ 2:EQUATIONWe are now ready to upper bound µ u :µ u ≤ 2 i-1 P(U < 2 i ) + 2 i P(U = 2 i ) + 2 i+1 P(U = 2 i+1 ) + j>i+1 2 j P(U = 2 j ) ≤ 2 i P (U = 2 i )   1 2 P (U < 2 i ) P (U = 2 i ) + 1 + 2 P (U = 2 i+1 ) P (U = 2 i ) + 1 2 i j>i+1 2 j P u U = 2 j P (U = 2 i )   ≤ 2 i 4 5 1 2 × 0.001 + 1 + 1 2 + 1 100 < 1.26 • 2 i ,where we get the third inequality from Eqs. (20), ( 21), ( 26) and (29).Proof for Theorem 10. Let U ∼ Q u where u = 2 i+1 for i ≥ 4 an even number. We first derive an upper bound on the variance EEQUATIONwhere the last inequality is obtained from Eqs. ( 20), ( 21), ( 26) and (28).We inspect the infinite series in the above inequality . Note that 2 2j e -2 j-1 is decreasing for j ≥ 1.j>i+1 2 2j e -2 j-1 ≤ 4 j≥2 4 j e -2 j ≤ 4 ∞ 1 4 x e -2 x dx = 4 ∞ 2 1 y ln 2 y 2 e -y dy = 12 ln 2 • e 2 .For all i ≥ 1, it follows that e -4 i 2 2i12 ln 2 • e 2 ≤ 0.02. Plugging into Equation 30, we have:EQUATIONOn the other hand, by Lemmas 26 and 27, we have thatU -µ(u) ≥                0.74 • 2 i A large if U ≥ 2 i+1 -0.26 • 2 i A medium if U = 2 i -1.26 • 2 i A small if U < 2 i .Then we can lower bound the third central momentE[|U -µ(u)| 3 ]. E[(U -µ(u)) 3 ] ≥ P(U ≥ 2 i+1 )A 3 large + P(U = 2 i )A 3 medium + P(U < 2 i )A 3 small = [1 -P(U = 2 i ) -P(U < 2 i )] • A 3 large + P(U = 2 i )A 3 medium + P(U < 2 i )A 3 small = (0.74 • 2 i ) 3 -P(U = 2 i )[(0.74 • 2 i ) 3 + (0.26 • 2 i ) 3 ] -P(U < 2 i )((0.74 • 2 i ) 3 + (1.26 • 2 i ) 3 )≥ (2 i ) 3 0.74 3 -0.8(0.74 3 + 0.26 3 ) -0.8 × 0.001(1.26 3 + 0.74 3 ) ≥ 0.065(2 i ) 3 .where the third inequality holds by Eqs. ( 21) and (26). Combining this last bound with Eq. (31), we obtain:EQUATIONwhere λ > 0 is a tuning parameter (to be chosen later) and q(y; u) = dQu dQ (y) is the density of Q u with respect to Q at y ∈ R. It should be clear from the definitions that q 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 of the confidence set it will be useful to derive an equivalent expression for the loss L. For this, first note that the density q satisfies q(y; u) = exp(yu -ψ Q (u)). Plugging this into the definition of L, we getL(θ; D t , λ) = λ 2 ∥θ∥ 2 + t-1 i=1 (ψ(X ⊤ i θ) -Y i X ⊤ i θ) .As it is well known, ψ is a convex function of its argument (Theorem 1.13 of [Bro86] ) and hence θ → L(θ; D) is strictly convex provided that λ > 0.For the confidence set construction we will need the non-constant part of the gradient of L(•; D t ), which we denote by g t . We will also need the curvature of L(•; D t ), which we denote by H t . These areEQUATIONH t (θ) = ∇ 2 θ L(θ; D t ) = λI + t-1 i=1 μ(X ⊤ i θ)X i X ⊤ i .The minimizer θt = arg max θ∈R d L(θ; D, λ) has the property that ∂L(θ; D t , λ) ∂θθ= θt = 0 .This implies thatg t ( θt ) - t i=1 X i Y i = 0.With this, we can introduce our confidence set construction, which is based on the work of [Jan+24] .For δ ∈ (0, 1], we letEQUATIONwhere for M to be chosen later (in Lemma 28),EQUATIONEQUATIONHere, S 0 = sup{∥θ∥ : θ ∈ Θ}, as defined in the main body of the paper. In the algorithm we then choose C t to be C δ t ( θt ) with a fixed value of δ ∈ [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 ∩ t≥1 C δ t ( θt ) have coverage 1 -δ: Lemma 28. Let Assumptions 1 and 2 hold and choose M ≥ max(K/ log(2), 1/(c 1 -S 1 ), 1/(c 2 + S 2 )) in Eqs. (34) and (35), where Γ is any stretch function for (Q u ) u∈[S2,S1] and K = sup S2≤u≤S1 Γ(u). Then, for the confidence set defined in Eq. (33) and for all δ ∈ (0, 1],P(∀t ≥ 1, θ ⋆ ∈ C δ t ( θt )) ≥ 1 -δ.Note that Theorem 7 and Assumption 2 guarantees the existence of a stretch function Γ mentioned in the theorem.In the remainder of this section, we will fix Γ to one such stretch function.In general, here, one wants to use the smallest such stretch function (i.e., Γ = Γ Q ). When Γ Q is not available, in the lack of a better choice for Γ, the choice worked out in Theorem 7 can be used.Let E δ be the event that E δ = {θ ⋆ ∈ C δ t ( θt )} which by Lemma 28 holds with probability at least 1 -δ. For the next theorem, recall that S 0 = sup θ∈Θ ∥θ∥ and S 1 = sup U, S 2 = inf U.Theorem 29. Let δ ∈ (0, 1] and T a positive integer and consider a well-posed GLB model G = (X , Θ, Q) and assume that Assumptions 1 and 2 hold. Then, by setting C t = C δ t ( θt ), for any θ ⋆ ∈ Θ, with probability at least 1 -δ, the regret Regret(T ) of Algorithm 1 when it interacts with the GLB instance specified by θ ⋆ can be upper bounded by,Regret(T ) ≤ 8c γ T (δ) d μ(x ⊤ ⋆ θ ⋆ )(1 + L/λ) log 1 + LT dλ T + 8c 2 γ 2 T (δ)L 2 Kκ log(λ + T /d) + 32c 2 γ 2 T (δ) • Kd(1 + L/λ) log 1 + LT dλ ,where c = (1 + 2K(S 1 -S 2 )) andEQUATIONProof. We first consider the case that the base distribution has 0 variance, which implies that Q is a Dirac. As discussed beforehand, and as it is easy to see it, in this caseU Q = R, Q u = Q for any u ∈ 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) > 0. Since µ(•) = ψQ (•) is infinitely differentiable (Proposition 2), we can perform a second-order Taylor expansion on the regretRegret(T ) = T t=1 µ(x ⊤ ⋆ θ ⋆ ) -µ(X ⊤ t θ ⋆ ) = T t=1 μ(X ⊤ t θ ⋆ )(x ⋆ -X t ) ⊤ θ ⋆ R1(T ) + 1 2 T t=1 μ(ξ t )((x ⋆ -X t ) ⊤ θ ⋆ ) 2 R2(T ), where ξ t is between X ⊤ t θ ⋆ and x ⊤ ⋆ θ ⋆ for all t ∈ [T ]. On event E δ , by definition of X t , θ t (in Algorithm 1), it holds that x ⊤ ⋆ θ ⋆ ≤ X ⊤ t θ t . Observe that γ t (δ) (Eq. ( 35)) is increasing in t, we have that γ t (δ) ≤ γ T (δ) for all t ∈ [T ]. Then we can bound R 1 (T ) as followsR 1 (T ) = T t=1 μ(X ⊤ t θ ⋆ )(x ⋆ -X t ) ⊤ θ ⋆ ≤ T t=1 μ(X ⊤ t θ ⋆ )X ⊤ t (θ t -θ ⋆ ) ≤ T t=1 μ(X ⊤ t θ ⋆ )∥X t ∥ H -1 t (θ⋆) ∥θ t -θ ⋆ ∥ Ht(θ⋆)where the last inequality is due to Cauchy-Schwarz. Since θ t and θ ⋆ are all in the confidence set on E δ , we are able to bound ∥θ t -θ ⋆ ∥ Ht(θ⋆) by the following lemma that exploits the properties of confidence set as well as self-concordant functions. This lemma is a variation of proposition 4 of Abeille, Faury, and Calauzènes [AFC21] where they show the result for logistic function that is 1-self-concordant.Lemma 30 (C δ t ( θt ) has small ellipsoidal diameters). Under Assumptions 1 and 2, for all θ 1 , θ 2 ∈ C δ t ( θt ), it follows that∥θ 1 -θ 2 ∥ Ht(θ1) ∨ ∥θ 1 -θ 2 ∥ Ht(θ2) ≤ 2(1 + 2K • (S 1 -S 2 ))γ t (δ),where K is defined in Eq. (36).By Lemma 30, we can upper bound R 1 (T ) to beR 1 (T ) ≤ T t=1 μ(X ⊤ t θ ⋆ )∥X t ∥ H -1 t (θ⋆) • 2(1 + 2K(S 1 -S 2 ))γ T (δ).Denote A t = μ(X ⊤ t θ ⋆ )X t and we have that H t (θ ⋆ ) = t s=1 A t A ⊤ t + λI as well as ∥A t ∥ ≤ √ L ≤ L where the second inequality is because WLOG we assume L ≥ 1 in Assumption 2. We can bound R 1 (T ) in the terms of A t .R 1 (T ) ≤ 2(1 + 2K(S 1 -S 2 ))γ T (δ) T t=1 μ(X ⊤ t θ ⋆ )∥X t ∥ 2 H -1 t (θ⋆) μ(X ⊤ t θ ⋆ ) ≤ 2(1 + 2K(S 1 -S 2 ))γ T (δ) T t=1 μ(X ⊤ t θ ⋆ )∥X t ∥ 2 H -1 t (θ⋆) T t=1 μ(X ⊤ t θ ⋆ ) (Cauchy-Schwarz) = 2(1 + 2K(S 1 -S 2 ))γ T (δ) T t=1 ∥A t ∥ 2 H -1 t (θ⋆) T t=1 μ(X ⊤ t θ ⋆ ) ≤ 4(1 + 2K(S 1 -S 2 ))γ T (δ) d(1 + L/λ) log 1 + LT dλ T t=1 μ(X ⊤ t θ ⋆ )where in the last step we use elliptical potential lemma of Abbasi-Yadkori, Pál, and Szepesvári [APS11] , which, for easy of reference, we give in Lemma 38. We now start to bound R 2 (T ). For convenience, we throw away the factor of 1/2.R 2 (T ) ≤ T t=1 μ(ξ t )((x ⋆ -X t ) ⊤ θ ⋆ ) 2 ≤ T t=1 μ(ξ t )(X ⊤ t (θ t -θ ⋆ )) 2 (X ⊤ t θ t ≥ x ⊤ ⋆ θ ⋆ ≥ X ⊤ t θ ⋆ ) ≤ T t=1 μ(ξ t ) ∥X t ∥ 2 H -1 t (θ⋆) ∥θ t -θ ⋆ ∥ 2 Ht(θ⋆) ≤ 4(1 + 2K(S 1 -S 2 )) 2 γ T (δ) 2 T t=1 μ(ξ t ) ∥X t ∥ 2 H -1 t (θ⋆)where in the last inequality we use Lemma 30. By definition of self-concordant function, we have that μ(ξ t ) ≤ Γ(ξ t ) μ(ξ t ). Since ξ t is between x ⊤ ⋆ θ ⋆ and X ⊤ t θ ⋆ . Note that Γ defined in Theorem 7 is increasing on [0, c 1 ) and decreasing on (-c 2 , 0), which gives usΓ(ξ t ) ≤ Γ(X ⊤ t θ ⋆ ) ∨ Γ(x ⊤ ⋆ θ ⋆ ) ≤ K. Let V t = λI + t i=1 X i X ⊤ i . We hence have R 2 (T ) ≤ 4(1 + 2K(S 1 -S 2 )) 2 γ T (δ) 2 T t=1 K μ(ξ t ) ∥X t ∥ 2 H -1 t (θ⋆) ≤ 4(1 + 2K(S 1 -S 2 )) 2 γ T (δ) 2 KL T t=1 ∥X t ∥ 2 H -1 t (θ⋆) ( μ(•) ≤ L (Assumption 2)) ≤ 4(1 + 2K(S 1 -S 2 )) 2 γ T (δ) 2 KLκ • T t=1 ∥X t ∥ 2 V -1 t (H -1 t (θ ⋆ ) ⪯ κV -1 t ) ≤ 4(1 + 2K(S 1 -S 2 )) 2 γ T (δ) 2 KLκ • L log(λ + T /d).(Lemma 38) Putting the bound on R 1 (T ) and R 2 (T ) together, we have thatEQUATIONWe mimic the trick used in Janz, Liu, Ayoub, and Szepesvári [Jan+24] to bound T t=1 μ(X ⊤ t θ ⋆ ) 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] .Lemma 31 (Self-bounding property of self-concordance functions). Let V = [a, b], a closed, nonempty interval over the reals, f a real valued function defined over an interval of the reals that is twice continuously differentiable over V such that for some Γ :V → R + , | f (v)| ≤ Γ(v) ḟ (v)holds for all v ∈ V. Assume that A = sup v∈V Γ(v) < ∞. Furthermore, assume that either ḟ is identically zero over V, or ḟ is positive valued over V. For n a positive integer, let {a t } n t=1 ⊂ V. Then,n t=1 ḟ (a t ) ≤ n ḟ (b) + A n t=1 f (b) -f (a t ).We apply this lemma with f= µ, [a, b] = [S 2 , x ⊤ ⋆ θ ⋆ ] ⊂ [S 2 , S 1 ] and Γ restricted to [a, b].Then, all the conditions of the lemma are satisfied by our choice of Γ. Furthermore,A = sup v∈[S2,x ⊤ ⋆ θ⋆] Γ(v) ≤ K < +∞.Hence, all the conditions of the lemma are verified. Hence,EQUATIONPlug Eq. (38) into Eq. (37),Regret(T ) ≤ 4(1 + 2K(S 1 -S 2 ))γ T (δ) d μ(x ⊤ ⋆ θ ⋆ )(1 + L/λ) log 1 + LT dλ T + 4(1 + 2K(S 1 -S 2 )) 2 γ T (δ) 2 L 2 Kκ log(λ + T /d) + 4(1 + 2K(S 1 -S 2 ))γ T (δ) Kd(1 + L/λ) log 1 + LT dλ Regret(T ). Let A = 4(1 + 2K(S 1 -S 2 ))γ T (δ) Kd(1 + L/λ) log 1 + LT dλ , B = 4(1 + 2K(S 1 -S 2 ))γ T (δ) d μ(x ⊤ ⋆ θ ⋆ )(1 + L/λ) log 1 + LT dλ T + 4(1 + 2K(S 1 -S 2 )) 2 γ T (δ) 2 L 2 Kκ log(λ + T /d),we can write out the inequalityRegret(T ) ≤ A Regret(T ) + B.Solving it we have that Regret(T ) ≤ 2A 2 + 2B. Plugging in the definition of A and B back,Regret(T ) ≤ 8(1 + 2K(S 1 -S 2 ))γ T (δ) d μ(x ⊤ ⋆ θ ⋆ )(1 + L/λ) log 1 + LT dλ T + 8(1 + 2K(S 1 -S 2 )) 2 γ T (δ) 2 L 2 Kκ log(λ + T /d) + 32(1 + 2K(S 1 -S 2 )) 2 γ T (δ) 2 • Kd(1 + L/λ) log 1 + LT dλ .In 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. Specifically, Corollary 33 and Lemma 34 are used to show Lemma 30, one of the key lemmas we use in the proof of Theorem 29. Lemma 5 is used to justify the confidence set contains θ ⋆ with high probability (Lemma 28). Now, by Corollary 33, we have thatμ(ξ) ≤ μ(u) • e K|u-ξ| ≤ μ(u)e Ks ≤ 2 μ(u),where the final inequality follows when |s| ≤ log(2)/K. Putting things together, it follows that if |s| ≤ log(2)/K and s ∈ U• Q -{u} then ψ Qu (s) = ψ Q (u + s) -ψ Q (u) ≤ sµ(u) + s 2 μ(u) .For S ⊂ R, r ∈ R, let S ± r = {s ± r : s ∈ S}. Since u is an arbitrary point in U, the above conditions on s will be satisfied if |s| ≤ log(2)/K and s ∈ Z. = ∩ u∈U U • Q -u. Now, from U • Q = (a, b), we have Z = ∩ u∈U (a -u, b -u) = (sup u∈U a -u, inf u∈U b -u) = (a -inf U, b -sup U), 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 U• Q = (a, b), a -inf U < 0 < b -sup U,which is equivalent to that a < inf U and sup U < b, which is always satisfied when U is a strict subset of U • Q .We now turn to proving Lemma 28 which is concerned with showing that the confidence sets C δ t contain the true parameter θ ⋆ 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 2 of [Jan+24] ). Fix λ, M > 0. Let (X t ) t∈N + be a B d 2 -valued random sequence, (Y t ) t∈N + a real valued random sequence and (ν t ) t∈N be a nonnegative valued random sequence. Let F = (F t ) t∈N be a filtration such that(i) (X t ) t∈N + is F-predictable and (ii) (Y t ) t∈N + are F-adapted. Let ϵ t = Y t -E[Y t |F t-1] and assume that the following condition holds:E[exp(sϵ t )|F t-1 ] ≤ exp(s 2 ν t-1 ) for all |s| ≤ 1/M and t ∈ N + .Then, for Ht = t i=1 ν i-1 X i X ⊤ i + λI and S t = t i=1 ϵ i X i and δ > 0,P ∃t ∈ N + : ∥S t ∥ H-1 t ≥ √ λ 2M + 2M √ λ log det( Ht ) 1/2 λ -d/2 δ + 2M √ λ d log(2) ≤ δ.We now turn to proving Lemma 28. For the convenience of the reader, we start by recalling the definition of the confidence sets C δ t involved (cf. Eq. ( 33)). Recall that c 2 < S 2 ≤ x ⊤ θ ≤ S 1 < c 1 for x ∈ X and θ ∈ Θ. For δ ∈ (0, 1], we haveC δ,λ t ( θt ) = θ ∈ Θ : g t (θ) -g t ( θt ) H -1 t (θ) ≤ γ t (δ)whereγ t (δ) = λ T 1 2M + S 0 + 4M d √ λ T log e 1 + tL d ∨ 1/δ for all t ∈ [T ] , λ T = 1 ∨ 2dM S 0 log e 1 + T L d ∨ 1/δ ,and recall that S 0 = sup θ∈Θ ∥θ∥ or an upper bound on this quantity, and M is specified in the next result:Lemma 28. Let Assumptions 1 and 2 hold and choose M ≥ max(K/ log(2), 1/(c 1 -S 1 ), 1/(c 2 + S 2 )) in Eqs. (34) and (35), where Γ is any stretch function for (Q u ) u∈[S2,S1] and K = sup S2≤u≤S1 Γ(u). Then, for the confidence set defined in Eq. (33) and for all δ ∈ (0, 1],P(∀t ≥ 1, θ ⋆ ∈ C δ t ( θt )) ≥ 1 -δ.Proof. From definition it follows that θ ⋆ ∈ Θ. Now we prove that with probability at least 1 -δ, it holds that ∥g t (θ ⋆ ) -g t ( θt )∥ ≤ γ T (δ) for all t ≥ 1. The proof goes through by using Proposition 35 and we now match the conditions of Proposition 35. By Assumption 1, we have that(X t ) t∈N + is a B d 2 -valued random sequence. Let F t-1 = σ(X 1 , Y 1 , ..., X t-1 , Y t-1 , X t ) for t ≥ 1. Consider the filtration F = (F t ) t∈N . Then by definition, (X t ) t∈N + are F-predictable and (Y t ) t∈N + are F-adapted. Note that µ(X ⊤ i θ ⋆ ) = E[Y i |F i-1 ] for all i ∈ [n]. Let ε i = Y i -E[Y i |F i-1]. This gives (ε t ) t∈N + are also F-adapted and the following identity follows by definitiong t ( θt ) -g t (θ ⋆ ) = t i=1 ε i X i + λθ ⋆ = S t + λθ ⋆ ,where S t = t i=1 ε i X i . Let ν t-1 = μ(X ⊤ t θ ⋆ ). Now we would like to apply Lemma 5 to show that, for |s| ≤ M , it follows that E[exp(sε t )|F t-1 ] ≤ exp(s 2 ν t-1 ).( = exp(-sµ(X ⊤ t θ ⋆ )) R e sy Q X ⊤ t θ⋆ (dy) = exp(-sµ(X ⊤ t θ ⋆ ) + ψ Q X ⊤ t θ⋆ (s)) ≤ exp(s 2 μ(X ⊤ t θ ⋆ )), where the last inequality is because |s| ≤ M implies that s ∈ [-log 2/K, log 2/K] ∩ (U • Q -S 2 ) ∩ (U • Q -S 1 ) so Lemma 5 is applicable (it is applied with (Q u ) u∈[S2,S1] and Γ as chosen in the statement). Then, Eq. (42) follows by noting that ν t-1 = μ(X ⊤ t θ ⋆ ). Lastly as defined above, Ht corresponds to H t (θ ⋆ ). 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 λ > 0 where the probability density function can be written as f (x; λ) = I(x ≥ 0)λ exp(-λx).For each arm x ∈ X , the reward distribution is an exponential distribution with parameter λx ⊤ θ ⋆ , where we ensure that sup x∈X x ⊤ θ ⋆ < λ, as illustrated by Example 1. The number of arms |X | = 20 and X ⊆ R 2 , the max variance of the reward distributions among all arms is 0.25 and κ = sup x∈X 1/ μ(x ⊤ θ ⋆ ) ≈ 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 δ is 0.05.2. The regularizer is set to be 2.3. The confidence width γ t (δ, λ) is set according to Eq. ( 43).Here are the results of the experiments. In Fig. 1 we plot the average regret along with standard From the plot we can see that the regret attained seems to be sublinear. In Fig. 2 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 √ T which confirms our theoretical bound.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).This assumption does not hold for distributions with unbounded support such as: normal, Poisson, exponential, gamma and negative binomial distributions.Here, we follows the terminology used in 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 a much larger class of distributions[GK98]. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- The papers could benefit from experimental results, although it is very clear that this is a theoretical paper.

Minor details:
- Many references have "et al." instead of the full list of authors. This should be fixed.
questions: 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: limitations: The authors addressed potential limitations.
paper_summary: paper_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).
strength_weakness: strength_weakness: - 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.
- With the convex confidence set, it would be nice to see some numerical experiments, especially the exponential bandits.
- 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.
- 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.


**Comments**
- 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.
- For each theorem statement, if not already done so, I would like to see a direct (hyper)ref to the Appendix containing its proof
- Typo: "Lemma ??" in pg. 24

[1] https://proceedings.mlr.press/v130/abeille21a.html

[2] https://proceedings.mlr.press/v238/lee24d.html

[3] https://arxiv.org/abs/2404.06831
questions: 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]$?
-
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: 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.

Comments: comment: I thank the authors for the response. I have no further questions and am keeping my positive score.
Thanks for the detailed explanation. I understand the authors' concerns as well as n2uQ's disappointment. I agree that my understanding of fitness in this venue can be wrong. 

But, I still believe that this paper has a high barrier for most readers and the presentation should be improved for readers without background knowledge about GLB.

I think that the authors' rebuttals are valid. I will more carefully review your manuscript based on the rebuttal and make changes in my evaluation.
As a fellow reviewer, I wanted to express my disappointment in this review, which is unfair, if not adversarial, in its assessment of the work. Overall, I feel that the reviewer doesn't have sufficient expertise to review this paper and acknowledge the significance of the technical contributions, despite the confidence 5.

The notion of self-concordance property is essential in the analysis of generalized linear bandits, in which prior literature either focused on bounded GLMs or GLMs that are explicitly assumed to satisfy the self-concordance property. Thus, the criticisms of the "abrupt" introduction and unclear contributions are invalid. Although it would have been nice to include experiments from the beginning, the theoretical contributions deserve some merit. Those are not just "relaxation of some assumptions" but a significant relaxation in that the stretch factor needs not to be constant, and the other technical contributions on how to use such self-concordance to derive the *first* $d \sqrt{T/\kappa}$ regret bound over generic generalized linear bandits are also quite significant. I'm quite confused about what the reviewer means by "not well-suited to this venue," which is definitely not true. Moreover, saying that the single-param NEF is not comprehensive enough is just plain wrong.

The review misses the whole point and context of this paper's contributions, which doesn't add much to the fair assessment of their soundness and relevance.
Thank you for the responses, and apologies for getting back so late.

After reading through the responses to my and other reviewer's reviews, I'm satisfied with the authors' responses and intend to keep my score.
Dear Reviewer,

The author-reviewer discussion period is shortly coming to an end. We were hoping to get a confirmation from you that you've considered our rebuttal, and to let us know if you have any further questions.