Model Based Learning 의 대표적인 알고리즘들이다.
실제 환경과 상호작용 없이 모델 정보 만으로 value function 을 찾는 방법에 대해 알아보자.
DP 의 한 방식으로, Bellman Optimality Equation 을 기반으로 value fuction 자체를 업데이트 하는 방식이다. 아직 최적의 value function을 모르기 때문에, 현재까지 알고 있는 정보를 통해 점진적으로 최적의 값까지 근사해 나가는 것이다.
$$ V_{k+1}(s)\leftarrow\text{max}a\sum{s',r}p(s',r\mid s,a)[r+\gamma V_k(s')] $$
이전 시점의 value function 을 이용해 값을 업데이트한다. k 는 업데이트 횟수로, 시간축이라고 생각하면 좋다.
업데이트 과정은 함수값이 수렴할 때 까지 반복된다.
과정은 다음과 같이 진행된다.
모든 state 에 대해 $V_0(s)$ 값을 0 으로 초기화
값이 수렴할 때 까지 모든 $V_k(s')$ 으로부터 $V_{k+1}(s)$ 를 업데이트
최종적으로 구한 value function 을 이용해 optimal policy 를 계산
$$ \pi_(s)=\text{argmax}a\sum{s',r}p(s',r\mid s,a)[r+\gamma V_(s')] $$
하지만 이 방법은 모든 state 조합에 대해 계산해야 하기 때문에 복잡도가 $O(S^2A)$ 로 느리다는 단점이 있다. 또한 State Value Function 만 업데이트 하고, 업데이트 내용을 바탕으로 Optimal Policy 를 유도하기 때문에 Policy 계산이 느리다. 이로 인해 Policy 가 수렴한 이후에 Value 가 수렴하는 경우가 생겨 비효율적이다.
위와 같이 각 State 에서 action 들을 평가한 결과를 저장한 테이블을 Q-table 이라고 한다. 이를 통해 에이전트는 어떤 행동이 가장 유리한지를 policy 없이 테이블만 보고 결정할 수 있다. 하지만 차원의 저주(curse of dimensionality) 로 인해 상태나 행동 공간이 커질 경우 테이블 크기가 급격히 증가하며, Q-table은 일반화 능력이 없기 때문에, 학습한 상태-행동 쌍 이외의 경우에는 적절한 판단을 내릴 수 없다.
