[KMOOC 강화학습] Week 04-2 Markov Process Ex

해당 강의는 K-MOOC의 “강화학습의 수학적 기초와 알고리즘 이해” 수업을 수강하며 기록한 내용입니다. 강의는 링크에서 확인하실 수 있습니다.

개괄

Markove Chain

확률변수가 셀 수 있는 값들 중 하나를 선택하는 경우

예시 : 쥐와 큐브

• Time space: 쥐가 한번 움직일 때를 하나의 단계로 가정할 때 단계들의 모음!
• 확률 변수 $X_{n}$ = $n$번째 단계에서의 쥐의 방 번호
• Sample path(episode) : 쥐가 움직인 경로

그리고 markov chain임을 증명하려면,

$P(X_{n+1}

X_{n},X_{n-1},…) = P(X_{n+1}

X_{n})$ : transition probability를 정의할 수 있어야 하며 행렬의 칸들을 채워야 한다.

과겨 이력과 상관없이 다음 상태가 셀 수 있는 경우라면 Markov Chain이라고 할 수 있다!

예시 : 재고 관리

• 확률 변수 : $X_{n}$ 는 n 번째 주 금요일 밤의 재고수준
• 주차별 수요확률은 알려져있음
• 주차별 발생 확률을 동일하며 이전 주차의 수요가 다음 주차 수요에 영향이 없다고 하자.

EX

$P(X_{n+1}=5

X_{n}=0)=P(D=0)$ 현재 주차에서 재고가 0일 때 다음 주차에서 재고가 5일 확률 = 수요가 없을 확률!

즉 이번 주차의 재고와 다음 주차 재고간 차이는 결국 해당 주차의 수요의 분포로 계산을 할 수 있을 것이다.!

$P(X_{n+1}=0

X_{n}=0)=P(D=5)+ P(D=6)$ : 재고가 안남았다 = 수요가 5이상이다!

만약 한 단계 더 간다면?

당연히 마르코브 프로세스라고 할 수 없다!

대신 다른 형태로 확률 과정을 정의하면 된다.

$[(X_{n}, X_{n+1})]$ 으로 정의하면 마르코브 인가? 즉 transition probability를 정의할 수 있으면 마르코브 프로세스다!

$[(X_{k}, X_{k+1})

(X_{k-1}, X_{k})] = P(X_{k+1}

X_{k-1}, X_{k})$ 라고 할 수 있으니 결국 마르코브 체인으로 볼 수 있다.

즉, 3개의 확률 과정과 변수를 묶고 이들간의 상태를 관찰하면 된다!

다만 문제점으로 상태 공간의 크기가 무한히 증가하여 계산하기 힘들다!