# Improved Exploration in Factored Average-Reward MDPs

arXiv: https://arxiv.org/abs/2009.04575 · HTML: https://mlsanity.com/paper/2009.04575/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2020.

## Built on by (most cited first, 3 of 3)

- [Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalization](https://mlsanity.com/paper/2202.06545/) (2022)
- [Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2310.07518/) (2023)
- [Optimal Activation of Halting Multi-Armed Bandit Models](https://mlsanity.com/paper/2304.10302/) (2023)

## Abstract (arXiv)

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 = otimesi=1n mathcal Xi and mathcal S=otimesi=1m mathcal Si, 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 Si'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.