탐험 심화: ε-탐욕을 넘어 UCB · 톰슨 샘플링 · 후회(regret)

탐험 심화: ε-탐욕을 넘어 UCB · 톰슨 샘플링 · 후회(regret)

모르는 선택지 앞에서 "아는 최선을 쓸까, 새것을 시험할까"는 강화학습의 가장 오래된 고민입니다. 앞 수업의 ε-탐욕은 무작위로 탐험했습니다. 이 수업은 덜 확인된 쪽을 골라 탐험하는 방법 세 가지(낙관적 초깃값 · UCB · 톰슨 샘플링)와, 탐험 전략을 숫자로 비교하는 잣대인 후회(regret) 를 손계산으로 익힙니다.

들어가기 전에

• 강화학습 입문 (Sutton · Barto, 2판) — 2절의 슬롯머신 문제, 표본 평균 갱신 $Q_{n+1}=Q_n+\frac1n(R_n-Q_n)$, ε-탐욕을 그대로 이어 씁니다.
• 확률과 통계 최소한 — 기댓값 · 분산 · 베이즈 정리. 톰슨 샘플링은 베이즈 갱신 그 자체입니다.

한눈에 보기

• ε-탐욕의 약점(가망 없는 손잡이도 똑같이 시험함)을 설명할 수 있습니다.
• UCB 점수 $Q_t(a)+c\sqrt{\ln t / N_t(a)}$ 를 직접 계산하고, $c$ 가 탐험의 세기를 어떻게 바꾸는지 봅니다.
• 성공/실패 횟수만으로 베타 분포를 갱신하는 톰슨 샘플링을 손으로 해 봅니다.
• 후회(regret)로 "탐험을 잘했다"를 숫자로 비교합니다.
• 실무의 A/B 테스트가 밴딧 문제의 한 형태임을 이해합니다.

1. ε-탐욕이 아쉬운 이유

직관(해설용 비유). 새 동네에 식당이 셋 있습니다. 한 곳은 여섯 번 가 봐서 맛을 잘 알고, 한 곳은 딱 한 번 가 봤습니다. ε-탐욕은 탐험할 때 주사위를 굴려 아무 곳이나 갑니다. 이미 잘 아는 곳에 '탐험 삼아' 또 가는 것은 정보가 거의 늘지 않는 낭비입니다. 더 나은 탐험은 아직 잘 모르는 곳, 그런데 좋을 가능성이 남아 있는 곳을 고르는 것입니다.

Sutton · Barto 2.7절도 같은 지적을 합니다. ε-탐욕은 탐욕적이지 않은 행동을 "가리지 않고" 시험하기 때문에, 추정값이 최고에 가까운지 · 불확실성이 큰지를 따지지 않습니다.

이 약점은 두 가지 비용으로 나타납니다.

1. 헛된 탐험: 확실히 나쁜 손잡이도 계속 $\varepsilon/k$ 의 확률로 당깁니다.
2. 끝나지 않는 탐험: ε 이 고정이면 충분히 배운 뒤에도 탐험을 멈추지 않습니다. 그래서 아래 5절에서 보듯 손해가 시간에 비례해 계속 쌓입니다.

2. 낙관적 초깃값: 가장 단순한 요령

직관. "모든 식당이 엄청 맛있을 것"이라고 믿고 시작하면, 어느 곳에 가든 실망하고 다른 곳을 찾아갑니다. 그 결과 탐욕적으로만 골라도 모든 곳을 몇 번씩 들르게 됩니다.

단계.

1. 모든 행동의 초깃값 $Q_1(a)$ 를 실제로 나올 법한 보상보다 훨씬 크게 둡니다.
2. 늘 탐욕적으로(가장 큰 $Q$) 고릅니다.
3. 받은 보상은 초깃값보다 작으므로 그 행동의 $Q$ 가 내려가고, 다음에는 아직 안 내려간 다른 행동이 1등이 됩니다.

책의 예는 10개 손잡이 시험대(각 손잡이의 참값 $q_*(a)$ 를 평균 0 · 분산 1 정규분포에서 뽑음)에서 초깃값을 $+5$ 로 둔 것입니다. 참값 대부분이 $-2\sim2$ 사이이므로 $+5$ 는 "터무니없이 낙관적"입니다. 이 탐욕 방법은 처음에는 탐험을 많이 해서 ε-탐욕($\varepsilon=0.1$, 초깃값 0)보다 못하지만, 탐험이 저절로 줄어들어 결국 더 나아집니다(그림 2.3, 두 방법 모두 고정 걸음 $\alpha=0.1$).

숫자로 해 보기(해설용). 손잡이 둘, 초깃값 $Q_1=5$, $\alpha=0.5$. 손잡이 A를 당겨 보상 1을 받으면 $Q(A)=5+0.5(1-5)=3$. 이제 B($Q=5$)가 더 커서 B를 당깁니다. B에서 보상 2를 받으면 $Q(B)=5+0.5(2-5)=3.5$. 다시 B, … 이렇게 둘 다 자연스럽게 시험됩니다.

한계(책의 평가). 탐험이 "시작할 때 한 번"에 몰려 있어, 보상 분포가 시간에 따라 바뀌는(비정상, nonstationary) 문제에는 도움이 안 됩니다. 간단하고 정상(stationary) 문제에서 꽤 효과적인 요령일 뿐, 일반적인 해법은 아닙니다.

3. UCB: 불확실한 만큼 점수를 얹어 주기

직관. 식당마다 "지금까지 평균 맛 + 아직 모르는 정도"를 점수로 매깁니다. 많이 가 본 곳은 '모르는 정도'가 작고, 한 번 가 본 곳은 큽니다. 점수가 가장 높은 곳에 갑니다. "의심스러우면 좋게 봐 준다(optimism in the face of uncertainty)"는 원리입니다.

책의 식 (2.10)은 다음과 같습니다.

왜 이 꼴인가. $a$ 를 고를 때마다 $N_t(a)$ 가 커져 덧셈 몫이 줄어듭니다. 다른 행동을 고르는 동안에는 $t$ 만 커져 덧셈 몫이 조금씩 다시 늘어납니다. 로그라서 늘어나는 속도는 점점 느려지지만 끝이 없으므로, 모든 행동이 결국 다시 시험되고 나쁜 행동은 점점 드물게 시험됩니다.

숫자로 해 보기(해설용). $t=10$, $\ln 10 \approx 2.303$. 세 손잡이의 현재 기록이 아래와 같다고 합시다.

$c=1$ 이면 평균은 가장 낮지만 한 번밖에 안 본 C를 고릅니다(탐험). $c=0.2$ 면 불확실성 몫이 작아져 평균이 가장 높은 A를 고릅니다(활용). $c$ 가 탐험과 활용의 저울추입니다.

UCB1과의 관계. Auer · Cesa-Bianchi · Fischer(2002)의 UCB1은 보상이 $[0,1]$ 범위일 때 평균 $+\sqrt{2\ln n / n_j}$ 를 점수로 씁니다($n$ 은 전체 횟수, $n_j$ 는 손잡이 $j$ 의 횟수). 책의 식에서 $c=\sqrt2\approx1.414$ 로 둔 것과 같은 꼴이며, 이 논문은 이 규칙의 기대 후회가 모든 시점에서 $\ln n$ 에 비례하는 상한을 가진다는 것을 보였습니다.

한계(책의 평가). 10개 손잡이 시험대에서는 UCB가 ε-탐욕보다 대체로 좋지만(그림 2.4, $c=2$ 대 $\varepsilon=0.1$), 비정상 문제나 상태가 아주 많은 일반 강화학습(함수 근사)으로 넓히기는 어렵다고 책은 말합니다. 그래서 딥 강화학습에서는 UCB를 그대로 쓰기보다, 방문 횟수 대신 '새로움'을 근사하는 탐험 보너스 같은 변형이 연구됩니다. 한편 트리 탐색(MCTS)에서는 UCB가 핵심 부품으로 살아남았습니다 — 뒤의 수업 모델 기반 강화학습과 계획 에서 다룹니다.

4. 경사 밴딧: 가치 대신 선호도를 배우기

가치를 추정하지 않고, 행동마다 선호도(preference) $H_t(a)$ 를 두고 소프트맥스로 확률을 만드는 방법도 있습니다(책 2.8절).

행동 $A_t$ 를 하고 보상 $R_t$ 를 받으면, 기준값 $\bar R_t$(지금까지의 평균 보상)와 비교해 갱신합니다.

숫자로 해 보기(해설용). 손잡이 둘, $H=(0,0)$ 이라 $\pi=(0.5,0.5)$. A를 골라 $R=1$, 기준값 $\bar R=0.5$, $\alpha=0.1$ 이면 $H(A)=0+0.1\times0.5\times0.5=0.025$, $H(B)=-0.025$. 새 확률은 $\pi(A)=1/(1+e^{-0.05})\approx0.512$ 입니다. 평균보다 잘 나온 행동은 확률이 오르고, 나머지는 반대로 내려갑니다.

책은 이 갱신이 기대 보상의 기울기를 따르는 확률적 경사 상승의 한 예임을 보입니다. 바로 정책 경사 의 가장 작은 판(상태가 하나뿐인 경우)이고, 기준값을 빼는 이유도 정책 경사의 기준값과 같습니다. 책 그림 2.5는 참값을 모두 $+4$ 근처로 올린 시험대에서 기준값을 빼지 않으면 성능이 크게 떨어지는 것을 보여 줍니다.

5. 후회(regret): 탐험 전략을 재는 잣대

직관. "처음부터 최고의 손잡이만 알고 당겼다면 받았을 보상"과 "실제로 받은 보상"의 차이가 후회입니다. 배우는 동안 치른 수업료라고 보면 됩니다.

Auer 외(2002)의 정의를 쉬운 기호로 쓰면 다음과 같습니다.

숫자로 해 보기(해설용). 참값이 $\mu=(0.7,\ 0.5,\ 0.2)$ 이고 100번 중 (80, 15, 5)번 당겼다면 후회는 $15\times0.2 + 5\times0.5 = 5.5$ 입니다.

고정 ε 의 후회는 계속 쌓입니다. $\varepsilon=0.1$ 이면 최고 손잡이를 완벽히 알아낸 뒤에도 매번 0.1의 확률로 무작위 손잡이를 당깁니다. 위 예에서 한 번당 평균 손해는 $0.1\times(0+0.2+0.5)/3\approx0.023$ 이라, 1,000번이면 약 23, 10,000번이면 약 233으로 시간에 비례해 늘어납니다. UCB1은 이것을 $\ln n$ 에 비례하는 수준으로 묶습니다. Lai · Robbins(1985)는 일정한 조건에서 어떤 방법이든 후회가 적어도 $\ln n$ 에 비례해 늘어난다는 하한을 보였으므로, 로그 후회가 "잘하는 탐험"의 기준이 됩니다.

6. 톰슨 샘플링: 믿음에서 하나 뽑아 행동하기

직관. 식당마다 "맛있을 확률에 대한 내 믿음"을 분포로 들고 다닙니다. 매번 각 분포에서 숫자를 하나씩 뽑아 보고, 가장 큰 숫자가 나온 식당에 갑니다. 많이 가 본 식당의 분포는 좁아서 늘 비슷한 숫자가 나오고, 덜 가 본 식당의 분포는 넓어서 가끔 큰 숫자가 튀어나옵니다. 그래서 불확실한 곳은 그 불확실성만큼 자주 시험됩니다. Sutton · Barto 2장의 참고 문헌 노트는 이 생각의 기원을 Thompson(1933, 1934)으로 소개합니다.

단계(성공/실패 보상, 베타-베르누이 판).

1. 손잡이마다 믿음을 베타 분포 $\mathrm{Beta}(\alpha,\beta)$ 로 둡니다. 처음엔 $\mathrm{Beta}(1,1)$ = 0~1 균등분포.
2. 매번 각 손잡이에서 $\hat\theta_j \sim \mathrm{Beta}(\alpha_j,\beta_j)$ 를 하나 뽑습니다.
3. $\hat\theta_j$ 가 가장 큰 손잡이를 당깁니다.
4. 성공이면 $\alpha_j \leftarrow \alpha_j+1$, 실패면 $\beta_j \leftarrow \beta_j+1$.

숫자로 해 보기(해설용). 광고 문구 A는 40번 보여 30번 클릭, B는 1번 보여 1번 클릭되었습니다.

• A: $\mathrm{Beta}(31,11)$, 평균 $31/42\approx0.738$, 표준편차 $\approx0.067$
• B: $\mathrm{Beta}(2,1)$, 평균 $2/3\approx0.667$, 표준편차 $\approx0.236$

평균만 보면 A가 낫지만, B가 뽑힐 확률 $P(\hat\theta_B>\hat\theta_A)$ 를 계산해 봅시다. $\mathrm{Beta}(2,1)$ 은 $P(\hat\theta_B > x)=1-x^2$ 이므로 $P=1-\mathbb{E}[\hat\theta_A^2]$ 이고, $\mathbb{E}[\hat\theta_A^2]=\frac{31\cdot32}{42\cdot43}\approx0.549$ 입니다. 따라서 약 45% 의 확률로 B를 시험합니다(시뮬레이션 400만 번으로도 0.451). 증거가 쌓여 B의 분포가 좁아지면 이 비율은 B의 실제 실력에 맞게 줄어듭니다.

왜 인기가 있나. Russo 외의 튜토리얼은 톰슨 샘플링을 계산이 가볍고 널리 쓰이는 방법으로 소개하고, 한 행동의 결과가 다른 행동에 대한 정보도 주는 문제까지 다룹니다. 예로 드는 문제는 슬롯머신, 최단 경로, 상품 추천, 상품 구성 선택, 신경망 능동 학습, MDP 강화학습 등입니다. 구현 면에서도 베타-베르누이 판은 사전 분포 하나만 정하면 되고 갱신이 덧셈 한 번이라, ε 이나 $c$ 같은 탐험 상수를 따로 맞출 필요가 없습니다.

12345678flowchart LR
  A[손잡이마다 믿음 분포<br/>Beta α, β] --> B[각 분포에서<br/>θ̂ 하나씩 뽑기]
  B --> C[θ̂ 가 가장 큰<br/>손잡이 당기기]
  C --> D{성공?}
  D -- 예 --> E[α ← α+1]
  D -- 아니오 --> F[β ← β+1]
  E --> A
  F --> A

7. 맥락 밴딧과 A/B 테스트

맥락 밴딧(contextual bandit). 손잡이를 고르기 전에 상황 정보(사용자 나이대, 시간대 등)를 보고 고르는 판입니다. 책 2.9절은 이것을 연관 탐색(associative search)이라 부르며, 행동이 다음 상황에까지 영향을 주면 완전한 강화학습 문제가 된다고 설명합니다. 즉 밴딧 → 맥락 밴딧 → MDP 순으로 문제가 넓어집니다.

A/B 테스트와의 관계. 고전적 A/B 테스트는 정해진 기간 동안 트래픽을 50:50으로 고정해 나눈 뒤 승자를 고릅니다. 밴딧 관점에서 보면 "탐험만 하다가 한 번에 활용으로 넘어가는" 전략이라, 시험 기간 동안 나쁜 쪽에 절반을 보내는 후회가 생깁니다. 톰슨 샘플링 같은 밴딧은 좋아 보이는 쪽으로 트래픽을 점점 옮겨 그 후회를 줄입니다. 대신 각 안의 효과를 통계적으로 정밀하게 추정하는 데는 고정 분할이 더 깔끔하므로, "무엇이 목적인가(학습 중 손해 최소 vs 정확한 효과 추정)"에 따라 고릅니다.

연습 문제

1. 3절 표에서 $c=0.5$ 이면 어느 손잡이를 고르나요?
   • 풀이: 덧셈 몫은 A $0.310$, B $0.438$, C $0.759$. 점수는 A $0.910$, B $0.938$, C $1.059$ 이므로 C를 고릅니다.
2. UCB에서 $N_t(a)=0$ 인 행동이 있으면 어떻게 되나요?
   • 풀이: 그 행동을 최우선(점수 무한대처럼)으로 고릅니다. 그래서 처음 $k$ 번은 모든 손잡이를 한 번씩 당깁니다.
3. 톰슨 샘플링에서 손잡이가 $\mathrm{Beta}(1,1)$ 에서 출발해 성공 4번 · 실패 6번을 겪었습니다. 지금 분포와 평균은?
   • 풀이: $\mathrm{Beta}(5,7)$, 평균 $5/12\approx0.417$ 입니다.
4. 참값 $\mu=(0.5,\ 0.4)$ 인 두 손잡이에서 1,000번 중 나쁜 손잡이를 300번 당겼습니다. 후회는?
   • 풀이: $300\times(0.5-0.4)=30$ 입니다.
5. 경사 밴딧에서 받은 보상이 기준값보다 작으면($R_t<\bar R_t$) 고른 행동의 선호도는 어떻게 되나요?
   • 풀이: $(R_t-\bar R_t)<0$ 이므로 고른 행동의 $H$ 가 내려가고, 고르지 않은 행동들의 $H$ 는 올라갑니다.

스스로 점검

1. UCB가 ε-탐욕보다 탐험을 '똑똑하게' 하는 이유는?
   • 답: 무작위가 아니라 "덜 시도해서 불확실성이 큰 행동"에 점수를 더 얹어, 좋을 가능성이 남은 쪽을 골라 시험하기 때문입니다.
2. 톰슨 샘플링에서 오래 쓴 손잡이가 덜 탐험되는 이유는?
   • 답: 데이터가 쌓이면 베타 분포가 좁아져 뽑는 값이 평균 근처에만 나오므로, 평균이 낮은 손잡이가 우연히 1등 하는 일이 줄어들기 때문입니다.
3. ε 을 고정한 ε-탐욕의 후회는 왜 시간에 비례해 커지나요?
   • 답: 최고 손잡이를 알아낸 뒤에도 매 걸음 일정 확률로 나쁜 손잡이를 당겨, 한 걸음당 일정한 손해가 끝없이 쌓이기 때문입니다.

용어 정리

더 깊이 보려면

• Sutton · Barto 2장 끝의 매개변수 연구(그림 2.6): ε-탐욕 · 경사 밴딧 · UCB · 낙관적 초깃값을 같은 시험대에서 매개변수를 바꿔 가며 비교합니다.
• Russo 외 튜토리얼: 베타-베르누이 예에서 시작해 탐욕적 방법과의 비교, 더 복잡한 문제로의 확장을 다룹니다.
• 이 사이트의 Hugging Face 딥 강화학습 강좌 — ε 을 점점 줄이는 방식(ε 감쇠)과 Q-러닝으로 이어집니다.

다음에 볼 것

• Hugging Face 딥 강화학습 강좌 — 상태가 여러 개인 문제에서 경험으로 가치를 배우는 TD · Q-러닝 · SARSA.
• 직접 해 보기: 그리드월드 Q-러닝 — ε-탐욕 탐험이 실제 학습 결과를 어떻게 바꾸는지 코드로 확인합니다.

라이선스

본문은 KAITABASE 자체 해설입니다. 참고한 Sutton · Barto 2판 PDF는 판권면에 CC BY-NC-ND 2.0으로 표기되어 있고, Russo 외 튜토리얼은 arXiv 논문입니다. 원문 문장을 옮기지 않았으며, 표와 숫자 예는 이 수업을 위해 만든 해설용입니다(책의 그림 수치는 인용하지 않고 설정만 밝혔습니다).

출처

• Sutton · Barto, Reinforcement Learning: An Introduction 2판(2020 PDF) 2.6~2.9절: http://incompleteideas.net/book/RLbook2020.pdf
• Auer, Cesa-Bianchi, Fischer (2002), Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning 47: https://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf
• Russo, Van Roy, Kazerouni, Osband, Wen (2018), A Tutorial on Thompson Sampling, Foundations and Trends in ML: https://arxiv.org/abs/1707.02038