提出高效鲁棒算法,解决带对抗干扰的异方差广义线性老虎机问题。
A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions
- 基于镜面下降与海森权重,实现每轮常数时间空间复杂度。
- 理论证明在扰动预算下达到近最优后悔界,涵盖多种常见分布情形。
- 适合需高鲁棒性与实时性的在线决策场景,如金融、推荐系统。
我们研究存在对抗性干扰的异方差广义线性老虎机(GLBs)问题,该问题包含异方差线性老虎机以及逻辑/泊松老虎机等情形。提出HCW-GLB-OMD算法,由基于在线镜面下降(OMD)的估计器和基于海森矩阵的置信权重构成,具有每轮仅$O(1)$时空复杂度的计算效率。在链接函数自协调假设下,证明了后悔上界为$ ilde{O}ig(d oot d rom t o T g( au_t) m{ heta}_{t,ullet} + d^2 g_{ ext{max}} u + d(g_{ ext{max}} + u) Cig)$,其中$m{ heta}_{t,ullet}$为时间$t$时最优臂处均值函数的斜率,$g( au_t)$为可能随时间变化的离散度(如线性情形下$g( au_t)= au_t^2$,伯努利/泊松情形下$g( au_t)=1$),$g_{ ext{max}} = ext{max}_t g( au_t)$为最大离散度,$C eq 0$为对手总扰动预算。同时给出下界$ ilde ext{Ω}(d oot d rom t o T g( au_t) m{ heta}_{t,ullet} + d C)$,统一了此前特定问题的下界。因此,该算法在扰动项中仅相差$ u$因子下,实现了各类异方差GLBs实例下的实例化极小极大最优性。
原文摘要 · Abstract (English)
We consider the problem of heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions, which subsumes heteroskedastic linear bandits and logistic/Poisson bandits, in the presence of adversarial corruptions. We propose HCW-GLB-OMD, which consists of two components: an online mirror descent (OMD)-based estimator and Hessian-based confidence weights to achieve corruption robustness. This is computationally efficient in that it only requires ${O}(1)$ space and time complexity per iteration. Under the self-concordance assumption on the link function, we show a regret bound of $\tilde{O}\left( d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d^2 g_{\max} κ+ d (g_{\max} + κ) C \right)$, where $\dotμ_{t,\star}$ is the slope of $μ$ around the optimal arm at time $t$, $g(τ_t)$'s are potentially exogenously time-varying dispersions (e.g., $g(τ_t) = σ_t^2$ for heteroskedastic linear bandits, $g(τ_t) = 1$ for Bernoulli and Poisson), $g_{\max} = \max_{t \in [T]} g(τ_t)$ is the maximum dispersion, and $C \geq 0$ is the total corruption budget of the adversary. We complement this with a lower bound of $\tildeΩ(d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d C)$, unifying previous problem-specific lower bounds. Thus, our algorithm achieves, up to a $κ$-factor in the corruption term, instance-wise minimax optimality simultaneously across various instances of heteroskedastic GLBs with adversarial corruptions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。