타임트리

Week5부터는 Markov Decision Process(MDP)를 살펴보고 있다. Week5에서는 MDP의 구성요소(상태 공간, 시간 공간, 행동 공간, 상태전이확률, 보상)를 살펴보았다. Week6에서는 일반적인 상황에서 상태 가치함수와 행동 가치함수 그리고 이들의 벨만 기대 방정식과 함께 벨만 최적 방정식까지 살펴보았다. 특히, 시간 공간이 유한한 finite-horizion MDP 모델에서는 벨만 최적 방정식을 풀기 위해 역진 귀납법을 사용했다. 특히 중요한 부분은 강화학습의 수학적 근간이 되는 Infinite-horizon MDP 모델이다. Infinite-horizon MDP 모델에서는 정상성 가정(stationary assumption)이 중요한데, 보상과 상태전이확률이 시간에 의존하지 않..

지금까지 살펴봤던 내용들을 간단하게 정리해보자. MDP는 동적계획법 중 확률적 동적계획법의 특별한 경우에 속한다. 즉, 순차적인 의사결정 단계를 포함하며, 현재 상태에서 다음 상태로의 전이가 확정적이 아닌 확률적으로 일어난다. MDP의 구성요소로는 의사결정 단계의 집합인 Time space, 확률과정이 취하는 값들의 집합인 State space, 특정 상태에서 취할 수 있는 행돌의 집합인 Action space, 매 단계마다 특정 상태에서 특정 행동을 취했을 때 다음 상태가 될 확률을 나타내는 trainsition probability, 그리고 이때 발생하는 reward와 감가율 $\gamma$가 있었다. 1. MDP 가치함수 MDP는 순차적으로 매 단계마다 의사결정을 내린다(sequential deci..

마르코프 의사결정 프로세스(Markov decision process; MDP) 강화학습의 수학적 근간이 되는 이론적인 배경이다. 하지만 곧바로 MDP는 확률적 동적 계획법과 마르코프 프로세스가 합쳐진 것이므로 MDP를 배우기에 앞서, 마르코프 과정(Markov procss)에 대해 먼저 알아보자. 1. 불확실성 모델링 확률(Probability) 주위에서 발생하는 여러 사건들은 근본적으로 불확실성을 내포 불확실성을 표현하는 수단 불확실성을 확률변수와 확률분포를 사용해 수학적으로 모델링 확률변수와 확률분포 예시) 날씨는 맑음, 흐림, 비로 구성되어 있다고 하자. 날씨라는 불확실성을 내포한 시스템을 모델링하기 위해 날씨의 상태라는 확률변수를 정의하면, 다양한 분석을 가능하게 한다. $X=1$ (맑음), $..

최단 경로 문제(Shortest path problem) 아래 그림과 같이 1번 노드에서 10번 노드까지 최단 거리를 찾는 문제를 생각해보자. 우선 그래프를 살펴보자. 노드끼리 이어진 선은 아크(arc)라고 하며, 화살표(→)로 표시한 아크는 일방통행, 선으로만 표시된 아크는 양방통행을 나타낸다. 또한 아크 옆에 표시된 숫자는 노드에서 노드로 이동까지의 거리 혹은 소요되는 시간으로 볼 수 있다. 여기서는 거리라고 하자. 위와 같은 상황에서 1번 노드에서 10번 노드까지 가장 빨리 이동하는 경로를 찾기 위해서는 어떻게 해야할까? 먼저 가장 단순한 방법은 모든 경로에 대한 거리를 계산하고 비교하는 것이다. 그러나 이 방법은 비효율적이란 걸 금방 알아차릴 수 있다. 이 문제를 동적계획법으로 해결해보자. 동적계..