관련 포스트강화 학습 머신러닝 최적화 추천 시스템

마르코프 결정 과정(Markov Decision Process)

•

2026년 10월 18일 발행•2026년 10월 18일 수정

요약

상태·행동·전이 확률·보상·할인율로 순차적 의사결정 문제를 정의하는 강화 학습의 수학적 틀

중급

확률과 기댓값, 조건부 확률에 대한 이해가 필요하며, 재귀식인 벨만 방정식과 반복 알고리즘의 수렴 개념을 알아야 한다.

태그

강화 학습 머신러닝 최적화 추천 시스템

#개념

마르코프 결정 과정(Markov Decision Process, MDP)은 불확실한 환경에서 에이전트가 순차적으로 행동을 선택하는 문제를 수학적으로 표현한 틀이다. 상태, 행동, 전이 확률, 보상, 할인율로 문제를 정의하며, 강화 학습(Reinforcement Learning)의 이론적 기반이 된다.

MDP의 출발점은 마르코프 성질(Markov Property)이다. 다음 상태의 분포가 현재 상태와 행동에만 의존하고 그 이전의 이력과는 무관하다는 가정으로, $P(S_{t+1} \mid S_t, A_t) = P(S_{t+1} \mid S_0, A_0, \dots, S_t, A_t)$로 표현한다. 즉 현재 상태가 미래를 예측하는 데 필요한 정보를 모두 담고 있어야 하며, 그렇지 않다면 상태 정의를 보강해야 한다.

Bellman(1957)이 동적 계획법과 함께 체계화한 이후 MDP는 운용 과학, 제어 이론, 경제학, 인공지능에서 순차적 의사결정을 기술하는 공통 언어로 쓰여 왔다. 문제를 MDP로 정의하면 어떤 알고리즘을 적용할지, 해가 존재하는지, 수렴이 보장되는지를 일관되게 논할 수 있다. 표준적인 MDP는 다섯 요소의 튜플 $(S, A, P, R, \gamma)$로 정의된다.

MDP의 구성 요소

상태 집합(S): 에이전트가 처한 환경의 상황을 나타내는 모든 상태의 집합이다. 재고 수준, 사용자 맥락, 로봇의 관절 각도 등이 상태가 된다.
행동 집합(A): 각 상태에서 에이전트가 선택할 수 있는 행동의 집합이다. 이산적일 수도, 연속적일 수도 있다.
전이 확률(P): 상태 $s$에서 행동 $a$를 했을 때 상태 $s'$로 이동할 확률 $P(s' \mid s, a)$이다. 환경의 동역학을 나타낸다.
보상 함수(R): 전이에 따라 받는 즉각적인 수치 신호 $R(s, a, s')$이다. 에이전트가 달성해야 할 목표를 정의한다.
할인율(γ): 미래 보상을 현재 가치로 환산하는 0과 1 사이의 계수다.

에이전트와 환경은 매 시점 상태를 관측하고, 행동을 선택하고, 보상과 다음 상태를 받는 상호작용을 반복한다. 이 과정에서 생성되는 상태·행동·보상의 나열을 궤적(Trajectory)이라 하며, 에이전트의 목표는 시점 $t$ 이후 누적 보상인 이득(Return) $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$의 기댓값을 최대화하는 것이다.

할인율(Discount Factor) $\gamma$는 수학적 편의와 의미를 함께 가진다. $\gamma$가 1보다 작으면 무한히 이어지는 과제에서도 이득이 유한한 값으로 수렴하고, 불확실한 먼 미래보다 가까운 보상을 더 중시하게 된다. $\gamma$가 0에 가까우면 당장의 보상만 보는 근시안적 에이전트가, 1에 가까우면 장기 결과를 중시하는 에이전트가 된다. 실무에서는 대략 $1/(1-\gamma)$ 스텝을 유효 계획 범위로 해석하기도 한다.

에이전트의 행동 규칙을 정책(Policy) $\pi(a \mid s)$라 한다. 정책 $\pi$를 따를 때 상태 $s$에서 기대되는 이득을 상태 가치 함수(State-Value Function) $V^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$, 상태 $s$에서 행동 $a$를 먼저 한 뒤 $\pi$를 따를 때의 기대 이득을 행동 가치 함수(Action-Value Function) 또는 Q 함수 $Q^\pi(s, a) = \mathbb{E}_\pi[G_t \mid S_t = s, A_t = a]$라 한다.

가치 함수는 재귀적 구조를 가지며, 이를 벨만 기대 방정식(Bellman Expectation Equation)이라 한다. 상태 가치 함수는 $V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s, a)[R(s, a, s') + \gamma V^\pi(s')]$로 쓸 수 있다. 현재 상태의 가치가 즉각 보상과 다음 상태 가치의 할인 합으로 분해된다는 의미이며, 이 분해 덕분에 긴 미래를 한 스텝씩 계산할 수 있다.

모든 정책 중 가장 큰 가치를 주는 정책을 최적 정책이라 하고, 그 가치 함수는 벨만 최적 방정식(Bellman Optimality Equation) $V^(s) = \max_a \sum_{s'} P(s' \mid s, a)[R(s, a, s') + \gamma V^(s')]$을 만족한다. Q 함수로는 $Q^(s, a) = \sum_{s'} P(s' \mid s, a)[R(s, a, s') + \gamma \max_{a'} Q^(s', a')]$이며, 최적 Q 함수를 알면 각 상태에서 $\arg\max_a Q^*(s, a)$를 고르는 것만으로 최적 정책을 얻는다. 환경 모델을 알면 동적 계획법(Dynamic Programming)으로 이를 정확히 풀 수 있으며, 주요 알고리즘은 다음과 같다.

동적 계획법 기반 해법

정책 평가(Policy Evaluation): 벨만 기대 방정식을 반복 적용해 주어진 정책의 가치 함수를 계산한다.
정책 개선(Policy Improvement): 계산된 가치 함수에 대해 탐욕적으로 행동을 고르도록 정책을 갱신한다. 새 정책은 이전 정책보다 나쁘지 않음이 보장된다.
정책 반복(Policy Iteration): 정책 평가와 정책 개선을 번갈아 수행하며, 정책이 더 이상 바뀌지 않으면 최적 정책에 도달한다.
가치 반복(Value Iteration): 벨만 최적 방정식을 갱신 규칙으로 직접 반복 적용해 최적 가치 함수로 수렴시킨 뒤 정책을 추출한다.

동적 계획법은 상태와 행동 수가 많아지면 계산량이 폭증하는 차원의 저주(Curse of Dimensionality)에 부딪히고, 무엇보다 환경 모델 $P$와 $R$을 알아야 한다. 실제 문제에서는 전이 확률을 모르는 경우가 대부분이므로, 환경과 상호작용한 경험 샘플만으로 가치 함수나 정책을 학습하는 모델 프리(Model-Free) 방법이 필요하다.

대표적인 모델 프리 방법인 Q-러닝(Q-Learning)은 Watkins와 Dayan(1992)이 수렴성을 증명한 알고리즘으로, 경험 $(s, a, r, s')$마다 $Q(s, a) \leftarrow Q(s, a) + \alpha[r + \gamma \max_{a'} Q(s', a') - Q(s, a)]$로 갱신한다. 다음 상태에서 최선의 행동을 가정하므로 실제 행동 정책과 학습 대상 정책이 다른 오프 폴리시(Off-Policy) 방법이다.

SARSA는 다음 상태에서 실제로 선택한 행동 $a'$를 사용해 $Q(s, a) \leftarrow Q(s, a) + \alpha[r + \gamma Q(s', a') - Q(s, a)]$로 갱신하는 온 폴리시(On-Policy) 방법이다. 탐색 중의 위험한 행동까지 가치에 반영되므로 Q-러닝보다 보수적인 정책을 학습하는 경향이 있다. 두 방법 모두 상태 공간이 크면 표 대신 신경망으로 Q 함수를 근사하며, 이것이 DQN 같은 심층 강화 학습으로 이어진다. 한편 현실의 문제는 표준 MDP 가정을 벗어나는 경우가 많아 다양한 확장 모형이 쓰인다.

MDP의 주요 확장

부분 관측 MDP(Partially Observable MDP, POMDP): 에이전트가 상태를 직접 보지 못하고 관측만 받는 경우다. 상태에 대한 확률 분포인 믿음 상태(Belief State)를 새로운 상태로 삼아 다시 MDP로 다룬다.
반 마르코프 결정 과정(Semi-MDP): 행동마다 걸리는 시간이 다른 경우로, 여러 단계로 이루어진 옵션(Option)을 다루는 계층적 강화 학습의 기반이 된다.
제약 MDP(Constrained MDP): 보상 최대화와 함께 비용이나 위험에 대한 제약을 만족해야 하는 경우다. 예산 제약이 있는 광고 입찰이 해당한다.
마르코프 게임(Markov Game): 여러 에이전트가 같은 환경에서 상호작용하는 다중 에이전트 확장이다.

POMDP는 Kaelbling, Littman, Cassandra(1998)가 인공지능 계획 문제의 관점에서 정리했다. 믿음 상태는 연속 공간이므로 정확한 풀이가 매우 어렵고, 실무에서는 순환 신경망이나 트랜스포머로 관측 이력을 요약해 상태처럼 사용하는 근사가 흔하다. 반대로 상태 전이가 없는 극단적인 경우는 멀티암드 밴딧(Multi-Armed Bandit) 문제로 단순화된다. MDP는 산업 현장의 순차 의사결정 문제를 정식화하는 데에도 널리 쓰이며, 대표적인 응용은 다음과 같다.

주요 응용 분야

추천 시스템: 사용자 상태(최근 행동, 세션 맥락)에서 추천 목록을 행동으로 보고, 클릭뿐 아니라 장기 재방문·구매를 보상으로 삼아 장기 만족도를 최적화한다.
재고 관리: 재고 수준을 상태, 발주량을 행동, 판매 수익에서 보관·품절 비용을 뺀 값을 보상으로 두어 최적 발주 정책을 찾는다.
광고 입찰: 남은 예산과 시간을 상태, 입찰가를 행동, 전환이나 클릭을 보상으로 두어 캠페인 기간 전체의 성과를 최대화한다.
로보틱스와 제어: 센서 값을 상태, 모터 명령을 행동으로 두어 보행, 조작, 자율주행 같은 연속 제어 정책을 학습한다.

MDP를 실무에 적용할 때 가장 어려운 부분은 알고리즘보다 문제 정의다. 마르코프 성질을 만족할 만큼 충분한 정보를 상태에 담아야 하고, 보상이 실제 비즈니스 목표와 어긋나면 에이전트가 의도하지 않은 지름길을 찾는 보상 해킹(Reward Hacking)이 생긴다. 또 온라인에서 바로 탐색하기 어려운 서비스에서는 기존 로그로 정책을 학습·평가하는 오프라인 강화 학습과 오프 폴리시 평가가 함께 필요하다.

정리하면 MDP는 "현재 상태에서 어떤 행동을 해야 장기적으로 가장 좋은가"라는 질문을 수학적으로 다룰 수 있게 해 주는 공통 틀이다. 동적 계획법, Q-러닝, 정책 경사, 그리고 대규모 언어 모델(Large Language Model)의 인간 피드백 기반 강화 학습(RLHF)까지 대부분의 강화 학습 기법이 MDP 위에서 정의되므로, 강화 학습을 이해하려면 먼저 MDP의 구성 요소와 벨만 방정식을 정확히 이해해야 한다.

#관련 용어

마르코프 성질

다음 상태가 현재 상태와 행동에만 의존하고 과거 이력과는 무관하다는 성질

정책

각 상태에서 어떤 행동을 선택할지 정하는 규칙 또는 확률 분포

가치 함수

주어진 정책을 따를 때 상태나 상태·행동 쌍에서 기대되는 누적 할인 보상

벨만 방정식

현재 가치를 즉각 보상과 다음 상태 가치의 할인 합으로 재귀적으로 표현한 식

Q-러닝

환경 모델 없이 경험 샘플로 최적 행동 가치 함수를 학습하는 오프 폴리시 알고리즘

부분 관측 마르코프 결정 과정(POMDP)

에이전트가 상태를 직접 보지 못하고 관측만 받는 MDP의 확장

#직무 연관도

Data Analyst낮음

재고·입찰 등 순차 의사결정 문제의 구조를 이해하고 정책의 성과를 평가

Data Scientist밀접

강화 학습 문제를 정식화하고 상태·보상을 설계하며 알고리즘을 연구·개발

Data Engineer보통

시뮬레이션 환경과 학습 파이프라인을 구축하고 학습된 정책을 서비스에 배포

#사용 사례

전자상거래물류인터넷 서비스금융제조자율주행

개요

마르코프 결정 과정은 시간에 따라 이어지는 의사결정의 장기 효과를 최적화해야 하는 곳에서 쓰인다. 전자상거래와 인터넷 서비스에서는 장기 만족도를 고려한 추천과 광고 입찰에, 물류와 제조에서는 재고 보충과 생산 스케줄링에, 금융에서는 포트폴리오 조정과 주문 집행에, 자율주행과 로보틱스에서는 제어 정책 학습에 활용된다.

사례

광고 플랫폼에서 남은 예산과 남은 시간, 시간대별 트래픽을 상태로, 입찰 배수를 행동으로, 전환 수를 보상으로 정의한 MDP를 구성하고, 과거 입찰 로그로 정책을 학습해 하루 예산을 고르게 소진하면서 전환을 최대화한다.