가치 이터레이션 (Value Iteration)과 LQR

이번에는 벨만 최적 방정식을 이용하여 이산시간(discrete-time) LQR을 유도해 보도록 하자.

 

 

정책 이터레이션과 마찬가지로 마르코프 결정 프로세스(MDP)는 결정적(deterministic) 프로세스로 가정하고 환경 모델도 다음과 같다고 가정한다.

 

\[ \mathbf{x}_{t+1}=A \mathbf{x}_t+B \mathbf{u}_t \tag{1} \]

 

보상(reward)도 동일하게 다음과 같이 정의한다.

 

\[ r(\mathbf{x}_t, \mathbf{u}_t)= -\frac{1}{2} \left( \mathbf{x}_t^T Q \mathbf{x}_t+ \mathbf{u}_t^T R \mathbf{u}_t \right) \ \tag{2} \]

 

여기서 \( Q=Q^T \ge 0\), \(R=R^T \gt 0\) 이다. 이제 최적 상태가치 함수를 다음과 같이 정의한다.

 

\[ V^\star (\mathbf{x}_t)= -\frac{1}{2} \mathbf{x}_t^T P^\star \mathbf{x}_t \tag{3} \]

 

여기서 \(P^\star =P^{\star T} \gt 0\) 이다. 그러면, 벨만 최적 방정식에 의하여 다음 관계가 성립한다.

 

\[ \begin{align} 2V^\star (\mathbf{x}_t) &= -\mathbf{x}_t^T P^\star \mathbf{x}_t \tag{4} \\ \\ &= \max_{\mathbf{u}_t} \left( 2r(\mathbf{x}_t, \mathbf{u}_t) + 2 V^\star (\mathbf{x}_{t+1}) \right) \\ \\ &= \max_{\mathbf{u}_t} \left( -\mathbf{x}_t^T Q \mathbf{x}_t - \mathbf{u}_t^T R \mathbf{u}_t - (A \mathbf{x}_t+B \mathbf{u}_t)^T P^\star (A \mathbf{x}_t + B \mathbf{u}_t) \right) \end{align} \]

 

위 식에서 오른쪽 항을 최대로 만드는 \(\mathbf{u}_t\) 를 구하기 위하여 다음과 같이 미분을 수행한다.

 

\[ \begin{align} 0 &= \frac{\partial}{\partial \mathbf{u}_t} \left( -\mathbf{x}_t^T Q \mathbf{x}_t- \mathbf{u}_t^T R \mathbf{u}_t- (A \mathbf{x}_t+B\mathbf{u}_t)^T P^\star (A \mathbf{x}_t+B\mathbf{u}_t) \right) \tag{5} \\ \\ &= R \mathbf{u}_t+ B^T P^\star (A \mathbf{x}_t+B\mathbf{u}_t) \end{align} \]

 

그러면 최적 행동은 다음과 같이 구해진다.

 

\[ \mathbf{u}_t= K \mathbf{x}_t= - (B^T P^\star B+R)^{-1} B^T P^\star A \mathbf{x}_t \tag{6} \]

 

위 식을 식 벨만 최적 방정식에 대입하면,

 

\[ \begin{align} -\mathbf{x}_t^T P^\star \mathbf{x}_t &= -\mathbf{x}_t^T Q \mathbf{x}_t - \mathbf{x}_t^T K^T RK \mathbf{x}_t- \mathbf{x}_t^T (A+BK)^T P^\star (A+BK) \mathbf{x}_t \tag{7} \\ \\ &= - \mathbf{x}_t^T \left( A^T P^\star A-A^T P^\star B(B^T P^\star B+R)^{-1} B^T P^\star A+Q \right) \mathbf{x}_t \end{align} \]

 

이 되어, 다음과 같이 이산시간 대수 리카티 방정식(algebraic Riccati equation, ARE)를 얻을 수 있다.

 

\[ P^\star = A^T P^\star A-A^T P^\star B(B^T P^\star B+R)^{-1} B^T P^\star A+Q \tag{8} \]

 

따라서 이산시간 LQR에 대한 벨만 최적 방정식은 대수 리카티 방정식과 동일하다.

 

 

이제 가치 이터레이션을 이산시간 LQR에 적용해 보도록 한다. LQR에 대한 벨만 최적 방정식 (4)를 풀기 위해 가치 이터레이션을 적용하면 다음과 같다.

 

\[ \begin{align} 2V_{j+1} (\mathbf{x}_t) &= -\mathbf{x}_t^T P_{j+1} \mathbf{x}_t \tag{9} \\ \\ & \gets \max_{\mathbf{u}_t} \left( -\mathbf{x}_t^T Q \mathbf{x}_t - \mathbf{u}_t^T R \mathbf{u}_t - (A \mathbf{x}_t+B \mathbf{u}_t)^T P_j (A \mathbf{x}_t + B \mathbf{u}_t) \right) \end{align} \]

 

여기서 아래 첨자 \(j\) 는 최적 가치함수의 계산 반복 횟수를 나타낸다. 위 식에서 오른쪽 항을 최대로 만드는 \(\mathbf{u}_t\) 를 구하기 위하여 다음과 같이 미분을 수행한다.

 

\[ \begin{align} 0 &= \frac{\partial}{\partial \mathbf{u}_t} \left( -\mathbf{x}_t^T Q \mathbf{x}_t- \mathbf{u}_t^T R \mathbf{u}_t- (A \mathbf{x}_t+B\mathbf{u}_t)^T P_j (A \mathbf{x}_t+B\mathbf{u}_t) \right) \tag{10} \\ \\ &= R \mathbf{u}_t+ B^T P_j (A \mathbf{x}_t+B\mathbf{u}_t) \end{align} \]

 

위 식을 풀면, \(\mathbf{u}_t\) 가

 

\[ \mathbf{u}_t= - (B^T P_j B+R)^{-1} B^T P_j A \mathbf{x}_t \tag{11} \]

 

일 때 위 식의 오른쪽 항이 최대가 된다. 식 (11)을 (9)에 대입하면,

 

\[ P_{j+1} \gets A^T P_j A-A^T P_j B(B^T P_j B+R)^{-1} B^T P_j A+Q \tag{12} \]

 

가 되어, 이산시간 대수 리카티 방정식(ARE)의 재귀 형태(recursive form)가 된다.

 

 

위 식을 수렴할 때까지 반복하여 계산한다. 최적 정책은 최적 가치함수로부터 다음과 같이 계산하면 된다.

 

\[ \begin{align} \mathbf{u}_t &= \arg \max_{\mathbf{u}_t} \left( -\mathbf{x}_t^T Q \mathbf{x}_t - \mathbf{u}_t^T R \mathbf{u}_t - \mathbf{x}_{t+1}^T P^\star \mathbf{x}_{t+1} \right) \tag{13} \\ \\ &= -(B^T P^\star B+R)^{-1} B^T P^\star A \mathbf{x}_t \end{align} \]

 

여기서 \(P^\star\) 는 이산시간 대수 리카티 재귀 방정식 (12)의 수렴된 해이다.