[2025 강화학습 Recap] Chapter 2: Markov Decision Processes

[2025 강화학습 Recap] Chapter 2: Markov Decision Processes

 

강화학습의 핵심은 불확실한 환경에서 순차적 의사결정을 통해 누적 보상을 최대화하는 것임. 하지만 이런 문제를 어떻게 수학적으로 표현하고 분석할 수 있을까?

이 장에서는 강화학습 문제를 정형화하는 표준 프레임워크인 마르코프 결정 과정(Markov Decision Process, MDP)을 다룸. MDP는 에이전트와 환경 간의 상호작용을 상태, 행동, 보상, 전이확률이라는 명확한 수학적 개념으로 모델링함.

MDP의 핵심 가정인 마르코프 성질부터 시작해서, 정책과 가치함수의 정의, 그리고 최적해를 특성화하는 벨만 방정식까지 살펴볼 예정임. 이러한 이론적 토대는 이후 장에서 다룰 모든 강화학습 알고리즘의 근간이 됨.
단순해 보이는 이 프레임워크가 어떻게 복잡한 현실 문제들을 효과적으로 모델링할 수 있는지, 그리고 왜 강화학습 연구의 출발점이 되는지 함께 알아보자.

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

1.1 기본 개념

"미래는 과거에 독립적이며, 오직 현재에만 의존한다"

수학적 정의: P(St+1|St) = P(St+1|S1, S2, ..., St)

직관적 이해:

• 현재 상태가 과거의 모든 정보를 충분히 담고 있음
• 다음 상태를 예측하는 데 과거 히스토리는 불필요
• "현재가 과거와 미래를 분리한다"

실생활 예시:

• 체스: 현재 말의 배치만 알면 충분 (이전 수순은 중요하지 않음)
• 날씨: 현재 기상 상태로 내일 날씨 예측 (일주일 전 날씨는 무관)
• 주식: 현재 주가 상태 (과거 주가 히스토리보다 현재 상황이 중요)

Markov Property 위반 사례:

• 포커: 상대방이 이전에 어떻게 플레이했는지(블러핑 패턴)가 중요
• 대화: 현재 문장만으로는 맥락 파악 불가, 이전 대화 내용 필요
• 주가 기술적 분석: 과거 차트 패턴이 미래 예측에 중요하다고 믿는 경우

1.2 State Transition Matrix (상태 전이 행렬)

• 정의: 현재 상태 s에서 다음 상태 s'로 갈 확률을 담은 행렬
• 특성: 각 행의 합이 1 (확률의 총합 = 1)
• 표기: P_ss' = P(St+1 = s' | St = s)

예시: 날씨 예측

        내일
오늘    맑음  비   흐림
맑음    0.7  0.2   0.1    ← 오늘 맑으면 내일도 맑을 확률 70%
비      0.3  0.4   0.3    ← 비가 오면 내일도 비 올 확률 40%
흐림    0.4  0.3   0.3    ← 흐리면 내일 확률이 고르게 분포

 

중요한 성질들:

• 각 행의 합 = 1: 확률의 기본 성질
• Stationary: 시간이 지나도 전이 확률 불변
• Irreducible: 모든 상태에서 다른 모든 상태로 갈 수 있음 (연결성)
• Aperiodic: 특정 주기 없이 상태 방문 가능

2. Markov Process (마르코프 과정) <S, P>

2.1 정의

"상태들과 전이 확률로만 구성된 확률적 과정"

구성요소:

• S: 상태들의 집합 (finite or infinite)
• P: 상태 전이 확률 행렬

2.2 특징

• Memoryless: 기억이 없는 확률 과정
• Stochastic: 확률에 기반한 랜덤 과정
• 시간 독립적: 전이 확률이 시간에 따라 변하지 않음

실생활 예시:

• 웹 페이지 간 사용자 이동 패턴
• 고객의 브랜드 선호도 변화
• 게임 내 캐릭터 상태 변화

Random Walk 예제:

상태: [1] ↔ [2] ↔ [3] ↔ [4] ↔ [5]
각 상태에서 좌우로 0.5 확률씩 이동
양 끝에서는 제자리 또는 안쪽으로만 이동

 

장기 행동 분석:

• Stationary Distribution: 충분한 시간 후 각 상태에 있을 확률
• Mean Return Time: 특정 상태로 돌아오는 데 걸리는 평균 시간
• Absorption Probability: 흡수 상태에 도달할 확률

3. Markov Reward Process (MRP) <S, P, R, γ>

3.1 왜 MRP가 필요한가?

Markov Process의 한계: 단순히 상태만 변하는 것을 관찰할 뿐, **"어떤 상태가 좋은가?"**를 알 수 없음

MRP의 목표: "각 상태의 가치를 평가하자!"

3.2 정의

"보상과 할인율이 추가된 마르코프 과정"

구성요소:

• S: 상태 집합
• P: 상태 전이 확률 행렬
• R: 보상 함수 (각 상태에서 받는 즉시 보상)
• γ: 할인율 (0 ≤ γ ≤ 1)

3.3 Return (수익)

정의: Gt = Rt+1 + γRt+2 + γ²Rt+3 + ... = Σ(γᵏRt+k+1)

할인율이 필요한 이유:

1. 수렴성 보장: 무한한 보상의 합을 유한하게 만듦
2. 불확실성 반영: 미래는 불확실하므로 현재 가치로 할인
3. 즉시성 선호: 나중의 보상보다 지금의 보상이 더 가치 있음
4. 수학적 편의: 계산을 단순화

할인율의 의미:

• γ = 0: 극도로 근시안적 (즉시 보상만 고려)
• γ = 1: 극도로 원시안적 (모든 미래 보상 동등하게 고려)
• γ = 0.9: 10스텝 후 보상은 현재 가치의 약 35%
• γ = 0.99: 100스텝 후 보상은 현재 가치의 약 37%

할인율 선택 가이드:

• Episode가 짧은 경우: γ = 0.9 ~ 0.95
• Episode가 긴 경우: γ = 0.99 ~ 0.999
• 실시간 제어: γ = 0.8 ~ 0.9 (빠른 반응 중요)
• 장기 계획: γ = 0.95 ~ 0.99 (미래 고려 중요)

경제학적 해석:

• 이자율과 유사: 할인율 = 1/(1+이자율)
• Risk Premium: 불확실성에 대한 추가 할인
• Time Preference: 개인의 시간 선호도 반영

3.4 State Value Function (상태 가치 함수)

정의: v(s) = E[Gt | St = s]

의미: 상태 s에서 시작해서 끝까지 받을 것으로 예상되는 총 보상

실용적 해석: "이 상태가 얼마나 좋은가?"

3.5 Bellman Equation for MRP

해결하고 싶은 문제: "각 상태의 가치를 어떻게 계산할까?"

핵심 아이디어: 현재 가치 = 즉시 보상 + 할인된 다음 상태들의 기댓값

수식: v(s) = R(s) + γ Σ P(s'|s) v(s')

직관적 이해:

• 현재 상태의 가치는 두 부분으로 나뉨
• 1. 지금 당장 받는 보상
• 2. 다음에 갈 수 있는 모든 상태들의 할인된 가치

벡터 형태: v = R + γPv

• 이를 풀면: v = (I - γP)⁻¹R (행렬의 역원이 존재할 때)

해결 방법들:

1. 직접 해법: 연립방정식으로 풀기 (상태 수가 적을 때)
2. 반복 해법: v_{k+1} = R + γPv_k (수렴할 때까지 반복)
3. Monte Carlo: 실제 샘플 궤적으로 추정

계산 복잡도:

• 직접 해법: O(n³) - 행렬 역원 계산
• 반복 해법: O(n²) per iteration - 행렬-벡터 곱셈
• n이 클 때는 반복 해법이 유리

수렴 조건: γ < 1이면 항상 수렴 보장

4. Markov Decision Process (MDP) <S, A, P, R, γ>

4.1 MRP의 한계와 MDP의 필요성

MRP의 한계:

• 환경이 상태를 바꿔주기만 하고, 우리는 수동적으로 관찰만 함
• "더 좋은 상태로 가고 싶은데 어떻게 해야 할까?" → 답이 없음

MDP의 아이디어:

• "내가 행동을 선택해서 더 좋은 상태로 갈 수 있다면?"
• 의사결정권을 Agent에게 주자!

4.2 정의

"의사결정(행동 선택)이 추가된 마르코프 보상 과정"

구성요소:

• S: 상태 집합
• A: 행동 집합
• P: 상태 전이 확률 (이제 행동에 의존)
• R: 보상 함수 (상태와 행동에 의존)
• γ: 할인율

핵심 차이점: Agent가 행동을 선택할 수 있음!

MDP vs MRP 비교:

MRPMDP제어없음 (수동적)있음 (능동적)전이고정된 확률행동에 따라 변함목표예측 (Prediction)제어 (Control)해법벡터 연산최적화 문제

 

실제 응용 예시:

• 로봇 제어: 상태(위치), 행동(모터 명령), 보상(목표 달성)
• 게임 AI: 상태(게임 상황), 행동(플레이어 선택), 보상(점수)
• 금융: 상태(시장 상황), 행동(투자 결정), 보상(수익)
• 자율주행: 상태(센서 정보), 행동(조향/가속), 보상(안전한 주행)

4.3 Policy (정책)

정의: π(a|s) = P(At = a | St = s)

의미: "각 상태에서 어떤 행동을 선택할 것인가?"

특징:

• Stationary: 시간에 독립적 (같은 상태에서는 항상 같은 확률 분포)
• Markovian: 현재 상태에만 의존 (히스토리 무관)

정책의 종류:

• Deterministic Policy: π(s) = a (확정적)
• Stochastic Policy: π(a|s) (확률적)

왜 확률적 정책이 필요한가?

• 게임 이론에서 혼합 전략
• 탐험을 위한 랜덤성
• 연속 행동 공간에서의 자연스러운 표현

정책의 특성:

• Memoryless: 현재 상태만 고려 (과거 행동 무관)
• Stationary: 시간이 지나도 같은 정책 (시간 독립적)
• Complete: 모든 상태에서 행동이 정의됨

정책 표현 방법:

1. Table: 작은 상태 공간에서 직접 저장
2. Linear: π(a|s) = softmax(θᵀφ(s,a))
3. Neural Network: 딥러닝으로 복잡한 정책 표현

정책 평가의 어려움:

• 같은 정책도 환경의 확률성 때문에 다른 결과
• 여러 번 실행해서 평균을 구해야 함
• 탐험 부족으로 일부 상태는 방문하지 못할 수 있음

5. 잠깐만!

1단계: 문제 정의

MRP: "이 환경에서 가만히 있으면 얼마나 좋을까?" (수동적)
MDP: "내가 행동을 선택할 수 있다면 얼마나 좋을까?" (능동적)

 

MDP를 정의했으니 이제 실제로 해결하고 싶은 문제가 무엇인지 명확히 하자.

2단계: 해결하고 싶은 질문들

• Prediction 문제: "주어진 정책이 얼마나 좋은가?"
• Control 문제: "가장 좋은 정책은 무엇인가?"

3단계: 자연스러운 접근

Prediction → Bellman Expectation Equation 
"정책을 따를 때 가치를 어떻게 계산하지?"

Control → Bellman Optimality Equation
"최적 정책을 어떻게 찾지?"

 

왜 이 순서인가?

1. Prediction이 Control보다 쉬움: 정책이 주어지면 단순히 계산 문제
2. Control은 Prediction을 포함: 최적 정책을 찾으려면 각 정책을 평가할 수 있어야 함
3. 점진적 확장: MRP 개념을 MDP로 확장하는 자연스러운 과정

실제 사고 과정:

1. "MDP에서 정책을 평가하려면?" → Bellman Expectation
2. "그럼 최고의 정책은?" → Bellman Optimality  
3. "이걸 어떻게 풀지?" → Dynamic Programming, RL 알고리즘들

 

6. Bellman Expectation Equation (예측 문제의 해법)

6.1 문제 정의

해결하려는 문제: "정책 π가 주어졌을 때, 각 상태의 가치는 얼마인가?"

6.2 Value Functions

State Value Function

정의: vπ(s) = E_π[Gt | St = s] 의미: 정책 π를 따를 때 상태 s에서 시작해서 받을 기댓값

Action Value Function (Q-function)

정의: qπ(s,a) = E_π[Gt | St = s, At = a] 의미: 상태 s에서 행동 a를 한 후 정책 π를 따를 때의 기댓값

6.3 Bellman Expectation Equations

State Value

수식: vπ(s) = Σ π(a|s) [R(s,a) + γ Σ P(s'|s,a) vπ(s')]

두 단계 분해:

1. 정책에 따른 행동 선택: 정책 π에 따라 행동들의 가중평균
2. 환경의 응답: 선택한 행동에 대한 환경의 확률적 응답

Action Value

수식: qπ(s,a) = R(s,a) + γ Σ P(s'|s,a) Σ π(a'|s') qπ(s',a')

관계식:

• vπ(s) = Σ π(a|s) qπ(s,a)
• qπ(s,a) = R(s,a) + γ Σ P(s'|s,a) vπ(s')

6.4 벨만 방정식의 해석

State Value 관점:

현재 상태 가치 = 정책에 따른 행동들의 가중평균 가치

 

Action Value 관점:

상태-행동 가치 = 즉시 보상 + 다음 상태에서의 정책 따라 행동할 때의 할인된 가치

 

벨만 방정식의 기하학적 해석:

• 고정점 정리: 벨만 연산자의 고정점이 해
• 수축 연산자: γ < 1이면 유일한 해 존재
• 반복 개선: 임의의 초기값에서 시작해도 수렴

실제 계산 시 고려사항:

• Bootstrap: 추정값으로 추정값을 개선 (순환 참조)
• Bias vs Variance: 정확도와 안정성의 트레이드오프
• Sample Complexity: 정확한 추정에 필요한 샘플 수

벨만 방정식의 한계:

• 차원의 저주: 상태 수가 기하급수적으로 증가
• 모델 의존성: 전이 확률과 보상 함수를 알아야 함
• 연속 공간: 무한한 상태/행동 공간에서는 직접 적용 어려움

7. Bellman Optimality Equation (제어 문제의 해법)

7.1 문제 정의

해결하려는 문제: "가장 좋은 정책은 무엇이고, 그때의 최대 가치는 얼마인가?"

7.2 Optimal Policy

정의: π* ≥ π for all π if vπ*(s) ≥ vπ(s) for all s

특성:

• 항상 존재함 (유한 MDP에서)
• 여러 개일 수 있음 (같은 최적 가치를 갖는 서로 다른 정책)
• 최적 가치 함수는 유일함

최적 정책의 구조:

• Deterministic: 확률적 정책보다 결정적 정책이 항상 존재
• Stationary: 시간에 독립적인 정책으로 충분
• Greedy: 최적 가치 함수에 대해 탐욕적 선택

최적 정책 찾기의 어려움:

• 탐험 딜레마: 최적을 찾으려면 탐험 필요, 하지만 탐험은 비최적
• 지역 최적: 정책 공간에서 지역 최적에 빠질 위험
• 계산 복잡도: 일반적으로 NP-hard 문제

실무에서의 접근:

• ε-optimal: 거의 최적인 정책으로 타협
• Approximation: 함수 근사로 실용적 해 구하기
• Online Learning: 경험하면서 점진적으로 개선

7.3 Optimal Value Functions

Optimal State Value: v*(s) = max_π vπ(s) Optimal Action Value: q*(s,a) = max_π qπ(s,a)

관계식: v*(s) = max_a q*(s,a)

7.4 Bellman Optimality Equations

State Value: v*(s) = max_a [R(s,a) + γ Σ P(s'|s,a) v*(s')]

Action Value: q*(s,a) = R(s,a) + γ Σ P(s'|s,a) max_a' q*(s',a')

핵심 차이점: 기댓값(평균) → 최댓값(최적화)

7.5 최적성 방정식의 의미

• 탐욕적 선택: 각 상태에서 가장 좋은 행동만 선택
• 일관성: 부분 문제의 최적해가 전체 문제의 최적해를 구성
• 동적 계획법의 원리: Principle of Optimality

 

8. 벨만 방정식의 한계와 실제 해결의 어려움

8.1 이론은 완벽한데 실제로는...

벨만 방정식을 통해 이론적으로는 완벽한 해답을 얻었음:

• Prediction: vπ(s) = Σ π(a|s) [R(s,a) + γ Σ P(s'|s,a) vπ(s')]
• Control: v*(s) = max_a [R(s,a) + γ Σ P(s'|s,a) v*(s')]

하지만 실제로 풀려면...

문제 1: 계산 복잡도

• 상태 수가 많으면: 체스(10^40), 바둑(10^170) → 불가능
• 연립방정식: n개 상태면 n×n 행렬 연산 필요
• 실시간 요구: 로봇은 1ms 내에 결정해야 함

문제 2: 모델을 모름

• 전이확률 P: 실제 환경에서는 모르는 경우가 대부분
• 보상함수 R: 명확하지 않거나 복잡함
• 예시: 자율주행에서 "비 올 때 브레이크 밟으면 미끄러질 확률"을 정확히 아는가?

문제 3: 연속 공간

• 상태 공간: 로봇 팔의 각도(무한한 실수값)
• 행동 공간: 자동차의 스티어링 각도(연속값)
• 벨만 방정식: 이산적 합계 기반 → 적용 어려움

8.2 그럼 어떻게 해결할까?

접근 방향들:

1. 모델을 알 때: Dynamic Programming 사용
2. 모델을 모를 때: 경험으로 학습 (Model-free)
3. 상태가 많을 때: 함수 근사 (Function Approximation)
4. 연속 공간: 샘플링이나 근사 기법

이제 구체적인 해결 방법들을 알아보자.

9. MDP 해결 방법

9.1 Dynamic Programming (모델 기반)

언제 사용: 전이확률 P와 보상함수 R을 정확히 아는 경우

Value Iteration

• 아이디어: 벨만 최적성 방정식을 반복적으로 적용
• 알고리즘: v_{k+1}(s) = max_a [R(s,a) + γ Σ P(s'|s,a) v_k(s')]
• 장점: 구현 간단, 수렴 보장
• 단점: 각 iteration마다 모든 상태 업데이트 필요
• 복잡도: 메모리 O(|S|), 시간 O(|S|²|A|) per iteration

Policy Iteration

• 아이디어: 정책 평가 → 정책 개선 반복
• 단계:
  1. Policy Evaluation: 현재 정책의 가치 계산
  2. Policy Improvement: 가치 기반으로 정책 개선
• 장점: 보통 Value Iteration보다 빠름
• 단점: 각 iteration에서 정책 평가가 비쌈

Dynamic Programming의 한계: 모델을 알아야 하고, 상태 수가 많으면 불가능

9.2 Model-free Methods (모델 모름)

동기: "실제 환경에서는 P와 R을 모르는데, 어떻게 학습하지?"

핵심 아이디어: 환경과 상호작용해서 경험으로 학습

Monte Carlo

• 아이디어: 실제 궤적을 여러 번 실행해서 Return 평균 계산
• 방법: v(s) ≈ 상태 s에서 시작한 여러 episode들의 Return 평균
• 장점: Unbiased (편향 없음), 간단한 개념
• 단점: High variance, Episode 끝나야 학습 가능
• 예시: 게임을 100번 해보고 각 상황의 평균 점수 계산

Temporal Difference (TD)

• 아이디어: 부트스트래핑으로 실시간 가치 업데이트
• 핵심: v(s) ← v(s) + α[r + γv(s') - v(s)]
• 장점: Online 학습, Low variance
• 단점: Biased (편향 있음), 수렴 조건 까다로움
• 예시: 한 스텝만 가보고 바로 예측 업데이트

Model-free의 핵심: 실제 경험 데이터로 벨만 방정식을 근사적으로 풀기

9.3 대규모 문제를 위한 근사 방법

동기: "상태가 백만 개인데 어떻게 테이블로 저장하지?"

Function Approximation

문제: 상태 수가 10^6 이상이면 table 방식 불가능

해결책: 가치 함수를 함수로 근사

• Linear: v(s) ≈ θᵀφ(s) (feature의 가중합)
• Neural Network: v(s) ≈ NN(s; θ) (딥러닝)

장단점:

• Linear: 빠르고 수렴 보장, 하지만 표현력 제한
• Non-linear: 표현력 좋지만 수렴 보장 어려움
• Deep RL: 복잡한 환경에서 성공, 하지만 불안정

차원 축소 방법들

• Feature Engineering: 중요한 특징만 추출
• 계층적 강화학습: 큰 문제를 작은 문제들로 분할
• State Abstraction: 비슷한 상태들을 묶어서 처리

10. 정리: 이론에서 실제로

10.1 MDP의 계층 구조

1. Markov Property → 기본 가정
2. Markov Process → 상태 전이만
3. Markov Reward Process → 보상 추가 → "어떤 상태가 좋은가?"
4. Markov Decision Process → 의사결정 추가 → "어떻게 행동해야 하는가?"

10.2 문제 해결의 흐름

1. Prediction: "주어진 정책이 얼마나 좋은가?" → Bellman Expectation
2. Control: "가장 좋은 정책은 무엇인가?" → Bellman Optimality
3. Implementation: "실제로 어떻게 풀 것인가?" → RL 알고리즘들

10.3 이론과 실제의 간극을 메우는 방법들

완벽한 이론 (벨만 방정식)
      ↓
실제 한계들 (계산복잡도, 모델 무지, 대규모 공간)
      ↓  
해결 방법들 (DP, Model-free, Function Approximation)
      ↓
현대 강화학습 알고리즘들

 

10.4 핵심 통찰

• Bellman 방정식은 "현재 = 즉시 + 할인된 미래"의 구조
• 최적성은 탐욕적 선택으로 달성 가능
• 이론은 방향을 제시하고, 실제 방법들은 근사적으로 구현

10.5 MDP에서 실제 RL로

1. Model-free: 환경과 상호작용하며 학습
2. Function Approximation: 큰 상태 공간 처리
3. Online Learning: 실시간 개선
4. Generalization: 미경험 상태 처리

10.6 현대 강화학습의 도전

• Sample Efficiency: 적은 경험으로 빠른 학습
• Transfer Learning: 다른 환경으로 지식 전이
• Multi-agent: 여러 에이전트가 동시에 학습
• Partial Observability: 불완전한 관측 환경
• Continuous Control: 연속적 행동 공간
• Safety: 학습 중 안전성 보장

10.7 실무 팁

• 간단한 환경부터: Gridworld → Cartpole → Atari
• 시각화: 가치 함수와 정책을 그래프로 확인
• 하이퍼파라미터: 할인율부터 신중하게 선택
• 디버깅: 이론적 예상과 실제 결과 비교

MDP는 강화학습의 수학적 기초이며, 실제 알고리즘들은 모두 이 이론에서 출발함. **"왜 이 개념이 필요한가?"**부터 시작해서 자연스럽게 벨만 방정식에 도달하고, **"이론은 좋은데 실제로는 어떻게?"**라는 질문으로 구체적 해결 방법들까지 연결되는 것이 핵심임.

+) 용어

• Trajectory
  • 에이전트는 이따금 자신의 상태에 따른 보상(reward)을 받는다. 에이전트가 지나온 일련의 상태와 행동을 궤적(trajectory)이라고도 한다. 에이전트가 상태에서 보상을 받았다고 할 때, 이 보상으로 이끈 궤적은 S_0,a_0,S_1,a_1,S_2가 된다.
• Rollout
  • 데이터 transition {(s,a,s',r)}을 얻기 위해 에이전트와 환경이 1번(or n번) 상호작용 하는 것(sample)을 의미한다. trajectory의 경우 한 에피소드 전체를 바라보고, reward가 포함되어 있지 않지만, Rollout은 한번의 상호작용을 하고, reward를 포함한다.