Kosoy 提出鲁棒老虎机多项式时间学习器，推进 AI 对齐

要回答的是：哪一类robust bandits能同时做到次线性遗憾和多项式时间。

• 对齐动机：作者把对齐看成学习问题，并认为不可实现学习的更好学习者对解决该问题很关键。可实现性要求学习者比环境更有表达力；环境中有相近或更强的智能体时，这一假设失效。
• grain of truth：若双方都假设对方策略属于H，对整个H低遗憾的策略本身可能不在H中，于是有一方必须做不可实现学习。作者称，找自然且一般、学习者仍落在其中的H，尽管有reflective oracle上的进展，问题仍开放。
• agnostic不够用：作者称监督之外agnostic保证难获得；在线学习里可实现情形的遗憾通常更好；强化学习里agnostic情形通常在统计上难处理。bandit版对无穷策略类有不可能性结果；有限但很大时，遗憾随策略类规模的平方根增长，作者称情形无望。
• 计算边界：robust bandits仍要求真假设在H中，但假设只部分刻画环境，对手可任选相容环境。比较对象是知道真假设、却不知道对手在假设内如何选择的最优策略。Kosoy [51]对一大类有Θ(√T)遗憾，论文称无计算保证。该工作给出欧氏球、线性奖励、仿射约束下的多项式时间、Õ(√T)策略，并称若干小推广为NP-hard。
• 博弈设定：
  • 信息：共T轮，双方知道T。对手先选h⋆∈H。学习者知道X、D、H、r、T，不知道h⋆。
  • 交互：学习者选xt∈X；对手选Pt∈h⋆(xt)；抽出yt作为反馈，奖励为r(xt,yt)。
  • 遗憾：vh(x)是该假设下臂x的最坏期望奖励，Vh再对臂取最大。RT相对真假设的V⋆。
  • 效率：统计有效指对一切h⋆都有次线性遗憾。计算有效指时间是|ϕ|与T的多项式，且RT≤poly(|ϕ|)T^{1-α}，α>0固定。

• agnostic与不可实现学习：Kearns et al. (1994)、Ben-David et al. (2009)不做环境形式假设，只要求在给定策略类中有竞争力。作者称在线学习里可实现情形的遗憾通常好得多，并引用Littlestone (1988)。Daniely (2016)、Daniely and Shalev-Shwartz (2016)给出半空间与DNF上agnostic计算难、可实现版本容易的例子。bandit版在策略类较小时可行（Auer et al. 2002）；无穷策略类有不可能性（Bubeck, Munos, and Stoltz 2011; Bubeck et al. 2011）。作者称类有限但很大时，遗憾随规模的平方根增长，情形无望。强化学习方面，作者称agnostic情形通常统计上难处理，并引用Krishnamurthy et al. (2016)、Sekhari et al. (2021)、Jia et al. (2023)、Li (2025)。
• 不精确概率与部分刻画：Ellsberg (1961)、Gilboa and Schmeidler (1989)用凸概率集，并按最坏期望效用决策。Levi (1974, 1980)称闭凸分布集为credal set，Walley (1991)建立imprecise probability理论。作者把robust bandits看成用这一概念推广stochastic bandits。Alon et al. (2022)的partial concept class允许假设输出don't know。Pour, Mansouri, and Ben-David (2026)与Kosoy (2026)让假设对每个实例输出标签集，学习者猜其中任一标签。作者称其遗憾正好对应robust bandits，只是设定换成bandit：相对知道真假设、但不知道对手从允许集合里挑哪一个的学习者。
• 结果反馈：Bartók et al. (2014)的partial monitoring中，学习者看到的信号不必揭示奖励。Foster et al. (2021)在奖励之外还给任意观测。作者指出这两类模型与真实环境的最优动作或事后最优固定动作比，而不是与真假设的最坏情况价值比。
• 平滑对手：Spielman and Teng (2004)的smoothed analysis，以及Rakhlin et al. (2011)、Haghtalab, Roughgarden, and Shetty (2024)的smoothed adversaries，要求对手分布相对固定基测度的密度至多1/σ。该集合是credal set，因而是本文对手的特例。作者称这一限制使在线学习变得和统计学习一样容易（Block et al. 2022）；给定假设类的优化oracle时，计算上有效的学习成为可能（Haghtalab, Han, Shetty, and Yang 2022）。
• 基线与问题类：统计前作是Kosoy [51]的Θ(√T)学习者，论文称无计算保证；Appel and Kosoy [3]将imprecise bandits改称robust bandits。有限臂时作者称可归约到adversarial bandits，并在顶点上使用Exp3。下界来自Dani, Hayes, and Kakade (2008)的stochastic linear bandits。论文未使用命名的经验数据集。

作者把robust bandits当作不可实现情形下agnostic学习的另一条路，本文补的是其线性特例的计算边界。与平滑在线学习的差别是：那里credal set已知，这里要学习它；那里与事后最优假设比，这里与真假设的最坏情况价值比，作者称后者更容易。

整体做法是：在线性robust bandits上用椭球记录未知约束子空间，乐观地选臂，并用可观测惩罚决定一块探索要持续多久。多项式时间来自把选臂写成Bienstock算法可近似求解的QCQP。

问题设定与线性特例

• 实例：M=(X,D,H,r)。credal set是域上非空、弱拓扑下闭的凸概率集。H把每个臂映到一个credal set。对手先选h⋆∈H；每轮学习者选臂，对手在h⋆(xt)中选分布，学习者看到结果和已知奖励函数的值。
• 遗憾：定义为R_T:=TV^⋆−E[∑_t=1^Tr(x_t,y_t)]，即真假设的最坏情况价值与累计奖励之差。期望包含学习者、对手和采样。统计有效指对一切h⋆都有次线性遗憾。
• 计算有效：策略读入历史和参数ϕ的编码，输出下一臂。时间须是|ϕ|与T的多项式，且RT≤poly(|ϕ|)T^{1-α}，α>0固定。脚注写明：只要求次线性时，可用Pitt的delaying trick把指数时间策略改成多项式时间，所以定义要求T^{1-α}。运行时间按比特运算计。
• 线性特例：X、D是欧氏球，奖励对臂和结果都线性。每个假设用d_C个仿射约束规定可行均值，并满足Kosoy [51]的横截条件：解空间与D一致地远离相切，截断S∈(0,1]。ϕ含维数、球心与半径、奖励系数、S和奖励范围上界Cmax。数值为有理数；S^{-1}与Cmax以一进制给出，从而都不超过|ϕ|。因奖励对结果线性，臂价值等于在可行均值集上最小化奖励。

Algorithm 1：固定块长

• 表示：平移缩放后X、D为单位球，平移只加奖励常数，不改变遗憾或选臂。令w(x,y)=(1,x,y)。真约束对应一个线性子空间L；分布对臂x可行，当且仅当其均值m在D中且w(x,m)在L中。对手若只用更小的子空间，未使用的方向可以不学。
• 椭球：无噪声时新观测给出L的新方向；有噪声时不能确定地加入整条方向。知识记成椭球E_V，V从n^{-1}倍单位阵开始，块内不变。
• 选臂：块长为n，块内重复同一臂。若某臂的猜测可行集为空就选它，否则选猜测最坏奖励最大的臂。作者称猜测集偏保守，因而臂价值偏乐观。满块后若经验均值落在椭球外，就把ww^T加进V。
• 块长：n稍后取成约T的2/3次方，以平衡无信息块与有信息块的代价。这一节先假定选臂可以精确完成。

Algorithm 2：按惩罚结束块

• 分数：固定块长仍把每一块当成普通探索。经验均值已经远在椭球外时，不必等满n步。硬约束改成惩罚，分数为U_V,λ(x):=min_{y∈ D}[r(x,y)+λ p_V(x,y)]，再对臂取最大。V从单位阵开始。
• 停块：同一臂重复抽取，每步重算经验均值。首次出现np_V≥1，或时间到达T，就结束该块；若惩罚条件成立，则把长度加权的外积加进V。λ取⌈√T⌉，用来平衡每块的可观测惩罚和每轮剩余项。
• 先假定精确最大化该分数。精确界与高概率事件放在附录，不在这里展开。

多项式时间实现

• 选臂是瓶颈：更新V和检验p_V可在多项式时间完成。Algorithm 1要判断是否存在猜测集为空的臂，否则最大化一个本身由最小化定义的分数。内层问题凸，用Lagrange对偶和Sion的minimax定理写成对偶向量上的最大化。
• QCQP：得到的是约束个数固定、含一个有界椭球、目标二次、系数有理的QCQP。Bienstock [11, Theorem 1.3]对每个ε∈(0,1)返回违反各约束至多ε、目标至少比最优少ε的有理赋值，时间是输入规模与log(1/ε)的多项式。
• 近似不改速率：ε取成T的函数。作者称时间只对数依赖1/ε，故只多一个log T因子。Appendix A.1把椭球再放大一点，以得到有界的Lagrange乘子；空集检验用η=1/(2⌈√n⌉)，分数误差用κ=1/T。Algorithm 2没有空集检验，惩罚项已经是二次项，同样写成QCQP，κ同样为1/T。
• 精度假设：运行时间分析假定观测为有理数，比特长度是|ϕ|与T的多项式。

论文没有数值实验、实现计时或仿真。下面的「结果」都是遗憾界和复杂性归约。

实验设置

• 对象：线性robust bandits及其附近变体。论文未运行任何学习模型，也没有评审模型。
• 正结果设定：X、D为欧氏球，奖励线性，假设为带横截条件的仿射约束。参数ϕ有理，S^{-1}与Cmax以一进制给出。
• 两个策略：Algorithm 1块长n，非正式分析取n=T^{2/3}，精确实现取⌈T^{2/3}⌉。Algorithm 2取λ=⌈√T⌉。
• 指标：RT，对一切真假设h⋆和对手策略；期望含学习者、对手与采样。另有高概率界，失败概率记为δ。
• 下界来源：stochastic linear bandits，经Remark 2嵌入线性robust bandits。硬度归约来自MAX-CUT与CLIQUE。
• 重复：论文未报告重复实验次数。高概率界之外，期望遗憾再加至多CrTδ。

主结果

论文没有实验表。下表只转述定理中的遗憾界。

表格较宽，可左右滑动

学习者	条件	遗憾	出处
Algorithm 2	λ=⌈√T⌉，精确最大化分数	Õ(√T)	Theorem 1、11
Algorithm 2	同上，δ=(T+1)^{-2}，期望遗憾	Õ([q+(1+S^{-1})^2∥b∥₂²qd_D]√T)+O(Cr/T)	Theorem 21
Algorithm 1	n=T^{2/3}；精确实现用⌈T^{2/3}⌉	Õ(T^{2/3})	Theorem 4、15，Appendix A.1
任意学习者	最坏情况	Ω(√T)	Theorem 3，非正式

• 作者称T上的依赖在对数因子内是紧的：线性robust bandits包含stochastic linear bandits，而后者最坏遗憾为Ω(√T)。
• Theorem 1写明隐藏因子对维数、S^{-1}、Cr是多项式；这些量都不超过|ϕ|，因此符合第2节的计算有效定义。
• 作者称Bienstock算法的时间只对数依赖1/ε，近似选臂不改变上述速率。Appendix A.1、B.1把κ=1/T造成的额外遗憾写成至多1。

附近推广的计算硬度

• 测了什么：D改为单纯形、X改为多面体，或约束从Kosoy [51]的双线性放到三线性之后，已知真假设的规划是否仍容易；以及规划容易时学习是否仍容易。正式结论都是：若存在对全部参数和全部真假设满足计算有效定义的学习者，则复杂性类发生坍塌。摘要把这些推广称为NP-hard。
• 结果：Theorem 26（D为单纯形、X为球）、Theorem 31（X为多面体、D为球，证明用立方体）、Theorem 32（F对臂、假设参数、结果各自线性，X与D仍为欧氏球）写明，随机多项式时间学习者蕴含NP⊆BPP，确定性学习者蕴含P=NP。前两个归约自MAX-CUT，第三个自CLIQUE。第6节另写：X为单纯形、D为球时，问题相当于d_X+1个顶点臂，在顶点上跑Exp3得到Õ(√(d_X T))，且为多项式时间；X为有k个面的凸多面体时又变难。
• 作者的解读：线性实例处在可解边界上。多数硬度先说明已知真假设时最大化v⋆(x)已经难；Lemma 25把规划归约到学习，故学习也难。Theorem 34给出反方向的例子。

规划容易并不推出学习容易

• 归约：Lemma 25假定，对每个臂和每个η∈(0,1)，可在多项式时间从假设中抽出期望奖励不超过vh(x)+η的分布。再假定学习者满足RT≤P(|ϕ|)T^{1-α}。则对每个ε∈(0,1)，可在poly(|ϕ|,|h|,1/ε)时间内以概率至少2/3找到臂，使Vh−vh(x̂)≤ε。
• 反例：Theorem 34的参数是以一进制给出的整数n、k，2≤k≤n。臂和假设都对应k元子集，D是多面体，奖励含臂坐标与结果坐标的乘积。作者写明该族落在第2.1节设定之外。已知假设时规划为O(n^2)。
• 结论：若该族上仍有满足定义的随机多项式时间学习者，则NP=RP；确定性学习者则给出P=NP。归约自CLIQUE。作者由此称，只给规划oracle不足以得到多项式时间学习者。对手在该论证中每轮返回同一结果，因此即使遗憾保证只对这种对手成立，结论仍成立。

其他消融与分析

论文未报告数值消融。分析里写出的参数与结构事实如下。

• n=⌈T^{2/3}⌉、δ=(T+1)^{-2}：Algorithm 1的近似实现仍为Õ(T^{2/3})；用4V评分使高概率界的中间项加倍（Appendix A.1）。
• η=1/(2⌈√n⌉)、κ=1/T：空集检验与分数近似的设置；Tκ=1（Appendix A.1）。
• λ=⌈√T⌉、κ=1/T：Algorithm 2高概率界增加1，速率不变（Appendix B.1）。
• 更新次数：Algorithm 1至多O(log n)次（Lemma 7）；Algorithm 2完成的块为O(log T)（Theorem 21的论证）。
• 停块跳跃：Algorithm 2中np_V在最后一次观测后仍不超过4（Theorem 21的论证）。
• Remark 2：stochastic linear bandits可写成D=[-1,1]、r(x,y)=y、S=1的线性robust bandits，两边遗憾相同。

作者指出的局限与后续方向

• 其他学习框架：作者希望看到类似定义能否用于其他学习框架，以及能否为其设计计算有效的学习者（第7节）。
• 其他假设类：作者希望找出还有哪些假设类有计算有效的学习者（第7节）。
• 规划必须容易：作者写明，硬度结果说明线性实例的小改动已使规划变难，因此这类假设类需要某种使规划保持容易的结构（第7节）。
• 规划容易不够：作者写明Appendix C.5的例子说明，只有容易的规划并不够（第7节）。
• oracle：作者希望理解某些oracle存在时的计算效率，并具体问：除规划oracle外，是否有一组自然oracle，其存在能保证计算有效的学习者（第7节）。
• 结构化观测：Appel and Kosoy [3]把robust bandits推广到带结构化观测的在线决策，包含robust linear bandits和表格型强化学习，并给出遗憾界，但未处理计算效率。作者希望本文技术能否用于设计该设定的有效学习者（第7节）。

实验覆盖范围

• 正结果针对第2.1节的线性robust bandits：X、D为欧氏球，奖励对臂和结果线性，假设由仿射约束加截断S的横截条件给出。
• 计算参数ϕ包括维数、球心与半径、奖励系数、S和Cmax；数值为有理数，S^{-1}与Cmax以一进制给出，运行时间按比特运算计（第2.1节）。
• 上界是对一切h⋆∈H的遗憾界。Ω(√T)下界经Remark 2从stochastic linear bandits转入（Theorem 3）。
• 硬度归约使用MAX-CUT（Theorem 26、31）和CLIQUE（Theorem 32、34）。Theorem 34的臂与假设是k元子集，D为多面体，奖励含臂与结果坐标的乘积，作者写明它在第2.1节设定之外。
• 论文未报告算法实现、数值仿真或重复实验次数。多项式时间结论依赖Bienstock [11]的近似QCQP，以及观测为有理数、比特长度是|ϕ|与T的多项式这一假定（Appendix A.1、B.1）。

这是一篇关于不可实现bandit学习之计算边界的理论工作：线性robust bandits的一个欧氏球仿射特例有多项式时间、Õ(√T)遗憾的学习者，再做小推广就会落到复杂性坍塌。

• 问题：环境不必被假设完全刻画。robust bandits仍要求真假设在已知类中，但每个假设只给出部分规格，对手可任选相容环境。学习者要追上知道真假设、却不知道对手在假设内如何选择的最优策略。作者认为这类不可实现学习与对齐有关，因为环境里可以有相近或更强的其他智能体。
• 方法：用椭球累积对未知线性约束子空间的信息。固定块长的Algorithm 1按乐观的最坏奖励选臂；Algorithm 2把椭球硬约束改成惩罚，并用经验惩罚提前结束一块。选臂经对偶写成QCQP，用Bienstock的近似算法求解，容差随T选取，使近似不改变遗憾速率。
• 遗憾：Algorithm 2在λ=⌈√T⌉时，期望遗憾为Õ(√T)（Theorem 1、11）。Theorem 21在δ=(T+1)^{-2}下把期望遗憾写成Õ([q+(1+S^{-1})^2∥b∥₂²qd_D]√T)+O(Cr/T)。任意学习者的最坏遗憾为Ω(√T)（Theorem 3），论证是该问题包含stochastic linear bandits。固定块长版本在n=⌈T^{2/3}⌉时为Õ(T^{2/3})。
• 边界：摘要称若干小推广是NP-hard。正式结论是，D改为单纯形、X改为多面体或约束改为三线性时，随机多项式时间学习者蕴含NP⊆BPP，确定性学习者蕴含P=NP。另有一族实例，已知假设时规划只要O(n^2)，学习仍会推出NP=RP。
• 作者的结论：该线性特例处在可解边界上。作者认为robust bandits是处理不可实现性的一条路，并希望类似定义能做到其他学习框架；只让规划容易并不够，还需要能保住这一性质的结构，或规划之外的oracle。