arXiv:2610.13901v1 stat.ML

비동기 Q-러닝에 대한 도달 시간 경계

Hitting-Time Bounds for Asynchronous Q-Learning

Yang Peng

제출 2026-10-09

한국어 초록

우리는 유한 마르코프 결정 과정(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)을 얻는다.

원문 초록

We study the last iterate of standard asynchronous Q-learning from a single trajectory of a finite Markov decision process. The trajectory follows a fixed behavior policy whose state--action chain is irreducible and may be periodic. For discount factor $γ$, write $H=(1-γ)^{-1}$, and let $μ_{\min}$ be the minimum stationary state--action probability and $\mathfrak h_\star$ the largest expected hitting time of the reverse state--action chain. We prove that zero-initialized Q-learning with a constant step size achieves sup-norm error at most $\varepsilon$ with high probability using $\widetilde{O}(H^4/(μ_{\min}\varepsilon^2)+\mathfrak h_\star)$ transitions, for $0<\varepsilon\le1$. The statistical term retains the quartic effective-horizon dependence of standard Q-learning, while initialization cost is additive in $\mathfrak h_\star$. For aperiodic behavior chains, a comparison with mixing time yields a transient term $\widetilde{O}(t_{\mathrm{mix}}/μ_{\min})$. An empirical state--action count rule selects a constant step size for a subsequent training run and attains the same rate without prior knowledge of model parameters, target accuracy, or confidence level. The output is the last training iterate, with both stages included in the sample count. The proof uses two deterministic Bellman envelopes to separate statistical error from fixed-policy initialization error and adapts reverse-time hitting-cost compensation from TD learning to state--action propagation. An exploration lower bound holds for arbitrary predictable step sizes. Together with the existing statistical lower bound and its extension to pilot-selected constant steps, it yields matching mean-square rates up to logarithmic factors on the stated large-sample parameter classes.

제출 이력

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

  1. arXiv:2610.13901v1

함께 살펴볼 논문

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

arXiv:2610.01781v1cs.AI공통 태그 Q-Learning, Sequential Decision Making, markov decision process

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)의 실용적 배치를 향한 구체적인 진전을 이룹니다.

arXiv:2610.10942v2cs.AI공통 태그 Reinforcement Learning (RL), Sequential Decision Making

StoreBench: 자율 운영자 에이전트의 평가 및 학습을 위한 라이브 커머스 환경

StoreBench: A Live-Commerce Environment for Evaluating and Training Autonomous Operator Agents

강화학습(RL) 환경은 이제 사후 학습(post-training)에서 대규모 언어 모델(LLM)의 역량을 향상시키는 주요 수단이 되었으나, 대부분의 에이전트 벤치마크는 여전히 정적입니다. 즉, 에이전트가 행동할 때만 환경이 변화하고, 보상은 최종적인 판정으로 주어지며, 통과 기준은 자의적으로 설정됩니다. 본 논문에서는 에이전트가 프로덕션 수준의 상거래 백엔드에서 중간 규모의 온라인 의류 매장을 운영하며 불확실성 속에서 장기 계획 수립 및 경제적 판단력을 시험받는 라이브 커머스 환경인 StoreBench를 소개합니다. 고객은 24시간 내내 주문하고, 공급업체는 가격을 재책정하거나 공급에 실패하며, 시장 충격은 부분적인 예고만 있거나 예고 없이 발생합니다. 에이전트는 실제 인간 운영자가 사용하는 것과 동일한 29개의 판매자 도구를 통해 행동하며, 취해진 행동의 함수로 시뮬레이션 시간을 계산하는 윈도우 기반 운영 예산 하에서 작동하므로 모델 지연 시간이 시뮬레이션 시간에 영향을 미칠 수 없습니다. 통과 임계값은 스크립트 기반 앵커 정책을 기준으로 보정되었고, 보상은 다양한 보상 해킹 목록에 대비해 강화되었으며, 일련의 행동이 주어지면 모든 에피소드가 동일하게 재현됩니다. 본 연구에서는 추론 노력을 일치시킨 상태에서 세 가지 월드 시드에 걸쳐 30~45일 및 시뮬레이션된 1년 전체에 해당하는 11개 시나리오를 바탕으로 7개의 프론티어 LLM을 평가합니다. 평균적으로 스크립트 기반 스마트 트리아지(smart-triage) 정책에 필적하는 모델은 없었습니다. 최고 성능을 보인 DeepSeek-V4-Pro는 휴리스틱의 97% 대비 49%의 태스크-시드 셀을 통과했습니다. 동일한 도구와 예산을 사용하여 작업한 인간 전문가는 모든 모델보다 높은 점수를 기록했습니다(평균 종합 점수 0.708 대 0.700). Claude Code 하네스 기반의 시뮬레이션된 1년 전체에 걸쳐 대다수 모델은 극적인 성능 향상을 보입니다. GRPO 사후 학습 실행에서 서로 다른 5개의 태스크로만 학습된 Qwen3.5-27B는 홀드아웃(held-out) 평가 태스크에서의 평균 종합 점수를 0.136에서 0.373으로 향상시켰습니다. 본 연구에서는 학습 분할용 예시 태스크 5개, 샘플 궤적 10개, 점수 측정 및 검증 툴링을 공개하며, 벤치마크 오염을 방지하기 위해 전체 환경과 평가 스위트는 비공개로 유지합니다.

arXiv:2610.15888v1cs.LG공통 태그 Reinforcement Learning (RL), Sequential Decision Making

검증 가능한 보상을 활용한 강화학습을 위한 분산-최적 상태 리샘플링

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보다 우수한 성능을 달성합니다.

arXiv:2610.13755v1cs.LG공통 태그 Reinforcement Learning (RL), Sequential Decision Making

LLM 에이전트 학습을 위한 맥락 일치 그룹 정책 최적화

Matched-Context Group Policy Optimization for LLM Agent Training

장기적인(long-horizon) 언어 모델 에이전트를 학습시키려면 희소한 최종 피드백으로부터 중간 결정들에 대한 신용 할당(credit assignment)을 수행해야 합니다. 유한한 형제 롤아웃(sibling rollout) 그룹 내에서 유용한 행동 비교는 해당 행동의 맥락, 두 대안에 대한 증거, 그리고 그 증거가 학습에 어떻게 반영되는지에 따라 달라집니다. 본 연구에서는 이미 수집된 궤적(trajectory)으로부터 가중 행동 선호도를 구축하는 절차인 맥락 일치 그룹 정책 최적화(Matched-Context Group Policy Optimization, MCGPO)를 제안합니다. MCGPO는 행동 전 상태 요약 및 관찰된 루브릭 진행 상황으로 비교 맥락을 정의하며, 이는 작업 규칙에 의해 주석 처리됩니다. 두 행동 지지(two-action support)는 순서화된 정확 및 대략적 매칭 규칙 중에서 선택합니다. 고정 폴드(fixed fold)는 후보 결정들을 선호도 방향을 설정하는 데 사용되는 최종 결과로부터 분리하며, 지지 의존적 증거 가중치는 공유된 GraphGPO 작업 학습과 함께 보조 쌍별(pairwise) 목적 함수를 스케일링합니다. MCGPO는 롤아웃 데이터와 각 응답의 원래 이력을 재사용하여 비평자 없는(critic-free) 학습을 유지합니다. 각각 세 가지 학습 시드를 사용한 6개의 환경-백본 설정 전반에서, MCGPO는 일치된 GraphGPO 대비 평균 성공률을 향상시켰습니다. Qwen2.5-1.5B 및 7B를 사용한 ALFWorld와 WebShop에서 0.47~1.46%포인트 향상되었으며, Qwen3-4B 및 8B를 사용한 WebShop에서는 3.96 및 5.16포인트 향상되었습니다. ALFWorld의 성능 향상은 여유 공간이 제한적인 92% 이상의 기준선 성공률을 기반으로 이루어졌습니다. 통합 성공률은 4개의 Qwen2.5 설정 중 3개에서 향상되었습니다. 3개 시드 요인 제어(factorial controls)는 반대 폴드 증거 및 증거 가중치를 뒷받침하며, 결합 상태-루브릭 매칭은 4개의 표현-제어 설정 모두에서 가장 높은 평균을 달성했습니다.

arXiv:2610.08077v2cs.AI공통 태그 Reinforcement Learning (RL), Sequential Decision Making

자기 회고 증류: 사후 경험을 사전 예측력으로 전환하기

Self-Retrospection Distillation: Turning Post-hoc Experiences into Prior Foresight

검증 가능한 보상을 활용한 강화학습(RLVR)은 주로 상호작용 후의 스칼라 결과 보상을 통해 에이전트 경험을 학습 신호로 전환합니다. 그러나 그룹 상대적 목적 함수의 경우, 모든 롤아웃이 동일한 보상을 받으면 해당 궤적이 작업에 필요한 요소와 에이전트가 실패하는 방식에 대한 유용한 정보를 드러낼 수 있음에도 불구하고 이러한 신호가 사라집니다. 우리는 이와 상호보완적인 질문을 던집니다. 사후적 통찰(hindsight)이 에이전트에게 행동하기 전에 무엇을 예측할 수 있었는지를 가르쳐줄 수 있을까요? 우리는 상호작용 이전 시점에서의 예측을 지도하기 위해 사후 경험을 사용하는 전향적 학습(prospective learning)을 도입하고, 이를 자기 회고 증류(Self-Retrospection Distillation, SRD)로 구체화합니다. 직관적으로 완료된 궤적은 유용했을 지식과 피해야 했을 함정을 드러내며, SRD는 이 특권적 사후 통찰을 동일한 정책의 궤적 비인지 사전 예측으로 증류합니다. 사전 예측은 학습 목표로만 기능하며 추론 시 명시적으로 생성될 필요가 없습니다. 10가지 도구 통합 추론 및 장기적 에이전트 작업 전반에서, SRD는 RLVR 및 자기 증류 베이스라인을 보완하여 최대 24.2%p의 성능 향상을 달성합니다. 특히 모델 규모 전반에 걸쳐 롤아웃 그룹의 37~98%가 균일한 보상을 보여 보상 대조가 부족한 경우에도 SRD는 샘플링된 궤적으로부터 학습 신호를 활용할 수 있어 그 이점이 두드러집니다. 그룹의 98%가 전면 실패하는 2B 설정에서 RLVR 학습은 0.0%의 성공률로 끝나는 반면, 동일한 롤아웃 예산 하에서 SRD를 추가하면 60.6%에 도달합니다. 우리의 결과는 사후 에이전트 경험이 행동을 평가하거나 개선하는 것뿐만 아니라 상호작용 이전에 예측적 표현을 형성하는 데에도 유용함을 시사합니다.

arXiv:2608.05446v2cs.LG공통 태그 Reinforcement Learning (RL), Sequential Decision Making

EvoHarness-RL: 자기 진화형 에이전트를 위한 런타임 하네스 조율 학습

EvoHarness-RL: Learning Runtime Harness Coordination for Self-Evolving Agents

장기 작업(long-horizon) 대규모 언어 모델(LLM) 에이전트는 상태 유지, 진행 상황 추적, 실패 복구, 확장된 상호작용 전반에 걸친 경험 재사용을 위해 외부 실행 지원에 점점 더 많이 의존하고 있습니다. 그러나 기존 하네스 및 그 사용 방식은 특정 환경에 맞춤화되어 프롬프트, 휴리스틱 또는 시스템별 규칙을 통해 제어되는 경우가 많아 에이전트와 하네스 조율을 공동으로 최적화하기 어렵습니다. 본 논문에서는 환경별 하네스 구현을 공유 정책 인터페이스와 분리하는 통합 프레임워크인 EvoHarness-RL을 제안합니다. EvoHarness-RL은 외부 지원을 신념, 진행, 경험(Belief, Progress, and Experience, BPE) 작업 공간으로 구성하고, 이 상태에 접근 및 업데이트하기 위한 네 가지 간결한 하네스 행동을 노출합니다. 먼저 BPE를 추론 시점의 스캐폴드로 인스턴스화한 다음, 지도형 초기화에 이어 비용 인식 GRPO를 통해 하네스 조율을 학습 가능하도록 만듭니다. 이종의 장기 작업 전반에 걸쳐 EvoHarness-Base는 프론티어 모델의 평균 성공률을 10.0%p 향상시키며, EvoHarness-RL은 가장 강력한 오픈소스 기준선보다 8.5%p 뛰어난 성능을 보임과 동시에 더 높은 강화학습(RL) 롤아웃 효율성과 보지 못한 작업에 대한 더 강력한 일반화 성능을 보여줍니다. 분석 결과, 정책의 역량이 향상됨에 따라 학습을 통해 에이전트가 잦은 스캐폴드 사용에서 선별적이고 환경 의존적인 하네스 접근으로 점진적으로 전환되는 반면, 외부 작업 공간은 작업 실행과 일반화를 더 잘 지원하기 위해 지속적으로 진화하고 개선되는 것으로 나타났습니다. 종합적으로 이러한 결과는 장기 작업 에이전트가 외부 스캐폴딩 자체뿐만 아니라 비용 인식 정책의 일부로서 외부 지원과 조율하는 방법과 시점을 학습함으로써 이점을 얻는다는 점을 보여줍니다.

토론

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