MDP(마르코프 결정 과정): 순차적 의사결정을 모델링하는 프레임워크

불확실한 환경에서 순차적 결정을 모델링하는 틀

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

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

상태·행동·전이확률·보상·할인율로 정의되는 튜플

MDP는 다음 다섯 요소로 구성된 튜플 <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 사이의 값 사용

현재 상태만 보면 되는 마르코프 속성

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)
• 즉, 의사결정에 필요한 모든 정보가 현재 상태에 포함되어 있음

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

정책이 상태를 행동으로 연결한다

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

• 결정론적 정책(Deterministic Policy): π(s) = a
• 확률적 정책(Stochastic Policy): π(a|s) = P(a|s)

⤢✕

가치 함수로 기대 누적 보상을 계산한다

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 ]

벨만 방정식으로 최적 정책을 찾는다

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

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

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

• V*(s) = maxa [ 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 문제를 해결하는 주요 알고리즘은 모델 정보의 유무에 따라 나뉜다.

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

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

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

   • 몬테카를로 방법(Monte Carlo Methods)
   • 시간차 학습(Temporal-Difference Learning): Q-Learning, SARSA 등

⤢✕

자율주행·로봇·금융에서 MDP를 어떻게 정의하는가

자율주행 차량의 의사결정

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

로봇 내비게이션

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

금융 투자 의사결정

• 상태(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의 개념과 응용을 이해하는 것은 지능형 시스템 설계 및 의사결정 알고리즘 구현에 필수적인 역량이다.