Research map / Bandits and online learning / RL theory and MDPs
Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs
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 the MVP algorithm achieves a variance-aware gap-dependent regret bound using a new maximum conditional total variance quantity, plus a matching lower bound on the gap-dependent term for tabular episodic MDPs.
Problem
Gap-dependent regret for episodic tabular MDPs that is both variance-aware (tighter than maximum per-step variance H·Q*) and has improved H dependence.
Approach
Introduces the maximum conditional total variance (over policies, states and steps) as the variance quantity in gap-dependent bounds, and analyzes MVP via a reweighted sum of suboptimality gaps times visitation counts, avoiding clipping-and-recursion; a lower bound shows the conditional variance is necessary.
Key results
- MVP attains a gap-dependent regret bound scaling with min(H^2, maximum conditional total variance) in the gap terms, improving H dependence to H^2 versus H^3-H^6 in prior work.
- A lower bound Omega(sum (H^2 ∧ Var^c_max)/Δ · log K) shows the first term is tight up to log factors and that the conditional variance cannot be replaced by the unconditional maximum total variance.
- Upper bound's Z_opt term (H^2 ∧ Var^c_max)|Z_opt|/Δ_min does not match the lower bound's S/Δ_min term, leaving a gap.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MVP's conditional-total-variance-aware gap-dependent analysis | MVP · Time-inhomogeneous episodic tabular MDPs | gap-dependent regret upper bound: H^2 \land \cVarmax | Helped |
| Use the proposed bound instead of previous gap-dependent bounds | MVP · Time-inhomogeneous episodic tabular MDPs | worst-case horizon dependence in gap-dependent terms: H^2 | Helped |
| Condition total variance on the state and time step rather than use maximum unconditional total variance | Gap-dependent regret bounds for episodic tabular MDPs · Low-visitation states with large variance | gap-dependent regret lower bound: \Omega\left( \sum_{i : \Delta_i > 0} \frac{L}{\Delta_i}\cdot \log K\right) | Helped |
| Use maximum unconditional total variance in place of conditional total variance | Gap-dependent regret bounds for episodic tabular MDPs · Low-visitation states with large variance | gap-dependent regret guarantee | Hurt |
Surprising findings
- Low-visitation-probability states can contribute substantially to gap-dependent regret, even though they are negligible in minimax analyses.
- The maximum unconditional total variance can be O(1) while gap-dependent regret still has order H^2 lower-bound terms.
Limitations
- Upper bound's |Z_opt|/Δ_min term does not match the lower bound's S/Δ_min term.
- Analysis restricted to tabular MDPs; not extended to linear or general function approximation.
- Conditional variance Var^c_max can be as large as Θ(H^3) in the worst case, though bounded by H·Q*.
Experimental setup
Metrics: cumulative regret (theoretical bound)
Baselines: StrongEuler UCB-H (Q-learning) AMB UCB-Advantage Q-EarlySettled-Advantage
Builds on: MVP (Monotonic Value Propagation) Bernstein-style variance-aware regret analysis
Closest papers by meaning
- Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition (ICLR 2025 · similarity 0.92)
- Gap-Dependent Bounds for Federated $Q$-Learning (ICML 2025 · similarity 0.90)
- Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization (ICLR 2025 · similarity 0.89)
- Online Learning in Risk Sensitive constrained MDP (ICML 2025 · similarity 0.88)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · similarity 0.88)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · 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.