참고한 책 : Reinforcement Learning: An Introduction, 2nd edition (Richard S. Sutton, Andrew G. Barto)
개요
책의 챕터 9 이전에서 소개된 방법들은 value function이나 policy를 tabular한 형태로(표의 형태로) 구현하는 경우이다. 예를 들어 Value function은 수많은 state들과 그에 기대되는 가치의 관계는 표의 형태로 매핑된다. 하지만 이러한 Tabular한 접근은 한계가 있다. 환경이 복잡해질수록 state space는 매우 커지게 된다. 예를 들어서 지금 보고 있는 모니터로 표현할 수 있는 경우의 수는 어마어마하게 크다. 모니터 한 화면에 몇백만개의 픽셀이 있고, 한 픽셀은 256^3만큼의 정보량을 표현할 수 있다. 모니터 하나에는 256^3을 몇백만번 곱한 만큼의 state가 존재하는 것이다.
바둑은 19x19의 판 위에서 일어나는 일인데, 여러가지 규칙 때문에 불가한 경우를 제외하더라도208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935 가지의 경우가 가능하다고 한다. (참고)
이걸 전부 매핑할 테이블을 관리하는 것은 메모리 측면이나 계산비용이 문제가 되고, 또한 generalization 측면에서도 비효율적이다. 예를 들어 위의 W에서 점 몇개가 빠졌다고 해서 전혀 다른 state로 기록되면 낭비가 클 것이다. 이에 대한 훌륭한 해결책으로 function approximation이 있다. 저 수많은 경우들을 표현해 줄 수 있는 함수를 찾아버리는 것이다. 이는 널리 알려진 뉴럴 네트워크(인공신경망)가 하는 일과 동일하다. 뉴럴 네트워크는 한번의 inference로 계산이 가능하고, memory는 weight갯수에 한정되며, generalization또한 강력하다.
이걸 전부 매핑할 테이블을 관리하는 것은 메모리 측면이나 계산비용이 문제가 되고, 또한 generalization 측면에서도 비효율적이다. 예를 들어 위의 W에서 점 몇개가 빠졌다고 해서 전혀 다른 state로 기록되면 낭비가 클 것이다. 이에 대한 훌륭한 해결책으로 function approximation이 있다. 저 수많은 경우들을 표현해 줄 수 있는 함수를 찾아버리는 것이다. 이는 널리 알려진 뉴럴 네트워크(인공신경망)가 하는 일과 동일하다. 뉴럴 네트워크는 한번의 inference로 계산이 가능하고, memory는 weight갯수에 한정되며, generalization또한 강력하다.
Function approximation을 꼭 뉴럴 네트워크로 해야만 하는 것은 아니고, 책에는 여러가지 방법들이 소개되어 있다. 다만 가장 널리 이용되는 뉴럴 네트워크 위주로 서술하고자 한다.
챕터 9.2는 prediction시에 value function을 어떻게 function approximation을 할지에 대해 서술하고 있다.
VE는 value error의 약자로 실제 value function을 w(weight)로 이루어져있는 function인 v(s,w), 뉴럴 네트워크가 얼마나 잘 따라해주는가를 나타낸다. 뉴럴 네트워크가 본래 value function을 잘 근사해줄수록 VE는 0에 가까워질 것이다. 이러한 VE를 objective function으로 두고 gradient descent에 기반해 업데이트하여 근사를 진행한다.
이와 같이 objective function의 변화량을 사용해 weight를 업데이트하려면 objective function은 differentiable(미분가능)해야한다. 뉴럴 네트워크는 미분가능하다. 아래 예시는 Monte carlo prediction의 예시이다.
앞선 챕터 5 에서는 MC방식으로 샘플한 리턴들을 평균내서 value function에 직접 업데이트 했지만 여기서는 샘플한 에피소드 정보로 G, cumulative sum of reward를 계산해서 뉴럴 네트워크가 근사하게 한다. 이러한 근사 방식은 TD의 경우에서도 사용될 수 있다.
챕터 9 의 나머지 파트에서는 다양한 Linear methods, 이에 대한 feature construction 방식들로 Fourier basis, coarse coding, tile coding, Radial Basis Functions, 인공신경망 및 다양한 function approximation 방법들에 대해 소개한다.
p165, sutton and barto, Gradient MC prediction
앞선 챕터 5 에서는 MC방식으로 샘플한 리턴들을 평균내서 value function에 직접 업데이트 했지만 여기서는 샘플한 에피소드 정보로 G, cumulative sum of reward를 계산해서 뉴럴 네트워크가 근사하게 한다. 이러한 근사 방식은 TD의 경우에서도 사용될 수 있다.
챕터 9 의 나머지 파트에서는 다양한 Linear methods, 이에 대한 feature construction 방식들로 Fourier basis, coarse coding, tile coding, Radial Basis Functions, 인공신경망 및 다양한 function approximation 방법들에 대해 소개한다.
챕터 10은 Control with approximation을 다룬다. 4~6챕터에서 나왔던 control method들 또한 function approximation을 적용할 수 있다. 아래는 function approximation이 적용된 sarsa 알고리즘이다. 기존 tabular한 경우와 approximation여부를 제외하고는 거의 동일한 것을 볼 수 있다.
p198, sutton and barto, Episodic Semi-gradient Sarsa
챕터 11 은 Off-policy Methods with Approximation으로, 위 챕터 10은 on-policy의 경우이다. On-policy의 경우는 policy를 따라 탐색하고 그 정보를 동일한 policy에 업데이트 하는데 off-policy의 경우 target policy와 behavior policy가 따로 존재하여 업데이트 시 추가적인 어려움이 생긴다. 이러한 어려움을 importance sampling의 개념을 적용해 풀거나, 아니면 아예 이러한 어려움을 겪지 않아도 되는 방법을 사용하여 푼다고 한다.
챕터 12 는 Eligibility Traces로 TD와 MC의 특성, 한쪽은 짧고 한쪽은 너무 긴 특성을 서로 상호보완하는 형태로 계산할 수 있게 둘을 unify하는 방법이다.
챕터 12 는 Eligibility Traces로 TD와 MC의 특성, 한쪽은 짧고 한쪽은 너무 긴 특성을 서로 상호보완하는 형태로 계산할 수 있게 둘을 unify하는 방법이다.
챕터 13 은 Policy Gradient Methods로, GPI의 형태로 iterative하게 value function 및 policy 업데이트를 반복하는 형태가 아니라 parameterized policy(뉴럴 네트워크로 표현되는 policy)자체를 직접 업데이트하는 방법이다. 그러기 위해서 parameterized policy의 성능을 표현하고 이에 대한 변화량을 구해 파라미터를 업데이트 하는 방식을 사용한다.
Parameterized policy를 따라서 시작 state부터 episode 끝까지 움직인다면 얻어질 거라 기대되는 값이 곧 policy의 성능일 것이기에 이를 나타내는 function J 를 설정하고 J에 직접 미분을 때리고 식을 정리해 변화량을 나타내는 식을 구한다. (이 과정은 Policy gradient theorem으로 proof된다). 아래 식은 구한 변화량에 대한 식을 적용해서 파라미터를 업데이트하는 식이다.
Parameterized policy를 따라서 시작 state부터 episode 끝까지 움직인다면 얻어질 거라 기대되는 값이 곧 policy의 성능일 것이기에 이를 나타내는 function J 를 설정하고 J에 직접 미분을 때리고 식을 정리해 변화량을 나타내는 식을 구한다. (이 과정은 Policy gradient theorem으로 proof된다). 아래 식은 구한 변화량에 대한 식을 적용해서 파라미터를 업데이트하는 식이다.
알파값 오른쪽이 function J 의 변화량이며 parameter들은 gradient ascent 방식으로 업데이트된다.
p271, sutton and barto, REINFORCE
(ln으로 묶어서 표현되었기에 모양이 조금 달라보이지만 동일하다)
이러한 REINFORCE 알고리즘은 1992년에 Ronald J. Williams교수가 발표했다. 논문 제목은 Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning 이다. 그 때는 뉴럴 네트워크를 효과적으로 학습시키기 어려웠던 탓에 관련 연구가 비주류였다고 하는데 그 때문에 connectionist라 특별히 언급했던게 아닌가 싶다. 그 이후 책의 저자인 sutton교수가 1999년에 이론을 추가로 정리하기도 했다. 아래는 관련 논문들의 링크이다.
https://link.springer.com/article/10.1007/BF00992696
https://proceedings.neurips.cc/paper/1999/file/464d828b85b0bed98e80ade0a5c43b0f-Paper.pdf
그 이후 REINFORCE알고리즘은 2016년이 되어 알파고의 이론적 기반으로 사용되면서 실제로 세상에 나오게 되었다. 참 기가 막힌 사람들이라는 생각이 들었다. 천재들은 수십년을 앞서가는 듯 하다.
챕터 13.5 는 Actor-Critic Methods로, REINFORCE가 parameterized policy만 활용했던 것과 달리 parameterized된 state-value function도 함께 활용하는 방식이다. REINFORCE의 G는 monte carlo하게 샘플링된 리턴들을 가지고 계산되었지만 actor-critic의 경우는 TD와 같은 방식으로 식이 구성한다.
챕터 13의 이후 파트에서는 Continuing problem, continuous action등에 대응하는 방식들을 소개한다. 앞선 파트의 내용들은 continuing하지 않고 episode환경에서 정의되는 방식이며 action space또한 한정되어 있는 경우이다. Policy의 성능을 나타내는 function J를 average rate of reward per time step의 관점에서 정의하는 방법을 사용하여 continuing한 경우에 대응할 수 있고, action들의 확률분포를 Gaussian분포에 기반해서 모델링하여 continuous action의 경우에 대응할 수 있다.
댓글
댓글 쓰기