인공지능의 개론 - Markov Decision Process (MDP)

Markov Decision Process (MDP)

강화학습의 가장 기본적인 모델로 Markov Process의 확장.

-------------------------------------------------------------------

Markov Process (MP, Markov Chain)

Markov Property를 가정한 Stochastic Process.

• Markov Property (Markov Assumption)

어떤 State로 Transition할 확률은 오로지 현재 State에만 종속적이며, 과거 State와는 독립적이다.

임의의 state에서 다음 state로 진행할 확률은 이전 state들과는 무관하다.

• <S, P>Tuple.

Markov Process는 <S, P>튜플로 정의되어진다.

S : State Space(State Set)

n state-space.

P : Transition function 

(Transition Matrix, State Transition Probability Matrix)

각 transition의 확률을 나타낸다. 일종의 Transition model이다.

s에서 s'로 Transition할 확률. n x n matrix로 표현 가능하다.

• Episode

Initial State부터 P에 따라 랜덤하게 진행한 Terminal State까지의 sequence.

• Episode Sampling

여러개의 Episode를 추출하는 것.

-------------------------------------------------------------------

Markov Reward Process (MRP)

Markov Process에서 transition에 따라 reward를 받게되는 모델이다.

• <S, P, R, γ>Tuple.

Markov Process에 R과 γ가 추가되었다.

R : Reward function

어떤 state의 보상함수 값은 다음 state로 transition하면서 얻을 수 있는 *reward의 기대값이다. 

* transition에 따라 reward가 달라지기 때문

t+1 step에서의 reward는 r_(t+1)은 그 기대값 R_s(R_t) 와의 구분을 위해 소문자로 표현하였다.

γ : Discount factor

먼 미래에 얻게될 reward 기대값(R)은 그 time step 만큼의 Discount factor를 가져야 한다.

이는 Return이라는 개념에서 설명된다.

0이상 1이하의 실수이다.

• Return (G_t)

미래에 얻을수 있는 Reward의 기대값의 총합.

더 먼 미래의 Reward일수록 더 낮은 가중치를 가진다.

t step에서 미래에 얻을수 있는 모든 reward기대값의 합

γ가 0에 가까울수록 Myopic evaluation(근시적 평가)

γ가 1에 가까울수록 far-sighted evaluation(원시적 평가)

γ=1인경우, 0이 아닌 reward를 지닌 cycle edge가 존재할때 return이 무한이 되는 문제가 발생.

• Value Function (V(s))

어떤 state에서 가지는 *Return 기대값을 나타낸다. 

*Return 자체가 기대값의 합이라 별도의 계산이 필요 없다.

-------------------------------------------------------------------

Markov Decision Process (MDP)

MRP에 action을 추가한 모델

• <S, A, P, R, γ> Tuple

A : Action set, A = {a_1, a_2, a_3, ...}

P : 정의역에 A의 차원 추가

s state에서 a action을 했을때, s'로 transition할 확률.

R : 정의역에 A의 차원 추가

s state에서 a action을 했을때 받게되는 reward의 *기대값.

*여전히 Transition자체가 stochastic하기 때문에 그로인한 reward도 stochastic해서 기대값만을 유효하게 사용 가능하다.

• Policy (π(a|s))

어떤 state가 어떤 action을 취할 확률.

s state에서 a action을 취할 확률.

Policy는 Markov Property를 따르는가?

현재 state에만 의존하여 action을 정하는것은 P와 연계하여 다음 state는 오로지 현재 state에만 종속적이라는 Markov Property를 따른다.

• Value Function (V_π(s))

아래첨자 π추가, value function이 policy에 *종속적임을 나타낸다.

* A_t는 π에 종속적 → P에따라 S_n, A_n (n>t)는 π에 종속적 → R_n (n>t+1)은 π에 종속적 → G_t는 π에 종속적 → V는 π에 종속적

그러나 R, G는 보통 π를 첨자에 넣지 않는다. 하지만 π가 엄연한 변수인 만큼 필요에 따라 넣은 표현식을 사용해도 좋을것같다.

π policy일때의 return 기대값이다.

• Action-Value Function (Q_π(s, a))

어떤 state에서 어떤 action을 했을때의 value function값이다.

π policy에서 s state가 a action을 취할때의 return 기대값.

Value Function과의 유일한 차이점은 t time step 에서의 action이 주어지고, 따라서 첫 time step에는 π 가 관여하지 않는다는 것이다.

• V와 Q의 관계

V를 Q로 표현하기

Value Function은 어떤 state의 return 기대값이다.

그렇다면, Expectation의 정의로 인해 다음이 성립한다.

s state에서 가능한 모든 action별로 해당 action을 행할 확률과 그 action을 행하고 얻어질 수 있는 return 기대값의 총합이다.

Q를 V로 표현하기

Q의 정의에 따라 다음이 성립한다.

s state에서 a action을 할때의 reward 기대값 + (discounted된 모든 가능한 successor state의 transition 확률 x successor state의 return 기대값)의 총합 

• Bellman Expectation Equation

임의의 state의 value function과 그 다음 state의 value function의 상관관계를 나타내는 방정식. 어떤 변수에 대한 방정식으로 나타내느냐에 따라 방정식은 여러가지 형식으로 나타내어진다.

따라서 아래 6가지 방정식 모두 상호 유도 가능하다.

Return의 정의에 따른 Bellman Expectation Equation의 2가지 형식

1. V(s)와 V(s')의 관계식

G_t의 항들 중 t+2 이상의 항들은 γV(S_(t+1))로 대체가 된다.

 Bellman Expectation Equation[1]

2. Q(s,a)와 Q(s,a)의 관계식

Bellman Expectation Equation[2]

위의 수식에서 R은 (s,a)쌍에 종속인데, stochastic한 policy에서는 a가 stochastic하므로 *R_(t+1), V(S_(t+1)) 모두 stochastic하고 Expectation을 걷어낼 수 없다.

*Action-Value Function에서는 예외.

V와 Q의 관계식으로 유도한 Bellman Expectation Equation 4가지 형식

1. V(s)와 Q(s)의 관계식

Q(s)는 V(s')에 대한 다항식으로 나타내진다. Bellman Expectation Equation[4] 참조.

Bellman Expectation Equation[3]

2. Q(s)와 V(s')의 관계식

V(s')는 Q(s')에 대한 다항식으로 나타내진다. Bellman Expectation Equation[3] 참조.

Bellman Expectation Equation[4]

3. V(s)와 V(s')의 관계식

Bellman Expectation Equation[3]의 Q(s)를 Bellman Expectation Equation[4]를 사용해 치환.

Bellman Expectation Equation[5]

4. Q(s)와 Q(s')의 관계식

Bellman Expectation Equation[4]의 V(s')를 Bellman Expectation Equation[3]를 사용해 치환.

Bellman Expectation Equation[6]

Bellman Expectation Equation의 행렬 표현.

S 의 모든 원소 s에 대해 다음이 성립함을 Bellman Expectation Equation[5]를 통해 알수가 있다.

각 원소를 행렬로 표현하면 다음 수식이 나온다.

이는 편의상 다음과 같이 표현된다.

V, R: n x 1행렬, P: n x n행렬

이를 V에 대해 정리하면,

 n x n 행렬의 역행렬만 구한다면, n-state space의 각 원소들의 V값은 바로 구할수 있다. 그러나 n x n 행렬의 역행렬은 시간복잡도가 O(n^3)이다. 적절한 솔루션이 될수 없다.

따라서 n이 큰 문제에서는 Dynamic programming, Monte-Carlo evaluation, Temporal-Difference learning 기법을 사용한다.

• Optimal Value Function (V⁎(s))

임의의 state가 가질수 있는 value function의 최대값.

π*: optimal policy

Optimal Action-value Function (Q⁎(s))

임의의 state가 가질수 있는 action-value function의 최대값.

π*: optimal policy

• Optimal Policy(π*)

모든 state에 대해 그 value function값을 optimal하게 만드는 policy다.

Optimal Policy에 대한 정리 3가지

1. 모든 MDP에는 반드시 하나 이상의 optimal policy가 존재한다.

s는 임의의 state, π는 임의의 policy

2. 모든 Optimal policy는 임의의 state가 optimal value function값을 갖게 한다.

↪정의다.

3. 모든 Optimal policy는 임의의 state와 action이 optimal-action value function값을 갖게한다.

↪ Bellman Expectation Equation[4]를 보면 Q는 V와 양의 선형관계 가진다는 것을 알수 있다.

Optimal Policy 구하기

어떤 state에 대해 가능한 모든 action과의 Q값을 구해서 그중 Q값이 최대가 되는 action만을 선택하는 policy를 구성하면된다.

Q가 최대인 a값이 여러개면 optimal policy가 여러개가 되는거다. 그때는 그 중에서 확율을 주던 하나를 정하던 상관없다.