PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Scripted Search: Sample-Efficient Reward Discovery via Agentic Black-box Optimization

Minghao Li, Rui Tan, Ruihang Wang

arXiv:2609.32394v1cs.AI

TL;DR

Each reward candidate requires a full RL training run, making sample efficiency a central challenge in reward search. ARBO lets an LLM agent build its search strategy at runtime from persistent evaluation history. Under a shared budget, it reports gains of 29.9% in Bi-DexHands mean success rate and 192.8% in power-grid score over baselines.

  • Problem

    Reward discovery is sample-inefficient because each candidate’s quality can be assessed only by training a policy, and a full search can require hundreds of hours.

    Source: §1 · p. 1

  • Method

    ARBO gives an LLM agent a persistent history of oracle observations and agent-written beliefs to query when generating reward candidates at runtime.

    Source: §1 · p. 2

  • Results

    29.9% improvement over the baseline mean in mean success rate across ten Bi-DexHands tasks, and 192.8% average improvement over baselines in power-grid evaluation under the shared budget.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Across diverse control tasks, experiments show gains over evaluated baselines, and ablations support the contributions of the proposed components.

    Source: §6 · p. 9

    ARBO reasons over textual scores, per-term curves, and tracebacks; multimodal reasoning for failures apparent only in non-textual observations is left to future work.

    Source: §6 · p. 9

Abstract

from arXiv · show

Designing dense reward functions for low-level reinforcement learning (RL) control remains difficult. Recent work uses large language models (LLMs) to iteratively generate and refine reward functions using policy-training feedback within scripted search algorithms. However, evaluating each candidate requires a full RL training run, making sample efficiency a central challenge for reward search on complex control tasks. To address this limitation, we propose an Agentic Reward Black-box Optimization (ARBO) framework, in which an LLM agent builds the search strategy at run time from an evaluation history maintained as its persistent workspace. The evaluation history comprises two components: observations maintained by the evaluation oracle, including candidate scores, per-term training curves, and error tracebacks; and an agent-maintained belief that records diagnoses and intended next steps. The agent queries both with tools and generates the next batch of reward candidates, rather than generating them in a single pass from a fixed prompt. Across four control domains, ARBO achieves gains of 29.9% in manipulation success rate and 192.8% in power-grid score over baseline means under a shared evaluation budget. Ablations examine each component's contribution and sensitivity to backbone choice.

1 INTRODUCTION

Reward search is sample-inefficient because each candidate requires a costly policy-training run, while existing accelerators do not fit reward programs’ structure or discrete search space. ARBO lets an LLM build its search strategy from evaluation history at runtime and outperforms automated LLM baselines under a shared budget.

1 INTRODUCTION

  • Dense rewards provide progress signals for policy learning when a task’s own metric, such as success rate, is too sparse.Designing these rewards demands substantial expert effort, and LLMs can generate executable reward code from task descriptions and environment code.Source: §1 · p. 1
  • Each reward candidate requires policy training that takes hours, making sample-efficient search essential when a full search can take hundreds of hours.Existing black-box accelerators are ill-suited because reward-program changes are structural rather than numerical, the search space is discrete, and surrogate fitting would require many full training runs.Source: §1 · p. 1
  • ARBO retains the complete evaluation history and lets an LLM agent query observations and its own belief to generate subsequent candidates at runtime.Oracle-owned observations include candidate scores, per-term curves, and tracebacks; the agent maintains diagnoses and intent in its belief.Source: §1 · p. 2
  • 29.9% improvement over the baseline mean in mean success rate across ten Bi-DexHands tasks, and 192.8% average improvement over baselines in power-grid evaluation.Under the shared evaluation budget, the seven ablated variants lose 29.6% of the gain on average.Source: §1 · p. 3

2 RELATED WORK

Automated reward discovery has moved from one-shot generation to iterative refinement using policy-training feedback, with methods differing in how they retain history and generate candidates. More broadly, LLM optimization systems typically place generation within externally specified search procedures, whereas ARBO builds its search strategy at runtime for each task.

2 RELATED WORK

  • Iterative reward discovery revises candidates using training feedback, with LLM methods refining a best candidate greedily, evolving populations, or expanding search trees and graphs.Examples include Eureka and Zeng et al. (2024) for greedy refinement, Hazra et al. (2025), Li et al. (2025), and Zhao et al. (2026) for population methods, and Gao et al. (2026) and Yao et al. (2025) for trees or graphs.Source: §2 · p. 3
  • LLM optimization systems commonly use the LLM as a variation operator inside an externally managed search loop, while OPRO prompts directly from past solution-score pairs.ReEvo adds a reflector LLM, ShinkaEvolve uses adaptive parent sampling and novelty-based rejection, and GEPA reflects on execution traces.Source: §2 · p. 3
  • ARBO differs from scripted and meta-trained optimizers by building its search strategy at runtime on each task, with the agent querying its file-system history before proposing candidates.Meta-black-box optimization learns a meta-level policy over a problem distribution to configure a low-level optimizer, while ARBO has the agent write candidates directly.Source: §2 · p. 3

3 PROBLEM STATEMENT

The reward design problem fixes a task’s world model and learning algorithm, then searches over reward functions to maximize task performance. This search is black-box, and predefined history-selection and proposal rules can leave accumulated feedback unused.

3 PROBLEM STATEMENT

  • A reward design problem supplies a reward-free world model and chooses a reward function to complete the MDP, while the benchmark’s learning algorithm and evaluation metric remain fixed.The reward is the MDP component left to the designer, and the task metric scores the policy returned by the fixed learning algorithm.Source: §3 · pp. 3–4
  • Reward discovery evaluates candidate reward code by training a policy and measuring the task metric, with the goal of maximizing performance over rewards.The candidate is executable code emitted by a language model conditioned on the task specification; the benchmark’s fixed learning algorithm trains the policy under that reward.Source: §3 · p. 4
  • Reward discovery is black-box optimization because the objective has no analytic form and each candidate must be integrated, trained, and measured.The search strategy is decomposed into a history representation and a proposal operator that turns the represented history into the next query.Source: §3 · p. 4
  • In the logged 128-sample DoorCloseOutward run, 79% of candidates’ code, curves, and tracebacks entered no later prompt; across seven Bi-DexHands tasks, 77% neither improved the incumbent nor entered one.Selection criteria and proposal templates are predefined; the logged run also shows search performance plateauing below the task’s maximum score.Source: §3 · p. 4

4 SYSTEM DESIGN

ARBO organizes reward search around a persistent history, an agent-driven proposal process, an external evaluation oracle, and a scripted exploration schedule. Each round schedules a mode, proposes candidates through workspace interactions, and evaluates them.

4 SYSTEM DESIGN

  • ARBO combines a history, proposal operator, evaluation oracle, and schedule in rounds of scheduling, proposal, and evaluation.The agent proposes candidates from workspace interactions rather than a single generation call.Source: §4 · pp. 5–6, Figure 3 · p. 5
  • The history retains the full evaluation record alongside an agent-maintained belief, separating oracle observations from the agent’s evolving search state.The observations are maintained outside the agent; the agent updates its own belief and rolling notes.Source: §4 · p. 5
  • The agent’s belief records diagnoses and intended next steps, while candidate lineage records which search branch the agent judges worth extending.The agent overwrites its rolling notes each round; it commits candidates on the best line when refining or on a fresh branch when exploring.Source: §4 · p. 5
  • The proposal operator is an autonomous agent run that uses sandboxed tools to inspect workspace files and write reward candidates.The workspace includes read-only environment code, committed candidates, an evaluation log, and an analysis file for the belief.Source: §4 · pp. 5–6
  • The oracle trains one policy per candidate and appends the task acceptance metric, per-term reward curves, and any failure traceback to the history.The oracle operates outside the agent’s environment and cannot be invoked through its tools.Source: §4 · p. 6
  • An external schedule steers exploration or exploitation using the acceptance record and past prompts, rather than inspecting candidate contents.It switches back to exploration for at most ν rounds after the incumbent fails to improve for µ consecutive rounds.Source: §4 · p. 6
  • The loop starts from bootstrap code with an empty history, repeats rounds until the sample budget is spent, and returns the highest-scoring candidate.The incumbent is the highest-scoring candidate in the history.Source: §4 · p. 6

5 EXPERIMENTS

The experiments compare ARBO with five automated LLM search methods across four control domains under shared evaluation budgets. ARBO’s results vary by task, with its advantage most pronounced on sparse-feedback tasks and its candidate quality improving during search.

5.1 EXPERIMENT ENVIRONMENTS

  • The four domains cover dexterous manipulation, power-grid operation, legged locomotion, and traffic-signal control, each evaluated with its own acceptance metric.Metrics include Bi-DexHands success rate, the L2RPN score over 16 held-out Case14 scenarios, locomotion tracking and falls, and negated official average delay for traffic.Source: §5.1 · pp. 6–7

5.2 BASELINES

  • Five automated LLM search methods are compared under shared domain-specific budgets, backbone, and policy-training configurations.The baselines are Eureka, R⋆, REvolve, ShinkaEvolve, and RF-Agent; budgets are 72 reward samples for locomotion and 128 for the other domains.Source: §5.2 · p. 7

5.3 EXPERIMENT RESULTS

  • ARBO achieves the best score on most Bi-DexHands tasks and never ranks below second among automated methods across the ten-task suite.All methods share the same backbone and evaluation budget; Sparse uses the success indicator as its reward.Source: Table 1 · p. 7, §5.3 · p. 7
  • At 64 reward samples, ARBO’s group-mean best-so-far success already exceeds every baseline’s final score, and it finishes highest in every difficulty group.The final gap is small on easy tasks, while on hard tasks ARBO plateaus within about 30 samples and baselines close most of the gap by the budget’s end.Source: Figure 4 · p. 8, §5.3 · p. 8
  • ARBO’s candidate success distribution dominates the fixed-rule baselines, and its mean candidate quality increases most from the first to last budget quartile.A larger fraction of ARBO candidates clears each of the 0.5 and 0.8 quality thresholds.Source: Figure 5 · p. 8, §5.3 · p. 8
  • 0.95× on traffic and 2.9× on the power grid are ARBO’s final best-so-far gains over the baseline mean, across domains ordered from dense to sparse feedback.The advantage is more noticeable where feedback is sparse.Source: Figure 6 · p. 8, §5.3 · pp. 8–9

5.4 ABLATIONS

  • The ablations examine history components, search schedules, and normalized scores across backbones.History variants remove the belief or observations, or interpose a retriever; schedule variants use only exploration or exploitation, or remove the framework.Source: Figure 7 · p. 9

6 LIMITATION & CONCLUSION

ARBO uses an LLM agent to build its reward-search strategy at runtime from oracle observations and an agent-maintained belief. Its textual history limits it when relevant failures are visible only through non-textual observations.

6 LIMITATION & CONCLUSION

  • ARBO’s history is textual, so it can miss failures apparent only in non-textual observations, such as unnatural high-scoring movements or thermal fields.Adding multimodal reasoning is left to future work.Source: §6 · p. 9
  • The evaluation history separates oracle-appended observations from the agent’s diagnoses and intended next steps.The LLM agent builds its search strategy at runtime from this history.Source: §6 · p. 9
  • The paper reports that the benchmarks are public simulators used under the licenses specified in Appendix F.Code and further reproducibility details are provided in the paper and appendices.Source: ETHICS STATEMENT · p. 10, REPRODUCIBILITY STATEMENT · p. 10

A ENVIRONMENTS

The environments span dexterous manipulation, power-grid operation, traffic-signal control, and legged locomotion, with task-specific scores and control settings. The descriptions also define how performance is evaluated in each domain.

Bi-DexHands

  • Bi-DexHands evaluates two hands cooperating on object-passing, tool-use, or placement tasks; its binary success predicate gives no partial credit.Dense rewards therefore supply the learning signal; Figure 8 illustrates the ten tasks.Source: A ENVIRONMENTS · p. 14, Figure 8 · p. 14

Grid2Op

  • Grid2Op evaluates power-grid operation over recorded demand, with the score based on operating cost and whether the grid survives.The Case14 benchmark has 538 state dimensions, 273 competition actions, and 16 held-out scenarios of 8,064 steps each. The episode score interpolates between four cost references, then averages across scenarios.Source: A ENVIRONMENTS · pp. 14–15

RESCO

  • RESCO gives each signalized intersection its own learner, which reads only its own entry of the designed reward and does not communicate at execution time.The score is the negated average delay of the best training episode; the four networks range from a single intersection to a synthetic 4×4 grid.Source: A ENVIRONMENTS · p. 15, Figure 10 · p. 16

Isaac Lab locomotion

  • Isaac Lab asks the ANYmal-D quadruped and Cassie biped to track commanded velocity on flat and rough terrain, and ends an episode on a fall.Its score combines tracking error with a fall charge for steps removed from the episode; Figure 11 illustrates the four tasks.Source: A ENVIRONMENTS · p. 16, Figure 11 · p. 16

B TRAINING DETAILS

The training and search configurations specify how candidate rewards are evaluated, how ARBO schedules exploration and exploitation, and the shared settings used for backbone comparisons. The section also identifies the reported hardware and cost measures.

Policy training

  • Each candidate reward is trained from scratch using the benchmark’s published configuration, with only the reward varying and all methods searching under training seed 0.Selected best rewards are additionally trained with seeds 1–5 for curves in Appendix D; Table 2 lists the oracle configurations.Source: B TRAINING DETAILS · p. 17, Table 2 · p. 17

Search configuration

  • ARBO explores for an initial schedule, exploits once an incumbent exists, and may re-explore after consecutive unaccepted rounds; each attempted candidate counts as one sample.Table 3 lists the main-comparison search configuration.Source: B TRAINING DETAILS · p. 17, Table 3 · p. 17

Backbones

  • Five backbones vary model family, reasoning capability, and serving scale while sharing the same interface, temperature, instruction file, tools, and schedule.Table 4 lists the configurations.Source: B TRAINING DETAILS · p. 17, Table 4 · p. 17

Experiment environment

  • The agent, oracle, and training servers share one node, with Isaac Gym and Isaac Lab training batches on GPUs and Grid2Op and RESCO using CPU threads.Table 5 lists the hardware and software configuration.Source: B TRAINING DETAILS · p. 17, Table 5 · p. 17

Cost reporting

  • Per-candidate training and evaluation time is reported by task as a mean and 10th–90th percentile range; token use is reported per attempted candidate across the ten Bi-DexHands tasks.These measures are described in Tables 6 and 7, respectively.Source: B TRAINING DETAILS · p. 18, Table 6 · p. 18, Table 7 · p. 18

C BASELINE DETAILS

The baselines use distinct candidate-selection and expansion strategies, while each runs its own search against the oracle under identical settings. The section specifies the comparison setups for five methods.

Baseline comparison

  • All baselines search against the oracle at identical settings, with reasoning traces stripped before each method’s parser receives the reply.Table 8 summarizes the methods’ selection and expansion rules.Source: C BASELINE DETAILS · p. 18, Table 8 · p. 18

Eureka

REvolve

  • REvolve uses its fully automated variant, four candidates per iteration, and an elite archive capped at 13.Source: C BASELINE DETAILS · p. 18

RF-Agent

  • RF-Agent uses five action counts of (2, 2, 2, 1, 1), eight children per expansion, an annealed UCT constant, and thought-align and self-verify.The UCT constant decreases linearly from 0.4 to 0.1.Source: C BASELINE DETAILS · p. 18

R⋆

  • R⋆ is reimplemented with a population of 16, 12 reflection offspring, four crossover offspring, five LLM critics, and retraining of the top two individuals.Source: C BASELINE DETAILS · p. 19

ShinkaEvolve

  • ShinkaEvolve uses one candidate per generation, two islands, an archive of 40, and an LLM novelty judge, while disabling its embedding-based novelty filter.Its setup also specifies archive selection and patch probabilities.Source: C BASELINE DETAILS · p. 19

D ADDITIONAL RESULTS

Figure 12 presents reward-search and policy-training curves for Bi-DexHands. The search comparison spans ten tasks under a shared 128-sample budget.

D.1 DEXTEROUS MANIPULATION

  • Figure 12 plots best-so-far success against reward-function samples across ten Bi-DexHands tasks, with each method receiving 128 samples.Source: §D.1 · p. 19, Figure 12 · p. 19
  • Figure 12’s lower two rows plot the success rate of each method’s best-reward policy against environment steps.Source: §D.1 · p. 19, Figure 12 · p. 19

D.2 POWER-GRID OPERATION

The additional results show ARBO completing the most four-week power-grid scenarios, and describe evaluation plots for line loading, locomotion, and traffic-signal control.

D.2 POWER-GRID OPERATION

  • ARBO completes the most four-week power-grid scenarios; ShinkaEvolve completes a few, while no other method completes any.A survival fraction of 1.0 denotes completion of the full scenario.Source: §D.2 · p. 19, Figure 13 · p. 20
  • Figure 14 plots maximum line loading ρ across sixteen power-grid scenarios, marking Do-Nothing, blackouts, the thermal limit at ρ = 1, and each method’s official score.Source: §D.2 · pp. 19–20, Figure 14 · p. 20

D.3 LOCOMOTION

  • Figure 15 compares search scores and best-reward policy curves across four locomotion settings, using 72 reward samples and 800 PPO iterations per policy.Search scores are negated fall-charged tracking errors; training plots tracking error and fall rate.Source: §D.3 · p. 20, Figure 15 · p. 21

D.4 TRAFFIC-SIGNAL CONTROL

  • Figure 16 covers four traffic-signal settings; each method uses 128 reward samples and trains policies for 40 episodes, with delay summarized across five held-out seeds.Source: §D.4 · pp. 20–21, Figure 16 · p. 21

D.5 ABLATIONS

The ablation results report sensitivity to the LLM backbone, while the appendices provide search procedures, resource licenses, and prompt details.

D.5 ABLATIONS

  • Figures 17 and 18 show ablation search trajectories and training diagnostics for Cassie Flat, Cologne8, and GraspAndPlace.Search scores are expressed as loss shares of the full method’s gain over the relevant reference reward.Source: §D.5 · p. 21, Figure 17 · p. 22, Figure 18 · p. 22
  • MiniMax-Text-01 and Qwen3-32B perform poorly, particularly on manipulation, indicating that the method needs a capable backbone.Source: §D.5 · p. 22, Figure 19 · p. 22

E ALGORITHMS

  • Algorithm 1 specifies ARBO’s search procedure, taking a task specification, sample budget, and schedule constants, and returning the highest-scoring reward.Source: E ALGORITHMS · p. 23

F LICENSES

  • Table 9 lists licenses and URLs for the baselines, benchmarks, and training algorithms used.R⋆ releases no code, and its reimplementation follows Appendix C.Source: Table 9 · p. 23, F LICENSES · p. 23

G PROMPTS

  • The agent’s workspace includes candidate records with scores, per-term diagnostics, and error tracebacks, alongside its own notes from prior attempts.Source: G PROMPTS · p. 24
  • The schedule injects explore/exploit guidance each round: exploit refines the current best, while explore proposes a structurally different candidate.Source: G PROMPTS · pp. 24–25

Related papers

Loading 2609.32394v1…