[강화학습5]최적 정책(Optimal Policy)

최적정책에 대한 정의는 다음과 같이 내릴 수 있다.

$$\pi^* \geq \pi \iff v_{\pi^*}(s) \geq v_{\pi}(s)  , \forall s \in S$$

이번 포스팅에서는 최적정책의 존재에 대해서 증명해보려고 한다.

벨만최적방정식(Bellman optimality equation)

$$v^*(s) = v_{\pi^*}(s)$$

$v^*(s)$를 최적가치(Optimal value)라고 한다

$v^*(s)$는 $v_{\pi}(s)$중  최대 가치를 가져야 한다. 그러므로 가장 큰 $q^*(s, a)$를 가지는 행동을 선택해야 한다. 

$$v^*(s) = \underset {a}{\max} q^*(s, a)$$

$$q^*(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid a, s)  v^*(s')$$

---

$$v^*(s) = \underset {a}{\max}  R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) v^*(s')$$

$$q^*(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid a, s)  \underset {a'}{\max} q^*(s', a') $$

가치반복(Value Iteration)

벨만최적 방정식은 재귀적인 형태를 띠고 있기 때문에, 주어진 상태에 대한 최적가치는 다른 상태의 최적가치에
의존한다. 그렇기에 단순히 벨만 방정식만 사용해서는 바로 최적가치를 계산하는 것이 어렵다. 하지만 가치반복을 이용하여 최적가치의 근사치를 구하는 것은 가능하다. 가치반복은 다음과 같은 방식으로 진행된다:

1. 모든 상태에 대한 초기 가치를 임의로 설정한다. 이를 $v_0(s)$라고 하자.
2. 각 반복마다, 각 상태에 대해 최적가치를 계산하려고 한다. 즉, 아래의 방정식을 사용한다:
   $$v_{k+1}(s) = \max_a \left( R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) v_k(s') \right)$$
3. 반복을 진행할수록 최적가치에 더 가까워진다.

그렇다면 왜 가치반복을 진행할수록 $v_k$는 최적가치에 가까워질까? 아래는 이에 대한 증명 과정이다

$\Delta_k = \max_{s} | v^*(s) - v_{k}(s)|$

$\Delta_{k+1} = \max_{s} |v^*(s) - v_{k+1}(s)|$

             $= \max_{s} | \max_{a} q^*(s, a) - \max_{a} q_{k+1}(s, a)| $

             $\leq \max_{s} \max_{a} | q^*(s, a) - q_{k+1}(s, a)| $

---

잠깐 $\max_{s} | \max_{a} q^*(s, a) - \max_{a} q_{k+1}(s, a)|$이 어째서 
$\max_{s} | \max_{a} q^*(s, a) - \max_{a} q_{k+1}(s, a)| \leq \max_{s} \max_{a} | q^*(s, a) - q_{k+1}(s, a)| $
로 전개되는지 설명하겠습니다

$a_1$은 $q^*$에 대해 최적행동 $a_2$는 $q_{k+1}$에 대해 최적행동일 때

case1: $a_1$과 $a_2$가 같은 행동

• 만약 다른 행동$|q^*(s, a) - q_{k+1}(s, a)|$ 이 $|q^*(s, a_1) - q_{k+1}(s, a_2)|$ 보다 작거나 같다면
  $ \max_{s} | \max_{a} q^*(s, a) - \max_{a} q_{k+1}(s, a)| = \max_{s} \max_{a} | q^*(s, a) - q_{k+1}(s, a)| $
• 만약 다른 행동$|q^*(s, a) - q_{k+1}(s, a)|$ 이 $|q^*(s, a_1) - q_{k+1}(s, a_2)|$ 보다 크다면
  $ \max_{s} | \max_{a} q^*(s, a) - \max_{a} q_{k+1}(s, a)| < \max_{s} \max_{a} | q^*(s, a) - q_{k+1}(s, a)| $

case2: $a_1$과 $a_2$가 다른 행동
$A=|q^*(s, a_1) - q_{k+1}(s, a_2)|$, $n$은 양수

• $|a_1 - a_2| \geq 0$
  $|q^*(s, a_1) - (q_{k+1}(s, a_2) - n)| = A+n$
  $| q_{k+1}(s, a_2) - ( q^*(s, a_1) - n)| =???$
• $|a_1 - a_2| < 0$
  $|q^*(s, a_1) - (q_{k+1}(s, a_2) - n)| =???$
  $| q_{k+1}(s, a_2) - ( q^*(s, a_1) - n)| = A+n$

따라서 $\max_{s} | \max_{a} q^*(s, a) - \max_{a} q_{k+1}(s, a)| \leq \max_{s} \max_{a} | q^*(s, a) - q_{k+1}(s, a)| $

 

---

$\Delta_{k+1} \leq \max_{s} \max_{a} | \left( R(s, a) + \gamma \sum_{s'} P(s' \mid a, s)  v^*(s') \right) - \left( R(s, a) + \gamma \sum_{s'} P(s' \mid a, s)  v_k(s') \right)| $

                같은 MDP라면 가치함수가 다르더라도 같은 상태전이확률을 공유하기 때문에       

              $\leq \max_{s} \max_{a} |\gamma \sum_{s'} P(s' \mid a, s) \left(v^*(s') - v_k(s') \right) |$

                삼각부등식을 사용하여

              $\leq \max_{s} \max_{a} \gamma \sum_{s'} P(s' \mid a, s) |v^*(s') - v_k(s')|$

                이때 $ |v^*(s') - v_k(s')| \leq \Delta_k$이므로

              $\leq \max_{s} \max_{a} \gamma \sum_{s'} P(s' \mid a, s) \Delta_k $

$$\therefore \Delta_{k+1} \leq \gamma \Delta_k$$

$0 < \gamma < 1$일 때 가치반복을 진행할수록 최적가치에 가까워진다.

마무리

최적가치는 아래와 같이 표현할 수 있다.

$$ v^*(s) = \lim_{{k \to \infty}}v_k(s)$$

최적가치가 존재하므로 최적정책 역시 존재한다.

추가적으로 최적정책의 정의에 따르면, 환경에 따라 최적정책은 하나가 아닌 여러 개가 존재할 수도 있다. 나는 이 부분에 대해서 실제로 최적정책이 여러 개인 환경이 있다면 해당 정의에 대해 납득할 수 있다고 생각했다.

간단한 그리드 월드(grid world) 문제를 생각해 보자.

그림1

그리드는 2x2크기이며 상하좌우로 한 칸씩 움직일 수 있으며, 이동시 목적지에 도착하면 10의 보상을 그렇지 않을 경우 -1의 보상을 받는다. 이때 1번 정책과 2번 정책은 모두 최적정책이다. 따라서 이 같은 측면에서도 타당하다고 볼 수 있다.