마르코프 결정 과정(MDP)은 결과가 불확실할 때 순차적 의사 결정을 위한 수학적 모델이다. 이는 확률적 의사 결정 과정의 한 유형으로, 종종 확률적 동적 계획법 방법을 사용하여 해결된다. 1950년대 운영 연구에서 시작된 MDP는 이후 생태학, 경제학, 의료, 통신, 그리고 강화 학습과 같은 분야에서 인정을 받게 되었다. 강화 학습에서 MDP 프레임워크는 학습 에이전트와 환경 간의 상호 작용을 모델링하며, 상태, 행동, 보상으로 특징지어지고, 인과 관계, 불확실성, 명시적 목표를 포함한 Artificial intelligence 문제의 핵심 요소를 단순화된 표현으로 제공한다.
이 이름은 러시아 수학자 안드레이 마르코프가 개발한 마르코프 연쇄와의 연관성에서 유래한다. "마르코프" 속성은 상태 전이가 이전 이력이 아닌 현재 상태와 행동에만 의존하는 기본 구조를 의미한다. 이 과정은 이러한 전이에 영향을 미치는 결정을 내리는 것을 포함하기 때문에 "결정 과정"이라고 불리며, 마르코프 연쇄를 불확실성 하의 의사 결정으로 확장한다.
공식 정의
MDP는 일반적으로 4-튜플 \((S, A, P_a, R_a)\)로 정의되며, 여기서:
- \(S\)는 상태 공간으로, 이산적이거나 연속적일 수 있다 (예: 실수 집합).
- \(A\)는 행동 공간이며, \(A_s\)는 상태 \(s\)에서 사용 가능한 행동 집합을 나타낸다. 이 집합 역시 이산적이거나 연속적일 수 있다.
- \(P_a(s, s')\)는 시간 \(t\)에서 상태 \(s\)의 행동 \(a\)가 시간 \(t+1\)에서 상태 \(s'\)로 이어질 전이 확률이다. 이산 상태의 경우, \(P_a(s, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)\)이다. 연속 상태 공간의 경우, 확률은 적분을 통해 정의되며, 종종 르베그 측도에 대해 정의된다.
- \(R_a(s, s')\)는 행동 \(a\)를 취하여 \(s\)에서 \(s'\)로 전이한 후 받는 즉시 보상(또는 기대 보상)이다. 보상은 일반적으로 확률 변수이다.
정책 함수 \(\pi\)는 상태 공간에서 행동 공간으로의 (잠재적으로 확률적인) 매핑으로, 각 상태에서 어떤 행동을 취할지 지정한다.
최적화 목표
MDP의 목표는 무작위 보상의 누적 함수, 일반적으로 무한 지평선에 걸친 기대 할인 합: \(\mathbb{E}[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})]\)을 최대화하는 정책 \(\pi\)를 찾는 것이다. 여기서 \(\gamma \in [0, 1)\)는 할인 계수이다. 정책이 고정되면, 각 상태의 행동이 \(\pi(s)\)에 의해 결정되므로 MDP는 마르코프 연쇄처럼 작동한다.
일반적인 해결 방법에는 가치 반복과 정책 반복과 같은 동적 계획법 기법이 포함되며, 이는 최적 가치 함수 또는 정책을 계산한다. 이러한 방법은 Q-러닝 및 SARSA와 같은 Reinforcement learning 알고리즘의 기초가 된다.
응용 분야
MDP는 다양한 분야에 널리 적용된다. 경제학에서는 최적 소비 및 투자 결정을 모델링한다. 의료에서는 만성 질환 관리와 같은 불확실성 하의 치료 계획을 안내한다. 통신에서는 자원 할당 및 네트워크 라우팅을 최적화한다. 생태학에서는 종 관리의 보전 전략을 알린다. Machine learning에서 MDP는 강화 학습의 중심이며, 로봇 공학, 게임 플레이, 자율 시스템에서 볼 수 있듯이 에이전트가 환경과의 상호 작용을 통해 학습할 수 있게 한다.
강화 학습과의 관계
강화 학습(RL)은 MDP 프레임워크를 사용하여 에이전트-환경 상호 작용을 공식화한다. RL에서 에이전트는 전이 확률이나 보상 함수를 사전에 알지 못한다. 대신, 환경에서 얻은 샘플을 사용하여 시행착오를 통해 최적 정책을 학습한다. 이는 모델 매개변수가 알려져 있다고 가정하는 고전적 MDP 해결과 구별된다. 딥 강화 학습을 포함한 현대 RL은 MDP를 Neural network 함수 근사기와 결합하여 대규모 상태 공간을 처리하며, 게임 플레이 및 자율 주행과 같은 응용에서 입증되었다.
확장 및 변형
여러 확장이 기본 MDP의 한계를 해결한다. 부분 관측 가능 마르코프 결정 과정(POMDP)은 에이전트가 전체 상태를 직접 관찰할 수 없는 상황을 처리한다. 팩터화된 MDP는 상태 변수의 구조를 활용하여 확장성을 개선한다. 다중 에이전트 MDP는 상호 작용하는 목표를 가진 여러 의사 결정자로 프레임워크를 확장한다. 이러한 변형은 핵심 마르코프 속성을 유지하면서 더 복잡한 실제 문제에 적응한다.
역사적 배경
MDP의 공식화는 1950년대 리처드 벨만에 의해 이루어졌으며, 그는 동적 계획법도 개발했다. 안드레이 마르코프의 확률 과정에 대한 초기 연구는 이론적 기초를 제공했다. 그 이후로 MDP는 운영 연구와 인공 지능의 초석이 되었으며, 순차적 의사 결정의 이론적 및 응용 작업 모두에 영향을 미쳤다.