Reference
•
최대의 이득을 찾는 전략을 학습하는 강화학습 방식의 추천 알고리즘인 MAB에 대해 살펴 봅니다.
어떤 슬롯머신이 어떤 수익률을 가지는지 모를 때,
탐색(Exploration)과 활용(Exploitation)을 적절히 사용하여
최적의 수익을 찾아내고자 하는 강화학습 알고리즘!
1. MAB(Multi-Armed Bandits)란, 여러 선택지가 있을 때 어떤 선택이 가장 큰 보상을 얻을 수 있을지 모를 때 최적의 전략을 세우기 위한 알고리즘
2. 아직 잘 모르는 선택지를 시도해보는 탐험(Exploration)과, 높은 보상을 얻을 수 있다고 알려진 선택지를 선택하는 활용(Exploitation)을 적절히 활용해야함
3. 이러한 탐험과 활용 사이를 잘 조정하기 위해, ϵ𝜖-greedy, UCB(Upper Confidence Bound) 등의 다양한 variant가 고안되었음
1. Multi-Armed Bandits이란?
•
여러개(Multi)의 레버(Arm)를 가진 여러대의 슬롯머신(Bandits)
◦
알고리즘의 유래: “과거 카지노에서 어떤 슬롯머신에 게임을 해야 최대한 많은 수익을 얻어낼 수 있을까?”
•
기술적 정의 - 아래의 세 가지의 제약이 모두 주어졌을 때의 문제 (multi-armed bandit problem)를 해결하는 알고리즘
1.
한정된 자원 상황 하에 여러 개의 상충하는 선택을 내려야하는 경우
2.
어떠한 선택이 얼마 만큼의 이득을 얼마 만큼의 편차로 제공하는지를 알 수 없을 때 (그러나 같은 선택을 여러번 내림에 따라 불확실성이 줄어들 때)
3.
이 선택들의 예상되는 최대 이득이 극대화되도록 하고자 할 때
•
타짜 철용좌가 자신의 마지막 승부를 거는 상황을 예시로 들어보자.
2. 예시 상황
무너진 줄만 알았던 마포대교를 무사히 건넌 철용좌는 마지막 재산 1,000만원을 끌어 안고 인근의 유명한 도박장에 도착했습니다. 3대의 슬롯머신이 눈 앞에 놓여있고, 기계마다 수익률이 다르게 책정되어 있다는 사실을 알게 됩니다. 여기서 우리의 철용좌가 재기를 위해 최대한의 이익을 낼 수 있는 방법은 무엇일까요?
•
여기서 철용좌는 아직 3개의 bandit의 보상을 전혀 알지 못합니다. 철용좌는 마지막 자존심을 되찾을 수 있을까요?
•
평소 머신러닝에 관심이 많던 철용좌는 이 마지막 기회를 최대한 살리기 위해, 강화학습의 기초적인 형태인 Multi-Armed Bandit 알고리즘을 적용해보고자 합니다. 그가 떠올린 기초적인 강화학습의 플로우는 다음과 같습니다. 일반적인 강화학습과는 달리, 환경이 변하지 않는다는 점에서 더욱 문제가 단순해졌습니다.
•
Agent: 우리의 강화학습 모델
•
Action: 버튼을 2번 누른다!
•
결과에 따라 Enviorment 는 보상 여부 결정
Agent가 선택을 잘 했으면 “잘했어~” 하고 칭찬 해주고,
잘못된 선택을 하면 “응, 왜 그거 골랐어~” 하고 혼내주는 것
•
Agent는 최종 시점에서 최대의 누적 수익을 얻기위해 자신의 전략(Policy)을 점점 수정해 나가고, 이러한 플로우가 잘 구성되어 있는 경우에 최적의 전략을 발견하면서 학습을 종료
•
칭찬과 면박은 각각 Reward의 수치값으로 표현
◦
잘했어: 돈을 더 줌
◦
못했어: 돈을 잃게 만듦
•
보상의 형태
1.
일정한 보상 (Stationary Reward)
•
보상이 일정하다면 문제는 아주 간단해짐
1번 버튼은 500원
2번 버튼은 100원
3번 버튼은 -1,000원
•
몇번의 탐색 끝에 1번 버튼이 최고라는 것을 알게 될 것이고, 우리의 Agent는 1번을 남은 기회동안 눌러 최대의 보상을 얻게 될 것
2.
변칙적인 보상 (Non-Stationary Reward)
•
하지만, 현실은 역시 녹록치 않다.
1번 버튼은 첫 회에 500원이었다가 시간이 흐름에 따라 한 회마다 -50원씩 줄어듦
2번 버튼은 100원이었다가 -10원, +20원, -30원, +40원…
3번 버튼은 -1000원에서 한 회마다 500원씩 늘어남
•
보상의 분포가 시간의 흐름에 따라 변화한다고 표현 (Reward distribution changes over time)
•
어떻게하면 이렇게 알 수 없는 보상을 정확히, 최소한의 손실로 알아낼 수 있을까요?
•
이를 위해, 탐색과 활용(Exploration and Exploitation) 전략을 취하게 됩니다.
3. 탐색과 활용 (Exploration & Exploitation)
•
우리의 철용좌는 단 1,000번 만을 시도할 돈만 가지고 있기 때문에, 제한된 기회 내에서 최대한의 수익을 얻어내야 합니다.
•
그런데, 3개 중 1개의 가장 우수한 수익을 주는 슬롯머신이 있다고 할 때,
◦
3개 중 어떤 슬롯이 가장 많은 이득을 줄 지 알 수 없는 상황에서 한가지에 모두 쏟아버리기에는 위험할 것 같고 (exploitation only),
◦
또 반대로 계속 3개를 골고루 골라버리기에는 최대의 이득을 못 누릴 것 같습니다. (exploration only)
•
여기서, 두 번째 전략을 탐험(Exploration), 첫 번째 전략을 활용(Exploitation) 이라고 합니다
1.
탐험(Exploration): 어떤 버튼이 얼마의 보상을 주는지 탐험해보기
2.
활용(Exploitation): 알아낸 보상을 바탕으로 돈을 뽑아먹기
•
이 두 가지 전략을 적절히 섞어서 쓰는 것이 필요할텐데, 어떻게 풀어낼 수 있을까요? 이제 그 방법에 대해 알아보겠습니다.
4. 보상 최대화 알고리즘
•
탐색과 활용을 잘 절충해서, 보상을 최대화하는 세 가지 접근법에 대해 배워보겠습니다.
4.1. Greedy 알고리즘
그게 좋단 말이지? 묻고 더블로 가!
•
다시 철용좌의 이야기로 돌아가 봅시다. 1,000번에 걸쳐 슬롯을 돌려 볼 돈이 있을 때, 30번 정도를 ① ② ③ 번 버튼에 각각 10번씩 투자한 결과가 다음과 같다고 합시다.
•
이럴 때, 오케이, ① 번으로 나머지 970번 가즈아! 하는게 Greedy 알고리즘
•
즉, 가장 수익이 잘 나오는 버튼을 “탐욕적으로(greedy)” 하게 선택하는 알고리즘
•
수식
◦
𝑞∗(𝑎)는 𝑎 라는 임의의 버튼을 눌렀을 때 얻는 기대 보상
◦
등호 위에 점이 하나 찍혀 있는 것은 “거의 같다” 라는 의미이구요 (is defined as),
◦
두꺼운 E(𝐸) 는 기댓값
◦
그 안의 내용은 “𝑡 시점에서 𝐴(선택할 버튼, Action) 이 𝑎라는 버튼일 때의 𝑅(보상, Reward)”
•
수식을 요약하면, 𝑞∗(𝑎)는 𝑎를 골랐을 때 𝑡 시점에서 얻을 기대 보상
•
그런데 현실에서는 𝑞∗(𝑎)를 알지 못하기 때문에, 이를 추정한 𝑄𝑡(𝑎)를 사용한다는 것
•
𝑡기는 현재의 시점, a는 우리가 고른 버튼, 𝑄𝑡(𝑎)는 𝑡시점의 𝑎버튼의 진짜 보상의 추정치를 의미
•
맨 오른쪽 식의 1 모양은 Indicator Function
◦
이는 𝐴𝑖가 𝑎라는 식이 성립할 때 1의 값을, 그렇지 않을 때 0의 값을 출력하는 함수
•
정리하자면, 분모는 “𝑡기 전까지 𝑎가 선택된 횟수의 총 합”을, 분자는 “𝑡기 전까지 𝑎가 선택되었을 때 보상의 총 합”을 의미
◦
쉽게 말해 𝑎가 뽑혔을 때 보상을 평균 내준 이 값을, 𝑎의 진짜 보상값일거야! 라고 가정하는 것
•
Greedy 방식은 다음과 같은 방법으로 Action을 선택
◦
우리가 선택할 Action(즉, 어떤 버튼을 선택하는지)은 아까 구한 𝑄𝑡(𝑎)를 최대로 만들어 주는 𝑎를 사용한다!
4.2. 𝜖 - Greedy 알고리즘
묻고 더블로 가! 긴 하는데 가끔씩 살펴보긴 하자.
•
얼핏 보기에도 철용이형의 Greedy 알고리즘 방식은 돈을 잃기 쉬워보입니다. 단순히 30번의 시도로 확신을 해버린다는게 문제인데요.
•
𝜖(앱실론) - Greedy 알고리즘은, 이러한 문제를 조금 보완해 줍니다.
•
매 번마다 동전을 던져서, 앞면이 나오면 새로운 버튼을 눌러보고, 그렇지 않으면 지금까지 나온 최적의 버튼을 누르는 결정을 한다
◦
여기서 𝜖은 동전을 던졌을 때 앞면이 나올 확률
•
이런 약간의 변칙을 사용함으로써, greedy 방식(녹색 그래프)에 비해 더 나은 결과를 낳는다고 합니다
•
(+) 변칙적인 보상을 가질 때 더욱 효율적인 e-greedy 알고리즘 적용을 위해, 다음과 같은 방식이 적용
•
exponential decay를 적용한 것을 알 수 있습니다.
4.3. UCB(Upper-Confidence-Bound) 알고리즘
아직 안 살펴 본 애들을 좀 더 보면서 가자!
•
헌데 생각해보면, 이렇게 무작위로 하는 방식보다 조금 더 스마트한 방식이 있을 것 같습니다.
•
그래서 등장한 것이 바로 UCB 알고리즘
•
는 𝑡기 이전까지 a𝑎가 선택된 총 횟수를 뜻하고,
•
는 시점을 뜻하는 𝑡기에 자연로그를 취한 값을 의미합니다.
•
를 분모에, 를 분자에 둠으로써 라는 버튼이 시간이 많이 흘렀는데도 덜 뽑혀봤다면, 라는 배수만큼 더 무게를 준다! 라는 전략을 표현하는 것
•
요약하자면, UCB 방식은 “아직 안살펴본 녀석을 좀 더 꼼꼼히 살펴볼거야..”
4.4. 그 외 알고리즘
•
확률적 경사 상승법(Stochastic Gradient Ascent)을 적용한 Gradient Bandit
•
Greedy 알고리즘의 초기에 낙천적인 스탠스를 취하게 함으로써 열심히 모든 선택을 탐색하게끔 유도하는 Greedy with optimistic Initialization
•
아래의 그림은 알고리즘별 성능 비교 그래프로, 색깔별로 각각 다른 parameter를 의미
5. 코드 예제
•
•
이 외에도, ε-Greedy / UCB / LinUCB / Contextual Bandits / Kernel UCB 알고리즘의 수식과 업데이트 규칙 등을 직접 구현해 친절하고 직관적인 예제를 제공하고 있는 레포지터리가 있어, 한번 살펴보겠습니다.
•
전체 코드는 아래 커맨드로 git clone해 확인해 주세요.
> git clone https://github.com/akhadangi/Multi-armed-Bandits.git
JSON
복사
#===============================
# Epsilon Greedy ...
#===============================
mab = EpsGreedy(10, 0.05)
results_EpsGreedy, chosen_arms_EpsGreedy, cumulative_reward_EpsGreedy = offlineEvaluate(mab, arms, rewards, contexts, 800)
print('EpsGreedy average reward', np.mean(results_EpsGreedy))
#===============================
# UCB ...
#===============================
mab = UCB(10, 1.0)
results_UCB, chosen_arms_UCB, cumulative_reward_UCB = offlineEvaluate(mab, arms, rewards, contexts, 800)
print('UCB average reward', np.mean(results_UCB))
#===============================
# Linear UCB (Contextual) ...
#===============================
mab = LinUCB(10, 10, 1.0)
results_LinUCB, chosen_arms_LinUCB, cumulative_reward_LinUCB = offlineEvaluate(mab, arms, rewards, contexts, 800)
print('LinUCB average reward', np.mean(results_LinUCB))
#===============================
# Plotting results ...
#===============================
plt.figure(figsize=(12,8))
plt.plot(cumulative_reward_LinUCB/np.linspace(1,800,800), label = r"$\alpha=1$ (LinUCB)")
plt.plot(cumulative_reward_UCB/(np.linspace(1,800,800)), label = r"$\rho=1$ (UCB)")
plt.plot(cumulative_reward_EpsGreedy/(np.linspace(1,800,800)), label = r"$\epsilon=0.05$ (greedy)")
plt.legend(bbox_to_anchor=(1.2, 0.5))
plt.xlabel("Rounds")
plt.ylabel(r"$T^{-1}\sum_{t=1}^T\ r_{t,a}$", fontsize='large')
plt.title("Per-round Cumulative Rewards after single simulation")
plt.show()
Python
복사
•
위의 코드는 약 1,000번의 실행동안 LinUCB와 UCB, 𝜖이 0.05인 greedy 알고리즘의 실행 결과를 나타냅니다.
•
x축은 앞선 설명에서의 𝑡기를 나타낸다.
•
여기서 처음 소개된 LinUCB를 간단히 설명하자면, 입력 변수를 활용하는 contextual bandit의 일종으로, 입력된 피처 값을 바탕으로 선형 모델을 적합하여 보상을 예측도록 학습하는 알고리즘입니다.
•
다음 시간에 이러한 contextual bandits에 대해서도 다루어 보도록 하겠습니다.