PaperlayerView exact revision on arXiv

Source-linked AI summary

Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient

Yuda Song, Yifei Zhou, Ayush Sekhari, J. Andrew Bagnell, Akshay Krishnamurthy, Wen Sun

arXiv:2210.06718v3cs.LG

TL;DR

Online RL is sample-inefficient, while offline RL faces distribution shift; Hybrid RL combines offline data with online correction. The paper introduces Hy-Q, a fitted-Q-iteration adaptation, and reports theoretical efficiency plus strong performance across challenging benchmarks.

  • Problem

    Online RL often requires billions of interactions, while offline RL can suffer from distribution shift; Hybrid RL seeks to combine their favorable properties.

  • Method

    Hy-Q adapts fitted Q-iteration to use offline data and online samples under assumptions including high-quality-policy coverage and low bilinear rank.

  • Results

    Hy-Q is computationally and statistically efficient under its assumptions and outperforms online, offline, imitation-learning, and hybrid baselines on challenging benchmarks.

  • Takeaways & Limitations

    Hybrid RL can reduce online interaction requirements while addressing exploration and distribution-shift challenges without requiring a favorable initial-state distribution.

  • Takeaways & Limitations

    The theoretical guarantees assume offline coverage of a high-quality policy, low bilinear rank, Bellman completeness, and a least-squares regression oracle.

Abstract

from arXiv · show

We consider a hybrid reinforcement learning setting (Hybrid RL), in which an agent has access to an offline dataset and the ability to collect experience via real-world online interaction. The framework mitigates the challenges that arise in both pure offline and online RL settings, allowing for the design of simple and highly effective algorithms, in both theory and practice. We demonstrate these advantages by adapting the classical Q learning/iteration algorithm to the hybrid setting, which we call Hybrid Q-Learning or Hy-Q. In our theoretical results, we prove that the algorithm is both computationally and statistically efficient whenever the offline dataset supports a high-quality policy and the environment has bounded bilinear rank. Notably, we require no assumptions on the coverage provided by the initial distribution, in contrast with guarantees for policy gradient/iteration methods. In our experimental results, we show that Hy-Q with neural network function approximation outperforms state-of-the-art online, offline, and hybrid RL baselines on challenging benchmarks, including Montezuma's Revenge.

1 Introduction

Hybrid RL combines offline data with online interaction to reduce exploration and sample-efficiency challenges while correcting distribution shift. The paper introduces Hy-Q, a fitted-Q-iteration adaptation with theoretical guarantees and strong benchmark performance.

  • Hybrid RL uses offline data to address exploration and online interaction to identify and correct distribution shift.
  • Hybrid RL differs from reset-based methods by using offline data instead of requiring a favorable reset distribution, while online traces still begin from the environment’s initial-state distribution.
  • Hy-Q adapts fitted Q-iteration to value-based function approximation and is efficient when offline data covers a high-quality policy and structural assumptions hold.The assumptions include low bilinear rank, Bellman completeness, and a least-squares regression oracle.
  • Hy-Q outperforms online, offline, imitation-learning, and hybrid baselines on a rich-observation combination lock and Montezuma’s Revenge.It uses only a small fraction of the online experience required by online methods and remains effective when offline data contains many low-quality samples.

2 Related Works

Prior work spans pure online RL, reset-based online RL, offline RL, and hybrid methods. The paper positions Hy-Q as a model-free hybrid approach addressing computational, exploration, and low-quality-data challenges.

  • Pure online RL can be statistically efficient yet computationally intractable beyond tabular settings because optimism is difficult to implement.
  • Reset-based methods obtain efficient guarantees from exploratory reset distributions, but such distributions are generally unavailable in practice.
  • Offline RL can be oracle-efficient with global coverage, whereas partial coverage creates computational difficulties for pessimistic methods.
  • Hy-Q is model-free and targets function-approximation settings, distinguishing it from prior model-based hybrid work.
  • Prior hybrid empirical work often uses expert demonstrations and lacks rigorous guarantees for robustness to low-quality offline data.
  • The Hy-Q procedure combines offline and online samples through fitted Q-iteration updates.

3 Preliminaries

The paper formulates finite-horizon episodic RL as an MDP with stochastic rewards and transitions, initial-state resets, nonstationary policies, and value-based function approximation. Offline data are drawn from step-specific distributions assumed to cover a high-quality policy.

  • The environment is a finite-horizon MDP with state space S, action space A, horizon H, reward and transition distributions, and initial distribution d0.
  • The agent resets only from d0, and policies are nonstationary collections of step-specific action distributions.
  • Policy value is the expected total reward from d0, while Q and V functions describe step-specific action and state values.
  • The Bellman operator maps a state-action function through the reward and future maximal value.
  • Offline samples are drawn independently from step-specific distributions, which are assumed to cover some high-quality policy rather than themselves being expert-policy distributions.The distributions may mix high- and low-quality policies, so treating them as expert demonstrations can fail.

4 Hybrid Q-Learning

Hy-Q iteratively fits Q-functions using offline data and samples collected by the current greedy policies. Its key mechanism controls Bellman error on both distributions, avoiding explicit exploration while retaining offline coverage.

  • Hy-Q takes an offline dataset and Q-function class, then iteratively applies fitted Q-iteration using offline and on-policy samples.
  • At each iteration, the current estimate defines a greedy policy that generates online state-action-reward-next-state samples.
  • FQI updates proceed backward through the horizon using least-squares regression targets built from rewards and next-step maximal Q-values.
  • Hy-Q seeks small Bellman error under both the offline distribution and the current greedy policy’s distribution.If both errors are small, the greedy policy is at least as good as policies covered by the offline distribution; otherwise, the online distribution changes substantially.
  • The offline dataset should remain comparable in size to accumulated online data so updates do not forget the offline distribution.The implementation keeps a significant number of offline samples in every update rather than switching permanently to online data.

5 Theoretical Analysis: Low Bilinear Rank Models

The analysis establishes Hy-Q’s efficiency under bilinear-rank structure, Bellman completeness, realizability, and offline coverage of a high-quality policy. Its guarantees combine offline transfer with online learning while requiring only least-squares regression and no initial-distribution coverage assumption.

  • Assumptions: Hy-Q is analyzed under realizability, Bellman completeness, bounded bilinear rank, and an offline distribution covering a high-quality policy.These assumptions support the theoretical guarantees for the function-approximation setting.
  • Coverage: The transfer coefficient is weaker than related offline-RL coverage notions and need only be small for a high-quality comparator policy.The paper contrasts this with stronger all-policy requirements used in prior work.
  • Guarantees: Theorem 1 bounds cumulative suboptimality for Hy-Q with high probability under the function-class and bilinear-rank assumptions.The greedy policy at each round is defined by the learned function f_t.
  • Proof strategy: Hy-Q preserves the offline distribution across fitted Q-iteration updates while using online data to control the learned policy’s visitation error.The proof decomposes errors into offline and online components, controls the offline term through the transfer coefficient, and controls online progress using bilinear structure and covariance tracking.
  • Implications: The resulting oracle property lets Hy-Q compete with any sufficiently covered policy, while its computation requires only least-squares problems over the function class.The paper states that comparable purely online or offline efficiency is not known without stronger uniform coverage conditions.

6 Experiments

The experiments evaluate Hy-Q on combination lock and Montezuma’s Revenge against online, offline, imitation, and hybrid baselines. Hy-Q solves difficult settings while using substantially fewer interactions and remains robust as offline data quality declines.

  • Experimental setup: The experiments compare Hy-Q with representative imitation, offline, online, and hybrid RL baselines on combination lock and Montezuma’s Revenge.The evaluation includes BC, CQL, BRIEE, RND, and DQFD.
  • Experimental presentation: The experiments use five-replicate learning curves reporting medians and 80th/20th quantiles, with dashed lines for offline, imitation, and dataset-quality references.For online methods, the Montezuma’s Revenge y-axis is a moving average over 100 episodes.
  • Combination Lock: Hy-Q reliably solves combination lock under both offline data distributions using 500k offline samples and at most 25m online samples.BC fails on both datasets, while CQL fails on the optimal occupancy dataset.
  • Combination Lock: Hy-Q uses 5-10x fewer combined samples than BRIEE on combination lock.The comparison uses total online plus offline samples.
  • Montezuma’s Revenge: On Montezuma’s Revenge, Hy-Q is the only method that performs well when the offline dataset is low quality.CQL fails across datasets, while DQFD degrades as data quality declines and BC performs poorly on the hard dataset.
  • Montezuma’s Revenge: With 100k offline samples, Hy-Q is over 10x more efficient than RND in online sample complexity.This comparison holds across the three Montezuma’s Revenge datasets.

7 Conclusion

The paper presents Hy-Q as a simple, theoretically principled, and empirically effective approach to hybrid reinforcement learning. Its results indicate robustness and sample efficiency while leaving additional hybrid algorithms as future work.

  • Conclusion: Hy-Q is presented as a simple, theoretically principled, and empirically effective hybrid RL algorithm.The conclusion frames the algorithm as a demonstration of hybrid RL’s potential.
  • Conclusion: The theoretical results address computational issues associated with pure offline or online RL, while experiments highlight robustness and sample efficiency.The conclusion describes these as the paper’s main theoretical and empirical themes.
  • Future work: The authors identify further potential in the hybrid setting and leave its exploration to future work.They characterize Hy-Q as the most natural hybrid algorithm rather than the endpoint of the design space.

A Proofs for Section 5

This appendix introduces notation for feature covariance matrices and weighted ℓ2 norms used in the proofs. The definitions prepare the quantities used in subsequent theoretical arguments.

  • Additional notation: The appendix defines the feature covariance matrix Σt;h for use throughout the proofs.This notation is introduced before the subsequent supporting arguments.
  • Additional notation: For a distribution β over state-action pairs and a function f, the appendix defines a weighted ℓ2 norm.The norm is parameterized by β and applies to functions on state-action pairs.

A.1 Supporting lemmas for Theorem 1

The supporting lemmas establish least-squares generalization, performance-difference, and potential-function bounds used in the proof of Theorem 1. The proof repeatedly decomposes Bellman-error terms and controls them with these results.

  • Supporting lemmas: A least-squares generalization lemma extends regression bounds to sequential, potentially non-i.i.d. data with approximate realizability.The paper applies the result with approximation γ = 0 in its proofs.
  • Supporting lemmas: The proof bounds each part of a regret decomposition using Bellman errors of the value function.Two supporting lemmas are introduced for the separate terms.
  • Performance difference: The performance-difference analysis uses greedy policies defined by maximizing the value function over actions.The proof also sets the terminal value function to zero for notation.
  • Proof decomposition: The recursive proof repeatedly applies the same decomposition to propagate bounds across time steps.The terminal condition is f_H(s, a) = 0.
  • Potential bounds: An elliptical-potential argument controls sequences of bounded feature vectors in the bilinear-model analysis.The lemma assumes ||X_h(f_t)|| ≤ B_X for every t.

A.2 Proof of Theorem 1

Theorem 1 analyzes Hy-Q by combining offline and online samples in fitted Q-iteration, establishing a cumulative-suboptimality bound under bilinear structure and related assumptions.

  • Proof ingredients: The analysis controls regression error with a sequential generalization bound for samples generated from adaptive data-collection processes.Offline samples come from ν_h, while online samples are generated from distributions depending on prior iterates.
  • Proof ingredients: A change-in-distribution lemma relates Bellman error under the current policy distribution to squared Bellman error under the previous policy’s data distribution.This connects the online distributional analysis to errors controlled by least-squares regression.
  • Main bound: Theorem 1 bounds cumulative suboptimality with high probability for a comparator policy having bounded transfer coefficient.The stated result specializes to m_off = T and m_on = 1.
  • Main bound: The proof combines offline and online error terms, then converts the cumulative guarantee into a sample-complexity statement through online-to-batch conversion.The total online sample count includes an additional H factor because samples are collected at every time step.
  • Bilinear structure: The V-type bilinear extension uses uniform random actions during online collection and requires only a slight change to the data-collection process.The V-type definition evaluates actions from the greedy policy associated with one function, while online batches use uniformly sampled actions.
  • Algorithm and setup: Hy-Q estimates each value function by least-squares regression on aggregated offline and online data.The implementation initializes value functions and updates them through fitted Q-iteration using the combined dataset.

A.3.1 Complexity bound for V-type Bilinear models

This section extends the Hy-Q analysis to V-type bilinear models, deriving cumulative and sample-complexity guarantees while relating the transfer coefficient to coverage and feature conditioning.

  • Analysis: The V-type analysis reuses the FQI estimation and change-in-distribution machinery developed for the Q-type setting.The proof transfers the earlier analysis while modifying the online data collection for V-type models.
  • Main guarantee: For V-type bilinear models, the main theorem gives a high-probability cumulative-suboptimality bound when m_on = |A| and m_off = T.The bound is obtained by combining offline and online error terms under the V-type structure.
  • Main guarantee: Corollary 2 converts the cumulative guarantee into an ϵ-suboptimal policy using a total sample-complexity bound.The result assumes finite transfer coefficient C^π* and uses online-to-batch conversion.
  • Transfer coefficient: The transfer coefficient captures both distribution shift and function-class effects and is smaller than several existing density-ratio and Bellman-error concentrability coefficients.This coefficient provides a more targeted measure of transfer difficulty for the hybrid analysis.
  • Coverage interpretations: In linear Bellman-complete settings, the transfer coefficient is bounded through a relative condition number defined by feature covariance matrices.The argument uses the linear representation of value functions and Bellman completeness.
  • Coverage interpretations: In low-rank MDPs, the transfer coefficient can be bounded using relative feature coverage and an action-coverage parameter.The result assumes trajectory-generated offline distributions and invertible feature covariance, without requiring covariance eigenvalues to be lower bounded.

C Low Bellman Eluder Dimension problems

Hy-Q also extends to environments with low Bellman Eluder dimension, yielding a cumulative-suboptimality guarantee beyond bilinear models under suitable function-class assumptions.

  • Setting: The Bellman Eluder dimension is a distributional complexity measure applied to Bellman residuals induced by the value-function class.The analysis uses distributional Eluder dimension over occupancy measures generated by greedy policies.
  • Implication: The extension shows that Hy-Q applies to a broader model-free RL framework than the bilinear-rank setting alone.The section presents this as evidence that Hy-Q can obtain guarantees for problems with small Bellman Eluder dimensions.
  • Proof strategy: The proof controls accumulated Bellman error using a lemma that bounds sums of squared expectations over distribution sequences.It applies this control to Bellman residuals and occupancy measures induced by greedy policies.
  • Guarantee: Theorem 3 assumes Bellman Eluder dimension d, sets m_off = HT/d and m_on = H^2, and provides a high-probability cumulative-suboptimality bound.The comparator policy may be any policy π_e under the theorem’s stated assumptions.
  • Relation to prior work: The related-work discussion distinguishes Hy-Q from prior hybrid approaches by using Q-learning and allowing offline data that need not consist of expert demonstrations.Prior empirical work often combines offline expert demonstrations with online interaction, whereas Hy-Q targets more general offline datasets.

E.3 Implementation Details of Montezuma’s Revenge experiment

The Montezuma’s Revenge implementation uses discounted neural fitted Q-iteration with separate online and offline buffers, minibatch updates, exploration, and delayed target-network updates.

  • Algorithm configuration: Discounted Hy-Q uses a neural value-function class with discount factor, learning rate, exploration rate, and separate value and target update frequencies.These quantities are listed as required algorithmic inputs for the Montezuma’s Revenge implementation.
  • Baselines and reproducibility: The implementation uses standard public implementations and evaluates baselines in the same stochastic environment setup as the Hy-Q experiment.The reported setup includes CQL, BRIEE, RND, and DQfD implementations from public repositories.
  • Initialization: The implementation initializes online and target value functions, starts with an empty online buffer, and samples an initial state from d0.The target function is initialized from the current value function before interaction begins.
  • Data use and updates: At each interaction step, an ϵ-greedy policy selects actions, the transition is added to the online buffer, and minibatches are sampled from either online or offline data.The offline-versus-online minibatch choice is governed by the offline sample ratio β.
  • Data use and updates: The value network performs one-step gradient updates, while the target network is copied from the current value function only at delayed update intervals.This implementation follows the discounted Hy-Q procedure for the stochastic Atari setting.
Loading 2210.06718v3…