Algorithms for solving stochastic discrete optimal control problems on networks

In this paper we consider the stationary stochastic discrete optimal control problem with average cost criterion. We formulate this problem on networks and propose polynomial time algorithms for determining the optimal control by using a linear programming approach.