Extreme bandits

요약

본 논문은 의학, 보안 등 다양한 분야에서 제한된 자원을 여러 출처에 순차적으로 할당할 때, 단순히 평균 보상을 최대화하는 것을 넘어 가장 극단적인 값(outlier)을 탐지하는 효율적인 방법을 연구합니다. 기존 밴디트 이론이 주로 '최대 평균 보상'의 후회(regret)를 다루는 것과 달리, 본 연구에서는 출처가 출력한 가장 극단적인 값을 탐지하는 데 초점을 맞춘 '극단적 후회(extreme regret)' 개념을 도입합니다. 이를 위해 ExtremeHunter라는 새로운 알고리즘을 제안하고, 이론적 분석 및 실제 세계 실험을 통해 그 성능을 검증했습니다.

핵심 포인트

• 기존 밴디트 이론은 주로 최대 평균 보상에 대한 후회(regret)를 최소화하는 데 초점을 맞춘다.
• 본 연구는 네트워크 침입 탐지 등 극단적인 값(outlier) 탐지가 중요한 분야의 특성을 반영하여 '극단적 후회(extreme regret)' 개념을 도입했다.
• 제안된 ExtremeHunter 알고리즘은 제한된 자원 하에서 가장 꼬리가 무거운 출처를 효율적으로 선택하도록 설계되었다.
• 알고리즘의 성능은 합성 데이터와 실제 세계 실험 환경에서 경험적으로 평가되었다.