arXiv:2611.17109v1 cs.LG

오라클 효율적 적대적 문맥 밴딧에 대한 거의 최적인 후회 한계

Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits

Kiarash Banihashem, MohammadTaghi Hajiaghayi

제출 2026-11-12

한국어 초록

우리는 $K$개의 행동, $N$개의 정책 클래스, 그리고 학습자가 표집할 수 있는 분포에서 나오는 i.i.d. 문맥을 갖는 문맥 밴딧을 연구한다. 플레이 이전에 고정된 임의의 손실 함수 열에 대해, 실현된 문맥에서 사후적으로 최선인 정책에 대한 기대 후회가 $O(\sqrt{KT\log(2N)}\,\log(2KT))$인 오라클 효율적 알고리즘을 제시한다. 이는 기존 오라클 효율적 한계에서의 시간 지평에 대한 $T^{2/3}$ 의존성을 개선하며, 이 설정에서 로그 인수를 제외하고 최적의 후회율을 달성한다. 우리의 알고리즘은 보조 문맥의 푸아송 표본을 사용하여 정책 점수를 섭동한다. 각 표집된 문맥에서 행동에 할당되는 섭동은 해당 문맥과 행동에 특정한 스케일을 곱한 라플라스 잡음 표본이다. 과거 관측으로 결정되는 볼록 목적함수를 최소화하도록 이러한 스케일을 선택하면 명시된 후회 한계가 얻어짐을 보인다. 나아가 최적값을 반환하는 정확한 오프라인 비용 민감 최적화 오라클만을 사용하는 투영 확률적 경사 하강법으로 최소화 스케일을 근사한다. 스케일 표가 커질 수 있으므로, 알고리즘은 각 갱신을 결정하는 무작위 표본을 저장하여 SGD 반복값을 암묵적으로 표현하고 질의된 문맥에서만 스케일을 계산한다. 오라클 복잡도와 나머지 자원 한계는 모두 $T$, $K$, $\log(2N)$에 대해 다항식이다.

원문 초록

We study contextual bandits with $K$ actions, a class of $N$ policies, and i.i.d.\ contexts from a distribution that the learner can sample. For any sequence of loss functions fixed before play, we give an oracle-efficient algorithm with expected regret $O(\sqrt{KT\log(2N)}\,\log(2KT))$ against the best policy in hindsight on the realized contexts. This improves the $T^{2/3}$ dependence on the horizon in prior oracle-efficient bounds and achieves the optimal regret rate in this setting up to logarithmic factors. Our algorithm perturbs policy scores using a Poisson sample of auxiliary contexts. At each sampled context, the perturbation assigned to an action is a Laplace noise draw multiplied by a scale specific to that context and action. We show that choosing these scales to minimize a convex objective determined by past observations yields the stated regret bound. We further approximate the minimizing scales by projected stochastic gradient descent using only an exact offline cost-sensitive optimization oracle that returns the optimum value. Since the table of scales can be large, the algorithm represents the SGD iterates implicitly by storing the random draws that determine each update and evaluates the scales only at queried contexts. Both the oracle complexity and the remaining resource bounds are polynomial in $T$, $K$, and $\log(2N)$.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.17109v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.