[RL] Feature Construction for Linear Methods

(해당 포스트는 Coursera의 Prediction and Control with Function Approximation의 강의 요약본입니다)
 - 관련된 책 내용
  : 9.4 - Linear Methods
  : 9.5.3 - Coarse Coding
  : 9.5.4 - Tile Coding
  : 9.7 - Non-linear Function Approximation : ANN

 이전 포스트에서 설명한 Linear Function Approximation은 일반적으로 표로 표현된 value function을 어느 유사한 function으로 근사함으로써 효율성을 가져오자는 취지에서 나온 것이고, 보통 이 function을 조절하는데 weight vector \(\mathbb{w}\)를 사용한다. 그래서 이에 대한 결과는 이 weight vector와 현재 state에 대한 value를 표현한 feature \(\mathbb{x}\)의 dot product 형태로 표현된다.

$$ v_{\pi}(s) \approx \hat{v}(s, \mathbb{w}) = \mathbb{w}^{T} \mathbb{x}(s)  $$

 이때 feature vector는 이전 function approximation이전에 나왔던 표에서 한칸 한칸을 표현을 표현한 것이다. 강의에서는 이해를 돕기 위해서 다음과 같이 도식화시켰다.

 

그림 1. Binary Representation of feature vector

 

 만약 예시와 같이 agent가 특정 칸에 있는 state를 표현하고자 한다면, 해당 칸에 있는 경우는 1로 표현하고 나머지 칸은 0으로 표현하는 것이다. 그래서 왼쪽 윗칸에 있으면 [1, 0, 0, 0], 그 다음칸은 [0, 1, 0, 0], ... 이런식으로 말이다. 이런식으로 binary one-hot  feature vector의 형태(한번에 한칸만 1로 표기된 vector)로 표현할 수 있게 된다. 결국 기존의 쓰는 표 방식도 말이 표를 쓰는 value function인 것이지 실제로는 이 포스트에서 다루고 있는 linear function approximation의 특수 케이스라고도 볼 수 있다. 

 물론 이 방법은 우리가 구하고자 하는 목적에 부합하지 않는다. 만약 위와 같이 간단하게 표현되는 방식이 아니라 표를 구성하는 칸이 많아진다면? 아니면 agent가 경험하는 state가 연속성(continuous)을 띈다면? 이럴 경우 표도 커질 것이고, 매번 이 표를 update하는 것도 무리가 될 것이다. 그래서 tabular 방식에서 이를 극복하기 위한 방법으로 소개되었던 것이 state aggregation, 즉 여러개의 state를 또 다른 state로 묶어서 처리하자는 것이었다.

 

그림 2. Agent in Pond

 

예를 들어서 위와 같이 Agent가 위와 같은 연못에 놓여 있는 상황을 가정할 때, 이 agent가 연못의 특정 영역에 있을 때에 대한 value function을 표로 처리하기는 어려웠다. 그런데 만약에

 

그림 3. Agent in Pond with State Aggregation

 

 위와 같이 연못을 크게 나눠서 따져 본다면, 우리가 처리해야 할 state의 수도 적어질 것이고, 이에 따라서 feature vector도 binary representation이 가능할 것이다. 물론 이게 정확한 value function이라고 할 수는 없겠지만, 적어도 Function Approximation을 통해서 대략적으로 현재의 value function을 근사하면서, 이를 효율적으로 policy update에 활용할 수 있는 방법이 생긴 것이다. 처음에는 state aggregation할 때도 같은 모양의 칸으로 나누고, 서로 겹치는 구역도 없게끔 제약들이 있었는데, 이런 제약들을 풀면서 나온 방법이 Coarse Coding과 Tile Coding이란 방법이다. 
(아마 시스템쪽 공부한 사람이라면 Coarse Grain / Fine Grain System이란 용어를 들어봤을텐데 그 용어 뜻 그대로 뭔가 덩어리 단위로 구분하는 개념을 Coarse Grain, 잘게 쪼개서 구분하는 개념을 Fine Grain이라고 표현하고, 보통 이런 구분형식을 Granularity라고 한다.)

 

그림 4. Coarse Coding

 

 Coarse Coding은 위와 같이 특정 도형의 형태로 state들을 다시 표현한 것이다.(여기서 특정 도형이란 원이나 타원, 사각형 등 다양한 모양을 말한다. 위의 그림에서는 이해를 위해 원으로 표현되었다.) 여기에서 state들은 서로 겹쳐도 되는데, 유의 사항은 이런 도형으로 기존의 state들이 모두 표현되어야 한다는 점이다. 다시 말해서 빈칸이 있으면 안된다는 것이다. 

 이런 특성을 활용해서 agent가 속해있는 state를 앞에서 소개한 binary representation 형식으로 표현한다. 그러면 이전과 같이 one-hot의 형태로는 표현되지는 않겠지만, 이와 유사하게 feature vector가 표현될 것이다.

 

그림 5. Feature Vector with Coarse Coding

 

 위의 예시에서는 agent가 속해 있는 원이 가운데의 원과 오른쪽 하단의 원이므로 해당 칸들만 1로 표현되고, 나머지 칸은 0으로 표시되었다. 이런 특성은 애초에 Coarse Coding을 적용할 때부터 빈칸이 생기지 않도록 만들었기 때문에 agent가 어떠한 칸에 있어도 feature vector로 표현할 수 있고, 근접한 state들끼리도 유사한 특성을 나타낼 수 있도록 할 수 있다. 또한 지금 예시가 2차원으로 표현되어 있지만, 이를 확정시켜서 고차원의 state에 대해서도 적용할 수 있다. 한번 위와 같은 원이 아닌, 구의 형태를 가진 value function을 생각해보면 똑같은 개념을 적용할 수 있을 것이다.

 누차 말하지만 Coarse Coding의 제약은 빈칸이 생기지 않게끔 하는 것이다. 이 환경을 설계하는 사람 마음대로 모양도 변경할 수 있고, 원의 갯수나 크기도 마음대로 변경할 수 있다. 아래 그림처럼 원을 조금더 촘촘하게 표현할 수도 있는 것이다.

 

그림 6. Broadness of generalization

 

  그럼 좀전에 나왔던 그림과 바로 위의 그림간의 차이는 무엇일까?

 

그림 7. Broadness of generalization

 agent가 특정 state에 위치해 있을 때, 해당 state에서의 value를 표기한 feature vector가 달라질 것이다. 그림상으로도 차이가 나타나지만, 이렇게 하면 이전 포스트에서 소개했던 generalization 관점에서도 차이가 발생하게 된다. 잠깐 돌이켜보면 value function을 표현하는데 있어 generalization과 discrimination간의 trade-off가 있는데, 우리가 지향하는 바는 generalization도 잘되면서 discrimination도 잘되는 것이다. 위의 그림 중 왼쪽과 같이 서로 겹치는 부분이 적게 되면, 그만큼 feature vector로 표기할 수 있는 내용이 커지기 때문에 generalization이 잘 되지는 않을 것이고, 오른쪽 그림은 그 반대 상황이 될 것이다.

그림 8. Coarse Coding with vertically elongated ellipses

 아니면 위와 같이 굳이 원이 아닌 타원의 형태로 generalization을 추구하는 coarse coding을 구현할 수 있다. 이는 전적으로 이 환경을 개발하는 사람 마음이다.

 앞에서 Generalization과 함께 Discrimination에 대해서도 잠깐 언급했었는데, 우리가 알고있는 discrimination은 두개의 서로 다른 state에 대한 value function을 얼만큼 차이를 둘수 있는지, 혹은 차별을 둘 수 있는지를 판단하는 요소이다. state aggregation을 통해서 state가 많이 적어졌다면, 그만큼 state간의 구분이 적어졌기 빼문에 discrimination 성향이 작을 것이고, 위의 예시로 놓고 본다면 agent가 같은 원(혹은 타원)내에 있을 경우는 동일한 state로 구분하게 된다. 이때 도형들간에 겹치는 부분이 발생할텐데, 이 영역이 바로 discrimination의 level 정도를 나타내는 척도가 된다. 쉽게 설명하자면, 만약 겹치는 도형이 3개라면, 주변 state의 변화에 따라서 겹치는 영역에 따른 value도 같이 변하게 될 것이고, 그만큼 이웃 state들간의 상관관계가 발생하게 되는 것이다. 그래서 같은 색을 띄는 부분은 같은 value를 가지게 될 것이고, 이 말을 다시 정리하면 같은 색을 띄는 부분은 같은 feature vector를 공유하게 된다는 것으로 표현할 수 있게 된다. 물론 이런 겹치는 영역이 많아지고, 작아질수록 Coarse Grain에서 Fine Grain으로 넘어가는 과정이므로 그만큼 discrimination이 잘 될 것이다.

 결국 위의 내용을 통해 정리할 수 있는 것은 이렇게 도형의 크기, 갯수, 모양, 도형간의 겹치는 영역 자체가 generalization과 discrimination에 영향을 준다는 것이다.

 Tile Coding은 위와 같은 Coarse Coding을 큰 사각형(Tile)으로 하겠다는 것이다. 이 Tile을 여러개 사용해서 Generalization과 Discrimination을 효율적으로 구현하겠다는 것이 목적이다. 

그림 9. Single Tile Coding

 위의 경우는 하나의 tile로 표현한 것인데, 이 경우는 앞에서 소개한 원을 이용한 Coarse Coding과 유사하다. 차이는 바로 여러개의 tile로 썼을 때이다.

그림 10. Multi Tile Coding

여러 개의 tile을 쓰게 되면 위와 같이 overlap되는 영역이 많이 생기면서 agent가 닿는 영역을 세밀하게 표현할 수 있어 discrimination입장에서 좋아지게 된다. 더구나 앞의 coarse coding의 overlap 영역이 뭔가 불규칙한 반면에 tile coding의 overlap 영역은 위와 같이 사각형 형태로 되어 있어 계산하기도 좋아지게 된다. 물론 Coarse Coding과 마찬가지로 사각형의 형태만 유지할 뿐 사각형의 크기나 모양(정사각, 직각 등)은 변화시키면서 Generalization 효과를 극대화시킬 수 있다.

 Tile Coding의 효과는 단순히 State Aggregation에만 그치는 것이 아니라, 연산량 입장에서도 효율적이다. 보다시피 Tile들이 일종의 격자를 형성하고 있기 때문에, 정수 인덱스만 활용해도 해당 state가 어떤 위치에 있는지를 쉽게 판단할 수 있다. 물론 현재 환경의 state에 대한 차원이 늘어날수록 (i.e. 관찰하는 변수가 많아질수록) Tile Coding으로 해당 state를 표현하는데 필요한 tile도 기하급수적으로 늘어나는 점은 인지해야 할 부분이다.

그러면 이렇게 좋은 Tile Coding을 앞에서 다룬 Linear TD에서는 어떻게 적용할 수 있을까? 잠깐 복습하자면 Linear TD는 value function을 일종의 linear function으로 근사하고 생각하자는 것이다. 식으로 표현하면 다음과 같다.$$ v_{\pi}(s) \approx \hat{v}(s, \mathbb{w}) = \mathbb{w}^{T} \mathbb{x}(s)  $$위의 식은 복잡한 행렬곱으로 되어 있긴 하지만, 사실 \(\mathbb{x}(s)\)가 원하는 state의 cell만 1이고, 나머지는 0인 vector이기 때문에 행렬곱을 해도 결국은 원하는 state의 value만 뽑게끔 되어 있다. 이렇게 표현한 형식을 sparse binary representation이라고 한다. (사실 feature vector가 0과 1로만 이뤄진 binary 형태이기도 하다). 그래서 원래의 행렬곱은 연산량이 복잡하지만, 이렇게 binary feature vector에 대한 것은 결국 특정 weight에 대한 덧셈만 하면 되기 때문에 연산량이 크지 않다.

그림 11. example of tile coding

간단한 예시로 위와 같이 연못위의 물고기를 4개의 칸으로 구성된 tile 2개로 표현한다고 가정해보자. 참고로 이 때의 Linear TD의 weight vector는 다음과 같다.

$$ \mathbb{w} =  \begin{bmatrix} 0.0 \\ 1.5 \\ 1.1 \\ 0.2 \\ 0.5 \\ -0.3 \\ 1.3 \\ -0.7 \end{bmatrix} $$

그러면 현재 물고기는 1번 cell과 4번 cell이 중첩되는 구간에 놓여져 있다. 그러면 feature vector도 1번, 4번 cell에 해당 것과 표현하면 되고, 이에 대한 value function도 다음과 같이 표현된다.

$$ v_{\pi}(s) = \mathbb{w}^T \mathbb{x}(s) = \begin{bmatrix} 0.0 & 1.5 & 1.1 & 0.2 & 0.5 & -0.3 & 1.3 & -0.7 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} = 2 $$

앞에서 다룬 바와 같이 Value function을 표현하는 방법이 State Aggregation도 있고, Tile Coding도 있는데, 어떤 부분이 어떻게 좋을까? 가령 1000개의 state로 구성된 환경을 State Aggregation으로 표현하면 20개의 state씩 50개의 group으로 묶어서 볼 수 있다. 그런데 Tile Coding을 쓰게 되면, 위의 그림에서도 보다시피 tile끼리 약간의 overlap이 발생하고, 부족한 부분을 채우기 때문에 50개 이상의 tile이 필요하다. 물론 두 방법 다 raw state를 쓰는 기본 방식보다는 generalization 측면에서 이점이 있고, 특히 Tile coding같은 경우는 overlap되는 부분을 통해서도 state를 조금 더 세부화해서 표현할 수 있기 때문에 discrimination측면에서는 단순 State Aggregation보다는 좋은 성능을 낼 수 있다.