Ch. 10 On-policy Control with Approximation

1. Introduction

On-policy Control with Approximation 개요

• On-policy란?
  • 현재 학습 중인 정책(행동 전략)을 개선하기 위해 해당 정책 자체를 활용하는 방법입니다.
  • 즉, 현재 사용 중인 정책을 수정하여 더 나은 정책을 만드는 과정입니다.
• Control 문제:
  • 주어진 상태에서 최적의 행동을 찾아야 하는 문제입니다.
  • 이를 위해 **행동 가치 함수(Action-value function)**를 근사화해 사용합니다. q(s,a,w)≈q∗(s,a)q(s, a, w) \approx q^*(s, a)q(s,a,w)≈q∗(s,a)
    • 여기서 q(s,a,w)q(s, a, w)q(s,a,w)는 www라는 가중치를 가진 함수로, 특정 상태 sss와 행동 aaa의 가치를 예측합니다.
• 주 초점:
  • Sarsa와 같은 알고리즘을 사용해 에피소드 기반 학습 및 연속 학습 문제를 해결.

---

2. Episodic Semi-gradient Control

Semi-gradient Sarsa란?

• Sarsa는 매 순간 행동 후 받은 보상과 다음 상태를 기반으로 학습하는 알고리즘입니다.
• Semi-gradient란?
  • 값을 업데이트할 때, 근사된 함수의 일부만 사용하는 방식입니다.
  • 함수 전체를 고려하지 않으므로 계산이 단순하고 빠릅니다.
• 업데이트 공식: wt+1=wt+α(Rt+1+γq(St+1,At+1,w)−q(St,At,w))∇q(St,At,w)w_{t+1} = w_t + \alpha \big( R_{t+1} + \gamma q(S_{t+1}, A_{t+1}, w) - q(S_t, A_t, w) \big) \nabla q(S_t, A_t, w)wt+1​=wt​+α(Rt+1​+γq(St+1​,At+1​,w)−q(St​,At​,w))∇q(St​,At​,w)
  • wtw_twt​: 현재 가중치.
  • α\alphaα: 학습률.
  • Rt+1R_{t+1}Rt+1​: 다음 상태에서 받은 보상.
  • γ\gammaγ: 미래 보상을 현재로 반영하는 할인율.
  • ∇q(St,At,w)\nabla q(S_t, A_t, w)∇q(St​,At​,w): 기울기(gradient), 학습 방향을 결정.

수렴 특성

• Sarsa는 안정적으로 학습하며 최적의 정책에 수렴합니다.
• TD(0)와 비슷한 방식으로 동작하지만, 행동-가치 함수에 초점이 있습니다.

---

3. Example 10.1: Mountain Car Task

문제 정의

• 목표:
  • 약한 엔진을 가진 차가 언덕을 넘어 목표 지점에 도달해야 합니다.
  • 차가 바로 목표에 도달할 수 없으므로 언덕 아래로 굴러가 에너지를 축적한 후 올라가야 합니다.
• 학습 방법:
  • Sarsa 알고리즘을 사용해 차가 최적의 행동(예: 왼쪽/오른쪽으로 가속)을 학습합니다.
• Sarsa의 역할:
  • 상태(위치, 속도)와 행동(가속 방향)을 학습하여 최적의 경로를 찾아냅니다.

---

4. Semi-gradient nnn-step Sarsa

nnn-step Sarsa란?

• 기존 Sarsa는 "다음 상태"만 고려하지만, nnn-step Sarsa는 "여러 단계의 보상"을 한 번에 고려합니다.
• 반환값 Gt:t+nG_{t:t+n}Gt:t+n​: Gt:t+n=Rt+1+γRt+2+⋯+γn−1Rt+n+γnq(St+n,At+n,w)G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n q(S_{t+n}, A_{t+n}, w)Gt:t+n​=Rt+1​+γRt+2​+⋯+γn−1Rt+n​+γnq(St+n​,At+n​,w)
  • nnn: 학습에 고려할 단계 수.
  • 보상과 nnn단계 후 상태의 예측값을 모두 반영.

업데이트 공식

wt+n=wt+n−1+α(Gt:t+n−q(St,At,w))∇q(St,At,w)w_{t+n} = w_{t+n-1} + \alpha \big( G_{t:t+n} - q(S_t, A_t, w) \big) \nabla q(S_t, A_t, w)wt+n​=wt+n−1​+α(Gt:t+n​−q(St​,At​,w))∇q(St​,At​,w)

• Gt:t+nG_{t:t+n}Gt:t+n​: nnn-단계 보상 합.
• ∇q(St,At,w)\nabla q(S_t, A_t, w)∇q(St​,At​,w): 현재 상태에서의 기울기.

왜 필요할까?

• 더 긴 미래를 고려함으로써 장기적인 보상을 더 잘 반영.
• 짧은 단위(1-step)만 고려하는 방식보다 더 나은 정책을 학습할 가능성이 높음.

---

5. Performance Analysis of nnn-step Sarsa

부트스트래핑(bootstrapping)

• nnn-step Sarsa는 부트스트래핑 기법을 사용해 여러 단계의 보상을 계산합니다.
• 부트스트래핑 수준:
  • nnn이 작으면(예: n=1n=1n=1), 학습이 빠르고 안정적이지만, 장기적인 보상을 제대로 반영하지 못함.
  • nnn이 크면 더 많은 정보를 학습하지만, 초기에는 변동성이 커질 수 있음.

---

6. Exercise

연습 문제

1. Semi-gradient one-step Expected Sarsa의 의사 코드를 작성해 보세요.
2. nnn-step Sarsa에서 nnn이 커질수록 표준 오차가 커지는 이유를 설명하세요:
   • nnn이 클수록 초기 탐색의 변동성이 후속 학습에 큰 영향을 미침.

---

7. Average Reward Setting

평균 보상이란?

• 평균 보상은 주어진 정책이 장기적으로 얼마나 좋은지를 평가하는 기준입니다.
• 수식: rπ=lim⁡T→∞1T∑t=0T−1Rtr_\pi = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} R_trπ​=T→∞lim​T1​t=0∑T−1​Rt​
  • TTT: 전체 시간.
  • RtR_tRt​: ttt시점의 보상.

왜 필요한가?

• 에피소드 시작과 끝이 없는 연속적인 환경에서는 평균 보상이 더 적합합니다.

---

8. Deprecating the Discounted Setting

할인율 방식의 한계

• 기존 방식에서는 보상을 할인(할인율 γ\gammaγ)해 미래의 보상을 현재값으로 반영.
• 하지만, 연속적인 환경에서는 이 방식이 적합하지 않을 수 있음.

평균 보상으로 전환

• 평균 보상을 사용하면, 연속적인 환경에서 더 나은 성능을 보임.

---

9. Differential Semi-gradient nnn-step Sarsa

차이 반환값

• 반환값에서 평균 보상 Rˉ\bar{R}Rˉ을 뺀 차이를 학습에 반영: Gt:t+n=Rt+1−Rˉ+⋯+Rt+n−Rˉ+γnq(St+n,At+n,w)G_{t:t+n} = R_{t+1} - \bar{R} + \dots + R_{t+n} - \bar{R} + \gamma^n q(S_{t+n}, A_{t+n}, w)Gt:t+n​=Rt+1​−Rˉ+⋯+Rt+n​−Rˉ+γnq(St+n​,At+n​,w)
• TD 오류: δt=Gt:t+n−q(St,At,w)\delta_t = G_{t:t+n} - q(S_t, A_t, w)δt​=Gt:t+n​−q(St​,At​,w)