Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

arXiv:2610.05659v1 Announce Type: new Abstract: We study linear bandits with memory, where past actions induce endogenous nonstationarity through an arbitrary known, bounded matrix-valued memory map. To trade off exploration and exploitation while accounting for the memory dynamics, we develop RSM-LinUCB, a Bellman-centric algorithm that learns as in linear bandits and plans as in reinforcement learning. This design admits a novel regret decomposition which separates the memory-induced error from the cumulative reward estimation error along the learner's trajectory. We prove a high-probability regret bound of widetilde Oig(dRS(M+1)+sigma dsqrt Tig), where T is the learning horizon, d is the parameter dimension, M is the memory length, R and S bound the memory-map operator norm and reward-parameter norm, respectively, and sigma is the sub-Gaussian noise scale. Our results reveal that the multiplicative memory-horizon coupling in prior bounds is not intrinsic: memory only contributes an additive cost, up to logarithmic factors. We also prove a matching minimax lower bound, establishing near-optimality. We further extend the algorithm to generalized linear rewards, preserving this separation with near-optimal memory and leading statistical dependence. Our algorithms outperform the baselines in numerical experiments on synthetic instances and semi-synthetic KV- and semantic-cache tasks.

Related

• Generalized Linear Bandits with Memory
• Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
• Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

Source: arXiv cs.LG | 2026-10-06