Playing Markov Games Without Observing Payoffs

Daniel Ablin, Alon CohenarXiv 2025 · DOI · arXiv

Introduction

In the field of multi-agent reinforcement learning (MARL), agents typically rely on observing rewards to optimize their strategies. However, in many real-world scenarios—such as high-frequency trading or complex automated systems—the environment may be too opaque or fast-moving to provide real-time feedback. This paper explores a fundamental question: can an agent compete effectively in a complex game without knowing the rules, seeing the score, or understanding how their actions influence the environment?

Problem Formulation: The Informational Disadvantage

The research focuses on Zero-Sum Symmetric Markov Games. In this setting, the learner faces a "severe informational disadvantage": they do not know the payoff function, they are unaware of the transition laws (how states change), and they never receive a single reward signal. The only information available to the learner is the opponent's actions.

A basic state transition in a Markov game where joint actions determine the next state.

The goal is to achieve sublinear regret, ensuring that as the number of rounds $T$ increases, the average loss per round approaches zero. This effectively allows the learner to force a draw against even an omniscient adversary.

Categorizing Symmetry in Markov Games

The authors formalize three nested levels of symmetry to categorize these games:

  1. Per-state Symmetric (SSG): Every individual state behaves like a symmetric matrix game (e.g., Rock-Paper-Scissors).
  2. Markov Policy Symmetric (MSG): The total expected reward is symmetric when players use Markov policies (strategies based only on the current state).
  3. History-dependent Symmetric (HSG): Symmetry must hold even if players use complex strategies based on the entire history of the game.

Proposed Methods and Algorithms

To overcome the lack of payoff information, the paper introduces two primary algorithmic frameworks:

Local Copycat

For SSGs, the learner treats every state as an independent mini-game. By applying a "copycat" strategy locally—mimicking the opponent's previous move in that specific state—the learner can maintain a competitive stance without knowing the underlying rewards.

Expected Payoff Redistribution (EPR)

For MSGs, the authors propose EPR, a mathematical reduction technique. EPR "peels back" the game's time horizon, demonstrating that global symmetry constraints force the game to behave like a collection of simpler, local symmetric games.

Transition dynamics in a symmetric Markov game, illustrating how actions $(a_1, a_2)$ influence the probability of moving to different future states.

Additionally, for more general cases, the problem is framed as Online Linear Optimization (OLO). By playing a "virtual game" against an imaginary player and using Online Gradient Descent (OGD), the learner can find a robust strategy regardless of the hidden payoffs.

Key Insights: The Hierarchy Paradox

A significant theoretical finding is the "Hierarchy Paradox." While one might expect global symmetry (MSG/HSG) to allow for more complex game structures than local symmetry (SSG), the authors prove the opposite. The requirement for global symmetry is so restrictive that it collapses the game's complexity. Specifically, they show that HSG is "trivial"—the entire Markov game effectively collapses into a single, static matrix game because future dynamics become irrelevant to the expected payoff.

Results and Complexity Analysis

The proposed algorithms achieve a regret bound of $O(n \sqrt{T |S| H})$, where $n$ is the number of actions, $T$ is the number of rounds, $|S|$ is the number of states, and $H$ is the horizon. This bound is near-optimal, matching the lower bound of $\Omega(n \sqrt{T |S| H})$. Furthermore, all proposed algorithms are computationally efficient, running in polynomial time.

Conclusion and Future Work

This work demonstrates that in symmetric environments, knowledge of transition laws and payoffs is not a prerequisite for forcing a draw. A simple mimicking strategy is robust enough to overcome an adversary's complete knowledge of the system. Future research will explore approximate symmetry, investigating how these strategies perform when the game is slightly biased, a critical step toward real-world application.

Summary updated

BibTeX
@misc{ablin2025playing,
  author = {Daniel Ablin and Alon Cohen},
  title = {{Playing Markov Games Without Observing Payoffs}},
  year = {2025},
  eprint = {2509.00179},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.00179},
}
Figure