arXiv preprint ·
Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory
- Published
- Source
- arXiv preprint, posted before peer review
- Published in
- arXiv
- DOI
- 10.48550/arxiv.2610.05659
- Original
- Read it at arXiv
- Cited by
- 0 works, as OpenAlex counts them
- Topics
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 O\big(dRS(M+1)+σd\sqrt T\big)$, 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Visual Grounding Safety in Vision-Language Models
SkillFormer: Skill-Decomposed Adaptation for Audio Language Models
Spacecraft Rendezvous Trajectory Generation with Modular Constraints via Diffusion Model Composition
Preserving Unstable Modes Through Inverse Dynamics in JEPA World Models
When Does a Diffusion Model Decide What to Draw ?
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.