arXiv:2606.24981v1 cs.LG

A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging

Wei-Cheng Lee, Francesco Orabona

제출 2026-06-23

원문 초록

We study linear TD(0) under Markovian sampling, where data are generated along a single trajectory. We provide high-probability guarantees for a plain unprojected TD(0) algorithm with Polyak-Ruppert (PR) averaging, using a single stepsize schedule $η_t \propto \frac{1}{τ_{\mathrm{mix}}\log(t)\sqrt{t}}$ that depends on the mixing time but requires no prior knowledge of the curvature parameter $ω$. Our first result shows that such a choice of the stepsize guarantees that the TD(0) iterates are automatically and uniformly bounded with high probability, without projections and without any stability argument based on $ω$. Building on this result, we establish a simultaneous high-probability convergence guarantee for the PR average: the same stepsize yields both a robust curvature-free $\widetilde{\mathcal{O}}\!\left(\frac{τ_{\mathrm{mix}}}{\sqrt{T}}\right)$ rate and a fast curvature-dependent $\widetilde{\mathcal{O}}\!\left(\frac{τ_{\mathrm{mix}}^2}{ωT}\right)$rate, with the bound taking the minimum of the two. The core technical ingredient is a Poisson-equation toolkit for geometrically mixing Markov chains, which decomposes Markov noise into a martingale term plus a controlled remainder and enables a new self-bounding inductive argument for pathwise stability.

요약

단일 궤적 Markovian 샘플링 하에서 투영(projection) 없는 선형 TD(0)에 Polyak–Ruppert 평균을 적용하고, 혼합 시간에만 의존하는 단일 스텝사이즈로 반복값의 고확률 유계(boundedness)와 동시 수렴을 증명한다. 곡률(curvature) 파라미터 ω를 몰라도 동일 스텝사이즈가 곡률 무관 견고율 Õ(τ_mix/√T)과 곡률 의존 빠른 수렴율 Õ(τ_mix²/(ωT)) 중 더 나은 쪽을 보장하며, 핵심 기법은 기하학적 혼합 Markov chain용 Poisson 방정식 분해와 자기 유계(self-bounding) 귀납 논증이다.

제출 이력

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

  1. arXiv:2606.24981v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2607.23030v1cs.LG공통 태그 Reinforcement Learning, policy evaluation, temporal difference

동적 UBSR 척도를 갖는 MDP의 온라인 정책 평가

Online Policy Evaluation for MDPs with Dynamic UBSR Measures

리스크 인식 강화학습에서 정책 평가를 위한 효율적인 함수 근사(function approximation) 방법을 개발하는 것은 근본적인 과제이다. 기존 접근법은 제한적인 리스크 척도 클래스에만 초점을 맞추거나 시뮬레이터 접근에 의존하여, 완전 온라인 설정에서의 적용 가능성을 제한한다. 본 연구에서는 선형 함수 근사 하에서 동적 유틸리티 기반 쇼트폴 리스크(UBSR) 척도를 갖는 마르코프 결정 과정(MDP)에서의 정책 평가를 위한 계산적으로 효율적인 온라인 학습 알고리즘을 제안한다. 구체적으로, UBSR-TD 알고리즘을 도입하고, 거의 확실(almost surely) 수렴하는 조건을 수립하며, 수렴을 가속하기 위해 설계된 여러 변형을 개발한다. 우리의 공식화는 리스크 중립 MDP에 대한 기존 정책 평가 알고리즘이 시간차(temporal-difference) 오차에 손실 함수를 통합함으로써 동적 UBSR 설정에 쉽게 적응될 수 있음을 보여준다. 수치 실험은 이론적 결과를 뒷받침하며, 유통기한 불확실성을 갖는 부패성 재고 관리 문제에 대한 적용은 제안된 방법의 실용적 효과를 보여준다.

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

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

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:2608.30317v2cs.LG공통 태그 Reinforcement Learning, parameter estimation

링크 흐름 전파 안내 기반 강화학습을 활용한 동적 기종점 통행량 행렬의 온라인 추정

Online Estimation of Dynamic Origin-Destination Matrices Using Reinforcement Learning with Link-Flow Propagation Guidance

동적 기종점(OD, Origin-Destination) 행렬 추정은 관측된 링크 흐름(link flow)을 재현하도록 시뮬레이션을 위한 시변 입력 수요를 보정합니다. 학습된 정책이 단 한 번의 평가(evaluation)만으로 수요를 추정할 수 있기 때문에 강화학습(reinforcement learning)은 온라인 추정에 매우 적합하지만, 변동하는 목표 흐름으로 인해 집계된 보상(aggregate reward) 기반의 학습이 복잡해집니다. 본 연구에서는 시뮬레이션된 차량 전파 기록과 다운스트림 오류를 결합하여 개별 OD 요소를 유도하는 링크 흐름 전파 안내 기반 강화학습(LFPG-RL)을 제안합니다. 멜버른 간선 도로망에서 수집한 250개 평일 링크 흐름 궤적을 사용한 결과, LFPG-RL은 15분 간격당 평균 테스트 평균 제곱근 오차(RMSE) 7.41대, 평균 절대 백분율 오차 31.24%, 피어슨 상관계수 0.987을 달성했습니다. 최적화, 필터링, 그리고 안내가 없는 강화학습과의 비교 결과, 가장 강력한 기준선(baseline)인 전파 안내 기반 경사하강법(gradient descent) 대비 RMSE가 40.1% 감소했습니다. LFPG-RL은 빠른 수요 업데이트를 가능하게 하여 교통 시뮬레이션이 관측된 조건과 일치하도록 유지함으로써 교통 관리 전략의 평가를 지원합니다.

arXiv:2609.26978v1stat.ML공통 태그 Stochastic Optimization, parameter estimation

다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

고정된 알려지지 않은 선형 효용(utility)을 갖는 온라인 역 선형 최적화를 연구한다. 각 라운드에서 환경(environment)은 컴팩트 행동 집합을 제시하고, 학습자(learner)는 그 집합에서 행동(action)을 추천하며, 환경은 동일한 집합 위에서 효용을 최대화하는 행동을 반환한다. 효용 벡터와 행동이 $d$차원 유클리드 단위 구(unit ball) 안에 있을 때, 시간 지평(time horizon)을 알 필요 없이 모든 시간 지평에 대해 기대 후회(regret)---최적 행동 대비 누적 효용 부족분---가 $O(\sqrt d)$인 무작위 알고리즘을 제시한다. $d$에 대한 의존성은 $T\ge d$인 지평에 대한 알려진 $\Omega(\sqrt d)$ 하한에 의해 상수 배수까지 최적이다. 우리 알고리즘은 기하학적으로 간격을 둔 스케일에서 다항식 특징(feature) 공간上的 행렬 곱셈 가중(matrix multiplicative weights)을 유지한다. 선형 프로그램(linear program)을 풀어 추천 분포를 선택하고, 이용 가능한 행동과 피드백 행동을 비교하여 점수 행렬을 갱신한다. 유리수 oracle 출력과 피드백 행동 하에서, 선형 최적화 oracle에 상대적으로 계산 가능한 구현이 $O(\sqrt d)$ 후회 상한을 유지한다. 차원, 지평, 입력 길이에 대해 다항 시간 실행 복잡도로 동일한 rate를 달성할 수 있는지는 열려 있다.

arXiv:2609.27581v1cs.LG공통 태그 Stochastic Optimization, parameter estimation

Step Law는 소규모 언어 모델에도 전이되는가? 59M 파라미터 미만에서의 실증적 재보정

Does Step Law Transfer to Small-Scale Language Models? An Empirical Recalibration Below 59M Parameters

Step Law는 언어 모델 사전학습 시 최적 피크 학습률 η*와 배치 크기 B*에 대한 멱법칙(power-law) 공식을 제공한다. 원 저자들은 59M~1B 파라미터 모델에서 이를 보정했으며, N < 59M인 소규모 모델 영역은 실증적으로 검증한 적이 없다. 이 영역은 단일 GPU 학습, 해석 가능성 연구, 교육용 실험, 메모리·비용상 더 큰 모델을 쓰기 어려운 환경에서 중요하다. 우리는 Step Law가 소규모 언어 모델에도 전이되는지 검증한다. 세 가지 결과를 가정한다. H1: 원래 계수를 그대로 쓸 수 있다. H2: 멱법칙 형태는 유지되나 계수가 다르다. H3: 이 영역에서는 멱법칙이 최적점을 설명하지 못한다. 모든 실험은 2048 토큰 BPE 어휘, AdamW, warmup-cosine 스케줄을 사용하는 단일 nanoGPT/TinyStories 파이프라인에서 수행했다. 각 (N, D) 셀의 최적점은 평활화된 학습 손실에 대해 log-log 좌표에서 국소 이차 근사를 통해 손실 표면 L(η, B)에서 추출했다. 최종 데이터셋은 서로 다른 (N, D) 셀 29개와 분석에 사용 가능한 run 935개를 포함한다. 주 재적합은 작업 구간 4 <= D/N <= 600에서 25개 셀(815 runs)을 사용한다. 풀링 데이터에서는 H2를 채택한다. 함수 형태는 유지되나 계수는 원 논문과 다르다. η*(N, D) = 0.0985 N^(-0.508) D^(0.238) (R^2 = 0.834)와 B*(D) = 3.6 × 10^(-4) D^(0.931) (R^2 = 0.950)를 얻었다. Step Law의 구조적 주장인 B*의 N 비의존성은 재현된다(p = 0.87). 다만 B*가 D에 따라 증가하는 기울기는 원 논문의 거의 2배다. Step Law를 직접 전이하면 최적 학습률을 체계적으로 과대 추정한다. η_SL / η*의 중앙값 비는 약 4.0배이며, 범위는 2.4배에서 6.6배이다.

토론

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