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

Achieving Tractable Minimax Optimal Regret in Average Reward MDPs

NeurIPS 2024 · Bandits and online learning › RL theory and MDPs · approach: Average-reward and latent MDPs · 2 citations (OpenAlex)

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.

Proposes PMEVI-DT, a tractable average-reward RL algorithm whose regret matches the minimax lower bound sqrt(sp(h*) S A T) up to logs, without prior knowledge of the bias span, by projecting and mitigating extended value iteration with bias confidence regions.

Problem

Learning average-reward MDPs with minimax-optimal regret in terms of bias span, while remaining computationally tractable and not requiring prior knowledge of the span of the optimal bias.

Approach

A new subroutine PMEVI replaces extended value iteration by projecting onto a bias confidence region (estimated from commute-time bias difference estimators and span constraints) and mitigating the optimistic backup with empirical Bernstein variance bounds, yielding polynomial-time bias-constrained optimistic planning; it can be plugged into UCRL2-style algorithms.

Key results

• Proves regret O(sqrt(c S A T log(SAT/delta))) + lower-order term for PMEVI-DT, matching the minimax lower bound sqrt(sp(h*) S A T) up to logarithmic factors, with time complexity O(D S^3 A T) when using UCRL2 confidence regions.
• PMEVI-DT with no prior (H_* = R^S) requires no knowledge of sp(h*); span constraint uses c_0 = T^{1/5}.
• On RiverSwim, prior bias knowledge substantially reduces burn-in regret of PMEVI-DT relative to UCRL2 on a 3-state instance.

Measured effects reported in the paper

Surprising findings

• The choice of the underlying confidence region has little importance once bias information is used to refine the Bellman operator.
• Replacing EVI with PMEVI gives almost identical behavior to EVI when no bias prior is given, since the bias region is too large early on.

Limitations

• Regret bound holds under regularity assumptions on the confidence region (sub-Weissman rewards, convex rectangular regions, EVI convergence).
• Second-order lower-order term T^{9/20} and the span-constraint parameter c_0 = T^{1/5} add overhead; the bound is only minimax up to logs and lower-order terms.
• Experiments are limited to small RiverSwim instances.

Experimental setup

Benchmarks: RiverSwim

Metrics: cumulative regret

Baselines: UCRL2 UCRL2B UCRL3 KL-UCRL REGAL SCAL EBF PSRL Politex MDP-OOMD

Builds on: UCRL2 EVI EBF REGAL SCAL

Closest papers by meaning

• Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.92)
• Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.91)
• Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach (NeurIPS 2025 · similarity 0.90)
• Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.90)
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.90)
• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.90)