MDP안에서 최적의 policy를 찾아나가 보는 solution에 대해서 배워보자 .
2. policy Evaluation
policy가 정해졌을때 value function이 어떻게 되는지 찾기
3. policy iteration, value iteration
어떤 iterate한 방법론을 통해서 최적의 policy를 찾아나가는 방법인데 policy 기반의 방법이 있고 value기반의 방법이 있다.
dynamic programming : 복잡한 문제를 작은 문제로 나누어서 푸는 방법
참고로 RL은 model based, model free로 나뉘게 되고
model based는 environment를 다 알고있을때를 말하며
이를 푸는걸 planning을 사용하는데 그 방법 중에서 dynamic programming이 있다.
dynamic programming이 되기 위해서는 2가지 조건이 필요한데
1. optimal substructure가 있어야되고
2. subproblem 들이 계속 겹쳐서 나와야 된다.(divide and quanqure처럼)
mdp는 위의 뒤 조건을 만족함.
bellman equation이 recursive하게 되어있고 그것들이 계속 사용된다.
dynamic programming은 mdp에 모든걸 알고있다.
mdp를 푼다는건 두가지가 있는데
1. prediction 문제는 푸는것(optimal value function을 찾는거)과
2. control 문제는 푸는것 (optimal policy를 찾으려 하는거)이다.
dynamic programming으로 두가지를 다 할것임.
dynaminc programming은 다양한 곳에서 쓰인다.
policy evaluation문제는 이 policy를 따랐을떄 받는 return이 얼마나 되냐(=value function)을 찾는 것이다.
bellman expectation을 이용해서 iterative 하게 이용하는 방법론이다.
처음에 random하게 모든 state의 v를 정해둠
이를 계속 update해나가면서 optimal에 가깝게 만듬
이 수식은 V을 Q로 표현했다가 bellman equation으로 다시 Q를 V로 표현하여 V를 V로 표현한 bellman equation이다
저 R의 정확한 정보가 조금씩 계속 들어감.
이게 값이 안바뀔떄까지, 수렴할때까지 계속 함.
우리는 prediction
MDP가 주어졌을때 5에서 6으로 가는걸 볼때
random policy일때 value(return 의 기대값)가 무엇일까?
이게 어려운 문제이다.
prediction (value function)을 찾아보면 처음에는 random
계속 update하였더니 value가 점점 정확해진다.
policy를 평가만 하였는데도 바보같은 policy를 greedy하게 움직이기만 해도 optimal을 찾을 수 있다.
이번에는 policy iteration이다
우선 앞에서 하듯이 평가하고(value function을 찾는거)
중간중간에 policy를 greedy하게 찾아봐서 update함
처음에는 V를 evaluate (value function을 찾고) 이 찾은 value function에서 greedy하게 움직이는 policy를 만들고 이를 반복하면 점점 V가 star에 도착한다.
eval impove를 반복하는게 policy iteration이다.
일단 deterministic하게 움직이는 policy
