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 O(dRS(M+1)+σdT), 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.
Figures & tables
Comparisons for LBM
Algorithm
Regret
Jaksch et al. (2010)
UCRL2
O(RSMnM+1/2T+σn(M+1)/2T)
Clerici et al. (2023)
OFUL-memory
O(R(S+σ)dMT3/4)
Ann et al. (2026)
OFUL-memory (improved)
O(RSdMT+σmax{1,S}dmax{d,R2}T)
Ours (Upper Bound)
RSM-LinUCB Theorem 4.3
O(dRSM+σdT)
Ours (Lower Bound)
Theorem 4.5
Ω(dRSM+σdT)
Comparisons for GLBM
Algorithm
Regret
Table 1 : Comparison of regret bounds for the basic LBM setting and the extended GLBM setting.
Figure 1 : Cumulative pseudo-regret for synthetic (A–D), KV-cache (E–F), and semantic-cache (G–H). Shading denotes one standard deviation and some baseline curves exceed the displayed range.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 2 : Cumulative pseudo-regret for additional synthetic experiments with additive memory. Shading denotes one sample standard deviation. Some baseline curves exceed the displayed range.
We study an endogenous nonstationary stochastic bandit problem with latent linear dynamics, where actions affect both immediate rewards and the future evolution of an unobserved latent state. Rewards are bilinear in the current action and latent state, inducing history-dependent rewards and a nontrivial long-horizon planning problem. The existing explore-then-commit approach achieves O~(T2/3) regret by uniformly exploring to estimate the latent dynamics and then committing to an optimized open-loop action sequence. We show that this rate can be improved via adaptive block-level optimism. Our key step is a cyclic approximation: under stable dynamics, the infinite-memory reward process can be truncated, and the open-loop benchmark can be approximated by optimizing a finite-memory block-level proxy. Building on this reduction, we propose a UCB-based block algorithm that maintains confidence sets for the truncated dynamics parameters and selects blocks optimistically. We prove a regret bound of order O~(T), significantly improving over the previous O~(T2/3) guarantee for the same model. To the best of our knowledge, this is the first O~(T) regret guarantee for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark.
This paper considers stochastic linear contextual bandits (SLCB) with bounded reward noise. Existing works typically assume sub-Gaussian reward noise and bounded expected rewards, under which the optimal regret bound scales as O~(T) in terms of horizon T. However, in many applications, realized/observed rewards are also naturally bounded, implying bounded reward noise. Bounded noise is more informative than the sub-Gaussian condition but has not been leveraged explicitly in the SLCB literature. In this paper, we propose a novel algorithm SME-OFU by utilizing an uncertainty quantification method called set-membership estimation (SME) and applying the principle of optimism in the face of uncertainty (OFU). Our algorithm enjoys an improved regret bound O(logT). Notice that this does not contradict the existing optimal bound O~(T) for sub-Gaussian noise because bounded noise is a stronger condition. Finally, simulations show empirical improvements of SME-OFU over a benchmark algorithm designed for sub-Gaussian noise when the reward noise is bounded.
Haonan Xu, Yingying Li
The Grainger College of Engineering University of Illinois Urbana-Champaign Champaign, IL, 61801
Motivated by the recency effect in online learning, we study algorithms for single-pass sliding-window streaming multi-armed bandits (MABs) in this paper. In this setting, we are given n arms with unknown sub-Gaussian reward distributions and a parameter W. The arms arrive in a single-pass stream, and only the most recent W arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.
Vladimir Braverman, Chen Wang, Liudeng Wang +1
Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University