Lecture 5: Model-Free Control

다시 한번 Prediction과 Control의 차이을 알아보겠습니다. 

Prediction (Value Function을 찾는 문제입니다.)

• 입력 : MDP $<S,A<P,R,\gamma>$ 그리고 정책 $\pi$
• 또는 : MRP $<S,P^{\pi},R^{\pi},\gamma>$
• 출력 : 가치함수 $v_{\pi}$

Control (Policy를 찾는 문제입니다.)

• 입력 : MDP $<S,A,P,R,\gamma>$
• 출력 : 최적의 가치함수 $v_{*}$
• 그리고 : 최적의 정책 $\pi_{*}$

Uses of Model-Free Control

다음은 MDP로 모델링을 할 수 있는 몇가지 예제 문제에 대해서 설명하고 있습니다.

• 대부분의 이러한 문제에 대해 설명해 보겠습니다.
  • MDP 모델은 알 수 없지만, 경험은 샘플링이 가능합니다.
  • MDP 모델을 알 수 있지만, 쓰기에는 너무 크고, 샘플은 제외됩니다.
• Model-free control은 이러한 문제들을 해결할 수 있습니다.

On and Off-Policy Learning

• On-policy learning
  
  • 직접 Policy를 찾으면서 배웁니다.
• Off-policy learning
  • 다른 사람이 쌓아놓은 Policy의 경험를 통해서 배웁니다.

Generalised Policy Iteraion (Refresher)

• 저번 시간에 Generalised Policy Iteration에 대해서 공부했었습니다.
  • 정책 평가는 어떤 고정된 정책 $\pi$가 있다고 하였을 때 그것을 평가합니다.
  • 정책 개선은 정책 평가 부분에서 나온 정책 $\pi$를 향상 시킵니다.
• 이 한 episode를 계속 반복하는 것을 Policy Iteration이라고 배웠었습니다.

Generalised Policy Iteration With Monte-Carlo Evaluation

• 정책 평가 부분에서는 MC 정책 평가를 사용하면 안될까?
  • V를 바탕으로 정책 평가를 한다는 것은 다음 State를 알고 있다는 가정하에 이루어집니다. 그렇다면 다음 State를 안다는 것은?? 결국 MDP를 아는 것이라고 말할 수 있습니다. Model-Free에서는 환경을 모르는데 환경을 아는 방식으로 평가하게 된다면 당연히 안되겠지요.
• 정책 개선 부분에서는 Greedy 정책 개선을 사용하면 안될까?

Model-Free Policy Iteration Using Action-Value Function

• MDP의 모델을 알아야  Greedy 정책 개선을 통해 V(s)를 알 수 있다.

$$\pi(s) = \underset{a \in A}{argmax} R^{a}_{s} + P^{a}_{ss'} V(s^{'})$$

• State Value Function이 아닌 Action Value Fucntion을 이용했다고 하면 Q함수는 사용이 가능할까?

$$\pi(s^{'}) = \underset{a \in A}{argmax} Q(s,a)$$

Generalised Policy Iteraion with Action-Value Function

• 정책평가에서는 MC의 평가, $Q = q_{\pi}$
• 정책 향상에서는 Greedy정책 개선을 사용한다??
  • Greedy정책 개선을 할려면 모든 State를 충분하게 봐야 하는데, 하지만 모든 State를 보지 않고 막힐 수 있음(Greedy하게 한다면 충분히 많은 곳을 가볼 수 없음) -> Explore이 되지 않음

Example of Greedy Action Selection

• 위 예시는 Greedy 행동 선택에 대한 예시를 보여주고 있습니다.
• 위의 예시같이 선택한다면 과연 가장 좋은 문을 선택할 수 있을까요???

$\epsilon$-Greddy Exploration

• 1 - $\epsilon$의 확률로 다른 greedy한 행동을 선택합니다.
• 또는 $\epsilon$의 확률로 무작위도 행동을 선택합니다.
• $\epsilon$이 있어 좋은 두가지 성질 
  • 모든 행동을 탐험 할 수 있는 것을 보장할 수 있습니다.
  • 정책이 계속 발전하는 것을 보장할 수 있습니다.

$\epsilon$-Greedy Policy Improvement

• $\epsilon$ Greedy를 해도 정책이 향상된다는 내용입니다.
• 어떠한 모든 $\epsilon - greedy$ 정책 $\pi$의 경우 $q_{\pi}$에 대한 $\epsilon - greedy$정책 $\pi^{'}$이 개선되었습니다, $v_{\pi^{'}}(s) \geq v_{\pi}(s)$

Monte-Carlo Policy Interation

• MC를 이용해서 Q를 평가합니다.
• greedy policy improvement 대신에 $\epsilon-greddy$ policy improvement를 사용합니다.

Monte-Carlo Control

• MC로 Policy evaluation할 경우에 한개의 episode단위로 value function을 업데이트 하기 때문에 끝까지 화살표가 가지 않습니다.
• Evluation 단계 때 끝까지 가지 않고 바로 improve를 수행합니다.

GLIE

• GLIE Property(Greedy in the Limit with Infinite Exploration)
  • 모든 State action 페어들이 무한히 반복되어야 합니다. (그래야 Explore를 충분히 할 수 있음) Exploration에 관한 것

$$\underset{k \rightarrow \infty }{lim} N_{k}(s,a) = \infty$$

• 정책은 greedy 정책에 수렴합니다.(Exploitation에 관한 것)

$$\underset{k \rightarrow \infty }{lim} \pi_{k}(a \mid s) = a(a = \underset{a^{'} \in A}{argmax} Q_{k}(s,a^{'}))$$

GLIE Monte-Carlo Control

• 샘플 k번째 에피소드를 사용팝니다 $\pi : {S_{1},A_{1},R_{2},...,S_{T}} \sim \pi$
• GLIE MC control은 최적의 행동가치함수에 수렴을 합니다. $Q(s,a) \rightarrow q_{*}(s,a)$

Back to the Blackjack Example

• Control에 대한 블랙잭 게임 예시입니다.

Monte-Carlo Control in Blackjack

MC vs. TD Control

• TD 학습은 MC에 비해 몇가지 장접이 있습니다.
  • 낮은 분산
  • 실시간
  • 불완전한 수열
• Control loop에서 우리는 MC 대신에 TD를 쓰면 안되는 걸까??
  • TD를 $Q(S,A)$에 적용
  • $\epsilon - greedy$ 정책 발전을 사용
  • 매 스텝마다 업데이트 적용

Updating Action-Value Functions with Sarsa

이 알고리즘은 Sarsa 알고리즘이라고 불립니다.

On-Policy Control With Sarsa

• 한 episode만큼 가는게 아니라 한 스텝만큼 갑니다.
  • Sarsa 정책평가 $Q \approx q_{\pi}$
  • $\epsilon-greedy$를 통해 정책 개선

Sarsa Algorithm for On-Policy Control

Convergence of Sarsa

• Sarsa는 최적의 행동가치함수,$Q(s,a) \rightarrow q_{*}(s,a)$에 수렴합니다.
  • GLIE 수열의 정책들 $\pi_{t}(a \mid s)$
  • Robbins-Monro 수열의 Step-size $a_{t}$

$$\sum_{t=1}^{\infty}a_{t} = \infty$$

\[\sum_{t=1}^{\infty}a_{t}^{2} < \infty\]

Windy Gridworld Example

Sarsa on the Windy Gridworld

Sarsa를 이용한 Windy Gridworld 업데이트입니다.  

n-Step Sarsa

Forward View Sarsa($\lambda$)

Backward View Sarsa($\lambda$)

Sarsa($\lambda$) Algorithm

Sarsa($\lambda$) Gridworld Example

Off-Policy Learning

Off-Policy에 대해서 알아보겠습니다.($\mu$와 $\pi$가 다른 것)

• behaviour policy $\mu(a \mid s)$가 존재합니다.
• behaviour policy $\mu$는 실제 Action을 샘플링하는 policy입니다.
• target policy $\pi$가 있음

$${S_{1},A_{1},R_{2}, ..., S_{T}} \sim \mu$$

• Off-Policy는 왜 중요한가?
  • 이것은 Agent의 행동을 관찰하는 것으로도 배울 수 있습니다.
  • 옛날의 정책 $\pi_{1},\pi_{2},...,\pi_{t-1}$ 을 이용해 재사용하여 경험이 가능합니다.
  • 탐험적인 행동을 하면서 최적의 정책을 배울 수 있습니다.
  • 한개의 정책을 따르면서 여러개의 정책을 배울 수 있습니다.

Importance Sampling

• Importance Sampling은 다른 분포에 대한 기대값을 추정하는 방식입니다.
• 너무큰 분산이라 현실세계에서는 쓸 수 없습니다.

Importance Sampling for Off-Policy Monte-Carlo

• $\pi$를 평가하기 위해 $\mu$에서 생성 된 반환을 사용합니다.
• 정책간의 유사성에 따른 반환값 $G_{t}$인 Weight를 반환합니다.
• 전체 에피소드에 따라 중요도 샘플링 수정값을 곱합니다.

Importance Sampling for Off-Policy TD

Q-Learning

• 행동가치함수인 Q를 Off-Policy를 통해서 학습하고 싶은게 목적입니다.
• 여기서는 importance sampling을 쓰지않고 하고 싶음
• Behavior policy를 통해서 Action을 하나 뽑고 Action을 수행합니다. $S_{t+1}$에 도착하면 behavior policy 대신에 target policy를 사용해주면 됩니다.

Off-Policy Control with Q-Learning

• 우리는 behavior policy처럼 target policy도 improve되었으면 좋겠습니다.
• Target policy는 greedy Q로 policy를 정합니다.
• behavior policy는 $\epsilon-greedy$ Q로 정합니다.

Q-Learning Control Algorithm

• 할수 있는 Action들 값중에 선택하는 것이기 때문에 3개가 있음
  • Q-learning control은 최적의 행동가치함수, $Q(s,a) \rightarrow q_{*}(s,a)$에 수렴합니다.
  • Sarsa max로도 불립니다.

Q-Learning Algorithm for Off-Policy Control

Relationship Between DP and TD