RL: 2. Markov Decision Process
Markov Decision 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 Decision Process
Markov Decision Process를 배우기 위해 Markov State, Markov Process(or Markov Chain)를 먼저 배웠습니다.
1) Definition: Markov Property
저번 포스팅에서 마르코프 속성(Markov Property)는 아래 정의와 같다고 했습니다.
현재가 주어진다면, 미래는 과거에 대해 독립적이다.
The future is independent of the past given the present
2) Definition: Markov Process
그리고 마찬가지로 저번 포스팅에서 마르코프 프로세스(Markov Process)는 아래와 같다고 했습니다.
Markov Process ( or Markov Chain )은 <S, P> 튜플입니다.
- S는 상태들의 집합(finite set of states)입니다.
- P는 State Transition Probability Matrix
출처: David Silver, http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf각 상태의 변화를 나타낸 데이비드 실버의 강의자료 중 MP(Markov Process)의 다이어그램입니다.
3) Definition: Markov Reward Process
마르코프 프로세스에서 보상 R과 할인율 gamma를 추가한 것이 바로 MRP, 마르코프 리워드 프로세스 입니다. 상태가 변하는 마르코프 프로세스에서 각 상태로 이동할 때마다 보상이 주어지는 프로세스로 변화했습니다.
A Markov reward process is a Markov chain with values.
Markov Reward Process는 Markov Process에 가치 판별값(value judgement)을 포함한 것입니다.
Markov Reward Process는 <S, P, R, gamma>로 이루어진 튜플입니다.
- S는 상태들의 집합(finite set of states)입니다.
- P는 State Transition Probability Matrix입니다.
- R은 reward function입니다.
- gamma는 할인율입니다.
출처: David Silver, http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf데이비드 실버의 강의자료에서 가져온 MRP 그림 예시입니다. 기존의 MP(Markov Process)에서 보상을 추가했습니다. 각 상태에 도달할 때 보상의 변동이 있습니다.
4) Definition: Bellman Equation
Bellman Equation은 현재 가치함수와 미래 가치함수와의 관계를 나타내는 선형 함수입니다. 선형함수이기에 직접 해법이 가능합니다.
계산 복잡도는 n가지 상태가 있다고 했을때, O(n^3) 입니다.
작은 MRP에 대해 직접 해법이 가능합니다.
큰 MRP에 대해 여러 반복적인 방법들이 있습니다.
- 다이내믹 프로그래밍(Dynamic programming)
- 몬테카를로 측정(Monte-Carlo evaluation)
- 시간차 학습(Temporal-Difference learning)
5) Definition: Markov Decision Process
Markov Decision Process(MDP)는 결정(Decision)이 포함된 Markov Reward Process(MRP)입니다. MDP는 모든 상태들이 Markov인 환경입니다.
Markov Decision Process 는 <S, A, P, R, gamma> 로 이루어진 튜플입니다.
출처: David Silver, http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf드디어 대망의 MDP입니다. 마르코프 의사결정 프로세스는 각 상태에서 어떤 액션(A)을 취하면 어떤 상태 변화(S, P)와 보상(R, gamma)을 얻을수 있는 지 정의한 프로세스입니다.
6) Definition: Policies
정책 π는 상태가 주어졌을 때 행동의 분포입니다.
A policy π is a distribution over actions given states.
- 정책은 에이전트가 어떻게 행동하는지 완전히 정의합니다.
- MDP 정책은 현재 상태에 의존합니다. (과거에 의존하지 않고)
- 정책은 stationary합니다. (시간 독립적)
4. Purpose of the Reinforcement Learning
저는 종종 면접질문으로 이 질문을 합니다.
강화학습을 통해서 최종적으로 얻고자 하는 것이 뭔가요?
강화학습을 통해서 우리가 최종적으로 얻어내야 하는 것은 최적 정책 함수(Optimal Policy Function)입니다. 현재 상황에서 어떤 행동을 해야할 지 알려주는 Optimal Policy(최적 정책)을 알아내는 것이 바로 강화학습의 목표입니다. 가치 함수(Value Function)이나 궤적(trajectories)이나 리플레이 메모리(Replay Memory) 다 부차적인 것입니다.
제가 여러번 말해왔습니다. 강화학습에 제가 빠지게 된 이유는 바로 강화학습이 컴퓨터 스스로 '의사결정'을 하게 만드는 알고리즙이기 때문입니다.
스스로 결정할 수 있는 능력을 창조한다는 아이디어는
정말 매력적이지 않나요?
