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

MDP란?

마르코프 결정 과정(Markov Decision Process, MDP)은 강화학습에서 의사결정을 포함한 확률적 모델을 말합니다. 어떤 상태에서 에이전트가 행동을 선택하면, 그에 따라 확률적으로 다음 상태로 전이되고 보상(reward)을 받는 구조예요.

한 줄로 말하면, "상태·행동·전이·보상·할인율로 환경을 정의하고, 다음 상태는 현재 상태와 행동에만 의존한다고 보는 틀"이라고 볼 수 있습니다. 강화학습에서는 이 MDP 환경 속에서 에이전트가 장기적인 누적 보상(기대 수익)을 최대화하는 최적 정책(policy)을 학습하는 것이 목표입니다.

MDP의 기본 구성

• 상태(State) · 행동(Action) · 전이확률(Transition) · 보상(Reward) · 할인율(γ)
• Markov 성질: 다음 상태는 과거 전체가 아니라 현재 상태와 현재 행동에만 의존한다고 가정합니다.

---

1. 마르코프 성질 (Markov Property)

마르코프 성질은, 미래 상태가 과거 전체 이력이 아니라 오직 현재 상태에만 의존한다는 성질이에요. “현재 상태가 과거 정보를 다 요약하고 있다”고 보는 거라고 생각하면 됩니다. 강화학습에서는 환경을 마르코프 성질을 만족한다고 가정해서 상태 전이와 의사결정을 단순화합니다.

마르코프한 상태 예: 바둑

바둑판 위의 현재 돌 배치 전체(흑·백 위치, 공배 등)가 바로 하나의 상태입니다. 마르코프 성질에 따르면, 다음 수 이후의 상태는 “과거에 어떤 순서로 뒀는지”와는 무관하고, 지금 판 모양 + 이번에 선택한 착수에 의해서만 결정돼요. 같은 판 모양이면, 중앙을 먼저 뒀든 귀를 먼저 뒀든 상관없이, 지금 어디에 두느냐만 중요합니다. 즉 “현재 판의 모양”이 과거를 다 담고 있다면, 그 한 판이 마르코프 상태의 예라고 보면 됩니다.

마르코프하지 않은 상태 예: 다이어트

현재 상태만으로는 미래를 예측하기 어렵고, 과거 이력이 더 필요할 때 마르코프하지 않다고 합니다. 예를 들어 “지금 배가 고프다”만으로는 다음 행동(폭식할지, 참을지)을 예측하기 어려워요. 어제 얼마나 굶었는지, 최근 스트레스, 단 음식 섭취 빈도 같은 과거 정보가 행동에 크게 영향을 주기 때문입니다. 같은 “배고픈 상태”라도 과거가 다르면 선택이 달라지는 경우라서, 마르코프 성질을 만족하지 않습니다.

💬 마르코프하게 만들려면?
현재 상태에 “과거에 필요한 정보” 를 넣어 주면 됩니다.
→ 여러 관측을 모아서 상태를 만들거나
→ RNN처럼 과거를 기억하게 하거나
→ 상태를 더 크게 정의해서 마르코프하게 만든다.

---

2. Markov Process (마르코프 프로세스)

Markov Process(MP)는 “현재 상태만 알면 미래 상태를 예측할 수 있다”는 마르코프 성질을 따르는 확률적 상태 전이 과정이에요. 다음 상태는 과거 전체가 아니라 오직 현재 상태에만 의존해서 결정된다고 보는 모델입니다. 강화학습에서는 환경을 일단 이렇게 된 마르코프 프로세스로 보고, 여기에 보상·행동이 더해지면 MRP, MDP로 확장됩니다.

• 상태 전이 다이어그램: 노드 = 상태, 화살표 = 전이, 화살표 위 숫자 = 전이 확률
  (예: S1→S2 (0.7) → 현재 S1일 때 70%로 S2)
• 전이 확률 행렬: 다음 상태는 반드시 하나로 가야 하므로 각 행의 합은 1입니다.

---

3. Markov Reward Process (MRP, 마르코프 보상 과정)

Markov Reward Process(MRP)는 Markov Process에 보상(reward)과 할인율(γ)이 붙은 모델이에요. 행동은 없고, 상태 전이 + 보상만 정의된 구조라고 보면 됩니다. (상태 집합 S, 전이확률 P, 보상 함수 R, 할인율 γ)로 쓰고, 목표는 특정 상태에서 시작했을 때의 기대 누적 보상 = 가치 함수 V(s)를 구하는 것입니다.

예: S = {Working, Lunch, Home, Overheated}, P = 전이확률, R = 상태 보상, γ = 0.9

💬 할인률 (γ, 감마)

할인률(Discount Factor, γ)은 미래 보상을 현재 가치로 얼마나 반영할지 정하는 0~1 사이 계수예요. γ=0.9면 한 단계 뒤 보상은 0.9배, 두 단계 뒤는 0.9²=0.81배처럼, 멀어질수록 영향력을 줄여서 계산한다고 보면 됩니다.

• γ가 0에 가까우면 → 당장 보상만 중요. 단기적 의사결정. “지금 이 순간이 가장 중요하다”는 관점.
• γ가 1에 가까우면 → 미래 보상까지 거의 동일하게 반영. 장기 전략. “지금보다 미래가 더 중요할 수 있다”는 관점.

에이전트가 단기로 볼지 장기로 볼지를 정하는 핵심 하이퍼파라미터라고 생각하면 됩니다.

💬 가치 함수와 “왜 즉시 보상만 보면 안 되나”

Working의 즉시 보상이 +5로 제일 크다고 해서, 무조건 Working만 하면 될까요? Overheated(-10)로 갈 확률이 있기 때문에, 장기 기대 보상을 봐야 합니다. 그래서 가치 함수 V(s), Q(s,a)로 “앞으로 얼마나 좋을지”를 수치화하는 거예요.

---

4. MDP와 MP의 차이 · Action · Policy · Value

MP vs MDP

• Markov Process(MP): 상태 + 전이 확률만. 의사결정 주체 없이 확률적으로 흐르는 과정.
• Markov Decision Process(MDP): 여기에 Action(행동)이 추가. 에이전트가 행동을 고르면 그에 따라 다음 상태·보상이 달라짐. 미래를 통제하고 장기 보상을 최적화하는 의사결정 모델이라고 보면 됩니다.

Action (행동)

에이전트가 현재 상태를 보고 환경에 영향을 주기 위해 선택하는 것이 행동입니다. 같은 상태라도 어떤 행동을 하느냐에 따라 다음 상태와 보상이 달라지니까, 학습에서 매우 중요해요. 이산적(위·아래·좌·우)일 수도 있고 연속적(로봇 관절 각도 등)일 수도 있으며, 미래 결과를 바꾸는 핵심 결정 변수라고 이해하면 됩니다.

Policy (정책)

“이 상황에서 나는 무엇을 할 것인가?”에 대한 규칙표예요. 상태를 넣으면 그에 맞는 행동을 골라 주는 행동 매뉴얼이라고 보면 됩니다.

• 결정적 정책: 같은 상태면 항상 같은 행동 (예: 배고프면 항상 햄버거)
• 확률적 정책: 같은 상태에서도 확률로 여러 행동 중 하나 선택 (예: 배고프면 70% 햄버거, 30% 샐러드)

Value (가치)

특정 상태(또는 상태–행동)에서 시작했을 때, 앞으로 받을 미래 누적 보상의 기대값이에요. “지금 이 상태(또는 이 행동)가 장기적으로 얼마나 좋은가?”를 숫자로 나타낸 거라고 보면 됩니다. 상태 가치 V(s), 행동 가치 Q(s, a)가 있고, 에이전트는 이걸 학습해서 더 높은 가치를 갖는 쪽으로 정책을 개선합니다. 단기 보상이 아니라 미래까지 포함한 ‘좋음의 정도’를 정량화한 지표라고 이해하면 됩니다.

---

5. MDP 구성 요소 요약

기호	의미	한 줄 설명
S	상태 집합	에이전트가 놓일 수 있는 모든 상황
A	행동 집합	각 상태에서 선택 가능한 행동들
P(s′ | s, a)	전이 확률	상태 s에서 행동 a 시 다음 상태 s′로 갈 확률
R(s, a)	보상 함수	(s, a)에서 받는 (기대) 보상
γ	할인율 (0~1)	미래 보상을 얼마나 중요하게 볼지

---

6. 벨만 방정식 (Bellman Equation)

가치 함수가 “한 스텝 보상 + 다음 상태의 가치”로 재귀적으로 정의된다는 식이에요.

• 상태 가치: V^π(s) = 지금 받는 기대 보상 + γ × (다음 상태들의 가치를 π에 따라 평균)
• Q 함수: Q^π(s, a) = (s,a)에서의 기대 보상 + γ × (다음 상태 s′에서 π 따를 때의 기대 가치)

이걸 이용해 가치 반복(Value Iteration), 정책 반복(Policy Iteration) 같은 동적 계획법(DP) 알고리즘을 유도합니다.

---

7. MDP와 강화학습 알고리즘

• 환경 모델(전이 P, 보상 R)을 알 때 → 벨만 방정식으로 V, Q, π를 반복 계산하는 DP(동적 계획법).
• 환경 모델을 모를 때 → Monte Carlo, TD, Q-learning, Policy Gradient 등은 경험(샘플)만으로 V 또는 Q 또는 π를 근사합니다.

정리하면, MDP = 강화학습 문제의 수학적 정의, 다양한 RL 알고리즘 = 그 MDP를 모델 유무·가치/정책 기준으로 푸는 방법이라고 보면 됩니다.

---

8. MDP 예제: 퇴근 후 선택 (Working → Gym → Home)

이론만 보면 어렵게 느껴질 수 있어서, 퇴근 후 선택 상황으로 MDP를 한 번 구현해 보는 예제를 해봤어요!

상황

• 상태: Working(일하는 중), Gym(헬스장), Home(집)
• 행동: 현재 상태에서 갈 수 있는 곳 중 하나 선택 (예: Working에서는 working / gym / home)
• 종료: Home 도착 시 보상 10점 받고 에피소드 종료

보상 표 (Reward)

현재 상태	행동	다음 상태	보상
Working	Working	Working	3점
Working	헬스장(gym)	Gym	5점
Working	집(home)	Home	2점
Gym	Working	Working	4점
Gym	집(home)	Home	2점
Home	(종료)	-	10점

현재 상태를 출력하고 input()으로 행동을 받아서 다음 상태로 넘어가며 보상을 누적하고, Home에 도착하면 Return(할인 적용 보상 합)을 계산해 보면 됩니다.

# 코드 작성해보기
total_reward = 0
state = 'working'

while True:
    print('현재 상태:', state)

    if state == 'working':
        print('gym / home / working')
        action = input('행동 선택: ').strip().lower()
        if action == 'working':
            reward = 3
            state = 'working'
        elif action == 'gym':
            reward = 5
            state = 'gym'
        elif action == 'home':
            reward = 2
            state = 'home'
        else:
            print("잘못된 입력 (gym / home / working 중 선택)")
            continue
    elif state == 'gym':
        print('gym / home / working')
        action = input('행동 선택: ').strip().lower()
        if action == 'working':
            reward = 4
            state = 'working'
        elif action == 'home':
            reward = 2
            state = 'home'
        else:
            print("잘못된 입력 (gym / home / working 중 선택)")
            continue

    elif state == 'home':
        reward = 10
        total_reward += reward
        print(f'보상: {reward} | 누적 보상: {total_reward}')
        break

    else:
        print('상태 값 오류!')
        break

    total_reward += reward
    print(f'보상: {reward} | 누적 보상: {total_reward}')
     print('끝!')

문제 1: Return 계산

경로: working → gym → working → home, γ = 0.9
보상 순서: 5, 4, 2, 10 → G = r₀ + γ·r₁ + γ²·r₂ + γ³·r₃
정답: 18.32

문제 2: 정책 비교

• 정책 A: working → working → working → home → G_A = 14.61
• 정책 B: working → gym → working → home → G_B = 17.51
• 정답: B*

문제 3: γ에 따른 행동 전략

정답: γ가 0에 가까우면 현재만 보고, 1에 가까우면 미래까지 계산한다.

# 문제 풀이용 코드로 수정
total_reward = 0
gamma = 0.9
state = 'working'
rewards = []

while True:
    print('현재 상태:', state)

    if state == 'working':
        print('gym / home / working')
        action = input('행동 선택: ').strip().lower()
        if action == 'working':
            reward = 3
            state = 'working'
        elif action == 'gym':
            reward = 5
            state = 'gym'
        elif action == 'home':
            reward = 2
            state = 'home'
        else:
            print("잘못된 입력 (gym / home / working 중 선택)")
            continue
    elif state == 'gym':
        print('gym / home / working')
        action = input('행동 선택: ').strip().lower()
        if action == 'working':
            reward = 4
            state = 'working'
        elif action == 'home':
            reward = 2
            state = 'home'
        else:
            print("잘못된 입력 (gym / home / working 중 선택)")
            continue

    elif state == 'home':
        reward = 10
        total_reward += reward
        rewards.append(reward)
        print(f'보상: {reward} | 누적 보상: {total_reward}')
        break

    else:
        print('상태 값 오류!')
        break

    rewards.append(reward)
    total_reward += reward
    print(f'보상: {reward} | 누적 보상: {total_reward}')

G = 0
for i, r in enumerate(rewards):
    G += (gamma ** i) * r

print('보상 리스트: ', rewards)
print('총 보상: ', total_reward)
print('리턴: ', round(G, 2))

[ 오늘의 정리 ]

마르코프 결정 과정(MDP)은 “상태, 행동, 전이 확률, 보상, 할인율”로 환경을 정의하고, “다음 상태는 현재 상태와 행동에만 의존한다”는 마르코프 성질을 전제로, 강화학습의 목표(기대 Return 최대화)와 가치 함수·벨만 방정식·최적 정책을 수학적으로 다루기 위한 기본 틀이라고 보면 됩니다.