Source-linked AI summary
Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
Nathan Kallus, Masatoshi Uehara
TL;DR
The paper asks how efficiently off-policy evaluation can estimate a target policy’s value in Markov decision processes, addressing a gap in globally efficient estimators. It derives the relevant efficiency bounds and introduces double reinforcement learning, which achieves Markov efficiency under fourth-root nuisance rates and retains double robustness. The results show that exploiting memorylessness can avoid the generally exponential horizon dependence of the non-Markov model.
Problem
The paper addresses the lack of globally efficient, nonparametric off-policy evaluation estimators for Markov decision processes despite the importance of efficient estimation with scarce data.
Method
The paper derives efficient influence functions and constructs double reinforcement learning by cross-fold estimation of q-functions and density ratios.
Results
Double reinforcement learning is globally efficient with fourth-root nuisance rates, remains consistent when only some nuisances are consistently estimated, and achieves the Markov efficiency bound, generally polynomial in horizon length T.
Takeaways & Limitations
Leveraging the Markov property can yield more efficient off-policy evaluation than estimators targeting non-Markov models, whose efficiency bound is generally exponential in horizon length.
Takeaways & Limitations
Some influence-function results rely on restrictive models, such as a known transition kernel, and the non-sample-splitting alternative requires a Donsker condition that the authors do not recommend.
Abstract
from arXiv · showhide
Off-policy evaluation (OPE) in reinforcement learning allows one to evaluate novel decision policies without needing to conduct exploration, which is often costly or otherwise infeasible. We consider for the first time the semiparametric efficiency limits of OPE in Markov decision processes (MDPs), where actions, rewards, and states are memoryless. We show existing OPE estimators may fail to be efficient in this setting. We develop a new estimator based on cross-fold estimation of $q$-functions and marginalized density ratios, which we term double reinforcement learning (DRL). We show that DRL is efficient when both components are estimated at fourth-root rates and is also doubly robust when only one component is consistent. We investigate these properties empirically and demonstrate the performance benefits due to harnessing memorylessness.
1 Introduction
The paper studies semiparametrically efficient off-policy evaluation under non-Markov and Markov decision-process models, where exploiting memorylessness can improve efficiency. It introduces double reinforcement learning, which combines cross-fold q-function and density-ratio estimation and remains efficient under weak nuisance-rate conditions.
- Motivation: The paper’s results are motivated by applications such as healthcare and education, where using available data efficiently is crucial.The stated goal is minimal asymptotic mean squared error under nonparametric models for the sequential process and behavior policy.
- Models and gap: The paper derives efficiency bounds and efficient influence functions for both non-Markov and Markov decision processes.The Markov model restricts transitions, rewards, and policies to depend on the recent state and action rather than full history.
- Models and gap: Existing work on the Markov model had been restricted to parametric finite-state-finite-action settings, with no globally efficient estimator proposed.The paper addresses this gap for more general action and state spaces and nonparametric models.
- Efficiency consequences: The Markov efficiency bound is generally polynomial in horizon length T, whereas the non-Markov bound is generally exponential.Thus, estimators targeting the non-Markov model generally suffer from the curse of horizon, while the Markov bound leverages memorylessness.
- Double reinforcement learning: The proposed Double Reinforcement Learning estimator plugs cross-fold estimates of q-functions and density ratios into the model-specific efficient influence function.It is globally efficient when nuisances converge at fourth-root rates, without Donsker or bounded-entropy restrictions, and is consistent when only some nuisances are consistently estimated.
- Problem: Off-policy evaluation estimates a target policy’s average cumulative reward from trajectories generated by a different behavior policy.The behavior policy may be known or unknown, and the setting is important when exploration is costly or data are scarce.
2 Semiparametric Inference for Off-Policy Evaluation
The paper derives semiparametric efficiency bounds and efficient influence functions for OPE under non-Markov and Markov models. Leveraging the Markov structure generally lowers the bound and changes trajectory-level nuisance functions to marginalized, state-action functions.
- Efficiency bounds and influence functions: The paper derives efficient influence functions and semiparametric efficiency bounds for OPE under NMDP and MDP models, including known-behavior-policy variants.The MDP models impose q_t=q_t(s_t,a_t) and v_t=v_t(s_t).
- Efficiency bounds and influence functions: The MDP efficient influence function replaces cumulative density ratios with marginalized density ratios and uses q- and v-functions depending only on recent state and action.This structure follows from imposing conditional independence of past and future trajectories given the intermediate state.
- Consequences of Markov structure: DRL is introduced to attain the relevant efficiency bound under mild assumptions, providing the first globally efficient OPE estimator for MDPs.Its construction uses the efficient influence functions derived for the respective models.
- Robustness: The efficient influence functions retain a doubly robust structure: control-variate terms allow consistent OPE when only one nuisance component is consistently estimated.The components include q- and v-functions or density ratios, depending on the model.
- Consequences of Markov structure: The Markov assumption generally reduces the efficiency bound, with strict reduction under a stated nonconstancy condition on density ratios and reward-plus-value terms.The comparison follows from Jensen’s inequality.
- Consequences of Markov structure: The NMDP efficiency bound is generally exponential in horizon length, whereas the MDP bound is generally polynomial, identifying the curse of horizon as model-dependent.The NMDP curse is unavoidable for estimators targeting that model, while additional structure can permit polynomial variance in MDPs.
3 Efficient Estimation Using Double Reinforcement Learning
DRL is a cross-fold estimator that combines q-functions and density ratios to achieve semiparametric efficiency under nonparametric OPE models, including MDPs. It also provides double robustness and accommodates flexible nuisance estimation under rate conditions rather than Donsker assumptions.
- Estimator properties: DRL is globally efficient under NMDP and MDP models, with the MDP result providing the first globally efficient OPE estimator for MDPs.The estimator achieves the relevant semiparametric efficiency bound under both models.
- Estimator properties: Fourth-root nuisance convergence is sufficient for DRL efficiency, while consistent estimation of only one nuisance can preserve consistency or root-n consistency under stated conditions.The results permit slow nonparametric rates and establish double robustness when one model or nuisance component is correctly specified.
- Nuisance estimation: Cross-fold sample splitting avoids Donsker conditions, allowing complex machine-learning estimators when their convergence rates satisfy the required conditions.Examples discussed include highly adaptive LASSO, high-dimensional cadlag estimators, and random forests.
- Finite-sample and implementation properties: DRL can achieve efficiency with either sample splitting or adaptive in-sample estimation under a Donsker condition, and its finite-sample leading term is controlled by the efficient variance.The MDP estimator can also retain efficiency without sample splitting under the corresponding regularity condition.
- Comparison with alternatives: Alternative estimators can be less robust or inefficient: marginalized importance sampling has a different influence function, while standard doubly robust estimators require stronger conditions in NMDPs.The asymptotic variance of DRL remains efficient regardless of the supported fourth-root-rate method used to estimate the relevant nuisance.
4 Estimating the q-function and Efficiency Under M1q, M2q
The paper estimates q-functions through conditional moment equations, using efficient methods for parametric models and sieve minimum distance for nonparametric models. These approaches support semiparametric efficiency results under both non-Markov and Markov models, with the Markov restriction simplifying the relevant functions.
- q-function formulation: q-functions are characterized by recursive definitions that can be rewritten as conditional moment equations, enabling their efficient estimation.The policy value is determined by q_0, linking q-function estimation to policy-value estimation.
- Parametric q-function models: Under parametrically restricted q-functions, efficiency bounds are derived for the q-function parameters and policy value under both M1q and M2q.The M2 formulation replaces histories with current state-action variables.
- Parametric q-function models: Efficient GMM or conditional-moment methods are preferred over backward-recursive ordinary least squares when estimating nonlinear or linear q-models.Ordinary least squares can achieve root-n consistency yet remain inefficient; optimal GMM weighting addresses this issue.
- Parametric q-function models: In the tabular setting, Effbd(M2q) = Effbd(M2), because the parametrically represented q-function model coincides with the Markov model.This equality follows from the finite state and action representation.
- Nonparametric q-function estimation: Nonparametric conditional-moment estimation can achieve the op(n^-1/4) rate required for DRL under appropriate smoothness and regularity conditions.The Fisher and L2 norms are equivalent under mild conditions, transferring the rate to the L2 norm.
- Nonparametric q-function estimation: The Fisher-norm equivalence requires conditional variances to be bounded away from zero, after which the q-function rate supplies the conditions needed by the DRL efficiency theorems.The cited efficiency results require L2 convergence of the q-function estimators.
5 Experiments
The experiments compare OPE estimators under parametric misspecification and in two OpenAI Gym tasks. DRL(M2), which leverages MDP structure, generally provides the strongest empirical performance.
- DRL(M2) nearly dominates the other estimators across simulation settings and sample sizes.It performs similarly to or better than every comparator in the reported settings.
- DRL(M2) is locally efficient when both models are correct and doubly robust in the other simulation settings.It remains consistent throughout all settings and outperforms the also-consistent IS and DRL(M1).
- In setting (2), DRL(M2) outperforms inconsistent DM when the q-model is incorrect.Consistent IS and MIS also outperform DM, but not by as much as DRL(M2).
- Large cumulative density ratios produce high RMSE for IS, MIS, and DRL(M1) under substantial behavior-target policy mismatch.Misspecifying the µ-model can make MIS significantly worse, highlighting the robustness of importance sampling with known behavior policy.
- DRL(M2) outperforms all other estimators in Cliff Walking and Mountain Car, with a stronger improvement in Cliff Walking.The comparisons use RMSE across varying evaluation dataset sizes and 1000 replications per setting.
6 Conclusions
The paper derives efficiency bounds and influence functions for OPE under NMDP and MDP models, then uses the MDP result to construct DRL. DRL is presented as the first efficient OPE estimator for MDPs, with robustness and empirical performance benefits.
- The paper establishes semiparametric efficiency bounds and efficient influence functions for OPE under NMDP and MDP models.These quantities characterize how quickly policy value can be estimated in each model.
- DRL uses the newly derived MDP efficient influence function with cross-fold nuisance estimation.The construction targets efficiency under weak and mostly agnostic conditions on nuisance estimation.
- DRL is the first efficient OPE estimator for MDPs and also has double robustness properties.The conclusion states that these properties translate into better experimental performance.
A Notation
This appendix defines the paper’s notation and abbreviations for policies, trajectories, value functions, density ratios, models, distributions, and asymptotic quantities.
- The notation distinguishes states, actions, rewards, histories, value functions, and cumulative density ratios across time.The appendix lists symbols for trajectory variables and model-specific value functions.
- M1 denotes the NMDP model, while M2 denotes the MDP model, with variants indicating behavior-policy and q-function assumptions.The model labels include M1b, M1q, M2b, and M2q.
- The appendix defines empirical expectations, dataset sizes, asymptotic variance, normal distributions, and uniform distributions.It also notes that P and E are used interchangeably for expectations in the proofs.
- The abbreviation table covers NMDP, MDP, RL, OPE, MLE, RAL, CAN, and MSE.These abbreviations refer to the paper’s decision-process, evaluation, estimation, and statistical properties.
B Proofs
The proofs section introduces definitions used to derive a semiparametric lower bound and directs readers to established references for a complete treatment.
- The proof development summarizes definitions and arguments used to derive a semiparametric lower bound.The authors place the complete rigorous treatment in the cited semiparametric inference literature.
- The section cites Bickel et al., van der Laan and Robins, van der Vaart, Tsiatis, and Vermeulen for background and accessible treatments.
B.1 Semiparametric theory
This section develops semiparametric tools for characterizing efficient estimators through gradients, tangent spaces, and influence functions.
- A pathwise differentiable target has gradients linked to influence functions of regular asymptotically linear estimators.
- The efficient influence function is the unique gradient lying in the model’s tangent space, or the projection of any gradient onto that space.
- Efficient influence functions can be derived by calculating a candidate gradient, characterizing the tangent space, and proving orthogonality to its complement.
- The efficiency bound is a local asymptotic minimax lower bound and also bounds the asymptotic variance of regular estimator sequences.
- The convolution theorem provides a second optimality characterization through a lower bound involving the variance of the efficient influence function.
B.2 Proof
The proofs establish efficient influence functions and efficiency results for the M1 and M2 models, while analyzing cross-fitted estimator terms and doubly robust behavior.
- M1 and M2 efficiency: The M1 and M2 efficient influence functions are verified by constructing tangent spaces and proving orthogonality to their orthogonal complements.
- M1 and M2 efficiency: Knowing the target policy in M1b leaves the efficiency bound unchanged because its additional tangent-space component is orthogonal to the M1 efficient influence function.
- Efficiency bounds: Jensen’s inequality yields a strict inequality when the relevant conditional variance is nonzero and the associated quantity is not conditionally constant.
- Estimator analysis: Cross-fitting is used to analyze estimator terms, including terms shown to be op(1) under sample splitting and convergence-rate assumptions.
- Efficiency results: DRL(M1) and DRL(M2) are identified as efficient estimators under their respective models.
- Estimator analysis: Additional lemmas bound selected estimator terms with high probability by quantities depending on n, C, Rmax, T, and δ.
- Robustness: The proofs use a doubly robust structure to establish consistency across cases involving the q-model and related nuisance components.
C Additional Details from Section 5.2
The experiments use Cliff Walking and Mountain Car tasks, with horizons of 400 and 200 respectively, and construct target policies using q-learning.
- Cliff Walking: Cliff Walking uses a 4 × 12 board with horizon T = 400, step reward −1, goal reward 0, and cliff penalty −100 with reset.
- Mountain Car: Mountain Car uses continuous position and velocity states, three discrete actions, and horizon T = 200 with reward −1 until reaching position 0.5.
- Target policy: The target policy is learned with standard q-learning using tabular learning for Cliff Walking and feature expansion for Mountain Car.