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

Sunmook Choi, Yahya Sattar, Yassir Jedra, Maryam Fazel, Sarah Dean
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:2071-2079, 2026.

Abstract

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 $\tilde{\mathcal{O}}(pT^{2/3})$ regret where $p$ is the action dimension. 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-choi26a, title = { Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics }, author = {Choi, Sunmook and Sattar, Yahya and Jedra, Yassir and Fazel, Maryam and Dean, Sarah}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {2071--2079}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/choi26a/choi26a.pdf}, url = {https://proceedings.mlr.press/v300/choi26a.html}, abstract = { 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 $\tilde{\mathcal{O}}(pT^{2/3})$ regret where $p$ is the action dimension. 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. } }
Endnote
%0 Conference Paper %T Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics %A Sunmook Choi %A Yahya Sattar %A Yassir Jedra %A Maryam Fazel %A Sarah Dean %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-choi26a %I PMLR %P 2071--2079 %U https://proceedings.mlr.press/v300/choi26a.html %V 300 %X 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 $\tilde{\mathcal{O}}(pT^{2/3})$ regret where $p$ is the action dimension. 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.
APA
Choi, S., Sattar, Y., Jedra, Y., Fazel, M. & Dean, S.. (2026). Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:2071-2079 Available from https://proceedings.mlr.press/v300/choi26a.html.

Related Material