Solution Methods for Constrained Markov Decision Process with Continuous Probability Modulation

Marek Petrik, Dharmashankar Subramanian, Janusz Marecki

Abstract: We propose solution methods for previously-unsolved constrained MDPs in which actions can continuously modify the transition probabilities within some acceptable sets. While many methods have been proposed to solve regular MDPs with large state sets, there are few practical approaches for solving constrained MDPs with large action sets. In particular, we show that the continuous action sets can be replaced by their extreme points when the rewards are linear in the modulation. We also develop a tractable optimization formulation for concave reward functions and, surprisingly, also extend it to non-concave reward functions by using their concave envelopes. We evaluate the effectiveness of the approach on the problem of managing delinquencies in a portfolio of loans.

Introduction

Researchers at IBM T.J. Watson have addressed a complex optimization problem prevalent in finance and operations: making optimal decisions when actions continuously influence the probabilities of future events, all while adhering to strict safety or regulatory boundaries. This scenario is modeled as a Constrained Markov Decision Process (CMDP) with continuous probability modulation.

Consider the management of a large loan portfolio. Loans transition between states such as "current," "30 days late," "90 days late," or "default." Interventions, like offering payment plans, are intended to prevent defaults. This problem is complicated by two factors:

  1. Constraints: Regulatory or budget limits (e.g., keeping the expected default rate below 4%).
  2. Continuous Probability Modulation: Actions are not discrete choices but continuous adjustments to the probability of state transitions.

Directly solving these problems typically results in high-degree, non-convex polynomial optimization problems, which are NP-hard and prone to local optima.

Methodology

The authors propose three solution methods tailored to the nature of the reward function:

Affine (Linear) Rewards

For linear rewards, the authors prove that the infinite range of continuous actions can be reduced to the "extreme points" (vertices) of the feasible action set. This simplification transforms the continuous problem into a more manageable discrete one.

Concave Rewards

A novel convex optimization formulation is developed using joint state-action visitation probabilities. By applying positive homogeneity, the researchers transform non-convex constraints into a set of convex constraints solvable by standard optimization software.

Non-Concave Rewards

In cases where reward functions exhibit non-concavity (e.g., economies of scale), the problem is traditionally intractable. However, because optimal policies in CMDPs are often randomized, the authors demonstrate that the problem can be solved using the concave envelope of the reward function. This "tight lid" over the non-concave function allows for the reconstruction of an optimal randomized policy.

The concave envelope (dashed) provides a tractable upper bound for non-concave reward functions (solid), enabling optimization via randomization.

Evaluation and Results

The methods were evaluated using real-world loan data (8 delinquency states over a 6-month horizon) and synthetic benchmarks designed to test scalability up to 100+ states.

Performance and Scalability

The proposed optimal method achieved an average 13.97% reduction in expected costs across six actual loan portfolios compared to current human-managed strategies. Furthermore, the global optimizer produced stable, smooth intervention strategies over time, avoiding the erratic investments common in "greedy" algorithms.

Computational efficiency was a key highlight. While the "extreme point" method failed to scale beyond 30 states due to exponential growth in vertices, the "concave" formulation maintained linear scalability, solving problems with over 100 states in seconds.

Computational time comparison: the concave formulation scales gracefully with state size, while the extreme point method grows exponentially.

Conclusion

This research provides a tractable framework for solving CMDPs with continuous action sets, turning previously NP-hard problems into efficient optimization tasks. While the current model assumes risk neutrality, future work may explore risk-averse scenarios and methods for constructing concave envelopes for higher-dimensional reward functions. The ability to handle 100+ states represents a significant leap forward for practical financial and operational decision-making.

Summary updated

Abstract

We propose solution methods for previously-unsolved constrained MDPs in which actions can continuously modify the transition probabilities within some acceptable sets. While many methods have been proposed to solve regular MDPs with large state sets, there are few practical approaches for solving constrained MDPs with large action sets. In particular, we show that the continuous action sets can be replaced by their extreme points when the rewards are linear in the modulation. We also develop a tractable optimization formulation for concave reward functions and, surprisingly, also extend it to non- concave reward functions by using their concave envelopes. We evaluate the effectiveness of the approach on the problem of managing delinquencies in a portfolio of loans.
BibTeX
@inproceedings{petrik2013solution,
  author = {Marek Petrik and Dharmashankar Subramanian and Janusz Marecki},
  title = {{Solution Methods for Constrained Markov Decision Process with Continuous Probability Modulation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=dQDXwxHSMB},
}
Figure