betaFeedback

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 tt 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 tt” 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 (ϵ,δ)(\epsilon,\delta)-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 (S,A,s0,p,r,c,θ,γ)(S, A, s_0, p, r, c, \theta, \gamma). The components other than cc and θ\theta define a standard discounted MDP: SS is a finite state space, with initial state s0∈Ss_0 \in S; AA is a finite action space; p:S×A→Δ(S)p : S \times A \to\Delta(S) is the transition kernel; r:S×A→Rr : S \times A \to\mathbb{R} is the reward function; and γ∈(0,1)\gamma\in(0, 1) is the discount factor. The additional components cc and θ\theta specify a cost function c:S×A→Rc : S \times A \to\mathbb{R} and a state-wise threshold θ(s)∈R\theta(s) \in\mathbb{R} for each s∈Ss \in S. Without loss of generality, we assume that rewards and costs lie in [−1,1][-1, 1].

Let a policy π\pi assign an action distribution π(h)∈Δ(A)\pi(h) \in\Delta(A) to each finite history h=h = (s0,a0,…,st)(s_0, a_0, \ldots, s_t). For a reachable history hh, we define the onward reward value as

Vrπ(h)=Eπ[∑t′=t∞γt′−t⋅r(st′,at′)∣h]V_r^\pi(h) = \mathbb{E}_\pi\left[\sum_{t'=t}^{\infty} \gamma^{t'-t} \cdot r(s_{t'},a_{t'}) \mid h\right]

where Eπ[⋅∣h]\mathbb{E}_\pi[\cdot\mid h] denotes expectation conditional on hh under π\pi, and Pπ(h)\mathbb{P}_\pi(h) denotes the probability of observing hh. Similarly, Vcπ(h)V_c^\pi(h) denotes the onward discounted cost, defined by replacing rr with cc.

Our objective is to maximize expected discounted reward while bounding the onward discounted cost after every reachable history:

max⁡πVrπ(s0)(1)\max_\pi\quad V_r^\pi(s_0) \tag*{(1)}
s.t.Vcπ(h)≤θ(st)for all h=(s0,a0,…,st), t≥0: Pπ(h)>0(2)\text{s.t.}\quad V_c^\pi(h) \le\theta(s_t) \qquad\text{for all } h=(s_0,a_0,\ldots,s_t),\ t\ge0:\ \mathbb{P}_\pi(h)>0 \tag*{(2)}

The formulation imposes a constraint on every subprocess starting from a reachable history hh.

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 s1s_1 or s2s_2 with equal probability.1 There are two actions, aa and bb. All transitions are deterministic, as depicted in the figure, and are independent of the chosen action. All rewards and costs are zero except for r(s3,b)=c(s3,b)=1r(s_3,b)=c(s_3,b)=1. The cost thresholds are θ(s1)=0\theta(s_1)=0 and θ(s2)=θ(s3)=1\theta(s_2)=\theta(s_3)=1.

The only way to obtain positive reward in this instance is to choose action bb at s3s_3, which also incurs cost 1. Under any stationary policy, however, choosing bb at s3s_3 with positive probability would violate the subprocess constraint at s1s_1, where the onward cost must not exceed θ(s1)=0\theta(s_1)=0. Hence, every feasible stationary policy must choose action aa at s3s_3 with probability 1, yielding value zero.2

In contrast, history dependence allows the agent to condition its action at s3s_3 on the preceding state: choose aa if the trajectory starts from s1s_1, and choose bb if it starts from s2s_2. This satisfies all subprocess constraints and yields expected value γ/2\gamma/2, 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 ((ϵ,δ\epsilon,\delta)-optimal policy). A policy π\pi is (ϵ,δ)(\epsilon,\delta)-optimal if the following conditions hold:

  1. δ\delta-feasibility: π\pi violates every subprocess constraint in Eq. (2) by at most δ\delta.

  1. ϵ\epsilon-optimality: Vrπ(s0)≥Vrπ′(s0)−ϵV_r^\pi(s_0) \ge V_r^{\pi'}(s_0) - \epsilon for every policy π′\pi' 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 π′\pi' used for comparison are stationary.

Theorem 1. Fix any discount factor γ∈(0,1)\gamma\in(0,1). There exist constants ϵ,δ>0\epsilon,\delta> 0 such that computing a stationary policy that is (ϵ,δ)(\epsilon,\delta)-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 hh, can we efficiently compute the action distribution of a near-optimal policy at hh? 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 x:S×A→R2\mathbf{x}: S \times A \to\mathbb{R}^2 such that

x(s,a):=(r(s,a),c(s,a))\mathbf{x}(s,a) := (r(s,a),c(s,a))

for every (s,a)∈S×A(s,a) \in S \times A. Similarly, for any policy π\pi and history hh, we write V⃗π(h)=(Vrπ(h),Vcπ(h))\vec{V}^{\pi}(h) = (V_r^{\pi}(h),V_c^{\pi}(h)) for the vector of onward discounted reward and cost.

Definition 2 (Achievable value set). The achievable value set of a state ss, denoted V⋆(s)V^\star(s), is the set of all vectors v∈R2\mathbf{v} \in\mathbb{R}^2 that can be achieved by some feasible policy π\pi when starting from ss, i.e., v=V⃗π(s)\mathbf{v} = \vec{V}^{\pi}(s) for some π\pi satisfying (2).

We call functions like V⋆V^\star, that map each state to a subset of R2\mathbb{R}^2, value-set functions.

Using V⋆V^\star, we can express the optimal objective value in Eqs. (1) and (2) as the maximum reward component over the achievable set at s0s_0:

max⁡v=(v1,v2)∈V⋆(s0)v1.\max_{\mathbf{v}=(v_1,v_2)\in V^\star(s_0)} v_1.

If V⋆V^\star 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 v∈V⋆(s)\mathbf{v} \in V^\star(s) into a feasible policy π\pi with V⃗π(s)=v\vec{V}^{\pi}(s)=\mathbf{v}. We will return to the computation of V⋆V^\star and address the remaining algorithmic challenges in the following sections.

Unrolling Policies Based on Achievable Sets

Consider an arbitrary state ss and a target value vector v=(v1,v2)∈V⋆(s)\mathbf{v} = (v_1, v_2) \in\mathcal{V}^{\star}(s). By definition, some feasible policy π\pi achieves v\mathbf{v}, so a Bellman-style expansion gives

v=Ea∼πˉ(x(s,a)+γEs′∼p(⋅∣s,a)w(a,s′)).(3)\mathbf{v} = \mathbb{E}_{a \sim\bar{\pi}}\left(\mathbf{x}(s,a) + \gamma\mathbb{E}_{s' \sim p(\cdot\mid s,a)}\mathbf{w}(a,s')\right). \tag*{(3)}

Here πˉ=π(s)∈Δ(A)\bar{\pi} = \pi(s) \in\Delta(\mathcal{A}) is the action distribution at state ss; and for each pair (a,s′)(a,s'), w(a,s′)=V⃗π(s,a,s′)\mathbf{w}(a,s') = \vec{V}^{\pi}(s,a,s') is the onward value, given history (s,a,s′)(s,a,s').

Crucially, the fact that each onward value w(a,s′)\mathbf{w}(a,s') is achieved in the subsequent process means that:

w(a,s′)∈V⋆(s′) for all a,s′:πˉ(a)⋅p(s′∣s,a)>0,(4)\mathbf{w}(a,s') \in\mathcal{V}^{\star}(s') \text{ for all } a,s' : \bar{\pi}(a) \cdot p(s' \mid s,a) > 0, \tag*{(4)}

where only the (s,a,s′)(s,a,s') triples with positive probability under πˉ\bar{\pi} and the transition function pp 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 v∈V⋆(s)\mathbf{v} \in\mathcal{V}^{\star}(s) into an action distribution πˉ\bar{\pi} and a collection w\mathbf{w} of onward values based on Eqs. (3) and (4). It samples an action aa from πˉ\bar{\pi} and observes the next state s′s'. The onward value w(a,s′)\mathbf{w}(a,s') 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 v∈V⋆(s)\mathbf{v} \in\mathcal{V}^{\star}(s), there always exists a valid decomposition into πˉ\bar{\pi} and w\mathbf{w}. 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 ss, the target value lies in V⋆(s)\mathcal{V}^{\star}(s), so the procedure can continue indefinitely.

We can verify that the recursive procedure has expected discounted reward and cost exactly equal to v\mathbf{v}. Effectively, the procedure implements a policy that achieves v\mathbf{v} (i.e., V⃗π(s)=v\vec{V}^{\pi}(s) = \mathbf{v}).

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 π(h)\pi(h) for any history hh starting at s0s_0 and any target v∈V⋆(s0)\mathbf{v} \in\mathcal{V}^{\star}(s_0), where π\pi is a policy that achieves v\mathbf{v}. 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 hh. On reachable histories, its recursive calls return the action distribution induced by Achieve(v,s0\mathbf{v},s_0) conditional on hh.

Let π\pi be the policy computed by ActProbs(v,⋅\mathbf{v},\cdot), i.e., π(h):=ActProbs(v,h)\pi(h):=\texttt{ActProbs}(\mathbf{v},h) for every history hh starting at s0s_0. It can be verified that π\pi is feasible and V⃗π(s0)=v\vec{V}^{\pi}(s_0)=\mathbf{v}. Hence, choosing v∗∈arg max⁡v∈V⋆(s0)v1\mathbf{v}^{*}\in\operatorname*{arg\,max}_{\mathbf{v}\in\mathcal{V}^{\star}(s_0)}v_1 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:

  1. computing V⋆\mathcal{V}^{\star}, and

  1. computing πˉ\bar{\pi} and w\mathbf{w} that satisfy Eqs. (3) and (4).

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.

V⋆\mathcal{V}^{\star} as a Fixed Point

To begin, let us characterize V⋆\mathcal{V}^{\star} as a fixed point. Recall from Eqs. (3) and (4) that every v∈V⋆(s)\mathbf{v}\in\mathcal{V}^{\star}(s) admits a Bellman-style decomposition. In our S-CMDP model, there is one additional necessary condition: at state ss, the cost component of every achievable vector v\mathbf{v} must not exceed the state-wise threshold:

v2≤θ(s).(5)v_2\leq\theta(s). \tag*{(5)}

This condition is not just necessary: together with Eqs. (3) and (4), it is sufficient for the achievability of v\mathbf{v}, as the following lemma states.

Lemma 2. For any s∈Ss\in S and v=(v1,v2)∈R2\mathbf{v}=(v_1,v_2)\in\mathbb{R}^2, we have v∈V⋆(s)\mathbf{v}\in\mathcal{V}^{\star}(s) if and only if v2≤θ(s)v_2\leq\theta(s) and there exist a distribution πˉ∈Δ(A)\bar{\pi}\in\Delta(A) and a vector w(a,s′)∈R2\mathbf{w}(a,s')\in\mathbb{R}^2 for each (a,s′)∈A×S(a,s')\in A\times S such that Eqs. (3) and (4) hold.

Lemma 2 characterizes V⋆\mathcal{V}^{\star} as a fixed point of the following operator Φ\Phi on value-set functions. For any s∈Ss\in S,

Φ(V)(s):={v∈R2v=Bellman⁡(s,πˉ,w),(πˉ,w)∈Onward⁡(s,V),v2≤θ(s)}.(6)\Phi(\mathcal{V})(s):=\left\{\begin{array}{c|l} \mathbf{v}\in\mathbb{R}^{2} & \mathbf{v}=\operatorname{Bellman}(s,\bar{\pi},\mathbf{w}),\\ &(\bar{\pi},\mathbf{w})\in\operatorname{Onward}(s,\mathcal{V}),\\ &v_2\leq\theta(s) \end{array}\right\}. \tag*{(6)}

where we use the shorthand Bellman⁡(s,πˉ,w)\operatorname{Bellman}(s,\bar{\pi},\mathbf{w}) to represent the right-hand side of Eq. (3), and

Onward⁡(s,V):={(πˉ,w)|w(a,s′)∈V(s′) if πˉ(a)⋅p(s′∣s,a)>0}(7)\operatorname{Onward}(s,\mathcal{V}):=\left\{(\bar{\pi},\mathbf{w})\middle|\mathbf{w}(a,s')\in\mathcal{V}(s')\text{ if }\bar{\pi}(a)\cdot p(s'|s,a)>0\right\} \tag*{(7)}

consists of all (πˉ,w)(\bar{\pi},\mathbf{w}) pairs satisfying the onward achievability condition for every (a,s′)∈A×S(a,s')\in A\times S, with respect to V\mathcal{V} (i.e., Eq. (4) with V⋆\mathcal{V}^{\star} replaced by V\mathcal{V}).

Intuitively, Φ(V)(s)\Phi(\mathcal{V})(s) consists of values obtained by combining an action distribution with onward values from V\mathcal{V}, subject to the cost threshold at ss. Lemma 2 immediately yields the following corollary.

Corollary 3. V⋆\mathcal{V}^{\star} is a fixed point of Φ\Phi, i.e., V⋆=Φ(V⋆)\mathcal{V}^{\star}=\Phi(\mathcal{V}^{\star}).

Convergence of Value-Set Iteration to V⋆V^\star

This suggests computing a fixed point of Φ\Phi to obtain V⋆V^\star. 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 Φ\Phi to a value-set function (Algorithm 4), in the hope that it converges to V⋆V^\star.

VSI(Φ\Phi, V\mathcal{V}):

  1. Repeat V←Φ(V)\mathcal{V} \leftarrow\Phi(\mathcal{V}) until V=Φ(V)\mathcal{V} = \Phi(\mathcal{V}).

  2. Return V\mathcal{V}.

Algorithm 4: VSI (value-set iteration).

This approach, however, requires more care. Unlike the classical Bellman operator, Φ\Phi 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 Φ\Phi 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 Φ\Phi becomes key to our convergence argument.

Lemma 4 (Monotonicity). If V⊆V′\mathcal{V} \subseteq\mathcal{V}', then Φ(V)⊆Φ(V′).\Phi(\mathcal{V}) \subseteq\Phi(\mathcal{V}').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, V⋆V^\star is precisely the greatest bounded fixed point of Φ\Phi: it contains every bounded fixed point of Φ\Phi (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 V\mathcal{V} of V⋆V^\star that Φ\Phi maps into itself, i.e., Φ(V)⊆V\Phi(\mathcal{V}) \subseteq\mathcal{V}, we obtain a decreasing sequence of value-set functions. Indeed, since all rewards and costs lie in [−1,1][-1,1], the L∞L_\infty ball

B:={v∈R2∣∥v∥∞≤11−γ}\mathcal{B} := \left\{v \in\mathbb{R}^{2} \mid\lVert v \rVert_\infty\le\frac{1}{1-\gamma}\right\}

provides such an upper bound, as the following lemma states.

Lemma 5. V⋆⊆BV^\star\subseteq\mathcal{B} and Φ(B)⊆B.\Phi(\mathcal{B}) \subseteq\mathcal{B}.8

We show that the iterates of VSI(Φ,B\Phi,\mathcal{B}) converge to V⋆V^\star. Let (Vk)k≥0(\mathcal{V}^{k})_{k\geq0} be the sequence it generates:

  • V0=B\mathcal{V}^{0} = \mathcal{B}, and

  • Vk+1=Φ(Vk)\mathcal{V}^{k+1} = \Phi(\mathcal{V}^{k}) for all k≥0k \geq0.

By Lemma 5, V⋆⊆BV^\star\subseteq\mathcal{B}, so monotonicity of Φ\Phi gives Φ(V⋆)⊆Φ(B)\Phi(V^\star) \subseteq\Phi(\mathcal{B}). Since V⋆=Φ(V⋆)V^\star= \Phi(V^\star) and Φ(B)⊆B\Phi(\mathcal{B}) \subseteq\mathcal{B}, we obtain

V⋆⊆Φ(B)⊆B.V^\star\subseteq\Phi(\mathcal{B}) \subseteq\mathcal{B}.

Recall that V0=B\mathcal{V}^{0}=\mathcal{B} and V1=Φ(V0)\mathcal{V}^{1}=\Phi(\mathcal{V}^{0}), so this becomes

V⋆⊆V1⊆V0.\mathcal{V}^{\star}\subseteq\mathcal{V}^{1}\subseteq\mathcal{V}^{0}.

By monotonicity, repeatedly applying Φ\Phi to these inclusions propagates the nesting to all kk, yielding the following result.

Lemma 6. V⋆⊆Vk+1⊆Vk\mathcal{V}^{\star}\subseteq\mathcal{V}^{k+1}\subseteq\mathcal{V}^{k} for all k≥0k\geq0.

Consequently, (Vk)k≥0(\mathcal{V}^{k})_{k\geq0} is a decreasing sequence bounded below by V⋆\mathcal{V}^{\star}. Each Vk(s)\mathcal{V}^{k}(s) is compact, and a compactness argument shows that the intersection of these iterates is a fixed point of Φ\Phi (see the proof of Theorem 8). This fixed point must equal V⋆\mathcal{V}^{\star}, which bounds it not only from below but also, by the following lemma, from above.

Lemma 7. If V\mathcal{V} is bounded and V=Φ(V)\mathcal{V}=\Phi(\mathcal{V}), then V⊆V⋆\mathcal{V}\subseteq\mathcal{V}^{\star}.

The proof of Lemma 7 follows the recursive construction in § 4, where we showed that every v∈V⋆(s)\mathbf{v}\in\mathcal{V}^{\star}(s) can be achieved by the Achieve procedure (Algorithm 2). Here, we show more generally that for any bounded fixed point V\mathcal{V} of Φ\Phi, every v∈V(s)\mathbf{v}\in\mathcal{V}(s) can be achieved by the same procedure, with V\mathcal{V} in place of V⋆\mathcal{V}^{\star} in the onward value constraint in Eq. (4). This modified procedure is well defined because V=Φ(V)\mathcal{V}=\Phi(\mathcal{V}) guarantees a valid decomposition at every recursive call. Consequently, every v∈V(s)\mathbf{v}\in\mathcal{V}(s) is realized as the expected discounted return of a feasible policy and is therefore achievable from ss.

These lemmas lead to the following convergence theorem.

Theorem 8. Vk→V⋆\mathcal{V}^{k}\to\mathcal{V}^{\star} as k→∞k\to\infty.9

Approximate VSI for Finite-Time Convergence

We have established the convergence of value-set iteration to V⋆\mathcal{V}^{\star}, 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 Φ\Phi to be computed efficiently.

As in practical implementations of value iteration, we adopt an approximation approach. Rather than computing V⋆\mathcal{V}^{\star} 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 (ϵ,δ)(\epsilon,\delta)-optimal policy (Definition 1).

Approximate Operator and Convergence

Starting from B\mathcal{B}, repeated applications of Φ\Phi 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 Φ\Phi. To control the representation complexity, we discretize the two-dimensional value space using a grid and approximate Φ\Phi based on this discretization.

Illustration of approximate operator

Figure 1 (PDF p. 9). Illustration of Φ^\widehat{\Phi}.

Approximate Operator Choose a positive grid spacing ξ≤(1−γ)⋅min⁡{ϵ,δ/2}\xi\le(1-\gamma)\cdot\min\{\epsilon,\delta/2\}. Let Gξ:={ξx∣x∈Z2}\mathcal{G}_{\xi}:=\{\xi x \mid x\in\mathbb{Z}^{2}\} be the set of grid points. For any X⊆R2X\subseteq\mathbb{R}^{2}, define

GridHull⁡ξ(X):=Conv⁡(X∩Gξ),\operatorname{GridHull}_{\xi}(X):=\operatorname{Conv}(X\cap\mathcal{G}_{\xi}),

where Conv⁡(⋅)\operatorname{Conv}(\cdot) denotes the convex hull. Define the approximate operator as

Φ^(V)(s):=GridHull⁡ξ(Neigh⁡ξ(Φ(V)(s))).(8)\widehat{\Phi}(\mathcal{V})(s):=\operatorname{GridHull}_{\xi}\left(\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s))\right). \tag*{(8)}

where Neigh⁡ξ(X)\operatorname{Neigh}_{\xi}(X) denotes the ξ\xi-neighborhood of XX, consisting of all points within L∞L_{\infty} distance ξ\xi of some point in XX.

Figure 1 illustrates this construction. Whenever Φ(V)(s)\Phi(\mathcal{V})(s) is convex, its ξ\xi-neighborhood is also convex, and we can verify that the following inclusions hold:

Figure 1.

Φ(V)(s)⊆Φ^(V)(s)⊆Neigh⁡ξ(Φ(V)(s)).\Phi(\mathcal{V})(s)\subseteq\widehat{\Phi}(\mathcal{V})(s)\subseteq\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s)).

Specifically, the left-hand inclusion holds even without convexity of Φ(V)(s)\Phi(\mathcal{V})(s): every point of Φ(V)(s)\Phi(\mathcal{V})(s) lies in a grid cell whose vertices are within L∞L_{\infty} distance ξ\xi of that point; the cell is contained entirely in Neigh⁡ξ(Φ(V)(s))\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s)) 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 Φ^\widehat{\Phi} remains monotone. To initialize VSI, let B^ξ\widehat{\mathcal{B}}_{\xi} denote the smallest grid-aligned L∞L_{\infty} ball that strictly contains B\mathcal{B}, i.e.,

B^ξ:={v∈R2∣∥v∥∞≤(⌊11−γ⌋ϵξ+1)⋅ξ}.\widehat{\mathcal{B}}_{\xi}:=\left\{\mathbf{v}\in\mathbb{R}^{2}\mid\|\mathbf{v}\|_{\infty}\le\left(\left\lfloor\frac{1}{1-\gamma}\right\rfloor\frac{\epsilon}{\xi}+1\right)\cdot\xi\right\}.

We run VSI⁡(Φ^,V^0)\operatorname{VSI}(\widehat{\Phi},\widehat{\mathcal{V}}^{0}) (Algorithm 4) with V^0=B^ξ\widehat{\mathcal{V}}^{0}=\widehat{\mathcal{B}}_{\xi}. This yields a sequence (V^k)k≥0(\widehat{\mathcal{V}}^{k})_{k\ge0} such that:

  • V^0=B^ξ\widehat{\mathcal{V}}^{0}=\widehat{\mathcal{B}}_{\xi}, and

  • V^k+1=Φ^(V^k)\widehat{\mathcal{V}}^{k+1}=\widehat{\Phi}(\widehat{\mathcal{V}}^{k}) for all k≥0k\ge0.

The strict outer rounding of V^0\widehat{\mathcal{V}}^{0} ensures Φ^(V^0)⊆V^0\widehat{\Phi}(\widehat{\mathcal{V}}^{0})\subseteq\widehat{\mathcal{V}}^{0}. Together with V⋆⊆B⊆V^0\mathcal{V}^{\star}\subseteq\mathcal{B}\subseteq\widehat{\mathcal{V}}^{0} and the monotonicity of Φ^\widehat{\Phi}, this makes (V^k)k(\widehat{\mathcal{V}}^{k})_{k} a decreasing sequence of nested value sets. We extend Lemma 6 to this sequence as follows.

Lemma 9. V⋆⊆V^k+1⊆V^k\mathcal{V}^{\star}\subseteq\widehat{\mathcal{V}}^{k+1}\subseteq\widehat{\mathcal{V}}^{k} for all k≥0k\ge0.

Given Lemma 9, the discretization then ensures finite-time convergence. Specifically, by construction, each V^k(s)\widehat{\mathcal{V}}^{k}(s) is fully characterized by the grid points it contains. Since the sequence is decreasing, whenever V^k+1≠V^k\widehat{\mathcal{V}}^{k+1}\ne\widehat{\mathcal{V}}^{k}, at least one grid point must have been removed from the latter. Let Nξ=∣Gξ∩B^ξ∣N_{\xi}=|\mathcal{G}_{\xi}\cap\widehat{\mathcal{B}}_{\xi}| be the number of grid points inside B^ξ\widehat{\mathcal{B}}_{\xi}. Across the ∣S∣|S| value sets, at most ∣S∣Nξ|S|N_{\xi} grid points can be removed, so VSI⁡(Φ^,V^0)\operatorname{VSI}(\widehat{\Phi},\widehat{\mathcal{V}}^{0}) reaches a fixed point within O(∣S∣Nξ)O(|S|N_{\xi}) iterations. When γ\gamma and ξ\xi are fixed, NξN_{\xi} is a constant, so the iteration bound is O(∣S∣)O(|S|).

(ϵ,δ)(\epsilon,\delta)-Optimality at Convergence

Let V^⋆\widehat{\mathcal{V}}^{\star} be the fixed point obtained via VSI⁡(Φ^,V^0)\operatorname{VSI}(\widehat{\Phi},\widehat{\mathcal{V}}^{0}), i.e.,

∃k≥0: V^⋆=V^k=V^k+1.\exists k\ge0:\ \widehat{\mathcal{V}}^{\star}=\widehat{\mathcal{V}}^{k}=\widehat{\mathcal{V}}^{k+1}.

By Lemma 9, V⋆⊆V^⋆\mathcal{V}^{\star}\subseteq\widehat{\mathcal{V}}^{\star}, so the approximation retains all achievable values, including the optimal one.

Although V^⋆\widehat{\mathcal{V}}^{\star} may contain values outside V⋆\mathcal{V}^{\star}, Lemma 10 shows that every value it contains is achievable approximately, in the sense defined below. Choose v⋆∈arg max⁡v∈V^⋆(s0)v1\mathbf{v}^{\star}\in\operatorname*{arg\,max}_{\mathbf{v}\in\widehat{\mathcal{V}}^{\star}(s_{0})}v^{1}. The lemma gives a δ\delta-feasible policy whose return is within ϵ\epsilon of v⋆\mathbf{v}^{\star}. Since v1⋆v^{\star}_{1} is at least the reward of every exactly feasible policy, this policy is (ϵ,δ)(\epsilon,\delta)-optimal (Definition 1).

Definition 3 ((ϵ\epsilon, δ\delta)-achievability). v∈R2\mathbf{v} \in\mathbb{R}^{2} is (ϵ\epsilon, δ\delta)-achievable from state ss if there exists a δ\delta-feasible policy π\pi, with ∥V⃗π(s)−v∥∞≤ϵ\lVert\vec{V}^{\pi}(s) - \mathbf{v} \rVert_{\infty} \leq\epsilon.

Lemma 10. If V\mathcal{V} is bounded and V=Φ^(V)\mathcal{V} = \widehat{\Phi}(\mathcal{V}), then for all s∈Ss \in S every v∈V(s)\mathbf{v} \in\mathcal{V}(s) is (ϵ\epsilon, δ\delta)-achievable from ss.

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ξ_{\xi}, replaces Expand with the relaxed subroutine Expandξ_{\xi} shown in Algorithm 5.

Relaxed Value Expansion Compared with the exact implementation, Expandξ_{\xi} only requires (πˉ,w)(\bar{\pi}, \mathbf{w}) to induce a value close to v\mathbf{v}. This relaxation is essential because V^⋆\widehat{\mathcal{V}}^{\star} is a fixed point of Φ^\widehat{\Phi}, but need not be a fixed point of the original operator Φ\Phi. In general, it can contain values outside Φ(V^⋆)\Phi(\widehat{\mathcal{V}}^{\star}).

Indeed, insisting on an exact Bellman expansion of such values may require onward vectors outside V^⋆\widehat{\mathcal{V}}^{\star}. 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ξ_{\xi} prevents this drift by keeping the onward vectors within V^⋆\widehat{\mathcal{V}}^{\star} while allowing a Bellman error of at most ξ\xi at each step. Such an expansion exists because V^⋆⊆Neigh⁡ξ(Φ^(V^⋆))\widehat{\mathcal{V}}^{\star} \subseteq\operatorname{Neigh}_{\xi}(\widehat{\Phi}(\widehat{\mathcal{V}}^{\star})). Due to geometric discounting, the total accumulated offset is bounded by ξ1−γ≤ϵ\frac{\xi}{1-\gamma} \leq\epsilon.

Replacing Expand with Expandξ_{\xi} in Algorithm 3 yields a corresponding extension of ActProbs. The extension, call it ActProbsξ_{\xi}, computes the action distributions prescribed by a δ\delta-feasible policy that achieves the target value within error ϵ\epsilon. We omit the pseudocode for both ActProbsξ_{\xi} and Achieveξ_{\xi}.

Computation and Tractability

It remains to make these operations computationally efficient. As outlined at the end of Section 4, we need to:

  1. compute applications of Φ^\widehat{\Phi}, so that we can obtain its fixed point using VSI; and

  1. compute (πˉ,w)(\bar{\pi}, \mathbf{w}) in Expandξ_{\xi}, so that ultimately we can execute an (ϵ\epsilon, δ\delta)-optimal policy using Achieveξ_{\xi}, or compute its action distributions using ActProbsξ_{\xi}.

We establish tractability by reducing both tasks to linear programming (LP).

Computing Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s) From the construction in Eq. (8), computing each Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s) reduces to determining, for each grid point g\mathbf{g}, whether g∈Neigh⁡ξ(Φ^(V)(s))\mathbf{g} \in\operatorname{Neigh}_{\xi}(\widehat{\Phi}(\mathcal{V})(s)). We can restrict attention to grid points in B^ξ\widehat{B}_{\xi} because by Lemma 9 all relevant value sets are contained in V^0=B^ξ\widehat{\mathcal{V}}^{0} = \widehat{B}_{\xi}. Thus, for fixed γ\gamma and ξ\xi, there is only a fixed number of grid points to check per state.

To efficiently decide whether g∈Neigh⁡ξ(Φ^(V)(s))\mathbf{g} \in\operatorname{Neigh}_{\xi}(\widehat{\Phi}(\mathcal{V})(s)), we show that Neigh⁡ξ(Φ^(V)(s))\operatorname{Neigh}_{\xi}(\widehat{\Phi}(\mathcal{V})(s)) can be characterized by linear constraints, so the decision problem reduces to an LP. Indeed, v∈Neigh⁡ξ(Φ^(V)(s))\mathbf{v} \in\operatorname{Neigh}_{\xi}(\widehat{\Phi}(\mathcal{V})(s)) means that there exists some v~∈Φ^(V)(s)\widetilde{\mathbf{v}} \in\widehat{\Phi}(\mathcal{V})(s) such that

∥v−v~∥∞≤ξ.(9)\lVert\mathbf{v} - \widetilde{\mathbf{v}} \rVert_{\infty} \leq\xi. \tag*{(9)}
  1. Run VSI(Φ^,V0\widehat{\Phi}, \mathcal{V}^{0}) to obtain a fixed point V^⋆\widehat{\mathcal{V}}^{\star}, where V^0=B^ξ\widehat{\mathcal{V}}^{0}=\widehat{\mathcal{B}}_{\xi}. If V^⋆(s0)=∅\widehat{\mathcal{V}}^{\star}(s_{0})=\varnothing, report that no exactly feasible policy exists and stop.

  1. Choose a target v⋆∈arg⁡max⁡v∈V^⋆(s0) v1\mathbf{v}^{\star}\in\underset{\mathbf{v}\in\widehat{\mathcal{V}}^{\star}(s_{0})}{\arg\max}\ v_{1}.

  1. To execute a policy: Run Achieve⁡ξ(v⋆,s0)\operatorname{Achieve}_{\xi}(\mathbf{v}^{\star},s_{0}) to achieve v⋆\mathbf{v}^{\star} within ϵ\epsilon error while violating each subprocess constraint by at most δ\delta.

To compute a policy: Run ActProbs⁡ξ(v⋆,h)\operatorname{ActProbs}_{\xi}(\mathbf{v}^{\star},h) to compute π(h)\pi(h) of an (ϵ,δ)(\epsilon,\delta)-optimal policy π\pi.

Algorithm 6: VSI framework for solving S-CMDPs.

According to the definition of Φ\Phi in Eq. (6), the membership v~∈Φ(V)(s)\widetilde{\mathbf{v}}\in\Phi(\mathcal{V})(s) is in turn equivalent to the existence of π‾∈Δ(A)\overline{\pi}\in\Delta(A) and w\mathbf{w} satisfying the following constraints:

v~=∑a∈Aπ‾(a)(x(s,a)+γ∑s′∈Sp(s′∣s,a)w(a,s′))(10)\widetilde{\mathbf{v}}=\sum_{a\in A}\overline{\pi}(a)\left(\mathbf{x}(s,a)+\gamma\sum_{s'\in S}p(s'\mid s,a)\mathbf{w}(a,s')\right) \tag*{(10)}
v~2≤θ(s),(11)\widetilde{v}_{2}\leq\theta(s), \tag*{(11)}
w(a,s′)∈V(s′)for all a,s′:π‾(a)⋅p(s′∣s,a)>0.(12)\mathbf{w}(a,s')\in\mathcal{V}(s')\qquad\text{for all }a,s':\overline{\pi}(a)\cdot p(s'\mid s,a)>0. \tag*{(12)}

Hence, v∈Neigh⁡ξ(Φ(V)(s))\mathbf{v}\in\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s)) if and only if there exist v~\widetilde{\mathbf{v}}, π‾∈Δ(A)\overline{\pi}\in\Delta(A), and w\mathbf{w} satisfying Eqs. (9) to (12).

These constraints are nonlinear in π‾\overline{\pi} and w\mathbf{w}: Eq. (10) contains products π‾(a)⋅w(a,s′)\overline{\pi}(a)\cdot\mathbf{w}(a,s'), while the pairs constrained by Eq. (12) depend on π‾(a)\overline{\pi}(a). To convert them into standard linear constraints, we first rewrite Eq. (12), for pairs with p(s′∣s,a)>0p(s'\mid s,a)>0 and V(s′)≠∅\mathcal{V}(s')\ne\varnothing, as

π‾(a)⋅w(a,s′)∈π‾(a)⋅V(s′),\overline{\pi}(a)\cdot\mathbf{w}(a,s')\in\overline{\pi}(a)\cdot\mathcal{V}(s'),

where π‾(a)⋅V(s′):={π‾(a)⋅v∣v∈V(s′)}\overline{\pi}(a)\cdot\mathcal{V}(s'):=\{\overline{\pi}(a)\cdot\mathbf{v}\mid\mathbf{v}\in\mathcal{V}(s')\} is the polytope V(s′)\mathcal{V}(s') scaled by π‾(a)\overline{\pi}(a). If p(s′∣s,a)>0p(s'\mid s,a)>0 but V(s′)=∅\mathcal{V}(s')=\varnothing, feasibility instead requires π‾(a)=0\overline{\pi}(a)=0. For nonempty successor sets, each product π‾(a)⋅w(a,s′)\overline{\pi}(a)\cdot\mathbf{w}(a,s') is a convex combination of the scaled vertices. We introduce convex weights to eliminate w(a,s′)\mathbf{w}(a,s') and introduce auxiliary variables to linearize the products between π‾(a)\overline{\pi}(a) and these weights.

More formally, we present the following lemma, establishing the tractability of Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s).

Lemma 11. Suppose each V(s′)\mathcal{V}(s') is given as the convex hull of finitely many grid points. For any ss and v\mathbf{v}, the feasibility of Eqs. (9) to (12) can be decided by solving an LP.

Computing Expand⁡ξ(v,s)\operatorname{Expand}_{\xi}(\mathbf{v},s) For any v∈V^⋆(s)\mathbf{v}\in\widehat{\mathcal{V}}^{\star}(s), a valid output of Expand⁡ξ(v,s)\operatorname{Expand}_{\xi}(\mathbf{v},s) can be obtained by solving Eqs. (9), (10) and (12) with V=V^⋆\mathcal{V}=\widehat{\mathcal{V}}^{\star} and the given v\mathbf{v}. The same linearization as above applies directly, so the tractability of Expand⁡ξ(v,s)\operatorname{Expand}_{\xi}(\mathbf{v},s) 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 γ∈(0,1)\gamma\in(0,1), choosing ξ=(1−γ)min⁡{ϵ,δ/2}\xi=(1-\gamma)\min\{\epsilon,\delta/2\} allows us to compute a fixed point V^⋆⊇V⋆\widehat{\mathcal{V}}^{\star}\supseteq\mathcal{V}^{\star} of Φ^\widehat{\Phi} in time polynomial in the input size, 1/ϵ1/\epsilon, and 1/δ1/\delta. If V^⋆(s0)≠∅\widehat{\mathcal{V}}^{\star}(s_{0})\ne\varnothing, there exists an (ϵ,δ)(\epsilon,\delta)-optimal policy π\pi whose action distribution π(h)\pi(h) can be computed in time polynomial in the same quantities and ∣h∣|h| for any given history hh.

Input: State s∈Ss \in S; current value-set function V\mathcal{V} in vertex representation Output: Vertex representation of Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s)

Solve an LP to find an arbitrary v∈Φ(V)(s)\mathbf{v} \in\Phi(\mathcal{V})(s);

if LP infeasible then return ∅\varnothing;

Initialize K\mathcal{K} as the set of vertices of the grid cell containing v\mathbf{v};

repeat Compute the convex hull of K\mathcal{K}; for each facet of the hull do Let n\mathbf{n} be the outward normal vector of the facet; Solve the MILP: max⁡g∈Gξn⋅g\max_{\mathbf{g}\in G_{\xi}} \mathbf{n}\cdot\mathbf{g}, subject to g∈Neigh⁡ξ(Φ(V)(s))\mathbf{g}\in\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s)); \hfill // Gξ={ξx∣x∈Z2}G_{\xi}=\{\xi\mathbf{x}\mid\mathbf{x}\in\mathbb{Z}^{2}\} if MILP returns a grid point g\mathbf{g} outside the current hull then K←K∪{g}\mathcal{K}\leftarrow\mathcal{K}\cup\{\mathbf{g}\}; break; until no new grid point is found

return K\mathcal{K}.

Algorithm 7: An MILP-based practical algorithm for computing vertices of Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s).

Implementation

To implement the VSI framework, we introduce one main practical adaptation: a mixed-integer linear programming (MILP)-based procedure for computing Φ^(V)\widehat{\Phi}(\mathcal{V}).

In the theoretical algorithm, each value set Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s) 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,

Φ^(V)(s)=GridHull⁡ξ(Neigh⁡ξ(Φ(V)(s))),\widehat{\Phi}(\mathcal{V})(s)=\operatorname{GridHull}_{\xi}\left(\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s))\right),

so computing Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s) amounts to computing the convex hull of the grid points contained in Neigh⁡ξ(Φ(V)(s))\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s)). Under a vertex representation,10 it suffices to identify a set of grid points whose convex hull equals Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s).

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 Neigh⁡ξ(Φ(V)(s))\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s)), but additionally restrict the candidate value to GξG_{\xi} 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.

  1. Initialization. First, find an arbitrary point v∈Φ(V)(s)\mathbf{v}\in\Phi(\mathcal{V})(s) by solving the LP from § 6.3 without the ξ\xi-neighborhood relaxation. (Effectively, solve Eqs. (10) to (12) for v~\tilde{\mathbf{v}}.) If the

LP is infeasible, then Φ(V)(s)=∅\Phi(\mathcal{V})(s)=\varnothing and hence Φ^(V)(s)=∅\widehat{\Phi}(\mathcal{V})(s)=\varnothing, which we return. Otherwise, we use a grid cell containing v\mathbf{v} as the initial polytope.

For every vertex g\mathbf{g} of this cell, ∥g−v∥∞≤ξ\lVert\mathbf{g}-\mathbf{v}\rVert_{\infty}\leq\xi. Since v∈Φ(V)(s)\mathbf{v}\in\Phi(\mathcal{V})(s), we therefore have

g∈Neigh⁡ξ(Φ(V)(s))∩Gξ.\mathbf{g}\in\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s))\cap G_{\xi}.

Hence, by the definition of GridHull⁡\operatorname{GridHull}, the entire initial cell is contained in Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s). Using the cell ensures that the initial polytope is full-dimensional, so that the subsequent facet-enumeration procedure is well-defined.

  1. 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 GξG_{\xi}.

  • 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 Φ^(V)(s)\widehat{\Phi}(\mathcal{V})(s).

The algorithm terminates because Neigh⁡ξ(Φ(V)(s))\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s)) 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 Φ^(V)(s)\hat{\Phi}(V)(s) can be computed independently for each state ss, 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.

Value sets from an example run

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.

Achievable value sets for States 0–3

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 B=2.0B = 2.0.

Trajectory of target values

Figure 3. Trajectory of target values generated during the execution of an (ϵ,δ)(\epsilon,\delta)-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 dd cost functions by enlarging the value space from R2\mathbb{R}^{2} to Rd+1\mathbb{R}^{d+1}, the number of grid points grows exponentially in dd. 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 γ∈(0,1)\gamma\in(0,1). There exist constants ϵ,δ>0\epsilon, \delta> 0 such that computing a stationary policy that is (ϵ,δ)(\epsilon,\delta)-optimal among stationary policies is NP-hard.

Proof. We reduce from the GAP 3-SAT problem. An instance is a 3CNF formula φ\varphi, promised to be either satisfiable (a yes-instance) or such that no Boolean assignment satisfies more than a β\beta fraction of its clauses (a no-instance). This problem is NP-hard for any constant β∈(7/8,1)\beta\in(7/8,1) [18].

Consider a GAP 3-SAT instance φ\varphi. Let x1,…,xmx_1,\ldots,x_m be its Boolean variables and C1,…,CnC_1,\ldots,C_n its clauses. Each clause is a disjunction of three literals, each of which is a variable xix_i or its negation ¬xi\neg x_i.

We construct an S-CMDP instance in which every trajectory reaches an absorbing terminal state within four steps. The state space is {s0,s⊥}∪{x1,…,xm}∪⋃j=1n{Cj,ℓj1,ℓj2,ℓj3}\{s_0,s_\perp\} \cup\{x_1,\ldots,x_m\} \cup\bigcup_{j=1}^{n}\{C_j,\ell_{j1},\ell_{j2},\ell_{j3}\}. An example of the reduction is illustrated in Figure 5. In more detail:

Reduction from GAP 3-SAT

Figure 5. Reduction from GAP 3-SAT. In this example, there are four variables x1,…,x4x_1,\ldots,x_4 in φ\varphi and C1=(x1∨x2∨¬x4)C_1=(x_1\lor x_2\lor\neg x_4). The states connected to C1C_1 are shown. The initial state s0s_0, which transitions uniformly to the clause states, is omitted. Edge labels give the reward, which equals the cost in this reduction.

  • s⊥s_\perp is an absorbing terminal state with zero reward and cost. Each state xix_i corresponds to the variable xix_i in the GAP 3-SAT instance; each state CjC_j corresponds to the clause CjC_j; and each state ℓjk\ell_{jk} corresponds to the kk-th literal in CjC_j.

  • The initial state is s0s_0. Irrespective of the action taken, it transitions to each clause state CjC_j with probability 1/n1/n, generating zero reward and cost.

    All other transitions are deterministic:

    • There are four actions available at each CjC_j: one leading to s⊥s_\perp, and three others each leading to one of the literal states ℓj1,ℓj2,ℓj3\ell_{j1},\ell_{j2},\ell_{j3}. All these transitions generate zero reward and zero cost; for all a∈Aa \in A:

      r(Cj,a)=c(Cj,a)=0.r(C_j,a)=c(C_j,a)=0.

      (The action leading to s⊥s_\perp ensures that there is a feasible policy for every instance.)

    • At each literal state ℓjk\ell_{jk}, the only available action leads to the corresponding variable state xix_i. Its reward and cost depend on the sign of the literal:

      r(ℓjk,a)=c(ℓjk,a)={γif ℓjk=xi,0if ℓjk=¬xi.r(\ell_{jk},a)=c(\ell_{jk},a)= \begin{cases} \gamma& \text{if }\ell_{jk}=x_i,\\ 0 & \text{if }\ell_{jk}=\neg x_i. \end{cases}
    • At each variable state xix_i, there are two actions available; call them a0a_0 and a1a_1. Both actions lead to s⊥s_\perp, generating the following reward and cost:

      r(xi,a0)=c(xi,a0)=0,r(x_i,a_0)=c(x_i,a_0)=0,

      and

      r(xi,a1)=c(xi,a1)=1.r(x_i,a_1)=c(x_i,a_1)=1.

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.

    θ(s)={γif s is a positive literal state,2otherwise.\theta(s)= \begin{cases} \gamma& \text{if }s\text{ is a positive literal state},\\ 2 & \text{otherwise}. \end{cases}

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 β∈(7/8,1)\beta\in(7/8,1), choose η∈(0,1−β)\eta\in(0,1-\beta), and set δ=γη\delta=\gamma\eta. We establish the following two claims:

  • Completeness: If the GAP 3-SAT instance is a yes-instance, then there exists a feasible stationary policy π\pi with Vrπ(s0)=γ3V_r^\pi(s_0)=\gamma^3.

  • Soundness: If it is a no-instance, then Vrπ(s0)≤(β+η)γ3V_r^\pi(s_0)\leq(\beta+\eta)\gamma^3 for every δ\delta-feasible stationary policy π\pi.

Taking ϵ=(1−β−η)γ3/2>0\epsilon=(1-\beta-\eta)\gamma^3/2>0 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 φ\varphi is a yes-instance, so there exists a satisfying assignment f:{x1,…,xm}→{true,false}f:\{x_1,\ldots,x_m\}\to\{true,false\}. Consider the following stationary policy π:S→Δ(A)\pi:S\to\Delta(A). We show that Vrπ(s0)=γ3V_r^\pi(s_0)=\gamma^3.

  • At each variable state xix_i, choose a0a_0 if f(xi)=truef(x_i)=true, and a1a_1 otherwise.

  • At each clause state CjC_j, choose with probability 1 an action leading to a literal that is true under ff. Such a literal exists because ff satisfies φ\varphi.

If the chosen literal is positive, its immediate reward and cost are γ\gamma, and the next action is a0a_0, with zero reward and cost. If the chosen literal is negative, its immediate reward and cost are zero, and the next action is a1a_1, with reward and cost 1. Thus, in both cases the onward reward and cost at the literal state equal γ\gamma. All constraints are satisfied, each clause state has reward value γ2\gamma^2, and Vrπ(s0)=γ3V_r^\pi(s_0)=\gamma^3.

Proof of Soundness Suppose that φ\varphi is a no-instance, and let π\pi be any δ\delta-feasible stationary policy. Write

qi=π(a1∣xi).q_i=\pi(a_1\mid x_i).

At a reachable positive literal corresponding to xix_i, the onward cost is γ+γqi\gamma+\gamma q_i. Since its threshold is γ\gamma, δ\delta-feasibility requires qi≤δ/γ=ηq_i\leq\delta/\gamma=\eta. Thus, a positive literal with qi>ηq_i>\eta cannot be reached under π\pi.

Let T={xi∣qi≤η}T=\{x_i\mid q_i\leq\eta\} and let FF contain the remaining variables. We bound the reward at each clause state CjC_j by considering three cases:

  • Case 1: CjC_j contains a positive literal xix_i with xi∈Tx_i\in T. Selecting such a literal gives reward γ2(1+qi)≤(1+η)γ2\gamma^2(1+q_i)\leq(1+\eta)\gamma^2 at CjC_j. Any selectable positive literal satisfies the same bound, and any negative literal gives at most γ2\gamma^2. Thus Vrπ(Cj)≤(1+η)γ2V_r^\pi(C_j)\leq(1+\eta)\gamma^2.

  • Case 2: Case 1 does not apply, but CjC_j contains a negative literal ¬xi\neg x_i with xi∈Fx_i\in F. All positive literals in the clause are unreachable under π\pi, and selecting any negative literal gives reward γ2qi≤γ2\gamma^2q_i\leq\gamma^2 at CjC_j. Hence Vrπ(Cj)≤γ2V_r^\pi(C_j)\leq\gamma^2.

  • Case 3: Neither of the above cases applies. Every positive literal has its variable in FF and is therefore unreachable, while every negative literal has its variable in TT and gives reward at most ηγ2\eta\gamma^2 at CjC_j. The terminal action gives zero reward, so Vrπ(Cj)≤ηγ2V_r^\pi(C_j)\leq\eta\gamma^2.

Assigning true to the variables in TT and false to those in FF satisfies every clause in Cases 1 and 2. Since φ\varphi is a no-instance, these cases cover at most a β\beta fraction of the clauses. Their reward values are at most (1+η)γ2(1+\eta)\gamma^2, while the remaining clause values are at most ηγ2\eta\gamma^2. Accounting for the initial transition from s0s_0, we obtain

Vrπ(s0)=γn∑j=1nVrπ(Cj)≤γ(β(1+η)γ2+(1−β)ηγ2)=(β+η)γ3.V_r^\pi(s_0)=\frac{\gamma}{n}\sum_{j=1}^{n}V_r^\pi(C_j)\leq\gamma\bigl(\beta(1+\eta)\gamma^2+(1-\beta)\eta\gamma^2\bigr)=(\beta+\eta)\gamma^3.

In a yes-instance, any (ϵ,δ)(\epsilon,\delta)-optimal stationary policy has value at least γ3−ϵ\gamma^3-\epsilon. In a no-instance, every δ\delta-feasible stationary policy has value at most (β+η)γ3(\beta+\eta)\gamma^3. Since γ3−ϵ>(β+η)γ3\gamma^3-\epsilon>(\beta+\eta)\gamma^3, 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 s∈Ss\in S and v=(v1,v2)∈R2\mathbf{v}=(v_1,v_2)\in\mathbb{R}^2, we have v∈V⋆(s)\mathbf{v}\in\mathcal{V}^\star(s) if and only if v2≤θ(s)v_2\leq\theta(s) and there exist a distribution πˉ∈Δ(A)\bar{\pi}\in\Delta(A) and a vector w(a,s′)∈R2\mathbf{w}(a,s')\in\mathbb{R}^2 for each (a,s′)∈A×S(a,s')\in A\times S 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 v2≤θ(s)v_2\leq\theta(s) and there exist πˉ\bar{\pi} and w\mathbf{w} satisfying the stated conditions. By Eq. (4), for each pair (a,s′)(a,s') with πˉ(a)⋅p(s′∣s,a)>0\bar{\pi}(a)\cdot p(s'\mid s,a)>0, there exists a feasible policy πa,s′\pi_{a,s'} that achieves the onward vector w(a,s′)\mathbf{w}(a,s') from state s′s'. We construct a policy π\pi by concatenating πˉ\bar{\pi} and these policies: π\pi selects its initial action at ss according to πˉ\bar{\pi}, and thereafter follows πa,s′\pi_{a,s'} once action aa is taken and state s′s' is reached. Its action distribution on unreachable histories can be chosen arbitrarily. Since v2≤θ(s)v_2\leq\theta(s) and each πa,s′\pi_{a,s'} is feasible, the resulting policy π\pi satisfies the subprocess constraints. Applying the Bellman equation then yields Vπ(s)=v\mathbf{V}^\pi(s)=\mathbf{v}. Hence v\mathbf{v} is achievable: v∈V⋆(s)\mathbf{v}\in\mathcal{V}^\star(s). □

Lemma 4 (Monotonicity). If V⊆V′\mathcal{V}\subseteq\mathcal{V}', then Φ(V)⊆Φ(V′)\Phi(\mathcal{V})\subseteq\Phi(\mathcal{V}').

Proof. It is immediate from the definition that Onward⁡(s,⋅)\operatorname{Onward}(s,\cdot) is monotone. Hence, if V⊆V′\mathcal{V}\subseteq\mathcal{V}', then we have Onward⁡(s,V)⊆Onward⁡(s,V′)\operatorname{Onward}(s,\mathcal{V})\subseteq\operatorname{Onward}(s,\mathcal{V}'). According to the definition of Φ\Phi, enlarging the feasible set Onward⁡(s,V)\operatorname{Onward}(s,\mathcal{V}) can only enlarge the resulting value set. Therefore, Φ(V)(s)⊆Φ(V′)(s)\Phi(\mathcal{V})(s)\subseteq\Phi(\mathcal{V}')(s) for all s∈Ss\in S. □

Lemma 5. V⋆⊆BV^\star\subseteq B and Φ(B)⊆B\Phi(B) \subseteq B.

Proof. The inclusion V⋆⊆BV^\star\subseteq B follows from the boundedness of discounted returns. Since rewards and costs are assumed to lie in [−1,1][-1,1], the discounted cumulative return of any policy is bounded in magnitude by the geometric sum ∑t=0∞γt=1/(1−γ)\sum_{t=0}^{\infty} \gamma^t = 1/(1-\gamma). Hence every achievable value vector lies in BB.

For the second inclusion, consider any v∈Φ(B)(s)\mathbf{v} \in\Phi(B)(s). By definition of Φ\Phi, v\mathbf{v} is obtained from an immediate payoff of magnitude at most 11 together with an onward value bounded by 1/(1−γ)1/(1-\gamma). Therefore

∥v∥∞≤1+γ⋅11−γ=11−γ,\lVert\mathbf{v} \rVert_\infty\le1 + \gamma\cdot\frac{1}{1-\gamma} = \frac{1}{1-\gamma},

which implies v∈B\mathbf{v} \in B. Hence Φ(B)⊆B\Phi(B) \subseteq B. □

Lemma 6. V⋆⊆Vk+1⊆VkV^\star\subseteq V^{k+1} \subseteq V^k for all k≥0k \ge0.

Proof. We first prove the base case V⋆⊆V1⊆V0V^\star\subseteq V^1 \subseteq V^0.

Since V⋆⊆BV^\star\subseteq B (Lemma 5), monotonicity of Φ\Phi implies

Φ(V⋆)⊆Φ(B).\Phi(V^\star) \subseteq\Phi(B).

Recall that V⋆=Φ(V⋆)V^\star= \Phi(V^\star) (Corollary 3). Moreover, by definition of the sequence (Vk)k(V^k)_k, we have V0=BV^0 = B and V1=Φ(V0)V^1 = \Phi(V^0). Combining these results establishes

V⋆=Φ(V⋆)⊆Φ(B)=V1.V^\star= \Phi(V^\star) \subseteq\Phi(B) = V^1.

Together with Φ(B)⊆B\Phi(B) \subseteq B (Lemma 5), this yields the base case V⋆⊆V1⊆V0V^\star\subseteq V^1 \subseteq V^0.

Now suppose that V⋆⊆Vk+1⊆VkV^\star\subseteq V^{k+1} \subseteq V^k holds for some k≥0k \ge0. Applying Φ\Phi to the inclusions and using monotonicity gives

Φ(V⋆)⊆Φ(Vk+1)⊆Φ(Vk).\Phi(V^\star) \subseteq\Phi(V^{k+1}) \subseteq\Phi(V^k).

By definition of the sequence (Vk)k(V^k)_k and the fact that V⋆=Φ(V⋆)V^\star= \Phi(V^\star), this becomes V⋆⊆Vk+2⊆Vk+1V^\star\subseteq V^{k+2} \subseteq V^{k+1}.

By induction, the stated result then follows. □

Lemma 7. If VV is bounded and V=Φ(V)V = \Phi(V), then V⊆V⋆V \subseteq V^\star.

Proof. Suppose VV is bounded and V=Φ(V)V = \Phi(V). Fix s∈Ss \in S and v∈V(s)\mathbf{v} \in V(s). We construct a policy π\pi and show that it is feasible and satisfies V⃗π(s)=v\vec{V}^{\pi}(s) = \mathbf{v}.

Recursive Policy Construction For a history hh, let shs_h denote its last state. We define the policy π\pi and targets vh∈V(sh)\mathbf{v}_h \in V(s_h) recursively over reachable histories:

  • At the initial history h0=(s)h_0 = (s), assign the target vh0=v\mathbf{v}_{h_0} = \mathbf{v}.

  • At each reachable history hh with target vh\mathbf{v}_h, choose (πˉh,wh)∈Onward⁡(sh,V)(\bar{\pi}_h, \mathbf{w}_h) \in\operatorname{Onward}(s_h,V) such that

Bellman⁡(sh,πˉh,wh)=vh.\operatorname{Bellman}(s_h,\bar{\pi}_h,\mathbf{w}_h) = \mathbf{v}_h.

Such a pair exists because V=Φ(V)V = \Phi(V). Set

π(h)=πˉh.\pi(h) = \bar{\pi}_h.
  • For every pair (a,s′)(a,s') with πˉh(a)⋅p(s′∣sh,a)>0\bar{\pi}_h(a) \cdot p(s' \mid s_h,a) > 0, assign to the reachable extension h′=(h,a,s′)h' = (h,a,s') the target

vh′=wh(a,s′).\mathbf{v}_{h'} = \mathbf{w}_h(a,s').

Crucially, the onward condition imposed on wh\mathbf{w}_h ensures that vh′∈V(s′)\mathbf{v}_{h'} \in V(s'), so the construction can continue at h′h'.

For completeness, for all unreachable histories hh, we assign an arbitrary action distribution to π(h)\pi(h). Exact Realization Let V⃗π(h)\vec{V}^{\pi}(h) denote the true onward value of π\pi conditional on hh. Its Bellman expansion and the exact decomposition of vh\mathbf{v}_h use the same immediate reward and cost terms. Subtracting them and using the successor targets gives

V⃗π(h)−vh=γEπ[V⃗π(h′)−vh′∣h],\vec{V}^{\pi}(h)-\mathbf{v}_h=\gamma\mathbb{E}_{\pi}\left[\left.\vec{V}^{\pi}(h')-\mathbf{v}_{h'}\right|h\right],
∥V⃗π(h)−vh∥∞≤γEπ[∥V⃗π(h′)−vh′∥∞∣h].\left\|\vec{V}^{\pi}(h)-\mathbf{v}_h\right\|_{\infty}\leq\gamma\mathbb{E}_{\pi}\left[\left.\left\|\vec{V}^{\pi}(h')-\mathbf{v}_{h'}\right\|_{\infty}\right|h\right].

where h′h' is the next history obtained from hh under π\pi and pp, and the inequality follows from the triangle inequality. Since V\mathcal{V} is bounded, let M<∞M<\infty bound the L∞L_{\infty} norms of its vectors. Every target then has norm at most MM, while every true onward value has norm at most 1/(1−γ)1/(1-\gamma). Iterating the inequality for T≥1T\geq1 steps therefore yields

∥V⃗π(h)−vh∥∞≤γT(11−γ+M).\left\|\vec{V}^{\pi}(h)-\mathbf{v}_h\right\|_{\infty}\leq\gamma^{T}\left(\frac{1}{1-\gamma}+M\right).

Letting T→∞T\to\infty gives V⃗π(h)=vh\vec{V}^{\pi}(h)=\mathbf{v}_h at every reachable history. In particular, V⃗π(s)=v\vec{V}^{\pi}(s)=\mathbf{v}.

Feasibility At every reachable history hh, we have vh∈V(sh)=Φ(V)(sh)\mathbf{v}_h\in\mathcal{V}(s_h)=\Phi(\mathcal{V})(s_h), so vh,2≤θ(sh)v_{h,2}\leq\theta(s_h). Since V⃗π(h)=vh\vec{V}^{\pi}(h)=\mathbf{v}_h, the policy π\pi is feasible. Thus v∈V⋆(s)\mathbf{v}\in\mathcal{V}^{\star}(s), proving V⊆V⋆\mathcal{V}\subseteq\mathcal{V}^{\star}.

Theorem 8. Vk→V⋆\mathcal{V}^{k}\to\mathcal{V}^{\star} as k→∞k\to\infty.

Proof. Let V∞(s):=⋂k≥0Vk(s)\mathcal{V}^{\infty}(s):=\bigcap_{k\geq0}\mathcal{V}^{k}(s) for every s∈Ss\in S. By Lemma 6, we already have V⋆⊆V∞⊆B\mathcal{V}^{\star}\subseteq\mathcal{V}^{\infty}\subseteq\mathcal{B}. Thus, by Lemma 7, it suffices to show that V∞\mathcal{V}^{\infty} is a fixed point of Φ\Phi. We prove the two inclusions separately.

The Inclusion V∞⊆Φ(V∞)\mathcal{V}^{\infty}\subseteq\Phi(\mathcal{V}^{\infty}) We construct a Bellman decomposition in V∞\mathcal{V}^{\infty} by taking a limit of decompositions in the iterates. Fix an arbitrary state s∈Ss\in S and vector v∈V∞(s)\mathbf{v}\in\mathcal{V}^{\infty}(s). By definition, v∈Vk(s)\mathbf{v}\in\mathcal{V}^{k}(s) for all k≥0k\geq0. Since Vk+1=Φ(Vk)\mathcal{V}^{k+1}=\Phi(\mathcal{V}^{k}), we also have v∈Φ(Vk)(s)\mathbf{v}\in\Phi(\mathcal{V}^{k})(s). According to the definition of Φ\Phi, for each kk, there exists (πˉk,wk)∈Onward⁡(s,Vk)(\bar{\pi}^{k},\mathbf{w}^{k})\in\operatorname{Onward}(s,\mathcal{V}^{k}) such that

v=Bellman⁡(s,πˉk,wk).\mathbf{v}=\operatorname{Bellman}(s,\bar{\pi}^{k},\mathbf{w}^{k}).

Choose wk(a,s′)=0\mathbf{w}^{k}(a,s')=\mathbf{0} whenever πˉk(a)⋅p(s′∣s,a)=0\bar{\pi}^{k}(a)\cdot p(s'\mid s,a)=0; this does not affect the Bellman expansion. All onward vectors then lie in B\mathcal{B}. Consider the sequence (πˉk,wk)k≥0(\bar{\pi}^{k},\mathbf{w}^{k})_{k\geq0}. Since both components are bounded, by the Bolzano–Weierstrass theorem, this sequence admits a convergent subsequence (πˉkℓ,wkℓ)ℓ≥0(\bar{\pi}^{k_{\ell}},\mathbf{w}^{k_{\ell}})_{\ell\geq0}. Let (πˉ,w)(\bar{\pi},\mathbf{w}) 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. (πˉ,w)∈Onward⁡(s,V∞)(\bar{\pi},\mathbf{w})\in\operatorname{Onward}(s,\mathcal{V}^{\infty}).

Proof. According to the definition of Onward⁡(s,⋅)\operatorname{Onward}(s,\cdot) in Eq. (7), we need to show that:

  1. πˉ∈Δ(A)\bar{\pi}\in\Delta(A); and

  2. w(a,s′)∈V∞(s′)\mathbf{w}(a,s')\in\mathcal{V}^{\infty}(s') for all aa and s′s' such that πˉ(a)⋅p(s′∣s,a)>0\bar{\pi}(a)\cdot p(s'\mid s,a)>0.

For (i), note that Δ(A)\Delta(A) is closed and each πˉkℓ∈Δ(A)\bar{\pi}^{k_{\ell}}\in\Delta(A). Since πˉ\bar{\pi} is their limit, it follows that πˉ∈Δ(A)\bar{\pi}\in\Delta(A).

For (ii), fix a∈Aa\in A and s′∈Ss'\in S such that πˉ(a)⋅p(s′∣s,a)>0\bar{\pi}(a)\cdot p(s'\mid s,a)>0. Let k≥0k\geq0 be arbitrary. Since kℓ→∞k_{\ell}\to\infty and πˉkℓ(a)→πˉ(a)>0\bar{\pi}^{k_{\ell}}(a)\to\bar{\pi}(a)>0, there exists LL such that kℓ≥kk_{\ell}\geq k and πˉkℓ(a)⋅p(s′∣s,a)>0\bar{\pi}^{k_{\ell}}(a)\cdot p(s'\mid s,a)>0 for all ℓ≥L\ell\geq L. Because (πˉkℓ,wkℓ)∈Onward⁡(s,Vkℓ)(\bar{\pi}^{k_{\ell}},\mathbf{w}^{k_{\ell}})\in\operatorname{Onward}(s,\mathcal{V}^{k_{\ell}}) we have

wkℓ(a,s′)∈Vkℓ(s′)⊆Vk(s′)\mathbf{w}^{k_{\ell}}(a,s')\in\mathcal{V}^{k_{\ell}}(s')\subseteq\mathcal{V}^{k}(s')

for all ℓ≥L\ell\ge L.

To pass to the limit, we use the fact that Φ\Phi 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 V0(s′)=B\mathcal{V}^{0}(s') = \mathcal{B} is closed and all iterates are bounded, induction shows that every Vk(s′)\mathcal{V}^{k}(s') is closed.

Taking limits therefore gives w(a,s′)∈Vk(s′)\mathbf{w}(a,s') \in\mathcal{V}^{k}(s'). Since kk is arbitrary, we conclude that w(a,s′)∈⋂k≥0Vk(s′)=V∞(s′)\mathbf{w}(a,s') \in\bigcap_{k\ge0}\mathcal{V}^{k}(s') = \mathcal{V}^{\infty}(s'). □

We can now pass to the limit in the Bellman expansion. Since v=Bellman⁡(s,πˉkℓ,wkℓ)\mathbf{v} = \operatorname{Bellman}(s,\bar{\pi}^{k_\ell},\mathbf{w}^{k_\ell}) for all ℓ\ell, and Bellman⁡(s,⋅,⋅)\operatorname{Bellman}(s,\cdot,\cdot) is continuous, taking limits along the subsequence yields v=Bellman⁡(s,πˉ,w)\mathbf{v} = \operatorname{Bellman}(s,\bar{\pi},\mathbf{w}). Moreover, v2≤θ(s)v_2 \le\theta(s) since v∈V1(s)\mathbf{v} \in\mathcal{V}^{1}(s). Together with Claim 1, this implies v∈Φ(V∞)(s)\mathbf{v} \in\Phi(\mathcal{V}^{\infty})(s). Because the choice of s∈Ss \in S and v∈V∞(s)\mathbf{v} \in\mathcal{V}^{\infty}(s) is arbitrary, we conclude that

V∞⊆Φ(V∞).\mathcal{V}^{\infty} \subseteq\Phi(\mathcal{V}^{\infty}).

The Reverse Inclusion Since V∞⊆Vk\mathcal{V}^{\infty} \subseteq\mathcal{V}^{k} for every k≥0k \ge0, monotonicity gives Φ(V∞)⊆Φ(Vk)=Vk+1\Phi(\mathcal{V}^{\infty}) \subseteq\Phi(\mathcal{V}^{k}) = \mathcal{V}^{k+1}. Taking intersections yields, for every s∈Ss \in S,

Φ(V∞)(s)⊆⋂k≥0Vk+1(s)=⋂k≥0Vk(s)=V∞(s),\Phi(\mathcal{V}^{\infty})(s) \subseteq\bigcap_{k\ge0}\mathcal{V}^{k+1}(s) = \bigcap_{k\ge0}\mathcal{V}^{k}(s) = \mathcal{V}^{\infty}(s),

where dropping V0(s)\mathcal{V}^{0}(s) does not change the intersection because the iterates are nested. Therefore, V∞=Φ(V∞)\mathcal{V}^{\infty} = \Phi(\mathcal{V}^{\infty}). By Lemma 7, V∞⊆V⋆\mathcal{V}^{\infty} \subseteq\mathcal{V}^{\star}, and the reverse inclusion from Lemma 6 gives V∞=V⋆\mathcal{V}^{\infty} = \mathcal{V}^{\star}. □

Proofs in Section 6

Lemma 9. V⋆⊆V^k+1⊆V^k\mathcal{V}^{\star} \subseteq\widehat{\mathcal{V}}^{k+1} \subseteq\widehat{\mathcal{V}}^{k} for all k≥0k \ge0.

Proof. Let rξr_{\xi} denote the radius of B^ξ\widehat{\mathcal{B}}_{\xi}. By definition,

rξ>11−γandrξ∈ξN,r_{\xi} > \frac{1}{1-\gamma} \qquad\text{and}\qquad r_{\xi} \in\xi\mathbb{N},

and V^0=B^ξ\widehat{\mathcal{V}}^{0} = \widehat{\mathcal{B}}_{\xi}.

We first establish (i) V⋆⊆V^0\mathcal{V}^{\star} \subseteq\widehat{\mathcal{V}}^{0}, and (ii) Φ^(V^0)⊆V^0\widehat{\Phi}(\widehat{\mathcal{V}}^{0}) \subseteq\widehat{\mathcal{V}}^{0}. Indeed, condition (i) is immediate, since

V⋆⊆B⊆B^ξ=V^0.\mathcal{V}^{\star} \subseteq\mathcal{B} \subseteq\widehat{\mathcal{B}}_{\xi} = \widehat{\mathcal{V}}^{0}.

To verify (ii), fix any s∈Ss \in S and v∈Φ^(V^0)(s)\mathbf{v} \in\widehat{\Phi}(\widehat{\mathcal{V}}^{0})(s). Since the immediate return is bounded in L∞L_{\infty} norm by 1 and every onward value in V^0\widehat{\mathcal{V}}^{0} has L∞L_{\infty} norm at most rξr_{\xi}, we get that

∥v∥∞≤1+γrξ<rξ,\lVert\mathbf{v}\rVert_{\infty} \le1+\gamma r_{\xi} < r_{\xi},

where the strict inequality follows from rξ>1/(1−γ)r_{\xi} > 1/(1-\gamma).

Now consider any

g∈Neigh⁡ξ(Φ^(V^0)(s))∩Gξ.\mathbf{g} \in\operatorname{Neigh}_{\xi}\bigl(\widehat{\Phi}(\widehat{\mathcal{V}}^{0})(s)\bigr) \cap G_{\xi}.

There exists v∈Φ^(V^0)(s)\mathbf{v} \in\widehat{\Phi}(\widehat{\mathcal{V}}^{0})(s) such that ∥g−v∥∞≤ξ\lVert\mathbf{g}-\mathbf{v}\rVert_{\infty} \le\xi, and hence ∥g∥∞<rξ+ξ\lVert\mathbf{g}\rVert_{\infty} < r_{\xi}+\xi. Since g∈Gξ\mathbf{g} \in G_{\xi}, ∥g∥∞\lVert\mathbf{g}\rVert_{\infty} is a multiple of ξ\xi. As rξr_{\xi} is also a multiple of ξ\xi, it follows that

∥g∥∞≤rξ.\lVert\mathbf{g}\rVert_{\infty} \le r_{\xi}.

Thus every such grid point belongs to V^0\widehat{\mathcal{V}}^{0}. Since V^0\widehat{\mathcal{V}}^{0} is convex, by the definition of Φ^\widehat{\Phi}, we get that

Φ^(V^0)(s)=GridHull⁡ξ(Neigh⁡ξ(Φ(V^0)(s)))⊆V^0.\widehat{\Phi}(\widehat{\mathcal{V}}^{0})(s)=\operatorname{GridHull}_{\xi}\left(\operatorname{Neigh}_{\xi}\left(\Phi(\widehat{\mathcal{V}}^{0})(s)\right)\right)\subseteq\widehat{\mathcal{V}}^{0}.

Since ss was arbitrary, condition (ii) follows.

Finally, observe that for any value-set function V\mathcal{V}, we have

Φ(V)(s)⊆Φ^(V)(s)for every s∈S.\Phi(\mathcal{V})(s)\subseteq\widehat{\Phi}(\mathcal{V})(s)\qquad\text{for every }s\in S.

Indeed, fix any v∈Φ(V)(s)\mathbf{v}\in\Phi(\mathcal{V})(s) and consider a grid cell containing v\mathbf{v}. Every vertex g\mathbf{g} of this cell belongs to GξG_{\xi} and satisfies ∥g−v∥∞≤ξ\lVert\mathbf{g}-\mathbf{v}\rVert_{\infty}\leq\xi, so

g∈Neigh⁡ξ(Φ(V)(s))∩Gξ.\mathbf{g}\in\operatorname{Neigh}_{\xi}(\Phi(\mathcal{V})(s))\cap G_{\xi}.

Since v\mathbf{v} is a convex combination of the vertices of the cell, the definition of GridHull⁡ξ\operatorname{GridHull}_{\xi} then implies v∈Φ^(V)(s)\mathbf{v}\in\widehat{\Phi}(\mathcal{V})(s); therefore, Φ(V)(s)⊆Φ^(V)(s)\Phi(\mathcal{V})(s)\subseteq\widehat{\Phi}(\mathcal{V})(s).

Applying this to V⋆\mathcal{V}^{\star} and using V⋆=Φ(V⋆)\mathcal{V}^{\star}=\Phi(\mathcal{V}^{\star}) gives

V⋆=Φ(V⋆)⊆Φ^(V⋆).\mathcal{V}^{\star}=\Phi(\mathcal{V}^{\star})\subseteq\widehat{\Phi}(\mathcal{V}^{\star}).

Together with the monotonicity of Φ^\widehat{\Phi}, conditions (i) and (ii) give

V⋆⊆V^1⊆V^0.\mathcal{V}^{\star}\subseteq\widehat{\mathcal{V}}^{1}\subseteq\widehat{\mathcal{V}}^{0}.

Applying Φ^\widehat{\Phi} repeatedly and using V⋆⊆Φ^(V⋆)\mathcal{V}^{\star}\subseteq\widehat{\Phi}(\mathcal{V}^{\star}) then yields

V⋆⊆V^k+1⊆V^k\mathcal{V}^{\star}\subseteq\widehat{\mathcal{V}}^{k+1}\subseteq\widehat{\mathcal{V}}^{k}

for every k≥0k\geq0.

Lemma 10. If V\mathcal{V} is bounded and V=Φ^(V)\mathcal{V}=\widehat{\Phi}(\mathcal{V}), then for all s∈Ss\in S every v∈V(s)\mathbf{v}\in\mathcal{V}(s) is (ϵ,δ)(\epsilon,\delta)-achievable from ss.

Proof. Suppose V\mathcal{V} is bounded and V=Φ^(V)\mathcal{V}=\widehat{\Phi}(\mathcal{V}). Fix s∈Ss\in S and v∈V(s)\mathbf{v}\in\mathcal{V}(s). We construct a policy π\pi and show that it is δ\delta-feasible and satisfies ∥V⃗π(s)−v∥∞≤ϵ\lVert\vec{V}^{\pi}(s)-\mathbf{v}\rVert_{\infty}\leq\epsilon. The construction uses a relaxed version of Achieve (Algorithm 2), allowing a Bellman error of at most ξ\xi at each step.

Recursive Policy Construction We first note that, for every s′∈Ss'\in S,

Φ^(V)(s′)=GridHull⁡ξ(Neigh⁡ξ(Φ(V)(s′)))⊆Neigh⁡ξ(Φ(V)(s′)).\widehat{\Phi}(\mathcal{V})(s')=\operatorname{GridHull}_{\xi}\left(\operatorname{Neigh}_{\xi}\left(\Phi(\mathcal{V})(s')\right)\right)\subseteq\operatorname{Neigh}_{\xi}\left(\Phi(\mathcal{V})(s')\right).

Indeed, V=Φ^(V)\mathcal{V}=\widehat{\Phi}(\mathcal{V}) has convex values, so Φ(V)(s′)\Phi(\mathcal{V})(s') is convex by mixing Bellman decompositions. Its ξ\xi-neighborhood is therefore convex and contains the convex hull of its grid points. Using V=Φ^(V)\mathcal{V}=\widehat{\Phi}(\mathcal{V}) now gives

V(s′)⊆Neigh⁡ξ(Φ(V)(s′)).\mathcal{V}(s')\subseteq\operatorname{Neigh}_{\xi}\left(\Phi(\mathcal{V})(s')\right).

For a history hh, let shs_h denote its last state. We define the policy π\pi and targets vh∈V(sh)\mathbf{v}_h\in\mathcal{V}(s_h) recursively over reachable histories:

  • At the initial history h0=(s)h_0=(s), assign the target vh0=v\mathbf{v}_{h_0}=\mathbf{v}.

  • At each reachable history hh with target vh\mathbf{v}_h, choose (πˉh,wh)∈Onward⁡(sh,V)(\bar{\pi}_h,\mathbf{w}_h)\in\operatorname{Onward}(s_h,\mathcal{V}) such that

Bellman⁡(sh,πˉh,wh)∈Neigh⁡ξ(vh),(13)\operatorname{Bellman}(s_h,\bar{\pi}_h,\mathbf{w}_h)\in\operatorname{Neigh}_{\xi}(\mathbf{v}_h), \tag*{(13)}

and set

π(h)=πˉh.\pi(h)=\bar{\pi}_h.

Such a choice exists because the inclusion above ensures that some vector in Φ(V)(sh)\Phi(\mathcal{V})(s_h) lies within distance ξ\xi of vh\mathbf{v}_h. By the definition of Φ\Phi, that vector admits a Bellman decomposition using a pair in Onward⁡(sh,V)\operatorname{Onward}(s_h,\mathcal{V}), which satisfies Eq. (13).

  • For every pair (a,s′)(a,s') with πˉh(a)⋅p(s′∣sh,a)>0\bar{\pi}_h(a)\cdot p(s'\mid s_h,a)>0, assign to the reachable extension h′=(h,a,s′)h'=(h,a,s') the target

vh′=wh(a,s′)∈V(s′).v_{h'}=w_h(a,s')\in\mathcal{V}(s').

The membership wh(a,s′)∈V(s′)w_h(a,s')\in\mathcal{V}(s') follows from the onward condition; it ensures that the recursive construction can continue at h′h'.

Define π\pi arbitrarily on unreachable histories. The construction uses precisely the relaxed expansion in Algorithm 5, with V\mathcal{V} in place of V^⋆\widehat{\mathcal{V}}^\star.

Approximation Error For each reachable history hh, write v~h=Bellman⁡(sh,πˉh,wh)\tilde{v}_h=\operatorname{Bellman}(s_h,\bar{\pi}_h,w_h). By Eq. (13),

∥v~h−vh∥∞≤ξ.(14)\lVert\tilde{v}_h-v_h\rVert_\infty\leq\xi. \tag*{(14)}

Let V⃗π(h)\vec{V}^{\pi}(h) denote the true onward value of π\pi conditional on hh. Define the onward-value function W⃗h\vec{W}_h by

W⃗h(a,s′)=V⃗π(h,a,s′)\vec{W}_h(a,s')=\vec{V}^{\pi}(h,a,s')

for each reachable extension (h,a,s′)(h,a,s'), assigning arbitrary values on zero-probability pairs. The Bellman equation then gives

V⃗π(h)=Bellman⁡(sh,πˉh,W⃗h),v~h=Bellman⁡(sh,πˉh,wh).\vec{V}^{\pi}(h)=\operatorname{Bellman}(s_h,\bar{\pi}_h,\vec{W}_h),\qquad\tilde{v}_h=\operatorname{Bellman}(s_h,\bar{\pi}_h,w_h).

Both expressions use the same immediate reward and cost terms. Subtracting them and using the successor targets gives

V⃗π(h)−v~h=γEπ[V⃗π(h′)−vh′∣h],\vec{V}^{\pi}(h)-\tilde{v}_h=\gamma\mathbb{E}_{\pi}\left[\vec{V}^{\pi}(h')-v_{h'}\mid h\right],

where h′h' is the next history obtained from hh under π\pi and pp. Taking the L∞L_\infty norm and applying the triangle inequality and Eq. (14) gives

∥V⃗π(h)−vh∥∞≤∥V⃗π(h)−v~h∥∞+∥v~h−vh∥∞≤ξ+γEπ[∥V⃗π(h′)−vh′∥∞∣h]≤ξ+γmax⁡h′∥V⃗π(h′)−vh′∥∞.\begin{aligned} \lVert\vec{V}^{\pi}(h)-v_h\rVert_\infty &\leq\lVert\vec{V}^{\pi}(h)-\tilde{v}_h\rVert_\infty+\lVert\tilde{v}_h-v_h\rVert_\infty\\ &\leq\xi+\gamma\mathbb{E}_{\pi}\left[\lVert\vec{V}^{\pi}(h')-v_{h'}\rVert_\infty\mid h\right]\\ &\leq\xi+\gamma\max_{h'}\lVert\vec{V}^{\pi}(h')-v_{h'}\rVert_\infty. \end{aligned}

Here, the expectation is a weighted average over all histories h′h' reachable from hh in one step, so it is bounded by the maximum over those histories. Since V\mathcal{V} is bounded, let M<∞M<\infty bound the L∞L_\infty norms of its vectors. Every target then has norm at most MM, while every true onward value has norm at most 1/(1−γ)1/(1-\gamma). Iterating this inequality for T≥1T\geq1 steps therefore yields

∥V⃗π(h)−vh∥∞≤ξ∑j=0T−1γj+γT(11−γ+M).\lVert\vec{V}^{\pi}(h)-v_h\rVert_\infty\leq\xi\sum_{j=0}^{T-1}\gamma^j+\gamma^T\left(\frac{1}{1-\gamma}+M\right).

Letting T→∞T\to\infty gives

∥V⃗π(h)−vh∥∞≤ξ1−γ≤ϵ.(15)\lVert\vec{V}^{\pi}(h)-v_h\rVert_\infty\leq\frac{\xi}{1-\gamma}\leq\epsilon. \tag*{(15)}

Applying this at h0=(s)h_0=(s) gives ∥V⃗π(s)−v∥∞≤ϵ\lVert\vec{V}^{\pi}(s)-v\rVert_\infty\leq\epsilon.

Feasibility Every target vh\mathbf{v}_h lies within distance ξ\xi of Φ(V)(sh)\Phi(\mathcal{V})(s_h), whose vectors satisfy the cost threshold at shs_h. Hence

vh,2≤θ(sh)+ξ.(16)v_{h,2} \le\theta(s_h) + \xi. \tag*{(16)}

Together with Eq. (15), this yields, at every reachable history hh,

V2π(h)≤vh,2+ξ1−γ≤θ(sh)+ξ+ξ1−γ≤θ(sh)+δ,V^\pi_2(h) \le v_{h,2} + \frac{\xi}{1-\gamma} \le\theta(s_h) + \xi+ \frac{\xi}{1-\gamma} \le\theta(s_h) + \delta,

where the final inequality follows from ξ≤(1−γ)min⁡{ϵ,δ/2}\xi\le(1-\gamma)\min\{\epsilon,\delta/2\}. Thus π\pi is δ\delta-feasible and v\mathbf{v} is (ϵ,δ)(\epsilon,\delta)-achievable from ss. □\square

Lemma 11. Suppose each V(s′)\mathcal{V}(s') is given as the convex hull of finitely many grid points. For any ss and v\mathbf{v}, 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 πˉ(a)⋅w(a,s′)\bar{\pi}(a)\cdot\mathbf{w}(a,s'). Second, the index selection condition in (12) depends on the variable πˉ(a)\bar{\pi}(a). 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 a∈Aa\in A and s′∈Ss'\in S, where we write πˉ(a)⋅V(s′)={πˉ(a)⋅v∣v∈V(s′)}\bar{\pi}(a)\cdot\mathcal{V}(s')=\{\bar{\pi}(a)\cdot\mathbf{v}\mid\mathbf{v}\in\mathcal{V}(s')\}:

πˉ(a)⋅w(a,s′)∈πˉ(a)⋅V(s′)if p(s′∣s,a)>0 and V(s′)≠∅,πˉ(a)=0if p(s′∣s,a)>0 and V(s′)=∅.\begin{aligned} \bar{\pi}(a)\cdot\mathbf{w}(a,s') &\in\bar{\pi}(a)\cdot\mathcal{V}(s') && \text{if }p(s'\mid s,a)>0\text{ and }\mathcal{V}(s')\ne\varnothing,\\ \bar{\pi}(a)&=0 && \text{if }p(s'\mid s,a)>0\text{ and }\mathcal{V}(s')=\varnothing. \end{aligned}

The first constraint holds automatically if πˉ(a)=0\bar{\pi}(a)=0; and if πˉ(a)>0\bar{\pi}(a)>0, it reduces to w(a,s′)∈V(s′)\mathbf{w}(a,s')\in\mathcal{V}(s'). Thus the dependence of the index condition on πˉ(a)\bar{\pi}(a) is removed.

Linearizing Quadratic Terms Let G(s′)G(s') be the finite set of grid points representing V(s′)\mathcal{V}(s'), so that V(s′)=Conv⁡(G(s′))\mathcal{V}(s')=\operatorname{Conv}(G(s')). We introduce convex-weight variables only for pairs (a,s′)(a,s') with p(s′∣s,a)>0p(s'\mid s,a)>0 and G(s′)≠∅G(s')\ne\varnothing; empty successor sets with positive transition probability are handled by the zero-action-probability condition above. Then any πˉ(a)⋅w(a,s′)∈πˉ(a)⋅V(s′)\bar{\pi}(a)\cdot\mathbf{w}(a,s')\in\bar{\pi}(a)\cdot\mathcal{V}(s') can be written as a convex combination

πˉ(a)⋅w(a,s′)=∑g∈G(s′)ya,s′(g)⋅(πˉ(a)⋅g),\bar{\pi}(a)\cdot\mathbf{w}(a,s')=\sum_{\mathbf{g}\in G(s')}y_{a,s'}(\mathbf{g})\cdot\bigl(\bar{\pi}(a)\cdot\mathbf{g}\bigr),

where ya,s′=(ya,s′(g))g∈G(s′)\mathbf{y}_{a,s'}=(y_{a,s'}(\mathbf{g}))_{\mathbf{g}\in G(s')} satisfies

ya,s′∈Δ(G(s′)).(17)\mathbf{y}_{a,s'}\in\Delta(G(s')). \tag*{(17)}

Namely, πˉ(a)⋅V(s′)\bar{\pi}(a)\cdot\mathcal{V}(s') is the convex hull of the grid points scaled by πˉ(a)\bar{\pi}(a).

Substituting this representation of πˉ(a)⋅w(a,s′)\bar{\pi}(a)\cdot\mathbf{w}(a,s') into (10) and the reformulation of (12) above, we convert the quadratic terms to πˉ(a)⋅ya,s′(g)\bar{\pi}(a)\cdot y_{a,s'}(\mathbf{g}). To eliminate these terms, introduce auxiliary variables

za,s′(g)=πˉ(a)⋅ya,s′(g).z_{a,s'}(\mathbf{g})=\bar{\pi}(a)\cdot y_{a,s'}(\mathbf{g}).

Since ya,s′∈Δ(G(s′))\mathbf{y}_{a,s'}\in\Delta(G(s')), the variables za,s′=(za,s′(g))g∈G(s′)\mathbf{z}_{a,s'}=(z_{a,s'}(\mathbf{g}))_{\mathbf{g}\in G(s')} satisfy the following constraints:

za,s′(g)≥0,∑g∈G(s′)za,s′(g)=πˉ(a).(18)z_{a,s'}(\mathbf{g})\ge0,\qquad\sum_{\mathbf{g}\in G(s')}z_{a,s'}(\mathbf{g})=\bar{\pi}(a). \tag*{(18)}

We replace (17) with them.

This substitution replaces every product πˉ(a)⋅ya,s′(g)\bar{\pi}(a)\cdot y_{a,s'}(\mathbf{g}) with a linear variable. The resulting constraints are linear in πˉ\bar{\pi} and the auxiliary variables za,s′\mathbf{z}_{a,s'}.

Equivalence of the Reformulation The reformulation is trivially equivalent before introducing z\mathbf{z}. To see that it remains equivalent after we replace y\mathbf{y} with z\mathbf{z}, observe that if (v~,πˉ,y)(\tilde{\mathbf{v}}, \bar{\pi}, \mathbf{y}) satisfies the original formulation, then (v~,πˉ,z)(\tilde{\mathbf{v}}, \bar{\pi}, \mathbf{z}) with za,s′=πˉ(a)ya,s′z_{a,s'} = \bar{\pi}(a)y_{a,s'} satisfies the reformulated constraints.

Conversely, given feasible (v~,πˉ,z)(\tilde{\mathbf{v}}, \bar{\pi}, \mathbf{z}), define, for each pair with p(s′∣s,a)>0p(s' \mid s,a)>0 and G(s′)≠∅G(s') \ne\varnothing,

ya,s′={za,s′/πˉ(a)if πˉ(a)>0,an arbitrary vector in Δ(G(s′))if πˉ(a)=0.y_{a,s'} = \begin{cases} z_{a,s'}/\bar{\pi}(a) & \text{if } \bar{\pi}(a)>0,\\ \text{an arbitrary vector in } \Delta(G(s')) & \text{if } \bar{\pi}(a)=0. \end{cases}

Then (v~,πˉ,y)(\tilde{\mathbf{v}}, \bar{\pi}, \mathbf{y}) satisfies the original formulation. In particular, in the case where πˉ(a)=0\bar{\pi}(a)=0, Eq. (18) implies that za,s′=0z_{a,s'}=0; hence, any arbitrary ya,s′∈Δ(G(s′))y_{a,s'} \in\Delta(G(s')) gives za,s′=πˉ(a)⋅ya,s′z_{a,s'}=\bar{\pi}(a)\cdot y_{a,s'}.

The Full LP Reformulation In summary, the full LP reformulation is as follows. The variables are:

  • v~=(v~1,v~2)\tilde{\mathbf{v}}=(\tilde{v}_1,\tilde{v}_2);

  • πˉ(a)\bar{\pi}(a) for each a∈Aa\in A; and

  • za,s′(g)z_{a,s'}(\mathbf{g}) for each a∈Aa\in A, s′∈Ss'\in S, and g∈G(s′)\mathbf{g}\in G(s').

For uniform notation, we retain the variables for pairs with p(s′∣s,a)=0p(s'\mid s,a)=0; they are unconstrained and contribute nothing to the Bellman expression. The constraints are:

  • Eqs. (9) and (11): ∥v−v~∥∞≤ξ\lVert\mathbf{v}-\tilde{\mathbf{v}}\rVert_{\infty}\le\xi, and v~2≤θ(s)\tilde{v}_2\le\theta(s).

  • The linearized form of Eq. (10), as follows:

v~=∑a∈Aπˉ(a)⋅x(s,a)+γ∑a∈A∑s′∈Sp(s′∣s,a)∑g∈G(s′)za,s′(g)⋅g\tilde{\mathbf{v}}=\sum_{a\in A}\bar{\pi}(a)\cdot\mathbf{x}(s,a)+\gamma\sum_{a\in A}\sum_{s'\in S}p(s'\mid s,a)\sum_{\mathbf{g}\in G(s')}z_{a,s'}(\mathbf{g})\cdot\mathbf{g}
  • The linearized form of Eq. (12), for each a∈Aa\in A and s′∈Ss'\in S such that p(s′∣s,a)>0p(s'\mid s,a)>0:

    • If V(s′)≠∅\mathcal{V}(s')\ne\varnothing, then za,s′(g)≥0z_{a,s'}(\mathbf{g})\ge0 for all g∈G(s′)\mathbf{g}\in G(s') and ∑g∈G(s′)za,s′(g)=πˉ(a)\sum_{\mathbf{g}\in G(s')}z_{a,s'}(\mathbf{g})=\bar{\pi}(a);

    • If V(s′)=∅\mathcal{V}(s')=\varnothing, then πˉ(a)=0\bar{\pi}(a)=0.

  • Finally, πˉ∈Δ(A)\bar{\pi}\in\Delta(A) so that πˉ\bar{\pi} is a valid distribution.

Any feasible (v~,πˉ,z)(\tilde{\mathbf{v}},\bar{\pi},\mathbf{z}) yields a feasible solution (v~,πˉ,w)(\tilde{\mathbf{v}},\bar{\pi},\mathbf{w}) of the original constraints by setting

w(a,s′)={∑g∈G(s′)za,s′(g)⋅g/πˉ(a)if πˉ(a)>0,arbitraryif πˉ(a)=0.w(a,s')= \begin{cases} \sum_{\mathbf{g}\in G(s')}z_{a,s'}(\mathbf{g})\cdot\mathbf{g}/\bar{\pi}(a) & \text{if } \bar{\pi}(a)>0,\\ \text{arbitrary} & \text{if } \bar{\pi}(a)=0. \end{cases}

This completes the proof.

Theorem 12. For fixed γ∈(0,1)\gamma\in(0,1), choosing ξ=(1−γ)min⁡{ϵ,δ/2}\xi=(1-\gamma)\min\{\epsilon,\delta/2\} allows us to compute a fixed point V^⋆⊇V⋆\hat{V}^{\star}\supseteq V^{\star} of Φ^\hat{\Phi} in time polynomial in the input size, 1/ϵ1/\epsilon, and 1/δ1/\delta. If V^⋆(s0)≠∅\hat{V}^{\star}(s_0)\ne\varnothing, there exists an (ϵ,δ)(\epsilon,\delta)-optimal policy π\pi whose action distribution π(h)\pi(h) can be computed in time polynomial in the same quantities and ∣h∣\lvert h\rvert for any given history hh.

Proof. Let Nξ=∣Gξ∩B^ξ∣N_{\xi}=\lvert G_{\xi}\cap\hat{B}_{\xi}\rvert. Each application of Φ^\hat{\Phi} requires at most ∣S∣Nξ\lvert S\rvert N_{\xi} LP feasibility checks: for each state ss and grid point g∈Gξ∩B^ξ\mathbf{g}\in G_{\xi}\cap\hat{B}_{\xi}, we test whether

g∈Neigh⁡ξ(Φ(V)(s)),\mathbf{g}\in\operatorname{Neigh}_{\xi}(\Phi(V)(s)),

:::#?

using Lemma 11. The resulting sets can be represented by all accepted grid points, so each LP has polynomial size in the input and NξN_{\xi}. 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 V^⋆\widehat V^\star within O(∣S∣Nξ)O(|S|N_{\xi}) iterations. With ξ=(1−γ)min⁡{ϵ,δ/2}\xi=(1-\gamma)\min\{\epsilon,\delta/2\} and fixed γ\gamma, NξN_{\xi} is polynomial in 1/ϵ1/\epsilon and 1/δ1/\delta, establishing the first claim.

If V^⋆(s0)=∅\widehat V^\star(s_0)=\varnothing, then V⋆(s0)=∅V^\star(s_0)=\varnothing by Lemma 9, so no exactly feasible policy exists. Otherwise, select a target at the initial state by solving

v⋆∈arg⁡max⁡v∈V^⋆(s0) v1.v^\star\in\underset{v\in\widehat V^\star(s_0)}{\arg\max}\ v_1.

Since V^⋆(s0)\widehat V^\star(s_0) is a convex polytope described as the convex hull of finitely many grid points (by construction of Φ^\widehat\Phi), 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 v⋆v^\star is (ϵ,δ)(\epsilon,\delta)-achievable from s0s_0. Let π\pi 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 V⋆⊆V^⋆V^\star\subseteq\widehat V^\star, the reward component of v⋆v^\star is at least that of every exactly feasible policy. Hence π\pi is (ϵ,δ)(\epsilon,\delta)-optimal. We compute its action distributions using ActProbs⁡ξ\operatorname{ActProbs}_{\xi}, which replaces Expand⁡\operatorname{Expand} in ActProbs (Algorithm 3) with Expand⁡ξ\operatorname{Expand}_{\xi} (Algorithm 5).

The procedure takes (v⋆,h)(v^\star,h) as input and returns the action distribution π(h)\pi(h) prescribed at history hh. At each recursive step on a reachable history, the current target satisfies v∈V^⋆(s)v\in\widehat V^\star(s), so a valid output of Expand⁡ξ(v,s)\operatorname{Expand}_{\xi}(v,s) 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 LL 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 L+CL+C bits per numerator and denominator, where CC is polynomial in the input size and NξN_{\xi}. This common denominator cancels when recovering ww by dividing a weighted sum of the zz-variables by πˉ(a)\bar{\pi}(a). Since the grid coordinates are fixed, the next target also requires at most L+C′L+C' bits per numerator and common denominator, for a polynomial bound C′C' 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 ∣h∣|h| 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 ∣h∣|h|.

This yields an (ϵ,δ)(\epsilon,\delta)-optimal policy π\pi whose action distribution π(h)\pi(h) can be computed in polynomial time for any given history hh.

References

  1. [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. [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. [3]Eitan Altman. Constrained Markov decision processes. Routledge, 2021.DOI
  4. [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. [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. [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. [7]Betsy Beyer, Chris Jones, Jennifer Petoff, and Niall Richard Murphy. Site Reliability Engineering: How Google Runs Production Systems. O’Reilly Media, 2016.
  8. [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. [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
  10. [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.
  11. [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.
  12. [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.
  13. [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.
  14. [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
  15. [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.
  16. [18]Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–859, 2001.
  17. [19]Mitri Kitti. Subgame perfect equilibria in discounted stochastic games. Journal of Mathematical Analysis and Applications, 435(1):253–266, 2016.DOI
  18. [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.
  19. [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
  20. [22]Chris Murray and Geoff Gordon. Finding correlated equilibria in general sum stochastic games. Technical Report CMU-ML-07-113, Machine Learning Department, School of Computer Science, Carnegie Mellon University, 2007.
  21. [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
  22. [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 &amp; 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.
  23. [25]Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285—309, 1955.DOI
  24. [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
  25. [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
  26. [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

Paper details

vlnc:W_yk8knqhd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents