다중 팔 밴딧(Multi-Armed Bandits)에서의 예상 샘플 복잡도

샘플 복잡도는 순차적 의사결정 문제에서 널리 사용되는 측정 지표로, 에이전트와 환경 간의 상호작용 중 발생하는 최적이 아닌 결정의 수를 정의합니다. 우리는 확률적 다중 팔 밴딧(stochastic multi-armed bandit) 문제의 샘플 복잡도를 연구하고, 근사적으로 기대값에서 정확한 기댓값 성능 측정 지표(approximately correct in expectation, ACE)를 도입하여 분석합니다. 우리는 ACE 보장이 다른 프레임워크에서 발견되는 고확률 보장과 달리 최적 예상 보상으로 거의 확실하게 수렴함을 보여주며, 또한 ACE 보장을 명시적인 기대 후회(expected regret) 경계로 변환하는 방법도 제시합니다. 나아가 기존 측정 지표와 달리 결정론적 알고리즘은 유리한 ACE 경계를 얻을 수 없음을 보여주고, 두 가지 설정에서 확률적 알고리즘을 분석합니다: 허용 가능한 최적이 아닌 수준 $\epsilon$이 알고리즘에 알려진 경우와 알려지지 않은 경우입니다. 전자의 경우, 우리는 탐색 후-$\epsilon$-그리디(explore-then-$\epsilon$-greedy) 알고리즘을 고안하고, 후자의 경우 Thompson sampling의 예상 샘플 복잡도를 분석합니다. 마지막으로, 두 설정 모두에 대해 거의 일치하는 하한 경계를 확립하여, 해당 알고리즘들이 $\epsilon$에서 타이트(tight)함을 보여주고 두 영역 간의 성능 분리를 증명합니다.