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 Õ(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 Õ(√T), significantly improving over the previous Õ(T2/3) guarantee for the same model. To the best of our knowledge, this is the first Õ(√T) regret guarantee for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark.
Related
- A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets
- Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
- The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits
- Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits
- Set Membership Estimation for Stochastic Linear Contextual Bandits
BibTeX
@misc{hwang2026block,
title = {{Block Optimism for Nonstationary Bandits with Latent Linear Dynamics}},
author = {Taehyun Hwang and Hyunjun Choi and Heesang Ann and Min-hwan Oh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00911},
eprint = {2610.00911},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00911},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
AU - Taehyun Hwang
AU - Hyunjun Choi
AU - Heesang Ann
AU - Min-hwan Oh
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00911
UR - https://arxiv.org/abs/2610.00911
AB - 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 Õ(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 Õ(√T), significantly improving over the previous Õ(T^2/3) guarantee for the same model. To the best of our knowledge, this is the first Õ(√T) regret guarantee for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark.
ER -