Upper Confidence Bound 1

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

Algorithm

$$UCB{1}_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