Multi-Armed Bandit for RL(2) - Action Value Methods

이번 포스팅에선 이전 포스팅에서 다룬 MAB의 행동가치함수기반 최대보상을 얻기위한 행동선택법을 취하는 전략을 살펴보겠습니다.

Action Value Methods

큰 제목은 action value methods입니다. 즉 행동가치함수 기반 행동을 취하는 전략의 모음입니다. 기본적으로 action value methods는 행동가치가 큰 쪽으로 행동을 취합니다. 행동가치함수가 $t$ 시점에서 $Q_{t}$로 추정되었다는 대전제 아래 차근차근 살펴보겠습니다.

Greedy Action Selection

뼈대가 되는 방법은 탐욕 행동 선택법(greedy action selction)입니다. 탐욕 행동 선택법은 각 시점에서 기대보상이 최대인 행동을 취하는 전략 방법으로 아주 심플합니다. 가볍게 수식으로 정리하면, $$A_{t}=\underset{a}{\operatorname{argmax}}Q_{t}(a)$$ 눈치채셨겠지만 탐욕 행동 선택법에는 고질적인 문제가 있습니다. 단 2개의 행동만 선택 가능하다고 가정하겠습니다. 행동 1을 했을 경우엔 보상이 5이고, 행동 2를 했을 경우엔 보상이 3입니다. 그리고 우연히 첫 시도를 행동 2로 했다면, 항상 행동 2의 행동가치가 최대가 되어 sub-optimal에 빠지는 문제가 발생합니다.

Dilemma of Exploration & Exploitation (탐험과 활용의 딜레마)

Greedy Action Selection에서는 특정 시점 $t$에서의 정보를 이용하여 의사결정을 했습니다. 이러한 상황, 즉, 현 시점의 정보를 최대한 활용(Exploitation)한다고 합니다. Greedy Action Selection에서 계속 활용만하면, sub-optimal에 빠짐을 확인했습니다. 이런 문제를 방지하기 위해, 매 의사결정마다 일정확률로 랜덤하게 행동하여 탐험(Exploration)하는 전략을 취할 수 있습니다.

우리는 매 시점마다 오직 한 가지 선택을 해야되기 때문에 탐험과 활용을 동시에 수행할 수는 없습니다. 그래서 이를 탐색과 활용의 딜레마라고 부릅니다. 이어서 등장할 방법은 탐험과 활용의 밸런스를 유지하며 최대보상을 얻기 위한 행동선택전략법입니다. 

$\epsilon$-greedy Action Selection

탐험과 활용의 밸런스를 유지하기 위한 가장 심플하고 강력한 방법은 $\epsilon$-greedy Action Selection입니다. $\epsilon$-greedy는 강화학습의 전 영역에 핵심적인 역할을 하니 꼭 이해하고 넘어가야됩니다. (어렵지도 않아요!) 

$\epsilon$-greedy는 매 행동선택시 $\epsilon$의 확률로 exploration하고, $1-\epsilon$의 확률로 exploitation하는 방법입니다. $\epsilon$만큼 탐험하기 때문에 특별히 $\epsilon$을 exploration rate이라고 부릅니다. 가볍게 수식으로 정리하고 마치겠습니다. $$A_{t}\leftarrow \begin{cases}\underset{a}{\operatorname{argmax}}Q_{t}(a), & \text{ with probability }1-\epsilon \\ \text{a random action}, & \text{with probability }\epsilon\end{cases}$$

MAB Pseudocode

MAB의 알고리즘을 pseudocode로 살펴보겠습니다.

Figure 1: MAB pseudocode

위 상황에서 $\epsilon=0$이면 greedy action selection이 되고, 아닌 경우 $\epsilon\in(0,1]$는 $\epsilon$-greedy action selection이 됩니다. ($N(A)$: 행동 $A$를 선택한 횟수, $Q(A)$: 행동 $A$의 평균행동가치)

Upper Confidence Bound (UCB) Action Selction

$\epsilon$-greedy action selection의 exploration은 근거 없이 랜덤하게 행동을 선택한다는 약간의 단점이 있습니다. Upper Confidence Bound Action Selection (UCB)는 exploration을 할 때, 선택가능한 행동들의 불확실성(uncertainty)를 반영하고, 불확실성이 높은 선택을 할 수 있게하는 행동 선택 전략입니다.

UCB의 행동 선택 전략은 다음과 같습니다. $$A_{t}=\underset{a}{\operatorname{argmax}}\left[Q_{t}(a)+c\sqrt{\frac{\log{t}}{N_{t}(a)}}\right]$$ 수식의 모양이 신뢰구간(confidence interval)과 굉장히 유사합니다. 핵심내용은 square root안의 내용입니다. 분모 $N_{t}(a)$는 $t$ 시점 까지 어떤 행동 $a$가 선택한 횟수이며, 적게 선택한 행동일 수록 불확실성이 커지며, 상대적으로 많이 선택되게됩니다. 만약 $N_{t}(a)=0$인 경우 square root의 값을 무한대로 간주(불확실성이 큰 것으로 간주)하여 무조건 한 번은 뽑히도록합니다. 이어서 분자에는 $\log{t}$가 있습니다. 즉 $N_{t}(a)$가 증가하지않는 상태에서 시간이 지나면 square root의 값이 증가함에 따라 불확실성이 커지는 구조입니다. 마지막으로 $c$는 탐험의 강도를 나타내는 상수로 사용자가 선택해주면 됩니다. 요약하면 UCB는 exploration을 할 때 과거에 선택이 적게된 행동(불확실성이 있는 행동) 위주로 하는 방식입니다.

참고한 문헌의 연구결과에 따르면 UCB 전략이 $\epsilon$-greedy 전략보다 우세하다고 합니다. 그럼에도 불구하고 MAB가 아닌 강화학습에서는 대다수가 $\epsilon$-greedy 전략을 사용합니다. 왜냐하면 sample average (이곳 참조)와 비슷하게 최근의 결과를 강하게 반영시키기 어려워 nonstationary한 문제에 취약하기 때문입니다.

마치며

요약하면 Action Value Methods는 행동가치함수기반 행동 선택 전략이고, 탐색과 활용의 밸런스가 중요하며 크게 $\epsilon$-greedy와 UCB가 있는 것이 큰 틀입니다. 다음 포스팅에서는 Gradient Bandit Algorithm에 대해 알아보겠습니다. 감사합니다 :)

References

• Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 2. No. 4. Cambridge: MIT press, 1998.