Model Free Control

Control - 환경을 모를 때 최적의 정책을 찾는 것

 

- 저번 강의에선 MDP를 모를 때 value를 찾는 prediction 문제에 대해 다룸
- 이번 강의에선 MDP를 모를 때 최적의 정책을 찾는 것을 다룸(최적의 가치 = 최적의 정책)

 

- On-policy는 내가 최적화하고자 하는 정책과 환경에서 경험을 쌓는 정책이 같은 것
- Off-policy는 다른 에이전트가 행동한 경험들을 통해 배우는 정책 방법

 

 

• 정책 평가 (Policy Evaluation):
  • 현재 정책 π\piπ에 대해 상태가치 함수 VπV^\piVπ를 추정합니다.
  • 예: 반복 정책 평가 (Iterative Policy Evaluation)
• 정책 개선 (Policy Improvement):
  • 현재 정책 π\piπ를 사용하여 새로운 정책 π′\pi'π′를 생성합니다. 여기서 π′≥π\pi' \geq \piπ′≥π입니다.
  • 예: 탐욕적 정책 개선 (Greedy Policy Improvement)

 

 

- 몬테 카를로도 evaluation으로 가능한가?

• 정책 평가:
  • 몬테카를로 정책 평가를 사용하여 V=vπ  추정
• 정책 개선:
  • 탐욕적 정책 개선 방법을 사용하여 새로운 정책을 생성합니다.

위 방법으로 하면 최적의 정책을 찾는 것 아닌가? - 안된다.
- 내 다음 State를 알아야 Greedy(다음 상태중에 가장 VALUE가 높은 쪽으로 가는 것)하게 가능한데, 현재 MDP를 모르는 상태다. 불가능!

- MC를 이용해 Q를 찾아내고, Greedy policy improvement를 사용하면 되겠네? No!

- Greedy하게 움직이면 충분히 많은 곳으로 갈 수 없다. 아래 사진을 보면 문제점 예시이다.

 

- 처음 연 왼쪽문 +점수만 가지고는, 오른쪽이 무조건 좋다고 할 수 없는데, greedy하게 가면 무조건 오른쪽만 연다.
- 그래서 나온게 입실론-Greedy

 

- Exploration(탐험)을 보장, 여러곳을 갈 수 있다.
- 입실론의 확률로 랜덤하게 무작위로 행동한다. 예를들어 입실론이 0.05면, 0.95확률로 가장 좋은 곳을 찾아가고, 0.05 확률로 랜덤하게 간다.

- 입실론-greedy 사용하면 가능하다.

- 한 에피소드만 MC방법 쓰고, 바로 입실론-greedy 사용.
- 더 빨리 greedy 해서 유용하다. 잘 수렴하기 위해선 몇가지 성질이 필요하다. (GLIE)

- 모든 State, Action 들이 무한히 반복되어야 exploration을 충분히 할 수 있다.
- 결국에는 policy가 입실론-greedy policy가 greedy policy로 수렴해야 한다. (0.05확률로 바보같은 행동을 하는데 최적이냐?에 대한 물음)

- 위 조건들을 만족하면 GLID Monte-Carlo Control이다.

- MC말고, TD Control도 가능하다. S에서 A행동을 해서 R보상을 받고 S'상태에서 다시 A'액션을 하는 것. Sarsa 라고 함

 

- TD기 때문에 한 에피소드가 아닌, 한 스텝마다 Q가 업데이트가 된다! 극단적이다. Sarsa 알고리즘이다.

- Q 테이블(state와 action에 관한)을 만든다.
- A 행동중에 하나를 뽑는다. 액션에 대한 리워드와 다음 state(S')를 관측, S'에서 랜덤한 행동 A'를 또 골라서  Q를 업데이트 한다.
- 위 사항 반복하면 Sarsa 알고리즘이다. 

- 다음 두 조건이 만족하면 Sarsa 알고리즘은 optimal action-value function이다.
- GLIE(모든 State, Action에 접근해야되고, 입실론이 줄어들어서 결국 greedy policy에 수렴해야한다)
- 알파가 1~무한까지 더하면 무한이 되어야 한다. 스텝사이즈가 충분히 커야한다. 알파제곱의 합이 무한보다 작다. q밸류를 수정하는게 결국 수렴한다는 것. 실제 사용할때는 이 두 조건은 별로 신경쓰지 않아도 policy를 잘 찾는다.

- Sarsa도 TD처럼 가능하다. n-Step, 람다, Backward 등

1. TD 학습 (TD Learning)

• 기본 아이디어: TD 학습은 현재 상태에서 다음 상태로 이동할 때의 차이를 사용하여 가치 함수나 정책을 업데이트합니다. TD(0)라고도 합니다.
• 업데이트 공식: Q(st,at)←Q(st,at)+α(rt+1+γQ(st+1,at+1)−Q(st,at))Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left( r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \right)Q(st​,at​)←Q(st​,at​)+α(rt+1​+γQ(st+1​,at+1​)−Q(st​,at​))
• 장점: 샘플 효율적이며, 미래의 예측을 반영하여 업데이트합니다.
• 단점: 단일 스텝만을 고려하므로 학습이 느릴 수 있습니다.

2. N-step SARSA

• 기본 아이디어: N-step SARSA는 단일 스텝 대신 N개의 스텝을 사용하여 더 긴 기간 동안의 보상을 고려하여 업데이트합니다.
• 업데이트 공식: Q(st,at)←Q(st,at)+α(∑k=0N−1γkrt+k+1+γNQ(st+N,at+N)−Q(st,at))Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left( \sum_{k=0}^{N-1} \gamma^k r_{t+k+1} + \gamma^N Q(s_{t+N}, a_{t+N}) - Q(s_t, a_t) \right)Q(st​,at​)←Q(st​,at​)+α(k=0∑N−1​γkrt+k+1​+γNQ(st+N​,at+N​)−Q(st​,at​))
• 장점: 더 많은 정보를 사용하므로, 업데이트가 더 정확할 수 있습니다.
• 단점: 적절한 N값을 선택하는 것이 어렵고, 계산량이 증가할 수 있습니다.

3. λ(람다) Forward SARSA (SARSA(λ))

• 기본 아이디어: SARSA(λ)는 TD(0)와 Monte Carlo 방법 사이의 균형을 맞추기 위해 시간차의 가중 평균을 사용합니다. λ는 가중치 감소율을 나타냅니다.
• 업데이트 공식: Q(st,at)←Q(st,at)+α(Gt(λ)−Q(st,at))Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left( G_t^{(\lambda)} - Q(s_t, a_t) \right)Q(st​,at​)←Q(st​,at​)+α(Gt(λ)​−Q(st​,at​)) 여기서 Gt(λ)G_t^{(\lambda)}Gt(λ)​는 λ-반복 수렴 (λ-return)입니다.
• 장점: 다른 시간 차원에서의 정보를 결합하여 더 안정적인 학습을 가능하게 합니다.
• 단점: λ값을 적절히 선택하는 것이 중요하며, 계산 복잡도가 증가할 수 있습니다.

4. Backward SARSA

• 기본 아이디어: Backward SARSA는 자가 예측을 통한 추정 방법으로, 후방에서의 TD 에러를 사용하여 업데이트합니다. 흔히 엘리젤릭 트레이스를 사용합니다.
• 업데이트 공식: e(st,at)=λγe(st−1,at−1)+1e(s_t, a_t) = \lambda \gamma e(s_{t-1}, a_{t-1}) + 1e(st​,at​)=λγe(st−1​,at−1​)+1 Q(st,at)←Q(st,at)+αδte(st,at)Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \delta_t e(s_t, a_t)Q(st​,at​)←Q(st​,at​)+αδt​e(st​,at​) 여기서 e(st,at)e(s_t, a_t)e(st​,at​)는 엘리젤릭 트레이스이며, δt\delta_tδt​는 TD 에러입니다.
• 장점: 효율적인 메모리 사용과 빠른 수렴 속도를 가질 수 있습니다.
• 단점: 복잡한 추적 관리와 적절한 λ값 설정이 필요합니다.

비교 요약

• TD 학습: 단일 스텝 기반의 간단한 업데이트, 느린 학습 속도.
• N-step SARSA: 여러 스텝을 반영하여 보다 정확한 업데이트, 계산 복잡도 증가.
• SARSA(λ): 다양한 시간 차원 정보를 가중 평균, 안정적이나 λ 설정이 중요.
• Backward SARSA: 후방 추적과 TD 에러 사용, 메모리 효율적이나 복잡도 증가.

이 방법들은 각기 다른 상황과 요구에 맞춰 사용될 수 있으며, 보상 신호와 학습 환경에 따라 적절한 방법을 선택하는 것이 중요합니다.

더 설명하자면,

λ(람다) Forward SARSA

λ(람다) Forward SARSA는 현재 시점에서 앞으로 여러 스텝 동안의 반환값(Return)을 고려하여 가중치를 줍니다. 이는 여러 스텝의 보상과 추정값을 조합하여 가치 함수를 업데이트합니다.

• 기본 개념:
  • λ(람다)는 미래의 보상에 대한 가중치 감소율을 나타냅니다.
  • 현재 시점에서 여러 스텝에 걸쳐 얻은 보상들을 가중 평균하여 사용합니다.
• 업데이트 방식:
  • 각 스텝마다 미래의 여러 스텝에서 얻을 보상들을 가중치 λ를 적용하여 결합한 값을 사용하여 가치 함수를 업데이트합니다.
  • Gt(λ)G_t^{(\lambda)}Gt(λ)​는 λ-반복 반환값(λ-return)으로, 이는 현재부터 앞으로의 여러 스텝에 걸친 보상들의 가중 합입니다.
  • 업데이트 공식: Q(st,at)←Q(st,at)+α(Gt(λ)−Q(st,at))Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left( G_t^{(\lambda)} - Q(s_t, a_t) \right)Q(st​,at​)←Q(st​,at​)+α(Gt(λ)​−Q(st​,at​))
  • 여기서 Gt(λ)G_t^{(\lambda)}Gt(λ)​는 다음과 같이 정의됩니다: Gt(λ)=(1−λ)∑n=1∞λn−1Gt(n)G_t^{(\lambda)} = (1 - \lambda) \sum_{n=1}^\infty \lambda^{n-1} G_t^{(n)}Gt(λ)​=(1−λ)n=1∑∞​λn−1Gt(n)​ Gt(n)=∑k=0n−1γkrt+k+1+γnQ(st+n,at+n)G_t^{(n)} = \sum_{k=0}^{n-1} \gamma^k r_{t+k+1} + \gamma^n Q(s_{t+n}, a_{t+n})Gt(n)​=k=0∑n−1​γkrt+k+1​+γnQ(st+n​,at+n​)
  • 이는 각 스텝마다 미래의 여러 스텝에서 얻을 보상들을 고려하여 가중치를 적용한 값을 업데이트에 반영하는 방식입니다.

Backward SARSA (with Eligibility Traces)

Backward SARSA는 과거의 경험을 반영하는 방식으로, 후방에서부터 가중치를 적용하여 업데이트합니다. 이 방법은 엘리젤릭 트레이스(eligibility trace)를 사용하여 과거의 상태-행동 쌍에 대한 가중치를 점진적으로 감소시키며 반영합니다.

• 기본 개념:
  • 엘리젤릭 트레이스는 특정 상태-행동 쌍에 대한 책임의 정도를 나타내는 값입니다.
  • 현재 시점의 TD 에러를 과거의 상태-행동 쌍에 누적하여 반영합니다.
• 업데이트 방식:
  • 각 시점에서의 TD 에러 δt\delta_tδt​를 계산하고, 이를 엘리젤릭 트레이스를 사용하여 과거의 상태-행동 쌍에 반영합니다.
  • 엘리젤릭 트레이스는 다음과 같이 업데이트됩니다: e(st,at)=γλe(st−1,at−1)+1e(s_t, a_t) = \gamma \lambda e(s_{t-1}, a_{t-1}) + 1e(st​,at​)=γλe(st−1​,at−1​)+1
  • Q 값 업데이트 공식은 다음과 같습니다: Q(s,a)←Q(s,a)+αδte(s,a)Q(s, a) \leftarrow Q(s, a) + \alpha \delta_t e(s, a)Q(s,a)←Q(s,a)+αδt​e(s,a)
  • 이는 현재의 TD 에러를 과거의 여러 상태-행동 쌍에 반영하여 업데이트하는 방식입니다.

요약

• λ(람다) Forward SARSA: 현재 시점에서 미래의 여러 스텝 동안의 반환값에 가중치를 주어 가치 함수를 업데이트합니다.
• Backward SARSA: 과거의 경험을 반영하여 현재의 TD 에러를 후방에서부터 가중치를 적용하여 가치 함수를 업데이트합니다.

 

 

- 다른 에이전트나 사람을 보고 배움
- 기존에 했었던 것이 있으면 사용하기 좋다.
- 탐험적인 행동을 하면서 안전하게 optimal policy를 배울 수 있다.
- 여러 정책들을 학습 가능

Off-Policy Learning - Important Sampling, Q-Learning 

- 식을 알아야 한다. f(X)의 기댓값을 P를 이용해 구하고 싶다. P 주사위를 굴려서 Q의 기댓값을 구하고 싶은 경우, 정규 확률 P(X)와, 약간 확률이 다른 Q(X)로 구할 수 있다. 

예시 설명

예를 들어, 우리가 어떤 주식의 일일 수익률을 분석한다고 가정해봅시다. 두 가지 분포가 있습니다:

• P(X)P(X)P(X): 주식 시장의 실제 분포
• Q(X)Q(X)Q(X): 우리가 샘플을 얻을 수 있는 분포 (예: 모의 거래 데이터)

우리는 실제 주식 시장 분포 PPP에서의 기대 수익률 EX∼P[f(X)]\mathbb{E}_{X \sim P}[f(X)]EX∼P​[f(X)]을 알고 싶지만, 실제 데이터가 부족합니다. 대신 모의 거래 데이터 QQQ에서 샘플을 얻어 이를 추정할 수 있습니다.

단계별 설명

1. 실제 기대값 정의:
   • EX∼P[f(X)]=∑P(X)f(X)\mathbb{E}_{X \sim P}[f(X)] = \sum P(X) f(X)EX∼P​[f(X)]=∑P(X)f(X)
   • 이는 실제 분포 PPP에서 함수 f(X)f(X)f(X)의 기대값입니다.
2. 다른 분포 QQQ로 변환:
   • P(X)f(X)P(X) f(X)P(X)f(X)를 Q(X)Q(X)Q(X)를 이용해 다시 작성: ∑P(X)f(X)=∑Q(X)P(X)Q(X)f(X)\sum P(X) f(X) = \sum Q(X) \frac{P(X)}{Q(X)} f(X)∑P(X)f(X)=∑Q(X)Q(X)P(X)​f(X)
   • 여기서 P(X)Q(X)\frac{P(X)}{Q(X)}Q(X)P(X)​는 중요도 가중치입니다. 이는 분포 QQQ에서 샘플링된 데이터를 분포 PPP에서 샘플링된 데이터로 조정하는 역할을 합니다.
3. 기대값의 형태로 재작성:
   • EX∼P[f(X)]=EX∼Q[P(X)Q(X)f(X)]\mathbb{E}_{X \sim P}[f(X)] = \mathbb{E}_{X \sim Q} \left[ \frac{P(X)}{Q(X)} f(X) \right]EX∼P​[f(X)]=EX∼Q​[Q(X)P(X)​f(X)]
   • 이는 분포 QQQ에서 샘플링한 데이터로부터 분포 PPP에서의 기대값을 추정할 수 있음을 의미합니다.

실제 예시 적용

• 우리가 실제로 모의 거래 데이터 QQQ에서 100개의 샘플을 얻었다고 가정해봅시다.
• 각 샘플 XiX_iXi​에 대해 f(Xi)f(X_i)f(Xi​)는 해당 샘플에서의 일일 수익률입니다.
• 우리는 P(Xi)Q(Xi)\frac{P(X_i)}{Q(X_i)}Q(Xi​)P(Xi​)​를 계산하여 각 샘플의 중요도 가중치를 구합니다.
• 각 샘플에 대해 중요도 가중치를 곱한 수익률을 평균 내어 실제 기대 수익률을 추정합니다.

이를 통해 우리는 실제 데이터를 직접 얻지 않더라도, 모의 거래 데이터에서 실제 분포의 기대값을 추정할 수 있습니다. 중요한 점은 각 샘플의 중요도 가중치를 정확히 계산하여 분포의 차이를 보정하는 것입니다.

 

- 몬테카를로 Off-Policy, 각 샘플들의 값들을 곱하면, 직접적인 에피소드들은 아니지만, 결국 value를 찾을 수 있다는 것. 현실적으로 불가능하다. 왜냐하면 해당 변수가 너무 커서 동작을 할 수가 없다. 그래서 TD를 쓴다.

- TD를 사용하거나, Q-Learning으로 변수값을 크게 줄일 수 있다.

1. 오프-정책 학습 (Off-Policy Learning):
   • 정의: 학습 중에 취하는 행동(행동 정책 μ\muμ)과 최적의 행동을 취하기 위한 정책(목표 정책 π\piπ)이 다를 때, 이를 오프-정책 학습이라고 합니다.
   • Q-러닝은 대표적인 오프-정책 학습 방법입니다.
2. 중요도 샘플링이 필요하지 않음:
   • Q-러닝은 중요도 샘플링을 사용하지 않습니다. 즉, 행동 정책 μ\muμ와 목표 정책 π\piπ의 비율을 계산하여 조정할 필요가 없습니다.
   • 이는 Q-러닝이 목표 정책 π\piπ의 가치 추정을 직접 업데이트하기 때문입니다.
3. 행동 정책 (μ\muμ)를 사용하여 다음 행동 선택:
   • 학습 중에 에이전트는 행동 정책 μ\muμ에 따라 행동 At+1A_{t+1}At+1​를 선택합니다. 이 행동 정책은 에이전트가 환경에서 실제로 수행하는 행동을 정의합니다. 
4. 대안 후속 행동 (A′A'A′) 고려:
   • 하지만 Q-러닝은 목표 정책 π\piπ에 따라 대안 행동 A′A'A′를 고려하여 업데이트를 수행합니다.
   • 즉, 다음 상태 St+1S_{t+1}St+1​에서 목표 정책 π\piπ가 선택할 행동 A′A'A′를 사용합니다. 
5. Q-값 업데이트:
   • 현재 상태-행동 쌍 (St,At)(S_t, A_t)(St​,At​)에 대한 Q-값은 다음과 같이 업데이트됩니다: Q(St,At)←Q(St,At)+α(Rt+1+γQ(St+1,A′)−Q(St,At))Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left( R_{t+1} + \gamma Q(S_{t+1}, A') - Q(S_t, A_t) \right)Q(St​,At​)←Q(St​,At​)+α(Rt+1​+γQ(St+1​,A′)−Q(St​,At​))
   • 여기서:
     • Q(St,At)Q(S_t, A_t)Q(St​,At​): 현재 상태-행동 쌍의 Q-값.
     • α\alphaα: 학습률.
     • Rt+1R_{t+1}Rt+1​: 현재 상태 StS_tSt​에서 행동 AtA_tAt​를 수행한 후 받는 보상.
     • γ\gammaγ: 할인율.
     • Q(St+1,A′)Q(S_{t+1}, A')Q(St+1​,A′): 다음 상태 St+1S_{t+1}St+1​에서 목표 정책 π\piπ가 선택할 행동 A′A'A′에 대한 Q-값.

요약

Q-러닝은 오프-정책 학습 방법으로, 중요도 샘플링을 사용하지 않고 행동 정책 μ\muμ를 통해 다음 행동을 선택하지만, 목표 정책 π\piπ를 통해 대안 행동을 고려하여 Q-값을 업데이트합니다. 이를 통해 목표 정책 π\piπ를 따르는 최적의 Q-값을 학습합니다. 실제 행동 정책이 아닌, 목표 정책을 사용해 구할 수 있다.

 

- 행동 정책도 improve 되면 좋겠다. 
- 목표 정책은 greedy, 행동 정책은 입실론-greedy로 구한다.
- 이를 Q-러닝이라 한다

 

1. 벨만 기대 방정식(Bellman Expectation Equation) 

• Full Backup (DP): Iterative Policy Evaluation
  • 반복 정책 평가(Iterative Policy Evaluation)에서는 모든 상태에 대해 기대 값을 계산하여 정책의 가치 함수를 반복적으로 평가합니다.
  • 그림에서 각 상태는 모든 가능한 다음 상태로의 전이를 고려하여 업데이트됩니다.
• Sample Backup (TD): TD Learning
  • TD 학습에서는 현재 상태에서 샘플 하나를 사용하여 기대 값을 업데이트합니다.
  • 그림에서 현재 상태와 다음 상태 간의 샘플 전이만을 사용하여 업데이트됩니다.

2. 벨만 기대 방정식(Bellman Expectation Equation)

• Full Backup (DP): Q-Policy Iteration
  • Q-정책 반복(Q-Policy Iteration)은 상태-행동 가치 함수 qπ(s,a)q_\pi(s, a)qπ​(s,a)를 반복적으로 평가하고 개선합니다.
  • 모든 상태와 행동 쌍에 대해 모든 가능한 다음 상태와 행동을 고려하여 업데이트됩니다.
• Sample Backup (TD): SARSA
  • SARSA는 현재 상태와 행동, 다음 상태와 행동을 사용하여 가치 함수를 업데이트합니다.
  • 그림에서 현재 상태-행동 쌍과 다음 상태-행동 쌍을 사용하여 업데이트됩니다.

3. 벨만 최적 방정식(Bellman Optimality Equation)

• Full Backup (DP): Q-Value Iteration
  • Q-가치 반복(Q-Value Iteration)은 상태-행동 가치 함수 q∗(s,a)q_*(s, a)q∗​(s,a)의 최적 값을 반복적으로 찾습니다.
  • 모든 상태와 행동 쌍에 대해 가능한 모든 다음 상태와 행동을 고려하여 최적 값을 업데이트합니다.
• Sample Backup (TD): Q-Learning
  • Q-러닝은 현재 상태와 행동, 다음 상태에서의 최적 행동을 사용하여 가치 함수를 업데이트합니다.
  • 그림에서 현재 상태-행동 쌍과 다음 상태에서의 최적 행동을 사용하여 업데이트됩니다.

요약

방정식Full Backup (DP)Sample Backup (TD)

벨만 기대 방정식 vπ(s)v_\pi(s)vπ​(s)	Iterative Policy Evaluation	TD Learning
벨만 기대 방정식 qπ(s,a)q_\pi(s, a)qπ​(s,a)	Q-Policy Iteration	SARSA
벨만 최적성 방정식 q∗(s,a)q_*(s, a)q∗​(s,a)	Q-Value Iteration	Q-Learning

• Iterative Policy Evaluation: 모든 상태에 대해 반복적으로 가치 함수를 평가.
• Q-Policy Iteration: 상태-행동 가치 함수를 반복적으로 평가하고 개선.
• Q-Value Iteration: 최적의 상태-행동 가치 함수를 반복적으로 찾음.
• TD Learning: 샘플 하나를 사용하여 기대 값을 업데이트.
• SARSA: 샘플 상태-행동 쌍을 사용하여 가치 함수를 업데이트.
• Q-Learning: 샘플 상태-행동 쌍과 다음 상태에서의 최적 행동을 사용하여 가치 함수를 업데이트.

 

- 정리 -

- 1, 2장은 MDP를 알때,
- 3, 4, 5장은 MDP를 모를때
- 3장 - 동적 프로그래밍(DP, Model-Based), 4,5장 Model free들 에서 On- Policy,Off-Policy 배움