Module nfsp 

Neural Fictitious Self-Play (NFSP) trainer (issue #106). Neural Fictitious Self-Play (NFSP) trainer.

Burn-native implementation of NFSP (Heinrich & Silver 2016, arXiv:1603.01121). The original paper proves ε-Nash convergence in the 2-agent zero-sum setting (§3 Algorithm 1, Theorem 3). Tracking issue: #106.

N-player (“approximate NFSP”) caveat

As of #119, the trainer accepts joint_config.num_agents > 2. The Vitter Algorithm R uniformity invariant on each per-agent reservoir survives unchanged (the per-agent reservoirs are independent and Algorithm R’s correctness does not depend on the number of agents). However, the §3 Algorithm 1 ε-Nash convergence guarantee does NOT generalize to N > 2 — Heinrich & Silver §5 explicitly flags “extending the convergence theory to N-player general-sum games” as future work. For N > 2 this implementation is therefore best described as an “approximate NFSP” smoke trainer: the BR/AP mechanics, η-anticipatory mixing, and reservoir sampling are all exercised, and empirically the average policy converges on symmetric mixed-Nash games like crate::env::games::n_player_matching_pennies::NPlayerMatchingPennies, but no formal guarantee is shipped beyond the per-agent reservoir uniformity.

Pseudocode (Heinrich & Silver §3 Algorithm 1)

for each iteration k:
    for each rollout step t:
        draw c ~ Bernoulli(η)             # η-anticipatory mixing
        if c == 1:
            a_t ~ best_response_policy   # BR (PPO actor)
            reservoir.push((s_t, a_t))    # ← reservoir-sampled
        else:
            a_t ~ average_policy          # AP (supervised actor)
            # NOTE: do NOT push AP actions into the reservoir
    train BR with PPO on the rollout (freeze-N-1 via JointMultiAgentTrainer)
    sample minibatch from reservoir; train AP via cross-entropy on (s, a)
end

The reservoir is Vitter’s Algorithm R (paper §3.2 footnote 3, see also Vitter 1985 “Random Sampling with a Reservoir”). Using a FIFO or sliding window instead defeats the convergence guarantee: NFSP depends on the supervised target being a uniform sample over the history of best-response actions so the AP converges to the time-averaged BR policy.

η-anticipatory mixing

At every rollout step the trainer flips a Bernoulli(η) coin. With probability η it samples from the best-response (BR) policy and pushes the observation/action pair into the reservoir buffer. With probability 1 − η it samples from the average (AP) policy and does not push to the reservoir. Appending AP actions to the reservoir collapses NFSP to vanilla fictitious play and prevents convergence to NE — this is the critical invariant the paper’s footnote calls out. Default η = 0.1 per Heinrich & Silver §3.

Reservoir vs FIFO

Heinrich & Silver §3.2 footnote 3: “Reservoir sampling avoids the policy distribution drift caused by uniformly drawing from a more recent window.” A FIFO buffer biases the AP towards recent BR actions, which is roughly equivalent to learning a recency-weighted mixture — that mixture is not the time-average and need not match any fictitious-play fixed point. Vitter’s Algorithm R keeps the held-items’ distribution uniform across the entire history of pushes regardless of stream length.

Per-agent observation handling

NFSP builds on top of crate::multi_agent::joint::JointMultiAgentTrainer, which records a per-agent observation stream in JointRollout::observations_per_agent. Agent i’s reservoir receives agent i’s observation (not agent 0’s), so partial- observability envs supervise the AP module on the correct view. Matching pennies returns identical observations to both agents, which keeps the regression tests bit-stable through the per-agent refactor (PR #118).

Determinism dependency on #109

The reservoir buffer’s eviction RNG, the η-anticipatory coin flips, and the average-policy minibatch sampler are all seeded from NfspConfig::seed via an internal StdRng. However, the inner crate::multi_agent::joint::JointMultiAgentTrainer::update_with_active_agents still uses rand::rng() for its per-epoch shuffle (see src/multi_agent/joint.rs:662), which means same-seed PSRO and NFSP runs are not yet bit-identical across wall-clock invocations. Issue #109 tracks the fix. The in-module determinism here is sufficient for the reservoir-uniformity and η-mixing unit tests in this PR.

Structs

NfspConfig

NFSP trainer configuration.

NfspIterationStats

Per-iteration NFSP statistics.

NfspStats

Aggregate NFSP trainer statistics returned by NfspTrainer::run.

NfspTrainer

NFSP outer-loop trainer.

ReservoirBuffer

Reservoir-sampled buffer backing the NFSP average-policy supervised dataset. Implements Vitter (1985) Algorithm R: every distinct item streamed through push is retained with probability capacity / stream_index (1-indexed across the full lifetime of the buffer). Under capacity, all pushes are kept; at capacity, each push at stream index i ≥ capacity + 1 is inserted with probability capacity / i replacing a uniformly-random existing slot.