Finite Markov Decision Process, MDP

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

유한 마르코프 결정 과정 (MDP)는 강화 학습에서 사용하는 수학적 프레임워크로, 부분적으로는 확률적이고 부분적으로는 에이전트의 결정에 따라 제어되는 환경을 설명하는데 사용된다. 유한 MDP의 구성 요소는 다음과 같다.

구성 요소

The agent- environment interaction in reinforcement learning.

구성 요소

1. 상태 (States, (S)): 에이전트가 존재할 수 있는 유한한 상태 집합. 에이전트는 어느 시점에 하나의 상태에 있고, 이 상태는 환경에 대한 정보를 제공한다.
2. 행동 (Actions, (A)): 에이전트가 취할 수 있는 유한한 행동의 집합. 에이전트는 현재 상태에 기반해 행동을 선택한다.
3. 전이 확률 (Transition Probability, (P)): 특정 행동을 취할 때 한 상태에서 다른 상태로 전이될 확률을 정의한다. 이는 환경의 동적 변화를 나타낸다.
   $$
   P(s', r \mid s, a) = \mathbb{P}(S_{t+1} = s', R_{t+1} = r \mid S_t = s, A_t = a)
   $$
4. 보상 (Rewards, (R)): 에이전트가 행동을 취하여 상태가 전이된 후 받는 보상. 이는 에이전트가 시간이 지남에 따라 최대화하려는 수치다.
5. 정책 (Policy, ($\pi$)): 정책은 에이전트가 상태에서 행동을 선택하는 방식을 나타낸다. 이는 상태가 주어졌을 때 행동을 선택할 확률 분포로 정의될 수 있다.
   $$
   \pi(a \mid s) = \mathbb{P}(A_t = a \mid S_t = s)
   $$
6. 가치 함수 (Value Function): 가치 함수는 주어진 상태에서 시작하여 기대할 수 있는 미래의 보상을 추정한다. 상태가 얼마나 좋은지를 나타낸다.
   • 상태 가치 함수 ($(V^\pi(s))$): 상태 (s)에서 시작하여 정책 ($\pi$)를 따를 때 기대되는 보상.
     $$
     V^\pi(s) = \mathbb{E}^\pi \left[ \sum_{t=0}^\infty \gamma^t R_{t+1} \mid S_0 = s \right]
     $$
   • 행동 가치 함수 ($(Q^\pi(s, a))$): 상태 (s)에서 행동 (a)를 취하고 그 이후에 정책 ($\pi$)를 따를 때 기대되는 보상.
     $$
     Q^\pi(s, a) = \mathbb{E}^\pi \left[ \sum_{t=0}^\infty \gamma^t R_{t+1} \mid S_0 = s, A_0 = a \right]
     $$

---

목표 (Goal ( G ))의 두 가지 유형: 에피소드와 지속적 과제

강화 학습에서 에이전트의 목표 (Goal)는 보상의 총합을 최대화하는 것이다. 목표는 두 가지로 나뉠 수 있다: 에피소드 과제 (Episodic Tasks)와 지속적 과제 (Continuing Tasks).

1. 에피소드 과제 (Episodic Tasks)

에피소드 과제는 명확한 종료 시점이 존재하는 과제이다. 이 과제에서는 에이전트가 일정한 시작 상태에서 시작하여 목표에 도달하거나 종료 조건을 만족할 때까지 진행된다. 에피소드가 종료되면 새로운 에피소드가 시작되고, 매 에피소드마다 반환이 계산된다.

• 종료 조건: 목표 도달, 실패, 제한된 시간/횟수 등이 종료 조건이 될 수 있다.
• 반환 ( $G_t$ ): 에피소드 과제에서 반환은 에피소드 종료 시점까지의 보상을 합산한 값이다.여기서 ( T )는 에피소드가 종료되는 시간이다. 에피소드 과제에서는 반환의 합이 유한하며, 각 에피소드의 끝에서 합산이 종료된다.
  $$
  G_t = \sum_{k=0}^T R_{t+k+1}
  $$

예시

• 체스: 게임이 끝나는 시점에서 승리 또는 패배로 에피소드가 종료된다.
• 미로 탈출: 목표 위치에 도달할 때 에피소드가 끝난다.

2. 지속적 과제 (Continuing Tasks)

지속적 과제는 명확한 종료 시점 없이 무한히 이어지는 과제이다. 이러한 과제에서는 에이전트가 무한한 시간 동안 계속 행동하며, 보상이 누적된다. 따라서 반환의 합은 무한할 수 있기 때문에, 할인율 ( $\gamma$ )가 매우 중요해진다.

• 종료 조건: 지속적 과제에서는 명확한 종료 조건이 없으며, 에이전트는 계속해서 학습한다.
• 반환 ( $G_t$ ): 반환은 에피소드와 달리, 무한히 지속되는 과제에서 할인된 미래 보상의 합으로 정의된다.이 경우, 할인율 ( $\gamma$ )는 미래의 보상을 현재보다 덜 중요하게 취급하며, ( $\gamma$ )가 1에 가까워질수록 먼 미래의 보상도 중요하게 고려된다.
  $$
  G_t = \sum_{k=0}^\infty \gamma^k R_{t+k+1}
  $$
  $$
  G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \dots
  $$
  $$
  = R_{t+1} + \gamma \left( R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \dots \right)
  $$
  $$
  = R_{t+1} + \gamma G_{t+1}
  $$

예시

• 공장 제어 시스템: 공장은 중단 없이 계속 운영되며, 각 시간 단위에서의 수익이 누적된다.
• 로봇 제어: 로봇은 정해진 종료 시점 없이 계속해서 환경과 상호작용하며 임무를 수행한다.

---

벨만 방정식 (Bellman Equations)

상태-가치 함수 ( $V_\pi(s)$ )

상태-가치 함수는 주어진 상태 ( s )에서 시작해 정책 ( $\pi$ )를 따를 때 기대되는 반환을 나타낸다.

$$
V_\pi(s) = \mathbb{E}_\pi \left[ \sum_{t=0}^\infty \gamma^t R_{t+1} \mid S_0 = s \right]
$$

이 식은 벨만 기대 방정식 (Bellman Expectation Equation)으로 재귀적으로 표현될 수 있다.

$$
\begin{aligned}
V_\pi(s)
&= \mathbb{E}_\pi \left[ G_t \mid S_t = s \right] \\
&= \mathbb{E}_\pi \left[ R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s \right] \\
&= \sum_{a} \pi(a \mid s) \sum_{s',r} P(s',r \mid s,a) \left[ r + \gamma V_\pi(s') \right].
\end{aligned}
$$

행동-가치 함수 ( $Q_\pi(s, a)$ )

행동-가치 함수는 상태 ( s )에서 특정 행동 ( a )를 취하고 그 이후 정책 ( \pi )를 따를 때 기대되는 반환을 나타낸다.

$$
Q_\pi(s, a) = \mathbb{E}_\pi \left[ \sum_{t=0}^\infty \gamma^t R_{t+1} \mid S_0 = s, A_0 = a \right]
$$

이는 벨만 기대 방정식으로 나타낼 수 있다.
$$
V_\pi(s) = \sum_{a} \pi(a \mid s) Q_\pi(s,a)
$$

$$
\begin{aligned}
Q_\pi(s,a)
&= \mathbb{E}\left[ R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s, A_t = a \right] \\
&= \sum_{s',r} P(s',r \mid s,a) \left[ r + \gamma V_\pi(s') \right] \\
&= \sum_{s',r} P(s',r \mid s,a) \left[ r + \gamma \sum_{a'} \pi(a' \mid s') Q_\pi(s',a') \right]
\end{aligned}
$$

---

MDP의 최적성

최적 정책 ( $\pi^*$ )는 주어진 상태에서 기대 반환을 최대화하는 정책이다. 최적 가치 함수는 다음과 같이 정의된다.

• 최적 상태-가치 함수 ( $V^*(s)$ ): 정책 ( \pi ) 하에서 상태 ( s )에서 달성할 수 있는 최대 기대 반환.
  $$
  V^*(s) = \max_\pi V_\pi(s)
  $$
• 최적 행동-가치 함수 ( $Q^*(s, a)$ ): 상태 ( s )에서 행동 ( a )를 취하고 이후 최적 정책을 따를 때 달성할 수 있는 최대 기대 반환.
  $$
  Q^*(s, a) = \max_\pi Q_\pi(s, a)
  $$

벨만 최적 방정식 (Bellman Optimality Equation)

벨만 최적 방정식은 최적 가치 함수에 대한 재귀적 관계를 정의한다.

• 최적 상태-가치 벨만 방정식:
  $$
  V^*(s) = \max_{a} \sum_{s', r} P(s', r \mid s, a) [r + \gamma V^*(s')]
  $$
• 최적 행동-가치 벨만 방정식:
  $$
  Q^*(s, a) = \sum_{s', r} P(s', r \mid s, a) [r + \gamma \max_{a'} Q^*(s', a')]
  $$

---

주요 개념

• 마르코프 속성 (Markov Property): 미래 상태는 현재 상태와 행동에만 의존하며, 과거 상태에는 의존하지 않는다.
  $$
  P(S_{t+1} = s' \mid S_t = s, A_t = a) = P(S_{t+1} = s' \mid S_0, A_0, ..., S_t = s, A_t = a)
  $$
• 할인율 (($\gamma$)): 미래 보상의 중요도를 결정하는 매개변수로, 0에 가까울수록 즉각적인 보상에 더 중점을 두고, 1에 가까울수록 미래의 보상도 중요하게 여긴다.

출처: Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). The MIT Press.