분할 정복 몬테카를로 트리 탐색 (Divide-and-Conquer Monte Carlo Tree Search)
따끈따끈한 구글 딥마인드의 강화학습 연구논문
Title
Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning
2020.04.23 arxiv (link)
cf. 분할 정복과 몬테카를로 트리 탐색
요약
몬테카를로 계획법(planning), 몬테카를로 트리 탐색, 동적 프로그래밍을 포함해서, 순차 의사 결정을 위한 일반적인(standard) 계획법들은 암시적인 순차 계획 가정(sequential planning assumption)에 의한 제약을 받는데, 이 때 계획이 수립되는 순서는 그것이 실행되는 순서와 동일하다.
(주 _ 마지막 문장을 기억해 두는 것이 좋다)
저자들은 목표 지향(goal-directed) 강화학습 문제의 클래스에 대해 이 가정의 대안을 고려한다. 환경 전이 모델(environment transition model) 대신 불완전한 목표 지향 정책을 가정하는데, 이 로우 레벨 정책은 시작 상태부터 목표 상태까지 이어지는(guide) 하위 목표들(sub-goals)의 적절한 시퀀스로 구성된 플랜에 의해 개선될 수 있다.
저자들은 Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS, 분할 정복 몬테카를로 트리 탐색) 라는 계획 수립(planning) 알고리즘을 제안한다. DC-MCTS는 초기 작업(initial tasks)을 독립적, 재귀적으로 해결되는 더 간단한 작업들로 계층 분할하는 중간 하위 목표들(intermediate sub-goals)로 제안함으로써 최적에 근사한 플랜을 도출한다. 이 알고리즘은 이전 경험에 기초하여 새로운 작업의 적절한 분할 트리를 찾기 위해 학습된 하위 목표 제안(learned sub-goal proposal)을 비판적으로(critically) 사용하는데, 하위 목표 제안 학습을 위한 각각(different)의 전략들이 순차적 계획 수립을 일반화하는 서로 다른(different) 계획 수립 전략(planning strategies)을 유도한다.
저자들은 계획을 짜는 이러한 알고리즘의 유연성이 그리드 월드의 탐색 작업에서 향상된 결과를 내는 것을 보였다.
도입
사실 이 섹션은 원고에 추가될 마지막 섹션 중 하나였지만, 계획을 수립하는 순서가 그 계획을 실행하는 순서와 일치할 필요는 없다.
(주 _ 떡밥 하나 회수하는 딥-마인드)
순차적 의사 결정 문제(sequential decision making problems)에 대한 대부분의 일반적인 계획법들(몬테카를로 계획법, 몬테카를로 트리 탐색, 동적 프로그래밍 등)은 기본적으로 순차 계획 가정을 가지고 있다. 이러한 방법들은 처음 상태 (또는 마지막 상태)에서 시작하여 순서에 따라 (또는 역순으로) 행동을 계획한다. 그러나 이 순차적 접근은 두 가지 핵심 문제에 직면한다.
먼저, 계획 수립에 사용되는 전이 모델을 장기적으로 신뢰할 수 있어야 하는데 이는 모델이 데이터로부터 추론되어야(inferred) 할 때 달성되기 어렵다. 다음으로, 각각의 행동에 대해 신뢰 할당(credit assignment)을 하는 것이 어렵다. 예를 들어 100단계의 기간(horizon)에 걸친 계획 수립 문제에서 첫 번째 행동에 신뢰 할당을 하려면 나머지 99단계에 대한 최적의 비용을 계산해야 하는데 이는 단지 원래 문제를 푸는 것보다 아주 약간 쉬울 뿐이다.
(주 _ Credit Assignment Problem, CAP)
이 두 가지 문제를 해결하기 위해 저자들은 순차 계획 수립자(sequential planners)의 기본적인 가정의 대안을 고려한다. 이를 위하여 에이전트가 시작 상태로부터 목표 상태에 도달해야 하는 목표 지향 의사 결정 문제(goal-directed decision making problems)에 초점을 맞춘다.
환경에 대한 전이와 보상 모델(transition and reward model) 대신, 저자들은 주어진 목표 지향 정책(goal-directed policy), 즉 로우 레벨 정책(low-level policy), 그리고 어떠한 주어진 작업에 대해 그 로우 레벨 정책의 성공 가능성을 반환하는 연합 가치 오라클(associated value oracle)을 가정한다. 로우 레벨 정책은 일반적으로 최적이 아니지는 않을 것이다. 다시 말하면 현재 상태에서 멀리 떨어진 목표 상태에 확실하게 도달하기에는 너무 “근시안”적일 수도 있다.
이제 저자들은 로우 레벨 정책을 시작 지점부터 목표 지점까지 효율적으로 유도하는 적절한 하위 목표 시퀀스(sequence of sub-goals)를 통해 이를 개선하여 전체 작업의 성공 가능성을 극대화하고자 한다. 좋은 하위 목표 시퀀스를 찾음으로서 계획을 수립하는 것은, 명시적 환경 모델들을 학습하는 것을 불필요하게 만드는데, 이는 그 모델들이 로우 레벨 정책과 그 정책의 가치 함수(value functions)로 대체되기 때문이다.
하위 목표 계획 수립 문제(sub-goal planning problem)는 시작 상태로부터 도달하기 위한 첫 번째 하위 목표를 탐색하는 것으로 시작하여 다음 하위 목표에 대한 계획을 차례대로 세우는, 종래의 순차적 계획법(conventional sequential planner)으로도 여전히 해결될 수 있다. 실제로 이는 옵션 또는 하위 목표에 기반한 대부분의 계층적 강화학습에서 사용된 접근법이다. (e.g. Dayan & Hinton, 1993; Sutton et al., 1999; Vezhnevets et al., 2017)
그러나 첫 번째 하위 목표가 유용한지 평가하는 것은 여전히 나머지 플랜의 성공 가능성을 평가하는 것을 필요로 하므로 앞서 언급한 신뢰 할당 문제가 여전히 존재한다. 그 대신 전체 플랜의 “한가운데”에 있는 하위 목표의 유용성에 대해 논하는 것이 상당히 쉬울 수 있는데, 그 하위 목표가 긴 문제의 길이를 시작 지점으로부터 하위 목표로 도달하는 것과 하위 목표로부터 최종 목표로 도달하는 두 개의 하위 문제로 쪼개기 때문이다.
이러한 직관에 기초하여, 저자들은 원본 작업을 비슷한 복잡도를 갖는 두 개의 독립적인 하위 작업들로 나누는 하위 목표를 탐색한 뒤, 이 하위 작업들을 재귀적으로 해결함으로써 신뢰 할당을 매우 용이하게 하는 계획법인 분할 정복 MCTS (Divide-and-Conquer MCTS, DC-MCTS) 계획법을 제안한다. 중간 하위 목표의 공간(space)을 효율적으로 찾기 위해 DC-MCTS는 과거 탐색 결과와 에이전트 경험으로부터 학습한 유망 하위 목표 제안을 위해 휴리스틱 접근법을 사용한다.
- <Improving Goal-Directed Policies with Planning> 및 <Best-First AND/OR Planning> 두 섹션에 걸쳐서 자세한 수식 정의와 위와 같은 알고리즘 의사코드가 설명되어 있으나 본 글에서는 다루지 않았다.
실험
저자들은 그들이 제안한 DC-MCTS 알고리즘을 그리드 월드 미로(grid-world maze)의 탐색 등을 통해 평가한다. 각 계획을 실행함으로써 해결된 미로의 비율에 기반하여 DC-MCTS를 일반적인 순차적 MCTS와 비교하였다. (결과 비디오 링크)
DC-MCTS와 MCTS의 계획 수립 차이를 더 자세히 설명하기 위해, 아래 그림에서 각 방법의 예제 탐색 트리를 살펴볼 수 있다. 하늘색 노드들이 최종 계획(final plan)의 일부분으로, 일반적인 MCTS의 경우 플랜이 단일 체인인 반면, DC-MCTS의 경우 플랜이 어떻게 탐색 트리 내의 하위 트리에 분포되어 있는지에 주목하라. 첫 번째 ‘실행 가능한’ 하위 목표, 즉 로우 레벨 정책에 전달될 수 있는 첫 번째 하위 목표는 DC-MCTS의 경우 가장 왼쪽의 리프 노드이고 MCTS의 경우 루트 노드로부터 첫 번째 검은 노드이다.
논의
분할 정복 스타일 계획 수립을 가능하게 하기 위해, 저자들은 약간의 강한 가정을 두었다. 먼저 하위 목표에 기초한 계획 수립은 로우 레벨 정책의 보편적 가치 함수 오라클을 필요로 한다. 많은 경우 이는 데이터로부터 근사되어야 할 것이다. 다음으로 최소한 현재의 나이브한 단계에서는 계획자(planner)의 “행동 공간”(action space)이 근본적인 마르코프 결정 프로세스(MDP)의 전체 상태 공간이라는, 하위 목표 계획 수립상의 한계점이 남는다.
Reference
