[RL] 벨만 방정식 (with MDP)

이 포스팅은 학교수업과 노승은 저자의 "바닥부터 배우는 강화 학습"을 바탕으로 정리했다.

 

학교 수업또한 저자 책을 바탕으로 수업을 받기 때문에 강의자료(요약에 가까운)와 책을 보며 정리했다.

---

개념

벨만 방정식은 MDP를 수식적으로 쉽게 이해하기 위해 접근한 방정식이다.

 

또한 밸류를 구할 때 벨만 방정식을 사용해야 한다.

 

분류는 벨만 기대 방정식, 벨만 최적 방정식 두 가지로 나뉜다.

 

벨만 기대 방정식

책에서는 벨만 방정식을 단계별로 설명했다.

 

0단계

$v_π(S_t) = E_π[G_t|S_t]$

$=E_π[R_{t+1} + γR_{t+2} + γ^2R_{t+3} + ···|S_t]$

$= E_π[R_{t+1} + γ(R_{t+2} + γR_{t+3} + ···)|S_t]$

$= E_π[R_{t+1} + γ(G_{t+1})|S_t]$

$= E_π[R_{t+1} + γv_π(S_{t+1})|S_t]$

 

치환과정에서 E는 선형성에 의해 생략되었다.

 

$ v_π(S_t) = E_π[R_{t+1} + γv_π(S_{t+1})|S_t]$

 

이 식을 다르게도 표현할 수 있다.

 

$v(s) = R_s + γ \sum_{s'∈S}^{} P_{ss'}v(S')$

 

기대값은 확률변수의 평균적인 값으로, 

 

여러 가능한 결과들 각각의 값에 그 결과가 일어날 확률을 곱한 후 그 값들을 모두 합한 것이다.

 

이 경우, 가능한 모든 다음 상태 $s'$에 대하여,

 

각 상태로 전이할 확률 $P_{ss′}$ 과 그 상태의 가치 $v(S′)$의 곱을 모두 더함으로써 기대 리턴을 계산한다.

 

이 식을 또 다시 행렬로 표현할 수 있다.

 

$v = R + γPv$

$v = (I - γP)^{-1} R$

 

$\begin{bmatrix}
v(1) \\
\vdots \\
v(n) \\
\end{bmatrix} = \begin{bmatrix}
R_1 \\
\vdots \\
R_n \\
\end{bmatrix} + γ\begin{bmatrix}
P_{11} & \cdots & P_{1n} \\
\vdots &  &  \\
P_{n1} & \cdots & P_{nn} \\
\end{bmatrix} \begin{bmatrix}
v(1) \\
\vdots \\
v(n) \\
\end{bmatrix} $

 

이 식을 통해 행렬 방정식을 반복적으로 계산하여, 모든 상태에 대한 최적의 가치 함수를 근사할 수 있다.

 

이 과정에서, 각 반복에서의 가치 함수 추정치는 점차적으로 실제 최적 가치 함수에 수렴하게 된다.

 

1단계

가치 v

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$v_π(s) = \sum_{a∈A}π(a|s)q_π(s,a)$

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$π(a|s)$ : s에서 a를 실행할 확률

$q_π(s,a)$ : s에서 a를 실행하는 것에 대한 밸류

 

한 state에서의 예시를 들어보자.

$π(a_1|s)$ = 60%,정책$π$에서 $a_1$을 했을 때 $q_π(s,a_1) = 1$

$π(a_2|s)$ = 40%, 정책$π$에서 $a_2$을 했을 때 $q_π(s,a_2) = 2$

 

따라서 $v_π$는 공식에 의해

$v_π = π(a_1|s)*q_π(s,a_1) + π(a_2|s)*q_π(s,a_2)$

$ = 0.6*1 + 0.4*2 = 1.4$

 

액션에 대한 가치 q

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$q_π(s,a) = r^a_s + γ\sum{s'∈S}{}P^a_{ss'}v_π(s')$

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$P^a_{ss'}$ : s에서 a를 실행하면 s'에 도착할 확률

 

한 state에서의 예시를 들어보자.

 

$a_1$에서 $s_1$으로 갈 확률 : 70%, 그것에 대한 가치 $v_π=1.5$

$a_1$에서 $s_2$으로 갈 확률 : 30%, 그것에 대한 가치 $v_π=-1$

$a_1$에 대한 보상 r : 0.5

 

따라서 $q_π$ 공식에 의해

 

$q_π(s,a_1) = r^a_s + P^{a_1}_{ss_1} * v_π(s_1) + P^{a_1}_{ss_2} * v_π(s_2)$

$= 0.5 + 0.7 * 1.5 + 0.3 * (-1) = 1.25$

 

2단계

2단계는 1단계에서 구한 것을  v에 대한 것과 q에 대한 것을 서로 각자 대입해주는 것이다.

 

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$v_π(s) = \sum_{a∈A}π(a|s)q_π(s,a)$

$v_π(s) = \sum_{a∈A}π(a|s) ( r^a_s + γ\sum{s'∈S}{}P^a_{ss'}v_π(s') )$

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$q_π(s,a) = r^a_s + γ\sum{s'∈S}{}P^a_{ss'}v_π(s')$

$q_π(s,a) = r^a_s + γ\sum{s'∈S}{}P^a_{ss'} ( \sum_{a∈A}π(a|s)q_π(s,a) )$

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

 

이 벨만 기대 방정식을 구할 때는 반드시 보상함수 $r^a_s$와 $P^a_{ss'}$을 알아야한다.

 

실제로 MDP를 모를 때와 알떄의 학습으로 나뉜다.

 

그리고 이건 벨만 "기대" 방정식이고 아직 벨만 "최적" 방정식이 남았다....

 

 

벨만 최적 방정식

벨만 최적 방정식은 액선을 선택할 때 확률적이 아닌 무조건 최댓값을 고르는 것이다.

 

0단계

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$v^*(s) = max_π E[r + γv^*(s')| S_t =s]$

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$q^*(s,a) = E[r + γmax_a' q^*(s',a') | S_t = s, A_t = a]$

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

우선 위의 식처럼 최댓값을 나타내 주는 식을 정해준다.

 

액션은 확률을 따르지 않고 $E[r + γv^*(s')]$을 최대로 하는 액션을 선택한다.

 

환경에 의한 전이 확률 $P^a_{ss'}$에 의해 다양한 s'에 도달할 수 있기 때문에 기댓값 연산자가 필요하다.

 

1단계

$v^*(s) = max_a q^*(s,a)$

액션의 가치인 q가 높은 것을 잡는다.

 

$q^*(s,a) = r^a_s + γ\sum_{s'∈S}P^a_{ss'}v^*(s')$

 

2단계

1단계에서 구한 식을 기대방정식 구할 때 처럼 그대로 대입해준다.

 

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$v^*(s) = max_a q^*(s,a)$

$v^*(s) = max_a ( r^a_s + γ\sum_{s'∈S}P^a_{ss'}v^*(s') )$

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

$q^*(s,a) = r^a_s + γ\sum_{s'∈S}P^a_{ss'}v^*(s')$

$q^*(s,a) = r^a_s + γ\sum_{s'∈S}P^a_{ss'} max_a q^*(s,a) $

--- --- --- --- --- --- --- --- --- --- --- --- --- --- ---