Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes
This provides a tighter worst-case complexity bound for a fundamental algorithm in decision-making, which is incremental but important for theoretical understanding.
The paper tackles the problem of analyzing Howard's policy iteration algorithm for deterministic Markov decision processes with mean-payoff objectives, showing that it requires Ω̃(I) iterations, an improvement from the previous sub-linear lower bound of Ω̃(√I).
Deterministic Markov Decision Processes (DMDPs) are a mathematical framework for decision-making where the outcomes and future possible actions are deterministically determined by the current action taken. DMDPs can be viewed as a finite directed weighted graph, where in each step, the controller chooses an outgoing edge. An objective is a measurable function on runs (or infinite trajectories) of the DMDP, and the value for an objective is the maximal cumulative reward (or weight) that the controller can guarantee. We consider the classical mean-payoff (aka limit-average) objective, which is a basic and fundamental objective. Howard's policy iteration algorithm is a popular method for solving DMDPs with mean-payoff objectives. Although Howard's algorithm performs well in practice, as experimental studies suggested, the best known upper bound is exponential and the current known lower bound is as follows: For the input size $I$, the algorithm requires $\tildeΩ(\sqrt{I})$ iterations, where $\tildeΩ$ hides the poly-logarithmic factors, i.e., the current lower bound on iterations is sub-linear with respect to the input size. Our main result is an improved lower bound for this fundamental algorithm where we show that for the input size $I$, the algorithm requires $\tildeΩ(I)$ iterations.