안전한 제어기 선택을 위한 상쇄 없는 제약 SquareCB
Cancellation-Free Constrained SquareCB for Safe Controller Selection
한국어 초록
우리는 학습자가 매 라운드마다 $K$개의 행동 중 하나를 선택하여, 플레이의 기대 비용을 예산 이하로 유지하면서 손실을 최소화하는 제약 문맥 밴딧을 연구한다. 온라인 회귀로의 기존 환원 방식은 과거 제약 잔차로부터 학습된 라그랑주 승수로 비용에 가중치를 부여하므로, 일부 라운드의 여유가 다른 라운드의 위반을 상쇄할 수 있다. 우리는 대신 \citep{foster2020beyond}에서 제안된 SquareCB를 비용에 대한 정류된 가중치와 함께 실행한다. 이 가중치는 추정 비용이 예산 이내이면 0이고, 그렇지 않으면 비용을 예산으로 되돌리기에 딱 충분한 크기이다. 실현 가능성과 마진 $\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배 낮으며 후회는 더 낮거나 비슷하다.
원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2611.21880v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.