Multi-Armed Bandit (MAB)

Reinforcement Learning — Multi-Arm Bandit Implementation ❘ by Jeremy Zhang ❘ Towards Data Science

 

Multi-Armed Bandit 문제는 기계학습과 알고리즘에서 자주 사용되는 개념으로,

특히 '최적화'와 '탐험 vs 활용' (exploration vs exploitation)에 관한 문제를 다룰 때 유용합니다.

이름에서 알 수 있드시 여러 개의 팔이 있는 도박기계(슬롯머신)에서 나온 비유로,

간단히 말하면 어떤 선택지를 고를 때 각 선택이 줄 수 있는 이득을 최대화하는 방법을 찾아가는 것을 목표로 합니다.

 

MAB의 기본 개념 이해하기

MAB 문제를 '사탕기계 문제'로 비유해보겠습니다.

여러분은 여러 개의 캔디 머신을 가지고 있고, 각 머신에 돈을 넣으면 맛있는 캔디가 나옵니다.

그러나 각 캔디 머신은 주는 캔디의 양이나 맛이 조금씩 다릅니다.

어떤 머신은 더 많은 캔디를 줄 수 있고, 어떤 머신은 조금 줄수도 있어요.

그래서 매번 돈을 넣기 전에 어떤 캔디 머신에 넣는 것이 가장 좋은 선택(최대한 많은 캔디를 얻기)인지 고민하게 됩니다.

• 탐험 (exploration) : 새 고운 캔디 머신에 돈을 넣어 보는 것이에요.  즉, 아직 잘 모르는 캔디 머신을 한 번 시험합니다.
• 활용 (Exploitation) : 이미 알고 있는 캔디 머신 중에서 가장 많은 캔디를 줄 것 같은 머신을 선택합니다.

이 두 가지 방법을 적절히 조합해서 여러 캔디머신을 탐험도 해보고 지금까지 알아간 캔디머신 중 가장 많은 캔디를 주는 머신을 선택하면서 최대한 많은 캔디를 얻는 것이 바로 MAB 알고리즘입니다.

 

 

MAB 알고리즘 종류

다양한 MAB알고리즘이 있지만, 최근 자주 사용하는 주요 알고리즘을 알아볼까요?

 

(1) Epsilon-Greedy 알고리즘

Epsilon-Greedy는 가장 간단한 방법 중 하나인데요.

이 방법에서는 '탐험과 활용'의 비율을 정하고 그에 따라 행동을 하는 것을 의미합니다. 

 

(예) 90% 확률로 현재까지 가장 많은 캔디를 준 머신에 돈을 넣기. 10% 확률로 다른 머신을 시도해 보기.

 

(2) UCB (Upper Confidence Bound) 알고리즘

UCB는 '확률'과 '기댓값'을 계산해서 각 캔디 머신의 Confidence를 계산하여 좋은 선택을 하는 방법이에요.

많이 사용한 머신일수록 확신이 높고, 적게 사용한 머신일수록 불확실성이 높다고 할 수 있는데요.

UCB는 이 불확실성을 고려하여 아직 충분히 사용해보지 않은 머신에게도 기회를 주도록 설계되었어요.

1. 초기단계 : 모든 캔디머신을 최소한 한 번씩 사용해 봅니다.
2. 평균 보상 계산 : 각 머신이 지금까지 준 캔디의 평균 개수를 계산합니다.
3. 상한 신뢰 구간 (Upper Confidence Bound) 계산 : 각 머신의 사용한 횟수와 전체 사용 횟수에 따라 확신 정도를 수치로 나타내요. 적게 사용한 머신일수록 추가 점수가 높아집니다.
4. 최종 점수 계산 : 평균 보상 + 확신정도를 더해서 각 머신의 최종 점수를 구합니다.
5. 다음 선택 : 최종 점수가 가장 높은 머신을 선택하여 사용
6. 반복

 

(예) 캔디 머신 C가 가끔 10개의 캔디를 준다고 할 때, UCB알고리즘은 캔디머신 C가 가장 많은 캔디를 줄 가능성이 있다고 생각해 한번 더 시도해 봅니다.

 

(3) Tompson Sampling 알고리즘

Tompson Sampling은 '확률' 개념을 더 많이 활용하는 방법입니다.

각 캔디 머신이 캔디를 줄 확률을 추정하고, 그 확률에 따라 랜덤 하게 선택하는 방식입니다.

 

(예) 각 캔디 머신의 성능을 고려해서 C 머신이 많은 캔디를 줄 가능성이 높다고 판단하면 C 머신을 선택할 확률을 조금 더 높이는 식으로 결정합니다.

 

 

MAB는 어디에 사용될까?

생각보다 MAB알고리즘은 여러 분야에 쓰이고 있어요.

• 온라인 광고 : 여러 광고 중에 어느 광고가 사람들에게 가장 많이 클릭될지 실험하고 최적의 광고를 선택할 때 MAB 알고리즘을 사용합니다.
• 추천 시스템 : 유튜브나 넷플릭스 같은 플랫폼에서 사용자에게 어떤 콘텐츠를 추천할지 결정할 때 사용됩니다.
• 게임 : 여러 가지 보상을 주는 아이템이 있을 때 어떤 아이템을 줘야 사용자들이 게임에 더 오래 머물지 실험할 때도 사용돼요.