Markov Decision Processes

이제 RL이 해결하고자 하는 대상인 environment로 관심을 돌릴 때이다. Agent는 environment에서 오는 시그날인 state에 따라 판단하여 결정을 내린다. 여기서, state라고 함은 agent가 받아들이는 모든 정보(information)을 의미한다. 이 state information은 가공되지 않은 information일 수 도 있고, 기본 정보를 이용항 가공된 정보일 수도 있다. 단지 agent가 판단(decision-making)에 이용할 수 있는 정보형태이면 된다. State 정보가 agent의 판단에 이용된다고 해서, 판단에 필요한 모든 정보를 다 받아야 한다는 의미는 아니다. 보다 정확한 판단을 위해 필요한 정보(hidden state information)가 있더라도 주어진 정보를 최대한 이용하여 판단을 하는 것이며, environment가 가지는 모든 정보를 받아야 하는것은 더더군다나 아니다. 단지 우리가 관심을 두는 것은 주어진 정보를 이용하여 어떻게 바람직한 판단을 이끌어 내는 알고리즘을 구축하느냐이다.

판단정보를 가지고 있는 state signal에 관해 시간의 관점에서 바라보자. 이 시그널은 바람직하건데 과거의 정보를 포함하고 있는 것이 좋다. 이처럼 과거의 상태나 정보가 함축되어 포함된 state를 Markov property를 가진다고 한다. 예를 들어, 장기판의 현재 상태는 과거 player들이 행한 모든 게임의 결과물이 표현된 것이다. 이런 특성을 가지기 위해서는현재 state signal은 반드시  history나 path에 무관해야 한다. 즉, 과거 history에 따라 현재의 stat signal이 다른 의미를 가진다면 Markov property를 가진다고 할 수 없다. 이를 수식으로 표현하면 다음과 같다.

 p(s',r|s,a) \doteq Pr \{S_{t+1}=s', R_{t+1}=r | S_t = s, A_t =a\}

Markov property는 reinforcement learning에서 매우 중요한 개념인데, 이는 decision이나  value가 현재의 state만의 함수라는 것을 가정으로 하기 때문이다. 그러나, 완전히 Markov property를 가지지 않은 non-Markov property state signal일지라도 대부분은 이 이론을 적용하여 알고리즘을 구축하고 성공적으로 응용할 수 있는 경우가 많다. 우선은 Markov property를 보이는 state에 대한 완전한 이해로 부터 시작해야 보다 복잡한 non-Markov case에 대한 확장 응용이 가능해 질것이다.

Markov Decision Processes

Markov property를 만족하는 reinforcement learning task를 Markov decision process, MDP,라고 한다. 이중에서 state와 action space가 유한공간인 경우를 finite Markov decision process라고 하며 우리가 다루는 reinforcement learning은 대부분 이 경우이다. 이것을 수학적 표현을 dynamics of environment라고 하며 위의 식과 같이, 주어진 상태 s와 action a가 주어지면 다음상태 s’과 reward  r을 나타날 확률로 environment를 표현할 수 있다. 이 확률분포(다시 말해, environment dynamics)를 알 수 있으며, environment에 관련하여 알고 싶은 모든것을 계산할 수 있다고 볼 수 있다. 예를 들어, 어느 state-action pair에 대한 reward state-transition probability는 다음과 같이 나타낼 수 있다.

r(s,a) \doteq \mathbb{E}[R_{t+1} | S_t = s, A_t = a] = \displaystyle\sum_{r\in\mathcal{R}}r\displaystyle\sum_{s'\in\mathcal{S}}p(s',r|s,a)

p(s'|s,a) \doteq Pr\{S_{t+1}=s' | S_t = s, A_t = a\} = \displaystyle\sum_{r\in\mathcal{R}}p(s',r|s,a)

위의 수학적 표현으로 environment dynamics가 정의되었지만, 아무래도 개념을 보다 구체화하기 위해서는 실례를 들어 설명하는 것이 좋다. Sutton & Barto의 책에서는 recycling robot을 예로 들어 설명하였는데, recycling robot의 state는 robot이 battery energy level이고 state set은 \mathcal{S} = \{high, low\}이다. 반면 action space를 다음과 같이 정의한다.

\mathcal{A}(high) \doteq \{search, wait\}

\mathcal{A}(low) \doteq \{search, wait, recharge\}

Agent가 취하는 행동에 따른 상태변화와 그것의 확률 및 reward를 한꺼번에 표현해 도식적으로 표현한 그림을 transition graph라고 하며, 이 그래프를 이용하면 finite MDP를 요약하여 표기할 수 있다. Recycling robot의 경우 아래 그림과 같이 표현될 수 있다.

rl-recycling-robot-transition-graph

위의 transition graph에서 관심있게 보아야 할것이 있다. Large open circle로 표현된 것을 state nodes라고 small solid circle로 표현된 것을 action nodes라고 한다. 아래는 recycling robot의 transition probability와 reward를 표로 나타낸 것이다. 앞서 말한 수학적 정의와 함께 보면 간단히 개념이 이해될 수 있다.

rl-recycling-robot-transition-table

Value Functions

RL의 최종목적은 쉽게 정의할 수 있지만, 그전에 agent의 state나 취하는 action에 대해 평가를 하는 작업이 필요하다. 이것을 value function이라고 하고 “how good”을 의미한다. 이 “how good”이라는 개념은 미래의 reward, 더 정확하게는 예상되는 return을 의미한다. 물론, 이 future reward는 agent가 어떤 행동(action)을 취하느냐에 따라 달라지게 되어 있다. 그러므로, value function은 필연적으로 특정 policy와 관련지어 생각해야 한다.


사실, agent가 하는 행동에 대한 평가는 지금 당장 내릴 수 없는 경우가 많다. 장기나 바둑을 둘때 지금 둔 착석의 최종 평가는 게임의 승리 여부이다. 그러므로 value function을 정의하는 것이 매우 중요하며, 경우에 따라서는 Monte Carlo Tree Search와 같은 알고리즘이 더 적당 할 수 있다.


Policy \pi에 따르는 상태 s의 value는  v_{\pi}(s)로 표현하고 상태 s에서 policy \pi를 따를 때 예상되는 return를 의미한다.

v_\pi (s) \doteq \mathbb{E}_\pi [G_t | S_t = s] = \mathbb{E}_\pi \begin{bmatrix}  \displaystyle\sum_{k=0}^{\infty}\gamma^k R_{t+k+1} | S_t = s \end{bmatrix}

여기서, \mathbb{E}_\pi [ \cdot ] 은 agent가 policy \pi를 따를 때 얻을수 있는 value를 의미한다. 그리고, terminal state에서의 value는 항상 zero이고, 위와 같이 정의된 {v_\pi}state-value function for policy {\pi}라고 한다.

마찬가지로, agent가 policy \pi를 따라 state s에서 action a를 취할 때 얻을수 있는 value를 정의할 수 있으며, 정의된 {q_\pi}(s, a)action-value function for policy {\pi}라고 한다.

q_\pi (s, a) \doteq \mathbb{E}_\pi [G_t | S_t = s, A_t = a] = \mathbb{E}_\pi \begin{bmatrix}  \displaystyle\sum_{k=0}^{\infty}\gamma^k R_{t+k+1} | S_t = s , A_t = a \end{bmatrix}

앞서 정의된 두개의 value function은 경험에 의해 값이 예측된다. 예를들어, agent가 policy \pi를 따라 어느 상태에서 경험적으로 얻을 수 있는 실제의 return값을 평균낸 값이라고 할 수 있다. 그 경험이 무한대에 가까워 지면 실제 값이 될것이다. Action value에 대해서 마찬가지로 추론할 수 있으며, 이처럼 random sample의 return값의 평균을 이용하여 예측하는 방법을 Monte Carlo method라고 한다.

Reinforcement Learning에 사용되는 value function의 기본적 특징은 recursive relationship(순환 참조)을 만족한다는 것이다. 주어진 policy \pi와 state s에서 다음과 같은 관계를 만족한다.

 v_\pi (s) \doteq \mathbb{E}_\pi [G_t | S_t = s] = \mathbb{E}_\pi \begin{bmatrix}  \displaystyle\sum_{k=0}^{\infty}\gamma^k R_{t+k+1} | S_t = s \end{bmatrix} \\=\mathbb{E}_\pi \begin{bmatrix}  R_{t+1} + \gamma \displaystyle\sum_{k=0}^{\infty}\gamma^k R_{t+k+2} | S_t = s \end{bmatrix} \\=\displaystyle\sum_{a} \pi (a|s)\displaystyle\sum_{s'} \displaystyle\sum_{r} p(s',r|s,a) \begin{bmatrix} r + \gamma \mathbb{E}_\pi \begin{bmatrix}\displaystyle\sum_{k=0}^{\infty}\gamma^k R_{t+k+2} | S_t = s' \end{bmatrix} \end{bmatrix} \\ =\displaystyle\sum_{a} \pi (a|s)\displaystyle\sum_{s', r} p(s',r|s, a) \begin{bmatrix} r + \gamma v_{\pi} (s') \end{bmatrix}

여기서 특히 마지막 식을 눈여겨 볼 필요가 있다. 모든 a, s’, r에 대하여 확률값을 weight로 사용하여 bracket내부의 return값을  가중평균내는 것과 같은 의미이다. 이 식을 v_\pi에 관한 Bellman equation 이라고 한다. 이 식은 현재 상태의 value값과 후속 상태의 value값과의 관계를 표현한 식이다. 이 관계를 도식적으로 표현한 것을 backup diagram이라고 하는데, 이유는 강학학습의 핵심이 되는 update 또는 backup operation을 도식적으로 표현해 주기 때문이다. 이것은 알고리듬을 간단히 도식적으로 표현할 때 매우 유용하게 사용된다.

rl-backup-diagram-sample

여기서, (a)는 state-value function인 v_\pi를 나타내고, (b)는 action-value function인  q_\pi에 대한 backup diagram이다.

Optimal Value Functions

우리가 value function을 정의하였으므로, 이 값을 최적상태(최대화)로 만들어 주는 policy가 존재할 가능성이 있다. Reinforcement learning task를 해결한다는 것은, 결국 이런 best policy를 찾아내는 것을 의미한다. 만약 모든  s \in \mathcal{S}에 대해 v_\pi (s) \geq v_\pi' (s) 인 policy \pi \geq \pi'를 존재한다면 이것을 optimal policy라고 하며, \pi_*로 표기한다. 이때의 state-value fuction을 optimal state-value function이라고 하며, v_*로 표기한다.

v_* (s) \doteq max_{\substack{\pi}} v_\pi (s) \text{ for all }s \in \mathcal{S}

같은 맥락에서, optimal action-value function, q_* 를 정의할 수 있다.

q_* (s, a) \doteq max_{\substack{\pi}} q_\pi (s, a) \text{ for all }s \in \mathcal{S}\text{ and } a \in \mathcal{A}

같은 optimal policy기준으로 두개의 value function을 정의하였으므로, 다음과 같이 두 value function간의 관계가 성립한다.

q_* (s, a) = \mathbb{E}[R_{t+1} + \gamma v_* (S_{t+1}) | S_t = s, A_t =a]

Optimal value function에 대해서도 Bellman equation이 성립하며, optimal policy하에 있는 value function은 가장 최적의 action을 취할 때 얻을수 있는 return값과 같을 것이다. v_*와 q_*에 대한 Bellman optimality equation은 다음과 같다.

rl-eq3-163-17rl-eq3-17a

위의 식들은 도식적으로 backup diagram으로 표현하면 아래와 같다. 이것은 v_\pi q_\pi과 같은 방식으로 v_* q_*를 표현한거지만 한가지 차이점이 있다면, agent가 선택할수 있는 지점에서 arc를 표시하여 선택할 수 있는 action중 최선의 선택만을 한다는 것을 나타내고 있다.

rl-backup-diagram-for-optimality

실제로 v_*값을 알게되면 agent가 행동할때 greedy policy에 의해 선택하는 행동들의 집합이 optimal policy가 된다. 이 이유는 v_*가 이미 모든 미래의 가능한 행동들을 감안하여 평가되었기 때문이다. 그러므로 one-step-ahead 탐색이 결국 long-term  optimal action이라는 것을 의미한다. Optimal action value q_*를 알게되면 이 작업은 더욱더 쉬워진다. one-step-search도 필요 없어 지기 때문이다. 단순히 더 큰q_* (s,a)를 가지는 action을 선택하는 것이 optimal policy가 되기 때문이다. 그러므로, state space만 고려하는것이 아니라 action space을 고려한 state-action pair의 value function값을 저장하는 수고로움을 하는 대신 후속 상태(successor states)와 그 값에 대한 정보 없이도 (다시 말하면, environment dynamics를 알지 못해도) 최적의 action을 선택할 수 있도록 해준다.

Optimal value function이나 policy는 정의가 되었지만, 실제로 agent가 최적의 policy를 찾아 내는 것은 그다지 쉽지 않은 일이며, 가능하더라도 매우 값비싼 computing cost가 요구될것이다. 실제 우리가 environment dynamics에 완전하고 정확한 model을 알고 있다손 치더라도 Bellman equation을 통해 optimal policy를 찾아내는 것은 쉽지 않은 일이다. 그러므로 현실적인 solution은 최적해에 대한 근사해(approximation)의 관점에서 접근하는 것이다. 그 다음은 어떤 방법이 더 효율적으로 approximation을 찾아내는가이다. 모든 경우의 수를 다 해볼 수 없다면, 자주 접하는 state에 대해 더 많은 노력을 기울이는 것이 효율적인 approach일것이다.

여기까지 reinforcement learning에 필요한 기본 개념을 모두 정리한것 같다. 다은 포스트부터는 보다 실전적 문제를 다룰 예정이다.

Note) 본 포스팅은 Sutton과 Barto가 공저한 Reinforcement Learning : An Introduction을 기초로 작성된것이다.

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중