[RL] MDP(Markov Decision Process)

너무 공부하기 싫은 강화학습 울며 겨자먹기로 공부 시작

 

 

강화학습에는 agent라는 학습자와 의사 결정자가 존재합니다. 그리고 상호 작용하는 주변을 환경(environment)이라고 합니다. 환경은 agent의 행동(action)에 따라 보상(reward)과 새로운 상태(state)를 제공합니다.

 

따라서 강화학습에선 agent에게 어떻게 해야하는지 가르치지 않고 행동에 따른 긍정적이든 부정적이든 보상을 제공합니다. (나도 잘하면 떡 좀 주라.) 그리고 강화학습은 모든 문제를 수학적으로 공식화합니다.

 

가장 기본이 되는 공식이 MDP(Markov Decision Process)입니다.

 

 

알아야 하는 것

 

• The Agent-Environment relationship
• Markov Property
• Markov Process and Markov chains
• Markov Reward Process (MRP)
• Bellman Equation
• Markov Reward Process

 

The Agent-Environment relationship

• Agent: 지능적 결정을 내리는 소프트웨어 프로그램이며 학습자입니다. agent는 행동으로 환경과 상호작용하고 행동에 따른 보상을 받습니다. $A_t$
• Environment: 해결해야 할 문제의 데모입니다. agent가 상호 작용할 실제 환경 또는 시뮬레이션된 환경을 가질 수 있습니다.
• State: 환경의 특정 time step에서 agent의 위치입니다. agent가 작업을 수행할 때마다 환경은 agent에게 보상을 제공하고 해당 작업을 수행하여 agent가 도달한 new state를 제공합니다.

 

Environment는 agent가 임의로 변경할 수 없는 모든 것을 의미합니다. Action은 agent가 배우기를 원하는 모든 결정의 집합이며, State는 action을 선택하는데 유용할 수 있는 모든 것이 됩니다.

 

환경의 모든 것을 agent가 모른다고 가정하지 않는다고 합니다. agent는 자신의 행동과 상태의 함수로 보상이 계산되는 방식을 알고 있어도 이 보상 계산은 환경의 일부로 간주됩니다. 보상을 임의로 받는 것이 아니기 때문입니다.

 

이걸 게임으로 비유할 때, 게임 플레이 방법을 알지만 여전히 해결할 수 없는 것처럼 보상의 개념은 최대화하는 것이 어려운 문제라고 설명할 수 있습니다.

 

따라서 agent-environment의 관계는 지식이 아니라 agent 제어의 한계를 나타냅니다. 

 

 

Markov Property

 

• Transition: 한 state에서 이동하는 것을 의미합니다.
• Transition Probability: agent가 한 state에서 다른 state로 이동할 확률을 의미합니다.

 

“Future is Independent of the past given the present”

 

 

'미래는 현재 주어진 과거와 무관하다'는 것이 Markov 속성이라고 하는데요. 이를 공식으로는

 

$P[S_{t+1}|S_t] = p[S_{t+1}|S_1, \dots, S_t]$

 

$S_t$는 agent의 현재 state를 나타내고 $S_{t+1}$은 다음 state를 나타냅니다. 위 방정식의 의미는 $S_t$에서 $S_{t+1}$로의 transition이 과거와 완전히 independent하다는 것입니다.

 

 

State Transition Probability

 

transition probability는 전환할 확률을 의미했고, $S_t$에서 $S_{t+1}$로의 Markov State, 즉 다른 successor state은 아래와 같이 주어집니다.

 

$P_{ss'} = P[S_{t+1}=s' | S_t = s]$

 

 

행렬의 각 행은 원래 state 또는 시작 state에서 successor state로 이동할 확률을 의미합니다. 따라서 각 행의 합은 1입니다.

 

Markov Process and Markov chains

 

Markov property가 있는 임의의 상태 $S_1, S_2, \dots S_n$의 sequence입니다. 따라서 기본적으로 Markov 속성이 있는 state sequence입니다.

 

state set($S$)와 transition probability matrix($P$)를 이용해 정의내립니다.

 

그렇다면 임의의 프로세스는 무엇을 의미하나요? (random process)

 

 

 

tree의 가장 자리는 transition probability를 의미합니다. 해당 chain에서 0.6 확률로 뛰고, 0.2 확률로 자고, 0.1 확률로 아이스크림을 먹습니다. 그러면 이 chain을 활용해 sampling 한다면?

 

• 잔다 - 달린다 - 아이스크림 먹는다 - 잔다
• 잔다 - 아이스크림 먹는다 - 아이스크림 또 먹음 - 달린다

 

(달리는 것 빼곤 최고의 삶...)

 

해당 두 시퀀스에서 체인을 실행할 때마다 임의의 state set($S$) 즉, Sleep, Ice-cream, Sleep을 얻습니다. 이걸 Markov process가 임의의 시퀀스 세트라고 불리는 이유라고 한다고 하는데, 더 봐야 알 것 같습니다.

 

또, 강화학습을 공부하다 보면 state, action 등 이외 아래 용어도 자주 등장하는데요.

 

 

Reward and Return

• Reward: agent가 일부 환경의 일부 상태에서 일부 작업을 수행할 때 받는 숫자 값입니다. 숫자 값은 agent의 작업에 따라 양수 혹은 음수입니다.
• Return: 강화학습은 agent가 받는 reward를 최대화하는데 항상 관심 있습니다! 따라서 agent가 환경에서 받는 reward의 총합을 return이라 합니다.

Return의 식

 

$G_t = r_{t+1} + r_{t+2} + \dots + r_T$

 

$r_{t+1}$은 한 state에서 다른 state로 이동하는 action을 수행하는 동안, time step $t_0$에서 받는 reward입니다. $r_{t+2}$는 다른 state로 이동하는 동작을 수행함으로서 time step $t_1$에서 agent가 받는 reward입니다. $r_T$는 agent가 마지막 step에서 다른 state로 이동하는 action을 수행하며 받는 보상입니다.

 

Episodic and Continuous Tasks

 

• Episodic tasks: 종료가 있는 작업을 의미합니다. → terminal state. 레이싱 게임에서 플레이하면 게임 오버나 완주가 있듯이요. 이를 episode라 부릅니다. 그리고 게임을 다시 시작하면, initial state에서 시작하므로 모든 episode는 independent합니다.
• Continuous tasks:끝이 없는 작업을 의미합니다. 즉, terminal state가 없습니다. 예를 들어, 코딩 배우기...

 

어쨌든 이런 유형의 작업은 합에서 무한으로의 반환이 필요하고, 이런 reward를 계산하기 위해 Discount factor($\gamma$) 개념이 등장합니다.

 

 

Discount Factor

• Discount factor($\gamma$): 이 할인율은 즉각적인 reward와 future reward를 얼마나 중요하게 생각할지에 기여합니다. 이는 연속적 작업에서 reward로 무한대를 피하는데 도움이 되는데요. 보통 0~1 사이의 값을 갖고, 0은 즉각적인 reward가 더 중요함을 1은 future reward가 더 중요함을 의미합니다. 실제로 0은 즉각적 reward만 고려하므로 학습하지 않고, 1은 무한대로 이어질 수 있는 미래 보상에 계속 적용됩니다. 따라서 최적 값은 0.2~0.8 사이입니다.

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \Sigma \gamma^k R_{t+k+1},$

 

로 식을 정의할 수 있습니다.

 

이 방정식은 나중에 Bellman 방정식 유도에 사용됩니다.

 

예를 들어, 일주일 동안 마셔야 할 물이 100L라고 가정할 때 $\gamma$ 매개변수로 두 가지 가능성을 살펴볼 것입니다.

 

$\gamma$가 0.8이면 $G_t = 100 + 80 + 64 ...$ 

 

감소가 별로 크지 않아서 일주일을 기다려야 한다는 것을 의미합니다. future reward에 관심이 있다는 뜻입니다.

 

$\gamma$가 0.2면 $G_t = 100 + 20 + 4...$ 

 

시간이 지날수록 reward가 현저히 낮아지며 감소가 매우 큽니다. 따라서 가치가 없으므로 일주일을 기다리지 않습니다. 따라서 $\gamma$가 0에 가까울수록 즉각적 보상이 미래보다 더 중요함을 의미합니다.

 

$\gamma$는 agent가 어떤 작업을 수행하는지에 따라 다릅니다. 약간 한 판당 이겨야 하는 오목이나 바둑 같은 게임은 즉각적인 보상인 승패가 중요하고, 보스를 물리쳐야 하는 게임은 future reward를 중시하는 뭐 그런 느낌 아닐까요?

 

Markov Reward Process (MRP)

 

Markov chain이 일련의 state(S)와 Transition probability matrix(P)를 사용했습니다. RL은 reward를 최대화하는 것에 관심이 있어서 reward를 추가해본다고 합니다.

 

Markov reward process: MDP는 value judgement가 있는 markov chain입니다. 기본적으로 agent가 있는 모든 state에서 value를 얻습니다.

 

수학적으로 MDP를 아래와 같이 정의합니다.

 

$R_s = E[R_{t+1} | S_t]$

 

이 방식은 특정 상태 $S_t$에서 얻는 reward의 양입니다. agent가 있는 특정 상태에서 즉각적 보상을 알려주는데 각 상태에서 받는 누적 보상을 최대화하는 방법으로 MRP를 살펴볼 예정입니다.

 

MRP를 $(S, P, R, \gamma)$로 정의합니다.

 

• $S$: State set
• $P$: Transition probability matrix
• $R$: Reward function
• $\gamma$: Discount factor

 

Markov Decision Process

 

이제 Bellmanm Equation과 MDP를 이해하기 위해 떠납니다.

 

Policy Function and Value Function

 

Value function은 agent가 특정 state에 있는 것이 얼마나 좋은지를 결정합니다. 이 결정을 위해 취하게 될 몇 가지 action에 의존하게 되는데요. 여기서 필요한 것이 policy(정책)입니다. policy는 특정 state에서 수행할 action을 정의합니다.

 

정책은 각 state($s \in S$)에 대한 action($a \in A$)에 대한 확률 분포를 정의하는 함수입니다. 시간 $t$의 agent가 정책 $p$를 따르는 경우 $\pi(a|s)$는 특정 time step($t$)에서 agent가 action을 취할 확률입니다.

 

RL에선 agent의 경험이 policy의 변화를 결정합니다.

 

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

 

즉, 어떤 상태에서 어떤 행동을 취하게 될 확률을 의미합니다.

 

이때, $\pi$를 따를 때, 상태 $s$의 값은 $s$에서 시작해서 최종 state에 도달할 때까지 다음 state에 대한 정책 $\pi$를 따르는 기댓값입니다.

 

이 value function을 공식화하면

 

 

입니다.

 

위 방정식은 정책 $\pi$를 사용해 state에서 시작해서 뒤의 state로 가는 기댓값을 제공합니다. 여기서 얻는 값은 expectation이지만, state의 value는 expectation이 아니라는 점을 주의해야 합니다.

 

시작 state가 class 2이고 class 3으로 이동한 다음, pass, sleep으로 이동한다고 가정합니다. (Class 2 > Class 3 > Pass > Sleep)

 

여기서의 기댓값은 discounter factor가 0.5일 때입니다.

 

$G_t = -2 + (-2 \times0.5) + 10 \times0.25 + 0 = -0.5$

 

(아 사실 계산을 이해 못했습니다.)

 

Reward에 discount factor 0.5를 곱해서 더한 후의 기댓값인데, ... 일단 pass

 

Bellman Equation for Value Function

벨만 방정식은 최적의 정책과 가치 함수를 찾는데 도움을 줍니다.

 

policy가 experience에 따라 달라지므로 모든 정책에 따라 다른 value function을 갖게 됩니다. 

 

여기서 optimal value function이란 다른 모든 value function과 비교해 최댓값을 제공하는 함수를 의미합니다.

 

벨만 방정식은 value function을 두 가지로 분해합니다.

 

• Immediate Reward, $R_{t+1}$
• Discounted value of successor states

 

$V(s) = E[R_{t+1} + \gamma v[S_{t+1} | S_t = s]$

 

위 공식이 벨만 방정식입니다.

 

$s$에서 $s'$로 이동한다고 가정할 때, 현재 state에 있는 것이 얼마나 좋았는지를 살펴봅니다.

 

따라서 state를 떠날 때 얻은 reward의 기대치에다가 그 다음 state($s'$)에서의 기대치를 더한 값입니다.

 

이렇게 백업 다이어그램으로 표현됩니다.

 

state $s$의 값이 궁금하고, state의 value는 우리가 그 state를 떠날 때 얻은 $r$에 우리가 이동한 state의 discount된 value에 이동할 transition probability를 곱한 값입니다.

 

$V(s) = R_s + \gamma \Sigma_{s' \in S} P_{ss'} v(s')$

 

위 식은 행렬로 표현하여 linear equation으로 표현될 수도 있습니다.

 

$v = R+\gamma P_v$

$(1-\gamma P)v = R$

$v = (1-\gamma P)^{-1}R$

 

여기서의 $v$는 있었던 state의 값으로, 즉각적 보상에 다음 state의 discount된 값에 해당 state로 이동할 확률을 곱한 값입니다.

 

이 계산의 시간 복잡도가 $O(n^3)$이고, 이를 위해 DP, Monte-Claro, TD-learning의 방법을 뒤에 배우게 됩니다.

 

 

Markov Decision Process

 

이는 decision이 있는 MRP입니다. 모든 것이 MRP와 동일하지만 이제 결정을 내리거나 조치를 취하는 기관이 추가된 것입니다.

 

$(S, A, P, R, \gamma)$의 튜플입니다.

 

• $S$: State set
• $A$: agent가 택할 수 있는 일련의 action
• $P$: Transition probability matrix
• $R$: agent의 action에 의해 누적된 Reward
• $\gamma$: Discount factor

 

Transition probability matrix

 

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

 

 

Reward function

 

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

 

이제 reward function은 action에 의존합니다.

 

지금까지 agent가 정책 $\pi$에 따라 일련의 state를 통과할 때 보상($r$)을 받는 것에 대해 이야기했다면, 실제로 Markov Decision Process(MDP)에서 정책은 결정을 내리는 메커니즘입니다.

 

MDP의 policy는 현재 state에 따라 다릅니다. 과거에 의존하지 않는다는 markov property를 따릅니다. 현재 state가 이미 과거를 갖고 있다고 생각합니다.

 

agent가 특정 state에 있는 것(State-value function)이 얼마나 좋은지를 보았고, 이제 state $s$가 Action-value function에서 정책 $\pi$에 따라 특정 action을 취하는지를 살펴봅니다.

 

State-action value function or Q-Function

 

이 함수 는 에이전트가 정책 $\pi$가 있는 state에서 action을 취하는 것이 얼마나 좋은지를 지정합니다 .

 

State-action value function은 아래와 같습니다.

 

$q_{\pi}(s,a) = E_{\pi} [G_t|S_t=s, A_t=a] = E_{\pi} [\Sigma_{k=0}^{\infty} \gamma^k R_{t+k+1}| S_t=s, A_t=a]$

 

입니다. 아까 위의 value function에서 action이 추가되었습니다. 기본적으로 정책 $\pi$인 state에서 특정 action을 수행하는 값을 알려줍니다.

 

MDP의 예시를 살펴보면,

 

 

아까 위의 그림에서 확률이 사라진 점을 볼 수 있습니다.

 

agent가 action을 선택하고, 일부 정책 $\pi$로 정의되어 그에 따른 reward를 받게 됩니다.

 

Summary

• Markov Processes
  • State
• Markov Reward Processes
  • State, Reward (Discount)
• Markov Decision Processes
  • State, Reward, Action

 

지금까지 MDP를 살펴보았고, 그 뒤 벨만 방정식을 더 자세히 볼 예정입니다.

 

틀린 부분 지적 부탁드리며, 아까 위에서 이해 못한 계산 과정을 아시는 분은 댓글 부탁드립니다!