acceptodds
Under review as a conference paper at ICLR 2027

Auditing Rectangularization in Robust MDPs: Selective Recoupling of Shared Transition Uncertainty

Abstract

Robust MDPs are often made tractable by assuming transition uncertainty is independent across time, states, and actions. Under this rectangular assumption, an adversary chooses the worst transition at each time-state-action triple, enabling Bellman recursion. This can be overly pessimistic when transitions share an episode-persistent factor, because locally adverse choices may not be jointly realizable. We study the intervening design problem: which declared transition dependencies yield the largest certified reduction when at most modeling blocks are recoupled? For a fixed policy and transitions affine in shared scalar factors, we derive an exact decomposition of the rectangularization gap into nonnegative defects at reachable rows. These defects yield computable certificates and a Global-Balance rule for jointly selecting dependencies, including complementarities between groups. We also provide a mixed-integer formulation, approximation and selection guarantees, and finite-data certificates valid after data-dependent selection. In generated routing and queue systems with binary persistent regimes, Global Balance captures cross-block certificate gains on 47.3% of policy-subset pairs. Restoring eight of ten blocks reduces held-out candidate-menu regret relative to full release, while an incorrect sharing map reverses the benefit of full recoupling. With six independent factors, certificate-selected blocks recover 89.5% of the full recoupling gain using 4 of the 64 conditional evaluations required by full recoupling.

Primary area:
reinforcement learning
Keywords:
robust Markov decision processes, robust reinforcement learning, non-rectangular uncertainty, transition uncertainty, rectangularization, shared transition uncertainty, uncertainty quantification, dependency selection

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_1ez5OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper discusses the limitations of rectangualrity assumption of RMDPs where the assumption is overly conservative. They provide theoretical results explaining the gap and also propose a selection algorithm to globally balance which dependencies to restore accounting for interactions between groups that simpler rankings might miss.

Critical strengths
  1. The paper addresses a genuine weakness of rectangular uncertainty sets: they can combine individually plausible transitions into an impossible joint model. Quantifying the resulting pessimism is useful for robust control and safety-critical decision-making.
  2. Theorem 1 decomposes the release gap into nonnegative local defects weighted by coherent-model state–action occupancies. This provides a precise explanation of where rectangularization pessimism comes from, rather than relying solely on empirical comparisons.
  3. The certificate pools positive and negative endpoint preferences across selected blocks. This is important because a block may have zero value in isolation but contribute substantially when selected alongside another block. The paper provides a simple example where the individual certificates are zero, but the joint certificate is positive.
Critical weaknesses
  1. How reliable is the method when the true factor structure is unknown or only partially specified? Can the authors detect misspecification or provide guarantees under uncertainty about the sharing map itself?
  2. How much of the proposed method extends to continuous factor spaces, nonlinear parameterizations, infinite-horizon problems, or policies that adapt to information about persistent latent factors?
  3. Are there practically meaningful additional assumptions, such as stronger mixing or more refined reachability bounds that give better horizon dependence?
  4. Can the certification procedure handle general categorical transitions and uncertainty in the loss function without losing its practical usefulness?
Questions for authors

See weaknesses

Reviewer_XYUhOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the overly pessimistic behavior caused by the rectangular assumption in robust MDPs. If, throughout the decision process, multiple transition rows are driven by the same shared factor, the rectangular assumption allows nature to choose the worst transition independently at each row, thereby combining extreme cases that could never occur simultaneously in reality. For a fixed policy under an affine transition structure (i.e., transitions are affine in the shared factors), the authors derive an exact identity that decomposes the value gap caused by the rectangular assumption into a weighted sum of nonnegative defects at reachable transition rows. Building on this, the authors propose the Global-Balance certificate: by separately aggregating the pressure toward each of the two endpoints and taking the smaller value, it provides a lower bound on the reduction in worst-case loss after recoupling blocks. Around this certificate, the paper also gives a mixed-integer program (MIP) for selecting blocks under a limited budget, an approximation guarantee involving the horizon factor χ−(H−1)\chi^{-(H-1)}, and finite-data certificates that remain valid after data-driven selection. Experiments are conducted on small tabular systems including routing, queue, inventory, crosswind, and CliffWalking, and the results show that the certificate holds on all instances. On a benchmark with six factors, executing only 4 of the 64 Bellman passes achieves 89.5% of the gain obtainable from full recoupling.

Critical strengths
  1. The problem the paper raises is quite novel and meaningful: it treats the rectangular assumption as a model selection that can be audited and partially revised, a perspective that is highly insightful.

  2. The theoretical derivations are rigorous and correct, and sharpness constructions are provided. The appendix also honestly presents comparisons in which the method performs poorly.

Critical weaknesses
  1. As a selection mechanism, Global Balance is no better than other methods: in the experiment of Table 3, its performance is essentially on par with Matching prefix and clearly behind the two marginal-ranking methods and the exact-defect method; however, the main text does not mention this table at all.

  2. The core theory is to a large extent a combination of known tools; moreover, under the paper’s tested settings, the χH−1\chi^{H-1} term can reach the order of 102410^{24}, giving it almost no practical guidance value.

Questions for authors
  1. Why does the main text not discuss Table 3, where Global Balance is essentially on par with Matching prefix and behind the marginal-ranking and exact-defect methods? In which settings should Global Balance be preferred over these selectors?

  2. Given that the χH−1\chi^{H-1} term can reach about 102410^{24} in the tested settings, what practical role does the approximation guarantee play?

  3. Since the 47.3% reflects how the signs of the slopes are distributed across blocks, can the abstract instead report a measure tied to decision quality?

Reviewer_amWAOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the excessive pessimism introduced by rectangularization in robust MDPs. When transition rows share an uncertain factor, treating them independently can permit mutually inconsistent worst-case choices. The paper derives an occupancy-weighted identity for this pessimism and introduces the Global Balance certificate to lower-bound the benefit of restoring shared dependence. It then formulates joint block selection under a budget as a mixed-integer optimization problem. The theoretical results provide approximation and finite-sample guarantees, including guarantees for data-dependent block selection. Experiments evaluate certificate quality, block selection, and downstream candidate policy selection. The primary scope is fixed-policy evaluation and uncertainty-set design, rather than policy learning through online interaction.

Critical strengths

The problem is well motivated, and the joint block-selection formulation provides a useful insight: two blocks with zero individual certificates can yield a positive certificate when selected together. This illustrates why independent block rankings can miss valuable interactions and provides a clear rationale for joint selection.

The paper also characterizes conditions under which the certificate becomes loose, rather than presenting only favorable guarantees. The finite-sample guarantee for data-dependent selection and the experiments with misspecified sharing structures further strengthen the analysis by addressing both statistical validity and the consequences of incorrect modeling assumptions.

Critical weaknesses
  1. The empirical advantage of Global Balance is not consistent across settings.\textbf{The empirical advantage of Global Balance is not consistent across settings.} In Table 3, Global Balance and Matching achieve similar AUC values, and the confidence interval for their difference includes zero. The six-factor experiment shows a larger advantage, but its construction makes singleton certificates zero and is therefore particularly well suited to demonstrating the benefits of joint selection. This is a useful mechanism study, but it does not by itself establish a general advantage. The eight-factor results also show improvements, although smaller ones. Moreover, the inventory, crosswind, and CliffWalking experiments primarily evaluate exact-defect ranking rather than Global Balance. These results support the broader framework, but leave the effectiveness of the main proposed selector across diverse environments less well established.

  2. Certificate tightness and subset-selection quality are distinct, and the latter requires further evaluation.\textbf{Certificate tightness and subset-selection quality are distinct, and the latter requires further evaluation.} The approximation guarantee depends on χ−(H−1)\chi^{-(H-1)} and can become weak for long horizons. The authors acknowledge this limitation and provide certificate-tightness experiments. However, these experiments do not directly establish whether maximizing the certificate continues to select subsets with near-optimal actual gains when the bound becomes loose. A direct comparison with the best achievable gain under the same budget would better clarify the practical implications of the theoretical limitation.

  3. The connection between the selection objective and downstream policy selection is not sufficiently clear.\textbf{The connection between the selection objective and downstream policy selection is not sufficiently clear.} Equation (17) maximizes the average certificate over probe policies, whereas the candidate policy regret bound in Remark 14 depends on the maximum remaining pessimism over candidate policies. Reducing average pessimism does not necessarily improve the relative ranking of the policies that determine the final decision. Further justification is needed to explain why the proposed average objective is appropriate for downstream policy selection.

  4. The computational comparisons do not fully establish an advantage under matched total cost.\textbf{The computational comparisons do not fully establish an advantage under matched total cost.} A block budget does not directly control evaluation cost, which depends on the number of retained factors and can grow exponentially. Consequently, selecting the same number of blocks can incur different computational costs. Appendix F.9 reports selection times after the score arrays have been constructed, excluding score construction and policy evaluation. Although the paper provides some runtime results, the overall computational advantage remains unclear without comparisons that include these components and account for differences in evaluation cost.

Questions for authors
  1. Could the authors report Global Balance results on inventory, crosswind, and CliffWalking alongside the existing exact-defect results? How does it compare with Matching and exact-defect ranking in terms of actual gain and, where applicable, candidate policy selection performance? Reporting how often the Global Balance certificate is zero would also help clarify its usefulness in these settings.

  2. In the horizon and overlap experiments in Appendix F.6, how close is the actual gain of the subset selected by Global Balance to the maximum achievable gain under the same budget? For small instances where exhaustive comparison is feasible, this would help distinguish a loose certificate from poor subset selection.

  3. What motivates the average-certificate objective in Equation (17), given that Remark 14 depends on maximum remaining pessimism? Is there a theoretical justification or empirical comparison supporting this objective for candidate policy selection?

  4. Could the authors compare the total runtime of Global Balance, Matching, sequential fitted-gain, and full recoupling, including score construction, subset selection, and final policy evaluation? Please distinguish comparisons under equal block budgets from those under equal retained-factor counts or evaluation budgets.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.