PaperlayerView exact revision on arXiv

Source-linked AI summary

Tail-Likelihood Reinforcement Learning

Shrinivas Ramasubramanian, Daman Arora, Fahim Tajwar, Guanning Zeng, Qingyang Wu, Zhongzhu Zhou, Chenfeng Xu, Haiwen Feng, Yuda Song, Aarti Singh, Ruslan Salakhutdinov, J. Andrew Bagnell, Jeff Schneider, Andrea Zanette

arXiv:2609.02987v1cs.LGstat.ML

TL;DR

Average reward can obscure a policy’s chance of producing rare, exceptionally good rollouts, limiting how well it captures the value of additional samples. TailRL optimizes upper-tail likelihoods instead, and across four settings it improves learning from rare outcomes, sample scaling, and resistance to suboptimal collapse.

  • Problem

    Expected-reward and fixed-threshold objectives do not fully preserve continuous reward information or distinguish policies’ probabilities of producing rare, high-reward rollouts.

    Source: §1 · p. 1, §3.3 · p. 5

  • Method

    TailRL maximizes the log-probability of exceeding a uniformly sampled reward threshold, emphasizing rare upper-tail events through a simple advantage-function modification.

    Source: §1 · p. 2, §5 · p. 8

  • Results

    Across four settings, TailRL matches strong baselines, uses 128–256× fewer inference rollouts for GUI grounding, and achieves a 7.7× Best-of-1024 speedup on code optimization.

    Source: §1 · pp. 2–3, §8 · p. 14

  • Takeaways & Limitations

    TailRL is most beneficial when high-reward rollouts are rare or training tends toward common suboptimal behavior, improving learning reliability and sample scaling.

    Source: §8 · p. 14

    The formulation assumes a deterministic reward function with bounded rewards in [0, 1].

    Source: §2 · p. 3

Abstract

from arXiv · show

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.

1 Introduction

TailRL addresses the loss of rare, high-reward rollout coverage hidden by mean-reward optimization by maximizing tail likelihood across reward thresholds. It connects this objective to inference-time scaling, admits an unbiased finite-rollout estimator, and improves performance across four tasks.

Motivation

  • Mean reward can hide large differences in rare high-reward rollout probabilities, whose coverage determines gains from additional training or inference samples.Standard RL can lose these rollouts, degrading Best-of-k performance and limiting inference-time scaling.Source: §1 · p. 1

TailRL objective

  • TailRL treats each reward threshold as a binary success event and maximizes the log-probability of exceeding a uniformly drawn threshold.For rewards in [0, 1], this continuous-reward objective requires no threshold or weighting hyperparameter and reduces to MaxRL for binary rewards.Source: §1 · p. 2

Inference-time scaling

  • TailRL optimizes upper-tail probabilities across reward levels, and its gradient decomposes into a harmonic mixture of Best-of-k gradients.This directly connects training to high-reward rollout coverage and improves Best-of-k at every inference budget without selecting one in advance.Source: §1 · p. 2

Implementation

  • TailRL uses a critic-free policy-gradient estimator that differs from standard RL only through its advantage calculation, enabling integration by swapping the advantage function.The method therefore remains compatible with existing reinforcement-learning pipelines.Source: §1 · p. 2

Finite-rollout estimator

  • A group of N rollouts yields an unbiased finite-rollout estimator whose objective interpolates from expected reward at N = 1 to the population objective as N →∞.Unlike REINFORCE, increasing the rollout budget changes the optimized objective rather than only reducing variance.Source: §1 · p. 2

Empirical results

  • 7.7× Best-of-1024 speedup on code optimization, while matching RLOO’s Pass@1024 with 128–256× fewer inference rollouts on GUI grounding.TailRL also matches supervised objectives on object localization and succeeds from 0.01% initial success on maze navigation where expected-reward baselines fail.Source: §1 · pp. 2–3

2 Preliminaries

The preliminaries define reinforcement learning as shaping the reward distribution induced by a policy, then relate upper-tail inference objectives to binary-success optimization. They establish the continuous-reward setting and connect MaxRL to rare-success weighting and Pass@k gradients.

2 Preliminaries

  • Critic-free policy-gradient methods estimate score-function gradients from independent rollouts, and TailRL retains this template while changing only advantage computation.The framework includes GRPO (Shao et al., 2024), RLOO, and related finite-rollout estimation methods.Source: §2 · p. 3

2.1 Inference-Time Selection

  • Best-of-k for continuous rewards and Pass@k for binary rewards improve with additional samples and expose upper-tail differences that mean reward can hide.At k = 1, both reduce to mean reward; as k approaches infinity, each approaches the maximum reward in its support.Source: §2.1 · p. 3

2 Preliminaries

  • A policy samples rollouts whose deterministic rewards induce a reward distribution, so training changes probability mass across reward values rather than only the mean.The setup primarily uses rewards r(x, z) ∈ [0, 1], with randomness arising from the policy; the outer average is over inputs.Source: §2.2 · p. 3, §2 · p. 3

2.2 Policy as a Generative Model of Rewards

  • Different policies can share the same mean while assigning different probability to high-reward outcomes, motivating objectives over the entire reward distribution.Continuous rewards can be viewed through threshold events, where each rollout contributes success to every threshold below its reward.Source: §2.2 · p. 3, Figure 2 · p. 4

2.3 MaxRL for Binary Rewards

  • For binary rewards, MaxRL (Tajwar et al., 2026) maximizes log success probability, weighting rare successes more and decomposing its gradient as a harmonic mixture of Pass@k gradients.Binary expected reward equals success probability, which fully determines the Bernoulli reward distribution.Source: §2.3 · p. 4

3 Tail-Likelihood Reinforcement Learning

TailRL optimizes the expected log-probability of clearing a uniformly sampled reward threshold, emphasizing difficult high-reward tail events across the full reward range. Its objective decomposes into harmonic Best-of-k signals, recovers MaxRL for binary rewards, and admits an independent quality-audit interpretation.

3 Tail-Likelihood Reinforcement Learning

  • TailRL maximizes the average log-probability of exceeding a uniformly sampled reward threshold, rather than aggregating tail probabilities arithmetically.The uniform threshold distribution covers the full reward support without a weighting hyperparameter.Source: §3 · p. 4, §3.3 · p. 6
  • Higher reward thresholds receive larger gradient weights because their tail probabilities are smaller.This makes difficult-to-reach, high-reward events more influential during optimization.Source: §3 · p. 4

3.1 Harmonic Decomposition over Best-of-k

  • TailRL combines Best-of-k learning signals with harmonic weights 1/k, avoiding the need to select a target inference budget in advance.The decomposition applies across all inference-time sampling budgets.Source: §3.1 · p. 5

3.2 Recovery of MaxRL for Binary Rewards

  • For binary rewards, TailRL exactly recovers MaxRL because Best-of-k becomes Pass@k and the harmonic decomposition becomes the harmonic Pass@k decomposition.TailRL therefore generalizes MaxRL from binary to continuous rewards.Source: §3.2 · p. 5

3.3 Probabilistic Interpretation of TailRL

  • TailRL preserves continuous reward information by evaluating a likelihood event at every threshold instead of treating all outcomes below one success cutoff identically.A single threshold can stop rewarding improvements after success and leave performance poor at higher reward levels.Source: §3.3 · p. 5
  • The independent quality-audit interpretation assigns separate rollouts to thresholds and passes only when every rollout clears its assigned threshold.Independence is necessary; reusing one rollout would collapse the nested events to the hardest threshold.Source: §3.3 · p. 5

4 Estimating the TailRL Gradient

Section 4 derives a finite-rollout approximation to TailRL and an unbiased policy-gradient estimator computable from sampled rewards. The rollout budget selects the approximation order, shifting learning from expected reward toward higher-order Best-of-k signals.

4.1 From Finite Rollouts to a Finite-Order Objective

  • A finite rollout budget N naturally defines an order-N truncation of the population TailRL objective and admits a simple unbiased policy-gradient estimator.At T = 1, the method recovers the standard expected-reward gradient; increasing T progressively emphasizes harder-to-reach reward levels.Source: §4 · p. 6, §4.1 · p. 6

4.2 Finite-Rollout Estimator

  • At each threshold, one unit of credit is divided among sampled rollouts exceeding it, so thresholds cleared by fewer rollouts receive greater weight.The weights are computed exactly after sorting the sampled rewards, and centering them enables use as a drop-in advantage replacement.Source: §4.2 · pp. 6–7
  • For N independent rollouts, TailRL provides an unbiased score-function estimator for the order-(N−1) truncated objective by changing only rollout weights.The estimator preserves the standard policy-gradient form and differs from critic-free methods only in converting sampled rewards into weights.Source: §4.2 · p. 7
  • One rollout recovers the expected-reward gradient, whereas larger groups incorporate progressively higher Best-of-k learning signals instead of merely reducing variance.This distinguishes TailRL from REINFORCE, whose larger rollout counts leave the expected-reward objective unchanged.Source: §4.2 · p. 7

5 Unifying Gradient Weight View

TailRL and expected reward maximization share a unified gradient-weight view: their objectives differ only in how they value each tail probability. Expected reward weights all tails equally, whereas TailRL applies inverse-tail-probability weighting and emphasizes rarely reached high thresholds.

Unified gradient-weight view

  • TailRL and expected reward maximization differ only in the gradient weight assigned to each tail probability.The derivative ϕ′(p) is the marginal value of making a tail event more likely, rather than a new objective.Source: §5 · p. 8

Expected reward maximization

  • Expected reward uses ϕ(p) = p and ϕ′(p) = 1, giving every tail probability equal weight regardless of how often it is reached.Table 1 summarizes this equal-weight behavior for standard reinforcement learning.Source: §5 · p. 8, Table 1 · p. 8

TailRL

  • TailRL uses ϕ(p) = log p and ϕ′(p) = 1/p, assigning greater weight to rarely reached higher reward thresholds.Because tail probability decreases as the reward threshold increases, inverse-probability weighting emphasizes high-reward tails.Source: §5 · p. 8, Table 1 · p. 8

Truncated family

  • Order-T TailRL interpolates between the objectives: its multiplier is 1−(1−p)^T / p, equals 1 at T = 1, and approaches 1/p as T →∞.Figure 3 shows Order-T TailRL approaching the population weight, while PKPO’s weight is capped at kopt and vanishes as p grows.Source: Figure 3 · p. 7, §5 · p. 8

6 Experiments

Across four settings, TailRL tests its population objective, rare high-reward learning, inference-time scaling, and resistance to moderate-reward shortcuts. It consistently supports retaining probability mass on rare, high-reward outcomes, from localization and maze navigation to GUI grounding and code optimization.

6 Experiments

  • The experiments evaluate four theory-driven questions using localization, Text-Maze, GUI grounding, and code optimization settings against GRPO, RLOO, and PKPO.They test population-objective estimation, rare high-reward learning, Best-of-k-aligned inference scaling, and resistance to moderate-reward displacement.Source: §6 · p. 8

6.1 ImageNet Object Localization

  • TailRL matches or exceeds supervised localization objectives, surpassing L1+GIoU on CorLoc@0.5 and CorLoc@0.75 with comparable mean IoU.Finite-rollout gradients and performance approach the population-level objective as N increases; at N = 16, TailRL exceeds GRPO and RLOO trained at N = 1024.Source: §6.1 · pp. 9–10, Figure 5 · p. 9, Figure 7 · p. 10

6.2 Text-Maze Navigation from Low-Success Initial Policies

  • TailRL’s advantage concentrates when shortest-path successes are attainable but rare, outperforming expected-reward baselines and PKPO at low initial success rates.RLOO, GRPO, and TailRL behave similarly when successes are frequent, but expected-reward methods fail reliably as initial success falls; TailRL upweights rare exceptional rollouts.Source: §6.2 · p. 11, Figure 9 · p. 11

6.3 GUI Grounding with Vision-Language Models

  • TailRL’s Pass@k keeps rising with additional GUI samples, reaching RLOO’s Pass@1024 with 8 rollouts at 3B and 4 at 7B, reductions of 128× and 256×.TailRL and RLOO have similar Pass@1, while GRPO is inferior and TailRL leaves more inputs with non-negligible success probability.Source: §6.3 · p. 12

6.4 Code Runtime Optimization

  • TailRL achieves a 7.7× mean Best-of-1024 speedup versus 0.98× for GRPO and 0.96× for RLOO, while continuing risky exploration instead of copying inputs.These matched-compute results are not converged endpoints; TailRL remains higher-entropy and raises mean reward to 2.92, nearly three times the copying value.Source: §6.4 · pp. 13–14, Figure 12 · p. 13

7 Related Work

TailRL differs from expected-reward, selected-budget, and risk-sensitive reinforcement-learning objectives by integrating log tail-probability across all reward thresholds. It directly reweights rollout groups without a learned critic and recovers MaxRL for binary rewards.

Objectives beyond expected reward

Coverage and tail-sensitive reinforcement learning

  • TailRL counters distribution narrowing and lost rare high-reward behavior by inversely weighting reward levels according to their rollout frequency, rather than adding a diversity regularizer.This addresses effects studied mechanistically and observed at large sampling budgets (Cui et al., 2025; Kirk et al., 2024).Source: §7 · p. 14
  • Unlike distributional and risk-sensitive reinforcement learning, TailRL uses no learned critic and integrates every reward threshold instead of fixing one risk level.Its policy-gradient weights are computed directly from rollout groups, avoiding risk levels that can overlook rare successes (Bellemare et al., 2017; Greenberg et al., 2022).Source: §7 · p. 14

8 Conclusion … C.3.5 Recovery of MaxRL on Binary Rewards

This section develops TailRL’s threshold-based objective and its connections to harmonic Best-of-k optimization, reward reparameterization, and binary-reward MaxRL/Pass@k. It also summarizes the supporting theoretical conditions and clarifies the scope of threshold-scale selection.

8 Conclusion

  • TailRL maximizes expected log-probability over uniformly sampled reward thresholds, recovers MaxRL for binary rewards, and improves learning from rare high-reward outcomes across four settings.It also benefits more from additional training and inference samples while avoiding suboptimal collapse.Source: §8 · p. 14

B Extended Related Work

  • TailRL integrates log tail-probabilities over every threshold, unlike related objectives that commit to one threshold, transform, or order statistic.Its order-T truncation is a harmonic combination of Best-of-k objectives and reduces exactly to MaxRL for binary rewards.Source: B Extended Related Work · p. 25
  • TailRL changes the training objective rather than rollout exploration or variance reduction, reweighting rare high-reward thresholds by inverse tail-probability without an added regularizer.This targets the distribution narrowing and mode-collapse failure associated with expected-reward training.Source: B Extended Related Work · pp. 24–25

C.1 Regularity of the TailRL Gradient

  • Under smooth-policy, finite-objective, and bounded-weighted-score assumptions, the population objective and finite truncations are differentiable and the required gradient, integral, and expectation exchanges are valid.The result applies to the score-function identity and the derivations used throughout Sections 4 and 4.2.Source: §C.1 · pp. 26–27

C.2 Derivation of the Rollout-Weight Forms

  • The TailRL gradient becomes a rollout-weight form by restricting each rollout’s threshold integral to thresholds below its reward, with the same construction extending to order-N truncations.Fubini’s theorem permits the threshold integral and rollout expectation to be exchanged under the regularity conditions.Source: §C.2 · p. 28

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

  • Finite TailRL objectives and gradients decompose harmonically over Best-of-k objectives and gradients, while the population decomposition follows by monotone and dominated convergence.Threshold weighting is additionally equivalent to rescaling the reward axis through a strictly increasing transformation.Source: §C.3.2 · p. 29, §C.3.3 · p. 30, §C.3.4 · p. 30

C.3.4 Threshold Weighting as Reward Reparameterization

  • Weighted TailRL on r is exactly uniform TailRL on the monotone-rescaled reward er = Fw(r).Choosing a threshold density therefore selects a monotone coordinate system for reward quality; nonuniform weighting may encode a preferred reward scale, but selecting or learning that scale is outside this work’s scope.Source: §C.3.4 · pp. 30–31

C.3.5 Recovery of MaxRL on Binary Rewards

  • On binary rewards, TailRL’s finite objective is the order-T Maclaurin truncation of MaxRL, and Best-of-k(θ; x) equals Pass@k(θ; x).For every nontrivial threshold, pθ(x, τ) = qθ(x), and the maximum of k binary rewards is one exactly when at least one rollout succeeds.Source: §C.3.5 · p. 31

C.4 Harmonic Best-of-k Expansion of the Tail-Likelihood … C.8 Estimator-Level Recovery of MaxRL on Binary Rewards

These sections establish TailRL’s harmonic Best-of-k decomposition, unbiased finite-rollout estimation, and closed-form implementation weights. They further show how mean-centering reduces truncation order and how the estimator exactly recovers MaxRL for binary rewards.

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

  • TailRL’s truncated objective is a harmonic sum of Best-of-k objectives, while the full tail-likelihood is the corresponding infinite series.Every truncation is an upper bound that tightens monotonically to the tail-likelihood.Source: §C.4 · pp. 31–32
  • The truncated TailRL gradient is a positively weighted combination of Best-of-k gradients, and its first member equals expected-reward reinforcement learning up to an additive constant.The coefficient on the Best-of-k gradient is 1/k, and all coefficients are positive.Source: §C.4 · p. 32

C.5 Unbiasedness of the finite rollout Estimator

  • The finite-rollout TailRL estimator is unbiased for the order-N truncated gradient under Assumptions 3 to 5.The proof handles threshold-dependent rollout gates with a denominator capped below at one, while preserving finite conditional score means.Source: §C.5 · pp. 32, 34
  • The estimator is MaxRL applied across every threshold on one shared rollout group, and exactly recovers MaxRL when binary rewards concentrate all mass at one threshold.At thresholds with at least one success it averages clearing-rollout scores; with no successes it returns zero.Source: §C.5 · p. 34

C.6 Closed-Form Weights and Algorithm Correctness

  • Closed-form empirical weights depend only on sorted reward gaps, satisfy a recurrence, and have total weight equal to the group’s largest reward.The weights are nonnegative and lie in [0, N r(N)], so the update scale is controlled by the best observed reward.Source: §C.6 · p. 35

C.7 Effect of the Mean-Centering Baseline

  • Mean-centering lowers the TailRL truncation order from N to N−1.The centered estimator subtracts a max-reward-weighted score sum corresponding to the Best-of-N gradient.Source: §C.7 · pp. 35–36

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

  • For binary rewards with M > 0 successes, successful rollouts receive uncentered weight 1/M and unsuccessful rollouts receive zero, yielding the MaxRL estimator.After mean-centering, successful weights are 1/M −1/N and unsuccessful weights are −1/N; when M = 0, all weights are zero.Source: §C.8 · p. 36

D TailRL on a General Reward Range

TailRL extends directly from unit-interval rewards to any bounded range by averaging log-tail probabilities over uniformly sampled thresholds. Affine reward transformations preserve the objective and leave the normalized finite-rollout algorithm unchanged.

D TailRL on a General Reward Range

  • For rewards r(x, z) ∈ [rmin, rmax], TailRL averages log pθ(x, τ) over thresholds τ ∈ [rmin, rmax) with uniform normalization.The normalization makes the objective invariant to the units used to measure reward.Source: D TailRL on a General Reward Range · p. 37
  • Rescaling rewards to ˜r := (r − rmin)/(rmax − rmin) makes the general-range objective equivalent to the unit-interval objective, so results carry over directly.Shifting or rescaling rewards only relabels thresholds.Source: D TailRL on a General Reward Range · p. 37
  • The normalized finite-rollout estimator operates on raw rewards from any bounded range without changing the algorithm.Affine rescaling multiplies all consecutive weights by rmax − rmin, and Eq. (118)'s normalization cancels that factor.Source: D TailRL on a General Reward Range · p. 37

E Connection to Ordinal Cross-Entropy … H.2 Computing the Population-Level Objective

The appendices establish TailRL’s exact connection to ordinal cross-entropy, distinguish its advantage weighting from GRPO and RLOO, and formalize Pass@k, Best-of-k, and ImageNet localization evaluation. They also provide an exact population-level TailRL objective for the finite box policy.

E Connection to Ordinal Cross-Entropy

  • The population TailRL objective is exactly ordinal cross-entropy at target r = 1, while the finite-rollout procedure estimates it and recovers it as N →∞.For binary rewards, this reduces to the MaxRL objective log qθ(x).Source: E Connection to Ordinal Cross-Entropy · pp. 37–38

F Advantage Functions of GRPO, RLOO, and TailRL

  • TailRL, GRPO, and RLOO share a critic-free N-rollout update and differ only in how rewards are mapped to advantages.TailRL’s inverse-tail weighting gives a reward threshold cleared by one of N rollouts N times the per-reward weight of a threshold cleared by all rollouts.Source: F Advantage Functions of GRPO, RLOO,… · p. 38

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

  • Pass@k measures binary success probability and Best-of-k measures the expected maximum continuous reward; both evaluate keeping the best of k samples and improve or remain unchanged with k.They are identical for binary rewards, and unbiased estimators use K > k evaluation rollouts.Source: G Pass@k and Best-of-k Empirical… · p. 38

G.1 Pass@k

  • The Pass@k estimator uses the number of successes among K rollouts and the probability that a uniformly random size-k subset avoids all successes.This yields an unbiased estimate of the probability that at least one sampled rollout succeeds.Source: §G.1 · p. 38

G.2 Best-of-k

  • The Best-of-k estimator sorts K rewards and weights each order statistic by its probability of being the maximum in a uniformly random size-k subset.A layer-cake formulation shows that Best-of-k reduces to Pass@k for binary rewards.Source: §G.2 · p. 39

H ImageNet Object Localization

  • ImageNet localization predicts bounding boxes rewarded by IoU, comparing TailRL rollout counts with supervised MSE, L1, GIoU, and L1+GIoU anchors using CorLoc@δ, mean IoU, and Best-of-1024 IoU.Training uses a pretrained ResNet-50, four 50-bin coordinate heads, 30 epochs, and three evaluation seeds.Source: H ImageNet Object Localization · p. 39

H.1 Supervised Anchor Losses

  • The supervised localization anchors make deterministic predictions without rollouts, so their greedy, mean, and Best-of-k outputs are identical.The combined L1+GIoU anchor uses DETR weights λL1 = 5 and λGIoU = 2.Source: §H.1 · p. 40

H.2 Computing the Population-Level Objective

  • For ImageNet localization, the population variant computes exact TailRL objectives and gradients over the finite categorical box policy, with no sampling error.The policy has four independent 50-bin heads, yielding 6,250,000 possible boxes; sorted reward values turn the threshold integral into a finite sum without additional discretization error.Source: §H.2 · p. 40

H.3 Additional Results … I.4 Task Representation and Prompt Template

Additional experiments show that TailRL improves with rollout budget, especially on difficult localization cases, and preserves performance across reward thresholds better than binarized-reward alternatives. The text-maze study defines a continuous shortest-path reward and evaluates training from checkpoints spanning very different initial success rates.

H.3 Additional Results

  • TailRL improves steadily with training rollout budget, whereas GRPO improves only slightly and RLOO does not improve; both baselines remain below TailRL’s smallest reported budget.At N = 1024, GRPO has the largest mean gradient norm and RLOO the smallest, but larger gradients do not explain final accuracy differences.Source: §H.3 · pp. 40–41, Figure 13 · p. 41
  • TailRL’s gap over the stronger expected-reward baseline widens from roughly 0.09 IoU on easy images to 0.18 on hard images, where TailRL reaches 0.49.Difficulty bands contain 19,628 easy, 19,977 medium, and 10,395 hard validation images; hard cases emphasize the rare high-reward rollouts targeted by TailRL.Source: §H.3 · p. 41, Figure 14 · p. 41

H.4 The Effect of Binarizing the Reward

  • At CorLoc@0.9, TailRL reaches approximately 0.39, versus 0.24 for the 0.75-threshold MaxRL and 0.02 for the 0.5-threshold variant.At CorLoc@0.5, all methods reach approximately 0.78, while at CorLoc@0.75 TailRL and the 0.75-threshold variant reach approximately 0.63 versus 0.30 for the 0.5-threshold variant.Source: §H.4 · p. 42, Figure 15 · p. 42
  • Binarized rewards specialize policies near their selected threshold, while TailRL uses the full continuous reward and continues improving at stricter evaluation thresholds.Once a rollout exceeds its threshold, binary reward no longer distinguishes barely acceptable from nearly perfect outcomes, and additional rollouts cannot recover that lost ordering.Source: §H.4 · pp. 41–42

I Text-Maze Navigation

  • Text-maze navigation uses 17 × 17 mazes and a continuous reward combining formatting, goal progress, and path efficiency, with reward 1 for shortest-path success.The policy is a 3M-parameter decoder-only transformer trained from scratch and evaluated on shortest-path rate.Source: I Text-Maze Navigation · p. 42

I.2 Post-Training Configuration

  • Post-training starts from seven checkpoints with held-out shortest-path rates from 0.012% to 0.83%, using 5,000 steps, N = 16 rollouts, 256 mazes, and three seeds.The configuration also specifies evaluation sampling, while the reported rate estimates single-rollout success from 64 rollouts on each of 256 held-out mazes.Source: I Text-Maze Navigation · p. 42, §I.2 · p. 43, Table 4 · p. 43

I.1 Dataset and Pretraining

  • Pretraining selects up to 16 goal-reaching paths per maze across solution-quality intervals, retaining diverse lengths and spatial routes through next-token prediction.Candidate paths are constrained to length below ub = 60, with at most four paths of each length retained before quality-based selection.Source: §I.1 · pp. 42–43

I.3 Reward Function

  • The maze prompt serializes grid tokens without English or pretrained language priors, and the reward combines partial progress with path-length efficiency, scoring only shortest-path completion as 1.Outputs continue after PATH_START as movement tokens ending in DONE; malformed rollouts and wall collisions receive zero reward.Source: §I.3 · p. 43, §I.4 · pp. 43–44

I.5 Additional Results … J.6 Evaluation Protocol

TailRL improves inference-time scaling by retaining high-reward rollouts, especially when training receives enough samples to discover them. The GUI-grounding evaluation uses a fixed on-policy pipeline, dense coordinate reward, and matched sampling-based comparisons across methods.

I.5 Additional Results

  • TailRL’s Pass@k and Best-of-k reward improve more rapidly than GRPO and RLOO as inference rollouts increase, revealing differences understated by k = 1.TailRL assigns greater probability to high-reward rollouts, making them more likely to be discovered as k grows.Source: §I.5 · p. 44, Figure 16 · p. 44
  • With an initial shortest-path success rate of 0.024%, TailRL’s Pass@k and Best-of-k reward increase sharply from N = 4 to N = 16, whereas expected-reward baselines gain little.At N = 16, rare high-reward rollouts occur frequently enough for TailRL to learn; increasing inference samples cannot rescue failed training.Source: §I.5 · p. 44, Figure 17 · p. 45
  • TailRL retains substantially more entropy and steadily lengthens generated paths during training, while expected-reward baselines lose entropy early and stop changing their rollout distributions.The shared dynamics indicate that exploration toward distant goals requires both sustained entropy and increasing path lengths.Source: §I.5 · p. 45, Figure 18 · p. 45

J.4 Prompt Template

  • Both model scales use the same measured-and-frozen image-first prompt requesting only a parseable absolute pixel coordinate, without a tool-call wrapper or chain of thought.The prompt was selected using greedy accuracy and sampling format compliance.Source: §J.1 · p. 46, §J.4 · pp. 46–47

J.2 Reward

  • The dense SE-GUI reward combines target-box inclusion, distance-based partial credit normalized by dmax, and a 0.5 format-parsing bonus, with parsing applied identically across methods.The implementation follows released SE-GUI code and was verified against reference code on 500 randomized examples.Source: §J.2 · p. 46

J.3 Training Protocol

  • Training is fully on-policy with one update per batch, 8 prompts, 8 rollouts per prompt, no KL regularization, and a shared 26,448-step horizon.Models use bfloat16, gradient checkpointing, a trainable vision tower, maximum gradient norm 100, and one seed per method.Source: §J.3 · p. 46, setup · p. 46

J.6 Evaluation Protocol

  • Evaluation covers all 1,581 ScreenSpot-Pro items using greedy accuracy and fixed 4,096-sample temperature-0.6 Pass@k and Best-of-k protocols, with bootstrap confidence intervals and paired item-wise comparisons.Absolute values are not directly comparable with published results because those use a different tool-call format; comparisons therefore remain within the shared pipeline.Source: §J.6 · p. 47, §J.5 · p. 47

J.7 Additional Results … K.6 Additional Results

Additional results show that TailRL’s inference-scaling advantage persists across GUI task categories and throughout training, while code optimization demonstrates how reward design and rollout-distribution coverage distinguish TailRL from copying-based solutions. The code experiments evaluate correctness-preserving runtime improvements under controlled training and held-out Best-of-k analysis.

J.7 Additional Results

  • At k = 128, TailRL leads the better baseline in eleven of twelve ScreenSpot-Pro scale-category cells, by up to 12.0 points at 3B and 11.5 points at 7B.At k = 1, the three post-trained methods remain close; OS at 7B is a statistical tie under item-bootstrap intervals.Source: §J.7 · p. 47, Figure 19 · p. 48, Figure 20 · p. 48
  • TailRL separates from both baselines within the first epoch at every inference budget above k = 1 and maintains that separation across training checkpoints.The result holds for both Pass@k and Best-of-k evaluations rather than only the final checkpoint.Source: §J.7 · p. 47, Figure 21 · p. 49, Figure 22 · p. 49

K Code runtime optimization

  • The code task uses PIE pairs of correct slow C++ programs and faster human rewrites, requiring the policy to produce a faster program with identical outputs.The source program is provided as input, and the output must be a single fenced C++ block.Source: K Code runtime optimization · pp. 47–48

K.1 Reward

  • A code rollout receives zero reward unless it compiles and passes every test, after which reward is its speedup measured with deterministic gem5 execution time.The reward is unbounded above, while copying the input safely earns exactly 1 and forms a suboptimal shortcut.Source: §K.1 · pp. 49–50

K.2 Dataset Construction

  • The PIE corpus is filtered for compilability, test reliability, valid timing cases, and remaining program pairs before train, validation, and test splits are created.The fastest valid human rewrite is stored as an oracle reference for each source program.Source: §K.2 · pp. 50–51

K.3 Model and Training

  • All code methods use the same model, data order, optimizer, schedule, prompt, and reward, differing only in their advantage estimator under fully on-policy training without KL regularization.Batches contain 64 programs with 16 rollouts per program, and repeated rewrites are compiled only once per training step.Source: §K.3 · p. 51, Table 6 · p. 51

K.5 Reported Quantities

  • Training reports rollout-level reward, correctness, entropy, and held-out Best-of-1024 evaluation, with curves averaged over three runs per objective.The prompt is minimal: it asks for an equivalent faster C++ program and requires the final answer under an exact marker as one code block.Source: §K.5 · p. 51, §K.4 · p. 51, §K.6 · p. 51

K.6 Additional Results

  • In code optimization, TailRL’s Best-of-k speedup mass centers near 5× at k = 1 and shifts rightward with larger budgets, unlike GRPO and RLOO, which remain pinned at the copy line.The pretrained model’s density rises from below 1× toward 2× but does not reach TailRL’s region.Source: §K.6 · pp. 51–52, Figure 27 · p. 52

K.7 Sample Generations

On held-out problem p02318, TailRL’s best of 64 rollouts produced a genuine optimized rewrite with 27.0× verified speedup, while the pretrained model reached 5.05× and GRPO/RLOO reproduced the input verbatim.

Sample Generations

  • The example uses a held-out dynamic-programming edit-distance problem, with each policy’s complete reasoning trace and code selected by verified speedup among 64 rollouts.The prompt was shown exactly as received by the models.Source: §K.7 · p. 53
  • GRPO and RLOO reproduced the input program byte for byte inside their code blocks, unlike TailRL’s rewritten solution.The identity claims refer to raw rollouts; displayed code was syntax-highlighted and lightly normalized for typesetting.Source: §K.7 · p. 53
  • 27.0× verified speedup: TailRL’s best rollout from 64 samples was a genuine rewrite, versus 5.05× for the pretrained model.All post-trained policies were evaluated at step 300 after one training epoch on held-out problem p02318.Source: §K.7 · pp. 53, 55

Related papers

Loading 2609.02987v1…