-
UCB1 알고리즘의 pseudo-regret 분석
소개 멀티 암드 밴딧(Multi-armed bandit) 문제는 순차적 의사결정 문제(sequential decision problems)의 일종으로써 충분한 정보가 주어지지 않은 상황에서 탐색(exploration)과 이용(exploitation)의 균형을 찾는 것을 목표로 합니다. 멀티 암드 밴딧 문제에는 다양한 변종이 있는데 이번 글에서는 확률론적 멀티 암드 밴딧(Stochastic Multi-armed Bandit)과 성능 지표인 후회값(regret)의 정의를 알아보겠습니다. 또한, 이 문제를 해결할 수 있는 간단한 알고리즘 중 하나인 UCB1의 유사 후회(pseudo-regret)의 상한이 라운드 수에 대한 로그 스케일 이하임을 증명해보겠습니다. Stochastic Multi-armed Bandit 확률론적 멀티 암드 밴딧(Stochastic Multi-armed Bandit)은 각...
-
Thompson Sampling 소개 및 non-stationary MAB 문제 해결
이번 포스트에서는 Multi Armed Bandit 문제와 Thompson sampling을 소개하고 non-stationary MAB를 해결하는 간단한 알고리즘 중 하나인 Discounted Thompson Sampling에 대해 알아보려고 합니다. 이 알고리즘은 Vishnu Raj, Sheetal Kalyani의 논문 Taming Non-stationary Bandits: A Bayesian Approach에 자세히 소개되어 있습니다. 이 논문에서는 또 하나의 알고리즘 Discounted Optimistic Thompson Sampling(dOTS)을 제안했지만 본 포스트에서는 다루지 않겠습니다. Multi Armed Bandit, Thompson sampling에 대한 소개글은 Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen의 A Tutorial on Thompson Sampling을...