Anytime-Constrained Equilibria in Polynomial Time
Authors: Jeremy McMahan
Venue: ICML 2025 poster (2025)
Keywords: Markov Games
Constrained Equilibria
Computational Complexity Theory
Approximation Algorithms
Primary area: theory->game_theory
TL;DR: We design polynomial-time approximation algorithms for anytime-constrained equilibria

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.

Anytime-Contrrineed Equilibria in Polynomial Time
Jeremy McMahan
Abstract
2022: Wiering, 2000). Despite their relevance, anytime con- straints have yet to be studied in the multi-agent setting, which we remedy in this work.
We extend anytime constraints to the Markov game setting and the corresponding solution con-
cept of anytime-constraieed equilibrium (ACE). Then, we present a comprehensive theory of anytime-constrained equílibria that includes (1) computational characterization of feasible poli- cies, (2) fixed-parameter tractable algorithm for computing ACE, and (3) a cotoommll-imme algo- rithm for approximately computing ACE. Since computing a feasible policy is NP-hard even for two-player zero-sum games, our approxima- tion guarantees are the best possible so long as P # N.. We also develop the first theory of effi- cient computation for action-constrained Markov games, which may be of independent interest.
Formally, we consider constrained Markov game (cMG) G with a budget vector B. A joint policy я satisfies an anytime constraint every player i's accumulated cost at most B; at all times: P2 (//h E [H] Σi= Crat S B.] = Given such a constraint, the natural solution concept is the muytime-constrainne equilibrium (ACE). At a high level, an ACE is feasible joint policy for which no player can gain a higher value from any feasible deviation. Our main question is as follows:
For what class of cMGs can ACE be computed (approximately) in polynomial time?
Already in the single-agent setting, McMahan and Zhu (2024) showed computing optimal mnytime-constraimg policies is NP-hard. The situation for games is even worse: we show that even for simple two-player zero-sum anytime-constrained MGs, computing a feasible policy is NP-hard. Furthermore, as shown in (McMahan and Zhu, 2024), pnpectation-constraiie
1. Introduction
Although multi-agent reinforcement learning (MARL) has made many breakthroughs in game-playing, the literature has long since advocated the importance of constraints in real-world applications (Gu et al., 2023b). Despite their im- portance, the literature on constrained MARL is far behind the state-of-the-art in the single-agent setting. Most recently, almost-sure (Castellano et al., 2022) and anytime (McMahan and Zhu, 2024; McMahan, 2024) constraints have emerged in the single-agent setting to capture real-world scenarios, such medical applications (Coronato et al., 2020; Paragli- ola et al., 2018; Kolesar, 1970), disaster relief scenarios (Fan et al., 2021; Wu et al., 2019; Tsai et al., 2019), and re- source management (Mao et al., 2016; Li et al., 2018; Peng and Shen, 2021; Bhatia et al., 2021). However, many of these motivating applications are actually multi-agent prob- autonomous vehi- al., 2016; Wu et al., 2019) must interact with other vehicles, which is key aspect of MARL (Chu et al., 2020; Dinneweth et al.,
policies can arbitrarily vio- late anytime constraints, implying that standard expectation- constrained approaches fail. Moreover, constrained MGs, efficient algorithms are unknown outside of regret settings (Chen et al., 2022; Ding et al., 2023), which have different constraint requirements. Lastly, typi- cal distributed learning and self-play approaches fail since the feasibility player's 's action generally depends on the choices of others.
for expectation-
Past Work. time constraints also fail to generalize to the multi-agent setting. The approach designed in (McMahan, 2024) only applies to one constraint. On the other hand, the approach from (McMahan and Zhu, 2024) requires state augmenta- tion and -eeeeddeenndent action spaces. Although simple in the single-agent setting, the coupled nature of the players' constraints induces state-dependent action spaces that do not form product spaces. Consequently, each stage game be- comes non-normal-fone game for which efficient solvers are unknown. Moreover, their approach utilizes a relaxed augmented-state space that relies on - -oo to identify infea- sible states. However, the con-uniqueness of equilibria in
The only known efficient algorithms for any-
lems. Most obviously, anttime-complinn
cles (McMahan and Zhu, 2024; Shalev-Shward
'Department of Computer Science, University of Wisconsin- Madison, Wisconsin, USA. Correspondence to: Jeremy McMahan <jmemahan& @ wisc.edu>>
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Maytime-Constraing Equilibria in Polynomial Time
games could allow -oo solutions, which should indicate infeasibility, even when feasible equilibrium exists.
ung. 2019).
Safe MARL. Most works implement safety using some constraints (García et al., 2015), and several multi-agent works exist down this line (Shalev-Shwartz et al., 2016; Gu et al., 2023a; Elsayed-Aly et al., 2021). The single agent setting has mainly focused on no-violation learning for cMDPs (Chow et al., 2018; Bossens and Bishop, 2022; Gu et al., 2023b) and solving CCMDPs (Wang et al., 2023; Gu et al., 2023b), which capture the probability of enter- ing unsafe states. Performing learning while avoiding dan- gerous states has also been studied (Roderick et al., 2021; Thomas et al., 2021; Zhao et al., 2023) under non-trivial assumptions.
Our Contributions. We present a comprehensive theory of unytime-consttrained MGs, which includes (1) a com- putational characterization of feasible policies, (2) fixed- parameter tractable (FPT) (Downey and Fellows, 2012) al- gorithm for computing subgame-
ACE, and (3) polynomial time algorithm for computing approximately feasible -erffmee--eeeetttt ACE. Notably, our FPT algorithm runs in polynomial time so long as the supported costs require small precision. Similarly, our approximation al- gorithm runs in polynomial time so long as the maximum supported cost is bounded by a polynomial factor of the algorithmic guar-
budget. Given our hardness results, antees are the best possible in the worst case. Along the way, we develop efficient algorithms for constrained games, culminating in a theory of action-constrained MGs, which may be of independent interest.
2. Equilibria
Constrained Markov Games. A (tabular, finite-horizon) n-player Constrained Markov Game (cMG) is tuple G = (S.A, R, C, H). where (i) S is the finite set of states, (ii) A = A x ... ...An is the finite set of joint actions, (iii) (s, E A(S) is the transition distribu- tion, (iv) Rn(s,a) E A(R)) is the reward distribution, (v) Cx(s,)) a) E A(R") is the cost distribution, and (vi) H is the finite time horizon. To simplify notation, we let Th (s def [s) denote the expected reward, |AA| denote the number of joint actions [H] def (1...., H). and [G] be the total description size of the cMG.
Each of our main results utilizes a different algorithmic technique. For (I), we view a policy's ' set of feasibly re- alizable histories a directed graph and then construct an AND/OR tree whose TRUE subtree is the union of all feasible policy graphs. For (2), we show that the subgame- perfect ACE of a eMG corresponds to the Markov-perfect equilibria of an cetion-constrained MG. Then, we design efficient algorithms for solving aetion-constraine games by solving sequence of linear programs (LP). For (3). we use combination of cost truncation and rounding to derive approximate game whose solutions are approximately feasi- ble equilibria for the original cMG. Then, we show that the approximate game's 's subgame-perfect ACE is computable in polynomial time.
s def [S] denote the number of states, A del'
The agents interact with G using joint policy π {Th MH In the fullest generality, ma Hr - (AA) is a mapping from the observed history at time h (including costs) to a distribution of actions. Often, researchers study Markovian policies, which take the form TA : S + A(A), and product policies, which take the form π = { where each Ti an independent policy for player i.
Interaction Protocol.
1.1. Related Work
Constrained MARL. Ever since constrained equilibria were introduced (Altman and Shwartz, 2000), most works have focused on learning in the regret setting (Altman and Shwartz, 2000; Chen et al., 2022; Gattami et al., 2021; Ding al., 2023; Jordan et al., 2024). Outside of these works, the Markov
The agents start at an initial state 81 E S with observed history = (s1). For any h E [H], the agents choose a joint action ag ~ (TA).. Then, the agents receive immediate reward vector Th ~ R, a) and cost vector Ch. ~ (s, Lastly, G transitions to state 8h+1 ~ (h ax) and the agents update their observed history to Th+1 = (Th: an. Ch $h41). This process is repeated for H steps; the interaction ends once sH+1 is reached.
literature has focused on single-agent-consttaiinn Decision Processes (cMDP). It is known that cMDPs can be solved in polynomial time using linear programming (Altman, 1999), and many interesting planning and learn- ing algorithms have been developed for them (Paternain et al., 2019; Vaswani et al., 2022; Borkar, 2005; Hasanzade- Zonuzy al., 2021). Many learning algorithms can even avoid violation during the learning process under certain as- sumptions (Wei et al., 2022; Bai et al., 2023). Furthermore, Brantley et al. (2020) developed no-regret algorithms for cMDPs and extended their algorithms to the setting with a constraint on the cost accumulated over all episodes, which called a knapsack constraint (Brantley et al., 2020; Che-
Anytime Constraints. Suppose the agents have budget vector B E I", We say a joint policy л satisfies anytime constraints if,
P.
vh E [H],
Σ
c S B =1.
(ANY)
2

---

Daytime-Constraing Equilibria in Polynomial Time
Here, P. denotes the probability law over histories induced from the interaction of with G, and all vector operations are performed component-wise. If G only has anytime constraints, which will be the case in this work, we call G an anytime-constrained Markov game (acMG). We refer to any policy x satisfying (ANY) as feasible for G, and let llg denote the set of all feasible policies for G.
finish the game whenever a player takes an unsupported but feasible action.
Formally, we let Hi {Th E Mr PG[Ta] > 0} denote the subset of partial histories at time h that are realizable by a policy 9, and let Fr Uzena Hg denote the set of partial histories time h realizable by some feasible policy. For any feasible subgame Th E Fh, we let,
def
Remark 2.1 (Extensions). Our results can also handle mul- tiple constraints per agent, infinite discounting, and the weaker class of almost sure constraints. We defer the details to the appendix.
P vA E [M), (T)) def I
Σ Eas
CaSBI Th
(SUB)
Solution Concepts. Solutions to games traditionally take the form of equilibrium. In the MARL realm, the most pop- ular notions include the Nash equilibrium (NE), correlated equilibrium (CE), and course corree-correlated equilibrium (CCE). Given constraints, the key difference is focus feasible policies. Infeasible policies lead to disastrous outcomes for an agent. Thus, not only should a constrained equilibrium be feasible, but agents should only consider deviating if doing so would be feasible.
denote the set of feasible policies for the subgame The To capture our earlier intuition, we require an anytime- constrained SPE to be a policy that feasible for any feasi- ble subgame, and that beats any feasible deviation for that subgame.
Definition 2.4 (Anytime- Conttrain Perfect Equilibria). We call a joint policy πT an anytime-constrained subgame-perfect equilibrium (ACSPE) for an acMG G if for all times h E [H + 1]. and all ceasibly-realizen
histories Th E Fn. æ satisfies (1) æ E [T(()) and (2) for all players E [n]], and potential deviation policies Tे. either,
a joint policy и an anytime-constraicn Equilibria). We call equilibrium (ACE) for an acMG G if (1) π E 1l and (2) for all players i [n] and potential deviation policies Th. either,
Definition 2.2
( T<) & (Tk)
OR (T,a(Th) 2 V.T.T (Tr).
(ACSPH)
(m/) & II
OR V VI
(ACE)
denotes i's value from time h onward conditioned under history The Lastly, we call an equilibrium (ACSPNE) for G if x is additionally a product policy.
Here, (T.) def Σ Tie Th.
Here, Vi" def EG Et= Ti,t denotes i's value from inter- acting with G under and RE denotes the expectation defined by the law P7. Lastly, we call л an anytime- constrained Nash equilibrium (ACNE) for G if π is ad- ditionally a product policy.
Sabbame--erfeee Nash
Next, we show that ACSPE exists whenever a feasible policy exists. Here, we require the cost distributions to have finite support. We relax this assumption for our approximation algorithms later in Section 6.
Remark 2.3 (Correlated Equilibrium). Our definition of ACE in Definition 2.2 technically corresponds to anytime- constrained course-correlated equilibria (ACCCE), which we simplify to ACE for exposition purposes. Our results correlated equi-
Assumption 2.5 (Finite Cost Support). Throughout Sec- tion 2 Section 5, we assume each Cn(s, a) has finite sup- port.
apply equally well anytime-constraime libria (ACCE). We delay the definition and discussion of ACCE to the appendix. In the main text, we signal when results specialize to each equilibria type by writing ACE (NE/CE/CCE).
Proposition 2.6 (Existence). For any acMG G. the follow- ing are equivalent
1. G admits an ACE (CE/CCE),
Stage Games. It is often useful to consider refinements of equilibrium notions that are more structured and robust. The classical refinement for sequential games is the subgame- perfect equilibrium (SPE). An SPE policy is required to behave optimally under any history, also called subgames, even if those subgames are not realizable. That way, players could still recover if any deviated from the policy's 's sugges- tion. In the constrained setting, we only consider feasible subgames, i.c., subgames that are realizable by some fea- sible policy. This means the players could still adapt and
2. G admits an ACSPE (CE/CCE), and
3. G admits a feasible policy:
The equivalence also holds for ACNE so long as G admits a feasible product policy.
Although Proposition 2.6 implies equilibria exist under very minimal assumptions, they are generally hard to compute. As shown in (McMahan and Zhu, 2024), feasible policies
3

---

Anytime-Constrainet Equilibria in Polynomial Time
are generally not Markovian nor product policies. Moreover, just determining whether there exists feasible policy is NP- hard even for the simplest of acMGs.
point where all available actions lead to immediate viola- tion. Under this interpretation, it is easy to see that a policy is feasible if and only if it always reaches time H + 1 under any realization. We can utilize this intuition constructively through the idea of realizability graphs.
Proposition 2.7 (Hardness). Determining if a feasible pol- icy exists for an acMG is NP-hard even for the restricted class of two-player zero-sum acMGs for which S = 1,
For given policy π, we define its realizabillity graph R del (V*, E.) to be the directed acyelic multi-graph satisfying (i) v is the set of (time, state, cost)-triples feasibly-realizabbe under æ, and (ii) Et is the set of all feasible one-step (time, state, -ost)--volutions under т. We also label each edge by the action responsible for that evolution. Then, any я realizable feasible history Th corresponds to the labeled path p = ((1, $1, 1) 01,...; (h, 8h. Cx)) in R Thus, æ is feasible if and only if all sink nodes in R are distance H from the source node (1, O).
A = 2, and cost functions are deterministic mappings to non-negative integers.
3. Feasibility
Before we can fully understand ACE, we must first un- derstand feasible policies. This section derives characteri- zations of feasibly realizable histories under anytime con- straints. This leads us to design an algorithm that determines if a feasible policy exists, while also producing the set of all feasibly realizable cumulative costs and actions. These sets will be critical to our later equilibria computation in Section 4.
Algorithmic Approach. Overall, we can determine if HG * Ø by proving the existence of a realizability graph whose sinks are all distance from the source. Further- more, we can compute all feasibly realizable histories by computing the union of all feasible policy realizability graphs. We accomplish this by constructing a single graph containing all feasible realizability graphs and then pruning it to match the union.
First, observe that for a policy π to be feasible, all his- tories realizable under т must obey the budget. If Tr = ($1, a1, .I,...,.h)) E Hr is any partial history, we let Ch def E/=1 Gt denote the vector of cumulative costs in- duced by the history. Given this notation, we see that Hg if and only if for all h E [H + 1] and all Th E HG. it holds that C₁ < B.
Our graph is generated by iteratively taking feasible actions. If no sequence of feasible actions ever reaches time H + 1, then naturally no feasible policy exists. However, we must also ensure all branches generated from an action reach time H + to satisfy the anytime constraints. We deal with this difficulty by making each action an AND node. On the other hand, for a (time, state, cost)-triple to be feasible, there need only be a single action that ensures time H + is reached. Thus, we make each triple an OR node. We will later show that a TRUE subgraph corresponds to our desired solution.
History Translation. Consequently, we only need to con- sider the (state, cost)-pairs induced by history to deter- mine feasibility. In particular, we can focus on in del ((s), 0), a1, (1), .q..... : (sh, ex)), which denotes Th written in (state, formm Observe that for any The the translation of Th to (state, fost)-form is well-defined and unique. Specifically, given i.. we can infer any immediate cost Cs uniquely by Ck- = čk-1- Tg. and given The we can infer εN uniquely by Ex >>=1 C. Given this equivalence, we focus on characterizing the following sets.
Definition 3.2 (Feasibility Tree). We iteratively define an AND/OR tree T (Martelli and Montanari, 1973). We define the root node to be (1, $1, 0). For any time h E [H], and node (h, s. Z) E VT, we call E A a feasible action if no realization under a leads immediate violation, i.c. Pro-Ca(s.a) + c S B] 1. For any feasible action a, we create a new AND node u def (h, a) and edge (h, + (h,,,,,,,, For every s Supp(Pr ()) and Supp(Cn(s, we also create new OR node w der (h 1, ē + c) and edge (h, C, a) + (h + 1, s. a c). We label any leaf node of the form (H + 1,8,0 a) as TRUE and any leaf node of the form (h, s, c) for h < H + as
Definition 3.1 (Feasible Sets). We define the set of state, cumulative cost pairs realizable by feasible policy at time h by,
FS,
def U U ((sh, }.
xElle T.EHA
We define the set of actions taken by some feasible policy at a pair (8)d) E FS, by,
cs) def
U U
{an)
(2)
rello T141 (#h (x).e))=(s.e)
FALSE
Since any feasible policy can only take feasible actions by definition, any feasibly realizable history appears in (state, cost)-form as a path in T. Moreover, conditionally feasible histories appear as superpaths in T.
Realizability Graphs. Now, imagine that the game ter-
minates prematurely should (1) the agents ever choose an action that could immediately violate the budget or (2) reach
4

---

Equilibria in Polynomial Time
Algorithm 1 Feasibility
4. Reduction
Require: G
As hinted in the previous section, we can convert the anytime constraint on full histories into a per-time constraint on the available actions. Specifically, if the agents track their cumulative costs, they can identify actions that satisfy the constraint long term. These actions exactly correspond to those in F.A, (s, Z).
1: T t Definition 3.2(G)
2: ATSOLVE(T)
3: if (I, $1, 0) is FALSE then
4: return "Infeasible"
5: end if
6: for h <- to H do
7: RSA 5 Ø and (.) +
Then, the agents can convert their anytime-constraing MG G into a traditional Markov game G with non-stationary state space FS and non-stationary, state-dependent action space (s, 2). Importantly, FAAx (s, é) may induce non- normal- subgames because the exclusion of infeasible joint actions can cause FA, 2) not to take the form of a product space such as A x .... x An, Consequently, G is an action-constrained Markov game.
8: for TRUE (h, 8, E VT do
9: RSA RS₁ {(s,a)}
for TRUE (,, (0) ( do (x, + R.A Ua) 12: end for
10:
11:
13: end for
14:
end for
15:
return ((RS))n, (5)..)
Definition 4.1. We define an action-constrained Markov game G def (S,A, H) where,
Lemma 3.3. For any time h E + + 1I, and any reasibby- history Th E Frr there ex- ists a unique path PT.. S T satisfying PTn. ((1,s), (1, (1,,,,,,)).... sh, sh, Ca)). Moreover, ih any suphistory of Th realizable by some E IIT(TT), then P.n. PTx
1. Sp. def FSh.
2. As 2) del FA),s,
3. Pr((s', C + c) (s, der (.)))ss)) s,a)
and.
Thus, if any feasible history exists, then there exists at least one length H path in T. However, always taking actions that are feasible at the current time is greedy strategy that may not guarantee reaching time H + 1. Consequently, T contains many infeasible paths as well. On the bright side, we can show that any infeasible path must contain a FALSE node.
Ra(s, whenever a E (s 7) and 4. Rn,(s, a),a) def Ra(- (s, c) a) otherwise.
In addition, we define G's initial state to be 31 def (s1, 0).
For typical MGs, the standard solution concept is the Markov-perfed equilibrium. For action-constrained MGs, we use the same solution concept, but add the condition that the policy must only support actions in the constrained action sets.
Lemma
3.4. If
P
(11, 0), (1. $1, 0, ai)..... (h, sn, ON)) T is any path ending at FALSE node, then Th = (1,, 8k) is not realized by any feasible policy. Moreover, TN is any feasible subhistory of The then Th is not realizable by any [TT(T)).
Definition 4.2 (Markov-Perfedt Equilibria). For an action- constrained MG G, we say Markovian policy æ is all- subgame-feasible or simply feasible in this work if (z) (A) for all times h E [H] and all states ø E S. We let lL denote the set of all feasible policies for G. Then, a Markov-perfect equilibrium (MPE) for G is a Markovian joint policy x satisfying (1) π E Ilg. and (2) for all players E [n]. all times h E (H). all partial histories Th. E Hn, and all potential deviation policies Th, either.
Pruning. Overall, we see the subtree of TRUE nodes T exactly the union of all feasible policy realizability graphs. Computing the TRUE nodes for AND/OR tree can be done in linear time using standard tree recursion (Martelli and Montanari, 1973). Suppose that AOSOLVE is any such AND/OR tree solver. Then, we can compute the FS and FA sets by implicitly pruning the FALSE nodes from T. The full procedure is described Algorithm 1.
(I), &f 1l
OR
(T, 2 V.T. (Tr).
(MPH)
Proposition 3.5. For any acMG G, Algorithu (G)
Here, (i), def F G
Σn Tie 3 = denotes i's ex-
outputs "Infeasible" if 11 = Ø and otherwise outputs ((FSr)n. (F). rithm 1G) runs in time O(HHSDD)))) where De IU,, UNER (on Cn & B
pected value in G under π from time h onward conditioned on starting at state s. Lastly, we call π a Markov-perfeet Nash equilibrium (MPNE) for G i is additionally a prod- uet policy.
Moreover, Algo- def
5

---

Mnytime-Constraing Equilibria in Polynomial Time
Algorithm 2 Reduction
MGs, here, we must iteratively solve action-constrained matrix stage games. Then, can combine the constructed policies for each stage to solve the full game. We prove the correctness of this algorithm by deriving a novel theory of equilibria in action-constrained Markov games.
Require: (G)
1: x < Algorithm I(G)
2: if "Infeasible" then
3: return "Infeasible"
4: end if
5: Construct G <- Definition 4.1 (G)
Matrix Games. The key bottleneck to this backward in- duction approach is solving the cetton-constrained matrix games. Formally, let (A, X, u) denote an action-constrained matrix game, where (i) A is the joint action space, (ii) X S A is the set of feasible actions, and (iii) u. is the utility function. We tackle this problem by devising a varia- tion of the standard CE/CCE LP.. Importantly, we modify the constraint EneA (a)
6: π + MGSOLVE(G)
7: return π
Augmented Policies. Any Markovian policy a for G can be viewed as history-dependent policy for G represented in a compact form. In particular, by definition of P. we see that the é part of G's state space always corresponds to the current cumulative cost vector. Thus, π is equivalent to the history-dependent policy x' formed by n/ (T.) def (5h, G,), and can be used directly in G just by feeding in the pair (sh, Cn) to to generate the next joint action.
which ensures the total proba- bility mass of all joint actions equals one, into the constraint Eeex (a) = 1, which ensures the support of the joint strategy is contained in the valid joint action space. We also define the utility of any infeasible action to be- -00 so that infeasible deviations will be appropriately ignored by the LP. The full definition of the LP, which has no objective function, is,
Moreover, if π is feasible for G. we see that since As(s,) = (s, a) by definition, it must be the case that x is feasible for G by Proposition 3.5. Although less obvious, we also show that any MPE for G is an ACE for G.
Σ (a) (uz(a) a,(a 20, Vi, A: OEX
Σ ca) 11, REX o(a) 20
Lemma 4.3 (Equilibria). Any MPE (NEJCF/CCE) is an ACSPE for G.
Va X (CLP)
Then, we can compute an ACSPE for G or determine that none exists by attempting to find an MPE for G. We sum- marize the full reduction in Algorithm 2.
Lemma 5.1. If (,)) is any action-constrrained matrix game and a is any solution to (CLP) X, u). then for any player [n], and deviation oe E A(A:) for which a' def (o(,o-)) E A(X), we have that Egro E Z Ea-a [u=(a)]. Moreover, if X # 2, then there exists solution to (A,
Theorem 4.4 (Reduction). For any acMG G. if MGSOLvE can compute a feasible MPE (NE/CE/CCE) for any feasi- ble action-constrained Markov game, then Algorithm 2(G) correctly outputs "Infeasible" " if lIg Ø and outputs ACSPE (NE/CE/CCE) π, otherwise. Moreover, if MG- SOLVE runs in time ((G)), then Algorithm 2(G)
runs in time (poly([G)) DG)), and any output policy can be stored with O(H)ADe) space.
Markoy Games. To use (CLP) in our backward induction, it will be useful to represent stage games with the Q matrix. Formally, for any given partial policy n. any time E [H]. and any state 5 S, we define the stage game to be the matrix game Qn(s) whose utility for any player i [m] under joint action â E A is defined by,
5. Computation
In the last section, we showed how to reduce our mnytime--oostrained game problem to an action-constrained game problem. However, efficient algorithms for action- constrained games are currently unknown. In this section, we remedy this knowledge gap by designing efficient algo- rithms for computing MPE of an action-constraineed MG. contrrccnnt
Q (5, a) def (n) ((, E5 P7((5 3.a)
-00 if E Ax
(Q)
Then, given some LP feasibility algorithm LPSOLVE, we use these ideas to solve action-constrained MGs in Algo- rithm 3.
Moreover, show that feeding method into our reduction yields polynomial time algo- rithm for computing ACE so long as the cost precision is logarithmic.
Theorem 5.2 (Constrained Solver), For any feasible action- constrained MG G, if LPSOLVE is a polynomial- linear- program feasibility solver, then Algorithm 3(G) correctly outputs a feasible MPE (CE/CCE) in polynomial time.
We take a backward induction approach similar to other planning algorithms for Markov games. Unlike traditional
6

---

Anytime-Constrainee Equilibria in Polynomial Time
Algorithm 3 Constrained Solver
between supported costs. Technically, we also need the CDF of the distribution be efficiently computable for use in computation.
Require: G
1: V.. H.H-1 (8) + 0 for all i E [n] and E S1+1
2: for h = H down to do
Assumption 6.1 (Bounded). We assume that each cmaa def suph.s.a sup SuppuppCCCn(s < oc, and that each Cx(s,a) = (C ()) is a product distribution.
3: for & E S, do
4:
(5, + (Q) for each E [n] and ā E A
5:
+- LPSSLLVE(CCPPA = A, = u
(5))
Moreover, if Heqaaz I B, observe that every policy is feasi- ble for player i, which just leads to a standard unconstrained problem for that player. A similar phenomenon happens if ci < 0. Thus, we assume WLOG that Hemes > B and cmaaz 0. We can then define our relaxed feasibility notions follows.
6: V. ($) + Ea Ta(a 8)07,,
7: end for
8: end for
9: return
Definition 6.2 (Approximate Feasibility). For any > 0, joint policy π is e-additive feasible for G if,
Reduction Analysis. Given our efficient action- constrained game solver, we can now finish analyzing the running time of our reduction. Since Theorem 5.2 implies that Algorithm 3 runs in time poly([G]), Theorem 4.4 implies that Algorithm with MGSOLVE = Algorithm 3 runs in time poly([G], DG). The main issue is that DG can be exponentially large in the worst case. However, we can show that DG < poly ((G))20(dd), where d denotes the cost precision, which is the number of significant bits needed to represent any supported cost. By definition, our method is FPT (Downey and Fellows, 2012) in the cost precision.
h
P wh E [H] Σe EasB+c- =1
(3)
1=1
and c-relative feasible for G if,
PPg 4h E [M], Σ B
B(1+ + coB) =1, (4)
where is the sign of B², We then define an e- additive/relative approximate ACE to satisfy the usual con- ditions of Definition 2.2 but with the feasibility condition (I) relaxed to an e-additiverrelative feasibility condition.
Theorem 5.3 (FPT), Equipped with any polynomial-time LP solver and MGSOLVE = Algorithm 3, Algorithm 2 is a fixed-paramett tractable algorithm for computing ACSPE Consequently, if
Rounding.
The key idea of our approximations is to have players round down any cost vector they receive to the near- est multiple of some l > O. Doing so allows the players to track far fewer cumulative costs than originally. In ad- dition, we can effectively truncate the lower regime of the distribution using the fact that player i ever receives an immediate cost smaller than B, Hemax, then it may take any action whatsoever going forward without violating its budget. Thus, the player can treat any smaller cost as if it were B, - He This process of rounding costs then induces a new cMG with finite support cost distributions.
(CE/CCE) in the cost-precision (log(GG)) while n is held constant or d = O() while n is arbitrary, then Algorithm 2 runs in polynomial time and any output policy can be stored in polynomial space.
Remark 5.4 (Learning). Our methods immediately apply to the learning setting through model-based approaches. More- over, any new learning algorithm for action-constrained MGs can immediately solve G and thus compute ACE for G.
6. Approximation
Definition 6.3 (Approximate Game). For any >> 0, we de- fine |c|e [ é to be the largest multiple of É that lower bounds For any player i E [n]. let Č₁11 S ... & 6i.m denote the elements of the finite set of player i's rounded costs {LeAee I C E [B, Hemaa cmmo]]] in order, and let č.D del port distribution C,,, (s, a) into finite support distribution (r, a) by defining for each k E [m].
In the previous section, we showed our method runs in polynomial time whenever the cost precision is small. How- ever, in cases where the cost precision is large or, even worse infinite, the computation may require exponential time due to the NP-hard nature of finding feasible solution, Proposition 2.7. To combat this issue, we slightly relax the feasibility condition. This allows to compute equilibrium policies that only violate the budget by given > 0 at the cost of an additional poly(1/e) factor in running time.
= -0. We discretize the potentially infinite sup-
Pr [C E Can(Cin (s))) cnCC,
(5)
In this section, we allow any infinite support cost distri- butions that are bounded above. We also require that dis- tribution is a product distribution to enable comparisons
'When the costs and budgets are negative, negating the con- straint yields Σ a 2 [B] e). which is the traditional notion of relative approximation for covering objectives.
7

---

Anytime-Constraiee Equilibria in Polynomial Time
Algorithm 4 Approximation
e-relative approximate ACSPE (CE/CCE) for any acMG. Moreover, if c < poly([G]) B), Algorithm 4 runs in time O(poly(IG], e
Require: (G)
1: Construct G + Definition 6.3(G)
2: Let MGSOLVE Algorithm 3
Remark 6.9 (Cost Bound). We can efficiently compute approximately feasible solutions so long as c < poly([@l) [B] This condition is very natural. When the supported costs all have the same sign, any feasible policy induces costs with c I [B] anyway. Importantly, this restriction is not an artifact of our approach; some bound on cm necessary for efficient computation as proved in (McMahan and Zhu, 2024).
3: return Algorithm 2(G)
We then define the approximate acMG & def (S,A,P R, H) to be our original game G but
with different cost distribution.
Since outside of extreme cases, we always round costs down, the players always maintain an underestimate of their true cumulative cost. Consequently, the players may be incurring more costs than expected. However, we can show that the true cost accumulated is not much larger than the surrogate cost.
7. Conclusion
In this work, we introduced seytimee-costraiingg for Markov games and studied the corresponding solution concept of anytime-constrained equilibria. Although finding a feasible policy is NP-hard for simple games, we showed efficient computation is possible so long as the cost precision con- stant. The main ingredients to our approach were graph algorithm to derive all feasibly realizable histories and ef- ficient algorithm for solving action-constraingg MGs. Lastly, we presented approximation algorithms for computing ap- proximately feasible in polynomial time so long as the cost distribution's 's supre- mum is no larger than a polynomial factor of the budget. Given the hardness results, our approximation guarantees are best possible under worst-case analysis.
Lemma 6.4. Any feasible policy for G is an Hé-additive feasible policy for G.
On the flip side, the fact that players are willing to spend more than before means they have more actions available to them at each stage. Consequently, they can always find strategies that achieve the same value or even higher than any truly feasible policy for the game. It is then easy to see that solutions G satisfy condition (2) in Definition 2.2, so form approximate ACE for G.
equilibria running
Lemma 6.5. Any ACSPE (NE/CE/CCE) for & are He- additive approximate ACSPE (NE/CEICCE) for G. More- over, if Ilg # 2 then 1g + Ø.
Impact Statement
Consequently, we can compute approximate equilibria for G by solving G. The full algorithm is described in Algo- rithm 4. Since every approximate cost an integer multiple of every approximate cumulative cost will also be an integer multiple of f. In fact, for each E [n), every ap- proximate cumulative cost's multiple must reside in the mon
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
set {
Depending on the choice of f, the players may need to track far fewer cumula- tive costs behave optimally.
Re
H
E. Altman. Constrained Markov Decision Processes. Chap- man and Hal//CRC, 1999. doi: 10. 10.1201/9781315140222
Theorem 6.6 (Approximation). For any acMG G and > O, Algorithm (G) correctly outputs "Infeasible" if Ht- additive feasible policies for G exist and ouiputs He- additive approximate (CE/CCE) n, otherwise. More- over, Algorithm- 4 runs in time (ppoly((c))))) (GG), llema=-Bli -BIl)) )).
E. Altman and A. Shwartz. Constrained markov games: Nash equilibria. In J. A. Filar, V. Gaitsgory, and K. Mizukami, editors, Advances in Dynamic Games and Applications, pages 213-221, Boston, MA, 2000. Birkhäuser Boston. ISBN 978-144612-1336.9
Corollary 6.7 (Additive). For any > O, if we define l def e/H, then Algorithum correctly outputs "Infeasible" or an c-additive approximate ACSPE (CE/CCE) for any acMG.
Q. Bai, A. Singh Bedi, and V. Aggarwal. Achieving zero constraint violation for constrained reinforcement leam- ing via conservative natural policy gradient primal-dual algorithm. Proceedings of the AAAI Conference on Artifi- cial Intelligence, 37(6):6777 67444, 6 2023. doi: 10.1609/ saai.v37:6.25888 URL / / index, http://ppp/.a//rrrall///////////
Moreover, if I| -Bll Blooo S poly((G)), Algorithm 4 runs in time (p 1)))
we define def <) BB/ H. then Algorithm 4 correctly outputs "Infeasible" or
Corollary 6.8 (Relative). For any e > O, we
8

---

Anytime-Constranne Equilibria in Polynomial Time
A. Bhatia, P. Varakantham, and A. Kumar. Resource constrained deep reinforcement learning. Proceedings of the International Conference Automated Plan- ning and Scheduling. 291))610-620, 5 2021. doi:
e02ff 6a09 Paper.
pdf.
Y. Chow, O. Nachum, E. Duenez-Guzman, and M. Ghavamzadeh. A lyapunov-basee approach to safe reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., cc/paper__illesspppee////// metpeidpdiinnnneespe.eee.....e neurips.
10. 1wt99/ccp...29......... 1.358. wtt.ttts:: aaai. org/indes wttp:p///..cce/aaatccceeeeeeeeee
V. Borkar. An actor-critic algorithm for constrained markov decision processes. Systems & Con- trol Letters, 54(3):207-213, 2005. ISSN 0167-
2018. URL https///rrooo.
6911. doi: http:://oo.nn/000.000iissssooeoa 007. URL hitiecc//artccle//////////111112
4fe51499199627755beebbbbbb Paper.... pdf.
D. M. Bossens and N. Bishop. Explicit explore, exploit, or escape (e4): Near-optimal safety-constrained reinforce- ment learning in polynomial time. Mach. Learn., 112 (3):817-858 6 2022. ISSN 0885-6125, doi: 10.1007/ $10994-002--06201-- URL http://oooo.oo/.//// 1007/s10998 0200002--22222 06201-2.
T. Chu, J. Wang, L. Codecà, and Z. Li. Multi-agent deep reinforcement learning for large-scale traffic signal con- trol. IEEE Transactions on Intelligent Transportation Systems, 21(3):1086-1095, 2020. doi: 10.1109/TITS. 2019.2901791.
A. Coronato, M. Naeem, G. De Pietro, and G. Paragliola. Reinforcement learning for intelligent healtheare applications: A survey. Artificial Intelligence in
K. Brantley, M. Dudík, T. Lykouris, Miry- oosefi, M. Simchowitz, A. Slivkins, and W. Sun. Constrained episodic reinforcement learning in concave-convex and knapsack settings. In NewrlPS, 2020. URL
Medicine, 109:101964, 2020. ISSN 0933-3657. 200. 101964. com/
doi: URL
http::://wwww.ciiencceeseesseees science/ science/article//peee http:///accccc//////3300002000/0
wttp:ps..ccpppppp neauzipe..c//pppee/////aaaa 22167388818884477788777776822233 html.
D. Ding, X. Wei, Z. Yang, Z. Wang, and M. Jovanovic. Provably efficient generalized lagrangian policy opti- mization for safe multi-agent reinforcement learning. In N. Matni, M. Morari, and G. J. Pappas, editors, Proceed- ings of The 5th Annual Learning for Dynamics and Con- trol Conference, volume 211 of Proceedings of Machine Learning Research, pages 315-332 PMLR, 15-16 Jun 2023. ht https/tttt///p/ceeeeeeeiie http///poooceeeeeeeeeeeeee/es mlr mlr.press/ press/ v2 v211 html.
A. Castellano, H. Min, E. Mallada, and J. A. Bazerque. Re- inforcement learning with almost sure constraints. In R. Firoozi, N. Mehr, E. Yel, R. Antonova, J. Bohg, M. Schwager, and M. Kochenderfer, editors, Proceed- ings of The 4th Annual Learning for Dynamics and Control Conference, volume 168 of Proceedings of Ma- chine Learning Research, pages 559-570. PMLR, 6 2022. htRpttttt:///ooceeee ngs mlr..mrr..... m.l..press/// v168 11.6/casteelano222... htmm.
J. Dinneweth, A. Boubezoul, R. Mandiau, and S. Espié. Multi-agent reinforcement learning for autonomous vehi- cles: a survey, Autonomous Intelligent Systems, 2(1):27, 2022, doi: 1000007/443644442220000044 URL https: ///oii.org//// 1007 -22 -0200000----- z.
Z. Chen, S. Ma, and Y. Zhou. Finding correlated equi- librium of constrained markov game: A primal-dual approach. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, vol- ume 35, pages 25560-25572. Curran Associates, Inc., 2022. URL. https::tp//c.c....... http:://p/cceeeeeee sew.is....rss.... cc co/paper_fiiieeccccc fiaaeerrffleessppper///////////
R. Downey and M. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer New York, 2012. ISBN 9781461205159, URL https: //bokks.///....o// google. hwmgle.com//ccooooooooommm/./ooe www./oooooo.eooooooooooooooooooe /wt.//oooss////oooo ?id JBWAAAAAAAAAAAAAAAAAAAA a3f8E584 oef htt.://eeeeeeeeeo..aa.ee--------
pdf.
I. Elsayed-Aly, S. Bharadwaj. C. Amato, R. Ehlers,
U. Topeu, and I.. Feng. Safe multi-agent reinforcement learning via shielding, 2021. URL htttps://arxtt org/ abs 22021.111111 11196.
W. C. Cheung. Regret minimization for reinforcement learn- ing with vectorial feedback and complex objectives. In Advances in Neural Information Processing Systems, vol- ume 32, 2019. URL https: /ptp/eeeegce.....e neurips. oa/ wttp://ppppp//11///e/..
/
C. Fan, C. Zhang, A. Yahja, and A. Mostafavi. Dis- aster city digital twin: A vision for integrating
9

---

Anytime-Constraine Equilibria in Polynomial Time
artificial and human intelligence for disaster man- agement. International Journal of Information Management, 56:102049, 2021. ISSN 0268-4012. doi:
R. Li, Z. Zhao, Q. Sun, C.-L. C. Yang, X. Chen, M. Zhao, and H. Zhang. Deep reinforcement learning for resource management in network slicing. IEEE Access, 6:74429- 74441, 2018. doi: 10. 00.109/ACCESSS2018..8888
URL bettps:/www..oo www.wweiiiiiciiiiiieeecccc encediicceiiieec rect. com/
H. Mao, M. Alizadeh, I. Menache, and S. Kandula. Re- source management with deep reinforcement learning. Proceedings of the 15th ACM Workshop on Hot Topics in Networks, HotNets '16, page 50-56, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450346610. doi: 10.1145/ 0005745.3005777 1
J. Gareía, Fern, and Fernández. A comprehen- sive survey on safe reinforcement learning. Jour- nal of Machine Learning Research, 16(44): 2015. URL http://jalr.org/ pttpp...///ppppe/////// garcia15a. htmml.
URL attps://doli org/10. 30055500.
A. Gattami, Q. Bai, and V. Aggarwal. Reinforcement learning for constrained markov decision processes. In A. Banerjee and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelli- gence and Statistics, volume 130 of Proceedings of Ma- chine Learning Research, pages 2656-2664 PMLR, 13- 15 Apr 2021. URL https: httpsspp:////coceeeeee pwwp/edinceengss...oo../.. mm.....n............mmmm.......m mmlr. hatsss/v33//gatee
A. Martelli and U. Montanari. Additive and/or graphs. In Proceedings of the 3rd International Joint Conference on Artificial Intelligence, IJCAI73, page 1-11, San Fran- cisco, CA, USA, 1973. Morgan Kaufmann Publishers Inc.
J. McMahan. Deterministic policies for constrained re- inforcement learning in polynomial-time, 2024. URL https:
html.
S. Gu, J. Grudzien Kuba, Y. Chen, Y. Du, L.. Yang. A. Knoll, and Y. Yang. Safe multi-agent reinforce- ment learning for multi-robot control. Artificial Intelligence, 319:103905, 2023a. ISSN 0004-3702. doi:
J. McMahan and X. Zhu. Anytime-constrainee re- inforcement learning. In S. Dasgupta, S. Mandt, and Y. Li, editors, Proceedings of The 27th Interna- tional Conference on Artificial Intelligence and Statis- tics, volume 238 of Proceedings of Machine Learn- ing Research, pages 4321-4329, PMLR, 02-04 May 2024. hwtttttss///poceeeeeee v238 / ht/////mmaaa222.a2mm .attaalnnnna...l..... html.
URL /iianee/articcee//////0992222222
com/
mlr. m....pres//
S. Gu, L. Yang, Y. Du, G. Chen, F. Walter, J. Wang, Y. Yang, and A. Knoll. A review of safe reinforcement learning: Methods, theory and applications, 2023b.
G. Paragliola, A. Coronato, M. Naeem, and G. De Pietro. A reinforcement rearning-based approach for the risk man- agement of e-health environments: A case study. In 2018 14th International Conference on Signal-Imag Technol- ogy & Internet-Bass -Based Systems (SITIS), pages 711-716, 2018. doi: 10.1109/SITIS. 201.220010011 14.
A. HasanzadeZonuzy, A. Bura, D. Kalathil, and S. Shakkot- tai. Learning with safety constraints: Sample com- plexity of reinforcement learning for constrained mdps. Proceedings of the AAAI Conference on Artificial In- telligence, 35(9):66677667, 5 2021. doi: 10.1609/ vaai.v35i9.169377 URL https::///////t aww..//.//o/a.aaaaoooooo.ooo org/ index. AAAI httpp//////aarrreeeeeeeeee//////
S. Paternain, L. Chamon, M. Calvo-Fullana, and A. Ribeiro. Constrained reinforcement learning has zero duality gap. In Advances in Neural In- formation Processing Systems, volume 32. 2019. URL. cc/sapee__iieee/ppprr/////////fp al 000b66517acc7333511777566600000 Paper. pdf.
Jordan, A. Barakat, and N. He. Independent learning in constrained Markov potential games. In S. Dasgupta, S. Mandt, and Y. Li, editors, Proceedings of The 27th International Conference Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Lear- ing Research, pages 4024-4032. PMLR, 02-04 May 2024. httsstss::/ http:///oooeeddeeeeeeee www.innnss......mmmmmmm...m.em.m mil.ppress/ v238/jordan24a.. html.
httpss//proccedingg..ees
H. Peng and X. Shen. Multi-agent reinforcement learning based resource management in mec- and uav-assisted vehicular networks. IEEE Journal Selected Areas in Communications, 39(1):131-141, 2021. doi: 10.1109/ JSAC.2020.3036962.
P. Kolesar. A markovian model for hospital admission scheduling. Management Science, 16(6):B384 B33,, 1970. ISSN 00251909, 15265501. URL http: /www.
M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994, ISBN 0471619779.
10

---

Anytime-Cnnstranned Equilibria in Polynomial Time
M. Roderick, V. Nagarajan, and Z. Kolter. Provably safe pac-mdp exploration using analogies. In A. Baner- jee and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Ma- chine Learning Research, pages 1216-1224. PMLR, 4 mlr. press//
of The 25th International Conference on Artificial In- telligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 3274-3307, PMLR, 2022. URL https: httpssss/ppccceeieeeeeee mlr press// v151 / /we 22a ht.ml.
M. Wiering. Multi-agent reinforcement leraning for traffic light control. In Proceedings of the Seventeenth Inter- national Conference on Machine Learning, ICML '00, page 1151 158, San Francisco, CA, USA, 2000. Mor- gan Kaufmann Publishers Inc. ISBN 1558607072.
2021. URL http:httts::proeeeedeeee v1 v130/roderickkla. html.
S. Shalev-Shwartz, S. Shammah, and A. Shashua. Safe, agett- reinforcement learning for autonomous driv- ing, 2016. URL httt::t:///axiiiiii 03295.
C. Wu, B. Ju. Y. Wu, X. Lin, N. Xiong, G. Xu. H. Li, and X. Liang. Uav autonomous target search based on deep reinforcement learning in complex disaster scene. IEEE Access, 11117227-112444 2019. doi: 10.1109/ 2019.2933002.
G. Thomas, Y. Luo, and T. Ma. Safe reinforcement learning by imagining the near future. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 13859-13869, Curran Associates, Inc., 2021. URL https: httpss:/pprooeeedigg..oo neurips. cc httpppper_.lllleeeppe///////////
W. Zhao, T. He, R. Chen, T. Wei, and C. Liu. State-wise safe reinforcement learning: a survey. In Proceedings of the Thirty-Second International Joint Conference on Arti- ficial Intelligence, IJCAI '23, 2023, ISBN 978-1-956792- 03-4. doi: 10.24963/jccii 2023/76.. URL https: / //db..org//0.22463333
#B277781226611221332024553333333 pdf.
L. Tsai, A. Phatak, P. K. Kitanidis, and C. B. Field. Deep Reinforcement Learning for Disaster Response: Navigat- ing the Dynamic Emergency Vehicle and Rescue Team Dispatch during Flood. AGU Fall Meeting Abstracts, volume 2019, pages NH33B-14, Dec. 2019.
S. Vaswani, L. Yang, and C. Szepesvari. Near-optimal sample complexity bounds for constrained mdps. In S. Koyejo, S. Mohamed, A. Agarwal, D. Bel- grave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, vol- ume 35, pages 3110-3122. Curran Associates, Inc., 2022. URL https: neurips.. oc ca/paper_fiie [eaper_fflee/pppper///////// ort.a//co222ctt..e...eee0.6aarrr pdf.
Y. Wang, S. S. Zhan, R. Jiao, Wang, W. Jin, Z. Yang, Z. Wang, C. Huang, and Q Zhu. Enforcing hard con- straints with soft barriers: Safe reinforcement learning in unknown stochastic environments. In A. Krause, E. Brun- skill, K. Cho. B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Ma- PMLR, 2023. Utthttps: : / ppwppeeiiogggs.oeeeeeppppppp..se mlr press/ v202 2212///an223a.. html.
chine Learning Research, pages
H. Wei, X. Liu, and L. Ying. Triple-q: A model-free algo- rithm for constrained reinforcement learning with sub- linear regret and zero constraint violation. In G. Camps- Valls, F. J. R. Ruiz, and I. Valera, editors, Proceedings

---

Anytime-Constrainee Equilibria in Polynomial Time
A. Proofs for Section 2
A.I. Proof of Proposition 2.6
Proof. If ll = 2, then by definition no ACE or ACSPE can exist since they must be feasible. On the other hand, la + 2, then Algorithm yields an ACSPE as shown by Proposition 3.5. Thus, an ACSPE exists and so an ACE also exists.
A.2. Proof of Proposition 2.7
Proof. The proof of Theorem (McMahan and Zhu, 2024) shows computing feasible seytimm-constrainee policy NP-hard for constraints. Since this fact is independent of the reward structures, the result applies to two-player zero-sum cMGs by treating one player dummy with influence the transitions.
B. Proofs for Section 3
We introduce a few helpful observations here.
Observation (Decomposaaiiltyy) For any policy n, time E [H] and x-realizable partial history Th+11 E H we have that Th+1 = (Th, ah, Ch, 81+1) where,
1. on (TT))
2. Ch. E (sn, an)).
3. S1.11 E Supp( Ph (sh, an)), and
4. pd [m]] > O.
Proof. By the Markov property (Fquation (2.1.11) from (Puterman, 1994)), we can decompose 7h+1 = (Thy (h, Cha 8h++1) so that,
PT [+++]] = (T) (cn 8h, an
8h, an).
(6)
Since PT [m4+1] > 0 by assumption. it must be the case that each quantity on the RHS is also positive. In particular, we see that (i) ag E Supp(m((TT)) (ii) a E SSppp(C, an)), (iii) 84+1 E Supp Pa (sh, an)), and (iv) 1pTt [Tx] > O.
Observation 2. For any feasible policy π E II. time h E [H], and n-realizable history E 7% it must be that Supp(TA(TT)) C {a E A (raaC + B) = 1}. The same claim holds for the set (T)(()) as well.
Proof. Fix any such æ, h, and Let s def a E (upp(Tx(TT.) satisfying (ro)C +e > B 0. Then, we would have that,
Sh and ā def The Suppose for the sake of contradiction that there exists some
&
PT Ba E [H], Σ 4 >
B)
tm
1
B Th [m.]
t=l
+ ch
B
Th | [Ta]
(T
Th)
Pr
B
0.
The penultimate line used the Markov property, and the final line used the fact that each quantity occurs with non-zero probability by assumption. Thus, we the existence of such action leads contradiction.
B.1. Proof of Lemma 3.3
Proof. For the first claim, we proceed by induction on
12

---

Anytime-Constranned Equilibria in Polynomial Time
Base Case. For the base case, we consider h 1. In this case, the only realizable history is T1 (51) with 6 By definition, have (1, 81, 0) is the source node. Thus, the claim holds.
Inductive Step. For the inductive step, we consider any h 2 1. Since Th+1 Fh-1 by assumption, there must exist some π E He that realizes Th-1- Then, Observation 1 implies can decompose Th+1 into 7h+1 (T, (Th, uh, Ch. 8h+1) satisfying conditions (i)-(iv). Since Th is r-realizable according to (iv), the induction hypothesis
implies Pr.. = ((1, $1, 0), (1, $1, 0, ai)...., (h, sh. CA)) is path in T. Also, Observation 2 implies that as satisfies Pre-Ch(ss,an, ( + c < B = 1, so on is feasible action for (h, Sn. Cx). By definition of T. we then know that (h, Sh, Ch2 a4. is a node in T that is adjacent to (h, Sh, Ct.). Similarly, by (ii) and (iii), we then know that (h + 1, Sh+1, Cx++) a node in T and is adjacent to (h, Sb; Cb. an). Un)) Thus, Pr, = (Pr.: (h, 8hs Ch an); (h + 1, Ch+1)) is the desired path in T. This completes the induction.
For the second claim, fix any h and any Th E Fu. We show that for any N that is r-rralizable for some (T.) that Pr, S Pr. We proceed by induction on k.
Base Case. For the base case, consider k = h. In this case, the only realizable history conditioned 7p is Th itself. Trivially, we have that Pr,, Prr
Inductive Step. For the inductive step, we consider any k 2 h. Again, we can decompose Tk+1 (Tk Cg. Ck. $1+1) by Observation I where a& is feasible action for (k, Sk,, 2k) by Observation 2. By the induction hypothesis, we know that Pro. SPr Again, it is easy to see that the path Pro+, = (Pr., (k, 82, CR2 ax). (k + 1, Sk+1, Cx+1)) is well-defined path in T. is then immediate that Pri S Prr C CPr This completes the induction.
B.2. Proof of Lemma 3.4
Proof. We then proceed by backward induction on the number of nodes in P, h.
Base Case. For the base case, we consider h = H + 1. In this case, P ends in a H + node, which is TRUE by definition of T. Thus, the claim vacuously holds.
Inductive Step. For the inductive step, we consider any h < H. First suppose that (h, sh, Cn. is sink node. Then, by definition of TT there must be no safe actions for Th- If there were a feasible π E ITG realizing Th at time h, then Observation would imply a feasible action does exist, a contradiction. Thus, Th cannot be feasibly realized.
Now, suppose that (h, Sh, (n) has outgoing edges. Since any triple-node is an OR node, we know all out-neighbors of (h, 8h, Ch) must be FALSE. In other words, for any action a, there exists at least one super-path P (P, (h, Sh, Cu2 a), (h + 1, 8h+1, (x+1) ending in FALSE node. By the induction hypothesis, we know that the corresponding history Th+11 is not feasibly realizable. Therefore, any policy realizing Th+1 must violate the budget by definition. Moreover, by definition of the edges of T. if π realizes 7a and (a Th) > O, then π realizes Th+11 Consequently, if a policy π realizes Th and a, then x is not feasible. Since this holds for any possible action a, we have that Tr is not feasibly realizable.
The argument for why any feasible subhistory cannot realize Tr nearly identical: if it could realize 7y from some policy, then that policy must be infeasible.
B.3. Proof of Proposition 3.5
Proof. The proof of correctness follows from Lemma 3.3 and Lemma 3.4. Specifically, Lemma 3.3 (along with the fact that no feasible paths are removed due Lemma 3.4) implies that RS, 2 FS₁, and (5) 2 FA) for any 5 since all feasibly-realizable histories appear in T. Then, Lemma 3.4 implies that any paths containing FALSE nodes are not feasibly realizable. Consequently, RS,, C FSA and (8) FAA (8) for any 8.
For the complexity claim, we observe the time taken to construct the tree and perform a bottom-up tree evaluation is linear in the size of 'T. Moreover, the final loop to construct the feasible sets also requires touching every node and edge one time. Thus, the time complexity is dominated by the size of the fcasibility tree. The number of nodes in the tree is at most H.S. ADG since there most one tuple per time, state, action, and non-violating cumulative cost. Moreover, there are at
13

---

Anytime-Constrainet Equilibria in Polynomial Time
quadratic number of edges. Hence, the number of edges is most A times the number of nodes, leading total size of ((HHSDDe)))
C. Proofs for Section 4
For any given policy т, player i E [n]. time h E [H + 1], and history Th E HA where def compute player i's value from æ under cMG G recursively using the tabular policy evaluation equations (Equation 4.2.6 (Puterman, 1994)). In the cMG setting, these equations take the following form:
Policy Evaluation.
Sh, we can
(Th) B Bawnn (TT) ren(s,a)+ Σ a, 8,a) (() 0,6'
(CPE)
For traditional or action-constrained MG G, the policy evaluation equations take the more familiar form:
V.A (Tr) (a~
FEn(3, 1 (8,0)
(PE)
When # is Markovian, these equations further simplify to.
V. 1a
Frr(B,a)) + Σ PM(s' (
(*PE)
immediately treat any feasible Markovian policy for G = Definition 4.1(G, B) compact -ettoddd policy x for G by simply using the transformation т (T.) def (n(8,, (.) Going even further, we can treat history dependent policies for one game as full history dependent policies for the other. The key observation that any history тh E H4 has a unique equivalent history tn. E Hz, and vice versa.
Policy Translations. As mentioned in the appendix,
Specifically, the history Th ((s1, 0), a1, (12, (8h:Ch)) Cn)) and vice versa. Moreover, given Th it is easy to infer any Gg since O ck+1 Ck. and given it is easy to infer (52, Cx). We call Fr. the translation of to T and denote it by (Tk). Importantly, this conversion allows us to formally discuss a policies value in both games by simply modifying its input history.
($1, a1 C1. S2, .p. can be effectively permuted into the history Fb.
Lemma C.1 (Translations). For any feasible policy æ E HG, time h E [H +1, and partial history TI E HT if def (T(TT) the translation of Th Hi, then V (Tr) Vi, (F.). Moreover, π is Markovian in S, then (T))(T)) (5,, Ct.)
Proof. We proceed by induction h. We first note by Lemma 3.3 that all realizable histories of have (state, cumulative- cost)-pair in FS, and actions in FAx (8). Thus, in the argument below we can always assume histories realized by lead to valid history for G.
Base Case. For the base case, we consider h = H + 1. In this case, (.:+i(TH = 0 = (FH41) by definition of the value function at time H + 1. The second claim also holds since ( (8H+1, CH+1) = 0.
def sy and let
def (sh, Ch). We observe by (CPE)
Inductive Step. For the inductive step. we consider any h < H. Let and (PE) that,
14

---

Anytime-Constranned Equilibria in Polynomial Time
V (Th) (T
(s,(s, Echle Ph() s, saa)aant(
(TT)
(s, Cnlc Pa() s, V. (Fh, (6', c))
(5, P
Ps(s') 3
(L)(5, Σ PA Tha
V V.AA (FA).
The first line used (CPE). The second line applied the induction hypothesis along with the fact that Th+1 (Th a, c, s') translates Th+11 (Th, a, (s', G + c)) where is the translation of The The third line used the definition of F and from Definition 4.1. The fourth line used the fact that (Fx) T (Tr) by definition of the translation. The last line used (PE).
For the second claim, we note if is Markovian in S, then we can replace TA (Th) by (5) and inductively replace Vi (Th, a, 8") by V ( These replacements result in the second to last line exactly matching the RHS of (*PE). Thus, V,J. (Tx) VIJh (32, C,) in this case.
C.1. Proof of Lemma 4.3
We first make the following observation.
Observation 3. For any policy n, if N Tgg then IT((T) for any Fn and (H].
Proof. This is immediate from Lemma 3.4 as any policy whose support is contained in An(s) FA) at each stage is an feasibee policy.
We will also show the following stronger claim.
Claim 1. Suppose that is any MPE for G, and that n¹ def (=)) Th is a feasible deviation for player i. Then, for all times h E [ 1), and all partial histories Th E H.. we have that ViA (Tr) 2 Vi5((T). (Tr).
Proof. Observe that,
VrJ (sh a.) 2 (T.)()))) (T.).
The first equality used Lemma C.I for Markovian policy in S. The inequality used the fact that æ is a MPE for G with Fh being the unique translation of Th to an element of Hd. The final equality again used Lemma C.I.
Proof Lemma. ACSPE.
The lemma then follows as the observation yields condition (1) and the claim yields condition (2) of
C.2. Proof of Theorem 4.4
Proof. The correctness the algorithm is immediate from Proposition 3.5 and Lemma 4.3, For the complexity claim, the time the algorithm takes is ADG)) time to construct and poly(G) time to solve the L.P. Since the description
15

---

Anytime-Constrainee Equilibria in Polynomial Time
size of G is also polynomial in HSADG we then see the running time is bounded by O[poly([G), Dc)). The number of
G's states is most O(HSDG), and for each state up A joint actions' probabilities must be stored. Hence, the storage claim follows.
D. Proofs for Section 5
D.I. Proof Lemma 5.1
Proof. Let (A, u) be any action-constraineed matrix game, a be any solution to (C,P) X, u), i E [r] be any player, and of be any deviation strategy satisfying o' = 0_1 E A(X). By definition of the constraints, we see that,
Eave [u.(a)] = Σ o(a)ui(a)
aEA
Σ a(a)u((a)
aEX
E d((a))
Σ
a(a)u((a)
dEA
aex
Σ d((d))
Σ
Ca(a)u(ddaaa)
dEA:
E d((a))
Σ
Σ
oaai a(aaa)))sl
dEA:
a-IEA-; RiEA:
E
Σ
d(dd)--(aa))ud( a-1)
dEAiRLEEA.
Σ d'(d'uu((a)
d'EA
Ealwat [u;(a')]
The second line used the second constraint that ensured Supp(a) C X. The fourth line used the first constraint. The sixth line used the definition of marginals.
For the second claim, the fact that X * Ø implies there exist at least one feasible joint action, and so feasible exists. A specific a satisfying the other constraints is then immediate from classical game theory since it corresponds to the constraint of a normal-form game with possible oo entries (which can be replaced by the worst possible utility minus 1).
D.2. Proof of Theorem 5.2
We first make the following observation.
Observation 4. For any feasible action-constrained MG G, suppose that π is putpulfrom Algorithm 3(G). Then, E II
Proof. Since G is feasible, at any time h E [H] and state ă E S,, we know that (x) * 2 by definition. Thus, Lemma 5.1 implies that (CLP) always outputs a solution and that solution is supported on (5 for any stage game (h, 8). Since æ is exactly the collection of all such stage solutions, we then see that Supp T. (x)) An(s) for all (h,8). Thus, IT
The following claim will also prove useful.
Claim 2. For any feasible action--onstraaied MG G. suppose that is output from Algorithm 3GG). Then, for all players
i [n], times h [H + 1), deviations ग. satisfying N/ def (T),T_) Il and histories Fy E Hy', we have that 1,4 (5%) 2 (T.)
Proof. We proceed by induction on h.
Base Case. For the base case, we consider h = H + 1. this case, (3) = (x) by definition of the value function of feasible policy time +
16

---

Anytime-Constranned Equilibria in Polynomial Time
Inductive Step.
For the inductive step, we consider any h H. We observe that,
2.4 (8) (a
(3, Σ (s (3,0) (ha
2 (3) (3)
(1, + Σ
Ps (3
= Ba
(T, a)
2 (t)) (tr)
( (Tr, a)
(F.).
The first line used (PE). The second line uses the induction hypothesis. The third line used the definition of the Q-function. The fourth line used Lemma 5.1 and the fact that Supp( (F.))) S An by assumption that is feasible. The last line used the relationship between the Q and value functions.
Proof of Theorem. By Observation 4, we know the output policy of our algorithm is feasible, and by Claim 2 we know the output policy satisfies the stage game solution condition. Thus, it is MPE for G. The running time follows since run polynomial time LP solver on polynomial sized matrix game, O(A), for polynomial number of times, ((HS).
D.3. Proof of Theorem 5.3
Proof. We follow the same argument in (McMahan and Zhu, 2024). By ignoring insignificant digits, number in the form 2 2- + ......221. b_ + 20 + + 2 for some By dividing by 2- each number is of the form 20 + ... + ba- Notice, the largest possible number that can be represented in this form is ΣI 2 2d 1. Since each time h, potentially add the maximum cost, the largest cumulative cost achieved is at most 2 H 1. Since that is the largest cost achievable, no more than H can ever be achieved through all H times. Similarly, no cost can be achieved smaller than - H.
write each
Thus, each cumulative cost is in the range 1-2 + 1, H 1] and so at most 2d+1 H cumulative costs can ever be created. By multiplying back the 2 term, we see at most 2d+1 H costs are ever generated by numbers with d bits of precision. Since this argument holds for each constraint independently, the total number of cumulative cost vectors that could ever be achieved is (1/241)' Hence, De < =1=2(d+1)n
Theorem 5.3 then follows immediately from Theorem 4.4, Theorem 5.2, and the definition of fixed- parameter tractabil- ity (Downey and Fellows, 2012).
E. Proofs for Section 6
E.1. Proof of Lemma 6.4
For any h let C++1 := f(T++1) be random variable of the history defined inductively by and 2x+1 fu(C,, ck) for all k < h. Here, f is function that either rounds the immediate cost or truncates é, Notice that since f is deterministic function, čn can be computed from Th+1 for all & [h + 1]. Then, probability distribution over é is induced by the one over histories.
Proof. The key observation is that for each time h. generally é < cr S cn + (h 1)E holds. The one exception is when a very negative cost is received, in which case the agents' truncation may lead to higher cost in G. However, in that case, any action will still be allowed and so overestimated cost does not lead to issues. Formally, we can show
P c < < E (h- 1)f v E E S B- (H h + 1) mex 1.
The proof of this claim follows identically to the proof of Lemma in (McMahan and Zhu, 2024).
17

---

Anytime-Constrained Equilibria in Polynomial Time
Then, if is feasible for G, that pa Vhh E [M] & S B| Thus.
P vh [H], on - B (h 1) =
In words, is He-assibble for G.
E.2. Proof of Lemma 6.5
Proof. Approximate feasibility of any such æ from Lemma 6.4. Moreover, we observe that there are more feasible deviations (T/, m-i) in G since the cost constraint is easier to satisfy as also shown in the proof of Lemma 6.4, Thus, must also beat any feasible deviation for G. Hence, it is approximate equilibrium.
E.3. Proof of Theorem 6.6
Proof. The correctness of the algorithm follows immediately from Lemma 6.4 and Lemma 6.5. For the complexity claim, we first note that to construct & from G, we must loop over each approximate cost while performing the iteration to create G. The number of such immediate costs per agent i is the number integer multiples of & we consider, which consists of the Hemnn
range {
The number elements of this set is,
Caaa e
B₁
Hem
G (H +1)
-B; -
+15
8 +
Thus, if we consider the worst case player, the bound becomes |c [e + 2. Since this holds indepen- dently for each player, the total number supported immediate costs in each approximate cost distribution is at most O [|c" (H+1)- Bl Moreover, since each immediate cost is integer multiple of f, any cumulative cost in the range
widest {H
B: Hemnnr
11
}. Overall, see the time needed to construct & and the size of the state set of G The rumning time claims then follow from the previous running time claims.
blow up by factor of 0(
B B
E.4. Proof of Corollary 6.7
Proof. The proof is immediate from Theorem 6.6 and the definition of &.
E.5. Proof of Corollary 6.8
Proof. The proof is immediate from Theorem 6.6 and the definition of l. Note, here are using a vector &. It is easy that the proof of Lemma 6.4 easily handles this variation.
F. Extensions
The infinite discounted case, and generalized anytime constraints case follow similarly to in (McMahan and Zhu, 2024). As for almost sure constraints, we note that we can the same meta-graph construction, but we start by including all possible cumulative costs, since we do not know which may eventually lead success until we have seen the end. All other results follow similarly.
For ACCE, we observe all of our results follow with the minimal change of considering strategic modification deviation á π instead of the general deviation (T m-)) we originally considered. Our LP solution is also easily adapted by replacing the CCE condition with the CE condition.
18


Reviews:
[{"review_id": "cW6GKUurPj", "reviewer": "Reviewer_Gjeu", "summary": "The paper extends anytime constraints to the Markov game setting and the corresponding solution concept of anytime-constrained equilibrium (ACE). The authors provide: (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. The approximation guarantees are the best possible unless P = NP.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! Please see our general rebuttal below, which addresses the relevancy of anytime constraints in the literature and comparisons to standard expectation constraints. We also provide additional commentary below the general rebuttal.\n\n--- *General Rebuttal* ---\n\nWe appreciate the reviewers' thoughtful feedback and would like to address the general concerns regarding the relevancy of the ACE concept and the absence of empirical evaluation.\n\n**[Anytime Constraints Literature]** Anytime and almost-sure constraints were introduced to the Constrained Reinforcement Learning (CRL) literature to handle safety and resource management tasks and have received much recent attention. Anytime constraints are important to many applications that we mentioned in the introduction, including the popular settings:\n1. Self-driving cars with fuel and safety constraints,\n2. Autonomous rescue vehicle teams for disaster relief scenarios with safety and rescue constraints.\n\nObserve that both of these applications, in addition to many others, are naturally multi-agent settings, yet previous works discussing these applications have only designed algorithms for the single-agent setting. This discrepancy between the motivating applications and the work's algorithms motivated our investigation of anytime constraints in the multi-agent setting. Even though previous works have already motivated anytime-constrained multi-agent applications, we are the first to formalize and develop algorithms for these constraints in the multi-agent context. We would be happy to add more motivating applications from previous works if the reviewers feel this would be beneficial!\n\n**[Empirical Evaluation]** Being a work on theoretical foundations, we excluded empirical evaluations for two key reasons.\n1. First, the main purpose of our work is to address the problem's intrinsic computational complexity: \"For what class of cMGs can ACE be computed (approximately) in polynomial time?\" This mirrors the question posed in the original paper on anytime constraints for the single-agent setting [1], allowing us to fairly compare the computational complexity of the single-agent and multi-agent settings. In particular, we showed that while exact computation is harder in the multi-agent setting, approximate computation is not much harder. Importantly, we emphasize that establishing worst-case complexity bounds requires mathematical proof; empirical evaluation cannot establish such bounds.\n2. Second, we designed the first-ever algorithm for anytime-constrained Markov games. Consequently, there are no previous works to compare against. The most similar setting to ours is the classical expectation-constrained Markov game, but anytime constraints and expectation constraints are fundamentally different, both structurally and computationally [1]. Notably, expectation-constrained policies can arbitrarily violate anytime constraints and can be computed in polynomial time, whereas anytime-constrained policies are NP-hard to compute.\n\nAlthough we do not perform any empirical evaluation, we acknowledge their importance and hope our theoretical insights will be beneficial for the design of practical algorithms in the future.\n\n**[Our Contributions]** We would like to emphasize our theoretical contributions to the literature. Not only is our algorithm the *first ever* algorithm for anytime-constrained Markov games, but it is also provably *optimal* in terms of approximation guarantees. On the path to creating this algorithm, we developed new insights about anytime-constrained policies through the notion of realizability trees and established fixed-parameter tractability bounds for anytime-constrained Markov games. We also developed the first-ever polynomial-time algorithm for solving action-constrained Markov games that we use as a subroutine in our main algorithm. Our results imply the complexity of approximating anytime-constrained Markov games is at most polynomially larger than for single-agent anytime-constrained MDPs.\n\n**References**\n\n[1] \"Anytime-Constrained Reinforcement Learning\", Jeremy McMahan and Xiaojin Zhou. AISTATS 2024.\n\n--- *End of General Rebuttal* ---\n\n**[Q1]** As mentioned in the general rebuttal, these two constraint types are generally incomparable. In terms of applications, anytime constraints are preferred in safety contexts since an expectation-constrained policy could be arbitrarily unsafe under some realizations. \n\n**[Q2]** Generally, non-Markovian policies are not feasible for anytime constraints [1]. The policies we construct are augmented and so just a compact history dependent policy. Similarly, non-stationarity is required for finite-horizon settings [1], but stationary ACEs are possible in infinite discounted settings (though again Markovian only in the augmented space).\n\nThank you for your feedback and let us know if you have any other questions!", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "N.A.", "theoretical_claims": "I went through the correctness of many proofs but not in depth.", "experimental_designs_or_analyses": "N.A.", "relation_to_broader_scientific_literature": "The paper studies the solution concept of anytime-constrained equilibria in constrained Markov games. The key contributions of the paper in the context of related work are based on the definition of anytime-constrained equilibria, and essentially extend to the multi-agent setting a previous work [1], which studies single-agent constrained MDPs. The proposed constrained Markov game setting differs from the more established safe MARL setting (e.g., see [2]) introducing an extra cost function with anytime aggregated cost constraints, instead of explicitly using constraints for the value function. In the context of the proposed setting, the main results of the paper are interesting and novel.\n\n\n[1] McMahan, Jeremy, and Xiaojin Zhu. \"Anytime-constrained reinforcement learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.\n\n[2] Chen, Ziyi, Shaocong Ma, and Yi Zhou. \"Finding correlated equilibrium of constrained markov game: A primal-dual approach.\" Advances in Neural Information Processing Systems 35 (2022): 25560-25572.", "essential_references_not_discussed": "The authors have included the important references related to their work.", "other_strengths_and_weaknesses": "### Other strengths\n- The paper is well-written and easy-to-follow.\n- The paper provides an efficient computation for action-constrained Markov games, which can be of independent interest.\n- The authors use interesting, and different, techniques, as well as non-trivial reductions to prove the main results.\n- The main results hold for the more general settings (e.g., the infinite horizon setting)\n\n### Weaknesses\n- The anytime-constrained equilibria studied in the paper are not a well-established solution concept in the literature.", "other_comments_or_suggestions": "- Maybe it would be helpful the authors to provide a table with related settings in constrained Markov games and similar solution concepts.", "questions_for_authors": "- What is the relation between the anytime-constrained equilibrium and the more established constrained equilibria of [1] ?\n- What can we say about Markovian/Non-Markovian and stationary/non-stationary anytime equilibria in the proposed constrained Markov game setting ?\n\n[1] Chen, Ziyi, Shaocong Ma, and Yi Zhou. \"Finding correlated equilibrium of constrained markov game: A primal-dual approach.\" Advances in Neural Information Processing Systems 35 (2022): 25560-25572.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7nkNaqNQ47", "reviewer": "Reviewer_7CQV", "summary": "This paper introduces the concept of anytime-constrained equilibria in the context of constrained Markov games, where agents must adhere to strict budget constraints at every time step. The authors extend the notion of anytime constraints from single-agent settings to multi-agent settings. The authors provide a method to determine whether a feasible policy exists under any time constraints. They propose an FPT algorithm for computing subgame-perfect ACE, which runs in polynomial time when the cost precision is small. At last, the authors also present an algorithm for computing approximately feasible ACE in polynomial time, provided the maximum supported cost is bounded by a polynomial factor of the budget.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We will make sure to improve the paper using the suggestions mentioned. Please see our general rebuttal in the rebuttal section for Reviewer Gjeu, which addresses several of your concerns, including practical applicability. For your other concerns, please see below.\n\n**[Scalability]** First, we would like to emphasize that the FPT result can be restrictive if the precisions are high, but this is a fundamental limit in the problem itself rather than a flaw in our particular algorithm design. This potential scalability issue is exactly why we then derive provable approximation algorithms that run in polynomial time regardless of the precision of the input numbers. We also note that this is the very first set of algorithms for the problem, and we hope our insights will lead to faster algorithms in the future.\n\n**[Uniqueness]** To clarify, we do not assume existence in this paper. In fact, developing an algorithm to determine the existence of an ACE for an acMG is the primary purpose of section 3, which culminates in Algorithm 1. In terms of uniqueness, we do not have any characterization for the uniqueness of ACE; to our knowledge, a characterization of uniqueness is an open question for standard CCE as well. Nevertheless, the non-uniqueness of ACE is not an issue for our algorithms.\n\n**[Multiple Constraints]** Handling multiple constraints is immediate by adding dummy agents that capture that constraint. Alternatively, one could think of each agent as keeping a cumulative cost vector for each of its constraints. Either way, whether the constraints conflict or not, only affects the existence of a feasible policy, not our algorithmic approach. The complexity of our methods then scales exponentially with the number of constraints instead of the number of agents. This seems to be a fundamental bottleneck, as recent works have shown that anytime feasible policies are NP-hard to even find approximately when the number of constraints is too large, reflecting the standard curse of multi-agents.\n\n**[Infinite Discounting]** The infinite discounted setting is immediate just by using the standard trick of effective horizon. We can truncate the game at the point where the future discounted cost is at most $\\epsilon/2$ for all players and then run our approximation algorithm with parameter $\\epsilon/2$. This guarantees us a solution that only violates the budget by $\\epsilon$ as before and retains polynomial complexity since the discounting always ensures this effective horizon will be polynomial-sized. Thus, the infinite discounted case enjoys the same theoretical claims. \n\nThanks again, and please let us know if there is anything else we can clarify!", "claims_and_evidence": "Yes, all the claims are well justified.", "methods_and_evaluation_criteria": "No experiments are included in this paper.", "theoretical_claims": "The proofs look good to me. I checked the proof of main theorem 4.4.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper studies cMDPs and constrained MARL, introducing concepts like ACE and providing efficient algorithms for their computation. By addressing the challenge of enforcing constraints at every time step in multi-agent settings, the paper contributes to the broader goals of safe and reliable AI, bridging the gap between theoretical research and practical applications. Its connection to prior work on approximation methods and equilibrium concepts further solidifies its relevance to the scientific literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper introduces ACE for multi-agent systems and provides rigorous proofs for their existence, NP-hardness, and efficient computation via FPT and approximation algorithms.  However, the paper lacks empirical evaluation, which limits its practical validation, and the reliance on low-cost precision for the FPT algorithm potentially restricts scalability. The complexity is so large since $D_G$ could be significantly large.", "other_comments_or_suggestions": "The paper defines feasibility via realizable traces, ensuring all histories satisfy budget constraints at every step, which is ideal for safety-critical applications. An alternative is expectation constraints, where only the expected cost must stay within bounds. The authors could discuss the trade-offs between these definitions and their suitability for different applications.", "questions_for_authors": "The paper assumes the existence of equilibria but does not discuss uniqueness. Are there conditions under which the anytime-constrained equilibrium is unique, and how does non-uniqueness affect the proposed algorithms?\n\nThe paper briefly mentions handling multiple constraints. How does the complexity of the algorithms scale with the number of constraints, and are there specific challenges when constraints are conflicting?\n\nFor infinite-horizon problems, how would the feasibility tree and backward induction approach need to be adapted, and what are the theoretical guarantees in this setting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gZarIU9bYv", "reviewer": "Reviewer_JvMv", "summary": "This paper introduces anytime constraints to the Markov game setting and develops a comprehensive theory of anytime-constrained equilibria (ACE). The authors present three main contributions: (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. The work also develops efficient algorithms for action-constrained Markov games.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! We will make sure to improve the paper using the suggestions mentioned. Please see our general rebuttal in the rebuttal section for Reviewer Gjeu, which addresses your concerns about empirical evaluation and existing methods. For your other concerns, please see below.\n\n**[Q1 + Q4]** These are addressed thoroughly in the general rebuttal, but we also mention here that there are no existing methods to compare to, as our work is the very first to design any algorithm whatsoever for anytime-constrained Markov games and for action-constrained Markov games.\n\n**[Q2]** Yes, the methods do extend, but the analysis is more involved, so we have deferred it to future work.\n\n**[Q3]** Which parameters is the reviewer referring to here? The only parameter in the control of the user is the violation parameter $\\epsilon$. In terms of $\\epsilon$, Corollary 6.7 and 6.8 indicate the running time scales as $1/\\epsilon^n$ where $n$ is the number of agents. We conjecture this scaling is unavoidable due to the usual curse of multi-agents. \n\nThanks again, and please let us know if there is anything else we can clarify!", "claims_and_evidence": "See the theoretical claim section below. The experimental evaluations are missing.", "methods_and_evaluation_criteria": "Equilibirum cirteria is used for the evaluation.", "theoretical_claims": "1. Extension of anytime constraints to multi-agent reinforcement learning\n2. Computational characterization of feasible policies using AND/OR trees\n3. Fixed-parameter tractable algorithm for computing subgame-perfect ACE\n4. Polynomial-time algorithm for approximately computing ACE\n5. Development of efficient algorithms for action-constrained Markov games", "experimental_designs_or_analyses": "The experiments are not provided in the paper. It would be beneficial if authors can provide at least some basic experiments that demonstrates the usefulness of the method and compare it with the other state of the art methods.", "relation_to_broader_scientific_literature": "The paper is well written and is the first to provide anytime constraint for the mulit-agent system. The idea is therefore, novel and the  authors did a fairly good job to provide a clear disctinction the work with the existing literature.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n\nSee the theoretical claims section above.\n\nWeakness:\n\n1. Lack of experimental results or case studies\n2. Limited discussion on the practical implications and potential applications\n3. Assumption of finite support for cost distributions may be restrictive for some scenarios", "other_comments_or_suggestions": "The paper is generally well-written and structured. The introduction provides a clear motivation for the work and situates it within the existing literature. The technical sections are detailed and rigorous. However, it is desirable to \n\n1. More intuitive explanations or examples to illustrate key concepts\n2. A dedicated section on potential applications or empirical evaluations\n3. A more extensive discussion of limitations and future work directions\n\nOverall, the paper presents a significant theoretical contribution to the field of constrained multi-agent reinforcement learning. However, it could be strengthened by including practical demonstrations and a more thorough discussion of real-world implications.", "questions_for_authors": "1. How does the performance of the proposed algorithms compare to existing methods in practice?\n2. Can we extend the  to handle continuous state and action spaces?\n3. How sensitive are the algorithms to the choice of parameters, particularly in the approximate case?\n4. Are there specific real-world scenarios where this approach provides significant advantages over existing methods?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: The paper introduces anytime constraints for Markov games and studies anytime-constrained equilibria. There are three main contributions: (1) a characterization of feasible policies, (2) a fixed-parameter tractable algorithm for computing anytime constrained equilibria, and (3) a polynomial-time algorithm for approximately computing anytime constrained equilibria. Overall the paper received slightly positive reviews from all the reviewers and there was an agreement about the value of the contributions of the paper. It seems the paper is above the bar for acceptance. We recommend a weak accept as there was no clear accept among the reviewers.
Decision: Accept (poster)