Source-linked AI summary
Offline Reinforcement Learning with Realizability and Single-policy Concentrability
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, Jason D. Lee
TL;DR
Offline RL sample-efficiency guarantees have often required strong assumptions on both data coverage and function approximation, and prior work had relaxed only one at a time. The paper analyzes a regularized primal-dual algorithm that models discounted occupancy with a density ratio. It reports polynomial sample complexity under realizability and policy-coverage assumptions.
Problem
Prior offline RL work relaxed either data-coverage or function-approximation assumptions, leaving the other strong assumption in place.
Source: §1 · p. 2Method
The algorithm uses an MDP primal-dual formulation and models discounted occupancy with a density-ratio function against offline data.
Source: §1 · p. 3Results
With proper regularization, the algorithm has polynomial sample-complexity guarantees when its density ratio and regularized optimal-policy value function are realizable and the data covers that policy.
Source: §1 · p. 3Takeaways & Limitations
The analysis gives a positive answer to whether sample-efficient offline RL is possible with realizability and weak policy coverage assumptions.
Source: §1 · p. 3The main guarantee technically requires two-policy rather than single-policy concentrability; the paper separately addresses competing with the best policy supported on data.
Source: §4.1 · p. 12
Abstract
from arXiv · showhide
Sample-efficiency guarantees for offline reinforcement learning (RL) often rely on strong assumptions on both the function classes (e.g., Bellman-completeness) and the data coverage (e.g., all-policy concentrability). Despite the recent efforts on relaxing these assumptions, existing works are only able to relax one of the two factors, leaving the strong assumption on the other factor intact. As an important open problem, can we achieve sample-efficient offline RL with weak assumptions on both factors? In this paper we answer the question in the positive. We analyze a simple algorithm based on the primal-dual formulation of MDPs, where the dual variables (discounted occupancy) are modeled using a density-ratio function against offline data. With proper regularization, we show that the algorithm enjoys polynomial sample complexity, under only realizability and single-policy concentrability. We also provide alternative analyses based on different assumptions to shed light on the nature of primal-dual algorithms for offline RL.
1 Introduction
Offline RL guarantees have typically required strong assumptions on data coverage and function approximation, while prior efforts relaxed only one factor at a time. This paper proposes a primal-dual algorithm intended to obtain sample efficiency under weaker assumptions on both.
1 Introduction
- Offline RL faces distribution shift and function-approximation error, while common guarantees require all-policy concentrability and Bellman-completeness.The paper defines sample efficiency as polynomial sample complexity in relevant parameters.Source: §1 · p. 2
- Prior offline RL analyses relax either data-coverage or function-approximation assumptions, but not both simultaneously.Some approaches use single-policy concentrability but retain completeness-type assumptions.Source: §1 · p. 2
- The paper asks whether sample-efficient offline RL is possible under realizability and single-policy concentrability, and answers positively with a primal-dual algorithm.It models the dual variables, corresponding to discounted occupancy, with a density-ratio function against offline data.Source: §1 · p. 3
- With regularization, the main result gives polynomial sample-complexity guarantees under realizability of the density ratio and regularized optimal-policy value function, with data covering that policy.The paper also studies approximation and optimization errors, uncovered optimal policies, unknown behavior policies, and an unregularized algorithm under alternative assumptions.Source: §1 · p. 3
1.1 Related works
- Existing lower bounds do not contradict the results because the analysis also assumes realizability of the density-ratio function.The paper identifies marginalized importance weights as a key insight, a technique common in off-policy evaluation literature.Source: §1.1 · pp. 3–4
- Unlike AlgaeDICE and MABO, the approach uses an MDP linear-programming formulation to solve directly for an optimal policy rather than evaluate other policies.OptiDICE is closely related and inspired the work, but the paper says its own design choices are important for the desired sample-complexity guarantees.Source: §1.1 · p. 5
2 Preliminaries
The preliminaries define the discounted MDP setting, policies and their occupancies, and the offline learning objective based on a fixed dataset.
2 Preliminaries
- The setting is an infinite-horizon discounted MDP with state and action spaces, transition function, initial-state distribution, bounded rewards, and discount factor.The results are stated not to depend on finite state- or action-space cardinalities.Source: §2 · p. 5
- A policy induces a discounted state-action occupancy and associated value and action-value functions, while the RL objective is to maximize expected discounted return.The unregularized optimal policy is denoted π*.Source: §2 · p. 5
- Offline RL uses a pre-collected dataset whose state-action pairs are sampled from the offline distribution, with rewards and next states supplied by the reward and transition functions.The behavior policy is represented by the dataset's conditional action distribution given state.Source: §2 · p. 5
3 Algorithm: PRO-RL
PRO-RL uses a regularized primal-dual formulation of the MDP linear program, representing dual variables with occupancy density ratios against offline data. The section motivates regularization with a construction where the unregularized algorithm can fail even with infinite data.
3 Algorithm: PRO-RL
- PRO-RL uses a regularized MDP linear-program formulation, modeling dual variables as discounted-occupancy density ratios against offline data.The formulation extracts a policy from the resulting occupancy solution.Source: §3 · p. 6
- Behavioral regularization penalizes divergence from the offline-data occupancy, encouraging the learned policy's occupancy to stay within the data distribution.The regularizer f is strongly convex and continuously differentiable.Source: §3 · p. 6
- The algorithm optimizes an empirical primal-dual objective over function classes V and W that approximate the value function and density ratio.It assumes the behavior policy is known; Section 4.4 extends the results to an unknown behavior policy estimated by behavior cloning.Source: §3 · p. 7
- Regularization is crucial to the main result; the unregularized algorithm can fail even with infinite data under realizability and coverage of the optimal policy.In the construction, two actions are equally optimal at initial state A, but the data do not cover actions at state C, where the MDP instances differ in reward.Source: §3 · pp. 7–8
- With the same optimal value function, the unregularized objective cannot distinguish occupancies choosing L or R at A, and may select R, leading to a suboptimal action at C.The example's function class contains the optimal value function, and the offline data cover (A, L), (A, R), and B.Source: §3 · p. 8
4 Main results
The main results analyze PRO-RL’s polynomial-sample guarantees under realizability and weak data-coverage assumptions, extending them to approximation and optimization errors, arbitrary data distributions via covered-policy competition, unknown behavior policies, and the unregularized setting. Across these settings, the guarantees trade off policy coverage, realizability, and sample complexity.
4.1 Sample-efficiency with only realizability and weak concentrability
- For unregularized learning, Corollary 1 requires coverage of two policies, while the high-accuracy result can use concentrability and realizability for the unregularized optimizer.The paper identifies this high-accuracy regime as ǫ → 0; its stated guarantee also requires W to contain the unregularized optimizer’s density ratio.Source: §4.1 · p. 12
- PRO-RL learns near-optimal policies for regularized and unregularized objectives with polynomial samples under realizability and weak data-coverage assumptions.The main guarantees assume exact realizability and single-policy concentrability; the unregularized guarantee controls the regularization parameter.Source: §4.1 · pp. 10–12
4.2 Robustness to approximation and optimization errors
- Inexact-PRO-RL retains polynomial-sample near-optimality guarantees when approximation and optimization errors are present.The analysis measures approximation errors in ℓ1 norm and incorporates both approximation and optimization errors into its guarantee.Source: §4.2 · p. 13
4.3 Handling an arbitrary data distribution
- For arbitrary offline-data distributions, PRO-RL can compete with policies whose occupancy is bounded by Bw times the data distribution, without assuming data coverage.It imposes d(s, a) ≤ Bw dD and makes realizability assumptions with respect to the optimizer of this constrained problem.Source: §4.3 · p. 15
- Corollary 4 lets PRO-RL compete with π*_0 using concentrability only for π*_0, rather than requiring coverage for both the unregularized and regularized optimal policies.This resolves the two-policy concentrability requirement by setting the density-ratio bound to Bw,0; the result requires the stated realizability and boundedness assumptions.Source: §4.3 · p. 18
4.4 Policy extraction via behavior cloning
- PRO-RL-BC handles an unknown behavior policy by minimizing a weighted ℓ1 imitation objective, avoiding the KL approximation condition used by maximum-likelihood cloning.Its extra samples affect only higher-order terms, so total sample complexity is dominated by the PRO-RL estimation samples, matching the known-behavior rate.Source: §4.4 · pp. 18–20
4.5 PRO-RL with α = 0
- With α = 0, PRO-RL has a faster sample-complexity rate and realizability for the unregularized optimizers, but requires much stronger concentrability and is less general.The strong condition includes standard all-policy concentrability and a lower bound on the optimal policy’s density ratio.Source: §4.5 · pp. 21–22
5 Analysis for regularized offline RL (Theorem 1)
The proof uses saddle-point invariance to justify restricting the primal-dual optimization to the chosen function classes, then combines concentration bounds and strong concavity to control the learned solution. The accompanying discussions compare PRO-RL with OptiDICE and clarify assumption strength and practical extensions.
5.1 Intuition: invariance of saddle points
- Restricting the optimization sets preserves the saddle point when they contain the original solution, supporting optimization over V × W.The proof sketch then uses an unbiased empirical objective, uniform convergence, and strong concavity in w to control the learned dual variable.Source: §5.1 · p. 23
5.2 Preparation: boundedness of v∗
- KKT conditions and positive occupancy for some action at each state are used to bound v*_α under Assumptions 1 and 5.The proof sketch also bounds the empirical objective using boundedness assumptions before applying concentration inequalities.Source: §5.2 · p. 23, §5.3 · p. 23
5.3 Proof sketch of Theorem 1
- The proof sketch combines concentration, saddle-point invariance, and strong concavity to control the learned occupancy weights and policy error.It separately handles states with positive and zero estimated state occupancy when relating weights to the policy.Source: §5.3 · pp. 23–24
A.1 Comparison with OptiDICE (Lee et al., 2021)
- Unlike OptiDICE’s arbitrary-v optimization, PRO-RL optimizes over V × W, avoiding a completeness-type assumption; its policy-extraction algorithm requires policy realizability without increasing sample complexity.The OptiDICE comparison identifies double sampling and the need to approximate ev for arbitrary v as obstacles to analyses under realizability alone.Source: §A.1 · pp. 29–30
A.2 Discussion about Assumption 14; A.3 Combination of different practical factors
- Assumption 14 is weaker than Assumption 17 because the upper bound in Assumption 17 implies Assumption 14.For α > 0, the paper says PRO-RL can combine its results for approximation and optimization error, poor coverage, and unknown behavior policy; the corresponding α = 0 extensions for coverage relaxation and unknown behavior policy are difficult.Source: §A.2 · p. 30, §A.3 · pp. 30–31
B.9 Proof of Lemma 12
The proof invokes the performance difference lemma and rewrites the value difference between two policies using the discounted occupancy of one policy.
B.9 Proof of Lemma 12
- The value difference between policies is expressed using the discounted occupancy of π′ and the advantage of π′ over π.The derivation uses the definition of dπ′ and Vπ(s) = E_a∼π(·|s)[Qπ(s,a)].Source: §B.9 · pp. 36–37
C Proof of Corollary 1
The proof derives Corollary 1 by comparing the regularized solution with the unregularized objective and applying properties of the regularizer.
C Proof of Corollary 1
- The proof uses that the regularized solution optimizes problem (2)(3) to compare its objective with the unregularized solution.The displayed inequalities then use non-negativity of f and, when α = 0, its boundedness under Assumption 5.Source: C Proof of Corollary 1 · p. 37
- The proof’s comparison distinguishes the α = 0 case, where boundedness of f is invoked, from the regularized case.This condition is stated in the explanation of inequalities (140) and (141).Source: C Proof of Corollary 1 · p. 37
- The final comparison follows by combining the preceding bounds.The supplied proof passage identifies this combination as the concluding step.Source: C Proof of Corollary 1 · p. 38
D Proof of Proposition 1
The proof relates the regularized problem to a constrained optimization formulation and compares their primal and dual optima through KKT conditions.
D Proof of Proposition 1
- The proof recasts the regularized problem using a more commonly used Lagrangian and an auxiliary constrained optimization problem.It represents the equality constraint as Aw = b before forming the associated linear program.Source: D Proof of Proposition 1 · pp. 38–39
- The proof establishes equivalence between the auxiliary problem’s constraints and membership in W*aux, then examines its KKT conditions.It uses those conditions to compare the auxiliary problem with the Lagrangian formulation.Source: D Proof of Proposition 1 · p. 39
D.1 Proof of Lemma 13
- Lemma 13’s proof compares equations for the regularized and unregularized solutions to relate their corresponding multipliers.The passage states that the two equation systems are the same, implying equality of the indicated multiplier.Source: §D.1 · pp. 40–41
E Proof of Theorem 2
The proof follows Theorem 1's three-step procedure, with a more complicated second step. It uses continuity bounds for the Lagrangian under Assumptions 4, 5, and 6.
E Proof of Theorem 2
- The proof reuses Theorem 1's first and third steps, while elaborating a more complicated second step.It bounds the empirical-to-population Lagrangian difference, characterizes the error in w, and completes the proof using strong convexity of f and Lemma 9.Source: E Proof of Theorem 2 · pp. 41–42
- The proof applies Lemma 6 to terms (2) and (5), and uses optimality bounds for terms (4) and (7).The remaining terms (1) and (6) are bounded using Lemma 14's continuity result.Source: E Proof of Theorem 2 · p. 42
E.1 Proof of Lemma 14
- Lemma 14 bounds changes in Lα when v or w changes, assuming Assumptions 4, 5, and 6.The displayed bounds use L1 distances under the initial-state and offline-data distributions, with coefficients including αBf′,α and Be,α.Source: E Proof of Theorem 2 · p. 42, §E.1 · p. 43
F Proof of Lemmas in Theorem 3
The appendix proof treats cases for the maximizing density ratio and invokes Bellman-flow constraints; it also gives a variational expression for policy distance.
F.1 Proof of Lemma 1
- The KKT analysis separates cases where some action has an interior density-ratio value from cases where all values are endpoints.For the endpoint case, the proof introduces Lemma 15 before bounding the value-function difference.Source: §F.1 · p. 44
F.2 Proof of Lemma 15
- The Lemma 15 proof uses that both the candidate occupancy and the dataset visitation distribution satisfy Bellman-flow constraints.The latter follows from Assumption 11, which identifies dD as the discounted visitation distribution of πD.Source: §F.2 · p. 45
G.1 Proof of Lemma 2
- Policy L1 distance at a state equals the maximum expectation gap over action functions bounded in sup norm by 1.This is the variational form of total variation used in the proof of Lemma 2.Source: §G.1 · p. 46
G.2 Proof of Theorem 4
Theorem 4's proof conditions on an event and combines concentration with a lemma relating an estimated occupancy to the optimal one. A separate proof establishes that lemma.
G.2 Proof of Theorem 4
- The proof applies Hoeffding's inequality to bounded density-ratio and test-function terms, uniformly over π and h.The passage specifies 0 ≤ bw(s, a) ≤ Bw,α and |h(s, a)| ≤ 1.Source: §G.2 · p. 46
- Conditioned on event E, the proof uses concentration and Lemma 16 to bound the optimal-policy expectation of a policy-distance quantity.Lemma 16 states that the estimated discounted occupancy bd′ is close to d*α on E.Source: §G.2 · p. 47
G.3 Proof of Lemma 16
- The proof is described as similar to Lemma 9; the fragments say it proves the second part, then turns to the first part and begins discussing term (1).Source: §G.3 · pp. 48–49
H Proof of Corollary 6
The corollary proof invokes Lemma 7 and substitutes the unregularized optimal value function into an inequality. Its accompanying lemma uses an initial-state coverage bound.
H Proof of Corollary 6
- The proof identifies v*0 as the unregularized MDP's optimal value function and d*0 as the optimal policy's discounted state visitation distribution.It then invokes Lemma 12 and uses that the optimal value function implies −ev*0(s)(s, a) ≥ 0.Source: H Proof of Corollary 6 · p. 50
H.1 Proof of Lemma 11
- Lemma 11's proof combines dD(s) ≥ (1 − γ)µ0(s) with dπ(s) ≤ Berg,2µ0(s) for every state and policy.The stated coverage inequality is used to relate policy visitation to the initial-state distribution.Source: §H.1 · p. 51