Reinforcement Learning 기초 개념 (1): Concept, MDP, Mathematical Formulation

Reinforcement Learning은 agent가 environment와 상호작용하면서 reward를 최대화하는 방향으로 decision making strategy를 학습하는 Machine Learning 방법이다. 이 글에서는 이후 REINFORCE algorithm을 이해하기 위해 필요한 기본 개념을 정리하였다.

Figure 1. Agent-environment interaction loop.

Concept

Reinforcement Learning은 sequential decision making problem을 다루는 학습 방법이다. 일반적인 Supervised Learning에서는 input과 label이 주어지고 model이 label을 예측하도록 학습한다. 반면 Reinforcement Learning에서는 agent가 environment 안에서 action을 선택하고, 그 결과로 reward를 받으며 policy를 개선한다.

즉, Reinforcement Learning의 핵심은 정답 label을 직접 학습하는 것이 아니라, trial-and-error를 통해 더 높은 reward를 얻는 behavior를 학습하는 데 있다.

Reinforcement Learning system은 agent와 environment로 구성된다. Environment는 현재 system의 state 정보를 제공하고, agent는 관측한 state를 바탕으로 action을 선택한다. 선택된 action은 environment에 영향을 주며, environment는 다음 state와 reward를 agent에게 제공한다.

Reinforcement Learning system은 다음 구성 요소로 표현된다.

Term	Meaning
Agent	environment 안에서 action을 선택하는 학습 주체
Environment	agent가 상호작용하는 외부 system
State	현재 environment의 상태 정보
Action	agent가 state를 보고 선택하는 행동
Reward	action 이후 environment가 agent에게 제공하는 scalar feedback
Policy	state에서 action을 선택하는 규칙 또는 함수

Agent는 현재 state를 관측하고, policy에 따라 action을 선택한다. Environment는 agent의 action을 받아 다음 state로 transition하고 reward를 반환한다. 이 과정이 하나의 time step을 구성하며, terminal state에 도달하거나 maximum time horizon에 도달할 때까지 반복된다.

Policy는 agent의 action-producing function이다. 즉, policy는 state를 입력으로 받아 어떤 action을 선택할지 결정하는 함수이다. Policy를 Deep Learning model로 근사하면 policy network라고 한다.

Reinforcement Learning problem에는 objective가 필요하다. 일반적으로 objective는 agent가 episode 동안 받는 reward의 총합 또는 expected return을 최대화하는 것으로 정의한다. Agent는 시행착오를 통해 environment와 상호작용하고, 높은 reward를 얻는 action에 대한 선호를 강화하면서 policy를 학습한다.

Reinforcement Learning Process

Reinforcement Learning의 학습 과정은 agent와 environment가 반복적으로 signal을 주고받는 feedback loop로 볼 수 있다. 이 feedback loop는 state, action, reward의 순환 구조로 표현된다.

Agent가 현재 state $s_t$를 관측한다.
Agent가 policy $\pi$에 따라 action $a_t$를 선택한다.
Environment가 action $a_t$를 받아 다음 state $s_{t+1}$로 transition한다.
Environment가 reward $r_t$를 agent에게 제공한다.
Agent는 얻은 experience를 이용해 policy 또는 value function을 update한다.

이 과정에서 environment는 state $s_t$에 대한 정보를 제공하고, agent는 이 정보를 이용해 action $a_t$를 선택한다. Action $a_t$가 수행되면 environment의 state가 변화하고, 그 결과로 next state $s_{t+1}$와 reward $r_t$가 agent에게 전달된다.

하나의 time step에서 agent와 environment가 주고받는 signal은 보통 $(s_t, a_t, r_t)$ 또는 $(s_t, a_t, r_t, s_{t+1})$ 형태로 표현한다. 이러한 tuple을 experience라고 한다.

Experience의 각 성분은 다음과 같이 해석할 수 있다.

Symbol	Meaning
$s_t$	time step $t$에서 agent가 관측한 state
$a_t$	state $s_t$에서 agent가 선택한 action
$r_t$	action $a_t$ 이후 environment가 제공한 reward
$s_{t+1}$	action 이후 transition된 next state

Experience는 Reinforcement Learning에서 data에 해당한다. Supervised Learning에서는 dataset이 학습 전에 주어지는 경우가 많지만, Reinforcement Learning에서는 agent가 environment와 직접 상호작용하면서 experience를 생성한다.

Feedback loop는 무한히 반복될 수도 있지만, 일반적으로 특정 종료 조건을 만족하면 멈춘다. 대표적인 종료 조건은 terminal state에 도달하는 경우와 maximum time step $T$에 도달하는 경우이다.

Episode는 $t=0$부터 terminal state 또는 maximum time step $T$까지의 interaction 전체를 의미한다. 즉, 하나의 episode는 agent가 environment에서 시작해 종료 조건을 만족할 때까지 얻은 experience의 sequence이다.

Trajectory는 하나의 episode 동안 발생한 experience의 연속을 의미하며, 일반적으로 $\tau$로 나타낸다.

\[\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \cdots, s_T, a_T, r_T)\]

따라서 Reinforcement Learning에서 학습은 하나의 experience만으로 끝나는 것이 아니라, 여러 episode에서 생성된 trajectory를 이용해 policy 또는 value function을 개선하는 과정으로 이해할 수 있다.

Markov Decision Process

Reinforcement Learning problem은 보통 Markov Decision Process, 즉 MDP로 정의한다. MDP는 agent가 environment와 상호작용하는 sequential decision making problem을 수학적으로 표현하는 framework이다.

MDP는 다음과 같은 tuple로 표현한다.

\[\mathcal{M} = (\mathcal{S}, \mathcal{A}, P, R)\]

각 구성 요소는 다음과 같다.

Symbol	Term	Meaning
$\mathcal{S}$	State space	가능한 모든 state의 집합
$\mathcal{A}$	Action space	가능한 모든 action의 집합
$P$	Transition function	현재 state와 action으로부터 next state가 결정되는 확률 함수
$R$	Reward function	transition 이후 reward를 계산하는 함수

State $s_t$는 time step $t$에서 agent가 관측하는 environment의 상태이다. State space $\mathcal{S}$는 가능한 모든 state의 집합을 의미한다.

Action $a_t$는 time step $t$에서 agent가 선택하는 행동이다. Action space $\mathcal{A}$는 가능한 모든 action의 집합을 의미한다.

Reward $r_t$는 agent가 action을 수행한 뒤 environment로부터 받는 scalar feedback이다. Reward function $R(s_t, a_t, s_{t+1})$는 현재 state $s_t$, action $a_t$, next state $s_{t+1}$를 이용해 reward를 계산하는 함수이다.

Transition function $P(s_{t+1} \mid s_t, a_t)$는 현재 state $s_t$와 action $a_t$가 주어졌을 때 next state $s_{t+1}$로 transition할 확률을 나타낸다.

MDP의 핵심 가정은 Markov property이다. Markov property는 next state가 과거 전체 history가 아니라 현재 state와 현재 action에 의해서만 결정된다고 가정한다.

일반적인 transition은 다음과 같이 과거 history 전체에 의존할 수 있다.

\[s_{t+1} \sim P(s_{t+1} \mid s_0, a_0, s_1, a_1, \cdots, s_t, a_t)\]

Markov property를 가정하면 transition은 다음과 같이 단순화된다.

\[s_{t+1} \sim P(s_{t+1} \mid s_t, a_t)\]

이 가정은 Reinforcement Learning problem을 다루기 쉽게 만든다. 모든 과거 state-action history를 저장하거나 modeling하지 않고, 현재 state $s_t$가 decision making에 필요한 정보를 충분히 담고 있다고 보기 때문이다.

Mathematical Formulation

Reinforcement Learning의 목표는 agent가 받는 reward의 discounted sum을 최대화하는 policy를 찾는 것이다. 이를 위해 먼저 return을 정의한다.

Return $R(\tau)$는 하나의 trajectory $\tau$에서 얻는 discounted reward의 합이다.

\[R(\tau) = \sum_{t=0}^{T} \gamma^t r_t\]

여기서 $\gamma$는 discount factor이다.

\[0 \leq \gamma \leq 1\]

Discount factor $\gamma$는 future reward를 현재 기준으로 얼마나 중요하게 볼지를 결정한다. $\gamma$가 0에 가까우면 immediate reward를 더 중요하게 보고, $\gamma$가 1에 가까우면 future reward까지 길게 고려한다.

Policy $\pi$는 state로부터 action을 선택하는 함수이다. Stochastic policy에서는 특정 state $s$에서 action $a$가 선택될 확률을 다음과 같이 표현한다.

\[\pi(a \mid s) = P(a_t = a \mid s_t = s)\]

Agent는 policy $\pi$로부터 action $a_t$를 sampling할 수 있다.

\[a_t \sim \pi(\cdot \mid s_t)\]

Reinforcement Learning의 objective는 policy $\pi$가 생성하는 trajectory의 expected return을 최대화하는 것이다.

\[J(\pi) = \mathbb{E}_{\tau \sim \pi}[R(\tau)]\]

Return의 정의를 대입하면 다음과 같다.

\[J(\pi) = \mathbb{E}_{\tau \sim \pi} \left[ \sum_{t=0}^{T} \gamma^t r_t \right]\]

따라서 Reinforcement Learning algorithm은 다음 최적화 문제를 푸는 과정으로 이해할 수 있다.

\[\pi^* = \arg\max_{\pi} J(\pi)\]

이 식에서 $\pi^*$는 expected return을 최대화하는 optimal policy를 의미한다.

Value Function

Value function은 현재 state 또는 state-action pair가 future return 관점에서 얼마나 좋은지를 평가하는 함수이다. Policy를 직접 update하는 REINFORCE를 이해할 때도 return과 value function의 개념은 중요하다.

State value function $V^{\pi}(s)$는 state $s$에서 policy $\pi$를 따른다고 가정했을 때 기대되는 return이다.

\[V^{\pi}(s) = \mathbb{E}_{\tau \sim \pi} \left[ \sum_{t=0}^{T} \gamma^t r_t \mid s_0 = s \right]\]

State-action value function $Q^{\pi}(s,a)$는 state $s$에서 action $a$를 먼저 선택한 뒤 policy $\pi$를 따른다고 가정했을 때 기대되는 return이다.

\[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]\]

$V^{\pi}(s)$는 state의 좋고 나쁨을 평가하고, $Q^{\pi}(s,a)$는 특정 state에서 특정 action을 선택하는 것이 얼마나 좋은지를 평가한다.

MDP로 정의된 Reinforcement Learning system에서 agent가 학습할 수 있는 대상은 크게 세 가지로 나눌 수 있다.

Learning target	Meaning
Policy $\pi$	state에서 action을 선택하는 함수
Value function $V^{\pi}$, $Q^{\pi}$	state 또는 state-action pair의 expected return을 추정하는 함수
Transition function $P$	action 이후 environment가 어떤 next state로 이동할지 예측하는 함수

Policy를 학습하면 agent는 state에서 어떤 action을 선택해야 하는지 직접 알 수 있다. Value function을 학습하면 agent는 future return 관점에서 state 또는 action의 가치를 평가할 수 있다. Transition function을 학습하면 agent는 실제 environment와 상호작용하지 않고도 future state를 예측할 수 있다.

Summary

Reinforcement Learning은 agent가 environment와 상호작용하면서 reward를 최대화하는 policy를 학습하는 sequential decision making framework이다.

기본 interaction은 state $s_t$, action $a_t$, reward $r_t$, next state $s_{t+1}$의 순환 구조로 표현된다.

Policy는 state에서 action을 선택하는 action-producing function이며, Deep Learning model로 근사하면 policy network가 된다.

Experience는 하나의 time step에서 얻는 $(s_t, a_t, r_t)$ 또는 $(s_t, a_t, r_t, s_{t+1})$ 형태의 signal tuple이다.

Episode는 $t=0$부터 terminal state 또는 maximum time step $T$까지의 interaction 전체를 의미한다.

Trajectory $\tau$는 하나의 episode 동안 발생한 experience의 sequence이다.

MDP는 Reinforcement Learning problem을 state space $\mathcal{S}$, action space $\mathcal{A}$, transition function $P$, reward function $R$로 정의하는 수학적 framework이다.

Markov property는 next state $s_{t+1}$가 과거 전체 history가 아니라 현재 state $s_t$와 action $a_t$에 의해 결정된다고 가정한다.

Return $R(\tau)$는 discounted reward의 합이며, Reinforcement Learning의 objective는 expected return $J(\pi)$를 최대화하는 policy $\pi$를 찾는 것이다.

Value function은 state 또는 state-action pair가 future return 관점에서 얼마나 좋은지를 평가하는 함수이다.