acceptodds
Desk rejected at ICLR 2027

Certifying Tactical Mistakes in Self-Play Reinforcement Learning

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Self-play scores can conceal decisions that discard a forced win because sampled opponents fail to refute them. We present a certificate-based audit that turns local tactical proofs into executable opponent responses and quantitative guarantees on their value. The audit distinguishes mistakes on the realized deal from winning actions identifiable using the player's observations. Each denial witness supplies a payoff cap for a responding coalition, reducing certified response optimization to optimal stopping under ordinary self-play. A paired martingale-dual score bounds a fixed switching rule's regret within this response class, using exact conditional values or independent successor simulation. We give a sharp coefficient-one residual bound for predictor-greedy rules and an exact-boundary absorption result. In complete games of a sampled proximal policy optimization (PPO) policy, a simulated switching rule has mean certified score points per game, with stopping regret below points at 95% confidence. Across enumerable stochastic endgames, exact regret is and the paired dual bound is . Refutation replay denies first place on all audited throws. As a further use of the audit, reusing the certified action sets in training raises sampled retention from to on a fixed Tien Len challenge set over five independent runs.

Primary area:
reinforcement learning
Keywords:
self-play reinforcement learning, policy auditing, certified opponent responses, tactical certification, adversarial evaluation, optimal stopping, martingale duality, imperfect-information games

Related papers

Discussion (0)

Sign in to comment.