Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation

Yaqi Duan; Mengdi Wang

Source-linked AI summary

Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation

Yaqi Duan, Mengdi Wang

arXiv:2002.09516v1Feb 21, 2020cs.LGmath.STstat.ML

TL;DR

The paper asks how accurately off-policy evaluation can estimate a target policy’s cumulative value from logged data under linear function approximation and unknown behavior policies. It analyzes a regression-based fitted Q iteration method, showing its equivalence to plug-in estimation and deriving upper and lower statistical guarantees. The method nearly attains the minimax limit, with error governed by a function-class-restricted χ2-divergence, and it yields a computable confidence bound.

Problem
Off-policy evaluation must estimate a new target policy’s cumulative value from logged history generated by unknown behavior policies.
Method
The paper analyzes regression-based fitted Q iteration, which is equivalent to a model-based plug-in estimator of the transition operator and does not require knowing the behavior policy.
Results
The regression-based evaluator nearly achieves the minimax lower bound, with error characterized by a function-class-restricted χ2-divergence between target-policy occupancy and data distributions.
Takeaways & Limitations
The restricted χ2-divergence identifies the distributional mismatch relevant to the function class, while the algorithm provides a computable confidence bound for policy evaluation.
Takeaways & Limitations
The theory assumes the target-policy transition operator preserves the chosen function class, including the reward function.

Abstract

from arXiv · show

This paper studies the statistical theory of batch data reinforcement learning with function approximation. Consider the off-policy evaluation problem, which is to estimate the cumulative value of a new target policy from logged history generated by unknown behavioral policies. We study a regression-based fitted Q iteration method, and show that it is equivalent to a model-based method that estimates a conditional mean embedding of the transition operator. We prove that this method is information-theoretically optimal and has nearly minimal estimation error. In particular, by leveraging contraction property of Markov processes and martingale concentration, we establish a finite-sample instance-dependent error upper bound and a nearly-matching minimax lower bound. The policy evaluation error depends sharply on a restricted $χ^2$-divergence over the function class between the long-term distribution of the target policy and the distribution of past data. This restricted $χ^2$-divergence is both instance-dependent and function-class-dependent. It characterizes the statistical limit of off-policy evaluation. Further, we provide an easily computable confidence bound for the policy evaluator, which may be useful for optimistic planning and safe policy improvement.

1. Introduction

The paper develops and analyzes regression-based off-policy evaluation with linear function approximation, establishing nearly minimax-optimal error guarantees and a computable confidence bound. Its error depends on a function-class-restricted χ2-divergence that captures relevant distributional mismatch.

The paper studies off-policy evaluation: estimating a new policy’s cumulative value from logged history when new experiments are costly.
The restricted χ2-divergence measures distributional mismatch relevant to the function class and determines the theoretical limits of off-policy evaluation.With function approximation, it can be smaller than the worst-case density ratio used in importance sampling, and it can be estimated as a finite-matrix condition number.
The regression-based evaluator unifies fitted Q iteration and plug-in estimation without requiring knowledge or estimation of the behavior policy.For linear models, it is computable using simple matrix-vector operations.
N = Ω(dH3) prevents the curse of horizon, because contraction analysis makes multi-step estimation error accumulate linearly rather than exponentially.
The minimax lower bound nearly matches the upper bound, establishing that regression-based fitted Q iteration is nearly statistically efficient.
The paper also provides a data-dependent confidence bound that can be computed as a byproduct of fitted Q iteration.

2. Problem and Model

The problem is to estimate a target policy’s finite-horizon value from fixed empirical transitions generated by unknown behavior policies. The model uses an MDP with a target-policy transition operator and a function class, chiefly a linear span of d features, that contains the relevant value functions.

The MDP evolves from state-action pairs to random next states and bounded rewards, while a policy selects actions conditional on the current state.
The objective is to estimate the expected cumulative reward of a target policy over an H-horizon episode from a fixed transition dataset.
The target-policy Q-functions describe expected future rewards under the target policy and unknown transition model.
The conditional transition operator Pπ maps functions through the environment transition followed by the target policy’s next-action distribution.
The function class Q is closed under Pπ and contains the reward function, while the analysis focuses mainly on a d-dimensional linear span of feature functions.
The main analysis assumes transition data come from multiple independent episodes, although the confidence-bound setting also permits a long adaptive single path.

3. Regression-Based Off-Policy Evaluation

The paper evaluates a target policy with regression-based fitted Q iteration under linear function approximation. The estimator is equivalent to a model-based plug-in method that embeds the conditional transition operator and admits simple finite-dimensional computations.

Function approximation: The method assumes Q-functions lie in a known d-dimensional linear function class and does not require knowing the behavior policy.The approach uses a basis of feature functions and operates directly on logged transitions.
Fitted Q-iteration: FQI recursively estimates target-policy Q-functions from batch data through supervised regression.The procedure initializes the terminal Q-function and works backward across the horizon using regularized regression.
Model-based interpretation: FQI is exactly equivalent to a model-based plug-in estimator that estimates a conditional transition operator and inserts it into the Bellman recursion.The equivalence holds for linear Q and the specified regularization, while the estimated operator is a projection onto the function class.
Model-based interpretation: With d-dimensional features, the conditional transition operator is represented by a d × d matrix mean embedding, enabling vector-matrix implementation.The transition operator acts on linear functions through the feature map and estimated matrix.
Connections: The estimator is related to importance-sampling approaches, reducing to marginalized importance sampling in the tabular case.Its estimated weights can be viewed as importance-sampling weights, and the paper also connects it to DualDICE.

4. Finite-Sample Error Bound

The paper derives an instance-dependent finite-sample error bound for linear-function-approximation OPE. The bound is governed by function-class-restricted distributional mismatch, while contraction controls horizon dependence and martingale concentration controls sampling error.

General upper bound: Theorem 2 gives a high-probability, instance-dependent policy-evaluation error upper bound under assumptions on feature covariance and regularization.The result requires sufficiently large N and bounds involving κ1, κ2, C1, d, H, and the minimum eigenvalue of Σ.
General upper bound: The upper bound improves under nonnegative feature-covariance geometry or time-inhomogeneous MDPs.These conditions are stated as alternatives under which the paper obtains a sharper bound.
Distributional mismatch: The error can be expressed through a Q-restricted χ2-divergence measuring mismatch between target-policy occupancy and the data distribution.In the tabular case, the bound connects directly to Pearson χ2-divergence between behavior and target state-action distributions.
Proof strategy: The analysis decomposes value error into a first-order sampling term, a high-order bias-inducing term, and a regularization term.The first-order term is handled with martingale concentration, while the high-order term is controlled using Markov-process contraction.
Proof strategy: Contraction prevents exponential growth in horizon when N is sufficiently large, with the high-order term bounded as |E2| ≲ dH^3.5/N when N ≳ dH^3.The argument uses concentration bounds for estimated transition and covariance operators.

5. Minimax Lower Bound

The paper proves a minimax lower bound for linear-function-approximation OPE that nearly matches its finite-sample upper bound. The construction uses nearby transition models with separated policy values, showing that restricted distributional mismatch controls statistical difficulty.

Lower-bound result: Theorem 3 establishes a minimax lower bound for OPE with linear function approximators that nearly matches Theorem 2’s upper bound.The lower bound applies to arbitrary estimators, including biased and unbiased procedures.
Interpretation: The Q-χ2-divergence term determines the statistical complexity of OPE within the chosen function class.This links the lower bound to the same distributional-mismatch quantity appearing in the upper bound.
Example: In the two-absorbing-state example, z measures how distinguishable the high- and low-value states are under behavior-policy data.When z ≈ 1/2, the states cannot be distinguished from the logged data and the lower bound becomes unbounded.
Proof construction: The lower bound is constructed from similar MDP instances whose target-policy values differ by a nontrivial gap.The proof perturbs the transition model while keeping the resulting instances difficult to distinguish from data.
Proof outline: The proof reduces estimation to distinguishing nearby transition models through likelihood-ratio testing and concentration arguments.The perturbation changes transitions toward high- and low-value state sets while preserving the required construction constraints.

6. A Computable Confidence Bound

The paper provides a computable high-probability confidence bound for policy evaluation under weak data-generation assumptions. The bound can be obtained from quantities already calculated by the fitted Q-iteration procedure.

Data assumptions: The confidence analysis allows transition samples collected in time order, including data from a single path under a nonstationary adaptive policy.This assumption is weaker than requiring independent episodes.
Confidence guarantee: Under these assumptions, the paper gives an analytically computable high-probability bound on |vπ − bvπ|.The theorem assumes bounded feature norms and guarantees the result with probability at least 1 − δ.
Computation: The confidence bound is available as a byproduct of FQI-OPE because the required empirical quantities are computed during its iterations.The regularization parameter λ can be tuned to obtain a smaller confidence bound.

7. Extension to Infinite-Horizon Discounted MDP

The paper extends its off-policy evaluation analysis to infinite-horizon discounted MDPs, retaining minimax-optimal error guarantees under stated assumptions.

The extension considers infinite-horizon discounted MDPs with discount factor γ ∈(0, 1).
The analysis assumes episodic data collection as in Assumption 2.
The paper concludes that the discounted-MDP OPE error bound is minimax-optimal, with the proof analogous to the finite-horizon case.
Theorem 5 provides a finite-sample upper bound under feature, sample-size, and horizon conditions.
Theorem 5 also establishes a minimax lower bound for suitable MDP instances and behavior policies.

8. Summary

The paper characterizes statistical limits of linear-function-approximation OPE and shows that its regression-based FQI method nearly attains them.

The minimax lower bound depends on a function-class-restricted χ2-divergence between data and the target policy.
Regression-based FQI is equivalent to a plug-in estimator and nearly achieves the minimax lower bound.
The algorithm also provides a computable confidence bound as a byproduct.

Appendices

The appendices formulate FQI in a linear function class and connect its parameterization to the estimated transition and reward operators.

FQI replaces the function g with the linear form φ(·)⊤w to obtain an estimated Q function.
The optimal parameter satisfies w∗= bR + c M π bwπ under the stated definitions.
The linearity result can also apply to an infinite-dimensional linear space Q, although finite-dimensional Q is used for notational simplicity.

A.2. Relations to Other Methods

The appendix relates FQI-OPE to importance sampling, DualDICE, and contraction-based error analysis, while decomposing and controlling its estimation error.

Relations to importance sampling: FQI-OPE can be interpreted as importance sampling with estimated importance weights, and reduces to MIS in the tabular special case.
Relation to DualDICE: For the chosen function classes, a version of DualDICE produces the same estimator as FQI-OPE.
Contraction analysis: The contraction property implies that the relevant Markov operator is nonexpansive under a suitable matrix norm.
Contraction analysis: The target policy induces a Markov process whose feature embedding is represented by M π.
Error decomposition: The policy evaluation error is decomposed into first-order, high-order, and ridge-bias terms.
Error control: Martingale concentration controls the first-order term under a bounded feature condition.
Error control: With N ≥20κ1(2 + κ2)2 ln(8dH/δ)C1dH3 and a corresponding ridge constraint, the high-order analysis obtains its stated event with probability at least 1 −δ.
Error control: The contraction-based deterministic bound does not grow exponentially with the horizon H.

B.7. Proof of Corollary 1

The proof establishes the tabular corollary by applying the general upper bound and constructing a perturbed transition model for a minimax lower bound. Likelihood-ratio concentration and a value gap show that no estimator can avoid a large error on at least one indistinguishable instance.

Upper bound: In the tabular case, indicator features make Σ diagonal and ensure the nonnegativity condition needed to apply Theorem 2’s upper bound.The proof identifies φ(s, a) with the state-action indicator vector.
Lower-bound construction: The lower-bound construction perturbs transition probabilities by a feature-dependent term while preserving membership in the model class.The perturbation is parameterized by x and is kept sufficiently small to remain hard to distinguish from the original model.
Lower bound: If the two models’ values differ sufficiently, one estimator cannot simultaneously achieve the prescribed accuracy under both models.The contradiction argument uses the value gap and likelihood-ratio events to force a large estimation error on at least one instance.
Concentration: The likelihood-ratio analysis treats its centered increments as martingale differences and applies Freedman’s inequality under a bounded feature-norm condition.The proof separately controls the linear and quadratic terms in the log-likelihood ratio.
Conclusion: The constructed value gap is maximized by choosing x through an optimization problem, and the resulting argument yields the minimax lower bound in (18).The proof combines the perturbation, likelihood-ratio concentration, and value-gap lemmas.

D. Proof of Data-Dependent Confidence Bound

The confidence-bound proof controls data-dependent martingale quantities through truncation, Freedman concentration, and induction. These bounds are then combined across time steps and estimator components to establish the theorem’s high-probability guarantee.

Martingale control: The proof introduces truncated martingales to control the growth of the data-dependent quantity Θh,n.Appropriately chosen truncation thresholds ensure the truncated process remains bounded with high probability.
Concentration: Freedman’s inequality yields simultaneous high-probability bounds for the truncated process across all sample indices.Lemma D.4 provides the concentration event used in the subsequent induction.
Induction: An induction argument shows Θh,n ≤ ϑh,n for every n under the concentration event.The inductive step combines the recursive control from Lemma D.2 with the event guaranteed by Lemma D.4.
Theorem completion: A union bound extends the result across all time steps h and completes the proof of Theorem 4.The theorem follows after substituting the intermediate bounds into the target inequality.
Discounted setting: For the discounted setting, the proof decomposes the value error into martingale, model, and higher-order terms and combines their concentration bounds.The decomposition uses the Bellman equation and a transition-operator representation of the value gap.