Lecture 2. 마르코프 결정 과정 (Markov Decision Process)

마르코프 성질 (Markov Property)

• 과거와 현재 상태가 주어졌을 때, 미래 상태의 조건부 확률분포가 과거 상태에 영향을 받지 않고 독립적으로 현재 상태로만 결정되는 것을 의미한다.

$$\text{ A state }S_t \text{ is Markov}\text{ if and only if } P[S_{t+1} \mid S_{t} ] = P[S_{t+1} \mid S_{1}, S_{2}, ..., S_{t}] $$

마르코프 과정 (Markov Process, Markov Chain)

• 마르코프 과정은 Memoryless한 특징을 가지는 Random Process이다. 즉, 마르코프 성질을 띄며 상태가 무작위적으로 변하는 과정을 가진다는 의미이다.
  $$\text{ A Markov Process (or Markov Chain) is a tuple } \left\langle \mathcal{S}, \mathcal{P} \right\rangle \ \text{ } \\ \begin{aligned} &\mathcal{S} \text{ is finite set of states.} \\ &\mathcal{P} \text{ is a state transition probability matrix.} \end{aligned}$$

예시
$$ \mathcal{S} = \{ s_0, s_1, ... , s_n \} $$

상태 전이 확률 (State Transition Probability)

• 상태 전이 확률이란 각 상태에서 각 상태로 이동할 확률이다.

• Markov한 상태에서 다음 상태로 이동할 때의 상태 전이 확률은 다음과 같이 표현할 수 있다.
  $$ \mathcal{P}_{ss'} = \mathbb{P}[S_{t+1} = s' \mid S_{t}=s]$$

• 또한 상태 전이 확률을 행렬로 표현할 수 있다. (State Transition Probability Matrix)
  $$
  \mathcal{P}=
  \begin{bmatrix}
  \mathcal{P_{11}} & \cdots & \mathcal{P_{1n}} \\
  \vdots & \ddots & \vdots \\
  \mathcal{P_{n1}} & \cdots & \mathcal{P_{nn}}
  \end{bmatrix} (\mathcal{P}_{ij}\text{ means probability of moving from } s_i \text{ to } s_j )
  $$

Episode와 Sampling

마르코프 과정 (Markov Process)를 거치다 보면, 시작 상태(Initial State)를 거쳐 종료 상태(Terminal state)에 도달하기 까지 다양한 과정들이 존재할 수 있을 것이다. 이런 다양한 Sequence들을 Episode(에피소드)라고 하며, 이런 Episode들을 뽑아내는 것을 Sampling이라고 한다.

Markov Reward Process (MRP)

Markov Reward Process는 Markov Chain에서 Reward의 개념을 추가한 것이다.

$$\text{ A Markov Reward Process is a tuple } \left\langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \right\rangle , \ \text{ } \ \begin{aligned} &\mathcal{S} \text{ is finite set of states.} \\ &\mathcal{P} \text{ is a state transition probability matrix.} \\ &\mathcal{R} \text{ is Reward Function.} \\ &\gamma \text{ is discount factor,} \gamma \in [0, 1] \end{aligned}$$
그리고 Reward Function은 다음과 같이 표현할 수 있다.
$$ \mathcal{R}_s = \mathbb{E}[R_{t+1} \mid S_t = s ] $$
보상의 시간이 t+1인 이유는, 보상을 에이전트(Agent)가 아닌 환경(Environment)가 주는 것이기 때문이다. (1장 참고.)

보통 시간 t+1에 받는 보상을 immediate reward, 그 이후 보상들을 future reward라고 하는데, future reward의 가치를 낮추는 데 사용하는 것이 discount factor(할인율) 이다.

$$ R_{t+1}, \gamma R_{t+2}, \gamma^2 R_{t+3}, ...$$

가치를 낮추는 이유는 여러 가지가 있다.

• 수학적으로 편리하다. (할인율에 의해 임의의 값에 수렴한다. 수렴하지 않으면 수치적으로 비교가 불가능하다.)
• 현재에 받는 보상과 나중에 받는 보상이 수치적으로 같다면 구분할 수 없다.
• etc.

보상을 추가함으로써, 어떤 상태가 가치가 있는지 계산할 수 있게 되었다. 강화학습에서 시간이 지날 때마다 보상이 쌓일 것이고, 그 쌓이는 보상(cumulative reward)들을 Return이라고 한다.

Return

Return은 시간 t의 진행에 따라 얻은 모든 감가상각된 보상(total discounted reward)의 합이다. 강화학습의 목적은 Return을 최대화하는 것이다.
$$ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... \ = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$$ 할인율이 0에 가깝다면, 에이전트는 근시안적인 사고를 할 것이고, 반대로 1에 가깝다면 장기적으로 생각하며 행동할 것이다.

가치 함수 (Value Function)

가치 함수는 현재 상태 s 에서부터 장기적으로 얻을 수 있는 보상의 기댓값(expectation)을 계산하는 함수이다. 더 자세한 설명은 아래서 다루도록 한다.
$$ v(s) = \mathbb{E}[G_{t} \mid S_t = s ] $$

가치 함수는 두 부분으로 분해할 수 있다.
$$\begin{cases}
\text{immediate reward : } \mathcal{R}_{t+1} \\ \text{다음 상태 } S_{t+1} \text{에 대한 discounted value : } \gamma v(S_{t+1})
\end{cases}$$

증명 (Bellman Equation)
$$ \begin{align}
&v(s) = \mathbb{E}[G_{t} \mid S_t = s ] \\ &= \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... \mid S_t = s ] \\ &= \mathbb{E}[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + ...) \mid S_t = s ] \\ &= \mathbb{E}[R_{t + 1} + \gamma G_{t+1} \mid S_t = s ] \\ &= \mathbb{E}[R_{t + 1} + \gamma v(S_{t+1}) \mid S_t = s ]
\end{align}$$

마르코프 결정 과정 (Markov Decision Process, MDP)

마르코프 결정 과정이란 Markov Reward Process에서 Decision의 개념을 추가한 것이다. 당연히 MDP는 모든 상태가 Markov한 환경을 가진다.

$$\text{ A Markov Decision Process is a tuple } \left\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \right\rangle , \ \text{ } \ \begin{aligned} &\mathcal{S} \text{ is finite set of states.} \\ &\mathcal{A} \text{ is finite set of actions.} \\ &\mathcal{P} \text{ is a state transition probability matrix.} \\ &\mathcal{R} \text{ is Reward Function.} \\ &\gamma \text{ is discount factor,} \gamma \in [0, 1] \end{aligned}$$

정책 (Policy)

정책이란 주어진 상태(State)에 대해 어떤 행동(Action)을 할지 나타내는 확률분포이다. MDP의 경우, 모든 상태가 Markov하므로 MDP에서의 정책은 현재 상태만을 고려한다. 또한, 정책은 에이전트의 모든 행동에 대해 (틀릴지라도) 정의가 되어있어야만 한다.

$$ \pi(a \mid s) = \mathbb{P}[A_{t} = a \mid S_{t} = s]$$

이제 정책을 포함하여 마르코프 과정들의 요소를 다시 정의할 수 있다.
$$ \mathcal{P}_{ss'}^\pi = \sum_{a \in \mathcal{A} } \pi(a \mid s) \mathcal{P}_{ss'}^a \\ \mathcal{R}_{s}^\pi = \sum_{a \in \mathcal{A} } \pi(a \mid s) \mathcal{R}_{s}^a $$

state-value Function과 action-value Function

state-value Function은

1. 정책 𝛑를 따르면서,
2. 상태 s에서 출발하면서
3. 얻을 수 있는 Return에 대한 기댓값(Expectation)이다.

$$ v_\pi(s)\ = \mathbb{E}_\pi[G_{t} \mid S_t = s ] $$

action-value Function은

1. 정책 𝛑를 따르면서,
2. 상태 s에서 출발하면서, 행동 a를 하면
3. 얻을 수 있는 Return에 대한 기댓값(Expectation)이다.

$$ q_\pi(s, a)\ = \mathbb{E}_\pi[G_{t} \mid S_t = s, A_t = a ] $$

action-value Function은 Q-Function (Q함수) 라고도 한다.

Bellman Expectation Equation

Bellman Expectation Equation이란 반복적으로 기댓값(Expectation)을 갱신해 나가기 위해 현재 가치 함수와 다음 가치 함수 사이를 (재귀적으로) 정의한 방정식이다.

state-value Function과 action-value Function은 다음과 같이 분해가 가능하다. $$ v_\pi(s) = \mathbb{E}_\pi[R_{t + 1} + \gamma v_\pi(S_{t+1}) \mid S_t = s ] \\ q_\pi(s, a) = \mathbb{E}_\pi[R_{t + 1} + \gamma q_\pi(S_{t+1}, A_{t+1}) \mid S_t = s, A_t = a ] $$

• state-value와 action-value를 사용하여 다음과 같이 나타낼 수 있다.

$$ v_\pi(s) = \sum_{a \in \mathcal{A} } \pi(a \mid s) q_\pi(s, a) $$

• 반대로 action-value는 state-value를 사용하여 다음과 같이 나타낼 수 있다.

$$ q_\pi(s, a) = \mathcal{R}_{s}^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_\pi(s') $$

위 수식들을 합쳐 가치 함수(Value Function)를 재귀적으로 표현할 수 있다.

1. State-value의 재귀적 표현

$$\begin{align}
v_\pi(s) &= \sum_{a \in \mathcal{A} } \pi(a \mid s) q_\pi(s, a) \\
&= \sum_{a \in \mathcal{A} } \pi(a \mid s) \left( \mathcal{R}_{s}^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_\pi(s') \right)
\end{align}$$

2. Action-value의 재귀적 표현

$$\begin{align}
q_\pi(s, a) &= \mathcal{R}_{s}^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_\pi(s') \\
&= \mathcal{R}_{s}^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a \left( \sum_{a' \in \mathcal{A} } \pi(a' \mid s') q_\pi(s', a') \right)
\end{align}$$

Optimal Value Function

모든 정책(Poicy)에 대하여 계산했을 때 최대의 값을 지니는 Value Function을 Optimal Value Function이라고 한다.
(일반적으로 Optimal을 정의할 때, *를 붙인다.)

• Optimal state-value Function
  $$ v_{*}(s) = \max_\pi v_\pi(s) $$
• Optimal action-value Function
  $$ q_{*}(s, a) = \max_\pi q_\pi(s, a) $$

그러나 현실적으로 현재의 가치 함수(Value Function)가 Optimal한지는 파악이 어렵다.
따라서, 일반적인 경우에는 가능한(Possible) 최고 성능을 내는 함수를 뜻한다.
Optimal Value Function을 구하는 것을 MDP를 푼다고 말한다.

Optimal Policy

모든 경우에서 정책(Policy)을 서로 비교할 수 있는 것은 아니지만(Partial-Ordering), 어떤 상황에서는 확실히 어떤 정책(Policy)이 낫다고 할 수 있다.
다음과 같은 조건을 만족할 때, 더 나은 정책(Policy)이라고 할 수 있다.
$$ \pi \ge \pi' \text{ if } v_{\pi}(s) \ge v_{\pi'}(s), \text{ } \forall s $$

또한, 모든 마르코프 결정 과정(Markov Decision Process)에 대하여 다음 정리(Theorem)가 성립한다.

• 다른 모든 정책들과 같거나 더 나은 Optimal Policy 𝛑* 가 존재한다.
  $$ \pi_* \ge \pi, \forall \pi $$
• 모든 Optimal Policy는 Optimal value function을 이룬다.
  $$ v_{\pi*}(s) = v_{ * }(s) $$
• 모든 Optimall Policy는 Optimal action-value function을 이룬다.
  $$ q_{\pi*}(s, a) = q_{ * }(s, a) $$

Optimal Policy는 Optimal action-value function이 있다면 반드시 하나를 찾아낼 수 있다.

증명
$$ \pi_* (a \mid s) = \begin{cases}
1, & \mbox{if }a = \underset{a \in \mathcal{A}}{\operatorname{argmax}} \text{ } q_* (s, a) \\
0, & \mbox{otherwise}
\end{cases} $$

• 정책(Policy)은 기본적으로 Stochastic 하다. 하지만 위 식을 따르면 Optimal action-value function을 가지고 있을 때는 Deterministic 하다고 볼 수 있다.
• 모든 MDP는 항상 Deterministic Optimal Policy를 가진다.

이 이야기는 가위바위보에도 적용이 가능하다.
A와 B가 가위바위보를 한다고 가정하자. A는 가위, 바위, 보를 균일한 확률로 낸다.
B는 그럼 가위(또는 바위, 보)를 계속 내는 Policy를 Optimal Policy로 가질 수 있다! (그 이상으로 승률을 올리기는 불가능하므로)
또는 A가 50% 확률로 가위를 낸다고 한다면 B의 Optimal Policy는 계속 주먹을 내는 것이 될 것이다.

Bellman Optimality Equation

기본적인 사항은 Bellman Expectation Equation을 설명한 것과 동일하다. 그러나 차이점이 있다면, Bellman Optimality Equation은 이름 그대로 항상 최적치만을 추구한다는 점이다.

수식에 max가 추가되어서 함수가 Non-linear하게 바뀌었다. 따라서 행렬 계산으로 Policy를 구하는 방법은 Optimal Policy를 구할 때 사용할 수 없다.

1. Optimal state-value Function
   

   

$$ v_{*}(s) = \max_a q_{ * }(s, a) $$

2. Optimal action-value Function

   

$$ q_{*}(s, a) = \mathcal{R}_{s}^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{*}(s') $$

3. Recursive Optimal state-value Function

$$ v_{*}(s) = \max_a \mathcal{R}_{s}^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a v_{*}(s') $$

4. Recursive Optimal action-value Function

$$ q_{*}(s, a) = \mathcal{R}_{s}^a + \gamma \sum_{s' \in \mathcal{S} } \mathcal{P}_{ss'}^a \max_{a'} q_{ * }(s', a') $$

Bellman Optimality Equation은 이야기했듯이 Non-linear하기 때문에 구하는 방법에 고정적인 형태가 존재하지 않는다.
대신 다음과 같은 반복적인(iterative) 해결책들이 존재한다.

• Value Iteration
• Policy Iteration
• Q-learning
• Sarsa