# Learning to Control in Metric Space with Optimal Regret

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2019.

## Built on by (most cited first, 9 of 9)

- [Adaptive Discretization in Online Reinforcement Learning](https://mlsanity.com/paper/2110.15843/) (2021)
- [Provable General Function Class Representation Learning in Multitask Bandits and MDPs](https://mlsanity.com/paper/2205.15701/) (2022)
- [Theoretically Principled Deep RL Acceleration via Nearest Neighbor Function Approximation](https://mlsanity.com/paper/2110.04422/) (2021)
- [Perturbational Complexity by Distribution Mismatch: A Systematic Analysis of Reinforcement Learning in Reproducing Kernel Hilbert Space](https://mlsanity.com/paper/2111.03469/) (2021)
- [Explaining Off-Policy Actor-Critic From A Bias-Variance Perspective](https://mlsanity.com/paper/2110.02421/) (2021)
- [Coarse-Grained Smoothness for RL in Metric Spaces](https://mlsanity.com/paper/2110.12276/) (2021)
- [HG2P: Hippocampus-inspired High-reward Graph and Model-Free Q-Gradient Penalty for Path Planning and Motion Control](https://mlsanity.com/paper/2410.09505/) (2024)
- [Towards Understanding the Benefit of Multitask Representation Learning in Decision Process](https://mlsanity.com/paper/2503.00345/) (2025)
- [Learning Optimal Distributionally Robust Stochastic Control in Continuous State Spaces](https://mlsanity.com/paper/2406.11281/) (2024)

## Abstract (arXiv)

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)^fracd-1d)  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.