[RL] Overview

RL은 ML(Machine Learning)의 한 종류로 agent가 어떤 environment에서 어떤 action을 했을 때, 그것이 올바른 action인지를 나중에 판단하여 reward를 받는 과정을 반복하여 스스로 학습을 하는 방법입니다.

결국, RL은 순차적으로 action을 계속해서 결정해야 하는 문제를 푸는 것이라 할 수 있고, MDP는 이런 문제를 수학적으로 표현한 것입니다.

Policy는 모든 state에서 agent가 해야 할 action을 결정합니다. Agent가 RL을 통해 학습해야 할 것은 여러 정책 중 optimal policy입니다. Optimal policy는 각 state에서 단 하나의 action만을 선택합니다. 하지만, 학습 시에는 하나의 action을 선택하기 보다는 확률적으로 여러 action을 선택할 수 있도록 하여 최적 policy를 찾을 수 있도록 해야합니다.

MDP (Markov Decision Process)

RL은 MDP에 학습의 개념을 넣은 것이라 볼 수 있으므로 이 MDP에 대한 이해가 중요합니다.

Markov Assumption

현재 상태는 바로 이전의 상태에만 영향을 받는다고 가정하는 것입니다.

Markov Process

Markov Assumption을 만족하는 일련의 연속적인 상태입니다.

Markov Process는 S, P로 구성됩니다.

MDP

Markov Process를 기반으로 한 의사 결정 model입니다.

MDP는 S, A, P, R, 𝛄로 구성됩니다.

Agent는 action의 주체이며, agent가 어떤 state에서 어떤 action을 할지를 결정하는 것을 policy라고 합니다.

Bellman Equation

Ballman Equation은 현재 state의 State Value Function과 다음 state의 State Value Function의 관계식 입니다.

Bellman Expectation Equation과 Bellman Optimality Equation이 있습니다.

Bellman Expectation Equation은 특정 policy를 따라갔을 때, State Value Function과 Action Value Function 사이의 관계식 입니다.

Bellman Optimality Equation은 최적의 Value Function을 얻게 하는 optimal policy를 따랐을 때의 State Value Function과 Action Value Function 사이의 관계식 입니다. 

State Value Function

어떤 state에서 policy를 따랐을 때 받을 것이라 예상되는 reward의 합을 반환합니다.

다시 말하면, agent가 어떤 action을 수행하면서 state가 변하고 이 때 보상을 받게 되는데, 시간에 따라 할인된 reward들의 누적합의 기댓값으로 value를 구합니다.

Action Value Function

어떤 state에서 action을 수행했을 때 얻게될 총 reward의 기댓값 즉, value를 반환합니다.

Bellman Expectation Equation

Bellman Expectation Equation으로 State Value Function과 Action Value Function을 기대값으로 표현할 수 있습니다.

기댓값은 재귀적으로 풀 수 있습니다.

Bellman Optimality Equation

최적 value는 가장 큰 reward를 받을 수 있는 policy를 따랐을 때 얻는 value를 뜻합니다.

DP (Dynamic Programming)

Bellman Equation을 이용해 MDP로 정의된 문제를 계산으로 푸는 방법입니다.

DP는 Policy Iteration과 Value Iteration으로 이루어져 있습니다.

Bellman Expectation Equation을 푸는 것이 Policy Iteration이며, Bellman Optimality Equation을 푸는 것이 Value Iteration입니다.

DP는 P와 R을 미리 알고 있어야 하고 state가 유한해야 가능합니다. 따라서 현실 문제에는 적용하기 어렵습니다.

Policy Iteration

Policy Iteration에서는 State Value Function을 반복적으로 갱신합니다.

같은 value를 갖는 next state가 있으면 동일한 확률을 부여해 가장 높은 value를 갖는 state로 이동하게 합니다.

어떤 policy가 있을 때, Policy Evaluation을 통해 얼마나 좋은 policy인지 평가하고, 그 평가를 기준으로 Policy Improvement를 합니다.

State Value Function을 근거로 Policy Evaluation을 하고, 주로 greedy 방법으로 Policy Improvement를 합니다.

Value Iteration

Policy Iteration에서는 next state의 value를 policy 함수의 확률과 곱해 모두 더했지만, Value Iteration에서는 greedy하게 가장 큰 next value를 선택합니다.

Policy Iteration에서는 State Value Function을 update하고 이후에 policy를 update했지만, Value Iteration에서는 policy를 update하는 과정이 없습니다. Value Iteration에서는 현재 policy가 최적이라고 가정하고 reward의 최대값을 취합니다.

Bellman Optimality Equation과 유사한 형태입니다.

RL (Reinforcement Learning)

MDP에서는 P와 R을 model이라고 하므로, 이것을 알고 있는 경우는 model-based라고 하고 모르는 경우는 model-free라고 합니다.

RL 문제는 주로 model-free environment와 무한 개의 state를 갖는다는 특징을 갖고 있습니다.

Prediction & Control

RL은 model-free이기 때문에 State Value Function의 값을 predict합니다. 그리고 이 prediction이 정확해지도록 control합니다. 이 과정을 반복하는 것이 RL입니다.

Prediction은 agent가 주어진 policy에 따라 environment과의 소통을 통해 State Value Function을 학습시키는 것입니다.

RL에서는 모든 state에 대해 value를 판단할 수 없기 때문에 sampling을 합니다.

Control은 prediction을 통해 학습한 Value Function을 기반으로 policy를 학습하는 것입니다.

Prediction에는 대표적으로 Monte-Carlo Prediction과 Temporal-Difference Prediction이 있습니다.

Control에는 대표적으로 SARSA와 Q-Learning이 있습니다.

Bootstrap

Next state에 대한 value로 현재 state의 value를 prediction하는 방법입니다.

RL에서 terminal state까지의 state transition이 이뤄진 것을 episode라고 합니다.

Bootstrap을 사용하면 episode가 진행되는 동안에 State Value Function을 update할 수 있습니다.

On-Policy & Off-Policy

On-Policy는 action을 결정하는 policy와 학습할 policy가 같은 RL을 의미하고, Off-Policy는 서로 다른 RL을 의미합니다.

즉, On-Policy RL은 경험을 쌓아도 policy가 update되면 이 경험을 학습에 사용할 수가 없으므로, 데이터 효율 관점에서 Off-Policy가 더 낫다고 할 수 있습니다.

Exploitation & Exploration

Exploitation은 현재 알고 있는 한 가장 최적의 action을 선택하는 것을 의미합니다. 즉, greedy하게 action을 선택한다고 할 수 있습니다.

Exploration은 다양한 경험을 위해 아무 action이나 해보는 것을 의미합니다.

RL Methods

MC (Monte-Carlo Learning)

MC Prediction에서는 sampling을 통해 State Value Function을 학습해 나갑니다.

이전의 State Value Function과 새로운 reward와의 차이를 더해줌으로 State Value Function을 update 합니다.

이 차이를 오차라고 하고, 오차에 곱해지는 값을 learning rate로 생각합니다.

MC Prediction에서 사용하는 총 획득 보상 G는 episode가 끝나야 알 수 있기 때문에 episode 종료 시점에서 State Value Function을 갱신할 수 있습니다.

MC Control은 State Value Function대신 Action Value Function을 사용합니다.

Action Value Function의 value가 높은 action을 선택하고 특정한 확률로 exploration을 진행할 수 있습니다.

TD (Temporal-Difference Learning)

TD Prediction에서는 episode가 끝나야 update가 가능했던 MC와 달리, time step마다 Value Function을 update할 수 있습니다.

또한, TD는 DP와 마찬가지로 Bootstrap을 사용한다고 할 수 있습니다.

On-Policy TD Control을 SARSA라 하고, Off-Policy TD Control을 Q-Learning이라고 합니다.

SARSA

하나의 sample이 (현재 S, 현재 A, R, next S, next A)로 구성되어 SARSA라고 부릅니다.

Action Value Function을 사용하고, action을 결정할 때 임의의 확률로 exploration을 합니다.

Next state에 대한 action을 알고 있어야 하기 때문에, action을 결정하는 policy와 학습할 policy를 분리할 수 없어서 On-Policy 방식입니다.

Q-function을 업데이트하기 위해 Bellman Expectation Equation을 사용하여 Policy Iteration으로 풉니다.

Q-Learning & DQN (Deep Q-Network)

SARSA를 Off-Policy 방식으로 변형해 발전시킨 방식입니다.

Next state에서 가잘 큰 Q값을 이용해 Action Value Function을 update합니다.

Action을 선택할 때는 Q값이 높은 action을 선택하면서도 충분히 exploration을 합니다.

보통 exploration은 학습 초기에는 많이 하고, 갈수록 적게하는 방법을 사용합니다.

Q-function을 업데이트하기 위해 Bellman Optimality Equation을 사용하여 Value Iteration으로 풉니다.

Q-Learning은 SARSA의 문제였던 탐험과 optimal policy 학습의 문제를 policy를 분리시키고, action은 ε-greedy policy로 선택하고, Bellman Optimality Equation을 이용해 업데이트 함으로써 해결합니다.

Action Value Function으로 DNN(Deep Neural Network)을 사용하면 DQN입니다.

PG (Policy Gradient)

PG는 classification 문제를 푸는 RL로 볼 수 있습니다.

바꿔 말하면 어떤 state에서 어떤 action을 선택하는 것이 가장 좋을지를 판단하는 것입니다.

PG는 action들의 확률을 학습합니다.

AC, A2C, A3C는 PG의 변형이라고 볼 수 있습니다.

AC (Actor-Critic)

Q-Learning이나 PG는 단일 신경망을 이용한 RL임에 반해, AC는 Q-Learning과 PG의 hybrid 방식의 RL이라고 할 수 있습니다.

Actor는 PG를 사용해 action을 결정합니다. 즉, policy 신경망을 학습합니다.

Critic은 선택한 action을 criticism하기 위해 Q-Learning을 사용합니다. 즉, Action Value Function 신경망을 학습합니다.

AC는 Actor와 Critic이 효율성을 위해 신경망을 공유하며 RL을 수행합니다.

이렇게 하면 high variance 문제를 피할 수 있습니다.

A2C (Advantage Actor-Critic)

AC에서 expectation을 advantage로 사용하는 방법입니다.

Advantage는 Action Value에서 State Value를 뺀 값입니다.

A2C에서는 Critic을 advantage로 학습합니다. 이렇게 하면 어떤 state에서 수행한 action이 얼마나 좋은지 뿐만 아니라 얼마나 더 좋아지는지를 학습할 수 있습니다.

A3C (Asynchronous Advantage Actor-Critic)

A2C에 asynchronous 개념을 추가한 방법으로 Google Deepmind에서 발표한 RL 방법입니다.

A3C에서는 agent가 여러 개의 environment에서 동시에 action을 수행하고 공유 신경망을 학습합니다. 이렇게 여러 environment에서 동시에 학습하기 때문에 asynchronous라고 부릅니다.

Summary

	MDP	DP	MC	TD SARSA	Q-L	DQN	PG	AC	A2C	A3C
Model-based	O	O
Model-free			O	O	O	O
Bootstrap		O		O	O	O		O	O	O
Exploration			O	O	O	O	O	O	O	O
On-Policy			O	O
Off-Policy					O	O	O	O	O	O
Value-Based			O	O	O	O		O	O	O
Policy-based							O	O	O	O
DNN						O	O	O	O	O
Advantage									O	O
Asynchronous										O