Reinforcement Learning with Verifiable Rewards: GRPO's Effective Loss, Dynamics, and Success Amplification

• URL: http://arxiv.org/abs/2503.06639v2
• Date: Fri, 14 Mar 2025 15:25:46 GMT
• Title: Reinforcement Learning with Verifiable Rewards: GRPO's Effective Loss, Dynamics, and Success Amplification
• Authors: Youssef Mroueh,
• Abstract summary: Group Relative Policy Optimization was introduced and used successfully to train DeepSeek R1 models.<n>We show in this paper that GRPO with verifiable rewards can be written as a Kullback Leibler ($mathsfKL$) regularized contrastive loss.
• Score: 19.315342870604113
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Group Relative Policy Optimization (GRPO) was introduced and used successfully to train DeepSeek R1 models for promoting reasoning capabilities of LLMs using verifiable or binary rewards. We show in this paper that GRPO with verifiable rewards can be written as a Kullback Leibler ($\mathsf{KL}$) regularized contrastive loss, where the contrastive samples are synthetic data sampled from the old policy. The optimal GRPO policy $\pi_{n}$ can be expressed explicitly in terms of the binary reward, as well as the first and second order statistics of the old policy ($\pi_{n-1}$) and the reference policy $\pi_0$. Iterating this scheme, we obtain a sequence of policies $\pi_{n}$ for which we can quantify the probability of success $p_n$. We show that the probability of success of the policy satisfies a recurrence that converges to a fixed point of a function that depends on the initial probability of success $p_0$ and the regularization parameter $\beta$ of the $\mathsf{KL}$ regularizer. We show that the fixed point $p^*$ is guaranteed to be larger than $p_0$, thereby demonstrating that GRPO effectively amplifies the probability of success of the policy.

Related papers

• $Q\sharp$: Provably Optimal Distributional RL for LLM Post-Training [60.01594991938747]
  $Qsharp$ is a value-based algorithm for KL-regularized RL that guides the reference policy using the optimal regularized $Q$ function.<n>Our results highlight $Qsharp$ as an effective approach for post-training LLMs, offering both improved performance and theoretical guarantees.
  arXiv  Detail & Related papers  (2025-02-27T21:43:00Z)
• Distributionally Robust Policy Learning under Concept Drifts [33.44768994272614]
  This paper studies a more nuanced problem -- robust policy learning under the concept drift.<n>We first provide a doubly-robust estimator for evaluating the worst-case average reward of a given policy.<n>We then propose a learning algorithm that outputs the policy maximizing the estimated policy value within a given policy class.
  arXiv  Detail & Related papers  (2024-12-18T19:53:56Z)
• Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation [48.92318828548911]
  We present LoRa-PI (Low-Rank Policy Iteration), a model-free learning algorithm alternating between policy improvement and policy evaluation steps. LoRa-PI learns an $varepsilon$-optimal policy using $widetildeO(S+Aover mathrmpoly (1-gamma)varepsilon2)$ samples where $S$ denotes the number of states (resp. actions) and $gamma$ the discount factor.
  arXiv  Detail & Related papers  (2024-10-30T20:22:17Z)
• Information Theoretic Guarantees For Policy Alignment In Large Language Models [19.315342870604113]
  We show that the $sqrtmathsfKL$ information theoretic upper bound holds if the reward under the reference policy has sub-gaussian tails. We also prove for the best of $n$ policy, that the $mathsfKL$ upper bound can be obtained for any $f$-divergence.
  arXiv  Detail & Related papers  (2024-06-09T18:41:50Z)
• Theoretical guarantees on the best-of-n alignment policy [110.21094183592358]
  We show that the KL divergence between the best-of-$n$ policy and the reference policy is an upper bound on the actual KL divergence.<n>We also propose a new estimator for the KL divergence and empirically show that it provides a tight approximation.<n>We conclude with analyzing the tradeoffs between win rate and KL divergence of the best-of-$n$ alignment policy.
  arXiv  Detail & Related papers  (2024-01-03T18:39:13Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  In many bandit problems, the maximal reward achievable by a policy is often unknown in advance. We consider the problem of estimating the optimal policy value in the sublinear data regime before the optimal policy is even learnable. We present a more practical, computationally efficient algorithm that estimates a problem-dependent upper bound on $V*$.
  arXiv  Detail & Related papers  (2023-02-19T01:09:24Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs) Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
  arXiv  Detail & Related papers  (2022-10-05T22:52:00Z)
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation [92.99933928528797]
  We study the model-based reward-free reinforcement learning with linear function approximation for episodic Markov decision processes (MDPs) In the planning phase, the agent is given a specific reward function and uses samples collected from the exploration phase to learn a good policy. We show that to obtain an $epsilon$-optimal policy for arbitrary reward function, UCRL-RFE needs to sample at most $tilde O(H4d(H + d)epsilon-2)$ episodes.
  arXiv  Detail & Related papers  (2021-10-12T23:03:58Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  In high stake applications, active experimentation may be considered too risky and thus data are often collected passively. While in simple cases, such as in bandits, passive and active data collection are similarly effective, the price of passive sampling can be much higher when collecting data from a system with controlled states.
  arXiv  Detail & Related papers  (2021-06-18T07:54:23Z)
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method [38.34416337932712]
  Policy gives rise to a rich class of reinforcement learning (RL) methods, for example the REINFORCE. Yet the best known sample complexity result for such methods to find an $epsilon$-optimal policy is $mathcalO(epsilon-3)$, which is suboptimal. We study the fundamental convergence properties and sample efficiency of first-order policy optimization method.
  arXiv  Detail & Related papers  (2021-02-17T07:06:19Z)
• Robust Policy Gradient against Strong Data Corruption [30.910088777897045]
  We study the problem of robust reinforcement learning under adversarial corruption on both rewards and transitions. Our attack model assumes an textitadaptive adversary who can arbitrarily corrupt the reward and transition at every step within an episode. We develop a Filtered Policy Gradient algorithm that can tolerate even reward corruption and can find an $O(epsilon1/4)$-optimal policy.
  arXiv  Detail & Related papers  (2021-02-11T01:48:38Z)

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.