MDP(Markov Decision Process)

열수철·2025년 2월 18일

MDP는 Markov Decision Process의 약자로, 불확실한 환경에서 순차적으로 의사결정을 내리기 위한 수학적 모델입니다. 강화학습(Reinforcement Learning, RL)의 기본 기법으로 사용되며, 전이 확률과 보상 함수를 알고 있다면 MDP(확률적 제어 기법)를, 그렇지 않고 시뮬레이션 결과(보상 값)를 활용할 때는 강화학습을 적용하게 됩니다.

MDP의 구성요소

MDP는 다섯 가지 기본 구성요소로 정의됩니다:

S: 상태 집합 (State Space)
시스템 또는 환경의 현재 상황을 나타냅니다.
- 예: 테트리스에서 게임판의 블록 배치, 현재 떨어지고 있는 블록의 모양 등
- 표기:
  - 이산적인 경우: S = {1, 2, …, n}
  - 연속적인 경우: S = ℝⁿ
A: 행동 집합 (Action Space)
에이전트가 선택할 수 있는 모든 행동을 의미합니다.
- 예: 테트리스에서 블록의 회전, 좌우 이동 등
- 표기:
  - 이산적인 경우: A = {1, 2, …, n}
  - 연속적인 경우: A = ℝⁿ
P: 전이 확률 (Transition Probability)
현재 상태 s에서 행동 a를 취했을 때, 다음 상태 s'로 전이될 확률입니다.
- 수식:
```
P(s' | s, a) := Prob(sₜ₊₁ = s' | sₜ = s, aₜ = a)
```
- 특징: 결정론적인 경우, 특정 s'에 대해 1의 값을 갖고 나머지는 0입니다.
R: 보상 함수 (Reward Function)
상태 s에서 행동 a를 수행했을 때 즉각적으로 받는 보상입니다.
- 수식:
```
rₜ = r(sₜ, aₜ)
```
- 의미: 현재 단계에서 에이전트의 수행 정도를 평가하지만, 장기적인 효과는 누적 보상으로 판단합니다.
γ: 할인율 (Discount Factor)
미래 보상의 현재 가치를 평가하기 위한 계수로, 보통 0과 1 사이의 값을 사용합니다.
- 설명:
  - γ 값이 1에 가까우면 미래 보상을 현재 보상과 거의 동일하게 취급합니다.
  - γ 값이 0에 가까우면 미래 보상의 가중치를 크게 감소시킵니다.
- 예시:
  - 즉각적인 보상이 10일 때, γ = 0.9이면
    - 1단계 후 보상의 현재 가치는 10 × 0.9 = 9
    - 2단계 후 보상은 10 × 0.9² ≈ 8.1로 평가됩니다.

추가 용어: Decision Rule과 Policy

Decision Rule (의사결정 규칙):
각 상태에서 어떤 행동을 선택할지 결정하는 규칙입니다.
- Markov Decision Rule: 현재 상태에만 의존하는 규칙
- History Dependent Rule: 지금까지의 방문 기록 전체에 의존하는 규칙
구현 방식:
- Deterministic: 한 상태에 대해 단 하나의 행동을 결정
  - 예: πₜ(s) = a
- Stochastic (Randomized): 한 상태에 대해 행동 확률 분포를 할당
  - 예: πₜ(a | s) = Prob(aₜ = a | sₜ = s)
- 일반적으로: 단순성과 효율성을 위해 Deterministic Markov decision rule이 선호되며, 그 다음으로 Randomized Markov rule이 고려됩니다.
Policy (정책):
모든 상태에 대한 의사결정 규칙의 집합으로, 에이전트의 전체 전략을 나타냅니다.
- 예:
  - Deterministic: π(sₜ) = aₜ
  - Stochastic: π(a | s) = Prob(aₜ = a | sₜ = s)
- Stationary Policy: 시간에 따라 변화하지 않는 정책 (일반적으로 최적 정책은 stationary policy를 사용합니다).

Value Function과 MDP의 목표

Value Function vₚ(s):
현재 상태 s에서 시작해 앞으로 받을 누적 보상의 기대값을 의미합니다.
- 수식:
```
vₚ(s) := Eₚ [ Σₜ₌₀∞ γᵗ · r(sₜ, aₜ) | s₀ = s ]
```
MDP의 목표:
모든 상태에서 누적 보상을 최대화하는 최적의 정책 π*를 찾는 것입니다.
- 최적화 문제:
```
maxₚ Eₚ [ Σₜ₌₀∞ γᵗ · r(sₜ, aₜ) ]
```

에이전트는 행동 선택에 따라 미래 상태가 달라짐을 고려해 장기적인 이득을 최대화해야 합니다.

MDP와 강화학습의 관계

알고리즘을 알고 있을 때:
전이 확률 P와 보상 함수 R을 알고 있다면, MDP를 기반으로 동적 프로그래밍(Dynamic Programming) 등의 확률적 제어 기법을 직접 적용할 수 있습니다.
알고리즘을 모를 때:
시뮬레이션 결과, 즉 보상 값들만을 활용해 최적의 정책을 찾으려면 Q-Learning, SARSA, DQN과 같은 강화학습 알고리즘을 사용합니다.

MDP는 결국 함수 최적화 문제로 볼 수 있는데, 직접적인 gradient descent나 일반 최적화 기법을 적용하기 어려워 Dynamic Programming (DP)를 활용해 Bellman Equation 기반으로 문제를 분할하여 해결합니다.

모델 기반 (Model-based):: 전이 확률과 보상 함수가 주어지면 DP를 통해 최적의 해를 구함
모델 프리 (Model-free):: 전이 확률과 보상 함수를 모르는 경우, 시뮬레이션과 경험을 통해 가치 함수를 학습하여 최적 정책을 찾음

MDP 이해를 위한 간단한 다이어그램

다음은 MDP의 기본 흐름을 나타낸 다이어그램입니다:

       +-------------+
       |  State s  |<------------------+
       +-------------+                   |
             | a                        | P(s' | s, a)
             v                          |
       +-------------+       r          |
       |  Action a  |  ----------->  +-------------+
       +-------------+                |  State s'  |
                                      +-------------+
                                             |
                                             | r, s' →
                                             v
                                      (반복)