面向无知对手下多臂老虎机的最优切换遗憾

arXiv cs.LG 论文

摘要

本文解决了一个开放问题,表明一个单一算法在无知对手下的多臂老虎机中,针对每个S值都能实现最优切换遗憾。

arXiv:2609.13547v1 公告类型:新 摘要:我们研究对抗性多臂老虎机中的切换遗憾,其中学习者与最多改变$S$次的臂序列竞争。当$S$已知时,可获得最优期望遗憾$\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ [Auer et al., 2002]。然而,当$S$未知时,Marinov and Zimmert [2021] 表明在自适应对手下这个保证是不可能的。在本文中,我们表明一个单一算法在无知对手下,针对每个$S$都能实现$\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$期望遗憾,从而解决了Auer et al. [2019b] 的一个开放问题。我们的算法结合了一个以小学习率初始化的固定份额学习者和使用随机化学习率与隐式探索搜索局部改进的二进区间子程序。重要的是,一个非均匀先验倾向于跟随主学习者,保持维护许多子程序的成本较小。当子程序在主学习者上累积足够的改进时,其学习率加倍,从而允许适应未知数量的比较器切换$S$。
查看原文
查看缓存全文

缓存时间: 2026/09/15 08:45

# 迈向无视对手条件下多臂老虎机的最优切换遗憾

来源:https://arxiv.org/html/2609.13547

###### 摘要

我们研究对抗性多臂老虎机中的切换遗憾,其中学习者与一个切换次数最多为S的臂序列进行竞争。当S已知时,可以达到最优的期望遗憾 \(\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})\)(Auer 等人, 2002 (https://arxiv.org/html/2609.13547#bib.bib4))。然而,当S未知时,Marinov 和 Zimmert (2021) (https://arxiv.org/html/2609.13547#bib.bib18) 表明,在自适应对手下这个保证是不可能实现的。本文中,我们展示了一个单一算法,针对每一个S,在无视对手条件下都能达到 \(\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})\) 的期望遗憾,从而解决了 Auer 等人 (2019b) (https://arxiv.org/html/2609.13547#bib.bib6) 提出的一个开放问题。我们的算法结合了一个以小学习率初始化的固定份额学习者,以及使用随机学习率和隐式探索在二进制区间上搜索局部改进的子程序。重要的是,非均匀先验倾向于跟随主学习者,从而保持维护许多子程序的成本较小。当子程序累积了相对于主学习者的足够改进时,其学习率会翻倍,从而能够适应未知的比较器切换次数S。

## 1 引言

对抗性多臂老虎机作为部分反馈下序列决策的基本模型,已被研究数十年。在T轮的时间范围内,学习者反复选择K个动作之一,并仅观察所选动作的损失,而环境可以为所有动作任意分配损失。经典性能度量是静态遗憾,它将学习者的累积损失与事后最佳固定动作的损失进行比较。最小最大静态遗憾为 \(\Theta(\sqrt{KT})\)(Auer 等人, 2002 (https://arxiv.org/html/2609.13547#bib.bib4);Audibert 和 Bubeck, 2009 (https://arxiv.org/html/2609.13547#bib.bib3))。然而,当最佳动作随时间变化时,静态遗憾可能不够强。这促使了更强的S切换遗憾的概念,它将学习者与一个切换次数最多为S的最佳动作序列进行比较。在非平稳随机老虎机中,这个基准通常受到损失分布变化最多为S的环境的推动。一系列工作已经开发了即使在预先不知道分布变化次数S的情况下也能达到近似最优动态遗憾的算法(Auer 等人, 2019a (https://arxiv.org/html/2609.13547#bib.bib5);Auer 等人, 2019b (https://arxiv.org/html/2609.13547#bib.bib6);Wei 和 Luo, 2021 (https://arxiv.org/html/2609.13547#bib.bib26);Suk 和 Kpotufe, 2022 (https://arxiv.org/html/2609.13547#bib.bib23))。

当损失是对抗性的时,我们所知甚少。Auer 等人 (2002) (https://arxiv.org/html/2609.13547#bib.bib4) 的开创性工作引入了 EXP3.S,当其参数使用S调整时,它实现了 \(\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})\) 的切换遗憾。因此,当切换预算提供给学习者时,最优速率是已知的。对于自适应对手,这种对先验知识的依赖通常无法去除。特别是,Marinov 和 Zimmert (2021) (https://arxiv.org/html/2609.13547#bib.bib18) 表明,没有任何单一算法能够同时在所有切换类别上达到最小最大速率。对于无视对手的相应问题则知之甚少。最近,Qian 和 Wei (2026) (https://arxiv.org/html/2609.13547#bib.bib19) 表明,对于已知变化次数的分段常数确定性损失序列,一个算法可以同时达到最优的静态和动态遗憾率。从切换遗憾的角度来看,他们的结果控制了S=0以及一个规定的非零S值,该值等于已知的损失变化次数。它没有为每一个可能的S值同时提供最优保证。这留下了一个开放性问题:是否存在一个单一算法,在不知道S的情况下,针对无视对手,同时为每一个S实现 \(\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})\) 的切换遗憾?

##### 贡献

在本文中,我们通过设计一个单一算法肯定地回答了这个问题,该算法保证了对所有 \(S \in \{0,\ldots,T-1\}\) 同时实现 \(\mathcal{O}(\sqrt{(S+1)KT}\log^{4}(KT))\) 的期望遗憾。这匹配了最小最大值对S、K和T的依赖,最高可达对数因子,解决了 Auer 等人 (2019b) (https://arxiv.org/html/2609.13547#bib.bib6) 提出的开放问题。我们的算法从一个以小学习率启动的固定份额主学习者开始,并在二进制区间上启动辅助学习者,以在不同时间尺度上搜索局部改进。每个辅助学习者可以选择遵循主分布,或者将概率质量转向一个挑战者臂,使用随机学习率和隐式探索从老虎机反馈中学习。一个关键的设计选择是非均匀先验,它将大部分权重放在跟随主学习者上。这保持了保留主分布的聚合初始化惩罚较小,同时保留了利用局部改进的能力。在这个过程中,算法还跟踪了辅助学习者相对于主学习者累积改进的可观察估计。当这个估计达到一个规定的阈值时,算法会以两倍的学习率重新启动主学习者。分析解释了为什么这个规则可以适应未知的切换预算。如果主学习者远远落后于一个切换比较器,它的劣势可以追溯到固定臂表现更好的二进制区间。我们表明,随机学习率允许辅助学习者尽管有老虎机反馈也能捕捉到足够多的这些改进。将估计的改进与实际损失联系起来,可以控制每个时段的遗憾,并表明累积的收益在预期中覆盖了更大学习率的额外成本。

### 1.1 相关工作

##### 对抗性多臂老虎机中的切换遗憾。
Auer 等人 (2002) (https://arxiv.org/html/2609.13547#bib.bib4) 通过 EXP3.S 算法开创了在老虎机反馈下切换遗憾的研究。对于切换次数最多为S的比较器,适当选择其学习和共享率可以得到 \(\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})\) 的遗憾。然而,学习率调整取决于S。因此,他们的结果为规定的切换预算提供了最优保证,但它没有为需要不同学习率尺度的两个切换预算提供一次最优调整的运行,更不用说同时为每一个S提供了。Marinov 和 Zimmert (2021) (https://arxiv.org/html/2609.13547#bib.bib18) 将这个同时适应问题表述为一个模型选择问题。他们表征了相关的帕累托前沿,并表明自适应对手排除了在同一运行中为静态比较器和更丰富的切换比较器实现最优遗憾的可能性。然而,他们的下界并不涵盖无视对手,在这种情况下,整个损失序列在交互开始前就已固定,并且不会适应学习者的动作。在这个设定中,一个通用的途径是通过主构造来管理不同调整的 EXP3.S 副本,例如 Cheung 等人 (2022) (https://arxiv.org/html/2609.13547#bib.bib13) 的 Bandit-over-Bandit 框架。然而,这仅对所有S同时产生 \(\widetilde{\mathcal{O}}(K^{1/4}T^{3/4}+\sqrt{(S+1)KT})\) 的切换遗憾(Qian 和 Wei, 2026 (https://arxiv.org/html/2609.13547#bib.bib19))。Auer 等人 (2019b) (https://arxiv.org/html/2609.13547#bib.bib6) 明确地将不需要切换预算先验知识的最优对抗性遗憾作为一个开放问题。最近,Qian 和 Wei (2026) (https://arxiv.org/html/2609.13547#bib.bib19) 在移除这种用于无视确定性损失的开销方面迈出了第一步。当损失向量是分段常数且其平稳段的数目已知时,他们同时获得了最优的静态和动态遗憾。从切换遗憾的角度来看,他们的保证控制了S=0以及一个由已知环境变化数决定的规定非零S值。因此,它没有给出一个算法,能够在任意的无视损失表上,同时为每一个比较器切换预算达到最优。

##### 超越对抗性多臂老虎机的动态遗憾。
早期关于环境非平稳性下动态遗憾的工作研究了随机多臂老虎机(Besbes 等人, 2014 (https://arxiv.org/html/2609.13547#bib.bib7);Auer 等人, 2019a (https://arxiv.org/html/2609.13547#bib.bib5))和上下文老虎机(Luo 等人, 2018 (https://arxiv.org/html/2609.13547#bib.bib15);Chen 等人, 2019 (https://arxiv.org/html/2609.13547#bib.bib9))。这一路线被扩展到线性和广义线性老虎机(Cheung 等人, 2019 (https://arxiv.org/html/2609.13547#bib.bib11);Russac 等人, 2019 (https://arxiv.org/html/2609.13547#bib.bib21);Russac 等人, 2021 (https://arxiv.org/html/2609.13547#bib.bib22);Faury 等人, 2021 (https://arxiv.org/html/2609.13547#bib.bib14)),组合半老虎机(Chen 等人, 2021 (https://arxiv.org/html/2609.13547#bib.bib10)),以及非平稳马尔可夫决策过程(Cheung 等人, 2020 (https://arxiv.org/html/2609.13547#bib.bib12);Mao 等人, 2021 (https://arxiv.org/html/2609.13547#bib.bib17))。Wei 和 Luo (2021) (https://arxiv.org/html/2609.13547#bib.bib26) 随后开发了一个无先验知识的黑盒归约,该归约恢复了多臂和上下文老虎机的结果,并将最优动态遗憾适应扩展到了线性老虎机和强化学习。随机和上下文老虎机的进一步发展包括 Suk 和 Kpotufe (2022) (https://arxiv.org/html/2609.13547#bib.bib23);Abbasi-Yadkori 等人 (2023) (https://arxiv.org/html/2609.13547#bib.bib2);Suk 和 Kpotufe (2023) (https://arxiv.org/html/2609.13547#bib.bib24)。相关工作还研究了具有老虎机反馈的老虎机凸优化和非平稳随机优化(Besbes 等人, 2015 (https://arxiv.org/html/2609.13547#bib.bib8);Zhao 等人, 2021 (https://arxiv.org/html/2609.13547#bib.bib27);Wang, 2025 (https://arxiv.org/html/2609.13547#bib.bib25))。这些工作研究了环境非平稳性或比较器路径长度,而我们的结果则适应了在有限臂老虎机反馈下、任意无视损失表的事后比较器的切换次数。另一个最近的进展是 Rumi 等人 (2026) (https://arxiv.org/html/2609.13547#bib.bib20),它在不需要知道S的情况下,获得了无约束对抗性线性老虎机的最优 \(\widetilde{\mathcal{O}}(\sqrt{d(S+1)T})\) 切换依赖性,最高可达损失尺度和比较器范数因子。他们的方法利用了无界动作空间 \(\mathbb{R}^d\) 特有的尺度-方向分解,并指出将其扩展到约束动作集并非易事。我们的有限臂老虎机设置将每个播放动作限制为K个臂之一,并且仅揭示该臂的损失,因此他们的结果并不蕴含我们的结果。

## 2 预备知识和符号

##### 符号。
对于整数 \(n \geq 1\),记 \([n] \triangleq \{1,\ldots,n\}\)。令 \(\Delta_K\) 表示 \([K]\) 上的概率单纯形,定义为 \(\Delta_K \triangleq \{x \in \mathbb{R}^K: \sum_{i=1}^K x_i = 1, x_i \geq 0, \forall i \in [K]\}\)。令 \(e_i\) 表示 \(\mathbb{R}^K\) 中的第 \(i\) 个标准基向量,并记 \(\langle x, y \rangle\) 为标准内积。我们使用粗体符号表示序列,写作 \(\mathbf{a} = \{a_t\}_{t \in [N]}\),其中长度 \(N\) 从上下文中理解。事件的示性函数记为 \(\mathbb{I}\{\cdot\}\)。所有对数均为自然对数,除非显示了底数,并且 \(\log^+ z \triangleq \max\{0, \log z\}\),其中 \(z > 0\)。令 \(\mathbf{1}\) 和 \(\mathbf{0}\) 表示适当维度的全一向量和全零向量。对于公共单纯形中的概率向量 \(x, y\),令 \(\text{KL}(x \| y)\) 表示从 \(x\) 到 \(y\) 的 KL 散度。

##### 问题设定。
假设 \(T > K \geq 2\)。学习者与环境的交互持续 \(T\) 轮。在学习者抽取任何私有随机性之前,一个*无视*对手固定一个确定性损失表 \(\ell \in [0,1]^{T \times K}\),其中 \(K\) 是动作的数量。记 \(\ell_t = (\ell_{t,1},\ldots,\ell_{t,K})\) 为第 \(t\) 轮的损失向量。在每一轮 \(t \in [T]\),学习者根据其过去的观察和私有随机性选择一个分布 \(p_t \in \Delta_K\),抽取一个臂 \(i_t \sim p_t\),承受损失 \(\ell_{t,i_t}\),并且仅观察到这个选定的损失。所有期望都是针对固定损失表上的学习者随机化。学习者自身改变臂没有成本或约束。

##### 切换遗憾。
对于 \(S \in \{0,\ldots,T-1\}\),定义切换次数最多为S的比较器序列类为:
\[
\mathcal{U}_S \triangleq \left\{\mathbf{u} = \{u_t\}_{t \in [T]}: u_t \in \{e_1,\ldots,e_K\},\ \sum_{t=2}^T \mathbb{I}\{u_t \neq u_{t-1}\} \leq S\right\}.
\]
(1)
对于每个S,固定一个最佳比较器 \(\mathbf{u}^{(S)} \triangleq \{u_t^{(S)}\}_{t \in [T]} \in \arg\min_{\mathbf{u} \in \mathcal{U}_S} \sum_{t=1}^T \langle u_t, \ell_t \rangle\),
(2)
根据任意确定性规则打破平局。比较器 \(\mathbf{u}^{(S)}\) 仅取决于损失表,因此在学习者随机化之前就已固定。对于学习者的分布序列 \(\mathbf{p} = \{p_t\}_{t \in [T]}\),定义其S切换遗憾为 \(\mathbf{Reg}_T(\mathbf{u}^{(S)}) \triangleq \sum_{t=1}^T \langle p_t - u_t^{(S)}, \ell_t \rangle\)。我们的目标是设计一个单一算法,在不知道S的情况下,使得对于每一个 \(S \in \{0,\ldots,T-1\}\),有 \(\mathbb{E}\left[\mathbf{Reg}_T(\mathbf{u}^{(S)})\right] \leq \widetilde{\mathcal{O}}(\sqrt{(S+1)KT})\)。在分析过程中,我们也将其他决策序列与时间范围子区间上的 \(\mathbf{u}^{(S)}\) 进行比较。对于区间 \(I \subseteq [T]\) 和可能随机的序列 \(\mathbf{a} = \{a_t\}_{t \in [T]}\)(其中 \(a_t \in \Delta_K\)),定义 \(\mathbf{Reg}_I^{\mathbf{a}}(\mathbf{u}^{(S)}) \triangleq \sum_{t \in I} \langle a_t - u_t^{(S)}, \ell_t \rangle\)。
(3)
在部分

相似文章

具有反馈图的多臂老虎机问题的近最优一阶遗憾

arXiv cs.LG

该论文研究具有已知有向反馈图的对抗性多臂老虎机的一阶遗憾保证,通过固定点采样规则和两层聚合方法,将强可观察图的期望遗憾改进至接近最优的 Õ(√(αL*) + α),弥合了最坏情况与一阶保证之间的图依赖差距。

在具有不可观测状态和受限决策周期的马尔可夫匪徒中学习

arXiv cs.LG

本文研究了具有不可观测状态和可能受限决策周期的马尔可夫匪徒中的遗憾最小化问题,引入了一种称为自退化马尔可夫匪徒的推广。作者提出了UCB-NOM算法,该算法实现了接近对数的遗憾,并给出了不依赖于状态数量的界限。