Erdős-Rényi 측관측 그래프를 이용한 온라인 학습
요약
본 논문은 학습자가 선택한 팔 외에도 일정 확률로 다른 팔들의 손실을 관측할 수 있는 적대적 다팔 밴디트 문제를 다룹니다. 연구진은 서로 다른 손실 공개 확률 $r$의 범위에 적용되는 두 가지 새로운 알고리즘을 제안했습니다. 이 알고리즘들은 각각 특정 조건 하에서 기대 후회(expected regret)를 최적으로 달성하며, 특히 빠른 추정 절차도 함께 제공합니다.
핵심 포인트
- 적대적 다팔 밴디트 문제(adversarial multi-armed bandit problems)를 분석하여, 선택되지 않은 팔의 손실을 관측하는 상황을 모델링함.
- 손실 공개 확률 $r$에 따라 두 가지 최적화된 알고리즘을 제안했으며, 각각 다른 후회 경계($O( ext{regret})$)를 달성함.
- 제시된 후회 경계는 손실 공개 확률 $r$을 아는 어떤 알고리즘의 최적 성능과 로그 계수 이내로 증명됨.
- 손실 공개 확률 $r$ 자체를 결정하는 효율적인 추정 절차도 함께 제공함.
학습자가 실제로 선택한 팔 (arm) 외에도 일정 수의 팔의 손실 (loss) 을 관측할 수 있는 적대적 다팔 밴디트 문제 (adversarial multi-armed bandit problems) 를 고찰합니다. 모든 선택되지 않은 팔이 고정되었으나 알려지지 않은 확률 $r$로 독립적으로 그리고 학습자의 행동과 무관하게 손실을 공개하는 경우를 연구합니다. 우리는 서로 다른 $r$의 범위에 적용되는 두 가지 알고리즘을 제안합니다. $N$개의 팔을 가진 밴디트 문제에서 $T$라운드 후, 첫 번째 알고리즘의 기대 후회 (expected regret) 는 $r \ge(\log T)/(2N)$일 때 $O(\sqrt{(T /r) \log N })$이며, 두 번째 알고리즘은 더 작은 $r$값에 대해 $O(\sqrt{(T/r) \log (N+T)})$의 후회를 달성합니다. 또한 $r$의 범위를 결정하는 빠른 추정 절차도 제공합니다. 모든 우리의 경계는 $r$조차 알 수 있는 어떤 알고리즘의 최적 성능보다 로그 계수 (logarithmic factors) 이내입니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기