Pith. sign in

REVIEW 1 major objections 5 minor 30 references

Convex Approximations of Random Constrained Markov Decision Processes

T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For constrained Markov decision processes with random running costs—and with both random costs and random transition probabilities—the paper constructs convex upper-bound programs and a linear-programming lower bound whose gap certifies…

desk verdict Solid, honest convex-bounding work for chance-constrained MDPs, but the Section 4 lower bound is only for the stationary-policy restriction—the abstract overstates it. read the letter →

arxiv 2505.24815 v1 pith:RQCEHJ2Y submitted 2025-05-30 math.OC cs.SYeess.SY

V Varagapriya , Vikas Vikram Singh , Abdel Lisser This is my paper
classification math.OCcs.SYeess.SY MSC 90C4090C1590C25
keywords chance-constrainedoptimizationconstrainedMarkovdecisionprocessesconvexprogrammingsecond-orderconeGumbel-HougaardcopulaqueueingcontrolproblemGarnetsdistribution-freebounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Constrained Markov decision processes tell a controller how to act when several long-run costs must stay below thresholds, but the standard theory assumes the costs and transition probabilities are known exactly. This paper studies the realistic case where those parameters are random, so both the objective and the constraints are random. It claims that the resulting joint chance-constrained problem—where all constraints must be satisfied together with high probability—can be bracketed by a family of tractable deterministic programs: convex programs that give upper bounds and one linear program that gives a lower bound. Only means, variances, and ranges of the random parameters are needed, not their exact distributions. If the gap between upper and lower bounds is small, the stationary policy extracted from the upper-bound solution is nearly optimal.

What carries the argument

The load-bearing objects are deterministic inner and outer approximations of a single linear chance constraint $\mathbb P(r^T z \le a)\ge p$. The inner approximations are second-order cone constraints from one-sided Chebyshev ($r^T\mu_z+\sqrt{p/(1-p)}\|\Sigma_z^{1/2}r\|_2\le a$), Hoeffding, and sub-Gaussian inequalities, plus a Bernstein exponential-convex constraint; the outer approximation is the new linear system $r^T\mu_z-a\le(1-p)m$, $r^T z^u-a\le m$, $r^T z^l\le a$, obtained by bounding the indicator of violation by a linear function through the constant $m$. The Gumbel-Hougaard copula (a function coupling the marginal distributions of the random constraint vectors) converts the joint constraint into individual constraints with probability levels $p_1^{y_k^{1/\theta}}$, and convexity lemmas for the resulting functions of $y$ keep the programs convex. For random transitions, the identity $\tilde Q_f = Q_f^M(I+\alpha Z_f\tilde Q_f)$ and componentwise bounds $C_{\min},C_{\max},D^k_{\min},D^k_{\max}$ reduce the random discounted value to an individual linear chance constraint in the perturbation variables.

What would settle it

Take a small JCCMDP with random transitions (two states, two actions) and search over history-dependent policies by enumeration or policy iteration: if some history-dependent randomized policy is feasible at levels $(p_0,p_1)$ with a strictly smaller objective than every stationary policy, then the paper's bounds apply only to the stationary-policy restriction (19), not to the original problem (4). For the random-cost case, fix the marginals and choose a non-Gumbel-Hougaard copula such as a Clayton copula; if the feasible set of the individual chance constraints in Lemma 2 differs from the joint chance constraint's feasible set, then the copula assumption is load-bearing and cannot be dropped.

Watch

Extended reading notes

Core claim

The paper establishes that a discounted-cost constrained MDP with random running costs—and, in a stationary-policy restriction, with both random costs and random transition probabilities—can be approximated from outside and from inside by deterministic convex programs. For random costs alone, the joint chance constraint is split, under a Gumbel-Hougaard copula, into individual chance constraints; each individual constraint is replaced by a convex certificate using one-sided Chebyshev, Hoeffding, sub-Gaussian, or Bernstein inequalities, giving four upper-bound programs, while a new linear outer approximation (Theorem 7) gives a lower bound. For random transitions, the random transition matrix is written as a mean matrix plus a bounded zero-mean perturbation, the identity $\tilde Q_f = Q_f^M(I+\alpha Z_f\tilde Q_f)$ separates mean and perturbation effects, and a union bound converts the joint constraint into individual chance constraints; three convex upper-bound programs and one LP (Theorem 10) follow from the same inequality toolkit. In both settings the upper-bound values are valid upper bounds and the LP value is a valid lower bound; the difference is a certified suboptimality gap for the stationary policy obtained from any upper-bound solution.

Load-bearing premise

The analysis presupposes that the optimal value is reached by a stationary policy when transitions are random, and that the true dependence among the random cost constraints is of the Gumbel-Hougaard copula type assumed (a function coupling the marginal distributions).

Editorial extensions

If this is right

  • A controller who knows only means, variances, and upper and lower ranges can compute a stationary policy with a certified suboptimality gap, without assuming a specific distribution for the costs.
  • The LP lower bound has polynomial-time interior-point solvers, with complexity roughly $O(|\mathcal K|^{1/2}|\ln\hat\epsilon|)$, so the approximation approach scales to large state-action spaces.
  • When information improves—from bounded ranges to sub-Gaussian parameters to exact Gaussian or elliptical distributions—the upper bound tightens, showing the concrete value of distributional knowledge.
  • For random transition probabilities, the gap grows with the perturbation magnitude $\eta$ and the discount factor $\alpha$, so the method is most accurate when transition noise is modest.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step is to determine when the stationary-policy restriction is without loss of optimality for random transitions; the paper leaves that question open.
  • The paper's moment-and-range approach could be combined with robust optimization by treating means, covariances, and bounds as set-valued uncertain parameters, which would guard against estimation error.
  • The LP lower bound could be sharpened by increasing the tangent points $N$ or by replacing the indicator bound with tighter outer approximations, at the cost of more constraints.
  • Practitioners with heavy-tailed costs should check sub-Gaussianity empirically, since the Hoeffding and sub-Gaussian certificates are known to degrade or fail for heavy tails.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper studies a discounted-cost constrained Markov decision process in which the running costs, or both running costs and transition probabilities, are random. The authors formulate a joint chance-constrained MDP (JCCMDP) and derive tractable convex approximations. For random running costs and a Gumbel-Hougaard copula dependence, they give four upper-bound programs based on one-sided Chebyshev, Hoeffding, sub-Gaussian, and Bernstein inequalities, and an LP lower bound obtained from a new linear outer approximation of a scalar chance constraint. For the case with random running costs and random transition probabilities, they restrict attention to stationary policies, give three upper-bound programs and an LP lower bound, and test the gaps on a queueing control problem and on randomly generated Garnet MDPs.

Significance. The paper addresses a natural and under-studied setting, and its bounds are genuinely distribution-free in the sense that they use only moments, supports, or sub-Gaussian parameters through standard external inequalities; no constants are fitted to the data, and the lower-bound LP is a new element. If the claims are taken with the stationary-policy qualification in the random-transition case, the results provide a practical certificate-style gap analysis for chance-constrained CMDPs. The numerical study is substantial and compares the proposed bounds with existing elliptical-distribution bounds, showing the value of distributional information. The main limitation is the scope gap for random transitions discussed below, which affects the advertised JCCMDP claim rather than the internal validity of the restricted results.

major comments (1)
  1. [§4, (19), Lemma 8, Theorem 10, §6] The results of Section 4 are all stated for problem (19), the restriction of the JCCMDP to stationary policies, and the lower bound in Lemma 8, Theorem 10, and LP (37) is only proved to be a lower bound for the optimal value of (19). Since a history-dependent policy can adapt to information about the realized transition matrix, the optimal value V_HD of (4) satisfies V_HD <= V_stat, and it is possible that V_HD < LB. In that case (37) is not a lower bound for (4), and the reported gap UB-LB does not certify epsilon-optimality for (4). Section 6 acknowledges the restriction, but the abstract and Section 1 present the contributions as bounds for the JCCMDP problem without this qualification. This is a load-bearing scope gap: either prove sufficient conditions under which the stationary restriction is without loss of optimality for (4), or explicitly reframe the Section 4 results as approximations of the stationary-policy restriction throughout, including the abstract and the epsilon-optimal policy statement.
minor comments (5)
  1. [Theorem 8(2), Theorem 9, Table 2] The expression typeset as `ln 1-p1/K` should be written as `ln((1-p1)/K)`. As printed it is ambiguous and could be read as `ln(1-p1/K)`, which would not match the target probability `1-(1-p1)/K` in (27b).
  2. [§6, Conclusions] The statement that the random-cost-and-transition case makes no assumption on the dependency structure overstates the paper, since Assumption 3.1 (known covariance) and Assumption 3.3 (independence of the perturbation vectors) are used by the upper-bound Theorems 8 and 9; only the lower-bound Theorem 10 is free of a dependence assumption.
  3. [Lemma 4] Lemma 4 asserts convexity on y in [0,1], but the expression is undefined at y=0, where p1^{y^{1/theta}}=1; the statement should use (0,1] or define an extended value at 0.
  4. [§5] The numerical experiments report average gaps but not standard deviations or instance-level spreads; given the infeasibility counts in Figure 2(b), reporting dispersion would make the comparison more informative.
  5. [§5] No code is released. Providing the instance-generation seeds and solver settings would improve reproducibility of the reported gaps and CPU times.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the bounds derive from external probability inequalities and the self-cited JCCMDP-to-LP reduction is a published, parameter-free equivalence.

full rationale

The derivation chain is free of circular reductions. Lemma 1 and Lemma 2 are quoted from the authors' prior work [15], but the JCCMDP-to-LP equivalence for known transition probabilities is a standard occupancy-measure result, and the copula reduction is a mathematical identity under the explicitly stated Gumbel-Hougaard assumption; neither is defined in terms of the paper's target quantities, nor fitted to the numerical instances. The upper bounds in Theorems 5, 6, 8, and 9 are direct applications of external inequalities (one-sided Chebyshev, Hoeffding, sub-Gaussian, Bernstein) to linear chance constraints, with no calibrated constants. The lower bounds in Theorems 7 and 10 use the paper's own linear outer approximation (Theorem 4), whose proof is an indicator-function/Markov argument independent of the final claims. The Section 4 results concern the stationary-policy restriction (19) rather than the history-dependent problem (4); this is a scope limitation explicitly acknowledged in Section 6 and not a circular reduction. No fitted input is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

The central bounds rest on standard probability inequalities, a copula dependence assumption for random costs, exact knowledge of moments and support bounds, and a stationary-policy restriction for random transitions. No new physical entities are introduced. The h, lambda, and N parameters are user-chosen and affect tightness, not validity.

free parameters (4)
  • Bernstein scaling constants h_rc^0, h_rc^k, h_rp^0, h_rp^k = 10 in experiments
    Arbitrary positive constants in Theorems 6 and 9; the bounds hold for any positive value, but tightness and feasibility depend on the choice.
  • Tangent point set for linearization of p1^{y^{1/theta}} = N = 20, points in (0.1, 1)
    Chosen by hand in Lemma 5 and Theorem 7; larger N gives a tighter LP lower bound at higher computational cost.
  • Regularization constants lambda_rc_c, lambda_rc_d, lambda_rp_c, lambda_rp_dk = 1e-5
    Small positive constants in Theorem 4 used to keep m bounded away from zero; they do not affect validity of the bounds.
  • Copula parameter theta = varied in experiments
    Model input characterizing dependence under the Gumbel-Hougaard copula; assumed known rather than estimated from data.
assumptions (7)
  • domain assumption Dependence among random constraint vectors follows a Gumbel-Hougaard copula independent of the decision vector.
    Assumption 1 in Section 3; used to transform the joint chance constraint (10b) into individual chance constraints in Lemma 2.
  • domain assumption Mean vectors, covariance matrices, and componentwise upper and lower bounds of random costs are known exactly.
    Assumption 2 in Section 3 and Assumption 3 in Section 4; the approximations require these quantities as inputs.
  • domain assumption Transition probability perturbations have zero mean, known componentwise bounds with zeta_l <= 0 <= zeta_u, and row sums equal to zero.
    Equation (21) and surrounding text in Section 4; these properties are used to bound the random expected discounted costs.
  • domain assumption For random transition probabilities, optimality is sought only over stationary policies.
    Problem (19) in Section 4 explicitly restricts the JCCMDP to stationary policies because random transitions make even stationary expected costs nonlinear.
  • standard math Standard probability inequalities: one-sided Chebyshev, Hoeffding, Bernstein, and sub-Gaussian tail bounds.
    Theorems 2 and 3 in Section 2.2 provide the external inequalities used to construct all upper bound approximations.
  • standard math Sklar's theorem and the copula representation of joint distributions.
    Theorem 1 in Section 2.1 supports the copula-based reduction of the joint chance constraint.
  • domain assumption Linear programming equivalence of a discounted CMDP with known parameters.
    Equation (2) and the occupation measure set Q_alpha(gamma) come from Altman [1]; used throughout as the base LP formulation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Convex Approximations of Random Constrained Markov Decision Processes." pith.science (2026). https://pith.science/paper/RQCEHJ2Y

@misc{pith2026250524815,
  author       = {Pith},
  title        = {Pith review of: Convex Approximations of Random Constrained Markov Decision Processes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RQCEHJ2Y}},
  note         = {Machine review of arXiv:2505.24815}
}
read the original abstract

Constrained Markov decision processes (CMDPs) are used as a decision-making framework to study the long-run performance of a stochastic system. It is well-known that a stationary optimal policy of a CMDP problem under discounted cost criterion can be obtained by solving a linear programming problem when running costs and transition probabilities are exactly known. In this paper, we consider a discounted cost CMDP problem where the running costs and transition probabilities are defined using random variables. Consequently, both the objective function and constraints become random. We use chance constraints to model these uncertainties and formulate the uncertain CMDP problem as a joint chance-constrained Markov decision process (JCCMDP). Under random running costs, we assume that the dependency among random constraint vectors is driven by a Gumbel-Hougaard copula. Using standard probability inequalities, we construct convex upper bound approximations of the JCCMDP problem under certain conditions on random running costs. In addition, we propose a linear programming problem whose optimal value gives a lower bound to the optimal value of the JCCMDP problem. When both running costs and transition probabilities are random, we define the latter variables as a sum of their means and random perturbations. Under mild conditions on the random perturbations and random running costs, we construct convex upper and lower bound approximations of the JCCMDP problem. We analyse the quality of the derived bounds through numerical experiments on a queueing control problem for random running costs. For the case when both running costs and transition probabilities are random, we choose randomly generated Markov decision problems called Garnets for numerical experiments.

Figures

Figures reproduced from arXiv: 2505.24815 by the authors.

Figure 1
Figure 1. In 1(a), ‘∗’,‘o’, and ‘∆’, ‘|’, ‘−’, and ‘×’ indicate the average gaps corresponding to (12) under part 1 of Theorem 5, (14), and approximations of [15] under Gaussian, T-Student(5), Logistic, and T-Student(1) distributions, respectively. In 1(b), ‘∗’,‘o’, ‘∆’, ‘|’, and ‘−’ indicate the percentage reduction in the average upper bound values when we switch the approximations in the following order: (12) under part 1 … view at source ↗
Figure 2
Figure 2. In 2(a), ‘∗’, ‘∆’, and ‘o’ indicate the average gaps corresponding to (31) under parts 1-2 of Theorem 8, and (32), respectively. In 2(b), these indicate the number of instances with a feasible solution. α, with the best gap obtained corresponding to (32). For relatively higher values of η and α, fewer than 50 instances of the upper bound approximations yield feasible solutions, and the resulting gaps are larger than… view at source ↗
Figure 3
Figure 3. In 3(a), ‘∗’,‘o’, and ‘∆’, ‘|’, ‘−’, and ‘×’ indicate the average percentage reduction in the gaps corresponding to (12) under part 1 of Theorem 5, (14), and approximations of [15] under Gaussian, T-Student(5), Logistic, and T-Student(1) distributions, respectively. In 3(b), ‘∗’,‘o’, and ‘∆’ correspond to (31) under part 1 of Theorem 8, (32), and (31) under part 2 of Theorem 8, respectively. 6 Conclusions We study a… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 29 canonical work pages

  1. [15]

    Joint cha nce-constrained Markov decision processes

    V Varagapriya, Vikas Vikram Singh, and Abdel Lisser. “Joint cha nce-constrained Markov decision processes”. In: Annals of Operations Research 322 (2023), pp. 1013–1035. 29

    work page 2023

  2. [1]

    E. Altman. Constrained Markov Decision Processes . London: Chapman and Hall/CRC, 1999

    work page 1999

  3. [2]

    Puterman

    Martin L. Puterman. Markov Decision Process . 1st. USA: John Wiley & Sons, 1994

    work page 1994

  4. [3]

    Dynamic programming and optimal control

    Dimitri Bertsekas. Dynamic programming and optimal control . 3rd. Vol. I. Belmont, MA, USA: Athena scientific, 2005

    work page 2005

  5. [4]

    A linear programming approach to nonstationary infinite-horizon Markov decision processes

    Archis Ghate and Robert L Smith. “A linear programming approach to nonstationary infinite-horizon Markov decision processes”. In: Operations Research 61.2 (2013), pp. 413– 425

    work page 2013

  6. [5]

    Solution and forecast h orizons for infinite-horizon nonhomogeneous Markov decision processes

    Torpong Cheevaprawatdomrong et al. “Solution and forecast h orizons for infinite-horizon nonhomogeneous Markov decision processes”. In: Mathematics of Operations Research 32.1 (2007), pp. 51–72

    work page 2007

  7. [6]

    Bias and variance approximation in value functio n estimates

    Shie Mannor et al. “Bias and variance approximation in value functio n estimates”. In: Management Science 53.2 (2007), pp. 308–322

    work page 2007

  8. [7]

    Markovian decision processes with uncertain transition probabilities

    Jay K Satia and Roy E Lave Jr. “Markovian decision processes with uncertain transition probabilities”. In: Operations Research 21.3 (1973), pp. 728–740

    work page 1973

Show all 30 references
  1. [8]

    Bounded-param eter Markov decision processes

    Robert Givan, Sonia Leach, and Thomas Dean. “Bounded-param eter Markov decision processes”. In: Artificial Intelligence 122.1-2 (2000), pp. 71–109

    2000

  2. [9]

    Robust control of Markov decision processes with uncertain transition matrices

    Arnab Nilim and Laurent El Ghaoui. “Robust control of Markov decision processes with uncertain transition matrices”. In: Operations Research 53.5 (2005), pp. 780–798

    2005

  3. [10]

    Robust dynamic programming

    Garud N Iyengar. “Robust dynamic programming”. In: Mathematics of Operations Re- search 30.2 (2005), pp. 257–280

    2005

  4. [11]

    Robust Markov decision pro- cesses

    Wolfram Wiesemann, Daniel Kuhn, and Ber¸ c Rustem. “Robust Markov decision pro- cesses”. In: Mathematics of Operations Research 38.1 (2013), pp. 153–183

    2013

  5. [12]

    Constra ined Markov decision processes with uncertain costs

    V Varagapriya, Vikas Vikram Singh, and Abdel Lisser. “Constra ined Markov decision processes with uncertain costs”. In: Operations Research Letters 50.2 (2022), pp. 218–

    2022

  6. [13]

    Rank-1 t ransition uncertainties in constrained Markov decision processes

    V Varagapriya, Vikas Vikram Singh, and Abdel Lisser. “Rank-1 t ransition uncertainties in constrained Markov decision processes”. In: European Journal of Operational Research 318.1 (2024), pp. 167–178

    2024

  7. [14]

    Percentile optimization for Markov decision processes with parameter uncertainty

    Erick Delage and Shie Mannor. “Percentile optimization for Markov decision processes with parameter uncertainty”. In: Operations Research 58.1 (Jan. 2010), pp. 203–213

    2010

  8. [16]

    Roger B. Nelsen. An Introduction to Copulas (Springer Series in Statistics) . Berlin, Hei- delberg: Springer-Verlag, 2006. isbn: 0387286594

    2006

  9. [17]

    Copula theory and its applications

    Piotr Jaworski et al. Copula theory and its applications. Proceedings of the work shop held in Warsaw, Poland, 25–26 September 2009 . Jan. 2010. isbn: 978-3-642-12464-8

    2009

  10. [18]

    Chance con strained 0–1 quadratic programs using copulas

    Jianqiang Cheng, Michal Houda, and Abdel Lisser. “Chance con strained 0–1 quadratic programs using copulas”. In: Optimization Letters 9 (2015), pp. 1283–1295

    2015

  11. [19]

    Deterministic approximations of probability inequ alities

    Janos Pinter. “Deterministic approximations of probability inequ alities”. In: Zeitschrift f¨ ur Operations-Research33.4 (1989), pp. 219–239

    1989

  12. [20]

    Probability inequalities for sums of bounded ra ndom variables

    Wassily Hoeffding. “Probability inequalities for sums of bounded ra ndom variables”. In: Journal of the American Statistical Association 58.301 (1963), pp. 13–30

    1963

  13. [21]

    High-dimensional statistics: A non-asymptotic viewpoint

    Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint . Vol. 48. Cambridge university press, 2019

    2019

  14. [22]

    A sample approximation app roach for optimization with probabilistic constraints

    James Luedtke and Shabbir Ahmed. “A sample approximation app roach for optimization with probabilistic constraints”. In: SIAM Journal on Optimization 19.2 (2008), pp. 674– 699

    2008

  15. [23]

    Convex relaxations of chance constrained op timization problems

    Shabbir Ahmed. “Convex relaxations of chance constrained op timization problems”. In: Optimization Letters 8 (2014), pp. 1–12

    2014

  16. [24]

    Bounds fo r probabilistic programming with application to a blend planning problem

    Shen Peng, Francesca Maggioni, and Abdel Lisser. “Bounds fo r probabilistic programming with application to a blend planning problem”. In: European Journal of Operational Research 297.3 (2022), pp. 964–976

    2022

  17. [25]

    Primal-dual interior-point methods

    Stephen J Wright. Primal-dual interior-point methods . Society for Industrial and Applied Mathematics, 1997

    1997

  18. [26]

    Convex approxima tions of chance constrained programs

    Arkadi Nemirovski and Alexander Shapiro. “Convex approxima tions of chance constrained programs”. In: SIAM Journal on Optimization 17.4 (2007), pp. 969–996

    2007

  19. [27]

    Applications of second-order cone pr ogramming

    Miguel Sousa Lobo et al. “Applications of second-order cone pr ogramming”. In: Linear Algebra and its Applications 284 (1998), pp. 193–228

    1998

  20. [28]

    On the ge neration of Markov decision processes

    T. W. Archibald, K. I. M. McKinnon, and L. C. Thomas. “On the ge neration of Markov decision processes”. In: Journal of the Operational Research Society 46.3 (1995), pp. 354– 361

    1995

  21. [29]

    Score-based inverse Reinforcement Lear ning

    Layla El Asri et al. “Score-based inverse Reinforcement Lear ning”. In: Proceedings of the 2016 International Conference on Autonomous Agents & Mu ltiagent Systems . AA- MAS ’16. Singapore, Singapore: International Foundation for Aut onomous Agents and Multiagent Systems, 2016...

    2016

  22. [30]

    Symmetric Multivariate and Related Distributions

    Kai-Tai Fang, Samuel Kotz, and Kai Wang Ng. Symmetric Multivariate and Related Distributions. London, New York: Chapman and Hall/CRC, 1990. isbn: 9781351077040. 30

    1990

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.