Robust Deterministic Policies for Markov Decision Processes under Budgeted Uncertainty

Erik Demeulemeester; Fei Wu; Jannik Matuschke

REVIEW 2 major objections 5 minor 17 references

Robust Deterministic Policies for Markov Decision Processes under Budgeted Uncertainty

T0 review · 2 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that finding an optimal deterministic policy in the LDST budgeted-uncertainty MDP model is computationally intractable, with NP-hardness already for two stages and a single deviating terminal reward, and…

desk verdict Hardness results are solid, but the approximation theorem has an unstated nonnegativity assumption that currently makes it false as written. read the letter →

arxiv 2412.12879 v1 pith:XQ3P4R2X submitted 2024-12-17 math.OC cs.DM

Fei Wu , Erik Demeulemeester , Jannik Matuschke This is my paper · ORCID

classification math.OCcs.DM MSC 90C4068Q1790C47

keywords robustMarkovdecisionprocessesdeterministicpoliciesbudgeteduncertaintyLDSTmodelNP-hardnessapproximationalgorithmsSigma-2hardnessmixedintegerprogramming

topics P versus NP

open problems P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how hard it is to choose a deterministic policy for a Markov decision process when the parameters (terminal rewards or transition probabilities) may deviate from their nominal values at a bounded number of states, the 'Lightning Does Not Strike Twice' (LDST) uncertainty model. It claims that this task is computationally hard in stark contrast to the randomized-policy case, which earlier work showed can be solved in polynomial time for reward uncertainty. Specifically, the paper establishes that already a two-stage MDP with a single deviating terminal reward is strongly NP-hard to optimize, and that the general reward-uncertainty version has no bounded approximation unless P equals NP. For transition uncertainty, the paper proves the problem is Sigma_2^p-hard, effectively excluding compact mixed-integer linear programming formulations. On the positive side, it gives a constant-factor approximation algorithm for the two-stage reward-uncertainty case.

What carries the argument

The argument for hardness is carried by reductions from classic problems: 3-Partition for the two-stage NP-hardness, Vertex-Disjoint Paths for the inapproximability of the general reward case, Max-Min Vertex Cover for the Sigma_2^p-hardness of transition uncertainty, and 3-SAT for the fixed-budget decision version. The positive algorithm is organized around the loss of a policy, $L(\pi) = R(\pi) - \hat{R}(\pi)$, the drop in expected reward under the worst-case deviation. It solves a Knapsack Cover relaxation (with an FPTAS) for instances where the optimal loss is large relative to the optimal worst-case reward, and a Generalized Assignment relaxation (with a standard rounding for assignment problems) for instances where the loss is small; the better of the two resulting policies is returned.

What would settle it

For a terminal state $t$ with nominal reward $r(t)=1$, deviating reward $r'(t)=-1$, and a policy reaching $t$ with probability 1, the paper's reduction yields $h=0$ and replaces $t$ by a state with nominal reward 2 and deviating reward 0, changing the worst-case value from $-1$ to $0$; any 2-Stage Reward-DLP instance containing such a negative deviation therefore tests whether Theorem 3's guarantee actually covers the paper's stated domain of arbitrary real rewards, and the described reduction shows it does not.

Watch

Extended reading notes

Core claim

The central discovery is a separation between randomized and deterministic policies in the LDST model. Whereas optimal randomized policies under reward uncertainty can be computed efficiently, the deterministic version is intractable: the two-stage reward case is strongly NP-hard (Theorem 1), the general reward case admits no constant-factor approximation unless P = NP (Theorem 2), and the version with uncertain transitions is Sigma_2^p-hard (Theorem 5), with a further NP-hardness result for deciding positive robust reward with budget k=2 (Theorem 4). The only general positive result is a 1/(5+epsilon)-approximation for the two-stage reward case (Theorem 3), obtained by running two complementary relaxations and taking the better policy.

Load-bearing premise

The paper's positive constant-factor approximation for two-stage reward uncertainty depends on an unstated assumption that every deviating reward is nonnegative and no larger than the nominal reward, since its reduction to zero deviations splits a terminal state into an integer number of copies using $h = \lceil r'(t)/(r(t)-r'(t)) \rceil$, a formula that is not value-preserving when $r'(t) < 0$.

Editorial extensions

If this is right

Even the simplest meaningful deviation—a single terminal reward changing in a two-stage MDP—makes the optimal deterministic policy impossible to compute in polynomial time unless P = NP.
For general reward uncertainty, no polynomial-time algorithm can guarantee any fixed fraction of the optimal worst-case reward, so approximation must be restricted to special structures.
For transition uncertainty, the Sigma_2^p-hardness implies that no compact mixed-integer programming formulation can capture the problem unless the polynomial hierarchy collapses.
The 1/(5+epsilon)-approximation for the two-stage reward case shows that this restricted problem is approximable despite being NP-hard, and the approximation factor is independent of the size of the MDP.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the unstated nonnegativity of deviating rewards is genuinely required, the positive approximation result is less general than the problem definition suggests; extending it to negative deviations would need a different rounding or a different relaxation.
The hardness contrast suggests that randomization in robust MDPs is not merely a modelling convenience but a source of tractability, which may matter for applications that require deterministic execution.
The two-relaxation idea—one for large-loss and one for small-loss regimes—could plausibly be adapted to other budgeted-robust optimization problems where a similar loss measure is available.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

One thing you should know: this is a real contribution, and the hardness results should hold up. The paper's main positive result, however, is currently only proved under an unstated nonnegativity assumption, and the proof as written collapses when alternative rewards are negative.

What is genuinely new: the contrast between polynomial-time randomized policies and NP-hard deterministic policies in the LDST model, even with two stages and a single deviating reward. The reductions are clean. The 3-Partition construction in Theorem 1 is straightforward and correct; the disjoint-paths reduction for Theorem 2 is a nice use of layered DAGs and the epsilon-weighting trick. Theorem 5's Sigma_2^p-hardness is intricate, and while the proof contains a misstated equation for epsilon, the chosen value does satisfy the inequalities, so that is a minor typo. The approximation algorithm combining a Knapsack Cover relaxation and a Generalized Assignment relaxation is clever, and the two-lemma structure is sound given its assumptions. No circularity: the paper relies on external FPTAS for Knapsack Cover and Shmoys-Tardos, and the hardness targets are established problems.

The soft spot is load-bearing. In Section 5.1, the paper claims WLOG that r'(t)=0 for every terminal state, but the transformation is only defined when r'(t)>0. The model in Section 2.3 allows r'(s) <= r(s) with no lower bound, so negative alternative rewards are permitted. The stress-test example is the right one: two terminals, both nominal reward 1, alternative rewards 0 and -1, one deviating state, equal probability on the two terminals. The true robust value is 0, L(pi)=1, and Lemma 10 fails because no UB1(L,t) with L=1 can have value at least 0 -- the largest single-terminal nominal reward is 1/2. The enumeration bounds in Theorems 7 and 8 also rely on rmin <= L(pi) <= rmax, which breaks with negative r'. So Theorem 3 as stated is false or at least unproven for the model actually defined. This is fixable by explicitly assuming r'(t) >= 0 (and r(t) > r'(t)) in the theorem, or by extending the transformation, but it changes the scope of the positive result.

Verdict: the hardness half is solid and worth publishing; the approximation half needs a revision. The paper deserves a serious referee. I would send it to review with a clear request to address the nonnegativity issue. For a reading group, it is a maybe -- the gap is a good discussion point, but the main results are narrow.

Referee Report

2 major / 5 minor

Summary. The paper studies the computational complexity of finding optimal deterministic policies in the Lightning Does Not Strike Twice (LDST) robust MDP model under budgeted uncertainty. It proves that 2-Stage Reward-DLP is strongly NP-hard (Theorem 1), that Reward-DLP has no polynomial-time constant-factor approximation unless P=NP (Theorem 2), that Transition-DLP is NP-hard even for budget k=2 (Theorem 4), and that Transition-DLP is Sigma_2^p-hard (Theorem 5). On the positive side, it gives a 1/(5+epsilon)-approximation algorithm for 2-Stage Reward-DLP (Theorem 3), based on a Knapsack Cover relaxation and a Generalized Assignment relaxation. The hardness reductions appear sound and are mostly clean; the main issue is that the positive result relies on an unstated nonnegativity assumption that is not part of the model as defined.

Significance. If the results stand, they are significant: they sharply separate deterministic from randomized policies in the LDST model, complementing Mannor et al.'s polynomial-time result for randomized policies. The Sigma_2^p-hardness of Transition-DLP is a strong statement about the impossibility of compact mixed-integer formulations. The approximation algorithm for the two-stage reward case is a useful positive counterpoint to the hardness results. The paper's reductions are from established hard problems and use external algorithms (FPTAS for Knapsack Cover and the Shmoys-Tardos algorithm for Generalized Assignment), which makes the proofs verifiable. However, the positive result currently depends on an assumption that is absent from the model definition, and one central reduction contains a misstated equation; these issues are fixable but require revision.

major comments (2)

[Section 5.1, Assumption 2; Theorems 3, 7, 8] The reduction to r'(t)=0 is not without loss of generality for the model defined in Sections 2.1-2.3. The model allows arbitrary real terminal rewards and only requires r'(s) <= r(s). The transformation in Section 5.1 is applied only for r'(t)>0; for r'(t)<0, the formula h = ceil(r'(t)/(r(t)-r'(t))) is non-positive or undefined, and the replacement states and probabilities are not well-defined. This is not a cosmetic gap: in the two-terminal instance with S1={s}, S2={t1,t2}, p(t1)=p(t2)=1/2, r(t1)=r(t2)=1, r'(t1)=0, r'(t2)=-1, and k=1, the true robust value is 0, L(pi)=1, but no policy can achieve nominal reward at least 1 on a single terminal, so Lemma 10 fails. The enumeration in Theorems 7 and 8 also assumes r_min>0 in the definition of L_i, which is not guaranteed by the model. Theorem 3 therefore needs an explicit assumption such as r'(t) >= 0 and r(t) > r'(t) (which implies nonnegative nominal rewards), or the transformation and guarantees must be extended to negative alternative rewards.
[Section 6, proof of Theorem 5] The sentence identifying the choice of epsilon is incorrect as written. The text states that epsilon is 'the unique solution to 1 - |I|*epsilon/|V| = epsilon/(2m)', but the value epsilon = 2m/(2m|I|+|V|) does not satisfy this equation in general; for example, with m=1, |I|=1, |V|=10, the left-hand side is approximately 0.983 while the right-hand side is approximately 0.083. The inequalities later needed (p_e > p_v for e in E_{t_pi} and p_e < p_v otherwise) do hold for the stated epsilon because p_v = 1/(2m|I|+|V|), p_e = 2epsilon/(3m) = 4/(3(2m|I|+|V|)) for e in E_{t_pi}, and p_e <= epsilon/(3m) = 2/(3(2m|I|+|V|)) otherwise. The proof is thus repairable, but the present derivation does not justify the claim and should be corrected.

minor comments (5)

[Section 4, proof of Theorem 1] In the definition of the state space, 'S3 := {tj}' should be 'S2 := {tj}', since the three stages are S0, S1, and S2.
[Section 5.3, definition of UB2] The artificial state t* is denoted with the same star symbol used in v_{st}^*, which makes the notation confusing in the definition of v_{st}^* and in Lemmas 12 and 13; please use distinct notation for the artificial state.
[Section 5.3, proof of Theorem 8] In the displayed inequality after invoking the Shmoys-Tardos algorithm, the right-hand side should be the objective value of the fractional solution, not the same expression with y' on both sides. Also, the enumeration in the proof of Theorem 8 loops over every t-hat in S2, but UB2(L) does not depend on t-hat; only the L_i values are needed.
[Section 6, proof of Theorem 4] In the definition of A', 'for some i in N' should be 'for some i in M' (the clauses), and the notation 'pi(sCi)' should be 'pi(s_{c_i})' for consistency.
[Throughout] There are several typographical slips: 'there a is a 1/(5+epsilon)-approximation' in Theorem 3, and the expression 'pv = 1 - epsilon|I| / |V|' in the proof of Theorem 5 should be parenthesized as '(1 - epsilon|I|)/|V|'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all hardness reductions and approximation guarantees rest on external problems and external algorithms.

full rationale

The paper's derivation chain is self-contained against external benchmarks rather than against its own inputs. Theorem 1 is proved by a direct reduction from 3-Partition, Theorem 2 from Vertex-Disjoint Paths, Theorem 4 from 3-SAT, and Theorem 5 from Max-Min Vertex Cover; each of these is an established NP-hard or Sigma_2^p-complete problem, and the reductions construct LDST instances whose robust-policy values correspond to the source instances' answers. The approximation result for 2-Stage Reward-DLP does not fit any parameter to the quantity it later calls a prediction. Theorems 7 and 8 derive worst-case guarantees from two relaxations, UB1 and UB2, and the algorithm combines them via Lemma 9; the relaxed subproblems are solved with the external FPTAS for Knapsack Cover and the external Shmoys-Tardos algorithm for Generalized Assignment, respectively. The bounds are proven directly: Lemma 10 shows UB1 gives an upper bound on the robust reward for suitable guessed loss values, Lemma 11 converts a UB1 solution back to a policy with guaranteed robust reward, Lemma 12 shows UB2 upper-bounds half the nominal reward, and Lemma 13 converts a UB2 solution to a policy losing at most the guessed loss. None of these steps equates the claimed result to a fitted or self-referential quantity by construction. The paper's use of Mannor et al. is contextual (defining LDST and contrasting the randomized-policy setting) and is not load-bearing for any new theorem. The reviewer-identified weakness concerning the unstated nonnegativity condition in the 'without loss of generality' reduction to r'(t)=0 is a genuine assumption gap and a potential correctness issue, but it is not circularity: the approximation proof would be invalid on a larger instance class, not circular because it assumes what it proves. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The paper is a pure theory paper. Its results rest on standard algorithmic and complexity-theoretic results (FPTAS, Shmoys-Tardos, known hardness). No fitted parameters or new physical entities are introduced. The main unstated assumption is the nonnegativity of rewards needed for the approximation algorithm.

assumptions (8)

standard math FPTAS for Knapsack Cover (Pruhs and Woeginger 2007)
Used in Theorem 7 to compute near-optimal solutions to the Knapsack Cover relaxation UB1(L, t). Cited in Section 5.2.
standard math Shmoys-Tardos approximation algorithm for Generalized Assignment Problem
Used in Theorem 8 to round fractional solutions of UB2(L) to integral solutions with doubled capacities while preserving the objective. Cited in Section 5.3.
standard math NP-hardness of 3-Partition, Vertex-Disjoint Paths, and 3-SAT, and Sigma_2^p-completeness of Max-Min Vertex Cover
Source problems for the reductions in Theorems 1, 2, 4, and 5. Cited in Sections 4 and 6.
standard math Woeginger's theorem: Sigma_2^p-hard optimization problems admit no compact MIP formulation unless the polynomial hierarchy collapses
Used to conclude from Theorem 5 that Transition-DLP has no compact mixed-integer programming formulation. Cited as [17] in Section 3.
domain assumption Nonnegativity of rewards (implicit)
The WLOG transformation to r'(t)=0 in Section 5.1 requires r'(t) >= 0 and r(t) > r'(t). The problem definition in Section 2.1 allows r(s) in R. This assumption is never stated.
domain assumption LDST budgeted uncertainty model
The uncertainty set is defined by at most k states deviating from nominal parameters. This is the framework inherited from Mannor et al., defined in Section 2.3.
domain assumption Finite-horizon, layered (acyclic) MDP structure
The state space is partitioned into stages S0,...,ST and transitions only go to the next stage, as defined in Section 2.1. Remark 6 argues extension to infinite horizon with absorbing states.
domain assumption Deterministic, history-independent policies as the policy class
The paper studies this class exclusively; the problem definitions and all results depend on it. Stated in Section 2.1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Robust Deterministic Policies for Markov Decision Processes under Budgeted Uncertainty." pith.science (2026). https://pith.science/paper/XQ3P4R2X

@misc{pith2026241212879,
  author       = {Pith},
  title        = {Pith review of: Robust Deterministic Policies for Markov Decision Processes under Budgeted Uncertainty},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XQ3P4R2X}},
  note         = {Machine review of arXiv:2412.12879}
}

abstract

This paper studies the computation of robust deterministic policies for Markov Decision Processes (MDPs) in the Lightning Does Not Strike Twice (LDST) model of Mannor, Mebel and Xu (ICML '12). In this model, designed to provide robustness in the face of uncertain input data while not being overly conservative, transition probabilities and rewards are uncertain and the uncertainty set is constrained by a budget that limits the number of states whose parameters can deviate from their nominal values. Mannor et al. (ICML '12) showed that optimal randomized policies for MDPs in the LDST regime can be efficiently computed when only the rewards are affected by uncertainty. In contrast to these findings, we observe that the computation of optimal deterministic policies is $N\!P$-hard even when only a single terminal reward may deviate from its nominal value and the MDP consists of $2$ time periods. For this hard special case, we then derive a constant-factor approximation algorithm by combining two relaxations based on the Knapsack Cover and Generalized Assignment problem, respectively. For the general problem with possibly a large number of deviations and a longer time horizon, we derive strong inapproximability results for computing robust deterministic policies as well as $\Sigma_2^p$-hardness, indicating that the general problem does not even admit a compact mixed integer programming formulation.

Figures

Figures reproduced from arXiv: 2412.12879 by the authors.

**Figure 2.1.** There, the optimal randomized policy takes action a and b, respectively, each with probability 1 2 , achieving an expected reward of 1 2 . However, the optimal value achievable by any deterministic policy is 0. s0 a b 1 t1 1/0 1 t2 1/0 [PITH_FULL_IMAGE:figures/full_fig_p005_2_1.png] view at source ↗

**Figure 4.1.** Construction of the reduction from 3-Partition to 2-Stage Reward-DLP. Proof. We prove the theorem by reduction from 3-Partition. Thus, we are given b1, . . . , b3n ∈ N and B ∈ N with Pn i=1 bi = nB, and our goal is to decide whether there is a partition U1, . . . , Un of U := {1, . . . , 3n} with P j∈Ui bj = B [PITH_FULL_IMAGE:figures/full_fig_p008_4_1.png] view at source ↗

**Figure 4.2.** The construction of the reduction from 3-Vertex-Disjoint Paths problem in D to Reward-DLP is shown in this figure, where the actions in each state correspond to the edges that leave from the respective node in D and δ = ε + ε 2 + ε 3 . Note that in the example, no pair of vertex-disjoint s1-t1- and s3-t3-paths exists in D and similarly, as any such paths would intersect at node v. Similarly, no policy can reach both… view at source ↗

Figures from the paper (2 more)

**Figure 6.1.** Figure 6.1: Construction of the Reduction from max-min VC to TransitionDLP. The solid gray arrows represent an nominal deterministic outcomes of a transition, with the dashed gray line representing the alternative transition outcomes from the uncertainty set. Proof. We prove th…

**Figure 6.2.** Figure 6.2: Construction for the reduction from 3-SAT to Transition-DLP. The solid gray arrows represent an nominal deterministic outcomes of a transition, with the dashed gray line representing the alternative transition outcomes from the uncertainty set. There are at most k = …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 16 canonical work pages

[1]

The price of robustness

Dimitris Bertsimas and Melvyn Sim. The price of robustness. Operations research, 52(1):35–53, 2004

work page 2004
[2]

On the complexity of timetable and mul- ticommodity ﬂow problems

S Even, A Itai, and A Shamir. On the complexity of timetable and mul- ticommodity ﬂow problems. SIAM Journal on Computing , 5(4):691–703, 1976

work page 1976
[3]

Bounded-parame ter markov decision processes

Robert Givan, Sonia Leach, and Thomas Dean. Bounded-parame ter markov decision processes. Artiﬁcial Intelligence , 122(1-2):71–109, 2000

work page 2000
[4]

Robust markov decision p rocesses: Beyond rectangularity

Vineet Goyal and Julien Grand-Clement. Robust markov decision p rocesses: Beyond rectangularity. Mathematics of Operations Research, 48(1):203–226, 2023

work page 2023
[5]

Robust dynamic programming

Garud N Iyengar. Robust dynamic programming. Mathematics of Opera- tions Research, 30(2):257–280, 2005

work page 2005
[6]

On the complexity of min-max optimizat ion problems and their approximation

Ker-I Ko and Chih-Long Lin. On the complexity of min-max optimizat ion problems and their approximation. In Minimax and Applications , pages 219–239. Springer, 1995

work page 1995
[7]

Bia s and variance approximation in value function estimates

Shie Mannor, Duncan Simester, Peng Sun, and John N Tsitsiklis. Bia s and variance approximation in value function estimates. Management Science , 53(2):308–322, 2007. Robust Deterministic Policies for MDPs under Budgeted Unce rtainty 25

work page 2007
[8]

Lightning does not strike tw ice: robust MDPs with coupled uncertainty

Shie Mannor, Oﬁr Mebel, and Huan Xu. Lightning does not strike tw ice: robust MDPs with coupled uncertainty. In Proceedings of the 29th Interna- tional Conference on Machine Learning , ICML’12, page 451–458, Madison, WI, USA, 2012. Omnipress

work page 2012

Show all 17 references

[9]

Robust MDPs with k-rectangular uncertainty

Shie Mannor, Oﬁr Mebel, and Huan Xu. Robust MDPs with k-rectangular uncertainty. Mathematics of Operations Research , 41(4):1484–1509, 2016

2016
[10]

Robust control of markov de cision processes with uncertain transition matrices

Arnab Nilim and Laurent El Ghaoui. Robust control of markov de cision processes with uncertain transition matrices. Operations Research, 53(5): 780–798, 2005

2005
[11]

Approximation schemes fo r a class of subset selection problems

Kirk Pruhs and Gerhard J Woeginger. Approximation schemes fo r a class of subset selection problems. Theoretical Computer Science , 382(2):151–156, 2007

2007
[12]

Markov decision processes: discrete stochastic dynamic programming

Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014

2014
[13]

Markovian decision processes with uncertain transition probabilities

Jay K Satia and Roy E Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, 21(3):728–740, 1973

1973
[14]

An approximation algorithm for the generalized assignment problem

David B Shmoys and ´Eva Tardos. An approximation algorithm for the generalized assignment problem. Mathematical programming, 62(1-3):461– 474, 1993

1993
[15]

Markov decision processes with im- precise transition probabilities

Chelsea C White III and Hany K Eldeib. Markov decision processes with im- precise transition probabilities. Operations Research, 42(4):739–749, 1994

1994
[16]

Robust ma rkov de- cision processes

Wolfram Wiesemann, Daniel Kuhn, and Ber¸ c Rustem. Robust ma rkov de- cision processes. Mathematics of Operations Research , 38(1):153–183, 2013

2013
[17]

The trouble with the second quantiﬁer

Gerhard J Woeginger. The trouble with the second quantiﬁer. 4OR, 19(2): 157–181, 2021

2021

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

The price of robustness

Dimitris Bertsimas and Melvyn Sim. The price of robustness. Operations research, 52(1):35–53, 2004

work page 2004

[2] [2]

On the complexity of timetable and mul- ticommodity ﬂow problems

S Even, A Itai, and A Shamir. On the complexity of timetable and mul- ticommodity ﬂow problems. SIAM Journal on Computing , 5(4):691–703, 1976

work page 1976

[3] [3]

Bounded-parame ter markov decision processes

Robert Givan, Sonia Leach, and Thomas Dean. Bounded-parame ter markov decision processes. Artiﬁcial Intelligence , 122(1-2):71–109, 2000

work page 2000

[4] [4]

Robust markov decision p rocesses: Beyond rectangularity

Vineet Goyal and Julien Grand-Clement. Robust markov decision p rocesses: Beyond rectangularity. Mathematics of Operations Research, 48(1):203–226, 2023

work page 2023

[5] [5]

Robust dynamic programming

Garud N Iyengar. Robust dynamic programming. Mathematics of Opera- tions Research, 30(2):257–280, 2005

work page 2005

[6] [6]

On the complexity of min-max optimizat ion problems and their approximation

Ker-I Ko and Chih-Long Lin. On the complexity of min-max optimizat ion problems and their approximation. In Minimax and Applications , pages 219–239. Springer, 1995

work page 1995

[7] [7]

Bia s and variance approximation in value function estimates

Shie Mannor, Duncan Simester, Peng Sun, and John N Tsitsiklis. Bia s and variance approximation in value function estimates. Management Science , 53(2):308–322, 2007. Robust Deterministic Policies for MDPs under Budgeted Unce rtainty 25

work page 2007

[8] [8]

Lightning does not strike tw ice: robust MDPs with coupled uncertainty

Shie Mannor, Oﬁr Mebel, and Huan Xu. Lightning does not strike tw ice: robust MDPs with coupled uncertainty. In Proceedings of the 29th Interna- tional Conference on Machine Learning , ICML’12, page 451–458, Madison, WI, USA, 2012. Omnipress

work page 2012