본 내용은 David Silver 교수님의 Reinforcement Learning 강좌, Markov Decision Process 부분을 토대로 작성한 글입니다.
1. What is Markov Decision Process?
Markov Decision Process(MDP) 는 대부분 강화학습에서 사용하고 있는 만큼 꼭 알아야 합니다. 앞 장 에서는 Agent 를 주로 얘기했습니다. 사실 environment 가 정확히 무엇인지 설명하지 않았기도 합니다. 이번 MDP 를 통해서 환경(Environment) 에 대해 설명하겠습니다. 왜냐하면 MDP 는 강화학습(Reinforcement Learning) 에서 환경(Environment) 를 설명하기 때문이죠.
MDP 를 간단히 정의하면, Process 의 온전한 특성들(completely characteries) 이라고 할 수 있습니다.
1.1. Markov Property
“The future is independent of the past given the present”
현재가 주어진다는 조건아래 미래는 과거로부터 독립적이다라는 얘기인데요. 과거(History) 를 없애고 State 만 기억하는 것이 Markov Property 라고 합니다.
수식은 과거로부터 독립적임을 표현한 것일 뿐이고 1(과거, 혹은 시작점)에서부터 지금까지 쌓인 State 가 결국 현재의 State 와 미래에 일어날 S_{t+1}에 대해서 확률적으로 동일하다는 것을 얘기하고 있습니다. 즉, 현재 State 가 충분한 통계량을 가지고 있기에 미래를 예측할 수 있다고 할 수 있죠. 이 내용은 Markov 의 주장이니 근거를 살펴봅시다. 그 전에, 이 수식이 맞다면 우리는 무엇을 얻을 수 있을까요? 과거의 모든 상태를 다 따져서 메모리에 넣어두기보다 현재 상태만 가지고 있어서 보다 더 빠른 계산도 가능할 것이고 자원관리 차원에서 효율도 충분히 올라갈 것으로 보입니다.
State Transition Matrix
State Transistion Matrix 는 지금의 상태 s와 그로부터 이어지는 상태 s’로 이어지는 확률들을 희소행렬(Sparse Matrix) 의 형태로 만든 것입니다.
Pss’는 이어지는 상태에 대해 발생할 확률을 얘기하겠죠. 여러 상태가 경우의 수로서 만들어지지 않겠습니까? 그게 아래처럼 보여질 수 있습니다.
\[\quad \qquad \quad\text{to}\\P = \text{from} \left[ \begin{matrix} P_{11} \dots P_{1n}\\ \vdots\\ P_{n1} \dots P_{nn} \end{matrix} \right]\]잘 생각해보면 행의 합이 1입니다. 예를 들겠습니다. 0~9까지 적힌 10장의 카드를 하나 뽑았을 때, 0이 나왔습니다. 이어서 뽑을 때 1~9까지 나올 확률은 100%(1)고 각 값들이 나올 확률은 100/9 %(1/9) 입니다.
다시 그림을 보여드리겠지만, 값이 들어간 희소행렬은 위와 같습니다.
1.2. Markov Chains(Markov Process)
State Transition Matrix 에서 연쇄적인 상태에 대해 언급이 됐습니다. 그 생각이 발전되어 Markov Chains(Markov Process) 는 연쇄적인 상태발생에 대한 얘기를 합니다.
Markov Process
먼저 Markov Process 는 복원추출개념의 Memoryless Random Process를 얘기합니다. 수학적 정의을 먼저 볼까요? 혹시 아시는 분이 있을 지는 모르겠는데, Timed-Finite State Automata(F-FSA) 와 유사한 성질을 지닙니다. 학술적으로는 다르지만, 아시는 분이 있다면 State 는 동일하고 Time 값이 Prob. 값으로 바뀌었으니 쉽게 이해할 수 있습니다.
수학적 정의를 보면 Markov Process 는 2-tuple 구조입니다. S는 유한한 상태의 집합이고, P는 위에서 설명한 STM 입니다. 아래는 Markov Process Diagram 입니다.
상태와 확률에 대해서 트리와 행렬로 표현합니다. 이제 좀 환경(Environment) 이라고 할 수 있겠죠?
2. Markov ‘Reward’ Process
그동안 Markov Process 를 설명했습니다. 이제 보상(Rward) 를 곁들인…
Markov Reward Process 는 4-tuple로 구성됩니다. 추가된 R은 기대되는 보상(Reward) 그 자체를 의미하고, 감마 는 미래에 얻을 수 있는 보상(Reward) 의 중요도를 조절할 수 있는 Discount factor 입니다. 강화학습(Reinforcement) 는 목표 지향 계산법(Goal-Directed Computational Approach) 이기에 보상은 agent 를 움질일 수 있도록 도와주죠. 참고로 감마 가 0에 가까울 수록 근시적 평가(myopic) 가 이뤄지고 1에 가까울수록 원시적 평가(far-sighted) 가 이뤄집니다.
감마 위에 k 가 있으니, 스텝이 이어질수록 점점 보상이 적어집니다.
왜 Discount factor가 필요한가?
- 수학적으로 가중치(
Discount factor)는 계산(Reward)을 편하게 도와줍니다. Markov Process는 순환가능합니다. Class1 -> Facebook 을 영원히 돌 수 있죠. 그러니, 순환에서 이탈하도록 도와줍니다.- 불확실한 미래에 대한 감안을 할 수 있습니다.
- 보상이 재정적이라면, 즉시 보상(
immediate rewards)에 대해 더 높은 가치를 부여합니다. - 행동은 즉각적인 보상에 대한 선호도를 가지게 합니다.
이제 슬슬 다이어그램이 제법 강화학습에서 얘기하는 환경(Environment) 로 보이네요. Reward 를 통해 어디를 가야할 지 목표가 있어 보입니다.
값을 대입하면 아래와 같은 모양이 나옵니다. 단, 쉬운 계산을 위해 감마 는 0입니다.
2.1. Bellman Equation
Richard E. Bellman 은 저희에게 친숙한 이름입니다. Bellan-Ford algorithm 에서 동적 계획법을 통해 미래가치를 보고 최단거리를 찾는 아이디어를 제안한 사람이고, 차원의 저주라는 표현을 맨 처음 얘기한 사람입니다.
State Value function 은 두 가지의 조건으로 나눠집니다.
현재 가치에 미래 가치를 더하여 최적의 경로를 찾아내는 것이죠.
결론적으로 Bellan equation 은 선형방정식이라 아래 표현처럼 볼 수 있습니다.
자 그럼 방정식을 풀어보겠습니다.
\[\begin{array}{l} \text{v} = R+\gamma P\text{v}\\ (I-\gamma P)\text{v} = R\\ \text{v} = (I-\gamma P)^{-1}R \end{array}\]Big-O notation 에 의한 계산복잡도는 O(n^3) 이 나옵니다. 이처럼 규모가 작을 때는 바로 해결할 수 있고 규모가 클 때는 아래 세 가지의 이미 알려진 방법으로 해결할 수 있습니다.
- Dynamic programming(동적 계획법)
- Monte-Carlo evaluation(몬테 카를로 평가법)
- Temporal-Difference learning(시간차 학습)
3. Markov ’Decision’ Process
긴 시간을 함께 해주셨습니다. Markov Process 는 그저 맵일 뿐, 어디가 중요한지 몰랐죠. Markov Reward Process 는 어디가 중요한지 보상(Reward) 이랑 Discount factor 를 가중치로서 알려줬습니다. 더 나아가, 이제 결정(Decision) 에 대한 Markov Process 를 알아보겠습니다.
Markov Decision Process(MDP) 는 Markov Reward Process 에 여러 결정들이 들어가 있는 경우입니다. 어떻게 결정을 할까요? 바로 행동(action) 이 추가됩니다. 모든 States 에 대한 환경(Environment)이라고 할 수 있죠. MDP 는 5-tuple 입니다.
Markov Decision Process 에서는 A set 이 추가되고 P 가 변했습니다. A 는 유한한 수를 가지는 행동에 대한 집합이고, P 위에 붙은 a 는 다음 상태가 되기까지 현재의 state 와 action 을 고려한 확률입니다.
3.1. Policies
제가 앞 전에 정책(Policy) 은 Function approximator 라고 설명드렸었는데요. MDP 를 설명하면 좀 더 개념을 잡겠습니다.
정책(Policy)은 agent 의 행동(action) 에 대해 모두 정의합니다.
MDP 정책은 과거(history) 를 제외하고 현재 상태에만 의존합니다. 이는 Markov Process 에서 현재 상태(State) 가 과거의 기록을 다 반영하고 있음을 따라갑니다.
정책(Policy) 은 시간에 독립적이며 업데이트를 진행하기 전 까지는 고정되어 있습니다.(stationary)
환경(MDP) 와 정책(Policy) 이 있다면, 과거로부터 이어져오는 일련의 상태(States) 는 Markov Process 에 있습니다. 그리고 상태와 보상이 이어지는 것은 Markov Reward Process 에 있죠. 이를 정리하면 아래와 같습니다.
이제 저희는 파이가 정책이라는 점을 알았습니다. 그럼 해당 정책에서 State Value function 은 위 Bellan Equation 에서 크게 변하지 않고 아래처럼 볼 수 있습니다.
또한 Action-Value function 은 해당 정책(파이)를 따를 때, 상태와 행동에서 기대되는 가치를 확인할 수 있습니다.
3.2. Bellman Expectation Equation
State-Value function 은 즉각적인 reward와 다음 state 에 감마(discount factor) 로 나눌 수 있습니다. Bellman Equation 이 다시 나오는 순간이죠.
Action-Value function 도 위와 유사하게 나눌 수 있습니다.
이제 트리로서 설명하겠습니다.
정책(Policy)은 여전히 파이입니다. 흰색 원은 상태(State) 이고, 검은색 원은 행동(Action) 입니다. 왼쪽 이미지와 오른쪽 이미지 모두 State 와 Action 의 시작점만 다를 뿐 가치 함수 를 얘기하고 있습니다.
왼쪽 오른쪽 트리에 대한 수식은 이렇게 정리할 수 있겠네요.
\[v_{\pi}(s) =\sum_{a\in A}\pi(a|s)q_\pi(s,a)\qquad q_\pi(s,a)=R_s^a+\gamma\sum_{s'\in S}P_{ss'}^a v_\pi(s')\]이 두가지는 앞으로 Q function , Q Learning, DQN, PPO, SAC , DDPG 등을 이해하는데 기저가 됩니다. Action 과 State 가 어떻게 엮여있는지 나타내줍니다.
위 그림은 현재상태(s) 에서 다음상태(s') 까지의 함수를 나타냅니다. 하나의 상태(s)에 대해서 두 가지의 action 을 할 수 있고, 각 action 들이 두 개씩 다음 state 를 맡고 있습니다. 같은 이유로 오른쪽은 action 에 초점을 맞춘 트리입니다. 이 또한 두 가지 식으로 얘기할 수 있죠. 위 식에서 뻗어져나온 것이니 크게 다를 건 없습니다.
다음 상태(s')와 액션(a') 에 대한 가치 함수(function) 수식들 입니다. 특히 q(s,a) 가 많이 바꼈죠.
Matrix form 에 대한 Bellman Expectation Equation 은 아래와 같습니다.
3.3. Optimal Value Function and Policy
최적화된 가치 함수(Optimal Value Function) 는 모든 정책(Policies) 을 넘어서 가치함수(Value function 가 최대화될 때를 의미합니다. 당연하겠지만, state-value function, action-value function 둘 다 있습니다. 별거 아니지만, 아래 식을 참고해볼까요.
또한 최적화된 정책(Optimal Policy) 도 있습니다. Optimal Policy 는 정책들(Policies) 에서 부분순서(partial ordering) 를 정의합니다. 다만, 여기서는 집합론의 의미로서 수식을 표현합니다.
수식에 대한 설명은 아래와 같습니다.
For any Markov Decision Process
- 모든 정책들 중에서, 최적의 pi*가 존재합니다.
- 모든 최적의 정책들이 최적의 가치 함수를 만들어 줍니다.
- 마찬가지로 모든 최적의 정책들이 최적의
action-value function을 만들어 줍니다.
직역이 아닙니다. 아래 원 내용을 참고하세요.
\(\begin{array}{l} \text{For any Markov Decision Process}\\ \cdot\ \text{There exists an optimal policy } \pi_*\ \text{that is better than or equal to all other policies, }\pi_*\ \ge\ \pi,\ \forall\pi \\ \cdot\ \text{All optimal policies achieve the optimal value function, }v_{\pi_*}(s)=v_*(s)\\ \cdot\ \text{All optimal policies achieve the optimal action-value function, }q_{\pi_*}(s,a) = q_*(s,a) \end{array}\) 최적의 정책(optimal policy) 는 최적의 q function 을 최대화하면서 찾을 수 있습니다.
어떤 MDP 에 대해 늘 결정적입니다. 또한 우리가 최적의 q function 을 알고있다면, 즉시 최적의 정책(optimal policy) 를 찾을 수 있습니다.
Sleep(끝) 에서 역순으로 Reward 를 대입합니다. 결국 미래가치를 알 수 있게 됩니다.
4. Extensions to MDPs
MDP 를 응용한 몇 가지 방법을 설명하겠습니다.
4.1. Infinite and continuous MDPs
Infinite and Countinuous MDPs 는 연속된 시간과 상태, 그리고 무한한 상태(state)와 액션(action) spaces를 의미합니다. space 는 실행 가능한 경우들로 이해하시면 됩니다. 첫 번째로 무한한(Infinite) 공간(state and/or action spaces) 이라면 무엇이 달라질까요? 바로 Straightforward 의 성질이 생깁니다. 깊이우선탐색(Depth-First Search) 에서 어떤 노드의 자식들이 끝도 없이 이어져있다면, 옆에 있는 형제노드를 쳐다도 안보고 앞만 달려가겠죠? 직진성(Straightforward) 입니다. 두 번째는 연속된 공간(Continuous state and/or action spaces) 입니다. 먼저 사람의 생각과 지금까지의 MDP 는 모두 이산(Discrete) 형태로서 동작합니다. state , action 모두가 0에서 바로 1로 바뀌듯 비연속적이죠. 만약 연속으로 바뀐다면 닫힌 형태(Feed back, Closed loop, Closed form)를 가지게 됩니다. 이 부분의 자세한 설명은 UC Berkeley 교수의 Benjamin Recht의 글인 Total Control 에 매우 정확한 설명이 있습니다. 끝으로 위 두 설명에 의해 종속되는 연속된 시간(Continuous time) 의 얘기입니다. 연속된 시간으로 바뀐만큼 이제 상태(state), 행동(action) 에 대해 편미분을 해야합니다. 우리는 연속에 대한 변화량을 알아야하니까요.
4.2. Partially observable MDPs
POMDPs(Partially Observable Markov Decision Process) 는 숨겨진 상태(Hidden states)가 들어간 MDP 입니다. 7-tuple로 표현하고 아래와 같습니다.
O는 Observation 으로 환경에서 얻어지는 측정값이고 다음 상태와, 현재 행동이 주어지면 다음에 기대되는 Observation 확률을 알 수 있다는 Z 함수 입니다. 이를 보면 행동을 통해서 측정값이 나온다는 것을 표현했다고 볼 수 있죠.
4.3. Undiscounted, average reward MDPs
끝으로 Average Reward MDP 입니다. ` Ergodic Markov Process(EMP) 라고 하며 이는 사실 중심극한의 정리와 비슷한 얘기입니다. EMP`의 설명을 아래서 확인할 수 있습니다.
순환(Recurrent): 각 상태는 무한한 숫자로 반복된다.
간헐(Aperiodic): 각 상태는 일정한 주기에 상관없다.
EMP 는 제한적으로 고정된 분산 d^pi(s)를 가지고 있습니다. 또한 어떤 정책 파이여도 Ergodic MDP 는 시작 상태(state) 와 독립적으로 시간(p^pi)으로 나눠진 평균 보상(Reward)을 가집니다. 주기가 없이 반복되는 수가 엄청나게 많아지면 특정한 분포를 따르기 때문이죠.
이러한 특성 때문에 Average Reward Value Function 은 undiscounted 합니다. 그래서 Ergodic MDP는 평균 보상(Average Reward) 으로 표현합니다. 아래는 s에서 시작할때 추가되는 보상에 대한 설명입니다. 그리고 그에 맞춘 Bellan equation 입니다.