이제 MDP를 모른다. 전이도 보상도 모른 채, 환경과 상호작용해 얻은 경험만으로 주어진 정책의 가치를 추정한다. 두 큰 갈래가 몬테카를로와 시간차 학습이다.

강의 슬라이드: PDF

몬테카를로 (MC)

에피소드가 끝날 때까지 기다렸다가, 실제로 받은 리턴 $G_t$로 가치를 끌어당긴다.

$$V(S_t) \leftarrow V(S_t) + \alpha\,(G_t - V(S_t))$$

완결된 에피소드가 필요하다(끝이 있어야 한다). 한 에피소드에서 같은 상태를 여러 번 밟을 수 있는데, 그 상태의 첫 방문만 세면 최초 방문 MC, 밟을 때마다 다 세면 모든 방문 MC다. 둘 다 방문이 쌓이면 참 가치로 수렴한다.

원래 MC는 리턴의 단순 평균이다. 이걸 매번 다시 계산하는 대신 갱신식으로 바꾸면, $1/N$ 자리에 상수 $\alpha$를 두는 순간 의미가 살짝 달라진다. $1/N$은 모든 과거 에피소드를 똑같이 반영하는 진짜 평균이고, 상수 $\alpha$는 옛 에피소드를 지수적으로 잊는다. 환경이 조금씩 변하는(비정상) 문제에서는 잊는 편이 낫다.

실버의 예는 블랙잭이다. 딜러 규칙도 확률도 모른 채, 수많은 판을 실제로 쳐 보고 각 상황(내 카드 합, 딜러가 보인 카드, 쓸 수 있는 에이스 유무)의 가치를 이기고 진 결과의 평균으로 매긴다. 모델 없이 경험만으로 가치 지도가 채워진다.

시간차 학습 (TD)

끝까지 기다리지 않고 한 걸음만 내다본 뒤, 추정치로 추정치를 갱신한다(부트스트래핑). TD(0)은 이렇다.

$$V(S_t) \leftarrow V(S_t) + \alpha\,\big(R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\big)$$

괄호 안이 TD 오차다. 에피소드가 끝나지 않아도 매 걸음 온라인으로 배운다.

실버의 예는 퇴근길이다. 집까지 걸리는 시간을 예측하며 운전하는데, 차에 타서 30분을 예상했다가 비를 만나면 그 자리에서 40분으로 고친다. 도착해서야(에피소드 끝) 예측을 고치는 게 MC라면, TD는 매 순간 새 정보로 예측을 바로바로 손본다. 끝을 안 봐도 배우는 것이 TD의 힘이다.

MC와 TD, 무엇을 언제

  • MC: 실제 리턴, 무편향, 고분산, 종료가 필요, 초기값에 둔감.
  • TD: 부트스트랩, 편향, 저분산, 온라인, 초기값에 민감하고 마르코프성을 활용.

편향과 분산의 차이가 어디서 오는지 보면 직관이 선다. 리턴 $G_t$ 하나에는 에피소드 끝까지의 모든 무작위 행동·전이·보상이 들어 있다. 그래서 무편향이지만 크게 출렁인다(고분산). TD 타깃 $R + \gamma V(S')$에는 딱 한 걸음의 무작위성만 들어 있다. 대신 아직 틀린 추정치 $V(S')$에 기대므로 편향이 생기지만, 훨씬 덜 흔들린다(저분산).

둘이 무엇으로 수렴하는지도 다르다. 실버의 유명한 A, B 예가 이걸 드러낸다. 여덟 번의 짧은 경험만 주고 배치로 학습시키면, MC는 관측된 리턴의 평균만 맞추려 해서 A의 가치를 0으로 본다(A가 나온 유일한 에피소드의 리턴이 0이었으니까). TD는 “A 다음에 B가 오고 B는 대개 보상을 준다"는 구조를 이어 붙여 A의 가치를 B를 거쳐 0.75로 본다. MC는 겪은 것의 평균(최소제곱)을, TD는 겪은 것으로 세운 MDP의 답(확실성 등가)을 찾는다. 그래서 마르코프 구조가 있으면 TD가 유리하고, 없으면 MC가 더 안전하다.

무작위 걸음. 중앙에서 출발해 좌우로 무작위로 걷고, 오른쪽 끝에 닿으면 보상 +1이다. 참값은 A부터 E까지 1/6, 2/6, …, 5/6(점선). 에피소드를 눌러 가며 MC와 TD(0)의 추정(실선)이 참값으로 다가가는 속도를 비교해 보자. 대개 TD가 더 빨리 붙는다.

통합 뷰: 부트스트랩과 샘플링

DP, MC, TD를 한 좌표에 놓으면 지도가 그려진다. 두 축이다. 첫째는 부트스트랩 여부, 즉 다음 상태의 추정치를 목표에 쓰는가. 둘째는 샘플링 여부, 즉 다음 상태들을 확률로 전부 훑는가(전폭), 아니면 실제 겪은 하나만 쓰는가(표본).

  • 동적 계획법: 부트스트랩 O, 전폭(샘플링 X). 모델을 알고 얕게 훑는다.
  • 몬테카를로: 부트스트랩 X, 표본 O. 모델 없이 끝까지 깊게 간다.
  • 시간차 학습: 부트스트랩 O, 표본 O. 모델 없이 얕게 훑는다.

강화학습의 거의 모든 방법이 이 두 축 어딘가에 놓인다. 이 강의는 그 지도의 세 귀퉁이를 세운 셈이다.

n-스텝과 TD(λ)

한 걸음(TD)과 끝까지(MC)는 양극단일 뿐이다. n걸음을 내다보는 n-스텝 리턴이 그 사이를 잇는다. 그리고 모든 n의 리턴을 한꺼번에 섞은 것이 λ-리턴인데, n-스텝 리턴에 $(1-\lambda)\lambda^{n-1}$의 가중치를 준다. 최근 스텝일수록 크고 뒤로 갈수록 기하급수적으로 작아지는 이 형태 덕에, 무한한 합을 효율적으로 재귀 계산할 수 있다. $\lambda=0$이면 첫 항만 남아 TD(0), $\lambda=1$이면 MC에 가깝다.

TD(λ)에는 두 얼굴이 있다. 앞을 보는 전방 뷰는 위의 λ-리턴을 목표로 쓴다. 직관은 명료하지만 미래를 다 봐야 해서 에피소드가 끝나야 계산된다. 뒤를 보는 후방 뷰는 적격 흔적으로 같은 일을 온라인으로 해낸다.

적격 흔적은 신용 할당 문제를 푼다. 종이 세 번 울리고 불빛이 한 번 켜진 뒤 전기충격이 왔다면, 무엇이 충격을 불렀나. 자주 일어난 신호(빈도)와 방금 일어난 신호(최근성)를 둘 다 의심하는 게 합리적이다. 적격 흔적은 그 둘을 곱해 각 상태에 남긴다.

$$E_t(s) = \gamma\lambda\, E_{t-1}(s) + \mathbf{1}(S_t = s)$$

상태를 밟으면 흔적이 1 솟고, 이후 매 걸음 $\gamma\lambda$배로 스러진다. 그리고 매 걸음의 TD 오차가 이 흔적에 비례해 과거 상태들로 번진다. 놀랍게도 전방 뷰와 후방 뷰는 오프라인에서 정확히 같은 갱신을 준다.

지금까지는 정책을 평가만 했다(예측). 다음 강에서는 이 도구로 최적 정책을 찾는 제어로 나아간다.