강화학습 - (Markov Decision Process)

---

Markov Decision Process

MRP까지는 어느쪽의 보상이 더 좋은지에 관한 얘기였다면 MDP는 강화학습의 본목적인 action을 선택하는 과정이 포함된다. 따라서 튜플에 action의 A가 추가되어 <S,A,P,R,γ>로 나타낸다. Reward function은 R_s = E[R_t+1|S_t=s, A_t=a]가 된다. 보상이 action에도 종속되는 것을 볼 수 있다.

또한 각 상태에서 어떤 decision을 가져갈지 정하는 규칙을 policy라고 한다. 따라서 MDP는 각 상태에서 최적의 선택 즉 optimal policy를 찾는 것이 최종적인 목적이다.

---

Recycling Robot example

수집한 쓰레기 수에 따라 reward를 주고 움직여서 쓰레기를 찾거나 멈춰서 쓰레기를 누군가가 버려주기를 기다리는 행동을 선택할 수 있다. 기본적으로 search를 통해 쓰레기를 얻는 것의 보상이 wait해서 얻는 보상보다 크다. energy가 감소하면 energy를 채우기 위해 재충전하는 선택을 할 수도 있다. 만약 적절한 때에 재충전을 하지 못하여 로봇이 꺼져서 사람이 직접 충전기로 옮겨줘야 하는 상황이 오면 -3이라는 큰 패널티가 주어진다. 이때 recharge하는 동안은 보상을 얻을 수 없다.

이전에 다룬 student MRP도 아래와 같이 MDP로 표현할 수 있다.

이때 state-value function은 아래와 같고

action-value function은 아래와 같다.

---

Bellman Expected Equation

State-value와 action-value의 function을 연속적인 action의 선택을 고려하면 두식은 아래와 같이 표현되고 그 관계를 graph로 표현할 수 있다. 

같은 action을 선택했다고 해서 동등한 state-value를 가질 수는 없다. 이를 표현한 것이 아래의 graph와 식이다.

위의 식들을 이용하면 state-value와 action-value를 모델에서 주워진 parameter를 이용하여 계산할 수 있게된다.

이때 optimal한 policy를 찾는 것은 결국 state-value와 action-value의 최대값을 만드는 policy를 찾아가는 과정일 것이다.

미래 사건에 대한 확률과 그 가치에 대한 할인율까지 계산한 조금더 복잡한 식은 아래와 같이 쓸 수 있다.

---

Example

예시를 통해 살펴보면 이해하기가 더욱 쉽고 직관적이다.

위의 조건을 이용하여 그래프를 그리면 아래와 같다.

방금 살펴본 식을 이용하여 연산을 해보자.

 

s0에서의 state-value는 아래와 같다.

이때 그래프의 좌측에서만 조금 더 policy를 설정하고 action의 reward를 연장하여 그려주면 아래와 같다.

이렇게 되면 action-value도 아래와 같이 계산할 수 있게된다.

---