한국어 초록
강화학습(RL)에서 준최적(nearly optimal) 가치 함수를 계산하기 위한 가치 반복(value iteration) 형태의 방법들은 광범위하게 연구되어 왔다. 생성 모델(generative model) 샘플링 환경에서 이러한 방법들은 특히 할인율(discount factor)에 대한 의존도 측면에서 정책 최적화(policy optimization) 접근법보다 더 우수한 샘플 복잡도(sample complexity)를 달성할 수 있다. 실제로는 오프라인 학습(offline training)에 주로 사용된다. 본 논문에서는 상태 공간 S, 행동 공간 A, 할인율 $\gamma\in(0,1)$ 및 $[0,1]$ 범위의 비용을 갖는 할인된 마르코프 결정 과정(discounted Markov decision process)을 고려한다. 우리는 볼록 최적화(convex optimization)의 미러 하강법(mirror descent)을 고전적인 가치 반복 프레임워크에 통합한 새로운 가치 최적화 방법인 가치 미러 하강법(value mirror descent, VMD)을 도입한다. 전이 커널(transition kernel)을 알고 있는 결정론적 환경에서 VMD가 선형 수렴함을 보인다. 생성 모델을 갖는 확률적 환경을 위해, 확률적 가치 반복 형태의 방법에서 흔히 사용되는 분산 감소(variance reduction) 기법을 통합한 확률적 변형인 SVMD를 개발한다. 일반적인 볼록 정규화 항을 갖는 강화학습 문제에 대해, SVMD는 $\tilde{O}(|S||A|(1-\gamma)^{-3}\epsilon^{-2})$의 최적에 가까운 샘플 복잡도를 달성한다. 나아가, 모델 오지정(model misspecification)이 존재하는 경우에도 생성된 정책과 최적 정책 사이의 브레그만 다이버전스(Bregman divergence)가 반복(iteration) 전반에 걸쳐 유계(bounded)로 유지됨을 규명한다. 이 특성은 기존의 확률적 가치 반복 형태의 방법들에는 없지만, 오프라인 학습 이후 효과적인 온라인(지속) 학습(online/continual learning)을 가능하게 하는 데 중요하다. 강볼록(strongly convex) 정규화 항 하에서 SVMD는 $\tilde{O}(|S||A|(1-\gamma)^{-5}\epsilon^{-1})$의 샘플 복잡도를 달성하여 고정밀 영역에서의 성능을 향상시킨다. 또한, 생성된 정책이 최적 정책으로 수렴함을 증명한다. 종합적으로 제안된 방법과 그 분석, 그리고 이에 따른 이론적 보장은 강화학습 및 최적화 분야 문헌에 새로운 기여를 제시한다.
원문 초록
Value iteration-type methods have been extensively studied for computing a nearly optimal value function in reinforcement learning (RL). Under a generative sampling model, these methods can achieve sharper sample complexity than policy optimization approaches, particularly in their dependence on the discount factor. In practice, they are often employed for offline training. In this paper, we consider discounted Markov decision processes with state space S, action space A, discount factor $\gamma\in(0,1)$ and costs in $[0,1]$. We introduce a novel value optimization method, termed value mirror descent (VMD), which integrates mirror descent from convex optimization into the classical value iteration framework. In the deterministic setting with known transition kernels, we show that VMD converges linearly. For the stochastic setting with a generative model, we develop a stochastic variant, SVMD, which incorporates variance reduction commonly used in stochastic value iteration-type methods. For RL problems with general convex regularizers, SVMD attains a near-optimal sample complexity of $\tilde{O}(|S||A|(1-\gamma)^{-3}\epsilon^{-2})$. Moreover, we establish that the Bregman divergence between the generated and optimal policies remains bounded throughout the iterations, even under the presence of model misspecification. This property is absent in existing stochastic value iteration-type methods but is important for enabling effective online (continual) learning following offline training. Under a strongly convex regularizer, SVMD achieves sample complexity of $\tilde{O}(|S||A|(1-\gamma)^{-5}\epsilon^{-1})$, improving performance in the high-accuracy regime. Furthermore, we prove convergence of the generated policy to the optimal policy. Overall, the proposed method, its analysis, and the resulting guarantees, constitute new contributions to the RL and optimization literature.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2604.06039v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
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)의 실용적 배치를 향한 구체적인 진전을 이룹니다.
시간적 근접성을 넘어서: 강화학습에서의 신용 할당을 위한 설명적 월드 모델
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)을 제공할 수 있음을 시사한다.
분산 감소 정책 그래디언트는 거의 미니맥스-최적이다
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)임을 확인해 준다.
Dream to Remember: 월드 모델을 활용한 범용 로봇 정책의 지속적 스티어링
Dream to Remember: Continual Steering of Generalist Robot Policies with World Models
범용 로봇 정책(generalist robot policy)은 모방 학습(imitation learning)으로 학습되며, 시연(demonstration)의 품질과 범위에 의해 제한된다. 강화학습은 정책 가중치를 미세조정하거나, 고정된(frozen) 생성형 정책의 입력 노이즈를 조정(steer)하는 작은 모듈을 학습시킴으로써 이를 개선하고 확장할 수 있다. 태스크가 순차적으로 주어질 때, 두 접근 방식 모두 치명적 망각(catastrophic forgetting)을 겪는다. 한 태스크에 대한 미세조정은 이전 태스크의 성능을 저하시키며, 스티어링 방식은 망각을 공유 스티어링 모듈로 옮길 뿐이다. 우리는 고정된 범용 정책을 새로운 태스크로 지속적으로 스티어링하면서도 이전에 습득한 능력을 유지하는 Dream to Remember(D2R)를 제안한다. 스티어링 모듈이 새로운 태스크를 학습하는 동안, 고정된 사전학습 월드 모델(world model)이 상상된 롤아웃(imagined rollout)을 통해 이전 태스크를 리허설(rehearse)함으로써, 리플레이 버퍼나 새로운 데이터 없이도 모듈을 이전 행동에 고정(anchor)시킨다. 월드 모델이 충분히 충실할 경우, D2R은 새로운 태스크를 전적으로 상상(imagination) 속에서 학습한다. 그렇지 않은 경우, 월드 모델은 이전 태스크를 리허설하는 데에만 사용하면서 새로운 태스크는 환경에서 직접 학습한다. CALVIN에서 D2R은 여덟 개의 태스크를 순차적으로 전적으로 상상 속에서 개선하여 평균 성공률을 63.7%에서 74.8%로 끌어올렸으며, 동일한 시퀀스에 대한 LoRA 미세조정은 성공률을 11.7%로 떨어뜨렸다. 고정된 기성(off-the-shelf) 범용 정책과 월드 모델인 π0와 A2World를 사용하여, D2R은 환경에서 보지 못한 LIBERO-90 태스크를 학습하면서도 π0가 미세조정되었던 LIBERO 스위트에서의 성능을 유지하는데, 이는 월드 모델이 정책 최적화에는 충분히 정확하지 않은 경우에도 가능하다. 마지막으로, 실제 Franka 로봇에서 D2R은 세 개의 태스크를 순차적으로 전적으로 상상 속에서 개선하면서도 이전에 이루어진 개선을 유지한다.
영차 잔차 추적을 통한 부분 정보 확률적 최적화
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)의 도함수가 없는 방법 중 가장 뛰어난 성능을 보입니다.
비동기 Q-러닝에 대한 도달 시간 경계
Hitting-Time Bounds for Asynchronous Q-Learning
우리는 유한 마르코프 결정 과정(Markov decision process)의 단일 궤적(trajectory)으로부터 표준 비동기 Q-러닝의 마지막 반복값(last iterate)을 연구한다. 이 궤적은 상태-행동 연쇄(state-action chain)가 기약적(irreducible)이고 주기적(periodic)일 수 있는 고정된 행동 정책(behavior policy)을 따른다. 할인율(discount factor) $γ$에 대해 $H=(1-γ)^{-1}$로 표기하고, $μ_{\min}$을 최소 정상 상태-행동 확률(stationary state-action probability), $\mathfrak h_\star$를 역방향 상태-행동 연쇄의 최대 기대 적중 시간(hitting time)으로 정의한다. 우리는 $0<\varepsilon\le1$에 대해, 상수 스텝 크기(step size)를 사용하는 0으로 초기화된 Q-러닝이 $\widetilde{O}(H^4/(μ_{\min}\varepsilon^2)+\mathfrak h_\star)$개의 전이(transition)를 사용하여 높은 확률로 최대 $\varepsilon$의 sup-노름(sup-norm) 오차를 달성함을 증명한다. 통계적 항은 표준 Q-러닝의 4차 유효 지평(effective horizon) 의존성을 그대로 유지하며, 초기화 비용은 $\mathfrak h_\star$에 가산적으로 더해진다. 비주기적(aperiodic) 행동 연쇄의 경우, 혼합 시간(mixing time)과의 비교를 통해 $\widetilde{O}(t_{\mathrm{mix}}/μ_{\min})$의 과도 항(transient term)을 얻는다. 경험적 상태-행동 카운트 규칙(empirical state-action count rule)은 이후의 학습 실행(training run)을 위한 상수 스텝 크기를 선택하며, 모델 매개변수, 목표 정확도, 신뢰 수준에 대한 사전 지식 없이도 동일한 비율을 달성한다. 출력값은 마지막 학습 반복값이며, 두 단계 모두 샘플 수에 포함된다. 증명은 두 개의 결정론적 벨만 외피(Bellman envelope)를 사용하여 통계적 오차와 고정 정책 초기화 오차를 분리하며, TD 학습(TD learning)의 역시간 적중 비용 보정(reverse-time hitting-cost compensation)을 상태-행동 전파(state-action propagation)에 맞게 적용한다. 임의의 예측 가능한(predictable) 스텝 크기에 대해 탐험(exploration) 하한이 성립한다. 기존의 통계적 하한 및 파일럿으로 선택된 상수 스텝으로의 확장과 결합하면, 명시된 대규모 샘플 매개변수(parameter) 클래스에서 로그 인자(logarithmic factor)까지 일치하는 평균제곱 비율(mean-square rate)을 얻는다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.