TailRL: Tail-Likelihood Reinforcement Learning

GUI grounding. Given a screenshot of a professional application and a plain-language instruction, such as open the layer panel, the model returns the pixel coordinates to click on. The interfaces are dense and the targets are small, so a click either lands inside the right element or it does not. Pass@$k$ is the chance that one of $k$ sampled clicks lands on it.

Pass@k, Best-of-k reward and training accuracy for Qwen2.5-VL 3B and 7B on ScreenSpot-Pro. The TailRL Pass@k curves keep climbing with the rollout budget while RLOO flattens and GRPO trails, even though training accuracy is similar for all three. — All three methods reach similar training accuracy, so after training they look alike. They separate as you sample: TailRL matches RLOO's best result using **$128\times$ fewer inference samples** at 3B and **$256\times$ fewer** at 7B.

TailRL trains for every sampling budget at once

TailRL's gradient is a harmonic combination of Best-of-$k$ gradients. Rather than committing to one sampling budget, it improves the policy at all of them together, and the $1/k$ weights fall out of the objective rather than being chosen.

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

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

What is Tail-Likelihood?

A reward density over the unit interval. A dashed line at a threshold tau splits it, and the shaded mass to the right of tau is labelled as the probability that a rollout's reward exceeds tau.

Why Tail-Likelihood Reinforcement Learning?

Reward densities on the unit interval. The base policy is broad and low. GRPO collapses to a narrow peak at a moderate reward. TailRL sits further right and keeps a second lobe of mass in the high-reward tail, so its mean is higher and its tail is thicker.

Standard reinforcement learning only maximizes the mean reward, losing coverage over rare excellent outputs. TailRL maximizes the policy's mean reward while simultaneously maximizing its tail-probabilities.

Three panels. Left: RL post-training reshapes the base policy's reward distribution; GRPO and RLOO sharpen it around the mean while TailRL grows a heavy high-reward tail. Middle: expected-reward RL pulls a single rope, the mean. Right: TailRL pulls a rope at every reward threshold, hardest at the rarest. — **Expected reward pulls one rope; TailRL pulls them all.** Expected-reward methods shift the reward distribution and sharpen it around the mean, improving it through that single handle. TailRL pulls up the tail-probability $p_\theta(x,\tau)$ at every threshold at once, hardest at the rarest, and grows a heavy high-reward tail.

Let's manipulate the reward distribution

Two policies can have the same expected reward and very different odds of producing an exceptional sample. Every preset opens as a matched pair with equal mean reward but different tail probabilities. This difference is reflected in their Best-of-$k$ as we increase sampling.

Drag inside either histogram to move mass between reward values.

Even if the mean is identical, the policy with the stronger tail keeps improving as sampling compute grows.

Tail-Likelihood Reinforcement Learning

Expected-reward RL

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

Expected reward

TailRL

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

Expected log tail-probability across reward thresholds

TailRL is the expected log tail-probability over uniformly sampled thresholds.

On binary rewards every nontrivial threshold asks the same question, did the rollout succeed, so the integral collapses to a single log-likelihood and TailRL reduces exactly to MaxRL.

The gradients of both objectives are a weighted sum of the score-function $S(x,z) := \nabla_\theta \log \pi_\theta(z \mid x)$.

Expected-reward RL

$\nabla_\theta J_{\mathrm{RL}}(\theta;x) = \mathbb{E}_{z}\!\left[\,r(x,z)\,S(x,z)\right]$

Weight: the reward itself

TailRL

$\nabla_\theta J_{\mathrm{TailRL}}(\theta;x) = \mathbb{E}_{z}\!\left[\left(\displaystyle\int_0^{r(x,z)}\frac{d\tau}{p_\theta(x,\tau)}\right)S(x,z)\right]$

Weight: expected inverse tail-probability

TailRL upweights the gradient of rollouts that are rare and excellent. Where the tail-probability $p_\theta(x,\tau)$ is low, $1/p_\theta(x,\tau)$ is large, so a rollout clearing reward thresholds the policy almost never reaches counts for far more than its reward alone would say.

Aligned with inference time objectives

The gradient of TailRL naturally decomposes as harmonically weighted gradients of Best-of-$k$ objectives.

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

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

The harmonic weights $1/k$ are derived from the Maclaurin series of the logarithm. They are not selected or tuned. The sum runs over every budget, so TailRL combines Best-of-$k$ objectives across inference budgets instead of committing to one.

Computing tail probabilities from finite rollouts

During training you never see the true tail probability. You see a group of $N$ rollouts and their rewards. Estimating it is just counting: fix a reward threshold $\tau$ and ask how many of the $N$ rollouts beat it.

$\hat p_\theta(x,\tau) \;=\; \dfrac{1}{N}\displaystyle\sum_{i=1}^{N}\mathbf{1}\!\left\{r_i > \tau\right\}$

Now slide the threshold from $0$ up to $1$. At each threshold we ask what fraction of rollouts attained a higher reward. That staircase is the tail-probability curve.

A rollout's continuous reward is compared against a ladder of reward thresholds; each comparison is a pass/fail test, and averaging the passes across a group of rollouts traces the tail-probability curve.

Easy plug-in for RLVR pipelines

In an existing RLVR pipeline this is a few lines inside the advantage computation: no critic, and no new hyperparameter. The advantages can simply be written as:

$\omega\!\left(r_{(i)}\right) = \displaystyle\sum_{k=1}^{i}\frac{r_{(k)}-r_{(k-1)}}{N-k+1}, \qquad A_i = \omega(r_i) - \bar\omega$

Pseudocode

Require rewards $r_1,\ldots,r_N$ from $N$ training rollouts for an input $x$
Sort the rewards increasingly: $r_{(1)}\le\cdots\le r_{(N)}$
Keep the sorting permutation, and set $r_{(0)}\gets 0$ and $\omega_{(0)}\gets 0$
for $i=1,\ldots,N$ do
1. $\omega_{(i)}\gets\omega_{(i-1)}+\dfrac{r_{(i)}-r_{(i-1)}}{N-i+1}$
$\bar\omega\gets\dfrac{1}{N}\sum_{j=1}^{N}\omega_{(j)}$
for $i=1,\ldots,N$ do
1. $A_{(i)}\gets\omega_{(i)}-\bar\omega$
Undo the sorting permutation: $A_{(1)},\ldots,A_{(N)}\rightarrow A_1,\ldots,A_N$
Ensure advantages $A_1,\ldots,A_N$

In a group-based RLVR pipeline, only the advantage computation changes.

Comparing REINFORCE and TailRL advantages

Both methods see identical rollouts and turn them into advantages. REINFORCE promotes a rollout by its raw margin over the group, so its update is spread roughly in proportion to reward. TailRL splits each reward gap among the rollouts that reach it, so a gap only the best rollout clears is worth $N$ times a gap everybody clears.

Draw your own reward distribution, then set how many rollouts are drawn from it.

Rollouts $N$ 64 Distribution

Drag inside the shaded band to reshape the reward distribution. Each advantage panel is scaled by its own largest magnitude, so compare the shape; the printed bounds carry the scale.

Rare, exceptional rollouts stay visible to the update instead of disappearing into the mean.

TailRL moves the sampling-compute frontier

Across every tested model and task, TailRL improves the performance-versus-sampling-compute frontier over expected-reward baselines. The largest gaps appear when exceptional outcomes are rare, or when a safe, moderate shortcut dominates the mean.

ImageNet Object Localization

Put a box around the object, without naming it. A rollout is one sampled box, scored by its overlap (IoU) with the true box. The set of boxes is finite, so here the exact objective can be computed rather than estimated.

How good is the population-level objective?

Trained on overlap alone, population TailRL matches or beats supervised objectives that see the true coordinates, leading the strongest of them, L1+GIoU, on both CorLoc thresholds.

Three panels showing CorLoc at 0.5, CorLoc at 0.75 and mean IoU against training epochs. The population TailRL curve sits at or above the L1, GIoU and L1+GIoU supervised baselines throughout. — CorLoc@$0.5$, CorLoc@$0.75$ and mean IoU for population TailRL against the supervised baselines L1, GIoU and L1+GIoU.

Takeaway Using only a scalar reward, the population-level objective performs as well as or better than task-specific supervised objectives.

Does the finite estimator approach the exact objective?

Larger training groups move the estimator toward that exact objective, and every TailRL budget stays above the expected-reward baselines.

Three panels showing CorLoc at 0.5, mean IoU and Best-of-1024 IoU against training epochs. TailRL curves at increasing rollout budgets rise toward a dashed exact-objective reference, and all sit above the GRPO, RLOO and PKPO curves. — CorLoc@$0.5$, mean IoU and Best-of-$1024$ IoU on the held-out validation set. TailRL trains at $N\in\{16,64,256,1024\}$, darker curves for larger $N$; the dashed curve optimizes the exactly computed population objective. GRPO, RLOO and PKPO ($k_{\mathrm{opt}}=16$) use $N=1024$.

Takeaway As the training rollout budget grows, the finite-rollout estimator converges to the population-level objective.

Maze Navigation: Bootstrapping from Weak Initializations

A small transformer solves mazes written as text. Stopping pretraining at different points gives starting policies from almost hopeless to occasionally successful. Reward gives partial credit for getting closer to the goal, and more for shorter paths.

Can RL bootstrap from a poor initial policy?

Pass@1 after RL plotted against Pass@1 before RL for TailRL, GRPO, RLOO and PKPO. In the shaded poor-initialization region the TailRL curve stays high, RLOO and GRPO start at zero, and PKPO sits well below TailRL. — Pass@$1$ before and after post-training with $N=16$. The shaded region marks poor policy initialization.

From a poor initialization, GRPO and RLOO fail to improve reliably. TailRL holds up across the whole sweep; PKPO trails it everywhere and falls off once successes are common.

Takeaway TailRL outperforms the other methods when the initial policy has poor coverage over rare excellent rollouts.

Code Runtime Optimization

Can the objective escape a safe but useless shortcut?

The initial reward distribution on PIE: a large mass of incorrect rollouts at zero, a tall spike at a speedup of one from copying the input, and a thin tail of correct and faster programs. — Before training: $74.4\%$ of rollouts are wrong, $23.5\%$ are correct but no faster, which is the spike at $1\times$, and only $2.1\%$ are correct and faster.

Each input is a slow C++ program, and the model rewrites it to run faster without breaking it. A rollout scores zero if it fails any test, otherwise its speedup over the input, timed in gem5 so noise cannot fake a gain.

Copying the input passes every test and earns reward $1$. It is by far the easiest thing to reach.

Three panels: mean training reward over one epoch, the density of per-problem Best-of-1024 reward on the test set, and correctness probability during training. TailRL's reward climbs well above the copying value while GRPO and RLOO settle at it. — Mean reward over one epoch (left), per-problem Best-of-$1024$ reward on the test set (middle), where GRPO and RLOO coincide at $1.0$, and the fraction of rollouts passing every test (right).

Takeaway When an easy suboptimal solution exists, expected-reward methods settle for it. TailRL keeps searching and learns to produce rarer and better outcomes.

GUI Grounding with Vision-Language Models

Do similar one-sample policies scale differently with more inference?

Given a screenshot and an instruction, the model outputs where to click. Reward combines how close the click lands, a bonus for landing inside the target, and a format bonus. Qwen2.5-VL at 3B and 7B, evaluated on ScreenSpot-Pro.

Takeaway TailRL scales better with inference compute than the expected-reward baselines.

Expected-reward training fails in two ways: it overlooks rare good outcomes, or it collapses to a frequent moderate one. TailRL addresses both by keeping rarely reached reward thresholds influential.

Read the paper View the code Copy BibTeX soon

BibTeX

@article{ramasubramanian2026tailrl,
  title   = {Tail-Likelihood Reinforcement Learning},
  author  = {Ramasubramanian, Shrinivas and Arora, Daman and Tajwar, Fahim and Zeng, Guanning
             and Wu, Qingyang and Zhou, Zhongzhu and Xu, Chenfeng and Feng, Haiwen and Song, Yuda
             and Singh, Aarti and Salakhutdinov, Ruslan and Bagnell, J. Andrew and Schneider, Jeff
             and Zanette, Andrea},
  journal = {arXiv preprint},
  year    = {2026}
}