PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation

Claire Chen, Shuze Daniel Liu, Licheng Luo, Rohan Chandra, Nan Jiang, Shangtong Zhang

arXiv:2608.24146v1cs.LGstat.ML

TL;DR

On-policy policy evaluation can be high variance, while existing behavior policy search methods generally overlook transition uncertainty. The paper introduces minimax, double-loop gradient optimization with transition-gradient and convergence guarantees, and reports lower variance under perturbed transitions.

  • Problem

    On-policy evaluation often has high variance, and behavior policies optimized under fixed simulator transitions may remain high variance when deployment dynamics differ.

  • Method

    The method formulates behavior policy search as minimax optimization over adversarial transitions and solves it with a double-loop gradient algorithm.

  • Results

    Under a shared perturbed transition, DRVG achieves lower evaluation variance than the compared methods.

  • Takeaways & Limitations

    The framework combines variance reduction with robustness to transition shifts for policy evaluation under perturbed environments.

  • Takeaways & Limitations

    The convergence analysis assumes bounded linear features and a closed, convex feasible parameter set.

Abstract

from arXiv · show

In reinforcement learning policy evaluation, classic on-policy methods often suffer from high variance when estimating policy performance. To mitigate this issue, behavior policy search has been proposed to learn data-collecting policies tailored to reduce online evaluation variance. However, these approaches do not account for uncertainties in the transition functions. In practice, simulator transitions often differ from the real world due to modeling errors or approximation limitations. As a result, behavior policies trained in simulation may still yield high variance when deployed in real environments, leading to costly reliance on real-world evaluation samples. In this work, we propose a double-loop gradient-based algorithm for learning behavior policies that are both efficient and robust to transition uncertainty. Theoretically, we derive novel transition-variance gradient expressions and establish global convergence guarantees for the algorithm. Numerically, we demonstrate that our method is less sensitive to transition perturbations than existing approaches, providing supportive evidence for its practical utility.

1 Introduction

On-policy evaluation can have high variance, motivating behavior policy search to collect more informative data. This paper extends that approach to transition uncertainty with a robust double-loop framework and convergence guarantees.

  • On-policy Monte Carlo estimates policy value by averaging target-policy returns but often produces high evaluation variance.
  • Behavior policy search optimizes a separate data-collecting policy to reduce variance in off-policy evaluation.
  • Existing behavior policy search methods generally assume prespecified transition functions, although real dynamics can differ because of modeling errors, perturbations, or partial observability.
  • A behavior policy optimized in simulation may still yield high variance after deployment in the real environment, increasing reliance on costly real-world samples.
  • The proposed framework formulates robust behavior policy search as minimax optimization over adversarial transitions and provides transition-gradient and global convergence guarantees.

2 Related Work

Prior work reduces evaluation variance through behavior policy search or addresses simulator mismatch through robust evaluation techniques. The paper targets the gap between these directions by optimizing variance under transition uncertainty.

  • Earlier behavior policy search methods optimize data-collecting policies for lower evaluation variance but overlook transition uncertainty.
  • Offline behavior-policy formulations may rely on fixed, pre-logged transition probabilities and cannot adapt when deployment dynamics shift.
  • Robust policy-evaluation methods address simulator mismatch through estimator modification or robust model learning but do not directly target high evaluation variance.
  • Robust MDP frameworks typically optimize rewards with linear programming, whereas this work addresses variance minimization under transition uncertainty using an adversarial transition-gradient method.

3 Background

The paper studies finite-horizon MDP policy evaluation, where on-policy Monte Carlo can be replaced by off-policy data collection. Robust behavior policy search then minimizes worst-case evaluation variance under transition perturbations.

  • The setting is a finite-horizon MDP with finite state and action spaces, transition probabilities, bounded rewards, an initial-state distribution, and horizon T.
  • A policy maps states to action distributions, while behavior and transition models are parameterized by θ and ω within feasible parameter sets.
  • A trajectory consists of states, actions, rewards, and successor states across the horizon, and policy value is the expected return.
  • On-policy Monte Carlo estimates the target policy value from target-policy trajectories, but its straightforward averaging procedure can have high evaluation variance.
  • Off-policy evaluation uses trajectories collected by a behavior policy, and behavior policy search minimizes the estimator variance over behavior-policy parameters.
  • Robust behavior policy search formulates an inner adversarial transition problem and an outer behavior-policy problem to minimize worst-case evaluation variance.

4 Solving the Inner Loop

The inner loop learns transitions that maximize evaluation variance using analytical gradients, while the outer behavior-policy loop counters this adversary. The analysis covers on-transition and off-transition sampling and includes KL regularization for realism.

  • The inner loop identifies adversarial dynamics that maximize evaluation variance, with analytical gradients derived for on-transition and off-transition settings.
  • For on-transition optimization, trajectories are sampled directly from the evolving transition pω while a fixed behavior policy is used.
  • Theorem 4.1 gives a general expectation-form variance gradient applicable to any off-policy estimator and estimable unbiasedly from sampled trajectories.
  • Algorithm 1 iteratively samples trajectories, updates the transition parameter toward higher variance, and converges to a finite variance with vanishing transition gradient under stated conditions.
  • An optional KL penalty discourages large deviations from the simulator transition, balancing robustness with realistic adversarial dynamics.
  • In the off-transition case, fixed simulator data are reweighted toward target transitions, requiring a gradient expression distinct from the on-transition setting.

5 Solving the Outer Loop

The outer loop of DRVG minimizes worst-case evaluation variance by updating the behavior policy against adversarial transitions. Under linear-softmax parameterization and stated boundedness assumptions, the double-loop method has a global convergence guarantee.

  • 5 Solving the Outer Loop: DRVG solves robust behavior policy search by minimizing evaluation variance under an adversarial transition probability.The method uses gradient ascent for the transition parameter and gradient descent for the behavior-policy parameter.
  • 5 Solving the Outer Loop: The policy gradient can be estimated from trajectories sampled directly from the behavior policy π_θ.This analytical gradient expression enables the double-loop DRVG algorithm.
  • 5 Solving the Outer Loop: The inner loop returns a worst-case transition probability up to precision ϵ_i, while the outer loop applies projected gradient descent over the feasible set Θ.The precision sequence permits faster policy updates while preserving the global convergence property.
  • 5.2 Global Convergence Analysis: The method is empirically evaluated under neural-network policy parameterization, with Figure 1 comparing relative variance increases under method-specific adversarial transitions.The comparison normalizes each method’s variance increase by that of on-policy Monte Carlo in the same environment.
  • 5 Solving the Outer Loop: The theoretical analysis assumes a closed, convex feasible parameter set, bounded state features, and a linear-softmax behavior-policy parameterization.These assumptions make the variance objective convex in θ and support the smoothness properties used in the convergence analysis.
  • 5.2 Global Convergence Analysis: DRVG converges to an ϵ-optimal solution at rate O(1/√n), matching the optimal projected-gradient-descent rate in convex optimization.The error bound includes the projected-gradient term and the accumulated inner-loop precision terms.

6 Numerical Results

The numerical study evaluates robustness and variance under perturbed transitions in Garnet and inventory-management environments. DRVG shows the smallest variance increase under method-specific adversarial transitions and lower evaluation variance under a shared adversarial transition.

  • Experimental Setup: The experiments test robustness to adversarial transition perturbations and compare evaluation variance under perturbed transitions with standard on-policy Monte Carlo.Garnet MDPs and inventory management are used as evaluation environments.
  • Experimental Setup: Each method is trained from the same initial transition function, and its final behavior policy collects evaluation data.The implementation uses neural-network parameterizations for behavior policies.
  • Variance Increase under Tailored Adversarial Transitions: DRVG exhibits the smallest variance increase when each behavior policy faces its own most adversarial transition.BPG and ROS incur larger variance increases than the on-policy Monte Carlo baseline under perturbed deployment transitions.
  • Variance Comparison under Shared and Perturbed Transition: Under a shared adversarial target transition, DRVG achieves lower evaluation variance than the other methods.Figure 2 reports relative variance normalized by the on-policy Monte Carlo variance in the same environment, with standard-error bars.
  • Evaluation Design: The reported experiments compare methods under both method-specific adversarial transitions and a shared adversarial target transition.The shared target is identified using Algorithm 1 for the on-policy baseline, whereas Section 6.1 uses a separate adversarial transition for each method.

7 Conclusion

The paper presents robust behavior policy search to jointly reduce evaluation variance and address transition mismatch. Its minimax framework, transition-gradient analysis, convergence guarantees, and numerical results support robustness under transition perturbations.

  • Conclusion: The framework addresses variance reduction and transition mismatch in real-world policy evaluation.It learns behavior policies while explicitly accounting for transition uncertainty.
  • Conclusion: The method formulates behavior policy search as minimax optimization over adversarial dynamics.The behavior policy minimizes evaluation variance while an adversarial transition model maximizes it.
  • Conclusion: The paper derives transition-variance gradient expressions and proves convergence guarantees for its adversarial inner loop and double-loop algorithm.The theoretical analysis is conducted under stated regularity conditions, including smooth transitions, compact convex parameter spaces, bounded importance-sampling ratios, and bounded state features.
  • Conclusion: Numerical results demonstrate increased robustness under transition perturbations.The conclusion characterizes the combined variance-reduction and robustness objective as a step toward reliable policy evaluation under uncertainty.

A.2 Proof of Theorem 4.1

The proof of Theorem 4.1 derives the transition gradient of the variance by separating transition-dependent trajectory probabilities from transition-independent terms, then decomposing the variance objective.

  • Theorem 4.1: The theorem concerns the transition gradient of the variance for a fixed behavior policy.The result is stated as Theorem 4.1.
  • Trajectory Probability Decomposition: The proof factorizes the trajectory probability into components that depend on the transition model and components that do not.The initial-state distribution and fixed behavior policy make p(h) independent of ω.
  • Gradient Derivation: The derivation differentiates the transition-dependent trajectory-probability term with respect to ω.The proof then manipulates the resulting derivative before decomposing the variance objective.

A.3 Proof of Lemma 4.2

The proof of Lemma 4.2 establishes convergence of Algorithm 1 by verifying smoothness, bounded gradient-estimator variance, and unbiasedness-related conditions under the paper’s assumptions.

  • Convergence Statement: Algorithm 1 converges: its evaluation-variance objective approaches a finite value and its transition gradient approaches zero.This is the statement of Lemma 4.2 for a fixed behavior policy.
  • Convergence Verification: The proof concludes Algorithm 1 converges after verifying the three conditions required by the cited stochastic-approximation proposition.Unbiased gradient estimates satisfy additional conditions, and the variance objective is bounded below by zero.
  • Smoothness: The proof verifies that the variance gradient is Lipschitz continuous with respect to ω.This follows by establishing boundedness of the second derivative under the transition-model assumptions.
  • Gradient-Estimator Variance: The proof separately establishes boundedness of the gradient estimator’s variance, including its decomposed terms and cross-product components.Sample splitting makes the estimators used for the cross-product components independent.
  • Boundedness Conditions: Bounded importance-sampling terms, transition derivatives, and finite trajectory length support the required boundedness arguments.Strictly positive transition probabilities on compact parameter spaces provide a uniform lower bound used to bound inverse trajectory probabilities.
  • Conclusion: The variance of the gradient estimate is bounded, completing the central technical step of the convergence proof.The proof explicitly concludes bounded estimator variance before invoking the convergence result.

A.4 Proof of Theorem 4.3

The proof develops transition-gradient results for evaluation variance under KL regularization and off-transition dynamics. It begins by manipulating the KL term and decomposing its gradient with respect to the transition parameter.

  • Theorem 4.3 gives a KL-regularized transition gradient of variance for a fixed behavior policy and η > 0.
  • The proof manipulates the KL-divergence term before decomposing the transition-gradient expression.
  • The KL-divergence gradient is taken with respect to the transition parameter ω.
  • Theorem 4.4 treats the off-transition variance gradient when pω differs from pω0.
  • Theorem 4.5 provides the corresponding off-transition variance gradient with KL regularization and η > 0.

A.7 Proof of Lemma 5.2

The proof establishes that the importance-sampling variance objective is Lipschitz, smooth, and convex in the behavior-policy parameters under bounded-feature, bounded-ratio, and bounded-reward assumptions.

  • The analysis assumes bounded linear features, a uniform upper bound C on πe(a|s) / πθ(a|s), and rewards bounded above by 1.
  • The objective is LΘ-Lipschitz in θ under the stated assumptions.The passage identifies the Lipschitz constant as LΘ but does not include its full displayed expression.
  • The proof bounds first- and second-derivative terms using state-wise logit directions and importance-sampling estimates.
  • The objective is ℓΘ-smooth in θ with ℓΘ = B2C2T T 3(5 + 8T).
  • The objective is convex in θ under the linear softmax parameterization of the behavior policy.
  • The convergence argument uses projected updates, convexity, and a telescoping inequality involving optimization errors ϵi.

B.1 Experimental Setup

The experiments use a uniform evaluation protocol across four environments, with neural behavior policies optimized by Adam and target policies spanning random to highly deterministic behavior.

  • Behavior policies use two-layer MLPs with 64 hidden units per layer, tanh activations, and a softmax output over discrete actions.
  • Adam optimization uses learning rate 10^-3 with β1 = 0.9 and β2 = 0.999.
  • 900 runs support each reported value: 30 target policies and 30 independent runs per target policy.Figure error bars represent the standard error of the mean across these runs.
  • Garnet environments vary states, actions, and branching factor, with larger branching factors approaching fully connected transitions.
  • The inventory example uses radial-type basis functions with deterministic centers and scaling parameters.
Loading 2608.24146v1…