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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 65 references that are in the map.
- First posted on arXiv 5 Oct 2026.

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

- [Algorithms for Non-Stationary Generalized Linear Bandits](https://mlsanity.com/paper/2003.10113/) (2020)
- [vCache: Verified Semantic Prompt Caching](https://mlsanity.com/paper/2502.03771/) (2025)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [A Linear Bandit for Seasonal Environments](https://mlsanity.com/paper/2004.13576/) (2020)
- [Linear Bandits on Ellipsoids: Minimax Optimal Algorithms](https://mlsanity.com/paper/2502.17175/) (2025)
- [ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving](https://mlsanity.com/paper/2604.00136/) (2026)
- [Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms](https://mlsanity.com/paper/2307.11655/) (2023)
- [Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets](https://mlsanity.com/paper/2609.00662/) (2026)

## Abstract (arXiv)

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 Obig(dRS(M+1)+σ d√ Tbig), 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 σ 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.