Dimitri의 2014 ADP - Lec.1

본 글은 Dimitri P. Bertsekas가 2014년 칭화대에서 강의한 Approximate Dynamic Programming의 강의자료를 공부하며 적는 글입니다.

web.mit.edu/dimitrib/www/publ.html

전체 강의 자료는 아래에서 다운로드 받을 수 있습니다. There is a complete lecture slide.

Dimitri Bertsekas - Approximate Dynamic Programming(2014)

web.mit.edu/dimitrib/www/ADP_Slides_Tsinghua_Complete.pdf

해당 강의는 아래 유튜브 채널에서 만나볼 수 있습니다.

www.youtube.com/channel/UCToelS8rQMz5hOBZqdgfAjQ/featured

 

 

강의 1의 목차

 - 동적계획법(DP)와 근사적 동적 계획법의 소개

 - 유한-지평선 문제

 - 유한-지평선 문제를 위한 동적 계획법 알고리즘

 - 무한-지평선 문제

 - 할인되는 무한-지평선 문제의 기초 이론

 

최적화 방법론으로써의 동적 계획법

일반적인 최적화 문제는 다음과 같다.

$$\underset{u \in U} {\text{min}} g(u) $$

 $u$는 최적화/결정 변수, $g(u)$는 비용 함수, $U$는 구속 집합이다.

 한 줄로 의미를 정리하면 할 수 있는 행동 중에서 비용 함수를 최소화 하는 행동을 구하는데에 목적이 있다.

문제의 범주

 - 이산 (유한 $U$) 또는 연속

 - 선형 ($g$가 선형이고 $U$가 다면체) 또는 비선형

 - 확률적 또는 결정론적 : 확률적 문제는 비용이 확률적 변수 $w$를 포함한다.

$$g(u) = E_w \left[G(u, w) \right]  $$

 

DP는 다단 확률론적 문제 Multi-stage stochastic problem을 다룬다.

 - $w$에 대한 정보는 단계에서 밝혀진다.

 - 의사 결정은 단계에서 이루어지며, 가용한 정보를 사용한다.

 - 이 방법론은 "다르다"

확률론적 동적 계획법의 기본 구조

다음의 이산 시스템이 있다.

$$x_{k+1} = f_k \left( x_k , u_k ,w_k \right) ,\hspace{10mm} k=0,1,\cdots,N-1$$

 - $k$ : 이산 시간

 - $x_k$ : 상태, 미래의 최적화와 관련된 과거의 정보를 함축하고 있다.

 - $u_k$ : 제어, 주어진 집합 내의 시간 $k$일때 선택된 결정

 - $w_k$ : 무작위 변수 라고도 하며 문맥에 따라서 '외란'이나 '소음'이라고도 부른다.

 - $N$ : 지평면 또는 제어해온 시간이다.

시간이 지나면서 다음의 비용함수가 더해진다.

$$E \left\{ g_N (x_N) + \sum_{k=0}^{N-1} g_k (x_k , u_k , w_k ) \right\}$$

시스템의 다른 표현은 다음과 같다. $x_{k+1} = w_k$이라면 $P(w_k | x_k ,u_k ) = P( x_{k+1} | x_k , u_k ) $ 이라서 이다.

$$P\left(x_{k+1} | x_k ,u_k \right)$$

 

창고를 관리하는 문제

현재 시간 $k$의 재고 $x_k$, 주문 $u_k$, 수요 $w_k$에 대해, 다음 시간 $k+1$의 재고 $x_{k+1}$는 다음과 같다.

다음 타임의 재고는 지금 재고 $x_k$ 와 주문해서 받은 량 $u_k$ , 팔아서 나간 양 $w_k$ 이다.

$$x_{k+1} = f_k (x_k ,u_k ,w_k ) = x_k + u_k -w_k$$

재고보관에 써온 돈인 비용 함수 $J$는 시간이 지남에 따라 현재 보관 비용인 $g_N (x_N)$ 이 더해진다.

$$ J(x_N) = E \left\{ g_N (x_N) + \sum_{k=0}^{N-1} g_k (x_k , u_k , w_k ) \right\} = E\left\{ \sum_{k=0}^{N-1} \left(cu_k + r(x_k + u_k -w_k ) \right) \right\}$$

 

추가 가정들

 $w_k$의 확률 분포는 과거 값 $w_{k-1}, \cdots, w_0$에 의존하지 않는다. 그러나 $x_k, u_k$에 의존할 수 있다. 다른 말로 $w, x, u$의 과거 값은 미래 최적화에 유용할 수 있다. 시간 $k$에 선택한 $u_k$인 구속 집합은 과거의 $x, u$가 아니라 현재의 $x_k$에 주효하게 의존한다.

정책에 대한 최적화 Optimization over policies(feedback control laws라고도 부른다)는 다음의 규칙이 있다.

$$u_k = \mu_k (x_k ), \hspace{10mm} k=0, \cdots, N-1$$

규칙은 상태(창고)를 제어(주문)에 사상한다. (Closed-loop optimization, use of feedback)

주요 차이점은 규칙 집합, 정책의 비용 함수를 최소화한다.

$$\left\{ \mu_0 ,\mu_1 \mu_2, \cdots, \mu_{N-1} \right\}$$

제어(주문)의 순서의 비용함수를 최소화 하는게 아니라

$$\left\{u_0, u_1, u_2 \cdots u_{N-1} \right\}$$

-> 왜? 학습을 하는 이유는 어떻게 해왔는지(제어의 순서)를 익히는게 아니라 어떤 상황에서 어떻게 할 지(규칙의 순서, 정책)를 익히는 것이다.

마치 밥 때가 되어서 밥을 먹는 것이 아니라 원래는 배가 고파서 밥을 먹는 것이다. 물론 교육을 통해 제 때에 먹도록 권유하긴 하지만 바쁘면 다른 때에 먹는 것 처럼 말이다.

 

일반적인 유한-지평선 문제

시스템$x_{k+1}$ System	$x_{k+1} = f_k ( x_k , u_k , w_k ), \hspace{10mm} k=0, \cdots, N-1$
제어 구속 $u_k$ Control constraints	$u_k \in U_k (x_k ) $
확률 분포 $P_k$ Probability distribution	$P_k (\cdot | x_k , u_k ) \hspace{5mm} \text{of} \hspace{5mm} w_k $
정책 $\pi$ Policies	$\pi = \left\{\mu_0 ,\mu _1 \cdots \mu_{N-1} \right\}$ $\mu_k$는 상태 $x_k$에 대해 제어 $u_k=\mu_k (x_k)$로 사상한다. $\mu_k (x_k) \in U_k (x_k), \forall x_k $
기대 비용 $J_\pi$ Expected cost	$J_\pi =E\left\{g_N (x_N) + \sum_{k=0}^{N-1} g_k (x_k, \mu_k (x_k), w_k ) \right\}$
최적 비용 함수 $J^{*}_\pi$ Optimal cost function	$J^{*}(x_0) = \underset{\pi} {\text{min}}J_\pi (x_0)$ $J_{\pi^*}(x_0) = J^* (x_0)$ 를 만족한다.

동적 계획법으로 풀면 $\pi^*$은 $x_0$와 독립이다.

 

최적화 원리 Principle of Optimality

최적의 정책 $\pi^* = \left\{\mu_0^* , \mu_1^* ,\cdots, \mu^*_{N-1} \right\}$이 있다고 하자. 시간 $k$의 $x_k$가 있고, 시간 $k$에서 시간 $N$ 가는 "진행 비용 cost-to-go"를 최소화하길 희망하는 꼬리 소문제 tail subproblem와

$$E\left\{ g_N (x_N ) + \sum_{l=k}^{N-1} g_l (x_l , \mu_l(x_l) , w_l ) \right\}$$

그리고 꼬리 정책 tail policy $\left\{ \mu_k^* , \mu_{k+1}^* ,\cdots , \mu_{N-1}^* \right\}$을 상정해보자.

최적화 원리 Principle of Optimality : 꼬리 정책은 꼬리 소문제에 대해 최적이다. (미래의 최적은 과거에 했던 것에 달려있지 않다)

동적 계획법은 모든 꼬리 소문제를 푸는 것이다.

모든 스텝에서 주어진 시간 길이의 모든 꼬리 소문제를 더 짧은 시간 길이의 꼬리 소문제의 해법으로 푼다.

나의 요약 큰 문제에 대해 각 시간 단계마다 작은 문제로 쪼갰을 때, 최적의 선택이 있다고 하자. 이를 최적화 원리라고 하고, 동적 계획법은 최적화 원리를 바탕으로 작은 문제를 푸는 규칙들을 모은다. 모두 다 풀어서 모으면 최적화 정책이 된다. 해법은 시간 단계보다 작은 시간 내에 해를 구할 수 있어야한다.

동적 계획법의 알고리즘

동적 계획법의 알고리즘은 다음과 같다.
1. 모든 시간 ${}^{\forall} k$의 상태 $x_k$를 계산하고
2. 초기 조건이 주어지면 $J_N (x_N ) = g_N (x_N )$
3. 후진으로 시간 스텝 $k+1$의 최적화를 진행하여 최적 규칙 $\mu_k$을 구한다.
$$J_k (x_k ) = \underset{u_k \in U_k (x_k ) , w_k } {\text{min}} E\left\{g_k (x_k ,u_k ,w_k ) + J_{k+1} (f_k (x_k ,u_k ,w_k ))\right\}, \hspace{10mm} k=N-1, \cdots , 0$$

4. 마지막 스텝 $k=0$의 기대 비용 $J_0 (x_0)$을 구했다면 계산한 정책 $\pi^* = \left\{\mu_0^* , \cdots , \mu_{N-1}^* \right\}$는 최적이다. 규칙 $\mu_k^* (x_k )$은 시간 $k$의 상태 $x_k$에서의 기대 비용을 최소화한다.

 

 

동적 계획법의 실제 난점

 동적 계획법을 적용하기에 어려운 점들은 차원의 저주 curse of dimensionality와 모델링의 저주 curse of modeling가 있고 그리고 실시간 해법의 제약이 있을 수 있다.

 차원의 저주란 상태 변수와 제어 변수가 증가함에 따라서 필요한 연산량 및 메모리가 기하급수적으로 증가한다는 것이다. 또한 조합 문제에서는 상태의 개수가 폭발적으로 증가한다.

 모델링의 저주란 가끔씩은 시스템의 시뮬레이터가 모델보다 구축하기가 쉽다는 점이다.

 실시간 해법의 제약이 있을 수도 있는데, 일련의 문제들은 해결될 수도 있다. 이는 해결해야하는 문제의 데이터가 예고 없이 주어진다는 것이다. 또한 시스템이 제어될 때, 문제 데이터가 변할 수도 있어서 이때는 실시간으로 재계획을 해야할 필요가 있다.

 위의 문제들은 근사와 시뮬레이션의 동기가 된다.

주요 아이디어 : 비용의 근사  최적 진행비용 $J_{k+1}$을 근삿값 $\tilde{J}_{k+1}$으로 대체한 동적 계획법 방정식이 계산한 정책을 사용한다. 아래의 식을 최소화하는 규칙 $\bar{\mu_k}(x_k )$ 을 구한다. $$\underset{u_k \in U_k (x_k ) , w_k } {\text{min}} E\left\{g_k (x_k ,u_k ,w_k ) + \tilde{J}_{k+1} (f_k (x_k ,u_k ,w_k ))\right\}$$ 이에 다음과 같은 접근 방법이 있다.  - 문제의 근사 $\tilde{f}_k$ : 관련이 있지만 더 간단한 문제의 $\tilde{J}_k$를 사용한다.  - 매개변수화된 진행비용의 근사 $\tilde{J}_k$ : 적절한 매개변수 형태의 함수로써 $\tilde{J}_k$를 사용한다. 매개변수는 경험적이거나 시스템적인 전략으로 조정한다. (이 강의는 여기에 초점을 둔다)  - Rollout 접근 : 준 최적 정책의 비용으로써 $\tilde{J}_k$를 이용한다. 이는 해석적이거나 시뮬레이션에 의해 계산된다. (Rollout이 단어만 듣고는 이해가 안가는데, 간단히 정리하면 시뮬레이션이나 해석적으로 풀어낸 정책을 채택한다는 이야기이다. 강화학습 첫걸음[1]이라는 책의 표현을 참고하면 다음과 같다. "이러한 축적된 연속적인 경험을 롤아웃 Rollout 또는 경험 자취 Experience trace라고 합니다" ) Rollout 알고리즘  각각의 시간 $k$의 상태 $x_k$에서 다음을 최소화하는 제어 $\bar{\mu}_k (x_k ) $를 사용한다. $$\underset{u_k \in U_k (x_k ) , w_k } {\text{min}} E\left\{g_k (x_k ,u_k ,w_k ) + \tilde{J}_{k+1} (f_k (x_k ,u_k ,w_k ))\right\}$$ $\tilde{J}_{k+1} $는 경험적 전략 heuristic policy의 진행 비용이다. (기저 정책 base policy 라고 부른다)  Rollout 알고리즘은 비용 향상의 성질을 가지고 있다. Rollout 알고리즘은 같은 상태에서 출발한 기저 정책보다 최악인 비용을 달성하지 않는다. 그리고 대부분은 더 낫다.  Rollout 알고리즘은 중대한 난점이 있다. 기저 정책의 진행비용을 해석적으로 계산할 수 없다면, $\tilde{J}_{k+1}(x)$를 계산하기가 빡셀 수도 있다.  - 문제가 확률적이라면, 몬테 카를로 시뮬레이션을 포함할 수도 있고  - 결정론적 경우는 상황이 낫다 (주요 적용 분야는 이산 최적화 분야이다)  - 모델 예측 제어 (MPC, Model Predictive Control)과 연결된다.

 

무한-지평면 문제 Infinite-Horizon Problem

기본 문제와 같지만, "상태의 개수가 무한"하며 "시스템이 정적 stationary"이다.

1) 총 비용 문제는 다음을 최소화한다.

$$J_\pi (x_0) = \underset{N \rightarrow \infty} {\text{lim}} \underset{k=0,1,\cdots}{\underset{w_k}{E}} \left\{ \sum_{k=0}^{N-1} \alpha^k g(x_k, \mu_k (x_k) , w_k ) \right\}$$

 1.1) 할인율 문제 ($\alpha < 1$, $g$는 유계 bounded)

 1.2) 확률론적 최단 거리 문제 ($\alpha = 1$, 종말 상태를 포함하는 유한-상태 문제)

 1.3) 단계당 무계 비용 unbounded cost 를 가지는 할인, 비할인 문제 (여기서 다루진 않는다)

2) 평균 비용 문제 (다루지 않음)

무한 지평의 특성은 다음과 같다.

 - 도전적인 분석, 고상한 해법과 알고리즘

 - 정적 정책 $\pi = \left\{ \mu,\mu,\cdots \right\}$과 동적 계획법의 정적 형태는 특별한 역할을 한다.

 

1.3) 할인율 문제/ 유계 비용

 정적 시스템 $x_{k+1} = f(x_k , u_k , w_k )$ 에 대해서

 정책 $\pi = \left\{ \mu_0 ,\mu_1 ,\cdots \right\}$의 비용은 다음과 같다.

$$J_\pi (x_0) = \underset{N \rightarrow \infty} {\text{lim}} \underset{k=0,1,\cdots}{\underset{w_k}{E}} \left\{ \sum_{k=0}^{N-1} \alpha^k g(x_k, \mu_k (x_k) , w_k ) \right\}$$

 $\alpha <1$이며, $g$는 유계이다. (어떤 $M$에 대해, $|g(x,u,w)| \leq M, \forall(x,u,w)$)

 최적 비용 함수는 $J^* (x) = \underset{\pi}{\text{min}} J_\pi (x)$ 으로 정의된다.

 이때 $g$의 유계는 모든 비용이 잘 정의되며 유계임을 보장한다. $|J_\pi (x) | \leq \frac{M}{1-\alpha}$

 이는 각 단계 당 비용 크기에 제한이 있어야 총 비용함수 크기도 제한이 있다는 이야기이다.

비용 함수 $J_\pi (x)$와 유계 조건 $|g(x,u,w)| \leq M, \forall(x,u,w)$으로부터 증명할 수 있다. 

$$ \left| J_\pi (x) \right| = \underset{N \rightarrow \infty}{\text{lim}} \left| \underset{k=0,1,\cdots}{\underset{w_k}{E}} \left\{ \sum_{k=0}^{N-1} \alpha^k g_k \right\} \right|$$

$$\leq \underset{N \rightarrow \infty}{\text{lim}}    \sum_{k=0}^{N-1} \alpha^k \left| g_k \right|\leftarrow |g(x,u,w)| \leq M$$

$$\leq \underset{N \rightarrow \infty}{\text{lim}}  \sum_{k=0}^{N-1} \alpha^k M \leq \underset{N \rightarrow \infty}{\text{lim}} M\frac{1-\alpha^N}{1-\alpha} = \frac{M}{1-\alpha}$$

$$ \therefore ) \left| J_\pi (x) \right| \leq \frac{M}{1-\alpha}$$

 모든 공간이 임의적이므로, 오직 $g$의 유계만이 중요하다.

 중요한 특수 경우는 놓인 모든 공간이 유한한 경우이다. (MDP, Markov Decision Problem)

모든 알고리즘은 궁극적으로 원래 문제를 근사한 유한 공간 MDP 같이 동작한다.

 

 동적 계획법 사상을 위한 축약어 표기법

  $x$에 대한 어떤 함수에 대해 다음과 같이 나타낸다.
$$(TJ)(x) = \underset{u \in U (x) }{\text{min}} \underset{w}{E} \left\{ g(x,u,w) + \alpha J (f(x,u,w)) \right\} \hspace{5mm} {}^{\forall} x$$
 $TJ$는 단계 비용 $g$와 종말 비용함수 $\alpha J$를 가지는 한 단계 문제에 대한 최적 비용 함수이다.
 $T$는 $x$에 대한 유계 함수를 연산하여 $x$에 대한 다른 유계 함수를 만든다.
 어떤 정적 정책 $\mu$에 대해 다음과 같이 나타낸다.
$$(T_\mu J ) (x) = \underset{w}{E} \left\{ g(x, \mu(x), w) + \alpha J(f(x,\mu(x),w))\right\} ,\forall x$$
 문제의 핵심 구조는 $T$와 $T_\mu$에서 얻어진다. 또한 할인율 문제의 전체 이론은 $T$와 $T_\mu$를 이용하여 빠르게 전개될 수 있다. $T$와 $T_\mu$는 동적 계획법에서 강력한 통합 프레임워크를 이룬다. 이는 책 "Abstract Dynamic Programming"의 핵심이다.

 

유한-지평면 비용의 표현 Finite-Horizon Cost Expression

  종말 비용이 $J$이고 $N$ 단계의 정책 $\pi_0^N=\left\{\mu_0 ,\mu_1, \mu_2, \cdots ,\mu_{N-1} \right\}$을 상정해보자. ($\pi_1^N=\left\{\mu_1, \mu_2, \cdots ,\mu_{N-1} \right\}$)

$$J_{\pi_0^N} (x_0) = E\left\{ \alpha^N J(x_k) + \sum_{l=0}^{N-1} \alpha^l g(x_l ,\mu_l (x_l ) , w_l )\right\}$$

$$E\left\{ g(x_0, \mu_0 (x_0) , w_0 ) + \alpha J_{\pi_1^N} (x_1)\right\} = (T_{\mu_0} J_{\pi_1^N }) (x_0) $$

$$J_{\pi_0^N} = (T_{\mu_0} T_{\mu_1} \cdots T_{\mu_{N-1}} J) (x) , \hspace{5mm} \forall x$$

 정적 정책 $\mu$에 대해 $N$ 단계의 비용함수는 다음과 같다.

$$J_{\pi_0^N} = T_\pi^N J$$

$T_\pi^N$는 $T_\mu$ N번째 구성이다. 비슷하게 최적의 N단계 비용함수는 $T^N J $이며 이는 $T^N J = T(T^{N-1} J)$의 동적 계획법 알고리즘을 따른다.

 

축약한 이론의 요약

 무한 지평면 비용 함수 표현은 다음과 같다. ($J_0 (x) \equiv 0$)

$$J_\pi (x)= \underset{N\rightarrow \infty}{\text{lim}} \left( T_{\mu_0} T_{\mu_1} \cdots T_{\mu_N} J_0 \right) (x) , \hspace{5mm} J_\pi (x) = \underset{N \rightarrow \infty} {\text{lim}} ( T_\pi^N J_0 ) (x) $$

 벨만 방정식 Bellman's equation

$$J^* = TJ^* ,\hspace{5mm} J_\mu = T_\mu J_\mu$$

 최적화 조건 Optimality condition

$$\mu : \text{optimal} \leftrightarrow T_\mu J^* = TJ^*$$

 Value iteration : 유계의 어떤 $J$에 대해

$$J^* (x) = \underset{k \rightarrow \infty} {\text{lim}} (T^k J) (x) , \hspace{5mm} \forall x $$

 Policy iteration : 주어진 $\mu^k$

    Policy evalution : $J_{\mu^k} = T_{\mu^k} J_{\mu^k}$ 를 만족하는 $J_{\mu^k}$

    Policy improvement : $T_{\mu^{k+1}} J_{\mu^k} = T J_{\mu^k}$를 인 $\mu^{k+1}$

 

두 가지 핵심 성질

 단조 성질 Monotonicity property

어떤 $\mu$와 모든 $x$에 대해 $J(x) \leq J'(x)$인 어떤 $J$, $J'$는 다음과 같다.

$$(TJ)(x) \leq (TJ' ) (x), \hspace{5mm} \forall x$$

$$(T_\mu J)(x) \leq (T_\mu J' ) (x), \hspace{5mm} \forall x$$

 일정한 이동 성질 Constant Shift property

 어떤 스칼라 $r$, 어떤 $J$, $\mu$에 대해

$$(T(J+re))(x) =(TJ) (x) +\alpha r ,\hspace{5mm} \forall x$$

$$(T_\mu (J+re))(x) =(T_\mu J) (x) +\alpha r ,\hspace{5mm} \forall x$$

$e$는 단위 함수이다. $e(x) \equiv 1$

단조 성질은 모든 동적 계획법 모델에서 나타나며 일정 이동 성질은 할인 모델의 특수한 성질이다.

할인율 문제는 또다른 중요한 속성이 있는데 $T$와 $T_\mu$가 단축 사상 Contraction mapping 이라는 것이다.

 Value Iteration의 수렴성과 증명

 유계의 모든 $J$에 대해,

$$J^* (x) = \underset{k\rightarrow \infty}{\text{lim}} (T^k J ) (x) , \hspace{5mm} \forall x$$

Value Iteration의 수렴성 증명

문제를 간단히 하고자 $J\equiv 0$라고 하면, 어떤 초기 상태 $x_0$와 정책 $\pi=\left\{ \mu_0, \mu_1 \cdots \right\} $ 에 대해 $$J_\pi (x_0) =E \left\{ \sum_{l=0}^{\infty} \alpha^l g(x_l ,\mu_l (x_l), w_l ) \right\}$$ $$= E \left\{\sum_{l=0}^{k-1} \alpha^l g(x_l ,\mu_l (x_l ) , w_l ) \right\} +E \left\{\sum_{l=k}^{\infty} \alpha^l g(x_l ,\mu_l (x_l ) , w_l ) \right\}$$ 꼬리부분은 $\left| g(x,u,w) \right| \leq M$인 $M$에 대해 다음과 같음을 증명하였다. $$ \left | E \left\{\sum_{l=k}^{\infty} \alpha^l g(x_l ,\mu_l (x_l ) , w_l ) \right\} \right| \leq M \frac{\alpha^k}{1-\alpha }$$

다른 증명 방법 $$||T^{k+1}J-J^*||_\infty=|| T(T^k J)-TJ^* ||_\infty \leq \alpha ||T^k J - J^* ||_\infty \leq$$ $$\cdots \leq \alpha^{k+1} ||J-J^*||_\infty \rightarrow \infty$$ 극한을 취하면 최적의 비용함수 값은 초기 비용함수 값와 같다.

Bellman's equation

최적 비용 함수 $J^*$는 벨만 방정식 $J^* =TJ^*$의 해이다.

$$J^* (x) = \underset{u\in U( x) }{\text{min}} \underset{w}{E} \left\{g(x,u,w) + \alpha J^* (f(x,u,w))\right\}$$

증명 Value Iteration의 증명의 과정에서 시작한다. $$\left|J_\pi (x) - E \left\{\sum_{l=k}^{\infty} \right\} \right| \leq \frac{\alpha^k M}{1-\alpha}$$ $$J^* (x) - \frac{\alpha^k M}{1-\alpha} \leq (T^k J_0 )(x) \leq J^* (x) + \frac{\alpha^* M }{1-\alpha}$$ 한 단계를 이동시키고 단조 성질과 일정한 이동을 이용하면, $$TJ^* (x) - \frac{\alpha^{k+1} M}{1-\alpha} \leq (T^{k+1} J_0 )(x) \leq TJ^* (x) + \frac{\alpha^{k+1} M }{1-\alpha}$$ 양 변에 $k$에 대한 극한을 취하면 $|g(x,u,w) \leq M|$임으로부터 꼬리부분이 다음을 만족함을 증명했다. $$\underset{k\rightarrow \infty}{\text{lim}}(T^{k+1} J_0 ) (x) = J^* (x) $$ 그리고 양변에 정책 $\pi$에 대한 min을 취하고, $k\rightarrow \infty$의 극한을 취하면 증명이 된다.

Contraction Property

 어떤 유계의 $J$, $J'$, $\mu$에 대해서

$$\underset{x}{\text{max}} |(TJ) (x) - (TJ')(x) | \leq \alpha \underset{x}{\text{max}}|J (x) -J'(x) |$$
$$\underset{x}{\text{max}} |(T_\mu J) (x) - (T_\mu J')(x) | \leq \alpha \underset{x}{\text{max}}|J (x) -J'(x) |$$

여기서 $J^*$는 $J^* = TJ^*$는 유일 해이며 $J_\mu$는 $J_\mu = T_\mu J_\mu$의 유일 해 이다.

증명 $c=\underset{x \in S}{\text{max}} |J(x) - J' (x) |$라 하면, $J(x) - c \leq J' (x) \leq J(x) + c \hspace{5mm} {}^{\forall}$ 양 변에 $T$를 취하면, 단조 성질과 일정 이동 성질을 사용하자. $$(TJ)(x) -\alpha c \leq (TJ') (x) \leq (TJ) (x) + \alpha c \hspace{5mm} {}^{\forall}$$ $$\therefore) \hspace{5mm} | (TJ) (x) - (TJ') (x) | \leq \alpha c \hspace{5mm} {}^{\forall}$$

최적 조건의 필요충분조건

어떤 정책 $\mu$이 최적이라 함은 $\mu$가 각 상태 $x$에 대해 벨만 방정식에서 $\mu(x)$이 minimum을 가질 때이다.

$$TJ^* = T_\mu J^*$$

이는 모든 $x$에 대해 다음과 등가하다.
$$\mu (x) \in \underset{u \in U(x)}{\text{argmin}} \underset{w}{E} \left\{ g(x,u,w) + \alpha J^* (f(x,u,w))\right\}$$

증명 $$TJ^* = T_\mu J^* \rightarrow \mu \text{ is optimal}$$ 만약 $TJ^* = T_\mu J^*$이라 하면, 벨만 방정식 ($J^* = TJ^*$)을 이용하면 $$J^* = T_\mu J^* $$ $T_\mu$의 고정된 점에서의 유일성으로부터, $J^* = J_\mu$라는, $\mu$가 최적임을 얻는다. $$\mu \text{ is optimal} \rightarrow TJ^* = T_\mu J^*$$ 만약 정적 정책 $\mu$가 최적이라면, $J^* = J_\mu$이다. 따라서 $$J^* = T_\mu J^*$$

 

참고문헌

[1] Juliani, A., 강화학습 첫걸음, 한빛미디어, 2017, pp.39.