When is Offline Hyperparameter Selection Feasible for Reinforcement Learning?

Vincent Liu, Prabhat Nagarajan, Andrew Patterson, Martha WhiteICLR 2023 · OpenReview

TL;DR

This paper investigates the fundamental question of when we can efficiently select the best policy from a set of candidates using only offline data in reinforcement learning. The authors establish that offline policy selection is inherently as hard as off-policy policy evaluation (OPE), meaning efficient selection requires conditions that also make OPE efficient. They then identify specific conditions under which two common OPE methods, Fitted Q-Evaluation (FQE) and Bellman Error, can achieve sample-efficient policy selection.

What Problem Does This Paper Address?

Deploying reinforcement learning (RL) agents in the real world often requires selecting the best policy from a pool of candidates that have been trained offline. This is crucial because online exploration can be expensive, dangerous, or simply infeasible. This process, known as offline policy selection (OPS), is particularly important for choosing the right algorithm and its hyperparameters. However, there's a significant lack of understanding regarding the fundamental limitations of OPS and when it can be performed efficiently (i.e., with a polynomial number of samples). The paper aims to bridge this gap by analyzing the sample complexity of OPS and identifying conditions for its efficiency.

Methods

The paper's core contribution lies in its theoretical analysis of the sample complexity of offline policy selection.

  • Relating OPS to OPE: The authors prove that the sample complexity of OPS is both upper-bounded and lower-bounded by the sample complexity of Off-Policy Policy Evaluation (OPE). This means that efficient OPS is only possible when OPE is also efficient, and no OPS method can be more sample-efficient than OPE in the worst case.
  • Conditions for FQE Efficiency: They theoretically analyze Fitted Q-Evaluation (FQE), a popular OPE method, and show that it can achieve sample-efficient OPS if the candidate policies are "well-covered" by the offline dataset. This means the data distribution adequately represents the behavior of all candidate policies.
  • Conditions for Bellman Error Efficiency: The paper also investigates using Bellman errors (BE) for policy selection. They provide theoretical arguments suggesting BE can be more sample-efficient than FQE under stronger assumptions, particularly when the environment dynamics are deterministic and data coverage is good.
  • Empirical Validation: The theoretical findings are complemented by an empirical study comparing FQE and BE on Acrobot and Cartpole environments, evaluating their performance under different data coverage scenarios.

Datasets

The paper does not introduce new datasets. Instead, it focuses on theoretical analysis and uses synthetic data generated according to specific distributions for empirical evaluation. These distributions are designed to represent different scenarios of data coverage:

  • Well-covered data: Generated by a mixture of all candidate policies.
  • Diverse data: Includes a mixture of candidate policies and an ε-greedy optimal policy to provide more diverse trajectories.
  • Expert data: Collected by a deterministic optimal policy.

Key Insights and Ideas

  • OPS is no easier than OPE: This is a fundamental takeaway. The paper rigorously shows that if you can't efficiently evaluate policies offline (OPE), you likely can't efficiently select the best one either. This implies that any hope for efficient OPS hinges on making OPE efficient, which often requires specific assumptions about the data or environment.
  • "Well-covered" data is key for FQE: The paper highlights that FQE's efficiency in policy selection is strongly tied to how well the offline data represents the behavior of all candidate policies. If the data is sparse or doesn't cover certain policies, FQE can struggle.
  • Bellman Error's potential and pitfalls: BE shows promise for sample efficiency, especially in deterministic settings with good data coverage. However, its reliance on stronger assumptions and potential for poor performance in stochastic environments or with poor data coverage are significant limitations.
  • The "deadly triad" still looms: The paper implicitly touches upon the challenges of combining off-policy learning, bootstrapping, and function approximation (the "deadly triad") in FQE, which can lead to divergence. This underscores the need for careful assumptions and analysis.

Key Results

  • Theoretical Bounds: The paper establishes that the sample complexity of offline policy selection is lower-bounded by that of off-policy policy evaluation (OPE).
  • FQE Efficiency: FQE is shown to be sample-efficient for policy selection when candidate policies are well-covered by the offline dataset.
  • BE Efficiency: Bellman Error (BE) can be more sample-efficient than FQE under stronger assumptions, particularly deterministic dynamics and good data coverage.
  • Empirical Findings:
    • FQE performs well when candidate policies are well-covered.
  • BE performs better than FQE with diverse data coverage, especially with smaller sample sizes.
  • Neither method performs well without their corresponding data coverage conditions.
  • In Acrobot, BE tends to perform better with larger k (number of top policies selected) even with good data coverage, while FQE can achieve low top-1 regret with good coverage.

Limitations and Future Work

  • Data Coverage is Crucial: The paper emphasizes that both FQE and BE rely heavily on specific data coverage assumptions. When these assumptions are violated, performance degrades significantly.
  • Stochastic Environments for BE: The theoretical analysis for Bellman Error is primarily focused on deterministic environments. Estimating BE in stochastic environments is noted as a direction for future work, potentially requiring more samples and having sample complexity similar to FQE.
  • Hyperparameter Tuning: While the paper provides theoretical insights, practical implementation still requires careful selection of function classes and optimization hyperparameters, which can be challenging.
  • Candidate Policy Set Structure: The authors suggest that future work could explore how the structure or properties of the candidate policy set can be exploited for more efficient selection.
  • Early Stopping and Pessimism: Investigating heuristic approaches like early stopping when FQE diverges or using pessimistic versions of FQE to handle uncovered policies are mentioned as potential avenues.

Summary updated

Abstract

Hyperparameter selection is a critical procedure before deploying reinforcement learning algorithms in real-world applications. However, hyperparameter selection prior to deployment requires selecting policies offline without online execution, which is a significant challenge known as offline policy selection. As yet, there is little understanding about the fundamental limitations of the offline policy selection problem. To contribute to our understanding of this problem, in this paper, we investigate when sample efficient offline policy selection is possible. As off-policy policy evaluation (OPE) is a natural approach for policy selection, the sample complexity of offline policy selection is therefore upper-bounded by the number of samples needed to perform OPE. In addition, we prove that the sample complexity of offline policy selection is also lower-bounded by the sample complexity of OPE. These results imply not only that offline policy selection is effective when OPE is effective, but also that sample efficient policy selection is not possible without additional assumptions that make OPE effective. Moreover, we theoretically study the conditions under which offline policy selection using Fitted Q evaluation (FQE) and the Bellman error is sample efficient. We conclude with an empirical study comparing FQE and Bellman errors for offline policy selection.
BibTeX
@inproceedings{liu2023when,
  author = {Vincent Liu and Prabhat Nagarajan and Andrew Patterson and Martha White},
  title = {{When is Offline Hyperparameter Selection Feasible for Reinforcement Learning?}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=Hvcmr6FSIX8},
}
Figure