Latent Dynamics · 2026-10-02
Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
Taehyun Hwang, Hyunjun Choi, Heesang Ann, Min-hwan Oh
AI-assisted summary based on the paper. Consult the linked source for methods and limitations. Benchmark numbers appear after editor verification.
TL;DR
The authors study endogenous nonstationary stochastic bandits with latent linear dynamics and bilinear rewards in the current action and unobserved latent state. They improve over an explore-then-commit (ETC) baseline by using stability to approximate the infinite-memory planning objective with a finite-memory cyclic block proxy, then applying block-level UCB with confidence sets for the truncated parameters. They prove a regret bound of order \tilde{O}(\sqrt{T}) versus the previous \tilde{O}(T^{2/3}).
Why it matters
The work gives a sharper regret rate for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark. The key technical step is a stability-based cyclic approximation that turns a coupled learning-and-planning problem into a stationary block-level learning problem, enabling optimistic exploration/exploitation instead of rigid explore-then-commit.
Method
- Use stability: geometrically decaying influence of far-past actions allows truncating the infinite-memory mean-reward and building a finite-memory block proxy reward.
- Apply cyclic approximation: approximate the open-loop benchmark by optimizing a block-level proxy over a cyclic repetition of the horizon.
- Run a block-level UCB (Block-OFUL) that maintains confidence sets for truncated dynamics parameters and updates the ridge estimate after each block to interleave learning and planning.
Abstract (from 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 $\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.
Related papers
- Statistical Foundations of Reinforcement Learning: A Non-Asymptotic Perspective
- World-Model Policy Arbiter for Goal-Conditioned Reinforcement Learning
- Reachability-Aware Diffusion Policy Optimization
- FewStepRL: Fine-tuning Few-step Diffusion Models with Reinforcement Learning
- Modeling Latent Disturbances for Robust Decision-Making in World Models
Publication record
Bibliographic evidence describes where and when a record appeared. It does not validate scientific claims.
First public release: 2026-10-01 · Indexed by Pub-AI: 2026-10-02 UTC
Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
Preprint posted: 2026-10-01 · Original record ↗
- arxiv
- 2610.00911
Explicit source versions (1)
- v1 · 2026-10-01
- Preprint available
Source date: 2026-10-01 · First detected: 2026-10-25 UTC · Historical baseline
Source evidence (1)
- Official evidence ↗ · atom:published (official metadata)
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 $\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.
