Skip to content

Posts UCB1 #
Find similar titles

Upper Confidence Bound 1 Algorithm. Multi-armed bandit 알고리즘의 하나.

알고리즘 #

한번도 관측되지 않은 arm이 있으면 해당 arm에 할당하고, 그렇지 않으면 아래 식에 따라 가장 점수가 높은 arm에 할당:

$$ score_i = r_i + \sqrt{ \frac {2 \cdot \log t} {a_i} } $$

r은 arm의 보상률(reward rate), t는 모든 arm의 관측횟수를 합한 것, a는 arm의 관측 횟수이다.

두번째 항에 대한 부연 설명 #

r 항은 0에서 1 사이의 값이고, 두번째 항은 관측횟수에 따른 보너스로, 해당 arm의 관측 횟수가 낮을수록 높은 값이 나온다.

\( t \)와 \( a_i \)의 값이 각각 0에서 100일 때 두번째 항만 따로 그려보면 아래와 같다. 참고로 \( a_i \)가 \( t \)보다 작을 수는 없으니 그림의 절반은 의미 없다:

Image

평면으로 보면 이런 모양. 밝은 색이 큰 값:

Image

(Wolfram Alpha에서 생성함)

함수의 모양이 재미있는데, \( t \)와 \( a_i \)의 값이 작을 때(즉, 실험 초기)는 관측 횟수의 사소한 차이가 결과에 크게 반영되고, 값이 클 때는 관측 횟수에 어지간한 차이가 있더라도 비슷한 값이 나온다.

결국 두 항을 합쳐보면, 보상률이 높은 arm에 더 많이 할당을 하긴 하되 다른 arm에 비해 관측이 지나치게 적게 되었으면 약간의 보너스 점수를 부여하여 관측횟수를 높일 기회를 부여한다. 그리고 실험이 진행되면 될수록 관측 횟수의 차이보다는 보상률의 차이를 더 중요하게 여긴다는 개념.

두번째 항(보너스 항)의 핵심은 \( \frac {\log t} {a_i} \) 부분. 제곱근, 상수 2 등은 이 값의 스케일을 적절히 보정해주는 역할을 한다. 보정을 하는 방식 때문에 이 알고리즘이 Upper Confidence Bound라고 불린다고 하는데 이 부분은 이해가 부족하여 설명을 생략.

Suggested Pages #

Other Posts #

0.0.1_20140628_0