강화학습의 근간 (5): 탐험의 이론 — Multi-Armed Bandit, Regret, 그리고 UCB

문제를 최소로 줄여보자

(4)까지로 model-free 예측이 끝났고 다음은 제어인데, 제어로 넘어가는 순간 새 문제가 하나 끼어든다 — 탐험. 해본 행동의 가치만 갱신되는 세계에서, 지금 최선으로 보이는 것만 하면 진짜 최선을 영영 모를 수 있다. 이 딜레마는 MDP의 다른 어려움들(전이, 신용 할당, 함수 근사)과 뒤엉키면 분석이 불가능해지므로, 이론은 반대로 간다: 상태와 전이를 전부 제거하고 탐험만 남긴 최소 문제를 만들어 거기서 완전한 답을 얻은 뒤, 그 답을 큰 문제에 이식한다. 그 최소 문제가 Multi-Armed Bandit(MAB) 이고, 이 글은 그 이론 — regret, 하한, UCB — 이다. 뒤의 글들에서 ε-greedy의 위상을 판정하는 자도, UCT와 알파고의 탐색 규칙도 전부 여기서 나온다.

Multi-Armed Bandit — 1-상태 강화학습

이름은 카지노에서 왔다: 팔(레버)이 $K$개인 슬롯머신 앞에서, 매 라운드 팔 하나를 당기고 그 팔의 미지의 분포에서 보상을 받는다. 형식화하면 MAB는 $\langle \mathcal{A}, \mathcal{R} \rangle$ — 행동(팔) 집합과 행동별 보상 분포 $\mathcal{R}^a = \mathbb{P}[R \mid A = a]$가 전부다. (2)의 MDP에서 상태가 하나뿐이고 전이가 없는 특수형, 즉 1-상태 MDP다. 행동 가치는

$q_*(a) = \mathbb{E}[R \mid A = a], \qquad v_* = \max_a q_*(a)$

이고, 상태가 없으니 벨만 재귀도 신용 할당도 없다 — 남은 문제는 오직 하나, $q_*$를 모르는 채로 어떤 순서로 팔을 당길 것인가다.

Regret — 탐험 알고리즘의 성적표

누적 보상 최대화는 문제마다 스케일이 달라 비교가 안 된다. 이론이 쓰는 자는 regret(후회) — 전지적 플레이어(항상 최적 팔) 대비 손실이다:

$L_T = T \, v_* - \mathbb{E}\left[ \sum_{t=1}^{T} R_t \right]$

각 팔의 gap $\Delta_a = v_* - q_*(a)$와 $T$까지의 선택 횟수 $N_T(a)$로 분해하면 구조가 드러난다:

$L_T = \sum_{a} \mathbb{E}[N_T(a)] \, \Delta_a$

— regret은 “나쁜 팔을 몇 번 당겼는가 × 그 팔이 얼마나 나쁜가”의 합이다. 좋은 알고리즘이란 gap이 큰 팔일수록 빨리 제껴두는 알고리즘이라는 것, 그리고 어려움의 원천은 gap이 작은 팔(구별에 표본이 많이 필요한)이라는 것이 이 한 줄에서 다 보인다. 관심사는 $L_T$가 $T$에 대해 어떻게 자라는가다 — 선형이면 실패(영원히 일정 비율로 손해), 로그면 성공(추가 손해가 갈수록 희박)이라는 것이 이 분야의 언어다.

소박한 전략들의 성적

Greedy: 지금까지의 표본 평균 $\hat{Q}_t(a)$가 최대인 팔만 당긴다. 초기 몇 번의 불운으로 최적 팔의 추정치가 낮게 잡히면 영원히 그 팔로 돌아가지 않는다 — 일정 확률로 차선에 갇히므로 regret이 선형으로 자란다.

고정 ε-greedy: 확률 $\varepsilon$로 무작위 탐험을 섞으면 갇힘은 없어진다. 하지만 $q_*$를 다 알게 된 뒤에도 영원히 라운드의 $\varepsilon$ 비율을 무작위에 쓴다 — 스텝당 최소 $\frac{\varepsilon}{K}\sum_a \Delta_a$의 손실이 멈추지 않으므로 역시 선형 regret이다.

감쇠 ε-greedy: $\varepsilon_t$를 $c/t$ 꼴로 줄이면 로그 regret이 가능하다 — 그런데 올바른 감쇠 상수가 gap에 의존한다(작은 gap일수록 천천히 줄여야 한다). 모르는 값을 알아야 최적이 되는, 이론적으로는 답이지만 실전에서는 손잡이가 하나 더 생긴 셈이다. (6)에서 만날 GLIE($\varepsilon_k = 1/k$)가 정확히 이 노선의 MDP 버전이다 — 수렴은 보장하지만 속도까지 최적은 아닌.

Lai-Robbins 하한 — 로그가 바닥이다

그럼 얼마나 잘할 수 있는가? Lai & Robbins(1985)의 고전적 결과: 모든 문제에서 준수하게 작동하는(consistent) 알고리즘이라면, 어떤 것이든

$\liminf_{T \to \infty} \frac{L_T}{\ln T} \;\ge\; \sum_{a : \Delta_a > 0} \frac{\Delta_a}{D_{\mathrm{KL}}\big(\mathcal{R}^a \,\Vert\, \mathcal{R}^{a^*}\big)}$

— regret은 로그보다 느리게 자랄 수 없다. 분모의 KL 발산이 문제의 난이도를 정의한다: 나쁜 팔의 분포가 최적 팔과 비슷할수록(KL이 작을수록) 구별에 더 많은 표본이 강제된다. 이 하한 덕에 목표가 정확해진다 — “탐험을 잘한다”의 정의는 로그 regret을, 가능하면 이 상수까지 맞춰 달성하는 것이다.

낙관주의, 그리고 UCB1

로그를 달성하는 고전적 원리가 불확실성 앞에서의 낙관(optimism in the face of uncertainty) 이다: 각 팔의 가치를 점 추정이 아니라 신뢰구간으로 들고, 상한이 가장 높은 팔을 당겨라. 이유가 우아하다 — 낙관적으로 고른 팔은 둘 중 하나다: 정말 좋았거나(활용 성공), 아니면 당겨본 덕에 신뢰구간이 좁아져 착각이 걷히거나(탐험 성공). 어느 쪽이든 남는 장사라 낭비되는 라운드가 구조적으로 없다.

상한은 Hoeffding 부등식으로 만든다. $[0,1]$ 보상에서 표본 평균이 참값을 $u$ 이상 과소평가할 확률은 $e^{-2 N u^2}$ 이하 — 이 확률을 $t^{-4}$ 수준으로 잡도록 풀면 보너스 $u = \sqrt{2 \ln t / N}$이 나온다. 그렇게 조립된 것이 UCB1(Auer, Cesa-Bianchi & Fischer, 2002):

$A_t = \arg\max_a \left( \hat{Q}_t(a) + \sqrt{\frac{2 \ln t}{N_t(a)}} \right)$

읽는 법: 보너스의 분자 $\ln t$는 시간이 갈수록 모든 팔을 언젠가 다시 시험하게 만들고(갇힘 방지), 분모 $N_t(a)$는 많이 당겨본 팔의 보너스를 줄여 추정이 확실한 팔은 평균으로 승부하게 한다. 그리고 원 논문의 정리 — 임의의 유계 보상 분포에 대해, 사전 지식이나 스케줄 조정 없이,

$L_T \;\le\; 8 \sum_{a : \Delta_a > 0} \frac{\ln T}{\Delta_a} + \Big(1 + \frac{\pi^2}{3}\Big) \sum_a \Delta_a$

— 모든 시점에서 균일하게 로그 regret이다(Lai-Robbins가 점근으로만 보인 것을 유한 시간 부등식으로). 나쁜 팔이 당겨지는 횟수가 $O(\ln T / \Delta_a^2)$로 억제된다는 것이 증명의 뼈대이고, gap이 작을수록 많이 당겨진다는 하한의 구조가 상한에도 그대로 나타난다.

같은 바닥에 도달하는 전혀 다른 스타일도 있다 — Thompson sampling(1933): 각 팔의 가치에 대한 사후 분포를 유지하고, 매 라운드 사후에서 표본 하나씩 뽑아 그 표본이 최대인 팔을 당긴다(확률 일치, probability matching). 80년 뒤에야 로그 regret이 증명됐지만(Agrawal & Goyal, 2012) 실전 성능은 종종 UCB보다 좋고, 베이지안 불확실성이 자연스러운 문제(추천, A/B 테스트)의 기본값이다. 낙관(신뢰 상한)과 무작위화(사후 표본) — 탐험의 두 정통 노선으로 기억해두면 된다.

밴딧에서 MDP로 — 이 이론이 어디에 꽂히는가

MAB에서 얻은 것을 시리즈의 나머지에 이식하며 닫자.

• ε-greedy의 좌표: (6)의 model-free control이 ε-greedy/GLIE를 쓰는 것은 그것이 최적이어서가 아니다 — 밴딧 기준으로는 로그도 못 맞추는 소박한 전략이지만, MDP에서는 “모든 상태-행동의 무한 방문”이라는 수렴 전제를 가장 값싸게 채워주기 때문이다. 이론적 바닥과 실무적 기본값의 간극을 알고 쓰는 것과 모르고 쓰는 것은 다르다.
• UCB의 실전 무대: 트리 탐색의 각 내부 노드는 “자식 중 어디에 다음 시뮬레이션을 쓸까”라는 밴딧이다 — 거기에 UCB1을 꽂은 것이 (8)의 UCT/MCTS이고, 사전 확률을 곱한 변형(PUCT)이 알파고의 선택 규칙이다. 이 글의 수식이 문자 그대로 재등장한다.
• 낙관주의의 확장: “불확실한 곳에 보너스”는 MDP 전반의 탐험 원리로 일반화된다 — Dyna-Q+의 $r + \epsilon\sqrt{n}$ 탐험 보너스가 정확히 이것이고, 심층 강화학습의 count-based 탐험·RND 같은 내재적 보상 계열이 그 후손이다. 다만 정직한 단서 하나: MDP에서는 탐험이 상태 분포 자체를 바꾸고 결과가 지연되므로, 밴딧의 로그 보장이 그대로 이식되지는 않는다(이론적으로는 UCRL 같은 별도 계열이 있다). 밴딧 이론은 MDP 탐험의 하계이자 어휘이지, 완성된 답은 아니다.

다음 글에서 이 어휘를 들고 model-free 제어로 간다 — ε-greedy와 GLIE부터 SARSA, Q-learning, DQN까지.