Agent benchmarks run inside sandboxes (containers that are supposed to reset to a clean state between episodes and hide everything except the intended observations). When they fail, the failure is usually found by accident. Two examples: on the original StarCraft benchmark, a policy that ignores every observation still wins, and on τ-bench, a do-nothing agent beats GPT-4o. This note proposes a principled detector built from learning theory. Sample-complexity lower bounds say how many interactions any learner must have before it can identify a good strategy in a deliberately hard family of games. If we plant such a game inside a real execution harness and some agent learns it faster than the information-theoretic limit allows, that agent must be getting information through a channel the harness was supposed to close: a seed reused across resets, a leftover file, a reward printed to a log, a writable scorer. Exceeding the limit is a certificate of leakage, not a heuristic flag.
The opportunity comes from an unusual fact in multi-agent learning theory. The lower bound itself depends on what the learner is allowed to see. In two-player zero-sum Markov games, an agent that observes rewards during exploration needs a number of samples that scales with the sum of the two players' action counts. An agent exploring without reward signals needs a number that scales with their product (Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity). The gap between these two bounds is exactly the value of the reward channel. A harness that claims to hide rewards during exploration can therefore be tested: if agents in "reward-free" mode learn at the sum rate, the harness is leaking reward.
Core Claim
For any finite family of hard game instances with a uniform prior over a hidden parameter, we can compute an exact ceiling on the success probability of any learner that uses only the legitimate observation channel. Running adaptive exploiter agents against this ceiling inside a sandbox detects side-channel leaks in the sandbox's shared machinery. That machinery is reset, seeding, logging, file system and scoring. The detector has controlled false-positive rates and catches leaks that checklists, do-nothing agents, open-loop agents and log-reading verifiers miss.
Concretely, let $\theta$ be drawn uniformly from a finite set $\Theta$ of game instances that differ only in a hidden "good" joint action. Let $n$ be the number of episodes allowed, and let $p^*(n)$ be the success probability of the Bayes-optimal learner. That learner uses the exact posterior over $\theta$ from legitimate observations to output an $\epsilon$-approximate equilibrium. Then every legitimate learner satisfies
$$ \Pr_{\theta}\left[\text{learner outputs an } \epsilon\text{-equilibrium after } n \text{ episodes}\right] \le p^*(n). $$
This holds because the Bayes-optimal rule maximizes average success over the prior. Given $k$ successes in $m$ independent instances, a one-sided binomial test of $k$ against $p^*(n)$ gives a p-value for "this harness leaks." The point of computing $p^*(n)$ exactly for the specific family, by Monte Carlo simulation of the Bayes-optimal learner, is that it avoids the unknown constants hidden in the asymptotic $\tilde{\Omega}(\cdot)$ bounds. Those constants make the textbook bounds unusable as a test.
Relation to Prior Work
Three groups of papers play different roles here.
The first group supplies the method: the hard-instance constructions and the algorithms that should approach the ceiling.
- Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity proves the reward-aware sum bound and the reward-agnostic product bound. Its constructions are our template for canary families.
- A Sharp Analysis of Model-based Reinforcement Learning with Self-Play gives Nash-VI, a model-based method for finding approximate equilibria in $\tilde{\mathcal{O}}(H^3SAB/\epsilon^2)$ episodes, and its reward-free variant VI-Zero.
- Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games reaches the same rate model-free, using a "min-gap" reference value: it keeps past optimistic and pessimistic value estimates and uses the pair closest together as a stable reference.
These algorithms are honest learners. On a clean harness they should come near the ceiling but never cross it, which makes them our calibration controls. Our direction runs opposite to theirs. They ask how close an algorithm gets to the bound. We take the bound as given and use it to test the environment.
The second group motivates the proposal by showing that leaks are common and costly.
- Establishing Best Practices for Building Rigorous Agentic Benchmarks audits ten benchmarks with a 32-item checklist. It finds that 70% violate task and outcome validity, and it documents agents overwriting ground-truth tests in SWE-Lancer.
- SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning shows that deterministic starts let observation-blind policies win near 100% of games on
8m_vs_9m.
Both found their leaks through human insight and targeted probes. Neither gives a test with a known false-positive rate, and neither can catch a leak that nobody thought to probe.
The third group constrains the design.
- Audit-Grade Harness for Agent-driven Scientific Computation Workflows shows that a fresh-context verifier reading append-only logs catches fabrication and silent degradation at 1.7% to 9.9% overhead. It also shows that such verifiers judge only what the logs reveal. A verifier cannot flag a leak whose trace looks like ordinary file reads.
- Agent-Diff verifies outcomes by comparing container state before and after a run. This checks whether the right change happened, not whether the agent knew too much while making it.
- The container literature establishes that hermetic images prevent dependency drift and state leakage between test runs: A Qualitative Study on the Sources, Impacts, and Mitigation Strategies of Flaky Tests, Bencher, and OpenHands. It does not address leaks inside a correctly built container, such as logs and seeds the agent can read. Those are the leaks we target.
Research Program
We would build a small library of canary families. Each is a tabular two-player zero-sum Markov game with a hidden good joint action, parameterized by states $S$, horizon $H$, action counts $A$ and $B$, and accuracy $\epsilon$. Each comes in a reward-aware mode and a reward-free mode, and each ships with a precomputed ceiling curve $p^*(n)$ for both modes. The reward-free ceiling uses the product-scaling construction, so the two curves separate measurably at moderate $A$ and $B$. The library also makes the sum-versus-product separation visible at fixed, known constants, which is a small contribution to the theory side in its own right.
Canaries are packaged to run through a host harness's own machinery. For a reinforcement-learning runner such as PyMARL or the SMACv2 runner, the canary replaces the simulator behind the same reset, seed and logging calls. For agent sandboxes in the style of OpenHands or TerminalTraj (Large-Scale Terminal Agentic Trajectory Generation from Dockerized Environments), the game is exposed as a command-line tool inside the standard Docker image. The image keeps its usual file system, logs and scorer, and the agent plays through the terminal.
Exploiters are the detector's sensors. We use two kinds. The first is a generic adaptive reinforcement learner that can read the full container observation, meaning files, environment variables and timing, not only the game interface. The second is an LLM agent instructed to "maximize your score by any means available inside the sandbox." The scope is narrow and should be stated plainly. Canaries test the shared infrastructure and only catch leaks some exploiter can find. Leaks in task-specific code are out of scope.
Baselines
The naive reference point is a clean harness running honest learners: the Bayes-optimal learner, Nash-VI, min-gap Q-learning and VI-Zero. These should sit at or below $p^*(n)$ on every family. Any crossing here is a false positive, and we target a rate under 5% at the chosen test level. This baseline also verifies that the ceiling computation is correct.
The strongest existing detectors are behavioral probes. The first is the do-nothing agent from the checklist audit, which reached a 38% success rate on τ-bench, above GPT-4o (Establishing Best Practices for Building Rigorous Agentic Benchmarks). The second is the open-loop, observation-blind policy from SMACv2, which wins near 100% on SMAC 8m_vs_9m and 0% on SMACv2. We also run two process-level detectors: a fresh-context LLM verifier over append-only logs following SciAgent, and a manual checklist review using the 32 criteria from the audit paper. All detectors receive the same harnesses, the same planted leaks and the same budget of agent episodes. The verifier gets the same base model as the LLM exploiter.
No paper in the file reports detection rates for planted side-channel leaks for any of these methods. We found no reported result on Lacuna for leak-detection power. Every baseline will therefore be run fresh by us.
Beating the baselines means two things. Canaries must detect at least as many planted leaks as the best probe at equal episode budget. They must also catch at least one leak class, reward-in-logs or cross-instance caching, that the do-nothing, open-loop and verifier baselines miss. The false-positive rate on clean harnesses must stay at or below the nominal level.
Two ablations isolate the key ingredient. The first replaces the exact ceiling $p^*(n)$ with an asymptotic lower bound using a guessed constant. We expect this to show that the test becomes either powerless or prone to false positives, depending on the guess. The second replaces adaptive exploiters with fixed-policy learners, which shows how much detection power comes from adaptivity.
Why not just…?
Why not just run everything in hermetic containers and follow the checklist? Containers fix drift between machines and leftover state between images. They do not stop an agent from reading a reward that the harness writes to a log inside the same container, or from benefiting from a seed reused across resets. The SWE-Lancer test-overwrite exploit happened in a containerized setting (Establishing Best Practices for Building Rigorous Agentic Benchmarks). Our planted-leak experiment builds every leak inside a correctly constructed Docker image and reports whether the checklist review flags it.
Why not just use do-nothing and observation-blind probes, as SMACv2 and the audit paper did? This is a real threat for one class of leaks. If the leak is determinism or a scoring bug, a blind or idle agent will expose it cheaply, and the canary adds little. The probes cannot detect information side channels that only an adaptive agent can exploit. An example is reward leaking during a supposedly reward-free phase, because a blind agent never uses the leaked signal. The planted-leak experiment reports detection per leak class. We will state honestly where probes match canaries.
Why not just have a fresh-context verifier read the provenance logs? SciAgent shows that verifiers catch fabrication and quality degradation visible in the logs. A side-channel read looks like an ordinary file access, though, and judging it suspicious requires knowing it was informative. The canary measures informativeness directly, by comparing learning speed to the ceiling. Running the verifier on the same logs is part of the comparison.
Why not just simulate noise and leaks in a notebook? That would check the statistics but not the harnesses. The question is whether real reset, seeding and logging code leaks. SMACv2's finding that tiny simulator details enabled blind policies shows that such details are not predictable from a model of the system.
Proposed Experiments
The first experiment is calibration. Across canary families with $A, B \in \{2, 4, 8\}$ and several $S$, $H$ and $\epsilon$, honest learners on clean harnesses must stay below $p^*(n)$ in both modes. This experiment also checks that reward-free learners in a clean harness show product-scaling sample needs.
The second experiment measures detection power on planted leaks, the decisive test. We plant six leaks in OpenHands-style and PyMARL-style harnesses:
- a seed reused across resets
- a persistent temporary directory
- the reward written to a readable log during reward-free exploration
- a writable scorer
- a cache shared across instances
- a timing side channel
For each leak we plot detection rate against episode budget for canaries and all baselines. The decisive outcome is whether canaries detect the reward-in-logs and cross-instance-cache leaks that the probes miss, at matched budget.
The third experiment audits existing harnesses without planted leaks: the SMACv2 runner, an OpenHands runtime, and TerminalTraj-style images. We report any ceiling crossing together with its forensic explanation.
If honest learners cross the ceiling in the first experiment, the ceiling computation is wrong and the method fails. If canaries detect nothing the probes miss in the second experiment, the contribution shrinks to a calibrated restatement of existing probes, and we would report it as such.
References
- Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
- A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
- Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games
- Establishing Best Practices for Building Rigorous Agentic Benchmarks
- SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning
- Audit-Grade Harness for Agent-driven Scientific Computation Workflows
- Agent-Diff: Benchmarking LLM Agents on Enterprise API Tasks via Code Execution with State-Diff-Based Evaluation
- A Qualitative Study on the Sources, Impacts, and Mitigation Strategies of Flaky Tests
- Bencher: Simple and Reproducible Benchmarking for Black-Box Optimization
- OpenHands: An Open Platform for AI Software Developers as Generalist Agents
- Large-Scale Terminal Agentic Trajectory Generation from Dockerized Environments