들어가며
웹 서비스를 운영하다 보면 이런 고민을 한 번쯤 해봤을 것이다.
"헤드라인 A와 B 중에 어떤 게 클릭률이 높을까?"
전통적인 A/B 테스트로 답을 구할 수 있다. 트래픽을 반반으로 나누고, 충분한 데이터를 모으고, 통계적으로 유의미한 결과가 나오면 승자를 선택한다. 깔끔하고 명확하다.
그런데 이 과정에서 한 가지 찝찝한 점이 있었다. 🤔
실험 도중에 이미 B가 압도적으로 안 좋다는 게 보이는데, 실험이 끝날 때까지 계속 B에 트래픽을 보내야 할까? 그 트래픽은 사실상 버리는 트래픽 아닌가?
이런 고민을 하다가 멀티암드 밴딧(Multi-Armed Bandit, MAB) 알고리즘을 알게 됐다. 도박장의 슬롯머신에서 이름을 따온 이 알고리즘은 실험하면서 동시에 최적화할 수 있는 꽤 매력적인 방법이었다.
오늘은 MAB 알고리즘의 핵심 아이디어와 대표적인 두 가지 알고리즘을 정리해보려고 한다.
멀티암드 밴딧이란?
용어부터 정리하자
멀티암드 밴딧을 이해하려면 먼저 용어를 알아야 한다.
용어 | 의미 | 예시 |
멀티암드 밴딧(MAB) | 고객이 선택할 수 있는 손잡이가 여러 개인 가상의 슬롯머신 | 다중 처리 실험에 대한 비유 |
손잡이(Arm) | 실험에서 어떤 하나의 처리 | 웹 테스트에서 헤드라인 A |
상금/수익(Win) | 슬롯머신으로 딴 상금에 대한 실험적 비유 | 고객들의 링크 클릭 수 |
슬롯머신을 숙칭 팔 하나인 강도(bandit)라고 부르기 때문이다. 도박꾼들이 지속적으로 조금씩 돈을 잃게 되는 구조이므로, 둘 이상의 손잡이가 달려 있고 각 손잡이는 다른 속도로 돈을 지불하는 슬롯머신을 상상해보자. 그것이 바로 이 알고리즘의 정식 이름(팔 여러 개 달린 강도)이라고 할 수 있다.
전통적인 A/B 테스트의 한계
전통적인 A/B 검정은 특정하게 설계된 실험을 통해 수집된 데이터를 이용하여 '처리 A나 처리 B 둘 중 어느 쪽이 더 좋은가?'와 같이 정해진 질문에 대한 답을 준다. 일단 답을 얻고 나면 실험은 멈추고 결과에 따라 행동한다.
깔끔해 보이지만, 이러한 접근에 몇 가지 어려움을 느낄 수도 있다.
첫째, 결론을 내리기 어려울 수 있다.
'입증되지 않은 효과', 즉 실험 결과를 통해 효과가 있다는 것을 유추할 수는 있지만, 효과가 있더라도 그것을 입증할 만한(전통적인 통계 표준을 만족시킬 만한) 크기의 표본이 없을 수 있다. 어떤 결론을 내릴 수 있을까?
둘째, 우리는 실험이 끝나기 전에 이미 얻은 결과들을 이용하기 시작할 수도 있다.
A가 초반부터 좋은 성과를 보이면, "아직 실험 중이니까 기다리자"라고 하기엔 비즈니스 비용이 너무 크다.
셋째, 마음을 바꿔서 실험이 끝난 후에 추가적으로 들어오는 데이터를 기반으로 다른 것을 시도하고 싶을 수 있다.
실험과 가설검정에 대한 전통적인 방법들은 1920년대에 시작된 것으로, 다소 유연하지 않다. 컴퓨터 성능과 소프트웨어의 출현으로 더 강력하고 유연한 접근 방식이 가능해졌다. 게다가 데이터 과학, 그리고 비즈니스 전반에서는 통계적 유의성보다는 제반 비용과 결과를 최적화하는 데 더 관심이 있다.
탐색과 활용의 딜레마
MAB의 핵심을 이해하려면, 탐색(Exploration)과 활용(Exploitation)의 균형을 알아야 한다.
구체적인 예를 들어보자. 우리의 목표는 가능한 한 많은 돈을 얻는 것이고, 더 구체적으로 말하면 많은 상금이 나오는 손잡이를 나중에 확인하는 것이 아니라 빨리 확인하는 것이다. 어려운 점은 손잡이를 잡아당길 때 총 얼마를 지불할지 모른다는 것이다. 손잡이를 당겼을 때 개별적인 결과만 알 수 있다.
어떤 '손잡이'든지 간에 '상금'이 모두 같은 금액이라고 가정하자. 다른 점은 승리할 확률이다. 처음에 각 손잡이마다 50번 시도한 후 다음과 같은 결과를 얻었다고 가정하자.
- 손잡이 A: 50번 중 10번 승리
- 손잡이 B: 50번 중 2번 승리
- 손잡이 C: 50번 중 4번 승리
그러면 단순히 다음과 같은 극단적인 결론을 내릴 수 있을 것이다.
'손잡이 A가 최고인 것으로 보인다. 다른 손잡이는 시도하지 말고 A만 당기자.'
이것은 초기 시험에서 얻은 정보를 최대한 활용하는 방법이다. A가 정말로 우월하다면, 우리는 그 이익을 초기에 얻게 된다. 하지만 사실은 B나 C가 더 좋다면 우리는 이 사실을 발견할 기회를 놓치게 된다.
또 다른 극단적인 접근법은 '모두 똑같이 잡아당기자.'이다. 이것은 A 외의 다른 것들의 확률을 알 수 있는 최대한의 기회를 제공한다. 그러나 그 과정에서 우리는 어쩔 수 없이 수익이 낮을 것으로 예상되는 행위를 자주 시도해야 한다.
이것을 얼마나 지속해야 할까? 밴딧 알고리즘은 하이브리드 접근 방식을 취한다.
A의 우위를 활용하기 위해 A를 더 자주 잡아당기는 것으로 시작하긴 하지만, 그렇다고 B와 C를 포기하지는 않는다. A에서 계속해서 성과를 거둔다면, B와 C를 당길 기회를 A에게 더 줘서 A를 더 자주 잡아당긴다. 반면 C가 더 좋아지거나 A가 더 나빠지기 시작하면 A로 가던 기회를 C에게 돌린다. 그 중 하나가 A보다 우수하고 이것이 초기 실험에서 우연히 감춰졌던 결과라면, 이제는 더 많은 테스트를 통해 이 사실이 밝혀질 수 있는 기회가 생기게 된다.
엡실론-그리디 알고리즘
가장 간단한 MAB 알고리즘
이제 이것을 웹 테스트에 적용하는 방법을 생각해보자. 여러 개의 슬롯머신 손잡이 대신에 웹 사이트에서 여러 가지 제안, 헤드라인, 색상 등을 테스트할 수 있다. 고객은 클릭(상품 판매자 입장에서의 '승리')하거나 클릭하지 않을 것이다.
처음에는 여러 제안이 무작위로 균등하게 표시된다. 그러다가 한 제안이 다른 제안보다 좋은 결과를 내기 시작하면 더 자주 표시('잡아당기')될 수 있게 한다.
그러면 잡아당기는 비율을 언제 어떻게 수정해야 할까?
엡실론-그리디 알고리즘이라는 A/B 검정을 위한 간단한 알고리즘은 같다.
알고리즘 동작 방식:
- 0부터 1 사이의 균등분포의 난수를 생성한다.
- 이 숫자가 0과 엡실론(0과 1 사이의 값으로 일반적으로 아주 작다) 사이에 존재하면, 50/50의 확률로 동전 뒤집기를 시행한다.
- a. 그 결과 동전이 앞면이면 제안 A를 표시한다.
- b. 동전이 뒷면이면 제안 B를 표시한다.
- 숫자가 엡실론보다 크면, 지금까지 가장 좋은 결과를 보인 제안을 표시한다.
엡실론의 의미
엡실론은 이 알고리즘을 제어하는 단일 파라미터이다.
- 엡실론이 1이면: 매 실험마다 A와 B를 무작위로 할당하게 되는 셈이다. 결국 전통적인 A/B 검정(매 실험마다 무작위 균등 할당)을 하게 되는 것과 같다.
- 엡실론이 0이면: 더 이상의 실험 없이, 지금까지 최상의 즉각적인 옵션(지역 최적)을 선택하는 완전한 **탐욕 알고리즘(greedy algorithm)**이 되어버린다. 피실험자(웹 방문자)들을 항상 지금까지 알려진 가장 좋은 제안에 할당한다.
보통 엡실론은 아주 작은 값(예: 0.05~0.1)으로 설정한다. 대부분의 트래픽은 현재 최선의 선택에 할당하되, 가끔씩 랜덤 탐색을 하는 것이다.
엡실론 = 0.1일 때: - 90%의 트래픽 → 현재 최선의 제안에 할당 (활용) - 10%의 트래픽 → 랜덤으로 할당 (탐색)
간단하고 직관적이다. 하지만 뭔가 아쉽다.
엡실론-그리디는 얼마나 확신이 있는가를 고려하지 않는다. 손잡이 A가 10번 중 3번 이겼든, 10,000번 중 3,000번 이겼든, 같은 방식으로 탐색한다. 직관적으로 후자의 경우에는 탐색을 줄여도 될 것 같은데 말이다. 🤔
톰슨 샘플링: 더 똑똑한 방법
베이즈 방식의 접근
톰슨 샘플링에서는 각 단계마다 '표본을 추출'(손잡이를 당김)하여 최고의 손잡이를 선택할 확률을 최대화한다. 당연히 어느 것이 가장 좋은 손잡이인지 모른다. 그러나 연속적인 추출을 통해 얻는 수익을 관찰하면 더 많은 정보를 얻을 수 있다.
톰슨 샘플링은 베이즈 방식을 사용한다. 즉, 베타 분포(beta distribution)를 사용하여 사전 정보를 지정하는 일반적인 메커니즘(베이즈 문제에서 사전 정보를 지정하는 일부 사전 분포를 가정)을 사용하여 수익의 일부 사전 분포를 가정한다.
톰슨 샘플링의 직관
톰슨 샘플링의 핵심 아이디어를 쉽게 풀어보면 이렇다.
각 손잡이(Arm)마다 "이 손잡이의 진짜 승률이 얼마일까?"에 대한 확률 분포를 유지한다. 처음에는 아무 정보가 없으니 균등분포(Beta(1,1))에서 시작한다. 데이터가 쌓이면서 이 분포가 점점 좁아지고, 진짜 승률 근처로 모인다.
매 시행마다 각 손잡이의 분포에서 값을 하나씩 랜덤 샘플링하고, 가장 높은 값이 나온 손잡이를 선택한다.
왜 이게 잘 작동할까?
- 확신이 높은 손잡이(데이터 많음): 분포가 좁다 → 샘플 값이 평균 근처에서 나온다
- 확신이 낮은 손잡이(데이터 적음): 분포가 넓다 → 가끔 높은 값이 나올 수 있다 → 자연스럽게 탐색됨
즉, 불확실한 곳을 자연스럽게 더 탐색하고, 확실한 곳에서는 활용에 집중하는 아름다운(!) 균형이 만들어진다. 😊
구체적인 예시로 이해하기
3개의 웹사이트 헤드라인 A, B, C를 테스트한다고 하자.
초기 상태 (각각 10번씩 시도 후):
헤드라인 | 시도 횟수 | 클릭 수 | 클릭률 | 베타 분포 |
A | 10 | 3 | 30% | Beta(4, 8) |
B | 10 | 5 | 50% | Beta(6, 6) |
C | 10 | 1 | 10% | Beta(2, 10) |
이 시점에서 톰슨 샘플링은:
- Beta(4, 8)에서 랜덤 샘플 → 예: 0.28
- Beta(6, 6)에서 랜덤 샘플 → 예: 0.55
- Beta(2, 10)에서 랜덤 샘플 → 예: 0.18
→ B가 가장 높으니 B를 표시!
하지만 C의 분포가 넓기 때문에, 가끔은 C에서 높은 값이 나와서 C도 선택될 수 있다. 이것이 자연스러운 탐색이다.
1000번 시도 후:
헤드라인 | 시도 횟수 | 클릭 수 | 클릭률 | 베타 분포 |
A | 200 | 60 | 30% | Beta(61, 141) |
B | 700 | 350 | 50% | Beta(351, 351) |
C | 100 | 10 | 10% | Beta(11, 91) |
이제 각 분포가 좁아져서 B가 거의 항상 선택된다. 자연스럽게 최적의 선택으로 수렴한 것이다.
각 추출 손잡이마다 사전 정보가 누적되면서 정보가 업데이트
각 추출 손잡이마다 사전 정보가 누적되면서 정보가 업데이트되기 때문에, 다음번에 최고 손잡이를 선택할 확률을 효과적으로 최적화할 수 있다.
이것이 엡실론-그리디와의 가장 큰 차이점이다:
특성 | 엡실론-그리디 | 톰슨 샘플링 |
탐색 방식 | 고정 확률로 랜덤 탐색 | 불확실성 기반 자연스러운 탐색 |
파라미터 | 엡실론 값 수동 설정 | 자동 조절 (베타 분포) |
확신도 반영 | 반영 안 됨 | 분포의 폭으로 자동 반영 |
수렴 속도 | 상대적으로 느림 | 상대적으로 빠름 |
구현 난이도 | 매우 쉬움 | 약간의 통계 지식 필요 |
밴딧 알고리즘은 언제 빛날까?
밴딧 알고리즘은 3가지 이상의 처리를 효율적으로 다루고 '최고'를 위한 최적의 선택을 하도록 돕는다.
전통적인 통계 검정의 경우, 3가지 이상의 처리를 위한 의사 결정은 전통적인 A/B 검정의 의사 결정보다 훨씬 복잡하며, 이 경우 밴딧 알고리즘의 장점이 훨씬 더 커진다.
정리하면:
- 전통적 A/B 검정: 임의표본추출 과정을 기본으로 하기 때문에, 수익이 낮은 것을 너무 많이 시도할 수 있다.
- MAB: 실험 도중에 얻은 정보를 통합하고 수익이 낮은 것의 빈도를 줄이는 쪽으로 표본추출 과정을 변경한다.
- 또한 두 가지 이상의 처리를 효과적으로 다룰 수 있다.
- 추출 확률을 수익이 낮은 처리에서 수익이 높으리라 추정되는 쪽으로 이동시키기 위한 다양한 알고리즘이 존재한다.
실무에서의 활용
어떤 상황에서 MAB를 쓸까?
MAB가 특히 유용한 상황들을 정리해봤다.
웹 최적화:
- 랜딩 페이지 헤드라인, CTA 버튼 색상, 배너 이미지 등
- 트래픽이 곧 비용이니까, 빠르게 최적화하는 게 중요
추천 시스템:
- 새로운 콘텐츠/상품이 계속 추가되는 환경
- "이 사용자에게 어떤 추천이 가장 좋을까?"
광고 최적화:
- 여러 광고 소재 중 어떤 것이 CTR이 높은지
- 예산을 효율적으로 분배하고 싶을 때
임상 시험:
- 여러 치료법 중 가장 효과적인 것을 빨리 찾고 싶을 때
- 윤리적으로도 효과 없는 치료에 환자를 계속 배정하는 건 문제가 될 수 있음
주의할 점도 있다
물론 MAB가 항상 정답은 아니다.
① 통계적 유의성이 중요한 경우
학술 연구나 규제 기관에 보고할 때는 전통적 A/B 테스트의 통계적 엄밀함이 필요할 수 있다. MAB는 "이것이 더 좋다"는 판단은 빠르게 내리지만, p-value 같은 전통적 통계량을 제공하지는 않는다.
② 효과의 크기를 정확히 측정해야 하는 경우
"A가 B보다 정확히 몇 % 좋은가?"를 알고 싶다면 A/B 테스트가 더 적합하다. MAB는 최적의 선택을 빠르게 찾는 데 초점을 맞추기 때문이다.
마치며
멀티암드 밴딧 알고리즘은 실험설계에 대한 전통적인 통계적 접근 방식보다 명시적인 최적화와 좀 더 빠른 의사 결정을 가능하게 해주는, 꽤 실용적인 도구라는 생각이 든다.
핵심을 다시 정리하면:
- 전통적 A/B 테스트: "먼저 충분히 실험하고, 그 다음에 최선을 선택하자"
- 엡실론-그리디: "대부분은 최선을 선택하되, 가끔 랜덤으로 탐색하자"
- 톰슨 샘플링: "불확실한 곳은 자연스럽게 더 탐색하고, 확실한 곳은 집중 활용하자"
개인적으로 톰슨 샘플링의 아이디어가 특히 인상적이었다. 불확실성을 확률 분포로 표현하고, 그 분포에서 샘플링하는 것만으로 탐색과 활용의 균형이 자동으로 맞춰진다는 게 정말 우아하다고 느꼈다. 😊
앞으로 추천 시스템이나 온라인 최적화 문제를 다룰 때 꼭 적용해보고 싶다. 다음에는 MAB의 확장 버전인 컨텍스트 밴딧(Contextual Bandit)이나 UCB(Upper Confidence Bound) 알고리즘도 정리해보려고 한다.
감사합니다! 😊
더 읽을 거리
- 존 마일즈 화이트의 『Bandit Algorithms for Website Optimization』(O'Reilly, 2012) - MAB에 대한 짧지만 아주 훌륭한 설명과 파이썬 코드, 시뮬레이션 결과를 제공
- 시프라 아그라와(Shipra Agrawal)와 나빈 고얄(Navin Goyal)의 「Analysis of Thompson Sampling for the Multi-armed Bandit Problem」 - 톰슨 샘플링에 대한 기술적인 추가 정보
- Peter Auer et al., 「Finite-time Analysis of the Multiarmed Bandit Problem」 - UCB 알고리즘의 이론적 분석