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.
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.
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