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

arXiv: https://arxiv.org/abs/2609.32394 · HTML: https://mlsanity.com/paper/2609.32394/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 37 of its 63 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 30 of 37)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [MemGPT: Towards LLMs as Operating Systems](https://mlsanity.com/paper/2310.08560/) (2023)
- [Isaac Gym: High Performance GPU-Based Physics Simulation For Robot Learning](https://mlsanity.com/paper/2108.10470/) (2021)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Eureka: Human-Level Reward Design via Coding Large Language Models](https://mlsanity.com/paper/2310.12931/) (2023)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [Learning to Walk in Minutes Using Massively Parallel Deep Reinforcement Learning](https://mlsanity.com/paper/2109.11978/) (2021)
- [Language to Rewards for Robotic Skill Synthesis](https://mlsanity.com/paper/2306.08647/) (2023)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [ShinkaEvolve: Towards Open-Ended And Sample-Efficient Program Evolution](https://mlsanity.com/paper/2509.19349/) (2025)
- [RL-VLM-F: Reinforcement Learning from Vision Language Foundation Model Feedback](https://mlsanity.com/paper/2402.03681/) (2024)
- [Evolution through Large Models](https://mlsanity.com/paper/2206.08896/) (2022)
- [Language Model Crossover: Variation through Few-Shot Prompting](https://mlsanity.com/paper/2302.12170/) (2023)
- [Evolutionary Computation in the Era of Large Language Model: Survey and Roadmap](https://mlsanity.com/paper/2401.10034/) (2024)
- [LLM and Simulation as Bilevel Optimizers: A New Paradigm to Advance Physical Scientific Discovery](https://mlsanity.com/paper/2405.09783/) (2024)
- [DrEureka: Language Model Guided Sim-To-Real Transfer](https://mlsanity.com/paper/2406.01967/) (2024)
- [Learning to run a Power Network Challenge: a Retrospective Analysis](https://mlsanity.com/paper/2103.03104/) (2021)
- [CodeEvolve: an open source evolutionary coding agent for algorithmic discovery and optimization](https://mlsanity.com/paper/2510.14150/) (2025)
- [MetaBox: A Benchmark Platform for Meta-Black-Box Optimization with Reinforcement Learning](https://mlsanity.com/paper/2310.08252/) (2023)
- [Learning to run a power network challenge for training topology controllers](https://mlsanity.com/paper/1912.04211/) (2019)
- [REvolve: Reward Evolution with Large Language Models using Human Feedback](https://mlsanity.com/paper/2406.01309/) (2024)
- [Learning Reward for Robot Skills Using Large Language Models via Self-Alignment](https://mlsanity.com/paper/2405.07162/) (2024)
- [RHO: Your Coding Agent is Secretly a Roboticist](https://mlsanity.com/paper/2606.16458/) (2026)

## Abstract (arXiv)

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.