Sketch-Aware Generalized Linear Bandits: Efficient One-Pass Updates via Frequent Directions

The nonlinear link function in generalized linear bandits (GLBs) makes it challenging to achieve statistical and computational efficiency simultaneously. Recent online mirror descent methods enable statistically efficient one-pass learning, but their guarantees rely on dense curvature geometry, incurring $O(d^2)$ memory and $O(d^3)$ computation per round in the feature dimension $d$. We propose a sketch-aware GLBs algorithm based on Frequent Directions, a deterministic sketch that incrementally compresses the adaptively revealed curvature geometry. A single sketch supports both estimator updates and optimistic action selection, reducing memory to $O(md)$ and, for small candidate action sets, amortized per-round computation to $O(md)$ for sketch size $m<d$. We establish a rigorous regret guarantee that quantifies the efficiency–utility trade-off: the approximation penalty is controlled by the discarded spectral tail, while the regret retains the statistical efficiency of its full-matrix counterpart under favorable spectral structure. Across synthetic and real-world benchmarks, our approach closely matches the regret of full-matrix methods while substantially reducing runtime and peak memory.