5
$\begingroup$

I'm new to the field of sequential decision making. I got intrigued by a stochastic shortest path problem, described in Chapter 5 of this book by W. Powell.

Consider the following stochastic shortest path problem:

  • Undirected graph $G(V,E)$, a source vertex $s$, and a destination vertex $t$
  • When located at some node $i\in V$, the travel times from $i$ to its neighboring nodes are revealed; travel times on the other edges are uncertain (stochastic).
  • We are interested in finding the shortest path from $s$ to $t$.

To solve this problem, the book sketches the following approximate DP approach:

  1. With every node $i\in V$, we associate a value $v_i$, representing the expected cost of reaching destination $t$ from $i$, where $v_t=0$.
  2. Let $\hat{c}_{ij}$ be a travel time realization on edge $(i,j)$. When located in node $i$, and deciding to which neighboring node $j^*$ to move next, we pick $j^*=\arg \min_{j:(i,j)\in E}\hat{c}_{ij}+v_j$. So, starting at node $s$, we move to a neighboring node $j$ for which the cost $\hat{c}_{sj}+v_j$ is minimum. We repeat until we reach node $t$.

Clearly, the challenge lies in determining $v_i$ for $i\in V$ efficiently. The book outlines the following iterative approach.

  1. Initialize $v_t=0$, and $v_i$ for $i\in V\setminus \{t\}$ to some positive value (e.g we can set all arc costs to their expected values, run Dijkstra to compute the shortest paths from $t$ to all other nodes and use the resulting costs to initialize $v_i$).
  2. Following an iterative process, we are going to learn the values $v_i$ for $i\in V$. Assume that $\hat{c}_{ij}^n$ is the travel time realization of edge $(i,j)$ obtained in the nth iteration. At every iteration, we step through the network, starting at node $i=s$. An iteration ends when we reach node $t$. While stepping through the network, when located at some node $i$, we determine the next node j* to move to by: $j^*=\arg \min_{j:(i,j)\in E}\hat{c}_{ij}^n+v_j$. Let $v'_i=\hat{c}_{ij^*}^n+v_{j*}$. Update $v_i$ by setting $v_i=(1-\alpha)v_i+\alpha v'_i$, and set $i=j^*$. Here, $\alpha$ is a predefined parameter that determines the learning rate. Continue stepping until $i=t$.

An implementation of the above algorithm is given here.

Approach related questions:

  1. In the example implementation, the authors walk from $s$ to $t$. Alternatively, we could have walked backwards, from $t$ to $s$. Does this matter?
  2. In the implementation, I noticed that while walking from $s$ to $t$, the algorithm does not track (a) which vertices have already been visited, or (b) how many segments we have traversed already. Shouldn't one include some sort of check to prevent cycling (e.g. in a walk from $s$ to $t$, you don't want to revisit the same vertex multiple times)?

General questions relating to the above solution framework to learn $v_i$ by iteratively sampling a path through the network:

  1. How does one prove for such an algorithm, whether, after $n$ iterations, the algorithm converges to some steady state? Clearly, it would be undesirable if the algorithm would start to diverge from the true values of $v_i$. Similarly, we don't want the algorithm to alternate between 2 solutions, i.e. in the kth iteration we would update the $v_i$ values, and in the (k+1)th iteration we would revert those changes back to the solution we found in iteration k.
  2. Assuming the algorithm converges, how do we establish the quality of the final solution (i.e. are the learned values of $v_i$ a good representation of the expected costs)?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.