Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes
한국어 초록
자연 정책 그래디언트(NPG)는 신뢰 영역 정책 최적화(Trust Region Policy Optimization) 및 근위 정책 최적화(Proximal Policy Optimization)와 같이 널리 사용되는 방법의 기반이 되는, 잘 정립된 강화학습 알고리즘이며, 이들 방법 모두 강력한 실증적 성공을 보여주었다. 본 논문에서는 동역학이 알려져 있고 수평선 의존적 전이 커널(horizon-dependent transition kernels)을 갖는 유한 수평선 마르코프 결정 과정(Markov Decision Processes)에서 정확한 NPG를 연구한다. 이 설정에서 해당 알고리즘에 대한 최초의 유한 시간 수렴 보장을 제공하며, 상수 및 증가하는 학습률(step size) 체제를 모두 고려한다. 상수 학습률 $η_t=η$에 대해, NPG가 $t$회 반복 후 $\mathcal{O}(H^{2}/t)$의 속도로 아선형(sublinear) 수렴함을 증명한다. 여기서 $H$는 수평선 길이이다. 또한 이 상수 학습률 분석을 전체 지지(full support) 투영 분포 하의 정확한 모집단 투영 오라클(population-projection oracle)에서의 선형 MDP로 확장하여, 테이블(tabular) 설정과 동일한 아선형 속도를 재현한다. 더 나아가 증가하는 학습률에 대해서는, 이 알고리즘이 문제 의존 상수 $\vartheta_ρ> 1$에 대해 $\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)$의 선형 수렴 속도를 달성함을 증명하며, $η_0>0$ 및 $H \geq 2$인 형태 $η_t=η_0(H/(H-1))^t$의 수평선만 의존하는(horizon-only) 강건 스케줄(robust schedule)이 동일한 기하(geometric) 속도를 달성한다.
원문 초록
Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success. In this paper, we study exact NPG in finite-horizon Markov Decision Processes with known dynamics and horizon-dependent transition kernels. We provide the first finite-time convergence guarantees for this algorithm in this setting, for which we consider both constant and increasing step size regimes. With a constant step size $η_t=η$, we prove that NPG converges sublinearly with a rate of $\mathcal{O}(H^{2}/t)$ after $t$ iterations, where $H$ is the horizon length. We also extend this constant step size analysis to linear MDPs in an exact population-projection oracle under a full support projection distribution, recovering the same sublinear rate as in the tabular setting. Furthermore, with increasing step sizes, we prove that this algorithm achieves a linear convergence rate of $\mathcal{O}\left(\left(1-\frac{1}{\vartheta_ρ}\right)^t\right)$ for a problem-dependent constant $\vartheta_ρ> 1$, and the horizon-only robust schedule of the form $η_t=η_0(H/(H-1))^t$ where $η_0>0$ and $H \geq 2$, attains this same geometric rate.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2607.22982v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
분산 감소 정책 그래디언트는 거의 미니맥스-최적이다
Variance-Reduced Policy Gradient is Nearly Minimax-Optimal
표준 정책 그래디언트(Policy Gradient, PG) 알고리즘은 몬테카를로 업데이트에 의존하기 때문에 추정 분산이 높다는 문제를 가진다. 오프-정책 분산 감소(off-policy variance reduction)가 이 문제를 완화하지만, 현재로서는 최적의 샘플 복잡도(sample complexity)를 확립하려면 균일하게 유계인(uniformly bounded) 중요도 가중치(importance weights)와 같은 제한적인 가정이나 비현실적인 2차(second-order) 연산이 필요하다. 본 연구에서는 Loopless Variance-Reduced PG(LVR-PG)를 소개한다. 이는 재귀적 업데이트(recursive update)와 방어적 중요도 샘플링(defensive importance sampling)을 결합한 1차(first-order) 추정량들의 한 클래스를 추상화하는 통합 이론적 프레임워크로, PAGE-PG와 STORM-PG와 같은 기존 추정량들을 포함한다. 우리는 일반적인 파라메트릭 정책(parametric policy)에 대해 약한 그래디언트 지배(weak gradient domination) 조건 하에서 이 알고리즘 클래스가 $\tilde{\mathcal{O}}(ε^{-2})$의 라스트 이터레이트(last-iterate) 전역 수렴(global convergence)을 달성함을 증명한다. 우리는 순수하게 1차 업데이트만을 사용하여, 최소한의 가정 하에 그래디언트 전처리기(gradient preconditioner) 없이 이 보장을 확립한다. 최신 하한(lower bound)을 연속적인 파라메트릭 정책(continuous parametric policy)으로 확장함으로써, 우리는 $Ω(ε^{-2})$의 샘플 복잡도 한계를 확립하며, 이는 로그 인자(logarithmic factor)와 호라이즌(horizon) 항을 제외하면 우리의 프레임워크가 미니맥스 최적(minimax-optimal)임을 확인해 준다.
MEC가 없는 마르코프 결정 과정(MDP)에서의 도달 가능성을 위한 Q-러닝
Q-Learning for Reachability in MEC-Free MDPs
도달 가능성(reachability) 명세를 위한 강화학습(RL)은 순차적 의사결정에서 기본이 되는 문제입니다. 기존 연구에서는 최적 정책으로의 점근적 수렴(asymptotic convergence)을 규명했으나, 이는 기저 마르코프 결정 과정(MDP)의 전이 확률을 명시적으로 추정해야만 하는 모델 기반(model-based) 방식을 통해서만 가능했습니다. 본 논문에서는 표준적인 MEC 몫(quotient) 연산을 통해 모든 MDP가 환원될 수 있는 기본 구성 요소인, 비종단 최대 끝 컴포넌트(non-terminal maximal end components, MEC)가 없는 MDP 단편에서 도달 가능성에 대한 점근적 보장을 제공하는 최초의 모델 프리(model-free) 알고리즘인 Quasar를 제시합니다. 본 알고리즘은 고전적인 Q-러닝 접근법을 따라 시간차(temporal-difference) 업데이트를 활용하여 전이 확률을 전혀 학습하지 않고도 최적 정책으로 수렴합니다. 이를 통해 도출된 학습기는 메모리 사용량을 모델 기반 방식에 필요한 O(|S|^2|A|)에서 O(|S||A|)로 줄입니다. 표준화된 정량 검증 벤치마크 세트(Quantitative Verification Benchmark Set)에서 본 알고리즘은 기존의 최신 모델 기반 기법(SOTA)보다 수 자릿수(orders of magnitude) 적은 샘플만으로 최적 정책에 수렴합니다. 이러한 결과는 도달 가능성 학습의 실질적인 적용과 더불어 명세 유도형 강화학습(specification-guided RL)의 실용적 배치를 향한 구체적인 진전을 이룹니다.
CREDO: 재생-보정된 크레딧 할당을 위한 분산 유도 루브릭 진화
CREDO: Variance-Guided Rubric Evolution for Replay-Corrected Credit Assignment
장기적(Long-horizon) 언어 에이전트는 희소한 최종 피드백을 받는 반면, 중간 루브릭(rubric)은 진행 상황에 대해 구조화되어 있지만 잠재적으로 잘못 명시될 수 있는 평가를 제공합니다. 재설정 가능한 학습 환경에서 반사실적 지속 롤아웃(counterfactual continuation rollout)을 통해 국소적 크레딧을 측정할 수 있지만, 완전한 재생(replay)은 비용이 많이 듭니다. 본 논문에서는 진화하는 의미론적 루브릭과 선택적 실행 기반 크레딧 보정을 결합한 프레임워크인 Credo를 제안합니다. 동결된 판별기(judge)는 가시적인 전이(transition)를 루브릭 특징에 매핑하고, 크레딧 헤드는 실현된 전이와 관련된 기대 최종 보상의 변화를 예측합니다. 독립적으로 샘플링된 양측 재생은 기록된 포함 확률을 사용하여 예측 잔차를 보정합니다. 본 연구는 조건부 비편향성과 두 가지 설계 선택(유지할 루브릭 특징 및 고정된 기대 재생 예산 할당 위치)을 연결하는 분산 분해를 유도합니다. 그 결과로 도출된 기준은 정책-점수 민감도와 누락된 재생 범위로 예측 오차에 가중치를 부여하며, 해당 할당 규칙은 지속 비용까지 추가로 고려합니다. 또한 최종 LOO(leave-one-out) 이점과의 실용적인 혼합을 설명하고, 클리핑 및 토큰 정규화가 적용된 PPO 구현을 이상적인 정책 그래디언트 추정량과 구별합니다. 이 예비 보고서는 방법론, 증명, 정확한 유한 모델 감사 및 통제된 평가 프로토콜을 제공하며, 언어 에이전트 벤치마크에서의 경험적 우수성은 주장하지 않습니다.
검증 가능한 보상을 활용한 강화학습을 위한 분산-최적 상태 리샘플링
Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards
검증 가능한 보상을 활용한 강화학습(RL)은 롤아웃 예산의 상당 부분을 학습 신호를 제공하지 않는 상태에 소비합니다. 본 연구에서는 이를 샘플링 분포 자체에 대한 질문으로 재구성합니다. 즉, 고정된 롤아웃 예산 하에서 어떤 상태 분포가 정책 그래디언트 추정량의 분산을 최소화하는가 하는 점입니다. 이에 대한 해답은 닫힌 형식(closed-form)의 네이만 배분(Neyman allocation), $μ_{\mathrm{var}}^π(s) \propto d^π(s)\,σ_π(s)$으로 도출되며, 이는 GRPO의 그룹 상대적 이점(group-relative advantage)과 자연스럽게 연결되고 외재적으로 부과된 스케줄 없이도 정책이 향상됨에 따라 창발적인 역방향 커리큘럼(reverse curriculum)을 유도합니다. 이러한 원리를 바탕으로, 접두 문맥(prefix) 재생 버퍼와 비용이 들지 않는 분산 프록시를 사용하는 GRPO의 플러그인 수정 기법인 VSR(Variance-driven State Resampling)을 제안합니다. 수학적 추론 벤치마크 및 긴 주기의 에이전트(agentic) 과제(Sokoban, BabyAI)에서 VSR은 업데이트당 생성되는 토큰 수를 줄이면서도 대부분의 벤치마크에서 GRPO 및 GiGPO보다 우수한 성능을 달성합니다.
시간적 근접성을 넘어서: 강화학습에서의 신용 할당을 위한 설명적 월드 모델
Beyond Temporal Proximity: Explanatory World Models for Credit Assignment in Reinforcement Learning
생성형 추천 시스템(Generative Recommenders)은 결정 이후 수백 또는 수천 번의 상호작용이 지난 뒤에야 나타나는 결과를 최적화하기 위해 점점 더 강화학습(Reinforcement Learning, RL)을 활용하고 있다. 표준 강화학습은 명시적인 관련성이 아니라 시간적 근접성에 따라 보상을 전파하며, 이로 인해 멀리 떨어져 있지만 중요한 행동에 할당되는 신호가 약화되고 샘플 비효율성의 원인이 된다. 우리는 설명(explanation)을 사용하여 실현된 결과에 그럴듯하게 기여했을 이전 사건들을 식별하는 귀속(attribution) 프레임워크인 설명적 월드 모델(Explanatory World Models, EWM)을 소개한다. 우리는 프론티어 언어 모델을 사용하여 EWM을 구체화하고, 할인되지 않은 에피소드 리턴(undiscounted episode return)을 보존하면서 보상을 재귀적으로 재분배하는 보수적인 계층적 연산자(hierarchical operator)를 통해 그 설명을 학습 신호로 사용한다. 무엇이 유용한 설명을 구성하는지를 조사하기 위해, 우리는 Halpern의 실제 인과관계(actual causation), Lombrozo의 설명적 단순성(explanatory simplicity), Deutsch의 변형하기 어려운 설명(hard-to-vary explanations)에서 영감을 받은 세 가지 상호 보완적인 변형을 구체화한다. 우리는 두 가지 통제된 장기 호라이즌(long-horizon) 강화학습 벤치마크, 공개된 순차적 추천(sequential-recommendation) 벤치마크, 그리고 산업 규모의 생성형 추천 시스템에서 EWM을 평가한다. Crafter와 WordCraft에서 EWM은 PPO와 LaRe를 크게 상회하며, 보상이 가장 지연될 때 가장 큰 성능 향상을 보인다. KuaiRand에서 EWM은 오프라인에서 SFT와 LaRe를, 온라인에서 A2C를 상회한다. 마지막으로, 산업용 생성형 추천 시스템에 대한 오프라인 평가에서 EWM은 재현율(Recall)을 상당히 개선하고 행동 대리 지표(behavioral proxies)를 증가시킨다. 이러한 결과는 설명이 지연된 결과로부터 학습하기 위한 구조화되고 재사용 가능한 신용(credit)을 제공할 수 있음을 시사한다.
영차 잔차 추적을 통한 부분 정보 확률적 최적화
Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
많은 최적화(optimization) 문제에서는 그래디언트(gradient)의 일부에만 직접 접근할 수 있으며, 나머지 성분은 함수 평가를 통해 추론해야 합니다. 이러한 구조는 수행적 예측(performative prediction), 수행적 강화학습(performative reinforcement learning), 그리고 블랙박스 하위 레벨을 갖는 이단계 최적화(bilevel optimization)에서 발생합니다. 본 논문에서는 사용 가능한 그래디언트 성분과 잔차의 이동 추정치를 결합하는 부분 정보 확률적 최적화(Partially Informed Stochastic Optimization, PISO)를 제안합니다. PISO는 각 영차(zeroth-order) 관측을 이 추정치 중심으로 정렬함으로써, 무작위 탐침으로 인한 분산이 잔차의 크기가 아닌 추적 오차에 의존하도록 만듭니다. 이를 통해 명시적인 수축 메커니즘과 모멘텀(momentum)에 대한 원리적 해석을 갖춘 무작위 스케치 반복(iteration)을 도출합니다. 매끄러운 비볼록 목적 함수에 대해, 접근 불가능한 그래디언트 성분에 대한 균일한 경계를 요구하지 않으면서 잔차의 변동과 초기 크기에 의존하는 수렴(convergence) 보장을 확립합니다. 독립적으로 샘플링된 함수 평가와 가우시안 또는 구면 탐침을 사용할 때, PISO는 립시츠 그래디언트 조건에서 \(O(d^{2}\varepsilon^{-6})\), 추가적인 립시츠 헤시안(Hessian) 가정 하에서는 \(O(d^{2}\varepsilon^{-5})\)의 우수한 함수 평가 복잡도를 달성합니다. 이러한 수렴 속도는 업데이트당 단 하나의 탐침 방향, 두 개의 함수 샘플, 그리고 하나의 기지 성분 샘플만을 필요로 합니다. 또한 본 분석은 배치 처리를 통해 배포 횟수를 줄이는 대신 관측치를 교환하는 방식을 정량화합니다. 다섯 가지 설정 전반에서, PISO 변형들은 세 가지 설정에서 유사한 오라클 접근을 갖는 테스트된 베이스라인 대비 성능을 향상시키고, 이단계 라우팅에서는 유사한 해에 더 빠르게 도달하며, 수행적 강화학습에서는 반응 모델(response-model)의 도함수가 없는 방법 중 가장 뛰어난 성능을 보입니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.