Research map / Learning theory and algorithms / Submodular and game algorithms

Anytime-Constrained Equilibria in Polynomial Time

ICML 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Zero-sum game learning dynamics

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 anytime constraints to Markov games, showing ACE feasibility is NP-hard for zero-sum games and giving an FPT exact algorithm (via AND/OR feasibility tree and action-constrained MG reduction) plus a polynomial-time approximation with additive/relative budget violation.

Problem

Computing anytime-constrained equilibria (feasible joint policies where every player's cumulative cost stays within budget at all times, and no feasible deviation is profitable) in constrained Markov games is hard; the paper asks for which classes it is tractable.

Approach

Characterize feasibly realizable (state, cumulative cost) pairs with an AND/OR feasibility tree, reduce the anytime-constrained game to an action-constrained Markov game with state-dependent action sets, solve stage games with a modified CCE/CE linear program, and obtain approximate ACE via cost rounding and truncation.

Key results

• Determining whether a feasible policy exists is NP-hard even for two-player zero-sum acMGs with S=1, A=2 and integer costs.
• Exact ACSPE computation is FPT in cost precision d and polynomial when d=O(log|G|) with n constant or d=O(1).
• Approximation computes H*ell-additive approximate ACSPE in time polynomial in |G| and 1/epsilon^n when max cost is polynomially bounded by the budget.

Surprising findings

• Computing a feasible policy is NP-hard even for simple two-player zero-sum anytime-constrained games, so worst-case polynomial exact algorithms are not possible.

Limitations

• Exact algorithm is only polynomial under small cost precision or constant number of players
• Approximation requires maximum cost bounded by a polynomial factor of the budget
• Purely theoretical with no empirical evaluation

Experimental setup

Builds on: constrained Markov decision processes correlated equilibrium linear program

Closest papers by meaning

• Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.88)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.88)
• Roping in Uncertainty: Robustness and Regularization in Markov Games (ICML 2024 · similarity 0.88)
• Polynomial-Time Approximability of Constrained Reinforcement Learning (ICML 2025 · similarity 0.87)
• Learning Nash Equilibrium of Markov Potential Games with a Shared Constraint via Primal-Dual Optimization (AAAI 2025 · similarity 0.87)
• Approximate State Abstraction for Markov Games (AAAI 2025 · similarity 0.87)