Photo from wikipedia
In this paper, we study discrete infinite-time horizon undiscounted finite-state and finite-action $$\textit{MDP}$$MDPs with average cost criteria. Based on a combinatorial approach, we show that completely ergodic $$\textit{MDP}$$MDPs can be… Click to show full abstract
In this paper, we study discrete infinite-time horizon undiscounted finite-state and finite-action $$\textit{MDP}$$MDPs with average cost criteria. Based on a combinatorial approach, we show that completely ergodic $$\textit{MDP}$$MDPs can be reduced to a generalized minimum cost circulation problem with equality constraints. We show that although the reduced problem has the same complexity as the original one, it enables a linear programming problem with an underlying network structure for which strongly polynomial algorithms can be developed.
Journal Title: Optimization Letters
Year Published: 2017
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!