§ 1모델과 계획 — 머릿속에서 경험을 만들다
환경의 모델(model)이란 에이전트가 자신의 행동에 대해 환경이 어떻게 반응할지 예측하는 데 쓸 수 있는 모든 것이다. 상태와 행동이 주어지면, 모델은 그 결과로 나타날 다음 상태와 다음 보상을 내다본다.
모델에는 두 종류가 있다. 분포 모델(distribution model)은 가능한 모든 다음 상태·보상과 그 확률을 통째로 내놓는다 — 동적 프로그래밍이 가정하는 p(s′,r|s,a)가 바로 이것이다. 샘플 모델(sample model)은 그 확률에 따라 추출된 가능성 하나만 내놓는다 — 5장 블랙잭의 모델이 그랬다. 분포 모델은 항상 샘플을 만들 수 있으니 더 강력하지만, 많은 응용에서 샘플 모델이 훨씬 얻기 쉽다. 주사위 12개의 합을 생각해 보라. 굴림을 시뮬레이션해 합을 반환하는 프로그램은 쉽지만, 가능한 모든 합과 확률을 계산하는 것은 어렵고 오류가 잦다.
계획(planning)이란 모델을 입력으로 받아 정책을 생성하거나 개선하는 모든 계산 과정이다. 이 책이 다루는 상태 공간 계획(state-space planning)은 두 가지 공통 구조를 가진다 — (1) 정책 개선의 핵심 중간 단계로 가치 함수를 계산하고, (2) 시뮬레이션된 경험에 적용된 갱신(백업) 연산으로 그 가치를 계산한다.
학습과 계획 방법 모두의 심장은 백업 갱신 연산을 통한 가치 함수의 추정이다. 차이는 단 하나 — 계획은 모델이 만든 시뮬레이션된 경험을 쓰고, 학습은 환경이 만든 실제 경험을 쓴다.
이 공통 구조 덕분에 많은 아이디어가 계획과 학습 사이를 자유로이 오간다. 특히 어떤 학습 알고리즘이든 계획 방법의 핵심 갱신 단계를 대신할 수 있다. 학습 방법은 입력으로 경험만을 요구하고, 그 경험이 실제이든 시뮬레이션이든 똑같이 작동하기 때문이다.
# 모델에 대한 최적 정책으로 수렴 — Q-학습과 동일한 조건 하에서 무한 반복: 1. 상태 S ∈ 𝒮 와 행동 A ∈ 𝒜(S) 를 무작위로 선택 2. S, A 를 샘플 모델에 보내 샘플 보상 R 과 샘플 다음 상태 S′ 를 얻음 3. S, A, R, S′ 에 1단계 표 기반 Q-학습을 적용: Q(S,A) ← Q(S,A) + α [ R + γ maxa Q(S′,a) − Q(S,A) ]
§ 2Dyna — 계획·행동·학습을 하나로
계획 에이전트 안에서 실제 경험은 두 가지 역할을 한다. 하나는 모델을 더 정확하게 다듬는 것(모델 학습), 다른 하나는 가치 함수와 정책을 곧장 개선하는 것(직접 강화학습, direct RL)이다. 모델을 통해 간접적으로 가치를 개선하는 것은 간접 강화학습이며, 이것이 곧 계획이다.
Dyna-Q는 이 모든 과정 — 계획, 행동, 모델 학습, 직접 RL — 을 하나의 구조로 통합한다. 모두 끊임없이 동시에 일어난다. Dyna-Q에서 직접 RL은 1단계 Q-학습이고, 계획은 무작위 샘플 Q-계획이며, 모델 학습은 결정적 환경을 가정해 마지막에 본 다음 상태·보상을 단순히 기록한다.
간접 방법은 제한된 경험을 더 완전히 활용해, 더 적은 환경 상호작용으로 더 나은 정책에 이른다. 직접 방법은 훨씬 단순하고 모델 설계의 편향에 영향받지 않는다. Dyna는 둘을 대립시키지 않고, 같은 가치 함수를 함께 갱신하게 함으로써 둘 다 취한다.
모든 s, a 에 대해 Q(s,a) 와 Model(s,a) 초기화 무한 반복: (a) S ← 현재 (비종료) 상태 (b) A ← ε-탐욕(S, Q) (c) 행동 A 를 취함; 결과 보상 R 과 상태 S′ 를 관찰 (d) Q(S,A) ← Q(S,A) + α [ R + γ maxa Q(S′,a) − Q(S,A) ] # 직접 RL (e) Model(S,A) ← R, S′ # 모델 학습 (결정적 가정) (f) n번 반복: # 계획 — 가상의 경험 S ← 이전에 관찰된 상태 중 무작위 A ← S 에서 이전에 취한 무작위 행동 R, S′ ← Model(S,A) Q(S,A) ← Q(S,A) + α [ R + γ maxa Q(S′,a) − Q(S,A) ]
(e)와 (f)를 지우면 남는 것은 평범한 1단계 Q-학습이다. (f)의 n이 핵심이다 — 실제 한 걸음마다 모델로 n번의 가상 갱신을 더 한다. 미로 예제에서 n=0(비계획) 에이전트는 (ε-)최적에 약 25 에피소드가 걸렸지만, n=5는 약 5 에피소드, n=50은 단 3 에피소드만에 도달했다. 아래 모션에서 이 가속을 보라.
§ 3모델이 틀렸을 때 — Dyna-Q+의 호기심
미로 예제의 모델은 운이 좋았다 — 빈 상태에서 시작해 정확한 정보로만 채워졌다. 일반적으로는 그럴 수 없다. 환경이 확률적이거나, 표본이 부족하거나, 함수 근사가 불완전하거나, 환경 자체가 변했는데 새 행동을 아직 관찰하지 못했기 때문에 모델은 부정확해진다.
모델이 낙관적으로 틀렸을 때 — 실제보다 더 큰 보상을 예측할 때 — 는 회복이 쉽다. 계획된 정책이 그 기회를 노리다가, 그것이 존재하지 않음을 발견한다(차단 미로). 어려운 것은 반대다. 환경이 더 나아졌는데 이전 정책이 그 개선을 드러내지 않을 때, 모델링 오류는 오래 — 어쩌면 영원히 — 감지되지 않는다(지름길 미로).
계획에서 탐색은 모델을 개선하는 행동을 시도하는 것, 활용은 현재 모델에 최적으로 행동하는 것이다. Dyna-Q+는 간단한 휴리스틱을 쓴다 — 각 상태-행동 쌍이 실제로 마지막에 시도된 이후 얼마나 시간이 지났는지(τ)를 추적한다. 오래된 쌍일수록 모델이 낡았을 가능성이 크다.
§ 4갱신을 어디에 둘 것인가 — 우선순위와 궤적
Dyna는 이전에 경험한 상태-행동 쌍 중에서 균일 무작위로 시뮬레이션을 시작했다. 그러나 균일 선택은 보통 최선이 아니다. 미로 두 번째 에피소드의 시작에서, 양의 가치를 가진 쌍은 목표 직전 상태뿐이다. 가치가 0인 상태에서 0인 상태로의 갱신은 아무것도 바꾸지 못한다 — 낭비다.
해법은 역방향 집중(backward focusing)이다. 가치가 변한 상태로부터 거꾸로 작업하라. 그 상태로 이어지는 행동들을 갱신하고, 그 선행 상태가 변하면 다시 그것들로 이어지는 행동을 갱신한다.
역방향으로 전파되는 갱신이 모두 똑같이 유용하진 않다. 많이 변한 상태의 선행 쌍이 많이 변할 가능성이 크다. 우선순위 스위핑(prioritized sweeping)은 갱신 시 추정 가치가 무시할 수 없을 만큼 변할 쌍들을 큐에 담고, 변화의 크기 순으로 우선순위를 매겨 처리한다. 미로 과제에서 5~10배의 속도 향상을 보였다.
모든 s, a 에 대해 Q(s,a), Model(s,a) 초기화; PQueue 를 비움 무한 반복: (a) S ← 현재 상태; (b) A ← policy(S, Q) (c) 행동 A 를 취함; R, S′ 를 관측; (d) Model(S,A) ← R, S′ (e) P ← | R + γ maxa Q(S′,a) − Q(S,A) | (f) if P > θ: S, A 를 우선순위 P 로 PQueue 에 삽입 (g) while PQueue 가 비어있지 않은 동안 n번 반복: S, A ← first(PQueue) R, S′ ← Model(S,A) Q(S,A) ← Q(S,A) + α [ R + γ maxa Q(S′,a) − Q(S,A) ] for S 로 이어질 것으로 예측되는 모든 S̄, Ā: R̄ ← S̄, Ā, S 에 대한 예측 보상 P ← | R̄ + γ maxa Q(S,a) − Q(S̄,Ā) | if P > θ: S̄, Ā 를 우선순위 P 로 PQueue 에 삽입
기대 갱신 vs 샘플 갱신
1단계 갱신은 세 가지 이진 차원으로 나뉜다 — 상태 가치 vs 행동 가치, 최적 정책 vs 주어진 정책, 그리고 기대 갱신 vs 샘플 갱신. 기대 갱신은 가능한 모든 다음 상태를 고려하니 정확하지만, 분기 인수 b배의 계산을 요구한다. 샘플 갱신은 다음 상태 하나만 본다 — 샘플링 오류가 있지만 훨씬 싸다.
적당히 큰 b에서, 샘플 갱신의 오차는 한 번의 기대 갱신에 드는 시간의 아주 작은 분량만으로 극적으로 떨어진다(√(b−1)/√(bt)의 속도로). 거대한 문제에서는 적은 쌍에 기대 갱신을 하는 것보다 많은 쌍에 샘플 갱신을 흩뿌리는 편이 훨씬 낫다.
궤적 샘플링
갱신을 어떻게 분배할까? 동적 프로그래밍의 고전적 방법은 전체 상태 공간을 철저히 스윕하지만, 큰 과제에서는 무관한 상태에까지 똑같은 시간을 낭비한다. 궤적 샘플링(trajectory sampling)은 현재 정책을 따라 모델과 상호작용하며 실제로 만나는 상태에 갱신을 집중한다 — 온-정책 분포를 따른다.
실험은 분명했다. 온-정책 집중은 초기에 더 빠른 계획을 낳고, 장기적으로는 약간 저해한다(흔한 상태는 이미 올바르므로). 그러나 상태가 많고 분기 인수가 작을수록 초기 이점은 크고 오래 지속된다. 실시간 동적 프로그래밍(RTDP)은 이 전략을 가치 반복에 적용해, 일부 문제에서는 상태의 일부만 방문하고도 관련 상태에 최적인 정책을 찾는다.
| 구분 | 철저한 스윕 (DP) | 궤적 샘플링 (온-정책) |
|---|---|---|
| 대상 상태 | 모든 상태 균등 | 현재 정책으로 도달 가능한 상태 |
| 무관한 상태 | 똑같이 갱신 — 낭비 | 건너뜀 |
| 초기 속도 | 느림 | 빠름 (시작 상태 후손에 집중) |
| 장기 (작은 문제) | 약간 우세 | 흔한 상태 반복 — 약간 손해 |
| 큰 문제 | 스윕 한 번도 못 끝낼 수 있음 | 큰 이점 |
§ 5결정 시점 계획 — 롤아웃과 몬테카를로 트리 탐색
계획은 두 가지로 쓰인다. 지금까지의 Dyna·DP는 배경 계획(background planning) — 행동이 선택되기 훨씬 전에 많은 상태의 가치를 점진적으로 개선한다. 다른 방식은 결정 시점 계획(decision-time planning) — 현재 상태 St를 만난 직후 계획을 시작·완료해, 단 하나의 행동 At를 출력하고 그 결과를 폐기한다.
인공지능의 고전적 휴리스틱 탐색(heuristic search)이 이 부류다 — 각 상태에서 가능한 연속의 큰 트리를 펼치고, 근사 가치를 리프에 적용한 뒤 루트로 역전파한다. 휴리스틱 탐색이 효과적인 이유는 더 깊은 탐색 자체가 아니라, 탐색 트리가 현재 상태 바로 다음의 상태와 행동에 갱신을 집중시키기 때문이다.
롤아웃 알고리즘(rollout algorithm)은 현재 상태에서 각 가능한 행동으로 시작해, 고정된 롤아웃 정책을 따르는 많은 시뮬레이션 궤적의 수익을 평균한다. 이는 각 행동의 qπ(s0,a) 추정이다. 가장 높은 추정의 행동을 고르는 것은 정책 개선 정리에 의해 롤아웃 정책을 개선하는 정책이다. 목표는 최적 정책이 아니라 — 주어진 롤아웃 정책의 한 걸음 개선이다.
몬테카를로 트리 탐색(MCTS)은 결정 시점 계획의 최근의, 그리고 놀랍도록 성공적인 예다. 컴퓨터 바둑을 약한 아마추어에서 그랜드마스터 수준으로 끌어올렸고, AlphaGo의 핵심이었다. 그 기반은 롤아웃 알고리즘이지만 — 시뮬레이션에서 얻은 가치 추정을 누적해, 다음 시뮬레이션을 더 높은 보상의 궤적으로 연속해서 유도한다.
MCTS는 현재 상태를 루트로 하는 트리를 점진적으로 키운다. 트리 내부에서는 탐험과 활용을 저울질하는 트리 정책(ε-탐욕, UCB 등)으로, 트리 밖에서는 단순한 롤아웃 정책으로 행동을 고른다. 각 반복은 네 단계로 이루어진다 — 아래 모션에서 보라.
while 시간이 남아있는 동안: # 매번 루트(현재 상태)에서 시작 1. 선택 (Selection) 트리 정책으로 트리를 순회해 리프 노드에 도달 2. 확장 (Expansion) (일부 반복) 미탐색 행동으로 자식 노드를 하나 이상 추가 3. 시뮬레이션 (Simulation) 롤아웃 정책으로 종료까지 한 판을 끝까지 플레이 4. 역전파 (Backup) 얻은 수익을 트리 정책이 순회한 엣지의 행동 가치로 거꾸로 전파 시간이 끝나면: 루트에서 가장 큰 행동 가치(또는 방문 횟수)의 행동을 선택
8장은 제 I 부 — 표 형식 해법 — 의 종착점이다. 우리가 본 모든 방법은 세 아이디어를 공유한다. 모두 가치 함수를 추정하고, 모두 궤적을 따라 가치를 백업하며, 모두 일반화된 정책 반복(GPI)을 따른다. 그러나 한 차원이 남았다 — 상태가 너무 많아 표가 불가능할 때의 함수 근사. 그것이 제 II 부, 9장의 문이다.