Geometric Policy Iteration for Markov Decision Processes
Recently discovered polyhedral structures of the value function for finite
state-action discounted Markov decision processes (MDP) shed light on
understanding the success of reinforcement learning. We investigate the value
function polytope in greater detail and characterize the polytope boundary
using a hyperplane arrangement. We further show that the value space is a union
of finitely many cells of the same hyperplane arrangement and relate it to the
polytope of the classical linear programming formulation for MDPs. Inspired by
these geometric properties, we propose a new algorithm, Geometric Policy
Iteration (GPI), to solve discounted MDPs. GPI updates the policy of a single
state by switching to an action that is mapped to the boundary of the value
function polytope, followed by an immediate update of the value function. This
new update rule aims at a faster value improvement without compromising
computational efficiency. Moreover, our algorithm allows asynchronous updates
of state values which is more flexible and advantageous compared to traditional
policy iteration when the state set is large. We prove that the complexity of
GPI achieves the best known bound $\mathcal{O}\left(\frac{|\mathcal{A}|}{1 -
\gamma}\log \frac{1}{1-\gamma}\right)$ of policy iteration and empirically
demonstrate the strength of GPI on MDPs of various sizes.