acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 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.

Primary area:
reinforcement learning
Keywords:
policy evaluation, behavior policy search, data collection, reinforcement learning, variance reduction, robust reinforcement learning, transition uncertainty

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_mGHDOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies an important and practical problem in reinforcement learning policy evaluation: how to collect online data so that an off-policy estimator has low variance even when the true environment dynamics differ from the simulator used for training. Existing behavior policy search methods optimize the data-collection policy for a fixed transition model, so the variance reduction can degrade under sim-to-real transition mismatch. The paper deals with this as a minimax problem: an adversarial transition model chooses dynamics that maximize evaluation variance, and the behavior policy chooses actions to minimize that worst-case variance. It proposes DRVG, a double-loop gradient algorithm. The inner loop does gradient ascent on the transition parameters; the outer loop does projected gradient descent on the behavior-policy parameters. The paper also adopts an optional KL regularization term to keep the adversarial transition close to the original simulator. The main theoretical contributions are the analytical transition-gradient formulas and convergence result for the inner adversarial optimization, followed by a global convergence guarantee for the outer DRVG algorithm. Importantly, the global result is proved under a linear-softmax behavior-policy parameterization, bounded features and importance ratios, and compact convex parameter sets; under these assumptions the worst-case variance objective becomes convex in the behavior-policy parameters and DRVG achieves an expected O(1/n)O(1 / \sqrt{n}) convergence rate with some additional terms. The empirical validation shows that DRVG has the smallest increase in variance under its own adversarial transition and also achieves the lowest variance among several methods under a shared perturbed transition.

Critical strengths

1. The paper addressed an important problem in behavior policy search. Existing BPS methods optimize the data-collection policy for a fixed transition model, but the paper recognizes that the quantity being optimized is ultimately evaluated in an environment with shifted dynamics. Formulating the problem as a minimax problem is neat: the adversary represents the transition uncertainty, while the behavior policy is explicitly optimized for worst-case evaluation variance.

2. The transition-gradient derivation is a good methodological contribution. A key technical step is showing that the gradient of the variance with respect to the transition parameters can be written in terms of the transition score and moments of the OPE estimator. This makes adversarial transition optimization possible directly from sampled trajectories and the paper derives the expression for a general OPE estimator rather than being tied intrinsically to one particular estimator. The resulting Algorithm 1 also uses sample splitting to construct an unbiased estimate of the product-of-expectations term.

Critical weaknesses

The global convergence guarantee depends on an inner-loop accuracy condition that the proposed algorithm does not establish. Specifically, Theorem 5.4 assumes that, at each outer iteration, the adversarial transition is an ϵi\epsilon_i-optimal solution to the inner maximization problem. It is unclear whether the practical algorithm can achieve this inner-loop guarantee. Consequently, the paper's main theoretical guarantee does not fully guarantee the behavior of its proposed algorithm.

Questions for authors

Q1. How does the practical inner-loop algorithm satisfy the accuracy assumption required by the global convergence theorem? Theorem 5.4 assumes that the inner maximization returns a ϵi\epsilon_i-optimal adversarial transition at every outer iteration. However, Algorithm 1 and Lemma 4.2 establish convergence to a stationary point, which seem not to guarantee global optimality.

Q2. How are the compactness and feasibility assumptions on the transition parameters enforced in Algorithm 1? The convergence analysis assumes a compact transition parameter space Ω\Omega, along with smoothness and bounded-derivative conditions for the transition model. However, Algorithm 1 seems to update the parameter ω\omega using an unconstrained gradient-ascent step, without projection onto the space Ω\Omega. Could the authors clarify how the transition parameters are kept within the theoretically assumed feasible set during optimization? Specifically, does the implementation impose parameter bounds, apply projection or clipping?

Q3. How realistic is the O(1/n)O(1/\sqrt{n}) convergence rate when its constants depend strongly on the horizon TT? Theorem 5.4 establishes a O(1/n)O(1/\sqrt{n}) theoretical guarantee, but the constants depend on the horizon TT. In particular, σθ2\sigma^2_{\theta} scales as 2B2C4TT62B^2 C^{4T} T^6. This seems huge. Could the authors clarify the regimes where this guarantee provides a realistic sample-complexity bound, rather than only an asymptotic convergence rate? For example, can the dependence on the horizon TT be improved under certain additional conditions?

2 comments

I would like to thank the authors for addressing my questions. The authors gave detailed reply to all three questions of mine, together with modification to the paper draft. I find the authors' reply directly answered all my question. Especially for Q3 where I have concerns about the strong dependence on T will make the bound poor in long horizon environments, the authors showed that the dependence can be improved without extra mathematical assumption. Overall, I appreciate the rebuttal and thus I raise my score.

Many thanks for taking the time to review our responses and revised manuscript! We are glad that our clarifications and the improved horizon-dependence analysis addressed your concerns. We sincerely appreciate your thoughtful feedback and your reconsideration of our paper!

Reviewer_ssomOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies behavior-policy learning for low-variance policy evaluation under uncertainty in environment dynamics. The paper proposes a double-loop gradient-based algorithm that alternates between adversarial transition updates and behavior-policy updates, supported by theoretical analysis and numerical experiments.

Critical strengths
  1. The paper presents a well-motivated formulation that explicitly accounts for transition uncertainty when optimizing data collection for policy evaluation. The problem formulation and proposed algorithm are clearly presented.

  2. The numerical experiments show lower evaluation variance than the evaluated baselines under the tested adversarial transition perturbations, supporting the intended robustness benefit.

Critical weaknesses

Although the paper includes experiments on two benchmark families, the method requires strong simulator access during training, including access to gradients of transition log-probabilities and the ability to sample from updated transition models. It remains unclear how these requirements would be met in practical settings, particularly when only a black-box simulator is available or the transition model must be learned from limited data. An application-inspired experiment with structured transition shifts would help clarify the method's practical applicability.

Questions for authors

I have no additional questions beyond the concern raised above.

2 comments

Thank you for the clarification and the concrete examples of suitable simulation frameworks. The discussion of the off-transition extension also helps clarify applicability when simulator dynamics cannot be modified. These explanations sufficiently address my concern, and I will maintain my positive assessment.

Many thanks for your encouraging feedback! We are glad that our clarifications addressed your concerns. We sincerely appreciate your thoughtful review and continued support!

Reviewer_G9MMOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers the optimization problem that learns a low-variance data-collection policy while maintaining reliable under transition-model mismatch, leading to the formulation min⁡θmax⁡ωVarpω,πθ[OPE(πe,πθ,H)].\min_{\theta}\max_{\omega}\mathrm{Var}_{p_{\omega}, \pi_{\theta}}[OPE(\pi_e, \pi_{\theta}, H)]. The paper provided gradient-based algorithm and global convergence guarantee for solving the mini-max optimization. Numerical results validate the efficiency and robustness of the authors' framework.

Critical strengths
  1. The provided formulation is interesting and can be flexibly adopted to general frameworks.
  2. The provided gradient-based algorithms are useful methodological contributions.
Critical weaknesses
  1. as far as I have understood, the global convergence algorithm requires each inner loop iterate solves the inner max problem up to global optimally gap \epsilon_i, but it is generally a non-concave objective so it is unclear how to do so.
  2. for the transition gradient of variance (Theorem 4.3), this is the main theorem of this manuscript, but the authors fail to provide detailed mathematical assumptions behind it.
  3. Theory and implementation is a little bit mismatched: theory used log-linear behavior policies, but experiment used neural nets.
Questions for authors
  1. Algorithm 1 assumes ω\omega is unconstrained, which contradicts to the assumption that ω∈Ω\omega\in\Omega
6 comments

Many thanks again for your thoughtful review! As the discussion period is approaching its end, we wanted to kindly follow up on our responses and revised manuscript. We hope our revisions have addressed your concerns, and we would greatly appreciate any further feedback or questions you may have.

Thank you again for your time and consideration!

I thank the authors' efforts, but I maintain my score due to the following reasons:

  1. the revision made by authors are not highlighted in blue or other colors explicitly, making it difficult to track how the authors addressed my concern.
  2. for the global convergence of my first concern, I read the manuscript, but do not fully understand why arbitrarily small optimality gap can be established without concavity requirement.

Many thanks for taking the time to examine our revised manuscript and for your follow-up questions! We appreciate the opportunity to clarify these two points.

1. Highlighting changes in the revised manuscript

Thank you for pointing this out! According to the ICLR 2027 Author Guidelines, a PDF diff is automatically generated to compare the revised manuscript with the original submission. We therefore leveraged this feature without manually highlighting modifications in color. We apologize if this made the changes difficult to locate.

For convenience, the main theoretical additions are:

  • Appendix A.2: Explicit mathematical assumptions underlying Theorems 4.1 and 4.3.
  • Appendix A.8: A new constructive inner-oracle guarantee (Proposition A.3), including its proof and an explicit end-to-end convergence bound.
  • Appendix A.7: A refined horizon-dependence analysis for Theorem 5.4.

We hope these pointers make the revisions easier to follow.

2. How can arbitrarily small global inner optimality gaps be achieved without concavity?

Thank you for this important follow-up! The key observation is that our new Proposition A.3 establishes global approximation accuracy through a finite-cover search over the entire feasible parameter set. Thus, inner concavity is not required as we do not rely on local gradient ascent.

Specifically, for a fixed behavior policy θ\theta, let Fθ(ω)=V(θ,ω)F_\theta(\omega)=V(\theta,\omega), and let ω⋆\omega^\star be a global maximizer over the compact set Ω\Omega. Under the boundedness and transition-regularity conditions stated in Appendix A.8, we establish that FθF_\theta is Λ\Lambda-Lipschitz.

We then construct a feasible δ\delta-net Ωδ⊆Ω\Omega_\delta\subseteq\Omega. By definition, there exists a candidate ωj∈Ωδ\omega_j\in\Omega_\delta such that ∥ωj−ω⋆∥≤δ\|\omega_j-\omega^\star\|\leq\delta. If ω^\widehat\omega is the candidate with the largest exact variance, we obtain

\Phi(\theta)-V(\theta,\widehat\omega) &=F_\theta(\omega^\star)-F_\theta(\widehat\omega)\\ &\leq F_\theta(\omega^\star)-F_\theta(\omega_j)\\ &\leq \Lambda\delta. \end{aligned}$$ Therefore, **for any desired $\epsilon>0$, choosing $\delta\leq\epsilon/\Lambda$ guarantees an $\epsilon$-globally optimal inner solution** (when $\Lambda>0$). This does not require concavity because the search covers the entire feasible domain, and that we are not relying on a stationary point being globally optimal. When candidate variances are evaluated with a uniformly bounded error $\zeta$, the same argument gives $$\Phi(\theta)-V(\theta,\widehat\omega) \leq\Lambda\delta+2\zeta.$$ Appendix A.8 further provides exact variance evaluation through dynamic programming in the fully evaluable finite-state setting, as well as high-probability and expected-error guarantees when variance is estimated from simulated trajectories. The trade-off is computational: the number of cover points may grow exponentially with the parameter dimension. Nevertheless, the construction establishes that the required global inner accuracy is attainable within our original transition family without assuming concavity, and provides a concrete inner-solver instantiation for the convergence guarantee in Theorem 5.4. This is complementary to the practical stochastic gradient-ascent method in Algorithm 1, whose analysis establishes stationarity. We hope this clarifies the mathematical mechanism behind Proposition A.3. We sincerely appreciate your careful reading and thoughtful questions, and would be happy to discuss any remaining concerns!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.