Multi-armed bandit problem - (1) (feat. 호구 형님)

대분의 알고리즘들이 그렇듯

강화학습의 궁극적 목적도 보상의 최대화이다. Multi-armed bandit 문제는 이 궁극을 잘 표현할 수 있는 사례이다.

여기서 bandit이란 영화에서라도 한 번쯤 봤을 라스베이거스에서 흔히 레버를 당겨 도박할 때 사용하는 그 기계가 맞다(...)

현재 우리가 선택 가능한 어떤 행동 $a$에 대한 기댓값을 $q_{*}(a)$라고 하자. 그런데, 일반적으로 우리는 어떤 레버를 당겨야 보상을 최대화할 수 있을지 모르는 상태이다.

bandit별 $q_{*}(a)$가 있을 거고, 기댓값이 가장 높은 bandit을 존나 당겨서 한몫 두둑이 챙기고 싶지만 $q_{*}(a)$를 몰라 보상을 최대화할 수 있는 알고리즘 내지 전략을 생각해야 한다.

즉 $q_{*}(a)$는 우리가 알고 싶은 함수이다.

그리고 다음과 같이 notation을 정의하면,

$A_{t}: \;\ t시점에서 \;\ 선택하는 \;\ 행동 \\ R_{t}: \;\; t시점에서 \;\; 받는 \;\ 보상 \\ E: \;\ 기댓값$

$q_{*}(a)$는 다음과 같이 정의할 수 있다.

$q_{*}(a) \doteq E \big[R_{t}|A_{t}=a\big]$

$q_{*}(a)$의 대충 estimated value를 $Q_{t}(a)$라 하면, 알고리즘의 과제는 결국 $Q_{t}(a)$를 $q_{*}(a)$에 근사 시키는 방법을 찾는 것이다.

그렇다면 $Q_{t}(a)$는 또 어떻게 알아내느냐.

존나 단순하게 생각하면 action-value method, 즉 action을 value를 estimate하는 방법을 쓰면 된다.

$Q_{t}(a)=\frac{t \;\ 이전에 \;\ 취한 \;\ a에 \;\ 대한 \;\ R의 \;\ 합}{t \;\ 이전에 \;\ a를 \;\ 취한 \;\ 횟수}=\frac{\Sigma^{t-1}_{i=1}R_{i}\cdot 1A_{i}=a}{\Sigma^{t-1}_{i=1}1A_{i}=a}$

위 식에서 1은 indicator fuction을 뜻하고, 원래 모양은 조금 더 간지나는데 markdown에서 어떻게 쳐야 구현될지 모르겠으니 넘어가고ㅋ 암튼 $a$라는 행동을 겁나 많이 해보면

즉 어떤 bandit을 많이 당겨보면 Law of Large Numbers에 따라 분모의 시행 횟수가 무수히 많아져 $Q_{t}(a)$가 $q_{*}(a)$에 근사하지 않겠냐는 식의 대충 생각이 가능은 하다.

그런데 우리가 무슨 호구 형님도 아니고 전재산 꼬라박을 때까지 도박을 할 수는 없는 노릇이기에.

보다 체계적인 전략이 필요할 것이다.

그래서 생각할 수 있는 전략은 일단 세 가지.

1. Greedy policy

지금 알고 있는 것 중 $Q_{t}(a)$가 가장 큰 $a$를 선택하는 식으로 exploitation을 하고, 이 전략은 이렇게 정식화.

$A_{t} \doteq \underset{a}{argmax} \;\ Q_{t}(a)$

그런데, 이것도 단점을 생각해보면 지금 당긴 것으로 잘 땄다고 계속 잘 따겠느냐? 일반적으로 그렇지 않을 것이다.

그러니까 $Q_{t}(a)$가 더 작은 action들도 시도해봐야 하는 것인데, 이를 exploration이라 한다. exploitation과 exploration은 일종의 trade off 관계이고 최적의 전략은 둘의 적당 짬뽕일 것이다.

2. e-Greedy policy

$\epsilon$-greedy policy는 바로 위와 같이 오지게 exploitation만 하면 탕진잼이니, exploration도 좀 해보자는 생각에서 비롯된 전략이다.

$\begin{cases} A_{t}=\underset{a}{armax} \;\ Q_{t}(a), with \;\ prob \;\ 1-\epsilon \\others, \;\ with \;\ prob \;\ \epsilon \end{cases}$

3. Optimistic initial value

세번째 전략은, exploration도 좀 해보자는 기본 아이디어는 $\epsilon$-greedy policy랑 동일하다. 단 차이는 exploration 수행 확률로 $\epsilon$을 따로 부여하지는 않고 모든 $a$에 대하여

엄청 큰 초기 기댓값을 부여해 exploration을 강제한다.

$Q_{1} = M \;\ \forall \;\ a$

이렇게 모든 $a$에 Large $M$을 준다는 것은 exploration을 전반적으로 해보겠다는 의도의 반영이다. 왜냐? 일단 어떤 행동을 해보면 기댓값이 떨어질 테고, greedy policy에 따라 아직 $M$이 살아있는 $a$들을 사이사이에 시도해볼 것이기 때문이다.

이 반복 과정을 통해 가장 기댓값이 높은 행동을 우리는 찾을 수 있지 않겠냐는 발상인 것이다.

이렇게 세 전략을 소개했고, 이것들 중 전략을 선택했다면

우리는 실제로 action을 취하면서 결과를 보고 기댓값을 계속 업데이트 할 수 있다. 앞으로 얻을 $n+1$번째 시점에 대한 기댓값은 $n$번째까지 얻은 보상들의 산술평균으로 볼 수 있다.

$Q_{n+1}=\sum^{n}_{i=1}R_{i} \times \frac{1}{n}$

같은 의미로, 이 값은 $n$번째 보상과 $n-1$번째까지의 보상들의 산술평균으로 볼 수도 있다.

$=\frac{1}{n}\big(R_{n}+(n-1)\frac{1}{n-1}\sum^{n-1}_{i=1}R_{i}\big)$

이런 식의 대충 논리로 대충 계속 분해하다보면 어느 순간 아 내가 지금 뭐하고 있는 거지?ㄷ라는 현타가 올 수 있다.

컴퓨터한테 시키면 된다지만 무한 경쟁 시대에서는 컴퓨팅 자원과 연산 속도 역시 소중하다니까(...) 아래와 같은 유도 과정을 거쳐 마지막 식으로 산식을 간소화할 수 있다.

$=\frac{1}{n}\big(R_{n}+(n-1)\frac{1}{n-1}\sum^{n-1}_{i=1}R_{i}\big) \\ =\frac{1}{n}\big(R_{n}+(n-1)Q_{n}\big)\\=\frac{1}{n}\big(R_{n}+nQ_{n}-Q_{n}\big)\\=Q_{n}+\frac{1}{n}\big[R_{n}-Q_{n}]$

위와 같이 우리는 기존 $n-1$번째 시점에서 우리가 일고 있었던 정보인 $Q_{n}$과, $n$번째 시점에서 새로 알게 된 정보인 $R_{n}$과 $Q_{n}$의 차이를 더함으로써 기댓값 $Q_{n+1}$을 예측할 수 있다.

물론, 새로 알게 된 정보의 반영 비중은 절대적이라고 볼 수는 없기 때문에 이제까지의 시점들의 개수 $n$으로 나눠 준 채 곱해야 한다.

여기까지 이해했다면, 우리는 보상을 최대화할 수 있는 전략도 대충 세웠고 정보도 업데이트할 수 있는 방법도 알았다.

그런데, 이제까지 논리는 $q_{*}(a)$는 변하지 않는다는 stationary를 가정한다. 문제는 세상이 그리 말랑말랑하지 않다는 거ㅎ

도박장 사장 응수형은 캐쉬 방어를 위해 bandit의 $q_{*}(a)$를 조정할 수 있고 시간이 지남에 따라 $q_{*}(a)$ 자체가 달라질 수 있다.

따라서 우리의 새로운 정보에 얼마나 가중치를 줄지를 $\alpha$ 파라미터로 볼 수 있고 Non-stationary 가정 하에서는 정보 업데이트 산식은 아래와 같이 바뀐다.

$Q_{n+1} \doteq Q_{n}+\alpha\big[R_{n}-Q_{n}\big]\\=(1-\alpha)^{n}Q_{1}+\sum_{i=1}^{n}\alpha(1-\alpha)^{n-1}R_{i}$

이때 $\alpha \;\ in \;\ (0,1)$이며 확률변수일 수도 있다. 다음 편에서는 실제로 Python으로 Bandit을 구현해보고자 한다.

참고: SUTTON, Richard S.; BARTO, Andrew G. Reinforcement learning: An introduction. MIT press, 2018.
사사: 숭실대학교 산업정보시스템공학과 강창묵 교수님.