Skip to main content

Module psro

thrust_rl::multi_agent

Module psro 

Source
Expand description

Policy-Space Response Oracles (PSRO) meta-game trainer (issue #107). Policy-Space Response Oracles (PSRO) meta-game trainer.

Burn-native implementation of the PSRO outer loop (Lanctot et al. 2017, arXiv:1711.00832) for 2-agent zero-sum games. Tracking issue: #107.

§Pseudocode

Population[i] = {π_i^(0)}   for each agent i      (initial random policy)
repeat for k = 1..K:
    1. Empirical game G_k = payoff matrix between Population[0] × Population[1]
    2. Meta-Nash σ_k = MetaSolver.solve(G_k)
    3. For each agent i in {0, 1}:
        a. Sample opponent policy from σ_k[1-i]
        b. Train π_i^(k) as best response to that mixture
        c. Append π_i^(k) to Population[i]
    4. Update payoff matrix with new row/column
end

§Why an in-tree Rust meta-solver instead of bucket-brigade-core?

Issue #107’s original framing called for wiring bucket-brigade-core::nash::DoubleOracleSolver (Rust) in as the meta-solver. Upon investigation, the DO solver in envs/bucket-brigade@6486a549fc is Python, not Rust (bucket_brigade.equilibrium.double_oracle_heterogeneous.py). The bucket-brigade-core Rust crate exposes only agents, engine, rng, scenarios — no nash module exists. Calling into Python from a Rust trainer would introduce a runtime Python dependency contrary to thrust’s pure-Rust posture (and the bucket-brigade-core dep is itself feature-gated off for v0.1.0 because the crate is not on crates.io). We instead define a MetaSolver trait with three in-tree Rust implementations:

  • UniformMetaSolver — degenerate uniform mixture. Always available; serves as the unit-test baseline.
  • FictitiousPlayMetaSolver — deterministic fictitious-play meta-solver. No external LP dependency.
  • ReplicatorDynamicsMetaSolver — non-trivial mixed-Nash solver via projected replicator dynamics. No LP dependency; converges to the symmetric Nash on small empirical games (≤50 strategies).

See the issue’s curator comment (#107c-4704239526) for the full rationale and the deferred Option 1 (port the Python solver to Rust upstream).

§Per-agent observation handling

PSRO builds on top of crate::multi_agent::joint::JointMultiAgentTrainer, which records a per-agent observation stream in JointRollout::observations_per_agent. Envs with distinct per-agent views (partial observability, asymmetric information) drop in without pre-concatenation. Matching pennies returns identical observations to both agents, which keeps the regression tests bit-stable through the per-agent refactor (PR #118).

§Population growth & cost

Population grows monotonically — one new best-response policy per PSRO iteration per agent. Per-iteration cost scales linearly in population size (one BR train + one n × n meta-solver call). The empirical-payoff matrix is cached: only the new row/column is evaluated each iteration (existing entries are unchanged by construction). Memory is quadratic in iteration count; bound it via PsroConfig::max_population_size (default 50). The trainer returns Err (not panic) when the cap is hit.

§What this module ships in the first PR

§What is deferred to follow-up PRs

The full set of acceptance criteria from the curator’s comment also call for a bucket-brigade integration test (gated behind env-bucket-brigade) and a train_psro.rs example with the gap_closed_homogeneous metric. Those depend on locally re-enabling the env-bucket-brigade feature (the crate is path-only and disabled in the published Cargo.toml) and porting the metric from envs/bucket-brigade/experiments/scripts/compute_nash_phase_diagram.py. Both are tracked as cleavage point #3 in the curator’s open question; see PR description for the deferred-pieces summary.

Structs§

AlphaRankMetaSolver
α-rank meta-solver (Omidshafiei et al. 2019, Nature Sci Reports 9:9937).
FictitiousPlayMetaSolver
Fictitious-play meta-solver.
PayoffCache
Cached N-tensor empirical-payoff cache for an N-agent symmetric game.
PsroConfig
PSRO trainer configuration.
PsroIterationStats
Per-iteration PSRO statistics.
PsroStats
Aggregate PSRO trainer statistics returned by PsroTrainer::run.
PsroTrainer
PSRO outer-loop trainer for symmetric N-agent games (N ≥ 2).
ReplicatorDynamicsMetaSolver
Replicator-dynamics meta-solver.
UniformMetaSolver
Degenerate uniform meta-solver.

Traits§

MetaSolver
Meta-solver over a symmetric 2-player zero-sum empirical game.