Lecture 2: Markov Decision Processes (1)

2장은 Markov Process(MP), Markov Reward Process(MRP)에 대해 살펴보도록 하겠습니다. Markov Decision Process의 경우는 다음 게시물인 Lecture2 (2)로 분리하여 정리하였습니다. 

 

 

MDPs

- MDP는 learning을 위한 env를 묘사한다.

- env가 fully observable한 상황에서

- 현재 state가 현재의 프로세스를 완벽하게 표현하는 경우 == Markov한 상황

- 대부분의 RL  문제들를 MDP로 formalised 할 수 있다. 

Optimal control, Bandit와 같은 문제들을 MDP로 전환가능 

 

---

Markov Property

- "현재가 주어져 있다면, 미래는 과거와는 독립적이다. "

- state가 모든 history와 관련된 모든 정보들을 가지고 있기 때문에, state를 아는 순간 history를 버릴 수 있다. 

- state는 미래에 대한 충분한 통계적 표현형이다. 

 

 

---

State Transition Matrix

- state transition probability(Pss'): s에서 s'으로 갈 확률

- state transition matrix: Pss'을 matrix 형식으로 나타낸 것

ex) P11: state가 1에 있을 때, 다음 state가 1에 있을 확률

     P1n: state가 1에 있을 때, 다음 state가 n에 있을 확률

 

 

---

Markov Process

- memoryless: 내가 어느 경로를 통해서 왔는지 상관 없이, 여기 온 순간 미래가 정의된다 == Markov property

- random process:  어느 state에서 시작해서 계속 이동해도 다양한 결과가 나온다는 sampling을 가능하게 함 

state가 n개 있고, matrix는 n*n만큼 크기를 가지고, 이를 만족할 시 Markov Process는 완전히 정의 가능

- S: state들의 set

- P: state transition 확률 matrix

 

 

---

 

Markov Chain Example

state 7개, state의 transition 확률은 화살표로 표기

- episode(start->terminal state까지 가는 과정)를 sampling이라 부른다. ==simulation 

Markov Process에서 sampling ex) C1 C2 C3 Pass Sleep, C1 FB FB C1 C2 C3 Pub C2 Sleep

 

State Transition Matrix Example

State Transition Matrix로 나타낸 Markov Process topology

 

 

---

Markov Reward Process

env에는 reward가 존재하므로 Markov Process <S,P>에 R와 r를 추가하면 Markov reward Process를 완전 정의 가능

- R: reward function, 어떤 state에 도달하면 reward 축적

- r: discount factor

Markov Process + Reward , discount factor = Markov Reward Process

MRP에서는 action이 존재하지 않고(action에 reward가 아닌 state에 reward 이므로), 확률적으로 state만을 선택함

 

---

state마다 reward가 설정되어 있음

 

---

Return

- Return Gt = cumulative discounted reward

- discount factor 'r'은 미래 reward에 대한 현재 value이다. 

- 미래에 받는 reward에 대해 k time-steps에 따른 r^k만큼의 감산을 누적한다. 

- r이 0에 가까울 수록 "근시안적인" 평가

- r이 1에 가까울 수록 "원시안적인" 평가

 

 

---

Why discount?

- 수학적으로 편리하기 때문(수렴성 증명)

sampling 중 만약 모든 sequence가 terminal state로 끝나는 것이 보장된다면, r=1이 가능할 수도 있음.

 

 

---

Value function

State Value function: 한 state에서 sampling된 return들의 기댓값

기댓값: 어떤 확률 과정을 무한히 반복했을 때, 얻을 수 있는 값의 평균으로서 기대할 수 있는 값. 보다 엄밀하게 정의하면 기댓값은 확률 과정에서 얻을 수 있는 모든 값의 가중 평균이다.말만 기댓값이지 확률이랑 똑같은 거다

 

sampling시에 같은 state에서 시작해도 episode마다 다른 return 값들이 생성되고 이에 대한 평균치가 v(s)

특정 state에 도달했을 때 어느정도의 return을 받을지 기댓값 

 

 

---

 

r=0, MRP state-Value function

r=0이기 때문에, reward와 v(s)가 같은 결과를 보임(short-sighted)

r=0.9, MRP state-Value function

r=0.9일 때의 sampling을 통해서 계산한 v(s)(far-sighted)

 

 

---

Bellman Equation for MRP

- Bellman Equation: value function은 즉시 reward인 Rt+1과 나머지 discounted value인 r*v(St+1)로 분해된다. 

 

sampling을 통한 기댓값으로 평균을 내는 것이 아닌 확률적 수학 계산을 통한 방식 표현

상단의 식에서 Expectation을 풀이해서 쓰면 다음 꼴로 표현

v(s) = s에서의 reward + r * ( Pss'의 각각 확률 * v(s')의 합들)

 

 

---

 Bellman Equation for MRP

v(s)들의 유기적 연결이므로 MRP에서는 한번에 해결 가능 ex) 4.3 = -1 + 0.6 * 10 + 0.4 * 0.8

 

 

---

Bellman Equation in Matrix Form

벡터와 행렬을 이용한 Bellman Equation 표현

 

solving Bellman Equation

- Bellman Equation은 선형 방정식인데, 다음의 식을 통해 v(s)를 directly하게 계산 가능하다.

v = R + rPv => v = {(1 - rP)^-1}*R

- 계산 복잡도는 n개 states시에 O(n^3)이므로 n^3에 비례하여 상당히 비싼 연산

- 따라 small MRP에서만 Direct solution은 사용 가능하다.

- 큰 MRP의 경우에는 Dynamic programming, Monte-Carlo evaluation, Temporal-Difference learning 방식의 iterative methods들이 사용된다. 

 

 

---

 아래는 교재 및 참고 블로그, 유튜브 강좌입니다. 

deepmind.com/learning-resources/-introduction-reinforcement-learning-david-silver

Interested in learning more about reinforcement learning? Follow along in this video series as DeepMind Principal Scientist, cre

youtube.com/watch?v=NMesGSXr8H4&list=PLpRS2w0xWHTcTZyyX8LMmtbcMXpd3s4TU&index=2