Improved Exploration in Factored Average-Reward MDPs

2020/09/09 by Talebi, Mohammad Sadegh, Anders Jönsson, Odalric-Ambrym Maillard +2
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Advanced Control Systems Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2009.04575

openalex publication_date 2020/09/09 · openalex created_date 2020/09/14 · openalex updated_date 2026/07/28

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 = ⊗_i=1ⁿ \mathcal X_i and \mathcal S=⊗_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.

Citations

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Empirical Bernstein Bounds and Sample Variance Penalization
• Near-optimal Reinforcement Learning in Factored MDPs
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

Related

• Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure
• Near-optimal Reinforcement Learning in Factored MDPs
• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
• Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting