通过偏差缩减方法，实现非平稳线性 bandit 的最优动态后悔率。
Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
- 将时间分块，将动态后悔转化为固定参数下的偏差问题。
- 在任意紧致决策集下达到最优 $\widetilde O(T^{2/3}P_T^{1/3})$ 动态后悔率。
- 适用于一般上下文线性 bandit，无需正交结构假设，适合动态环境决策者。
许多在线决策问题同时涉及轮次相关的可行动作和漂移的奖励模型：可选广告展示、可行价格和可用治疗随时间变化，而用户偏好、需求曲线和患者反应也可能演化。针对此类应用，我们研究具有轮次相关可行决策集的非平稳线性 bandit。现有方法虽能实现最优 $\widetilde O(T^{2/3}P_T^{1/3})$ 依赖关系（$P_T$ 为奖励参数序列的路径长度），但要求轮次相关决策集满足正交结构，这在上下文场景中可能过于受限。本文通过统一的偏差缩减视角解决该问题：将时间轴划分为块后，将每块的动态后悔与固定参数线性 bandit 基准的后悔关联起来，块内参数漂移作为有界偏差。采用具备偏差依赖后悔保证的重启算法，可在一般紧致决策集和 $K$-臂上下文线性 bandit 情况下均实现最优 $T^{2/3}P_T^{1/3}$ 动态后悔率。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。