改进带记忆的广义线性多臂老虎机,实现近最优后悔率。
Generalized Linear Bandits with Memory

- 采用分块算法与收缩置信区间,优化记忆影响下的决策策略。
- 理论证明后悔率可达 $ ilde{O}( ext{poly}(d,m, ext{κ}) imes ext{sqrt}(T))$,优于旧有 $T^{3/4}$ 结果。
- 首次统一处理非线性链接函数与记忆依赖,适合高维动态环境研究者。
我们研究带记忆的广义线性多臂老虎机,一种奖励依赖于过去动作的内生非平稳设置。基于线性模型的已有工作(Clerici 等,2024),我们指出先前 $ ilde{O}(T^{3/4})$ 的后悔界源于分析过松,并提供更紧致的分析,恢复了线性情形下的 $ ilde{O}( ext{sqrt}(T))$ 后悔率。随后将该改进扩展至广义线性模型,提出基于收缩置信区间的分块算法。该算法达到 $ ilde{O}ig( ext{sqrt}(mT) + d ext{sqrt}(T) + ext{sqrt}(κ) ext{ }d^2 m^{1/4} T^{1/4} + κd^2ig)$ 的后悔界,其中 $d$ 为特征维度,$m$ 为记忆长度,$κ$ 为链接函数的曲率参数。该结果在非线性奖励与记忆效应下仍保持 $ ext{sqrt}(T)$ 型速率。据我们所知,该分析首次统一处理记忆引起的非平稳性与非线性链接函数,且主导后悔项不依赖于链接函数的曲率。数值实验验证了理论发现的一致性。
原文摘要 · Abstract (English)
We study generalized linear bandits with memory, an endogenous non-stationary setting in which rewards depend on past actions through a finite memory matrix. Building on prior work for linear models (Clerici et al., 2024), we show that the previously known $\tilde{O}(T^{3/4})$ regret bound stems from a loose analysis, and we provide a sharpened analysis that recovers a $\tilde{O}(\sqrt{T})$ regret rate in the linear case. We then extend this improvement to generalized linear models and propose a block-wise algorithm based on shrunken confidence bounds. Our algorithm achieves a regret bound of $\tilde{O}\left(\sqrt{mT} + d\sqrt{T} + \sqrtκ\, d^{2} m^{1/4} T^{1/4} + κd^{2} \right)$, where $d$ denotes the feature dimension, $m$ the memory length, and $κ$ a curvature parameter of the link function. This attains a $\sqrt{T}$-type rate despite nonlinear rewards and memory effects. To the best of our knowledge, this analysis provides a unified treatment of memory-induced non-stationarity and nonlinear link functions, while ensuring that the leading regret term is independent of the curvature of the link function. We conduct numerical experiments that are consistent with our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。