강화학습 강의 (CS234) 2강 - Markov Process / MDP / MRP
- 본 포스팅은 CS234 2강의 내용을 정리합니다.
CS234 2강의 주요 내용은
- Markov Process (+ Markov Chain)
- Markov Reward Process (MRP)
- Markov Decision Process (MDP)
- Policy Iteration (PI)
- Value Iteraion (VI)
등이 있습니다.
Markov Process
Markov 한 상태를 띄는 랜덤한 State들.
Action도 없고, Reward도 없는 상태이다.
S는 states의 유한집합이고,
P는 현재 state s에 대해 다음 state s'를 나타내는 dynamics/transition model이다.
+ P는 그냥 모델이라는 뜻으로 받아들이면 된다. 단, 원래 모델에서의 정의와는 달리 다음 state인 st+1이 action에 영향을 받지 않고 이전의 state만의 영향을 받는다.
그리고, 이것을 Matrix로 하여 나타낸 것이 Markov Chain이다.
(아래쪽에 있는 Matrix)
Markov Reward Process (MRP) - Markov Process에 reward를 추가함.
S,P의 정의는 같고,
R는 reward function인데,
reward function은 현재 state에 대한 reward의 기댓값을 표현하는 함수이다.
ᵞ(감마)는 [0,1]의 범위를 갖는 discount factor이다.
discount factor는 현재 얻을 수 있는 immediate reward와 나중에 얻을 수 있는 reward간의 차이를 의미한다.
(나중에 더 자세히 나옴)
여기서도 Markov Process와 같이 Action은 없다.
Horizon : 각각의 에피소드에 대한 time step의 개수.
Agent나 Process의 time step의 개수.
horizon이 무한하지 않으면 finite Markov reward process라고 불리지만,
많은 경우 무한하다.(infinite)
가령, 주식 시장은 오늘도 열리고 내일도 열리고 모레도 열리고 .... 하는 식이다.
(그러니까 여기서 말하는 infinite는 엄밀한 정의의 infinite가 아니라, 그만큼 엄청 많아서 무한하다고 불러도 될 정도를 의미한다. 주식 시장은 사실상 우리가 살아있는 동안은 열려 있지 않겠는가? 그런 식이다.)
Return function (Gt) - time step t부터 horizon까지의 reward의 discounted sum.
즉, 지금부터 이 process가 끝날 때까지 (horizon이 무한하다면 그냥 앞으로 쭉)의 reward에 discount factor ᵞ를 곱한 값의 합.
State Value Function (V(s)) - state s에서 얻을 수 있는 reward의 기댓값.
참고로, 위 수식은 앞으로 계속 나오므로 잘 숙지해 둬야 한다!
Return function은 실제로 얻는 reward를 의미하고, Value Function은 그 reward의 기댓값이므로, 서로 다를 수 있다.
(물론, Deterministic한 경우엔 같을 수도 있다.)
위의 수식을 보면 알겠지만, V(s)는 state s일 때의 Gt의 기댓값으로 나타낼 수 있다.
Discount factor은 immediate reward (즉각적 보상)과 future reward (미래에 얻을 보상)과의 연관관계를 나타낸다.
[0, 1]의 범위 안에서, ᵞ = 0이면 future reward 무시, ᵞ=1이면 immediate reward = future reward란 의미를 가진다.
이때 ᵞ를 사용하는 것은 infinite 한 value를 피할 수 있으므로 수학적으로 용이하지만,
horizon이 finite한 경우에는 ᵞ=1을 사용해도 어차피 infinite한 value는 나오지 않으므로 ᵞ=1을 사용할 수 있다.
s1일때 reward 1, s7일때 reward 10, ᵞ=0.5라고 하자.
s4에서 시작해서 s5,s6,s7으로 가면
V(s)의 수식대로 갔을 때,
V(s) = 0 + 0.5 * 0 + 0.25 * 0 + 0.125 * 10 = 1.25
가 된다.
(이해가 안되면 저 위에 있는 V(s)의 공식을 보고 오라.)
그 외의 경우는 위의 ppt를 보며 직접 확인하면 될 것 같다.
V = [1.53 0.37 0.13 0.22 0.85 3.59 15.31] 은 각각의 s값에 대한 V(s)의 값이다.
MRP를 계산하는 방법은 크게 세 가지가 있다.
그 중 첫번째가 simulation인데,
그냥 하나하나의 경우의 수를 다 해보는 것이다.
(s4, s5, s6, s7의 경우, s4,s4,s5,s4의 경우 등등 그냥 죄다 해보면서 확률적으로 값을 도출한다는 뜻.)
두 번째 방법은 수학적인 방법이다.
finite state MRP의 경우, V(s)를 Matrix 연산으로 표현 가능한데,
V(s1, s2, ..., sn)은 각각의 state의 Reward (immediate reward)에 가능한 모든 경우의 수 (Markov Chain)에 Discount factor ᵞ를 곱하고, 거기에서 각각의 V(s1, s2, ..., sn)의 값을 또 곱한 것으로 표현이 된다.
(여기서 다시 곱하는 V(s1, s2, ..., sn)은 action을 취한 이후의 지점의 s값을 따른다. 밑의 예시를 참고하자.)
가령, 위의 Mars Rover MRP의 예시를 가져온다면
ᵞ가 0.5일때,
V(4)는 ᵞ(0.5)에다가 s4가 취할 수 있는 모든 경우의 수인 가만히 있기 (0.2), 왼쪽으로 가기 (0.4), 오른쪽으로 가기 (0.4)를 곱하고, 그 각각의 state의 V(s)를 곱해준다. (V(3), V(4), V(5))
더 자세한 예시는 밑에 나온다.
세 번째 방법은 Dynamic Programming이다.
k=1부터 시작해서, 모든 s에 대하여
Vk(s) = R(s) + ∑ᵞP(s'|s)Vk-1(s')를 계산해준다.
(이를 |Vk - Vk-1| < ε(엡실론, 그냥 아주 작은 특정 값) 일때 까지 반복한다.)
(그냥 저 V(s)의 공식을 다이나믹 프로그래밍으로 계산한다는 뜻이다.)
Markov Decision Process (MDP) : Markov Reward Process (MRP) + action
즉, MDP란 MRP에 action이 추가된 최종 진화형이다.
이게 어차피 Markov 변화의 마지막 형태이니까 기호를 하나씩 다시 써보면...
S는 Markov State s의 집합.
A는 actions 의 집합.
P는 각 action에 따른 dymanics/transition model. (위의 MRP / MP와 다르게 action이 포함되었다.)
R은 Reward function으로, 각 state와 action에 따른 reward의 기댓값이다.
그래서, MDP는 이 S,A,P,R과 discount factor ᵞ를 포함한 튜플 (S, A, P, R, ᵞ) 로 표현 가능하다.
위의 사진은 MDP에서의 P의 예시이다.
a1은 왼쪽으로 갈 확률이 1인 (즉, 무조건 왼쪽으로만 가는) action의 집합이고
a2는 오른쪽으로 갈 확률이 1인 (즉, 무조건 오른쪽으로만 가는) action의 집합이다.
Policy : 각각의 state에서 어떤 action을 취할지를 선택하는 것. (그냥 말 그대로 정책이다.)
결정론적(deterministic)일 수도, 확률적(stochastic)일 수도 있다.
Policy는 π(a|s) 이고, 이는 P(at = a | st = s) 와 같다.
그리고, MDP + π(a|s)는 Markov Reward Process 로 유도할 수 있다.
(정확히는, MRP(S, Rπ, Pπ, ᵞ) 로 유도할 수 있다.)
왜냐하면, π(a|s) 그 자체로 어떤 action을 취할지 알려주는 것이므로,
결국 π(a|s)만 알면 그 policy에 대한 reward의 기댓값 Rπ도 도출되고,
취할 행동의 distribution인 Pπ도 도출되는 것이다.
MDP는 MRP에서 R과 P를 Action에 관한 것으로 변경한 것이고,
policy는 각각의 state에 따른 action을 mapping 한 것이므로 (action을 대체 가능하다.)
MRP에서 R, P를 각각 Rπ와 Pπ로만 바꿔주면 되는 것이다.
이 성질은 추후 evaluation을 할 때 MDP가 아닌 MRP만 사용하면 되게 해주는 장점을 갖는다.
즉 위의 MDP + π(a|s) = MRP라는 성질을 사용하면
아까 저기 위에 있던 MRP의 Dynamic programming 수식을 조금만 바꾸어서,
Policy에 대한 V(s)를 구할 수 있게 된다.
(수식 참고)
위의 경우를 보자.
Mars Rover (로봇) 은 왼쪽 또는 오른쪽으로만 갈 수 있다.
s1에 Mars Rover가 위치하면 reward +1, s7에 Mars Rover가 위치하면 reward +10을 주고,
그 외의 나머지 경우에는 reward는 0이 주어진다.
π(s)는 모든 state에 대하여 a1이고 ᵞ=0이라고 했을 때,
Dynamic Programming 방식을 기용한다면 policy의 value는 무엇일까?
답은, s1과 s7에 있을 때를 제외하면 죄다 0이고,
s1에 있을 때는 1, s7에 있을 때는 10이다.
어차피 ᵞ = 0이므로 위의 v(s) 의 식의 ᵞ의 뒤에 있는 식들은 죄다 날라가고,
π(s) 당시의 reward, 즉 immediate reward만 합해주면 되므로
s1에 있을 땐 1, s7에 있을 땐 10이다.
두 번째 문제이다.
P(s6 | s6 , a1) = 0.5, P(s7 | s6,a1) = 0.5 이고,
reward는 위와 같을 때,
π(s) 가 언제나 a1을 취하고 k=1, ᵞ=0.5일때 π(s6)의 reward는?
아까 전의 MRP로의 식을 사용하면 된다.
우선 immediate reward는 0이다. (s6의 reward는 0이므로...)
그리고, P(s6 | s6 , a1) = 0.5, P(s7 | s6,a1) = 0.5이고 ᵞ=0.5이므로 최종 계산식은
0 + ᵞ * 0.5 * v(s6) + ᵞ * 0.5 * v(s7)
= 0 + 0.5 * 0.5 * 0 + 0.5 * 0.5 * 10
= 2.5
가 된다.
MDP Control은 optimal한 policy를 compute한다.
즉, Vπ(s)가 최대가 되는 π의 값을 구하는 것이다.
그리고, optimal한 value function은 언제나 unique 하다. (교수님이 이 부분은 설명을 안하고 넘어가셨다.. 중요하다고만 하심)
아까 전의 Mars Rover의 예시를 다시 가져오자.
states는 s1부터 s7까지 7개의 state가 있고, action은 왼쪽 또는 오른쪽 두 가지만 있다.
이 때, deterministic한 policy는 몇개인가?
ppt에 적혀있듯, 2^7개이다.
(각각의 action 2개가 각각의 state에서 실행 가능하므로)
그리고 이 이후의 예제에서도,
action의 개수 A와 state의 개수 S에 대하여 가능한 policy의 개수는 A^S개이다.
그리고, MDP의 optimal policy는 언제나 unique 한가?
위의 ppt에서 적혀있듯, No 이다. 만약 다른 Policy 두개의 Value가 모두 optimal value function의 값이 된다면,
이 Policy들 모두 optimal policy가 된다.
Policy Search : Optimal한 policy를 찾는 과정.
Policy Iteration은 이의 한 종류이다.
i=0으로 설정하고, π0(s)를 랜덤한 값으로 설정한 뒤 시작하는데,
i==0 or |πi - πi-1| >0일 때 반복한다.
(시작할때와 policy가 바뀌고 있을 때 반복한다.)
그런데, 이것을 제대로 하려면 일단 Policy Improvement가 뭔지 알아야 한다.
일단, PI에 들어가기 전에 먼저 Qπ에 대해 알아보자면,
Qπ(s, a) = R(s, a) + ᵞΣP(s'|s, a)Vπ(s') 이다.
이는 Vπ(s , π(s|a)) 에서 R(s, π(s))를 R(s, a)로 바꿔준 식으로,
일단은 Policy를 따르지 않고 action a를 취한 후에
그 뒤에 policy를 따르겠다는 뜻이다.
그리고, Qπi(s, a)를 모든 State의 s, 모든 Action의 a에 대하여 compute한 뒤에,
모든 State에 대하여 Qπi(s, a)가 최대가 되는 π를 찾는다.
자, Qπi(s, a)는 π(s|a)를 그대로 따르는 것이 아니라 각각의 State에서 가능한 모든 Action을 취하는 것이므로...
Qπi(s, a)의 값들 중 최소한 하나는 π(s|a)보다 크거나 같을 것이다.
(각각의 State에서 가능한 모든 Action은 π(s|a)에서 취한 행동도 포함하므로, 무조건 같은 것 하나는 나오게 된다.)
그리고, 이것을 πi+1에 넣어준다.
이것을, Policy Improvement라고 한다.
그러면, 이제 위에서 무슨 말을 하는지 이해가 될 것이다.
| πi - πi-1 | == 0이라는 것은 결국 πi가 optimal 하다는 뜻이므로 |πi - πi-1| > 0 일때 동안 반복하는 것이고,
그렇게 나온 πi+1로 policy improvement를 해주고, i++을 해준다.
(이렇게 해도 이해 안되면 강의 보쉬던지... 깔깔!)
조금 더 깊게 파고들자면,
Qπi(s, a)의 Max값은 R(s, Vi(s)) .... (이하 Vπ(s))보다 언제나 크거나 같다.
그리고, πi+1(s) 는 Qπi(s, a)의 최댓값을 보장하는 a를 의미한다. (즉, 더 나은 policy가 된다.)
그리고는, 이 이후에는 πi+1을 가져가고, πi는 버린다.
πi+1은 언제나 πi보다 낫거나 같기 때문이다.
즉, 모든 State s에 대해 Vπi >= Vπ2 : Vπ2(s) >= Vπ2(s)라는 이야기이다.
이를 증명 하자면...
위의 수식처럼 된다.
약간 참고만 하라고 첨언하자면,
πi+1 = argmax(a)Qπi(s,a) 이다.
그리고 주목해야할 부분은 두번째줄에서 세번째 줄로 넘어가는 부분인데,
Vπi(s) <= max(a) Qπi(s, a)이므로,
Vπi(s') <= max(a) Qπi(s', a) 이라는 점에서 두 번째 줄에서 세 번째 줄로 넘어갈 수 있다.
이를 계속 반복하다 보면, 결국 Vπi(s) <= Vπi+1(s) 라는 식이 나오게 된다.
(증명은 알아서 이해할 수 있도록 하자 ㅎ)
위 ppt의 조건대로라고 했을 때, (Policy Iteration을 사용할 때)
만약 Policy가 한번 바뀌지 않으면 앞으로도 바뀌지 않는가?
PI에서 최대 반복 횟수가 있는가?
답은 위에서 확인하도록 하자. (설명도 잘되어 있다.)
첫 번째 질문에 대한 comment만 달자면, 한번 Policy가 바뀌지 않으면
| πi - πi+1 | == 0이 되므로
더이상 Policy Iteration이 진행되지 않는다.
그러므로, Policy도 더이상 변하지 않는다.
다음은 Value Iteration이다.
위의 Policy Iteration과 비슷하다고 느껴질 수 있지만, 조금 다른 방식이다.
V0(s)를 0으로 초기화 한 뒤에,
V가 어떤 값으로 Converge 될때 까지 (수렴할때 까지), 또는 horizon이 끝날때 까지
Vk+1(s) = max(a) R(s, a) + ᵞΣP(s'|s, a)Vk(s')
을 반복한다.
풀어 말하자면, 각각의 time step에 대해서 최선의 선택만을 가지고 가는 것이다.
이는 원래 Policy를 랜덤으로 취한 뒤 policy를 가장 좋은 것으로 바꾸어 가는 Policy Iteration과는 다른 방식으로,
처음의 time step 0으로 시작해서, 모든 state에서 가능한 최선의 action만을 취해서 Policy를 만들어 가는 것이다.
그리고, Value Iteration은 수렴하는가? 에 대한 답은 YES이다.
결국 V(s)의 값에는 지속적으로 ᵞ가 씌워지므로,
Horizon이 무한하더라도 1보다 작은 ᵞ값을 무한정 제곱하여 더하는 꼴이 되므로
일정한 값에 수렴하게 된다.
Value Iteration과 Policy Iteration간의 차이점을 설명하자면,
Value Iteration은 time step (horizon) = k일 때의 optimal value를 찾아가며 k를 증가시키는 형식이고,
Policy Iteration은 infinite한 horizon에서 더 나은 policy를 찾아가는 형식이다.
이 Policy Iteration은 RL에서 매우 유명한 Policy Gradient라는 방식과 매우 유사하다.
여기까지 CS234 2강을 정리하도록 하겠다.
사실 그냥 간단한 정리노트만 쓰려고 했는데, 어찌어찌하다 보니 뭔가 강의 형식이 되어 버렸다.
그냥 정리 노트와 강의를 합쳐버리는 게 나을지도 모르겠다.
'인공지능 > 강화 학습 정리 (CS234)' 카테고리의 다른 글
| 강화학습 강의 (CS234) 6강 - CNN + DQN (Deep Q Network) (0) | 2019.06.06 |
|---|---|
| 강화학습 강의 (CS234) 5강 - Value Function Approximation (4) | 2019.05.27 |
| 강화학습 강의 (CS234) 4강 - MC / SARSA / Q-learning (1) | 2019.05.08 |
| 강화 학습 강의 (CS234) 3강 - Model-Free Policy Evaluation (Monte Carlo / Temporal Difference) (3) | 2019.04.21 |
| 강화 학습 강의 (CS234) 1강 (1) - 강화 학습이 뭘까? / Markov란? (5) | 2019.04.06 |