마르코프 결정 프로세스

강화 학습 스터디) 노승은 저자의 바닥부터 배우는 강화학습 책 기반의 정리입니다.

강화 학습은 순차적 의사결정 문제를 푸는 것임. 순차적 의사결정 문제는 MDP(Markov Decision Process)라는 개념을 통해 더 정확하게 표현할 수 있음

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

chatGPT가 생성한 MP의 모습. 다소 혼란스럽다.

• 미리 정의된 어떤 확률 분포를 따라서 상태와 상태 사이를 이동해 다니는 여정
• 어떤 상태에 도착하게 되면 그 상태에서 다음 상태가 어디가 될지 각각에 해당하는 확률이 있고, 그에 따라 다음 상태가 정해짐
• 하나의 상태에서 다른 여러 상태로 전이할 확률의 합은 1
• [Notation]
  • $MP \equiv (S,P)$
  • S: 상태 집합(가능한 상태를 모두 모아놓은 집합)
    • 상태가 5개면 $S = s_{1}, …, s_{5}$
  • P: 전이 확률 행렬
    • 전이 확률(transition probability) $P_{s,s’}$는 상태 s에서 다음 상태 s’에 도착할 확률을 가리킴
    • 조건부 확률로 표현 가능 $P_{s,s’} = P[S_{t+1} = s’ | S_{t} = s]$
    • 가능한 모든 상태에 대해 값을 가질 수 있어서 행렬로 표현 가능

 

마르코프 성질(Markov property)

마르코프 프로세스는 마르코프 성질을 따름

$P[s_{t+1}|s_{t}] = P[s_{t+1}|s_{1}, s_{2}, …, s_{t}]$ “미래는 오로지 현재에 의해 결정된다”

이는 각 상태에서 다른 상태로 전이될 확률을 우리가 다 알고 있기 때문에 성립함

따라서 $s_{t}$ 이전에 방문 했던 다른 여러 상태는 무시하고, $s_{t}$ 만 가지고 다음 상태로 갈 확률을 계산할 수 있음

어떤 상태를 어떻게 거쳐서 왔든 다음 상태가 $s_{t+1}$이 될 확률에는 변함이 없다

강화 학습 적용에 있어서 에이전트에게 주어지고 있는 상태가 마르코프 상태인지 따져보는 것은 이론적으로도, 또 응용의 측면에서도 정말 중요한 과정→ 어떤 현상을 마르코프 프로세스로 모델링 하려면 상태가 마르코프 해야하며, 단일 상태 정보만으로도 정보가 충분하도록 상태를 구성해야 함

하나의 상태로도 다음 상태를 정의할 수 있을 정도로 정보가 충분한가에 대한 질문을 던져서 평가해보면 됨!

마르코프한 상태: 체스

• 체스 게임에서 체스 판 위에 흑과 백의 말들이 자리하고 있고, 현재 백의 차례인 상황을 가정
• 이런 상황에 대한 사진 한장으로도 다음에 어떤 수를 둘지 정할 수 있음(과거 백의 상황과는 상관이 없음), 즉 정보가 하나의 상태로도 충분함

마르코프하지 않은 상태: 자동차 운전자의 상태

• 특정 시점의 사진을 가지고 운전을 해야하는 상황에서, 브레이크를 밟아야 하는지, 가속을 해야하는지 전혀 알 수 없음 → 과거의 기록이 필요(예: 1초 전의 사진, 2초 전의 사진, … 10초 전의 사진을 묶어서 → 현재 앞으로 가고 있는지, 속도와 가속도는 몇 인지 알 수 있음)
  • 영국의 딥마인드사에서 발표한 연구에서도 비디오 게임을 플레이하는 인공 지능을 학습시킬 때, 시점 t에서의 이미지와 함께 t-1, t-2, t-3의 과거 이미지를 엮어서 상태로 제공했음 → 상태를 조금이라도 더 마르코프하게 만들기 위함
  •  

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

마르코프 프로세스에 보상의 개념을 추가, 즉 각 상태에 대응되는 보상 값이 있음

• $MRP \equiv (S,P, R, \gamma)$
  • 보상 함수 $R=\mathbb{E}[R_{t}|S_{t}=s]$은 어떤 상태 S에 도착했을 때 받게 되는 보상을 의미
  • 기댓값이 등장한 이유: 특정 상태에 도달했을 때 받는 보상이 매번 조금씩 다를 수도 있기 때문(특정 상태에 도착했을 때 받는 보상이 확률적일 경우)
  • 감쇠 인자 $\gamma$: 0~1 사이의 숫자. 강화 학습에서 미래 얻을 보상에 비해 당장 얻는 보상을 얼마나 더 중요하게 여길 것인지를 나타내는 파라미터
  • 미래 시점으로 갈 수록 $\gamma$를 더 자주 곱해져 그 값을 작게 만드는 역할을 함
    • Return: 현재부터 미래 얻게 될 보상의 합
      • 에피소드 : $s_{0}$에서 시작하여 $s_{t}$로 가는 여정
      • return $G_{t}$$=R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + …$
        • 현재 time step이 t 일 때 그 이후에 발생하는 모든 보상의 값의 합
        • 강화 학습은 보상을 최대화 하도록 학습하는 것이 목적이라고 하는 것은 엄밀하게 틀림
        • 강화 학습은 보상이 아니라 return 을 최대화하도록 학습하는 것이 궁극의 목표
        • 리턴이 과거의 보상을 고려하지 않고 미래의 보상을 통해서 정의 된다는 것
          • 구글에 입사하기 위한 준비 과정에서 얻은 보상보다 입사 후 얻을 보상이 큼
        • 에이전트는 지금(t) 부터 앞으로의 보상의 합 $G_{t}$를 최대화
        • 그래서 $\gamma$가 0에 가까울 수록 현재 보상에 집중 → greedy
        • 1에 가까울 수록 매우 장기적인 시야를 갖는 에이전트
        • [$\gamma$가 꼭 필요한 이유]
          1. 수학적 편리성: 리턴 값이 무한대로 발산하는 것을 방지할 수 있음
             1. 리턴이 무한이라면 어느 쪽(에피소드?)이 더 좋을지 비교하기 어려움
          2. 사람의 선호 반영: 사람은 당장 100만원을 받는 것과 10년후 100만원을 받는 것 중 전자를 선호 → 에이전트에게 이를(사람의 사고) 반영시킬 수 있음
          3. 미래에 대한 불확실성 반영: 10년 후에 100만원을 100% 받을 수 있을 거란 보장이 없거나 100만원이라는 가치가 지금과 미래는 다를 수 있어서(100만원으로 짜장면도 못사먹는 나라가 될 경우, 나라가 망할 경우) → 미래의 가치에는 불확실성을 반영
      • 각 상태에서 다른 상태로 갈 때 확률적(확률 분포를 따름)으로 이동하기 때문에 $s_{0}$에서 시작해서 $s_{t}$ 까지 가는 에피소드는 여러개임 → 하나의 샘플 집합이 됨
      • 그러한 샘플집합에서 샘플링을 통해 현재 상태 $s_{t}$의 가치를 평가!
        • 각 에피소드 마다 리턴 값이 있고, 에피소드는 여러개이기 때문에 상태 s_{t}의 가치는 기댓값으로 정의할 수 있음
          • $v(s) = \mathbb{E}[G_{t}|S_{t} = s]$
        • 각 에피소드의 평균 값이 “누움” 이라는 상태의 가치!

 

마르코프 결정 프로세스(Markov Decision Process)

MRP의 경우 상태 변화가 자동적으로 이루어졌음, 즉 의사결정을 하는 주체가 없었음

→ 순차적 의사결정 문제를 풀기에 적합하지 않음

MDP는 의사결정을 하는 주체가 있어서 각 상황마다 액션(행동)을 취함 → 주체가 취한 액션에 따라 상태가 변하고 그에 따른 보상을 받음

$MDP \equiv (S, A ,P, R, \gamma)$

• MRP와 달리 액션 집합 $A$가 존재함
• 이는 에이전트가 취할 수 있는 행동의 집합
  • A = (앞으로 움직이기, 뒤로 움직이기, 흙을 채집하기)
• 에이전트는 스텝마다 액션의 집합 중에서 하나를 선택하여 액션을 취하며, 이에 따라 다음 상태에 도착

$P^a_{ss’}$

• 현재 상태가 s 일때 a라는 액션을 선택했을 때 다음 상태가 s’이 될 확률
• 상태 s 에서 액션을 취했을 때 도달하게 되는 상태가 결정론적이 아니다
• 엄밀한 정의 → $P^a_{ss’} = \mathbb{P}[S_{t+1}=s’|S_{t} = s, A_{t}=a]$

$R^a_{s} = \mathbb{E}[R_{t+1}|S_{t}=s, A_{t}=a]$

• 현재 상태 s에서 어떤 액션을 선택하느냐에 따라 받는 보상이 달라짐

MDP에서 궁극적으로 찾고자 하는 것

• 각 상태 s에 따라 어떤 액션 a를 선택해야 보상의 합을 최대로 할 수 있는지
• → 정책

정책(policy)

• 각 상태에서 어떤 액션을 선택할지 정해주는 함수
• $\pi(a|s) = \mathbb{P}[A_{t}=a|S_{t}=s]$
• 상태 s에서 액션 $a_{0}, a_{1},…$ 을 취할 확률의 합은 1
• 정책함수는 에이전트 안에 존재 함(환경은 변하지 않고, 정책은 언제든 수정 됨)

 

상태 가치 함수(State value function)

• 어떤 정책을 선택하냐에 따라 얻는 리턴이 달라짐
• 정책 $\pi$를 따랐을 때 현재 상태 s 의 가치
  • $v_{\pi}(s) = \mathbb{E}[r_{t+1} + \gamma r_{t+2}+…|S_{t}=s]$

 

액션 가치 함수(state action value function)

• 각 상태에서의 액션을 평가 → 액션을 평가할 수 있다면 각 상태에서 선택할 수 있는 액션을 모두 평가해본 다음에, 그중에 가장 가치 있는 액션을 선택하면 됨
• $q(s,a)$
  • action만 따로 평가할 수 없는 이유는 상태에 따라 취할 수 있는 액션이 달라지기 때문
  • $q_{\pi}(s,a) = \mathbb{E}[G_{t}|S_{t} = s, A_{t} = a]$
    • s에서 a를 선택하고, 그 이후에는 $\pi$를 따라서 움직일 때 얻는 리턴의 기댓값
    • $\pi$에 따라 이후 상태가 달라지기 때문에 $\pi$는 고정하고 평가 함
  • $v_{\pi}$에서는 s 에서 $\pi$ 가 액션을 선택하는 반면, $q_{\pi}(s,a)$를 계산할 때는 s에서 강제로 a를 선택함

 

• Prediction과 Control
  1. 주어진 상황이 있을 때 이를 MDP의 형태로 만든다.
  2. MDP를 푼다.
     1. MDP를 푼다는 것의 의미: Prediction과 Control 이라는 task를 푼다
        1. Prediction: $\pi$가 주어졌을 때 각 상태의 밸류를 평가하는 문제
        2. Control: 최적 정책 $\pi^*$를 찾는 문제
           1. 최적 정책→ 존재하는 모든 $\pi$ 중 가장 기대 return이 큰 $\pi$

 

참고 문헌

바닥부터 배우는 강화학습 - 노승은