Research map / Reinforcement learning / Policy gradient and actor-critic

Sequence Compression Speeds Up Credit Assignment in Reinforcement Learning

ICML 2024 · Reinforcement learning › Policy gradient and actor-critic · approach: Temporal-difference and discounting theory · 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 Chunked-TD, which uses learned-model transition probabilities to chunk trajectories and form adaptive lambda-returns for tabular on-policy value learning, speeding credit assignment in simple MDPs.

Problem

Temporal credit assignment in RL is slow under long delays and stochastic outcomes; TD(lambda) with a fixed lambda trades off bias and variance poorly, and model-based gradient or imagination approaches are fragile to model error.

Approach

Use predicted probabilities of next percepts from a learned model to set a time-varying lambda (lambda_{t+1} = P(x_{t+2}|x_{t+1})), so near-deterministic transitions are bridged with Monte Carlo-like targets while stochastic points bootstrap; inspired by history compression, and implementable online with eligibility traces.

Key results

• On Chain-and-Split, Chunked SARSA quickly converges to the true Delta Q = 0.01 while MC/SARSA(1) fails and SARSA(0) is slower and less stable (10 trials).
• On Accumulated-Charge, Chunked SARSA gives the fewest regretful choices across learning rates, while SARSA(lambda) shows high variance across seeds.
• On Key-to-Door with factored rewards, C-factored fails in only 669 +/- 17 of 5000 episodes versus about 1881 to 2688 for Expected-SARSA(lambda) and 2285 for C-default.

Measured effects reported in the paper

Surprising findings

• Default chunking with the whole-percept probability (C-default) performs poorly on Key-to-Door, because incompressible distractor noise prevents useful chunking; factoring rewards is needed.

Limitations

• Requires a generative model that gives next-state probabilities, which is costly to learn.
• Evaluated only with tabular value functions in small, fully observable MDPs.
• Hard credit assignment with noisy components needs a manual reward decomposition.

Experimental setup

Datasets: Chain-and-Split (custom MDP) Accumulated-Charge (custom MDP) Key-to-Door with factored rewards (custom MDP)

Benchmarks: Chain-and-Split Accumulated-Charge Key-to-Door

Metrics: action-value gap (Delta Q) number of regretful choices number of episodes without treasure collected

Baselines: SARSA(0) SARSA(1)/MC SARSA(lambda) Expected-SARSA(lambda) C-default

Builds on: TD(lambda) history compression Corrected-TD (Sutton and Singh 1994 variable TD) SARSA Expected-SARSA

Closest papers by meaning

• Reinforcement Learning with Action Chunking (NeurIPS 2025 · similarity 0.88)
• Discerning Temporal Difference Learning (AAAI 2024 · similarity 0.87)
• STAS: Spatial-Temporal Return Decomposition for Solving Sparse Rewards Problems in Multi-agent Reinforcement Learning (AAAI 2024 · similarity 0.87)
• Not Only Where, But When: Temporal Scheduling for RLVR (NeurIPS 2026 · similarity 0.86)
• Latent Reward: LLM-Empowered Credit Assignment in Episodic Reinforcement Learning (AAAI 2025 · similarity 0.86)
• The surprising efficiency of temporal difference learning for rare event prediction (NeurIPS 2024 · similarity 0.86)