이 챕터부터는 강화학습에서의 함수 근사(function approximation)에 대해 배우기 시작합니다. 이제까지는 가치 함수를 테이블 형식인 \(v_{\pi}(s)\)으로 나타냈지만, 본 챕터부터는 가중치(weight) 벡터 w를 사용하는 파라미터화(parameterized)된 함수 형식인 \(\hat{v}(s, w)\)로 표기합니다. 이 함수는 선형 함수일 수도 있고, 딥러닝의 artificial neural network일 수도 있으며, 그 외의 다른 함수일 수도 있습니다. 이렇게 파라미터화된 함수 형식으로 가치 함수를 표기하게 되면, 학습이 진행될 때 개별적인 \(v_{\pi}(s)\)값을 배우는 것이 아니라 파라미터인 가중치 벡터 w를 배우게 되고, 그렇게 되면 실제로 방문하지 않은 상태 s에 대해서도 파라미터 w를 통한 일반화가 가능해지게 됩니다. 이 방식은 또한, 모든 상태 정보에 접근성을 가지고 있지 못하는 partially observable 문제의 경우에도 적용 가능합니다.

9.1 가치 함수 근사(Value-function Approximation)

이제까지 다룬 prediction 방법들은 모두 어떤 상태(state)의 가치 함수값 v(s)를 어떠한 타겟으로 업데이트하는 식으로 이루어졌습니다. 예를 들어, Monte Carlo 방법은 \(S_t \rightarrow G_t\)을 타겟으로, TD(0)는 \(S_t \rightarrow R_{t+1} + \gamma \hat{v}(S_{t+1}, w_t)\)을 타겟으로, n-step TD는 \(S_t \rightarrow G_{t:t+n}\)을 타겟으로 업데이트를 하였습니다. 가치 함수 근사란 이 업데이트 방식에 머신러닝의 지도학습(supervised learning) 개념을 적용하여, 인풋 \(S_t\)가 주어지면 해당되는 타겟을 아웃풋하는 것을 말합니다. 여기서 각각의 업데이트는 일반적인 머신러닝에서 개별적인 training example로 볼 수 있고, 그렇게 프레임을 하게 되면 머신러닝의 대부분의 알고리즘을 사용할 수 있습니다.

그러나 모든 머신러닝 알고리즘이 강화학습의 근사 함수로 적합한 것은 아닙니다. 한 번에 전체 training data가 주어지는 지도학습과는 달리 강화학습에서는 데이터를 점진적으로 얻을 수 있기 때문에, 점진적으로 인풋되는 데이터를 효율적으로 사용해서 학습이 가능한 알고리즘을 필요로 합니다. 또한 타겟값이 고정된 지도학습과 달리 강화학습에서의 타겟은 고정되지 않기(nonstationary) 때문에, 이 부분을 잘 다루는 알고리즘이 우위를 가집니다.

9.2 The Prediction Objective\((\bar{VE})\)

Tabular case에서의 prediction 문제에서는 목표 함수(objective function)를 설정할 필요가 없었는데, 가치함수가 결국은 진실된 값에 수렴해 갔기 때문입니다. 그러나 근사 함수를 사용할 경우 모든 가능한 상태(state)의 값을 완벽하게 피팅하는 것이 불가능하므로 목표 함수가 필요합니다. 머신러닝에서와 비슷하게, Mean Squared Value Error를 사용할 수 있습니다.

여기서 \(\mu(s)\)는 각 상태(state)에 대해 우리가 얼마나 중요시하는지를 나타내는 변수입니다. 주로 에이전트가 해당 상태 s에서 얼마나 많은 시간을 보내는지의 값이 사용되는데, on-policy 하에서 학습될 경우 이는 on-policy distribution이라 부릅니다.

만약 문제가 continuing task일 경우 어떤 정책 \(\pi\) 하에서 on-policy distribution \(\mu\)는 stationary distribution이지만, episodic task일 경우 각 에피소드의 시작 상태(initial state)에 따라 바뀔 수 있습니다. 그럴 경우, \(\mu(s)\)값은 아래와 같은 순서로 계산됩니다.

먼저, \(\eta\)값은 해당 상태(state)의 기대 방문 횟수(expected number of visits)입니다. h(s)는 에피소드의 초기 상태가 s일 확률을 표기하며, \(\bar{s}\)는 이전 상태입니다.

그렇게 계산된 \(\eta(s)\)값을 위와 같이 normalize하여 \(\mu(s)\)값으로 사용합니다. 위는 할인율 \(\gamma\)이 1일 경우이고, 1보다 작을 경우 첫번째 \(\eta\) 계산 식의 우변의 두번째 항에 \(\gamma\)를 곱해주면 됩니다.

\(\bar{VE}\)의 global optimum을 찾을 수 있다면 이상적이겠지만, 이는 선형 함수와 같은 간단한 근사 함수 등에서 가끔 가능할 뿐이고 decision tree나 neural network 같은 대다수의 알고리즘에서는 local optimum을 찾을 수 있을 뿐입니다. 그래서 optimum이나 optimum에서 특정한 bound 내로 수렴(converge)한다는 보장은 없으며, 어떤 알고리즘들은 오히려 극한에서 diverge하는 경우도 있습니다. 일단 이 챕터의 나머지 부분에서는 gradient-descent 방법을 이용한 선형 근사 함수를 살펴 봅니다.

9.3 Stochastic-gradient and Semi-gradient Methods

이제 stochastic gradient descent(SGD)를 사용하는 알고리즘 그룹에 대해 살펴봅니다. SGD는 함수 근사에서 가장 많이 사용되는 방법 중 하나며 online reinforcement learning에 알맞습니다. Gradient-descent 방법에서 weight vector는 고정된 개수의 real valued component를 가진 column vector이며, 근사되는 가치 함수 \(\hat{v}(s, w)\)는 모든 s에 대해 미분가능한 w의 함수입니다.

SGD에서는 매 step마다 다음과 같이 \(\bar{VE}\)를 줄이는 방향으로 weight vector w에 대한 업데이트가 진행됩니다.

여기서 그라디언트 표시 \(\nabla\)는 아래와 같이 편미분의 벡터를 말합니다.

미분값의 벡터 버전인 이 그라디언트를 사용해서 오차를 줄이기 때문에 gradient descent라고 불리며, stochastic이라고 불리는 이유는, 매 업데이트마다 하나의 샘플을 사용해서 업데이트하기 때문에 많은 업데이트 후에는 평균적으로 오차가 줄지만 하나하나의 step에서는 샘플이 어떤가에 따라 오차가 커지기도 작아지기도 하기 때문입니다. 그렇기 때문에 learning rate인 \(\alpha\)은 충분히 작아야 하고, 섹션 2.7 (본 요약에서는 챕터 6.2)에서 나오는 \(\alpha\)의 두 가지 stochastic approximation condition을 만족하면 local optimum에 수렴하는 것이 보장됩니다.

만약 타겟이 실제 가치값인 \(v_{\pi}(S_t)\)가 아니라 무작위 값이나 bootstrap한 값 등의 근사값 \(U_t\)일 경우, 이 \(U_t\)값을 그대로 그 자리에 넣어서 근사할 수 있습니다. \(U_t\)값이 비편향 추정치(unbiased estimate)이고 \(\alpha\)가 앞서 말한 조건을 충족할 경우, local optimum으로 수렴하는 게 보장됩니다.

아래는 Monte Carlo의 타겟인 \(G_t\)를 사용한 SGD 방법입니다.

그런데 여기서 Monte Carlo의 타겟은 비편향 추정치이지만, bootstrap한 추정치의 경우, 타겟 자체가 현재 w값에 영향을 받아 편향(bias)이 생깁니다.

그러면 위의 식에서, 타겟이 \(w_t\)에 독립(independent)이 아니기 때문에, 실제의 gradient가 아니게 됩니다. 실제 gradient의 일부만 포함하는 gradient가 되기 때문에 semi-gradient method라고 불립니다. Semi-gradient method는 gradient method만큼 안정적으로 수렴되지는 않지만, 선형 함수의 경우를 비롯해 몇몇 주요한 경우에 나름 괜찮게 수렴을 합니다. 또한 semi-gradient method는 훨씬 더 속도가 빠른 편이며, 에피소드가 끝날 때까지 기다리기보다는 실시간(online)으로 연속적(continual)인 업데이트가 가능해서 선호되는 편입니다. 아래는 semi-gradient TD(0) 알고리즘의 pseudocode입니다.

State aggregation은 함수 근사를 일반화하는 단순한 형태인데, 여러 상태(state)들을 그룹으로 묶어 그룹별로 weight vector의 값 하나를 배정하는 것입니다. 그라디언트 벡터값에서 현재 업데이트되고 있는 상태 그룹의 요소만 1이고 나머지는 0이 됩니다. State aggregation에 대한 예는 페이지 203의 Example 9.1을 참조 바랍니다.

9.4 Linear Methods

근사함수 중 가장 중요한 스페셜 케이스는 선형 함수입니다.

여기서 벡터 x(s)는 상태(state)를 표현하는 feature vector이고, 가중치 벡터 w와 선형으로 곱해져서 가치함수 v가 계산됩니다. 이 경우 그라디언트는 단순히 x(s)가 됩니다.

그리고 SGD 업데이트는 아래와 같이 간단한 형태를 가집니다. 선형 함수는 최적점(optimum)이 하나밖에 없기 때문에, \(\alpha\)값이 수렴 조건만 충족한다면 무조건 global optimum으로 수렴하는 것이 보장됩니다.

반면, Semi-gradient TD(0)의 경우 선형 함수를 쓰면 수렴은 하지만 global optimum이 아닌 local optimum 근처로 수렴됩니다. 매 스탭 t에서의 업데이트를 풀어쓰면 아래가 되는데,

여기서 편의를 위해 \(x_t = x(S_t)\)로 축약해 표기해 놓았습니다. 만약 시스템이 안정된 상태(steady state)에 도달하게 되면, 어떤 주어진 \(w_t\)에 대해 \(w_{t+1}\)의 기대값은 아래와 같이 표기할 수 있습니다.

이를 통해, 우리는 만일 이 시스템이 수렴한다면, \(w_{TD}\)로 표기되는 weight vector로 수렴함을 알 수 있습니다.

이 \(w_{TD}\)를 TD fixed point라고 부르고 선형함수를 사용하는 linear semi-gradient TD(0)는 이 포인트로 수렴합니다. 이 과정을 증명하고 도출하는 자세한 과정은 페이지 206의 Proof of Convergence of Linear TD(0)를 참조하기 바랍니다.

TD fixed point에서의 \(\bar{VE}\)는, 가능한 \(\bar{VE}\)의 최저값에 비교해 아래와 같이 bound됩니다.

\(\gamma\)가 1에 가까울 경우가 많기 때문에 이 bound는 굉장히 커져서 TD method의 asymptotic performance의 loss가 꽤 커질 수 있지만, 이 전 챕터들에서 커버했듯이 MC method에 비해 TD method는 variance가 작다는 장점이 있습니다. 따라서 어느 방법이 더 좋은가는 문제에 따라 달려있다고 할 수 있습니다.

위의 bound와 비슷한 조건들이 다른 알고리즘들에도 적용이 되는데, 여기서 중요한 것은 on-policy distribution을 따라 상태(state)들이 업데이트 되는 경우에 그렇다는 것입니다. 다른 distribution으로 업데이트 된다면, bootstrapping 방법의 경우 수렴하지 않고 무한대로 diverge할 수 있습니다.

챕터 7에서 나온 tabular n-step TD 알고리즘 또한 semi-gradient function approximation으로 연장될 수 있는데, pseudocode는 아래와 같습니다.

9.5 Feature Construction for Linear Methods

선형 방법들은 수렴이 보장된다는 점도 있지만 데이터와 계산의 효율면에서도 매우 좋습니다. 하지만 이는 상태(state)들이 어떤 식으로 feature로 represent되느냐에 많이 달려 있습니다. Feature는 해당 분야의 도메인 지식을 알고리즘에 추가할 수 있는 중요한 수단입니다. Feature를 선형으로 사용하는 큰 단점 중 하나는 feature간의 상호작용을 고려하지 않는다는 것이고, 이를 가능케 하는 여러 방법 또한 알아보도록 하겠습니다.

9.5.1 Polynomials

Feature들을 다항으로 표현하는 것은 다른 방식에 비해 성능이 좋지는 않지만 가장 심플하고 기초적인 방식입니다. 예를 들어서 어떤 상태 s에 관한 정보를 표현하는 숫자 \(s_1\)와 \(s_2\)가 있다고 해 봅시다. \(x(s) = (s_1, s_2)^T\)로 표현할 수도 있지만 \(x(s) = (s_1, s_2, s_1 s_2)^T\)로 표현하거나 혹은 더 고차원의 feature를 사용해서 \(x(s) = (s_1, s_2, s_1 s_2, s_1^2, s_2^2)^T\) 등으로 표현할 수 있습니다. 더 고차원의 feature를 사용할수록 더 복잡한 함수를 표현할 수 있지만, 항의 개수가 기하급수적으로 늘어나므로 prior belief를 이용하거나 automatic selection method를 사용할 필요가 있습니다.

9.5.2 Fourier Basis

Sine과 cosine 함수를 이용하는 Fourier basis로 feature를 만들기도 하며, 일반적으로 Polynomial basis에 비해서 성능이 좋습니다. 어떤 상태 s의 observation이 \(s_1, s_2, ..., s_k)^T\)라고 하면, Fourier cosine basis는,

\(x_i(s) = cos(\pi s^T c^i)\)

로 표현할 수 있으며, c값에 따라 아래처럼 값들이 변화합니다. Fourier basis에 대한 더 자세한 설명은 페이지 211을 참조 바랍니다.

9.5.3 Coarse Coding

어떤 문제에서 상태(state)의 표현이 2차원에서 이루어진다고 가정할 때, 아래와 같은 원들을 feature로 사용할 수 있습니다. 만약 상태 s값이 해당 원 안에 있으면 그 원의 feature는 1, 원 밖에 있으면 0의 값을 가지는 binary feature를 사용하는 방식을 coarse coding이라고 합니다.

원의 크기가 작으면 각 업데이트가 여러 feature에 일반화(generalize)되는 것이 적고, 크기가 크면 많습니다. 일반화가 많이 된다는 것은 다시 말해서 어떤 training example이 주어졌을 때 그와 관련된 weight vector w의 요소들이 업데이트되면, 더 많은 다른 상태(state)들에 영향을 미치게 된다는 것입니다. 아래의 세번째 그림처럼 차원(dimension)별로 일반화의 정도를 다르게 할 수도 있습니다.

하지만 아래에서 보는 바와 같이, 일반화하는 과정에서는 원의 사이즈가 영향이 있지만, 극한에서(asymptotic) 수렴하는 것에는 큰 영향을 미치지 않습니다. 극한에서 더 중요한 것은 원의 개수입니다.

9.5.4 Tile Coding

Tile coding은 coarse coding의 한 종류로, 다차원의 연속 공간에 유연하게 적용되면서 계산도 효율적인 방법입니다.

위의 그림처럼 공간을 사각으로 나누는데, 만약 이러한 tiling을 하나만 사용한다면 앞서 나온 state aggregation과 동일하게 됩니다. 같은 사각형 안에 있는 상태(state)끼리만 일반화가 진행됩니다. 그런데 오른쪽 그림처럼 여러 개의 tiling을 사용하게 되면, 그러한 단절을 해결해서 좀더 부드럽게 업데이트 값을 퍼트릴 수 있게 됩니다.

이 방법에서는 어떤 state에 대해 어떤 특정 시점에 active한(값이 1인) feature의 개수가 모든 state에 대해 동일하다는 장점이 있습니다. 이로 인해 learning rate \(\alpha\) 직관적으로 설정할 수 있습니다. 만약 n이 tiling의 개수일 때 \(\alpha = \frac{1}{n}\)으로 두면, 정확히 one-trial learning이 됩니다. 예를 들자면, 이전 추정치가 \(\hat{v}(s, w_t)\)이고 training example이 \(s \rightarrow v\)라고 한다면, \(\alpha = \frac{1}{n}\)일 경우 한 번의 업데이트로 바로 이전 추정치가 v로 업데이트 되어 버립니다. 일반적으로 우리는 이보다는 느리게 업데이트를 진행하길 원하는데, \(\alpha = \frac{1}{10n}\)으로 설정하면 업데이트 한 번에 1/10씩 v를 향해 가서 10번만에 v값으로 업데이트가 되는 것입니다. Tile coding은 0 혹은 1의 값만 가지는 binary feature vector를 사용하기 때문에 계산에서도 효율적입니다.

어떤 상태(state)가 업데이트될 때, 이 상태와 tile이 겹치는 상태들 또한 함께 업데이트가 되며(generalization), 그 영향은 겹치는 tile 개수와 비례합니다. 따라서 Tiling들을 어떻게 겹치느냐도 generalization에 영향을 줍니다. 그 외 자세한 사항은 페이지 217을 참조 바랍니다. (이 섹션의 여러 가지 feature 추출 방식들은 요약한 형태로 읽는 것은 크게 얻는 것이 없어서 어느 정도 생략합니다)

9.5.5 Radial Basis Functions

Coarse coding은 0 혹은 1의 binary feature인데, RBF는 이를 일반화하여 0에서 1 사이의 실수값을 가지게 합니다.

RBF 중 가장 일반적으로 쓰이는 것은 위의 Gaussian 형태인데, c는 center state, \(\sigma\)는 feature의 넓이입니다.

위는 Euclidean distance metric을 사용한 예입니다. RBF가 가지는 장점은 연속적으로 부드럽고 미분가능한 근사함수를 준다는 것에 있습니다. 하지만 현업에서 큰 고려사항이 되지는 않고, 계산량이 많이 필요한 부분은 RBF의 단점입니다.

9.7 Nonlinear Function Approximation: Aritifical Neural Network

인공신경망은 비선형 함수 근사(nonlinear function approximation)에 널리 쓰입니다. 이 섹션에서는 딥러닝에 대한 소소한 설명, Dropout, Batch Normalization, Convolutional Network 등에 대해 나오는데, 강화학습을 공부하시는 분이면 딥러닝은 이미 공부하셨다고 생각해서 본 섹션 요약은 생략합니다. 이미 공부하신 분이면 어차피 효용이 없고, 공부를 아직 안하신 분이면 요약을 본다고 해서 알기가 힘들기 때문입니다. 딥러닝 기초가 필요하신 분께는 coursera.org에서 Andrew Ng 교수님의 딥러닝 수업을 추천드립니다.