벨만 방정식(Bellman Equation)

MDP 로 정의된 모델에서 누적 보상을 최대화 하기 위해서는 각 상태에서 최선의 행동을 선택하는 최적의 정책을 찾아야하며 이러한 최적의 정책은 즉각적인 현재 보상이 아닌 미래에 대한 평가를 나타내는 가치를 기준으로 행동을 선택해야 합니다. 따라서 가치를 계산하는 것은 강화 학습에서 중요한 문제이며 벨만 방정식을 통해 가치를 계산하는 방법을 알아보겠습니다.

벨만 방정식은 최적화 문제에서 가치 함수에 대해 이산 시간 $t$ 와 $t+1$ 간에 재귀적인 관계를 나타냅니다. 이러한 벨만 방정식은 벨만 기대 방정식과 벨만 최적 방정식으로 나누어집니다.

벨만 기대 방정식(Bellman Expectation Equation)

정책 $\pi$ 을 따르는 상태 가치 함수를 $v_\pi(s_t)$ 를 벨만 방정식의 형태로 풀어보면 다음과 같습니다.

$\begin{aligned}   

v_\pi(s) &\doteq \mathbb{E}_\pi[G_t|S_t=s] \\

&= \mathbb{E}_\pi[r_{t+1}+\gamma r_{t+2}+\gamma^2r_{t+3}+\cdots|S_t=s] \\   

&= \mathbb{E}_\pi[r_{t+1}+\gamma(r_{t+2}+\gamma r_{t+3}+\cdots)|S_t=s] \\  

&= \mathbb{E}_\pi[r_{t+1}+\gamma G_{t+1}|S_t=s] \\  

&= \mathbb{E}_\pi[r_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t=s] \\  

\end{aligned}$

행동 가치 함수 $q_{\pi(s,a)}$ 또한 비슷한 형태로 전개할 수 있습니다.

$\begin{aligned}    
q_\pi(s, a) &\doteq \mathbb{E}_\pi[G_t|S_t=s, A_t=a] \\ 

&= \mathbb{E}_\pi[r_{t+1}+\gamma r_{t+2}+\gamma^2r_{t+3}+\cdots|S_t=s, A_t=a] \\    

&= \mathbb{E}_\pi[r_{t+1}+\gamma(r_{t+2}+\gamma r_{t+3}+\cdots)|S_t=s, A_t=a] \\   

&= \mathbb{E}_\pi[r_{t+1}+\gamma G_{t+1}|S_t=s, A_t=a] \\   

&= \mathbb{E}_\pi[r_{t+1}+\gamma q_{\pi}(S_{t+1}, A_{t+1})|S_t=s, A_t=a] \\   
\end{aligned}$ 

가치 함수에 대해 기댓값 연산자를 포함하는 벨만 기대 방정식은 다음과 같습니다.

$v_{\pi}(s) \doteq \mathbb{E}_{\pi}[ r_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t=s ]$

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

또한 MDP 모델을 확실히 아는 상황에서는 계산하기 위한 형태의 식으로 변형할 수 있습니다. 

먼저 상태 가치를 행동 가치와의 관계로도 풀어낼 수 있습니다.

상태 $s$ 의 가치 $v_\pi(s)$ 는 취할 수 있는 행동에 대한 행동 가치 $q_{\pi}(s,a)$ 들의 합으로 구할 수 있습니다. 또한 정책을 고려하기 때문에 행동을 취할 확률을 곱하여 다음과 같이 나타낼 수 있습니다.

$v_{\pi}(s) = \displaystyle \sum_{a \in A} \pi(a|s) q_{\pi}(s,a)$

반대로 행동 가치 $q_{\pi}(s,a)$ 를 기준으로 풀어낼 수 있습니다.

상태 $s$ 에서 취한 행동에 대한 보상과 다음 상태의 가치로 나타낼 수 있습니다. 여기서는 다음 상태에 대한 전이 확률을 고려해야하며 다음과 같이 나타낼 수 있습니다.

$q_{\pi}(s,a) = \displaystyle \sum_{s' \in S} P_{ss'}^a \left[ r + \gamma v_{\pi}(s') \right] $

조금 더 뒤의 관계를 나타낼 수 있습니다.

위에서 얻은 식을 이용해서 순차적으로 전개하면 최종적으로 다음 형태가 됩니다.

$v_{\pi}(s) = \displaystyle \sum_{a \in A} \pi(a|s) \displaystyle \sum_{s' \in S} P_{ss'}^a \left[ r + \gamma v_{\pi}(s') \right]$

동일한 방식으로 행동 가치 함수도 다음 형태의 식을 얻을 수 있습니다.

$q_{\pi}(s,a) = \displaystyle \sum_{s' \in S} P_{ss'}^a \left[ r + \gamma \displaystyle \sum_{a' \in A} \pi(s'|a') q_{\pi}(s',a') \right]$

벨만 최적 방정식(Bellman Optimality Equation)

벨만 기대 방정식이 $v_{\pi}(s)$ 와 $q_{\pi}(s,a)$ 에 대한 수식이라면 벨만 최적 방정식은 $v_*(s)$ 와 $q_*(s,a)$ 에 대한 수식입니다.  다시 말하면 $v_\pi(s)$ 와 $q_\pi(s,a)$ 는 정책 $\pi$ 을 따르는 가치 함수이지만 $v_*(s)$ 와 $q_*(s,a)$ 는 최적 정책 $\pi_*$ 를 따르는 가치 함수인 것이고 최적 정책을 통해 계산된 가치 함수는 최적 가치 함수(optimal value function)인 것입니다.

최적 가치 함수는 다음과 같이 나타낼 수 있습니다.

$v_*(s) \doteq {\underset {\pi} {\text{max}} } \, v_{\pi}(s)$

$q_*(s,a) \doteq {\underset {\pi} {\text{max}} } \, q_{\pi}(s,a)$

많은 정책 중 최고의 정책을 따르는 가치 함수가 바로 최적 가치 함수라는 것입니다.

벨만 기대 방정식과는 무슨 차이가 있을까요?

벨만 기대 방정식에서는 정책 $\pi$ 를 따르기 때문에 취할 수 있는 행동들에 대해 기댓값을 계산한 것입니다. 하지만 벨만 최적 방정식은 최적 정책 $\pi_*$ 를 따르기 때문에 최적의 행동만을 고려하여 계산합니다.

따라서 상태 가치 함수와 행동 가치 함수의 관계는 다음이 성립하게 됩니다.

$\begin{aligned}  
v_*(s) & = {\underset {a \in \mathcal{A}(s)} {\text{max}} } \, q_{\pi_*}(s,a) \\  
& = {\underset {a} {\text{max}} } \, \mathbb{E}_{\pi_*}[G_t | S_t=s, A_t=a] \\ 
& = {\underset {a} {\text{max}} } \, \mathbb{E}_{\pi_*}[R_{t+1} + \gamma G_{t+1} | S_t=s, A_t=a] \\

& = {\underset {a} {\text {max}} } \, \mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1})| S_t=s, A_t=a] \\
& = {\underset {a} {\text {max}} } \displaystyle \sum_{s',r} p(s',r|s,a)[r + \gamma v_*(s')]
\end{aligned}$

최적 정책을 따르는 상태의 가치는 그 상태에서 최선의 선택으로 얻는 기댓값과 같다는 것입니다.

행동 가치 함수에 대한 벨만 최적 방정식은 다음과 같습니다.

$\begin{aligned}
q_*(s,a) & = \mathbb{E} \left[ R_{t+1} + \gamma {\underset {a'} {\text{max}} } \, q_*(S_{t+1},a') | S_t=s A_t=a \right] \\
& = \displaystyle \sum_{s',r} p(s',r|s,a) \left[ r + \gamma {\underset {a'} {\text{max}} } \, q_*(s',a') \right]
\end{aligned}$

마치며

벨만 방정식은 MDP 로 정의된 환경에서 가치를 계산하기 위한 것으로 가치 함수 $v_{\pi}$ 의 정의에서 유도했습니다. 이러한 벨만 방정식을 이용하면 $t$ 와 $t+1$ 의 시점에서 바로 계산할 수 있으며 이를 무한히 반복하면 기댓값에 수렴하는 것입니다.

또한 벨만 방정식은 벨만 기대 방정식과 벨만 최적 방정식으로 나누어집니다. 정책 $\pi$ 에 대한 가치 함수 $v_{\pi}$ 를 계산할 때는 벨만 기대 방정식을 이용하고 이는 정책 $\pi$ 를 평가하는 것과 같습니다. 최적 정책 $\pi_*$ 에 대한 최적 가치 함수 $v_*$ 를 계산할 때는 벨만 최적 방정식을 사용합니다.

마르코프 프로세스(Markov Process, MP)

마르코프 프로세스는 마르코프 특성(markov property)을 지니는 이산 시간 확률 과정입니다.

위의 마르코프 프로세스 모델은 6개의 상태와 각 상태에서 다음 상태로 전이될 확률을 가지고 있습니다. 또한 시간의 흐름에 따라 상태가 전이됩니다. 그 과정을 살펴보면 Pause 에서 시작하여 Stage 1 로 상태가 전이될 확률은 0.7, 가만히 있을 확률은 0.3입니다. 여러 과정을 거쳐 Stage 2 에서 0.7의 확률로 Win 으로 전이되고 1.0의 확률로 종료 상태(terminal state)인 Stop 에 도달하여 프로세스는 종료됩니다.

마르코프 프로세스는 상태의 집합 $S$ 와 전이 확률 행렬 $P$ 로 정의할 수 있습니다.

$MP \equiv (S,P)$

상태의 집합 $S$ 는 유한한 상태들의 집합입니다.

$S = \{s_0, s_1, s_2, \dots\}$ 

전이 확률 행렬 $P$ 는 다음과 같습니다.

$P_{ss'} = \mathbb{P}[S_{t+1} = s' | S_t = s]$

어떤 상태 $s$ 에서 다음 상태 $s'$ 로 변화하는 것을 상태 전이(state transition)라고 하며 그 확률을 전이 확률(transition probability)이라고 합니다. 또한 어떤 상태에서 다음 상태 전이 확률들의 합은 100% 입니다.

마르코프 프로세스의 상태 집합 $S$ 에 대한 전이 확률 행렬(transition probability maxtrix)은 다음과 같습니다. 

마르코프 특성(Markov Property)

마르코프 특성은 다음과 같이 정의됩니다.

$\mathbb{P}[s_{t+1}|s_t]=\mathbb{P}[s_{t+1}|s_1, s_2, ..., s_t]$

미래는 현재에 의해서만 결정된다는 의미로 마르코프 프로세스에서 다음 상태가 $s_{t+1}$ 이 될 확률은 현재 상태 $s_t$ 로 충분하며 $s_t$ 이전에 방문했던 상태 $s_1, s_2, ...$ 에 대한 정보는 다음 상태 $s_{t+1}$ 에 도달하는 데 영향을 주지 못한다는 것입니다.

동전 던지기를 예로 들어보면 동전을 던져 앞면이 5번 연속으로 나왔다고 가정합니다. 다음에 동전을 던지면 뒷면이 나올 확률이 높을 것 같지만 항상 뒷면이 나올 확률은 50% 입니다.

이것과 같이 마르코프 특성을 만족하는 상태를 마르코프한 상태라고 합니다.

이번에는 반대의 예를 들어봅니다. 운전을 하는 환경에서 운전자 시점의 사진 한장이 주어집니다. 그런데 현재 상태에서 사진 한장의 정보로는 차가 앞으로 가는지 뒤로 가는지 알 수 없습니다. 이 같은 상황은 마르코프하지 않은 상태로 볼 수 있습니다. 이전 사진들의 정보도 같이 주어진다면 조금 더 마르코프한 상태로 만들 수 있을 것입니다.

마르코프 보상 프로세스(Markov Reward Process, MRP)

마르코프 프로세스에 보상 함수 $R$ 과 감쇠 $\gamma$ 라는 개념이 추가되면 마르코프 보상 프로세스를 정의 할 수 있습니다. 

$MRP \equiv (S,P,R,\gamma)$

마르코프 보상 프로세스 모델은 각 상태에 도달하게되면 보상을 받습니다.

보상 함수 $R$ 은 어떤 상태 $s$ 에 도달했을 때 받는 보상으로 정의합니다.

$R=\mathbb{E}[R_t|S_t=s]$

MRP 에서는 연속된 상태 전이 과정을 통해 다음과 같은 궤적(trajectory)이 만들어 질 것입니다.

$s_t, R_t, s_{t+1}, R_{t+1}, s_{t+2}, R_{t+2}, \dots, s_T, R_T $

이러한 시점 $t, \dots, T$ 의 과정을 에피소드(episode)라고 하며 환경에 따라 종료되는 에피소드를 다루는 작업을 에피소딕 작업(episodic task), 주식과 같이 에피소드가 종료되지 않는 경우는 연속적인 작업(continuous task)이라고 합니다.

시점 $t$ 이후에 연속된 보상을 $R_{t+1}, R_{t+2}, R_{t+3}, \dots$ 으로 나열하고 이를 이용해서 누적 보상을 나타내는 리턴(return)을 정의하면 다음과 같습니다.

$G_t \doteq R_{t+1} + R_{t+2} + R_{t+3} + \cdots + R_T $ 

위의 식은 그대로 사용하기에는 무리가 있습니다. continuous task 인 경우 값이 계속 더해지면 무한히 커지는 문제도 있고 미래에 대한 불확실성과 같은 요소를 표현할 수 있는 감쇠(discounting)라는 개념이 나오게 됩니다. 이를 이용하여 다시 한번 정의하면 다음과 같습니다.

$G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \displaystyle \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$

감쇠 인자는 $0<\gamma<1$ 의 범위를 가지며 보상은 1로 하여 식을 전개하면 감쇠된 리턴값은 유한하다는 것을 알 수 있습니다.

$G_t = \displaystyle \sum_{k=0}^\infty \gamma^k = { 1 \over 1-\gamma }$

감쇠 인자 $\gamma$ 는 $0<\gamma<1$ 범위를 가지며 현재 상태에서 미래에 얻을 보상에 대해 얼마나 더 중요하게 여길 것인지를 나타내는 파라미터입니다.

또한 리턴을 이용해 상태에 대한 가치(state value)를 정의할 수 있으며 이를 함수로 표현한 것을 상태 가치 함수(state value function)라고 합니다. 상태 가치 함수는 입력으로 상태를 넣으면 가치를 출력해주는 함수이며 상태 $s$ 에서 시점 $t$ 이후로 얻는 리턴의 기댓값으로 정의됩니다.

$v(s)=\mathbb{E}[G_t|S_t=s]$

상태 $s$ 의 가치는 상태 $s$ 에서부터 여러 경로의 에피소드를 통해 나온 리턴들의 합으로 구할 수 있는 것입니다.

마르코프 결정 프로세스(Markov Decision Process)

앞에서 알아본 MP 와 MRP 에서는 시간의 흐름에 따라 상태 전이가 자동으로 이루어 집니다.

MRP 에서 행동의 집합 $A$ 의 개념이 추가되면 MDP 를 정의할 수 있습니다.

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

MDP 모델은 행동이 추가되었기 때문에 행동을 선택하며 학습을 하는 주체인 에이전트를 포함할 수 있게 됩니다. 에이전트는 각 상태마다 행동을 취하고 그 행동에 의해 상태가 전이되며 보상을 받습니다.

MRP 와 비교하여 추가된 행동으로 인해 전이 확률은 $P_{ss'}^a$ 로 나타내며 현재 상태 $s$ 에서 에이전트가 행동 $a$ 를 취하여 다음 상태 $s'$ 로 전이될 확률을 나타냅니다. 또한 보상 함수는 $R_s^a$ 로 나타내어 상태 $s$ 에서 행동 $a$ 를 취해서 받는 보상으로 정의합니다. 

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

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

강화 학습의 목적은 누적 보상을 최대화하는 것이고 각 상태마다 누적 보상이 최대가 되는 방향으로 행동을 선택해야 할 것입니다. 각 상태에 따라 행동을 선택하는 것을 정책(policy)이라는 개념을 통해 나타낼 수 있습니다. 

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

이는 입력으로 상태 $s$ 와 행동 $a$ 를 넣으면 $a$ 를 선택할 확률을 출력하는 함수입니다.

상태와 행동은 MDP 모델에 정의되어 있는 정보지만 정책은 에이전트에 정의되어 있는 것으로 학습을 통해 개선되어야 하는 것입니다. 

정책을 개선(improvement)하기 위해서는 먼저 평가(evaluation)를 해야합니다.

그렇다면 정책을 어떻게 평가할 수 있을까요? 

바로 상태 가치 함수를 통해 정책을 평가할 수 있습니다.

$v_\pi(s)=\mathbb{E}_\pi[G_t|S_t=s]$

상태 $s$ 에서 정책 $\pi$ 에 의해 얻는 리턴의 기댓값입니다. MRP 에서 알아본 가치 함수 $v(s)$ 와는 다른 것입니다. $v(s)$ 는 MRP 에 정의되어 있는 전이 확률에 의해 발생되는 여러 에피소드의 리턴을 이용하여 기댓값을 구하지만 $v_\pi(s)$ 는 행동 정책 $\pi$ 에 의해서 얻은 리턴들의 기댓값을 구하는 것입니다. 따라서 가치 함수 $v_\pi(s)$ 는 정책 $\pi$ 에 의존적인 것으로 $v_\pi(s)$ 를 구하는 것으로 정책을 평가할 수 있는 것입니다. 단순하게 상태 $s$ 에서 상태 가치가 $v_{\pi_1}(s) < v_{\pi_2}(s)$ 라면 정책을 $\pi_2$ 로 수정하는 것으로 정책이 개선되었다고 할 수 있는 것입니다.

또한 행동에 대한 가치 함수인 상태 행동 가치 함수(state action value function)를 정의할 수 있습니다.

$q_\pi(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a]$

이는 정책 $\pi$ 에 의한 상태 $s$ 에서 행동 $a$ 에 대한 리턴의 기댓값으로 각 상태에서 취할 수 있는 행동에 대한 가치를 계산하는 것입니다. 이를 통해 얻을 수 있는 이점은 특정 상태 $s$ 에서 행동 가치가 높은 행동 $a$ 를 선택한다면 최선의 선택일 것입니다.

강화 학습(Reinforcement Learning)

순차적 의사 결정(squential decision making) 문제에서 누적 보상을 최대화하기 위해 시행착오(trial-and-error)를 통해 행동을 교정하는 과정을 말합니다.

기계 학습은 크게 지도 학습, 비지도 학습, 강화 학습으로 나눌 수 있습니다.

지도학습은 정답(label)이 있는 데이터셋을 이용하여 학습하는 것이며 반대로 비지도 학습은 정답이 존재하지 않으며 데이터가 가진 특성(feature)을 기반으로 데이터의 구조를 찾는 것이라고 할 수 있습니다.

그에 반해 강화 학습은 지도 학습처럼 정답이 있지 않으며 비지도 학습처럼 데이터만을 기반으로 하지 않습니다. 강화 학습은 의사 결정을 하며 학습하는 주체인 에이전트(Agent)가 있고 풀고자하는 문제 혹은 대상에 해당하는 환경(Environment)의 상호작용을 통해 누적 보상을 최대화하는 방향으로 학습합니다.

이에 따라 강화 학습이 갖을 수 있는 어려운 점은 행동을 선택하는 에이전트는 탐색(exploration)과 활용(exploitation) 사이를 절충하는 것입니다. 에이전트는 보상을 얻기 위해 이미 경험한 행동들에 대해 활용해야 하지만 미래에 더 좋은 행동을 선택하기 위해 탐색을 해야하는 것입니다.

구성 요소

환경과 에이전트 외에도 강화 학습의 구성 요소에는 정책(policy), 보상(reward), 가치(value), 모델(model)이 있습니다.

보상은 에이전트의 행동에 대해 좋고 나쁨을 평가하는 지표로서 환경으로부터 그 수치를 전달받습니다. 또한 가치라는 개념이 나오게 되는데 보상은 환경으로부터 즉각적으로 받는 단기적인 관점의 수치라면 가치는 장기적인 관점의 수치입니다. 특정 상태의 가치는 그 상태의 시작점에서부터 에이전트가 기대할 수 있는 누적 보상의 합이라고 할 수 있습니다. 다시말해 보상은 주된 것이고 가치는 보상에 대한 예측이기 때문에 부수적이라고 할 수 있습니다. 보상없이 가치가 있을 수 없고 가치를 평가하는 것도 더 많은 보상을 얻기 위해라고 할 수 있습니다. 또한 행동의 선택은 가치를 기준으로 이루어집니다. 장기적으로 최대한 많은 보상을 얻을 수 있기 때문입니다. 즉 강화 학습의 핵심은 가치를 추정(estimate)하는 것이라고 할 수 있습니다.

정책은 특정 상태에서 에이전트가 취해야할 행동을 정의합니다.  강화 학습의 목적은 최적 정책(optimal policy)을 찾는 것입니다. 최적 정책이란 어떤 상태에서 누적 보상의 합이 최대가 되는 행동을 선택하는 정책을 의미합니다. 또한 정책은 확률적(stochastic) 혹은 확정적(deterministic)인 성격을 갖을 수 있습니다.

마지막으로 환경에 대한 모델은 두 가지로 나누어지는데 먼저 모델-프리(model-free)는 모르는 환경에 대해 에이전트가 시행착오를 겪으며 경험을 통해 학습하는 것을 말하며 모델-기반(model-based)는 환경을 알고 계획(planning) 하는 것으로 경험하지 않고 환경이 변화하는 것을 추정하는 것입니다.