Research map / Reinforcement learning / Policy gradient and actor-critic
Categorical Distributional Reinforcement Learning with Kullback-Leibler Divergence: Convergence and Asymptotics
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.
Studies categorical temporal-difference learning with a KL loss (KL-CTD), proposes a preconditioned variant (PKL-CTD) with a convergence proof, and derives its asymptotic variance versus TD and Monte Carlo in tabular settings.
Problem
Large-scale categorical distributional RL uses KL losses, but theory has only covered Cramér-distance variants; KL-CTD's convergence and asymptotic behaviour were unknown.
Approach
Preconditions the KL categorical TD update with C^T C, where C is the lower-triangular cumulative-sum matrix, so the expected update is a contraction in a weighted norm and the KL-based Lyapunov function decreases, giving provable almost-sure convergence; also derives asymptotic variance results for CMC, PCMC, TD and PKL-CTD.
Key results
- PKL-CTD is proven to converge almost surely to the categorical fixed point under Robbins-Munro step sizes, via a weighted contraction of the distributional Bellman operator.
- Empirical histograms over 10,000 seeds match the theoretical asymptotic density of categorical Monte Carlo after roughly 10^4 iterations.
- In tabular experiments, KL-CTD is preferable under high reward noise and PKL-CTD performs well in all non-deterministic environments; TD with a large learning rate is best in deterministic settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KL-CTD instead of TD | Tabular value estimation · Appendix G MDP | value MSE | Helped |
| Use Cramér-CTD instead of TD | Tabular value estimation · Appendix G MDP | value MSE | No clear effect |
| Use TD with a large learning rate | Tabular value estimation · Cycle with deterministic rewards | value MSE | Helped |
| Use KL-CTD instead of TD | Tabular value estimation · Environments with high reward noise | value MSE | Helped |
| Use PKL-CTD instead of TD | Tabular value estimation · Non-deterministic environments | value MSE | Helped |
| Use a support endpoint larger than the maximum return (ablation) | Categorical Monte Carlo · Returns supported on [0, 2] | value MSE | Hurt |
| Use a support endpoint smaller than the maximum return (ablation) | Categorical Monte Carlo · Returns supported on [0, 2] | value MSE | Hurt |
| Increase the number of support locations (ablation) | Categorical Monte Carlo · Fixed support size | value MSE | Helped |
| Scale the learning rate by √m when varying the number of atoms (ablation) | CTD · Fixed MDP, varying number of support locations | value MSE | Helped |
Surprising findings
- KL-CTD's expected value error need not decrease at each step, so the summed KL to the fixed point is not a Lyapunov function for unpreconditioned KL-CTD.
- Cramér-CTD and TD produce identical learning curves in the tabular experiment, while KL-CTD behaves very differently.
Limitations
- Analysis is tabular with finite state spaces; no function approximation.
- Convergence is proven for the preconditioned variant only; unpreconditioned KL-CTD convergence is not established.
Experimental setup
Benchmarks: tabular MDPs (Cycle, Garnet, Dirichlet) with deterministic, Gaussian, and t2 rewards
Metrics: value MSE asymptotic variance agreement
Baselines: TD Cramér-CTD KL-CTD CMC MC
Builds on: categorical distributional RL (C51) Cramér-CTD (Rowland et al., 2018) Robbins-Siegmund theorem Wu et al. 2024 TD asymptotic variance
Closest papers by meaning
- Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model (NeurIPS 2024 · similarity 0.91)
- Intrinsic Benefits of Categorical Distributional Loss: Uncertainty-aware Regularized Exploration in Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
- Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learning (NeurIPS 2026 · similarity 0.89)
- Foundations of Multivariate Distributional Reinforcement Learning (NeurIPS 2024 · similarity 0.89)
- Distributional Reinforcement Learning with Regularized Wasserstein Loss (NeurIPS 2024 · similarity 0.88)
- CTD4 – a Deep Continuous Distributional Actor-Critic Agent with a Kalman Fusion of Multiple Critics (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.