1) MDP, Value Function, Bellman Equation

출처: https://subsay.tistory.com/14

https://www.youtube.com/playlist?list=PLpRS2w0xWHTcTZyyX8LMmtbcMXpd3s4TU

이전 참고 글: 2020/07/29 - [공부/강화학습] - Reinforcement Learning, Open AI GYM

 

 

 

# Markov Process

MP는 state transition Matrix다. state set S와 state transition probability P로 표현한다.

MP = [ S , P ]

P = [[P11, ,,, , P1n], ,,, , [Pn1, ,,, , Pnn]]

 

 

 

# Markov Reward Process

MRP는 MP에 reward와 discount factor를 추가로 표현한다. 

MRP = [ S , P , R , γ ]

R = reward, γ = discount factor

 

 

 

# Markov Decision Process

MDP는 MRP에 action를 추가로 표현한다.

MDP = [ S , A , P , R , γ ]

순차적 행동 결정 문제. MDP를 푸는 과정은 더 좋은 정책을 찾는 과정이다.

 

 

 

# Reward

Agent가 현재 State에서 Action을 수행해서 얻는 학습 정보다.

Reward는 environment로부터 얻어진다.

같은 state, action이라도 확률적으로 다른 보상을 받을 수 있기 때문에 기댓값으로 생각해야 한다.

 

 

 

# Policy

agent의 action을 선택하는 함수이다.

모든 state에 적용되는, 행동 선택의 기준이 된다.

Policy에 따라 여러 개의 action을 확률적으로 선택할 수 있다.

π(a|s) = P[ At = a | St = s]는 action given state 할 확률

 

 

 

# Discount Factor

나중에 받을 보상보다 현재의 가치가 더 높기 때문에 보상에 감가율 Discount Factor γ를 적용한다.

Discount Factor는 reward를 구분하기 위해 사용하기도 한다.

수학적으로 수렴하는 방향이 더 편하기 때문에 사용하기도 한다.

0과 1 사이의 값이다.

 

 

# Return

시간마다 획득하는 보상을 모두 더한 값이다.

Return Gt는 어떤 시간으로부터 에피소드가 끝날 때까지 받은 보상을 정산한 값이다.

 

Return: total discounted reward

Discounted reward: present value of future reward

 

예를 들어 t=1부터 t=3까지의 보상에 대한 반환값은 다음과 같다.

 

G1 = R2 + γR3 + γ^2R4     :     t1에 action을 수행하면 다음 시점인 t2에 보상을 받게 된다.

G2 = R3 + γR4          :     t2 이후부터 끝날 때까지 받은 보상은 R3, R4이다.

G3 = R4               :     t3에 action을 해서 최종 보상 R4를 받고 에피소드가 끝난다.

 

 

 

# Value Function

return Gt는 실제로 agent가 environment를 탐험해서 얻은 보상의 합이다.

value function은 agent가 현재 state에서 정책을 따라 행동할 때, 받을 것이라 예상되는 보상의 합에 대한 기댓값이다.

어떤 state에서 Gt의 기댓값이다. v(s) = E[ Gt ] 가치 함수는 정책 판단의 기준이 된다.

 

value function은 아래와 같다. state에 대한 조건과 확률에 대한 것은 생략했다. E는 기댓값, π는 정책 policy를 고려한 것이다.

agent가 action을 수행하고 그 결과로 다음 state가 되고 reward를 받기 때문에 t+1에서 시작한다.

 

v(s) = E[ Gt ]

v(s) = E[ R(t+1) + γR(t+2) + γ^2R(t+3) + ,,, ]

v(s) = E[ R(t+1) + γ[ R(t+2) + γR(t+3) + ,,, ] ]

v(s) = E[ R(t+1) + γG(t+1) ]

v(s) = E[ R(t+1) + γv(s+1) ]

vπ(s) = Eπ[ R(t+1) + γvπ(s+1) ]

 

 

 

# Action - Value Function

가치 함수는 state를 받아서 앞으로 받을 보상의 합을 알려준다.

행동 가치 함수는 state를 받아서 어떤 action이 얼마나 좋을지에 대해 알려준다.

큐 함수는 행동의 가치를 직접적으로 표현한 '행동 가치 함수'이다. 강화 학습에서는 주로 큐 함수를 사용한다.

 

qπ(s, a) = Eπ[ R(t+1) + γqπ(S(t+1), A(t+1)) | St = s, At = a]

 

 

 

# 벨만 기대 방정식

위의 식 vπ(s) = Eπ[ R(t+1) + γvπ(s+1) ]이 벨만 기대 방정식 Bellman Expectation Equation이다.

현재 상태의 가치 함수와 다음 상태의 가치 함수에 대한 관계식이 벨만 기대 방정식이다.

강화 학습은 이 방정식을 풀어나가는 것이다. 점화식과 비슷한 모양인데 이는 dynamic programming과 관련 있다.

 

 

 

# 벨만 최적 방정식

벨만 방정식은 단순히 모든 정책의 가치 함수에 대한 관계식이다.

최적의 정책으로 최적의 가치 함수를 찾을 수 있고, 이 최적의 가치 함수에 대한 관계식이 벨만 최적 방정식이다.

최적의 보상, 최적의 행동을 찾을 때는 max, argmax의 개념이 들어간다.

 

optimal state value function: maximum value function overall policies

v*(s) = maxπ vπ(s)

v*(s) = maxa q*(s, a)

 

optimal action value function: maximum action-value function overall policeis

q*(s, a) = maxπ qπ(s, a)

 

 

 

# optimal policy

MDP에는 반드시 optimal policy가 있다.

optimal policy는 모든 state에서의 policy보다 좋거나 같다.

π*를 따라가면 v*, q*과 같다.

optimal policy는 여러 개가 있을 수 있다.

 

q*를 알면 π*를 알 수 있다.

π*(a|s) = if a: argmax q* 1 , otherwise 0로 표현할 수 있다.

There is a deterministic optimal policy.

위의 방법으로 표현하면 deterministic 하게 사용할 수 있다.