[RL] 2. Bellman equation

환경(상태 전이, 보상)와 에이전트 정책이 결정적이라면, 수익 공식인 $G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots$로 상태 가치 함수를 쉽게 구할 수 있다.

하지만 결정적이지 않다면, 위 방식으로 구할 수 없다.

 

벨만 방정식은 환경 및 에이전트 정책이 확률적일 때 상태 가치 함수를 구하는데 사용되는 유용한 식이다.

벨만 방정식 유도

$$\begin{matrix}G_t &=& R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots \\ &=& R_t + \gamma (R_{t+1} + \gamma R_{t+2} + \cdots) \\ &=& G_t = R_t + \gamma G_{t+1} \end{matrix}$$

 

$$\begin{matrix} v_\pi(s) &=& \mathbb E_\pi [G_t|S_t=s] \\ &=& \mathbb E_\pi [R_t + \gamma G_{t+1}|S_t=s] \\ &=& \mathbb E_\pi [R_t|S_t=s] + \gamma \mathbb E_\pi [G_{t+1}|S_t=s] \end{matrix}$$

 

$$\mathbb E_\pi[R_t|S_t=s] = \sum_{a} \pi(a|s)R_s^a$$

 

$$\begin{matrix} \mathbb E_\pi[G_{t+1}|S_t=s] &=& \sum_{a} \pi(a|s) \sum_{s^\prime} P_{ss^\prime}^a \mathbb E_\pi[G_{t+1}|S_{t+1}=s^\prime] \\ &=& \sum_{a} \pi(a|s) \sum_{s^\prime}P_{ss^\prime}^av_\pi(s^\prime) \end{matrix}$$

 

$$\begin{matrix} v_\pi(s) &=& \mathbb E_\pi [R_t|S_t=s] + \gamma \mathbb E_\pi [G_{t+1}|S_t=s] \\ &=& \sum_{a} \pi(a|s)R_s^a +  \gamma \sum_{a} \pi(a|s) \sum_{s^\prime}P_{ss^\prime}^av_\pi(s^\prime) \\ &=& \sum_{a} \pi(a|s)\left(R_{s}^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_\pi(s^\prime)\right) \end{matrix}$$

 

$v_\pi(s) = \sum_{a} \pi(a|s)\left(R_{s}^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_\pi(s^\prime)\right)$이 바로 벨만 방정식이다.

벨만 방정식 의의

벨만 방정식은 "현재 상태 $s$의 상태 가치 함수와 다음 상태 $s^\prime$의 상태 가치 함수의 관계"를 나타내는 식이다.

그렇기 때문에, 벨만 방정식을 이용해 상태 가치 함수를 연립 방정식으로 구할 수 있다.

이는 이전 방식(=수익 공식)의 두 가지 한계점을 해결했다.

1. 유한한 연립 방정식으로 수익 수식의 무한 굴레를 벗어났다.

2. 환경 및 에이전트 정책이 확률적이어도 구할 수 있다.

행동 가치 함수(action-value function, Q function)

행동 가치 함수는 상태 가치 함수에 행동 조건을 추가한 함수다.

다시 말해, 행동 가치 함수인 $q_\pi(s,a)$는 상태 $S_t$와 행동 $A_t$가 각각 $s$, $a$고 에이전트 정책이 $\pi$일 때, 에이전트가 얻을 기대 수익을 의미한다.

이를 수식으로 표현하면 다음과 같다.

$$q_\pi(s,a) = \mathbb E[G_t|S_t=s, A_t=a]$$

 

여기서, $q_\pi(s, a)$의 $a$는 정책 $\pi$와 무관하다는 점을 주의해야 한다. 즉, $A_{t+1}$부터 정책 $\pi$에 따른다.

이 점이 바로 상태 가치 함수와 행동 가치 함수의 유일한 차이점이다.

상태 가치 함수와 행동 가치 함수의 관계를 수식으로 표현하면 다음과 같다.

$$v_\pi(s) = \sum_a \pi(a|s)q_\pi(s,a)$$

 

추가로, 최적 정책의 행동 가치 함수를 최적 상태 가치 함수(optimal action-value function) 이라 하고, $q_*(s, a)$로 표기한다.

행동 가치 함수의 벨만 방정식 유도

$$\begin{matrix} q_\pi(s,a) &=& \mathbb E_\pi [G_t|S_t=s, A_t=a] \\ &=& \mathbb E_\pi [R_t + \gamma G_{t+1}|S_t=s, A_t=a] \\ &=& \mathbb E_\pi [R_t|S_t=s, A_t=a] + \gamma \mathbb E_\pi [G_{t+1}|S_t=s, A_t=a]\end{matrix}$$

 

$$\mathbb E_\pi [R_t|S_t=s, A_t=a] = R_s^a$$

 

$$\begin{matrix} \mathbb E_\pi [G_{t+1}|S_t=s, A_t=a] &=& \sum_{s^\prime} P_{ss^\prime}^a \mathbb E_\pi[G_{t+1}|S_{t+1}=s^\prime] \\ &=& \sum_{s^\prime} P_{ss^\prime}^a v_\pi(s^\prime) \\ &=& \sum_{s^\prime} P_{ss^\prime}^a \sum_{a^\prime} \pi(a^\prime|s^\prime) q_\pi(s^\prime, a^\prime) \end{matrix}$$

 

$$\begin{matrix} q_\pi(s,a) &=& \mathbb E_\pi [R_t|S_t=s, A_t=a] + \gamma \mathbb E_\pi [G_{t+1}|S_t=s, A_t=a] \\  &=& R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a \sum_{a^\prime} \pi(a^\prime|s^\prime) q_\pi(s^\prime, a^\prime) \end{matrix}$$

 

$q_\pi(s, a)=R_s^a + \sum_{s^\prime} P_{ss^\prime}^a \sum_{a^\prime} \pi(a^\prime|s^\prime) q_\pi(s^\prime, a^\prime)$가 행동 가치 함수의 벨만 방정식이다.

최적 벨만 방정식

벨만 방정식은 어떤 정책 $\pi$에 대해 성립하는 방정식이다.

이번에는 최적 정책 $\pi_*$에 대해서만 성립하는 벨만 최적 방정식(bellman optimality equation)에 대해 살펴보자.

상태 가치 함수의 최적 벨만 방정식

벨만 방정식에 최적 상태 가치 함수를 대입하면 다음과 같이 표현할 수 있다.

$$v_*(s) = \sum_{a} \pi_*(a|s)\left(R_{s}^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_*(s^\prime)\right)$$

 

여기서 최적 정책 $\pi_*$는 $R_{s}^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_*(s^\prime)$이 가장 큰 행동을 선택한다. 다시 말해, 값이 가장 큰 행동을 100% 확률로 선택한다.

왜냐하면, 최적 정책은 모든 상태에서 상태 가치 함수가 최대인 정책이기 때문이다.

이를 반영하면 수식은 다음과 같이 바뀐다.

$$v_*(s) = \underset{a}{\max} \left(R_{s}^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_*(s^\prime)\right)$$

행동 가치 함수의 최적 벨만 방정식

벨만 방정식에 최적 행동 가치 함수를 대입하면 다음과 같이 표현할 수 있다.

$$q_*(s, a) = R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a \sum_{a^\prime} \pi_*(a^\prime|s^\prime) q_*(s^\prime, a^\prime)$$

 

여기서 최적 정책 $\pi_*$는 $q_*(s^\prime, a^\prime)$이 가장 큰 행동을 선택한다. 다시 말해, 값이 가장 큰 행동을 100% 확률로 선택한다.

$q_*(s^\prime, a^\prime)$이 가장 큰 행동을 선택하면 $v_*(s^\prime)$이 가장 커지기 때문이다. ($v_\pi(s^\prime) = \sum_a^\prime \pi(a^\prime|s^\prime)q_\pi(s^\prime,a^\prime)$)

이를 반영하면 수식은 다음과 같이 바뀐다.

$$q_*(s, a) = R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a \underset{a^\prime}{\max} q_*(s^\prime, a^\prime)$$

 

최적 정책을 최적 행동 가치 함수로 표현하면 다음과 같다.

$$\mu_*(s) = \underset{a}{\text{argmax}} q_*(s, a)$$

최적 벨만 방정식 의의

최적 벨만 방정식은 "현재 상태 $s$의 최적 상태 가치 함수와 다음 상태 $s^\prime$의 최적 상태 가치 함수의 관계"를 나타내는 식이다.

그렇기 때문에, 최적 벨만 방정식을 이용해 최적 상태 가치 함수 $v_*(s)$를 연립 방정식으로 구할 수 있다.

 

그리고, 다음과 같이 최적 상태 가치 함수로 최적 행동 가치 함수를 구할 수 있다.

$$\begin{matrix} q_\pi(s,a) &=& R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a \sum_{a^\prime} \pi(a^\prime|s^\prime) q_\pi(s^\prime, a^\prime) \\ &=& R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_\pi(s^\prime) \end{matrix}$$

$$\text{so, }q_*(s,a) = R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_*(s^\prime)$$

그럼, 다음과 같이 최적 상태 가치 함수로 최적 정책을 바로 구할 수 있다.

$$\begin{matrix} \mu_*(s) &=& \underset{a}{\text{argmax }} q_*(s, a) \\ &=& \underset{a}{\text{argmax }}R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_*(s^\prime) \end{matrix}$$

즉, 모든 정책을 찾을 필요가 없어졌다.

정리

1. 모든 정책을 찾아 수익 수식 $G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots$으로 각 정책의 상태 가치 함수를 구하고, 이를 비교해 최적 정책을 찾는다.

 

2. 모든 정책을 찾은 후, 벨만 방정식$v_\pi(s) = \sum_{a} \pi(a|s)\left(R_{s}^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_\pi(s^\prime)\right)$을 사용해 각 정책의 상태 가치 함수를 연립 방정식으로 구하고, 이를 비교해 최적 정책을 찾는다.

이전 방식(=수익 수식)에서 두 가지 부분을 개선했다.

1. 유한한 연립 방정식으로 수익 수식의 무한 굴레를 벗어났다.

2. 환경 및 에이전트 정책이 확률적이어도 구할 수 있다.

 

3. 최적 벨만 방정식 $v_*(s) = \underset{a}{\max} \left(R_{s}^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_*(s^\prime)\right)$을 사용해 최적 상태 가치 함수를 연립 방정식으로 구하고, $\mu_*(s) = \underset{a}{\text{argmax }}R_s^a + \gamma \sum_{s^\prime} P_{ss^\prime}^a v_*(s^\prime)$으로 최적 정책을 찾는다.

벨만 방정식과 다르게 모든 정책을 찾는 수고를 들일 필요가 없어졌다.