Open Problem: Online Sabotaged Shortest Path

Wouter M. Koolen, Manfred K. Warmuth, Dmitri Adamskiy
Proceedings of The 28th Conference on Learning Theory, PMLR 40:1764-1766, 2015.

Abstract

There has been much work on extending the prediction with expert advice methodology to the case when experts are composed of components and there are combinatorially many such experts. One of the core examples is the Online Shortest Path problem where the components are edges and the experts are paths. In this note we revisit this online routing problem in the case where in each trial some of the edges or components are sabotaged / blocked. In the vanilla expert setting a known method can solve this extension where experts are now awake or asleep in each trial. We ask whether this technology can be upgraded efficiently to the case when at each trial every component can be awake or asleep. It is easy get to get an initial regret bound by using combinatorially many experts. However it is open whether there are efficient algorithms achieving the same regret.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Koolen15b, title = {Open Problem: Online Sabotaged Shortest Path}, author = {Koolen, Wouter M. and Warmuth, Manfred K. and Adamskiy, Dmitri}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {1764--1766}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Koolen15b.pdf}, url = {https://proceedings.mlr.press/v40/Koolen15b.html}, abstract = {There has been much work on extending the prediction with expert advice methodology to the case when experts are composed of components and there are combinatorially many such experts. One of the core examples is the Online Shortest Path problem where the components are edges and the experts are paths. In this note we revisit this online routing problem in the case where in each trial some of the edges or components are sabotaged / blocked. In the vanilla expert setting a known method can solve this extension where experts are now awake or asleep in each trial. We ask whether this technology can be upgraded efficiently to the case when at each trial every component can be awake or asleep. It is easy get to get an initial regret bound by using combinatorially many experts. However it is open whether there are efficient algorithms achieving the same regret.} }
Endnote
%0 Conference Paper %T Open Problem: Online Sabotaged Shortest Path %A Wouter M. Koolen %A Manfred K. Warmuth %A Dmitri Adamskiy %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Koolen15b %I PMLR %P 1764--1766 %U https://proceedings.mlr.press/v40/Koolen15b.html %V 40 %X There has been much work on extending the prediction with expert advice methodology to the case when experts are composed of components and there are combinatorially many such experts. One of the core examples is the Online Shortest Path problem where the components are edges and the experts are paths. In this note we revisit this online routing problem in the case where in each trial some of the edges or components are sabotaged / blocked. In the vanilla expert setting a known method can solve this extension where experts are now awake or asleep in each trial. We ask whether this technology can be upgraded efficiently to the case when at each trial every component can be awake or asleep. It is easy get to get an initial regret bound by using combinatorially many experts. However it is open whether there are efficient algorithms achieving the same regret.
RIS
TY - CPAPER TI - Open Problem: Online Sabotaged Shortest Path AU - Wouter M. Koolen AU - Manfred K. Warmuth AU - Dmitri Adamskiy BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Koolen15b PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 1764 EP - 1766 L1 - http://proceedings.mlr.press/v40/Koolen15b.pdf UR - https://proceedings.mlr.press/v40/Koolen15b.html AB - There has been much work on extending the prediction with expert advice methodology to the case when experts are composed of components and there are combinatorially many such experts. One of the core examples is the Online Shortest Path problem where the components are edges and the experts are paths. In this note we revisit this online routing problem in the case where in each trial some of the edges or components are sabotaged / blocked. In the vanilla expert setting a known method can solve this extension where experts are now awake or asleep in each trial. We ask whether this technology can be upgraded efficiently to the case when at each trial every component can be awake or asleep. It is easy get to get an initial regret bound by using combinatorially many experts. However it is open whether there are efficient algorithms achieving the same regret. ER -
APA
Koolen, W.M., Warmuth, M.K. & Adamskiy, D.. (2015). Open Problem: Online Sabotaged Shortest Path. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:1764-1766 Available from https://proceedings.mlr.press/v40/Koolen15b.html.

Related Material