MDP란?

The environment used in RL is often defined as finite MDP

• MDP는 decision making problems을 모델링하는 수학적 프레임워크이다.
  → agent가 좋은 행동을 하기 위하는데 이를 수학적으로 푸는 것이다. decision making 자체를 수학적으로 모델링으로 바꿀수 있도록함.
• 배우는 것을 agent, 그 외 다른 모든 것들을 environment라고 한다.

A MDP decision process is a 4-tuple

• S : set of states
  

• A : set of actions

• P : 조건부 확률, 현재 state가 s이고 action a를 했을 때 다음 state가 s’이 될 확률
  

• R : state s에서 a 라는 action을 취해서 s’으로 갔을 때 부여받는 immediate Rewaed (or expected immediate reward)

MDP goal

• policy function π : state s에서 action state a를 선택할 때 사용하는 mapping function

• MDP는 good policy를 찾는 것
  → state s에서 가장 reward를 많이 받을 수 있는 acion이 뭐지? 를 판단

Example

s0에서 a1을 택하면 s2로 감. s2에서 a0을 택하면 0.4의 확률로 s0으로 가고 0.6의 확률로 s2로 감

→ $P_{a_0} (s_2, s_0)$ = 0.4

✅ The Agent – Environment Interface

In MDP, agent-environment interactions are repeated until the goal is reached
goal을 찾을 때까지 아래의 루프를 반복

• agent는 action을 선택한다
  어떤 state에서 acion을 취하는 것에 의해 reward를 받는다.

• time step t ,
  $S_t$ 를 기준으로 $A_t$라는 액션을 취함

  내가 취한 action에 의해 environment의 변화가 생김
  → 다음 state $S_{t+1}$로 넘어감 + 리워드 $R_{t+1}$을 생성
  

• trajectory that begins like
  s0에서 a0을 취하면 r1이 나오고 다시 s1에서 a1을 취하면 r2가 나오고…
  

In finite MDP, the sets of states, actions, and rewards all have a finite number of elements

한정된 element를 가지고 있다는 가정

• $R_t, S_t$는 내가 바로 직전에 무엇을 했느냐에만 영향을 받는다

• p(s’, r | s, a) : 현재 s에서 a를 한 상태에서 s’로 넘어가면서 r이라는 보상을 받을 확률
  

• a dynamic function p: S × R × S × A → [0,1] (→ 4개의 파라미터 사용)

  • p : probability distribution
  • r이 가능한 모든 리워드를 포함하고 s’이 모든 state를 포함하는 p를 다 더하면 1이다.

Markov property

• 바로 직전것에만 영향을 받는다
• probabilities p는 environment에서 어떻게 행동했을 때 얘가 나한테 뭘 줄 수 있는지를 정의하는 것
• $S_{t-1} , R_{t-1}$만 알고 있으면 이 다음에 결정될 것들을 알 수 있다. → 그렇기에 우리가 수학적으로 이것을 풀 수 있다.
  
• S에 이미 이전의 agent-environment interaction을 가지고 있다
  
  

💁‍♀️ Why do we use Markov Property?

It enables theoretical proofs of RL

• 바로 이전에만 고려해도 된다. 학습을 할 때 loop를 돌아야 하는데 수많은 루프를 계속 돌리려면 힘들다.

• 더 효율적으로 하기 위해서

• 이전 것들을 모두 고려해서 결정을 내리는 거나 이전것만 고려하는 거랑 똑같은 확률을 갖도록 한다 → 메모리 절약 가능

State transition and reward functions

four-argument dynamics functio**n : p(s′, r | s, a)

three-argument state-transition probability function : p(s′ | s, a)

• 현재의state에서 a라는 action을 했을 때 s’으로 넘어갈 확률이다.
• 내가 원하는 목적에 따라 argument 의 수를 줄일 수 있다.
• reward는 뭐를 받는 상관없고 일단 state로 넘어가는 거만 좀 알고 싶을 때
• r이 빠졌기 때문에 r에 대해 시그마를 해준다.
  → 받을 수 있는 모든 r에 대해 시그마를 해주면 p(s′, r | s, a) 와 같아 진다.
  

expected rewards for **state-action** pairs as a **two-argument function : r(s, a)

• 이전 state는 s, 거기서 취한 이전 action은 a 일 때, 기대되는(E) reward $R_t$
• s’을 뺐으니 시그마로 더해준다
  

expected rewards for state-action-next state triples as a **three**-argument function : r(s, a, s′)

• 이전 state는 s, 거기서 취한 이전 action은 a 으로 s’ state로 왔을 때 받을 것으로 예상되는 Reward $R_t$
  

✔ Example

주머니에 100원 500 동전에 각각 하나씩 들어있다. 각가의 동전을 뽑을 확률이 1/2씩이다.

→ 주머니에서 하나의 동전을 뽑았을 때 가져올 수 있는 기대값 : 0/5 100 + 0.5 500

→ 여기서 Reward : 100, 500 / Reward가 나올 확률 : 0.5

→ 이 둘을 곱하면 기댓값이 되는거고 시그마로 전체 모든 가능한 r에 대해 계산하는 것이다.

The Agent – Environment Interface Example – Recycling Robot

모바일 로봇이 비어있는 소다 캔을 오피스에서 주워담는다. 센서로 센싱해서 arm을 이용해 주어담는다. 로봇 등에는 충전이 필요한 배터리가 있다. 로봇에는 컨트롤 시스템이 있다. 캔을 어떻게 찾을지를 강화학습에 의해 결정한다.

• state defined by battery charge level : S = {high, low}
• action : A(high) = {search, wait} and A(low) = {search, wait, recharge}
• rewards are zero most of the time / empty can (r =1) / battery runs all the way down (r = -3)
  → 웬만하면 배터리 소모되게 하지 마렴
  
• state = high
  → 𝛂 : high 상태로 남을 확률
  → 1-𝛂 : low 상태로 전환될 확률
  
• state = low
  → β : low 상태로 남을 확률
  → 1 - β : 방전 상태로 전환될 확률

Reference

이 글은 강형엽 교수님의 게임공학[GE-23-1] 수업을 수강하고 정리한 내용입니다.
[mdpw] https://en.wikipedia.org/wiki/Markov_decision_process
[sutton] Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press