If you are sometimes called upon directing a random walk in a directed graph, how should you direct it so as to maximize the probability it goes where you want?

More specifically, suppose you are given a directed graph $G$ with edge weights, two designated vertices $s$ and $t$, and a subset of the vertices $S$. The edges weights represent the transition probabilities of the random walk, the vertex $s$ the start, the vertex $t$ the target, and the set $S$ the set of switches. You are guaranteed that the weights on the out-edges of any node are non-negative and sum to one, that $t$ is absorbing (i.e., $t$ has one out-edge directed towards itself), and that the out-degree of any vertex in $S$ is exactly two.

A random walk is taken on $G$, starting at $s$. For any given vertex not in $S$, the weight on an out-edge is the probability that the walk will travel in that direction. Every time that the walk reaches a switch (a vertex in $S$), you are allowed to choose which of the two edges the walk will travel along (and you are allowed probabilistic strategies). How should you direct the path if you want to maximize the probability that the walk ends up at your target $t$?

I am most interested in this as an algorithmic question. How fast can you find the optimal strategy with respect to the size of the graph? My specific application has about 100 switches among 200 vertices in a fairly sparse graph (say out-degree bounded above by 6).

But we can also ask purely mathematical questions. For example, my intuition says (and I can hand-wave a proof) that there exists an optimal strategy that is deterministic in the sense that it always chooses the same direction for a given switch and this direction does not depend on the initial vertex $s$. Is this actually true?

Also, is there a sense in which the optimal strategy needs to "coordinate" among the switches? That is, is there a local optimum that is not a global optimum?

If you are sometimes called upon directing a random walk in a directed graph, how should you direct it so as to maximize the probability it goes where you want?

Formal statement

More specifically, suppose you are given a directed graph $G$ with edge weights, two designated vertices $s$ and $t$, and a subset of the vertices $S$. The edges weights represent the transition probabilities of the random walk, the vertex $s$ the start, the vertex $t$ the target, and the set $S$ the set of switches. You are guaranteed that the weights on the out-edges of any node are non-negative and sum to one, that $t$ is absorbing (i.e., $t$ has one out-edge directed towards itself), and that the out-degree of any vertex in $S$ is exactly two.

A random walk is taken on $G$, starting at $s$. For any given vertex not in $S$, the weight on an out-edge is the probability that the walk will travel in that direction. Every time that the walk reaches a switch (a vertex in $S$), you are allowed to choose which of the two edges the walk will travel along (and you are allowed probabilistic strategies). How should you direct the path if you want to maximize the probability that the walk ends up at your target $t$?

Questions

I am most interested in this as an algorithmic question. How fast can you find the optimal strategy with respect to the size of the graph? My specific application has about 100 switches among 200 vertices in a fairly sparse graph (say out-degree bounded above by 6).

But we can also ask purely mathematical questions. For example, my intuition says (and I can hand-wave a proof) that there exists an optimal strategy that is deterministic in the sense that it always chooses the same direction for a given switch and this direction does not depend on the initial vertex $s$. Is this actually true?

Also, is there a sense in which the optimal strategy needs to "coordinate" among the switches? That is, is there a local optimum that is not a global optimum?

Notes

A note on connectivity: we may assume that the graph is sufficiently connected. If not, we can identify all vertices that cannot be reached from the start node, as well as all of those that cannot reach the target node, into a single, absorbing fail state. We may assume the start node is not the fail node.