State-Separated SARSA: A Practical Sequential Decision-Making Algorithm with Recovering Rewards
원문 초록
While many multi-armed bandit algorithms assume that rewards for all arms are constant across rounds, this assumption does not hold in many real-world scenarios. This paper considers the setting of recovering bandits (Pike-Burke & Grunewalder, 2019), where the reward depends on the number of rounds elapsed since the last time an arm was pulled. We propose a new reinforcement learning (RL) algorithm tailored to this setting, named the State-Separate SARSA (SS-SARSA) algorithm, which treats rounds as states. The SS-SARSA algorithm achieves efficient learning by reducing the number of state combinations required for Q-learning/SARSA, which often suffers from combinatorial issues for large-scale RL problems. Additionally, it makes minimal assumptions about the reward structure and offers lower computational complexity. Furthermore, we prove asymptotic convergence to an optimal policy under mild assumptions. Simulation studies demonstrate the superior performance of our algorithm across various settings.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
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개, 점수 측정 및 검증 툴링을 공개하며, 벤치마크 오염을 방지하기 위해 전체 환경과 평가 스위트는 비공개로 유지합니다.
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개의 표현-제어 설정 모두에서 가장 높은 평균을 달성했습니다.
비동기 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)을 얻는다.
Actor-Critic Deep Reinforcement Learning for Solving Job Shop Scheduling Problems
시뮬레이션은 코드가 담당하고, 평가는 Jev가 담당한다
Code Owns the Simulation, Jev Owns the Evaluation
Jev와 같은 판단 모델(judgment model)은 단 한 번의 호출로 추론 텍스트 없이 설명된 각 선택지에 대한 확률을 반환합니다. 이러한 특징 덕분에 에이전트의 행동 선택 층(layer)으로서 매력적이지만, 어떤 결정을 신뢰할 수 있는지는 명확하지 않습니다. 본 연구에서는 인지 반사 테스트, 일회성 행렬 게임, 텍스트 게임 ALFWorld 및 로봇 제어에서 Jev를 테스트하고 뚜렷한 경계를 발견했습니다. Jev는 입력에 설명된 내용으로부터 올바른 선택지를 판단할 수 있을 때 성공하며, 이를 본 연구에서는 평가(evaluation)라고 부릅니다. 구체적으로, Jev는 직관에 반하는 인지 반사 테스트(Cognitive Reflection Test) 문제의 99%를 해결합니다. 그러나 올바른 선택지가 상대방의 행동이나 먼저 달성해야 하는 하위 목표와 같이 시뮬레이션(simulation, 즉 입력에 없는 내용을 예측하는 것)에 의존할 때는 실패합니다. 게임에서 Jev는 상대방의 행동이 주어지지 않기 때문에 합리적인 상대가 무작위로 행동하는 것처럼 차선으로 플레이합니다. ALFWorld에서 Jev는 작업 설명에 언급된 사물이나 장소를 지칭하는 명령을 선호합니다. 예를 들어, "서랍에 깨끗한 칼을 넣어라"라는 작업이 주어지면, Jev는 싱크대에서 칼을 먼저 씻는 대신 씻지 않은 칼을 서랍으로 곧장 가져갑니다. 놀랍게도 이러한 실패 중 다수는 지식의 부족 때문이 아닙니다. 상대가 무엇을 할지 별도로 질문을 받으면 Jev는 대개 정확하게 답하며, 상대의 행동이 주어지면 적절하게 대응합니다. Jev가 실패하는 것은 단 한 번의 호출로 시뮬레이션을 수행하고 이에 기반한 평가까지 동시에 처리해야 할 때입니다. 이는 예측이나 시뮬레이션을 코드가 수행하도록 할 것을 시사합니다. ALFWorld의 미리보기(lookahead)나 로봇 제어의 물리 시뮬레이션과 같이 코드가 이를 제공하면, Jev는 일반적인 평가 능력을 통해 전문가 수준의 제어기가 됩니다.
RSIPO: 스킬-정책 공진화를 통한 에이전트 강화학습용 재귀적 자기 개선 정책 최적화
RSIPO: Recursive Self-Improving Policy Optimization for Agentic Reinforcement Learning via Skill-Policy Co-Evolution
최근 에이전트(agent) 강화학습(RL) 분야에서는 긴 지평(long-horizon) 과제에서의 신용 할당(credit assignment)을 개선하는 데 집중하고 있습니다. 유망한 방향 중 하나는 검증 가능한 보상을 활용한 강화학습(RLVR)과 온-정책(on-policy) 자기 증류(OPSD)를 결합하여, 궤적 수준(trajectory-level)의 이점(advantage)과 조밀한 토큰 수준의 감독을 통합하는 것입니다. 이러한 일련의 연구는 학생 정책(student policy)이 생성한 토큰을 평가하기 위해 에이전트 스킬과 같은 특권적 문맥(privileged context)에 교사 모델을 조건화하는 경우가 많습니다. 이러한 진전에도 불구하고, 기존 연구들은 에이전트 스킬의 온-정책적 진화와 교사 감독의 신뢰성을 대체로 간과하고 있습니다. 이를 해결하기 위해, 본 논문에서는 학습 과정 전반에 걸쳐 에이전트 스킬과 정책 모델이 함께 공진화(co-evolve)할 수 있도록 하는 자기 진화형 에이전트 강화학습 프레임워크인 재귀적 자기 개선 정책 최적화(RSIPO)를 제안합니다. 구체적으로 RSIPO는 정책 모델 스스로가 완료된 궤적에서 스킬을 추출할 수 있도록 하며, 궤적 리플레이(trajectory replay)를 통해 스킬 생성 역량을 명시적으로 최적화합니다. 또한 스킬로 강화된 교사의 지도가 때로는 신뢰성이 떨어질 수 있다는 점을 고려하여, 경험적 베이즈 축소(empirical Bayes shrinkage)를 적용해 교사 점수에 대한 학생의 신뢰도를 동적으로 보정합니다. 체화된 상호작용(embodied interaction) 및 검색 기반 에이전트 과제에서 Qwen 계열 모델을 사용한 실험 결과, RSIPO가 비교 대상이 된 모든 기준선 접근법을 능가하는 성능을 보였습니다. Qwen2.5-7B를 기본 모델로 사용했을 때 RSIPO는 ALFWorld에서 평균 98.6%의 성공률을 달성하여, 차상위 기준선 및 표준 GRPO 대비 각각 2.5%와 17.4%의 절대적인 성능 향상을 기록했습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.