Article ID: | iaor20162576 |
Volume: | 67 |
Issue: | 4 |
Start Page Number: | 270 |
End Page Number: | 276 |
Publication Date: | Jul 2016 |
Journal: | Networks |
Authors: | Boyles Stephen D, Rambha Tarun |
Keywords: | combinatorial optimization, stochastic processes, programming: markov decision |
The online shortest path problem is a type of stochastic shortest path problem in which certain arc costs are revealed en route, and the path is updated accordingly to minimize expected cost. This note addresses the open problem of determining whether a problem instance admits a finite optimal solution in the presence of negative arc costs. We formulate the problem as a Markov decision process and show ways to detect such instances in the course of solving the problem using standard algorithms such as value and policy iteration.