Math Conjectures

Strongly polynomial finite Markov decision processes

OPENMajorOpen problemProposed c. 1983 · Standard version

Canonical statement

There is a strongly polynomial algorithm which, given a finite state set SS, finite nonempty action sets AsA_s, rational transition probabilities p(t∣s,a)p(t\mid s,a), rational rewards r(s,a)r(s,a), and rational 0<γ<10<\gamma<1, returns a stationary deterministic policy maximizing
Esπ ⁣[∑k=0∞γkr(Sk,π(Sk))] \mathbf E_s^\pi\!\left[\sum_{k=0}^{\infty}\gamma^k r(S_k,\pi(S_k))\right]
simultaneously for every initial state ss, using a number of arithmetic operations polynomial only in ∣S∣+∑s∣As∣|S|+\sum_s|A_s| and maintaining intermediate encoding lengths polynomial in the input length.
View source LaTeX
There is a strongly polynomial algorithm which, given a finite state set \(S\), finite nonempty action sets \(A_s\), rational transition probabilities \(p(t\mid s,a)\), rational rewards \(r(s,a)\), and rational \(0<\gamma<1\), returns a stationary deterministic policy maximizing
\[
\mathbf E_s^\pi\!\left[\sum_{k=0}^{\infty}\gamma^k r(S_k,\pi(S_k))\right]
\]
simultaneously for every initial state \(s\), using a number of arithmetic operations polynomial only in \(|S|+\sum_s|A_s|\) and maintaining intermediate encoding lengths polynomial in the input length.
OR-002:[Ye2011MDP][PostYe2015DeterministicMDP][DadushEtAl2024TwoNonzero]
Operations researchMathematical optimizationGame theory and mathematical economics

Notes

A finite discounted Markov decision process asks for a stationary deterministic policy maximizing the expected discounted reward simultaneously from every initial state. Such a policy always exists and can be computed in polynomial time via linear programming, since the discounted optimality conditions are linear. The problem, which dates in spirit to the early-1980s literature on strongly polynomial algorithms, asks whether an optimal policy can be found using a number of arithmetic operations polynomial in the numbers of states and actions alone, independently of the bit sizes of the rewards, transition probabilities, and discount factor γ\gamma.

Important special cases are settled. Ye proved that the simplex method and policy iteration are strongly polynomial when the discount factor is fixed [Ye2011MDP], and Post and Ye showed that the simplex method is strongly polynomial for deterministic Markov decision processes even with the discount supplied as input [PostYe2015DeterministicMDP]. A recent strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column resolves closely related linear-programming structure [DadushEtAl2024TwoNonzero].

For general stochastic processes with γ\gamma part of the input, and for the average-reward criterion, the question remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.