Dynamic Programming for Epistemic Uncertainty in Markov Decision Processes

Axel Benyamine, Julien Grand-Clément, Marek Petrik, Michael I. Jordan, Alain Oliviero Durmus
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:7541-7578, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-benyamine26a, title = {Dynamic Programming for Epistemic Uncertainty in {M}arkov Decision Processes}, author = {Benyamine, Axel and Grand-Cl\'{e}ment, Julien and Petrik, Marek and Jordan, Michael I. and Oliviero Durmus, Alain}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {7541--7578}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/benyamine26a/benyamine26a.pdf}, url = {https://proceedings.mlr.press/v306/benyamine26a.html}, 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.} }
Endnote
%0 Conference Paper %T Dynamic Programming for Epistemic Uncertainty in Markov Decision Processes %A Axel Benyamine %A Julien Grand-Clément %A Marek Petrik %A Michael I. Jordan %A Alain Oliviero Durmus %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-benyamine26a %I PMLR %P 7541--7578 %U https://proceedings.mlr.press/v306/benyamine26a.html %V 306 %X 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.
APA
Benyamine, A., Grand-Clément, J., Petrik, M., Jordan, M.I. & Oliviero Durmus, A.. (2026). Dynamic Programming for Epistemic Uncertainty in Markov Decision Processes. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:7541-7578 Available from https://proceedings.mlr.press/v306/benyamine26a.html.

Related Material