arXiv:2605.25590stat.MLcs.LG2026-05

提出新算法解决非平稳线性带宽问题,计算开销恒定且性能更优。

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

论文配图:Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
图 1 · 摘自论文原文
  • 用折扣在线镜射下降法实现参数估计,每轮仅需常数级计算与内存。
  • 在漂移和分段平稳环境中分别达到理论最优的动态后悔界。
  • 适合需要长期运行、实时更新的动态决策场景,如推荐系统。

我们研究非平稳广义线性带宽(GLBs)问题,其中期望奖励通过未知时变参数的非线性链接函数建模,涵盖线性、伯努利及二项分布奖励等广泛模型。现有方法多基于最大似然估计(MLE),采用滑动窗口、重启或折扣机制应对非平稳性,但通常需在每轮重新访问历史数据,导致计算与内存成本随时间增长;部分方法还依赖非凸投影步骤。本文提出DOMD-GLB算法,利用折扣在线镜射下降(DOMD)进行参数估计,每轮仅消耗O(1)计算与内存。理论上,我们在漂移环境中获得$ ilde{O}(c_μ^{-1/2} d^{3/4} P_T^{1/4} T^{3/4})$的动态后悔界,在分段平稳环境中获得$ ilde{O}(c_μ^{-1/3} d^{2/3} Γ_T^{1/3} T^{2/3})$,其中$d$为特征维度,$T$为时间跨度,$P_T$为路径长度,$Γ_T$为切换点数量,$c_μ$为链接函数的曲率参数。该算法显著提升计算效率,是首个实现每轮计算与内存独立于时间的非平稳GLB算法。

原文摘要 · Abstract (English)

We study nonstationary generalized linear bandits (GLBs), where the expected reward is modeled through a nonlinear link function with an unknown time-varying parameter. This framework encompasses a broad class of reward models, including linear, Bernoulli, and binomial rewards. Existing approaches are predominantly based on maximum-likelihood estimation (MLE), using sliding-window, restart, or discounting mechanisms to handle nonstationarity. Although these methods achieve statistically efficient regret guarantees, they generally require revisiting past observations at every round, which leads to computation and memory costs that grow with time; moreover, several of them rely on a non-convex projection step. In this paper, we propose DOMD-GLB, a new algorithm for nonstationary GLBs that utilizes discounted online mirror descent (DOMD) for parameter estimation, thereby incurring only $O(1)$ computation and memory costs per round. We prove dynamic regret bounds of order $\tilde{O} \big(c_μ^{-1/2} d^{3/4} P_T^{1/4} T^{3/4}\big)$ in drifting environments and $\tilde{O}\big(c_μ^{-1/3} d^{2/3} Γ_T^{1/3} T^{2/3}\big) $in piecewise-stationary environments, where $d$ denotes the feature dimension, $T$ the time horizon, $P_T$ the path length, $Γ_T$ the number of change points, and $c_μ$ a curvature parameter associated with the link function, while substantially improving computational efficiency over prior work. To the best of our knowledge, this is the first algorithm for nonstationary GLBs with per-round computation and memory costs independent of time.

强化学习在线学习带宽优化动态环境

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。