Research map / Bandits and online learning / RL theory and MDPs
More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning
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 that maximum-likelihood distributional RL (DistRL) yields second-order, variance-dependent regret and PAC bounds in online and offline RL with function approximation, and a distributional optimistic contextual bandit algorithm (DistUCB) that beats squared-loss RegCB empirically.
Problem
Existing DistRL theory gives only small-loss (first-order) bounds scaling with V*, which are slow when V* is far from zero even in near-deterministic tasks; the question is whether DistRL can give tighter variance-dependent (second-order) bounds in general function-approximation RL.
Approach
Use MLE-based distributional confidence sets and triangular discrimination to bound mean differences by variance times triangular discrimination, giving second-order bounds for O-DISCO/P-DISCO without variance-weighted regression; a DistUCB contextual bandit variant with disagreement-based width is implemented with neural nets.
Key results
- On King County Housing, DistUCB achieves average cost .683 vs RegCB .708 over all episodes (3 seeds).
- On Prudential Life Insurance, DistUCB achieves .248 vs RegCB .287 over all episodes; on CIFAR-100, .862 vs .890.
- Theory: second-order regret bound of order sqrt(sum of return variances) plus lower-order term, implying fast 1/N rates in near-deterministic MDPs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| learn the cost distribution with maximum likelihood instead of squared loss | DistUCB vs RegCB · King County Housing, all episodes | average cost: .708 -> .683 | Helped |
| learn the cost distribution with maximum likelihood instead of squared loss | DistUCB vs RegCB · King County Housing, last 100 episodes | average cost: .676 -> .640 | Helped |
| learn the cost distribution with maximum likelihood instead of squared loss | DistUCB vs RegCB · Prudential Life Insurance, all episodes | average cost: .287 -> .248 | Helped |
| learn the cost distribution with maximum likelihood instead of squared loss | DistUCB vs RegCB · Prudential Life Insurance, last 100 episodes | average cost: .278 -> .236 | Helped |
| learn the cost distribution with maximum likelihood instead of squared loss | DistUCB vs RegCB · CIFAR-100, all episodes | average cost: .890 -> .862 | Helped |
| learn the cost distribution with maximum likelihood instead of squared loss | DistUCB vs RegCB · CIFAR-100, last 100 episodes | average cost: .854 -> .823 | Helped |
Surprising findings
- DistRL helps even in near-deterministic systems, since the agent adapts to low variance without knowing it a priori.
- Second-order bounds can be obtained by plain MLE distributional learning without variance-weighted regression.
Limitations
- Distributional Bellman completeness is a stronger assumption than squared-loss completeness.
- Higher statistical complexity of the class of conditional distributions compared to value-function classes.
- Confidence-set optimization is computationally hard in general; experiments only cover contextual bandits.
Experimental setup
Datasets: King County Housing Prudential Life Insurance CIFAR-100
Benchmarks: King County Housing Prudential Life Insurance CIFAR-100
Metrics: average cost over all episodes average cost over last 100 episodes regret
Baselines: RegCB O-DISCO (small-loss) P-DISCO (small-loss)
Builds on: O-DISCO P-DISCO RegCB BCP GOLF
Closest papers by meaning
- Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds (ICLR 2025 · similarity 0.89)
- Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation (ICML 2024 · similarity 0.89)
- Selective Uncertainty Propagation in Offline RL (AAAI 2025 · similarity 0.88)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.88)
- Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs (NeurIPS 2024 · similarity 0.88)
- Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation (ICML 2025 · similarity 0.88)
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.