PaperlayerView exact revision on arXiv

Source-linked AI summary

Batch Policy Learning under Constraints

Hoang M. Le, Cameron Voloshin, Yisong Yue

arXiv:1903.08738v1cs.LGcs.AImath.OCstat.ML

TL;DR

The paper studies how to learn sequential policies from abundant, non-optimal off-policy data while satisfying multiple competing constraints. It develops a reduction-based batch policy-learning framework, instantiates it with learning and evaluation subroutines, and provides guarantees for the objective and constraints. The method achieves strong empirical results, while its FQE evaluator performs especially well in a challenging high-dimensional setting.

  • Problem

    The paper addresses learning sequential decision-making policies from pre-collected non-optimal behavior data while providing provable guarantees for multiple constraint-satisfaction requirements.

  • Method

    The framework uses a flexible meta-algorithm with batch reinforcement learning and online-learning subroutines, plus FQE for off-policy evaluation.

  • Results

    The approach provides guarantees for the primary objective and constraints and achieves strong empirical results across navigation and high-dimensional racing domains.

  • Takeaways & Limitations

    Constrained batch policy learning can accommodate general constraints and may support real-world domains with abundant behavior data.

  • Takeaways & Limitations

    The paper leaves noisy-update extensions for very large-scale or high-dimensional problems and further comparison of FQE’s bias-variance characteristics for future work.

Abstract

from arXiv · show

When learning policies for real-world domains, two important questions arise: (i) how to efficiently use pre-collected off-policy, non-optimal behavior data; and (ii) how to mediate among different competing objectives and constraints. We thus study the problem of batch policy learning under multiple constraints, and offer a systematic solution. We first propose a flexible meta-algorithm that admits any batch reinforcement learning and online learning procedure as subroutines. We then present a specific algorithmic instantiation and provide performance guarantees for the main objective and all constraints. To certify constraint satisfaction, we propose a new and simple method for off-policy policy evaluation (OPE) and derive PAC-style bounds. Our algorithm achieves strong empirical results in different domains, including in a challenging problem of simulated car driving subject to multiple constraints such as lane keeping and smooth driving. We also show experimentally that our OPE method outperforms other popular OPE techniques on a standalone basis, especially in a high-dimensional setting.

1. Introduction

The paper formulates batch policy learning under multiple constraints to use abundant off-policy behavior data while balancing competing objectives. It develops a reduction-based framework with end-to-end guarantees, improved sample complexity, and empirical validation in navigation and racing domains.

  • Motivation: Batch policy learning under multiple constraints addresses how to learn from abundant, non-optimal off-policy behavior data with provable constraint-satisfaction guarantees.The setting complements online reinforcement learning focused on exploration and imitation learning focused on expert demonstrations.
  • Contributions: The framework uses multi-level reductions to batch reinforcement learning and online learning, transferring subroutine guarantees to the original constrained policy-learning problem.The approach accommodates different batch RL and online-learning subroutines.
  • Contributions: The refined analysis improves a previously known nonlinear-function-approximation sample-complexity bound from O(n4) to O(n2).This improvement is obtained by leveraging batch RL as a subroutine.
  • Contributions: A simple off-policy policy-evaluation technique is proposed to evaluate and verify constraint satisfaction within the main algorithm.The technique is reported as competitive with other off-policy evaluation methods.
  • Experiments: Experiments cover a navigation domain with safety constraints and a high-dimensional racing-car domain with smooth-driving and lane-keeping constraints.These settings validate the algorithm and analysis.

2. Problem Formulation

The paper defines a discounted infinite-horizon constrained MDP and seeks a policy minimizing primary cost while satisfying multiple expected-cost limits. It connects this formulation to counterfactual, safe, multi-objective, and regularized policy learning.

  • 2. Problem Formulation: The constrained MDP uses bounded primary and constraint cost functions, unknown transition dynamics, a discount factor, and an initial-state distribution.Constraint costs are represented jointly as a vector-valued function.
  • 2. Problem Formulation: Policy values are defined as discounted expected cumulative primary and constraint costs, then averaged over the initial-state distribution.The constraint values form a vector with one component per constraint.
  • 2.1. Batch Policy Learning under Constraints: Given a fixed dataset of transitions from historical behavioral policies, the objective is to minimize primary cost while satisfying m constraint thresholds.The dataset may combine behavior from multiple policies.
  • 2.2. Examples of Policy Learning with Constraints: The framework supports counterfactual and safe policy learning when new cost objectives or safety costs can be computed from historical data.Chance constraints can express the probability of entering an error-state set.
  • 2.2. Examples of Policy Learning with Constraints: Multiple behavioral objectives, such as fast driving, smoothness, and lane keeping, can be represented directly as constraints rather than a single scalar objective.This formulation covers objectives that are not easily reducible to one cost function.
  • 2.3. Equivalence between Constraint Satisfaction and Regularization: Many regularized policy-learning methods can be cast as constrained optimization, including entropy regularization, smooth imitation, expert-demonstration regularization, and conservative improvement.Each example uses a constraint measuring the corresponding regularization quantity.
  • 2.3. Equivalence between Constraint Satisfaction and Regularization: The regularization–constraint equivalence follows from Lagrangian duality under convexity, Slater’s condition, and a non-removable constraint.The proposition states correspondence between positive regularization weights and constraint thresholds.

3. Proposed Approach

The proposed approach casts constrained batch policy learning as a primal-dual process, using policy best responses and no-regret updates over constraint weights. Its concrete instantiation combines FQI for policy learning with FQE for off-policy evaluation.

  • Meta-algorithm: Convexifying the policy class permits stochastic mixtures of policies while preserving first-moment statistics such as expected costs.The paper therefore identifies the policy class with its convex hull for analysis.
  • Meta-algorithm: The Lagrangian combines primary cost with constraint violations weighted by a nonnegative multiplier vector.This yields an equivalent min-max formulation under strong duality assumptions.
  • Meta-algorithm: At each round, a policy best response minimizes the weighted cost c + λ⊤g, while a no-regret online learner updates the constraint weights.The mixed policy is the uniform distribution over previous policies.
  • Meta-algorithm: The meta-algorithm terminates when the estimated primal-dual gap is below threshold ω.With exact best responses and exact gap evaluation, convergence depends on the online learner’s regret.
  • Policy learning: FQI is a model-free off-policy method that repeatedly reduces action-value approximation to supervised regression and selects actions minimizing the final learned Q-function.The paper notes applications of FQI in several empirical domains.
  • Off-policy evaluation: Off-policy evaluation is required to estimate both objective and constraint values from data generated by historical policies.The paper contrasts importance weighting, direct methods, and doubly robust techniques before introducing FQE.
  • Off-policy evaluation: FQE is a model-free function-approximation method for off-policy evaluation that iteratively updates Q-functions without the FQI minimization operator.It can also serve as a direct-method component in doubly robust evaluation.

4. Theoretical Analysis

The analysis establishes convergence and generalization guarantees for the primal-dual algorithm and its FQE/FQI subroutines, under distribution-shift and function-class assumptions. These results connect subroutine errors to near-optimal objectives and approximate constraint satisfaction.

  • Convergence of Algorithm 2: Algorithm 2’s empirical duality gap converges at a rate depending on the dual-radius B, maximal constraint value G, and number of constraints m.The stated rate is O(B^2/ω^2) for primal-dual gap ω.
  • Convergence of Algorithm 2: The convergence proof extends the no-regret analysis of the exponentiated-gradient procedure to the main primal-dual algorithm.The analysis leverages the no-regret property of EG.
  • FQE and FQI guarantees: FQE and FQI generalization bounds depend on function-class capacity, Bellman approximation error, and concentration of future state-action distributions.Pseudo-dimension measures nonlinear function-class capacity, while the concentration coefficient controls distribution shift from the data-generating distribution.
  • Assumptions: Finite concentration coefficients hold for finite MDPs and some infinite-state MDPs with bounded transition density, while sufficient exploration can bound them in a stochastic MDP.An example gives β_µ ≤ LM when state marginals and behavior-policy action probabilities satisfy the stated bounds.
  • Assumptions: Without sufficient data diversity, FQE and FQI may require exponentially many samples, as illustrated by the combination-lock MDP.The analysis also assumes a function class closed under the Bellman and policy-evaluation operators.
  • End-to-end guarantee: The end-to-end guarantee states that Algorithm 2 can approach the optimal main-objective performance while approximately satisfying every constraint with high probability.This requires sufficiently large B and K and sufficiently small ϵ.

5. Empirical Analysis

Experiments evaluate the method in FrozenLake and high-dimensional CarRacing, testing convergence, objective performance, constraint satisfaction, and off-policy evaluation. The returned policies improve over behavior data while meeting the reported constraints, and FQE is especially strong in CarRacing.

  • Experimental setup: The experiments use FrozenLake with a safety constraint and CarRacing with smooth-driving and lane-centering constraints.These domains test both a simple navigation setting and a high-dimensional racing problem.
  • FrozenLake: In FrozenLake, the empirical primal-dual gap quickly decreases monotonically toward zero, while the safety constraint remains satisfied.The main-objective cost converges smoothly to the value achieved by an unconstrained DQN baseline.
  • FrozenLake: The FrozenLake returned policy significantly outperforms the data-gathering policy πD on both main and safety costs.The safety threshold is τ = 0.1, interpreted as an acceptable failure probability.
  • CarRacing: The CarRacing dataset contains approximately 1,500 trajectories and 94,000 transition tuples from randomized DDQN behavior in a 96×96×3 pixel state space.The action space has 12 discretized steering, gas, and brake combinations.
  • CarRacing: In CarRacing, the returned mixture policy achieves low main-objective cost comparable to unconstrained online RL while eventually satisfying both constraints.The policy initially violates the braking constraint, then satisfies both constraints under the appropriate λ tradeoff.
  • Baselines: Regularized LSPI obtains good main-objective performance but fails to achieve acceptable constraint satisfaction, whereas the proposed approach avoids brute-force tuning across multiple constraints.One-shot regularized learning is sensitive to step changes in λ when objectives conflict.
  • Off-policy evaluation: FQE is competitive with DR and WDR in FrozenLake and significantly outperforms other OPE methods in high-dimensional CarRacing.The comparison uses random dataset subsamples from 10% to 100% of transitions across 30 trials.

6. Other Related Work

The paper relates constrained batch policy learning to constrained MDPs and multi-objective reinforcement learning. It positions its framework as a systematic alternative for off-policy, multi-constraint settings.

  • Constrained MDPs: Classical constrained MDP approaches rely on a fully specified model and tractable state dimensions, limiting their direct applicability in the paper’s setting.The related-work discussion contrasts these requirements with learning when the model is not initially specified.
  • Multi-objective reinforcement learning: Multi-objective reinforcement learning commonly approximates Pareto frontiers of competing objectives.The paper distinguishes this focus from its constrained policy-learning formulation.
  • Multi-objective reinforcement learning: The proposed approach offers a systematic paradigm for multi-objective reinforcement learning in both batch and online settings instead of relying on heuristic reward scalarization.The connection is stated for the broader MORL setting.

7. Discussion

The discussion frames the method as a general constrained-learning approach with empirical promise, while connecting regularization and imitation objectives to the formulation. It also identifies scalability and OPE bias-variance analysis as open directions.

  • Discussion: The formulation accommodates general constraint definitions and provides guarantees for both the main objective and constraint satisfaction.The authors describe the empirical results as promising for domains with abundant behavior data.
  • Open directions: The authors leave noisy updates for very large or high-dimensional problems and comparative bias-variance analysis of FQE for future work.These are identified as theoretical and practical extensions rather than established results.
  • Connections to related formulations: Entropy regularization, imitation constraints, conservative policy improvement, and regularized RL objectives can be represented within the constrained formulation.The discussion gives explicit mappings from several regularized or imitation objectives to constraints or costs.
  • Connections to related formulations: Regularized RL with imperfect demonstrations can be expressed using a standard RL objective plus imitation and n-step-return constraints.The paper writes the imitation constraint using a Q-function margin involving expert actions and divergence loss.
  • Regularization and constraints: Under strong duality, constrained and regularized policy-learning formulations can share an optimal solution for an appropriate regularization parameter.The argument uses Slater’s condition and the Lagrangian dual.
  • Optimization analysis: The algorithm’s termination follows from the online procedure’s no-regret bound, with iteration complexity determined by the resulting regret scaling.The empirical primal-dual gap becomes at most ω once the sublinear regret term is sufficiently small.

B.2. Empirical Convergence Analysis of Main Algorithm - Proof of Theorem 4.1

The empirical analysis bounds the primal-dual gap of the main algorithm using normalized exponentiated-gradient regret and shows convergence after a finite number of iterations.

  • Empirical convergence: Normalized exponentiated gradient supplies a regret bound for the online learning subroutine over T iterations.The bound depends on the dual-variable radius B, maximal constraint value G, and iteration count T.
  • Empirical convergence: The online-learning inequalities imply that the empirical primal-dual gap is at most 2ω_T.The argument combines upper and lower bounds on the empirical Lagrangian evaluated at the averaged policy and averaged dual variable.
  • Empirical convergence: The algorithm converges after 16B^2G^2 log(m+1) iterations under the stated rate calculation.The iteration requirement grows with the squared dual radius and constraint bound, and logarithmically with the number of constraints.

C. End-to-end Generalization Analysis of Main Algorithm

The end-to-end analysis lifts empirical primal-dual guarantees through FQE errors to obtain probabilistic bounds on the learned policy’s objective and constraint satisfaction.

  • Constraint satisfaction: The proof establishes approximate satisfaction of all constraints for the returned policy under feasibility of the empirical constraints.The argument uses the stopping condition and selects a dual coordinate corresponding to the largest constraint violation.
  • Generalization guarantee: The theorem combines empirical bounds with FQE and FQI generalization results to complete the end-to-end guarantee.The analysis explicitly lifts empirical error to generalization bounds for both the objective and constraints.
  • Constraint satisfaction: FQE estimates each constraint row within ±ϵ_FQE with probability at least 1−δ.The bound applies simultaneously row-wise across all m constraints.
  • Generalization guarantee: The returned mixture policy uniformly samples one of the T iterates, enabling the empirical Lagrangian bound to transfer to its average performance.The resulting bound compares the estimated Lagrangian with the optimal policy and includes FQI and FQE errors.
  • Main-objective guarantee: The learned policy’s objective satisfies C(bπ) ≤ C(π*) + ω + ϵ_FQI + (2+B)ϵ_FQE.This combines the empirical primal-dual guarantee with generalization errors from FQI and FQE.

D. Preliminaries to Analysis of Fitted Q Evaluation (FQE) and Fitted Q Iteration (FQI)

The preliminaries define the operators, function-class complexity, distribution-shift assumptions, and concentration quantities used to analyze FQE and FQI under batch data.

  • Analytical setup: FQE and FQI are analyzed in weighted ℓ2 norms using pseudo-dimension as the capacity measure for nonlinear function classes.The setup treats pseudo-dimension as a regression analogue of VC dimension.
  • Bellman operators: The Bellman evaluation operator Tπ has Qπ as a fixed point, while the optimality operator defines the corresponding control problem.The paper uses cost minimization notation, with C(π) denoting long-term accumulated cost.
  • Function approximation: FQE and FQI repeatedly project Bellman updates onto a chosen function class F, making approximation quality central to their analysis.The relevant approximation quantities are inherent Bellman and Bellman evaluation errors.
  • Distribution shift: The concentration coefficient measures distribution shift between future state-action distributions induced by learned policies and the behavior-data distribution µ.The analysis assumes this shift is sufficiently controlled over future time steps.
  • Distribution shift: The combination-lock MDP demonstrates that violating the concentration assumption can require an exponential number of trajectories for learning or evaluation.With behavior probability π_D(L|x) ≥ ν, the coefficient β_µ can nevertheless become arbitrarily large.
  • FQE guarantees: The standalone FQE guarantees are stated under both Bellman realizability and general settings, with high-probability bounds after K iterations.The realizable case assumes Tπf ∈ F, while the general case introduces an additional approximation term.

E.1. Error bound for single iteration - Bellman realizable case

The single-iteration analysis views FQE updates as supervised regression and derives improved finite-sample rates for general bounded nonlinear function classes, while tracking approximation error.

  • Bellman realizable case: Under Bellman evaluation realizability, the function class contains every Bellman evaluation update Tπf.This removes the inherent Bellman evaluation error from the single-iteration analysis.
  • Regression reduction: FQE constructs regression targets y_i = c_i + γQ_{k−1}(x′_i,π(x′_i)) and fits Q_k ∈ F by minimizing squared error.The Bellman evaluation update is the population regression function for these targets.
  • Bellman non-realizable case: In the non-realizable case, the error bound includes the worst-case inherent Bellman evaluation error d_F^π.This term arises because TπQ_{k−1} need not belong to F.
  • Bellman non-realizable case: Choosing a richer function class can reduce inherent Bellman error but increases sample requirements through a larger pseudo-dimension.The paper frames this as a bias-variance trade-off in function-class selection.
  • Multi-iteration guarantee: The final FQE guarantees propagate single-iteration errors across K iterations and account for distribution shift from µ to the evaluation distribution ρ.The analysis bounds the estimated value by first controlling Q-function error under ρ.

F.4. Finite-sample guarantees for Fitted Q Iteration

The FQI analysis gives finite-sample guarantees under Bellman-realizability and non-realizability settings, while the framework can instantiate batch learning with LSPI and online gradient updates.

  • Finite-sample guarantees: For general function approximation, the analysis bounds FQI error using inherent Bellman error dF and distribution-shift assumptions.The concentration coefficient measures worst-case distribution shift, while dF captures Bellman-operator approximation error.
  • Finite-sample guarantees: Compared with prior fitted value iteration analysis, the FQI error bound contains an additional factor 2 multiplying dF.This is an explicit comparison to the analysis of Munos and Szepesvári (2008).
  • Finite-sample guarantees: Under Bellman evaluation realizability, FQI provides a high-probability guarantee after K iterations for the greedy policy induced by QK.The guarantee applies under Assumptions 3 and 5 for any ϵ > 0 and δ ∈ (0, 1).
  • Algorithmic instantiation: The meta-algorithm can be instantiated with Online Gradient Descent and LSPI, using linear value functions over a k-dimensional feature map.The OGD update projects λ onto an ℓ2 ball of radius B, while LSPI supplies policy-learning updates from the batch dataset.
  • Algorithmic instantiation: The LSPI-based constrained learner evaluates main and constraint costs for each policy and updates λ using the estimated constraint violation.The procedure can return a policy greedy with respect to the learned weight vector when the policy-value range is sufficiently small.

H.2. Additional Discussion for the Car Racing Experiment

In the car-racing experiment, one-shot regularization often fails to satisfy both constraints, whereas the returned mixture policies usually satisfy constraints and tend to improve the main objective over the data-generating policy. The standalone OPE comparison attributes competing model-based methods’ weakness to inaccurate long-horizon dynamics prediction.

  • Regularized policy learning and grid-search: About 10% of regularized policies satisfy both car-racing constraints, while none of the regularized LSPI policies does.Regularized LSPI and FQI can achieve low main-objective cost, but constraint costs are sensitive to the regularization step.
  • Mixture policy and de-randomization: Individual policies from the learned mixture almost always satisfy constraints and tend to outperform πD on the main objective cost.The comparison uses the performance range of individual mixture policies against the stochastic behavior of the data-generating policy.
  • Off-policy evaluation standalone comparison: In the deterministic, long-horizon car domain, Per-Decision Importance Sampling typically evaluates the policy as 0.The passage contrasts this setting with the stochastic behavior and evaluation policies usually required by inverse propensity methods.
  • Off-policy evaluation standalone comparison: The dynamics model compresses 96 × 96 × 3 pixel states to 32 dimensions and uses an LSTM to model latent transition dynamics.The model is trained on a separate dataset from the evaluation dataset D.
  • Off-policy evaluation standalone comparison: Model-based DR and WDR estimates are limited because the learned dynamics model cannot accurately predict states several steps into this long-horizon, high-dimensional domain.The authors identify thorough benchmarking of OPE methods in high-dimensional domains as future work.
Loading 1903.08738v1…