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

Minghao Li; Rui Tan; Ruihang Wang

cs.AISep 26, 2026

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

Authors: Minghao Li, Rui Tan, Ruihang Wang

Organizations: Nanyang Technological University · Yunnan University

Abstract

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.

Figures & tables

Figure 1: Agentic Reward Black-box Optimization. Where prior methods wrap the LLM in a scripted outer search rule, arbo lets the agent analyze the history and propose the next candidates.

Figure 2: MCTS-style reward search: (a) Selection coverage (b) Candidate score.

Figure 3: arbo framework design. The agent queries the history

\mathcal{D}_{t}

with tools and commits reward candidates, while the oracle owns the observations and the schedule issues the prompt

m_{t}

Method	Easy				Medium			Hard
	Swing Cup	Lift Underarm	Door Close	Over	Grasp Place	Block Stack	Bottle Cap	Kettle	Catch Underarm	Catch Abreast	Avg
Sparse	0.01	0.00	0.06	0.00	0.00	0.02	0.03	0.02	0.00	0.00	0.014
REvolve	0.920	0.906	0.606	0.947	0.510	0.323	0.695	0.970	0.298	0.372	0.655
Eureka	0.994	0.889	0.972	0.939	0.527	0.529	0.873	0.965	0.676	0.558	0.792
RF-Agent	0.984	0.930	0.484	0.925	0.366	0.170	0.837	0.994	0.819	0.560	0.707
R $\star$	0.999	0.918	0.580	0.970	0.339	0.352	0.434	0.958	0.850	0.000	0.640

Table 1: Bi-DexHands success rate within the

128

-sample budget, where bold and underline mark the best and second-best automated search methods and runs short of the budget are reported at the samples completed.

Figure 4: Bi-DexHands sample efficiency by task difficulty, as group-mean best-so-far success against reward samples, with the group-mean Sparse reference dashed.

Figure 5: Bi-DexHands candidate statistics per method: (a) success of all proposed candidates, (b) fractions clearing

0.5

and

0.8

, (c) mean success in the first versus last budget quartile.

Figure 6: Search progress on (a) Case14 by official score, and by mean relative gain over (b) the untrained policy on locomotion and (c) the environment reward on traffic. (d) arbo ’s gain over the baseline mean in candidate quality and final best-so-far, domains from dense to sparse feedback.

Figure 7: Performance loss from ablating (a) the history, by removing the belief, the observations, or interposing a retriever, (b) the schedule, by using only exploration or exploitation or removing the framework, and (c) normalized score by backbone.

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 8 — Figure 8: Bi-DexHands task environments.

Figure 9: L2RPN Case14 environment.

Panel of Figure 10 — Figure 10: RESCO traffic networks, with controlled signals in blue.

Panel of Figure 11 — Figure 11: Isaac Lab locomotion environments.

	Algo.	Policy network	Learn. rate	Budget per candidate	Sim. step
Bi-DexHands	PPO	MLP $512{-}256{-}128$	$3\times 10^{-4}$	$3000$ iterations	$1/60$ s
Grid2Op Case14	PPO	MLP $256{-}256$	$3\times 10^{-4}$	$10{,}240$ timesteps	$5$ min
Isaac Lab locomotion	PPO	MLP $128{-}128{-}128$ (flat) to $512{-}256{-}128$ (rough)	$1\times 10^{-3}$	$800$ iterations	$0.005$ s
RESCO	DQN	Conv $2{\times}2{\times}64$ , MLP $64{-}64$	$1\times 10^{-3}$	$40$ episodes	$10$ s

Appendix

Table 2: Policy-training configuration of the four oracles.

Parameter	Value
Locomotion samples	$72$
Other domains’ samples	$128$
Initial explore rounds, $n_{0}$	$5$
Exploit patience, $\mu$	$20$
Re-exploration burst, $\nu$	$5$

Appendix

Table 3: arbo search configuration for the main comparisons.

Backbone	Serving	Reasoning
MiniMax-M2.7	hosted API	yes
MiniMax-Text-01	hosted API	no
DeepSeek-V4-Flash	hosted API	yes
Qwen3.8-Max	hosted API	yes
Qwen3-32B	local $4$ -bit quantization	yes
Temperature	$0.7$ for every backbone

Appendix

Table 4: Backbone ablation configurations.

Environment	Specification
GPUs	$4\times$ NVIDIA GeForce RTX 4090, $48$ GiB memory each
CPU	Intel Xeon Platinum 8173M, $112$ threads
Memory	$503$ GiB
OS	Ubuntu 22.04.5 LTS
Software	NVIDIA driver $590.48.01$ , CUDA $13.1$

Appendix

Table 5: Hardware and software configuration.

Task	Mean	Range
Bi-DexHands
SwingCup	$44$	$11$ – $62$
LiftUnderarm	$73$	$56$ – $91$
DoorCloseOutward	$65$	$57$ – $73$
Over	$42$	$38$ – $47$
GraspAndPlace	$23$	$16$ – $32$

Appendix

Table 6: Per-candidate wall clock in minutes, mean and

10

th–

90

th percentile range.

Method	Prefill Tokens	Decode Tokens
Ours	176,961	21,671
RF-Agent	10,783	9,990
REvolve	3,940	3,488
Eureka	3,919	3,511
R $\star$	3,391	6,132
ShinkaEvolve	19,242	7,726

Appendix

Table 7: LLM tokens per attempted candidate, averaged over the ten Bi-DexHands tasks.

Method	Selection	Expansion
Eureka ( Ma et al., 2024c )	Previous batch’s best, one per prompt.	One fixed improvement template.
REvolve ( Hazra et al., 2025 )	Rank-weighted from an elite archive capped at $13$ , one or two per prompt.	Mutation or crossover at equal rates.
RF-Agent ( Gao et al., 2026 )	UCT over the tree, at most four nodes per prompt.	Fixed menu of five actions.
R $\star$ ( Li et al., 2025 )	Global best for reflection, two rank-sampled parents for crossover.	Reflection hint from {improve, remove, add} or module crossover, plus parameter alignment.
ShinkaEvolve ( Lange et al., 2026 )	Score-weighted parent, one archive and one top- $k$ inspiration, at most three.	Patch type from {diff, full, cross} at fixed rates.
Ours	Chosen by the agent with tools over the full history, failures included.	Free-form edits from its diagnosis, batch size its own.

Appendix

Table 8: Selection and expansion rules of the compared methods.

Panel of Figure 12 — Figure 12: Bi-DexHands search and training curves.

Figure 13: Case14 per-scenario survival.

Figure 14: Case14 line-loading trajectories.

Panel of Figure 15 — Figure 15: Locomotion search and training curves.

Figure 16: RESCO search and training curves.

Figure 17: History and schedule ablation search curves.

Figure 18: History and schedule ablation training curves.

Panel of Figure 19 — Figure 19: Backbone ablation search and training curves.

Resources	License	URL
Eureka ( Ma et al., 2024c )	MIT	https://github.com/eureka-research/Eureka
REvolve ( Hazra et al., 2025 )	Available online	https://github.com/RishiHazra/Revolve
RF-Agent ( Gao et al., 2026 )	Available online	https://github.com/deng-ai-lab/RF-Agent
ShinkaEvolve ( Lange et al., 2026 )	Apache 2.0	https://github.com/SakanaAI/ShinkaEvolve
Isaac Gym ( Makoviychuk et al., 2021 )	BSD 3-Clause	https://github.com/isaac-sim/IsaacGymEnvs
Bi-DexHands ( Chen et al., 2023 )	Apache 2.0	https://github.com/PKU-MARL/DexterousHands

Appendix

Table 9: Resource licenses and URLs.

Reward Design for RL

Reward design for reinforcement learning studies how to specify, learn, and adapt signals that guide agents toward intended behavior.

See all 250 papers

RF-Agent: Automated Reward Function Design via Language Agent Tree Search
Feb 27, 2026Ning Gao, Xiuhui Zhang, Xingyu Jiang +3Reward Design for RL RL Control
Beihang University, 37 Xueyuan Road, Haidian District, Beijing
RDA: Reward Design Agent for Reinforcement Learning
Jun 1, 2026Hojoon Lee, Ajay Subramanian, Ben Abbatematteo +4Agentic RL Reinforcement Learning
Meta · Holiday Robotics · Boston Dynamics
ROOT: Discovering Rewards for User-Specified Embodied Behaviors
Oct 3, 2026Eren Sadikoglu, Aditya Taparia, Xinyuan Liu +1Reward Design for RL Robotic RL
Robotics and Autonomous Systems, Arizona State University, Tempe, Arizona, USA · School of Computing and Augmented Intelligence, Arizona State University, Tempe, Arizona, USA

Feb 27, 2026J/K move · Enter open · S save

RF-Agent: Automated Reward Function Design via Language Agent Tree Search

Ning Gao, Xiuhui Zhang, Xingyu Jiang, Mukang You+2

Beihang University, 37 Xueyuan Road, Haidian District, Beijing

Reward Design for RL RL Control LLM-Guided RL

Open paper AskPDF arXiv

Designing efficient reward functions for low-level control tasks is a challenging problem. Recent research aims to reduce reliance on expert experience by using Large Language Models (LLMs) with task information to generate dense reward functions. These methods typically rely on training results as feedback, iteratively generating new reward functions with greedy or evolutionary algorithms. However, they suffer from poor utilization of historical feedback and inefficient search, resulting in limited improvements in complex control tasks. To address this challenge, we propose RF-Agent, a framework that treats LLMs as language agents and frames reward function design as a sequential decision-making process, enhancing optimization through better contextual reasoning. RF-Agent integrates Monte Carlo Tree Search (MCTS) to manage the reward design and optimization process, leveraging the multi-stage contextual reasoning ability of LLMs. This approach better utilizes historical information and improves search efficiency to identify promising reward functions. Outstanding experimental results in 17 diverse low-level control tasks demonstrate the effectiveness of our method. The source code is available at https://github.com/deng-ai-lab/RF-Agent.

Abstract

Reward Design for RL

Explore similar work

RF-Agent: Automated Reward Function Design via Language Agent Tree Search

RDA: Reward Design Agent for Reinforcement Learning

ROOT: Discovering Rewards for User-Specified Embodied Behaviors