Playing Markov Games Without Observing Payoffs

Abstract

Optimization under uncertainty is a fundamental problem in learning and decision-making, particularly in multi-agent systems. Previously, Feldman, Kalai, and Tennenholtz [2010] demonstrated the ability to efficiently compete in repeated symmetric two-player matrix games without observing payoffs, as long as the opponents actions are observed. In this paper, we introduce and formalize a new class of zero-sum symmetric Markov games, which extends the notion of symmetry from matrix games to the Markovian setting. We show that even without observing payoffs, a player who knows the transition dynamics and observes only the opponents sequence of actions can still compete against an adversary who may have complete knowledge of the game. We formalize three distinct notions of symmetry in this setting and show that, under these conditions, the learning problem can be reduced to an instance of online learning, enabling the player to asymptotically match the return of the opponent despite lacking

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyablin2025playing

Related papers

• Online Learning In Unknown Markov Games (2020)0.00
• Model-free Learning For Two-player Zero-sum Partially Observable Markov Games With Perfect Recall (2021)0.00
• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• Last-iterate Convergence Of Payoff-based Independent Learning In Zero-sum Stochastic Games (2024)0.00
• Policy Optimization For Markov Games: Unified Framework And Faster Convergence (2022)0.00
• Generalized Individual Q-learning For Polymatrix Games With Partial Observations (2024)2.26
• Can We Find Nash Equilibria At A Linear Rate In Markov Games? (2023)0.00
• Asynchronous Gradient Play In Zero-sum Multi-agent Games (2022)0.00