We thank the reviewer for the feedback. We address the points below.

Weaknesses

Some experiments and theories can be added.

We believe the current manuscript provides a comprehensive theoretical framework and sufficient experimental validation. Theoretical contributions include the provable regret guarantees for reward selection, and our experiments span diverse tasks, ablations on different selection strategies, reward functions set size and budget. To help us better address your concern, could you please identify specific gaps in either our theoretical analysis or experimental validation that you feel need addressing? We would be happy to take the suggestions into consideration to improve the contribution of our work.

Questions

The experiments compared the performance of policies trained using No Design, Human, Naive Selection, and ORSO to show the superiority of ORSO. However, the impact of selecting different reward functions for ORSO algorithm on experimental results has not been analyzed. If possible, please provide relevant experiments to demonstrate the experimental differences caused by selecting different reward functions.

Thank you for the suggestion to analyze different reward functions in detail. However, running full training on each reward function would be computationally prohibitive, which is precisely the challenge our method aims to address.

To demonstrate the effectiveness of our approach, we provide results for the Ant task. Specifically, we trained a policy for each of the 96 reward functions used in Figure 5 (Figure 6 in the updated PDF). The table reports the mean task reward with 95% confidence intervals over five seeds. Rewards are ordered from best to worst, with those within one confidence interval of the best reward italicized (up to and including reward ID 54). Bolded values indicate the reward functions selected by ORSO + D3RB across the seeds we ran.

Our results show that ORSO consistently selects reward functions within one confidence interval of the best reward. The occasional selection of different reward functions can be attributed to the inherent stochasticity in reinforcement learning training.

Questions

• Q1

  The proposed method generates a set of candidate reward functions for the online selection phase. Does having K reward function candidates mean that the number of candidates is fixed? If all these candidates are not suitable or not the best, what is the solution?

  This is a great question. Our method includes an iterative improvement step that allows for refinement of the reward functions (proposal of new candidates). Furthermore, our experimental results demonstrate that even with a fixed set of reward functions, ORSO with D3RB performs well, given the reward function set is large enough (our Ant experiments in Section 5.3 show that with K=48 or K=96 can still outperform human-design performance). The large candidate set makes it highly probable to include effective reward functions.

• Q3

  Figure 4 shows the normalized cumulative regret for different selection algorithms. The manuscript mentioned that the ORSO’s regret can become negative, indicating that it finds reward functions that outperform the human baseline. The minimum value is zero in Figure 4, I didn’t observe the negative values.

  Thank you for this observation. The instantaneous regret can indeed become negative when ORSO identifies reward functions that outperform the human baseline. This causes the cumulative regret to decrease, but it does not necessarily drop below zero in the normalized cumulative regret plots.

• Q5

  The number of references is small, and more recent articles on reward shaping can be added.

  Thank you for this suggestion. While the manuscript includes foundational and relevant works, we will expand the related work section to include additional recent papers on reward shaping. If there are specific references the reviewer believes are important, we welcome the input.

We hope that our clarifications and the proposed additional experiments sufficiently address the reviewer’s questions and concerns. Given the theoretical results, comprehensive experimental evaluation, and practical relevance of ORSO, we believe our work makes a meaningful contribution to the field of reward design in reinforcement learning. We kindly ask the reviewer to reconsider their evaluation of the manuscript. Thank you for your thoughtful consideration.

We thank the reviewer for the quick response. We addressed the instability in choosing among many reward functions in the response to Reviewer DEh7's comments (https://openreview.net/forum?id=0uRc3CfJIQ&noteId=GdpudWUVqQ). Moreover, we show in our experiments with K=48 and K=96 that this instability does not occur. The additional table provided in the review above serves to show that ORSO indeed selects reward functions within one CI of the optimal one.

Regarding the suggestion to consider regression for obtaining new rewards instead of selection, we appreciate the idea but would like to better understand the intended approach.

We would also ask that if the previous comments clarified the reviewer’s questions, they would consider increasing the score accordingly. Thank you again for your time and feedback.

Thanks for the authors' response. Many of my concerns have been addressed.

Regarding the "regression" approach, I note from Appendix E.1 that most reward functions created by LLMs are parsing the observation space to extract various pieces of information, designing reward components, and then summing them with weights. If all candidate reward functions are of similar form, rather than having the LLM generate K reward functions and simultaneously maintaining K policies for selection, I wonder if it would be more flexible to let the LLM/human only specify the components and then learn the corresponding weights (a zero weight indicates the absence of a reward component). This is just an idea of mine and not a request for the authors to implement during the rebuttal period.

After carefully reading the revised paper and other reviewers' comments, I decided to maintain my score for the following reasons:

1. The LLM-generated reward functions have certain limitations and lack controllability. The LLM-generated reward functions are constrained by the LLM's understanding of the environment or the prior knowledge provided by humans. As shown in the examples from Appendix E.1, the LLM appears to have a clear understanding of what each element in the observation space represents. However, in many real-world environments, such as those with image-based observations, such detailed understanding is difficult to obtain. This limitation restricts the generalizability of ORSO.

2. In my view, the contribution of the paper is somewhat incremental. The method for generating candidate reward functions closely follows existing work (e.g., EUREKA). Similarly, the selection strategies employed are also existing algorithms (e.g., ETC, EG, UCB, EXP3, and D3RB). Simply combining these two parts and demonstrating improved performance over EUREKA without selection strategies does not constitute a sufficiently novel contribution.

3. The abstract claims that "While shaping rewards have been introduced to provide additional guidance, selecting effective shaping functions remains challenging and computationally expensive." However, this overlooks many methods that do not require explicit shaping function selection. Numerous algorithms exist that automate the generation of reliable reward models. Although the experiments in the paper explore the importance of reward selection and compare various selection strategies, the primary objective of the paper is reward design. To fully demonstrate its effectiveness, comparisons with SOTA (within the last five years) automated reward shaping methods would be necessary.

Given these considerations, I have decided to maintain my score. I would like to thank the authors again for their response.

We thank the reviewer for their response. We would like to address the concerns raised by the reviewer.

Regarding the "regression" approach, I note from Appendix E.1 that most reward functions created by LLMs are parsing the observation space to extract various pieces of information, designing reward components, and then summing them with weights. If all candidate reward functions are of similar form, rather than having the LLM generate K reward functions and simultaneously maintaining K policies for selection, I wonder if it would be more flexible to let the LLM/human only specify the components and then learn the corresponding weights (a zero weight indicates the absence of a reward component). This is just an idea of mine and not a request for the authors to implement during the rebuttal period.

We thank the reviewer for clarifying the regression approach. This is indeed an interesting approach for settings in which the possible reward components are known and the candidate rewards are all in the same form and would be exciting to explore as a future direction. However, we would like to note that one might not know all possible reward components or listing all possible components might not be feasible as there might be numerous possible transformations applied to, for example, the distance component. We further elaborate on this point here.

The LLM-generated reward functions have certain limitations and lack controllability. The LLM-generated reward functions are constrained by the LLM's understanding of the environment or the prior knowledge provided by humans. As shown in the examples from Appendix E.1, the LLM appears to have a clear understanding of what each element in the observation space represents. However, in many real-world environments, such as those with image-based observations, such detailed understanding is difficult to obtain. This limitation restricts the generalizability of ORSO.

We agree that LLM-based generation is not the answer to reward generation in general. However, we would like to point out that many real-world applications [1, 2, 3] are non-image-state-based. Moreover, as the reviewer pointed out, generation is not the main contribution of our paper, which is the only part of the algorithm that requires access to the environment code. The ORSO framework can be applied to any form of reward function. The choice of using LLMs to generate reward functions is motivated by the success of such methods in EUREKA and other similar works.

In my view, the contribution of the paper is somewhat incremental. The method for generating candidate reward functions closely follows existing work (e.g., EUREKA). Similarly, the selection strategies employed are also existing algorithms (e.g., ETC, EG, UCB, EXP3, and D3RB). Simply combining these two parts and demonstrating improved performance over EUREKA without selection strategies does not constitute a sufficiently novel contribution.

While ORSO is similar to EUREKA (Ma et al., 2024), our work extends beyond a simple modification. In Figure 3 of the updated PDF, we show that ORSO has significant (up to 16x fewer GPUs needed to achieve the same performance in the same time) gains in terms of necessary compute compared to EUREKA. All our experiments can be indeed run on a single commercial GPU (e.g., a 3090 Ti or even a 2080 Ti). This will open the possibility for researchers with smaller computational budgets to quickly iterate their experiments.

Moreover, the connection between model selection techniques and reward design in RL has not been explore before and our experimental results show that we gain in efficiency, while maintaining effectiveness. We provide a novel analysis of D3RB, which is in stark contrast with the regret guarantees of the original paper. Namely, our guarantee depend on the true regret coefficients rather than the monotonic ones.

References

[1] Margolis, Gabriel B., et al. "Rapid locomotion via reinforcement learning." The International Journal of Robotics Research 43.4 (2024): 572-587.

[2] Margolis, Gabriel B., and Pulkit Agrawal. "Walk these ways: Tuning robot control for generalization with multiplicity of behavior." Conference on Robot Learning. PMLR, 2023.

[3] Lee, Joonho, et al. "Learning quadrupedal locomotion over challenging terrain." Science robotics 5.47 (2020): eabc5986.

We thank the reviewer for the feedback and the suggestions to improve the paper. We address the comments below.

• W2

  The author states that this is a reward shaping approach, but the paper doesn't compare it with any reward shaping or reward selection baselines. If the authors could compare ORSO with some representative reward shaping algorithms (such as [1][2][3][4]), it would better showcase its advantages.

  These papers collectively discuss various approaches to reward shaping and intrinsic motivation in reinforcement learning, with a focus on improving learning efficiency in sparse-reward environments through methods like exploration-guided rewards (ExploRS), learning intrinsic rewards, self-supervised reward shaping, and random network distillation (RND).

  We note that methods like [1] are complementary to ORSO, meaning that one can use ORSO to propose shaped reward functions and then apply other shaping methods on top to further improve the performance of such reward functions.

  We chose to compare ORSO-designed reward functions with LIRPG because it is one of the most widely adopted methods for reward design in reinforcement learning. We provide experimental results with LIRPG on the Ant task. LIRPG jointly trains a policy and learns an intrinsic shaping reward, such that the intrinsic reward leads to higher extrinsic reward.

  In each experiment, we use the task reward function, the human-designed reward function, and the reward function selected by ORSO as the extrinsic reward for LIRPG, respectively. We run each experiment for 5 random seeds and report the mean base environmental reward achieved by training with each method, along with 95% confidence intervals.

  Method	Without LIRPG	With LIRPG
  No Design	4.67 +/- 0.84	5.73 +/- 1.08
  Human	9.84 +/- 0.30	10.02 +/- 0.30 (*)
  ORSO	11.09 +/- 0.68	11.51 +/- 0.45 (*)

  • LIRPG cannot design better rewards than ORSO: When LIRPG is applied to the task reward, it results in lower performance compared to using the human-designed or ORSO-selected rewards.
  • LIRPG as a complementary method: We emphasize that LIRPG can complement ORSO. By applying LIRPG to reward functions selected by ORSO (which have already undergone shaping), LIRPG may help learn an additional function that aids the agent in optimizing ORSO-designed rewards.

  The bolded entries have undergone one stage of reward shaping, while the entries in the table above marked with (*) have undergone two stages of reward design. First a performant reward function was obtained from a human designed or ORSO (both outperforming LIRPG on the task reward). Then, given the good quality of the reward, we show that we can apply LIRPG on such reward functions to some marginal improvement. We only provide such results for completeness. We note that the evaluation of each policy is done with respect to the task reward function (No Design).

  LIRPG does not help if the extrinsic reward function is too sparse. We also test LIRPG on sparse-reward manipulation tasks, such as the Allegro Hand. However, LIRPG does not provide any improvement over the environmental reward as the reward function is “too sparse.” This agrees with the experimental results in Figure 7 of [1], where the authors show that increasing the sparsity of the feedback (every 10, 20, or 40 steps) can decrease the performance of LIRPG.

• 1 (a)

  What are the specific forms of these reward functions? Are they related to the observations, features, and/or pre-defined reward components? Can these generated rewards capture all the necessary aspects to define effective rewards?

  The reward functions are generated as Python code. The input of the reward functions are environment observations and agent actions. We report some reward functions in the Appendix of the updated PDF file.

• 1 (b)

  If the optimal reward function is not included in the generated candidates, how does ORSO ensure that the final optimized policy is indeed optimal?

  The regret guarantee we provide is with respect to the optimal reward function in the set of candidate functions. While it is true that if the set does not contain an optimal one, ORSO would not achieve high task reward, we find that in practice this rarely happens. Practically, in order to find a performant reward functions, we need sampling and iterative improvement. Thanks to ORSO’s efficiency, we can explore a large set of functions within a limited budget, which leads to a higher probability of sampling the optimal reward function from the generator.

1. Q1

   The policy optimizes based on a given candidate reward function, would this make it difficult to ensure that the policy is optimizing the task's original objective (the environmental reward function defined by the MDP)?

   This is correct. If the candidate reward function does not optimize the for original environmental reward, the learned policy would not be optimal with respect to the original task. Reward candidates that, when optimized for, lead to low original environmental reward are discarded by our selection algorithm and those that lead to higher environmental reward will be chosen more often. Reward design involves aligning auxiliary reward functions with the task reward, especially when the task reward is sparse or difficult to optimize. This is typical in robotics [2, 3], cybersecurity [4] and more. Approaches like potential reward shaping [5] can provably preserve optimality, however, they have been shown to not work very well in practice [6], however, as shown in the additional LIRPG experiments above, such methods can help improve base reward functions marginally.

2. Q2

   Frequent switching of reward functions may lead to significant shifts in the policy's learning objectives. For instance, in a maze task, if reward function #1 focuses on avoiding obstacles, while reward function #2 focuses on resource collection, switching between these two may lead to inconsistent learning targets. Would this cause instability in the learning process?

   In the implementation, this behavior does not occur because a separate policy is instantiated for each reward function, as detailed in Algorithm 1, line 2. Consequently, each policy is updated only as frequently as its corresponding reward function is selected.

3. Q3

   I'm unclear about the evaluation metric in the experiments, specifically, in Figure 2 (left), it shows performance as a percentage of the human-designed reward function. In Section 5.1.1, the paper states, "No design is with the task reward function r for each MDP". I assume this refers to the original environmental reward function, which should be the primary objective the agent aims to optimize. However, in Figure 2 (left), the "No design" baseline is around half of the human-designed reward (I assume this figure reports cumulative rewards under each baseline's own reward function). This seems unfair and could introduce bias for deviating from the MDP’s original task objective.

   All evaluations in our experiments are with respect to the MDP’s task reward $r$. Because the human-designed reward functions were specifically designed so that training on those would improve task reward, we normalize result such that the policy of human designed reward functions is at 1.0. The “No Design” line being lower than the “Human” line means that training with the original task reward achieves lower performance than training with the human-designed reward function as measured by the original environmental reward function. This is exactly the objective of reward design: we aim to find reward functions that, when optimized, will lead to better performance with respect to the original task reward (because the designed reward is more amenable to optimization). In Figure 2 (left), the "No design" baseline — using the task reward function alone — achieves approximately half the performance of the human-designed reward. This demonstrates the difficulty of optimizing directly for the task reward and highlights the benefit of effective reward design in facilitating better optimization.

• Regarding the example MDP, we would like to reiterate that the evaluation is done with respect to the the original task reward. Therefore, if one were to evaluate using the human-designed reward function (0, 1, 1), an agent that equally visits the states 2 and 3 would be optimal but would not be optimal if we evaluate using the task reward (0, 0, 1). Therefore, in our evaluation, the human-designed reward function would not be considered a “good” one. On the other hand, a reward function of the form (0, 1, 2) would be “good” as it provides more guidance compared to (0, 0, 1) and the optimal strategy is still to visit state 3 as often as possible. This is more obvious if we consider an MDP with $n$ states $s_1, \ldots, s_n$ with task reward function (0, 0, …, 0, 1), i.e., zero everywhere, except for the n-th state. This reward function is clearly sparse and hard to optimize. A good human-designed reward function could look like (1/n, 2/n, …, (n-1)/n, n), which still leads the agent towards the n-th state but provides more guidance during training.

We hope these clarifications address the concerns raised. If clarifications and additional experiments resolve your concerns, we would be grateful if you could consider raising your score to reflect the improvements.

References

[1] Zheng, Zeyu, Junhyuk Oh, and Satinder Singh. "On learning intrinsic rewards for policy gradient methods." Advances in Neural Information Processing Systems 31 (2018).

[2] Cheng, Xuxin, et al. "Expressive whole-body control for humanoid robots." arXiv preprint arXiv:2402.16796 (2024).

[3] Margolis, Gabriel B., and Pulkit Agrawal. "Walk these ways: Tuning robot control for generalization with multiplicity of behavior." Conference on Robot Learning. PMLR, 2023.

[4] Bates, Elizabeth, Vasilios Mavroudis, and Chris Hicks. "Reward Shaping for Happier Autonomous Cyber Security Agents." Proceedings of the 16th ACM Workshop on Artificial Intelligence and Security. 2023.

[5] Ng, A. Y., Harada, D., & Russell, S. (1999). Policy invariance under reward transformations: Theory and application to reward shaping. In ICML.

[6] Cheng, Ching-An, Andrey Kolobov, and Adith Swaminathan. "Heuristic-guided reinforcement learning." Advances in Neural Information Processing Systems 34 (2021): 13550-13563.

Thanks for the authors' response.

I have some questions want to discuss:

1. regarding Q1(a), the specific forms of these reward functions, thanks for updating the detailed reward functions in the appendix. I have two main concerns: (a) seems the reward function needs much task-specific knowledge, like:

velocity = root_states[:, 7:10] # [vx, vy, vz]
torso_position = root_states[:, 0:3] # [px, py, pz]

how does LLM know this kind of information (like which dimensions refer to which metric) or it is given in the prompts? If we still need to provide this prior knowledge to LLM, not sure why not directly use a human-designed reward function. For example, if we already know the [7:10] represents the velocity, and suppose my final target is to let the ant be as fast as possible, then why not just write out this reward function?

Moreover, I see the final reward is the weight-sum of different components:

reward = forward_reward + balance_reward + angle_penalty - action_penalty_scaled + survival_bonus

can just learn some weights of different components, instead of "generating a lot of candidate reward functions and choose one from them"?

(b) How about some more complex environments, like Atari? given the pixel observations, does it still work to generate python reward functions?

2. Regarding the author's claim:

This is more obvious if we consider an MDP with n states $s_1,\dots,s_n$ with task reward function (0, 0, …, 0, 1), i.e., zero everywhere, except for the n-th state. This reward function is clearly sparse and hard to optimize. A good human-designed reward function could look like (1/n, 2/n, …, (n-1)/n, n), which still leads the agent towards the n-th state but provides more guidance during training.

But this still leads to non-consistent optimal policies, let's take a three-state example: $s_1,s_2,s_3$, and two reward schemes: $R_1: s_1 =0, s_2=0, s_3=1$, and $R_2: s_1 =1/3, s_2=2/3, s_3=3/3=1$ as the authors' claim. Then we consider the following trajectory: $t_1: s_1 \rightarrow s_2 \rightarrow s_3$, which we know clearly is the optimal trajectory under the environmental rewards. Then compute the returns under two reward schemes ($\gamma=0.9$):

while we further consider the trajectory: $t_2: s_1 \rightarrow s_2 \rightarrow s_2 \rightarrow s_3$, then:

We can see: $return_2(t_2) > return_2(t_1)$ but $return_1(t_2) < return_1(t_1)$, which means under the human-designed reward scheme, the optimal policy changes (actually, staying at $s_2$ longer can get higher returns). This is where my main concerns from, in the LLM-generated reward functions, could it be possible the reward functions make the agent stay in some local optimum and then lead to sub-optimal or non-consistent policies?

3. Regarding the novelty and contribution, from the papers' statements at around Line 309, and to my knowledge, the OSRA mainly modified the EUREKA (Ma et al., 2024) from selecting and testing one-by-one to initializing all candidates and testing in parallel, which is not a big improvement, but naturally trading space for time.

4. Lastly, I encourage the authors to compare ORSO with at least one more related baseline, as for now, the study of comparing ORSO with different sources of reward functions is good enough, but no other auto-reward-function-generation algorithms are compared, they also show good performance on sparse-reward envs and reward design.

Questions

• Q1

  Lines 54-59: I understand you are highlighting unique challenges compared to standard multi-arm bandit settings, yet ORSO uses the same selection algorithms typically used to solve such multi-arm bandit problems. The paper could be clearer in defining exactly which components of ORSO are key to address the unique challenges presented.

  The main difficulty of using classical MAB algorithms lies in the non-stationarity and statefulness of each learner (candidate reward function and corresponding policy) in ORSO. Algorithms such as UCB provide convergence guarantees if the utility of each arm is stationary. However, it is clear that as one trains using a reward function the task reward achieved by the corresponding policy will change. We integrate algorithms for online model selection (D3RB), which are designed to deal with stateful learners, into our ORSO implementation and show that such methods indeed overcome some of the problems encountered by MAB algorithms (e.g., they tend to commit to seemingly optimal reward functions early on and not exploring reward other reward functions enough). Therefore, the key component for successful selection is D3RB, which can deal with stateful learners.

• Q2

  I recommend expanding on the various resampling strategies, if more than one was tried out, and their impact on performance as this seems to be a key ingredient to the method's success.

  We have reported the resampling strategy in the Appendix, where we also discuss the pros and cons of different resampling strategies. We do not have have statistically significant evidence that the resampling strategy in our experiments is optimal, nor do we claim so. However, we observed in some early experiments that the chosen strategy (we resample one half of the new set of reward functions by conditioning the reward generation on the code of the previous best reward function and the other half is generated from scratch as if it was the first time the reward function set was generated) was a good tradeoff between greedily improving the best reward function for all new rewards and always resampling from scratch.

• Q3

  I would recommend adding the synthetically generated best-performing shaping reward functions for each task to appendix E. Are the reward functions sensible to the human reader? This has implications on how well these shaping reward functions could be further refined by human experimenters, and possibly give insights on their logical soundness.

  This is a great suggestion. We have reported the code for the best reward functions in the Appendix in the updated PDF.

• Q4

  Also, was any constraint, structure, human knowledge beyond the imposed when prompting the generation of such rewards or could the prompt be arguably generated programmatically (if so, I recommend just stating it - the code base is not available during the review process to verify)? While not directly related to the ORSO contribution, this is arguably important to showcase as ORSO heavily relies on the existence of an automated way of generating reward functions without human priors.

  In our experiments, we do not add any particular human knowledge in addition to simply exposing the observation space and some useful environment variables available in the environment definition. We will make sure to clarify this in the manuscript. We would also like to add that if human prior is available (e.g., we might know which reward components are important for quadruped locomotion — xy velocity tracking, yaw velocity tracking, action penalty, body height, etc. — but do not know how to weigh them), we can use a Bayesian way to update the distribution of each coefficient as detailed in the response to the first Weaknesses bullet point. This would indeed be an interesting future experiment

We thank the reviewer for the comments and the insightful feedback provided. We address the points below.

Weaknesses

• W1

  Ultimately, ORSO searches over a set of shaping reward functions. While the framework is simple and elegant, to my understanding, it ultimately relies on and is limited by the performance of the "shaping reward function generator".

  While it is true that ORSO’s performance relies on the set of reward functions given by the generator, our practical implementation includes an iterative improvement resampling step that allows the algorithms to improve the set of candidate reward functions. An alternative generator could be devised. For instance, if the required reward components are known, an alternative generator could sample different weights for the reward components from a uniform distribution over plausible ranges. For example, let the reward function $r(s, a)$ be a weighted sum of known components $r_1(s, a), r_2(s, a), \ldots, r_k(s, a)$, with weights $\boldsymbol{w} = [w_1, w_2, \ldots, w_k]$. ORSO could then operate on this sampled set (our experiments show that ORSO works well even with large reward sets). Then the results could be used to update a posterior distribution over the parameter weights. Repeating this process would allow the framework to explore any reward function space defined by its components.

• W2

  ORSO is only benchmarked against methods for which a performant human-engineered reward function can be defined. Impact would be higher if method could generalize beyond these settings.

  We would love to test ORSO on tasks where no human-designed reward function is available. If the reviewer has specific continuous control tasks and implementation in mind, we would be happy to explore them. However, this may fall outside the discussion timeframe, though we could incorporate these suggestions in future work.

• W3

  ORSO in its current form does not seem to offer the flexibility to deal with changing / annealing of shaping reward functions throughout training, a common technique in reward shaping literature.

  While we have not implemented shaping reward annealing in this version, this feature could be easily added. Since the selection algorithms track the frequency of each reward function being chosen, shaping rewards could be dynamically re-weighted, e.g., inversely proportional to the selection count. We encourage the reviewer to check our codebase following the publication of ORSO, as we plan to incorporate such variants to enhance the framework’s utility for the community.

Dear Reviewer,

We sincerely appreciate your thoughtful and positive feedback on our paper. Your insights were incredibly helpful in refining our work. We hope that our responses to your comments have addressed your concerns and clarified the contributions of our study.

If there are any remaining questions or areas where you feel further clarification is needed, we would be happy to provide additional details or engage in further discussion. We hope that our responses demonstrate the merits of the paper, and we kindly ask if you would consider revisiting your evaluation in light of these updates.

Thank you again for your time and effort in reviewing our submission. We greatly value your perspective and look forward to your final decision.

Best regards,

The Authors

We thank the reviewer for their thorough review. Your detailed understanding of our work is greatly appreciated, as reflected in your summary and questions. We address your points below:

1. Related Work

   We agree with moving the related work section to the main paper. This will help better contextualize our contributions. The revised PDF contains some related work in the main paper and a more thorough treatment of relevant literature in the appendix.

2. Assumption 4.2 and Monotonicity

   • In our experimental settings, we observed that monotonicity holds in most cases
   • The few violations we observed (visible in Figures 17 and 18) occurred with alternative selection strategies, not with D3RB
   • These cases likely represent situations where the selection strategy committed to a suboptimal reward function, while the optimal reward function still exhibited monotonic behavior
   • The convergence result presented in our manuscript (dependence on true regret coefficient) is different from the one presented in the original D3RB paper (dependence on the monotonic regret coefficient). The intuition behind the guarantees provided in our paper is that the true regret coefficient dependence implies that even if the optimal reward function has a “slow start”, it can still be selected and trained on and will achieve similar regret to running only the optimal.

3. Impact of Wrong/Redundant Reward Functions

   • While a direct analysis of wrong/redundant reward functions would be ideal, it would be computationally prohibitive given our large search space
   • However, our analysis of varying K (number of reward functions) serves as a useful proxy:
     • The results in the appendix show ORSO's robustness to K given sufficient budget
     • On the other hand
       • With small K, naive selection can evolve quickly but risks converging to and evolving suboptimal rewards
       • With large K, naive selection may explore more options and allow evolution to find optimal rewards, however, this will lead the naive selection algorithm to spend significant amount of time and compute on suboptimal reward functions initially

4. VLM-based Reward Design

   In some initial experiments, we tested the possibility of using VLMs to evaluate the behavior of trained agents and remove the need to the manually specified task reward function. We however observed that, at the time of the experiments, VLMs struggled to evaluate behaviors correctly and would hallucinate most of the time. We believe that as VLMs improve, this can be an exciting direction to explore.

We thank the reviewer again for their careful reading and constructive feedback that has helped us identify areas where we can strengthen the paper's presentation and discussion. We incorporate these clarifications in the revised version.

We thank the reviewer for their thoughtful feedback and for highlighting the strengths of our work, including the soundness of our approach, the in-depth related work section, and the detailed ablation analysis. Below, we address the specific questions and concerns raised.

• Human-Designed Reward Function

  The term human-designed reward function refers to reward functions manually created by domain experts who implemented the environments used in our experiments. These experts designed the rewards to reflect task objectives based on their domain knowledge. Details on how each reward function (task reward and human-designed reward) is defined can be found in Appendix E (Reward Functions Definitions). We note that the plots always plot the task reward. When Human is indicated, it means “performance of a policy trained with the human-designed reward function on the task reward.”

• Clarification on Proof for Lemma D1

  We appreciate the reviewer pointing out that the proof for D1 could benefit from additional clarity. We have updated the proof of Lemma D1 with the following structure in the updated PDF.

  Base Case ($t=1$)

  At $t=1$, for all algorithms $i \in [K]$:

  • $\widehat{d}^i_1 = d_{\min}$ (by initialization)
  • $n_1^i = 1$ if $i$ is the first algorithm chosen, 0 otherwise
  • Therefore $n_1^i \leq n_1^{i_\star} + 1$ holds

  Inductive Step

  Inductive Hypothesis: Assume that for some $t \geq 1$:

  • $\widehat{d}^{i_\star}_{t-1} = d_{\min}$
  • $n_{t-1}^i \leq n_{t-1}^{i_\star} + 1$ for all $i \in [K]$

  We need to show these properties hold for $t$. Let $i_t = i_\star$. When $\mathcal{E}$ holds, the LHS of D$^3$RB's misspecification test satisfies [proof as is].

  Combining these inequalities shows the misspecification test will not trigger, thus:

  1. $\widehat{d}^{i_\star}_t$ remains at $d_{\min}$
  2. For all $i \in [K]$, $n_t^i \leq n_t^{i_\star} + 1$ continues to hold

  This finalizes the proof.

• Impact of Poorly Chosen Task Rewards

  Regarding the concern about analyzing the impact of poorly chosen task rewards: this is fundamentally a task specification problem [1]. In any reinforcement learning framework, a misspecified task reward — whether used with ORSO or another method — will inevitably lead to optimization towards unintended objectives. While this highlights a broader challenge in reward design, it is not unique to ORSO.

• Presentation

  We agree that Section 2 might be a bit redundant for RL experts. We provided this section to help non-experts with the necessary notation. We provide more a more thorough presentation of online model selection preliminaries in the appendix.

We hope these changes, with the strengths the reviewer already highlighted will increase your confidence in our work. If these revisions resolve your concerns, we would be grateful if you could consider raising your score to reflect the improvements. We appreciate your time and constructive feedback, which has helped us refine our submission.

References

[1] Agrawal, Pulkit. "The task specification problem." Conference on Robot Learning. PMLR, 2022.

Dear Reviewer,

We sincerely appreciate your thoughtful and positive feedback on our paper. Your insights were incredibly helpful in refining our work. We hope that our responses to your comments have addressed your concerns and clarified the contributions of our study.

If there are any remaining questions or areas where you feel further clarification is needed, we would be happy to provide additional details or engage in further discussion. We hope that our responses demonstrate the merits of the paper, and we kindly ask if you would consider revisiting your evaluation in light of these updates.

Thank you again for your time and effort in reviewing our submission. We greatly value your perspective and look forward to your final decision.

Best regards,

The Authors

• Q2

  Does the paper simply apply the D^3RB algorithm, or does it introduce theoretical improvements? This aspect is somewhat unclear.

  We use the D3RB algorithm, for which we present guarantees under different assumptions. The convergence result presented in our manuscript (dependence on true regret coefficient) is different from the one presented in the original D3RB paper (dependence on the monotonic regret coefficient). The intuition behind the guarantees provided in our paper is that the true regret coefficient dependence implies that even if the optimal reward function has a “slow start”, it can still be selected and trained on and will achieve similar regret to running only the optimal.

• Q3 + Q4

  As I understand it, there’s no guarantee that the optimal policy obtained with the selected reward aligns with the optimal policies for the base reward (i.e., No Design), correct?

  Could you clarify the evaluation metrics? The ideal benchmark should be based on the base reward, as that’s ultimately the reward we aim to optimize.

  Yes, while there is no guarantee that the policies learned with the selected shaping reward perfectly align with the optimal policy for the task reward (base reward / No Design), our approach explicitly selects shaping rewards that maximize the task reward, and our experiments show significant performance gains over the No Design baseline. The “selection reward” in our framework measures the task reward achieved by each candidate reward function, ensuring that the selected shaping reward leads to improvements in the original task reward. As a clarification, the task reward is always used as the evaluation metric to assess the quality of policies and their corresponding candidate rewards.

• Q5

  The terminology around “effective budget” seems confusing. Based on the proposed algorithms, the effective budget for environment interactions should be TN rather than T, since each iteration assumes running the algorithm for at least N steps to yield a final policy. Could you clarify this? This also seems to affect Figure 1—does preferred reward selection occur after N iterations or a single one? As I understand it, each reward would at-least have to be evaluated N times, hence making a minimum budget of KN, right?

  We appreciate the reviewer’s comment and apologize for any confusion caused by the terminology. In Algorithm 1, $T$ refers to the number of selection steps, and the total number of iterations is indeed $T \times N$, where $N$ is the number of training iterations a reward function is trained on before selecting another one. To clarify the notion of “budget” and the allocation of iterations, we provide a more structured explanation below:

  • Budget: In our context, the budget refers to the total number of PPO iterations allowed for training
  • Number of Selection Steps: $T$
  • Number of Training Iterations per Selection Step: $N$
  • Number of Iterations to Train Baselines: n_iters

  In our experiments, we fix the total budget to be a fixed multiple of n_iters (the number of iterations used to train the baselines, i.e., task reward function and human-designed reward function) for each task and ablate the choice of the multiple. That is, we have total_iterations_budget = n_iters x B = T x N, where we ablate the choice of $B$ with $B \in \{5, 10, 15\}$. We choose N = n_iters / 100, so that $T = 100 \times B$.

  We note that we can arbitrarily choose values like 1e6 iterations for the budget, but this alone does not provide insight into the relative cost compared to training with the baseline reward functions.

  Regarding Figure 1, it is a schematic illustration intended to highlight the trade-off between allocating budget to suboptimal versus optimal reward functions when the budget is limited. The figure depicts an extreme case where $N = `n\_iters`$ and $T < 2 \times `n\_iters`$. However, this situation does not occur in our experiments. For example, in the Ant task, we use $`n\_iters` = 1500$ and set $N = 15$.

We hope these clarifications address the concerns raised. If clarifications and additional experiments resolve your concerns, we would be grateful if you could consider raising your score to reflect the improvements.

References

[1] Cheng, Ching-An, Andrey Kolobov, and Adith Swaminathan. "Heuristic-guided reinforcement learning." Advances in Neural Information Processing Systems 34 (2021): 13550-13563.

[2] Zheng, Zeyu, Junhyuk Oh, and Satinder Singh. "On learning intrinsic rewards for policy gradient methods." Advances in Neural Information Processing Systems 31 (2018).

(continued response) LIRPG does not help if the extrinsic reward function is too sparse. We also test LIRPG on sparse-reward manipulation tasks, such as the Allegro Hand. However, LIRPG does not provide any improvement over the environmental reward as the reward function is “too sparse.” This agrees with the experimental results in Figure 7 of [1], where the authors show that increasing the sparsity of the feedback (every 10, 20, or 40 steps) can decrease the performance of LIRPG.

• E2

  Iterative resampling appears to be essential for obtaining high-quality reward functions, as it involves reinitializing policies and refining rewards over iterations. However, the paper lacks discussion on the resampling process's challenges, frequency, and impact on performance. Additionally, it is unclear if resampling is an integral part of ORSO or a separate process.

  The details of the iterative resampling process and its frequency are discussed in Appendix F.

• E3

  In the experiments, performance is evaluated against human-designed rewards, but the actual evaluation should ideally be based on the baseline reward. This raises questions about the metrics used for evaluation. In Figure 2, the upper bounds should correspond to No Design, as the objective should be to assess performance against the MDP’s base reward.

  We would like to clarify that the evaluation is always based on the original task reward. The human-designed reward functions are heavily engineered reward functions, such that policies trained on them will achieve high original task reward (indeed, human-designed reward functions are strict improvements over the original task rewards). This is the reason for the red line being higher than the gray line. the question Figure 2 is answering is “How long does it take to design reward functions that perform as well as human-designed reward functions when evaluated with the original task reward?” Directly optimizing for the “No Design” reward does not achieve optimal policies because these reward can be sparse of poorly shaped, leading to a particularly hard optimization problem.

• E4

  The reward generation process seems to require access to code-level details of the MDP, which may not be feasible in cases where the environment is not code-based. Discussion of this limitation would improve transparency regarding the method’s applicability.

  This is correct. The generator used in our work requires a simulator for the environment and its code, which is common in robot learning, the application analyzed in the experiment in this paper. As mentioned above, the generation can be seen as both part of ORSO or not. If one is working with a non-code based environment, multiple reward functions can still be instantiated and ORSO can be applied to such pre-defined set of reward functions.

Questions

• Q1

  ORSO functions only as a selection algorithm, correct? Reward generation isn’t part of the algorithm itself?

  As state above, the two components can be decoupled. When using the iterative improvement step, the generation can be seen as part of ORSO. Instead, if one already has a set of candidate rewards, ORSO can be used on the fixed set directly.

We thank the reviewer for the comments and suggestions. We clarify the weaknesses and questions below.

Writing

The reward generation can be seen as both part of the ORSO or not. If one has a set of generated reward functions, then we can use ORSO to simply jointly select a performant reward function and train a policy with it. On the other hand, if there is no reward function provided beforehand, one can also see the generation as part of ORSO. Algorithm 4 provides the full pseudo-code with generation and iterative improvement of the reward function, where a new set of reward function is generated when the most selected reward function has been used to train for a maximum number of iterations.

Complexity

It is true that we need to maintain K separate policies. In our setting, the policies being simple MLPs, it does not create much overhead. We note that the naive approach (given a set of reward functions, train a policy until convergence for each reward function and then pick the best policy) still needs to instantiate K policies.

Performance Guarantees

How do you ensure consistency in performance when there is no guarantee that the proposed objective aligns with the base reward function?

Our performance guarantees are with respect to the set of reward functions used for selection. While potential reward shaping could be applied in ORSO to ensure optimal policy invariance guarantees, we did not incorporate this because empirical evidence suggests that potential shaping often does not improve performance substantially in practice (as shown in [1]). Specifically, applying potential shaping to human-designed rewards frequently leads to suboptimal outcomes. Instead, we focus on an online selection process that chooses the reward function to train on based on its performance on the base reward function, ensuring that the chosen reward function maximizes the base reward. Empirically, we observe that with a sufficiently diverse set of candidate rewards, it is likely that one will perform similarly to or better than a human-designed reward when evaluated using the original task reward.

Experiments

• E1

  The paper does not compare with established reward shaping methods, such as those by Ng et al. (1999), Zou et al. (2019), Zheng et al. (2018), Sorg et al. (2010), and Gupta et al. (2023). Including these comparisons would strengthen the experimental evaluation.

  We note that methods like [2] are complementary to ORSO, meaning that one can use ORSO to propose shaped reward functions and then apply other shaping methods on top to further improve the performance of such reward functions.

  We chose to compare ORSO-designed reward functions with LIRPG because it is one of the most widely adopted methods for reward design in reinforcement learning. We provide experimental results with LIRPG on the Ant task. LIRPG jointly trains a policy and learns an intrinsic shaping reward, such that the intrinsic reward leads to higher extrinsic reward.

  In each experiment, we use the task reward function, the human-designed reward function, and the reward function selected by ORSO as the extrinsic reward for LIRPG, respectively. We run each experiment for 5 random seeds and report the mean base environmental reward achieved by training with each method, along with 95% confidence intervals.

  Method	Without LIRPG	With LIRPG
  No Design	4.67 +/- 0.84	5.73 +/- 1.08
  Human	9.84 +/- 0.30	10.02 +/- 0.30 (*)
  ORSO	11.09 +/- 0.68	11.51 +/- 0.45 (*)

  • LIRPG cannot design better rewards than ORSO: When LIRPG is applied to the task reward, it results in lower performance compared to using the human-designed or ORSO-selected rewards.
  • LIRPG as a complementary method: We emphasize that LIRPG can complement ORSO. By applying LIRPG to reward functions selected by ORSO (which have already undergone shaping), LIRPG may help learn an additional function that aids the agent in optimizing ORSO-designed rewards.

  The bolded entries have undergone one stage of reward shaping, while the entries in the table above marked with (*) have undergone two stages of reward design. First a performant reward function was obtained from a human designed or ORSO (both outperforming LIRPG on the task reward). Then, given the good quality of the reward, we show that we can apply LIRPG on such reward functions to some marginal improvement. We only provide such results for completeness. We note that the evaluation of each policy is done with respect to the task reward function (No Design).