We make significant progress toward the stochastic shortest path problem with
adversarial costs and unknown transition. Specifically, we develop algorithms
that achieve $\widetilde{O}(\sqrt{S^2ADT_\star K})$ regret for the
full-information setting and $\widetilde{O}(\sqrt{S^3A^2DT_\star K})$ regret
for the bandit feedback setting, where $D$ is the diameter, $T_\star$ is the
expected hitting time of the optimal policy, $S$ is the number of states, $A$
is the number of actions, and $K$ is the number of episodes. Our work strictly
improves (Rosenberg and Mansour, 2020) in the full information setting, extends
(Chen et al., 2020) from known transition to unknown transition, and is also
the first to consider the most challenging combination: bandit feedback with
adversarial costs and unknown transition. To remedy the gap between our upper
bounds and the current best lower bounds constructed via a stochastically
oblivious adversary, we also propose algorithms with near-optimal regret for
this special case.

本文主要研究随机最短路径问题中的对手成本和未知转移，并提出了一种新的算法，可以在有限的次数内找到最优解，此外，我们还提出了一种新的算法，可以在特定情景下近似达到最优解。

在对手成本和未知转移情况下以低遗憾寻找随机最短路径

Finding the Stochastic Shortest Path with Low Regret: The Adversarial  Cost and Unknown Transition Case

In this paper, we prove some convergence results of a special case of
optimistic policy iteration algorithm for stochastic shortest path problem. We
consider both Monte Carlo and $TD(\lambda)$ methods for the policy evaluation
step under the condition that the termination state will eventually be reached
almost surely.

本文研究了乐观策略迭代算法在随机最短路径问题中的收敛性，考虑了蒙特卡罗和 $TD (\lambda)$ 方法在策略评估步骤中的应用。

乐观策略迭代在随机最短路径问题上的收敛性

On the convergence of optimistic policy iteration for stochastic  shortest path problem

In this invited contribution, we revisit the stochastic shortest path
problem, and show how recent results allow one to improve over the classical
solutions: we present algorithms to synthesize strategies with multiple
guarantees on the distribution of the length of paths reaching a given target,
rather than simply minimizing its expected value. The concepts and algorithms
that we propose here are applications of more general results that have been
obtained recently for Markov decision processes and that are described in a
series of recent papers.

本文介绍了关于随机最短路径问题的算法和策略，提供多种保证路径长度分布，而不仅是期望值最小的解决方案，并对最近在马尔科夫决策过程的研究成果进行了应用。