Online Submodular Resource Allocation with Applications to Rebalancing Shared Mobility Systems

Pier Giuseppe Sessa, Ilija Bogunovic, Andreas Krause, Maryam Kamgarpour
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:9455-9464, 2021.

Abstract

Motivated by applications in shared mobility, we address the problem of allocating a group of agents to a set of resources to maximize a cumulative welfare objective. We model the welfare obtainable from each resource as a monotone DR-submodular function which is a-priori unknown and can only be learned by observing the welfare of selected allocations. Moreover, these functions can depend on time-varying contextual information. We propose a distributed scheme to maximize the cumulative welfare by designing a repeated game among the agents, who learn to act via regret minimization. We propose two design choices for the game rewards based on upper confidence bounds built around the unknown welfare functions. We analyze them theoretically, bounding the gap between the cumulative welfare of the game and the highest cumulative welfare obtainable in hindsight. Finally, we evaluate our approach in a realistic case study of rebalancing a shared mobility system (i.e., positioning vehicles in strategic areas). From observed trip data, our algorithm gradually learns the users’ demand pattern and improves the overall system operation.

Cite this Paper


BibTeX
@InProceedings{pmlr-v139-sessa21a, title = {Online Submodular Resource Allocation with Applications to Rebalancing Shared Mobility Systems}, author = {Sessa, Pier Giuseppe and Bogunovic, Ilija and Krause, Andreas and Kamgarpour, Maryam}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {9455--9464}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/sessa21a/sessa21a.pdf}, url = {https://proceedings.mlr.press/v139/sessa21a.html}, abstract = {Motivated by applications in shared mobility, we address the problem of allocating a group of agents to a set of resources to maximize a cumulative welfare objective. We model the welfare obtainable from each resource as a monotone DR-submodular function which is a-priori unknown and can only be learned by observing the welfare of selected allocations. Moreover, these functions can depend on time-varying contextual information. We propose a distributed scheme to maximize the cumulative welfare by designing a repeated game among the agents, who learn to act via regret minimization. We propose two design choices for the game rewards based on upper confidence bounds built around the unknown welfare functions. We analyze them theoretically, bounding the gap between the cumulative welfare of the game and the highest cumulative welfare obtainable in hindsight. Finally, we evaluate our approach in a realistic case study of rebalancing a shared mobility system (i.e., positioning vehicles in strategic areas). From observed trip data, our algorithm gradually learns the users’ demand pattern and improves the overall system operation.} }
Endnote
%0 Conference Paper %T Online Submodular Resource Allocation with Applications to Rebalancing Shared Mobility Systems %A Pier Giuseppe Sessa %A Ilija Bogunovic %A Andreas Krause %A Maryam Kamgarpour %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-sessa21a %I PMLR %P 9455--9464 %U https://proceedings.mlr.press/v139/sessa21a.html %V 139 %X Motivated by applications in shared mobility, we address the problem of allocating a group of agents to a set of resources to maximize a cumulative welfare objective. We model the welfare obtainable from each resource as a monotone DR-submodular function which is a-priori unknown and can only be learned by observing the welfare of selected allocations. Moreover, these functions can depend on time-varying contextual information. We propose a distributed scheme to maximize the cumulative welfare by designing a repeated game among the agents, who learn to act via regret minimization. We propose two design choices for the game rewards based on upper confidence bounds built around the unknown welfare functions. We analyze them theoretically, bounding the gap between the cumulative welfare of the game and the highest cumulative welfare obtainable in hindsight. Finally, we evaluate our approach in a realistic case study of rebalancing a shared mobility system (i.e., positioning vehicles in strategic areas). From observed trip data, our algorithm gradually learns the users’ demand pattern and improves the overall system operation.
APA
Sessa, P.G., Bogunovic, I., Krause, A. & Kamgarpour, M.. (2021). Online Submodular Resource Allocation with Applications to Rebalancing Shared Mobility Systems. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:9455-9464 Available from https://proceedings.mlr.press/v139/sessa21a.html.

Related Material