○ 한국과학기술원 / 김기응(개방형 에너지 클라우드 플랫폼 연구단)
<연속 행동 공간에서 가치 기울기를 이용한 효율적인 몬테카를로 트리 탐색 알고리즘 개발>
- 주요내용 : 유한한 행동 샘플 집합의 기울기(gradient) 기반 미세 조정(fine-tuning) 기능을 추가한 몬테카를로 트리 탐색(Monte-Carlo tree search) 알고리즘인 가치 기울기 UCT (VG-UCT; Value-Gradient Upper Confidence bounds for Trees) 알고리즘을 제시하였음. 이 알고리즘은 몬테카를로 트리 탐색을 통한 전역 탐색(큰 규모에서의 거친 탐색)과 기울기 상승을 통한 지역 탐색(작은 규모에서의 세밀한 탐색)을 함께 수행함. 제안된 VG-UCT 알고리즘은 실험적으로 기존의 몬테카를로 트리 탐색 기법들과 다른 강력한 알고리즘들에 대비하여 연속 행동 공간의 문제들에서 높은 성능을 보임.
- 기존 지식/기술 대비 성과의 차별성 : 기존 몬테카를로 트리 탐색 알고리즘들은 크게 두 가지 방법으로 연속 행동 공간 문제를 해결함. 점진적 확장 방법은 방문 횟수에 따라 각 노드에서 사용 가능한 행동 수를 점진적으로 증가시킴. 다른 접근법은 계층적 낙관적 최적화 방법으로, 행동 공간을 분할한 후 점차 행동의 해상도를 증가시킴. 이러한 방법들은 적당히 좋은 행동을 선택하기에는 충분한 성능을 보여줄 수 있으나, 매우 정확한 제어를 위해서는 매우 많은 수의 행동 표본이 필요할 수 있음. 반면, 기울기 기반 최적화는 정확한 지역 최적점을 찾는 데 매우 효과적이지만 신중하게 초기화하지 않으면 전역 최적점에 도달할 수 없음. 제안된 VG-UCT 알고리즘은 두 가지 알고리즘들의 장점을 갖도록 설계되어 빠르게 지역 최적점에 도달하며 전역 최적점 역시 찾을 수 있음.
- 세계최고 수준의 성과와 비교 : 네 가지 연속 제어 문제들(Pendulum, Acrobot, Reacher, Pusher)에서 각 알고리즘들을 실험하였음. 제안한 알고리즘인 VG-UCT 및 커널 사용 변형인 VG-KR-UCT은 다른 여러 몬테카를로 트리 탐색 혹은 기울기 기반 계획법 알고리즘들에 비해 높은 성능을 보임을 볼 수 있음.
- 주요 기능/사양
블랙박스 시뮬레이터 상에서 동작 가능 : 제안된 VG-UCT 알고리즘은 동역학의 자코비안이 주어지지 않더라도 이를 계산하지 않으며, 유한차분법(finite-difference method)을 이용하여 가치의 기울기를 직접 구할 수 있고, 따라서 블랙박스 시뮬레이터 상에서도 동작 가능한 알고리즘임.
정책 향상을 위해 몬테카를로 트리 탐색 활용 가능 : 기존에 알려진 바와 같이, 몬테카를로 트리 탐색 알고리즘은 트리 탐색을 이용한 궤적 수집과 해당 궤적에서 최대 우도를 가지는 정책을 얻음으로써 정책 향상을 위한 기법으로 사용될 수 있음. VG-UCT 역시 유사하게 정책 향상 기법으로 사용될 수 있으며, 해당 방식으로 사용되었을 경우 UCT 대비 높은 성능을 보임.
- 기대효과 및 향후계획 : 몬테카를로 트리 탐색 기법은 이산 행동 공간을 가지는 현실적인 문제들에 널리 활용되어 왔으나, 연속 행동 공간이 포함될 경우 그 효율성이 떨어지는 문제가 있었음. 이를 해결함으로써 더욱 많은 종류의 문제들에 효율적인 계획법의 적용이 가능할 것으로 보임. 더 나아가, 정책 네트워크와 가치 네트워크를 모두 사용하여 VG-UCT의 성능을 끌어올릴 수 있음. 가치 네트워크를 훈련시키게 된다면 현재 알고리즘의 주 병목인 블랙박스 시뮬레이터에 대한 쿼리 횟수를 감소시켜 전체적인 성능을 향상시킬 수 있을 것임.
* 논문실적 (1건)
1) Lee, Jongmin, et al. "Monte-Carlo Tree Search in Continuous Action Spaces with Value Gradients." AAAI. 2020.