Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
Poster D: Tuesday -- 16:00 - 18:00
Victor Boone, Dorian Baudry, Odalric-Ambrym Maillard, Cyrille Kone, Waris Radji
Keywords: Reinforcement learning, regret minimization, instance dependent, posterior sampling, finite horizon MDPs, model based methods
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 $\pi_0$`-PSRL`, a variant of `PSRL` that uses posterior samples to decide when exploration is needed, while following a fixed reference policy $\pi_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 $\pi_0$`-PSRL, identifying the logarithmic exploration cost induced by $\pi_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.