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 lacks a unified treatment for datasets between expert demonstrations and uniform coverage, especially when composition is unknown. The paper introduces a single-policy concentrability framework and analyzes pessimistic LCB algorithms across bandits, contextual bandits, and MDPs. LCB is adaptively minimax optimal for contextual bandits, while bandits exhibit non-adaptivity and MDPs retain an unresolved intermediate regime.

  • Problem

    Offline RL needs a formulation and algorithm that accommodate varying dataset compositions, including expert and uniform-coverage data, without requiring prior knowledge of composition.

  • Method

    The paper measures composition with the single-policy concentrability coefficient C⋆ and studies lower confidence bound algorithms based on pessimism across three offline decision-making settings.

  • Results

    LCB is adaptively minimax optimal for offline contextual bandits across the full C⋆ range, while it is non-adaptive in some bandit regimes and only partially established for MDPs.

  • Takeaways & Limitations

    The C⋆ framework provides a smooth theoretical bridge between imitation learning and offline RL, with rates transitioning from 1/N near expert data toward 1/√N as composition becomes less expert-like.

  • Takeaways & Limitations

    For MDPs, VI-LCB has an extra 1/(1−γ)^2 factor in sample complexity, and the intermediate C⋆ regime remains unresolved.

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

Offline RL must handle datasets ranging from expert demonstrations to uniform coverage, motivating a framework based on how behavior differs from the optimal policy. The paper analyzes pessimistic LCB methods across bandits, contextual bandits, and MDPs, finding adaptive optimality in contextual bandits but important gaps or failures elsewhere.

  • Motivation: Offline RL datasets range from expert data, where imitation learning is effective, to uniform coverage data, where vanilla offline RL is suited.Uniform coverage aims to cover all states and actions, including those not visited by satisfactory policies.
  • Framework: The framework asks whether algorithms can achieve minimal sub-optimality across C⋆ values without knowing the data composition beforehand.The analysis focuses on a lower confidence bound method based on pessimism in the face of uncertainty.
  • Framework: C⋆ measures the deviation between the behavior distribution and the distribution induced by the optimal policy, interpolating between expert and uniform-coverage regimes.C⋆ = 1 recovers expert data; larger values permit samples from states and actions not visited by the optimal policy.
  • Multi-armed bandits: C⋆/N is achievable by LCB for offline multi-armed bandits when C⋆≥2, but LCB is not adaptively optimal across all C⋆ regimes.For C⋆∈[1,2), the optimal rate is exponential in N and is achieved by selecting the most-played arm, while LCB cannot adapt optimally to both regimes without knowing C⋆.
  • Contextual bandits: S(C⋆−1)/N for C⋆≥1+S/N and S/N for C⋆∈[1,1+S/N) are minimax-optimal contextual-bandit rates, smoothly transitioning from imitation learning to offline RL.LCB matches behavior cloning at C⋆=1 and achieves adaptive optimality across the full data-composition range.
  • Markov decision processes: S/N near C⋆=1 and SC⋆/N when C⋆≥1.1 are minimax-optimal MDP rates up to a 1/(1−γ)^2 factor in sample complexity, while the intermediate regime remains unresolved.The paper conjectures adaptive optimality across all C⋆ values and gives an episodic example closing the C⋆-dependence gap.

2 Background and problem formulation

This section formulates offline RL with fixed batch data and introduces a single-policy concentrability coefficient to characterize coverage of policies of interest. It defines discounted MDP quantities, the offline data model, and how the coefficient bridges expert-driven and broader coverage regimes.

  • 2.1 Markov decision processes: An infinite-horizon discounted MDP comprises finite states and actions, transition and reward distributions, an initial-state distribution, and discount factor γ.The agent receives a random reward and transitions according to the specified kernels after each state-action pair.
  • 2.1 Markov decision processes: A stationary deterministic policy maps each state to an action, while V^π and Q^π quantify discounted future rewards from states and state-action pairs.Both value functions are bounded between 0 and V_max.
  • 2.1 Markov decision processes: The expected policy value J(π) provides a scalar performance summary, and a stationary deterministic policy π⋆ simultaneously maximizes value at every state.The corresponding optimal functions are denoted V⋆ and Q⋆.
  • 2.1 Markov decision processes: Discounted occupancy measures record normalized state and state-action visitation frequencies induced by a policy.The notation Pt(st = s; π) represents the probability of visiting a state at time t under π from the initial distribution.
  • 2.2 Offline data and offline RL: Offline RL uses an inaccessible MDP and an i.i.d. batch dataset of (s, a, r, s′) tuples drawn from an unknown state-action distribution µ.N(s, a) counts observations of each pair, while N is the total dataset size.
  • 2.3 Assumptions on the dataset coverage: Single-policy concentrability C^π is the smallest constant quantifying distribution shift between policy π’s normalized occupancy measure and the data distribution µ.For the optimal policy, the paper writes C⋆ := C^π⋆.
  • 2.3 Assumptions on the dataset coverage: The framework treats expert-driven and broader-coverage datasets through policy-specific coverage rather than imposing coverage of all possible state-action pairs.The i.i.d. data model is motivated by randomization in experience replay.
  • 2.3 Assumptions on the dataset coverage: C⋆ can be much smaller than uniform concentrability because it requires coverage of state-action pairs visited by the optimal policy rather than by every policy.The paper characterizes this as a weaker coverage requirement.

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

The multi-armed-bandit warm-up shows why empirical-best-arm selection is fragile under uneven coverage and motivates lower confidence bounds that penalize poorly observed actions. LCB improves rates in favorable regimes, is near-optimal in broad regimes, but cannot adapt optimally across all coverage regimes without knowing the composition.

  • 3 A warm-up: LCB in multi-armed bandits: Offline MAB learning selects an arm from batch samples to minimize expected sub-optimality, with coverage summarized by the behavior probability of the optimal arm.The dataset contains independently sampled action-reward tuples and r(a) denotes the conditional mean reward.
  • 3.1 Why does the empirical best arm fail?: Selecting the highest empirical mean can fail because a sparsely observed sub-optimal arm may obtain an unusually high reward by chance.The empirical best arm is defined as the arm maximizing its empirical mean.
  • 3.1 Why does the empirical best arm fail?: A failure instance uses an optimal arm with deterministic reward 1/2 and sub-optimal Bernoulli arms with mean 1/4, where a one-time reward of 1 can mislead selection.The optimal arm is drawn with dominant probability while sub-optimal arms are sparsely sampled.
  • 3.2 LCB: The benefit of pessimism: LCB returns the action maximizing empirical reward minus a penalty that decreases with its observation count.The lower confidence bound is motivated by pessimism about poorly sampled actions and can rule out high-variance empirical outliers.
  • 3.2 LCB: The benefit of pessimism: On the empirical-best-arm failure instance, LCB achieves sub-optimality on the order of (log N)/N, improving over the vanilla approach.The bound applies with high probability under a sample-size condition involving C⋆ and log(1/δ).
  • 3.2 LCB: The benefit of pessimism: LCB can compete with any covered target policy, so its output performs nearly as well as a covered policy that need not be optimal.The guarantee is stated for policies selecting a fixed action under an appropriate coverage condition.
  • 3.3 Is LCB optimal for solving offline multi-armed bandits?: For C⋆≥2, LCB is optimal up to a logarithmic factor, while for C⋆∈[1, 2) the most-played-arm method achieves an exponential rate in N.The most-played-arm method fails when C⋆>2, whereas LCB retains a 1/N rate there.
  • 3.5 Non-adaptivity of LCB: LCB cannot be optimally adaptive across near-expert and broader-coverage regimes when C⋆ is unknown.The paper exhibits incompatible parameter choices: near-expert optimality requires a growing threshold, while C⋆≥6 requires δ = 1/N.

4 LCB in contextual bandits

This section extends pessimistic lower-confidence-bound learning to contextual bandits, where data coverage and missing mass determine offline policy quality. LCB achieves composition-adaptive guarantees, including a near-expert 1/N rate and near-optimal performance across the full coverage range.

  • Problem setting: Contextual bandits are MDPs with γ = 0, using independently sampled state-action-reward tuples from the batch dataset.The offline objective is to learn a policy minimizing expected sub-optimality relative to an optimal policy.
  • Algorithm: LCB computes empirical rewards and pessimistic penalties for every state-action pair, then selects the action maximizing the lower confidence bound.Algorithm 2 generalizes the multi-armed-bandit LCB procedure to contextual bandits.
  • Upper bound: Theorem 4 bounds sub-optimality by a statistical estimation term and a missing-mass term for states whose optimal action is unobserved.Missing mass captures states where the batch contains no observation of the optimal arm.
  • Upper bound: When C⋆ is close to one, LCB attains a faster 1/N rate without knowing C⋆ or the behavior policy, and its rate transitions smoothly toward offline-RL behavior.The improved dependence is C⋆−1 rather than C⋆ in the relevant estimation term.
  • Optimality and lower bounds: For contextual bandits with S ≥ 2, LCB is near-optimal for every C⋆, unlike the most-played-arm rule, which can fail to achieve a vanishing rate when C⋆∈(1, 2).The separation from the single-state case is attributed to missing mass when multiple states are present.

5 LCB in Markov decision processes

VI-LCB combines pessimistic lower-confidence updates with value iteration to handle offline MDPs across data-composition regimes. Its guarantees are fast near expert data, broadly near-optimal elsewhere, but retain gaps in intermediate concentrability regimes and effective-horizon dependence.

  • Algorithm: VI-LCB subtracts a penalty from empirical reward and transition estimates before applying the value-iteration update.The core update is Q(s, a) ← ˆr(s, a) − b(s, a) + γ ˆP_s,a · V.
  • Algorithm: Data splitting uses separate samples across iterations, easing dependence issues and removing an extra factor of S from sample complexity.The procedure is analytically useful but not required in practice.
  • Performance guarantees: For all C⋆ ≥ 1, VI-LCB provides a suboptimality guarantee, while its bounds are minimax optimal in the extreme regimes up to a 1/(1 − γ)^2 sample-complexity factor.The broad guarantee transitions between nearly-expert and larger-coverage regimes.
  • Open regime: In the intermediate regime C⋆ ∈ [1 + Ω(1/N), 1 + O(1)], the upper bound does not match the lower bound’s C⋆ − 1 dependence.The paper conjectures that this gap is an artifact of the analysis and illustrates a value-gap decomposition that can close it in an episodic example.
  • Performance guarantees: For nearly expert datasets, with 1 ≤ C⋆ ≤ 1 + L log(N)/(200(1 − γ)N), VI-LCB achieves the imitation-learning rate 1/N.The small-C⋆ regime corresponds to suboptimal actions having very small mass in the behavior distribution.
  • Limitations: VI-LCB’s sample complexity is loose by an extra 1/(1 − γ)^2 factor, which the authors suggest may be removed with Bernstein penalties and variance reduction.This concerns the effective-horizon dependence rather than the data-composition dependence.

6 Related work

Related work frames offline RL around dataset coverage, pessimistic algorithms, and information-theoretic limits. This paper uses a weaker single-policy coverage characterization and studies lower bounds across the full data spectrum.

  • Coverage assumptions: Offline RL faces insufficient coverage and distribution shift between behavior-policy and learned-policy occupancies.Concentrability coefficients characterize this shift through density-ratio bounds.
  • Coverage assumptions: Prior offline RL analyses commonly require density-ratio control over all policies, stronger than the paper’s single-policy concentrability requirement.The paper’s coefficient measures coverage for a specified competing policy rather than every policy.
  • Conservative methods: Existing methods address coverage through policy regularization, conservative value updates, or pessimistic model learning, often retaining strong data-distribution assumptions.Examples include uniformly lower-bounded coverage over state-action pairs visited by competing policies.
  • Lower bounds: The paper’s lower bounds depend on C⋆ and cover the entire data spectrum, including an information-theoretic bound for any algorithm at C⋆ = 1.This differs from prior imitation-learning results focused on behavior cloning.

7 Discussion

The paper proposes a concentrability-based framework that interpolates between expert and uniform-coverage datasets, then studies whether LCB can adapt to unknown composition. Results are strongest for contextual bandits, while MDPs retain an unresolved middle regime and several scope limitations.

  • 7 Discussion: A single-policy concentrability coefficient smoothly interpolates between expert data and uniform-coverage data.The framework targets datasets whose composition is unknown rather than assuming either extreme.
  • 7 Discussion: Contextual-bandit LCB is adaptively minimax optimal across the data-composition range, bridging 1/N and 1/√N rates.The faster 1/N behavior occurs near the expert-policy regime, while 1/√N is the typical offline-RL rate.
  • 7 Discussion: Bandit LCB is optimal across a wide composition range but provably non-adaptive near expert data when composition is unknown.This contrasts with the contextual-bandit result, where adaptation holds throughout the range.
  • 7 Discussion: MDP LCB is adaptively rate-optimal when C⋆ is extremely close to 1 or at least 1+constant, leaving an intermediate regime unresolved.The paper conjectures optimality across the full spectrum but does not establish it in the middle ground.
  • 7 Discussion: The analysis is tabular, has a 1/(1−γ)^2 sample-complexity gap, and leaves function approximation and alternative conservative algorithms for future work.The authors specifically mention Bernstein penalties, variance reduction, data reuse, function approximation, and value regularization as possible directions.

A.1 Proof of Proposition 1

The proof constructs a two-armed offline bandit instance where the optimal arm is clear in expectation but the empirical-best-arm rule can perform poorly with substantial probability. The resulting sub-optimality follows from a fixed-probability event and the reward gap.

  • A.1 Proof of Proposition 1: A two-armed instance sets the optimal arm’s behavior probability to (N−1)/N and its reward deterministically to 2ε.The second arm has behavior probability 1/N, creating a highly imbalanced offline dataset.
  • A.1 Proof of Proposition 1: The optimal arm is optimal by construction, but the empirical-best-arm estimator is intended to perform poorly with high probability.The proof studies the estimator using N offline samples from the specified behavior and reward distributions.
  • A.1 Proof of Proposition 1: For N≥500, the proof obtains P(E1)≥0.36 for every 0≤n≤N.This event supplies a constant-probability basis for the lower-bound argument.
  • A.1 Proof of Proposition 1: The reward gap is r(1)−r(2)=0.95ε, so selecting the empirical-best arm incurs the corresponding sub-optimality on the event.The proof then rescales ε to finish the lower-bound construction.

A.2 Proof of Theorem 1

The proof combines concentration bounds with Le Cam two-point constructions to establish LCB performance guarantees and matching minimax lower bounds across bandit regimes. It also compares these guarantees with the failure of empirical action selection.

  • A.2 Proof of Theorem 1: The confidence penalty satisfies ˆr(a)−b(a)≤r(a)≤ˆr(a)+b(a) simultaneously over actions with high probability.This follows from Hoeffding’s inequality and a union bound, including the zero-count case.
  • A.2 Proof of Theorem 1: LCB’s proof conditions on an event where reward estimates and optimal-action counts are controlled, then bounds the selected policy’s sub-optimality.The count lower bound is obtained using a Chernoff argument and the concentrability condition.
  • A.2 Proof of Theorem 1: Le Cam’s two-point method constructs difficult-to-distinguish MAB instances with different optimal rewards for minimax lower bounds.The construction is split into C⋆≥2 and C⋆∈(1,2), with the latter changing both behavior and reward distributions.
  • A.2 Proof of Theorem 1: For C⋆∈[1,2), the lower-bound construction varies both the behavior distribution and reward distributions across the two instances.For C⋆≥2, the proof instead uses a common behavior distribution with two alternative reward distributions.
  • A.2 Proof of Theorem 1: The proof controls empirical-arm error through the probability of selecting a non-optimal arm and applies Chernoff bounds to the optimal arm’s sample count.This establishes the relevant probability bound before the stated conclusion.
  • A.2 Proof of Theorem 1: The LCB lower-bound arguments separately analyze C⋆=1.5 and C⋆=6 using explicit two-arm reward constructions.These constructions assign deterministic or Bernoulli rewards and lower-bound the probability that LCB chooses the sub-optimal arm.

B.1 Proof of Theorem 4

The contextual-bandit proof derives LCB’s sub-optimality bound by decomposing error into missing expert actions, estimation error, and failure of the confidence event. It then bounds each component under a deterministic expert-policy assumption.

  • B.1 Proof of Theorem 4: The proof fixes a deterministic expert policy that need not be optimal and specializes the theorem to the optimal policy afterward.Taking π=π⋆ recovers the stated theorem.
  • B.1 Proof of Theorem 4: LCB sub-optimality is decomposed into missing-mass error, good-event estimation error, and error on the complement event.The three terms are denoted T1, T2, and T3, respectively.
  • B.1 Proof of Theorem 4: The proof bounds all three error terms and combines them with E_D[J(π)−J(ˆπ)]≤1 to obtain the guarantee.The displayed intermediate bounds include an L/N(s,a) term for observed state-action counts.
  • B.1 Proof of Theorem 4: When Cπ<2, the proof can omit an extra Cπ factor from the second term because the N term dominates.The comparison is made while continuing the upper-bound derivation for the missing-mass term.
  • B.1 Proof of Theorem 4: The contextual-bandit guarantee is obtained under an assumption involving the maximum state-wise quantity used in the proof.The final algebra uses the bound max_{x∈[0,1]} x(1−x)^N≤4/(9N).

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

The proof bounds LCB’s sub-optimality by partitioning states and actions according to importance and data frequency, then controlling each resulting error term with concentration arguments. The resulting bounds exploit frequent expert-action observations to identify the optimal action with high probability.

  • State and action partition: The state space is partitioned into three disjoint sets, including less-important states and states where the expert action is sampled more frequently.This partition supports separate bounds for the decomposed term T2.
  • State and action partition: T2 is decomposed according to the three state sets, allowing each component to be bounded separately.The proof then treats T2,1, T2,2, and T2,3 using their respective state and action conditions.
  • Final bounds: The selected logarithmic confidence radius and sample-count bounds produce inverse-polynomial bounds for the remaining components of T2.The supplied derivation reports bounds involving 1/N^9 and 1/N^10 for separate terms.
  • Concentration control: When the expert action is sampled much more frequently than non-expert actions, LCB selects it with high probability.The proof compares confidence-adjusted empirical rewards using concentrated sample counts and reward estimates.
  • Concentration control: The proof controls reward-estimation failures using Hoeffding’s inequality and a union bound over state-action pairs.Choosing δ = 1/N yields the advertised contribution from the complement of the clean event.

B.2 Proof of Theorem 5

The proof establishes Theorem 5 through regime-specific minimax lower bounds for contextual bandits. It reduces the expert-data case to imitation learning and uses hard, nearly indistinguishable reward instances with Fano’s inequality in the other regimes.

  • Regime-specific lower bounds: The lower-bound proof separates the regimes C⋆ = 1, C⋆ ∈ (1, 2), and C⋆ ≥ 2.The C⋆ = 1 case recovers imitation learning, while the other regimes generalize multi-armed-bandit constructions.
  • Regime-specific lower bounds: For C⋆ = 1, the offline contextual-bandit problem reduces to imitation learning because d⋆(s, a) = µ(s, a).The proof therefore applies an existing imitation-learning lower bound.
  • Hard instances: The hard contextual-bandit instances use S states, two actions per state, and reward distributions indexed by a separated Gilbert–Varshamov code.The code supplies exponentially many reward environments that remain difficult to distinguish from the data.
  • Information-theoretic step: Fano’s inequality converts the large family of nearly indistinguishable reward distributions into a policy-learning lower bound.The proof controls both the family size and pairwise KL divergence.
  • Regime-specific lower bounds: The constructions are adjusted across concentrability regimes by changing the initial and behavior distributions while preserving the contextual-bandit class constraint.The proof then combines the regime-specific bounds to obtain Theorem 5.

C.5 Proof of Theorem 6

The proof of Theorem 6 decomposes MDP sub-optimality into missing expert-action mass, clean-event estimation error, and confidence-event failure. It bounds these terms under general and nearly-expert concentrability regimes.

  • Proof structure: The proof analyzes a deterministic expert policy under the data-coverage assumption and separates the general case from the nearly-expert regime.The tighter regime is Cπ ≤ 1 + L/(200m).
  • Nearly-expert regime: When 1 ≤ Cπ ≤ 1 + L log(N)/(200(1 − γ)N), the analysis gives a tighter performance upper bound.This is the nearly-expert data-coverage regime identified in the theorem statement.
  • Error decomposition: The expected sub-optimality is decomposed into T1, T2, and T3, representing missing expert-action mass, clean-event error, and complement-event error.The complement event is where the empirical Q-function leaves its confidence interval.
  • General bound: For all Cπ ≥ 1, Algorithm 3 with δ = 1/N achieves the theorem’s general performance bound.The proof sets T = log N/(1 − γ) when deriving the final bound.
  • Error control: The proof controls policy disagreement through occupancy measures, concentrability, Cauchy–Schwarz, and bounds on the probabilities of misselection.The MDP argument parallels the contextual-bandit proof while accounting for discounted occupancy.

C.6 Proof of Theorem 7

Theorem 7 is proved with regime-specific minimax lower bounds using hard MDPs built from replicas whose transition probabilities encode hidden binary choices. Fano’s inequality then turns indistinguishability into lower bounds across the concentrability range.

  • Regime-specific construction: The proof treats C⋆ = 1, C⋆ ∈ (1, 2), and C⋆ ≥ 2 separately.The expert-data case adapts imitation-learning lower bounds, while the other cases use a hard MDP reduction to bandits.
  • Hard MDP construction: The hard MDP contains S/4 replicas, with the action choice at each decision state determining transition probabilities toward rewarding or punishing states.Only the transition dynamics at the two-action state vary across replicas.
  • Hard MDP construction: Each replica’s hidden binary parameter determines which of the two actions is optimal.For vj = 1, a2 is optimal; otherwise, a1 is optimal.
  • Information-theoretic step: A separated family of binary vectors yields transition environments with pairwise policy losses bounded below by δ/[32(1 − γ)].The separation follows from the Gilbert–Varshamov construction used for the transition probabilities.
  • Information-theoretic step: Fano’s inequality converts the transition environments’ indistinguishability into an expected sub-optimality lower bound.The proof controls the KL divergence between data distributions and then combines the three regime-specific bounds.

C.6.2 Proof of Lemma 6

For C⋆=1, the lower-bound construction makes the optimal action known on dataset-visited states while leaving it uniformly ambiguous elsewhere. The resulting analysis relates suboptimality to encountering unobserved states and compares imitation learning with LCB under different C⋆ regimes.

  • Construction and conditional distribution: When C⋆=1, d⋆=µ, corresponding to the imitation-learning setting used for the discounted-MDP lower bound.The analysis adapts an episodic-MDP information-theoretic lower bound to the discounted setting.
  • Construction and conditional distribution: The hard-instance distribution is generated by sampling the deterministic optimal policy uniformly and then constructing a deterministic MDP conditioned on it.The construction uses an initial distribution with ζ=1/(N+1), a rewarding optimal action, and a zero-reward absorbing bad state.
  • Construction and conditional distribution: Conditioned on the dataset, the optimal policy is uniform over policies compatible with observed actions, with optimal actions fixed on visited states and uniform elsewhere.The compatible family is Π_mimic(D), the deterministic policies agreeing with the optimal action on every state visited in D.
  • Bayes-risk lower bound: The Bayes-risk argument reduces lower bounding suboptimality to the first visit to a state outside the dataset’s observed states.The stopping time τ is defined as the first encounter with an unvisited state other than the absorbing bad state b.
  • Behavior cloning comparison: For C⋆∈(1,2), behavior cloning decomposes indicator loss into unobserved-state loss and errors where the optimal action is not most frequent.Under the stated conditional concentrability setting, the analysis bounds the resulting discounted suboptimality by S/[C0 N(1−γ)^2].

D.6 Analysis of LCB for a simple episodic MDP

The episodic VI-LCB analysis studies a three-level, two-action MDP under concentrability and deterministic-reward assumptions. It propagates high-probability action selection from the final level backward, using penalty comparisons and gap-dependent concentration to bound suboptimality.

  • Setup and assumptions: The example uses an episodic MDP with H=3, six states arranged across three levels, and two actions, with action 1 optimal everywhere.The analysis focuses on β2 when Cπ∈[1,2).
  • Setup and assumptions: The analysis assumes d⋆(s,a)≤C⋆µ(s,a), at least one sample for every state-action pair, and deterministic rewards.The implementation sets terminal-level Q-values using observed deterministic rewards.
  • Backward induction: At level 2, penalty bounds and concentration show that VI-LCB selects action 1 with high probability when the behavior distribution favors it by a factor of nine.The proof compares expected Q-value differences and uses N(s,2)≤N(s,1)/9.
  • Backward induction: At level 3, VI-LCB recovers V⋆ and selects action 1 in both terminal states because rewards are deterministic and every pair is observed.This supplies the base case for the backward induction.
  • Backward induction: Conditioned on correct level-2 choices, the level-1 analysis expresses suboptimality through the action gap and the probability of selecting the wrong action.Small gaps contribute little, while large gaps have negligible wrong-action probability via Hoeffding’s inequality.
  • Suboptimality bound: The proof combines these bounds into a final suboptimality bound after controlling the relevant stopping-time terms.The intermediate analysis includes τ2≲3N/160 and a resulting bound assembled from the level-wise estimates.
Loading 2103.12021v2…