MAB 문제란? - Multi-Armed Bandit (2)

앞선 글에서 MAB에 대한 정의와 대표적인 알고리즘인 greedy와 e-greedy 를 살펴보았다.

또한 Non-stationary 상태에서의 MAB 문제 해결방법에 대해서도 다루었다.

​

---

Optimistic Initial Value

우리가 다룬 대부분의 MAB 해결 방법론들은 초기 action-value 추정치가 어떤 값이냐에 따라 어느정도 영향을 받는다.

보통 이러한 상황을 'biased', 즉 편중되었다고 표현한다.

물론 현실에서는 'bias'를 나쁘게만은 생각하지 않을 뿐더러 도움이 될 때도 있지만,

bias를 허용한다는 것은 동시에 bias도 파라미터처럼 여겨져 사용자가 control해야하는 변수 내에 있다는 의미이기도 한다.

​

bias는 예상 가능한 보상의 수준을 알려주는 사전 지식으로서의 역할로도 작용하고,

탐험(exploration)에 대한 유인책으로서의 역할로도 작용한다.

예를 들어, 10-armed bandit이라고 생각했을 때 보상의 분포가 평균이 0이고 분산이 1인 정규분포를 따른다고 하자.

이 때 모든 보상의 값들을 5씩 높여 시작한다면 action후 실제 보상이 모두 초기값보다 적게 잡힐 것이고, 이에 따라 탐험을 더 하게 된다.

즉 매 순간 greedy action을 취했다고 하더라도, 매 action마다 실보상이 기대보다 낮기 때문에, 탐험의 기회를 계속해서 제공해는 셈이 된다.

​

출처 : Reinforcement Learning - An Introduction Second edition, in progress

실제로 테스트 데이터로 운영해보면 위와 같이 성능에 차이가 나는 것을 발견할 수 있다.

물론 이 결과 역시 테스트 조건을 어떻게 주느냐에 따라 다르게 나올 수 있다.

초기에 spike가 튀는 듯한 그래프를 그리는 이유는,

greedy알고리즘 특성상 실제론 bad option이지만 특정 step에서는 best일 때는 bad option임을 알 때까지 선택되기 때문이다.

실제 보상과 예상된 보상의 간차를 줄여나가는 과정이라고 볼 수 있다.

​

이러한 테크닉을 'optimistic initial value' (이상적인 초기값) 이라고 부른다. 이 테크닉은 주로 stationary 문제에서 유용하게 쓰인다.

Nonstationary한 방법에서는 유용하게 쓰이지 않을 수도 있는데,

그 이유는 언제까지나 알고리즘의 본래 특성상 탐험은 일시적인 전략이 되기 때문이다.

(greedy알고리즘은 탐험(exploration)보다는 수확(exploitation)을 선호)

---

Upper-Confidence-Bound Action Selection

action-value의 측정값에 대한 불확실성이 완전히 사라지기 전까지는 탐험(exploration)이 꼭 필요하다.

이러한 측정값의 불확실성을 반영한 알고리즘이 있는데, 바로 UCB이다.

$\combi{A}_t\ =\ \arg \max _a^{ }\left[\combi{\combi{Q}_t\left(a\right)+c\sqrt{\frac{\ln \ t}{\combi{N}_t\left(a\right)}}}\right]$At​ = argmaxa[Qt​(a)+c√ln tNt​(a)​]​

Nt(a)는 이전까지 누적하여 action a를 수행한 횟수이다. c는 탐험의 정도를 조정하는 파라미터이다.

Root 내에 있는 부분이 action a에 대한 보상의 기대값의 불확실성 정도를 나타내는 역할인데, action a의 보상 분포의 분산으로 볼 수 있다.

a가 선택되는 횟수가 많으면 많을 수록 불확실성 규모는 작아지고, 반대일수록 커진다.

자연로그를 취하는 이유는, 시간이 지날수록 값이 작아지는데, 일정 정도로 bound 되어 작아지기 때문이다.

​

이 함수를 통해 유추해볼 수 있는 바는, 이 알고리즘은 빈번하게 선택되었거나 보상 예측값이 낮은 action은 취하지 않는다는 것이다.

​

하지만 이 함수도 마찬가지로 non stationary 문제를 풀고자 할 때는 유용하게 작용하지 않을 수 있다.

---

Gradient Bandit Algorithm

지금까지는 action의 value에 대한 기대치와 그 기대치를 기반으로 action을 선택하는 이야기를 다루었다.

지금부터는 action에 대한 각 선호를 수치적으로 표현하고, 그 선호를 기반으로 action을 선택하는 이야기를 해볼 것이다.

선호는 value와는 다르게, 어떤 action이 유난히 더 많이 선택되었다고 하더라도, 그 자체가 수치적으로 동일하게 표현되진 않는다.

오로지 하나의 action이 다른 action들에 비해 선택되었다는 그 사실만이 중요한 것이다.

이 선호를 표현하기 위해 새로운 용어를 도입해보자.

​

$\Pr \left\{\combi{A}_t\ =\ a\right\}\ \doteq \ \frac{\combi{e}^{\combi{H}_t\left(a\right)}}{\sum _{b=1\ }^{\ k}\combi{e}^{\combi{H}_t\left(b\right)}}\doteq \combi{\ \ \Pi }_t\left(a\right)$Pr{At​ = a} ≐ eHt​(a) k∑b=1 eHt​(b)​≐  Πt​(a)​

파이t(a) 는 time t일 때 action a를 선택할 확률이다. 사실상 초기에는 선호가 모두 0으로 동일할테니 모든 action이 평등한 기회를 갖는다.

이는 softmax 함수와 동일하다.

​

우리는 선호를 기반으로 action을 선택할 것인데, 이 선호를 어떻게 정의하였을까?

$\combi{H}_{t+1}\left(a\right)\ \doteq \ \combi{H}_t\left(a\right)\ -\alpha \left(\combi{R}_t-\combi{\overline {R}}_t\right)\combi{\Pi }_t\left(a\right)$Ht+1​(a) ≐ Ht​(a) −α(Rt​−Rt​)Πt​(a)​

t+1일 때 action a에 대한 선호는 t 시간에 action a를 선택하고 Rt라는 보상을 받았을 때,

실제 보상과 전체 보상의 평균(baseline)을 뺀 값에 a를 취할 확률을 곱하여 선호를 업데이트한다.

알파는 양수의 step-size 파라미터이다. 만약 보상이 평균 보상보다 높을 경우 선호는 증가하는 셈이 되는 것이다.

​

선호에 대한 공식을 위와 같이 정의하게 된 배경으로는 아래와 같은 가설이 있었다.

t+1 타임에서의 action a에 대한 선호는 action을 취했을 때의 기대보상을 action a에 대한 선호로 편미분한 값에 비례하여 증가한다고 생각했다.

* Gradient ascent

$\combi{H}_{t+1}\left(a\right)\ \doteq \ \combi{H}_t\left(a\right)+\alpha \frac{\partial E\left[\combi{R}_t\right]}{\partial \combi{H}_t\left(a\right)}$Ht+1​(a) ≐ Ht​(a)+α∂E[Rt​]∂Ht​(a)​​

E[Rt]는 기대보상값이다. 위 식에서 increment effect는 기대보상에 대한 선호의 편도함수이다.

이 식을 이용하여 위 선호 공식을 도출하는 과정은 생략하도록 하겠다. 그 과정에는 일부 가정들이 필요하다.

​

책에서는 baseline과의 간차를 구하는 부분이 굉장히 중요하다고 강조하고 있다.

baseline이 있을때와 없을때의 모델 각각의 성능차를 테스트 데이터로 보여주었다.

출처 : Reinforcement Learning - An Introduction Second edition, in progress

---

Associative Search

이제는 Contextual Bandit에 대해 이야기해보자.

지금까지 이야기했던 Bandit 알고리즘들은 전부 상황에 영향을 받는다는 등의 Context 요인이 없었다.

Stationary한 상황에서는 가장 best한 action을 알아내어 고르면 되지만, 일반적으로 강화학습에서는 단일 situation이란 없다.

강화학습의 목표는 policy를 찾아나가는 것인데, 각 상황에 따라 알맞은 action을 취할 수 있어야한다.

​

associative search란 상황과 연관지어서 시행착오를 통해 best action을 찾아나가는 과정을 의미한다.

예를 들어 색깔이 변하면 보상도 변하는 slot machine이 있다고 해보자. 그 slot machine은 색에 따라 best action을 달리한다.

우리는 그럼 빨간색일 때 어떤 action이 베스트인지, 초록색일땐 어떤 action이 베스트인지 알아내야한다.

​

Contextual Bandit은 k-armed bandit문제와 강화학습 문제 사이에 위치한 성격을 띈다.

policy를 학습해나가는 과정이 강화학습과 유사한 점이고, 각 action이 단기간(immediate) 보상에 영향을 미친다는 점은 MAB문제와 유사하다.

만약 action이 다음 action의 결과에도 영향을 미쳤다면 Contextual Bandit은 강화학습과 동일한 범주였을 것이다.

---

참고도서

http://incompleteideas.net/book/the-book-2nd.html