루프를 MDP로 보기

루프를 수학으로 말하기

에이전틱 루프는 직관적으로는 명확하다. 관찰하고, 생각하고, 행동하고, 다시 관찰한다. 그런데 이 루프를 개선하려면 — 어떤 행동이 좋았는지, 어떤 프롬프트가 더 나은 결과를 냈는지 — 더 정밀한 언어가 필요하다. 강화학습(reinforcement learning, RL)이 수십 년에 걸쳐 발전시킨 마르코프 결정 과정(Markov Decision Process, MDP) 이 바로 그 언어다.

MDP는 다섯 가지 요소의 튜플 (S, A, T, R, γ)로 정의된다. 에이전틱 루프에 대응시키면 다음과 같다.

┌─────────────────────────────────────────────────────────────────┐
│               에이전틱 루프 ↔ MDP 매핑                            │
├──────────────────┬──────────────────────────────────────────────┤
│ MDP 요소         │ 에이전틱 루프에서의 대응                        │
├──────────────────┼──────────────────────────────────────────────┤
│ S  상태 공간      │ 파일시스템, DB, 외부 API 등 실제 세계 상태      │
│ O  관찰 공간      │ 모델이 받는 컨텍스트 창 (tool result 포함)      │
│ A  행동 공간      │ 도구 호출, 코드 실행, 메시지 출력               │
│ T  전이 함수      │ 도구 실행 결과 + 환경 변화                      │
│ R  보상 함수      │ 테스트 통과/실패, LLM 판사 점수, 사용자 승인    │
│ π  정책          │ LLM + 시스템 프롬프트 + 온도·샘플링 설정        │
│ γ  할인율         │ 미래 보상에 대한 현재 가중치                    │
└──────────────────┴──────────────────────────────────────────────┘

그런데 실제 에이전틱 환경은 순수한 MDP가 아니라 POMDP(Partially Observable MDP, 부분 관찰 가능 마르코프 결정 과정) 에 가깝다. 모델은 세계의 완전한 상태 S를 볼 수 없고, 컨텍스트 창이라는 필터를 거친 관찰 O만 받는다. 파일이 디스크에 있어도 read_file을 호출하기 전까지는 보이지 않는다. 이 부분 관찰 가능성이 에이전트 설계를 복잡하게 만드는 핵심 원인 중 하나다.

두 층위의 MDP

에이전틱 루프에는 시간 척도가 다른 두 층위의 MDP가 중첩되어 있다.

외부 루프 MDP (에이전트 이터레이션 레벨)
  ┌──────┐  행동·관찰  ┌──────┐  행동·관찰  ┌──────┐
  │ 이터 1│ ──────────▶│ 이터 2│ ──────────▶│ 이터 N│  ···
  └──────┘            └──────┘            └──────┘
         └──────────────────────────────────────┘
                       보상 R (희소)

각 이터레이션 내부: 토큰 레벨 MDP
  ┌────┐   ┌────┐   ┌────┐   ┌────┐
  │ t₁ │──▶│ t₂ │──▶│ t₃ │──▶│ tₙ │  (수백~수천 토큰)
  └────┘   └────┘   └────┘   └────┘

외부 루프 MDP: 각 이터레이션(도구 호출 → 결과 수신 → 다음 결정)이 하나의 타임스텝이다. 지평(horizon)은 수십~수백 이터레이션이고, 보상은 작업 완료 시에만 주어지는 경우가 많다.

내부 토큰 MDP: 하나의 모델 응답 생성 자체도 MDP다. 각 토큰 선택이 행동이고, 이전 토큰 시퀀스가 상태다. 행동 공간은 어휘 크기(수만 개 토큰)로 방대하다. GRPO, PPO 같은 RL 알고리즘은 이 내부 MDP의 정책을 직접 최적화한다(11-5절).

루프 엔지니어로서 우리가 주로 다루는 것은 외부 루프 MDP다. 모델 가중치를 학습시키는 것이 아니라, 루프 구조·프롬프트·도구 집합을 설계함으로써 정책 π(= LLM + 시스템 프롬프트)를 암묵적으로 형성한다.

희소 보상과 신용 할당 문제

MDP로 보는 순간 즉시 드러나는 핵심 난제가 있다. 보상이 희소(sparse)하다.

코딩 에이전트의 예를 들면, 에이전트가 50번의 도구 호출 끝에 테스트를 통과하면 보상 +1을 받는다. 그러나 어느 행동이 성공에 기여했고 어느 행동이 역효과를 냈는지 알 수 없다. 이것이 **신용 할당 문제(credit assignment problem)**다.

이터레이션:  1   2   3  ···  20  21  22  ···  49  50
행동:       📝  🔍  ✏️  ···  ✅  ❌  🔄  ···  🐛  ✅
보상:        0   0   0  ···   0   0   0  ···   0  +1
                                                   ↑
                              50번 중 어느 행동 덕분인가?

희소 보상에 대한 현실적인 대응 전략은 두 가지다.

전략 A — 단계 보상(dense reward) 추가: 각 이터레이션마다 LLM 판사 점수, 린트 에러 변화, 테스트 커버리지 등 중간 신호를 보상으로 활용한다. 신용 할당이 쉬워지지만 보상 해킹(reward hacking) 위험이 높아진다 — 에이전트가 실제 작업 대신 보상 프록시를 최적화하기 시작한다(8-2절).

전략 B — 결과 기반 평가만 사용: 최종 상태(테스트 통과/실패)만 평가하고, 신용 할당은 GRPO 같은 알고리즘에 위임한다(11-5절). 보상 신호를 단순·명확하게 유지하는 대신 충분한 샘플이 필요하다. DeepSeek-R1-Zero가 이 전략으로 순수 RL만으로 추론 능력을 창발시킨 것이 대표적 사례다.

MDP 관점이 루프 엔지니어에게 주는 체크리스트

이 형식화는 철학적 운동이 아니라 실용적 설계 도구다. 루프를 설계할 때 다음 질문들로 바꿔 쓸 수 있다.

MDP 요소	설계 질문
상태·관찰	에이전트가 작업 완료에 필요한 정보를 볼 수 있는가? 어떤 도구로 숨겨진 상태를 노출하는가?
행동 공간	도구 집합이 너무 크지 않은가? 탐색 공간이 합리적인가?
전이 함수	도구 실행 실패, 타임아웃, 빈 결과를 어떻게 처리하는가?
보상 함수	성공을 기계적으로 검증할 수 있는가? 보상 해킹 경로가 없는가?
정책	시스템 프롬프트, 도구 설명, 예시가 원하는 행동을 충분히 안내하는가?
지평	작업을 완료하기에 충분한 이터레이션 한도를 설정했는가?

다음 챕터에서는 이 MDP 관점을 가장 실용적으로 구현한 첫 번째 프레임워크인 DSPy를 살펴본다. DSPy는 프롬프트(= 정책의 일부)를 컴파일러가 자동으로 최적화하게 함으로써 루프의 ‘정책 설계’ 부담을 줄인다.