Research map / Reinforcement learning / Offline RL

Offline RL with Observation Histories: Analyzing and Improving Sample Complexity

ICLR 2024 · Reinforcement learning › Offline RL · approach: Simple practical offline RL · 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.

Shows theoretically that pessimistic offline RL over observation histories has poor worst-case sample complexity, and that learning history representations inducing a bisimulation metric restores efficiency; proposes an auxiliary bisimulation loss added to offline RL and tests it on gridworld, ViZDoom, and Wordle.

Problem

Offline RL in POMDPs conditioned on observation histories cannot benefit from trajectory stitching because histories rarely repeat, which may yield poor sample complexity.

Approach

Learn a compact history encoder whose distances approximate the pi*-bisimulation metric, and add a bisimulation loss to standard offline RL objectives; theory shows the summarized MDP over clusters gives improved sample complexity bounds.

Key results

• On ViZDoom, CQL + bisimulation reached 0.71 vs 0.64 for CQL on the base task and 0.58 vs 0.43 on the hard task.
• On Wordle, ILQL + bisimulation scored -2.19 vs -2.21 for ILQL, a marginal gain over the base method.
• Theory: PEVI on observation-history MDPs has suboptimality scaling with |H| (exponential in horizon), while the bisimulation-based summarized MDP gives bounds scaling with |Z|.

Measured effects reported in the paper

Surprising findings

• Standard ILQL implicitly reduces the bisimulation loss during training even without an explicit term, so explicit minimization gives only marginal gains on Wordle.
• Naive CQL in the gridworld sometimes fails to take the informative rightward path, attributed to RNN forgetting of early states.

Limitations

• Theoretical results are for tabular POMDPs, and the practical method is evaluated only on small-scale tasks.
• Bisimulation loss gives marginal improvement where base offline RL already performs well (Wordle).
• The bisimulation loss relies on learned reward and dynamics models and a learned policy as proxies for pi* and the true model.

Experimental setup

Datasets: Wordle human game dataset (from tweets) ViZDoom My Way Home offline dataset (random and A2C trajectories) Tabular gridworld offline dataset (synthetic)

Benchmarks: Tabular gridworld navigation ViZDoom My Way Home (base and hard tasks) Wordle

Metrics: mean reward Wordle score bisimulation loss value

Baselines: Filtered BC BC CQL Fine-tuning Filtered fine-tuning ILQL

Builds on: PEVI conservative Q-learning bisimulation metrics implicit language Q-learning DeepMDP-style bisimulation representation learning

Closest papers by meaning

• Hybrid Reinforcement Learning from Offline Observation Alone (ICML 2024 · similarity 0.91)
• Stitching Sub-trajectories with Conditional Diffusion Model for Goal-Conditioned Offline RL (AAAI 2024 · similarity 0.90)
• Beyond OOD State Actions: Supported Cross-Domain Offline Reinforcement Learning (AAAI 2024 · similarity 0.90)
• Learning from Reward-Free Offline Data: A Case for Planning with Latent Dynamics Models (NeurIPS 2025 · similarity 0.90)
• Forecasting in Offline Reinforcement Learning for Non-stationary Environments (NeurIPS 2025 · similarity 0.90)
• Tackling Data Corruption in Offline Reinforcement Learning via Sequence Modeling (ICLR 2025 · similarity 0.90)