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.
Cite
Text
Mcmahan. "Anytime-Constrained Equilibria in Polynomial Time." Proceedings of the 42nd International Conference on Machine Learning, 2025.Markdown
[Mcmahan. "Anytime-Constrained Equilibria in Polynomial Time." Proceedings of the 42nd International Conference on Machine Learning, 2025.](https://mlanthology.org/icml/2025/mcmahan2025icml-anytimeconstrained/)BibTeX
@inproceedings{mcmahan2025icml-anytimeconstrained,
title = {{Anytime-Constrained Equilibria in Polynomial Time}},
author = {Mcmahan, Jeremy},
booktitle = {Proceedings of the 42nd International Conference on Machine Learning},
year = {2025},
pages = {43399-43416},
volume = {267},
url = {https://mlanthology.org/icml/2025/mcmahan2025icml-anytimeconstrained/}
}