Efficient Constraint Generation for Stochastic Shortest Path Problems

Planning is an important facet of AI that gives efficient algorithms for solving current real-world problems. Stochastic Shortest Path problems (SSPs) (Bertsekas and Tsitsiklis 1991) generalise classical (deterministic) planning by introducing actions with probabilistic effects, which lets us model problems where the actions are intrinsically probabilistic. Value Iteration (VI) (Bellman 1957) is a dynamic programming algorithm that forms the basis of optimal algorithms for solving SSPs. VI finds the cost-to-go for each state, which describes the solution of an SSP. A state $s$’s cost-to-go is the minimum expected cost of reaching a goal from $s$, and similarly a action $a$’s cost-to-go is the minimum after applying $a$. VI finds the optimal cost-to-go by iteratively applying Bellman backups, which update each state’s cost-to-go with the minimal outgoing action’s cost-to-go.

LRTDP (Bonet and Geffner 2003) and iLAO^∗ (Hansen and Zilberstein 2001), the state-of-the-art algorithms for optimally solving SSPs, build on VI and offer significant speedup by using heuristics to apply Bellman backups only to promising states and pruning states that are deemed too expensive. A shortcoming of such algorithms is that each Bellman backup must consider all applicable actions. For instance, let $s$ and $a$ be a state and an applicable action, even if all successors of $a$ will be pruned because they are too expensive, a Bellman backup on $s$ still computes the $Q$-value of $a$, so these algorithms can prune unpromising states but not actions. This issue is compounded because algorithms for SSPs require arbitrarily many Bellman backups on each state $s$ to find the optimal solution, thus wasting time on computing $Q$-values for such actions many times.

This issue of computing unnecessary $Q$-values for a state $s$ is addressed by action elimination (Bertsekas 1995), which can be implemented in search algorithms to prune useless actions. Action elimination looks for pairs $(a,\widehat{a})$ of applicable actions in a state, such that a lower bound on $\widehat{a}$’s cost-to-go exceeds an upper bound on $a$’s cost-to-go, in which case $\widehat{a}$ is proved to be a useless action and can be pruned. Although domain-independent lower bounds (heuristics) can be computed efficiently, finding an efficient, domain-independent upper bound remains an open question to the best of our knowledge. This gap has limited the use of action elimination in domain-independent planning. In the context of optimal heuristic planning for SSPs, the only algorithm we are aware of that utilises action elimination to prune actions is FTVI (Dai, Weld et al. 2009). Other algorithms, such as BRTDP (McMahan, Likhachev, and Gordon 2005), FRTDP (Smith and Simmons 2006) and VPI-RTDP (Sanner et al. 2009), use upper bounds in conjunction with lower bounds to guide their search. However, unlike FTVI, they do not perform action elimination.

We present a general technique for ignoring actions that does not rely on upper bounds. In contrast to action elimination that incrementally prunes useless actions, our approach initially treats all actions as inactive, i.e., not contributing to the solution. It then iteratively adds actions to the search that are guaranteed to improve the current solution. To develop our approach, we strengthen the connections between planning and operations research by relating heuristic search to variable and constraint generation. Similar to heuristic search, variable and constraint generation enable the solving of large Linear Programs (LPs) by considering only a subset of variables and constraints. We show that algorithms such as iLAO^∗ implicitly perform constraint generation, albeit in a trivial manner, to the LP encoding of VI. Building on this, we introduce an efficient algorithm for constraint generation for SSPs that leads to inactive actions being ignored. We apply our approach to iLAO^∗ to get the novel algorithm: CG-iLAO^∗.

In our experiments, CG-iLAO^∗ solves problems up to $8\times$ and $3\times$ faster than LRTDP and iLAO^∗, respectively. CG-iLAO^∗ is faster than the others over various problem difficulties: its improvement is apparent from problems that require only 4 minutes to solve, and the improvement gap increases as problems take longer to solve. To explain this, we quantify that CG-iLAO^∗ only considers 43–65% of iLAO^∗’s total actions thus fewer actions’ costs-to-go are computed. Investigating further, we empirically show that CG-iLAO^∗ combines iLAO^∗’s efficient use of backups and LRTDP’s strong pruning capability, thereby displaying the best characteristics of both in a single algorithm.

The structure of this paper is as follows: we first introduce the background for SSPs and existing methods for solving SSPs. Second, we give a brief background to linear programming and connect linear programming techniques to heuristic search. Then we explain and motivate our novel algorithm CG-iLAO^∗ and prove its correctness. Finally, we empirically evaluate the performance of CG-iLAO^∗.

A Stochastic Shortest Path problem (SSP) (Bertsekas and Tsitsiklis 1991) is a tuple $\langle\mathsf{S},s_{0},\mathsf{G},\mathsf{A},P,C\rangle$ where: $\mathsf{S}$ is a finite set of states; $s_{0}\in\mathsf{S}$ is the initial state; $\mathsf{G}\subset\mathsf{S}$ are the goal states with $\mathsf{G}\neq\emptyset$; $\mathsf{A}$ is a finite set of actions and $\mathsf{A}(s)\subseteq\mathsf{A}$ denotes the actions applicable in state $s$; $P(s^{\prime}|s,a)$ gives the probability that applying action $a$ in state $s$ results in state $s^{\prime}$; $C(s,a)\in\mathbb{R}_{>0}$ is the cost of applying $a$ in $s$.

The states immediately reachable by applying $a$ to $s$ are called successors and are given by $\text{succ}(s,a)\coloneqq\{s^{\prime}\in\mathsf{S}:P(s^{\prime}|s,a)>0\}$. A solution to an SSP is given by a map $\pi:\mathsf{S}\to\mathsf{A}$, called a policy. A policy $\pi$ is closed w.r.t. $s_{0}$ if each state $s$ that can be reached by following $\pi$ from $s_{0}$ is either a goal or $\pi$ is defined for $s$. A policy is proper w.r.t. $s_{0}$ if it reaches the goal with probability 1 from $s_{0}$ and it is improper otherwise. An optimal policy $\pi^{*}$ is any proper policy that minimises the expected cost to reach the goal from the initial state $s_{0}$.

For simplicity, we make two standard assumptions: (i) there exists at least one proper policy w.r.t. $s_{0}$, this is called the reachability assumption; and (ii) all improper policies have infinite expected cost. A consequence of assumption (ii) is that $\mathsf{A}(s)\neq\emptyset$ for all $\mathsf{S}\setminus\mathsf{G}$. Note that we define $C$ to be strictly positive in order to avoid zero-cost cycles that would violate assumption (ii). In our experiments, we relax the reachability assumption by applying the fixed-penalty transformation of SSPs (Trevizan, Teichteil-Königsbuch, and Thiébaux 2017) resulting in a new SSP without dead ends. Other approaches for handling SSPs such as S3P (Teichteil-Königsbuch 2012) are also compatible with our approach.

An SSP’s optimal solution is uniquely represented by the optimal value function $V^{*}$, which is the unique fixed-point solution to the Bellman equations:

where $Q(s,a)\coloneqq C(s,a)+\sum_{s^{\prime}\in\mathsf{A}(a)}P(s^{\prime}|s,a)V(s)$ is known as the $Q$-value of $s$ and $a$. A (optimal) value function $V(s)$ and the associated $Q$-value $Q(s,a)$ represent the (minimum) expected cost to reach the goal from state $s$ and after executing action $a$ on state $s$, respectively. Given a value function $V$, the policy associated with it is defined as $\pi_{V}(s)\coloneqq\mathop{\rm argmin}_{a\in\mathsf{A}(s)}Q(s,a)$ and is known as the greedy policy for $V$. Ties can be broken arbitrarily thanks to assumption (ii), and for simplicity we assume some tie-breaking rules that ensure the greedy policy is unique.

The Bellman equations (1) can be iteratively solved by Value Iteration (VI) (Bellman 1957): VI starts with an arbitrary value function $V^{0}$ and computes $V^{t+1}(s)\coloneqq\min_{a\in\mathsf{A}(s)}Q(s,a)$ over all states, where $Q(s,a)$ uses the previous value function $V^{t}$. This process of computing $V^{t+1}(s)$ using $V^{t}$ is called a Bellman backup. VI is guaranteed to asymptotically converge to $V^{*}$ regardless of $V^{0}$. For practical reasons, VI is terminated at iteration $t$ when the Bellman residual $\textsc{res}(s)\coloneqq|V^{t}(s)-\min_{a\in\mathsf{A}(s)}Q(s,a)|$ is less than or equal to $\epsilon\in\mathbb{R}_{>0}$ for all $s\in\mathsf{S}$.

Given a policy $\pi$, its policy envelope $\mathsf{S}^{\pi}\subseteq\mathsf{S}$ is the set of all reachable states when following $\pi$ from $s_{0}$. Note that VI explores the complete state space $\mathsf{S}$ regardless of the optimal policy envelope $\mathsf{S}^{\pi*}$’s size. To address this shortcoming, heuristic search algorithms such as iLAO^∗ (Hansen and Zilberstein 2001) and LRTDP (Bonet and Geffner 2003) use a heuristic function $H$ to initialise $V^{0}$, which guides the exploration of the state space $\mathsf{S}$ in a way that expands as few states as possible. To find $V^{*}$, heuristic search algorithms require the heuristic to be admissible, that is, $H(s)\leq V^{*}(s)\;\forall s\in\mathsf{S}$. Often heuristics are also monotonic, which immediately implies admissibility. A value function $V$ is monotonic if $V(s)\leq\min_{a\in\mathsf{A}(s)}Q(s,a)\;\forall s\in\mathsf{S}$, and the definition is analogous for $H$. Similar to VI, heuristic search algorithms converge to $V^{*}$ asymptotically and require a practical stop criterion. This stop criterion is known as $\epsilon\text{-consistency}$ (Bonet and Geffner 2003) and is defined as:

We close this section by reviewing iLAO^∗ (Hansen and Zilberstein 2001). iLAO^∗ (alg. 1) is an iterative algorithm which works by incrementally growing a partial SSP:¹¹1Called the explicit graph in the original paper.

SSPs with terminal costs have a one-time terminal cost of $H(\widehat{g})$ that is incurred when $\widehat{g}\in\widehat{\mathsf{G}}$ is reached, so their Bellman equations are (1) with the goal case replaced by $V(\widehat{g})=H(\widehat{g})$ for all $\widehat{g}\in\widehat{\mathsf{G}}$. It is trivial to see that SSPs with terminal costs are equivalent to SSPs, and we use them to simplify our presentation. In a partial SSP $\widehat{\mathbb{S}}$, we refer to states in $\widehat{\mathsf{G}}\setminus\mathsf{G}$ as artificial goals, and we define $\widehat{\pi}_{V}$ to be the greedy policy over $V$ restricted to $\widehat{\mathsf{S}}\setminus\widehat{\mathsf{G}}$.

At each iteration, iLAO^∗ expands its partial SSP $\widehat{\mathbb{S}}$ by expanding the artificial goals reachable by $\widehat{\pi}_{V}$ into regular states. To expand $\widehat{g}\in\widehat{\mathsf{G}}\setminus\mathsf{G}$, iLAO^∗ adds $\widehat{g}$’s applicable actions to $\widehat{\mathbb{S}}$ and adds new reachable states as artificial goals (alg. 1 alg. 1). This artificial goal expansion is done to make $\widehat{\pi}_{V}$ eventually closed w.r.t. $s_{0}$ for the original SSP $\mathbb{S}$. Simultaneously, iLAO^∗ also works towards making $V$ $\epsilon\text{-consistent}$ by applying a Bellman backup to all the states reachable by $\widehat{\pi}_{V}$ (alg. 1 alg. 1). These Bellman backups are ordered by a post-order DFS traversal of $\widehat{\pi}_{V}$, so states that occur closer to artificial goals are updated first, and $s_{0}$ is updated last. Note that, when a state is expanded, it may have a successor $s$ already within the partial SSP. If this happens, the DFS in alg. 1 alg. 1 must keep traversing $\widehat{\pi}_{V}$ from $s$ to ensure the policy envelope $\mathcal{E}$ is accurate.

In the next section, we show how to interpret iLAO^∗ through the lens of Operations Research by relating it to techniques used for handling large linear programs.

SSPs can be solved by the Linear Program (LP) presented in LP 1. This LP is known as the primal LP or VI LP since it directly encodes the Bellman equations.

$\displaystyle\max_{\bm{\mathcal{V}}}\quad$ $\displaystyle\mathrlap{V_{s_{0}}}$ (LP 1) $\displaystyle\mathrm{s.t.}\quad$ $\displaystyle\mathrlap{V_{s}\leq C(s,a)+\!\sum_{\mathclap{s^{\prime}\in\mathsf{S}}}P(s^{\prime}|s,a)V_{s^{\prime}}}$ $\displaystyle\forall s\in\mathsf{S}\!\setminus\!\mathsf{G},a\!\in\!\mathsf{A}(s)$ (C1) $\displaystyle\mathrlap{V_{g}\leq 0}$ $\displaystyle\forall g\in\mathsf{G}$ (C2)

Variable generation is a technique from Operations Research that enables us to solve LPs with a large number of variables by considering only a subset of variables. Given an LP with missing variables called the Reduced Master Problem (RMP), variable generation finds a set of variables outside the RMP whose addition lets the RMP’s solution quality improve. Variable generation provides a sound and complete method to select such variables and a stop criterion that ensures the optimal solution for the RMP is also optimal for the original LP. Heuristic search algorithms, such as iLAO^∗, can be seen as a variable generation algorithm over LP 1, where each of its partial SSPs represents an RMP with the subset of variables $\{V_{s}:s\in\widehat{\mathsf{S}}\}$. For iLAO^∗, the variable selection mechanism is inherited from A^∗ and is represented by the expansion of the artificial goals reachable by $\widehat{\pi}_{V}$ (alg. 1 algs. 1 to 1): for all $s_{f}\in\mathsf{S}^{\widehat{\pi}_{V}}\cap(\widehat{\mathsf{G}}\setminus\mathsf{G})$ and $a\in\mathsf{A}(s_{f})$, we add the variables $V_{s}$ such that $s\in\text{succ}(s_{f},a)$ and $s\not\in\widehat{\mathsf{S}}$.

Constraint generation is a similar technique which enables the solving of LPs with a large (potentially infinite) number of constraints. The key idea is that the optimal solution of an LP with many constraints only makes a small number of constraints active, thus only a subset of constraints is needed to characterise this optimal solution. In constraint generation, the intermediate LPs are known as relaxed LPs since they relax the original LP by removing one or more constraints. Given a relaxed LP, constraint generation finds one or more constraints in the original LP that are violated by the optimal solution of the relaxed LP. By iteratively adding these violated constraints and re-optimising the new relaxed LP, a sequence of relaxed LPs with an increasing number of constraints is generated. When no violations are found, the optimal solution of the relaxed LP is an optimal solution for the original LP. The algorithm used to check constraint violations is called a separation oracle and the effectiveness of constraint generation relies on the availability of an efficient separation oracle for the original LP.

In the case of iLAO^∗, constraint generation adds all the actions of the expanded artificial goal (alg. 1 alg. 1) where each action $a\in\mathsf{A}(s_{f})$ added to the partial SSP implicitly represents the constraint $V(s_{f})\leq Q(s_{f},a)$. This separation oracle is computationally cheap since no checks are performed to detect if this new constraint is needed or not, at the cost that inactive constraints are unnecessarily added to the partial SSP. In the next section, we present our new algorithm that uses an efficient separation oracle that only adds violated constraints.

In iLAO^∗, as most search algorithms, each state is either unexpanded or fully expanded, i.e., either none or all of its applicable actions are considered and it is not possible to ignore just a subset of the applicable actions. We start by defining which actions can be safely ignored in a partial SSP.

An inactive action $a\in\mathsf{A}(s)\setminus\widehat{\mathsf{A}}(s)$ for $s\in\widehat{\mathsf{S}}$ represents the inactive constraint C1 for $s$ and $a$ in LP 1. Since inactive actions are not in the partial SSP and their associated constraints are inactive, adding them to the partial SSP does not change the solution and only adds overhead in the form of $Q$-value computation for sub-optimal actions.

We generalise iLAO^∗ by allowing states to be partially expanded, so these states only have a subset of actions available in the partial SSP. Under the lens of linear programming, we use constraint generation to identify and add actions that may be needed to encode the optimal solution and to ignore inactive actions. We call this algorithm Constraint-Generation iLAO^∗ (CG-iLAO^∗).

CG-iLAO^∗ is presented in alg. 2. One of the defining changes from iLAO^∗ is in CG-iLAO^∗’s expanding phase (alg. 2 alg. 2) where Partly-Expand-Fringes only expands a state with the greedy actions on $V$, rather than all the applicable actions. This introduces two challenges: (i) actions that were not added by the partial expansion may need to be added later when $V$ is more accurate; and (ii) when we add such actions, $V$ must be updated to reflect $a$’s availability. If (ii) is not addressed, the reduction to $V$ offered by $a$ is not propagated, potentially leading to a suboptimal solution since $V$ would overestimate $V^{*}$. The key insight of our algorithm is that both of these challenges are instances of constraint violation. Thus, we can solve both issues by finding which constraints are violated with a separation oracle and enforcing them in the style of constraint generation.

The trivial separation oracle checks all constraints $(s,a)$ for $s\!\in\!\widehat{\mathsf{S}}$ and $a\!\in\!\mathsf{A}(s)$ for violations; this is needlessly expensive since some non-violated constraints remain non-violated from one iteration to the next. Our separation oracle exploits this persistence between iterations by tracking changes in $V$ to compute a subset of constraints which could potentially be violated by the following rules (alg. 2 algs. 2 to 2 and alg. 2): suppose $V(s)$ is assigned $\min_{a\in\widehat{\mathsf{A}}(s)}Q(s,a)$, then there are three cases:

1. 1.

   $V(s)$ stays the same. No new constraint violations.

2. 2.

   $V(s)$ increases. The constraints $V(s)\leq Q(s,a^{\prime})$ may be violated for $(s,a^{\prime})\in\textsc{Ext-Succs}(s,\mathbb{S},\widehat{\mathbb{S}})\coloneqq\{(s,a):a\in\mathsf{A}(s)\setminus\widehat{\mathsf{A}}(s)\}$. Note that if $(s,a^{\prime})$ is already inside $\widehat{\mathbb{S}}$, i.e., $a^{\prime}\in\widehat{\mathsf{A}}(s)$, its constraint can not be violated since $V(s)\leftarrow\min_{a\in\widehat{\mathsf{A}}(s)}Q(s,a)\leq Q(s,a^{\prime})$.

3. 3.

   $V(s)$ decreases. The only constraints that may be violated are $V(s^{\prime})\leq Q(s^{\prime},a^{\prime})$ for $(s^{\prime},a^{\prime})\in\textsc{Preds}(s,\mathbb{S})\coloneqq\{(s^{\prime},a^{\prime}):s\in\text{succ}(s^{\prime},a^{\prime}),a^{\prime}\in\mathsf{A}(s^{\prime})\}$.

We store potential violations in $\Gamma$, i.e., if $V(s)$ increases, the elements of $\textsc{Ext-Succs}(s,\mathbb{S},\widehat{\mathbb{S}})$ are added to $\Gamma$ (alg. 2 alg. 2); and if $V(s)$ decreases, the elements of $\textsc{Preds}(s,\mathbb{S})$ are added to $\Gamma$ (alg. 2 alg. 2). Elements are removed from $\Gamma$ after they are checked. As we prove later in this section, checking constraints in $\Gamma$ is sufficient to find any constraint violations.

CG-iLAO^∗ fixes a violated constraint $(s,a)$ by setting $V(s)\leftarrow Q(s,a)$ (alg. 2 alg. 2). This change in $V$ may create a new violation in another state, so we must track such potential violations in the same way as before. This ensures that all constraint violations are tracked and fixed eventually before termination.

Note that $V(s)$ may decrease after an update (case 3 of the constraint violations) in CG-iLAO^∗ even if the heuristic used is monotonic. This is a departure from all other algorithms based on Bellman backups where $V$ is guaranteed to be monotonically non-decreasing during their executions when initialised with a monotonic heuristic. To illustrate a scenario where $V$ decreases in CG-iLAO^∗, consider the SSP in fig. 1 where $H$ is monotonic and represented inside nodes. The first iterations of CG-iLAO^∗ applied to this SSP are:

1. Iter. 1

   expands $s_{0}$.

2. Iter. 2

   partly expands $s_{1}$ with $a_{1}$.

3. Iter. 3

   expands $s_{2}$ with $a_{2}$ and, after CG-Backups, we have $V(s_{2})=3$, $V(s_{1})=4$, $V(s_{0})=5$ and $\Gamma=\{(s_{1},a^{\prime}_{1})\}$. Since $\Gamma\neq\emptyset$, Fix-Constrs verifies that $(s_{1},a^{\prime}_{1})$ is currently better than the existing action $a_{1}$ for $s_{1}$, so $a^{\prime}_{1}$ is added to $\widehat{\mathsf{A}}(s_{1})$ and $V(s_{1})$ is changed from 4 to 3. Recall that $V(s_{0})=5$, so when $V(s_{1})$ is updated to $3$, $\{s_{0},a_{0}\}$ is inserted into $\Gamma$, and no further changes are made in this iteration.

4. Iter. 4

   expands $s_{3}$ and CG-Backups reduces $V(s_{0})$ from 5 to 4, so $V$ has been decreased by CG-Backups.

CG-iLAO^∗ generalises iLAO^∗ by using a more precise separation oracle that only adds violated constraints, which translates to CG-iLAO^∗ ignoring inactive actions. For a state $s$, any action that has been ignored and left out of the partial SSP $\widehat{\mathbb{S}}$ is not considered by a Bellman backup of $s$ in $\widehat{\mathbb{S}}$, so such actions’ $Q$-values are not computed. However, CG-iLAO^∗ needs to compute additional $Q$-values in its separation oracle to check violations. As our experiments in section 5 show, the $Q$-values saved by ignoring inactive actions outweigh the additional $Q$-values in the separation oracle, which lets CG-iLAO^∗ outperform iLAO^∗.

To close the section, we prove that CG-iLAO^∗: (i) terminates (thm. 1); (ii) tracks all constraint violations (lem. 1); and (iii) returns an $\epsilon\text{-consistent}$ value function (thm. 2). Thus, CG-iLAO^∗ is optimal for SSPs.

In this section we empirically compare CG-iLAO^∗ to two state-of-the-art optimal heuristic search planners: iLAO^∗ (Hansen and Zilberstein 2001) and LRTDP (Bonet and Geffner 2003). We also compared CG-iLAO^∗ against FTVI (Dai, Weld et al. 2009), the only algorithm we are aware of that uses action elimination to prune actions, but it is uncompetitive and FTVI’s results are reported in section 7. We consider the following admissible heuristics: h-max ($h^{\text{max}}$); lm-cut ($h^{\text{lmc}}$) (Helmert and Domshlak 2009); and h-roc ($h^{\text{roc}}$) (Trevizan, Thiébaux, and Haslum 2017). As in (Trevizan, Thiébaux, and Haslum 2017), we use $h^{\text{roc}}$ with $h^{\text{max}}$ as a dead-end detection mechanism for problems with dead ends. We use $\epsilon=0.0001$ and convert SSPs into dead-end free SSPs (Trevizan, Teichteil-Königsbuch, and Thiébaux 2017) with a penalty of $D=500$ for all domains except Parc Printer variants where $D=10^{7}$ due to the large cost of single actions.

On all problems, we collected 50 runs with different random seeds for each combination of planner and heuristic. We refer to a problem paired with a fixed seed as an instance. All runs have a cutoff of 30 minutes of CPU time and 8GB of memory. The experiments were conducted in a cluster of Intel Xeon 3.2 GHz CPUs and each run used a single CPU core. The LP solver used for computing $h^{\text{roc}}$ was CPLEX version 20.1. We consider the following domains:

Building on existing connections between operations research and planning, we presented a new interpretation of heuristic search on SSPs as solving LPs using variable and constraint generation. We exploit this equivalence to introduce a new and efficient separation oracle for SSPs, which enables a search algorithm to selectively add actions when they are deemed necessary to find the optimal solution. This addresses the shortcoming of state-of-the-art algorithms that add all applicable actions during state expansion, with no mechanism for ignoring actions that will not contribute to the solution. Using this principle, we generalised iLAO^∗ into a new optimal heuristic search algorithm CG-iLAO^∗. Empirical evaluation showed that CG-iLAO^∗’s ability to consider a subset of actions results in significant savings in the number of $Q$-values computed, which in turn reduces the runtime of the algorithm compared to the state-of-the-art.

Regarding related work, LP 1 has been approximated for factored MDPs to get a more compact LP, called the approximate LP (ALP). Schuurmans and Patrascu (2001) apply constraint generation to the ALP; their separation oracle has a similar condition for adding constraints as CG-iLAO^∗; however, it checks for the condition naively, which is only practical on the compact ALP offered by factored MDPs, and is infeasible for SSPs. Constraint generation lends itself well to complex planning problems where a relaxation can be efficiently solved and constraint violations by the relaxed solution can be efficiently detected, e.g., in multiagent planning (Calliess and Roberts 2021) and metric hybrid factored planning in nonlinear domains (Say and Sanner 2019). For POMDPs, an LP with constraint generation can be used to prune unneeded vectors from the set of vectors used to represent the value function (Walraven and Spaan 2017). In all these works, the separation oracle either naively checks all possible constraints or relies on sampling to find violations.

As future work, we aim to expand the application of CG-iLAO^∗ to more complex models that can benefit from our iterative method of generating applicable actions. Models with imprecise parameters, such as MDPIPs and MDPSTs (White III and Eldeib 1994; Trevizan, Cozman, and Barros 2007), are suitable candidates for our approach since they have a minimax semantics for the Bellman equations. In this minimax semantics, the value function minimises the expected cost-to-go assuming that an adversary aims to maximise the cost-to-go by selecting the values of the imprecise parameters. As a result, computing $Q(s,a)$ in these models requires solving a maximisation problem; therefore, ignoring inactive actions could lead to significant improvements in performance.

Other suitable models include SSPs with PLTL constraints (Baumgartner, Thiébaux, and Trevizan 2018; Mallet, Thiébaux, and Trevizan 2021) in which both the state space and action space are augmented to keep track of constraint violations. In these models, the concept of inactive actions can be extended to also prevent adding actions that lead to constraint violations to their partial problems. The methods presented in this paper may also be applicable to model checking more broadly. In particular, there has been work investigating how to use heuristics to guide the search for probabilistic reachability (Brázdil et al. 2014), in which action elimination is applicable.

We thank the anonymous reviewers for their feedback. This research/project was undertaken with the assistance of resources and services from the National Computational Infrastructure (NCI), which is supported by the Australian Government.

We revisit the key questions of our experiments section by presenting additional results and explaining them.