Optimizing over a Restricted Policy Class in MDPs

Ershad Banijamali, Yasin Abbasi-Yadkori, Mohammad Ghavamzadeh, Nikos VlassisAISTATS 2019 · OpenReview

Abstract

We address the problem of finding an optimal policy in a Markov decision process (MDP) under a restricted policy class defined by the convex hull of a set of base policies. This problem is of great practical importance when safe or expert-derived policies are available. We prove the NP-hardness of this optimization and propose a dual-space algorithm that leverages occupancy measures to achieve significant computational efficiency and safety.

Introduction

In many real-world control and reinforcement learning (RL) scenarios, we often have access to a set of "base policies"—strategies that are known to be safe or reasonably effective, perhaps provided by human experts or previous algorithmic iterations. A natural objective is to find the optimal policy within the convex hull of these base policies. However, this task presents significant challenges. First, optimizing over a restricted policy class is computationally difficult. Second, traditional RL methods often require extensive environment interaction, which can be risky in safety-critical systems like chemical plants or autonomous vehicles.

Computational Complexity

A surprising finding of this work is that finding the optimal mixture of base policies is NP-hard. While unconstrained MDP optimization is generally solvable in polynomial time, restricting the search space to a convex hull introduces complexity. We establish this hardness through a reduction from the Independent-Set problem for graphs, utilizing the Motzkin-Straus theorem to demonstrate that even approximating the best mixture policy is computationally intractable in the general case.

The Dual-Space Approach

To overcome these hurdles, we propose a shift from the "primal space" (optimizing policy weights directly) to the "dual space" of occupancy measures. An occupancy measure represents the probability distribution over state-action pairs induced by a policy.

Instead of optimizing the policy mixture directly, our algorithm—the Stochastic Subgradient Method—optimizes a linear combination of the occupancy measures of the base policies. Since a linear combination of valid occupancy measures is not guaranteed to be a valid occupancy measure itself, we employ a convex surrogate function with a penalty term for "invalid" (negative) values. This approach allows for "offline" optimization: once the occupancy measures of the base policies are estimated from historical data, the optimization proceeds without further environment interaction, ensuring safety.

Experimental Evaluation

We evaluated our approach using simulated queuing systems, which serve as standard benchmarks for resource allocation. These include a simple 1-queue system and a more complex 8-queue system. The 8-queue system involves three servers managing eight queues, requiring complex prioritization decisions.

Schematic of the 8-queue system with three servers used for benchmarking.

Key Results

The dual-space method demonstrates remarkable efficiency and performance. In the 8-queue benchmark, the proposed algorithm was over 1,000 times faster than traditional primal-space policy gradient methods. Furthermore, despite the theoretical NP-hardness, the algorithm consistently found policies that were nearly as effective as the best possible mixture. In the 1-queue experiment, the dual-space policy even outperformed the best possible "primal" mixture.

Convergence of the cost function during optimization for the proposed dual-space method.

Conclusion and Future Work

By moving to the dual space, we provide a framework for policy optimization that is faster, safer, and theoretically grounded. The performance of this method depends on the "overlap" of the occupancy measures of the base policies; high overlap ensures more effective approximation. Future work will explore extending this framework to high-dimensional continuous spaces using sophisticated function approximation techniques like deep learning, as well as refining the initial estimation of occupancy measures.

Summary updated

Abstract

We address the problem of finding an optimal policy in a Markov decision process (MDP) under a restricted policy class defined by the convex hull of a set of base policies. This problem is of great...
BibTeX
@inproceedings{banijamali2019optimizing,
  author = {Ershad Banijamali and Yasin Abbasi-Yadkori and Mohammad Ghavamzadeh and Nikos Vlassis},
  title = {{Optimizing over a Restricted Policy Class in MDPs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=QNEggBSl9Ni},
}
Figure