OpenAI Spinning Up 번역] Part 2: 강화학습 알고리즘 종류

Welcome to Spinning Up in Deep RL!

원본은 Part 2: Kinds of RL Algorithms

• OpenAI Spinning Up 번역] Part 1: 강화학습 핵심 개념(Key Concepts in RL)
• OpenAI Spinning Up 번역] Part 2: 강화학습 알고리즘 종류(Kinds of RL Algorithms)
• OpenAI Spinning Up 번역] Part 3: 정책 최적화 소개(Intro to Policy Optimization)

Table of Contents

• Part 2: Kinds of RL Algorithms
  • A Taxonomy of RL Algorithms
  • Links to Algorithms in Taxonomy

이제까지 강화학습 용어와 표기법에 대한 기본을 익혔으니, 이제 좀 더 다양한 것들을 다룰 것입니다. 현대 강화학습 알고리즘들과 알고리즘을 설계하면서 생기는 trade-off 같은 것들을 말이죠.

A Taxonomy of RL Algorithms

철저하게 다 나열한 것은 아니지만 유용하게 분류된 현대 강화학습 알고리즘들입니다. 논문 인용은 맨 아래에 있습니다.

이번 절에서는 한 가지를 포기하고 시작하고자 합니다. 현대 강화학습 알고리즘들을 정확하게 포괄적으로 그려내는 것은 매우 어렵습니다. 트리 구조로 알고리즘 모듈성을 잘 표현하는 게 쉽지 않기 때문이죠. 또, 적절하게 소화할 수 있도록 한페이지에 다 담아내기 위해서 꽤 많은 고급 자료를 생략을 해야합니다. (exploration, transfer learning, meta learning 등) 즉, 우리의 목표는

• 무엇을, 어떻게 학습해야 하는지에 대한 심층 강화학습 알고리즘들의 가장 기초적인 설계 부분을 집중 조명하기 위해서,
• 이러한 설계 과정에서 생기는 trade-off를 경험하게 하기 위해서,
• 그리고 이러한 과정에서 몇몇 유명한 현대 알고리즘을 사용해볼 수 있게 하기 위해서

Model-Free vs Model-Based RL

강화학습 알고리즘에서 가장 중요한 분기점 중 하나는 에이전트가 환경의 모델(model)에 접근하거나 학습하는지에 대한 의문입니다. 환경의 모델은 상태 전이와 보상을 예측하는 것을 말합니다.

모델을 가지면 좋은점이 미리 앞부분을 생각하고, 가능한 선택의 범위에서 무엇이 일어날지 보고, 거기서 나온 선택 사항 중에서 선택하도록 해서 에이전트가 계획을 세울 수 있게 한다는 점입니다. 에이전트는 학습된 정책을 향해 계획한 결과를 내게됩니다. 이러한 방법으로 특히 유명한 것이 바로 AlphaZero입니다. 이 방법을 사용하게 되면 모델이 없는 방법보다 샘플 효율에 있어서 크게 향상된 결과를 가져옵니다.

단점은 에이전트가 환경의 ground-truth 모델을 사용할 수 없다는 것입니다.만약 이러한 경우에서 에이전트가 모델을 사용하고 싶다면, 순전히 경험으로부터 배워야합니다. 하지만 이러한 경우 몇 가지 문제가 있죠. 그 중 가장 큰 문제는 에이전트에 의한 모델의 편향(bias)으로, 학습된 모델에 대하여 에이전트는 잘 수행하겠지만, 실제 환경에서는 차선으로 (또는 이상하게) 행동할 수 있습니다. 그래서 모델을 학습 하는 것은 근본적으로 어려워서 많은 노력(수많은 시간과 계산을 투자해서)해도 실패로 돌아갈 수 있습니다.

모델을 사용하는 알고리즘은 model-based 방법이라 불리고, 이를 사용하지 않는 방법은 model-free. model-free 방법은 모델을 사용하여 생기는 샘플 효율에서의 잠재적인 이득은 얻을 수 없지만, 구현이나 튜닝에 있어서 쉬운 편이다. 이 글을 작성하던 시기 (2018년 9월)에, model-free 방법은 model-based 방법보다 매우 유명하고 개발되고 테스트되고 있다.

What to Learn

강화학습에서 또 다른 중요한 분기점은 무엇을 학습하는지에 대한 의문이다. 보통 다음을 포함하고 있다.

• 정책, 확률적(stochastic)인가 결정적(deterministic)인가
• 행동 가치함수 (Q-functions)
• 가치 함수
• 그리고, 또는 환경 모델

What to Learn in Model-Free RL

model-free RL의 에이전트를 나타내고 학습하는 방법은 크게 두 가지가 있다.

Policy Optimization. 이런 종류의 방법들은 $\pi_{\theta}(a|s)$과 같이 명시적으로 정책을 나타냅니다. 직접적으로 성능 목표 $J(\pi_{\theta})$로 gradient ascent를 하고, 간접적으로 $J(\pi_{\theta})$의 local 근사값을 최대화해서 파라미터를 최적화하죠. 이 최적화는 거의 항상 on-policy로 수행됩니다. 이 말은, 가장 최근의 정책에 따라 행동하면서 모인 데이터를 사용해 각각 업데이트한다는 것을 의미합니다. 또 policy optimization는 on-policy 가치 함수 $V^{\pi}(s)$에 대한 approximator $V_{\phi}(s)$를 학습하는 것도 포함되어 있어서 정책을 어떻게 업데이트하는지 알아내는데 사용됩니다.

policy optimization의 몇 가지 예를 들자면

• A2C / A3C, 직접적으로 성능을 최대화하기 위해 gradient ascent를 수행합니다.
• 그리고 PPO는 $J(\pi_{\theta})$가 업데이트 결과로 얼마나 변할지를 conservative 추정을 한 surrogate objective function을 최대화하는 방법으로 간접적으로 성능을 최대화 합니다.

Q-Learning. 이런 종류의 방법들은 최적의 행동 가치 함수, $Q^\ast(s,a)$가 되도록 approximator $Q_{\theta}(s,a)$를 학습합니다. 보통 이것들은 Bellman equation을 기반으로 한 objective function을 사용하죠. 이 최적화는 거의 항상 off-policy로 수행됩니다. 이 말은, 데이터를 얻을 때 환경을 탐험하기 위해 어떻게 선택했는지와 상관없이 학습하면서 어떤 지점에서의 모인 데이터를 사용합니다. 이에 상응하는 정책은 $Q^\ast$와 $\pi^\ast$간의 연결에 의해 얻어집니다. Q-learning 에이전트는 다음에 의해 행동이 정해집니다.

$$ a(s) = \arg \max_a Q_{\theta}(s,a). $$

Q-learning 방법의 예로는 다음과 같이 있는데요

• DQN, 심층 강화학습 분야에서 대부분 이것으로 시작하는 고전 알고리즘입니다.
• C51, return의 개대값이 $Q^\ast$인 분포를 학습하는 변형된 알고리즘입니다.

Trade-offs Between Policy Optimization and Q-Learning. policy optimization 방법들의 주된 강점은 원하는 방향으로 직접적으로 최적화한다는 의미에서 원칙적(principled)입니다. 그래서 안정적이고 신뢰성이 있습니다. 반면, Q-learning 방법들은 self-consistency 방정식을 만족하는 $Q_\theta$를 학습해서 agent의 성능을 간접적으로만 최적화합니다. 이러한 방법들에는 많은 실패가 있어서, 덜 안정적인 편이죠. 하지만 Q-learning 방법은 잘 동작한다면 대체로 더 많은 샘플 효율이 이루어진다는 장점이 있습니다. 왜냐하면 데이터를 policy optimization 기술보다 더 효과적으로 재활용하기 때문이죠.

Interpolating Between Policy Optimization and Q-learning 우연히도(Serendipitously), policy optimization과 Q-learning은 서로 양립할 수 없습니다. (그리고 어떤 조건에서는 같은(Equivalence) 경우도 있다고 합니다.) 그리고 이 두 개 사이에서 존재하는 알고리즘들도 있습니다. 이 스펙트럼 속에서 존재하는 알고리즘은 양측의 강약을 조심스럽게 조절(trade-off)할 수 있습니다. 예는 다음과 같습니다.

• DDPG, deterministic policy와 Q-function을 서로 발전시켜 동시에 학습시킵니다.
• SAC, 확률적인 정책(stochastic policy), entropy regularization, 그리고 그 외 안정적인 학습을 위한 트릭들을 사용해 표준 벤치마크에서 DDPG보다 더 높은 점수를 얻은 변형 형태입니다.

[1] Q-learning이 어떻게 그리고 왜 실패했는지에 대한 자세한 설명은 1) Tsitsiklis and van Roy의 고전 논문, 2) (좀 더 최근인) Szepesvari의 리뷰(section 4.3.2에 있음) 그리고 3) Sutton과 Barto의 chapter 11, 특히 11.3(function approximation, bootstrapping, 그리고 off-policy data의 "the deadly triad" 모두 value-learning 알고리즘에서 불안정하게 만드는 요인들임)에서 찾아보면 될 것 같습니다.

What to Learn in Model-Based RL

model-free RL과는 다르게, model-based RL을 정의하기 쉬운 방법이 많지 않습니다. 모델을 사용하는 것과는 다른 방법들이 많이 있거든요. 예를 들어볼건데, 이 리스트가 잘 정리한 것은 아닙니다. 각 경우 모델은 주어지거나 학습될 수도 있습니다.

Background: Pure Planning. 가장 기본적인 방법은 절대 명시적으로 정책을 나타내지 않고, 대신에 model-predictive control (MPC) 같이 행동을 선택하는 pure planning 기술을 사용합니다. MPC에서 에이전트가 환경을 관찰(observe)할 때마다, 에이전트는 모델에 관하여 어떤 것이 최적인지 계산합니다. 이 때 plan은 현재 이후 일정한 시간마다 취한 모든 행동에 대해 알려줍니다. (계산 범위를 벗어난 미래 보상들은 학습된 가치를 사용해서 planning 알고리즘으로 고려될 수도 있습니다.) 에이전트는 plan의 첫번째 행동을 실행하고 즉시 나머지 plan들을 버립니다. 그리고 환경과 상호작용할 준비를 할 때마다 새로운 plan을 계산하여 planning 계산 범위을 원하는 기간보다 짧게하여 행동하는 것을 막습니다.

• MBMF 심층강화학습에서 표준 벤치마킹으로 학습된 환경 모델로 MPC를 탐색(explore)합니다.

Expert Iteration. pure planning을 똑바로 후속 조치는 정책 $\pi_{\theta}(a|s)$의 명시적인 표현을 사용하고 학습하는 것이 포함되어 있습니다. 에이전트는 (Monte Carlo Tree Search 같은) planning 알고리즘을 사용하여, 현재 정책에서 샘플링된 plan에 대한 행동 후보를 만듭니다. planning 알고리즘은 정책만으로 만들어낸 행동보다 더 좋은 행동을 만들어 내서, 결국 정책에 비해 상대적으로 "전문가(expert)"입니다. 정책은 나중에 계획 알고리즘의 결과물과 유사한 행동을 생성하도록 업데이트됩니다.

• Exlt 알고리즘은 Hex를 플레이하기 위해 deep neural network를 학습하는데 이 방법을 사용합니다.
• AlphaZero는 이 방법의 다른 예시입니다.

Data Augmentation for Model-Free Methods. model-free RL 알고리즘을 정책이나 Q-function을 학습하는 데 사용하되, 에이전트를 업데이트 하는데 가상 경험으로 실제 경험을 늘리거나, 에이전트 업데이트를 위해 가상 경험만 사용하세요.

• 가상 경험으로 실제 경험을 늘리는 예는 MBVE를 보시면 됩니다.
• 에이전트를 학습하기 위한 순수 가상 경험을 사용하는 예시로 World Models를 보시면 됩니다. 이것은 "꿈속에서 학습하기(training in the dream)"라고 불립니다

Embdding Plannings Loops into Policies. 또다른 방법은 (complete plan이 정책의 부가 정보가 되도록 하기 위해) 서브루틴으로서 정책을 직접 palnning procedure에 넣는 한편, 어떤 표준 model-free 알고리즘으로 정책의 출력을 학습시킵니다. 중요한 개념은 이 프레임워크에서 정책은 어떻게 그리고 언제 plan을 사용할 지 선택하도록 학습할 수 있다는 것입니다. 이 방법은 모델이 문제가 덜 편향되도록 해줍니다. 왜냐하면 모델이 어떤 상태에서 planning이 안 좋았다면 정책은 단순히 무시하도록 학습하면 되기 때문이죠.

• 상상력이 깃든 에이전트(agents being endowed with this style of imagination.) 예시는 I2A을 보시면 됩니다.

Links to Algorithms in Taxonomy

[2] A2C / A3C (Asynchronous Advantage Actor-Critic): Mnih et al, 2016

[3] PPO (Proximal Policy Optimization): Schulman et al, 2017

[4] TRPO (Trust Region Policy Optimization): Schulman et al, 2015

[5] DDPG (Deep Deterministic Policy Gradient): Lillicrap et al, 2015

[6] TD3 (Twin Delayed DDPG): Fujimoto et al, 2018

[7] SAC (Soft Actor-Critic): Haarnoja et al, 2018

[8] DQN (Deep Q-Networks): Mnih et al, 2013

[9] C51 (Categorical 51-Atom DQN): Bellemare et al, 2017

[10] QR-DQN (Quantile Regression DQN): Dabney et al, 2017

[11] HER (Hindsight Experience Replay): Andrychowicz et al, 2017

[12] World Models: Ha and Schmidhuber, 2018

[13] I2A (Imagination-Augmented Agents): Weber et al, 2017

[14] MBMF (Model-Based RL with Model-Free Fine-Tuning): Nagabandi et al, 2017

[15] MBVE (Model-Based Value Expansion): Feinberg et al, 2018

[16] AlphaZero: Silver et al, 2017