Information-Theoretic Considerations in Batch Reinforcement Learning

Jinglin Chen; Nan Jiang

Source-linked AI summary

Information-Theoretic Considerations in Batch Reinforcement Learning

Jinglin Chen, Nan Jiang

arXiv:1905.00360v1May 1, 2019cs.LGcs.AIstat.ML

TL;DR

The paper examines why batch RL guarantees rely on mild distribution shift and representation conditions beyond realizability. It analyzes representative algorithms and proves lower bounds showing that unconstrained dynamics or concentratability can preclude sample-efficient learning, while exact realizability and completeness yield n^-1/2 rates.

Problem
Existing analyses indicate that sample-efficient learning of near-optimal policies often requires assumptions about distribution shift and value-function representation, but when these assumptions are needed remains unclear.
Method
The paper analyzes representative ADP algorithms and uses information-theoretic lower bounds to study distribution shift and representation conditions.
Results
Polynomial sample complexity is impossible without restricting MDP dynamics even under the most favorable data distribution, while exact realizability and completeness yield n^-1/2 suboptimality rates.
Takeaways & Limitations
Realizability alone is insufficient in the studied setting, and unconstrained concentratability immediately precludes sample-efficient learning even with benign data.
Takeaways & Limitations
The algorithmic analysis assumes finite value-function classes F and G because it uses a minimal setup.

Abstract

from arXiv · show

Value-function approximation methods that operate in batch mode have foundational importance to reinforcement learning (RL). Finite sample guarantees for these methods often crucially rely on two types of assumptions: (1) mild distribution shift, and (2) representation conditions that are stronger than realizability. However, the necessity ("why do we need them?") and the naturalness ("when do they hold?") of such assumptions have largely eluded the literature. In this paper, we revisit these assumptions and provide theoretical results towards answering the above questions, and make steps towards a deeper understanding of value-function approximation.

1. Introduction and Related Work

The paper examines when batch value-function approximation works, focusing on the necessity and naturalness of distribution-coverage and representation assumptions. It develops theoretical results including lower bounds, algorithm analyses, and a possible separation between model-based and value-based methods.

Batch value-function approximation underlies many reinforcement-learning methods, including off-policy applications of popular deep-RL algorithms.These methods use transition samples to approximate Q⋆ within a restricted function class encoding prior knowledge and inductive biases.
Finite-sample analyses commonly require sufficient state-action coverage and representation conditions stronger than realizability.The stronger conditions include approximate closedness under Bellman updates, often called completeness.
The paper revisits whether these assumptions are necessary and whether they hold in interesting problems, rather than treating them only as sufficient conditions.
The analysis formally justifies mild distribution shift through an information-theoretic lower bound, even while excluding failures caused solely by adversarial data.
The paper conjectures that realizability alone cannot suffice, shows two broad proof styles cannot establish the conjecture, and proves polynomial sample complexity for model-based RL with realizability alone.If the conjecture holds, this yields a formal separation between batch model-based and value-based RL with function approximation.
Connections to state abstractions and PAC exploration provide proof tools and examples where the assumptions of interest hold.

2. Preliminaries

The preliminaries define batch value-function approximation, FQI, and its relationship to state abstractions. The setup uses a batch transition dataset and a candidate function class intended to capture the optimal Q-function.

2.1. MDPs and Value Functions: An MDP consists of finite states and actions, transitions, rewards, discount factor γ, and an initial state distribution.Policies induce trajectories and seek to maximize expected discounted return; optimal Q⋆ satisfies the Bellman equation.
2.2. Batch Value-Function Approximation: Batch RL provides transition tuples sampled from a data distribution rather than direct access to the MDP.The standard dataset contains (s, a, r, s′) tuples, with state-action pairs generated i.i.d. from µ.
2.2. Batch Value-Function Approximation: The candidate class F is assumed to approximately capture Q⋆, a property known as realizability, and learning outputs the greedy policy πf for a fitted function.
2.2. Batch Value-Function Approximation: FQI iteratively regresses targets r+γV_fk−1(s′) onto F using squared loss, producing the next function fk.The algorithm is a representative approximate value-iteration method in the batch setting.
2.2. Batch Value-Function Approximation: FQI can oscillate and lack a fixed-point solution, although finite-sample guarantees may still hold under specified conditions.
2.3. State Abstractions: Value iteration in a certainty-equivalent model built from state abstraction φ is exactly equivalent to FQI over functions that are piecewise constant under φ.Thus, the two literatures have closely related characterizations of approximation error.

3. Bellman Error Minimization in Batch Reinforcement Learning

The section analyzes FQI and a minimax variant for batch value-function approximation, clarifying their relationship and deriving finite-sample guarantees under distribution and representation assumptions. It also shows that the minimax formulation addresses a conditional-variance mismatch and achieves a faster exact-case error rate.

Analysis overview: The section provides complete analyses of FQI and a related minimax algorithm, including finite-sample bounds and simplified treatments of prior results.The analyses also improve the dependence of error rates on sample size.
Bellman error minimization: The data-based regression objective differs from the desired Bellman error because it adds a conditional variance penalty.This penalty incorrectly disfavors functions with high variance under random state transitions.
Bellman error minimization: The minimax algorithm estimates and subtracts the conditional variance term, using a second function class to estimate the Bayes-optimal regressor.The estimate is consistent when that class realizes the Bayes-optimal regressor and has bounded statistical complexity.
FQI and the minimax variant: FQI is an approximation to the minimax program when G = F; zero excess regression error yields a fixed point, while positive error implies oscillation and no fixed point.When FQI reaches a fixed point, the two algorithms’ solutions coincide, and the minimax algorithm is more stable.
Assumptions: The guarantees use concentratability, realizability, and completeness assumptions, with completeness requiring T f ∈ G for every f ∈ F.For FQI, G = F makes completeness equivalent to closure of F under the Bellman operator.
Sample complexity: Under exact realizability and completeness, suboptimality decreases at rate n^-1/2, while general bounds degrade gracefully as approximation errors increase.The paper attributes the fast rate to Bernstein’s inequality; prior closely related analyses obtained n^-1/4 rates in comparable settings.
Limitations: The major limitation is the assumption that F and G are finite, which follows from the paper’s minimal setup.

4. On Concentratability

The section establishes that mild distribution shift, expressed through concentratability, is necessary even when data collection is highly favorable. The lower bound attributes the difficulty not only to the data distribution but also to unrestricted MDP dynamics and induced state distributions.

Necessity of concentratability: The paper proves that no algorithm can achieve polynomial sample complexity under unrestricted MDP dynamics, even with the most favorable data distribution.The result rules out a trivial explanation based solely on adversarially selected data.
Lower bound: The hard-instance construction preserves both realizability and completeness while allowing an algorithm to choose any favorable data distribution.
Lower bound: The concentratability coefficient is always exponential in the horizon for every data distribution on the worst-case MDP.Thus the lower bound does not conflict with upper bounds whose sample complexity depends on that coefficient.
Lower bound: The lower bound remains exponential in horizon even when algorithms can explore during data collection and receive compact classes satisfying realizability and completeness.

2. Since the MDPs in the construction share the same de-

Without restrictions on MDP dynamics, even favorable data distributions cannot guarantee polynomial sample complexity. Hard tree constructions reduce learning to best-arm identification, while rich-observation low-rank environments can admit naturally generated distributions with bounded concentratability.

Even active exploration requires Ω(|A|^H ln(1/δ)/ε^2) samples in the hard tree family.The construction has deterministic transitions, rewards only at leaves, and |A|^H possible optimal leaves.
The hard family satisfies realizability and completeness yet still rules out polynomial sample complexity under any favorable data distribution.The function classes have logarithmic statistical complexities proportional to H ln |A|, so these complexities do not explain away the exponential hardness.
Uniform data can still yield a concentratability coefficient scaling with |S × A|, making worst-case guarantees too large for challenging RL problems.Constructed tabular examples show that the coefficient need not always scale badly, motivating broader structural examples.
In visual-gridworld-like reactive POMDPs, hidden low-dimensional dynamics with rich observations admit a data distribution yielding small concentratability.The distribution can be naturally generated as a mixture of admissible distributions.
Bellman rank appears to be the online-exploration counterpart of the batch concentratability coefficient.The paper notes that analogous results extend to other low-rank structures, including large MDPs with low-rank transitions.

5. On Completeness

The paper investigates whether completeness is necessary beyond realizability for value-function approximation. It proves model-based sufficiency results, identifies limits of several lower-bound strategies, and connects completeness to bisimulation under piece-wise constant representations.

5. On Completeness: Exponential-sized model families cannot establish the conjectured information-theoretic lower bound because polynomial sample complexity is achievable information-theoretically.The paper concludes that any counterexample, if it exists, must be highly nontrivial and likely require ideas beyond standard SLT and RL constructions.
5. On Completeness: Batch model-based RL can achieve polynomial sample complexity with realizability alone.The proof reduces model-based learning to value-based learning and obtains completeness for free through constructed function classes.
5. On Completeness: Realizability alone is insufficient as a representation condition for the targeted value-based hardness question, with completeness proposed as a stronger candidate.The paper seeks hard MDPs under low concentratability and realizability, while noting that existing algorithm-specific divergence results are not information-theoretic lower bounds.
5. On Completeness: Value-profile hardness cannot arise in naive tabular constructions with realizability, constant-sized state-action spaces, and uniform data.Under sufficiently frequent state-action samples, an algorithm operating only through value profiles can still achieve polynomial sample complexity.
5. On Completeness: The paper leaves its proposed realizability-only lower bound as Conjecture 8 rather than proving it.The conjecture concerns algorithms restricted to accessing states through value profiles and does not assert that completeness is absolutely necessary.
5.2. Connection to Bisimulation: For piece-wise constant functions induced by an abstraction, completeness is equivalent to bisimulation.The proof identifies reward or transition discrepancies when the abstraction fails to be a bisimulation.

6. Discussions and Related Work

The discussion establishes that concentratability is necessary for sample-efficient learning under benign data, while completeness remains unresolved. It also connects the analysis to function-class structure and gives an information-theoretic perspective on bootstrapped-target difficulties.

Distribution shift: Not constraining the concentratability coefficient C precludes sample-efficient learning even with benign data.The paper also introduces empirical-RL problem families with low concentratability.
Completeness: The necessity of completeness remains an open question because two general lower-bound proof styles have been ruled out.The authors hope these negative results guide the search for constructions capturing fundamental difficulties of function approximation.
Alternative assumptions: Even if realizability is insufficient, other assumptions may break the conjectured lower bound, so completeness is not shown to be absolutely necessary.Such alternatives may constrain another function class or impose properties such as Bellman-operator contraction.
Related work: The paper’s information-theoretic perspective on realizability insufficiency is novel relative to predominantly algorithm-specific prior work on bootstrapped-target problems.The discussion relates this issue to undesirable phenomena in learning with bootstrapped targets.
Connections to RL theory: Concentratability is defined from the MDP, whereas Bellman rank depends on both environmental dynamics and the function class F.This connection motivates incorporating F into a broader definition of concentratability.

A. Proof of Proposition 1

The proof shows that a fixed point of FQI solves the associated optimization problem when the two function classes coincide. It then uses this fact to rule out non-oscillating FQI behavior under the stated contradiction setup.

Fixed-point characterization: When G = F, choosing g = f makes the minimax objective non-negative for every f ∈ F.If FQI reaches a fixed point, the corresponding pair attains objective value zero and solves Eq. (6).
Fixed-point characterization: A fixed point of FQI is a solution to Eq. (6), with ˆf = ˆg equal to the fixed-point iterate.This follows from the equality of the empirical losses at consecutive identical iterates.
Contradiction argument: If FQI does not oscillate and reaches a fixed point, the minimax objective value is zero, yielding the contradiction used in Claim 3.The proof substitutes the fixed-point solution from the previous claim.

B. Example of Low Concentratability in Rich-Observation Problems

The construction uses low-rank structure in reactive POMDPs with rich observations to build a mixture data distribution whose concentratability coefficient is small. The rank bound comes from the finite hidden-state space, and the mixture uses uniform actions.

Reactive POMDPs: A reactive POMDP has finite hidden states, potentially large observations, action-dependent hidden-state dynamics, emissions, rewards, and discounting.Its Q⋆ function depends only on the last observation, with an additional assumption that observations are Markov.
Concentratability bound: C ≤ |Z × A| when the data distribution is µ := µS × Unif(A), constructed as a mixture of admissible distributions.The proof combines the low-rank factorization with uniform action probabilities to establish the concentratability bound.
Matrix construction: Admissible state distributions are policy-induced marginals over states at a given timestep and are stacked into a matrix for rank analysis.The construction assumes finitely many admissible distributions and indexes them as matrix rows.
Concentratability bound: The technical assumption that the number of admissible distributions is finite does not affect the resulting upper bound’s dependence on their number.The paper introduces this assumption to avoid technical subtleties.
Low-rank structure: The admissible-distribution matrix has rank r ≤ |Z|, where |Z| is the number of hidden states.The proof factorizes the matrix as AZ = BZ CZ and selects a full-rank square submatrix from BZ.

C. Analysis of FQI

The FQI analysis derives high-probability error bounds under approximate completeness using auxiliary lemmas linking Bellman error, function approximation, and policy suboptimality. The resulting bound includes a slow-rate term that is controlled rather than dominant.

Error bound: The analysis develops a general FQI error bound when completeness holds only approximately.The theorem applies to finite function classes F and G, with G approximately realizing T F.
Rate behavior: The slow-rate term n^-1/4 is multiplied by 4√..., and the analysis states that it never dominates because it is a geometric mean of the fast-rate and approximation-error terms.The minimax algorithm’s bound has a similar structure, unlike prior bounds with a genuinely dominating slow-rate term.
Error bound: Theorem 11 gives a high-probability performance guarantee for the policy output by FQI after k iterations under approximate completeness.The guarantee is stated for a dataset of size n and includes the approximation error ǫF,F.
Proof strategy: The proof repeatedly expands policy suboptimality through a concentratability-based inequality and reduces the result to bounding ∥fk − T fk−1∥2,µ.Auxiliary lemmas relate greedy-policy suboptimality and Bellman error under ℓ2 norms.
Proof strategy: The empirical-loss analysis uses squared loss, Bayes optimality of T fk−1, concentration inequalities, and union bounds over F and G.These steps produce the finite-sample control used in the main theorem.

D. Analysis of the Minimax Algorithm

The minimax algorithm is analyzed under approximate realizability and completeness, yielding a high-probability error bound through concentration and comparison of empirical objectives. The proof reduces dependence on G, controls Bellman residuals, and transfers the resulting bound to policy performance.

Theorem and assumptions: Theorem 17 gives a high-probability error bound for the minimax algorithm when F and G satisfy approximate realizability and approximate completeness.The guarantee applies to a dataset of size n and holds with probability at least 1 − δ.
Proof strategy: The proof first upper-bounds the difference between the minimax objective involving G and the objective involving the true Bellman update T f.This removes direct dependence on the function class G up to an error controlled by concentration.
Proof strategy: The analysis bounds ∥f̂ − T f̂∥²,µ and then uses Lemma 15 and Lemma 13 to obtain a bound on ∥f̂ − Q⋆∥²,µ and the output policy.The final step transfers value-function approximation error into the policy guarantee.
Proof strategy: Approximate realizability supplies f⋆ ∈ F with small Bellman error, while minimax optimality compares the learned function’s objective against f⋆.The resulting comparison includes additive approximation terms such as 2ε² in the displayed intermediate bound.
Proof strategy: Concentration bounds apply Bernstein’s inequality and union bounds over f ∈ F, and over f ∈ F and g ∈ G when both classes appear.The analysis uses bounded i.i.d. variables formed from the transition samples and tracks the confidence parameter through δ′.

E.2. Proof of Equivalence Between Bisimulation and Completeness for Piece-wise Constant Function Class

For piece-wise constant functions induced by a state abstraction, the paper relates approximate bisimulation to Bellman completeness. Exact equivalence holds when the reward, transition, and completeness errors vanish, while approximate quantities provide separate bounds rather than equality.

Upper and lower bounds: Proposition 20 states that an approximate Q⋆-irrelevant abstraction yields an upper bound on Bellman completeness violation.The bound is expressed using reward error εR and transition error εP.
Exact case: When εR, εP, and the completeness error are all zero, Proposition 9 follows as a direct corollary.Thus exact bisimulation and completeness coincide in the exact case covered by the proposition.
Approximate case: In the approximate case, reward and transition errors give upper and lower bounds but not equality because their effects may cancel inside the Bellman operator.The mismatch is attributed to bisimulation separating reward and transition errors while completeness combines them.
Upper and lower bounds: The proof constructs a piece-wise constant approximation f′₁ whose Bellman-update error is at most εR/2 + γεPVmax/4.The construction treats reward and transition discrepancies separately within each abstract state-action pair.
Upper and lower bounds: The lower bound uses reward and transition witnesses to show completeness error is at least εR/2 or γεPVmax/4 in corresponding cases.The transition construction produces Bellman-update values separated by γεPVmax/2, implying approximation error at least γεPVmax/4.

F. Proof of Proposition 7

The proof of Proposition 7 represents states by their value profiles, forming a state abstraction under realizability, then estimates and plans in the resulting abstract model. This yields polynomial sample complexity when data are sufficiently uniform over abstract state-action pairs.

State abstraction: States sharing the same value profile are grouped into an abstraction φ, and realizability makes this abstraction Q⋆-irrelevant.The abstract state space is isomorphic to the set of distinct value profiles.
Model estimation: The procedure represents abstract states, estimates a tabular model, and outputs its optimal policy.Transition tuples are grouped by abstract state-action pairs to form the estimated model.
Sample analysis: Certainty-equivalence planning in the estimated abstract model is analyzed by concentration over abstract state-action pairs.Hoeffding’s inequality is applied to bounded independent samples, followed by a union bound.
Sample analysis: With a Q⋆-irrelevant abstraction, the resulting guarantee depends on the minimum number of samples received by an abstract state-action pair.The proof identifies nφ(D) as the relevant coverage quantity.
Sample complexity: Because nφ(D) = Ω(|D|/|S × A|), achieving error ε requires a sample size polynomial in the relevant parameters.The stated polynomial dependence follows from the bound on the abstract-pair coverage quantity.
Distribution shift: The abstraction perspective suggests that relatively uniform data over abstract states can suffice even when some raw states receive no data.For F = Fφ and bisimulation, the concentratability coefficient can be bounded by the number of abstract state-action pairs.