[AI]Markov Decision Process(MDP)

Markov decision process란

 

observable, stochastic environment with a Markovian transition model and additive rewards

라는 것인데

예시를 보며 알아보자.

 

다음과 같은 상황이 주어졌다고 하자.

+1, -1이 terminal state이고 reward가 각각 +1, -1이다.

또한 세가지 방향으로 이동가능한데 전진, 좌회전, 우회전 각각 0.8, 0.1, 0.1의 확률로 선택된다.

terminal state를 제외한 모든 state는 reward가 -0.04이다,

terminal state로 가는 방법에 대해 찾아보는 문제이다.

위 수식을 설명을 해보면

T(s, a, s' ) ≡ P(s'|s, a) 는  state s 에서 action a를 취하여 state s'으로 가는 확률을 의미한다.

R(s) (or R(s, a), R(s, a, s' ))는 state s 에서의 reward를 나타내어주는 함수이다.

 

우리의 목적은 최적의 sequence를 찾아내는 것이다,

MDP 방법에서는 optimal policy ㅠ(s)을 찾는데  모든 가능한 state s를 위한 best action으로 찾는다

그 이유는 어떤 state에서 terminate가 될지 모르기 때문에 모든 가능한 state 를 봐야한다.

 

여기서 구하는 optimal policy는 Expected sum of rewards 값을 최대화 한다고 말한다.

 

다음 그림은 terminal state를 제외한 state에서의 reward 값이 -0.04일 때의 optimal policy이다.

 

여기서 reward 값을 수정해주면 optimal policy도 바뀌게 되는데 다음과 같다.

 

간단히 설명해 보자면 r 즉, reward 값이 작아질 수록 map에서 빨리 탈출하는 것이 좋으므로 terminal state로 가기 위한 경향이 강하게 나타나는 반면

reward 값이 상대적으로 크거나, 양수이면 terminate 되려고 하지 않기 때문에 map 안에 계속 머무르려고 하는 경향이 강하게 나타나는 것을 확인할 수 있다.

 

대충 optimal policy를 구했다면 state의 sequence 들을 구해볼 수 있는데,

이러한 sequence들 사이에서도 선택을 해야 하므로 preference들을 알아볼 필요가 있다.

그렇다면 state sequence의 utility를 구해보자.

구하는 방법으로 두가지가 있는데

1. additive utility function

:말 그대로 각각의 reward 값을 그냥 더하는 것이다.

2.Discounted utility function

:0~1사이의 값의 요소를 각각의 reward에 곱해서 더하는 것이다,

 

Utility of State는 다음과 같이 정의 된다.

state의 utility 값들이 주어지면 best action을 고르는 것은

immediate successors의 maximum expected utility를 고르는 것이므로 MEU 이다.

 

하지만 이 방법에는 문제점이 존재한다.

만약 Lifetime이 무한대라면 additive utility들도 무한대가 될 것이다.

 

해결방안은 다음과 같이 3가지가 있을 수 있다.

optimal policy와 utility of a state 구하는 방법은 결국 아래와 같다.

위에서 나온 그림의 (1,1)좌표에서의 utility를 구하는 과정이다.

각각 차례대로 방향이 위로보는 경우, 왼쪽으로 보는 경우, 아래로 보는 경우, 오른쪽으로 보는 경우이다.

만약 벽으로 나아갈 수 없는 상황이면 s' 을 (1,1)로 표현하는 것이다.

 

이어서 Action-utility function(Q-function)이라는 것도 있는데

이는 expected utility of taking a given action in a given state를 표현한다.

U(s)란 결국 state s에서 expected utility를 최대로 하는 action을  나타내는 것이다.

 

이 Q function을 이용한 Optimal policy와 bellman equation은 다음과 같다.