MDP ( Markov Decision Process )

Markov Decision Process

 

의사결정 문제를 수학적으로 모델링 하는 방법이다.

특정 환경에서 에이전트가 어떻게 행동해야 하는지를 결정하기 위해 사용되는 방법으로. 임의의 수학공식 이라기 보다는 이러한 방법론 이 있다 정도로 받아드리면 된다.

 

환경의 현재 상태와 미래 상태간의 전이 가능성을 고려하여 최적의 결정을 내리는데 사용된다.

 

연속적으로 현재 가치에 따라 의사를 결정하는 방식이다.

 

여러개의 Action을 연속적으로 수행하여 S0의 동작 a0이 있고, 결과가 S1, S1의 동작이 a1 이라고 한다면,

 

S1에는 S0 -> a0의 상태0과 행동0을 포함한다고 볼 수 있다.

 

이러한 과정을 반복하여 결과를 뽑아내는것을 MDP방식 이라고 한다.

---

요소

 

상태(State) S

• 시스템의 현재 상황, 상태를 말한다.
• 에이전트의 위치, 시뮬레이션중인 상황의 현재 판도 등.

행동(Action) A

• 에이전트가 취할 수 있는 선택지 를 말한다.
• 에이전트의 이동 방향, 시뮬레이션의 다음 수

전이 확률 (Transition Probability) P

• 특정 상태에서 특정 행동을 취했을 때 다음 상태로 전이될 확률을 말한다.
• 에이전트가 오른쪽 으로 이동했을 때 다음 임의의 위치로 이동할 확률

보상 (Reward) R

 

의 크게 4가지 요소로 정리할 수 있다.

---

표현

 

MDP는 보통 (S, A, P, R)로 표현된다.

 

예시

 $ P(s^{'}|s,a) $

• 상태 s에서 행동 a를 했을 때 상태  $ s^{'} $ 로 전이될 확률

 $ R(s,a,s_{'}) $

• 상태 s에서 행동 a를 해서 상태 $ s^{'} $ 로 전이될 때 얻는 보상

 

정책 ( Policy )

각 상태에서 어떤 행동을 취할지를 결정하는 전략이다.

이것은 확률일수도 있고 결정일수도 있다. 정책은 보통 $ \pi (a|s) $ 로 표현된다.

상태 s에서 행동 a를 선택할 확률을 의미한다.

 

파이가 쓰이는이유는 딱히 없다; 그냥 파이라고 쓰고 정책이라고 읽자.

---

가치함수 (Value Function)

가치함수는 특정 정책을 따를 때 얻을것 으로 기대되는 보상의 총 합이다.

배가고플때 밥을 먹으러 식당으로 걸어가거나, 부엌으로 간다고 생각해보자.

 

밥을 먹는다 가 원하는 결과이고, 우리는 밥을 먹으러 가는 과정 자체가 보상가중치가 더해진다고 볼 수 있다.

이때, 식당을 가는행동이 나타나면 부엌에서 직접 밥을 해먹는것 보다 식당에서 먹는게더 맛있다고 여기기 때문에 식당의 가중치가 더 크다고 볼 수 있고,

 

부엌으로 간다면 부엌에서 해먹는 음식이 식당보다 맛있거나 임의의 다른 경재적 이득을 본다고 볼 수 있다.

 

이러한 결과를 유도하기 위해 보상을 주는방식이 가치함수 이다.

 

이는 두가지로 나눌 수 있다.

 

상태 가치 함수 ( State Value Function )

• 특정 상태에서 시작하여 정책을 따를 떄 얻는 기대보상을 말한다.
• $ V^{\pi}(s) $ 로 표현된다.

행동 가치 함수 ( Action Value Function )

• 특정 상태에서 특정 행동을 취하고 그 이후 정책을 따를 때 얻을 수 있는 기대보상을 말한다.
• $ Q^{\pi}(s,a) $ 로 표현된다.

---

벨만 방정식 ( Bellman Equation )

 

MDP에서 최적의 정책을 찾기위한 기본 도구이다. 함수나 수식이라고 표현하기는 하지만,

함수라고 볼수도 있지만, 이해하기 쉽게 생각하자면 가이드라인 이라고 생각하자.

 

상태 가치 함수:

$ V^{\pi}(s) = \sum_{a} \pi(a|s) \sum_{s^{'}}P(s^{'}|s,a)\left [ R(s,a,s^{'}) + \gamma V^{\pi}(s^{'}) \right ] $

 

행동 가치 함수:
$ Q^{\pi}(s,a) = \sum_{s^{'}} P(s^{'}|s,a)\left [ R(s,a,s^{'}) + \gamma \sum_{a^{'}}\pi(a^{'}|s^{'})Q^{\pi}(s^{'},a^{'}) \right ] $

 

$ V^{\pi}(s) $ 

상태 s의 가치로, 주어진 정책 $ \pi $를 따를 때 상태 s에서 시작하여 얻을 것으로 기대되는 총 보상의 현재 가치

 

$ \pi(a|s) $

정책 $ \pi $가상태 s에서 행동 a를 선택할 확률이다. 정책은 각 상태에서 어떤 행동을 취할지 결정하는 확률분포

 

a

에이전트가 선택할 수 있는 행동

 

$ \sum_{a} , \sum_{s} $

상태 a, s에서 가능한 모든 행동에 합을 구한다.

 

$ P(s^{'}|s,a) $

상태 s에서 행동 a를 했을 때, 다음 상태 $ s^{'} $ 로 전이될 확률이다. 이는 상태 전이 확률 로 불린다.

 

$ R(s,a,s^{'}) $

상태 s에서 행동 a를 취했을 때, 다음 상태 $ s^{'} $로 전이

 

$ \gamma $

 

할인 인수(discount factor)로, 미래 보상의 현재 가치에대한 가중치를 나타낸다.

감마는 0과 1 사이를 가지며 미래보상이 현재 보상에 비해 얼마나 중요한지를 나타낸다.

 

벨만 방정식은, 정책 파이를 따를 때 상태 또는 행동의 가치를 나타내는 방정식이다.

 

상태가치 함수는 특정 상태의 가치를 나타내며, 행동 가치 하뭇는 특정 상태에서 특정 행동의 가치를 나타낸다.

이러한 방정식들은 상태, 행동, 보상, 전이확률, 할인인수 등을 통해 상태 또는 행동의 기대가치를 계산하는데 사용된다.