# Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Run Time

### Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Run Time

The nonlinear Bellman equation = linear programming problem: Primal-Dual LP

Primal LP

(1)

Dual LP

(2)

Minmax Problem

(3)