확률적 결정 집합과 적대적 손실을 가진 온라인 조합 최적화

요약

본 논문은 행동이 고장 나거나 차단될 수 있는 등 신뢰할 수 없는 복합 행동 환경에서 온라인 조합 최적화 문제를 다룹니다. 연구진은 확률적 가용성을 처리하는 새로운 학습 알고리즘을 제안하며, 이는 Follow-The-Perturbed-Leader 예측 방법을 기반으로 합니다. 이 알고리즘은 'Counting Asleep Times'라는 독창적인 손실 추정 기법에 의존하며, 전체 정보, (반-)밴디트, 제한 정보 설정 모두에 대한 후회 경계를 제공하고 기존 방법 대비 성능을 크게 개선했음을 입증했습니다.

핵심 포인트

• 신뢰할 수 없는 복합 행동(unreliable composite actions) 환경에서의 온라인 조합 최적화 문제를 다룸.
• 확률적 가용성(probabilistic availability)을 처리하는 새로운 학습 알고리즘을 제안함.
• 알고리즘은 'Counting Asleep Times'라는 독창적인 손실 추정 기법을 사용함.
• 전체 정보, (반-)밴디트, 제한 정보 설정에 대한 후회 경계(regret bounds)를 제공하며 성능 개선을 입증함.