betaFeedback

WorksComputer Science

Reward Objectives for Robust (PO)MDPs: A Law-Preserving Equivalence with (Partially Observable) Games

Abstract

Robust partially observable Markov decision processes model agents that act under partial observability while adversarial environment resolves uncertainty in the transition probabilities. Reward objectives such as discounted-sum, long-run average and cumulative reward under finite and infinite horizons allow quantifying the utility of an agent. We consider the problem of solving RPOMDPs under all four reward objectives, where the goal is to decide whether the value of a risk measure with respect to a reward objective exceeds a given threshold. We consider different risk measures, such as (1)~expected value, (2)~mean-variance (MV), (3)~conditional value-at-risk (CVaR), and (4)~entropic risk (ERisk). Our results can be summarized as follows. First, we formalize the class of law-invariant risk measures, that subsume all four risk measures above. Second, we propose a unified framework for solving RPOMDPs with discounted-sum, long-run average and cumulative reward objectives under any law-invariant risk measure, by reducing the problem to solving partially observable stochastic games (POSGs). Our unified framework applies to (s,a)-rectangular RPOMDPs with polytopic uncertainty sets, which we show to be equivalent to POSGs, for each of the four reward objectives and any law-invariant risk measure. We prove equivalence by designing logspace reductions between the RPOMDP and POSG models, that map strategies to strategies and preserve the distribution of the reward objective, up to a constant rescaling factor. Third, as a corollary, we derive new computational complexity results for R(PO)MDPs and POSGs. In particular, we show that solving (s,a)-rectangular RMDPs is as hard as solving simple stochastic games.

Introduction

Partially observable Markov decision processes (POMDPs) are the standard model of an agent acting under partial observability in the presence of stochastic uncertainty [23]. The key limitation of POMDPs, however, is that their transition probabilities are assumed to be fully known. This is a strong assumption in the settings where transition probabilities are e.g. estimated from data. Robust MDPs (RMDPs) [22, 34, 51] and, more generally, robust POMDPs (RPOMDPs) [37, 6], account for this by replacing fully known transition probabilities with an uncertainty set of transition probabilities, with the adversarial environment being able to choose transition probabilities from this uncertainty set. Recent years have seen significant interest in solving R(PO)MDPs with reward objectives, such as discounted-sum reward [35, 22, 24, 47, 17, 20, 2] or long-run average reward objectives [49, 19, 18, 50, 9, 32]. The goal in solving an RPOMDP is to compute a strategy that maximizes the expected value of the reward objective. Existing works largely focused on designing efficient algorithms for solving RMDPs. Solving RPOMDPs, which also account for partial observability, has been considered in [6, 37, 7, 46, 33, 13, 16, 25]. These works all focus on computing a strategy that maximizes the expected value (EE) of the reward objective. However, while providing valuable information on the average-case performance of the strategy, expected value alone does not consider the variability of possible outcomes. Two strategies that achieve the same expected reward objective value may carry very different risks. This is why expected value is sometimes replaced by other risk measures such as mean-variance [30], conditional value-at-risk (CVaR) [42, 10], or entropic risk [21, 3]. However, computing strategies that optimize these risk measures has so far mostly been studied for MDPs, but not for robust models such as RMDPs or RPOMDPs. The goal of this work is to address this gap.

We present a unified framework for solving RPOMDPs with reward objectives and different risk measures, by reducing the problem to solving partially observable stochastic games (POSGs). Our framework applies to discounted-sum, long-run average and total reward under finite and infinite horizons objectives, and under any law-invariant risk measure. A risk measure is said to be law-invariant, if it only depends on the probability distribution of the value of the reward objective over RPOMDP runs. We show that common risk measures such as (1) expected value (EE), (2) mean-variance (MV), (3) conditional value-at-risk (CVaR), and (4) entropic risk (ERisk) are all law-invariant. Hence, our unified framework applies to all these risk measures.

We consider (s,a)(s,a)-rectangular RPOMDPs with polytopic uncertainty sets, which we show to be equivalent to POSGs. For each of the four reward objectives and under any law-invariant risk measure, we design two logspace reductions: one from RPOMDPs to POSGs, and one from POSGs to RPOMDPs. Our reductions map strategies to strategies and are law preserving, meaning that the image of every strategy achieves the same distribution of the reward objective value (up to the reward objective being normalized by a constant rescaling factor), thus mapping optimal strategies to optimal strategies under any law-invariant risk measure. Hence, we can reduce the problem of solving an RPOMDP to solving a POSG under the same reward objective and risk measure and vice-versa. In the case of RMDPs (with full observability), our reductions establish equivalence with turn-based stochastic games (TBSGs) [44, 11].

Building upon our equivalence result, we study the threshold problems for law-invariant risk measures such as E, MV, CVaR, and ERisk with rational parameters, and for the finite and infinite horizon total, long-run average and discounted-sum reward objectives. We consider the non-strict and strict threshold problems: given a model (RPOMDP/RMDP/POSG/TBSG), a risk measure Ψ\Psi, a reward objective XX, and a rational tt, decide whether a player in the RPOMDP/RMDP (or the maximizing player in POSG/TBSG) can guarantee a value of Ψ\Psi on the reward objective XX that is greater than tt (strict threshold), or greater or equal than tt (non-strict threshold). Table 1 summarizes our novel complexity results. Under partial observation, both variants are PSPACE-hard and decidable for finite horizon total reward, and undecidable for infinite horizon total reward and for long-run average reward objectives. For discounted-sum rewards, values can be approximated to any precision, which makes the strict problem recursively enumerable; it is nevertheless undecidable for E and CVaR, while for discounted mean-variance and entropic risk the decidability of the threshold problems remains open. Under full observation, both variants are SSG-hard for RMDPs with total or long-run average rewards for all four risk measures, and for discounted-sum rewards for the expected value. For the expected discounted-sum and the long-run average reward, the SSG bound is tight, since both problems lie in NP ∩\cap coNP. Here, SSG stands for the complexity of solving simple stochastic games, which is known to be in NP ∩\cap coNP [11] but the question of whether there exists a polynomial algorithm is an open problem.

Our contributions can be summarized as follows:

  1. Law-invariant risk measures. We formalize law-invariant risk measures for reward objectives in RPOMDPs. These include (1) expected value (E), (2) mean-variance (MV), (3) conditional value-at-risk (CVaR), and (4) entropic risk (ERisk).

  1. Equivalence of RPOMDPs and POSGs. We present a unified framework for solving RPOMDPs with reward objectives and law-invariant risk measures, by reducing the problem to solving

POSGs. Our framework applies to (s,a)(s,a)-rectangular polytopic RPOMDPs with discounted-sum, long-run average, total and finite-horizon reward objectives. It is based on our novel equivalence result between RPOMDPs and POSGs obtained via logspace reductions in both directions. In the case of RMDPs (with full observability), we obtain equivalence with TBSGs.

  1. Uniform complexity landscape. We derive new computational complexity results and provide a complexity landscape for RPOMDPs (and POSGs) under reward objectives and law-invariant risk measures.

Preliminaries

We write N={0,1,2,…}\mathbb{N} = \{0,1,2,\ldots\}, Q\mathbb{Q}, and R\mathbb{R} for the sets of natural, rational, and real numbers. For a finite set YY, we use Δ(Y)\Delta(Y) to denote the set of probability distributions over YY, and Dirac⁡(y)\operatorname{Dirac}(y) the distribution with all probability mass on y∈Yy \in Y. We write R‾=[−∞,+∞]\overline{\mathbb{R}} = [-\infty,+\infty] and D(R‾)\mathcal{D}(\overline{\mathbb{R}}) for the set of Borel probability measures on R‾\overline{\mathbb{R}}, which we call laws. For a random variable X:Ω→R‾X:\Omega\to\overline{\mathbb{R}} on a probability space (Ω,F,P)(\Omega,\mathcal{F},\mathbb{P}) and a Borel set B⊆R‾B \subseteq\overline{\mathbb{R}}, let X−1(B)={ω∈Ω:X(ω)∈B}X^{-1}(B) = \{\omega\in\Omega: X(\omega) \in B\} be the set of outcomes that XX maps into BB. The law of XX is the measure LX(B)=P(X−1(B))=P(X∈B)\mathcal{L}_X(B) = \mathbb{P}(X^{-1}(B)) = \mathbb{P}(X \in B). For c>0c > 0 and a law μ\mu, we write (Sc)#μ(S_c)_\#\mu for the law of cXcX when XX has law μ\mu, i.e., (Sc)#μ(B)=μ({x:cx∈B})(S_c)_\#\mu(B) = \mu(\{x : cx \in B\}) for every Borel set BB.

Robust POMDPs

RPOMDPs. A robust POMDP (RPOMDP) is a tuple

M=(S,A,P,s0,Oa,Oe,Za,Ze,r).\mathcal{M} = (S,A,\mathcal{P},s_0,\mathcal{O}_a,\mathcal{O}_e,Z_a,Z_e,r).

where SS and AA are finite sets of states and actions, s0∈Ss_0 \in S is the initial state, and Oa\mathcal{O}_a and Oe\mathcal{O}_e are finite sets of observations of the agent and of the environment, with observation functions Za:S→OaZ_a:S \to\mathcal{O}_a and Ze:S→OeZ_e:S \to\mathcal{O}_e. The reward function is r:S×A×S→Qr:S \times A \times S \to\mathbb{Q}. The uncertainty set is given by P⊆(S×A→Δ(S))\mathcal{P} \subseteq(S \times A \to\Delta(S)).

A POMDP is an RPOMDP in which P\mathcal{P} is a singleton, specifying for each state-action pair in S×AS \times A a single probability distribution over successor states. An RMDP is an RPOMDP in which ZaZ_a and ZeZ_e are injective, i.e., every observation corresponds to a unique state. An MDP is an RPOMDP that satisfies both conditions above.

Assumptions. As is standard in the algorithmic study of robust Markov models [22, 51, 9, 28], we consider (s,a)(s,a)-rectangular polytopic uncertainty sets of the form P=∏(s,a)∈S×AP(s,a)\mathcal{P} = \prod_{(s,a)\in S \times A}\mathcal{P}(s,a), where the environment chooses transition probabilities independently across state-action pairs, with each P(s,a)⊆Δ(S)\mathcal{P}(s,a) \subseteq\Delta(S) being a polytope with a finite vertex set Vs,aV_{s,a}. P(s,a)={∑i=1∣Vs,a∣αivi∣αi∈[0,1], ∑iαi=1, vi∈Vs,a}\mathcal{P}(s,a) = \left\{\sum_{i=1}^{|V_{s,a}|}\alpha_i v_i \mid\alpha_i \in[0,1],\ \sum_i \alpha_i = 1,\ v_i \in V_{s,a}\right\}, each vertex v∈Vs,av \in V_{s,a} has the form (x1,…,x∣S∣)(x_1,\ldots,x_{|S|}) with xi≥0x_i \ge0 and ∑ixi=1\sum_i x_i = 1. We assume that the uncertainty set P\mathcal{P} is given in the vertex set representation.

Semantics. The RPOMDP starts in s0s_0 and proceeds in steps t=0,1,…t = 0,1,\ldots to generate a random infinite play. If at time tt the RPOMDP is in state sts_t, the agent receives the observation Za(st)Z_a(s_t) and chooses an action at∈Aa_t \in A. The environment receives the observation Ze(st)Z_e(s_t) and selects a probabilistic transition function Pt∈PP_t \in\mathcal{P}; the next state st+1s_{t+1} is drawn from Pt(st,at)P_t(s_t,a_t), and the transition earns the reward rt=r(st,at,st+1)r_t = r(s_t,a_t,s_{t+1}). This follows the RPOMDP game semantics of [6] for dynamic uncertainty, in which the environment may choose a new assignment in every step.

The semantics are formalized via agent and environment strategies. A history is a finite sequence ht=s0,a0,s1,…,st∈(S×A)∗h_t = s_0,a_0,s_1,\ldots,s_t \in(S \times A)^*. An agent observation history for history hth_t is a sequence h=o0ao1a⋯ota∈Oa+h = o^{a}_{0}o^{a}_{1}\cdots o^{a}_{t} \in O_{a}^{+} of observations of the agent such that ota=Za(st)o^{a}_{t} = Z_{a}(s_{t}), and let Ha\mathcal{H}_{a} denote the set of agent observation histories. Then, an agent strategy is a map σ:Ha→Δ(A)\sigma: \mathcal{H}_{a} \to\Delta(A). Likewise, an environment observation history of hth_{t} is a sequence h=o0eo1e⋯ote∈Oe+h = o^{e}_{0}o^{e}_{1}\cdots o^{e}_{t} \in O_{e}^{+} of observations of the environment, and let He\mathcal{H}_{e} denote the set of environment observation histories. Then, an environment strategy is a map π:He×A→P\pi: \mathcal{H}_{e} \times A \to\mathcal{P}. We write ΣM\Sigma_{M} and ΠM\Pi_{M} for the sets of agent and environment strategies. A play is an infinite sequence ρ=s0a0s1a1⋯\rho= s_{0}a_{0}s_{1}a_{1}\cdots, and its reward sequence is (rt)t≥0(r_{t})_{t\geq0} with rt=r(st,at,st+1)r_{t} = r(s_{t}, a_{t}, s_{t+1}). A strategy profile (σ,π)(\sigma, \pi) induces a unique probability measure PMσ,π\mathbb{P}^{\sigma,\pi}_{M} on plays [41] under which a prefix s0a0⋯sts_{0}a_{0}\cdots s_{t} is extended by at+1st+1a_{t+1}s_{t+1} with probability

σ(hta)(at)⋅π(hte)(st,at)(st+1),\sigma(h^{a}_{t})(a_{t}) \cdot\pi(h^{e}_{t})(s_{t},a_{t})(s_{t+1}),

where hta=Za(s0)⋯Za(st)h^{a}_{t} = Z_{a}(s_{0})\cdots Z_{a}(s_{t}) is the history of the agent and hte=Ze(s0)⋯Ze(st)h^{e}_{t} = Z_{e}(s_{0})\cdots Z_{e}(s_{t}) is the history of the environment.

Without loss of generality, we adopt a standard assumption for RPOMDPs (and, later, for POSGs) that every action in the action alphabet of a decision maker is enabled at every state. We call an action effective at a state if the construction explicitly specifies its transition there, and an effective edge is a transition of positive probability under an effective action. In figures, we draw only effective actions and edges. Every omitted state-action pair is implicitly completed by a transition to an absorbing sink that is worst possible for the decision maker who chose the action.

Partially Observable Stochastic Games

POSGs. A turn-based partially observable stochastic game (POSG) between the players max and min is a tuple

References

  1. [1]Daniel Andersson and Peter Bro Miltersen. The complexity of solving stochastic games on graphs. In International Symposium on Algorithms and Computation, pages 112–121. Springer, 2009.DOI
  2. [2]Ali Asadi, Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Alipasha Montaseri, and Carlo Pagano. Strongly polynomial time complexity of policy iteration for l∞ robust mdps. CoRR, abs/2601.23229, 2026. URL https://doi.org/10.48550/arXiv.2601.23229.
  3. [3]Christel Baier, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer. Entropic risk for turn-based stochastic games. Information and Computation, 301:105214, 2024.
  4. [4]Alan Baker. Transcendental number theory. Cambridge university press, 2022.
  5. [5]Patrick Billingsley. Probability and Measure. New York, 3rd edition, 1995.
  6. [6]Eline M. Boy, Marnix Suilen, Sebastian Junges, and Nils Jansen. Imprecise probabilities meet partial observability: Game semantics for robust POMDPs. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pages 6697–6706, 2024.
  7. [7]Mahmoud El Chamie and Hala Mostafa. Robust action selection in partially observable markov decision processes with model uncertainty. In 57th IEEE Conference on Decision and Control, CDC 2018, Miami, FL, USA, December 17-19, 2018, pages 5586–5591, 2018. URL https://doi.org/10.1109/CDC.2018.8619468.
  8. [8]Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. A survey of partial-observation stochastic parity games. Formal Methods Syst. Des., 43(2):268–284, 2013. URL https://doi.org/10.1007/s10703-012-0164-2.
  9. [9]Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Mehrdad Karrabi, Petr Novotný, and Đorđe Žikelíć. Solving long-run average reward robust MDPs via stochastic games. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pages 6707–6715, 2024.arxiv.org/abs/2312.13912
  10. [10]Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision-making: a cvar optimization approach. Advances in neural information processing systems, 28, 2015.arxiv.org/abs/1506.02188
  11. [11]Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203–224, 1992.DOI
  12. [12]Anne Condon and Richard J. Lipton. On the complexity of space bounded interactive proofs. In FOCS, volume 89, pages 462–467, 1989.DOI
  13. [13]Murat Cubuktepe, Nils Jansen, Sebastian Junges, Ahmadreza Marandi, Marnix Suilen, and Ufuk Topcu. Robust finite-state controllers for uncertain pomdps. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 11792–11800, 2021. URL https://doi.org/10.1609/aaai.v35i13.17401.
  14. [14]Jerzy A. Filar, Lodewijk C. M. Kallenberg, and Huey-Min Lee. Variance-penalized Markov decision processes. Mathematics of Operations Research, 14(1):147–161, 1989.DOI
  15. [15]Hans Föllmer and Alexander Schied. Stochastic Finance: An Introduction in Discrete Time. De Gruyter, 4th edition, 2016.
  16. [16]Maris F. L. Galesloot, Roman Andriushchenko, Milan Ceska, Sebastian Junges, and Nils Jansen. Robust finite-memory policy gradients for hidden-model pomdps. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 8518–8526, 2025. URL https://doi.org/10.24963/ijcai.2025/947.
  17. [17]Mohammad Ghavamzadeh, Marek Petrik, and Yinlam Chow. Safe policy improvement by minimizing robust baseline regret. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2298–2306, 2016. URL https://proceedings.neurips.cc/paper/2016/hash/9a3d458322d70046f63dfd8b0153ece4-Abstract.html.arxiv.org/abs/1607.03842
  18. [18]Vineet Goyal and Julien Grand-Clément. Robust markov decision processes: Beyond rectangularity. Math. Oper. Res., 48(1):203–226, 2023. URL https://doi.org/10.1287/moor.2022.1259.
  19. [19]Julien Grand-Clément and Marek Petrik. Reducing blackwell and average optimality to discounted mdps via the blackwell discount factor. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 52628–52647. Curran Associates, Inc., 2023. doi: 10.52202/075280-2292. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/a4e720ce31ccd8ba747d8863e1580fa8-Paper-Conference.pdf.
  20. [20]Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for l1-robust markov decision processes. J. Mach. Learn. Res., 22:275:1–275:46, 2021. URL https://jmlr.org/papers/v22/20-445.html.
  21. [21]Ronald A. Howard and James E. Matheson. Risk-sensitive Markov decision processes. Management Science, 18(7):356–369, 1972.DOI
  22. [22]Garud N. Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257–280, 2005.DOI
  23. [23]Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1–2):99–134, 1998.DOI
  24. [24]David L. Kaufman and Andrew J. Schaefer. Robust modified policy iteration. INFORMS J. Comput., 25(3):396–410, 2013. doi: 10.1287/IJOC.1120.0509. URL https://doi.org/10.1287/ijoc.1120.0509.
  25. [25]Merlijn Krale, Eline M. Bovy, Maris F. L. Galesloot, Thiago D. Simão, and Nils Jansen. On evaluating policies for robust POMDPs. In Eighteenth European Workshop on Reinforcement Learning, 2025. URL https://openreview.net/forum?id=Q1qM9iF3iH.DOI
  26. [26]Jan Křetínský and Tobias Meggendorfer. Conditional value-at-risk for reachability and mean payoff in Markov decision processes. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 609–618. ACM, 2018.
  27. [27]Shigeo Kusuoka. On law invariant coherent risk measures. In Advances in Mathematical Economics, pages 83–95. Springer, Tokyo, Japan, 2001.
  28. [28]Durgam Latha, Dion Reji, S. Akshay, Dørde Žikelić, and Shankaranarayanan Krishna. Solving robust POMDPs with ω-regular objectives via partially observable stochastic games. arXiv preprint arXiv:2608.24986, 2026.arxiv.org/abs/2608.24986
  29. [29]Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic planning and related stochastic optimization problems. Artificial Intelligence, 147(1–2):5–34, 2003.DOI
  30. [30]Shie Mannor and John N. Tsitsiklis. Algorithmic aspects of mean–variance optimization in Markov decision processes. European Journal of Operational Research, 231(3):645–653, 2013.DOI
  31. [31]Tobias Meggendorfer. Risk-aware stochastic shortest path. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9858–9867, 2022.arxiv.org/abs/2203.01640
  32. [32]Tobias Meggendorfer, Maximilian Weininger, and Patrick Wienhöft. Solving robust markov decision processes: Generic, reliable, efficient. In Thirty-Ninth AAAI Conference on Artificial Intelligence, Thirty-Seventh Conference on Innovative Applications of Artificial Intelligence, Fifteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2025, Philadelphia, PA, USA, February 25 - March 4, 2025, pages 26631–26641, 2025. URL https://doi.org/10.1609/aaai.v39i25.34865.
  33. [33]Hideaki Nakao, Ruiwei Jiang, and Siqian Shen. Distributionally robust partially observable markov decision process with moment-based ambiguity. SIAM J. Optim., 31(1):461–488, 2021. URL https://doi.org/10.1137/19M1268410.
  34. [34]Arnab Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780–798, 2005.DOI
  35. [35]Arnab Nilim and Laurent El Ghaoui. Robustness in markov decision problems with uncertain transition matrices. In Advances in Neural Information Processing Systems 16 [Neural Information Processing Systems, NIPS 2003, December 8-13, 2003, Vancouver and Whistler, British Columbia, Canada], pages 839–846, 2003. URL https://proceedings.neurips.cc/paper/2003/hash/300891a62162b960cf02ce3827bb363c–Abstract.html.
  36. [36]Takayuki Osogami. Robustness and risk-sensitivity in markov decision processes. Advances in neural information processing systems, 25, 2012.
  37. [37]Takayuki Osogami. Robust partially observable markov decision process. In International Conference on Machine Learning, pages 106–115. PMLR, 2015.
  38. [38]Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of Markov decision processes. Mathematics of Operations Research, 12(3):441–450, 1987.DOI
  39. [39]Jakob Piribauer and Christel Baier. On Skolem-hardness and saturation points in Markov decision processes. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, pages 138:1–138:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.arxiv.org/abs/2004.11441
  40. [40]Jakob Piribauer, Ocan Sankur, and Christel Baier. The variance-penalized stochastic shortest path problem. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP), volume 229 of LIPIcs, pages 129:1–129:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.arxiv.org/abs/2204.12280
  41. [41]Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
  42. [42]R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2:21–42, 2000.DOI
  43. [43]Andrzej Ruszczyński. Risk-averse dynamic programming for Markov decision processes. Mathematical Programming, 125(2):235–261, 2010.DOI
  44. [44]Lloyd S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39 (10):1095–1100, 1953.
  45. [45]Matthew J. Sobel. The variance of discounted Markov decision processes. Journal of Applied Probability, 19(4):794–802, 1982.
  46. [46]Marnix Suilen, Nils Jansen, Murat Cubuktepe, and Ufuk Topcu. Robust policy synthesis for uncertain pomdps via convex optimization. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 4113–4120, 2020. URL https://doi.org/10.24963/ijcai.2020/569.
  47. [47]Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approximation. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, pages 181–189, 2014. URL http://proceedings.mlr.press/v32/tamar14.html.
  48. [48]Alfred Tarski. A decision method for elementary algebra and geometry. In Quantifier elimination and cylindrical algebraic decomposition, pages 24–84. Springer, 1998.
  49. [49]Ambuj Tewari and Peter L. Bartlett. Bounded parameter markov decision processes with average reward criterion. In Learning Theory, 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA, June 13-15, 2007, Proceedings, pages 263–277, 2007. URL https://doi.org/10.1007/978-3-540-72927-3_20.
  50. [50]Yue Wang, Alvaro Velasquez, George K. Atia, Ashley Prater-Bennette, and Shaofeng Zou. Robust average-reward markov decision processes. In Thirty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 15215–15223, 2023. URL https://doi.org/10.1609/aaai.v37i12.26775.
  51. [51]Wolfram Wiesemann, Daniel Kuhn, and Berc Rustem. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153–183, 2013.

Paper details

vlnc:W_fgqj8dmc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents