어떤 슬롯머신 이 어떤 수익 률 을 가지 는지 모를 때 , 탐색 ( Exploration ) 과 활용 ( Exploitation ) 을 적절히 사용 하 여 최적 의 수익 을 찾아내 고자 하 는 강화 학습 알고리즘 ! ​ 안녕 하 세요 , 배우 는 기계 러닝 머신 입니다 . ​ 오늘 은 추천 알고리즘 의 두 번 째 포스팅 으로 , " MAB ( Multi - Armed Bandits ) " 에 대해서 배워 보 려고 합니다 . 이 이름 의 뜻 은 여러 개 ( Multi ) 의 레버 ( Arm ) 를 가진 여러 대 의 슬롯머신 ( Bandits ) 이 라는 뜻 인데요 . ​ 이 알고리즘 의 유래 가 , 과거 카지노 에서 어떤 슬롯머신 에 게임 을 해야 최대한 많 은 수익 을 얻 어 낼 수 있 을까 ? 하 는 고민 에서 출발 했 기 때문 이 라고 합니다 . ​​ 1 . K - armed Bandits 돈 을 넣 고 슬롯 을 당겨 볼 슬롯머신 을 선택 한다고 했 을 때 를 가정 해 봅시다 . 이 문제 를 간단히 생각 해서 , 아래 그림 처럼 버튼 을 누를 때 마다 돈 을 받 는 게임 이 라고 생각 해 봅시다 . 총 1000 번 의 실행 에서 , 보상 을 최대 화 하 는 것 이 우리 의 목표 입니다 . 유감 스럽 게 도 우리 는 각 버튼 을 누를 때 마다 얼마 의 보상 을 받 게 될지 알 수 없 습니다 . ​ 이러 한 상황 에서 , 강화 학습 의 전형 적 인 플로우 를 살펴보 겠 습니다 . 우리 의 K - Armed Bandits 상황 에서 는 , 다른 복잡 한 강화 학습 문제 와 는 다르 게 환경 이 변화 하 지 않 는다는 점 에서 매우 간단 합니다 . ​ 여기 에서 Agent 는 우리 의 강화 학습 모델 입니다 . 이 Agent 가 어떠 한 액션 ( 예 를 들 면 , 버튼 2 번 을 누른다 ! ) 을 취하 면 , Environment ( 환경 ) 은 우리 에게 어떠 한 보상 을 주 게 됩니다 . ​ 간단히 말 해서 , Agent 가 선택 을 잘 했 으면 " 응 . 잘 했 어 ~" 하고 칭찬 해 주 고 , 반대 로 잘못 된 선택 을 하 면 " 응 , 왜 그거 골랐 어 ~" 하고 혼내 주 는 것 이 지요 . ​ 이러 한 과정 끝 에 , Agent 는 최종 시점 에서 최대 의 누적 수익 을 얻 기 위해 자신 의 전략 ( Policy ) 을 점점 수정 해 나가 고 , 이러 한 플로우 가 잘 구성 되 어 있 는 경우 에 최적 의 전략 을 발견 하 면서 학습 을 종료 하 게 됩니다 . ​ 앞서 말 했 던 칭찬 과 면박 은 각각 Reward 의 수치 값 으로 표현 됩니다 . 잘 했 어 ~ 는 돈 을 더 주 는 것 이 고 , 못 했 어 ~ 는 돈 을 잃 게 만드 는 것 이 지요 . ​​ 1 ) 일정 한 보상 ( Stationary Reward ) 만약 보상 이 일정 하 다면 문제 는 아주 간단 하 겠 지요 ? 가령 ① 번 버튼 은 500 원 , ② 번 버튼 은 100 원 , ③ 번 버튼 은 - 1000 원 이 라고 해 봅시다 . 그렇 다면 몇 번 의 탐색 끝 에 ① 번 버튼 이 최고 라는 것 을 알 게 될 것 이 고 , 우리 의 Agent 는 ① 번 을 남 은 기회 동안 눌러 최대 의 보상 을 얻 게 될 것 입니다 . ​ 2 ) 변칙 적 인 보상 ( Non - Stationary Reward ) 하지만 현실 은 역시 녹록 치 않 죠 . ① 번 버튼 의 보상 이 처음 에 는 500 원 이 었 다가 시간 이 흐름 에 따라 한 회 마다 - 50 원 씩 줄어들 고 , ② 번 버튼 은 100 원 이 었 다가 - 10 원 , + 20 원 , - 30 원 , + 40 원 . .. 이렇게 변화 하 고 , ③ 번 버튼 은 - 1000 원 에서 한 회 마다 500 원 씩 늘어나 는 것 처럼 보상 이 변화 할 수 도 있 을 것 같 습니다 . 이러 한 상황 을 변칙 적 인 보상 ( Non - Stationary Reward ) 라고 합니다 . 멋진 말 로 , 보상 의 분포 가 시간 의 흐름 에 따라 변화 한다고 표현 합니다 . ( Reward distribution changes over time ) 이 경우 에 는 조금 더 복잡 한 접근 이 필요 하 겠 죠 ? ​ 2 . 탐색 과 활용 ( Exploration and Exploitation ) 우리 는 제한 된 돈 을 가지 고 있 기 때문 에 , 두 가지 의 선택 을 취해야 합니다 . ​ 첫 번 째 는 " 어떤 버튼 이 얼마 의 보상 을 주 는지 탐험 해 보 기 "( Exploration ) 이 고 , ​ 두 번 째 는 " 알아낸 보상 을 바탕 으로 돈 을 뽑 아 먹 기 "( Exploitation ) 입니다 . ​ 둘 중 어느 하나 만 을 선택 해서 는 최대한 의 돈 을 버 는 시나리오 를 기대 하 기 어렵 겠 죠 . ​ 이 딜레마 를 어떻게 하 면 잘 풀어낼 수 있 을까요 ? 이제 그 방법 에 대해 알아보 려고 합니다 . ​​​ 3 . 보상 최대 화 하 기 ( Maximizing Reward ) ​ 탐색 과 활용 을 잘 절충 해서 , 보상 을 최대 화 하 는 세 가지 접근 법 에 대해 배워 보 겠 습니다 . ​​ 1 ) Greedy 알고리즘 ​ 1000 번 을 도박 할 돈 이 있 을 때 , 30 번 정도 를 ① ② ③ 번 버튼 에 각각 10 번 씩 투자 한 결과 가 다음 과 같 다고 합시다 . 이럴 때 , 오케이 , ① 번 으로 나머지 970 번 가즈 아 ! ​ 하 는 게 Greedy 알고리즘 이 라고 할 수 있 겠 습니다 . 가장 잘 나오 는 버튼 을 " 탐욕 적 으로 ( greedy ) " 몰 빵 하 는 알고리즘 이 라 greedy 라는 이름 이 붙 은 듯 합니다 . ​ 이 를 수식 으로 표현 하 면 아래 와 같 습니다 ! ​​ 잠시 창 을 나가 려는 그 손가락 을 내려 놓 으시 고 , 차근차근 제 설명 을 들 어 주 세요 . ​ 먼저 위 의 식 에서 , q *( a ) 는 a 라는 임의 의 버튼 을 눌렀 을 때 얻 는 기대 보상 입니다 . 등호 위 에 점 이 하나 찍혀 있 는 것 은 " 거의 같 다 " 라는 의미 이 구요 , 저 두꺼운 E 는 기댓값 을 , 그 안 의 내용 은 " t 시점 에서 A ( 선택 할 버튼 , Action ) 이 a 라는 버튼 일 때 의 R ( 보상 , Reward ) " 이 라는 의미 입니다 . ​ 요약 하 자면 q *( a ) 는 a 를 골랐 을 때 t 시점 에서 얻 을 기대 보상 이 라는 뜻 인데요 . 그런데 현실 에서 는 q *( a ) 를 알 지 못하 기 때문 에 , 이 를 추정 한 Qt ( a ) 를 사용 한다는 것 입니다 . 그리고 그 추정 하 는 방식 중 에 하나 를 아래 에서 소개 합니다 . ​ 이 를 Sample - Average Method 라고 합니다 . ㅎㅎ 이 식 은 이 Qt ( a ) 를 추정 하 는 방법 을 보여 줍니다 . t 기 는 현재 의 시점 , a 는 우리 가 고른 버튼 , Qt ( a ) 는 t 시점 의 a 버튼 의 진짜 보상 의 추정 치 를 의미 합니다 . ​ 맨 오른쪽 식 의 해괴 한 1 모양 은 , Indicator Function 이 라고 하 는데요 . 이 는 Ai 가 a 라는 식이 성립 할 때 1 의 값 을 , 그렇 지 않 을 때 0 의 값 을 출력 하 는 함수 입니다 . ​ 하 ㅎㅎ 말 이 정말 길 죠 . 분모 는 " t 기 전 까지 a 가 선택 된 횟수 의 총 합 " 을 , 분자 는 " t 기 전 까지 a 가 선택 되 었 을 때 보상 의 총 합 " 을 의미 합니다 . 쉽 게 말 해 a 가 뽑혔 을 때 보상 을 평균 내준 이 값 을 , a 의 진짜 보상 값 일 꺼 야 ! 라고 가정 하 는 것 이 됩니다 . ​​ 거의 다 왔 습니다 . Greedy 방식 은 다음 과 같 은 방법 으로 Action 을 선택 합니다 . 이 식 은 , 우리 가 선택 할 Action ( 즉 , 어떤 버튼 을 선택 하 는지 ) 은 아까 구한 Qt ( a ) 를 최대 로 만들 어 주 는 a 를 사용 한다 ! 라는 말 입니다 . ​​​ 2 ) ε - Greedy 알고리즘 ​ 얼핏 보 기 에 도 철 용 이 형 의 Greedy 알고리즘 방식 은 돈 을 잃 기 쉬워 보 입니다 . 단순히 30 번 의 시도 로 확신 을 해 버린다는 게 문제 인데요 . ​ 앱 실론 그 리디 알고리즘 은 , 이러 한 문제 를 조금 보완 해 줍니다 . ​ 매 번 마다 동전 을 던져서 , 앞면 이 나오 면 새로운 버튼 을 눌러 보 고 , 그렇 지 않 으면 지금 까지 나온 최적 의 버튼 을 누르 는 결정 을 한다는 겁니다 . ​ 여기 서 앱 실론 ( ε ) 은 동전 을 던졌 을 때 앞면 이 나올 확률 이 라고 생각 할 수 있 습니다 . ​​ 이런 약간 의 변칙 을 사용 함 으로써 , greedy 방식 ( 녹색 그래프 ) 에 비해 더 나 은 결과 를 낳 는다고 합니다 . ​* 변칙 적 인 보상 을 가질 때 더욱 효율 적 인 e - greedy 알고리즘 적용 을 위해 , 다음 과 같 은 방식 이 적용 되 었 습니다 . exponential decay 를 이용 한 방법 으로 생각 됩니다 . 자세 한 내용 은 교재 를 참조 해 주 세요 . ​ 3 ) UCB ( Upper - Confidence - Bound ) 알고리즘 헌데 생각 해 보 면 , 이렇게 무작위 로 하 는 방식 보다 조금 더 스마트 한 방식 이 있 을 것 같 습니다 . 그래서 등장 한 것 이 UCB 알고리즘 입니다 . ​​ greedy 방식 에서 ① 번 버튼 을 누르 는 것 을 탐욕 적 인 선택 ( greedy selection ) 이 라고 합니다 . 동전 을 던져 셋 중 다른 하나 를 고르 는 것 보다 는 , 좀 더 스마트 한 방법 을 써 보 자는 건데요 . ​ 어떻게 ? ​ 이렇게 요 ! ​ Nt ( a ) 는 t 기 이전 까지 a 가 선택 된 총 횟수 를 뜻 하 고 , ln t 는 시점 을 뜻 하 는 t 기에 자연로그 를 취한 값 을 의미 합니다 . Nt ( a ) 를 분모 에 , ln t 를 분자 에 둠 으로써 ​ a 라는 버튼 이 시간 이 많이 흘렀 는데 도 덜 뽑혀 봤 다면 , c 라는 배수 만큼 더 무게 를 준다 ! ​ 라는 전략 을 표현 하 는 것 입니다 . ​ 요약 하 자면 , UCB 방식 은 " 아직 안 살펴본 녀석 을 좀 더 꼼꼼히 살펴볼 거 야 . ." 정도 로 말 할 수 있 겠 네요 . ​​​ 4 ) 그 외 알고리즘 그 외 에 도 확률 적 경사 상 승법 ( Stochastic Gradient Ascent ) 을 적용 한 Gradient Bandit , Greedy 알고리즘 의 초기 에 낙천 적 인 스탠스 를 취하 게 함 으로써 열심히 모든 선택 을 탐색 하 게끔 유도 하 는 Greedy with optimistic Initialization 등 의 알고리즘 이 있 습니다 . ​ 아래 의 그림 은 교재 에 실린 성능 비교 그래프 인데요 , 색깔 별 로 각각 다른 parameter 를 의미 합니다 . ​ ​ 이상 으로 MAB 에 대해서 알 아 보 았 습니다 . 다음 시간 에 는 , 온라인 광고 마케팅 최적화 에 MAB 를 적용 한 논문 을 살펴볼까 합니다 ! ​​​​ p . s . 참고 자료 에 포함 된 Reinforcement Learning 은 pdf 파일 이 온라인 에 공개 되 었 습니다 . 하지만 제 가 공개 해도 될지 확신 이 없 어 , 공개 하 지 못한 점 양해 부탁 드립니다 . ​ 링크 가 필요 하 신 분 은 댓글 을 남겨 주 세요 . ​​​ 참고 자료 Reinforcement Learning : An Introduction - by Andrew Barto and Richard S . Sutton ​ https : / / wwiiiii . tistory . com / entry / MultiArmed - Bandit - Problem Multi - Armed Bandit ProblemMAB Multi - Armed Bandit Problem 1 . 개요 Multi - Armed Bandit ( MAB ) problem 이 란 강화 학습 에서 다루 는 분야 중 하나 로 , 여러 선택지 가 주어지 고 각 선택지 는 특정 한 확률 분포 를 따르 는 보상 을 돌려 준다고 할 때 . . wwiiiii . tistory . com ​ https : / / www . youtube . com / watch ? v = 9 LhNHK 1 ULxs & list = LLypIXWIsUMIMvCa 6 zQfOZmQ & index = 4 & t = 0 s ​ 크리스 송 님 의 간결 한 설명 에 많 은 도움 을 받 았 습니다 ! ​ https : / / brunch . co . kr / @ chris - song / 62 멀티 암드 밴 딧 ( Multi - Armed Bandits ) 심플 하고 직관 적 인 학습 알고리즘 | 강화 학습 의 정통 교과서 라 할 수 있 는 Sutton 교수 님 의 Reinforcement Learning : An Introduction 책 을 읽 어 보 자 . 챕터 1 에서 는 앞 으로 다룰 내용 에 대한 개요 가 나오 며 , 챕터 2 부터 본격 적 으로 기초 이론 을 다루 게 된다 . 챕터 2 의 제목 이 바로 멀티 암드 밴 딧 ( Multi - armed Bandits , 이하 MAB ) 이 다 . 사실 , brunch . co . kr ​​​​ p . s . 도움 이 되 었 다면 , 공감 / 댓글 부탁 드립니다 ! 누군가 에게 도움 이 되 었 다는 것 이 제게 소소 한 기쁨 이 됩니다 . ​ 잘못 된 정보 , 수정 해야 할 내용 지적 은 언제 든지 환영 합니다 !