More Like this

1. An explore-then-commit algorithm for submodular maximization under full-bandit feedback

   Nie, Guanyu; Agarwal, Mridul; Umrawal, Abhishek Kumar; Aggarwal, Vaneet; Quinn, Christopher John (January 2022, Uncertainty in Artificial Intelligence)

   Cussens, James; Zhang, Kun (Ed.)

   We investigate the problem of combinatorial multi-armed bandits with stochastic submodular (in expectation) rewards and full-bandit feedback, where no extra information other than the reward of selected action at each time step $$t$$ is observed. We propose a simple algorithm, Explore-Then-Commit Greedy (ETCG) and prove that it achieves a $(1-1/e)$-regret upper bound of $$\mathcal{O}(n^\frac{1}{3}k^\frac{4}{3}T^\frac{2}{3}\log(T)^\frac{1}{2})$$ for a horizon $$T$$, number of base elements $$n$$, and cardinality constraint $$k$$. We also show in experiments with synthetic and real-world data that the ETCG empirically outperforms other full-bandit methods. 

   more » « less
2. Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback

   Fourati, Fares; Aggarwal, Vaneet; Quinn, Christopher John; Alouini, Mohamed-Slim (April 2023, Proceedings of the International Workshop on Artificial Intelligence and Statistics)

   We investigate the problem of unconstrained combinatorial multi-armed bandits with full-bandit feedback and stochastic rewards for submodular maximization. Previous works investigate the same problem assuming a submodular and monotone reward function. In this work, we study a more general problem, i.e., when the reward function is not necessarily monotone, and the submodularity is assumed only in expectation. We propose Randomized Greedy Learning (RGL) algorithm and theoretically prove that it achieves a $$\frac{1}{2}$$-regret upper bound of $$\Tilde{\mathcal{O}}(n T^{\frac{2}{3}})$$ for horizon $$T$$ and number of arms $$n$$. We also show in experiments that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings. 

   more » « less
3. Bandit Online Linear Optimization with Hints and Queries

   Bhaskara, Aditya; Cutkosky, Ashok; Kumar, Ravi; Purohit, Manish (July 2023, Proceedings of Machine Learning Research)

   We study variants of the online linear optimization (OLO) problem with bandit feedback, where the algorithm has access to external information about the unknown cost vector. Our motivation is the recent body of work on using such “hints” towards improving regret bounds for OLO problems in the full-information setting. Unlike in the full-information OLO setting, with bandit feedback, we first show that one cannot improve the standard regret bounds of O(\sqrt{T}) by using hints, even if they are always well-correlated with the cost vector. In contrast, if the algorithm is empowered to issue queries and if all the responses are correct, then we show O(\log(T)) regret is achievable. We then show how to make this result more robust — when some of the query responses can be adversarial — by using a little feedback on the quality of the responses. 

   more » « less
4. Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback

   Fares Fourati, Vaneet Aggarwal (January 2023, Proceedings of Machine Learning Research)

   We investigate the problem of unconstrained combinatorial multi-armed bandits with fullbandit feedback and stochastic rewards for submodular maximization. Previous works investigate the same problem assuming a submodular and monotone reward function. In this work, we study a more general problem, i.e., when the reward function is not necessarily monotone, and the submodularity is assumed only in expectation. We propose Randomized Greedy Learning (RGL) algorithm and theoretically prove that it achieves a 1 2 -regret upper bound of O˜(nT 2 3 ) for horizon T and number of arms n. We also show in experiments that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings. 

   more » « less
5. Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization

   Pedramfar, Mohammad; Nadew, Yididiya Y; Quinn, Christopher J; Aggarwal; Vaneet (May 2024, The Twelfth International Conference on Learning Representations)

   This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial continuous DR-submodular optimization, spanning scenarios such as full information and (semi-)bandit feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. For every problem considered in the non-monotone setting, the proposed algorithms are either the first with proven sub-linear $$\alpha$$-regret bounds or have better $$\alpha$$-regret bounds than the state of the art, where $$\alpha$$ is a corresponding approximation bound in the offline setting. In the monotone setting, the proposed approach gives state-of-the-art sub-linear $$\alpha$$-regret bounds among projection-free algorithms in 7 of the 8 considered cases while matching the result of the remaining case. Additionally, this paper addresses semi-bandit and bandit feedback for adversarial DR-submodular optimization, advancing the understanding of this optimization area. 

   more » « less