[CS246] Bandits (2) - Epsilon-Greedy Algorithm

Epsilon-Greedy Algorithm

Algorithm

For $t=1:T$ 동안 다음의 단계로 Explore/Exploit를 결정한다.

• $\epsilon_t = O(\frac{1}{t})$. $\epsilon_t$는 time $t$가 지날때마다 $1/t$로 감소한다
• $\epsilon_t$의 확률로 Explore: arm은 uniformly at random하게 선택하고, 선택된 arm을 탐색
• $1-\epsilon_t$의 확률로 Exploit: empirical mean이 가장 높은 arm을 선택한다. 

Auer et al. 에 따르면, 적절한 $\epsilon_t$를 고르면 다음이 성립한다고 한다.

\[ R_T = O(k \log T) \Rightarrow \cfrac{R_T}{T} = O\left( \cfrac{k \log T}{T} \right) \to 0 \]

 

Issues with Epsilon-Greedy

입실론-그리디 알고리즘도 몇가지 단점을 갖는다.

1. 알고리즘은 Exploration과 Exploitation을 명확하게 구별한다. (큰 문제는 아니다)
2. Exploration은 suboptimal choice를 만든다. arm을 균등하게 랜덤하게 선택하기 때문에 생기는 문제다

단점에서 알 수 있는 점은 exploring/exploiting을 할 때 arm을 비교하여 선택해야 optimal한 결과를 얻을 수 있다는 것이다.

다음의 예시를 보자

 

Arm 1: $[1 \ 0 \ 0 \ 1 \ 1 \ 0 \ 0 \ 1 \ 0 \ 1]$

Arm 2: $[1]$

Arm 3 $[1 \ 1 \ 0 \ 1 \ 1 \ 1 \ 0 \ 1 \ 1 \ 1]$

arm의 평균은 각각 5/10, 1/1, 8/10이다.

그러면 어떤 arm은 선택하고 싶은가? 

기댓값이 높은 arm2를 고르지는 않을 것이다. 왜냐면 confidence가 낮기 때문이다.

confidence가 높은 arm을 고르는 대표적인 알고리즘으로 UCB가 있다.