ORSO: Accelerating Reward Design via Online Reward Selection and Policy Optimization
Authors: Chen Bo Calvin Zhang
Zhang-Wei Hong
Aldo Pacchiano
Pulkit Agrawal
Venue: ICLR 2025 Poster (2025)
Keywords: Reinforcement Learning
Reward Design
Reward Selection
Primary area: reinforcement learning
TL;DR: We present ORSO, a method for efficiently selecting shaping rewards in reinforcement learning.

Abstract: Reward shaping is critical in reinforcement learning (RL), particularly for complex tasks where sparse rewards can hinder learning. However, choosing effective shaping rewards from a set of reward functions in a computationally efficient manner remains an open challenge. We propose Online Reward Selection and Policy Optimization (ORSO), a novel approach that frames the selection of shaping reward function as an online model selection problem. ORSO automatically identifies performant shaping reward functions without human intervention with provable regret guarantees. We demonstrate ORSO's effectiveness across various continuous control tasks. Compared to prior approaches, ORSO significantly reduces the amount of data required to evaluate a shaping reward function, resulting in superior data efficiency and a significant reduction in computational time (up to 8×). ORSO consistently identifies high-quality reward functions outperforming prior methods by more than 50% and on average identifies policies as performant as the ones learned using manually engineered reward functions by domain experts.

Published as a conference paper at ICLR 2025
ORSO: ACCELERATING REWARD DESIGN VIA ONLINE REWARD SELECTION AND POLICY OPTIMIZATION
Chen Bo Calvin Zhang* Zhang-Wet Hong', Aldo Pacchiano Pulkit Agrawal Improbable AT Lab, Massachusetts Institute of Technology Boston University@
ETH Zurich
Broad Institute of MIT and Harvard*
ABSTRACT
Reward shaping is critical in reinforcement learning (RL), particularly for com- plex tasks where sparse rewards can hinder learning. However, choosing effective shaping rewards from set of reward functions in a computationally efficient man- ner remains an open challenge. We propose Online Reward Selection and Policy Optimization (ORSO), novel approach that frames the selection of shaping re- ward function as an online model selection problem. ORSO automatically identi- fies performant shaping reward functions without human intervention with prov- able regret guarantees. We demonstrate ORSO's 's effectiveness across various con- tinuous control tasks. Compared to prior approaches, ORSO significantly reduces the amount of data required to evaluate shaping reward function, resulting in su- perior data efficiency and a sigmificant reduction computational time (up to 8 8x). ORSO consistently identifies high-quality reward functions outperforming prior methods by more than 50% and on average identifies policies as performant as the ones learned using manually engineered reward functions by domain experts. Code is available at hhttt::/// //git/gtttt wiigtih.b...... com/ Improbable Tatppobball-A/orreeeeee
INTRODUCTION
& Barto (2018) they guide the learning of successful policies. In many real-world scenarios, the ultimate objective involves maximizing long-term rewards that are not immediately available (Vecerík et al. 2017 Rengarajan et al.) Vasan et al.), making optimization challenging. To address this, practitioners often introduce
Reward functions are crucial in reinforcement learning
shaping rewards (Margolis& Agrawal 2022] Liu et al. [024] MMhmood al. 2018 Ng al. [999] Park et al. 2024) to provide additional guidance during training. Instead of directly maximizing the task reward (R), it therefore common for the RL algorithm to maximize an easier-to-optimize shaped reward function F in the hope of obtaining high performance as measured by the task reward, R. While shaping rewards are designed to guide the agent to complete a task, maximizing them does not necessarily solve the task. For instance, an agent tasked with finding an exit (i.e.. longer-term reward in the future) may be provided with shaping rewards to avoid obstacles. However, the task's success ultimately depends
reaching the exit, not just avoiding obstacles. If poorly designed, the shaped rewards F' can mislead the agent because prioritizing the maximization of F may not maximize R (Chen al. 2022 Agrawall, 2021; [Hddfeld-Menell et al. 2017 Ng al. 1999). leading to training failure or suboptimal performance.
Designing effective shaping reward functions F is therefore challenging and time-consuming. It requires multiple iterations of training agents with different shaping rewards, evaluating their per- formance on the task reward Rt and refining F accordingly. This process is inefficient due to the lengthy training runs and because the performance measured early in training may be misleading, making it challenging quickly iterate over different shaping rewards.
To address this challenge, we propose treating the selection of the shaping reward function as an exploration-exploiatii problem and solving using provably efficient online decision-making al- gorithms similar to those in multi-armed bandits (Auer et al. 2002 Auer 2002) and model selection
(Agarwal al. 2017 Pacchiano et al. 2020 Dann et al. 2024 Foster et al. 2019 Lee al. 202T).
*Correspondence cbczhang@mi t. edu, pul kitaggmi edu.

---

Published as a conference paper at ICLR 2025
In this setup, each shaping reward function F corresponds to shaping reward function is J(x),, ). the expected cumulative reward of the policy N' under the task reward R. We aim to efficiently select the shaping reward function that leads to the best policy un- der the task reward R. To achieve this, we allocate computational resources strategically, exploring each reward function sufficiently to evaluate its potential while avoiding excessive exploration so that enough computational budget is left to optimize the policy using the best reward function.
model. The utility of
This approach presents unique challenges. Unlike standard multi-armed bandit settings with sta- tionary reward distributions, the utility of a shaping reward function in our case is nonstationary. As the agent explores new parts of the state space during training, the task reward distribution changes. Additionally, we must balance exploration and exploitation of a set of shaping reward functions to efficiently allocate training time among these shaping rewards without committing too early to high-performing options or wasting time on low- low-performing ones.
We introduce Online Reward Selection and Policy Optimization (ORSO), an algorithm that effi ciently selects the best shaping reward function from set of candidate shaping reward functions that maximize the task performance. ORSO provides regret guarantees and adaptively allocates training time to each shaping reward based on model selection algorithm at each step. Our empirical re- sults across various continuous control tasks using the Isaac Gym simulator (Makoviychuk et al.) 2021) demonstrate that ORSO identifies performant reward functions with 56% better performance on average compared to methods like EUREKA (Ma et al.] 2024) within a fixed interaction bud- get. Moreover, ORSO consistently selects reward functions that are comparable to, and sometimes surpass, those designed by domain experts, all while using up to 8x less compute.
2 PRELIMINARIES
Reinforcement Learning (RL) In RL, the objective is to learn a policy for an agent (e.g., a robot) that maximizes the expected cumulative reward during the interaction with the environment. The in- teraction between the agent and the environment is formulated as a Markov decision process (MDP) (Puterman 2014). M = (S, A. P, r, Y,PD), where the S and A denote state and action spaces, re- spectively, S x A + As is the state transition dynamics, r S x A + AR denotes the reward function, ? E [0, 1) the discount factor, and Po E As is the initial state distribution. At each timestep E N of interaction, the agent selects an action ag π( 8x) based on its policy π, receives a (possibly) stochastic reward rt ~ r(st,a)) az), and transitions to the next state $141 P(- 8t, 0z) according to the transition dynamics. Here, r is the task reward, also referred to as extrinsic reward (Chen et al., 2022). RL algorithms aim to find policy x that maximizes the discounted cumulative reward, i.e.,
DC
so po, at a( (s), re ~ ((s, 8141 ~ P( 8c, at)
π" E arg max ((T)
E
Σ
Y'r
(I)
Notation We denote 인 a reinforcement learning algorithm that takes MDP M (S, A, P.r, 7, an initial policy mo as input and returns policy nT (M, No).)
P,r,7, Po), a reward function f, a number of interaction steps with the environment N, and
METHOD: REWARD DESIGN AS SEQUENTIAL DECISION MAKING
As previously stated, the reward function encodes the task objective but can be difficult to optimize using RL methods directly. We formalize the reward design problem as follows.
Definition 3.1 (Reward Design). Given M and 2, the reward design problem aims to find a re- ward function ff S x A + Az. with f E R, the space of reward functions, such that the policy TO (M) achieves an expected return under the task reward r. such that T (x!) z
maxPeR J(T'') (T²).
While this could be achieved by running the algorithm I on every possible reward function r' E R, this is computationally prohibitive. The reward space R can be extremely large, and attempting to
As denotes the set of probability distributions over S.
2

---

Published as a conference paper at ICLR 2025
π
fi
f2
Too Exploitative
Too Explorative
Just Right
Task Reward
0.0
0.5
1.0 0.0
0.5
1.0
0.0
0.5
1.0
Interaction Budget
Figure 1: Comparison of three reward selection strategies given fixed interaction budget. The green dashed line represents the task reward of the optimal policy, π The red and blue curves show the task rewards for policies trained with reward functions f and f² respectiively. The yellow curve, my, tracks the maximum of the red and blue curves. Left: This selection strategy is overly exploitative, greedily selecting the reward function that seems perform best early but plateaus later in training. Center: On the other hand, this strategy continuously switched between f and f² exploring the suboptimal reward function too much. Right: The ideal strategy initially explore f and 1 but quickly latches onto the better reward function.
optimize over all possible rewards is impractical, especially when the available interaction budget is constrained.
To make the problem tractable, we assume access to a finite set of candidate shaping reward func- tions R* {f'...... ..... f G(R), where G is distribution that contains at least one near-optimal reward function and a budget of interactions B. If the budget does not allow training on each f RRK, need allocate resources gather useful informa- tion about the quality of each candidate, while simultancously optimizing the most promising ones. This introduces a fundamental exploration-exploiaatoon tradeoff. On the one hand, we must explore various rewards to identify high performers; on the other, we need to exploit promising candidates train performant policies.
the set of reward functions,
Figure shows simple example with two reward functions, f' and f² and three selection strate- gies. The selection strategies on the left and center are too exploitative and too explorative re- spectively. The exploitative selection strategy greedily spends the interaction budget on the reward function that performs best early in training, neglecting the potential of f On the other hand, the selection strategy in the center equally explores both reward functions, even when one is clearly preferred. The exploration strategy on the right initially explores both reward functions but quickly latches onto the best one and spends the remaining interaction budget on the better reward function. The suboptimality gap at iteration t of training can be measured via the regret of the best policy so far defined as reg(() = [(*)) I (mt), where मं arg max [TT).. The choice of nद reflects practical preference, as are more interested in the best-performing solution available at given point, rather than the most recent update. For instance, in deploying a robotic running policy, one would select the fastest policy observed thus far assuming the objective is as possible.
fast
A further discussion of the online model selection problem can be found in Appendix B
3.1 ORSO: ONLINE REWARD SELECTION AND POLICY OPTIMIZATION
In this section, introduce ORSO (Online Reward Selection and Optimization), novel approach to efficiently and effectively select shaping reward functions for reinforcement learning. Our method operates in two phases: (1) reward generation and (2) online reward selection and policy optimiza- tion.
Reward Generation In the first phase of ORSO, we generate a set of candidate reward functions RK for the online selection phase. Given MDP M (S, A. P.r, Po) and stochastic generator G, we sample a set of K reward function candidates, R K = {f ..... fk Vi E [K], f S
AR. I G), from G during the reward design phase. The generator G can be any distribution
3

---

Published as a conference paper at ICLR 2025
over the reward function space R. For instance, if the set of possible reward functions is given by a linear combination of two reward components C1, C2. which are functions of the current state and action, such that r(s, a) W W/ (s, a) + (2C2(s, a), then the generator G can be represented by the means and variances of two normal distributions, one for each weight W1, 102
Online Reward Selection and Policy Optimization Our algorithm for online reward selection and policy optimization is described in Algorithm [ On a high level, the algorithm proceeds as RL algorithm A and reward generator G,
follows. Given an MDP M = (S. A. P.r. (op)))))) Po), sample set of K reward functions R ~ and initialize K distinct policies n² ;.... , At step I of the reward selection process, the algorithm selects learner it [K] according
selection
strategy. We then run algorithm 21, updating the policy corresponding to reward function it to obtain r². Policy x' simultaneously evaluated under the task reward function and the necessary variables for the model selection algorithm are then updated (e.g., reward estimates, reward function visitation counts, and confidence intervals). The algorithm returns the reward function f and the corresponding policy π that performs the best under the task reward function r. We discuss the implementation details in Section 5
Algorithm ORSO: Online Reward Selection and Policy Optimization
Require: MDP M = AS,A, p.r. Po). algorithm 21 generator G
1: Sample K reward functions R (f ,...,,kk pk) ~
2: Initialize K policies {T' {T'....,TT)
3: for 1rrl=1 1,2, ...,. T do
4: Select an model i, E [K] according selection strategy
5: Update ,² p4 (M,
6: Evaluate J(*") f- Eval(r*t)
7: Update variables (e.g., reward estimates and confidence intervals)
8: end for
9: return 17 arg [ T(r')
Choice of Selection Algorithm While ORSO is general algorithm that can employ any selection method to pick the reward function to train on, the performance depends on the choice of algorithm.
For instance, using simple selection method like e-greedy introduces an element of exploration by occasionally selecting a random reward function (with probability =), but it risks overcommiting to scemingly promising reward function early This lead to suboptimal performance if the chosen reward function causes the task performance to plateau in the long run. However, greedier methods, such e-greedy, achieve lower regret if they commit to the optimal reward function early in the process. These methods are particularly effective when early performance signals are strong indicators of long-term success.
However, if initial performance is not a reliable predictor of future outcomes, these greedy ap- proaches may struggle, as they risk prematurely locking onto suboptimal rewards. In contrast, more exploratory algorithms like the exponential-weight algorithm for exploration and exploita- tion (Exp3) (Auer et al. 2002) maintain a broader search, potentially discovering better rewards in the long run, especially in environments where early signals are less informative. We empirically validate different choices of selection algorithms in Section
THEORETICAL GUARANTEES
In this section, we provide regret guarantees for ORSO with the Doubling Data-Driven Regret Bal- ancing (D²RB) algorithm by Dann et al. (024)). A discussion of the intuition behind the D algorithm and the full pseudo-code for ORSO with DORB is provided in Appendix
We first introduce some useful definitions for our analysis.
Definition 4.1 (Definition 2.1 from Dann et al. (2024)). The regret scale of learner after being played times is Σi= reg(n(a)) where reg rog(zi,)) (T/)) -[x*)) - I (1((1) and i (M, E) in the
Vi.
reward design problem.
4

---

Published as a conference paper at ICLR 2025
For positive constant dmin 0. the regret coefficient of learner i after being played for rounds is d() max{dmin (miin Ei=1 reg( (eg) Vt]. That is, die dman is the smallest number such that the incurred regret is bounded as Σi=1 reg( ( di dio)V
Dann et al. (2024) use V as this is the most commonly targeted regret rate in stochastic settings. regret guarantees is that the internal state of all suboptimal reward functions is only updated up to a point where the regret equals that of the best policy so far.
The main Idea underlying
We assume there exists learner that monotonically dominates every other learner.
Assumption 4.2. There a learner i, such that at all time steps, its expected sum of rewards dominates any other learner, i.e, u() 2 o/oy for all [K].t E and such that average
expected rewards are increasing. ie., "id S 21 d/i 2 di for all E N.
E. N. This is equivalent to saying that di+n
Assumption 4.2 guarantees that the cumulative expected reward of the optimal learner i, is always at least as large as the cumulative expected reward of any other learner and that its average performance increases monotonically.
Following the notation of Dann et al. 2024), we refer to the event that the confidence intervals for the reward estimator are valid as E
Definition 4.3 (Definition 8.1 from Dann et al. (2024)). We define the event & as the event in which for all rounds E N and learners [K] the following inequalities hold
ni In K Klnni
K Klnnj
- S sey nt
for the algorithm parameter 5 (0, 1) and universal constant O, where ni = -
1 i).
Then we can refine Lemma 9.3 from Dann et al. (2024) in the case where Assumption 4.2 holds.
Lemma 4.4. Under event & and Assumption 4.2 with probability 1 - 8, the regret of all learners i bounded all rounds as
n²
KlnT
reg(T(n)) S 6dp v nrj + 1 + 5ey (nz + 1) t=1
(3)
8
where di d'
(nit))
We provide the proof for Lemma 4.4 Appendix D Lemma 4.4 implies that when Assumption holds, the regrets are perfectly balanced. This is in stark contrast with the regret guarantees of Dann et al. (0024) that prove the DdRB algorithm's 's overall regret to scale as (dz;) 2 VT where de- = maxege di Instead, our results above depend not on the monotonic regret coefficients di but on the true regret coefficients di. Even if learner i, has slow start (and therefore large di;), as long as monotonicity holds and the i, learner recovers in the later stages of learning, our results show that RB will achieve regret guarantee comparable with running learner in isolation.
5 PRACTICAL IMPLEMENTATION AND EXPERIMENTAL RESULTS
In this section, we present a practical implementatior several continuous control tasks. We study the ability of ORSO design effective reward functions with varying budget constraints. We also study how different sample sizes, K, of the set of reward functions R influence the performance of ORSO and compare different selection algorithms.
2 of ORSO and its experimental results on
This section is structured as follows. First, we present the experimental setup, including the environ- ments and baselines, and the practical consideration of the reward generator G and the algorithms used in the online reward selection phase. Then, we present the main results and ablate our design choices. Further experimental results can be found Appendix H
Thhe code for ORSO is available at wthttps://githbb.eeo htt.:/b.ccommmmmmbbbbbee www.mppbbbblo...mm e-
5

---

Published as a conference paper at ICLR 2025
5.1 EXPERIMENTAL SETUP
Environments and RL Algorithm We evaluate ORSO on a set of continuous control tasks us- ing the Isaac Gym simulator (Makoviychuk et al. 202T Specifically, we consider the following tasks: CARTPOLE and BALLBALANCE, which are relatively simple; two locomotion tasks, ANT and HUMNAOID, which have dense but unshaped task rewards for instance, the agent rewarded for running fast, but the reward function lacks terms to encourage upright posture or smooth move- ment; and two complex manipulation tasks, ALLE and SHADOWHAND, which feature sparse task reward functions.
Our policies are trained using the proximal policy optimization (PPO) algorithm (Schulman et al.) 2017), with our implementation built on CleanRL (Huang et al. 2022 We chose PPO because Makoviychuk al. (202T) provide hyperparameters, which we use, that enable it to perform well on these tasks when using the human-engineered reward functions.
5.1.1 BASELINES
In our experiments, we consider three baselines. We analyze the performance of policies trained using each reward function detailed below. We evaluate the reward function selection efficiency of ORSO compared to more naive selection strategies.
No Design (Task Reward with No Shaping) We train the agent with the task reward function r for each MDP. These reward functions can be sparse (for manipulation) or unshaped (for locomotion). We use the same reward definitions as prior work (Ma et al., 2024). which we report in Appendix E
Human We consider the human- eennnnerr reward functions for each task provided by (Makoviy- chuk et al. 202T). We note that these constructed such that training PPO with the given hyperpa- rameters yields a performant policy with respect to the task reward function. The function definitions reported in Appendix E
Naive Selection A naive selection strategy involves sampling a set of reward functions and training policies on each reward to convergence. While this approach simple and widely used (Ma al., 2024), it can be inefficient because it uniformly explores each reward function for fixed number of iterations, regardless of the task performance.
5.1.2 IMPLEMENTATION
Reward Generation Similarly to recent works on reward design, which demonstrate that LLMs
can generate effective reward functions for training agents (Park et al. 2024 Ma et al., 2024 Xie
al.. 2024, Yu al. (024),, we follow this paradigm by using GPT-4 (Achiam et al. (023) to
avoid manually designing reward function components. The language model is prompted to generate reward function code in Python based on some minimal environment code describing the observation space and useful class variables. We employ prompts similar to those used by Ma al. (022)). Since the exact prompts are not the primary focus of our work, we do not detail them here; instead, we refer readers our codebase for further details on the prompt construction.
While the LLM produces seemingly good code, this does not guarantee that the sampled code is bug-free and runnable. In OrSO, we employ a simple rejection sampling technique to construct sets of only valid reward functions with high probability. We also note that the initial set of generated re- ward functions ORSO might not contain an effective reward function To address this limitation, we introduce a mechanism for improving the reward function set through iterative resampling and in-context evolution of new sets RK We provide more details on the rejection sampling mechanism and the iterative refinement process Appendix F
Online Reward Selection Algorithms We evaluate multiple reward selection algorithms from the multi-armed bandit and online model selection literature: explore-then-commit (ETC), e-greedy (EG), upper confidence bound (UCB) (uurr 2002), exponential-weight algorithm for exploration
An effective reward function is one that leads high performance with respect to the task reward when used for training.

---

Published as a conference paper at ICLR 2025
and exploitation (Exp3) (Auer al. )002), and doubling data-driven regret balancing (D²RB) (Dann jet al., 2024). We provide the pseudocode and the hyperparameters used for each selection algorithm Appendix G For every environment, we set the number of iterations N in Algorithm [ used to train the policy before we select a different reward function to N = n iters/ /100, where iters rers the number of iterations used to train the baselines, i.e., we perform least 100 iterations of online reward selection before the iterative resampling.
5.2 RESULTS
In this section, we present the experimental results of ORSO. We evaluate ORSO's ability to effi ciently select reward functions with varying budget constraints and reward function set size K. We consider interaction budgets B E (5, 10, 15) x n nitters and sample sizes K E {4, (4,8, 16).
Human
No Design
Naive
ORSO (D²RB)
1.25
Task Reward
Task Reward
+56%
1.0
1.00
0.75
0.5
0.50
0.0
Cartpole
Balance
Ant
Humanoid
Allegro
Shadow
10
15
Interaction Budget
Normalized task rewards averaged over interaction budgets and seeds. ORSO sistently matches or surpasses human-designed reward functions. Right: Normalized task reward function of interaction budget, averaged across tasks. ORSO scales effectively with increased budgets, achieving a 56% higher task reward than the naive strategy at the highest budget. Vertical bars in the plots indicate standard errors.
Figure 2: Left:
ORSO Surpasses Human-Designed Reward Functions Figure 2 (left) illustrates the average performance of ORSO compared to human- reward functions, the task reward function, and the naive selection strategy across different tasks. We observe that ORSO consistently matches or exceeds human-designed rewards, particularly in more complex environments. For each task, the results are averaged over interaction budgets, reward function set sizes and with seed per configuration, totaling 27 runs. The full breakdown is reported in Appendix H
ORSO Achieves 56% Higher Task Reward Figure 2 (right) shows how task performance scales with the interaction budget. While both ORSO and naive selection benefit from larger budgets, ORSO consistently superior and surpasses human-der -esigned rewards when B 10. Moreover, ORSO achieves 56% higher reward than the naive strategy the highest budget level. This demon- strates that ORSO can more effectively make use additional interactions with the environment, allocating more compute to better reward functions. Detailed per-task and per-budget results reported in Appendix
ORSO Can Reach Human Performance with Fewer GPUs One advantage of the naive selection strategy is that it can be easily parallelized on many GPUs. Figure 3 reports the estimated time required to achieve the same performance as policies trained with human-designed reward functions as a function the number of GPUs used. Notably, ORSO performs at a comparable speed to the naive selection strategy even when the latter leverages up to 8 GPUs in parallel, achieving similar performance within the same timeframe. should be noted that the plotted time is an approximation based on the time needed to complete one iteration of PPO for each task, where one iteration consists of collecting a batch of trajectories, updating the policy, and the value function. We report the results for all interaction budgets in the Appendix H

---

Published as a conference paper at ICLR 2025
Naive
ORSO (D'RB)
to Human Perforaancs (h)
Ant (B
Time Human Performance (h)
Alligro Hand 15)
Performance (h)
Shadow Hand (B 15)
40
ORSO (DPRB)
ORSO [DPR8)
ORS0 (DRRB)
30
80
20
10
Number
GPUs
Number
Figure 3: Median time to human-level performance as a function of number of parallel GPUs. Policies trained with ORSO can achieve the same performance as policies trained with the human- engineered reward functions with up to 8x fewer GPUs.
5.3 ABLATION STUDY
Choice of Selection Algorithm In Figure 4 compare different selection algorithms for ORSO. We find that D'RB performs best on average, consistently outperforming other algorithms. followed closely by Exp3. These algorithms allow ORSO balance exploration and exploitation effectively, leading to superior performance compared to more greedy approaches like UCB, ETC, and EG. Interestingly, even simpler strategies like EG and ETC substantially outperform the naive strategy, which highlights the importance of properly balancing exploration and exploitation for efficient reward selection. By framing reward design an petpioratioonxpplittattie problem, we demonstrate that even basic strategies offer considerable gains over static, inefficient methods.
Design
Naive
ETC
Human
EG
UCB
D'RB
Task Reward
1.0
1.0
0.5
0.5
0.0
3
6
9
12
15
DRRB
Exp3
UCB
ETC
EG
Naive
Interaction Budget
Figure 4: Comparison of different rewards selection algorithms for ORSO. Left: Number of itera- tions necessary for human-level performance. Right: Average normalized task reward for different selection algorithms. We provide
granular breakdown in Appendix H
Regret of Different Selection Algorithms To further quantify ORSO's performance, analyze its regret with respect to human-engineered reward functions This formulation motivated by two key considerations. First, lack access to the true optimal policy with respect to the task reward function ** Second, the PPO hyperparameters used in our experiments were specifically tuned for the human-engineereed reward function, making the policy trained with it reasonable proxy for the optimal policy. Regret provides a useful metric for understanding how much performance is lost due suboptimal reward selection high-quality reward functions, reducing the number of iterations wasted on poorly performing ones. Figure 5 shows the normalized regret for different selection algorithms. Notably, ORSO's regret can become negative, indicating that it finds reward functions that outperform the human human-designed designed ones.
time. Lower regret indicates that method quickly identifies
*The normalized regret with respect to the human-engincered reward functions defined Homer ((*))
8

---

Published as a conference paper at ICLR 2025
Natre
Expa
B 5
B 5 10
- 15
Nomaltzed Regret
1,00
1.0
0.75
0.50
0.25
0.0
0.0
Intoraction Budget
Interaction Budget
Interaction Budget
Figure 5: Regret of different selection algorithms with varying budgets. We recall that budget B indicates that the ORSO has been run for B x niteers iterations.
ORSO is Effective with Large Reward Sets Previous experiments considered at most 16 reward functions once, raising the question of whether ORSO remains effective when the candidate set is significantly larger. A larger set could pose challenges: excessive exploration might leave in- sufficient time for learning, while premature commitment could lead suboptimal performance. To investigate this, we evaluate ORSO with different selection algorithms on the ANT task, using interaction budget of
and reward sets of sizes E {48, 96].
Uniform
EG
ETC
UCB
Exp3
D
Human
K
96
Task Reward
10
Task Reward
10
5
0
9
12
12
15
Intercation Budget
Intercation Budget
Figure 6: Comparison of multiple selection algorithms for the ANT task with a high number of reward function candidates. The shaded areas represent standard errors over 5 different seeds. The order of the reward functions is randomized for each seed.
In this setting - with a fixed budget and reward function se algorithms that commit to a selec- tion earlier can allocate more iterations to training the chosen reward functions. On the other hand, exploring for longer may allow us to find the optimal reward function but potentially leave insufficient time for training.
As illustrated Figure 6 DRRB consistently identifies and selects an effective reward function from the set. In contrast, "greedier" methods such e-greedy, sxplore-then-comeee and UCB depend more on the stochasticity of training and on average do not surpass human-designed reward functions. Exp3 and uniform exploration, while more exploratory, may overemphasize exploration at the expense of exploiting promising reward functions, leading to suboptimal performance. We report the task reward of each reward function in Table to validate that ORSO with DºRB truly selects the best reward functions.
RELATED WORK
Traditionally, researchers manually specified reward components and tuned their coefficients (Ng et al., 1999; Margolis & Agrawal 2022 Liu et al.) 2024), a method that often requires significant domain expertise and involves numerous iterations of trial and error.
Recent work has increasingly explored the potential of foundation models in reward design. Ap- proaches like L2R (Yu al. 2023) leverage large language models to generate reward functions by
In this experiment, we do not perform iterative improvement. That is, the set of reward functions is fixed over the entire training.

---

Published as a conference paper at ICLR 2025
converting natural language descriptions into code using predefined reward API primitives, though this requires notable effort in manual template design. Other works such as EUREKA (Ma et al.) 2024) and Tex:2Reward (Xie et al., 2024) use language models to generate dense reward functions based on task descriptions and environment codes.
Foundation models have also been directly employed reward models. Researchers have used cosine similarity of CLIP embeddings (Rocamonde et al. 2024), vision language models for trajec- tory preference labeling (Wang al., (024), and large language models for constructing preference datasets and intrinsic reward modeling (Klissarov et al. 2024 K Kwon et al. 2023
Non-stationary scenarios have been extensively explored in the bandit literature, with the restless bandit model (Whittle 1988 Weber & Weiss) 1990) being a prominent example. In this model, each arm evolves according to a potentially unknown Markov decision process (MDP). Various solution approaches have been developed for this setting, including those leveraging the Whittle Index (Gittins et al., (0TT). However, the restless bandit framework does not fully capture the problem considered in this work. Unlike setting where each base learner corresponds to fixed MDP, the problem of reward selection involves base learners that when chosen advance their internal state never to revisit it. This forms the basis of the online model selection literature that has addressed the challenge of dynamically choosing suitable models in sequential decision makinng environments
Agarwal al. 2017 Foster et al. 2019. Pacchiano et al. 2020 Lee et al. 202
A more comprehensive review of related work is provided in Appendix A
CONCLUSION
In this paper, we introduce ORSO, novel approach for reward design in reinforcement learning that significantly accelerates the design of shaped reward functions. We find that even simple strate- gies like s-greedy and ssploretheencoomme suggesting that reward design can be effectively framed as sequential decision problem. ORSO reduces both time and computational costs by more than half compared to earlier methods, making reward design accessible to a wider range of researchers. What once required a larger amount of computational resources can not be done on a single desktop a reasonable time. By formalizing the reward design problem and providing a theoretical analysis of ORSO's 's regret when using the D²RB algorithm, we also contribute to the theoretical understanding of reward design in RL.
yield substantial improvements over naive selection,
Looking ahead, our work opens several promising directions for future research, including the devel- opment of more sophisticated exploration strategies tailored for reward design, and the application of our approach to more complex, real-world RL problems.
7.1 LIMITATIONS AND FUTURE WORK
Our experiments explored up to 16 reward functions with resampling of the reward function set and up to 96 without resampling. We find that using reward functions with as much interaction budget as possible yields the best results. We leave the study of even larger reward function sets for future work.
A key limitation of ORSO is its reliance on predefined task reward, which is typically straightfor- ward to construct for simpler tasks but can be challenging for more complex ones or for tasks that include qualitative element to them, e.g., making a quadruped walk with a "nice" gait. Future work could explore eliminating the need for such hand-crafted task rewards by leveraging techniques that translate natural language instructions directly into evaluators, potentially using rision-language models, similarly to Wang et al. (2024): Rocamonde et al. (2024). Another alternative is to use preference data to learn task reward model (Christiano et al. 2017 Zhang & Ramponi 2023) and use the latter as a signal for the model selection algorithm.
Finally, in principle, ORSO could be on multiple GPUs in parallel, with results from different runs aggregated for improved efficiency. Investigating parallelization strategies and their impact on reward selection remains an interesting direction for future study.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We thank members of the Improbable AI Lab for helpful discussions and feedback. We are grate- ful MIT Supercloud and the Lincoln Laboratory Supercomputing Center for providing HPC re- sources. This research was supported in part by Hyundai Motor Company. Quanta Computer Inc., an AWS MLRA research grant, ARO MURI under Grant Number W91 13- 1-0277, DARPA Ma- chine Common Sense Program, ARO MURI under Grant Number W911NF-21-1-OD MURI under Grant Number
and ONR The views and conclusions contained in this docu- ment those of the authors and should not be interpreted representing the official policies, either expressed or implied, of the Army Research Office or the United States Air Force or the U.S. Gov- emment. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes, notwithstanding any copyright notation herein.
1800014-2-1-220
AUTHOR CONTRIBUTIONS
Led the project, wrote the manuscript, ideated the method, im- plemented the algorithm, and conducted the experiments.
Chen Bo Calvin Zhang:
Zhang-Wei Hong: Provided guidance on the types of experiments to run and assisted with the implementation of saving and loading the simulator state in Isaac Gym. Drafted the introduction and advised on writing.
Aldo Pacchiano: Contributed to the theoretical aspects of the work, specifically the model selection part, including the development and proof of key concepts.
Pulkit Agrawal: Oversaw the project, assisted with positioning the paper, and contributed to the writing and presentation of the results.
REFERENCES
Pieter Abheel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 1, 2004.
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. GPT-4 technical report. arXiv preprint arXiv:2303. 08774, 2023.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling band of bandit algorithms. Conference on Learning Theory, pp. 12-38. PMLR, 2017.
Pulkit Agrawal. The task specification problem. In 5th Annual Conference Robot Learn- net wtw.://wwwwe///ouummmmmmm
ing, Blue Sky Submission Track, 2021. URL
cBdnThrYkV7
Peter Auer. Using confidence bounds for exploitation-expllration trade-offs. Journal of Machine Learning Research, 3(Nov):397-42) 2002.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM journal on computing. 32(1):48-77, 2002.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
Eric R Chen, Zhang- Wei Hong, Joni Pajarinen, and Pulkit Agrawal. Redeeming intrinsic re- wards via constrained policy optimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL .ne// httr//orummmmmmmm -iiimmddd=333332
Q
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 sys- fems, 30, 2017.
11

---

Published as a conference paper at ICLR 2025
Chris Dann, Claudio Gentile, and Aldo Pacchiano. Data-driven online model selection with regret guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 1531-1539.
PMLR, 2024.
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
John Gittins, Kevin Glazebrook, and Richard Weber. Multi-armed bandit allocation indices. John
Wiley & Sons, 2011.
Dylan Hadfield-Mennll, Smitha Milli, Pieter Abbeel, Stuart J Russell, and Anca Dragan. Inverse reward design. Advances in neural information processing systems, 30, 2017.
Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye, Jeff Braga, Dipam Chakraborty, Ki- nal Mchta, and JoAGo GM AraAšjo. Cleanrl: High-quality single-file implementations of deep reinforcement learning algorithms. Journal of Machine Learning Research, 23(274):1-18, 2022.
Martin Klissarov, Pierluca D' D'Oro, Shagun Sodhani, Roberta Raileanu, Pierre-Luc Bacon, Pascal Vincent, Amy Zhang, and Mikael Henaff. Motif: Intrinsic motivation from artificial intelligence feedback. In The Twelfth International Conference on Learning Representations, 2024. URL
htttps://openreview net Forumn?1==nBBBIecDBB
Minae Kwon, Sang Michael Xie, Kalesha Bullard, and Dorsa Sadigh. Reward design with language models. In The Eleventh International Conference on Learning Representations, 2023. URL
http://///ppeeeeeeewweee net htte://ooouum11111uuitiiit
Jonathan Lee, Aldo Pacchiano, Vidya Muthukumar, Weihao Kong, and Emma Brunskill. Online model selection for reinforcement learning with function approximation. International Con- ference Artificial Intelligence and Statistics, pp. 3340-3348. PMLR, 2021.
Minghuan Liu, Zixuan Chen, Xuxin Cheng. Yandong Ji, Ri-Zhao Qiu, Ruihan Yang, and Xiaolong Wang. Visual whole-body control for legged loco-manipulation. In 8th Annual Conference on net/forum? Id=cT2N3p1 ACE.
Robot Learning, 2024. URL http:tttts///peeeeetee
Yecheng Jason Ma, William Liang, Guanzhi Wang, De-An Huang, Osbert Bastani, Dinesh Jayara- man, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Eureka: Human-level reward design via coding large language models. In The Twelfth International Conference on Learning Representa- tions, 2024. URL
httrrriwwweeeeeeeeeee tnne/fforumts d- Lo
A Rupam Mahmood, Dmytro Korenkevych, Gautham Vasan, William Ma, and James Bergstra. Benchmarking reinforeement learning algorithms on real-world robots. In Conference on robot learning, pp. 561-591. PMLR, 2018.
Viktor Makoviychuk, Lukasz Wawrzyniak, Yunrong Guo, Michelle Lu, Kier Storey, Miles Macklin, David Hoeller, Nikita Rudin, Arthur Allshire, Ankur Handa, and Gavriel State. Isaac gym: High performance GPU based physics simulation for robot learning. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL forum? fooormmmddffffttoooooooo YQJ
htttp:://ppenreview net. :twp://wwwwwweeeeeoeeuuuemmma
Gabriel B. Margolis and Pulkit Agrawal. Walk these ways: Tuning robot control for generalization
with multiplicity of behavior. 6th Annual Conference on Robot Learning. 2022. URL https: 7/openzeviex nwt/ 5==52c5
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations:
Theory and application to reward shaping. In leml, volume 99, pp. 278-287, 1999.
Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems, Advances Neural Information Processing Systems, 33: 00110001013333 2020.
Younghyo Park, Gabriel B. Margoliss and Pulkit Agrawal. Position: Automatic environment shaping is the next frontier in RL. In Forty-first International Conference on Machine Learning. 2024. URL h hnttpss//opperevee
net/ ddd Uyy rN44
12

---

Published as a conference paper at ICLR 2025
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Desik Rengarajan, Gargi Vaidya, Akshay Sarvesh, Dileep Kalathil, and Srinivas Shakkottai. Rein- forcement learning with sparse rewards using guidance from offline demonstration. In Interna- tional Conference on Learning Representations.
Juan Rocamonde, Victoriano Montesinos, Elvis Nava, Ethan Perez, and David Lindner. Vision- language models are zero-shot reward models for reinforcement learning. In The Twelfth Interna- lional Conference Learming Representations, 2024. URL https: fttttp:://ppeneview..t net/
Forum?id=NM 12
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint
2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Gautham Vasan, Yan Wang, Fahim Shahriar, James Bergstra, Martin Jägersand, and Rupam Mah- mood. Revisiting sparse rewards for goal-reaching reinforcement learning. In Reinforcement Learning Conference.
Mel Vecerik, Todd Hester, Jonathan Scholz, Fumin Wang, Olivier Pietquin, Bilal Piot, Nico- las Heess, Thomas Rothörl, Thomas Lampe, and Martin Riedmiller. Leveraging demonstra- tions for deep reinforcement learning on robotics problems with sparse rewards. arXiv preprint (00.::7770088/77 2017.
Yufei Wang. Zhanyi Sun, Jesse Zhang, Zhou Xian, Erdem Biyik, David Held, and Zackory Erickson. RL-VLM-f: Reinforcement learning from vision language foundation model feedback. In Forty- first International Conference on Machine Learning, 2024. URL https:::p..........p. opwneeview.......e
net / d
Richard R Weber and Gideon Weiss. On an index policy for restless bandits. Journal of applied probability, 27( 648, 1990.
Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of applied proba- bility, 25(A):287-298, 1988.
Tianbao Xie, Siheng Zhao, Chen Henry Wu, Yitao Liu, Qian Luo, Victor Zhong, Yanchao Yang, and Tao Yu. Text2reward: Reward shaping with language models for reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024. URL https:
/popnreview. http:///oooommmiotttt3.3...
Chao Yu, Hong Lu, Jiaxuan Gao, Qixin Tan, Xinting Yang, Yu Wang, Yi Wu, and Eugene Vinit- sky. Few-shot in-context preference learning using large language models. arXiv preprint arXiv:2410.1727 17233, 2024.
Wenhao Yu. Nimrod Gileadi, Chuyuan Fu, Sean Kirmani, Kuang-Huet Lee, Montserrat Gonzalez Arenas, Hao-Tien Lewis Chiang, Tom Erez, Leonard Hasenclever, Jan Humplik, Brian Ichter, Ted Xiao, Peng Xu, Andy Zeng, Tingnan Zhang, Nicolas Heess, Dorsa Sadigh, Jie Tan, Yuval Tassa, and Fei Xia. Language rewards for robotic skill synthesis. In 7th Annual Conference on Robot Learning, 2023. URL
net/ www.mfrrummmmm Pid= Sgidd---PPyyyyy.MM...
Chen Bo Calvin Zhang and Giorgia Ramponi. HIP-RL: Hallucinated inputs for preference- based reinforcement learning in continuous domains. In ICML 2023 Workshop The Many Facets of Preference-Based Learning, 2023. URL https://openrev///
net fortmm?
id=PRm1 KxRrRI
Brian Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, al. Maximum entropy inverse Chicago, IL, USA, 2008
reinforcement learning. In Aaai, volume 8, pp.
13

---

Published as a conference paper at ICLR 2025
A RELATED WORK
Reward Design for RI. Designing effective reward functions for reinforcement learning has been a long-standing challenge. Several approaches have been proposed tackle it.
Traditionally, researchers manually specify reward components and tune their coefficients (Ng et al,, 1999 Margolis & Agrawal, 2022 Liu al. 2024). This method often demands significant domain expertise and can be highly resource- inteurceinteesive, involving numerous iterations of trial and error in designing reward functions, training policies, and adjusting reward parameters.
Another approach is to learn reward functions from expert demonstrations via methods like appren- ticeship learning (Abbeel & Ng. 2004) and maximum entropy inverse RL (Ziebart al. 2008). While these methods can capture complex behaviors, they often rely on high-quality demonstrations and may struggle in environments where such data scarce or noisy.
Preferences can also be used to learn reward functions (Zhang & Ramponi, 2023 Christiano et al., 2017]. This approach involves collecting feedback the form of preferences between different trajectories, which are then used to infer a reward function that aligns with the desired behavior: This method is particularly useful in scenarios where it is difficult to explicitly define a reward function or obtain expert demonstrations, it allows for more intuitive and accessible feedback from users.
Foundation Models and Reward Functions Recent work has explored the use of large lan- guage/vision models (LL/VMs) to aid in the reward design process. L2R (Yu et al. 22023) leverages large language models generate reward functions for RL tasks by first creating natural language "motion description" and then converting it into code using predefined reward API primitives. While innovative, L2R has notable limitations: it requires significant manual effort in designing templates and primitives and is constrained by the latter. EUREKA (Ma et al.) 2024) and Text2Reward (Xie)
jet al. 2024) use LLMs to generate dense reward functions for RL given the task description in natural language and the environment code.
Foundation models have also been directly used as reward models. Rocamonde et al. (2024) uses the cosine similarity of CLIP embeddings of language instructions and renderings of the state as a state- only reward model. Similarly, Wang et al. (2024) automatically generates reward functions for RL using vision language model label pairs of trajectories with preference, given task description. Motif (Klissarov et al.) 2024) first constructs a pair-wise preferences dataset using a large language model (LLM), learns preference-based intrinsic reward model with the Bradley-Terry (Bradley & Terry 1952 model, and then uses this reward model to train a reinforcement learning agent. K won
al. (022) uses similar approach, where an LLM used during training to evaluate an RL policy, given a few examples of successful behavior or a description of the desired behavior.
Online Model Selection The problem of model selection in sequential decision-making environ- ments has gained significant attention in recent years (Agarwal et al.) 2017; Foster et al. 2019 Pac- chiano et al. 2020 Lee et al.) 202I). This area of research addresses the challenge of dynamically choosing the most suitable model or algorithm from a set of candidates while learning.
Agarwal et al. (017) introduced CORRAL, a method to combine multiple bandit algorithms a master algorithm. Foster et al. (2019) proposed model selection guarantees for linear contextual bandits. Pacchiano et al. (2020) extend the CORRAL algorithm and propose Stochastic CORRAL. Caaree-Coomtt-llmmmnnnn
Lastly. Lee et al. (2021) ) propose
(ECE), algorithm for model selec- tion in RL with function approximation. A common requirement across all these approaches is the need know the regret guarantees of the base algorithms.
Our work is closely related to Dann et al. (024). which removes the need for known regret guaran- tees and instead uses realized regret bounds for the base learners. In our setting, the set of models comprises the reward functions set and their corresponding policies.
14

---

Published as a conference paper at ICLR 2025
B ONLINE MODEL SELECTION
In this section, we introduce the model selection problem and some necessary notation modified from Dann al. (2024) for our analysis.
We consider a general sequential decision decision-making process consisting of a meta learner interacting with an environment over 7 E rounds via a set of base learners. At each round of interaction f = 1,2, ..... T, the meta learner selects a base learner b, and after executing by. the environment returns a model selection reward Rg E R. The objective of the meta learner is to scquentially choose base learners bi...., br maximize the expected cumulative sum of model selection rewards, i.e.,
-= Rs We denote by e E[R bj the expected model selection reward, given that the learner chooses base learner 6, i.e., the value of base learner b. The total model selection reward accumulated by the algorithm over rounds is denoted by ur = Ei= v". The objective is to minimize the cumulative regret after 7 rounds of interaction,
max E
E
T
Reg(T) Σ reg(b;)
Σ
o
(4)
where e* is the value of the optimal base learner.
In our setting, each base learner corresponds to reward function / and its associated policy m ie., b = (f. T). In this case, choosing to execute base learner b means training with algorithm 2 starting from checkpoint и and using RL reward function f. The model selection reward R is then the evaluation of the trained policy under the task reward r, i.e,, J(T)). The regret base learner b can therefore be written as reg(b) =² - [(x)) [(r), where x is the optimal policy. Therefore the objective becomes minimizing
Reg (T) = (T') (m.)
(5)
The policy associated with base learner i at round / is denoted by mf. so that -.- We denote the number base learner i has been played up round t as nł Ei= fif = i) and the total cumulative reward for learner i as un = Σt= 1 fie = i} u where we use u b to highlight that the policy associated with base learner changes used for RL does not. We denote the internal clock for each base learner with a subscript (k) such that m(ey is the policy of learner when chosen for the k-th time, i.e., m. = ((n))*
Notation
time, but the reward function
We note important difference between the online model selection problem and the multi-armed bandit (MAB) problem. In model selection, the meta learner interacts with an environment over T rounds, selecting from K base learners. In each round t, the meta learner picks a base learner E [K] (index of base learner chosen at step t) and follows its policy, updating the base learner's s state with new data. Unlike MAB problems, where mean rewards are stationary, the mean rewards here are non-stationary due to the stateful nature of base learners (the base learners are learning as they see more data), making the design of effective model selection algorithms challenging.
The cumulative regret Equation (5) is an upper bound for the cunulative regret with respect to the best so far.
Remark 1.
Proof. This straightforward to see. Let us first note that, by definition, for all t E [T]. we have
T (mT) > J (TT)
(6)
Therefore,
Σ I -
< Σ J (T^) (Tt),
(7)
t=1
concluding the proof.
15

---

Published as a conference paper at ICLR 2025
C ORSO WITH DOUBLING DATA-DRIVEN REGRET BALANCING
Here, we present the complete ORSO algorithm with Doubling Data-Driven Regret Balancing (D²RB) as the model selection algorithm.
DORB is built upon the idea of regrel balancing, which aims to optimize the performance of multiple models by balancing their respective regrets. Imagine weighing two models balance scale where the "weight" corresponds to their regret; the goal is to keep the regret of both models balanced. This approach ensures that models with higher regret rates selected less frequeetly, while those with lower regret rates are favored.
Concretely, regret balancing involves associating each learner with candidate regret bound. The model selection algorithm then competes against the regret bound of the best-performing learner among those that are well-specified meaning their realized regret stays within their candidate bounds. Traditional approaches often rely on known expected regret bounds. In contrast, D focuses on realized regret, allowing the model selection algorithm to compete based on the actual regret outcomes of each base learner. The algorithm dynamically adjusts the regret bounds in data-driven manner, adapting to the realized regret of the best- rest-performing learner over time. This approach overcomes the limitation of needing known regret bounds, which are often unavailable for complex problems.
DCBB maintains three estimators for each base learner: regret coefficients d. average rewards 0j/ni and balancing potentials of. At each step t. D²RB selects the base learner with the lower balancing potential and executes it. Then it performs the misspecification test in Equation (8) to check if
the estimated regret coefficient for base learner i consistent with the observed data. If the test
triggers, i.e., the d' is too small, then the algorithm doubles it. Lastly, DORB sets the balancing potential of to di' Vn.
In
K In m
K la n
+ to
max
(8)
n
n
12
]K[K]
16

---

Published as a conference paper at ICLR 2025
Algorithm 2 ORSO with DORB
Require: MDP M (S, P.r, po). algorithm 21, generator G, minimum regret coefficients
dmin, failure probability
1: Sample K reward functions RK ,f. G
2: Initialize K policies { { .r!......"". ... {}}
3: Initialize balancing potentials of dmin for all E [K]
4: Initialize regret coefficients di dmin for add i E [K]
5: Initialize counts nij- 0 and total values op 0 for all E [K]
6: for t = 1, ,, do
7: Select a base learner it E [K] E arg (e of
8: Update n + 2 MM,
9:
Evaluate R₂ J (T') + Eval(T"
// Update necessary variables
Set n n 02 8; 1. di dr 1. and Φi41 of for all E [K] {it}
12:
Update statistics for current learner n = nL + and " 4 + Rr
13:
Perform misspecification test
In In
In m
Ut
8
max
Thg
74
JE(K]
17
14:
if test is triggered then
Double the regret coefficient d. 2d
16: else
Keep the regret coefficient unchanged dit di 18: end if
Update the balancing potential 0't + ti Vnz
19:
20:
end for
// Best policy and reward function under the task reward
22:
return ni; ft arg max T(T))
17

---

Published as a conference paper at ICLR 2025
D PROOF OF LEMMA 4.4
In this section, present the complete proof of Lemma We will start by showing that when Assumption h.2 then with probability at least the estimated regret coefficient of learner i, will never double provided that dmin 2 where is the confidence multiplier in D*RB.
Lemma D.1 (Non-doubling regret coefficient). When & holds, and algorithm D RB is in use
dmii and
ny I nz +1 for all i [K]
(10)
for all t E.
Proof. In order show this result it is sufficient to show that when & holds, algorithm i, does not undergo any doubling event. Doubling of the regret coefficients only happens when the misspecifi- cation test triggers for algorithm
We will show this by induction.
Base Case (t = 1) At = 1, for all algorithms i [K]:
dain (by initialization)
ni if is the first algorithm chosen, 0 otherwise
Therefore ni n + holds
Inductive Step Inductive hypothesis: assume that for some 1:
di dmin
n n + for all i E [K]
We need show these properties hold for t. Let is i.. When holds, the left-hand side (LHS) of D misspecification test satisfies
n4
In
Inn
mic
di
n4
In
K In
c
+ c
(ie i.)
nt
n2
14
T1.
nie"
n2
di 1
W4
(event E)
T4p"
u
dmin nig
(11)
where (i) holds because by the induction hypothesis di dmin- We will now show that n 2 n
for all E [K]. Since by the inductive hypothesis d; dmia for all s the potential 0i = dmii v n for all e L.
For E [K] let ((i), be the last time before time algorithm i was played. For i + i, have t(i) < t. Since i was selected at time t(i). by definition of the potentials,
Bio Vo-iviite - duii / 2 d 110001/1/000 2 duain / n(
so that n 2 - Since both ni- - and nē n we conclude that
n 2 nt.
18

---

Published as a conference paper at ICLR 2025
We now turn attention to the right-hand side (RHS) of D²RB's misspecificatioo test. When & holds, the RHS of D²RB's misspecification test satisfies,
K In m!
In
max j T
max ]E(K]
11
max JE[K]
(6)
(12)
nit"
where inequalities (i) and (ii) hold because of Assumption we conclude the misspecification test of algorithm DCRB will not trigger. Thus, di remains at dmin and for all i E [K], m S n.- + continues to hold. This finalizes the proof.
4.2 Combining inequalities 11 and 12
We are now ready to prove the regret bound on the base learners given in Lemma
Lemma 4.4. Under event & and Assumption 4.2 with probability 1 8, the regret of all learners is bounded in all rounds T as
n
Khn
(o)( I 6dlz / nij + +1+ 50y (n + 1) In 8
(3)
1=1
where dip d' (mit))
Proof. Consider a fixed base learner i and time horizon T, and let S T be the last round where i was played but the misspecification test did not trigger. If no such round exists, then set / 0. By
di. times between / and T. Corollary 9.1 in Dann et al. 2024), can be played at most 1 + loga Tam where dy maxegr dz. Thus,
dz
reg ((K)
reg
T(m)) + + loga
dmin
Am
If f = 0, then the desired statement holds. Thus, it remains to bound the first term in the RHS above when t 0. Since = & and the test did not trigger we have, for any base learner j with n/ > 0,
n
reg ((()s)
nip"
ui
(definition of regret)
1=1
n²p"
n 2n +
n/.
3 ui u.
11
n// 0*
+ n
n2
Σ reg (((3))
+
n
(definition of regret)
n!!
mm
72
n
<
d3
+
(definition of regret rate)
n²
nx
di
n2
+
19

---

Published as a conference paper at ICLR 2025
We now focus on j i. and use the balancing condition in Lemma 9.2 in Dann et al. (2024) to bound the first factor V n². n/////.. This condition gives that Φ'+1 I 36 Since both n/ 0 and
ni O, we have Φi+1 - de V ni and oif1 = di. V Vnj. Thus, we get
n
12
< 3,
(13)
where the last inequality holds because of Lemma D.1 and because di z dmii- Plugging this back into the expression above and setting j = i., we have
ai
Σ reg
(((s))
ni u ui. I 3d;-" v Vnj +
ny
To bound the last two terms, we use the fact that the misspecification test did not trigger in round Therefore,
K In mt
c//
ni
In
(event E)
n
+
In
K n
C Vnn m4
Klnnj K Klnng -20 ni In
20 nt In
Vv
n
n2
K Klnnk
at /n.
c/
In
(test not triggered)
8
8
Rearranging terms and plugging this expression in the bound above gives
reg( (x)) & 3d; v mt + V
nf n
o
nf
K Khnn
+ 20 n In
K In n
+ d: V
un
K Knnn 8
< 3d;"" v ni + 30 nł In
+ +20 ni In
+ de. ni (Equation 13
K Klnnt
Klnnf
nf In < 3d v nt 3e
20 In
+ 3d; v m 8
(Equation 13
3d. /nt 3d; Vnt + 50 ni In Klnt
(max(()) mt) S
8
K lnd
$ 3d v vn; + 3dmii / ni + +50/ nt In
(Lemma D.1
8
Finally, Lemma D.I also implics ni $ ni + 1 and since dmii S di,
reg (T())) & Gett V ni: + 1 + 50
50y(ng (nt
1)
K In
The statement follows by setting t T.
20

---

The task reward functions are the Published as a conference paper at ICLR 2025
E REWARD FUNCTIONS DEFINITIONS
In this section, we present the definition of the human-engineered reward functions and the task reward functions used to evaluate the generated reward Table T same the ones used in Ma et al. (0224.
Table 1: Task reward functions definitions.
ENVIRONMENT
Task REWARD
CARTPOLE
(agent is alive]
BALLBALANCE
(agent
(agent is alive]
ANT
current.distanee previous current.distance previous.distance
HUMNAOID
ALLEGROHAND
Σ (ootation.distance 0.1] Σ 1
SHADOWHAND
< 0.1]
The human-designed reward functions from (Makoviychuk al. 2021) are
CARTPOLE
r= (1.0 (1.0 po pole_angle 0.01 -ccar_caeee 0.005 (pole.vel))
The reward is additionally multiplied by -2.0 if |cart.pos| reset_dist and multi- plied by 2.0 once again if pole_angle >>
BBLLLBALANCE
r resare x speed 1 ball.dist ball.
where
ball aill_disto = bblll.ppp polllppo_.ue x2 + ball.pos. + Shall.pos.. - 0.7)3,
where 0.7 the desired height above the ground, and
ball.speed = ||ball.veocity|l
ANT and HUMNAOID
r Tppprggress Talive X 1 storso.heighh
termination.heihht) + Fupright
+ +heading + Tertort + Fact + Taot
+death X herrshheigght tterminationhheight,,
where
Pprogress current.potentiall
Fupright (torso.up.vector, up-vector) > 0.93
1.0.
if norm norm-angle to target 2 0.8
Theading heading.vector x tomanglett..arget otherwise
0.8
Σ
||actions]]
Tact
N
Teffort
actions; x normallieedmooorr.ttrenggg x dof.velocity,
Pearget Peorsolly
potential
dt
21

---

Published as a conference paper at ICLR 2025
ALL and SHADOWHAND
r r= -1reist Trot 2 x 10 1 act
where
Faist llaa Pearget l12
Tzot rosttist + 0.1
Tact = Σ ||action|]]
rot_dist = 2 x arcsin (max (1, 1l (lazgetll2)
where q is the quaternion and is its conjugate.
22

---

Published as a conference paper at ICLR 2025
E. REWARD FUNCTIONS SELECTED BY ORSO
We report the best reward function selected by ORSO below. The reward functions are reported as is, with only the formatting of comments and spacing changed to fit within the box.
Reward Function for Allegro Hand
def compute Beree__pp_______________ [pt__rewrrd(((
object_ rot: torch. Tensor, tensrr, goal_rot: torch. Tensor, shacors_handddo___pss torch. shados_hand_doo__eel: terch, actions: torch.
Tuple(terch. Tensor, Dict (str, torch. Tensor]
Configurable parameters
dist_ action_penalty_salle float (0.05)
lit___rewrdd_scala float (2.0)
success_toleranc float (0 (0.05)
reach_geal_ bonus = float (20.0)
Compute distance to goal rotation using Quaternion distance gddif object_ goal_ros dist to goal = norch. (g diff, dim=-1)
Rotation distance reward (scaled)
rot_reward worch.exp wawpcheeeppoistt_oaaaaeaaaaa
dist_to_gcal)
Action penalty (scaled)
action_penalty torch. sum (acticns< dim=-1)
action_penalty_sccale action_ aetion_penalty_scale acticn_penalty
Check if the goal has been reached within the tolerance success mask = dist_to_goal < success_tolerance goal_bonus bonus (
success_mask, torch.tensor (reach_sge basecchgool_beuuie device-dist_to_geall _t_.stttt__gll.eeiceeee.. torch. (0.0, device-dist_to_goal.deee
Total reward roward rot_roward action__eenalty_ccalld + gonus
Dictionary of individual reward components rexard__coponents
"rot_ "rot_reward"; rot_reward, "act paction_penaltye act a a to__penalty_scaall "goal_ pcnus_' goal_booo bonus
return reward, reward_components
23

---

Published as a conference paper at ICLR 2025
Reward Function for Ant
def
compute_gpt_reeeee
root_ torch. Tensor,
actions: torch, Tensor, dt: float
Tupleltorch, Tensor, Diet,str, torch. Tensor] Device
device
ixtract necessary information from the root states
velocity root soot_statesl:: 7:10| vvx, vy, vzl torso possttpositionn root_ pot__sttess:: 0:3] [px, py, pz]
Forward velocity along the x-axis forward_velocity velocityl:, 0]
# Reward component: scaled forward velocity Retain existing scaling factor forward_reward forward_velocityy 2.0
Fenalty for large actions
# (to avoid unnecessary jerky movements)
action_penalty torch. sum (actions*** dim=-1) Increased scaling factor for more impact aation_penaltyyscalle
action_penalty 1.0
Desired height range (e.g., 0.45 to 0.55)
Sarget_height corch.tensor (0.5, device=device) height_ciff tbrch.abs
2] target_height)
Adjusted temperature parameter to increase contribution malance_temperatee = 0.1
Retain existing scaling
bal balance_reward torch.exp httggggg.....fffaaaaaaaaaeeeeeaa
5.0
Additional penalty for deviaticn from target angle (to encourage running straight)
target angle torch.tensor (0.0, device=device)
Assuming index yaw angle angle_diff torch, abs (root_states(;; 5] target_angle) angle_penalty -torch. (-angle_diff / balance_temperatuue
Survival bonus encourage lenger episode lengths
Reduced overall magnitude survival_bonus torch.ones like (forward * 0.5
Total reward caleulation
reward forward_reward bawande_reward
angle_penalty action__enalty_scal
survival_bonus
Dicticnary individual reward components for debugging
reward cwwp:nentscccccccecce [
Forward_rewardd forward forward_reward,
reward,
act aetilon_penalty_scalee" saccoon_eenalty_ccalee
balance_roward': balance_reward,
angle_penalty': angle_penalty,
survivall_onus' survival_benis
return reward, sewaoe__o
24

---

Published as a conference paper at ICLR 2025
Reward Function for Ball Balance
def compute gpt gpt_reward((
compute_gpt_rewte ball_ sall_positions: corch.Tensor, ball_linvelis torch.Tensor. Tuple Tensor,, Dict torch. Tensor] ***
Compute the reward for keeping the ball on the table top without falling.
Args:
ball positions: torch. Tensor of shape (N, 3) giving the positions of the balls.
ball_ linvels: Tonsor of shape (N, 3) giving the linear velocities of the balls.
Returns:
reward: the total reward as torch,Tensor of shape (N,) reward_componentsr dictionary with individual reward components.
***
Assume lawl_apssstltaaaaaaa positionss, 21 is the height 2 of the ball. target_height torch. tensor (0.5,
s device)
Reward for staying close to the target height height_diff torch.abs poall_positions:; 2] target_height) # Decreased temperature for larger impact height_ = torch. tensso device-ball_positeeeee beight_reward torch.exp (-heightt_iif height_temp)
Reward for having low linear velocity ball__invels_oom Increased scale for more significant, impact
warch.linalg.neee (bal dim=1)
vel_scale torch.tensor (10.0, device-ball_positinee deviic vel_reware txrch.exp (-ball 1elii_iill___or_
vel_scale)
Penalty for being far from the center (in xy-plane) center xy tersort 01, device=ball wow.tticsssiiiissssoommm devicce xy_diff torch. tow.h..inalg.oomm. ball_positions :2] center_xy, dim-1
Some threshold distance xy_threshold torch. tensor (0.5, device=ball htwpebaall-osstiionndeddeee xy xy_penalty torch.where
xy_diff > xy_threshold,
-torch.exp diff tyrtheehh)
torch.tensor (0.0, device=ball posttinal .ev.i..i.ddeee.
Combine the rewards
total reward height__ieeaeeeeeeeeeeeeeeeeeeee reward vel reward xy xy_petly
Compile individual components into dictionary reward_compenents
"height_reward"; height_reward,
"vel_roward"; vel_reward, "xy_penalty"; xy_penalty
return totaldr rewarc_components
25

---

Published as a conference paper at ICLR 2025
Reward Function for Cartpole
def compute gpt_rrewat reward dof_pos: torch. Tensor, dof_vel: torch.Tensor
Tuple[torch. Tensor, Dict (str, torch. Tensor]]
Extract pole angle and angular velocity pole_angle dof dof_posl_ [;, 1] polc_ang_vel = dof_vell;, 1]
Reward components
Reward for keeping the pole upright
upright_bonus_ 10.0 upright_bonus torch.exp (-upright_ botnuuss_t_ (pole_anglexx2))
Penalty pole's angular velccity encourage stability)
ang vel penalty_t 0.1 ang ang_vel_ peyalty = torch.exp (-ang_ve__e_eeeeeee vel tttranngteeepppalyytttttt t* (pole ang_vel++2]]
Sum the rewards and penaltics
reward upright_bonus ang_vel_penalty
# Create a dictionary of individual reward components for
debugging or further analysis
reward__copooents uupright_bonus: upright_
ung_vel_penaltyy
return reward, reward_components
26

---

Published as a conference paper at ICLR 2025
Reward Function for Humanoid
def
root_ torch. Tensor,
targets: torch, Tensor, dt: float
Tupleltorch, Tensor, Diet torch. Tensor]
Extract relevant components velocity - root_states 7:10]
Vector pointing torso positoppssiionnnee rost poo__statess;, 0:31 to target = targets torso_ position to lo_target[;, 21
target
Normalize to_target get direction direction_to__argeet = torch. nn. functional. www.aoomaiiaa...a lizc to_target,
p-2.0,
dim=-1
Project velocity onto directien to target to get velocity component in the right direction velocitt__towrrs_targ torch.sum( velocity * direction_to_targer, dim=-l, keepdim=True
Reward for moving towards the target quickly reward = wolocityttowrrdeaaare.. squparr squeeze
Apply exponential transformation encourage higher speeds
temp_apee 0.1
reward d = torch. earcheexp(speed rtwppppeedeewwaaddeeeeeeeeeeeeee
-1.0
Combine rewards (single component in this case)
total_reward speed_rewar__rranfforr
Reward components in dicticnary form
rewards "aspeedrreward" teweedrrrrarddtaafffroooe
return total_ total_reward, rewards
27

---

Published as a conference paper at ICLR 2025
Reward Function for Shadow Hand
def
object_rot: tessr, goal_rot:
actions: torch. Tensor, success_tolerance: float, reach_goal float, rot_rexard_scale: flost, action__enalty__ane float Tuple[torch.Ienss:
Dict [str, terch. lensor]]
# Rotation Distance Reward with adjusted scaling rot dist = corrch.norm(o0) (object. rot goal_rot, dim=-1)
New temperature parameter for rotational reward rot_reward_temp 3.0
rot_reward torch.cxp
Goal Achievement Bonus
goal_reached rot_dist success_tolsrance
bonus reach_goal__oe
goal_reached, float ()
Action Penalty with increased scale increasing the action penalty scale increased_aps 2.0 action_penalty_scaale
action_penalty torch. sum (acticns442, dim=-1) increased_aps
Intermediate Reward for making progress towards retating to goal
intern_ stteemmsstees__ee____ 0.5
untermodiate__sccpe_roearr tor.hh..ggg.ooo..ddaa//mmmeeeeee
Fenalty for large deviations from goal orientation deviation_scale 0.2
deviation_penalty rot_dist deviation_scale
Calculate total reward
total_ reward = reward goal_ beauu +
intermediate steps
action penalty
deviation_penalty
Create a dictionary of individual rewards for monitcring
reward dict =
roo_reward"; rot_reward,
goal_bonus"; goal_bonus,
Incermcllac_stoop_eevwr.dr
"action "action_penalty": action_penalty;
"deviation_penalty"" ceviation_penalle
return total_reward rewaré_ćict
28

---

Published as a conference paper at ICLR 2025
F IMPLEMENTATION DETAILS
Rejection Sampling While the LLM produces seemingly good code, this does not guarantce that
the sampled code is bug-free and runnable. In OrSO, employ simple rejection sampling tech-
nique to construct sets of only valid reward functions with high probability, such that reward func- tions that cannot be compiled produce #oo or NaN values are discarded.
Given criteria & to be satisfied, our rejection sampling scheme repeats the steps in Algorithm 3 have sampled the desired number, K, of valid reward functions.
until
Algorithm Rejection Sampling in ORSO
1: Sample a candidate reward function f ~
2: if (ff) is satisfied then
3: Add f to the set of candidate reward functions
4: else
5: Reject reward function f
6: end if
In our practical implementation, checking if criteria ø are satisfied consists of instantiating envi- romment with the generated reward function, running a random policy on it, and checking the values produced by the reward function. If the environment cannot be instantiated or if the values returned by the reward function are +00 or NaN, the reward function is rejected. It is worth making two im- portant observations. First, this is much computationally cheaper than instantiating the environment for training because one does not need to initialize large neural networks and can use fewer parallel environments than the number necessary for training. Moreover, we note that the rejection sampling mechanism only guarantees a higher probability of a valid reward function code as the policy used evaluate the function is random and the optimization process used during the training of an RL algorithm could still induce undesirable values.
Iterative Improvement of the Reward Function Set In the initial phase of ORSO, the algorithm generates set of candidate reward functions RK for the online reward selection and policy opti- mization step. While this approach effective if R.K contains an effective reward function, any selection process will fail to achieve a high task reward if the set does not contain good reward function. To address this limitation, we introduce a mechanism for improving the reward function set through iterative resampling and in-context evolution. This is similar to Ma et al. (2024), how- ever, we introduce some important changes to prevent the in-context evolution from overfitting to initially suboptimal reward functions.
Resampling is triggered when at least one reward function has been used to train a policy for the number of iterations specified in the environment configuration if all the reward functions in the set incurred too large regret compared to the previous best policy if the algorithm has undergone least one resampling step.
There are several strategies for resampling reward functions, each with its trade-offs. The simplest approach is to sample new reward functions from scratch, using the same generator G that was used in the initial phase. However, this method may not provide significant improvement, as it essentially restarts the search process without leveraging the information gained from the previous iterations of training.
more sophisticated approach is to greedily in-context evolve the reward function from the best- performing candidate so far as is done in Ma et al. (2024). This involves making incremental ad- justments to the reward function that has shown the most promise, potentially moving it closer to an optimal reward function. However, while this greedy strategy can lead to improvements, it also has the risk of overfitting to an initially suboptimal reward function if, for example, the initial set does not contain effective reward functions.
To mitigate the risk of overfitting, we introduce a simple strategy that allows the algorithm to be more exploratory. Specifically,
combine greedy evolution with random sampling: half of the reward functions are evolved in context from the best-performing candidate, while the other half is sampled from scratch. This approach allows the algorithm to explore new regions of the reward
29

---

Published as a conference paper at ICLR 2025
function space while still exploiting the knowledge gained from previous iterations. We provide the full pseudo-code for ORSO with rejection sampling and iterative improvement in Algorithm
Algorithm 4 ORSO with Rejection Sampling and Iterative Improvement
Require: MDP M AS,A, P. r: 7: Po). algorithm 2. generator G, budget T, threshold n_iters Sample K valid reward functions Rx {f ...... ff...f using Algorithm
2: Initialize policies {T',,... π
3: Initialize selection counts N 0f
4: Set 1
5: while / < do
6: Select model
[K] according to selection strategy Update n + 2 pi (M,N, x²)
7:
8:
Evaluate [(**) ) + Eval(*"))
9:
Update selection counts: N N +1
10:
Update variables (e.g., reward estimates and confidence intervals)
if N 2 n_iters or regret w.r.t. previous best too high then
12:
Resample R G (half in-context evolution, half from scratch)
13:
Sample a new set of reward functions Rx {f ....... using rejection sampling
14:
Reset policies { "K,,,,KK) Reset selection counts N {O..... 0}
15:
end
17:
t ++1+1
18:
end while
19:
return nे f+ arg m [(T')
30

---

Published as a conference paper at ICLR 2025
G SELECTION ALGORITHMS AND HYPERPARAMETERS
In this section, we present the pseudocode for all reward selection algorithms used in our experi- ments with their associated hyperparameters in Table
Algorithm 5 g-Greedy
Require: Number of arms K, total time T, exploration probability Initialize counts ni- = and total values inj = for E [K]
2: for = .,..., do
3:
Select arm
4 arg max, (0/ /n/),, Uniform ([K]),
with probability with probability
4: Play arm i, and observe reward 7.
5: Set nž = n1-1, and Wi أi_ 1 for all i E [K] {
6: Update statistics for current learner m. ni_1 1 and itt 0 + Fz.
7: end for
Algorithm Exxplorethen-Coomee
Require: Number of arms K, total time T, exploration phase length To
1: Initialize counts nú = 0 and total values ih = 0 for all E [K]
2: // Explore
3: for fort=1,... To do
4: Select arm i (t mod K) +)+11
5: Play arm i, and observe reward ry
6:
Set nz n1 1. and i7 0/_1, for all i [K] \ {ic}
7: Update statistics for current learner n = ni= + and 8, = 0 + v2.
8: end for
9: // Commit
i, arg max, (u//1n
11: to
to T do
Play arm i, and observe reward rt
13: end for
Algorithm 7 UCB (Upper Confidence Bound)
Require: Number of arms K, total time T. confidence multiplier
1: Initialize counts núj = 0 and total values in = 0 for all e [K]
2: for = 1,... do
3: Select arm is =
4: Play arm é, and observe reward r.
5: Update statisties for current learner n.
n/_1
and at
0/11 + m
6: end for
7: for 1= K + 1, 1,... do
8: Select arm
ut
2 In
i arg max
c
ni
9: Play arm is and observe reward r
10:
Set ni = nt_ and 2 = شi_ for all i E [K] \ {ig}
11:
Update statistics for current learner m n and t6
+ F2
12:
end for
31

---

Published as a conference paper at ICLR 2025
Algorithm 8 Exp3 (Exponential-weiiht algorithm for Exploration and Exploitation)
Require: Number of arms K, total time T, learning rate
1: Initialize weights w = and probabilities pà = 1/K for all E [K]
2: for t =, 1,,.,, T do
3: Select arm é according to distribution P. = [p:....,.77 pp
K
4: Play arm i, and observe reward r
5: Estimate reward
re/p
6: Update weight w wt'1 exp(nf:/K) K)
7:
Update probabilities
Wi
p = (1 - 11)
+
for all i E [K]
> j=
w
K
8: end for
Table 2: Hyperparameters for MAB Algorithms
ALGORITHM
PARAMETER VALUE
EPSILON EPSILON-GREEDD EXPLORE-THEN-COMAE
0.1
5.
UCB
1.0
ExP3
0.1
32

---

Published as a conference paper at ICLR 2025
H ADDITIONAL EXPERIMENTAL RESULTS
In this section, we report additional experimental evaluations. In particular, we show how different configurations of budget constraints B and sizes K' of the reward function set perform with different reward selection algorithms in different environments in Figures to 10
Human
Dy3
pPR0
5-5
8-38 10
8 15
OatboNiTaak Runar
0.8
0.6
0.6
0.4
0.4
0.4
022
0.2
02
10
Beeatio Budget
Baratin Budget
Lxralion Budgal
10
0.8
0.0
0.6
0.6
0.6
0.4
6.2
0.0
5,0
0.0
10
0
16
Heration Budget
Rseation Budget
Budget
1.0
1.0
1.0
0.8
0.8
0.6
0.4
0.4
3.2
6.2
0.2
0.0
0.0
0.0
50
0
Harution Budget
laration
Budget
1.0
0.8
0.6
0.4
0.4
0.2
0.2
0.2
0.0
Heraaion Buriett
Escation Budget
Enistion Budget
10
1.0
1.2
1.0
1:00
0.6
0.85
0.6
0.30
0.2
0.5
Itrution Budget
luration Budget
Iotation Budget
10
1.2
0.1
1.0
HandiTak
0.6
0.75
0.6
0.2
0.5
Bandton Buriget
Seextio Buriget
Iendin Budget
Figure 7: Number of iterations necessary to reach human-engineered reward function performance with different computation budgets and tasks. The shaded areas represent standard errors.
33

---

Published as a conference paper at ICLR 2025
8 10
15
1.0
0.75
1.5
1.0
0.6
0.29
0.0
0.0
03
Budget
Budget
Budget
Figure 8: Number of iterations necessary to reach human-engineered reward function performance with different computation budgets. The shaded areas represent standard errors.
Design
crss (PPr)))
Km5
Nomettee Tayk Roward
5,
5m5.Kem
1.00
Nomalaud
0.50
0.25
0.0
Carpole
Humarod Alego Stadow
A
Cangese Dabetce
Nemaleel Teak Recood
8- K0
Nomalzee Task Rewerd
K-1
Nemsdrad Reeoed
5 1-11-16
0.5
0.5
Cargel Balanss
NI Humarod Alago
Brodow
0.0
Curbok: ar
Art MinaoddAggo Shadow
pargols Balance
Avi HamuroeAlugge Brudow
Nemselow Took Rowmeed
8 K=4
Normaited Taxe Rrward
8=15,Km8
5 1=15.K=12
2.0
1.5
1.0
1.0
65
6.0
Cargote Balance
Art
Humarod Allgoo
Srndow
0.0
Garbolle arce
Art
Hunarod Shadow
0.0
Ca Campale Belence
Ari
Shadow
Figure 9: Average performance with standard errors for ORSO with different interaction budget constraints and reward function set size. The dashed horizontal line represents the policies trained with the human- enginerre reward function.
K-8
1.00
1.00
0.75
0.75
Text (bevee
0:30
0:50
0.25
0.0
P7RB
UCB
0:00
0730
0800
UCB
Natm
8-10.K
Teak Beenee
1.0
Taak Roward
Yeak Beeeed
0.5
0.5
2.5
0.50
6:2
8 4
8=15.Kmm
8m
Teek Rowarrd
1.0
Toshk Rowadd
Togg Rowaard
1.0
35
Figure 10: Comparison of different reward selection algorithms for ORSO with different budget constraints and reward function set size.
We also plot in Figure the time necessary to achieve the same performance as policies trained with human-designed reward functions function of the number of parallel GPUs available for all budget constraints and all tasks considered.
34

---

Published as a conference paper at ICLR 2025
Nake
DESO (P*R0)
Time 13 Humee Pefomance 01
Busigel 5
Budgel -
Busigel
0.012
0.0123
0.010
0.010
0.0100
0.008
Curgole
0.0075
0.005
0.005
0004
0.0063
0.004
0.0025
0.002
0.000
Number of GPUs
Number of GPUs
Number of GPUs
Time Nummen Peffemmene 00
B
Budget 10
Budget
0.20
0.4
0.5
0.5
Bed Belance
0.4
0.10
0.2
0.3
2.05
0.1
Namber of GPUs
Number of GPUs
Numbar of GPUs
Suformane PM)
Budget
Budget
Budget
1.2
2.5
1.0
2.0
Am
1.0
0.4
Number of GPUs
Number of GPUs
Number of GPUs
Human Wakmarra (N)
Budget
Budget=
3.0
2.5
Ta Humanon
2.0
0.0
Number of GPUx
Number of GPUs
Numbe of GPUs
Time Haman memtreett (0)
30
12.5
25
42
Alwaro Heed
10.0
7.5
18
20
0.4
10
2.5
10
Number of GPUx
Number of GPUx
Numbe of GPUs
Tine to Human nufommnnc th
Budgel
Budieel
12
25
20
Statow
15
20
Number GPUs
Number GPUs
Number GPUs
Figure 11: Time necessary to achieve the same performance as policies trained with human-designed reward functions as a fuuction of the number of parallel GPUs.
H.1 CHOSEN REWARD FUNCTIONS FOR LARGE REWARD SET
In order to validate that ORSO with D²RB indeed chooses the optimal reward function, train policy for each of the K = 96 reward functions for the ANT task in Figure [ In Table we report 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 underlined. Bolded values indicate the reward functions selected by ORSO across the seeds we ran.
35

---

Published as a conference paper at ICLR 2025
Table 3: Mean task reward for each Reward ID with 95% confidence intervals (CI).
REWARD ID
MEAN (+ CT)
REWARD ID
MEAN (#: CT)
34
10.24 + 0.36
56
5.05 +
18
10.01 + 0.63
39
4.91 + 0.64
71
9.98 + 0.37
74
4.88 0.49
79
9.88 + 0.73
30
4.83 0.78
21
9.77 1 0.22
78
4.83 1
94
9.70 1 0.38
4.76 0.91
66
9.67 + 0.27
2
4.69
81
9.55 + 0.80
28
4.66
70
9.51 0.63
8
0.44
37
9.46 + 0.55
16
4.57
33
9.34 + 0.83
29
4.53
95
9.27 + 0.33
65
0.62
47
9.24 + 0.68
50
4.23
63
9.21 0.76
58
0.44
54
9.20 + 0.80
53
3.84
80
9.16 + 0.25
32
0.73
62
8.88 + 0.37
22
3.74
38
8.81 + 0.45
3.48
49
8.81 + 0.77
69
3.22
35
8.69 1 1.07
1.8810.4
8.61 0.56
88
3.18
52
8.35 1 1.43
64
3.12
67
8.32 + 0.85
3.11
46
8.30 + 0.89
17
3.10
68
8.20 + 1.22
93
3.02
75
8.09 + 0.40
14
2.99
84
8.05 + 1.25
45
+
85
7.77 + 0.97
83
2
72
7.64 + 1.27
27
7.50
55
7,43 1.46
10
2.15
20
7.16
57
1.69
23
7.26 1
1.67
86
7 0.42
82
1.03
36
7.06 + 0.68
42
+
91
6.93 1 1.45
41
0.37 0.30
6.50 1.17
43
0.33
0.80
76
0.22
61
6.06+0.9
89
0.22 0.07
19
5.78 1.43
24
0.21 0.03
25
5,67 1.41
11
0.21 + 0.08
48
5,65 1.54
12
0.19
59
+ 1.02
15
0.19 0.14
26
5.50+
92
+
60
5.47
77
1.004
44
5.47
13
0.05 0.00
40
5.34
51
0.000
73
5.33 4 1.77
87
0.05
5.30 + 1.38
90
0.000
36

---

Published as a conference paper at ICLR 2025
H.2 VISUALIZING ORSO
To better visualize how ORSO selects the best reward function, discards suboptimal ones efficiently, and thanks this, explores more reward functions, provide further visualizations in this section.
Figures 12 and 13 show a full training of ORSO (D*RB) and the naive selection stratecy (EUREKA) with budget B 15 and K 16 on the ALLEGROHAND task, respectively. In both figures, the top plot shows the task reward during training. The colors indicate the reward functions currently in use. The middle plot more clearly shows the reward function being currently used. The vertical axis contains the reward function indices. In both plots. the dashed vertical lines indicate that resampling has been triggered. Lastly, the bottom plot shows the unnormalized cumulative regret during training.
Comparing the two figures, we can see that ORSO initially explores reward functions near- uniformly, but quickly finds policy that surpasses the policy from the human-engineered reward function, leading to decrease in regret. On the other hand, EUREKA uniformly trains on each re- ward function leading the algorithm explore fewer reward functions. Moreover, see that the lack of rejection sampling can result in initial reward function sets that contain many invalid reward functions indicated by a in the figures.
Alegsstand USM with 5ith Solb
Howurd 2212222
20000
10833
500
70000
Figure 12: ORSO (D²RB) on ALLEGROHAND with B = 15 and K = 16.
37

---

Published as a conference paper at ICLR 2025
Mlgrottad BUTSSA B-18, Bold
Nowas
1923
290
0091
1999
1963
1133
209
1900
1930
1000
10000
1833
209
31533
4193
1993
1983
1990
Figure 13: EUREKA on ALLEGROHAND with B 15 and 16.
Mbgrarfand
0.00
0-4
9.6
5000
10000
1500
3983
2403
199
2013
2803
20000
100
1991
1590
2983
Figure 14: EUREKA on ALLEGROHAAD with B 5 and K
38

---

Published as a conference paper at ICLR 2025
1990
2901
199
2030
2003
-2000
500
50090
1500
2000
1500
Figure 15: ORSO (D²RB) on ALLEGROHAND with B = and K = 8.
Alligoffant 6.13 with Brit
23303
2590
2900
2000
15000
10000
1000
91931
1990
2983
2001
Figure 16: ORSO (Exp3) on ALLEGROHAND with = 5 and K =
39

---

Published as a conference paper at ICLR 2025
Alsgoshand UG3 with B-6, Ned
175
25
03
1983
10000
808
2003
1890
1133
1900
20000
2500
2300
-323
12:59
10000
2000
2900
Figure 17: ORSO (UCB) on ALLEGROHAND with = 5 and = 8.
Alggothard Big
Tha Rlward
1010
1900
15:00
20000
2400
1000
1900
11:00
12:0
1000
0
1000
1900
11:53
3000
Figure 18: ORSO (ETC) on ALLEGROHAND with and K 8.
40

---

Published as a conference paper at ICLR 2025
Alegge hand B-d,
2983
2903
198
2380
2500
10000
19890
1998
2383
2900
Figure 19: ORSO (EG) on ALLEGROHAND with and K 8.
200
196
R00
5800
12000
1420
1000
435
1093
1200
1480
1000
1:00
10:0
290
KCS
9831
1859
1480
1406
Figure 20: EUREKA on ANT with B 10 and
41

---

Published as a conference paper at ICLR 2025
Rowor
290
19E
1899
1859
1480
1400
2000
105
6093
8000
1833
12:03
1484
1000
1000
200
48%
B0C8
5800
1249
1485
1000
Figure 21: ORSO RD²RB) on ANT with = 10 and K 4.
1809 FroMar
4890
1480
10000
290
.393
1833
1480
10000
1003
120
290
199
KCS
9833
1743
1480
1006
Figure 22: ORSO (Exp3) on ANT with B 10 and
42

---

Published as a conference paper at ICLR 2025
Rooart
290
496
1839
1859
1485
1400
400
1480
10000
2000
2000
3000
1:00
1000
1903
1259
1480
1000
Figure 23: ORSO (UCB) on ANT with B 10 and
200
196
800
5800
12000
1420
1000
290
1033
1420
1000
4000
3000
290
KCS
9831
1859
1485
1406
Figure 24: ORSO (ETC) on ANT with 10 and K 4.
43

---

Published as a conference paper at ICLR 2025
290
430
1293
1008
1900
1200
1400
1000
2700
43%
0C83
5008
1300
12200
14025
1000
1200
200
105
RCS
5.03
12:00
1424
1000
Figure 25: ORSO (EG) on ANT with 10 and K 4.
44


Reviews:
[{"review_id": "2PBD1kO1lK", "reviewer": "Reviewer_sCCd", "summary": "The paper employs the data-driven online model selection algorithm D^3RB (Pacchiano et al., 2023) to choose between candidate reward functions for reinforcement learning, where these candidates are generated through an LLM. It replaces the naive reward selection from Ma et al. (2023) with D^3RB, enabling more efficient online selection among candidate rewards. A simple example shows how D^3RB helps prevent budget exhaustion by avoiding over-allocation to a single option. The paper further evaluates the algorithm’s effectiveness on Isaac Gym (Makoviychuk et al., 2021), comparing baseline and human-designed rewards. Ablations also explore various bandit exploration strategies, including UCB, EXP3, ETC, EG, and Naive.\n\n**References**\n\n- Pacchiano, A., Dann, C., & Gentile, C. (2023). *Data-driven regret balancing for online model selection in bandits.* arXiv preprint arXiv:2306.02869.\n    \n- Ma, Y. J., Liang, W., Wang, G., Huang, D.A., Bastani, O., Jayaraman, D., Zhu, Y., Fan, L., & Anandkumar, A. (2023). *Eureka: Human-level reward design via coding large language models.* arXiv preprint arXiv:2310.12931.\n    \n- Makoviychuk, V., Wawrzyniak, L., Guo, Y., Lu, M., Storey, K., Macklin, M., Hoeller, D., Rudin, N., Allshire, A., & Handa, A., et al. (2021). *Isaac Gym: High performance GPU-based physics simulation for robot learning.* arXiv preprint arXiv:2108.10470.", "questions": "The weaknesses section raised some key questions, which I’ll summarize here for clarity:\n\n1. ORSO functions only as a selection algorithm, correct? Reward generation isn’t part of the algorithm itself?\n    \n2. Does the paper simply apply the D^3RB algorithm, or does it introduce theoretical improvements? This aspect is somewhat unclear.\n    \n3. 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?\n    \n4. 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.\n    \n5. 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?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper addresses a significant issue in reinforcement learning, as sparse rewards indeed pose challenges, and reward shaping can provide dense feedback, potentially accelerating learning. The writing is clear, with well-presented graphs and experiments, and a well-defined motivation. The paper also successfully applies a recent online model selection algorithm, demonstrating in the proposed benchmark how the algorithm can aid in selecting the appropriate reward functions with limited budget and can scale effectively with increased budget and candidate reward functions.", "weaknesses": "**Writing**: In Section 3.1, ORSO is presented as an effective and efficient method for reward function design. However, my understanding is that ORSO simply selects a reward function from a set of candidates, with the reward generation handled separately. If this is correct, it would be helpful if the paper clearly defined ORSO’s components, specifying whether reward generation is part of ORSO or assumed to be user-provided. Clarification here would improve understanding.\n\n**Complexity**: The proposed method requires maintaining $K$ separate policies for each reward, which could create substantial memory overhead. Standard approaches in reward shaping often aim to achieve similar benefits while maintaining only a single policy, highlighting a potential drawback in scalability.\n\n**Performance Guarantees**: Traditional reward shaping studies typically ensure that the shaped reward aligns with a base reward function. Here, there is no guarantee that the proposed objective aligns with the base reward, leaving the outcome quality solely dependent on the reward generation process. This could raise concerns about consistency in performance.\n\n**Experiments**:\n\n1. 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.\n    \n2. 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.\n    \n3. 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.\n    \n4. 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.\n    \n\n**References**\n\n- Ng, A. Y., Harada, D., & Russell, S. (1999). *Policy invariance under reward transformations: Theory and application to reward shaping.* In ICML.\n    \n- Zou, H., Ren, T., Yan, D., Su, H., & Zhu, J. (2019). *Reward shaping via meta-learning.* arXiv preprint arXiv:1901.09330.\n    \n- Zheng, Z., Oh, J., & Singh, S. (2018). *On learning intrinsic rewards for policy gradient methods.* Advances in Neural Information Processing Systems.\n    \n- Sorg, J., Lewis, R. L., & Singh, S. (2010). *Reward design via online gradient ascent.* Advances in Neural Information Processing Systems.\n    \n- Gupta, D., Chandak, Y., Jordan, S. M., Thomas, P. S., & da Silva, B. C. (2023). *Behavior Alignment via Reward Function Optimization.* arXiv preprint arXiv:2310.19007.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m48RalZU1y", "reviewer": "Reviewer_t4Xg", "summary": "This paper introduces Online Reward Selection and Policy Optimization (ORSO), an approach that defines reward selection as an online model selection problem. The approach uses exploration strategies to identify shaping reward functions.", "questions": "* What is human designed reward and how it is computed?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Soundness\n======\nThe approach is generally sound. \n\t\nSignificance & Related work\n=========\nThe paper presents an in-depth related work section, and well defined preliminaries (note redundancy of section 2)  that lead to demonstrations of several results. \n\nExperimentation\n=========\nThe paper presents an in-depth ablation analysis of the performance of various selection algorithms.\n\nPresentation\n=========\nThe paper is well written.", "weaknesses": "Soundness\n======\nIt is unclear in the experiments in Fig 2 what ‘human-level performance’ or ‘human-designed reward function’ is and how it is defined/computed. Note that the proof for D1 needs to be rewritten for clarity to show base case and inductive hypothesis, should proof by induction still be the chosen approach.\n\t\nExperimentation\n=========\nThe paper presents an in-depth ablation analysis of the performance of various selection algorithms, however, the impact of poorly chosen task rewards needs to be analysed. \n\nPresentation\n=========\nPresentation is good, as above, Section 2 is too short and redundant.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZWHplOKPoT", "reviewer": "Reviewer_knxR", "summary": "This paper studies automated reward shaping by posing it as an online reward selection problem. Instead of multiple training runs to observe the impact of different shaping functions, this work aims to identify the best one within a fixed time budget. To this aim, the authors develop ORSO, a regret-minimizing approach that utilizes multi-armed bandits where a candidate shaping function is an arm. More specifically, ORSO uses the D3RB algorithm to select an arm. Upon selection of an arm, ORSO trains a policy corresponding to the said arm for a fixed number of iterations and then evaluates the policy with respect to the task rewards. The paper provides regret guarantees, assuming that a learner monotonically dominates all learners and its average performance increases monotonically. \n\nThe paper evaluates a practical implementation of ORSO in continuous control tasks with varying complexity whose rewards are either sparse or unshaped. The experimental results show that ORSO is faster than an LLM-based reward design method, can surpass human-designed rewards, and performs better as the budget increases. The authors also provide an ablation study for different arm selection strategies and different numbers of candidate shaping functions.", "questions": "- In what cases would the monotonicity assumption be violated? Do the environments in the experimental set-up violate or obey the assumption? How would ORSO handle such violations?\n\n- Future work mentions exciting directions. Since the naive approach is failing, how likely is a VLM-based reward design method to fail?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well-written. The motivation is clearly explained, and the problem and assumptions are well described. Moreover, given the assumptions, the proposed approach and its theoretical guarantees are clear.\n\n- The experimental set-up makes sense, and the evaluated baselines allow us to see how reward design is critical, humans can be sub-optimal at it, and naive attempts are prone to fail.\n\n- The experimental results clearly showcase its advantages in comparison to the baselines. In addition, the ablation study evaluates the impact of different components of ORSO and provides detailed insights.", "weaknesses": "- I urge the authors to move the related work, at least the most relevant parts, to the main document.\n\n- Assumption 4.2 seems limiting. A discussion of why the assumptions are viable or how they are needed would strengthen the paper's arguments. It would be even better to explain their role in causing the contrast with the regret guarantees in Pacchiano et al. (2023).\n\n- As the quality of candidate shaping functions plays an important role, an ablation study to understand the impact of wrong/redundant candidates would help the reader understand the limitations of ORSO.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s7GyK7BgKm", "reviewer": "Reviewer_C5vj", "summary": "This paper introduces ORSO, a method that aims to increase the efficiency of the reward shaping selection process by casting it as an automated online model selection problem.\nORSO is a general algorithmic framework that implements the following steps: (i) a reward function generation method is used to provide a set of candidate shaping reward functions, (ii) a selection algorithm is used to select a shaping reward function, (iii) an RL algorithm is used to train the policy associated with the selected shaping reward function for a set amount of iterations, (iv) the trained policy is then evaluated against the task reward function and the utility is used to update the parameters of the selection algorithm. This process is repeated until a predefined computational budget is exhausted.\nWhile the components within the ORSO framework are modular and exchangeable, this work uses (i) an LLM based generator as the reward function generation method, (ii) PPO as the RL algorithm, (iii) D3RB, as the reward function selection algorithm (ablations are additionally conducted with Exp3, D3RB,UCB, ETC, and EG).\nExperiments are conducted across tasks of varying difficulty, 3 budgets, and 3 reward functions sets.\nResults indicate that the ORSO performance in terms of task return scales with budget, and is comparable - and can surpass - that of human defined shaping reward functions; additionally ORSO is twice as fast as a prior shaping reward function selection method (EUREKA).", "questions": "- Unique contributions could be made clearer and explicitly called out in the introduction.\n\n- 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.\n\n- 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.\n\n- 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.\n\n- 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.\n\n- Please look at the weaknesses section and help clarify if any are can be addressed.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Claims: (1)  ORSO reduces both time and computational costs by more than half compared to earlier methods, making reward design accessible to a wider range of researchers. (2) By formalizing the reward design problem and providing a theoretical analysis of ORSO’s regret when using the D3RB algorithm, we also contribute to the theoretical understanding of reward design in RL.\n\n- The work proposes an original formulation of the shaping reward function selection process, viewing it as an online model selection problem.\n- The regret based analysis provides a clear and intuitive way to monitor ORSO's performance and efficiency gains.\n- Thanks to the problem formulation, the method is kept elegant in its simplicity and largely amounts to the application of existing approaches into a unified framework.\n- Results on a variety of tasks and domains against available baselines support the efficiency and performance claims.\n\nClarity:\n- The writing is clear, the paper is well structured, and appropriate context is provided to the reader.\n\nSignificance:\n- This work tackles the issue of reward design for RL. This has been and continues to be one of the most significant challenges keeping RL from widespread successful deployment in the real world.", "weaknesses": "Contribution:\n- 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\".\n- 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.\n- 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.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JLPqordvC8", "reviewer": "Reviewer_DEh7", "summary": "The paper proposed an Online Reward Selection and Policy Optimization (ORSO) algorithm for reinforcement learning. ORSO pre-generates some candidate reward functions by linearly combining some reward components or by LLM, while learning, ORSO dynamically evaluates which candidate reward function can lead to better policy optimization, then selects the optimal candidate to guide the learning process.", "questions": "1. Regarding Weakness 1, about candidate reward function generation, As described in  section 5.1.2, the candidate reward functions are directly generated through LLM, Could you clarify:\n\n(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?\n\n(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?\n\n2. 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)?\n\n3. 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?\n\n4. 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. \n\nFor example, suppose the MDP provides rewards of $0, 0, 1$ for states $s_1, s_2, s_3$ (only 3 states). A human-designed reward function might assign $0, 1, 1$ for $s_1, s_2, s_3$. Consequently, the cumulative reward under the human-designed reward function would be higher, and it also proposes new targets (both $s_2$ and $s_3$ are equally important). From my understanding, the performance should be evaluated consistently on the original MDP reward (the true objective), meaning that the \"No design\" case should actually serve as an upper bound.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The approach is easy to implement and effective at selecting reward functions, it also shows fast convergence in terms of both computational time and sample efficiency.", "weaknesses": "1. As this method follows a \"pre-define and select one\" paradigm, the final optimal performance that ORSO can achieve heavily depends on how good are the pre-generated candidate reward functions.\n2. 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.\n\n[1] Devidze, Rati, Parameswaran Kamalaruban, and Adish Singla. \"Exploration-guided reward shaping for reinforcement learning under sparse rewards.\" Advances in Neural Information Processing Systems 35 (2022): 5829-5842.\n\n[2] Zheng, Zeyu, Junhyuk Oh, and Satinder Singh. \"On learning intrinsic rewards for policy gradient methods.\" Advances in Neural Information Processing Systems 31 (2018).\n\n[3] Memarian, Farzan, et al. \"Self-supervised online reward shaping in sparse-reward environments.\" 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2021.\n\n[4] Burda, Y., Edwards, H., Storkey, A., and Klimov, O. (2018). Exploration by random network distillation. In International Conference on Learning Representations.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9rlMTAHM7q", "reviewer": "Reviewer_YU7z", "summary": "This manuscript proposes the Online Reward Selection and Policy Optimization (ORSO) to frame shaping reward selection as an online model selection problem. It automatically identifies promising shaping reward functions, balancing exploration and exploitation with provable regret guarantees. The ORSO method significantly improves sample efficiency and reduces computational time compared to traditional methods that fully evaluate each shaping reward function.", "questions": "1. 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?\n\n2. 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.\n\n3. 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.\n\n4. There is a similar paper ORSO: Accelerating Reward Design via Online Reward Selection and Policy Optimization published in ARLET 2024. What is the difference between these two works? Has the ARLET paper been cited?\n\n5. The number of references is small, and more recent articles on reward shaping can be added.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The idea is a little simple but effective.", "weaknesses": "Some experiments and theories can be added.", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)