Anderson Acceleration for Learning and Decision Systems in Partially Observable Environments

Abstract

In this thesis, we present an acceleration scheme, called Anderson acceleration (AA), for reinforcement learning (RL) algorithms. RL has been used for an agent to learn efficient decision-making strategies through its interactions with an environment. In this work, we look at the sequential decision making in environments, where the actions either have certain outcomes in which the system state is fully observable and the problem is modeled as Markov decision process (MDP), or have probabilistic out- comes in which the system state is partially observable and the problem is modeled as partially observable Markov decision process (POMDP). Since slow convergence and sample inefficiency of RL algorithms make them im- practical for complex real-world problems, we use AA for RL to speed up the computation of fixed-point problems. Because of the instability in the original AA method, we consider adaptive Anderson acceleration (A3) as a stabilized variant of AA, which contains both adaptive regularization to handle instability and safeguarding to enhance performance. We first apply A3 to value iteration using Q-functions for solving MDPs and show its convergence property. To extend the idea of A3 to model-free deep RL, we devise a simple variant of deep Q-networks (DQN). In order to solve POMDPs, we apply A3 to the fast informed bound (FIB) method, which is an approximate value iteration algorithm. We further propose a neural network architecture based on the FIB algorithm for planning under partial observability. We evaluate and analyze the performance of the proposed methods on a random MDP, the Atari benchmark and robot navigation problems.

본 논문에서는 강화 학습(RL) 알고리즘을 위해 앤더슨 가속도(AA)라고 하는 가속도 체계를 제시한다. RL은 에이전트에게 환경과의 상호작용을 통해 효율적인 의사 결정 전략을 학습하기 위해 사용되어 왔다. 본 연구에서는, 조치가 시스템 상태 를 완전히 관측할 수 있고 문제가 마르코프 의사결정 과정 (MDP)으로 모델링되는 특정 결과를 가지거나 시스템 상태를 부분적으로 관측할 수 있고 문제가 부분 관측 가능한 마르코프 의사결정 과정 (POMDP)으로 모델링되는 확률적 결과를 가지는 환경에서 순차적 의사결정을 검토한다. RL 알고리즘의 느린 수렴과 샘플 비효율성 으로 인해 복잡한 현실 문제에 실용적이지 못하기 때문에, 고정 지점 문제의 계산 속도를 높이기 위해 RL에 AA를 사용한다. 원래 AA 방법의 불안정성 때문에, 적응 형 앤더슨 가속도 (A3)를 AA의 안정화된 변형으로 간주한다. AA는 불안정을 처리 하기 위한 적응형 정기화와 성능을 향상시키기 위한 안전성을 모두 포함한다. 먼저, MDP 문제 해결을 위한 Q-기능을 활용한 반복성을 중시하고 융합성을 보여주기 위해 A3를 적용한다. A3의 아이디어를 모델 없는 딥 RL로 확장하기 위해 딥 Q- networks (DQN)의 단순한 변형을 구상한다. POMDP를 해결하기 위해 대략적인 값 반복 알고리즘인 FIB (Fast Informed Bound) 방식에 A3을 적용한다. 또한 부분적인 관찰가능성 하에서 계획하기 위한 FIB 알고리즘에 기초한 신경망 구조를 제안한다. 무작위 MDP, 아타리 벤치마크, 로봇 내비게이션 문제에 대해 제안된 방법의 성능을 평가하고 분석한다.