강화학습 - (4) UCB

강화학습

예측속의 불확실성 (Uncertainty in Estimates)

UCB는 탐색(exploration)에 사용되는 기법 중 하나로 밴딧 문제를 해결하는 논문들에 많이 나온다.

이 기법은 강화학습의 예측에서의 불확실성을 해결하기 위한 기법이다.

 

행동가치 Q(a)값을 예측한다고 가정해 보자.

그리고 해당 Q값은 어떠한 불확실성을 가지고 있다.

이 불확실성을 표현하기 위해 신뢰구간(confidence interval)을 설정한다.

따라서 이 신뢰구간 사이에 놓인 값들은 불확실성에 대해 확신이 있다고 보는 것이다.

만약 이 신뢰 구간이 작다면, 에이전트는 이 Q(a)값에 대해 엄청난 확신을 가지는 것이다.

반대로 이 신뢰 구간이 크다면, 에이전트는 이 Q(a)값에 대해 확신이 없는 것이다.

 

낙관적인 초기값 (Optimistic Initial Value)

이 이론에 의하면, 강화학습의 초기 값을 낙관적으로 선택하는 것이 초기 탐색에 도움을 준다고 한다.

여기서 낙관적이라는 말은 초기에 지식이 없는 상태에서 무조건 좋은 행동을 취한다는 말이다.

 

입실론 그리디를 예로 들어보면, 초기의 입실론(랜덤성)을 0으로 선택하고,

지식이 없는 상황에서 먼저 좋은 행동을 선택해 보는것이,

추후에 장기적으로 좋은 보상을 얻는데 도움이 된다는 말이다.

(먼저 어느정도의 좋은 보상을 탐색해 더 빠르고 좋은 학습이 되게 한다는 논리인 것 같다.)

 

하지만 이 방법에도 단점이 있는데,

초기에 좋은 것을 탐색했다고 해서, 더 좋은 행동이 없는것은 아닐 수 있기 때문에,

너무 빠르게 에이전트가 좋다고 생각하는 행동에 갇혀버릴 수 있다.

 

UCB (Upper-Confidence Bound)

UCB는 위에서 이야기한 신뢰구간의 upper bound를 활용해 탐색을 한다.

UCB는 존재하는 행동의 선택지 중에서, 가장 높은 upper bound를 가진 행동을 선택하는 알고리즘이다.

 

 

위 그림에서 가장 높은 upper bound를 가진 행동은 2번이다.

학습 초기라고 가정했을 때, 행동 2번은 너무 확실한 면이 있다고 해도,

가장 높은 upper bound를 가졌기 때문에 이를 선택하는 것이다.

 

 

하지만 보통의 경우 초기에 높은 upper bound를 가지는 것은,

위 그림에서의 행동 1번과 같이 불확실성이 강한 행동이다.

앞선 그림에서와 같이 실제로 불확실성이 적은 행동2의 경우라면, 높은 보상을 얻게 될 것이고,

현재 그림에서와 같이 불확실성이 높은 행동 1의 경우라면, 탐색이 가능해 지기 때문에,

탐색과 활용을 모두 잡으려는 알고리즘이라고 볼 수 있다.

 

UCB 알고리즘을 수식화 하면 다음과 같다:

$$A_t \dot{=} argmax\left[Q_t(a) + c \sqrt{\frac{ln t}{N_t(a)}}\right]$$

 

먼저 가장 높은 행동가치값인 $Q_t(a)$를 선택하고, 여기에 오른쪽항인 upper bound를 더해준다.

오른쪽항의 $c$는 하이퍼파라미터로, 탐색의 정도를 결정하는 값이다.

$ln t$는 현재까지 지난 시점에 $ln$을 취한 값이고, $N_t(a)$는 행동 $a$를 취한 횟수이다.

 

여기서 오른쪽 항은 에이전트가 탐색을 하게 하고, 왼쪽항은 가장 높은 $Q$값이기 떄문에 활용을 하게 한다.

또한 $c$를 통해 탐색의 정도를 조절할 수도 있다.

따라서 UCB는 탐색과 활용 모두를 잡기 위한 알고리즘이라고 볼 수 있다.