brunch

매거진 인공지능 1학년

라이킷 29 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by Chris송호연 Jan 06. 2018

멀티 암드 밴딧(Multi-Armed Bandits)

심플하고 직관적인 학습 알고리즘

강화학습의 정통 교과서라할 수 있는 Sutton 교수님의 Reinforcement Learning : An Introduction 책을 읽어보자. 챕터 1에서는 앞으로 다룰 내용에 대한 개요가 나오며, 챕터 2부터 본격적으로 기초 이론을 다루게 된다.

챕터 2의 제목이 바로 멀티 암드 밴딧(Multi-armed Bandits, 이하 MAB)이다. 사실, MAB는 강화학습으로 분류되지 않는다. 그럼에도 불구하고, 강화학습 책에서 첫번째 알고리즘으로 소개된다는 것은, 그 나름의 의미가 있다고 생각한다. 내가 생각하는 몇 가지 이유를 적어보겠다.

- 강화학습을 공부하기 위한 기초 중의 기초다

- 강화학습의 핵심 아이디어 중 하나인 탐색과 활용(Exploration & Exploitation)을 다루고 있다

- 이해하기 쉽다

- 엄청나게 유용하다

그리고, 필자가 이 알고리즘에 대해 글을 쓰기로 한 것은 실제 비즈니스 어플리케이션에서 상당한 성과를 거두고 있는 알고리즘이기 때문이다. MAB는 아주 간단한 알고리즘인데 상당히 눈에 띄게 성능을 개선시켜준다.

멀티 암드 밴딧(Multi-Armed Bandits)의 역사

우선, MAB를 이해하기 위해선 MAB의 역사를 알아둘 필요가 있다.

옛날 옛날에, 슬롯머신으로 엄청나게 흥행을 한 카지노가 있었다. 이 카지노에서는 오로지 슬롯머신만으로 장사를 했다. 그리고, 전 세계의 다양한 슬롯머신 기계들을 구비해놓았기에 고객들은 자신의 입맛에 맛는 슬롯머신으로 게임을 즐길 수 있었다.

그러다가, 카지노의 고객들은 유독 특정 슬롯 머신의 수익률이 좋다는 사실을 경험적으로 알게 되었다. 그리고 한번 대박이 터진 슬롯머신은 한동안 수익률이 좋지 않다는 사실로, 고객들은 같은 브랜드의 슬롯머신이라도 승률이 시간대에 따라 조금씩 다르다는 사실을 알게 되었다.

어느날 똑똑한 수학자가 이 카지노에 방문을 했다. 이 수학자는 문득 "이 슬롯머신에 어떻게 투자하면 최적의 수익을 얻을 수 있을까?"라는 생각을 한다.

멀티 암드 밴딧은 카지노에서 슬롯머신 투자를
최적화하기 위해 만들어진 알고리즘이다.

다시 한 번 정리를 해보겠다.

N개의 슬롯머신이 있다. 각각의 슬롯머신은 수익률이 다르다. 그런데, 당장 나는 각 슬롯머신의 수익률을 알지는 못한다. 여기서 내 돈을 어느 슬롯머신에 걸고 슬롯머신의 암(손잡이)을 내려야 돈을 제일 많이 벌 수 있을까? 여기서 슬롯머신이 밴딧(Bandit)이고, 슬롯머신의 손잡이가 암(Arm)이다. 다양한 슬롯머신이 있는데 내 돈을 어디에 걸고 손잡이를 내려야 하나? 마지막으로, 카지노에는 여러 개의 슬롯머신이 있기 때문에, 이 문제의 이름은 Multi-Armed Bandits가 된다.

오! 대박! 돈 될 거 같은 알고리즘이네!

MAB는 그 탄생 스토리에 걸맞게, 상당히 Profitable한 알고리즘이다. 이 쯤 되면, 사장님들의 귀가 솔깃해지셨을 것이다. 자, 이제 이 알고리즘에 대해 본격적으로 공부해보자.

탐색과 활용(Exploration and Exploitation)

멀티 암드 밴딧(MAB)에서 핵심 문제는 탐색과 활용(Exploration and Exploitation)이다. 이 한가지 문제를 잘 풀어내는 것만으로도 상당한 수의 비즈니스 문제를 해결할 수 있다.

예를 들어서 이야기해보겠다. 여러분은 오늘 카지노를 방문했다. 3가지 슬롯 머신 기계를 동시에 플레이 한다. 여러분의 이제 돈을 벌기 위한 전략을 수립한다.

전략1. greedy:
한 번씩 플레이 한 후, 점수 좋은 슬롯 머신에 몰빵

한 번씩 플레이 한 후, 돈을 가장 많이 딴 슬롯 머신에 모두 투자한다.

3대의 슬롯머신 중에 결과가 이렇게 나왔다고 치자.

슬롯머신1(Arm1): 1000원

슬롯머신2(Arm2): 0원

슬롯머신3(Arm3): 500원

"그래, 슬롯머신1이 최고구나! 슬롯머신1에 모두 투자해야지!"

상식적으로 생각해보자. 이 게 맞는 전략일까? 초등학생이라도 이 정도 전략에 문제가 있다는 건 잘 알 것이다. 여기서 문제는 무엇일까? 한 번씩만 테스트 했다는 점이다. 탐험(Exploration)이 충분히 이루어지지 않았다.

기본적으로 슬롯머신은 확률 게임인데, 단 한 번의 플레이 만으로 슬롯머신의 가치를 판단한다는 것 자체가 문제다. 탐험을 충분히 하지 않았기에 이 전략은 좋지 않다.

이 전략을 바로 greedy 알고리즘이라고 한다.

이 슬롯머신으로 얻은 보상의 합 / 전체 슬롯머신 시도 횟수

기대 보상을 최대로 만들어주는 슬롯머신을 선택

전략2. 입실론 그리디 e-greedy:
동전을 던져서 윗면이 나오면 점수 좋았던 슬롯머신,
뒷면이 나오면 랜덤으로 선택

탐험이 부족했던 전략1을 수정한 전략이다. 바로 일정한 확률로 랜덤으로 슬롯머신을 선택하도록 한다. 동전의 앞면이 나올 확률은 50%다. 50%의 확률로 greedy 알고리즘으로 경험상 성능이 좋았던 슬롯머신을 선택하고, 50%의 확률로 동전 뒷면이 나오면 슬롯머신의 성능과 상관없이 랜덤으로 슬롯머신을 고른다.

이 알고리즘을 epsilon-greedy(e-greedy, 입실론 그리디) 알고리즘이라고 부른다. 여기서 동전의 앞면이 나올 50%의 확률이 입실론(epsilon)이라는 하이퍼파라미터다.

저번에 슈퍼마리오 강화학습 2편에서 Deepmind의 DQN이 바로 이 입실론 그리디 알고리즘으로 탐험을 했다. e-greedy 알고리즘은 심플하면서도 강력한 알고리즘이다.

Reinforcement Learning Chapter2. - Richard Sutton

전략3. UCB(Upper-Confidence-Bound):
좋은 수익률을 보이며 최적의 선택이 될 가능성이 있는 슬롯머신을 선택한다.

전략2는 최적의 슬롯머신을 찾기 위해 랜덤으로 탐험을 한다. e-greedy 알고리즘이 우리가 지금까지 배운 알고리즘 중에선 최고의 성능을 보일 것 같다. 하지만, 탐험을 할 때 꼭 랜덤이어야만 할까? 좀 더 합리적으로 탐험을 할 수 없을까?

우리가 원하는 것은 진흙 속에서 숨겨진 보석을 찾는 것이다.

숨겨진 보석을 찾기 위해선, 탐험!을 해야 한다. 슬롯머신이 최적이 될 수 있을만한 가능성을 수치로 계산해서 가장 가능성이 있는 슬롯 머신을 선택하면 어떨까?

여러분의 가능성에 투자합니다!

"아직은 좋은 성능을 보여주진 못했지만, 왠지 더 시도해보면 잘 할 수 있을거 같아!"

UCB 알고리즘에서 다음 Action을 선택하는 알고리즘은 아래 수식으로 표현할 수 있다.

UCB 알고리즘에서 Action 선택 알고리즘

UCB 알고리즘을 기존의 전략1. greedy 알고리즘과 비교해보겠다.

greedy 알고리즘

Qt(a) 오른쪽에 빨간 네모 점선으로 표시된 수식이 추가되었다.

빨간 네모 점선에 표현된 수식이 바로, 해당 슬롯머신이 최적의 슬롯머신이 될 수도 있는 가능성이다. 가능성 혹은 불확실성이라고 할 수 있다. 여기서 c는 탐험의 정도를 조절할 수 있는 하이퍼파라미터이다. Nt(a)는 해당 슬롯머신을 선택했던 횟수다. 그리고 t는 모든 슬롯머신을 선택한 횟수의 합이다.

음, 각 변수들에 대한 설명을 들으면 생각보다 공식이 별거 없다는 것을 알게 될 것이다.

Reinforcement Learning Chapter2. - Richard Sutton

Sutton의 Reinforcement Learning 챕터 2의 마지막에서 이렇게 여러가지 알고리즘들의 성능 벤치마크 결과를 제공한다. 멀티암드밴딧 문제에서는 UCB 알고리즘을 베이스로한 알고리즘들이 제일 각광받고 있다.

이상, 멀티암드밴딧을 최대한 쉽게 풀어서 설명해보았다. 멀티암드밴딧은 대부분의 인터넷 기업들이 상당히 애용하는 알고리즘이다. 그리고 대부분의 최적화 문제에 있어서 Fit이 잘 맞는 알고리즘이라 볼 수 있다. 구현 자체도 어렵지 않기 때문에, 스타트업에서도 활용하기에 어려움이 없을 것이다.

음, 아직도 어디에 쓸 지 감이 안오시는 분들을 위해 부연설명을 해보겠다.

IT업계에 계신다면 A/B 테스트는 알고 있을거라 생각한다.

멀티암드밴딧(MAB)는 A/B테스트 전략의 진화된 버전이라 볼 수 있다.

A/B 테스트를 하면 몇 가지 문제가 있다.

- 테스트를 하는 데 오래걸리고 비용이 많이 든다.

- A/B 테스트를 할 때 A안이 훨씬 좋았다면 테스트 기간 동안엔 B안으로 인해 결국 손해를 보게 된다.

- A/B 테스트를 할 때는 A안이 좋았는데 일주일 지나니 B안 반응률이 더 좋아졌다.

이런 문제들에 멀티암드밴딧을 사용하면 문제가 말끔이 해결된다. 일일이 설명하지는 않겠다.

A/B 테스트가 기본이라 배웠던 마케터, 기획자, 개발자, 그리고 사장님들에게 멀티암드밴딧(MAB)은 엄청나게 유용한 알고리즘이다. 그리고, 멀티암드밴딧 알고리즘은 강화학습의 시작일 뿐이다!

즉, 강화학습을 저와 같이 공부하러 Naver에 지원하세요- 추천 필요하시면 이력서와 함께 이메일 주세요!

chris.ai@navercorp.com

읽어주셔서 감사합니다.