[Part 1] Multi-armed Bandit

포스팅에 앞서 Reference의 contents를 review하는 글임을 밝힙니다.

이번 포스팅에서 다룰 예제는 강화학습의 Multi-armed bandit algorithm에 대해 다루겠습니다. 원문에서는 Two-armed bandit이라는 제목을 달았는데, 저는 Multi-armed bandit(이하 MAB)가 조금 더 알려진 이름이고 실제로 실습 code도 2개 이상의 arm이 존재하는 slot machine을 다루기 때문에 원문과 다른 제목으로 바꾸어 달았습니다. 

MAB algorithm은 A/B testing을 보완한 algorithm입니다. 앞부분에 MAB에 대한 배경설명으로, A/B testing에 대해 간단히 알아보고 그 이후에 MAB algorithm에 대한 설명과 code로 구현한 것을 소개하겠습니다. 추가로, 관련 문제를 푸는 여러 algorithm에 대해서도 소개하겠습니다. 

---

A/B Testing 

 Concept

 A/B Testing은 주로 웹 서비스에서 그 효과성을 증명하기 위한 방법으로 사용하였습니다. 예를 들어, 홈 페이지를 renewal한다고 했을 때, 홈 페이지 visitor들을 임의의 두 그룹으로 나누어 각각 다른 시안이 적용된 페이지를 보여주고 반응을 정량적으로 측정하여 의사결정을 내리는 방법입니다. PC게임의 CBT나 Test server를 운용하여 user들의 feedback을 받는 것처럼 최근에는 모바일 앱 특히 모바일 게임에 많이 적용하고 있습니다. 어떤 것이 더 높다고 판단하기 위해서는 정량적인 지표가 필요한데, 웹 사이트의 경우에는 re-visit rate나 구매전환율 그리고 게임같은 경우는 신규가입율 등을 삼기도 합니다.

image source : https://vwo.com/ab-testing/

< Fig1. A/B Testing and Measurement >

 Disadvantages

 하지만 이러한 A/B testing에는 치명적인 단점이 존재하는데, '특정 시점에서 testing한 결과가 언제까지 유효한가'?'입니다. 세상은 계속 변화하고 하루가 다르게 발전하고 있습니다. 그에 걸맞춰 소비자들의 눈도 달라지고, 정보를 얻는 속도도 빨라지고 있습니다. 그렇다면 이에 대응하기 위해 주기를 짧게하여 자주 testing을 하려 한다면 비용대비 큰 효과를 기대하기어려울 수 있습니다. 주기가 너무 짧다면 변화하기도 전에 비용을 낭비하는 셈이고 주기가 너무 길다면 변화를 감지하고 따라갈 수 없습니다. 게다가 만약, 새롭게 도입한 방법이 기존의 방법보다 효과가 적다는 것이 testing 기간에 초기에 발견이 된다면, testing이 마치기 전까지 어쩌면 희망고문 때문에 계속해서 손실을 감수해야합니다.  

---

Exploration and Exploitation 

 비용 문제를 차치하고 Testing을 주기적으로 하면 변화에 대해 더 민감하게 잘 반응할 수 있습니다. 이미 알고 있는 최적의 방안을 얻었음에도 어느 정도 틀릴 수 있다는 여지를 두고 계속해서 실험하는 것을 Exploration이라고 합니다. 반면에 최적의 방안을 얻고나서 이를 계속 채택하여 최대의 이익을 창출하는 것을 Exploitation이라고 합니다. 이 둘은 어느 한쪽을 극대로 추구했을 때, 최대의 이익을 추구할 수 없는, 그렇다고 이 둘을 동시에는 극대로 추구할 수 없는 trade-off관계에 있습니다. 이러한 trade-off를 효과적으로 분배하는 문제를 Multi-armed bandit problem이라고 합니다.

 n-armed bandit은 n개의 lever가 있는 슬롯머신을 뜻합니다. 왜 Exploration and Exploitation 문제에 이런 이름이 붙여졌을 까요? 한 player에게 자신의 돈을 투자하지 않고 특정 시간동안만 무료로 여러 arm이 존재하는 슬롯머신을 이용할 수 있는 기회가 주어졌다고 생각해보겠습니다. 각각의 arm이 주는 reward는 모두 다르고, 한 번에 한 arm을 당길 수 있습니다. 제한된 시간동안 player가 가장 큰 이익을 취하기 위해서는 택해야하는 전략(강화학습의 policy)을 찾는 것이 이 문제의 핵심입니다. 

 만약 Player가 하나의 arm을 당겨 reward를 관측하고 그 arm만을 계속해서 선택할 수도 있습니다. 하지만, 이보다 더 큰 reward를 주는 arm이 존재한다면 이는 목표를 달성했다고 할 수 없습니다. 그렇다면, 모든 arm을 관측하여 reward를 확인하고 maximum reward를 주는 arm을 찾아서 이를 계속 선택하는 방법이 있습니다. 하지만 제한된 기회에서 모든 arm을 탐색하기에는 제약이 있고, 정작 maximum reward arm에 쓸 기회를 다른 arm의 reward를 확인하는 데에 쓸 수가 있습니다. 이때, 기존의 관측한 결과를 통해서 얻은 결과를 통해서 가장 좋은 arm을 선택하는 것을 Exploitation, 그리고 새로운 정보를 위해 해보지 않은 arm을 선택하는 것을 Exploration이라고 합니다. 앞서 예를 든 A/B testing도 이 Multi-armed bandit problem으로 정의됩니다. 선택지가 A/B 두 가지가 아니라 여러 개일 때, 그룹 당 하나의 시안을 보여줄 수 있기 때문에 해당 제약조건 하에 가장 좋은 시안을 testing하는 실험을 최적화하는 문제가 됩니다

Multi-armed Bandit Problem

 MAB Problem은 매우 다양한 variation들이 존재합니다. reward가 delayed reward로 주어질 수도 있고, reward가 주어지는 추가적인 조건(conditional reward)이 덧붙여질 수 있습니다. 하지만 이 글에서 다룰 문제와 실습 code는 아래와 같이 단순한 모델만 고려하겠습니다.

ㆍConstraints 

1) 각 arm은 각기 다른 reward를 제공한다

2) 제한된 시간 내에 제한된 횟수만큼 arm을 이용할 수 있다.

3) 한 번에 하나의 arm을 당길 수 있다.

ㆍObjective : 정해진 시간 내에 총 reward를 maximize하는 policy를 찾는다

 ε-greedy

 ε-greedy algorithm은 Exploitation and Exploration이 가장 직관적으로 반영된 algorithm입니다. concept은 ε의 확률로 random한 머신을 고르고, (1 - ε)의 확률로 기존에 관측한 값을 중 가장 좋은 머신을 선택하는 것입니다. 따라서 ε term의 값을 얼마를 취하느냐에 따라서 exploitation을 많이 줄 것인지, exploration을 많이 줄 것인지 선택하게됩니다. 이 algorithm을 반영한 code입니다. code에 대한 설명은 주석으로 대체하겠습니다.

이 algorithm의 문제점은 만약, 관측 시간이 적다면 empirical mean가 optimal value에 근사조차 하지 않을 수 있습니다. 하지만 충분한 시간이 흐른 뒤에 어느 정도 시간이 지나서 optimal 머신을 찾았다고 하더라도 계속해서 Exploration을 해야하기때문에 optimal 값으로 다가가는 것에 ε의 확률만큼 계속 break가 걸립니다. 심지어 ε의 확률의 Exploration동안 탐색하지 못하는 머신도 존재할 수 있습니다. 

 UCB

 UCB algorithm은 현재 empirical mean이 가장 좋은 것만에 전체 관측 횟수(n)와 해당 머신이 선택된 횟수(ni)를 반영한 식의 upper confidence bound(UCB)를 선택하는 algorithm입니다. empirical mean 뒤에 더하는 식에 따라 다양한 version이 있는데 여기서는 UCB1에 대해서만 다루겠습니다. UCB1은 아래와 같습니다. 

머신 i를 고를 때, empirical mean에 더하여 추가로 score가 붙었는데, 이 score는 관측 횟수가 적은 머신에 더 부여하겠다는 것입니다. 처음에는 n과 ni의 값이 작기 때문에 empirical mean이 좋은 머신 중에서도 관측 횟수가 적은 머신을 선택하다가 시간이 어느 정도 흐른 뒤에는 덧붙여진 점수가 비중이 적어져(emp. mean은 leaner-scale이고 두 번째 항은 sqrt(log)-scale이기때문에) empirical mean이 좋은 머신을 고르게 됩니다. 하지만, 결국 empirical mean에 따라 값이 달라지기 때문에 optimal을 위해서는 모든 머신에 대한 reward를 알아야한다는 맹점이 존재합니다. 

 Thompson Sampling

 Thompson sampling은 최근에 google에서 사용하고 있으며, 좋은 performance를 나타내어 각광받고 있는 algorithm입니다. 간단히 말씀드리자면, cumulative rewards 를 최대로 하는 action을 찾는 문제를 몇 가지 condition을 추가하여 Bayes' Thm.으로 MAP로 정의하는 것입니다. t시점의 context xt상에서 관측한 (at, rt)와 rt가 따르는 분포의 parameter θ 로 likelihood function : Pr[ rt | at, xt, θ ] 을 정의하면 다음을 max로 하는 θ 값을 찾는 MAP 문제가 됩니다.

여기서 D = {(x; a; r)} 으로 past observations입니다. 

 이 때, 우리가 매 t시점마다 action을 했을 때의 reward의 Expectation을 다음과 같이 쓸 수 있고,

이를 maximize하는 action을 a*라고 할 때 우리는 다음과 같이 쓸 수 있습니다.

이와 같은 수식을 통해 매 t시간에서 전체 parameter에 대해 구한 Expectation reward를 maximize하는 action을 선택하자는 것이 Thompson sampling의 목적입니다. 이러한 방법을 적용하면 한 번에 하나의 슬롯머신을 택하는 constraint 없이 여러 개의 슬롯머신을 선택할 수 있는 다소 복잡한 문제를 다룰 수 있게됩니다. Thompson sampling은 저도 처음 다루는 내용이기에 웬만하면 있는 자료들을 그대로 이해하여 다루었습니다.

마치며

 이번 MAB문제는 하나의 machine에 여러 arm이 달린 문제이기 때문에, state가 없이 action만으로 reward를 받을 수 있습니다. 다음 포스팅은 이에 state 개념이 추가된 Part 1.5 Contextual Bandit에 대해 포스팅하겠습니다.

오탈자나 잘못 언급된 부분이 있으면 댓글로 지적해 주세요 :)

Reference

[1] https://medium.com/@awjuliani/super-simple-reinforcement-learning-tutorial-part-1-fd544fab149

[2] http://ishuca.tistory.com/392

[3] http://sanghyukchun.github.io/96/

[4] http://www.ecogwiki.com/A-B_Testing%EC%9D%98_%EB%8B%A8%EC%A0%90%EA%B3%BC_%EA%B0%9C%EC%84%A0%EC%95%88

[5] https://en.wikipedia.org/wiki/Thompson_sampling