On the Fundamental Limitations of Dual Static CVaR Decompositions in Markov Decision Processes

• URL: http://arxiv.org/abs/2507.14005v1
• Date: Fri, 18 Jul 2025 15:18:19 GMT
• Title: On the Fundamental Limitations of Dual Static CVaR Decompositions in Markov Decision Processes
• Authors: Mathieu Godbout, Audrey Durand,
• Abstract summary: We show that evaluating the static CVaR of a given policy can be framed as two distinct minimization problems.<n>We then leverage our proposed risk-assignment perspective to prove that the search for a single, uniformly optimal policy via on the dual CVaR decomposition is fundamentally limited.
• Score: 5.66364012434579
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work has shown that dynamic programming (DP) methods for finding static CVaR-optimal policies in Markov Decision Processes (MDPs) can fail when based on the dual formulation, yet the root cause for the failure has remained unclear. We expand on these findings by shifting focus from policy optimization to the seemingly simpler task of policy evaluation. We show that evaluating the static CVaR of a given policy can be framed as two distinct minimization problems. For their solutions to match, a set of ``risk-assignment consistency constraints'' must be satisfied, and we demonstrate that the intersection of the constraints being empty is the source of previously observed evaluation errors. Quantifying the evaluation error as the CVaR evaluation gap, we then demonstrate that the issues observed when optimizing over the dual-based CVaR DP are explained by the returned policy having a non-zero CVaR evaluation gap. We then leverage our proposed risk-assignment perspective to prove that the search for a single, uniformly optimal policy via on the dual CVaR decomposition is fundamentally limited, identifying an MDP where no single policy can be optimal across all initial risk levels.

Related papers

• Policy Testing in Markov Decision Processes [48.642181362172906]
  We study the policy testing problem in discounted decision processes (MDP) under the fixed-confidence setting.<n>The goal is to determine whether the value of a given policy exceeds a numerical threshold.
  arXiv  Detail & Related papers  (2025-05-21T10:13:54Z)
• Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form [26.01796404477275]
  This paper presents the first algorithm guaranteed to identify a near-optimal policy in a robust constrained MDP (RCMDP)<n>An optimal policy minimizes cumulative cost while satisfying constraints in the worst-case scenario across a set of environments.
  arXiv  Detail & Related papers  (2024-08-29T06:37:16Z)
• Robust Risk-Sensitive Reinforcement Learning with Conditional Value-at-Risk [23.63388546004777]
  We analyze the robustness of CVaR-based risk-sensitive RL under Robust Markov Decision Processes. Motivated by the existence of decision-dependent uncertainty in real-world problems, we study problems with state-action-dependent ambiguity sets.
  arXiv  Detail & Related papers  (2024-05-02T20:28:49Z)
• A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents [44.09686403685058]
  We study risk-sensitive RL where the goal is learn a history-dependent policy that optimize some risk measure of cumulative rewards.<n>We propose two meta-algorithms: one grounded in optimism and another based on policy gradients.<n>We empirically show that our algorithms learn the optimal history-dependent policy in a proof-of-concept MDP.
  arXiv  Detail & Related papers  (2024-03-10T21:45:12Z)
• Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
  We consider the problem of quantifying uncertainty over expected cumulative rewards in model-based reinforcement learning. We propose a new uncertainty Bellman equation (UBE) whose solution converges to the true posterior variance over values. We introduce a general-purpose policy optimization algorithm, Q-Uncertainty Soft Actor-Critic (QU-SAC) that can be applied for either risk-seeking or risk-averse policy optimization.
  arXiv  Detail & Related papers  (2023-12-07T15:55:58Z)
• High-probability sample complexities for policy evaluation with linear function approximation [88.87036653258977]
  We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms. We establish the first sample complexity bound with high-probability convergence guarantee that attains the optimal dependence on the tolerance level.
  arXiv  Detail & Related papers  (2023-05-30T12:58:39Z)
• Provable Offline Preference-Based Reinforcement Learning [95.00042541409901]
  We investigate the problem of offline Preference-based Reinforcement Learning (PbRL) with human feedback. We consider the general reward setting where the reward can be defined over the whole trajectory. We introduce a new single-policy concentrability coefficient, which can be upper bounded by the per-trajectory concentrability.
  arXiv  Detail & Related papers  (2023-05-24T07:11:26Z)
• Risk-Sensitive Markov Decision Processes with Long-Run CVaR Criterion [9.792654108885676]
  We study the infinite-horizon discrete-time Markov decision process (MDP) with a long-run CVaR criterion. We derive a pseudo CVaR difference formula which quantifies the difference of long-run CVaR under any two policies. We develop a policy type algorithm to efficiently optimize CVaR, which is shown to converge to local optima in the mixed policy space.
  arXiv  Detail & Related papers  (2022-10-17T04:29:14Z)
• Stochastic first-order methods for average-reward Markov decision processes [10.023632561462712]
  We study average-reward Markov decision processes (AMDPs) and develop novel first-order methods with strong theoretical guarantees for both policy optimization and policy evaluation. By combining the policy evaluation and policy optimization parts, we establish sample complexity results for solving AMDPs under both generative and Markovian noise models.
  arXiv  Detail & Related papers  (2022-05-11T23:02:46Z)
• COptiDICE: Offline Constrained Reinforcement Learning via Stationary Distribution Correction Estimation [73.17078343706909]
  offline constrained reinforcement learning (RL) problem, in which the agent aims to compute a policy that maximizes expected return while satisfying given cost constraints, learning only from a pre-collected dataset. We present an offline constrained RL algorithm that optimize the policy in the space of the stationary distribution. Our algorithm, COptiDICE, directly estimates the stationary distribution corrections of the optimal policy with respect to returns, while constraining the cost upper bound, with the goal of yielding a cost-conservative policy for actual constraint satisfaction.
  arXiv  Detail & Related papers  (2022-04-19T15:55:47Z)
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy [95.98698822755227]
  We make the first attempt to study risk-sensitive deep reinforcement learning under the average reward setting with the variance risk criteria. We propose an actor-critic algorithm that iteratively and efficiently updates the policy, the Lagrange multiplier, and the Fenchel dual variable.
  arXiv  Detail & Related papers  (2020-12-28T05:02:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.