강화학습 5강: 모델 프리 제어

4강은 정책을 평가만 했다(예측). 이제 그 도구로 최적 정책을 찾는다(제어). 모델을 모르는 채로, 즉 전이도 보상도 모른 채 경험만으로 최적에 다가간다. 핵심은 세 가지다. 왜 상태 가치가 아니라 행동 가치를 배워야 하는가, 어떻게 탐험을 섞어야 하는가, 그리고 행동하는 정책과 배우는 정책을 같게 둘 것인가 다르게 둘 것인가(온-폴리시 대 오프-폴리시).

강의 슬라이드: PDF

모델 프리 제어가 필요한 곳

엘리베이터 배차, 로보컵 축구, 평행 주차, 퀘이크, 배 조종, 포트폴리오 관리, 생물반응기, 단백질 접힘, 헬리콥터 곡예, 로봇 보행, 바둑. 실버가 나열하는 이 문제들은 거의 다 둘 중 하나다. MDP 모델을 아예 모르지만 경험을 뽑아낼 수는 있거나, 모델을 알긴 하지만 너무 커서 표본으로만 다룰 수 있거나. 어느 쪽이든 모델 프리 제어가 답을 준다.

온-폴리시와 오프-폴리시의 구분도 여기서 미리 잡아 두자. 온-폴리시는 “일하면서 배우기"다. 내가 따르는 정책 $\pi$에서 나온 경험으로 바로 그 $\pi$를 배운다. 오프-폴리시는 “남의 어깨너머로 배우기"다. 다른 정책 $\mu$가 만든 경험으로 내가 알고 싶은 정책 $\pi$를 배운다.

일반화 정책 반복을 모델 프리로

3강의 뼈대는 일반화 정책 반복이었다. 정책을 평가하고(가치 추정), 그 가치로 정책을 개선하고(탐욕화), 이걸 번갈아 돌리면 최적으로 수렴한다. 모델 프리에서도 골격은 같다. 평가 자리에 4강의 몬테카를로를 꽂으면 된다. 그런데 개선 자리에서 문제가 생긴다.

왜 상태 가치가 아니라 행동 가치인가

상태 가치 $V(s)$로 탐욕 개선을 하려면 이렇게 써야 한다.

$$\pi'(s) = \arg\max_{a\in\mathcal{A}} \Big( R_s^a + P_{ss'}^a\, V(s') \Big)$$

여기 전이 확률 $P_{ss'}^a$와 보상 $R_s^a$, 즉 모델이 들어 있다. 모델을 모르면 이 $\arg\max$를 계산할 수 없다. “이 행동을 하면 어디로 가서 얼마를 받는가"를 모르니 상태 가치만으로는 어느 행동이 좋은지 짚을 수 없는 것이다.

행동 가치 $Q(s,a)$를 배우면 이 벽이 사라진다.

$$\pi'(s) = \arg\max_{a\in\mathcal{A}} Q(s,a)$$

행동 가치는 이미 “각 행동의 값"을 통째로 담고 있으므로, 모델 없이 표에서 가장 큰 값을 고르기만 하면 개선이 끝난다. 그래서 모델 프리 제어는 $V$가 아니라 $Q$를 배운다. 평가 자리에 “몬테카를로로 $Q \approx q_\pi$”, 개선 자리에 “$Q$에 대한 탐욕"을 넣는 것이 출발점이다.

탐험을 섞어야 하는 이유: 두 개의 문

순수한 탐욕 개선에는 함정이 있다. 실버의 두 개의 문 예제가 이 함정을 선명하게 보여준다.

앞에 문이 둘 있다. 왼쪽 문을 열었더니 보상 $0$이다. $V(\text{left})=0$. 오른쪽 문을 열었더니 $+1$. $V(\text{right})=+1$. 다시 오른쪽을 열었더니 $+3$이라 평균이 $+2$로 올라간다. 또 오른쪽을 열어 $+2$, 여전히 평균 $+2$. 이제 탐욕적으로 굴면 오른쪽만 계속 연다. 오른쪽이 왼쪽보다 좋아 보이니까.

그런데 정말 최선의 문을 고른 게 맞나? 왼쪽은 딱 한 번 열어 봤을 뿐이다. 그때 우연히 $0$이 나왔을 수도 있고, 사실은 평균 $+10$짜리 노다지 문이었을 수도 있다. 왼쪽을 영영 다시 안 열면 그 진실을 영원히 모른다. 한 번의 나쁜 경험으로 문을 닫아 버리는 것, 이것이 순수 탐욕의 위험이다. 그래서 계속 조금씩은 탐험해야 한다.

ε-탐욕

탐험을 보장하는 가장 단순한 방법이다. $m$개의 모든 행동에 0이 아닌 확률을 주되, 확률 $1-\epsilon$로는 탐욕 행동을, 확률 $\epsilon$로는 무작위 행동을 택한다.

$$\pi(a|s) = \begin{cases} \epsilon/m + 1 - \epsilon & a^* = \arg\max_{a} Q(s,a) \\ \epsilon/m & \text{그 외} \end{cases}$$

대부분은 가장 좋아 보이는 행동을 하되, 가끔은 딴 문도 열어 본다. 왼쪽 문이 노다지였다면 언젠가 그 $\epsilon$의 순간에 들통난다.

ε-탐욕은 반드시 개선이다

$\epsilon$을 섞으면 탐욕보다 못해지지 않을까 걱정할 수 있다. 아니다. 실버는 이걸 정리로 못 박는다. 어떤 $\epsilon$-탐욕 정책 $\pi$든, 그 $q_\pi$에 대한 새 $\epsilon$-탐욕 정책 $\pi'$은 반드시 개선이다. 즉 $v_{\pi'}(s) \ge v_\pi(s)$.

증명의 핵심은 새 정책으로 한 걸음 뒀을 때의 값이 옛 정책의 값보다 크거나 같음을 보이는 것이다.

$$q_\pi(s,\pi'(s)) = \sum_{a} \pi'(a|s)\, q_\pi(s,a) = \frac{\epsilon}{m}\sum_{a} q_\pi(s,a) + (1-\epsilon)\max_a q_\pi(s,a)$$

여기서 $\max_a q_\pi(s,a)$는 어떤 가중 평균보다도 크거나 같다. 특히 옛 정책 $\pi$의 확률을 $\epsilon/m$만큼 덜어 낸 나머지로 만든 가중 평균보다 크다.

$$\ge \frac{\epsilon}{m}\sum_{a} q_\pi(s,a) + (1-\epsilon)\sum_{a} \frac{\pi(a|s) - \epsilon/m}{1-\epsilon}\, q_\pi(s,a) = \sum_{a}\pi(a|s)\, q_\pi(s,a) = v_\pi(s)$$

정리하면 $q_\pi(s,\pi'(s)) \ge v_\pi(s)$이고, 정책 개선 정리에 의해 $v_{\pi'}(s) \ge v_\pi(s)$이다. $\epsilon$-탐욕으로 개선해도 손해는 없다는 것, 이 보장이 있어야 안심하고 탐험을 섞을 수 있다.

GLIE

그런데 언제까지나 $\epsilon$만큼 무작위로 굴면 끝내 최적 정책에 딱 붙지는 못한다. 그래서 탐험은 무한히 하되 점점 줄여야 한다. 이 조건이 GLIE(Greedy in the Limit with Infinite Exploration)다. 두 가지를 요구한다.

• 모든 상태-행동 쌍을 무한히 방문한다: $\lim_{k\to\infty} N_k(s,a) = \infty$.
• 정책이 결국 탐욕으로 수렴한다: $\lim_{k\to\infty} \pi_k(a|s) = \mathbf{1}(a = \arg\max_{a'} Q_k(s,a'))$.

$\epsilon$-탐욕은 $\epsilon$을 0으로 줄이면 GLIE가 된다. 가장 간단한 스케줄이 $\epsilon = 1/k$다. 초반에는 많이 헤매고(작은 $k$면 큰 $\epsilon$), 회를 거듭할수록 탐험을 줄여 탐욕으로 수렴한다. 무한히 탐험하면서도 결국 최적을 골라내는 절묘한 균형이다.

GLIE 몬테카를로 제어

이제 한 알고리즘으로 조립된다. $k$번째 에피소드를 현재 정책 $\pi$로 뽑는다. 그 에피소드의 각 상태 $S_t$, 행동 $A_t$에 대해

$$N(S_t,A_t) \leftarrow N(S_t,A_t) + 1$$

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \frac{1}{N(S_t,A_t)}\big(G_t - Q(S_t,A_t)\big)$$

로 행동 가치를 리턴의 평균 쪽으로 당긴다. 그다음 $\epsilon \leftarrow 1/k$로 줄이고 $\pi \leftarrow \epsilon\text{-탐욕}(Q)$로 정책을 개선한다. 정리에 의해 이 GLIE 몬테카를로 제어는 최적 행동 가치로 수렴한다. $Q(s,a) \to q_*(s,a)$.

실버의 예는 다시 블랙잭이다. 딜러 규칙도 확률도 모른 채 수많은 판을 실제로 치며 $Q$를 갱신하고 $\epsilon$-탐욕으로 정책을 다듬으면, 사람이 카드로 정리해 둔 ‘기본 전략’ 표에 아주 가까운 정책이 저절로 떠오른다. 언제 카드를 더 받고 언제 멈출지를 경험만으로 학습해 낸 것이다.

온-폴리시 TD 제어: Sarsa

몬테카를로 대신 시간차 학습을 제어 루프에 꽂으면 자연스러운 개선이 된다. TD는 MC보다 분산이 낮고, 온라인이며, 끝나지 않은 열에서도 배운다. 그러니 $Q(S,A)$에 TD를 적용하고, $\epsilon$-탐욕으로 개선하고, 매 걸음 갱신하자는 것이 발상이다.

실제로 택한 다음 행동 $A'$로 갱신한다. 상태, 행동, 보상, 다음 상태, 다음 행동을 다 쓴다고 해서 Sarsa다.

$$Q(S,A) \leftarrow Q(S,A) + \alpha\,\big(R + \gamma Q(S',A') - Q(S,A)\big)$$

행동을 고르는 정책과 배우는 정책이 같다(온-폴리시). 매 걸음마다 평가(Sarsa로 $Q\approx q_\pi$)와 개선($\epsilon$-탐욕)을 함께 돌린다.

Sarsa가 최적 행동 가치로 수렴하려면 두 조건이 필요하다. 하나는 앞서 본 GLIE 정책열이고, 다른 하나는 스텝사이즈 $\alpha_t$가 로빈스-먼로 조건을 만족하는 것이다. 즉 $\sum_{t=1}^{\infty}\alpha_t = \infty$이고 $\sum_{t=1}^{\infty}\alpha_t^2 < \infty$. 앞의 합이 무한이라는 건 아무리 멀리 가야 하는 값이라도 결국 도달할 만큼 보폭 총량이 충분하다는 뜻이고, 뒤의 합이 유한이라는 건 잡음이 점차 잦아들어 값이 한 점에 안착한다는 뜻이다. (실무에서는 이 조건을 엄밀히 지키지 않고 작은 상수 $\alpha$를 쓰는 경우가 많다.)

바람 부는 격자

실버의 예는 바람 부는 격자다. 출발점에서 도착점까지 상하좌우로 움직이는데, 도착할 때까지 매 걸음 보상 $-1$이다(할인 없음). 그러니 최대한 빨리 도착하는 것이 목표다. 함정은 특정 열들에 위로 부는 바람이 있다는 점이다. 그 열에서는 내가 이동한 뒤 바람이 말을 위로 한두 칸 더 밀어 올린다. Sarsa는 이 바람을 감안해 돌아가는 경로를 배운다. 바람이 미는 방향을 미리 계산에 넣어, 목표에 정확히 안착하는 우회로를 찾아낸다.

n-스텝 Sarsa와 Sarsa(λ)

예측에서 그랬듯 제어에서도 한 걸음과 끝까지는 양극단일 뿐이다. n걸음을 내다보는 n-스텝 Q-리턴이 그 사이를 잇는다.

$$q_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q(S_{t+n})$$

$n=1$이면 $R_{t+1} + \gamma Q(S_{t+1})$로 보통의 Sarsa이고, $n=\infty$면 에피소드 끝까지 가는 몬테카를로다. n-스텝 Sarsa는 $Q$를 이 n-스텝 Q-리턴 쪽으로 당긴다.

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\big(q_t^{(n)} - Q(S_t,A_t)\big)$$

전방 뷰 Sarsa(λ)는 모든 n의 Q-리턴을 $(1-\lambda)\lambda^{n-1}$의 가중치로 한꺼번에 섞은 $q^\lambda$-리턴을 목표로 쓴다.

$$q_t^\lambda = (1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1} q_t^{(n)}, \qquad Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\big(q_t^\lambda - Q(S_t,A_t)\big)$$

전방 뷰는 미래를 다 봐야 하므로 에피소드가 끝나야 계산된다. 후방 뷰 Sarsa(λ)는 적격 흔적으로 같은 일을 온라인으로 해낸다. 다만 이제 흔적은 상태별이 아니라 각 (상태, 행동) 쌍마다 하나씩 붙는다.

$$E_0(s,a) = 0, \qquad E_t(s,a) = \gamma\lambda\, E_{t-1}(s,a) + \mathbf{1}(S_t = s, A_t = a)$$

그리고 TD 오차 $\delta_t = R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)$를 이 흔적에 비례해 모든 쌍으로 흘려보낸다.

$$Q(s,a) \leftarrow Q(s,a) + \alpha\,\delta_t\, E_t(s,a)$$

직관은 이렇다. 어쩌다 보상에 도착하면, 그 좋은 신호가 방금 밟은 (상태, 행동) 쌍들로 흔적을 따라 한꺼번에 번진다. 최근에 밟았을수록 흔적이 진하니 더 크게 보정받는다. 보상이 드문 문제에서 이 번짐 덕에 학습이 크게 빨라진다. 실버의 격자 예를 보면, 한 걸음짜리 Sarsa(0)는 목표 바로 앞 한 칸만 값이 오르는 반면, Sarsa(λ)는 목표로 이어진 경로 전체에 한 번에 신용이 배분된다.

오프-폴리시 학습

지금까지는 행동하는 정책과 배우는 정책이 같았다. 오프-폴리시는 이 둘을 분리한다. 행동 정책 $\mu$를 따라 $\{S_1,A_1,R_2,\dots,S_T\}\sim\mu$를 겪으면서, 목표 정책 $\pi$의 가치 $v_\pi(s)$나 $q_\pi(s,a)$를 배운다. 왜 이게 중요한가. 실버는 네 가지 동기를 든다.

• 사람이나 다른 에이전트를 관찰해서 배운다. 남의 플레이를 보고 배우는 것이다.
• 옛 정책들 $\pi_1,\pi_2,\dots,\pi_{t-1}$이 만든 경험을 재사용한다. 버리지 않고 다시 쓴다.
• 탐험적인 정책을 따르면서도 최적 정책을 배운다. 이것이 Q-러닝의 핵심 동기다.
• 하나의 행동 정책을 따르면서 여러 목표 정책을 동시에 배운다.

중요도 표본

문제는 $\mu$가 만든 경험으로 $\pi$의 기댓값을 어떻게 추정하느냐다. 답이 중요도 표본이다. 다른 분포 $P$에 대한 기댓값을 손에 있는 분포 $Q$로 다시 쓰는 재주다.

$$\mathbb{E}_{X\sim P}[f(X)] = \sum_X P(X) f(X) = \sum_X Q(X)\frac{P(X)}{Q(X)}f(X) = \mathbb{E}_{X\sim Q}\left[\frac{P(X)}{Q(X)}f(X)\right]$$

두 분포의 비율 $P/Q$로 무게를 다시 매기는 것이다.

몬테카를로에 이걸 쓰면, $\mu$로 만든 리턴 $G_t$에 두 정책의 유사도를 곱해 보정한다. 문제는 리턴이 에피소드 끝까지 이어지므로, 매 걸음의 확률비를 에피소드 내내 곱해야 한다는 점이다.

$$G_t^{\pi/\mu} = \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}\frac{\pi(A_{t+1}|S_{t+1})}{\mu(A_{t+1}|S_{t+1})}\cdots\frac{\pi(A_T|S_T)}{\mu(A_T|S_T)}\, G_t$$$$V(S_t) \leftarrow V(S_t) + \alpha\big(G_t^{\pi/\mu} - V(S_t)\big)$$

$\pi$가 0이 아닌데 $\mu$가 0이면 쓸 수 없고(겪지 않은 경험은 보정도 못 한다), 무엇보다 확률비를 수십 번 곱하다 보면 분산이 폭발한다. 하나만 아주 작거나 커도 곱 전체가 요동친다. 그래서 MC 중요도 표본은 실전에서 거의 못 쓴다.

TD에 쓰면 사정이 크게 나아진다. TD 타깃 $R + \gamma V(S')$은 딱 한 걸음짜리라, 단 한 번의 중요도 보정만 필요하다.

$$V(S_t) \leftarrow V(S_t) + \alpha\left(\frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}\big(R_{t+1} + \gamma V(S_{t+1})\big) - V(S_t)\right)$$

두 정책이 한 걸음만 비슷하면 되므로 분산이 몬테카를로보다 훨씬 낮다.

Q-러닝: 중요도 표본이 아예 필요 없다

행동 가치 $Q(s,a)$의 오프-폴리시 학습에서는 더 극적인 일이 벌어진다. 중요도 표본이 아예 필요 없다. 이유는 이렇다. 다음에 실제로 할 행동 $A_{t+1}$은 행동 정책 $\mu$로 고르지만, 타깃 안에서는 목표 정책 $\pi$가 고른 대안 행동 $A'\sim\pi(\cdot|S_t)$의 값을 바로 쓴다.

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\big(R_{t+1} + \gamma Q(S_{t+1},A') - Q(S_t,A_t)\big)$$

타깃에서 이미 $\pi$가 고른 행동을 직접 넣으므로, 나중에 확률비로 보정할 것이 남지 않는다. 여기서 목표 정책 $\pi$를 $Q$에 대해 탐욕으로 두면, 즉 $\pi(S_{t+1}) = \arg\max_{a'} Q(S_{t+1},a')$로 두면 타깃이 깔끔하게 단순해진다.

$$R_{t+1} + \gamma Q(S_{t+1}, \arg\max_{a'} Q(S_{t+1},a')) = R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a')$$

$\pi$가 고른 대안 행동이 곧 $Q$를 최대화하는 행동이니, $\arg\max$가 $\max$로 접힌다. 이것이 Q-러닝의 그 유명한 갱신식이다.

$$Q(S,A) \leftarrow Q(S,A) + \alpha\,\big(R + \gamma \max_{a'} Q(S',a') - Q(S,A)\big)$$

행동은 $\epsilon$-탐욕 같은 탐험 정책 $\mu$로 하되, 배우는 대상은 탐욕적인 최적 정책이다. 행동 정책과 목표 정책이 함께 개선되며, Q-러닝은 최적 행동 가치로 수렴한다. $Q(s,a) \to q_*(s,a)$.

벼랑 걷기

온-폴리시(Sarsa)와 오프-폴리시(Q-러닝)의 차이를 벼랑 걷기 예가 잘 보여준다. 격자 아래쪽 가장자리가 벼랑이고, 벼랑에 빠지면 큰 벌점을 받고 출발점으로 돌아간다. 목표는 벼랑을 피해 반대쪽 끝에 닿는 것이다.

Q-러닝은 벼랑 바로 옆을 따라가는 최단 경로를 배운다. 목표 정책이 탐욕이라 “최적은 벼랑 옆 직선"이라는 걸 곧장 익힌다. 문제는 실제로 걸을 때는 $\epsilon$-탐욕으로 움직이므로, 가끔 그 $\epsilon$의 순간에 벼랑으로 발을 헛디딘다. 그래서 학습 중 실제 성적은 자주 곤두박질친다.

Sarsa는 다르다. 온-폴리시라 실제로 택하는 다음 행동, 즉 탐험까지 포함한 행동으로 배운다. “가끔 무작위로 움직일 나 자신"을 계산에 넣으니, 벼랑에서 한 칸 떨어진 안전한 우회로를 배운다. 최적은 아니지만 탐험 중 사고가 적어 실제 성적은 더 낫다. 최적을 아는 Q-러닝과 탐험까지 감안해 안전한 Sarsa, 둘의 성격 차이가 여기서 또렷하다.

벼랑 걷기. 아래 가장자리가 벼랑(−100)이고 S에서 G로 가야 한다. 에피소드를 돌리면 Q-러닝은 벼랑 바로 옆 최단 경로(빨강)를, Sarsa는 탐험까지 감안해 한 칸 떨어진 안전 경로(파랑)를 배운다. ε을 키우면 Sarsa가 더 멀리 돌아가는 것을 볼 수 있다.

DP와 TD, 한눈에

제어까지 오면 3강의 동적 계획법과 이번 강의 대응이 또렷해진다. 같은 벨만 방정식을, 모델을 알면 전폭 백업으로 풀고 모르면 표본 백업으로 푸는 셈이다. 대응은 이렇게 짝지어진다.

• 벨만 기대 방정식($v_\pi$): 전폭이면 반복 정책 평가, 표본이면 TD 학습.
• 벨만 기대 방정식($q_\pi$): 전폭이면 Q-정책 반복, 표본이면 Sarsa.
• 벨만 최적 방정식($q_*$): 전폭이면 Q-가치 반복, 표본이면 Q-러닝.

갱신식으로 나란히 두면 대응이 더 선명하다. $x \xleftarrow{\alpha} y$를 $x \leftarrow x + \alpha(y-x)$의 약속이라 하면,

$$Q(s,a) \leftarrow \mathbb{E}[R + \gamma Q(S',A') \mid s,a] \quad\Longleftrightarrow\quad Q(S,A) \xleftarrow{\alpha} R + \gamma Q(S',A')$$

왼쪽은 기댓값을 모델로 전부 훑는 Q-정책 반복이고, 오른쪽은 겪은 표본 하나로 그 자리를 메우는 Sarsa다. 최적 방정식도 똑같은 구조다.

$$Q(s,a) \leftarrow \mathbb{E}\Big[R + \gamma \max_{a'} Q(S',a') \mid s,a\Big] \quad\Longleftrightarrow\quad Q(S,A) \xleftarrow{\alpha} R + \gamma \max_{a'} Q(S',a')$$

DP에서 배운 골격이 모델 프리에서 기댓값 대신 표본으로 그대로 되풀이되는 것이다.

이 Q-러닝이 6강에서 신경망과 만나 DQN이 된다. 그리고 여기까지는 상태를 표에 하나씩 저장했다(테이블형). 상태가 아주 많거나 연속이면 표가 불가능하다. 다음 강은 가치함수를 함수로 근사한다.