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
- Mudit Verma (ORCID: https://orcid.org/0009-0008-7191-4519)
- Shyam Sundar Nambiraja
- Ryan Steubs
- Soham Patil
- Terence Agius
- Jeet Patel
- Kwaai Alignment Lab
- Brian Ragazzi
- Sathish Kumar
- Mohit Gupta
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