팡요랩 - 강화학습 2강 공부

팡요랩 - 강화학습 2강 공부

CS234 2019 Winter를 듣다보니 영어 강좌일 뿐 아니라 용어가 너무 어려워 따로 자료를 찾던 도중 발견한 곳이 팡요랩이었습니다.

2015 David silver 강좌를 기반으로 한 강화학습을 한국어로 설명해 주시기에 이를 토대로 블로깅해보며 한 번 적어볼까하고 시작해볼까합니다.

물론 이번 강좌를 필사하고 괜찮으면 더 이어갈 것이고 그렇지 않다면 아마 이 2강으로 끝나지 않을까 생각합니다.

1강 URL : https://www.youtube.com/watch?v=wYgyiCEkwC8

1강은 개요라서 생략 2강에 대한 공부를 할 것 입니다.

2강 URL : https://www.youtube.com/watch?v=NMesGSXr8H4

강화학습에 MDP Sequential 상태를 알아야한다.
Markov Decision Property
Markov State : 이전 history는 다 버리고 이전 State만을 가지고 사용할 것

순서
1. Markov Process
2. Markov Reward Process
3. Markov Decision Process
4. Extension to MDPs - 강의에서는 소개하지 않으므로 다루지 않는 부분

1. Markov Process
MDP 환경을 표현하는 것, 환경이 모두 관측가능한 상황을 말하는 뜻으로
거의 모든 강화학습은 MDP 형태로 만들 수 있다.

$P(S_{t+1} | S_t) = P(S_{t+1} | S_1,S_2, ... S_t)$
이전 history를 다 버릴 수 있다.

State Transition Matrix
env를 설명하는데 필요한 것으로
시간 t에 St=s라면 S_(t+1) = s`으로 전이할 확률들을 matrix 형태로 만든 것
$P_{ss^\prime} = P(S_{t+1}=s^\prime | S_t = s)$
nxn matrix에 각 state -> state로 가는 확률을 넣어만든 값

Markov Process
S : 상태들의 집합
P : transition probability matrix 전이 확률 행렬 상태를 나타낸 행렬

memoryless random process
episode : sampling 한다는 의미
sampling : 한 event sequence episode를 뽑아낸다.

2. Markov Reward Process
$\left\langle S,P,R, \gamma \right\rangle $
r : discount factor 0~1

action에 대한 reward를 주는 것은 state마다의 reward를 주는 것과는 다르다.
state와 action에 대한 reward는 다름

강화학습은 return을 maximize하는 것이 목표
경로 sampling 했을 때 $\gamma$ 지수승을 통해 먼 state에 대해서 약하게 할 수 있다.

r = discount factor : 수학적으로 편리해서 -> 수렴성을 증명이 가능하므로 사용
terminal 종료점이 있으면 r=1이 가능

value function : return의 기댓값
$E(G_t|S_t=s)$
$G_t$는 확률 변수
ex) $G_1 = R_2 + \gamma R_3 + \cdots + \gamma ^{T-2}R_T$
각 episode에 따라 v를 계산 -> 평균

Bellman Equation for MRPs
중요한 개념

Immediate reward $R_{t+1}$
discounted value of successor state $\gamma v(S_t+1)$
$v(s) = E[G_t | S_t = s]$
$= E[R_{t+1} +\gamma R_{t+2}+\gamma ^2 R_{t+3} + .... | S_t=s]$
$= E[R_{t+1} +\gamma (R_{t+2}+\gamma R_{t+3} + .... )| S_t=s]$
$= E[R_t+1 +\gamma G_{t+1}| S_t=s]$
$= E[R_t+1 +\gamma v(S_{t+1})| S_t=s]$
$v(s) = R_s + \gamma \sum_{s^\prime \in S} P_{ss^\prime v(s^\prime)}$

$v = R+\gamma Pv$
$(I-\gamma P)v = R$
$v = (I-\gamma P)^{-1}R$

3. Markov Decision Process : 36:40s
$\left\langle S,A,P,R, \gamma \right\rangle$
S : a finite set of state
A : a finite set of actions
P : a state transition probability matrix
$P_{ss^{\prime}}^a = P[S_{t+1} = s^\prime | S_t=s, A_t=a]$
$R_s^a = E[R_t+1 | S_t = s, A_t = a]$
$\gamma$ : a discount factor $\gamma \in [0,1]$

action마다 reward
action을 하면 확률적으로 state들로 진행
action이 나올 확률은? s

policies
$\pi(a|s) = P[A_t=a | S_t=s]$
현재의 상태에 의존 not history
stationary, time-independent
$P_{s,s^{\prime}}^{\pi} = \sum_{a \in A} \pi(a|s)P_{ss^{\prime}}^a $
$R_s^\pi = \sum_{a \in A} \pi(a|s)R_s^a$
policy $\pi$라 한다면 action을 했을 때의 state, reward를 통해 다음 state에 넘겨주는데 전체적으로 MRP로 볼 수 있다.
$\left\langle S,A,P,R,\gamma \right\rangle$ => $\left\langle S,P^\pi, R^\pi, \gamma \right\rangle$

value function
policy pi를 따라 진행된다.
state-value function : $v_\pi (s) = E_\pi [G_t | S_t =s]$
action--value function : $q_\pi (s,a) = E_\pi [G_t | S_t =s, A_t=s]$

bellman eqn을 통해 수식적 표현할 것임

state-value function : $v_\pi (s) = E_\pi [R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t =s]$
action--value function : $q_\pi (s,a) = E_\pi [R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1}) | S_t =s, A_t=s]$

$v_\pi (s) = R_s^a + \gamma\sum_{s^\prime \in S} P_{ss^\prime}^a v_\pi(s^\prime), \forall s$

Optimzal Value Function
$v_* (s) = max_\pi v_\pi (s)$
$q_* (s,a) = max_\pi q_\pi (s,a)$

Optimal Policy
$\pi \ge \pi^\prime if v_\pi(s) \ge v_{\pi^\prime}(s)$
모든 state에 대해서 value function이 클 때 조건이 너무 까다로운 정의
모든 MDP에 대해서 ...

Bellman Optimality Equation for v_*

$v_*(s) = max_a q_* (s,a)$
$q_*(s,a) = R_s^a + \gamma \sum_{s^\prime \in S} P_{ss^\prime v(s^\prime)}^a v_*(s^\prime)$
$v_*(s) = max_a R_s^a + \gamma \sum_{s^\prime \in S} P_{ss^\prime v(s^\prime)}^a v_*(s^\prime)$

max -> linear equation이 아님
식 전개로 풀 수 없음

끝

아~ 식 쓰는거 개빡셈...