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

Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling

NeurIPS 2026 · Bandits and online learning › RL theory and MDPs · approach: Average-reward and latent MDPs

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes π0-PSRL, a posterior sampling variant for episodic MDPs that uses posterior samples to decide when to explore while following a fixed reference policy during exploration episodes, aiming at instance-dependent regret optimality.

Problem

Regret minimization in finite-horizon episodic MDPs; minimax-optimal algorithms exist but tractable instance-dependent optimal approaches are lacking.

Approach

A PSRL variant that uses posterior samples only to decide when exploration is needed, and otherwise follows a fixed reference policy π0 during exploration episodes, targeting instance-dependent regret.

Experimental setup

Metrics: regret

Builds on: PSRL

Closest papers by meaning

• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning (NeurIPS 2021 · similarity 0.91)
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning (NeurIPS 2021 · similarity 0.91)
• Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (ICML 2017 · similarity 0.91)
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (ICML 2019 · similarity 0.91)
• Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees (NeurIPS 2022 · similarity 0.91)
• Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.90)