Generalized Linear Bandits (GLBs), a natural extension of the stochastic linear bandits, has been popular and successful in recent years.

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