arXiv:2610.13692v1 cs.LG

분산 감소 정책 그래디언트는 거의 미니맥스-최적이다

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Leonardo Cesani, Matteo Papini, Marcello Restelli

제출 2026-10-09

한국어 초록

표준 정책 그래디언트(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)임을 확인해 준다.

원문 초록

Standard Policy Gradient (PG) algorithms suffer from high estimation variance because they rely on Monte Carlo updates. While off-policy variance reduction mitigates this problem, establishing optimal sample complexity currently requires either restrictive assumptions, such as uniformly bounded importance weights, or impractical second-order operations. In this work, we introduce Loopless Variance-Reduced PG (LVR-PG), a unified theoretical framework that abstracts a class of first-order estimators that integrate recursive updates with defensive importance sampling, including known estimators such as PAGE-PG and STORM-PG. We prove that this algorithmic class achieves $\tilde{\mathcal{O}}(ε^{-2})$ last-iterate global convergence under weak gradient domination for general parametric policies. We establish this guarantee using purely first-order updates, with minimal assumptions and without gradient preconditioners. By extending state-of-the-art lower bounds to continuous parametric policies, we establish an $Ω(ε^{-2})$ sample complexity limit, confirming our framework is minimax-optimal up to logarithmic factors and horizon terms.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.13692v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.22982v1cs.LG공통 태그 Reinforcement Learning, Stochastic Optimization, policy gradient

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) 속도를 달성한다.

arXiv:2610.13789v1cs.LG공통 태그 Stochastic Optimization, variance reduction

저비용 예측기를 활용한 무작위 모멘텀 전송

Randomized Momentum Transport with Cheap Predictors

STORM 및 2차 모멘텀(second-order momentum)과 같은 모멘텀(momentum) 방법들은 모멘텀에 전송 보정(transport correction)을 추가하여 그래디언트(gradient)를 추적하며, 이는 반복(iteration)마다 추가적인 오라클(oracle) 호출을 필요로 한다. 본 논문은 확률 $q$로 보정을 평가하고 그렇지 않은 경우 저비용 예측(cheap prediction)을 사용하는 무작위 모멘텀 전송(randomized momentum transport)을 소개하며, 조건부 평균을 보존하는 중요도 가중(importance weighting)을 사용하고 분산에 예측 손실(loss)의 $(q^{-1}-1)$배를 추가한다. 전송 바이어스(bias), 2차 모멘트, 잔차 제어 가정 하에서, 정규화(normalized), 사인(sign), 정확한 스펙트럴(exact spectral, Muon) 방향을 포함한 선형 최소화 오라클(linear minimization oracle, LMO) 업데이트는 단일 그래디언트 초기화(initialization)를 사용하여 고정된 각 $q>0$에 대해 $O(T^{-1/3})$ 정상성(stationarity) 바운드를 유지한다. 정규화되지 않은(unnormalized) STORM의 경우, 그래디언트 차이 노이즈 모듈러스가 평활성 상수를 초과하는 경우에만 (그리고 오직 그 경우에만) 일부 $q<1$이 충분 그래디언트 예산의 선도 계수를 최대 약 $10\%$까지 낮춘다. 온라인 대각 예측기는 후회-수렴(regret-to-convergence) 보장을 허용한다. 오라클 비용이 거의 동일한 조건에서, 보정값의 4분의 1만 조회하는 것은 MNIST1D에서 최종 학습(training) 손실(loss)을 $18$에서 $43\%$까지 낮추고, CIFAR-10에서 헤시안(Hessian)-벡터 전송의 테스트 정확도를 $1.5$포인트 높인다.

arXiv:2610.13871v1cs.LG공통 태그 Reinforcement Learning, Stochastic Optimization

영차 잔차 추적을 통한 부분 정보 확률적 최적화

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)의 도함수가 없는 방법 중 가장 뛰어난 성능을 보입니다.

arXiv:2609.35698v3cs.LG공통 태그 Reinforcement Learning, sample complexity

정규화의 입증 가능한 이점: 적대적 모방 학습을 위한 빠른 수렴률

Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning

우리는 적대적 모방 학습(adversarial imitation learning, AIL)을 연구한다. AIL에서 에이전트(agent)는 전문가(expert) 행동과 학습자(learner) 행동을 구별하는 적대적 보상(reward)에 대해 정책(policy)을 최적화함으로써 전문가의 시연(demonstration)을 모방하는 법을 학습한다. 역사적으로 보상 정규화(regularization)와 엔트로피 기반 정책 정규화는 GAIL, LS-IQ와 같이 경험적으로 성공을 거둔 방법들의 핵심 구성 요소였지만, 유한 샘플(finite-sample) 환경에서의 이점은 아직 충분히 탐구되지 않았다. 우리는 일반적인 함수 근사(function approximation)를 사용하는 유한 구간(finite-horizon) 마르코프 결정 과정(Markov decision process)에서 공동으로 정규화된 AIL에 대한 빠른 수렴률을 도출한다. 우리의 모델 프리(model-free) 알고리즘인 Dually Regularized AIL은 KL 정책 정규화와 전문가 및 학습자의 점유율(occupancy)로 가중된 2차(quadratic) 보상 페널티를 결합한다. K개의 온라인 에피소드와 N개의 전문가 경로(trajectory)가 주어졌을 때, 고정된 정규화 파라미터에 대해 정규화된 모방 격차(imitation gap)에 대한 $\widetilde{O}\left(\frac{1}{K}+\frac{1}{N}\right)$ 경계(bound)를 증명한다. 우리의 분석은 유한한 전문가 데이터와 확률적(stochastic) 학습자 피드백으로 인한 추정 오차를 제어하기 위해 일반적인 컨벡스(convex) 보상 클래스에 대한 온라인 미러 디센트(mirror descent) 구성과, 낙관적(optimistic) KL 정규화 정책 학습에 대한 정교한(sharp) 분석을 결합한다. 우리가 아는 한, Dually Regularized AIL은 확률적 전문가(stochastic expert)가 존재하는 경우에도 이러한 정규화된 AIL 목적함수에 대해 전문가 시연과 온라인 상호작용(interaction) 양쪽 모두에서 $\widetilde{O}\left(\frac{1}ε\right)$ 샘플 복잡도(sample complexity)를 동시에 달성한 최초의 알고리즘이다. 이러한 결과는 AIL에서 보상 정규화와 정책 정규화가 갖는 상호 보완적인 통계적 이점을 엄밀하게 규명한다.

arXiv:2609.24174v1cs.AI공통 태그 Reinforcement Learning, policy gradient

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 구현을 이상적인 정책 그래디언트 추정량과 구별합니다. 이 예비 보고서는 방법론, 증명, 정확한 유한 모델 감사 및 통제된 평가 프로토콜을 제공하며, 언어 에이전트 벤치마크에서의 경험적 우수성은 주장하지 않습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.