In value iteration, we must define an updated value function V t +1 as a refinement of the previous iteration's value function, V t . States become forbidden in V t +1 if they violate any constraints directly or if any of their successors are forbidden according to V t .

States satisfy requirements if they satisfy them directly or if all of their successors satisfy the requirement.  To simplify the following expressions, we define S ′ to be the set of all successors:  { s ′ ∈ S | M g s ′ > 0} . The following expression provides the precise definition of this iterative step:

$$V^{t+1}(s)\leftarrow\max_{a\in A}\left\langle\bigvee_{c\in C_{f_{\delta}}}c(s)\vee\bigvee_{c\in C_{f_{\delta}}}c(s,a)\vee\bigvee_{s\in S^{\prime}}F^{\prime},\right.$$ $$\left.\left\{c\in C_{\tau}\left|c(s)\right\}\right\}\cup\left\{c\in C_{\tau a}\left|c(s,a)\right.\right\}\cup\bigcap_{V^{t}\left(s^{\prime}\right)=\left\{F^{\prime},N^{\prime},U^{\prime}\right\},s^{\prime}\in S^{\prime}}\right.$$ $$\left.R_{S}(s)+R(s,a)+\sum_{V^{t}\left(s^{\prime}\right)=\left\{F^{\prime},N^{\prime},U^{\prime}\right\},s^{\prime}\in S}\right.\tag{20}$$

Just as in standard value iteration, this iterative step specifies a maximization over all possible choices of action. However, with our two additional components to represent the value of the strategy with respect to the constraints, we no longer have an obvious comparison function to use when evaluating candidate actions. Therefore, we perform the maximization using the following preference ordering, where x ← y means that y is preferable to x :

$$\begin{array}{r c l}{{\langle t,N,U\rangle}}&{{\prec}}&{{\langle f,N^{\prime},U^{\prime}\rangle}}\\ {{\langle F,N,U\rangle}}&{{\prec}}&{{\langle F,N^{\prime}\supset N,U^{\prime}\rangle}}\\ {{\langle F,N,U\rangle}}&{{\prec}}&{{\langle F,N,U^{\prime}>U\rangle}}\end{array}$$

In other words, satisfying a forbidden constraint takes highest priority, satisfying more requiring constraints is second, and increasing expected value is last. We define the optimal action, P(s), as the action, a, for which the final V(s) expression above is maximized.

Despite the various set operations in Equation 20, the time complexity of this iteration step exceeds that of standard value iteration by only a linear factor, namely the number of constraints, [Cfs] + [Cfa] + [Cfs] + [Cra]. The efficiency derives from the fact that the constraints are satisfied /violated independently of each other.  The determination of whether a single constraint is satisfied/violated requires no more time than that of standard value iteration, hence the overall linear increase in time complexity.

Because expected value has the lowest priority, we can separate the iterative step of Equation 20 into two phases: constraint propagation and value iteration.  During the constraint-propagation phase, we compute only the first two components of our value function, ( F, N, ).  The value-iteration phase computes the third component, ( , , U ), as in standard value iteration. However, we can ignore any state/action pairs that, according to the results of constraint propagation, violate a forbidding constraint ((t,N, )) or requiring constraint ( { f, N ⊂ C r s ∪ C r α , } ). Because of the component-wise independence of Equation 20, the two-phase algorithm computes an identical value function as the original, single-phase version (over state/action pairs that satisfy all constraints).

In the rest of this Appendix we provide a proof of the correctness of the modified value iteration policy. Given a policy, P , constructed according to the above algorithm, we must