Kwangmin Kim - Multi-Armed Bandit 문제 정의

출처

이 글은 교재 직접 참조 없이 agent 사전학습 기반으로 작성되었다. 핵심 정리·논문 인용은 검증 가능한 원논문 (Robbins 1952, Lai & Robbins 1985, Auer et al. 2002, Thompson 1933 등) 에 한해 명시한다 (교재 미확인 — agent 사전학습 기반).

이 글은 Phase I (Multi-Armed Bandit) 시리즈 8 편의 첫 글이다. 이후 글에서 ε-greedy, UCB, Thompson Sampling, Contextual Bandit 같은 알고리즘 을 다루기 전에, 본 글은 문제 자체 의 정의와 trade-off 를 정리한다.

1 진입 직관 — 슬롯 머신의 딜레마

도박장에 들어간 한 명의 도박자. 앞에는 K 대의 슬롯 머신 (one-armed bandit) 이 있다. 각 머신은 서로 다른 평균 상금 을 지급하지만, 도박자는 어느 머신이 가장 좋은지 모른다. 도박자에게 N 회의 게임 기회가 있을 때, 총 상금을 최대화 하려면 어떻게 해야 하는가?

핵심 trade-off: 한 머신을 계속 당기면 (exploitation) — 그 머신이 진짜 최선인지 모른다. 여러 머신을 번갈아 당기면 (exploration) — 현재 좋아 보이는 머신의 보상을 놓친다.

이 단순한 비유에 통계 추론·강화학습·실험 설계 가 모두 압축되어 있다. 슬롯 머신을 광고 배너, 추천 아이템, 임상 처치 로 바꾸면 그대로 실무 문제가 된다.

비유 — 식당 선택: 새 동네로 이사 온 후 점심 식당 선택. 한 번 가본 괜찮은 곳 에 계속 갈 수도 있고, 새 곳 시도 도 가능. 계속 가본 곳 만 가면 더 좋은 곳을 영영 모른다. 모든 식당을 한 번씩 시도하면 맛없는 점심 을 여러 번 감수해야 한다. MAB 의 핵심 딜레마.

2 정의: Multi-Armed Bandit 문제

정의: K-Armed Bandit Problem

K 개의 팔 (arm) 이 있고, 각 팔 \(a \in \{1, ..., K\}\) 를 당기면 확률 분포 \(\nu_a\) 에서 reward \(X_a\) 추출. 학습자는:

각 시점 \(t = 1, ..., N\) 에 팔 하나 \(A_t\) 선택
Reward \(X_t \sim \nu_{A_t}\) 관찰
총 누적 보상 \(\sum_{t=1}^N X_t\) 를 최대화

핵심 가정 (가장 단순한 경우 — Stochastic Stationary MAB):

i.i.d.: 같은 팔의 reward 는 독립·동일 분포
Stationary: 분포 \(\nu_a\) 가 시간에 따라 불변
Bounded: \(X_a \in [0, 1]\) 또는 finite variance

이 가정의 변형이 Non-stationary MAB, Adversarial MAB, Contextual MAB 등으로 이어진다.

수식 직관: 각 팔의 진짜 평균 보상 \(\mu_a = \mathbb{E}[X_a]\) 는 학습자에게 알려지지 않음. 학습자가 알 수 있는 것은 시도해본 팔에서 관찰한 표본 평균 뿐. 그러나 표본이 적으면 추정치 분산이 큼 — 진짜 최선의 팔을 오인할 수 있음.

3 Reward 분포 가정 — 4 가지 변형

3.1 Stochastic Stationary (가장 단순)

각 팔이 고정된 확률 분포 를 가지고, 시간에 따라 변하지 않음. 본 시리즈의 ε-greedy, UCB, Thompson Sampling 모두 이 가정 하에서 분석.

3.2 Adversarial

각 시점의 reward 가 적대자 (adversary) 에 의해 결정. 학습자가 어떤 팔을 선택할지 예측하여 가장 불리한 reward 부여 가능. 알고리즘: Exp3 (Auer et al. 2002).

3.3 Contextual (Phase I-6 에서 다룸)

각 시점에 context 벡터 \(x_t\) 관찰. Reward 가 context 와 팔의 함수 — \(\mathbb{E}[X_a | x_t]\). 알고리즘: LinUCB (Li et al. 2010).

3.4 Non-stationary (Phase I-7 에서 다룸)

분포 \(\nu_a\) 가 시간에 따라 변함. Sliding window UCB, Discounted UCB 등으로 처리.

반사실 — 가정의 위반: 만약 stationary 알고리즘 (UCB) 을 non-stationary 환경 에 사용하면? 변경된 분포에 적응 못 함 → 과거 데이터에 묶임 → 실제 최선의 팔을 영원히 놓칠 수 있음. 가정과 알고리즘 매칭이 결정적.

4 Regret — 성능 측정의 두 종류

알고리즘 성능을 측정하는 핵심 지표는 regret (후회). “최선의 팔을 알았더라면 받았을 보상” 과 실제 받은 보상 의 차이.

4.1 Cumulative Regret (누적 후회)

정의: Cumulative Regret

\[ R_N = N \cdot \mu^* - \mathbb{E}\left[\sum_{t=1}^N X_t\right] \]

여기서 \(\mu^* = \max_a \mu_a\) 는 최선의 팔의 진짜 평균.

\(N \cdot \mu^*\): 처음부터 최선의 팔만 당겼을 때의 기대 총 보상
\(\mathbb{E}\left[\sum X_t\right]\): 알고리즘이 실제 받은 기대 총 보상
\(R_N\): 학습 비용 (= 탐색을 위해 지불한 보상 손실)

수식 직관: \(R_N\) 이 작을수록 좋은 알고리즘. 0 은 불가능 (탐색 자체에 비용 필요). 핵심 질문: \(N\) 이 커질 때 \(R_N\) 이 어떻게 증가하는가?

4.2 Simple Regret (단순 후회)

정의: Simple Regret

\[ r_N = \mu^* - \mu_{\hat{A}_N} \]

여기서 \(\hat{A}_N\) 은 학습 종료 후 최종 추천하는 팔.

\(r_N\): 마지막 추천이 얼마나 최선과 가까운가
누적 보상은 무시 — 마지막 추천만 평가

차이의 직관:

Cumulative regret: “도박장에서 총 얼마를 잃었나” — 실시간 의사결정

Simple regret: “탐색 끝에 어느 팔을 추천할 것인가” — pure exploration

4.3 두 regret 의 응용 맥락

문제	적합한 regret	사례
광고 배너 노출 (계속 수익 발생)	Cumulative	매 노출마다 매출 — 학습 중에도 손해 최소화
신약 후보 선정 (시험 종료 후 1 개 채택)	Simple	임상시험 후 1 개 약 선택 — 시험 중 보상은 무관
추천 시스템 (실시간 사용자)	Cumulative	매 사용자에게 좋은 추천
A/B 테스트 (실험 후 1 개 variant 채택)	Simple	실험 후 최선의 variant 만 배포

반사실: Cumulative regret 알고리즘 (UCB) 을 simple regret 문제 (best arm identification) 에 쓰면 비효율. UCB 는 최선 근처에서 모험 을 줄이지만, simple regret 에서는 명확히 분리되도록 더 공격적 탐색 필요. Phase I-8 에서 깊이.

5 Exploration vs Exploitation — 본질적 trade-off

공식 표현: 어떤 알고리즘이든 현재 추정 최선의 팔 을 당기는 것 (exploitation) 과 덜 시도된 팔 을 당기는 것 (exploration) 사이에서 선택.

5.1 양 극단의 함정

5.1.1 Pure Exploitation (탐색 전혀 없음)

첫 번째 시도에서 우연히 좋은 reward 받은 팔만 영원히 당김. 진짜 최선의 팔을 영영 발견 못 할 수 있음.

사례: 첫 시도에서 팔 A 가 reward 1, 팔 B 도 1 회 시도했는데 reward 0 이라고 가정. 진짜 평균은 A 가 0.3, B 가 0.7 이라도, 알고리즘은 A 가 좋다고 잘못 판단 → A 만 계속 당김 → cumulative regret 선형 증가 (\(O(N)\)).

5.1.2 Pure Exploration (활용 전혀 없음)

모든 팔을 균등 확률 로 당김. 학습한 정보를 사용 안 함 → 평균 reward 가 모든 팔의 평균 → cumulative regret 선형 (\(O(N)\)).

결론: 양 극단 모두 cumulative regret 선형. 의미 있는 알고리즘은 둘의 절충.

5.2 좋은 알고리즘의 조건

목표: \(R_N = O(\log N)\) — cumulative regret 이 시간 \(N\) 의 로그 함수. 즉 시간이 지날수록 추가 regret 이 거의 0 으로 수렴.

수식 직관:

\(O(N)\): 매 시점 고정된 비용 의 regret. 학습이 효과 없음.

\(O(\sqrt{N})\): 점진적 학습. Adversarial bandit 의 흔한 bound.

\(O(\log N)\): 최적 (Lai-Robbins 하한). Stochastic stationary 의 가능 최선.

\(O(1)\): 불가능 (탐색 자체에 비용 필요).

6 Lai-Robbins 의 하한 정리 (1985)

Lai & Robbins (1985) 가 증명한 stochastic stationary MAB 의 cumulative regret 하한.

정리 (informal): 어떤 합리적 알고리즘이든 다음을 만족.

\[ \liminf_{N \to \infty} \frac{R_N}{\log N} \geq \sum_{a: \mu_a < \mu^*} \frac{\mu^* - \mu_a}{\text{KL}(\nu_a \| \nu^*)} \]

여기서 \(\text{KL}\) 은 Kullback-Leibler divergence.

함의: 어떤 알고리즘도 \(\log N\) 보다 빠르게 regret 을 줄일 수 없음. UCB, Thompson Sampling 모두 이 하한에 상수배 이내 도달.

직관: 한 suboptimal 팔을 충분히 많이 시도해서 진짜 최선이 아님 을 충분히 확신 하려면 — Hoeffding/KL 부등식에 의해 시도 횟수 ∝ log N 필요. 따라서 suboptimal 팔에 누적된 regret ∝ log N.

6.1 왜 log N 이 자연스러운가

확률 직관: \(N\) 회 시도 후 suboptimal 팔의 평균이 진짜 평균 근처에 있을 확률 을 \(1 - 1/N\) 로 만들려면, Chernoff/Hoeffding 부등식으로 \(\log N\) 회 시도 필요. 이 \(\log N\) 회의 시도가 regret 의 누적 비용. 다른 어떤 비율도 이 정보 한계를 깨지 못함.

7 알고리즘의 위계 (다음 글들 미리 보기)

알고리즘	Cumulative Regret	글
Pure exploitation / random	\(O(N)\)	(불용)
ε-greedy (fixed ε)	\(O(N)\)	I-2
ε-greedy (decaying ε ∝ 1/t)	\(O(\log N)\)	I-2
UCB1	\(O(\log N)\)	I-3
Thompson Sampling	\(O(\log N)\)	I-4
Adversarial Exp3	\(O(\sqrt{N})\)	(Phase J)

핵심 결과: Stochastic stationary 환경에서 UCB·Thompson 모두 Lai-Robbins 하한 달성. 즉 이론적으로 최적. 차이는 상수 배 + 실용성.

8 A/B Test 와의 본질적 차이

측면	A/B Test	MAB
목표	효과 크기 정확 추정	총 보상 최대화
운영	고정 기간 + 균등 할당	적응적 할당
학습 시점	실험 종료 후	실시간
학습 비용	균등 할당의 기회비용	탐색의 regret
적합 regret	Simple	Cumulative
결정 단위	전체 모집단	각 사용자

상호 보완:

A/B test 는 효과의 통계적 유의성 검증 (Phase F 의 주제)

MAB 는 실시간 보상 최적화

둘은 다른 질문 에 답함

반사실: 신약 임상시험에서 MAB 적용 시 — 실시간으로 효과 좋아 보이는 약을 더 많은 환자에게. 윤리적 매력 있지만 최종 효과 추정 정밀성 약해짐. 규제기관은 고정 할당 RCT 선호 (Phase C 시리즈 참조). MAB 는 임상시험 외 영역에서 더 적합.

9 슬롯 머신을 넘어 — 응용 영역

9.1 1. 광고 추천

각 광고 배너 = 팔. 클릭률 = reward. 새 광고를 충분히 시도 + 좋은 광고에 트래픽 집중.

9.2 2. 추천 시스템

각 아이템 = 팔. 클릭/구매 = reward. Cold-start 문제 해결 (새 아이템도 시도).

9.3 3. 임상시험 (response-adaptive randomization)

각 처치 = 팔. 환자 반응 = reward. 윤리적 매력 (효과 좋은 약을 더 많이) 있지만 통계적 trade-off 큼.

9.4 4. 게임 트리 검색 (MCTS)

Move = 팔. 승률 = reward. AlphaGo 의 핵심 구성 요소.

9.5 5. 금융 포트폴리오

각 자산 = 팔. 수익률 = reward. Non-stationary + adversarial 변형 흔함.

공통 패턴: 제한된 자원으로 여러 옵션을 평가하면서 동시에 보상 최대화. 이 한 줄이 MAB 의 모든 응용을 통합.

10 시뮬레이션 — 두 극단 비교

import numpy as np
import matplotlib.pyplot as plt

np.random.seed(42)

# 환경 설정: K = 5 팔, 각 팔 Bernoulli reward
K = 5
true_means = np.array([0.30, 0.50, 0.70, 0.40, 0.60])
mu_star = true_means.max()   # 0.70
N = 2000

def pure_exploit(true_means, N):
    """첫 번째 sample 만으로 최선 결정 후 그 팔만 당김."""
    K = len(true_means)
    rewards = np.zeros(N)
    pulls = np.zeros(K, dtype=int)
    sums = np.zeros(K)

    # 각 팔 1 회 시도
    for a in range(K):
        r = np.random.binomial(1, true_means[a])
        rewards[a] = r
        sums[a] += r
        pulls[a] += 1

    # 이후 평균 최대 팔만 당김
    means = sums / np.maximum(pulls, 1)
    best = means.argmax()
    for t in range(K, N):
        rewards[t] = np.random.binomial(1, true_means[best])
    return rewards

def pure_explore(true_means, N):
    """모든 팔 균등 확률."""
    K = len(true_means)
    rewards = np.zeros(N)
    for t in range(N):
        a = np.random.randint(K)
        rewards[t] = np.random.binomial(1, true_means[a])
    return rewards

def cumulative_regret(rewards, mu_star):
    """매 시점의 누적 regret."""
    optimal = np.arange(1, len(rewards) + 1) * mu_star
    actual = np.cumsum(rewards)
    return optimal - actual

n_sim = 100
exploit_regrets = np.zeros((n_sim, N))
explore_regrets = np.zeros((n_sim, N))

for s in range(n_sim):
    exploit_regrets[s] = cumulative_regret(pure_exploit(true_means, N), mu_star)
    explore_regrets[s] = cumulative_regret(pure_explore(true_means, N), mu_star)

mean_exploit = exploit_regrets.mean(axis=0)
mean_explore = explore_regrets.mean(axis=0)

print("[100 회 평균 누적 regret — N=2000]")
print(f"Pure Exploit (첫 시도 결정): {mean_exploit[-1]:.1f}")
print(f"Pure Explore (균등 무작위):  {mean_explore[-1]:.1f}")
print(f"이론적 하한 (균등 무작위):   {N * (mu_star - true_means.mean()):.1f}")
print()
print("→ 두 극단 모두 N 에 대해 선형 증가 (O(N))")
print("→ 의미 있는 알고리즘은 다음 글들 (ε-greedy, UCB, Thompson) 에서.")

결과 해석:

Pure Exploit 의 regret 은 첫 시도가 최선의 팔이 아닐 때 영원히 누적. 100 시뮬레이션 평균은 약 200~400 (첫 시도 운에 따라).

Pure Explore 는 균등 무작위 — 매 시점 평균 regret = \(\mu^* - \bar{\mu}\). \(N=2000\) 에서 약 400.

두 모두 선형 증가 — 학습이 효과 없는 알고리즘.

11 IT / 디지털 실험 매핑

MAB 개념	IT 실무 응용
Arm	광고 배너, 추천 아이템, UI variant
Reward	클릭, 구매, 머무는 시간
Cumulative regret	학습 중 잃은 매출
Simple regret	최종 배포 variant 의 차선
Exploration	A/B 테스트의 균등 할당 단계
Exploitation	승자 결정 후 100% 트래픽
Lai-Robbins log N	“minimal exploration cost” 의 이론적 한계

실무 시사점: A/B 테스트와 MAB 를 경쟁 으로 보지 말 것. 어떤 질문에 답하려는가 에 따라 선택. 효과 크기 검증 → A/B. 실시간 매출 최적화 → MAB. Hybrid 접근 (탐색 단계 → A/B, 채택 단계 → MAB) 가능.

12 결론 — Phase I 시리즈의 출발점

MAB 는 제한된 자원으로 학습과 최적화를 동시에 수행 하는 문제의 정통 추상화.

핵심 메시지:

Slot machine 비유 — Exploration vs Exploitation
Stochastic stationary 가정 — 4 변형의 출발점
Cumulative vs Simple regret — 응용 맥락 따라 선택
Lai-Robbins 하한 \(O(\log N)\) — 어떤 알고리즘도 깨지 못함
A/B 테스트와의 차이 — 다른 질문, 다른 도구

다음 글에서 가장 단순한 알고리즘 — ε-greedy — 부터 시작하여 위계를 따라 올라간다.

13 관련 주제

선행 지식

Phase I 후속 글

다른 카테고리 연결

Agent — RAG / 추천 시스템에서의 MAB 활용 (placeholder)
Machine_Learning — Reinforcement Learning 의 contextual bandit 연결 (placeholder)

14 참고문헌

Robbins, H. (1952). Some aspects of the sequential design of experiments. Bull. Amer. Math. Soc. 58, 527-535.
Lai, T. L. & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6, 4-22.
Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25, 285-294.
Auer, P., Cesa-Bianchi, N., Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 235-256.
Lattimore, T. & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. (교재 미확인 — 향후 도서 추가 시 재작성 예정)
Sutton, R. S. & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.