Improved strategy cuts losses in hidden dynamics reward problems
Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
Machine Learning
Summary
This paper looks at a tricky problem where what you do now not only gives a reward but also changes hidden factors that affect future rewards. The authors found a smarter way to try out actions in blocks, learning as they go instead of committing too early. Their new approach cuts down mistakes much faster compared to older methods, making it easier to plan in complicated situations where the environment changes in unseen ways. This means computers can make better long-term decisions when rewards depend on hidden, shifting factors.
What this means in practice
- •For online advertising teams: Improve ad placement strategies by adapting campaigns that influence hidden user engagement dynamics for better long-term returns.
- •For robotic control engineers: Develop controllers for robots operating in environments where actions affect unobserved states and future rewards.
Authors
Taehyun Hwang, Hyunjun Choi, Heesang Ann, Min-hwan Oh
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 $\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.