앞서 Dynamic Programming, Monte Carlo, Temporal Difference 방법 등 Markov Decision Process (MDP) 모델을 기반으로 하는 강화 학습 알고리즘들을 살펴보았다.
이번에는 MDP와는 다른 방법으로 문제를 모델링하고 해결하는 'MAB' 문제를 살펴볼 것이다.
목차
1. Multi-Armed Bandit Problem
MAB Problem이란, 여러 슬롯 머신을 모델링한 문제로 볼 수 있다. 구체적인 모델링은 다음과 같다.
- action : arm(lever) 당기는 것
- reward : payout (랜덤으로 발생하는 확률 분포를 기반으로 함)
- one-armed bandit : 슬롯 머신 하나로 게임 진행하는 경우
- multi-armed bandit (k-armed bandit) : 슬롯 머신 k개로 게임 진행하는 경우
게임의 목적은 가장 좋은 reward를 주는 확률 분포를 찾는 것이다.
time step \(t\)에서 Agent는 action \(a_t\)를 하고, reward \(r_t\)를 받는다.
이때 arm의 value \(Q(a)\)는 average reward, 즉 다음 식으로 나타낼 수 있다.
\(Q(a) = \frac{Sum \; of \; rewards \; received \; from \; the \; arm}{Total \; number \; of \; times \; the \; arm \; was \; pulled} \)
그리고 Optimal arm \(Q(a^*)\)는 위 식으로 구한 \(Q(a)\)의 최댓값일 것이다.
\( Q(a^*) = \max Q(a)\)
이에 따라 arm을 당기는 횟수, 즉 cost를 최소화 하면서 optimal arm을 찾는 것이 최종 목적이며, optimal arm을 찾을 때 exploration-exploitation dilemma가 발생하게 된다. (새로운 머신을 explore? or 기존 머신들 중 최댓값을 주는 머신을 exploit?)
Exploration-exploitation dilemma 해결 전략은 다음과 같다. 이는 MDP 모델에서도 사용 가능한 알고리즘을 포함한다.
- \(\epsilon\)-greedy policy
- Softmax exploration
- Upper confidence bound algorithm
- Thompson sampling technique
1) MAB vs MDP
Multi-armed bandit problem과 Markov decision process의 특징을 비교해보자.
Multi-armed bandit problem은 다음과 같은 특징을 갖는다.
- 레버를 당기는 action을 하면, 곧바로 reward를 받는다. 즉, state가 없다.
- 각 arm은 고정된 reward 분포를 갖는다.
- 각 arm은 독립적이다. 즉 action끼리 서로 영향을 주지 않는다.
- 가장 좋은 reward 분포를 찾는 것이 목적이다.
이제까지 배워온 Markov Decision Process는 Multi-armed bandit과 비교하여 다음과 같은 특징을 갖는다.
- State가 존재한다.
만약 MDP 관점에서 MAB 모델을 바라본다면, 다음과 같이 생각해볼 수 있다.
- 모든 state가 terminal state인 MDP
- 모든 episode의 길이는 1이며, 서로 독립적인 MDP
2. Exploration-exploitation dilemma 해결 전략
1) Epsilon-greedy Policy
MDP 모델 기반의 강화 학습 알고리즘에서 Control 문제 해결 시 많이 사용했던 전략이다.
\(\epsilon\)이라는 작은 값을 설정하고, \(\epsilon\)의 확률로 새로운 action을 exploration하고, \(1 - \epsilon\)이라는 대부분의 확률로 기존 action 중 가장 좋은 action을 exploitation한다.
MAB problem에서는 action을 선택한다는 개념을 머신을 선택한다는 개념으로 대입하면 충분히 이해할 수 있을 것이다.
2) Softmax Exploration Algorithm (Boltzmann Exploration)
\(epsilon\)-greedy policy에서는 \(epsilon\)의 확률에 해당할 때, 단순히 랜덤으로 arm을 선택했지만, softamx exploration에서는 Boltzmann 분포에 따른 확률로 arm을 선택하게 된다.
\(Q\)가 클수록 좋은 arm이므로, 선택할 확률을 높여줄 수 있다.
\(P_t(a) = \frac{exp(Q_t(a)/\tau)}{\sum_{i-1}^{n} exp(Q_i(i)/\tau)} \)
- \(\tau\) : temperature factor로, 얼마나 많은 랜덤 arm을 explore할지를 나타낸다.
- \(\tau\)가 커질수록 모든 arm이 같은 확률로 선택되며, 작아지면 높은 reward(\(Q\) 값이 큰 경우)를 갖는 arm을 선택될 확률이 커진다.
- 다시말해, \(\tau\)가 커지면 \(Q\)값의 영향을 줄이고, \(\tau\)가 작아지면 \(Q\)값의 영향을 높인다.
- 단, \(Q\)값이 0이 아닌 이상, \(P\)값이 0인 경우는 없다.
확률의 개념이기 때문에, 모든 action에 대한 \(P_t(a)\) 의 값의 합은 항상 1이고, 양의 값을 갖는다.
3) Upper Confidence Bound Algorithm
앞선 두 가지 전략에서는 확률에 기반하여 random action을 취했다. 하지만, 이러한 방법은 전혀 좋은 reward를 주지 못할 가능성이 있다. (수렴이 늦거나, 초기에는 reward가 낮지만 학습이 진행될수록 좋아질 action을 발견하지 못할 수 있다.)
따라서 Upper Confidence Bound(UCB) 알고리즘을 통해 Uncertainty 기반으로 최적성을 판단한다.
즉, 불확실성이 높을수록 긍정적인 action으로 생각해보자는 아이디어이다.
먼저, 신뢰 구간 (Confidence Interval)이라는 개념을 알아둘 필요가 있다.
신뢰 구간이란, 평균 reward 값이 존재할 수 있는 구간으로, Uncertainty의 판단 기준이 된다.
예를 들어, MAB 문제에서는 같은 arm을 여러 번 당겨본 후, 각 arm이 받는 reward의 평균 값이 가장 높은 arm을 최적의 arm으로 선정하게 된다.
만약 두 개의 arm을 당기는데, 처음 당길 때 arm1은 0.3의 reward를 주었다고 가정하자. 추가로 이때 arm1의 신뢰구간은 [0.2, 0.9]로 주어졌다.
그렇다면 arm1의 confidence interval은 0.9-0.2 = 0.7, upper confidence bound는 신뢰 구간 중 상한값인 0.9, lower confidence bound는 신뢰 구간 중 하한값인 0.2를 의미한다.
UCB 알고리즘에서는 가장 큰 upper confidence bound, 즉 가장 높은 평균 reward 합을 갖는 arm(machine)을 선택하여 explore하게 된다. 또한 매번 arm을 당겨서 reward를 받을 때마다 arm의 평균 reward와 confidence bound를 업데이트한다.
여기서 UCB가 가장 크다고 해서 항상 가장 좋은 reward를 주는 것은 아니다. 반복을 통해 confidence interval을 줄여 실제 평균값에 수렴되도록 해야 할 것이다.
UCB는 다음과 같이 계산할 수 있다.
\(\sqrt{\frac{2 \log(t)}{N(a)}} \)
- \(N(a)\) : arm을 당긴 횟수
- \(t\) : 총 round 횟수
따라서 UCB 알고리즘에서는 다음 식을 통해 arm을 선택한다.
\( Arm = \underset{a}{argmax} [Q(a) + \sqrt{\frac{2 \log(t)}{N(a)}}] \)
이때 \(a\)가 선택될 때마다 uncertainty가 줄어들 것이다.
또한 \(a\) 이외의 action이 선택될 때마다 \(t\)값은 증가하지만 \(N(a)\) 값은 증가하지 않게 되므로 uncertainty가 증가하게 된다.
그리고 t에 log값을 취하므로 라운드가 진행될수록 UCB의 분자의 증가량이 작아진다.
4) Thompson Sampling Algorithm
Thompson Sampling (TS)이란, 확률적 알고리즘이며, prior distribution(사건 관찰 전에 가정하는 확률 분포, \(\leftrightarrow\) posterior distribution)을 기반으로 진행된다.
k개의 arm에 대해 prior(가정)을 계산한다. 즉, 각 k개의 arm으로 부터 n개 sample을 취하여 k개의 분포를 계산하는 것이다. 이때 prior는 모두 독립적이며, 목표는 prior distribution을 true distribution에 가깝게 만드는 것이다.
우리의 reward는 (negative or positive)로, 두 가지의 확률 분포를 갖는다. 따라서 Bernoulli reward로 볼 수 있으며, 두 개의 positive shape parmameter \(\alpha\), \(\beta\)로 parameterize한 연속 확률 분포인 'beta distribution'을 통해 prior를 계산한다.
(예를 들어, \(\alpha\) 변수를 positive reward 받은 횟수, \(\beta\) 변수를 negative reward 받은 횟수로 설정할 수 있을 것이다.)
beta distribution에 대한 정확한 개념은 여기서 다루지 않겠다.
중요한 것은, 두 개 파라미터 (\(\alpha\), \(\beta\))만 알면 자동으로 prior를 계산할 수 있다는 점이다.
Thompson Sampling 알고리즘의 과정은 다음과 같다.
- k개 분포 각각의 값을 sampling하여 이 값들을 prior mean으로 사용한다.
- 가장 높은 prior mean 값을 갖는 arm을 선택하고 reward를 계산한다.
- 계산한 reward 값으로 prior 분포를 수정한다.
이러한 과정을 반복하면, prior distribution은 true distribution에 가까워지기 시작한다. 과정을 반복함으로써 수렴하도록 할 수 있다.
3. Applications of MAB
계속 슬롯 머신으로만 모델을 설명했는데, 이 모델을 실생활에 어디에 적용할 수 있을지 알아보자.
MAB 문제는 AB testing 문제를 대체할 수 있다.
AB testing이란, A와 B 중 무엇이 좋은지 선호도(preference)를 조사하는 문제를 말한다.
기존의 AB testing에서는 exploration과 exploitation 각각에 시간을 따로 할당하여 비효율적으로 해결했으나, 앞선 4가지 전략을 통해 exploration과 exploitation을 동시에 진행하여 효율적인 선호도 조사를 진행할 수 있다.
예를 들어, website optimization, maximizing conversion rate, online advertisement, 등의 추천 시스템에 활용된다.
1) Contextual Bandits
특히, 유저의 선호도에 따라 추천 시스템을 개인화(personalization)할 필요가 있다.
일반적인 MAB problem은 action을 수행하여 단순히 각각에 대한 reward를 받는데, contextual badit은 상황 정보(environment), 즉 state를 고려해준다.
예를 들어 advertisement banner 선호도를 조사할 때, action은 광고를 보여주는 것, state는 유저의 행동(클릭 or not), reward는 광고 클릭 횟수로 모델링하여 문제를 해결할 수 있을 것이다.
이는 특히 개인화된 추천 시스템 중에서도 'cold-start problem' 해결에 많이 사용된다.
cold-start problem이란, 사용 이력이 없는 새로운 유저에 대해서도 개인화된 추천을 가능하도록 하는 문제를 말한다.
최근댓글