타임트리

지금까지 배운 내용들을 통해 강화학습의 수학적 기초를 다졌다. 동적 계획법에 대해 살펴보며 재귀식, 가치 함수, 정책, 상태, 행동이 어떻게 구성되는지를 살펴보았고, 강화학습에서 다루는 환경이 불확실성을 가지고 단계별로 진행되기 때문에 확률과정과 MP, MRP, MDP에 대해 살펴보았다. 이러한 수학적 기초를 바탕으로 앞으로는 강화학습 알고리즘에 대해서 학습한다. 우선, 강화학습은 agent와 environment 간 상호작용을 통해 agent가 환경에 대한 정보를 취득해 나아가며 학습하는 방법을 말한다. 그래서 아래 그림과 같이 agent는 매 단계마다 환경으로부터 주어지는 상태 정보를 취득하고 이를 바탕으로 특정 행동을 취한다. 행동을 통해서 agent는 환경으로부터 일종의 보상을 받게 되고, 환경은..

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 Processes: MDP)를 소개하기 위함이었다. 이번 주차에서는 MDP 모델이 무엇인지, 그리고구성요소에 대해 알아보자. 1. 마르코프 의사결정 프로세스 (MDP) 동적계획법은 확정적 동적계획법과 확률적 동적계획법으로 나눠지며, MDP는 확률적 동적계획법의 special case라고 볼 수 있다. 확정적 동적계획법은 앞선 주차에서 학습한 내용처럼 특정 상태에서 행동의 결과가 어떤 상태로 전이될지 이미 알려져있고, 그 상태로만 확정적으로 전이가 된다. 하지만, 확률적 동적계획법은 어떤 상태에서 행동을 취했을 때 다음 상태가 확률적으로 결정되는 경우에..

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

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

강화학습의 기본적인 매커니즘을 이해하기 위해서는 동적 계획법(dynamic programming)이라는 문제 해결을 위한 방법론에 익숙해지는 것이 좋다. 따라서, 동적 계획법을 이해하는 데 도움이 되는 수학적 귀납법을 먼저 간단하게 살펴보고 넘어가자. 수학적 귀납법 - $p_1,~p_2,...$를 참 또는 거짓인 명제라고 하자. 이때 1) $p_1$이 참이고 2) 모든 $n\ge1$에 대해 $p_n$이 참일 때 $p_{n+1}$도 참이면, 3) $p_1,~p_2,...$는 모두 참이다. 다음의 식을 수학적 귀납법을 통해 증명해보자. $$p_n: 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$ 증명 1) $p_1 = \frac{1\cdot2}{2}=1$ (참) 2) $p_n$이 참이..

강화학습: 주어진 상황(state)에서 보상(reward)을 최대화할 수 있는 행동(action)에 대해 학습하는 것 1. 강화학습의 특징 - 학습주체(agent)는 환경에 대한 정보를 모르는 상태에서 학습하기 때문에 특정 상황에서 적합한 행동을 찾기까지는 수많은 시행착오(trial & error)가 필요함 - 현재 선택한 행동이 미래의 순차적 보상에 영향을 미침(delayed reward) 2. Multi-armed Bandit 문제 강화학습의 모든 구성요소를 가지고 있지는 않지만, Multi-armed Bandit 문제를 통해 강화학습의 메커니즘을 간단히 이해해보자. 여러 대의 bandit machine이 있고 행동의 개수가 $k$로 정해진 상황에서 보상을 최대화하기 위해 어떤 행동을 취해야하는지 푸..