← 研踪 PaperTrailarXiv:2607.02891 · v2
Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
首次提交 2026-07-03 10:38
版本更新 2026-11-16 15:17
雷达观测 2026-11-17 17:12
摘要
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. Our key contribution is a blockwise reduction that connects parameter drift in non-stationary linear bandits to model misspecification in contextual linear bandits while preserving the round-specific decision benchmark. This connection allows us to leverage misspecification-adaptive learning to obtain dynamic-regret guarantees for general time-varying decision sets. For a known path-length budget , we establish these guarantees for general compact, adaptive non-anticipating decision sets under an oblivious parameter path, and for -armed contextual linear bandits under an oblivious environment. For general time-varying decision sets, our bounds improve the dependence on and from the guarantees available for existing LinUCB-based approaches to , matching the non-stationary lower-bound dependence up to logarithmic factors.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-16 15:17 · 最新观测版本
Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
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. Our key contribution is a blockwise reduction that connects parameter drift in non-stationary linear bandits to model misspecification in contextual linear bandits while preserving the round-specific decision benchmark. This connection allows us to leverage misspecification-adaptive learning to obtain dynamic-regret guarantees for general time-varying decision sets. For a known path-length budget , we establish these guarantees for general compact, adaptive non-anticipating decision sets under an oblivious parameter path, and for -armed contextual linear bandits under an oblivious environment. For general time-varying decision sets, our bounds improve the dependence on and from the guarantees available for existing LinUCB-based approaches to , matching the non-stationary lower-bound dependence up to logarithmic factors.
查看此版本解读 →查看此版本原文 ↗