벨만 방정식(Bellman Equation)이란?

벨만 방정식은 현재 상태의 가치(Value)와 다음 상태의 가치 사이의 관계를 나타내는 재귀식이다.

이는 현재 상태의 가치는 당장 얻는 보상과 다음 상태 가치의 합이라는 것을 수학적으로 증명한 식이다. 리처드 벨만(Richard Bellman)에 의해 정립되었으며, 복잡한 미래를 한 단계의 재귀적인 관계로 압축한 것이 핵심이다.

 

강화학습의 핵심인 반환값(Return, $G_t$)의 정의를 시간 단계별로 분해하여 얻을 수 있다.

 

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

$G_t = R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \dots) = R_{t+1} + \gamma G_{t+1}$

 

에이전트가 시간 $t$ 이후로 받을 모든 보상의 합이다. 미래의 보상일수록 불확실성을 고려하여 할인율($\gamma$)을 곱한다. 이 재귀적 성질을 기댓값($\mathbb{E}$) 기호 내에 적용한 것이 벨만 방정식이다.

 

식을 해석해 보자면, 해당 $R_{t+1}$표기는 시간 $t$에 한 행동($A_t$)의 결과로, 시간 $t+1$에 수령한 보상이라는 의미이다. 초기의 시간 상태와 행동에서는 보상을 받아낼 수 없으니, 첫 번째 행동을 한 결과가 나타나는 시점이 $t=1$이기에 수식에서 $t+1$으로 나타내 주는 것이다.

 

이전 내용을 다시 상기시켜 보자.

상태 가치 함수 (State-value Function)는 어떤 상태 $s$에 있는 것이 평균적으로 얼마나 좋은지를 나타낸다.

 

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

 

행동 가치 함수 (Action-value Function, Q-function)는 어떤 상태 $s$에서 특정 행동 $a$를 하는 것이 얼마나 좋은지를 나타낸다.

 

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

 

$V^\pi$와 $Q^\pi$의 상호 관계 (The Relationship)를 살펴보면, 이 두 함수는 서로를 통해 정의될 수 있으며, 이 관계가 벨만 방정식 유도의 핵심이 된다.

 

$Q$를 이용한 $V$의 정의를 알아보자. 특정 상태 $s$에서의 가치는, 그 상태에서 선택할 수 있는 모든 행동들의 가치($Q$)를 정책($\pi$)에 따라 평균 낸 값이다. 

 

$V^\pi(s) = \sum_{a \in \mathcal{A}} \pi(a|s) Q^\pi(s, a)$

 

내가 지금 이 상태($s$)에서 어떤 행동을 할 확률($\pi$)과 그 행동을 했을 때 얻을 가치($Q$)를 곱하여 모두 더한다. 상태 가치 $V$는 에이전트가 아직 행동을 하기 전에 내가 서 있는 자리를 평가하는 것이다. 따라서 $V$는 내가 앞으로 할 행동들이 각각 얼마나 가치 있는지($Q$)를 나의 정책($\pi$)의 영향을 받아 내놓은 총합이다.

 

$V$를 이용한 $Q$의 정의를 알아보자. 특정 행동 $a$을 실행했을 때의 가치는 그 행동 직후에 받는 보상과, 그 행동으로 인해 도착하게 될 다음 상태의 가치($V$)의 합에 대한 기댓값으로 정의된다.

 

$ Q^\pi(s, a) = \sum_{s', r} p(s', r | s, a) \left[ r + \gamma V^\pi(s') \right]$

 

행동 $a$를 했을 때 벌어질 수 있는 모든 시나리오($s', r ㅡ 환경이 우리를 어디로 보낼지, 얼마를 줄지에 대한 확률적인 상황$)에 대하여, 그 일이 벌어질 확률($p$)과 그때 얻는 실제 보상($r$) 및 미래 가치($V$)를 곱하여 합산하는 것이다.

 

행동 가치 $Q$는 행동을 이미 저지른 후의 가치를 평가하는 것이다. 내가 어느 행동($a$)을 했다면, 그다음의 운명은 환경의 전이 확률($p$)에 맡겨진다. 환경이 나를 좋은 상태($s'$)로 보낼 확률이 높을수록, 그 행동의 가치($Q$)는 올라간다.

 

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

해당 기대 방정식은 현재의 가치와 다음 스텝($t+1$)의 가치 사이의 관계를 나타내는 식이다. 이는 벨만 기대 방정식은 기대값(expectation) 연산자를 통해, 현재 상태의 가치함수 $V^\pi(s)$를 즉각적 보상과 다음 상태의 가치함수의 기댓값으로 재귀적으로 분해하는 식이다. 이 단계에서 확률론적 원리를 분석하여 나타낸다.

 

전체 기댓값의 법칙 (Law of Total Expectation)에 대해 먼저 알아보자

수학적인 정의로는 아래와 같다.

 

$\mathbb{E}[X] = \mathbb{E}[\mathbb{E}[X|Y]]$,

$\mathbb{E}[X|Z] = \mathbb{E}[\mathbb{E}[X|Y,Z]|Z]$ (Z는 배경정보, 조건)

 

이 법칙의 직관적인 의미는 "전체 평균을 구하고 싶다면, 먼저 부분 그룹별($Y$)로 평균을 낸 뒤($\mathbb{E}[X|Y]$), 그 부분 그룹들의 평균값들에 대한 전체 평균을 내도 같다"는 것

 

예시를 들어서 설명해 보자

어느 고등학교의 전교 수학 평균($\mathbb{E}[X]$)을 구하고 싶다고 가정해 보자.

1. 방법 A (직접 계산): 모든 학생의 점수를 다 더해서 전체 학생 수로 나눔. ($\mathbb{E}[X]$)
2. 방법 B (전체 기댓값의 법칙): * 먼저 각 반별로 평균을 냄, [1반 평균, 2반 평균, ...] $\rightarrow$ 이것이 $\mathbb{E}[X|Y]$ (반 $Y$라는 조건이 주어졌을 때의 평균)이다.
   • 이제 이 반별 평균값들의 평균을 다시 낸다. $\rightarrow$ 이것이 $\mathbb{E}[\mathbb{E}[X|Y]]$ 이다.

결과적으로 방법 A와 방법 B의 값은 항상 같다는 것을 주목하자. 즉, "전체 평균을 구하려면, 그룹별로 먼저 평균을 낸 뒤 그 평균들을 다시 평균 내도 된다"는 법칙인 것이다.

 

아래는 상태 가치 함수 $V^\pi$에 대한 기대 방정식이다.

 

$ \begin{aligned} V^\pi(s) & := \mathbb{E}_\pi [G_t | S_t = s] \\ & = \mathbb{E}_\pi [R_{t+1} + \gamma G_{t+1} | S_t = s] & \dots \text{(1)} \\ & = \mathbb{E}_\pi [R_{t+1} + \gamma \mathbb{E}_\pi [G_{t+1} | S_{t+1}, S_t = s] | S_t = s] & \dots \text{(2)} \\ & = \mathbb{E}_\pi [R_{t+1} + \gamma \mathbb{E}_\pi [G_{t+1} | S_{t+1}] | S_t = s] & \dots \text{(3)} \\ & = \mathbb{E}_\pi [R_{t+1} + \gamma V^\pi(S_{t+1}) | S_t = s] & \dots \text{(4)} \end{aligned}$

 

• (1) 재귀적 분해: $G_t$를 즉각 보상 $R_{t+1}$과 미래 리턴 $\gamma G_{t+1}$로 나눈다.
• (2) 전체 기댓값의 법칙 (Tower Property): $\mathbb{E}[X|Z] = \mathbb{E}[\mathbb{E}[X|Y,Z]|Z]$ 성질을 이용한다. 여기서 $X=G_{t+1}$, $Y=S_{t+1}$, $Z=S_t$이다. 미래 리턴의 평균을 구하기 위해 다음 상태($S_{t+1}$)라는 중간 조건을 먼저 고려한다.
• (3) 마르코프 성질 (Markov Property): 해당 마르코프 성질의 표현은 이전글에서 봤다시피 아래와 같았다.
  
                                  $E_{\pi}[G_{t+1} | S_{t+1}, S_t = s] = E_{\pi}[G_{t+1} | S_{t+1}]$
  
    현재 상태 $S_{t+1}$이 주어지면, 그 이전 상태인 $S_t$는 미래의 리턴 $G_{t+1}$에 추가 정보를 주지 않으므로 조건에서 제거된다. 즉, 현재 상태 $S_{t+1}$​만 알면, 과거의 모든 이력  $(S_t, S_{t-1}, \dots)$과 무관하게 미래의 리턴 $G_{t+1}$​ 전체를 예측할 수 있다는 것이다.
• (4) 가치 함수의 정의 대입: $\mathbb{E}_\pi [G_{t+1} | S_{t+1}]$은 정의에 의해 다음 상태의 가치 $V^\pi(S_{t+1})$이 된다.

최종 형태는 아래와 같다.

 

$ \begin{aligned} V^\pi(s) & = \mathbb{E}_\pi [R_{t+1} + \gamma V^\pi(S_{t+1}) | S_t = s] \\ & = \sum_{a \in \mathcal{A}} \pi(a|s) \sum_{s', r} p(s', r | s, a) \left[ r + \gamma V^\pi(s') \right] \end{aligned}$

 

아래는 $Q^\pi$에 대한 기대 방정식이다.

 

$ \begin{aligned} Q^\pi(s, a) & := \mathbb{E}_\pi [G_t | S_t = s, A_t = a] \\ & = \mathbb{E}_\pi [R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a] & \dots \text{(1)} \\ & = \mathbb{E}_\pi [R_{t+1} + \gamma \mathbb{E}_\pi [G_{t+1} | S_{t+1}, A_{t+1}, S_t = s, A_t = a] | S_t = s, A_t = a] & \dots \text{(2)} \\ & = \mathbb{E}_\pi [R_{t+1} + \gamma \mathbb{E}_\pi [G_{t+1} | S_{t+1}, A_{t+1}] | S_t = s, A_t = a] & \dots \text{(3)} \\ & = \mathbb{E}_\pi [R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) | S_t = s, A_t = a] & \dots \text{(4)} \end{aligned} $

 

여기서 유도 단계는 상태 가치 함수와 비슷하다.

최종 형태는 아래와 같다.

 

$\begin{aligned} Q^\pi(s, a) & = \mathbb{E}_\pi [R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) | S_t = s, A_t = a] \\ & = \sum_{s', r} p(s', r | s, a) \left[ r + \gamma \sum_{a' \in \mathcal{A}} \pi(a'|s') Q^\pi(s', a') \right] \end{aligned}$

 

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

에이전트가 최적 정책(Optimal Policy, $\pi^*$)을 따를 때인, 가중 평균($\sum \pi$) 대신 최댓값($\max$)을 선택했을 상황을 다룬다. 

 

최적 정책 하에서의 관계

 

$V^*(s) = \max_a Q^*(s, a)$

 

최적 상태 가치 함수 ($V^*$)

 

$V^*(s) = \max_a \sum_{s', r} p(s', r | s, a) \left[ r + \gamma V^*(s') \right]$

 

최적 행동 가치 함수 ($Q^*$)

 

$Q^*(s, a) = \sum_{s', r} p(s', r | s, a) \left[ r + \gamma \max_{a'} Q^*(s', a') \right]$