Scalable Generalized Linear Bandits: Online Computation and Hashing
Generalized Linear Bandits (GLBs), a natural extension of the stochastic linear bandits, has been popular and successful in recent years. However, existing GLBs scale poorly with the number of rounds and the number of arms, limiting their utility in practice. This paper proposes new, scalable solutions to the GLB problem in two respects. First, unlike existing GLBs, whose per-time-step space and time complexity grow at least linearly with time t, we propose a new algorithm that performs online computations to enjoy a constant space and time complexity. At its heart is a novel Generalized Linear extension of the Online-to-confidence-set Conversion (GLOC method) that takes any online learning algorithm and turns it into a GLB algorithm. As a special case, we apply GLOC to the online Newton step algorithm, which results in a low-regret GLB algorithm with much lower time and memory complexity than prior work. Second, for the case where the number N of arms is very large, we propose new algorithms in which each next arm is selected via an inner product search. Such methods can be implemented via hashing algorithms (i.e., "hash-amenable") and result in a time complexity sublinear in N . While a Thompson sampling extension of GLOC is hash-amenable, its regret bound for d-dimensional arm sets scales with d 3/2 , whereas GLOC's regret bound scales with d. Towards closing this gap, we propose a new hashamenable algorithm whose regret bound scales with d 5/4 . Finally, we propose a fast approximate hash-key computation (inner product) with a better accuracy than the state-of-the-art, which can be of independent interest. We conclude the paper with preliminary experimental results confirming the merits of our methods.
The paper identifies two problems with existing Generalized Linear Model Bandit algorithms: their per-step computational complexity is linear in t (time-steps) and N (number of arms). The first problem is solved by the proposed GLOC algorithm (first that achieves constant-in-t runtime and O(d T^½ polylog(T) ) regret) and the second by a faster approximate variant (QGLOC) based on hashing. Minor contributions are a (claimed non-trivial) generalization of linear online-to-confidence bounds to GLM, an exploration-exploitation tradeoff parameter for QGLOC that finally justifies a common heuristic used by practitioners and a novel simpler hashing method for computing QGLOC solutions.
I think the paper is interesting and proposes a novel idea, but the presentation is sometimes confused and makes it hard to evaluate the impact of the contribution w.r.t. the existing literature.
the authors claim that all existing GLMB algorithms have a per-step complexity of t. This is clearly not the case in the linear setting when \mu is the identity, and closed forms for \hat{theta}_t allow the solution to be computed incrementally. This cannot be done in general in the GLM where \hat{\theta}_t is the solution of a convex optimization problem that requires O(t) time to be created and solved. Indeed, GLOC itself uses ONS to estimate \theta, and then obtain a closed form solution for \hat{\theta}, sidestepping the O(t) convex problem. The authors should improve the presentation and comparison with existing methods, highlighting when and where this dependence on t comes from and why other methods (e.g., why hot restarting the convex solver with \hat{\theta}_{t-1}) cannot provide the same guarantees, or other examples in which closed forms can be computed.
The authors should expand the discussion on line 208 to justify the non-triviality: what original technical results were necessary to extend Abbasi-Yadkori [2] to GLMs?
While the road to solving the O(t) problem is somewhat clear, the approach to reduce the O(N) complexity is not well justified. In particular (as i understood):
GLOC-TS is hash-amenable but has d^3/2 regret (when solved exactly)
QGLOC is hash-amenable and has d^5/4 regret, but only when solved exactly
GLOC-TS has no know regret bound when solved inexactly (using hashing)
QGLOC has a fixed-budget regret guarantee (presented only in the appendix, d^5/4 or d^3/2?) that holds when solved inexactly (using hashing), but reintroduces a O(t) space complexity (no O(t) time complexity?)
This raises a number of questions: does GLOC-TS have a regret bound when solved inexactly? Does any of these algorithms (GLOC, QGLOC, GLOC-TS) guarantee O(d^{1,5/4,3/2}\sqrt{T}) regret while using sublinear space/time per step BOTH in t and N at the same time?
The presentation should also be improved (e.g., L1-sampling requires choosing m, but QGLOC's theorem makes no reference to how to choose m)
The experiments report regret vs. t (time), and I take t here is the number of iterations of the algorithm. In this metric, UCB-GLM (as expected) outperforms the proposed method. It is important to report metrics (runtime) that were the reason for the introduction of GLOC, namely per-step time and space complexity, as t and N change.
Minor things:
L230 "certain form" is a vague term
L119 S must be known in advance, it is very hard to estimate, and has a linear impact on the regret. How hard it is to modify the algorithm to adapt to unknown S?
L109+L127 The loss fed to the online learner is \ell(x,y) = -yz +m(z) and m(z) is \kappa strongly convex under Ass. 1. For strongly convex functions, ONS is not necessary and simple gradient descent achieves logarithmic regret. Under appropriate conditions on \kappa and y, the problem might become simpler.
L125 Ass. 1 is common in the literature, but no intuition for a value of \kappa is provided. Since the regret scales linearly with \kappa, it would be useful to show simple examples of known \kappa e.g. in the probit model and 0/1 rewards used in the experiments. It would also be useful to show that it does not satisfy the previous remark.
L44 3 is not included in the "existing algorithm". Typo, or TS does not suffer from both scalability issues?
L158 S should be an input of Alg. 1 as well as Alg. 2
AFTER REBUTTAL
	I have read the author rebuttal, and I confirm my accept. I believe the paper is interesting, but needs to make a significant effort to clarify the message on what it does and what it does not achieve.