Model free Prediction/Control

MDP의 모든 요소(state, tansition probability, reward, discount factor, action)들을 다 알고 있을 때 dynamic programming을 사용하여 optimal value function과 policy를 구했었다.

 

MDP에서 transition matrix를 모르는 상태, 즉 Model free한 상황에서 agent가 value와 policy를 어떻게 학습시킬 수 있을까? 2가지 모델을 통해 그 방법을 자세히 알아보도록 하겠다.

 

1.Monte Carlo(MC)

1)Prediction

-MC prediction에서는 agent가 model free한 상황, 즉 transition probability를 모르는 상황에서 value function 값을 구하는 것을 목적으로 한다.

-과정

1)agent는 각 state마다 episode를 실행한다

2)각 episode별로 Return값을 저장을 한다.

3)지정된 횟수 만크 에피소드를 실행을 하면 Return을 평균을 한다.

=>즉 V(s) = average(G1, G2, G3 ...) 값이 된다.

-각 state에 새로운 return값이 주어지면 V(s)가 업데이트 되는데 이 때 기존의 평균을 구하는 방식(한번에 더해서 나누는 방식)이 아닌 incremental mean을 사용하게 된다.

incremental mean

 

incremental로 인해 유도된 식

-incremenral mean을 이용하여 V(s)를 업데이트하는 식을 유도하였다. 기존의V(s)값과 새로운 Gt값 그리고 인수의 개수만 주어지면 새로운 V(s)를 구할 수 있게된다.

-episode형식으로 학습을 진행하는 MC에서 agent는 특정 state를 중복해서 지나가는 경우가 있다. 이렇게 중복해서 state를 지나갈 때의 reward값을 어떻게 계산할 건지에 따라 First visit과 Every Visit으로 나눌 수 있다.

  =>First Visit: 맨 처음 지나갈 때의 reward만을 고려

  =>Every Visit: 모든 state의 reward를 고려

 

2)Control

-DP에서는action value function을 최대로 하는 action으로 policy를 업데이트를 하는 Greedy policy방식으로 control을 진행 하였다. 하지 Model이 free한 상황에서 학습이 충분히 이루어지지 않은 경우 greedy policy사용할 때 optimal한 값을 도출하기 어려워 질 수 있다. 예를 들면 agent가 action을 취해서 goal state로 진행하는 에피소드를 실행했다면 이 때받은 return으로 인해 해당 action이 optimal 하지 않더라고 그 방향으로 학습을 하게 된다.

-그래서 ε-greedy policy란 방식으로 MC control을 진행

 =>ε이란 state에서 action을 랜덤하게 취할(exploration) 확률을 의미한다.

 =>각 state별로 actio value function을 구하고 argmax함수로 action value function이 높은 action을 정하면  ε-greedy policy를 이용하여 policy를 업데이트 하게된다.

 

 

2. Temporal Difference

1)Prediction

-MC의 Prediction의 과정과 동일하다.

-'incremental mean'으로 유도된 식을 보면 V(s)가 특정 값으로 수렴하기 위해서는 빨강색의 식이 V(St)에 수렴을 해야한다.

TD prediction

TD target/error

따라서 빨간 글씨의 식이 TD target, 거기서 V(S)값을 뺀값을 TD error라고 정의한다.

 

2)Control

-우선 새롭게 등장하는 policy의 종류를 알아보도록 하자

 =>Target policy: 학습의 대상이 되는 policy

 =>Behavior policy: 실제로 Behavior을 하는 policy

-이 두개의 policy가 같은 경우 on policy, 다른 경우를 off policy라고 한다.

-SARSA(on policy)

SARSA

  =>아래의 식은 SARSA에서 action Value를 업데이트 하는 식이다. incremental mean을 이용하여 유도되었으며 현재의 state가 아닌 그 다음 state인 S'에서 A'를 취한 것까지가 고려가 되어 현재 state S에서의 action value function이 업데이트 된다.

  => 현재의 state S에서 action A를 취해 reward R을 저장하고 그 다음 state S'에서 A'를 취한 후 S의 action value가 update 된다 해서 과정의 initial을 따서 SARSA라는 명칭이 부여되었다.

  =>action을 취할 때는  S와 S' 모두 ε-greedy policy따른다.

 

- Q Learning

Q Learning

 =>Q learning에서도 S와 S'에서 ε-greedy policy를 취하지만 SARSA와 다른 점은 target policy가 greedy policy를 따른다는 점이다. 따라서 action value를 구하는 식에서도 Q(S',A')에 max를 씌운 것을 알 수 있다.

 =>이렇게 ε-greedy policy와 greedy policy를 모두 사용하여 control을 하는 Q learning은 exploration을 하는 동시에 optimal한 다는 장점이 있다.