마르코프 결정 프로세스 (Markov decision Processes)

수강일시: 2021.01.20

출처: kmooc SNU048

 

www.kmooc.kr/courses/course-v1:SNUk+SNU048_011k+2020_T2/course/

강좌 | SNU048_011k | K-MOOC

 

마르코프 결정 과정

지난시간에 배운 makov reward system에서 A(set of actions)가 추가 되었다.

즉 agent가 취할 수 있는 action set이 추가된 것인데 이에따라 transition function과 reward function도 변화하게 되었다.

왜냐하면, 기존에는 Transition function의 경우 한 state에서 다른 state로 가는 확률분포를 표현했다고 하면, 지금은 어떤 state에서 어떤 action을 취했을 때 어떤 state로 가는것이 state transition으로 정의가 되기 때문에 정의역이 조금씩 바뀌게 된다. 즉 정의역이 action set에 대한 곱집합으로 표현이 됐다.

 

이에따라 policy를 정의해 보도록 하자.

policy는 history가 아닌 현재 state에 의존적이다.

value function은 policy가 주어졌을 때 결정이 된다. 따라서 policy가 바뀌면 value function도 바뀐다.

 

action value function(Q pi)은 어떤 action을 취했을때의 expected return으로 볼 수 있다.

 

벨만1. bellman expectation equation

기존의 Value Function은 모든 상황에 대해 각 Reward 값을 구한 후 모두 더한 값인데 action이 추가된 MDP에서는 적절하지 않다. 따라서 현재 state 의 value function과 다음 state의 value function의 상관관계를 나타낸 벨만 equation을 이용해서 나타내고자 한다.

 

벨만 equation을 통해 V와 Q의 관계를 밝히고자 하는데

 

Vπ에서 qπ(s, a)는 상태 s에서 행동 a를 했을 때 예상되는 보상이고 π(a | s)는 상태 s에서 행동 a를 할 확률이다.

따라서 이의 sum이 Vπ가 된다.

Qπ는 Rs s에서 a를 했을 때의 reaward  γ는 discount factor

Pss'는 s state에서 행동 a를 했을 때 s′가 될 확률

Vπ는상태 s′에서 예상되는 보상으로 나타낸다.

이러한 표현방식의 문제점은 V는 Q로 Q는 V로 나타내야한다는것이고 두 식을 이용하여

오른쪽의식을 얻을 수 있다.

 

이를 계산하기위해 matrix form으로 표현하였다.

다만 시간복잡도가 매우 높은 작업이므로 DP나 몬테카를로 evaluation을 이용해 풀 수 있다.

다음 게시물에서 dp방식으로 위 식을 계산해보도록 하겠습니다.

 

 

다음으로 optimal value function에 대해 보자.

optimal policy는 optimal value function을 이용해 비교적 쉽게 구할 수 있다.