강화학습 - Planning

이번 챕터에서는 MDP를 알고 있을 때의 value를 평가하는 플래닝에 대해서 알아봅시다.
규모가 작은 문제, MDP를 알고있다라는 두 가지 조건을 만족해야하는 상황에서 사용하는 방법입니다.

보상 함수 $R$과 전이 확률 행렬 $P$를 알고있다는 가정입니다. MDP의 모든 정보를 알 때 정책을 개선하는 과정을 플래닝이라고 말합니다. 상상 속에서 시뮬레이션 하면서 좋은 계획을 세우는 과정이라고 생각하면 될 것 같습니다.

---

정책 $\pi$가 주어졌을 때 각 상태의 value를 평가하는 prediction과 최적 정책 함수를 찾는 control 문제를 푸는 방법에 대해 살펴보겠습니다. 내용은 주로 테이블 기반 방법론(tabular method)에 기반합니다.
테이블 기반 방법론은 상태나 액션의 개수가 많지 않아서 그에 해당하는 테이블을 만들어 그 값들을 업데이트 하는 방법입니다.

반복적 정책 평가

가장 쉬운 격자 모양의 길찾기 과정에서 예시를 보겠습니다.

4방향으로 랜덤하게 움직이는 에이전트가 있고 각 스텝마다 -1의 보상을 받을 때 각 상태의 밸류를 평가하는 문제입니다.
4방향 랜덤이라는 정책 $\pi$가 주어졌고 각 상태에 대한 가치 함수 $v(s)$를 구하는 전형적인 prediction 문제입니다. 반복적 정책 평가(Iterative policy evaluation) 방법론을 통해 문제를 해결할 수 있습니다.

1. 테이블 값을 적당히 0으로 초기화

2. 하나의 상태값을 업데이트
   이 값은 벨만 기대 방정식을 통해 업데이트합니다.

   $v_{\pi}(s)=\Sigma_{a\in A}\pi(a|s)(r_{s}^{a}+\gamma\Sigma_{s'\in S}P_{ss'}^{a}v_{\pi}(s'))$

   식은 어려워 보이지만 실제 값을 대입하면 간단하게 변합니다.

   $v_{\pi}(s_{5})=0.25\times(-1+0)+0.25\times(-1+0)\\+0.25\times(-1+0)+0.25\times(-1+0)=-1$

   테이블의 상태를 -1로 업데이트 하게됩니다.

   이 시점에서 이게 왜 더 정확한 값이지?하고 의문이 생길 수 있습니다. 단지 임의로 정한 0값을 현재 상태를 업데이트하는데 사용했기 때문입니다. 물론 현재 테이블에 담긴 값과 다음 상태의 값만 가지고 업데이트 한다면 무의미할 수 있지만 보상이라는 실제 환경이주는 정확한 시그널을 섞어서 업데이트합니다. 그래서 처음은 무의미하더라도 업데이트 할수록 실제 값에 가까워지게 됩니다.

3. 모든 상태에 대해 2의 과정을 적용해준다.

4. 2~3의 과정을 반복

간단하게 그림으로 보면 아래와 같습니다.

그림 4에서 -59.4는 평균적으로 약 60번정도 움직여야 종료상태에 도달한다는 의미입니다.

최적 정책 찾기

MDP를 알 때 최적 정책을 찾는 2가지 방법이 있습니다.

정책 이터레이션

정책 이터레이션은 기본적으로 정책 평가와 정책 개선을 번갈아 수행하여 정책이 수렴할 때까지 반복하는 방법론입니다. 위에서 가치 평가를 통해 구한 결과에서 그리디하게 바로 다음 상태를 보고 선택하는 방법을 정책으로 선택하면 바로 최적정책을 구할 수 있습니다.
물론 이렇게 그리디한 정책을 택했을 때 최적 정책과 일치하는 경우는 예시가 너무 간단한 MDP이기 때문에 그렇습니다. 보통은 이전 정책에 비해 소폭 향상되는 정도로 그칩니다. 중요한 부분은 정책이 개선되었는 점입니다.

정책 이터레이션은 정책 평가, 정책 개산 총 두 단계로 이루어져 있습니다.
정책 평가 단계에서는 임의의 정책 $\pi$에 대한 각 상태의 value를 모두 구합니다. 각 상태의 가치를 평가하는 일이기 때문에 정책 평가라고 부릅니다. 정책 개선 단계는 앞 단계에서 구한 $v(s)$에 대해서 그리디 정책을 생성하면 됩니다. 이 단계를 반복하면 정책도 변하지 않고 가치도 변하지 않는 단계에 도달하는데 수렴하는 곳이 바로 최적 정책과 최적 가치입니다.

정책 평가 부분은 반복적인 loop 작업이 포함되어 있는데 이를 간소화시킬 수 있습니다. 강화학습의 목적이 가장 최적인 정책을 찾는 것이기 때문에 가치 평가하여 나온 값들은 필요하지 않습니다. 그래서 실제로 가치 평가할 때 극단적으로 한번만 업데이트해도 된다고 합니다(loop를 한번만 실행). 그리디 정책이 이전과 다르기만 하면 일단 개선은 할 수있고 결국 수렴하여 최적 정책을 찾을 수 있기 때문입니다.

---

실제로 정책이 개선되는지 의문이 생깁니다. 그리디하게 가다가 이상한 지점에 수렴하거나 수렴이 안되는 경우도 있지 않나?라는 생각을 가져볼 수 있습니다. 직관적으로 보면 미래의 보상을 가지고 정책평가과 가치평가가 이루어지고 값을 업데이트 하여 반복하기 때문에 그리디 정책을 따르는 게 좋은 것 같습니다. 실제로 이 방법론에 대한 수학적인 부분은 증명이 되있다고 하는데 다음에 시간이 나면 찾아봐야겠습니다.

밸류 이터레이션

정책 이터레이션은 단계마다 서로 다른 정책의 가치를 평가했지만 밸류 이터레이션의 경우는 최적 정책이 만드는 최적 밸류하나만 바라보고 수행합니다. 이 방법은 이해하기 훨씬 쉽습니다.

우리는 MDP를 알고 있기 때문에 반복적 정책평가를 통해 최적 가치 $v_{*}(s)$를 구할 수 있습니다. 이제 에이전트 입장에서 어디로가면 다음 상태에서 받을 보상이 가장 클지 알기 때문에 그리디 정책처럼 최적 밸류가 가장 높은 칸으로 움직이면 끝납니다. 어차피 가장 높은 값으로 이동하는 것 말고는 다른 선택지는 없습니다.