Learning to Control in Metric Space with Optimal Regret

Abstract

We study online reinforcement learning for finite-horizon deterministic control systems with {\it arbitrary} state and action spaces. Suppose that the transition dynamics and reward function is unknown, but the state and action space is endowed with a metric that characterizes the proximity between different states and actions. We provide a surprisingly simple upper-confidence reinforcement learning algorithm that uses a function approximation oracle to estimate optimistic Q functions from experiences. We show that the regret of the algorithm after $K$ episodes is $O(HL(KH{)}^{\frac{d-1}{d}})$ where $L$ is a smoothness parameter, and $d$ is the doubling dimension of the state-action space with respect to the given metric. We also establish a near-matching regret lower bound. The proposed method can be adapted to work for more structured transition systems, including the finite-state case and the case where value functions are linear combinations of features, where the method also achieve the optimal regret.

References in corpus (5)

• Playing Atari with Deep Reinforcement Learning
• On Lower Bounds for Regret in Reinforcement Learning
• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
• Minimax Regret Bounds for Reinforcement Learning
• Methods for computing state similarity in Markov Decision Processes

Cited by in corpus (9)

• Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
• Adaptive Discretization in Online Reinforcement Learning
• Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces
• Adaptive Discretization for Model-Based Reinforcement Learning
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis
• Off-Policy Interval Estimation with Lipschitz Value Iteration
• Coarse-Grained Smoothness for RL in Metric Spaces
• Model-Free Algorithm and Regret Analysis for MDPs with Long-Term Constraints
• Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation