강화학습 학습하기

7편 - Value Function Approximation

"강화학습 학습하기"시리즈는 KAIST 신하용 교수님의 수업 IE540 "DP and RL"수업 내용을 제가 제 방식대로 요약 및 정리한 것입니다. 퍼가실때는 미리 물어봐주시고, 내용은 제가 변형하고 추가하되 렉쳐노트에 쓰인 그림은 사용해도 된다고 교수님께 허락 받았습니다. 

0. Previously on..

그 동안 우리가 배운 상황은 lookup table을 사용한 경우였다. 

 Lookup tables for state value function(V),action value fuction(Q)

Lookup table을 사용할때란 discrete한 경우의 state와 action이 있고, 해당되는 값(Value function)들이 적힌 표가 쭉 나열되어있는 것이다. 그리고 TD를 사용하던, MC를 사용하던 target들을 이용하여 현재 value function의 값을 update하는 것이다. 이때 사용되는 error는 method마다 당연히 다르다. 이 방식은 많은 상황에서 효과적이나 두 가지 문제점이 있다. 

첫 번째는 large state space/action space에는 적용하기 매우 어렵다는 것이다. 저장공간이나 계산시간이 기하급수적으로 늘어나기 때문에, impractical하다. 또한 continuous action/space의 경우에는 적용하기 힘들다. infinite한 길이를 가진 state space는 만들 수 없기 때문이다. 

두 번째로 이게 더 중요한 부분인데, No generalization problem이다. Lookup table은 각각 상태를 개별적으로(독립적으로) 계산한다. 많은 경우에는 인접한 state끼리는 value function이 비슷하다. 예를 들어 밑에 있는 그림처럼 trap의 영향을 크게 받는 부분을 제외한 부분들은 어떤 비슷한 경향성이 있다. Start state(가장 위쪽,왼쪽 state로 -5.26) 오른쪽 값은 -4.86으로 수렴하고, 밑쪽 값은 -4.88로 수렴한다. 이것처럼 비슷한 값을 갖는다는 것을 고려하지 못한 상태로 각각의 상태들을 독립되게 계산한다면(상태들이 서로 isolate되면서 계산한다면) 비효율적이다. 이것을 해결하기 위해 우린 Value Function Approximation을 공부한다. 

이와 비슷한 방식은 이미지 처리를 위해서 pixel를 기다란 띠로 만들어서 계산하다가 CNN(합성곱신경망)을 적용해서 general feature를 뽑아 내는 것이다. 

인접한 state끼리는 크게 다르지 않다. 적어도 어떠한 경향성을 고려할만한 가치가 있다.  

1. Function Approximation

1-1. Function Approximation

Function Approximation

V(state), Q(s,a)를 그대로 사용하는게 아니라 V,Q를 어떤 parameter에 대한 식이라고 생각해보자. 이를 parameterize라고 한다. w는 function parameter가 되며, 이때 앞서 말한 문제점 1번을 해결하기 위해 w의 dim은 원래 state의 크기(not dimension of S but cardinality of S)보다 훨씬 작아야 한다. 이제 우리의 문제는 정확하게 V,Q를 모사하는 최적의 w를 찾는 것이다. 이때의 w는 환경과의 interaction을 통해서 (Error) update한다. 

두 가지 선택지

Function Approximation할 때는 두 가지가 필요하다. 첫 번째는 어떤 feature를 선택할지, 그리고 어떤 function form을 택할지 이다. 일반적으로 linear combination of features와 neural net을 사용하는데, 이번 편에서는 linear까지만 다루고 다음 편에 Neural Net을 이용한 DQN을 다룰예정이다. 

1-2. Optimization formulation of FA.

앞서 말했듯이 이제 문제는 funtion parameter w를 구하는 문제로 바뀌었다. 이 문제는 최적화라는 카테고리로 들어간다.

Objective Function(or cost function)

위에 있는 목적 함수는 true value function와 현재 estimated value function의 차이를 제곱해서 평균(mean squared error,MSE)낸 것이다. 밑에 있는 목적함수(mean squared value error,MSVE)는 어떤 상태들에 몇 번이나 방문했는지를 반영한 staionary distribution을 이용한 식으로 더 많이 방문한 state는 더 정확하게 적게 방문한 state는 덜 정확하게 update되는 경향을 가진다. 

최적의 해를 찾아가기 위해서는 gradient descent라는 개념이 필요하다. 현재 gradient의 반대방향으로 가야 해를 찾을 수 있기 때문에 목적함수의 gradient를 구한다. 

Derivatives of Objective Function

Expectation까지 계산하기 어렵기 때문에, 일반적으로 sample gradient를 사용한다. 

이때 문제점이 V_pi(s)를 모른다는 것이다. 이미 true value function을 안다면 이런 고생을 안해도 되지만 모르는 값에서 차이를 계산해서 다시 모르는 값을 찾기 위해 gradient descent하는 것은 모순이지 않은가. 그래서 같이 사용하는 method에 따라서 true state value funtion 대신에 target value를 대입해서 푼다.

True target을 사용할 수 없기에 아래 같은 target value를 이용한다. 

v(S_t+1;w_t)를 계산할 수 없는 이유는 이전 method들과 다르게 V(S_t)값을 저장하지 않기 때문에 이러한 계산을 불가능하다. TD(lambda) with value function approximation을 같이 살펴보면서 어떤 방식으로 w를 update하는지 알아보자. 먼저 Forward view라면 끝까지 계산하고 나서 그 값을 이용한 error를 계산하고 그 error를 이용해 w를 update한다. 

만약 backward view라면 매 step마다 생기는 1-step TD error를 eligibilty 를 가지고 뒤쪽 상태를 업데이트하는 것이다. 이때 책임감을 갖는 것은 state가 아니라 바로 parameter w이다. 이때의 eligibility는 decay하고 gradient value function을 계산한다.

원래 TD method를 사용할때면 terminal state의 value function을 0으로 해야하지만, parameter를 이용할 경우 이는 불가능하다. 그래서 만약 다음 상태가 terminal이라면 이때 v(S')이 0으로 정의한다. 앞서 봤던 TD algorithm과 거의 동일하다.

Algorithm TD(lambda) with VFA

1-3. Control with VFA

Evaluation을 했으면 한발 더 나아가서 어떤 action을 취할 것으로 정하는 control을 고려할 수 있다. 밑에 보이는 식들은 VFA를 이용한 다양한 method의 w update 식이다. learning rate와 method_error(Method Target-현재 고려중인 value function)과 gradient of value function의 곱이다. TD(lambda) 중 backward view의 경우만 eligibilty를 고려한다. 

Control with VFA, The blank is "the w gradient of q(S_t,A_t ; w_t)".

1-4. Many algorithms

Value Function Approximation을 이용한 여러가지 algorithm이다. State를 이용한 algorithm과 거의 유사하지만, V(state)값을 update하지 않고 w를 update하는 것이 큰 특징이다. 

2. Features

2-1. Feature vector

Feature vector는 VFA에서 state를 대체하는 것이다. 

chess의 경우처럼 모든 말에 대한 위치를 state로 저장하면, 크기가 매우 커진다. 64^32이기때문에 impractical 경우이다. 그래서 feature vector는 그렇게 계산하기 보다는 black nights가 몇개인지를 고려하는 feature로 사용한다. 또 다른 예로는 컬링이 있다. 컬링의 경우도 모든 돌의 위치 정보를 state로 할 수 있지만, 그보다는 빨간 돌이 house에 얼마나 있는지, 주위에 가장 가까운 돌이 빨간색인지 아닌지를 판단하는 특성 벡터를 만들어서 사용한다. 

모든 정보를 담는 state보단 특징, 경향성을 이용해서  curse of dimensionality 문제를 해결하려고 한다.

2-2. Feature construction

이러한 feature vector를 만드는 방식에는 여러가지가 있다. 

 첫 번째로 polynomial terms이다. 다항식 term들로 feature 구성하는 것이다. 이때 예제를 참고하면, 상태는 두개인데, feature vector가 더 복잡한 형태인 것(quadratic regression)이다. 이는 복잡한 형태의 feature vector와 linear functional form을 이용하면, 매우 효과적이기 때문이다. 그래서 최대한 linear한 functioal form을 적용하기 위해 feature vector가 자연스레 복잡해진다. 

두 번째로는 우리가 잘 알고 있는 ln(s), 1/s혹은 periodic function일 경우 주기성을 고려하기 위해 Fourier analysis의 basis인  cosine,sine function을 사용한다. 

세 번째로는 기준 점 S를 잡은 후에 S로부터의 떨어진 거리를 feature하는 경우가 있다. 

 또 중요한 방법으로는 state aggregation이 있다. 회사에서 파티션을 나누는 것처럼 서로 겹치지 않는 파티션을 나눈 후에 이에 해당하는 상태들에 대해서 function 1(indicator function)을 적용한다. 여기서 function 1은 만약 function 1(condition)일 때, condition 이 true면 1을 return하고 false면 0을 return한다. Feature vector x(s)는 state s가 어디 파티션에 들어가 있는지를 나타내는 feature이다. 우리가 사용했던 random walks문제에서도 이런 방식을 적용하며, 특이한 점은 같은 파티션은 같은 value function을 갖는 것이다. 다른 state이지만 같은 파티션이고 같은 feature vector이기 때문이다. 

 비슷한 방식으로는 Coarse coding이 있다. 이 방식은 앞에서 봤던 state aggregation에서 파티션을 나눌때 중복해서 나눠도 된다는 것이다. 흰색 X자 표시에 해당하는 state라면 narrow generalization의 경우는 겹치는 부분이 상대적으로 좁기 때문에 3개의 feature를 갖게 되지만, broad 의 경우는 더 많은 4개의 feature를 가진다.

 또 다른 tile construction 방법으로는 Tile coding이 있다. 타일을 뒤덮는 것처럼 만드는 것으로  coarse coding과 state aggregation을 합친 모양이다. Tiling이란 state space의 하나의 파티션을 말하고, 하나의 tiling안에 있는 하나의 tile은 state spae S의 subset이다. 

 예제를 통해 보면, 예를 들어, 4*4 grid world가 있고, 우리가 표현하고 싶은 상태는 state8이라고 하자. 이 위치는 (2,4)이다. 이 상태를 state 8이라고 하는게 아니라 tile coding으로 표현하면, row tiling은 파란색 타일이 4개씩 들어있는 4개의 가로줄들이 되고, column tiling은 빨간색 tile이 4개씩 들어있는 4개의 세로줄들이 된다. 우리가 원하는 위치의 feature vector는 ( 0,1,0,0,0,0,0,1)이 된다. State aggregation처럼 상태공간을 파티션으로 나눴지만, 그 파티션을 동시에 공유하는 stete가 있어도 된다. 마치 (2,4)의 feature vector처럼. 이 feature vector는 row tiling 중에서 R2와 column tiling 중 C4를 동시에 가진다. 

위에 그림처럼 불규칙적이거나, 간격이 일정하지 않거나 아예 기울어진 형태로 tile coding을 진행할 수 있다. 지금까지 설명한 여러가지 방법을 통해서 기존에 가지고 있는 state들 사이의 정보를 잘 반영하는 feature vector를 만들 수 있다. 이러한 feature vector가 만들어졌다면, state에 해당하는 값을 가지고 있는 w parameter를 같이 고려하면 function approximation을 할 수 있고 w를 지속적으로 update하면서 true value function을 찾을 수 있다. 

3. Linear Function Approximation

VFA는 feature selection, function form selection을 잘 하면 된다. Well chosen n features에다가 appropriate function form을 얹으면 VFA는 자동적으로 된다. 이번 경우의 function form은 linear만 고려한다. Linear VFA는 매우 간단한 형태로 주로 (well chosen) features에 사용한다. 앞서 봤던 예제처럼 복잡한 features를 사용해도 괜찮은 이유는 linear function form을 사용할 수 있기 때문이다. 

v(s;w)는 w와 x의 linear combination이고, 당연하게도 v에 대한 w gradient는 x(s):state feature vector이다. 

v에 대한 w gradient 자리에 전부 x(s)가 들어가 있는 것을 확인 할 수 있다. v가 아니라 q를 사용해도 마찬가지이다. 

우리가 앞서 봤던 lookup table은 linear VFA일까? 답은 그렇다. 

위에 보이는 그림 처럼, lookup table에서 현재 state value function값 업데이트하는 결론이 똑같이 나온다. 앞서 말했던 function1이 indicator function으로 조건문이 true면 1이다. 

4. Convergence of Control methods with VFA

- Function approximation

- Bootstrapping

- Off-policy training

-> 이 세 가지 문제가 결합되는 경우는 converge하기 어렵다. 

Q-learning algorithm with linear VFA를 사용하면, 위에 언급된 세 가지 문제가 다 해당되기 때문에 converge하지 않는다. Bootstrapping을 사용하는 SARSA의 경우는 with linear VFA인 경우 근사적으로 최적값으로 converge한다. 그러나 nonlinear VFA를 사용할 경우 converge하기 쉽지 않다.