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

추천 시스템이나 지능형 튜터링 시스템 같은 응용 분야에서는 시간이 지남에 따라 행동(action)과 관련된 보상(reward)이 감소하는 현상이 흔하게 발생합니다. 이러한 보상의 감소는 과거 실행된 행동 때문일 수도 있고(예: 특정 장르의 노래가 반복 추천되어 사용자가 흥미를 잃음), 외부 요인으로 인해 콘텐츠 자체가 구식이 되기 때문일 수도 있습니다. 본 논문은 이러한 상황을 '휴식성 로팅 밴딧 (rested rotting bandit)'과 '활동성 로팅 밴딧 (restless rotting bandit)'이라는 특정 사례로 모델링합니다.

이전 연구에서는 이 두 가지 문제가 매우 다르다고 여겨졌으며, 실제로 Levine et al. (2017)의 연구는 활동성 밴딧(restless bandit)에 대한 최신 알고리즘들이 휴식성 로팅 환경에서 성능이 떨어진다는 것을 보여주었습니다.

이에 본 논문은 **Rotting Adaptive Window UCB (RAW-UCB)**라는 새로운 알고리즘을 도입합니다. RAW-UCB의 가장 큰 특징은 다음과 같습니다:

1. 범용성: 휴식성(rested)이든 활동성(restless)이든, 또는 특정 유형의 비정상성(non-stationarity, 예: piece-wise constant, bounded variation)을 가지는 경우에도 근사 최적의 후회(regret)를 달성합니다. 즉, 환경에 대한 사전 지식이 필요 없습니다.
2. 강력한 성능: 이전 연구들에서 보상이 증가하는 상황에서는 유사한 결과를 얻기 어렵다는 부정적인 결과가 보고된 것과 대조적으로, RAW-UCB는 로팅(decaying) 환경에서 매우 강력하고 안정적인 이론적 성능을 입증했습니다.

연구진은 합성 데이터셋 및 실제 데이터 기반 실험들을 통해 이러한 이론적 발견들을 검증하였으며, 이 알고리즘이 다양한 실세계 시나리오에 적용될 수 있음을 보여주었습니다. RAW-UCB는 복잡하고 변화무쌍한 환경에서 최적의 의사결정을 내리는 데 중요한 기여를 할 것으로 기대됩니다.