몬테카를로 Pass@k Critic을 이용한 단일 시뮬레이션 기반 강화 학습

Learning with a Single Rollout via Monte Carlo Pass@k Critic

언어 모델을 위한 강화 학습(RL)에서 토큰 수준의 이점을 추정하는 것은 에피소드 경험 수집을 확장하는 데 비용이 많이 들기 때문에 여전히 어려운 문제입니다. 특히, 기준점 이점 추정 방법에서는 반복적인 샘플링으로 인해 경로가 상당히 다른 추론 단계로 분기되는 문제가 발생합니다. 이러한 맥락에서 GRPO와 같은 RL 알고리즘은 중간 단계와 같은 특정 행동에 대한 보상을 제공하기에는 너무 희소하고, 샘플링된 경로 간의 비교는 이질성 때문에 어렵다는 한계점을 가지고 있습니다. 본 연구에서는 반복적인 샘플링의 계산 비용과 신용 할당의 어려움을 완화하기 위해, 언어 모델을 위한 강화 학습에서 토큰 수준의 신용 할당 기능을 갖춘 단일 시뮬레이션 기반 근접 정책 최적화(SR-PPO) 방법을 제안합니다. 우리는 후보 그룹 내 에피소드 수익을 정규화하여 이점을 추정하는 대신, 프롬프트당 하나의 시뮬레이션을 통해 얻은 몬테카를로 결과를 사용하여 보정된 토큰 수준의 신용 평가기를 학습시킵니다. 특히, 이 평가기는 Pass@1 시도에서 파생된 프롬프트 접두부에서의 Pass@k 성공 확률을 예측하는 데 사용됩니다. 이러한 선택은 Pass@1보다 더 선택적인 학습 신호를 제공합니다. 즉, 쉽게 해결되는 접두부를 할인하고 성공 확률이 낮은 어려운 접두부에 우선순위를 부여합니다. 우리는 k 값이 증가함에 따라 Pass@k가 도달 가능성 지표로 수렴하며, 이는 접두부가 최소한 하나의 성공적인 결과를 가져올 수 있는지를 나타냅니다. 명시적인 상태 그래프에서 극한값(k → ∞)은 O(|V|+|E|) 시간 내에 계산할 수 있으며, 이는 대조 경로를 샘플링하지 않고도 직접적인 신용 할당을 위한 유망한 대체 방법입니다. 초기 검증 결과, SR-PPO는 안정적인 학습 동역학을 보이며, HMMT26 및 AIME24과 같은 수학적 추론 벤치마크에서 Pass@128 성공률이 꾸준히 향상되었습니다.

Estimating token-level advantages in reinforcement learning (RL) for language models remains challenging because scaling up episodic experience collection is expensive. The difficulty intensifies for baseline advantage estimation methods, where repeated sampling causes trajectories to diverge into substantially different reasoning prefixes. In this context, RL algorithms such as GRPO prove limited: an outcome reward is too sparse to be attributed to specific actions like intermediate steps, and comparisons across sampled traces are non-trivial because they are heterogeneous. To mitigate both the computational cost of repeated sampling and the difficulty of credit assignment, we study single-rollout proximal policy optimization (SR-PPO) featuring token-level credit assignment in RL for language models. Instead of estimating advantages by normalizing episodic returns within the candidate group, we train a calibrated token-level credit critic using Monte Carlo outcomes from one rollout per prompt. Specifically, we use the critic to predict the Pass@k success probability at the prompt prefix, which is derived from a Pass@1 attempt. This choice yields a more selective learning signal than Pass@1: it discounts easily solved prefixes while prioritizing hard ones whose success probability remains marginal. We show that as $k$ increases, Pass@k converges to a reachability indicator, reflecting whether a prefix can lead to at least one successful continuation. In an explicit state graph, the limit ($k \rightarrow \infty$) can be computed in $O(|V|+|E|)$ time, offering a promising surrogate for direct credit assignment without the need to sample contrastive traces. As an initial validation, SR-PPO exhibits stable learning dynamics, along with consistent gains in Pass@128 success rates on mathematical reasoning benchmarks such as HMMT26 and AIME24.