Programowanie liniowe lub LP, o którym wspomniano pokrótce w Rozdziale 4 (str. 139), jest ogólnym podejściem do formułowania problemów optymalizacji z ograniczeniami, a dostępnych jest wiele przemysłowych rozwiązań LP. Biorąc pod uwagę, że równania Bellmana zawierają wiele sum i maksimów, być może nie jest zaskakujące, że rozwiązywanie MDP można sprowadzić do rozwiązania odpowiednio sformułowanego programu liniowego. Podstawową ideą tego sformułowania jest rozważenie jako zmiennych w LP użyteczności U(s) każdego stanu s, zwracając uwagę, że użyteczności dla optymalnej polityki są najwyższymi osiągalnymi użytecznościami, które są zgodne z równaniami Bellmana. W języku LP oznacza to, że staramy się zminimalizować U (s) dla wszystkich podlegających nierówności
dla każdego stanu i każdego działania Tworzy to połączenie programowania dynamicznego z programowaniem liniowym, dla którego algorytmy i kwestie złożoności zostały dogłębnie zbadane. Na przykład z faktu, że programowanie liniowe jest rozwiązywalne w czasie wielomianu, można wykazać, że MDP można rozwiązać w czasie wielomianu w liczbie stanów i akcji oraz liczbie bitów wymaganych do określenia modelu. W praktyce okazuje się, że solwery LP rzadko są tak wydajne, jak programowanie dynamiczne w rozwiązywaniu MDP. Co więcej, czas wielomianowy może brzmieć dobrze, ale liczba stanów jest często bardzo duża. Na koniec warto pamiętać, że nawet najprostsze i najbardziej niedoinformowane algorytmy wyszukiwania działają w czasie liniowym pod względem liczby stanów i akcji.