Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations
Abstract
We study online adaptive policy selection in systems with time-varying costs and dynamics. We develop the Gradient-based Adaptive Policy Selection (GAPS) algorithm together with a general analytical framework for online policy selection via online optimization. Under our proposed notion of contractive policy classes, we show that GAPS approximates the behavior of an ideal online gradient descent algorithm on the policy parameters while requiring less information and computation. When convexity holds, our algorithm is the first to achieve optimal policy regret. When convexity does not hold, we provide the first local regret bound for online policy selection. Our numerical experiments show that GAPS can adapt to changing environments more quickly than existing benchmarks.
Cite
Text
Lin et al. "Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations." Neural Information Processing Systems, 2023.Markdown
[Lin et al. "Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/lin2023neurips-online/)BibTeX
@inproceedings{lin2023neurips-online,
title = {{Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations}},
author = {Lin, Yiheng and Preiss, James A. and Anand, Emile and Li, Yingying and Yue, Yisong and Wierman, Adam},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/lin2023neurips-online/}
}