[Dynamic Programming - 1] Intro

Dynamic Programming

: Problem을 더 쉽고, 작은 Problems로 나누어 solution을 찾는 방법이다. 우리가 풀어야하는 Problem은 Optimal Policy $\pi_*$를 찾는 것

Property

: Dynamic Programming이 되기 위해서는 2가지 properties를 반드시 가져야한다.

1. Optimal substructure

: 나누어진 subproblems들의 optimal solution들을 구해서 합치면, original problem의 optimal solution이 되는 구조이다. 이는 즉, 각각의 state의 optimal solution을 합하면 entire problem의 optimal solution이 되는 구조이어야 한다는 뜻이다.

$$ \pi_*(s_1) \to \pi_*(s_2) \to \pi_*(s_3) = \pi_* $$

 

2. Overlapping subproblems

: 각 subproblem의 solution들은 서로 dependent하는 구조이다. Bellman optimality equations를 보면, State value(혹은 Action value)가 다른 State value(혹은 Action value)에 의존하고 있으며, 이는 Overlapping subproblems를 만족한다는 것을 알 수 있다.

What does DP exactly do?

 

$$ v_*(s) = \max_a\sum_{s',r}p(s',r|s,a)[r+\gamma v_*(s')] $$

$$ V(s) \gets \max_a\sum_{s',r}p(s',r|s,a)[r+\gamma V(s')] $$

첫번째 식인 Bellman Equation을 통해 두번째 식과같은 Update Rule로 만들어 Iterative하게 Improve하는 것이 Dynamic Programming이다.

 

위와 같은 estimate 과정은 beginning이 accurate할 필요는 없다. iterative하게 improve되면 된다.

Model of the environment

DP의 중요한 점은 Expected Value(기대값)을 사용하여 문제를 푸는 것이다. (not trial, or error) Action을 취할 때 발생할 수 있는 모든 가능한 결과를 고려하고 그것을 사용해 추정값을 업데이트한다. 따라서 DP를 사용하기 위해서는 현재 State에서 어떠한 Action을 취했을 때 어떠한 State로 변할지에대한 확률을 미리 알고있어야 한다.

• ex: $\pi(a|s) = [0.2, 0.3, 0.5]$

이러한 정보를 미리 알고있어야하는 상태 즉, perfect model of the environment가 필요하다는 점은 Dynamic programming의 커다란 한계이다. 왜냐하면, 큐브를 푸는 것과같이 어떠한 축을 돌렸을 때 다음 결과가 명확한(perfect model of the environment)인 경우에는 괜찮지만 더 커다란 문제 혹은 model of the environment를 알 수 없는 경우에는 모든 가능한 결과를 고려할 수 없기 때문에 다른 알고리즘을 사용해야한다.