[Paper] 모델 기반 강화 학습 in Discrete-Action Non-Markovian Reward Decision Processes

Source: arXiv - 2512.14617v1

Overview

이 논문은 QR‑MAX를 소개한다. QR‑MAX는 보상이 현재 상태뿐만 아니라 전체 행동 이력에 의존하는 작업을 처리할 수 있는 모델 기반 강화 학습 알고리즘이다. 전이 학습을 reward machines를 통해 보상 이력 처리와 분리함으로써, 저자들은 다항식 샘플 복잡도로 증명 가능한 근접 최적성을 달성했으며, 이 아이디어를 연속 상태 문제에 적용한 Bucket‑QR‑MAX까지 확장한다.

주요 기여

• 이산 행동 NMRDP를 위한 최초의 PAC‑보장 모델‑기반 RL 알고리즘 – QR‑MAX는 필요한 샘플 수에 대한 증명 가능한 경계를 갖는 최적 정책을 학습합니다.
• 보상 머신을 통한 팩터화 – 비‑마코프 보상 요소를 마코프 동역학으로부터 분리하여 학습 및 분석을 단순화합니다.
• 연속 상태 공간으로의 확장 – Bucket‑QR‑MAX는 SimHash‑기반 이산화를 사용하여 손수 만든 그리드나 신경망 근사 없이도 팩터화된 구조를 유지합니다.
• 실증 검증 – 점점 복잡해지는 벤치마크에서 선도적인 모델‑기반 베이스라인에 비해 우수한 샘플 효율성과 견고성을 입증합니다.

Methodology

1. Reward Machines (RMs) – 시간적 보상 사양(예: “A를 방문한 뒤 5스텝 이내에 B를 방문”)을 인코딩하는 유한 상태 자동화. RM은 보상 계산에 필요한 히스토리를 추적하고, 기본 환경은 마코프성을 유지합니다.

2. QR‑MAX Core

   • Transition Model: 표준 테이블 추정기(카운트 → 경험적 확률)로 학습됩니다.
   • Reward Model: RM에 의해 관리되며, 각 RM 상태마다 자체 보상 분포를 갖고 전이 모델과는 독립적으로 학습됩니다.
   • Planning: 고전적인 Q‑learning with MAX의 변형을 사용합니다(이름 그대로). 전이 모델에 대한 Q값을 업데이트하고 RM을 통해 보상을 전파하는 과정을 번갈아 수행합니다.

3. Bucket‑QR‑MAX for Continuous States

   • 고차원 연속 관측을 이산 “버킷”으로 매핑하기 위해 SimHash를 적용합니다.
   • 해시 함수는 지역 민감성을 가지고 있어 유사성을 보존하므로, 인접한 상태들이 동일한 버킷을 공유하게 되어 팩터화된 학습 파이프라인을 유지합니다.

전체 파이프라인은 간단합니다: 경험을 수집 → 전이 카운트 업데이트 → RM 보상 업데이트 → Q값 재계산 → 탐욕적으로 행동.

결과 및 발견

• 샘플 효율성: QR‑MAX는 최고의 모델 기반 경쟁자보다 5‑10배 적은 환경 상호작용으로 거의 최적에 가까운 성능을 달성합니다.
• 견고성: 팩터화된 접근 방식은 보상 이력 정보를 망각하는 재앙적 현상을 방지하여 무작위 시드 전반에 걸쳐 더 안정적인 학습 곡선을 제공합니다.
• 확장성: Bucket‑QR‑MAX의 해시 기반 이산화는 그리드 해상도를 수동으로 조정할 필요 없이 연속 도메인에 확장됩니다.

실용적인 시사점

• Production RL에서의 Temporal Logic: 엔지니어는 복잡한 작업 사양(예: “프로세스 A는 B보다 먼저, 마감 시간 내에 완료되어야 함”)을 직접 학습 루프에 삽입할 수 있으며, 수작업 보상 설계가 필요하지 않습니다.
• 데이터 수집 비용 감소: PAC 보장은 목표 성능을 달성하기 위해 필요한 에피소드 수를 추정할 수 있게 해주며, 비용이 많이 드는 시뮬레이션이나 실제 로봇 분야에 유용합니다.
• 플러그‑앤‑플레이 통합: QR‑MAX는 기존의 모델 기반 플래너와 모두 호환되며, 추가로 필요한 구성 요소는 고수준 사양(예: LTL 공식)에서 생성할 수 있는 보상 머신뿐입니다.
• 연속 상태 응용: Bucket‑QR‑MAX는 빠르고 안정적인 학습이 필요할 때(예: 엣지 디바이스, 저지연 제어 루프) 딥 함수 근사기 대신 사용할 수 있는 경량 대안을 제공합니다.

제한 사항 및 향후 연구

• 이산‑행동 가정: 현재 이론과 보장은 유한 행동 집합에 대해 성립하며, 연속 행동으로 확장하려면 추가 분석이 필요합니다.
• 보상 기계 구축: 논문에서는 RM을 수작업으로 만드는 방법을 제시하지만, 자연어 또는 고수준 사양으로부터 자동 합성하는 것은 아직 해결되지 않은 과제입니다.
• 해시 버킷의 확장성: 매우 고차원 공간에서는 해시 충돌이 성능을 저하시킬 수 있으며, 적응형 해싱이나 하이브리드 신경‑해시 방식을 향후 방향으로 제안합니다.

저자

• Alessandro Trapasso
• Luca Iocchi
• Fabio Patrizi

논문 정보

• arXiv ID: 2512.14617v1
• 분류: cs.LG, cs.AI
• 출판일: 2025년 12월 16일
• PDF: Download PDF