Timezone: »
Recent work has considered natural variations of the {\em multi-armed bandit} problem, where the reward distribution of each arm is a special function of the time passed since its last pulling. In this direction, a simple (yet widely applicable) model is that of {\em blocking bandits}, where an arm becomes unavailable for a deterministic number of rounds after each play. In this work, we extend the above model in two directions: (i) We consider the general combinatorial setting where more than one arms can be played at each round, subject to feasibility constraints. (ii) We allow the blocking time of each arm to be stochastic. We first study the computational/unconditional hardness of the above setting and identify the necessary conditions for the problem to become tractable (even in an approximate sense). Based on these conditions, we provide a tight analysis of the approximation guarantee of a natural greedy heuristic that always plays the maximum expected reward feasible subset among the available (non-blocked) arms. When the arms' expected rewards are unknown, we adapt the above heuristic into a bandit algorithm, based on UCB, for which we provide sublinear (approximate) regret guarantees, matching the theoretical lower bounds in the limiting case of absence of delays.
Author Information
Alexia Atsidakou (University of Texas at Austin)
Orestis Papadigenopoulos (The University of Texas at Austin)
Soumya Basu (Google)
Constantine Caramanis (University of Texas)
Sanjay Shakkottai (University of Texas at Austin)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: Combinatorial Blocking Bandits with Stochastic Delays »
Thu. Jul 22nd 04:00 -- 06:00 AM Room
More from the Same Authors
-
2021 : Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators »
Zaiwei Chen · Siva Maguluri · Sanjay Shakkottai · Karthikeyan Shanmugam -
2021 : Under-exploring in Bandits with Confounded Data »
Nihal Sharma · Soumya Basu · Karthikeyan Shanmugam · Sanjay Shakkottai -
2023 Poster: Last Switch Dependent Bandits with Monotone Payoff Functions »
Ayoub Foussoul · Vineet Goyal · Orestis Papadigenopoulos · Assaf Zeevi -
2023 Poster: A Statistical Perspective on Retrieval-Based Models »
Soumya Basu · Ankit Singh Rawat · Manzil Zaheer -
2023 Poster: Reward-Mixing MDPs with Few Latent Contexts are Learnable »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2023 Poster: Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits »
Ronshee Chawla · Daniel Vial · Sanjay Shakkottai · R Srikant -
2023 Poster: PAC Generalization via Invariant Representations »
Advait Parulekar · Karthikeyan Shanmugam · Sanjay Shakkottai -
2022 Poster: MAML and ANIL Provably Learn Representations »
Liam Collins · Aryan Mokhtari · Sewoong Oh · Sanjay Shakkottai -
2022 Poster: Asymptotically-Optimal Gaussian Bandits with Side Observations »
Alexia Atsidakou · Orestis Papadigenopoulos · Constantine Caramanis · Sujay Sanghavi · Sanjay Shakkottai -
2022 Spotlight: Asymptotically-Optimal Gaussian Bandits with Side Observations »
Alexia Atsidakou · Orestis Papadigenopoulos · Constantine Caramanis · Sujay Sanghavi · Sanjay Shakkottai -
2022 Spotlight: MAML and ANIL Provably Learn Representations »
Liam Collins · Aryan Mokhtari · Sewoong Oh · Sanjay Shakkottai -
2022 Poster: Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation »
Daniel Vial · Advait Parulekar · Sanjay Shakkottai · R Srikant -
2022 Spotlight: Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation »
Daniel Vial · Advait Parulekar · Sanjay Shakkottai · R Srikant -
2022 Poster: Linear Bandit Algorithms with Sublinear Time Complexity »
Shuo Yang · Tongzheng Ren · Sanjay Shakkottai · Eric Price · Inderjit Dhillon · Sujay Sanghavi -
2022 Poster: Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2022 Spotlight: Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2022 Spotlight: Linear Bandit Algorithms with Sublinear Time Complexity »
Shuo Yang · Tongzheng Ren · Sanjay Shakkottai · Eric Price · Inderjit Dhillon · Sujay Sanghavi -
2021 Poster: Exploiting Shared Representations for Personalized Federated Learning »
Liam Collins · Hamed Hassani · Aryan Mokhtari · Sanjay Shakkottai -
2021 Spotlight: Exploiting Shared Representations for Personalized Federated Learning »
Liam Collins · Hamed Hassani · Aryan Mokhtari · Sanjay Shakkottai -
2021 Poster: Beyond $log^2(T)$ regret for decentralized bandits in matching markets »
Soumya Basu · Karthik Abinav Sankararaman · Abishek Sankararaman -
2021 Spotlight: Beyond $log^2(T)$ regret for decentralized bandits in matching markets »
Soumya Basu · Karthik Abinav Sankararaman · Abishek Sankararaman -
2020 Poster: Learning Mixtures of Graphs from Epidemic Cascades »
Jessica Hoffmann · Soumya Basu · Surbhi Goel · Constantine Caramanis -
2019 Poster: Robust Estimation of Tree Structured Gaussian Graphical Models »
Ashish Katiyar · Jessica Hoffmann · Constantine Caramanis -
2019 Poster: Pareto Optimal Streaming Unsupervised Classification »
Soumya Basu · Steven Gutstein · Brent Lance · Sanjay Shakkottai -
2019 Oral: Pareto Optimal Streaming Unsupervised Classification »
Soumya Basu · Steven Gutstein · Brent Lance · Sanjay Shakkottai -
2019 Oral: Robust Estimation of Tree Structured Gaussian Graphical Models »
Ashish Katiyar · Jessica Hoffmann · Constantine Caramanis -
2018 Poster: Multi-Fidelity Black-Box Optimization with Hierarchical Partitions »
Rajat Sen · kirthevasan kandasamy · Sanjay Shakkottai -
2018 Oral: Multi-Fidelity Black-Box Optimization with Hierarchical Partitions »
Rajat Sen · kirthevasan kandasamy · Sanjay Shakkottai -
2017 Poster: Identifying Best Interventions through Online Importance Sampling »
Rajat Sen · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai -
2017 Talk: Identifying Best Interventions through Online Importance Sampling »
Rajat Sen · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai