강화학습 - (10) 벨만 최적 방정식

강화학습

벨만 최적 방정식 (Bellman Optimality Equation)

정책은 에이전트가 어떻게 행동하는지를 결정한다.

어떻게 행동하는지에 대한 정책이 정해져야, 그 뒤에 가치함수가 정의될 수 있다.

강화학습의 목표는 장기적인 보상을 최대로 하는 정책을 찾아내는 것이다.

 

최적 정책

최적의 정책을 찾기 위해서는 하나의 정책이 다른 정책보다 어떻게 나은것인지를 판단할 수 있어야 한다.

다음 그래프는 두개의 정책이 각 상태에서 어떠한 가치를 주는지를 그려놓은 것이다.

 

앞선 상태들이세는 정책 $\pi_1$이 정책 $\pi_2$ 보다 높은 가치를 주고,

뒤 상태들이세는 반대로 정책 $\pi_2$ 이 정책 $\pi_1$ 보다 높은 가치를 준다.

위 그림 만으로는 $\pi_1$가 $\pi_2$보다 낫다는것을 장담할 수 없다.

 

정책 $\pi_1$가 $\pi_2$보다 좋다는 것을 판단하려면, 다음 그림과 같아야 한다.

$\pi_1 \ge \pi_2$를 만족하기 위해서는, $\pi_1$이 모든 상태에 대해 $\pi_2$보다 더 높은 가치를 주어야 한다.

 

최적 정책이란 이 상태들에 대해 다른 어떤 정책보다 더 높은 가치를 주는 정책을 말한다.

어떠한 상태 집합에 대해 최적 정책은 항상 적어도 한가지는 존재하며, 한가지 이상일 수도 있다.

최적 정책은 보통 $\pi_*$로 표기한다.

 

최적 정책이 항상 존재한다는 것이 이해가 되지 않을 수도 있다.

첫번째 그래프를 볼 때, 정책 $\pi_1$은 앞선 상태들에서 더 가치가 높고, $\pi_2$는 반대이다.

만약 새로운 정책 $\pi_3$를 정의하고, 앞선 상태들에선 $\pi_1$를 따르고, 뒤 상태들에서는 $\pi_2$를 따르게 한다면,

$\pi_3$은 두가지 정책들보다 더 나은 정책이라고 말할 수 있을 것이다.

따라서 어떠한 상태 집합에 대해서는 항상 최적의 정책이 존재할 수 밖에 없게 된다.

 

예제)

다음과 같은 두가지 케이스의 MDP가 존재한다:

 

위 두가지 정책들 중 어떠한 정책이 최적이냐고 묻는다면, 이는 감가율 $\gamma$에 달려있다.

만약 $\gamma = 0$이라면, 에이전트는 가장 가까운 보상만을 고려하게 된다.

따라서 이는 다음과 같은 결과를 낳게 된다:

$v_{\pi_1}(X) = 1$

$v_{\pi_2}(X) = 0$

이 경우라면 $\pi_1$이 최적 정책이 된다.

 

만약 $\gamma = 0.9$라면, 에이전트는 미래의 보상까지 고려하게 된다.

따라서 이는 다음과 같은 결과를 낳는다:

$v_{\pi_1}(X) = \sum_{k=0}^{\infty} (0.9)^{2k} \approx 5.3$

$v_{\pi_2}(X) = \sum_{k=0}^{\infty} (0.9)^{2k+1} * 2 \approx 9.5$

이 경우에는 $\pi_2$가 최적 정책이 된다.

 

반응형

 

최적 가치

최적 상태 가치 벨만 방정식 (state-value Bellman optimality equation)

최적 정책을 따라서 행동하면, 그 결과로 최적 가치를 얻게 된다.

최적의 상태가치함수는 다음과 같이 정의될 수 있다.

$v_* = max_{\pi} v_{\pi}(s)$

 

앞선 포스팅에서 정의한 상태 가치 벨만방정식을 다시 살펴보자.

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

 

이 수식에 최적 정책과 최적 상태 가치를 대입하면 다음과 같이 재정의 될 수 있다.

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

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

 

두번째 최적 수삭을 다시 살펴보면, 최적 정책 $\pi_*(a|s)$가 수식에서 사라진 것을 볼 수 있다.

이는 최적의 상태가치는 최적 정책에 의해 선택된 하나의 행동에 의해서 정의되기 때문이다.

이를 다른말로 표현하면, 최적의 상태가치는 최적의 정책을 따라서만 얻을 수 있다는 의미이다.

 

최적 행동 가치 벨만 방정식 (state-value Bellman optimality equation)

최적의 행동가치함수는 다음과 같이 정의될 수 있다.

$q_* = max_{\pi} q_{\pi}(s, a)$

 

역시 앞선 포스팅에서 언급한 행동 가치 벨만방정식을 살펴보자.

$q_{\pi}(s,a) = \sum_{s'} \sum_{r}p(s',r|s,a)\left[r+\gamma \sum_{a'} \pi(a' | s') q_{\pi}(s', a')\right]$

 

이 수식에 최적 정책과 최적 행동 가치를 대입하면 다음과 같이 재정의 될 수 있다.

$q_*(s,a) = \sum_{s'} \sum_{r}p(s',r|s,a)\left[r+\gamma \sum_{a'} \pi_*(a' | s') q_*(s', a')\right]$

$q_*(s,a) = \sum_{s'} \sum_{r}p(s',r|s,a)\left[r+\gamma max_{a'} q_*(s', a')\right]$

 

위 수식에서 역시 최적의 행동 하나만을 고려하기 때문에 정책이 사라지고, 가장 가치있는 행동만이 남아있게 된다.

 

최적 가치에서 최적 정책으로

최적 가치와 최적 정책의 관계는 매우 심플하다.

최적의 정책은 곧 가치가 최대가 되는 행동을 고르면 되기 떄문이다.

 

최적 가치가 다음과 같이 최대의 가치를 주는 행동에서 나온다면,

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

 

최적 정책은 그저 최적 가치가 최대로 되는 행동을 고르기만 하면 되는 것이다.

이를 강화학습에서는 $argmax$ 라는 함수를 사용한다.

$argmax$를 함수로 표현하면 $f(x)$가 최대가 되는 $x$를 반환하는 것이다.

따라서 최적정책을 수식화 하면 다음과 같이 표현할 수 있다.

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