[강화학습 요약] Policy Iteration / MC / TD learning

Markov

참고로 Markov는 수학자 이름임

Markov  Process

미래의 process는 현재의 상태에만 의존함

i.e. 동전 던지기로 앞/뒷면이 나오는 process에서 앞면이 직전에 10번 연속으로 나온 것과 상관없이 앞면/뒷면의 확률은 각각 50%

Markov Chain

: Sequence of states and their transition

Markov State

System에서 정의가능한 상태

i.e. S1 : 비가 온다 / S2 : 화창하다 / S3 : 흐리다

 

Policy

각각의 State에서 어떤 action을 취할 것 인지

 

Value function

agent가 상태 s에서 policy를 따랐을 때 총 보상을 얼만큼 가질 수 있을 지 (미래의 보상도 포함)

$V(s) = E[\sum_{t=0}^{\infty}\gamma^tR_{t+1}|s_0=s]$

감마는 discount factor라고 불리며 0과 1 사이이다

1이면 현재의보상=미래의보상이고

0이면 현재의 보상만 포함한다

 

Q function

agent가 s상태에서 a라는 행동을 했을 때 총 보상

$Q(s,a) = R(s,a)+\gamma \sum P(s'|s,a)V(s')$

$P(s'|s,a)$의 뜻은 s,a에서 s'으로 전이될 확률이다

 

Value function의 정의에 따라

$Q(s,\pi(s)) = V(s)$

 

Optimal Policy 구하기

Policy Iteration

최적의 Policy를 찾는 방법 중 하나

Policy Iteration = (Policy evaluation + Policy improvement) * 반복

 

Policy improvement

$Q^{\pi_i}(s,a) = R(s,a)+\gamma \sum P(s'|s,a)V(s')$

=> $\pi_{i+1}(s) = arg max_a Q^{\pi_i}(s,a)$

예를 들어 s1상태에서 (a1,a2,a3) action을 취할 수 있다고 하자

$Q^{\pi_i}(s_1,a_1) = 1$

$Q^{\pi_i}(s_1,a_2) = 2$

$Q^{\pi_i}(s_1,a_3) = 1$

a2를 취했을 때가 가장 큰 Q 값이 나오므로 s1상태에서는 a2를 취하는 것이 좋은 policy이다.

따라서, $\pi_{i+1}(s_1) = a_1$

Policy evaluation

주어진 policy로 Value function (On policy) 또는 Q function (Off policy) 계산

- On policy / Off policy는 나중에 설명

$V^{\pi+1}(s) = R(s,\pi(s))+\gamma \sum   P(s'|s,a)V(s')$

이 방법을 Dynamic programming이라고 함

 

Model-free

dynamics 나 reward를 모를 때 Policy Evaluation 하는 법

 

Monte Carlo(MC)

V(s) = mean return of all trajectories' return

- No bootstrapping

 (bootstrapping : 이전의 estimate로 다음 estimate 업데이트 함)

- Episodic한 도메인만 적용가능

 

First-Visit MC

한 episode에서 한 state를 처음 방문 했을 때만 value를 update한다

 

Every-Visit MC

한 episode에서 방문한 모든 state만 value를 update한다

episode 중 특정 episode가 특정 state를 많이 방문한다고 가정

많이 방문한 state는 overestimate되고 적게 방문한 state는 underestimate되어 bias가 커지게 되어 수렴하는데 더 많은 시간이 걸림

 

Incremental MC

$V^\pi(s) = V^\pi(s) + \alpha (G_{i,t}-V^\pi(s))$

$\alpha = \frac{1}{N(s)}$ 면 every-visit 과 같아짐

 

예제

Value function 구하기

episode1 : (s1,a2) (s2,a1) (s1,a2) (s2,a2) (s3,a2)

episode2 : (s1,a1) (s1,a2) (s2,a2) (s3,a2)

Initial V,S,G=0

R : [0,0,16]

$\gamma=0.5$

$\alpha=0.5$

	Episode1					Episode2
	(s1,a2)	(s2,a1)	(s1,a2)	(s2,a2)	(s3,a2)	(s1,a1)	(s1,a2)	(s2,a2)	(s3,a2)
	Git = 1	Git = 2	Git = 4	Git = 8	Git = 16	Git = 2	Git = 4	Git = 8	Git = 16
First visit	G(s1)=1	G(s2)=2	-	-	G(s3)=16	G(s1)=1+2	-	G(s2)=2+8	G(s3)=16+16
	N(s1)=1	N(s2)=1	-	-	N(s3)=1	N(s1)=2	-	N(s2)=2	N(s3)=2
	V(s1)=1	V(s2)=2	-	-	V(s2)=16	V(s1)=1.5	-	V(s2)=5	V(s3)=16
Every visit	G(s1)=1	G(s2)=2	G(s1)=2+4	G(s2)=2+8	G(s3)=16	G(s1)=6+2	G(s1)=8+4	G(s2)=10+8	G(s3)=16+16
	N(s1)=1	N(s2)=1	N(s1)=2	N(s2)=2	N(s3)=1	N(s1)=3	N(s1)=4	N(s2)=3	N(s3)=2
	V(s1)=1	V(s2)=2	V(s1)=3	V(s2)=5	V(s2)=16	V(s1)=1.67	V(s1)=3	V(s2)=6	V(s3)=16
Incremental	V(s1)=0+0.5*(1-0)	V(s2)=0+0.5*(2-0)=1	V(s1)=0.5+0.5*(4-0.5)	V(s2)=1+0.5*(8-1)	V(s3)=0+0.5*(16-0)	V(s1)=2.25+0.5*(2-2.25)	V(s1)=2.125+0.5*(4-2.125)	V(s2)=4.5+0.5*(8-4.5)	V(s3)=8+0.5*(16-8)
	=0.5	=1	=2.25	=4.5	=8	=2.125	=3.0625	=6.25	=12

 

TD learning

Incremental MC : $V^\pi(s) = V^\pi(s) + \alpha (G_{i,t}-V^\pi(s))$

여기서 $(s_t,a_t,r_t,s_{t+1})$에 대해

$V^\pi(s) = V^\pi(s) + \alpha ([r_t+\gamma V^\pi(s_{t+1})]-V^\pi(s))$ 로 계산한다

- bootstapping

- continuing 도메인에서도 쓸 수 있음