Optimizing over a Restricted Policy Class in Markov Decision Processes

Ershad Banijamali, Yasin Abbasi-Yadkori, Mohammad Ghavamzadeh, Nikos VlassisarXiv 2018 · OpenReview

TL;DR

This paper tackles the challenge of finding the best policy within a limited set of options (a "restricted policy class") in Markov Decision Processes (MDPs), especially when we have a few good "base policies." They prove this problem is NP-hard but introduce an efficient algorithm that finds near-optimal solutions when the base policies' "occupancy measures" (how often states and actions are visited) overlap significantly. This new approach offers computational advantages over traditional methods, particularly in complex systems.

What Problem Does This Paper Address?

In many real-world control problems, we might not need to find the absolute best policy from scratch. Instead, we might already have a collection of reasonably good or safe policies, perhaps provided by experts. The problem then becomes: can we combine these existing policies in a smart way to achieve even better performance? This paper focuses on a specific way of combining policies: taking their "convex hull." Imagine each base policy as a point in a space; their convex hull is the shape formed by connecting all these points. The authors are interested in finding the optimal policy within this shape.

This is particularly relevant when dealing with large state spaces in MDPs, where finding a truly optimal policy from scratch is computationally infeasible. Traditional methods like policy gradients can get stuck in local optima and require extensive interaction with the environment. The authors aim to leverage prior knowledge embedded in the base policies to overcome these limitations.

Methods

The paper's core contribution lies in two main areas: theoretical hardness results and an efficient algorithmic solution.

Theoretical Hardness: The authors prove that finding the optimal policy within the convex hull of base policies is NP-hard, both for exact solutions and for arbitrary approximation accuracy. This is a significant theoretical result, especially considering that optimizing over an unconstrained policy space (which is exponentially larger) is tractable. The hardness arises from the need for the optimal policy to potentially randomize its actions, unlike deterministic optimal policies in the unconstrained case.

Algorithmic Solution (Dual Space Optimization): Instead of directly optimizing in the "primal space" of policy mixtures, the authors propose a clever approach by moving to the "dual space" of occupancy measures. Occupancy measures describe the long-term average visitation of state-action pairs under a given policy. The key insight is that a linear combination of the base policies' occupancy measures can represent a policy, and optimizing in this dual space can be more tractable, especially when the base policies' occupancy measures have significant overlap.

They formulate an optimization problem in this dual space and use a stochastic subgradient method to solve it. This method iteratively updates a parameter vector that defines a linear combination of occupancy measures. The algorithm's efficiency stems from its ability to compute occupancy measures in time linear to the state space size (or estimate them via roll-outs) and its avoidance of backward simulators, making it applicable to systems with only forward simulators.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development, using simulated environments for experiments rather than real-world datasets.

Key Insights and Ideas

  • NP-Hardness is Surprising: It's counterintuitive that restricting the policy space to a convex hull of base policies makes the problem NP-hard, while optimizing over an exponentially larger space of all possible policies is tractable. This highlights the subtle complexities of policy optimization.
  • Dual Space Advantage: Shifting the optimization problem from the primal space of policy mixtures to the dual space of occupancy measures can significantly simplify the problem, especially when base policies' occupancy measures overlap. This overlap is crucial for generating useful policies in the dual space.
  • Overlap is Key: The paper emphasizes that the efficiency and effectiveness of their algorithm depend on the "large overlap" of the occupancy measures of the base policies. This suggests that the base policies should be somewhat similar in their long-term behavior to yield substantial benefits from combining them.
  • Computational Efficiency: The proposed algorithm avoids repeated interactions with the environment during optimization, which is a major advantage in complex systems where simulating a policy can be very time-consuming. This is achieved by working with pre-computed or estimated occupancy measures.

Key Results

  • Theoretical Hardness: The problem of optimizing over a restricted policy class (convex hull of base policies) is proven to be NP-hard.
  • Efficient Algorithm: An efficient algorithm is presented that finds a near-optimal policy in the dual space, with performance guarantees that depend on the overlap of base policy occupancy measures.
  • Computational Complexity: The algorithm's running time is linear in the number of states and polynomial in the number of base policies.
  • Experimental Validation: The paper demonstrates the algorithm's effectiveness on queuing problems, showing that optimizing in the dual space (occupancy measures) yields better policies and significant computational savings compared to optimizing in the primal space (policy mixtures) or using traditional policy gradient methods. For instance, in one experiment, the dual space optimization achieved a cost of 447, significantly lower than the best mixture policy in the primal space (533.60).

Limitations and Future Work

  • Overlap Condition: The theoretical guarantees of the algorithm are contingent on the base policies' occupancy measures having "large overlap." The paper provides a condition for this overlap but doesn't fully explore the performance degradation when overlap is small.
  • Approximation Guarantees: While the algorithm finds a near-optimal policy, the theoretical bounds are expressed in terms of the number of rounds and parameters like the constraint multiplier, which might require careful tuning.
  • Future Work: The authors suggest extending their work to average cost criteria and exploring the computational complexity of related problems. They also hint at the potential for using this approach in POMDPs (Partially Observable Markov Decision Processes). The experimental results suggest that further investigation into the benefits of dual space optimization across a wider range of complex systems would be valuable.

Summary updated

Abstract

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.
BibTeX
@misc{banijamali2018optimizing,
  author = {Ershad Banijamali and Yasin Abbasi-Yadkori and Mohammad Ghavamzadeh and Nikos Vlassis},
  title = {{Optimizing over a Restricted Policy Class in Markov Decision Processes}},
  year = {2018},
  eprint = {1802.09646},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.09646},
}
Figure