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

arXiv:2610.05659 · cs.LG · Submitted 2026-10-05 · Read on arXiv

cs.LG

Submitted: 2026-10-05

Updated: 2026-10-05

Project page: https://kvcache-ai.github.io/Mooncake/design/mooncake-store.html

Terminology

• Regret — 1× in this paper · explained in 3 episodes

Sources

• Linear Bandits with Memory: from Rotting to Rising
• A Linear Bandit for Seasonal Environments
• Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms
• Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets
• Algorithms for Non-Stationary Generalized Linear Bandits
• vCache: Verified Semantic Prompt Caching
• ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving
• Linear Bandits on Ellipsoids: Minimax Optimal Algorithms

Related papers

• Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
• AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
• Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
• Convergence issues in Relational Concept Analysis based on AOC-posets
• Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
• Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks