한국어 초록
우리는 학습자가 제한된 시간 단계 집합에서만 결정 규칙을 갱신할 수 있는 적대적 배치 온라인 학습을 도입한다. 이는 시간 구간이 배치들로 분할되고 각 배치 내에서 학습자가 고정된 정책을 사용해야 한다는 것과 동등하다. 우리는 이 모델을 확률적 밴딧, 온라인 볼록 최적화, 전문가 조언을 이용한 예측, 적대적 밴딧이라는 네 가지 대표 문제에 대해 연구한다. 확률적 밴딧에 대해서는 상대적 배치 증가에 기반한 보편적 복잡도 척도를 규명하고 간극 의존적 및 간극 독립적 후회 한계를 모두 확립한다. 표준 간극 의존적 복잡도에 대한 곱셈적 페널티가 배치 경직도에 대해 초선형으로 증가할 수 있음을 보인다. 나머지 세 문제에 대해서는 최적 후회가 배치 길이 수열의 2-노름으로 엄밀하게 특징지어짐을 보인다. 상한은 배치 구조를 알지 못하는 배치 무관 학습자가 이 복잡도 척도에 맞춘 일반적인 적응형 더블링 기법을 통해 달성한다. 반면 하한은 배치를 인지하는 학습자에게도 성립한다.
원문 초록
We introduce adversarially batched online learning, where the learner may update its decision rule only at a restricted set of time steps. Equivalently, the time horizon is partitioned into batches, within which the learner must use a fixed policy. We study this model for four canonical problems: stochastic bandits, online convex optimization, prediction with expert advice, and adversarial bandits. For stochastic bandits, we identify a universal complexity measure based on relative batch growth and establish both gap-dependent and gap-independent regret bounds. We show that the multiplicative penalty relative to the standard gap-dependent complexity can grow superlinearly in batch hardness. For the remaining three, we show that the optimal regret is tightly characterized by the 2-norm of the batch-length sequence. The upper bound is achieved by a batch-oblivious learner who does not know the batch structure, via a generic adaptive doubling trick tailored to this complexity measure. In contrast, the lower bound holds even for batch-aware learners.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.