Anytime-Constrained Equilibria in Polynomial Time
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 20 of its 45 references that are in the map. First posted on arXiv 31 Oct 2024.
Builds on
20 of 45 references.
References · 20
- 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
- 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 278
- 2019Multi-Agent Deep Reinforcement Learning for Large-scale Traffic Signal Controlcited by 159
- 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
- 2021Safe Multi-Agent Reinforcement Learning via Shieldingcited by 60
- 2022Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environmentscited by 54
- 2023State-wise Safe Reinforcement Learning: A Surveycited by 48
- 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 36
- 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 33
- 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
- 2018Deep Reinforcement Learning for Resource Management in Network Slicingcited by 27
- 2018Resource Constrained Deep Reinforcement Learningcited by 23
8 more
- 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 19
- 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
- 2021Reinforcement Learning with Almost Sure Constraintscited by 11
- 2024Independent Learning in Constrained Markov Potential Gamescited by 10
- 2020Provably Safe PAC-MDP Exploration Using Analogiescited by 9
- 2021Explicit Explore, Exploit, or Escape (E4): near-optimal safety-constrained reinforcement learning in polynomial timecited by 6
- 2023Anytime-Constrained Reinforcement Learningcited by 5
- 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Timecited by 5
Built on by
Citing papers per year: 2026: 1.
1 paper.