4.1 마르코브 프로세스 개요 : 강화학습의 수학적 기초와 알고리즘의 이해

강화학습의 수학적 기초와 알고리즘의 이해를 보고 정리한 글임을 밝힙니다.

 

확률(Probability)

주위에서 발생하는 여러 사건들 → 불확실성 내포 : 이런 불확실성을 표현하는 수단

• 확률변수
• 확률분포
  → 확률변수가 취하는 값들에 따라 어느 정도의 가능성을 가지고 해당 event가 발생하는지 표현하기 위한 개념

EX) 날씨

• X = 1(맑음), 2(흐림), 3(비) : 확률변수
• P(X=1) = 0.6, P(X=3) = 0.2, P(X=3) = 0.2 : 확률분포

시간에 따른 날씨 시계열

불확실성 + 내일 날씨와 오늘 날씨의 상관관계 존재 → 시간의 흐름에 따라 불확실성 변동

 

시간에 따라 확률적으로 변화하는 프로세스를
모델링 하기위한 방법으로 사용하는 것이 무엇일까?

 

확률과정 (추계적 과정 : Stochastic process, Random process)

확률적으로 변화하는 프로세스를 모델링하기 위해 수학적으로 접근하는 방법

불확실성을 가지고 변하는 일련의 과정

= 시간에 따라 어떤 사건들이 발행할 확률값이 변하는 과정

 

불확실한 시스템 모델링 : 확률변수와 결합확률분포의 정의가 필요

• 시간공간(Time Space) T : 시스템의 상태를 관찰하는 시점들의 집합
• 상태(State)
  • 확률 변수들이 가지는 어떤 값(시스템의 상태) == 어떤 시점에서 확률과정이갖는 값
    • ex) 주가, 날씨, 전염병 신규 확진자 수
• 상태공간(State Space) S
  • 확률과정 $\left\{ X_t : t \in T \right\}$의 확률변수 $X_t$가 가질 수 있는 모든 가능한 값들의 집합
    
    
• 샘플경로,에피소드(Sample path; episode)
  • 시간 t가 변함에 따라 확률과정 $\left\{ X_t : t \in T \right\}$ 가 갖는 값의 자취
  • 확률과정의 실현치들을 모아 놓은 것 (일종의 시계열 데이터 샘플)
    • ex) 동전을 던지는 주체가 바뀌면(혹은 반복되면) 나오는 값들의 sequence도 바뀔 수 있으므로
• 정상과정(Stationary process)
  • 시간 t에 따라 확률법칙이 변하지 않는 확률과정
  • t가 변하더라도 상태확률이 변하지 않는 확률과정

 

⇒ 시간공간 T와 상태공간 S에서 정의된 확률변수들의 집합

⇒ 시간이 진행 함에 따라 상태가 확률적으로 변화하는 과정

 

EX) 동전 던지기 - 불확실성을 가짐

• 개요
  • 동전을 던져 앞면이 나오면 +1점, 뒷면이 나오면 -1점 → 점수의 총합이 게임의 점수
  • 플레이어가 종료를 선언하면 게임 종료
  • 종료 시점에 점수가 양수면, 점수 당 천원 받기 / 음수면, 점수 당 천원 내기
  • 시작점수 : 0

위와 같은 게임이 있다고 할 때, 확률과정을 정의해 보자.

확률변수는 게임을 통해서 우리가 얻을 수 있는 시스템의 상태값이 되어야 하는데,

여기서는 n번째 동전을 던졌을 때의 누적 점수 값들이 될 수 있을 것이다.

먼저 확률과정을 정의하기 위해서는 어떤 시점에서의 상태를 정의하기 위한 확률변수를 정의해야 한다.

그러므로 상태공간 S는 $\left\{ \dots, -2, -1, 0, 1, 2, \dots \right\}$ 과 같이 정의될 수 있다.

 

시간 공간은 동전을 던질 때마다 증가하는 횟수가 되므로 $T = \left\{ 0,1,2, \dots \right\}$ 로 정의될 수 있다.

 

 

< 확률과정의 4가지 분류 >

시간공간 T와 상태공간 S가 셀 수 있느냐 없느냐에 따라 경우를 나눌 수 있다.

 

그래서 확률과정을 통해 알고 싶은 것은 무엇이냐? 예측이다

 

 

확률과정 $\left\{ X_t : t \in T \right\}$ 에 대해 :

$P(X_{k+1} | X_k, X_{k-1}, \dots, X_0)$ 이와 같은 확률은 얼마나 되는지? 가 궁금한 것이다.

 

위의 수식을 말로 풀어보면,

과거부터 현재까지 이런 과정을 가졌을 때,

그 다음 단계에서 확률변수가 가지는 특정값이 될 확률은 무엇인지?이다.

 

이를 계산하기 위해 결합확률분포가 필요하다.

$P(X_0, X_1, \dots, X_k) = P(X_0)P(X_1|X_0)\cdots P(X_k|X_l-1, \dots, X_1, X_0)$

위 식에서 보듯이 결합확률분포를 알기 위해서 조건부 확률을 알아야 한다.

 

결국, 조건부 확률이 확률 과정의 결합확률분포를 결정하는 중요한 개념이 된다.

조건부 확률이 가장 단순할 경우는 과거와 완전히 독립적인 경우이다.

이는 시간의 흐름과 관계없다는 말과 같기 때문에 확률과정을 이용하여 분석할 필요도 없어진다.

 

두번째로 단순한 경우는 현재만이 미래를 결정하는 지표가 되는 경우이다

미래는 현재로부터 정해지며, 과거는 영향을 주지 못한다

$P(the \ future | the \ present, \ the \ past) = P(the \ future | the \ present)$

 

$P(X_{k+1} | X_k, K_{k-1}, \dots ) = P(X_{k+1} | X_k)$ 로 표현할 수 있다.

위와 같은 성질을 마르코프 성질(Markov property) 라고 하며,

이런 성질을 가진 확률과정을 마로코프 프로세스(Markov Process)라 한다.

 

마르코브 프로세스(Markov process)

과거와 상관없이 현재 상태만 의존하는 가장 단순한 형태의 확률과정이다.

 

Discrete-Time Markov Chain(DTMC)

마르코브 프로세스 중에 시간공간(time space, T)가 discrete(이산적, 셀 수 있는)한 마르코브 체인

 

다음의 성질을 만족하는 확률과정 $\left\{ X_n : n \ge 1 \right\}$

• 모든 n에 대해 $X_n \in S$

확률과정을 정의하기 위해 결합확률분포를 정의해야 하고, 이를 위해 조건부 확률을 정의해야 한다.

• 모든 $i, j \in S$ 에 대해, $P(X_{n+1} = j | X_n = i, X_{n-1}, \dots, X_0) = P(X_{n+1} = j | X_n = i)$
  → 마르코브 성질을 만족하는 조건부 확률

위와 같은 조건들을 만족하는 확률 과정을 DTMC라고 하고,

여기서 Chain이라고 이름을 붙인 이유는

상태공간에 속해 있는 어떤 값들이 셀 수 있는 값(discrete)인 경우이기 때문이다.

 

상태 전이확률(1-step state transition probability)

$i$ 상태에서 다음 단계 $j$가 될 확률 기술

$$ P(X_{n+1} = j | X_n = i) $$

• 단계별 정의 가능 : 단계별로 전이확률이 다를 수 있다. (일반적 DTMC)

Time-homogeneous(시간동질) DTMC

전이확률이 시간에 독립적인 상황일 때

• 이 확률은 n과 독립적이기 때문에 어느 시점에나 내가 현재 $i$ 상태에 있으면 그 다음 상태가 $j$가 될 확률은 시간에 독립적으로 다 동일하다.
  • $P(X_{n+1} = j | X_n = i ) = p_{ij}$