휴식 및 활동성 밴딧 문제에 모두 적용 가능한 단일 알고리즘 제안

요약

본 논문은 추천 시스템이나 지능형 튜터링 시스템처럼 시간 경과에 따라 보상이 감소하는 '로팅 밴딧(rotting bandit)' 문제를 다룹니다. 기존 연구에서는 휴식성(rested) 밴딧과 활동성(restless) 밴딧을 분리하여 다루었으며, 두 환경 간의 성능 차이가 크다는 한계가 있었습니다. 본 논문은 이러한 이질적인 환경에 관계없이 근사 최적의 후회(regret)를 달성하는 새로운 알고리즘인 Rotting Adaptive Window UCB (RAW-UCB)를 제안합니다. RAW-UCB는 설정된 밴딧 유형이나 비정상성(non

핵심 포인트

• RAW-UCB 알고리즘을 통해 휴식성 및 활동성 로팅 밴딧 환경 모두에서 근사 최적의 후회(regret) 달성이 가능합니다.
• 제안된 알고리즘은 설정에 대한 사전 지식이 필요 없으며, 비정상성의 유형(예: piece-wise constant, bounded variation)과 무관하게 작동합니다.
• 기존 연구들이 보상이 증가하는 경우 성능 저하를 보인 것과 달리, RAW-UCB는 로팅 환경에서 강력한 성능을 입증했습니다.