2nd/10_Wiki/Topics/AI_and_ML/Multi-armed-Bandit-Problem.md

---
id: wiki-2026-0508-multi-armed-bandit-problem
title: Multi-armed Bandit Problem
status: verified
canonical_id: wiki-2026-0508-multi-armed-bandit-problem
aliases: [MAB, Multi-Armed Bandit, K-Armed Bandit, Bandit Algorithm]
duplicate_of: none
source_trust_level: A
confidence_score: 0.92
verification_status: applied
tags: [reinforcement-learning, bandit, exploration-exploitation, ab-testing, optimization]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack: [python, numpy, vowpal-wabbit, scikit-learn]
---

# Multi-armed Bandit Problem

## 한 줄 정의

여러 선택지(arm) 중 보상이 최대인 것을 찾되, **탐색(exploration)과 활용(exploitation)의 균형**을 맞추는 순차적 의사결정 문제. 슬롯머신 비유에서 이름이 유래했고, A/B 테스트의 효율적 대안으로 널리 쓰인다. 전통 RL과 달리 상태(state)가 없거나(stateless) context만 있는 경량 형태.

## 핵심

### 기본 알고리즘

- **ε-greedy**: 확률 ε로 무작위 탐색, 1-ε로 최선 arm 선택. 단순·강건.
- **UCB (Upper Confidence Bound)**: 신뢰구간 상한이 가장 큰 arm을 선택. 이론적 후회(regret) 보장 O(log T).
- **Thompson Sampling**: posterior 분포에서 sample → 가장 큰 arm 선택. 베이지안, 실전 성능 최강.
- **Softmax/Boltzmann**: 보상 비례 확률로 sampling.

### Contextual Bandit

각 round마다 context vector x가 주어지고 정책 π(a|x)가 arm을 선택. 추천 시스템·광고 입찰의 표준. **LinUCB**, **Contextual Thompson**, neural bandit 등.

### A/B 테스트와의 차이

A/B 테스트는 고정 트래픽 분할 → 종료 후 승자 채택(2단계). MAB는 학습 중 분배를 동적 조정 → **regret 최소화**, 손실 트래픽 적음. 단 통계적 유의성 보장은 약함.

### 응용

추천(뉴스·콘텐츠), 광고 입찰, 임상시험 적응적 할당, UI 실험, hyperparameter tuning, LLM prompt 선택, RLHF 변형.

## 💻 패턴

### ε-greedy

```python
import numpy as np

class EpsilonGreedy:
    def __init__(self, n_arms, epsilon=0.1):
        self.n = n_arms
        self.eps = epsilon
        self.counts = np.zeros(n_arms)
        self.values = np.zeros(n_arms)

    def select(self):
        if np.random.random() < self.eps:
            return np.random.randint(self.n)
        return int(np.argmax(self.values))

    def update(self, arm, reward):
        self.counts[arm] += 1
        n = self.counts[arm]
        self.values[arm] += (reward - self.values[arm]) / n
```

### UCB1

```python
class UCB1:
    def __init__(self, n_arms):
        self.counts = np.zeros(n_arms)
        self.values = np.zeros(n_arms)

    def select(self):
        t = self.counts.sum() + 1
        # 미시행 arm 우선
        if (self.counts == 0).any():
            return int(np.argmin(self.counts))
        ucb = self.values + np.sqrt(2 * np.log(t) / self.counts)
        return int(np.argmax(ucb))

    def update(self, arm, reward):
        self.counts[arm] += 1
        n = self.counts[arm]
        self.values[arm] += (reward - self.values[arm]) / n
```

### Thompson Sampling (Beta-Bernoulli)

```python
class ThompsonBernoulli:
    def __init__(self, n_arms):
        self.alpha = np.ones(n_arms)  # success + 1
        self.beta_ = np.ones(n_arms)  # failure + 1

    def select(self):
        samples = np.random.beta(self.alpha, self.beta_)
        return int(np.argmax(samples))

    def update(self, arm, reward):  # reward in {0,1}
        self.alpha[arm] += reward
        self.beta_[arm] += 1 - reward
```

### Contextual: LinUCB

```python
class LinUCB:
    def __init__(self, n_arms, d, alpha=1.0):
        self.A = [np.eye(d) for _ in range(n_arms)]
        self.b = [np.zeros(d) for _ in range(n_arms)]
        self.alpha = alpha

    def select(self, x):
        scores = []
        for a in range(len(self.A)):
            A_inv = np.linalg.inv(self.A[a])
            theta = A_inv @ self.b[a]
            score = theta @ x + self.alpha * np.sqrt(x @ A_inv @ x)
            scores.append(score)
        return int(np.argmax(scores))

    def update(self, arm, x, reward):
        self.A[arm] += np.outer(x, x)
        self.b[arm] += reward * x
```

### Regret 측정

```python
def simulate(bandit, true_means, T=10000):
    optimal = max(true_means)
    regret = 0
    history = []
    for _ in range(T):
        a = bandit.select()
        r = np.random.binomial(1, true_means[a])
        bandit.update(a, r)
        regret += optimal - true_means[a]
        history.append(regret)
    return history
```

## 결정 기준

| 상황 | 추천 |
|---|---|
| 단순·빠른 baseline | ε-greedy (ε≈0.1) |
| 이론 보장 필요 | UCB1 |
| 실전 추천·광고 | **Thompson Sampling** |
| context feature 있음 | LinUCB, Contextual Thompson |
| 비정상(non-stationary) 환경 | sliding window UCB, discounted Thompson |
| A/B 대체 (loss 최소화) | Bandit |
| 통계적 유의성 강제 | A/B test |

기본값: **Thompson Sampling**. Contextual이면 **LinUCB**.

## 🔗 Graph

- 부모: [[Reinforcement-Learning]] · [[Online-Learning]]
- 응용: [[Recommendation-Systems]] · [[Hyperparameters|Hyperparameter-Tuning]]

## 🤖 LLM 활용

**언제**: 알고리즘 선택 가이드, regret 분석 코드 리뷰, posterior 도출 sanity check, contextual feature 설계 brainstorm.

**언제 X**: 실서비스 트래픽에 LLM 직접 의사결정 위임 (latency·cost·재현성 문제). Bandit 정책은 결정론적/확률적 코드로 구현하고 LLM은 메타 분석에 한정.

## ❌ 안티패턴

- 비정상 환경에 vanilla UCB1 사용 → 과거 평균에 갇힘. discounted/sliding 변형 필요.
- ε를 너무 크게(>0.3) → 수렴 지연·손실 증가.
- A/B 테스트 신뢰도가 필요한데 Bandit 결과로 p-value 주장.
- Contextual feature가 reward와 무관한데 LinUCB 강행 → 단순 Thompson보다 나쁨.
- Reward delay 무시(클릭 후 conversion까지 시간) → 잘못된 update.

## 🧪 검증 / 중복

Verified source: Sutton & Barto *Reinforcement Learning* Ch.2, Lattimore & Szepesvári *Bandit Algorithms* (2020), Vowpal Wabbit/contextual-bandit 문서. 신뢰도 A.

중복 후보 없음. [[Reinforcement-Learning]]은 부모 개념이고 MAB는 stateless 특수 케이스로 별도 페이지 유지.

## 🕓 Changelog

- 2026-05-08 Phase 1 — 초기 stub.
- 2026-05-10 Manual cleanup — FULL 구조로 재작성. 알고리즘 4종 + LinUCB 코드, regret 시뮬, 결정 기준, 안티패턴 정리.