19장 - 보상 모델과 선형 동적 시스템

19장. 보상 모델과 선형 동적 시스템

이번 강의에서는 MDP 프레임워크의 두 가지 일반화인 상태-행동 보상과 유한 지평 MDP를 다룬 뒤, 선형 동적 시스템과 이차 비용 함수를 결합한 선형 이차 조절기(LQR)를 유도한다. LQR은 적용 가능한 문제에서 근사 없이 최적 정책을 정확히 계산할 수 있는 강력한 알고리즘이다.

19.1 MDP 프레임워크의 일반화

지난 강의에서 기본적인 MDP의 구성 요소, 즉 상태, 행동, 상태 전이 확률, 할인 인자, 보상을 배웠다. 또한 적합 가치 반복(fitted value iteration)을 통해 상태 공간이 연속적인 경우에도 가치 함수를 근사하는 방법을 살펴보았다. 이번에는 이 프레임워크를 약간 확장하여 특정 유형의 문제를 더 쉽게 모델링할 수 있도록 한다.

첫 번째는 상태-행동 보상이고, 두 번째는 유한 지평 MDP다. 이 두 가지 일반화를 통해 로봇 제어나 공장 자동화 같은 문제를 더 자연스럽게 표현할 수 있다.

그 다음에는 **선형 동적 시스템(Linear Dynamical System)**을 다룬다. 상태 공간이 무한하고 연속적인 실수 집합이더라도, 특정 조건이 충족되면 가치 함수를 정확히 계산할 수 있는 특수한 경우가 존재한다. 선형 회귀 같은 함수 근사기를 사용해 가치 함수를 근사할 필요가 전혀 없다. 이 프레임워크가 모든 문제에 적용되는 것은 아니지만, 적용 가능한 경우에는 놀라울 만큼 효율적이고 편리하다.

참고로, 적합 가치 반복이나 오늘 배울 LQR 알고리즘은 실제로 자율 헬리콥터를 저속으로 비행시키는 데 충분히 작동한다. 초고속 비행이나 거꾸로 뒤집는 극단적인 기동에는 추가적인 기법이 필요하지만, 저속 비행에는 이 알고리즘들이 거의 그대로 사용된다.

19.2 상태-행동 보상

기존 MDP에서 보상 함수는 상태만의 함수였다.

\[R : S \to \mathbb{R}\]

상태-행동 보상에서는 보상 함수가 상태와 행동 모두의 함수로 확장된다.

\[R : S \times A \to \mathbb{R}\]

MDP에서 에이전트는 상태 \(s_0\)에서 출발하여 행동 \(a_0\)을 취하고, 상태 \(s_1\)에 도달하여 행동 \(a_1\)을 취하는 식으로 진행된다. 상태-행동 보상 체계에서 총 보상은 다음과 같이 표현된다.

\[R(s_0, a_0) + \gamma R(s_1, a_1) + \gamma^2 R(s_2, a_2) + \cdots\]

이 일반화가 유용한 이유는 서로 다른 행동이 서로 다른 비용을 가질 수 있음을 모델링할 수 있기 때문이다.

예시

• 미로 속 로봇: 가만히 서 있는 행동은 보상이 0이지만, 이동하는 행동은 전기를 소모하므로 약간의 음의 보상을 부여할 수 있다.
• 헬리콥터 비행: 조종간을 급격하게 당기는 행동은 헬리콥터를 심하게 흔들리게 하므로, 공격적인 기동에 높은 비용을 부과하는 보상 함수를 설정할 수 있다.
• 최단 경로 탐색: 스탠퍼드에서 샌프란시스코까지 운전할 때, 도로 구간마다 교통량이나 속도 제한에 따라 연료 소비나 소요 시간이 다르다. 이를 상태-행동 보상으로 자연스럽게 모델링할 수 있다.
• 공장 유지보수: 유지보수 팀을 보내는 행동에는 일정한 비용이 들고, 아무것도 하지 않는 행동에는 다른 비용이 들며, 기계가 고장 나면 또 다른 비용이 발생한다.

벨만 방정식의 변화

상태-행동 보상 체계에서 벨만 방정식은 다음과 같이 수정된다.

\[V^*(s) = \max_a \left[ R(s, a) + \gamma \sum_{s'} P_{sa}(s') V^*(s') \right]\]

기존 공식과 비교하면, \(\max\)가 즉각 보상 항까지 포함하도록 바깥으로 이동했다. 이는 즉각 보상이 현재 선택하는 행동에 의존하기 때문이다.

가치 반복(value iteration)은 이 형태에서도 동일하게 작동한다. \(V\)가 \(V^*\)로 수렴한 후, 최적 정책은 다음과 같다.

\[\pi^*(s) = \arg\max_a \left[ R(s, a) + \gamma \sum_{s'} P_{sa}(s') V^*(s') \right]\]

주어진 상태에서 즉각 보상과 기대 미래 보상의 합을 최대화하는 행동을 선택하는 것이다.

19.3 유한 지평 MDP

유한 지평 MDP에서는 할인 인자 \(\gamma\)를 사용하는 대신 지평 시간 \(T\)를 도입한다. MDP는 유한한 \(T\) 단계 동안만 실행된다.

\[s_0 \xrightarrow{a_0} s_1 \xrightarrow{a_1} s_2 \xrightarrow{a_2} \cdots \xrightarrow{a_T} \text{종료}\]

총 보상은 유한한 합으로 표현된다.

\[\text{총 보상} = R(s_0, a_0) + R(s_1, a_1) + \cdots + R(s_T, a_T)\]

할인을 적용할 수도 있지만, 유한 지평 설정에서는 보통 할인이 필요하지 않다.

실용적 예시

• RC 헬리콥터: 연료가 20~30분밖에 없다면, 그 시간 동안 보상을 최대한 축적한 뒤 착륙해야 한다.
• 비행기: 대형 상업 항공기는 이륙 시 연료가 전체 무게의 3분의 1 이상을 차지하기도 한다. 런던에 착륙할 때쯤이면 연료 소모로 무게가 극적으로 줄어들어 비행 역학이 달라진다.

비정상 정책

유한 지평 MDP의 흥미로운 성질은 최적 행동이 시계의 시간에 따라 달라질 수 있다는 것이다.

미로에서 왼쪽에 \(+1\) 보상이, 오른쪽에 \(+10\) 보상이 있다고 하자. 로봇이 중간에 있을 때 왼쪽으로 갈지 오른쪽으로 갈지는 남은 시간에 달려 있다. 시계에 2~3 단계만 남았다면 가까운 \(+1\)을 향해 달려가는 것이 낫다. 10~20 단계가 남았다면 멀리 있는 \(+10\)을 향해 가는 것이 최적이다.

따라서 최적 정책은 상태뿐 아니라 시간의 함수이기도 하다.

\[\pi^*_t(s)\]

이를 **비정상 정책(non-stationary policy)*이라 부른다. 시간에 따라 변하는 정책이라는 뜻이다. 이와 대조적으로, 무한 지평 할인 MDP에서의 최적 정책 $\pi^(s)$는 시간에 무관한 **정상 정책(stationary policy)**이었다.

비정상 전이 확률과 보상

비정상 정책을 사용하고 있다면, 상태 전이 확률이나 보상 역시 시간에 따라 달라지도록 확장할 수 있다.

\[P_{s_t, a_t}^{(t)}(s_{t+1}), \quad R_t(s, a)\]

예시는 다음과 같다.

• 교통 예측: 팔로알토에서 샌프란시스코까지 운전할 때, 오후 5~6시 러시아워에는 도로 상황이 변한다. 특정 도로 구간의 통과 시간이 시간대에 따라 달라지므로 상태 전이 확률이 비정상이 된다.
• 기상 예보: 오늘 밤 비가 올 것이라는 예보가 있다면, 지면이 진흙탕이 되어 역학이 변한다.
• 산업 자동화: 24시간 가동하는 공장에서 정오에 작업자를 부르는 비용과 새벽 3시에 부르는 비용은 다르다. 노동 가용성에 따라 행동의 비용이 시간에 따라 변한다.

유한 지평 MDP의 풀이: 동적 프로그래밍

최적 가치 함수를 시간 \(t\)와 상태 \(s\)의 함수로 정의한다.

\[V^*_t(s) = \text{시간 } t \text{에 상태 } s \text{에서 시작하여 최적 정책을 따를 때의 기대 총 보상}\]

가치 반복은 동적 프로그래밍 알고리즘이 된다.

기저 단계 (최종 시간 \(T\)):

\[V^*_T(s) = \max_a R(s, a)\]

시계가 다 되었으므로 즉각 보상만 최대화하면 된다. 이후 상태는 존재하지 않는다.

귀납 단계 (\(t = T-1, T-2, \ldots, 0\)):

\[V^*_t(s) = \max_a \left[ R(s, a) + \sum_{s'} P_{sa}(s') V^*_{t+1}(s') \right]\]

\(V^*_T\)를 먼저 계산한 뒤, \(V^*_{T-1}\), \(V^*_{T-2}\), ..., \(V^*_0\)의 순서로 역방향으로 계산해 나간다.

최적 정책은 다음과 같다.

\[\pi^*_t(s) = \arg\max_a \left[ R(s, a) + \sum_{s'} P_{sa}(s') V^*_{t+1}(s') \right]\]

비정상 상태 전이 확률이나 비정상 보상을 추가하는 것은 이 알고리즘에 대한 매우 작은 수정에 불과하다. 전이 확률과 보상에 시간 첨자 \(t\)만 추가하면 된다.

유한 지평과 무한 지평의 관계

\(T\)를 무한대로 보내면 일반적인 가치 반복이 되지 않을까 하는 의문이 생길 수 있다. 문제는 할인 없이 \(T\)를 무한대로 보내면 가치가 한없이 커진다는 것이다. 이것이 무한 지평 MDP에서 할인 인자를 사용하는 주된 이유 중 하나다. 할인 인자 \(\gamma\)를 사용하면 보상이 \(R_{\max}\)로 제한될 때 가치 함수는 \(\frac{R_{\max}}{1-\gamma}\)로 상한이 정해진다. 유한 지평에서는 보상을 \(T\) 번만 더하므로 \(T \cdot R_{\max}\)를 넘지 않는다.

19.4 선형 이차 조절기 (LQR)

**선형 이차 조절기(Linear Quadratic Regulator, LQR)**는 적용 가능한 문제의 범위가 제한적이지만, 적용 가능한 경우에는 매우 효율적이고 우수한 제어 정책을 제공하는 알고리즘이다. LQR은 유한 지평 MDP 형태를 사용한다.

MDP의 구성 요소

LQR이 적용되려면 다음 두 가지 핵심 가정이 필요하다.

가정 1: 선형 동적 시스템 (상태 전이)

상태 \(s \in \mathbb{R}^n\), 행동 \(a \in \mathbb{R}^d\)이며, 상태 전이는 다음과 같은 선형 함수로 주어진다.

\[s_{t+1} = A s_t + B a_t + w_t\]

여기서 - \(A\)는 \(n \times n\) 행렬 - \(B\)는 \(n \times d\) 행렬 - \(w_t \sim \mathcal{N}(0, \Sigma_w)\)는 가우시안 잡음

자동차 운전 문제를 예로 들면, 상태 공간은 \((x, y, \theta, \dot{x}, \dot{y}, \dot{\theta})\)로 6차원이고, 행동 공간은 가속과 조향으로 2차원이다.

참고: 여기서 \(A\)는 행렬인 동시에 행동 집합을 나타내는 기호이기도 하다. 이는 LQR의 아이디어가 전기공학과 기계공학의 제어 이론에서 유래했고, 강화 학습의 아이디어는 컴퓨터 과학에서 유래했기 때문이다. 두 분야의 문헌이 합쳐지면서 표기법이 충돌하게 되었다.

가정 2: 이차 비용 함수 (보상)

보상 함수는 다음과 같은 이차 형태를 갖는다.

\[R(s, a) = -(s^\top U s + a^\top V a)\]

여기서 - \(U\)는 \(n \times n\) 양의 준정부호(positive semi-definite) 행렬 - \(V\)는 \(d \times d\) 양의 준정부호 행렬

\(U\)와 \(V\)가 양의 준정부호이므로 \(s^\top U s \geq 0\)이고 \(a^\top V a \geq 0\)이다. 따라서 보상은 항상 0 이하이며, 상태와 행동이 0에 가까울수록 보상이 높아진다.

이차 비용 함수의 예시

자율 헬리콥터를 제자리에서 호버링하게 하려면 상태 벡터(위치, 방향, 속도, 각속도)를 0 근처로 유지해야 한다. \(U\)와 \(V\)를 단위 행렬로 설정하면 다음과 같다.

\[R(s, a) = -(\|s\|^2 + \|a\|^2)\]

이 비용 함수는 상태가 0에서 벗어나는 것과 큰 행동(급격한 조종간 조작)을 동시에 벌칙으로 부과한다. \(V = 0\)으로 설정하면 행동에 대한 벌칙이 사라지고, 상태만 0 근처에 유지하면 된다.

비정상 동적 시스템으로 확장하려면 행렬 \(A\), \(B\)를 시간에 따라 변하게 하거나(\(A_t\), \(B_t\)), 비용 행렬 \(U\), \(V\)를 시간에 따라 변하게 하면 된다(\(U_t\), \(V_t\)).

19.5 행렬 A와 B의 결정

선형 동적 시스템을 구성하려면 행렬 \(A\)와 \(B\)를 알아야 한다. 두 가지 방법이 있다.

방법 1: 데이터에서 학습

헬리콥터를 직접 비행시켜 데이터를 수집한다. \(m\)개의 궤적(trajectory)을 각각 \(T\) 단계씩 수집하면 다음과 같은 데이터가 모인다.

\[s_0, a_0, s_1, a_1, \ldots, s_T\]

\(s_{t+1} \approx A s_t + B a_t\)라는 모델을 가정하고, 좌변과 우변의 차이를 최소화하도록 행렬 \(A\)와 \(B\)를 피팅한다.

\[\min_{A, B} \sum \|s_{t+1} - (A s_t + B a_t)\|^2\]

이는 선형 회귀와 매우 유사한 절차다. 실제로 헬리콥터 비행 데이터를 수집하여 이 모델을 피팅하면, 저속 비행의 동적 시스템을 상당히 합리적으로 모사할 수 있다.

방법 2: 비선형 모델의 선형화

물리 시뮬레이터나 뉴턴 역학 방정식으로부터 비선형 동적 모델을 얻을 수 있는 경우가 있다.

\[s_{t+1} = f(s_t, a_t)\]

예를 들어, 도립 진자(inverted pendulum)의 경우 상태는 카트의 위치, 막대의 각도, 그리고 이들의 속도로 구성된다. 물리 방정식을 통해 현재 상태와 행동이 주어지면 다음 상태를 계산하는 함수 \(f\)를 유도할 수 있다.

선형화(linearization) 과정은 1차원 예시로 이해할 수 있다. \(s_{t+1} = f(s_t)\)라는 비선형 함수가 있을 때, 특정 점 \(\bar{s}_t\) 주변에서 접선을 그어 직선으로 근사한다.

\[s_{t+1} \approx f'(\bar{s}_t)(s_t - \bar{s}_t) + f(\bar{s}_t)\]

이 직선은 \(\bar{s}_t\) 근처의 작은 영역에서 원래 함수 \(f\)를 잘 근사한다. \(\bar{s}_t\)에서 멀어질수록 근사의 오차가 커지므로, 시스템이 대부분의 시간을 보낼 것으로 예상되는 점을 \(\bar{s}_t\)로 선택하는 것이 중요하다. 헬리콥터가 0 상태 근처에서 호버링하거나, 도립 진자가 막대를 세운 채 정지해 있는 경우라면 \(\bar{s}_t = \mathbf{0}\)으로 설정하는 것이 합리적이다.

상태와 행동 모두의 함수인 일반적인 경우로 확장하면 다음과 같다.

\[s_{t+1} \approx f(\bar{s}_t, \bar{a}_t) + \nabla_s f(\bar{s}_t, \bar{a}_t)^\top (s_t - \bar{s}_t) + \nabla_a f(\bar{s}_t, \bar{a}_t)^\top (a_t - \bar{a}_t)\]

여기서 \((\bar{s}_t, \bar{a}_t)\)는 선형화의 기준점, 즉 전형적인 상태와 행동이다. 이 수식은 \(s_{t+1}\)을 \(s_t\)와 \(a_t\)의 아핀 함수(일차 함수 + 상수)로 표현한다.

약간의 대수적 정리와 절편 항의 추가(상태 벡터에 절편 특성을 추가)를 통해 이를 다음 형태로 변환할 수 있다.

\[s_{t+1} = A s_t + B a_t\]

19.6 LQR의 동적 프로그래밍 풀이

LQR 문제를 공식적으로 정리하면 다음과 같다.

\[s_{t+1} = A s_t + B a_t + w_t, \quad w_t \sim \mathcal{N}(0, \Sigma_w)\]

\[R(s, a) = -(s^\top U s + a^\top V a)\]

\[\text{총 보상} = R(s_0, a_0) + R(s_1, a_1) + \cdots + R(s_T, a_T)\]

LQR의 핵심적인 성질은 가치 함수가 이차 함수라는 것이다. 이를 동적 프로그래밍으로 보인다.

기저 단계

최종 시간 \(T\)에서 최적 가치 함수를 구한다.

\[V^*_T(s_T) = \max_{a_T} R(s_T, a_T) = \max_{a_T} \left[ -(s_T^\top U s_T + a_T^\top V a_T) \right]\]

\(V\)가 양의 준정부호이므로 \(a_T^\top V a_T \geq 0\)이다. 이 항을 최소화하는 행동은 \(a_T = \mathbf{0}\)이다. 따라서

\[V^*_T(s_T) = -s_T^\top U s_T\]

최적 정책은 \(\pi^*_T(s_T) = \mathbf{0}\)이다. 마지막 시간 단계에서는 아무 행동도 취하지 않는 것이 최적이다.

귀납 단계

핵심 관찰: \(V^*_{t+1}\)이 다음과 같은 이차 함수라고 가정하자.

\[V^*_{t+1}(s_{t+1}) = s_{t+1}^\top \Phi_{t+1} \, s_{t+1} + \Psi_{t+1}\]

여기서 \(\Phi_{t+1}\)은 \(n \times n\) 행렬이고 \(\Psi_{t+1}\)은 실수 상수다. (기저 단계에서 \(\Phi_T = -U\), \(\Psi_T = 0\)이므로 가정이 성립한다.)

이제 한 단계의 동적 프로그래밍을 수행한다.

\[V^*_t(s_t) = \max_{a_t} \left[ R(s_t, a_t) + \mathbb{E}_{s_{t+1} \sim \mathcal{N}(As_t + Ba_t, \, \Sigma_w)} \left[ V^*_{t+1}(s_{t+1}) \right] \right]\]

이산 상태 공간에서 \(\sum_{s'} P_{sa}(s') V^*(s')\)로 표현되던 부분이, 연속 상태 공간에서는 기댓값 \(\mathbb{E}[\cdot]\)으로 대체된다.

대괄호 안의 표현을 전개하면, 가우시안 분포에 대한 이차 함수의 기댓값을 계산하게 된다. 이를 정리하면 전체 표현이 \(a_t\)에 대한 이차 함수가 된다. 이차 함수를 \(a_t\)에 대해 미분하고 0으로 놓으면 최적 행동을 구할 수 있다.

대수적 유도를 거치면 최적 행동은 다음과 같다.

\[a_t^* = L_t \, s_t\]

여기서

\[L_t = -(B^\top \Phi_{t+1} B + V)^{-1} B^\top \Phi_{t+1} A\]

이것이 의미하는 바는 매우 중요하다. 최적 행동은 상태의 선형 함수다. 이는 직선을 피팅해서 얻은 근사가 아니다. 선형이든 비선형이든 세상에 존재할 수 있는 모든 함수 중에서, 최적의 행동은 정확히 선형이라는 사실이다. 어떤 근사도 포함되어 있지 않다.

최적 행동을 \(V^*_t\)의 정의에 대입하고 정리하면, \(V^*_t\) 역시 이차 함수 형태가 된다.

\[V^*_t(s_t) = s_t^\top \Phi_t \, s_t + \Psi_t\]

갱신 공식은 다음과 같다.

\[\Phi_t = A^\top \Phi_{t+1} A - A^\top \Phi_{t+1} B (B^\top \Phi_{t+1} B + V)^{-1} B^\top \Phi_{t+1} A - U\]

\[\Psi_t = \Psi_{t+1} + \text{tr}(\Sigma_w \Phi_{t+1})\]

여기서 \(\text{tr}(\cdot)\)은 대각합(trace) 연산이다.

19.7 LQR 알고리즘 요약

전체 알고리즘을 정리하면 다음과 같다.

초기화:

\[\Phi_T = -U, \quad \Psi_T = 0\]

역방향 반복 (\(t = T-1, T-2, \ldots, 0\)):

1. \(L_t\)를 계산한다. \[L_t = -(B^\top \Phi_{t+1} B + V)^{-1} B^\top \Phi_{t+1} A\]

2. \(\Phi_t\)를 갱신한다. \[\Phi_t = A^\top \Phi_{t+1} A - A^\top \Phi_{t+1} B (B^\top \Phi_{t+1} B + V)^{-1} B^\top \Phi_{t+1} A - U\]

3. \(\Psi_t\)를 갱신한다. \[\Psi_t = \Psi_{t+1} + \text{tr}(\Sigma_w \Phi_{t+1})\]

최적 정책:

\[\pi^*_t(s_t) = L_t \, s_t\]

이 알고리즘의 주목할 만한 성질은, MDP를 선형 동적 시스템과 이차 비용 함수로 모델링한 이후에는 어떤 근사도 포함되지 않는다는 것이다. 가치 함수가 이차 함수인 것은 근사가 아니라 사실이며, 최적 정책이 선형 함수인 것도 사실이다. 근사가 필요한 단계는 오직 현실의 시스템을 선형 동적 시스템으로 모델링하는 과정(데이터 피팅 또는 선형화)과, 보상 함수를 이차 형태로 제한하는 과정뿐이다.

19.8 잡음에 대한 흥미로운 성질

LQR에는 매우 독특하고 흥미로운 성질이 하나 있다.

\(L_t\)의 공식을 보면 \(\Phi\)에만 의존하고 \(\Psi\)에는 의존하지 않는다. 또한 \(\Phi_t\)의 갱신 공식도 \(\Phi_{t+1}\)에만 의존하고 \(\Psi_{t+1}\)에는 의존하지 않는다. 한편, \(\Sigma_w\)(잡음의 공분산)가 등장하는 유일한 곳은 \(\Psi_t\)의 갱신 공식뿐이다.

따라서 \(\Psi_t\)를 아예 계산하지 않아도 최적 정책 \(L_t\)를 온전히 구할 수 있다. 이는 다음을 의미한다.

최적 정책은 잡음의 공분산 \(\Sigma_w\)에 의존하지 않는다.

최적 가치 함수 \(V^*\)는 \(\Sigma_w\)에 의존한다. 잡음이 크면(거센 돌풍이 헬리콥터를 흔들면) 가치는 낮아진다. 그러나 최적 정책 \(\pi^*\)와 \(L_t\)는 \(\Sigma_w\)와 무관하다.

이 성질은 LQR에만 해당되며, 다른 강화 학습 알고리즘에는 일반화되지 않는다. 그러나 실용적으로 중요한 직관을 제공한다.

• LQR을 적용할 때 \(\Sigma_w\)를 정밀하게 추정할 필요가 없다. 수학적으로 정확히 최적 정책에 영향을 미치지 않기 때문이다.
• 일반적인 MDP에서도, 시스템에 잡음을 추가하는 것 자체가 중요하지, 잡음의 정확한 수준이 10% 높거나 낮은 것은 생각보다 중요하지 않은 경우가 많다. 행렬 \(A\)와 \(B\)를 정확하게 추정하는 것이 잡음 모델의 정밀도보다 훨씬 더 중요하다.

핵심 정리

이전 장: 18장 - 연속 상태 MDP와 모델 시뮬레이션 다음 장: 20장 - 강화 학습 디버깅과 진단