Timezone: »
Poster
Congested Bandits: Optimal Routing via Short-term Resets
Pranjal Awasthi · Kush Bhatia · Sreenivas Gollapudi · Kostas Kollias
For traffic routing platforms, the choice of which route to recommend to a user depends on the congestion on these routes -- indeed, an individual's utility depends on the number of people using the recommended route at that instance. Motivated by this, we introduce the problem of Congested Bandits where each arm's reward is allowed to depend on the number of times it was played in the past $\Delta$ timesteps. This dependence on past history of actions leads to a dynamical system where an algorithm's present choices also affect its future pay-offs, and requires an algorithm to plan for this. We study the congestion aware formulation in the multi-armed bandit (MAB) setup and in the contextual bandit setup with linear rewards. For the multi-armed setup, we propose a UCB style algorithm and show that its policy regret scales as $\tilde{O}(\sqrt{K \Delta T})$. For the linear contextual bandit setup, our algorithm, based on an iterative least squares planner, achieves policy regret $\tilde{O}(\sqrt{dT} + \Delta)$. From an experimental standpoint, we corroborate the no-regret properties of our algorithms via a simulation study.
Author Information
Pranjal Awasthi (Google)
Kush Bhatia (UC Berkeley)
Sreenivas Gollapudi (Google Research)
Kostas Kollias (Google Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Spotlight: Congested Bandits: Optimal Routing via Short-term Resets »
Wed. Jul 20th 05:50 -- 05:55 PM Room Room 327 - 329
More from the Same Authors
-
2022 Poster: Do More Negative Samples Necessarily Hurt In Contrastive Learning? »
Pranjal Awasthi · Nishanth Dikkala · Pritish Kamath -
2022 Oral: Do More Negative Samples Necessarily Hurt In Contrastive Learning? »
Pranjal Awasthi · Nishanth Dikkala · Pritish Kamath -
2022 Poster: Agnostic Learnability of Halfspaces via Logistic Loss »
Ziwei Ji · Kwangjun Ahn · Pranjal Awasthi · Satyen Kale · Stefani Karp -
2022 Oral: Agnostic Learnability of Halfspaces via Logistic Loss »
Ziwei Ji · Kwangjun Ahn · Pranjal Awasthi · Satyen Kale · Stefani Karp -
2022 Poster: H-Consistency Bounds for Surrogate Loss Minimizers »
Pranjal Awasthi · Anqi Mao · Mehryar Mohri · Yutao Zhong -
2022 Poster: Individual Preference Stability for Clustering »
Saba Ahmadi · Pranjal Awasthi · Samir Khuller · Matthäus Kleindessner · Jamie Morgenstern · Pattara Sukprasert · Ali Vakilian -
2022 Poster: Active Sampling for Min-Max Fairness »
Jacob Abernethy · Pranjal Awasthi · Matthäus Kleindessner · Jamie Morgenstern · Chris Russell · Jie Zhang -
2022 Oral: H-Consistency Bounds for Surrogate Loss Minimizers »
Pranjal Awasthi · Anqi Mao · Mehryar Mohri · Yutao Zhong -
2022 Oral: Individual Preference Stability for Clustering »
Saba Ahmadi · Pranjal Awasthi · Samir Khuller · Matthäus Kleindessner · Jamie Morgenstern · Pattara Sukprasert · Ali Vakilian -
2022 Spotlight: Active Sampling for Min-Max Fairness »
Jacob Abernethy · Pranjal Awasthi · Matthäus Kleindessner · Jamie Morgenstern · Chris Russell · Jie Zhang -
2020 : Short Talk 6 - Preference learning along multiple criteria: A game-theoretic perspective »
Kush Bhatia -
2019 Poster: POLITEX: Regret Bounds for Policy Iteration using Expert Prediction »
Yasin Abbasi-Yadkori · Peter Bartlett · Kush Bhatia · Nevena Lazic · Csaba Szepesvari · Gellért Weisz -
2019 Poster: Online Algorithms for Rent-Or-Buy with Expert Advice »
Sreenivas Gollapudi · Debmalya Panigrahi -
2019 Oral: Online Algorithms for Rent-Or-Buy with Expert Advice »
Sreenivas Gollapudi · Debmalya Panigrahi -
2019 Oral: POLITEX: Regret Bounds for Policy Iteration using Expert Prediction »
Yasin Abbasi-Yadkori · Peter Bartlett · Kush Bhatia · Nevena Lazic · Csaba Szepesvari · Gellért Weisz -
2019 Poster: Hiring Under Uncertainty »
Manish Purohit · Sreenivas Gollapudi · Manish Raghavan -
2019 Oral: Hiring Under Uncertainty »
Manish Purohit · Sreenivas Gollapudi · Manish Raghavan