PaperlayerView exact revision on arXiv

Source-linked AI summary

Is Pessimism Provably Efficient for Offline RL?

Ying Jin, Zhuoran Yang, Zhaoran Wang

arXiv:2012.15085v3cs.LGcs.AImath.OCmath.STstat.ML

TL;DR

Offline RL lacks a provably efficient theory when datasets provide insufficient coverage. This paper proposes pessimistic value iteration (PEVI) and proves minimax optimality for linear MDPs up to dimension and horizon factors.

  • Problem

    Offline RL remains theoretically underdeveloped when active environment interactions are infeasible, motivating the question of provably efficient learning.

    Source: §1 · pp. 1–2

  • Method

    PEVI adds an uncertainty-quantifying penalty to value iteration by reversing the exploration bonus used in online RL.

    Source: §1 · p. 2

  • Results

    PEVI is minimax optimal for linear MDPs up to multiplicative factors of dimension and horizon, with suboptimality depending on coverage of the optimal-policy trajectory.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Pessimism eliminates spurious correlation from PEVI’s suboptimality and yields an oracle property focused on information relevant to the optimal policy.

    Source: §1 · p. 2

    The analysis assumes bounded rewards and does not restrict affinity between the learned and behavior policies.

    Source: §1 · p. 3, §2.1 · p. 4

Abstract

from arXiv · show

We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a dataset collected a priori. Due to the lack of further interactions with the environment, offline RL suffers from the insufficient coverage of the dataset, which eludes most existing theoretical analysis. In this paper, we propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function. Such a penalty function simply flips the sign of the bonus function for promoting exploration in online RL, which makes it easily implementable and compatible with general function approximators. Without assuming the sufficient coverage of the dataset, we establish a data-dependent upper bound on the suboptimality of PEVI for general Markov decision processes (MDPs). When specialized to linear MDPs, it matches the information-theoretic lower bound up to multiplicative factors of the dimension and horizon. In other words, pessimism is not only provably efficient but also minimax optimal. In particular, given the dataset, the learned policy serves as the "best effort" among all policies, as no other policies can do better. Our theoretical analysis identifies the critical role of pessimism in eliminating a notion of spurious correlation, which emerges from the "irrelevant" trajectories that are less covered by the dataset and not informative for the optimal policy.

1 Introduction

The paper studies offline RL under insufficient dataset coverage, where uncertainty and spurious correlation can mislead policy learning without further environment interaction. It proposes pessimistic value iteration and shows that uncertainty-based pessimism removes spurious correlation and is minimax optimal for linear MDPs up to dimension and horizon factors.

1 Introduction

  • Offline RL learns from a pre-collected dataset without further interaction, addressing the high sample cost and risk of online data collection in domains such as medicine and autonomous driving.Online deep RL may require millions to billions of environment interactions, while offline datasets include electronic health records and human driving trajectories.Source: §1 · p. 1
  • Insufficient coverage creates intrinsic uncertainty about optimal-policy trajectories and spurious correlation from poorly related trajectories that happen to appear rewarding.Because the dataset is collected a priori, sufficient-coverage assumptions may fail in practice.Source: §1 · p. 2
  • PEVI adds a pessimistic penalty to value iteration by flipping the sign of an exploration bonus, and uncertainty-quantifier penalties eliminate spurious correlation from suboptimality in general MDPs.The paper decomposes suboptimality into intrinsic uncertainty, spurious correlation, and optimization error, identifying spurious correlation even in multi-armed bandits.Source: §1 · p. 2
  • For linear MDPs, PEVI’s instantiated penalty satisfies the uncertainty-quantifier condition, yielding minimax optimality up to multiplicative factors of dimension and horizon.The intrinsic uncertainty cannot be eliminated because it is reflected in the information-theoretic lower bound.Source: §1 · p. 2
  • PEVI has an oracle property: its suboptimality depends on coverage of the optimal-policy trajectory rather than unrelated trajectories, while requiring only dataset compliance and no sufficient-coverage or behavior-affinity assumptions.Thus, given the dataset, the learned policy is a best effort because no other policy can do better under the stated limit.Source: §1 · pp. 2–3

1.1 Related Works

  • Related offline-RL methods use policy regularization or value penalties to address distribution shift and extrapolation error, but existing theory commonly assumes sufficient coverage that often fails in practice.The paper instead provides a principled uncertainty-quantifier framework without restricting affinity between learned and behavior policies, complementing prior pessimism work.Source: §1.1 · pp. 3–4

2 Preliminaries

This section defines the episodic MDP setting and policy suboptimality metric, then formalizes offline datasets collected a priori under a compliance condition that permits broad, non-exploratory data-collection processes.

2.1 Episodic MDP and Performance Metric

  • An episodic MDP has bounded rewards, horizon H, transition dynamics, and policies evaluated by expected cumulative reward and suboptimality from initial state x.The optimal policy, Q-function, and value function provide the corresponding benchmarks.Source: §2.1 · pp. 4–5

2.2 Offline Data Collecting Process

  • The offline learner receives K trajectories collected a priori, with actions chosen by an experimenter and rewards and transitions generated by an underlying MDP.Dataset compliance requires the collecting process to preserve the underlying MDP’s reward and transition structure while allowing trajectories to be interdependent.Source: §2.2 · p. 5
  • The compliance assumption permits fixed, adaptive, or adversarial behavior and does not require the dataset to explore the state-action space well.Actions may be interdependent across trajectories, including when the experimenter sequentially improves the behavior policy using online RL.Source: §2.2 · p. 6

3 What Causes Suboptimality?

The section decomposes policy suboptimality into spurious correlation, intrinsic uncertainty, and optimization error. It shows that dataset-dependent spurious correlation can cause substantial error, including in multi-armed bandits with uneven coverage, whereas intrinsic uncertainty is unavoidable and greedy optimization error is nonpositive.

3 What Causes Suboptimality?

  • Suboptimality decomposes into spurious correlation, intrinsic uncertainty, and optimization error, with the terms evaluated along learned and optimal policy trajectories.The decomposition applies to general MDPs and is then specialized to the multi-armed bandit setting.Source: §3 · p. 6, §3.1 · p. 6

3.1 Spurious Correlation Versus Intrinsic Uncertainty

  • Spurious correlation can make the learned policy select actions with large estimation errors, causing significant suboptimality even when the estimator is unbiased.The issue arises because both the learned policy and model evaluation error depend on the dataset; intrinsic uncertainty is unavoidable by information-theoretic lower bounds, while greedy optimization error is nonpositive.Source: §3.1 · pp. 6–7

3.2 Illustration via a Special Case: MAB

  • In the MAB, uneven action coverage can produce a large maximum estimation error, causing a greedy policy to choose an under-sampled action despite its low true reward.For an action with small count N(a), its sample-average estimate can be spuriously large; the problem becomes more severe in general MDPs because state-action coverage is harder to ensure.Source: §3.2 · p. 8

4 Pessimism is Provably Efficient

This section establishes data-dependent efficiency and minimax optimality for pessimistic value iteration, including guarantees for linear MDPs and extensions to RKHS function approximation. The analyses relate performance to trajectory coverage, dataset-dependent information, and effective dimension while avoiding uniform coverage and covering-number dependence.

4 Pessimism is Provably Efficient

  • PEVI flips the online-RL exploration bonus into a penalty and uses an uncertainty quantifier to construct pessimistic value iteration for general MDPs.The section develops a sufficient condition for eliminating spurious correlation and then specializes the analysis to linear MDPs.Source: §4 · p. 8, §4.1 · p. 9

4.1 Pessimistic Value Iteration: General MDP

  • For general MDPs, a valid uncertainty quantifier makes the penalty eliminate spurious correlation pointwise, leaving only intrinsic uncertainty in PEVI’s suboptimality.The guarantee holds on an event with probability at least 1−ξ and requires the uncertainty quantifier to control Bellman-operator approximation error.Source: §4.1 · pp. 9–10

4.2 Pessimistic Value Iteration: Linear MDP

  • In linear MDPs, PEVI requires neither uniform coverage nor affinity to a behavior policy, while its suboptimality depends only on intrinsic uncertainty along the optimal trajectory.The resulting oracle property ignores coverage of off-trajectory state-action pairs and adapts to the unknown support of the optimal trajectory.Source: §4.2 · p. 11
  • When the optimal trajectory is sufficiently covered, PEVI’s suboptimality decays at a K^-1/2 rate; in tabular MDPs, off-trajectory coverage does not affect this bound.This oracle behavior can let PEVI outperform a demonstration policy whose dataset covers irrelevant state-action pairs more heavily than the optimal trajectory.Source: §4.2 · pp. 12–14
  • The linear-MDP intrinsic-uncertainty term admits an information-gain interpretation: it measures uncertainty about the regression parameter removed by observing optimal-trajectory features.This connects the suboptimality bound to conditional mutual information between the parameter given the dataset and optimal-trajectory features.Source: §4.2 · pp. 12–13
  • As K →∞, PEVI’s suboptimality in linear MDPs vanishes at the H^2K^−1/2 scale, matching the offline policy-evaluation lower-bound rate.The result concerns offline policy optimization, which is more challenging than policy evaluation.Source: §4.2 · p. 14

4.3 Minimax Optimality: Information-Theoretic Lower Bound

  • Theorem 4.7 matches Theorem 4.4 up to β and absolute constants, establishing minimax optimality for linear MDPs; Proposition C.2 further gives local optimality on worst-case MDPs.The lower bound is formulated for any algorithm’s output on a compliant dataset.Source: §4.3 · p. 15

4.4 Pessimistic Value Iteration: Reproducing Kernel Hilbert Spaces

  • PEVI extends from linear models to kernel function approximation through RKHSs, with finite-spectrum kernels recovering the linear setting as a special case.The RKHS formulation uses a kernel feature map and supports infinite-dimensional function classes.Source: §4.4 · p. 15, §4.4.1 · p. 16

4.4.2 Pessimistic Value Iteration for Kernel Function Approximation with Data Splitting

  • Data splitting assigns distinct reverse-ordered trajectory folds to value iteration steps, removing statistical dependence and avoiding covering-number dependence in the uncertainty analysis.For linear function approximation, the resulting choice is β = e O(√dH) instead of β = e O(dH).Source: §4.4.2 · p. 16, Figure 3 · p. 17
  • Theorem 4.9 decomposes RKHS suboptimality into a kernel-class parameter B and a dataset- and optimal-policy-dependent information quantity, with pessimism eliminating spurious correlation.For finite-spectrum RKHSs, the information quantity reduces to the linear-setting expression with data splitting.Source: §4.4.2 · p. 18
  • With γ-finite spectrum, data splitting improves the upper-bound parameter from e O(γH) to e O(√γH), while its sample-size cost adds a factor H.Thus splitting is favorable when H is smaller than γ, or more generally when the kernel class’s covering number exceeds exp(H).Source: §4.4.2 · p. 19
  • For i.i.d. behavior-policy trajectories, the suboptimality depends on the effective dimension relating behavior-policy and optimal-policy feature covariances; when d_eff ≈ e O(H^3/2K^1/2), it is K^−1/2 under finite or exponential spectral decay and K^(κ*−1/2) under polynomial decay.The polynomial-decay result additionally assumes γ(1 −2τ) > 1.Source: §4.4.2 · p. 20

5 Proof Sketch

The proof sketch establishes PEVI’s pessimistic estimation for general MDPs, specializes the argument to linear MDPs, and proves minimax optimality through a Le Cam lower-bound construction.

5.1 Suboptimality of PEVI: General MDP

  • Under event E with probability at least 1 −ξ, PEVI’s uncertainty quantifiers satisfy 0 ≤ι_h(x, a) ≤2Γ_h(x, a) pointwise.This bound makes the constructed Q-functions pessimistic estimators of the optimal Q-functions and controls their underestimation bias.Source: §5.1 · p. 21
  • The general-MDP proof applies a performance decomposition to PEVI’s greedy policy, where pessimism bounds spurious correlation and intrinsic uncertainty terms.The resulting inequality holds under E, whose probability is at least 1 −ξ.Source: §5.1 · p. 21

5.2 Suboptimality of PEVI: Linear MDP

  • For linear MDPs, properly chosen regularization and scaling parameters make Algorithm 2’s bonuses ξ-uncertainty quantifiers, allowing Theorem 4.2 to specialize to Theorem 4.4.The specialization is concluded under event E with probability at least 1 −ξ.Source: §5.2 · p. 22

5.3.1 Construction of a Hard Instance

  • The hard-instance construction uses a class of linear MDPs with three states, at least three actions, absorbing successor states, and dimension d = A + 2.The dataset consists of K trajectories from the same initial state, with arbitrary later actions that do not affect transitions, and remains compliant with the linear MDP.Source: §5.3.1 · pp. 22–24

5.3.2 Information-Theoretic Lower Bound

  • The lower-bound proof constructs two hard-to-distinguish linear MDPs whose optimal initial actions differ, so no dataset-based policy can be simultaneously near-optimal for both.Le Cam’s method reduces policy learning to hypothesis testing and yields Theorem 4.7’s information-theoretic lower bound.Source: §5.3.2 · pp. 24–25

A Proofs of Suboptimality Decomposition · B Proofs of Pessimistic Value Iteration

The appendix decomposes the learned policy’s suboptimality into estimated-value discrepancies and bounds those terms using an extended value-difference lemma. The supplied passages specify applications to the optimal and learned policies, with expectations taken over their induced trajectories.

A Proofs of Suboptimality Decomposition

B.1 Proof of Lemma 5.1

On event E, the model evaluation errors ι_h are nonnegative and bounded above by twice the uncertainty penalty Γ_h. The proof derives these bounds by considering the sign of Q_h and using the clipped nonnegative estimate bQ_h.

B.1 Proof of Lemma 5.1

  • On event E, ι_h(x, a) ≥ 0 for every h and (x, a), whether Q_h(x, a) is negative or nonnegative.For Q_h < 0, nonnegativity follows from nonnegative rewards and bV_{h+1}; for Q_h ≥ 0, it follows from event E and the penalty Γ_h.Source: §B.1 · p. 33
  • On event E, ι_h(x, a) ≤ 2Γ_h(x, a) for every h and (x, a), establishing the upper bound in Lemma 5.1.The construction gives Q_h(x, a) ≤ H − h + 1, while clipping ensures bQ_h(x, a) ≥ Q_h(x, a), yielding the stated error bound.Source: §B.1 · p. 33

B.2 Proof of Lemma 5.2

The proof establishes that, under Assumption 2.2, PEVI’s uncertainty quantifiers bound the Bellman estimation error uniformly with probability at least 1−ξ. It does so by exploiting linear MDP structure, bounded value-function weights, and uniform self-normalized concentration over an ε-cover.

Proof of Lemma 5.2

  • Under Assumption 2.2, the event E holds with probability at least 1−ξ when Γ_h are chosen as the ξ-uncertainty quantifiers.The proof concludes that the quantities defined in Equation (4.7) satisfy the required uncertainty guarantee uniformly over all h, states, and actions.Source: §B.2 · pp. 33, 40
  • Linearity of transitions and rewards implies (B_h bV_h+1)(x,a)=φ(x,a)⊤w_h for every h, state, and action.This representation converts the Bellman estimation problem into bounding linear prediction errors in the feature map.Source: §B.2 · p. 34
  • Lemma B.1 bounds the norms of the true and estimated Bellman weights using the value-function range and Λ_h ⪰ λ·I.These norm bounds control one component of the difference between B_h bV_h+1 and bB_h bV_h+1.Source: §B.2 · pp. 34–35
  • Uniform concentration handles the data-dependent bV_h+1 by covering its function class with an ε-net and applying self-normalized concentration to each fixed cover function.The proof uses that bV_h+1 belongs to the relevant function class, then combines Lemma B.2, a union bound, and covering-number control.Source: §B.2 · pp. 36–39
  • Choosing ε=dH/K and λ=1, the covering-number bound completes the uniform Bellman-error bound needed to certify {Γ_h}^H_{h=1}.The covering argument controls the logarithmic complexity of the value-function class and yields the final high-probability guarantee.Source: §B.2 · pp. 39–40

B.3 Proof of Corollary 4.5

The proof combines concentration events with norm and eigenvalue bounds to establish Corollary 4.5. A rank constraint on the covariance matrices yields the refined conclusion in Equation (4.11).

B.3 Proof of Corollary 4.5

  • On E† ∩ E‡, Cauchy–Schwarz, Jensen’s inequality, and λh,j(x) ∈ [0, 1] control the relevant eigenvalue-based quantity using Corollary 4.5’s scaling choice β > 0.The bounded feature norm ∥φ(s, a)∥ ≤ 1 is also used in the Jensen step.Source: §B.3 · p. 41
  • The intersection event E† ∩ E‡ has probability at least 1 − ξ by combining two 1 − ξ/2 probability guarantees with a union bound.This high-probability event yields Equation (4.10).Source: §B.3 · p. 41
  • If rank(Σh(x)) ≤ r for every x and h, the same event yields the rank-dependent bound in Equation (4.11).The refinement uses λh,j(x) ∈ [0, 1], the rank restriction, and Corollary 4.5’s choice of β.Source: §B.3 · p. 41

B.4 Proof of Corollary 4.6 · C Proofs of Minimax Optimality

The proof of Corollary 4.6 establishes high-probability concentration for the centered, independent trajectory-derived matrices and combines this event with the theorem’s event via a union bound. Under sufficiently large K and the covariance lower bound, the conclusion holds with probability at least 1 − ξ.

B.4 Proof of Corollary 4.6

  • The K dataset trajectories yield independent, centered random matrices for every stage h.This follows because trajectories are i.i.d. under the fixed behavior policy and the relevant matrices have zero expectation.Source: §B.4 · p. 42
  • Applying Lemma E.1 produces a concentration bound for each fixed stage h.The argument applies the matrix concentration lemma to Z_h and then controls all stages using a union bound.Source: §B.4 · p. 42
  • With probability at least 1 − ξ/2, the concentration event holds simultaneously over all h.The probability is taken with respect to the dataset distribution P_D.Source: §B.4 · p. 43
  • The covariance condition λ_min(Σ_h) ≥ c/d implies ||Σ_h^-1||_op ≤ d/c, enabling the required inverse-covariance control.This condition is combined with the preceding concentration inequalities when K is sufficiently large.Source: §B.4 · p. 43
  • For K ≥ 40d/c · log(4dH/ξ), the covariance-control event holds with probability at least 1 − ξ/2.The proof derives this event from the concentration estimates and the inverse-covariance bound.Source: §B.4 · p. 43
  • Intersecting the covariance-control event with the event from Theorem 4.4 yields the corollary with probability at least 1 − ξ.The final probability follows by a union bound on the two events, under sufficiently large K.Source: §B.4 · p. 43

C.1 Proof of Lemma 5.3 · C.2 Suboptimality of PEVI on M

The appendix proves Lemma 5.3 by contrasting two linear MDPs with different optimal first-step actions, then establishes PEVI’s suboptimality on the broader class M under specified regularization, confidence, and sample-size conditions.

C.1 Proof of Lemma 5.3

  • C.1 considers M1 = M(p∗, p, p) and M2 = M(p, p∗, p), where p∗ > p makes b1 optimal in M1 and b2 optimal in M2.Thus the two environments differ in their optimal first-step action at x0.Source: §C.1 · p. 43
  • For any offline algorithm’s dataset-dependent policy, the C.1 argument compares its suboptimality across these two indistinguishable-action alternatives and concludes Lemma 5.3.The proof takes expectation over datasets generated under either MDP and uses a maximum-versus-mixture inequality to complete the argument.Source: §C.1 · p. 44

C.2 Suboptimality of PEVI on M

  • C.2 establishes a suboptimality lemma for PEVI on linear MDPs in M when λ = 1 and β = c · dH log(4dHK/ξ).The result assumes Assumption 2.2, with c an absolute constant and ξ ∈ (0, 1) the confidence parameter.Source: §C.2 · p. 44
  • When K ≥ 32 · log(8/ξ), the stated PEVI pessimism guarantee holds with probability at least 1 − ξ over the dataset.The probability is taken with respect to the dataset distribution P_D.Source: §C.2 · p. 44
  • The C.2 proof computes PEVI’s uncertainty terms from diagonal covariance matrices at the initial and absorbing states.At the initial state, the matrix depends on action counts n_1,…,n_A, while later matrices depend on absorbing-state counts m_1 and m_2.Source: §C.2 · p. 45
  • Concentration of Bernoulli transition counts, followed by union bounds and Theorem 4.4, supplies the high-probability event used to derive the PEVI suboptimality bound.The proof uses p_1,p_2,p_3 ∈ [1/4, 3/4], Hoeffding’s inequality, and separate probability bounds combined at confidence ξ.Source: §C.2 · pp. 45–46

C.3 Proof of Theorem 4.7

The proof establishes Theorem 4.7 by reducing offline policy selection to testing between two carefully constructed linear MDPs. Bounding their distinguishability and the optimal-policy performance gap yields the claimed lower bound for sufficiently large K.

Construction

  • Two linear MDPs swap transition parameters p* and p across the first two actions, with p* > p and balanced sample counts n1,n2.The construction assumes n1,n2 ≥ 4 and 1/c̄ ≤ n1/n2 ≤ c̄, with the dataset compliant under either MDP.Source: §C.3 · pp. 46–47

Testing reduction

  • Any offline algorithm’s output policy induces a test for distinguishing the two MDPs, whose error is controlled through total variation and Pinsker’s inequality.The dataset can be reduced to observations from the absorbing states, enabling the likelihood and KL-divergence calculations.Source: §C.3 · p. 46

Information bound

  • Choosing p and p* in [1/4, 3/4] with a sufficiently small gap bounds the KL divergence and prevents reliable discrimination between the two environments.The bound follows from the likelihood expressions and the parameter choice in Equation (C.16).Source: §C.3 · p. 47

Conclusion

  • For sufficiently large K, combining the testing and performance bounds proves the lower bound in Equation (4.14), and therefore Theorem 4.7 for linear MDPs.The argument applies because the constructed class M is a subclass of linear MDPs, under conditions K ≥ 64·log(2K) and K ≥ 2/C′.Source: §C.3 · pp. 47, 49

Performance gap

  • The optimal policies choose different first-step actions in the two MDPs, so testing failure translates into suboptimality for at least one environment.For M1 the optimal action is b1, whereas for M2 it is b2; concentration of the relevant Bernoulli counts makes the performance argument hold with high probability.Source: §C.3 · pp. 48–49

C.4 Locally Refined Upper Bounds · D Proofs of PEVI with Kernel Function Approximation

PEVI admits a locally refined analysis for the linear-MDP class, improving the generic suboptimality rate from e O(H2A/√nj∗) to e O(H/√nj∗) under coverage of the optimal action. This refinement makes Pess∗(D) superior to Pess(D) by a factor of HA while remaining minimax optimal up to H.

C.4 Locally Refined Upper Bounds

  • The construction defines empirical Bellman updates and a function Γ_ξ to instantiate PEVI, with Pess∗(D) denoting the resulting output policy.The estimated value function starts from bV_H+1 equal to zero, and unobserved actions receive a zero first-step update.Source: §C.4 · pp. 49–50
  • The local-optimality proposition assumes that the optimal action b_j∗ appears at least once in the compliant dataset, namely n_j∗ ≥ 1.Here j∗ = arg max_j∈{1,2}{p_j}.Source: §C.4 · p. 50
  • With probability at least 1 − ξ, the proposition establishes the suboptimality upper bound for Pess∗(D) under the data distribution P_D.The constant c is absolute, and Λ_h uses λ = 1.Source: §C.4 · pp. 50, 52
  • e O(H/√nj∗) is the refined suboptimality bound achieved by Pess∗(D), improving the generic e O(H2A/√nj∗) rate.The bounds omit logarithmic terms and absolute constants.Source: §C.4 · p. 50
  • Pess∗(D) is superior to Pess(D) by a factor of HA and is minimax optimal up to a factor of H.Both algorithms are minimax optimal, but the locally tailored uncertainty quantifier yields the tighter guarantee.Source: §C.4 · pp. 49–50
  • The proof verifies that Γ_ξ provides valid ξ-uncertainty quantifiers and then applies Theorem 4.2 to derive the policy guarantee.The argument uses concentration for actions with n_j ≥ 1 and a union bound over those actions.Source: §C.4 · pp. 50–51

D.1 Proof of Theorem 4.9

The appendix proves Theorem 4.9 by showing that Algorithm 3’s penalty is a valid uncertainty quantifier and then deriving its stated upper bound. The proof combines RKHS ridge-regression representations with martingale concentration under the dataset assumptions.

Theorem 4.9 proof

  • Theorem 4.9 follows by applying the general uncertainty-quantifier conclusion to the penalty construction in Equation (4.19), then simplifying Γ_h(s_h, a_h).The construction uses fixed Gram matrices K_h and operators k_h, with the expectation taken over trajectories induced by π*.Source: §D.1 · pp. 52–53
  • Under Assumption 4.8, the constructed {Γ_h} is a ξ-uncertainty quantifier when Algorithm 3 uses β = B and λ ≥ 1 + 1/K.The proof concludes this property with probability at least 1 − ξ after choosing λ = 1 + 1/K.Source: §D.1 · pp. 53, 56

Lemma D.1

  • The lemma derives a finite-dimensional closed form for the RKHS kernel-ridge estimator and expresses the fitted value through the Gram matrix K_h and feature operator k_h.This follows by orthogonally reducing the RKHS problem to the span of observed features and solving the resulting ridge-regression system.Source: §D.1 · pp. 53–54
  • The uncertainty bound is obtained by decomposing the empirical Bellman error, applying Cauchy–Schwarz and martingale concentration, and combining the resulting inequalities uniformly over all steps.The inverse sample-splitting order makes the relevant terms adapted to the filtration, while dataset compliance supplies the needed conditional-mean property.Source: §D.1 · pp. 54–56

D.2 Proof of Proposition 4.11

The proof translates Theorem 4.9’s condition on B into a sufficient inequality, then bounds it under three spectral-decay regimes. These bounds yield an explicit choice of B with logarithmic dependence on K, H, and ξ.

Reduction

  • Theorem 4.9’s condition on B is reduced to requiring 2 · G(K/H, 1 + 1/K) + 5 · log(H/ξ) ≤ 1/2.The reduction uses 2K/H · log(1 + 1/K) ≤ 1 ≤ log(H/ξ).Source: §D.2 · p. 57

Spectral-decay cases

  • Lemma E.5 bounds the reduced expression separately for γ-finite, γ-exponential, and γ-polynomial spectral decay.In the γ-finite case, 1 + 1/K lies in [1, 2], while the bounding constant depends only on d and γ in the stated cases.Source: §D.2 · p. 57

Parameter choice

  • Choosing B = c · H · (log(KH/ξ))^(1/2+1/(2γ)) for sufficiently large c satisfies the condition, with c depending on d, γ, C1, C2, and Cψ.The proof’s displayed choice applies after combining the bounds from the spectral-decay cases.Source: §D.2 · p. 57
  • For the final logarithmic bound, c > 0 is sufficiently large and depends on d and γ.This dependence is stated alongside the log(KH/ξ) term.Source: §D.2 · p. 57

D.3 Proof of Corollary 4.13 · D.4 Proof of Lemma D.2 · E Supporting Lemmas

This section proves key auxiliary results and collects supporting tools for the analysis, including effective-dimension bounds, projection and covering arguments, operator and Gram-matrix identities, concentration inequalities, and information-gain bounds under eigenvalue-decay assumptions.

D.3 Proof of Corollary 4.13

  • D.3 derives high-probability effective-dimension bounds for finite, exponential, and polynomial eigenvalue decay, with constants independent of K and H.The proof selects m, λ, and ε separately for each decay regime and concludes the target bounds with probability at least 1 −δ or 1 −ξ.Source: §D.3 · pp. 58, 59, 60, 62

D.4 Proof of Lemma D.2

  • D.4 proves Lemma D.2 by projecting onto the first m basis functions, applying concentration on an ε-cover, and transferring the result to the full RKHS operator.Lemma D.3 controls projection tails and Lemma D.4 supplies the fixed-direction concentration step, while the covering number enables a uniform bound.Source: §D.4 · pp. 62–65

E Supporting Lemmas

  • E records Matrix Bernstein and self-normalized-process concentration inequalities used as supporting probabilistic tools.The self-normalized result holds uniformly over time with probability at least 1 −δ under the stated measurability, sub-Gaussian, and positive-definiteness assumptions; the cited sources are Tropp (2015) and Abbasi-Yadkori et al. (2011).Source: E Supporting Lemmas · p. 65
  • Lemma E.3 relates RKHS regularized operators to Gram matrices and gives a bounded-feature specialization.The lemma defines Λ_t from RKHS feature vectors and states corresponding identities involving K_t.Source: E Supporting Lemmas · p. 66
  • Lemma E.4 provides a simultaneous high-probability concentration result for self-normalized RKHS processes with conditionally sub-Gaussian noise.It assumes adapted inputs and zero-mean σ-sub-Gaussian noise, with probability at least 1 −δ over all t.Source: E Supporting Lemmas · p. 66
  • Lemma E.5 bounds maximal information gain when the bounded, continuously differentiable RKHS kernel has finite-spectrum, exponential, or polynomial eigenvalue decay.The bound applies for λ ∈[c1, c2], with a constant depending only on the stated dimension, decay, kernel, and regularization parameters.Source: E Supporting Lemmas · pp. 66–67

Related papers

Loading 2012.15085v3…