This research note accompanies the Q-Learning Exploitability project and its public repository.
1. The surprising failure
The agent looked competent. It drew every game against the original heuristic, won most games against random play, and produced plausible moves. Then an exact best-response search showed that every one of six seed-and-seat policies could be forced to lose.
Tic-Tac-Toe is useful here precisely because it is small. Instead of treating sampled reward curves or win rates as proxies, I could exhaustively ask whether an opponent strategy exists that defeats a frozen policy.
2. Why sampled evaluation was misleading
Self-play generates its own training distribution. A policy can become effective
against the behaviors produced by its co-evolving counterpart without assigning
correct values to alternative legal responses. The clearest counterexample was
baseline seed 211 as O from ..X/.../...: after roughly 1,000 visits it confidently
preferred a losing side move over the only drawing center move.
This was an observability result as much as an RL result. Aggregate W/D/L had hidden a specific, reproducible, high-confidence failure.
3. Exact best-response evaluation
I froze each Q-table and made its greedy decisions deterministic for audit. On opponent turns, a complete search selected the branch minimizing the Q-agent’s eventual outcome. This is a best response to a fixed policy, not symmetric Minimax play: only the opponent branches, while the Q-agent remains committed to its learned choices.
The evaluator also counted losing opening responses and every reachable Q-state from which an adversary could force a loss. Those metrics showed whether an intervention merely moved an exploit or actually reduced the vulnerable region.
4. Opponent diversity helps—but does not solve it
The first controlled intervention changed only the episode-level opponent mix: 75% shared self-play, 12.5% randomized heuristic, and 12.5% fork-aware heuristic. Q-update budgets stayed matched.
Strategic fixtures improved from 16/21 to 20/21. The seed-211 local error was corrected, and sampled losses to the stronger heuristics disappeared. Exact exploitability, however, remained 6/6 with unchanged shortest paths. More diverse experience improved sampled robustness without changing what the Bellman target was estimating.
5. Changing the Bellman backup
The baseline target used the response actually sampled during training:
target = r_b + γ max_a Q(s_b, a).
The next intervention enumerated every legal opponent response and backed up the worst estimated continuation:
target = min_b [r_b + γ max_a Q(s_b, a)].
The implementation constructs every successor from the original learner’s perspective; it does not minimize Q-values expressed from the opponent’s plane semantics. Immediate wins, losses, and draws are terminal values. The exact game solver remains evaluation-only, so training is not receiving oracle labels.
This reduced force-loss policies from 6/6 to 4/6. Two first-player policies now drew against exact best response, and vulnerable reachable-state fractions fell to 0.9–3.8% in the remaining cases.
6. The remaining sparse-state failure
The intervention changed the failure mode. In a seed-101 second-player exploit,
OX./..X/... appeared only 29 times and the selected action had four updates.
Several actions remained tied at zero even though exact outcomes ranged from a
forced win to a forced loss. High-confidence systematic misvaluation had given
way to sparse Bellman propagation and unresolved ties.
That distinction determined the next experiment. More opponents would not directly address evidence split across equivalent board orientations.
7. D4 symmetry as evidence pooling
Tic-Tac-Toe has eight rotations and reflections. I canonicalized the player- relative board only after fixing plane semantics, transformed action indices with the same reversible mapping, and stored one Q-vector per canonical state.
The reachable representation shrank from 4,520 to 627 states and from 16,167 to 2,270 state-action pairs. For the sparse failure state, eight orientations pooled 169 visits and the winning action received 78 equivalent updates. Its ranking became Win > Draw > Loss.
8. Final results
| Method | Force-loss policies | Strategic fixtures |
|---|---|---|
| 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 |
Across all 4,520 reachable states, final greedy actions were exact-optimal in 99.93–99.96% of cases. More importantly, all six final seed-and-seat policies had zero losing states in their reachable regions.
9. What this experiment does and does not show
In this implementation, sampled self-play evaluation concealed exploitability; opponent diversity alone did not eliminate it; pessimistic opponent-response backups materially reduced it; and symmetry-aware evidence pooling removed the remaining reachable forced-loss vulnerabilities under the same update budget.
This is not a new RL algorithm or a general proof about self-play. Tic-Tac-Toe is deterministic, fully observable, discrete, and exhaustively searchable. Larger stochastic or partially observable systems may respond differently. The remaining 2–3 globally non-optimal rankings per seed are retained as an honest limitation.
10. Reproducibility
The public repository contains fixed seeds, all twelve small checkpoints, machine-readable metrics, exact trajectories, experiment scripts, and tests for perspective semantics, terminal backups, legal actions, exact best response, and D4 mapping. See the repository’s reproducibility guide for the complete command sequence and expected outputs.