Upper Confidence Bound 1

MAB 알고리즘의 일종. Epsilon Greedy와 달리 결정론적이고 파라메터가 없다는 점이 장점. 단 각 시행에 대한 보상이 0에서 1 사이여야 한다는 제약이 있음.

Algorithm

$$UCB1_i(t) = \hat u_i + \sqrt\frac{2 \ln t}{n_i}$$

where

• $\hat u_i$: mean reward of arm $i$ so far
• $n_i$: times arm $i$ has been played
• $t$: round