Research map / Bandits and online learning / RL theory and MDPs

Position: Constants are Critical in Regret Bounds for Reinforcement Learning

ICML 2025 · Bandits and online learning › RL theory and MDPs · approach: Regret bounds with function approximation

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.

Position paper arguing that multiplicative constants and lower-order terms matter for RL regret bounds; refines UCBVI's Chernoff-Hoeffding and Bernstein-Freedman bonuses and analysis, and shows empirically that tighter constants cut regret versus original UCBVI and MVP on tabular toy MDPs and RiverSwim.

Problem

Theoretical RL work treats regret bounds as "closed" when they match lower bounds up to constants, ignoring constants that strongly affect actual empirical exploration and performance in finite-horizon tabular MDPs.

Approach

Re-derive UCBVI's exploration bonuses and regret analysis with tighter constants and lower-order terms (Chernoff-Hoeffding and Bernstein-Freedman versions), and show that these constant improvements yield large empirical regret reductions, arguing that constants should be considered in algorithm design and analysis.

Key results

• Refined Bernstein-Freedman UCBVI (UCBVI-BF-I) reduces empirical regret by a factor of 1.87 on average relative to original UCBVI-BF.
• Refined analysis reduces dominant-term regret bound constants by factor 2 (Chernoff-Hoeffding) and 5/4 (Bernstein-Freedman), and lower-order terms by roughly 90x and 4x.
• MVP shows no sublinear regret trend in RiverSwim over the considered horizon, while both UCBVI variants do, with UCBVI-BF-I roughly half the regret of UCBVI-BF.

Measured effects reported in the paper

Surprising findings

• MVP, the state-of-the-art order-optimal algorithm, performs poorly empirically and fails to show sublinear regret in RiverSwim.
• The doubling trick used by MVP, though only costing a constant in theory, appears to waste samples and hurt practical performance.

Limitations

• Empirical evaluation limited to small tabular toy environments (S=3 or 5) and a single RiverSwim instance.
• Improvements are in constants and lower-order terms, not regret order; benefits for deep RL are conjectured rather than shown.

Experimental setup

Benchmarks: random tabular MDPs S=3 A=3 H in {5,10} K up to 10^6 RiverSwim S=5 H=10

Metrics: cumulative regret

Baselines: UCBVI-CH UCBVI-BF MVP

Builds on: UCBVI MVP Bernstein-Freedman inequality

Closest papers by meaning

• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (ICML 2019 · similarity 0.91)
• Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.90)
• Regret Bounds for Learning State Representations in Reinforcement Learning (NeurIPS 2019 · similarity 0.90)
• Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.88)
• Automatic Reward Shaping from Confounded Offline Data (ICML 2025 · similarity 0.88)
• Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs (NeurIPS 2024 · similarity 0.88)