[RL] Lecture 5: Model-Free Control by David Silver

| 강의 목표

• MDP의 보상과 전이 함수를 모르더라도, 최적의 정책을 학습하는 방법을 익힌다.
• 정책 평가가 아니라, 정책 개선과 최적화(control) 에 집중한다.

---

| 목차 개요

1. On-Policy Monte Carlo Control
2. On-Policy Temporal Difference Control (Sarsa)
3. Off-Policy Learning (Q-Learning)
4. 중요 샘플링과 이론
5. 종합 요약 및 예시

---

| On-Policy Monte-Carlo Control

Generalized Policy Iteration (GPI)

• 정책 평가 → Monte-Carlo 방식으로 $Q^\pi(s, a)$ 추정
• 정책 개선 → ε-greedy 방식으로 개선

모델 없이도 가능한 정책 반복

Initialize: Q(s, a), π = ε-greedy(Q)

Repeat for each episode:
  - Generate episode using π
  - For each (s, a) in episode:
      - Q(s, a) ← average of returns
  - π ← ε-greedy(Q)

---

ε-Greedy Exploration

• $\pi(a|s) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{m} & \text{if } a = \arg\max Q(s,a) \\ \frac{\epsilon}{m} & \text{otherwise} \end{cases}$

→ 모든 행동에 확률 부여 → 무한 탐험 보장

---

GLIE 조건 (Greedy in the Limit with Infinite Exploration)

1. 모든 상태-행동 쌍이 무한히 탐험됨
2. 시간에 따라 정책은 greedy 정책으로 수렴함

→ 예시: $\epsilon_k = \frac{1}{k}$
→ 보장: $Q(s, a) \to q^*(s, a)$

---

예시: Blackjack MC Control

• 상태 공간: 합계, 딜러 카드, usable ace 여부
• 행동: Stick / Hit
• 보상: Win(+1), Lose(-1), Draw(0)

→ Monte Carlo 제어로 최적 정책과 Q 함수 수렴 가능

---

| On-Policy TD Control – Sarsa

기본 아이디어

• TD를 사용해서 Q 함수 학습
• 개선된 정책은 ε-greedy(Q)

Sarsa 알고리즘

Initialize Q(s, a)

Loop for each episode:
  S ← initial state
  A ← ε-greedy(Q)
  Loop for each step:
    Take action A, observe R, S'
    A' ← ε-greedy(Q)
    Q(S, A) ← Q(S, A) + α(R + γQ(S', A') - Q(S, A))
    S ← S', A ← A'

• 이름: S → A → R → S' → A' ⇒ SARSA

---

예시: Windy Gridworld

• 보상: time-step당 -1
• 목표 도달 시 종료
• Sarsa로 최적 정책 학습 가능 (on-policy control)

---

n-Step Sarsa & Sarsa(λ)

• $q^{(n)}_t = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{n-1} R_{t+n} + \gamma^n Q(S_{t+n})$

• λ를 적용하면:

  $q^\lambda_t = (1 - \lambda) \sum_{n=1}^\infty \lambda^{n-1} q^{(n)}_t$

• Eligibility Traces를 사용해 Backward View Sarsa(λ) 구현

---

| Off-Policy Learning – Q-Learning

핵심 개념

• 행동 정책(µ) 으로 경험을 수집하지만
• 목표 정책(π) 을 따르는 Q를 학습

→ 목표 정책은 greedy(Q)

---

Q-Learning 알고리즘

Initialize Q(s, a)

Loop for each episode:
  S ← initial state
  Loop:
    A ← ε-greedy(Q)
    Take action A, observe R, S'
    Q(S, A) ← Q(S, A) + α(R + γ * max_a' Q(S', a') - Q(S, A))
    S ← S'

• Off-policy이기 때문에
  A'는 실제 행동이 아닌 $\arg\max Q(S', a')$

---

예시: Cliff Walking

• 바닥이 절벽인 gridworld
• Sarsa는 안전 경로, Q-learning은 최단거리 선택
• Off-policy vs. on-policy의 차이 확인 가능

---

| Off-Policy Monte-Carlo & TD with Importance Sampling

Importance Sampling Ratio

• Episode: {S₁, A₁, R₂, ..., S_T}
• 목표: $\pi$, 행동: $\mu$
• Correction:

→ Gt를 $\rho$로 가중하여 업데이트

Off-policy TD는 1-step IS만 필요

→ 분산이 적고 안정적

---

정리

알고리즘	특징	정책
MC Control	에피소드 기반, 평균 Return	On-policy
Sarsa	TD 기반, 각 스텝 업데이트	On-policy
Q-Learning	TD 기반, off-policy 목표	Off-policy
Importance Sampling	policy 간 mismatch 보정	Off-policy