Improved Exploration in Factored Average-Reward MDPs

Abstract

We consider a regret minimization task under the average-reward criterion in an unknown Factored Markov Decision Process (FMDP). More specifically, we consider an FMDP where the state-action space $\mathcal{X}$ and the state-space $\mathcal{S}$ admit the respective factored forms of $\mathcal{X}={\otimes }_{i=1}^n{\mathcal{X}}_i$ and $\mathcal{S}={\otimes }_{i=1}^m{\mathcal{S}}_i$, and the transition and reward functions are factored over $\mathcal{X}$ and $\mathcal{S}$. Assuming known factorization structure, we introduce a novel regret minimization strategy inspired by the popular UCRL2 strategy, called DBN-UCRL, which relies on Bernstein-type confidence sets defined for individual elements of the transition function. We show that for a generic factorization structure, DBN-UCRL achieves a regret bound, whose leading term strictly improves over existing regret bounds in terms of the dependencies on the size of ${\mathcal{S}}_i$'s and the involved diameter-related terms. We further show that when the factorization structure corresponds to the Cartesian product of some base MDPs, the regret of DBN-UCRL is upper bounded by the sum of regret of the base MDPs. We demonstrate, through numerical experiments on standard environments, that DBN-UCRL enjoys substantially improved regret empirically over existing algorithms that have frequentist regret guarantees.

arXiv comment23 pages. To appear in Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS) 2021

References in corpus (11)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• (More) Efficient Reinforcement Learning via Posterior Sampling
• Empirical Bernstein Bounds and Sample Variance Penalization
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
• Near-optimal Reinforcement Learning in Factored MDPs
• Model-based Reinforcement Learning and the Eluder Dimension
• Factored Value Iteration Converges
• Improved Analysis of UCRL2 with Empirical Bernstein Inequality
• Tightening Exploration in Upper Confidence Reinforcement Learning