§ 1MC와 TD 사이의 공간
이 장은 앞의 두 장 — 몬테카를로(MC) 방법과 1-단계 시간차(TD) 방법 — 을 하나로 통합한다. MC도 1-단계 TD도 항상 최선은 아니다. n-단계 TD 방법은 두 방법을 일반화하여, 한쪽 끝에 MC를, 다른 쪽 끝에 1-단계 TD를 둔 스펙트럼을 형성한다. 최선의 방법은 대개 두 극단 사이의 어딘가에 있다.
n-단계 방법을 바라보는 또 다른 관점은, 그것이 우리를 시간 단계의 폭압(tyranny of the time step)에서 해방시킨다는 것이다. 1-단계 TD에서는 같은 시간 단계가 두 가지를 동시에 정한다 — 행동을 얼마나 자주 바꿀 수 있는가, 그리고 부트스트래핑이 이뤄지는 시간 간격은 얼마인가. 많은 응용에서 우리는 변화를 빠르게 반영하려고 행동을 매우 빠르게 갱신하고 싶지만, 부트스트래핑은 의미 있고 인식 가능한 상태 변화가 일어나는 시간 길이에 걸쳐 수행될 때 가장 효과적이다. 1-단계 TD에서는 이 두 간격이 같으니 타협해야 한다. n-단계 방법은 여러 단계에 걸쳐 부트스트랩하게 하여 그 폭압을 푼다.
n-단계 아이디어는 보통 적격도 흔적(eligibility traces, 12장)이라는 개념을 소개하는 도구로 쓰인다. 적격도 흔적은 여러 시간 간격에 걸쳐 동시에 부트스트래핑을 가능하게 한다. 그러나 여기서는 n-단계 부트스트래핑을 독립적으로 다루고, 흔적 메커니즘은 뒤로 미룬다 — 문제를 더 잘 분리하여, 가능한 한 많은 부분을 더 단순한 n-단계 설정에서 다루기 위함이다.
π로 생성한 샘플 에피소드에서 vπ를 추정한다 하자. 몬테카를로는 각 상태에 대해 그 상태부터 에피소드 끝까지의 전체 보상 시퀀스를 기반으로 갱신한다. 1-단계 TD는 단 하나의 다음 보상만 기반으로, 한 단계 후 상태의 가치를 나머지 보상들의 대리로 삼아 부트스트랩한다.
그렇다면 중간 방법은 — 중간 개수의 보상을 기반으로 갱신한다. 하나보다는 많지만 종료까지 전부보다는 적은 개수. 2-단계 갱신은 처음 두 보상과 두 단계 후 상태의 추정 가치를, 3-단계는 셋을, … n-단계는 n개를 본다.
§ 2n-단계 TD 예측
몬테카를로 갱신의 목표는 완전한 반환값 Gt = Rt+1 + γRt+2 + ⋯ + γT−t−1RT이다. 1-단계 갱신의 목표는 첫 보상에 다음 상태의 할인된 추정 가치를 더한 1-단계 반환값 Gt:t+1 = Rt+1 + γVt(St+1)이다. 핵심 통찰은 — 이 발상이 한 단계 후만큼이나 n단계 후에도 똑같이 타당하다는 것이다.
모든 n-단계 반환값은 전체 반환값의 근사다 — n단계 후에 잘리고, 누락된 항들은 Vt+n−1(St+n)으로 보정된다. n > 1인 반환값은 시간 t에서는 사용할 수 없는 미래 보상·상태를 포함한다. Rt+n을 보고 Vt+n−1을 계산하기 전까지는 쓸 수 없으니, 처음 사용 가능한 시점은 t+n이다. 따라서 자연스러운 갱신은 다음과 같다 — Vt+n(St) = Vt+n−1(St) + α[Gt:t+n − Vt+n−1(St)]. 이를 n-단계 TD라 부른다. 각 에피소드의 처음 n−1 단계 동안은 아무 갱신도 없고, 이를 보상하기 위해 에피소드가 끝난 뒤 같은 수의 추가 갱신이 이뤄진다.
아래 모션은 이 스펙트럼을 보여준다 — n이 1(TD)에서 ∞(MC)로 커질수록 n-단계 백업이 얼마나 멀리 내다보는지.
# 입력: 정책 π · 매개변수: 스텝 크기 α, 양의 정수 n 모든 s 에 대해 V(s) 임의 초기화 각 에피소드에 대해 반복: S0 초기화·저장 (S0 ≠ 종료), T ← ∞ for t = 0, 1, 2, ...: if t < T: π(·|S_t)에 따라 행동, R_{t+1}·S_{t+1} 관찰·저장 if St+1 가 종료: T ← t+1 τ ← t − n + 1 # 갱신될 상태의 시간 if τ ≥ 0: G ← Σi=τ+1min(τ+n,T) γi−τ−1 Ri if τ+n < T: G ← G + γn V(Sτ+n) # G_{τ:τ+n} V(Sτ) ← V(Sτ) + α[ G − V(Sτ) ] until τ = T − 1
5-상태 무작위 걷기에서 첫 에피소드가 C→D→E를 거쳐 오른쪽에서 +1로 끝났다 하자. 모든 가치는 0.5에서 시작. 1-단계 방법은 마지막 상태 V(E)만 1을 향해 올린다. 2-단계 방법은 V(D)와 V(E) 둘 다 올린다. 3-단계 이상은 방문한 세 상태 모두를 같은 양만큼 올린다.
어느 n이 더 나은가? 19-상태 무작위 걷기에 대한 경험적 테스트에서 — 중간 n값을 가진 방법들이 가장 잘 작동했다. TD와 MC를 n-단계로 일반화하면 두 극단 어느 쪽보다도 잠재적으로 나은 성능을 낼 수 있다.
§ 3n-단계 Sarsa — 제어로 확장
n-단계 방법을 제어에도 쓰려면? 주요 아이디어는 단순하다 — 상태를 행동(상태-행동 쌍)으로 바꾸고 ε-탐욕 정책을 쓴다. Sarsa의 n-단계 버전을 n-단계 Sarsa라 하며, 앞 장의 원래 버전은 이제 1-단계 Sarsa 또는 Sarsa(0)다. 추정 행동 가치의 관점에서 n-단계 반환값을 다시 정의한다.
Qt+n(St,At) = Qt+n−1(St,At) + α[ Gt:t+n − Qt+n−1(St,At) ]
n-단계 Sarsa가 1-단계보다 학습을 왜 가속하는지는 그리드월드 예시(그림 7.4)에 선명하다. 에이전트가 한 에피소드에서 높은 보상 위치 G에 도달하는 경로를 걸었다 하자. 모든 가치는 처음 0이었고 G의 보상만 양수다. 1-단계 방법은 G로 이어진 행동 시퀀스의 마지막 행동 하나만 강화한다. n-단계 방법은 시퀀스의 마지막 n개 행동을 강화한다 — 한 에피소드에서 훨씬 더 많이 배운다. 아래 모션이 이 차이를 보여준다.
§ 4n-단계 오프-정책 학습
오프-정책 학습은 한 정책 b를 따르면서 다른 정책 π의 가치 함수를 배우는 것이다. b의 데이터를 쓰려면 두 정책의 차이를 — 취해진 행동들의 상대 확률, 즉 5장의 중요도 샘플링을 — 고려해야 한다. n-단계 방법에서는 반환값이 n단계에 걸쳐 구성되니, 바로 그 n개 행동의 상대 확률에 관심을 둔다.
n-단계 Sarsa의 오프-정책 형태도 마찬가지로 비율로 가중한다 — 다만 중요도 샘플링 비율이 한 단계 늦게 시작하고 끝난다(ρt+1:t+n). 우리가 상태-행동 쌍을 갱신하고 있으니, 첫 행동은 이미 선택했고 그것을 선택할 가능성을 따질 필요가 없다 — 후속 행동에 대해서만 보정하여, 일어난 일로부터 온전히 배운다.
§ 5트리 백업과 통합 알고리즘 Q(σ)
중요도 샘플링 없이 오프-정책 학습이 가능할까? 6장의 Q-러닝과 기대 Sarsa는 1-단계 경우에 그렇게 한다. 그 다단계 대응물이 n-단계 트리 백업(tree-backup) 알고리즘이다.
트리 백업의 아이디어는 백업 다이어그램을 약간 확장한 데서 온다. 중앙 축을 따라 샘플 상태·보상·행동이 늘어서고, 각 상태의 측면에는 선택되지 않은 행동들이 매달려 있다. 선택되지 않은 행동에 대한 샘플 데이터는 없으니, 그들의 가치 추정치를 부트스트랩하여 목표에 포함시킨다 — 갱신이 추정된 행동 가치들의 전체 트리로부터 이뤄지기에 트리 백업이라 부른다.
리프 노드는 목표 정책 π 하에서 발생할 확률에 비례하는 가중치로 목표에 기여한다. 1단계 행동 a는 π(a|St+1)로, 선택 안 된 2단계 행동 a′는 π(At+1|St+1)π(a′|St+2)로 — 마치 행동 노드로 향하는 각 화살표가 그 행동의 선택 확률로 가중되는 것과 같다. 트리 백업은 확률적 목표 정책을 가진 Q-러닝의 자연스러운 다단계 확장이다.
이제 우리는 세 종류의 행동-가치 알고리즘을 가졌다. n-단계 Sarsa — 모든 전이가 샘플. 트리 백업 — 모든 상태-행동 전이가 샘플링 없이 완전히 분기. n-단계 기대 Sarsa — 마지막을 제외한 전부가 샘플이고 마지막만 기댓값으로 분기. 이들을 어디까지 통합할 수 있을까?
통합의 아이디어는 — 단계별로 결정한다. Sarsa처럼 행동을 샘플로 취할지, 아니면 트리 백업처럼 모든 행동의 기댓값을 고려할지. 항상 샘플링하면 Sarsa, 전혀 안 하면 트리 백업, 마지막만 빼고 샘플링하면 기대 Sarsa가 된다.
가능성을 더 넓혀, 샘플링과 기댓값 사이의 연속적 변화를 둔다. σt ∈ [0,1]을 단계 t에서의 샘플링 정도라 하자 — σ=1은 완전한 샘플링, σ=0은 순수한 기댓값. 이 새 알고리즘이 n-단계 Q(σ)이며, 앞의 모든 것을 특수 경우로 품는다.