[LG Aimer] 강화학습 - MDP

강화 학습은 주로 Markov Desion Process(MDP)라는 확률 모델로 표현된다. MDP는 의사결정 과정을 확률과 그래프를 이용하여 모델링한 것으로, 시간 t에서의 상태는 t-1에서의 상태에만 영향을 받는다 라는 가정을 갖는다.

• Markov: 의사 결정을 내리기 위해 필요한 모든 정보를 관측
• Decision: 행동
• Process: 시간에 따라 바뀌는 그런 시스템에서 문제를 푸는 과정

강화학습(Reinforcement Learning)

1. Markov Reward Process
   Markov Process의 각 state에서 Reward를 추가해 확장한 것 <S,P,R,y>라는 4-tuple로 표현

• S: state의 집합

• P: 각 요소가 $p(s'|S)=Pr(S_{(t+1)}=s'|S_t=s)$인 집합 $p(s'|S)$는 현재 상태s에서 s'로 이동할 확률이며, transition Probablity라고 한다.

• R: 각 요소가 $r(S)=E[R_{t+1}|S_t=s]$인 집합. r(s)는 state s에서 얻는 reward의미

• y: 즉각적으로 얻는 reward와 미래에 얻는 reward간의 중요도를 조절하는 변수(discount factor라 함)

  Return

  Return $G_t$는 시간 t이후부터 얻을 수 있는 reward의 합을 의미, discount factory Y를 통해 식이 정의된다
  $v(s)=E[G_t|S_t=s]$

  • v(s)는 궁극적인 목표 달성을 위해 state S가 얼마나 좋은 상태인지 나타낸다.
    재귀: $v(s) = R_{t+1}+Y\sum_{s'\in S} P(s'|s)v(s')$

  ---

2. Markov Decision Process
   MDP는 Markov Decision Process에 action이라는 요소가 추가된 모델로써, <S,A,P,R,y>라는 tuple로 정의

• 학습하고자 하는 시스템 등에 해당하는 agent는 $S_t$에 해당하는 state에서 $A_t$에 해당하는 action을 수행한다.
• 엔진 등에 해당하는 environmemt는 다음 state에 해당하는 $S_{t+1}$과 상응하는 reward $R_{t+1}$을 agent에게 반환한다.
  목적: MDP로 정의된 문제에 대해 각 state마다 전체적인 reward를 최대화하려는 action이 무엇인지 결정
  $\pi(a|s)=Pr(A_t=a|S_t=s)$
• $\pi$: 각각의 state마다 acion의 분포(action이 선택될 확률)를 표현하는 함수
• MDP가 주어진 $\pi$를 따를 때, S에서 s'로 이동할 확률:
  $P_{\pi}(s'|s)=\sum_{a\in A} \pi(a|s)p(s'|s,a)$
• s에서 얻을 수 있는 reward식 계산: $r_{\pi}(s)=\sum_{a\in A}r(a|s)p(s,a)$