Abstract
We address reinforcement learning problems with finite state and actionspaces where the underlying MDP has some known structure that could bepotentially exploited to minimize the exploration rates of suboptimal (state,action) pairs. For any arbitrary structure, we derive problem-specific regretlower bounds satisfied by any learning algorithm. These lower bounds are madeexplicit for unstructured MDPs and for those whose transition probabilities andaverage reward functions are Lipschitz continuous w.r.t. the state and action.For Lipschitz MDPs, the bounds are shown not to scale with the sizes $S$ and$A$ of the state and action spaces, i.e., they are smaller than $c\log T$ where$T$ is the time horizon and the constant $c$ only depends on the Lipschitzstructure, the span of the bias function, and the minimal action sub-optimalitygap. This contrasts with unstructured MDPs where the regret lower boundtypically scales as $SA\log T$. We devise DEL (Directed Exploration Learning),an algorithm that matches our regret lower bounds. We further simplify thealgorithm for Lipschitz MDPs, and show that the simplified version is stillable to efficiently exploit the structure.