RRO: LLM Agent Optimization Through Rising Reward Trajectories
Authors: Zilong Wang
Jingfeng Yang
Sreyashi Nag
Samarth Varshney
Xianfeng Tang
Haoming Jiang
Jingbo Shang
Sheikh Muhammad Sarwar
Venue: COLM 2025 (2025)
Keywords: large language model
agent
reinforcement learning
process reward model
TL;DR: A new "Reward Rising Optimization" method trains AI agents more efficiently by only collecting data when rewards increase between steps.

Abstract: Large language models (LLMs) have exhibited extraordinary performance in a variety of tasks, while it remains challenging for them to solve complex multi-step tasks as agents. In practice, agents are sensitive to the outcome of certain key steps, which makes them likely to fail the task because of a subtle mistake in the planning trajectory. Recent approaches resort to calibrating the reasoning process through reinforcement learning. They reward or penalize every reasoning step with process supervision, known as Process Reward Models (PRMs). However, PRMs are difficult and costly to scale up with a large number of next action candidates since they require extensive computations to acquire the training data through per-step trajectory exploration. To mitigate this issue, we focus on the relative reward trend across successive reasoning steps and propose maintaining an increasing reward in the collected trajectories for process supervision, which we term Reward Rising Optimization (RRO). Specifically, we incrementally augment the process supervision until we identify a step exhibiting positive reward differentials, i.e., rising rewards, relative to its preceding iteration. This method dynamically expands the search space for the next action candidates, efficiently capturing high-quality data. We provide mathematical groundings and empirical results on the WebShop and InterCode-SQL benchmarks, showing that our proposed RRO method achieves superior performance while requiring much less exploration cost.

Published as a conference paper at COLM 2025
RRO: LLM Agent Optimization Through Rising Reward Trajectories
Zilong Wang' Jingfeng Yang² Sreyashi Nag²
Samarth Varshney²
Xianfeng Tang" Haoming Jiang² Jingbo Shang' Sheikh Muhammad Sarwar
Universityy of California, San Diego Amazon
{z {zlwang, jshang))ucsd.edd smsarwarrQamazon.cco
Abstract
Large language models (LLMs) have exhibited extraordinary performance in variety of tasks while it remains challenging for them to solve complex multi-step tasks as agents. In practice, agents are sensitive to the outcome of certain key steps which makes them likely to fail the task because of a subtle mistake in the planning trajectory. Recent approaches resort to calibrating the reasoning process through reinforcement learning. They reward or penalize every reasoning step with process supervision, known as Process Reward Models (PRMs). However, PRMs are difficult and costly to scale up with large number of next action candidates since they require extensive computations to acquire the training data through per-step trajec- tory exploration. To mitigate this issue, focus the relative reward trend across successive reasoning steps and propose maintaining an increasing reward in the collected trajectories for process supervision, which we term Reward Rising Optinization (RRO). Specifically, we incrementally augment the process supervision until we identify a step exhibiting positive reward differentials, i.e. rising rewards, relative to its preceding iteration. This method dynamically expands the search space for the next action candi- dates, efficiently capturing high-quality data. We provide mathematical groundings and empirical results on the WebShop and InterCode-SQU benchmarks, showing that our proposed RRO method achieves superior performance while requiring much less exploration cost.
1 Introduction
Large language models (LLMs) have achieved remarkable advancements in numerous domains, ranging from natural language understanding to code generation (Brown et al., 2020; Kojima et al., 2022; Wei et al., 2022; Chen et al., 2023b; Zhou et al., 2023; Zhong al., 2024). Their ability to process and generate human-like text has significantly expanded their utility in real-world applications. However, solving complex multistep tasks that require reasoning and decision-making capabilities continue to pose substantial challenges for these models (Lightman et al., 2024; Wang et al., 2024b; Song al., 2024). This limitation has led researchers to explore novel methodologies to enhance the reasoning abilities of LLMs, particularly the context of agentic tasks requiring temporal sequential decision-making based on the environment feedback (Song et al., 2024; Xiong et al., 2024).
Recent efforts have introduced the reinforcement learning framework into the agent training process. They leverage Process Reward Models (PRMs) to evaluate and guide every reason- ing step (Wang et al., 2024c; Luo et al., 2024; Xiong et al., 2024). PRMs utilize reinforcement signals from each step to encourage effective reasoning trajectories while penalizing subop- timal steps, thereby enhancing probhemmmmrmmmmmaeeoo.o problem-solving Despite their promise, the scalability of PRMs remains tricky problem. Acquiring training data for these models often relies on the next action exploration for every reasoning step, which is computationally expensive and time-intensive (Wang et al., 2024b; Xiong al., 2024; Luo et al., 2024). Such requirements

---

Published as a conference paper at COLM 2025
(a) Direct Preference Optimization
(b) Process Reward Estimation
a Trujectory Prefix Average the outcome rewards
at
Ot
Optimiee the LLM with DPO Loss.
O L.M
a+++1
*1
Trojectory Rollouts
Step-level Preference Data
DPO with Process Rewards
(PRM a.)
(c) Next Action Exploration for DPO Data
Fixed-stzed Exploration Space (Baselines)
Dynamic Exploration Space (RRO)
Procers Reward
Case Over-explored
Case 2: Under-oxplorod
Case Scale up to the exploration until finding the action with the rising reward
ag
condidates
K candidates
(1)
1: Stop Atadex
(1) 0.5
a++1
a
ft [0.8]
Of
a
ar
[0.1]
Action with lowest reward
a
1.0
(3)
(K)
a1+1
(2
(FC)
..*
a [0.9]
...
Action with the risinn reward compared preceding action
11.0
Figure 1: Reward Rising Optimization: We dynamically adjust the scope of the next action exploration and prioritize action steps that exhibit "rising reward trend" compared to their predecessors, avoiding the over-exploration or under-exploration. (a) The illustration of Direct Preference Optimization (Rafailov al., 2024) where pair of the preference data is used to optimize the LLM agent. (b) The process reward estimation used in RRO where the average outcome reward set of rollouts serves as the process reward of an intermediate step. (c) The comparison of different strategies in the next action exploration stage where our RRO achieves a balance between the computation and data quality.
limit the feasibility of deploying PRMs scale, particularly in scenarios requiring extensive exploration of decision paths.
In this paper, we address these challenges by re-thinking the process supervision paradigm. Rather than uniformly expanding data collection efforts for every step, we propose a novel approach, Reward Rising Optimization (RRO), that prioritizes actions exhibiting "rising reward" trend compared to their predecessors, as shown in Figure 1. By focusing on the relative reward tendencies of neighboring reasoning steps, our method dynamically adjusts the scope of candidate action exploration to efficiently identify high-quality data points. This strategy significantly reduces the computational burden in terms of the number of action candidates that need to be explored, while preserving the ability to capture critical decision maaiing patterns, enabling scalable process supervision for LLMs.
We provide theoretical foundations to support our approach, demonstrating the feasibility of exploring the action candidate with the rising rewards. Additionally, we conduct compre- hensive empirical evaluations automated agent benchmarks, WebShop (Yao et al., 2022) and InterCode-SQL. (Yang et al., 2023). The results highlight the efficacy of our method in improving task performance while maintaining computational efficiency. By redefining the data collection paradigm for process supervision, our work paves the way for scalable and effective reinforcement learning frameworks in enhancing the reasoning capabilities of LLMs. We summarize our contribution as follows,
We propose Reward Rising Optimization (RRO), scalable process supervision framework that prioritizes reasoning steps with rising reward trends, reducing the burden of extensive data collection.
2

---

Published as a conference paper at COLM 2025
The proposed dynamic expansion strategy for sampling next action candidates i
efficiently identifies and captures high-quality data for training.
We provide theoretical insights and empirical evidence demonstrating the feasibility of the dynamic expansion strategy and the improved performance and computa- tional efficiency of RRO, on diverse benchmarks, InterCode-SQU and WebShop.
2 Preliminary
Task Formulation Automated agents play crucial role in real-world applications. The overall paradigm can be formulated as a partially observable Markov decision process (POMDP) defined by the elements S, O, T, R). Here, we denote the instruction space as U, the state space as S, the action space as A, the observation space as O, the transition function as T S A + S, and the reward function as R S A - [0, 1]. Since we investigate automated agents powered by LLMs in this paper, A, are represented in the form of natural language. Formally, given a task description serving policy model Te, generates the next action E A and observes the execution result E O, iteratively. The whole trajectory follows the ReAct style (Yao et al., 2023) and can be formulated as aj ~ (P((-11 (1,,,,, (1, 01, ..., 0;-1) E A, and the last action By serves as the final outcome from the agent. The interaction loop between the agent and the execution environment repeats until the task completes or exceeds the maximum iteration limit.
U, the LLM-based agent,
01, 02-11, fn), where is the number of steps,
Outcome Supervision The outcome reward model (ORM) rewards or penalizes the policy model based on the final outcome of a trajectory, which is formulated as FORM (u, e [0, where is the task description and is the generated trajectory. This outcome supervision evaluates the ultimate success of the agent in accomplishing the specified task rather than focusing on intermediate steps. The normalized reward range [0, 1] provides standardized measure of task completion quality, with higher values indicating more successful outcomes. Unlike process-level rewards that provide feedback on individual actions, outcome supervision captures the holistic performance of the entire action sequence, enabling the model to learn task completion strategies that may involve different valid approaches to reach the same successful outcome.
Process Supervision To further enhance the capability of LLM-based agents, process supervision has been proposed to capture the fine-grained rewards for each action in the trajectory (Lightman et al., 2023; Xiong et al., 2024), also known as the process reward model (PRM). Unlike outcome supervision that evaluates only the final result, process supervision provides feedback on individual actions, enabling more precise guidance throughout the decision-making sequence. Formally, we denote a prefix of trajectory as Cl#t [u, 01, a,,o,, oi), where is the task description, a; represents actions, and o, represents observations or environment feedback. The process reward model is represented as r(s,,a) E [0, 1), where š and are the state and action at the 5th step. This formulation allows for evaluating the quality of each decision point within the trajectory. Recent work has leveraged Monte Carlo tree search (MCTS) (Wang et al., 2024a;c; Xiong et al., 2024) to build effective step-wise reward models. In this paper, we also adopt the MCTS-based process reward model which is formulated as:
1 Σr roRM(u, @ ( (PR a:)
where @ represents the concatenation operation and 1+1x denotes one of the sampled rollouts subsequent to the prefix e1., The approach involves sampling m possible future trajectories from the current state-action pair and calculating the average of their correspond- ing outcome rewards. This Monte Carlo estimation provides a measure of the expected future return when taking action a state st.
3

---

Published as a conference paper at COLM 2025
3 Reward Rising Optimization
As introduced in the preliminary (62), process supervision is promising in improving LLM- based agents. However, how to effectively sample candidates during next action exploration and construct robust training set for reinforcement learning algorithms remains an open question. In this paper, we focus the relative reward trend of successive reasoning steps and propose to scale up the exploration until we find a step with rising rewards compared to the previous step. The complete pipeline of our proposed Reward Rising Optimization (RRO) contains three stages: (1) supervised fine-tuning ($3.1); (2) reward rising sampling ($3.2); and (3) agent optimization ($3.4).
3.1 Supervised Fine-tuning
Similar to previous work (Song et al., 2024; Xiong et al., 2024), we introduce the basic knowledge of the targeted task by first fine-tuning our base model with a supervised dataset to develop basic planning capabilities and adhere to the expected format for each task. We denote this fine-tuned model as 7SFT. The supervised dataset consists of expert trajectories for the agent tasks, providing demonstrations of successful task completion sequences.
We denote the supervised dataset as D = { ())
[D]
i==1 where represents the user instruc-
tion or task specification, and e = [u, 01 01, 0,, ..., Rt] is the corresponding expert trajectory. The loss function for the supervised fine-tuning stage is formulated as:
CSFT (Tt) -E (ue))D [log rel(e (ue))
Σ log rea (a
This formulation decomposes the trajectory modeling problem into a sequence of next- action predictions, where a; is the action subsequent to the trajectory prefix 61#-1. By maximizing the log likelihood of expert trajectories with this loss function, TSFT learns to imitate the decision-making process demonstrated the expert data. This supervised learning phase is crucial as it provides the initial policy that will later be refined through preference optimization techniques.
3.2 Reward Rising Sampling
After the supervised fine-tuning phase, the supervised fine-tuned model 7SFT acquires fundamental planning capabilities for the target agent task and can function effectively as policy model. The subsequent challenge lies in better aligning this policy with the specific requirements and objectives of the agent task. Before delving into the agent optimization paradigm ($3.4), we introduce in this section our novel Reward Rising Sampling approach, which dynamically scales the exploration process for next action candidates while efficiently capturing the reward rising tendency.
The preference data for process supervision consists of contrastive action pairs (aj ,4 where at > a; |e--1, indicating that action at is preferred over action a, given the trajectory prefix 614-11 To generate these contrastive pairs, we sample multiple action candidates using the policy model: a. E {ā,lâ, TTFT(-le1x-1))
A straightforward approach to constructing contrastive action pairs would be to select the action candidate with the highest process reward as the chosen sample and the action candidate with the lowest process reward as the rejected sample. However, this naive approach presents critical trade-off: scaling up the sampling size would increase the probability of generating stronger preferred candidates but would simultaneously introduce substantial computational costs. This raises important question: what criteria should determine when to stop the sampling process, ensuring that the sampled action candidate is sufficiently strong to serve good preferred sample?
Our key insight is to focus on the relative reward tendency between neighboring actions rather than pursuing absolute maximum. Specifically, we stop scaling up the sampling
4

---

Published as a conference paper at COLM 2025
Algorithm 1: Reward Rising Optimization (RRO)
Data: is the task instruction; Ty is the supervised fine-tuned policy model; 1 the trajectory prefix from step 1 to f; m the number of samples Monte-Carlo Tree Search.
Function ProcessReward (u, eiu [4, 11.,0 (t, 0zl, Tιg, m):
MC
for = 1 to do
2++1m ~ TTp (-(e))))) e< t1 D 1a
Sample the rollout 4 from the policy model nt D. Concatenate the trajectory prefix and rollout to have the full trajectory the trajectory.
5
Evaluate outcome
end
'PRM
E FORM TORM
Estimate the process reward with the average outcome rewards.
return FPRM
10
11
Function RRO (u, TT, 1):
Sample 1 steps the trajectory prefix. (PRMA-1 f ProcessReward(itcc 01:--, Tea, m) > Estimate the process rew via Monte-Carlo Sampling.
61--1 [1, 11 1-11. 0--1 (T)
13
Cand []
15
repeat
16
âr ~ nT6-1e1=-1)
Explore the candidates for the next action.
+ C14 + å
18
MRRM, - ProcessReward( e1:t, Toa m)) b. Estimate the process reward for the next action candidate.
(Aa (PRM))
until FPRM, 2 PPRM,-1 20
b Stop the exploration until showing a rising reward cumpared do
21
a: arg max (d,
Cand]
a, min (2,
E Cand)
72p (TT, (a7 a
Update policy model the preference pair from sampling.
size when we identify action candidate with higher process reward compared to its preceding action, as detailed in Algorithm 1. This approach offers a more efficient exploration strategy while maintaining the quality of preference data.
The algorithm operates as follows: suppose our last action in the trajectory prefix is A:-1 with a process reward of f;-1 r($)-1,A(-1), we sample the next action candidate and calculate the corresponding process reward iteratively:
( a E (ārlā; ~ ntp ng(-le1a-1)br)) = r()),a)))
In this iterative sampling process, we compare the reward of each sampled action with that of its preceding action in the trajectory, meaning we compare rt-1 and r Once we sample an action a!" whose process reward r|" is greater than or equal to the preceding action's
reward r, f- we terminate the sampling process and designate a, as our preferred sampled action in the preference data. We then select the candidate with the lowest process reward encountered during sampling as the rejected action in the preference data.
This reward rising criterion provides an efficient stopping condition that balances explo- ration quality with computational efficiency. By identifying actions that improve upon the current reward state, we can construct meaningful preference pairs without exhaus- tively sampling the action space. This approach is particularly valuable in complex agent environments where the action space vast and the computation of rewards can be resource- intensive.
3.3 Math Grounding
In this section, we provide math grounding on the feasibility of the dynamic sampling strategy based on the process reward setting adopted in RRO. Following previous work,
5

---

Published as a conference paper at COLM 2025
define the process reward as:
(s,,()),
E (u, e1s @
alf efft..)
m
which represents the expected success probability of the current action. Expanding this further, we express the process reward as:
FPRM ai)
m E (u, + e P(1 15.,,,,..,,1..... = P(1let:)-
1
Using the law of total probability, we rewrite the probability of success as:
p(1le==)
Σ
Σ
M++1
We now replace the probability terms with their corresponding process rewards:
(s, = -E P(1lens)))P(aaaeess
Σ
Mr+1
Since P(a++1lera) E [0,1], there must exist at least one sampled action of4 such that its corresponding process reward satisfies:
(PRM(51+1/
2 (s,
This result follows from the fact that the process reward is an expectation over multiple sampled outcomes, and least one of them must meet or exceed the previous step's reward. Furthermore, this formulation aligns naturally with the Bellman equation, reinforcing the iterative improvement of the expected success probability.
3.4 Agent Optimization
We follow the classic Direct Preference Optimization (DPO) training paradigm and continu- ously train the supervised fine-tuned model TSFT through DPO on the collected preference data. This approach enables to effectively align the model with human preferences without requiring separate reward model. The resulting model is denoted as 7DPO-
The DPO training objective is formulated as:
LDPO(TT) E (x.gaag)) log (<(BlO8 To (y Blog To(ly) (Ter
where (x, y1) represents a preference data point with input prompt and a pair of model responses where yuu > y! indicates our sampled preference data shows y is preferred over y/. The action you is considered superior to y! under the policy model Ti that we are optimizing.
The DPO objective effectively maximizes the likelihood of the model correctly ranking preferred responses higher than non-preferred ones, while maintaining reasonable proximity to the original reference model distribution. The sigmoid function o(.) converts the log probability ratio differences into probability space, allowing the model to learn from preference comparisons rather than absolute reward values.
Experiments
4.1 Dataset
We evaluate method two representative agent datasets that cover distinct interactive domains: WebShop (Yao et al., 2022) for web navigation and InterCode-SQL (Yang et al., 2023) for SQL database querying.

---

Published as a conference paper at COLM 2025
WebShop WebShop presents simulated e-commerce environment where agents must navigate through product listings, apply filters, and make purchase decisions based on specific user requirements. This dataset effectively captures the challenges of sequential decision-making in web interfaces, requiring agents to understand natural language instruc- tions and translate them into appropriate navigation actions.
InterCode-SQL InterCode-SQI focuses database interaction scenarios where agents must formulate and execute SQL queries to retrieve, manipulate, or analyze data according to user specifications. This dataset tests the agent's ability to understand database schemas, compose syntactically correct SQL statements, and iteratively refine queries based on execution results.
Both WebShop and InterCode-SQL, provide a dense reward scale from 0 to 1 to measure the task completion, enabling fine-grained evaluation of agent performance. We employ the average reward as the evaluation metric for all tasks, which effectively captures the overall performance across varying difficulty levels within each dataset.
4.2 Baseline
In our experimental evaluation, we compare our proposed Reward Rising Optimization (RRO) approach against several established baselines using Gemma-228 Team et al. (2024) as the base model. These baselines represent the current state-of-the-art methods in agent planning for WebShop and InterCode-SQI. tasks.
Few-shot:
This approach uses in-context learning with small number of examples, without any additional training. It serves as our most basic baseline to demonstrate the performance gap between zero/ few-shot prompting and more sophisticated techniques.
Supervised Fine-tuning (SFT) (Chen et al., 2023a): Supervised Fine- Munn-Tuning uses direct imitation learning to train the model on expert demonstrations, capturing the mapping from inputs to desired outputs.
Exploration-based Trajectory Optimization (ETO) (Song et al., 2024): Exploration- based Trajectory Optimization improves upon SFT by focusing on trajectories that standard SFT.
maximize the outcome reward, showing modest improvements
Iterative Step-level Process Refinement (IPR) (Xiong et al., 2024): Iterative Step- level Process Refinement iteratively improves the agent's planning and execution steps through feedback on intermediate processes.
Fixed-sized Exploration: We sample a fixed number of candidates for the next action and select the one with the highest reward as the chosen action and the one with the lowest reward as the rejected action. The key difference from our proposed RRO is the absence of the dynamic exploration of next actions and the reward rising selection criteria.
Our proposed RRO builds upon these process supervision approaches, introducing novel optimization strategy that dynamically extends the exploration space. This approach achieves superior performance while significantly reducing computational costs, as demon- strated by the results in Table 1.
4.3 Implementation
We utilize the Gemma-228-bus model as the foundation for our experiments, running on computational infrastructure of 8 NVIDIA A100-80G GPUs. This hardware setup accom- modates the demands of our preference optimization framework and supports extensive ablation studies across varying experimental configurations. During the supervised fine- tuning stage, we fine-tune the base model using expert trajectories from each dataset over 3 epochs, with a batch size of 48 and a learning rate of 2 x 10-5 cosine learning rate scheduler with warmup ratio of 0.03 is employed to enhance training stability. In the
7

---

Published as a conference paper at COLM 2025
Table 1: Agent planning results of RRO and the baselines on Webshop and InterCode-SQL. The methods are using 22mma-228 as the base model. (underline denotes the second-best performance; bold denotes the best performance; the improvement measured against the second-best performing method.)
Agent Planning
Base Model
Method
WebShop
InterCode-SQI.
Reward
Sample !
Reward
# Sample J
Without Post-training
Few Shot
12.62
3.86
Outcome Supervision
SFT (Chen et al., 2023a)
48.94
45.33
ETO (Song al., 2024)
52.34
47.13
Gemma-220
Process Supervision
IPR (Xiong et al., 2024)
61.39
4
52.39
Fixed-sized Exploration
61,20
54.68
Reward Rising Optimization (RRO)
62.91 (+1.57)
55.08 (-0.40)
reward rising optimization sampling stage, candidate actions are sampled to identify those with rising trend in process rewards. Sampling continues until an action yields higher reward than the previous one maximum of 5 candidates is reached; if no rising reward found, that step omitted in the agent optimization phase. Each candidate action's process reward is estimated by averaging the outcome rewards of generated rollouts, with a maximum of 10 rollout iterations. Finally, in the agent optimization stage, we apply the standard Direct Preference Optimization (DPO) algorithm to fine-tune the actor model over 3 epochs, using batch size of 32, constant learning rate of 3 x 10-6, and warmup ratio of 0.1. These hyperparameters are held consistent across all baseline and ablation settings.
4.4 Main Results
We compare our method with the strong baseline methods listed in Table 1. Based on the results, the proposed RRO demonstrates superior performance compared to other ap- proaches across both WebShop and InterCode-SQL. RRO achieves the highest reward scores (62.91 for WebShop and 55.08 for InterCode-SQL) while requiring a reasonable number of samples (1.86 and 1.64 respectively). This represents a significant improvement over both outcome supervision methods (SFT and ETÒ) and other process supervision approaches (IPR and Fixed-sized Exploration). The results clearly show that RRO outperforms existing techniques, suggesting that the dynamic exploration strategy and reward rising criteria effectively balances exploration and reward maximization in agent planning scenarios. This empirical evidence strongly supports the effectiveness of the RRO method as a promising advancement in improving language model performance complex reasoning tasks.
To further assess the robustness and scalability of Reward Rising Optimization (RRO), we extended experiments to the larger Gemma-2gg-base model. On this model, SFT achieved reward scores of 63.59 on WebShop and 61.41 on InterCode-SQV) Fixed-sized Exploration improved performance to 68.87 and 65.30 respectively, using fixed sample budget of 3. In contrast, RRO further elevated performance, reaching 71.24 on WebShop and 67 27 on InterCode-SOU. while requiring only 1.38 and 1.55 average samples respectively. These results confirm that RRO maintains its advantages even at larger model scales, achieving higher performance with improved sample efficiency. This successful scaling underscores the potential of RRO in complex, real-world environments.
4.5 Sampling Efficiency Analysis
Based on Figure 2, the results show that our proposed RRO significantly outperforms IPR in terms of sampling efficiency across both WebShop and InterCode-SQL tasks. For WebShop (Figure 2a), RRO achieves a high reward of 62.91 using only 1.86 sampled trajectories average, while IPR requires 5 trajectories in the iterative DPO training to reach comparable reward of 61.32, with performance improving gradually from 47.8 to 61.39 trajectory
8

---

Published as a conference paper at COLM 2025
count increases. Similarly, for InterCode-SQL (Figure 2b), RRO attains reward of 55.08 with just 1.64 sampled trajectories on average, whereas IPR shows a peak performance of 52.39 at 3 trajectories before declining to 42.5 at 5 trajectories. These results demonstrate RRO's superior efficiency, requiring fewer sampled trajectories to achieve higher rewards across both benchmarks.
15.0-RRD-O0 achieves 62.91 reward with only 1.86 trajectories
achieves 55
61.39 01.32
55.0
with with 1.64 trajectoriis
52.5
52.39
Reward
57.5
Reward
50.0
49.57
35.0
52.5
51.99
47.5
45.7
50.0
42.5
47.5
42.5
Number Required Sampled Trajectories (RRO IPR)
Number of Required Sampled Trajectories (RRO vs IPR)
Reward Rising Optimization (RRO) IPR (Xiang al., 2024)
Reward Rising Optimization (RRD) (Kiang et al., 2024)
(a) WebShop
(b) InterCode-SQL
Figure 2: Sampling efficiency of RRO and IPR on WebShop and InterCode-SQL.
4.6 Rising Rewards Analysis
We analyze the reward tendency in the trajectories generated by the supervised fine-tuned model 75FT and the reward rising optimized model πRRO- Specifically, we check if the neighboring actions demonstrate a rising tendency and calculate the proportion of actions with the rising rewards. We divide each trajectory into three equal stages (Initial, Middle, and Final), with each covering one-third of the trajectory length. As shown in Table 2, we find that TRRO consistently outperforms TsFT across both WebShop and InterCode-SQU datasets. On WebShop, our method shows modest improvements in the Middle (+1.20%) and Final (+1.36%) phases, while initially performing slightly lower (-0.58%). The benefits are more pronounced on InterCode-SQL, with significant gains across all stages: Initial (+6.75%), Middle (+2.08%), and Final (+4.42%). By the Final phase, our approach achieves 45.29% of actions with rising reward versus 40.87% for the baseline method, demonstrating more effective optimization and better reward alignment throughout the trajectory.
Table 2: Reward tendency of RRO and SFT WebShop and InterCode-SQL in the Initial, Middle, and Final stages (each covering one-third of the trajectory length).
Proportion of Actions with Rising Reward (%)
Method
WebShop
InterCode-SQL
Initial
Middle
Final
Initial
Middle
Final
Supervised Fine-tuning
1.33
32.75
9.00
15.67
41.75
40.87
Reward Rising Optimization
0.75 (40.58
33.95 (+1.20)
10.36 (+136)
22.42 (+6.75)
43.83 (+2.08)
45,29 (+4.42)
Related Work
Reinforcement Learning Fine-tuning large language models (LLMss with reinforcement learning has proven effective for aligning model outputs with user preferences. Instruct- GPT (Ouyang et al., 2022) demonstrated the potential of reinforcement learnig from human feedback (RLHF) to improve truthfulness and reduce toxicity in generated outputs. How- ever, RLHF's complexity and instability have motivated simpler alternatives, such as Direct Preference Optimization (DPO), which leverages closed-form optimal policy to aligm LLMs with human preferences more efficiently (Rafailov et al., 2024). Proximal Policy Opti- mization (PPO) (Schulman et al., 2017), foundational algorithm in reinforcement learning,

---

Published as a conference paper at COLM 2025
also underpins many RLHF methods by enabling stable policy updates through surrogate objectives. These advancements highlight the growing body of work aimed at enhancing the alignment and utiliiyy of LLMs.
Process Reward Model Recent advancements in reinforcement learning have explored process reward models (PRMs) to enhance agent training by evaluating intermediate actions or decision-making steps. Christiano et al. (2017) introduced reward models based on human preferences, demonstrating the potential of Line-grained feedback for aligning agent behavior with human expectations. Bai et al. (2022) extended this by incorporating iterative feedback for multi-step tasks, enabling more effective supervision in reasoning- heavy domains. In the context of structured decision-making, Fu et al. (2022) proposed leveraging hierarchical rewards to guide agents through complex processes, improving sample efficiency and task generalization. These works collectively highlight the role of PRMs in bridging the gap between traditional RL and multi-step reasoning tasks.
Conclusion
In conclusion, we propose Reward Rising Optimization (RRO) which dynamically extends the next action exploration in training process reward models and focuses on the relative reward tendencies between reasoning steps. By identifying steps with rising rewards, the proposed RRO offers more efficient and scalable solution to process reward modeling compared traditional computatioallintensiivi a The mathematical foundations and empirical evidence across WebShop and InterCode-SQL. underscore the potential of this technique to improve multi-step reasoning capabilities in large language models. Future work could explore the generalizability of this method across diverse task domains and further optimize the reward identification mechanism.
References
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint atXivv2204.05882 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Baian Chen, Chang Shu, Ehsan Shareghi, Nigel Collier, Karthik Narasimhan, and Shunyu Yao. Fireact: Toward language agent fine-tuning. arXiv preprint arXi::2310005915, 2023a.
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. Transactions on Machine Learning Research, 2023b.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, and Tushar Khot. Complexity prompting for multi-step reasoning. In The Eleventh International Conference on Learning Representations, 2022.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems,, 221119922221, 2022.
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2023.
10

---

Published as a conference paper at COLM 2025
Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, llya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2024.
Liangchen Luo, Yinxiao Liu, Rosanne Liu, Samrat Phatale, Harsh Lara, Yunxuan Li, Lei Shu, Yun Zhu, Lei Meng, Jiao Sun, et al. Improve mathematical reasoning in language models by automated process supervision. arXiv preprint ar arXio:2406.0659) 2024.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744, 2022.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36, 2024.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal 2017.
policy optimization algorithms. Xiv preprint ar Xix::1707.0666
Yifan Song, Da Yin, Xiang Yue, Jie Huang, Sujian Li, and Bill Yuchen Lin. Trial and error: Exploration-based trajectory optimization of LLM agents. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), Pp. 7584-7600, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 409. URL https: wwwannholoogyyoooooooooooooooooe org/ 2024. ac long-loog.4440 409.
Gemma Team, Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, et al. Gemma 2: Improving open language models at a practical size. arXiv preprint ar arXiv:2408.00118, 2024.
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce LLMs step-by-step without human annotations. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9439, Bangkok, Thailand, August 2024a. Association for Computational Linguistics. doi: 10.18653/ 11//222.acl-oong... URL https: / ac lanthology org/ 510.
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce Ilms step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9426-9439, 2024b.
Zihan Wang, Yunxuan Li, Yuexin Wu, Liangchen Luo, Le Hou, Hongkun Yu, and Jingbo Shang. Multi-step problem solving through a verifier: An empirical analysis on model- induced process supervision. arXiv preprint XrXi:22002.0265, 2024c
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Fd Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Weimin Xiong, Yifan Song, Xiutian Zhao, Wenhao Wu, Xun Wang, Ke Wang, Cheng Li, Wei Peng, and Sujian Li. Watch every step! Ilm agent learning via iterative step-level process refinement. arxiv preprint ar Xit::2406.111766666 2024.
John Yang, Akshara Prabhakar, Karthik Narasimhan, and Shunyu Yao. Intercode: Standard- izing and benchmarking interactive coding with execution feedback. Advances in Neural 2023.
Information Processing Systems,
11

---

Published as a conference paper at COLM 2025
Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 20744-20757 Curran Associates, Inc., 2022. URL /ttp:///////ooeeeeeeeeeeee neurips cappa witees/aape///////// /0022/ 2ree22aaaeeaa114444000oo-------r
conpeer-coofeeecee..d
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and
Yuan Cao. React: Synergizing reasoning and acting in language models. In International
Conference on Learning Representations (ICLR), 2023.
Li Zhong, Zilong Wang, and Jingbo Shang. Debug like human: A large language model debugger via verifying runtime execution step by step. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Findings of the Association for Computational Linguistics, ACL. 2024, Bangkok, Thailand and virtual meeting, August 11-16, 2024, pp. 851-870. Association for Computational Linguistics, 2024. doi: 10.18653 htttps://do1 http//ooooogg/o./ 18653,86331111 v1 2024. findings- ac1.49.
URL
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting en- ables complex reasoning in large language models. In The Eleventh International Conference on Learning Representations, 2023.
12


Reviews:
[{"review_id": "XeoWciHXEO", "reviewer": "Reviewer_yiKS", "summary": "This paper focuses on the efficiency problem on the process supervision for LLM agent learning. To effectively acquire the training data throug the per-step trajectory exploration, this paper propose Reward Rising Optimization method. This method dynamically expands the search space for the next action candidates. Experiments show the effectiveness of the method.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* The proposed RRO method introduces a dynamic search space expansion mechanism for process reward-based LLM agent training, offering a fresh perspective on efficiency optimization.\n* Experiments show that RRO outperforms both outcome-based and process-based reward methods while requiring fewer exploration samples.\n* This paper is well-written.", "reasons_to_reject": "* The experiments lack detailed setup. Key hyperparameters and implementation specifics are missing, making reproducibility difficult.\n* Experiments are conducted only on Gemma-2-2B. Broader validation on larger models (e.g., 7B or larger LLMs) would strengthen the claims.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hTT2mnvuXf", "reviewer": "Reviewer_w85m", "summary": "This paper addresses the challenge of training LLM-based agents to perform complex multi-step reasoning tasks. Such tasks often fail due to their sensitivity to key decision points and the difficulty of correcting subtle trajectory errors. While Process Reward Models (PRMs) have been proposed to provide fine-grained feedback for each step, their scalability is hindered by the high computational cost of exploring every possible action at each step.\n\nTo mitigate this, the authors propose Reward Rising Optimization (RRO), a new method that emphasizes the relative reward trend across sequential steps. RRO dynamically scales the sampling process and halts exploration once an action yields a higher process reward than its predecessor. This strategy prioritizes high-reward trajectories while reducing computational overhead. The paper provides both theoretical justifications and empirical evidence from experiments on the WebShop and InterCode-SQL benchmarks.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. **Novel Approach for Agent Training**: The paper introduces RRO that focuses on the relative reward tendency and dynamic adjustment of the search space. While it bears resemblance to classical search heuristics, its application to process supervision in agent learning offers an effective alternative to exisiting PRM schemes.\n\n2. **Improved Empirical Results and Sampling Efficiency**: The method achieves state-of-the-art performance on WebShop and InterCode-SQL, outperforming both outcome-supervised baselines (SFT, ETO) and process-supervised baselines (IPR, fixed-size exploration). Notably, it achieves higher rewards while requiring fewer sampled trajectories, demonstrating better sampling efficiency.\n\n3. **Theoretical Grounding**: The authors provide theoretical justification for the reward rising criterion, showing that under the Bellman equation and process reward formulation, there always exists a future action with equal or higher expected reward. This adds credibility to the method's stopping criterion.", "reasons_to_reject": "1. **Limited Generalization Across Tasks and Models**: The method is evaluated on only two agent benchmarks, which—although representative—are limited in diversity. Furthermore, experiments are conducted using only a single model (Gemma-2-2B). It remains unclear how RRO would generalize to models of different architectures or other domains.\n\n2. **Implementation Complexity and Opaque Computational Trade-offs**: The overall pipeline includes supervised fine-tuning, reward rising sampling, and DPO training. While modular, each stage introduces its own complexity. Reproducing the full pipeline may require substantial engineering effort, particularly in large-scale environments. Although RRO is shown to be more sampling-efficient, the total computational cost (e.g., GPU hours) is not reported. Since the method still relies on Monte Carlo tree search and dynamic sampling, a more comprehensive comparison of computational cost would help practitioners assess its practicality.", "questions_to_authors": "To my understanding, RRO halts sampling as soon as it observes a rising reward. What if a better (higher-reward) action exists further in the sampling sequence? Does this mean RRO is not guaranteed to find the globally optimal trajectory?\n\nComments:\nThe Gemma-2-2B model is used in all experiments but is not properly cited in the main text. Please include a citation for clarity and reproducibility.", "extra_scores": {}}, {"review_id": "pgcuGIfv14", "reviewer": "Reviewer_a4Sq", "summary": "This paper proposes Reward Rising Optimization (RRO), a new approach to process supervision in LLM-based agent learning. RRO focuses on relative reward increases --- sampling is stopped once an action yields a higher process reward than the previous step. This strategy improves sample efficiency and reduces computation cost. Authors demonstrate that RRO is validated with mathematical justifications and evaluated on WebShop and InterCode-SQL, and show that it outperforms prior methods like IPR and ETO.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- Introduces a conceptually simple yet effective sampling stopping criterion based on reward increase.\n- Demonstrated ability to achieve comparable or better performance with significantly fewer samples.\n- The method is well-motivated, and Algorithm 1 is easy to understand and replicable.", "reasons_to_reject": "- Simple experiments. The authors only conduct experiments on a small model Gemma-2B on two tasks. I would expect some experiments on at least 7B models to show that the method is still effect.\n- No justification of fewer samples. Although the experiments show that the RRO methods achieves the similar results as IPR, and other methods while with fewer samples been explored. There is no proof of it, I would concern in some cases, the RRO will need more exploration compared to other methods. The math ground of the existence does not mean it is easier to find.\n- What happens when rewards are flat or noisy? Is the “first rising” heuristic always reliable?", "questions_to_authors": "- How does RRO behave in environments where rewards are noisy or non-monotonic across good trajectories?\n- Have you explored using a threshold delta (e.g., reward increase ≥ 0.05) instead of any positive increase?\n- Can this method be applied to domains without dense reward functions or where the reward model is unreliable?", "extra_scores": {}}, {"review_id": "BfI5R9xedr", "reviewer": "Reviewer_QfKa", "summary": "This paper proposed Reward Rising Optimization (RRO), a dynamic exploration strategy for process supervision in LLM agent learning,aimed at improving process supervision in LLM agent learning.The approach prioritizes actions that exhibit a \"rising reward\" trend compared to preceding steps, offering an efficient strategy for exploring the action space. By dynamically adjusting the exploration scope, RRO helps in reducing computational costs while still capturing high-quality trajectory data. The method is empirically validated on WebShop and InterCode-SQL, showing significant improvements over existing benchmarks state-of-the-art approaches in terms of both performance and sample efficiency.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The method provides a scalable solution for LLM-based agent training, offering clear advantages in real-world applications where computational resources are limited.The \"rising reward\" criterion balances exploration quality and computational cost, avoiding over- or under-exploration.\n2. RRO is supported by robust theoretical explanations that show its potential for addressing critical challenges in multi-step agent tasks, reinforcing its applicability.\n3. The experiments cover two distinct benchmarks, demonstrating RRO’s versatility and general applicability across different types of agents tasks.", "reasons_to_reject": "1. The paper focuses primarily on controlled benchmarks (WebShop and InterCode-SQL), but it does not address how well the proposed method would generalize to real-world tasks or complex environments, which would provide a clearer picture of its practical utility.\n2. The absence of an ablation study prevents a clear understanding of the contribution of key components in RRO.\n3. The paper lacks analysis of average/max sampling steps required for convergence.\n4. Does the baseline method (such as IPR) in this paper reproduce under the same hardware/hyperparameters? It is necessary to explain the consistency of the experimental Settings to avoid the conclusion being affected by the implementation differences.\n5. Figure.2 lacks error bars or confidence intervals, obscuring the variance in reward scores.", "questions_to_authors": "please refer to section \"Reasons To Reject\"", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work proposes a search heuristic that focuses on promising trajectories for better PRMs.
All reviewers agree that this sampling strategy is a nice contribution that leads to better performance and efficiency. The authors also added experiments with a second model during the author response.
Decision: Accept