다중 슬롯머신

통계 최적설계 수치해석 마지막 수정: 2026-08-20 04:51:33

1. 개요[편집]

다중 슬롯머신 Multi-Armed Bandit
딜레마	탐험(exploration) ↔ 활용(exploitation)
성능 척도	후회(regret) $R_T=\sum_t(\mu^*-\mu_{a_t})$
하한	Lai–Robbins (1985): $\Omega(\ln T)$
대표 정책	ε-탐욕 · UCB1 · 톰슨 샘플링
확장	문맥 밴딧 · 적대적 밴딧(EXP3)
응용	A/B 테스트 · 광고 · 추천 · 임상시험

다중 슬롯머신(multi-armed bandit) 문제는 여러 개의 선택지(팔) 중에서, 각 팔의 보상 분포를 모른 채 반복적으로 하나를 골라 당기며, 누적 보상을 최대화하는 순차적 의사결정 문제다. 이름은 슬롯머신(외팔이 강도, one-armed bandit)이 여러 대 늘어선 카지노에서 왔다 — 어느 기계가 가장 잘 터지는지 모르는 도박꾼이, 돈을 잃어 가며 그것을 알아내야 하는 상황.¹

이 문제의 심장은 탐험-활용 딜레마(exploration–exploitation dilemma)다. 지금까지 가장 좋아 보이는 팔을 계속 당기면(활용) 당장은 이득이지만, 실은 더 나은 팔을 놓치고 있을 수 있다. 그렇다고 이것저것 찔러 보면(탐험) 정보는 얻지만 열등한 팔에 자원을 낭비한다. “확실히 좋은 것을 지금 쓸까, 더 좋을지 모를 것을 알아볼까” — 이 긴장이 광고 노출, 임상시험, 추천 시스템, A/B 테스트에 이르기까지 똑같은 얼굴로 나타난다. 밴딧은 이 딜레마를 가장 순수하게 증류한 모형이다.

2. 문제 설정[편집]

$K$ 개의 팔이 있고, 팔 $k$ 를 당기면 미지의 분포에서 보상 $r$ 이 나온다. 그 분포의 평균을 $\mu_k$ , 그중 최선을 $\mu^* = \max_k \mu_k$ 라 하자. 매 라운드 $t=1,\dots,T$ 에 팔 $a_t$ 를 골라 보상 $r_t$ 를 받고, 그 팔의 보상만 관측한다(고르지 않은 팔이 무엇을 줬을지는 영영 모른다 — 이 부분관측이 밴딧을 강화학습의 축소판이자 그 나름의 어려움으로 만든다).

밴딧에도 갈래가 있다. 각 팔의 분포가 고정된 확률적(stochastic) 밴딧이 기본이고, 보상을 적이 마음대로 정하는 적대적(adversarial) 밴딧, 라운드마다 부가정보(특징)가 주어지는 문맥(contextual) 밴딧이 대표적 변형이다. 이 문서는 확률적 밴딧을 중심에 두고 나머지로 넓혀 간다.

3. 후회 — 무엇을 최소화하는가[편집]

성능은 보상의 절대량이 아니라 후회(regret)로 잰다 — 매 라운드 최적 팔을 당겼다면 얻었을 보상과 실제 사이의 누적 격차다.

R_T \;=\; \sum_{t=1}^{T}\big(\mu^* - \mu_{a_t}\big) \;=\; \sum_{k:\,\Delta_k>0} \Delta_k\, \mathbb{E}[N_k(T)]

여기서 $\Delta_k = \mu^* - \mu_k$ 는 팔 $k$ 의 차선 간격(suboptimality gap), $N_k(T)$ 는 $T$ 라운드 동안 그 팔을 당긴 횟수다. 오른쪽 등식이 핵심 통찰이다 — 후회는 결국 열등한 팔을 몇 번이나 당겼느냐로 결정된다. 좋은 알고리즘의 목표는 “각 열등한 팔의 당김 횟수를 최소로 억제하되, 그것이 열등하다는 것을 알아낼 만큼은 당기는” 것이다.

후회가 $T$ 에 선형이면( $R_T \propto T$ ) 재앙이다 — 매 라운드 평균적으로 손해를 본다는 뜻이니 아무것도 못 배운 것이다. 반대로 후회가 로그( $\ln T$ )로만 자라면, 라운드당 평균 후회 $R_T/T$ 가 0으로 가므로 사실상 최적을 학습한 것이다. 그래서 밴딧 이론의 성배는 로그 후회다.

4. 하한 — Lai–Robbins[편집]

얼마나 잘할 수 있는가에는 정보이론적 천장이 있다. 라이와 로빈스(1985)는 어떤 “합리적인”(일관된) 알고리즘도 다음을 밑돌 수 없음을 증명했다.

\liminf_{T\to\infty}\frac{\mathbb{E}[R_T]}{\ln T}\;\ge\;\sum_{k:\,\Delta_k>0}\frac{\Delta_k}{\mathrm{KL}(\theta_k,\theta^*)}

읽는 법은 이렇다. 팔 $k$ 가 최적이 아님을 통계적으로 확신하려면 그 팔을 최소 $\sim \ln T / \mathrm{KL}(\theta_k,\theta^*)$ 번은 당겨 봐야 한다 — 두 분포의 쿨백-라이블러 발산이 작을수록(구별이 어려울수록) 더 많이 당겨야 한다. 후회의 로그 성장은 피할 수 없는 정보 비용이라는 것이 이 하한의 메시지다. 이후 모든 좋은 알고리즘은 “이 하한을 상수배까지 달성하는가”로 평가받는다.

5. 정책 — 탐험을 설계하는 세 가지 방식[편집]

ε-그리디·UCB1·톰슨 샘플링을 같은 6-팔 베르누이 인스턴스·같은 보상 난수로 돌려 누적 후회 R(t)=t·μ*−Σr 를 겹쳐 그린다(200 실현 앙상블). t=16000 에서 톰슨 64·UCB1 334·ε-그리디 401 — 톰슨/UCB1 은 로그, 고정 ε 은 선형이라 Δ=0.08 에서 t≈11400 부근에 ε-그리디가 UCB1 을 추월한다. 상단 패널은 후회가 어느 팔에서 왔는지 방문수로 분해한다.

밴딧 알고리즘은 탐험을 어떻게 짜 넣느냐로 갈린다. 세 가지 대표 철학이 있다.

5.1. ε-탐욕 (ε-greedy)[편집]

가장 단순하다. 확률 $1-\varepsilon$ 로 현재 표본평균이 가장 높은 팔을(활용), 확률 $\varepsilon$ 로 아무 팔이나 무작위로 당긴다(탐험).

a_t = \begin{cases} \arg\max_k \hat\mu_k & \text{확률 } 1-\varepsilon \\ \text{무작위 팔} & \text{확률 } \varepsilon \end{cases}

구현이 한 줄이고 어디서나 통하지만 두 결함이 있다. 첫째, $\varepsilon$ 을 고정하면 후회가 선형으로 자란다( $\varepsilon T/K$ 만큼은 영원히 무작위 낭비). 둘째, 탐험이 무차별적이다 — 명백히 나쁜 팔에도 좋은 팔과 똑같은 탐험을 쓴다. 첫째 결함은 $\varepsilon_t \sim 1/t$ 로 시간에 따라 식히면 로그 후회에 도달할 수 있지만(Auer 외 2002), 냉각 속도를 사람이 맞춰야 한다는 부담이 남는다.

5.2. UCB1 — 낙관으로 탐험[편집]

더 영리한 발상은 불확실성 앞에서 낙관(optimism in the face of uncertainty)이다. 각 팔에 대해 표본평균에 신뢰구간의 폭만큼 보너스를 더한 상계를 만들고, 그 상계가 가장 큰 팔을 당긴다.

a_t = \arg\max_k \left(\hat\mu_k + \sqrt{\frac{2\ln t}{N_k}}\right)

발상이 우아하다 — 적게 당겨 본 팔은 $N_k$ 가 작아 보너스가 크므로 “혹시 좋을지 모른다”며 자동으로 탐험되고, 많이 당겨 본 팔은 보너스가 줄어 표본평균이 그대로 드러난다. 탐험량이 불확실성에 정확히 비례하는 것이다. 보너스 항은 호에프딩 부등식에서 나오는데, $N_k$ 번 관측한 평균이 참값에서 벗어날 확률의 상한을 뒤집으면 저 $\sqrt{\ln t / N_k}$ 폭이 떨어진다. 아우어·체사-비앙키·피셔(2002)는 UCB1의 후회가

\mathbb{E}[R_T] \le \sum_{k:\Delta_k>0}\frac{8\ln T}{\Delta_k} + O(1)

로 로그 성장함을 증명했다 — 라이-로빈스 하한과 같은 차수다(상수는 최적이 아니지만). 튜닝 파라미터 없이 로그 후회를 보장하는 이 결과가 UCB를 밴딧의 표준 기준선으로 만들었다.

5.3. 톰슨 샘플링 — 사후분포로 탐험[편집]

세 번째는 불확실성을 난수로 바꾸는 베이즈 방식이다. 각 팔의 보상 파라미터에 사후분포를 두고, 매 라운드 각 팔에서 표본을 하나씩 뽑아 가장 큰 팔을 당긴다. 그러면 “그 팔이 실제로 최적일 사후확률”과 정확히 같은 비율로 각 팔이 선택된다(확률 일치). UCB의 결정론적 보너스를 확률적 표본으로 대체한 셈이며, 실측 성능·배치/지연 강건성·튜닝 없음이라는 장점 때문에 온라인 시스템에서 자주 UCB를 이긴다. 유도·후회 한계·구현·언제 쓰면 안 되는지까지는 톰슨 샘플링 문서가 전담하므로 여기서 반복하지 않는다.

세 정책을 같은 보상 스트림 위에서 돌려 누적 후회를 비교하면, 대체로 톰슨 ≲ UCB1 ≪ 고정 ε-탐욕의 순서가 나온다. 위 시뮬이 그 곡선을 그린다.

6. 적대적 밴딧 — 가정이 무너질 때[편집]

지금까지는 각 팔의 보상 분포가 고정됐다고 가정했다. 그 가정이 성립하지 않는 경우(보상이 시간에 따라 변하거나, 심지어 적이 우리 알고리즘을 알고 최악으로 정하는 경우)를 다루는 것이 적대적 밴딧이다. 여기서는 표본평균이나 사후분포가 무의미하고, 대신 후회를 최소화하는 순수 온라인 학습으로 접근한다.

대표 알고리즘 EXP3(Exponential-weight for Exploration and Exploitation)는 각 팔에 지수 가중치를 두고, 관측한 보상을 선택확률로 나눠(중요도 가중) 편향 없이 갱신하며, 균등 탐험을 약간 섞어 모든 팔의 정보를 유지한다. 후회는 $O(\sqrt{TK\ln K})$ 로, 확률적 밴딧의 로그 후회보다 나쁘지만 어떤 적에 대해서도 성립하는 강건한 보장이다. 이 계열의 뿌리는 전문가 조언 통합의 헤지 알고리즘이며, 밴딧은 그 부분관측판이다.

7. 문맥 밴딧 — 상황을 아는 밴딧[편집]

현실의 추천·광고는 “빈” 밴딧이 아니다. 매 라운드 사용자 특징·시간·기기 같은 문맥 $x_t$ 가 주어지고, 최적 팔이 문맥에 따라 달라진다. 이것이 문맥 밴딧(contextual bandit)이다. 보상을 문맥의 함수로 모형화하고( $\mathbb{E}[r\mid a,x]=x^\top\theta_a$ 같은 선형 모형이 흔하다) 그 위에서 UCB(LinUCB)나 톰슨 샘플링을 돌린다. 문맥 밴딧은 지도학습(문맥→보상 예측)과 밴딧(탐험)의 교배종이며, 전면적 강화 학습으로 가는 징검다리다.

8. A/B 테스트와의 관계[편집]

밴딧의 가장 실용적인 얼굴이 A/B 테스트의 적응적 대안이다. 고전적 A/B 테스트는 트래픽을 고정 비율(50:50)로 나눠 정해진 기간 동안 관측한 뒤 승자를 고른다 — 그 기간 내내 열등한 안에도 절반의 트래픽을 계속 보내는 것이 후회의 관점에서는 낭비다. 밴딧은 데이터가 쌓일수록 우월한 안으로 트래픽을 적응적으로 옮겨 이 낭비(=후회)를 줄인다.

공짜는 아니다. 적응적 배분은 트래픽 비율이 시간에 따라 변하므로 단순 평균 비교에 편향이 생기고, 통계적 검정력·재현성·감사 로그가 고정 배분보다 까다로워진다. 그래서 실무는 “빨리 이득을 회수하고 싶다(밴딧)“와 “결과를 깨끗하게 검정하고 싶다(고정 A/B)” 사이에서 목적에 따라 고른다.² 또 밴딧의 목표가 누적 보상 최대화임을 잊으면 안 된다 — “실험이 끝난 뒤 최선의 안을 자신 있게 지목하라”가 목표라면(순수 탐색), 밴딧이 아니라 최적 팔 식별(best-arm identification) 알고리즘을 써야 한다.

9. MDP 안에서의 자리[편집]

밴딧은 **상태가 하나뿐인 마르코프 결정 과정**으로 볼 수 있다 — 행동(팔)이 다음 상태에 영향을 주지 않고 즉시 보상만 줄 때가 밴딧이다. 반대로 행동이 상태를 바꾸고 보상이 여러 스텝 뒤에나 오는 일반적 순차 결정이 강화 학습이다. 그래서 밴딧에서 다듬은 탐험 원리(낙관·사후표본추출)가 강화학습의 탐험 전략으로 그대로 승격된다. 한편 상태 전이는 없지만 팔의 상태가 당길 때마다 진화하는 기틴스 지수(Gittins index)로 풀리는 마르코프 밴딧은, 할인 보상 아래 최적 정책이 각 팔의 지수 비교로 분해된다는 아름다운 결과를 남겼다 — 다만 계산이 무겁고 유한기간·비할인에서는 최적성이 깨져 실무에서는 UCB·톰슨에 자리를 내줬다.

10. 관련 문서[편집]

“밴딧(bandit)“은 슬롯머신의 속어다. 돈을 야금야금 털어 가는 것이 노상강도 같다고 붙은 별명. 그러니 “multi-armed bandit”은 직역하면 “여러 팔 달린 노상강도”인데, 학술 용어 중 가장 밈스러운 작명 중 하나로 꼽힌다. 로빈스(Herbert Robbins)가 1952년 이 문제를 정식화하며 도박 비유를 학계에 들여왔다. ↩
밴딧을 켜자고 하면 데이터 분석가가 반드시 하는 질문이 “그럼 유의성 검정은 어떻게 하죠”다. 정답은 “그냥은 안 됩니다”에 가깝다 — 적응적으로 수집된 데이터는 표본이 독립이 아니라 옛 검정 가정이 깨진다. 그래서 실무에서는 밴딧으로 트래픽을 옮기되 소량의 고정 배분(exploration bucket)을 남겨 깨끗한 검정용 데이터를 따로 확보하는 절충이 흔하다. 세상에 공짜 점심은 없고, 여기서는 통계적 순수성이 값이다. ↩