aiqbench analysis
This paper introduces $\pi_0$-PSRL, a novel algorithm for episodic Markov Decision Processes that decouples exploration triggers from policy selection to achieve instance-dependent regret optimality. By proving logarithmic exploration costs and leveraging new concentration results for Dirichlet random variables, the work advances theoretical bounds in reinforcement learning beyond existing minimax-optimal approaches. The contribution lies specifically in refining the mathematical framework for efficient exploration within finite-horizon MDPs.
Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
arXiv:2610.26029v1 Announce Type: cross 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 $\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.
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 $\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.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2610.26029 [stat.ML]
(or arXiv:2610.26029v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2610.26029 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 255 words