[2차시] Average Reward

서론

지금까지는 정책이 만들어내는 마르코프 체인을 장기적인 관점에서 분석하기 위한 이론적 기반을 살펴보았다. 정상분포와 에르고딕 성질을 통해, 정책을 충분히 오래 수행하면 각 상태를 얼마나 자주 방문하는지를 하나의 확률분포로 표현할 수 있음을 확인하였다.

그러나 상태를 얼마나 자주 방문하는지만으로는 정책의 성능을 평가할 수 없다. 어떤 상태는 좋은 상태일 수도 있고, 어떤 상태는 피해야 하는 상태일 수도 있기 때문이다. 즉, 상태의 방문 빈도에 '좋음'이라는 기준이 함께 주어져야 비로소 정책의 우수성을 비교할 수 있다.

이를 위해 강화학습에서는 각 상태(또는 상태-행동)에 보상(Reward) 을 부여하여 상태의 가치를 수치로 표현한다. 그리고 에르고딕 성질에 의해 얻은 장기 방문 비율과 이 보상을 결합하면, 정책이 장기간 수행되었을 때 평균적으로 얼마나 좋은 성과를 내는지를 하나의 값으로 나타낼 수 있다. 이러한 정책의 장기 성능 지표를 평균보상(Average Reward) 이라 한다.

Observation Reward: 실제로 관측되는 보상
State-wise Expected Reward: 상태별 기대보상
Long-run State Visitation Distribution: 장기 상태 방문 비율
Finite-time Average Reward: 유한 시간의 평균보상
Average Reward: 정책의 장기 평균보상
- Example: Sunny–Cloudy Average Reward

실제로 관측되는 보상: \(R_{t+1}\)

정책을 평가하려면, 그 정책을 따랐을 때 에이전트가 장기적으로 얼마나 좋은 결과를 얻는지를 하나의 값으로 나타내야 한다. 이를 위해 먼저 정책 \(\pi\)가 각 상태에서 한 스텝 동안 평균적으로 얼마나 좋은 결과를 만드는지를 정의하고, 그다음 에이전트가 장기적으로 각 상태를 얼마나 자주 방문하는지를 함께 고려한다.

S_t \rightarrow A_t \rightarrow R_{t+1}, S_{t+1}

같은 상태에서 같은 정책을 사용하더라도 다음 상태가 다르게 결정될 수 있기 때문에, 항상 같은 보상을 받는 것은 아니다.

상태별 기대보상: \(r_{\pi}(s)\)

현재 상태가 s라고 고정했을 때, 정책 \(\pi\)를 따라 한 스텝 행동하여 평균적으로 받는 보상을 다음과 같이 정의한다.

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

\(r_{\pi}(s)\)는 현재 상태가 s일 때 정책 \(\pi\)를 따르면 다음 한 스텝에서 평균적으로 얻는 보상이다.

따라서 이는 특정 경로에서 실제로 받은 보상 \(R_{t+1}\)이 아니라 상태 s에서 가능한 결과들을 모두 고려한 한 스텝 기대보상이다.

\(r_{\pi}(s)\)를 알면 각 상태가 한 스텝 관점에서 얼마나 좋은지는 알 수 있다.

그러나 아주 높은 보상을 주는 상태가 존재하더라도 정책이 그 상태를 거의 방문하지 않는다면 정책 전체의 성능은 높지 않을 수 있다. 반대로 보상이 적당히 좋은 상태를 매우 자주 방문한다면 장기적인 평균 성능은 높을 수 있다.

따라서 상태별 기대보상뿐 아니라 상태별 장기 방문 비율도 필요하다.

장기 상태 방문 비율: \(d_{\pi}(s)\)

정책 \(\pi\)를 고정하면 에이전트의 상태변화는 하나의 마르코프 체인이 되고 이 체인이 에르고딕하다면 시간이 충분히 지났을 때 상태 s를 방문하는 비율은 정상분포 \(d_{\pi}(s)\)로 수렴한다.

\(d_{\pi}(s)\): 정책 \(\pi\)를 장시간 따랐을 때 상태 s에 머무는 비율

수식으로는

P_{\pi}(S_t = s) \longrightarrow d_{\pi}(s)\\[10pt]\frac{N_T(s)}{T} \longrightarrow d_{\pi}(s)

\(N_T(s)\)는 \(T\)스텝 동안 상태 s를 방문한 횟수이다.

유한한 시간의 평균보상: \(\bar{R}_T\)

정책을 \(T\)스텝 동안 수행하여 보상

R_1 + R_2 + \cdots + R_T

을 받았다면 실제로 관측한 보상의 평균은

\bar{R}_T = \frac{1}{T} \sum_{t=0}^{T-1} R_{t+1}

위 수식은 한 번의 경로에서 계산한 표본 평균이다.

\(T:\) 정책을 수행한 전체 스텝 수
t: 현재 스텝을 나타내는 인덱스
\(R_{t+1}\): t시점의 상태에서 한 번 전이한 뒤 받은 보상
\(\bar{R}_T\): \(T\)스텝 동안 실제로 관측한 보상의 평균

예를 들어 \(T=5\) 동안 보상이

\[0, 0, 1, 0, 1\]

이었다면 보상 평균은

\bar{R}_5 = \frac{0 + 0 + 1 + 0 + 1}{5} = 0.4

다른 경로에서는 다른 값이 나올 수 있다. 따라서 \(\bar{R}_T\)는 정책의 고정된 성질이라기보다, 한 번의 유한한 실행에서 관측한 결과이다.

정책의 Average reward: \(g_{\pi}\)

정책 \(\pi\)의 평균보상은 정책을 무한히 오랫동안 수행했을 때 한 스텝당 평균적으로 얻는 보상이다.

g_{\pi} = \lim_{T \to \infty} \mathbb{E}_{\pi} \left[ \bar{R}_T \right]

\(\bar{R}_T\)를 대입하면

g_{\pi} = \lim_{T \to \infty} \mathbb{E}_{\pi} \left[ \frac{1}{T} \sum_{t=0}^{T-1} R_{t+1} \right]

이고 기대값의 선형성을 사용하면

g_{\pi} = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}_{\pi} [R_{t+1}]

가 된다. 각 시점의 기대보상 \(\mathbb{E}_{\pi}[R_{t+1}]\)은 상태별로 나눠 계산가능하다.

\mathbb{E}_{\pi}[R_{t+1}] = \sum_{s \in \mathcal{S}} P_{\pi}(S_t = s) \mathbb{E}_{\pi}[R_{t+1} \mid S_t = s]

그리고 조건부 기댓값을 다음과 같이 정의했으므로

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

이렇게 기댓값을 풀면 상태에 있을 확률(가중치)와 각 상태의 보상 \(r_{\pi}(s)\)가 곱해진다.

\mathbb{E}_{\pi}[R_{t+1}] = \sum_{s} P_{\pi}(S_t = s) r_{\pi}(s)

이를 다시 전체 식에 대입하면

g_{\pi} = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \sum_{s} P_{\pi}(S_t = s) r_{\pi}(s)

가 된다. 시그마의 순서를 바꾸면

g_{\pi} = \sum_{s} \left[ \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} P_{\pi}(S_t = s) \right] r_{\pi}(s)

가 된다.

그런데 에르고딕한 마르코프 체인에서는 각 시점의 상태확률이 정상분포로 수렴함으로

P_{\pi}(S_t = s) \xrightarrow{t \to \infty} d_{\pi}(s)

가 된다. 슈톨츠–체사로의 평균 정리(Stolz–Cesàro - 어떤 수열의 각 항이 점점 \(L\)에 가까워진다면, 그 항들을 처음부터 평균낸 값도 결국 \(L\)에 가까워진다.) 에 의해 실수열의 극한 \(\lim_{n \to \infty} x_n = L\) 이면 다음이 성립한다.

\lim_{n \to \infty} \frac{x_1 + x_2 + \dots + x_n}{n} = L

따라서 상태확률들을 시간에 따라 평균낸 값도 \(d_{\pi}(s)\)로 수렴한다.

\lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} P_{\pi}(S_t = s) = d_{\pi}(s)

따라서 최종적으로 Average reward는

g_{\pi} = \sum_{s} d_{\pi}(s) r_{\pi}(s)

가 된다.

이 식의 의미는

\(d_{\pi}(s)\): 상태 s를 장기적으로 방문하는 비율에
\(r_{\pi}(s)\): 상태 s에서 한 스텝 동안 평균적으로 얻은 보상을 곱하여

상태 s가 정책에 장기 평균보상에 기여하는 정도이다.

그리고 모든 상태에 대한 기여도를 더하면 정책의 전체적인 장기 성능 \(g_{\pi}\)가 된다.

Example: Sunny–Cloudy 날씨의 평균보상

앞에서 사용한 날씨예제로 average reward을 구해보자. 상태는 두 가지가 있다.

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

이제 각 상태에 보상을 부여하여 Sunny 상태에 도착하면 보상 +1을 받고, Cloudy 상태에 도착하면 보상 0을 받는다고 하자.

정책을 따랐을 때 상태전이행렬은 다음과 같다.

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

현재 상태가 Sunny일 때의 기대보상은

r_{\pi}(s) = \mathbb{E}_{\pi}[R_{t+1} \mid S_t = s] = \sum_{s' \in \mathcal{S}} r(s') P_{\pi} \left( S_{t+1} = s' \mid S_t = s \right)

\begin{align*} r_{\pi}(\text{Sunny}) &= \sum_{s' \in \mathcal{S}} r(s') P_{\pi} (S_{t+1} = s' \mid S_t = \text{Sunny}) \\[15pt] &= r(\text{Sunny}) P_{\pi} (S_{t+1} = \text{Sunny} \mid S_t = \text{Sunny}) \\[5pt] &\quad + r(\text{Cloudy}) P_{\pi} (S_{t+1} = \text{Cloudy} \mid S_t = \text{Sunny}) \end{align*}

위 수식에 값을 대입하면

\begin{align*}r_{\pi}(\text{Sunny}) &= \frac{2}{3} \cdot 1 + \frac{1}{3} \cdot 0 \\&= \frac{2}{3}\end{align*}

현재 상태가 Cloudy일 때의 기대보상은

\begin{align*}r_{\pi}(\text{Cloudy}) &= \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 0 \\&= \frac{1}{2}\end{align*}

기대보상을 다음과 같이 표현할 수 있다.

r_{\pi} = \begin{pmatrix} \frac{2}{3} \\[5pt] \frac{1}{2} \end{pmatrix}

이전에 마르코프 체인의 정상분포를 구한 결과는

d_{\pi} = \begin{pmatrix} \displaystyle\frac{3}{5} & \displaystyle\frac{2}{5} \end{pmatrix}

이였다.

정책 \(\pi\)를 따랐을 때의 장기적인 평균보상은

\begin{align*}g_{\pi} &= d_{\pi}(\text{Sunny}) r_{\pi}(\text{Sunny}) + d_{\pi}(\text{Cloudy}) r_{\pi}(\text{Cloudy}) \\&= \frac{3}{5} \cdot \frac{2}{3} + \frac{2}{5} \cdot \frac{1}{2} \\&= \frac{2}{5} + \frac{1}{5} \\&= \frac{3}{5} \\&= 0.6\end{align*}

이다. 따라서 정책 \(\pi\)를 장기간 수행하면 한 번의 상태 전이마다 평균적으로 0.6의 보상을 얻는다는 의미이다.

정리

평균이 많이 등장하여 정리한다.

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

는 상태 s에 대한 평균 보상이고

\sum_{s} d_{\pi}(s) r_{\pi}(s)

는 각 상태의 기대보상을 정책 \(\pi\)를 따랐을 때의 받는 평균보상(정책의 가치)이다.

마무리

평균보상은 정책의 장기 성능을 하나의 값으로 나타낼 수 있지만, 이를 위해서는 정책이 만드는 마르코프 체인이 에르고딕하여 정상분포가 유일하고 초기 상태와 무관하게 수렴해야 한다.

그러나 현실의 많은 강화학습 문제는 이러한 조건을 만족하지 않는다. 예를 들어 게임 오버, 로봇의 넘어짐, 목표 지점 도착처럼 과제가 종료되는 문제에는 보통 종료 상태가 존재한다. 이 상태에 도달하면 이전 상태로 다시 돌아갈 수 없으므로 체인이 여러 영역으로 나뉘며 에르고딕하지 않을 수 있다.
이러한 문제를 억지로 무한 시간까지 확장한다 하더라도 종료 이전의 보상과 행동이 전체 시간에서 차지하는 비중은 점차 0이 된다. 그 결과 평균보상은 목표에 얼마나 빠르고 안전하게 도달했는지, 보상을 얼마나 일찍 얻었는지와 같은 과정과 시점의 차이를 충분히 반영하지 못한다.

따라서 에르고딕성을 요구하지 않으면서도 종료되는 문제에서는 종료 시점까지 받은 보상의 합으로 정책을 평가하고 종료되지 않고 계속되는 문제에서도 평가 가능한 방법이 있는데 이 방식이 바로 할인보상 방식(discounted reward)이다.

다음 시간에는 이러한 할인보상 방식을 바탕으로, 상태전이와 보상을 함께 표현하는 MRP(Markov Reward Process) 를 먼저 살펴본다. 이후 여기에 에이전트의 행동 선택을 추가한 MDP(Markov Decision Process) 로 확장하여, 상태가치함수와 정책평가가 어떻게 정의되는지 알아본다.