Woojae Joo ursonice

[3차시] Markov Decision Process

작성 2026년 7월 14일수정 2026년 7월 18일

서론

평균보상에는 한계가 있었다. 에르고딕성이라는 강한 조건이 필요하고, 종료 상태가 존재하는 문제에서는 종료 이전의에 받은 보상이 무한한 시간 속에서 영향력이 점차 사라진다. 결국 보상을 '얼마나' 받았는지뿐 아니라 '언제' 받았는지까지 반영하는 새로운 평가 방식이 필요하다.

이번 시간에는 이 요구를 만족하는 할인보상(Discounted Reward) 방식을 도입한다. 미래의 보상일수록 가치를 일정 비율로 줄여서 더하면, 종료되는 문제와 종료되지 않는 문제를 하나의 기준으로 평가할 수 있고 이른 보상을 선호하는 성질도 자연스럽게 얻어진다.

그리고 이 기준 위에서 각 상태가 얼마나 좋은지를 나타내는 상태가치함수도 함께 정의해본다. 먼저 행동이 없는 단순한 구조인 MRP(Markov Reward Process)에서 가치함수와 벨만 방정식을 유도하고, 여기에 행동 선택을 추가한 MDP(Markov Decision Process)로 확장한다.

목차

  • Return Function
  • MRP
  • State Value Function
  • Bellman Equation
    • Example: Sunny–Cloudy MRP의 가치 계산
  • MDP
  • Action Value Function

Return Function

평균보상 방식의 한계를 살펴보면서 종료되는 문제에서는 정책을 평가하는 기준을 다르게 생각할 필요가 있음을 확인했다.

예를 들어 로봇이 목표 지점에 도달하면 과제가 끝나는 문제라면,시점 t 이후에 받는 보상이

\[R_{t+1}, R_{t+2}, R_{t+3}, \dots\]

라면 이를 단순히 더하면

\[R_{t+1}+R_{t+2}+R_{t+3}, \dots\]

된다.

종료 시점이 명확한 에피소드형 문제에서는 보상이 유한개만 존재하므로 이 합을 그대로 사용할 수 있다. 그러나 공장 제어, 서버 운영, 로봇의 지속적인 이동처럼 종료되지 않는 문제에서는 보상이 끝없이 발생한다. 이때 보상을 단순히 더하면 합이 무한히 커질 수 있다.

예를 들어 매 스텝 보상 1을 받는다면

\[1 + 1 + 1 + \dots = \infty\]

가 되어 정책의 성능을 유한한 값으로 표현할 수 없다.

따라서 종료되지 않는 문제에서도 미래 보상의 합을 안정적으로 계산할 수 있도록 가중치를 부여한다.

\[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \dots\]

이를 할인된 보상의 합 return function이라고 하며 \(G_t\)로 표현한다.

\[G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}=R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots\]

여기서 \(\gamma\)를 Discount Factor라고 한다.

Discount Factor

\(\gamma\)는 미래의 보상을 현재 시점에서 얼마나 중요하게 평가할지를 결정한다.

\(\gamma\)가 작으면 가까운 보상을 중요하게 평가한다.

\[\gamma \approx 0\]

반대로

\[\gamma \approx 1\]

이면 먼 미래의 보상도 비교적 중요하게 고려한다.

discount factor(할인율)은 일반적으로 \(0 \leq \gamma <1\)의 값을 사용한다.

Return Function의 재귀적 구조

이는 이후 증명에서 많이 다뤄짐으로 return function을 아래처럼도 표기가능하다는 점을 알아두자.

\[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \dots\]

첫 번째 보상 \(R_{t+1}\)을 제외한 나머지항에서 \(\gamma\)를 묶으면

\[G_t = R_{t+1} + \gamma ( R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \dots )\]

가 된다.

그런데 괄호 안의 식은 시점 t+1부터 시작한 return function이다.

\[G_{t+1} = R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \dots\]

따라서

\[G_t = R_{t+1} + \gamma G_{t+1}\]

이라는 관계를 얻는다.

이 수식의 의미는 현재 시점부터 얻게 될 전체 미래 누적 보상 합은 바로 다음에 받는 보상과, 다음 시점부터 얻게 될 그 이후의 상태부터의 할인된(discounted) 미래 누적 보상 합이다.

Markov Reward Process(MRP)

Return function으로 부터 전체 할인된 보상을 계산하려면 두 가지 정보가 필요하다.

첫째, 현재 상태에서 다음 한 스텝 동안 평균적으로 얼마의 보상을 받는지 알아야 한다.

둘째, 다음에는 어떤 상태로 이동하는지 알아야 한다. 다음 상태가 달라지면 그 이후에 받게 될 미래 보상도 달라지기 때문이다.

그런데 이 두 정보는 지금까지 공부한 마르코프 체인에 보상과 할인율을 추가하면 표현할 수 있다.

Markov Chain \(\langle \mathcal{S}, \mathcal{P} \rangle\)에 두 가지를 추가한다:

\[\text{MRP} = \langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \rangle\]
  • \(\mathcal{S}:\) state space - \(\mathcal{S}=\{s_1, s_2, ...,s_n\}\)
  • \(\mathcal{P}:\) transition Matrix
    • transition probability: \(P_{ss'}= P(S_{t+1}=s'|s_t=s)\)
  • \(\mathcal{R}:\) reward function - 보상 함수로 상태 s에 도달하면 받는 점수 \(r(s) = \mathbb{E}[R_{t+1} \mid S_t = s]\)
  • \(\gamma :\) discount factor(할인율)

평균보상 방식에서는 정책 \(\pi\)가 반영된 전이확률을 다뤘다. 그래서 P밑에 첨자에 정책 \(\pi\)가 붙어있는 것이다.

\[P_\pi(s' | s) = \sum_{a} \pi(a | s) P(s' | s, a)\]

그러나 MRP에서는 정책이 반영되지 않는 전이확률을 다루고 정책이 반영된 것은 MDP에서 다룬다.

상태별 기대보상

MRP에서 상태별 기대보상은 아래와 같다.

\[r(s) = \mathbb{E} [ R_{t+1} \mid S_t = s ]\]

상태가치 함수

  • 이전 평균보상방식은 \(g_{\pi}\)까지 배웠고 평균보상방식의 상태가치함수까지 다루진 않았다.
  • 왜냐하면 강화학습에서는 거의 사용되지 않기 때문이다. 그래서 왜 \(G_t\)라는 할인형 보상함수가 등장했는지에 대한 이야기를 위해 언급한 부분이였다.
  • 이 이야기를 하는 이유는 \(g_{\pi}\)와 상태가치함수를 비교하려 한다면 헷갈릴까봐이다.
  • \(g_{\pi}\)와 비교대상은 \(G_t\)이지 상태가치함수가 아니다

이제 위에서 배운 내용을 바탕으로 각 상태가 장기적으로 얼마나 좋은지 평가해보자.

시점 t부터 얻게 될 return function(할인수익)은 \(G_t\)는 같은 상태에서 출발하더라도 이후에 어떤 상태로 전이되는지에 따라 받는 보상이 달라지기 때문에 항상 같은 값을 가지지 않는다.

따라서 여러 \(G_t\)에 대하여 평균을 내어 상태의 가치를 평가한다.

\[V(s) = \mathbb{E} [ G_t \mid S_t = s ]\]

현재 상태 s에서 출발하여 MRP의 상태전이 확률을 따랐을 때, 앞으로 얻게 될 전체 할인수익의 평균이다.

상태별 기대보상 vs 상태가치 함수

상태별 기대 (즉시)보상

\[r(s) = \mathbb{E} [ R_{t+1} \mid S_t = s ]\]

현재 상태 s에서 바로 다음 한 스텝 동안 받을 보상의 평균이다.(다음 한 스텝만 평가)

상태가치함수

\[V(s) = \mathbb{E} [ G_t \mid S_t = s ]\]

는 현재 상태 s에서 시작해 앞으로 받게 될 모든 할인보상의 평균이다.(현재부터 미래 전체를 평가)

현재 즉시보상이 높은 상태라고 해서 반드시 가치가 높은 상태인 것은 아니다. 현재 보상은 크더라도 이후 매우 나쁜 상태로 이동한다면 V(s)는 낮을 수 있다.

반대로 현재 보상은 작더라도 이후 보상을 지속적으로 얻는 상태로 연결된다면 V(s)는 높을 수 있다. 즉, 상태가치함수는 현재 상태의 즉시적인 좋음뿐 아니라 그 상태가 어떤 미래로 이어지는지까지 평가한다.

Bellman Equation

V(s)는 현재 상태가 s일 때 앞으로 얻게 될 할인수익 \(G_t\)의 기댓값이다.

그런데 이를 그대로 계산하려면 상태 s에서 출발하여 발생할 수 있는 모든 미래 경로를 고려해야 한다. 상태전이가 반복될수록 가능한 경로의 수는 계속 증가하므로, 무한한 미래의 보상을 직접 나열하여 계산하는 것은 현실적으로 어렵다.

이를 해결하기 위해 앞서 확인한 할인수익의 재귀 구조를 이용한다.

\[G_t = R_{t+1} + \gamma G_{t+1}\]

이 식은 현재부터의 전체 할인수익을: 다음 한 스텝의 보상 + 다음 시점부터의 할인수익

으로 나눠 표현해 무한한 미래를 한꺼번에 계산하는 대신 다음 한 스텝과 다음 상태 이후의 가치문제로 줄여나간다.

상태가치함수

\[V(s) = \mathbb{E} [ G_t \mid S_t = s ]\]

여기에

\[G_t = R_{t+1} + \gamma G_{t+1}\]

를 대입하면

\[V(s) = \mathbb{E} \left[ R_{t+1} + \gamma G_{t+1} \mid S_t = s \right]\]

이 된다.

기댓값의 선형성에 의해 두 항을 나누면

\[V(s) = \mathbb{E} \left[ R_{t+1} \mid S_t = s \right] + \gamma \mathbb{E} \left[ G_{t+1} \mid S_t = s \right]\]

이다.

첫 번째 항은 앞에서 정의한 상태 s의 즉시 기대보상이다.

\[r(s) = \mathbb{E} [ R_{t+1} \mid S_t = s ]\]

따라서

\[V(s) = r(s) + \gamma \mathbb{E} \left[ G_{t+1} \mid S_t = s \right]\]

가 된다.

두 번째 항에 대해서 좀 더 봐보면

\[\mathbb{E} [ G_{t+1} \mid S_t = s ]\]

은 이중 기댓값의 법칙에

\[\mathbb{E}[X \mid Z] = \mathbb{E}\left[ \mathbb{E}[X \mid Y, Z] \mid Z \right]\]

에 따라 \(X=G_{t+1},\;Y=S_t,\; Z=S_{t+1}\) 이라해보자

\[\begin{align} \mathbb{E} \left[ \underbrace{G_{t+1}}_{X} \ \middle|\ \underbrace{S_t = s}_{Y} \right]=\mathbb{E} \left[ \mathbb{E} \left[ \underbrace{G_{t+1}}_{X} \ \middle|\ \underbrace{S_t = s}_{Y}, \underbrace{S_{t+1} = s'}_{Z} \right] \ \middle|\ \underbrace{S_t = s}_{Y} \right]\end{align}\]

\(G_{t+1}\)은 Time-step이 t+1임으로 \(S_{t}\)에는 영향을 받지 않는다.

\[\mathbb{E} \left[ G_{t+1} \mid S_t = s, S_{t+1} = s' \right] = \mathbb{E} \left[ G_{t+1} \mid S_{t+1} = s' \right]\]

따라서

\[\begin{align} \mathbb{E} \left[ G_{t+1} \ \middle|\ S_t = s \right] = \mathbb{E} \left[ \mathbb{E} \left[ G_{t+1} \ \middle|\ S_{t+1} = s' \right] \ \middle|\ S_t = s \right] \end{align}\]

되고 상태가치 함수의 정의에 의해

\[\mathbb{E} \left[ G_{t+1} \mid S_t = s \right] = \mathbb{E} \left[ \underbrace{\mathbb{E} \left[ G_{t+1} \mid S_{t+1} = s' \right]}_{V(S_{t+1})} \ \middle|\ S_t = s \right]\]

된다.

이므로

\[\begin{align} \mathbb{E} \left[ G_{t+1} \ \middle|\ S_t = s \right] &= \mathbb{E} \left[ V(S_{t+1}) \ \middle|\ S_t = s \right] \\[5pt] \mathbb{E} \left[ X \ \middle|\ Y=y\right] &= \sum_{x}x\cdot P(X=x \ \mid Y=y) \\[5pt] &= \sum_{s' \in S} V(S_{t+1}) P(S_{t+1} = s' \mid S_t = s) \\[10pt]&= \sum_{s' \in S} P_{ss'} V(s') \end{align}\]

가 되어 최종적으로

\[V(s) = r(s) + \gamma \sum_{s' \in S} P_{ss'} V(s')\]

가 되어 이를 MRP의 Bellman Equantion이라고 한다.

이 식의 의미는 현재 상태의 가치는 기대 즉시 보상과 할인된 다음 상태 가치의 기댓값을 말한다.

Example: Sunny–Cloudy MRP의 상태가치 계산

앞에서 사용한 Sunny–Cloudy 마르코프 체인에 할인율만 추가하여 각 상태의 가치 V(s)를 계산해보자.

이때 할인율 \(\gamma=0.9 =\frac{9}{10}\)

상태전이 행렬과 보상은 2차시의 예제와 동일하게 사용한다.

상태공간은

\[S = \{\text{Sunny}, \text{Cloudy}\}\]

이고, 상태전이행렬은

\[\mathcal{P} = \begin{pmatrix} \displaystyle\frac{2}{3} & \displaystyle\frac{1}{3} \\[1.5em] \displaystyle\frac{1}{2} & \displaystyle\frac{1}{2} \end{pmatrix}\]

다음 상태가 Sunny에 도달하면 보상 1, Cloudy에 도달하면 0을 받는다고 하였으므로

현재 상태가

\[\begin{align*}r(\text{Sunny}) &= \sum_{s' \in \mathcal{S}} r(s') P(S_{t+1} = s' \mid S_t = \text{Sunny}) \\[8pt]&= r(\text{Sunny}) P(S_{t+1} = \text{Sunny} \mid S_t = \text{Sunny}) \\[5pt]&\quad +r(\text{Cloudy}) P(S_{t+1} = \text{Cloudy} \mid S_t = \text{Sunny}) \\[8pt]&= 1 \cdot \frac{2}{3} + 0 \cdot \frac{1}{3} \\[8pt]&= \frac{2}{3}\end{align*}\]

현재 상태가

\[\begin{align*}r(\text{Cloudy}) &= \sum_{s' \in \mathcal{S}} r(s') P(S_{t+1} = s' \mid S_t = \text{Cloudy}) \\[8pt]&= r(\text{Sunny}) P(S_{t+1} = \text{Sunny} \mid S_t = \text{Cloudy}) \\[5pt]&\quad + r(\text{Cloudy}) P(S_{t+1} = \text{Cloudy} \mid S_t = \text{Cloudy}) \\[8pt]&= 1 \cdot \frac{1}{2} + 0 \cdot \frac{1}{2} \\[8pt]&= \frac{1}{2}\end{align*}\]

정리하면

\[\begin{align*}r(\text{Sunny}) &= \frac{2}{3} \cdot 1 + \frac{1}{3} \cdot 0 = \frac{2}{3} \\[10pt]r(\text{Cloudy}) &= \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 0 = \frac{1}{2}\end{align*}\]

이다.

Bellman 방정식은

\[\begin{align*} V(s) &= r(s) + \gamma \sum_{s'} P(s' \mid s) V(s') \end{align*}\]

이다.

\[\begin{align*}V(\text{Sunny}) &= r(\text{Sunny}) \\&\quad + \gamma \left[ P(\text{Sunny} \mid \text{Sunny}) V(\text{Sunny}) + P(\text{Cloudy} \mid \text{Sunny}) V(\text{Cloudy}) \right]\end{align*}\]

값을 대입하면

\[V(\text{Sunny}) = \frac{2}{3} + \frac{9}{10} \left[ \frac{2}{3} V(\text{Sunny}) + \frac{1}{3} V(\text{Cloudy}) \right]\]

정리하면

\[V(\text{Sunny}) = \frac{2}{3} + \frac{3}{5} V(\text{Sunny}) + \frac{3}{10} V(\text{Cloudy})\]

이므로

\[\frac{2}{5}V(\text{Sunny}) - \frac{3}{10}V(\text{Cloudy}) = \frac{2}{3}\]

를 얻는다. 양변에 30을 곱하면

\[12V(\text{Sunny}) - 9V(\text{Cloudy}) = 20\]

가 된다.

\[\begin{align*}V(\text{Cloudy}) &= r(\text{Cloudy}) \\&\quad + \gamma \left[ P(\text{Sunny} \mid \text{Cloudy}) V(\text{Sunny}) + P(\text{Cloudy} \mid \text{Cloudy}) V(\text{Cloudy}) \right]\end{align*}\]

값을 대입하면

\[V(\text{Cloudy}) = \frac{1}{2} + \frac{9}{10} \left[ \frac{1}{2} V(\text{Sunny}) + \frac{1}{2} V(\text{Cloudy}) \right]\]

이다.

이를 정리하면

\[V(\text{Cloudy}) = \frac{1}{2} + \frac{9}{20} V(\text{Sunny}) + \frac{9}{20} V(\text{Cloudy})\]

이므로

\[-\frac{9}{20} V(\text{Sunny}) + \frac{11}{20} V(\text{Cloudy}) = \frac{1}{2}\]

가 된다.

양변에 20을 곱하면

\[-9 V(\text{Sunny}) + 11 V(\text{Cloudy}) = 10\]

이다.

두 상태의 Bellman 방정식을 함께 쓰면

\[\begin{cases} 12V(\text{Sunny}) - 9V(\text{Cloudy}) = 20 \\ -9V(\text{Sunny}) + 11V(\text{Cloudy}) = 10 \end{cases}\]

이고 이를 잘 계산하면

\[\begin{aligned}V(\text{Sunny}) &= \frac{310}{51} \approx 6.08 \\[10pt]V(\text{Cloudy}) &= \frac{100}{17} \approx 5.88\end{aligned}\]

를 얻는다.

이 결과의 의미는 Sunny 상태에서 시작하여 앞으로 얻게 될 할인수익의 기댓값이 약 6.08이라는 뜻이고

Cloudy 상태에서 시작했을 때의 기대 할인수익이 약 5.88이라는 뜻이다. 따라서 Sunny에서 출발하는 것이 조금 더 유리하다.

Markov Decision Process: MDP

지금까지 다룬 MRP에서는 현재 상태가 주어지면 다음 상태로 이동하는 확률이 이미 정해져 있었다.

즉, 에이전트가 현재 상태에서 어떤 선택을 하는지는 고려하지 않았으며, 시스템은 주어진 전이확률에 따라 상태를 이동할 뿐이었다.

지금부터는 에이전트가 행동을 선택하고, 그 행동에 따라 다음 상태와 보상이 달라지는 구조로 동작한다. MRP에 행동을 추가하여 확장한 모델을 Markov Decision Process, MDP라고 한다.

MRP → MDP

MRP에서는 현재 상태 s가 주어지면 다음 상태의 분포가 바로 결정되었다

\[S_t \rightarrow R_{t+1}, S_{t+1}\]

전이확률은

\[P(s' \mid s)\]

이었고, 기대 즉시보상은

\[r(s) = \mathbb{E} \left[ R_{t+1} \mid S_t = s \right]\]

이었다.

반면 MDP에서는 현재 상태에서 에이전트가 행동 \(A_t\)를 선택한다.

\[S_t \xrightarrow{A_t} R_{t+1}, S_{t+1}\]

따라서 다음 상태와 보상은 현재 상태뿐 아니라 선택한 행동에도 영향을 받는다.

\[\begin{gathered}P(s' \mid s, a) \\r(s, a) = \mathbb{E} \left[ R_{t+1} \mid S_t = s, A_t = a \right]\end{gathered}\]

MDP의 구성요소

MDP에서의 구성요소에 대해 자세히 알아본다.

\[\text{MDP} = \langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle\]
  • \(\mathcal{S}:\) state space - \(\mathcal{S}=\{s_1, s_2, ...,s_n\}\)
  • \(\mathcal{A}:\) Action space - \(\mathcal{A}=\{a_1, a_2, ...,a_n\}\)
  • \(\mathcal{P}:\) transition Matrix - \(P(s' \mid s, a) = P(S_{t+1} = s' \mid S_t = s, A_t = a)\)
  • \(\mathcal{R}:\) reward function - \(r(s, a) = \mathbb{E} \left[ R_{t+1} \mid S_t = s, A_t = a \right]\)
  • \(\gamma :\) discount factor(할인율) - \(0 \le \gamma < 1\)

정책 Policy

MDP에서는 상태마다 여러 행동을 선택할 수 있다. 그렇다면 현재 상태에서 어떤 행동을 선택할지를 정하는 규칙이 필요하다. 이 규칙을 정책(Policy) 이라고 한다.

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

\(\pi(a \mid s)\)는 상태 s에서 행동 a를 선택할 확률이고 각 상태 행동에 대한 확률분포를 출력한다.

예를 들어 상태 s에서 선택가능한 행동이

\[\mathcal{A} = \{ \text{Left}, \text{Right}, \text{Forward} \}\]

이고 정책이 다음과 같다고 하자.

그러면 행동 확률분포는 아래와 같이 구성될 수 있다.

\[\begin{aligned}\pi(\text{Left} \mid s) &= 0.2 \\\pi(\text{Right} \mid s) &= 0.3 \\\pi(\text{Forward} \mid s) &= 0.5\end{aligned}\]

정책은 상태에 대한 행동 확률분포 임으로 각 상태에서 행동 확률의 합은 반드시 1이여야 한다.

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

정책하에서 전이확률

이제 정책이 무엇인지 알았음으로 정책에 대한 전이 확률을 정확히 표현할 수 있다.

정책이 \(\pi(a \mid s)\)이고 MDP의 전이확률이 \(P(s'\mid s, a)\) 임으로 정책이 상태 s에서 행동 a를 선택하고 그 행동에 따라 다음 상태 s’으로 이동하므로 정책 아래에서의 전이확률은

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

가 된다. 정책하에서라는 표기를 하기위해 P밑에 첨자로 \(\pi\)가 붙는 것으로 구분 가능하다.

의미는 가능한 각 행동에 대해 그 행동을 선택할 확률 x 그 행동으로 s’에 갈 확률을 모두 더한 것이다.

예를들어 상태 s에서 정책이 \(\pi(a_1 \mid s) = 0.7, \quad \pi(a_2 \mid s) = 0.3\)의 확률로 행동을 선택하고,

\(P(s' \mid s, a_1) = 0.8, \quad P(s' \mid s, a_2) = 0.2\) 라면 정책 아래에서 s′로 이동할 확률은

\[\begin{aligned} P_{\pi}(s' \mid s) &= \pi(a_1 \mid s) P(s' \mid s, a_1) + \pi(a_2 \mid s) P(s' \mid s, a_2) \\[5pt] P_{\pi}(s' \mid s) &= 0.7 \cdot 0.8 + 0.3 \cdot 0.2 = 0.62\end{aligned}\]

가 되어 정책을 고정하면 상태와 행동에 의존했던 전이 확률 \(P_{\pi}(s' \mid s, a)\)이 상태에만 의존하는 \(P_{\pi}(s' \mid s)\) 전이확률 로 바뀐다.

정책하에서 기대 즉시보상

MDP에서 상태 s에서 행동 a를 선택했을 때의 기대 즉시보상은

\[r(s, a) = \mathbb{E} [ R_{t+1} \mid S_t = s, A_t = a ]\]

였는데, 정책 \(\pi\)가 고정되면 상태 s에서 어떤 행동을 선택할지도 확률적으로 정해짐으로 상태 s에서 받을 기대보상은 행동별 기대보상의 가중평균이 된다.

\[\begin{aligned}r_{\pi}(s) &= \mathbb{E}_{\pi} [ R_{t+1} \mid S_t = s ] \\[5pt] \mathbb{E}[X] &= \sum_{y} P(Y = y) \mathbb{E}[X \mid Y = y] \\r_{\pi}(s)&= \sum_{a \in \mathcal{A}} \pi (A_t = a \mid S_t = s) \mathbb{E} [ R_{t+1} \mid S_t = s, A_t = a ]\end{aligned}\]

따라서

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

를 얻는다. 의미는 행동 선택확률과 그 행동별 기대보상을 곱하고 모든 행동에 대하여 모두 더한 것이다.

예를들어 정책 π를 따를 때 상태 s에서 얻을 할인수익의 기댓값을 \(\pi(a_1 \mid s) = 0.7, \quad \pi(a_2 \mid s) = 0.3\) 이고 \(r(s, a_1) = 2, \quad r(s, a_2) = -1\) 이라면

\[\begin{aligned} r_{\pi}(s) &= \pi(a_1 \mid s) r(s, a_1) + \pi(a_2 \mid s) r(s, a_2) r_{\pi}(s) \\&= 0.7 \cdot 2 + 0.3 \cdot (-1) \\ &= 1.4 - 0.3 \\ &= 1.1 \end{aligned}\]

가 된다.

정책하에서 상태가치함수

정책 \(\pi\)를 따를 때 상태 s의 가치함수는 다음과 같다.

\[V_{\pi}(s) = \mathbb{E}_{\pi} [ G_t \mid S_t = s ]\]

상태가치함수를 Bellan Equation 형태로 표현해보자.

이중 기댓값의 정리에 의해

\[\mathbb{E}[X \mid Z = z] = \sum_{y} \mathbb{E}[X \mid Y = y, Z = z] \cdot P(Y = y \mid Z = z)\]

로 쓸 수 있음으로 \(X=G_t, \;Y=A_t,\; Z=S_t\) 로 보면 아래 처럼 쓸 수 있다.

\[V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi( \underbrace{A_t = a}_{Y} \mid \underbrace{S_t = s}_{Z} ) \mathbb{E}_{\pi} [ \underbrace{G_t}_{X} \mid \underbrace{S_t = s}_{Z}, \underbrace{A_t = a}_{Y} ]\]

가 된다. 두 번째식에서 \(G_t = R_{t+1} + \gamma G_{t+1}\) 임으로

\[V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \mathbb{E}_{\pi} [R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a]\]

가 되고 기댓값의 선형성에 의해

\[\begin{align*}V_{\pi}(s) &= \sum_{a \in \mathcal{A}} \pi(a \mid s) \Big[ \mathbb{E} [ R_{t+1} \mid S_t = s, A_t = a ] + \gamma \mathbb{E}_{\pi} [ G_{t+1} \mid S_t = s, A_t = a ] \Big]\end{align*}\]

가 되고 \(r(s, a) = \mathbb{E} [ R_{t+1} \mid S_t = s, A_t = a ]\) 임으로

\[V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \left[ r(s, a) + \gamma \mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a] \right]\]

로 쓸 수 있다.

두 번째항에서

\[\mathbb{E}_{\pi} \left[G_{t+1} \mid S_t = s, A_t = a\right]\]

이중 기댓값의 정리에 의해

\[\mathbb{E}[X \mid Z = z] = \sum_{y} \mathbb{E}[X \mid Y = y, Z = z] \cdot P(Y = y \mid Z = z)\]

\(X = G_{t+1}, \quad Y = (S_t, A_t), \quad Z = S_{t+1}\)두고 값을 대입하면

\[\begin{align*}\mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a] &= \sum_{s' \in \mathcal{S}} \mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s'] \\&\qquad \times P(S_{t+1} = s' \mid S_t = s, A_t = a)\end{align*}\]

가 된다.

\(G_{t+1}\)은 \(S_t\)와 \(A_t\)에 대해서는 영향을 받지 않는다.

\[\begin{align*}\mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a] &= \sum_{s' \in \mathcal{S}} \mathbb{E}_{\pi} [G_{t+1} \mid S_{t+1} = s'] \\&\qquad \times P(S_{t+1} = s' \mid S_t = s, A_t = a)\end{align*}\]

\(P(S_{t+1} = s' \mid S_t = s, A_t = a)\)는 \(P^a_{ss'}\)으로 바꿔쓰면

\[\begin{align*}\mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a] &= \sum_{s' \in \mathcal{S}} \mathbb{E}_{\pi} [G_{t+1} \mid S_{t+1} = s'] \times P^a_{ss'}\end{align*}\]

된다. 그리고

\[V_{\pi}(s')=\mathbb{E}_{\pi} [G_{t+1} \mid S_{t+1} = s']\]

이므로

\[\begin{align*}\mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a] &= \sum_{s' \in \mathcal{S}} V_{\pi}(s') \times P^a_{ss'}\end{align*}\]

으로 쓸 수 있다. 기존 수식에

\[V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \left[ r(s, a) + \gamma \mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a] \right]\]

대입하면

\[V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \left[ r(s, a) + \gamma \sum_{s' \in \mathcal{S}} V_{\pi}(s') P^a_{ss'} \right]\]

가 되고 이 가치함수 식은 \(\pi\)에 대한 Bellman Expectation Equation 형태로 표현한 것이다.

Example

정책과 보상이 다음과 같이 있다고 하자

\[\begin{align*}\pi(a_1 \mid s) &= 0.7, \quad \pi(a_2 \mid s) = 0.3 \\r(s, a_1) &= 2, \quad r(s, a_2) = -1\end{align*}\]

전이 확률은

\[\begin{align*}P(s'_1 \mid s, a_1) &= 0.8, \quad P(s'_2 \mid s, a_1) = 0.2 \\P(s'_1 \mid s, a_2) &= 0.2, \quad P(s'_2 \mid s, a_2) = 0.8\end{align*}\]

이라고 하자.

상태가치 벨만 방정식은

\[V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \left[ r(s,a) + \gamma \sum_{s' \in \mathcal{S}} P(s' \mid s,a) V_{\pi}(s') \right]\]

이고 행동이 2개 상태가 2개 임으로

\[\begin{aligned}V_{\pi}(s) &= \pi(a_1 \mid s) \left[ r(s,a_1) + \gamma \left\{ P(s_1' \mid s,a_1)V_{\pi}(s_1') + P(s_2' \mid s,a_1)V_{\pi}(s_2') \right\} \right] \\&\quad + \pi(a_2 \mid s) \left[ r(s,a_2) + \gamma \left\{ P(s_1' \mid s,a_2)V_{\pi}(s_1') + P(s_2' \mid s,a_2)V_{\pi}(s_2') \right\} \right]\end{aligned}\]

값을 대입해보면

\[\begin{aligned}V_{\pi}(s) &= 0.7 \left[ 2 + \gamma \left\{ 0.8 V_{\pi}(s_1') + 0.2 V_{\pi}(s_2') \right\} \right] \\&\quad + 0.3 \left[ -1 + \gamma \left\{ 0.2 V_{\pi}(s_1') + 0.8 V_{\pi}(s_2') \right\} \right].\end{aligned}\]

이고 정리하면

\[V_{\pi}(s) = 1.1 + \gamma \left[ 0.62 V_{\pi}(s_1') + 0.38 V_{\pi}(s_2') \right]\]

과 같이 현재 보상만 평균내는 것이 아니라 각 행동으로 이동할 다음 상태들의 가치까지 함께 고려한다.

이렇게 상태가치 함수 \(V_{\pi}(s)\)는 상태 s에서 정책 \(\pi \)를 따랐을 때 평균적인 미래 보상을 나타낸다.

하지만 이 값에는 정책이 선택할 수 있는 여러 행동의 결과가 평균되어 들어 있다. 따라서 \(V_{\pi}(s)\)만 보고는 상태 s에서 어느 행동이 더 좋은지 직접 알기 어렵다.

강화학습의 목표는 각 상태에서 더 좋은 행동을 선택하도록 정책을 개선하는 것이다.

이를 위해서는 상태 s에서 선택 가능한 여러 행동을 비교하여, 어떤 행동이 가장 많은 미래 보상으로 이어지는지 알아야 한다. 그리고 더 높은 미래 보상을 주는 행동을 선택하도록 정책을 업데이트한다.

이처럼 상태 s에서 행동 a를 선택하는 것이 얼마나 좋은지를 나타내는 함수가 행동가치함수(Action-value Function) 이다.

Action Value Function(행동가치 함수)

상태 s에서 행동 a를 먼저 선택하고, 그 이후부터 정책 \(\pi\)를 따랐을 때 얻게 될 할인수익의 기댓값을 행동가치함수라고 한다.

\[Q_{\pi}(s, a) = \mathbb{E}_{\pi} [G_t \mid S_t = s, A_t = a]\]

상태가치함수와 행동가치함수의 차이는 다음과 같다.

  • 상태가치함수: 정책이 선택하는 행동들을 평균한 상태의 가치
  • 행동가치함수: 특정 행동 a를 선택했을 때의 가치

그리고 이 둘의 관계는

\[V_{\pi}(s) = \sum_{a} \pi(a \mid s) Q_{\pi}(s, a)\]

이다.

기존 상태가치함수를 벨만 방정식으로 표현한

\[V_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) \underbrace{\left[ r(s, a) + \gamma \sum_{s' \in \mathcal{S}} V_{\pi}(s') P^a_{ss'} \right]}_{Q_{}\pi(s,a)}\]

수식을 보면 바로 저 부분이 행동가치함수이다.

예를 들어 상태 s에서 두 행동의 가치가

\[Q_{\pi}(s, a_1) = 10, \quad Q_{\pi}(s, a_2) = 2\]

이고 현재 정책이 두 행동을 각각 절반의 확률로 선택한다면,

\[V_{\pi}(s) = 0.5 \cdot 10 + 0.5 \cdot 2 = 6\]

이다.

그러나 \(V_{\pi}(s) =6\)이라는 값만 보면 \(a_1\)이 좋은 행동인지 \(a_2\)가 좋은 행동인지 또는 두 행동이 모두 비슷한지를 알 수 없다. 왜냐하면 행동별 정보가 평균 속에 섞여 있기 때문이다.

그래서 상태 s에서 행동 a를 먼저 선택하고, 그 이후부터 정책 \(\pi\)를 따랐을 때 얻는 할인수익의 기댓값을 정의한다.

정리하면 상태가치함수는 정책을 평가하는 데 유용하고, 행동가치함수는 행동을 비교하여 정책을 개선하는 데 필요하다.

행동가치 함수를 Bellan Equation형태로 표현해보자.

\[Q_{\pi}(s, a) = \mathbb{E}_{\pi} [ G_t \mid S_t = s, A_t = a ]\]

이고 \(G_t\)는

\[G_t = R_{t+1} + \gamma G_{t+1}\]

이를 행동가치함수에 대입하면

\[Q_{\pi}(s, a) = \mathbb{E}_{\pi} [ R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a ]\]

기댓값의 선형성을 적용하면

\[\begin{aligned}Q_{\pi}(s, a) &= \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a] \\&\quad + \gamma \mathbb{E}_{\pi}[G_{t+1} \mid S_t = s, A_t = a]\end{aligned}\]

이다.

첫 번째 항은 상태 s에서 행동 a를 선택했을 때의 기대 즉시보상이다.

\[r(s, a) = \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a]\]

따라서

\[Q_{\pi}(s, a) = r(s, a) + \gamma \mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a]\]

로 쓸 수 있다.

이중 기댓값의 법칙을 적용하면

\[\mathbb{E}[X \mid Z = z] = \sum_{y} \mathbb{E}[X \mid Y = y, Z = z] \cdot P(Y = y \mid Z = z)\]

로 쓸 수 있음으로 \(X=G_{t+1}, \;Y=S_{t+1},\; Z=S_t,A_t\) 로 보면 아래 처럼 쓸 수 있다.

\[\begin{aligned} &\mathbb{E}_{\pi} [ \underbrace{G_{t+1}}_{X} \mid \underbrace{S_t = s, A_t = a}_{Z} ] \\ &= \sum_{s' \in \mathcal{S}} P( \underbrace{S_{t+1} = s'}_{Y} \mid \underbrace{S_t = s, A_t = a}_{Z} ) \\ &\quad \times \mathbb{E}_{\pi} [ \underbrace{G_{t+1}}_{X} \mid \underbrace{S_t = s, A_t = a}_{Z}, \underbrace{S_{t+1} = s'}_{Y} ] \end{aligned}\]

\(G_{t+1}\)은 \(S_t\)와 \(A_t\)에 대해서는 영향을 받지 않는다.

\[\begin{aligned}&\mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s'] \\&= \mathbb{E}_{\pi} [G_{t+1} \mid S_{t+1} = s']\end{aligned}\]

상태가치함수의 정의에 의해

\[V_{\pi}(s') = \mathbb{E}_{\pi} [G_{t+1} \mid S_{t+1} = s']\]

이므로

\[\mathbb{E}_{\pi} [G_{t+1} \mid S_t = s, A_t = a] = \sum_{s' \in \mathcal{S}} P(S_{t+1}=s' \mid S_t=s,A_t=a) V_{\pi}(s')\]

가 된다.

이를 앞의 식에 대입하면

\[Q_{\pi}(s, a) = r(s, a) + \gamma \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')\]

임으로 s′의 가치는 그 상태에서 선택 가능한 행동들의 가치를 정책의 행동 선택 확률로 평균한 값이다.

이를

\[Q_{\pi}(s, a) = r(s, a) + \gamma \sum_{s' \in \mathcal{S}} P^a_{ss'} V_{\pi}(s')\]

에 대입하면

\[Q_{\pi}(s, a) = r(s, a) + \gamma \sum_{s'} P(s' \mid s, a) \sum_{a'} \pi(a' \mid s') Q_{\pi}(s', a')\]

이 식은 행동가치를 기대 즉시보상과 할인된 다음 상태의 가치로 표현한 행동가치 Bellman Equation형태이다.

행동/상태 가치함수를 Bellman 형태로 표현하는 이유

상태가치함수와 행동가치함수는 현재부터 미래까지 얻을 모든 할인보상의 기댓값이다.

\[\begin{aligned}V_{\pi}(s) &= \mathbb{E}_{\pi}[G_t \mid S_t = s] \\Q_{\pi}(s, a) &= \mathbb{E}_{\pi}[G_t \mid S_t = s, A_t = a]\end{aligned}\]

하지만 이를 정의 그대로 계산하려면 현재 상태에서 출발할 수 있는 모든 미래 경로와 그 경로에서 발생하는 모든 보상을 고려해야 한다. 시간이 길어질수록 가능한 경로가 기하급수적으로 증가하며, 계속되는 문제에서는 미래 경로가 무한히 이어지므로 직접 계산하기 어렵다.

왜 어려운가?
\[G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots\]

이를 상태가치함수에 그대로 대입하면

\[V_{\pi}(s) = \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \mid S_t = s \right]\]

이 된다.

기대값의 선형성에 의해

\[\begin{aligned}V_{\pi}(s) &= \mathbb{E}_{\pi}[R_{t+1} \mid S_t = s] \\&\quad + \gamma \mathbb{E}_{\pi}[R_{t+2} \mid S_t = s] \\&\quad + \gamma^2 \mathbb{E}_{\pi}[R_{t+3} \mid S_t = s] + \cdots\end{aligned}\]

로 풀린다.

그리고 첫 번째 보상의 기대값은

\[\mathbb{E}_{\pi} [R_{t+1} \mid S_t = s] = \sum_{a_t} \pi(a_t \mid s) r(s, a_t)\]

두 번째 보상의 기대값은 \(R_{t+2}\)를 받으려면 다음 과정을 모두 고려해야 한다.

\[s \xrightarrow{a_t} s_{t+1} \xrightarrow{a_{t+1}} R_{t+2}\]

따라서

\[\begin{aligned} &\mathbb{E}_{\pi} [ R_{t+2} \mid S_t = s ] \\ &= \sum_{a_t} \pi(a_t \mid s) \sum_{s_{t+1}} P(s_{t+1} \mid s, a_t) \sum_{a_{t+1}} \pi(a_{t+1} \mid s_{t+1}) r(s_{t+1}, a_{t+1}) \end{aligned}\]

가 된다.

세 번째 보상의 기대값은 \(R_{t+3}\)를 받으려면 경로가 더 길어진다.

\[s \xrightarrow{a_t} s_{t+1} \xrightarrow{a_{t+1}} s_{t+2} \xrightarrow{a_{t+2}} R_{t+3}\]

따라서

\[\begin{aligned}&\mathbb{E}_{\pi}[R_{t+3} \mid S_t = s] \\&= \sum_{a_t} \pi(a_t \mid s) \sum_{s_{t+1}} P(s_{t+1} \mid s, a_t) \sum_{a_{t+1}} \pi(a_{t+1} \mid s_{t+1}) \\&\quad \times \sum_{s_{t+2}} P(s_{t+2} \mid s_{t+1}, a_{t+1}) \sum_{a_{t+2}} \pi(a_{t+2} \mid s_{t+2}) r(s_{t+2}, a_{t+2})\end{aligned}\]

가 된다.

Bellman 방정식을 사용하지 않고 전체 상태가치함수를 적어보면

\[\begin{aligned}V_{\pi}(s) &= \sum_{a_t} \pi(a_t \mid s) r(s, a_t) \\&+ \gamma \sum_{a_t} \sum_{s_{t+1}} \sum_{a_{t+1}} \pi(a_t \mid s) P(s_{t+1} \mid s, a_t) \\&\quad \times \pi(a_{t+1} \mid s_{t+1}) r(s_{t+1}, a_{t+1}) \\&+ \gamma^2 \sum_{a_t} \sum_{s_{t+1}} \sum_{a_{t+1}} \sum_{s_{t+2}} \sum_{a_{t+2}} \pi(a_t \mid s) P(s_{t+1} \mid s, a_t) \\&\quad \times \pi(a_{t+1} \mid s_{t+1}) P(s_{t+2} \mid s_{t+1}, a_{t+1}) \\&\quad \times \pi(a_{t+2} \mid s_{t+2}) r(s_{t+2}, a_{t+2}) \\&+ \cdots\end{aligned}\]

가 된다.

시간이 한 단계 증가할 때마다 가능한 상태와 행동에 대한 합이 계속 추가되어 매우 복잡해진다.

\[V_{\pi}(s) = \sum_{a} \pi(a \mid s) \left[ r(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V_{\pi}(s') \right] \\ Q_{\pi}(s, a) = r(s, a) + \gamma \sum_{s'} P(s' \mid s, a) \sum_{a'} \pi(a' \mid s') Q_{\pi}(s', a')\]

Bellman 형태로 나타내면 무한한 미래를 한꺼번에 계산하지 않고, 현재 한 스텝과 다음 상태 또는 행동의 가치만을 이용해 가치함수를 반복적으로 계산할 수 있다. 이 재귀적 구조가 정책평가, 정책개선, 가치 반복, Q-learning과 같은 강화학습 알고리즘의 기반이 된다.

따라서 Bellman 방정식은 무한한 미래의 가치 계산을 반복 가능한 한 단계 문제로 바꾸기 위해 필요하다.

마무리

평균보상 방식은 에르고딕성이 필요하고 보상을 '언제' 받았는지를 반영하지 못했다. 이를 해결하기 위해 미래 보상을 \(\gamma\)로 할인하여 더하는 할인수익 \(G_t\)를 도입하였다.

이를 바탕으로 MRP와 MDP의 상태가치함수 및 Bellman 방정식을 살펴보았다.

또한 정책하에서의 상태가치 \(V_\pi(s)\)는 행동들의 가치가 평균된 값이므로, 각 행동을 직접 비교하기 위해 행동가치함수 \(Q_\pi(s,a)\)가 필요함을 확인했다.

지금까지는 주어진 정책 하나에 대한 평가일 뿐, 강화학습의 목표는 가장 좋은 정책을 찾는 것이다. 다음 시간에는 최적 정책 \(\pi^*\)를 구하기 위한 발판인 벨만 최적 방정식을 유도하고, 평가와 개선을 반복하여 최적 정책에 도달하는 동적 계획법(정책 반복, 가치 반복)을 알아본다.