PaperlayerView exact revision on arXiv

Source-linked AI summary

Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism

Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, Stuart Russell

arXiv:2103.12021v2cs.LGcs.AImath.OCmath.STstat.ML

TL;DR

Offline RL must handle datasets between expert-only and uniform-coverage extremes, but their composition is often unknown. This paper introduces a concentrability-based LCB framework and finds adaptive optimality for contextual bandits, with mixed results for bandits and MDPs.

  • Problem

    Offline RL lacks a formulation for datasets between expert-only and uniform-coverage extremes despite practical variation and insufficient coverage from distribution shift.

    Source: §1.1 · p. 4, §6.1 · p. 23

  • Method

    The paper develops a single-policy concentrability framework with lower confidence bounds based on pessimism to adapt offline learning to unknown data composition.

    Source: §5.1 · p. 18, §7 · p. 25

  • Results

    LCB is adaptively minimax optimal for contextual bandits, but is non-adaptive near-expert bandits and only partially rate-optimal across MDP data compositions.

    Source: §7 · p. 25

  • Takeaways & Limitations

    The framework provably bridges imitation learning and offline RL for contextual bandits, while LCB’s guarantees remain mixed for bandits and MDPs.

    Source: §7 · p. 25

    LCB cannot be optimally adaptive in both near-expert and less expert bandit regimes without knowing the data-composition range.

    Source: §3.5 · p. 13

Abstract

from arXiv · show

Offline (or batch) reinforcement learning (RL) algorithms seek to learn an optimal policy from a fixed dataset without active data collection. Based on the composition of the offline dataset, two main categories of methods are used: imitation learning which is suitable for expert datasets and vanilla offline RL which often requires uniform coverage datasets. From a practical standpoint, datasets often deviate from these two extremes and the exact data composition is usually unknown a priori. To bridge this gap, we present a new offline RL framework that smoothly interpolates between the two extremes of data composition, hence unifying imitation learning and vanilla offline RL. The new framework is centered around a weak version of the concentrability coefficient that measures the deviation from the behavior policy to the expert policy alone. Under this new framework, we further investigate the question on algorithm design: can one develop an algorithm that achieves a minimax optimal rate and also adapts to unknown data composition? To address this question, we consider a lower confidence bound (LCB) algorithm developed based on pessimism in the face of uncertainty in offline RL. We study finite-sample properties of LCB as well as information-theoretic limits in multi-armed bandits, contextual bandits, and Markov decision processes (MDPs). Our analysis reveals surprising facts about optimality rates. In particular, in all three settings, LCB achieves a faster rate of $1/N$ for nearly-expert datasets compared to the usual rate of $1/\sqrt{N}$ in offline RL, where $N$ is the number of samples in the batch dataset. In the case of contextual bandits with at least two contexts, we prove that LCB is adaptively optimal for the entire data composition range, achieving a smooth transition from imitation learning to offline RL. We further show that LCB is almost adaptively optimal in MDPs.

1 Introduction

The paper introduces an offline RL framework based on C⋆, a weak concentrability measure that interpolates between expert and uniformly covered data. A pessimistic lower-confidence-bound algorithm adapts to unknown data composition, achieving optimal or nearly optimal rates across bandits and MDPs.

1 Introduction

1.1 Motivating questions

  • The framework measures dataset deviation using C⋆, the ratio between optimal-policy and behavior-distribution occupancy densities, with C⋆=1 representing expert data and larger values allowing spurious samples.Uniform coverage with behavior probabilities at least µ_min implies C⋆ is bounded by µ_min^-1.Source: §1.1 · pp. 4–5
  • LCB forms policy-value lower confidence bounds from batch data and maximizes them without knowing C⋆, achieving almost optimal performance in bandits and MDPs and optimal performance in contextual bandits.The method is designed to accommodate the full data-composition range rather than requiring prior knowledge of dataset composition.Source: §1.1 · pp. 4–5

1.2 Main results

  • In multi-armed bandits, LCB achieves C⋆/N sub-optimality and is adaptively optimal for C⋆∈[2,∞), while C⋆∈[1,2) has optimal rate e^-N via the most-played-arm algorithm.LCB cannot be adaptively optimal over every C⋆≥1 range when the relevant C⋆ range is unknown.Source: §1.2 · p. 6
  • LCB is minimax optimal across all C⋆ regimes for contextual bandits with at least two contexts, smoothly transitioning from imitation learning to offline RL rates.For C⋆∈[1,1+S/N), the rate is S/N; for C⋆≥1+S/N, it is S(C⋆−1)/N.Source: §1.2 · p. 7
  • In MDPs, LCB with value iteration attains S/N near C⋆=1 and SC⋆/N for C⋆≥1.1, with minimax optimality up to a 1/(1−γ)^2 sample-complexity factor.The intermediate regime C⋆∈(1+1/N,1.1) remains a gap, although the authors conjecture full adaptive optimality and exhibit an episodic variant closing it.Source: §1.2 · pp. 7–8

2 Background and problem formulation

This section formalizes the discounted MDP setting, offline batch-data model, policy-value objectives, and coverage assumptions that underpin the offline RL framework. It emphasizes single-policy concentrability as a weaker alternative to uniform coverage.

2.1 Markov decision processes

  • The environment is an infinite-horizon discounted MDP with finite states and actions, transition kernel P, bounded rewards, initial distribution ρ, and discount factor γ.Rewards lie in [0,1], and γ ∈ [0,1).Source: §2.1 · p. 8
  • A stationary deterministic policy maps states to actions, inducing value and Q-functions bounded between 0 and Vmax.The expected policy value summarizes performance, and an optimal stationary deterministic policy π⋆ maximizes values for all states and expected performance.Source: §2.1 · pp. 8–9
  • Discounted state and state-action occupancy measures record normalized visitation frequencies under a policy from the initial distribution.These measures quantify how policies distribute visitation across states and actions.Source: §2.1 · p. 9

2.2 Offline data and offline RL

  • Offline RL uses a fixed batch D of (s,a,r,s′) transitions, with state-action pairs sampled i.i.d. from an unknown distribution μ.N(s,a) counts observations of each pair, while N=|D| is the total sample size.Source: §2.2 · p. 9

2.3 Assumptions on the dataset coverage

  • Single-policy concentrability Cπ measures distribution shift between a policy’s normalized occupancy measure and the data distribution μ.The coefficient is defined as the smallest constant satisfying the corresponding coverage inequality.Source: §2.3 · pp. 9–10
  • For the optimal policy, C⋆=Cπ⋆ can be substantially smaller than uniform concentrability C, which maximizes Cπ over all policies.Thus, small C⋆ requires coverage of state-action pairs visited by the optimal policy, whereas small C requires coverage for every policy.Source: §2.3 · p. 10

3 A warm-up: LCB in multi-armed bandits

The bandit warm-up shows why empirical reward maximization fails under uneven coverage and how pessimistic lower confidence bounds improve performance. It then characterizes LCB’s near-optimality, the sharper imitation-learning rate, and LCB’s inability to adapt across regimes.

3.1 Why does the empirical best arm fail?

  • The empirical best arm fails because a sparsely observed sub-optimal arm can receive an unusually high reward and overwhelm the well-covered optimal arm.This failure occurs even in a benign instance where the optimal arm is drawn with dominant probability and sub-optimal arms are sparse.Source: §3.1 · pp. 10–11

3.2 LCB: The benefit of pessimism

  • LCB penalizes arms with few observations, selecting the arm with the largest empirical reward minus a count-dependent penalty interpreted as a lower confidence bound.The penalty shrinks as N(a) increases and rules out highly variable empirical rewards caused by small sample counts.Source: §3.2 · pp. 11–12
  • LCB achieves sub-optimality on the order of (log N)/N on the failure instance, improving over the empirical best arm’s constant error.The empirical best arm can select a sparsely observed sub-optimal arm because of a high empirical reward by chance, even when C⋆≈1.Source: §3.1 · pp. 10–11, §3.2 · p. 11

3.3 Is LCB optimal for solving offline multi-armed bandits?

  • For C⋆≥2, LCB is optimal up to a logarithmic factor under the minimax criterion for offline multi-armed bandits.The bandit family contains behavior and reward distributions satisfying 1/µ(a⋆) ≤ C⋆, and the risk is evaluated over this family.Source: §3.3 · pp. 12–13

3.4 Imitation learning in bandit: The most played arm achieves a better rate

  • When C⋆∈[1, 2), selecting the most frequently observed arm achieves an exponential dependence on N, outperforming LCB’s 1/N upper bound.The most-played-arm method fails when C⋆>2, whereas LCB retains a 1/N rate; as C⋆→1, its dependence becomes 1/(C⋆−1)N.Source: §3.4 · p. 13

3.5 Non-adaptivity of LCB

  • No single LCB parameter is optimally adaptive in both regimes: choices yielding the exponential rate for C⋆∈(1, 2) fail to achieve 1/N when C⋆≥6.As the penalty weight grows, LCB approaches the most-played-arm algorithm; as it shrinks, LCB approaches the empirical best arm.Source: §3.5 · pp. 13–14

4 LCB in contextual bandits

In contextual bandits, LCB extends pessimistic offline learning beyond the single-state case and achieves near-optimal, composition-adaptive rates for datasets ranging from nearly expert to broadly covered. Its analysis and lower bound show why multiple states create a missing-mass barrier absent in multi-armed bandits.

4.1 Algorithm and its performance guarantee

  • The contextual-bandit LCB algorithm estimates every state-action reward, subtracts a pessimistic penalty, and selects the action with the largest lower confidence bound in each state.Algorithm 2 generalizes the multi-armed-bandit LCB procedure to contextual bandits.Source: §4.1 · pp. 14–15

4.2 Optimality of LCB for solving offline contextual bandits

  • LCB achieves a near-optimal rate for contextual bandits with at least two states across the entire data-composition range, smoothly transitioning from 1/N near expert data toward the usual offline-learning rate.The upper bound separates a statistical estimation term from missing mass; its dependence on composition is C⋆−1 rather than C⋆, yielding 1/N when C⋆ is close to one without knowing C⋆ or the behavior policy.Source: §4.1 · p. 15, §4.2 · p. 16
  • With at least two states, the information-theoretic difficulty is 1/N in the nearly expert regime because an optimal action can remain unobserved for at least one state.For one state, the corresponding missing-action probability decays exponentially, whereas multiple states produce the slower missing-mass behavior.Source: §4.2 · p. 16

4.3 Architecture of the proof

  • The most-played-arm policy fails to achieve a vanishing rate when C⋆∈(1, 2), whereas LCB remains near-optimal because pessimism handles state-wise missing mass and uneven action coverage.The proof decomposes errors by missing optimal actions, confidence validity, state weights, and whether optimal actions are more likely than suboptimal actions in the data.Source: §4.2 · p. 16, §4.3 · pp. 16–18

5 LCB in Markov decision processes

VI-LCB extends lower-confidence-bound value iteration to offline MDPs, combining pessimistic updates with data splitting and monotonic improvement. Its guarantees recover fast imitation-learning rates near C⋆=1, while lower bounds expose a remaining middling-regime and effective-horizon gap.

5.1 Offline value iteration with LCB

  • VI-LCB subtracts a penalty from empirical reward and transition estimates, using data splitting and monotonic updates to improve the analysis.Data splitting removes an extra factor of S in sample complexity, while monotonic updates shave a 1/(1−γ) factor.Source: §5.1 · p. 19

5.2 Performance guarantees of VI-LCB

  • VI-LCB enjoys a rate of 1/N, as in imitation learning, when 1 ≤ C⋆ ≤ 1 + L log(N)/(200(1−γ)N), while an upper bound is guaranteed for all C⋆≥1.Source: §5.2 · pp. 20–21

5.3 Information-theoretic lower bound for offline RL in MDPs

  • The MDP lower bound contains separate imitation-learning and large-C⋆ terms, with C⋆−1 dependence differing from VI-LCB’s upper bound.The comparison establishes the statistical limit for any C⋆≥1 when γ≥0.5.Source: §5.3 · p. 21
  • The VI-LCB upper bound is loose by an extra 1/(1−γ)^2 sample-complexity factor, potentially removable with Bernstein penalties and variance reduction.This gap is identified by comparing Theorems 6 and 7.Source: §5.3 · p. 22

5.4 What happens when C⋆∈[1 + Ω(1/N), 1 + O(1)]?

  • In the middling regime C⋆∈[1 + Ω(1/N), 1 + O(1)], VI-LCB’s C⋆ dependence is unresolved because MDP error propagation complicates tight action-selection analysis.An episodic example closes the C⋆ gap using a value-gap decomposition with threshold (C⋆−1)/N.Source: §5.4 · pp. 22–23

6 Related work

This section situates the paper’s dataset-coverage assumptions, conservative offline-RL methods, and information-theoretic lower bounds relative to prior work. Its central distinction is coverage through the best concentrability coefficient C⋆ and lower bounds spanning the full data spectrum, including imitation learning.

6.1 Assumptions on batch dataset

  • The paper requires coverage only over states and actions visited by an optimal policy, using the “best” concentrability coefficient C⋆ rather than stronger all-policy or uniformly lower-bounded coverage assumptions.Existing definitions often bound density ratios over all state-action pairs and policies, whereas uniformly lower-bounded or generative-model assumptions are stronger than bounded C⋆.Source: §6.1 · p. 23

6.2 Conservatism in offline RL

  • Policy-regularization methods target nearly-expert datasets, while value-based and pessimistic-model methods impose stronger coverage or lack the paper’s adaptivity and horizon guarantees.MSB-QI has horizon dependence 1/(1 −γ)4 versus the paper’s 1/(1 −γ)2.5; Jin et al. (2020) has tabular gap SAH versus the paper’s H and does not study data-composition adaptivity.Source: §6.2 · p. 24
  • Yin et al. (2021) proves matching bounds under a uniform lower bound tracing an optimal policy, but that stronger characterization does not recover imitation learning when behavior equals the optimal policy.Their assumption can require optimal actions in states not visited by an optimal policy, and the data-distribution lower bound may remain small even when behavior is optimal.Source: §6.2 · p. 24

6.3 Information-theoretic lower bounds

  • Unlike prior lower bounds, the paper’s bounds depend on C⋆ and hold across the entire data spectrum, including an information-theoretic lower bound for any algorithm when C⋆ = 1.The imitation-learning lower bound adapts Rajaraman et al. (2020) to the discounted setting, whereas Xu et al. (2020) analyzes behavior cloning specifically.Source: §6.3 · pp. 24–25

7 Discussion · A Proofs for multi-armed bandits

The framework unifies expert and uniform-coverage offline data through single-policy concentrability, while LCB is adaptively optimal in contextual bandits but has mixed adaptivity elsewhere. The discussion identifies MDP gaps, horizon dependence, tabular limitations, and alternative algorithms as future directions, while Appendix A outlines the multi-armed-bandit proofs.

7 Discussion

  • LCB is adaptively minimax optimal for contextual bandits, smoothly transitioning from a 1/N rate near expert data to 1/√N under typical offline RL.N denotes the batch-dataset sample size.Source: §7 · p. 25
  • The framework uses a single-policy concentrability coefficient to interpolate between expert and uniform-coverage datasets and supports algorithms that need not know data composition.Source: §7 · p. 25
  • For offline multi-armed bandits, LCB is optimal across a wide range of data compositions but is provably non-adaptive near expert data without composition knowledge.Source: §7 · p. 25
  • For MDPs, LCB is adaptively rate-optimal when C⋆ is extremely close to 1 or C⋆≥1+constant, while optimality across the full spectrum remains conjectural.Source: §7 · p. 25
  • Future work should tighten MDP upper bounds when C lies in (1+Ω(1/N), 1+o(1)), especially when much data comes from the optimal policy.Source: §7 · p. 25
  • The analysis leaves a 1/(1−γ)^2 sample-complexity gap for infinite-horizon discounted MDPs; Bernstein penalties, variance reduction, or cross-iteration data reuse may help.Source: §7 · p. 25
  • The paper studies tabular problems, motivating extensions to function approximation and investigations of value-regularization methods for adaptivity or minimax optimality.Source: §7 · p. 25

A Proofs for multi-armed bandits

  • Appendix A proves empirical-arm failure, derives LCB upper and minimax lower bounds, and establishes LCB’s lack of adaptivity for offline multi-armed bandits.Source: A Proofs for multi-armed bandits · p. 33

A.1 Proof of Proposition 1

The proof constructs a two-arm bandit instance where the optimal arm is rarely absent from the offline data, causing the empirical best arm to perform poorly with constant probability. For sufficiently large N, the key event occurs with probability at least 0.36, yielding the claimed lower bound after rescaling ϵ.

A.1 Proof of Proposition 1

  • The construction uses two arms with optimal arm 1, behavior probabilities µ(1)=(N−1)/N and µ(2)=1/N, and reward R(1)=2ϵ almost surely.Source: §A.1 · p. 33
  • On this event, the empirical best arm performs poorly with high probability, and the construction has reward gap r(1)−r(2)=0.95ϵ before rescaling ϵ completes the proof.Source: §A.1 · p. 33
  • For N≥500, the proof establishes that event E1 occurs with probability at least 0.36, uniformly over 0≤n≤N.Source: §A.1 · p. 33

A.2 Proof of Theorem 1 … B Proofs for contextual bandits

The appendix proves the main bandit guarantees and lower bounds using concentration inequalities, confidence bounds, and Le Cam’s two-point method. It also introduces the contextual-bandit proof structure, covering LCB guarantees, minimax lower bounds, and failure of the most-played-arm approach.

A.2 Proof of Theorem 1

  • Theorem 1 is proved by sandwiching each true mean reward between its empirical estimate and a penalty term, then applying a union bound over actions.The confidence relation follows from Hoeffding’s inequality, including the zero-count case, and the proof conditions on the event that the relevant bounds hold.Source: §A.2 · pp. 33–34
  • The A.2 proof completes its high-probability guarantee by conditioning on the joint confidence event and verifying its probability under N≥8C⋆log(1/δ).The expected sub-optimality argument then uses the same bound together with µ(a⋆)≥1/C⋆ and δ=1/N.Source: §A.2 · p. 34

A.3 Proof of Theorem 2

  • Theorem 2’s lower bound uses Le Cam’s two-point method to construct hard-to-distinguish two-armed bandit instances for both C⋆≥2 and C⋆∈(1, 2).For C⋆≥2, the behavior distribution is shared across reward instances; for C⋆∈(1, 2), both behavior and reward distributions differ.Source: §A.3 · p. 35, The case of C⋆∈(1, 2) · pp. 35–36
  • The lower-bound constructions quantify indistinguishability through KL divergence between the resulting offline bandit data distributions.For Bernoulli rewards, the proof invokes a quadratic KL upper bound before choosing the separation parameter to obtain the desired lower bound.Source: §A.3 · p. 35

A.4 Proof of Proposition 2

  • Proposition 2 controls the probability of selecting a suboptimal arm by reducing the error event to an unusually low count for the optimal arm and applying a Chernoff bound.The argument uses bounded rewards to relate expected sub-optimality to the probability of choosing the wrong arm.Source: §A.4 · p. 36

A.5 Proof of Theorem 3

  • Theorem 3 establishes lower bounds on LCB performance through explicit two-armed constructions analyzed separately at C⋆=1.5 and C⋆=6.The constructions assign deterministic or Bernoulli rewards to the optimal and suboptimal arms, and the proof combines LCB comparisons with binomial-tail and KL-divergence bounds.Source: §A.5 · pp. 36, 38

B Proofs for contextual bandits

  • The contextual-bandit appendix is organized around proving the LCB sub-optimality guarantee, a minimax lower bound, and the failure of the most-played-arm approach.These results are developed respectively in Sections B.1, B.2, and B.3.Source: B Proofs for contextual bandits · p. 39

B.1 Proof of Theorem 4 · B.1.1 Proof of the bound (35a) on T1

The proof establishes a stronger version of Theorem 4 for any deterministic expert policy, then recovers the theorem by choosing the optimal expert policy. It decomposes LCB suboptimality into missing-mass, good-event estimation, and failure-event terms, with the first bounded using the weak concentrability condition.

B.1 Proof of Theorem 4

  • The proof analyzes Algorithm 2 for a deterministic expert policy π that need not be optimal, and Theorem 4 follows by setting π = π⋆.This generalization is the proof’s main strengthening before specializing to the optimal expert policy.Source: §B.1 · p. 39
  • LCB suboptimality is decomposed into T1, T2, and T3, representing missing expert-action mass, error on the good event, and suboptimality on its complement.T1 concerns states where the expert action is absent from the dataset; T2 and T3 cover the good-event and failure-event contributions.Source: §B.1 · p. 39
  • The three error terms receive separate upper bounds, which are combined with the bounded expected performance difference to obtain the theorem’s overall guarantee.The component bounds are proved in subsequent subsections, and the final combination uses E_D[J(π) − J(π̂)] ≤ 1.Source: §B.1 · pp. 39–40
  • The final bound is simplified by distinguishing whether C_π is at least 2 or below 2, omitting an extra C_π factor in the second term when C_π < 2.This case distinction yields the desired claim in Theorem 4.Source: §B.1 · p. 40

B.1.1 Proof of the bound (35a) on T1

  • The T1 bound uses the weak concentrability condition ρ(s)μ(s,π(s)) ≤ C_π to control the contribution from missing expert actions.The proof continues the upper bound on T1 after applying this condition.Source: §B.1.1 · p. 40
  • The final step in bounding T1 relies on max_{x∈[0,1]} x(1 − x)^N ≤ 4/(9N), producing the stated 1/N-type factor.The supplied passage identifies this maximization inequality as the justification for the last bound.Source: §B.1.1 · p. 40

B.1.2 Proof of the bound (35b) on T2 · B.1.3 Proof of the bound (35c) on T3

The proof of (35b) partitions states and decomposes T2, controlling expert-dominated states through action-selection concentration and the remaining terms through confidence bounds. The proof of (35c) applies Hoeffding’s inequality and a union bound to show the bad event contributes at most δ, yielding T3 ≤ 1/N when δ = 1/N.

B.1.2 Proof of the bound (35b) on T2

  • B.1.2 partitions the state space into three disjoint sets, distinguishing less-important states from states where the expert action is sampled more frequently under μ.This partition enables a corresponding decomposition of T2.Source: §B.1.2 · p. 40
  • For states in S2, the proof separates suboptimal actions into A1(s) and A2(s), then bounds policy mistakes through events where an action’s lower confidence estimate exceeds the expert action’s.The construction uses A2(s) for suboptimal actions with behavior probability above L/(200N).Source: §B.1.2 · p. 41
  • When expert actions are sampled much more frequently, concentration implies that LCB selects the optimal action with high probability, controlling the corresponding contribution to T2.The proof uses the coverage relationship between expert and non-expert action frequencies together with Chernoff bounds.Source: §B.1.2 · p. 42
  • The A2(s) contribution is bounded using a high-probability event for sample-count concentration, Chernoff and union bounds, and the cardinality bound |A2(s)| ≲ N.The resulting intermediate bound is ρ(s)p2(s) ≲ 1/N^9.Source: §B.1.2 · pp. 41, 43
  • The T2,3 term is controlled on the good event by the LCB definition, the confidence-radius bound, Cauchy–Schwarz, and the assumption max_s ρ(s)/μ(s, π(s)) ≤ Cπ.The final step also uses the definition of S3 to bound the relevant probability.Source: §B.1.2 · p. 44

B.1.3 Proof of the bound (35c) on T3

  • For T3, zero-count pairs satisfy the confidence inequality trivially, while positive-count pairs are handled with Hoeffding’s inequality and the definition of b(s, a).This establishes the per-pair deviation bound needed for the union-bound argument.Source: §B.1.3 · p. 45
  • B.1.3 proves T3 ≤ δ by bounding each reward-estimation failure probability and applying a union bound over all state-action pairs; setting δ = 1/N gives T3 ≤ 1/N.For fixed (s, a), the failure probability is at most δ/(S|A|).Source: §B.1.3 · p. 45

B.2 Proof of Theorem 5 … C.4 Proof of Lemma 2

The proofs establish Theorem 5 through regime-specific contextual-bandit lower bounds and show that Proposition 3 can fail even with unlimited data. The MDP proofs develop Bellman identities and establish the confidence-bound, monotonicity, and value-difference properties needed for later guarantees.

B.2 Proof of Theorem 5

  • Theorem 5’s lower bound is proved separately for C⋆=1, C⋆∈(1,2), and C⋆≥2, using imitation-learning reductions or hard contextual-bandit instances with Fano’s inequality.For C⋆=1, the problem reduces to imitation learning and invokes a lower bound from Rajaraman et al. (2020); the other regimes generalize multi-armed-bandit constructions.Source: §B.2 · pp. 45–46
  • The hard-instance construction uses separated reward distributions whose dataset divergences are controlled, yielding the claimed lower bounds after combining the three regimes.The construction uses a Gilbert–Varshamov family with exponentially many separated vectors, while the KL bound scales as 16δ^2 in one regime and 16(C⋆−1)δ^2/C⋆ in another.Source: §B.2 · pp. 46–48

B.3 Proof of Proposition 3

  • Proposition 3 constructs a two-state MDP in which µ(s0,a0)<µ(s0,a1), so the algorithm fails to identify optimal arm a0 even as N→∞.Taking ϵ→0 gives the proposition’s conclusion under the stated concentrability-valid distributions.Source: §B.3 · p. 48

C Proofs for MDPs

  • The MDP proof sequence introduces Bellman equations for values and discounted occupancy measures before proving algorithmic properties, LCB suboptimality, minimax lower bounds, and imitation-learning results.The occupancy measures satisfy dπ = (1 −γ)ρ + γdπPπ and dπ = (1 −γ)ρ(I −γPπ)^−1, with analogous equations for ρπ.Source: C Proofs for MDPs · p. 48, §C.1 · p. 49

C.2 Proof of Lemma 1

  • Lemma 1 establishes the algorithm’s confidence bounds by separating zero-count and positive-count cases, applying Hoeffding’s inequality, and taking a union bound over states, actions, and time.The union bound uses δ1 = δ/[2S|A|(T+1)].Source: §C.2 · p. 49

C.3 Proof of Proposition 4

  • The proof establishes Vt−1 ≤ Vt ≤ Vπt and recursively bounds Qπ−Qt by γPπ(Qπ−Qt−1)+2bt under the clean event EMDP.The step Vt ≤ Vπt uses Bellman-operator monotonicity.Source: §C.3 · pp. 49–50

C.4 Proof of Lemma 2

  • Lemma 2 converts the value gap into ρπ(Qπ−Qt) and repeatedly applies Proposition 4’s recursion to obtain the desired discounted error bound.The proof uses that Vmid_t is greedy with respect to Qt, the identity Eρ[Vπ−Vπt]≤ρπ(Qπ−Qt), and powers of γPπ.Source: §C.4 · pp. 50–51

C.5 Proof of Theorem 6 … C.5.4 Proof of the bound (56b) on T ′2

The proof establishes a stronger version of Theorem 6 for any deterministic expert policy under the data-coverage assumption. It handles general and nearly expert regimes by decomposing sub-optimality into coverage, clean-event, and failure-event terms, then bounding each component.

C.5 Proof of Theorem 6

  • The proof splits into the general regime C_π ≥ 1 and the nearly-expert regime C_π ≤ 1 + L/(200m).In the general case, sub-optimality is decomposed into T1, T2, and T3, corresponding respectively to missing expert-action mass, the clean event, and its complement.Source: §C.5 · pp. 51–52
  • Algorithm 3 achieves the stated general and tighter nearly-expert performance bounds, with the latter applying when C_π is sufficiently close to one.Theorem 6 follows by setting π = π⋆; the proof uses δ = 1/N and T = log N/(1 −γ).Source: §C.5 · pp. 51–52
  • The general-case bounds imply the desired claim because, in the interesting regime S C_π(1 −γ)^3/N ≤ 1, the leading term dominates while policy sub-optimality is always at most 1/(1 −γ).The parameter choices δ = 1/N and T = log N/(1 −γ) also ensure γ^T ≤ 1/N.Source: §C.5 · p. 52
  • The nearly-expert analysis links policy sub-optimality to disagreement with the expert policy and separates disagreement into states with missing expert-action samples and states with observed expert actions.This decomposition yields the bound corresponding to (53) after setting δ = 1/N and T = log N/(1 −γ).Source: §C.5 · p. 53

C.5.1 Proof of the bound (54a) on T1 and the bound (56a) on T ′

  • The bound on T1 and T′1 follows from occupancy domination by the expert-action coverage coefficient, a union bound, and m = N/(T + 1).The T′1 argument is identical after replacing the normalized occupancy measure ρ with d_π.Source: §C.5.1 · p. 53

C.5.2 Proof of the bound (54b) on T2

  • The bound on T2 is derived on the clean event by substituting the confidence-radius definition, applying Lemma 14, the concentrability assumption, and Cauchy–Schwarz, then using m = N/(T + 1).The T3 bound is obtained separately using Lemma 1.Source: §C.5.2 · p. 54, §C.5.3 · p. 54

C.5.4 Proof of the bound (56b) on T ′2

  • For T′2, the proof partitions states into less-important and remaining sets, then bounds β1 and β2 using the fact that expert actions are sampled much more often than non-expert actions.An inclusion argument reduces final disagreement to either an initially incorrect action or a confidence-bound comparison favoring a non-expert action; Chernoff bounds then control these events.Source: §C.5.4 · pp. 55–57

C.6 Proof of Theorem 7 · C.6.1 Proof of Lemma 7

Theorem 7’s lower bound is proved separately for C⋆=1, C⋆∈(1,2), and C⋆≥2 using discounted imitation-learning and hard-MDP constructions. Lemma 7 establishes the pairwise loss separation needed for the Fano argument.

C.6 Proof of Theorem 7

  • The proof splits into C⋆=1, C⋆≥2, and C⋆∈(1,2), adapting imitation-learning lower bounds or reducing MDP policy learning to bandits.The initial distribution ρ is designed to incorporate C⋆ into the lower bound.Source: §C.6 · p. 57
  • For C⋆=1, the behavior occupancy equals the expert occupancy, so the discounted lower bound is adapted from Rajaraman et al. (2020).This is the imitation-learning setting, with the episodic analysis changed to the discounted setting.Source: §C.6 · p. 57
  • The hard MDP uses S/4 four-state replicas plus an absorbing zero-reward state, with transition uncertainty encoded by vj∈{−1,+1} and δ.Only s1 has two actions; s⊕ is the sole rewarding state, reducing policy learning to repeated action choices.Source: §C.6 · pp. 57–58
  • A Gilbert–Varshamov code supplies a family V with |V|≥exp(S/32) and pairwise Hamming distance at least S/8, producing nearly indistinguishable dynamics.Each codeword determines transition probabilities at the decision states.Source: §C.6 · p. 59

C.6.1 Proof of Lemma 7

  • Lemma 7 proves that any policy has combined loss L(π;P1)+L(π;P2) ≥ δ/[32(1−γ)] for distinct transition dynamics.The proof connects value differences to δ and then uses the code family’s pairwise separation.Source: §C.6 · p. 59, §C.6.1 · pp. 62–63

C.6 Proof of Theorem 7

  • For C⋆≥2, the construction yields E[L(π̂;P)] ≳ δ/(1−γ), and choosing δ according to the KL constraint gives lower bound (62).Fano’s inequality is applied to a family of nearly indistinguishable transition dynamics.Source: §C.6 · p. 60
  • For C⋆∈(1,2), the proof changes ρ0 and µ0, incorporates an extra C⋆−1 factor, and selects δ to obtain lower bound (63).The final choice is δ = 1/4 when the stated sample-size condition fails.Source: §C.6 · pp. 60–61
  • The three case-specific lower bounds (61)–(63) combine to establish Theorem 7 across the full range of C⋆.The C⋆=1 case matches (61), C⋆≥2 follows from (62), and C⋆∈(1,2) combines (61) and (63).Source: §C.6 · p. 61

C.6.2 Proof of Lemma 6 … D.5 The case of Cπ ∈[1, 2)

This section develops lower-bound and finite-sample analysis for imitation learning and episodic LCB value iteration under conditional coverage. It establishes value-difference and sub-optimality bounds across general and nearly expert regimes, while examining the unresolved case of $C_pi \in [1,2)$.

C.6.2 Proof of Lemma 6

  • Under C⋆=1, the lower-bound construction makes the optimal policy uniform over dataset-compatible policies, with unseen-state actions remaining uniformly unknown.The hard MDP rewards optimal actions and sends other actions to an absorbing zero-reward bad state, linking suboptimality to the first unobserved state encountered.Source: §C.6.2 · pp. 63–64, Figure 6 · p. 64

C.7 Imitation learning in discounted MDPs

  • Behavior cloning under conditional density-ratio coverage achieves expected suboptimality bounded by S/[C0N(1−γ)^2] for C⋆∈[1,2).The proof decomposes error into unobserved states and states where the optimal action is not most frequent, using Chernoff control for the latter.Source: §C.7 · pp. 66–67

D.1 Model and notation

  • The episodic setting uses finite-horizon MDPs with i.i.d. state-action batch samples, deterministic policies, occupancy measures, and concentrability coefficient Cπ.Algorithm 4 applies backward value iteration with lower-confidence penalties to empirical rewards and transitions.Source: §D.1 · pp. 68–69

D.2 Episodic value iteration with LCB

  • Algorithm 4 computes episodic values by backward recursion while subtracting lower-confidence penalties from empirical Q-functions, following the value-iteration framework of Jin et al. (2020).Theorem 9 analyzes the policy returned by this penalized recursion under an arbitrary deterministic comparison policy.Source: §D.2 · pp. 69–70
  • Theorem 9 gives episodic LCB sub-optimality guarantees for all Cπ≥1 and a tighter bound when 1≤Cπ≤1+L/(200N).The analysis also conjectures a smooth transition from 1/N to 1/√N as Cπ increases from 1 to 2.Source: §D.2 · p. 70

D.3 Properties of Algorithm 4

  • The episodic analysis proves that the clean event holds with probability at least 1−δ and that Algorithm 4’s suboptimality is bounded through an expected-bonus value-difference lemma.The confidence argument uses independence from disjoint state levels and Hoeffding’s inequality, followed by a union bound.Source: §D.3 · pp. 70–71
  • Lemma 11 provides a value-difference guarantee for Algorithm 4 on the event EEMDP.The proof uses a self-consistency error, Bellman operators, the maximization defining the returned policy, and occupancy measures.Source: §D.3 · pp. 71–72

D.4 Proof of Theorem 9

  • Theorem 9 is proved by separately treating the general regime Cπ ≥ 1 and the nearly expert regime C⋆ ≤ 1 + L/(200N).The proof decomposes sub-optimality into a clean-event term T1 and a confidence-interval failure term T2, then sets δ = 1/N.Source: §D.4 · p. 72

D.4.2 Proof of the bound (88b) on T2

  • The bound on T2 controls sub-optimality when the penalty-based confidence interval fails to contain the empirical Q-function estimate.The argument invokes Lemma 10 after bounding the relevant value difference.Source: §D.4 · p. 72, §D.4.2 · p. 73

D.4.1 Proof the bound (88a) on T1

  • The bound on T1 follows from Lemma 11, inverse binomial-moment bounds, the concentrability assumption, and Cauchy–Schwarz.This establishes the clean-event contribution to the general-regime analysis.Source: §D.4.1 · p. 73

D.4.3 Proof of the bound (89a) on T′1

  • The bound on T′1 controls disagreement states with no observed samples using occupancy probabilities and the concentrability assumption.The proof also uses max_x∈[0,1] x(1 − x)^N ≤ 4/(9N).Source: §D.4.3 · pp. 73–74

D.4.4 Proof of the bound (89b) on T′2

  • For T′2, states are partitioned by target-policy occupancy, and when the target action is included more frequently, the LCB algorithm picks it with high probability.The cited analysis uses N(s, π(s)) ≥ L and L ≥ 70 in establishing the comparison.Source: §D.4.4 · pp. 74–75

D.5 The case of Cπ ∈[1, 2)

  • For Cπ ∈ [1, 2), the analysis decomposes T1 by states where the expert action is more frequently sampled, proves a bound on β1, and conjectures an analogous β2 bound.The β2 conjecture is demonstrated only for an episodic MDP with H = 3, |S_h| = 2, and |A| = 2 in Appendix D.6.Source: §D.5 · pp. 75–76

D.6 Analysis of LCB for a simple episodic MDP · E Auxiliary lemmas

The simple episodic-MDP analysis shows how concentrability and dataset imbalance enable VI-LCB to identify optimal actions with high probability and bound suboptimality. Auxiliary lemmas provide the concentration, binomial inverse-moment, and packing tools used in the broader LCB analysis.

D.6 Analysis of LCB for a simple episodic MDP

  • In the H = 3 episodic MDP, deterministic rewards, concentrability, and μ(s, 1) ≥ 9μ(s, 2) define the setting for analyzing β2 when Cπ ∈ [1, 2).The analysis assumes N(s, a) ≥ 1 and action 1 is optimal in every state.Source: §D.6 · p. 77
  • The suboptimality analysis decomposes performance by the level-2 optimal-action event and by state gaps, making small-gap losses small and large-gap action errors negligible.Conditioned on the event, LCB-VI chooses optimal actions at levels 2 and 3, while Hoeffding concentration controls wrong-action probabilities for large gaps.Source: §D.6 · pp. 78, 80
  • VI-LCB selects the optimal action at level 3 exactly and, using penalty comparisons plus concentration, selects action 1 at levels 2 and 1 with high probability.At level 2, the expected Q-value difference is nonnegative under the penalty bounds; the level-1 argument proceeds similarly.Source: §D.6 · pp. 78–79
  • The resulting bound combines the two suboptimality contributions, including τ2 ≲ 3 N160 and an additional term proportional to (N + 1) N160.The displayed excerpts provide the component and combined bound forms but omit enough surrounding formula text to reconstruct their exact interpretation.Source: §D.6 · pp. 80–81
  • The penalty comparisons rely on μ(s, 1) ≥ 9μ(s, 2), which implies N(s, 1) ≥ 9N(s, 2), together with concentrability-based bounds on optimal-action mass.These relations establish the penalty inequalities used throughout the level-wise policy analysis.Source: §D.6 · p. 81

E Auxiliary lemmas

  • Lemma 13 extends Hoeffding’s inequality to independent samples from two bounded distributions, giving a bound under the condition ϵ + E[Y] − E[X] ≥ 0.The samples are i.i.d. in [0, 1] and independent across the two groups.Source: E Auxiliary lemmas · p. 81
  • Lemma 14 bounds inverse moments of n ∼ Binomial(N, p) by constants depending only on k, using a decomposition and separate treatment of small and larger p.The proof handles p ≤ 1/N directly and analyzes p > 1/N through the helper function gN(p), mean-value arguments, and binomial tails.Source: E Auxiliary lemmas · p. 82
  • Lemma 15 supplies a Gilbert–Varshamov packing: a subset V of {−1, 1}S has size at least exp(S/8) and pairwise ℓ1 distance at least S.This construction is identified as useful for hard instances in minimax lower bounds.Source: E Auxiliary lemmas · p. 83

Related papers

Loading 2103.12021v2…