PaperlayerView exact revision on arXiv

Source-linked AI summary

The Statistical Complexity of Interactive Decision Making

Dylan J. Foster, Sham M. Kakade, Jian Qian, Alexander Rakhlin

arXiv:2112.13487v3cs.LGmath.OCmath.STstat.ML

TL;DR

Interactive decision making lacks a general-purpose complexity theory for sample-efficient learning in adaptive, high-dimensional settings requiring function approximation. This paper introduces the Decision-Estimation Coefficient and Estimation-to-Decisions, establishing matching lower-bound and algorithmic principles for interactive learning.

  • Problem

    Existing theory is relatively complete for small state-action spaces or short horizons, but general-purpose function approximation remains desirable for interactive decision making.

  • Method

    The paper introduces the Decision-Estimation Coefficient and a framework that uses an online estimation oracle as input to the Estimation-to-Decisions algorithm.

  • Results

    The Decision-Estimation Coefficient lower bounds sample complexity for any interactive decision-making problem, while Estimation-to-Decisions achieves optimal sample complexity characterized by it.

  • Takeaways & Limitations

    The framework provides a theory of learnability and a unified algorithm design principle for reinforcement learning.

  • Takeaways & Limitations

    Upper and lower bounds differ in their dependence on estimation complexity, whose correct characterization requires additional complexity parameters.

Abstract

from arXiv · show

A fundamental challenge in interactive learning and decision making, ranging from bandit problems to reinforcement learning, is to provide sample-efficient, adaptive learning algorithms that achieve near-optimal regret. This question is analogous to the classical problem of optimal (supervised) statistical learning, where there are well-known complexity measures (e.g., VC dimension and Rademacher complexity) that govern the statistical complexity of learning. However, characterizing the statistical complexity of interactive learning is substantially more challenging due to the adaptive nature of the problem. The main result of this work provides a complexity measure, the Decision-Estimation Coefficient, that is proven to be both necessary and sufficient for sample-efficient interactive learning. In particular, we provide: 1. a lower bound on the optimal regret for any interactive decision making problem, establishing the Decision-Estimation Coefficient as a fundamental limit. 2. a unified algorithm design principle, Estimation-to-Decisions (E2D), which transforms any algorithm for supervised estimation into an online algorithm for decision making. E2D attains a regret bound that matches our lower bound up to dependence on a notion of estimation performance, thereby achieving optimal sample-efficient learning as characterized by the Decision-Estimation Coefficient. Taken together, these results constitute a theory of learnability for interactive decision making. When applied to reinforcement learning settings, the Decision-Estimation Coefficient recovers essentially all existing hardness results and lower bounds. More broadly, the approach can be viewed as a decision-theoretic analogue of the classical Le Cam theory of statistical estimation; it also unifies a number of existing approaches -- both Bayesian and frequentist.

1 Introduction

Interactive decision making lacks general complexity measures and universal algorithms comparable to those in statistical learning. The paper introduces the Decision-Estimation Coefficient and E2D to provide fundamental limits and a unified route to sample-efficient learning.

  • Motivation: Interactive decision making lacks general tools that characterize sample complexity and fundamental limits across new problem domains.Existing algorithm design is often case-by-case, making optimality and possible improvements unclear.
  • Framework: The paper formulates Decision Making with Structured Observations, covering structured bandits, reinforcement learning, and partially observed Markov decision processes.The framework supports models including linear models, neural networks, random forests, and other function approximators.
  • Decision-Estimation Coefficient: The Decision-Estimation Coefficient is a fundamental limit that lower bounds sample complexity for any interactive decision-making problem.It balances decision regret against estimation error relative to a nominal model in an information-acquisition game.
  • Estimation-to-Decisions: Estimation-to-Decisions is a universal reduction that converts online estimation algorithms into decision-making algorithms and achieves the DEC lower bound whenever estimation is possible.Its computational efficiency depends on efficiently solving the associated minimax program.
  • Implications: Together, the results give a learnability theory: with non-trivial online estimation complexity, sublinear regret is possible if and only if the DEC decays sufficiently quickly as γ increases.The DEC also subsumes existing structural conditions and supplies a necessary condition for sample-efficient reinforcement learning.
  • Extensions: The framework extends to contextual decision making and yields oracle-efficient algorithms for contextual bandits with large action spaces and contextual Markov decision processes.These extensions incorporate side information observed before each decision.

2 Preliminaries

The preliminaries formalize interactive decision making through measurable decision, reward, observation, and history spaces, then define models, algorithms, regret, divergences, and related Bayesian quantities. They also state assumptions connecting frequentist and Bayesian regret and introduce notation used for reinforcement learning and complexity analysis.

  • DMSO formalization: The framework represents decisions, rewards, observations, and histories on measurable spaces, with H(t) recording all actions, rewards, and observations through time t.These spaces support the formal probability model for interactive trajectories.
  • DMSO formalization: A model is a probability kernel mapping decisions to reward-observation distributions, while an algorithm adaptively selects decisions through history-dependent probability kernels.The induced law PM,p governs the resulting history.
  • Model assumptions: A common dominating kernel is assumed for upper-bound density estimation, but this assumption is not required for lower bounds.The assumption requires M(π) ≪ ν(π) for every model and decision.
  • Notation: The preliminaries introduce total variation, Hellinger distance, Kullback-Leibler divergence, occupancy measures, policy composition, transition operators, and asymptotic notation for later analyses.Reinforcement-learning notation includes state, state-action, and trajectory occupancy measures.
  • Regret objectives: The paper defines minimax frequentist regret as its main objective and also considers Bayesian regret when the unknown model is drawn from a known prior.Under mild technical conditions, the two regret notions coincide via minimax arguments.
  • Regret objectives: Proposition 2.1 establishes coincidence of minimax frequentist and Bayesian regret under finite decisions, bounded rewards, and additional stated conditions.The authors expect the proposition’s conditions can be weakened, while noting that partial-information minimax results are subtler.

3 A Theory of Learnability for Interactive Decision Making

The paper develops a theory of learnability for interactive decision making through a Decision-Estimation Coefficient lower bound and an Estimation-to-Decisions upper-bound principle. These tools characterize when sublinear regret is achievable and recover known bounds across bandit and reinforcement-learning settings.

  • 3 A Theory of Learnability for Interactive Decision Making: Estimation-to-Decisions is a universal reduction from supervised estimation to online decision making.The method uses an estimation algorithm to construct decisions, with regret controlled by the Decision-Estimation Coefficient and estimation complexity.
  • 3 A Theory of Learnability for Interactive Decision Making: Sublinear regret is achievable when online estimation complexity is non-trivial and decγ(M) decays sufficiently quickly as γ increases.This gives a characterization of learnability based on the Decision-Estimation Coefficient.
  • 3 A Theory of Learnability for Interactive Decision Making: The Decision-Estimation Coefficient provides a universal lower bound on regret for interactive decision-making problems.The lower bound applies to arbitrary model classes and holds with moderate probability; an in-expectation variant uses a stronger localization notion.
  • 3 A Theory of Learnability for Interactive Decision Making: The Decision-Estimation Coefficient accounts for information in observations, including structured feedback and auxiliary reward information.In tabular reinforcement learning, reward-only feedback can require 2^Ω(H) samples, whereas observing trajectories permits polynomial sample complexity; irrelevant observations do not change the coefficient, while data processing cannot decrease it.
  • 3 A Theory of Learnability for Interactive Decision Making: The upper and lower bounds have similar functional forms, but differ in localization, estimation complexity, and convexity requirements.The upper bound includes log|M| as an estimation-complexity term and uses co(M), whereas the lower bound considers M directly.
  • 3 A Theory of Learnability for Interactive Decision Making: The framework extends to rich, potentially nonparametric model classes through covering-number-based guarantees.Applications include structured bandits and reinforcement learning, where the coefficient recovers canonical lower bounds and hardness results.

4 The E2D Meta-Algorithm: General Toolkit

The E2D meta-algorithm provides a general toolkit that converts online estimation into interactive decision making, with regret controlled by the Decision-Estimation Coefficient and estimation error.

  • General toolkit: E2D is a meta-algorithm that can use any user-specified online estimation oracle for decision making.Its performance depends on the oracle’s estimation performance, measured through cumulative Hellinger error.
  • General toolkit: The general E2D guarantee bounds decision-making regret using the estimation oracle’s cumulative Hellinger error.This establishes a bridge between online estimation and interactive decision making.
  • Estimation oracles: For finite model classes, Vovk’s aggregating algorithm gives expected Hellinger estimation error at most log|M| and a high-probability bound 2 log(|M|/δ).These bounds provide an estimation-oracle guarantee that can be inserted into E2D.
  • Variants and localization: Option I is simpler to implement but does not achieve localization, whereas the more general guarantees incorporate localized Decision-Estimation Coefficients.The distinction affects the resulting regret bounds and their dependence on the model class.
  • DEC perspectives: The DEC is a min-max game in which decisions trade off regret against information acquisition against a worst-case model.Its dual Bayesian form instead balances the same tradeoff under a prior over models; under mild conditions, primal and dual DEC coincide.
  • Extensions: E2D also extends to general divergences and randomized estimators, while square-loss estimation can yield tighter finite-class bounds than Hellinger estimation.For finite classes, the supplied text gives EstSq ≤ log|FM| versus EstH ≤ log|M|.

5 Illustrative Examples

The examples show that the Decision-Estimation Coefficient yields matching upper and lower regret guarantees for bandits and tabular reinforcement learning. Bayesian posterior sampling and frequentist inverse-gap methods provide complementary ways to bound it, while PC-IGW gives an efficient exploration strategy for reinforcement learning.

  • Multi-armed bandits: The DEC admits both upper and lower bounds for finite-armed bandits, recovering the problem’s minimax regret rate up to a log A factor.The analysis uses minimax duality and includes an explicit Bayesian algorithm via posterior sampling.
  • Multi-armed bandits: E2D converts DEC bounds and supervised estimation performance into regret guarantees for finite-armed bandits.Using the Vovk-Azoury-Warmuth algorithm gives E[EstSq] ≤ A log(T).
  • Tabular reinforcement learning: For tabular reinforcement learning, posterior sampling yields a dual Bayesian DEC bound scaling with H2SA, with H dependence improvable from H2 to H for time-homogeneous dynamics.The dependence on S and A is stated to be optimal.
  • Tabular reinforcement learning: Policy Cover Inverse Gap Weighting combines inverse-gap weighting with policy covers to bound the frequentist DEC and can be implemented in poly(H, S, A, log(η)) time.The method balances state coverage against suboptimality and provides provable exploration without confidence sets or optimism.
  • Tabular reinforcement learning: The tabular reinforcement-learning results include matching DEC lower bounds under stated conditions on S, A, and H.The lower-bound construction applies when S ≥ 2, A ≥ 2, and H ≥ 2 log2(S/2).
  • Discussion: The discussion notes that upper-confidence-bound approaches are absent because their historical-data exploration criterion does not directly bound future on-policy estimation error in the DEC.Whether this distinction is fundamental remains open.

6 Application to Bandits

The DEC framework recovers tight or near-tight guarantees across structured bandits, including linear, convex, Lipschitz, ReLU, and gap-constrained settings. It also connects regret to eluder dimension and introduces star-number bounds that can be tighter.

  • Overview: The section develops DEC upper and lower bounds for linear, convex, and non-parametric bandits, plus additional lower bounds for ReLU and gap-constrained problems.These results are presented as applications of the general framework to canonical structured-bandit settings.
  • Linear bandits: Linear-bandit regret bounds are optimal for finite and bounded-diameter infinite action spaces, while E2D yields a general bound of E[RegDM] ≤ O(√dT · EstH).The finite-action result scales as √(dT log|Π|), and the infinite-action result is eO(d√T).
  • Linear bandits: The DEC lower bound for linear bandits persists under Euclidean geometry, showing that the finite-armed-bandit embedding is not the only source of hardness.The corresponding regret lower bound is derived through Theorem 3.2.
  • Convex bandits: For convex bandits, combining the DEC bound with estimation complexity gives regret E[RegDM] ≤ eO(d2.5√T), while the optimal dependence on d remains unresolved.The stated upper bound assumes bounded action-set diameter.
  • Non-parametric bandits: Lipschitz-bandit DEC bounds recover the minimax rate under covering-number conditions, and the analysis extends straightforwardly to other nonparametric classes such as Hölder bandits.The upper and lower results use covering numbers with respect to the action-space metric.
  • Lower bounds: The DEC recovers impossibility results for ReLU bandits and produces meaningful lower bounds even for gap-constrained multi-armed and linear bandits.The gap examples show hardness despite low statistical complexity.
  • Combinatorial complexity: Star-number bounds recover eluder-dimension regret guarantees while offering an eO(s2√T) bound that can be arbitrarily tighter than the eluder-dimension alternative.The comparison arises because the star-number expression has quadratic dependence, whereas the eluder-dimension expression has linear dependence.

7 Application to Reinforcement Learning

The reinforcement-learning applications extend DEC and E2D analysis from tabular problems to bilinear and function-approximation settings. They provide specialized upper bounds and recover exponential lower bounds for linearly realizable MDPs.

  • Bilinear classes: The section extends posterior-sampling and PC-IGW techniques to bilinear classes, which encompass many reinforcement-learning settings with sample-efficient learning guarantees.The generic results initially apply when model estimation complexity is moderate.
  • Bilinear classes: Tighter bilinear-class guarantees depend on estimation complexity for the induced Q-functions rather than the full model class, but are more specialized.This refinement recovers a broader set of sample-efficient learning guarantees within the bilinear framework.
  • Generic upper bounds: For general bilinear classes, the regret bound scales as RegDM ≲ (dbi(M) · EstH)1/3 · T2/3, matching prior T dependence based on forced exploration.T-regret for general bilinear classes is not currently known.
  • Frequentist methods: PC-IGW.Bilinear adapts policy-cover ideas through G-optimal design, generalizing coverage to bilinear reinforcement-learning classes.The strategy has separate on-policy and general-estimation-policy variants, and its guarantee matches posterior sampling up to a factor of H under stated assumptions.
  • Refined guarantees: The refined analysis uses Bellman residuals, yielding tighter rates because the relevant distance depends only on residuals rather than the complete model distributions.These bounds are better suited to model-free reinforcement-learning settings.
  • Lower bounds: The DEC lower bound for linear MDPs is unavoidable in bilinear dimension, with a regret lower bound matching the Section 7.1 upper bound in dimension and horizon dependence.The construction uses horizon H = 1 and bounded bilinear representations.
  • Lower bounds: For linearly realizable MDPs, the DEC is exponential, recovering exponential reinforcement-learning lower bounds even for instances with constant suboptimality gap.A complementary deterministic construction gives E[RegDM] ≥ eΩ(min{d, T}).

8 Incorporating Contextual Information

The contextual DMSO framework allows arbitrarily selected contexts and generalizes interactive decision making beyond standard contextual bandits. Contextual E2D uses estimation and a context-specific DEC optimization to obtain learnability guarantees when estimation is feasible.

  • 8 Incorporating Contextual Information: The framework encompasses contextual bandits and contextual reinforcement learning, including settings with structured or continuous action spaces.It also accommodates arbitrarily generated context sequences and auxiliary observations.
  • 8 Incorporating Contextual Information: Contexts may be chosen arbitrarily and adaptively, while rewards and observations are stochastic draws from an unknown model containing the true model.The learner receives a context before each decision and observes the resulting reward and observation.
  • 8 Incorporating Contextual Information: At each round, contextual E2D estimates a model, solves the DEC-defining optimization problem for the current context, samples a decision, and updates its estimation oracle.The algorithm retains the basic E2D structure while using the current context in the minimax problem.
  • 8 Incorporating Contextual Information: Algorithm 6 generalizes SquareCB to arbitrary contextual decision making and translates DEC bounds into oracle-efficient contextual algorithms.The paper gives applications to finite actions, continuous concave rewards, and linear action spaces.
  • 8 Incorporating Contextual Information: Any problem learnable non-contextually remains learnable under arbitrarily selected contexts when estimation is feasible.The guarantee depends on the estimation performance of the online oracle with respect to the chosen divergence.
  • 8 Incorporating Contextual Information: The framework imposes no assumption on the context space or how contexts map to MDPs, allowing flexible function approximation through an estimation oracle.The stated setting still requires finite states and actions for each MDP.

9 Additional Related Work and Follow-Up Work

The paper relates DEC to classical minimax estimation, structured-bandit complexity, and Bayesian information-ratio approaches. These comparisons emphasize DEC’s worst-case, finite-sample treatment of uncertainty and its broader applicability.

  • 9 Additional Related Work and Follow-Up Work: DEC is an interactive analogue of the classical modulus of continuity, replacing passive estimation’s maximization with a decision-dependent minimax tradeoff.Both measures balance risk against information gain relative to a reference model.
  • 9 Additional Related Work and Follow-Up Work: Compared with Graves–Lai complexity, DEC evaluates regret under a worst-case model rather than only under the nominal reference model.The distinction reflects finite-sample minimax regret rather than asymptotic instance-dependent analysis.
  • 9 Additional Related Work and Follow-Up Work: Finite-sample guarantees based on Graves–Lai complexity require strong structural assumptions to control plug-in estimation error, whereas DEC incorporates uncertainty directly.The paper therefore argues that Graves–Lai complexity alone is insufficient for optimal finite-sample instance-dependent guarantees.
  • 9 Additional Related Work and Follow-Up Work: A worst-case Bayesian information-ratio parameter bounds the KL-based DEC, and combining this relation with the DEC theorem recovers information-directed sampling’s Bayesian regret result.This connects the Bayesian approach to the paper’s DEC-based framework.
  • 9 Additional Related Work and Follow-Up Work: The information ratio can be arbitrarily larger than DEC and may be infinite for Lipschitz bandits, despite DEC yielding an optimal regret bound there.The paper attributes this limitation to ratio-based boundedness and numerical-instability issues.
  • 9 Additional Related Work and Follow-Up Work: The information ratio is tied to Bayesian bandits, while its frequentist analogue can also be arbitrarily larger than the Bayesian version even for multi-armed bandits.The paper’s frequentist focus motivates a different complexity treatment.

10 Discussion

The discussion presents the work as a foundation for learnability and algorithm design in reinforcement learning and interactive decision making. It also identifies computational, scope, and technical questions for future research.

  • 10 Discussion: The paper develops a theory of learnability and a unified algorithm design principle for reinforcement learning and interactive decision making.The authors describe these results as a foundation for future theory of data-driven decision making.
  • 10 Discussion: E2D is studied primarily for statistical rather than computational guarantees, except in special cases.Determining when and how it can be implemented efficiently remains an open direction.
  • 10 Discussion: The framework extends beyond bandits and reinforcement learning to settings such as POMDPs, but its implications there remain incompletely understood.The paper identifies this as a scope boundary rather than a resolved application.
  • 10 Discussion: Future extensions include adaptive or instance-dependent guarantees and constraints such as safety.These are presented as natural directions beyond the current results.
  • 10 Discussion: More work is needed to determine how tightly estimation complexity can be bounded or removed and whether E2D can support offline estimation oracles.These questions concern sharpening guarantees and extending the algorithmic interface.

A.3.5 Proofs

The appendix develops technical tools used throughout the paper, including concentration inequalities, divergence comparisons, and bounds for online learning. It then proves supporting estimation and high-probability results.

  • A.3.5 Proofs: The proof section derives in-expectation and high-probability guarantees using martingale concentration, expert aggregation, covering arguments, and bounded-divergence estimates.The displayed proof steps combine these ingredients to establish the stated lemmas.

B Decision-Estimation Coefficient: Structural Results

The section establishes local-to-global properties for the Decision-Estimation Coefficient and proves matching lower- and upper-bound results under stated structural assumptions.

  • Structural consequences: Proposition 2.1 and Theorem 3.6 provide structural conditions under which the Decision-Estimation Coefficient yields algorithmic guarantees for interactive decision making.The section explicitly introduces conditions for comparing localized and global coefficients and states an algorithmic consequence whenever Proposition 2.1 holds.
  • Local-to-global results: The local-to-global lemmas lower bound localized Decision-Estimation Coefficients using star-convexity, a constant reference reward, and, for Gaussian bandits, star-closure around zero.The general lemma assumes star(M, M0) ⊆ M with constant f_M0; the Gaussian-bandit version assumes star(F_M, 0) ⊆ F_M and σ^2 ≥ 1/8.
  • Lower bounds: Theorem 3.1 gives a high-probability lower bound: for any algorithm, some model in M incurs regret governed by dec_γ and the horizon T.The theorem uses the localized model class M_ε(M), a confidence parameter δ, and ε̄_γ proportional to γ divided by a logarithmic complexity factor.
  • Lower bounds: Theorem 3.2 provides the corresponding in-expectation lower bound, using stronger localization to simplify the change-of-measure argument.Its proof follows the structure of Theorem 3.1 but exploits stronger localization for the change-of-measure step.
  • Upper bounds: Theorem 3.3 gives a finite-class upper bound through Algorithm 1 and an estimation oracle, with probability at least 1 − δ.The theorem assumes R ⊆ [0, 1] and Assumption 3.1; the supplied statement defines a logarithmic complexity factor C.
  • Upper bounds: Theorem 3.4 extends the upper bound to general classes, with complexity terms C1, C2 and an infimum balancing estimation accuracy against model-class covering complexity.The supplied statements define C1 = O(c_ℓ^2 log c_ℓ(T) log^2(BT)) and C2 = O(log^2(BT)).

C.3 Proofs for Learnability Results

The learnability results characterize when sublinear regret is possible by combining Decision-Estimation Coefficient decay with sublinear supervised estimation performance.

  • Learnability: Theorem 3.5 states learnability when M is convex, Assumptions 3.2 and 3.3 hold, and est(M, T) = eO(T^q) for q < 1.The theorem provides a sufficient condition based on sublinear estimation complexity and the model’s Decision-Estimation Coefficient.
  • Necessary and sufficient behavior: If dec_γ(M)γ^ρ tends to zero for some ρ > 0, an algorithm achieves sublinear regret at a corresponding rate.The supplied result states existence of an algorithm with a rate exponent below one, including the relation p′ = 1/2(p + 1) < 1.
  • Necessary and sufficient behavior: If dec_γ(M)γ^ρ remains positive for every ρ > 0, every algorithm has regret that cannot satisfy the corresponding sublinear rate for any p < 1.This is the complementary lower-bound case in the learnability characterization.
  • Refined learnability: Theorem 3.7 removes the assumption on est(M, T) when est(ΠM, T) = eO(T^q) and Proposition 2.1 holds.Under these conditions, the conclusion of Theorem 3.5 continues to hold.
  • Learnability: E2D achieves expected regret eO(dec_γ(M) · T + γ · T^q) under the stated estimation-rate condition.This bound follows by applying the general upper bound with est(M, T) = eO(T^q).

D.1 Proofs from Section 4.1

The proofs for Section 4.1 establish localized regret guarantees by maintaining confidence-set containment, connecting confidence sets to localized model classes, and applying estimation-error control.

  • Proof setup: Assumption D.1 supplies a high-probability Hellinger estimation guarantee and requires the confidence-model estimate c_M(t) to lie in co(M(t)).These conditions are used by the localized upper-bound theorem.
  • Localized upper bound: Theorem 4.1a gives a high-probability localized regret bound for Algorithm 1 with Option II and R2 = g_EstH(T, δ).The result assumes R ⊆ [0, 1], Assumption D.1, and confidence estimates in the convex hull of the confidence sets.
  • Confidence-set containment: Lemma D.1 proves by induction that the true model M⋆ remains in every confidence set M(t) on the designated high-probability event.The base case holds with probability one, and the induction step uses the confidence-set update rule.
  • Confidence-set localization: Lemma D.2 relates the minimax Decision-Estimation Coefficient to Hellinger estimation error for models contained in the confidence sets.This relation enables the conversion from confidence-set guarantees to localized model-class guarantees.
  • Confidence-set localization: The proof then embeds M(t) in a localized class around c_M(t), enabling Algorithm 1’s localized decision rule to use the coefficient-based bound.The construction uses the nesting of confidence sets and c_M(t) ∈ co(M(t)).
  • Applications and examples: Additional propositions and constructions establish coefficient bounds for finite action spaces, metric covers, packing-based classes, and linear or gap-structured examples.The supplied passages derive bounds by covering, packing, and explicit hard-family constructions.

E.2 Proofs from Section 6.2

The proofs for Section 6.2 bound the Decision-Estimation Coefficient through decoupling and posterior-sampling arguments, then connect these tools to reinforcement-learning simulation and change-of-measure lemmas.

  • Decoupling framework: The section first proves a generic decoupling lemma for randomly indexed reward functions and policies, then applies it to Theorems 6.1 and 6.2.The setup uses an index distribution μ and families {f_z, π_z} to decouple their dependence.
  • Disagreement-based bounds: Lemma E.2 bounds the relevant quantity for function classes F ⊆ (Π → [−R, R]) using the disagreement coefficient and the induced policy distribution ρ_μ.The proof clips variables, applies Cauchy–Schwarz and AM-GM, and tunes η and ε relative to γ and R.
  • Posterior sampling: Theorem 6.2 uses posterior sampling, where ρ_μ(π) is the probability that a model sampled from μ selects policy π, to obtain the coefficient bound.The proof exploits that a posterior-sampled policy and the model-optimal policy have the same law under μ.
  • Reinforcement learning: The reinforcement-learning proof tools include Bellman residual decomposition, global and local simulation lemmas, and a change-of-measure result for MDPs.These lemmas compare reward and transition behavior between MDPs under bounded-horizon assumptions.
  • Reinforcement learning: The change-of-measure proof controls differences between MDP-induced distributions using Hellinger-distance inequalities and bounded rewards.The supplied assumptions include rewards in [0, 1] and a policy distribution over the reinforcement-learning policy class.

F.2 Proofs from Section 7.1

The section proves DEC bounds for posterior sampling and PC-IGW strategies in bilinear classes, distinguishing on-policy from general estimation policies. It also establishes the normalization needed by PC-IGW.

  • Posterior sampling: Theorem 7.1 analyzes modified posterior sampling for bilinear classes with an arbitrary reference model and an interpolation parameter α.The proof uses Bellman residual decomposition, bilinear structure, Cauchy–Schwarz, and AM-GM.
  • Estimation policies: On-policy estimation permits α = 0, while general estimation policies require a nonzero α choice.The distinction is stated explicitly for the posterior-sampling and PC-IGW analyses.
  • Posterior sampling: The posterior-sampling proof bounds the DEC by selecting η as a function of γ, H, α, L, and the bilinear complexity.The resulting bound is obtained after averaging over the prior and tuning η.
  • PC-IGW.Bilinear: PC-IGW.Bilinear is analyzed with an approximate optimal-design solver having approximation factor Copt ≥ 1.The proof verifies that the strategy is well-defined before bounding its DEC.
  • PC-IGW.Bilinear: The PC-IGW normalization constant is unique and lies in [1/2, 1].This follows from continuity and strict decrease of the normalization function.
  • PC-IGW.Bilinear: 9H^3CαCoptL^2 bounds the DEC after setting η = η′ = γ/(3dH^3CoptCαL^2).The bound is the concluding quantitative result of the PC-IGW.Bilinear proof.

F.3 Proofs from Section 7.2

The section proves upper and lower results for bilinear and linearly realizable MDP settings, including confidence-set estimation, posterior sampling, and hardness constructions. It also relates Bellman representability to Bellman-eluder dimension and the Bellman-star number.

  • Theorem 7.3: Theorem 7.3 gives an E2D.Bayes guarantee for bilinear classes under Assumption 7.1 and on-policy estimation.The algorithm uses the optimization problem in (81) and is parameterized by a prior and γ.
  • Theorem 7.3: The proof controls estimation error with confidence sets, ε-covers, concentration bounds, and the elliptic potential lemma.The confidence radius uses ε^2T and log(HTN/δ), and the resulting events hold uniformly over rounds, layers, and covering elements.
  • Theorem 7.3: The confidence-set argument shows that the true model’s covering element remains admissible across all layers and rounds on the concentration event.The conclusion uses the covering property and a sufficiently large numerical constant in R1.
  • Lower bounds: Proposition 7.3 constructs linearly realizable MDPs yielding a lower bound for dimensions d ≥ 29 and horizons H ≥ 2.The construction uses nearly orthogonal vectors, a terminal state, and a family indexed by a⋆.
  • Lower bounds: Proposition 7.4 gives a lower bound for deterministic linearly realizable MDPs with H = 1, constant suboptimality gap, and deterministic rewards and dynamics.The proposition applies to rewards in [0, 1].
  • Bellman representability: Bellman representability recovers Bellman-eluder dimension as a special case and introduces the Bellman-star number as a potentially smaller parameter.The Bellman-star number can be arbitrarily smaller than Bellman-eluder dimension in general.

G.4 Proofs from Section 9

The section analyzes DEC and information-ratio behavior in Lipschitz and multi-armed bandit problems. It shows that information ratios can be infinite even when DEC remains finite.

  • Lipschitz bandits: In the Lipschitz bandit setting, the information ratio is infinite for all d ≥ 1.The proof reduces to d = 1 and constructs a family of localized 1-Lipschitz models.
  • Multi-armed bandits: For multi-armed bandits with an interior model and positive minimum gap, Proposition 9.3 establishes a lower bound on the information ratio.The model class uses Π = [A], and the condition requires every suboptimal action to have positive gap.
  • Multi-armed bandits: The multi-armed bandit example also satisfies decγ(M) ≤ IB(M) ≤ O(A/γ) for every γ > 0.This contrasts finite DEC control with the infinite information-ratio behavior identified in the Lipschitz construction.
  • Lipschitz bandits: The Lipschitz-bandit information ratio becomes +∞ because η can be chosen arbitrarily large under the constructed interior reward function.The argument considers both distributions with zero action probability and interior distributions.
Loading 2112.13487v3…