VinePPO: Accurate Credit Assignment in RL for LLM Mathematical Reasoning

Authors: amirhossein  kazemnejad
milad  aghajohari
eva  portelance
alessandro  sordoni
siva  reddy
aaron  courville
nicolas  le roux
microsoft  research
Venue: NeurIPS_cc_2024_Workshop_MATH-AI
Published: 2024-09-25 22:18:09

Abstract: Large language models (LLMs) are increasingly required to solve complex reasoning tasks, like mathematical problems, that involve multiple reasoning steps before feedback is received. Effectively identifying and prioritizing key steps by accurately assigning credit to these intermediate steps is essential for enhancing model performance. Proximal Policy Optimization (PPO), a state-of-the-art reinforcement learning algorithm for finetuning LLMs, addresses the credit assignment problem by employing value networks to predict the expected cumulative rewards of intermediate states. In this work, we identify significant limitations with this value estimation method. To address this, we propose \methodname that leverages the flexibility of language environments to compute unbiased Monte Carlo-based estimates of the intermediate values. VinePPO consistently outperforms standard PPO,
doing so more efficiently and with lower divergence from the reference model. Our findings underscore the critical importance of accurate credit assignment in LLM post-training and present a simple, yet effective solution.

Main paper: 
 introduction: 
 Large language models (LLMs) are increasingly employed in tasks requiring complex reasoning, such as solving mathematical problems (Trinh et al., 2024; OpenAI, 2024) . In these settings, LLMs often engage in extended reasoning chains and perform numerous actions. Prioritizing steps that lead to correct solutions while downplaying erroneous ones during finetuning is essential for improving the performance and reducing unnecessary updates. This is particularly important as most reasoning steps generated by a model often do not impact its likelihood of solving the problem (Fig. 2 ). This issue is known as the credit assignment problem in reinforcement learning (RL, Sutton and Barto 1998) . Proximal Policy Optimization (PPO) (Schulman et al., 2017; Ouyang et al., 2022) , the state-of-the-art algorithm for RL tuning of LLMs (Xu et al., 2024; Ivison et al., 2024; Shao et al., 2024) , is a variant of actor-critic methods that utilizes a value network (critic) to handle credit assignment (Bai et al., 2022 (Bai et al., , 2023;; Havrilla et al., 2024) . The value network is a separate model (the same size as and initialized from a pretrained checkpoint of the LLM) that learns to estimate expected cumulative future reward (value) of intermediate actions during training. PPO then uses the predicted values to measure the advantage of each action and update the model accordingly. For example, in Fig. 2 , an ideal value network would assign a low value to s 0 , where the model initially struggles, and a higher value to s 2 and beyond, where a critical action led to solving the problem.Accurately predicting rewards from a partial and incomplete response requires the value network to grasp the space of correct solutions and predict the model's future behavior -both of which are 1.0 This is pure imaginary if and only if the real part is 0, i.e. s41.0 2a + 7b = 0. s51.0 Then a = -7 2 b, so a b = -7 2 .x . . .y t-1 y t . . . τ ′ 1 τ ′ 2 . . . τ ′ K VMC(st) = 1/K k R(τ k )Figure 2 : (Left) A response generated by the model. The notation p(correct|s :t ) represents the estimated probability of successfully solving the problem at step t, based on nine model rollouts. In this example, only step s 2 is critical; after this, the model completes the solution correctly. (Right) Illustration of estimating the value of a state within the trajectory.challenging. There are hints in the literature that standard PPO implementations for LLM finetuning have inaccurate value estimations. Ahmadian et al. (2024) and Luong et al. (2024) demonstrate that value networks often serve best as just a baseline in policy gradient2 . Shao et al. (2024) shows that the value network can be replaced by averaging rewards of a group of responses to a given problem, without degradation in performance.As estimation errors can significantly hamper model convergence and performance (Sutton et al., 1999; Greensmith et al., 2001) , it is crucial to ask: how accurately do value networks perform in practice during LLM finetuning? While recent studies (Hwang et al., 2024; Setlur et al., 2024) have begun to highlight the importance of identifying early reasoning errors and incorporating these as training signals in "RL-free" approaches (Rafailov et al., 2023) , to what extend the accuracy of credit assignment plays a role in RL tuning of LLMs remains an open question.In this work, we evaluate the standard PPO pipeline in mathematical reasoning tasks across various model sizes and find that value networks consistently provide inaccurate estimates and a sub-optimal training signal for finetuning. To address this, we propose VinePPO. Instead of relying on value networks, VinePPO computes unbiased estimates by resetting the environment to intermediate states and performing independent Monte Carlo (MC) rollouts to calculate the average return of individual steps. This approach takes advantage of a special property of the language environment-the ability to easily reset to any intermediate state of a trajectory (Schulman et al., 2015) . Not only does it removes the need for large, memory-intensive value networks, VinePPO also outperforms standard PPO and other baselines such as RestEM (Singh et al., 2023) (Fig. 1 ). VinePPO is also able to match PPO's final accuracy in fewer iterations, requiring less wall-clock time (Fig. 4 ), and achieving a lower KL divergence (Fig. G .3) from the base model. These findings highlight the importance of accurate credit assignment in RL post-training and position VinePPO as an effective alternative to value networks. 
advantage estimation with monte carlo: 
 We build on PPO (Schulman et al., 2017; Ouyang et al., 2022) , for which we provide an extensive background in Appendices B and I. VinePPO only modifies the way advantages are estimated. We start by estimating the true value function V (s t ). Instead of relying on a value network, for any intermediate state s t , we sample K independent trajectories starting from s t . The average return across these trajectories serves as the value estimate:EQUATIONwhere τ k is an independent continuation sampled from the model, starting from s t and R(•) is the return over the completed trajectory. This is an MC estimate of the value functionV (s t ) = E [R(τ ) | s 0 = s t ].Once the values VMC (s t ) are computed, we compute the advantages with:EQUATIONwhere r(•) is the step-wise reward (in practice, equal to zero unless at final step). Note that for any K ≥ 1, the policy gradient computed using the advantage estimator ÂMC is an unbiased estimate of the gradient of expected return.In essence, VinePPO only alters advantage computation in PPO pipeline, leaving the rest unchanged. With this simple modification, we eliminate the need for a value network, significantly reducing memory footprint (up to 112GB for a 7B LLM) while providing unbiased estimates of advantages.The parameter K offers a trade-off between computational cost (i.e. more MC samples per state) and the variance of the estimator. To enhance the efficiency of ÂMC , we also group states within a reasoning step and compute a single advantage, which is then assigned to all tokens in that step. Since everything else in the PPO pipeline of VinePPO is unchanged, by comparing the two methods, we can systematically evaluate of the impact of accurate credit assignment in RL tuning of LLMs. 
experiments: 
 We use two strong base LLMs pretrained for mathematical reasoning: (1) DeepSeekMath 7B (Shao et al., 2024) and (2) RhoMath 1.1B (Lin et al., 2024) . Our focus is the MATH dataset (Hendrycks et al., 2021) , which contains competition-level problems. We compare three LLM reasoning finetuning strategies, PPO, VinePPO , and RestEM to the supervised finetuned model (SFT) baseline, from which all methods are initialized. We tune PPO hyperparameters like KL penalty coefficient, batch size, and GAE λ, applying best practices in PPO optimization. VinePPO uses the same hyperparameters as PPO but modifies the advantage estimation A(s t , a t ) to isolate the effect of accurate credit assignment.We sample K = 9 trajectories in VMC . For RestEM, we closely follow the original setup while ensuring consistency in training conditions for a fair comparison. We choose the best checkpoint based on a held-out validation set for all experiments3 . 
results and analysis: 
 Task Performance As shown in Fig. 1 Computational efficiency VinePPO and standard PPO need different kinds of resources. The value network needs to be trained and alongisde its optimizer consuming more GPU memory. In contrast, MC rollouts need fast inferences and as a result VinePPO is generally slower per iteration compared to PPO. In our setup, RhoMath 1.1B and DeepSeekMath 7B are 5x and 2x slower per iteration when using VinePPO . However, as shown in Fig. 4 , the impact of accurate credit assignment with VinePPO is substantial. VinePPO reaches the final accuracy of PPO in fewer iterations and less time. Specifically, RhoMath 1.1B and DeepSeekMath 7B achieve PPO's final test accuracy 3.7× and 2.3× faster in wall-clock time, and in 20× and 5× fewer gradient steps, respectively.5 Value Prediction Accuracy To analyze the accuracy of value prediction, we compute the ground truth value of each state by taking 256 MC samples. We compare value network (from PPO) predictions against VinePPO's. As shown in Fig. 3 , VinePPO and PPO produce errors of very different types. VinePPO estimates are unbiased, with variance peaking at 0.5 and dropping to zero at 0 and 1. In contrast, the value network's estimates exhibit high bias. See Appendix H for full details. 
related work: 
 Credit Assignment in Post-Training of LLM PPO (Schulman et al., 2017) , as applied in Reinforcement Learning from Human Feedback (RLHF, Ouyang et al. 2022) , was among the pioneering approaches for RL finetuning of LLMs. While effective, PPO is known for its computational overhead and sensitivity to hyperparameters. As a result, subsequent approaches have sought to simplify or bypass PPO without sacrificing performance. For example, RL-free methods such as DPO (Rafailov et al., 2023) and its newer variants (Azar et al., 2023; Ethayarajh et al., 2024) operate in a bandit setting, where the entire response is treated as a single action, without distinguishing intermediate states. Similarly, methods based on rejection sampling, like RestEM (Singh et al., 2023) , finetune the model on full high-reward responses. In the realm of PPO simplifications, methods like RLOO (Ahmadian et al., 2024) and GRPO (Shao et al., 2024) abandon the value network of PPO. They sample a group of M responses per each prompt and compute the average reward (of other M -1 responses) as a policy gradient baseline for all tokens in the group, effectively treating the entire response as a single action. Recent works, however, have started to emphasize the importance of finer credit assignment. Work such as Hwang et al. (2024) and Setlur et al. (2024) introduce Monte Carlo-based mechanisms that detect key errors in reasoning chains and apply use them negative sample in DPO. Unlike these approaches, which rely on ad-hoc heuristics, our work fully embraces RL training pipeline and addresses the core issue of inaccurate value estimation in PPO to unlock its full potential. In parallel, there has been interest (Hosseini et al., 2024; Lightman et al., 2023a) in building better verifiers and reward models that can provide per-step feedback. Although these methods often require costly human annotation, recent efforts (Ma et al., 2023; Uesato et al., 2022; Luo et al., 2024; Wang et al., 2023) have automated data collection using MC rollouts. VinePPO is orthogonal to these approaches, as it operates within PPO-based training, optimizing a given task's reward rather than designing new reward models. Our method can further benefit from improvements in reward modeling as they emerge.Value Estimation in RL and Monte Carlo Tree Search Deep RL algorithms are categorized into value-based and policy-based methods. Value-based algorithms, such as DQN and its successors (Mnih et al., 2013; Wang et al., 2015) , train a neural network to predict values and derive the policy from the learned value function. Policy-based methods, including A2C, A3C (Mnih et al., 2016) , SAC (Haarnoja et al., 2018) , and PPO (Schulman et al., 2017) , train a policy directly and use value estimates only to guide the policy updates. Typically, these methods rely on critic networks for value prediction. An exception is a variant of TRPO (Schulman et al., 2015) , known as the "Vine" variant, where state value estimation is performed using MC samples. However, the authors note that the Vine variant is limited to environments that allow easy resets to any state, which is uncommon in most RL settings as the focus is on black-box engines or real-world deployment. In contrast to common RL environments, language generation, allows for easy resets to any intermediate state, presenting unique opportunities for RL tunning of LLM. In fact, when easy resets were available in RL (e.g., Go, Chess), strong MC-based methods like AlphaGo (Silver et al., 2016) and AlphaZero (Silver et al., 2017) have emerged. AlphaGo trains a policy using expert moves data and self-play, alongside a value network to predict the win probability from a given state. Then during the inference, it applies a tree search guided by MC rollouts and the value network to find the best possible moves. AlphaZero advances this approach by distilling MCTS outcomes into its policy, removing the need for expert data. Recent works have adapted AlphaZero's principles and lessons to LLM, using similar search techniques during inference to improve responses and during training to find better trajectories for distillation (Xie et al., 2024; Chen et al., 2024; Feng et al., 2023; Zhang et al., 2024; Hao et al., 2023) . While this is a promising direction, VinePPO is not an MCTS method; it rather utilizes MC samples solely for value estimation and only during PPO training to improving credit assignment. In fact, inference-time search like MCTS can be layered on top of VinePPO to further enhance performance. 
conclusion: 
 Credit assignment is a weak spot for current RL finetuning of LLMs. While value networks are tasked and trained to estimate these values, they perform poorly. VinePPO simply replaces the value networks with MC samples. We found that it reaches higher accuracy faster supporting the significant impact that accurate credit assignment has on RL finetuning of LLMs for reasoning. We hope our work encourages researchers to look into the details of RL finetuning pipelines of LLMs and to explore more computationally practical methods for accurate credit assignment. 
 
 Appendix: In this work, we focused on complex mathematical reasoning tasks, which provide a clear testbed for evaluating the impact of accurate credit assignment. While VinePPO is a general-purpose modification to PPO for LLM finetuning, its performance on more general human alignment tasks remains unclear.It is plausible that the performance gap between VinePPO and PPO would be less pronounced on tasks where the value network can generalize more easily. For example, in tasks like detecting toxicity in partial responses, the value network may perform well, reducing the advantage VinePPO offers.We focus on the RL tuning phase in the RLHF pipeline, following Ziegler et al. (2019a); Ouyang et al. (2022) ; Shao et al. (2024) . In this section, we provide an overview of actor-critic finetuning as implemented in PPO.In this setup, the policy π θ represents a language model that generates a response y = [y 0 , . . . , y T -1 ] autoregressively given an input x = [x 0 , . . . , x M -1 ], such that π θ (y|x) =T -1 t=0 π θ (y t |x; y <t ). The goal of RL finetuning is to maximize the expected undiscounted (γ = 1) finite-horizon return, while incorporating a KL-divergence constraint to regularize the policy and prevent it from deviating too far from a reference policy π 0 (typically the initial supervised finetuned (SFT) model). The objective can be written as:EQUATIONwhere D is the dataset of prompts, R(x; y) is the complete sequence-level reward function, and β controls the strength of the KL penalty. Note that the policy π θ is initialized from π 0 .Language Environment as an MDP The language generation is typically modeled as a token-level Markov Decision Process (MDP) in an actor-critic setting, where each response y is an episode. Specifically, the state at time step t, s t ∈ S, is the concatenation of the input prompt and the tokens generated up to that point: s t = x; y <t = [x 0 , . . . , x M -1 , y 0 , . . . , y t-1 ]. At each time step, the action a t corresponds to generating the next token y t from fixed vocabulary. The process begins with the initial state s 0 = x, and after each action, the environment transitions to the next state, s t+1 = s t ; [a t ], by appending the action a t to the current state s t . In this case, since states are always constructed by concatenating tokens, the environment dynamics are known and the transition function is deterministic, i.e., P (s t+1 |s t , a t ) = 1. During the generation process, the reward r t is set to zero for all intermediate actions a t 's, with the sequence-level reward R(x; y) only applied at the final step when the model stops generating. A trajectory τ = (s 0 , a 0 , s 1 , a 1 , . . . ) is therefore a sequence of state-action pairs, starting from the input prompt until the terminal state. Finally, we define the cumulative return of a trajectory τ as R(τ) = T -1 t=0 r t = R(s T ) = R(x; y).Policy Gradient Given this MDP formulation, policy gradient methods like PPO maximize Eq. 3 by repeatedly sampling trajectories and taking a step in the direction of the gradient g pg := ∇ θ J(θ) to update the parameters. Policy gradient g pg takes the following form:g pg = E τ ∼π θ T -1 t=0 ∇ θ log π θ (a t |s t )A(s t , a t ), where s t = x; y <t , a t = y t , (4) τ = (s 0 , a 0 , . . .), and A(s t , a t ) is the advantage function. The gradient g pg points towards increasing the probability π θ (a t | s t ) when A(s t , a t ) > 0 and the opposite when A(s t , a t ) < 0. Intuitively, the advantage function A(s t , a t ) quantifies how much better taking action a t at state s t is compared to the average action taken in that state under the policy. Formally, it is defined as:EQUATIONwhere Q(s t , a t ) is the state-action value and V (s t ) is the per-state value function 6 . The value function, V (s t ) : S → R, offers a long-term assessment of how desirable a particular state is under the current policy. Formally, it represents the expected cumulative reward obtained from starting in state s t and following the policy thereafter7 :V (s t ) = E τ ∼π θ [R(τ ) | s 0 = s t ]. PPO uses the same advantage-weighted policy gradient as in Eq. 4, but constrains policy updates through clipping to ensure stable training. For full details, see Appendix I.Estimating the Advantage via Value Networks In practice, the advantage function A(s t , a t ) is not known a priori and commonly estimated by first using a value network Vϕ to approximate the true value function V (s t ) and then plugging the learned values into Eq. 5 or other variants such as GAE (Schulman et al., 2016) . The value network is parameterized by ϕ and trained alongside the policy network π θ . The training objective for the value network minimizes the mean squared error between the predicted value and the empirical return:EQUATIONwhereG t = T -1 t ′ =t r t ′is the empirical return from state s t . PPO uses the same objective for Vϕ but enhances stability by applying clipping during training (see Appendix I.1 for details). In RL-tuning of LLMs, the value network is often initialized using the initial policy π 0 (or the reward model when available), with the language modeling head swapped out for a scalar output head to predict values (Zheng et al., 2023) . This setup leverages the prior knowledge of the pretrained model for value estimation.As outlined in Appendix B, a step in the PPO gradient update (Eq. 4) aims to increase the probability of better-than-average actions while decreasing the probability of those that perform worse-a process quantified by advantage function A(s t , a t ). However, the true advantage function is generally unknown and must be estimated, typically by substituting estimates from a value network into Eq. 5. As we will elaborate in Appendix H, neural networks are imperfect function approximators and can result in biased value estimates. Fortunately, the language environment offers a useful property that allows for deriving an unbiased estimator of value function V (s t ). In this section, we first describe this property and then explain how VinePPO leverages it to enhance credit assignment.The language environment, as defined in Appendix B, possesses a unique property not commonly found in traditional RL settings: the ability to reset to any point within a trajectory. Since states are simply concatenated tokens, we can prompt the language model π θ to generate continuations from any intermediate state. This flexibility allows us to explore alternative future paths from arbitrary points in a generation. In contrast, standard RL typically collect training data through sequential rollouts, a process reflected in the design of the Gym (Towers et al., 2024) , the de facto RL environment API. Gym environments provide two primary functions: (1) env.reset(), which resets the environment to its initial state, and (2) env.step(action), which advances the environment based on the agent's action. There is no mechanism for resetting to an arbitrary intermediate state within a trajectory. This design suits classic RL, where the focus is on black-box game engines or real-world deployment. Moreover, recent advancements in LLM inference engines (Kwon et al., 2023; Zheng et al., 2024) have dramatically increased the speed of on-the-fly response generation-for example, an LLM with 7B parameters can generate up to 5,000 tokens per second on a single GPU8 . This computational efficiency makes it feasible to conduct fast environment simulation, opening up unique opportunities for RL training of LLMs.Datasets and Pretrained LLMs We conduct our experiments using strong LLMs specifically pretrained for mathematical reasoning: (1) DeepSeekMath 7B (Shao et al., 2024) and (2) RhoMath 1.1B (Lin et al., 2024) , both of which have been trained on diverse mathematical and natural language corpora. Having models from different sizes allows for evaluating the effect of scaling. We focus on mathematical reasoning datasets MATH (Hendrycks et al., 2021) , which consists of competitionlevel mathematical problems and present a range of difficulty levels that allow for comprehensive evaluation of reasoning abilities. To ensure our setup is reproducible, we only make use of publicly available data and checkpoints on Huggingface. For each dataset, we finetune the base LLMs on their respective training sets to obtain the initial SFT models (π 0 ). In all experiments, we employ full-parameter finetuning to allow utilization of models' full capacity (Biderman et al., 2024; Sun et al., 2023) .Evaluation We evaluate model performance on the test sets of each dataset, using accuracy (Pass@1) as our primary metric, which measures the correctness of the final answers produced by the models. As our baseline, we adopt the standard PPO framework, as commonly implemented for LLM finetuning (Ouyang et al., 2022; Touvron et al., 2023; Huang et al., 2024) . Additionally, we compare our proposed method against RestEM (Singh et al., 2023) , which applies Expert Iteration, a form of Iterative Rejection Finetuning (Yuan et al., 2023; Anthony et al., 2017) with measures to prevent overfitting. All methods are initialized from the same SFT checkpoint π 0 to ensure a fair comparison.To ensure standard PPO (and its value network) has a healthy training and our evaluation reflects its full potential, we first focus our hyperparameter search on PPO parameters (such as KL penalty coefficient, batch size, minibatch size, GAE λ, number of epochs per iteration) and apply all well-known techniques and best practices (Huang et al., 2024; Ivison et al., 2024) in PPO tuning (Refer to Appendix J.2 for the full list). VinePPO borrows the exact same hyperparameters from PPO and only modifies the advantage A(s t , a t ) estimation, keeping the rest of the pipeline unchanged. This allows us to isolate the effect of accurate credit assignment. We found that sampling K = 9 trajectories in VMC performs well; the effect of varying K is fully analyzed in Fig. 4 . For the other baseline, we closely follow the original setup while ensuring consistency in training conditions for a fair comparison. We choose the best checkpoint based on a held-out validation set for all experiments. Full implementation details, including all hyperparameters and training procedures, are provided in Appendix J.5. Sampling temperature is a critical hyperparameter that controls the randomness of trajectories generated by the model. At higher temperatures, the model generates more diverse trajectories, encouraging exploration that can accelerate training, especially during the early stages. However, increased diversity in the trajectories also presents a challenge: the value network in PPO must generalize over a wider range of states, complicating value estimation. To evaluate the effect of temperature on performance, we compared VinePPO and PPO runs using different temperatures T ∈ {0.6, 0.8, 1.0} over 360 training steps, analysed their training dynamics. As shown in Fig. F .2, VinePPO consistently benefits from higher temperatures, achieving faster convergence and higher accuracy. In contrast, PPO not only fails to benefit from increased temperature, but also diverges when the temperature is set to its highest value, T = 1.0, where the trajectories are most diverse.These findings raise concerns about the scalability of PPO, particularly in real-world scenarios involving large and diverse datasets, in contrast to VinePPO which maintains robust value estimation regardless of the diversity in the trajectories.Both PPO and VinePPO estimate values as means to credit assignment, one employing a value network and the other using MC samples. More accurate value estimates lead to more precise advantage computations, resulting in more effective policy updates. As shown in Section 4, VinePPO consistently outperforms PPO. In this section, we explore the underlying reasons for this performance gap by closely analyzing the value prediction of both methods. To assess the accuracy of value predictions, we first establish a "ground truth" value for each state within trajectories, denoted as V * (s t ), by running multiple MC rollouts (256 in our case) and averaging the returns. This provides a low-variance reference value. We then compare the value predictions in both methods against this ground truth on the DeepSeekMath 7B and MATH datasets. Step: 60Step: 360Step: 540Step A trajectory τ = (s 0 , a 0 , s 1 , a 1 , . . . ) thus represents a sequence of state-action pairs that begins at the input prompt and continues until reaching the terminal state. Finally, the cumulative return of a trajectory τ is defined as R(τ ) =T -1 t=0 r t = r T -1 = R(x; y). The goal of RL tuning is to maximize the expected return of the model's responses to prompts in the dataset, as defined by the reward function R (Eq. 3). PPO, similar to other policy gradient methods, achieves this goal by repeatedly sampling trajectories for a batch of prompt sampled from D and taking multiple optimization steps in the direction of the gradient g ppo to update the parameters. PPO gradient g ppo is defined as the gradient of the following loss:EQUATIONwhere π θ k is the policy at the previous iteration, ϵ is the clipping parameter, β is the KL penalty coefficient, A θ k t = A θ k (s t , a t ) is the advantage estimate for policy π θ k , and the clip(θ) function is:EQUATIONNote that the KL penalty could be also added to the reward function R. We follow the more recent implementations (Shao et al., 2024; Qwen, 2024) , where it is added to the loss function. The KL term can be computed using the following unbiased estimator (Schulman, 2020) :EQUATION)where π 0 denotes the reference model (initial SFT).In addition to the policy π θ , PPO also trains a separate value network Vϕ to obtain an estimate the true values V (s t ) of states s t . Parameterized by ϕ, the value network is trained alongside the policy network π θ using the following loss:L ValNet (ϕ) = 1 2 E τ ∼π θ 1 T T -1 t=0 max Vϕ (s t ) -G t 2 , clip(ϕ) -G t 2 (11)where Vϕ k is the value network at the previous iteration, G t =T -1 t ′ =t γ t ′ -t r t ′ is the empirical return from state s t , ϵ ′ is a value clipping parameter, and the clip(θ) is defined as:EQUATION)In RL-tuning of LLMs, the value network is typically initialized from the initial policy π 0 (or the reward model, if available), replacing the language modeling head with a scalar output head to predict values (Zheng et al., 2023) This approach takes advantage of the base model's prior knowledge for value estimation.Advantage Estimation Once the estimated values Vϕ (s t ) are obtained, the advantages A(s t , a t ) are computed using the GAE (Schulman et al., 2016) :EQUATIONwhere δ t = r t + γ Vϕ (s t+1 ) -Vϕ (s t ) is the temporal difference error, λ is the GAE parameter, and γ is the discount factor. Also, we have:EQUATIONAdjusting the GAE parameter λ allows for a trade-off between bias and variance in the advantage estimates. However, as we discuss in Appendix J.5, we found that λ = 1 works best in our experiments (similar to the findings of Luong et al. (2024) and Ahmadian et al. (2024) ). In this case, the GAE simplifies to the following form (assuming γ = 1): ÂGAE (s t , a t ) =T -1 t ′ =t r t ′ -Vϕ (s t ).We focus on mathematical reasoning datasets that require step-by-step solutions and are widely used to evaluate the reasoning capabilities of LLMs. Below is a brief overview of the datasets used in our experiments:MATH (Hendrycks et al., 2021) The MATH dataset contains problems from high school math competitions, covering a wide range of topics such as algebra, geometry, and probability. • Advantage Normalization: After calculating the advantages, we normalize them to have zero mean and unit variance, not only across the batch but also across data parallel ranks. This normalization step is applied consistently in both our PPO and VinePPO implementations. • Reward Normalization: We follow Ivison et al. (2024) and do not normalize the rewards, as the reward structure in our task is already well-defined within the range of [0, 1]. Specifically, correct responses are assigned a reward of 1, while incorrect responses receive 0. • End-of-Sequence (EOS) Trick: As detailed in Appendix I, rewards are only applied at the final token of a response, which corresponds to the EOS token when the response is complete. For responses that exceed the maximum length, we truncate the response to the maximum length and apply the reward to the last token of the truncated sequence. We also experimented with penalizing truncated responses by assigning a negative reward (-1), but this did not lead to performance improvements. • Dropout Disabling: During the RL tuning phase, we disable dropout across all models.This ensures that the log probabilities remain consistent between different forward passes, thereby avoiding stochastic effects that could hurt training stability. • Fixed KL Coefficient We use a constant coefficient for the KL penalty. Although the original PPO implementation for finetining language models (Ziegler et al., 2019b) utilized an adaptive KL controller, more recent implementations typically do not use this approach (Ouyang et al., 2022; Touvron et al., 2023; Xu et al., 2024) .To ensure a systematic and reproducible evaluation, we create our SFT models π ref by finetuning the base pretrained LLMs (as opposed to their "Instruct" version) on the training splits of the respective datasets. Specifically, we produce two distinct SFT models: two base LLM (DeepSeekMath 7B and RhoMath 1.1B ) across MATH. The base models are finetuned using the Adam optimizer without weight decay. We employ a learning rate warm-up over 6% of the total training steps. Each model is trained for three epochs with a batch size of 64, and the best checkpoint is selected based on validation accuracy. For each SFT model, we conduct a hyperparameter sweep over learning rates in the range {1 × 10 -7 , 3 × 10 -7 , 1 × 10 -6 , 3 × 10 -6 , 1 × 10 -5 , 3 × 10 -5 , 8 × 10 -5 , 1 × 10 -4 } to ensure optimal performance. We then use these SFT models as the initial checkpoint for training the methods mentioned in our paper.We evaluate each method's performance on the test sets of each dataset. For example, when we report that PPO achieves 42.8% accuracy on the MATH dataset for the DeepSeekMath 7B model, this means the PPO training was initialized with the SFT model specific to DeepSeekMath 7B on the MATH dataset, and accuracy was measured on the MATH test set. Our primary evaluation metric is accuracy, specifically Pass@1, which reflects the percentage of correct responses on the first attempt. This metric is crucial because it represents a realistic user interaction, where the model is expected to deliver a correct answer without the need for multiple tries. For each evaluation, we sample a response from the model for a given prompt, using a maximum token length of 1024 and a temperature of 0.35. A response is considered correct if its final answer matches the ground truth final answer, as detailed in Appendix J.1. Furthermore, each accuracy score is averaged over 16 evaluation rounds, each conducted with different random seeds. This will ensure a robust and low variance assessment of model performance.In this section, we present a comprehensive overview of the hyperparameters used in our experiments.PPO Finetuning LLMs using PPO is known to be sensitive to hyperparameter selection, and finding the optimal settings is critical for achieving strong performance. To ensure the robustness of our study, we explored hyperparameter values reported in recent studies (Shao et al., 2024; Zheng et al., 2023; Ivison et al., 2024; Huang et al., 2024) and conducted various sweeps across a wide range of values to identify the best configuration for our tasks and models. The full set of hyperparameters, along with their respective search spaces, is detailed in Table 1 .setting GAE,(Schulman et al., 2016) parameter λ to 1.Refer to Appendix D for full details.The full definition is in Appendix B.Note that this is despite the fact that all of hyperparameter searches were tuned for PPO.Such derivation is possible as the language environment is deterministic.We drop the dependency on π θ for brevity.Nvidia A100 GPU with model loaded in 16bit precision. 


Decision: The paper identifies a weakness of PPO and proposes an effective alternative that can be generally applied.

Reviews: review: title: title: Smart observation
main_review: main_review: This paper presents a highly insightful observation. While Proximal Policy Optimization (PPO) often struggles with accurately estimating intermediate state values, the proposed method cleverly capitalizes on a unique feature of the language environment—the ability to easily reset to any intermediate state in a trajectory. By leveraging this property, the authors utilize Monte Carlo rollouts to estimate these values more effectively.

Pros:

The use of Monte Carlo rollouts to estimate intermediate state values is both innovative and well-suited to the characteristics of the language environment. This novel approach addresses a key limitation of PPO, demonstrating creative problem-solving.

The proposed method demonstrates a significant improvement over the baseline, showcasing its effectiveness in addressing the problem at hand.

Cons:

The explanation of Figure 3 is unclear, making it difficult to interpret its significance. I recommend providing additional context or clarification to help readers better understand its role in supporting the paper’s claims.

The paper lacks comparisons with other existing methods, which makes it difficult to evaluate how the proposed approach performs relative to the broader state of the art.
title: title: Official Review of Submission76 by Reviewer 863D
main_review: main_review: **Overall**:

This paper introduces a novel approach for credit assignment in large language models (LLMs) using a modified version of PPO, named VinePPO. The authors highlight an issue with potentially high bias when using classical PPO for credit assignment in LLM reasoning and propose leveraging Monte Carlo-based value estimates instead of a value network for more accurate value estimation, leading to improved performance.  

The paper is generally well-written, with clearly articulated points and promising simulation results. However, providing a deeper explanation of the underlying mechanisms driving the improved performance of VinePPO would enhance the reader's understanding. Specifically, elaborating on why the classical PPO lead to high bias, and the theoretical or empirical justifications for why it leads to better credit assignment by using VinePPO, would offer clearer insights into the advantages of this approach.

**Strength**:

The paper presents a clear motivation and offers a neat approach to addressing inaccuracies in credit assignment for LLM reasoning. The writing is clear and easy to follow, with a well-structured presentation. The extensive simulation studies are thorough, and the hyper-parameter tuning process is well-explained, contributing to a solid overall contribution.

**Weakness**:
1. While the results are promising, the use of Monte Carlo for unbiased estimation is a well-established concept in the context of reinforcement learning (RL) and has been widely applied. This might moderate the originality of the paper.

2. The explanation of why VinePPO outperforms classical PPO remains somewhat unclear. Expanding on the rationale behind its superiority, as touched upon briefly in Lines 512-520, would improve the reader's understanding. A more detailed elaboration on the theoretical and empirical aspects of this improvement would be beneficial in the main paper.


**Questions**:

1. The results presented in the paper are quite promising. However, does VinePPO consistently outperform PPO only in the specific context of LLM reasoning, or does this advantage extend to other tasks, such as general language modeling or even non-language environments? It would be interesting to hear the authors' thoughts and speculations regarding its generalizability.

3. In terms of the tradeoff between accuracy and computational complexity introduced by VinePPO, would it be possible to combine PPO and VinePPO depending on the training stages? Monte Carlo sampling might offer more stable value estimates early in training, where VinePPO could be most effective. Later, when the training process stabilizes, switching to classical PPO could reduce computational overhead. I wonder how the authors feel about this potential hybrid approach, and if there’s any comparison between the accuracy of PPO and VinePPO with respect to the number of training iterations.

**Minor issue**: 
1. While this may be a matter of terminology, it could be somewhat misleading to describe classical PPO as "biased" in Line 420. As the algorithm's recursion size increases, PPO provides consistent estimates of the value function under proper conditions. It may be more appropriate to state that "VinePPO" yields more accurate value function estimates compared to classical PPO.
title: title: This paper considers the credit assignment problem of RL fine tuning in LLMs. It proposes a new algorithm based on proximal policy gradient to address the limitations of current method and provides empirical numerical experiments to show its performance.
main_review: main_review: Summary:
This paper addresses one crucial problem in LLM with reinforcement learning fine tuning, the credit assignment problem. Based on Proximal Policy Optimization (PPO), the author proposed a new method VinePPO based on Monte Carlo rollouts instead of value networks. By numerical experiments, the author showed that VinePPO overwhelms standard PPO in math task datasets with respect to accuracy and concentration.

Strengths: 

1. The empirical analysis of the algorithm are in-depth with detailed illustration. The paper is well-written and to some degree self-contained.

2. The difference between PPO and VinePPO is only using MC instead of value networks, yet the adjusted algorithm could deal with credit assignment issue.

Weaknesses:

1. Lack of theoretical insights of intuitive explanation (see questions below) about the algorithm or about existing principles regarding what procedure would be suitable for credit assignment. I believe with such math intuition, the paper will be more convincing.

2. I suggest the author providing more comparison between the proposed algorithm and other fine tuning strategies, which could make the paper more convincing.

Questions: I’m not an expert in LLM empirical study and fine-tuning so please forgive me if my questions are naive.

1. May one ask if you have any theoretical intuition about why value network provides inaccurate estimation in credit assignment?

2. Are there any math intuition about why MC algorithm performs much better apart from empirical illustration? In other words, what's your intuition about choosing this fine-tuning strategy?

3. Apart from math tasks, could your algorithm be applied to other kinds of tasks which need fine tuning? Thanks!
title: title: review
main_review: main_review: The paper proposes VinePPO, which replaces the value network of PPO with the Monte-Carlo estimation of the value function.

Pros:
 - The paper is well-motivated: during PPO training of the language models, there are signs that the value network cannot provide accurate estimate of the value functions. The authors also carry out experiments to justify the claim.
 - The authors show positive improvements of the proposed VinePPO algorithm to the original PPO algorithm on math reasoning datasets with two models (RhoMath 1.1B & DeepSeekMath 7B).

Cons:
 - The proposed method seems to be a universal method that can also extend to general alignment scenarios. The paper will benefit from more experiments on general alignment tasks (e.g. consider testing on AlpacaEval). However, it will be hard to naturally partition the language model's generation into states of multiple tokens. This seems to limit the proposed algorithm to reasoning tasks and models with output format of explicit steps. (The authors already mentioned this limitation in Appendix B.)
 - The paper will benefit from comparing with other baseline policy optimization algorithms without a value network, e.g., the GRPO algorithm (Shao et al. 2024) that the authors claimed to have motivated their work.