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

Learning in large state-action spaces remains a central reinforcement-learning challenge, motivating structural conditions that capture learnability across models. This paper introduces Bilinear Classes and BiLin-UCB, and establishes sample-efficient learning when both optimal Q and V are linear.

  • Problem

    Learning in large state-action spaces is a central reinforcement-learning challenge, and natural structural conditions for learnability across general RL models remain a research question.

    Source: §1 · pp. 1–2

  • Method

    The paper defines Bilinear Classes through a bilinear structural condition and presents optimization-based BiLin-UCB with a unified analysis based on the elliptical potential lemma.

    Source: §1 · p. 3

  • Results

    Assuming both Q* and V* are linear in given features yields a setting where sample-efficient learning is possible, unlike assuming only Q* is linear.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The framework extends results to infinite-dimensional RKHS models, with non-parametric rates depending on critical information gain.

    Source: §1 · p. 4, §7 · p. 50

    The setup assumes access to a hypothesis class whose hypotheses each have associated state-action value and value functions.

    Source: §4 · p. 9

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 a structural framework for generalization across reinforcement-learning models, motivated by the limits of existing model-specific and general frameworks. It presents a polynomial-sample-complexity algorithm, a reduction to supervised-learning generalization error, and extensions to new models and non-parametric settings.

Our Contributions

  • BiLin-UCB achieves polynomial sample complexity for Bilinear Classes using a unified analysis based on the elliptical potential lemma [Dani et al., 2008, Srinivas et al., 2009].The paper describes the proof as substantially simpler than prior approaches.Source: §1 · p. 3
  • Bilinear Classes bound Bellman error by a hypothesis-dependent bilinear form that can be estimated for all hypotheses from the same dataset, generalizing Bellman rank [Jiang et al., 2017].Reusing data allows the learner to estimate Bellman error simultaneously and eliminate hypotheses with high error.Source: §1 · pp. 2–4
  • The RL sample-complexity result reduces to supervised-learning generalization error without explicit assumptions on the hypothesis class, permitting neural classes in some cases.The Bilinear Class instead posits an implicit relationship between the hypothesis class and the underlying MDP.Source: §1 · p. 4
  • Bilinear Classes include new models such as linear Q*/V* and Low Occupancy Complexity, plus RKHS versions of linear MDPs and linear mixture MDPs.When both Q* and V* are linear in given features, sample-efficient learning is possible, contrasting with the impossibility result when only Q* is linear.Source: §1 · p. 4
  • The framework supports non-parametric RL rates stated in terms of critical information gain, an analogue of the critical radius in non-parametric statistics.The paper develops new analysis tools for this setting, where non-parametric rates for RL are described as rare.Source: §1 · pp. 3–4
  • Simple modifications extend Bilinear Classes to cases outside its strict definition, including Witness Rank and Kernelized Nonlinear Regulator.The introduction describes the framework as flexible and illustrates these extensions in Section 6.Source: §1 · pp. 4–5

2 Related Work: Frameworks and Models

The section compares Bilinear Classes with existing complexity frameworks and surveys which reinforcement-learning models they capture. It emphasizes that Bilinear Classes cover some model-based settings that other frameworks miss, while remaining distinct from Bellman Eluder and Bellman-completeness approaches.

Relations Among Frameworks

  • Bellman Rank yields polynomial-sample-complexity algorithms and covers tabular MDPs, LQR, Reactive POMDPs, Reactive PSRs, Block MDPs, and linear MDPs; its algorithms require finite actions.Witness Rank generalizes Bellman Rank to model-based settings; finite-action requirements also prevent direct application to infinite-action linear MDPs and LQR.Source: §2 · p. 5
  • Low-rank frameworks—Bellman Rank and Witness Rank—and Bellman Completeness do not contain one another; Linear Bellman Complete fits the latter and Bilinear Classes, but not the rank frameworks.Linear Bellman Complete assumes a linear Q-function class closed under the Bellman operator.Source: §2 · pp. 5, 7

Comparison to Bellman Eluder

  • Neither Bellman Eluder nor Bilinear Classes captures the other; Bilinear Classes can capture model-based factored MDPs, KNRs, and linear mixture MDPs even when value functions are highly complex.For factored MDPs, model-free methods such as OLIVE can have exponential worst-case sample complexity, whereas Bilinear Classes and Witness Rank capture their complexity.Source: §2 · p. 6
  • Bellman Eluder applies eluder dimension to Bellman error, whereas Bilinear Classes apply flexible estimators to that error; their complexity measures are equivalent for RKHS, but the frameworks still differ.With Bellman completeness, Jin et al. [2021] obtain faster regret rates; Bilinear Classes and OLIVE do not require that stronger assumption, which excludes models such as linear mixtures.Source: §2 · p. 7

Reinforcement Learning Models

  • Reactive POMDPs, Block MDPs, Reactive PSRs, and FLAMBE admit low-rank structure and can be incorporated into Bellman Rank, Witness Rank, and Bilinear Classes.Their assumptions include small hidden-state spaces, decodable hidden states for Block MDPs, observable grounding for Reactive PSRs, and feature selection without known features for FLAMBE.Source: §2 · p. 7
  • Linear MDPs belong to all frameworks, while linear mixture MDPs fit only Bilinear Classes among those discussed; Bellman Rank and Witness Rank algorithms cannot handle infinite action sets directly.LQR has low Bellman and Witness Rank but uncountable actions prevent those algorithms from incorporating it; Q*-only linearity has an exponential lower bound absent near-determinism and a large suboptimality gap.Source: §2 · pp. 7–8

3 Setting

The section formalizes an episodic, finite-horizon, non-stationary MDP and the policy and value-function notation used throughout. The setup uses a fixed initial state, with results generalizing to any fixed initial-state distribution.

3 Setting

  • The setting is an episodic finite-horizon, non-stationary MDP with bounded expected rewards, transition kernels, and observed transition information recorded at each timestep.The observed tuple is (r_h, s_h, a_h, s_{h+1}).Source: §3 · p. 8
  • The analysis fixes an initial state, and the results generalize to any fixed initial-state distribution.Source: §3 · p. 8
  • A deterministic stationary policy maps states to actions, while a non-stationary policy is a sequence of stationary policies; Q- and value-functions are defined for policies, with starred notation for the optimal policy.Source: §3 · pp. 8–9

4 Bilinear Classes

Bilinear Classes provide a general framework for value-based and model-based hypotheses, covering finite Bellman-rank methods and several known and newly proposed RL models. The framework supports data reuse for estimation and includes models whose feature spaces may be infinite-dimensional.

4.2 Bilinear Classes

  • Bilinear Classes allow value- or model-based hypothesis sets with associated Q and V functions, require realizability, and enable estimation without knowing the framework’s W and X functions.The definition’s second property lets data collected under one hypothesis estimate bilinear forms for other hypotheses, supporting data reuse across the class.Source: §4 · p. 9, §4.2 · p. 12

4.1 Warmup: Bellman rank, the Q and V versions.

  • The framework covers both Q- and V-Bellman rank, extending Jiang et al. [2017]’s finite-dimensional treatment to infinite-dimensional hypothesis classes.The Q version enforces Bellman consistency of state-action values, while the V version enforces consistency of value functions.Source: §4.1 · p. 11

4.2.1 Finite Bellman rank =⇒Bilinear Class

  • Finite Q-Bellman rank with on-policy estimation and finite V-Bellman rank with uniform-action estimation each imply a Bilinear Class.The framework thus captures both Bellman-rank variants under their respective estimation-policy choices.Source: §4.2.1 · p. 13

4.3 Examples

  • The examples include known Linear Bellman Complete and Linear Mixture models, plus the new Linear Q⋆/V⋆ and Low Occupancy Complexity models.The paper returns to these examples for non-parametric sample-complexity results in Section 5.3.Source: §4.3 · p. 13

4.3.1 Linear Mixture MDP.

  • A Linear Mixture MDP is a Bilinear Class under its specified discrepancy function and on-policy estimation.The model uses known features and an unknown parameter in a Hilbert space to represent transitions and rewards.Source: §4.3.1 · p. 14

4.3.2 Linear Q⋆/V ⋆(new model)

  • The new Linear Q⋆/V⋆ model assumes both optimal value functions are linear in known features, possibly in infinite-dimensional Hilbert spaces, and is a Bilinear Class.Its result uses the specified discrepancy function and on-policy estimation.Source: §4.3.2 · pp. 15–16

4.3.3 Bellman Complete and Linear MDPs

  • Linear Bellman Completeness with respect to an MDP implies a Bilinear Class, capturing the linear MDP model.The hypothesis class consists of linear functions over known features and must be realizable.Source: §4.3.3 · pp. 16–17

4.3.4 Low Occupancy Complexity (new model).

  • Low Occupancy Complexity yields a Bilinear Class while requiring only realizability, allowing otherwise arbitrary hypothesis classes, including neural state-action value classes.The feature mapping and coefficients may be unknown to the algorithm; a state-only low-occupancy variant uses uniform-action estimation.Source: §4.3.4 · pp. 17–18

5 The Algorithm and Theory

The section presents BiLin-UCB, which iteratively restricts a version space with collected batch data and optimistically selects a feasible hypothesis. It develops guarantees that reduce reinforcement-learning sample complexity to supervised generalization error and provide finite-dimensional and RKHS bounds across Linear Q*/V* and other specified model settings.

5 The Algorithm and Theory

  • BiLin-UCB refines its version space with constraints from prior batch data, then optimistically chooses a feasible hypothesis maximizing total reward.When estimation and fitting policies differ, batches can be collected by rolling in with the fitting policy and sampling the action at each timestep from the estimation policy.Source: §5 · p. 19

5.1 Main Theory: Generalization in Bilinear Classes

  • Under Assumption 5.1, Theorem 5.1 states that Algorithm 1 uses at most mHT trajectories in the finite-dimensional case, while Theorem 5.2 gives at most mH edm trajectories in the RKHS case.Source: §5.1 · pp. 20, 22

5.2 Proof of Theorem 5.1 and Theorem 5.2

  • Uniform convergence makes the optimal hypothesis feasible and guarantees optimism; an elliptical-potential argument then ensures an iteration has low regret.The proof uses the bilinear regret lemma and bounds the sum of bilinear forms across iterations to establish a high-quality policy.Source: §5.2 · pp. 24, 25, 26, 28

5.3 Corollaries for Particular Models

  • The framework applies to linear Q*/V*, RKHS Bellman-complete and linear-mixture models, and low occupancy-complexity models, extending linear Bellman-complete and linear-mixture results to RKHS settings.The paper notes that information gain can remain small even for infinite-dimensional RKHS feature sets.Source: §5.1 · p. 22, §5.3 · p. 28

5.3.1 Linear Q⋆/V ⋆

  • For linear Q*/V* models, the paper gives both finite-dimensional and RKHS sample-complexity guarantees, with the latter using critical information gain rather than explicit feature dimension.The finite-dimensional corollary assumes bounded feature and parameter norms; the RKHS corollary bounds trajectories by mH times critical information gain.Source: §5.3.1 · p. 29
  • The Linear Q⋆/V⋆ proof completion uses on-policy estimation, yielding trajectory complexity mT.The passage states π_est = π_ft for all t.Source: §5.3.1 · p. 32

5.3.2 RKHS Bellman Complete.

  • For finite-dimensional Bellman completeness, Corollary 5.4 guarantees an ε-optimal policy with probability at least 1−δ using the stated trajectory bound.The corollary assumes a Hilbert space V ⊂ R^d and bounded parameter and feature norms.Source: §5.3.2 · p. 32
  • For RKHS Bellman completeness, Algorithm 1 uses at most mH edm(X) trajectories and returns a hypothesis f with probability at least 1−δ.The result is stated for a Hilbert space V with bounds on the hypothesis parameters and feature norms.Source: §5.3.2 · p. 33

5.3.3 RKHS linear mixture model

  • For the finite-dimensional linear mixture model, Corollary 5.6 guarantees an ε-optimal policy with probability at least 1−δ using the stated trajectory bound.The corollary assumes a Hilbert space V ⊂ R^d and bounded parameter and feature norms.Source: §5.3.3 · p. 35
  • For the RKHS linear mixture model, Algorithm 1 uses at most mH edm(X) trajectories and returns a hypothesis f with probability greater than 1−δ.The corollary assumes bounded hypothesis parameters and feature norms.Source: §5.3.3 · pp. 35–36

5.3.4 Low Occupancy Complexity

  • Under low occupancy complexity, Algorithm 1 uses at most mH edm(X) trajectories and returns a hypothesis f.The corollary assumes a bound on the occupancy-weighted hypothesis norms and states a further condition on f.Source: §5.3.4 · p. 37

5.3.5 Finite Bellman Rank

  • For finite Bellman rank d, Corollary 5.9 guarantees an ε-optimal policy with probability at least 1−δ using the stated trajectory bound.The corollary assumes bounded occupancy-weighted hypothesis norms and bounded X_h(f).Source: §5.3.5 · pp. 38–39

6 Extended Bilinear Classes

Section 6 extends Bilinear Classes through a generalized definition and shows that it encompasses KNR, generalized linear Bellman completeness, finite Witness Rank, and factored MDPs.

6 Extended Bilinear Classes

  • Generalized Bilinear Classes add nonlinear transformations and discriminator classes; the algorithm achieves a regret bound under Assumptions 6.1–6.2 linked to supervised-style generalization.Source: §6 · pp. 41–42

6.1 Kernelized Nonlinear Regulator (KNR)

  • KNR [Kakade et al., 2020] is captured as a Generalized Bilinear Class with on-policy estimation, although Bellman rank and Witness Rank do not directly capture it.Source: §6.1 · p. 43

6.2 Generalized Linear Bellman Complete

  • Under a nondecreasing inverse link with bounded slope, generalized linear Bellman completeness is captured by Definition 6.1.Source: §6.2 · pp. 45, 47

6.3 Witness Rank

6.3.1 Factored MDP

  • In factored MDPs, constant-size parent sets can make transition complexity exponentially smaller than |O|^d, and the model is captured by Definition 6.1.Source: §6.3.1 · pp. 49–50

7 Conclusion · A Additional Examples of Bilinear Classes · A.1 FLAMBE / Feature Selection

The paper presents Bilinear Classes and BiLin-UCB as a shared framework and algorithm for analyzing learnable RL models, with extensions to new models and infinite-dimensional settings. Its appendix illustrates the framework with a feature-selection model whose unknown features are assumed realizable in a function class.

7 Conclusion

  • Bilinear Classes and BiLin-UCB let many learnable RL models be analyzed with the same algorithm and proof.The paper presents the framework together with a sample-efficient algorithm.Source: §7 · p. 50
  • The framework introduces linear Q⋆/V⋆, RKHS Bellman complete, RKHS linear mixture, and low occupancy complexity models, and extends prior finite-dimensional results to RKHS settings using critical information gain.The rates are described as non-parametric and depend on critical information gain, an analog of the critical radius in non-parametric statistics.Source: §7 · p. 50
  • Bilinear Classes can be extended to cover Witness Rank and Kernelized Nonlinear Regulator, and the paper suggests future models may also admit such extensions.The appendix introduces additional Bilinear Class examples, including feature selection.Source: §7 · p. 50, A Additional Examples of Bilinear… · p. 58

A Additional Examples of Bilinear Classes

  • The appendix considers Agarwal et al. [2020b] feature selection, a low-rank model with unknown features φ⋆ represented by a realizable class Φ, unlike linear MDPs where φ⋆ is known.The model uses unknown functions and features in a Hilbert space.Source: §A.1 · p. 58

A.1 FLAMBE / Feature Selection

  • Because φ⋆ belongs to Φ and the optimal Q-function is linear in φ⋆(s, a), the appendix places the optimal Q-function in its hypothesis class H.The passage defines H to capture Q⋆.Source: §A.1 · p. 58
  • For the low-rank feature-selection model, the specified hypothesis class, discrepancy, and uniform-random-action estimation policies form an implicit Bilinear Class.Lemma A.1 establishes this result.Source: §A.1 · p. 58

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

The appendix shows that the Q⋆irrelevance aggregation model can be represented as a linear Q⋆/V⋆ model, making it an implicit Bilinear Class. The setup uses a known state mapping and a linear hypothesis class.

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

  • The model is defined using a known mapping ζ from states to V.The supplied definition passage ends before stating the condition on pairs of states.Source: §A.2 · p. 59
  • The hypothesis class is specified as a set of linear functions over the mapped state set Z = {ζ(s) : s ∈ S}.Source: §A.2 · p. 59
  • The Q⋆irrelevance aggregation model is an implicit Bilinear Class under the stated hypothesis class, discrepancy, and on-policy estimation policies.The proof reduces the model to a linear Q⋆/V⋆ model, which is a Bilinear Class.Source: §A.2 · p. 60

A.3 Linear Quadratic Regulator

The subsection establishes finite-horizon discrete-time LQRs as Bilinear Classes using a hypothesis class, discrepancy function, and on-policy estimation policies. It also notes that non-stationary linear policies induce quadratic value functions and that the algorithm avoids dependence on the number of actions.

A.3 Linear Quadratic Regulator

  • Unlike Jiang et al. [2017], whose small-bellman-rank algorithm has action-dependent sample complexity, this algorithm has no dependence on the number of actions.The setting takes S ⊂ R^d and A ⊂ R^K.Source: §A.3 · p. 60
  • The LQR definition uses unknown matrices A ∈ R^{d×d}, B ∈ R^{d×K}, and Q ∈ R^{d×d} to specify transitions and rewards in a finite-horizon discrete-time MDP.Source: §A.3 · p. 60
  • For non-stationary linear policies, the induced value function is quadratic.The policy has the form π_h(s_h) = C_{π,h}x; the subsection assumes s_0 = 0 and a_0 = 0.Source: §A.3 · p. 61
  • For LQRs, the specified hypothesis class, discrepancy function, and on-policy estimation policies form an (implicitly) Bilinear Class.The proof establishes a stronger equality version of Equation (2), which also proves Equation (1).Source: §A.3 · p. 61

A.4 Linear MDP · A.5 Block MDP and Reactive POMDP

The sections characterize Linear MDPs, Block MDPs, and Reactive POMDPs through assumptions that place them within the Bilinear Class framework. They specify how linear features, context decoding, and reactive value functions establish that connection.

A.4 Linear MDP

  • In a Linear MDP, unknown transition measures and reward parameters represent transitions and rewards as inner products with known Hilbert-space features.The transition distribution is P_h(· | s, a) = ⟨φ(s, a), μ_h(·)⟩, and the reward is r_h(s, a) = ⟨φ(s, a), θ_h⟩.Source: §A.4 · p. 62
  • The linear hypothesis class satisfies Bellman completeness and therefore is a Bilinear Class, as observed in Jin et al. [2020][Proposition 2.3].Its hypotheses are tuples (θ_0, …, θ_{H−1}) with each θ_h in the feature space V.Source: §A.4 · p. 62

A.5 Block MDP and Reactive POMDP

  • Block MDPs and Reactive POMDPs share a partially observable setup with finite latent states and actions, observable contexts, and distinct assumptions.The setup uses latent-state transitions and a context-emission function; the sections then define the models’ differing assumptions.Source: §A.5 · pp. 62–63
  • In a Block MDP, context space partitions into disjoint blocks, each containing the support of the emission distribution for its corresponding latent state.This partition yields a perfect decoder from contexts to their generating states.Source: §A.5 · p. 63
  • Block MDPs are a subclass of FLAMBE and thus belong to the Bilinear Class framework.The construction uses one-hot vectors for decoded contexts and latent-state transition probabilities as features in a |S|-dimensional Euclidean space.Source: §A.5 · p. 63
  • For a POMDP with known deterministic rewards in [0, 1], beliefs are posteriors over latent states, updated deterministically by Bayes’ rule from the current belief, action, and next observation.The initial belief is proportional to the initial state distribution times the observation-emission probability, and the optimal policy maps beliefs to actions.Source: §A.5 · pp. 63–64
  • Reactive POMDPs have optimal Q-functions dependent only on the latest observation and action; their Bellman rank is bounded by |S|, placing them in the Bilinear Class.The Bellman-rank result is attributed to Jiang et al. [2017].Source: §A.5 · p. 64

B Proofs for Section 5

The proof of Corollary 5.1 uses a high-probability sample guarantee to meet Assumption 5.1, apply Theorem 5.1, and derive a trajectory complexity for an ε-optimal policy.

B Proofs for Section 5

  • Lemma F.1 provides a 1 − δ probability guarantee for an i.i.d. sample of size m, uniformly over all g ∈ H and any distribution µ over S × A × S.The guarantee is stated for every δ ∈ (0, 1).Source: B Proofs for Section 5 · p. 64
  • The proof uses this bound to satisfy Assumption 5.1 and then applies Theorem 5.1.The passage sequence gives the assumption check before the theorem application.Source: B Proofs for Section 5 · p. 64
  • The proof derives total trajectory complexity by choosing the sample size m to obtain an ε-optimal policy.The passages state that the policy guarantee follows from a lower bound on m, then give the resulting total trajectory complexity.Source: B Proofs for Section 5 · p. 65

C An Elliptical Cover for Hilbert Spaces

The section presents an elliptical cover theorem for bounded vectors and Hilbert-space parameters, a technical contribution that supports non-parametric convergence rates.

C An Elliptical Cover for Hilbert Spaces

  • For X in a Hilbert space with norm bounded by B_X and W within a radius-B_W ball, Theorem C.1 constructs a cover C with log |C| ≤ T log(1 + 3B_W B_X T/epsilon).The theorem also asserts that every w in W has a representative w' in C satisfying an inner-product approximation condition.Source: C An Elliptical Cover for Hilbert Spaces · pp. 65, 67
  • The proof builds an epsilon'-net on Range(M_T), a T+1-dimensional space, and uses a standard covering-number bound to control its size.The proof begins with a regularized operator Σ_0 = λI.Source: C An Elliptical Cover for Hilbert Spaces · pp. 65–66

D Concentration Arguments for Special Cases · E Generalized Bilinear Classes · F Auxiliary Lemmas

Appendices D–F give RKHS concentration results, extend the generalized-bilinear theorem proof, and collect auxiliary concentration and information-gain lemmas.

D Concentration Arguments for Special Cases

E Generalized Bilinear Classes

  • The generalized-bilinear proof establishes uniform convergence and feasibility, yielding optimism, and uses concavity of ξ with Jensen’s inequality in its derivation.Source: E Generalized Bilinear Classes · p. 70
  • The proof also establishes existence of a high-quality policy using an elliptical-potential argument and combines that result with Equation (13).Source: E Generalized Bilinear Classes · p. 70

F Auxiliary Lemmas

  • The auxiliary lemmas provide Azuma–Hoeffding concentration, a log-dominance rule, and maximum and critical information-gain bounds; the concentration proof applies Lemma F.1 with a union bound.Source: F Auxiliary Lemmas · pp. 72–73

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

Although bounded maximum information gain enables polynomial sample complexity for RHKS Bellman Complete and Linear MDP, removing that assumption permits an exponential-in-horizon lower bound. The construction shows why bounded maximum information gain is necessary in this setting.

Hard instance

  • The hard instance is a binary tree with H levels, where only one special state-action pair at the final level yields reward 1.Prior hardness results for this construction are attributed to Du et al. [2020a] and Krishnamurthy et al. [2016].Source: G Sample Complexity Lower Bound for… · p. 74

Feature construction

  • The construction assigns standard-basis features and a hypothesis class containing Q*, ensuring realizability while keeping both feature and hypothesis norms bounded by 1.The feature space has dimension d = 2|S|, and the class at each level consists of the standard basis vectors.Source: G Sample Complexity Lower Bound for… · p. 74

Theorem G.1

  • Any algorithm needs Ω(2^H) samples to achieve 0.5 optimality gap with probability at least 0.9 on the constructed MDPs.Theorem G.1 uses Bellman-complete classes with unit-bounded hypothesis and feature norms; transitions and rewards are deterministic, with 2^H − 1 states and two actions.Source: G Sample Complexity Lower Bound for… · p. 74

Related papers

Loading 2103.10897v3…