

![0_image_0.png](0_image_0.png)

both. We also present a detailed proof that our algorithm's output is the correct strategy
(i.e., the strategy with the highest expected utility, subject to the user-specified constraints).

In the standard MDP value iteration algorithm, the value of a strategy in a particular state is a single number, an expected utility U . With the addition of our two types of constraints, this value is now a tuple (F, N, U). F represents a strategy's ability to satisfy the forbidding constraints; therefore, it is a boolean indicating whether the state is forbidden or not. N represents a strategy's ability to satisfy the necessary constraints; therefore, it is the set of requiring constraints that will be satisfied. As in traditional value iteration, U is the expected reward. For instance, if the value of a state, V(s) = (true, {c,,}, 0.3),
then executing the policy from state s will achieve an expected value of 0.3 and will satisfy required-state constraint crx. However, it is not guaranteed to satisfy any other requiredstate, nor any required-action, constraints. In addition, s is forbidden, so there is a nonzero probability of violating a forbidden-action or forbidden-state constraint. We do not record which forbidding constraints the policy violates, since violating any one of them is equally bad. We do have to record which requiring constraints the policy satisfies, since satisfying all such constraints is preferable to satisfying only some of them. Therefore, the size of the value function grows linearly with the number of requiring constraints, but is independent of the number of forbidding constraints.

Following the form of standard value iteration, we initialize the value function over states by considering the immediate value of the strategy in the given state, without any lookahead. More precisely:

$$V^{0}(s)\leftarrow\left\langle\bigvee_{c\in C_{fs}}c(s),\left\{c\in C_{Ts}|c(s)\right\},R_{S}(s)\right\rangle\tag{19}$$

Thus, the state s is forbidden if any forbidden-state constraints immediately apply, and it satisfies those required-state constraints that immediately apply. As in standard value iteration, the expected utility is the value of the reward function in the state.