acceptodds
Withdrawn from ICLR 2027

Minimax-Optimal Robust Reinforcement Learning with -divergence Uncertainty Set under - and -Rectangularity

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We study the sample complexity of model-based distributionally robust reinforcement learning (DR-RL) with -divergence defined uncertainty set under balanced nominal generative-model sampling. For -rectangular uncertainty set, existing upper and lower bounds do not match in the uncertainty level . We close this gap by establishing a tighter upper bound of , which matches with the minimax lower bound and thus we establish the minimax optimality. Here, is the discount factor, and are the state and action spaces, and is the optimality gap. Our proof develops a novel variance-sensitive framework that exploits the second-moment structure of adversarial density ratios to control robust Bellman estimation and to propagate statistical errors while preserving dependence linear in the divergence. For -rectangular uncertainty set with shared state-wise budget of , we further establish an upper bound of and also a matching minimax lower bound, and therefore we establish the minimax optimality also for -rectangular uncertainty set. Our results show that the sample complexity shall not depend on the minimum of non-zero transition probability of the nominal transition kernel, and provide the correct scaling with the uncertainty level .

Primary area:
learning theory
Keywords:
learning theory, Chi-Square, distributionally robust reinforcement learning

Reviews

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

This paper studies discounted tabular distributionally robust reinforcement learning with χ2\chi^{2}-divergence uncertainty sets under the model-based setting. The paper analyzes the uncertinaty for both SA- and S-rectangular uncertinty sets. The claimed total sample complexities are O~(∣S∣∣A∣ε3(1−γ)3(1+ρ1−γ))\widetilde O\left(\frac{|S||A|}{\varepsilon^{3}(1-\gamma)^{3}}(1+\frac{\rho}{1-\gamma})\right) that closes the uncertinaty size regime (1−γ)2≪ρ≪1(1-\gamma)^{2}\ll \rho \ll 1 which matches the minimal optimality for all regimes and eliminate the pmin⁡p_{\min} dependence. The proposed analysis uses the second moments of adversarial density ratios to obtain a variance-sensitive Bellman error bound.

Critical strengths
  1. The problem close the parameter regime gap Previous work has achieved minimax optimality in both small- and large-parameter regimes; however, these results involve terms of the form max⁡{ρ,ρ}\max\{\rho, \sqrt{\rho}\}. This paper addresses this gap by introducing a variance-sensitive framework that exploits the second-moment structure of adversarial density ratios. This framework enables us to control robust Bellman estimation errors and their propagation while maintaining a linear dependence on the divergence.

  2. The technique novelty is clear. The technique contribution variance-sensitive analysis of the χ2\chi^2-robust Bellman operator. The analysis exploits the second-moment structure of worst-case likelihood ratios to relate estimate error to the adversarial variance and the uncertainty radius, providing a promising route to the claimed linear dependence on the radius. Extending this approach to S-rectangular uncertainty sets is also technically meaningful.

Critical weaknesses

My main concern is an unjustified change of probability measure in Appendix B, page 21. Lines 1099–1105 bound the variance of the normalized dual function under the interpolated nominal distribution P0,s,a(t)P_{0, s,a}(t), whereas the Bernstein relateds steps in lines 1113-1118 requires the variance under the nominal transition kernel P0,s,aP_{0,s,a}. Lines 1120-1121 then substitute the former bound for the latter without establishing a comparison between these two variances. At the empirical endpoint t=0t=0, both the dual threshold and its normalizer are defined under P^0,s,a\widehat P_{0,s,a}, so the preceding KKT identifier dnes not directly justify the required bound under P0,s,aP_{0,s,a}, which affects the variance-sensitive estimation bound used to support the main upper bound result.

Questions for authors
  1. What inequality or high-probability argument justifies transferring the variance bound from P0,s,a(t)P_{0,s,a}(t) to P0,s,aP_{0,s,a}, particularly at t=0t=0, where the dual threshold and normalizer depend on the empirical samples?
  2. Can you provide a more detailed derivation and propagate any additional error terms through the sample-complexity analysis, showing that the stated rates remain valid without introducing dependence on the minimum positive transition probability? It is unclear for me how the minimal support probability parameter is eliminated.
  3. In my opinion, the primary contribution of this paper lies in establishing convergence guarantees for the "intermediate-gap" regime where (1−γ)2≪ρ≪1(1-\gamma)^2\ll\rho\ll 1, while simultaneously eliminating the dependence on pmin⁡p_{\min}. Including a table in the "Related Work" section that compares the different regimes would significantly enhance the paper's readability.

If the authors resolve this issue and show that the stated convergence rates are preserved, I would reconsider my assessment and consider raising my score.

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

The paper studies robust RL with chi-square uncertainty sets under balanced sampling from a nominal generative model. It develops upper and lower sample-complexity bounds for SA- and S-rectangular models using variance-sensitive Bellman analysis and shared-budget lower-bound constructions.

Critical strengths

I find the shared-budget lower-bound construction interesting because it separates branch selection from transition estimation. The distinction between balanced sampling and adaptive allocation is also useful for understanding exactly what the claimed rates cover.

Critical weaknesses
  1. The main concentration step does not justify the data-dependent quantity to which it is applied. In Equations (18)–(19) on page 15, the optimizing threshold at t = 0 and its normalizer are computed from the empirical transition distribution. The Bernstein bound on page 16 (lines 848–857) then treats the resulting normalized function as though it were fixed independently of those same samples. Fixing the value function does not resolve this dependence. A uniform concentration event over the relevant thresholds and normalizers, or another valid argument, is needed; I could not find one that supports this step. The zero-expectation assertion on page 15 (lines 802–804) has the same problem: unbiasedness of the empirical transition distribution does not imply zero expectation after multiplying by a function selected from that distribution. These are substantive gaps in the statistical argument supporting the upper bounds.

  2. The proof does not complete the passage to the claimed policy-error bounds. Section 6 describes an absorbing-state/scalar-grid construction and a two-sided resolvent comparison, but I could not locate their full implementation for the empirical value functions and policies used in the analysis. The calculations in Appendices B and C end with robust-expectation error bounds (pages 23 and 29); they do not by themselves complete the derivation from Lemma 4 to Theorems 1–2. In particular, the proof needs to handle empirical policies and S-rectangular budget allocations, and propagate the variance terms when the relevant minimizing kernels differ, while retaining the stated parameter dependence. I do not think these steps can simply be left implicit in a paper whose main claim is a sharp sample-complexity characterization.

Taken together, these issues leave me unconvinced that the claimed minimax-optimal upper bounds are established by the current proof. My negative assessment is primarily about this lack of a complete justification, rather than about presentation alone. Separately, the saturated/degenerate case in Proposition 1 (page 15) needs an explicit treatment when the displayed normalizer vanishes; I view this as a secondary, potentially local repair.

Questions for authors
  1. What concentration event controls the sample-dependent thresholds and normalizers in Equations (18)–(19), including empirical policies and S-rectangular budget allocations?
  2. Where is the absorbing-state or scalar-grid argument established for the empirical value functions used in the proof?
  3. Could you complete the derivation from Lemma 4 to Theorems 1–2, particularly variance propagation when minimizing kernels differ? A complete justification could materially change my soundness assessment.
Reviewer_QqJhOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the sample complexity of robust RL with χ2\chi^2-divergence uncertainty sets. It aims to close the uncertainty-radius gap under SA-rectangularity and establish matching bounds for shared-budget S-rectangularity. The approach uses empirical robust value iteration, supported by theoretical upper and lower bounds.

Critical strengths
  • The paper addresses a concrete statistical question about the precise cost of χ2\chi^2 robustness as the uncertainty radius varies.

  • The shared-budget S-rectangular lower-bound construction accounts for randomized policies and appears sound after reconciling the divergence convention.

Critical weaknesses
  • I could not verify the complete derivation of Theorems 1–2. The detailed arguments establish local Bellman estimation bounds, but the treatment of data-dependent value functions and dual thresholds, and the subsequent variance propagation needed for the stated policy-error rates, remain insufficiently demonstrated. Section 6 mentions uniform concentration, an absorbing-state construction, and resolvent absorption, but I could not locate the corresponding complete arguments. These steps are essential to the central claims.

  • Proposition 1 does not appear to hold as stated in saturated cases, where the proposed kernel formula can have a zero denominator. For example, taking P0=(1/2,1/2),V=(0,1),ρ=2P_0=(1/2,1/2), V=(0,1), \rho=2 makes the displayed dual objective uniquely maximized at η∗=0\eta^*=0. The treatment of these cases and zero radius needs clarification, especially since later arguments rely on this formula.

Questions for authors
  • Please help resolve the concerns in the weakness part.
  • Also, how is the action-dependent remainder in the final inequalities eliminated without an additional assumption on ∣A∣|A|?

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

Related papers

Discussion (0)

Sign in to comment.