安全源于设计：具有连续动作的情境强盗中的实现成本约束

# 安全设计：连续动作上下文强盗算法的实现成本约束
来源：https://arxiv.org/html/2608.26755
Aldo Pacchiano  
隶属单位：波士顿大学  
隶属单位：MIT与哈佛大学布罗德研究所

###### 摘要
上下文强盗算法是处理不确定性下序贯决策的标准框架，在临床试验、剂量选择、推荐系统和自主系统等领域有广泛应用。安全性在许多应用中至关重要，因为在剂量选择或自动驾驶等场景中，单次不安全决策可能导致灾难性后果。在强盗问题中建模安全性的常见方法是为每个动作关联奖励信号和成本信号，并在成本约束下优化奖励。现有大多数安全约束强盗模型通过要求每个动作的期望成本低于规定阈值来实现安全性。然而，在异方差环境中，这种方法可能不够充分，因为所选动作不仅影响期望奖励和成本，还会影响观测结果的变异性。我们研究具有连续一维动作和基于实现成本的阶段性高概率约束的上下文强盗算法。我们提出了高概率约束UCB算法，这是一种乐观-悲观算法，在保守估计安全动作集的同时为奖励进行探索。对于线性奖励和成本模型，我们证明了严格的Õ(d√T)遗憾界，并利用eluder维度将分析扩展到一般函数类。实验表明，强制实现成本安全性相比基于期望成本的基线方法显著减少了约束违反情况。

## 1 引言
强盗算法[thompson1933likelihood,auer2002using,lattimore2020bandit]已广泛应用于多个领域，包括基于人类反馈的强化学习(RLHF)[christiano2017deep,xie2024exploratory]、临床试验[matsuura2022optimal,lee2020contextual,aziz2021multi,villar2015multi,bastani2020online]、推荐系统[wang2022context]、动态定价[mueller2019low]、大型语言模型[bouneffouf2024tutorial]和公平分配[procaccia2024honor]；更多概述参见[bouneffouf2019survey]。在这些领域中，学习者与未知环境进行序贯交互，旨在从观测中学习并通过决策最大化累积奖励。近期，人们对上下文强盗算法[foster2023foundations,lattimore2020bandit]的兴趣日益增长，学习者在从可能很大或连续的动作空间中选择动作之前会观察上下文。在此通用框架中，当应用涉及资源限制或安全要求[dai2023safe,wachi2020safe]时，约束强盗算法尤为重要。这些约束可以采用不同形式，包括背包强盗中的预算约束[badanidiyuru2018bandits]、公平性约束[joseph2016fairness]以及同时具有奖励和成本信号的模型[amani2019linear,pacchiano2021stochastic,pacchiano2024contextual]。后一种公式在广告和药物管理等应用中尤为自然，因为这些应用需要在效用与风险之间取得平衡。例如，在药物剂量问题中，治疗产生疗效信号（视为奖励）和毒性信号（视为成本）；目标是在确保毒性低于规定阈值τ的情况下最大化治疗效益，这与第二阶段临床试验类似。例如，相关工作[lee2020contextual]考虑了二元奖励-成本模型，该模型强制约束随时间的平均成本。虽然累积或平均成本控制在某些应用中足够，但许多安全关键场景需要阶段性约束，即控制每个时间步长的成本。为满足这一要求，研究人员研究了成熟的线性安全强盗问题[hutchinson2024directional,pacchiano2024contextual,moradipari2019safe]，其中在每个轮次t中，所选动作产生奖励信号rₜ∈ℝ和成本信号cₜ∈ℝ。目标是最大化期望累积奖励，同时确保每轮期望成本保持在已知安全阈值τ以下，且该约束以高概率成立。在同方差模型中（噪声水平不受所选动作影响），成本信号期望值的保证是自然的。然而，在自动驾驶、机器人控制和药物治疗等应用中，结果的变异性本身可能取决于动作水平。例如，机器人更快的运动可能由于摩擦或传感器噪声导致下一个位置的分布更广；自动驾驶中较大的速度可能比小速度更难预测；药物效果可能因剂量水平而异[kpeglo2021identification]。在此类异方差环境中，仅满足期望值约束并不能排除个别轮次出现灾难性结果。这促使我们设计能够控制每个时间步长实现成本信号本身的算法，而非仅控制其期望值。基于这一动机，我们考虑以下问题：是否可能设计出受约束的低遗憾算法，以高概率在每个轮次控制实现成本？本文在异方差奖励-成本模型[amani2019linear,pacchiano2024contextual,majzoubi2020efficient]中解决此问题，该模型具有一维连续动作。我们的目标是通过要求实现成本Cₜ满足约束P(Cₜ≤τ)≥1-δ来控制每个时间步长的成本信号，其中δ>0是用户指定的置信参数。与先前工作类似，最终保证同时考虑成本观测的噪声和算法的内部随机化。为实现这一目标，我们提出了一种类似UCB的算法——高概率约束UCB。该方法基于面对不确定性的乐观原则(OFUL)[auer2002using,abbasi2011improved]，且不需要事先知道初始安全动作，这与几种现有方法不同[pacchiano2024contextual]。该算法适用于随机和对抗性上下文环境，前提是奖励和成本信号的亚高斯噪声标准假设。在此假设下，我们构造了一个高概率约束事件，确保实现成本在每个轮次低于安全阈值。我们证明所提算法实现了T轮遗憾界Õ(d√T)，这对于线性强盗算法[lattimore2020bandit]在维度d和时间范围T上的依赖是最小最大最优的。此外，我们在合成数据集和真实数据集上实证验证了方法性能。最后，我们将分析扩展到非线性奖励和成本函数的场景，用eluder维度[russo2013eluder]（一般函数类的复杂度度量）刻画遗憾界。本工作的主要贡献如下：
- • 引入异方差环境中具有连续一维动作的奖励-成本约束强盗的安全框架。
- • 为线性和非线性奖励与成本模型推导出具有严格遗憾保证的算法。
- • 在合成数据集和真实数据集上验证方法，显示了高概率实现成本保证在异方差环境中的重要性。

## 2 模型与问题表述
**符号说明**。本文使用以下符号。对于向量x,y∈ℝᵈ，我们定义⟨x,y⟩=xᵀy和⟨x,y⟩ₐ=xᵀₐy分别为标准内积和加权内积，其中ₐ∈ℝᵈˣᵈ为正定矩阵。类似地，定义‖x‖₂=√⟨x,x⟩和‖x‖ₐ=√⟨x,x⟩ₐ分别为x的ℓ₂范数和加权ℓ₂范数。指示函数记为𝟙{⋅}。大写字母表示随机变量（如X），小写字母表示其实现（如X=x）。记[T]={1,…,T}。Õ表示忽略对数因子的大O符号。受自适应剂量分配强盗算法[matsuura2022optimal,lee2020contextual,aziz2021multi]启发，我们考虑以下动作、奖励和成本公式。在每轮t∈[T]中，学习者观察d维上下文向量Xₜ∈ℝᵈ，该向量可表示结构化测量值（如医疗测试结果）或非结构化信息（如语言模型生成的文本描述[baheri2023llms]）的嵌入。我们不对Xₜ施加分布假设；上下文可以是随机或对抗生成的。学习者选择一维连续动作αₜ∈[0,1][majzoubi2020efficient]，可视为有限剂量水平集的连续推广。环境根据以下公式生成奖励和成本信号：
Rₜ := g(αₜ)·(r(Xₜ)+ξₜʳ)， (1)
Cₜ := g(αₜ)·(c(Xₜ)+ξₜᶜ)， (2)
其中ξₜʳ和ξₜᶜ为亚高斯噪声项，r(Xₜ)和c(Xₜ)为底层奖励和成本函数。函数g:[0,1]→[0,1]已知且严格递增，满足g(0)=0且g(1)=1。在剂量应用中，g可解释为协变量无关的剂量反应曲线，例如可从先验研究估计的人群疗效或毒性剖面¹。自然扩展是允许奖励和成本具有不同的剂量反应函数，记为gᵣ(⋅)和gₙ(⋅)。虽然此扩展在实践中相关，但未引入额外理论困难，故我们使用公共函数g(⋅)简化符号。归一化g(1)=1无一般性损失，因为任何常数尺度均可吸收到奖励和成本函数中。该公式允许近似平坦区域以建模饱和或收益递减，同时保持可逆性。在剂量类应用中，通常假设疗效和毒性随剂量水平增加而增加；参见[aziz2021multi,lee2020contextual,le2009dose]及参考文献。在线性设置中，我们假设r(Xₜ)=⟨Xₜ,θ*⟩和c(Xₜ)=⟨Xₜ,μ*⟩，其中θ*,μ*∈ℝᵈ为未知参数。在更一般设置中，仅需r(Xₜ)和c(Xₜ)有界。交互协议总结如图1所示。为说明线性情况，考虑医疗场景，其中上下文Xₜ∈ℝᵈ表示编码医疗属性（如血压、氧饱和度或实验室检测结果）的患者特征向量。在此模型中，存在未知参数θ⋆,μ⋆∈ℝᵈ使得：
Rₜ = g(αₜ)·(⟨Xₜ,θ⋆⟩+ξₜʳ)，
Cₜ = g(αₜ)·(⟨Xₜ,μ⋆⟩+ξₜᶜ)。
向量θ⋆表征患者特征如何影响治疗疗效：内积⟨Xₜ,θ⋆⟩为正表示治疗预期效益高。类似地，向量μ⋆捕获相同特征与不良反应或毒性的关系，⟨Xₜ,μ⋆⟩值越大表示副作用风险越高。噪声项ξₜʳ和ξₜᶜ表示线性模型未捕获的随机变异性，如未观测的生理因素或测量误差。动作αₜ∈[0,1]表示给药剂量水平。通过已知响应函数g，剂量同时缩放奖励和成本信号，使学习者可在疗效与毒性间权衡。例如，炎症标志物升高（对应高⟨Xₜ,θ⋆⟩值）的患者可能从治疗中显著受益。但若同一患者表现出肾功能受损（对应高⟨Xₜ,μ⋆⟩值），则可能需减少剂量以减轻不良后果。该公式与疗效-毒性剂量反应曲线的标准单调性假设[wages2011dose,le2009dose]一致，即增加剂量往往同时增加治疗和毒性效应。相同动作依赖缩放也使模型具有异方差性。实际上，观测奖励和成本的变异性通过g(αₜ)取决于所选剂量。这捕获了积极治疗可能导致响应更难预测的事实[rawlins1974variability]。在此意义上，该模型允许随机偏离确定性单调性，如生物响应中的饱和或不稳定性。结果，学习者选择动作αₜ不仅要最大化期望累积奖励，还需控制治疗引发的变异性。我们的模型属于异方差强盗算法[xu2023noise,mukherjee2024speed,weltz2023experimental,hsieh2019stay]这一更广泛类别，其中噪声分布可能同时依赖于当前上下文和所选动作。在更一般公式中，噪声方差或亚高斯参数可按二次型φ(Xₜ,Aₜ)ᵀΣ⋆φ(Xₜ,Aₜ)缩放，其中φ(⋅,⋅):𝒳×𝒜→ℝᵈ表示联合上下文-动作嵌入，Σ⋆为未知正定矩阵。虽然我们的模型采用更简单结构，但它捕获了奖励-成本系统中常见的单调剂量反应行为，并保持可解释性，这一特性在医疗决策环境中尤为宝贵。
图1：安全强盗协议。

### 2.1 假设
在呈现分析和结果之前，我们说明全文使用的假设。这些假设在约束上下文强盗文献中是标准的；参见[hutchinson2024directional,pacchiano2024contextual,moradipari2019safe]及参考文献。