[Lec1] Markov Decision Process

이 포스팅은 다음 자료들을 정리했음을 알려드립니다. 혹시 저작권 문제가 있으면 바로 삭제하도록 하겠습니다.

강화학습 한글자료(PDF) : https://www.gitbook.com/book/dnddnjs/rl/details.

파이썬과 케라스로 배우는 강화학습 : http://wikibook.co.kr/reinforcement-learning/

Reinforcement Learning: An introduction: http://www.incompleteideas.net/book/bookdraft2017nov5.pdf

2. Markov Decision Process

순차적 행동 결정 문제를 수학적으로 정의한 것이 Markov Decision Process(이하 MDP)이다.
MDP는 상태(State), 행동(Action), 보상(Reward), 상태 변환 확률(State Transition Probability), 감가율(Discount Factor), 정책(Policy)으로 구성되어 있으며 이를 통해 더 좋은 정책을 찾는 과정을 배워보자

2.1. 상태(State)

State란 에이전트가 관찰 가능한 상태의 집합인데 여기서 상태란 "자신의 상황에 대한 관찰", 로봇과 같은 실제 세상의 에이전트에게는 센서값이 상태라 할 수 있다.

에이전트의 상태는 시간에 따라 달라지는데, 에이전트가 가질 수 있는 모든 상태의 집합을 S 라 할 때, 시간이 t일때 에이전트의 상태s를 다음과 같이 나타낸다.

s는 앞서 정의된 상태 집합 S의 원소이다.

다음 그림과 같은 그리드월드의 경우를 예로 들어보자.

예시의 그리드 월드에서 격자 상의 각 위치(좌표)가 상태s이고 상태의 전체 집합 S 는 다음과 같다

현재 t=1인 시점에서 에이전트는 (3,3) 지점에 있으므로 다음과 같이 표현 할 수 있다.

2.2. 행동(Action)

Action이란 에이전트가 상태 St에서 가능한 행동으로 전체 행동의 집합 A 로 나타낸다
State와 마찬가지로 에이전트가 시간 t에서 특정 행동 a를 하는것을 다음과 같이 나타낸다.

a는 가능한 행동의 집합 A의 원소이다.

앞의 그리드 월드에서 에이전트가 할 수 있는 행동은 네 방향으로 움직이는것으로 수식으로 나타내면 다음과 같다.

만약 t=1 시점에서 에이전트가 오른쪽으로 이동 즉, A1 = right 의 행동을 한다면 t=2 시점의 에이전트의 상태는 S2 = (3, 4) 가 될 것이다.

2.3. 보상(Reward)

보상이란 환경이 에이전트에게 주는 정보로 에이전트가 학습할 수 있는 유일한 정보이다.

에이전트가 St = s 일때 At = a 라면 에이전트가 받을 보상에 대한 기댓값은 다음과 같이 나타 낸다.

여기서 주목해야 할 점은 보상을 기댓값을 사용한다는 점이다.

기댓값이란 일종의 평균(average)으로 '어떤 확률을 가진 사건을 무한히 반복했을 경우 얻을 수 있는 값의 평균'이며, 확률변수 X의 확률분포함수가 f(x)일 때 X의 기대값 E(X)는 다음과 같다.

1. 확률변수 X가 이산확률변수 일 경우,

2. 확률변수 X가 연속확률변수 일 경우,

예를 들어 1과 6사이의 눈을 가진 정육면체 주사위를 던져 나오는 값을 X라 하면 X의 기댓값 E[X]는 다음과 같이 구할 수 있다.

이 때 기댓값은 실제 값이 아닌 기대할 수 있는 평균 값임을 주목하자(3.5는 주사위 눈에 존재하지 않음)

보상 또한 상태 s에서 행동 a를 했을 경우에 받을 것이라 예상하는 기댓값으로 특이한 점은 상태와 행동은 t시점이지만 보상은 t+1시점이다.

이것은 에이전트는 t시점의 상태 St에서 행동 At를 하지만 환경은 t+1시점에 새로운 상태 St+1과 보상 rt+1를 알려 주기 때문이다.

2.4. 상태 변환 확률(State Transition Probability)

상태 변환 확률이란 에이전트가 상태 s에서 행동 a를 취했을 때 환경의 확률적인 요인에 의해다른 상태 s'에 도달할 확률로서 다음과 같이 나타낸다.

만약 그리드 월드에서 0.3의 확률로 4번째 열에 바람이 분다고 가정하면 다음 그림과 같이 에이전트가 오른쪽으로 이동한다고 하더라도 바람이 불게 되면 한칸 아래로 이동하게 된다.

따라서 에이전트는 오른쪽으로 행동을 하지만 새로운 상태는 확률적으로 오른쪽으로 움직이거나 오른쪽 아래 방향으로 움직이는 두가지 상태가 가능하다.

이러한 상황을 상태변환 확률로 나타내면 다음과 같다.

2.5. 감가율(Discount Factor)

감가율이란 에이전트가 현재에 가까운 시점에 받는 보상을 미래에 받는 보상보다 가치 있게 해주는 개념이다.

예를들어 우리가 같은 100만원을 받는데 이를 오늘(현재) 받는 것과 1년뒤(미래)에 받는것은 가치가 다르다. 현실에서도 은행의 100만원을 넣어두고 1년뒤 받게 되면 이자를 얹어 100만원+@ 만큼 받게 된다. 이는 결국 현재의 100만원이 1년뒤에 100만원 보다 적은 금액 만큼의 가치를 가진다는 의미이다.

따라서 같은 보상이더라도 시간이 지날수록 가치가 줄어드는 것을 반영하기 위해 감가율(Discount Factor)이라는 개념을 사용한다.

감가율 r 은0과 1사이의 값을 가지며, 현재 시간 t로부터 k 시간이 지난 후의 보상은 다음과 같이 나타낼수 있다.

2.6. 정책(Policy)

정책이란 모든 상태에 대해 에이전트가 할 행동으로 다음과 같이 나타낸다.

우리가 강화학습을 하는 목적이 바로 이 정책들 중 최적 정책을 학습하는 것이다. 그리드 월드에서 정책의 예는 다음과 같이 나타낼 수 있다.

2.7. 학습방법

지금까지 MDP를 이용한 순차적 행동 결정 과정을 살펴보았다.

아래 그림과 같이 에이전트는 환경으로부터 상태(St)와 보상(rt)을 받게 되고 에이전트는 정책에 따라 행동(at)을 하게 된다.

환경은 에이전트의 행동에 대해 새로운 상태(St+1)와 보상(rt+1)을 주게 되고 이를 통해 Agent가 스스로 정책을 업데이트 하는 과정을 통해 보상이 최대화 되는 최적 정책을 학습하게 된다.