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)))。
正文 · 原文
Abstract:We study constrained contextual bandits, in which a learner chooses one of $K$ actions in each round to minimize loss while keeping the expected cost of its play below a budget. Existing reductions to online regression weight the cost by a Lagrange multiplier learned from past constraint residuals, so slack in some rounds can offset violations in others. We instead run SquareCB proposed in \citep{foster2020beyond} with a rectified weight on the cost: it is zero when the estimated cost is within the budget, and otherwise just large enough to bring it back to the budget. Under realizability and Slater's condition with margin $\delta$, the algorithm attains regret $O(\sqrt{KT\,\mathrm{Reg}_{\mathsf{Sq}}(T)}/\delta)$ and cancellation-free violation $\sum_t(V_c^{p_t}-b)^+=O(\sqrt{KT\,\mathrm{Reg}_{\mathsf{Sq}}(T)})$, where $\mathrm{Reg}_{\mathsf{Sq}}$ is the error of the regression oracle. The same bounds hold when the budget must be met in every context, potentially adversarially chosen contexts. In controller selection for a safe-control-gym quadrotor and a BOPTEST building, the violation is 6 to 9 times lower than that of primal-dual and virtual-queue baselines, with a lower or comparable regret.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML) |
| Cite as: | arXiv:2611.21880 [cs.LG] |
| (or arXiv:2611.21880v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.21880 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Kartik Pandit [view email]
[v1]
Mon, 16 Nov 2026 20:47:19 UTC (43,991 KB)
来源:arXiv cs.AI · arxiv.org