Tail-Likelihood Reinforcement Learning
Abstract Overview
This paper proposes Tail-Likelihood Reinforcement Learning (TailRL), an RL objective for continuous rewards that maximizes the expected log-probability of exceeding a uniformly sampled reward threshold. The method reframes a continuous reward as a family of binary tail events and emphasizes reward levels that are rarely reached, rather than optimizing only mean reward. The paper shows that TailRL decomposes into a harmonic mixture of Best-of-k gradients and reduces exactly to MaxRL in the binary-reward case. It also derives an unbiased finite-rollout estimator that changes only the rollout weighting or advantage computation, making the method compatible with standard critic-free RL pipelines. Empirically, the authors evaluate TailRL on object localization, text-maze navigation, GUI grounding, and code runtime optimization.
Novelty
The main novelty is an RL objective that integrates log tail probabilities over all reward thresholds, providing a continuous-reward analogue of likelihood-based success optimization. A distinctive theoretical result is the exact harmonic decomposition into Best-of-k gradients, which ties training directly to inference-time sampling performance without requiring the selection of a single target k.
Results
Across four tasks, TailRL consistently improves coverage of high-reward outcomes relative to expected-reward baselines such as GRPO and RLOO. Demonstrated results include matching or exceeding supervised localization objectives, learning from maze policies with approximately 0.01% initial shortest-path success where expected-reward baselines fail, matching RLOO's Pass@1024 in GUI grounding with 128x to 256x fewer inference rollouts, and achieving a 7.7x Best-of-1024 speedup in code optimization while GRPO and RLOO collapse to copying the input.
Key Points
- TailRL optimizes the log-likelihood of exceeding reward thresholds, up-weighting rare high-reward rollouts instead of treating all tail probabilities equally.
- The method provides an unbiased finite-rollout estimator that only modifies rollout weights or advantages, where larger rollout groups correspond to optimizing higher-order truncations of the TailRL objective rather than merely reducing variance.
- Empirical evaluations show TailRL is especially effective when strong outcomes are attainable but rare, preventing policy collapse onto safe suboptimal shortcuts and improving scaling with inference compute.