Approximate solutions to constrained risk-sensitive Markov decision processes

Uday Kumar M, Sanjay P. Bhat, Veeraruna Kavitha, Nandyala HemachandraEur. J. Oper. Res 2022 · OpenReview

TL;DR

This paper tackles the challenge of finding optimal decision-making policies in complex systems (modeled as Markov Decision Processes) that have both performance constraints and a preference for avoiding risk. The authors propose a novel approach to approximate solutions for these "Constrained Risk-Sensitive Markov Decision Processes" by transforming the problem into simpler, finite-horizon versions, making it more computationally tractable.

What Problem Does This Paper Address?

In many real-world scenarios, decision-makers face not only the goal of optimizing some objective (like minimizing costs or maximizing rewards) but also the need to satisfy certain constraints. These constraints can be related to average performance or specific risk levels. Furthermore, decision-makers often have a preference for avoiding high-risk outcomes, even if it means a slight compromise on the expected outcome. This is where "risk-sensitive" decision-making comes into play.

Traditional Markov Decision Processes (MDPs) typically focus on optimizing expected costs or rewards, which is a "risk-neutral" approach. While extensions exist for risk-sensitive objectives or constraints separately, combining both in an infinite-horizon setting presents significant theoretical and computational hurdles. Specifically, finding exact solutions for these "Constrained Risk-Sensitive Markov Decision Processes" (CRSMDPs) is often intractable. This paper aims to bridge this gap by developing methods to find approximate solutions that are both near-optimal and satisfy the given constraints, even in the presence of risk aversion.

Methods

The core of the paper's methodology lies in approximating the infinite-horizon CRSMDP problem with finite-horizon CRSMDPs. This is achieved through two key strategies:

  1. Time-Truncation: The infinite-horizon objective and constraint functions are "truncated" at a finite horizon $T$. This means considering the costs and constraints only up to time $T$.
  2. Constraint Perturbation: The upper bounds of the constraints are slightly adjusted (perturbed) in the finite-horizon approximations. This is a crucial step to ensure that the approximate solutions are related to the original problem's feasible region.

By solving these approximated finite-horizon problems, the authors derive ultimately stationary (US) Markovian randomized (MR) policies. The paper then proves that these policies are either $\epsilon$-optimal and feasible for the original problem (using one approximation) or near-optimal and approximately feasible (using the other approximation). A key technical contribution is the development of a suitable metric space for policies that makes the objective and constraint functions continuous, enabling the application of standard optimization techniques. The paper also provides a linear programming (LP) formulation for solving these finite-horizon approximations.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic approaches for a general class of problems, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging Infinite and Finite Horizons: The paper demonstrates that by carefully time-truncating and perturbing constraints, complex infinite-horizon problems can be effectively approximated by simpler finite-horizon ones. This is a common strategy in dynamic programming, but its application here to CRSMDPs is novel.
  • The Power of Approximation: The authors show that even if exact solutions are elusive, near-optimal and feasible policies can be reliably obtained through these approximations. This is crucial for practical applications where perfect optimality might be computationally infeasible.
  • Topology Matters: The introduction of a specific metric and topology on the policy space is a critical technical step. It ensures that the objective and constraint functions behave well (are continuous), which is essential for proving the existence of solutions and the convergence of approximations.
  • Feasibility vs. $\epsilon$-Feasibility: The paper distinguishes between policies that are strictly feasible for the original problem and those that are "$\epsilon$-feasible," meaning their constraint violations are bounded by a small quantity $\epsilon$. This offers flexibility in practical scenarios.

Key Results

  • Existence of Solutions: The paper proves that if a CRSMDP is feasible (i.e., there exists at least one policy that satisfies all constraints), then both the original infinite-horizon problem and its finite-horizon approximations have solutions.
  • $\epsilon$-Optimality and Feasibility: For a sufficiently large truncation horizon $T$, a policy that solves the first type of finite-horizon approximation is $\epsilon$-optimal and feasible for the original infinite-horizon CRSMDP, provided a specific local minimum condition on constraint violation is met.
  • $\epsilon$-Feasibility and Near-Optimality: For a sufficiently large $T$, a policy that solves the second type of finite-horizon approximation is $\epsilon$-feasible and approximately optimal for the original problem, without requiring the additional local minimum condition.
  • LP Formulation: The paper provides a linear programming formulation to solve the finite-horizon CRSMDPs, making the derived approximate solutions computationally accessible.

Limitations and Future Work

  • Local Minimum Condition: Theorem 3.2, which guarantees an $\epsilon$-optimal and feasible solution, relies on a condition that 0 is not a local minimum of the maximum constraint violation function. The authors acknowledge that checking this condition can be difficult in practice and provide a counterexample where its violation leads to failure.
  • Computational Complexity: While the LP formulation provides a method for solving the finite-horizon problems, the complexity of solving these LPs can still be significant, especially for large state and action spaces or long horizons.
  • Future Work: The paper suggests that the LP-based approach can be extended to solve the finite-horizon CRSMDPs directly, without the need for the intermediate step of converting RS costs to standard discounted costs on an augmented state space. The authors also mention that the framework can be adapted for multiple discount factors, which is a direction for future research.

Summary updated

Abstract

Highlights•We consider the problem to find solution of infinite-horizon, constrained risk-sensitive Markov decision processes.•Objective and constraints are standard and risk-sensitive discounted cost functions over finite & infinite horizons.•Two methods are given for finding an ultimately stationary randomized policy by time-truncating the cost functions.•These two methods essentially solve two finite-horizon risk-sensitive Markov decision processes.•We discuss two applications and illustrate an inventory control problem.
BibTeX
@article{m2022approximate,
  author = {Uday Kumar M and Sanjay P. Bhat and Veeraruna Kavitha and Nandyala Hemachandra},
  title = {{Approximate solutions to constrained risk-sensitive Markov decision processes}},
  journal = {Eur. J. Oper. Res.},
  year = {2022},
  url = {https://openreview.net/forum?id=ZnF6gNYj7D},
}
Figure