Research map / Multi-agent systems and games / Games and equilibria

Playing Markov Games Without Observing Payoffs

NeurIPS 2026 · Multi-agent systems and games › Games and equilibria · approach: Learning in Markov games · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends copycat learning from repeated symmetric matrix games to zero-sum symmetric Markov games, giving sublinear-regret, polynomial-time algorithms for three symmetry notions (SSG, MSG, HSG) when only the opponent's actions are observed.

Problem

Learning to compete in zero-sum symmetric Markov games without observing payoffs or knowing transitions, observing only the adversary's actions, against an adversary that knows the full game.

Approach

Applies the copycat strategy (equalizing counts of symmetric action pairs via a virtual zero-sum game) locally per state for per-state symmetric games; shows MSG reduces to SSG via an expected payoff redistribution transformation and HSG collapses to a single symmetric matrix game, enabling copycat-style regret bounds.

Key results

• SSG: regret O(n sqrt(T|S|H)) in poly(|S|,n,T) time, with matching Omega(n sqrt(T|S|H)) lower bound.
• MSG: reduces to SSG via expected payoff redistribution, achieving O(n sqrt(T|S|H)).
• HSG: collapses to a single matrix game with O(Hn sqrt(T)) regret.

Surprising findings

• Stronger, more holistic symmetry notions (MSG, HSG) make the problem easier, not harder; HSG collapses to a single matrix game.
• Learner can force a draw without knowing transition laws.

Limitations

• Results are purely theoretical with no experiments.
• Adversary is assumed omniscient and learner restricted to Markov policies.
• Only exact symmetry is considered; approximate symmetry is left to future work.

Experimental setup

Metrics: expected cumulative payoff regret bound O(n sqrt(T|S|H))

Builds on: copycat strategy (Feldman, Kalai, Tennenholtz 2010) Blackwell approachability online gradient descent

Closest papers by meaning

• Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms (NeurIPS 2024 · similarity 0.89)
• Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.89)
• Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularization (ICML 2025 · similarity 0.88)
• Roping in Uncertainty: Robustness and Regularization in Markov Games (ICML 2024 · similarity 0.88)
• State-Constrained Zero-Sum Differential Games with One-Sided Information (ICML 2024 · similarity 0.88)
• The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.88)