[강화학습] Markov Decision Process

강화학습의 기초가 되는 Markov Decision Process을 알아보자.

먼저, action을 하는 agent와 그를 둘러싼 모든 환경 environment를 중심으로 학습이 이루어진다. 이렇게 말하면 잘 와닿지 않으니 그림과 함께 알아보자.

 

discrete time step t에 대해 현재 state $S_t$를 agent가 받으면 그에 대해 특정 action $A_t$를 하여 나타나는 다음 state $S_{t+1}$를 바탕으로 reward $R_{t+1}$를 제공한다. agent는 reward을 많이 받는 action을 하도록 학습되기 때문에 return은 현재 시점부터 그 이후의 미래까지 누적된 reward이 되고, 우리의 학습 목표는 이 return의 기댓값을 최대로 만드는 것이다.  이때, 미래는 추정하는 것이고 우리가 알고 있는 정보는 현재에 대한 정보이기 때문에 미래로 갈 수록 우리가 추정한 reward가 부정확할 가능성이 높다. 따라서 이를 반영하기 위해 discount factor $\gamma$를 사용하여 표현한다. 가장 중요한 개념은 policy이다. policy는 agent가 특정 상태에서 어떠한 action을 하는 규칙이라고 생각하면 쉽다. 사실상 우리는 학습을 시키는 것이기 때문에 순간의 운으로 높은 return 혹은 reward를 얻기만 하는 것이 중요한게 아니라 그를 바탕으로, 특정 state에서 어떤 action을 해야 최대의 return을 얻을 수 있는가가 가장 중요하다. 그래서 우리는 optimal policy를 얻고자 한다. 한편, environment가 deterministic하다 혹은 stochastic하다 라고 하는데, deterministic environment는 특정 action을 했을 때 state가 하나로 결정되는 것을 말한다. 반면, stochastic environment는 dynamics / transition probability가 존재해서 action을 했을 때의 state가 확률적으로 결정되는 것을 말한다. 그래서 보통 dynamics가 없다고 하면 deterministic하구나, state가 하나로 결정되는 구나 라고 생각할 수 있다.

그렇다면 markov property란 무엇일까? Markov property는 과거의 정보 없이 현재 정보만으로 미래를 추정하는 것이다. 예를 들어, 위의 과정에서 주어진 $S_t$에 대해 $A_t$을 하고 $S_{t+1}$가 결정된다. 원래라면 미래를 추정하기 위해 $S_0, A_0, \cdots , A_t$까지 모두 알아야 이를 바탕으로 한 $S_{t+1}$를 추정할 수 있지만 markov property를 만족하는 경우에는 현재 정보인 $S_t$와 $A_t$만으로 $S_{t+1}$을 추정할 수 있는 것이다. MDP에서는 policy와 transition probability가 대표적인 markov property를 만족하는 요소들이다. policy는 $\pi (a|s)$로 나타내는데, $s$는 현재 state로 이 정보를 바탕으로 현재 action인 $a$를 선택할 확률을 나타내기 때문이다. 또한, transition probability는 $p(s'|s,a)$로 나타내는데, $s'$은 다음 스텝의 state로, 현재의 state와 action을 바탕으로 그 다음 스텝의 state가 무엇으로 결정될지 확률을 나타내는 것이므로 이또한 markov property를 만족한다. 이렇게 markov property를 만족하는 요소들로 이루어지면 markov process라고 한다. 

이번에는 value function을 알아보자. value function에는 state-value function $V_\pi (s)$와 action-value function $Q_\pi (s,a)$이 있다. $V_\pi (s)$는 policy $\pi$에 대해 $s$를 평가하는 것이고, $Q_\pi (s,a)$에 대해 $(s,a)$ 쌍을 평가하는 것이다. 이때 $a$는 policy $\pi$를 따를 수도 있고 그렇지 않을 수도 있다. 그냥 임의의 action인 것이다. 먼저 의미상으로 이해해보자. 만약 $Q_\pi (s,a) > V_\pi (s)$라고 주어진다면 이는 무엇을 의미할까? 현재의 policy가 하는 선택보다 임의의 action $a$가 더 좋은 선택이었음을 의미한다. 같다면 둘의 기대 보상이 같다는 것이고 반대라면 현재의 policy가 더 좋은 선택이라는 의미일 것이다. 이를 간단하게 나타내보면 아래와 같다.

$$V_\pi (s) = \mathbb{E}_\pi \{G_t | S_t = s\} = \mathbb{E}_\pi \{\Sigma^\infty_{k=0} \gamma^k R_{t+k+1} | S_t = s\}$$

$$Q_\pi (s,a) = \mathbb{E}_\pi \{G_t | S_t = s, A_t = a\} = \mathbb{E}_\pi \{\Sigma^\infty_{k=0} \gamma^k R_{t+k+1} | S_t = s, A_t = a\}$$

여기에 Bellman equation을 적용하면 아래와 같이 나타낼 수 있다.

$$ V_\pi (s) = \mathbb{E}\{G_t|s\} = \mathbb{E}\{R_{t+1} + \gamma G_{t+1}|s\} = \Sigma_a \pi (a|s) \Sigma_{s',r} p(s',r|s,a)(r + \gamma \mathbb{E}_\pi\{G_{t+1}|S_{t+1}=s'\})$$

$$ Q_\pi (s,a) = \mathbb{E}\{G_t|s,a\} = \mathbb{E}\{R_{t+1} + \gamma G_{t+1}|s,a\} = \Sigma_{s',r} p(s',r|s,a)(r+\gamma \mathbb{E}_\pi\{G+{t+1}|S_{t+1}=s'\})$$

그렇다면 optimal policy는 무엇을 말하는 걸까? 모든 s, $\pi$에 대해 $v_\pi(s)$가 가장 클 때의 policy 혹은 모든 s, a, $\pi$에 대해 $q_\pi(s,a)$가 가장 클 때의 policy를 말한다.

이 글은 Sutton & Barto의 Reinforcement Learning 3장을 바탕으로 작성되었다.