Multi Armed Bandit
Reinforcement Learning 순한 맛
나는 회사에서 상당히 broad한 업무를 하고 있는데, 그 중 특별한 것 하나는 속해있는 팀에서 구성원이 단순히 Operation을 넘어, Data Analyst/Scientist로써 최소한의 역량을 갖추어 커리어 성장의 기회가 있기를 기대하는 목적으로 1달에 한번씩 스터디를 진행하고 있다. (번외로 아래 책 꽤 괜찮다고 생각함)
그러다가 내용중에 나도 학부때 넘어갔던 MAB가 이번에 포함 되어 있어서 한번 정리하고 넘어가려고 한다.
자 여러분은 DS다. DS로써 핵심 업무는 팀이 점심을 어느 식당에서 먹을지 결정하는 것으로, 구성원들의 높은 만족감이라는 지표를 위해 열심히 분석과 실험을 해야한다.
이쯤 되면 눈치챘겠지만 DS는 Dining Scientist다. (물론 Data Scientist 도 높은 지표를 위해 이런 저런 실험을 한다는 맥락에선 비슷하다)
그러나 큰 문제가 생겼다. 여러분이 열심히 기록해 둔 맛집 리스트가 오피스 이사로 인해 전부 무용지물이 되어버린 것이다. 즉, 데이터가 없다 !!!
근처에 있는 식당들에 대해서 리뷰들도 없기에 말 그대로 “실험”을 해야 하는 상황이다.
자 여기서, 전제를 몇가지 하고 이야기를 이어가자,
- 식당은 5개가 있으며 각각 궁극적으로 N(7, s1), N(13, s2), N(10, s3), N(15, s4), N(12, s5) 만큼의 만족도 분포를 나타내지만, 지금은 알 수 없는 상황이다.
- 이번 오피스에는 1년만 있을 예정이다. (대충 300일이라고 하자)
결과를 모르는 상황에서 여러가지의 선택지 중 최고의 선택지를 골라, 높은 퍼포먼스를 보이기 위해서 할 수 있는 것은 크게 2개로 구성된다.
Exploration
첫번째로 할 수 있는 것은. 선택지들을 동일한 비중으로 실험 하는 것이다.
이 경우 5개의 식당을 각각 60일만큼 가는 것이고, 그 결과 7*60 + 13*60 + 10*60 + 15*60 + 12*60 = 3420 이라는 총 만족도를 얻게 된다.
이론상, 가장 높게 기대 할 수 있는 총 만족도는 4번째 식당만 300일 내내 갔을때 얻을 수 있고, 값은 15*300 = 4500이다.
랜덤하게 배치 하는 것으로 이미 우리는 1080 만큼의 점심시간을 손해봤다.
Exploitation
한번의 인생 시뮬레이션을 통해 점심시간을 아쉽게 보낸 여러분은, 더 만족스러운 점심시간을 위해 고민 해본 결과, 다음과 같은 생각을 하게 된다.
“처음에 조금 가보고 별로인 곳은 안가면 되지 않을까?”
그래서 10번씩 먼저 식당을 가보기로 했다. 그 결과, 50번만큼의 데이터는 2번째 식당이 괜찮았음을 보여주었고 이를 토대로 남은 기간동안 2번만 주구장창 가기로 한다. (당연하지만 s의 존재로 인해 식당마다 그날의 퍼포먼스는 조금씩 다를 수 있다)
이 결과 기대할 수 있는 총 만족도는, 7*10 + 13*260 + 10*10+15*10+12*10 = 3820이다.
무작정 랜덤하게 가는 것 보다는 400만큼 행복해 졌지만 여전히 Best는 아니다.
e-greedy strategy
이 방법은 앞의 2 인생 시뮬레이션을 통해 배운 것을 적절히 섞는 방법이다. 그럼 여기서 등장해야 하는 질문, “어떻게 섞을까?”
이를 위해 새로운 epsilon 이라 하는 파라미터가 등장한다. 그냥 e라고 쓰겠다
e는 1과 0 사이의 값, 즉 확률로써 다음 액션을 Exploration을 할지, Exploitation을 할지를 고르는 역할을 한다. (정의하기에 따라 바뀔 수 있겠지만, Exploration을 할 확률이라고 하자)
만약 e가 0이라면 항상 Exploitation을 한다는 뜻으로, 기존에 갔던 식당들중 제일 기대치가 높은 식당만 가겠다는 뜻이며, 반대로 e가 1이라면 매번 랜덤한 식당을 가겠다는 의미를 갖는다.
보통 e는 0.1 의 값으로 사용한다. 즉 10%의 확률로 랜덤한 식당을 가 새로운 데이터를 얻고, 90%의 확률로 기존에 제일 높은 퍼포먼스를 보인 식당을 방문한다. 그 결과 30일 랜덤 방문 + 270일 높은 식당 방문으로
( 7*6+13*6+10*6+15*6+12*6 ) + (15*270) = 4392 . 꽤 best 솔루션에 근접 하게 된다.
그 외
가장 직관적이라서 e greedy를 서술하긴 했지만, 이 외에도 multi arm bandit 에는 다양한 커스텀 방법들이 있다.
- e를 점점 줄여가는 방법
- 베이지안을 적용해서 e를 변화시키는 방법
- 퍼포먼스에 따라 랜덤하게 선택하는 확률을 바꾸는 방법
- Thompson sampling (퍼포먼스가 꽤 괜찮다고 한다)
등등.
그럼 마지막으로 multi arm bandit 과 테스트하면 제일 먼저 떠오르는 A/B 테스트를 비교해보자. A/B 테스트는 “실험을 잘 설계”해야 한다는 문제도 있지만 그것이 핵심 차이라기 보단, Reinforcement 처럼 dynamical하게 전략을 바꿔가면서 optimize 하는게 핵심 차이라고 생각한다.
애덤 그랜트의 말처럼 계속 변화할 수 있어야 하는 것 같다. 끝
아래 자료들은 설명이 참 잘 되어있어 해에 도움이 될 자료들이다.
