1. 벨만 기대 방정식
시점 t에서의 밸류와 시점 t+1에서의 밸류 사이의 관계를 다루고 있으며 또 가치 함수와 정책 함수 사이의 관계도 다룸. 무언가 정책이 주어지고, 그 정책을 평가하고 싶을 때 이용.
0단계
$v_\pi(s_t) = E_\pi[r_{t+1} + \gamma v_\pi(s_{t+1})]$
$q_\pi(s_t,a_t) = E_{\pi}[r_{t+1} + \gamma q_\pi(s_{t+1},a_{t+1})]$
- 현재 상태의 밸류와 다음 상태의 밸류 사이의 관계를 나타냄
- 모델-프리: MDP에 대한 정보를 모를때 사용, 실제로 상태s에서 액션a를 해서 학습하는 접근법(0단계 식)
1단계
$v_\pi(s) = \sum\limits_{a\in A} \pi(a|s) q_\pi(s,a) \quad$ 정책이 고정되고 상태 s의 밸류를 계산
$q_\pi(s,a) = r^a_s + \gamma \sum\limits_{s’\in S} P^a_{ss’}v_\pi(s’) \quad$ 액션의 밸류를 평가
2단계
$v_\pi(s) = \sum\limits_{a\in A} \pi(a|s) \left( r_s^a + \gamma \sum\limits_{s’ \in S} P_{SS’}^a v_\pi(s’) \right)$
$q_\pi(s,a) = r^a_s + \gamma \sum\limits_{s’\in S} P^a_{ss’} \sum\limits_{a’\in A} \pi(a’|s’)q_\pi(s’,a’)$
- MDP를 알 때 이용
- 모델 기반 플래닝: 보상함수와 전이 확률을 다 안다면 실제로 경험해보지 않고 시뮬레이션하는 접근법(2단계 식)
2. 벨만 최적 방정식
$\pi$에 의한 확률적 요소가 사라짐. 액션을 선택할 때 확률적으로 선택하는 것이 아니라 최대값 연산자를 통해 제일 좋은 액션을 선택
- 부분 순서(partial ordering): 전체 중에 일부만 대소관계를 비교하여 순서를 정할수 있다.
MDP내의 모든 $\pi$에 대해 $\pi_* > \pi$를 만족하는 $\pi_* $가 반드시 존재.
상태별로 가장 높은 밸류를 주는 정책이 모두 다르다면 각 상태별로 새로운 $\pi_*$를 따르면 된다.
0단계
$v_* (s) = \max_a \mathbb{E}[r+\gamma v_* (s’)|s_t=s, a_t=a]$
$q_* (s,a) = \mathbb{E}[r+\gamma \max_a q_* (s’,a’)|s_t=s, a_t=a]$
- 상태s에서 최적 밸류는 일단 한 스텝만큼 진행하여 보상을 받고, 다음 상태인 $s’$의 최적 밸류를 더해줘도 똑같다.
1단계
$v_* (s) = \max_a q_* (s,a)$
- 상태 s의 최적밸류는 s에서 선택할 수 있는 액션들중에 밸류가 가장 높은 액션(100%)의 밸류와 같다.
$q_* (s,a) = r^a_s + \gamma \sum\limits_{s’\in S} P^a_{ss’}v_* (s’)$ $\quad \pi$ 대신 $\pi_* $를 따름
2단계
$v_* (s) = \max_a \left [ r^a_s + \gamma \sum\limits_{s’\in S} P^a_{ss’}v_* (s’) \right]$
현재 상태의 최적 밸류와 다음 상태의 최적 밸류 사이의 관계 식.
따라서 MDP를 알 때 최적 밸류를 구할 수 있음.
$q_* (s,a) = r^a_s + \gamma \sum\limits_{s’\in S} P^a_{ss’} \max_{a’} q_* (s’,a’)$
-->
Comments