LQR, Riccati, and the Bellman Bridge

이 문서는 discrete-time finite-horizon LQR에서 optimal feedback gain과 Riccati recursion을 유도하고, infinite-horizon DARE·MPC·Bellman equation·Kalman filtering과의 관계를 조건과 함께 정리합니다.

1. LQR 문제의 정의와 가정
2. Finite-horizon Bellman recursion
3. Quadratic value function의 closure
4. Optimal feedback gain 유도
5. Riccati recursion 유도
6. Infinite-horizon limit와 DARE
7. Stabilizing solution의 조건
8. Constrained MPC와의 정확한 관계
9. Bellman equation과 RL의 관계
10. Kalman filtering과 Riccati duality

1. LQR 문제의 정의와 가정

Finite-horizon discrete-time LQR은 다음 linear time-varying dynamics를 다룹니다.

x_{k+1}=A_kx_k+B_ku_k,\qquad k=0,\ldots,N-1.

Regulation cost는

J= x_N^{\top}Q_Nx_N+ \sum_{k=0}^{N-1} \left(x_k^{\top}Q_kx_k+u_k^{\top}R_ku_k\right)

이며 표준 가정은

Q_k=Q_k^{\top}\succeq0,\qquad Q_N=Q_N^{\top}\succeq0,\qquad R_k=R_k^{\top}\succ0

입니다. $Q_k\succeq0$ 은 state cost가 음수가 되지 않게 합니다. $R_k\succ0$ 은 각 stage의 minimization이 $u_k$ 에 대해 strictly convex가 되게 하는 간단하고 표준적인 충분조건입니다. Generalized LQR에서는 더 약한 조건도 가능하므로, $R_k\succ0$ 이 모든 formulation에서 논리적으로 필요한 것은 아닙니다. 비용 각 항의 의미는 Anatomy of the LQR Cost Function에 정리되어 있습니다.

여기서 LQR은 문제 class의 이름입니다. Riccati recursion은 이 문제를 푸는 구조화된 방법이며, LQR의 정의 자체는 아닙니다.

2. Finite-horizon Bellman recursion

시각 $k$ 의 value function을

V_k(x)= \min_{u_k,\ldots,u_{N-1}} \left[ x_N^{\top}Q_Nx_N+ \sum_{j=k}^{N-1} \left(x_j^{\top}Q_jx_j+u_j^{\top}R_ju_j\right) \right]

로 정의합니다. Terminal condition은

V_N(x)=x^{\top}Q_Nx

입니다. Bellman principle을 적용하면 전체 horizon의 minimization을 한 stage와 남은 cost-to-go로 분리할 수 있습니다.

\boxed{ V_k(x)= \min_u \left[ x^{\top}Q_kx+u^{\top}R_ku+ V_{k+1}(A_kx+B_ku) \right] }

이 식은 미래의 optimal decisions가 $V_{k+1}$ 에 이미 포함되어 있다는 뜻입니다. 따라서 시각 $k$ 에서는 현재 입력 $u$ 만 최소화하면 됩니다. 일반 Bellman equation과의 관계는 Markov Decision Process (MDP)를 참고합니다.

3. Quadratic value function의 closure

Terminal value function이 quadratic이므로 다음 induction hypothesis를 둡니다.

V_{k+1}(x)=x^{\top}P_{k+1}x,\qquad P_{k+1}=P_{k+1}^{\top}\succeq0.

이를 Bellman recursion에 대입합니다.

\begin{aligned} V_k(x) &=\min_u\left[ x^{\top}Q_kx+u^{\top}R_ku+ (A_kx+B_ku)^{\top}P_{k+1}(A_kx+B_ku) \right] &&\text{(definition substitution)}\\ &=\min_u\left[ x^{\top}(Q_k+A_k^{\top}P_{k+1}A_k)x +2x^{\top}A_k^{\top}P_{k+1}B_ku +u^{\top}(R_k+B_k^{\top}P_{k+1}B_k)u \right] &&\text{(quadratic expansion)}. \end{aligned}

다음을 정의합니다.

G_k=R_k+B_k^{\top}P_{k+1}B_k,\qquad F_k=B_k^{\top}P_{k+1}A_k.

$P_{k+1}\succeq0$ 이므로 $B_k^{\top}P_{k+1}B_k\succeq0$ 입니다. 따라서 $R_k\succ0$ 이면 $G_k\succ0$ 이고 $G_k^{-1}$ 가 존재합니다.

4. Optimal feedback gain 유도

$u$ 에 의존하는 항은

u^{\top}G_ku+2x^{\top}F_k^{\top}u

입니다. Completing the square을 적용하면

\begin{aligned} u^{\top}G_ku+2x^{\top}F_k^{\top}u &= (u+G_k^{-1}F_kx)^{\top}G_k (u+G_k^{-1}F_kx) -x^{\top}F_k^{\top}G_k^{-1}F_kx &&\text{(completing the square)}. \end{aligned}

$G_k\succ0$ 이므로 첫 항의 unique minimizer는

u_k^{\ast}=-G_k^{-1}F_kx_k

입니다. 따라서

\boxed{ u_k^{\ast}=-K_kx_k,\qquad K_k= \left(R_k+B_k^{\top}P_{k+1}B_k\right)^{-1} B_k^{\top}P_{k+1}A_k }

를 얻습니다. Feedback form을 미리 가정한 것이 아니라, Bellman minimization의 해가 state에 linear한 형태로 나온 것입니다.

Gradient로도 같은 결과를 얻을 수 있습니다.

\nabla_uJ_k =2G_ku+2F_kx=0 \quad\Longrightarrow\quad u^{\ast}=-G_k^{-1}F_kx.

필요한 matrix derivative는 Matrix Calculus (Gradients)에 정리되어 있습니다.

5. Riccati recursion 유도

Square-completed 식에 $u_k^{\ast}$ 를 대입하면 제곱항이 $0$ 이 됩니다.

\begin{aligned} V_k(x) &=x^{\top} \left( Q_k+A_k^{\top}P_{k+1}A_k -F_k^{\top}G_k^{-1}F_k \right)x &&\text{(optimal input substitution)}\\ &=x^{\top}P_kx &&\text{(definition of }P_k\text{)}. \end{aligned}

따라서 backward Riccati recursion은

\boxed{ P_k= Q_k+A_k^{\top}P_{k+1}A_k -A_k^{\top}P_{k+1}B_k \left(R_k+B_k^{\top}P_{k+1}B_k\right)^{-1} B_k^{\top}P_{k+1}A_k }

이며 시작값은 $P_N=Q_N$ 입니다. 이 결과로 induction이 닫힙니다. 즉 $V_{k+1}$ 이 quadratic이면 $V_k$ 도 quadratic이며, terminal condition부터 $k=N-1,\ldots,0$ 순서로 계산할 수 있습니다.

같은 recursion은 다음 closed-loop form으로도 쓸 수 있습니다.

P_k= Q_k+K_k^{\top}R_kK_k +(A_k-B_kK_k)^{\top}P_{k+1}(A_k-B_kK_k).

이 형태는 $P_k\succeq0$ 과 cost decomposition을 확인할 때 유용합니다.

6. Infinite-horizon limit와 DARE

Time-invariant system

x_{k+1}=Ax_k+Bu_k

과 constant stage cost matrices $Q,R$ 를 고려합니다. 적절한 조건 아래 finite-horizon recursion의 초기 구간이 stationary limit $P$ 로 수렴하면 $P_k=P_{k+1}=P$ 를 대입할 수 있습니다.

\boxed{ P=Q+A^{\top}PA -A^{\top}PB(R+B^{\top}PB)^{-1}B^{\top}PA }

이 식이 discrete-time algebraic Riccati equation, DARE입니다. Stationary gain은

K=(R+B^{\top}PB)^{-1}B^{\top}PA

이며 closed-loop dynamics는

x_{k+1}=(A-BK)x_k

입니다. DARE의 해가 여러 개일 수 있으므로 실제로 필요한 것은 $A-BK$ 를 Schur stable하게 만드는 stabilizing solution입니다.

Continuous-time CARE와의 관계는 Hamilton-Jacobi-Bellman (HJB)에 정리되어 있습니다. DARE에서 sampling interval만 형식적으로 $0$ 으로 보내는 것으로 CARE가 자동으로 나오지는 않습니다. Dynamics와 cost를 같은 sampling convention으로 discretize한 뒤 limit를 취해야 합니다.

7. Stabilizing solution의 조건

표준 infinite-horizon discrete LQR에서 다음 조건을 사용합니다.

$R\succ0$ , $Q\succeq0$
$(A,B)$ 가 stabilizable
$(A,Q^{1/2})$ 가 detectable

Stabilizable은 모든 unstable mode가 input으로 제어 가능하다는 뜻입니다. Detectable은 cost가 보지 못하는 mode가 모두 stable하다는 뜻입니다. 자세한 정의와 PBH test는 Controllability, Observability, Stabilizability, Detectability에 있습니다.

이 조건 아래에서 표준 DARE는 unique stabilizing PSD solution을 가지며, 그 해가 만든 $A-BK$ 는 Schur stable합니다. 여기서 detectability의 output matrix는 physical sensor matrix가 아니라 $Q^{1/2}$ 입니다. 즉 state cost가 unstable mode를 감지해야 합니다.

Finite-horizon recursion 자체에는 stabilizability와 detectability가 필요하지 않습니다. 이 조건들은 infinite-horizon stabilizing limit의 존재와 성질에 관한 조건입니다.

8. Constrained MPC와의 정확한 관계

Linear dynamics와 quadratic cost를 쓰는 finite-horizon optimal control problem은 input sequence를 decision variable로 두면 convex QP로 쓸 수 있습니다. State 또는 input inequality constraint를 추가하면 일반적으로 unconstrained LQR의 single linear feedback law는 유지되지 않습니다.

다만 다음 조건에서는 finite-horizon problem과 infinite-horizon LQR의 첫 입력이 정확히 일치합니다.

Dynamics와 stage cost가 time-invariant입니다.
Inequality constraint가 없거나 optimal trajectory에서 모두 inactive입니다.
Terminal cost가 stabilizing DARE solution $P$ 인 $x_N^{\top}Px_N$ 입니다.

이때 Bellman fixed point가 horizon 끝에 이미 주어졌으므로 backward recursion의 모든 $P_k$ 가 같은 $P$ 로 유지되고, 모든 stage에서 $u_k^{\ast}=-Kx_k$ 가 나옵니다.

MPC 전체를 “constrained LQR”로 정의할 수는 없습니다. MPC는 nonlinear dynamics, nonquadratic cost, time-varying model도 포함하는 더 넓은 framework입니다. 다만 linear-quadratic MPC에서는 LQR의 Riccati solution이 terminal cost와 local feedback 설계에 직접 사용됩니다. 실제 constrained legged-locomotion 사례는 Convex MPC for Legged Locomotion에 있습니다.

9. Bellman equation과 RL의 관계

LQR과 reinforcement learning은 모두 dynamic programming의 Bellman principle을 사용합니다. 그러나 두 문제의 수렴 조건을 같은 것으로 취급하면 안 됩니다.

항목	LQR	일반 RL 또는 MDP
state와 action	continuous vector	discrete 또는 continuous
dynamics	알려진 linear model	알려지거나 unknown인 transition law
objective	quadratic cost 최소화	expected return 최대화 또는 cost 최소화
value representation	정확한 quadratic form $x^{\top}Px$	일반적으로 table 또는 function approximation
solution	Riccati recursion	DP, sampling, optimization, learning 등

Discount factor는 infinite discounted return과 Bellman operator의 contraction에 관여합니다. Stabilizability와 detectability는 undiscounted LQR에서 stabilizing finite-cost solution의 존재에 관여합니다. 서로 관련된 맥락은 있지만 같은 조건의 다른 표현은 아닙니다.

LQR의 action-value function 역시 quadratic form으로 표현할 수 있습니다. 하지만 이를 data에서 학습해 optimal controller를 얻으려면 quadratic parameterization, 충분한 excitation, identifiable data, 그리고 수렴 조건을 갖춘 learning algorithm이 필요합니다. Quadratic regression 하나만으로 model-free optimal control이 자동으로 성립하지는 않습니다.

10. Kalman filtering과 Riccati duality

LQR의 control Riccati recursion과 Kalman filter의 covariance recursion은 transpose duality를 가집니다. Time-invariant notation에서 대표적인 대응은 다음과 같습니다.

Control	Estimation
dynamics matrix $A$	transposed dynamics $A^{\top}$
input matrix $B$	measurement matrix $H^{\top}$
state cost $Q$	process covariance $Q$
input cost $R$	measurement covariance $R$
feedback gain $K_c$	predictor gain $L=A K_f$ 의 transpose
controllability·stabilizability	observability·detectability

두 Riccati equation이 같은 문제라는 뜻은 아닙니다. Control Riccati equation은 deterministic optimal cost-to-go의 quadratic coefficient를 계산하고, estimation Riccati equation은 estimation error covariance를 계산합니다. Algebraic structure가 dual한 것입니다. 위 대응에서 $K_f=P^-H^{\top}(HP^-H^{\top}+R)^{-1}$ 는 measurement correction gain이고, prior-covariance DARE의 subtraction term에 직접 나타나는 dual gain은 $L=A K_f$ 입니다.

Partial observation 아래에서 LQR controller와 Kalman filter를 결합하면 LQG controller가 됩니다. 표준 formulation은 linear dynamics, quadratic cost, risk-neutral expected objective, unconstrained input, Gaussian initial state, 그리고 known covariances를 가진 zero-mean white Gaussian process·measurement noise를 가정합니다. 두 noise sequence는 서로 independent이고 initial state와도 independent입니다. 이 조건 아래에서는 separation principle에 의해 estimator와 controller를 따로 설계할 수 있습니다. Infinite-horizon stationary gains와 stability에는 control·estimation Riccati equations의 stabilizability·detectability conditions가 추가로 필요합니다. Riccati duality는 Kalman Filtering L7 §6, separation과 LQG의 조건·한계는 Kalman Filtering L7 §7과 Kalman Filtering L7 §8에서 다룹니다.

이해 확인

1. Finite-horizon Riccati recursion을 계산하는 방향과 그 이유를 설명하시오.

2. Finite-horizon recursion과 infinite-horizon stabilizing solution에서 요구되는 조건이 다른 이유를 설명하시오.

3. Finite-horizon linear-quadratic MPC의 첫 입력이 infinite-horizon LQR과 일치하는 조건을 쓰시오.

4. Control Riccati equation과 estimation Riccati equation에서 matrix $P$ 가 각각 무엇을 나타내는지 설명하시오.

답

1. $P_N=Q_N$ 에서 시작해 $k=N-1$ 부터 $0$ 까지 backward로 계산합니다. Bellman recursion에서 현재 value function이 다음 시각의 $P_{k+1}$ 에 의존하기 때문입니다. → §5

2. Finite horizon에서는 terminal cost부터 유한 횟수만 recursion을 계산하면 됩니다. Infinite horizon에서는 stationary limit가 존재하고 그 해가 closed loop를 안정화해야 하므로 stabilizability와 detectability가 추가로 필요합니다. → §7

3. Time-invariant dynamics와 stage cost, inactive inequality constraints, 그리고 stabilizing DARE solution을 사용한 terminal cost가 필요합니다. → §8

4. Control에서 $P$ 는 optimal cost-to-go의 quadratic coefficient이고, estimation에서 $P$ 는 estimation error covariance입니다. 식의 구조는 dual하지만 의미는 다릅니다. → §10

Related: LQR and the Riccati Equation · Anatomy of the LQR Cost Function · Hamilton-Jacobi-Bellman (HJB) · Kalman Filtering

목차