Research map / Reinforcement learning / MDPs and planning

On The Statistical Complexity of Offline Decision-Making

ICML 2024 · Reinforcement learning › MDPs and planning · approach: Offline RL sample complexity

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterizes offline decision-making (contextual bandits and MDPs) with function approximation via pseudo-dimension and a new policy transfer coefficient, giving near-minimax lower and upper bounds and hybrid offline-online rates.

Problem

Offline decision-making with function approximation under distribution shift: what determines sample-efficient learnability, given that prior data-coverage notions (concentrability, relative condition number, data diversity, HK transfer exponent) are incompatible and lack lower bounds.

Approach

Introduces policy transfer coefficients, which bound the expected value gap under the target policy by a power of the squared L2 distance under the behavior policy, strictly generalizing prior coverage notions; combined with pseudo-dimension, it yields matching lower bounds and an actor-critic Hedge-based upper bound, plus hybrid offline-online analysis.

Key results

• Lower bound of order (Cd/n)^{1/(2rho)} for offline contextual bandits over the class with policy transfer coefficients (rho,C), matched up to log factors by OfDM-Hedge for parametric classes when rho>=1.
• Hybrid lower bound min{(Cd/n)^{1/(2rho)}, sqrt(d/m)}, showing offline or online alone is nearly optimal depending on transfer coefficient; the adaptive hybrid algorithm achieves a matching rate in some regimes.
• For MDPs, lower bound (H^2 Cd/n)^{1/(2rho)} and upper bound with a gap of O(H).

Surprising findings

• Mixing offline and online data gives no worst-case benefit beyond running the better of the two pure approaches when the transfer coefficient is known.
• The proposed transfer coefficient is finite in cases where concentrability is infinite (e.g., halfspace/sphere example), so it is strictly more general than prior coverage notions.

Limitations

• Lower bounds only for parametric classes with finite pseudo-dimension; upper bounds for nonparametric classes lack matching lower bounds.
• Upper bound in MDPs has an O(H) gap to the lower bound; fast transfer regime (rho<1) lower bound not established.
• Hybrid adaptive algorithm matches the lower bound only when online budget m is large enough.

Experimental setup

Metrics: suboptimality (theoretical bound)

Baselines: concentrability coefficient Hanneke-Kpotufe transfer exponent data diversity FALCON+

Builds on: Hanneke-Kpotufe transfer exponent FALCON+ EXP4 pessimistic actor-critic offline RL

Closest papers by meaning

• Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.89)
• Leveraging (Biased) Information: Multi-armed Bandits with Offline Data (ICML 2024 · similarity 0.89)
• Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.88)
• Online Markov Decision Processes Configuration with Continuous Decision Space (AAAI 2024 · similarity 0.88)
• Offline-Online Reinforcement Learning for Linear Mixture MDPs (NeurIPS 2026 · similarity 0.88)
• Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.87)