Dimitri의 2014 ADP - Lec.3

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

 

 

강의 3의 목차

 - 할인된 동적 계획법의 복습

 - 근사적 동적 계획법의 소개

 - 근사 아키텍쳐

 - 시뮬레이션 기반 근사적 정책 반복

 - 근사적 정책 평가

 - 근사와 시뮬레이션에 대한 일반적인 이슈들

 

근사적 동적 계획법 Approximate DP, ADP

ADP로의 일반적 방향성

 80년대 말에서 지금까지 ADP는 동적 계획법의 응용영역이 상태의 수가 많거나 무한인 경우에 대한 문제로 확장되게 해준 획기적인 방법론이다. ADP는 다른 이름으로도 불리곤 했는데, 강화학습 Reinforcement learning RL, 신경-동적 계획법 Neuro-dynamic programming NDP, 적응적 동적 계획법 Adaptive dynamic programming ADP 등이다.

 위 강의에서는 n개의 상태의 할인율 문제에 주로 적용할 것이다. (가장 쉬운 경우인데, 매우 큰 n을 생각해보자)

다른 동적 계획법 모델(연속 공간, 연속 시간, 비할인)로 확장 될 수는 있으나 매우 변칙적이다. 이 부분은 추후를 위해 놔두자.

 접근 방법

 - 문제의 근사

 - 시뮬레이션 기반 접근법

 시뮬레이션 기반의 3가지 접근법

 - Rollout

 - 가치 공간의 근사

 - 정책 공간의 근사

 

왜 시뮬레이션을 사용해야할까?

 엄청난 양의 항을 포함하는 합과 기댓값 연산에서연산 복잡성의 이점이 있다.

 시뮬레이션은 시스템의 해석적 모델을 사용할 수 없으나 시뮬레이션/컴퓨터 모델은 가능할 때 편리하게 쓸 수 있다.

 

가치 공간과 정책 공간의 근사

가치 공간의 근사

$i$는 현재 상태이고 $r=\left( r_1, \cdots r_m \right)$가 "튜닝 가능한" 스칼라 가중치인 매개변수화된 클래스 $\tilde{J} (i;r)$로부터 $J^*$ 또는 $J_\mu$를 근사하고, 다양한 알고리즘과 연산에서 $J^*$ 또는 $J_\mu$의 위치에 $\tilde{J}$를 사용한다.

 $r$의 역할은 $r$을 조정함으로써 $\tilde{J}$의 형상을 바꾸고, $J^*$ 또는 $J_\mu$에 가깝게 하는 것이다.

두 가지 중요 이슈

 - 매개변수화 된 클래스 $\tilde{J}(i;r)$의 선택 (근사적 아키텍쳐)

 - 가중치를 튜닝하기 위한 기법 (아키텍쳐를 "훈련"시킴)

성공은 "이러한 이슈들이 어떻게 처리되는지, 문제에 대한 직관"에 크게 좌우된다.

시뮬레이터를 사용할 수도 있는데, 부분적으로 시스템의 수학적 모델은 없지만 컴퓨터 모델이 있는 경우이다.

위 강의에서는 시뮬레이션에 초점을 두지만, 이는 오직 가능성에만 두진 않는다.

또한 Q-factor나 비용함수 차분에 대해서 매개변수 근사화를 사용할 수 있다.

 

근사 아키텍쳐

 선형과 비선형으로 나뉘며

 선형 아키텍쳐는 학습시키기에 더 쉽지만 비선형 아키텍쳐는 학습시킬게 더 많다. (are richer)

 체스를 계산한다고 하자.

 - 보드의 위치를 상태로 상태로, 움직임을 명령으로 생각하자.

 - 각각의 위치/이동에 점수(또는 근사한 Q-factor)를 할당하는 특징 feature 기반 위치 평가를 사용한다.

 

선형 근사 아키텍쳐

 종종 특징 feature는 근사된 비용 함수에 수많은 비선형적 본질을 부호화 encode한다. 그렇다면 복잡한 아키텍쳐를 제외하고는 근사화는 꽤 정확할 수도 있다. 잘 골라진 특징을 가지고 선형 아키텍쳐를 사용할 수 있다.

$$\tilde{J}(i;r) = \phi (i)'r ,\hspace{5mm} i=1,\cdots ,n$$

$$\tilde{J}=\Phi r = \sum_{j=1}^s \Phi_j r_j$$

$\Phi$ 는 행이 $\phi(i)'$인 행렬이다.

아래는 부분공간의 근사이다.

$$S=\left\{ \Phi r  | r \in \mathcal{R}^s\right\}$$

이는 기저 함수인 $\Phi$열에 걸쳐있다.

특징 종류는 다양한 예를 들 수 있는데, 다항식이나 radial basis function(RBF) 등이 있다.

Ex) 다항식 타입

다항 근사 : 예를 들면 이차 근사 함수가 있다. 상태를 $i=\left(i_1 , \cdots ,i_q\right)$라 하고 다음을 정의한다.

$$\phi_0 (i) = 1 ,\phi_k (i) = i_k , \phi _km (i) = i_k i_m , \hspace{5mm} k,m=1,\cdots , q $$

선형 근사 아키텍쳐

$$\tilde{J}(i;r) = r_0 + \sum_{k=1}^q r_k i_k + \sum_{k=1}^q \sum_{m=k}^q r_{km} i_k i_m$$

$r$는 $r_0 , r_k , r_km$의 구성을 가진다.

보간 : 특수한/대표 상태들의 부분 집합 $I$을 선택하고, 매개변수 벡터 $r$는 상태 $i\in I$ 당 하나의 구성요소 $r_i$을 가진다. 근사 함수는 다음과 같다.

$$\tilde{J}(i;r) = r_i , \hspace{5mm} i\in I$$

$\tilde{J}(i;r)$는 $i\in I$에서의 값을 이용한 보간이다.

예를 들면 부분 상수 piecewise constant, 부분 선형 piecewise linear, 더 일반적인 다항식 보간 등이 있다.

 

도메인 특화된 예제 : 테트리스 게임

$J^*(i)$ 위치 $i$에서부터 시작한 최적의 점수

상태의 갯수는 보드 크기가 $10\times 20$이므로 $2^{200}@보다 많다.

성공에 22가지 특징점이 있고, 이는 보드 위치의 중요한 양상(줄 높이 같은거)을 획득함으로써 즉각 테트리스 플레이어에게 인지된다.

 

정책 반복의 근사 - $J_\mu$ 또는 $Q_\mu$의 근사

현재 정책 $\mu$의 비용 $J_\mu$를 근사하기 위해 시뮬레이션을 사용한다.

위 과정을 통해서 (근사화된) 벨만 방정식을 최소화하는 방법으로 향상된 정책 $\bar{\mu}$를 만든다.

다른 방법으로는 $\mu$의 Q-factor를 근사하는 것도 있다.

그렇다면 정책 반복의 과정은 다음과 같다.

 1 - 초기 정책을 정의한다.

 2 - (근사적 정책 평가)근사적 비용 $\tilde{J}_\mu (i,r)$ 또는 근사적 Q-factor $\tilde{Q}_\mu (i,u,r)$을 평가한다.

 3 - (정책 향상) 향상된 정책 $\bar{\mu}$를 만든다.
$$\bar{\mu}(i) = \text{argmin}_{u\in U(i)} \tilde{Q}_\mu (i,u,r)$$

과정 2~3을 반복한다.

 

최적 비용 함수 $J^*$ 또는 Q-factor $Q^*$의 근사

 - Q-학습 : Q-factor를 근사하기 위해 시뮬레이션을 사용한다.

$$Q^*(i,u) = g(i,u) + \alpha \sum_{j=1}^{n} p_{ij}(u) J^* (j)$$

최적 비용은 다음과 같다.

$$J^* (i) = \underset{min}{u \in U(i)} Q^* (i,u)$$

 - 벨만 오차 접근법 : 다음의 $r$을 찾는다.
$$\underset{min}{r} E _i \left\{\left(\tilde{J}(i;r)-(T\tilde{J}) (i;r)\right)^2 \right\}$$

$E_I \{\}$는 상태들의 분포의 관점에서 얻어진다.

 - 근사적 선형 계획법

Q-학습은 근사에 사용될 수 있다. 또한 Q-학습과 벨만 오차 접근법은 정책 평가에 사용될 수 있다.

 

정책 공간에서의 근사화

벡터 $r=(r_1,\cdots,r_s)$를 가지고 매개변수화 한 정책들 $\mu(i;r)$을 사용한다.

- 다항식 구조 : $\mu(i;r) = r_1 + r_2 \cdot i + r_3 \cdot i^2$

- 선형 특징점 기반 $\mu(i;r) = \phi_1(i)\cdot r_1 + \phi_2 (i) \cdot r_2$

$r$에 대한 비용을 최적화하면 다음과 같이 해볼 수 있다.

- $r$에 대한 각각의 값은 상태 $i$에서 시작하는 비용 $\tilde{J}(i;r)$을 가지는 정적 정책을 정의한다.

- $(p_1, \cdots p_n ) $ 를 상태에 대한 확률 분포라고 하고 $r$에 대해 다음을 최소화한다.

$$\sum_{i=1}^n p_i \tilde{J}(i;r)$$

- 랜덤 탐색, 그래디언트, 또는 다른 방법을 써본다.

특수 경우 : 정책이 근사적 비용 아키텍쳐를 통해 매개변수화 되는 경우

$$\mu(i;r)\in \underset{u \in U(i)}{\text{argmin}} \sum_{j=1}^n p_{ij} (u) (g(i,u,j) + \alpha \hat{J} (j;r))$$

 

근사적 정책 평가 기법

직접 정책 평가 Direct Policy Evaluation

 최소 자승법과 시뮬레이션에서 생성한 비용 샘플을 이용해서 현재 정책의 비용을 근사한다. 이는 근사 부분공간 $S=\left\{\Phi r | r \in \mathcal{R}^s \right\}$으로 $J_\mu$를 사영한 값$\Pi J_\mu$ 이다. 

 최소 자승법으로 해를 구하고 regular, optimistic의 정책 반복이다. 비선형 근사 아키텍쳐가 사용될 수 있다.

 

시뮬레이션을 통한 직접 평가

Monte-Carlo 시뮬레이션으로 사영하기

 가중치를 가지는 유클리드 norm $$||\cdot||_\xi$$에 대해서 부분 공간 $S=\left\{ \Phi r | r \in \mathcal{R}^s \right\}$에 $J_\mu$에 대한 사영 $\Pi J_\mu$를 계산한다.

위와 등가하게, 다음으로부터 $\Phi r^*$을 찾는다.

$$r^* = \underset{r\in \mathcal{R}^s}{\text{argmin}} ||\Phi r - J_\mu ||_{\xi}^2 = \underset{r \in \mathcal{R}^s}{\text{argmin}} \sum_{i=1}^n \xi_i (\phi(i)'r - J_\mu (i))^2$$

$r^*$에서 그래디언트를 0으로 설정하면

$$r^* = \left(\sum_{i=1}^n \xi_i \phi(i) \phi(i)' \right)^{-1} \sum_{i=1}^n \xi_i \phi(i) J_\mu(i)$$

분포 $\xi$를 이용하여 샘플 $\left\{(i_1, J_\mu(i_1)),\cdots , (i_k , J_\mu (i_k))\right\}$를 생성한다.

Monte-Carlo를 통해 저차원 연산으로 두 개의 "예상 값"을 근사한다.

$$\hat{r}_k = \left(\sum_{i=1}^n \phi(i) \phi(i)' \right)^{-1} \sum_{i=1}^n  \phi(i) J_\mu(i)$$

등가하게, 최소 자승법의 대안 연산은 다음과 같다.

$$\hat{r}_k = \underset{r \in \mathcal{R}^s}{\text{argmin}} \sum_{i=1}^n (\phi(i)'r - J_\mu (i))^2$$

 

간접 정책 평가 Indirect Policy Evaluation

ex) Galerkin 근사

사영 방정식 $\Phi_r = \Pi T_\mu (\Pi r)$을 푼다. 여기서 $\Pi$는 적절한 가중치가 있는 유클리드 norm에 대한 사영이다.

시뮬레이션을 이용하는 해법은 다음이 있다.

 - TD($\lambda$) : stochastic iterative algorithm for solving $\Phi r = \Pi T_\mu (\Phi r)$

 - LSTD($\lambda$) : 표준 해법을 가지고 시뮬레이션 기반 근사를 푼다.

 - LSPE(\lambda$) : 사영한 가치 반복의 시뮬레이션 기반 형태로

$$\Phi r_{k+1}  = \Pi T_\mu (\Phi r_k ) + \text{simulation noise}$$

 

벨만 방정식 오차 기법 Bellman Equation Error Methods

 간접적 근사 정책 평가의 다른 예시이다.

$$\underset{r}{\text{min}} ||\Phi r = T_\mu (\Phi r) ||_{\xi}^2$$

이는 사영 방정식/Galerkin 방정식과 매우 밀접하게 관련이 있다.

-------

 

또다른 간접 기법 : Aggregation

 묶기? 응집? 정도로 번역할 수 있을 것 같다.

 기본적인 아이디어는 비슷한 상태들을 "응집 상태 aggregate state"로 묶고, 각 그룹 $x_i$에 대해 공통적인 비용 가치 $r_i$를 할당한다. 그리고 $r=(r_1, \cdots , r_s)$를 얻기 위해 응집 상태를 가지는 "aggregate" DP 문제를 푼다. 이를 hard aggregation이라 한다.

 더 일반적인/수학적 시점으로 보면, 다음을 푸는 것이다.

$$\Phi r = \Phi DT_\mu (\Phi r)$$

$D$와 $\Phi$의 행은 확률 분포이다. ($D$와 $\Phi$는 선형 시스템 $J=T_\mu J$의 행과 열을 응집 aggregate 시킨다.)

사영 방정식 $\Phi r = \Pi T_\mu (\Phi r)$과 비교해보면 Aggregation은 다른 경우에서는 $\Phi D$는 사영이다.

----

 

근사 정책 반복의 주제들 Approximate Policy Iteration Issues

근사 정책 반복의 이론적 기초

 만약 다음과 같은 근사 아키텍처를 이용하여 근사적 정책 평가 Policy Evaluation 를 한다면?

$$\underset{i}{\text{max}} \left| \tilde{J} (i,r_k ) - J_{\mu^k} (i) \right| \leq \delta, \hspace{5mm} k=0,1,\cdots$$

 정책 향상 Policy Improvement 또한 근사한다면

$$\underset{i}{\text{max}} \left| (T_{\mu^{k+1}} \tilde{J} ) (i,r_k) - (T \tilde{J}) (i,r_k) \right| \leq \epsilon, \hspace{5mm} k=0,1,\cdots$$

오차의 유계 : 시퀸스 $\left\{ \mu^k\right\}$는 다음을 만족하는 근사적 정책 반복 Policy Iteration에 의해 생성된다.

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

전형적인 실제 거동으로, 위 기법은 한 점으로 꾸준히 나아가게 되며, $J_{\mu^k}$를 $J^*$의 이웃 내에서 진동시킨다

 진동은 매우 예측할 수 없다. 몇몇 좋지 않은 진동이 만들어지기도 한다. 그러나 실질적으로 정책간 진동들이 아마 주된 관심이 아니다.

탐험에 대한 주제 The issue of Exploration

 정책 $\mu$를 평가하기 위해, 해당 정책을 이용하여 비용 표본을 생성할 필요가 있다. 이는 정책 $\mu$ 하에 일어날 것 같진 않은 적게 나타낸 상태들에 의해 시뮬레이션으로 편향된다. 적게 나타낸 상태의 진행 비용(Cost-to-go) 평가는 매우 부정확할 수도 있다. 이는 향상된 정책 $\bar{\mu}$에 심각하게 영향을 준다. 이를 불충분한 탐험(Inadequate exploration)이라 한다. 전이 확률에서 내포된 무작위성이 "상대적으로 작을"때, 특히 더욱 어렵다. (결정론적 시스템 같은)

 해결 방안

 - 주기적으로 시뮬레이션을 재시작하고, 사용하는 초기 상태를 다양하고 대표적인 부분집합으로 설정한다.

 - 가끔 정책 $\mu$에 의한 제어가 아닌 무작위적으로 선택된 제어를 사용한 전이를 일으킨다.

 - 다른 방법 - 두 마르코프 연쇄를 사용한다. (하나는 정책 연쇄이며 전이 시퀸스를 생성하는데 사용하며, 다른 하나는 상태 시퀸스를 생성하는데 사용한다)

Q-factor의 근사

 주어진 $\tilde{J}(i;r)$에 대해, 정책 향상은 모델을 필요로 한다. (모든 제어 $u \in U(i)$에 대한 $p_{ij}(u)$의 지식)

 Model-free의 대안 : Q-factor를 근사한다.

$$\tilde{Q}(i,u;r) \approx \sum_{j=1}^n p_{ij} (u) \left( g(i,u,j) + \alpha J_\mu (j) \right)$$

 그리고 정책 향상을 위해 최소화를 이용한다.

$$\bar{\mu}(i) \in \text{arg} \underset{u \in U(i)}{\text{min}} \tilde{Q} (i,u;r)$$

 $r$는 조정 가능한 매개변수 벡터이고, $\tilde{Q}(i,r;r)$는 아래와 같은 매개변수화된 아키텍처이다.

$$\tilde{Q}(i,u;r) = \sum_{m=1}^s r_m \phi_m (i,u)$$

 여기에 비용 근사 접근법을 적용해볼 수 있다. (ex> projected equations, aggregation)

상태 $(i,u)$인 마르코프 연쇄를 이용하고, $p_{ij}(\mu(i))$는 $(j,\mu(i))$의 전이확률이다.

주요 관심사 : 격렬히 감쇄되는 탐험

 

일반적인 주제

Stochastic Algorithms : Generalities

 $A+W_k, b+w_k, k=1,\cdots,m$인 $m$개의 시뮬레이션 샘플을 이용하는 선형 방정식 $x=Ax+b$의 해법을 생각해보자. $w_k , W_k $는 시뮬레이션 소음같은 무작위값이다.

 $x=Ax+b$를 근사적 정책 평가로 생각해보자. (projected or aggregation equations)

 추계 근사 접근 (SA, Stochastic Approximation Approach)

$$x_{k+1} = (1-\gamma_k ) x_K + \gamma_k \left((b+w_k ) + (A+W_k ) x_k \right), k=1,\cdots,m$$

 몬테-카를로 추정 접근법 (MCE, Monte-Carlo Estimation Approach)

$A$와 $b$의 몬테 카를로 추정을 구성한다.

$$b_m = \frac{1}{m} \sum_{k=1}^m \left(b+w_k \right) , \hspace{5mm}A_m =\frac{1}{m}\sum_{k=1}^m \left(A+W_k \right)$$

그러면 $x=b_m +A_m x$은 역행렬을 이용하여 푼다.

$$x_m = \left(1-A_m \right)^-1 b_m $$

- TD($\lambda$)와 Q-learning은 SA 기법이며

- LSTD($\lambda$)과 LSPE($\lambda$)은 MCE 기법이다.

 

비용, 비용의 차이? 어떤게 좋을까?

 정확한 정책 향상 과정을 고려해보자. 상태 $x$에서 제어 $u$와 $u'$를 비교하면,

$$E\left\{ g(x,u,w) -g(x,u',w) + \alpha \left(J_\mu (\bar{x}) - J_\mu (\bar{x}')\right)\right\}$$

 여기서 $\bar{x} = f(x,u,w)$이고, $\bar{x}' = f(x,u',w)$이다.

$J_\mu (\bar{x})$ 또는 다음을 근사한다.

$$D_\mu (\bar{x} , \bar{x}') = J_\mu (\bar{x}) - J_\mu (\bar{x}')$$

$D_\mu (\bar{x}, \bar{x}')$를 근사하는 것은 "소음의 차분 Noise differencing"을 피한다. 이는 큰 차이를 만들 수 있다.

중요한 점은 $D_\mu$가 상태 $(x,x')$를 가지는 시스템에 대한 Bellman equation을 만족한다.

$$D_\mu (x,x') = E\left\{ G_\mu (x,x', w) + \alpha D_\mu (\bar{x}, \bar{x}')\right\}$$

 여기서 $\bar{x} = f(x,\mu(x),w)$이고, $\bar{x}' = f(x,\mu(x'),w)$이며 

$$G_\mu (x,x',w) = g(x,\mu(x), w) - g(x' , \mu (x'), w)$$

$D_\mu$는 표준 기법으로 "학습 될" 수 있다. (TD, LSTD, LSPE, Bellman error, aggregation 등..) 이는 차분 학습 Diffential training이라 한다.

 

Example : 

 다음의 시스템과 단계 당 비용이 있다.

$$x_{k+1} = x_k + \delta u_k , \hspace{5mm} g(x,u) = \delta (x^2 + u^2 ) $$

$\delta>0$는 매우 작다; $dx(t)/dt = u(t)$인 연속-시간 문제의 이산화를 생각해보자.

정책 $\mu(x) = 2x$라면 비용함수 $J_\mu (x)$와 Q-factor $Q_\mu (x,u)$는 다음과 같다.

$$J_\mu (x) = 1.25x^2 (1+\delta) + O(\delta^2)$$

$$Q_\mu (x,u) = 1.25x^2 + \delta \left(2.25x^2 + u^2 +2.5xu\right) + O(\delta^2)$$

정책 향상의 중요한 부분은 아래 부분이다.

$$\delta(u^2 + 2.2xu)$$

$J_\mu (x) \text{ or } Q_\mu(x,u)$는 $\tilde{J}_\mu(x;r) \text{ or } \tilde{Q}_\mu (x,u;r)$에 의해 근사된다. 이는 $2.5x^2$이 지배적이게 되고, 사라질 것이다.

 

끝.