번외_권휘님의 UCB 소개
Optimism in the face of uncertainty
David Silver 교수님 강의인 Reinforcement Learning 9강 Exploration and Exploitation 내용과 Sutton 교수님 책 Chapter2. Multi-armed Bandits에 언급되는 UCB(Upper-Confidence-Bound)에 대해 소개하는 내용입니다.
강의에서는 Optimism in the face of uncertainty의 방법으로 UCB를 소개하고 있습니다.
- 조건:
-
2장의 multi-armed bandit을 예시로 한다.
-
각 action에 대한 reward 분포를 정규분포라고 가정한다.
-
environment가 non-stationary 하다고 가정한다.
- 표기:
-
: 시점까지의 $a$에 대한 averaging reward
-
$Q(a)$: $a$에 대한 expected reward (true action-value)
-
$N_t(a)$: $t$ 시점에서 $a$의 방문 횟수
-
$U_t(a)$: $t$ 시점에서 $a$의 uncertainty
-
분포 그래프:
-
아래 그래프에서 $Q$를 $\hat Q_t(a)$ 라고 생각하자. bandit을 $t$에 따라 시행했을 때 $a$에 따라 얻는 $\hat Q_t(a)$의 분포를 나타낸다.
-
각 색깔 별 그래프의 특징을 살펴보자.
-
초록: 분포가 좁고 값이 가장 크다.
-
파랑: 분포가 넓고 값이 가장 작다.
-
빨강: 초록과 파랑의 중간이다.
-
분포가 좁다는 것은 해당 $a$이 많이 선택되었다는 의미이며 넓다는 것은 해당 $a$가 적게 선택되었다는 의미이다.
-
-
-
$a$ 선택 전략:
-
위 그래프만 보고 어떤 $a$를 택하는 것이 현명할까?
-
눈 앞의 이득을 보기 위해선 초록 or 빨강이 좋아보인다.
-
더 exploration을 할 여유가 있다고 했을 때, 파랑이 시도해볼만한 가치가 있어보인다.
- sample이 적어서 sample mean과 true mean의 차이가 작을 confidence가 크지 않다.
-
우리에게 exploration을 계속 할 수 있는 여유가 있다고 생각해보자. 위에서 생각한 방식대로 분포를 고려하면서 $a$를 선택할 수 있지 않을까?
-
-
Hoeffding’s Inequality
-
특정 $a$을 무한히 많이 실행하는 경우에 $\hat Q(s, a)$의 $Q(s, a)$로의 수렴성은 보장이 된다. (Law of large numbers)
- 물론 $a_1, a_2, a_3$에 대해서 모두 무한히 방문하는 경우에 정확한 $Q(a_1), Q(a_2), Q(a_3)$를 구할 수 있겠지만 너무 비효율적이다.
-
$\hat Q(s, a)$의 분포를 통해 confidence interval을 정의해보자 (Hoeffding’s inequality)
-
Hoeffding’s inequality는 어떤 random variable의 sample mean이 true expectation과 어떤 값 이상 차이가 날 확률에 대한 upper bound를 제시한다.
-
$\mathbb{P} [Q(a) - \hat Q_t (a) \ge U_t(a)] \le p = e^{-2N_t(a) U_t(a)^2} - (1)$
-
$Q(a)$를 모르지만 현재 아는 $\hat Q_t(a)$에 일정 값을 더해서 비교했을 때 어느 정도의 확률로 작은지는 알 수 있다. 만약 이 확률이 0이 되면 우리는 $Q(a)$를 알 수 있다!
-
-
-
UCB
-
$(1)$식에서 우리는 100% confidence를 만족하는 upper bound를 구하고 싶다. 그래서 $t$가 커짐에 따라 $e^{-2N_t(a)U_t(a)^2}$ 가 0에 가까워지도록 한다.
- $p = e^{-2N_t(a)U_t(a)^2} = t^{-4} - (2)$
-
$(2)$식에서 $U_t(a)$를 정리해보자.
- $U_t(a) = \sqrt{\dfrac {2\log t} {N_t(a)}}$
-
$t$가 충분히 커졌다고 했을 때 $Q(a) \approx \hat Q_t(a) + U_t(a)$ 로 근사 할 수 있다. $Q(a)$를 구했다고 가정했을 때, optimal action $A_t \doteq \arg\max_a \big [Q_t(a) + c \sqrt{\dfrac {\log t} {N_t(a)}} \big]$ 로 구하면 된다.
-
-
참고 자료:
- David Silver 교수님 강의 Lecture slides:
Reference: