RL Basics: 1. Markov Process
강화학습의 기본: Markov Process
1. Acknowledgment
이 글은 세 가지 교재와 강의 영상의 내용을 재구성하여 편집하였습니다.
Introduction to Reinforcement Learning - Richard Sutton
http://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf
Reinforcement Learning Course, University of - David Silver
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Home.html
파이썬과 케라스로 배우는 강화학습, 이웅원 외 5명
아티클 연재의 아웃라인은 David Silver의 강의안을 중심으로 진행합니다.
2. Study Purpose
강화학습에 대한 기초 개념을 하나 하나 완전히 이해하는 것을 목표로 합니다. 사실, 기본 정의(Definition)들은 암기하는 게 좋을 것 같습니다. 저도 많이 부족한만큼, 겸손하게 하나씩 공부해보도록 하겠습니다.
3. Markov Process
Markov Decision Process(MDP)는 강화학습의 환경을 형식적으로 설명해냅니다.
거의 모든 강화학습 문제는 MDP로 형식화될 수 있습니다.
- 최적화된 콘트롤은 Continuous MDP를 다룹니다.
- 부분적으로 관찰가능한(Partially observable problems) 문제도 또한 MDP로 형식화될 수 있습니다
- Bandit 문제는 State가 하나 밖에 없는 MDP 문제입니다.
Markov Decision Process(MDP)를 이해하기 위해 MDP의 기본이 되는 개념들에 대해 하나씩 공부해보겠습니다.
1) Definition: Markov Property
가장 먼저, Markov Decision Process에서 Markov란 무슨 뜻일까요? 어떤 상태 S_t가 Markov라면 이건 무슨 의미일까요?
현재가 주어진다면, 미래는 과거에 대해 독립적이다.
The future is independent of the past given the present
왠지, Doctor Strange의 대사와도 같은 이 한 마디는 Markov State의 속성을 설명합니다.
2) Definition: Markov State
상태 S_t가 Markov 라는 말은
- 현재의 상태를 나타내는 S_t가 주어졌을 때, S_{t+1}가 일어날 확률과
- 최초의 시점부터 현재까지 모든 상태 S_1, ..., S_t 가 주어졌을 때, S_{t+1}이
일어날 확률이 같다는 뜻입니다.
참고)
여기서 if and only if 라는 표현은 필요충분조건이라는 말입니다.
P[A|B]는 B라는 사건이 일어났을 때 A가 일어날 확률을 뜻하는 조건부 확률입니다.
Markov State st는 과거 정보들(s1, s2, ... st)을 잘 확보하고 있습니다.
우리가 정의한 상태(State)가 Markov라고 한다면,
현재 상태가 있을때 과거의 상태는 버려도 되는 것입니다.
이렇게 상태를 Markov 상태로 한정하게 되면 우리가 해결해야 하는 문제의 복잡도가 낮아집니다.
현재 상태만으로 미래의 Reward를 최대화할 Action을 찾는 데 충분하다는 가정은 최적의 정책을 계산하는 데 과거부터 현재까지 모든 기록을 다 input으로 넣어야 할 필요성을 없애줍니다. 계산을 아주 효율적으로 할 수 있도록 만들어주는 설정이죠.
3) Definition: State Transition Probability
두 번째 정의로 State Transition Probability를 배워보겠습니다.
상태 s와 그에 이어지는 상태 s'에 대해서, State Transition Probability는 아래와 같이 정의됩니다.
For a Markov state s and successor state s', the state transition probability is defined by
Pss' 는 Markov 상태 s에서 상태 s'로 이동할 확률을 말합니다.
4) Definition: State Transition Matrix
그 다음은, State Transition Matrix입니다. 상태와 상태간 이동하는 확률을 정의한 행렬입니다.
State Transision Matrix는 상태 s로부터 상태 s'로 가는 모든 Transition Probabilties를 정의합니다.
State transition matrix P defines transition probabilities from all states s to all successor states s'
여기서 특이한 점은, 각 행렬의 열의 숫자를 더하면 1이 된다는 점입니다. 상태 1에서 다른 상태들 1,2,3, ... n까지 이동할 확률의 합은 1이어야하기 때문이죠.
5) Definition: Markov Process ( or Markov Chain )
Markov Process ( or Markov Chain )은 <S, P> 튜플입니다.
- S는 상태들의 집합(finite set of states)입니다.
- P는 State Transition Probability Matrix
A Markov Process ( or Markov Chain ) is a tuple <S, P>
- S is a (finite) set of states
- P is a State transition probability matrix
4. Next Topic
이번 아티클에서는 5가지 강화학습 기본 개념들의 정의(Definition)들을 알아봤습니다. 인공지능 학회에 참석해보면, 최신 강화학습 알고리즘들이 쏟아지고 있지만, 우리가 사랑하는 강화학습의 기본부터 다시 공부하는 계기가 되었으면 합니다. 다음 포스팅에선 Markov Reward Process에 대해 공부해보겠습니다.
