Search papers, labs, and topics across Lattice.
This paper introduces budget-constrained confidence-scheduled restricted responses (CS-RNR), a novel method for safe opponent exploitation in two-player zero-sum imperfect-information games. By allowing agents to compute a self-audited certificate for their strategies, CS-RNR ensures that every exploit is backed by a confidence guarantee, effectively managing the trade-off between risk and reward. In experiments with Leduc hold'em, CS-RNR achieved a remarkable $6.2\times$ gain over traditional methods while adhering to budget constraints, demonstrating its effectiveness across multiple game scenarios.
Agents can now exploit flawed opponents safely, achieving up to 13.6 times the expected budget gain while certifying their own strategies.
An agent playing a Nash-equilibrium strategy in a two-player zero-sum imperfect-information game secures the game value but forfeits the additional value offered by a flawed opponent. Diffuse deviations pose a particular challenge: binary release rules may gather too little evidence to act, while a full best response to an incomplete opponent model can be highly exploitable. We introduce \emph{budget-constrained confidence-scheduled restricted responses} (CS-RNR), the first opponent-exploitation method whose safety guarantee is a certificate the agent computes on the strategy it actually deploys, so that every exploit it commits to is one it has audited itself. The method tracks pooled action frequencies with anytime-valid confidence sequences and treats a frequency as exploitable only once its interval separates from an equilibrium reference. The confirmed deviations define a conservative opponent model, which a restricted-response solve turns into candidate counter-strategies over a grid of pin levels. Before deployment, each complete candidate is evaluated by a full-tree best response. The resulting certificate is compared with a user-specified budget and committed atomically with the strategy. Because this check is performed on the played strategy, model quality determines the exploitation achieved while the certificate controls reference-relative expected loss. In Leduc hold'em, CS-RNR obtains $6.2\times$ the steady-state gain of a money-verified binary gate while keeping every deployed strategy within budget. A trajectory mixture using the same estimator reaches $13.6\times$ the budget. Across Leduc, Liar's Dice, and 5-rank Leduc, all $36{,}000$ audited hands satisfy the reported certificate tolerance.
Tsinghua AI