Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces

In this paper, we introduce PSI-LinUCB, a scalable variant of LinUCB that enables efficient training, inference, and memory usage by representing the inverse regularized design matrix as a sum of a diagonal matrix and low-rank correction. We derive numerically stable rank-1 and batched updates that maintain the inverse without explicitly forming the matrix. To control memory growth, we employ a projector-splitting integrator for dynamical low-rank approximation, yielding an average per-step update cost and memory usage of O(dr) for approximation rank r. The inference complexity of the proposed algorithm is O(dr) per action evaluation. Experiments on recommender system datasets demonstrate the effectiveness of our algorithm.