[2025 강화학습 Recap] Chapter 3. Model-based Prediction & Control

AI/Reinforcement Learning 2025. 8. 10. 10:50

728x90

[2025 강화학습 Recap] Chapter 3. Model-based Prediction & Control

Chapter 2에서 MDP의 수학적 구조와 벨만 방정식을 배웠지만, 한 가지 중요한 질문이 남아있음. "이론적으로는 완벽하지만, 실제로는 어떻게 풀까?"
벨만 방정식은 최적 정책과 최적 가치 함수가 만족해야 하는 조건을 명확하게 제시하지만, 이를 직접 계산하는 방법은 별도로 필요함. 마치 "x² = 4"라는 방정식이 해가 ±2라는 걸 알려주지만, 실제로 그 해를 구하는 과정은 따로 있는 것과 같음.
이 장에서는 가장 이상적인 조건에서 MDP를 푸는 방법인 동적계획법(Dynamic Programming)을 다룸. 여기서 "이상적"이라는 것은 환경의 모델(전이확률과 보상함수)을 완벽하게 알고 있다는 뜻임. 현실적이지 않아 보일 수 있지만, 이는 강화학습 알고리즘의 이론적 기준점 역할을 함.
Policy Iteration과 Value Iteration이라는 두 가지 핵심 알고리즘을 통해 벨만 방정식을 실제로 풀어볼 예정임. 이 과정에서 "평가(Evaluation)"와 "개선(Improvement)"이 번갈아 일어나는 패턴을 발견하게 될 것인데, 이는 이후 모든 강화학습 알고리즘의 기본 구조가 됨.
완벽한 조건에서의 완벽한 해법을 먼저 이해해야, 불완전한 현실에서 근사적 해법을 설계할 수 있음. Dynamic Programming은 그 출발점임.

1. Chapter 2에서 Chapter 3로: 이론에서 실제로

1.1 Chapter 2에서 우리가 얻은 것

벨만 방정식이라는 완벽한 이론적 해답:

Prediction: vπ(s) = Σ π(a|s) [R(s,a) + γ Σ P(s'|s,a) vπ(s')]
Control: v*(s) = max_a [R(s,a) + γ Σ P(s'|s,a) v*(s')]

1.2 남은 문제: "어떻게 실제로 풀 것인가?"

벨만 방정식을 만족하는 해를 어떻게 구할까?

가장 단순한 경우부터 시작하자:

✅ Model을 완벽히 안다: P(전이확률), R(보상함수) 모두 알고 있음
✅ 상태 수가 적다: 계산 가능한 크기
✅ 충분한 시간: 실시간 제약 없음

→ 이런 이상적 조건에서 벨만 방정식을 어떻게 풀까? → Dynamic Programming!

1.3 Dynamic Programming의 등장 배경

왜 DP가 MDP에 적합한가?

최적 부분구조: 최적 정책의 부분도 최적 (Principle of Optimality)
중복 부분문제: 같은 상태의 가치를 여러 번 계산
재귀적 구조: 벨만 방정식 자체가 재귀적

→ DP의 핵심 아이디어와 MDP의 구조가 완벽하게 일치!

2. Dynamic Programming 기본 개념

2.1 Dynamic Programming이란?

정의: 복잡한 문제를 더 간단한 부분 문제들로 나누어 해결하고, 그 결과를 저장하여 재사용하는 방법

핵심 원리:

분할: 큰 문제를 작은 문제들로 나눔
정복: 작은 문제들을 해결
저장: 해결한 결과를 메모리에 저장 (Memoization)
재사용: 같은 문제가 나오면 저장된 결과 사용

2.2 MDP에서 DP의 적용

MDP에서 DP가 가능한 조건:

완벽한 모델: P(s'|s,a), R(s,a) 모두 알고 있음
유한한 상태/행동 공간: 계산 가능한 크기
마르코프 성질: 미래가 현재에만 의존

DP = Planning:

Planning: 환경과 상호작용 없이 모델만으로 계산
Learning: 환경과 상호작용하면서 학습 (Chapter 4에서 다룰 예정)

2.3 벨만 방정식과 DP의 관계

벨만 방정식의 재귀적 구조:

현재 상태 가치 = 즉시 보상 + 할인된 다음 상태들의 가치

DP의 활용:

부분 문제: 각 상태의 가치 계산
재귀 관계: 벨만 방정식
저장: Value Function Table
반복: 수렴할 때까지 업데이트

3. DP의 두 가지 문제: Prediction vs Control

3.1 문제 분류

Chapter 2에서 정의한 두 가지 문제를 DP로 해결:

Prediction (Policy Evaluation)

문제: "주어진 정책 π의 가치는 얼마인가?"

입력: 정책 π, MDP model
출력: vπ(s) for all s
방법: Iterative Policy Evaluation

Control (Policy Optimization)

문제: "최적 정책과 최적 가치는 무엇인가?"

입력: MDP model
출력: π*(s), v*(s) for all s
방법: Policy Iteration, Value Iteration

3.2 왜 Prediction부터?

더 간단함: 정책이 주어져 있어서 최적화 불필요
Control의 구성요소: Control 과정에서 Prediction이 필요
단계적 학습: 쉬운 것부터 차근차근

4. Prediction: Iterative Policy Evaluation

4.1 목표

주어진 정책 π에 대해 vπ(s)를 모든 상태 s에서 구하기

4.2 핵심 아이디어

벨만 방정식을 반복적으로 적용하여 수렴시키기

벨만 방정식 (복습): vπ(s) = Σ π(a|s) [R(s,a) + γ Σ P(s'|s,a) vπ(s')]

4.3 Iterative Policy Evaluation 알고리즘

1. 모든 상태의 가치를 임의로 초기화: v0(s) for all s
2. k번째 반복에서:
   vk+1(s) = Σ π(a|s) [R(s,a) + γ Σ P(s'|s,a) vk(s')]
3. 수렴할 때까지 반복: |vk+1(s) - vk(s)| < θ for all s

4.4 알고리즘의 특징

수렴성: γ < 1이면 항상 참값 vπ(s)로 수렴 보장

업데이트 방식:

Synchronous: 모든 상태를 동시에 업데이트
Asynchronous: 상태를 하나씩 순차적으로 업데이트

계산 복잡도: O(|S|²|A|) per iteration

4.5 실제 예시: GridWorld

3x3 격자, 목표: 오른쪽 하단 도달
정책: 각 상태에서 4방향으로 균등하게 이동 (π(a|s) = 0.25)

초기값: v0(s) = 0 for all s
1회 반복 후: 목표 근처 상태들의 가치가 증가
여러 반복 후: 목표에서 멀수록 낮은 가치로 수렴

4.6 Policy Evaluation의 의미

결과 해석:

높은 가치: 이 상태에서 시작하면 정책 π를 따라 좋은 결과
낮은 가치: 이 상태에서는 정책 π가 별로
가치 gradient: 어느 방향이 더 유리한지 보여줌

5. Control: 최적 정책 찾기

5.1 Control 문제의 접근법

기본 아이디어: Prediction과 Policy Improvement를 번갈아 수행

Generalized Policy Iteration (GPI):

π0 → E → π1 → E → π2 → E → ... → π*

E: Evaluation (가치 계산)
→: Policy Improvement (정책 개선)

5.2 Policy Improvement 원리

현재 정책 π에서 더 나은 정책 π'를 만들기

Greedy Policy: π'(s) = argmax_a qπ(s,a)

Policy Improvement Theorem: 만약 qπ(s,π'(s)) ≥ vπ(s) for all s라면, vπ'(s) ≥ vπ(s) for all s

직관: "각 상태에서 가장 좋은 행동만 선택하면 전체적으로 더 좋아진다"

6. Policy Iteration

6.1 알고리즘 구조

1. 임의의 정책 π0로 초기화
2. 반복:
   a) Policy Evaluation: vπ를 정확히 계산
   b) Policy Improvement: π'(s) = argmax_a Σ P(s'|s,a)[R(s,a) + γvπ(s')]
   c) π ← π'
3. 정책이 변하지 않을 때까지 반복

6.2 Policy Iteration의 특징

수렴성: 유한 MDP에서 항상 최적 정책으로 수렴

단조성: 정책이 단조적으로 개선됨 (vπk+1 ≥ vπk)

유한성: 정책 수가 유한하므로 유한 시간에 수렴

계산량: 각 iteration에서 Policy Evaluation이 비쌈

6.3 Policy Iteration의 과정 예시

초기 정책: 모든 상태에서 랜덤 행동
1차 반복: 이 정책의 가치 계산 → 각 상태에서 최선 행동 선택
2차 반복: 개선된 정책의 가치 계산 → 또 다시 개선
...
수렴: 더 이상 개선할 수 없는 최적 정책 도달

6.4 Policy Evaluation의 정확도

완전한 평가 vs 부분 평가:

완전: 수렴할 때까지 Policy Evaluation
부분: 몇 번만 반복하고 Policy Improvement

Modified Policy Iteration: Policy Evaluation을 일정 횟수만 수행

더 빠르지만 수렴 보장이 약해질 수 있음
극단적 경우: 1번만 → Value Iteration

7. Value Iteration

7.1 기본 아이디어

"Policy Evaluation을 한 번만 하고 바로 개선하면?"

핵심 통찰: 벨만 최적성 방정식을 직접 반복 적용 vk+1(s) = max_a [R(s,a) + γ Σ P(s'|s,a) vk(s')]

7.2 Value Iteration 알고리즘

1. 모든 상태의 가치를 임의로 초기화: v0(s)
2. k번째 반복에서:
   vk+1(s) = max_a [R(s,a) + γ Σ P(s'|s,a) vk(s')]
3. 수렴할 때까지 반복
4. 최적 정책 추출: π*(s) = argmax_a [R(s,a) + γ Σ P(s'|s,a) v*(s')]

7.3 Value Iteration의 특징

수렴성: γ < 1이면 v*로 수렴 보장

효율성: Policy Iteration보다 각 iteration이 빠름

구조: Evaluation과 Improvement가 동시에 일어남

정책 추출: 마지막에 최적 정책을 greedy하게 추출

7.4 Principle of Optimality

벨만의 최적성 원리: "최적 정책의 어떤 부분도 그 자체로 최적이어야 한다"

MDP에서의 적용:

최적 정책 π가 상태 s에서 행동 a를 선택했다면
a* 이후의 정책도 해당 부분 문제에서 최적이어야 함

Value Iteration의 정당성: 이 원리가 Value Iteration의 수렴을 보장

8. Policy Iteration vs Value Iteration

8.1 비교표

특성Policy IterationValue Iteration각 iteration오래 걸림빠름iteration 수적음많음전체 시간비슷비슷메모리정책 + 가치 저장가치만 저장중간 정책의미 있음의미 없음구현복잡단순

8.2 언제 무엇을 사용할까?

Policy Iteration 선호:

좋은 초기 정책이 있을 때
중간 정책도 활용하고 싶을 때
행동 공간이 클 때

Value Iteration 선호:

구현 단순성을 원할 때
메모리 제약이 있을 때
최종 정책만 필요할 때

8.3 시간 복잡도 분석

State Value Function 사용 시:

Policy Iteration: O(|S|²|A|) per evaluation + O(|S||A|) per improvement
Value Iteration: O(|S|²|A|) per iteration

Action Value Function 사용 시:

더 높은 복잡도: O(|S||A|²)
하지만 정책 추출이 더 간단: π(s) = argmax_a Q(s,a)

9. 실제 구현 고려사항

9.1 수렴 판정

Value Function 기준:

max_s |vk+1(s) - vk(s)| < θ

Policy 기준 (Policy Iteration):

πk+1(s) = πk(s) for all s

9.2 초기화 전략

Value Function:

v0(s) = 0 (일반적)
도메인 지식 활용한 좋은 초기값

Policy:

균등 정책 (uniform random)
휴리스틱 기반 정책

9.3 업데이트 순서

Synchronous: 모든 상태 동시 업데이트 Asynchronous: 상태별 순차 업데이트

In-place 업데이트로 메모리 절약
수렴 속도 개선 가능

9.4 실제 적용 시 한계

상태 공간 폭발: 상태 수가 기하급수적 증가 Model 요구사항: 완벽한 P, R 필요 계산 복잡도: 큰 문제에는 비현실적

10. DP의 확장과 응용

10.1 Asynchronous DP

In-place Value Iteration: 같은 배열에서 즉시 업데이트 Prioritized Sweeping: 변화가 큰 상태 우선 업데이트 Real-time DP: 현재 상태 주변만 업데이트

10.2 Approximate DP

Function Approximation: 가치 함수를 함수로 근사 State Aggregation: 비슷한 상태들을 묶어서 처리 Linear Programming: DP를 선형계획법으로 변환

10.3 Partial Observable MDP

Belief State: 확률 분포로 상태 표현 Point-based DP: 대표적인 belief state들만 계산

11. Chapter 3 정리 및 다음 단계

11.1 DP가 해결한 것

✅ 완벽한 모델에서 최적 해법: 벨만 방정식을 실제로 풀 수 있음 ✅ 이론의 구현: MDP 이론을 실제 알고리즘으로 변환 ✅ 두 가지 접근법: Policy Iteration과 Value Iteration

11.2 DP의 한계

❌ 완벽한 모델 필요: 실제로는 P, R을 모르는 경우가 많음 ❌ 계산 복잡도: 상태 수가 많으면 불가능 ❌ 실시간 제약: 계획 단계에서만 사용 가능

11.3 다음 단계: Model-free RL (Chapter 4)

해결하고 싶은 문제들:

"모델을 모를 때는 어떻게 하지?" → Monte Carlo, TD Learning
"실시간으로 학습하려면?" → Online Learning
"상태가 너무 많으면?" → Function Approximation

DP에서 배운 핵심 아이디어들:

GPI (Generalized Policy Iteration): Evaluation ↔ Improvement 반복
Bootstrapping: 추정값으로 추정값 업데이트
Bellman Backup: 벨만 방정식 기반 업데이트

→ 이들이 Model-free RL의 핵심 구성요소가 됨!

11.4 핵심 메시지

Dynamic Programming은 강화학습의 이론적 토대:

MDP 이론을 실제 알고리즘으로 구현하는 방법
완벽한 조건에서의 최적 해법
실제 RL 알고리즘들의 원형과 영감의 원천

"이상적 조건에서 완벽한 해법을 알았으니, 이제 현실적 제약에서 근사적 해법을 찾아보자!"

Dynamic Programming은 강화학습 여행의 첫 번째 목적지였음. 완벽한 지도(환경 모델)를 가지고 최적의 경로(정책)를 찾는 방법을 배웠음. Policy Iteration과 Value Iteration을 통해 벨만 방정식이 단순한 이론이 아니라 실제로 풀 수 있는 문제라는 것을 확인했음.

하지만 현실은 그리 호락호락하지 않음. 대부분의 실제 문제에서는 환경의 완벽한 모델을 알 수 없고, 상태 공간은 계산하기 어려울 만큼 크며, 실시간으로 학습해야 하는 경우가 많음. DP는 이런 현실적 제약들 앞에서 한계를 드러냄.

그럼에도 불구하고 DP에서 배운 핵심 아이디어들은 앞으로의 여정에서 계속 등장할 예정임. 평가와 개선을 반복하는 Generalized Policy Iteration의 구조, 추정값으로 추정값을 업데이트하는 Bootstrapping, 벨만 방정식을 기반으로 한 업데이트 방식 등은 모든 강화학습 알고리즘의 DNA가 됨.

다음 장에서는 모델 없이도 학습할 수 있는 Model-free 방법들을 살펴볼 예정임. 완벽한 지도 없이 시행착오를 통해 길을 찾아가는 방법들 말임. DP가 제시한 이론적 기준점을 바탕으로, 이제 현실적인 해법들을 하나씩 탐험해보자.

완벽한 조건에서의 완벽한 해법을 알았으니, 이제 불완전한 세상에서 통하는 실용적인 방법들을 찾아갈 차례임.