Block Optimism for Nonstationary Bandits with Latent Linear Dynamics

Abstract

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 $\tilde{O}(T^{2/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 $\tilde{O}(\sqrt T)$, significantly improving over the previous $\tilde{O}(T^{2/3})$ guarantee for the same model. To the best of our knowledge, this is the first $\tilde{O}(\sqrt T)$ regret guarantee for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning (Statistics)

• arXiv preprint · 1 October 2026

  Learning Multiple Timescales for Goal-Conditioned Reinforcement Learning

  Pedro Robles Dutenhefner, Dikshant Shehmar, Wagner Meira and 1 other
• arXiv preprint · 2 October 2026

  Generalization Bounds for Flow-matching Generative Models for Intrinsically Low-dimensional Data

  Saptarshi Chakraborty, Quentin Berthet and Peter L. Bartlett
• arXiv preprint · 2 October 2026

  Differential Privacy of Gradient Descent on Perturbed Objectives

  Austin Watkins and Raman Arora
• arXiv preprint · 1 October 2026

  Platonic Task Arithmetic

  Junghwan Park and Woojin Cho
• arXiv preprint · 2 October 2026

  Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback

  Khang Luong, Dinh Thai Son, Hoang Ta and 2 others

All new papers in Machine Learning (Statistics)