Exploration in Structured Reinforcement Learning

Abstract

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 $c\log 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 $SA\log 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.

References in corpus (5)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Minimal Exploration in Structured Stochastic Bandits
• Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
• On Lower Bounds for Regret in Reinforcement Learning
• Model-based Reinforcement Learning and the Eluder Dimension

Cited by in corpus (16)

• Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Structure in Deep Reinforcement Learning: A Survey and Open Problems
• $Q$-learning with Logarithmic Regret
• From self-tuning regulators to reinforcement learning and back again
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Approximate Exploration through State Abstraction
• Adaptive Exploration in Linear Contextual Bandit
• Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis
• On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix
• Task-Optimal Exploration in Linear Dynamical Systems
• Transfer Learning in Bandits with Latent Continuity
• Learning to Actively Learn: A Robust Approach