MDP를 정확히 알지 못하는 상황에서 Prediction을 수행하는 방법. value function을 estimate.
Model-free Reinforcement Learning
- Model-free prediction : value function을 estimate (policy를 따랐을 때 리턴의 기대값이 어떻게 될것인지)
- Model-free Control : value function과 policy의 optimal한 값을 찾는 것. ㄹ
Monte-Carlo (MC) Learning
MDP를 모르기 때문에(어떻게 state가 변화할지, 리워드는 얼마나 받을지) Policy를 따라서 직접 에피소드를 진행하는 방식. 모든 에피소드는Terminal state가 있어야 하며, 각 에피소드가 terminal-state까지 진행됐을 때 받을 수 있는 리턴의 평균값을 학습함.
Monte-Carlo Policy Evaluation : 리턴의 평균값을 통해 계산. Policy의 V(s)를 계산.
V(s) = 리턴의 기대값 (MC에서의 V(s) = 리턴의 평균값)
Gt(리턴) = discounting factor가 적용된 리워드의 총합
evaluation계산 과정 :
1) N(s) 업데이트 : k번의 에피소드 수행 시 이 state에 몇 번 방문했는지 카운팅
- First time-step : 첫 번째 방문 시에만 카운팅
- Every time-step : 모든 방문 시 카운팅
2) Z(s) 업데이트 : Total return. 매 에피소드마다 발생한 리턴을 저장
3) V(s) = Z(s)/N(s) : 리턴의 평균.
=> N이 커지면 평균값은 같은 값으로 수렴한다. 이 때 수렴한 값을 Policy의 Value Function으로 할당함.
Incremental Monte-Carlo Update (실시간 업데이트)
K번의 모든 에피소드가 끝나고 value를 업데이트 하는 것이 아니라 매 에피소드마다(한 번 에피소드 수행 시) Value 값 업데이트
- 현재의 평균(V(St)) = 현재 리턴값(Gt)과 이전 리턴 평균값(V(St))을 통해 업데이트. (현재 구한 리턴값과 이전 리턴 평균값의 차이를 통해 차이값만큼 이전 평균에 더해서 V(St)를 업데이트.
- MDP 환경이 계속 변화하는 문제에서는 리턴의 평균을 산출 할 때 running mean인 알파값을 사용해서 계산하는 것이 유용할 수 있음.
(e.g. 옛날에 했던 에피소드는 영향력이 작게 반영되도록 알파값을 작은 수로 가정.)
Temporal-Difference (TD) Learning (model-free)
다음 state의 value의 추정값을 가지고 현재 state의 value를 추정하여 업데이트
MC vs TD
- 실제 에피소드를 경험하여(MDP를 모르기 때문에) Policy를 따라 에피소드를 수행했을 때, 여러 번의 에피소드에서 나오는 결과를 가지고 policy를 evaluation(policy의 value를 prediction)
- 차이점 :
- MC
terminal state까지 가서 에피소드가 끝나야(completed episode) 리턴값 계산 가능. - TD
1) Terminal state까지 가지 않아도 리턴값을 예측함으로써Value값을 evaluation 할 수 있음.
- Terminal state가 없는 연속적인 에피소드 환경에서도 학습을 할 수 있다.
- Final outcome이 나오기 전에 업데이트를 할 수 있고, 에피소드 수행시 매 step마다 학습이 가능하다 (online으로 학습 가능)
2) 다음 state의 value값(추정값)을 통해 현재 state의 value 추정.
- TD target : 다음 state 리턴을 예측한 값
- MC에서의 Gt가 TD에서는 TD target
Bias/Variance Trade-off
1. MC : 0 bias, high variance
- 리턴값 Zero bias
- V(St) : N(St)가 커지게 되면 Value가 하나의 값으로 수렴한다
- 초기값의 영향이 적다(초기값이 어떤 값이더라도 결국 하나로 수렴하기 때문에 초기값의 영향을 받지 않음) - action, transition, reward High variance
- 랜덤한 action, transition, reward를 갖게 됨. 모두 high variance.
- 어떤 액션을 하느냐에 따라 값이 많이 차이남. 여러개의 에피소드 진행하면 액션도 무수히 많은 경우의 수 발생하고, 완전 새로운 곳으로 터미널을 가고, 리워드도 각각임.
=>(리턴 평균에 대해 high variance를 가질 수 있고, 이것은 Policy 결과에 대한 일관성이 떨어짐)
2. TD : some bias, low variance
- TD target, V(s) – some bias.
- 정확한 평균값보다는 차이가 있을 수 있음. - action, transition, reward High variance
- 전체 에피소드 보는 게 아니라 다음 에피소드만 보기 때문에 한 번의 action과 transition만 수행되어 전체를 다 보는 것보다는 당연히 변화가 적다.
- Variance관점에서 MC보다 유리하다