Solution Methods for Constrained Markov Decision Process with Continuous Probability Modulation

Marek Petrik, Dharmashankar Subramanian, Janusz Marecki

This paper, presented by researchers at IBM T.J. Watson, tackles a complex optimization problem often found in finance and operations: how to make optimal decisions when your actions continuously nudge the probabilities of future events, all while staying within strict safety or regulatory boundaries.

TL;DR

The authors provide a tractable way to solve Constrained Markov Decision Processes (CMDPs) where actions continuously modulate transition probabilities. By leveraging convex optimization and "concave envelopes," they transform a traditionally NP-hard non-convex problem into one that can be solved in seconds, demonstrating a nearly 14% cost reduction in real-world loan portfolio management.

What Problem Does This Paper Address?

Imagine you are managing a massive portfolio of loans. Each loan can be in various states: "current," "30 days late," "90 days late," or "default." You want to intervene (e.g., offer a principal reduction or a payment plan) to prevent defaults.

In mathematical terms, this is a Markov Decision Process (MDP). However, it has two major complications:

  1. Constraints: You have a budget or a regulatory limit. For example, "The expected percentage of defaults at the end of the year must be less than 4%." This makes it a Constrained MDP.
  2. Continuous Probability Modulation: Unlike a standard game where you choose from a few discrete moves (Action A or Action B), here an "action" is a continuous adjustment. You can spend a little or a lot to shift the probability of a loan moving from "late" back to "current."

Directly solving this leads to high-degree, non-convex polynomial optimization problems. These are notoriously difficult (NP-hard) because they are riddled with local optima, making it nearly impossible for standard solvers to find the best global strategy.

Methods

The authors propose three escalating solution methods based on the nature of the reward (profit/cost) function:

  • For Affine (Linear) Rewards: They prove that if rewards are linear, you don't need to consider the infinite range of continuous actions. You only need to look at the "extreme points" (the vertices) of the feasible action set. This turns the continuous problem back into a discrete one.
  • For Concave Rewards: They develop a novel convex optimization formulation. By using "joint state-action visitation probabilities" as variables and applying a mathematical trick (positive homogeneity), they transform the non-convex constraints into a set of convex constraints that a computer can solve efficiently.
  • For Non-Concave Rewards: This is the most surprising part. If a reward function is non-concave (perhaps showing "economies of scale" where the more you spend, the more efficient the modulation becomes), the problem is usually a nightmare. The authors show that because optimal policies in CMDPs are often randomized, you can solve the problem using the concave envelope of the reward function—essentially a "tight lid" over the non-concave function—and then reconstruct the optimal randomized policy from that solution.

Datasets

The authors evaluated their methods using two sources:

  1. Real-World Loan Data: A dataset from an actual loan service provider featuring 8 delinquency states and a 6-month planning horizon.
  2. Synthetic Benchmarks: Generated loan delinquency problems with varying numbers of states (up to 100+) to test how the algorithms scale as the problem size grows.

Key Insights and Ideas

  • The "Extreme Point" Insight: In many financial scenarios, the best move is either to do nothing or to go "all-in" on a specific intervention. This paper provides the formal proof for when and why this is true in the context of probability modulation.
  • Randomization as a Feature, Not a Bug: In standard MDPs, we usually want a "deterministic" policy (in State X, always do Y). In Constrained MDPs, the optimal strategy is often to flip a coin between two actions to perfectly hit a constraint boundary. The authors lean into this, using randomization to justify the use of concave envelopes.
  • Scalability: The "concave" formulation is significantly more robust than the "extreme point" method. While the number of vertices (extreme points) can grow exponentially with the number of states, the convex optimization approach scales gracefully to hundreds of states.

Key Results

  • Cost Savings: On six actual loan portfolios, the proposed optimal method achieved an average 13.97% reduction in expected costs compared to the benchmark strategies currently used by human loan managers.
  • Computational Efficiency: In synthetic tests, the "extreme point" method became unusable once the problem hit 30 states. In contrast, the "concave" method solved problems with 100+ states in just a few seconds using standard off-the-shelf solvers (like CPLEX).
  • Smoothing Interventions: Unlike "greedy" algorithms that tend to make aggressive, erratic investments month-to-month, the proposed global optimizer produced smooth, stable intervention strategies over the 6-month horizon.

Limitations and Future Work

  • Risk Neutrality: The current model assumes the loan provider is "risk-neutral" (only cares about the average outcome). In reality, many banks are "risk-averse" and might want to avoid "worst-case" scenarios even if the average is good.
  • Envelope Complexity: While the concave envelope approach is powerful, constructing that envelope for very high-dimensional or highly irregular reward functions remains a challenge.
  • State Space Limits: While 100+ states is a huge improvement, truly massive systems (like national-scale economic models) would still require further approximation or decomposition techniques.

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},
}

Loading related content...

Figure