Deep Reinforcement Learning for Weakly Coupled MDP's with Continuous Actions

Francisco Robledo, Urtzi Ayesta, Konstantin Avrachenkov

TL;DR

This paper introduces LPCA, a novel deep reinforcement learning algorithm designed for weakly coupled Markov Decision Processes (MDPs) with continuous action spaces. LPCA effectively handles resource constraints by employing a Lagrange relaxation, enabling efficient policy learning and outperforming existing methods like DDPG in complex scenarios.

What Problem Does This Paper Address?

The paper tackles the challenge of decision-making under uncertainty in environments where multiple independent processes (projects) are coupled by a shared resource constraint. This is a common problem in fields like telecommunications, finance, and robotics. Specifically, the authors focus on "weakly coupled MDPs" where each project has its own state and action space, but their actions collectively consume a limited pool of resources. The complexity arises from the continuous nature of actions (e.g., adjusting resource levels) and the interdependency introduced by the shared resource. Traditional methods struggle with the exponential growth of the decision space and the difficulty of optimizing for both reward maximization and resource constraint satisfaction simultaneously.

Methods

The core innovation is the Lagrange Policy for Continuous Actions (LPCA) algorithm. LPCA leverages a Lagrange relaxation of the weakly coupled MDP problem. This relaxation transforms the constrained optimization problem into an unconstrained one by introducing a Lagrange multiplier ($\lambda$) that penalizes resource overconsumption.

LPCA uses a neural network to approximate the Q-values, which are now dependent on the Lagrange multiplier $\lambda$. The algorithm operates in a two-timescale manner:

  1. Learning Q-values: A neural network is trained to learn the Q-values for various state-action pairs across a range of $\lambda$ values. This involves using a target network for stability and a mini-batch approach for updates.
  2. Optimizing $\lambda$ and Actions: For a given state, LPCA first determines the optimal Lagrange multiplier $\lambda^*$ that minimizes a specific objective function (balancing rewards and costs). Then, it uses this $\lambda^*$ to select the best continuous actions for each project.

Two distinct strategies are proposed for action selection:

  • LPCA-DE (Differential Evolution): This method uses a differential evolution algorithm to explore the action space, aiming to find actions that maximize the Q-values while respecting the resource budget. It incorporates a penalty for unused resources to encourage full utilization.
  • LPCA-Greedy: This approach iteratively selects actions by evaluating the gradient of the Q-values with respect to actions. It prioritizes actions that offer the highest increase in Q-value per unit of resource, aiming for quick identification of profitable actions.

Datasets

The paper does not introduce new datasets. Instead, it uses simulated environments designed to represent different types of weakly coupled MDP problems with continuous actions. These include:

  • Type A and Type B Environments: These are continuous action versions of problems similar to those found in existing literature. They feature two states per project, with specific reward and cost functions, and differ in their transition probability matrices.
  • Mixed Environment: This combines Type A and Type B projects to test the algorithm's ability to handle heterogeneous environments.
  • Speed Scaling Environment: Inspired by existing work, this environment involves projects with six states and is adapted to a discrete-time version using uniformization.

Key Insights and Ideas

  • Lagrange Relaxation as a Decoupling Mechanism: The paper demonstrates that Lagrange relaxation is a powerful tool for decoupling weakly coupled MDPs, even with continuous actions, by transforming the problem into a series of independent optimization tasks guided by the Lagrange multiplier.
  • The Role of the Lagrange Multiplier ($\lambda$): $\lambda$ acts as a crucial trade-off parameter, allowing the algorithm to balance immediate rewards against action costs. A higher $\lambda$ prioritizes cost minimization, while a lower $\lambda$ favors reward maximization.
  • Neural Networks for Continuous Action Q-Value Approximation: Using neural networks to approximate Q-values that are functions of both state, action, and the Lagrange multiplier is key to handling the continuous action space and the complex resource constraints.
  • Differential Evolution for Robust Optimization: LPCA-DE's use of differential evolution proves effective in navigating complex action spaces and avoiding local optima, especially when resource utilization needs to be maximized.
  • Greedy Approach for Efficiency: LPCA-Greedy offers a faster, simpler alternative that quickly identifies high-payoff actions, though it might not explore as broadly as DE.

Key Results

The experimental results show that LPCA, in both its DE and Greedy variants, consistently outperforms the DDPG algorithm augmented with OptLayer.

  • Superior Performance: LPCA achieved significantly better discounted rewards across various settings, particularly in more complex scenarios with more projects and limited resources.
  • Faster Convergence: LPCA algorithms converged to performance levels similar to Whittle indices much faster than DDPG, which often took tens of thousands of iterations.
  • Scalability: LPCA demonstrated superior scalability with an increasing number of projects.
  • Effectiveness in Complex Scenarios: In the Type B environment and the mixed environment, LPCA-DE and LPCA-Greedy obtained better policies, closely matching the performance of the Whittle index policy, while DDPG struggled.

Limitations and Future Work

  • Limitations: The paper acknowledges that while the greedy approach is faster, it might not explore as widely as differential evolution. The choice between DE and Greedy depends on the specific problem characteristics, such as the nature of resource constraints and the desired balance between utilization and reward.
  • Future Work: The authors propose testing LPCA in larger-scale environments with more states per project to further evaluate its scalability and effectiveness. They also aim to broaden its applicability to a wider array of practical problems in operations research and beyond, guiding future enhancements and adaptations.

Summary updated

BibTeX
@inproceedings{robledo2024deep,
  author = {Francisco Robledo and Urtzi Ayesta and Konstantin Avrachenkov},
  title = {{Deep Reinforcement Learning for Weakly Coupled MDP's with Continuous Actions}},
  booktitle = {ASMTA},
  year = {2024},
  doi = {10.1007/978-3-031-70753-7\_5},
}
Figure