IT Professional Engineering/AI.ML

MDP(Markov Decision Process): 불확실성 환경에서의 의사결정 모델링 프레임워크

GilliLab IT 2025. 4. 11. 01:16
728x90
반응형

MDP(Markov Decision Process): 불확실성 환경에서의 의사결정 모델링 프레임워크

MDP의 기본 개념

Markov Decision Process(MDP)는 순차적 의사결정 문제를 모델링하는 수학적 프레임워크로, 특히 불확실성이 존재하는 환경에서 최적의 의사결정 전략을 수립하는 데 활용됨.

  • 강화학습(Reinforcement Learning)의 이론적 기반
  • 로봇 제어, 게임 AI, 자율주행차, 금융 트레이딩 등 다양한 분야에 적용
  • 현재 상태만으로 의사결정이 가능한 "마르코프 속성(Markov Property)"에 기반

MDP의 5가지 핵심 요소

MDP는 다음 5가지 요소로 구성된 튜플 <S, A, P, R, γ>로 정의됨:

  1. 상태(State, S): 에이전트가 인식하는 환경의 상태

    • 게임에서의 현재 위치, 점수, 남은 시간 등
    • 자율주행에서의 차량 위치, 속도, 주변 차량 정보 등

  2. 행동(Action, A): 에이전트가 각 상태에서 선택할 수 있는 행동들의 집합

    • 로봇의 이동 방향(상, 하, 좌, 우)
    • 주식 트레이딩에서의 매수, 매도, 홀딩 등

  3. 상태 전이 확률(State Transition Probability, P): 현재 상태에서 특정 행동을 취했을 때 다음 상태로 전이될 확률

    • P(s'|s,a): 상태 s에서 행동 a를 취했을 때 상태 s'로 전이될 확률
    • 환경의 불확실성을 수학적으로 모델링

  4. 보상(Reward, R): 특정 상태에서 특정 행동을 취했을 때 얻는 즉각적인 보상

    • R(s,a,s'): 상태 s에서 행동 a를 취해 상태 s'로 전이됐을 때 얻는 보상
    • 에이전트의 목표를 정의하는 신호

  5. 할인율(Discount Factor, γ): 미래 보상의 현재 가치를 결정하는 파라미터(0≤γ≤1)

    • γ=0: 즉각적인 보상만 고려
    • γ=1: 모든 미래 보상을 현재와 동일하게 중요시
    • 일반적으로 0.9~0.99 사이의 값 사용

마르코프 속성(Markov Property)

MDP의 핵심 가정인 마르코프 속성은 다음과 같이 정의됨:

  • 현재 상태가 주어졌을 때, 미래 상태는 과거 상태와 독립적
  • 수학적으로 표현: P(s{t+1}|s_t, a_t, s{t-1}, a{t-1}, ..., s_0, a_0) = P(s{t+1}|s_t, a_t)
  • 즉, 의사결정에 필요한 모든 정보가 현재 상태에 포함되어 있음

이러한 속성은 복잡한 의사결정 문제를 단순화하고 계산 효율성을 높이는 핵심 요소임.

MDP에서의 정책(Policy)

정책(π)은 각 상태에서 어떤 행동을 선택할지 결정하는 전략:

  • 결정론적 정책(Deterministic Policy): π(s) = a
  • 확률적 정책(Stochastic Policy): π(a|s) = P(a|s)
graph LR
    A[상태 s] --> B[정책 π]
    B --> C[행동 a]
    C --> D[환경]
    D --> E[새로운 상태 s']
    D --> F[보상 r]
    E --> A

가치 함수(Value Function)

MDP에서는 두 가지 중요한 가치 함수가 정의됨:

  1. 상태 가치 함수(State Value Function, V^π(s)): 정책 π를 따를 때 상태 s에서 시작하여 얻을 수 있는 기대 누적 보상

    V^π(s) = Eπ [ ∑{t=0}^{∞} γ^t R_{t+1} | S_0 = s ]

  2. 행동 가치 함수(Action Value Function, Q^π(s,a)): 정책 π를 따를 때 상태 s에서 행동 a를 취한 후 얻을 수 있는 기대 누적 보상

    Q^π(s,a) = Eπ [ ∑{t=0}^{∞} γ^t R_{t+1} | S_0 = s, A_0 = a ]

최적 정책과 벨만 방정식(Bellman Equation)

MDP의 목표는 기대 누적 보상을 최대화하는 최적 정책 π*를 찾는 것:

  • 최적 상태 가치 함수: V*(s) = max_π V^π(s)
  • 최적 행동 가치 함수: Q*(s,a) = max_π Q^π(s,a)

벨만 최적 방정식(Bellman Optimality Equation)은 이러한 최적 가치 함수의 재귀적 관계를 표현:

  • V(s) = max*a [ R(s,a) + γ ∑{s'} P(s'|s,a) V*(s') ]
  • Q(s,a) = R(s,a) + γ ∑{s'} P(s'|s,a) max{a'} Q(s',a')

MDP 해결 방법

MDP 문제를 해결하는 주요 알고리즘:

  1. 다이나믹 프로그래밍(Dynamic Programming): 모델이 완전히 알려진 경우

    • 가치 반복(Value Iteration)
    • 정책 반복(Policy Iteration)

  2. 모델 프리 방법(Model-Free Methods): 모델을 모르는 경우

    • 몬테카를로 방법(Monte Carlo Methods)
    • 시간차 학습(Temporal-Difference Learning): Q-Learning, SARSA 등
flowchart TD
    A[MDP 문제] --> B{모델 정보?}
    B -->|알고 있음| C[다이나믹 프로그래밍]
    B -->|모름| D[모델 프리 방법]
    C --> E[가치 반복]
    C --> F[정책 반복]
    D --> G[몬테카를로 방법]
    D --> H[시간차 학습]
    H --> I[Q-Learning]
    H --> J[SARSA]

실제 MDP 적용 사례

1. 자율주행 차량의 의사결정

  • 상태(S): 차량 위치, 속도, 주변 차량 정보, 도로 상태 등
  • 행동(A): 가속, 감속, 좌회전, 우회전, 차선 변경 등
  • 전이 확률(P): 행동 후 차량의 다음 상태 확률(도로 상태, 타 차량 반응 등에 영향)
  • 보상(R): 안전 주행(+), 목적지 도착(+++), 교통 법규 위반(-), 충돌(- - -)
  • 할인율(γ): 0.95~0.99 (장기적 안전 고려)

2. 로봇 내비게이션

  • 상태(S): 로봇의 위치, 방향, 배터리 상태, 장애물 정보
  • 행동(A): 전진, 회전, 정지 등
  • 전이 확률(P): 모터 오차, 슬립 등으로 인한 불확실성
  • 보상(R): 목표 지점 접근(+), 장애물 회피(+), 충돌(-), 배터리 소모(-)
  • 할인율(γ): 0.9 (효율적 경로 계획)

3. 금융 투자 의사결정

  • 상태(S): 포트폴리오 구성, 시장 상태, 경제 지표 등
  • 행동(A): 매수, 매도, 홀딩
  • 전이 확률(P): 시장 변동에 따른 다음 상태 확률
  • 보상(R): 수익(+), 손실(-), 거래 비용(-)
  • 할인율(γ): 0.8~0.95 (투자 기간에 따라 다름)

MDP의 한계와 확장

MDP는 강력한 프레임워크지만 몇 가지 한계가 존재:

  1. 부분 관측 문제: 실제 환경에서는 상태를 완전히 관측하기 어려움

    • 해결책: POMDP(Partially Observable MDP)

  2. 차원의 저주: 상태 공간이 커지면 계산 복잡도가 기하급수적으로 증가

    • 해결책: 함수 근사(Function Approximation), 딥러닝 활용

  3. 탐색-활용 딜레마(Exploration-Exploitation Dilemma): 새로운 정보 탐색과 기존 지식 활용 사이의 균형

    • 해결책: ε-greedy, UCB(Upper Confidence Bound), Thompson Sampling 등

  4. 모델 불확실성: 전이 확률과 보상 함수의 정확한 추정이 어려움

    • 해결책: 베이지안 RL, 강건한 MDP(Robust MDP)

결론

MDP는 불확실성이 존재하는 환경에서 순차적 의사결정 문제를 효과적으로 모델링하는 수학적 프레임워크로, 강화학습의 이론적 기반을 제공함.

  • 5가지 핵심 요소(상태, 행동, 전이 확률, 보상, 할인율)로 구성
  • 마르코프 속성에 기반한 단순화된 모델링
  • 벨만 방정식을 통한 최적 정책 도출
  • 다양한 실제 문제에 적용 가능

정보처리기술사로서 MDP의 개념과 응용을 이해하는 것은 지능형 시스템 설계 및 의사결정 알고리즘 구현에 필수적인 역량임.

Keywords

Markov Decision Process, 마르코프 결정 과정, Reinforcement Learning, 강화학습, State Transition Probability, 상태 전이 확률, Bellman Equation, 벨만 방정식, Value Function, 가치 함수, Decision Making, 의사결정, Dynamic Programming, 동적 계획법

728x90
반응형