강화학습 9강: 탐험과 활용

지금 아는 정보로 최선의 선택을 할까(활용), 아니면 손해를 감수하고 더 나은 선택지가 있는지 알아볼까(탐험)? 온라인 의사결정의 가장 근본적인 갈등이다. 실버는 이 강의에서 겉보기에 제각각인 탐험 전략들을 다섯 개의 원리로 묶는다. 순진한 탐험, 낙관적 초기화, 불확실성 앞의 낙관, 확률 매칭, 그리고 정보 상태 탐색이다. 이후의 모든 절은 이 다섯 원리 어딘가에 매달린다.

강의 슬라이드: PDF

탐험이냐 활용이냐

활용은 지금 아는 것으로 최선의 결정을 내리는 것이고, 탐험은 더 많은 정보를 모으는 것이다. 핵심은 장기적으로 최선의 결정을 하려면 단기적 희생이 필요할 수 있다는 데 있다. 지금 손해를 좀 보더라도 정보를 충분히 모아야, 전체 여정에서 최선의 선택을 할 수 있다.

실버가 드는 예들이 직관을 세운다. 식당을 고를 때, 활용은 늘 가던 단골집에 가는 것이고 탐험은 새 집을 한번 가 보는 것이다. 배너 광고에서 활용은 가장 잘 먹히던 광고를 다시 띄우는 것이고 탐험은 다른 광고를 시험하는 것이다. 유전 시추라면 활용은 지금까지 가장 잘 나온 자리를 파는 것이고 탐험은 새 자리를 뚫어 보는 것이다. 바둑이라면 활용은 최선이라 믿는 수를 두는 것이고 탐험은 실험적인 수를 던지는 것이다. 모두 같은 긴장이다. 지금의 최선과 미지의 가능성 사이에서 어떻게 시간을 나눌 것인가.

다섯 원리

이 강의의 뼈대다. 실버는 탐험 방법들을 다음 다섯 원리로 정리한다.

• 순진한 탐험: 탐욕 정책에 잡음을 더한다. $\epsilon$-탐욕이 대표.
• 낙관적 초기화: 반증되기 전까지는 모든 선택지가 최고라고 가정한다.
• 불확실성 앞의 낙관: 가치가 불확실한 행동을 선호한다.
• 확률 매칭: 각 행동을 그것이 최적일 확률만큼 뽑는다.
• 정보 상태 탐색: 정보의 가치까지 계산에 넣어 앞을 내다보고 계획한다.

아래에서 이 원리들을 먼저 가장 단순한 무대인 다중 슬롯머신에서 세우고, 그다음 문맥 밴딧과 MDP로 끌어올린다.

다중 슬롯머신

다중 슬롯머신(멀티암드 밴딧)은 튜플 $\langle \mathcal{A}, \mathcal{R} \rangle$이다. $\mathcal{A}$는 알려진 $m$개의 행동(팔) 집합이고, $\mathcal{R}^a(r) = \mathbb{P}[r \mid a]$는 알려지지 않은 보상 분포다. 매 스텝 $t$에 에이전트가 팔 $a_t$를 당기면 환경이 보상 $r_t \sim \mathcal{R}^{a_t}$를 내준다. 목표는 누적 보상 $\sum_{\tau=1}^t r_\tau$를 최대로 하는 것이다. 상태도 전이도 없다. 오직 어느 팔이 좋은가만 남은, 탐험과 활용의 순수 실험실이다.

후회

성과를 재는 자연스러운 잣대가 후회(regret)다. 행동의 가치는 그 팔의 평균 보상 $Q(a) = \mathbb{E}[r \mid a]$이고, 최적 가치는

$$V^* = Q(a^*) = \max_{a \in \mathcal{A}} Q(a)$$

한 스텝의 후회는 최적을 두고 다른 팔을 당겨서 놓친 기회 손실이다.

$$l_t = \mathbb{E}[V^* - Q(a_t)]$$

전체 후회는 이걸 다 더한 것이다.

$$L_t = \mathbb{E}\Big[\sum_{\tau=1}^t V^* - Q(a_\tau)\Big]$$

누적 보상을 최대로 하는 것은 곧 전체 후회를 최소로 하는 것과 같다. 앞으로는 후회를 줄인다는 관점으로 본다.

후회를 세어 보기

후회를 좀 더 뜯어보면 무엇이 문제인지가 드러난다. $N_t(a)$를 스텝 $t$까지 팔 $a$를 당긴 기대 횟수라 하고, 갭(gap) $\Delta_a = V^* - Q(a)$를 최적 팔과 팔 $a$의 가치 차이라 하자. 그러면 후회는 갭과 횟수의 함수로 깔끔하게 갈라진다.

$$L_t = \mathbb{E}\Big[\sum_{\tau=1}^t V^* - Q(a_\tau)\Big] = \sum_{a \in \mathcal{A}} \mathbb{E}[N_t(a)]\,(V^* - Q(a)) = \sum_{a \in \mathcal{A}} \mathbb{E}[N_t(a)]\,\Delta_a$$

읽는 법이 중요하다. 좋은 알고리즘은 갭이 큰 팔(즉 많이 나쁜 팔)일수록 적게 당겨야 한다. 갭이 크면 한 번 당길 때마다 그만큼 후회가 크게 쌓이니까. 그런데 함정이 있다. 우리는 갭을 모른다. 갭을 알았다면 애초에 최적 팔이 뭔지 아는 것이고 문제가 끝난다. 나쁜 팔을 덜 당기고 싶은데, 어느 팔이 얼마나 나쁜지 모른다는 것, 이게 밴딧 문제의 본질이다.

선형 후회냐 준선형 후회냐

시간이 흐르며 전체 후회가 어떻게 자라는지가 알고리즘의 등급을 가른다. 두 극단은 둘 다 실패한다. 영원히 탐험만 하면(무작위로 계속 당기면) 나쁜 팔을 계속 당기니 후회가 시간에 비례해 선형으로 자란다. 영원히 탐험을 안 하면(한번 정한 팔만 계속 당기면) 잘못 찍은 경우 그 손해가 영원히 이어져 역시 선형이다. 질문은 이것이다. 후회를 선형보다 느리게, 즉 준선형으로 줄일 수 있는가.

탐욕과 $\epsilon$-탐욕

먼저 각 팔의 가치를 몬테카를로로 추정한다. 지금까지 그 팔에서 받은 보상의 평균이다.

$$\hat{Q}_t(a) = \frac{1}{N_t(a)} \sum_{t=1}^{T} r_t\,\mathbf{1}(a_t = a)$$

탐욕 알고리즘은 추정 가치가 가장 높은 팔을 고른다. $a_t^* = \arg\max_a \hat{Q}_t(a)$. 문제는 명백하다. 초반에 운 나쁘게 진짜 최적 팔에서 낮은 보상을 몇 번 받으면, 탐욕은 그 팔을 영영 외면하고 차선에 눌러앉을 수 있다. 한번 갇히면 못 나온다. 그래서 탐욕은 선형 후회를 낳는다.

$\epsilon$-탐욕은 이 갇힘을 막으려 잡음을 섞는다. 확률 $1-\epsilon$로 $\arg\max_a \hat{Q}(a)$를 고르고, 확률 $\epsilon$로는 아무 팔이나 무작위로 당긴다. 덕분에 영원히 탐험을 이어 가므로 최적 팔을 아예 놓치지는 않는다. 하지만 $\epsilon$을 상수로 두면 매 스텝 $\epsilon$의 확률로 나쁜 팔을 당기는 관성이 사라지지 않는다.

$$l_t \geq \frac{\epsilon}{|\mathcal{A}|} \sum_{a \in \mathcal{A}} \Delta_a$$

이 최소 후회가 매 스텝 깔리므로, 상수 $\epsilon$-탐욕도 결국 선형 후회다. 이것이 순진한 탐험의 한계다.

낙관적 초기화

두 번째 원리다. 아주 단순하고 실전적인 아이디어로, 모든 팔의 초기 가치 $Q(a)$를 일부러 높게 잡아 둔다. 그리고 증분 몬테카를로로 갱신하되 처음부터 $N(a) > 0$으로 시작한다.

$$\hat{Q}_t(a_t) = \hat{Q}_{t-1} + \frac{1}{N_t(a_t)}(r_t - \hat{Q}_{t-1})$$

효과는 이렇다. 모든 팔이 처음엔 “최고일지도 몰라"라는 부푼 기대를 달고 있으니, 에이전트는 자연스럽게 안 당겨 본 팔부터 하나씩 시도한다. 실제로 당겨 보면 부풀린 기대가 현실 값으로 깎이고, 그제서야 낙관이 걷힌다. 반증되기 전까지는 최고라고 가정한다는 원리의 말 그대로다. 초반 탐험을 체계적으로 유도한다는 점에서 좋지만, 근본 처방은 아니다. 운 나쁘게 초반에 최적 팔의 낙관이 빨리 깎여 버리면 여전히 차선에 갇힐 수 있다. 그래서 탐욕에 낙관적 초기화를 더해도, $\epsilon$-탐욕에 더해도 여전히 선형 후회다.

감소하는 $\epsilon$-탐욕

$\epsilon$을 상수로 두는 게 문제라면, 시간이 갈수록 줄이면 어떨까. 감소 스케줄 $\epsilon_1, \epsilon_2, \dots$를 잡는다. 다음 스케줄을 보자. $c > 0$이고 $d = \min_{a \mid \Delta_a > 0} \Delta_i$(가장 작은 양의 갭)일 때

$$\epsilon_t = \min\left\{1, \frac{c|\mathcal{A}|}{d^2 t}\right\}$$

놀랍게도 이 감소 $\epsilon$-탐욕은 점근적으로 로그 후회를 달성한다. 선형에서 로그로 내려온 것이다. 그런데 결정적인 단서가 붙는다. 이 스케줄은 갭 $d$를 미리 알아야 한다. 앞서 봤듯 갭은 우리가 모르는 바로 그것이다. 그러니 목표를 다시 잡아야 한다. 보상 분포 $\mathcal{R}$에 대한 사전 지식 없이도, 임의의 다중 슬롯머신에 대해 준선형 후회를 내는 알고리즘을 찾는 것이다.

하한: 라이-로빈스

그런데 아무리 영리해도 넘을 수 없는 벽이 있다. 어떤 문제가 어려운가를 먼저 보자. 문제의 난이도는 최적 팔과 나머지 팔들이 얼마나 닮았는가로 정해진다. 어려운 문제는 겉보기(분포)는 비슷한데 평균이 미세하게 다른 팔들을 가진다. 두 팔의 보상 분포가 거의 겹치면, 어느 쪽이 조금 더 나은지 가려내는 데 아주 많은 표본이 필요하기 때문이다. 이 닮음은 갭 $\Delta_a$와 분포 사이 KL 발산 $\mathrm{KL}(\mathcal{R}^a \Vert \mathcal{R}^{a^*})$로 형식화된다.

정리 (라이와 로빈스). 점근적 전체 후회는 스텝 수의 로그 이상이다.

$$\lim_{t \to \infty} L_t \geq \log t \sum_{a \mid \Delta_a > 0} \frac{\Delta_a}{\mathrm{KL}(\mathcal{R}^a \Vert \mathcal{R}^{a^*})}$$

읽는 법은 이렇다. 어떤 알고리즘도 후회를 로그보다 빠르게 줄일 수 없다. 로그 후회가 우리가 바랄 수 있는 최선이다. 그리고 분모의 KL이 작을수록(팔들이 닮을수록) 하한이 커진다. 비슷해 보이는데 평균이 다른 팔이 가장 어렵다는 직관이 수식에 그대로 박혀 있다. 이제 남은 일은 이 로그 하한에 실제로 닿는 알고리즘을 찾는 것이다.

불확실성 앞의 낙관

세 번째 원리다. 여러 팔의 가치 추정이 저마다 다른 폭의 불확실성(분포)을 달고 있다고 하자. 어떤 팔을 골라야 할까. 실버의 답이 이 원리의 핵심이다. 어떤 행동의 가치에 대해 불확실할수록, 그 행동을 탐험하는 것이 더 중요하다. 왜냐하면 바로 그 팔이 사실은 최고일 수도 있기 때문이다. 불확실하다는 것은 위쪽으로 크게 열려 있을 가능성을 품는다는 뜻이다.

파란 팔을 당겨 보면 그 팔의 가치에 대한 불확실성이 줄고, 그러면 아직 더 불확실한 다른 팔로 관심이 옮겨 간다. 이 과정을 반복하다 보면 결국 진짜 최고의 팔로 수렴한다. 낙관을 데이터로 하나씩 검증해 가는 셈이다.

신뢰 상한

이 원리를 수치로 만든 것이 신뢰 상한(UCB)이다. 각 행동에 상한 보너스 $\hat{U}_t(a)$를 붙여, 높은 확률로 참값이 그 아래 있게 한다.

$$Q(a) \leq \hat{Q}_t(a) + \hat{U}_t(a)$$

이 보너스는 그 팔을 몇 번 당겼는지 $N_t(a)$에 달려 있다. $N_t(a)$가 작으면(덜 당겨 봤으면) $\hat{U}_t(a)$가 크고(추정이 불확실), $N_t(a)$가 크면 $\hat{U}_t(a)$가 작다(추정이 정확). 그리고 이 상한이 가장 높은 팔을 고른다.

$$a_t = \arg\max_{a \in \mathcal{A}} \hat{Q}_t(a) + \hat{U}_t(a)$$

추정치가 좋아서(가치가 높아서) 뽑히거나, 덜 당겨 봐서(불확실해서) 뽑히거나. 활용과 탐험이 하나의 식에 녹아든다.

회프딩 부등식에서 보너스를 끌어내기

그런데 보너스 $\hat{U}_t(a)$를 아무 상수나 대충 정하면 안 된다. 이것은 통계적 신뢰구간이어야 하고, 그 폭은 회프딩 부등식에서 나온다.

정리 (회프딩 부등식). $X_1, \dots, X_t$가 $[0,1]$ 안의 독립 동일 분포 확률변수이고 $\overline{X}_t = \frac{1}{t}\sum_{\tau=1}^t X_\tau$가 표본평균이면,

$$\mathbb{P}\big[\mathbb{E}[X] > \overline{X}_t + u\big] \leq e^{-2tu^2}$$

읽는 법이 열쇠다. 표본평균이 참평균에서 $u$ 이상 벗어날 확률이 $u$가 커질수록 지수적으로 작아진다. 이걸 팔 $a$를 골랐을 때의 보상에 적용하면

$$\mathbb{P}\big[Q(a) > \hat{Q}_t(a) + U_t(a)\big] \leq e^{-2 N_t(a) U_t(a)^2}$$

이제 참값이 상한을 넘을 확률 $p$를 하나 정하고 $U_t(a)$에 대해 풀면 된다.

$$e^{-2 N_t(a) U_t(a)^2} = p \quad\Longrightarrow\quad U_t(a) = \sqrt{\frac{-\log p}{2 N_t(a)}}$$

관측이 쌓일수록 상한을 넘는 사고를 더 엄격히 막고 싶으니 $p$를 시간에 따라 줄인다. 예컨대 $p = t^{-4}$로 두면 $t \to \infty$에서 최적 행동을 확실히 고르게 되고, 보너스가 다음의 깔끔한 꼴이 된다.

$$U_t(a) = \sqrt{\frac{2 \log t}{N_t(a)}}$$

이 $\sqrt{2 \ln t / N(a)}$가 임의로 고른 마법의 상수가 아니라는 것이 핵심이다. 이것은 회프딩이 보장하는 신뢰구간의 폭 그 자체다. 덜 당겨 본 팔일수록($N$이 작을수록) 넓게, 시간이 흐를수록($t$가 클수록 확신을 요구하므로) 조금씩 넓게 열린다.

UCB1

이걸 그대로 알고리즘으로 굳힌 것이 UCB1이다.

$$a_t = \arg\max_{a \in \mathcal{A}} Q(a) + \sqrt{\frac{2 \log t}{N_t(a)}}$$

정리. UCB 알고리즘은 점근적으로 로그 전체 후회를 달성한다.

$$\lim_{t \to \infty} L_t \leq 8 \log t \sum_{a \mid \Delta_a > 0} \Delta_a$$

갭을 미리 알아야 했던 감소 $\epsilon$-탐욕과 달리, UCB1은 갭에 대한 사전 지식 없이도 로그 후회에 닿는다. 라이-로빈스 하한이 로그였으니, UCB는 그 벽에 상수배 안으로 붙은 셈이다. 실버는 실제 10팔 밴딧 실험에서 UCB가 $\epsilon$-탐욕을 안정적으로 앞선다는 비교 그림을 보여 준다.

확률 매칭과 톰프슨 표집

지금까지는 보상 분포에 대해 상한만 가정하고 별다른 사전 지식을 쓰지 않았다. 베이지안 밴딧은 여기서 한 걸음 더 나간다. 보상에 대한 사전분포 $p[\mathcal{R}]$을 가정하고, 관측 이력 $h_t = a_1, r_1, \dots, a_{t-1}, r_{t-1}$이 주어졌을 때의 사후분포 $p[\mathcal{R} \mid h_t]$를 계산해 탐험을 이끈다. 사전 지식이 정확하면 성능이 더 좋아진다. 이 사후분포를 쓰는 길이 둘인데, 하나는 베이지안 UCB이고 다른 하나가 이제 볼 확률 매칭(톰프슨 표집)이다.

베이지안 UCB의 예로 보상이 가우시안이라 가정하면, 각 팔의 평균과 분산에 대한 가우시안 사후를 베이즈 법칙으로 얻고, 평균에 표준편차를 상수배 얹은 팔을 고른다.

$$a_t = \arg\max_a\; \mu_a + \frac{c\,\sigma_a}{\sqrt{N(a)}}$$

앞의 UCB와 같은 정신이다. 불확실할수록($\sigma_a$가 클수록) 위로 더 밀어 올려 준다.

확률 매칭

네 번째 원리다. 확률 매칭은 각 행동을 그 행동이 최적일 확률만큼 뽑는다.

$$\pi(a \mid h_t) = \mathbb{P}\big[Q(a) > Q(a'),\ \forall a' \neq a \mid h_t\big]$$

이 정책이 왜 불확실성 앞의 낙관과 통하는지 보라. 불확실한 행동일수록 사후분포의 위쪽 꼬리가 두터워서, 다른 모든 팔보다 값이 클 확률, 즉 최적일 확률이 자연히 높아진다. 그래서 불확실한 팔이 더 자주 뽑힌다. 다만 이 확률을 사후분포에서 해석적으로 계산하기가 어렵다는 게 흠이다.

톰프슨 표집

여기서 놀랄 만큼 간단한 트릭이 등장한다. 톰프슨 표집은 확률 매칭을 표본 하나로 구현한다.

$$\pi(a \mid h_t) = \mathbb{P}\big[Q(a) > Q(a'),\ \forall a' \neq a \mid h_t\big] = \mathbb{E}_{\mathcal{R} \mid h_t}\big[\mathbf{1}(a = \arg\max_a Q(a))\big]$$

절차는 이렇다. 베이즈 법칙으로 사후분포 $p[\mathcal{R} \mid h_t]$를 얻고, 그 사후에서 보상 분포 $\mathcal{R}$을 하나 표집하고, 그 표본으로 가치 $Q(a) = \mathbb{E}[\mathcal{R}^a]$를 계산한 뒤, 그 표본 위에서 최댓값을 주는 팔을 고른다. $a_t = \arg\max_a Q(a)$. 매번 사후에서 뽑은 한 표본의 argmax를 취하는 이 단순한 행위가, 정확히 “각 팔이 최적일 확률만큼 뽑기"를 실현한다. 불확실한 팔은 표본이 크게 나올 때가 많아 자주 이긴다.

반전은 역사에 있다. 이 방법은 1933년 톰프슨이 제안한 아주 오래된 아이디어인데, 놀랍게도 톰프슨 표집은 라이-로빈스 하한을 달성한다. UCB와 마찬가지로 이론적 최선에 닿는데, 구현은 사후에서 표본 하나 뽑는 것으로 끝난다.

10팔 밴딧에서 ε-탐욕·UCB·톰프슨의 누적 후회. 톰프슨이 대체로 가장 낮다. “+5000"으로 오래 돌리면 ε-탐욕은 상수 탐험 탓에 후회가 선형으로 가파르게 벌어지는 반면, UCB와 톰프슨은 준선형(로그)으로 눕는 게 뚜렷해진다. ε을 키우거나 “새 밴딧"으로 다른 문제에서도 확인해 보자.

정보의 가치와 베이즈 적응

다섯 번째 원리다. 탐험이 왜 유용한가. 정보를 얻기 때문이다. 그렇다면 정보의 가치를 값으로 매길 수 있을까. 정보의 가치란, 결정을 내리기 전에 그 정보를 갖기 위해 의사결정자가 기꺼이 치를 보상의 양이다. 정보를 얻은 뒤의 장기 보상에서 당장의 보상을 뺀 것이다. 불확실한 상황일수록 얻을 정보가 많으니, 불확실한 상황을 더 탐험하는 것이 이치에 맞다. 정보의 가치를 알면 탐험과 활용을 최적으로 저울질할 수 있다.

정보 상태 공간

여기서 관점이 크게 바뀐다. 지금까지 밴딧을 한 스텝짜리 결정 문제로 봤지만, 순차적 결정 문제로도 볼 수 있다. 매 스텝 정보 상태 $\tilde{s}$가 있다. $\tilde{s}$는 이력의 통계량 $\tilde{s}_t = f(h_t)$로, 지금까지 쌓인 모든 정보를 요약한다. 아직 무엇을 모르는가를 담은 상태인 셈이다. 그리고 각 행동 $a$는 (정보를 더함으로써) 새 정보 상태 $\tilde{s}'$로의 전이를 일으킨다. 확률 $\tilde{\mathcal{P}}^a_{\tilde{s},\tilde{s}'}$로. 이것이 확장된 정보 상태 공간 위의 MDP $\tilde{\mathcal{M}} = \langle \tilde{\mathcal{S}}, \mathcal{A}, \tilde{\mathcal{P}}, \mathcal{R}, \gamma \rangle$를 정의한다. 탐험이 곧 이 거대한 MDP 위의 계획 문제로 환원되는 것이다.

예: 베르누이 밴딧

구체적인 예가 그림을 완성한다. 베르누이 밴딧에서는 각 팔이 $\mathcal{R}^a = \mathcal{B}(\mu_a)$, 즉 확률 $\mu_a$로 이기고 지는 게임이다. 어느 팔의 $\mu_a$가 가장 높은지 찾고 싶다. 여기서 정보 상태는 $\tilde{s} = \langle \alpha, \beta \rangle$이다. $\alpha_a$는 팔 $a$를 당겨 보상이 0이었던 횟수, $\beta_a$는 보상이 1이었던 횟수다. 이 $\langle \alpha, \beta \rangle$가 곧 그 팔의 보상 모델에 대한 $\mathrm{Beta}(\alpha, \beta)$ 사후분포에 대응한다.

팔을 당길 때마다 사후가 갱신되는 것이 그대로 상태 전이가 된다.

$$\langle \alpha_a, \beta_a \rangle \to \begin{cases} \langle \alpha_a + 1, \beta_a \rangle & r = 0 \\ \langle \alpha_a, \beta_a + 1 \rangle & r = 1 \end{cases}$$

$\mathrm{Beta}(\alpha_a, \beta_a)$ 사전에서 시작해, 팔을 뽑을 때마다 사후를 갱신하는 이 흐름이 베이즈 적응 MDP의 전이함수 $\tilde{\mathcal{P}}$를 정의한다. 각 상태 전이가 하나의 베이지안 모델 갱신에 대응하는 것이다.

기틴스 지수와 시뮬레이션 탐색

이제 우리 손에는 정보 상태 위의 무한 MDP가 있다. 이건 강화학습으로 풀 수 있다. 모델프리로 가면 Q-러닝(Duff, 1994) 같은 방법이고, 베이지안 모델기반으로 가면 기틴스 지수(Gittins, 1979)다. 이 접근을 베이즈 적응 강화학습이라 부르며, 사전분포에 대해 베이즈 최적의 탐험/활용 저울질을 찾는다. 즉 베이즈 적응 MDP를 동적 계획법으로 풀면 정확해가 나오고, 그 해가 곧 기틴스 지수다.

문제는 이 정확해가 대개 다루기 힘들다는 것이다. 정보 상태 공간이 너무 크다. 그래서 실전에서는 최근 아이디어인 시뮬레이션 기반 탐색(Guez et al. 2012)을 쓴다. 현재 정보 상태에서 여러 시뮬레이션을 굴려 정보 상태 공간 앞쪽을 내다보는 방식이다.

문맥 밴딧

밴딧에 상태(맥락)를 더하면 실전에 한 발 다가선다. 문맥 밴딧은 튜플 $\langle \mathcal{A}, \mathcal{S}, \mathcal{R} \rangle$이다. $\mathcal{S} = \mathbb{P}[s]$는 알려지지 않은 상태(맥락) 분포이고, $\mathcal{R}^a_s(r) = \mathbb{P}[r \mid s, a]$는 상태와 행동에 조건 붙은 보상 분포다. 매 스텝 환경이 상태 $s_t \sim \mathcal{S}$를 내고, 에이전트가 행동 $a_t$를 고르면, 환경이 보상 $r_t \sim \mathcal{R}^{a_t}_{s_t}$를 준다. 뉴스 첫 화면에 어떤 기사를 걸까, 이 사용자에게 어떤 광고를 띄울까 같은 문제가 여기 딱 들어맞는다. 맥락(사용자, 시간대)에 따라 최선의 행동이 달라진다.

선형 UCB

가치함수를 선형 근사기로 추정한다. $Q_\theta(s, a) = \phi(s, a)^\top \theta \approx Q(s, a)$. 파라미터는 최소제곱 회귀로 구한다.

$$A_t = \sum_{\tau=1}^t \phi(s_\tau, a_\tau)\phi(s_\tau, a_\tau)^\top, \quad b_t = \sum_{\tau=1}^t \phi(s_\tau, a_\tau) r_\tau, \quad \theta_t = A_t^{-1} b_t$$

여기서 결정적인 관찰이 있다. 최소제곱 회귀는 평균 가치 $Q_\theta(s, a)$만 주는 게 아니라, 그 가치의 분산 $\sigma_\theta^2(s, a)$까지 준다. 파라미터 추정 오차에서 오는 불확실성이다. 그러니 불확실성만큼 보너스 $U_\theta(s, a) = c\sigma$를 얹으면 된다. 평균보다 $c$ 표준편차 위를 UCB로 삼는 것이다. 기하로 보면, 파라미터 $\theta_t$ 둘레에 참 파라미터 $\theta^*$를 높은 확률로 품는 신뢰 타원체 $\mathcal{E}_t$를 그리고, 그 안에서 가치를 최대로 하는 파라미터를 골라 불확실성을 반영한다.

최소제곱에서 파라미터 공분산이 $A^{-1}$이고 가치가 특징에 선형이므로, 가치의 분산은 이차식이 된다. $\sigma_\theta^2(s, a) = \phi(s, a)^\top A^{-1} \phi(s, a)$. 따라서 선택 규칙은

$$a_t = \arg\max_{a \in \mathcal{A}} Q_\theta(s_t, a) + c\sqrt{\phi(s_t, a)^\top A_t^{-1} \phi(s_t, a)}$$

밴딧의 $\sqrt{2\log t / N(a)}$가 문맥판에서 신뢰 타원체 폭 $c\sqrt{\phi^\top A^{-1} \phi}$로 자란 것이다. 실버는 이 선형 UCB로 뉴스 첫 화면 기사를 고른 리(Li) 등의 사례를 든다.

MDP로의 확장

밴딧에서 세운 다섯 원리는 그대로 MDP로 올라간다. 순진한 탐험, 낙관적 초기화, 불확실성 앞의 낙관, 확률 매칭, 정보 상태 탐색. 각각을 MDP판으로 옮겨 보자.

낙관적 초기화

모델프리로는 행동 가치를 낙관적으로 초기화한다.

$$Q(s, a) \leftarrow \frac{r_{\max}}{1 - \gamma}$$

이렇게 도달 가능한 최대치로 부풀려 두고, 몬테카를로 제어든 사르사든 Q-러닝이든 좋아하는 모델프리 알고리즘을 돌리면, 안 가 본 상태와 행동을 체계적으로 탐험하게 된다. 모델기반으로는 낙관적 MDP를 세운다. 아직 안 겪은 전이는 “천국으로 간다"고, 즉 $r_{\max}$ 보상을 주는 종료 상태로 간다고 초기화한다. 그리고 이 낙관적 MDP를 정책 반복이든 가치 반복이든 트리 탐색이든으로 푼다. 이것이 RMax 알고리즘(Brafman and Tennenholtz)이다.

불확실성 앞의 낙관

모델프리 UCB는 행동 가치의 상한을 최대로 한다. $a_t = \arg\max_a Q(s_t, a) + U(s_t, a)$. 정책 평가의 불확실성을 추정하는 것은 쉽지만, 정책 개선에서 오는 불확실성은 무시한다. 이를 제대로 반영해 최적 행동 가치 $Q^*$의 상한을 노리려면 $a_t = \arg\max_a Q(s_t, a) + U_1(s_t, a) + U_2(s_t, a)$처럼 개선에서 오는 불확실성 $U_2$까지 더해야 하는데, 이 부분이 까다롭다.

확률 매칭: 모델기반 톰프슨

베이지안 모델기반 강화학습은 MDP 모델 자체에 대한 사후분포 $p[\mathcal{P}, \mathcal{R} \mid h_t]$를 유지한다. 전이와 보상을 함께 추정하는 것이다. 이 사후로 톰프슨 표집을 하면 확률 매칭이 된다.

$$\pi(s, a \mid h_t) = \mathbb{E}_{\mathcal{P}, \mathcal{R} \mid h_t}\big[\mathbf{1}(a = \arg\max_a Q^*(s, a))\big]$$

절차가 밴딧판을 그대로 닮았다. 사후 $p[\mathcal{P}, \mathcal{R} \mid h_t]$를 계산하고, 거기서 MDP $\langle \mathcal{P}, \mathcal{R} \rangle$을 통째로 하나 표집하고, 그 표본 MDP를 좋아하는 플래닝 알고리즘으로 풀어 $Q^*$를 얻고, 그 표본에서 최적 행동을 고른다. 밴딧에서 보상 분포 하나를 뽑던 것이, MDP에서는 세계 전체를 하나 뽑아 그 안에서 계획하는 것으로 커진다.

정보 상태 탐색

MDP도 정보 상태를 붙여 확장할 수 있다. 확장된 상태는 $\langle s, \tilde{s} \rangle$로, $s$는 원래 MDP 안의 상태이고 $\tilde{s}$는 이력의 통계량(쌓인 정보)이다. 각 행동은 새 상태 $s'$로의 전이와 새 정보 상태 $\tilde{s}'$로의 전이를 함께 일으켜, 확장된 정보 상태 공간 위의 MDP $\tilde{\mathcal{M}}$를 정의한다.

특히 MDP 모델에 대한 사후분포 $\tilde{s}_t = \mathbb{P}[\mathcal{P}, \mathcal{R} \mid h_t]$ 자체가 하나의 정보 상태가 되고, $\langle s, \tilde{s} \rangle$ 위의 확장 MDP를 베이즈 적응 MDP라 부른다. 이걸 풀면 (사전분포에 대해) 최적의 탐험/활용 저울질이 나온다. 다만 밴딧에서와 마찬가지로 베이즈 적응 MDP는 대개 어마어마하게 커서, 시뮬레이션 기반 탐색(Guez et al.)이 효과적이었다.

맺으며

실버는 탐험과 활용의 여러 원리를 훑었다. $\epsilon$-탐욕 같은 순진한 방법, 낙관적 초기화, 신뢰 상한, 확률 매칭, 정보 상태 탐색. 이 다섯은 모두 가장 단순한 밴딧 무대에서 태어났지만, 똑같은 원리가 MDP에도 그대로 적용된다. 겉보기에 제각각이던 탐험 전략들이, 실은 하나의 다섯 갈래 지도 위에 놓여 있었던 셈이다.