The Backward View of TD ( )
앞서 forward 관점은 이론적인 접근이고,
backward 관점은 알고리즘의 구현하는 측면에서 본 것이다.
eligibility trace
e(s) 라는 변수가 알고리즘에 사용되는데, 이 것의 이름이 eligibility trace 이다.
각 상태 마다 할당 되고, 각 상태의 적합도로 볼 수 있다.
특히, 현재의 episode 의 상태들의 적합도로 볼 수 있다.
매 단계 마다, 적합도는 가 곱해져 결국 값이 작아진다.
는 이제 까지 보아온 discount factor 이고
는 forward 관점에서 설명한 이다
visited state's eligibility
알고리즘이 수행되면서 실행하는 episode 에서,
방문한 상태의 적합도는 항상 1 증가 하게 한다.
이를 책에서는 다음과 같은 식으로 표현했다.
실제 알고리즘에서는, 방문했으면, 먼저 1 을 증가 시키고
다음에 적합도를 감소시키다.
TD - error
TD(0) 에서 보아온 TD-error 를 사용한다.
그리고, 바로 기대값을 갱신하지 않고 약간 뒤에 한다.
알고리즘과 각 줄의 의미
책에 나온 알고리즘은 아래와 같다.
초기화
e(s) 는 0 으로 모두 초기화 된다.
V(s) 는 임의로 ( ? arbitrary ) 초기화 된다.
TD-error 구하기
현재 상태의 TD-error (증분) 을 계산한다.
다음에 나올 순환문 때문에 ,
episode 의 이 전 단계의 상태들에 대한 TD-error 로도 사용 된다.
episode 와 관련없는 상태는 변화가 없다.
방문하면 적합도 1 증가
현재 방문했기 때문에 적합성을 무조건 1 올린다.
즉, 방문한 상태만 적합성을 높인다.
모든 상태 순환
For all s:
모든 상태에 대해서 순환하면서, udpate 하고, 적합도를 줄인다.
update 할 때는 현재 방문한 상태만 하지 않는다.
이전에 방문한 episode 의 상태도 update 한다.
왜냐하면 , 모든 상태를 순환하기 때문이다.
순환하면서 update ( backup )
TD-error 로 기대값을 update ( backup) 한다.
episode 와 관련 없는 상태는 적합도가 0 이므로, update 되지 않는다.
전에 방문했던 상태의 update ( backup)
모든 상태들을 순환하기 때문에,
현 episode 의 이전 단계의 상태도 처리하게 된다.
이전 단계의 상태의 적합도는,
이전에 방문했을 때 1 증가 했고, 약간 줄어들었지만 0 은 아니다.
따라서 현재의 TD-error 로 이전 상태의 기대값도 backup(update) 된다.
마치, n-step reward 를 구현한 듯 하다.
순환하면서 적합도 감소시키기
무조건 매번 적합도를 줄인다.
알고리즘의 의미
forward 관점은 시작 상태에서 이론적으로 분석한 것이고,
backwarod 관점은 실제 알고리즘에서는 현 상태에서 이전 상태들을 update 한다.
방문한 상태의 적합도가 무조건 1 증가하고,
'이 전' 적합도는 모두 0 이다.
결국 TD(0) 가 된다.
discount factor 만 남게 된다.
이경우 왜 MC 가 되는지 아직 모름
TD(1)
= 1 이면 , TD(1) 이라고 한다.
이 TD(1) 은 MC 를 일반화한 것으로 볼 수 있고,
또한 아래와 같이 MC 보다 적용성이 더 높다.
- discounted factor 를 사용할 수 있고,
- continuing task, 즉, episode 가 없는 경우에도 사용 가능
- on-line 으로 동작한다. ( MC 는 episode 가 종료된 후 배운다 )