# Exploration in Structured Reinforcement Learning

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2018.

## Built on by (most cited first, 30 of 34)

- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps](https://mlsanity.com/paper/2203.13935/) (2022)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Metrics and continuity in reinforcement learning](https://mlsanity.com/paper/2102.01514/) (2021)
- [Improved Corruption Robust Algorithms for Episodic Reinforcement Learning](https://mlsanity.com/paper/2102.06875/) (2021)
- [Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs](https://mlsanity.com/paper/2203.09251/) (2022)
- [Task-Optimal Exploration in Linear Dynamical Systems](https://mlsanity.com/paper/2102.05214/) (2021)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [Structured Neural Networks for Density Estimation and Causal Inference](https://mlsanity.com/paper/2311.02221/) (2023)
- [Gap-Dependent Unsupervised Exploration for Reinforcement Learning](https://mlsanity.com/paper/2108.05439/) (2021)
- [Logarithmic regret bounds for continuous-time average-reward Markov decision processes](https://mlsanity.com/paper/2205.11168/) (2022)
- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)
- [Asymptotic Instance-Optimal Algorithms for Interactive Decision Making](https://mlsanity.com/paper/2206.02326/) (2022)
- [Blending Data-Driven Priors in Dynamic Games](https://mlsanity.com/paper/2402.14174/) (2024)
- [Gap-Dependent Bounds for Two-Player Markov Games](https://mlsanity.com/paper/2107.00685/) (2021)
- [Categorical semantics of compositional reinforcement learning](https://mlsanity.com/paper/2208.13687/) (2022)
- [Model-Free Active Exploration in Reinforcement Learning](https://mlsanity.com/paper/2407.00801/) (2024)
- [Long-term Safe Reinforcement Learning with Binary Feedback](https://mlsanity.com/paper/2401.03786/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/2506.06521/) (2025)
- [Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning](https://mlsanity.com/paper/2406.06856/) (2024)
- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)
- [Reduce, Reuse, Recycle: Categories for Compositional Reinforcement Learning](https://mlsanity.com/paper/2408.13376/) (2024)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Transfer Learning in Bandits with Latent Continuity](https://mlsanity.com/paper/2102.02472/) (2021)
- [Regret Analysis in Deterministic Reinforcement Learning](https://mlsanity.com/paper/2106.14338/) (2021)
- [Q-Learning with Fine-Grained Gap-Dependent Regret](https://mlsanity.com/paper/2510.06647/) (2025)

## Abstract (arXiv)

We address reinforcement learning problems with finite state and action spaces where the underlying MDP has some known structure that could be potentially exploited to minimize the exploration rates of suboptimal (state, action) pairs. For any arbitrary structure, we derive problem-specific regret lower bounds satisfied by any learning algorithm. These lower bounds are made explicit for unstructured MDPs and for those whose transition probabilities and average 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 clog T where T is the time horizon and the constant c only depends on the Lipschitz structure, the span of the bias function, and the minimal action sub-optimality gap. This contrasts with unstructured MDPs where the regret lower bound typically scales as SAlog T. We devise DEL (Directed Exploration Learning), an algorithm that matches our regret lower bounds. We further simplify the algorithm for Lipschitz MDPs, and show that the simplified version is still able to efficiently exploit the structure.