A policy gradient approach for Finite Horizon Constrained Markov Decision Processes

Soumyajit Guin, Shalabh Bhatnagar

Researchers from the Indian Institute of Science have addressed a significant limitation in Reinforcement Learning (RL) by developing a novel policy gradient algorithm specifically for Finite Horizon Constrained Markov Decision Processes (C-MDPs). This work bridges the gap between theoretical RL models and real-world applications where tasks must be completed within a strict timeframe while adhering to safety or resource constraints.

The Problem: The Mismatch of Infinite Horizons

Most traditional RL research operates under the "infinite horizon" assumption. In this setting, an agent behaves as if it has an unlimited amount of time to achieve its goals, leading to the adoption of stationary policies. A stationary policy dictates that an agent should take the same action in a specific state regardless of whether it is at the beginning of its mission or seconds away from a deadline.

However, many practical scenarios are inherently time-critical. For instance, a robot with a depleting battery or a financial portfolio manager facing a market close must adapt their strategies based on the remaining time. When these tasks are governed by safety constraints—such as avoiding high-risk zones or maintaining a minimum liquidity—the problem becomes a Constrained MDP. Prior to this research, policy gradient methods lacked a unified framework that combined finite horizons, hard constraints, and the function approximation necessary for complex, large-scale environments.

Methodology: Non-Stationary Actor-Critic

The authors propose a non-stationary Actor-Critic architecture. Unlike standard methods, this algorithm recognizes that the optimal policy changes as the horizon ($H$) approaches. The core of the approach rests on three pillars:

  1. Lagrangian Relaxation: To manage constraints, the researchers employ a Lagrange multiplier ($\lambda$). This converts the constrained optimization problem into an unconstrained one by penalizing the agent for safety violations, effectively balancing the pursuit of rewards against the cost of constraint infringement.
  2. Multi-Timescale Stochastic Approximation (MTSA): To ensure numerical stability and convergence, the algorithm updates its components at three distinct "speeds" or step-sizes:
  3. The Critic (Fastest): Learns the value function for specific state-time pairs.
  4. The Actor (Middle): Refines the policy based on the critic’s evaluations.
  5. The Lagrange Multiplier (Slowest): Gradually adjusts the penalty weight based on long-term constraint satisfaction trends.
  6. Time-Varying Parameters: The algorithm maintains a unique set of parameters for every discrete time step in the horizon. This allows the agent to learn non-stationary strategies, such as being risk-averse in the early stages and becoming more aggressive as the deadline nears.

Experimental Evaluation

The proposed algorithm was tested in a dynamic 2D Grid World environment where reward locations and hazardous "constraint states" shifted over time. The agent's goal was to maximize rewards while keeping the total constraint cost below a threshold ($\alpha = 25$) within a fixed horizon of $H=100$ steps.

The researchers compared their "FH-Constrained" and "NN-Constrained" (Neural Network) versions against established infinite-horizon baselines, including Constrained Policy Optimization (CPO) and PPO-Lagrangian.

Key Insights

  • The Failure of Stationarity: Infinite-horizon algorithms like CPO struggled because they attempt to find a single "average" policy. In time-varying environments, an average policy is often suboptimal at every specific time step.
  • The "Clock" Advantage: Providing the agent with separate parameters for each time step proved superior to the common "hack" of simply adding the remaining time as an input feature to a standard algorithm.
  • Theoretical Rigor: Beyond empirical success, the paper provides mathematical proofs that the multi-timescale approach converges to a constrained local optimum, offering a reliable theoretical foundation for safety-critical deployments.

Results and Future Directions

The experimental results demonstrated that the proposed algorithm was the only method to consistently satisfy the safety constraints. In contrast, popular baselines either significantly exceeded the safety threshold or failed to accumulate meaningful rewards.

Despite these successes, the authors note certain trade-offs. Because the algorithm stores separate parameters for each time step $h \in \{0, \dots, H-1\}$, memory requirements scale linearly with the horizon length. Future work will focus on improving sample complexity and testing the framework in high-dimensional continuous control environments, such as robotics simulations, to further validate its robustness in the real world.

Summary updated

BibTeX
@inproceedings{guin2023policy,
  author = {Soumyajit Guin and Shalabh Bhatnagar},
  title = {{A policy gradient approach for Finite Horizon Constrained Markov Decision Processes}},
  booktitle = {CDC},
  year = {2023},
  doi = {10.1109/cdc49753.2023.10383413},
}
Figure