betaFeedback

WorksMathematics

Robust Markov Decision Processes: An Introduction Using Convex Optimization and Game Theory

Abstract

The goal of these notes is to provide a unified and rigorous introduction to robust sequential decision-making. We offer a self-contained introduction to the main results in the field. After a concise introduction to MDPs we introduce robust MDPs with general uncertainty sets, before focusing on rectangular models of uncertainty. We make a significant effort to show connections between robust MDPs and several other popular models for sequential decision-making: MDPs with uncertain rewards, Multi-Objective MDPs and Pareto optimality, MDPs with time-varying uncertain parameters, non-rectangular robust MDPs, stochastic games, distributionally robust MDPs, and risk-averse MDPs. Having all these results in one place, within a single unifying formalism, will hopefully be useful for researchers who want to start working on this topic. The exposition combines operator and fixed point approaches, convex optimization (more specifically, duality in saddle-point problems), and game-theoretic arguments. The latter identifies robust MDPs with a certain type of two-player game; this helps build useful intuition, especially when constructing counterexamples.

Introduction to Markov Decision Processes

Model, assumptions, and objective

Markov decision processes (MDPs) are used to model sequential decision-making problems. An MDP M\mathcal{M} is a tuple M=(S,A,r,P,p0)\mathcal{M} = (\mathcal{S}, \mathcal{A}, r, P, p_0) where:

  • S\mathcal{S} and A\mathcal{A} are the finite sets of states and actions,

  • r∈RS×A×Sr \in\mathbb{R}^{\mathcal{S} \times\mathcal{A} \times\mathcal{S}} models the instantaneous rewards attached to each (s,a,s′)(s, a, s') with (s,a)∈S×A(s, a) \in\mathcal{S} \times\mathcal{A} the current state-action pair and s′s' the next state,

  • P∈Δ(S)S×AP \in\Delta(\mathcal{S})^{\mathcal{S} \times\mathcal{A}}, where P(s,a,s′)P(s, a, s') models the transition probabilities toward the next state s′s' given a current state-action pair (s,a)(s, a),

  • p0∈Δ(S)p_0 \in\Delta(\mathcal{S}) is the initial distribution over the set of states: p0(s)p_0(s) is the probability that we start in state s∈Ss \in\mathcal{S}.

Recall that the simplex Δ(E)\Delta(\mathcal{E}) over a finite set E\mathcal{E} is the set of all probability distributions over E\mathcal{E} and can be identified with {x∈RE∣∑e∈Ex(e)=1,x(e)≥0, ∀e∈E}\{x \in\mathbb{R}^{\mathcal{E}} \mid\sum_{e \in\mathcal{E}} x(e) = 1, x(e) \ge0, \ \forall e \in\mathcal{E}\}. We usually represent the dynamics as in Figure 1.1. It is worth emphasizing the assumptions listed above:

Figure 1.1. Dynamics for Markov decision processes. The next state is sampled with the probability distribution P(s,a)∈Δ(S)P(s,a) \in\Delta(\mathcal{S}). We choose action aa in state ss to balance the instantaneous reward r(s,a,s′)r(s,a,s') and the likelihood of obtaining good rewards in the future (from the next state s′s').

  1. In these notes we focus on finite sets of states and actions, and discrete time periods. Already in this setting many interesting phenomena occur. We will later need compact action sets (see § 3.2).

  1. The dynamics is assumed to be Markovian, in that a current state-action pair (st,at)(s_t,a_t) at period tt completely suffices to specify the distribution of the next state st+1s_{t+1} as a random variable with values in S\mathcal{S}.

  1. For now, we assume that the same set of actions is available at each state. This is without loss of generality, and we do so to lighten notation for now, but we will need MDPs with state-dependent action sets when we study robust MDPs in § 3.2.

We will tend to emphasize the role of the transition probabilities since this will play a key role for robust MDPs.

Policies. We now explain how we make decisions in an MDP. A policy π\pi should choose an action at each period t∈Nt \in\mathbb{N}, based on all the information observed so far. At period t∈Nt \in\mathbb{N}, we can observe ht=(s0,a0,s1,a1,…,st−1,at−1,st)∈(S×A)t×Sh_t=(s_0,a_0,s_1,a_1,\ldots,s_{t-1},a_{t-1},s_t) \in(\mathcal{S} \times\mathcal{A})^t \times\mathcal{S}, i.e., we can observe the sequence of all states visited and actions chosen, we know the current state, and we need to decide what action to pick next. Thus in all generality a policy is a map from the set of all finite histories H=⋃t∈N(S×A)t×S\mathcal{H}=\bigcup_{t\in\mathbb{N}}(\mathcal{S} \times\mathcal{A})^t \times\mathcal{S} to the simplex Δ(A)\Delta(\mathcal{A}) over the action set A\mathcal{A}.

We use the following notation for the sets of policies of interest:

  • ΠH\Pi_{\mathrm{H}} is the set of all policies, possibly history-dependent: ΠH={π:H→Δ(A)}\Pi_{\mathrm{H}}=\{\pi:\mathcal{H}\to\Delta(\mathcal{A})\}.

  • ΠM\Pi_{\mathrm{M}} is the set of Markovian policies, i.e., policies where the action chosen at period tt may only depend on the current state st∈Ss_t \in\mathcal{S} and period tt, but not on the state-action pairs (s0,a0,…,st−1,at−1)(s_0,a_0,\ldots,s_{t-1},a_{t-1}) from the past.

  • ΠS\Pi_{\mathrm{S}} is the set of stationary policies, i.e., policies where the action chosen at period tt may only depend on the current state st∈Ss_t \in\mathcal{S}.

  • ΠSD\Pi_{\mathrm{SD}} is the set of stationary deterministic policies, i.e., policies where the action chosen at period tt may only depend on the current state st∈Ss_t \in\mathcal{S} and the same action is always chosen at a given state.

Of course we have ΠSD⊂ΠS⊂ΠM⊂ΠH\Pi_{\mathrm{SD}} \subset\Pi_{\mathrm{S}} \subset\Pi_{\mathrm{M}} \subset\Pi_{\mathrm{H}}. Note that we can naturally identify the set ΠM\Pi_{\mathrm{M}} of Markovian policies with Δ(A)S×N\Delta(\mathcal{A})^{\mathcal{S}\times\mathbb{N}}, i.e., with maps returning a randomized action in Δ(A)\Delta(\mathcal{A}) for each pair (s,t)(s,t) of state-period in S×N\mathcal{S} \times\mathbb{N}. We can identify the set ΠS\Pi_{\mathrm{S}} of stationary policies with the compact set Δ(A)S\Delta(\mathcal{A})^{\mathcal{S}} (returning a randomized action for each state) and the set ΠSD\Pi_{\mathrm{SD}} of stationary deterministic policies with the finite set AS\mathcal{A}^{\mathcal{S}}.

Note that history-dependent policies require (in the worst case) keeping track of everything that happened in the past and may be difficult to store and deploy. Similarly, randomized stationary policies mean that every time we visit the same state ss, we need to sample from π(s)∈Δ(A)\pi(s) \in\Delta(\mathcal{A}). This may be difficult to explain in some applications (e.g., in a healthcare application where the set of states is the set of health conditions for our patients and the set of actions is the set of feasible treatments), and in fact, randomization means delegating part of the decision to a generator of random numbers, which again may be problematic (how do you explain this to practitioners?). For all purposes, the set of stationary deterministic policies is the simplest, and its policies are the easiest to implement.

Example 1.1. Consider the MDP instance from Figure 1.2. The set of states is S={s0,G,B}\mathcal{S} = \{s_0, G, B\} and there are two actions: A={a1,a2}\mathcal{A} = \{a_1, a_2\}. The rewards are 00 starting from s0s_0 or BB, and the reward from GG is always 11. The transition probabilities are parametrized by some p∈[0,1]p \in[0, 1]. Note that the only difference between a1a_1 and a2a_2 lies in the transitions out of s0s_0. For instance, if p=0p = 0, choosing action a1a_1 in s0s_0 leads to BB deterministically and choosing a2a_2 in s0s_0 leads to GG deterministically. If p=1p = 1 it is the reverse. The transition probabilities are given by P(s0,a1)=(0,p,1−p)P(s_0, a_1) = (0, p, 1 - p), P(s0,a2)=(0,1−p,p)P(s_0, a_2) = (0, 1 - p, p), P(G,a1)=P(G,a2)=P(B,a1)=P(B,a2)=(1,0,0)P(G, a_1) = P(G, a_2) = P(B, a_1) = P(B, a_2) = (1, 0, 0). The “good” state GG yields a reward of 11, while the “bad” state yields a reward of 00. Obviously we want to pick our actions so that we pass through state GG more often than state BB.

Transitions and rewards for actions a1 and a2

Figure 1.2. MDP instance for Example 1.1. The transition probabilities and rewards are indicated beside each arc.

Example 1.2. Consider the MDP instance from Figure 1.3, where there are five states {s0,s1,s2,s3,s4}\{s_0, s_1, s_2, s_3, s_4\} and two actions a1a_1 and a2a_2. The transition probabilities are parametrized by p,p′∈[0,1]p, p' \in[0, 1]. Absorbing states are represented with squares. The rewards are only obtained in the absorbing states s2,s3,s4s_2, s_3, s_4. Actions a1a_1 and a2a_2 swap the probabilities towards the next states from s0s_0 and s1s_1.

Transitions and rewards for actions $a_1$ and $a_2$

Figure 1.3. MDP instance for Example 1.2. The transition probabilities and rewards are indicated beside each arc.

Remark 1.1 (Finite-horizon models). An additional property of Example 1.2 (compared to Example 1.1) is that this MDP instance is absorbed after at most two periods. Hence, it actually represents a sequential decision problem with a finite horizon. There are two main models for finite-horizon problems:

Model (A): we assume that we visit independent copies of the state set at each period (so that each state is visited only once), or

Model (B): we assume that we can visit the same states multiple times. Both models are equivalent, but stationary policies in case (A) correspond to Markovian policies in case (B). In these notes we’ll focus on infinite-horizon models, and our results apply to finite-horizon models with model (A) (up to renormalizing the rewards at each state with the appropriate power of the discount factor).

References

  1. [1]Marianne Akian and Stéphane Gaubert. Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial. arXiv preprint arXiv:1310.4953, 2013.arxiv.org/abs/1310.4953
  2. [2]Yonatan Ashlag, Uri Koren, Mirco Mutti, Esther Derman, Pierre-Luc Bacon, and Shie Mannor. State entropy regularization for robust reinforcement learning. Advances in Neural Information Processing Systems, 38:21018–21046, 2025.arxiv.org/abs/2506.07085
  3. [3]Vivek S Borkar, Vladimir Ejov, and Jerzy A Filar. On the Hamiltonicity gap and doubly stochastic matrices. Random Structures & Algorithms, 34(4):502–519, 2009.DOI
  4. [4]Richard Ernest Bellman. Dynamic Programming. Princeton University Press, Princeton, N.J., 1957.
  5. [5]Axel Benyamine, Julien Grand-Clément, Marek Petrik, Michael I. Jordan, and Alain Oliviero Durmus. Dynamic programming for epistemic uncertainty in Markov decision processes. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pages 7541–7578. PMLR, 2026.arxiv.org/abs/2602.03381
  6. [6]Axel Benyamine, Julien Grand-Clément, Marek Petrik, Michael I. Jordan, and Alain Oliviero Durmus. On the existence of uniformly optimal policies for MDPs under epistemic uncertainty. In Advances in Neural Information Processing Systems, 2026.
  7. [7]Bahram Behzadian, Marek Petrik, and Chin Pang Ho. Fast algorithms for L∞-constrained s-rectangular robust MDPs. Advances in Neural Information Processing Systems, 34:25982–25992, 2021.
  8. [8]Peter Buchholz and Dimitri Scheftelöwitsch. Computation of weighted sums of rewards for concurrent MDPs. Mathematical Methods of Operations Research, 89(1):1–42, 2019.DOI
  9. [9]Peter Buchholz and Dimitri Scheftelöwitsch. Concurrent MDPs with finite Markovian policies. In International Conference on Measurement, Modelling and Evaluation of Computing Systems, pages 37–53. Springer, 2020.DOI
  10. [10]Stephen Boyd and Lieven Vandenberghe. Convex optimization, volume 1. Cambridge university press, Cambridge, 2004.
  11. [11]Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Extended formulations in combinatorial optimization. 4OR, 8(1):1–48, 2010.
  12. [12]Michael G Crandall and Luc Tartar. Some relations between nonexpansive and order preserving mappings. Proceedings of the American Mathematical Society, 78(3):385–390, 1980.DOI
  13. [13]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
  14. [14]F d’Epenoux. Sur un problème de production et de stockage dans l’aléatoire. Revue Française de Recherche Opérationnelle, 14(3-16):4, 1960.
  15. [15]Guy De Ghellinck. Les problèmes de décisions séquentielles. Cahiers du Centre d’Etudes de Recherche Opérationnelle, 2(2):161–179, 1960.
  16. [16]Florent Delgrange, Joost-Pieter Katoen, Tim Quatmann, and Mickael Randour. Simple strategies in multi-objective MDPs. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 346–364. Springer, 2020.
  17. [17]Esther Derman, Daniel J Mankowitz, Timothy A Mann, and Shie Mannor. Soft-robust actor-critic policy-gradient. In Uncertainty in Artificial Intelligence (UAI), 2018.arxiv.org/abs/1803.04848
  18. [18]Eugene A Feinberg and Adam Shwartz. Constrained Markov decision models with weighted discounted rewards. Mathematics of Operations Research, 20(2):302–320, 1995.DOI
  19. [19]Eugene A Feinberg and Adam Shwartz. Handbook of Markov decision processes: methods and applications, volume 40. Springer Science & Business Media, 2012.
  20. [20]Hans Föllmer and Alexander Schied. Stochastic Finance: An Introduction in Discrete Time. Walter de Gruyter, 4th edition, 2016.
  21. [21]Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
  22. [22]Joel Goh, Mohsen Bayati, Stefanos A Zenios, Sundeep Singh, and David Moore. Data uncertainty in Markov chains: Application to cost-effectiveness analyses of medical innovations. Operations Research, 66(3):697–715, 2018.DOI
  23. [23]Julien Grand-Clément and Marek Petrik. On the convex formulations of robust Markov decision processes. Mathematics of Operations Research, 50(3):1681–1706, 2025.
  24. [24]Julien Grand-Clément, Marek Petrik, and Nicolas Vieille. Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality. Operations Research, 74(4):2088–2112, 2026.
  25. [25]Julien Grand-Clément, Nian Si, and Shengbo Wang. Dynamic programming-compatible uncertainty sets in robust Markov decision processes. Mathematics of Operations Research, 2026.
  26. [27]Vineet Goyal and Julien Grand-Clément. Robust Markov decision processes: Beyond rectangularity. Mathematics of Operations Research, 48(1):203–226, 2023.DOI
  27. [28]Robert Givan, Sonia Leach, and Thomas Dean. Bounded parameter Markov decision processes. In European Conference on Planning, pages 234–246. Springer, 1997.
  28. [29]Ernst Moritz Hahn, Vahid Hashemi, Holger Hermanns, Morteza Lahijanian, and Andrea Turrini. Multi-objective robust strategy synthesis for interval Markov decision processes. In International Conference on Quantitative Evaluation of Systems, pages 207–223. Springer, 2017.
  29. [30]Alan J Hoffman and Richard M Karp. On nonterminating stochastic games. Management Science, 12(5):359–370, 1966.DOI
  30. [31]Onésimo Hernández-Lerma and Rosario Romera. The scalarization approach to multiobjective Markov control problems: Why does it work? Applied Mathematics and Optimization, 50(3):279–293, 2004.
  31. [32]Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM (JACM), 60(1):1–16, 2013.arxiv.org/abs/1008.0530
  32. [33]Ronald A Howard. Dynamic programming and Markov processes. 1960.
  33. [34]Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for L1-robust Markov decision processes. The Journal of Machine Learning Research, 22(1):12612–12657, 2021.arxiv.org/abs/2006.09484
  34. [35]Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Robust phi-divergence MDPs. Advances in Neural Information Processing Systems, 35:32680–32693, 2022.arxiv.org/abs/2205.14202
  35. [36]G. Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257–280, 2005.DOI
  36. [37]Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51):1563–1600, 2010.
  37. [38]Lodewijk Kallenberg. Markov decision processes. Lecture Notes, University of Leiden, 2011.
  38. [39]Toshinori Kitamura, Arnob Ghosh, Alex Ayoub, Thang D Chu, and Csaba Szepesvári. Revisiting subgradient dominance in robust MDPs: Counterexamples, hardness, and sufficient conditions. Advances in Neural Information Processing Systems, 2026.arxiv.org/abs/2604.21177
  39. [40]Michael Kupper and Walter Schachermayer. Representation results for law invariant time consistent functions. Mathematics and Financial Economics, 2(3):189–210, 2009.DOI
  40. [41]Harold W Kuhn. Extensive games and the problem of information. Contributions to the Theory of Games, 2(28):193–216, 1953.
  41. [42]Joon Kwon. An introduction to reinforcement learning. https://joon-kwon.github.io/rl-ups/reinforcement-learning-lecture-notes.pdf, 2026.
  42. [43]Elita A Lobo, Mohammad Ghavamzadeh, and Marek Petrik. Soft-robust algorithms for batch reinforcement learning. arXiv preprint arXiv:2011.14495, 2020.arxiv.org/abs/2011.14495
  43. [44]Haoye Lu, Daniel Herman, and Yaoliang Yu. Multi-objective reinforcement learning: Convexity, stationarity and Pareto optimality. In The Eleventh International Conference on Learning Representations, 2023.
  44. [45]Yan Li. Computational hardness of static distributionally robust Markov decision processes. Operations Research Letters, (67:107465), 2026.arxiv.org/abs/2511.02224
  45. [46]Michael L Littman. Memoryless policies: Theoretical limitations and practical results. In From Animals to Animats 3: Proceedings of the third international conference on simulation of adaptive behavior, volume 3, pages 238–245. MIT Press Cambridge, MA, USA, 1994.DOI
  46. [47]Rida Laraki and Sylvain Sorin. Advances in zero-sum dynamic games. In Handbook of game theory with economic applications, volume 4, pages 27–93. Elsevier, 2015.DOI
  47. [48]Yan Li and Alexander Shapiro. Rectangularity and duality of distributionally robust Markov decision processes. Mathematical Programming, pages 1–42, 2025.arxiv.org/abs/2308.11139
  48. [49]Yann Le Tallec. Robust, risk-sensitive, and data-driven control of Markov decision processes. PhD thesis, Massachusetts Institute of Technology, 2007.
  49. [50]Alan S Manne. Linear programming and sequential decisions. Management Science, 6(3):259–267, 1960.DOI
  50. [51]H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th international conference on machine learning (ICML-03), pages 536–543, 2003.
  51. [52]Alexandre Marthe, Aurélien Garivier, and Claire Vernade. Beyond average return in Markov decision processes. Advances in Neural Information Processing Systems, 36:56488–56507, 2023.DOI
  52. [53]Shie Mannor, Ofir Mebel, and Huan Xu. Lightning does not strike twice: Robust MDPs with coupled uncertainty. ICML, 2012.arxiv.org/abs/1206.4643
  53. [54]S. Mannor, O. Mebel, and H. Xu. Robust MDPs with k-rectangular uncertainty. Mathematics of Operations Research, 41(4):1484–1509, 2016.DOI
  54. [55]J F Mertens and Abraham Neyman. Stochastic games. International Journal of Game Theory, 10:53–66, 1981.
  55. [56]Jean-François Mertens, Sylvain Sorin, and Shmuel Zamir. Repeated games. Cambridge University Press, 2015.
  56. [57]John F Nash. Non-cooperative games. volume 54, pages 286–295. 1951.
  57. [58]A. Nilim and L. El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780–798, 2005.DOI
  58. [59]Abraham Neyman and Sylvain Sorin. Stochastic games and applications, volume 570. Springer Science & Business Media, 2003.DOI
  59. [60]Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
  60. [61]S. S. Rao, R. Chandrasekaran, and K.P.K. Nair. Algorithms for discounted stochastic games. Journal of Optimization Theory and Applications, 11(6):627–637, 1973.DOI
  61. [62]Jérôme Renault. A tutorial on zero-sum stochastic games. arXiv preprint arXiv:1905.06577, 2019.arxiv.org/abs/1905.06577
  62. [63]Ralph Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1970.
  63. [64]Willem Röpke, Mathieu Reymond, Patrick Mannion, Diederik M Roijers, Ann Nowé, and Roxana Rădulescu. Divide and conquer: Provably unveiling the Pareto front with multi-objective reinforcement learning. AAMAS 2025.arxiv.org/abs/2402.07182
  64. [66][RS06] Andrzej Ruszczyński and Alexander Shapiro. Conditional risk mappings. Mathematics of Operations Research, 31(3):544–561, 2006.
  65. [67][RS14] Jean-François Raskin and Ocan Sankur. Multiple-environment Markov decision processes. In International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014.arxiv.org/abs/1405.4733
  66. [68][Rus10] Andrzej Ruszczyński. Risk-averse dynamic programming for Markov decision processes. Mathematical Programming, 125(2):235–261, 2010.DOI
  67. [69][RVWD13] Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of multi-objective sequential decision-making. Journal of Artificial Intelligence Research, 48:67–113, 2013.
  68. [70][SBB+24] Marnix Suilen, Thom Badings, Eline M Bovy, David Parker, and Nils Jansen. Robust Markov decision processes: A place where AI and formal methods meet. In Principles of Verification: Cycling the Probabilistic Landscape: Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday, Part III, pages 126–154. Springer, 2024.
  69. [71][SBHH17] Dimitri Scheftelowitsch, Peter Buchholz, Vahid Hashemi, and Holger Hermanns. Multi-objective approaches to Markov decision processes with uncertain transition parameters. In Proceedings of the 11th EAI International Conference on Performance Evaluation Methodologies and Tools, pages 44–51, 2017.
  70. [72][Sch13] Bruno Scherrer. Improved and generalized upper bounds on the complexity of policy iteration. Advances in Neural Information Processing Systems, 26:386–394, 2013.arxiv.org/abs/1306.0386
  71. [73][Sha53] Lloyd S Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10):1095–1100, 1953.
  72. [74][Sha12] Alexander Shapiro. Time consistency of dynamic risk measures. Operations Research Letters, 40(6):436–439, November 2012.DOI
  73. [75][SL73] J.K. Satia and R.E. Lave. Markovian decision processes with uncertain transition probabilities. Operations Research, 21(3):728–740, 1973.DOI
  74. [76][SL25a] Alexander Shapiro and Yan Li. Distributionally robust stochastic optimal control. Operations Research Letters, 60:107234, 2025.arxiv.org/abs/2406.05648
  75. [77][SL25b] Alexander Shapiro and Yan Li. Risk-averse formulations of stochastic optimal control and Markov decision processes. arXiv preprint arXiv:2505.16651, 2025.arxiv.org/abs/2505.16651
  76. [78]Ambuj Tewari and Peter L Bartlett. Bounded parameter Markov decision processes with average reward criterion. In International Conference on Computational Learning Theory, pages 263–277. Springer, 2007.DOI
  77. [79]Nikos Vlassis, Michael L Littman, and David Barber. On the computational complexity of stochastic controller optimization in POMDPs. ACM Transactions on Computation Theory (TOCT), 4(4):1–8, 2012.arxiv.org/abs/1107.3090
  78. [80]Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153–183, 2013.DOI
  79. [81]Shengbo Wang, Nian Si, Jose Blanchet, and Zhengyuan Zhou. On the foundation of distributionally robust reinforcement learning. arXiv preprint arXiv:2311.09018, 2023.arxiv.org/abs/2311.09018
  80. [82]Huan Xu and Shie Mannor. Distributionally robust Markov decision processes. Advances in Neural Information Processing Systems, 23:2505–2513, 2010.
  81. [83]Yinyu Ye. The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Mathematics of Operations Research, 36(4):593–603, 2011.

Paper details

vlnc:W_snqbxnkz
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.

  • Mathematics

OpenAI’s ChatGPT

View statement
Looking for related papers…
Contents