[강화학습] 7. Planning and Learning with Tabular Methods

Planning and Learning with Tabular Methods

미리 말하자면 이번 포스팅이 Tabular method의 마지막 장이다.

※ Tabular method : table에 value function값을 기록할 수 있을 만큼 discrete space인 경우. 간단히 표현하면 지금까지 '쉬운 문제'에 다뤘다고 생각하면 된다..

이번 챕터에서는 model-based(≒GP)와 model-free method(≒MC, TD)의 integration에 대해서 알아보자.

RL에서 model은 state, action이 입력 됐을 때 reward와 next state을 출력하는 environment dynamics를 의미한다.

그리고 model은 distribution model이 있고 sample model이 있다.

• Distribution model : p(s', r | s, a)
  : 모든 possible한 distribution을 가지고 있다.

• Sample model
  : 모든 경우를 표현하지는 못하고, sample에 의해서 결과를 알 수 있다. (ex. Black jack)

이런 model이 만들어 내는 데이터는 simulate the environment라고 할 수 있다.

Planning & Learning

model을 input으로 받아서 policy를 출력하는 방법을 Planning이라고 한다.

그리고 중간 과정에 simulated experience를 거쳐 value function을 estimate하고 policy를 출력하는 프로세스를 state-space planning이라 부른다. 이런 문제를 풀이하는데는 DP가 대표적이다.

Learning과 Planning의 공통점은 value function을 잘 estimate한다는 점에서는 동일하다.

다만 차이점은 Planning은 model에 의해 생성되는 simulated experience를 사용하고,

Learning은 environment에 의해 생성되는 real experience를 사용한다는 것이다.

두 방식은 명확하게 구분되어 있지만 많은 아이디어 혹은 알고리즘이 두 방식을 복합해서 사용하고 있다. 대표적으로 "The Planning method based on Q-Learning"이 있다.

이 알고리즘은 one-step tabular Q-learning과 random sample from sample model의 개념을 합쳤다 해서 "random-sample one-step Q-planning"알고리즘이라 부른다.

• 2번째 줄을 확인하면 real experience를 학습하는 Q-learning때와는 달리, sample model이 만들어 내는 데이터를 활용한다.(bootstrap)

• 3번째 줄은 Q-Learning때와 똑같은데, 다른 점은 Q를 sample model을 이용해서 improve 한다는 것이다.

Dyna : Integrated Planning, Acting, and Learning

Dyna는 major function을 모두 포함하는 online planning agent이다.

위 그림을 보며 value/policy의 update를 2가지 방법으로 하는 것을 확인할 수 있다.

첫 번째는 real experience를 통한 direct RL이고,

두 번째는 real experience를 입력으로 받는 model의 planning이다.

• Planning : random sample one-step Q-learning

• Model-learning : table-based

• Direct RL method : one-step tabular Q-learning

pseudo code를 보면 좀 더 명확하게 planning-learning integration이 보인다.

• (c) observe는 실제 데이터란 뜻이며, bootstrap을 의미한다.

• (d) 과정에서 Q-learning으로 direct RL한다.

• (e) input, output이 있으니 model을 학습시킬 수 있다.

• (f) planning part에서 마치 planning 문제처럼 model의 estimate로 improve하는데, 이 때 model은 실제 데이터를 학습한 모델이다. 이 때 estimated value는 모든 action의 maximum값을 취하는 Q-planning을 활용한다.

그리고 확실히 planning과 learning을 함께 결함했을 때 optimal policy로 수렴하는 속도가 훨씬 빠른 것을 위 예제로부터 확인할 수 있다.

Prioritized Sweeping

그럼 Dyna agent의 문제점은 뭘까? 바로 Q-planning에서 state-action pair를 고를 때 random하게 고른 것이다. 

오히려 planning할 때 particular state-action pairs에 focus하는 것, 즉 priority를 주는 것이 더 효과적이다. 왜냐하면 실제로 대부분의 action-value는 0이고, goal로 가는 방향에서만 positive를 가진다. 즉, 모든 transition에 대해 update하는 것은 pointless다.하기 때문에 영향을 주는 것만 focus하자는 것이 Prioritized Sweeping의 개념이다.

그럼 어떤 state에 대해 focus할 것인지가 중요한데, 결과적으로 value가 dynamic하게 변하는 state에 focus할 수 있도록 priority를 높혀주는 것이다. 

그 구현은 자료 구조 중 하나인 priority queue를 통해 쉽게 구현할 수 있다.

(e)과정에서 value의 변화량을 감지하고, (f)에서 변화량이 일정수준 이상일 때 priority queue에 담는다.

그리고 (g)에서 priority가 높은 순서대로 pop하면서 control하는 것을 확인할 수 있다.

그리고 Dyna에 priority sweeping 개념을 적용 했을 때 좀 더 적은 update량으로 optimal에 수렴시킬 수 있음을 확인할 수 있다.