[RL] Tile coding

Tiling은 이산화(discretize) 시키고 싶은 공간을 partition 한다. 여기서 하나의 class는 하나의 tile이고, 하나의 Binary feature와 대응된다. 공간 상의 한 점은 하나의 tile에 대응되는 feature의 값이 1이고 나머지 feature 의 값이 0인 경우와 대응된다. 

Tiling은 같은 space에 대해 여러번 적용 시킬 수 있는데, 이는 하나의 Tiling으로 하는 것보다 space를 좀더 세밀하게 이산화 시킨다.  1번 tiling 과 다른 2번 tiling을 수행한다면,  1번 tiling의 7번 tile에 속하는 점 2개를 2번 tiling에서 서로 다른 tile에 속하도록 만들 수 있다.

하나의 Tiling에서 보다 많은 개수의 tile을 갖게 하는 것, 그리고 적은 개수의 tile이지만 여러번 Tiling을 적용하는 것 중에 어느게 효과적인 지는 모르겠다. 그러나 결국 총 feature의 수가 같다면 최종적으로 근사된 함수의 모양은 크게 다르지 않을 것이다.

모든 tiling의 tile들을 일렬로 세우고 번호를 붙였을 때, 공간상의 한 점은 자신이 매 tiling에서 속한 tile의 index들의 집합과 대응 된다. 예를 들면 1번 tiling에서 25개의 tile을, 2번 tiling에서 64개의 tile을 가진다면, 전체 tile은 1 부터 25+64 까지 index를 부여할 수 있고, 공간 상의 한 점은 2개의 index, 1~25 사이 중 하나, 26부터 25+64 중 하나의 index와 대응될 수 있다. 이 때 이 점은 두 개의 feature의 값이 1이고 나머지는 0인 어떤 feature vector와 대응된다. 이 때 알 수 있는 것은 대응되는 feature vector가 tiling의 수 만큼의 1을 가지고 나머지는 0이라는 것이다. 따라서 우리는 feature vector를 이용하여 우리가 근사하고자 하는 함수를 계산할 때 feature의 개수 대신 tiling의 수에 비례하는 연산을 수행하여 보다 빠르게 함수값을 계산할 수 있다.

공간의 크기가 클수록 전체 tile의 수가 상당히(혹은 무한히) 많을 수도 있다. 공간이 무한하지만 실제 우리가 관심을 가지는 영역은 일부분이라면 그 수를 줄일 수 있다. 예를 들어, 실수 변수 하나가 취하는 값의 범위가 제한 되어있으면 그 범위에 한하여 tiling을 수행할 수 있다. 만약 우리가 그 제한 범위를 모른다면 hashing을 사용할 수 있다. 즉, 보다 큰 범위를 가진 값(key)를  컴퓨터가 저장할 수 있는 훨씬 작은 범위의 값(data 혹은 hash)에 대응시키는 것이다. 필연적으로 hashing은 서로 다른 key값들이 동일한 data에 대응되는 것을 피할 수 없다(Collision). 이에 대해서는 여러가지 충돌 해결기법이 있다.

Tile coding 을 구현한 소프트웨어의 사용법은 아래 링크를 참고
Tile coding 에 대한 설명도 있으니 참조할 것.
http://rlai.cs.ualberta.ca/RLAI/RLtoolkit/tiles.html