[RL] 2. Multi-Armed Bandits Problem

2. Multi-Armed Bandits Problem

처음에 들었을 때 bandits라고 해서 '도둑이라는 뜻 말고 다른게 있나?'하며 의아해 했던 기억이 있다. 알고보니 여기서 bandit은 슬롯머신을 말하는 것이었다. 즉, 여러개의 레버가 달린 슬롯머신을 떠올리면 될 것 같다.

여기서 문제는 슬롯머신에 달린 여러개의 레버 중에 어떤것을 당기는 것이 수익률이 가장 높을 것인가 하는 것이다. 이를 RL의 문제로 다시 풀어내면,

어떤 시점 t에 k 개의 action 중 하나를 선택할 수 있다. action을 선택하면 그에따른 reward를 받는다. Agent의 목표는 정해진 시간동안 받는 total reward를 maximize 하는 것이다.

일단 모든 레버를 당기기 전에는 어떤 레버가 얼만큼의 수익을 주는지 알 수 없다. 그리고 동일한 레버를 당긴다고 해서 항상 같은 수익을 얻지는 않는다. 즉, 같은 레버 1을 여러번 당겨도 어쩔땐 100원, 어쩔땐 110원, 어쩔땐 50원을 얻을 수 있는 것이다.

이같은 상황에서 우리는 어떻게 해야 이익을 극대화 할 수 있을까?

1. 일단 한번씩 다 당겨보고 가장 큰 수익을 주는 레버만 계속 당긴다.
   • 매우 단순한 방법이다. 하지만 만약 내가 계속 당기는 레버가 딱 첫판에만 가장 큰 reward를 주고, 나머지 회차에선 계속 적은 수익만 주는 레버였다면?
2. 각 레버를 여러번 당겨보고 각 레버가 주는 reward의 평균을 구한 뒤, 평균이 가장 큰 레버를 계속 당긴다.
   • 첫번째 방법보단 훨씬 그럴 듯 하다. 문제는 평균값을 알기 위해 몇번이나 당겨야 하는지 모르고, 그럴듯한 평균값이 구해지기 전까지는 계속 수익이 optimal 하지 않을 수 있다는 점이다.

수익을 극대화 하기 위해서는 현재 시점에서reward를 많이 주는 것 같은 레버를 최대한 자주 당기면서도 다른 레버들의 가능성 또한 무시하지 않는 알고리즘이 필요하다.

여기서 RL에서 중요한 두가지 키워드를 소개한다.

Exploitation: '이용한다' 라는 의미로, 현재 시점에서 가장 큰 reward를 주는 action을 선택하는 것을 말한다. Exploitation을 다른말로 'greedy action selection' 이라고 한다. 이를 수식으로 표현하면 다음과 같다.

$$A_{t} = argmax_{a} Q_{t}(a)$$

여기서 $Q_{t}(a)$ 는 어떤 action a 를 선택했을때의 평균 reward를 의미한다. 즉, greedy action selection은 $Q_{t}$가 가장 큰 action a를 선택하는 것이다.

Exploration: '탐험한다' 라는 의미로, 비록 현재 시점에서 가장 큰 reward를 주지는 않지만, 다른 action이 더 큰 reward를 줄 지도 모르니 다른 action을 선택해보는 것이다. 다른 말로는 _non-greedy action selection_이라고 한다.

즉, 좋은 RL 알고리즘은 greedy action과 non-greedy action을 적절히 섞어가면서 각각의 action이 주는 reward의 기대값을 업데이트 해야 한다.

Action selection 방법 중 가장 유명한(가장 기초적인) 알고리즘은 바로 $\epsilon$-greedy 알고리즘이다.

$\epsilon$-greedy action selection

간단히 설명하면 다음과 같다:

1. 어떤 작은 수 $\epsilon$ << 1 을 설정한다.
2. 매 시점 t에 $0 \leq r \leq 1$을 랜덤으로 생성한다.
3. 만약 $r \geq \epsilon$ 이라면, 현재 가장 큰 reward를 주는 action(편의상 K라고 하자)을 택한다.
   • 만약 $r \leq \epsilon$ 라면, 나머지 action들 중 하나를 랜덤으로 택한다.
4. 선택한 action에 따른 reward를 관찰하고, 해당 action의 $Q_{t}$를 업데이트한다.
5. 2.~ 4.를 반복한다.

즉, 매 시점에 $K \in A_{t}$가 선택될 확률은 $1-\epsilon + \frac{\epsilon}{|A|}$ 이 되고, K가 아닌 다른 action들 중에 하나가 선택될 확률은 $\epsilon - \frac{\epsilon}{|A|}$이 되는 것이다. ($\frac{\epsilon}{|A|}$가 더해지는 것은 random selection 시 K도 포함해서 random을 돌리기 때문이다.) $\epsilon$이 크면 클수록 agent는 Exploration를 더 많이 하게 되지만, 그만큼 그 시점에 큰 reward를 받는 빈도는 감소하게 된다.

이 알고리즘은 매우 단순하여 적용하기 쉽고, ($\epsilon$에 따라) 성능도 괜찮기 때문에 최신 RL 알고리즘들에서도 계속해서 보이는 알고리즘이다.

일반적으로는 $\epsilon$이 작을수록(0은 아니고) long-term을 놓고 봤을때 누적 reward가 높아진다. 이는 왠만큼 탐험을 하고나면 이제 어떤 action이 reward를 제일 많이 주는지를 확실히 파악이 되었으니 걔를 더 자주 당겨야 하는데, $\epsilon$이 높으면 높은 확률로 계속 explore 하게 되어 발생하는 현상이다.

Upper Confidence Bound(UCB) Action Selection

책에서는 Multi-armed bandits 문제에서 이보다 성능이 좋은 알고리즘을 소개한다. 바로 UCB 알고리즘이다.

$$A_{t} \doteq argmax_{a} \Big( Q_{t}(a) + c \sqrt{\frac{\ln t}{N_{t}(a)}} \Big)$$

$Q_{t}(a)$: action a의 평균 reward
c: 어떤 상수(hyperparameter)
t: 지금까지 흐른 시점
$N_{t}(a)$: t 시점까지 action a 가 선택된 횟수

여기서 $c \sqrt{\frac{\ln t}{N_{t}(a)}} \Big)$ 부분이 빠진다면 위 수식은 앞서 설명한 greedy action selection이 된다.
$c \sqrt{\frac{\ln t}{N_{t}(a)}} \Big)$ 부분이 바로 upper confidence bound로, 어떤 action a가 그동안 얼만큼 선택이 되었는지에 대한 가중치이다. 이는 a가 자주 선택되었을수록 점점 작아진다. 즉, 선택이 덜 되었을수록 이번에 선택될 가능성이 커지는 것이다.

위의 수식을 풀이하자면, 현재 시점 t에서의 action $A_{t}$는, 각 action a 의 평균값에 UCB를 더한 값이 최대인 action를 택한다.

위처럼 UCB는 multi-armed bandits 를 풀이하는데는 좋은 성능을 보이지만, 다른 RL 문제에서는 쓰이는 경우는 못본것 같다.

오늘은 여기까지~