Current methods for solving Stochastic Shortest Path Problems (SSPs) find
states' costs-to-go by applying Bellman backups, where state-of-the-art methods
employ heuristics to select states to back up and prune. A fundamental
limitation of these algorithms is their need to compute the cost-to-go for
every applicable action during each state backup, leading to unnecessary
computation for actions identified as sub-optimal. We present new connections
between planning and operations research and, using this framework, we address
this issue of unnecessary computation by introducing an efficient version of
constraint generation for SSPs. This technique allows algorithms to ignore
sub-optimal actions and avoid computing their costs-to-go. We also apply our
novel technique to iLAO* resulting in a new algorithm, CG-iLAO*. Our
experiments show that CG-iLAO* ignores up to 57% of iLAO*'s actions and it
solves problems up to 8x and 3x faster than LRTDP and iLAO*.

利用规划和运筹学的新框架，解决了随机最短路径问题中冗余计算的问题，提出了一种有效的约束生成技术，应用到了新算法 CG-iLAO*，实验证明 CG-iLAO * 相较于 LRTDP 和 iLAO * 在解决问题时速度提高了 8 倍和 3 倍，并忽略了 iLAO * 的多达 57% 的动作。

随机最短路径问题的高效约束生成

Efficient Constraint Generation for Stochastic Shortest Path Problems

Solving general Markov decision processes (MDPs) is a computationally hard
problem. Solving finite-horizon MDPs, on the other hand, is highly tractable
with well known polynomial-time algorithms. What drives this extreme disparity,
and do problems exist that lie between these diametrically opposed
complexities? In this paper we identify and analyse a sub-class of stochastic
shortest path problems (SSPs) for general state-action spaces whose dynamics
satisfy a particular drift condition. This construction generalises the
traditional, temporal notion of a horizon via decreasing reachability: a
property called reductivity. It is shown that optimal policies can be recovered
in polynomial-time for reductive SSPs -- via an extension of backwards
induction -- with an efficient analogue in reductive MDPs. The practical
considerations of the proposed approach are discussed, and numerical
verification provided on a canonical optimal liquidation problem.

本文通过分析满足特定漂移条件的随机最短路径问题的子类，引入降低可达性的概念，提出了一种构建并求解随机最短路径问题和马尔可夫决策过程的多项式时间算法，经实验验证效果良好。

简化的马尔可夫决策过程：超出时间范围的视角

Reductive MDPs: A Perspective Beyond Temporal Horizons

Several goal-oriented problems in the real-world can be naturally expressed
as Stochastic Shortest Path Problems (SSPs). However, the computational
complexity of solving SSPs makes finding solutions to even moderately sized
problems intractable. Currently, existing state-of-the-art planners and
heuristics often fail to exploit knowledge learned from solving other
instances. This paper presents an approach for learning \emph{Generalized
Policy Automata} (GPA): non-deterministic partial policies that can be used to
catalyze the solution process. GPAs are learned using relational, feature-based
abstractions, which makes them applicable on broad classes of related problems
with different object names and quantities. Theoretical analysis of this
approach shows that it guarantees completeness and hierarchical optimality.
Empirical analysis shows that this approach effectively learns broadly
applicable policy knowledge in a few-shot fashion and significantly outperforms
state-of-the-art SSP solvers on test problems whose object counts are far
greater than those used during training.

本文提出了一种利用关系型特征抽象学习广义策略自动机（Generalized Policy Automata，GPA）来解决随机最短路径（Stochastic Shortest Path Problems，SSPs）问题的方法，该方法通过少量数据训练便能学到适用于各种相关问题的泛化的非确定性部分策略（partial policy），并在针对数量超过训练数据的问题上显著优于现有的 SSP 求解器。