Skip to content

Environment-Grounded Automated Prompt Optimization for LLM Game Agents

🕒 Published (v1): 2026-06-16 12:06 UTC · Source: Arxiv · link

Why this paper was selected

Lindauer & Feurer (top AutoML); automated prompt optimization as harness tuning layer

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

RAPOA (Reward-driven Automatic Prompt Optimisation for Agentic systems) is an automated framework that decomposes an LLM game agent into a descriptor sub-agent and an action-selection sub-agent, then iteratively refines both prompts via an LLM-driven evolutionary loop guided by environment reward signals. On the hardest BabyAI task (PutNext), RAPOA lifts success rate from 0% to 72.5% without any weight updates. The framework generalizes to monolithic agents as well, improving BALROG's RobustCoTAgent from 29.3% to 49.0% mean success.

Problem

Prompt engineering for LLM agents deployed in interactive environments is manual, task-specific, and brittle—small prompt changes cause large performance swings (e.g., BALROG's monolithic agent varies from 29.3% to 58.5% success across plain vs. guided prompts). Existing automated prompt optimization methods (APE, OPRO, ProTeGi) optimize against fixed datasets, making them prone to dataset overfitting and unable to exploit live environment feedback. Multi-agent decompositions compound the problem by requiring jointly functional prompts across sub-agents.

Method

RAPOA models the agent as a DAG of sub-agents \(\{A, E^A\}\), each with its own prompt \(p_i\), and optimizes the joint prompt set \(P^* \in \arg\max_P J(\pi^P)\) using environment return as the sole signal.

The core architecture is a Split Perception Action (SPA) agent: a descriptor agent \(A_\text{des}: O \to G\) that converts raw observations into goal-conditioned summaries, chained to an action-selection agent \(A_\text{act}: G \to A\).

The optimization loop (Algorithm 1): 1. Rollout phase: collect \(k_\text{opt}\) episodes with fresh seeds. 2. Behavior Analyzer (BA): an LLM prompted to analyze \(l\) sampled trajectories, identify failure modes and successes, attribute them to specific sub-agents, and produce a severity-ranked list of (issue, sub-agent) pairs. 3. Mutator: an LLM that rewrites the implicated sub-agent's prompt targeting the identified failure mode. 4. Two-stage acceptance test: the mutated system must exceed current performance by threshold \(\delta\) on both in-loop seeds \(S_\text{opt}\) and held-out selection seeds \(S_\text{select}\); accepted mutations trigger immediate restart of the inner loop.

Two selection-pressure modes are evaluated: HSP (high, must improve mean over all \(S_\text{opt}\)) and LSP (low, must improve only over the sampled candidate trajectories \(S_\text{cand} \subseteq S_\text{opt}\), with \(S_\text{select}\) as safeguard).

Key Contributions

  • An automated Interaction Prompt Optimization (IPO) framework that uses environment reward as the optimization signal in place of static datasets, applicable to both monolithic and multi-agent LLM systems.
  • A Behavior Analyzer module that attributes trajectory outcomes to specific sub-agents and ranks failure modes by severity, enabling targeted per-sub-agent prompt mutation.
  • A two-stage acceptance criterion (in-loop + held-out seeds) with configurable selection pressure, preventing prompt drift while maintaining sufficient mutation acceptance rate.
  • Empirical demonstration on all five BALROG/BabyAI tasks showing consistent improvement over non-optimized baselines, with PutNext 0% → 72.5% as the headline result.

Results

  • PutNext (hardest): SPA baseline 0%, RAPOA best 72.5% (LSP, guided, \(\delta=0.05\)).
  • SPA guided, mean across 5 tasks: 65.5% (non-optimized) → 79.2% (optimized best), +13.7pp.
  • SPA plain, mean across 5 tasks: 59.8% → 62.2% (optimized best).
  • BALROG RobustCoTAgent (monolithic, plain/16-step): 29.3% → 49.0%, +19.7pp.
  • SPA plain (no task-specific guidance, 1-step history) matches BALROG guided/16-step (both ~58–59%), demonstrating decomposition's robustness.
  • Tasks near ceiling pre-optimization (GoTo, PickUp with guided prompts) accept few or no mutations and remain unchanged, confirming the optimizer avoids unnecessary drift.
  • Ablation: always-accept (\(\delta = -\infty\)) can find high-performing prompts transiently but does not preserve them; the acceptance gate is necessary for monotonic improvement.

Limitations

  • Evaluated on a single LLM (GPT-OSS20B at temperature 0.6); generalization to other model families is unverified.
  • Optimization uses a fixed single environment seed (42) and inference seed, so optimized prompts may overfit to that seed's distribution; held-out evaluation uses separate seeds but the optimization budget is small (\(N=20\) cycles).
  • The SPA architecture is fixed (two sub-agents in a chain); the framework does not search over agent graph topologies.
  • The Behavior Analyzer and Mutator receive privileged environment physics information that the runtime agents do not, creating an asymmetry that may not generalize to domains without such oracle descriptions.
  • Computational cost of iterative environment rollouts during optimization is not analyzed; no wall-clock or API-call budgets are reported.

Relevance to Harnesses / Meta-Harnesses

RAPOA is a concrete instance of a meta-harness: a self-modifying outer loop that governs a population of inner agent modules (descriptor + actor), using environment-grounded feedback to rewrite the sub-agents' instruction prompts. The Behavior Analyzer functions as a meta-level critic that introspects sub-agent behavior and routes targeted edits—structurally analogous to a harness coordinator that selects which module to reconfigure next. The two-stage acceptance gate (in-loop + held-out seeds) is a harness-level validation step that prevents inner-loop overfitting, a pattern directly applicable to any meta-harness that must gatekeep automated self-modification. For researchers tracking harnesses, this paper provides an end-to-end worked example of reward-driven prompt evolution with formal convergence criteria, severity-ordered module selection, and ablations that isolate the contribution of the acceptance mechanism.