Anytime-Constrained Equilibria in Polynomial Time

Jeremy McMahan

ICML 2025poster0 citations

Anytime-Constrained Equilibria in Polynomial Time

Abstract

We extend anytime constraints to the Markov game setting and the corresponding solution concept of anytime-constrained equilibrium (ACE). Then, we present a comprehensive theory of anytime-constrained equilibria that includes (1) a computational characterization of feasible policies, (2) a fixed-parameter tractable algorithm for computing ACE, and (3) a polynomial-time algorithm for approximately computing ACE. Since computing a feasible policy is NP-hard even for two-player zero-sum games, our approximation guarantees are the best possible so long as $P \neq NP$. We also develop the first theory of efficient computation for action-constrained Markov games, which may be of independent interest.

Markov GamesConstrained EquilibriaComputational Complexity TheoryApproximation Algorithms

BibTeX

@inproceedings{
mcmahan2025anytimeconstrained,
title={Anytime-Constrained Equilibria in Polynomial Time},
author={Jeremy McMahan},
booktitle={Forty-second International Conference on Machine Learning},
year={2025},
url={https://openreview.net/forum?id=8mEhwcebmz}
}