지금까지는 상태마다 칸을 하나씩 두는 표로 가치를 적었다. 하지만 백개먼은 상태가 $10^{20}$개, 바둑은 $10^{170}$개, 헬리콥터는 아예 연속이라 칸을 셀 수조차 없다. 표는 여기서 무너진다. 대신 파라미터 몇 개짜리 함수로 가치를 근사하고, 본 적 없는 상태로도 일반화한다.
강의 슬라이드: PDF
왜 표를 버리는가
표 룩업의 문제는 두 가지다. 상태나 행동이 너무 많아 메모리에 다 못 담고, 담더라도 각 상태의 가치를 하나씩 따로 배우는 건 너무 느리다. 한 번도 안 가 본 상태는 영원히 모른다.
해법은 함수 근사다. 참 가치 $v_\pi(s)$를 파라미터 $\mathbf{w}$를 가진 근사 함수로 대신한다.
$$\hat v(s, \mathbf{w}) \approx v_\pi(s) \quad\text{또는}\quad \hat q(s, a, \mathbf{w}) \approx q_\pi(s, a)$$파라미터는 상태 수보다 훨씬 적다. 그래서 본 상태에서 배운 것이 안 본 상태로 새어 나간다(일반화). 그리고 이 $\mathbf{w}$를 앞 강의에서 배운 MC나 TD로 갱신한다.
근사기를 어떻게 연결하느냐에 따라 세 가지 아키텍처가 있다.
- 상태 하나를 넣어 그 상태의 가치 $\hat v(s, \mathbf{w})$ 하나를 뱉는다.
- 상태와 행동을 함께 넣어 그 짝의 행동가치 $\hat q(s, a, \mathbf{w})$ 하나를 뱉는다.
- 상태 하나만 넣고, 가능한 모든 행동의 행동가치 $\hat q(s, a_1, \mathbf{w}), \dots, \hat q(s, a_m, \mathbf{w})$를 한꺼번에 뱉는다.
세 번째가 DQN이 쓰는 방식이다. 제어에서는 $\max_a \hat q(s, a)$를 자주 구해야 하는데, 세 번째 구조면 한 번의 전방 계산으로 모든 행동값이 나오므로 그 최댓값 고르기가 공짜에 가깝다.
근사기 후보는 많다. 특징의 선형 결합, 신경망, 결정 트리, 최근접 이웃, 푸리에나 웨이블릿 기저 등. 이 강의는 그중 미분 가능한 것만 다룬다(경사를 따라야 하니까). 선형 결합과 신경망이 그 주인공이다.
그리고 중요한 단서가 하나 있다. 강화학습의 데이터는 일반 지도학습과 다르다. 정책이 바뀌면 데이터 분포가 바뀌니 비정상이고, 연속한 상태들은 서로 강하게 얽혀 독립·동일분포(iid)가 아니다. 그래서 지도학습을 그대로 가져다 쓸 수 없고, 이런 데이터에 맞는 학습법이 따로 필요하다. 이 강의의 절반이 그 이야기다.
증분법: 경사를 타고 내려가기
목표는 뚜렷하다. 근사 가치와 참 가치의 평균제곱오차를 줄이는 것이다.
$$J(\mathbf{w}) = \mathbb{E}_\pi\big[(v_\pi(S) - \hat v(S, \mathbf{w}))^2\big]$$이 $J$의 경사 반대 방향으로 $\mathbf{w}$를 조금씩 밀면 지역 최솟값으로 내려간다. 스텝 크기 $\alpha$를 두고 $\Delta\mathbf{w} = -\tfrac{1}{2}\alpha\nabla_\mathbf{w}J(\mathbf{w})$이다. 기댓값을 풀면
$$\Delta\mathbf{w} = \alpha\,\mathbb{E}_\pi\big[(v_\pi(S) - \hat v(S, \mathbf{w}))\nabla_\mathbf{w}\hat v(S, \mathbf{w})\big]$$전체 기댓값을 매번 계산하는 건 비싸다. 그래서 한 번에 표본 하나만 뽑아 경사를 흉내 낸다. 이게 확률적 경사하강(SGD)이다.
$$\Delta\mathbf{w} = \alpha\,(v_\pi(S) - \hat v(S, \mathbf{w}))\nabla_\mathbf{w}\hat v(S, \mathbf{w})$$표본 하나짜리 갱신의 기댓값이 전체 경사 갱신과 같으므로, 많이 반복하면 결국 같은 곳으로 간다.
특징 벡터와 선형 근사
상태를 숫자 몇 개로 요약한 것이 특징 벡터다.
$$\mathbf{x}(S) = \big(x_1(S), \dots, x_n(S)\big)^\top$$로봇이 랜드마크들로부터 떨어진 거리, 주식 시장의 추세, 체스판의 말 배치 같은 것이 특징이 된다. 가장 단순한 근사는 이 특징들을 선형으로 결합하는 것이다.
$$\hat v(S, \mathbf{w}) = \mathbf{x}(S)^\top \mathbf{w} = \sum_{j=1}^{n} x_j(S)\,w_j$$이때 목적함수는 $\mathbf{w}$에 대해 이차식이라 지역 최솟값이 곧 전역 최솟값이다. SGD가 전역 최적으로 수렴한다. 게다가 경사가 아주 깔끔하다. $\nabla_\mathbf{w}\hat v(S, \mathbf{w}) = \mathbf{x}(S)$이므로 갱신식이
$$\Delta\mathbf{w} = \alpha\,(v_\pi(S) - \hat v(S, \mathbf{w}))\,\mathbf{x}(S)$$가 된다. 말로 풀면 갱신 = 스텝 크기 × 예측 오차 × 특징값이다. 오차가 크고 그 특징이 강하게 켜져 있던 방향으로 파라미터를 민다.
여기서 재미있는 사실 하나. 표 룩업은 선형 근사의 특수한 경우다. 특징을 “이 상태냐 아니냐"의 지시자로 잡으면
$$\mathbf{x}^{\text{table}}(S) = \big(\mathbf{1}(S = s_1), \dots, \mathbf{1}(S = s_n)\big)^\top$$이 특징 벡터와 $\mathbf{w}$를 곱하면 현재 상태에 해당하는 칸의 $w_i$만 살아남는다. 즉 파라미터 벡터가 각 상태의 가치를 그대로 담는 표가 된다. 표는 근사의 반대가 아니라, 특징을 극단적으로 잘게 쪼갠 한쪽 끝일 뿐이다.
참값이 없다: 목표를 갈아 끼우기
지금까지 식에는 참 가치 $v_\pi(S)$가 들어 있었다. 하지만 강화학습에는 정답을 알려 주는 감독자가 없다. 오직 보상뿐이다. 그래서 $v_\pi(S)$ 자리에 앞 강의에서 만든 목표를 대신 끼운다.
- MC는 실제 리턴 $G_t$를 목표로: $$\Delta\mathbf{w} = \alpha\,(G_t - \hat v(S_t, \mathbf{w}))\nabla_\mathbf{w}\hat v(S_t, \mathbf{w})$$
- TD(0)은 부트스트랩한 TD 목표 $R_{t+1} + \gamma\hat v(S_{t+1}, \mathbf{w})$을: $$\Delta\mathbf{w} = \alpha\,(R_{t+1} + \gamma\hat v(S_{t+1}, \mathbf{w}) - \hat v(S_t, \mathbf{w}))\nabla_\mathbf{w}\hat v(S_t, \mathbf{w})$$
- TD(λ)는 λ-리턴 $G_t^\lambda$를: $$\Delta\mathbf{w} = \alpha\,(G_t^\lambda - \hat v(S_t, \mathbf{w}))\nabla_\mathbf{w}\hat v(S_t, \mathbf{w})$$
MC의 리턴은 참값의 무편향(다만 시끄러운) 표본이다. 그래서 $\langle S_1, G_1\rangle, \langle S_2, G_2\rangle, \dots$을 훈련 데이터 삼아 지도학습처럼 돌릴 수 있고, 비선형 근사기를 써도 지역 최적으로 수렴한다.
TD 목표는 아직 틀린 추정치 $\hat v(S_{t+1}, \mathbf{w})$를 품고 있어 편향된 표본이다. 그래도 훈련 데이터로 세워 학습할 수 있고, 선형 TD(0)은 전역 최적 근처로 수렴한다. 선형 TD(0)의 갱신은 TD 오차 $\delta$를 써서 $\Delta\mathbf{w} = \alpha\delta\,\mathbf{x}(S)$로 깔끔하게 쓰인다.
TD(λ)도 마찬가지로 전방 뷰(λ-리턴을 목표로)와 후방 뷰(적격 흔적으로 온라인 처리)가 있고, 선형에서는 둘이 정확히 같은 갱신을 준다. 후방 뷰는
$$\delta_t = R_{t+1} + \gamma\hat v(S_{t+1}, \mathbf{w}) - \hat v(S_t, \mathbf{w})$$$$E_t = \gamma\lambda E_{t-1} + \mathbf{x}(S_t), \qquad \Delta\mathbf{w} = \alpha\delta_t E_t$$이제 흔적이 상태 지시자가 아니라 특징 벡터 $\mathbf{x}(S_t)$를 쌓는다는 점만 4강과 다르다.
제어: 행동가치를 근사하기
예측을 넘어 제어로 가려면 상태가치가 아니라 행동가치를 근사한다. $\hat q(S, A, \mathbf{w}) \approx q_\pi(S, A)$의 평균제곱오차를 줄이고, 근사한 $\hat q$로 정책을 $\varepsilon$-탐욕적으로 개선하는 일반화된 정책 반복을 돈다. 선형이면 상태·행동을 함께 특징화해 $\mathbf{x}(S, A)$로 두고
$$\hat q(S, A, \mathbf{w}) = \mathbf{x}(S, A)^\top\mathbf{w}, \qquad \Delta\mathbf{w} = \alpha\,(q_\pi(S, A) - \hat q(S, A, \mathbf{w}))\mathbf{x}(S, A)$$로 갱신한다. 예측 때처럼 $q_\pi$ 자리에 MC면 $G_t$, TD(0)이면 $R_{t+1} + \gamma\hat q(S_{t+1}, A_{t+1}, \mathbf{w})$, TD(λ)면 λ-리턴을 끼운다. TD(0) 버전이 곧 근사기를 얹은 사르사다.
마운틴 카: 연속 상태를 특징으로
마운틴 카는 힘이 모자란 자동차가 골짜기에 갇혀 있는 문제다. 그냥 오른쪽으로 밀면 못 올라가고, 일부러 반대편 언덕으로 후진했다가 반동으로 넘어야 한다. 상태는 위치와 속도, 둘 다 연속이다. 칸이 무한하니 표는 못 쓴다.
실버는 여기에 선형 사르사를 얹는다. 연속 상태를 특징으로 바꾸는 방법이 관건인데, 거친 부호화(coarse coding)를 쓴다. 위치·속도 평면을 서로 겹치는 여러 격자(타일)로 덮고, 지금 상태가 어느 타일들 안에 있는지를 켜고 끄는 지시자로 특징을 만든다. 한 점이 여러 타일에 동시에 걸치므로 인접한 상태끼리 특징을 공유하고, 그래서 매끄럽게 일반화된다. 타일 대신 방사기저함수(RBF, 중심에서 멀어질수록 부드럽게 줄어드는 종 모양 특징)를 써도 비슷하게 연속 표면을 덮을 수 있다.
이렇게 특징만 만들어 주면 나머지는 앞서 본 선형 사르사 갱신 그대로다. 학습이 진행되면서 골짜기 모양의 가치 표면이 점점 또렷해지고, 반동으로 언덕을 넘는 정책이 자연히 떠오른다.
부트스트랩을 해야 하나
증분법에서 자연스레 따라오는 질문. λ를 얼마로 둘까. $\lambda = 0$은 완전 부트스트랩(TD), $\lambda = 1$은 부트스트랩 없음(MC), 그 사이가 절충이다.
실버는 여러 도메인(마운틴 카를 포함한)에서 λ를 바꿔 가며 성능을 재 본 그래프를 보여 준다. 결론은 한결같다. $\lambda = 1$(순수 MC)은 거의 항상 최악이고, 성능이 가장 좋은 지점은 대개 그 중간 어딘가다. 4강에서 부트스트랩과 샘플링을 두 축으로 그렸던 스펙트럼이, 함수 근사를 얹은 실전에서도 그대로 실증되는 셈이다. 부트스트랩은 편향을 감수하고 분산을 크게 줄이는데, 근사기의 잡음과 만나면 그 분산 절감의 이득이 특히 크다.
베어드 반례: 발산의 순간
좋은 소식이 여기서 끝난다. 세 가지가 겹치면(오프폴리시 + 선형 근사 + TD), 학습이 수렴하기는커녕 파라미터가 실제로 무한대로 발산한다. 베어드 반례가 그 구체적 증거다. 몇 개 안 되는 상태로 이루어진 작은 MDP인데, 오프폴리시로 선형 TD를 돌리면 가중치가 반복마다 점점 커져 그래프가 폭발한다. 버그가 아니라 알고리즘의 성질이다.
수렴 표로 정리하면 이렇다.
| 표 룩업 | 선형 | 비선형 | |
|---|---|---|---|
| 온폴리시 MC | O | O | O |
| 온폴리시 TD(0) | O | O | X |
| 온폴리시 TD(λ) | O | O | X |
| 오프폴리시 MC | O | O | O |
| 오프폴리시 TD(0) | O | X | X |
| 오프폴리시 TD(λ) | O | X | X |
오프폴리시 + 선형 + TD 칸이 바로 X, 베어드가 터지는 자리다.
근본 원인을 짚으면 이렇다. TD 갱신은 어떤 목적함수의 진짜 경사가 아니다. 겉보기엔 $\Delta\mathbf{w} = \alpha\delta\,\mathbf{x}(S)$가 경사하강처럼 생겼지만, TD 목표 안의 $\hat v(S_{t+1}, \mathbf{w})$도 $\mathbf{w}$에 의존하는데 우리는 그 부분을 미분하지 않고 상수처럼 얼려 둔다(준경사). 진짜 경사가 아니므로 “언덕을 내려간다"는 보장이 없고, 오프폴리시로 데이터 분포가 어긋나면 오히려 언덕을 기어오를 수 있다.
처방은 진짜 경사를 따르게 만드는 것이다. 경사 TD(Gradient TD)는 투영 벨만 오차라는 잘 정의된 목적함수의 실제 경사를 따라 내려간다. 그러면 오프폴리시에 선형·비선형 근사를 얹어도 수렴이 회복된다.
| 표 룩업 | 선형 | 비선형 | |
|---|---|---|---|
| 오프폴리시 TD | O | X | X |
| 오프폴리시 경사 TD | O | O | O |
제어로 가면 상황이 한 겹 더 미묘하다. 선형 근사를 쓴 몬테카를로 제어나 사르사는 대개 최적 근처로 가긴 하지만, 정확히 한 점에 멈추지 않고 근사 최적 주변을 계속 진동한다(chattering). 정책이 조금 바뀌면 가치가 바뀌고, 그 가치가 다시 정책을 조금 바꾸는 되먹임 때문이다. 선형 Q-러닝은 아예 발산할 수 있고, 경사 Q-러닝이 이를 다잡는다.
배치법: 경험을 모아 한 번에
증분법(SGD)은 단순하고 매력적이지만 표본을 낭비한다. 한 번 갱신에 쓴 경험을 버리기 때문이다. 배치법은 반대로 묻는다. 지금까지 모은 경험 전체에 가장 잘 맞는 가치 함수는 무엇인가.
경험을 상태·가치 쌍의 모음 $\mathcal{D} = \{\langle s_1, v_1^\pi\rangle, \dots, \langle s_T, v_T^\pi\rangle\}$로 두면, 최소제곱은 이 전체에 대한 오차 합을 최소화하는 $\mathbf{w}$를 찾는다.
$$LS(\mathbf{w}) = \sum_{t=1}^{T}(v_t^\pi - \hat v(s_t, \mathbf{w}))^2$$경험 재생
이 최소제곱 해를 SGD로도 얻을 수 있다. 매 스텝 새 경험만 쓰는 대신, 저장해 둔 경험 풀 $\mathcal{D}$에서 쌍을 무작위로 다시 뽑아 갱신하기를 반복한다.
- 경험에서 표본을 뽑는다: $\langle s, v^\pi\rangle \sim \mathcal{D}$
- SGD 갱신을 적용한다: $\Delta\mathbf{w} = \alpha\,(v^\pi - \hat v(s, \mathbf{w}))\nabla_\mathbf{w}\hat v(s, \mathbf{w})$
이걸 충분히 반복하면 최소제곱 해 $\mathbf{w}^\pi = \arg\min_\mathbf{w} LS(\mathbf{w})$로 수렴한다. 이게 경험 재생(experience replay)이다. 같은 경험을 여러 번 우려먹으니 표본 효율이 올라가고, 무작위로 섞어 뽑으니 연속 상태끼리의 상관(non-iid 문제)도 깨진다.
선형이면 닫힌 해
근사가 선형 $\hat v(s, \mathbf{w}) = \mathbf{x}(s)^\top\mathbf{w}$이면 반복할 필요도 없다. 최소제곱 해를 바로 계산할 수 있다. 최솟점에서는 기대 갱신이 0이어야 하므로
$$\sum_{t=1}^{T}\mathbf{x}(s_t)(v_t^\pi - \mathbf{x}(s_t)^\top\mathbf{w}) = 0$$을 풀면
$$\mathbf{w} = \left(\sum_{t=1}^{T}\mathbf{x}(s_t)\mathbf{x}(s_t)^\top\right)^{-1}\sum_{t=1}^{T}\mathbf{x}(s_t)v_t^\pi$$가 나온다. 특징이 $N$개면 이 직접 해는 역행렬 때문에 $O(N^3)$이 든다(셔먼-모리슨으로 증분 갱신하면 $O(N^2)$).
참값 $v_t^\pi$를 모르는 건 여기서도 마찬가지라, 그 자리에 노이즈 섞인 표본을 끼운다. 리턴을 쓰면 LSMC, TD 목표를 쓰면 LSTD, λ-리턴을 쓰면 LSTD(λ)다. 각 경우 MC·TD·TD(λ)의 고정점을 곧바로 닫힌 해로 푼다. 흥미롭게도 오프폴리시에서 증분 TD는 발산해도, 그 고정점을 직접 푸는 LSTD는 선형에서 수렴한다.
제어로 확장한 것이 최소제곱 정책 반복(LSPI)이다. 저장한 경험 $\mathcal{D}$를 정책을 바꿔 가며 반복해 재평가한다. 안쪽에서 LSTDQ로 행동가치를 오프폴리시로 최소제곱 평가하고(옛 정책이 만든 전이에서, 새 정책이 고를 후속 행동 $A' = \pi_{\text{new}}(S_{t+1})$의 값 쪽으로 당긴다), 바깥에서 $\pi'(s) = \arg\max_a Q(s, a)$로 탐욕 개선하기를 정책이 안정될 때까지 돈다. 실버는 50개 상태의 체인 워크 문제에서 LSPI가 몇 번의 반복 만에 최적 정책으로 수렴하는 걸 보인다.
DQN: 재생과 고정 타깃
경험 재생이라는 아이디어가 비선형 근사(심층 신경망)와 만나 폭발한 것이 DQN이다. DQN은 두 장치로 학습을 안정시킨다.
- 경험 재생: $\varepsilon$-탐욕 정책으로 행동하고 전이 $(s_t, a_t, r_{t+1}, s_{t+1})$를 재생 메모리 $\mathcal{D}$에 쌓는다. 학습할 땐 거기서 미니배치를 무작위로 뽑는다. 상관을 깨고 표본을 재활용한다.
- 고정 타깃 네트워크: Q-러닝 목표를 계산할 때 지금 학습 중인 파라미터 $\mathbf{w}$가 아니라, 한동안 얼려 둔 옛 파라미터 $\mathbf{w}^-$를 쓴다. 목표가 학습과 함께 매 스텝 흔들리는 걸 막는다.
손실은
$$L_i(\mathbf{w}_i) = \mathbb{E}_{s,a,r,s' \sim \mathcal{D}_i}\left[\left(r + \gamma\max_{a'}Q(s', a'; \mathbf{w}_i^-) - Q(s, a; \mathbf{w}_i)\right)^2\right]$$이고, SGD의 변형으로 최소화한다. 목표 안이 $\mathbf{w}_i^-$(얼린 것), 예측이 $\mathbf{w}_i$(학습 중)인 점이 핵심이다.
이 두 장치가 각각 얼마나 기여하는지, 절제 실험이 뚜렷하게 보여 준다. 다섯 게임에서 재생·고정타깃을 켜고 끈 점수다.
| 게임 | 재생+고정타깃 | 재생만 | 고정타깃만 | 둘 다 없음 |
|---|---|---|---|---|
| 브레이크아웃 | 316.8 | 240.7 | 10.2 | 3.2 |
| 엔듀로 | 1006.3 | 831.3 | 141.9 | 29.1 |
| 리버 레이드 | 7446.6 | 4102.8 | 2867.7 | 1453.0 |
| 시퀘스트 | 2894.4 | 822.6 | 1003.0 | 275.8 |
| 스페이스 인베이더 | 1088.9 | 826.3 | 373.2 | 302.0 |
브레이크아웃을 보면 둘 다 없을 때 3.2점, 둘 다 켜면 316.8점이다. 백 배 차이다. 두 안정화 장치가 없으면 비선형 근사 + 오프폴리시 + 부트스트랩이라는 위험한 조합이 그대로 무너지고, 두 장치를 얹는 순간 살아난다.
픽셀에서 사람 수준으로
이렇게 안정화한 DQN을 아타리 게임에 통째로 붙인 것이 1강에서 봤던 그 결과다. 입력은 게임 규칙이나 손질된 특징이 아니라 마지막 네 프레임의 원시 픽셀 더미다. 출력은 조이스틱·버튼 18가지 위치 각각의 $Q(s, a)$이고(앞서 말한 세 번째 아키텍처, 상태 하나에서 모든 행동값을 동시에), 보상은 그 스텝의 점수 변화뿐이다. 네트워크 구조와 하이퍼파라미터는 모든 게임에 똑같이 고정했다. 게임마다 손대지 않았는데도, 픽셀만 보고 여러 게임에서 사람 수준의 실력을 냈다.
표 하나 못 채우던 큰 문제를 파라미터 근사로 넘고, 그 근사가 발산하지 않도록 재생과 고정 타깃으로 붙든 것. 그것이 이 강의가 이어 붙인 다리다. 다음 강에서는 가치를 근사하는 대신 정책 자체를 직접 파라미터화하는 정책 경사로 나아간다.