Markov Decision Process (MDP)

마르코프 결정 과정(MDP)은 순차적 의사결정 문제를 나타내는 수학적 모델입니다. 에이전트는 상태를 관찰하고 행동을 선택한 뒤 보상을 받으며, 선택과 우연의 영향을 함께 받는 다음 상태에 도달합니다. 형식적으로 MDP는 상태 집합, 행동 집합, 상태 전이 확률 P(s′ | s, a), 보상 함수 R(s, a), 그리고 일반적으로 0과 1 사이의 할인율 γ로 구성됩니다. 문제를 푼다는 것은 각 상태에서 행동을 선택하는 규칙인 정책을 찾아 미래 보상의 할인 합계 기댓값을 최대화하는 것입니다. MDP는 1950년대 운영 연구에서 등장했으며, Richard Bellman의 동적 계획법이 문제 해결 방법을 제공했습니다. MDP는 강화 학습(RL)의 표준 문제 설정입니다.

마르코프 성질#

정의에 필요한 가정은 마르코프 성질입니다. 다음 상태와 보상은 그 상태까지 이어진 경로가 아니라 현재 상태와 행동에만 의존합니다. 따라서 상태는 에이전트가 고려해야 할 모든 정보를 완전히 요약합니다. 움직이는 물체의 경우 단일 카메라 프레임에는 위치만 표시되고 속도는 나타나지 않으므로 이 가정을 충족하지 않습니다. 이에 DeepMind의 Atari 게임 DQN은 움직임을 파악할 수 있도록 마지막 네 프레임을 쌓아 네트워크에 입력했습니다.

노이즈가 있거나 가려진 센서를 사용하는 로봇처럼 에이전트가 전체 상태를 관측할 수 없는 경우 문제는 부분 관측 마르코프 결정 과정(POMDP)이 됩니다. 이때 에이전트는 상태 자체가 아니라 필터 또는 순환 네트워크를 사용해 유지하는 상태에 대한 믿음을 바탕으로 행동합니다.

MDP의 구성 요소#

• 상태: 에이전트가 처할 수 있는 상황입니다. 예를 들어 로봇의 관절 각도와 로봇이 잡으려는 물체의 위치가 있습니다.
• 행동: 각 상태에서 선택할 수 있는 항목입니다. 행동 공간은 이산적일 수도 있고(좌회전, 우회전), 연속적일 수도 있습니다(도 단위의 조향 각도).
• 전이 확률: 행동 이후 각 다음 상태에 도달할 확률입니다. 바퀴가 미끄러지는 경우, 다른 운전자 및 기타 모든 무작위 요인을 반영합니다.
• 보상: 상태 전이에 대해 즉시 제공되는 수치 피드백입니다. 설계자가 보상을 선택하는 방식이 작업을 정의하며, 부주의한 설계는 보상 해킹을 유발할 수 있습니다.
• 할인율: 즉각적인 보상에 비해 미래 보상을 얼마나 중요하게 반영할지를 나타냅니다. γ = 0.9이면 10단계 뒤의 보상은 지금 같은 보상을 받는 경우의 0.9¹⁰ ≈ 0.35만큼 가치가 있습니다.

에피소드가 끝날 때까지 매 시간 단계에서 같은 상호작용을 반복합니다:

MDP 풀이#

상태 가치는 정책에 따라 해당 상태에서 기대할 수 있는 수익이며, 최적 가치는 벨만 방정식을 만족합니다. 각 상태의 가치는 최선의 행동이 제공하는 즉각적인 보상과 그 행동으로 이어지는 상태 가치의 할인된 확률 가중 합계입니다. 전이 확률과 보상을 알고 있으면 동적 계획법으로 이 방정식을 직접 풉니다. 가치 반복(Bellman, 1957)은 값이 더 이상 변하지 않을 때까지 방정식을 반복 적용하고, 정책 반복(Howard, 1960)은 정책 평가와 개선을 번갈아 수행합니다.

이 NumPy 예제는 Sutton과 Barto의 강화 학습: 입문에 나오는 재활용 로봇 문제에 가치 반복을 적용합니다. 이 로봇은 배터리가 높거나 낮을 때 캔을 찾거나, 기다리거나, 충전하는 행동 중 하나를 선택해야 합니다:

import numpy as np

# 재활용 로봇 MDP: 상태 0 = 배터리 높음, 1 = 배터리 낮음; 행동 0 = 탐색, 1 = 대기, 2 = 충전
gamma = 0.9  # 할인율
P = np.zeros((2, 3, 2))  # P[s, a, s'] = 상태 s에서 행동 a를 취한 후 s'에 도달할 확률
P[0, 0] = [0.7, 0.3]  # 배터리가 높을 때 탐색하면 배터리가 낮은 상태로 떨어질 수 있음
P[1, 0] = [0.4, 0.6]  # 배터리가 낮을 때 탐색하면 방전될 수 있음(로봇이 구조되어 충전됨)
P[:, 1] = np.eye(2)  # 대기하면 배터리 수준이 그대로 유지됨
P[:, 2] = [1.0, 0.0]  # 충전하면 항상 배터리가 높은 상태로 복구됨
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # 기댓값 R[s, a]; 배터리가 낮을 때 탐색: 0.6 * 2 + 0.4 * -3 = 0

# 가치 반복: 값이 더 이상 변하지 않을 때까지 벨만 최적성 업데이트 적용
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # 각 상태에서 각 행동의 가치
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

출력 결과는 배터리가 높은 상태에서 15.75, 낮은 상태에서 14.17이며, 배터리가 높을 때는 탐색하고 낮을 때는 충전하는 정책입니다. 배터리가 낮을 때 탐색하면 40% 확률로 −3의 구조 페널티를 받으므로 탐색의 가치가 충전보다 낮아집니다.

전이 확률을 알 수 없는 경우 강화 학습은 경험에서 같은 가치를 추정합니다. Q-러닝은 샘플링한 전이에서 행동 가치를 업데이트하고, 정책 그래디언트 방법은 정책을 직접 조정하며, 딥 강화 학습은 상태 공간이 너무 커서 나열하기 어려울 때 신경망을 사용합니다. 몬테카를로 트리 탐색과 같은 계획 알고리즘은 현재 상태에서 도달 가능한 미래만 시뮬레이션하여 거대한 MDP를 온라인으로 풉니다.

MDP와 관련 모델 비교#

• 마르코프 연쇄: 행동이나 보상이 없는 무작위 상태의 연속입니다. MDP에는 선택과 목표가 추가됩니다.
• 은닉 마르코프 모델(HMM): 노이즈가 있는 신호로만 상태를 관측할 수 있는 마르코프 연쇄입니다. POMDP와 MDP의 관계도 이와 같습니다.
• 다중 무장 밴딧: 상태가 하나뿐이며 각 행동의 보상이 과거와 관계없이 독립적으로 결정되는 MDP입니다.
• 강화 학습: 전이 확률을 제공받지 않고 상호작용을 통해 MDP에서 효과적으로 행동하는 방법을 학습하는 기법군입니다.

응용 분야#

• 로보틱스 및 제어: 물체 잡기, 걷기, 내비게이션은 MDP로 공식화하며, 정책은 시뮬레이션에서 학습하는 경우가 많습니다. 카메라 기반 제어에서는 Ultralytics YOLO26과 같은 탐지기가 상태 정보를 제공할 수 있습니다. 그러면 각 프레임이 객체 클래스와 박스 좌표의 짧은 목록으로 바뀌어 원시 픽셀보다 정책 입력의 크기가 훨씬 작아집니다.
• 언어 모델 학습: RLHF와 RLVR은 텍스트 생성을 MDP로 다룹니다. 상태는 프롬프트와 지금까지 생성된 토큰으로 구성되고, 행동은 다음 토큰이며, 응답이 완성되면 보상이 주어집니다.
• 운영 연구: 재고 재주문, 장비 유지보수, 동적 가격 책정은 전형적인 MDP 문제입니다. Ronald Howard는 Sears 카탈로그 우편 발송을 최적화하면서 정책 반복을 개발했습니다.