RevengeBench: Reverse Engineering Code-Space Policies from Behavioral Experiments

RevengeBench: Reverse Engineering Code-Space Policies from Behavioral Experiments§

Core Problem§

Reconstructing an unknown agent's decision policy as executable code given only observations of its behavior in game environments, with the ability to design targeted experiments (custom opponent policies).

Methodology§

1. Target Policy Generation: 75 policies are generated by LLMs as Python functions across 5 CodeClash game environments. Policies are Elo-calibrated to ensure varied strengths.
2. Observation Phase: The learner (another LLM) observes the hidden target policy play against a set of default opponents, producing behavioral traces.
3. Experimental Design: The learner can iteratively propose custom opponent policies (behavioral probes) to elicit more informative traces from the target.
4. Hypothesis Submission: The learner submits an executable hypothesis policy (Python code) which is evaluated against the true policy using continuous action-distance metrics.
5. Evaluation: Action-distance $d(a, a') = 1 - \frac{a \cdot a'}{\|a\|\|a'\|}$ (cosine distance) between action embeddings (one-hot encoding or learned). Recovery quality is defined as the fraction of initial distance closed: $Q = \frac{d_{\text{initial}} - d_{\text{final}}}{d_{\text{initial}}}$.
6. Downstream Validation: Recovered policies are used in player-vs-player tournaments to measure competitive advantage.

Key Results§

• Reconstructed policies provide measurable win rate improvements, especially for weaker models that struggle to design effective counter-strategies.
• The ability to design controlled experiments improves recovery by up to 20% over passive observation.

Code Example§

import openai

def recover_policy(traces, environment_name):
    prompt = f"""You are observing traces from an opponent in {environment_name}.
Traces: {traces}
Write a Python function `policy(state) -> action` that predicts the opponent's next action.
Return only the function code."""
    response = openai.ChatCompletion.create(
        model="gpt-4",
        messages=[{"role": "user", "content": prompt}],
        max_tokens=500
    )
    code = response.choices[0].message.content
    # extract code block if needed
    return code

Mathematical Formulation§

Let $\pi_{\theta}$ be the true policy parameterized by code $\theta$, $\mathcal{T}$ be the set of traces against default opponents, and $\mathcal{P}$ be the set of probe opponents designed by the learner. The learner's objective: $$ \hat{\theta} = \arg\min_{\theta'} \mathbb{E}_{\tau \sim (\mathcal{T} \cup \mathcal{P})} [d(\pi_{\theta}(\tau), \pi_{\theta'}(\tau))] $$ where $d$ is the action-distance metric. The optimization is performed implicitly by the LLM generating code that minimizes this expected distance.

Contributions§

• Formalizes behavioral recovery of programmatic policies as a tractable inverse problem.
• Provides a benchmark with multiple environments, policies, and metrics.
• Demonstrates that recovered policies carry actionable information for downstream tasks (tournament play).
• Highlights the importance of active probing in inverse problems.

Implications§

This work opens avenues for opponent modeling, policy interpretability, and understanding how to infer latent mechanisms from observations.