해당 글은 강화 학습의 개념 전반에 대해 순차적으로 다룰 예정입니다.

이번 포스팅에서는 MDP와 더불어 가장 기초가 되는 Bellman 방정식에 대해 다루겠습니다.

Bellman Equation

시점 $t$에서의 가치와 $t+1$에서의 가치 사이의 관계를 나타내는 방정식이다. 따라서 벨만 방정식은 재귀 함수의 형태로 표현되어 있다.

Bellman Expectation Equation

벨만 기대 방정식은 기댓값을 포함한 재귀 함수의 형태로 제시되어 있는 상태 가치 함수를 계산하기 위한 방정식이다.

상태 가치 함수

우선, 시점 $t$에서의 가치를 계산하기 위한 상태 가치 함수는 아래와 같이 정리할 수 있다.

$v_\pi(s_t)=E_\pi[G_t|S_t=s]=E_\pi[r_{t+1}+\gamma r_{t+2} + \gamma^2r_{t+3}+...|S_t=s]\\=E_\pi[r_{t+1} + \gamma v_\pi(s_{t+1})|S_t=s]$

이 때 고려해야 할 점은, 전이 확률 행렬을 통해 알 수 있듯 $t+1$ 시점의 가치를 특정할 수 없기 때문에 $s_{t+1}$이 될 수 있는 모든 상태의 가치에 대한 평균으로 기댓값을 계산해야 한다는 점이다. 또한, 상태 $s$에서의 각 액션에 대한 가치 $q_\pi(s, a)$를 알고 있다면, 상태 가치 함수는 아래와 같이 표현할 수도 있다.

$v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s, a)$

이 식은 각 액션에 대한 가치와 정책 함수를 이용하여 (액션 $a$를 선택할 확률) X (액션 $a$의 가치)의 총합을 통해 상태 $s$의 가치를 판단하는 방식이다. 결국 상태 가치 함수 $v_\pi(s)$는 상태 $s$에서 선택할 수 있는 각각의 액션 $a$의 액션 가치 함수 $q_\pi(s, a)$의 기댓값으로 표현되는 것이다.

액션 가치 함수

반대로 각 상태에 대한 가치 $v_\pi(s)$를 알고 있을 때 액션 가치 함수는 아래와 같이 나타낼 수 있다.

$q_\pi(s, a)=r^a_s + \gamma \sum_{s'\in S}P^a_{ss'}v_\pi(s')$

위 식은 아래의 두 항으로 이루어져 있다.

$r^a_s$ : 보상 함수를 통해 확인할 수 있는 상태 $s$에서 액션 $a$를 수행했을 때 에이전트가 획득하는 보상
$\sum_{s'\in S}P^a_{ss'}v_\pi(s')$ : 액션 $a$를 통해 상태 $s'$로 넘어간 결과 획득할 수 있는 보상의 기댓값

해당 식은 액션 가치 함수 $q_\pi(s, a)$가 해당 액션 $a$의 결과로 넘어갈 수 있는 상태 $s'$의 가치의 기댓값을 의미한다는 사실을 기반으로 도출해낸 식이다. 주의할 점은 상태 가치 함수와는 다르게 액션 가치 함수는 다음 상태의 리턴에 영향을 받기 때문에 감쇠 함수를 사용해 주어야 하며, 상태 $s$의 보상은 액션 $a$가 수행된 직후에 제공되기 때문에 상태 가치 함수에는 없던 $r_s^a$(상태 $s$에서 액션 $a$를 수행했을 때의 보상) 항이 추가가 된다는 점이다. 따라서 가중치(감쇠 함수 $\gamma$)를 반영하여 각 항을 더해주면 위 식과 같이 상태 $s$에서의 액션 $a$의 가치를 계산할 수 있다.

이제 이렇게 얻어낸 두 식을 연립하여 상태 가치 함수 $v_\pi(s)$에 대한 재귀 함수의 형태로 식을 나타낼 수 있다.

$v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s, a) = \sum_{a\in A}\pi(a|s)[r^a_s + \gamma \sum_{s'\in S}P^a_{ss'}v_\pi(s')]$

따라서 처음 처음 정의했던 식과 연립하면 실질적인 기댓값의 계산이 어떻게 수행되는지 알 수 있는데, 이 식을 벨만 기대 방정식이라고 한다.

$v_\pi(s)= E_\pi[r'+\gamma v_\pi(s')]= \sum_{a\in A}\pi(a|s)[r^a_s + \gamma \sum_{s'\in S}P^a_{ss'}v_\pi(s')]$

이 식을 이용해 상태 가치 함수 $v_\pi(s)$를 계산하기 위해서는 정책 함수 $\pi(a|s)$와 전이 확률 행렬 $P^a_{ss'}$에 대해 알아야 한다. 이 값들은 MDP의 환경에 포함되어 있는 값들로, 실제 강화학습을 위해 주어진 환경은 해당 정보가 주어져 있을 수도, 주어지지 않았을 수도 있다. (보통 없는 경우가 더 많다고 보면 된다.) 만약 정책 함수와 전이 확률 행렬이 주어져 있다면, 실질적인 강화학습은 해당 정보와 벨만 기대 방정식을 이용한 시뮬레이션을 통해 수행할 수 있다. (이 방법을 Planning Method라고 한다.) 하지만 이러한 정보들이 주어져있지 않다면 우리는 직접 각각의 상태 및 액션에 대한 확률과 보상을 테스트를 통해 알아내야 한다. (이 방법은 Model-Free Method라고 한다.)

추가적으로, 아까 설명했던 액션 가치 함수 $q_\pi(s, a)$에 상태 가치 함수 $v_\pi(s)$를 대입한 결과식은 아래와 같다.

$q_\pi(s,a)=r^a_s+\gamma \sum_{s'\in S}P^a_{ss'}v_\pi(s')=r^a_s+\gamma \sum_{s'\in S}P^a_{ss'}\sum_{a'\in A}\pi(a'|s')q_\pi(s', a')$

Bellman Optimality Equation

벨만 기대 방정식이 이후의 시점에서 획득할 보상의 기댓값을 기반으로 가치 함수를 정의한 것이라면, 벨만 최적 방정식은 각각의 모든 상태에서의 가치가 최대가 되는 최적 정책 $\pi_*$를 통해 가치 함수를 정의한다.

최적 정책 $\pi_*$에 관한 구체적인 설명은 다음과 같다.

• 주어진 환경의 각각의 상태 $s$ 별로 상태 가치 함수 $v_\pi(s)$가 최대가 되는 정책 $\pi'$이 존재할 것이다.
• 그렇다면, 이렇게 모인 정책 $\pi'$ 중에서 ‘모든 상태에서의 가치가 다른 정책의 가치보다 높은 최적 가치인 정책’이 반드시 존재하고, 그 정책을 최적 정책 $\pi_*$라고 하는 것이다.
  • 이 부분을 납득하는데 어려움이 있었지만, 구체적인 증명은 아직 다룰 수준이 아니기 때문에 일단은 참고 넘어가기로 하겠다.
  • 이 정의를 수식으로 표현하면 아래와 같다.

    $\pi \ge \pi' \ if \ v_\pi(s) \ge v_{\pi'}(s), \ \forall s$

결국, 벨만 최적 방정식은 정책을 최적 정책 $\pi_*$으로 고정시켰을 때의 상태/액션 가치 함수를 정의한 것이다. 이전의 포스팅에서 설명했듯이, 환경에 종속되어 있는 상태 천이 함수 $P_{ss'}^a$와 달리 정책 $\pi$는 agent에 종속되어 있기 때문에 그 값을 변경할 수 있다. 하지만 벨만 최적 방정식에서는 그 정책을 최적 정책 $\pi_*$로 고정함으로써 모든 상황에서의 가치가 최대가 되는 상황을 설정한 것이다.

벨만 최적 방정식으로 나타낸 가치 함수는 다음과 같이 표현할 수 있다.

상태 가치 함수

$v_*(s)=\max_aq_*(s, a)$

벨만 기대 방정식과 비교해보면, $\sum_{a \in A}\pi(a|s)$에 해당하는 부분이 $\max_a$로 변경되었다는 것을 확인할 수 있다.

$\pi_*(a|s)=\lbrace{1 \ \ \ \ if \ a=\arg \max_{a \in A}q_*(s, a) \atop 0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ otherwise\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }$

이는 액션 가치 함수를 최대로 만들기 위한 최적 정책 $\pi_*$의 위의 정의에 의한 변경 사항이다. 해당 정의에 따르면 액션 가치 함수가 최대가 되는 액션을 선택할 확률을 1로 설정하도록 최적 정책이 설정되어 있다는 사실을 확인할 수 있다. 결국, 최적 정책에 의해 특정 상태에서 선택할 수 있는 액션이 하나로 고정되어 있기 때문에 상태 가치 함수를 위와 같이 표현할 수 있는 것이다. 사실 최적 정책이 위처럼 정의되어 있다면 $v_*(s)=q_*(s, a)$로 나타낼 수도 있을 것이라 생각하지만, 아마도 이해와 표현의 편의성 때문에 저렇게 표현한 것이 아닌가 생각한다.

액션 가치 함수

$q_*(s, a)=R_s^a+\gamma \sum_{s' \in S}P_{ss'}^av_*(s')$

액션 가치 함수의 경우, 벨만 기대 방정식과 비교 했을 때 $\pi$가 포함되어 있던 가치 함수의 표현이 최적 가치 함수로 변경되었다는 부분 외에는 변경 사항이 없다는 사실을 확인할 수 있다. 이런 현상은 정책의 변경에 의해 영향을 받는 상태 가치 함수와 달리, 액션 가치 함수는 ‘특정 행동을 했을 때 어떤 상태로 넘어갈 것인가’에 영향을 주는 상태 천이 함수에 영향을 받는 항목이기 때문에 발생한 것이다. 따라서 액션 가치 함수의 경우 벨만 기대 방정식과 비교해서 크게 변경되는 부분은 없다.

벨만 기대 방정식과 마찬가지로 이제 각각의 가치 함수를 자기 자신만으로 표현되는 재귀 함수의 형태로 변형하면 다음과 같이 나타낼 수 있다.

상태 가치 함수

$v_*(s)=\max_a(R_s^a+\gamma \sum_{s' \in S}P_{ss'}^av_*(s'))$

액션 가치 함수

$q_*(s, a)=R_s^a+\gamma \sum_{s'\in S}P_{ss'}^a \max_{a'}q_*(s', a')$

따라서, MDP를 푼다는 것은 이처럼 최적 정책을 찾는다는 것을 의미한다. 즉, 제시된 문제에 해당하는 MDP를 만들고, MDP에 해당하는 최적 정책을 찾음으로써 문제를 해결하는 것이 강화 학습의 목적인 것이다.