# Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 17 Oct 2025.

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

- [Optimal Regularization Can Mitigate Double Descent](https://mlsanity.com/paper/2003.01897/) (2020)
- [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)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020)
- [Current Challenges and Visions in Music Recommender Systems Research](https://mlsanity.com/paper/1710.03208/) (2017)
- [Blocking Bandits](https://mlsanity.com/paper/1907.11975/) (2019)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [Making Non-Stochastic Control (Almost) as Easy as Stochastic](https://mlsanity.com/paper/2006.05910/) (2020)
- [Rebounding Bandits for Modeling Satiation Effects](https://mlsanity.com/paper/2011.06741/) (2020)
- [Regret Minimization in Partially Observable Linear Quadratic Control](https://mlsanity.com/paper/2002.00082/) (2020)
- [Online Convex Optimization with Unbounded Memory](https://mlsanity.com/paper/2210.09903/) (2022)
- [Learning Linear Dynamics from Bilinear Observations](https://mlsanity.com/paper/2409.16499/) (2024)
- [Finite Sample Identification of Partially Observed Bilinear Dynamical Systems](https://mlsanity.com/paper/2501.07652/) (2025)
- [Non-Stationary Latent Auto-Regressive Bandits](https://mlsanity.com/paper/2402.03110/) (2024)
- [Sub-optimality of the Separation Principle for Quadratic Control from Bilinear Observations](https://mlsanity.com/paper/2504.11555/) (2025)

## Built on by (most cited first, 2 of 2)

- [Dual Control of Linear Systems from Bilinear Observations with Belief Space Model Predictive Control](https://mlsanity.com/paper/2604.24663/) (2026)
- [Block Optimism for Nonstationary Bandits with Latent Linear Dynamics](https://mlsanity.com/paper/2610.00911/) (2026)

## Abstract (arXiv)

We study a nonstationary bandit problem where rewards depend on both actions and latent states, the latter governed by unknown linear dynamics. Crucially, the state dynamics also depend on the actions, resulting in tension between short-term and long-term rewards. We propose an explore-then-commit algorithm for a finite horizon T. During the exploration phase, random Rademacher actions enable estimation of the Markov parameters of the linear dynamics, which characterize the action-reward relationship. In the commit phase, the algorithm uses the estimated parameters to design an optimized action sequence for long-term reward. Our proposed algorithm achieves tildeO(T2/3) regret. Our analysis handles two key challenges: learning from temporally correlated rewards, and designing action sequences with optimal long-term reward. We address the first challenge by providing near-optimal sample complexity and error bounds for system identification using bilinear rewards. We address the second challenge by proving an equivalence with indefinite quadratic optimization over a hypercube, a known NP-hard problem. We provide a sub-optimality guarantee for this problem, enabling our regret upper bound. Lastly, we propose a semidefinite relaxation with Goemans-Williamson rounding as a practical approach.