[RL] Markov Decision Process

Markov Decision Processes (MDP)

• MDP는 Fully observable한 환경에서, 강화학습을 위한 환경을 묘사한다.
• 즉, 현재 상태가 완전하게 과정을 특징한다.
• 대부분의 RL 문제들은 MDP로 정리할 수 있다.
  • Partially observable problem도 MDP로 변환될 수 있다.

Markov Property

• 현재 상태를 안다면 미래와 과거는 독립적이다
  • 상태는 역사로부터 모든 관련있는 정보들을 포집한다.
  • 상태가 알려져있다면, 역사는 갖다 버려도 된다.

Markov Process

• Markov process는 memoryless한 random process이다.

Definition: Markov Process
Markov Process (또는 Markov Chanin)은 순서쌍 $\mathcal{(S, P)}$이다.

• $\mathcal{S}$는 유한한 상태들의 집합이다.
• $\mathcal{P}$는 상태 전이 확률분포 행렬이다.
  $\mathcal{P}_{ss'} = \mathbb{P}[S_t=s' | S_t=s]$

State Transition Matrix

• 마르코프 상태 $S$와 후속 상태 $S'$에 대해, 상태 전이 확률은 다음과 같이 정의된다.
  $\mathcal{P}_{ss'} = \mathbb{P}[S_t=s' | S_t=s]$
• 상태 전이 행렬 $P$는 모든 전이 확률들을 포함한다.
  $\mathcal{P} = \text{from} \overset{\text{to}}{\begin{bmatrix} \mathcal{P}_{11} & \dots & \mathcal{P}_{1n} \\ \vdots & & \vdots \\ \mathcal{P}_{n1} & \dots & \mathcal{P}_{nn} \end{bmatrix}}$
• 각 열의 합은 1이다.

Markov Reward Process

Markov reward process는 values(rewards)를 포함하는 Markov chain이다.

Definition: Markov Reward Process
Markov Reward Process은 순서쌍 $\mathcal{(S, P, R, \gamma)}$이다.

• $\mathcal{S}$는 유한한 상태들의 집합이다.
• $\mathcal{P}$는 상태 전이 확률분포 행렬이다.
  $\mathcal{P}_{ss'} = \mathbb{P}[S_t=s' | S_t=s]$
• $\mathcal{R}$은 reward function으로, $\mathcal{R}_s = \mathbb{E}[R_{t+1} | S_t = s]$이다.
• $\gamma$는 discount factor로, $\gamma \in [0,1]$ 이다.

(Discounted) Return

Definition: Return
Return $G_t$는 time step $t$부터의 총 discounted reward를 의미한다.

$G_t = R_{t+1} + \gamma R_{t+2} + \dots = \sum ^{\infin}_{k=0}\gamma^k R_{t + k + 1}$

• $\gamma$는 현재의 보상을 지연된 보상보다 얼마나 중요시할지를 의미한다.
  • $\gamma$가 0에 가까울 수록 근시안적,
  • $\gamma$가 1에 가까울 수록 원시안적이다.

Discount factor를 사용하는 이유

• 순환하는 Markov process에서 무한한 return을 피하기 위해
• 미래에 대한 불확정성이 충분히 표현되지 않았을 수 있으므로
• 만약 보상이 금전적이라면 당장의 보상이 지연된 보상보다 더 중요하므로
• 인간과 동물은 당장의 보상을 더 선호하므로

Value Function

• value function $v(s)$는 $s$로부터의 long-term value를 계산한다.
• MRP의 state value function은 $s$로 부터 시작할 때 return의 기댓값이다.
  $v(s) = \mathbb{E}[G_t \mid S_t = s]$

Bellman Equation for MRPs

• Value function은 두 파트로 나뉘어질 수 있다.
  • 당장의 보상 $R_{t+1}$
  • 후속 상태의 할인된 보상 $\gamma V(S_{t+1})$
    $\begin{aligned} v(s) &= \mathbb{E}[G_t \mid S_t = s] \\ &= \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \mid S_t = s] \\ &= \mathbb{E}[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \dots) \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] \\ &= \mathcal{R}_s + \gamma\sum_{s'\in \mathcal{S}}\mathcal{P}_{ss'}v(s') \end{aligned}$

Bellman Equation in Matrix Form

• Bellman equation은 $V$가 각 상태별로 하나의 요소만 갖는 열벡터일때, 행렬들을 이용해서 더 간결하게 표현될 수 있다.
  $V = R + \gamma PV$

Solving the Bellman Equation

• 벨만 방적식은 선형방정식으로 직접적으로 풀 수 있다.

• 시간복잡도는 $N$ 개의 상태에 대해 $O(N^3)$이고,
• 이는 작은 MRP에 대해서만 가능하다.
• 큰 MRP에 대해서는 다음과 같은 iterative method 들이 있다.
  • Dynamic programming
  • Monte-Carlo evaluation
  • Temporal-Difference learning

Markov Decision Process

Markov decision process는 decision이 있는 Markov reward process이다.

Definition: Markov Decision Process
Markov Decision process은 순서쌍 $\mathcal{\lang S, A, P, R, \gamma\rang}$이다.

• $\mathcal{S}$는 유한한 상태들의 집합이다.
• $\mathcal{A}$는 유한한 행동들의 집합이다.
• $\mathcal{P}$는 상태 전이 확률 행렬이다.
  $\mathcal{P}_{ss'}^a = \mathbb{P}[S_t=s' | S_t=s, A_t = a]$
• $\mathcal{R}$은 reward function으로, $\mathcal{R}_s^a = \mathbb{E}[R_{t+1}^a | S_t = s, A_t = a]$이다.
• $\gamma$는 discount factor로, $\gamma \in [0,1]$ 이다.

Policies

Definition: Policy
Policy $\pi$는 주어진 상태에 대한 행동들의 분포이다.

$\pi(a|s) = \mathbb{P}[A_t = a | S_t = s]$

• 정책은 에이전트의 행동을 완전히 정의한다.
• MDP 정책은 현재 상태 (not history)에 의해 결정된다.
• 즉, 정책은 시간에 독립적이다. $A_t \sim \pi(\cdot | S_t), \forall t > 0$
• MDP = $\lang S, A, P, R, \gamma \rang$와 정책 $\pi$가 정해졌을 때,
• 상태 시퀀스 $S_1, S_2, \dots$는 Markov process $\lang S, P^\pi \rang$이다.
• 상태와 리워드 시퀀스 $S_1, R_2, S_2, \dots$는 Markov reward process $\lang S, P^\pi, R^\pi, \gamma \rang$이다.

Value Function

Definition: State-Value Function
state-value function $v_\pi(s)$는 $s$상태에서 $\pi$ 정책을 따를 때의 return의 기댓값이다.

$v_\pi(s) = \mathbb{E}_\pi [G_t | S_t = s]$

Definition: Action-Value Function
action-value function $q_\pi(s, a)$는 $s$상태에서 $a$ 행동을 취했고, $\pi$ 정책을 따를 때의 return의 기댓값이다.

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

Bellman Expectation Equation

• State-value function은 당장의 리워드와 후속상태의 할인된 리워드로 분해될 수 있다.
  $v_{\pi}(s) = \mathbb{E}_{\pi} [R_{t+1} + \gamma v_{\pi}(S_{t+1}) \mid S_t = s]$
• Action-value function도 비슷하게 분해될 수 있다.
  $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]$

Bellman Expectation Equation for $V^\pi$

(3) 참고

Bellman Expectation Equation for $Q^\pi$

Bellman Expectation Equation in Matrix Form

(1) 참고

Optimal Value Function

Optimal value function은 MDP에서 가능한 가장 좋은 성능을 말해주므로, 우리가 Optimal value function을 안다면 MDP가 해결되었다고 할 수 있음.

Definition Optimal value function
optimal state-value function $v_*(s)$은 모든 정책 중 가장 큰 maximum state-value function을 의미함

$v_*(s) = \max _\pi v_\pi (s)$

optimal action-value function $q_*(s,a)$는 가장 큰 action-value function을 의미함

$q_*(s,a) = \max_\pi q_\pi(s,a)$

Optimal policy

$\pi$가 모든 state에 대해 return의 기댓값이 $\pi'$보다 크거나 같다면, $\pi$가 $\pi'$보다 좋거나 같다.

Theorem
임의의 Markov Decision Process에 대해

• optimal policy $\pi_*$가 존재한다면, 존재하는 모든 다른 $\pi$에 대해 $\pi_* \ge \pi,\; \forall \pi$이다.
• 모든 optimal policy는 optimal value function을 달성한다. $v_{\pi_*}(s) = v_*(s)$
• 모든 optimal policy는 optimal action-value function을 달성한다. $q_{\pi_*}(s,a) = q_*(s,a)$

Finding an Optimal Policy

• Optimal policy는 $q_*(s,a)$ 를 최대화하는 방향으로 찾을 수 있다.

• 어떤 MDP던 결정론적 optimal policy가 존재한다.
• 만약 우리가 $q_*(s,a)$를 안다면 즉시 optimal policy를 알 수 있다.

Bellman Optimality Equation for $v_*$

(7) 참고

Bellman Optimality Equation for $q_*$