linear programming for MDPs

Dynamic programming is not the only exact way to solve a known MDP. The Bellman optimality equations turn out to define a linear program — an optimization with a linear objective and linear constraints — so you can hand the whole MDP to a standard LP solver and read the optimal values straight off the solution. It is a different lens on the same answer.

You minimize the sum of state values subject to the constraint that each value is at least the expected reward-plus-discounted-successor for every action. At the optimum those inequalities tighten to equalities exactly where the optimal actions sit, recovering the optimal value function. The dual LP has a lovely reading: its variables are the long-run state–action visitation frequencies of the optimal policy. LP solves MDPs in polynomial time and underpins richer ideas such as constrained MDPs.