Learning to Control in Metric Space with Optimal Regret

2019/05/05 by Lin F. Yang, Yang, Lin F., Chengzhuo Ni +3 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Receptor Mechanisms and Signaling #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1905.01576

openalex publication_date 2019/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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)^(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.

Citations

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

Cited by

• Off-Policy Interval Estimation with Lipschitz Value Iteration
• Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis

Related

• Kernel-Based Reinforcement Learning: A Finite-Time Analysis
• Value Function Approximations via Kernel Embeddings for No-Regret Reinforcement Learning
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Provably adaptive reinforcement learning in metric spaces