Optimizing over a Restricted Policy Class in Markov Decision Processes
This addresses the challenge of optimizing policies in complex systems where safe or good policies exist, but it is incremental as it builds on known base policies.
The paper tackles the problem of finding an optimal policy in a Markov decision process when restricted to the convex hull of known base policies, showing it is NP-hard but providing an efficient algorithm under a condition of large overlap in occupancy measures, with running time linear in states and polynomial in base policies.
We address the problem of finding an optimal policy in a Markov decision process under a restricted policy class defined by the convex hull of a set of base policies. This problem is of great interest in applications in which a number of reasonably good (or safe) policies are already known and we are only interested in optimizing in their convex hull. We show that this problem is NP-hard to solve exactly as well as to approximate to arbitrary accuracy. However, under a condition that is akin to the occupancy measures of the base policies having large overlap, we show that there exists an efficient algorithm that finds a policy that is almost as good as the best convex combination of the base policies. The running time of the proposed algorithm is linear in the number of states and polynomial in the number of base policies. In practice, we demonstrate an efficient implementation for large state problems. Compared to traditional policy gradient methods, the proposed approach has the advantage that, apart from the computation of occupancy measures of some base policies, the iterative method need not interact with the environment during the optimization process. This is especially important in complex systems where estimating the value of a policy can be a time consuming process.