跳到正文
arXiv cs.AI· Kartik Pandit, Sourav Ganguly, Arnob Ghosh·· 4 小时前AI 评分24

无抵消约束 SquareCB:面向安全控制器选择的新算法

Cancellation-Free Constrained SquareCB for Safe Controller Selection

AI 导读

研究提出一种无抵消的约束上下文赌博机算法,在 SquareCB 基础上对成本施加修正权重——估计成本在预算内时权重为零,超出时仅调回预算水平。在可实现性与 margin 为 δ 的 Slater 条件下,该算法取得 O(√(KT·Reg_Sq(T))/δ) 的 regret 和无抵消违规上界 O(√(KT·Reg_Sq(T)))。

正文 · AI 翻译

查看 PDF HTML(实验性)

摘要:我们研究带约束的情境赌博机问题,其中学习者在每一轮从 $K$ 个动作中选择一个,以最小化损失,同时使其行动的期望成本保持在预算之下。现有的归约到在线回归的方法通过从过去约束残差中学习到的拉格朗日乘子对成本加权,因此某些轮次的松弛可以抵消其他轮次的违反。我们改为运行 \citep{foster2020beyond} 中提出的 SquareCB,并对成本施加整流权重:当估计成本在预算之内时权重为零,否则权重恰好大到足以将其拉回预算。在可实现性和边际为 $\delta$ 的 Slater 条件下,该算法达到遗憾 $O(\sqrt{KT\,\mathrm{Reg}_{\mathsf{Sq}}(T)}/\delta)$ 和无抵消违反 $\sum_t(V_c^{p_t}-b)^+=O(\sqrt{KT\,\mathrm{Reg}_{\mathsf{Sq}}(T)})$,其中 $\mathrm{Reg}_{\mathsf{Sq}}$ 是回归预言机的误差。当预算必须在每个上下文中都得到满足(上下文可能被对抗性地选择)时,同样的界也成立。在 safe-control-gym 四旋翼飞行器和 BOPTEST 建筑的控制器选择中,违反量比原始-对偶和虚拟队列基线低 6 到 9 倍,而遗憾更低或相当。
主题: 机器学习 (cs.LG);人工智能 (cs.AI);机器学习 (stat.ML)
引用为: arXiv:2611.21880 [cs.LG]
  (或 arXiv:2611.21880v1 [cs.LG] 用于此版本)
  https://doi.org/10.48550/arXiv.2611.21880

由 DataCite 颁发的 arXiv DOI(待注册)

提交历史

来自:Kartik Pandit [查看电子邮件]
[v1] 2026年11月16日星期一 20:47:19 UTC(43,991 KB)

来源:arXiv cs.AI · arxiv.org