Reinforcement Learning - #1. Markov Decision Process (MDP, 마르코프 결정 과정), Bellman Optimality Equation (벨만 최적 방정식)

본 문서는 2022년 서울대학교 수리과학부에서 Ernest K. Ryu 교수님께서 진행하신 Reinforcement Learning 강의 내용을 정리한 것입니다.

1. Markov Decision Process (MDP)

강화학습(RL)은 마르코프 결정 과정(MDP) 내에서 순차적 의사결정을 고려함.

1-1. Definition

• 시간: $t = 0,1, \cdots , T$

• 상태 전이:
  $s_t \xrightarrow{\pi} a_t \xrightarrow{p} (r_t, s_{t+1})$

• 경로 (Trajectory):
  $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \dots, s_{T-1}, a_{T-1}, r_{T-1}, s_T)$

• 상태: $s_t \in \mathcal{S}$

• 행동: $a_t \in \mathcal{A}$

  • 일반적으로 가능한 행동의 집합은 $s_t$에 따라 달라질 수 있음: $a_t \in \mathcal{A}(s_t)$

• 보상: $r_t \in \mathbb{R}$

  • 정책을 선택하여 보상의 합을 최대화하는 것이 목표

• 종결 시간: $T$는 terminal time 혹은 stopping time

  • $s_T$가 종결 상태이면 $T$가 종료됨.
  • $T = \infty$도 가능하며, 만약 종결 상태가 $\mathcal{S}$에 포함되지 않으면 $T = \infty$가 반드시 성립.

• 초기 상태 분포: $s_0 \sim p_0$ (일반적으로 고정됨)

• 상태 전이 확률: 환경이 제공하는 확률 분포 $p(r, s' | s, a)$
  $(r_t, s_{t+1}) \sim p(\cdot, \cdot | s_t, a_t)$

• 정리

  • 상태 $s_t \in \mathcal{S}$
  • 행동 $a_t \in \mathcal{A}$
  • 보상 $r_t \in \mathbb{R}$
  • 종결 시간 $T$ (종료 상태가 존재하지 않으면 $T = \infty$)
  • 초기 상태 분포 $s_0 \sim p_0$
  • 상태 전이 확률 $p(r, s' | s, a)$ (일반적으로 정확히 알려지지 않음)

1-2. 특성

• $r_t$ 는 경우에 따라 $(s_t, a_t)$ 의 완전히 결정적인 함수일 수 있음.

• $s_{t+1}$ 역시 경우에 따라 $(s_t, a_t)$ 의 완전히 결정적인 함수일 수 있음.

• stationary 동역학을 가정:

  $(r_t, s_{t+1}) \sim p_t(\cdot, \cdot | s, a)$

  stationary 가정하에:

  $p_t(r, s' | s, a) = p(r, s' | s, a)$

  (즉, 시간에 따라 전이확률 p가 변하지 않는다.)

• 행동 $a_t$ 는 정책 $\pi$ 에 의해 선택됨 (주어진 상태 $s_t$ 에서).

  • 확률적 정책 ($\pi$ 가 stochastic인 경우):
    $\pi(a | s)$
    는 확률 분포이며, $a_t \sim \pi(\cdot | s_t)$ 를 따름.
  • 결정적 정책 ($\pi$ 가 deterministic인 경우):
    $a_t = \pi(s_t)$

    • 일반적으로 정책 $\pi$ 는 신경망으로 파라미터화됨:
      $\pi = \pi_{\theta}$
      $\theta$: 신경망의 학습 가능한 파라미터

• 현재는 에이전트가 상태 $S_t$ 를 완전히 관찰한다고 가정하지만, 일반적으로 부분 관찰 환경(partial observation) 에서는 다음과 같이 정의 가능:

  $o_t = \phi(s_t)$

  여기서 $\phi$ 는 상태 $s_t$ 를 변환하는 함수.

• cf.

  • 정책(Policy)은 비정지(non-stationary)일 수도 있음.
  • TODO: 종결 상태(Terminal State)에서의 정책 정의 필요.

2. 강화학습의 목표

강화학습의 목표는 기대 할인 반환(Expected Discounted Return)을 극대화하는 것입니다.

• 누적 할인 보상(Cumulative Discounted Return):

  $\sum_{t=0}^{T-1} \gamma^t r_t = r_0 + \gamma r_1 + \cdots + \gamma^{T-1} r_{T-1} = G_0.$

• 정의:

  • $G_0$: 누적 반환(Cumulative Return).
  • $r_t$: 순간 보상(Instantaneous Reward).
  • 할인 계수(Discount Factor): $\gamma \in (0,1]$.
  • $T = \infty$인 경우, 반환이 유한하게 유지되려면 $\gamma < 1$이어야 함.
  • $\mathbb{E}^{\pi}$: 정책 $\pi$ 하에서의 기대값.
    • $a_t \sim \pi(\cdot | s_t)$
    • $(r_t, s_{t+1}) \sim p(\cdot, \cdot | s_t, a_t)$

• 시간 $t$부터의 반환(Return from time $t$):

  $G_t = r_t + \gamma r_{t+1} + \cdots + \gamma^{T-1-t} r_{T-1} = \sum_{t' = t}^{T-1} \gamma^{t'-t} r_{t'}.$

3. 상태 가치 함수 $V^{\pi}$ 및 상태-행동 가치 함수 $Q^{\pi}$

3-1. 상태 가치 함수 (State Value Function)

상태 가치 함수 $V^{\pi}(s)$는 정책 $\pi$를 따를 때 상태 $s$에서 시작하여 기대되는 반환(Expected Return)을 의미합니다.

즉, 주어진 상태 $s$에서 정책 $\pi$를 따른 경우 기대되는 보상의 총합입니다.

3-2. 상태-행동 가치 함수 (State-Action Value Function)

상태-행동 가치 함수 $Q^{\pi}(s, a)$는 정책 $\pi$를 따를 때 상태 $s$에서 행동 $a$를 수행한 이후 기대되는 반환을 의미합니다.

즉, 상태 $s$에서 특정 행동 $a$를 선택했을 때, 그 이후 정책 $\pi$를 따랐을 경우 기대되는 보상의 총합입니다.

3-3. 가치 함수의 기본 성질

정책 $\pi$ 하에서 상태 가치 함수는 상태-행동 가치 함수의 기대값으로 표현될 수 있습니다:

이는 상태 가치 함수가 정책 $\pi$에 따라 행동을 선택하는 확률적 기대값으로 나타낼 수 있음을 의미합니다.

또한, 정지성(stationarity)을 가정하면 다음이 성립합니다:

정지성(stationarity)은 상태 가치 함수가 특정 시간 $t$에서 동일한 기대값을 가지는 것이 아니라, 환경의 확률적 동역학이 시간에 따라 변하지 않음을 의미합니다.
즉, 특정 시간 $t$에서의 기대 반환도 동일한 관계를 따르지만, $V(s_0)$와 $V(s_t)$가 같다는 의미는 아닙니다.

4. 1-스텝 전이 속성 (1-step Transition Property)

4-1. 상태 가치 함수의 1-스텝 관계

마르코프 성질에 의해 상태 가치 함수는 다음과 같은 재귀 관계를 가집니다:

이를 전개하면:

이를 상태-행동 관계로 확장하면:

이를 정리하면:

4-2. 상태-행동 가치 함수의 1-스텝 관계

이를 마르코프 성질을 적용하여 전개하면:

이를 상태 전이 확률과 행동 선택 확률을 적용하여 풀어 쓰면:

즉, 상태-행동 가치 함수는 보상과 할인된 다음 상태의 기대값으로 표현될 수 있으며, 이는 가치 반복(Value Iteration) 및 Q-러닝(Q-Learning)의 핵심 개념이 됩니다.

4-3. 요약

1. $V^{\pi}(s)$: 특정 상태 $s$에서 시작하여 정책 $\pi$를 따를 때 기대되는 반환.
2. $Q^{\pi}(s, a)$: 상태 $s$에서 행동 $a$를 선택하고 이후 정책 $\pi$를 따를 때 기대되는 반환.
3. 벨만 방정식(Bellman Equation):
   • $V^{\pi}(s)$는 상태 전이 확률과 행동 선택 정책을 반영한 기대값으로 표현 가능.
   • $Q^{\pi}(s, a)$는 보상과 다음 상태-행동 쌍의 가치 함수의 기대값으로 재귀적으로 표현 가능.

이러한 관계들은 정책 평가(Policy Evaluation), 정책 개선(Policy Improvement), 그리고 최적 정책 학습(Optimal Policy Learning)에 핵심적으로 사용됩니다.

---

5. 바나흐 고정점 정리 (Banach Fixed Point Theorem)

바나흐 고정점 정리는 수축 사상(contraction mapping)에 대해 유일한 고정점이 존재함을 보장하는 정리입니다.

정리:

• $\mathcal{X}$가 거리 공간(metric space)이고 거리 함수 $d$를 가진다고 가정합니다.

• 함수 $\mathcal{T}: \mathcal{X} \to \mathcal{X}$가 $\gamma$-수축(contraction mapping)이라면:

  $d(\mathcal{T}(x), \mathcal{T}(y)) \leq \gamma d(x,y), \quad \forall x,y \in \mathcal{X}, \, 0 \leq \gamma < 1$
  • 이때, $\mathcal{T}$는 고정점을 가지며, 고정점은 유일함.
  • 초기값 $x_0 \in \mathcal{X}$에 대해 $k \to \infty$로 보낼 때, $\mathcal{T}^k(x_0)$는 유일한 고정점 $x^*$로 수렴함:
  $\mathcal{T}^k(x) \to x^*$
  • 여기서 $x^*$는 $\mathcal{T}(x^*) = x^*$를 만족하는 유일한 고정점.

6. 벨만 방정식과 바나흐 정리

6-1. 벨만 방정식 (Bellman Equation) for $V^{\pi}$

6-1-1. 벨만 방정식의 정의

벨만 방정식(Bellman Equation)은 동적 계획법에서 핵심이 되는 방정식으로, 현재 상태에서의 최적 정책이 다음 상태에서도 유지됨을 보장하는 재귀적 관계식입니다. 이는 가치 함수(value function)를 표현하는 방식으로 사용됩니다.

정책 $\pi$가 주어졌을 때, 상태 가치 함수 $V^{\pi}(s)$는 다음과 같은 관계를 만족합니다:

즉, 상태 $s$에서 정책 $\pi$에 따라 행동을 선택했을 때, 현재 받을 보상과 다음 상태에서 받을 보상의 할인된 합이 기대값으로 나타납니다.

6-2. 벨만 연산자(Bellman Operator)와의 관계

벨만 연산자 $\mathcal{B}^{\pi}$는 벨만 방정식을 보다 쉽게 표현하기 위해 정의된 연산자(operator)입니다. 이는 가치 함수 공간에서 가치 함수 공간으로 매핑하는 연산자로 볼 수 있습니다.

이 연산자는 가치 함수 $V$를 사용하여 다음 상태에서의 기대 가치를 업데이트하는 역할을 합니다.

벨만 방정식은 $V^{\pi}$가 벨만 연산자의 고정점(fixed point)이 됨을 의미합니다:

즉, $V^{\pi}$는 벨만 연산자를 적용해도 변하지 않는 상태로 수렴합니다.

6-3. 벨만 연산자의 수축성 (Banach Fixed Point Theorem 적용)

벨만 연산자가 수축 사상(contraction mapping)임을 보이려면, 두 가치 함수 $V_1$과 $V_2$에 대해 다음이 성립해야 합니다:

즉, 벨만 연산자는 항상 입력 간의 거리를 $\gamma$배 축소시키므로 바나흐 고정점 정리에 의해 $V^{\pi}$는 유일한 해로 수렴하게 됩니다.

6-4. 벨만 방정식 (Bellman Equation) for $Q^{\pi}$

상태-행동 가치 함수(state-action value function) $Q^{\pi}$는 다음을 만족합니다:

이는 특정 상태 $s$에서 특정 행동 $a$를 수행한 후, 정책 $\pi$를 계속 따랐을 때의 기대 반환을 의미합니다.

이를 벨만 연산자로 나타내면:

이제, $Q^{\pi}$ 역시 벨만 연산자의 고정점으로 수렴하게 됩니다:

6-5. 요약

1. 벨만 방정식은 가치 함수가 현재 보상과 다음 상태에서의 기대 가치의 합으로 표현되는 재귀적 관계식입니다.
2. 벨만 연산자는 가치 함수를 업데이트하는 연산자로, 벨만 방정식을 더욱 간결하게 표현할 수 있도록 도와줍니다.
3. 벨만 연산자는 $\gamma$-수축 사상이며, 바나흐 고정점 정리에 의해 $V^{\pi}$와 $Q^{\pi}$가 유일한 값으로 수렴함이 보장됩니다.

이러한 개념들은 강화학습 알고리즘에서 정책 평가(Policy Evaluation), 정책 개선(Policy Improvement), 그리고 최적 정책 학습(Optimal Policy Learning)의 이론적 근거가 됩니다.

7. 최적 정책과 최적 가치 함수 (Optimal Policy and Value Functions)

7-1. 최적 정책 (Optimal Policy)

최적 정책 $\pi^*$는 모든 정책 $\pi$에 대해 가치 함수가 최대가 되는 정책입니다:

즉, 최적 정책 $\pi^*$를 따르면 어떤 상태에서도 최대 기대 보상을 받을 수 있습니다.

• 최적 상태 가치 함수:
  $V^* = V^{\pi^*}$
• 최적 상태-행동 가치 함수:
  $Q^* = Q^{\pi^*}$

최적 정책 $\pi^*$는 유일하지 않을 수 있지만, 최적 가치 함수 $V^*$와 $Q^*$는 유일합니다.

7-2. 벨만 최적 방정식 (Bellman Optimality Equation for $V^*$)

7-2-1. 정의

최적 상태 가치 함수 $V^*$는 다음의 벨만 최적 방정식을 만족합니다:

즉, 상태 $s$에서 가능한 모든 행동 중 최적의 행동을 선택했을 때 얻을 수 있는 최대 기대 반환입니다.

• 최적 정책 $\pi^*$는 다음과 같이 결정됨:
  $\pi^*(s) = \arg\max_{a \in \mathcal{A}} \mathbb{E}_{(r,s') \sim p(\cdot | s,a)} \left[ r + \gamma V^*(s') \right]$
  이는 최적 상태-행동 가치 함수와도 연결됩니다:
  $\pi^*(s) = \arg\max_{a \in \mathcal{A}} Q^*(s,a)$

7-3. 벨만 최적 연산자와 수렴성 (Bellman Optimality Operator)

벨만 최적 연산자 $\mathcal{B}^*$를 정의하면 다음과 같습니다:

이는 상태 가치 함수의 최적 업데이트 규칙을 나타냅니다.

• $\mathcal{B}^*$가 $\gamma$-수축 사상임을 보일 수 있음:
  $\| \mathcal{B}^* V_1 - \mathcal{B}^* V_2 \|_{\infty} \leq \gamma \| V_1 - V_2 \|_{\infty}$
  따라서 바나흐 고정점 정리에 의해 $V^*$는 유일한 해로 수렴합니다.

7-4. 벨만 최적 방정식 (Bellman Optimality Equation for $Q^*$)

최적 상태-행동 가치 함수 $Q^*$는 다음의 벨만 최적 방정식을 만족합니다:

이는 최적 행동을 선택했을 때 기대할 수 있는 최대 보상을 나타냅니다.

최적 정책은 $Q^*$를 기반으로 결정됩니다:

이를 벨만 최적 연산자로 표현하면:

이는 가치 반복(Value Iteration) 알고리즘의 핵심 원리입니다.

7-5. 벨만 최적 방정식의 적용 조건

최적 가치 함수와 정책이 존재하고 유일한 해로 수렴하려면 다음 조건들이 필요합니다:

1. 할인율 조건: $\gamma \in (0,1)$이어야 함. 만약 $\gamma = 1$이면 보상이 무한대로 발산할 가능성이 있음.
2. 유한한 상태와 행동 공간: $|\mathcal{S}| < \infty$ 또는 $|\mathcal{A}| < \infty$일 경우 유한한 해가 보장됨.
3. 보상 조건: 보상 함수 $r$이 유한한 상한 $R$을 가질 경우 수렴 보장이 가능함.
4. 확률적 정책 및 환경 모델: 상태-전이 확률 $p(s' | s,a)$가 주어져야 하고, 상태가 충분히 방문 가능해야 함.

7-6. 요약

1. 최적 정책 $\pi^*$는 모든 정책 중에서 최적의 기대 보상을 제공하는 정책임.
2. 최적 가치 함수 $V^*$는 벨만 최적 방정식을 만족하는 유일한 해임.
3. 최적 상태-행동 가치 함수 $Q^*$ 역시 벨만 최적 방정식을 만족함.
4. 벨만 최적 연산자는 $\gamma$-수축 사상이며, 바나흐 고정점 정리에 의해 $V^*$와 $Q^*$는 유일한 값으로 수렴함.
5. 최적 정책과 가치 함수의 수렴성을 보장하기 위해서는 $\gamma$, 상태/행동 공간, 보상 구조 등의 특정 조건이 충족되어야 함.

이러한 개념들은 정책 반복(Policy Iteration), 가치 반복(Value Iteration), 그리고 Q-러닝(Q-Learning)과 같은 강화학습 알고리즘의 핵심 원리가 됩니다.