Reinforcement Learning 기초 개념 (2): Algorithm Types
Reinforcement Learning algorithm은 environment model을 사용하는지, 수집한 experience를 어떻게 사용하는지, 그리고 어떤 function을 중심으로 학습하는지에 따라 여러 종류로 나눌 수 있다. 이 글에서는 Reinforcement Learning algorithm을 이해하기 위한 대표적인 분류 기준을 간략히 정리하였다.
Concept
Reinforcement Learning algorithm은 agent가 environment와 상호작용하면서 얻은 experience를 이용해 더 높은 return을 얻는 decision making strategy를 학습하는 방법이다.
Reinforcement Learning problem에서는 agent가 state $s_t$를 관측하고, action $a_t$를 선택하며, environment로부터 reward $r_t$와 next state $s_{t+1}$를 받는다. Algorithm은 이러한 interaction에서 얻은 data를 이용해 policy 또는 value function을 개선한다.
Reinforcement Learning algorithm은 대표적으로 다음 기준에 따라 분류할 수 있다.
| Classification criterion | Main question |
|---|---|
| Model-free vs Model-based | Environment model을 사용하는가 |
| On-policy vs Off-policy | 어떤 policy가 만든 data를 update에 사용하는가 |
| Policy-based vs Value-based | Policy를 직접 학습하는가, value function을 학습하는가 |
이 분류 기준들은 서로 독립적으로 사용될 수 있다. 예를 들어 어떤 algorithm은 model-free이면서 on-policy일 수 있고, 다른 algorithm은 model-free이면서 off-policy일 수 있다.
Model-free vs Model-based
Model-free와 model-based의 차이는 environment model을 사용하는지 여부에 있다.
여기서 environment model은 transition function $P(s_{t+1} \mid s_t, a_t)$ 또는 reward function $R(s_t, a_t, s_{t+1})$처럼 environment의 dynamics를 설명하는 함수를 의미한다.
Model-free Reinforcement Learning
Model-free Reinforcement Learning은 transition model $P(s_{t+1} \mid s_t, a_t)$를 직접 학습하거나 사용하지 않고, environment와의 interaction에서 얻은 experience를 이용해 policy 또는 value function을 학습하는 방법이다.
즉, agent는 action $a_t$를 선택했을 때 next state $s_{t+1}$가 어떤 방식으로 생성되는지 명시적으로 modeling하지 않는다. 대신 실제 environment에서 얻은 reward와 trajectory를 이용해 좋은 action selection strategy를 학습한다.
| Feature | Description |
|---|---|
| Environment model | 사용하지 않음 |
| Main learning target | Policy 또는 value function |
| Data source | 실제 environment interaction에서 얻은 experience |
| Advantage | 다양한 environment에 비교적 단순하게 적용 가능 |
| Limitation | 많은 interaction data가 필요할 수 있음 |
대표적인 model-free algorithm에는 Policy Gradient, Q-Learning, DQN, PPO, SAC 등이 있다.
Model-based Reinforcement Learning
Model-based Reinforcement Learning은 environment의 transition dynamics를 학습하거나 이미 주어진 environment model을 사용하는 방법이다.
Transition model은 현재 state $s_t$와 action $a_t$가 주어졌을 때 next state $s_{t+1}$가 어떻게 결정되는지를 나타낸다.
\[s_{t+1} \sim P(s_{t+1} \mid s_t, a_t)\]Model-based algorithm에서 agent는 environment model을 이용해 future trajectory를 예측할 수 있다. 즉, 실제 environment에서 action을 수행하기 전에 여러 action candidate의 결과를 simulation할 수 있다.
| Feature | Description |
|---|---|
| Environment model | 사용함 |
| Main learning target | Transition model, reward model, policy, value function |
| Data source | 실제 experience와 model-generated experience |
| Advantage | sample efficiency가 높을 수 있음 |
| Limitation | model prediction error가 누적될 수 있음 |
대표적인 model-based algorithm에는 MPC, MCTS, Dyna 계열 방법이 있다.
On-policy vs Off-policy
On-policy와 off-policy의 차이는 training data를 생성한 policy와 update되는 policy가 같은지 여부에 있다.
On-policy Reinforcement Learning
On-policy algorithm은 현재 policy $\pi$로부터 생성된 data만 사용하여 현재 policy를 update하는 방법이다.
즉, agent가 현재 사용 중인 policy로 trajectory를 수집하고, 그 trajectory를 이용해 같은 policy를 개선한다. Policy가 update되면 이전 policy로 수집한 data는 현재 policy의 data가 아니게 되므로, 많은 on-policy algorithm에서는 이전 data를 재사용하기 어렵다.
| Feature | Description |
|---|---|
| Data-generating policy | 현재 policy |
| Updated policy | 현재 policy |
| Data reuse | 제한적 |
| Advantage | data distribution과 update objective가 비교적 일치함 |
| Limitation | sample inefficient할 수 있음 |
대표적인 on-policy algorithm에는 Policy Gradient, A2C, PPO 등이 있다.
Off-policy Reinforcement Learning
Off-policy algorithm은 현재 policy와 다른 policy로부터 수집된 data도 update에 사용할 수 있는 방법이다.
여기서 data를 생성하는 policy를 behavior policy라고 하고, 학습하거나 개선하려는 policy를 target policy라고 할 수 있다. Off-policy algorithm에서는 과거에 수집한 experience를 replay buffer에 저장하고, 이를 여러 번 재사용할 수 있다.
| Feature | Description |
|---|---|
| Data-generating policy | 현재 policy 또는 과거 policy |
| Updated policy | Target policy |
| Data reuse | 가능 |
| Advantage | sample efficient할 수 있음 |
| Limitation | data distribution mismatch를 고려해야 함 |
대표적인 off-policy algorithm에는 Q-Learning, DQN, DDPG, SAC 등이 있다.
Policy-based Algorithm
Policy-based algorithm은 policy $\pi$를 직접 학습하는 방법이다. Policy는 state $s$에서 action $a$를 선택하는 함수이다.
Stochastic policy는 다음과 같이 표현할 수 있다.
\[\pi(a \mid s) = P(a_t = a \mid s_t = s)\]Policy-based algorithm에서는 parameter $\theta$를 갖는 policy $\pi_{\theta}$를 학습한다.
\[\pi_{\theta}(a \mid s) = P(a_t = a \mid s_t = s; \theta)\]이때 학습의 목표는 expected return을 크게 만드는 policy parameter $\theta$를 찾는 것이다.
\[\theta^* = \arg\max_{\theta} J(\pi_{\theta})\]Policy-based algorithm의 특징은 다음과 같다.
| Feature | Description |
|---|---|
| Main learning target | Policy $\pi_{\theta}$ |
| Action selection | Policy가 action distribution 또는 action을 직접 출력 |
| Objective | Expected return maximization |
| Advantage | discrete, continuous action space에 모두 적용 가능 |
| Limitation | gradient variance가 크고 sample inefficient할 수 있음 |
Policy-based method는 policy를 직접 optimize한다는 점에서 직관적이다. 또한 continuous action space처럼 action을 직접 선택해야 하는 문제에 자연스럽게 적용할 수 있다.
대표적인 policy-based algorithm에는 Policy Gradient 계열 방법이 있다.
Value-based Algorithm
Value-based algorithm은 policy를 직접 학습하기보다 value function을 학습하는 방법이다. 일반적으로 state value function $V^{\pi}(s)$보다 state-action value function $Q^{\pi}(s,a)$를 학습하는 경우가 많다.
State-action value function은 다음과 같이 정의된다.
\[Q^{\pi}(s,a) = \mathbb{E}_{\tau \sim \pi} \left[ \sum_{t=0}^{T} \gamma^t r_t \mid s_0 = s, a_0 = a \right]\]Value-based algorithm에서는 state $s$에서 $Q^{\pi}(s,a)$가 가장 큰 action $a$를 선택하는 방식으로 policy를 구성할 수 있다.
\[a^* = \arg\max_{a \in \mathcal{A}} Q^{\pi}(s,a)\]Value-based algorithm의 특징은 다음과 같다.
| Feature | Description |
|---|---|
| Main learning target | Value function $Q^{\pi}(s,a)$ |
| Action selection | 가장 큰 value를 갖는 action 선택 |
| Objective | Value estimate improvement |
| Advantage | sample efficient한 경우가 많음 |
| Limitation | continuous action space에서 $\arg\max$ 계산이 어려울 수 있음 |
Value-based method는 policy를 명시적으로 학습하지 않아도 value function을 통해 action을 선택할 수 있다. 따라서 action마다 expected return을 비교할 수 있는 discrete action problem에서 자주 사용된다.
대표적인 value-based algorithm에는 SARSA, Q-Learning, DQN, Double DQN 등이 있다.
Algorithm Type Overview
Reinforcement Learning algorithm의 주요 분류를 정리하면 다음과 같다.
| Classification | Type | Key idea | Example |
|---|---|---|---|
| Environment model 사용 여부 | Model-free | Environment model 없이 experience로부터 학습함 | Policy Gradient, DQN |
| Environment model 사용 여부 | Model-based | Environment model을 이용해 planning 또는 simulation을 수행함 | MPC, MCTS |
| Data 사용 방식 | On-policy | 현재 policy가 생성한 data로 현재 policy를 update함 | Policy Gradient, PPO |
| Data 사용 방식 | Off-policy | 과거 policy 또는 다른 behavior policy가 생성한 data도 재사용함 | Q-Learning, DQN |
| 학습 대상 | Policy-based | Policy를 직접 학습함 | Policy Gradient |
| 학습 대상 | Value-based | Value function을 학습함 | SARSA, Q-Learning, DQN |
Reinforcement Learning algorithm은 하나의 기준으로만 분류되지 않는다. Environment model을 사용하는지, data를 재사용하는지, policy와 value function 중 무엇을 중심으로 학습하는지에 따라 여러 속성을 동시에 가질 수 있다.
References
- OpenAI Spinning Up. Part 2: Kinds of RL Algorithms. https://spinningup.openai.com/en/latest/spinningup/rl_intro2.html
- Sutton, R. S., & Barto, A. G. Reinforcement Learning: An Introduction, 2nd edition. MIT Press.