Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problems

• URL: http://arxiv.org/abs/2505.15201v1
• Date: Wed, 21 May 2025 07:26:36 GMT
• Title: Pass@K Policy Optimization: Solving Harder Reinforcement Learning Problems
• Authors: Christian Walder, Deep Karkhanis,
• Abstract summary: Reinforcement Learning (RL) algorithms sample multiple n>1 solution attempts for each problem and reward them independently.<n>This prioritizes the strength of isolated samples at the expense of the diversity and collective utility of sets of samples.<n>We propose Pass-at-k Policy Optimization (PKPO), a transformation on the final rewards which leads to direct optimization of pass@k performance.
• Score: 6.873119751136341
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Reinforcement Learning (RL) algorithms sample multiple n>1 solution attempts for each problem and reward them independently. This optimizes for pass@1 performance and prioritizes the strength of isolated samples at the expense of the diversity and collective utility of sets of samples. This under-utilizes the sampling capacity, limiting exploration and eventual improvement on harder examples. As a fix, we propose Pass-at-k Policy Optimization (PKPO), a transformation on the final rewards which leads to direct optimization of pass@k performance, thus optimizing for sets of samples that maximize reward when considered jointly. Our contribution is to derive novel low variance unbiased estimators for pass@k and its gradient, in both the binary and continuous reward settings. We show optimization with our estimators reduces to standard RL with rewards that have been jointly transformed by a stable and efficient transformation function. While previous efforts are restricted to k=n, ours is the first to enable robust optimization of pass@k for any arbitrary k <= n. Moreover, instead of trading off pass@1 performance for pass@k gains, our method allows annealing k during training, optimizing both metrics and often achieving strong pass@1 numbers alongside significant pass@k gains. We validate our reward transformations on toy experiments, which reveal the variance reducing properties of our formulations. We also include real-world examples using the open-source LLM, GEMMA-2. We find that our transformation effectively optimizes for the target k. Furthermore, higher k values enable solving more and harder problems, while annealing k boosts both the pass@1 and pass@k . Crucially, for challenging task sets where conventional pass@1 optimization stalls, our pass@k approach unblocks learning, likely due to better exploration by prioritizing joint utility over the utility of individual samples.

Related papers

• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• Make Optimization Once and for All with Fine-grained Guidance [78.14885351827232]
  Learning to Optimize (L2O) enhances optimization efficiency with integrated neural networks.<n>L2O paradigms achieve great outcomes, e.g., refitting, generating unseen solutions iteratively or directly.<n>Our analyses explore general framework for learning optimization, called Diff-L2O, focusing on augmenting solutions from a wider view.
  arXiv  Detail & Related papers  (2025-03-14T14:48:12Z)
• SeWA: Selective Weight Average via Probabilistic Masking [51.015724517293236]
  We show that only a few points are needed to achieve better and faster convergence.<n>We transform the discrete selection problem into a continuous subset optimization framework.<n>We derive the SeWA's stability bounds, which are sharper than that under both convex image checkpoints.
  arXiv  Detail & Related papers  (2025-02-14T12:35:21Z)
• Adaptive Preference Scaling for Reinforcement Learning with Human Feedback [103.36048042664768]
  Reinforcement learning from human feedback (RLHF) is a prevalent approach to align AI systems with human values. We propose a novel adaptive preference loss, underpinned by distributionally robust optimization (DRO) Our method is versatile and can be readily adapted to various preference optimization frameworks.
  arXiv  Detail & Related papers  (2024-06-04T20:33:22Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences.<n>To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model.<n>Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• Overcoming Reward Overoptimization via Adversarial Policy Optimization with Lightweight Uncertainty Estimation [46.61909578101735]
  Adversarial Policy Optimization (AdvPO) is a novel solution to the pervasive issue of reward over-optimization in Reinforcement Learning from Human Feedback. In this paper, we introduce a lightweight way to quantify uncertainties in rewards, relying solely on the last layer embeddings of the reward model.
  arXiv  Detail & Related papers  (2024-03-08T09:20:12Z)
• Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
  We address the problem of semi-bandits, where a player selects among P actions from the power set of a set containing d base items. We show that our approach efficiently leverages the semi-bandit feedback and outperforms bandit feedback approaches.
  arXiv  Detail & Related papers  (2024-02-23T08:07:54Z)
• Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variance [37.646655530394604]
  Federated Learning (FL) is a distributed learning paradigm to train a global model across multiple devices without collecting local data. We present the first adaptive client sampler, K-Vib, employing an independent sampling procedure. K-Vib achieves a linear speed-up on the regret bound $tildemathcalObig(Nfrac13Tfrac23/Kfrac43big)$ within a set communication budget.
  arXiv  Detail & Related papers  (2023-10-04T10:08:01Z)
• Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization [42.92248233465095]
  We propose a simple but effective method, called symmetric replay training (SRT), which can be easily integrated into various Deep reinforcement learning (DRL) methods. Our method leverages high-reward samples to encourage exploration of symmetric regions without additional online interactions - free. Experimental results demonstrate the consistent improvement of our method in sample efficiency across diverse DRL methods applied to real-world tasks.
  arXiv  Detail & Related papers  (2023-06-02T05:34:01Z)
• Sample Dropout: A Simple yet Effective Variance Reduction Technique in Deep Policy Optimization [18.627233013208834]
  We show that the use of importance sampling could introduce high variance in the objective estimate. We propose a technique called sample dropout to bound the estimation variance by dropping out samples when their ratio deviation is too high.
  arXiv  Detail & Related papers  (2023-02-05T04:44:35Z)
• Optimizer Amalgamation [124.33523126363728]
  We are motivated to study a new problem named Amalgamation: how can we best combine a pool of "teacher" amalgamations into a single "student" that can have stronger problem-specific performance? First, we define three differentiable mechanisms to amalgamate a pool of analyticals by gradient descent. In order to reduce variance of the process, we also explore methods to stabilize the process by perturbing the target.
  arXiv  Detail & Related papers  (2022-03-12T16:07:57Z)
• Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback [31.826205004616227]
  Client sampling plays an important role in federated learning (FL) systems as it affects the convergence rate of optimization algorithms.<n>We propose an online mirror descent (OSMD) algorithm designed to minimize the sampling variance.<n>We show how our sampling method can improve the convergence speed of federated optimization algorithms over the widely used uniform sampling.
  arXiv  Detail & Related papers  (2021-12-28T23:50:52Z)
• The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization [0.0]
  We prove that Nesterov's extrapolation has the strength to make the individual convergence of gradient descent methods optimal for nonsmooth problems. We give an extension of the derived algorithms to solve regularized learning tasks with nonsmooth losses in settings. Our method is applicable as an efficient tool for solving large-scale $l$1-regularized hinge-loss learning problems.
  arXiv  Detail & Related papers  (2020-06-08T03:35:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.