Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
Abstract
We study regret minimization in finite-horizon episodic Markov Decision Processes (MDPs). While minimax-optimal algorithms are known, tractable approaches to instance-dependent optimality are still lacking. Motivated by this gap, we introduce π0-PSRL, a variant of PSRL that uses posterior samples to decide when exploration is needed, while following a fixed reference policy π0 during exploration episodes. This decouples the test for exploration, triggered when the sampled and empirical MDPs have different optimal policies, from the choice of the policy used to gather information. The resulting design addresses a limitation of standard PSRL, where the sampled optimal policy may not be the optimal choice for exploration. We prove instance-dependent regret bounds for π0-PSRL, identifying the logarithmic exploration cost induced by π0 and taking a step toward matching asymptotic lower bounds for episodic RL. Our proof techniques showcase a novel proof structure to derive problem-dependent regret bounds in episodic MDPs, and concentration results for Dirichlet random variables, that may be of independent interest.
Related
- Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
- Minimax-Optimality of Posterior Sampling for Reinforcement Learning
- Instance-dependent sequential limits as an exact information ledger
- Accelerating posterior sampling in Bayesian inverse problems with diffusion models: an online-offline perspective
- Instance-dependent Stochastic Lipschitz bandit
BibTeX
@misc{boone2026towards,
title = {{Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling}},
author = {Victor Boone and Cyrille Kone and Waris Radji and Odalric-Ambrym Maillard and Dorian Baudry},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26029},
eprint = {2610.26029},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26029},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
AU - Victor Boone
AU - Cyrille Kone
AU - Waris Radji
AU - Odalric-Ambrym Maillard
AU - Dorian Baudry
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26029
UR - https://arxiv.org/abs/2610.26029
AB - We study regret minimization in finite-horizon episodic Markov Decision Processes (MDPs). While minimax-optimal algorithms are known, tractable approaches to instance-dependent optimality are still lacking. Motivated by this gap, we introduce π_0-PSRL, a variant of PSRL that uses posterior samples to decide when exploration is needed, while following a fixed reference policy π_0 during exploration episodes. This decouples the test for exploration, triggered when the sampled and empirical MDPs have different optimal policies, from the choice of the policy used to gather information. The resulting design addresses a limitation of standard PSRL, where the sampled optimal policy may not be the optimal choice for exploration. We prove instance-dependent regret bounds for π_0-PSRL, identifying the logarithmic exploration cost induced by π_0 and taking a step toward matching asymptotic lower bounds for episodic RL. Our proof techniques showcase a novel proof structure to derive problem-dependent regret bounds in episodic MDPs, and concentration results for Dirichlet random variables, that may be of independent interest.
ER -