This paper studies Stochastic Shortest Path (SSP) problems in known and
unknown environments from the perspective of convex optimisation. It first
recalls results in the known parameter case, and develops understanding through
different proofs. It then focuses on the unknown parameter case, where it
studies extended value iteration (EVI) operators. This includes the existing
operators used in Rosenberg et al. [26] and Tarbouriech et al. [31] based on
the l-1 norm and supremum norm, as well as defining EVI operators corresponding
to other norms and divergences, such as the KL-divergence. This paper shows in
general how the EVI operators relate to convex programs, and the form of their
dual, where strong duality is exhibited.
This paper then focuses on whether the bounds from finite horizon research of
Neu and Pike-Burke [21] can be applied to these extended value iteration
operators in the SSP setting. It shows that similar bounds to [21] for these
operators exist, however they lead to operators that are not in general
monotone and have more complex convergence properties. In a special case we
observe oscillating behaviour. This paper generates open questions on how
research may progress, with several examples that require further examination.

本文从凸优化的角度研究了已知和未知环境中的随机最短路径问题，回顾了已知参数情况下的结果，并通过不同的证明发展了理解。其后专注于未知参数情况，在此基础上研究了扩展值迭代算子，包括现有算子和定义了其他算子。本文表明了 EVI 算子与凸规划的关系及其对偶形式，同时提出了一些进一步研究的问题。