강화학습(reinforcement learning)이란?

개요

강화학습(reinforcement learning)은 머신러닝의 한 종류로 어떠한 환경에서 어떠한 행동을 했을 때 그것이 잘 된 행동인지 잘못된 행동인지를 나중에 판단하고 보상(또는 벌칙)을 줌으로써 반복을 통해 스스로 학습하게 하는 분야입니다.

강화학습에는 다음과 같이 두 가지 구성 요소로 환경(environment)과 에이전트(agent)가 있습니다.

강화학습의 개념도

에이전트는 특정 환경에서 행동(action)을 결정하고 환경은 그 결정에 대한 보상을 내립니다. 이 보상은 행동 즉시 결정되기보다는 여러 행동들을 취한 후에 한꺼번에 결정되는 경우가 많습니다. 특정 행동을 취했을 때 바로 그 행동에 대한 평가를 내릴 수 없는 경우가 많기 때문입니다.

강화학습은 앞서 다룬 딥러닝과 밀접한 관계가 있습니다. 에이전트가 행동을 결정하고 환경이 주는 보상으로 스스로 학습할 때 주로 딥러닝에서 다룬 인공 신경망을 사용합니다. 환경과 에이전트의 상태 등을 입력값으로 인공 신경망이 행동을 결정하고 보상이 있으면 이전의 입력값과 행동들을 긍정적으로 학습합니다.

강화학습의 기초가 된 마르코프 의사 결정 과정

강화학습은 마르코프 의사결정 과정(Markov decision process, MDP)에 학습의 개념을 넣은 것이라 할 수 있습니다. 그러므로 MDP에 대해 잘 이해하는 것이 강화학습 시스템 개발에 있어 중요합니다. 그럼 MDP를 포함하여 강화학습의 주요 이론을 살펴보겠습니다.

마르코프 가정

마르코프 가정(Markov assumption)은 상태가 연속적인 시간에 따라 이어질 때 어떠한 시점의 상태는 그 시점 바로 이전의 상태에만 영향을 받는다는 가정입니다. 현재의 상태가 바로 이전 상태에만 영향을 받는다고 가정하는 것이 어떻게 보면 무리한 가정일 수 있습니다. 그러나 직관적으로 생각해 보면 현재 상태는 이전 상태에 가장 큰 영향을 받고, 이전 상태는 그 이전 상태에 큰 영향을 받고, 더 이전의 상태들도 이러한 식으로 그보다 이전 상태에 가장 큰 영향을 받는다고 생각하면 그래도 합리적인 가정이라고 볼 수 있습니다. 결정적으로 마르코프 가정으로 어려운 문제들을 단순화하고 만족스러운 결과를 얻는 경우가 많습니다.

마르코프 가정의 수식은 다음과 같습니다.

$$\mathbb{P}(S_t|S_1,S_2,\dots,S_{t-1})=\mathbb{P}(S_t|S_{t-1})$$

위 수식에서 좌변은 어떠한 시점 $t$에서의 상태 $S_t$는 최초의 상태 $S_1$에서 바로 이전의 상태 $S_{t-1}$까지에 영향을 받는다는 뜻입니다. 이는 연속적으로 존재하며 일어나는 일련의 상태들을 확실하게 표현하지만 이를 실제로 계산하기는 매우 어렵습니다. 그래서 상태 $S_t$는 바로 이전 상태인 $S_{t-1}$에 가장 큰 영향을 받고 $S_{t-1}$에서 $S_{t-2}$를 반영하는 등 연쇄적으로 모든 이전 상태들이 반영된다고 가정하는 마르코프 가정을 적용하면 위 수식의 우변과 같이 단순화할 수 있습니다.

마르코프 과정

마르코프 과정(Markov Process)은 마르코프 가정을 만족하는 연속적인 일련의 상태입니다. 마르코프 과정은 일련의 상태 $$와 상태 전이 확률(state transition probability) $P$로 구성됩니다.

상태 전이 확률 $P_{s,s'}=\mathbb{P}(S_{t+1}=s'|S_t=s)$은 어떠한 상태가 i일 때 그 다음 상태가 j가 될 확률을 의미합니다. 여기서 $\mathbb{P}(A|B)$는 조건부 확률로 $B$일 때 $A$일 확률을 의미합니다. 마르코프 가정을 반영했기 때문에 이렇게 계산 가능한 상태 전이 확률을 정의할 수 있는 것입니다.

마르코프 의사 결정과정

마르코프 의사 결정과정(Markov decision process, MDP)은 마르코프 과정을 기반으로 한 의사 결정 모델입니다. MDP는 아래 수식과 같이 상태(state) 집합 $S$, 행동(action) 집합 $A$, 상태 전이 확률(state transition probability) 행렬 $P$, 보상(reward) 함수 $R$, 할인 요인(discount factor) $\gamma$로 구성되어 있습니다.

$$MDP=(S,A,P,R,\gamma)$$

상태 집합은 MDP에서 가질 수 있는 모든 상태의 집합 S={s_1,s_2,…,s_|S|}입니다. 아래 식과 같이 어떠한 시점에서의 상태 S_t는 상태 집합 S에 포함된 특정 상태가 됩니다.

$$S_t=s,s \in S$$

행동 집합은 행동 주체인 에이전트가 할 수 있는 모든 행동들의 집합 $A={a_1,a_2,\dots,a_{|A|}}$입니다. 에이전트는 어떠한 시점에서 행동 $A_t=a,a \in A$를 취하는 것입니다. MDP에서의 상태 전이 확률은 마르코프 과정의 상태 전이 확률보다 조금 더 복잡합니다. MDP에서의 상태 전이 확률 수식은 아래와 같습니다.

$$P_{s,s'}^a=\mathbb{P}(S_{t+1}=s'|S_t=s,A_t=a)$$

$P_{s,s'}^a$는 에이전트가 어떠한 상태 $s$에서 행동 $a$를 취했을 때 상태 $s'$으로 변할 확률입니다.

보상 함수는 에이전트가 어떠한 상태에서 취한 행동에 대한 보상을 내리기 위한 함수입니다. 그 수식은 아래와 같습니다.

$$R_s^a=\mathbb{E}[R_{t+1}|S_t=s,A_t=a]$$

보상 함수 $R_s^a$ 상태 $s$에서 행동 $a$를 했을 때의 보상의 기대값을 수치로 반환합니다.

할인 요인은 과거의 행동들을 얼마나 반영할지를 정하는 값으로 0에서 1 사이의 값입니다. 과거 5번의 행동에 대한 보상을 1씩 받았다고 했을 때 할인 요인 $\gamma$이 1이면 $<1, 1, 1, 1, 1>$이 되고 할인 요인 $\gamma$이 0.9이면 $<1, 0.9, 0.81, 0.729, 0.6561>$이 됩니다. 즉 먼 과거에 대한 보상일수록 깎아서 반영하는 것입니다.

에이전트는 어떠한 상태 $s$에서 수행할 행동 $a$를 정해야 하는데 이를 정책(policy)라고 합니다.

$$\pi(a│s)=\mathbb{P}(A_t=a|S_t=s)$$

정책 $\pi$는 총 보상을 최대화하는 방향으로 갱신되어 갑니다. 다음과 같은 MDP의 간단한 예로 위의 설명들을 정리해 보겠습니다.

MDP 예제의 상태 집합과 행동 집합

이 예제는 에이전트가 위, 오른쪽, 아래, 왼쪽으로 움직이면서 출발점에서 목적지까지 함정을 피하면서 도착하는 것을 목표로 합니다. 상태 전이 확률은 에이전트가 행동하는 대로 다음 상태로 움직일 수 있도록 정해져 있다고 가정합니다. 예를들어 $P_{s_1,s_2}^{a_2}=1$로, $s_1$에서 $a_2$를 수행하면 $s_2$가 됩니다.

에이전트는 정책 $\pi$에 따라서 행동을 결정하고 함정에 다다르면 -0.1을 보상으로 주고 목적지에 다다르면 1을 보상으로 주어 정책을 조정해 나갑니다.

출발점 $s_1$에서 $a_2$, $a_2$를 취하여 $s_3$가 되면 -0.1을 보상으로 주는데, 이때 다음과 같이 $\pi(a_2 |s_1)$과 $\pi(a_2│s_2)$의 값을 다시 똑같이 함정에 빠지지 않는 방향으로 갱신합니다.

$$\pi(a_2│s_1)=\pi(a_2|s_1)\times(1-0.1 \times 0.9)$$ $$\pi(a_2│s_2)=\pi(a_2|s_2)\times(1-0.1)$$

$s_2$에서 $s_3$으로 이동한 것이 가장 최근 행동이기 때문에 보상을 그대로 주고 그 전의 행동인 $s_1$에서 $s_2$로 이동한 것은 할인 요인을 곱하여 보상을 반영합니다. 함정이 아니라 목적지에 다다르게 되면 취했던 행동들의 확률 값을 높이게 됩니다.

이런 식으로 경험을 쌓다 보면 정책이 함정을 피하면서 목적지로 갈 수 있도록 조정되게 됩니다.

상태 가치 함수와 상태-행동 가치 함수

상태 가치 함수(state-value function)

에이전트가 어떠한 행동을 수행하면서 상태가 시간에 따라 변하게 됩니다. 이 때 보상을 받게 되고 시간에 따라 할인된 보상을 더해서 얻게되는 가치는 다음과 같이 표현할 수 있습니다.

$$V_\pi(s)=\mathbb{E}[\sum_{i=0}\gamma^iR_{t+i+1}|S_t=s]$$

정책 $\pi$에 의해서 행동들이 결정되고 결정된 행동들에 의해서 상태들도 정해집니다. 상태 가치 함수는 현재 상태 $s$에서 정책 $\pi$를 따랐을 때의 가치를 반환합니다.

상태-행동 가치 함수(action-value function)

상태-행동 가치 함수는 어떠한 상태 $s$에서 행동 $a$를 수행했을 때의 가치를 반환합니다. 상태-행동 가치 함수는 Q-value라고도 합니다. 어떠한 상태 $s$에서 행동 $a$를 수행했을 때 획득할 총 보상의 기대값입니다.

$$Q_\pi(s,a)=\mathbb{E}[\sum_{i=0}\gamma^iR_{t+i+1}|S_t=s,A_t=a]$$

수식을 보면 상태 가치 함수에서 행동 $a$에 대한 조건이 추가되었음을 알 수 있습니다. 상태-행동 가치 함수는 현재 상태 $s$에서 정책 $\pi$를 따라 행동 $a$를 수행했을 때의 가치를 의미합니다.

벨만 방정식(Bellman equation)

벨만 방정식은 위에서 다룬 상태 가치 함수와 상태-행동 가치 함수의 관계를 나타내는 방정식입니다. 벨만 방정식에는 벨만 기대 방정식(Bellman expectation equation)과 벨만 최적 방정식(Bellman optimality equation)가 있습니다.

벨만 기대 방정식(Bellman expectation equation)

벨민 기대 방정식으로 상태 가치 함수와 상태-행동 가치 함수를 기대값 E로 표현할 수 있습니다. 상태 가치 함수의 벨만 기대 방정식은 다음과 같이 표현됩니다.

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

현재 상태 $S_t$에서의 가치는 다음 상태 $S_{t+1}$의 가치에 할인율 $\gamma$를 곱하여 더한 기대값이라는 의미입니다.

상태-행동 가치 함수의 벨만 기대 방정식은 다음과 같습니다.

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

현재 상태 $S_t$에서 행동 $A_t$를 수행하면 기대 보상 $R_{t+1}$에다가 다음 상태 $S_{t+1}$와 행동 $A_{t+1}$의 상태-행동 가치에 할인율을 곱한 값을 더한 것이라는 의미입니다.

상태 가치 함수에서 이 기대값을 다음과 같이 정책 $\pi$를 따르는 상태-행동 가치 함수로 바꿔 표현해 볼 수 있습니다.

$$V_\pi (s)= \sum_{a\in A}\pi(a│s) Q_\pi (s,a)$$

상태 $s$에서 정책 $\pi$에 의해 행동 $a$를 선택할 확률과 상태 $s$에서 $\pi$에 따라 행동 $a$를 수행했을 때의 가치를 곱하여 더한 것입니다. 이 수식에서 상태-행동 가치 함수 역시 상태 가치 함수로 다시 풀어볼 수 있습니다.

$$Q_\pi (s,a)=R_s^a+\gamma \sum_{s'\in S}P_{s,s'}^a V_\pi (s')$$

현재 상태 $s$에서 행동 $a$를 수행했을 때 기대 보상과 다음 상태 $s'$에 대한 기대 가치를 상태 전이 확률과 함께 곱하여 더하고 거기에 할인율을 붙인 값을 더한 것입니다.

이 수식을 위의 상태 가치 함수에 대입해보면 다음과 같습니다.

$$V_\pi (s)= \sum_{a\in A}\pi(a│s)(R_s^a+\gamma \sum_{s'\in S}P_{s,s'}^a V_\pi (s'))$$

이렇게 가치 함수 수식에서 모호한 기대값 표현 E를 덜어내고 재귀적으로 표현하게 되었습니다.

비슷한 방식으로 상태-행동 가치 함수도 재귀적으로 표현해 보면 다음과 같습니다.

$$Q_\pi (s,a)=R_s^a+\gamma \sum_{s'\in S}P_{s,s'}^a \sum_{a'\in A}\pi(a'│s') Q_\pi (s',a')$$

이렇게 상태 가치 함수와 상태-행동 가치 함수를 벨만 방정식을 통해 재귀적으로 풀어보았습니다.

벨만 최적 방정식(Bellman optimality equation)

최적의 상태 가치와 최적의 상태-행동 가치를 다음과 같이 표현할 수 있습니다. 최적 가치란 의미는 가장 큰 총 보상을 받을 수 있는 정책을 따랐을 때 얻을 가치를 뜻합니다.

$$V_ (s)=\max_\pi⁡V_\pi (s)$$ $$Q_ (s,a)=\max_\pi⁡Q_\pi (s,a)$$

$V$와 $Q$에 별(*)을 붙여서 최적 가치임을 표현했습니다.

벨만 최적 방정식으로 최적 상태 가치와 최적 상태-행동 가치를 다음과 같이 표현합니다.

$$V_ (s)=\max_a⁡ R_s^a+\gamma \sum_{s'\in S}P_{s,s'}^a V_ (s')$$ $$Q_ (s,a)=R_s^a+\gamma \sum_{s'\in S}P_{s,s'}^a V_ (s')$$

MDP를 위한 동적 프로그래밍(dynamic programming)

다룬 벨만 방정식을 이용하여 MDP를 푸는 동적 프로그래밍을 알아보겠습니다. 동적 프로그래밍(dynamic programming, DP)은 재귀적인 최적화 문제를 푸는 방법입니다.

DP는 정책 반복(policy iteration)과 가치 반복(value iteration)으로 이루어져 있습니다.

정책 반복(policy iteration)

정책 반복에서는 다음과 같이 상태 가치 함수를 반복적으로 갱신합니다.

$$V_{k+1} (s)= \sum_{a\in A}\pi(a│s)(R_s^a+\gamma \sum_{s'\in S}P_{s,s'}^a V_k (s'))$$

여기서 k는 반복 과정을 의미합니다. N번 반복하면서 가치함수 $V$를 갱신하여 $V_1$, $V_2$, …, $V_N$을 생성합니다. 벨만 기대 방정식과 같은 형태입니다.

위의 MDP 예제를 다시 가져오겠습니다. 다음은 3x3 그리드 영역에서의 정책을 보여줍니다.

DP 정책 예제

처음에는 모든 상태에서 모든 행동을 동일한 확률 0.25로 수행할 수 있도록 했습니다. 할인율은 적용하지 않았습니다. 즉 $\gamma=1$입니다.

함정에 도달하는 경우 -0.1을, 목적지에 도달하는 경우 1을 보상으로 부여합니다. 이제 상태 가치 함수를 반복적으로 갱신하면 어떻게 되는지 살펴보겠습니다.

다음은 정책 반복 과정에서의 상태 가치 함수가 어떻게 변하는지 보여줍니다.

정책 반복에서의 상태 가치 함수 변화

이렇게 상태 가치 함수를 갱신하고 정책 역시 갱신합니다. k=8일 때 정책을 다음과 같이 갱신할 수 있습니다.

상태 가치 함수 기반 정책 갱신

상태 가치 함수 기반 정책 갱신 같은 가치를 가지는 다음 상태가 있으면 동일한 확률을 부여하여 가장 높은 가치를 가지는 상태로 이동하도록 합니다. 가치 반복(value iteration) 가치 반복은 정책 반복과 유사합니다. 차이점은 우선 가치 반복의 수식을 보고 알아보겠습니다.

$$V_{k+1}(s)=\max{a \in A}⁡ R_s^a +\gamma\sum_{s' \in S} P_{s,s'}^a V_k(s')$$

정책 반복에서는 다음 상태들 가치를 정책 함수의 확률과 곱하여 모두 더했는데 가치 반복에서는 탐욕적으로 가장 큰 다음 가치를 선택합니다. 수식을 보면 벨만 최적 방정식이라는 것을 알 수 있습니다. 정책 반복에서는 상태 가치 함수를 갱신하고 이후에 정책을 갱신했는데, 가치 반복에서는 따로 정책을 갱신하는 단계가 없습니다. 가치 반복에서는 현재의 정책이 최적이라고 가정하고 보상의 최대값을 취하게 됩니다.

다음은 위의 동일한 예제에서 가치 반복의 상태 가치 함수가 어떻게 변하는지 보여줍니다.

가치 반복에서의 상태 가치 함수 변화

동적 프로그래밍의 한계와 강화학습이 필요한 이유

동적 프로그래밍은 MDP의 상태 전이 확률과 보상 함수가 주어져야 하기 때문에 현실적으로 상태 전이 확률과 보상 함수를 미리 알 수 없는 대부분의 현실 문제(real-world problem)에서 젹용하기가 어렵습니다.

문제가 정말 잘 정의가 되어 있어서 상태 전이 확률과 보상 함수를 알고 있더라도 상태의 수가 많아지면 현실적으로 벨만 방정식을 풀기 어려워 집니다.

그렇기 때문에 상태 전이 확률과 보상 함수를 미리 알 수 없고 상태가 무한한 대부분의 현실 문제에서 동적 프로그래밍을 적용하기가 어렵습니다. 다음 장부터 본격적으로 다루게 될 강화학습으로 문제에 접근하면 이러한 단점을 극복할 수 있습니다.

주요 강화학습 개념

강화학습은 MDP의 개념과 큰 차이는 없습니다만 복잡한 문제를 스스로 풀기 위해서 다음과 같은 특징을 가집니다.

• 완전한 상태 전이 확률과 보상 함수를 미리 알 수 없다.
• 상태 집합이 (거의) 무한하다.

앞서 설명한 MDP에서는 상태가 불연속적(discrete)이였습니다. 그러나 강화학습를 적용하는 대부분의 문제들은 상태가 연속적(continuous)이어서 가능한 상태의 수가 매우 많습니다. 예를 들어 두 개의 실수로 구성할 수 있는 공간은 $R^2$으로 무한합니다. 상태를 구성하는 요소 개수가 많아질수록 그 공간은 방대해지는 것입니다.

강화학습 표기법(notation)

이미 상태, 행동 등의 강화학습 용어를 MDP를 설명하면서 언급했지만 이들을 포함하여 강화학습 용어들을의 표기법을 다시 정리하고 넘어가겠습니다. - $s$: 상태; 강화학습 환경에서의 상태 - $a$: 행동; 에이전트가 수행할 수 있는 행동 - $P$: 상태 전이 확률 - $V$: 상태 가치 - $\pi$: 정책 - $Q$: 상태-행동 가치 함수 - $R$: 보상 함수

Model-based vs. Model-free

강화학습에서는 상태 전이 확률과 보상 함수를 미리 알 수 없다고 했습니다. MDP에서 이 상태 전이 확률과 보상 함수를 모델(model)이라 합니다.

MDP에서 상태 전이 확률과 보상함수를 정할 수 있는 경우 model-based라고 합니다. 상태, 행동 공간이 적고 미리 상태 전이 확률과 보상 함수를 알고 있는 경우에 해당합니다. 그래서 model-based로 풀 수 있는 문제는 제한적입니다. MDP와 동적 프로그래밍이 model-based에 해당합니다.

MDP 모델 없이 하는 강화학습을 model-free라고 합니다. 현실의 대부분의 문제들은 MDP로 풀기 어려워서 최근 주목받는 대부분의 강화학습 기법들은 model-free라고 할 수 있습니다.

예측(prediction)과 제어(control)

강화학습에서는 MDP 모델을 미리 알 수 없기 때문에 상태 가치 함수의 값을 예측합니다. 그리고 점점 더 그 예측이 정확해 지도록 제어합니다. 이러한 예측과 제어를 반복해 나가는 것이 강화학습이라 할 수 있습니다.

예측은 에이전트가 주어진 정책에 따라 환경과의 소통을 통해 상태 가치 함수를 학습시키는 것입니다. 강화 학습에서는 모든 상태에 대해서 가치를 판단할 수 없기 때문에 샘플링(sampling)을 합니다. 에이전트는 이런 샘플들을 경험을 하면서 환경을 학습합니다. 제어는 예측을 통해 학습한 가치 함수를 기반으로 정책을 학습하는 것입니다.

예측 방법에는 몬테카를로 예측(Monte-Carlo prediction)과 시간차 예측(temporal-difference prediction)을 들 수 있습니다. 제어의 대표적인 방법으로는 SARSA와 Q-learning을 들 수 있습니다. 이 방법들은 뒤에서 더 자세히 다루도록 하겠습니다.

부트스트랩(bootstrap)

부트스트랩(bootstrap)은 다음 상태에 대한 가치 함수 값으로 현재 상태의 가치 함수 값을 예측하는 방식입니다.

강화학습에서 종료 상태(terminal state)까지의 상태 전이가 진행된 것을 에피소드(episode)라고 합니다. 부트스트랩을 사용하면 에피소드가 진행되는 동안에 상태 가치 함수를 업데이트 할 수 있습니다. 뒤에서 부트스트랩을 사용하는 방법도 다룹니다.

On-policy vs. Off-policy

On-policy는 행동을 결정하는 정책(policy)과 학습할 정책이 같은 강화학습을 의미합니다. 반대로 Off-policy는 행동하는 정책과 학습하는 정책이 다른 방법입니다.

이 말을 다시 생각해 보면 On-policy 강화학습은 경험을 실컷 쌓아놓아도 정책이 업데이트되면 이 경험들을 학습에 사용할 수가 없습니다. 그러므로 데이터 효율 관점에서 Off-policy가 좋다고 볼 수 있습니다.

이용(exploitation)과 탐험(exploration)

이용(exploitation)은 현재 알고 있는 한 가장 최적의 행동을 선택하는 것을 의미합니다. “현재 알고 있는 한”이라는 말은 선택한 행동이 정말로 최적의 행동은 아닐 수 있음을 뜻합니다. 따라서, 탐욕(greedy)적으로 행동을 선택한다고도 합니다.

탐험(exploration)은 다양한 경험을 쌓기 위해 아무 행동을 선택해 보는 것을 의미합니다. 탐욕적으로만 행동을 선택하다 보면 정작 정말 최적인 행동을 전혀 선택하지 못할 수도 있습니다. 이러한 문제를 해결하기 위해 간혹 탐험을 하는 것입니다.

주요 강화학습 기법

주요 강화학습 기법으로는 몬테카를로 학습(Monte-Carlo learning, MC), 시간차 학습(temporal-difference learning, TD), Q-learning, 정책 경사(policy gradient, PG), Actor-Critic(AC), A2C(advantage actor-critic), A3C(asynchronous advantage actor-critic) 등이 있습니다.

이 책에서는 신경망으로 가치와 정책을 신경망을 통해 구하는 강화학습 기법만 다룹니다. 그러므로 Q-learning을 DQN으로 여기면 됩니다. 각 강화학습 기법에 대해서 이어서 살펴보겠습니다.

몬테카를로 학습(Monte-Carlo learning, MC)

몬테카를로 학습(Monte-Carlo learning)을 예측과 제어의 관점에서 살펴보겠습니다.

몬테카를로 예측(Monte-Carlo prediction)에서는 샘플링을 통해 상태 가치 함수를 학습해 나갑니다. 충분한 에피소드를 거치고 나면 상태 가치 함수가 정답에 가까워지게 될 것입니다.

샘플링한 상태들에 대한 경험을 통해 획득 보상(gain)을 다음과 같이 정의합니다.

$$G_t=R_{t+1}+\gamma R_{t+2}+⋯+\gamma^{n-1} R_{t+n}$$

상태 가치를 다시 획득 보상으로 표현해보면 다음과 같습니다.

$$V_{n+1}(s)=\frac{1}{n} \sum_{i=1}^n G_i=\frac{1}{n} (G_n+\sum_{i=1}^{n-1} G_i )=\frac{1}{n} (G_n+ (n-1) \frac{1}{n-1} \sum_{i=1}^{n-1} G_i )=V_n (s)+\frac{1}{n} (G_n-V_n(s))$$

이 수식을 보면 이전의 상태 가치 함수과 새로운 획득 보상과의 차이를 더해 줌으로써 상태 가치 함수를 업데이트 합니다. 여기서 이전의 상태 가치 함수와 새로운 획득 보상과의 차이를 오차라고 합니다. 이 오차에 곱해지는 $1/n$은 $\alpha$로 치환하여 학습 속도(learning rate)로 여깁니다. 이제 최종 수식을 다시 써보겠습니다.

$$V_{n+1}(s)=V_n(s)+\alpha(G_n-V_n(s))$$

딥러닝에서와 마찬가지로 학습 속도 $\alpha$를 너무 크게 정하면 최적 가치 함수로 수렴이 잘 안 될것이고 너무 작게 잡으면 학습이 너무 오래 걸릴 수 있습니다.

몬테카를로 예측에서 사용하는 총 획득 보상 $G$는 에피소드가 끝나야지 알 수 있기 때문에 에피소드 종료 시점에서 상태 가치 함수를 갱신할 수 있습니다.

몬테카를로 제어(Monte-Carlo control)는 상태 가치 함수 대신 상태-행동 가치 함수를 사용합니다.

$$Q(s,a) \leftarrow Q(s,a)+\alpha(G_n-Q(s,a))$$

이렇게 상태-행동 가치 함수 값이 높은 행동을 선택하고 어떠한 확률로 탐험을 진행할 수 있습니다.

시간차 학습(temporal-difference learning, TD)

시간차 학습(temporal-difference learning) 역시 예측과 제어의 관점에서 살펴보겠습니다.

몬테카를로 예측에서는 에피소드가 끝나야지 상태 가치 함수를 갱신할 수 있었습니다. 그렇기에 학습을 실시간으로 수행하기 어려운 단점이 있습니다. 시간차 예측(temporal-difference prediction, TD)을 활용하면 매 시간 단계(time step)마다 가치 함수를 업데이트 할 수 있습니다.

시간차 예측은 다음과 같이 가치 함수를 업데이트 합니다.

$$V(S_t) \leftarrow V(S_t)+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t))$$

몬테카를로 예측과 다르게 매 시간 단계 $t$에서 가치 함수를 갱신하게 됩니다. 이렇게 에피소드 중에 다음 상태의 가치 함수로 현재 상태의 가치 함수를 갱신하므로 TD는 부트스트랩을 사용한다 할 수 있습니다. 사실 동적 프로그래밍에서도 가치 함수를 매 시간 단계마다 갱신했었습니다. 그러므로 DP 역시 부트스트랩을 사용한다고 할 수 있습니다.

시간차 학습에서 제어는 On-policy이냐 Off-policy이냐에 따라 그 이름이 달라집니다. On-policy 시간차 제어(On-policy temporal-difference control)을 SARSA(state–action–reward–state–action)라고 하고 Off-policy 시간차 제어(Off-policy temporal-difference control)을 Q-learning이라 합니다. Q-learning은 뒤에서 보도록 하고 SARSA를 여기서 이어서 살펴보겠습니다.

TD에서 상태-행동 가치 함수를 적용하고 탐험(exploration)을 추가하여 제어하면 SARSA(state–action–reward–state–action)가 됩니다. 이름이 SARSA인 이유는 하나의 샘플이 현재 state, action, reward, 다음 state, 다음 action으로 구성되어 있기 때문입니다.

SARSA는 상태-행동 가치 함수 Q를 사용하는 방법입니다. 수식은 다음과 같습니다.

$$Q(s,a) \leftarrow Q(s,a)+\alpha(R_s^a+ \gamma Q(s',a')-Q(s,a))$$

상태-행동 가치 함수인 Q를 사용하였습니다. 그리고 행동을 결정할 때 어떠한 확률로 탐험을 수행합니다. SARSA는 다음 상태에 대한 행동을 알고 있어야 하기 때문에 행동을 결정하는 정책과 학습 정책을 분리할 수 없어서 On-policy 방식이라고 할 수 있습니다.

Q-러닝(Q-learning, QL)과 DQN(deep Q-network)

SARSA는 On-policy TD인 반면 Q-러닝(Q-learning)은 TD의 Off-policy 제어 방식입니다.

$$Q(s,a) \leftarrow Q(s,a)+\alpha(R_s^a+\gamma \max_{a'} ⁡Q(s',a')-Q(s,a))$$

다음 상태 $s'$에서 가장 큰 $Q$ 값을 이용하여 Q 함수를 갱신하게 됩니다. 행동을 결정할 때는 $Q$ 값이 높은 행동을 선택하면서도 충분한 탐험을 수행합니다. 탐험은 학습 초기에는 많이하고 학습 후반으로 갈수록 적게하는 기법을 많이 사용합니다.

여기서 Q 함수로 심층신경망을 사용하면 DQN(deep Q-network)이 됩니다. DQN은 회귀(Regression) 문제를 푸는 대표적인 강화학습으로 볼 수 있습니다.

정책 경사(policy gradient, PG)

정책 경사는 분류(classification) 문제를 푸는 강화학습으로 볼 수 있습니다. 어떠한 상태에서 어떠한 행동을 결정하는 것이 가장 좋을지를 판단하는 것입니다. 정책 경사도 어떠한 상태에서의 행동에 대한 확률 값들을 인공 신경망으로 모델링합니다.

Q-러닝에서는 Q 함수를 학습하고 $Q$ 값이 높은 행동을 취하는 방식이였습니다. 정책 경사에서는 행동의 확률을 학습하게 됩니다. 정책 경사에서 손실 함수는 다음과 같이 정할 수 있습니다.

$$L(\theta)=-\mathbb{E}[\nabla_\theta \log⁡ \pi_\theta (a|s) Q(s,a)]$$

여기서 $Q(s,a)$는 장기간의 보상을 고려한 상태 $s$에서 행동 $a$를 수행했을 때의 가치입니다. 정책 경사는 다양한 방식으로 손실 함수를 정할 수 있습니다. 다음에 이어서 살펴볼 Actor-Critic, A2C, A3C 등이 정책 경사 방식의 변형이라고 볼 수 있습니다.

Actor-Critic

Q-러닝이나 정책 경사는 단일 신경망을 이용한 강화학습 방식이였습니다. Actor-Critic은 Q-러닝과 정책 경사의 하이브리드(hybrid) 강화학습 모델이라고 볼 수 있습니다.

Actor는 정책 경사 모델을 사용하여 수행할 행동을 결정하고, Critic은 수행한 행동을 비평(criticism)하기 위해 Q-러닝 모델을 사용합니다. 이렇게 했을 때 단일 모델을 사용했을 때 발생하기 쉬운 고 분산(high variance) 문제를 피할 수 있습니다.

Actor-Critic의 구조를 다음과 같이 표현해 볼 수 있습니다.

Actor-Critic의 구조

이렇게 Actor-Critic은 Actor와 Critic이 신경망을 공유하며 강화학습을 수행합니다. 손실 함수는 다음과 같이 표현할 수 있습니다.

$$L(\theta)=-\mathbb E[\nabla_\theta \log⁡ π_\theta (a|s)Q_c (s,a)]$$

여기서 $Q_c$ 함수는 Critic의 신경망 출력입니다. Actor-Critic 방법에서는 정책 경사로 정책 신경망을 학습하면서 동시에 Q-러닝으로 상태-행동 가치 신경망을 학습합니다. 다만 효율적인 학습을 위해 두 신경망은 일부를 공유하고 있을 수 있습니다.

A2C(advantage actor-critic)

A2C는 Actor-Critic 방법에서 기대 출력을 Advantage로 사용하는 방법입니다. Advantage는 상태-행동 가치에서 상태 가치를 뺀 값입니다.

$$D(s,a)=Q(s,a)-V(s)$$

Advantage를 적용한 손실 함수는 다음과 같이 바뀌게 됩니다.

$$L(\theta)=-E[\nabla_\theta \log⁡ π_\theta (a|s)D(s,a)]$$

A2C에서는 Critic을 Advantage로 학습합니다. 이렇게 하면 어떠한 상태에서 행동이 얼마나 좋은지 뿐만 아니라 얼마나 더 좋아지는지를 학습할 수 있게 됩니다.

A3C(asynchronous advantage actor-critic)

A3C는 구글 딥마인드에서 발표한 대표적인 강화학습 방법 중 하나입니다. A3C는 A2C와 비슷하지만 그 이름에서도 알 수 있듯이 A2C에 비동기 개념을 추가한 방법입니다.

A3C는 에이전트가 여러개의 환경에서 동시에 행동을 수행하고 신경망을 학습해 나갑니다. 이렇게 여러 환경에서 동시에 신경망을 학습하기 때문에 비동기라 부르는 것입니다.

다음과 같이 여러 환경에서 행동을 수행하고 보상을 얻습니다. 그리고 비동기적으로 신경망을 업데이트합니다.

A3C의 구조

이렇게 여러 에이전트가 독립적으로 개별 환경에서 행동, 보상, 비평을 발생시켜 나가며 강화학습을 진행합니다. 이로써 더욱 다양한 경험을 통해 빠르고 효과적으로 학습할 수 있게 됩니다.

주요 강화학습 기법 정리

지금까지 마르코프 의사 결정과정(MDP), 동적 프로그래밍(DP), 몬테카를로 학습(MC), 시간차 학습(TD), 시간차 학습(TD), Q-러닝(QL), DQN, 정책 경사(PG), Actor-Critic(AC), A2C, A3C를 살펴보았습니다. 이들 강화학습 기법들의 강화학습 특징들을 표시해보면 다음 표와 같습니다.

표 3.1 강화학습 기법 정리

	MDP	DP	MC	TD(SARSA)	QL	DQN	PG	AC	A2C	A3C
Model-based	O	O
Model-free			O	O	O	O
Bootstrap		O		O	O	O		O	O	O
Exploration			O	O	O	O	O	O	O	O
On-policy			O	O
Off-policy					O	O	O	O	O	O
Value-based			O	O	O	O		O	O	O
Policy-based							O	O	O	O
DNN						O	O	O	O	O
Advantage									O	O
Asyncronous										O

이렇게 강화학습이 발전되 왔고 현재도 계속 발전 중입니다. 이 책에서는 심층신경망을 사용하는 DQN, PG, AC, A2C, A3C를 뒤에서 주식투자 도메인에서의 구현까지 계속 다루겠습니다.