# Block Optimism for Nonstationary Bandits with Latent Linear Dynamics

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

## Key facts

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

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

- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [Learning Linear-Quadratic Regulators Efficiently with only √T Regret](https://mlsanity.com/paper/1902.06223/) (2019)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [The Nonstochastic Control Problem](https://mlsanity.com/paper/1911.12178/) (2019)
- [Current Challenges and Visions in Music Recommender Systems Research](https://mlsanity.com/paper/1710.03208/) (2017)
- [Logarithmic Regret for Online Control](https://mlsanity.com/paper/1909.05062/) (2019)
- [Blocking Bandits](https://mlsanity.com/paper/1907.11975/) (2019)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [Rebounding Bandits for Modeling Satiation Effects](https://mlsanity.com/paper/2011.06741/) (2020)
- [Randomized Exploration for Non-Stationary Stochastic Linear Bandits](https://mlsanity.com/paper/1912.05695/) (2019)
- [Improved rates for prediction and identification of partially observed linear dynamical systems](https://mlsanity.com/paper/2011.10006/) (2020)
- [Optimal Rates for Bandit Nonstochastic Control](https://mlsanity.com/paper/2305.15352/) (2023)
- [Learning Linear Dynamics from Bilinear Observations](https://mlsanity.com/paper/2409.16499/) (2024)
- [Dynamical Linear Bandits](https://mlsanity.com/paper/2211.08997/) (2022)
- [Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics](https://mlsanity.com/paper/2510.16208/) (2025)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)

## Abstract (arXiv)

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