[강화학습] MDP(마르코프) 환경과 동역학(dynamics)

 

 

 

강화학습은 MDP(Markov Decision Process) 환경에서 적용되는 알고리즘이다

 

 

이전 포스팅 참고한 후 글을 읽으면 이해에 도움이 될 것이다.

2024.09.25 - [Data Science/강화학습] - [강화학습] 강화학습이란? 기초, Overview

[강화학습] 강화학습이란? 기초, Overview

 

 

강화학습은 MDP 환경이 깨지면 더이상의 학습을 이어갈 수 없다.

그럼 MDP 환경이란 무엇인가?

MDP 환경

 

MDP는 state S 에서 action A를 취했을 때 next state로 움직이면서 보상 R를 받는 순환 환경을 MDP 환경이라고 한다.

$$ S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, S_{2}, A_{2}, R_{3}, ... $$ 

MDP의 특성에 대해 알아보자.

 

 

 

Markov Property (마르코프 특성)

 

next state(s') 와 reward(r) 은 current state(s) 와 action(a) 에만 종속된다. 

현재의 나의 state는 그동안 agent가 행해온 action들과 reward들의 결과이다

따라서 이전 state에 있던지 그 이전 state와 무관하게 현재 state만 고려 대상이 된다.

 

정리하자면 현재 state는 미래의 행동에 필요한 모든 정보를 가지고 있으므로 과거 정보를 기억하고 있을 필요가 없다.

이 내용을 다음과 같은 식으로 나타낼 수 있다.

 

$$ \mathbb{P}[S_{t+1}|S_{t}] = \mathbb{P}[S_{t+1}|S_{1},...,S_{t}] $$

 

$ S_{t+1} $ : next state

$ S_{t} $ : current state

 

조금 풀어서 설명을 하면 

현재 state인 $ S_{t} $ 에서 $ S_{t+1} $ 로 갈 확률은 $ S_{t} $ 에만 종속된다.

이렇게 된다면 이전 state를 저장할 필요가 없기 때문에 메모리를 절약할 수 있다는 장점이 존재하게 된다.

 

next state(s')가 current state(s)와  action(a)에 종속된다는 것을 이해했다.

그렇다면 current state(s)가 next state(s')로 넘어갈 확률은 어떻게 될까?

그것을 State Transition Probability(전이확률) 라고 한다.

 

 

 

State Transition Probability (전이확률)

 

다음과 같은 식으로 정의할 수 있다.

$$ p_{ss'}=\mathbb{P}[S_{t+1}=s' | S_{t}=s] $$

 

$ p_{ss'} $ : current state(s)가 next state(s')로 넘어갈 확률

$ S_{t}=s $ : time t 에서의 state (current state)

$ S_{t+1}=s' $ : time t+1에서의 state (next state)

 

그렇다면 모든 state s 에서 모든 next state s' 으로의 전이 확률을 State Transition Matrix P 로 정의할 수 있다.

 

 

 

State Transition Matrix

 

모든 state s 에서 모든 next state s' 으로의 전이 확률을 matrix 형식으로 나타낸 것이고, 이를 식으로 나타내면 다음과 같다.

$$ p = from\begin{bmatrix}
p_{11} & ... & p_{1n} \\
p_{n1} & ... & p_{nn} \\
\end{bmatrix} $$

 

예시를 들어서 설명해보면

아래 Student Markov Chain 환경을 나타내고 있는 것이다.

Class 1, Class 2, Class 3, Facebook, Pub, Pass, Sleep 라는 state가 있고 각 state로의 전이 확률이 나타나져 있다.

Student Markov Chain Episodec

 

이 환경에서의 전이 확률을 matrix 으로 나타내어보면 다음과 같다.

state들의 전이확률을 matrix로 표현

 

이렇게 본다면 모든 전이 확률을 한번에 확인할 수 있게 된다.

그렇다면 Class1에서 Sleep로 가는 Episidec Task를 시행한다고 했을 때, 최적의 에피소드를 찾아보자.

 

Episode 1 : C1 C2 C3 Pass Sleep

Episode 2 : C1 C2 Pub C1 C2 Sleep

Episode 3 : C1 FB FB C1 C2 Pub C1 FB FB FB C1 C2 C3 Pub C2 Sleep

 

만약 reward 까지 감안한 후 최적의 에피소드를 찾는다고 했을 때 첫 번째 에피소드가 최적이라고 할 수 있다. 

이런 경로들을 한번씩 다 거쳐본 후 스스로 학습하여 최적 경로를 찾는 것이 강화학습의 과정이라고 할 수 있다.

 

 

 

유한 MDP(Finite MDP)의 동역학 (dynamics)

 

next state(s') 와 reward(r) 은 current state(s) 와 action(a) 에만 종속된다고 했다.

이때  s → s' 로 가는 action a가 policy π에 의해 동작된다고 했을 때, π에 의해 a가 동작될 확률을 동역학 이라고 한다.

backup diagram

조금 더 쉽게 표현 해보자면

action a 에 의해 갈 수 있는 state가 여러개가 존재할 수도 있다는 의미이다.

예를 들어보자면,

빙판 위에서 앞으로 나아가는 action a를 시행했을 때 앞으로 나아가는 state로 갈 수 있고 미끄러지는 state로 갈 수도 있다.

확률적으로(π) action a을 했을 때 next state가 확률적으로 올 수 있다는 의미이다.

 

그리고 모든 가능한 next state와 reward 확률의 합은 1이 된다.

이를 수식으로 나타내면 다음과 같다.

$$ \sum_{s'\in S}^{}\sum_{r\in R}^{}p(s', r|s, a) = 1 $$

 

s : current state

a : s state's action

s' : next state

r : when s → s' reward

 

식 해석을 위의 backup diagram과 함께 설명을 해보자면 

current state s 에서 action a를 했을 때 모든 경우의 수의 next state s'와 그때의 보상값을 받을 확률을 모두 더했을 때의 값은 1이 된다.

 

그래서 p(dynamics)는 전이확률을 의미하는 것이고, 4개의 변수 (s, a, s', r)로 이루어진 함수가 된다.