Dimitri의 2014 ADP - Lec.2

본 글은 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

 

 

전 강의의 요약

요약 할인율 문제/유계 비용  어떤 상태공간으로 표현된 정적 시스템에 대해서 정책 $\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\{ \right\}$$  $\alpha < 1 $이며 $|g^{\forall}(x,u,w)|\leq M$으로 단계 비용 stage cost $g$는 유계이다. 동적계획법의 사상을 위한 축약 표기 $$(TJ) (x) = $$ 정적 정책 $\mu$에 대해서, 축약한 이론의 요약 - Bellman's equation $$J^* = TJ^* ,\hspace{10mm} J_\mu = T_\mu J_\mu $$ $$J^* (x) = \underset{u \in U(x) } {\text{min}} \underset{w}{E} \left\{ g(x,u,w) + \alpha J^* ( f(x,u,w)) \right\}, \forall x $$ $$ J_\mu (x) = \underset{w} {E }\left\{ g(x,\mu(x),w) + \alpha J_\mu (f(x,\mu(x), w) ) \right\}, \forall x $$ - Optimality condition $$\mu : \text{optimal} \leftrightarrow T_\mu J^* = TJ^*$$ $$u\in \text{arg} \underset{u\in U(x) } {\text{min}} \underset{w}{E} \left\{ g(x,u,w) + \alpha J^* (f(x,u,w))\right\}, \forall x $$ - Value iteration : 유계의 어떤 $J$에 대해 $$J^*(x) = \underset{k\rightarrow \infty}{\text{lim}} (T^k J ) (x) , \hspace{5mm} \forall x$$ - Policy iteration : 주어진 $\mu^k$에 대해     Policy evaluation $J_{\mu^k} = T_{\mu^k} J_{\mu^k}$ 인 $J_{\mu^k}$를 찾는다.     Policy improvement $T_{\mu^{k+1}} J_{\mu^K} = TJ_{\mu^k}$인 $\mu^{k+1}$를 찾는다.   주요 성질  - Monotonicity property $$(TJ)(x) \leq (TJ')(x)$$ $$(T_\mu J) (x) \leq (T_\mu J') (x) , \hspace{3mm} {}^{\forall}x\in X$$  - Contraction property $$\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) |$$  - Compact Contraction Notatin $$||TJ-TJ'|| \leq \alpha ||J-J'|| $$ $$|| T_\mu J - T_\mu J' || \leq \alpha ||J-J'||$$ 어떤 유계의 $J$에 대해서, $||J||$ sup-norm을 나타내면 $$||J|| = \underset{x}{\text{max}}|J(x)|$$

강의 2의 목차

 - 할인율 문제 이론의 리뷰

 - 축약 표기의 리뷰

 - 할인율 DP를 위한 알고리즘

 - 가치 반복 Value Iteration

 - 정책 반복 Policy Iteration의 다양한 형태

 - 최적 정책 반복

 - Q-factor와 Q-learning

 - 다른 DP 모델 - 연속 공간/시간

 - DP의 추상적인 관점

 - 비동기 알고리즘

 

두 가지 주 알고리즘 : V.I.와 P.I.

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

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

 - Policy Iteration : 주어진 $\mu^k$에 대해 

    Policy Evalution : $J_{\mu^k} = T_{\mu^k} J_{\mu^k}$을 풀어서 $J_{\mu^k}$을 구한다.

$$J_{\mu^k} (x) = \underset{w}{E} \left\{ g(x,mu^k ( x) ,w) + \alpha J_{\mu^k} (f(x,\mu^k (x),w) ) \right\}, \forall x $$

    Policy Improvement : $T_{\mu^{k+1}} J_{\mu^k} = T J_{\mu^k}$를 만족하는 $\mu^{k+1}$을 구한다.

$$\mu^{k+1} (x) \in \text{arg} \underset{u\in U(x) } {\text{min}} \underset{w}{E}\left\{g(x,u,w) + \alpha J_{\mu^k} (f(x,u,w)) \right\} ,\forall x $$

 

$n$ 개의 상태에 대해서 policy evaluation은 $n \times n$의 선형 시스템 $J_\mu = g_\mu + \alpha P_\mu J_\mu $을 푸는 것과 같다. 이로 인해 $n$이 크다면, 정확한 P.I.는 구할 수가 없다.

 

P.I.의 타당성

 $J_{\mu^k} \geq J_{\mu^{k+1}}\hspace{5mm} \forall k$

증명 

$$J_{\mu^k} \geq T_{\mu^{k+1}} J_{\mu^k} \geq T_{\mu^{k+1}}^2 J_{\mu^k} \geq \cdots \geq \underset{N\rightarrow \infty}{\text{lim}} T_{\mu^{k+1}}^N J_{\mu^k} = J_{\mu^{k+1}}$$

$$\therefore) J_{\mu^k} \geq J_{\mu^{k+1}}$$

반복 $k$에서 알고리즘이 엄격히 향상된 정책을 만들던지 최적의 정책을 찾는다. 그래서 유한 공간 MDP는 최적 정책에서 종료되고 무한 공간 MDP는 무한히 수렴하게 된다.

Optimistic Policy Iteration

 최적의 PI는 유한한 가치 반복(VI)과 근사하게 정책 평가가 진행된다. 그래서 정책 평가는 다음과 같이 근사할 수 있다.

$$J_\mu \approx T_{\mu}^{m} J ,\hspace{5mm} m\in [1,\infty)$$

 Shorthand definition으로부터, 

$$T_{\mu^k} J_k = T J_k, \hspace{5mm} J_{k+1} =T{\mu^k}^{m_k} J_k , \hspace{5mm} k=0,1,\cdots$$

 $m_k \equiv 1$라면 VI 이며

 $m_k = \infty $라면 PI이가 된다.

반대 아닌가???

 이는 유한과 무한 공간의 할인율 문제에 수렴하는 특성을 보이며, 큰 문제들에 대해서 VI와 PI보다 일반적으로는 빠르게 동작한다.

Approximate Policy Iteration

 정책 평가 policy evaluation의 근사가 가능하다면

$$|| J_k -J_{\mu^k} || \leq \delta , \hspace{5mm} k=0,1,\cdots$$

 정책 향상 policy improvement도 근사한다.

$$|| T_{\mu^{k+1}} J_k - TJ _k || \leq \epsilon, \hspace{5mm} k=0,1,\cdots $$

여기서 $\delta , \epsilon$은 양의 스칼라이다.

 오차의 유계 I : 근사적 정책 반복에 의해 만들어진 $\{ \mu^k \}$는 다음을 만족한다.

$$\underset{k\rightarrow \infty} {\text{limsup}} || J_{\mu^k} -J^* || \leq \frac{\epsilon + 2 \alpha \delta }{\left(1-\alpha \right)^2}$$

 이 방법은 지속하여 한 점으로 나아가며, 반복 $J_{\mu^k}$는 $J^*$의 이웃 내에서 진동한다.

 오차의 유계 II : $\{ \mu^k \}$는 계속해서 $\bar{\mu}$을 생성하며 $\bar{\mu}$에서 종료된다.

 $$|| J_{\bar{\mu}} -J^* || \leq \frac{\epsilon + 2 \alpha \delta }{1-\alpha }$$

 

Q-factor

 $(x,u)$의 최적 Q-factor는 다음과 같다.

$$Q^* (x,u) = E\left\{g(x,u,w) + \alpha ^* (\bar{x})\right\} $$

 이는 $x$에서 시작하여, 1번째 단계에 $u$를 적용하고, 1번째 단계 이후의 최적의 정책에 대한 비용이다.

 벨만 방정식은 아래와 같이 쓸 수 있는데

$$J^* (x) = \underset{u\in U(x) } {\text{min}} Q^*(x,u), \hspace{5mm} \forall x $$

VI 또한 등가하게 쓸 수 있다.

$$J_{k+1} (x) = \underset{u\in U(x) } {\text{min}} Q_{k+1} (x,u) \hspace{5mm} \forall x$$

 Q factor는 상태가 $(x,u)$ 인 다음의 문제에 대한 비용이다. 이는 벨만 방정식을 만족한다.
$$(FQ)(x,u) = \text{E} \left\{ g(x,u,w) + \alpha \underset{u \in U(\bar{x}) } {\text{min}} Q(\bar{x} , v) \right\}$$

Q-factor의 VI, PI는 수학적으로 비용의 VI, PI와 같다.

최적의 Q-factor를 가지는 것은 다음과 같이 최적 정책을 실시간으로 계산할 때 편리하다.

$$\mu^* = \underset{u\in U(x) } {\text{min}} Q^*( x,u) $$

한 번 $Q^* (x,u)$를 안다면 $g$와 $E\left\{\cdot\right\}$과 같은 모델은 필요치않다. (Model-free operation)

Q-Learning은 샘플링 방법으로, 시스템의 시뮬레이터를 이용하여 $Q^* (x,u)$를 계산하기 때문에 모델이 필요하지 않다.

 

다른 DP 모델

 앞서 해석하기가 매우 간단하고 결과가 가장 명확한 할인율 문제 discounted models 에 대해 다루었다. 다른 DP 문제는 다음을 고려해볼 수 있다.

 - 비할인율 문제 ($\alpha =1$) : 이는 확률적 최단 경로 문제와 같은 특이한 종말 문제를 포함할 수 있다.

 - 연속-시간, 유한-상태 MDP : 전이 간의 시간이 무작위적이고 상태-제어 종속적이다. 이는 일반적으로 준-마르코프 MDP Semi-Markov MDP라 불리는 Queueing System에 속한다. 이러한 문제는 상태-제어가 종속적인 할인율 계수를 가지는 할인율 문제로 볼 수 있다.

 - 연속-시간, 연속-공간 모델 : 고전 자동 제어, 공정 제어, 로봇 공학 문제이다.

    이산-시간 모델과 상당한 차이가 있다.

    수학적으로 더 복잡한 이론이다. (특히 확률적 문제에 대해서)

    결정론적 버전은 고전 최적 제어 이론으로 해석할 수 있다.

    시간 이산화에 기반하여 DP의 해법을 적용할 수 있다.

 

연속-시간 모델의 동적 계획법

시스템 방정식	$dx(t)/dt = f(x(t), u(t))$
비용 함수	$int_{0}^{\infty} g(x(t) ,u(t))$
$x$에서 시작한 최적 비용	$J^* (x)$
$\delta$ 시간 이산화	$x_{k+1} = x_k +\delta \cdot f(x_k , u_k )$

$\delta$ 시간 이산화에 대한 벨만 방정식은 다음과 같다.

$$J_{\delta}^* = \underset{u}{\text{min}} \left\{\delta \cdot g(x,u) + J_\delta^* (x+\delta \cdot f(x,u))\right\}$$

$\delta \rightarrow 0$을 취하면, Hamilton-Jacobi-Bellman 방정식을 얻을 수 있다. ($\text{lim}_{\delta\rightarrow 0} J_\delta^* (x) = J^* (x) $라고 가정하면)

$$0=\text{min}_u \left\{g(x,u) + \color{red}{\nabla J^* (x) '} f(x,u) \right \} ,\hspace{5mm} \forall x $$

Policy Iteration

- Policy Evalution : 현재 $\mu$에 대해 다음을 푼다.

$$0=g(x,\mu(x)) + \nabla J_\mu (x) ' f(x,\mu(x)) , \hspace{5mm} \forall x$$

- Policy Improment : 

$$\bar{\mu}(x) \in \underset{u}{\text{argmin}} \left\{ g(x,u) + \color{red}{\nabla J_\mu (x)'} f(x,u) \right\}, \hspace{5mm} \forall x$$

 

동적 계획법에 대한 더 일반적인/추상적인 관점

 $Y$를 norm이 있는 실 벡터 공간이라고 하고, $\rho \in (0,1)$이라 할 때, 함수 $F : Y\rightarrow Y$를 contraction mapping이라 부르자. $\rho$는 함수 $F$의 modulus of contraction이라 부른다.

$$|| Fy - Fz || \leq \rho || y - z|| , \hspace{5mm} \forall y,x \in Y$$

중요 예제

 $X$를 집합으로, $v : X \rightarrow \mathcal{R}$ 를 양수 함수라 하자. 그리고 $B(X)$를 $x$로 $J(x)/v(x)$가 유계가 되는 모든 함수 $J: X \rightarrow \mathcal{R}$의 집합이라고 하자. 이때 $B(X)$의 norm을 정의하며 weighted sup-norm이라고 부른다.

$$||J|| = \underset{x \in X} {\text{min}} \frac{|J(x)|}{v(x)}$$

중요한 특별 케이스는 $T$, $T_\mu$을 사상하는 할인율 문제이다. ($v(x) \equiv 1 , \rho=\alpha$)

 

Contraction Mapping 의 예제

 

 

비동기 알고리즘 Asynchronous Algorithms

사용 동기

 - 빠른 수렴

 - 병렬/분산 연산

 - 시뮬레이션 기반 시행

General Framework

공집합이 아닌 부분집합 $X_1 , \cdots X_m $에서 분리한 분할 $X$과 $J(x)$를 갱신하는 나뉜 연산기 $l$를 사용한다.

$J$가 다음과 같이 분할되었다고 하자.

$$J=(J_1, \cdots J_m ) $$

$J_l$은 집합 $X_l$의 비용함수 $J$의 구속이다.

- Synchronous VI algorithm

$$J_{l}^{t+1}  (x) = T( J_1^t , \cdots , J_m^t ) (x) , \hspace{5mm} x\in X_l , l=1,\cdots,m$$

- Asynchronous VI algorithm

어떤 시간의 부분 집합 $\mathcal{R}_l $ 에 대해서

$$J_{l}^{t+1} = \cases{T (J_{1}^{\tau_{l1}(t)}, \cdots J_{m}^{\tau_{lm}(t)} )(x) \text{if} t\in \mathcal{R}_l \\ J_l^t (x) \text{,  if  } t \in \mathcal{l}}$$

여기서 $t-\tau{lj}(t)$는 통신 '지연'이다.

 

One-State-At-a-Time Iterations

특징적인 케이스 : $n$ 상태, 각 상태에 대한 분리된 연산기, 지연이 없다고 하자.

상태의 시퀸스 $$\left\{x^0 , x^1 ,\cdots \right\}$$를 생성한다, 어떤 방식이든 아마도 시뮬레이션으로 생성될 것이다. (각 상태는 종종 무한히 생성된다.)

- Asynchronous VI : 

$$J_{l}^{t+1} = \cases{T (J_{1}^{\tau_{l1}(t)}, \cdots J_{m}^{\tau_{lm}(t)} )(x) \text{if } l = x^t \\ J_l^t (x) \text{if } l \ne x^t}$$

$T(J_1^t ,\cdots , J_n^t ) (l)$는 벡터의 $l$번째 성분이다.

$$T(J_1^t ,\cdots , J_n^t )=TJ^t$$

특별한 경우는 다음과 같다. 이를 Gauss-Seidel method라 한다.

$$\left\{x^0 , x^1 ,\cdots \right\} = \left\{ 1, \cdots n ,1, \cdots , n , 1, \cdots \right\}$$

 

비동기 수렴 이론 Asynchronous Convergence Theorem 

핵심 명제 : VI와 PI는 변형이 있어도 비동기 시행에서 여전히 작동한다.

${}^{\forall} l,j=1,\cdots m$, $\mathcal{R}_l$이 무한하며, $\text{lim}_{t\rightarrow \infty} \tau_{lj} (t) = \infty$라고 가정하자.

명제 : $T$가 유일한 고정 점 $J^*$을 가진다고 하자. 그리고 공집합이 아닌 부분 집합 $\left\{S(k)\right\} \cup R(X) \text{ with } S(k+1) \cup S(k), {}^{\forall}k$의 시퀸스가 있다고 하자. 그리고 다음의 성질을 가진다고 하자.

(1) Synchronous Convergence Condition

 각 $k$에 대한 매 시퀸스 $\left\{J^k \right\} \text{ with } J^k \in S(k)$는 $J^*$로 수렴한다.

$$TJ \in S(k+1),\hspace{5mm} {}^{\forall} J\in S(k) , k=0,1,\cdots $$

(2) Box Condition

 $S({}^{\forall}k ) $는 곱집합의 형태이다.

$$S(k) = S_1 (k) \times \cdots \times S_m (k)$$

그러면 모든 $J\in S(0)$에 대해서, 비동기 알고리즘이 생성한 시퀸스 $\left\{ J^t \right\}$는 $J^*$ 방향으로 수렴한다.

 

 

Contraction Mapping 부분을 제외하고 끝.