벨만 최적 방정식

 

 

• 아 졸려...

 

---

 

 

벨만 최적 방정식 Bellman Optimality Equation

• 벨만 최적 방적식도 앞에서 보았던 벨만 기대 방정식과 비슷하게 0단계와 1,2단계로 나누어져있다
• 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')]$
  • maxa는 모든 가능한 행동 a에 대하여 최댓값을 선택함을 의미하며, E는 기댓값을 의미
• 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')$

Optimal Value란?

• $v_*(s) = \max_{\pi} v_{\pi}(s)$
• $q_*(s, a) = \max_{\pi} q_{\pi}(s, a)$
• $v_*(s)$ : 어떤 MDP가 주어졌을 때, 그 MDP 안에 존재하는 모든 𝜋 들 중 가장 좋은 𝜋∗를 선택하여 계산한 상태 s의 밸류
• 그럼 더 좋은 𝜋(policy)가 무엇일까? 𝜋1과 𝜋2가 주어졌을 때 무엇이 더 좋은지 어떻게 말할 수 있을까?

Policy 의 비교

• 𝜋1 과 𝜋2 가 주어졌을 때 무엇이 더 좋은지 말할 수 있나?
  
  • 말할 수 있는 경우도 있다
  • 말할 수 없는 경우도 있다
• 말할 수 있는 경우는?
  
  • 모든 상태 s에 대해 $𝑣_{𝜋1}(s) ≥ 𝑣_{𝜋2}(s)$ 일때 𝜋1> 𝜋2
  • 이는 Partial Ordering
• Theorem
  
  • 모든 MDP에는 𝜋∗ 가 존재한다
  • 𝜋∗ 는 MDP 안에 존재하는 모든 𝜋 에 대해 𝜋∗ ≥ 𝜋 를 성립
  • 항상 최적의 파이가 존재한다는 것을 이미 학자들이 증명했음

Optimal Policy란?

• Theorem
  
  • 모든 MDP에는 𝜋∗ 가 존재한다
  • 𝜋∗ 는 존재하는 모든 기타 𝜋 에 대해 𝜋∗ ≥ 𝜋
• 정리
  • 최적의 정책: 𝜋
  • 최적의 밸류: $v_{*}(s)=v_{𝜋_{*}}(s)(𝜋_{*}를 따랐을 때의 밸류)$
  • 최적의 액션 밸류: $q_{*}(s,a)=q_{𝜋_{*}}(s,a)(𝜋_{*}를 따랐을 때의 액션 밸류)$

밸만 최적 방정식 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')]$
• 설명
  
  • 벨만 기대 방정식의 0단계와 같은 취지
  • 현재 상태에서의 optimal value는
    • Optimalaction을이용해 한 스텝 진행하고 나서
    • 그 다음 상태의 optimal value를구하면 된다

밸만 최적 방정식 1단계

• 수식 1
  • $v_*(s) = \max_a q_*(s, a)$
• 설명

• $v_*(s) = \max_a q_*(s, a)$
  $= \max(q_*(s, a_1), q_*(s, a_2))$
  $= \max(1, 2) = 2$
• 수식 2
  • $q_*(s, a) = r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_*(s')$
• 설명
  
  • s 에서 a를 선택했을 때의 optimal value는
  • 우선 a를 선택했을 때의 리워드를 받고,
  • 다음에 도달하게 되는 상태들의 optimal value 와 그 상태에 도달할 확률의 곱

밸만 최적 방정식 2단계

• 2단계는 그냥 대입만 하면 끝이다

• 가장 복잡해 보이지만 가장 쉬운 식이다

 

 

 

 

 

 

 

---