[2025 강화학습 Recap] Chapter 5. Model-Free Control

 

[2025 강화학습 Recap] Chapter 5. Model-Free Control

 

Chapter 4에서 주어진 정책의 가치를 추정하는 방법을 배웠지만, 여전히 핵심 질문이 남아있음. "이제 가치를 구할 수 있으니, 어떻게 더 나은 정책을 찾을까?"

지금까지는 "이 정책을 따르면 얼마나 좋을까?"라는 평가 문제만 해결했음. 하지만 강화학습의 진짜 목표는 "어떤 정책이 가장 좋을까?"를 찾는 것임. 환경의 모델도 모르는 상황에서 어떻게 최적 정책을 학습할 수 있을까?

답은 Chapter 3에서 배운 Generalized Policy Iteration 구조에 있음. 평가(Evaluation)와 개선(Improvement)을 반복하되, 이제 모든 것을 실제 경험으로 대체하는 것임. 하지만 여기에는 새로운 도전이 기다리고 있음. 모델 없이 어떻게 정책을 개선할까? 탐험과 활용의 딜레마는 어떻게 해결할까?

이 장에서는 Monte Carlo부터 시작해서 SARSA, Q-Learning까지 차례로 살펴보며 Model-free Control의 완전한 그림을 그려볼 예정임. 특히 On-policy와 Off-policy라는 두 가지 근본적으로 다른 접근법의 차이점과 각각의 장단점을 명확히 이해하게 될 것임.

드디어 환경과 직접 상호작용하면서 스스로 최적 정책을 찾아가는 진짜 강화학습의 세계로 들어가보자.

 

 

1. Chapter 4에서 Chapter 5로: Prediction에서 Control로

1.1 Chapter 4에서 달성한 것

Model-Free Prediction 문제 해결: ✅ 환경 모델 없이도 정책의 가치 추정 가능 ✅ Monte Carlo: 전체 에피소드로 실제 Return 사용 ✅ Temporal Difference: 한 스텝 + 추정값으로 즉시 업데이트

 

1.2 남은 문제: Control

현재 상황: "주어진 정책의 가치는 구할 수 있다" 다음 단계: "어떻게 더 나은 정책을 찾을까?"

Control 문제의 핵심:

• Prediction: vπ(s) 또는 qπ(s,a) 구하기 ✅
• Control: 최적 정책 π* 찾기 ❓

 

1.3 Chatper 3. DP에서 배운 GPI (Generalized Policy Iteration)

기본 아이디어: Evaluation ↔ Improvement 반복

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

 

Model-Free에서의 도전:

• Evaluation: MC/TD로 해결 가능 ✅
• Improvement: 모델 없이 어떻게? ❓

 

 

2. Model-Free Control의 기본 원리와 접근법들

2.1 Control 문제 정의

목표: 환경 모델 없이 최적 정책 π* 찾기

주어진 것: 환경과의 상호작용만 가능 찾아야 할 것: 최적 정책 π*(s) = argmax_a Q*(s,a)

 

2.2 왜 Model-Free Control이 어려운가?

DP에서 Policy Improvement:

π'(s) = argmax_a Σ P(s'|s,a)[R(s,a) + γv(s')]
                  ↑ 모델 필요!

 

Model-Free에서는:

• P(s'|s,a): 전이확률 모름
• R(s,a): 보상함수 모름
• 직접 경험만 사용 가능

→ 어떻게 정책을 개선할 것인가?

 

2.3 두 가지 가능한 접근법

Chapter 4에서 배운 두 방법을 Control에 적용:

접근법 1: Monte Carlo 기반

• 장점: 개념적으로 단순, 정확한 추정
• 단점: 에피소드 완료까지 대기 필요
• 적용: Monte Carlo Control

접근법 2: Temporal Difference 기반

• 장점: 실시간 학습, 빠른 업데이트
• 단점: 추정값 사용으로 편향 가능
• 적용: SARSA, Q-Learning

 

2.4 왜 Monte Carlo부터 시작하는가?

교육적 순서:

1. 개념적 단순함: MC는 실제 Return을 사용해서 이해하기 쉬움
2. DP와의 연결: Policy Iteration 구조를 그대로 활용
3. 점진적 발전: MC의 한계를 통해 TD 방법의 필요성 부각

실제 발전 과정:

DP Policy Iteration → MC Policy Iteration → MC Control → SARSA → Q-Learning

 

 

3. Monte Carlo Control

3.1 DP Policy Iteration에서 MC Policy Iteration으로

DP Policy Iteration 구조 (복습): (Chapter 3에서 배웠던 Model-Based Control 해결 방법)

1. Policy Evaluation: 벨만 방정식으로 vπ(s) 계산
2. Policy Improvement: π'(s) = argmax_a Σ P(s'|s,a)[R(s,a) + γvπ(s')]
3. 수렴할 때까지 반복

 

MC Policy Iteration 아이디어: "DP와 같은 구조를 사용하되, 벨만 방정식 대신 MC로 가치 추정하자!"

1. Policy Evaluation: MC로 qπ(s,a) 추정 ← 모델 불필요!
2. Policy Improvement: π'(s) = argmax_a qπ(s,a) ← 모델 불필요!
3. 수렴할 때까지 반복

 

핵심 통찰: Action-Value Function Q(s,a)를 사용하면 모델 없이도 정책 개선 가능!

 

3.2 MC Control이 사용하는 벨만 방정식

중요한 구분: MC Control은 어떤 벨만 방정식을 사용하는가?

Bellman Expectation Equation 사용:

qπ(s,a) = E[R + γ Σ π(a'|s') qπ(s',a')]
          ↑ 현재 정책 π에 대한 가치

 

왜 Bellman Optimality가 아닌가?

• MC Control은 Policy Iteration 구조를 따름
• 현재 정책의 가치를 정확히 추정한 후 개선
• Bellman Optimality는 나중에 Q-Learning에서 사용

 

3.3 Monte Carlo Policy Iteration의 3가지 문제점

문제 1: Value Function 선택

State Value vs Action Value:

State Value Function 사용 시 문제:

π'(s) = argmax_a Σ P(s'|s,a)[R(s,a) + γv(s')]
                  ↑ 모델 필요!

 

해결책: Action Value Function 사용:

π'(s) = argmax_a q(s,a)  ← 모델 불필요!

 

Action Value의 장점:

• 모델 없이도 정책 개선 가능
• 행동 간 직접 비교 가능
• Model-Free Control의 핵심

문제 2: Exploration 부족

Pure Greedy Policy의 문제:

π(s) = argmax_a Q(s,a)  ← 항상 최선만 선택

 

문제점:

• 탐험 부족으로 local optimum에 빠질 위험
• 미경험 상태-행동 쌍을 학습하지 못함
• 초기 추정이 잘못되면 개선 어려움

해결책: ε-Greedy Policy:

π(a|s) = {
  1-ε+ε/|A|  if a = argmax Q(s,a)  (탐욕적 행동)
  ε/|A|      otherwise              (탐험적 행동)
}

 

ε-Greedy의 특징:

• ε 확률로 랜덤 행동 (exploration)
• 1-ε 확률로 최선 행동 (exploitation)
• 모든 행동에 양수 확률 보장

문제 3: Policy Evaluation의 비효율성

완전한 Policy Evaluation 문제:

• 수렴할 때까지 기다리면 너무 오래 걸림
• 실제로는 완전한 수렴 불필요

해결책: 제한된 Evaluation:

• 한 에피소드만 실행하고 바로 개선
• Value Iteration과 유사한 아이디어

 

3.3 Monte Carlo Control 알고리즘

최종 알고리즘:

1. 임의의 ε-greedy 정책으로 초기화
2. 반복:
   a) 현재 정책으로 에피소드 실행
   b) 모든 (s,a) 쌍에 대해 Q(s,a) 업데이트
   c) 각 상태에서 ε-greedy로 정책 개선

 

 

3.4 GLIE (Greedy in the Limit with Infinite Exploration)

정의: 무한한 탐험 후 탐욕적 정책으로 수렴

GLIE 조건:

1. 모든 상태-행동 쌍이 무한히 탐험됨
2. 정책이 탐욕적 정책으로 수렴

ε-Greedy with Decaying ε:

ε_t = 1/t  (또는 다른 감소 함수)

 

왜 GLIE가 중요한가?:

• 초기에는 충분한 탐험 보장
• 나중에는 최적 정책으로 수렴
• 이론적 수렴 보장의 기반

 

4. Temporal Difference Control: SARSA

4.1 SARSA의 등장 배경

Monte Carlo Control의 한계:

• 에피소드가 끝날 때까지 기다려야 함
• 긴 에피소드나 연속 태스크에 부적합

SARSA의 아이디어: "TD(0)를 Action Value Function에 적용하면?"

 

4.2 SARSA가 사용하는 벨만 방정식

Bellman Expectation Equation의 TD 버전:

qπ(s,a) = E[R + γqπ(s',a')] where a' ~ π(·|s')

 

SARSA 업데이트:

Q(St,At) ← Q(St,At) + α[Rt+1 + γQ(St+1,At+1) - Q(St,At)]
                                     ↑ 실제 정책이 선택한 행동

 

핵심: 현재 정책이 실제로 선택할 다음 행동 At+1을 사용 이름의 유래: State-Action-Reward-State-Action

업데이트 규칙:

Q(St,At) ← Q(St,At) + α[Rt+1 + γQ(St+1,At+1) - Q(St,At)]

 

구성요소:

• TD Target: Rt+1 + γQ(St+1,At+1)
• TD Error: Rt+1 + γQ(St+1,At+1) - Q(St,At)

 

4.3 SARSA의 특징

On-Policy 학습:

• 학습하는 정책 = 행동하는 정책
• 실제 따르는 정책의 가치를 학습

알고리즘 구조:

1. 상태 S에서 정책에 따라 행동 A 선택
2. 행동 A 실행, 보상 R과 다음 상태 S' 관찰  
3. S'에서 정책에 따라 다음 행동 A' 선택
4. Q(S,A) 업데이트: Q(S,A) ← Q(S,A) + α[R + γQ(S',A') - Q(S,A)]
5. S ← S', A ← A'로 이동

 

4.4 SARSA vs Monte Carlo

특성Monte CarloSARSA학습 속도에피소드 후매 스텝적용 범위Episodic만모든 태스크Bias/VarianceUnbiased/High VarBiased/Low Var수렴성보장조건부

 

 

 

5. Off-Policy Learning

5.1 On-Policy vs Off-Policy

On-Policy Learning

정의: 학습하는 정책 = 행동하는 정책 예시: SARSA 특징:

• 실제 따르는 정책의 성능 학습
• 안전하고 안정적
• 탐험과 활용의 딜레마

Off-Policy Learning

정의: 학습하는 정책 ≠ 행동하는 정책 예시: Q-Learning 특징:

• 한 정책으로 행동하며 다른 정책 학습
• 과거 경험 재활용 가능
• 더 효율적인 학습 가능

 

5.2 Off-Policy의 장점

1. 탐험과 학습 분리:

• Behavior Policy: 탐험 중심 (ε-greedy)
• Target Policy: 최적화 중심 (greedy)

2. 데이터 재활용:

• 다른 에이전트의 경험 활용
• 과거 정책의 데이터 재사용

3. 안전한 학습:

• 보수적으로 행동하며 공격적으로 학습

 

5.3 Importance Sampling

핵심 아이디어: 한 분포의 샘플로 다른 분포의 기댓값 추정

수학적 원리:

E_p[X] = E_q[X · p(X)/q(X)]

 

강화학습 적용:

E_π[Return] = E_μ[Return · π(trajectory)/μ(trajectory)]

 

 

5.4 Off-Policy Monte Carlo

기본 아이디어:

• Behavior Policy μ로 데이터 수집
• Target Policy π에 대한 가치 학습

Importance Sampling Ratio:

ρ = ∏(π(At|St)/μ(At|St))  (전체 궤적에 대해)

 

업데이트:

V(s) ← V(s) + α[ρ·Gt - V(s)]

 

문제점:

• μ(a|s) = 0이면 사용 불가
• High variance (여러 확률의 곱)

 

5.5 Off-Policy TD Learning

개선점: 한 스텝만 Importance Sampling

ρ = π(At|St)/μ(At|St)  (한 스텝만)

 

업데이트:

V(s) ← V(s) + αρ[Rt+1 + γV(St+1) - V(St)]

 

여전한 문제: Importance Sampling으로 인한 variance

 

 

6. Q-Learning: Off-Policy TD Control

6.1 Q-Learning의 핵심 아이디어

문제 해결: "Importance Sampling 없이 Off-Policy 가능한가?"

해답: Action Value Function + 다른 정책으로 다음 행동 선택

 

6.2 Q-Learning이 사용하는 벨만 방정식

Bellman Optimality Equation의 TD 버전:

q*(s,a) = E[R + γ max_a' q*(s',a')]
                 ↑ 최적 행동 선택

 

Q-Learning 업데이트:

Q(St,At) ← Q(St,At) + α[Rt+1 + γ max_a Q(St+1,a) - Q(St,At)]
                                     ↑ 최선 행동의 가치

 

핵심 차이점:

• SARSA (Bellman Expectation): 실제 선택한 행동 사용
• Q-Learning (Bellman Optimality): 최선 행동 사용

 

6.3 이것이 Off-Policy인 이유

Two Different Policies:

1. Behavior Policy (행동 선택): ε-greedy로 실제 행동
2. Target Policy (가치 학습): greedy로 최적 가치 학습

수식으로 보는 차이:

행동 선택: At ~ ε-greedy(Q(St,·))     ← Behavior Policy
가치 업데이트: max_a Q(St+1,a)        ← Target Policy (greedy)

 

업데이트 규칙:

Q(St,At) ← Q(St,At) + α[Rt+1 + γ max_a Q(St+1,a) - Q(St,At)]

 

핵심 차이점:

• SARSA: Rt+1 + γQ(St+1,At+1) ← 실제 선택한 행동
• Q-Learning: Rt+1 + γ max_a Q(St+1,a) ← 최선 행동

 

6.3 Q-Learning의 구조

Two-Policy 구조:

• Behavior Policy: ε-greedy w.r.t. Q(s,a) (탐험용)
• Target Policy: greedy w.r.t. Q(s,a) (학습용)

알고리즘 흐름:

1. 상태 S에서 ε-greedy로 행동 A 선택 (behavior policy)
2. 행동 A 실행, 보상 R과 다음 상태 S' 관찰
3. Q(S,A) 업데이트: Q(S,A) ← Q(S,A) + α[R + γ max_a Q(S',a) - Q(S,A)]
   (target policy로 다음 행동 가치 계산)
4. S ← S'로 이동

 

 

6.4 Chapter 2의 구분과 실제 Model-Free의 차이

Chapter 2에서 배운 명확한 구분:

Prediction 문제 → Bellman Expectation Equation
Control 문제 → Bellman Optimality Equation

 

하지만 Model-Free에서는 더 복잡함:

Control 문제를 푸는 두 가지 방식

방식 1: Policy Iteration 스타일 (MC Control, SARSA)

1. Bellman Expectation으로 현재 정책 평가 (Prediction)
2. 정책 개선 (Policy Improvement)  
3. 반복 → 결과적으로 Control 해결

 

방식 2: Value Iteration 스타일 (Q-Learning)

Bellman Optimality로 최적 가치 직접 학습 → Control 해결

 

왜 이런 차이가 생기는가?

이론 (Chapter 2):

• 명확한 구분 가능 (완벽한 모델 있음)
• Control = Bellman Optimality 직접 적용

실제 (Model-Free):

• 환경과 상호작용하며 점진적 학습
• 안전한 방법: 현재 정책 평가 후 개선 (MC, SARSA)
• 직접적 방법: 최적 가치 바로 추정 (Q-Learning)

핵심 통찰

Control 문제 = 두 가지 해법:

1. 간접적: Prediction(평가) + Improvement(개선) 반복
2. 직접적: Bellman Optimality로 최적 가치 직접 학습

Model-Free에서는 둘 다 유용함:

• MC/SARSA: 안정적이지만 느림
• Q-Learning: 빠르지만 복잡함

6.5 벨만 방정식 관점에서 보는 전체 그림

방법사용하는 벨만 방정식Control 해결 방식정책 타입MC ControlBellman Expectation평가 + 개선 반복On-PolicySARSABellman Expectation평가 + 개선 반복On-PolicyQ-LearningBellman Optimality최적 가치 직접 학습Off-Policy

 

Chapter 2 vs Model-Free 비교:

• Chapter 2: Control = Bellman Optimality (이론적)
• Model-Free: Control = 두 가지 방식 (실용적)
  • 간접적: Bellman Expectation + Policy Improvement
  • 직접적: Bellman Optimality

 

6.5 Q-Learning의 장점

1. Importance Sampling 불필요:

• 확률비 계산 없음
• Variance 문제 해결

2. 최적 정책 직접 학습:

• Target policy가 항상 greedy
• 수렴 시 최적 Q* 함수 획득

3. 데이터 효율성:

• 모든 경험을 최적 정책 학습에 활용
• Off-policy의 모든 장점 보유

 

6.5 SARSA vs Q-Learning: Cliff Walking 예제

환경 설정: 절벽이 있는 격자 세계

SARSA (On-Policy):

• 실제 ε-greedy 정책의 가치 학습
• 절벽 근처에서 조심스러운 경로 학습
• 안전한 길로 우회

Q-Learning (Off-Policy):

• 최적 greedy 정책의 가치 학습
• 절벽 바로 옆의 최단 경로 학습
• 위험하지만 최적인 경로

실제 성능:

• SARSA: 안전하지만 느린 경로
• Q-Learning: 위험하지만 빠른 경로

 

7. n-step Methods와 Eligibility Traces

7.1 TD와 MC의 중간 지점

문제 인식:

• TD(0): 빠르지만 높은 bias
• MC: 정확하지만 높은 variance

해결 아이디어: "n-step만큼 실제 경험 후 추정"

 

7.2 n-step TD Prediction

n-step Return:

G(n)t = Rt+1 + γRt+2 + ... + γ^(n-1)Rt+n + γ^n V(St+n)

 

업데이트:

V(St) ← V(St) + α[G(n)t - V(St)]

 

특성:

• n=1: TD(0)
• n=∞: Monte Carlo
• n 증가 시: bias 감소, variance 증가

 

7.3 λ-Return: Forward View

문제: "어떤 n이 최적인가?"

해결책: 모든 n-step return의 가중평균

G^λ_t = (1-λ) Σ λ^(n-1) G(n)t

 

특성:

• λ=0: TD(0)
• λ=1: Monte Carlo
• Geometric weighting으로 모든 n 조합

 

7.4 n-step SARSA

n-step Action Value:

G(n)t = Rt+1 + γRt+2 + ... + γ^(n-1)Rt+n + γ^n Q(St+n,At+n)

 

SARSA(λ):

G^λ_t = (1-λ) Σ λ^(n-1) G(n)t

 

 

 

8. 실제 구현 고려사항

8.1 학습률 설정

SARSA:

• 수렴 조건: Σα=∞, Σα²<∞
• 실제: α=0.01~0.1 고정

Q-Learning:

• 더 안정적인 수렴
• 상대적으로 큰 학습률 사용 가능

8.2 탐험 전략

ε-Greedy 변형들:

• Decaying ε: ε_t = ε_0/t
• Boltzmann: 확률적 선택 with temperature
• UCB: 불확실성 기반 탐험

8.3 함수 근사

큰 상태 공간 문제:

• Q-table → Q-function 근사
• 선형 함수, 신경망 등 활용
• Deep Q-Learning의 기초

 

 

9. Chapter 5 정리 및 다음 단계

9.1 Model-Free Control이 해결한 것

✅ 환경 모델 없이 최적 정책 학습: Action Value Function 활용 ✅ 탐험과 활용 균형: ε-greedy, GLIE 등 ✅ 온라인 학습: SARSA로 실시간 개선 ✅ 데이터 효율성: Q-Learning으로 off-policy 학습

9.2 주요 알고리즘 비교

알고리즘정책학습 방식특징MC ControlOn-Policy에피소드 단위안정적, 느림SARSAOn-Policy매 스텝실제 정책 학습Q-LearningOff-Policy매 스텝최적 정책 학습

 

9.3 남은 도전과제

❌ 함수 근사: 큰 상태 공간 처리 방법 ❌ 수렴 보장: 함수 근사 시 안정성 ❌ 샘플 효율성: 더 적은 경험으로 빠른 학습 ❌ 연속 행동 공간: 무한한 행동 처리

 

9.4 다음 단계: Function Approximation (Chapter 6)

해결하고 싶은 문제들:

• "상태가 백만 개면 어떻게 하지?" → 함수 근사
• "연속 상태/행동 공간은?" → 매개변수화된 정책
• "딥러닝과 결합하면?" → Deep Reinforcement Learning

 

9.5 핵심 메시지

Model-Free Control은 실용적 강화학습의 핵심:

• 환경 모델 없이도 최적 정책 학습 가능
• Action Value Function이 핵심 도구
• On-Policy vs Off-Policy의 trade-off 이해
• 탐험과 활용의 균형이 성공의 열쇠

"이제 tabular 방법은 완성했다. 실제 복잡한 문제를 위해 함수 근사로 확장해보자!"

 

 

이 장에서 우리는 강화학습의 가장 중요한 단계를 완료했음. 환경의 모델을 전혀 모르는 상황에서도 실제 경험만으로 최적 정책을 학습할 수 있다는 것을 보여줬음. Monte Carlo Control의 직관적 접근법부터 SARSA의 안정적인 온라인 학습, Q-Learning의 효율적인 오프폴리시 학습까지, 각각이 서로 다른 상황에서 빛을 발하는 도구들임.

특히 Action-Value Function Q(s,a)가 Model-free Control의 핵심이라는 점을 기억해야 함. 이것이 있어야 모델 없이도 정책을 개선할 수 있고, 탐험과 활용의 균형을 맞출 수 있음. SARSA와 Q-Learning의 차이도 명확함. 안전하고 실제적인 성능을 원하면 SARSA를, 최적성과 데이터 효율성을 원하면 Q-Learning을 선택하면 됨.

하지만 지금까지 다룬 방법들은 모두 테이블 기반이었음. 상태와 행동이 유한하고 적은 경우에만 적용 가능함. 현실의 복잡한 문제들은 어떨까? 자율주행차의 무수한 센서 데이터, 바둑의 천문학적인 상태 공간, 로봇의 연속적인 관절 제어... 이런 문제들을 해결하려면 새로운 도구가 필요함.

다음 장에서는 함수 근사(Function Approximation)를 통해 이런 현실적 제약을 뛰어넘는 방법을 알아볼 예정임. 선형 함수부터 시작해서 신경망까지, 강화학습이 어떻게 복잡한 실세계 문제에 적용되는지 보게 될 것임. 지금까지 배운 모든 알고리즘들이 함수 근사와 결합되면서 진짜 실용적인 도구로 거듭나게 됨.

Tabular 강화학습의 여정이 끝났음. 이제 무한한 가능성의 세계로 확장해보자.