Research map / Reinforcement learning / MDPs and planning

Offline-Online Reinforcement Learning for Linear Mixture MDPs

NeurIPS 2026 · Reinforcement learning › MDPs and planning · approach: Offline RL sample complexity · 0 citations (OpenAlex)

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.

Proposes O-O UCRL-VTR, an offline-online algorithm for linear mixture MDPs under known bounded environment shift that intersects online-only and offline-online confidence sets, giving min-of-two regret bounds with a near-matching lower bound.

Problem

Safely leveraging biased offline data from a shifted environment, collected by a possibly adaptive behavior policy, to speed up online regret minimization in linear mixture MDPs.

Approach

Maintain two estimators of the online transition parameter (online-only and offline-online) and plan optimistically over the intersection of their confidence sets, so offline data is used only when informative; coverage tau is controlled by designing auxiliary value functions for offline regression rather than pessimism.

Key results

• Regret upper bound of min{[BH^2 d sqrt(K) + H^4 d^{3/2} Delta sqrt(K) sqrt(M^off/tau)] x sqrt(log(...)), BH^2 d sqrt(K)} matching online linear mixture MDP rate when offline data is uninformative.
• Offline data is informative (regret O~(BH^2 d K^{1/2-eps})) when tau = Omega(H^3 K^{1+2eps}/M^off) and Delta/tau = O(B/(H^{7/2} d^{1/2} K^{1/2+eps})); with M^off = Theta(K^2) and Delta <= K^{-1}, regret is O(log K).
• Lower bound Omega(min{dH sqrt(K), dH sqrt(K)(...)}) matches upper bound in d, K, M^off, Delta up to a d^{3/2} vs sqrt(d) gap in the Delta term and H gap.
• Simulations on a tabular MDP show O-O UCRL-VTR beats UCRL when Delta is small and degrades gracefully to UCRL as Delta grows, while COMPLETE degrades substantially.

Surprising findings

• Harder online instances (smaller suboptimality gaps) can make offline data more beneficial under adaptive UCB1 behavior policies, since more offline exploration raises coverage.
• Pessimism-based construction of offline value function estimates performs worse than the proposed coverage-maximizing design in simulations.

Limitations

• Assumes the environment shift bound Delta is known and the reward function is known and deterministic.
• Lower bound is only proven for tau = Theta(1); the tau = o(1) regime lacks a matching lower bound.
• Sufficiently large K and M^off assumed for asymptotic notations; additional H and d gaps remain between upper and lower bounds.

Experimental setup

Datasets: synthetic tabular MDP (|S|=5, |A|=10, H=3)

Benchmarks: synthetic tabular MDP

Metrics: cumulative regret

Baselines: UCRL COMPLETE DP-LSVI UCBVI O-O UCRL-VTR (Pessimistic)

Builds on: UCRL-VTR COMPLETE UCB1 UCBVI

Closest papers by meaning

• Information-Directed Offline-to-Online Reinforcement Learning (NeurIPS 2026 · similarity 0.91)
• Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction (ICML 2025 · similarity 0.91)
• Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.91)
• A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs (ICML 2024 · similarity 0.91)
• RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation (NeurIPS 2024 · similarity 0.90)
• Bayesian Design Principles for Offline-to-Online Reinforcement Learning (ICML 2024 · similarity 0.90)