We thank the reviewer for valuable feedback and suggestions, and for recognizing our paper's technical soundness and contributions.

Number of clumsinesses, Typos, Organization issues

We apologize for the typographical errors and the organizational issues identified in the manuscript. We are committed to correcting these in the revised version, including re-organizing the appendices as suggested by the reviewer. We sincerely appreciate the reviewer's effort in pointing out these issues.

To ensure clarity, we address each typo as follows:

• Line 69. $\mathcal{B}^d(1)$ is the ball of radius 1 centered at the origin in R^d.
• Line 77. The mentioned properties of GLM are provided in [14], which we will add as reference
• Line 80. Of course. For Gaussian, $R_{\dot{\mu}} = 1$; for Poisson, $R_{\dot{\mu}} = e^S$; for Bernoulli, $R_{\dot{\mu}} = \frac{1}{4}$. Thank you for this suggestion, which would make our presentation clearer.
• Line 95. Yes. We will appropriately change the sentence.
• Line 129. Yes, it should be the likelihood ratio.
• Line. 583. We sincerely apologize for this mishap. Due to the pressing time, we forgot to replace this with rigorous proof. Below, we provide rigorous proof of this result, which will, of course, be reflected in the revision:

Let us denote $f(p) := p^{-1/2} \left( \mathbb{E}[{X}^p] \right)^{1/p}$ for $p \in \mathbb{N}$.

Then, using well-known properties of the Gamma function, we have that

$

f(2p) = \sigma 2^{\frac{2p-1}{4p}} (2p)^{\frac{1}{2p} - \frac{1}{2}} \left( (p-1)! \right)^{\frac{1}{2p}}
= \sigma \sqrt{ p^{-1} \left( \sqrt{2} p! \right)^{\frac{1}{p}} }

$

and

$

f(2p - 1) = \sigma 2^{\frac{2p - 2}{2(2p - 1)}} (2p - 1)^{\frac{1}{2p - 1} - \frac{1}{2}} \left( \sqrt{\pi} \frac{(2p - 3)!!}{2^{p - 1}} \right)^{\frac{1}{2p - 1}}
= \sigma (2p - 1)^{\frac{1}{2p - 1} - \frac{1}{2}} \left( \sqrt{\pi} (2p - 3)!! \right)^{\frac{1}{2p-1}},

$

where we define $(-1)!! := 1$.

Then, we have that

$

f(2p) \overset{(i)}{<} \sigma \sqrt{p^{-1} (\sqrt{2} p^p)^{\frac{1}{p}}}
= \sigma 2^{\frac{1}{4p}}
\leq \sigma 2^{\frac{1}{4}},

$

where $(i)$ follows from $p! < p^p$. We also have that

$

f(2p-1) \overset{(i)}{<} \sigma (2p - 1)^{\frac{1}{2p - 1} - \frac{1}{2}} \left( \sqrt{\pi} (2p - 1)^p \right)^{\frac{1}{2p-1}}
\overset{(ii)}{<} \sigma \left( \sqrt{\pi} (2p - 1)  \right)^{\frac{1}{2p-1}}
\overset{(iii)}{<} \sigma \sqrt{\pi},

$

where $(i)$ follows from $(2p - 3)!! < (2p - 1)^p$, $(ii)$ follows from $\frac{p}{2p - 1} > \frac{1}{2}$, and $(iii)$ follows from the observations that for $z \geq e$, $f(z) = (\sqrt{\pi} z)^{1/z}$ is decreasing, and $f(1) = \sqrt{\pi} > f(3) = (3 \sqrt{\pi})^{1/3}$. The first observation can be easily verified as follows: $\frac{d}{dz} \log f(z) = \sqrt{\pi} \frac{1 - \log z}{z^2} \leq 0, \quad \forall z \geq e.$

Finally, as $2^{1/4} < \sqrt{\pi}$, we have that $\sup_{p \in \mathbb{N}} f(p) \leq \sqrt{\pi} \sigma.$

How small can $\beta_t(\delta)$ be when we don’t require the confidence region to be time-uniform?

This is an interesting question, and thank you for bringing this up. First, we note that the mixture of martingale-type arguments (e.g., our PAC-Bayesian time-uniform guarantees) usually gives an anytime-valid guarantee for free.

If the reviewer is asking about the optimal $\beta_t(\delta)$ when the data $\mathcal{D}_t = \\{ (x_s, r_s) \\}\_{s \in [t]}$ can be adaptively collected for a given $t$, we don't have a definitive answer. This resembles the fixed-budget best-arm identification in bandits [15], which may be a good starting point for this direction.

When the data $\mathcal{D}_t$ is collected independently, the problem reduces to the fixed-design setup. For the linear case, one has the confidence region of the following form [Eqn. (20.2) of 16]: for any fixed $x \in \mathcal{B}^d(1)$,

$

\mathbb{P}\left( \langle x, \hat{\theta}_t - \theta_{\star} \rangle \leq \mathcal{O}\left( \lVert x \rVert_{V_t^{-1}} \sqrt{\log\frac{1}{\delta}} \right) \right) \geq 1 - \delta,

$

where $V_t = \sum_{s=1}^t x_s x_s^\top$ is the design matrix that we assume to be invertible for now.

For the logistic model, we have the following [Theorem 1, 17]:

$

\mathbb{P}\left( \langle x, \hat{\theta}_t - \theta_{\star} \rangle \leq \mathcal{O}\left( \lVert x \rVert_{H_t^{-1}} \sqrt{\log\frac{t_{eff}}{\delta}} \right) \right) \geq 1 - \delta,

$

where $t\_{eff}$ is the number of distinct vectors in $\\{x_s\\}\_{s \in [t]}$ and $H_t = \sum_{s=1}^t \dot{\mu}(\langle \widehat{\theta}_t, x \rangle) x_s x_s^\top$ is the Fisher information matrix that we assume to be invertible for now. In both cases, the confidence width is dimension-independent and asymptotically optimal with respect to the Cramér-Rao lower bound. Thus, for each fixed $t$, we indeed have a tighter $\beta_t(\delta)$.

We thank the reviewer’s valuable reviews and comments.

W1. “Numerically tightness” of CS

We intended "numerically tight" to mean numerically tighter than previously known and non-vacuous, a phrase often used in prior works on PAC-Bayes. We will clarify this sentence in the revised manuscript.

W2. “Cleverly”

We concur with the reviewer that the novelty of the approach should be left to the reader's judgment. Accordingly, we will remove this word.

W3. Open problem should be well-known that numerous other people should’ve tackled and fail

We start by pointing out that obtaining a tight (hopefully optimal) regret bound for generalized linear bandits, including logistic bandits, has been a long unresolved open problem in bandits, starting from the seminal work of Filippi et al. (2010) and tackled by numerous researchers. Although we cited Lee et al. (2024) [1] as the source of the open problem, this is to emphasize the dependency of $S$ that has been ignored for quite sometime before [1]. We will fix the references to the original reference and provide more context into the importance of our open problem.

We also highlight that Lee et al. (2024) [1] has been available on arXiv since October 2023. In our submission, we cited it using the BibTeX of its most recent conference version in 2024.

W4. Importance of ellipsoidal confidence set

Thank you for pointing this out. We would like to clarify that our original statement did not imply that the solution to the UCB $\max_{x \in X} \max_{\theta \in \mathcal{C}_t(\delta)} \mu(\langle x, \theta \rangle)$ has a closed solution. Upon further reflection, we acknowledge that the current wording may lead to misunderstanding, and we appreciate the reviewer for highlighting this. In Global Response #2, we elaborate on our intended meaning and how it can be corrected. We assure the reviewer that these corrections will be reflected in the revised manuscript. Additionally, as the reviewer mentioned, if the arm set is of combinatorial size, e.g., $2^d$, then we are indeed bound to incur at least $\Omega(2^d)$ computational cost. However, we demonstrate in Global Response #2 that if the CS is precisely an ellipsoid, the computational cost is $O(2^d)$, which is significantly more efficient than solving a convex optimization for each arm.

W5. Weak experiments

Please refer to Global Response #1.

Regarding Section 3.3

Thank you for your suggestion. We will make sure to explain the relationships more clearly or consider removing this section from the revision.

Typos

We apologize for the typographical errors and will commit to correcting them in the revision. We sincerely thank the reviewer for taking the time to point them out.

To ensure clarity, we address each typo as follows:

• Lines 312-313: The reviewer is correct. We will correct it to “randomized (exploration) algorithms.”
• Lines 95-97: We will revise this sentence appropriately.
• Line 129: It should indeed be the likelihood ratio. Theorem 3.2, second line: We will correct it to $\mathbb{P}(\exists t \geq 1 : \theta_\star \not\in \mathcal{E}_t(\delta)) \leq \delta$.
• Line 82: We will correct it to $\mathbb{P}(\exists t \geq 1 : \theta_\star \not\in \mathcal{C}_t(\delta)) \leq \delta$.
• Line 75: The rewards should indeed be in the filtration.

We hope that our response has properly addressed the reviewer’s concerns and that the reviewer would reconsider the score. Thank you.

I wanted to voice that I find this review to be an unfair, if not adversarial, assessment of the work. The review makes some comments about writing style until line ~110 and then something about the conclusion. This makes me wonder, if the reviewer read the full paper with sufficient care and give it enough thought.

It has become common fashion to emphasize the paper's contributions in the introduction. Compared to the standard, I would not say that this paper is heavily exaggerating the results that follows. However, I realize that qualitative descriptions of the results can through-off a reader, e.g. them getting mad over the usage of a simple adjective ("cleverly").

I think the paper indeed makes non-trivial contributions, and has a fresh approach (combining Ville's with the change of measure technique in the proof) that I have not seen in this immediate area of work. In their rebuttal, the authors also provide a benchmark including the most related work, even reporting the runtimes. The benchmark is still for a synthetic dataset, with small values of $S$, but already gives some insight into the average case performance of the algorithms (as the bounds are worst-case wrt the reward class).

I think the review focuses on form/presentation, and misses out on the content. I am not sure how useful or reliable is this type of review, to make a fair assessment of soundness and relevance of the contributions.

We thank the reviewer for several enlightening questions and suggestions that will certainly improve our paper.

W1. & Q3. Statistical issues with ellipsoidal relaxation

Indeed, the ellipsoidal CS introduces an additional factor of $S$, as it uses the self-concordance control (Lemma A.4). For logistic bandits, the blowup is only by a factor of $S$, as $R_s = 1$ for Bernoulli distribution. Among the ellipsoidal CSs available for linear and logistic bandits, our ellipsoidal CS’s width is theoretically the tightest, ignoring absolute constants. Indeed, we believe that our ellipsoidal CS-based UCB algorithm attains $\mathcal{O}(d \sqrt{ST / \kappa_\star(T)})$ regret, which is strictly better than many baselines' regret guarantees, e.g., ada-OFU-ECOLog. Also, the complexity of computing the Hessian $H_t = \sum_{s=1}^t \dot{\mu}(\langle x_s, \hat{\theta}_t \rangle) x_s x_s^\top$ is similar to that of the design matrix in linear bandits, making our ellipsoidal CS practical.

W2. & W3. Lacking experiments

Please refer to our Global Response #1, where we address many of the reviewer’s suggestions and concerns about the experiments. As measuring the number of flops for constrained nonlinear convex optimization was unclear, in SPDF, we report the algorithms' runtimes (sec), measured by Python’s time module.

Q0. Are we sacrificing something for $\log S$?

Yes, obtaining $\log S$ requires more computational power (e.g., norm-constrained MLE). Please refer to our above response to W1 & W3.

Q1. Batched vs. sequential estimator?

We apologize for the confusion. These terms distinguish between $\mathcal{L}_t(\hat{\theta}_t)$, which uses a single MLE to compute the loss at $t$, and $\mathcal{L}_t(\\{\hat{\theta}_s\\}\_{s=1}^t)$, which uses all the MLEs computed to far to compute the loss at $t$ as in weighted likelihood ratio testing [4]. We will clarify this in the revision.

Q2. Why constrained MLE?

If we stick to the uniform prior, then we are not aware of any way to allow the regularized MLE since then we cannot ensure that there is a sufficient prior probability mass around the regularized MLE (the regularized MLE can be far outside of the support of the uniform prior). Constrained MLE ensures that the estimator falls in the support of the uniform prior, so one can find a sufficient probability mass around it.

But then one may wonder why uniform prior? We made this choice since we found that the KL divergence between uniform prior and posterior has a closed form and that it provides us with much easier control of under-approximating the integral w.r.t. the posterior. Alternatively, one can consider, e.g., Gaussian prior, and attempt to make the regularized MLE work, but we found that terms are much harder to control. We have not done an exhaustive attempt on this, so we believe it is an interesting future direction!

Q4. & W1. Computational complexity of calculating the CS?

First, the radii in Theorem 3.1 and 3.2 can be explicitly computed using the Lipschitz constants for various GLMs provided in Table 1. Also, the complexity for computing the matrix norm w.r.t. the Hessian matrix $H_t = \sum_{s=1}^t \dot{\mu}(\langle x_s, \hat{\theta}_t \rangle) x_s x_s^\top$ isn’t too much, considering how its computation is composed of matrix-vector products. Please refer to our Global Response #2 for the computational issues in the UCB.

Q5. A clear kernelized extension?

No, extending to the RKHS setup seems non-trivial. The primary issue is that no translation-invariant Lebesgue measure exists in infinite-dimensional function space (e.g., RKHS), i.e., no uniform distribution and no concept of likelihood, among many counterintuitive issues. Indeed, the usual properties that hold in finite dimensions may fail in infinite dimensions (see, e.g., [13]), and one must be very careful when transferring the current PAC-Bayes proof to infinite dimensions. For instance, for the KL between two Gaussian measures to be well-defined, one measure must be absolutely continuous against another, which holds under certain nontrivial conditions on mean and covariance operators (Feldman–Hájek theorem). One could consider using the well-studied Gaussian Process prior/posteriors (as hinted at in our answer to Q2), but choosing the mean and kernel to obtain similar guarantees is non-trivial.

Q6. Is Thm 4.1 minimax optimal?

Somewhat yes. As elaborated in lines 250-272, the leading term of our regret bound for logistic bandits is indeed (locally) minimax optimal in $d, T, \kappa_\star(T)$ relative to the lower bound of [2]. Moreover, a closer look into their proof shows that their lower bound scales as $1 / S$, indicating a gap of $S$ between the lower and upper bounds. To the best of our knowledge, there isn’t any generic regret lower bound that holds simultaneously for all GLBs. We suspect a similar $d\sqrt{T / \kappa_\star(T)}$ lower bound would hold for GLBs. One could either carefully modify the proof of [2] for GLMs (e.g., their relative entropy decomposition lemma (Lemma 6) relies on the fact that the reward distribution is Bernoulli) or come up with something new. We leave this as future work.

Q7. Is Fig 1(c) ellipsoid?

No, our CS at each time $t$ is a level set of the negative log-likelihood loss $\mathcal{L}_t(\cdot)$, which isn’t precisely an ellipsoid. But, as the CS tightens, it more closely resembles an ellipsoid, as the second-order Taylor approximation (an ellipsoid as shown in our Theorem 3.2) gets tighter. We will elaborate on this in the revision.

Q8. Are you using theoretical $\beta_t(\delta)$ for experiments?

Yes, we use the precise theoretical $\beta_t(\delta)$ in all of our experiments, including additional ones in the supplementary pdf.

Thank you for your detailed review, for recognizing the significance of our technical contributions, and for providing valuable feedback.

W1. Writing and paper organization + Regret Analysis

Thank you for your suggestions. Indeed, Section 3.2 implicitly assumes that the reader is familiar with PAC-Bayesian analysis. Due to space constraints, we could not provide more details and instead referenced two standard sources [9,10]. In the revision, we will ensure Section 3.2 is easier to follow.

Additionally, as the reviewer noted, the proof sketch of the regret bound can be improved. We will address this in the revision. Allow us to elaborate on the main technical novelty of our regret analysis, which will be included in the revised version.

The existing proof relies on the original self-concordance lemma [11, Lemma 9], which allows the appearance of $\nabla^2 \mathcal{L}_t(\theta\_{*})$ (related to the matrix $H\_t(\\theta\_\*)$ in [11]). Consequently, it allows for one to use the elliptical potential lemma (Lemma B.1), with $x_s$ replaced by $\sqrt{\dot{\mu}(\langle \theta\_\star, x_s \rangle)} x_s$. However, as described in our proof sketch, the self-concordance lemma introduces an additional factor of $S$. To avoid this and at the same time to use our confidence sequence (Theorem 3.1), we utilize the Cauchy-Schwartz w.r.t. $\widetilde{G}_t(\widehat{\theta}_t, \nu_t) = \lambda \mathbf{I} + \frac{1}{g(\tau)} \sum\_{s=1}^{t-1} \tilde{\alpha}_s(\widehat{\theta}_t, \nu_t) x_s x_s^\top$ (see Eqn. (26) in Appendix B.1). $\widetilde{G}_t$ arises naturally when one performs second-order Taylor expansion of $\mathcal{L}_t(\cdot)$ around its minimum $\widehat{\theta}_t$; in particular the confidence set can be rewritten as a quadratic form involving $\widetilde{G}_t$ (Lemma B.6). However, now note that the elliptical arguments are no longer applicable to $\sum_t \lVert x_t \rVert\_{\tilde{G}_t(\hat{\theta}_t, \nu_t)^{-1}}^2$. Our main technical novelty is designating the "worst-case $\theta$" over all future confidence sets from time $s$ to $T$ (see $\bar{\theta}_s$ in Eqn. (24) of Appendix B.1). With this, we can follow an alternate chain of inequalities to obtain $\sum_t \lVert x_t \rVert\_{\bar{H}_t^{-1}}^2$, where $\bar{H}_t = 2 g(\tau) \lambda \mathbf{I} + \sum\_{s=1}^{t-1} \dot{\mu}(\langle \bar{\theta}_s, x_s \rangle) x_s x_s^\top$ (see Eqn. (26) in Appendix B.1). Then the elliptical potential lemma is applicable with $x_s$ replaced by $\sqrt{\dot{\mu}(\langle \bar{\theta}_s, x_s \rangle)} x_s$, concluding our proof. Note that there are other details we are omitting here, but they are relatively minor manipulation of adding and subtracting the desired quantities to get to the place where we can apply the elliptical potential lemma as we stated above.

Q1. Why $P_t$ is a valid posterior?

The terms "prior" and "posterior" are somewhat misleading in PAC-Bayes, as they need not strictly be the Bayesian prior and posterior. Instead, "prior" should be interpreted as any data-free distribution. and "posterior" as any data- and prior-dependent distribution, providing more flexibility in choosing them. The reviewer is correct that one should choose the "prior" and "posterior" such that their KL divergence is not too large. Simultaneously, in our context, the posterior should be chosen so that the Lipschitz inequality is not too loose (see line 164). We refer the reviewer to the excellent introduction to PAC-Bayes by P. Alquier [9] and a survey on PAC-Bayes time-uniform bounds by Chugg et al. [10]. There is no need to apologize; we also found it challenging to adapt to PAC-Bayes terminologies while writing the paper.

Q2. Does the learner require the knowledge of $R_\mu$?

Thank you for highlighting this point. Indeed, the learner needs to know $R_{\dot{\mu}}$ or its upper bound. This requirement arises because the bandit algorithm relies on our new confidence sequence (Theorem 3.1), which in turn depends on the Lipschitz constant $L_t$ of the GLM negative log-likelihood, which depends on $R_{\dot{\mu}}$; see Table 1 and Appendix A of our submission. We will clarify this in the revision.

Q3. Elaborating on the connection of Theorem 3 of Foster et al. (2018) with our Section 3.2

To recall the proof of Theorem 3 of [12], they first consider a distribution $P_t(\cdot)$ over the parameter $W$ (see their Algorithm 1) and use $\eta$-mixability of the logistic loss to obtain an inequality involving the negative-log-integral term $\int_{\mathcal{W}} \exp\left( -\eta \sum_t \ell(Wx_t, y_t) \right) dW$. They define $S = \theta W^\star + (1 - \theta) \mathcal{W} \subseteq \mathcal{W}$, where $W^\star$ is the ground-truth optimal parameter and $\theta \in [0, 1)$ is to be determined later. The proof concludes by chaining the inequality $\int_{\mathcal{W}} \geq \int_S$ with the Lipschitzness of the logistic loss and expanding the integral.

Our Section 3.2 follows a similar approach with some key differences. While their negative-log-integral also arises in our scenario, we adopt a more compact, streamlined PAC-Bayes approach. In our case, a similar quantity $\mathbb{E}\_{\theta \sim \mathbb{Q}}[\exp(-\mathcal{L}_t(\theta))]$ arises from our Donsker-Varadhan representation (Lemma 3.2), where $\mathbb{Q}$ is our prior. We then apply Ville’s inequality to obtain the time-uniform PAC-Bayes bound (Lemma 3.3), and our choices of prior/posterior resemble their choice of $S$. Our Lipschitzness arguments also resemble their $\ell\_{\infty}$ Lipschitzness argument (see their pg. 17 in the PMLR proceeding version).

We will provide a more detailed explanation of the proof in the revision. Thank you for bringing this to our attention.