We propose an algorithm for deterministic continuous Markov Decision Processes with sparse rewards that computes the optimal policy exactly with no dependency on the size of the state space. The algorithm has time complexity of $O( |R|^3 \times |A|^2 )$ and memory complexity of $O( |R| \times |A| )$, where $|R|$ is the number of reward sources and $|A|$ is the number of actions. Furthermore, we describe a companion algorithm that can follow the optimal policy from any initial state without computing the entire value function, instead computing on-demand the value of states as they are needed. The algorithm to solve the MDP does not depend on the size of the state space for either time or memory complexity, and the ability to follow the optimal policy is linear in time and space with the path length of following the optimal policy from the initial state. We demonstrate the algorithm operation side by side with value iteration on tractable MDPs.

该论文提出了一种算法，用于确定性连续马尔可夫决策过程，该算法能够精确计算出最优策略，并且不依赖于状态空间的大小。此算法的时间复杂度为$O(|R|^3×|A|^2)$，空间复杂度为$O(|R|×|A|)$，并且还提出了一种伴随算法。与值迭代的算法相比，在可处理的马尔可夫决策过程中，算法的操作成果得到了一致的验证。

稀疏奖励确定性 MDP 的无记忆精确解