[Ch.8] Value Function Approximation

 

 지난 포스팅까지 살펴본 방법론들은 제가 구현한 code를 보시면 느끼셨겠지만 value func.과, action value func.을 table로 저장하고 이를 꺼내어 쓰고, update하는 방식으로 이루어집니다. 이러한 방법을 Tabular Method라고 합니다. Ch.5의 MC control agent와 Ch.6의 SARSA agent를 구현한 gridworld에서는 col, row가 각각 5개씩, 그리고 이에 취할 수 있는 action은 4개였습니다. 하지만, 간단한 gridworld가 아닌, 현실의 문제는 이보다 훨씬 복잡한 환경에서 이루어집니다. 아래글은 Sutton 교수님의 책에서 이에 대해 인용한 것입니다.

 

We have so far assumed that our estimates of value functions are represented as a 

table with one entry for each state or for each state-action pair. This is a particularly clear and instructive case, but of course it is limited to tasks with small numbers of states and actions. The problem is not just the memory needed for large tables, but the time and data needed to fill them accurately. In other words, the key issue is that of generalization

 

 

 "small numbers of states and actions"로 이루어진 task에만 적용할 수 있다는 한계가 있으며, generalization의 issue가 있다고 합니다. 지금까지는 모두 간단하고 직관적인 환경에서 적용하며 개념을 익혔다면, 앞으로는 현실의 문제로 generalization할 방법을 다룰 것이고 그 첫 걸음이 바로 이번 포스팅에서 다룰 Value function Approximation입니다.

 

---

Value function Approximation

 Parameterizing value function

 우리가 사용할 data가 아래 왼쪽 그림과 같다고 가정해보겠습니다. 각각을 정확하게 알고 있으면 좋겠지만, 그 양이 무수히 많으면 모두 저장하고 있는 것에 한계가 있습니다. 그래서, 오른쪽 그림과 같이 이를 대신하여 data들이 일정한 경향성을 가지고 있다면, 그리고 이를 함수화시켜 놓는다면 필요할 때마다 실측값에 근사하여 사용할 수 있습니다. 이렇게 되면 상당한 이점이 있습니다. 

 

1) 실제로 가지고 있지 않은 data도 func.을 통해서 구할 수 있다

2) 실제 data의 noise를 배제하고 training할 수 있다

3) 고차원의 data도 효율적으로 저장이 가능하다

 

 

image source : http://eeweb.poly.edu/iselesni/lecture_notes/least_squares/LeastSquares_SPdemos/poly_approx/html/poly_approx_demo.html

 

<Fig 1. Data(Left), Value approximation with func.(Right)>

 

이렇게 각각의 data들을 모두 저장하는 것이 아니라 만약 ax3+bx2+cx+d라는 식의 형태로 표현이 가능하다면 방대한 양의 data를 저장하는 것 대신, parameter(a,b,c,d)만 저장하는 방식을 택합니다. 이처럼 강화학습에서는 차원이 큰 문제를 다루기 위해 table을 이용하여 값을 저장하는 것이 아닌 새로운 변수 w에 대해 parameterizing한 function을 이용합니다. 그리고 이렇게 parameter를 이용하여 실제 값에 approximate하는 함수를 function approximator라고 합니다. 우리는 아래와 같이 value func.과 action value func.에 w로 parameterization하여 함수화합니다. 

 

 

그리고 학습을 통해 이 w라는 parameter를 update하며 true value func.과 근사하도록 맞춰나갑니다. atari게임에서는 function approximator로써 deep learning을 사용했기에 deep reinforcement learning이라고 부릅니다. 최근에는 이 deep learning을 사용하는 방법이 주목받고 있습니다.

Learning with Function Approximator

 이제 w를 update하는 방법에 대해 알아보겠습니다. 크게는 Gradient descent방법을 사용하는데, 이 방법도 1) Stocahstic Gradient Descent(SGD) 2) Betch Methods로 나뉩니다. 이 단락에서는 개략적인 Gradient descent의 개념에 대해서 다루고 뒤에서 두 가지 방법에 대해 각각 설명하겠습니다.

 Gradient Descent

 기본적인 개념은 이렇습니다. true value func.과 estimated value func의 error를 parameter w의 함수 J(w)로 잡고(differentiable), 이를 minimize하는 것을 목표로 합니다. 이 때, 어느 방향으로 움직여야 error값을 줄일 수 있느냐를 판단해야하는 데, 이를 함수의 gradient, ∇wJ(w)를 이용하여 판단합니다. 하지만, gradient 자체는 경사의 기울기이기 때문에 이에 (-)값을 취해서 이를 descent하면 error를 줄이는 방향으로 이동합니다.

 

 

      

 

다만, Ch.5 MC Control의 2) Local Optimum 부분에서 골짜기와 공의 예를 들어 설명하였듯이 이 방법은 local optimum에 빠질 위험이 있습니다. 아래는 간단하게 local opitmum 문제를 살펴보기 위해 구현한 code입니다.

 

 

 

 

code를 보시면 extreme point는 두 개로 minimize를 하는 문제에서는 -2.25가 global optimum이지만 x=1부터 gradient descent방법을 적용하다보면 x=0인 local optimum에 빠지는 것을 확인할 수 있습니다. 이를 해결하는 방법은 다른 포스팅에서 다루고 여기서는 gradient descent라는 개념만 살펴봅니다. 이 방법은 가장 간단한 gradient descent 방법으로 Vanilla method라고도 부릅니다.

 Gradient Descent on RL

For state-value func.

 위 개념을 강화학습에 적용해보겠습니다. update의 대상이 되는 것은 true value func.이고 error함수,  J(w)를 true value func.과 approximated value func.의 MSE로 잡습니다.

그리고, gradient를 아래와 같이 정의해서 gradient descent 방법을 적용합니다.

         

이전에 MC와 TD에서 다루었듯이, update의 target을 변형해서 다양한 variation이 가능합니다. 

        

                    

For action-value func.

 우리가 model-free하기 위해서는 action-value func.을 이용합니다. GD방법을 적용할 때에 위 식에서 value func.을 action-value func.으로 바꾸어주면 됩니다.

 

    

그리고 이 역시도 다양한 variation이 가능합니다.

 

               

   

  

Stochastic Gradient Descent(SGD)

 이제 gradient descent방법 중 하나인 Stochastic Gradient Descent(SGD)에 대해서 살펴보겠습니다. 우리는 parameter w에 대해 loss func.으로 J(w)를 정의했습니다. 그리고 이것의 gradient, ∇wJ(w)의 (-)방향으로 이동하며 loss의 minimum값으로 도달하는 것이 목표입니다. 이때, loss func.을 계산하고, parameter w를 update하기까지의 과정에서 1개의 data를 사용하는 방법을 생각해 볼 수 있습니다. 다만, 이 data를 뽑는데, 전체 data에서 random하게 확률적(stochastic)으로 추출합니다. 그래서 이 방법을 Stochastic Gradient Descent(SGD)라고 합니다.  

Batch Methods

하지만 data 하나만 이용하게 되면 update가 매우 자주 일어나므로 global optimum으로 일정하게 가지 않을 수도 있고 계산량이 많아 속도가 느립니다. 그래서 이와 다르게, 지금까지의 경험들을 모아서 loss func.을 모든 state에 대해 계산하는 (Full) Batch gradient descent를 생각해볼 수 있습니다.

대부분의 경우에는 SGD나 Full Batch GD보다는 mini-Batch SGD를 사용하게 되는데, training data set을 일정한 크기만큼 sampling하여 mini-batch를 만들고 이를 통해 update하는 방법입니다. 비슷한 방법으로, DeepMind가 atari game에 DQN(Deep Q-newworks)과 함께 적용한 Exprerienc Replay라는 algorithm이 있습니다. GD에서 sample을 한번 update하고 끝나는 것이 아니라 이를 replay memory에 time step마다 transition pair(st, at, rt+1, st+1)를담아두고 정해진 n개만큼 꺼내어 mini-batch를 형성하고 이들을 통해 parameter w를 update합니다. ith mini-batch에 대해 w-는 olde paramter, Di는 replay memory입니다. J(w)와 구분하여 loss func, L(w)는 아래와 같습니다.

 

 

The Algorithm of Gradient Descent Optimization 

 최근에는 이러한 SGD를 이용하는 방법이 neural network에서 한계에 부딪혀 이를 변형한 다양한 알고리즘이 등장합니다. 여기서는 교재에서 나온 GD이외에 Momentum과, NAG에 대해 다루겠습니다. 이외에 Adagrad, Adadelta, RMSProp 그리고 Adam이라는 algorithm도 있으나, 이는 추후에 다루겠습니다.

 

 아래는 Ref.[6]에서 이 방법들이 수렴하는 방향과 속도를 가시화한 그림입니다. SGD보다 속도도 빠르고 더 잘 수렴하는 것을 확인할 수 있습니다.

 

 

image source : 

http://ruder.io/optimizing-gradient-descent/index.html#challenges(Ref.[6])

<Fig 2. GD optimization algorithms on loss surface contours>

 Momentum 

 Momentum은 말 그대로 관성을 이용하는 것입니다. GD의 방법으로는 위와 같이 수렴하는 속도가 느리기때문에 이전에 속도에 가속을 하자는 idea입니다. 우리가 parameter w를 update하는 식은 아래와 같습니다.

 

 

이 식에 momentum을 적용해 보겠습니다. t시간에서 w가 이동하는 vector, vt를 이용하고 momentum rate, γ(<1)를 이용하여, 이전 vt-1를 얼마나 가져갈 것이냐를 결정합니다.

 

 

 

 

Momentum은 특히 SGD가 oscillate(진동)할 때, SGD에 accelerate하여 조금 더 빨리 수렴할 수 있록 도움을 줍니다. 이 Momentum term은 gradient가 기존에 진행하던 방향과 같은 data에 대해서는 증가하고, 이를 바꾸는 data에 대해서는 update의 정도를 줄여서 oscillation을 줄이고, 더 빨리 수렴하는 것을 기대함과 동시에 가속의 영향으로 local optimum에 빠지는 문제도 해결합니다. 보통 momentum rate, γ는 0.9정도로 setting합니다. 

 Nesterov accelerated gradient

 때때로, 우리가 이전에 진행하는 방향을 수정해야할 때가 있습니다. 하지만, Momentum 방식으로 update할 시에는 이 관성때문에 방향을 수정하려고해도 기존 방향을 계속 따를 수밖에 없습니다. 따라서, 우리는 이전의 관성도 이용하면서 적당히 바꿔야할 방향으로 flexible하게 바뀌는 방법이 필요합니다. NAG는 Momentum의 방법에서 이와 같은 문제점을 해결하기 위해 gradient를 계산하는 방법에 variation을 주는 것입니다. 

 

<Fig 3. Neterov accelerated gradient(NAG)>

 

Momentum update방법에서는 현재 data에서의 gradient와 momentum vector를 독립적으로 두고 계산합니다. 하지만 NAG방법은 momentum을 먼저 진행했을 때의 도착점에서 gradient를 계산함으로써 actual step을 조금 더 gradient step쪽으로 바뀌게 됩니다. update식은 아래와 같습니다.

 

 

       

마치며

이번 포스팅에서는 현실에서 정의된 MDP를 풀기 위해 func. approximator를 이용하는 이유와 그 중 대표적인 Gradient Descent에 대해 알아보았습니다. 다음 포스팅에서는 이 func. approximator로써 Deep Learning을 이용한 DQN에 대해 다루겠습니다. 

 

오탈자나 잘못 언급된 부분이 있으면 댓글로 지적해 주세요 :)

 

Reference

[1] https://dnddnjs.gitbooks.io/rl/content/value_function_approximator.html

[2] 이웅원, 양혁렬, 김건우, 이영무, 이의령. "파이썬과 케라스로 배우는 강화학습". 위키북스. p.154-192

[3] https://en.wikipedia.org/wiki/Gradient_descent

[4] https://wikidocs.net/4760

[5] http://codepractice.tistory.com/76

[6] http://ruder.io/optimizing-gradient-descent/index.html#challenges

[7] http://aikorea.org/cs231n/neural-networks-3/#sgd