[바닥부터 배우는 강화학습] - Chapter 3. 벨만 방정식

대부분의 강화 학습 알고리즘은 밸류를 구하는 것에서 출발합니다. 그리고 밸류를 구하는 데 뼈대가 되는 수식이 바로 벨만 방정식입니다. 벨만 기대 방정식과 벨만 최적 방정식이라는 두 종류의 방정식을 배워봅니다.

---

재귀함수

• 벨만 방정식은 기본적으로 재귀적 관계에 대한 식임
  • 시점 t에서의 밸류와 시점 t+1에서의 밸류 사이의 관계를 다루며, 또한 가치함수와 정책 함수 사이의 관계도 다룸
    
    
• 재귀 함수 : 자기 자신을 호출하는 함수 (ex - 피보나치 수열)
  • 피보나치 수열 일반화
    • $\text{fib}(n) = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right)$
      
      
  • 재귀함수를 이용한 표현
    • $\text{fib}(n) = \text{fib}(n - 1) + \text{fib}(n - 2)$

---

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

• 0단계
  $v_{\pi}(s_t) = \mathbb{E}_{\pi} [r_{t+1} + \gamma v_{\pi}(s_{t+1})]$
  $q_{\pi}(s_t, a_t) = \mathbb{E}_{\pi} [r_{t+1} + \gamma q_{\pi}(s_{t+1}, a_{t+1})]$
  
  
• 1단계
  $v_{\pi}(s) = \sum_{a \in A} \pi(a|s) q_{\pi}(s, a)$
  $q_{\pi}(s, a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s')$
  
  
• 2단계
  $v_{\pi}(s) = \sum_{a \in A} \pi(a|s) \left( r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s') \right)$
  $q_{\pi}(s, a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \sum_{a' \in A} \pi(a'|s') q_{\pi}(s', a')$

---

0단계

$v_{\pi}(s_t) = \mathbb{E}_{\pi} [r_{t+1} + \gamma v_{\pi}(s_{t+1})]$

• 이 식은 현재 상태의 밸류와 다음 상태의 밸류 사이 관계를 나타내고 있음

  • 증명
    $v_{\pi}(s_t) = \mathbb{E}_{\pi} [G_t]$
    $= \mathbb{E}_{\pi} [r{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots]$
    $= \mathbb{E}_{\pi} [r{t+1} + \gamma (r_{t+2} + \gamma r_{t+3} + \cdots)]$
    $= \mathbb{E}_{\pi} [r{t+1} + \gamma G_{t+1}]$
    $= \mathbb{E}_{\pi} [r{t+1} + \gamma v_{\pi}(s_{t+1})]$

  • 현재 상태 $s_t$의 밸류는 리턴의 기댓값임
    • 먼저 리턴이 한 스텝만큼 진행하여 보상을 받고, 그 다음 상태인 $s_{t+1}$부터 미래의 받을 보상을 더해주는 것

---

1단계

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

• 액션 밸류 $q_{\pi}(s, a)$를 이용하여 상태 밸류 $v_{\pi}(s)$를 표현
  
  • 즉, 어떤 상태에서 선택할 수 있는 모든 액션의 밸류를 모두 알고 있다면, 이를 이용해 해당 상태의 밸류를 계산할 수 있음
    • $q_{\pi}(s, a)$에 액션을 선택할 확률을 곱하고, 모두 더해주는 방식임

$q_{\pi}(s, a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s')$

• 상태 밸류 $v_{\pi}(s)$를 이용하여 액션 밸류 $q_{\pi}(s, a)$를 표현
  
  • s에서 a를 실행하는 것의 밸류를 표현하기 위해선 아래 3가지 정보를 모두 알고있어야함
    1. a를 선택하자 마자 얻는 보상의 값
    2. a를 선택했을 경우 다음 상태가 어디가 될지 그 각각에 대한 전이 확률
    3. 각 상태의 밸류 $v(s_1)$ ($t = 1,2,3,…$)

---

2단계

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

• 1단계의 $q_{\pi}$에 대한 식을 $v_{\pi}$에 대한 식에 대입
  

$q_{\pi}(s, a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \sum_{a' \in A} \pi(a'|s') q_{\pi}(s', a')$

• 1단계의 $v_{\pi}$에 대한 식을 $q_{\pi}$에 대한 식에 대입
  

---

0단계 : $v_{\pi}(s_t) = \mathbb{E}_{\pi} [r_{t+1} + \gamma v_{\pi}(s_{t+1})]$

2단계 : $v_{\pi}(s) = \sum_{a \in A} \pi(a|s) \left( r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{\pi}(s') \right)$

• $s_t$를 $s$로, $s_{t+1}$을 $s'$으로 표기법을 통일하고 보면, 0단계와 2단계 모두 $v_\pi(s)$에 대한 식임

• 0단계 : 현재 상태의 밸류와 다음 상태의 밸류를 기댓값 연산자를 통해 연결해 놓은 식
  
  

• 2단계 : 0단계에서 그 기댓값을 계산하기 위한 식

  • 즉, 수식도 결국 현재 상태의 밸류와 다음 상태의 밸류 사이 연결고리를 나타내며, 0단계에 있는 기댓값 연산자를 모든 확률과 밸류의 곱 형태로 풀어서 쓴 형태
    
    
  • 2단계 식을 계산하기 위해서는 다음 2가지를 반드시 알아야함
    • 보상 함수 $r_s^a$ : 각 상태에서 액션을 선택하면 얻는 보상
    • 전이 확률 $p_{ss'}^a$ : 각 상태에서 액션을 선택하면 다음 상태가 어디가 될지에 관한 확률 분포
      
      

• 여기서 $r_s^a$과 $p_{ss'}^a$는 환경의 일부임. 이 2가지에 대한 정보를 알 때 “MDP를 안다” 고 표현

  • $r_s^a$를 안다는 것 : 상태 $s$에서 액션 $a$를 해보기도 전에 얼마의 보상을 받을지 그 기댓값을 안다는 것
  • $p_{ss'}^a$를 안다는 것 : 상태 $s$에서 액션 $a$를 했을 때 어떤 상태에 도달하게 될지 그 확률 분포를 미리 다 알고 있다는 것
    
    

• 실제 세계에는 MDP에 대한 모든 정보를 아는 상황보다 모르는 상황이 더 많음

  • 미리 $r_s^a$를 알지 못하기 때문에 실제로 상태 $s$에서 액션 $a$를 해보는 수밖에 없음
  • 이후, 시행했을 때 받는 보상 등의 경험을 통해 학습하게됨
    
    

• 이렇게 MDP에 대한 정보를 모를 때 학습하는 접근법을 “모델-프리(model-free)” 접근법이라고 함

  • 반대로, $r_s^a$와 $p_{ss'}^a$를 다 안다면 실제로 경험해보지 않고 머릿속에서 시뮬레이션 해보는 것도 가능한데, 이런 종류의 접근법을 “모델 기반(Model-based)” 혹은 “플래닝(planning)” 이라고함

---

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

최적 벨류와 최적 정책

• 벨만 기대 방정식 : $v_{\pi}(s)$와 $q_{\pi}(s, a)$에 대한 수식
  • $v_{\pi}(s)$와 $q_{\pi}(s, a)$는 모두 정책이 $\pi$로 고정되었을 때의 밸류에 관한 함수
    
    
• 벨만 최적 방정식 : $v_{*}(s)$와 $q_{*}(s, a)$에 대한 수식
  • $v_{*}(s)$와 $q_{*}(s, a)$는 최적 밸류(value)에 대한 함수

$v_{*}(s) = \max_{\pi} v_{\pi}(s)$

$q_{*}(s, a) = \max_{\pi} q_{\pi}(s, a)$

• 어떤 MDP가 주어졌을 때 그 MDP 안에 존재하는 모든$\pi$ 들 중에서 가장 좋은 $\pi$를 ($v_{\pi}(s)$의 값을 가장 높게 하는 선택) 하여 계산한 밸류가 곧 최적 밸류 $v_{*}(s)$라는 뜻
  • 실제로 모든 상태에서, 모든 상태에서 최적 밸류를 갖게 하는 정책 $\pi_{*}$가 최소한 1개 이상 존재함
    
    
• 이 정책 $\pi_{*}$를 따르면 모든 상태에 대해 그 어떤 정책보다도 높은 밸류를 얻게 됩니다. 이러한 정책 $\pi_{*}$를 최적 정책(optimal policy) 이라고함
  • 즉, 최적 정책은 모든 정책 $\pi_1, \pi_2, \pi_3, ..., \pi_{\infty}$ 중에 제일 좋은 정책
    
    
    

• 쉬운 버전 설명
  • 다른 정책을 따를 때보다 최적의 정책 $\pi_*$를 따를 때 얻는 보상의 총 합이 가장 크다
    
    
• 어려운 버전 설명
  • “모든 상태 $s$에 대해, $v_{\pi_1}(s) > v_{\pi_2}(s)$ 이면 $\pi_1 > \pi_2$이다.”
    • 만약 존재하는 모든 상태에 대해서$\pi_1$의 밸류가 $\pi_2$의 밸류보다 크다면 $\pi_1$이 더 좋다고 표현 가능함. 즉, 정책 사이의 더 좋다는 기호를 ‘>’를 사용하여 표현하면 $\pi_1 > \pi_2$가 성립하는 것
      
      
  • 부분 순서(partial ordering) : 전체 중에 일부만 대소관계를 비교하여 순서를 정할 수 있다는 뜻
    • 세상에 존재하는 모든 정책들 사이 서열을 매길 수는 없지만, 그중에는 서열을 매길 수 있는 정책들이 부분적으로 존재함
    • 즉, “MDP 내의 모든 $\pi$에 대해 $\pi_*$ > $\pi$ 를 만족하는 $\pi_*$가 반드시 존재한다.”
      
      
      

• 최적의 정책만 정의되고 나면 최적 밸류, 최적의 액션 밸류는 다음과 같은 등식이 성립함.
  • 최적의 정책: $\pi_*$
  • 최적의 밸류: $v_*(s) = v_{\pi_*}(s)$ ($\pi_*$를 따랐을 때의 밸류)
  • 최적의 액션 밸류: $q_*(s, a) = q_{\pi_*}(s, a)$ ($\pi_*$를 따랐을 때의 액션 밸류)

---

벨만 최적 방정식

• 0단계
  $v_{*}(s_t) = \max_{a} \mathbb{E} [r_{t+1} + \gamma v_{*}(s_{t+1})]$
  $q_{*}(s_t, a_t) = \mathbb{E} [r_{t+1} + \gamma \max_{a'} q_{*}(s_{t+1}, a')]$
  
  
• 1단계
  $v_{*}(s) = \max_{a} q_{*}(s, a)$
  $q_{*}(s, a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{*}(s')$
  
  
• 2단계
  $v_{*}(s) = \max_{a} \left[ r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{*}(s') \right]$
  $q_{*}(s, a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \max_{a'} q_{*}(s', a')$

• 벨만 최적 방정식에서는 $\pi$에 의한 확률적 요소가 사라짐. 액션을 선택할 때 확률적으로 선택하는 것이 아니라 최댓값(max) 연산자를 통해 제일 좋은 액션을 선택하기 때문.

---

0단계

$v_{*}(s_t) = \max_{a} \mathbb{E} [r_{t+1} + \gamma v_{*}(s_{t+1})]$

$q_{*}(s_t, a_t) = \mathbb{E} [r_{t+1} + \gamma \max_{a'} q_{*}(s_{t+1}, a')]$

• 상태 $s$에서의 최적 밸류는 일단 한 스텝만큼 진행하여 보상을 받고, 다음 상태인 $s'$의 최적 밸류를 더하는 것으로 벨만 기대 방정식 0단계 수식과 동일하지만, $\mathbb{E}_{\pi}$가 $\mathbb{E}$로 바뀜

  • 벨만 기대 방정식에서는 주어진 $\pi$가 액션을 선택했지만, 벨만 최적 방정식에서는 할 수 있는 모든 액션들 중에 $\mathbb{E}[r + \gamma v_*(s')]$의 값을 가장 크게 하는 액션 $a$를 선택해야 하기 때문에 $\pi$의 역할은 없어져 사라짐
    
    
  • 하지만, 환경에 의한 확률적 요소가 남아있어, 전이 확률에 의해 다양한 $s'$에 도달할 수 있고 그때마다 $r + \gamma v_(s')$의 값이 달라지기 때문에 여전히 기댓값 연산자가 필요함
    
    

• ($q_*(s, a)$에 대한 식은 이후에 Q러닝에 대한 내용을 배울 때 다시 등장)

---

1단계

$v_{*}(s) = \max_{a} q_{*}(s, a)$

• 상태 s의 최적 밸류는 s에서 선택할 수 있는 액션들 중에 밸류가 가장 높은 액션의 밸류와 같다는 뜻
  
  
• 벨만 최적 방정식에서는 100%의 확률로 최적의 밸류를 선택하기 때문에 각 액션을 선택할 확률의 대한 변수가 제거됨

$q_{*}(s, a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{*}(s')$

• 벨만 기대 방정식 1단계 수식과 동일 ($q(s, a), v(s')$이 $q_{*}(s, a), v_{*}(s')$로 변경)

---

2단계

$v_{*}(s) = \max_{a} \left[ r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{*}(s') \right]$

• $v_{*}(s)$의 식에 $q_{*}(s, a)$의 식 대입
  
  • 현재 상태의 최적 밸류와 다음 상태의 최적 밸류 사이 관계 식을 얻음. 이를 통해 MDP를 알때 최적 밸류를 구할 수 있음

$q_{*}(s, a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a \max_{a'} q_{*}(s', a')$

• $q_{*}(s, a)$의 식에 $v_{*}(s)$의 식 대입
  

---

정리

• 벨만 기대 방정식 : 무언가 정책 $\pi$가 주어져 있고, 룰을 평가하고 싶을 때
  
  
• 벨만 최적 방정식 : 최적의 밸류를 찾는 일을 할 때