평균 기반 알고리즘: 하한선 및 후회 (Regret)

평균 기반 알고리즘 (Mean-based algorithms)은 평균 보상이 낮은 행동에 낮은 확률을 할당하는 온라인 학습 (Online learning) 알고리즘의 한 부류입니다. 최근 연구에 따르면 이러한 알고리즘은 경제 게임에서 내쉬 균형 (Nash equilibria)을 근사하는 직렬적으로 우세하지 않은 (Serially undominated) 행동으로 유리하게 수렴한다는 것을 보여줍니다. 그러나 경험적 연구에서는 밴딧 피드백 (Bandit-feedback) 시나리오에서 기존 알고리즘들에 비해 수렴 속도가 더 느리다는 점도 나타납니다. 본 연구에서는 시간 지평 (Time horizon)을 알 수 없고 오직 밴딧 피드백만을 사용할 수 있는 상황에서의 평균 기반 알고리즘을 연구합니다. 이러한 설정에서, 우리는 알고리즘을 정의하는 수열 $γ_t$에 대한 최초의 하한선 (Lower bound)을 제공하여, 이 알고리즘들이 얼마나 빠르게 학습할 수 있는지에 대한 한계를 공식적으로 확립합니다. 또한, 우리는 두 가지 평균 기반 알고리즘을 제안합니다. 하나는 $\epsilon$-greedy를 일반화한 것이며, 다른 하나는 평균 기반 Exp3를 미지의 지평 (Unknown horizons)으로 확장한 것입니다. 실험 결과, 평균 기반 알고리즘은 비록 약간 느리지만 다른 밴딧 피드백 알고리즘들과 경쟁력 있는 성능을 보일 수 있음을 확인했습니다. 나아가 우리는 무후회 (No-regret) 알고리즘과의 관계를 분석합니다. $γ_t$의 선택에 따라 무후회 알고리즘과의 교집합은 단순하지 않으며, 우리는 평균 기반이면서 동시에 무후회인 알고리즘이 존재함을 보여줍니다. 이는 이전 연구들이 시사했던 이 알고리즘 부류의 "착취 가능성 (Exploitability)"에 대한 맥락을 더해줍니다.