Ch05. Markov Decision Process and Dynamic Programming (1)

Markov Decision Process (MDP)는 강화학습 모델링의 기반이다. MDP는 문제의 정의, 즉 수식의 정의에 사용되고, Dynamic Programming은 iterative하게 equation을 푸는 방법을 제시한다.

 

OpenAI Gym을 사용한 실습 내용이 궁금하다면 아래 링크를 참조하자.

 

https://github.com/JJukE/ReinforcementLearning

GitHub - JJukE/ReinforcementLearning: Reinforcement Learning Course

 

https://jjuke-brain.tistory.com/60?category=957313 

Ch04. Getting Started with OpenAI and Tensorflow (2)

 

 

목차

 

 

 

 

 

1. The Markov Chain and Markov Process

 

 

 

 

1) Markov Chain and Markov Process

 

 

 

(1) Markov Property and Markov chain

 

먼저, Markov Property(성질)이 무엇인가에 대해 알아둘 필요가 있다.

Markov property란, time step 't+1'의 미래 상황은 오직 현재 time step 't'에만 의존하고, 그 이전의 과거인 't-1', 't-2', ... 등에는 영향을 받지 않는 것을 말한다.

 

이에 따라 Markov chain이라는 말이 등장하는데, 이는 다음 상태를 예측하는 데 현재의 상태에만 의존하는 확률모델이다.

미래 상태(future state)는 과거에 독립적이고, 이러한 Markov chain은 Markov property를 엄격하게 따른다.

쉽게 말해, 't-2'는 't-1'에, 't-1'은 't'에, 't'는 't+1'에, ... 이런식으로 하나의 time step씩 영향을 주면서 chain 형태로 묶인다고 생각하면 된다.

 

예를 들어, 현재 구름이 가득 낀 상태라면, 이 다음 상태에는 비가 올 것이라는 예측을 해볼 수 있다. 이 예측은 오직 현재 상태인 구름 낀 날씨에 의해서만 일어난다. 과거에 맑았던, 바람이 불었던지는 전혀 상관이 없다.

 

 

 

(2) Transition Probability

 

Transition이란, 현재 state에서 다른 state로 넘어가는 것을 말한다.

여기서 Transition Probability라는 개념이 등장하는데, 글자 그대로, transition이 일어날 확률이다.

보통 table의 형태로 나타내며, 이를 Markov table이라고 부른다.

 

Markov table

 

위 table에서, 현재 구름이 낀 상태(current state)일 때, 다음 상태(next state)가 비가 올 확률(transition probability)은 0.6이라는 것을 알 수 있다.

 

Markov chain은 위와 같이 table로 나타내거나, 아래와 같이 state diagram으로 나타낼 수 있다.

 

state diagram

 

 

 

 

 

2. The Markov Decision Process (MDP)

 

 

 

 

1) MDP and Elements of MDP

 

MDP는 앞서 살펴본 Markov chain의 확장 버전이라고 생각하면 된다. 의사결정하게 되는 상황을 모델링하는 수학적인 framework를 제공하며, 대부분의 Reinforcement Learning 문제는 MDP로 모델링된다. 이는 곧 RL 문제들이 대부분 Markov property를 따른다는 것을 의미한다.

 

MDP 표현에서 다음과 같은 5개의 중요한 요소들이 있다.

1. States (\(S\))  : agent가 존재할 수 있는 상태의 집합을 말한다.
2. Actions (\(A\)) : agent가 수행할 수 있는 행동의 집합 \(A\)을 말하며, 한 state에서 다른 state로의 움직임을 뜻한다.
3. Transition Probability (\(P^{a}_{ss'}\)) : action \(a\)를 수행하여 기존 state \(s\)에서 다른 state \(s'\)로 움직일 확률을 말한다. $$P^{a}_{ss'} = pr(s_{t+1} = s' | s_t = s, a_t = a)$$ pr은 조건부 확률을 나타낸다.
4. Reward Probability (\(R^{a}_{ss'}\)) : action \(a\)를 수행하여 기존 state \(s\)에서 다른 state \(s'\)로 움직일 때, agent가 특정 reward를 받을 확률을 말한다. Probability 없이 Reward로 표현하기도 한다. $$R^{a}_{ss'} = \mathbb{E}(R_{t+1} | s_t = s, s_{t+1} = s', a_t  = a)$$ 여기서, E는 기대값을 뜻한다.
5. Discount factor (\(\gamma\)) : 현재와 미래 reward의 중요도를 나타낸다. 뒤에서 자세히 알아보자.

 

 

 

 

2) Rewards and Returns

 

Agent와 Environment가 상호작용하는 과정은 다음과 같다.

 

Agent-Environment Interface

 

위 그림을 통해 Markov Decision Process에서 현재 agent의 state가 \(S_t\)이고, action \(A_t\)를 함으로써 \(S_t\)가 \(S_{t+1}\)이 되며, 이때 agent는 \(R_{t+1}\)을 받는 것을 알 수 있다.

 

agent는 총 reward의 합, 즉 cumulative reward를 최대화하려 하기 때문에, \(R_1\)만이 아니라 에피소드가 끝날 때까지의 모든 \( R \)들을 고려해야 한다.

이때 총 reward의 합을 Return이라 한다. (위에서는 reward를 \( R \)로 표현하였지만, 이제부터는 Return을 \( R \)로, Reward는 \( r \)로 표현하기로 한다.

$$ R_t = r_{t+1} + r_{t+2} + ... + r_T $$

여기서 주의할 점은, 정의에 의해 \( r_{t+1} \)은 time step \( t \)에서 action \( a_t \)에 의해 받는 reward라는 것이다. \( T \)는 에피소드가 끝날 때의 time step을 말한다.

 

 

 

 

3) Episodic and Continuous Tasks

 

그렇다면, Continuous task는 어떻게 return을 정의할까?

먼저 episodic task와 continuous task를 비교하며 이해해보자.

 

위에서 return에 대한 수식은 episodic task, 즉 끝 state가 정해진 task에서만 유효하다. RL에서 에피소드는 agent와 environment가 상호작용하기 시작하는 state부터 마지막 state까지를 말한다.

예를 들어, 자동차 경주 게임을 한다면, 게임을 시작하는 것이 initial state, 경주가 완료되는 시점이 final state일 것이다. 이 과정 전체가 하나의 에피소드로 볼 수 있다.

게임이 끝나면, 게임을 재시작하여 새로운 에피소드를 진행할 수 있다. 여기서 첫 번째 game과 두 번째 game은 관련이 없다. 마치 첫 번째 게임에서 위치가 어디였든, 처음 시작 위치는 정해져있는 것처럼 말이다. 한마디로 각 에피소드들은 모두 서로 독립적이다.

 

반면에 Continuous task는 끝이 정해져있지 않다. terminal state (final state)가 없고, 끝나지 않는다.

예를 들어, 비서 로봇은 끝 상태가 따로 정해져있지 않다.

 

 

 

 

4) Discount Factor (\(\gamma\))

 

이러한 Continuous task에서 Return을 정의하기위해 'discount factor'라는 개념을 도입한다.

 

episodic task에서의 return을 다시 보자면, 다음과같이 정의하고 계산이 가능하다.

$$ R_t = r_{t+1} + r_{t+2} + ... + r_T  $$

앞서 언급했듯이, \( T \)는 에피소드의 마지막 state를 말한다.

 

하지만 continuous task에서의 return을 표현해보면 다음과 같다.

$$ R_t = r_{t+1} + r_{t+2} + ... $$

즉, 마지막 state가 존재하지 않으므로 무한히 reward들이 더해질 것이다.

여기서 discount factor \(gamma\)를 이용하여 return을 정의하고, agent가 이러한 return을 최대화하는 방향으로 학습시킬 수 있다.

 

discount factor는 0에서 1사이의 값을 가지며, future reward를 얼마나 중요하게 반영할 것인지를 나타낸다. 즉, 값이 클수록 future reward의 영향이 커진다.

따라서 아래와 같이 return을 정의할 수 있게 된다.

 

 

위와 같이 return을 정의할 경우, 먼 미래의 reward는 discount factor가 반복해서 곱해짐으로써 영향이 점점 사라진다.

하지만, 이 형태도 코드로 구현을 할 수는 없다. 구현을 위해 다음과 같이 iterative하게 계산될 수 있도록 한다.

 

 

가장 아래 식을 보면, time step \( t+1 \)에서의 return을 통해 time step \( t \)에서의 return을 구한다. 즉 return은 뒤에서부터 앞으로 계산된다.

 

discount factor의 값은 hyperparameter로, 모델을 설계하는 설계자가 임의로 정해주는 값이다. 보통 0.2에서 0.8 사이의 값을 부여한다.

 

경우에 따라 discount factor 값을 적절히 설정해주어야 한다. 예를 들어, 체스 게임에서는 상대방의 king을 죽이는 것이 목표이다. 현재 reward, 즉 king이 아닌 다른 말을 죽이는 것에 큰 중요도를 부여하면(즉, discount factor 값이 작으면), agent는 king을 죽이는 actual goal보다 현재 죽일 수 있는 말을 죽이는 sub-goal을 달성하는 데 집중할 것이다. 따라서 이러한 경우 future reward가 중요하므로 discount factor 값을 크게 설정해야 한다.

 

 

 

 

3. Policy Function, Value Function, Q Function

 

강화학습은 MDP로 설정한 문제를 Equation으로 표현한 후 푸는 과정으로 볼 수 있다.

그렇다면, MDP 문제를 Equation으로 정의하기 위해 사용되는 함수들에 어떤 것들이 있는지, 개념은 무엇인지 알아보자.

 

 

 

 

1) Policy Function, \(\pi(s)\)

 

Policy Function은 특정 state에서 어떤 action을 선택할 확률을 말하며, 다음과 같이 표현한다.

$$ \pi(s) : S → A $$

최종적인 목표는 optimal policy를 찾는 것이다. 이는 곧 각 state에서 return을 최대화하는 action을 선택하는 것으로 볼 수 있다.

 

 

 

 

2) Value Function, \(V(s)\)

 

Value Function은 State Value Function이라고도 불리며, agent가 policy \(\pi\)에 기반하여 \(s\) state에 있을 때, \(s\)가 얼마나 좋은 state인지를 나타내는 함수이다.

Value Function은 다음과 같이 표현할 수 있다.

$$ \begin{align*} V^{\pi}(s) &= \mathbb{E}[R_t | s_t = s] \\ &= \mathbb{E}[\sum^{\infty}_{k=0} \gamma^{k}r_{t+k+1} | s_t = s] \end{align*} $$

즉, \(V^{\pi}(s)\)는 특정 policy \(\pi\)를 따랐을 때, 현재 state \(s\)가 갖게 될 Return의 기댓값이다. 여기서 \( \sum^{\infty}_{k=0} \gamma^{k}r_{t+k+1} \)는 \(R_t\)임을 알 수 있다.

따라서 policy가 바뀌면 당연히 Value function도 바뀌게 된다.

 

Value function의 특성은 아래와 같이 recursive relationship을 만족한다는 것이다.

$$ \begin{align*} V^{\pi}(s) &= \mathbb{E}[R_t | s_t = s] \\ &= \mathbb{E}[r_{t+1} + \gamma R_{t+1} | s_t = s] \end{align*} $$

위 식에서 '\(R_t = r_{t+1} + \gamma R_{t+1}\)'라는, 위에서 살펴본 return의 recursive relationship을 볼 수 있다.

 

value function은 아래와 같이 table로 나타낼 수 있다. 따라서 value function 기반의 RL을 tabular solution method라고 부른다. (참고로 non-tabular solution method는 value function을 table로 표현할 수 없는 경우를 말한다.)

 

value function table

 

policy \(\pi\)를 따르는 두 state가 있다. 여기서 value는 각 state가 agent에게 얼마나 좋은 상태인지를 나타낸다.

예시에서 state 1보다는 state 2가 더 좋은 상태라는 것을 알 수 있다.

이러한 value들을 어떻게 직관적으로 나타낼 수 있는지 뒤에서 다룰 예정이다.

 

 

 

 

3) Q Function (State-Action Value Function), \(Q(s, a)\)

 

Q Function은 Value function에서 action의 개념이 추가된 것으로 생각하면 쉽다. 즉, 특정 state \(s\)에서 어떤 action \(a\)가 얼마나 좋은지를 나타낸다.

Q Function은 아래와 같이 정의된다. 

$$ \begin{align*} Q^{\pi}(s, a) &= \mathbb{E}_{\pi}[R_t | s_t = s, a_t = a] \\ &= \mathbb{E}_{\pi}[\sum^{\infty}_{k=0} \gamma^{k}r_{t+k+1} | s_t = s, a_t = a] \end{align*} $$

 

Value Function과 마찬가지로, Q Function도 table로 표현할 수 있다. 이를 Q table이라 한다.

예를 들어, 두 가지 state에 대해 두 가지 action이 가능하다면, 아래와 같은 Q table을 만들 수 있다.

 

Q table

 

Q table은 모든 가능한 state, action 쌍의 value를 보여준다.

위 표를 보고, \(s_1\) state에서는 \(a_1\) action이, \(s_2\) state에서는 \(a_2\) action이 좋다는 것을 알 수 있다.

 

최종적으로 학습의 목표는 optimal Q table을 찾는 것이다. 이는 곧 optimal policy를 찾는다는 말과 같다.