[RL] 1. Markov Decision Chain

마크로프 결정 과정이란?

마르코프 결정 과정(Markov Decision Process)은 마크코프 보성 과정에 결정(action) 요소를 추가한 모델이다.

마르코프 보상 과정(Markov Reward Process)은 마르코프 연쇄(Markov Chain)에 보상(reward) 요소를 추가한 모델이다.

 

구체적으로 MDP의 정의(definition)를 살펴보면 다음과 같다.

 

A Markov Decision Processes is a tuple $<\mathcal S, \mathcal A, \mathcal P, \mathcal R, \gamma>$

- $\mathcal S$ is a set of states

- $\mathcal A$ is a finite set of actions

- $\mathcal P$ is a state transition probability matrix, $\mathcal P_{ss^\prime}^a = \mathbb P[S_{t+1} = s^\prime | S_t = s, A_t = a]$

- $\mathcal R$ is a reward function, $R^a_s = \mathbb E[R_{t+1}|S_t=s, A_t = a]$

- $\gamma$ is a discount factor $\gamma \in [0, 1]$

 

$\mathcal S$는 환경(environment)이 가질 수 있는 모든 상태(state)를 원소로 가지고 있다.

$\mathcal A$는 에이전트(agent)가 취할 수 있는 모든 행동(action)을 원소로 갖고 있다.

상태 전이 확률(state transition probabilities) $\mathcal P_{ss^\prime}^a$는 현재 상태($S_t$)가 $s$이고 현재 행동($A_t$)가 $a$일 때, 다음 상태($S_{t+1}$)가 $s^\prime$가 될 확률을 의미한다.

이때, 과거 정보($S_{<t}$, $A_{<t}$)를 고려하지 않는 이유는 모든 Markov chain 기반 모델이 Markov property를 따르기 때문이다.

$R_s^a$는 현재 상태($S_t$)가 $s$이고 현재 행동($A_t$)가 $a$일 때, 환경이 주는 보상의 기댓값을 의미한다.

MDP(환경?)가 마르코프 성질을 따르게 때문에, 보상도 과거 상태 및 행동을 고려하지 않는다.

할인률 $\gamma$는 미래에 얻을 보상을 현재 가치에 맞게 감가해주는 역할을 한다.

 

MDP (모델)를 환경 (모델)으로 봐도 무방하다. 왜냐하면, MDP의 모든 요소를 환경이 정해주기 때문이다. (할인률은 아닐 수 있다.)

 

MDP의 사이클을 추상화하면 다음과 같다.

 

상태 $S_t$에서 에이전트가 행동 $A_t$를 수행하면 상태가 $S_{t+1}$로 전환될 뿐만 아니라, 그에 따른 보상 $R_t$도 주어지는 방식으로 환경과 에이전트 사이에 상호작용이 이루어지고 있고 있음을 그림에서 확인할 수 있다.

MDP의 목표 (최적 정책)

MDP에서 우리가 알고자 하는 것은 최적 정책(optimal policy)이다.

정책, 수익, 상태 가치 함수

최적 정책이 무엇인지 알기 위해서는 세 가지 용어(정책, 수익, 상태 가치 함수)를 알아야 한다.

 

1. 정책(policy)

정책은 에이전트가 행동을 결정하는 방식이다.

이때, 에이전트도 현재 상태 $s$만 고려해 행동을 결정한다.

환경이 마르코프 성질에 따라 동작하기 때문이다.(=MDP 모델이 마르코프 성질을 따르기 때문이다.)

다시 말해, 환경이 상태 전이를 할 때 혹은 보상을 줄 때 현재 상태 $s$와 현재 행동 $a$만 고려하기 때문이다.

이가 의미하는 바는 "환경에 대해 필요한 정보는 모두 현재 상태에 있다"는 것이다.

그렇기 때문에, 에이전트는 현재 상태만으로 행동을 결정할 수 있는 것이다.

수식으로 표현하면 다음과 같다.

$$\pi(a|s) = \mathbb P[A_t=a|S_t=s]$$

 

다시 한번 강조하면, MDP의 마르코프 성질이라는 특성은 에이전트에 대한 제약이 아니라 "환경에 대한 제약"이다.

즉, 마르코프 성질을 만족하도록 "상태" 및 "보상"을 관리하는 책임이 환경 쪽에 있다는 뜻이다.

 

참고로, $\mathcal A$은 에이전트가 아닌 환경이 정해주기 때문에, 정책이야말로 에이전트가 유일하게 컨트롤할 수 있는 요소라고 볼 수 있다.

 

2. 수익(return)

수익이란 보상의 합이다. 구체적으로, 시점 $t$부터 얻은 모든 보상에 할인율(discount rate)을 적용해 합한 것이다.

이를 수식으로 표현하면 다음과 같다.

$$G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots, \quad (\gamma \text{ is discount rate})$$

 

3. 상태 가치 함수(state-value function)

상태 가치 함수인 $v_\pi(s)$는 상태 $S_t$가 $s$고 에이전트 정책이 $\pi$일 때, 에이전트가 얻을 기대 수익을 의미한다.

기대 수익 즉, 평균을 사용하는 이유는 매 에피소드마다 얻는 수익이 달라지기 때문이다.

이를 수식으로 표현하면 다음과 같다.

$$v_\pi(s) = \mathbb E_\pi[G_t|S_t=s]$$

 

이제 최적 정책이 무엇인지 알아보자.

최적 정책 $\pi_*$은 모든 상태에서 수익의 기댓값(=가치 or 상태 가치 함수 값)가 다른 어떤 정책보다 큰 정책을 의미한다.

최적 정책은 "결정적 정책"이며, 수식으로는 $\alpha = \mu_*(s)$와 같이 나타낸다.

그리고, 최적 정책의 상태 가치 함수를 최적 상태 가치 함수(optimal state-value function) 이라고 하고, $v_*$라고 표기한다.

 

참고로, 소문자 $v_\pi$는 실제 상태 가치 함수이고, 대문자 $V_\pi$는 추정 상태 가치 함수다.

그리고, 상태 전이가 결정적이면 상태 전이 함수인 $s^\prime = f(s, a)$로 표현하고, 정책이 결정적이라면 $\alpha = \mu(s)$로 표현한다. 마지막으로, 보상이 결정적이라면 보상 함수를 $r(s, a)$로 표현할 것이다.