← 목록으로
AI·데이터
#멀티암드밴딧#탐험활용#톰슨샘플링#UCB#온라인학습
최종 업데이트 · 2026-11-19

멀티암드 밴딧(Multi-Armed Bandit)과 탐험·활용 최적 배분

1. 개요

정의: 멀티암드 밴딧(Multi-Armed Bandit, MAB)은 보상 분포를 미리 알 수 없는 여러 선택지(arm) 중에서 매 시점 하나를 선택하고 그 결과(보상)를 관측하는 과정을 반복하면서, 탐험(exploration, 미지의 선택지 정보 수집)과 활용(exploitation, 현재까지 가장 좋아 보이는 선택지 선택)의 균형을 통해 누적 보상을 최대화(=누적 후회를 최소화)하는 순차적 의사결정(sequential decision making) 문제이자 알고리즘군이다.

이름은 여러 개의 손잡이(arm)를 가진 슬롯머신(one-armed bandit, 외팔이 도둑) 앞에 선 도박사의 상황에서 유래한다. 각 손잡이는 당길 때마다 서로 다른(그러나 알 수 없는) 확률로 상금을 주며, 도박사는 제한된 횟수 안에서 어떤 손잡이가 좋은지 알아내는 데 드는 비용과 좋다고 판단된 손잡이에서 상금을 거두는 이득 사이에서 끊임없이 저울질해야 한다. 이 추상화가 디지털 시대에 와서 광고 소재 선택, 추천 알고리즘, 가격 결정, 임상시험 환자 배정 등 "제한된 기회 안에서 불확실한 대안 중 반복 선택"이 필요한 거의 모든 문제의 수학적 뼈대가 되었다.

MAB의 본질은 탐험-활용 딜레마(exploration-exploitation dilemma)다. 활용만 하면 초반의 운 좋은(혹은 운 나쁜) 관측에 갇혀 실제로 더 좋은 선택지를 영영 놓칠 수 있고, 탐험만 하면 이미 열등하다고 판명난 선택지에 자원을 낭비한다. 좋은 밴딧 알고리즘은 "충분히 불확실한 선택지는 더 자주 시도해 보되, 증거가 쌓여 열등함이 분명해지면 빠르게 손절"하는 원리를 수학적으로 구현한다. 이때 성능의 척도는 후회(regret) — 매 시점 항상 최적 선택지를 골랐을 때의 기대 보상과 실제로 알고리즘이 얻은 보상의 누적 차이 — 이며, 좋은 알고리즘일수록 시간 T에 대해 후회가 느리게(이론적으로 O(log T)) 증가한다.

등장 배경과 필요성

전통적 A/B 테스트는 사용자를 고정 비율(예: 50:50)로 나눠 일정 기간 끝까지 열등안에도 트래픽을 보낸 뒤, 종료 시점에 통계적으로 승자를 가린다. 이 방식은 인과효과를 깨끗하게 추정하는 데는 탁월하지만, 실험 기간 내내 명백히 나쁜 안에 절반의 사용자를 노출시키는 기회비용(실험 유감, experimentation regret)을 피할 수 없다. 특히 소재가 수십·수백 개이거나, 트렌드가 빨라 소재의 수명이 짧거나(뉴스 헤드라인, 패션 상품), 기회가 희소한(임상시험) 상황에서는 "끝까지 공평하게 나누는" 고정 실험이 비효율적이다.

MAB는 실험하면서 동시에 학습 결과를 즉시 배분에 반영함으로써 이 손실을 줄인다. 좋아 보이는 선택지에 점점 더 많은 트래픽을 흘려보내므로, 실험 자체의 누적 손실이 작고 "최적안 수렴"과 "손실 최소화"를 동시에 달성한다. 또한 선택지를 중간에 추가·제거할 수 있어 동적 환경에 유연하다. 이 때문에 추천·광고·개인화처럼 대안이 많고 빠르게 변하는 영역에서 MAB는 고정 A/B 테스트를 보완하거나 대체하는 핵심 기법으로 자리 잡았다.

기술사 관점의 문제 정의

논술에서 MAB를 "좋은 걸 더 자주 고르는 알고리즘"으로만 쓰면 실패다. 핵심 축은 ① 탐험-활용 딜레마를 후회(regret) 최소화로 정식화하는 관점, ② ε-greedy·UCB·톰슨 샘플링의 원리적 차이와 수렴 보장, ③ 맥락(context)·비정상성(non-stationarity)·지연 보상 같은 현실 제약의 확장, ④ A/B 테스트와의 역할 분담 및 통계적 추론의 trade-off를 정량·구조적으로 전개하는 것이다.

2. 전체 구조와 핵심 구성요소

MAB는 "선택 → 보상 관측 → 믿음 갱신 → 다음 선택"이 이어지는 하나의 온라인 학습 루프다. 아래 구조도는 에이전트와 환경의 상호작용, 그리고 탐험-활용 정책이 어디에서 작동하는지를 보여 준다.

flowchart TD
  P["정책(Policy): 탐험-활용 균형 규칙"] --> SEL["Arm 선택(a_t)"]
  SEL --> ENV["환경(Environment): 보상 분포 미지"]
  ENV --> R["보상 관측(r_t)"]
  R --> UPD["추정 갱신(평균·불확실성)"]
  UPD --> P
  UPD --> REG["후회(Regret) 누적 측정"]
  CTX["맥락(Context): 사용자·시간 특성"] -.-> P
  REG -.->|"성능 평가"| EVAL["오프라인 평가·IPS/DR"]

밴딧 문제의 구성요소는 네 가지다. 첫째 선택지 집합(arms)은 광고 소재·추천 상품·UI 변형처럼 에이전트가 고를 수 있는 대안들이다. 둘째 보상(reward)은 각 선택의 결과로, 클릭 여부(베르누이), 체류시간·매출(연속값)처럼 문제에 따라 분포가 다르다. 셋째 정책(policy)은 지금까지의 관측을 바탕으로 다음 선택지를 결정하는 규칙이며, 여기에 탐험-활용 전략이 녹아 있다. 넷째 후회(regret)는 성능 지표로, 사후적으로 알게 된 최적 선택지 대비 손실의 누적이다.

가. 탐험-활용 딜레마와 후회

탐험-활용 딜레마는 MAB의 모든 것을 관통하는 원리다. 각 선택지에는 현재까지의 추정 평균 보상과 그 추정의 불확실성(표본이 적을수록 큼)이 있다. 활용은 추정 평균이 높은 선택지를, 탐험은 불확실성이 큰(아직 덜 시도한) 선택지를 선호한다. 핵심 통찰은 "불확실성이 큰 선택지는 실제로는 최고일 수도 있으므로, 그 가능성을 배제하기 전에 몇 번 더 시도해 볼 가치가 있다"는 것이다.

이를 정량화한 것이 후회다. 선택지 i의 기대 보상을 μ_i, 최적 선택지를 μ라 하면, T회 선택 후 기대 후회는 Σ(μ − μ_{a_t})로 정의된다. 순진한 ε-greedy(ε 고정)는 끝까지 ε 비율로 아무 선택지나 고르므로 후회가 시간에 선형(O(T))으로 증가하지만, UCB·톰슨 샘플링처럼 불확실성을 정교하게 다루는 알고리즘은 열등 선택지를 점점 덜 고르게 되어 후회가 로그(O(log T))로 억제된다. 예컨대 클릭률 10%·5%인 두 소재를 100만 회 노출할 때, 고정 50:50 실험은 열등 소재에서 약 2만5천 클릭을 잃지만, 좋은 밴딧은 수천 클릭 손실로 수렴한다.

나. 추정과 믿음 갱신

밴딧의 심장은 각 선택지에 대한 믿음(belief)을 데이터로 갱신하는 과정이다. 가장 단순하게는 선택지별 표본 평균 보상을 유지하되, 증분 평균 공식 Q ← Q + (r − Q)/n 으로 매 관측마다 O(1)에 갱신한다. 비정상 환경에서는 과거를 잊기 위해 고정 학습률 α로 지수가중이동평균 Q ← Q + α(r − Q)을 쓴다.

더 정교한 접근은 평균뿐 아니라 불확실성 전체를 분포로 유지하는 것이다. 베르누이 보상(클릭/비클릭)의 경우 켤레사전분포인 베타(Beta) 분포를 각 선택지에 두고, 성공·실패를 α·β 모수에 누적하면 사후분포가 닫힌 형태로 갱신된다. 이렇게 "점추정"이 아니라 "분포"를 유지하면, 뒤에 설명할 톰슨 샘플링처럼 불확실성을 자연스럽게 탐험에 활용할 수 있다.

다. 맥락(Context)과 평가의 문제

현실에서는 "어떤 소재가 좋은가"가 사용자에 따라 다르다. 20대 여성에게 좋은 광고와 50대 남성에게 좋은 광고가 다르다는 것이다. 이를 반영한 것이 맥락적 밴딧(contextual bandit)으로, 매 시점 사용자·시간·기기 특성 벡터 x_t를 받아 "이 맥락에서 각 선택지의 기대 보상"을 선형모형·신경망으로 추정하고 그 위에 탐험 규칙을 얹는다(LinUCB, 신경 밴딧 등). 맥락이 없는 고전 밴딧이 "전체 평균 최적안"을 찾는다면, 맥락적 밴딧은 개인화된 최적안을 찾는다.

또 하나의 난제는 오프라인 평가다. 밴딧은 선택하지 않은 선택지의 보상을 관측하지 못하므로(반사실, counterfactual), 과거 로그만으로 새 정책을 평가하기 어렵다. 이를 위해 역성향가중(IPS, Inverse Propensity Scoring)·이중강건(Doubly Robust) 추정량이 쓰이며, 로그를 남길 때 각 선택의 확률(propensity)을 함께 기록해야 편향 없는 오프라인 평가가 가능하다. 이 설계는 실무에서 밴딧 신뢰성을 좌우하는 핵심 결정이다.

3. 주요 알고리즘과 동작 절차

대표 알고리즘은 탐험을 어떻게 주입하느냐로 구분된다. 아래 프로세스 다이어그램은 한 번의 의사결정 사이클에서 세 계열이 어떻게 갈라지는지를 보여 준다.

flowchart TD
  START["라운드 t 시작"] --> HOW{"탐험 주입 방식"}
  HOW -->|"무작위 섞기"| EG["ε-greedy: 확률 ε로 무작위, 1-ε로 최선"]
  HOW -->|"낙관적 보너스"| UCB["UCB: 평균 + 신뢰상한 보너스 최대 선택"]
  HOW -->|"사후분포 표집"| TS["톰슨 샘플링: 각 arm 사후분포에서 표본 추출 후 최대 선택"]
  EG --> ACT["선택 실행 → 보상 관측"]
  UCB --> ACT
  TS --> ACT
  ACT --> UP["추정·사후분포 갱신"]
  UP --> START

가. ε-greedy — 가장 단순한 탐험

ε-greedy는 확률 ε로 선택지를 무작위로 고르고(탐험), 1−ε로 현재 추정 평균이 가장 높은 선택지를 고른다(활용). 구현이 한 줄이면 끝날 만큼 단순하고 직관적이어서 산업 표준 베이스라인으로 널리 쓰인다. 다만 두 가지 약점이 있다. 첫째, ε이 고정이면 충분히 학습된 뒤에도 계속 ε만큼 손실을 내므로 후회가 선형으로 증가한다. 이를 완화하려고 시간에 따라 ε을 줄이는 ε-감소(decay) 변형을 쓴다. 둘째, 탐험이 "완전 무작위"여서 명백히 나쁜 선택지와 유망한 선택지를 똑같이 시도하는 비효율이 있다.

그럼에도 ε-greedy가 실무에서 꾸준히 쓰이는 이유는 견고함과 설명가능성이다. 분포 가정이 거의 없고, 비정상 환경에서도 ε만큼의 탐험이 항상 보장돼 환경 변화를 놓치지 않는다. 넷플릭스가 초기 아트워크(썸네일) 개인화에 ε-greedy 계열을 광범위하게 적용해 시청 참여를 끌어올린 사례처럼, "완벽한 최적성"보다 "운영 단순성과 안정성"이 중요한 현장에서 여전히 1순위 후보다.

나. UCB — 불확실성에 대한 낙관

UCB(Upper Confidence Bound)는 "불확실성 앞에서 낙관하라(optimism in the face of uncertainty)"는 원리를 구현한다. 각 선택지에 대해 추정 평균에 신뢰상한 보너스(관측이 적을수록 큰 값, 예: √(2 ln t / n_i))를 더한 값을 계산하고, 이 합이 가장 큰 선택지를 선택한다. 덜 시도된 선택지는 보너스가 커서 자연히 선택되고, 많이 시도돼 불확실성이 줄면 보너스가 작아져 평균만으로 경쟁한다. 즉 탐험이 무작위가 아니라 "정보 가치가 큰 쪽으로 방향성 있게" 일어난다.

UCB의 강점은 이론적 후회 보장(O(log T))이 증명된다는 점과, 무작위성 없이 결정론적으로 동작해 재현·디버깅이 쉽다는 점이다. 약점은 보너스 항이 보상 분포 가정(유계성 등)에 민감하고, 선택지가 수천·수만 개로 많거나 맥락이 고차원일 때 계산·튜닝 부담이 커진다는 것이다. 맥락 확장인 LinUCB는 선형모형의 공분산으로 신뢰구간을 계산해 뉴스 추천 등에서 널리 쓰였다.

다. 톰슨 샘플링 — 사후분포에서 표집

톰슨 샘플링(Thompson Sampling)은 베이지안 접근으로, 각 선택지의 보상에 대한 사후분포에서 하나씩 표본을 뽑아 그 표본값이 가장 큰 선택지를 선택한다. 베르누이 보상이면 각 선택지의 베타 사후분포에서 성공률을 표집해 비교하는 식이다. 불확실성이 큰 선택지는 사후분포가 넓어 가끔 큰 값이 뽑히므로 탐험되고, 증거가 쌓여 분포가 좁아지면 열등 선택지가 뽑힐 확률이 급감한다. 탐험-활용이 확률적으로 자연스럽게 균형을 이룬다.

실무에서 톰슨 샘플링은 평균 후회가 작고, 지연 보상·배치 갱신에 강건하며, 구현이 의외로 간단해 가장 선호되는 알고리즘 중 하나다. 구글·마이크로소프트 등이 광고·추천 시스템에 폭넓게 적용했고, 수백 개 소재를 동시에 다루는 콘텐츠 최적화에서 UCB보다 안정적이라는 보고가 많다. 다만 보상 모형의 사전분포·우도를 정의해야 하므로 비정형 보상에는 모델링 노력이 필요하다.

라. 알고리즘 비교

세 계열의 차이는 "탐험을 어디에서 끌어오는가"에서 갈린다. 아래 표는 핵심 특성을 비교하되, 숫자 자체보다 왜 그런 차이가 생기는지가 중요하다. ε-greedy의 선형 후회는 "고정 비율의 무지성 탐험"에서, UCB·톰슨의 로그 후회는 "불확실성에 비례한 지향성 탐험"에서 비롯된다.

구분 ε-greedy UCB 톰슨 샘플링
탐험 방식 확률 ε로 무작위 신뢰상한 보너스(결정론) 사후분포 표집(확률)
후회 차수 O(T)(고정 ε) / 개선 가능 O(log T) O(log T)
분포 가정 거의 없음 유계성 등 필요 사전·우도 정의 필요
지연·배치 보상 강건 다소 취약 강건
구현 난이도 매우 낮음 낮음 중간
설명가능성 높음 높음 중간(확률적)

4. 비교와 적용 사례

가. A/B 테스트와의 관계 — 대체가 아니라 역할 분담

MAB와 A/B 테스트는 종종 대립 구도로 소개되지만, 실제로는 목적이 다른 상보적 도구다. A/B 테스트는 트래픽을 고정 비율로 끝까지 유지해 깨끗한 인과효과와 신뢰구간을 얻는 것이 목적이다. 반면 MAB는 실험 중 손실(유감)을 줄이고 최적안으로 빠르게 수렴하는 것이 목적이어서, 트래픽이 승자에게 쏠리는 순간 "열등안의 효과크기를 정밀 추정"하는 능력은 떨어진다. 즉 MAB에서는 "B가 A보다 정확히 몇 % 좋았다"를 사후에 신뢰구간으로 말하기 어렵다.

따라서 실무 원칙은 명확하다. 학습이 목적(정확한 효과 추정·의사결정 근거 확보)이면 A/B 테스트, 수익 최적화가 목적(손실 최소화·빠른 배분)이면 MAB를 쓴다. 소재 수명이 짧거나(헤드라인, 프로모션 배너) 대안이 수십 개 이상이면 MAB가, 핵심 기능의 장기 효과를 엄밀히 검증해야 하면 A/B 테스트가 적합하다. 둘을 결합해 "초기에 A/B로 후보를 거른 뒤 MAB로 배분 최적화"하는 하이브리드도 흔하다.

나. 산업 적용 사례

실제 적용은 광범위하다. 디지털 광고에서는 수십 개 광고 소재 중 클릭률이 높은 소재에 노출을 점증시키는 데 톰슨 샘플링·UCB가 표준적으로 쓰인다. 하루 수억 임프레션 규모에서 1%의 CTR 개선이 막대한 매출로 직결되므로, "열등 소재 손절 속도"가 곧 수익이다. 뉴스·콘텐츠 추천에서는 야후·뉴스 포털이 LinUCB 계열 맥락적 밴딧으로 사용자별 기사 배치를 최적화해 클릭률을 유의하게 높인 공개 사례가 있다.

임상시험에서는 환자를 윤리적으로 더 효과적인 치료군에 점점 더 많이 배정하는 반응적응배정(response-adaptive randomization)에 밴딧 아이디어가 쓰인다. 환자 한 명 한 명이 희소하고 윤리적 비용이 크므로, "실험 유감 최소화"라는 MAB의 목적이 생명과 직결된다. 그 밖에 동적 가격 결정(여러 가격대를 탐험하며 매출 극대화), 추천 시스템의 콜드스타트(신규 상품 노출 배분), 하이퍼파라미터 탐색 등에서 밴딧이 활용된다.

국내에서도 e-커머스·OTT·포털의 개인화 영역에서 밴딧 적용이 확산되고 있다. 예컨대 상품 상세페이지의 배너·쿠폰 소재를 수십 종 준비해 두고 밴딧으로 노출을 최적화하면, 고정 A/B 테스트처럼 "한 번에 두세 개씩 몇 주간 검증"하는 병목 없이 소재 풀 전체를 실시간으로 저울질할 수 있다. 특히 프로모션·시즌 상품처럼 수명이 짧은 소재는 A/B 테스트가 통계적 유의성을 확보할 때쯤이면 이미 시즌이 끝나 버리므로, "학습하면서 곧바로 배분"하는 밴딧의 이점이 두드러진다. 반대로 결제 플로우 변경처럼 되돌리기 어렵고 장기 영향을 엄밀히 검증해야 하는 변경은 여전히 고정 실험이 안전하다는 점에서, 조직은 두 도구의 의사결정 기준(변경의 가역성·소재 수명·효과 추정 필요성)을 사전에 합의해 두어야 한다.

5. 심화 — 맥락·비정상성·강화학습으로의 확장과 최신 동향

MAB는 더 일반적인 순차 의사결정으로 확장되며, 그 경계에서 최신 연구가 활발하다. 첫째, 맥락적 밴딧에서 심층 신경망 기반(neural bandit)으로의 확장이다. 선형 가정을 벗어나 복잡한 사용자-소재 상호작용을 학습하되 탐험을 유지하기 위해, 드롭아웃·앙상블·베이지안 신경망으로 불확실성을 근사하는 기법이 쓰인다. 다만 신경망의 과신(overconfidence) 때문에 탐험이 조기 붕괴하는 위험을 관리해야 한다.

둘째, 비정상 밴딧(non-stationary bandit)이다. 사용자 취향·트렌드가 시간에 따라 변하는 현실에서는 과거 데이터를 무한히 신뢰하면 안 된다. 슬라이딩 윈도우 UCB, 할인(discounted) UCB, 변화점 탐지 결합 기법 등이 "과거를 적절히 잊으며" 환경 변화를 추적한다. 이는 모델 드리프트 모니터링과도 맞닿아 있다.

셋째, 강화학습(RL)과의 관계다. 밴딧은 "상태(state)가 없거나 선택이 다음 상태에 영향을 주지 않는" 특수한 RL로 볼 수 있다. 선택이 환경 상태를 바꾸고 보상이 지연되어 누적되면 완전한 RL(MDP)이 되며, 밴딧의 탐험-활용 원리(UCB·톰슨)는 RL의 탐험 전략으로 그대로 계승된다. 최근에는 LLM 기반 추천·대화 최적화에서 응답 후보 선택을 밴딧으로 모델링하거나, RLHF의 보상모델 탐색에 밴딧 이론을 접목하는 흐름도 나타난다. 넷째, 광고·추천 플랫폼의 오프라인 정책 평가(OPE) 고도화로, IPS·DR·스위치 추정량을 통해 "라이브 트래픽 없이" 새 밴딧 정책을 안전하게 사전 검증하는 MLOps 관행이 정착되고 있다.

6. 고려사항 및 시사점

MAB 도입을 기술사 관점에서 설계·평가할 때는 다음을 균형 있게 고려해야 한다.

  • 목적 적합성(학습 vs 수익) 판단: 밴딧은 손실 최소화에 강하지만 효과크기의 정밀 추정에는 약하다. "근거 기반 의사결정"이 필요한 전략적 변경은 A/B 테스트로, "운영 최적화"는 밴딧으로 나누되, 두 접근을 하이브리드로 엮는 포트폴리오 전략이 바람직하다.

  • 통계적 추론과의 trade-off: 트래픽이 승자에게 쏠리면서 생기는 적응적 데이터(adaptive data) 때문에 단순 평균·표준오차가 편향된다. 사후 분석에는 IPS·이중강건 추정, 신뢰성 보정이 필요하며, 선택 확률(propensity) 로깅이 전제되어야 한다. 이 설계를 빠뜨리면 "최적화는 됐는데 설명·검증은 불가능한" 블랙박스가 된다.

  • 비정상성과 지연 보상 관리: 보상이 늦게 도착하거나(구매 전환 지연) 분포가 바뀌면 순진한 밴딧은 잘못된 선택지에 쏠린다. 윈도우·할인·배치 갱신, 지연 보상에 강건한 톰슨 샘플링 선택 등 환경 특성에 맞춘 알고리즘·주기 설계가 필요하다.

  • 공정성·안전·가드레일: 수익만 극대화하는 밴딧이 특정 집단을 체계적으로 불리하게 대하거나(공정성), 극단적 소재로 쏠려 브랜드·사용자 경험을 해칠 수 있다. 최소 노출 보장(각 선택지에 바닥 트래픽), 가드레일 지표 감시, 탐험 상한 설정으로 안전장치를 두어야 한다.

  • 운영 복잡도와 조직 역량: 맥락적·신경 밴딧은 피처 파이프라인·실시간 추론·오프라인 평가 체계를 요구한다. ε-greedy 같은 단순 기법으로 시작해 점진적으로 고도화하고, 실험 플랫폼·MLOps·모니터링과 통합하는 성숙도 로드맵이 성공을 좌우한다.

참고자료


한 줄 요약: 멀티암드 밴딧은 보상이 불확실한 여러 선택지 사이에서 탐험과 활용의 균형으로 누적 후회를 최소화하는 순차 의사결정 기법으로, ε-greedy·UCB·톰슨 샘플링이 대표 알고리즘이며, 손실을 줄이며 최적안으로 빠르게 수렴해야 하는 광고·추천·가격·임상 영역에서 A/B 테스트를 보완한다.