acceptodds
Under review as a conference paper at ICLR 2027

Bridging Likelihood-Ratio Offline RL and Robust RL: Tractability and Error Bounds

Abstract

Likelihood-based offline reinforcement learning optimizes against models that fit the data, but its statistical appeal comes with a computational obstacle. A single likelihood constraint couples the entire model, whereas row-wise robust dynamic programming minimizes transition rows independently. We develop a tractable bridge between these formulations and quantify the price of using it. For tabular product transition models, planning over the exact state–action rectangular hull reduces to scalar reverse-KL problems and value iteration. Our central contribution is a two-sided, occupancy-sensitive analysis of the resulting approximation: a convex repair constructs a likelihood-feasible adversary, and a complementary convex program lower-bounds the loss incurred by independent row minimization. The error depends on incompatibility along visited rows, not likelihood-budget overspending alone. We characterize exactness for arbitrary initialization and distinguish fixed-policy approximation from coupled policy optimality. Combining this analysis with likelihood calibration yields offline performance guarantees that separate statistical uncertainty, relaxation error, and numerical error. The construction extends to valid shared linear-mixture models. Finite-model experiments support the bridge through faster matched-objective rectangular planning, occupancy-sensitive gap bounds, and common-parameter exactness checks. The bridge therefore makes a principled approximation to likelihood-based offline planning implementable and explains the additional pessimism introduced for computation.

Primary area:
reinforcement learning
Keywords:
offline reinforcement learning, robust reinforcement learning, likelihood-ratio models

Reviews

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

This paper quantifies the price of replacing the coupled likelihood-ratio objective of CPPO-LR — which shares one global reverse-KL budget across all transition rows and is computationally intractable — with its (s,a)(s,a)-rectangular relaxation, which is solvable by standard robust value iteration. The key geometric fact is that the rectangular hull of the likelihood region hands every row the full budget independently, and the authors use this to characterize exactly when the relaxation is lossless: because any nontrivial reverse-KL row minimizer must saturate the budget, exactness requires at most one visited row to be “critical,” with a reachability-based refinement for arbitrary initial distributions. When exactness fails, two complementary convex programs — an occupancy-weighted repair and a dual lower envelope — bracket the coupled value, and combining these with likelihood calibration under two sampling designs yields an offline guarantee that separates statistical uncertainty, rectangularization error, and numerical error. The construction extends to valid shared linear-mixture models. Experiments on small tabular domains (FrozenLake, forest, a two-state recurrent chain) separately test planning speed at matched objective, the tightness of the two-sided bounds, and exactness under shared parameters; the authors are explicit that these do not demonstrate statistical dominance over CPPO-LR or end-to-end policy improvement.

Critical strengths

Proposition 1 plus the budget-saturation identity (Eq. 5) is the paper’s real intellectual contribution. The observation that the rectangular hull hands every row the full budget bb (radius b/Nib/N_i, not a recalibrated row threshold), combined with the fact that any nontrivial reverse-KL minimizer must spend bb exactly, yields a sharp and very legible criterion: exactness requires at most one visited covered row to have a non-degenerate value profile. This specializes the general simultaneous-solvability perspective (Grand-Clément et al., 2026) to the likelihood set in a way that is both concrete and checkable, and Theorem 3’s reachability refinement (unreachable uncertainty is repairable at zero cost; recurrently visited rows compete for the budget) is a genuinely illuminating structural statement. This is consequential because it converts a vague “rectangularization is conservative” intuition into a decidable condition with a finite algorithm.

Critical weaknesses

Once one has decided to plan over a rectangular set, nothing forces that set to be the hull of Ub\mathcal{U}_b. A union-bounded product region with per-row budgets bi=(ki−1)+2(ki−1)log⁡(1/βi)+log⁡(1/βi)b_i=(k_i-1)+\sqrt{2(k_i-1)\log(1/\beta_i)}+\log(1/\beta_i) is also a valid 1−β1-\beta confidence set, is solved by the same scalar reverse-KL oracles at the same cost, and is strictly contained in Rect(Ub)\mathrm{Rect}(\mathcal{U}_b), since b≈D=∑i(ki−1)≫bib\approx D=\sum_i(k_i-1)\gg b_i. The paper acknowledges this at l.

1654–1657 (“This can improve the generic rectangular bound”) and moves on. But this is precisely the comparison that determines whether the machinery is useful: the hull’s per-row radius is ∼D/Ni\sim D/N_i rather than ∼(ki−1)/Ni\sim(k_i-1)/N_i, i.e. conservative by a factor ∼m\sim m in KL and ∼m\sim\sqrt m in TV, which is exactly the m\sqrt m loss that appears when comparing (16) to the matched coupled bound (37). The only thing the hull buys over direct calibration is a certified relationship to JLRJ_{\mathrm{LR}} — a quantity nobody can compute. Absent either a theoretical argument that the hull can beat row-wise calibration or an experiment showing it does, the practical recommendation that follows from this paper is “calibrate row-wise and skip the bridge,” which undercuts the stated motivation.

Questions for authors

Please compare Rect(Ub)\mathrm{Rect}(\mathcal{U}_b) against a directly calibrated product region with union-bounded per-row budgets bib_i — both theoretically and on the recurrent cohort of Sec. 6.2. Specifically: is there any regime in which the hull yields a tighter valid pessimistic value than row-wise calibration? If not, is the correct reading of the paper that the bridge is a diagnostic for CPPO-LR rather than a planning recommendation?

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

This paper studies the connection between likelihood-based offline RL and rectangular robust RL. In likelihood-based offline RL, a single log-likelihood constraint defines a joint model confidence set e.g. P:∑s,a,s′∈Dlog⁡P(s′∣s,a)≤b\\{P: \sum_{s,a,s'\in D}\log P(s'|s,a)\leq b\\}, coupling transition distributions across state–action pairs. Rectangular robust planning instead uses decoupled uncertainty sets for each transition P(⋅∣s,a)P(\cdot\mid s,a), enabling efficient dynamic programming. The paper approximates the joint confidence set by its smallest rectangular superset and analyzes the additional pessimism introduced by this relaxation. Its main results characterize and bound the evaluation gap for a fixed policy, while a separate result bounds the returned policy’s suboptimality under the original joint objective.

Critical strengths
  1. The paper provides computable programs to support efficient computation.
Critical weaknesses
  1. The presentation is hard to follow. There are many terms are presented before clearer explanation. For example, the first page introduces “initialization-aware exactness” without clarifying what is “initialization” or what is "exactness". Additionally, the related work is in Appendix J, and contribution discussion is not clear for the at the beginning. It is therefore hard to tell which part of the analysis is new and which part exists.

  2. The motivation is unclear. From my understanding, tabular offline RL already has provably efficient solution and can usually achieve optimal performance [1]. Why it is necessary to relax that to this decoupled constraint?

[1] Li, et al., Settling the Sample Complexity of Model-Based Offline Reinforcement Learning, 2024.

Questions for authors
  1. My question is about the motivation: why we need to relax the likelihood constraint provided tabular offline RL is efficiently implementable.
Reviewer_qPuJOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the approximation gap introduced by replacing a globally coupled likelihood-ratio uncertainty set in offline RL with its state-action rectangular hull. Under the original likelihood constraint, a single global budget is shared across all transition rows. The rectangular hull considered in this paper allows each covered state-action row to independently use the full likelihood budget. This design makes robust planning and computationally tractable by reducing it to row-wise value iteration. There are three main theoretical contributions:

  1. It characterizes the exact state-action rectangular hull and establishes conditions under which rectangularization is exact. When exactness fails, the authors derive two-sided bounds on the fixed-policy approximation gap using an occupancy-weighted feasible-model repair and a complementary convex optimization problem.
  2. It distinguishes fixed-policy evaluation error from policy suboptimality under the original coupled likelihood objective. The authors provide a coupled policy-suboptimality bound for the exact rectangular greedy policy and an offline performance guarantee that separates statistical uncertainty, rectangularization error, and numerical optimization error.
  3. They extend the framework to linear-mixture MDPs while explicitly preserving the validity of the entire shared transition model through normalization and non-negativity constraints. The experiments demonstrate substantial warm-solve speedups over cached conic solvers at matched objectives and accuracy targets, provide tight upper and lower bounds on the approximation gap in a recurrent MDP, and examine exactness under shared transition parameters.
Critical strengths
  1. The paper provides an interesting perspective on understanding and quantifying the additional conservatism introduced by rectangularizing a globally coupled likelihood uncertainty set in offline RL.
  2. The empirical results provide useful evidence supporting the theoretical analysis. In particular, the experiments demonstrate the effectiveness of the proposed computational approach and illustrate the tightness of the approximation-gap bounds in the studied settings.
Critical weaknesses
  1. The actual policy optimality gap of interest is JLR⋆−JLRπ~J_{LR}^\star - J_{LR}^{\tilde{\pi}}, where π~\tilde{\pi} is the policy returned by the approximate planner. Proposition 6 provides a coupled policy-suboptimality bound for the exact rectangular greedy policy πR\pi_R. Meanwhile, Proposition 13 bounds the numerical policy loss of an approximately greedy policy π~\tilde{\pi} under the rectangular objective. However, the paper does not explicitly establish how these results translate into a bound on the coupled-objective suboptimality of π~\tilde{\pi}.

  2. The main empirical evaluation of the approximation-gap uses a recurrent model with only two unknown transition rows. Although Section 6.1 demonstrates computational speedups on larger tabular benchmarks, the tightness and practical usefulness of the proposed gap bounds have not been demonstrated on these larger or more complex MDPs. It remains unclear how these bounds would be more realistic in large-scale settings.

  3. Several theoretical results are nontrivial, but their underlying proof ideas are only briefly discussed in the main text, with the complete proofs deferred to the appendices. Providing more explicit proof sketches for the key theorems and propositions would help readers better understand the main technical arguments and the intuition behind the proposed approximation bounds.

Questions for authors

Please see the weaknesses noted above.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.