LQR, DDP, LQG

해당 글은 cs229-notes13를 참고하여 작성되었습니다.

1. Finite-horizon MDPs

• MDP : 의사결정 문제의 수학적 모델링
  1. 상태($s_t$)에서 행동($a_t$)선택 -> 다음상태($s_t$)로 전이
  2. 위의 과정에서 에이전트는 보상을 받음
  3. 에이전트의 목표는 최대한 많은 보상을 받는 Policy 찾기
• optimal Bellman equation : 현재상태의 최적가치함수($V^{\pi^*}(s)$)와 다음 상태의 최적가치함수($V^{\pi^*}(s')$)의 관계식
  $V^{\pi^*}(s) = R(s) +max_{a} \sum_{s'}P_{sa}(s')V^{\pi^*}(s')$
  $\pi^{*}(s) = argmax_{a} \sum_{s'}P_{sa}(s')V^{\pi^*}(s')$
  - 이때 $V$는 가치함수로, cost-to-go이며 $\pi$는 policy이다. *가 붙는건 최적이라는 의미
  
• general setting
  1. discrete 및 continuous 모두 커버하기 위해 $\sum$표기를 기댓값 표기로 변경
  2. "즉시 보상" 개념 도입 -> 현재 state에서 action에 따른 보상 역시 현재의 최적 policy 항에 포함됨
  3. 유한 시간 범위의 MDP 고려
     - "남은 step 수"의 존재에 따라서 policy, 전이확률분포, 보상함수가 시간의 함수가 되어버림
     • 전이함수는 왜 시간의 함수가 되는가? : 상태 중 일부였던 시간을 따로 빼서 생각한다고 보면됨.
• Finite-horizon MDPs에서 최적가치함수 찾는 법
  • back ground : 유한시간의 마지막 스텝에선 "다음스텝의 가치함수"항이 없음
  • 알고리즘
  1. $V_T^*$ 계산 (유한 시간 중 가장 마지막 step)
  2. $V_t^*$를 이용하여 $V_{t-1}^*$ 계산 (가장 마지막의 전 step으로부터 0스텝이 될때까지)

2. LQR

• 가정
  1. 선형 전이 모델(노이즈 포함)
     • $s_{t+1} = A_ts_t + B_ta_t + w_t$
       • $w_t \sim \mathcal{N}(0, \sum_t)$
  2. 2차 보상함수 모델
     • $R^{(t)}(s_t,a_t) = -s_t^{\top} U_ts_t - a_t^{\top} W_ta_t$
     • 위의 보상함수에 따르면 입력도 작고 상태도 origin에 가까울수록 보상이 큰 것. 이는 최종 목표상태를 보통 원점으로 두기 때문
• LQR 알고리즘
  1. 만약 모델의 $A,B,\sum$을 모른다면, 임의의 정책으로 전이들을 모으고, 이걸로 가장 전이함수를 잘 나타내는 $A,B$ 찾기
  2. DP로 최적 정책 찾기
  1. Initialization step : $V^*_T(s_T) = -s_T^{\top}U_Ts_T$로 마지막 step의 최적가치함수 계산
  2. Recurrence step : $V^*_{t+1}(s_{t+1})$이 state에 대해 2차면 $V^*_{t}(s_{t})$도 state에 대해 2차임을 사용해 이의 미분이 0이 되도록 하는 $a$가 $a^*$임을 이용하여 $a_t^*$찾기
     • $a^*_t = [(B_t^{\top}\Phi_{t+1}B_t-W_t)^{-1}B_t\Phi_{t+1}A_t]\cdot s_t = L_t \cdot s_t$
     • $L_t = [(B_t^{\top}\Phi_{t+1}B_t-W_t)^{-1}B_t\Phi_{t+1}A_t]$
     • $\Phi_t = A_t^{\top}(\Phi_{t+1}-\Phi_{t+1}B_t(B_t^{\top}\Phi_{t+1}B_t-W_t)^{-1}B_t\Phi_{t+1})A_t - U_t$
     • $\Psi_t = -tr(\sum_t \Phi_{t+1})+\Psi_{t+1}$
  • Optimal policy is linear in $s_t$
  • $\Phi_t$ depens on neither $\Psi$ nor the noise $\sum_t$
  • optimal policy also does not depend on the noise

3. From non-linear dynamics to LQR

• Linearization of dynamics : 비선형 동역학을 1차 테일러 전개를 통해 특정지점에서의 선형 동역학으로 근사
  1. $s_{t_1} = F(s_t) \approx F(\bar{s}_t) + F'(\bar{s}_t)\cdot (s_t - \bar{s}_t)$
  2. $s_{t_1} \approx F(\bar{s}_t,\bar{a}_t) + \nabla_sF(\bar{s}_t,\bar{a}_t)\cdot (s_t - \bar{s}_t) + \nabla_aF(\bar{s}_t,\bar{a}_t)\cdot (a_t - \bar{a}_t)$
  3. $s_{t+1} \approx As_t + Ba_t + \kappa$
     • 이때 $\kappa$는 상수. 즉, LQR의 전제처럼 Linear하지 않은 동역학이 됨. 이는 $s_t$의 차원을 하나 늘려서 선형으로 바꾸는 trick 사용
• DDP : 각 time step마다 nominal trajectory을 discrete하게 나눠서 각 지점에 대해 동역학을 근사화하고 LQR을 돌림
  • 이때 nominal trajectory는 비선형 동역학을 따르므로, step이 증가하면 다시 다음 지점에 대해 동역학을 선형화하고 LQR을 돌려야함. stopping criterion까지

4. LQG

• POMDP에서 사용가능한 LQR
  • POMDP : 각 time step에서 state의 정보를 전부 알 수 있는게 아님. state를 관측하여 관측치만 알 수 있음
  • 모델
    • $s_{t+1} = A_ts_t + B_ta_t + w_t$
    • $y_t = C \cdot s_t + v_t$
      • 이때 $R^(t)$는 MDP와 똑같음. 안달라짐
      • $w_t, v_t$는 모두 가우시안 분포를 따음
  • LQG 알고리즘
    1. 우리가 가진 관찰로 belif state distribution 계산
       $s_t|y_1,\cdots,y_t \approx \mathcal{N}(s_{t|t}, \sum_{t|t})$
    2. $s_{t|t}$를 $s_t$의 가장 좋은 근사로 사용
       • LQR이 노이즈에 대해 독립이라 이래도 됨
    3. $a_t := L_ts_{t|t}$로 LQR돌림
  • Kalman filter : $s_{t|t}$와 $\sum_{t|t}$를 구하는 것은 칼만필터 사용을 추천