마르코프 결정 과정(馬爾科夫 決定 過程, Markov Decision Process, MDP)은 순차적 의사 결정 문제(sequential decision-making problem)를 수학적으로 모델링하기 위한 프레임워크이다. 확률론, 제어 이론, 인공지능, 강화 학습 등 다양한 분야에서 환경과의 상호작용을 통해 최적의 정책(policy)을 찾는 문제를 정의하는 데 널리 사용된다.
1. 정의 및 구성 요소 마르코프 결정 과정은 보통 5개의 튜플 $(S, A, P, R, \gamma)$로 정의된다.
- 상태 공간 (State Space, $S$): 에이전트(agent)가 처할 수 있는 모든 가능한 상태의 집합이다. 유한 집합이거나 연속 공간일 수 있다.
- 행동 공간 (Action Space, $A$): 각 상태에서 에이전트가 선택할 수 있는 모든 가능한 행동의 집합이다.
- 상태 전이 확률 (Transition Probability, $P$): 현재 상태 $s$에서 행동 $a$를 취했을 때 다음 상태 $s'$로 전이될 확률 $P(s' | s, a)$를 나타낸다. 이는 마르코프 성질(Markov property)을 만족한다. 즉, 다음 상태는 과거의 모든 이력이 아닌 현재 상태와 행동에만 의존한다.
- 보상 함수 (Reward Function, $R$): 상태 $s$에서 행동 $a$를 취하여 상태 $s'$로 전이될 때 얻는 즉각적인 보상(스칼라 값) $R(s, a, s')$ 또는 $R(s, a)$의 기대값을 정의한다.
- 할인율 (Discount Factor, $\gamma$): $0 \le \gamma \le 1$ 범위의 값으로, 미래 보상의 현재 가치를 평가하는 데 쓰인다. $\gamma$가 1에 가까우면 장기적 보상을 중시하고, 0에 가까우면 즉각적 보상을 중시한다.
2. 핵심 개념
- 정책 (Policy, $\pi$): 에이전트의 행동 전략을 정의하는 함수로, 결정론적 정책 $\pi(s) = a$ 또는 확률론적 정책 $\pi(a|s)$로 표현된다. 목표는 기대 누적 보상(수익, return)을 최대화하는 최적 정책 $\pi^*$을 찾는 것이다.
- 가치 함수 (Value Function): 특정 정책 $\pi$를 따를 때 상태 $s$에서 시작하여 얻을 것으로 기대되는 누적 할인 보상의 기대값을 상태 가치 함수 $V^\pi(s)$로, 상태-행동 쌍 $(s, a)$에서 시작할 때의 기대값을 행동 가치 함수 $Q^\pi(s, a)$로 정의한다.
- 벨만 방정식 (Bellman Equation): 가치 함수들 간의 재귀적 관계를 나타내는 방정식이다. 최적 가치 함수는 벨만 최적 방정식(Bellman Optimality Equation)을 만족하며, 이를 통해 최적 정책을 유도할 수 있다.
3. 해결 방법 마르코프 결정 과정의 해(최적 정책 찾기)는 주로 다음과 같은 방법으로 구한다.
- 동적 계획법 (Dynamic Programming, DP): 환경 모델($P, R$)을 완전히 알고 있을 때 사용하며, 가치 반복(value iteration), 정책 반복(policy iteration) 알고리즘 등이 있다.
- 몬테카를로 방법 (Monte Carlo Methods): 모델을 모를 때 경험(episode)을 통해 가치 함수를 추정한다.
- 시간차 학습 (Temporal Difference Learning, TD Learning): DP와 몬테카를로의 장점을 결합한 것으로, 모델 없이 부트스트랩(bootstrap) 방식으로 학습한다. Q-러닝(Q-learning), SARSA 등이 대표적이다.
- 함수 근사 (Function Approximation): 상태 공간이 거대하거나 연속적일 때 신경망 등을 이용해 가치 함수나 정책을 근사하는 심층 강화 학습(Deep Reinforcement Learning) 기법(DQN, Actor-Critic 등)이 사용된다.
4. 확장 및 변형
- 부분 관측 마르코프 결정 과정 (POMDP, Partially Observable MDP): 에이전트가 상태를 직접 관측하지 못하고 관측(observation)을 통해 상태를 추론해야 하는 경우로 확장된 모델이다.
- 연속 시간 마르코프 결정 과정 (Continuous-time MDP): 시간이 이산적이지 않고 연속적으로 흐르는 경우를 다룬다.
- 다중 에이전트 마르코프 결정 과정 (Multi-agent MDP / Markov Game): 여러 에이전트가 상호작용하는 환경을 모델링한다.
5. 응용 분야 로봇 제어, 자율 주행, 게임 AI(바둑, 비디오 게임 등), 자원 관리, 금융 포트폴리오 최적화, 추천 시스템, 자연어 처리 대화 시스템 등 순차적인 의사 결정이 필요한 광범위한 분야에 적용된다.
