# Anytime-Constrained Equilibria in Polynomial Time

arXiv: https://arxiv.org/abs/2410.23637 · HTML: https://mlsanity.com/paper/2410.23637/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 45 references that are in the map.
- First posted on arXiv 31 Oct 2024.

## Builds on (most cited first, 20 of 20)

- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Multi-Agent Deep Reinforcement Learning for Large-scale Traffic Signal Control](https://mlsanity.com/paper/1903.04527/) (2019)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Safe Multi-Agent Reinforcement Learning via Shielding](https://mlsanity.com/paper/2101.11196/) (2021)
- [Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environments](https://mlsanity.com/paper/2209.15090/) (2022)
- [State-wise Safe Reinforcement Learning: A Survey](https://mlsanity.com/paper/2302.03122/) (2023)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [Deep Reinforcement Learning for Resource Management in Network Slicing](https://mlsanity.com/paper/1805.06591/) (2018)
- [Resource Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/1812.00600/) (2018)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm](https://mlsanity.com/paper/2206.05850/) (2022)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [Reinforcement Learning with Almost Sure Constraints](https://mlsanity.com/paper/2112.05198/) (2021)
- [Independent Learning in Constrained Markov Potential Games](https://mlsanity.com/paper/2402.17885/) (2024)
- [Provably Safe PAC-MDP Exploration Using Analogies](https://mlsanity.com/paper/2007.03574/) (2020)
- [Explicit Explore, Exploit, or Escape (E4): near-optimal safety-constrained reinforcement learning in polynomial time](https://mlsanity.com/paper/2111.07395/) (2021)
- [Anytime-Constrained Reinforcement Learning](https://mlsanity.com/paper/2311.05511/) (2023)
- [Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time](https://mlsanity.com/paper/2405.14183/) (2024)

## Built on by (most cited first, 1 of 1)

- [Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation](https://mlsanity.com/paper/2609.39093/) (2026)

## Abstract (arXiv)

We extend anytime constraints to the Markov game setting and the corresponding solution concept of an 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 optimal 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.