Markov Decision Problems (MDPs) are a widely-used abstraction of sequential decision-making. A policy specifies an action to take from each state of the MDP. Every MDP has an optimal policy, which maximises the expected long-term reward from each starting state. A well-known approach to compute an optimal policy for a given MDP is by solving an induced Linear Program (LP). This paper establishes the computational efficiency of a family of “Algebraic Simplex” (AS) algorithms for solving these induced LPs. Unlike geometric methods that rely on quantities such as “value”, “gain”, or “flux”, AS algorithms query policies sequentially for the discrete set of locally-improving state-action pairs. We provide upper bounds on the complexity of AS algorithms in three settings: (1) when there are many more states than actions, (2) when there are many more actions than states, and (3) when transitions are deterministic. For all three cases, we furnish AS algorithms with running-time upper bounds that are within a polynomial factor of the tightest known yet across all algorithms. These results demonstrate that the use of geometric information and random access memory do not contribute substantively to the established efficiency of state-of-the-art algorithms.