A Survey on Practical Applications of Multi-Armed and Contextual Bandits
---
paper_title: Interactive Anomaly Detection on Attributed Networks

paper_content:

Performing anomaly detection on attributed networks concerns with finding nodes whose patterns or behaviors deviate significantly from the majority of reference nodes. Its success can be easily found in many real-world applications such as network intrusion detection, opinion spam detection and system fault diagnosis, to name a few. Despite their empirical success, a vast majority of existing efforts are overwhelmingly performed in an unsupervised scenario due to the expensive labeling costs of ground truth anomalies. In fact, in many scenarios, a small amount of prior human knowledge of the data is often effortless to obtain, and getting it involved in the learning process has shown to be effective in advancing many important learning tasks. Additionally, since new types of anomalies may constantly arise over time especially in an adversarial environment, the interests of human expert could also change accordingly regarding to the detected anomaly types. It brings further challenges to conventional anomaly detection algorithms as they are often applied in a batch setting and are incapable to interact with the environment. To tackle the above issues, in this paper, we investigate the problem of anomaly detection on attributed networks in an interactive setting by allowing the system to proactively communicate with the human expert in making a limited number of queries about ground truth anomalies. Our objective is to maximize the true anomalies presented to the human expert after a given budget is used up. Along with this line, we formulate the problem through the principled multi-armed bandit framework and develop a novel collaborative contextual bandit algorithm, named GraphUCB. In particular, our developed algorithm: (1) explicitly models the nodal attributes and node dependencies seamlessly in a joint framework; and (2) handles the exploration-exploitation dilemma when querying anomalies of different types. Extensive experiments on real-world datasets show the improvement of the proposed algorithm over the state-of-the-art algorithms.
---
paper_title: Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback

paper_content:

We study the online influence maximization problem in social networks under the independent cascade model. Specifically, we aim to learn the set of "best influencers" in a social network online while repeatedly interacting with it. We address the challenges of (i) combinatorial action space, since the number of feasible influencer sets grows exponentially with the maximum number of influencers, and (ii) limited feedback, since only the influenced portion of the network is observed. Under a stochastic semi-bandit feedback, we propose and analyze IMLinUCB, a computationally efficient UCB-based algorithm. Our bounds on the cumulative regret are polynomial in all quantities of interest, achieve near-optimal dependence on the number of interactions and reflect the topology of the network and the activation probabilities of its edges, thereby giving insights on the problem complexity. To the best of our knowledge, these are the first such results. Our experiments show that in several representative graph topologies, the regret of IMLinUCB scales as suggested by our upper bounds. IMLinUCB permits linear generalization and thus is both statistically and computationally suitable for large-scale problems. Our experiments also show that IMLinUCB with linear generalization can lead to low regret in real-world online influence maximization.
---
paper_title: Interactive Anomaly Detection on Attributed Networks

paper_content:

Performing anomaly detection on attributed networks concerns with finding nodes whose patterns or behaviors deviate significantly from the majority of reference nodes. Its success can be easily found in many real-world applications such as network intrusion detection, opinion spam detection and system fault diagnosis, to name a few. Despite their empirical success, a vast majority of existing efforts are overwhelmingly performed in an unsupervised scenario due to the expensive labeling costs of ground truth anomalies. In fact, in many scenarios, a small amount of prior human knowledge of the data is often effortless to obtain, and getting it involved in the learning process has shown to be effective in advancing many important learning tasks. Additionally, since new types of anomalies may constantly arise over time especially in an adversarial environment, the interests of human expert could also change accordingly regarding to the detected anomaly types. It brings further challenges to conventional anomaly detection algorithms as they are often applied in a batch setting and are incapable to interact with the environment. To tackle the above issues, in this paper, we investigate the problem of anomaly detection on attributed networks in an interactive setting by allowing the system to proactively communicate with the human expert in making a limited number of queries about ground truth anomalies. Our objective is to maximize the true anomalies presented to the human expert after a given budget is used up. Along with this line, we formulate the problem through the principled multi-armed bandit framework and develop a novel collaborative contextual bandit algorithm, named GraphUCB. In particular, our developed algorithm: (1) explicitly models the nodal attributes and node dependencies seamlessly in a joint framework; and (2) handles the exploration-exploitation dilemma when querying anomalies of different types. Extensive experiments on real-world datasets show the improvement of the proposed algorithm over the state-of-the-art algorithms.
---
paper_title: Algorithm Selection as a Bandit Problem with Unbounded Losses

paper_content:

Algorithm selection is typically based on models of algorithm performance learned during a separate offline training sequence, which can be prohibitively expensive. In recent work, we adopted an online approach, in which a performance model is iteratively updated and used to guide selection on a sequence of problem instances. The resulting exploration-exploitation trade-off was represented as a bandit problem with expert advice, using an existing solver for this game, but this required the setting of an arbitrary bound on algorithm runtimes, thus invalidating the optimal regret of the solver. In this paper, we propose a simpler framework for representing algorithm selection as a bandit problem, with partial information, and an unknown bound on losses. We adapt an existing solver to this game, proving a bound on its expected regret, which holds also for the resulting algorithm selection technique. We present experiments with a set of SAT solvers on a mixed SAT-UNSAT benchmark.
---
paper_title: Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback

paper_content:

We study the online influence maximization problem in social networks under the independent cascade model. Specifically, we aim to learn the set of "best influencers" in a social network online while repeatedly interacting with it. We address the challenges of (i) combinatorial action space, since the number of feasible influencer sets grows exponentially with the maximum number of influencers, and (ii) limited feedback, since only the influenced portion of the network is observed. Under a stochastic semi-bandit feedback, we propose and analyze IMLinUCB, a computationally efficient UCB-based algorithm. Our bounds on the cumulative regret are polynomial in all quantities of interest, achieve near-optimal dependence on the number of interactions and reflect the topology of the network and the activation probabilities of its edges, thereby giving insights on the problem complexity. To the best of our knowledge, these are the first such results. Our experiments show that in several representative graph topologies, the regret of IMLinUCB scales as suggested by our upper bounds. IMLinUCB permits linear generalization and thus is both statistically and computationally suitable for large-scale problems. Our experiments also show that IMLinUCB with linear generalization can lead to low regret in real-world online influence maximization.
---
paper_title: Algorithm Selection as a Bandit Problem with Unbounded Losses

paper_content:

Algorithm selection is typically based on models of algorithm performance learned during a separate offline training sequence, which can be prohibitively expensive. In recent work, we adopted an online approach, in which a performance model is iteratively updated and used to guide selection on a sequence of problem instances. The resulting exploration-exploitation trade-off was represented as a bandit problem with expert advice, using an existing solver for this game, but this required the setting of an arbitrary bound on algorithm runtimes, thus invalidating the optimal regret of the solver. In this paper, we propose a simpler framework for representing algorithm selection as a bandit problem, with partial information, and an unknown bound on losses. We adapt an existing solver to this game, proving a bound on its expected regret, which holds also for the resulting algorithm selection technique. We present experiments with a set of SAT solvers on a mixed SAT-UNSAT benchmark.
---

Title: A Survey on Practical Applications of Multi-Armed and Contextual Bandits

Section 1: Introduction
Description 1: Introduce the survey with a discussion of sequential decision-making problems, the exploration vs. exploitation trade-off, and an overview of the multi-armed bandit (MAB) and contextual bandit (CMAB) problems.

Section 2: Real-Life Applications of Bandit
Description 2: Provide an overview of various real-life applications of the bandit framework, including different practical domains.

Section 3: Healthcare
Description 3: Discuss the application of bandit algorithms in healthcare, focusing on clinical trials, treatment dosage, and brain and behavior modeling.

Section 4: Finance
Description 4: Cover the use of bandit algorithms in finance, specifically in sequential portfolio selection and risk-aware portfolio construction.

Section 5: Dynamic Pricing
Description 5: Explain how bandit algorithms can be applied to dynamic pricing problems faced by online retailers.

Section 6: Recommender Systems
Description 6: Discuss the application of bandit algorithms in recommender systems, addressing challenges like the exploration-exploitation dilemma and content evolution.

Section 7: Influence Maximization
Description 7: Describe the use of bandit algorithms for influence maximization in social networks, including various proposed algorithms.

Section 8: Information Retrieval
Description 8: Discuss the application of bandit algorithms in information retrieval tasks, such as document adjudication and mobile information retrieval.

Section 9: Dialogue Systems
Description 9: Explore the use of bandit algorithms in dialogue systems, including response selection, proactive dialogue, and multi-domain dialogue orchestration.

Section 10: Anomaly Detection
Description 10: Cover how bandit algorithms are applied to anomaly detection, specifically in networks and credit card fraud detection.

Section 11: Telecommunication
Description 11: Describe the application of bandit algorithms in telecommunications, including wireless network selection and optimization of communication parameters.

Section 12: Bandit in Real-Life Applications: Summary and Future Directions
Description 12: Summarize the various applications discussed and highlight potential future research directions in applying bandit algorithms to real-life problems.

Section 13: Bandit for Better Machine Learning
Description 13: Discuss how bandit algorithms can improve machine-learning algorithms, such as algorithm selection, hyperparameter optimization, feature selection, and more.

Section 14: Algorithm Selection
Description 14: Explain how bandit algorithms can assist in selecting the best algorithm for a given problem instance.

Section 15: Hyperparameter Optimization
Description 15: Describe how bandit algorithms can be employed to optimize hyperparameters efficiently.

Section 16: Feature Selection
Description 16: Discuss the application of bandit algorithms in feature selection for enhancing model performance.

Section 17: Bandit for Active Learning
Description 17: Cover the application of bandit algorithms in active learning to select the most informative samples for labeling.

Section 18: Clustering
Description 18: Describe how bandit algorithms can be used in collaborative clustering for multi-view and distributed data clustering.

Section 19: Reinforcement Learning
Description 19: Explore the integration of bandit algorithms with reinforcement learning to orchestrate policy choice and enhance learning.

Section 20: Conclusions
Description 20: Conclude the survey by summarizing the notable contributions, open problems, and future directions in the research on bandit algorithms.