  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.
