CH2. 마르코프 결정 프로세스

[바닥부터 배우는 강화학습] CH2. 마르코프 결정 프로세스을 읽고 정리한 내용입니다.


강화 학습에서 문제를 잘 정의하려면 주어진 문제를 MDP(Markov Decision Process)의 형태로 만들어야 한다.

마르코프 프로세스(Markov Process)

  • 미리 정의된 어떤 확률 분포를 따라서 상태와 상태 사이를 이동하는 프로세스
    • 어떤 state에 도착했을 때, 다음 state가 어디가 될지 각각에 해당되는 확률이 있고 그 확률에 따라 다음 state가 결정됨
    • 하나의 상태에서 뻗어 나가는 화살표의 합은 항상 100%다
\[MP \equiv (S,P)\]
  • 상태의 집합 $S$
    • 가능한 상태들을 모두 모아 놓은 집합
    • $S = {s_0, s_1, … }$
  • 전이 확률 행렬 $P$
    • transition probability $P_{SS’}$는 상태 $S$에서 다음 상태 $S’$에 도착할 확률을 나타낸다.
    • 조건부 확률 개념을 이용해서 표현해보면, $P_{SS’} = \mathbb{P}[S_{t+1}=s’|S_t=s]$
    • 즉, 시점 t에서 상태가 s였다면 t+1에서의 상태가 s’이 될 확률을 구한 것.

마르코프 성질

  • 미래는 오로지 현재에 의해 결정된다.
  • 마르코프 프로세스에서 다음 상태 $s_{t+1}$이 될 확률을 계산하려면 현재의 상태 $s_t$가 무엇인지만 주어지면 충분하다.
    • 이전에 방문했던 state들은 t+1 시점에 아무런 영향을 주지 못한다.

마르코프 리워드 프로세스 (Markov Reward Process)

MRP를 정의하기 위해서는 reward function $R$과 damping factor $\gamma$ 가 필요하다. \(MRP \equiv (S,P,R,\gamma)\)

  • S, P는 이전과 동일
  • 보상 함수 $R$
    • 어떤 state s에 도착했을 때 받게 되는 보상
    • \[R = \mathbb{E}[R_t|S_t=s]\]
    • 특정 상태에 도달했을 때 받는 보상이 매번 조금씩 다를 수 있기 때문에 기댓값으로 표현한다
  • damping factor $\gamma$
    • 0과 1 사이의 숫자
    • 미래 얻을 보상에 비해 당장 얻는 보상을 얼마나 더 중요하게 여길 것인지를 나타내는 파라미터
    • 미래에 얻을 보상의 값에 $\gamma$가 여러번 곱해지는 형식

감쇠된 보상의 합, Return

  • MRP에서는 MP와 다르게 상태가 바뀔 때마다 해당하는 보상을 얻음
  • episode : $s_0$에서 종료 상태 $s_r$까지 가는 여정
  • Return은 아래와 같이 정의됨. \(G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ...\)
  • 위 식에 따라 리턴은 t시점부터 미래에 받을 감쇠된 보상의 합이 된다.
    • 현재에서 멀어질수록 $\gamma$가 여러번 곱해지기 때문에
    • 따라서 $\gamma$의 크기를 통해 미래 얻게 될 보상에 비해 현재 얻는 보상에 가중치를 줄 수 있다

$\gamma$의 필요성

  • 만일 감마가 0이라면 미래의 보상은 모두 0이 되고, 감마가 1이라면 현재의 보상과 미래의 보상이 완전히 대등해진다.
  • 수학적 편리성, 사람의 선호 반영, 미래에 대한 불확실성 반영

에피소드의 샘플링

  • 에피소드가 어떻게 sampling되냐에 따라 리턴은 달라진다
  • Monte-Carlo 접근법

State Value Function (상태 가치 함수)

에피소드마다 리턴이 다르기 때문에 특정 state s의 v는 기댓값을 이용하여 정의함.

\[v(s) = \mathbb{E}[G_t|S_t = s]\]

마르코프 결정 프로세스

MDP의 정의

  • MDP는 MRP에 에이전트가 정해진 것이다. \(MDP \equiv (S,A,P,R,\gamma)\)

  • 전이 확률 행렬 P는 에이전트가 바꿔줄 수 있는 부분이 아니며, 같은 상태에서 같은 액션을 해도 확률적으로 다음 상태가 달라질 수 있다.
    이를 수식으로 표현하면 $ P^a_{ss’} = \mathbb{P}[S_{t+1}=s’|S_t=s, A_t=a] $

  • 보상 함수 R : \(R^a_s = \mathbb{E}[R_{t+1}|S_t=s, A_t=a]\)

정책함수와 2가지 가치함수

  • 정책 함수 : 각 상태에서 어떤 액션을 선택할지 정해주는 함수
    $ \pi(a|s) = \mathbb{P}[A_t=a|S_t=s] $

  • 상태 가치 함수(state value function) : 어떤 상태가 주어졌을 때 그 상태를 평가해주는 함수
    $ v_\pi (s) = \mathbb{E}\pi [r{t+1} + \gamma r_{t+2} + … | S_t =s] $

  • 액션 가치 함수(state-action value function) : s에서 a를 선택하고, 그 이후에는 $\pi$를 따라서 움직일 때 얻는 리턴의 기댓값
    $ q_\pi (s,a) = \mathbb{E}_\pi [G_t|S_t=s, A_t=a] $

Prediction과 Control

  • prediction : $\pi$가 주어졌을 때 각 상태의 벨류를 평가하는 문제
  • control : 최적 policy를 찾는 문제. 즉, 이 세상에 모든 $\pi$ 중에서 가장 기대 리턴이 큰 $\pi$를 찾는다.