PaperlayerView exact revision on arXiv

Source-linked AI summary

Bilinear Classes: A Structural Framework for Provable Generalization in RL

Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, Ruosong Wang

arXiv:2103.10897v3cs.LGcs.AImath.OCstat.ML

TL;DR

The paper addresses how to obtain sample-efficient RL generalization over large state-action spaces with function approximation. It introduces Bilinear Classes and BiLin-UCB, yielding polynomial guarantees reduced to supervised-learning generalization while covering new models and non-parametric RKHS settings.

  • Problem

    Large state-action spaces make RL generalization difficult, motivating structural conditions that characterize learnability across broad function-approximation models.

  • Method

    The paper defines Bilinear Classes through shared bilinear-form estimation of Bellman error and develops the optimization-based BiLin-UCB algorithm.

  • Results

    The framework provides polynomial sample-complexity guarantees, includes linear Q∗/V∗ and other new models, and extends to infinite-dimensional RKHS settings using critical information gain.

  • Takeaways & Limitations

    Bilinear Classes unify many sample-efficient RL models while allowing non-parametric guarantees without explicit dependence on feature dimension.

  • Takeaways & Limitations

    The linear-MDP setting assumes a known feature map into a Hilbert space and linear-function hypothesis class.

Abstract

from arXiv · show

This work introduces Bilinear Classes, a new structural framework, which permit generalization in reinforcement learning in a wide variety of settings through the use of function approximation. The framework incorporates nearly all existing models in which a polynomial sample complexity is achievable, and, notably, also includes new models, such as the Linear $Q^*/V^*$ model in which both the optimal $Q$-function and the optimal $V$-function are linear in some known feature space. Our main result provides an RL algorithm which has polynomial sample complexity for Bilinear Classes; notably, this sample complexity is stated in terms of a reduction to the generalization error of an underlying supervised learning sub-problem. These bounds nearly match the best known sample complexity bounds for existing models. Furthermore, this framework also extends to the infinite dimensional (RKHS) setting: for the the Linear $Q^*/V^*$ model, linear MDPs, and linear mixture MDPs, we provide sample complexities that have no explicit dependence on the explicit feature dimension (which could be infinite), but instead depends only on information theoretic quantities.

1 Introduction

The paper proposes Bilinear Classes as structural conditions for sample-efficient RL generalization and develops BiLin-UCB with guarantees reduced to supervised-learning generalization. The framework covers existing and new models, including non-parametric RKHS settings and flexible extensions.

  • Contributions: BiLin-UCB achieves polynomial sample complexity for Bilinear Classes through an optimization-based algorithm.The algorithm repeatedly restricts a version space using batch-data constraints and optimistically selects a feasible hypothesis.
  • Contributions: Bilinear Classes require Bellman error control through a hypothesis-dependent bilinear form estimable for all hypotheses using one dataset.This shared estimation enables data reuse and elimination of hypotheses with high Bellman error.
  • Contributions: The sample-complexity guarantee reduces RL learning to the generalization error of an underlying supervised-learning problem without explicit assumptions on H itself.This can allow neural hypothesis classes when they satisfy the implicit Bilinear Class relationship with the MDP.
  • New models: The framework includes linear Q∗/V∗, Low Occupancy Complexity, and RKHS versions of linear MDPs and linear mixture MDPs.In particular, sample-efficient learning becomes possible when both Q∗ and V∗ are linear, contrasting with the stated impossibility under only linear Q∗.
  • Non-parametric results: The results are non-parametric and use critical information gain, extending finite-dimensional analyses to settings where feature representations may be infinite-dimensional.The paper relates critical information gain to the critical radius used in non-parametric statistics.
  • Extensions: Simple modifications extend Bilinear Classes to settings such as Witness Rank and Kernelized Nonlinear Regulator.The paper presents these extensions in Section 6.

2 Related Work: Frameworks and Models

The related-work discussion contrasts low-rank, completeness, eluder-dimension, and Bellman-eluder frameworks with Bilinear Classes. It emphasizes that Bilinear Classes cover models and action spaces that some alternatives cannot handle.

  • Existing frameworks: Bellman Rank and Witness Rank use low-rank structures, while Bellman Complete assumes the approximating function class is closed under the Bellman operator.The low-rank and complete-style frameworks do not contain one another.
  • Bellman Eluder: Bilinear Classes and Bellman Eluder dimension do not capture each other because they apply complexity measures to different structural aspects of the MDP.Bilinear Classes apply to loss estimators of Bellman error, while Bellman Eluder applies directly to Bellman error.
  • Bellman Eluder: Bilinear Classes naturally capture model-based settings including linear mixture MDPs, KNRs, and factored MDPs through flexible Bellman-error estimators.The comparison identifies these settings as difficult for model-free algorithms and frameworks.
  • RL models: Linear MDPs satisfy low-rank and complete conditions, whereas linear mixture MDPs are included by Bilinear Classes but not by Bellman Rank, Witness Rank, or Bellman Complete.Linear MDPs assume transition probabilities and rewards are linear in given features; linear mixture MDPs use mixtures of base transition models.
  • RL models: Bellman Rank and Witness Rank cannot incorporate LQR when their algorithms scale with the number of actions, because LQR has an uncountable action set.The discussion likewise notes action-count limitations for some linear-MDP settings with infinitely many actions.

3 Setting

The paper studies episodic finite-horizon, non-stationary MDPs with states, actions, rewards, transition kernels, and a fixed initial state. Policies, Q-functions, and value functions are defined over trajectories induced by the policy.

  • MDP setting: The setting uses an episodic finite-horizon, non-stationary MDP with horizon H, state space S, action space A, rewards in [0,1], and transition kernels P_h.The initial state s0 is fixed, with results stated to generalize to any fixed initial-state distribution.
  • Policies: A deterministic stationary policy maps states to actions, while a non-stationary policy is a sequence of timestep-specific stationary policies.Actions are selected adaptively from the current state.
  • Value functions: The Q-function assigns expected return from a state-action pair at a timestep under a policy, and the value function assigns expected return from a state.Both expectations are taken over trajectories generated by the policy.
  • Value functions: Q∗ and V∗ denote the Q- and value-functions of the optimal policy.The notation is used throughout the paper for optimal-policy quantities.
  • Sample efficiency: An algorithm is considered sample-efficient when its trajectory count is polynomial in H, inherent dimension d, and accuracy 1/ε, and polylogarithmic in candidate value-functions.This is the paper’s stated sample-efficiency convention.

4 Bilinear Classes

The paper defines Bilinear Classes through Bellman-error structure and shared estimation, then shows the framework subsumes prior models and supports new settings.

  • The framework allows abstract model-based or value-based hypothesis classes, provided each hypothesis has associated Q- and V-functions.Examples include explicit Q/V pairs, Q-only classes with greedy V-functions, and model or transition-kernel classes.
  • Bilinear Classes generalize Bellman rank through suitable discrepancy functions and estimation policies for both Q- and V-Bellman rank.The Q version uses on-policy estimation, while the V version uses uniform action estimation.
  • Known Linear Bellman Complete and Linear Mixture Models, plus new Linear Q*/V* and Low Occupancy Complexity models, are presented as Bilinear Classes.The framework is also extended to RKHS versions of several models and can include Witness Rank and Kernelized Nonlinear Regulator through modifications.
  • The framework introduces Linear Q*/V* models, where optimal Q* and V* are linear in known features in possibly infinite-dimensional Hilbert spaces.The paper establishes that Linear Q*/V* instances are Bilinear Classes.
  • The framework also introduces Low Occupancy Complexity, requiring realizability while allowing otherwise arbitrary hypothesis classes and unknown feature mappings.The algorithm need not know the occupancy features or associated coefficients, and neural state-action value classes are permitted.

5 The Algorithm and Theory

The paper presents BiLin-UCB, an optimization-based algorithm whose RL sample complexity reduces to supervised-learning generalization, including finite- and infinite-dimensional settings.

  • BiLin-UCB iteratively constrains a version space using discrepancy estimates formed from all previously collected data.It takes iteration count T, trajectory batch size m, and confidence radius R as inputs.
  • The algorithm collects on-policy trajectories when estimation follows the candidate policy, or separately samples each timestep under a general estimation policy.The latter procedure rolls in with the candidate policy, samples the timestep action from the estimation policy, then observes the transition and reward.
  • Theorem 5.2 provides a high-probability sample-complexity guarantee for Bilinear Classes in terms of the supervised-learning generalization and confidence functions.The finite-dimensional theorem and RKHS theorem instantiate this guarantee under their respective feature-space conditions.
  • Polynomial RL learning follows when the discrepancy class has generalization error εgen(m, H) decaying at least as m^-α for a constant α.The main assumption separates uniform-convergence error from failure-probability dependence.
  • In the RKHS setting, complexity can depend on the information-theoretic quantity γ_n(λ; X) rather than explicitly on feature dimension, including when the RKHS is infinite-dimensional.The effective quantity may be smaller than the ambient dimension when covariance eigenspectra concentrate in a low-dimensional subspace.
  • The results extend to Linear Q*/V*, Bellman Complete, Linear Mixture, and Low Occupancy Complexity models, including RKHS versions of several models.For the finite-dimensional Bellman Complete and Linear Mixture cases, the algorithm returns an ε-optimal policy with probability at least 1−δ under the stated parameter settings.

6 Extended Bilinear Classes

The paper extends Bilinear Classes through nonlinear transformations and discriminator classes, showing that the generalized framework captures several additional RL models and supports supervised-learning-style generalization analysis.

  • Generalized Bilinear Classes: Generalized Bilinear Classes add nonlinear transformations ξ and ζ and discriminator classes F_h to the original framework.The definition retains realizability and bilinear representations in a Hilbert space while extending the discrepancy structure.
  • Generalized Bilinear Classes: The extended framework reduces learning guarantees to supervised-learning-style generalization error for the enlarged hypothesis and discriminator classes.The analysis assumes a generalization function ε_gen(m, H, F) and derives regret guarantees under the stated transformation assumptions.
  • 6.1 Kernelized Nonlinear Regulator: Kernelized Nonlinear Regulators are generalized Bilinear Classes under on-policy estimation, despite value functions that may be too complicated for prior model-free frameworks.The construction uses empty discriminator classes and sets the estimation policy to π_f.
  • 6.2 Generalized Linear Bellman Complete and Witness Rank: Generalized linear Bellman complete models and finite Witness Rank models are also represented as Bilinear Classes.The corresponding results use on-policy estimation for generalized linear Bellman completeness and uniform estimation for finite Witness Rank.
  • 6.4 Factored MDP: The framework captures factored MDPs with complexity that can be exponentially smaller than |O|^d when parent sets remain small.The stated complexity depends on the parent-set structure rather than the full un-factorized observation-space representation.

7 Conclusion

The conclusion presents Bilinear Classes and BiLin-UCB as a unified framework and algorithm for function-approximation RL, including new models and non-parametric information-theoretic rates.

  • 7 Conclusion: Bilinear Classes and BiLin-UCB provide a shared framework, algorithm, and proof strategy for many learnable RL models.The authors emphasize that the same algorithm and proof can analyze multiple models with function approximation.
  • 7 Conclusion: The framework includes linear Q⋆/V⋆, RKHS Bellman complete, RKHS linear mixture, and low occupancy complexity models.It also extends to further examples including Witness Rank and Kernelized Nonlinear Regulators.
  • 7 Conclusion: The resulting rates are non-parametric and depend on critical information gain rather than explicit feature dimension.Critical information gain is described as analogous to the critical radius in non-parametric statistics.

A.2 Q⋆irrelevance Aggregation / Q⋆state Aggregation

The Q⋆irrelevance aggregation model is shown to be a Bilinear Class by reducing it to a linear Q⋆/V⋆ representation.

  • A.2 Q⋆irrelevance Aggregation / Q⋆state Aggregation: Q⋆irrelevance aggregation assumes a known state representation ζ that supports the model’s aggregation structure.The representation set is Z = {ζ(s) : s ∈ S}.
  • A.2 Q⋆irrelevance Aggregation / Q⋆state Aggregation: The model uses a hypothesis class of linear functions over the representation set Z.The construction defines H as a product of horizon-indexed linear function classes.
  • A.2 Q⋆irrelevance Aggregation / Q⋆state Aggregation: The Q⋆irrelevance aggregation model forms an implicitly Bilinear Class with on-policy estimation policies π_est(f) = π_f.This is established for the specified hypothesis and discrepancy function.
  • A.2 Q⋆irrelevance Aggregation / Q⋆state Aggregation: The proof constructs one-hot representations that reduce the model to the linear Q⋆/V⋆ model.The linear Q⋆/V⋆ reduction then yields the Bilinear Class result.

A.3 Linear Quadratic Regulator

The paper shows that finite-horizon discrete-time Linear Quadratic Regulators form Bilinear Classes, using quadratic value functions induced by linear policies.

  • A.3 Linear Quadratic Regulator: The Linear Quadratic Regulator has unknown linear dynamics and reward parameters with state space S ⊂ R^d and action space A ⊂ R^K.The model is defined through unknown matrices A, B, and Q.
  • A.3 Linear Quadratic Regulator: Linear non-stationary policies induce quadratic value functions in the LQR setting.This property motivates the horizon-indexed hypothesis class used in the Bilinear Class construction.
  • A.3 Linear Quadratic Regulator: The constructed LQR hypothesis and discrepancy function use on-policy estimation policies π_est(f) = π_f.The paper defines the discrepancy over observed transition information and proves the resulting structure is an implicitly Bilinear Class.
  • A.3 Linear Quadratic Regulator: The LQR proof verifies a stronger equality form of the Bilinear Class condition using Bellman conditions.The argument also uses ⟨W_h(f⋆), X_h(f)⟩ = 0, which follows from those conditions.

A.4 Linear MDP

This section instantiates the Bilinear Class framework for Linear MDPs and describes related partially observable models. Linear MDPs use Hilbert-space features to represent transitions and rewards, and the associated linear hypothesis class satisfies Bellman completeness and is therefore a Bilinear Class.

  • Linear MDP: Linear MDPs represent transitions and rewards as inner products between Hilbert-space features and unknown measures or parameters.For each horizon step, P_h(·|s,a)=⟨φ(s,a),μ_h(·)⟩ and r_h(s,a)=⟨φ(s,a),θ_h⟩.
  • Linear MDP: The Linear MDP hypothesis class consists of functions linear in φ, parameterized by tuples (θ_0,…,θ_{H−1}).
  • Linear MDP: This hypothesis class satisfies Bellman completeness and is therefore also a Bilinear Class.
  • Related models: Block MDPs use disjoint observation blocks that permit perfect decoding of latent states and are a subclass of FLAMBE, hence they fall within the Bilinear Class framework.
  • Related models: Reactive POMDPs have optimal Q-functions depending only on the latest observation and action, and their Bellman rank is bounded by the latent-state-space size.

B Proofs for Section 5

This section derives a sample-size condition for obtaining an ε-optimal policy from concentration and log-dominance lemmas. The resulting trajectory complexity follows by combining the required per-sample size with the auxiliary bound.

  • Proof of Corollary 5.1: The proof applies Lemma F.1 to obtain a uniform concentration statement over hypotheses under an i.i.d. sample.
  • Proof of Corollary 5.1: The concentration bound is substituted into Assumption 5.1 and then Theorem 5.1 to derive the required sample size.
  • Proof of Corollary 5.1: An ε-optimal policy is obtained by choosing m at least as large as the derived threshold.
  • Proof of Corollary 5.1: Lemma F.2 supplies a solution for m, which yields the total trajectory complexity after substitution.

C An Elliptical Cover for Hilbert Spaces

This section develops an elliptical covering argument for bounded subsets of Hilbert spaces. The cover controls approximation through the finite-dimensional range of the accumulated feature operator rather than the ambient Hilbert-space dimension.

  • Overview: The key technical contribution is an elliptical-cover argument that supports non-parametric convergence rates.
  • Theorem C.1: Theorem C.1 constructs a cover C of W whose logarithmic size is bounded by T log(1 + 3B_WB_X/ε).
  • Proof: The proof initializes a regularized operator and uses projection onto the range of M_T to establish the cover properties.
  • Cover construction: The accumulated operator has a range that is a T+1-dimensional object, enabling an ε′-net with a covering-number bound.
  • Interpretation: The resulting cover is based on the finite-dimensional operator range, allowing Hilbert-space arguments without directly covering the full ambient space.

D Concentration Arguments for Special Cases

This section develops concentration and covering results for Hilbert-space and RKHS function classes. These tools bound uniform deviations using elliptical covers, information gain, and bounded feature or parameter norms.

  • RKHS Linear MDPs: RKHS linear MDPs use Hilbert-space features φ:S×A→H and apply an elliptical cover to the feature set Φ.
  • RKHS Linear MDPs: The cover size and approximation guarantee are controlled through T, feature-norm bounds, and parameter-norm bounds rather than an explicit finite feature dimension.
  • Concentration: Uniform concentration holds over all bounded linear predictors under an i.i.d. sample, with deviations expressed through the critical information-gain quantity.
  • Proof strategy: The proofs combine covering arguments, union bounds, approximation between cover elements, and auxiliary concentration and logarithmic-dominance lemmas.
  • RKHS linear functions: The corresponding RKHS transition-feature result applies to ζ:S×A×S→V under bounded norms and gives a uniform sample-dependent guarantee.
  • Generalized Bilinear Classes: The generalized Bilinear Class extension preserves uniform convergence, feasibility, optimism, and high-quality-policy arguments using concavity and Jensen’s inequality.
  • Generalized Bilinear Classes: The analysis uses elliptical-potential and mean-value arguments to control cumulative errors across horizon steps.
  • Auxiliary lemmas: The auxiliary results include Azuma–Hoeffding concentration, a logarithmic-dominance rule, covering numbers, and determinant-trace-based information-gain bounds.

G Sample Complexity Lower Bound for RHKS Bellman Complete and Linear MDP

The section establishes that bounded maximum information gain is necessary for polynomial-sample learning in the RHKS Bellman Complete and Linear MDP setting. A deterministic binary-tree construction yields an exponential lower bound despite bounded feature and hypothesis norms.

  • Motivation: Without bounded maximum information gain, RHKS Bellman Complete and Linear MDP admits an exponential sample-complexity lower bound in horizon H.This supports the necessity of the maximum-information-gain assumption for polynomial guarantees in this setting.
  • Hard instance: The hard instance uses an H-level binary tree with 2^H − 1 states and two actions.States are arranged so level h contains 2^h distinct states.
  • Hard instance: The feature map assigns distinct standard basis vectors to each state-action pair in a d-dimensional space with d = 2|S|.The construction uses V = R^d and includes standard basis vectors in each hypothesis class H_h.
  • Guarantee: The construction satisfies realizability, with both the hypothesis and feature norm bounds at most 1, while transitions and rewards remain deterministic.The theorem states Bellman completeness and bounded norms for the constructed MDP class.
  • Guarantee: Any algorithm achieving value error at most 0.5 with probability at least 0.9 requires Ω(2^H) samples.The lower bound applies to the constructed class of MDPs with 2^H − 1 states and two actions.
Loading 2103.10897v3…