Tail-Likelihood Reinforcement Learning

Shrinivas Ramasubramanian$^{1}$ Daman Arora$^{1}$ Fahim Tajwar$^{1}$ Guanning Zeng$^{1}$
Qingyang Wu$^{4}$ Zhongzhu Zhou$^{4}$ Chenfeng Xu$^{4}$
Haiwen Feng$^{2,3}$ Yuda Song$^{1}$ Aarti Singh$^{1}$ Ruslan Salakhutdinov$^{1}$
J. Andrew Bagnell$^{5,1}$ Jeff Schneider$^{1,\dagger}$ Andrea Zanette$^{1,\dagger}$
$^{1}$Carnegie Mellon University $^{2}$University of California, Berkeley $^{3}$Impossible, Inc.
$^{4}$Together AI $^{5}$Aurora Innovation
{shrinivr, jeff4, azanette}@andrew.cmu.edu

$^{\dagger}$ Joint advising.
Project website, code, and other assets: https://zanette-labs.github.io/TailRL-website/

Abstract

Reinforcement learning typically optimizes average reward. For generative policies, the average can hide an important distinction: two policies can achieve the same mean reward while having very different chances of producing a rare but high-reward rollout. This matters as sampling increases during training and inference, since its benefit depends on retaining probability mass on high-reward outcomes. We propose to optimize this coverage directly. Rather than considering only expected reward, we consider all of its upper tails: for each reward threshold, how likely is the policy to exceed it? This turns a continuous reward into a family of binary success events. We introduce Tail-Likelihood Reinforcement Learning (TailRL), which maximizes the log-probability of exceeding a randomly chosen reward threshold. Its gradient gives more weight to rare, high-reward rollouts and can be interpreted as a mixture of Best-of-($k$) gradients. TailRL requires only a simple modification to the advantage function, making it compatible with existing reinforcement learning pipelines. Across object localization, maze navigation, GUI grounding, and code optimization, TailRL leverages rare high-reward training samples to avoid suboptimal solutions and yields models that benefit more from additional samples at inference time.

Executive Summary: Reinforcement learning for generative models usually maximizes expected reward, yet this average can mask a critical weakness: policies with similar means can differ sharply in their probability of producing rare but high-value outputs. When sampling increases during training or inference, this gap becomes decisive because further gains depend on retaining coverage over those upper-tail outcomes. The paper introduces Tail-Likelihood Reinforcement Learning to address exactly this issue for continuous rewards.

The work sets out to optimize the full family of upper-tail probabilities rather than a single mean. For every reward threshold, it treats the event of exceeding that threshold as a binary success and maximizes the expected log-probability of success across thresholds drawn uniformly from the reward range. The resulting objective decomposes into a harmonic mixture of Best-of-k gradients, so a single training run improves performance at every inference budget without choosing one in advance. Implementation requires only a change to the advantage weights inside existing critic-free pipelines such as GRPO or RLOO; the weights are computed in closed form from a small group of rollouts and remain unbiased for a truncated version of the population objective.

Experiments across four domains show consistent gains where high-reward outcomes are rare or where standard methods collapse to safe but mediocre behavior. On ImageNet object localization, population-level TailRL matches or exceeds supervised coordinate regression while finite-rollout versions outperform GRPO and RLOO at matched or lower training budgets. In text-maze navigation, it learns reliably from initial policies whose success rate is only 0.01 percent, a regime in which expected-reward baselines fail. On GUI grounding with vision-language models, it reaches the Pass@1024 level of strong baselines with 128- to 256-fold fewer inference samples. On code runtime optimization, it produces a 7.7 times higher Best-of-1024 speedup while GRPO and RLOO converge to the trivial copy-the-input solution.

These results matter because many current post-training pipelines already rely on group-based policy gradients and inference-time selection. Replacing the advantage calculation with the TailRL weights adds negligible overhead yet materially improves both training stability and the returns from additional test-time compute. The method introduces no new hyperparameters beyond the rollout group size, which itself selects the truncation order of the objective.

Further work is needed to test the approach on larger models, longer-horizon tasks, and settings where rewards are only partially observed or unbounded. The finite-rollout estimator is exact only up to the chosen group size, and all reported results use bounded rewards; extensions to unbounded or learned rewards remain open. Overall the evidence is strong within the evaluated domains, yet broader validation across production-scale systems would increase confidence for high-stakes deployment.

1. Introduction

Section Summary: Standard reinforcement learning optimizes a policy's average reward, but this can cause the policy to lose track of rare, exceptionally strong outcomes that matter when multiple samples can be drawn during training or later use. The paper introduces TailRL, which instead maximizes the chance of exceeding many different reward thresholds at once, directly encouraging a heavier upper tail in the reward distribution. This produces policies that better preserve high-performing outputs, align training with inference-time scaling, and outperform standard methods on tasks such as navigation, grounding, and code optimization.

Reinforcement learning (RL) typically optimizes the expected reward of a policy ([1, 2, 3, 4, 5]). For generative policies, however, the mean reward does not fully characterize performance: two policies with similar mean reward can have very different probabilities of producing rare but exceptionally good rollouts. This distinction matters whenever additional samples can be drawn, both during training and at inference time.

Recent work has exposed this problem directly: standard RL training can progressively lose coverage over rare, high-reward rollouts, often visible as a degradation in Best-of- $k$ performance ([6, 7, 8, 9, 10]). Once these rollouts become sufficiently unlikely, they are rarely sampled again, making further policy improvement increasingly difficult. The same loss of coverage limits inference-time scaling: a policy may perform well with a single sample while gaining little from drawing many ([11, 12, 13]). Thus, optimizing only the mean reward can discard information about the upper tail of the reward distribution that is crucial for both training and inference scaling.

For binary rewards, MaxRL ([14]) offers one way to address this problem. Rather than maximizing the probability of success, MaxRL maximizes its log-probability, placing greater emphasis on rare successes. Its gradient decomposes into a harmonic mixture of Pass@ $k$ gradients, directly connecting likelihood maximization to a mixture of Pass@ $k$ objectives.

How should this principle extend to continuous rewards? Our starting point is simple: every reward threshold defines a binary event. Given an input $x$, a rollout $z\sim\pi_\theta(\cdot\mid x)$, and a threshold $\tau$, we ask whether the reward exceeds $\tau$. The corresponding tail probability is

$ p_\theta(x, \tau) := \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)} \bigl(r(x, z)>\tau\bigr).\tag{1} $

A continuous reward can be viewed as a family of binary success events, one for every threshold $\tau$. This perspective leads to Tail-Likelihood Reinforcement Learning (TailRL). For rewards in $[0, 1]$, TailRL maximizes the expected log-likelihood of exceeding a uniformly chosen reward threshold:

$ J_{\mathrm{TailRL}}(\theta;x)

\int_0^1 \log p_\theta(x, \tau), d\tau.\tag{2} $

Unlike expected-reward maximization, which acts on a single summary of the reward distribution, TailRL explicitly optimizes upper-tail probabilities across reward levels. We show that the gradient of TailRL decomposes into a harmonic mixture of Best-of- $k$ gradients (Section 3.1), directly connecting the training objective to coverage of high-reward rollouts and inference-time scaling. MaxRL emerges as the binary-reward special case. Despite its different objective, TailRL admits a simple critic-free policy-gradient estimator that differs from standard RL only in its advantage calculation, allowing it to be implemented by swapping the advantage function in an existing RL pipeline. Across object localization (Section 6.1), maze navigation (Section 6.2), GUI grounding (Section 6.3), and code optimization (Section 6.4), TailRL leverages rare high-reward samples during training to avoid suboptimal solutions and produces policies that benefit more from additional samples at inference time.

Our contributions are as follows.

1. A likelihood objective for continuous rewards. TailRL maximizes the log-probability of exceeding a uniformly drawn reward threshold, which weights each reward level by the inverse of how often the policy reaches it. It introduces no threshold or weighting hyperparameter and reduces exactly to MaxRL for binary rewards.
2. Alignment with inference-time scaling. The gradient of TailRL decomposes harmonically over Best-of- $k$ gradients (Section 3.1),

$ \nabla_{\theta} J_{TailRL}(\theta; x) = \sum_{k=1}^{\infty}\frac{1}{k}, \nabla_\theta, \text{Best-of-}k(\theta; x), $

so TailRL improves Best-of- $k$ at every inference budget without choosing one in advance. 3. An unbiased finite-rollout estimator. A group of $N$ rollouts defines an order- $N$ truncation of TailRL that interpolates from expected reward ($N=1$) to the population objective ($N\to\infty$), and we derive closed-form rollout weights that estimate its gradient without bias (Section 4). Unlike REINFORCE, where more rollouts only reduce variance, here the rollout budget selects the objective being optimized. 4. Strong empirical results. TailRL matches supervised objectives that observe the ground truth on object localization (Section 6.1), learns from initial policies with $0.01%$ success where expected-reward baselines fail on maze navigation (Section 6.2), matches RLOO's Pass@1024 on GUI grounding with $128$ – $256\times$ fewer inference rollouts (Section 6.3), and reaches a $7.7\times$ Best-of-1024 speedup on code optimization where GRPO and RLOO collapse onto copying the input (Section 6.4).

2. Preliminaries

Section Summary: The preliminaries introduce continuous-reward reinforcement learning in which a policy generates rollouts that receive scalar rewards between zero and one, with the usual policy-gradient objective weighting score functions by those rewards. They also describe how extra inference compute can be spent sampling multiple rollouts and keeping the best one, measured by Pass@k for binary rewards or Best-of-k for continuous ones, and they frame the policy as a generative model that shapes an entire distribution over possible reward values rather than just their average. The section closes by contrasting standard mean-reward training with MaxRL, which instead maximizes the log-probability of success for binary rewards.

We primarily focus on optimizing continuous reward reinforcement learning, where for each input $x$, a rollout $z$ is generated by the policy $\pi_{\theta}$. A rollout may be a generated response, program, or trajectory. A deterministic reward function provides a scalar feedback for an input rollout pair $r(x, z)\in[0, 1]$. Appendix D treats a more general bounded reward range.

Training ultimately averages over $x\sim\rho$. To keep the notation light, we write each objective for a fixed input $x$ and leave the outer average over inputs implicit. We define the policy's score-function as $S(x, z):=\nabla_\theta\log\pi_\theta(z\mid x)$. Standard reinforcement learning maximizes expected reward and the score-function identity ([1]) gives its policy gradient as follows,

$ \begin{gathered} J_{RL}(\theta;x) := \mathbb{E}{z\sim\pi\theta(\cdot\mid x)} !\left[r(x, z)\right], \ \nabla_\theta J_{\mathrm{RL}}(\theta;x)

\mathbb{E}{z\sim\pi\theta(\cdot\mid x)} !\left[r(x, z)S(x, z)\right]. \end{gathered}\tag{3} $

Thus, the policy gradient is a weighted combination of the score-function and the weights are determined by the rollout's reward. During training, critic-free rollout based policy gradient methods draw $N$ independent rollouts $z_1, \ldots, z_N\sim\pi_\theta(\cdot\mid x)$. Critic-free methods such as GRPO ([2]) and RLOO ([3]) compute a finite rollout estimate of Equation 3. PKPO ([11]) optimizes Pass@ $k$ and Best-of- $k$ for binary and continuous rewards using a similar finite-rollout based estimation framework. Section 4 shows that TailRL uses the same template and changes only how these advantages are computed, and Appendix F places the three advantage functions side by side.

2.1 Inference-Time Selection

At deployment, additional inference compute can be used to sample several rollouts and select the one with the highest reward. For $k$ independent rollouts, this performance is measured by probability of at-least one success (Pass@ $k$) when rewards are binary and expected maximum reward among (Best-of- $k$) when rewards are continuous:

$ \begin{aligned} & \text{Pass@}k(\theta;x) := 1 - \left(\operatorname{Pr}{z\sim\pi{\theta}(\cdot\mid x)}\bigl(r(x, z)=0\bigr)\right)^{k}, && \text{(binary reward)} \quad\text{(a)}\ & \text{Best-of-}k(\theta; x) := \mathbb{E}{{z_i}{i=1}^{k} \sim \pi_{\theta}(\cdot \mid x)}!\left[\max_{1\le i\le k} r(x, z_i)\right], && \text{(continuous reward)} \quad\text{(b)} \end{aligned}\tag{4} $

At $k=1$, both reduce to the mean reward, $ J_{\mathrm{RL}}(\theta;x)$. Appendix G gives the estimators we typically use to compute both empirically. Both Pass@ $k$ and Best-of- $k$ are non-decreasing in $k$, and as $k\to\infty$ each approaches the maximum reward in their support.

Unlike mean reward, $\text{Best-of-}k$ depends strongly on the upper part of the reward distribution. Two policies with the same mean can scale differently with additional training or inference compute if one assigns more probability to high-reward rollouts.

2.2 Policy as a Generative Model of Rewards

A policy and reward function together define a distribution over rewards. For an input $x$, the policy samples a rollout $z$ and the reward function assigns its reward:

$ z\sim\pi_\theta(\cdot\mid x), \qquad r=r(x, z)\in[0, 1].\tag{5} $

Because the reward function is deterministic, all randomness in the reward comes from the policy. The induced reward distribution for any event $A$ ($A\subseteq[0, 1]$) over the support of rewards is defined as,

$ \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)} !\left(r(x, z)\in A\right) = \mathbb{E}{z\sim\pi{\theta}(\cdot \mid x)}[\mathbb{1}_{{r(x, z) \in A }}]\tag{6} $

In this view, the policy is a generative model over rewards, and training manipulates the probability mass over reward values. Expected reward reinforcement learning uses only the mean reward to shape this reward distribution.

Different policies can have the same mean reward while assigning very different probabilities to high-reward outcomes. This becomes visible in their difference in Best-of- $k$ and Pass@ $k$ performance. This motivates objectives that act on the entirety of the reward distribution rather than only its mean. We begin with binary rewards, where the distribution is completely determined by a single success probability.

2.3 MaxRL for Binary Rewards

For a binary reward $r(x, z)\in{0, 1}$, expected reward equals the probability of success.

$ q_\theta(x) := \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)} !\left(r(x, z)=1\right).\tag{7} $

The reward distribution is therefore a Bernoulli distribution over success and failures. The reward distribution is fully determined by $q_\theta(x)$. Standard reinforcement learning maximizes $q_\theta(x)$, whereas MaxRL ([14]) maximizes $J_{\mathrm{MaxRL}}(\theta;x) = \log q_\theta(x)$ and its gradient is,

$ \nabla_\theta J_{\mathrm{MaxRL}}(\theta;x)

\frac{1}{q_\theta(x)} \mathbb{E}{z\sim\pi\theta(\cdot\mid x)} !\left[\mathbb{1}_{{r(x, z)=1}}S(x, z) \right].\tag{8} $

The factor $1/q_\theta(x)$ gives greater weight to inputs on which success is rare. MaxRL also connects to inference-time sampling. $\nabla_\theta J_{\mathrm{MaxRL}}(\theta;x)$ decomposes as a harmonic mixture of Pass@ $k$ gradients.

$ \nabla_\theta J_{\mathrm{MaxRL}}(\theta;x)

\sum_{k=1}^{\infty} \frac{1}{k} \nabla_\theta\mathrm{Pass@}k(\theta; x)\tag{9} $

3. Tail-Likelihood Reinforcement Learning

Section Summary: TailRL reframes the usual goal of maximizing expected reward by instead focusing on the policy’s tail probabilities—the chances of exceeding each possible reward threshold. Rather than adding these probabilities together, it takes their average logarithm, which automatically gives more weight to harder, higher-reward thresholds and produces a geometric emphasis on rare successes. The approach generalizes an earlier method for binary rewards and connects to combining “best-of-k” performance signals across every possible number of samples.

We motivate TailRL by expressing expected reward in terms of the policy's upper-tail probabilities. For rewards in $[0, 1]$, define the tail probability at threshold $\tau$ as

$ p_\theta(x, \tau) := \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)} \left(r(x, z)>\tau\right).\tag{10} $

The expected reward is exactly the area under this tail-probability curve:

$ J_{\mathrm{RL}}(\theta;x)

\mathbb{E}[r(x, z)]

\int_0^1 p_\theta(x, \tau), d\tau.\tag{11} $

Tail-Likelihood Reinforcement Learning (TailRL) instead applies the MaxRL likelihood principle at every reward threshold. It maximizes the average log-probability of exceeding a uniformly sampled threshold:

$ J_{\mathrm{TailRL}}(\theta;x) := \int_0^1 \log p_\theta(x, \tau), d\tau

\mathbb{E}{\tau\sim\mathrm{Unif}[0, 1]} \left[\log p\theta(x, \tau)\right].\tag{12} $

Equivalently, expected-reward RL aggregates tail probabilities arithmetically, whereas TailRL aggregates them geometrically. This makes small tail probabilities more influential, as seen directly from its gradient

$ \nabla_\theta J_{\mathrm{TailRL}}(\theta;x)

\int_0^1 \frac{1}{p_\theta(x, \tau)} \nabla_\theta p_\theta(x, \tau) , d\tau.\tag{13} $

The higher the reward threshold, the smaller the tail-probability and higher is the weight for the gradient. Thus reward thresholds that are difficult to reach receive larger weight during optimization.

3.1 Harmonic Decomposition over Best-of-k

Although TailRL is defined through reward thresholds, it has an exact interpretation in terms of inference-time sampling. Recall that $\mathrm{Best\text{-}of\text{-}k}(\theta;x)$ is the expected maximum reward among $k$ independent rollouts from $\pi_\theta(\cdot\mid x)$.

########## {caption="Theorem 1: Best-of- $k$ decomposition"}

The TailRL objective decomposes as

$ J_{\mathrm{TailRL}}(\theta;x)

\sum_{k=1}^{\infty} \frac{\mathrm{Best\text{-}of\text{-}k}(\theta;x)-1}{k},\tag{14} $

and, under the regularity conditions of Lemma 6, its gradient satisfies

$ \nabla_\theta J_{\mathrm{TailRL}}(\theta;x)

\sum_{k=1}^{\infty} \frac{1}{k} \nabla_\theta \mathrm{Best\text{-}of\text{-}k}(\theta;x).\tag{15} $

Thus, TailRL combines Best-of- $k$ learning signals across all inference budgets. The harmonic weights $1/k$ arise automatically from the logarithm, so TailRL does not require selecting a target inference budget in advance. The proof is given in Appendix C.3.3.

3.2 Recovery of MaxRL for Binary Rewards

For binary rewards, every nontrivial reward threshold defines the same success event. Let

$ q_\theta(x) := \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)} \left(r(x, z)=1\right) $

denote the probability of success. For every $\tau\in[0, 1)$, $p_\theta(x, \tau)=q_\theta(x)$, and therefore

$ J_{\mathrm{TailRL}}(\theta;x)

\int_0^1 \log q_\theta(x), d\tau

\log q_\theta(x)

J_{\mathrm{MaxRL}}(\theta;x).\tag{16} $

Moreover, for binary rewards $\mathrm{Best\text{-}of\text{-}k}$ coincides with $\mathrm{Pass@}k$, so the harmonic Best-of- $k$ decomposition above reduces exactly to the harmonic Pass@ $k$ decomposition of MaxRL. Thus, TailRL directly generalizes MaxRL from binary to continuous rewards.

3.3 Probabilistic Interpretation of TailRL

A direct extension of MaxRL would define only $r(x, z)=1$ as success and treat every lower reward as the same failure. Exact success may be rare or unattainable. Lowering the success threshold makes the event more common, but still treats all rewards on either side of the threshold as equivalent. Once a rollout crosses the threshold, the objective has no preference for improving it further. The resulting policy can perform well at the chosen threshold while remaining poor at higher reward levels (Appendix H.4). We therefore need a likelihood event that preserves the continuous reward signal.

A continuous reward defines such an event at every reward threshold. For $\tau\in[0, 1)$, define the tail-probability

$ p_\theta(x, \tau) := \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)} !\left(r(x, z)>\tau\right).\tag{17} $

Independent quality audit

We combine the tail events by assigning each reward threshold an independent rollout. The audit passes only if every rollout clears its assigned threshold. Independent rollouts are necessary: reusing one rollout would collapse the nested events to the hardest threshold.

For an audit with $L$ equally spaced thresholds, let $\tau_\ell=(\ell-1)/L$ and draw $z_1, \ldots, z_L\overset{\mathrm{i.i.d.}}{\sim}\pi_\theta(\cdot\mid x)$. Define the event that the policy passes the audit as

$ E_L := \bigcap_{\ell=1}^{L} \left{ r(x, z_\ell)>\tau_\ell \right}.\tag{18} $

Because the rollouts are independent, the audit probability factorizes:

$ \operatorname{Pr}{z_1...z_L \sim \pi\theta(\cdot\mid x)}(E_L\mid x)

\prod_{\ell=1}^{L} p_\theta(x, \tau_\ell).\tag{19} $

The number of thresholds controls only the resolution of the audit. Requiring invariance to the change in scale of the objective due to increasing resolution of the audit, while agreeing with ordinary log-likelihood when $L=1$, uniquely gives the normalization $1/L$:

$ \frac{1}{L} \log \operatorname{Pr}_\theta(E_L\mid x)

\frac{1}{L} \sum_{\ell=1}^{L} \log p_\theta(x, \tau_\ell).\tag{20} $

Each midpoint $\tau_\ell$ represents an interval of width $1/L$. The right-hand side of Equation 20 is therefore a Riemann sum over the reward range. Letting $L\to\infty$ gives

$ J_{\mathrm{TailRL}}(\theta;x) := \lim_{L\to\infty} \frac{1}{L} \log \operatorname{Pr}_\theta(E_L\mid x)

\int_0^1 \log p_\theta(x, \tau) , d\tau,\tag{21} $

We call Equation 12 the population-level TailRL objective. Equivalently, TailRL maximizes the expected log-probability of clearing a uniformly sampled reward threshold.

TailRL uses the full support of the reward distribution rather than selecting an arbitrary cut-off. Uniform sampling of threshold $\tau$ assigns equal importance to the log-likelihood of their tail-events. It introduces no weighing hyperparameter. More generally, one could sample $\tau$ from a non-uniform distribution inducing a re-weighting of the log-likelihood terms. Any strictly positive normalized weighting is exactly equivalent to applying TailRL after a monotone transformation of the rewards (Proposition 9). We use the uniform distribution throughout and leave task-specific reward shaping to future work. The audit defines the population objective; it does not yet prescribe the finite-rollout estimator used for training (Section 4).

4. Estimating the TailRL Gradient

Section Summary: With only a limited number of rollouts available during training, the full TailRL objective cannot be estimated directly, so the authors instead work with a natural finite-order truncation of that objective whose gradient can be computed exactly from the samples. They derive an unbiased estimator by assigning each rollout a weight that integrates credit across reward thresholds, giving higher weight to outcomes that exceed fewer other samples. In practice the weights are centered within each group of rollouts to reduce variance while preserving unbiasedness for a slightly lower-order version of the objective.

Training observes only a finite group of rollouts during training. The population-level objective is inestimable from finite rollouts. We show that a rollout budget of $N$ naturally defines an order- $N$ truncation of the TailRL objective and admits a simple unbiased policy-gradient estimator.

4.1 From Finite Rollouts to a Finite-Order Objective

For an order $T\geq 1$, define

$ J_{\mathrm{TailRL}}^{(T)}(\theta;x) := \sum_{k=1}^{T} \frac{\mathrm{Best\text{-}of\text{-}k}(\theta;x)-1}{k}.\tag{22} $

Its gradient is

$ \nabla_\theta J_{\mathrm{TailRL}}^{(T)}(\theta;x)

\sum_{k=1}^{T} \frac{1}{k} \nabla_\theta \mathrm{Best\text{-}of\text{-}k}(\theta;x).\tag{23} $

At $T=1$, this has the standard expected-reward gradient, while $J_{\mathrm{TailRL}}^{(T)}(\theta;x)\to J_{\mathrm{TailRL}}(\theta;x)$ as $T\to\infty$.

Equivalently, the finite-order gradient can be written directly in terms of tail probabilities:

$ \nabla_\theta J_{\mathrm{TailRL}}^{(T)}(\theta;x)

\int_0^1 \frac{1-(1-p_\theta(x, \tau))^T} {p_\theta(x, \tau)} \nabla_\theta p_\theta(x, \tau) , d\tau.\tag{24} $

The threshold weight equals $1$ at $T=1$ and approaches $1/p_\theta(x, \tau)$ as $T\to\infty$. Thus, increasing $T$ smoothly moves the objective from expected-reward RL toward population TailRL, progressively emphasizing reward levels that are harder to reach. Figure 3 visualizes this interpolation and compares it with PKPO.

For binary rewards, the finite-order family and its estimator reduce exactly to their MaxRL counterparts; see Appendix C.8.

4.2 Finite-Rollout Estimator

Critic-free methods express policy gradients as weighted combination of the score-function for different rollouts. In this section we seek to express the exact weights that allows us to give an unbiased estimate of the gradient of the order- $N$ truncated objective.

Suppose we draw $N$ independent rollouts $z_1, \ldots, z_N\sim\pi_\theta(\cdot\mid x)$. At each reward threshold, we divide one unit of credit equally among the sampled rollouts that exceed that threshold. A rollout accumulates this credit over every threshold below its reward:

$ \omega(r(x, z_i)) := \int_0^{r(x, z_i)} \frac{d\tau} {\sum_{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}}.\tag{25} $

Thresholds cleared by fewer rollouts therefore contribute more weight.

The weights can be computed exactly after sorting the rewards. Let $r_{(1)}\leq\cdots\leq r_{(N)}$ denote the sorted rewards and set $r_{(0)}:=0$. Then

$ \omega(r_{(i)})

\omega(r_{(i-1)}) + \frac{r_{(i)}-r_{(i-1)}}{N-i+1}, \qquad \omega(r_{(0)})=0.\tag{26} $

The resulting policy-gradient estimator has the standard score-function form:

$ g_{\mathrm{TailRL}}^{(N)}(x) := \sum_{i=1}^{N} \omega(r(x, z_i)), S(x, z_i).\tag{27} $

Thus, TailRL differs from a standard critic-free policy-gradient method only in how sampled rewards are converted into rollout weights.

########## {caption="Theorem 2: Unbiased finite-rollout estimator"}

For $N$ independent rollouts,

$ \mathbb{E}[g_{\mathrm{TailRL}}^{(N)}(x)]

\nabla_\theta J_{\mathrm{TailRL}}^{(N)}(\theta;x).\tag{28} $

Hence, the rollout budget determines which member of the TailRL family is optimized: one rollout recovers the expected-reward gradient, while larger rollout groups incorporate progressively higher Best-of- $k$ learning signals. This differs from REINFORCE, where increasing the rollout count reduces estimation variance without changing the underlying expected-reward objective.

Centered advantages.

In practice, we center the rollout weights within each group:

$ A_i := \omega(r(x, z_i))-\bar{\omega}, \qquad \bar{\omega} := \frac{1}{N}\sum_{j=1}^{N}\omega(r(x, z_j)).\tag{29} $

Centering reduces variance and allows TailRL to be used as a drop-in replacement for the advantage calculation in standard policy-gradient implementations. Because the baseline is estimated from the same rollout group, the centered estimator is unbiased for $\nabla_\theta J_{\mathrm{TailRL}}^{(N-1)}$ rather than $\nabla_\theta J_{\mathrm{TailRL}}^{(N)}$. Complete derivations and proofs are given in Appendix C.

5. Unifying Gradient Weight View

Section Summary: The section presents TailRL and standard expected reward maximization as members of a single family of objectives that differ only in how they weight the gradient contributions from tail probabilities. In this shared formulation, a scalar function φ determines the marginal value assigned to increasing the chance of exceeding any given reward threshold, yielding equal weighting for all thresholds under expected reward maximization but inverse-probability weighting under TailRL. The resulting view also encompasses the order-T truncation and PKPO, each with its own distinct gradient multiplier.

{width=60%}

To compare population-level TailRL with expected reward maximization, we look one step earlier. We express the gradients of TailRL and expected reward maximization under a unified view and ask how each objective up-weights its gradients. TailRL and expected reward maximization belong to a common family of objectives.

Consider a fixed input $x$ and a fixed parameters $\theta$ of our policy $\pi_{\theta}(\cdot \mid x)$. Recall that we can express the tail-probability as,

$ p_\theta(x, \tau):= \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)}!\left(r(x, z)>\tau\right)\tag{30} $

Its gradient $\nabla_\theta p_\theta(x, \tau)$ points in the direction that makes the tail-event more likely. Up to constants independent of $\theta$, they can be written in the common form they can be expressed as,

$ J_\phi(\theta;x):=\int_0^1\phi!\left(p_\theta(x, \tau)\right)d\tau,\tag{31} $

Here, $\phi(p)$ specifies how the objective values a tail-probability $p_{\theta}(x, \tau)$. Differentiating w.r.t $\theta$ gives

$ \nabla_\theta J_\phi(\theta;x)=\int_0^1\phi'!\left(p_\theta(x, \tau)\right)\nabla_\theta p_\theta(x, \tau), d\tau.\tag{32} $

\begin{tabular}{lcc}
\toprule
Objective & $\phi(p)$ & $\phi'(p)$ \\
\midrule
$J_{\mathrm{RL}}$ & $p$ & $1$ \\
$J_{\mathrm{TailRL}}^{(T)}$ & $-\sum_{\ell\le T}(1-p)^{\ell}/\ell$ & $\tfrac{1-(1-p)^{T}}{p}$ \\
$J_{\mathrm{TailRL}}$ & $\log p$ & $1/p$ \\
$J_{\mathrm{PKPO}}$ & $1-(1-p)^{k_{\mathrm{opt}}}$ & $k_{\mathrm{opt}}(1-p)^{k_{\mathrm{opt}}-1}$ \\
\bottomrule
\end{tabular}

The derivative $\phi'$ is therefore the gradient weight of the derivative of a tail-probability $p_{\theta}(x, \tau)$, and it does not introduce a new objective. It is the marginal value that the objective assigns to making that level more likely. The three objectives differ only in this weight (Figure 3 and Table 1).Expected reward maximization uses $\phi(p)=p$, so $\phi'(p)=1$: every tail-probability receives the same weight, regardless of how often the policy reaches it. TailRL uses $\phi(p)=\log p$, so $\phi'(p)=1/p$. Because $p_\theta(x, \tau)$ is non-increasing in $\tau$, this places greater weight on higher reward thresholds that the policy reaches rarely. The gradient of order- $T$ member of the truncated family is,

$ \nabla_\theta J_{\mathrm{TailRL}}^{(T)}(\theta;x)

\int_0^1 \frac{1-\left(1-p_\theta(x, \tau)\right)^T} {p_\theta(x, \tau)} \nabla_\theta p_\theta(x, \tau), d\tau.\tag{33} $

It up-weights the gradient of the tail probabilities as $\phi'(p)=\frac{1-\left(1-p\right)^T} {p}$, i.e. the multiplier in Equation 33. At $T=1$, this multiplier equals $1$, recovering the expected reward gradient. As $T\to\infty$, it approaches the tail-likelihood weight $1/p$. Expected reward maximization gives equal weight to the gradient of all tail-probabilities.

6. Experiments

Section Summary: The experiments evaluate TailRL by testing four theory-derived questions on whether its population objective is learnable, effective for rare high rewards, aligned with inference-time scaling, and resistant to suboptimal shortcuts. Four settings address these: ImageNet object localization to check convergence of finite-rollout estimators to the exact objective, Text-Maze for rare-reward behavior, GUI grounding for scaling, and code optimization for shortcut resistance, with comparisons to GRPO, RLOO, and PKPO. In the ImageNet task, population-level TailRL matches or exceeds direct supervision on metrics like CorLoc while finite-rollout gradients approach the true objective with larger rollout budgets.

We organize the experiments around four questions implied by the theory. [YSC: quickly recap the theory and itemize the 4 qs]

1. First, is the population-level TailRL objective a useful learning target, and does its finite-rollout estimator approach it as number of rollouts increases? (Section 4.1)
2. Second, does TailRL help specifically when high-reward rollouts are attainable but rare? (Section 3)
3. Third, does its alignment with Best-of- $k$ yield stronger inference-time scaling? (Section 3.1)
4. Finally, can TailRL prevent a common moderate-reward behavior from displacing rarer, better outcomes? (Section 3.1 and Section 3)

To answer these questions, we devise 4 experimental settings. We test the population level objective and its finite-rollouts approximation on a localization task in the ImageNet dataset (Section 6.1) . To understand the behavior of TailRL under rare, high reward rollouts, we consider a Text-Maze setting (Section 6.2). GUI grounding allows us to study the scaling behavior of models trained with TailRL as more inference compute in poured into the problem (Section 6.3) and finally, Code Optimization tests resistance to a safe but suboptimal shortcut (Section 6.4). Together, they test whether TailRL works for the reasons predicted by the theory, from the population objective to the behavior of the learned policy.

We compare TailRL with GRPO ([2]), RLOO ([3]), two popular group-based policy optimization algorithms, and PKPO [11] that maximizes Best-of- $k_{\mathrm{opt}}$ for an inference budget $k_{\mathrm{opt}}$ under pure on-policy policy gradient setup to avoid confounders.

6.1 ImageNet Object Localization

ImageNet object localization requires predicting a bounding box around an object of interest without classifying the object ([16]). This setting addresses three questions. First, how does reinforcement learning from a scalar reward compare with supervised objectives that directly observe the ground-truth bounding box? Second, does the finite rollout TailRL gradient estimator $g_{\mathrm{TailRL}}^{(N)}$ approach the population-level gradient $\nabla_\theta J_{\mathrm{TailRL}}$ as $N$ increases? Third, how does TailRL compare with the expected reward baselines at matched and smaller training rollout budgets?

Task and setup

For an input image $x$, a rollout $z$ is a bounding box drawn from the categorical policy of Figure 4, and the continuous reward $r(x, z)\in[0, 1]$ is its intersection-over-union (IoU) with the ground-truth box. We report CorLoc@ $\delta$, the fraction of input images for which the greedy prediction has IoU greater than $\delta$ ([17]); mean IoU; and Best-of- $k$ IoU, the largest IoU among $k$ inference rollouts.

Its worthwhile to note that since the policy induces a categorical distribution over the finite set of possible bounding boxes, we can evaluate the probability and IoU reward of every box. This gives us the exact reward distribution in closed form. Using this we can directly compute and optimize the population-level objective $J_{\mathrm{TailRL}}$. We also train supervised baselines that directly regress the ground-truth coordinates. Training and evaluation details are provided in Appendix H.

Comparison with direct supervision

Using only scalar IoU rewards, population-level TailRL matches or exceeds objectives that directly supervise the ground-truth coordinates (Figure 5). Among the supervised objectives, the combined L1+GIoU objective ([18]) used by DETR ([19]) is the strongest. TailRL achieves higher CorLoc@ $0.5$ and CorLoc@ $0.75$ than L1+GIoU while obtaining comparable mean IoU. It also outperforms the individual L1 and GIoU baselines across all reported metrics throughout training. These results show that under large training compute, optimizing a scalar continuous reward can compete with task-specific supervised objectives.

{width=50%}

Increasing training rollout budget

Increasing training rollouts, $N$ moves the finite rollout TailRL curves toward the exact population-level objective (Figure 7). At $N=1024$, TailRL closely tracks the population-level objective, while smaller rollout budgets remain progressively farther away. This ordering holds across CorLoc@ $0.5$, mean IoU, and Best-of- $1024$ IoU and other performance measures that we test for this experiment. We test this convergence directly at the gradient level in Figure 6. As $N$ increases, the cosine similarity between the sampled finite rollout gradient and the population-level gradient rises steadily toward exact agreement. This increasing alignment is consistent with the convergence predicted in Section 4.1. Increasing rollouts not only reduce the variance of the objective we are trying to estimate, but it also approximates a higher order truncated objective.

Comparison with RL baselines

At a matched budget of $N=1024$, TailRL outperforms GRPO and RLOO across all three metrics, despite every method receiving the same continuous IoU feedback. The gap does not close at smaller budgets: even at $N=16$, TailRL exceeds both baselines trained at $N=1024$, using $\tfrac{1}{64}$ as many training rollouts per input. TailRL also pareto dominates PKPO which maximizes expected maximum reward. With just $N=16$ training rollouts, it outperforms at CorLoc@ $0.5$ and mean IoU. At matched training compute, TailRL matches PKPO at Best-of- $1024$ reward, while significantly outperforming at mean IoU and CorLoc@ $0.5$.

6.2 Text-Maze Navigation from Low-Success Initial Policies

Next we examine how TailRL and other baselines compare when we vary the quality of the initialization policy. By varying the amount of supervised pretraining before doing RL post-training, we obtain a controlled range of initial policies with varying coverage over high reward attaining rollouts. We ask whether TailRL can learn from poor initialization of policies and how it compares against expected reward maximization baselines.

Task and setup

For an input $17\times17$ maze represented as text, a rollout is a token sequence describing a path. The continuous reward $r(x, z)\in[0, 1]$ measures proximity to the goal and path length relative to the shortest path (Figure 8). A rollout receives reward $1$ only when it reaches the goal along a shortest path, an event we call shortest-path success. Unsuccessful rollouts receive partial credit for ending closer to the goal, while successful rollouts receive more reward for shorter paths. We evaluate the post-trained policies on a held-out validation set of $1024$ mazes.

By varying the amount of supervised pretraining on goal-reaching trajectories, we obtain initial policies with shortest-path success rates ranging from approximately $1%$ down to $0.01%$. Starting from each checkpoint, we separately post-train policies with TailRL, GRPO, and PKPO ($k_{\mathrm{opt}}$). All methods use the same initial policy and $N=16$ unless stated otherwise. Model, reward, training, and evaluation details are provided in Appendix I.

{width=60%}

Learning from low-success initial policies

Figure 9 shows that RLOO, GRPO and TailRL behave similarly when the initial policy produces shortest-path successes frequently, but diverge as the initial success rate falls. Despite higher coverage of initial policy, PKPO underperforms TailRL at Pass@ $1$. The expected reward baselines fail to learn reliably in the low initial success regime. PKPO consistently improves Pass@ $1$ across the spectrum of initialization policy yet still under-performs TailRL at Pass@ $1$ even at the regime of poor policy initalization. Once the initial success rate rises beyond this regime, TailRL, RLOO and GRPO learn well and their differences narrow. GRPO's performance improves before RLOO, although the performance becomes seed dependent before it consistently starts to navigate the maze. The advantage of TailRL is therefore concentrated where high-reward rollouts are attainable but rare. Inference and training-rollout budget sweeps are reported in Appendix I.5.

6.3 GUI Grounding with Vision-Language Models

We next demonstrate the efficacy of TailRL on Vision Language Models (VLM). We consider a visual grounding task with verifiable rewards. Through this task, we show that models trained with TailRL benefit from inference-time sampling.

Task and setup: Given a screenshot and a natural-language instruction to perform a click, the VLM policy generates the coordinates of the click location. The continuous reward $r(x, z)\in[0, 2.5]$ combines proximity to the target, a bonus for clicking inside the target element, and a format bonus ([20]). We fine-tune Qwen2.5-VL-3B and Qwen2.5-VL-7B ([21]) on the GTA1 grounding corpus ([22]). The training configuration is identical across TailRL, GRPO, and RLOO except for the advantage estimator. We evaluate the resulting policies on ScreenSpot-Pro ([23]). Here, Pass@ $k$ is the probability that at least one of $k$ inference rollouts clicks inside the target element ([24]), while Best-of- $k$ reward is the largest continuous reward among those rollouts. The reward construction, training protocol and evaluation procedure are detailed in Appendix J.

Results: At both model scales, TailRL and RLOO achieve similar Pass@ $1$, but they substantially differ in how the learned policies respond to additional inference sampling (Figure 10). As inference rollouts $k$ increases, TailRL's Pass@ $k$ continues to rise, whereas RLOO plateaus considerably earlier; GRPO's Pass@ $k$ is inferior to TailRL and RLOO. TailRL leaves more inputs with a non-negligible probability of producing a successful click, so additional samples continue to reveal useful candidates.

We define the matching budget as the smallest evaluated value of $k$ at which TailRL reaches or exceeds a baseline's mean Pass@ $1024$. On ScreenSpot-Pro, at 3B, TailRL reaches RLOO's Pass@ $1024$ with $8$ rather than $1024$ inference rollouts, a $128$-fold reduction; at 7B it does so with $4$ rollouts, a $256$-fold reduction. A single TailRL rollout exceeds GRPO's mean Pass@ $1024$ at both model scales.

6.4 Code Runtime Optimization

We now ask a qualitatively different question: what happens when training is attracted to a safe but systematically suboptimal behavior hurting further exploration? Such behaviors provide a reliable moderate reward and can become stable solutions, even when rarer and riskier behaviors offer substantially better outcomes ([25, 26]). This creates a stress test for TailRL: whether it concentrates the policy on the dependable yet suboptimal shortcuts or improves the policy's coverage over high-reward tail.

{width=60%}

Task and setup

Each input is a slow C++ program from the PIE ([27]) corpus of competitive-programming. The LLM is prompted to write a faster yet correct version of the input program. A rollout is a rewritten program and is compiled and executed against the problem's test suite. Incorrect outputs receives zero reward otherwise receives a reward equal to the speedup over the input program. We measure speedup using gem5 time so that timing noise cannot create spurious improvements ([28, 29]). We post-train Qwen3-1.7B ([30]) with TailRL, GRPO, and RLOO using $N=16$ rollouts per program.

We report mean reward over all rollouts; density of Best-of- $k$ rewards at $k=1024$ ; and the fraction of rollouts that pass every test; and Best-of- $k$ reward density at $k=1024$. A policy that always reproduces its input obtains a mean reward of $1$ and passes all test cases. Full task, training, and evaluation details are provided in Appendix K.

Results

GRPO and RLOO rapidly converge toward the copying shortcut (Figure 12) as evidenced by sample rollouts (Appendix K.8). Their correctness rise above $98%$, while their mean rewards settle just below $1.0$. Their policy entropy collapses by one to two orders of magnitude over the same interval (Figure 25). Expected-reward training therefore converges to the most reliable mode of the reward distribution while eliminating the behavior to maximize coverage over excellent outputs.

TailRL follows a different trajectory. Rather than collapsing onto the guaranteed reward from copying the input, it maintains substantially higher entropy and continues producing risky rewrites. This lowers single-rollout correctness, but places more probability on programs that are both correct and meaningfully faster, raising mean reward to $2.92$, nearly three times the copying value. All methods use the same one-epoch training budget, and TailRL is still improving at step $300$; these are therefore matched-compute results rather than converged endpoints. On the held-out test set the trained policies separate sharply: TailRL's mean Best-of- $1024$ speedup is $7.7\times$ against $0.98\times$ for GRPO and $0.96\times$ for RLOO, whose best rollouts never beat the input they reproduce (Figure 12, middle; Figure 26).

7. Related Work

Section Summary: Recent reinforcement-learning methods for training reasoning models mostly maximize expected reward using practical policy-gradient variants such as GRPO and RLOO, while a smaller set of approaches instead target success probabilities, Pass@k metrics, or other fixed thresholds. TailRL differs by directly changing the training objective to integrate log tail-probabilities over every reward level, which produces harmonic combinations of best-of-k terms and recovers earlier binary-reward methods exactly. This built-in weighting also helps maintain rare high-reward behaviors without separate diversity terms or learned critics, setting it apart from risk-sensitive or distributional reinforcement learning.

Objectives beyond expected reward

Reinforcement-learning post-training for reasoning and agentic models still largely maximizes expected reward ([31, 32]). GRPO ([2]) and RLOO ([3]) are practical, critic-free variants of the score-function policy gradient ([1]). RLOO changes the baseline, while GRPO applies a common normalization to the update for each input; neither changes the relative weighting of reward levels within that input (Section 5). TailRL changes the objective instead. Closest to our work, MaxRL maximizes the log-probability of success for binary rewards and decomposes its gradient into a harmonic sum of Pass@ $k$ gradients ([14]). PKPO derives unbiased estimators for a chosen Pass@ $k$ objective and its continuous counterpart, Best-of- $k$ ([11]); related methods directly optimize a selected inference-time metric ([33, 12]) or study objectives defined by monotone transforms of success probability ([34]). These approaches select a threshold, transform, or inference budget. TailRL instead integrates log tail-probability over all reward thresholds, yielding harmonic combinations of Best-of- $k$ objectives and recovering MaxRL exactly for binary rewards.

Coverage and tail-sensitive reinforcement learning

Expected-reward training can narrow the policy distribution and remove rare, high-reward behavior, an effect studied mechanistically ([6]) and observed at large sampling budgets ([7, 10]). Rather than adding a separate diversity regularizer, TailRL addresses this through the objective itself by weighting each reward level inversely by how often the policy reaches it. TailRL is also distinct from distributional and risk-sensitive reinforcement learning, which learn a return distribution through a critic or optimize a tail statistic at a chosen risk level ([35, 36]). TailRL uses no learned critic: its policy-gradient weights are computed directly from each rollout group, and it integrates over all reward thresholds rather than fixing one risk level, which can otherwise overlook rare successes ([37]). We discuss further connections to exploration, sample allocation, threshold decompositions of continuous rewards, and the evaluated domains in Appendix B.

8. Conclusion

Section Summary: TailRL is a new training method that treats a continuous reward signal not as a number to average, but as a series of success thresholds; it trains a model to raise the odds of clearing a randomly chosen threshold on any given attempt. The approach proved especially helpful in situations where truly high-reward outcomes were scarce or where ordinary training tended to settle on a mediocre pattern, allowing the system to learn more steadily from rare successes and to keep improving with extra samples. In essence, the method offers a straightforward way to make models more reliable at reaching better results across a range of difficulty levels.

We introduced TailRL, a likelihood objective for continuous rewards that maximizes the expected log-probability of exceeding a uniformly sampled reward threshold. It recovers MaxRL exactly for binary rewards, decomposes harmonically over Best-of- $k$ gradients, and admits a simple, critic-free finite-rollout estimator. Across four settings, its gains were largest when high-reward rollouts were rare or when training was drawn toward a common but suboptimal behavior. In these regimes, TailRL learned more reliably from rare outcomes, benefited more from additional training and inference samples, and avoided suboptimal collapse. More broadly, a continuous reward is more than a scalar to average: it defines a family of success events, one at every reward level. TailRL provides a practical way to optimize their likelihoods.

Acknowledgements

Section Summary: This research received key computing resources from the DeltaAI system, funded by the National Science Foundation and the State of Illinois through the ACCESS program, plus extra support from Sooth Labs and partial grants from the NSF and companies like Stack AV and Skylark Labs. Several team members, especially Brett Bode, helped make effective use of these tools to finish the work on time. The authors also thank many colleagues who reviewed earlier drafts and professors who offered ongoing advice and suggestions.

This research used the DeltaAI advanced computing and data resource ([38]), which is supported by the National Science Foundation under award OAC-2320345 and by the State of Illinois. DeltaAI is a joint effort of the University of Illinois Urbana-Champaign and its National Center for Supercomputing Applications. These resources were used through the Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support (ACCESS) program ([39]). Overall, this project used ACCESS allocations CIS250426, CIS260353, CIS260522, CIS260557, CIS260677, CIS260678, and CIS260679. We are especially grateful to Brett Bode of the NCSA Delta Support team, whose assistance in effectively using the Delta cluster was critical to completing this work on schedule. We would like to extend our sincere gratitude to Sooth Labs for their generous support by granting us their compute resources. This work was partially supported by the National Science Foundation under Grants CCF-2106778. Fahim and Shrinivas were funded in part by Stack AV and Skylark Labs

We are grateful to Sumukh Aithal, Ben Freed, Surgan Jandial, Sreyas Venkatraman, Kartik Sharma, Elton Lobo, Parv Maheshwari, Rhea Basappa, Srinath Ravi, Rishubh Parihar, Harsh Rangwani, Chaitanya Chawla, and Mayank Mishra for carefully reviewing earlier drafts and providing valuable feedback. We also thank Rohit Sonkar, Anoushka Alavilli, Jiayu Chen, and Mineui Hong from the CMU Auton Lab, and Lawrence Jang from Russ lab for their helpful feedback that improved the quality of the draft. The authors would also like to extend their gratitude to Prof. Yaser Sheikh and Prof. Yonatan Bisk for helpful discussions and suggestions throughout this work.

Appendix

Section Summary: The appendix begins with a complete notation table that defines every symbol appearing in the paper. It then supplies an expanded related-work discussion that fills out the brief overview given in the main text, covering reinforcement-learning post-training methods, alternatives to simply maximizing average reward, inference-time selection techniques, how standard training tends to reduce output diversity, exploration strategies, and distributional or risk-sensitive approaches to reinforcement learning. The section also references additional supporting literatures on threshold-based reward decompositions and the specific application domains evaluated in the study.

etocdepthtag.tocappendix

Appendix Contents

etocsettagdepthmaintextnone etocsettagdepthappendixsubsubsection etocsettocstyle{}

A. Notation

Table 2 collects every symbol used in the paper. One symbol, one meaning is strictly enforced.

::: {caption="Table 2: Notation."}

:::

B. Extended Related Work

This section gives the full related-work discussion summarized in Section 7, together with several literatures not covered there: inference-time selection as its own topic, exploration and sample-allocation methods, threshold decompositions of continuous rewards, and the literatures behind each evaluated domain.

Reinforcement learning post-training

Reinforcement learning now drives post-training for reasoning and agentic models, and almost all of it maximizes expected reward. The recipe descends from learning against human preferences ([40, 31]) and, once verifiable rewards replaced learned reward models, produced the current generation of reasoning systems ([32, 41, 42, 43]). Practical estimators have converged on critic-free group-relative updates: GRPO standardizes rewards within a group ([2]), RLOO subtracts a leave-one-out baseline ([3, 44]), and later variants adjust clipping, normalization, and the level at which the ratio is formed ([4, 5, 45]). Every one of these estimators traces back to the score-function policy gradient ([1, 46, 47]) and differs from the others in variance rather than in target. They share one population objective, the mean of the reward distribution, and in the weight view of Section 5 they share the flat gradient weight $\phi'(p)=1$. TailRL changes that target rather than the variance around it.

Objectives beyond the mean

A recent line of work replaces the mean with a nonlinear functional of the policy's success probability, and TailRL belongs to it. MaxRL maximizes the log-probability of success for binary rewards and expands that logarithm into a harmonically weighted sum of Pass@ $k$ gradients ([14]). PKPO derives unbiased estimators for Pass@ $k$ and for its continuous generalization, the expected maximum of $k$ rewards ([11]), while other work optimizes a chosen inference-time metric directly ([33, 12]) or reweighs rollouts by problem difficulty ([13]). [34] unify much of this by showing that popular algorithms implicitly ascend a monotone transform of the success probability, and [48] recast the resulting Pass@ $k$ advantage weights as surrogate reward maximization. Related objectives target diversity ([49, 50]), risk sensitivity ([51]), and rare-success amplification ([52, 53]). Contemporaneous works extend two pieces of this picture: RL2ML generalizes the harmonic coefficient for binary rewards ([54]), and OrderGrad estimates gradients of L-statistics over sorted rewards ([55]). Each of these methods commits to one threshold, one transform, or one order statistic. TailRL instead integrates the log tail-probability over every threshold, so its order- $T$ truncation is a harmonic combination of Best-of- $k$ objectives and reduces to MaxRL exactly when the reward is binary.

Inference-time scaling and selection

Drawing many rollouts and keeping the best one has become a standard axis of deployment compute, which makes Pass@ $k$ and Best-of- $k$ the metrics that matter at inference. Repeated sampling raises coverage predictably over several orders of magnitude ([56, 57]), and allocating compute at test-time can beat allocating it to parameters ([58]). Selecting among the samples requires either agreement ([59]), a reward function ([60, 61]), or execution ([62]), and the unbiased Pass@ $k$ estimator we use comes from this literature ([24]). Selection also has limits, since optimizing hard against an imperfect reward function eventually degrades true quality ([63]). This body of work measures or exploits the upper tail after training has finished. TailRL makes that same upper tail the training objective.

Distribution narrowing under expected reward training

Expected-reward post-training reliably sharpens the policy, which is the failure mode TailRL is designed to resist. [6] characterize this as an entropy mechanism in which the policy-gradient covariance term stays positive and entropy falls monotonically without intervention. Measured at large sampling budgets, the effect is visible as a narrowing of what the policy can produce: base models can match or exceed post-trained models on Pass@ $k$ at large $k$ ([7]), the reachable support changes little ([8, 64]), and diversity drops across settings ([10, 9]). Regularization is one reported cause, since a KL penalty to a reference policy can itself favor mode collapse ([65]). A parallel line intervenes on entropy directly, through token-level selection ([66]), entropy-aware bonuses ([67, 68]), or smoothing ([69]), and these interventions show that coverage can be partly recovered. TailRL takes a different route and reweights reward thresholds by the inverse of how often the policy reaches them (tail-probability), so rare high-reward threshold keep influence without an added regularizer.

Exploration and sample allocation

Exploration methods change which rollouts a learner sees, whereas TailRL changes how a fixed group of rollouts is weighted. Classical approaches add bonuses from visitation counts, prediction error, or information gain ([70, 71, 72]). Their language-model counterparts penalize repeated outcomes ([73]), reward novelty in representation space ([74, 75]), widen the rollout budget ([76]), or schedule problems by difficulty ([77, 78]). Closest to us, Reinforce-Ada allocates samples adaptively under a non-linear objective and arrives at a difficulty-prioritizing weighted estimator ([79]).

Distributional and risk-sensitive reinforcement learning

Modeling a whole reward or return distribution is not new, so it is worth stating precisely what TailRL does differently. Distributional reinforcement learning learns the return distribution as a critic, representing it categorically ([35]) or through quantiles ([80, 81, 82]), and propagates it with a distributional Bellman operator. Risk-sensitive methods optimize a tail functional of that distribution, most often the conditional value at risk ([36, 83, 84, 85]). Two differences separate these from TailRL. First, TailRL carries no critic and performs no bootstrapping: the reward function supplies the reward in one step, and the tail probabilities appear only inside a policy-gradient weight computed from the group itself. Second, risk measures fix a single risk level, and a fixed level can make a learner blind to rare successes ([37]), whereas TailRL integrates the log tail-probability uniformly across every threshold.

Threshold decompositions of continuous rewards

Splitting a continuous reward into a family of binary threshold events is a classical device in supervised learning, and it is the direct ancestor of the decomposition in Figure 2. Cumulative-link models predict $P(y > j)$ at each threshold ([86]), and reductions to extended binary classification train one classifier per threshold and reassemble the prediction ([87, 88]). Neural versions inherit the same structure, with multiple binary outputs ([89]) and rank-consistency constraints across cuts ([90, 91]). [92] carry the idea into policy optimization for discrete rewards. TailRL is the policy-gradient counterpart for continuous rewards: the threshold $\tau$ plays the role of the ordinal cut, the indicator $\mathbb{1}_{{r(x, z)>\tau}}$ plays the role of the binary label, and the decomposition runs over a continuum rather than a finite set of cuts.

Reinforcement learning in the evaluated domains

Our four settings each connect to an established line of work. Bounding-box prediction is normally trained by direct supervision on coordinates, using an $L1$ term, a generalized intersection-over-union term, or the combination adopted by DETR ([18, 19]), against which Section 6.1 compares a purely reward-driven policy ([16, 17]). GUI grounding has recently been posed as reinforcement learning with a dense point reward on top of vision-language backbones ([21, 22, 20, 93]) and evaluated on high-resolution professional interfaces ([23]). Code generation has long used execution feedback as a reward signal ([94, 95, 96, 97, 98, 99]), and optimizing runtime rather than correctness requires both a corpus of slow programs and a deterministic timing oracle ([27, 28]). That last setting also admits a reward-preserving shortcut, returning the input unchanged, which is an instance of the reward gaming characterized by [25]. Section 6.4 uses it to separate an objective that settles for a dependable moderate outcome from one that keeps searching for a rare better one.

C. Supporting Results for the TailRL Gradient Estimator

This section supplies the regularity conditions and proofs used in Section 4. We continue to work at a fixed input $x$ and assume $r(x, z)\in[0, 1]$.

C.1 Regularity of the TailRL Gradient

The derivations of Section 4 rest on three operations. The score-function identity differentiates the tail-probability under an expectation over the policy's rollouts. The second operation moves a gradient from outside the threshold integral to inside it. The third swaps the order of the threshold integral and the rollout expectation. Each operation exchanges two limits, and each exchange is valid once the quantity being moved is bounded by something with a finite integral. We state one assumption for each operation, justify each in turn, and then record the lemma that licenses all three. Throughout, fix an input $x$, let the rollouts take values in a countable set, and let $\Theta$ be an open set of parameters.

########## {caption="Assumption 3: Smooth policy"}

The support of $\pi_\theta(\cdot\mid x)$ is the same for every $\theta\in \Theta$, each probability $\pi_\theta(z\mid x)$ is differentiable in $\theta$ on $\Theta$, and

$ \sum_z \sup_{\theta\in \Theta}, \bigl|\nabla_\theta\pi_\theta(z\mid x)\bigr| ;<; \infty.\tag{34} $

Assumption 3 is the classical hypothesis behind likelihood-ratio gradient estimators ([1, 100]): it is the interchange condition of [101], and [102] survey it as the standing assumption of the score-function estimator class. It holds by inspection for the policies of this paper: a softmax policy has a fixed finite support, its rollout probabilities are differentiable in $\theta$, and a finite sum of continuous gradient norms is bounded on a bounded $\Theta$.

########## {caption="Assumption 4: Finite objective"}

The tail-likelihood is finite on $\Theta$: $\int_0^1\bigl|\log p_\theta(x, \tau)\bigr|, d\tau<\infty$ for every $\theta\in \Theta$.

Assumption 4 is the substantive assumption, and full support is what delivers it. A softmax policy assigns strictly positive probability to every rollout in its finite support, and the auto-regressive token policies of this paper, softmax at every step with bounded generation length, are of this form. Let $z^\star$ be a rollout of maximal reward on $x$ and normalize that maximum to $1$. Every threshold $\tau\in[0, 1)$ is then cleared at least by $z^\star$, so the tail-probability is squeezed between two positive constants:

$ 0 ;<; \pi_\theta(z^\star\mid x) ;\le; p_\theta(x, \tau) ;\le; 1, \qquad \int_0^1\bigl|\log p_\theta(x, \tau)\bigr|, d\tau ;\le; -\log\pi_\theta(z^\star\mid x) ;<;\infty.\tag{35} $

The bound is uniform over any bounded parameter set $\Theta$, since $-\log\pi_\theta(z^\star\mid x)$ is continuous in $\theta$. If no rollout attains reward $1$, the same squeeze holds over thresholds below the largest attainable reward, and the threshold integral is read over that range. One consequence is used repeatedly below: the finiteness of the integral forces $p_\theta(x, \tau)>0$ for almost every $\tau$, so the logarithm and every ratio with $p_\theta(x, \tau)$ in its denominator are defined.

########## {caption="Assumption 5: Bounded weighted score"}

There is a constant $C<\infty$ such that, for almost every $\tau$,

$ \sup_{\theta\in \Theta}; \frac{\mathbb{E}{z\sim\pi\theta(\cdot\mid x)} !\left[\mathbb{1}_{{r(x, z)>\tau}}, |S(x, z)|2\right]} {p\theta(x, \tau)} ;\le; C.\tag{36} $

Assumption 5 follows from the bounded-reward assumption $\sup_{\theta\in \Theta}\sup_{z}|S(x, z)|\le C$ routine in policy-gradient convergence analyses ([103, 104, 105]), since $\mathbb{E}{z}!\left[\mathbb{1}{{r(x, z)>\tau}}, |S(x, z)|\right]\le C, p_\theta(x, \tau)$. Scores are bounded for the softmax policies of this paper whenever the logits have bounded gradients.

With the assumptions justified, the lemma states only its conclusion.

########## {caption="Lemma 6: Regularity for the TailRL gradient"}

Under Assumption 3, Assumption 4, and Assumption 5, at every $\theta\in \Theta$, the population objective and every finite truncation are differentiable, and the score-function identity and every exchange of a gradient, threshold integral, and rollout expectation in Section 4 and Section 4.2 are valid.

Proof: The proof verifies the three operations in order, at an arbitrary $\theta\in \Theta$.

The score-function identity. Fix a threshold $\tau$. The tail-probability is the sum of the policy probabilities over the rollouts that clear it,

$ p_\theta(x, \tau)

\sum_z \mathbb{1}{{r(x, z)>\tau}}, \pi\theta(z\mid x).\tag{37} $

By Assumption 3, every term of the differentiated series is bounded by the summable envelope of Equation 34, so the gradient of the sum is the sum of the gradients.

$ \nabla_{\theta} p_\theta(x, \tau)

\sum_z \mathbb{1}{{r(x, z)>\tau}}, \nabla{\theta}\pi_\theta(z\mid x).\tag{38} $

Substituting $\nabla_\theta\pi_\theta(z\mid x)=\pi_\theta(z\mid x), S(x, z)$ in Equation 38 turns the differentiated sum into the score-function identity

$ \nabla_\theta p_\theta(x, \tau)

\mathbb{E}{z\sim\pi\theta(\cdot\mid x)} !\left[\mathbb{1}_{{r(x, z)>\tau}}, S(x, z)\right].\tag{39} $

Moving the gradient inside the threshold integral. The triangle inequality applied to 39, followed by Equation 36, bounds the log-gradient at every threshold:

$ \bigl|\nabla_\theta\log p_\theta(x, \tau)\bigr|

\frac{|\nabla_\theta p_\theta(x, \tau)|}{p_\theta(x, \tau)} \le \frac{\mathbb{E}{z}!\left[\mathbb{1}{{r(x, z)>\tau}}, |S(x, z)|\right]}{p_\theta(x, \tau)} \le C.\tag{40} $

The objective is finite by Assumption 4, and the gradient of its integrand is bounded by the constant $C$, so the gradient moves inside the threshold integral:

$ \nabla_\theta J_{\mathrm{TailRL}}(\theta;x)

\int_0^1 \frac{\nabla_\theta p_{\theta}(x, \tau)}{p_{\theta}(x, \tau)} , d\tau.\tag{41} $

The truncations need nothing new. The order- $N$ threshold multiplier is a finite geometric sum and is therefore bounded,

$ \frac{1-\left(1-p_\theta(x, \tau)\right)^N}{p_\theta(x, \tau)}

\sum_{j=0}^{N-1}\left(1-p_\theta(x, \tau)\right)^j \le N,\tag{42} $

so the gradient of the truncated integrand is bounded by $NC$ and the same argument differentiates $J_{\mathrm{TailRL}}^{(N)}$.

Swapping the threshold integral and the rollout expectation. Integrating Equation 36 over the thresholds gives

$ \int_0^1 \mathbb{E}{z\sim\pi{\theta}(\cdot\mid x)} !\left[\frac{\mathbb{1}{{r(x, z)>\tau}}}{p{\theta}(x, \tau)} , |S(x, z)| \right] d\tau \le C <\infty,\tag{43} $

so the integrand is absolutely integrable and Fubini's theorem permits taking the threshold integral and the rollout expectation in either order. The truncated multiplier never exceeds $1/p_{\theta}(x, \tau)$, so the truncated weighted score-function is bounded by the integrand of Equation 43 and the same swap applies at every order $N$.

The countability of the rollout space is inessential: for a policy with densities over a continuous rollout-space, the sum in Equation 37 becomes an integral against a common reference measure and the proof is unchanged.

C.2 Derivation of the Rollout-Weight Forms

We derive the population rollout-weight form of the TailRL gradient and its order- $N$ truncation, Equation 24. Because the tail-likelihood averages per-level log-likelihoods, its gradient is an average of per-level likelihood gradients,

$ \nabla_\theta J_{\mathrm{TailRL}}(\theta;x)

\int_0^1 \frac{\nabla_\theta p_\theta(x, \tau)} {p_\theta(x, \tau)} , d\tau

\mathbb{E}{\tau \sim \mathrm{U}[0, 1]}\left[\frac{\nabla\theta p_\theta(x, \tau)} {p_\theta(x, \tau)}\right].\tag{44} $

At a fixed threshold, the log-derivative trick expresses the pass-rate gradient as a score-function expectation:

$ \nabla_\theta p_\theta(x, \tau)

\mathbb{E}{z\sim\pi\theta(\cdot\mid x)} !\left[\mathbb{1}_{{r(x, z_j)>\tau}}S(x, z) \right].\tag{45} $

Substituting into Equation 44 writes the population gradient as a double expectation,

$ \nabla_\theta J_{\mathrm{TailRL}}(\theta;x)

\mathbb{E}{\tau\sim\mathrm{U}[0, 1]}\left[\mathbb{E}{z\sim \pi_{\theta}(\cdot\mid x)} !\left[\frac{\mathbb{1}{{r(x, z)>\tau}}} {p\theta(x, \tau)} S(x, z) \right]\right],\tag{46} $

and the integrability condition of Lemma 6 permits Fubini's theorem to exchange the two. The inner threshold integral then runs over exactly the thresholds cleared by the rollout, gives us Equation 47 as restated below.

$ \nabla_\theta J_{\mathrm{TailRL}}(\theta;x)

\mathbb{E}z !\left[\left(\int_0^{r(x, z)} \frac{1} {p\theta(x, \tau)} , d\tau \right) S(x, z) \right],\tag{47} $

The order- $N$ member follows the same route. Differentiating Equation 22 and summing the finite geometric series gives

$ \nabla_\theta J_{\mathrm{TailRL}}^{(N)}(\theta;x)

\int_0^1 \left(\frac{1-\left(1-p_\theta(x, \tau)\right)^N} {p_\theta(x, \tau)} \right) \nabla_\theta p_\theta(x, \tau) , d\tau,\tag{48} $

and substituting Equation 45 and exchanging the threshold integral with the rollout expectation restricts the integral to the thresholds below the rollout's reward,

$ \nabla_\theta J_{\mathrm{TailRL}}^{(N)}(\theta;x)

\mathbb{E}z !\left[\left(\int_0^{r(x, z)} \frac{1-\left(1-p\theta(x, \tau)\right)^N} {p_\theta(x, \tau)} , d\tau \right) S(x, z) \right],\tag{49} $

which is Equation 24.

C.3 Best-of-k Decompositions and Probabilistic Interpretations

We prove the finite and population Best-of- $k$ decompositions stated in Section 3. It also shows that threshold weighting is equivalent to rescaling the reward axis. We continue to work at a fixed input $x$ and assume $r(x, z)\in[0, 1]$. The gradient statements use the regularity conditions of Lemma 6.

C.3.1 Layer-Cake Form of Best-of-k

Let $z_1, \ldots, z_k\overset{\mathrm{i.i.d.}}{\sim}\pi_\theta(\cdot\mid x)$ and write $R_i:=r(x, z_i)$ and $M_k:=\max_{1\leq i\leq k}R_i$. Since $M_k\in[0, 1]$, the layer-cake identity gives

$ \mathbb{E}[M_k]

\int_0^1 \operatorname{Pr}(M_k>\tau), d\tau.\tag{50} $

The maximum fails to clear $\tau$ exactly when all $k$ rollouts fail it. By independence,

$ \operatorname{Pr}(M_k\leq\tau)

\left(1-p_\theta(x, \tau)\right)^k.\tag{51} $

Therefore,

$ \text{Best-of-}k(\theta;x)

\int_0^1 \left[1-\left(1-p_\theta(x, \tau)\right)^k \right] d\tau.\tag{52} $

C.3.2 Finite Harmonic Decomposition

########## {caption="Proposition 7: Harmonic Best-of- $k$ expansion of the finite objective"}

For every truncation order $T\geq1$,

$ J_{\mathrm{TailRL}}^{(T)}(\theta;x)

\sum_{k=1}^{T} \frac{\text{Best-of-}k(\theta;x)-1}{k}.\tag{53} $

Proof: Exchange the finite sum in Equation 22 with the threshold integral:

$ \begin{aligned} J_{\mathrm{TailRL}}^{(T)}(\theta;x) &= -\sum_{k=1}^{T} \frac{1}{k} \int_0^1 \left(1-p_\theta(x, \tau)\right)^k , d\tau \nonumber\ &= \sum_{k=1}^{T} \frac{1}{k} \left(\int_0^1 \left[1-\left(1-p_\theta(x, \tau)\right)^k\right] , d\tau -1 \right). \end{aligned} $

The integral in parentheses is $\text{Best-of-}k(\theta;x)$ by Equation 52.

########## {caption="Proposition 8: Harmonic Best-of- $k$ expansion of the finite gradient"}

Under Lemma 6, for every $T\geq1$,

$ \nabla_\theta J_{\mathrm{TailRL}}^{(T)}(\theta;x)

\sum_{k=1}^{T} \frac{1}{k} \nabla_\theta\text{Best-of-}k(\theta;x).\tag{54} $

Equivalently,

$ \nabla_\theta J_{\mathrm{TailRL}}^{(T)}(\theta;x)

\int_0^1 \frac{1-\left(1-p_\theta(x, \tau)\right)^T} {p_\theta(x, \tau)} \nabla_\theta p_\theta(x, \tau) , d\tau,\tag{55} $

where the ratio is interpreted by continuity as $T$ when $p_\theta(x, \tau)=0$.

Proof: Differentiating Equation 53 term by term gives Equation 54. Differentiating Equation 22 under the integral gives

$ \begin{aligned} \nabla_\theta J_{\mathrm{TailRL}}^{(T)}(\theta;x) &= \int_0^1 \left[\sum_{k=1}^{T} \left(1-p_\theta(x, \tau)\right)^{k-1} \right] \nabla_\theta p_\theta(x, \tau) , d\tau \nonumber\ &= \int_0^1 \frac{1-\left(1-p_\theta(x, \tau)\right)^T} {p_\theta(x, \tau)} \nabla_\theta p_\theta(x, \tau) , d\tau, \end{aligned} $

where the second equality uses the finite geometric-series identity.

At $T=1$, Equation 53 gives

$ J_{\mathrm{TailRL}}^{(1)}(\theta;x)

\text{Best-of-}1(\theta;x)-1

J_{\mathrm{RL}}(\theta;x)-1.\tag{56} $

Also, since $0\leq(1-p_\theta(x, \tau))^k\leq1$,

$ -H_T \leq J_{\mathrm{TailRL}}^{(T)}(\theta;x) \leq 0, \qquad H_T:=\sum_{k=1}^{T}\frac{1}{k}.\tag{57} $

C.3.3 Population Harmonic Decomposition

Proof of Theorem 1: For each threshold, define

$ s_T(\tau) := \sum_{k=1}^{T} \frac{\left(1-p_\theta(x, \tau)\right)^k}{k}.\tag{58} $

The sequence $s_T(\tau)$ is nondecreasing in $T$. The Maclaurin series gives the extended-real pointwise limit

$ \lim_{T\to\infty}s_T(\tau)

-\log p_\theta(x, \tau).\tag{59} $

The monotone convergence theorem therefore gives

$ \begin{aligned} \lim_{T\to\infty} J_{\mathrm{TailRL}}^{(T)}(\theta;x) &= -\int_0^1 \lim_{T\to\infty}s_T(\tau) , d\tau \nonumber\ &= \int_0^1 \log p_\theta(x, \tau) , d\tau

J_{\mathrm{TailRL}}(\theta;x). \end{aligned}\tag{60} $

Combining this limit with Equation 53 yields

$ J_{\mathrm{TailRL}}(\theta;x)

\sum_{k=1}^{\infty} \frac{\text{Best-of-}k(\theta;x)-1}{k}\tag{61} $

whenever the population objective is finite.

For the gradients, define

$ w_T(p) := \frac{1-(1-p)^T}{p}

\sum_{j=0}^{T-1}(1-p)^j.\tag{62} $

For every $p>0$, $w_T(p)\uparrow1/p$, and $0\leq w_T(p)\leq1/p$. By Lemma 6,

$ \frac{\left|\nabla_\theta p_\theta(x, \tau)\right|} {p_\theta(x, \tau)} \leq C\tag{63} $

for almost every threshold and some finite $C$. Dominated convergence applied to 55 gives

$ \begin{aligned} \lim_{T\to\infty} \nabla_\theta J_{\mathrm{TailRL}}^{(T)}(\theta;x) &= \int_0^1 \frac{\nabla_\theta p_\theta(x, \tau)} {p_\theta(x, \tau)} , d\tau \nonumber\ &= \nabla_\theta J_{\mathrm{TailRL}}(\theta;x). \end{aligned} $

The finite gradient identity then identifies this limit with $\sum_{k=1}^{\infty}k^{-1}\nabla_\theta\text{Best-of-}k(\theta;x)$.

C.3.4 Threshold Weighting as Reward Reparameterization

The uniform threshold distribution in Equation 12 is the simplest member of a weighted family. Let $w:[0, 1]\to(0, \infty)$ be a fixed density satisfying $\int_0^1w(\tau), d\tau=1$, and define

$ J_w(\theta;x) := \int_0^1 w(\tau) \log p_\theta(x, \tau) , d\tau.\tag{64} $

########## {caption="Proposition 9: Threshold weighting is reward-axis rescaling"}

Define

$ F_w(t) := \int_0^t w(s), ds, \qquad \widetilde{r}(x, z):=F_w!\left(r(x, z)\right).\tag{65} $

Then $F_w$ is a strictly increasing map from $[0, 1]$ to $[0, 1]$, and

$ J_w(\theta;x)

\int_0^1 \log \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)} !\left(\widetilde{r}(x, z)>u\right) , du.\tag{66} $

Thus, weighted TailRL on $r$ is exactly uniform TailRL on the monotone rescaling $\widetilde{r}=F_w(r)$.

Proof: Since $w$ is positive and integrates to one, $F_w$ is strictly increasing with $F_w(0)=0$ and $F_w(1)=1$. For $u\in[0, 1]$,

$ \begin{aligned} \operatorname{Pr}!\left(\widetilde{r}(x, z)>u\right) &= \operatorname{Pr}!\left(F_w(r(x, z))>u\right) \nonumber\ &= \operatorname{Pr}!\left(r(x, z)>F_w^{-1}(u)\right)

p_\theta!\left(x, F_w^{-1}(u)\right). \end{aligned} $

Therefore,

$ \begin{aligned} \int_0^1 \log \operatorname{Pr}!\left(\widetilde{r}(x, z)>u\right)du &= \int_0^1 \log p_\theta!\left(x, F_w^{-1}(u)\right)du \nonumber\ &= \int_0^1 w(\tau)\log p_\theta(x, \tau)d\tau, \end{aligned} $

where the last equality uses the substitution $u=F_w(\tau)$.

The proposition shows that choosing a threshold density is equivalent to choosing a monotone coordinate system for reward quality. Uniform weighting corresponds to the original normalized reward axis and introduces no additional function or hyperparameter. A nonuniform weighting may still be useful when a task provides a preferred reward scale, but selecting or learning that scale is outside the scope of this work.

C.3.5 Recovery of MaxRL on Binary Rewards

Proof of Equation 16: If $r(x, z)\in{0, 1}$, then for every $\tau\in[0, 1)$,

$ {r(x, z)>\tau}

{r(x, z)=1}.\tag{67} $

Therefore $p_\theta(x, \tau)=q_\theta(x)$ for every nontrivial threshold, and

$ J_{\mathrm{TailRL}}(\theta;x)

\int_0^1\log q_\theta(x), d\tau

\log q_\theta(x).\tag{68} $

The same substitution in the finite objective gives

$ J_{\mathrm{TailRL}}^{(T)}(\theta;x)

-\sum_{k=1}^{T} \frac{\left(1-q_\theta(x)\right)^k}{k},\tag{69} $

which is the order- $T$ Maclaurin truncation of MaxRL. Finally, the maximum of $k$ binary rewards equals one exactly when at least one rollout succeeds, so $\text{Best-of-}k(\theta;x)=\mathrm{Pass@}k(\theta;x)$.

C.4 Harmonic Best-of-k Expansion of the Tail-Likelihood

This section proves that the truncated objective is a partial sum of Best-of- $k$ objectives with harmonic coefficients, and that the tail-likelihood is the full series. Since the maximum of $k$ rewards clears a threshold unless all $k$ rollouts fail it, by layer cake identity,

$ \text{Best-of-}k(\theta;x)

\mathbb{E}\Big[\max_{1\le i\le k} r(x, z_i)\Big]

\int_0^1 \Big[1-\big(1-p_\theta(x, \tau)\big)^{k}\Big], d\tau .\tag{70} $

########## {caption="Proposition 10: Harmonic Best-of- $k$ expansion of the objective"}

Fix an input $x$ and a parameter $\theta$. For every truncation order $T \ge 1$,

$ J^{(T)}_{\mathrm{TailRL}}(\theta;x)

\sum_{k=1}^{T} \frac{1}{k}\Big(\text{\emph{Best-of-}}k(\theta;x) - 1\Big),\tag{71} $

and if $J_{\mathrm{TailRL}}(\theta;x) > -\infty$, the same identity holds for the full series,

$ J_{\mathrm{TailRL}}(\theta;x)

\sum_{k=1}^{\infty} \frac{1}{k}\Big(\text{\emph{Best-of-}}k(\theta;x) - 1\Big).\tag{72} $

Proof: We prove the finite identity first and obtain the series as its limit. Start from the definition of the truncated objective in Equation 22 and exchange the finite sum with the threshold integral:

$ J^{(T)}_{\mathrm{TailRL}}(\theta;x)

-\int_0^1 \sum_{k=1}^{T} \frac{\big(1-p_\theta(x, \tau)\big)^{k}}{k}, d\tau

-\sum_{k=1}^{T} \frac{1}{k} \int_0^1 \big(1-p_\theta(x, \tau)\big)^{k}, d\tau .\tag{73} $

Each integral on the right is one minus a Best-of- $k$ value by Equation 70, and substituting it in gives Equation 71.

For the series, we let $T \to \infty$ on both sides of Equation 71 and identify the two limits.

We first show the left side converges to the tail-likelihood. Since $J_{\mathrm{TailRL}}(\theta;x) > -\infty$, the tail-probability $p_\theta(x, \tau)$ is positive for almost every threshold. Fix such a $\tau$, so that $0 \le 1-p_\theta(x, \tau) < 1$. The Maclaurin series of the logarithm, evaluated at $1-p_\theta(x, \tau)$, gives the pointwise limit of the partial sums:

$ \lim_{T\to\infty} \sum_{k=1}^{T} \frac{\big(1-p_\theta(x, \tau)\big)^{k}}{k}

\sum_{k=1}^{\infty} \frac{\big(1-p_\theta(x, \tau)\big)^{k}}{k}

-\log p_\theta(x, \tau).\tag{74} $

The convergence is monotone: every added term $\big(1-p_\theta(x, \tau)\big)^{T+1}/(T+1)$ is nonnegative, so the partial sums only grow with $T$. The integrands in the definition 22 of $J^{(T)}_{\mathrm{TailRL}}$ are exactly these partial sums. Because they are nonnegative and increasing in $T$, the limit of their integrals is the integral of their limit, which is the monotone convergence theorem. Therefore

$ \lim_{T\to\infty} J^{(T)}_{\mathrm{TailRL}}(\theta;x)

-\int_0^1 \lim_{T\to\infty} \sum_{k=1}^{T} \frac{\big(1-p_\theta(x, \tau)\big)^{k}}{k}, d\tau

\int_0^1 \log p_\theta(x, \tau), d\tau

J_{\mathrm{TailRL}}(\theta;x).\tag{75} $

The right side needs no computation. For every $T$, the right side of Equation 71 is the $T$-th partial sum of the series in Equation 72. Its limit exists because it equals the left side at every $T$, and by Equation 75 that limit is $J_{\mathrm{TailRL}}(\theta;x)$. This is Equation 72.

Every term of the series is nonpositive, since no Best-of- $k$ value exceeds $1$, so the partial sums decrease monotonically to the tail-likelihood: each truncation is an upper bound on $J_{\mathrm{TailRL}}$, tightening as $T$ grows. At the other end, $J^{(1)}{\mathrm{TailRL}}(\theta;x) = \text{Best-of-}1(\theta;x) - 1 = J{\mathrm{RL}}(\theta;x) - 1$, so the first member of the family is expected reward reinforcement learning up to an additive constant and shares its gradient.

########## {caption="Proposition 11: Harmonic Best-of- $k$ expansion of the gradient"}

Under Assumption 3, Assumption 4, and Assumption 5, for every $\theta\in \Theta$ and every $T \ge 1$,

$ \nabla_\theta J^{(T)}_{\mathrm{TailRL}}(\theta;x)

\sum_{k=1}^{T} \frac{1}{k}, \nabla_\theta, \text{\emph{Best-of-}}k(\theta;x)

\int_0^1 \frac{1-\big(1-p_\theta(x, \tau)\big)^{T}}{p_\theta(x, \tau)}, \nabla_\theta p_\theta(x, \tau), d\tau .\tag{76} $

Proof: Lemma 6 moves the gradient inside the threshold integral of Equation 70, and the chain rule gives

$ \nabla_\theta, \text{Best-of-}k(\theta;x)

k \int_0^1 \big(1-p_\theta(x, \tau)\big)^{k-1}, \nabla_\theta p_\theta(x, \tau), d\tau .\tag{77} $

Multiply Equation 77 by $1/k$, sum over $k = 1, \ldots, T$, and exchange the finite sum with the integral:

$ \sum_{k=1}^{T} \frac{1}{k}, \nabla_\theta, \text{Best-of-}k(\theta;x)

\int_0^1 \Bigg[\sum_{k=1}^{T} \big(1-p_\theta(x, \tau)\big)^{k-1}\Bigg], \nabla_\theta p_\theta(x, \tau), d\tau .\tag{78} $

The bracket is a finite geometric sum, $\sum_{k=1}^{T}(1-p)^{k-1} = \big(1-(1-p)^{T}\big)/p$, which gives the right side of Equation 76. The left equality is Lemma 6 again, differentiating Equation 71 term by term. Every coefficient $1/k$ is positive, so the truncated gradient is a fixed, positively weighted combination of the Best-of- $k$ gradients for $k = 1, \ldots, T$.

C.5 Unbiasedness of the finite rollout Estimator

This section proves Equation 28, restated here in full.

Equation 28

(Unbiasedness of the TailRL estimator, restated). The unbiased estimator of $\nabla_\theta J_{\mathrm{TailRL}}^{(N)}(\theta;x)$ can be expressed as,

$ g_{\mathrm{TailRL}}^{(N)}(x) := \sum_{i=1}^N \omega(r_i), S_i, \qquad \omega(r_i) := \int_0^{r_i}\frac{d\tau}{\sum_{j=1}^{N}\mathbb{1}_{{r_j>\tau}}}\tag{79} $

Under Assumption 3, Assumption 4, and Assumption 5, the estimator $g_{\mathrm{TailRL}}^{(N)}(x):=\sum_{i=1}^N\omega\bigl(r(x, z_i)\bigr), S(x, z_i)$ is unbiased for the order- $N$ truncated gradient:

$ \mathbb{E}{z{1:N}}!\left[g_{\mathrm{TailRL}}^{(N)}(x)\right]

\nabla_\theta J_{\mathrm{TailRL}}^{(N)}(\theta;x).\tag{80} $

Proof of Equation 28: The weight Equation 79 for rollout $i$ over its integration range clears the threshold, so its denominator is at least one. The first step extends the integral from $[0, r(x, z_i))$ to $[0, 1)$ with an integrand that vanishes beyond $r(x, z_i)$. We cap the denominator below at one; the cap is active only where the numerator already vanishes:

$ \omega\bigl(r(x, z_i)\bigr)

\int_0^{r_i}\frac{d\tau}{\sum_{j=1}^{N}\mathbb{1}_{{r_j>\tau}}}

\int_0^1 \frac{\mathbb{1}{{r(x, z_i)>\tau}}}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)} , d\tau.\tag{81} $

Every ratio from here on carries this capped denominator, so no expression in the proof is ever indeterminate. Multiplying by $S(x, z_i)$ with their weights $\omega(r(x, z_i))$ and summing over the group, we make use of the score-functions being independent of the thresholds, so we swap the order of integration and summation:

$ g_{\mathrm{TailRL}}^{(N)}(x)

\int_0^1 \frac{\sum_{i=1}^{N}\mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i)}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)} , d\tau.\tag{82} $

The chain of expectations. Take the expectation over the training group. Lemma 6 moves it inside the integral over thresholds $\tau$, and linearity then moves it inside the finite sum over rollouts:

$ \begin{aligned} \mathbb{E}{z{1:N}}!\left[g_{\mathrm{TailRL}}^{(N)}(x)\right] &= \int_0^1 \mathbb{E}{z{1:N}}!\left[\left (\sum_{i=1}^{N} \frac{\mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i)}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}{{r(x, z_j)>\tau}}\Bigr)} \right)\right] d\tau \nonumber\ &= \int_0^1 \sum{i=1}^{N} \left (\mathbb{E}{z{1:N}}!\left[\frac{\mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i)}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)} \right] \right) d\tau. \end{aligned}\tag{83} $

By regularity condition Lemma 6, this integral is bounded. The next tool we use is the tower property of conditional expectation: for random variables $X$ and $Y$ on the same support,

$ \mathbb{E}_{X}!\left[X\right]

\mathbb{E}{Y}!\left[, \mathbb{E}{X}!\left[X\mid Y\right]\right],\tag{84} $

where the inner expectation averages $X$ with $Y$ held at its realized value and the outer expectation averages the result over $Y$. We apply it with the substitution

$ X := \frac{\mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i)}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}{{r(x, z_j)>\tau}}\Bigr)}, \qquad Y := { \mathbb{1}{{r(x, z_i)>\tau}}}_{i=1}^{N},\tag{85} $

the clearance pattern of the group at threshold $\tau$; both are functions of the training group $z_{1:N}$, so every expectation below averages over $z_{1:N}$. The tower property Equation 84 gives

$ \mathbb{E}{z{1:N}}!\left[\frac{\mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i)}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)} \right]

\mathbb{E}{z{1:N}}!\left[, \mathbb{E}{z{1:N}}!\left[\left. \frac{\mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i)}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}{{r(x, z_j)>\tau}}\Bigr)} , \right|, { \mathbb{1}{{r(x, z_i)>\tau}}}_{i=1}^{N}\right] \right].\tag{86} $

Before taking the inner expectation, note one pointwise identity. An indicator equals its own square, so multiplying the fraction by a second copy of rollout $i$ 's indicator changes nothing:

$ \frac{\mathbb{1}{{r(x, z_i)>\tau}}}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}{{r(x, z_j)>\tau}}\Bigr)} ; \mathbb{1}{{r(x, z_i)>\tau}}

\frac{\mathbb{1}{{r(x, z_i)>\tau}}}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)}.\tag{87} $

So $X$ factors into the fraction times the conditional score:

$ X

\frac{\mathbb{1}{{r(x, z_i)>\tau}}}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}{{r(x, z_j)>\tau}}\Bigr)} ; \mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i), \qquad Y

\bigl{\mathbb{1}{{r(x, z_j)>\tau}}\bigr}{j=1}^{N}.\tag{88} $

Conditioning on $\bigl{\mathbb{1}{{r(x, z_j)>\tau}}\bigr}{j=1}^{N}$ determines all $N$ indicator functions, so the expression simplifies as:

$ \mathbb{E}{z{1:N}}!\left[\left. \frac{\mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i)}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)} , \right|, Y\right]

\frac{\mathbb{1}{{r(x, z_i)>\tau}}}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}{{r(x, z_j)>\tau}}\Bigr)} ; \mathbb{E}{z_{1:N}}!\left[, \mathbb{1}_{{r(x, z_i)>\tau}}, S(x, z_i), \middle|, Y\right].\tag{89} $

It remains to compute the conditional mean of the gated score. The rollouts are independent, so the only part of $Y$ that constrains $z_i$ is its own indicator, and we split on the two values it can take. If rollout $i$ clears, $z_i$ follows the policy restricted to the clearing set, $\pi_\theta(z\mid x), \mathbb{1}{{r(x, z)>\tau}}/p\theta(x, \tau)$; the gate is one everywhere on this support, so the mean is the clearing-rollout mean score, whose norm is at most $C$ by Assumption 5. If rollout $i$ fails, $z_i$ is supported on $r(x, z)\le\tau$, where the gate is zero, so the mean is exactly the zero vector. Both branches are finite, and together they give:

$ \mathbb{E}{z{1:N}}!\left[, \mathbb{1}_{{r(x, z_i)>\tau}}, S(x, z_i), \middle|, Y\right]

\mathbb{1}{{r(x, z_i)>\tau}}; \mathbb{E}{z\sim\pi_\theta(\cdot\mid x)}!\left[S(x, z)\mid r(x, z)>\tau\right].\tag{90} $

Substituting Equation 90 into Equation 89 and applying Equation 87 once more removes the extra indicator:

$ \mathbb{E}{z{1:N}}!\left[\left. \frac{\mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i)}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)} , \right|, Y\right]

\frac{\mathbb{1}{{r(x, z_i)>\tau}}}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}{{r(x, z_j)>\tau}}\Bigr)} ; \mathbb{E}{z\sim\pi_\theta(\cdot\mid x)}!\left[S(x, z)\mid r(x, z)>\tau\right].\tag{91} $

Finally the outer expectation of Equation 86 wraps over Equation 91. The clearing-rollout mean score-function is a fixed vector, so by linearity the outer expectation acts only on the fraction of indicators:

$ \begin{split}\mathbb{E}{z{1:N}}!\left[\frac{\mathbb{1}{{r(x, z_i)>\tau}}, S(x, z_i)}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}{{r(x, z_j)>\tau}}\Bigr)} \right] &= \mathbb{E}{z\sim\pi_\theta(\cdot\mid x)}!\left[S(x, z)\mid r(x, z)>\tau\right]\&\quad\times; \mathbb{E}{z{1:N}}!\left[\frac{\mathbb{1}{{r(x, z_i)>\tau}}}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)} \right].\end{split}\tag{92} $

Substituting Equation 92 into Equation 83, summing over $i$, and recombining the $N$ terms under one expectation by linearity leaves the sum of the fractions, which share one denominator and collapse to a single ratio of the same count:

$ \sum_{i=1}^{N} \frac{\mathbb{1}{{r(x, z_i)>\tau}}}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)}

\frac{\sum_{j=1}^{N}\mathbb{1}{{r(x, z_j)>\tau}}}{\max\Bigl(1, ;\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\Bigr)}

\mathbb{1}{{\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\geq 1}}.\tag{93} $

The last equality is checked outcome by outcome: if the number of rollouts attaining a reward above the threshold is $\geq1$, the cap is inactive and the ratio is $=1$; if no rollout clears, the ratio is $0/1=0$. The expectation of this event indicator is its probability, and the $N$ rollouts fail the threshold independently, each with probability $1-p_\theta(x, \tau)$:

$ \mathbb{E}{z{1:N}}!\left[\mathbb{1}{{\sum{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}\geq 1}}\right]

1-\left(1-p_\theta(x, \tau)\right)^{N}.\tag{94} $

The remaining constant is evaluated by the definition of conditional expectation given an event, $\mathbb{E}[S\mid A]=\mathbb{E}[S, \mathbb{1}A]/\operatorname{Pr}(A)$, with $A={r(x, z)>\tau}$ and $\operatorname{Pr}{z\sim\pi_\theta(\cdot\mid x)}(A)=p_\theta(x, \tau)$; its numerator is the score-function identity Equation 39:

$ \mathbb{E}{z\sim\pi\theta(\cdot\mid x)}!\left[S(x, z)\mid r(x, z)>\tau\right]

\frac{\mathbb{E}{z\sim\pi\theta(\cdot\mid x)}!\left[\mathbb{1}{{r(x, z)>\tau}}, S(x, z)\right]}{p\theta(x, \tau)}

\frac{\nabla_\theta p_\theta(x, \tau)}{p_\theta(x, \tau)}.\tag{95} $

Assembling the chain. Substituting Equation 92, Equation 93, Equation 94, and 95 into Equation 83 yields the truncated gradient of Equation 48:

$ \mathbb{E}{z{1:N}}!\left[g_{\mathrm{TailRL}}^{(N)}(x)\right]

\int_0^1 \Bigl(1-\left(1-p_\theta(x, \tau)\right)^{N}\Bigr) \frac{\nabla_\theta p_\theta(x, \tau)}{p_\theta(x, \tau)} , d\tau

\nabla_\theta J_{\mathrm{TailRL}}^{(N)}(\theta;x).\tag{96} $

The proof identifies the estimator as MaxRL run at every threshold on one shared group of rollouts: wherever any rollout clears a threshold the cap is inactive and the integrand of Equation 82 is the average score-function of the clearing rollouts, MaxRL's success-averaging rule for the threshold event, while at thresholds no rollout clears it is zero, MaxRL's rule for a group with no successes; its expectation carries MaxRL's order- $N$ truncated weight from Equation 33, and the binary case, where a single threshold carries all the mass, recovers MaxRL exactly (Corollary 14).

Loss reduction

The estimator is a sum over the group. A mean-reduced policy-gradient loss, which divides the group sum by $N$, must therefore use the coefficients $N, \omega\bigl(r(x, z_i)\bigr)$, and after mean-centering $N\bigl(\omega\bigl(r(x, z_i)\bigr)-\bar\omega\bigr)$. A sum-reduced loss uses $\omega\bigl(r(x, z_i)\bigr)$, and after mean-centering $\omega\bigl(r(x, z_i)\bigr)-\bar\omega$.

C.6 Closed-Form Weights and Algorithm Correctness

The next proposition proves the recurrence in Equation 26. Throughout, $z_1, \ldots, z_N$ is the training group of Equation 28, and $r_{(1)}\le\cdots\le r_{(N)}$ denote the group rewards $r(x, z_1), \ldots, r(x, z_N)$ sorted increasingly, with $r_{(0)}:=0$. The weight Equation 79 depends on a rollout only through its reward, so rollouts with equal rewards receive equal weights and $\omega\bigl(r_{(i)}\bigr)$ is well defined.

########## {caption="Proposition 12: Closed-form empirical weights"}

For every $i=1, \ldots, N$,

$ \omega\bigl(r_{(i)}\bigr)

\sum_{k=1}^{i} \frac{r_{(k)}-r_{(k-1)}}{N-k+1}.\tag{97} $

Equivalently, all weights follow the recurrence

$ \omega\bigl(r_{(i)}\bigr)

\omega\bigl(r_{(i-1)}\bigr) + \frac{r_{(i)}-r_{(i-1)}}{N-i+1}, \qquad \omega\bigl(r_{(0)}\bigr)=0.\tag{98} $

Proof: The empirical tail-probability distribution is a piecewise constant function. Fix $k\in{1, \ldots, N}$ and a threshold $\tau\in[r_{(k-1)}, r_{(k)})$. The rewards $r_{(k)}, \ldots, r_{(N)}$ are at least $r_{(k)}$ and therefore exceed $\tau$, while the rewards $r_{(1)}, \ldots, r_{(k-1)}$ are at most $r_{(k-1)}\le\tau$ and fail, since clearance is strict:

$ \sum_{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}

N-k+1 \qquad \text{for every }\tau\in[r_{(k-1)}, r_{(k)}).\tag{99} $

The intervals $[r_{(k-1)}, r_{(k)})$ for $k=1, \ldots, i$ partition the integration range $[0, r_{(i)})$ of the weight, with tied rewards contributing empty intervals, so substituting Equation 99 evaluates the integral interval by interval:

$ \omega\bigl(r_{(i)}\bigr)

\int_0^{r_{(i)}} \frac{d\tau}{\sum_{j=1}^{N}\mathbb{1}_{{r(x, z_j)>\tau}}}

\sum_{k=1}^{i} \int_{r_{(k-1)}}^{r_{(k)}} \frac{d\tau}{N-k+1}

\sum_{k=1}^{i} \frac{r_{(k)}-r_{(k-1)}}{N-k+1},\tag{100} $

which is Equation 97; every denominator on the range is at least $N-i+1\geq 1$, so no ratio is ever indeterminate. Subtracting Equation 97 at ranks $i$ and $i-1$ leaves the single term $k=i$, which is the recurrence Equation 98; the base case is the integral over the empty range $[0, r_{(0)})$.

Scale of the weights

Every weight is nonnegative, since every gap $r_{(k)}-r_{(k-1)}$ is nonnegative. The total is the largest reward in the group: exchanging the order of the finite double sum counts each gap once per rank at or above it, and that count cancels its denominator, leaving a telescoping sum:

$ \sum_{i=1}^{N}\omega\bigl(r_{(i)}\bigr)

\sum_{k=1}^{N};\sum_{i=k}^{N} \frac{r_{(k)}-r_{(k-1)}}{N-k+1}

\sum_{k=1}^{N}\bigl(r_{(k)}-r_{(k-1)}\bigr)

r_{(N)}

\max_{1\le j\le N} r(x, z_j).\tag{101} $

For rewards in $[0, 1]$, the pre-centering advantages $N, \omega\bigl(r(x, z_i)\bigr)$ therefore sum to $N, r_{(N)}\le N$ and each lies in $[0, , N, r_{(N)}]$, so the update scale is controlled by the best reward observed in the group.

C.7 Effect of the Mean-Centering Baseline

########## {caption="Proposition 13: The mean baseline lowers the truncation order by one"}

For $N\geq2$, let

$ \bar\omega := \frac{1}{N}\sum_{i=1}^N\omega\bigl(r(x, z_i)\bigr), \qquad \hat{g}{\mathrm{TailRL}}^{(N)}(x) := \sum{i=1}^N \Bigl(\omega\bigl(r(x, z_i)\bigr)-\bar\omega\Bigr), S(x, z_i).\tag{102} $

Then

$ \mathbb{E}{z{1:N}}!\left[\hat{g}_{\mathrm{TailRL}}^{(N)}(x)\right]

\nabla_\theta J_{\mathrm{TailRL}}^{(N-1)}(\theta;x).\tag{103} $

Proof: By Equation 101, the weights of a group sum to its largest reward, so the centered estimator is the uncentered one minus a max-reward-weighted sum of scores:

$ \hat{g}_{\mathrm{TailRL}}^{(N)}(x)

g_{\mathrm{TailRL}}^{(N)}(x)

\frac{1}{N} \Bigl(\max_{1\le i\le N}r(x, z_i)\Bigr) \sum_{i=1}^N S(x, z_i).\tag{104} $

The subtracted term is the score-function estimator of the Best-of- $N$ gradient: the group is one draw from the product policy, whose score-function is $\sum_{i=1}^N S(x, z_i)$, so

$ \nabla_\theta, \mathbb{E}{z{1:N}}!\left[\max_{1\le i\le N}r(x, z_i)\right]

\mathbb{E}{z{1:N}} !\left[\Bigl(\max_{1\le i\le N}r(x, z_i)\Bigr) \sum_{i=1}^N S(x, z_i) \right].\tag{105} $

Taking expectations in Equation 104 and invoking Equation 28 for the first term and 105 for the second yields

$ \mathbb{E}{z{1:N}}!\left[\hat{g}_{\mathrm{TailRL}}^{(N)}(x)\right]

\nabla_\theta J_{\mathrm{TailRL}}^{(N)}(\theta;x)

\frac{1}{N} \nabla_\theta, \mathbb{E}{z{1:N}}!\left[\max_{1\le i\le N}r(x, z_i)\right].\tag{106} $

It remains to identify the right side as the order- $(N-1)$ gradient. The expected maximum is the Best-of- $N$ value, whose layer-cake form is Equation 70 at $k=N$:

$ \mathbb{E}{z{1:N}}!\left[\max_{1\le i\le N}r(x, z_i)\right]

\int_0^1 \Bigl[1-\left(1-p_\theta(x, \tau)\right)^N\Bigr] d\tau.\tag{107} $

Meanwhile, the definitions of two consecutive truncations differ in one term of the inner sum:

$ J_{\mathrm{TailRL}}^{(N)}(\theta;x)

J_{\mathrm{TailRL}}^{(N-1)}(\theta;x)

-\frac{1}{N} \int_0^1 \left(1-p_\theta(x, \tau)\right)^N d\tau.\tag{108} $

Combining Equation 107 and 108 shows the two sides differ by a constant:

$ J_{\mathrm{TailRL}}^{(N)}(\theta;x)

J_{\mathrm{TailRL}}^{(N-1)}(\theta;x)

\frac{1}{N}, \mathbb{E}{z{1:N}}!\left[\max_{1\le i\le N}r(x, z_i)\right]

\frac{1}{N}.\tag{109} $

The final term is constant in $\theta$, so differentiating gives

$ \nabla_\theta J_{\mathrm{TailRL}}^{(N)}(\theta;x)

\frac{1}{N} \nabla_\theta, \mathbb{E}{z{1:N}}!\left[\max_{1\le i\le N}r(x, z_i)\right]

\nabla_\theta J_{\mathrm{TailRL}}^{(N-1)}(\theta;x).\tag{110} $

Substituting Equation 110 into Equation 106 proves the result.

C.8 Estimator-Level Recovery of MaxRL on Binary Rewards

########## {caption="Corollary 14: Binary-reward recovery"}

Suppose $r_i\in{0, 1}$ and let $M:=\sum_{i=1}^N \mathbb{1}{r_i=1}$. If $M>0$, then every successful rollout receives weight $1/M$ and every unsuccessful rollout receives weight zero. Hence the uncentered TailRL estimator reduces to

$ g_{\mathrm{TailRL}}^{(N)}(x)

\frac{1}{M} \sum_{i:r_i=1}S_i,\tag{111} $

which is the MaxRL estimator. After mean-centering, successful rollouts have weight $1/M-1/N$ and unsuccessful rollouts have weight $-1/N$. If $M=0$, all uncentered and centered weights are zero.

Proof: For binary rewards with $\sum_{i=1}^N \mathbb{1}{r_i=1}>0$,

$ \omega(1)=\int_0^1\frac{d\tau}{\sum_{i=1}^N \mathbb{1}{r_i=1}}=\frac{1}{\sum_{i=1}^N \mathbb{1}{r_i=1}} $

and $\omega(0)=0$. The uncentered result follows immediately. The mean weight is

$ \bar\omega=\left(\sum_{i=1}^N \mathbb{1}{r_i=1}\right)\frac{1}{\sum_{i=1}^N \mathbb{1}{r_i=1}}\cdot\frac{1}{N}=\frac{1}{N}, $

which gives the centered weights. When $\sum_{i=1}^N \mathbb{1}{r_i=1}=0$, every reward and hence every weight is zero.

D. TailRL on a General Reward Range

The main paper assumes rewards in $[0, 1]$ only to simplify notation. The same objective applies to any bounded reward range.

Suppose the reward function returns rewards in an arbitrary bounded range, $r(x, z)\in[r_{\mathrm{min}}, r_{\mathrm{max}}]$ with $r_{\mathrm{min}}<r_{\mathrm{max}}$. For thresholds $\tau\in[r_{\mathrm{min}}, r_{\mathrm{max}})$, define the tail-probability as before: $p_\theta(x, \tau):= \operatorname{Pr}_{z\sim\pi_\theta(\cdot\mid x)}[r(x, z)>\tau]$. The TailRL objective averages the log-tail-probability across this range:

$ J_{\mathrm{TailRL}}^{[r_{\mathrm{min}}, r_{\mathrm{max}}]}(\theta;x) := \frac{1}{r_{\mathrm{max}}-r_{\mathrm{min}}} \int_{r_{\mathrm{min}}}^{r_{\mathrm{max}}} \log p_\theta(x, \tau), d\tau .\tag{112} $

The factor $1/(r_{\mathrm{max}}-r_{\mathrm{min}})$ makes this the expected log-tail-probability under a threshold drawn uniformly from $[r_{\mathrm{min}}, r_{\mathrm{max}}]$. It also prevents the scale of the objective from depending on the units of the reward.

To recover the unit-interval objective, substitute $\tau = r_{\mathrm{min}}+(r_{\mathrm{max}}-r_{\mathrm{min}}), u$ with $u\in[0, 1)$ and define the rescaled reward $\tilde{r} := (r-r_{\mathrm{min}})/(r_{\mathrm{max}}-r_{\mathrm{min}})\in[0, 1]$. Then

$ J_{\mathrm{TailRL}}^{[r_{\mathrm{min}}, r_{\mathrm{max}}]}(\theta;x)

\int_0^1 \log \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)}!\bigl[\tilde{r}(x, z)>u\bigr] , du

J_{\mathrm{TailRL}}(\theta;, x) \quad \text{for the reward }\tilde{r} .\tag{113} $

Thus, applying TailRL to rewards in $[r_{\mathrm{min}}, r_{\mathrm{max}}]$ is equivalent to applying the unit-interval objective to $\tilde{r}$. Shifting or rescaling the reward only relabels its thresholds, so every result in the paper carries over directly.

The finite rollout estimator behaves in the same way. For sorted rewards, consecutive weights satisfy

$ \omega_{(i)}-\omega_{(i-1)}

\frac{r_{(i)}-r_{(i-1)}}{N-i+1},\tag{114} $

so an affine rescaling of the rewards multiplies every weight by $r_{\mathrm{max}}-r_{\mathrm{min}}$. The normalization in Equation 112 cancels this factor. Without the normalization, the update direction remains unchanged and only its magnitude is rescaled. The estimator can therefore operate on raw rewards from any bounded range without changing the algorithm.

E. Connection to Ordinal Cross-Entropy

Threshold decompositions turn an ordinal or continuous target into a family of binary events, one event per threshold, and fit each event with a binary classifier ([86, 87, 88, 89, 90]). This appendix makes the relation to TailRL exact. The population TailRL objective is the ordinal cross-entropy objective evaluated at the maximal target $r=1$, and the finite rollout TailRL procedure is the finite sample estimation of that objective.

Fix an input $x$ and recall the tail-probability $p_\theta(x, \tau) = \operatorname{Pr}{z\sim\pi\theta(\cdot\mid x)}\left(r(x, z) > \tau\right)$. For a target level $t \in [0, 1]$, define the threshold-decomposed cross-entropy between the point target $t$ and the model's family of threshold events,

$ \mathrm{CE}(t;\theta, x) := -\int_0^1 \Big[, \mathbb{1}{{t>\tau}}, \log p\theta(x, \tau) ;+; \mathbb{1}{{t\le\tau}}, \log\big(1-p\theta(x, \tau)\big) , \Big], d\tau .\tag{115} $

For each fixed $\tau$ the bracket is the binary cross-entropy of the event ${r>\tau}$ against the label $\mathbb{1}_{{t>\tau}}$, and the integral weights all thresholds by the same uniform measure that defines the tail-likelihood.

Setting the target to the maximal reward $t=1$ makes $\mathbb{1}_{{t>\tau}}=1$ for every $\tau\in[0, 1)$, so the second term in Equation 115 vanishes on a set of full measure and

$ \mathrm{CE}(1;\theta, x) ;=; -\int_0^1 \log p_\theta(x, \tau), d\tau ;=; -, J_{\mathrm{TailRL}}(\theta;x).\tag{116} $

Maximizing the tail-likelihood is therefore exactly minimizing the ordinal cross-entropy against the ideal target $r=1$. When the reward is binary the tail-probability is constant in $\tau$, the integral collapses to a single binary cross-entropy against the label $1$, and 116 reduces to the MaxRL objective $\log q_\theta(x)$, consistent with Section 3.2.

The correspondence extends to the finite rollout procedure. The order- $N$ objective $J^{(N)}_{\mathrm{TailRL}}$ of Equation 22 truncates the same integral at the resolution a group of $N$ rollouts can support, and the estimator of Equation 28 is unbiased for its gradient using only the $N$ sampled rewards. Training with TailRL on $N$ rollouts is in this sense the finite sample estimation of the ordinal cross-entropy objective at target $r=1$: the rollouts play the role of the samples from which the threshold events are estimated, and the truncation order grows with the sample size, recovering Equation 116 as $N\to\infty$.

F. Advantage Functions of GRPO, RLOO, and TailRL

All three methods share the same critic-free template: draw $N$ rollouts, map their rewards to advantages, and form the update $\sum_{i=1}^{N} A_i, S(x, z_i)$. They differ only in that map, which we record here. For convenience of notation, we write $r_i:=r(x, z_i)$ for the reward of rollout $z_i$.

RLOO

RLOO subtracts the leave-one-out mean of the other rollouts,

$ A_i^{(\mathrm{RLOO})}

r_i - \frac{1}{N-1}\sum_{j \ne i} r_j .\tag{117} $

The baseline is independent of rollout $i$, so the update is an unbiased estimator of the expected reward gradient. The advantage is affine in $r_i$ with unit slope: a rollout is promoted by its raw margin over the rest of the group.

GRPO

GRPO standardizes within the group,

$ A_i^{(\mathrm{GRPO})}

\frac{r_i - \bar{r}}{\sigma(r) + \epsilon}, \qquad \bar{r} = \frac{1}{N}\sum_{j=1}^{N} r_j, \qquad \sigma(r)^2 = \frac{1}{N}\sum_{j=1}^{N} (r_j - \bar{r})^2 .\tag{118} $

Dividing by the group standard deviation makes the update invariant to affine rescaling of the reward. The same divisor applies to every rollout in the group, so it changes the size of an input's update rather than the relative weight of rewards within it.

TailRL

TailRL assigns weights proportional to inverse tail-probability's integral and centers it,

$ A_i^{(\mathrm{TailRL})}

\omega(r_i) - \bar\omega, \qquad \omega(r_i) = \int_0^{r_i} \frac{d\tau}{\sum_{j=1}^{N} \mathbb{1}{{r_j > \tau}}}, \qquad \bar\omega = \frac{1}{N}\sum{j=1}^{N}\omega(r_j) .\tag{119} $

The integrand is the reciprocal of the number of rollouts attaining a reward above a given reward threshold, so a level cleared by one rollout out of $N$ contributes $N$ times the weight per unit of reward of one cleared by all. The map is computed in closed form by the recurrence in Equation 26 and reduces to the MaxRL advantages when the reward is binary (Appendix C.8).

G. Pass@k and Best-of-k Empirical Calculation

Pass@ $k$ is used for binary rewards and measures the probability that at least one rollout succeeds. Best-of- $k$ is used for continuous rewards and measures the expected reward of the highest-scoring rollout. Both metrics evaluate a policy when we sample $k$ rollouts and keep the best one. The two metrics are identical for binary rewards, and both improve or remain unchanged as $k$ increases. When we have $K$ evaluation rollouts to estimate Pass@ $k$ or Best-of- $k$ with $K > k$, we use all $K$ rollouts to compute their unbiased estimators below.

G.1 Pass@k

If $M$ of the $K$ sampled rollouts succeed, the unbiased estimator of [24] is

$ \widehat{\mathrm{Pass@}k}

1 - \frac{\binom{K-M}{k}}{\binom{K}{k}} .\tag{120} $

The ratio is the probability that a uniformly random size- $k$ subset of the $K$ rollouts avoids all $M$ successes.

G.2 Best-of-k

Best-of- $k$ is defined as in Equation 70

$ \text{Best-of-}k(\theta; x)

\mathbb{E}!\left[\max_{1 \le i \le k} r(x, z_i)\right]

\int_0^1 \left[1 - \left(1 - p_\theta(x, \tau)\right)^{k}\right] d\tau,\tag{121} $

the second form by the layer-cake identity applied to the maximum, which reduces to Pass@ $k$ when the reward is binary. Sorting the $K$ sampled rewards increasingly as $r_{(1)} \le \cdots \le r_{(K)}$, the unbiased estimator weights each order statistic by the probability that it is the maximum of a uniformly random size- $k$ subset:

$ \widehat{\text{Best-of-}k}

\sum_{i=k}^{K} \frac{\binom{i-1}{k-1}}{\binom{K}{k}}, r_{(i)} .\tag{122} $

H. ImageNet Object Localization

We study single-object localization on ImageNet-scale data ([16]). Given an image, the policy predicts a bounding box and receives its intersection-over-union (IoU) with the ground-truth box as a reward in $[0, 1]$.

The policy uses a pretrained ResNet-50 backbone ([15]) with four categorical heads, one for each box coordinate. Each head contains $50$ uniformly spaced bins, and a rollout samples one bin from each head to form a box. All methods train for $30$ epochs with Adam, a learning rate of 5 x 10^-4 with warmup, and a batch size of $128$. They differ only in how they compute the advantages. We train TailRL with $N\in{16, 64, 256, 1024}$ rollouts and separately optimize the exact population-level objective described in Appendix H.2.

For comparison, we also train supervised models directly on the ground-truth coordinates using MSE, L1, GIoU ([18]), and L1+GIoU losses (Appendix H.1).

We evaluate on held-out images using CorLoc@ $\delta$, mean IoU, and Best-of- $1024$ IoU. CorLoc@ $\delta$ is the fraction of images whose greedy prediction exceeds IoU $\delta$. Best-of- $1024$ IoU is the highest IoU among $1024$ sampled boxes for each image. We report results over $3$ seeds. The large- $N$ gradient measurements in Figure 6 use one seed, as noted in the figure. Table 3 summarizes the full configuration.

::: {caption="Table 3: Training hyperparameters for ImageNet object localization."}

:::

H.1 Supervised Anchor Losses

Let $b = (x_1, y_1, x_2, y_2)$ denote the predicted box and $b^\star$ the ground-truth box. Both use normalized corner coordinates. The L1 loss measures the absolute error across the four coordinates:

$ \mathcal{L}_{\mathrm{L1}}(b, b^\star)

\left| b - b^\star \right|_1

\sum_{j=1}^{4} \left| b_j - b^\star_j \right|_1 .\tag{123} $

The GIoU loss ([18]) extends IoU with a penalty based on the smallest box enclosing both boxes. We use $|b|$ to denote the area enclosed by the bounding box $b$. Let $\mathrm{I} = |b \cap b^\star|$ be the intersection area, $\mathrm{U} = |b\cup b^\star|$ the union area, and $c$ the smallest axis-aligned box enclosing both $b$ and $b^{\star}$ and has an area $|c|$:

$ \mathcal{L}_{\mathrm{GIoU}}(b, b^\star)

1 - \underbrace{\frac{\mathrm{I}}{\mathrm{U}}}_{\mathrm{IoU}}

• \frac{|c| - \mathrm{U}}{|c|} .\tag{124} $

The final term measures the empty space inside the enclosing box. Unlike IoU, it remains informative when the predicted and ground-truth boxes do not overlap. The combined loss follows DETR ([19]):

$ \mathcal{L}_{\mathrm{L1+GIoU}}(b, b^\star)

\lambda_{\mathrm{L1}} \mathcal{L}{\mathrm{L1}}(b, b^\star) + \lambda{\mathrm{GIoU}} \mathcal{L}_{\mathrm{GIoU}}(b, b^\star) .\tag{125} $

We use the DETR weights $\lambda_{\mathrm{L1}} = 5$ and $\lambda_{\mathrm{GIoU}} = 2$. All three supervised anchors make one deterministic prediction and use no rollouts. Their greedy, mean, and Best-of- $k$ outputs are therefore identical.

H.2 Computing the Population-Level Objective

Computing the population objective $J_{\mathrm{TailRL}}(\theta;x) = \int_0^1 \log p_\theta(x, \tau) d\tau$ usually requires the unknown tail-probability $p_\theta(x, \tau)$. In this setting, we can compute it exactly because the policy has a finite output space. The policy predicts each of the four box coordinates with an independent categorical head over $K = 50$ uniformly spaced bins. A rollout samples one bin from each head, so its probability factorizes as

$ \pi_\theta(b \mid x) = \prod_{j=1}^{4} \pi_\theta^{(j)}(b_j \mid x), \qquad b \in \mathcal{B}, \quad |\mathcal{B}| = K^4 = 6{,}250{,}000 .\tag{126} $

Each box $b$ has a deterministic reward $r(x, b)$ given by its IoU with the ground-truth box. We can therefore compute $\left(\pi_\theta(b \mid x), r(x, b)\right)$ for every box in $\mathcal{B}$. The tail-probability at a threshold is the total probability of all boxes whose rewards exceed that threshold:

$ p_\theta(x, \tau) = \sum_{b \in \mathcal{B}} \pi_\theta(b \mid x) \mathbb{1}_{{r(x, b) > \tau}}\tag{127} $

The finite set $\mathcal{B}$ produces a finite set of reward values. The function $\tau \mapsto p_\theta(x, \tau)$ is constant between consecutive reward values, so the threshold integral becomes a finite sum. This calculation introduces no discretization error beyond the original coordinate bins. In practice, we use the independence of the four heads to avoid explicitly enumerating all $K^4$ boxes. Algorithm 1 forms the joint probabilities from the four marginal distributions and accumulates them over the sorted reward values.

Require: Head distributions $\pi_\theta^{(j)}(\cdot \mid x)$ over $K$ bins, $j = 1,\ldots,4$; ground-truth box $b^\star$
$\mathcal{B} \gets \{1,\ldots,K\}^{4}$ // every box the policy can emit
for $b = (b_1,\ldots,b_4) \in \mathcal{B}$ do
  $\pi_\theta(b \mid x) \gets \prod_{j=1}^{4} \pi_\theta^{(j)}(b_j \mid x)$ // the heads are independent
  $r(x,b) \gets \mathrm{IoU}(b, b^\star)$
end for
$u_1 < \cdots < u_m \gets$ the distinct values of $\{\, r(x,b) : b \in \mathcal{B} \,\}$, sorted increasingly
for $i = 1,\ldots,m$ do
  $q_i \gets \sum_{b \,:\, r(x,b) = u_i} \pi_\theta(b \mid x)$ // reward distribution
end for
$p_\theta(x, u_m) \gets 0$ // no box exceeds the largest attainable reward
for $i = m-1,\ldots,1$ do
  $p_\theta(x, u_i) \gets p_\theta(x, u_{i+1}) + q_{i+1}$ // $p_\theta(x,\tau) = p_\theta(x,u_i)$ for $\tau \in [u_i, u_{i+1})$
end for
$J_{\mathrm{TailRL}}(\theta;x) \gets \sum_{i=1}^{m-1} (u_{i+1} - u_i) \log p_\theta(x, u_i)$
$\nabla_\theta J_{\mathrm{TailRL}}(\theta;x) \gets \sum_{i=1}^{m-1} (u_{i+1} - u_i) \dfrac{\nabla_\theta\, p_\theta(x, u_i)}{p_\theta(x, u_i)}$
Ensure: $J_{\mathrm{TailRL}}(\theta;x)$ and $\nabla_\theta J_{\mathrm{TailRL}}(\theta;x)$, exact, with no sampling error

Substituting the exact $p_\theta(x, \tau)$ into Equation 44 gives the gradient used by the population variant. This is an exact population gradient, not a large- $N$ approximation. We obtain it by automatically differentiating through the probability accumulation because each tail-probability value is a differentiable function of the prediction head probabilities.

H.3 Additional Results

Training dynamics

Figure 13 shows training from three perspectives. The left panel reports final held-out CorLoc@ $0.5$ across training rollout budgets $N$. TailRL improves steadily as $N$ increases and approaches the exact population objective. GRPO improves only slightly, while RLOO does not improve with additional rollouts. At every budget, both baselines perform worse than TailRL at its smallest reported budget.

The center panel shows the mean gradient norm by epoch at $N=1024$. GRPO produces the largest gradients, while RLOO produces the smallest. However, GRPO also achieves the lowest final accuracy, showing that larger gradients do not explain the performance differences in Figure 7.The right panel shows each method's training loss over RL steps using a logarithmic step axis. Because the methods optimize different objectives, their loss values are not directly comparable. Nevertheless, all three losses flatten near zero late in training.

Figure 14 stratifies validation performance by difficulty band. The bands are defined by the area of the ground-truth box as a fraction of the image, since a box that fills a moderate part of the frame is far easier to localize than a very small or a nearly full-frame one. An image is easy when that area lies between $0.30$ and $0.70$, medium when it lies between $0.10$ and $0.30$ or between $0.70$ and $0.95$, and hard when it falls below $0.10$ or above $0.95$; the three bands partition the $50{,}000$ validation images into $19{,}628$, $19{,}977$, and $10{,}395$. The gap between TailRL and the stronger expected reward baseline widens as the band gets harder: roughly $0.09$ IoU on the easy band, $0.16$ on medium, and $0.18$ on hard, where both baselines sit near $0.30$ and TailRL reaches $0.49$. Hard inputs are those on which high-reward rollouts are rare, and rarity is where the inverse-probability weighting of the tail-likelihood concentrates its effort, so the ordering of the gaps matches the mechanism the objective is built around. SR: pkpo td

H.4 The Effect of Binarizing the Reward

A continuous reward contains more information than binary reward. Binarizing it with a threshold removes this information by treating all outputs above or below the threshold as equally goor or bad. We test the cost of this lost signal by binarizing IoU at ${0.5, 0.75}$ and training MaxRL on each binary reward. We compare both variants with TailRL trained on the original continuous reward across four rollout budgets, with all other settings held fixed.

Binarization produces policies that perform well near their chosen threshold but poorly at higher quality levels (Figure 15). At CorLoc@ $0.5$, all methods reach approximately $0.78$. At CorLoc@ $0.75$, MaxRL trained with the $0.5$ threshold reaches only $0.30$, compared with approximately $0.63$ for TailRL and MaxRL trained with the $0.75$ threshold. At CorLoc@ $0.9$, the gap widens further: TailRL reaches approximately $0.39$, compared with $0.24$ for the $0.75$ threshold and $0.02$ for the $0.5$ threshold.

Once a rollout has an IoU above its binarization threshold, the binary reward no longer distinguishes a barely acceptable box from a nearly perfect one. This lost ordering produces both qualitative specialization to the chosen threshold and large quantitative losses above it. Increasing the rollout budget cannot recover information removed from the reward, so the binarized methods flatten while TailRL continues to improve at stricter thresholds. TailRL avoids choosing a specific threshold and learns from the full continuous reward, allowing one policy to perform well across all evaluated quality levels.

I. Text-Maze Navigation

We study navigation in $17 \times 17$ gridworld mazes represented as text. Given a maze, the policy generates a sequence of movement tokens. The continuous reward measures whether the sequence is well formed, how close it ends to the goal, and how its length compares with the shortest path. A rollout that reaches the goal along a shortest path receives a reward of $1$.

The policy is a $3$ M-parameter decoder-only transformer trained from scratch. We first pretrain it through supervised learning on $1.3$ M mazes with up to $16$ annotated paths per maze. To test how each RL method behaves under different initial policy qualities, we retain seven pretraining checkpoints. Their held-out shortest-path rates range from $0.012%$, or roughly one success in ten thousand attempts, to $0.83%$.

Starting from each checkpoint, we train every method for $5{,}000$ steps using $N = 16$ rollouts for each of $256$ mazes per step. Training is fully on-policy, uses no KL regularization, and is repeated over three seeds. We report the shortest-path rate, defined as the probability that a single sampled rollout reaches the goal using an optimal-length path. We estimate this rate from $64$ rollouts on each of $256$ held-out mazes.

I.1 Dataset and Pretraining

Each maze is a $17 \times 17$ grid with the start and goal at opposite corners. We generate a perfect maze using Prim's algorithm and then remove a uniformly sampled $5$ to $30%$ of its interior walls. Removing these walls creates alternative routes and varies the number of valid paths across mazes.

For pretraining, we pair each maze with up to $16$ goal-reaching paths selected by Algorithm 2. We first find the shortest-path length $L^{\star}$ using breadth-first search. A budgeted depth-first search then finds simple paths shorter than $\mathrm{ub}=60$. To prevent common path lengths from dominating the corpus, reservoir sampling retains at most four paths of each length.

We select paths that span a range of solution qualities. Each candidate path $P$ receives a reward, where a shortest path receives $1$ and longer paths receive smaller values. We divide reward $ r \in (0, 1]$ into $16$ equal intervals and select at most one path from each nonempty interval. When an interval contains multiple candidates, we select the path that overlaps least with those already chosen. This produces paths that vary in both length and spatial route. We train the policy on the resulting maze-path pairs using next-token prediction.

Require: Maze $m$; length limit $\mathrm{ub}=60$; target number of paths $n_{\mathrm{paths}}=16$
$\mathcal{C}\gets$ all simple start-to-goal paths found by breadth-first search with path length 
lt;\mathrm{ub}$
Divide $\mathcal{C}$ into $n_{\mathrm{paths}}$ equal buckets according to path length
$\mathcal{S}\gets\emptyset$
for each nonempty bucket $\mathcal{C}_t$ do
  Select one path $P_t\in\mathcal{C}_t$
  $\mathcal{S}\gets\mathcal{S}\cup{\{P_t\}}$
end for
Ensure: A set $\mathcal{S}$ of paths with diverse lengths

I.2 Post-Training Configuration

The reinforcement-learning stage starts from the checkpoints above and uses the configuration of Table 4, which also lists the evaluation sampling.

::: {caption="Table 4: Training hyperparameters for Text-Maze navigation."}

:::

I.3 Reward Function

A rollout is parsed into a sequence of moves and replayed in the maze. Write $L^\star$ for the length of a shortest path from start to goal, $L$ for the length of the rollout's path when it reaches the goal, and $d$ for the breadth-first distance from the rollout's final cell to the goal. The reward is the sum of a progress term and a solution term,

$ r(x, z) = \underbrace{\tfrac{1}{2}\min!\left(1, \tfrac{L^\star - d}{L^\star}\right)}{\text{progress}} ; + ; \underbrace{\tfrac{1}{2}\min!\left(1, \tfrac{L^\star}{L}\right)\mathbb{1}{{\text{goal reached}}}}_{\text{solution}},\tag{128} $

with both terms clipped below at zero, and with $r(x, z) = 0$ whenever the rollout is malformed or walks into a wall. The progress term pays partial credit for ending closer to the goal than the start, so a rollout that never arrives is still ranked by how far it got. The solution term pays full credit only for a shortest path and decays as $L^\star / L$ when the policy reaches the goal by a longer route. The reward equals $1$ exactly when the rollout reaches the goal along a shortest path, the event called shortest-path success in Section 6.2.

I.4 Task Representation and Prompt Template

A maze is serialized as a flat token sequence rather than as natural language, so the policy never sees English and cannot rely on pretrained language priors. The grid is written cell by cell with one token per cell, rows separated by a newline token, and the prompt ends at the marker that opens the path; the model then generates the path itself as a sequence of coordinate tokens. Each row of the $17 \times 17$ grid contributes seventeen cell tokens drawn from WALL, PATH, START, and GOAL, followed by NEWLINE; a rollout is the continuation after PATH_START, a sequence of movement tokens closed by DONE. It is scored for well-formedness, for how close it ends to the goal, and for its length against the shortest path.

**Input:**

<bos> GRID_START WALL WALL WALL $\ldots$ WALL START PATH PATH $\ldots$ NEWLINE $\ldots$ GOAL WALL NEWLINE $\ldots$ GRID_END PATH_START

**Output:**

RIGHT RIGHT DOWN DOWN $\ldots$ RIGHT DONE <eos>

Reward examples

Figure 8 shows four rollouts on one maze with the reward each receives. The two left paths never reach the goal and are scored by how far they get, which is what makes the reward continuous rather than binary. The third path reaches the goal but wanders, so it scores below a shortest path; only the rightmost path, which reaches the goal along a shortest path, receives reward $1$.

I.5 Additional Results

Effect of the inference rollout budget

We evaluate how the learned rollout distributions respond to additional inference rollouts. Figure 16 reports Pass@ $k$ and Best-of- $k$ reward as $k$ increases. At small $k$, policies trained with the three methods can appear similar. As $k$ increases, both metrics improve more rapidly for TailRL than for GRPO or RLOO. Despite GRPO and RLOO improving their Pass@ $1$ after RL post-training on policy initializations with good coverage, TailRL still outperforms them at test-time scaling. Evaluation at $k=1$ therefore understates the differences among the learned rollout distributions. The increasing separation is consistent with the Best-of- $k$ decomposition in Section 3: TailRL assigns greater probability to high-reward rollouts, making them more likely to be discovered as $k$ grows.

Effect of the training rollout budget

To study the effect of the training rollout budget, we vary $N$ while holding fixed an initial policy with a shortest-path success rate of approximately $0.02%$ (Figure 17). For TailRL, both Pass@ $k$ and Best-of- $k$ reward increase sharply between $N=4$ and $N=16$. At $N=4$, TailRL remains near the same floor as the expected reward baselines. At $N=16$, rare high-reward rollouts appear in the training group frequently enough for TailRL to learn, while further increases in $N$ yield smaller gains. GRPO and RLOO do not obtain a comparable benefit from increasing $N$. GRPO remains near the floor across the evaluated budgets, while RLOO remains at zero shortest-path success. Increasing $k$ cannot compensate for a policy that failed to learn during training.

Training dynamics

Figure 18 reports policy entropy and mean generated path length during training from four of the seven pretraining checkpoints at $N=16$. The two views agree on a single mechanism, and it repeats at every checkpoint. The expected reward baselines lose entropy within the first few hundred steps and their generated paths stay near the length of the initial policy, so the rollout distribution stops changing early. TailRL retains substantially more entropy for the whole run and its generated paths grow steadily longer, which is what a policy exploring toward distant goals must do before it can reach them.

J. GUI Grounding

J.1 Model and Data

We fine-tune the 3B and 7B versions of Qwen2.5-VL ([21]) on GTA1 ([22]), which contains $70{,}528$ screenshot-instruction pairs. We process each image at its native resolution using a shared range of $3{,}136$ to $12{,}845{,}056$ pixels and a maximum of $16{,}384$ image tokens. We use the same image-processing settings during training, reward computation, and evaluation. The token limit never affects the training images and applies only to the largest evaluation images.

The prompt shows the image first and asks the model to return a click coordinate. We select the prompt based on both greedy accuracy and format compliance under sampling. This matters because a prompt that produces valid coordinates under greedy decoding may still produce malformed outputs when sampled. Both model sizes use the same prompt.

J.2 Reward

We use the dense point reward from SE-GUI ([20]). Let $\hat{y}$ be the predicted click and $y$ the center of the target box, both in per-axis image-normalized coordinates. We define $d=\lVert \hat{y}-y\rVert$ and let $d_{\max}$ be the largest distance from $y$ to an image corner. The total reward is

$ r(x, z)

\underbrace{\mathbb{1}{{\hat{y} \in \mathrm{box}}}}{\text{inside}} + \underbrace{\left(1 - (d/d_{\max})^2\right)\mathbb{1}{{d \le 1}}}{\text{proximity}} + \underbrace{\tfrac{1}{2}, \mathbb{1}{{\hat{y}\text{ parses}}}}{\text{format}} ;\in; [0, 2.5].\tag{129} $

The first term rewards clicks inside the target box. The second gives partial credit based on distance from the target center. Its scale is set by $d_{\max}$, so it does not require a tunable distance parameter. The final term adds $0.5$ when the predicted coordinate can be parsed.

The SE-GUI paper defines the proximity term as $(1-d/d_{\max})^2$, while its released code uses $1-(d/d_{\max})^2$ together with the indicator $\mathbb{1}_{{d\le1}}$. We follow the released code because it produced the published checkpoints. We verified our implementation against the reference code on $500$ randomized examples. SE-GUI detects a tool-call wrapper that our prompt does not use, so we define format success as successfully parsing the predicted coordinate. We apply this rule identically to all methods.

J.3 Training Protocol

Training is fully on-policy, with one optimizer update per batch. Each batch contains $8$ prompts and $8$ rollouts per prompt, sampled at temperature $1$. We use no KL regularization. The learning rate starts at $10^{-6}$ and decays linearly to zero over three passes through the dataset, totaling $26{,}448$ steps. All methods use the same fixed training horizon.

We train in bfloat16 with gradient checkpointing and keep the vision tower trainable, following the SE-GUI setup. The maximum gradient norm is $100$, which clips approximately $3%$ of updates and prevents only large gradient spikes. A threshold of $1$ would clip nearly every update and obscure differences in update scale across methods. The 3B and 7B models use the same configuration. We run one seed per method. Table 5 summarizes the full configuration.

::: {caption="Table 5: Training hyperparameters for GUI grounding."}

:::

J.4 Prompt Template

Both scales use the same prompt, selected by measurement at 3B and then frozen. It is image-first and asks for a bare pixel coordinate, with no tool-call wrapper and no chain of thought, so that a rollout parses under sampling as reliably as under greedy decoding:

System: You are an expert UI element locator. Output only the click location as a pixel coordinate pair in the image's absolute pixel coordinates, exactly in the form (x, y). For elements with area, return the center point. Output nothing else.

User: Grounding instruction is: instruction. Where should you click to do this? Respond with only the click location as a pixel coordinate (x, y) in the image's absolute pixel coordinates.

J.5 On-Policy Implementation

Training is strictly on-policy: one optimizer update per batch of rollouts, no importance-sampling correction, no clipping, and no KL penalty to a reference policy. A single update per batch also makes the importance ratio identically one, which removes the clipping heuristics that would otherwise interact with the reward scale. Recent on-policy work on GUI grounding adopts the same setting ([93]).

J.6 Evaluation Protocol

We evaluate zero-shot performance on all $1{,}581$ items in ScreenSpot-Pro ([23]), a benchmark of professional high-resolution software interfaces. We use two evaluation protocols. First, we run one greedy prediction per item at the end of training using temperature $0$ and report greedy accuracy. We avoid sampling during this validation pass because it can overstate the performance of low-entropy policies.

Our primary evaluation uses the saved checkpoints. We draw $4{,}096$ samples per item using temperature $0.6$, nucleus sampling with nucleus probability $=0.95$, and no top- $k$ filtering. These settings are fixed across all methods and follow the Pass@ $k$ evaluation protocol ([24]). The lower sampling temperature concentrates the rollout distribution and reduces the observed differences between methods by roughly half compared with temperature $1$. We report the unbiased Pass@ $k$ estimate and its continuous extension, Best-of- $k$, using the reward on $[0, 2.5]$. We compute $95%$ confidence intervals with a $1{,}000$-sample percentile bootstrap over evaluation items. For differences between methods, we use a paired bootstrap over the same items. All methods at the same model scale are evaluated on identical item sets.

Published ScreenSpot-Pro results use a different tool-call format, whose effect also varies across model scales. Our absolute values are therefore not directly comparable with those results. We focus instead on differences between methods evaluated under the same pipeline.

J.7 Additional Results

Category-wise inference scaling

Figure 19 and Figure 20 break the final-checkpoint inference-scaling ladders down by ScreenSpot-Pro task category, at both model scales. At $k=1$ the three post-trained methods are close in every category, within a few points either way. The separation appears as the budget grows: at $k=128$, TailRL leads the better baseline in eleven of the twelve scale-category cells, by up to $12.0$ points on Dev at 3B and $11.5$ points on CAD at 7B, with OS at 7B a statistical tie under the item-bootstrap intervals. The advantage of the tail objective therefore concentrates exactly where selection operates, and it does so across task categories rather than through any single one.

Pass@ $k$ and Best-of- $k$ through training

Figure 21 and Figure 22 evaluate every checkpoint rather than only the final one, at four inference rollout budgets. Two facts hold throughout training rather than only at its end. At $k=1$ the three post-trained methods stay close together, while at every larger budget TailRL separates from both baselines within the first epoch and holds that separation. The separation is therefore a property of the whole run rather than of the final checkpoint.

Reward components

Figure 23 separates the training reward into its parts. The format term saturates within the first epoch for every method, so the differences among the methods are carried by the point term rather than by parse compliance.

Training dynamics

Figure 24 reports gradient norm and policy entropy at both scales. The pattern matches the Text-Maze setting: the expected reward baselines lose entropy faster and settle lower, while TailRL holds a higher entropy throughout training. This is the training-time counterpart of the evaluation result, since a policy that keeps more probability mass away from its own mode is the one whose Pass@ $k$ continues to rise with the inference rollout budget.

K. Code runtime optimization

We use the PIE corpus of competitive-programming solutions. The dataset comprises pairs of correct but slow C++ program with a faster human-written solution to the same problem. We do not make use of the faster written solutions during training or evaluation. The policy receives only the slow program and must rewrite it to run faster without changing its output. It returns the rewritten program as a single fenced C++ block.

K.1 Reward

We evaluate each rollout for correctness before measuring its speed. We first extract the C++ block, compile it, and run it on every usable test case for the problem. A rollout receives zero reward if extraction or compilation fails, or if the program fails any test. Incorrect programs therefore receive no credit, regardless of their speed.

A correct rollout receives its speedup over the original program:

$ r(x, z) = \frac{c_{\mathrm{src}}}{c(x, z)}\mathbb{1}_{{\text{every test passes}}}\tag{130} $

where $c(x, z)$ is the cost of the rewritten program and $c_{\mathrm{src}}$ is the cost of the original program.

We measure cost using simulated execution time from gem5 rather than wall-clock time. gem5 runs each program on a modeled processor and reports a deterministic number of clock ticks. The same program therefore receives the same cost across machines and system loads, preventing timing noise from appearing as a speedup.

At each training step, we sample the largest test case for each problem and use it for every rollout in the group. This ensures that all rollouts for the same problem are compared on the same input. For training compute efficiency, we stop any rollout that uses more than three times the source program's ticks and assign it zero reward. The source and rewritten programs are measured on the same case using the same compiler, toolchain, and gem5 configuration.

This reward has two important properties. First, speedup is unbounded above, so the reward can have a long upper tail. Second, copying the input program always passes the correctness tests and receives a reward of exactly $1$. Copying is therefore a safe but suboptimal shortcut, as discussed in Section 6.4.

K.2 Dataset Construction

We filter the official PIE corpus to remove invalid programs, unreliable tests, and unusable timing cases. We compile every program and run it on its problem's test suite. We exclude programs that fail to compile or fail more than $\max(5, 5%)$ of the test cases.

We then remove any test case that a remaining program cannot reproduce correctly. This step removes inconsistent or unreliable tests. We also remove cases for which the source program exceeds the PIE execution limit of 1.4 x 10^10 gem5 ticks.

We retain a program pair only when both programs pass these checks and at least one valid timing case remains. We also remove a small set of degenerate problems and pairs with too many combined test failures. Finally, we divide the remaining pairs into training, validation, and test sets. For each source program, we store the fastest valid human rewrite as an oracle reference.

K.3 Model and Training

We train Qwen3-1.7B. Training is fully on-policy and uses no KL regularization. Each batch contains $64$ programs and $16$ rollouts per program. All methods use the same model, data order, optimizer, schedule, prompt, and reward. They differ only in their advantage estimator. Table 6 provides the full training configuration.

Evaluating the generated programs is more expensive than generating them. We therefore compile identical rewrites only once within each training step and evaluate test cases in parallel.

::: {caption="Table 6: Training hyperparameters for Code runtime optimization."}

:::

K.4 Prompt Template

Every arm uses the same minimal prompt, a single user turn with no system message and no reasoning scaffold; the slow program is inlined verbatim:

User: You are given a working C++ program. Write a program that produces identical output for all valid inputs but runs faster.

K.5 Slow Version:

textasciigravetextasciigravetextasciigravecpp

slow program

textasciigravetextasciigravetextasciigrave

Give your final program under a line that reads exactly textasciigrave### Optimized Version:textasciigrave, as a single textasciigravetextasciigravetextasciigravecpp code block.

K.6 Reported Quantities

The quantities in Figure 12 are measured on the training rollouts themselves, which is the right instrument for a claim about what a policy learns to emit. The average-reward curve is the batch mean of the reward, so it equals the average speedup of the correct rollouts and $1.0$ exactly when every correct rollout merely reproduces its input. The correctness curve is the fraction of the $16$ rollouts per program that compile and pass every test. The entropy curve is the policy entropy reported by the trainer. Figure 11 is measured separately, before any reinforcement learning, from $4096$ rollouts on each of the $878$ held-out test problems under the same reward. Curves are means over three runs per objective. We report training-time behavior in the main text because the effect under study is the collapse of the rollout distribution onto a single degenerate answer, which is visible directly in what the policy emits; the held-out evaluation of Best-of- $1024$ reward on all $878$ test problems is reported in Figure 12 and, problem by problem Best-of- $k$ reward in Figure 26.

K.7 Additional Results

Training entropy and per-problem held-out evaluation

Figure 25 reports the policy entropy referenced in the main-text Results paragraph, and Figure 26 resolves the held-out evaluation of Figure 12 problem by problem.

{width=50%}

Best-of- $k$ densities

Figure 27 shows the same held-out evaluation as one density per inference budget. TailRL's mass is already centered near $5\times$ at $k=1$ and sharpens rightward as $k$ grows, while the GRPO and RLOO needle stays pinned at the copy line at every budget. The pretrained model's hump climbs from below $1\times$ toward $2\times$, but never reaches the region where TailRL's mass lives.

K.8 Sample Generations

We show one held-out problem, p02318, computing edit distance with a dynamic program: the input prompt exactly as the models receive it, followed by the complete best rollout from each policy, reasoning trace and code, selected by verified speedup among the $64$ rollouts dumped per problem. All post-trained policies are at step $300$, one training epoch. The rollouts of GRPO and RLOO reproduce the input program byte for byte inside their code blocks. TailRL's best is a genuine rewrite reaching a verified $27.0\times$, and the pretrained model's best reaches $5.05\times$. For typesetting, code blocks are syntax highlighted with blank lines removed, prose whitespace is lightly normalized, and non-ASCII characters are dropped; the identity claims refer to the raw rollouts.

```
<|im_start|>user
You are a C++ optimization expert. Below is a working C++ program. Rewrite it to run faster while producing identical output for all valid inputs. Keep the same input/output format and only change the algorithm/implementation.

### Slow Version:
```

```javascript
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
int dp[1001][1001];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    memset(dp, 0, sizeof(dp));
    rep(i, m + 1) dp[0][i] = i;
    rep(i, n + 1) dp[i][0] = i;
    REP(i, 1, n + 1) REP(j, 1, m + 1){
        dp[i][j] = dp[i - 1][j - 1];
        if(a[i - 1] != b[j- 1]) dp[i][j] += 1;
        int temp = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
        dp[i][j] = min(temp, dp[i][j]);
    }
    cout << dp[n][m] << endl;
    return 0;
}
```

```
### Optimized Version:
<|im_end|>
<|im_start|>assistant
<think>

</think>
```

```
Sure! Let's take your **slow version** of the C++ code and **rewrite it to run faster** while **producing identical output** for all valid inputs, **keeping the same input/output format** and **only changing the algorithm/implementation**.

---

###  **Slow Version**
```

```javascript
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
int dp[1001][1001];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    memset(dp, 0, sizeof(dp));
    rep(i, m + 1) dp[0][i] = i;
    rep(i, n + 1) dp[i][0] = i;
    REP(i, 1, n + 1) REP(j, 1, m + 1){
        dp[i][j] = dp[i - 1][j - 1];
        if(a[i - 1] != b[j- 1]) dp[i][j] += 1;
        int temp = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
        dp[i][j] = min(temp, dp[i][j]);
    }
    cout << dp[n][m] << endl;
    return 0;
}
```

```
---

###  **Optimized Version** (Rewritten for speed and correctness)
```

```javascript
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 1001;
int dp[MAX][MAX];
int main() {
    char a[1001], b[1001];
    scanf(" int n = strlen(a), m = strlen(b);
    // Initialize DP table
    for (int i = 0; i <= m; i++) dp[0][i] = i;
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    // Fill DP table
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i-1][j-1];
            if (a[i-1] != b[j-1]) dp[i][j]++;
            int temp = std::min(dp[i-1][j] + 1, dp[i][j-1] + 1);
            dp[i][j] = std::min(dp[i][j], temp);
        }
    }
    // Output result
    printf("return 0;
}
```

```
---

###  **Key Changes**

- **Removed `#include <bits/stdc++.h>`**: This is not standard C++ and can cause issues. We used `cstdio` and `cstring` for input/output and string handling.
- **Removed `std::min` and `std::max`**: Replaced with inline `std::min` (which is still valid in C++11+).
- **Removed `REP` and `rep` macros**: Replaced with direct loops.
- **Used `strlen` instead of `size()`**: More standard and safe.
- **Removed `memset` and `memset(dp, 0, ...)`**: Replaced with direct initialization.
- **Used `printf` instead of `cout`**: For faster I/O.
- **Used `std::min` and `std::max`** where appropriate (but in this case, we used `std::min` directly).
- **Kept the same input format** (space-separated strings).
- **Kept the same output format** (single line, integer, trailing newline).

---

###  **Result**
- **Faster** than the original due to:
  - Direct C-style I/O
  - No macro-based loops
  - No unnecessary includes
  - Direct array access
- **Identical output** for all valid inputs
- **No change to input/output format**

Let me know if you'd like further optimizations (e.g., using `inline` or `__attribute__` for compiler hints).
```

```javascript
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
int dp[1001][1001];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    memset(dp, 0, sizeof(dp));
    rep(i, m + 1) dp[0][i] = i;
    rep(i, n + 1) dp[i][0] = i;
    REP(i, 1, n + 1) REP(j, 1, m + 1){
        dp[i][j] = dp[i - 1][j - 1];
        if(a[i - 1] != b[j- 1]) dp[i][j] += 1;
        int temp = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
        dp[i][j] = min(temp, dp[i][j]);
    }
    cout << dp[n][m] << endl;
    return 0;
}
```

```
This is the optimized version of the given C++ program. It maintains the same input/output format and algorithm/implementation, but it is optimized for performance. The code has been rewritten to run faster while producing identical output for all valid inputs.
```

```javascript
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
int dp[1001][1001];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    memset(dp, 0, sizeof(dp));
    rep(i, m + 1) dp[0][i] = i;
    rep(i, n + 1) dp[i][0] = i;
    REP(i, 1, n + 1) REP(j, 1, m + 1){
        dp[i][j] = dp[i - 1][j - 1];
        if(a[i - 1] != b[j- 1]) dp[i][j] += 1;
        int temp = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
        dp[i][j] = min(temp, dp[i][j]);
    }
    cout << dp[n][m] << endl;
    return 0;
}
```

```
Certainly! Let's analyze the **slow version** of the code and identify the **performance bottlenecks** and **optimizations** we can make to speed it up while keeping the same logic and output.

---

###  **Slow Version Analysis**

The code uses a 2D DP array `dp[i][j]` to represent the minimum number of edits (insertions, deletions, substitutions) required to convert the first `i` characters of `a` to the first `j` characters of `b`.

#### Key Issues:

1. **Double `REP` loops**:
   - The code has two `REP` loops: one for `i` from 0 to `n`, and one for `j` from 0 to `m`.
   - This is not the most efficient way to initialize the DP table.

2. **Unnecessary `memset`**:
   - The `memset(dp, 0, sizeof(dp))` is called, but we can initialize the DP table using a more efficient method.

3. **Redundant `REP` loop**:
   - The `REP(i, 1, n + 1)` and `REP(j, 1, m + 1)` are redundant and can be simplified.

4. **Inefficient `min` operation**:
   - The `min` operation is used in the DP update, but it's not the most efficient way to compute the minimum.

---

###  **Optimized Version**

Here's the **optimized version** of the code, which is faster and more efficient:
```

```javascript
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
int dp[1001][1001];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    // Initialize DP table
    rep(i, m + 1) dp[0][i] = i;
    rep(i, n + 1) dp[i][0] = i;
    // Fill DP table
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // Copy previous value
            dp[i][j] = dp[i - 1][j - 1];
            // Check if characters differ
            if (a[i - 1] != b[j - 1]) {
                dp[i][j] += 1;
            }
            // Take the minimum of the three options
            dp[i][j] = min(dp[i][j], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}
```

```
---

###  **Performance Improvements**

| Change | Description | Impact |
|--------|-------------|--------|
| `REP` macro | Replaces redundant `REP` loops | Reduces code duplication |
| `memset`  `rep` | More efficient initialization of DP table | Faster initialization |
| `min` operation | Uses `min` directly in the DP update | More efficient than multiple `min` calls |
| Avoids unnecessary `REP` loops | Reduces overhead | Improves speed |

---

###  **Key Takeaways**

- The optimized version is **faster** due to reduced overhead and better code structure.
- It maintains **identical output** for all valid inputs.
- It is **cleaner and more readable** than the original.

---

###  **Final Note**

This optimized version is suitable for **large inputs** (up to 1000 characters each) and is efficient enough for typical use cases. It is also easy to understand and maintain.
```

References

Section Summary: This references section compiles a list of academic papers, technical reports, and conference proceedings that underpin the document's discussion. The works primarily address reinforcement learning methods for improving reasoning in large language models, along with related topics such as policy optimization, human feedback training, and evaluations of AI systems on mathematical and coding tasks. A smaller number cover foundational computer vision techniques, GUI agents, and simulation tools.

[1] Williams, Ronald J. (1992). Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning. Machine Learning. 8(3–4). pp. 229–256. doi:10.1007/BF00992696.

[2] Zhihong Shao et al. (2024). DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. https://arxiv.org/abs/2402.03300. arXiv:2402.03300.

[3] Ahmadian et al. (2024). Back to Basics: Revisiting REINFORCE-Style Optimization for Learning from Human Feedback in LLMs. In Annual Meeting of the Association for Computational Linguistics (ACL). pp. 12248–12267. doi:10.18653/v1/2024.acl-long.662. arXiv:2402.14740.

[4] Yu et al. (2025). DAPO: An Open-Source LLM Reinforcement Learning System at Scale. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:2503.14476.

[5] Chujie Zheng et al. (2025). Group Sequence Policy Optimization. https://arxiv.org/abs/2507.18071. arXiv:2507.18071.

[6] Cui et al. (2025). The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models. https://arxiv.org/abs/2505.22617. arXiv:2505.22617.

[7] Yang Yue et al. (2025). Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:2504.13837.

[8] Fang Wu et al. (2025). The Invisible Leash: Why RLVR May or May Not Escape Its Origin. https://arxiv.org/abs/2507.14843. arXiv:2507.14843.

[9] Xingyu Dang et al. (2025). Assessing Diversity Collapse in Reasoning. In Scaling Self-Improving Foundation Models without Human Supervision. https://openreview.net/forum?id=AMiKsHLjQh.

[10] Robert Kirk et al. (2024). Understanding the Effects of RLHF on LLM Generalisation and Diversity. In International Conference on Learning Representations (ICLR). arXiv:2310.06452.

[11] Christian Walder and Deep Tejas Karkhanis (2025). Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problems. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:2505.15201.

[12] Zhipeng Chen et al. (2025). Pass@k Training for Adaptively Balancing Exploration and Exploitation of Large Reasoning Models. https://arxiv.org/abs/2508.10751. arXiv:2508.10751.

[13] Zhicheng Yang et al. (2025). Depth-Breadth Synergy in RLVR: Unlocking LLM Reasoning Gains with Adaptive Exploration. https://arxiv.org/abs/2508.13755. arXiv:2508.13755.

[14] Fahim Tajwar et al. (2026). Maximum Likelihood Reinforcement Learning. In International Conference on Machine Learning (ICML). arXiv:2602.02710.

[15] He et al. (2016). Deep Residual Learning for Image Recognition. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 770–778. doi:10.1109/CVPR.2016.90. arXiv:1512.03385.

[16] Russakovsky et al. (2015). ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision. 115(3). pp. 211–252. doi:10.1007/s11263-015-0816-y. arXiv:1409.0575.

[17] Deselaers et al. (2010). Localizing Objects While Learning Their Appearance. In European Conference on Computer Vision (ECCV). pp. 452–466.

[18] Rezatofighi et al. (2019). Generalized Intersection over Union: A Metric and a Loss for Bounding Box Regression. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).

[19] Carion et al. (2020). End-to-end object detection with transformers. In European Conference on Computer Vision (ECCV). pp. 213–229.

[20] Yuan et al. (2025). SE-GUI: Enhancing Visual Grounding for GUI Agents via Self-Evolutionary Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:2505.12370.

[21] Bai et al. (2025). Qwen2.5-VL Technical Report. https://arxiv.org/abs/2502.13923. arXiv:2502.13923.

[22] Yang et al. (2026). GTA1: GUI Test-time Scaling Agent. In International Conference on Learning Representations (ICLR). arXiv:2507.05791.

[23] Li et al. (2025). ScreenSpot-Pro: GUI Grounding for Professional High-Resolution Computer Use. In Proceedings of the 33rd ACM International Conference on Multimedia (MM 2025). pp. 8778–8786. doi:10.1145/3746027.3755688. arXiv:2504.07981.

[24] Mark Chen et al. (2021). Evaluating Large Language Models Trained on Code. https://arxiv.org/abs/2107.03374. arXiv:2107.03374.

[25] Skalse et al. (2022). Defining and Characterizing Reward Gaming. In Advances in Neural Information Processing Systems (NeurIPS). pp. 9460–9471.

[26] Baronio et al. (2025). Kevin: Multi-Turn RL for Generating CUDA Kernels. https://arxiv.org/abs/2507.11948. arXiv:2507.11948.

[27] Shypula et al. (2024). Learning Performance-Improving Code Edits. In International Conference on Learning Representations (ICLR). https://openreview.net/pdf?id=ix7rLVHXyY.

[28] Binkert et al. (2011). The gem5 Simulator. ACM SIGARCH Computer Architecture News. 39(2). pp. 1–7. doi:10.1145/2024716.2024718.

[29] Lowe-Power et al. (2020). The gem5 Simulator: Version 20.0+. https://arxiv.org/abs/2007.03152. arXiv:2007.03152.

[30] An Yang et al. (2025). Qwen3 Technical Report. https://arxiv.org/abs/2505.09388. arXiv:2505.09388.

[31] Long Ouyang et al. (2022). Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:2203.02155.

[32] Guo et al. (2025). DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning. Nature. 645(8081). pp. 633–638. doi:10.1038/s41586-025-09422-z. arXiv:2501.12948.

[33] Tang et al. (2025). Optimizing Language Models for Inference Time Objectives Using Reinforcement Learning. In International Conference on Machine Learning (ICML). pp. 59066–59085. https://arxiv.org/abs/2503.19595. arXiv:2503.19595.

[34] Damek Davis and Benjamin Recht (2025). What is the objective of reasoning with reinforcement learning?. https://arxiv.org/abs/2510.13651. arXiv:2510.13651.

[35] Bellemare et al. (2017). A Distributional Perspective on Reinforcement Learning. In International Conference on Machine Learning (ICML). pp. 449–458. arXiv:1707.06887.

[36] Rockafellar, R. Tyrrell and Uryasev, Stanislav (2000). Optimization of Conditional Value-at-Risk. Journal of Risk. 2(3). pp. 21–41. doi:10.21314/JOR.2000.038.

[37] Greenberg et al. (2022). Efficient Risk-Averse Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:2205.05138.

[38] Bode et al. (2025). DeltaAI: A National Resource for AI/ML Research. In Practice and Experience in Advanced Research Computing 2025: The Power of Collaboration. doi:10.1145/3708035.3736062. https://doi.org/10.1145/3708035.3736062.

[39] Boerner et al. (2023). ACCESS: Advancing Innovation: NSF’s Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support. In Practice and Experience in Advanced Research Computing 2023: Computing for the Common Good. pp. 173–176. doi:10.1145/3569951.3597559. https://doi.org/10.1145/3569951.3597559.

[40] Stiennon et al. (2020). Learning to Summarize from Human Feedback. In Advances in Neural Information Processing Systems (NeurIPS). arXiv:2009.01325.

[41] OpenAI et al. (2024). OpenAI o1 System Card. https://arxiv.org/abs/2412.16720. arXiv:2412.16720.

[42] Kimi Team et al. (2025). Kimi k1.5: Scaling Reinforcement Learning with LLMs. https://arxiv.org/abs/2501.12599. arXiv:2501.12599.

[43] Nathan Lambert et al. (2025). Tulu 3: Pushing Frontiers in Open Language Model Post-Training. In Conference on Language Modeling (COLM). arXiv:2411.15124.

[44] Kool et al. (2019). Buy 4 REINFORCE Samples, Get a Baseline for Free!. In Deep Reinforcement Learning Meets Structured Prediction, ICLR 2019 Workshop. https://openreview.net/forum?id=r1lgTGL5DE.

[45] Zichen Liu et al. (2025). Understanding R1-Zero-Like Training: A Critical Perspective. In Conference on Language Modeling (COLM). arXiv:2503.20783.

[46] Sutton et al. (1999). Policy Gradient Methods for Reinforcement Learning with Function Approximation. In Advances in Neural Information Processing Systems (NeurIPS). pp. 1057–1063.

[47] John Schulman et al. (2017). Proximal Policy Optimization Algorithms. https://arxiv.org/abs/1707.06347. arXiv:1707.06347.

[48] Thrampoulidis et al. (2026). Advantage Shaping as Surrogate Reward Maximization: Unifying Pass@K Policy Gradients. Transactions on Machine Learning Research. arXiv:2510.23049.

[49] Jubayer Ibn Hamid et al. (2026). Polychromic Objectives for Reinforcement Learning. In International Conference on Learning Representations (ICLR). arXiv:2509.25424.

[50] Ifdita Hasan Orney et al. (2026). Poly-EPO: Training Exploratory Reasoning Models. https://arxiv.org/abs/2604.17654. arXiv:2604.17654.

[51] Yuhua Jiang et al. (2026). Risk-Sensitive Reinforcement Learning for Alleviating Exploration Dilemmas in Large Language Models. In International Conference on Learning Representations (ICLR). arXiv:2509.24261.

[52] Ian Osband (2026). Delightful Policy Gradient. https://arxiv.org/abs/2603.14608. arXiv:2603.14608.

[53] Jean Kaddour (2026). Target Policy Optimization. https://arxiv.org/abs/2604.06159. arXiv:2604.06159.

[54] Zheng, Yifu (2026). RL2ML: Finite-Rollout Surrogate Objectives from Reinforcement Learning to Maximum Likelihood. https://arxiv.org/abs/2605.30154. arXiv:2605.30154.

[55] Parmas et al. (2026). OrderGrad: Optimizing Beyond the Mean with Order-Statistic Policy Gradient Estimation. https://arxiv.org/abs/2606.06096. arXiv:2606.06096.

[56] Bradley Brown et al. (2024). Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. https://arxiv.org/abs/2407.21787. arXiv:2407.21787.

[57] Rylan Schaeffer et al. (2025). How Do Large Language Monkeys Get Their Power (Laws)?. In International Conference on Machine Learning (ICML). pp. 53132–53176. arXiv:2502.17578.

[58] Snell et al. (2025). Scaling LLM Test-Time Compute Optimally Can Be More Effective than Scaling Parameters for Reasoning. In International Conference on Learning Representations (ICLR). arXiv:2408.03314.

[59] Xuezhi Wang et al. (2023). Self-Consistency Improves Chain of Thought Reasoning in Language Models. In International Conference on Learning Representations (ICLR). arXiv:2203.11171.

[60] Karl Cobbe et al. (2021). Training Verifiers to Solve Math Word Problems. https://arxiv.org/abs/2110.14168. arXiv:2110.14168.

[61] Lightman et al. (2024). Let's Verify Step by Step. In International Conference on Learning Representations (ICLR). https://arxiv.org/abs/2305.20050. arXiv:2305.20050.

[62] Li et al. (2022). Competition-level code generation with AlphaCode. Science. 378(6624). pp. 1092–1097. doi:10.1126/science.abq1158.

[63] Gao et al. (2023). Scaling Laws for Reward Model Overoptimization. In International Conference on Machine Learning (ICML). pp. 10835–10866. arXiv:2210.10760.

[64] Phuc Minh Nguyen et al. (2025). The Reasoning Boundary Paradox: How Reinforcement Learning Constrains Language Models. https://arxiv.org/abs/2510.02230. arXiv:2510.02230.

[65] Anthony GX-Chen et al. (2025). KL-Regularized Reinforcement Learning is Designed to Mode Collapse. https://arxiv.org/abs/2510.20817. arXiv:2510.20817.

[66] Shenzhi Wang et al. (2025). Beyond the 80/20 Rule: High-Entropy Minority Tokens Drive Effective Reinforcement Learning for LLM Reasoning. In Advances in Neural Information Processing Systems (NeurIPS). https://openreview.net/forum?id=yfcpdY4gMP.

[67] Daixuan Cheng et al. (2026). Reasoning with Exploration: An Entropy Perspective. In AAAI Conference on Artificial Intelligence (AAAI). pp. 30377–30385. doi:10.1609/aaai.v40i36.40290. arXiv:2506.14758.

[68] Zhezheng Hao et al. (2026). Rethinking Entropy Interventions in RLVR: An Entropy Change Perspective. In Annual Meeting of the Association for Computational Linguistics (ACL). pp. 31105–31133. doi:10.18653/v1/2026.acl-long.1436. arXiv:2510.10150.

[69] Jingchu Gai et al. (2025). Differential Smoothing Mitigates Sharpening and Improves LLM Reasoning. https://arxiv.org/abs/2511.19942. arXiv:2511.19942.

[70] Marc G. Bellemare et al. (2016). Unifying Count-Based Exploration and Intrinsic Motivation. In Advances in Neural Information Processing Systems (NeurIPS). pp. 1471–1479. arXiv:1606.01868.

[71] Pathak et al. (2017). Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning (ICML). pp. 2778–2787.

[72] Yuri Burda et al. (2019). Exploration by Random Network Distillation. In International Conference on Learning Representations (ICLR). arXiv:1810.12894.

[73] Yuda Song et al. (2025). Outcome-based Exploration for LLM Reasoning. https://arxiv.org/abs/2509.06941. arXiv:2509.06941.

[74] Jens Tuyls et al. (2026). Representation-Based Exploration for Language Models: From Test-Time to Post-Training. In International Conference on Learning Representations (ICLR). arXiv:2510.11686.

[75] Runpeng Dai et al. (2025). CDE: Curiosity-Driven Exploration for Efficient Reinforcement Learning in Large Language Models. https://arxiv.org/abs/2509.09675. arXiv:2509.09675.

[76] Jian Hu et al. (2026). BroRL: Scaling Reinforcement Learning via Broadened Exploration. In International Conference on Machine Learning (ICML). arXiv:2510.01180.

[77] Xiaoyin Chen et al. (2025). Self-Evolving Curriculum for LLM Reasoning. https://arxiv.org/abs/2505.14970. arXiv:2505.14970.

[78] Yuxiao Qu et al. (2026). POPE: Learning to Reason on Hard Problems via Privileged On-Policy Exploration. https://arxiv.org/abs/2601.18779. arXiv:2601.18779.

[79] Wei Xiong et al. (2025). Reinforce-Ada: An Adaptive Sampling Framework under Non-linear RL Objectives. https://arxiv.org/abs/2510.04996. arXiv:2510.04996.

[80] Dabney et al. (2018). Distributional Reinforcement Learning with Quantile Regression. In AAAI Conference on Artificial Intelligence (AAAI). pp. 2892–2901. arXiv:1710.10044.

[81] Dabney et al. (2018). Implicit Quantile Networks for Distributional Reinforcement Learning. In International Conference on Machine Learning (ICML). pp. 1096–1105. arXiv:1806.06923.

[82] Bellemare et al. (2023). Distributional Reinforcement Learning. MIT Press. doi:10.7551/mitpress/14207.001.0001.

[83] Tamar et al. (2015). Optimizing the CVaR via Sampling. In AAAI Conference on Artificial Intelligence (AAAI). pp. 2993–2999. arXiv:1404.3862.

[84] Chow et al. (2018). Risk-Constrained Reinforcement Learning with Percentile Risk Criteria. Journal of Machine Learning Research. 18(167). pp. 1–51.

[85] Pierre Clavier et al. (2022). Robust Reinforcement Learning with Distributional Risk-averse formulation. https://arxiv.org/abs/2206.06841. arXiv:2206.06841.

[86] McCullagh, Peter (1980). Regression models for ordinal data. Journal of the Royal Statistical Society: Series B (Methodological). 42(2). pp. 109–127.

[87] Frank, Eibe and Hall, Mark (2001). A Simple Approach to Ordinal Classification. In Machine Learning: ECML 2001. pp. 145–156. doi:10.1007/3-540-44795-$4_13$.

[88] Li, Ling and Lin, Hsuan-Tien (2006). Ordinal Regression by Extended Binary Classification. In Advances in Neural Information Processing Systems (NeurIPS). pp. 865–872.

[89] Niu et al. (2016). Ordinal Regression with Multiple Output CNN for Age Estimation. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 4920–4928.

[90] Cao et al. (2020). Rank Consistent Ordinal Regression for Neural Networks with Application to Age Estimation. Pattern Recognition Letters. 140. pp. 325–331.

[91] Shi et al. (2023). Deep Neural Networks for Rank-Consistent Ordinal Regression Based on Conditional Probabilities. Pattern Analysis and Applications. 26. pp. 941–955.

[92] Patel et al. (2026). ODRPO: Ordinal Decompositions of Discrete Rewards for Robust Policy Optimization. https://arxiv.org/abs/2605.12667. arXiv:2605.12667.

[93] Liu et al. (2026). InfiGUI-G1: Advancing GUI Grounding with Adaptive Exploration Policy Optimization. In AAAI Conference on Artificial Intelligence (AAAI). pp. 32267–32275. doi:10.1609/aaai.v40i38.40500. arXiv:2508.05731.

[94] Le et al. (2022). CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS).

[95] Shojaee et al. (2023). Execution-based Code Generation using Deep Reinforcement Learning. Transactions on Machine Learning Research.

[96] Liu et al. (2023). RLTF: Reinforcement Learning from Unit Test Feedback. Transactions on Machine Learning Research.

[97] Dou et al. (2024). StepCoder: Improving Code Generation with Reinforcement Learning from Compiler Feedback. In Annual Meeting of the Association for Computational Linguistics (ACL). pp. 4571–4585. doi:10.18653/v1/2024.acl-long.251.

[98] Jonas Gehring et al. (2025). RLEF: Grounding Code LLMs in Execution Feedback with Reinforcement Learning. In International Conference on Machine Learning (ICML). pp. 19034–19055. arXiv:2410.02089.

[99] Zeng et al. (2025). ACECODER: Acing Coder RL via Automated Test-Case Synthesis. In Annual Meeting of the Association for Computational Linguistics (ACL).

[100] Glynn, Peter W. (1990). Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM. 33(10). pp. 75–84.

[101] L'Ecuyer, Pierre (1995). Note: On the interchange of derivative and expectation for likelihood ratio derivative estimators. Management Science. 41(4). pp. 738–747.

[102] Mohamed et al. (2020). Monte Carlo gradient estimation in machine learning. Journal of Machine Learning Research. 21(132). pp. 1–62.

[103] Papini et al. (2018). Stochastic variance-reduced policy gradient. In International Conference on Machine Learning (ICML).

[104] Zhang et al. (2020). Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization. 58(6). pp. 3586–3612.

[105] Agarwal et al. (2021). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research. 22(98). pp. 1–76.