### Abstract

We study online reinforcement learning for finite-horizon deterministic control systems with arbitrary state and action spaces. Suppose 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(DLK)^{\frac{d}{d+1}}H where D is the diameter of the state-action space, 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.

Original language | English (US) |
---|---|

Title of host publication | 2019 57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 726-733 |

Number of pages | 8 |

ISBN (Electronic) | 9781728131511 |

DOIs | |

State | Published - Sep 2019 |

Externally published | Yes |

Event | 57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019 - Monticello, United States Duration: Sep 24 2019 → Sep 27 2019 |

### Publication series

Name | 2019 57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019 |
---|

### Conference

Conference | 57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019 |
---|---|

Country | United States |

City | Monticello |

Period | 9/24/19 → 9/27/19 |

### All Science Journal Classification (ASJC) codes

- Artificial Intelligence
- Computer Networks and Communications
- Hardware and Architecture
- Safety, Risk, Reliability and Quality
- Control and Optimization

## Fingerprint Dive into the research topics of 'Learning to Control in Metric Space with Optimal Regret'. Together they form a unique fingerprint.

## Cite this

*2019 57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019*(pp. 726-733). [8919864] (2019 57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2019.8919864