[3] Finite Markov Decision Process

Reinforcement Learning : An Introduction - [3] Finite Markov Decision Process

Chapter 3. Finite Markov Decision Process

Markov Process

마르코브 프로세스란, 시간 연속적인 state series 들이 과거의 state 의 영향을 받는
조건부 확률로 정의됨을 의미합니다.

Markov Reward Process

마르코브 프로세스에 reward 의 개념(과 감가상각)을 추가한 것이 마르코브 reward process 입니다.

• Return

  : total discount reward
  전체 reward를 시간에 따른 감가상각을 포함하여 합산 한 것이 return 입니다.

• value function

  : expected return starting from state s
  상태 s 에서 부터 시작할때 기대되는 return 값을 말합니다.

  
  cf. 이웅원님 글
  value function을 구하는 하나의 방법을 예를 들어보겠습니다.
  Value function은 return(실재 경험을 통해서 받은 reward의 discounted
  amount)의 expectation이기 때문에 마치 주사위를 던져 보듯이 던져 보면서 expectation 값을 구할 수 있습니다.

  계속 그 state로부터 시작되거나 그 state를 지나가는 episode를 try해보면서 얻어진 reward들에 대한 data들로 그 value function에 점점 다가갈 수 있는데 사실 주사위도 무한번 던져야 1/3이라는 true expectation값을 가지듯이 value function 또한 무한 히 try를 해봐야 true value function을 찾을 수 있을 것 입니다. 그렇다면 어떻게 적 당한 선을 찾아서 "이 정도는 true 값이라고 하자"라고 결정을 내릴까요? 이 또한 생각해봐야 할 점인 것 같습니다.

  -> 따라서 true value function 은 일반적으로 알 수 없다.

• bellman equation
  

  Bellman equation을 통해서 현재 시점의 value는 현재의 보상과 다음 시점의 value로 표현 할 수 있다는 것을 알수 있게 되었습니다.

• solving bellman equation

  이 bellman equation 을 풀기 위해서는 어떻게 해야할까요?
  

  위와 같이 value fuction equation 은 state-transition matrix $P_ss$를 통해서 표현이 가능합니다.

이를 위처럼 행렬식으로 전개하여 위처럼 이렇게 표현할 수 있게 되면 linear 할 시 역행렬로 value function 에 대해 풀 수 있습니다. (작은 MRPs 의 경우)

이와 달리, iterative 하게 MRPs 를 풀수 있는 DP, 몬테카를로, TD 방식들이 있습니다.

Markov Decision Process

Rewards process 와 달라진 점은 action 에 대한 고려가 들어갔다는 점입니다. action 을 선택해야하기 때문에 decision 의 개념이 들어갑니다.

• policy

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

Policy 는 state 가 주어졌을 때 action 들이 일어날 확률을 정의합니다. 이는 deterministic 할 수도 있지만 stochastic 할 수도 있습니다.

policy를 고려시, state transition 과 reward function은 아래와 같이 변화합니다.

• state -value function

value function 에 policy 를 반영하게 되면 state s 인 조건에서 policy 를 따르는 기대되는 보상들의 합이 됩니다.

• action - value function

이는 action 의 개념이 추가 되어 state s 이면서 action a 인 조건에서 policy 를 따르는 기대되는 보상의 합 입니다.

->이 둘의 차이에 대하여 아래와 같은 관계가 있습니다.

**** 조금더 이야기해볼것

• bellman equation
  

policy 를 반영한 state-value, action-value function 은 위와 같이 표현 할 수 있습니다.

• find optimal policy
  

  optimal policy 의 경우 위와 같은 조건이 필요합니다.
  

따라서 optimal 한 value function 을 가질 수 있는 policy를 optimal policy 라고 한다면, 이는 다른 policy 보다 항상 더 같거나 큰 value / action-value function을 가지는 policy 일 것입니다.

이러한 optimal policy 를 구하기 위해서는 optimal value / action-value function 을 구해야 하며, 이에 다시 bellman equation 이 도입 됩니다.

• Bellman Optimality equation
  

이를 살펴보면 state-value funtion 에서는 action 에 따른 reward 가 maximize 되는 action 을 선택하는 것이 opitmal 이 되며,

action - value function 에서는 action a 중 선택하였을 때 해당 q를 maximize 할 수 있는 action 을 선택하는 것이 optimal 이다.

-> 더 이야기 해보기

• solving bellman optimality equation
  

bellman optimality eqaton 은 linear 하지 않기 때문에 close form 으로 구현되지 않고, iterative solution 으로만 구할 수 있다. 여러가지 방식의 솔루션들이 존재한다.