Exact agent evaluation and failure analysis for self-play Q-learning
- Question
- Can apparently competent self-play Q-policies still be systematically exploitable?
- Result
- Exact best-response evaluation found force-loss exploits in 6/6 baseline checkpoint-seat policies. Controlled changes reduced this to 0/6.
- Contribution
- A reproducible failure-analysis study separating sampled opponent robustness, adversarial Bellman objectives, and symmetry-aware evidence pooling.
- Evidence
- Public repository · frozen checkpoints · exact best-response evaluator · controlled experiment reports · 24-test suite · machine-readable metrics
Research question
Sampled matches can make a self-play agent look competent while leaving a systematic counter-policy undiscovered. This study asks which failures become visible when every frozen policy is evaluated against an exact best response, and which controlled interventions remove them under matched Q-update budgets.
Tic-Tac-Toe is used as an exhaustively searchable testbed, not as the product. The focus is agent evaluation, causal failure analysis, and reproducible experimental reasoning.
Controlled experiment chain
| Method | Force-loss exploitable policies | Strategic tests |
|---|---|---|
| Sampled self-play | 6/6 | 16/21 |
| + Opponent mixture | 6/6 | 20/21 |
| + Adversarial backup | 4/6 | 20/21 |
| + Adversarial backup + D4 | 0/6 | 21/21 |
Opponent mixture improved sampled behavior and repaired a visible local error, but exact evaluation still found all six policies exploitable. Changing the Bellman backup to minimize over legal opponent responses reduced exploitability to 4/6 and changed the residual failure from confident misvaluation to sparse updates and unresolved ties. D4 canonicalization then pooled equivalent evidence across rotations and reflections without increasing the update budget.
Mechanism evidence
- Reachable states compressed from 4,520 to 627.
- Reachable state-actions compressed from 16,167 to 2,270.
- A historical sparse state went from 29 raw-orientation visits to 169 pooled visits.
- Final policies selected exact-optimal greedy actions in 99.93–99.96% of reachable states.
- All six final fixed policy/seat cases had zero force-loss vulnerabilities.
Reproducibility and limits
The repository includes fixed seeds, twelve frozen checkpoints, machine-readable metrics, exact exploit trajectories, experiment reports, and tests covering perspective semantics, terminal backups, legal actions, exact best response, and D4 mappings. The technical research note explains the causal chain and evidence boundary.