본문 바로가기
AI 딥러닝/강화학습

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

by 세인트 워터멜론 2021. 4. 28.

벨만의 최적성 원리(Bellman’s principle of optimality)는 일견 자명해 보이는 사실에 바탕을 두고 있다.

 

 

만약 상태변수와 그 상태변수에서 내린 어떤 결정들의 시퀀스가 최적(optimal)이라면, 맨 첫 번째 상태변수와 결정을 해당 시퀀스에서 제거해도, 나머지 시퀀스는 여전히 최적 시퀀스라는 것이다. 물론 나머지 시퀀스는 두 번째 상태변수와 결정을 초기 조건으로 하는 시퀀스가 된다. 좀 더 구체적으로 설명해 본다. 다음과 같은 그림에서 최적 경로가 경로 a-b-d 라고 하자.

 

 

노드 a에서 처음 내린 결정(decision)으로 경로 a-b가 선택됐고 그 때의 비용은 \(J_{ab}\)라고 하고, 그 다음 결정으로 경로 b-d가 선택됐고 그 때의 비용이 \(J_{bd}\)라고 하자. 그리고 경로 a-d의 최소 비용이 \(J_{ad}^\star=J_{ab}+J_{bd}\)라고 하자. 그러면 다음과 같은 주장이 가능하다.

만약 경로 a-b-d가 경로 a-d의 최적 경로(optimal path)라고 하면, 경로 b-d는 노드 b부터 d까지의 최적 경로이다. 증명은 다음과 같이 할 수 있다.

우선 노드 b부터 d까지의 최적 경로를 b-c-d라고 가정하자. 그러면 비용은 \(J_{bcd} \lt J_{bd}\)가 되어서 \(J_{ab}+J_{bcd} \lt J_{ab}+J_{bd}=J_{ad}^\star\)가 된다. 이것은 \(J_{ad}^\star\)가 최적이라는 가정에 위배되므로, 경로 b-c-d는 노드 b부터 d까지의 최적 경로가 아니다. 이와 같은 주장을 정리한 것을 벨만(R. E. Bellman)의 최적성 원리라고 한다.

"최적 정책(optimal policy)은 이전의 결정(decision)과 관계없이 그 이후의 결정은 이전 결정으로 초래된 상태에 대해서 최적 정책(optimal policy)이어야 한다."

벨만의 최적성 원리를 이용한 최적화 방법을 다이나믹 프로그래밍(dynamic programming)이라고 한다. 벨만의 최적성 원리는 최종 상태에서 초기 상태로 거슬러 올라가며 최적 정책을 결정해야 한다는 것을 의미한다.

모든 정책 중에서, 상태가치 값을 최대로 만드는 정책을 적용했을 때의 상태가치 함수와 행동가치 함수를 각각 최적 상태가치 함수(optimal state-value function)와 최적 행동가치 함수(optimal action-value function)라고 한다. 그리고 그 정책을 최적 정책(optimal policy)이라고 한다.

 

\[ \begin{align} & V^\star = \max_\pi⁡ V^\pi (\mathbf{x}_t) \\ \\ & Q^\star = \max_\pi ⁡Q^\pi (\mathbf{x}_t, \mathbf{u}_t) \end{align} \]

 

상태가치 함수는 다음과 같이 행동가치 함수를 행동에 관해 평균값을 취한 것이었다.

 

\[ V^\pi (\mathbf{x}_t )= \int_{\mathbf{u}_t} Q^\pi (\mathbf{x}_t, \mathbf{u}_t ) \pi (\mathbf{u}_t | \mathbf{x}_t ) d \mathbf{u}_t \]

 

최적 가치함수는 최적 행동가치 함수의 평균값이 아니라 최대값을 취하면 된다. 따라서 다음과 같다.

 

\[ \begin{align} V^\pi (\mathbf{x}_t ) & = \int_{\mathbf{u}_t} Q^\pi (\mathbf{x}_t, \mathbf{u}_t ) \pi (\mathbf{u}_t | \mathbf{x}_t ) d \mathbf{u}_t \\ \\ & \le \int_{\mathbf{u}_t} Q^\star (\mathbf{x}_t, \mathbf{u}_t ) \pi (\mathbf{u}_t | \mathbf{x}_t ) d \mathbf{u}_t \\ \\ & \le \max_{\mathbf{u}_t} Q^\star (\mathbf{x}_t, \mathbf{u}_t ) \int_{\mathbf{u}_t} \pi (\mathbf{u}_t | \mathbf{x}_t ) d \mathbf{u}_t \\ \\ & = \max_{\mathbf{u}_t} Q^\star (\mathbf{x}_t, \mathbf{u}_t ) \end{align} \]

 

따라서 가치함수의 최대값, 즉 최적 가치함수는 다음과 같다.

 

\[ V^\star (\mathbf{x}_t )= \max_{\mathbf{u}_t} Q^\star (\mathbf{x}_t, \mathbf{u}_t ) \]

 

최적 정책은 상태가치 값을 최대로 만드는 정책이므로 다음과 같이 계산할 수 있다.

 

\[ \pi^\star (\mathbf{x}_t )= \arg \max_{\mathbf{u}_t} Q^\star (\mathbf{x}_t, \mathbf{u}_t ) \]

 

따라서 최적 정책은 확정적(deterministic) 정책임을 알 수 있다.

 

 

이제 벨만의 최적성 원리를 이용하여 최적 상태가치 함수를 구해보자. 상태가치 함수에 대한 벨만 방정식은 다음과 같았다.

 

\[ V^\pi (\mathbf{x}_t ) = \mathbb{E}_{ \mathbf{u}_t \sim \pi (\mathbf{u}_t | \mathbf{x}_t ) } \left[ r_t + \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma V^\pi ( \mathbf{x}_{t+1} ) \right] \right] \]

 

벨만의 최적성 원리에 의하면 상태변수 \(\mathbf{x}_t\)에서 최대의 상태가치는 다음 식을 만족해야 한다.

 

\[ \begin{align} V^\star (\mathbf{x}_t ) &= \max_\pi \mathbb{E}_{ \mathbf{u}_t \sim \pi (\mathbf{u}_t | \mathbf{x}_t ) } \left[ r_t + \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma V^\star ( \mathbf{x}_{t+1} ) \right] \right] \\ \\ &= \max_{\mathbf{u}_t }⁡ \left[ r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma V^\star (\mathbf{x}_{t+1} ) \right] \right] \end{align} \]

 

여기서 최적 정책은 확정적 정책임을 고려하였다. 한편 행동가치 함수에 대한 벨만 방정식은 다음과 같으므로

 

\[ Q^\pi (\mathbf{x}_t, \mathbf{u}_t ) = r_t + \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \mathbb{E}_{ \mathbf{u}_{t+1} \sim \pi (\mathbf{u}_{t+1} | \mathbf{x}_{t+1} ) } \left[ \gamma Q^\pi ( \mathbf{x}_{t+1}, \mathbf{u}_{t+1} ) \right] \right] \]

 

최대의 행동가치는 다음 식을 만족해야 한다.

 

\[ \begin{align} Q^\star (\mathbf{x}_t, \mathbf{u}_t ) &= r_t + \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \max_\pi \mathbb{E}_{ \mathbf{u}_{t+1} \sim \pi (\mathbf{u}_{t+1} | \mathbf{x}_{t+1} ) } \left[ \gamma Q^\star ( \mathbf{x}_{t+1}, \mathbf{u}_{t+1} ) \right] \right] \\ \\ &= r_t + \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma \max_{\mathbf{u}_{t+1}} Q^\star ( \mathbf{x}_{t+1}, \mathbf{u}_{t+1} ) \right] \end{align} \]

 

위 두 식을 벨만 최적 방정식(Bellman optimality equation)이라고 한다. 벨만 최적 방정식은 현재의 최적 가치와 다음 시간스텝의 최적 가치와의 관계를 나타내는 식이다.

한편 최적 정책은 최적 상태가치 함수를 이용하여 다음과 같이 계산할 수도 있다.

 

\[ \pi^\star (\mathbf{x}_t ) = \arg \max_{\mathbf{u}_t }⁡ \left[ r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma V^\star (\mathbf{x}_{t+1} ) \right] \right] \]

 

 

 

댓글