Pith. sign in

REVIEW 5 major objections 5 minor 57 references

Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes

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

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

Pith's one-line read Robust policy evaluation for non-rectangular Lp-bounded transition uncertainty reduces to a fixed-point binary search, with the worst-case kernel being a rank-one perturbation of the nominal kernel.

desk verdict The union decomposition and dual expression are genuinely new, but the paper's signature algorithm loses its guarantee once you look at what actually computes F(λ). read the letter →

arxiv 2502.09432 v1 pith:3VCPNPRK submitted 2025-02-13 cs.AI cs.LG

Navdeep Kumar , Adarsh Gupta , Maxence Mohamed Elfatihi , Giorgia Ramponi , Kfir Yehuda Levy , Shie Mannor This is my paper · ORCID
classification cs.AIcs.LG MSC 90C4090C47
keywords robustMarkovdecisionprocessesnon-rectangularuncertaintyLpnormpolicyevaluationdualformulationrank-oneadversaryfixed-pointbinarysearchgradient
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 tries to establish that robust policy evaluation—finding the worst-case return of a fixed policy—is not inherently intractable for non-rectangular Markov decision processes when the transition uncertainty is bounded by an Lp ball around a nominal kernel. For this class, the worst-case kernel is a rank-one perturbation of the nominal kernel, and the robust return splits into the nominal return minus a penalty term that is a fixed point of a scalar function. That fixed point can be found by binary search with linear convergence, which the paper presents as the first efficient robust policy evaluation algorithm for non-rectangular kernel uncertainty. The paper also characterizes the adversary in closed form and derives a robust policy gradient method. If correct, this makes a class of coupled, less conservative uncertainty models computationally usable rather than merely expressive.

What carries the argument

The load-bearing machinery is the decomposition $U_p = \bigcup_{b\in B} U^{sa}_p(b)$, which rewrites one coupled Lp ball as an infinite union of state-action-rectangular Lp balls sharing the nominal kernel. This makes the known rank-one form of the sa-rectangular adversary available piecewise, and the Sherman-Morrison formula turns the induced return into a bilinear fractional function of nominal occupancy and value terms. The binary search hinges on the scalar function $F(\lambda) = \max_{b\in B} \|E^\pi_\lambda b\|_q$, whose crossing of the diagonal locates the robust penalty. The outer bisection is exact when $F$ is evaluated exactly, while the p=2 inner norm maximization is handled by the spectral Algorithm 2.

What would settle it

Take a small random MDP, compute $F(\lambda)$ exactly by global optimization at the bisection points, and compare it with Algorithm 2's value; if there is any $\lambda$ where Algorithm 2 returns a value on the wrong side of the diagonal, such as $F_{\text{approx}}(\lambda) > \lambda$ while $F_{\text{exact}}(\lambda) < \lambda$, then Algorithm 1 selects the wrong half of the interval and the reported robust return differs from $J^\pi - \lambda^*$, falsifying the practical claim of linear-convergence evaluation for p=2.

Watch

Extended reading notes

Core claim

The central claim is that for the non-rectangular Lp-bounded uncertainty set $U_p = \{P : \|P - \hat{P}\|_p \le \beta,\ \sum_{s'} P(s'|s,a) = 1\}$, robust policy evaluation is tractable because $U_p$ decomposes into a continuum of sa-rectangular Lp sets sharing the same nominal kernel. On each such set the adversary's worst kernel has the form $P = \hat{P} - b k^\top$; applying the Sherman-Morrison formula gives $J^\pi_{U_p} = J^\pi - \gamma \max_{b,k} [\langle k, v^\pi_R\rangle \langle d^\pi, b^\pi\rangle / (1 + \gamma \langle k, v^\pi_b\rangle)]$, all in nominal terms. Defining $F(\lambda) = \max_{b\in B} \|E^\pi_\lambda b\|_q$, the penalty is the unique fixed point $\lambda^*$ of $F$, with $F(\lambda) > \lambda$ iff $\lambda > \lambda^*$; hence Algorithm 1 converges linearly, $J_n - J^\pi_{U_p} \le O(2^{-n})$. The paper further argues that the known strong NP-hardness for non-rectangular RMDPs, proved for uncertainty sets cut by finitely many half-spaces, does not transfer to Lp balls, and it supplies an $O(S^3 A^3 \log \epsilon^{-1})$ p=2 spectral inner solver as the practical implementation.

Load-bearing premise

Algorithm 1's binary search is only as correct as the inner maximization $F(\lambda)$, and the proposed p=2 subroutine is a heuristic with no exactness or approximation guarantee, so if $F(\lambda)$ is computed inexactly the bisection decision can flip and the linear-convergence theorem does not follow.

Editorial extensions

If this is right

  • For any policy, robust evaluation under an Lp-ball uncertainty set is performed by Algorithm 1 with error decaying like $O(2^{-n})$ per bisection step; with the p=2 spectral inner solver the cost is $O(S^3 A^3 \log \epsilon^{-1})$.
  • The adversary for non-rectangular Lp uncertainty is a rank-one perturbation $\hat{P} - b k^\top$ whose direction $k$ maximizes reward loss $\langle k, v^\pi_R\rangle$ while minimizing long-term exposure to high-uncertainty states; this is the first description of the non-rectangular adversary in nominal terms.
  • Because the robust return is $J^\pi - \lambda^*$ and $\lambda^*$ is computed from nominal quantities, robust policy gradient updates can be computed without a separate NP-hard worst-kernel oracle; the resulting double-loop algorithm converges to an $\epsilon$-optimal robust policy in $O(\epsilon^{-8})$ iterations.
  • Non-rectangular Lp sets avoid the exponential over-conservatism of rectangular enclosures: the volume ratio of the smallest enclosing rectangular set to the L2 ball is exponentially small in the state-action count, so Lp sets can reduce conservatism while remaining evaluable.
  • The dual min-max formulation $J^*_{U_p} = \max_{D\in\mathcal{D}} \min_{k,b} [\mu^\top D R - \gamma \mu^\top D b\, k^\top D R/(1+\gamma k^\top D b)]$ is the first dual formulation for robust MDPs and gives a new tool for robust value- and policy-based methods.

Reading between the lines

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

  • Inference: The same union decomposition would extend to finite unions of Lp balls, which the paper names as future work, and would make any uncertainty set approximated by Lp balls evaluable; the practical bottleneck is the number of balls and the exactness of the inner norm solve.
  • Inference: A provable approximation guarantee for the inner maximization $\max_{x\ge 0, \|x\|_2\le 1}\|Ax\|_2$ would convert Algorithm 1 into an approximation scheme with certified error; without one, the linear-convergence theorem should be read as conditional on exact inner solves.
  • Inference: The spectral heuristic's accuracy likely degrades when $A^\top A$ has many comparable eigenvalues, because it selects from single-eigenvector positive parts; this is a testable prediction, namely that random matrices with near-degenerate leading eigenvalues should show larger gaps against a global solver.
  • Inference: If the fixed-point perspective transfers to other divergence-bounded uncertainty sets whose worst kernel has a closed form, non-rectangular robustness beyond Lp might also escape the half-space hardness barrier; the paper does not claim this.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 5 minor

Summary. The paper studies robust policy evaluation for non-rectangular Lp-bounded transition kernel uncertainty sets. It shows that the non-rectangular set can be decomposed into a union of sa-rectangular Lp sets (Proposition 3.2), derives a min-max fractional expression for the robust return in terms of nominal quantities (Lemma 3.3), states a dual formulation (Theorem 3.4), and proposes a binary-search algorithm (Algorithm 1) that evaluates a function F(λ) at each step, claiming linear convergence (Theorem 3.6). For p = 2 the inner maximization is handled by a spectral heuristic (Algorithm 2). The paper also derives a policy gradient and combines it with the evaluation oracle into a policy improvement scheme.

Significance. The core decomposition (Proposition 3.2) is simple and correct, and the fractional expression in Lemma 3.3 is a clean, nominal-only characterization of the robust return that provides genuine insight into the adversary's rank-one perturbation. The paper ships code and presents experiments showing large speedups over random sampling baselines. If the algorithmic guarantees could be established, this would be a valuable first step for non-rectangular Lp RMDPs. However, the main algorithmic claim is currently not supported: the inner maximization defining F(λ) is not solved exactly, and the paper itself notes that the required bilinear oracle is NP-Hard. The claimed separation from the NP-hardness result of Wiesemann et al. is also under-substantiated. The dual theorem is stated without proof. These gaps place the central contributions at risk.

major comments (5)
  1. [§3.2, Theorem 3.6; Appendix H, H.1] The linear convergence guarantee of Algorithm 1 presupposes an exact evaluation of F(λ)=max_{b∈B} ||E_λ b||_q at every bisection step. For p=2, the provided solver is Algorithm 2, and Appendix H.1 explicitly states that this approach 'may not always yield the exact solution, especially when multiple eigenvectors significantly contribute to the optimal x.' An inexact inner solve can reverse the comparison F(λ_n)>λ_n, so the bisection can move in the wrong direction; Theorem 3.6's O(2^{-n}) bound therefore does not hold for the implemented Algorithm 1 combined with Algorithm 2. This gap also propagates to Theorem 5.2, whose O(ε^{-8}) complexity calls Algorithm 1 as a subroutine. Please either provide an exact polynomial-time inner solver (or a certified approximation that provably preserves the bisection decision) and restate the guarantees accordingly, or present Algorithm 1+2 as a heuristic without the linear-convergence claim.
  2. [§3.2, Lemma 3.5] The stated equivalence 'F(λ)>λ if and only if λ>λ*' is reversed relative to the proof. In Lemma F.1, f(λ)=max_{b∈B} ||E_λ b||_q - λ = F(λ)-λ, and Proposition D.7 gives f(λ) ≥ 0 iff λ* ≥ λ. Hence F(λ) ≥ λ iff λ ≤ λ*, not λ > λ*. Algorithm 1's update rule in the main text uses the correct direction (raising λ_l when F>λ), so the algorithm is not affected by this error, but the lemma and the surrounding discussion must be corrected.
  3. [§1 and Appendix D.2] The argument that L1-bounded non-rectangular uncertainty is tractable because 'U1 is defined by a single global constraint (∥P−P̂∥1≤β)' is not valid: the L1 ball in the space of transition matrices is a polyhedral set with exponentially many facets, not a single-constraint polyhedron in the sense of the IP reduction in [9]. The claim that only knapsack-like integer programs can be reduced to U1 requires a formal proof; without it, the contribution that the NP-hardness result of [9] does not apply to Lp-bounded RMDPs is not established.
  4. [Theorem 3.4] The dual formulation for J*_Up is stated without proof and no appendix contains its derivation. Since 'derive a novel dual formulation' is one of the stated contributions, the theorem needs a proof or a precise pointer to a proof; in particular, the definition of the set D = {D^π H^π | π∈Π} and the max-min exchange must be justified.
  5. [§2, Proposition 3.1] The volume ratio claim is justified only by analogy between a sphere and an enclosing cube, but the sets in question are not full-dimensional spheres or products of cubes: each component of U^sa_2 is a ball inside the simplex affine subspace, and U2 is a ball inside the global affine subspace of stochastic matrices. The claimed exponential ratios O(c^{-SA}) and O(c^{-S}) are plausible but are not established by the proof as written.
minor comments (5)
  1. [§3.2 / Appendix H] The relationship between the inner maximization max_{b∈B} ||E_λ b||_q and the bilinear problem max_{b,k} k^T A b, which Appendix H labels NP-Hard, should be stated precisely; the two problems are not obviously equivalent for general p.
  2. [Theorem 3.4 / Lemma 3.3] The operator H^π is used without a formal definition; the phrase 'H^π R := R^π' is not sufficient to specify its action on all arguments, and the notation in Theorem 3.4 (e.g., D b for a matrix D and vector b) should be clarified.
  3. [Appendix J.2, Algorithm 5] Algorithm 5 uses a stopping criterion f(λ)>ε, whereas Algorithm 1 uses F(λ)>λ as the bisection test; the two terminating conditions should be reconciled, and the relationship between f and F should be made explicit in the algorithm box or its caption.
  4. [Appendix H.1, Proposition H.8] The proof that the set B is convex is not rigorous: the 'minor arc' argument is a sketch at best. The convexity claim may be true (as the image of a convex set under a linear map), but it needs a proper proof or a citation.
  5. [Throughout] There are numerous typos and word-level errors, e.g., 'insishts' (p.2), 'trie to tweak' (p.3), 'precious work' (p.4), 'diamension' (p.6), and 'theses uncertainty sets' (p.3). A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the non-rectangular result is derived from independent rectangular-set theorems and algebra, not from its own conclusion.

full rationale

The paper's derivation chain is: decompose the non-rectangular Lp ball Up into a union of sa-rectangular sets (Prop. 3.2/D.4), reduce each member to a rank-one worst-case kernel (Prop. 2.1, cited to [20]), apply Sherman-Morrison to get the fractional penalty term (Lemma 3.3), and then rewrite the penalty as a fixed point of F(λ) via the fractional-programming equivalence (Lemma F.1/Prop. D.7). The decomposition is a direct set equality; the rank-one and closed-form sa-rectangular results are prior published theorems about rectangular uncertainty sets that do not assume the non-rectangular conclusion, so citing them is legitimate independent support rather than circularity. The Sherman-Morrison step is algebraic and not an assumption of the target. The main technical weakness is that Theorem 3.6's linear convergence needs an exact F(λ) oracle, while Algorithm 2 is described in Appendix H.1 as a spectral method that 'may not always yield the exact solution'; this is a soundness/complexity gap, not a circular step. Also, the bisection direction stated in Lemma 3.5 (F(λ)>λ iff λ>λ*) is reversed relative to Proposition D.7 and Appendix F.1, but Algorithm 1's update uses the direction implied by D.7, so this is an internal typo rather than a circularity. No step in the paper equates a fitted parameter with the predicted quantity, nor does any load-bearing argument reduce solely to a self-citation chain.

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

No free parameters are fitted to data. The derivation relies on two published theorems from the same group, the rank-one worst-kernel result and the sa-rectangular closed form, treated as external inputs. The genuinely new step, the union decomposition, is an elementary norm identity. The main unverified ingredient is the exact solution of the inner maximization needed by Algorithm 1.

assumptions (5)
  • domain assumption The worst kernel for sa-rectangular Lp RMDPs is a rank-one perturbation of the nominal kernel: P^pi_U = Phat - b k^T.
    Imported from [20] and used in Section 3.1 and Lemma E.2 to restrict the adversary to rank-one perturbations. The paper does not re-prove it.
  • domain assumption Closed-form robust return for sa-rectangular Lp RMDPs: J^pi_U = J^pi - sum_{s,a} d^pi(s,a) b_{sa} sigma_q(v^pi_U).
    Imported from [19] and referenced in Section 3 before the dual derivation. It is not proved here.
  • domain assumption The uncertainty radius beta is small enough that every P in Up is a valid transition kernel.
    Stated in Section 3 and consistent with prior work [18, 20, 19]. The derivations do not handle positivity constraints near the boundary of the simplex.
  • standard math Sherman-Morrison formula for inverting (I - gamma(P^pi - b k^T))^-1.
    Used in Lemma 3.3 and Appendix D.1 to obtain the fractional expression for robust return. Standard linear algebra.
  • standard math sigma_q(v) = max_{||k||_p<=1, 1^T k=0} k^T v.
    Stated as Proposition D.2 and used in the fixed-point derivation for F(lambda). Follows from Holder duality and the zero-mean constraint.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes." pith.science (2026). https://pith.science/paper/3VCPNPRK

@misc{pith2026250209432,
  author       = {Pith},
  title        = {Pith review of: Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3VCPNPRK}},
  note         = {Machine review of arXiv:2502.09432}
}
abstract

We study robust Markov decision processes (RMDPs) with non-rectangular uncertainty sets, which capture interdependencies across states unlike traditional rectangular models. While non-rectangular robust policy evaluation is generally NP-hard, even in approximation, we identify a powerful class of $L_p$-bounded uncertainty sets that avoid these complexity barriers due to their structural simplicity. We further show that this class can be decomposed into infinitely many \texttt{sa}-rectangular $L_p$-bounded sets and leverage its structural properties to derive a novel dual formulation for $L_p$ RMDPs. This formulation provides key insights into the adversary's strategy and enables the development of the first robust policy evaluation algorithms for non-rectangular RMDPs. Empirical results demonstrate that our approach significantly outperforms brute-force methods, establishing a promising foundation for future investigation into non-rectangular robust MDPs.

Figures

Figures reproduced from arXiv: 2502.09432 by the authors.

Figure 1
Figure 1. Modeling Uncertainty with Non-Rectangular and Rectangular [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Illustration of Proposition 3.2: N-dimensional sphere can be written as infinite union [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Projections of set D along principal components, for S = 3, A = 2 with 10 millions samples. This figure strongly suggests the non-convexity of the set. Additionally, by maximizing the robust return J π Up over policies, we derive a novel dual formulation, as stated below. Theorem 3.4. The optimal robust return is the solution to J ∗ Up = max D∈D min k∈K,b∈B h µ T DR − γµT Db k T DR 1 + γkT Db i where D =  DπHπ | π … view at source ↗
Figures from the paper (17 more)
Figure 4
Figure 4. Figure 4: Performance of Robust Policy Evaluation methods with equal amount of time, with [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Convergence of Robust Policy Evaluation Methods, with fixed [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: MDP Pξ, and R( [PITH_FULL_IMAGE:figures/full_fig_p026_6.png]
Figure 7
Figure 7. Figure 7: Random Kernel Guess takes exponentially long time to converge. While Algorithm 1 [PITH_FULL_IMAGE:figures/full_fig_p038_7.png]
Figure 8
Figure 8. Figure 8: Comparison of optimality across methods. [PITH_FULL_IMAGE:figures/full_fig_p039_8.png]
Figure 9
Figure 9. Figure 9: Comparison of computational time across methods [PITH_FULL_IMAGE:figures/full_fig_p040_9.png]
Figure 10
Figure 10. Figure 10: 2D PCA projections of the first 5 components. [PITH_FULL_IMAGE:figures/full_fig_p042_10.png]
Figure 11
Figure 11. Figure 11: 3D PCA projection of the first three principal components. [PITH_FULL_IMAGE:figures/full_fig_p043_11.png]
Figure 12
Figure 12. Figure 12: 2D Random Projections of the Data. variations compared to brute-force (random kernel sampling) and semi-brute (random sampling of rank-one perturbations of the nominal kernel) approaches. Notably, the scipy SLSQP variant performs slightly better on average, but the sp…
Figure 13
Figure 13. Figure 13: 3D Random Projection Example. speed. Algorithm 5 Binary Search for Robust Policy Evaluation for Uncertainty set Up J.2 Our Method 1: Input: Tolerance ϵ = 0.001, β = 0.01 2: Initialize: λ = 0.5 1−γ , λmax = 1 1−γ , λmin = 0 3: while Tolerance is not met: f(λ) > ϵ do 4:…
Figure 14
Figure 14. Figure 14: Performance of Robust Policy Evaluation methods with equal amount of time. [PITH_FULL_IMAGE:figures/full_fig_p046_14.png]
Figure 15
Figure 15. Figure 15: Convergence of Robust Policy Evaluation Methods [PITH_FULL_IMAGE:figures/full_fig_p046_15.png]
Figure 16
Figure 16. Figure 16: β=0.1, A=8 [PITH_FULL_IMAGE:figures/full_fig_p047_16.png]
Figure 17
Figure 17. Figure 17: β=0.02, A=8 47 [PITH_FULL_IMAGE:figures/full_fig_p047_17.png]
Figure 18
Figure 18. Figure 18: β=0.005, A=8 [PITH_FULL_IMAGE:figures/full_fig_p048_18.png]
Figure 19
Figure 19. Figure 19: Robust Penalty Function F(λ) vs λ for S = 100, a = 10, β = 1/S 48 [PITH_FULL_IMAGE:figures/full_fig_p048_19.png]
Figure 20
Figure 20. Figure 20: Robust Penalty Function F(λ) vs λ for S = 100, a = 10, β = 0.1 49 [PITH_FULL_IMAGE:figures/full_fig_p049_20.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

57 extracted references · 52 canonical work pages

  1. [9]

    Robust markov decision processes

    Wolfram Wiesemann, Daniel Kuhn, and Breç Rustem. Robust markov decision processes. Mathematics of Operations Research, 38(1):153–183, 2013

    work page 2013

  2. [1]

    Tsitsiklis

    Shie Mannor, Duncan Simester, Peng Sun, and John N. Tsitsiklis. Bias and variance in value function estimation. InProceedings of the Twenty-First International Conference on Machine Learning, ICML ’04, page 72, New York, NY, USA, 2004. Association for Computing Machinery

    work page 2004

  3. [2]

    Robust data-driven dynamic programming

    Grani Adiwena Hanasusanto and Daniel Kuhn. Robust data-driven dynamic programming. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. 14

    work page 2013

  4. [3]

    Scaling up robust mdps using function approxi- mation

    Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust mdps using function approxi- mation. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, volume 32 ofJMLR Workshop and Conference Proceedings, pages 181–189. JMLR.org, 2014

    work page 2014

  5. [4]

    Robust control of markov decision processes with uncertain transition matrices.Oper

    Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices.Oper. Res., 53:780–798, 2005

    work page 2005

  6. [5]

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

    work page 2005

  7. [6]

    Robustness and generalization, 2010

    Huan Xu and Shie Mannor. Robustness and generalization, 2010

    work page 2010

  8. [7]

    Hospedales

    Chenyang Zhao, Olivier Sigaud, Freek Stulp, and Timothy M. Hospedales. Investigating generalisation in continuous deep reinforcement learning, 2019

    work page 2019

Show all 57 references
  1. [8]

    Assessing generalization in deep reinforcement learning, 2018

    Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song. Assessing generalization in deep reinforcement learning, 2018

    2018

  2. [10]

    Robust mdps with k-rectangular uncertainty

    Shie Mannor, Ofir Mebel, and Huan Xu. Robust mdps with k-rectangular uncertainty. Math. Oper. Res., 41(4):1484–1509, nov 2016

    2016

  3. [11]

    Robust markov decision process: Beyond rectan- gularity, 2018

    Vineet Goyal and Julien Grand-Clément. Robust markov decision process: Beyond rectan- gularity, 2018

    2018

  4. [12]

    Kaufman and Andrew J

    David L. Kaufman and Andrew J. Schaefer. Robust modified policy iteration.INFORMS J. Comput., 25:396–410, 2013

    2013

  5. [13]

    Andrew Bagnell, Andrew Y

    J. Andrew Bagnell, Andrew Y. Ng, and Jeff G. Schneider. Solving uncertain markov decision processes. Technical report, Carnegie Mellon University, 2001

    2001

  6. [14]

    Partial policy iteration for l1-robust markov decision processes, 2020

    Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for l1-robust markov decision processes, 2020

    2020

  7. [15]

    Online robust reinforcement learning with model uncertainty, 2021

    Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty, 2021

    2021

  8. [16]

    Policy gradient method for robust reinforcement learning, 2022

    Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning, 2022

    2022

  9. [17]

    Policy gradient in robust mdps with global convergence guarantee, 2023

    Qiuhao Wang, Chin Pang Ho, and Marek Petrik. Policy gradient in robust mdps with global convergence guarantee, 2023

    2023

  10. [18]

    Twice regularized mdps and the equivalence between robustness and regularization, 2021

    Esther Derman, Matthieu Geist, and Shie Mannor. Twice regularized mdps and the equivalence between robustness and regularization, 2021. 15

    2021

  11. [19]

    Efficient value iteration for s-rectangular robust markov decision processes

    Navdeep Kumar, Kaixin Wang, Kfir Yehuda Levy, and Shie Mannor. Efficient value iteration for s-rectangular robust markov decision processes. InForty-first International Conference on Machine Learning, 2024

    2024

  12. [20]

    Pol- icy gradient for rectangular robust markov decision processes

    Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Yehuda Levy, and Shie Mannor. Pol- icy gradient for rectangular robust markov decision processes. InThirty-seventh Conference on Neural Information Processing Systems, 2023

    2023

  13. [21]

    Natural actor-critic for robust reinforcement learning with function approximation

    Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Natural actor-critic for robust reinforcement learning with function approximation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023

    2023

  14. [22]

    Robust reinforce- ment learning via adversarial kernel approximation, 2023

    Kaixin Wang, Uri Gadot, Navdeep Kumar, Kfir Levy, and Shie Mannor. Robust reinforce- ment learning via adversarial kernel approximation, 2023

    2023

  15. [23]

    Solving non-rectangular reward-robust mdps via frequency regularization, 2023

    Uri Gadot, Esther Derman, Navdeep Kumar, Maxence Mohamed Elfatihi, Kfir Levy, and Shie Mannor. Solving non-rectangular reward-robust mdps via frequency regularization, 2023

    2023

  16. [24]

    Smith and Mavina K

    David J. Smith and Mavina K. Vamanamurthy. How small is a unit ball?Mathematics Magazine, 62(2):101–107, 1989

    1989

  17. [25]

    Puterman

    Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. In Wiley Series in Probability and Statistics, 1994

    1994

  18. [26]

    Tractable robust markov decision processes, 2024

    Julien Grand-Clément, Nian Si, and Shengbo Wang. Tractable robust markov decision processes, 2024

    2024

  19. [27]

    Sutton and Andrew G

    Richard S. Sutton and Andrew G. Barto.Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018

    2018

  20. [28]

    Wasserstein robust reinforcement learning, 2019

    Mohammed Amin Abdullah, Hang Ren, Haitham Bou Ammar, Vladimir Milenkovic, Rui Luo, Mingtian Zhang, and Jun Wang. Wasserstein robust reinforcement learning, 2019

    2019

  21. [29]

    Robust $\phi$-divergence MDPs

    Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Robust $\phi$-divergence MDPs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors,Advances in Neural Information Processing Systems, 2022

    2022

  22. [30]

    E. Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999

    1999

  23. [31]

    Bellemare

    Robert Dadashi, Adrien Ali Taïga, Nicolas Le Roux, Dale Schuurmans, and Marc G. Bellemare. The value function polytope in reinforcement learning, 2019

    2019

  24. [32]

    The geometry of robust value functions

    Kaixin Wang, Navdeep Kumar, Kuangqi Zhou, Bryan Hooi, Jiashi Feng, and Shie Mannor. The geometry of robust value functions. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors,Proceedings of the 39th International Conference ...

    2022

  25. [33]

    Lightning does not strike twice: Robust mdps with coupled uncertainty.CoRR, abs/1206.4643, 2012

    Shie Mannor, Ofir Mebel, and Huan Xu. Lightning does not strike twice: Robust mdps with coupled uncertainty.CoRR, abs/1206.4643, 2012

    2012 arXiv

  26. [34]

    M. S. Bartlett. An Inverse Matrix Adjustment Arising in Discriminant Analysis.The Annals of Mathematical Statistics, 22(1):107 – 111, 1951

    1951

  27. [35]

    Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, EvgeniBurovski, PearuPeterson, WarrenWeckesser, JonathanBright, StéfanJ

    Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, EvgeniBurovski, PearuPeterson, WarrenWeckesser, JonathanBright, StéfanJ. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric J...

    2020

  28. [36]

    Policy gradient methods for reinforcement learning with function approximation

    Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In S. Solla, T. Leen, and K. Müller, editors,Advances in Neural Information Processing Systems, volume 12. MIT Press, 2000

    2000

  29. [37]

    M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, first edition edition, 1979

    1979

  30. [38]

    Cambridge University Press, March 2004

    Stephen Boyd and Lieven Vandenberghe.Convex Optimization. Cambridge University Press, March 2004

    2004

  31. [39]

    Policy gradient for reinforce- ment learning with general utilities, 2023

    Navdeep Kumar, Kaixin Wang, Kfir Levy, and Shie Mannor. Policy gradient for reinforce- ment learning with general utilities, 2023. 17 A Summary of Notations and Definitions For a setS, |S| denotes its cardinality. ⟨u,v⟩ := ∑ s∈Su(s)v(s) denotes the dot product between function...

    2023

  32. [40]

    This makes sense, as the more the agent visits states with high uncertainty, the higher is the ability of the adversary to undermine it

    Maximizing the average uncertainty in the trajectoriesJπ β. This makes sense, as the more the agent visits states with high uncertainty, the higher is the ability of the adversary to undermine it

  33. [41]

    nominal value functionvπ R)

    Choosing the perturbation directionk that discourages the agent to transition into good value states (w.r.t. nominal value functionvπ R). This observation was also seen in a previous study [20], for sa and s rectangular uncertainty sets but it was w.r.t. robust value function ...

  34. [42]

    This can be done, by putting negative entries ofk at maximal entries of vπ β, and positive entries ofkT at states which has minimum uncertainty value function

    Choosing the uncertainty radius vectorβ and the perturbation directionk, such that the kTvπ β is minimized. This can be done, by putting negative entries ofk at maximal entries of vπ β, and positive entries ofkT at states which has minimum uncertainty value function. In other ...

  35. [43]

    State SpaceS ={bj,b 0 j,b 1 j|j = 1,··· ,n}∪{ c0,τ}, whereτ is a terminal state

  36. [44]

    Singleton Action Space:A= {a}

  37. [45]

    Uncertainty set:U ={Pξ|ξ∈ [0, 1]n,Fξ ≤g}

  38. [46]

    Discount factorγ∈ [0, 1); Uniform initial state distributionµ

  39. [47]

    Big rewardM≥ γAn ∑ ici 2ϵ2 where ϵ<< 1 helps in rounding

  40. [48]

    Robust policy evaluation is proven to be NP-hard for general uncertainty sets defined as intersections of finite hyperplanes [9]

    Transitions and rewards are illustrated in Figure 6 Figure 6: MDPPξ, andR(Figure 5 of [9]). Robust policy evaluation is proven to be NP-hard for general uncertainty sets defined as intersections of finite hyperplanes [9]. Specifically, robust MDPs with uncertainty setUhard := ...

  41. [49]

    Generate N random vectorsxi≥ 0, i = 1,...,N

  42. [50]

    Normalize each vector to unit norm:xi←xi/∥xi∥2

  43. [51]

    This method is simple to implement but computationally expensive, as it evaluatesA for a large number of randomly generated vectors

    Compute∥Axi∥2 for each vector and select the maximum value. This method is simple to implement but computationally expensive, as it evaluatesA for a large number of randomly generated vectors. See figure 7 37 Figure 7: Random Kernel Guess takes exponentially long time to conve...

  44. [52]

    Define the objective function as−∥Ax∥2

  45. [53]

    Impose constraints:∥x∥2≤ 1 and x≥ 0

  46. [54]

    This method provides the exact solution but is computationally more expensive than the spectral method

    Solve the problem usingscipy.optimize.minimize, with an initial guessx0. This method provides the exact solution but is computationally more expensive than the spectral method. H.3 Comparison Metrics The three methods are compared based on: • Optimality: The maximum value∥Ax∥2...

  47. [55]

    Generating random vectorsx∈ Rn for the brute force method

  48. [56]

    Computing the spectral decomposition ofA⊤A for the eigenvalue heuristic

  49. [57]

    The results, including the optimal values and computational times, are recorded for each method

    Defining and solving a constrained optimization problem for the numerical optimization method. The results, including the optimal values and computational times, are recorded for each method. 40 Evaluation Metrics The performance of the methods was assessed using the following...

    2023

Pith tools

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