[강화학습] 8. On-Policy Prediction with Approximation

On-Policy Prediction with Approximation

지금까지 한 모든 방법론은 state/action function을 table형태로 저장하여 꺼내쓰고 update하는 Tabular method였었다. 하지만 복잡한 현실의 문제를 table로 표현하는데 한계가 있다.

• state과 action이 굉장히 많을 때 (바둑의 states는 10의 170승) 

• state나 action이 discrete 하지 않고 continuous할 때 (Robot control)

이럴 때 function approximation 개념을 도입해 table 형태가 아닌 continuous한 value function을 approximate할 수 있다.

그리고 미리 말하자면 function approximation을 우리에게 제법 친숙한 방법으로 찾을 예정이다. 바로 학습 가능한 parameter를 통한 learning개념(like supervised learning)으로 function approximation하는 방법을 소개한다. 

※ 참고로 function approximation을 deep learning으로 학습하면 Deep RL이라고 부른다. 최근에 주목받고 있는 방법이다. 추후에 DQN시간에 자세히 다루도록 한다.

Intro. On-Policy prediction with approximation

우리의 첫 target은 늘 그랫듯, policy가 주어졌을 때 value-function을 evaluate(혹은 prediction)하는 것인데, 이 과정을 한번 function approximation 해보자.

이제 우리에게 주어진 value-function은 discrete하지 않고 state의 continuous function이다. 이 식을 우리는 weight w로 parameterize 시킬 예정이다. 그리고 앞서 언급했듯, supervised learning에서 weight를 학습해 loss function을 찾는 과정과 매우 유사하다.

그렇기 때문에 weight 학습을 위해 우리에게 필요한 것은 training example with label과 measure of error이다.

※ 참고로 weight를 이용한다는 것은, 무수히 많은 states 즉, 고차원 state를 상대적으로 낮은 weight의 차원으로 근사화 한단 것을 의미하기도 한다.

그리고 value function을 approximate 하려면 "function의 모양이 어떨 것이다." 라는 가정(hypothesis)이 필요한데, 

• linear function

• polynomial function

• multi-layer neural network

등 value function의 hypothesis를 결정하는 다양한 basis function에 대해서도 살펴볼 예정이다.

그리고 value function의 hypothesis, sample state(=x), sample value(=label), error 등 만발의 준비가 끝나면 위와 같이 supervised learning 하듯 value function을 fitting 할 예정이며,

fitting이 끝나면 위 그림과 같이 sample value를 학습한 curve가 완성될 예정이다. 

그리고 한번의 학습으로 각 state의 value가 결정되는 Tabular method에 비해, approximation method는 sample이 추가될 때 마다 adaptive learning 되는 특징이 있어서, 위 그림과 같이 전체 state의 value가 update된다.

그럼 지금부터 value function을 approximate 하기 위해 필요한 구성요소들에 대해서 하나하나 알아보도록 하자.

Weighting distribution

앞서 우리는 true value function을 추정하기 위해 parameterized 된 function을 구하기로 소개하였다. 

그리고 분명, true vs. approx. function간의 오차를 최소화 하는 optimization 과정을 가질텐데, 이 때 optimal policy에 영향을 미치지 않는 state들까지 모두 세세하게 튜닝될 필요는 없다. 

그래서 필요한 개념이 바로 weighting distribution이다. weighting distribution μ(s)은 어떤 state를 집중해서 케어해야할 것인지 중요도를 판단하기 위한 개념이다. 

그리고 그 중요도는 허무할 정도로 간단하게 구해진다. 바로 episode에서 자주 보였던 state의 priority를 크게 평가하는 방법이다.

위 pseudo code의 η(s)는 모든 episode에 몇 번이나 state s가 출현했는지를 counting 하는 것을 의미한다. η(s)를 구할때 h(s)는 start state에 나타났었는지를 의미하고(0 or 1), 나머지 우측항은 그 이후에 policy를 따라 action을 취했을 때 나온 횟수이다.

그리고 μ(s)는 각 state의 출현 횟수를 전체 num_states로 normalize한 것이다.

Performance measure

weighting distribution은 true vs. approx. function의 error를 measure하는데 사용된다.

approximate value-function이 얼마나 잘 근사화 됐는지를 측정하기 위해 두 function간 MSE개념을 적용하며, 단순 error가 아니라 value의 error라고 해서 Mean Squared Value Error(MSVE)라고 부르기도 한다. 

그리고 'Mean'의 역할을 앞서 배운 weighting distribution 즉, 확률을 곱해 평균을 취해줌으로써 performance measure로 활용한다.

이제 우리는 이 measure를 최소화 하는 방향으로 weight를 학습하면 value-function의 근사화가 완료된다.

이 때 만약 우리가 global minimum을 찾았다면 위 관계가 성립할텐데, 대부분의 문제는 한번에 global minimum을 찾기는 쉽지 않기 때문에 local minimum 후보들 중 택하는 방법을 주로 사용한다.

Backups as training examples

이제 우리의 error function을 잘 보자. error function에는 true value function vπ(s)가 존재한다. 그런데 문제는 우리는 vπ(s)가 continuous한 real target value라 모르는 상태이다.

그래서 우리는 위와 같이 전 포스팅에서 배웠던 MC, DP, TD 등의 estimate를 사용할 수 밖에 없다. 관련해서는 조금 뒤에 자세히 다루기로 하고, 일단은 estimate를 활용해서 value function을 approximate 해야한다는 것만 기억하자.

Stochastic-Gradient Descent (SGD)

그럼 이제 error 를 최소화 시켜줄 수 있는 weight를 찾아볼텐데, 아주 익숙한 알고리즘이 등장한다. 바로 SGD 알고리즘이다.

SGD 알고리즘은 특히 deep learning에 자주 쓰이는 iterative optimization 알고리즘 중 하나이며, batch_size = 1인 mini_batch optimizer라고 간단히 표현할 수 있다.

[mini-batch size = m인 SGD pseudo code]

매우 자세한 원리가 위 링크에 있으니 참고하도록 하고, On-policy prediction을 approximate하기 위해 SGD가 어떻게 weight를 구하는지 알아보도록 하자.

SGD의 정의에 따라 1개 sample이 주어졌을 때 weight의 update는 위와 같다. (α=learning rate)

다만 앞서 error를 설명할 때 언급했듯, label역할을 하는 true value v(s)를 모르기 때문에, Ut라는 값으로 approximate해야 한다. 

다행히 Ut가 unbiased estimator라면 true value일 것이고, wt는 local optimal value로 수렴할 것이란 것은 guarantee 되어 있다. 그리고 대표적인 unbiased estimator로써는 Monte Carlo의 target인 Gt가 있다. 

(real reward를 이용해 Gt → value를 estimate하는 MC는 unbiased estimator라 할 수 있다.)

위 pseudo code는 MC target G를 label로 한 gradient descent를 구현한 것이다.

Semi-gradient methods

그럼 MC가 아니라 DP나 TD의 evaluate도 error를 구하기 위한 true value로 사용할 수 있을까? 정답은 '가능하다' 이다. 하지만 bootstrapping을 사용한 시점에서 gradient method라고 부르기는 어렵다.

왜냐하면 MC의 estimate인 Gt는 true value로 w와 상관없이 구해지는 반면에, 

TD와 같이 bootstrapping으로 구해지는 estimate는 weight에 dependent 함으로 gradient를 계산할 때 함께 미분되어야 한다. 하지만 미분이 어려운 형태라 미분하지 않고 그냥 estimate 자체로 쓰기때문에 엄연히 gradient method라 볼 수 없다.

그런데 아이러니하게도 그 자체를 estimate로 적용했을 때 어느정도의 성능을 보장하고,

part of gradient를 구하는 bootstrapping의 특성을 고려해 semi-gradient method라 부른다.

그리고 다소 수렴성에 있어서는 약점을 가지고 있지만, 

linear case와 같은 간단한 경우에는 어느정도 수렴하고, terminal state까지 갈 필요 없이 빠르게 estimate 할 수 있다는 bootstrapping의 장점 때문에 자주 사용되곤 한다. 

State aggregation

state aggregation은 state가 많을 때 state의 그룹을 나눠서 그룹별로 one estimated value를 할당하는 대표적인 simple form of generalizing function이다.

위 예제는 1000개의 state가 있고, 왼쪽으로 갈수록 -1, 오른쪽으로 갈수록 +1의 reward를 갖는 아주 간단한 value function을 state aggregation으로 approximate한 결과다. SGD, Semi-GD와 같이 아주 가깝게 근사 시키지는 못하지만 어느정도 value function의 추세는 확인할 수 있는 간단한 방법이다.

Linear methods

지금까지 Label역할을 할 vπ(x)와 error function 그리고 SGD와 semi-GD와 같은 optimizer에 대해서 알아 봤다. 이제는 v_(hat)을 parameterize 시키고 본격적으로 학습시켜보자.

이 때 우리는 복잡한 state function을 basis function을 통해 linear model로 변환하여 SGD를 적용해볼 예정이다.

※ 많은 경우 linear technique를 사용해 linear problem으로 전환하는 것이 solution을 찾는데 쉽다. linear model이나 basis function에 대한 자세한 내용은 [머신러닝/딥러닝] Linear model 을 참고하도록 하자.

※ linear model로 state를 표현할 수 있다면 global optimal 혹은 그 주변으로 수렴한다는 것이 guarantee되어 있다. 

basis function을 통해 approximate value function을 linear function으로 변환했다면, weight로 편미분 함으로써 gradient는 쉽게 얻을 수 있다.

그렇기 때문에 MSVE(Mean Squared Value Error)를 최소화 하는 목적함수의 미분도 위와 같이 쉽게 전개할 수 있으며,

최종적으로 위와 같은 weight update rule을 도출 할 수 있다. 위 식의 Expectation이 구하기 어렵긴 하지만 우리는 1개 sample로 update하는 SGD를 적용하기로 했음으로,

이렇게 simple form으로 1개 sample이 입력됐을 때 weight를 update할 수 있는 update rule을 정의할 수 있다. 

위 식의 Ut는 true value function을 의미하는데, 앞서 설명한 TD(0)의 estimate를 대입한 예를 살펴보자. (물론 Ut에 TD(0)의 estimate를 대입하는 것은 엄연히 semi-gradient descent이다.)

여담으로 위 식의 양변에 Expectation을 취하고 정리하면 아래와 같은데,

wt가 수렴한다는 것은 좌, 우변의 변화량이 없다는 뜻이고,

좌, 우변의 변화량이 없다는 것은 위 조건을 만족하는 것을 의미하기 때문에, 

이 조건을 만족하는 weight Wtd를 TD fixed point라고 한다.

(= Linear semi-gradient TD(0) converges to this point)

위 예제는 state aggregation에서도 선보인 1000-state random walk task를 semi-gradient TD(0)로 value function을 approximate 한 결과이다.

확실히 MC의 결과(True value)에 미치지 못할 뿐만 아니라 state aggregation보다도 bias가 높은 것을 확인할 수 있지만, TD(λ)의 step λ를 조절하면 성능을 개선시킬 수 있음을 확인할 수 있다. (bootstrapping의 빠른 학습 속도를 누리기 위해 자주 사용된다.)

Feature Construction for Linear Model

앞서 확인했듯, state space를 basis function을 활용해 linear model로 전환할 수만 있다면 value-function을 쉽게 approximate 할 수 있는 것을 확인했다.

이렇게 원본 차원을 새로운 차원(feature)로 변환 하는 것을 feature construction이라고 하는데, feature construction을 어떻게 하느냐에 따라서 당연히 performance도 다를 것이다.

Linear transformation을 위한 몇 가지 basis function을 알아보도록 하자.

1) Polynomials

Polynomial basis는 여러 차원의 조합으로 polynomial feature를 생성해내는 방법이다.

예를 들어 s = {s1, s2} two dimensional states가 있을 때 이 두 차원를 조합해서 x(s) = (1, s1, s2, s1s2) 과 같은 feature vector를 만드는 것이다.

2) Fourier Basis

Fourier transformation을 통해 state를 sine, cosine function으로 조합된 차원으로 전환하는 방법이다. 

3) Coarse Coding

state가 continuous two-dimensional에 표현될 때, 특정 크기의 circle을 그려서 그 안에 포함되면 1, 바깥이면 0으로 binary하게 feature 를 뽑는 것이다.

위 예제를 통해 보면 좀 더 명확한데,

• s1은 circlr 1, 2, 4, 5와 겹쳐있기 때문에 s1 = [1 1 0 1 1 0]

• s2는 circle 3, 5, 6과 겹쳐있기 때문에 s2 = [0 0 1 0 1 1]

위와 같이 one-hot encoding과 유사하게 feature를 생성하는 방법이다.

4) Tile Coding

state가 blue tile의 몇번째에 들어갔는지, orange tile의 몇 번째에 속하는지를 표현하는 방법이다. multiple tiling을 할 수록 복잡한 feature를 생성한다 할 수 있다. 

(가까이 있는 state들끼리 feature가 유사하게 표현되는 효과가 있다.)

5) Radial Basis Functions (RBFs)

4, 5)에서 언급한 feature를 continuous하게 [0, 1]사이 값으로 표현하기 위해 Gaussian distribution으로 표현하는 방법이다. continuous 한 형태로 나타냄으로써 backprop. 혹은 미분이 쉽다는 장점이 있다.

6) Nonlinear Function Approximation: ANN

이론적으로 모든 함수를 근사화 할 수 있는 ANN(Artificial Neural Network)도 활용하기에 따라 function approximation으로 활용할 수 있다.