3강 | Planning by Dynamic Programming

Dynamic programming : 큰 문제를 작은 문제로 나누고 작은 문제를 풀어서 큰 문제를 푸는
Dynamic programming의 조건
- Optimal substructure
  - 전체 큰 솔루션에 대해서 작은 솔루션으로 나뉠 수 있어야 한다.
- Overlapping subproblems
  - 한 subproblems을 풀면 저장을 해뒀다 re-use를 할 수 있어야 한다.
- MDP는 이 두 조건을 모두 만족한다.
  - Bellman equation은 recursive하게 subproblem으로 나뉜다
  - Value function이 작은 문제의 해 기 때문에 store, reuse가 가능하다.
Dynamic programming은 MDP에 대한 모든 지식을 알고 있다고 가정한다.
For prediction:
- Input : MDP and Policy $\pi$ or MRP
- Output : value function $v_\pi$
Or for control:
- Input : MDP
- Output : optimal value function $v_$ and optimal policy $\pi_$

Problem : evaluate a given policy $\pi$
처음에 랜덤한 v1 → v2 … → v_pi
synchronous backup
- each iteration마다 모든 스테이트에 대해서 Update $v_{k+1}(s) from \, \, v_k(s')$
- 이것이 $v_\pi$에 수렴한다
- Bellman Expectation Equation을 통해 $v_k$를 구해준다면 그 구한 $v_k$를 greedy하게 따라간다면 optimal Policy가 된다. ( Greedy Policy w.r.t $v_k$)