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

arXiv: https://arxiv.org/abs/2510.19349 · HTML: https://mlsanity.com/paper/2510.19349/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 22 Oct 2025.

## Builds on (most cited first, 12 of 12)

- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Offline Reinforcement Learning as Anti-Exploration](https://mlsanity.com/paper/2106.06431/) (2021)
- [Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward](https://mlsanity.com/paper/2206.06426/) (2022)
- [Efficient Linear Bandits through Matrix Sketching](https://mlsanity.com/paper/1809.11033/) (2018)
- [Online Matching: A Real-time Bandit System for Large-scale Recommendations](https://mlsanity.com/paper/2307.15893/) (2023)
- [Dynamic Global Sensitivity for Differentially Private Contextual Bandits](https://mlsanity.com/paper/2208.14555/) (2022)
- [Linear Contextual Bandits with Hybrid Payoff: Revisited](https://mlsanity.com/paper/2406.10131/) (2024)
- [Dynamic Modeling of User Preferences for Stable Recommendations](https://mlsanity.com/paper/2104.05047/) (2021)
- [Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics](https://mlsanity.com/paper/2203.01170/) (2022)
- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Efficient Implementation of LinearUCB through Algorithmic Improvements and Vector Computing Acceleration for Embedded Learning Systems](https://mlsanity.com/paper/2501.13139/) (2025)
- [Comparative Performance of Collaborative Bandit Algorithms: Effect of Sparsity and Exploration Intensity](https://mlsanity.com/paper/2410.12086/) (2024)

## Built on by (most cited first, 2 of 2)

- [Efficient Hypergradient Descent for Inverse Reinforcement Learning](https://mlsanity.com/paper/2608.11052/) (2026)
- [Accelerating Linear Bandits with Persistent Candidate Sets](https://mlsanity.com/paper/2610.13407/) (2026)

## Abstract (arXiv)

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.