이 챕터에서는 모델을 사용하는(model-based) 강화학습과 사용하지 않는(model-free) 강화학습을 통합된 프레임 하에서 살펴보도록 하겠습니다.

8.1 Models and Planning

모델(model)이란, 에이전트가 환경(environment)이 본인의 행동(action)에 대해 어떻게 반응할지를 예측하는데 사용되는 모든 것을 말합니다. 상태(state)와 행동(action)이 주어지면, 모델은 그에 따른 다음 상태와 보상(reward)이 무엇인지를 예상합니다. 확률적인 모델(stochastic model)의 경우, 확정적인 하나의 다음 상태와 보상을 아웃풋하지 않고 여러 상태와 보상과 그에 따른 확률들을 아웃풋합니다. 모델은 아웃풋 방식에 따라 두 가지로 나뉩니다.

• Distribution model: 가능한 모든 상태와 보상과 그에 따른 확률들을 상세히 아웃풋하는 모델
• Sample model: 가능한 상태와 보상 중에서 하나를 확률에 따라 샘플링해서 아웃풋하는 모델

예를 들어 주사위의 모델이 있다고 가정할 때, distribution model은 여섯 개의 숫자에 1/6씩의 확률을 배정해서 아웃풋하고, sample model은 1/6의 확률로 추첨한 하나의 수를 아웃풋합니다. Distribution model은 더 포괄적이고 sample model을 만드는데 사용될 수도 있지만, 많은 예에서 sample model을 만들기가 훨씬 간편합니다. 모델은 경험을 시뮬레이션하는데 사용될 수 있습니다. Sample model을 이용해서 에피소드를 시뮬레이션해볼 수 있고, distribution model을 이용하면 모든 확률적으로 가능한 에피소드들의 조합을 시뮬레이션할 수 있습니다.

강화학습에서 계획(planning)이란, 모델을 입력(input)으로 받아서 정책(policy)을 도출(output)하는 계산 과정을 지칭합니다. 인공 지능 연구에서 planning을 하는 방법은 크게 두 가지가 있습니다.

• State-space planning: 이 책의 방법론도 포함하는데, 상태 공간(state space)를 검색해서 최적의 정책을 찾는 방법입니다. 에이전트의 행동들로 인해 환경은 어떠한 상태에서 다른 상태로 옮겨가며, 가치 함수(value function) 또한 상태를 기준으로 계산됩니다.
• Plan-space planning: 이 방법론에서 planning은 여러 plan들 사이에서 최적을 찾는 식으로 진행됩니다. 이 방법론은 강화학습의 포커스인 확률적 순차 결정 문제(sequential decision problem)에서 사용되기 힘들기 때문에, 이 책에서는 다루지 않습니다.

이 챕터에서 다루려고 하는 관점은, 모든 state-space planning 방법들이 어떠한 공통된 구조를 가진다는 것입니다. 모든 state-space planning 방법들은 1) 정책을 개선하기 위한 중간 과정으로써 가치 함수를 계산하며, 2) 그 가치 함수 계산 과정은 시뮬레이션된 경험에 업데이트나 backup operation 등을 적용함으로써 이루어집니다. Dynamic Programming을 포함한 모든 방법들은 아래의 프레임워크으로 설명될 수 있습니다.

Planning 과정을 이러한 프레임의 시각에서 보는 것은, learning과의 관계를 강조하는데 도움이 됩니다. Planning과 learning 두 가지의 공통점은, back-up update operation을 통해 가치 함수를 추정하는 것이고, 차이점은 전자가 시뮬레이션된 경험을 사용한다면 후자는 실제 환경에서 생성된 경험을 사용한다는 것입니다. 이 차이가 많은 다른 차이로 이어지긴 하지만, 공통적인 구조를 갖기 때문에 많은 알고리즘들이 이 두 가지 사이에서 트랜스퍼될 수 있음을 알 수 있습니다.

한 예를 들자면 위는 sample model에서 시뮬레이션된 경험을 이용하여 Q-learning을 적용한 알고리즘이며, 실제 환경 하에서 Q-learning이 최적 정책에 수렴하는 것과 마찬가지로 해당 sample model에 대한 최적 정책에 수렴을 합니다.

8.2 Dyna: Integrated Planning, Acting and Learning

Planning이 실시간(online)으로 이루어지는 경우 사용될 수 있는 간단한 알고리즘 Dyna-Q를 소개합니다. 만약 실시간으로 planning이 이루어질 경우, 실제의 경험은 1) 현재의 model을 개선하는데 쓰이기도 하고, 2) 가치 함수를 직접적으로 개선하는데 쓰이기도 합니다. 전자는 indirect RL 혹은 model-learning이라고 하고, 후자는 direct RL이라고 합니다. 아래의 도표는 이 관계를 정리한 것입니다.

두 방식은 각기 장단점이 있는데, indirect RL은 제한된 수의 경험을 더 극대화해서 사용한다는 장점이 있지만 model에서 오는 편향(bias)에 노출되고, direct RL은 그러한 편향에서 자유롭고 더 간단합니다. 이 두 방식 중 어느 것이 나은지는 갑론을박이 있어왔지만, 이 책에서는 이 두 가지의 공통점에 초점을 맞추려고 합니다. Dyna-Q 알고리즘은 이 두 가지를 모두 사용하는 알고리즘으로써, 아래의 도표에 나와 있습니다. (위의 도표와 거의 같습니다) 여기서 search control은, 모델에서 시뮬레이션된 경험의 시작 상태와 행동을 선택하는 프로세스를 말합니다. 일반적으로 Dyna-Q에서, direct RL update와 planning update에서 사용되는 알고리즘은 동일합니다. 즉, 왼쪽의 direct RL 과정과 오른쪽의 indirect RL 과정이 다른 점은 실제 경험을 사용하는지, 아니면 모델에서의 시뮬레이션된 경험을 사용하는지입니다.

개념적으로는 planning, acting, model-learning, direct RL이 모두 동시적으로 이뤄지지만, 실제 컴퓨터에서 이를 구현할 때는 순서를 정해야 합니다. 일반적으로 acting, model-learning, direct RL은 계산량이 적고, planning이 가장 계산량을 많이 차지합니다. 아래는 Dyna-Q의 pseudocode입니다.

여기서 direct RL은 (d), model-learning은 (e), planning은 (f)입니다. 만약 (e)와 (f)가 생략된다면, 위의 알고리즘은 일반적인 one-step tabular Q-learning이 됩니다. 구체적인 예시는 페이지 164의 Example 8.1을 참조바랍니다.

8.3 모델이 잘못되었을 경우

확률적인 환경에서 환경이 변화하거나 샘플이 부족해서 모델이 불완전할 경우, planning 프로세스는 최적의 정책을 찾지 못할 가능성이 높습니다. 어떤 경우, 최적이 아닌(suboptimal) 정책은 모델링 에러를 발견하고 수정하는데 쓰일 수 있는데, 보통 모델이 실제 가능한 것보다 더 낙관적으로 높은 보상(reward)을 예측하고 있을 때 그럴 경우가 많습니다.

아래는 어떠한 미로에서 오른쪽이 열려 있다가 1000 step 후에 왼쪽이 열린 것으로 바뀌는 예입니다. Dyna-Q와 조금 더 개선된, 곧 설명할 Dyna-Q+ 알고리즘은 둘다 1000 step 후에 어느 정도 헤메긴 하지만 제자리를 찾습니다.

그러나 아래의 예처럼, 원래의 통로가 열려 있는 상황에서는, 오른쪽에 더 빠른 길이 생겼음에도 Dyna-Q는 그것을 발견하지 못합니다. 이는 탐색(exploration)과 이용(exploitation) 사이의 갈등의 예입니다. Exploration은 모델을 개선하기 위해 해보지 않은 행동을 해 보는 것이고, exploitation은 이제까지 배운 모델에서 최적의 행동을 하는 것입니다. Exploitation은 현재 가장 높은 보상을 가져다주지만, 장기적으로 높은 보상을 축적하기 위해서는 단기적인 보상을 포기하고 exploration을 어느 정도 진행해야 합니다.

두번째 문제에서 개선을 하는데 성공한 Dyna-Q+은 이 exploration/exploitation 갈등을 해결하기 위해 다음의 방법을 사용합니다. 어떤 행동을 한지 오래되었을수록 환경이 변화했을 가능성이 높기 때문에 그 행동을 하는 것에 대한 추가 보상을 주는 것입니다. 예를 들어 어떤 행동을 했을 때의 보상이 r이라면, Dyna-Q+에서는 \(r+k\sqrt{t}\)를 보상으로 주는데, 여기서 k는 사용자가 조절할 수 있는 파라미터이고, t는 해당 행동을 했던 시점에서 얼마나 time step이 흘렀는지입니다.

8.4 Prioritized Sweeping

Dyna 알고리즘의 planning에서 시뮬레이션된 경험(pseudocode의 f 참조)은 무작위의 상태-행동 쌍에서 시작합니다. 하지만 많은 경우, 특히 실제 경험을 한지 얼마 되지 않아서 대부분의 상태의 가치 함수값이 0일 때, 무작위의 시작점을 잡는 것은 많은 계산을 낭비할 수가 있습니다. 예를 들어 Goal state의 보상이 1이고 나머지 state의 보상이 0인 MDP의 경우, 초기에는 goal state 근처의 가치 함수값들이 업데이트되고 점점 더 먼 곳으로 이 값이 전파되게 됩니다.

따라서 무작위 선택보다 조금 더 효율적인 방법은, 가치가 변화한 상태(state)를 기준으로 그 상태에 이르는 길에 있는 상태들을 먼저 업데이트하는 것입니다. 이를 backward focusing이라고 합니다. 하지만 어떤 상태의 변화가 이전 상태들로 역전파되는 과정에서, 업데이트할 수 있는 후보 상태들의 수가 기하급수적으로 늘어날 수 있습니다. 따라서 가치함수값이 얼마나 변화했느냐에 따라서, 많이 변화한 상태들의 이전 상태들부터 우선적으로 업데이트하는 방식을 사용할 수 있습니다.

아래는 해당 알고리즘입니다.

물론 prioritized sweeping은 하나의 방법일 뿐이며 최선은 아닙니다. 이 알고리즘의 한계는 모든 확률을 고려한 expected update를 사용함으로써, 매우 낮은 확률을 가졌음에도 변화량이 큰 케이스들 때문에 비효율적이 될 수 있다는 것입니다. 이보다는 sample update를 사용하는 방식이 더 유리할 수 있는데, sample update에서는 일어날 확률이 적은 케이스들이 update값에 반영되지 않고, 실제로 sample된 transition에 따라 더 집중적인 업데이트를 할 수 있기 때문입니다.

8.5 Expected vs Sample Updates

이 책에서 이제까지 우리는 가치 함수를 업데이트하는 것과 관련해서 여러 가지 방식을 살펴봤습니다. One-step 업데이트에만 논의를 한정지은 상황에서, 가치함수 업데이트 방식을 분류하는 방식에는 크게 세 가지 방향이 있습니다. 처음 두 가지는 1) 상태 가치함수 V를 업데이트하는지 행동 가치함수 Q를 업데이트하는지, 2) 최적의 정책에 대한 가치값을 추정하는지 아니면 재량의 정책에 대한 가치값을 추정하는지입니다. 이 두 방향에 의해 \(q_*, v_*, q_\pi, v_\pi\) 네 가지 가치 함수 중 어느 것을 사용할지가 결정됩니다.

그 다음은 3) 업데이트가 기대값에 따른 expected update인지 아니면 샘플 하나의 값에 따른 sample update인지입니다. 이 세 가지에서 8가지 조합이 나오고 그 중 7개가 아래의 구체적인 알고리즘으로 분류될 수 있습니다.

이들은 전부 planning 방법에 사용될 수 있습니다. 앞서 다룬 Dyna-Q에서는 \(q_*\) sample update를 사용하지만 \(q_*\) expected update나 \(q_\pi\)를 사용해도 되며 Dyna-AC에서는 \(v_\pi\)를 사용합니다. Expected update는 sampling error가 없지만 더 많은 계산을 필요로 해서 이것이 한계가 되는 경우가 많습니다. 더 구체적으로는, b를 branching factor, 즉 다음 가능한 상태의 개수라고 할 때, 대략적으로 b배의 계산이 필요합니다. 반면, sample update에서는 sampling error가 생깁니다.

계산량 vs 에러를 객관적으로 비교하면 어떠할지에 대해 측정한 결과가 위의 도표에 나타나 있습니다. Expected update는 sampling error가 없기 때문에 한번 계산을 다 수행하면 끝이고, 이 시점을 1b로 표기합니다. 그 계산량인 1b에 대비해서 sampling update가 얼마나 효율적으로 오차를 줄이는지를 나타내는 것이 곡선들인데, b = 2처럼 간단한 문제에서는 expected update가 요구하는 계산량이 아주 적기 때문에 그 적은 시간동안 sample update를 해도 오차를 많이 줄이지 못합니다. 하지만 b = 10000과 같이 복잡한 문제에서는 expected update를 하는 시간 1b는 엄청 길고, 그 긴 시간에 비교해서 sample update는 굉장히 단시간 하에 오차를 expected update에 근접하게 줄일 수 있습니다. 구체적 수치로 이야기하자면, 어떤 상태에 대해 그 다음 상태가 모두 동일한 확률을 가지는 b개의 상태로 이루어져 있다고 가정할 때, sample update는 에러를 각 스텝 t마다 \(\sqrt{\frac{b-1}{bt}}\)만큼씩 줄여나갑니다.

8.13 Part I 요약 (책에서는 챕터 2 - 8)

이제까지 배운 모든 방법들은 세 가지 공통 요소들을 가집니다.

• 가치 함수를 추정하려 한다는 점.
• 실제 혹은 가능한 상태 궤도(state trajectory)를 따라 가치값을 back-up한다는 점.
• 모두 generalized policy iteration (GPI)의 프레임워크, 즉 근사적인 가치함수와 근사적인 정책을 가지고 계속해서 서로에 대해 개선하려고 하는 틀을 따른다는 점.

이 방법론들을 분류하는 두 개의 큰 축은 아래에 표기되어 있습니다. 가로축은 sample update를 사용하는지 expected update를 사용하는지이고, 세로축은 bootstrap를 몇 스텝까지 하는지입니다.

이 두 개의 축 외에 또 하나 중요한 기준은 on-policy인지 off-policy인지에 대한 것인데, 전자는 현재 따르고 있는 정책에 대한 가치함수를 배우려 하고, 후자는 현재 환경에서 행동하고 있는 정책과는 별개의 정책에 대한 가치함수를 배우려 합니다.

이 외에도 방법론들을 분류하는 기준들은 다음이 있습니다.

• 행동 가치함수인지, 상태 가치함수인지, 혹은 다음 상태(afterstate) 가치함수인지
• 어떻게 exploration과 exploitation의 갈등을 해결하는지. 예를 들어 이제까지 이에 대해 배운 것 중에 가장 간단한 방법은 \(\epsilon\)-greedy 정책이 있었습니다.
• 상태들의 가치 에 대한 업데이트가 동시에 일어나는지(synchronous) 아니면 어떠한 순서에 따라 비동시적(asynchronous)으로 일어나는지.
• 환경에서의 실제 경험을 사용하는지 아니면 시뮬레이션된 경험을 사용하는지, 혹은 둘 다 사용하면 그 비율은 어떤지.
• 어떤 상태 혹은 상태-행동 쌍을 업데이트하는지. Model-free 방법들은 실제로 경험한 상태만 업데이트 가능하지만, model-based 방법에서는 재량으로 상태를 선택할 수 있습니다.
• 업데이트의 타이밍. 행동을 선택하면서 업데이트를 할지, 아니면 선택한 후에 업데이트를 할지.
• 업데이트에 대한 메모리 사용. 업데이트된 가치들이 얼마나 오래 저장되어야 하는지.

물론 이 리스트는 전체를 포괄하지도 않고 서로 상충되는 것도 아닙니다. 그리고 파트 1에서 다루지 않아서 여기 언급되지는 않았지만 매우 중요한 기준은 함수 근사(function approximation)입니다. 이에 대해서는 파트 2에서 자세하게 다룹니다.