An Exact and Black-Box Admission Method for Generated Environments with Shortcut Probability Estimated from Replays

We study the admission of generated environments in reinforcement learning with verifiable rewards (RLVR), in which a generator produces environments, a verifier admits some of them, and the policy is paid by a checkable success flag. A check that the intended solution exists says nothing about the other routes to the flag, and training is paid to find the cheapest of them. When the environment is explicit, its soundness can be checked exactly; when it is only a simulator that we can replay, the designer needs an estimate of this probability and its price. We consider that the learner is the optimum of a reward regularised by its divergence from a uniform reference, and we call its probability of an unintended success the shortcut probability. We investigate how many replays a black box needs to test this probability, to estimate it to a relative error, and to do so without being told anything about the instance, and whether trained learners land on it. Via theoretical and experimental results, we show that estimation needs exhaustive replay up to a crossover depth that the regulariser sets and sampling beyond it; that an interleaved estimator is instance-adaptive within a logarithmic factor of a price with a variance term and a range term, while in the worst case, at small regularisation, no estimator attains the variance term alone; and that our deployable estimator, which picks its depth from a pilot and stops on an empirical Bernstein rule, kept its guarantee in every run and needed 55 times fewer replays than the stopping-rule Monte Carlo of Dagum et al. at the same guarantee on a family with hidden short shortcuts (median of 200 environments), and 1.7 to 5·103 times fewer on six generated families, although there it pays far more than an oracle Monte Carlo. We also find that a policy-gradient learner that missed the closed form by 0.47 was not converged: its entropy collapsed early, and with a step of 0.02 (24 environments) or with exact gradients from the uniform policy it lands on the closed form. This record holds the compiled paper (PDF) and its LaTeX source. A companion software record with the code, the saved outputs of every run and call, and the scripts that recompute every number in the paper will follow and will be linked to this record.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-20
DOI
https://doi.org/10.5281/zenodo.24408549
Primary Topic
Reinforcement Learning in Robotics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

An Exact and Black-Box Admission Method for Generated Environments with Shortcut Probability Estimated from Replays

Mudit Verma, Shyam Sundar Nambiraja, Ryan Steubs, Soham Patil et al.
Zenodo (CERN European Organization for Nuclear Research)
Reinforcement Learning in Robotics
preprint

An Exact and Black-Box Admission Method for Generated Environments with Shortcut Probability Estimated from Replays

Mudit Verma, Shyam Sundar Nambiraja, Ryan Steubs, Soham Patil, Terence Agius, Jeet Patel, Kwaai Alignment Lab, Brian Ragazzi, Sathish Kumar, Mohit Gupta
preprint en

Abstract

We study the admission of generated environments in reinforcement learning with verifiable rewards (RLVR), in which a generator produces environments, a verifier admits some of them, and the policy is paid by a checkable success flag. A check that the intended solution exists says nothing about the other routes to the flag, and training is paid to find the cheapest of them. When the environment is explicit, its soundness can be checked exactly; when it is only a simulator that we can replay, the designer needs an estimate of this probability and its price. We consider that the learner is the optimum of a reward regularised by its divergence from a uniform reference, and we call its probability of an unintended success the shortcut probability. We investigate how many replays a black box needs to test this probability, to estimate it to a relative error, and to do so without being told anything about the instance, and whether trained learners land on it. Via theoretical and experimental results, we show that estimation needs exhaustive replay up to a crossover depth that the regulariser sets and sampling beyond it; that an interleaved estimator is instance-adaptive within a logarithmic factor of a price with a variance term and a range term, while in the worst case, at small regularisation, no estimator attains the variance term alone; and that our deployable estimator, which picks its depth from a pilot and stops on an empirical Bernstein rule, kept its guarantee in every run and needed 55 times fewer replays than the stopping-rule Monte Carlo of Dagum et al. at the same guarantee on a family with hidden short shortcuts (median of 200 environments), and 1.7 to 5·103 times fewer on six generated families, although there it pays far more than an oracle Monte Carlo. We also find that a policy-gradient learner that missed the closed form by 0.47 was not converged: its entropy collapsed early, and with a step of 0.02 (24 environments) or with exact gradients from the uniform policy it lands on the closed form. This record holds the compiled paper (PDF) and its LaTeX source. A companion software record with the code, the saved outputs of every run and call, and the scripts that recompute every number in the paper will follow and will be linked to this record.

Zenodo (CERN European Organization for Nuclear Research)
Reinforcement Learning in Robotics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon