Multi Armed Bandit for RL(1) - 개요

이번 포스팅에서는 Multi Armed Bandit (MAB)을 다루려고 합니다. 다만 여기에서는 Reinforcement Learning으로 나아가기 위한 관점에서 서술합니다. (철저한 MAB 관점의 글은 이곳에서 확인할 수 있습니다.) MAB은 엄밀하게 강화학습은 아니지만, 강화학습으로 나아가기 위한 과도기적 방법이고, 적용이 간편하여 널리 사용되고 있습니다.

Multi Armed Bandit (MAB)

MAB 정의

MAB 정의는 굉장히 심플합니다. 아래 그림과 같이 살펴보겠습니다.

Figure 1: k-armed bandit problem

MAB는 위 상황으로부터 출발합니다. k개의 슬롯머신이 있는데 에이전트는 각 시도 마다, k개중 단 1개의 슬롯을 당겨 최종적으로 최고의 보상을 얻고 싶은 상황을 말합니다. 다시 말하면 에이전트가 1000번의 게임을 하는데 최대 보상을 얻기위해 1000번을 어떻게 당겨야할까를 푸는 문제입니다. 이러한 문제를 k-armed bandit problem이라고하며 MAB도 결국 같은 말입니다. 이렇듯 MAB의 시작은 슬롯머신의 보상을 최대화지만, 당연하게도 많은 상황으로 확장가능합니다.

Notation

• $t\in\{1,2,\cdots\}$: 시점
• $A_{t}$: $t$ 시점에서의 행동
• $R_{t}$: $A_{t}$ 행동에 대한 보상

위 k-armed bandit problem을 notation을 이용해서 나타내면 아래와 같습니다. $$A_{1}\rightarrow R_{1}\rightarrow A_{2}\rightarrow R_{2} \rightarrow \cdots \rightarrow A_{1000}\rightarrow R_{1000}$$

Action의 기준

각 시도마다 에이전트가 큰 보상을 얻기 위해선 어떤 지표가 필요할 것입니다. 어떤 지표가 좋다고 말해주는 행동을 취한다면 최대 보상을 얻을 전략을 수립할 수 있습니다. MAB에서는 크게 두 지표를 이용합니다.

• 행동 가치 함수: $$q_{*}(a)=\mathbb{E}\left[R_{t}|A_{t}=a\right]$$
• Preference: $$\mathbb{P}\left[A_{t}=a\right]=\frac{e^{H_{t}(a)}}{\sum_{b=1}^{k}e^{H_{t}(b)}}=\pi_{t}(a)$$

여기에서 $H_{t}(a)$는 행동 $A_{t}=a$에 대한 선호도입니다. (당장은 이런게 있다는 것만 알아두고 넘어가셔도 충분합니다.) 위 두 가지 지표를 확인하면서 최대보상을 얻기 위한 행동을 취할 수 있습니다. 두 지표의 성격이 약간 다릅니다. 행동 가치 함수는 행동을 취했을 때 평균 보상을 의미하고, preference는 $t$ 시점에서 선호할 행동을 확률로 나타낸 것입니다.

이번 포스팅과 다음 포스팅에 이에서 행동가치함수(action value function)을 이용하여 MAB를 푸는 방법을 살펴보고, preference는 따로 살펴보겠습니다.

행동가치함수추정

행동가치함수를 이용하여 행동을 선택하려면 행동가치함수가 당연히 어떤 값인지 알고 있어야 합니다. 세 가지 방법에 대해 알아보겠습니다.

Sample Average

첫 번째는 단순히 평균을 내는 방법입니다. 위에서 살펴 봤듯 행동, 보상, 행동, 보상, ... 의 순으로 반복됩니다. 이를 이용하여 $k$개 행동이 가능할 때 $t$ 시점의 각 행동별 가치함수는 다음과 같이 추정할 수 있습니다. $$Q_{t}(a)=\frac{\sum_{i=1}^{t-1}R_{i}I_{A_{i}=a}}{\sum_{i=1}^{t-1}I_{A_{i}=a}}$$ 즉 $t$ 시점의 가치는 $t-1$ 시점까지 실제로 어떤 행동 $a$가 취해 얻어진 보상의 합을, 행동이 취해진 횟수로 나누어 구하는 방법입니다. 만약 분모가 0인 기간에는 $Q_{t}(a)=0$같이 어떤 상수로 초기화합니다.

Incremental Implementation

Sample Average 방법은 컴퓨터 계산에 있어 약간의 문제를 갖고있습니다. $t=1$ 시점부터 어떤 시점 $T$까지 $$\{A_{1},A_{2},\cdots,A_{T}\}, \{R_{1},R_{2},\cdots,R_{T}\}$$를 저장하고 있어야합니다. 따라서 $T$가 커지면 메모리 이슈가 발생하게 됩니다. 이를 방지하고자 online으로 평균을 업데이트 시키는 컨샙이 incremental implementation이며, 앞으로 다룰 강화학습 전 영역에 걸쳐서 굉장히 중요한 역할을 합니다.

$n+1$ 시점에서의 보상의 incremental implementation은 아래와 같습니다. $$\begin{align*}Q_{n+1}&=\frac{1}{n}\sum_{i=1}^{n}R_{i}\\&=\frac{1}{n}\left(R_{n}+\sum_{i=1}^{n-1}R_{i}\right)\\&=\frac{1}{n}\left(R_{n}+(n-1)Q_{n}\right)\\&=\frac{1}{n}\left(R_{n}+nQ_{n}-Q_{n}\right)\\&=Q_{n}+\frac{1}{n}\left[R_{n}-Q_{n}\right]\end{align*}$$

Incremental Implementation을 이용한다면 단지 $Q_{n}$, $R_{n}$만 메모리에 기록해두면 계속해서 행동가치함수를 업데이트 할 수 있습니다. 앞에서 강화학습 전 영역에 걸쳐서 중요한 역할을 한다고 했습니다. Incremental Implementation은 아래와 같이 일반화 할 수 있습니다. $$NewEstimate \leftarrow OldEstimate + StepSize\left[Target-OldEstimate\right]$$ New Estimate, Old Estimate, Step Size, Target은 각각 sample average의 $Q_{n+1}$, $Q_{n}$, $n^{-1}$, $R_{n}$과 대응됩니다. 여기에서 $\left[Target-OldEstimate\right]$은 error라고 부릅니다. Target과 Step Size를 추가적으로 살펴보겠습니다. $R_{n}$이 target인 이유는 $n-1$ 시점까지의 평균 행동가치가 대비 $n$ 시점에 나아갈 방향을 제시해주기 때문입니다. Sample Average의 Step Size는 $n^{-1}$로 $n$에 대한 함수이며, 시간이 지날 수록 값이 줄어듭니다. Step Size의 경우 상수로도 처리할 수 있으며, 상수로 처리하는 것이 강화학습에서는 더 일반적 상황입니다.

Exponential Recency-Weighted Average

Incremental Implementation 말미에 Step Size를 상수로 처리하는 것이 일반적 상황이라고 했습니다. 실제로 직면하는 강화학습문제에서는 보상이 stationary하지 않은 경우가 대다수 입니다. 보상이 stationary하다는 것은 시간이 오래지나더라도 얻는 보상의 형태가 일정하다는 것을 의미합니다. 다시 말해 보상이 non-stationary하며, 이에 따라 아주 오래전 과거보다는 현재의 결과가 더 중요합니다. 그래서 가중평균방법을 이용하여 행동가치함수를 추정하며, 지수적으로 과거 보상의 반영분을 줄입니다. 이러한 방법을 exponential recency-weighted average라고 부릅니다. 방법은 아주 간단합니다 sample average의 step size를 상수로 바꿔주면 끝입니다. $$\begin{align*}Q_{n+1}&=Q_{n}+\alpha\left[R_{n}-Q_{n}\right]\\&=\alpha R_{n} +(1-\alpha)Q_{n}\\&=\alpha R_{n}+(1-\alpha)\left[\alpha R_{n-1}+(1-\alpha)Q_{n-1}\right]\\&=(1-\alpha)^{n}Q_{1}+\sum_{i=1}^{n}\alpha(1-\alpha)^{n-i}R_{i}\end{align*}$$ 여기에서 $\alpha\in(0,1]$ 이며, 1에 가까울수록 현재를 더 중요하게 생각한다는 의미가 됩니다.

마치며

이번 포스팅에서는 MAB를 이해하기 위한 초석을 다졌습니다. 다음 포스팅에선 행동가치함수기반 행동을 선택하는 여러전략에 대해서 살펴보고, MAB관련 마지막 포스팅에서 gradient bandit algorithm을 진행하도록 하겠습니다. 감사합니다 :)

References

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