Generalized Linear Bandits with Limited Adaptivity

We thank the reviewer for the feedback. We address the comments and questions below:

Regarding Weakness 1: Prior knowledge of $\kappa$.
We note that [7], in fact, assumes the knowledge of an upper bound on $\kappa$ in Procedure 1 for the non-contextual problem and while calculating $**V**^\mathcal{H}_s$ matrix for the contextual setting. We work under the constraint of limited adaptivity, and our algorithms use the value of $\kappa$ during the warmup round of B-GLinCB and for the first switching criteria in RS-GLinCB. We believe a $\kappa$-dependent warmup round is especially necessary for the batch algorithm.
As mentioned in response (1a) for Review wYhM, access to an upper bound on $\kappa$ suffices. In particular, as is standard in bandit literature (specifically, linear and generalized linear bandits), one can assume access to an upper bound on $\theta*$. Such an upper bound directly translates into the required upper bound for $\kappa$.

We thank the reviewer for pointing us to the relevant work of Periviar & Goyal, which we will include in the final version of the paper.

Regarding Weakness 2: Dependence on context dimension $d$ in computational complexity.
A detailed discussion on computational complexity is provided in Appendix D (lines 675-692).
Our results hold for GLMs, in general. Here, for any class of reward functions (e.g., logistic rewards) for which the specified convex optimization problem can be solved efficiently, we obtain a polynomial dependence on $d$.

Regarding Question 1.
Our novel instantiation with respect to self concordance is detailed in Remark 1.3 (Lines 93-98).
Our overarching contribution is the development of GLM bandit algorithms with a key focus on limited adaptivity. This required new algorithmic techniques (e.g., the $\kappa$ dependent exploration phase). To complement the algorithms’ design, the analysis required new ways to adapt the self-concordance property of the reward distribution (e.g. Lemma A.5, A.7). Further, new technical ideas were required both on the technical (e.g., Lemmas A.16 A.17) and analytic fronts.

Regarding Question 2: "In the experiments, it appears that ECOLog in [7] is a sub-algorithm for reward parameter estimation".
We have discussed the superior empirical performance of RS-GLinCB in detail in Appendix D (lines 693-715).
There seems to be a factual oversight here: we do not use ECOLog as a sub-algorithm. In fact, ECOLog and our algorithms solve notably different optimization problems for estimating $\theta^*$.

In particular, ECOLog [7] estimates $\theta^*$ by optimizing a second order approximation of the true log-loss while we optimize the true log-loss; however, we do it less frequently. That is, RG-GLinCB solves a ‘larger’ convex optimization problem but less frequently. This results in a smaller overhead at the implementation level. By contrast, ECOLog solves a smaller optimization problem but does so every round. Moreover, ECOLog solves additional optimization problems every round for the adaptive warmup criteria (for estimating parameter ${\theta}_t^0$, ${\theta}_t^1$ and $\bar{\theta}_t$ in Algorithm 2). We, on the other hand, have a simpler warmup criteria (see Switching Criteria 1) that only relies on the arm geometry and does not require solving an optimization problem.

Regarding Question 3. Space permitting, we will extend the experiments to highlight the dependence of the execution times on $d$.

Regarding Question 4: Different values of $S$ for logistic and probit rewards.
We observe that the empirical performance of RS-GLinCB is consistently better in terms of both regret and computational performance compared to the previous best logistic and other GLM bandit algorithms. The choice of exact parameter value $S, \kappa$ etc., is arbitrary. We will include a comparison with different values of $S$ in the updated version.

We thank the reviewer for pointing out the minor typos and will fix them.

We thank the reviewer for the detailed and insightful review.

Regarding Weakness 1: Numerical comparisons with DDRTS-GLB and EVILL.
This is a useful suggestion. We will implement the additional empirical comparisons mentioned in the review.
On the theoretical front, it is, however, relevant to note that DDRTS-GLB is an O(T^2) computation algorithm with non-optimal regret ($\kappa$-dependence). EVILL is not comparable because that work deals with fixed arm sets, not contextual arms.

Regarding Weakness 2: Regarding arm-geometry-adaptive term.
Our analysis is not tuned to the arm-geometry dependent $R_-(X)$ term as found in [2] and [17]. This is primarily because our algorithms require a warm-up (implicitly in RS-GLinUCB and explicitly in B-GLinUCB), during which there is no control over the regret, even in the analysis. This conforms with existing literature, for example, [7], where the second-order term is not able to accommodate the arm-geometry dependent $R_-(X)$ term. As future work, it will be interesting to investigate algorithms that are efficient while being able to accommodate arm-geometry dependent regret for GL Bandits.
We appreciate this point and will highlight it in the updated version.

Regarding Weakness 3: Warm-up in RS-GLinCB.
The warm-up in RS-GLinCB is implicit and arm-geometry adaptive. The rounds in which warm-up occurs (i.e., when Switching Criterion I is triggered) are deterministic, based on the sequence of contexts $\\{ X_t \\}_{t \geq 1}$. This leads to warm-up only in certain rounds based on the geometry of the contexts, which is very different from warm-up in [7], where warm-up is decided based on the stochasticity of rewards as well. Therefore, in our experiments, we observe that after a few initial rounds, the regret is nearly constant, while other algorithms display a growing nature. For the logistic case, among the efficient algorithms available, RS-GLinUCB’s superiority is clearly established.

Regarding Weakness 4: Prior works.
Thank you for pointing out the relevant work of Mason et al. 2018. We will include it in our final version.

Regarding Weakness 5 and Question 1: Convex relaxation and dependence on S.
The reviewer is right that a convex relaxation leads to poly(S)-dependence in the first-order regret term. It would be interesting to design algorithms that require only convex optimizations but are still poly(S)-free. Thank you for the suggestion regarding non-convex optimization for poly(S)-free regret. We will clarify this in the introduction of our final version.

Regarding Question 2: Unbounded self-concordant GLMs.
Indeed, it does seem that our analysis extends to unbounded, self-concordant GLMs as well. However, we expect to incur additional log factors ($\log{T}$) in the regret. Taking Gaussian rewards as an example, the confidence interval would remain unchanged. We use the upper bound on the reward ($R$) in several places during the analysis (eg., in Lemma A.5) or in the algorithm (while defining $\beta(x)$) – similar arguments can be made for Gaussian rewards as well. The analysis for Gaussian rewards follows from the fact that Gaussian random variables remain bounded with high probability, allowing for extensions of our analysis. While such extensions are interesting, the current work focuses on the GLM model proposed in [8] and addresses the challenges in the limited adaptivity setting.

Regarding Question 3: Regarding l2-penalized MLE.
We have intentionally separated the convex optimization part and the (non-convex) projection step. This separation ensures that certain properties can be obtained before and after the projection; see, e.g., equation (26), which would not hold if we included the projection into the considered convex optimization problem. Moreover, it is not clear how the non-convex optimization projection can be included as a constraint in the log-loss optimization, while ensuring that the desired properties hold. Appendix E provides additional details in this direction.

Regarding Question 4: Geometry-dependent norm for warm-up.
We thank the reviewer for this helpful suggestion. We will include this in the updated version of the paper. Indeed, while the worst-case regret guarantee remains unchanged, we can use the geometry-dependent norm during warmup. Also, the algorithms analysis remains essentially the same.

Regarding Question 5: Ellipsoidal projection.
The reason why restricting optimization (6) to the ellipsoid around $\theta_o$ leads to tighter regret is because for the Non-”Switching Criterion I” rounds, it is guaranteed that $\lVert x \rVert_{V^{-1}} \leq O(1/\sqrt{\kappa})$. Hence $\langle x, \theta^* - \theta_o \rangle \leq ||x||_{V^{-1}} || \theta^* - \theta_o ||_V \leq O(1/\sqrt{\kappa}) \gamma \sqrt{\kappa}$. Therefore, the main idea is in the design of the Switching Criterion I and not just in the ellipsoidal projection. Whether one can combine this Switching Criterion with existing algorithms and obtain better guarantees is an interesting direction worth exploring.

Regarding Question 6: Best arm identification.
This is an interesting question that complements the paper’s goals. It is, however, worth noting that the current warm-up conditions are designed to address changing contexts. Applying them to static arm sets may be suboptimal. For static arm sets, one can simply allocate initial rounds for warmup, as in [7]. The switching criteria-based warmup is needed in the current work because we are dealing with adversarial contexts. Overall, it remains unclear as to what one would gain by using the criteria for static arm sets.

Note: All reference numbers are same as in the submitted paper.

We thank the reviewer for the feedback. We address the comments and questions below:

Regarding Weakness 1.
(1a) Unknown $\kappa$.
It is relevant to note that an upper bound on $\kappa$ suffices for the mentioned use cases. $\kappa$ is an instance-dependent parameter that captures the non-linearity and quantifies the hardness of the GLM instance. There is no cyclic dependency here between estimating $\theta^*$ and $\kappa$. In particular, it is standard in bandit literature (specifically, linear and generalized linear bandits) to assume an upper bound on $\theta^*$. Such an upper bound directly translates into an applicable upper bound for \kappa; see discussion below.

(1b) Dependence of $\kappa$ on $\theta^*$.
We note that the inclusion of $\theta^*$ in the definition of $\kappa$, $\left( \kappa = \max_{x \in \cup_{t=1}^T {\cal X}t} \frac{1}{\dot{\mu} ( \langle x, \theta^* \rangle )} \right)$ is beneficial. Prior works, such as [1],[2] use the following definition $\kappa = \max_{\lVert \theta \rVert \leq S } \max_{x \in \cup_{t=1}^T {\cal X}t} \frac{1}{\dot{\mu} (\langle x, \theta \rangle)}$ which also appears in their regret expression. Our definition is much tighter, leading to potentially smaller regret.

Regarding Weakness 2.
Here, it is best to not conflate $\kappa$ and $T$. $\kappa$ is an instance dependent parameter, which is potentially large, but fixed for the instance. The number of rounds, $T$, on the other hand, is a growing quantity.

Regarding the definition of $\beta(x) and minor comments.
Yes, the understanding is correct. We will move this definition next to the first expression in the final version.
Thank you for pointing out the minor typos. We will fix these in the updated version of the paper.

[1] Filippi, Sarah, et al. "Parametric bandits: The generalized linear case." Advances in neural information processing systems 23 (2010).
[2] Faury, Louis, et al. "Jointly efficient and optimal algorithms for logistic bandits." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

Dear Authors,

Thank you for your response, in which the following points have been resolved:

• (1) In the algorithm design, the access to an upper bound is sufficient.
• (2) Other questions such as the definition of $\kappa$ and its difference from prior work.
• (3) The necessary assumptions in the paper are standard in the field of GLMs.

I found that the analysis in this paper is very well-developed, particularly the self-concordance of bounded GLMs. Therefore, I have changed my score to Accept.