MDP, 상태, 행동, 보상(MDPs, States, Actions & Rewards)

마르코프 결정 과정(Markov Decision Process; MDP)은 다섯 가지 요소, 즉 상태(states), 행동(actions), 전이(transitions), 보상(rewards), 할인(discount)으로 이루어집니다. 강화학습(Reinforcement Learning; RL)의 모든 것, 즉 Q-learning, PPO, DPO, GRPO는 이 형태 위에서 최적화를 수행합니다. 한 번 제대로 익히면 나머지 강화학습 자료를 훨씬 쉽게 읽을 수 있습니다.

유형: Learn 언어: Python 선수 지식: Phase 1 · 06 (확률과 분포), Phase 2 · 01 (ML 분류 체계) 예상 시간: 약 45분

문제

여러분이 체스 봇(chess bot)을 만들고 있다고 해봅시다. 혹은 재고 계획기(inventory planner)나 거래 에이전트(trading agent)를 만들고 있을 수도 있고, 추론 모델(reasoning model)을 학습시키는 PPO 루프를 작성하고 있을 수도 있습니다. 서로 다른 네 가지 영역(domain)처럼 보이지만 놀라운 공통점이 하나 있습니다. 네 경우 모두 같은 수학적 대상(mathematical object) 하나로 정리된다는 점입니다.

지도학습(supervised learning)은 (x, y) 쌍을 제공하고 그 위에 함수를 맞추라고 요구합니다. 반면 강화학습(reinforcement learning)에는 라벨(label)이 주어지지 않습니다. 대신 상태들의 흐름, 우리가 취한 행동들, 그리고 하나의 스칼라 값으로 표현되는 보상(scalar reward)만 주어집니다. 방금 둔 수가 게임을 이기게 했나요? 그 재고 보충 결정이 비용을 절감했나요? 그 거래가 이익을 냈나요? LLM이 방금 생성한 토큰(token)이 평가자(judge)로부터 더 높은 보상을 받게 만들었나요?

이 흐름을 형식화(formalize)하기 전에는 거기에서 무언가를 학습할 수 없습니다. "내가 무엇을 보았는가", "내가 무엇을 했는가", "다음에는 무슨 일이 일어났는가", "그 결과가 얼마나 좋았는가"라는 네 가지 질문이 각각 추론 가능한 객체로 표현되어야 합니다. 그 형식화의 결과물이 바로 마르코프 결정 과정(MDP)입니다. 이 phase에서 다루는 모든 강화학습 알고리즘은 마지막에 등장하는 RLHF와 GRPO 루프까지 포함해, 모두 이 같은 형태 위에서 최적화를 수행합니다.

개념

다섯 가지 구성 요소.

• 상태(States) S. 에이전트(agent)가 결정을 내리는 데 필요한 모든 정보입니다. GridWorld에서는 격자 위의 칸(cell)이고, 체스에서는 보드(board) 전체이며, LLM에서는 컨텍스트 윈도우(context window)와 필요한 메모리(memory)입니다.
• 행동(Actions) A. 에이전트가 선택할 수 있는 선택지입니다. 위/아래/왼쪽/오른쪽으로 이동하기, 한 수를 두기, 다음 토큰(token)을 내보내기 등이 여기에 해당합니다.
• 전이(Transitions) P(s' | s, a). 상태 s에서 행동 a를 취했을 때 도달할 다음 상태의 확률 분포입니다. 체스에서는 결정론적(deterministic)이고, 재고 관리에서는 확률적(stochastic)이며, LLM 디코딩(decoding)에서는 거의 결정론적입니다.
• 보상(Rewards) R(s, a, s'). 스칼라 신호(scalar signal)입니다. 승리 = +1, 패배 = -1처럼 정의할 수도 있고, 매출에서 비용을 뺀 값일 수도 있으며, GRPO의 로그 가능도 비율 항(log-likelihood ratio term)일 수도 있습니다.
• 할인(Discount) γ ∈ [0, 1). 미래 보상을 현재 보상 대비 얼마나 반영할지 결정하는 값입니다. γ = 0.99는 대략 100 스텝 정도의 지평(horizon)을, γ = 0.9는 대략 10 스텝 정도의 지평을 확보합니다.

마르코프 성질(Markov property) 은 다음과 같이 표현됩니다.

P(s_{t+1} | s_t, a_t) = P(s_{t+1} | s_0, a_0, …, s_t, a_t)

즉, 미래는 오직 현재 상태에만 의존한다는 뜻입니다. 만약 그렇지 않다면 상태 표현(state representation)이 불완전한 것이며, 이는 방법론의 실패가 아니라 상태 설계의 실패로 봐야 합니다.

정책과 리턴(Policies and returns). 정책(policy) π(a | s)는 상태를 행동 분포로 매핑하는 함수입니다. 리턴(return) G_t = r_t + γ r_{t+1} + γ² r_{t+2} + …은 미래 보상들을 할인하여 합한 값(discounted sum)입니다. 가치(value) V^π(s) = E[G_t | s_t = s]는 정책 π를 따를 때 상태 s에서 시작하는 기대 리턴(expected return)이고, Q-값(Q-value) Q^π(s, a) = E[G_t | s_t = s, a_t = a]은 첫 행동을 a로 고정했을 때의 기대 리턴입니다. 모든 강화학습 알고리즘은 이 둘 중 하나를 추정한 뒤 그 추정값을 바탕으로 정책 π를 개선합니다.

벨만 방정식(Bellman equations). 이 phase 전체가 사용하는 고정점 방정식(fixed-point equations)은 다음과 같습니다.

V^π(s) = Σ_a π(a|s) Σ_{s', r} P(s', r | s, a) [r + γ V^π(s')]

Q^π(s, a) = Σ_{s', r} P(s', r | s, a) [r + γ Σ_{a'} π(a'|s') Q^π(s', a')]

이 식들은 기대 리턴을 "이번 스텝(step)에서 받는 보상"과 "도달한 다음 상태의 할인된 가치(discounted value)"로 분해합니다. 본질적으로 재귀적(recursive)인 구조이며, Phase 9의 모든 알고리즘은 이 방정식을 수렴할 때까지 반복하거나(동적 계획법, dynamic programming), 샘플링하거나(몬테카를로, Monte Carlo), 한 스텝만큼만 부트스트랩(bootstrap, 시간차 학습 temporal difference)합니다.

직접 만들기

Step 1: 작은 결정론적 MDP 만들기

4×4 GridWorld 환경을 구성합니다. 에이전트는 왼쪽 위(top-left) 칸에서 시작하고, 오른쪽 아래(bottom-right) 칸이 종료 상태(terminal)입니다. 매 스텝마다 -1의 보상이 주어지며, 행동은 {up, down, left, right} 네 가지입니다. 자세한 구현은 code/main.py에서 확인할 수 있습니다.

GRID = 4
TERMINAL = (3, 3)
ACTIONS = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)}

def step(state, action):
    if state == TERMINAL:
        return state, 0.0, True
    dr, dc = ACTIONS[action]
    r, c = state
    nr = min(max(r + dr, 0), GRID - 1)
    nc = min(max(c + dc, 0), GRID - 1)
    return (nr, nc), -1.0, (nr, nc) == TERMINAL

다섯 줄 남짓한 짧은 코드가 환경(environment) 전체입니다. 결정론적 전이(deterministic transitions), 매 스텝마다 일정한 페널티(step penalty), 흡수 종료 상태(absorbing terminal state)를 갖춘 구조입니다.

Step 2: 정책 롤아웃(rollout) 수행하기

정책은 상태를 받아 행동에 대한 분포로 매핑해 주는 함수입니다. 가장 단순한 형태의 정책은 모든 행동을 같은 확률로 선택하는 균등 무작위(uniform random) 정책입니다.

def uniform_policy(state):
    return {a: 0.25 for a in ACTIONS}

def rollout(policy, max_steps=200):
    s, total, steps = (0, 0), 0.0, 0
    for _ in range(max_steps):
        a = sample(policy(s))
        s, r, done = step(s, a)
        total += r
        steps += 1
        if done:
            break
    return total, steps

이 무작위 정책을 1,000번 실행해 봅니다. 4×4 보드에서 평균 리턴은 대략 -60에서 -80 사이로 측정됩니다. 반면 최적 리턴은 -6으로, 단순히 아래쪽과 오른쪽 방향을 따라 직선 경로로 이동하기만 하면 됩니다. 이 평균 리턴과 최적 리턴 사이의 간격을 줄여 나가는 것이 Phase 9 전체의 핵심 과제입니다.

Step 3: 벨만 방정식으로 V^π를 정확히 계산하기

규모가 작은 MDP에서 벨만 방정식은 곧 하나의 선형 시스템(linear system)입니다. 모든 상태를 열거(enumerate)하고, 각 상태에 기대값 연산을 적용한 뒤, 값이 더 이상 변하지 않을 때까지 반복하면 됩니다.

def policy_evaluation(policy, gamma=0.99, tol=1e-6):
    V = {s: 0.0 for s in all_states()}
    while True:
        delta = 0.0
        for s in all_states():
            if s == TERMINAL:
                continue
            v = 0.0
            for a, pi_a in policy(s).items():
                s_next, r, _ = step(s, a)
                v += pi_a * (r + gamma * V[s_next])
            delta = max(delta, abs(v - V[s]))
            V[s] = v
        if delta < tol:
            return V

이 절차가 바로 반복 정책 평가(iterative policy evaluation)입니다. Sutton & Barto 교재의 가장 첫 번째 알고리즘이며, 이후 등장하는 모든 강화학습 방법의 이론적 토대가 됩니다.

Step 4: γ는 물리적 의미를 가진 하이퍼파라미터입니다

유효 지평(effective horizon)은 대략 1 / (1 - γ) 정도로 계산됩니다. γ = 0.9는 약 10 스텝, γ = 0.99는 약 100 스텝, γ = 0.999는 약 1000 스텝의 시야를 의미합니다.

γ가 너무 낮으면 에이전트가 근시안적(myopic)으로 행동하게 됩니다. 반대로 너무 높으면 신용 할당(credit assignment)이 매우 어지러워집니다. 먼 미래의 보상 하나에 너무 많은 초기 스텝이 책임을 나눠 갖게 되기 때문입니다. LLM 분야의 RLHF는 에피소드(episode)가 짧고 명확히 끝(bounded)이 있기 때문에 보통 γ = 1을 사용합니다. 제어(control) 작업에서는 0.95–0.99를 자주 쓰고, 지평이 매우 긴 전략 게임에서는 0.999 같은 값을 사용합니다.

주의할 점

• 비마르코프 상태(Non-Markovian state). 결정을 내리는 데 최근 세 개의 관측(observation)이 필요하다면, 현재 관측 하나만으로는 "상태"라고 할 수 없습니다. 해결책은 여러 프레임을 쌓아서 상태로 만드는 프레임 스태킹(frame-stacking)입니다. 예를 들어 Atari 환경의 DQN은 4개의 프레임을 쌓아 입력으로 사용합니다. 또는 관측 위에 순환 상태(recurrent state)를 두는 방법, 즉 LSTM이나 GRU를 활용하는 방법도 있습니다.
• 희소 보상(Sparse rewards). 승패에서만 보상이 발생하는 경우, 상태 공간이 큰 환경에서는 학습이 거의 불가능에 가깝습니다. 이런 경우에는 중간 신호를 제공하도록 보상을 다듬는 보상 셰이핑(reward shaping)을 적용하거나, 모방 학습(imitation learning)으로 초기 단계를 부트스트랩(bootstrap)할 수 있습니다(Phase 9 · 09 참조).
• 보상 해킹(Reward hacking). 실제 목표 대신 대리 보상(proxy reward)을 최적화하면 종종 병적인 행동(pathological behavior)이 나타납니다. OpenAI의 보트 레이싱 에이전트가 경주를 끝내지 않고 파워업을 영원히 모으기 위해 제자리에서 원을 그리며 돌았던 사례가 대표적입니다. 보상은 항상 대리 지표가 아니라 우리가 진짜로 원하는 목표 결과(target outcome)를 기준으로 정의해야 합니다.
• 할인 계수 설정 오류(Discount mis-spec). 무한 지평 작업에서 γ = 1을 사용하면 모든 가치가 무한대로 발산합니다. 반드시 유한 지평을 정해 두거나 γ < 1을 사용해야 합니다.
• 보상 스케일(Reward scale). {+100, -100} 보상과 {+1, -1} 보상은 동일한 최적 정책(optimal policy)을 만들어 내지만, 그라디언트 크기(gradient magnitudes)는 매우 다릅니다. PPO나 DQN에 입력하기 전에 대략 [-1, 1] 범위로 정규화해 두는 것이 좋습니다.

사용해보기

2026년 기준의 강화학습 스택은 코드를 작성하기 전에 모든 강화학습 파이프라인을 먼저 MDP 형태로 정리합니다.

학습 루프(training loop)를 작성하기 전에 위의 다섯 가지 튜플(tuple)을 먼저 종이에 적어 봅니다. "강화학습이 동작하지 않는다"는 버그 리포트 대부분은, 알고 보면 종이 위에서부터 MDP 형식화가 이미 깨져 있는 경우에서 비롯됩니다.

산출물 만들기

outputs/skill-mdp-modeler.md로 저장합니다.

---
name: mdp-modeler
description: Given a task description, produce a Markov Decision Process spec and flag formulation risks before training.
version: 1.0.0
phase: 9
lesson: 1
tags: [rl, mdp, modeling]
---

Given a task (control / game / recommendation / LLM fine-tuning), output:

1. State. Exact feature vector or tensor spec. Justify Markov property.
2. Action. Discrete set or continuous range. Dimensionality.
3. Transition. Deterministic, stochastic-with-known-model, or sample-only.
4. Reward. Function and source. Sparse vs shaped. Terminal vs per-step.
5. Discount. Value and horizon justification.

Refuse to ship any MDP where the state is non-Markovian without explicit mention of frame-stacking or recurrent state. Refuse any reward that was not defined in terms of the target outcome. Flag any `γ ≥ 1.0` on an infinite-horizon task. Flag any reward range >100x the typical step reward as a likely gradient-explosion source.

연습문제

1. 쉬움. code/main.py에 4×4 GridWorld 환경과 무작위 정책 롤아웃을 구현합니다. 에피소드를 10,000번 실행한 뒤, 리턴의 평균(mean)과 표준편차(std)를 보고합니다. 그 결과를 최적 리턴(-6)과 비교해 봅니다.
2. 중간. 균등 무작위 정책(uniform-random policy)에 대해 γ ∈ {0.5, 0.9, 0.99}로 policy_evaluation을 실행합니다. 각각의 V를 4×4 격자 형태로 출력합니다. γ가 커질수록 종료 상태 근처의 상태 가치가 더 빠르게 커지는 이유를 설명해 봅니다.
3. 어려움. GridWorld를 확률적 환경으로 바꿉니다. 각 행동이 확률 p = 0.1로 인접 방향(adjacent direction)으로 미끄러지도록 만들고, 균등 정책을 다시 평가합니다. 시작 상태의 가치 V[start]는 좋아지나요, 아니면 나빠지나요? 그 이유는 무엇인가요?

핵심 용어

더 읽을거리

• Sutton & Barto (2018). Reinforcement Learning: An Introduction, 2nd ed. — 강화학습 분야의 표준 교재입니다. 3장에서는 MDP와 벨만 방정식을 다루고, 1장에서는 이후 모든 lesson의 바탕이 되는 보상 가설(reward hypothesis)을 설명합니다.
• Bellman (1957). Dynamic Programming — 벨만 방정식의 기원이 되는 저서입니다.
• OpenAI Spinning Up — Part 1: Key Concepts — 심층 강화학습(deep RL) 관점에서 MDP를 간결하게 소개하는 입문 자료입니다.
• Puterman (2005). Markov Decision Processes — MDP와 정확해법(exact solution methods)을 다루는 운영 연구(operations research) 분야의 대표적 참고서입니다.
• Littman (1996). Algorithms for Sequential Decision Making (PhD thesis) — MDP를 동적 계획법의 특수한 형태(dynamic-programming specialization)로 유도하는 가장 깔끔한 자료 중 하나입니다.