Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
2026-07-03 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a problem where decisions must be made over time with changing options and shifting rewards, like choosing ads or prices that vary each round. Previous methods worked well but required strict assumptions about how available choices change, limiting their use in real scenarios. The authors introduce a new approach by breaking the timeline into blocks and treating changes within each block as small errors, allowing the use of existing algorithms to handle these errors. This method achieves good performance guarantees without restrictive assumptions, applicable to general decision sets and contextual problems.
non-stationary linear banditsdynamic regretdecision setspath lengthmisspecificationcontextual banditsregret minimizationonline decision-makingreward driftblock partitioning
Authors
Zihao Hu, Yuan Yao, Jiheng Zhang, Zhengyuan Zhou
Abstract
Many online decision-making problems involve both round-specific feasible actions and drifting reward models: eligible ad impressions, feasible prices, and available treatments can change over time, while user preferences, demand curves, and patient responses may evolve. Motivated by these applications, we study non-stationary linear bandits with round-specific feasible decision sets. Existing methods that obtain the optimal \(\widetilde O(T^{2/3}P_T^{1/3})\) dependence, where \(P_T\) is the path length of the reward-parameter sequence, impose an orthogonal-structure assumption on round-specific decision sets, which can be restrictive in contextual applications. We address this gap through a unified misspecification-reduction viewpoint: after partitioning the horizon into blocks, we relate each block's dynamic regret to regret against a fixed-parameter linear bandit benchmark, with the within-block parameter drift entering as bounded misspecification. Restarting algorithms with misspecification-dependent regret guarantees then yields the optimal \(T^{2/3}P_T^{1/3}\) dynamic-regret dependence for both linear bandits with general compact decision sets and \(K\)-armed contextual linear bandits.