2024-04-18-depavia24a.md

title	software	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Learning-Based Algorithms for Graph Searching Problems	https://github.com/ADePavia/graph_searching	We consider the problem of graph searching with prediction recently introduced by Banerjee et al. (2023). In this problem, an agent starting at some vertex r has to traverse a (potentially unknown) graph G to find a hidden goal node g while minimizing the total distance traveled. We study a setting in which at any node v, the agent receives a noisy estimate of the distance from v to g. We design algorithms for this search task on unknown graphs. We establish the first formal guarantees on unknown weighted graphs and provide lower bounds showing that the algorithms we propose have optimal or nearly-optimal dependence on the prediction error. Further, we perform numerical experiments demonstrating that in addition to being robust to adversarial error, our algorithms perform well in typical instances in which the error is stochastic. Finally, we provide simpler performance bounds on the algorithms of Banerjee et al. (2023) for the case of searching on a known graph and establish new lower bounds for this setting.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	depavia24a	0	Learning-Based Algorithms for Graph Searching Problems	928	936	928-936	928	false	DePavia, Adela F. and Tani, Erasmo and Vakilian, Ali	given family Adela F. DePavia given family Erasmo Tani given family Ali Vakilian	2024-04-18		Proceedings of The 27th International Conference on Artificial Intelligence and Statistics	238	inproceedings	date-parts 2024 4 18	https://proceedings.mlr.press/v238/depavia24a/depavia24a.pdf