[3차시] Markov Decision Process

서론

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

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

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

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
- trainsition probaility: \(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 ]

상태가치 함수

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

시점 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}

된다.

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

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

이므로

날씨 예제에 보상을 얹어 보자. Sunny인 날은 기분이 좋아 +1, Cloudy인 날은 −1이라 하자:

R(\text{Sunny}) = +1, \quad R(\text{Cloudy}) = -1

이때 상태전이 행렬은 아래와 같았다.

\begin{aligned} \mathcal{P} &= \begin{pmatrix} \frac{2}{3} & \frac{1}{3} \\[6pt] \frac{1}{2} & \frac{1}{2} \end{pmatrix}\end{aligned}

이제 각 상태에 보상이 주어졌으므로, 어떤 상태가 얼마나 좋은지 평가할 수 있다. 그러나 상태의 좋음은 현재 받는 보상만으로 결정되지 않는다. 예를 들어 오늘이 Sunny라면 현재 보상 +1을 받을 뿐 아니라, 내일도 Sunny일 확률이 높아( \(P_{11}=\frac{2}{3}\) ) 미래에도 좋은 보상을 받을 가능성이 크다. 따라서 한 상태의 가치는 그 상태에서 시작했을 때 앞으로 받을 모든 보상의 기대값으로 평가해야 한다.