Research map / Bandits and online learning / RL theory and MDPs
Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Heavy-OFUL with adaptive Huber regression for heavy-tailed rewards | Linear bandits · Heavy-tailed linear bandits | regret: \tilde{O}\big(d T^{\frac{1-\epsilon}{2(1+\epsilon)}} \sqrt{\sum_{t=1}^T \nu_t^2} + d T^{\frac{1-\epsilon}{2(1+\epsilon)} | Helped |
| Use Heavy-LSVI-UCB with adaptive Huber reward estimation and weighted ridge transition estimation | Linear MDPs · Heavy-tailed linear MDPs | regret: \tilde{O}(d \sqrt{H\mathcal{U}^*} K^{\frac{1}{1+\epsilon}} + d \sqrt{H\mathcal{V}^*K}) | Helped |
| Use Heavy-LSVI-UCB rather than the prior first-order bound | Linear MDPs · Linear MDPs with uniformly bounded rewards | first-order regret: by a factor of \sqrt{H} | Helped |
| Apply Heavy-LSVI-UCB in the worst case | Linear MDPs · Heavy-tailed linear MDPs | regret: \tilde{O}(dHK^\frac{1}{1+\epsilon} + d \sqrt{H^3 K}); lower bound: \Omega(d H K^{\frac{1}{1+\epsilon}} + d \sqrt{H^3 K}) | Helped |
| Use the proposed central-moment-dependent regret analysis with finite variance (ε=1) | Heavy-LSVI-UCB · Linear MDPs with finite-variance rewards | regret: \tilde{O}(d\sqrt{H\cG^*K}) | Helped |
| Use the proposed first-order regret bound instead of the existing first-order result | Heavy-LSVI-UCB · Linear MDPs | first-order regret: \tilde{O}(d\sqrt{H^2 V_1^* K}) versus \tilde{O}(d\sqrt{H^3 V_1^* K}) | Helped |
| Use truncation-based methods that depend on raw moments rather than central moments | Heavy-tailed bandit and RL algorithms · Deterministic instances | regret | Hurt |
| Use adaptive Huber regression with the proposed robust self-normalized concentration bound | Online regression with heavy-tailed noise · Heavy-tailed online regression | estimation error: \beta_t = 3 \sqrt{\lambda}B + 24 t^{\frac{1-\epsilon}{2(1+\epsilon)}} \sqrt{2\kappa} b (\log 3T)^{\frac{1-\epsilon}{2(1+ | Helped |
| Replace the ideal reward residual with an estimated residual when estimating reward central moments | Heavy-LSVI-UCB · Linear MDPs | estimation error: \|\hat{\bpsi}_{k,h}-\bpsi_{k,h}\|_{\bH_{k,h}} \le 6 \kappa \max_{s\le t}\hat{\beta}_s | Hurt |
Closest papers by meaning
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.92)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.90)
- Catastrophic Goodhart: regularizing RLHF with KL divergence does not mitigate heavy-tailed reward misspecification (NeurIPS 2024 · similarity 0.89)
- Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning (ICLR 2024 · similarity 0.89)
- Nearly Minimax Optimal Submodular Maximization with Bandit Feedback (NeurIPS 2024 · similarity 0.89)
- Exact Policy Recovery in Offline RL with Both Heavy-Tailed Rewards and Data Corruption (AAAI 2024 · similarity 0.89)
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.