[강화학습] Lec.2 Markov decision process(MDP)

MDP

환경이 observable할때, 현재 state가 process를 완전히 특정 지을 수 있다. 

 

Markov process

 - S : set of states

 - P : state transition probability matrix

 

states가 총 n 개일 때, State Transition Matrix

 

Terminal state : Markov process의 마지막 state, 위 그림에서는 Sleep

episodes : MP에서 특정 state에서 terminal state까지의 경로 set, MP에서의 random sample

 

---

 

Markov Reward Process

Markov process에서 R(reward)과 r가 추가

A Markov Reward Process is a tuple <S, P , R , r >
S is a nite set of states
P is a state transition probability matrix,
R is a reward function, Rs = E[Rt+1 | St = s]  > reward가 state에서 정의되고 주어진다.
 is a discount factor,   r  > 0,1사이값, 감가상각 역할을 한다. 수학적 편리성을 위함

 

 

Return

특정 에피소드에서 총 reward의 감가상각 합/ 함수 형태

 

Value function

 

state에서 정의되는 return의 기대값

 

 

 

 

Bellman Equation

 

value function 계산이 매우 복잡하므로 이를 간단하게 바꿔주는 방정식. 모든 value function은 이 방정식에 기반해서 계산된다. 즉, value function은 reward랑 다음 step의 value function에 합으로 표현될 수 있다.

 

예를 들어, 위 그림처럼 4.3이라는 state에 value가 계산된 과정은 해당 state reward -2에 다음 state로 갈 transition prob에 해당 state value를 곱해서 아래와 같이 구해지게된다.

 

가만 보면, state들 끼리 value가 서로의 value를 결정하는데 interaction을 주고 있으므로 바로 value를 구하기 쉽지 않다. 이를 matrix notation으로 표현 해보면,

 

v : value, R : reward, r : discount factor, P : trainsit prob matrix

위와 같고, 역행렬을 이용해 다음과 같이 value function을 한번에 구할 수 있다.

 

하지만, computational cost가 낮은편이 아니므로(n^3), state 수가 적은 MRPs에서만 가능하다.

 

---

 

Markov decision process (MDP)

 > MRP에서 action이 추가된 process

 > MRP랑 다르게 state가 아닌 action마다 reward를 받고, state와 action에 의해 정의된다. 밑에 그림에서 빨간색 action들 밑에 R값들

 > action을 한다고 반드시 state를 이동하는게 아니라, action이 가지고 있는 transit prob에 의해 이동, 예를 들어 밑에 그림에서 Pub이라는 action을 하면 0.4의 확률로 가운데 state로 이동한다. 

 

 

Policy

- 특정 state에서 action을 취할 확률분포, 현재 state에만 의존하고 stationary하다(time-independent). (Markov property 때문)

- Agent에게 주어지고, 이 policy가 고정되면, MDP의 state sequence는 MP가 된다.

 

Value Function

 

1. state-value function

2. action-value function

Bellman Expectation Equation을 통해 q와 v를 다음과 같이 decomposition 할 수 있다.

 

 

q는 state와 action이 주어져야 정의되므로,