Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms
Abstract
This paper introduces the online state exploration problem. In the problem, there is a hidden d -dimensional target state. We are given a distance function between different states in the space and a penalty function depending on the current state for each incorrect guess. The goal is to move to a vector that dominates the target state starting from the origin in the d -dimensional space while minimizing the total distance and penalty cost. This problem generalizes several natural online discrete optimization problems such as multi-dimensional knapsack cover, cow path, online bidding, and online search. For online state exploration, the paper gives results in the worst-case competitive analysis model and in the online algorithms augmented with the prediction model. The results extend and generalize many known results in the online setting.
Cite
Text
Im et al. "Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2023. doi:10.1007/978-3-031-43421-1_20Markdown
[Im et al. "Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2023.](https://mlanthology.org/ecmlpkdd/2023/im2023ecmlpkdd-online/) doi:10.1007/978-3-031-43421-1_20BibTeX
@inproceedings{im2023ecmlpkdd-online,
title = {{Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms}},
author = {Im, Sungjin and Moseley, Benjamin and Xu, Chenyang and Zhang, Ruilong},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2023},
pages = {333-348},
doi = {10.1007/978-3-031-43421-1_20},
url = {https://mlanthology.org/ecmlpkdd/2023/im2023ecmlpkdd-online/}
}