Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values

• URL: http://arxiv.org/abs/2603.00945v2
• Date: Tue, 03 Mar 2026 04:40:49 GMT
• Title: Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values
• Authors: Shengbo Wang, Nian Si,
• Abstract summary: We study non-rectangular robust Markov decision processes under the average-reward criterion.<n>We show that any history-dependent policy achieving sublinear expected regret uniformly over the ambiguity set is robust-optimal.
• Score: 11.174902793218834
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study non-rectangular robust Markov decision processes under the average-reward criterion, where the ambiguity set couples transition probabilities across states and the adversary commits to a stationary kernel for the entire horizon. We show that any history-dependent policy achieving sublinear expected regret uniformly over the ambiguity set is robust-optimal, and that the robust value admits a minimax representation as the infimum over the ambiguity set of the classical optimal gains, without requiring any form of rectangularity or robust dynamic programming principle. Under the weak communication assumption, we establish the existence of such policies by converting high-probability regret bounds from the average-reward reinforcement learning literature into the expected-regret criterion. We then introduce a transient-value framework to evaluate finite-time performance of robust optimal policies, proving that average-reward optimality alone can mask arbitrarily poor transients and deriving regret-based lower bounds on transient values. Finally, we construct an epoch-based policy that combines an optimal stationary policy for the worst-case model with an anytime-valid sequential test and an online learning fallback, achieving a constant-order transient value.

Related papers

• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality [53.525547349715595]
  We propose a novel primal-only algorithm called Rectified Robust Policy Optimization (RRPO)<n>RRPO operates directly on the primal problem without relying on dual formulations.<n>We show convergence to an approximately optimal feasible policy with complexity matching the best-known lower bound.
  arXiv  Detail & Related papers  (2025-08-24T16:59:38Z)
• Best-Effort Policies for Robust Markov Decision Processes [69.60742680559788]
  We study the common generalization of Markov decision processes (MDPs) with sets of transition probabilities, known as robust MDPs (RMDPs)<n>We call such a policy an optimal robust best-effort (ORBE) policy.<n>We prove that ORBE policies always exist, characterize their structure, and present an algorithm to compute them with a small overhead compared to standard robust value iteration.
  arXiv  Detail & Related papers  (2025-08-11T09:18:34Z)
• Probabilistic Reach-Avoid for Bayesian Neural Networks [71.67052234622781]
  We show that an optimal synthesis algorithm can provide more than a four-fold increase in the number of certifiable states. The algorithm is able to provide more than a three-fold increase in the average guaranteed reach-avoid probability.
  arXiv  Detail & Related papers  (2023-10-03T10:52:21Z)
• Importance-Weighted Offline Learning Done Right [16.4989952150404]
  We study the problem of offline policy optimization in contextual bandit problems. The goal is to learn a near-optimal policy based on a dataset of decision data collected by a suboptimal behavior policy. We show that a simple alternative approach based on the "implicit exploration" estimator of citet2015 yields performance guarantees that are superior in nearly all possible terms to all previous results.
  arXiv  Detail & Related papers  (2023-09-27T16:42:10Z)
• Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets [10.560809881699468]
  We propose policy gradient algorithms for robust infinite-horizon Markov decision processes (MDPs) with non-rectangular uncertainty sets.<n>The corresponding robust MDPs cannot be solved with dynamic programming techniques and are in fact provably intractable.<n>We thus present the first complete solution scheme for robust MDPs with non-rectangular uncertainty sets offering global optimality guarantees.
  arXiv  Detail & Related papers  (2023-05-30T13:02:25Z)
• Hallucinated Adversarial Control for Conservative Offline Policy Evaluation [64.94009515033984]
  We study the problem of conservative off-policy evaluation (COPE) where given an offline dataset of environment interactions, we seek to obtain a (tight) lower bound on a policy's performance. We introduce HAMBO, which builds on an uncertainty-aware learned model of the transition dynamics. We prove that the resulting COPE estimates are valid lower bounds, and, under regularity conditions, show their convergence to the true expected return.
  arXiv  Detail & Related papers  (2023-03-02T08:57:35Z)
• Kernel Conditional Moment Constraints for Confounding Robust Inference [22.816690686310714]
  We study policy evaluation of offline contextual bandits subject to unobserved confounders. We propose a general estimator that provides a sharp lower bound of the policy value.
  arXiv  Detail & Related papers  (2023-02-26T16:44:13Z)
• Bounded Robustness in Reinforcement Learning via Lexicographic Objectives [54.00072722686121]
  Policy robustness in Reinforcement Learning may not be desirable at any cost. We study how policies can be maximally robust to arbitrary observational noise. We propose a robustness-inducing scheme, applicable to any policy algorithm, that trades off expected policy utility for robustness.
  arXiv  Detail & Related papers  (2022-09-30T08:53:18Z)
• Conformal Off-Policy Prediction in Contextual Bandits [54.67508891852636]
  Conformal off-policy prediction can output reliable predictive intervals for the outcome under a new target policy. We provide theoretical finite-sample guarantees without making any additional assumptions beyond the standard contextual bandit setup.
  arXiv  Detail & Related papers  (2022-06-09T10:39:33Z)
• Consistent Non-Parametric Methods for Adaptive Robustness [26.016647703500887]
  A major drawback of the standard robust learning framework is the imposition of an artificial robustness radius $r$ that applies to all inputs. We propose a new framework for adaptive robustness, called neighborhood preserving robustness.
  arXiv  Detail & Related papers  (2021-02-18T00:44:07Z)
• Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learning [70.01650994156797]
  Off- evaluation of sequential decision policies from observational data is necessary in batch reinforcement learning such as education healthcare. We develop an approach that estimates the bounds of a given policy. We prove convergence to the sharp bounds as we collect more confounded data.
  arXiv  Detail & Related papers  (2020-02-11T16:18:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.