강화학습 : MDP와 벨만 방정식

March 20, 2022, 11:14 p.m.

이번 포스트에서는 강화학습의 아주 기초가 되는 개념들에 대해서 알아보려고 합니다.

강화학습은 순차적으로 어떤 행동을 결정해야 하는 문제를 푸는 알고리즘 입니다. 이것을 순차적 행동 결정 문제라고 합니다. 알파고가 해낸 바둑도 순차적 행동 결정 문제에 해당하죠.

강화학습으로 구현을 하려면 먼저 순차적 행동 결정 문제를 수학적으로 표현해야합니다. 수학적으로 표현한 이것을 마르코프 결정 과정, MDP라고 합니다. 이번 포스트에서는 MDP를 수학적으로 표현하는 개념들, 그리고 벨만 방정식에 대해서 알아보겠습니다.

1. MDP의 구성 요소

MDP는 행동의 주체인 에이전트, 상태(S), 행동(A), 보상(R), 정책(P)로 구성됩니다. 앞으로는 편의를 위해 영어 약자를 사용하겠습니다.

상태, S 란 에이전트의 정보입니다. 에이전트의 위치, 속도와 같은 상태정보, 그리고 에이전트가 관찰하는 정보(주변 물체의 위치, 바둑판의 바둑알 배열) 등이 있습니다.

행동, A 이란 에이전트가 어떠한 S에서 취할 수 있는 행동입니다. 상하좌우의 움직임이나 바둑돌을 어느 위치에 놓는 행위등이 될 수 있겠습니다.

보상 R 이란 에이전트의 행동으로 인해 얻게되는 결과물로써 에이전트가 학습하게 되는 대상입니다. 즉, 에이전트는 시간에 따라서 얻는 보상을 최대로 하는 방법을 찾는 것이 목적입니다.

정책 P란 MDP에서 궁극적으로 구해야 하는 답입니다. 에이전트는 P에 따라서 특정 S에서 어떤 A를 하게 됩니다. 제일 좋은 P는 최적 정책이라고 하며 에이전트는 이때 최대의 보상을 얻을 수 있습니다.

2. MDP의 수학적 표현

위에서 알아본 MDP의 각 요소들이 수학적으로 자세히 어떤 의미를 가지는지 살펴보도록 하겠습니다.

1) 상태 S

5X5의 격자라는 환경이 있고 에이전트는 각 좌표를 움직여 다닌다고 생각을 해보겠습니다. 그러면 상태 S는 격자의 각 좌표가 됩니다. 총 25개의 S가 존재하네요.

에이전트가 (4,3)에 있다면 에이전트의 현재 S는 (4,3)이 되는 것입니다.

2) 보상함수 r(s,a)

보상함수는 에이전트가 학습하는 유일한 대상입니다. 어떤 시간 t에서 상태는 $S_t = s$일때 행동을 $A_t = a$ 로 했을 때 받을 보상에 대한 기대값입니다. 기대값이라는 것은 평균을 의미하는데 왜냐하면 에이전트는 여러 요인에 의해서 같은 상태에서 같은 행동을 했는데도 보상을 다르게 받을 수 있기 때문입니다. 아래의 식으로 표현됩니다.

$$r(s,a) = E[R_{t+1} | S_t = s, A_t = a]$$

$R_{t+1}$인 이유는 t일 때 에이전트가 해당 행동을 한 뒤에 환경이 보상을 알려주는 것이기 때문입니다.

3) 상태 변환 확률 $P_{ss'}^a$

상태변환 확률이란 상태 s에서 에이전트가 해당 행동을 했을 때 다음 상태 s`로 이동할 확률입니다. 아래와 같이 표현합니다.

$$P_{ss'}^a = P[S_{t+1} = s' |S_t = s, A_t = a]$$

이 또한 에이전트는 이 정보를 모르고 에이전트가 해당 행동을 하면 환경은 환경의 상태 변환 확률에 의거해 에이전트의 다음 상태를 알려줍니다.

4) 할인율 $\gamma$

보상은 나중에 받는 것일 수록 가치가 줄어듭니다. 이를 고려하기 위해 할인율 $\gamma$을 도입하였습니다. 0에서 1사이의 값이며 가장 최근에 받은 보상은 그대로지만 시간 k가 지난 뒤에 받은 보상은 $\gamma^{k-1}R_{t+k}$로 표현됩니다. 즉 k-1만큼 할인되어 적용된다는 뜻이 되겠습니다.

5) 정책 $\pi(a|s)$

정책이란 앞서 말했듯이 어떤 상태 s에서 에이전트가 할 행동을 말합니다. 상태 s를 집어넣으면 행동 a가 나오는 일종의 함수입니다. 쉽게 말해서 각 행동을 할 확률을 반환합니다.

아래의 식으로 나타냅니다.

$$\pi(a|s) = P[A_t = a | S_t = s]$$

위의 식을 보면 알 수 있듯이, 시간 t에서 에이전트의 상태 $S_t = s$ 일때 에이전트가 $A_t = a$ 라는 행동을 할 확률을 나타냅니다.

이처럼 MDP를 통해 순차적 행동 결정 문제를 정의해 보았습니다. 에이전트는 현재 상태에서 정책에 의거해서 다음 행동을 하고, 환경은 에이전트에게 행동으로 인한 보상과 에이전트의 다음 상태를 알려주게 됩니다.

3. 가치 함수

에이전트는 위에서 정의한 MDP대로 가장 많은 보상을 받을 최적 정책을 학습하면 됩니다. 에이전트는 어떻게 이 최적 정책을 학습할 수 있을까요?

바로 행동을 통해 어떠한 상태에 도달했을 때 받을 보상에 대한 기대값, 즉 가치가 최대가 되도록 정책을 발전시켜 나가면 됩니다.

가치란 무엇일까요?

에이전트는 행동을 통해 다음 상태로 가고, 또 다음상태로 가고 계속해서 다음 상태로 이동하면서 마지막 상태에 도달할때 까지 이동하면서 보상을 받습니다. 이 보상들을 모두 더하면 에이전트가 해당 행동을 통해 얻을 보상의 반환값 R이 됩니다.

이때 가장 가까운 시점에 받는 보상이 나중 시점에 받는 보상보다 중요하기 때문에 각 보상에 할인율을 곱해서 더해서 반환값을 구합니다.

그리고 이 반환값 G 에 대한 기댓값이 바로 그 상태 s에 대한 가치 v가 됩니다. 아래와 같은 수식으로 나타낼 수 있겠네요.

$$v(s) = E[G_t|S_t = s]$$

즉 가치함수는 상태를 입력받고 이에 해당하는 받을 보상의 총 합인 가치를 반환하는 함수입니다.

그런데 여기서 현재 상태와 다음 상태의 관계를 생각해 볼까요?

현재 상태의 가치는 다음 상태로 갈때 받을 보상과 다음 상태의 가치에 할인율을 한번 곱한값과 같습니다.

그렇기 때문에 아래와 같이도 표현을 할 수 있겠군요!

$$v(s) = E[R_{t+1} + \gamma v(S_{t+1})|S_t = s]$$

그리고 이 가치함수는 궁극적으로 에이전트의 정책 $\Pi$에 따라 결정되는 보상에 의해 결정되기 때문에 첨자로 명시해 주는 것이 좋겠네요.

$$v_\pi(s) = E_\pi[R_{t+1} + \gamma v_\pi(S_{t+1})|S_t = s]$$

이것이 바로 현재 상태의 가치함수와 다음 상태의 가치함수간의 관계를 나타내는 벨만 기대 방정식입니다.

4. 큐 함수

가치 함수는 상태에 대한 보상의 합을 출력하는 함수입니다. 에이전트는 주변의 이동할 수 있는 상태들 중 가치함수가 가장 큰 상태로 이동하려고 할 것입니다.

그러나 에이전트가 그 상태로 이동하기 위한 행동을 행하는 과정에서 상태 변환 확률이 매우 낮아서 갈 확률이 낮다거나 하는 경우가 있어 오히려 그럴 바에 가치 함수가 조금 낮은 다른 상태로 이동하는 것이 사실 나을 수도 있습니다.

즉 상태의 가치를 판단하기 보다는 어떤 상태에서 에이전트가 행하는 행동에 대한 가치를 판단하는 것이 훨씬 실리적이라고 볼 수 있습니다.

바로 이 행동에 대한 가치, 즉 어떠한 상태 s에서 에이전트가 a라는 행동을 했을 때의 가치를 나타내는 함수를 큐함수라고 부릅니다.

큐함수도 벨만 기대 방정식의 형태로 나타내 볼 수가 있습니다.

$$q_\pi(s,a) = E_\pi[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]$$

큐함수는 다음 상태에서의 큐함수에 할인율을 곱한 값과 보상을 더한 값의 기대값으로 나타낼 수 있습니다.

가치함수는 그 상태에서의 받을 보상의 합인데, 큐함수는 그 상태에서 어떠한 행동을 했을 때의 보상을 의미합니다. 즉, 해당 상태에서의 가능한 모든 행동의 큐함수와 그 행동을 할 확률(정책)을 곱해서 모두 더하면 그 상태의 가치함수가 됩니다.

가치함수와 큐함수의 관계를 나타낸 식입니다.

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

5. 벨만 기대 방정식

위에서 가치함수와 큐함수의 벨만 기대 방정식 형태를 살펴보았습니다. 해당 방정식의 해가 바로 어떤 정책 $\pi$를 따랐을 때의 참 가치함수와 참 큐함수입니다.

계산하기 위해서는 벨만 기대 방정식을 조금 더 계산이 가능한 형태로 바꾸어 주어야 합니다. 아래와 같이요.

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

이 방정식의 해 $v_\pi$를 한번에 구할 수는 없습니다. 무한대의 이터레이션을 통해서 $v_\pi$의 수렴값을 구할 수 있는데 이것이 바로 이 방정식의 해 $v_\pi$, 즉 참 가치함수입니다.

이터레이션을 어떻게 진행할까요? 먼저 $v_\pi$ 를 모든 상태 s에 대해서 0으로 초기화 합니다. 즉 $v_0(s) = 0$ 입니다. 그 다음 1번째 이터레이션 때 모든 상태 s에 대해서 위의 식의 우변을 계산한 뒤 $v_1(s)$ 에 대입해줍니다. 그다음 정책을 업데이트 해주고 다시 이터레이션을 진행하여 이것을 수렴할때까지 반복해 줍니다. 자세한 내용은 정책 이터레이션에서 자세히 알아보겠습니다.

k번째 이터레이션과 k+1번째 이터레이션의 가치함수의 관계는 아래와 같습니다.

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

이것을 반복하다보면 $v_{k+1}$은 수렴하게 되며 이것이 $v_\pi$, 즉 참 가치함수가 됩니다.

6. 벨만 최적 방정식

위에서 벨만 기대 방정식을 통해서 어떤 정책 $\pi$를 따랐을 때의 참 가치함수를 구하는 방법을 알아보았습니다. 즉 어떤 정책의 가치를 구할 수 있는 것입니다.

에이전트는 이것을 바탕으로 자신의 정책을 수정해 나가야합니다. 그래서 결국 가장 최대의 가치함수를 항상 얻는 최적 정책을 얻어야합니다.

그리고 이 최적 정책을 바탕으로 구한 참 가치함수가 최적 가치함수가 되는 것입니다. 그리고 큐함수도 마찬가지입니다.

최적 가치함수와 최적 큐함수를 각각 $v_*(s)$ $q_*(s,a)$ 라고 한다면 참 가치함수와 최적의 가치함수간의 관계는 아래와 같이 정의됩니다.

$$v_*(s) = max[v_\pi(s)]$$ $$q_*(s,a) = max[q_\pi(s,a)]$$

즉 수많은 정책으로 얻을 수 있는 참 가치함수들 중에서 가장 큰 것이 최적 가치함수가 되는 것입니다.

이렇게 가장 높은 가치함수나 큐함수를 에이전트가 찾았다고 생각해봅시다. 이때의 최적 정책은 각 상태 s의 최적 큐함수 중에서 가장 큰 큐함수에 해당하는 행동을 하면 되는 것입니다. 이것이 이 에이전트의 최적 정책$\pi_*(s,a)$이 됩니다.

최적 가치함수와 최적 큐함수의 관계는 어떻게 될까요? 현재 상태의 가치함수가 최적이라는 것은 에이전트가 가장 최적의 행동, 즉 가장 큰 최적 큐함수를 선택한다는 뜻입니다. 즉 현재상태에서 최적 가치함수는 에이전트가 현재 상태에서 얻을 수 있는 최적 큐함수 중에서 가장 큰 값을 취하면 됩니다.

$$v_*(s) = max[q_*(s,a)|S_t = s, A_t = a]$$

이것을 큐함수를 가치함수로 바꾸어서 표현하면 아래의 수식이 됩니다. E가 붙는 이유는 위에서 설명했듯이 상태변환 확률에 의해서 다음 상태가 여러가지일 수 있기 때문입니다.

$$v_*(s) = maxE[R_{t+1} + \gamma v_*(S_{t+1}) | S_t = s, A_t = a]$$

이것이 바로 벨만 최적 방정식입니다. 현재 상태와 다음 상태의 최적 가치함수간의 관계를 나타내죠.

아래처럼 큐함수로도 벨만 최적 방정식을 표현할 수 있습니다.

$$q_*(s,a) = E[R_{t+1} + \gamma max q_*(s_{t+1},a') | S_t = s, A_t = a]$$

7. 마무리

이번 포스트에서는 강화학습의 기초와 기반이 되는 MDP와 벨만 방정식의 구성 요소에 대해서 알아보았습니다. 다음 포스트에서는 본격적으로 강화학습을 적용하기 전에 벨만 기대 방정식과 벨만 최적 방정식의 개념을 적용해서 간단한 MDP 문제를 푸는 예시를 보여드리겠습니다.

이러한 개념들을 잘 알아두면 나중에 강화학습을 직접 적용하고 응용할때 훨씬 도움이 되리라 생각됩니다!

MDP 강화학습