RECORD
Dynamic Programming for Epistemic Uncertainty in Markov Decision Processes
Computer Science and Game Theory · Submitted 3 Feb 2026
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Our work draws connections among several variants of MDP models and fully delineates what is possible under the dynamic programming paradigm and which risk measures require leaving it.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
In this paper, we propose a general theory of ambiguity-averse MDPs, which treats the uncertain transition probabilities as random variables and evaluates a policy via a risk measure applied to its random return. This ambiguity-averse MDP framework unifies several models of MDPs with epistemic uncertainty for specific choices of risk measures. We extend the concepts of value functions and Bellman operators to our setting. Based on these objects, we establish the consequences of dynamic programming principles in this framework (existence of stationary policies, value and policy iteration algorithms), and we completely characterize law-invariant risk measures compatible with dynamic programming. Our work draws connections among several variants of MDP models and fully delineates what is possible under the dynamic programming paradigm and which risk measures require leaving it.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In this paper, we propose a general theory of ambiguity-averse MDPs, which treats the uncertain transition probabilities as random variables and evaluates a policy via a risk measure applied to its random return. | contribution 0.94 | 0.89 | 0.11 | asserted 1.00 |
| s1 | This ambiguity-averse MDP framework unifies several models of MDPs with epistemic uncertainty for specific choices of risk measures. | contribution 0.59 | 0.62 | 0.12 | asserted 1.00 |
| s2 | We extend the concepts of value functions and Bellman operators to our setting. | contribution 0.70 | 0.92 | 0.03 | asserted 0.98 |
| s3 | Based on these objects, we establish the consequences of dynamic programming principles in this framework (existence of stationary policies, value and policy iteration algorithms), and we completely characterize law-invariant risk measures compatible with dynamic programming. | contribution 0.66 | 0.95 | 0.39 | asserted 1.00 |
| s4 | Our work draws connections among several variants of MDP models and fully delineates what is possible under the dynamic programming paradigm and which risk measures require leaving it. | contribution 0.50 | 0.93 | 0.58 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
In this paper, we propose a general theory of ambiguity-averse MDPs, which treats the uncertain transition probabilities as random variables and evaluates a policy via a risk measure applied to its random return. This ambiguity-averse MDP framework unifies several models of MDPs with epistemic uncertainty for specific choices of risk measures. We extend the concepts of value functions and Bellman operators to our setting. Based on these objects, we establish the consequences of dynamic programming principles in this framework (existence of stationary policies, value and policy iteration algorithms), and we completely characterize law-invariant risk measures compatible with dynamic programming. Our work draws connections among several variants of MDP models and fully delineates what is possible under the dynamic programming paradigm and which risk measures require leaving it.
Human review
References
How the literature uses it
1 arXiv paper cite this in 1 sentence
What it cites · 12 sentences without a confident label
Compares with 1 paper
-
In fact, we note that our results closely align with the separations between NP-hard problems that require history-dependent policies (multi-model MDPs and percentile optimization with static kernels, e.g., [ref] ) and models that can be solved efficiently and for which optimal stationary policies exist (e.g., robust and optimistic MDPs for both static and resampled kernels, see [ref] ).
Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality · Discussion · 0.93
Cites as support 2 papers
-
Note that for robust MDPs to satisfy <ref>, the product structure is a necessary condition (as recently shown in [ref] ), and without the convexity requirement on the support of $ν$, even s-rectangular robust MDPs may fail to satisfy <ref> (see Table 3 and Table 4 in [ref] ).
On the Foundation of Distributionally Robust Reinforcement Learning · Dynamic programming · 0.97
-
Note that for robust MDPs to satisfy <ref>, the product structure is a necessary condition (as recently shown in [ref] ), and without the convexity requirement on the support of $ν$, even s-rectangular robust MDPs may fail to satisfy <ref> (see Table 3 and Table 4 in [ref] ).
Dynamic Programming-Compatible Uncertainty Sets in Robust Markov Decision Processes · Dynamic programming · 0.97
Cites as background 3 papers
-
Several other frameworks for MDPs with uncertain parameters exist, e.g., multi-model MDPs [ref] that optimize over the average of the return across plausible parameters, models based on value at risk (percentile optimization) [ref] , conditional value at risk () [ref] and the entropic risk measure () [ref] .
Entropic Risk Constrained Soft-Robust Policy Optimization · Introduction · 0.97
-
Several other frameworks for MDPs with uncertain parameters exist, e.g., multi-model MDPs [ref] that optimize over the average of the return across plausible parameters, models based on value at risk (percentile optimization) [ref] , conditional value at risk () [ref] and the entropic risk measure () [ref] .
Soft-Robust Algorithms for Batch Reinforcement Learning · Introduction · 0.97
-
Recent work on risk-averse MDPs has also focused on the Conditional Value-at-Risk () [ref] , the Entropic Risk Measure () and the Entropic Value-at-Risk () [ref] .
On the Fundamental Limitations of Dual Static CVaR Decompositions in Markov Decision Processes · Risk measures · 0.94
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.