마르코프 결정과정으로 문어 (알파카) 키우기

최근에 여름방학 챌린저스 서버가 열리면서 메이플스토리를 다시 플레이하고 있습니다. 지난 겨울에 하다가, 챌린저스 서버가 닫히면서 접었었는데 이번 이벤트는 뉴비로 시작해도 꽤 재밌게 플레이할만 한 것 같습니다.

지난 2월에 메이플스토리에는 “황금문어” 라는 이벤트가 추가되었고, 호응이 좋았는지 이번 여름에 “에버니아 무역왕” 이라고 이름을 바꾸어 재출시되었습니다. 메이플스토리가 항상 그랬지만, 이 이벤트는 확률을 절묘하게 이용해서 떄로는 피가 거꾸로 솟게 만들고, 때로는 그 어느 이벤트보다 도파민 터지게 하는 경향이 있는 것 같습니다.

저로써는 이런 이벤트를 보면, 최적 전략을 생각해보지 않을 수 없습니다. 특히, 이 게임은 강화학습의 바탕이 되기도 하는 마르코프 결정 과정 (Markov Decision Process) 의 굉장히 좋은 예제이기 때문에, 이 포스팅에서는 문어 게임을 따라가면서 MDP에 대해서 알아보고자 합니다.

게임의 규칙

게임의 룰을 먼저 간략히 정리해 보면 아래와 같습니다. (문어와 알파카 이벤트는 본질적으로 똑같기 때문에, 아래에는 일반적인 단어들로 바꾸어 서술합니다)

• 게임은 총 100번의 “라운드” 로 구성되어 있습니다.
• 플레이어는 1레벨에서 시작해서, 최대 9레벨까지 레벨을 올리는 것이 목표입니다.
• 각 레벨에는 정의된 보상 값이 있습니다. 당연히, 레벨이 높을수록 많은 보상이 할당되어 있습니다.
• 각 라운드에서, 플레이어는 다음 두 가지중 하나의 선택을 할 수 있습니다.
  • 레벨업 시도 (이하, “도전” 이라 부르겠습니다): $l$ 레벨에서 레벨업을 시도합니다.
    이때, 가능한 경우의 수로는 성공, 실패, 조난 이 있어서,
    • 성공 시에는 레벨이 1만큼 상승하고
    • 실패 시에는 레벨이 1만큼 하락하고 (단, 2레벨에서는 1레벨로 하락하지 않고, 2레벨을 유지합니다)
    • 조난 시에는 보상 없이 게임이 즉시 종료됩니다.
  • 보상 획득 (이하, “만족” 이라 부르겠습니다): $l$ 레벨에 해당하는 보상을 얻고 게임을 종료합니다.
• 100라운드가 끝날때까지 만족을 택하지 않았다면, 100라운드가 종료되는 시점에서 만족한 것으로 판정합니다.

실제 메이플스토리에는 다음의 두 가지 요소가 더 있으나, 분석에서 크게 중요한 요소는 아닙니다.

• 실제 게임에서는 $l$에서 낮은 확률로 성공 시에 $l+2$로 2레벨 상승합니다. 이 확률은 분석에서 일단 무시하겠습니다.
• 위 서술은 마치 라운드 시도에 비용이 들지 않는 것처럼 쓰여 있지만, 실제 게임에서는 각 라운드를 시도할 때마다 300마리의 몬스터를 더 사냥해야 합니다. 다만, 이 게임을 이렇게 최적전략을 생각하면서 플레이하시는 분들에게 100라운드를 도전하기 위한 3만 1천 마리의 레벨 범위 몬스터 사냥은 가능한 범주에 있기 때문에, 이것도 무시하겠습니다. 그렇게 많은 몬스터를 사냥할수 없다면 100라운드에서 라운드를 줄여서 생각하면 됩니다.

마르코프 결정 과정

이 게임의 최적 전략을 분석하는 것이 자명하지 않은 이유는, 내 행동에 따라 상태가 확률적으로 변화하며, 그 상태의 가치는 내가 미래에 취할 전략에 따라 달라진다는 데 있습니다.

예를 들어, 이 게임을 무조건 100번 도전하는 식으로 플레이한다고 가정해 보겠습니다. 이때 최종 상태를 계산하는 것은 일반적인 마르코프 체인 으로 가능합니다. 상태들 간의 전이확률을 행렬 $P$ 로 나타내고 (시작 상태와 이미 조난당한 상태를 포함하여), 시작 상태의 벡터를 $\mathbf{x} = [1, 0, \dots, 0]$로 쓴 다음, $P^{100} \mathbf{x}$ 를 계산하면 마지막 순간 각 레벨에 있을 확률을 바로 알 수 있습니다. 이를 통해 기댓값도 쉽게 계산할 수 있을 것입니다.

그러나, 내가 위험을 감수할 수 없는 성격이라서 6레벨에서 반드시 만족하는 사람과, 9레벨까지 용맹정진하는 사람에게 있어서는 현재 상황 5레벨이 갖는 가치(보상에 대한 기대)가 다릅니다.

이러한 불확실성 하에서의 의사결정을 모델링하는 방법이 바로 마르코프 결정 과정 (Markov Decision Process) 입니다.

정의

편의 상, 100번의 게임은 항상 끝까지 진행하되, 조난당한 상태에서는 무엇을 하든 빠져나올 수 없다고 생각하면 분석을 쉽게 할 수 있습니다. MDP는 다음과 같이 정의합니다.

\[MDP = (\mathcal{S}, \mathcal{A}, P, R, \gamma)\]

• 상태 $\mathcal{S}$ 는 이 시스템이 존재하는 모든 상태의 집합입니다. 여기서는 레벨 1부터 9까지 아홉개에, 조난당한 상태 (0레벨) 까지 총 10개가 있습니다.
• 행동 $\mathcal{A}$ 는 우리가 취할 수 있는 행동의 집합입니다. 여기서는 도전과 만족이 있습니다.
• 전이 함수 $P: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to [0, 1]$ 은 상태 $s$ 에서 행동 $a$ 를 취했을 때, 상태 $s’$ 로 전이할 확률 $P[s’ \mid s, a]$ 를 의미합니다.
• 보상 함수 $R: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ 은 상태 $s$ 에서 행동 $a$ 를 취했을 때 획득하는 보상입니다. 우리는 여기서, 획득하는 도파민의 양 같은 변수에 현혹되지 않고 엄격하게 게임이 제공하는 보상 (솔 에르다 조각 등) 을 기준으로 합니다. 도전은 보상값이 항상 0이고, 각 상태에서 만족이 주는 보상값만 정의할 수 있습니다.
• 할인 상수 $\gamma \in [0, 1]$는 미래에 얻을 보상을 현재 보상으로 환산하기 위해 곱하는 상수값이나, 우리는 이 게임에서 이 상수를 1로 고정하고 무시할 것입니다.

분석을 쉽게 하기 위해서는, $A$가 두개밖에 없으므로, $P_{도전}$ 과 $P_{만족}$ 이 각각 행렬이라고 생각하면 편합니다. 또한, $R$ 함수는 도전할 때에는 항상 0이고, 만족할 때에만 정의되어 있다고 생각하면 됩니다. 그렇게 하면, 만족 행동은 사실 어떤 보상을 받고 조난 상태 (0레벨) 로 이동하는 것과 동치임을 알 수 있습니다.

각 스텝 $t$ 에서의 상태를 $S_t$, 그때 취하는 행동을 $A_t$ 로 쓰기로 하겠습니다. 이 프로세스의 이름에 마르코프 가 들어가는 것은, 아래 성질을 만족하는 상태를 다루기 때문입니다.

이는, 30번째 라운드에서 내가 4레벨인 상태에서 도전을 누른다면, 그 4레벨이 방금 29번째 라운드에서 5레벨에서 떨어져서 온건지, 3레벨에서 올라와서 온건지가 확률에 영향을 미치지 않아야 한다는 것입니다. ¹

정책과 가치

마르코프 결정 과정에서 우리가 최적화하는 대상은 정책 (Policy) 이라고 부릅니다. Formal하게 쓰면

\[\pi: \mathcal{S} \times \mathcal{A} \to [0, 1]\]

정책 $\pi$ 는 현재 상태 $s$ 에서 어떤 행동 $a$ 를 취할 확률로 정의합니다. 다만, 우리는 이 게임을 확률적으로 플레이하고 싶지는 않으므로, 결정론적인 정책 ($\pi(s, *)$ 가 $(1, 0, 0, \dots)$ 와 같은 one-hot vector) 을 생각할 것입니다. 편의상, 앞으로 이 정책함수를 $\pi(a \mid s)$ 와 같이, $s$ 상태에서 각 행동 $a$ 의 조건부확률로 기술하겠습니다.

우리가 원하는 것은, $\pi$를 적절히 선택하여, 기대되는 보상을 최대화하는 것입니다. 그러기 위해서는 $\pi$ 가 게임에 미치는 영향을 정확히 이해할 필요가 있습니다.

정책 $\pi$ 가 정해져 있다면, 현재 상태 $s$ 에 대해, 다음 상태 $s’$ 의 확률은 다음과 같이 정해집니다.

\[\begin{align*} P[S_{t+1} = s' \mid S_{t} = s] &= \sum_{a \in \mathcal{A}} \textcolor{red}{P[S_{t+1} = s' \mid A_{t} = a, S_t = s]} \times \textcolor{blue}{P[A_t = a \mid S_t = s]} \\ &= \sum_{a \in \mathcal{A}} \textcolor{red}{P[s' \mid s, a]} \times \textcolor{blue}{\pi(a \mid s)} \end{align*}\]

또한, 우리가 상태와 행동에 따른 보상을 정의했으므로, 상태에 대한 보상도 비슷하게 정의할 수 있습니다.

\[R(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) R(s, a)\]

벨만 방정식: 무한 라운드

잠시 편의상, 라운드가 100번이 아닌, 무한히 많이 할 수 있다고 가정해 보겠습니다.

무한히 많은 라운드가 있을 때, 우리가 궁금한 것은 “그래서 내가 지금 5레벨이면, 앞으로 얼마 정도 기대해 볼 수 있는가?” 일 것입니다. 무한히 많은 라운드를 앞으로 플레이한다면 이전에 무슨일이 있었는지는 별로 알 필요가 없고, 상태 $s$의 가치는 여기서 출발해서 정책 $\pi$ 를 따르면 앞으로 얼마의 보상을 기대할 수 있는지에 따라 정해질 것입니다.

\[\begin{align*} V^{\pi}(s) &= \mathbb{E}_\pi \left[\sum_{t = 0}^{\infty} R(S_t, A_t) \mid S_0 = s\right] \end{align*}\]

그런데, $t$ 상태에서의 $S_t$ 가 무엇일지는 $S_0$에서 출발해서 $t$번이나 행동을 거친 이후의 상태이므로 그 확률을 알기 어렵습니다. 다만 이때는 라운드가 무한히 많기 때문에, $V$ 에 대해서 다음의 재귀적 관계가 성립합니다.

\[\begin{align*} V^{\pi}(s) &= \sum_{a \in \mathcal{A}} \pi(a \mid s) \textcolor{blue}{\left(R(a, s) + \sum_{s' \in \mathcal{S}} P[s' \mid s, a] V^{\pi}(s')\right)} \end{align*}\]

즉, $s$에서의 가치는, 이 시점에서 어떤 행동 $a$를 취하는 데 있는데, 행동 $a$를 취하고 나면 소정의 보상 $R(a, s)$ 을 획득함과 동시에 상태가 바뀌며, 그때부터는 또 바뀐 상태 $V^{\pi}(s’)$ 의 보상값이 (얼마인지는 모르지만 정해져 있는) 기대값에 반영된다는 것입니다.

그런데, 저 기댓값 식에서 파란색으로 표시된 부분은 우리가 상태 $s$ 에서 $a$ 라는 행동을 취했을 때의 기대되는 가치라고 해석해 볼 수 있습니다. 그러니까, $s$라는 상태의 가치는 사실 그 상태에서 $a$ 라는 행동을 취할 확률로 그 상태-행동 조합이 갖는 가치를 가중합한, 상태-행동-가치의 기댓값 인 것이죠. 즉,

\[Q^{\pi}(s, a) = R(a, s) + \sum_{s' \in \mathcal{S}} P[s' \mid s, a] V^{\pi}(s')\] \[V^{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) Q^{\pi}(s, a)\]

라고 쓸 수 있고, 이 식을 벨만 방정식 (Bellman Equation) 이라고 부릅니다.

그러면 이제 우리가 원하는 것은 이 상태에서 최적의 가치를 뽑아낼 수 있는 전략 $\pi$를 찾고 싶고, 또 그때 최적의 가치를 얻는 전략 $\pi$ 를 찾고 싶습니다. 이 과정을 최적화하는 여러 알고리즘들이 알려져 있으나, 우리의 현재 관심사는 일단은 아닙니다. 그래도 짧게 생각해보면, 어떤 정책 $\pi$를 하나 잡고, 그 상태에서 $V^{\pi}$ 를 일단 계산해보고, 그렇게 계산된 $V$ 값을 이용해서 $\pi’(a \mid s)$를 최대한 잘 설정하는 $\pi’(a \mid s) = \argmax_a Q^{\pi}(s, a)$ 를 반복하면 뭔가 약간 될 것 같이 느껴집니다.

이 알고리즘을 Policy Iteration 이라고 부릅니다.

벨만 최적 방정식

어떠한 경로로든, 최적의 전략 $\pi^$ 를 이미 알고 있다고 가정해 보겠습니다. 그렇다면, 그 $\pi^$ 하에서 $V$ 나 $Q$의 값은 상태마다 ($Q$의 경우 $(s, a)$ 순서쌍마다) 이제 하나로 정해지게 됩니다. 즉,

\[V^{*}(s) = \sum_{a \in \mathcal{A}} \pi^*(a \mid s) Q^{*}(s, a)\]

그런데 생각해보면, 이때 $\pi^*(a \mid s)$ 는 당연히 최대한 가치가 높은 $a$ 하나에 몰아주는것이 최적일 것입니다.

즉, 최적 상태에서는 다음이 만족되어야 합니다.

\[V^{*}(s) = \max_{a \in \mathcal{A}} Q^{*}(s, a) = \max_{a \in \mathcal{A}} R(a, s) + \sum_{s' \in \mathcal{S}} P[s' \mid s, a] V^{*}(s')\] \[\begin{align*} Q^{*}(s, a) &= R(a, s) + \sum_{s' \in \mathcal{S}} P[s' \mid s, a] V^{*}(s') \\ &= R(a, s) + \sum_{s' \in \mathcal{S}} P[s' \mid s, a] \max_{a' \in \mathcal{A}} Q^*(s', a') \end{align*}\]

이 식을 벨만 최적 방정식 (Bellman Optimality Equation) 이라고도 부릅니다. ²

유한 라운드

유한한 라운드에서는 생각을 달리해야 하는 요소들이 있습니다. 가령, 100번만 할 수 있는 문어 키우기를 처음 시작할 때는 용감하게 5레벨에서 6레벨로 나아가 볼 수 있겠지만, 97번째에서도 똑같이 누를 수 있을까요? 97번째에서는 “도전했다가는 4레벨로 떨어져서, 다시 올라오지 못할” 가능성을 고려히지 않을 수 없을 것입니다.

그렇기 때문에, 유한 시간 MDP는 조금 다르게 접근해야 합니다. 우리는 $t$ 만큼 시간이 남아 있는 상황에서의 가치함수 $V_t^{\pi}$, 그때의 전략 $\pi_t$ 와 같은 것들을 생각할 것입니다. 여기서, $t$가 현재 시간이 아닌, 남은 시간임에 주의하여야 합니다.

일단 가치가 시간에 따라 변한다는 것을 인정하고 나면, 앞서 본 Bellman equation과 비슷하게 재귀적으로 가치를 산정해 볼 수 있습니다. 먼저, 시간에 따라 전략이 바뀌지 않는다면,

\[\begin{align*} \textcolor{red}{V_{t}^{\pi}(s)} &= \sum_{a \in \mathcal{A}} \pi(a \mid s) \left(R(a, s) + \sum_{s' \in \mathcal{S}} P[s' \mid s, a] \textcolor{red}{V_{t-1}^{\pi}(s')}\right) \end{align*}\]

이렇게 쓸 수 있습니다. 그런데 이 문제의 경우 시간에 따라 당연히 전략이 바뀌어야 하므로, 최적 전략을 찾기 위해 우리는 맨 뒤부터 거꾸로 접근합니다.

더이상 할 수 있는 행동이 없을 때 ($t = 0$) 의 최적전략은 자명합니다. 이걸 이용해서 위 벨만 최적방정식처럼 써보면,

\[\begin{align*} \textcolor{red}{V_{t}^{*}(s)} &= \max_{a \in \mathcal{A}} \left(R(a, s) + \sum_{s' \in \mathcal{S}} P[s' \mid s, a] \textcolor{red}{V_{t-1}^{*}(s')}\right) \end{align*}\]

이 식을 만족하는 $V$ 가 최적일 것입니다. 이렇게 최적의 $V$를 구했다면, $Q$를 구하는 것은 자명한 계산이며, $\pi_t^*$ 도 위 식을 최적화하는 $a$를 고르는 것이 항상 최적일 것입니다.

그렇다면, 이 문제는

• 경계값 ($t = 0$) 이 주어져 있고,
• 모든 계산이 $t$를 하나씩 늘려가면서 이전 상태만 참고하여 할 수 있으므로

알고리즘적으로 동적 계획법 (다이나믹 프로그래밍) 을 이용하여 풀 수 있습니다!³ 위 식을 $t = 0$에서 역방향으로 귀납적으로 적용하면, $O(T \abs{\mathcal{S}}^2 \abs{\mathcal{A}})$ 시간에 정확히 풀 수 있습니다.

문어 키우기

다시 문어 (알파카) 키우기로 돌아와 보겠습니다. 편의상 조난상태를 레벨 0이라고 정의합니다. 이하, 확률과 보상값은 2025년 7월 에버니아 이벤트를 기준으로 하겠습니다.
1레벨부터 9레벨까지 각 레벨에서 게임이 종료되었을 때 획득하는 솔 에르다 조각은 다음과 같습니다. ⁴

(0, 1, 3, 6, 10, 15, 25, 150, 500)

$t = 0$ 은 100라운드가 모두 끝난 상황을 의미합니다. 아무것도 할 수 없으므로, 이 값이 곧 $V_0(1)$ 부터 $V_0(9)$ 까지가 됩니다. (조난당한 상태에는 보상이 없으므로 $V_0(0) = 0$까지 생각하면 됩니다)

이제, $t = 1$에서 (이는 99번째 라운드가 끝나고, 100번째 라운드를 시작하기 전을 의미합니다!) 6레벨에서 7레벨을 눌러야 할지 생각해 보겠습니다. 만약 이때 만족 을 선택한다면, 안전하게 15의 보상을 받습니다. 이는 위 재귀식에서 $Q_1(6, 만족) = 15$ 임을 의미하며, 아래와 같이 계산합니다.

• $R(6, 만족) = 15$ 이고,
• $P[0 \mid 6, 만족] = 1$ 이며 (만족 전략은 보상을 받고 조난당하는 것과 동치)
• $V_0(0) = 0$ 이기 때문에, $15 + 1 \times 0$ (그러면 더이상 보상을 기대할 수 없음)

도전의 보상을 계산해 보겠습니다. $V_0(7) = 25$, $V_0(6) = 15$, $V_0(5) = 10$ 이며, 6레벨에서 올라갈 확률은 20.5%, 실패확률은 76.5%, 조난 확률은 3%입니다. 이는 즉,

• $R(6, 도전) = 0$ 이고 (도전은 즉시 보상을 수령하지 않음)
• $P[0 \mid 6, 도전] = 0.03, P[5 \mid 6, 도전] = 0.765, P[7 \mid 6, 도전] = 0.205$ 입니다.
• 따라서, 기대 보상값 $Q_{1}(6, 도전)$ 은 $25 * 0.205 + 10 * 0.765 + 0 * 0.03 = 12.775$ 입니다.

즉, 기회가 한 번 남았는데 6레벨에서 7레벨을 도전해서는 안 된다 라는 것을 알 수 있습니다.

여기서 주목해야 할 점은, 이제 $t = 2$ 를 계산하는 데 있어서는 $V_1(6) = 15$ 를 취한다는 것입니다. 이미 $t = 1$에서 6레벨에 도달한다면 만족하는 것이 옳음을 알기 때문에, 그 뒤의 최적전략은 항상 정해져 있습니다. 이제 “두번 남았는데 5레벨에서 눌러야 하나” 를 계산할 때는, “한번 남고 6레벨에 도달한다면 멈출 것이므로 그 가치가 15” 로 계산하면 된다는 것입니다. 이 부분이 단순 마르코프 체인 계산과 달리 (비록 여기서는 만족이 더 나은 전략이었지만), MDP에서는 “미래에 내가 적절히 잘 판단해서 누른다면” 어떻게 보상을 최적화하는지 알 수 있는 대목입니다.

그래서 눌러요, 말아요?

다음 포스팅에 계속 알아보겠습니다.

---