CS234 2강 Summary
CS234 강의 중 Lecture 2(Given a Model of the World)을 듣고 정리해보자
본 포스팅은 Stanford Univ의 CS234:Reinforcement Learning 강의를 듣고 정리한 글입니다.
Markov Process
저번 포스팅에서도 말했듯이 Markov State는 다음 상태가 현재 상태에만 의존하고, 그 이전의 상태나 액션에는 의존하지 않는 성질을 가진 State이다. 따라서 전체 History를 알 필요 없이 현재 State만을 고려하여 최적의 행동을 결정할 수 있다.. 만약, 시스템에 Markov 성질이 없다면 Agent는 과거의 정보 즉, 더 많은 정보를 기억하고 이를 바탕으로 행동을 결정해야 하므로 학습이 더 복잡해질 수 있다.
위 그림과 같이 Markov Process는 Markov 한 상태를 띄는 랜덤한 State들로 구성되어 있으며 Action와 Reward가 없는 상태이지만 시간이 지남에 따라 진화하는 확률론적 프로세스가 있을 수 있다. 시간에 따라 바뀌는 주식 시장이 그 예이다.
S는 states의 유한집합이고, P는 현재 state $s$ 에 대해 다음 state $s^{\prime}$ 를 나타내는 dynamics/transition model이다.
그림에서도 확인할 수 있듯이 이러한 Process를 Matrix로 하여 나타낸 것이 Markov Chain이다.
위 그림은 Markov Chain의 예시이며, 각 state 아래에 적혀 있는 확률은 다음 step에서도 같은 state로 머물 확률을 의미한다. (즉, Diagonal entry 들을 의미한다고 볼 수 있다.)
또한 $s_{1}$에서 $s_{2}$ 로 state를 전환할 확률은 0.4이며, $s_{1}$에서는 같은 state에 머물거나 $s_{2}$ 로 전환하는 2가지 case가 있으며, 이에 반해 $s_{2}$ 의 경우, 제자리에 머물거나 $s_{1}$ 혹은 $s_{3}$ 로 전환할 수 있다. (3가지 Case) 따라서 이러한 확률들을 Matrix 형태로 전개한 것이 위의 그림에서의 P이다.
Markov Reward Processes(MRPs)
Markov Reward Processes은 Markov Process에 reward를 추가한 것으로, reward는 생겼지만, 아직 action은 없다.
S와 P의 정의는 이전과 동일하고, R는 reward function로 현재 state에 대한 reward의 기댓값을 표현하는 함수이다.
다음으로는 앞으로 자주 볼 용어들의 정의를 정리해보자.
-
Horizon : 각각의 에피소드에 대한 time step의 개수 즉, Agent가 작동하는 시간 혹은 Process가 진행 되는 시간을 의미하며, Horizon이 무한하지 않으면 finite Markov reward process라고 불리지만, 우리는 Agent가 영원히 행동하거나 Process가 영원히 진행될 수 있는 경우 즉, Horizon이 무한한 경우에 대해 자주 생각한다. 예를 들어, 주식 시장은 오늘도 열리고 내일도 열리고 모레도 열리고 …. 하는 식이다. (그러니까 여기서 말하는 infinite는 엄밀한 정의의 infinite가 아니라, 그만큼 엄청 많아서 무한하다고 불러도 될 정도를 의미한다. 주식 시장은 사실상 우리가 살아있는 동안은 열려 있지 않겠는가? 그런 식이다.)
-
Return function($G_{t}$) : time step t부터 Horizon까지의 reward의 discounted sum으로 Process가 끝날 때까지 reward에 discount factor($\gamma$)를 곱한 값의 합이다.
-
State Value Function($V(s)$) : state $s$에서 얻을 수 있는 reward의 기댓값을 의미한다. Return function은 실제로 얻는 reward를 의미하고, Value Function은 그 reward의 기댓값이므로, 서로 다를 수 있다. (물론, Deterministic한 경우엔 같을 수도 있다.)
discount factor($\gamma$)의 경우 지난 포스팅에서도 정의했지만, immediate reward (현재에 받는 즉각적 보상)과 future reward (미래에 얻을 보상)과의 연관관계를 나타낸다. [0, 1]의 범위 안에서, ($\gamma$) = 0 이면 future reward(미래의 보상)를 무시하고 immediate reward(현재의 보상)만 고려하겠다는 것을 의미하고, ($\gamma$)=1 이면 미래의 보상을 현재의 보상만큼 중요하게 고려함을 의미한다.
만약, Horizon이 무한하다면 보상의 총합은 무한대로 커지기에 discount factor($\gamma$)가 1이 될 수 없고, 반대로 유한하다면 discount factor($\gamma$)를 1로 설정할 수 있다. 보통은 0에서 1사이의 값을 사용한다.
MRP 계산방법
MRP를 계산하는 방법은 크게 세 가지가 있다. 그 중 첫 번째 방법은 Simulation이다. 이는 state $s_{4}$에서 시작해서 위의 그림 처럼 $s_{4},s_{5},s_{6},s_{7}$ 혹은 $s_{4},s_{4},s_{5},s_{4}$ 등 하나하나의 경우의 수를 다 해보는 것이다.
두 번째 방법은 수학적인(analytic) 방법이다. 위의 그림에서 확인할 수 있듯이 finite state MRP의 경우, V(s)를 Matrix 연산으로 표현 가능한데, $V(s)$ 은 각각의 state의 Reward (immediate reward)에 가능한 모든 경우의 수 (Markov Chain)에 Discount factor $\gamma$ 를 곱하고, 거기에서 각각의 $V(s)$의 값을 또 곱한 것으로 표현이 된다.
예시를 들어보기 위해 앞서 언급했던 Markov Chain에서의 예제를 다시 살펴보자.
Discount factor $\gamma$ 가 0.5일때, 해당 state에서의 reward에다가 $V(s_{4})$ 는 $\gamma$ 와 모델의 transition 확률(P) 다시 말해서 $s_{4}$ state 에서 취할 수 있는 모든 경우의 수인 가만히 있기 (0.2), 왼쪽으로 가기 (0.4), 오른쪽으로 가기 (0.4)를 곱하고, 그 각각의 state의 $V(s)$ 를 곱해준다. 예를 들어, 가만히 있기 (0.2) 의 경우 $V(s_{4})$를, 오른쪽으로 가기 (0.4)의 경우 $V(s_{5})$ 를 곱해준다.
마지막으로 세 번째 방법은 Dynamic Programming이다. 이 방법은 위의 그림에서도 확인할 수 있듯이 k=1부터 시작해서 $V_{k}(s)$ 수식을 $V_{k}$ 와 $V_{k-1}$간의 차이가 우리가 설정할 아주 작은 값이 될 때까지 Dynamic Programming으로 반복하여 계산하는 방법이다.
Markov Decision Processes(MDPs)
Markov Decision Processes(MDPs)는 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 $\gamma$를 포함한 튜플 $(S,A,P,R,\gamma)$ 로 표현 가능하다.
Policy는 각각의 state에서 어떤 action을 취할지를 선택하는 것 즉, 말 그대로 정책 or 전략이라고 생각해볼 수 있다. 이는 결정론적(deterministic)일 수도, 확률적(stochastic)일 수도 있다.
여기서 결정론적(deterministic)이란 말은 상태와 보상이 정해져 있는 경우를 의미하며, 이에 반해 확률적(stochastic)이라는 것은 상태와 보상이 확률적으로 결정되는 경우를 의미한다.
이러한 Policy는 $\pi(a \vert s)$ 로 표현할 수 있고, 이는 $P(a_{t}=a \vert s_{t}=s)$와 같다.
또한, MDP + $\pi(a \vert s)$ 는 MRP(Markov Reward Process) 로 유도할 수 있다. (정확히는, MRP(S, Rπ, Pπ,$\gamma$)로 유도할 수 있다.)
왜냐하면, $\pi(a \vert s)$ 가 어떤 action을 취할지 알려주는 것이므로, $\pi(a \vert s)$ 만 알면, 해당 Policy에 대한 reward의 기댓값 $R^{\pi}$ 도 도출되고, 취할 행동의 distribution인 $P^{\pi}$ 도 도출된다.
MDP는 MRP에서 R과 P를 Action에 관한 것으로 변경한 것이고, policy는 각각의 state에 따른 action을 mapping 한 것이므로 action을 policy로 대체 가능하기에 MRP에서 R과 P를 MDP에서는 각각 $R^{\pi}$,$P^{\pi}$ 로 바꿔주면 된다.
이러한 성질은 추후 evaluation을 할 때 MDP가 아닌 MRP만 사용하면 되게 해주는 장점을 갖는다.
즉 위의 그림과 같이 MRP의 Dynamic programming 수식을 조금만 바꾸어서, Policy에 대한 Value function $V(s)$를 구할 수 있게 된다.
이는 특정 Policy에 대한 Bellman backup이라고도 한다.
Example 1
위 그림과 같은 예시를 보자.
Mars Rover (로봇) 은 왼쪽 또는 오른쪽으로만 갈 수 있다. $s_{1}$에 Mars Rover가 위치하면 reward +1, $s_{7}$ 에 Mars Rover가 위치하면 reward +10을 주고, 그 외의 나머지 경우에는 reward가 0으로 주어진다.
$\pi (s) = a$ 즉, Policy가 항상 aciton $a_{1}$만 수행하고, $\gamma = 0$ 이라고 했을 때, Dynamic Programming 방식을 기용한다면 Policy의 value는 무엇일까 ?
$\gamma = 0$ 이므로 현재의 reward 즉, immediate reward만 합해주면 되므로 $s_{1}$에 있을 때는 +1, $s_{7}$에 있을 때는 +10, 그 외의 나머지 state에 있을 때는 전부 0이다.
Example 2
위 그림과 같은 예시를 보자.
State $s_{6}$에 있을 때, action $a_{1}$으로 인해 그곳에 머물 확률이 0.5, $s_{7}$ 로 갈 확률이 0.5라고 하자. reward 는 $s_{1}$이 1, $s_{7}$ 이 10이고 그 외는 0이다. 또한 $\gamma = 0.5$ 이다.
하나의 backup만을 진행할 때 즉 다시 말해서 k=1에서 k=2가 될 때, $\pi (s_{6})$ 의 reward는 뭘까 ?
이전의 MRP식을 이용해보자.
$s_{6}$에서의 reward는 0이기에 immediate reward는 0이다. 따라서 최종 계산식은 슬라이드와 같이 $0 + 0.5 * 0.5 * 0 + 0.5 * 0.5 * 10 = 2.5$로 계산된다.
MDP Control
MDP Control은 optimal한 policy를 compute한다. 즉, $V^{\pi}(s)$를 최대화시키는 $\pi$를 구하는 것이다.
Example 3
아까 전의 Mars Rover의 예시를 다시 가져오자.
action은 왼쪽 또는 오른쪽 두 가지만 있다. 이 때, deterministic한 policy는 몇개인가 ?
각각의 action 2개가 각각의 state에서 실행 가능하므로 $2^{7}$이다. 즉 action의 개수 A와 state의 개수 S에 대하여 가능한 policy의 개수는 $A^{S}$ 개 이다.
그리고, MDP의 optimal policy는 언제나 unique 한가?
위의 ppt에서 적혀있듯, No 이다. 만약 서로 다른 Policy 두 개의 Value가 모두 optimal value function의 값이 된다면, 이 Policy들 모두 optimal policy가 된다.
How to find Optimal Policy
그러면 이러한 Optimal Policy는 어떻게 찾을 수 있을까 ?
Policy Iteration
Optimal한 policy를 찾는 과정을 Policy Search 라고 하는데, Policy Iteration는 이의 한 종류이다.
위의 슬라이드에서 확인할 수 있듯이 Policy Iteration는 i=0으로 설정하고, $\pi_{0} (s)$를 랜덤한 값으로 설정한 뒤 시작하는데, $ i ==0\,or\,\vert \pi_{i} - \pi_{i-1} \vert > 0 $일 때 반복한다. 즉, 시작할 때와 policy가 바뀌고 있을 때 반복한다.
그런데, 이것을 제대로 하려면 일단 Policy Improvement가 뭔지 알아야 하며, Policy Improvement에 대해 들어가기 전, State Action Value $Q^{\pi}$에 대해서 알아보자.
\[Q^{\pi} (s,a) = R(s,a) + \gamma \sum_{s^{\prime} \in S} P(s^{\prime} \vert s,a) V^{\pi}(s^{\prime})\]이는 State Value function $V^{\pi}$ 에서 $R(s,\pi(s))$를 $R(s,a)$로 바꿔준 식으로, 일단은 Policy를 따르지 않고 action a를 취한 후에 그 뒤에 policy를 따르겠다는 뜻이다.
위의 그림에서 알 수 있듯이 Policy Improvement는 $Q^{\pi_{i}}(s,a)$ 를 모든 State의 s, 모든 Action의 a에 대하여 compute한 뒤에, 모든 State에 대하여 $Q^{\pi_{i}}(s,a)$ 가 최대가 되는 $\pi$를 찾는 것이다.
앞서 말했듯, $Q^{\pi_{i}}(s,a)$는 $\pi(s \vert a)$를 그대로 따르는 것이 아니라 Action을 취하고 Policy를 따르는 것 즉, 각각의 State에서 가능한 모든 Action을 취하는 것이므로 $Q^{\pi_{i}}(s,a)$ 의 값들 중 최소한 하나는 $\pi(s \vert a)$ 보다 크거나 같을 것이다.(각각의 State에서 가능한 모든 Action은 $\pi(s \vert a)$에서 취한 행동도 포함하므로, 무조건 같은 것 하나는 나오게 된다.)
이렇게 최대가 되는 $Q^{\pi_{i}}(s,a)$ 를 다음 Policy 즉, $\pi_{i+1}(s)$에 넣어준다. 이것을 Policy Improvement라고 한다.
따라서 앞서 Policy itration 슬라이드에서 $\vert \pi_{i} - \pi_{i-1} \vert == 0$ 이라는 것은 결국 $\pi_{i}$가 optimal 하다는 것이므로 $\vert \pi_{i} - \pi_{i-1} \vert > 0 $ 일 때 동안 반복하는 것이고, Policy improvement를 통해 새로운 Policy $\pi_{i+1}(s)$를 구하고 i++ 를 한다.
정리하자면 $\vert \pi_{i} - \pi_{i-1} \vert == 0$ 이 될 때 까지 즉, 최적의 Policy가 나올 때 까지 Policy Improvement를 반복하는 것이 Policy iteration이다.
Policy iteration을 하다 Policy가 바뀌지 않으면 $\vert \pi_{i} - \pi_{i-1} \vert == 0$ 을 의미하는 것으로 더이상 Policy Iteration이 진행되지 않는다.
Value Iteration
Value Iteration은 Policy Iteration과 비슷하다고 느껴질 수 있지만, 조금 다른 방식이다.
Value Iteration은 $V_{0}(s)$ 를 0으로 초기화 한 뒤에, V가 어떤 값으로 Converge 될때 까지 (수렴할때 까지), 또는 horizon이 끝날때 까지 슬라이드 속 수식($V_{k+1}(s) = \sim $)을 반복한다.
풀어 말하자면, 각각의 time step에 대해서 최선의 선택만을 가지고 가는 것이다. 이는 원래 Policy를 랜덤으로 취한 뒤 Policy를 가장 좋은 것으로 바꾸어 가는 Policy Iteration과는 다른 방식으로, 처음의 time step 0으로 시작해서, 모든 state에서 가능한 최선의 action만을 취해서 Policy를 만들어 가는 것이다.
이 때 Value Iteration에서 $V(s)$ 의 값은 수렴한다. 왜냐하면 지속적으로 $\gamma$가 씌워지므로, Horizon이 무한하더라도 1보다 작은 $\gamma$ 값을 무한정 제곱하여 더하는 꼴이 되기 때문이다.
2가지 방식의 차이점
Value Iteration과 Policy Iteration간의 차이점을 설명해보자.
우선 Value Iteration은 time step (horizon) = k일 때의 optimal value를 찾아가며 k를 증가시키는 형식이다.
그에 반해, Policy Iteration은 infinite한 horizon에서 더 나은 policy를 찾아가는 형식이다. 이러한 Policy Iteration은 RL에서 매우 유명한 Policy Gradient라는 방식과 매우 유사하다.
댓글남기기