[Find-A] Markov process

Markov decision processes

Markov process 파트에서는 RL(Reinforcement Learning) 문제를 해결하는 데 사용되는 방법으로 이동을 가능하게 하는 RL의 이론적 토대를 익힐 것

 

이 파트는 책의 나머지 부분을 이해하는 데 중요하며 RL에 익숙해지는 것을 보장

 

먼저 방금 논의한 formalisms(reward, agent, actions, observations, and environment)의 수학적 표현과 개념을 소개하고,  이것을 기초로 하여 우리는 state, episode, history, value, gain을 포함한 RL언어의 2차적 개념을 소개하는데, 이는 책의 후반부에서 다른 방법을 설명하는데 반복적으로 사용됨

 

그리고 Markov decision process에 대한 우리의 설명은 러시아 마트료시카 인형과 같음

 

<러시아 마트료시카 인형>

우리는 Markov Process(MP : Markov chain)의 가장 단순한 사례에서 시작하여 rewards로 확장하여 Markov reward processes로 전환

 

그런 다음 actions을 추가하여 이 아이디어를 다른 봉투에 넣음으로써 Markov Decision Processes(MDPs)로 이어질 것

 

 Markov processes와 Markov decision processes는 computer science와 다른 공학분야에서 널리 사용됨

 

따라서 이 챕터를 읽는 것은 RL contexts 뿐만 아니라 훨씬 더 광범위한 주제에 도움이 될 것

 

MDPs를 이미 잘 알고 있다면, 나중에 사용할 용어 정의에만 주의를 기울이면서 이 장을 빠르게 훑어봐도 됨

 

 

Markov process

Markov process는 Markov chain이라고도 알려져 있음

 

당신 앞에 오직 여러분이 관찰할 수 있는 어떤 시스템이 있다고 상상해보고, 여러분이 관찰하는 것을 states라고 하며, 시스템은 역학 법칙에 따라 전환할 수 있다고 함.

 

이때 당신은 시스템에 영향을 줄 수 없고 오직 상태가 변화하는 것을 지켜볼 뿐

 

시스템에 대한 가능한 모든 상태는 state space라는 집합을 형성

 

Markov processes에서 우리는 이 상태 집합이 유한해야 한다고 가정(그러나 매우 클 수 있음)

 

관측치는 일련의 states 또는 체인을 형성(이 때문에 Markov processes를 Markov chains라고도 함)

 

예를 들어, 어떤 도시의 가장 간단한 날씨 모델을 보면, 우리는 주 공간인 현재 날을 맑거나 비가 오는 것으로 관찰할 수 있음

 

시간에 따른 일련의 관측은 [sunny, sunny, rainy, sunny, ...]와 같은 일련의 체인을 형성하며 이것을 history라고 부름

 

이러한 시스템을 Markov Process라 부르기 위해서는 Markov property를 충족해야 하는데, 이는 어떤 상태에서도 미래의 시스템 역학은 이 상태에만 의존해야 한다는 것을 의미

 

Markov property의 요점은 시스템의 미래를 설명하기 위해 관측 가능한 모든 상태를 스스로 포함시키는 것

 

다시 말해, Markov property는 시스템 상태가 서로 구별될 수 있고 고유해야하며, 시스템의 미래 역학을 모델링하는 데 하나의 상태만 필요하며 전체 history는 아니어야 함

 

우리의 날씨 예제의 경우, Markov property는 우리가 과거에 봤던 맑은 날의 양에 상관없이 같은 확률로 맑은 날이 비가 오는 날 뒤에 올 수 있는 경우에만 모델을 나타내도록 제한함

 

상식적으로 내일 비가 올 가능성은 현재 상태뿐만 아니라 계절, 위도, 그리고 근처의 산과 바다의 존재와 같은 많은 요소들에 달려있다는 것을 알고 있기 때문에 그다지 현실적인 모델은 아님

 

태양 활동조차도 날씨에 큰 영향을 미친다는 것이 최근에 증명되었고, 따라서 우리의 예는 정말 순진하지만 한계를 이해하고 그것에 대한 의식적인 결정을 내린다는 것이 중요함

 

물론, 모델을 더 복잡하게 만들고 싶다면, 우리는 항상 state space를 확장할 수 있고 이것은 우리가 더 많은 의존성을 포착할 수 있게 할 것

 

예를 들어, 여름과 겨울 동안 비가 올 확률을 별도로 확보하려면 해당 계절을 상태에 포함할 수 있음

 

이 경우의 state space는 [sunny+summer, sunny+winter, rainy+summer, rainy+winter]이 됨

 

시스템 모델이 Markov property를 준수하므로 NxN 크기의 제곱행렬인 transition matrix를 사용하여 확률을 확보할 수 있음

 

여기서 N은 모델의 상태 수를 의미하고 행렬의 행 i와 열 j에 있는 모든 셀은 시스템이 상태 i에서 상태 j로 전환된 확률을 포함

 

예를 들어, sunny/rainy가 오는 예시에서 전이 행렬은 다음과 같을 수 있음

 

	sunny	rainy
sunny	80%	20%
rainy	10%	90%

이 경우, 맑은 날이 있다면, 다음 날이 맑을 확률은 80%이고, 다음 날이 비가 올 확률은 20%이고 만약 우리가 비가 오는 날을 관찰한다면, 날씨가 좋아질 확률은 10%이고, 다음날 비가 올 확률은 90% 임

 

Markov process의 공식적 정의는 다음과 같음

• 시스템이 있을 수 있는 상태 집합(S)
• 시스템 역학을 정의하는 전이 확률과 전이 행렬(T)

MP의 유용한 시각적 표현은 시스템 상태와 가장자리에 해당하는 노드가 있는 그래프이며, 상태에서 상태로의 가능한 전환을 나타내는 확률로 레이블이 지정됨

 

전이 확률이 0이면 가장자리를 그리지 않고(한 상태에서 다른 상태로 이동하는 방법은 없음) 이러한 종류의 표현은 automata theory에서 연구되는 finite state machine에서도 널리 사용됨

 

sunny/rainy 날씨 모델의 경우 그래프는 다음과 같음

<Sunny/Rainy weather model>

 

더 복잡한 예를 들어보면, 직장인의 또 다른 모델(Scott Adams의 유명한 만화에 나오는 주인공 Dilbert가 좋은 예)을 소개해봄

 

이 예시에서 state space는 다음과 같음

• Home : 사무실에 없음
• Computer : 사무실에서 컴퓨터로 일하고 있음
• Coffee : 사무실에서 커피를 마시고 있음
• Chatting : 사무실에서 동료들과 무언가를 의논하고 있음

상태 전환 그래프는 다음과 같음

<State transition graph>

우리는 그의 근무일이 보통 Home에서 시작되며 예외 없이 항상 Coffee와 함께 근무를 시작하길 기대함(no Home → Computer edge and no Home → Chatting edge)

 

위 다이어그램은 또한 근무일이 항상 컴퓨터 상태에서 종료됨을 나타내고 이전 다이어그램의 전이 행렬은 다음과 같음

	Home	Coffee	Chat	Computer
Home	60%	40%	0%	0%
Coffee	0%	10%	70%	20%
Chat	0%	20%	50%	30%
Computer	20%	20%	10%	50%

 

전환 확률은 다음과 같이 상태 전이 그래프에 직접 배치할 수 있음

<State transition graph with transition probabilities>

실제로, 우리는 정확한 전이 행렬을 아는 것은 거의 불가능함

 

훨씬 더 실제적인 상황은 시스템 상태에 대한 관찰만 있을 때이며, 이를 episode라고 함

• home -> coffee -> coffee -> chat -> chat -> coffee -> computer -> computer -> home
• computer ->  computer -> chat -> chat -> coffee -> computer -> computer -> computer
• home -> home -> coffee -> chat -> computer -> coffee -> coffee

우리의 관찰에 의해 전이 행렬을 추정하는 것은 복잡하지 않음; 우리는 단지 모든 상태에서 모든 전이를 세고 그것들을 1의 합으로 정규화하면 됨

관측 데이터가 많을수록 추정치는 실제 기본 모형에 더 가까울 것

또한 Markov property는 stationarity(즉, 모든 상태에 대한 기본 전이 분포는 시간이 지남에 따라 변하지 않음)을 의미한다는 점에 주목할 필요가 있음

 

Nonstationarity는 우리의 시스템 역학에 영향을 미치는 숨겨진 요인이 있다는 것을 의미하며, 이 요인은 관찰에 포함되지 않음

 

그러나 이는 전이 이력에 관계없이 동일한 상태에 대해 기본 확률 분포가 동일해야 하는 Markov property와 모순됨

 

한 에피소드에서 관찰된 실제 전이와 전이 행렬에서 주어진 기본 분포 사이의 차이를 이해하는 것이 중요

 

우리가 관찰하는 구체적인 에피소드는 모델의 분포에서 무작위로 샘플링되므로 에피소드마다 다를 수 있으나 표본이 추출될 구체적인 전이 확률은 동일하게 유지

 

그렇지 않으면 Markov chain formalism은 적용되지 않음

이제 더 나아가 Markov process 모델을 확장하여 RL 문제에 더 가깝게 만들 수 있음

---

https://www.packtpub.com/product/deep-reinforcement-learning-hands-on-second-edition/9781838826994

Deep Reinforcement Learning Hands-On - Second Edition | Packt