WorksComputer Science
Subprocess-Constrained Markov Decision Processes
Abstract
Constrained Markov decision processes (CMDPs) typically bound expected cumulative cost from an initial state. Such a guarantee can be insufficient when a policy must remain feasible after every history it may encounter. We introduce subprocess-constrained MDPs (S-CMDPs), which require the expected discounted cost of each continuation, conditional on any reachable history, to satisfy a bound determined by the current state. This stronger requirement changes the structure and complexity of the problem: we show that stationary policies can be strictly suboptimal, and finding even an approximately optimal stationary policy is NP-hard. We adapt a recently introduced value-set iteration framework to show that history-dependent policies surprisingly overcome both obstacles. Our polynomial-time algorithm represents such a policy implicitly: its expected reward is within of the optimal feasible value, it violates each subprocess cost bound by at most , and its action distribution can be computed in polynomial time for any given history.
Introduction
Markov decision processes (MDPs) are a standard model for sequential decision-making under uncertainty. At each step, an agent observes the state of the environment, chooses an action, and receives a reward as the environment evolves stochastically. In many domains, however, decision-making is subject to requirements that are not captured by reward alone: energy consumption must stay within a budget, risk must remain below a safety threshold, and violations of service-level targets must be limited. Constrained Markov decision processes (CMDPs) [3] address such requirements by augmenting an MDP with a cost function and imposing a constraint, typically on the expected cumulative cost over the entire trajectory. This global, expectation-based formulation has a long history in stochastic control and operations research and remains central to modern safe reinforcement learning [17] (Garcıa and Fernández 2015).
Yet, in safety- and reliability-critical applications, the classical CMDP viewpoint can be misaligned with how systems are deployed and assessed. Standard constraints are evaluated only from the initial state, providing guarantees tied to the beginning of the trajectory. In many settings, the continuation from time step should satisfy the same requirements as a process starting anew. It is therefore natural to require the constraints imposed on the full process to hold for every subprocess following a reachable history. Without such subprocess constraints, a policy may satisfy a global expected-cost budget while behaving unacceptably after certain histories. For example, low early costs may offset high future costs under the global constraint, or high-cost trajectories may be averaged against low-cost ones.
Such concerns arise naturally in practice. For instance, when an autonomous robot reaches a crowded region or a narrow passage near humans, safety in expectation from the initial deployment state is not enough; from the newly reached configuration, the controller should still keep future collision risk below an acceptable threshold [13, 28].
Similarly, in online services governed by service-level objectives (SLOs), reliability is monitored continuously through service-level indicators and error budgets. Exhausting an error budget can trigger responses such as reliability work or deployment freezes [7, 8]. It is unacceptable to enter a congested state from which expected future latency or availability violations exceed acceptable thresholds, even if the initial expected violations remain within budget. In these settings, constraints that apply only at initialization can be too weak.
Our Work and Contributions
To address this limitation, we introduce subprocess-constrained MDPs (S-CMDPs). Informally, S-CMDPs require policies to remain feasible under a “restart at time ” interpretation after every reachable history, capturing a subprocess-level notion of safety and reliability not enforced by classical CMDPs. Although this may appear to be a modest change in formulation, it fundamentally changes the problem: standard CMDP solution methods do not transfer directly. We study the algorithmic aspects of S-CMDPs and establish the following foundational results:
We identify a fundamental computational separation between S-CMDPs and standard CMDPs. Stationary policies, which suffice for optimality and can be optimized efficiently in classical MDPs and CMDPs, can be strictly suboptimal in S-CMDPs. More importantly, even if we accept this loss of optimality and restrict attention to stationary policies, finding the best policy in that class, even just approximately, is NP-hard.
We show that history-dependent policies, which can be necessary for optimality, can be handled efficiently using value-set iteration (VSI). This is surprising because representing a history-dependent policy explicitly requires space exponential in the horizon. In S-CMDPs, allowing history dependence is key to establishing tractability. Our approach leverages an implicit representation of history-dependent policies: rather than explicitly specifying action distributions, the policy is given by an algorithm that efficiently computes its action distribution for any given history.
VSI extends classical value iteration to a set-valued dynamic programming framework. Unlike classical value iteration, the associated set-valued operator is generally not a contraction, so convergence requires a different analysis. We characterize the solution of an S-CMDP as a fixed point of this operator and develop a bicriteria approximation scheme that computes a fixed point of an approximate operator in polynomial time. This yields an -optimal history-dependent policy, in contrast to the NP-hardness of computing such a stationary policy.
Our results establish S-CMDPs as a distinct extension of CMDPs that enforces a stronger notion of safety while remaining tractable through our VSI framework.
Related Work
Our work builds on several strands of CMDP and safe RL research, while differing from them in its treatment of onward feasibility. Classical CMDPs constrain expected cumulative cost from the initial state and admit strong structural results and solution methods, including linear programming and Lagrangian optimization [2, 3]. Much of modern safe RL inherits this formulation; for example, constrained policy optimization (CPO) [1] targets global constraints while providing guarantees about constraint satisfaction. Surveys of safe RL [16, 17] similarly center on initial-state expectation constraints and closely related risk criteria. Our S-CMDP model imposes a stronger feasibility requirement: onward feasibility after every reachable history, rather than only feasibility in expectation from the start.
Several lines of work in safe RL and constrained MDPs strengthen safety requirements at individual times or states. For example, peak-constrained CMDPs [5] require constraints to hold at every time step with probability one; in such formulations, the constraint can often be viewed as inducing a safe action set at each state-time pair. Related safe RL formulations impose instantaneous hard constraints that rule out unsafe actions or unsafe states during learning [4, 23, 26]. A distinct line of work studies instantaneous constraints in expectation and develops Lagrangian or augmented-Lagrangian methods for enforcing time-indexed constraint violations [20]. Recent work on state-wise constrained policy optimization also imposes constraints at individual states [27], including variants that guide learning by requiring visited states to remain within a safe state set [24].
These formulations are complementary in motivation, but they primarily constrain local quantities: immediate action safety, next- or visited-state safety, worst-case state-wise violations, or expected instantaneous violations. By contrast, S-CMDPs constrain the entire discounted continuation from each reachable history, which spans multiple or even infinite time steps rather than only the next action, transition, or visited state.
Closer to our model is the recent work on anytime-constrained MDPs [21]. Anytime-constrained MDPs also recognize that feasibility from the initial state alone may be insufficient, and instead require the agent to avoid violating its budget at any time. McMahan and Zhu [ [21] show, among other results, that Markovian policies are generally insufficient unless augmented with additional information, such as cumulative cost. Our S-CMDP formulation shares this motivation but bounds the expected onward cost of every subprocess rather than the accumulated cost along every prefix. This distinction leads to different algorithmic techniques. Anytime-constrained MDPs motivate state augmentation by cumulative cost or related bookkeeping variables [21]. In contrast, we use value-set reasoning over attainable subprocess values, which enables a direct characterization of feasible continuations and a polynomial-time procedure for computing near-optimal history-dependent policies.
On the algorithmic side, value-set iteration has precedents in game theory, where similar set-valued dynamic programming methods have been used to compute equilibria in sequential games [22, 19, 15, 14] (Derman and Isbell 2009). In these settings, players’ incentive constraints are defined in terms of expected future payoffs and must be satisfied in every subgame, mirroring the subprocess constraints in our model. The recent work of Gan and Majumdar [ [14] provides a detailed algorithmic study of value-set iteration for computing extensive-form correlated equilibria in Markov games. Our work adapts this framework to S-CMDPs, a setting that we believe admits an even broader range of applications in planning, control, and RL. At a technical level, our VSI framework rests on a fixed point of a monotone operator. The computation of Tarski fixed points has recently attracted growing attention in theoretical computer science [12, 9, 6] (Etesami et al. 2019).
The S-CMDP Model
An S-CMDP is given by a tuple . The components other than and define a standard discounted MDP: is a finite state space, with initial state ; is a finite action space; is the transition kernel; is the reward function; and is the discount factor. The additional components and specify a cost function and a state-wise threshold for each . Without loss of generality, we assume that rewards and costs lie in .
Let a policy assign an action distribution to each finite history . For a reachable history , we define the onward reward value as
where denotes expectation conditional on under , and denotes the probability of observing . Similarly, denotes the onward discounted cost, defined by replacing with .
Our objective is to maximize expected discounted reward while bounding the onward discounted cost after every reachable history:
The formulation imposes a constraint on every subprocess starting from a reachable history .
Why Not Stationary Policies
In standard CMDPs, stationary policies—which map each state to an action distribution—suffice for optimality. This is no longer the case for S-CMDPs. The maximum value attained by stationary policies can be strictly lower than that attained by history-dependent policies. Moreover, even if we accept this loss of optimality and restrict attention to stationary policies, optimizing over this class is computationally intractable. Both limitations persist in the finite-horizon setting.
Suboptimality of Stationary Policies Consider the S-CMDP shown on the right. The process starts in either or with equal probability.1 There are two actions, and . All transitions are deterministic, as depicted in the figure, and are independent of the chosen action. All rewards and costs are zero except for . The cost thresholds are and .
The only way to obtain positive reward in this instance is to choose action at , which also incurs cost 1. Under any stationary policy, however, choosing at with positive probability would violate the subprocess constraint at , where the onward cost must not exceed . Hence, every feasible stationary policy must choose action at with probability 1, yielding value zero.2
In contrast, history dependence allows the agent to condition its action at on the preceding state: choose if the trajectory starts from , and choose if it starts from . This satisfies all subprocess constraints and yields expected value , strictly outperforming all feasible stationary policies.
Intractability of Stationary Policies A further limitation of stationary policies is computational intractability. Optimizing over feasible stationary policies, even approximately, is NP-hard. This intractability persists even when the subprocess constraints are relaxed to permit small violations. We formalize this claim with the following approximation notion and Theorem 1.
Definition 1 (()-optimal policy). A policy is -optimal if the following conditions hold:
-feasibility: violates every subprocess constraint in Eq. (2) by at most .
-optimality: for every policy in the class under consideration that satisfies (2) exactly.
Unless stated otherwise, the class contains all policies. In Theorem 1, both the computed policy and the policies used for comparison are stationary.
Theorem 1. Fix any discount factor . There exist constants such that computing a stationary policy that is -optimal among stationary policies is NP-hard.
For the remainder of the paper, we turn to history-dependent policies and show that they overcome both limitations of stationary policies.
Enabling History Dependence: Two Birds with One Stone
While allowing history dependence removes the restriction behind the preceding suboptimality example, its computational tractability is far from obvious. Because the number of reachable histories can grow exponentially with the horizon, even writing down a history-dependent policy may be infeasible, let alone computing an optimal one.
We therefore adopt an implicit computational view and ask: given any history , can we efficiently compute the action distribution of a near-optimal policy at ? An algorithm that does so allows us to execute the policy without explicitly storing all action distributions; effectively, it encodes the policy.
The value-set iteration (VSI) framework provides an answer to this question. In this section, we first introduce a central concept underlying the VSI framework—the achievable value sets—and explain how it enables us to handle history-dependent policies.
Achievable Value Sets
Our goal is to characterize which combinations of cumulative reward and cost can be attained by feasible policies. To this end, we view each state–action pair as producing a two-dimensional payoff whose components are reward and cost. Formally, define a payoff function such that
for every . Similarly, for any policy and history , we write for the vector of onward discounted reward and cost.
Definition 2 (Achievable value set). The achievable value set of a state , denoted , is the set of all vectors that can be achieved by some feasible policy when starting from , i.e., for some satisfying (2).
We call functions like , that map each state to a subset of , value-set functions.
Using , we can express the optimal objective value in Eqs. (1) and (2) as the maximum reward component over the achievable set at :
If were known, this maximization would give the optimal value immediately. To further obtain a policy that achieves the optimal value, we next introduce a procedure that unrolls any target value into a feasible policy with . We will return to the computation of and address the remaining algorithmic challenges in the following sections.
Unrolling Policies Based on Achievable Sets
Consider an arbitrary state and a target value vector . By definition, some feasible policy achieves , so a Bellman-style expansion gives
Here is the action distribution at state ; and for each pair , is the onward value, given history .
Crucially, the fact that each onward value is achieved in the subsequent process means that:
where only the triples with positive probability under and the transition function are relevant, as the others do not contribute to Eq. (3).
Policy Execution via Recursive Value Expansion Eqs. (3) and (4) lead to the recursive value expansion procedure in Algorithm 2. The procedure expands a given target value into an action distribution and a collection of onward values based on Eqs. (3) and (4). It samples an action from and observes the next state . The onward value is then chosen as the new target, and the procedure recurses. We fix a deterministic rule for selecting a valid decomposition whenever several are available.
Expand(v, s):
Return (π̄, w) satisfying Eqs. (3) and (4).
Algorithm 1: Expand.
Achieve(v, s):
1. (π̄, w) ← Expand(v, s).
2. Sample a ∼ π̄; observe s′ ∼ p(· | s, a).
3. Achieve(v′, s′), where v′ = w(a, s′).
Algorithm 2: Achieve.
Since , there always exists a valid decomposition into and . Moreover, Eq. (4) ensures that the new target value also lies within the corresponding achievable set, so a valid decomposition exists at the next recursive call as well. Thus, at every recursive call with current state , the target value lies in , so the procedure can continue indefinitely.
We can verify that the recursive procedure has expected discounted reward and cost exactly equal to . Effectively, the procedure implements a policy that achieves (i.e., ).
Notably, executing this policy requires storing only the current target value. At each step, the target is expanded into 1) an action distribution used to sample the next action and 2) onward values used to update the target. Thus, the target serves as a fixed-dimensional summary of the history, independent of the horizon length.3
Computing the Policy Returning to the algorithmic question posed at the beginning of this section, we can adapt the recursive expansion procedure to compute the action distribution for any history starting at and any target , where is a policy that achieves . We present this algorithm as ActProbs in Algorithm 3.
ActProbs(v, h = (s₀, a₀, . . . , sₜ)):
1. (π̄, w) ← Expand(v, s₀).
2. If t = 0, then return π̄.
3. Return ActProbs(v′, h′), where
v′ = w(a₀, s₁) and h′ = (s₁, a₁, . . . , sₜ).
Algorithm 3: ActProbs.4
Rather than sampling actions and states, ActProbs follows the given history . On reachable histories, its recursive calls return the action distribution induced by Achieve() conditional on .
Let be the policy computed by ActProbs(), i.e., for every history starting at . It can be verified that is feasible and . Hence, choosing as the target yields an optimal policy for the S-CMDP.
The following sections formalize these claims. In summary, the algorithmic challenge of S-CMDPs now reduces to:
computing , and
We introduce the VSI algorithm next.
Value-Set Iteration
At a high level, our approach mirrors classical value iteration for unconstrained MDPs: we define an operator whose fixed point characterizes the achievable values, and we design an iterative process that converges to this fixed point. In our setting, however, the operator acts on sets of vectors rather than scalar values. More crucially, due to the subprocess constraints, its convergence requires a fundamentally different argument from that used for classical value iteration.
as a Fixed Point
To begin, let us characterize as a fixed point. Recall from Eqs. (3) and (4) that every admits a Bellman-style decomposition. In our S-CMDP model, there is one additional necessary condition: at state , the cost component of every achievable vector must not exceed the state-wise threshold:
This condition is not just necessary: together with Eqs. (3) and (4), it is sufficient for the achievability of , as the following lemma states.
Lemma 2. For any and , we have if and only if and there exist a distribution and a vector for each such that Eqs. (3) and (4) hold.
Lemma 2 characterizes as a fixed point of the following operator on value-set functions. For any ,
where we use the shorthand to represent the right-hand side of Eq. (3), and
consists of all pairs satisfying the onward achievability condition for every , with respect to (i.e., Eq. (4) with replaced by ).
Intuitively, consists of values obtained by combining an action distribution with onward values from , subject to the cost threshold at . Lemma 2 immediately yields the following corollary.
Corollary 3. is a fixed point of , i.e., .
Convergence of Value-Set Iteration to
This suggests computing a fixed point of to obtain . For discounted unconstrained MDPs, the Bellman optimality operator admits a unique fixed point, which is exactly the optimal value function. The existence and uniqueness of this fixed point follow from the contraction mapping theorem (Banach’s fixed-point theorem), thanks to the Bellman operator being a contraction.5 Thus, through repeated application of the Bellman operator, classical value iteration converges to the fixed point at a geometric rate.
Motivated by the above, it is tempting to design a similar iteration scheme by repeatedly applying to a value-set function (Algorithm 4), in the hope that it converges to .
VSI(, ):
Repeat until .
Return .
Algorithm 4: VSI (value-set iteration).
This approach, however, requires more care. Unlike the classical Bellman operator, need not be a contraction, so the contraction mapping theorem does not apply in general. Its fixed point may not be unique;6 moreover, repeated application of from an arbitrary initial value-set function may fail to converge or may converge to an undesired fixed point.
As it turns out, the following monotonicity property of becomes key to our convergence argument.
Lemma 4 (Monotonicity). If , then 7
Convergence by Monotonicity The monotonicity property motivates a fixed-point argument inspired by Tarski’s fixed-point theorem [25]. The theorem states that the fixed points of a monotone self-map on a complete lattice form a complete lattice and, in particular, include a greatest fixed point. In our setting, is precisely the greatest bounded fixed point of : it contains every bounded fixed point of (as we establish directly in Lemma 7).
More importantly, monotonicity suggests a way to find this fixed point. If we initialize value-set iteration (Algorithm 4) from an upper bound of that maps into itself, i.e., , we obtain a decreasing sequence of value-set functions. Indeed, since all rewards and costs lie in , the ball
provides such an upper bound, as the following lemma states.
Lemma 5. and 8
We show that the iterates of VSI() converge to . Let be the sequence it generates:
, and
for all .
By Lemma 5, , so monotonicity of gives . Since and , we obtain
Recall that and , so this becomes
By monotonicity, repeatedly applying to these inclusions propagates the nesting to all , yielding the following result.
Lemma 6. for all .
Consequently, is a decreasing sequence bounded below by . Each is compact, and a compactness argument shows that the intersection of these iterates is a fixed point of (see the proof of Theorem 8). This fixed point must equal , which bounds it not only from below but also, by the following lemma, from above.
Lemma 7. If is bounded and , then .
The proof of Lemma 7 follows the recursive construction in § 4, where we showed that every can be achieved by the Achieve procedure (Algorithm 2). Here, we show more generally that for any bounded fixed point of , every can be achieved by the same procedure, with in place of in the onward value constraint in Eq. (4). This modified procedure is well defined because guarantees a valid decomposition at every recursive call. Consequently, every is realized as the expected discounted return of a feasible policy and is therefore achievable from .
These lemmas lead to the following convergence theorem.
Theorem 8. as .9
Approximate VSI for Finite-Time Convergence
We have established the convergence of value-set iteration to , but this does not automatically yield a finite-time algorithm, let alone an efficient one. To obtain a practical algorithm, two issues must be addressed: 1) ensuring termination in finitely—preferably polynomially—many iterations; and 2) representing value-set functions in a way that allows applications of to be computed efficiently.
As in practical implementations of value iteration, we adopt an approximation approach. Rather than computing exactly, we iterate an approximate operator that reaches a fixed point in finitely many steps. As we show in this section, this approach is sufficient for our purpose of computing an -optimal policy (Definition 1).
Approximate Operator and Convergence
Starting from , repeated applications of produce convex polytopes at each state (as the LP formulation in § 6.3 makes explicit). These convex polytopes can in principle be represented by linear inequalities, but the issue is that the number of inequalities can grow exponentially under repeated applications of . To control the representation complexity, we discretize the two-dimensional value space using a grid and approximate based on this discretization.

Figure 1 (PDF p. 9). Illustration of .
Approximate Operator Choose a positive grid spacing . Let be the set of grid points. For any , define
where denotes the convex hull. Define the approximate operator as
where denotes the -neighborhood of , consisting of all points within distance of some point in .
Figure 1 illustrates this construction. Whenever is convex, its -neighborhood is also convex, and we can verify that the following inclusions hold:
Figure 1.
Specifically, the left-hand inclusion holds even without convexity of : every point of lies in a grid cell whose vertices are within distance of that point; the cell is contained entirely in as well as its grid hull. The right-hand inclusion follows because the convex neighborhood contains the convex hull of its grid points.
Finite-Time Convergence The operator remains monotone. To initialize VSI, let denote the smallest grid-aligned ball that strictly contains , i.e.,
We run (Algorithm 4) with . This yields a sequence such that:
, and
for all .
The strict outer rounding of ensures . Together with and the monotonicity of , this makes a decreasing sequence of nested value sets. We extend Lemma 6 to this sequence as follows.
Lemma 9. for all .
Given Lemma 9, the discretization then ensures finite-time convergence. Specifically, by construction, each is fully characterized by the grid points it contains. Since the sequence is decreasing, whenever , at least one grid point must have been removed from the latter. Let be the number of grid points inside . Across the value sets, at most grid points can be removed, so reaches a fixed point within iterations. When and are fixed, is a constant, so the iteration bound is .
-Optimality at Convergence
Let be the fixed point obtained via , i.e.,
By Lemma 9, , so the approximation retains all achievable values, including the optimal one.
Although may contain values outside , Lemma 10 shows that every value it contains is achievable approximately, in the sense defined below. Choose . The lemma gives a -feasible policy whose return is within of . Since is at least the reward of every exactly feasible policy, this policy is -optimal (Definition 1).
Definition 3 ((, )-achievability). is (, )-achievable from state if there exists a -feasible policy , with .
Lemma 10. If is bounded and , then for all every is (, )-achievable from .
The proof of Lemma 10 follows the same recursive construction as that of Lemma 7, allowing a bounded error at each expansion. The corresponding extension of Achieve (Algorithm 2), denoted Achieve, replaces Expand with the relaxed subroutine Expand shown in Algorithm 5.
Relaxed Value Expansion Compared with the exact implementation, Expand only requires to induce a value close to . This relaxation is essential because is a fixed point of , but need not be a fixed point of the original operator . In general, it can contain values outside .
Indeed, insisting on an exact Bellman expansion of such values may require onward vectors outside . Repeating this at subsequent steps can cause the targets to drift outward and become unbounded, preventing them from being realized as discounted returns.
The procedure Expand prevents this drift by keeping the onward vectors within while allowing a Bellman error of at most at each step. Such an expansion exists because . Due to geometric discounting, the total accumulated offset is bounded by .
Replacing Expand with Expand in Algorithm 3 yields a corresponding extension of ActProbs. The extension, call it ActProbs, computes the action distributions prescribed by a -feasible policy that achieves the target value within error . We omit the pseudocode for both ActProbs and Achieve.
Computation and Tractability
It remains to make these operations computationally efficient. As outlined at the end of Section 4, we need to:
compute applications of , so that we can obtain its fixed point using VSI; and
compute in Expand, so that ultimately we can execute an (, )-optimal policy using Achieve, or compute its action distributions using ActProbs.
We establish tractability by reducing both tasks to linear programming (LP).
Computing From the construction in Eq. (8), computing each reduces to determining, for each grid point , whether . We can restrict attention to grid points in because by Lemma 9 all relevant value sets are contained in . Thus, for fixed and , there is only a fixed number of grid points to check per state.
To efficiently decide whether , we show that can be characterized by linear constraints, so the decision problem reduces to an LP. Indeed, means that there exists some such that
Run VSI() to obtain a fixed point , where . If , report that no exactly feasible policy exists and stop.
Choose a target .
To execute a policy: Run to achieve within error while violating each subprocess constraint by at most .
To compute a policy: Run to compute of an -optimal policy .
Algorithm 6: VSI framework for solving S-CMDPs.
According to the definition of in Eq. (6), the membership is in turn equivalent to the existence of and satisfying the following constraints:
Hence, if and only if there exist , , and satisfying Eqs. (9) to (12).
These constraints are nonlinear in and : Eq. (10) contains products , while the pairs constrained by Eq. (12) depend on . To convert them into standard linear constraints, we first rewrite Eq. (12), for pairs with and , as
where is the polytope scaled by . If but , feasibility instead requires . For nonempty successor sets, each product is a convex combination of the scaled vertices. We introduce convex weights to eliminate and introduce auxiliary variables to linearize the products between and these weights.
More formally, we present the following lemma, establishing the tractability of .
Lemma 11. Suppose each is given as the convex hull of finitely many grid points. For any and , the feasibility of Eqs. (9) to (12) can be decided by solving an LP.
Computing For any , a valid output of can be obtained by solving Eqs. (9), (10) and (12) with and the given . The same linearization as above applies directly, so the tractability of follows.
Consequently, we establish Theorem 12 as a main algorithmic result. An overview of the VSI framework is given in Algorithm 6.
Theorem 12. For fixed , choosing allows us to compute a fixed point of in time polynomial in the input size, , and . If , there exists an -optimal policy whose action distribution can be computed in time polynomial in the same quantities and for any given history .
Input: State ; current value-set function in vertex representation Output: Vertex representation of
Solve an LP to find an arbitrary ;
if LP infeasible then return ;
Initialize as the set of vertices of the grid cell containing ;
repeat Compute the convex hull of ; for each facet of the hull do Let be the outward normal vector of the facet; Solve the MILP: , subject to ; \hfill // if MILP returns a grid point outside the current hull then ; break; until no new grid point is found
return .
Algorithm 7: An MILP-based practical algorithm for computing vertices of .
Implementation
To implement the VSI framework, we introduce one main practical adaptation: a mixed-integer linear programming (MILP)-based procedure for computing .
In the theoretical algorithm, each value set is obtained by exhaustively checking every grid point in the bounded value region. Although this approach suffices to establish tractability, it can be inefficient in practice because many grid points—particularly those in the interior of the polytope—are unnecessary for its vertex representation. Our implementation instead employs an iterative MILP-based separation procedure that searches directly for grid points that expand the current convex hull.
Vertex Computation via MILP Separation
By definition,
so computing amounts to computing the convex hull of the grid points contained in . Under a vertex representation,10 it suffices to identify a set of grid points whose convex hull equals .
To avoid exhaustively enumerating all candidate grid points, our implementation builds on the LP formulation from § 6.3. For vertex discovery, we use the same linear constraints that characterize membership in , but additionally restrict the candidate value to using integer grid indices and optimize a linear objective over the resulting feasible grid points. This yields an MILP that can search directly for grid points outside the current convex hull. The search procedure, presented in Algorithm 7, works as follows.
Initialization. First, find an arbitrary point by solving the LP from § 6.3 without the -neighborhood relaxation. (Effectively, solve Eqs. (10) to (12) for .) If the
LP is infeasible, then and hence , which we return. Otherwise, we use a grid cell containing as the initial polytope.
For every vertex of this cell, . Since , we therefore have
Hence, by the definition of , the entire initial cell is contained in . Using the cell ensures that the initial polytope is full-dimensional, so that the subsequent facet-enumeration procedure is well-defined.
Vertex discovery via facet separation. The algorithm then enumerates the facets of the current polytope. For each facet, it solves an MILP to optimality in the corresponding outward normal direction over all feasible grid points. The MILP uses the constraints from Eqs. (9) to (12), together with integer variables that restrict the candidate value to .
If the maximizing grid point lies strictly beyond the current facet, that point is added to the maintained point set, the convex hull and its facets are recomputed, and the procedure repeats.
If optimization over every facet direction produces no point outside the current polytope, the current polytope is returned as .
The algorithm terminates because is bounded and therefore contains only finitely many grid points, while every non-terminal iteration adds a feasible grid point lying outside the current convex hull. The returned polytope is correct because a point outside a full-dimensional polytope must violate at least one of its facet-defining inequalities. At termination, optimization in every outward facet direction certifies that no feasible grid point violates any such inequality. Hence, no feasible grid point lies outside the returned polytope, and the procedure recovers the convex hull of all feasible grid points without exhaustively enumerating them.
Code
Further details and a Python implementation of the VSI algorithm are available in the following GitHub repository: https://github.com/jrgan/VSI. Since can be computed independently for each state , the implementation supports parallel computation across states to improve efficiency.
Figure 2 to Figure 4 present results for an instance with 4 states and 5 actions. These results can be reproduced using the code provided in the repository.

Figure 2. Value sets from an example run. The horizontal and vertical axes show expected discounted reward and cost, respectively. In each plot, the dark inner polytope represents the final value set. The lighter outer polytopes represent intermediate value sets generated during the iterations. For this instance, VSI converges after 37 iterations.

Figure 4. Achievable value sets as the cost bound decreases, for the same instance as in Figure 2. The horizontal and vertical axes show expected discounted reward and cost, respectively. The cost bound in Figure 2 and Figure 3 is .

Figure 3. Trajectory of target values generated during the execution of an -optimal policy for the same instance as in Figure 2. The horizontal and vertical axes show expected discounted reward and cost, respectively. The red points mark the target values.
Conclusion
We introduced S-CMDPs, which strengthen classical CMDPs by requiring cost constraints to hold for every subprocess encountered during execution. Algorithmically, this seemingly small change fundamentally alters the problem: stationary policies can be suboptimal and are computationally intractable. We adapted the VSI framework to show that history-dependent policies are surprisingly tractable in this setting. Besides the theoretical results, we also provide a Python implementation based on MILP vertex computation; details can be found in § 7.
Two natural next steps are to consider multiple cost functions and move beyond the model-based setting. Although our algorithm extends to cost functions by enlarging the value space from to , the number of grid points grows exponentially in . Developing scalable approaches for such settings—potentially combining our structural insights with heuristic or RL-based methods—remains an interesting direction.
Omitted Proofs
Proofs in Section 3
Theorem 1. Fix any discount factor . There exist constants such that computing a stationary policy that is -optimal among stationary policies is NP-hard.
Proof. We reduce from the GAP 3-SAT problem. An instance is a 3CNF formula , promised to be either satisfiable (a yes-instance) or such that no Boolean assignment satisfies more than a fraction of its clauses (a no-instance). This problem is NP-hard for any constant [18].
Consider a GAP 3-SAT instance . Let be its Boolean variables and its clauses. Each clause is a disjunction of three literals, each of which is a variable or its negation .
We construct an S-CMDP instance in which every trajectory reaches an absorbing terminal state within four steps. The state space is . An example of the reduction is illustrated in Figure 5. In more detail:

Figure 5. Reduction from GAP 3-SAT. In this example, there are four variables in and . The states connected to are shown. The initial state , which transitions uniformly to the clause states, is omitted. Edge labels give the reward, which equals the cost in this reduction.
is an absorbing terminal state with zero reward and cost. Each state corresponds to the variable in the GAP 3-SAT instance; each state corresponds to the clause ; and each state corresponds to the -th literal in .
The initial state is . Irrespective of the action taken, it transitions to each clause state with probability , generating zero reward and cost.
All other transitions are deterministic:
There are four actions available at each : one leading to , and three others each leading to one of the literal states . All these transitions generate zero reward and zero cost; for all :
(The action leading to ensures that there is a feasible policy for every instance.)
At each literal state , the only available action leads to the corresponding variable state . Its reward and cost depend on the sign of the literal:
At each variable state , there are two actions available; call them and . Both actions lead to , generating the following reward and cost:
and
Hence, the reward and cost are equal for every state-action pair in the S-CMDP instance.
Finally, we set the thresholds in the constraints as follows.
All onward costs are at most 2, so only the positive literal states have nontrivial constraints.
The construction has polynomial size. State-dependent action sets can be replaced by a common action set by duplicating available actions.
Fix , choose , and set . We establish the following two claims:
Completeness: If the GAP 3-SAT instance is a yes-instance, then there exists a feasible stationary policy with .
Soundness: If it is a no-instance, then for every -feasible stationary policy .
Taking then leaves a strict gap between the value guaranteed in a yes-instance and the upper bound in a no-instance. Note that it is essential that, in the completeness condition, the yes-instance corresponds to a policy that satisfies the constraints exactly because of the resource augmentation in the approximation criterion considered (Definition 1).
Proof of Completeness Suppose that is a yes-instance, so there exists a satisfying assignment . Consider the following stationary policy . We show that .
At each variable state , choose if , and otherwise.
At each clause state , choose with probability 1 an action leading to a literal that is true under . Such a literal exists because satisfies .
If the chosen literal is positive, its immediate reward and cost are , and the next action is , with zero reward and cost. If the chosen literal is negative, its immediate reward and cost are zero, and the next action is , with reward and cost 1. Thus, in both cases the onward reward and cost at the literal state equal . All constraints are satisfied, each clause state has reward value , and .
Proof of Soundness Suppose that is a no-instance, and let be any -feasible stationary policy. Write
At a reachable positive literal corresponding to , the onward cost is . Since its threshold is , -feasibility requires . Thus, a positive literal with cannot be reached under .
Let and let contain the remaining variables. We bound the reward at each clause state by considering three cases:
Case 1: contains a positive literal with . Selecting such a literal gives reward at . Any selectable positive literal satisfies the same bound, and any negative literal gives at most . Thus .
Case 2: Case 1 does not apply, but contains a negative literal with . All positive literals in the clause are unreachable under , and selecting any negative literal gives reward at . Hence .
Case 3: Neither of the above cases applies. Every positive literal has its variable in and is therefore unreachable, while every negative literal has its variable in and gives reward at most at . The terminal action gives zero reward, so .
Assigning true to the variables in and false to those in satisfies every clause in Cases 1 and 2. Since is a no-instance, these cases cover at most a fraction of the clauses. Their reward values are at most , while the remaining clause values are at most . Accounting for the initial transition from , we obtain
In a yes-instance, any -optimal stationary policy has value at least . In a no-instance, every -feasible stationary policy has value at most . Since , computing such a policy would distinguish the two cases, proving the claimed hardness. Since all nonzero rewards and costs occur within four steps, the result also holds for a finite horizon. □
Proofs in Section 5
Lemma 2. For any and , we have if and only if and there exist a distribution and a vector for each such that Eqs. (3) and (4) hold.
Proof. The “only if” direction follows directly from the Bellman equation and the subprocess feasibility requirement.
For the “if” direction, suppose and there exist and satisfying the stated conditions. By Eq. (4), for each pair with , there exists a feasible policy that achieves the onward vector from state . We construct a policy by concatenating and these policies: selects its initial action at according to , and thereafter follows once action is taken and state is reached. Its action distribution on unreachable histories can be chosen arbitrarily. Since and each is feasible, the resulting policy satisfies the subprocess constraints. Applying the Bellman equation then yields . Hence is achievable: . □
Lemma 4 (Monotonicity). If , then .
Proof. It is immediate from the definition that is monotone. Hence, if , then we have . According to the definition of , enlarging the feasible set can only enlarge the resulting value set. Therefore, for all . □
Lemma 5. and .
Proof. The inclusion follows from the boundedness of discounted returns. Since rewards and costs are assumed to lie in , the discounted cumulative return of any policy is bounded in magnitude by the geometric sum . Hence every achievable value vector lies in .
For the second inclusion, consider any . By definition of , is obtained from an immediate payoff of magnitude at most together with an onward value bounded by . Therefore
which implies . Hence . □
Lemma 6. for all .
Proof. We first prove the base case .
Since (Lemma 5), monotonicity of implies
Recall that (Corollary 3). Moreover, by definition of the sequence , we have and . Combining these results establishes
Together with (Lemma 5), this yields the base case .
Now suppose that holds for some . Applying to the inclusions and using monotonicity gives
By definition of the sequence and the fact that , this becomes .
By induction, the stated result then follows. □
Lemma 7. If is bounded and , then .
Proof. Suppose is bounded and . Fix and . We construct a policy and show that it is feasible and satisfies .
Recursive Policy Construction For a history , let denote its last state. We define the policy and targets recursively over reachable histories:
At the initial history , assign the target .
At each reachable history with target , choose such that
Such a pair exists because . Set
For every pair with , assign to the reachable extension the target
Crucially, the onward condition imposed on ensures that , so the construction can continue at .
For completeness, for all unreachable histories , we assign an arbitrary action distribution to . Exact Realization Let denote the true onward value of conditional on . Its Bellman expansion and the exact decomposition of use the same immediate reward and cost terms. Subtracting them and using the successor targets gives
where is the next history obtained from under and , and the inequality follows from the triangle inequality. Since is bounded, let bound the norms of its vectors. Every target then has norm at most , while every true onward value has norm at most . Iterating the inequality for steps therefore yields
Letting gives at every reachable history. In particular, .
Feasibility At every reachable history , we have , so . Since , the policy is feasible. Thus , proving .
Theorem 8. as .
Proof. Let for every . By Lemma 6, we already have . Thus, by Lemma 7, it suffices to show that is a fixed point of . We prove the two inclusions separately.
The Inclusion We construct a Bellman decomposition in by taking a limit of decompositions in the iterates. Fix an arbitrary state and vector . By definition, for all . Since , we also have . According to the definition of , for each , there exists such that
Choose whenever ; this does not affect the Bellman expansion. All onward vectors then lie in . Consider the sequence . Since both components are bounded, by the Bolzano–Weierstrass theorem, this sequence admits a convergent subsequence . Let be the limit of this subsequence.
The key is to show that the limiting onward vectors for positive-probability pairs remain in every iterate, and hence in their intersection.
Claim 1. .
Proof. According to the definition of in Eq. (7), we need to show that:
; and
for all and such that .
For (i), note that is closed and each . Since is their limit, it follows that .
For (ii), fix and such that . Let be arbitrary. Since and , there exists such that and for all . Because we have
for all .
To pass to the limit, we use the fact that preserves closedness of bounded closed value sets. Indeed, all onward vectors can be restricted to a closed ball containing the input sets. The onward constraints remain valid under limits: any action–state pair with positive limiting probability has positive probability for all sufficiently large indices, so its onward vectors lie in the corresponding closed input set, which also contains their limit. Together with the closed cost constraint, this makes the feasible decompositions a compact set. Its continuous Bellman image is compact and hence closed. Since is closed and all iterates are bounded, induction shows that every is closed.
Taking limits therefore gives . Since is arbitrary, we conclude that . □
We can now pass to the limit in the Bellman expansion. Since for all , and is continuous, taking limits along the subsequence yields . Moreover, since . Together with Claim 1, this implies . Because the choice of and is arbitrary, we conclude that
The Reverse Inclusion Since for every , monotonicity gives . Taking intersections yields, for every ,
where dropping does not change the intersection because the iterates are nested. Therefore, . By Lemma 7, , and the reverse inclusion from Lemma 6 gives . □
Proofs in Section 6
Lemma 9. for all .
Proof. Let denote the radius of . By definition,
and .
We first establish (i) , and (ii) . Indeed, condition (i) is immediate, since
To verify (ii), fix any and . Since the immediate return is bounded in norm by 1 and every onward value in has norm at most , we get that
where the strict inequality follows from .
Now consider any
There exists such that , and hence . Since , is a multiple of . As is also a multiple of , it follows that
Thus every such grid point belongs to . Since is convex, by the definition of , we get that
Since was arbitrary, condition (ii) follows.
Finally, observe that for any value-set function , we have
Indeed, fix any and consider a grid cell containing . Every vertex of this cell belongs to and satisfies , so
Since is a convex combination of the vertices of the cell, the definition of then implies ; therefore, .
Applying this to and using gives
Together with the monotonicity of , conditions (i) and (ii) give
Applying repeatedly and using then yields
for every .
Lemma 10. If is bounded and , then for all every is -achievable from .
Proof. Suppose is bounded and . Fix and . We construct a policy and show that it is -feasible and satisfies . The construction uses a relaxed version of Achieve (Algorithm 2), allowing a Bellman error of at most at each step.
Recursive Policy Construction We first note that, for every ,
Indeed, has convex values, so is convex by mixing Bellman decompositions. Its -neighborhood is therefore convex and contains the convex hull of its grid points. Using now gives
For a history , let denote its last state. We define the policy and targets recursively over reachable histories:
At the initial history , assign the target .
At each reachable history with target , choose such that
and set
Such a choice exists because the inclusion above ensures that some vector in lies within distance of . By the definition of , that vector admits a Bellman decomposition using a pair in , which satisfies Eq. (13).
For every pair with , assign to the reachable extension the target
The membership follows from the onward condition; it ensures that the recursive construction can continue at .
Define arbitrarily on unreachable histories. The construction uses precisely the relaxed expansion in Algorithm 5, with in place of .
Approximation Error For each reachable history , write . By Eq. (13),
Let denote the true onward value of conditional on . Define the onward-value function by
for each reachable extension , assigning arbitrary values on zero-probability pairs. The Bellman equation then gives
Both expressions use the same immediate reward and cost terms. Subtracting them and using the successor targets gives
where is the next history obtained from under and . Taking the norm and applying the triangle inequality and Eq. (14) gives
Here, the expectation is a weighted average over all histories reachable from in one step, so it is bounded by the maximum over those histories. Since is bounded, let bound the norms of its vectors. Every target then has norm at most , while every true onward value has norm at most . Iterating this inequality for steps therefore yields
Letting gives
Applying this at gives .
Feasibility Every target lies within distance of , whose vectors satisfy the cost threshold at . Hence
Together with Eq. (15), this yields, at every reachable history ,
where the final inequality follows from . Thus is -feasible and is -achievable from .
Lemma 11. Suppose each is given as the convex hull of finitely many grid points. For any and , the feasibility of Eqs. (9) to (12) can be decided by solving an LP.
Proof. The constraints involve two difficulties. First, (10) involves quadratic terms of the form . Second, the index selection condition in (12) depends on the variable . We show that both issues can be eliminated to obtain an equivalent formulation with only linear constraints.
Removing the Index Condition Observe that (12) is equivalent to imposing the following conditions for every and , where we write :
The first constraint holds automatically if ; and if , it reduces to . Thus the dependence of the index condition on is removed.
Linearizing Quadratic Terms Let be the finite set of grid points representing , so that . We introduce convex-weight variables only for pairs with and ; empty successor sets with positive transition probability are handled by the zero-action-probability condition above. Then any can be written as a convex combination
where satisfies
Namely, is the convex hull of the grid points scaled by .
Substituting this representation of into (10) and the reformulation of (12) above, we convert the quadratic terms to . To eliminate these terms, introduce auxiliary variables
Since , the variables satisfy the following constraints:
We replace (17) with them.
This substitution replaces every product with a linear variable. The resulting constraints are linear in and the auxiliary variables .
Equivalence of the Reformulation The reformulation is trivially equivalent before introducing . To see that it remains equivalent after we replace with , observe that if satisfies the original formulation, then with satisfies the reformulated constraints.
Conversely, given feasible , define, for each pair with and ,
Then satisfies the original formulation. In particular, in the case where , Eq. (18) implies that ; hence, any arbitrary gives .
The Full LP Reformulation In summary, the full LP reformulation is as follows. The variables are:
;
for each ; and
for each , , and .
For uniform notation, we retain the variables for pairs with ; they are unconstrained and contribute nothing to the Bellman expression. The constraints are:
Eqs. (9) and (11): , and .
The linearized form of Eq. (10), as follows:
The linearized form of Eq. (12), for each and such that :
If , then for all and ;
If , then .
Finally, so that is a valid distribution.
Any feasible yields a feasible solution of the original constraints by setting
This completes the proof.
Theorem 12. For fixed , choosing allows us to compute a fixed point of in time polynomial in the input size, , and . If , there exists an -optimal policy whose action distribution can be computed in time polynomial in the same quantities and for any given history .
Proof. Let . Each application of requires at most LP feasibility checks: for each state and grid point , we test whether
:::#?
using Lemma 11. The resulting sets can be represented by all accepted grid points, so each LP has polynomial size in the input and . By Lemma 9, the sequence is decreasing, and every strict change removes at least one grid point from a state value set. Thus the procedure reaches a fixed point within iterations. With and fixed , is polynomial in and , establishing the first claim.
If , then by Lemma 9, so no exactly feasible policy exists. Otherwise, select a target at the initial state by solving
Since is a convex polytope described as the convex hull of finitely many grid points (by construction of ), the above maximization reduces to a linear program over convex combination weights, and can therefore be solved in polynomial time.
By Lemma 10, the vector is -achievable from . Let be the policy constructed in the proof of Lemma 10, using a fixed deterministic rule for selecting a basic feasible LP solution at each expansion. Since , the reward component of is at least that of every exactly feasible policy. Hence is -optimal. We compute its action distributions using , which replaces in ActProbs (Algorithm 3) with (Algorithm 5).
The procedure takes as input and returns the action distribution prescribed at history . At each recursive step on a reachable history, the current target satisfies , so a valid output of can be found by solving an LP of polynomial size.
To bound the bit lengths through these recursive calls, write the target coordinates over a common denominator, using at most bits for each numerator and the denominator. The LP coefficient matrix is fixed by the instance and grid, and its right-hand side depends affinely on the target. By Cramer’s rule, the variables of a basic feasible solution in standard form can therefore be written over a common denominator using at most bits per numerator and denominator, where is polynomial in the input size and . This common denominator cancels when recovering by dividing a weighted sum of the -variables by . Since the grid coordinates are fixed, the next target also requires at most bits per numerator and common denominator, for a polynomial bound independent of the current target. Thus each expansion adds only polynomially many bits, so both target and LP solution bit lengths remain polynomial after at most expansions.
Using a fixed deterministic polynomial-time LP algorithm to select basic feasible solutions, the procedure performs at most one expansion per state in the input history and returns an arbitrary fixed distribution if the history is unreachable. Its total running time is thus polynomial in the stated quantities and .
This yields an -optimal policy whose action distribution can be computed in polynomial time for any given history .
References
- [1]Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22–31. PMLR, 2017.arxiv.org/abs/1705.10528
- [2]Eitan Altman. Constrained markov decision processes with total cost criteria: Lagrangian approach and dual linear program. Mathematical methods of operations research, 48(3): 387–417, 1998.DOI
- [3]Eitan Altman. Constrained Markov decision processes. Routledge, 2021.DOI
- [4]Sanae Amani, Christos Thrampoulidis, and Lin Yang. Safe reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 243–253. PMLR, 2021.arxiv.org/abs/2106.06239
- [5]Qinbo Bai, Vaneet Aggarwal, and Ather Gattami. Provably sample-efficient model-free algorithm for MDPs with peak constraints. Journal of Machine Learning Research, 24(60):1–25, 2023. URL http://jmlr.org/papers/v24/21-0117.html.
- [6]Eleni Batziou, John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Monotone contractions. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC ’25), page 507–517, 2025.arxiv.org/abs/2411.10107
- [7]Betsy Beyer, Chris Jones, Jennifer Petoff, and Niall Richard Murphy. Site Reliability Engineering: How Google Runs Production Systems. O’Reilly Media, 2016.
- [8]Betsy Beyer, Niall Richard Murphy, David K. Rensin, Kent Kawahara, and Stephen Thorne. The Site Reliability Workbook: Practical Ways to Implement SRE. O’Reilly Media, 2018.
- [9]Xi Chen and Yuhao Li. Improved upper bounds for finding tarski fixed points. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC ’22), pages 1108–1118, 2022.arxiv.org/abs/2202.05913
- [12]John Fearnley, Dömötör Pálvölgyi, and Rahul Savani. A faster algorithm for finding tarski fixed points. ACM Transactions on Algorithms (TALG), 18(3):1–23, 2022.
- [13]Jaime F. Fisac, Andrea Bajcsy, Sylvia L. Herbert, David Fridovich-Keil, Steven Wang, Claire J. Tomlin, and Anca D. Dragan. Probabilistically safe robot planning with confidence-based human predictions. In Robotics: Science and Systems, 2018.
- [14]Jiarui Gan and Rupak Majumdar. Value-set iteration: Computing optimal correlated equilibria in infinite-horizon multi-player stochastic games, 2025. URL https://arxiv.org/abs/2506.07186.
- [15]Jiarui Gan, Rupak Majumdar, Debmalya Mandal, and Goran Radanovic. Sequential principal-agent problems with communication: Efficient computation and learning, 2023. URL https://arxiv.org/abs/2306.03832v2.
- [16]Javier Garcia and Fernando Fernández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1437–1480, 2015.DOI
- [17]Shangding Gu, Long Yang, Yali Du, Guang Chen, Florian Walter, Jun Wang, and Alois Knoll. A review of safe reinforcement learning: Methods, theories and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
- [18]Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–859, 2001.
- [19]Mitri Kitti. Subgame perfect equilibria in discounted stochastic games. Journal of Mathematical Analysis and Applications, 435(1):253–266, 2016.DOI
- [20]Jingqi Li, David Fridovich-Keil, Somayeh Sojoudi, and Claire J Tomlin. Augmented lagrangian method for instantaneously constrained reinforcement learning problems. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2982–2989. IEEE, 2021.
- [21]Jeremy McMahan and Xiaojin Zhu. Anytime-constrained reinforcement learning. In International conference on artificial intelligence and statistics, pages 4321–4329. PMLR, 2024.arxiv.org/abs/2311.05511
- [23]Ming Shi, Yingbin Liang, and Ness Shroff. A near-optimal algorithm for safe reinforcement learning under instantaneous hard constraints. In International Conference on Machine Learning, pages 31243–31268. PMLR, 2023.arxiv.org/abs/2302.04375
- [24]Yifan Sun, Feihan Li, Weiye Zhao, Rui Chen, Tianhao Wei, and Changliu Liu. Learn with imagination: Safe set guided state-wise constrained policy optimization. In Necmiye Ozay, Laura Balzano, Dimitra Panagou, and Alessandro Abate, editors, Proceedings of the 7th Annual Learning for Dynamics & Control Conference, volume 283 of Proceedings of Machine Learning Research, pages 298–309. PMLR, 04–06 Jun 2025. URL https://proceedings.mlr.press/v283/sun25a.html.
- [25]Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285—309, 1955.DOI
- [26]Honghao Wei, Xin Liu, and Lei Ying. Safe reinforcement learning with instantaneous constraints: the role of aggressive exploration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 21708–21716, 2024.arxiv.org/abs/2312.14470
- [27]Weiye Zhao, Rui Chen, Yifan Sun, Feihan Li, Tianhao Wei, and Changliu Liu. State-wise constrained policy optimization. Transactions on Machine Learning Research, 2024.arxiv.org/abs/2306.12594
- [28]Hai Zhu and Javier Alonso-Mora. Chance-constrained collision avoidance for mavs in dynamic environments. IEEE Robotics and Automation Letters, 4(2):776–783, 2019.DOI
