MDP를 안다 = 상태 전이 확률과 보상함수를 안다.

MDP를 알 때 이를 이용하여 정책을 개선하는 것을 플래닝이라고 한다.

prediction - 정책 $\pi$가 주어졌을 때 각 상태의 value를 평가하는 것

control - 최적의 정책 함수를 찾는 것

MDP를 알 때 최적 정책 구하는 방법

1. 정책 이터레이션 (policy iteration)

• 본 과정은 크게 2단계로 이루어져 있다.

• 1. policy evaluation
     랜덤 정책 $\pi$에 대해 반복적 정책 평가를 통해 각 state의 value를 계산하는 것
• 2. policy improvement
     각 state에서의 value를 기반으로 현재 상태에서 가장 높은 value를 가지는 다음 상태로 가는 greedy한 행동을 하도록 하는 정책을 만들었을 때 이전에 비해 최적 정책에 가까워 진다.

• 이 두 과정을 무한히 반복하여 수렴하는 곳이 optimal policy와 optimal value가 된다.

반복적 정책 평가 (Iterative policy evaluation)

• 말 그대로 그 정책을 따라갔을 때의 상태를 계산하는 것
• 테이블의 값들을 초기화한 후, 벨만 기대 방정식을 반복적으로 사용하여 테이블에 적어 놓은 값을 조금씩 업데이트해 나가는 방법론
• 만약 MDP를 안다면 사용할 수 있는 방법
• 4x4 gird world 상황에서 한 스텝마다 -1, 동서남북으로 이동할 확률이 모두 같은 상황이라면 MDP를 알고 있으므로 적용 가능하다. ($r_s^a$= -1,$P^a_{ss'}$ = 1/4)

policy iteration의 단점

이 방법은 상당히 많은 연산이 필요하다.
우선 첫번째 단계인 policy evaluation의 경우 각 state의 value를 계산하기 위해 value가 수렴할 때 까지 진행해야 하는데 state의 개수, action의 개수가 많을수록 시간이 오래 걸린다.
그리고 두번째 단계는 policy가 수렴할 때 까지 진행해야 하는데 언제 수렴하는지 알 수 없다.
이러한 문제를 해결하기 위해서는 첫번째 단계에서 과연 각 state value가 수렴할 때까지 진행해야 하는가? 라는 질문을 던져봐야 한다.

만약 state value의 값들의 대소관계가 수렴했을 때와 같은 상황에 있더라면 여기서의 greedy policy는 수렴했을 때의 greedy policy와 같다. 따라서 우리는 어느 정도만 방향성이 나온다면 두번째 단계로 넘어갈 수 있다.

2. 밸류 이터레이션 (value iteration)

이 개념을 알기 위해서는 optimal value에 대한 정의를 다시 살펴볼 필요가 있다.
optimal value란 optimal policy를 따라갔을 때 얻는 값이다.

이번엔 policy iteration과 다르게 벨만 최적 방정식을 이용한다.

우리는 MDP를 알기 때문에 위를 바로 계산할 수 있다.
이를 무한히 반복하면 state가 수렴하게 되고, 그때에서의 greedy policy가 optimal policy가 된다.