arXiv:2605.06866v3 cs.LG

비동기 범주형 분포 시차 학습을 위한 정밀한 유한 반복 이론

A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning

Ege C. Kaya, Abolfazl Hashemi

제출 2026-05-07

저자 비고

arXiv Comments

68 pages, 3 figures

한국어 초록

본 논문에서는 크라메르(Cramér) 기하에서의 스칼라 범주형 TD(CTD)와 최대 평균 불일치(MMD) 기하에서의 다변량 부호 범주형 TD(MTD)를 포괄하여, 비동기 범주형 분포 시차 학습(distributional temporal-difference) 방법의 유한 반복(finite-iteration) 거동을 연구한다. 저자들은 i.i.d. 샘플링 및 연속적인 마르코프 궤적 하에서 높은 확률의 이론적 보장을 확립한다. CTD의 경우, 분산 감소나 데이터 삭제 기법을 사용하지 않고도 실제 반환 분포에 도달하기 위한 크라메르 표본 복잡도의 주요 항이 i.i.d. 설정에서는 $\tilde O(ρ_{\min}^{-1}(1-γ)^{-2}\varepsilon^{-2})$, 마르코프 설정에서는 $\tilde O(μ_{\min}^{-1}(1-γ)^{-2}\varepsilon^{-2}+μ_{\min}^{-1}t_{\mathrm{mix}})$임을 보인다. MTD의 경우, MMD 표본 복잡도의 주요 항은 $\tilde O(ρ_{\min}^{-1}(1-γ)^{-1-c}\varepsilon^{-2})$ 및 $\tilde O(μ_{\min}^{-1}(1-γ)^{-1-c}\varepsilon^{-2}+μ_{\min}^{-1}t_{\mathrm{mix}})$이며(여기서 $c\in(0,2)$는 MMD 커널의 동차 지수), 이는 $c=1$일 때 CTD 수렴 속도로 단순화된다. 이는 저자들이 알기로 MTD에 대한 최초의 유한 반복 수렴 속도이다. 무할인 고정 지평(undiscounted fixed-horizon) 정책 평가의 경우, 동일한 분석이 i.i.d. 및 에피소딕 샘플링 하의 CTD와 MTD 고정 지평 버전에 적용되며, 유효 지평 $(1-γ)^{-1}$이 주요 항에서 지평 $H$로 대체되어 할인 설정의 수렴 속도와 일치한다. 일치하는 미니맥스(minimax) 하한은 주요 항과 내포된 1-바서슈타인(Wasserstein) 속도가 i.i.d., 마르코프, 에피소딕 샘플링 하에서 최적임을 보여준다. 종합적으로 이러한 결과들은 스칼라, 다변량, 할인 및 고정 지평 설정 전반에 걸쳐 비동기 범주형 분포 TD에 대한 통합된 비점근적(non-asymptotic) 분석을 제공하며, 주요 항에서 미니맥스 최적의 수렴 속도를 달성한다.

원문 초록

We study finite-iteration behavior of asynchronous categorical distributional temporal-difference methods, covering scalar categorical TD (CTD) in the Cramér geometry and multivariate signed-categorical TD (MTD) in the maximum mean discrepancy (MMD) geometry. We establish high-probability guarantees under i.i.d. sampling and under a continuing Markovian trajectory. For CTD, the Cramér sample complexity to the true return law has leading term $\tilde O(ρ_{\min}^{-1}(1-γ)^{-2}\varepsilon^{-2})$ in the i.i.d. and $\tilde O(μ_{\min}^{-1}(1-γ)^{-2}\varepsilon^{-2}+μ_{\min}^{-1}t_{\mathrm{mix}})$ in the Markovian setting, without using variance reduction or data dropping. For MTD, the MMD sample complexity has leading terms $\tilde O(ρ_{\min}^{-1}(1-γ)^{-1-c}\varepsilon^{-2})$ and $\tilde O(μ_{\min}^{-1}(1-γ)^{-1-c}\varepsilon^{-2}+μ_{\min}^{-1}t_{\mathrm{mix}})$, where $c\in(0,2)$ is the homogeneity exponent of the MMD kernel, and they reduce to the CTD rates when $c=1$. These are, to our knowledge, the first finite-iteration rates for MTD. For undiscounted fixed-horizon policy evaluation, the same analysis applies to fixed-horizon versions of CTD and MTD under i.i.d. and episodic sampling, and the rates match the discounted ones with the effective horizon $(1-γ)^{-1}$ replaced by the horizon $H$ in the leading term. Matching minimax lower bounds show that the leading terms, and the implied $1$-Wasserstein rates, are optimal under i.i.d., Markovian, and episodic sampling. Together, these results provide a unified non-asymptotic analysis of asynchronous categorical distributional TD across scalar, multivariate, discounted, and fixed-horizon settings, with rates that are minimax optimal in their leading terms.

제출 이력

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

  1. arXiv:2605.06866v3

함께 살펴볼 논문

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

arXiv:2610.13692v1cs.LG공통 태그 Reinforcement Learning, Stochastic Optimization, sample complexity

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

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)임을 확인해 준다.

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:2607.22982v1cs.LG공통 태그 Reinforcement Learning, Stochastic Optimization

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

토론

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