Markov Decision Process(MDP)

본 게시글은 인하대학교 유상조 교수님의 Reinforcement Learning Tutorial Seminar

수강 후정리를 위한 포스팅입니다.

모든 포스팅의 저작관은 유상조 교수님에게 있음을 사전 공지합니다.

---

Before This Episode

https://jinwoo-jung.tistory.com/12

Markov Reward Process(MRP)

---

Preview

 

MRP(left) and MDP(right)

 

이전시간에 배운 MRP는 Action 개념이 존재하지 않았고, constant reward로 구성되어 있었다.

MDP는 MRP에서 Action 개념이 확장된 Markov Decision Process이다.

이전에 언급 한 것처럼, 동일한 action에 대해서도 Env의 영향 등에 의해 서로 다른 state로의 변화가 발생한다. 왼쪽 MDP에서 $a_1$로 인해 $S_0$에서 ${P_ss'}^a$에 기반하여 $S_k,S_1$ 서로 다른 state로의 변화가 발생함을 알 수 있다. 

또한, K-armed Bandit의 slot machine처럼 reward 역시 constant가 아닌 특정 PDF를 기반으로 하는 Random Variable일 수도 있다. 더 자세히 알아보자,,!!

---

Markov Decision Process(MDP)

MDP는 $<S,A,P,R,\gamma>$로 정의된다

$S$ : a finite set of states

$A$ : a finite set of actions

$P$ : a state transition probability matrix

$$ {P_ss'}^a=P[S_{t+1} = s'|S_t = s, A_t = a]$$

즉, 현재 state가 $s$이고 action $a$로 인해 $s'$으로 state가 변화 할 transition probability matrix를 의미한다.

이때, $ {P_ss'}^a =1$ 즉, $a$로 인한 $s \to s'$의 확률이 1일 경우를 deterministic하다라고 표현한다. 

 

$R$ : a reward function

$${R_s}^a = E[R_{t+1}|S_t=s,A_t=a]$$

MRP에서는 delayed reward가 constant로 표현 되었지만, action에 따른 reward가 다르기 때문에 위처럼 표현되며, Reward 역시 Random Variable일 수 있기 때문에 평균값으로 표현된다.

 

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

 

여기서 새로운 Policy $\pi(a|s)$라는 개념이 등장한다.

Policy는 각 state에서 어떤 action을 어떻게 규정하는지에 대한 개념으로, 해당 state에서 각각의 action을 선택할 확률로써 정의된다. 따라서 각 state 마다 Policy는 다르게 정의된다.

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

Policy Example

 

위와 같은 간의 MDP에서 $S_0$에서의 policy는 $a_1,a_2,a_3$를 선택하는 확률로 결정되며, 예를들면 $\pi(a_1|s) = 0.2, \pi(a_2|s) = 0.5, \pi(a_3|s) = 0.3$과 같이 표현된다.

 

Recycling Robot Example

 

Recycling Robot의 MDP를 예시로 살펴보자. Robot은 빈 캔을 줍는 동작을 수행하며, 이를 위해 active하게 search해서 빈 캔을 찾아 줍거나, wait하여 누가 주워 버려주기를 기다리는 행동을 한다. 일반적으로 $r_{search} > r_{wait}$로 측정되며, 배터리가 없는 경우 recharge하는 action도 가능하다. 따라서 state는 로봇의 배터리 상태인 high와 low로 나뉜다.

 

아래의 MDP를 보면 high state에서 search action을 통해 $\alpha$의 확률로 high state로 돌아오며 $1-\alpha$의 확률로 배터리가 low인 state로 변화하며 둘다 search에 따른 $r_{search}$를 reward로 받음을 알 수 있다.

따라서 high state에서 search action에 대한 policy는 $\pi(search|high) = \alpha, \pi(search|low) = 1-\alpha$로 표현된다.

 

위와같이 $(M(Model) = <S,A,P,R,\gamma> , \pi$가 주어졌다고 했을 때, 우리는 몇가지를 추가적으로 정의할 수 있다.

$${P_{SS'}}^{\pi} = \sum_{a \in A}^{}\pi(a|S){P_{SS'}}^a \qquad , \qquad  {R_{S}}^{\pi} = \sum_{a \in A}^{}\pi(a|S){P_{S}}^a$$

 

Simple MDP

 

${P_{SS'}}^{\pi}$는  $\pi$의 policy가 주어졌을 때, $S \to S'$ state 변화의 확률이다.

위 MDP에서 ${P_{SS'}}^{\pi} = \pi(a_1|S){P_{SS'}}^a_1+ \pi(a_2|S){P_{SS'}}^a_2+ \pi(a_3|S){P_{SS'}}^a_3$로 계산할 수 있다. 따라서 위의 식이 성립한다.

 

&{R_{S}}^{\pi} = \sum_{a \in A}^{}\pi(a|S){P_{S}}^a$는 state S에서 주어진 policy데로 수행했을 때의 expected reward이다. 따라서 위에서 정의한 것 처럼, 각 action을 선택했을 policy와 그때의 reward의 곱의 합으로 표현 가능하다.

 

이전 MRP에서도 정의한 state-value function 역시 MDP에서 정의되는데 $\pi$가 추가적으로 부여된다. 즉, 미리 주어진 policy데로 action을 수행했을 때의 state-value function이 MDP에서는 아래와 같이 정의된다.

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

즉, state $s$에서 부터 정해진 policy데로 action을 수행하고, 추후 action 역시 policy데로 수행했을 때, 얻어지는 Avg return value를 의미한다.

 

MDP에서는 추가적으로 action-value function $q_{\pi}(s,a)$가 정의되는데,  이는 state $s$에서 action $a$를 했을 때 얻어지는 Avg return value를 의미한다.

$$ q_{\pi}(s,a) = E_{\pi}[G_t|S_t = s, A_t = a]$$

Relationship between $v_{\pi}(s)$ and $q_{\pi}(s,a)

 

위 예시를 토대로 다시 정리하면, state-value function은 정해진 policy데로 각 action을 선택했을 때의 Avg return value이고, action-value function은 각 action을 시행했을 때, 이후에 얻어지는 Avg return value이다.

 

MRP와 같이 식을 조금 풀어서 해석 해 보면,

$$v_{\pi}(s) = E_{\pi}[G_t|S_t = s] = E_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1})|S_t = s]$$

policy에 따라서 각 action을 선택했을 때 얻어지는 Rewar를 state $S_{t+1}$에서의 state-value function에 discount factor를 곱한 값을 더한 평균값으로 해석되고,

$$q_{\pi}(s,a) = E_{\pi}[G_t|S_t = s, A_t = a]= q_{\pi}(s,a) = E_{\pi}[G_t|S_t = s, A_t = a] $$

action a를 했을 때 얻어지는 Reward를 다음 state $S_{t+1}$에서 $A_{t+1}$ action을 했을때의 action-value function에 discount factor를 곱한 값을 더한 평균으로 해석할 수 있다.

 

따라서 둘 사이의 관계를 잘 유도 해 보면 발생가능한 모든 action의 action-value function의 합으로 state-value function을 아래와 같이 표현할 수 있다.

$$v_{\pi}(s) = \sum_{a \in A}^{}\pi(a|s)q_{\pi}(s,a)$$

즉, policy에 의해 각 action이 선택될 확률과 해당 action에서의 action-value function을 곱한 값의 합으로 표현 가능하다.

 

또한, action-value function은 아래처럼 유도할 수 있는데,

$$q_{\pi}(s,a) = {R_S}^a + \gamma \sum_{s' \in S}^{}{P_{SS'}}^a v_{\pi}{S'}$$

즉, 특정 action $a$에서 발생한 Reward와 이후에 가능한 미래가치들을 discount factor를 적용한 합으로 표현 가능하다.

 

Relationship between $v_{\pi}(s)$ and $q_{\pi}(s,a)

 

이를 조합하여 state-value function을 해결하기 위해 action-value function을state-value로 표현하면 아래와 같다.

$$v_{\pi}(s) = \sum_{a \in A}^{}\pi(a|s)({R_S}^a + \gamma \sum_{s' in S}^{}{P_{SS'}}^av_{\pi}{S'})$$

action-value function 역시 action-value function 만으로 표현하면 아래와 같다.

$$q_{\pi}(s,a) = {R_S}^a + \gamma \sum_{s' in S}^{}{P_{SS'}}^a \sum_{a' \in A}^{}\pi(a'|s')q_{\pi}(s',a') $$

 

지금까지 전개해 온 과정은 policy가 주어졌다는 가정하에 진행되었다. 하지만 해당 policy가 optimal poljcy가 아닐 수 있기에 아래와 같이 "optimal"에 대한 추가적인 정의가 필요하다.

 

optimal state-value function $v_*(s)$ : the maximum value function over all policies

$$ v_*(s) = \underset{\pi}{max} v_{\pi}(s) $$

 

optimal action-value function $q_*(s,a)$ : the maximum action-value function over all policies

$$ q_*(s,a) = \underset{\pi}{max} q_*(s,a) $$

 

Bellman Expected Equation

$v_{\pi}(s)$ 에서 Reward ${R_S}^a$는 State $S$에서 Action $a$를 선택했을 때의 Expected Reward이다. 

 

 

위의 MDP에서 같은 $a$를 선택하여도 일정 확률로 인해 다음 State $s'$이 달라진다면 그에따른 reward도 달라진다. 이때, 그 확률은 ${P_SS'}^a$로 정의된다. 따라서 Reward를 확률을 기반한 Random Value로 정의할 수 있다.

$$v_{\pi}(s) = \sum_{a \in A}^{}\pi(a|s)({R_S}^a + \gamma \sum_{s' in S}^{}{P_{SS'}}^av_{\pi}{S'})$$

$$= \sum_{a \in A}^{}\pi(a|s)\sum_{s' \in S, r \in R}^{} p)s',r|s,a)(r+\gamma v_{\pi}(s'))$$

즉, reward를  State $S$에서 Action $a$를 선택했을 때 State가 $S'$으로 바뀔 확률과 그때의 reward가 $r$일 확률 그리고 그때의 reward $r$과 $S'$에서의 discounted state-value function으로 표현 가능하다.

 

$ q_*(s,a)$의 reward 역시 Random Value로써 표현한다면 아래와 같다.

$$q_{\pi}(s,a) = E_{\pi}[G_t|S_t = s, A_t = a]= q_{\pi}(s,a) = E_{\pi}[G_t|S_t = s, A_t = a] $$

$$= \sum_{s' \in S, r \in R}^{} p(s',r | s,a)(r+\gamma \sum_{a' \in A}^{} \pi(a'|s') q_{\pi}(s', a'))$$

이를 Bellman Expected Equation이라 한다.

 

아래의 예시를 통해 복잡한 수식을 이해 해 보자.

Example of Solving Bellman Expected Equation

 

state $S_0$에서의 state-value function을 구해보자. 이때, $P_{SS'}^a, \pi$는 사전에 주어지는 정보이다.

위 식을 토대로 계산 해 보면, $  \sum_{a \in A}^{}\pi(a|s)$는 $S_0$에서 $a_1,a_2$ 각 action의 확률으로 각각 0.4, 0.6이다. $a_1$이 선택 되었을 때, $S_1, S_2$로 갈 확률은 각각 0.3, 0.7이고, 그때의 reward $r_{11}, r_{12}$는 동일하게 0.5의 확률로 1 또는 2가 선택되므로, 1x0.5+2x0.5로 평균 값을 구할 수 있다. 그리고 discount factor이 적용된 이후의 state에서의 state-value function이 더해진다. 

 

결국 Bellman Expected Equation은 state-value function, action-value function을 RV로써의 reward를 가만하여 푸는 방정식으로 정의할 수 있다.