Source-linked AI summary
A Survey on Practical Applications of Multi-Armed and Contextual Bandits
Djallel Bouneffouf, Irina Rish
TL;DR
Sequential decisions often involve limited feedback, and contextual bandits additionally use side information when choosing actions. This article surveys recent bandit applications, organizes them by setting, and identifies trends and open problems. Its synthesis presents bandit research as active and promising, while noting gaps in the settings covered by existing machine-learning applications.
Problem
Sequential decisions may provide feedback only for the chosen action, while existing bandit formulations described in the introduction may omit available context.
Source: §1 · p. 1Method
The article reviews recent multi-armed and contextual bandit applications, organizes them by bandit setting, and discusses advantages, open problems, and future extensions.
Source: §1 · pp. 1–2, §4 · p. 6Results
Takeaways & Limitations
The authors characterize bandit research as active and promising, with novel techniques and applications emerging each year.
Source: §4 · p. 6In the surveyed machine-learning settings, contextual bandits were not used for feature selection or hyperparameter optimization, and non-stationary bandits were rarely considered.
Source: Summary and Future Directions · p. 6
Abstract
from arXiv · showhide
In recent years, multi-armed bandit (MAB) framework has attracted a lot of attention in various applications, from recommender systems and information retrieval to healthcare and finance, due to its stellar performance combined with certain attractive properties, such as learning from less feedback. The multi-armed bandit field is currently flourishing, as novel problem settings and algorithms motivated by various practical applications are being introduced, building on top of the classical bandit problem. This article aims to provide a comprehensive review of top recent developments in multiple real-life applications of the multi-armed bandit. Specifically, we introduce a taxonomy of common MAB-based applications and summarize state-of-art for each of those domains. Furthermore, we identify important current trends and provide new perspectives pertaining to the future of this exciting and fast-growing field.
1 Introduction
Sequential decisions often provide limited feedback: an agent observes a reward only for the action it chooses, while balancing exploration and exploitation. The article reviews multi-armed and contextual bandit applications across practical domains and machine learning.
1 Introduction
- Sequential decisions arise in settings such as clinical trials, recommender systems, and anomaly detection, where feedback may be limited to the chosen option.In the clinical-trial example, context is a patient's medical record, actions are treatments, and reward reflects treatment outcome.Source: §1 · p. 1
- Classical MAB chooses among K arms with unknown reward distributions to maximize cumulative reward, but the described stochastic and Bayesian approaches do not account for context.The exploration–exploitation trade-off motivates this sequential decision framework.Source: §1 · p. 1
- In a contextual bandit, the agent observes an N-dimensional context before choosing an arm and uses past rewards to select an action for the current context.The aim is to learn the relationship between contexts and rewards over time.Source: §1 · p. 1
- The survey covers bandit applications in healthcare, computer-network routing, finance, and machine learning, including hyperparameter tuning and algorithmic choices.It also addresses supervised learning, active learning, and reinforcement learning.Source: §1 · pp. 1–2
2 Real-Life Applications of Bandit
The section frames bandits as a formalism for sequential decisions under uncertainty and surveys healthcare applications, including treatment allocation, dosing, and behavioral modeling.
2 Real-Life Applications of Bandit
- The stochastic multi-armed bandit formalizes sequential decision-making under uncertainty as an exploration-versus-exploitation problem.The survey presents it as a natural formalism for many real-life online decision problems.Source: §2 · p. 2
2.1 Healthcare
- Clinical-trial work models treatment allocation as a contextual bandit and uses subsampling within Gaussian Process regression to compare treatments with equivalent information.The adaptive strategy allocates more samples to explore promising treatments because conventional random allocation can make full-range disease-stage data difficult to collect safely.Source: §2.1 · p. 2
- Warfarin dosing work models initial dose assignment as a multi-armed bandit with high-dimensional covariates and proposes an algorithm based on the LASSO estimator.The dose varies across patients, and incorrect initial doses can have adverse consequences.Source: §2.1 · p. 2
- Behavioral modeling work [Bouneffouf et al., 2017a] extends Thompson Sampling to represent reward-processing biases associated with several neurological and psychiatric conditions.The authors present the framework as a first step toward a unifying computational model of reward-processing abnormalities across multiple mental conditions.Source: §2.1 · p. 2
2.2 Finance
The finance section describes bandit approaches to sequential portfolio selection that address risk and return through different portfolio-construction strategies.
2.2 Finance
- Shen et al. [2015] use correlations among arms to construct orthogonal portfolios and combine them with an upper-confidence-bound bandit framework for a risk-adjusted portfolio strategy.The resulting strategy combines passive and active investments.Source: §2.2 · p. 2
- Huo and Fu [2017] filter assets using financial-market topology and combine an optimal multi-armed bandit policy with coherent-risk minimization to balance risk and return.Source: §2.2 · p. 2
- Sequential portfolio selection frames investment choices as a bandit problem seeking to maximize cumulative reward while trading off exploration and exploitation.Source: §2.2 · p. 2
2.3 Dynamic Pricing
The section surveys bandit approaches to dynamic pricing and recommender systems, including methods that adapt decisions as demand, products, or user interests evolve.
2.3 Dynamic Pricing
- For incomplete demand information, Misra et al. [2018] combine multi-armed bandits with partial identification to balance immediate profit against learning for future profits.Source: §2.3 · p. 2
- For high-dimensional multi-product pricing, Mueller et al. [2018] reduce revenue maximization to online bandit convex optimization with observed demands as side information.Their approach operates in a projected low-dimensional space of latent product features while learning that space through online singular value decomposition.Source: §2.3 · pp. 2–3
2.4 Recommender Systems
- Recommender-system bandits address exploration and exploitation, with approaches for large or infinite item sets, evolving user interests, and recommendations of fresh documents.The cited work describes continuous exploration as a way to address cold start; other approaches adapt exploration to the situation or to users' risk.Source: §2.4 · p. 3
2.5 Influence Maximization
The survey covers online influence maximization with bandit methods, including approaches for learning seed selection under limited feedback. [Vaswani et al., 2017; Wen et al., 2017]
2.5 Influence Maximization
- [Vaswani et al., 2017] use a novel parametrization and a monotone, submodular surrogate for influence maximization, then develop a LinUCB-based algorithm for learning propagation factors.The parametrization is agnostic to the diffusion model and is described as statistically efficient to learn from data.Source: §2.5 · p. 3
- [Wen et al., 2017] propose IMLinUCB, a computationally efficient UCB-based algorithm for online seed selection with exponentially many feasible sets and feedback limited to influenced nodes.The approach addresses a combinatorial action space and observes only the influenced portion of the network.Source: §2.5 · p. 3
2.6 Information Retrieval
The survey describes bandit applications in information retrieval and dialogue systems, spanning document adjudication, online response selection, proactive dialogue, and multi-domain skill orchestration.
2.6 Information Retrieval
- model iterative information retrieval selection as a contextual bandit and propose seven document-adjudication methods across stationary and non-stationary settings.Their comparative study also includes methods designed for pooling-based evaluation and metasearch.Source: §2.6 · p. 3
2.7 Dialogue Systems
- [Liu et al., 2018] use a contextual bandit with nonlinear rewards for online dialogue response selection, combining bidirectional LSTM representations with customized Thompson sampling in polynomial feature space.The LSTM represents dialogue contexts and responses for input to the bandit.Source: §2.7 · p. 3
- [Silander and others, 2018] extend contextual bandits for proactive dialogue with two differentiable memory models that incorporate past interactions into reward estimation.The models are Convolutional Selective Memory Networks and Contextual Attentive Memory Network, the latter using differentiable attention over past interactions.Source: §2.7 · pp. 3–4
- [Upadhyay et al., 2018] formalize online posterior dialogue orchestration as a Context-Attentive Bandit with Observations, selecting skills under a skill-execution budget.The setting is evaluated on simulated non-conversational and proprietary conversational datasets.Source: §2.7 · p. 4
2.8 Anomaly Detection
The survey describes bandit approaches to anomaly detection, including querying experts about network anomalies and balancing exploration with exploitation in fraud review.
2.8 Anomaly Detection
- use a collaborative contextual bandit to select attributed-network anomalies for expert review, maximizing true anomalies presented within a query budget.Their algorithm jointly models node attributes and dependencies while handling exploration and exploitation across anomaly types.Source: §2.8 · p. 4
- model fraud investigation rewards and use an incremental regression tree to cluster transactions by expected reward for contextual-bandit allocation.Exploration investigates transactions to improve predictive models, while exploitation investigates transactions already detected as suspicious.Source: §2.8 · p. 4
2.9 Telecommunication
The survey covers bandit models for wireless network selection and communication-parameter adaptation, balancing user quality, energy consumption, and packet loss.
2.9 Telecommunication
- extend MAB with measure and use actions that can span multiple time steps, introducing measure-use-UCB1 and Measure with Logarithmic Interval for multi-RAT selection.The objective is to maximize quality perceived by the final user.Source: §2.9 · p. 4
- use bandit algorithms to select LoRaWAN spreading factor and emission power, managing energy consumption and packet loss better than an Adaptive Data Rate algorithm.The Adaptive Data Rate comparator adapts spreading factors and transmission powers based on Signal to Interference and Noise Ratio values.Source: §2.9 · p. 4
2.10 Bandit in Real-Life Applications: Summary and Future Directions
Table 1 summarizes the bandit formulations used across real-life application domains. The review identifies underexplored settings, including non-stationary bandits in healthcare.
2.10 Bandit in Real-Life Applications: Summary and Future Directions
- Table 1 summarizes the bandit problem formulations used in the real-life application domains discussed in the review.The passage names healthcare, computer network routing, and finance among the practical domains covered.Source: §2.10 · pp. 4–5, Table 1 · p. 4
- Non-stationary bandits had not been used in healthcare applications, while changing patient states may instead call for reinforcement learning.The review also points to adversarial anomalies as a setting where non-stationary contextual bandits with drift adaptation could be useful.Source: §2.10 · p. 5
- The review notes that existing work had not developed bandit algorithms for solving tasks across domains or transferring knowledge between them.It identifies multitask and transfer learning, along with continuous or lifelong learning, as future directions.Source: §2.10 · p. 5
3 Bandit for Better Machine Learning
The section surveys how bandit methods are applied to improve machine-learning algorithms and choices, including algorithm selection, hyperparameter search, active learning, clustering, and reinforcement learning.
3.1 Algorithm Selection
- Online algorithm selection updates performance models across problem instances; another bandit formulation handles partial information with an unknown bound on losses.The earlier bandit-with-expert-advice approach required an arbitrary runtime bound, invalidating the solver's optimal regret.Source: §3.1 · p. 5
3.2 Hyperparameter Optimization
- Hyperband allocates resources to randomly sampled hyperparameter configurations and achieved more than an order-of-magnitude speedup over popular Bayesian optimization methods on a variety of deep-learning and kernel-based problems.The approach formulates hyperparameter optimization as a pure-exploration, non-stochastic infinite-armed bandit with adaptive resource allocation and early stopping.Source: §3.2 · p. 5
3.3 Feature Selection
- For feature selection, bandit feedback supports online prediction using a small active feature set, including an epsilon-greedy approach and a combinatorial Thompson Sampling approach.The latter addresses feature selection as a combinatorial optimization problem in the stochastic bandit setting.Source: §3.3 · p. 5
3.4 Bandit for Active Learning
- Active learning methods use bandit ideas to select unlabeled examples for querying, including contextual-bandit Active Thompson Sampling and a pool-based binary-classification algorithm.Active Thompson Sampling samples a point from a distribution over the pool and queries its label.Source: §3.4 · p. 5
3.5 Clustering
- A non-stochastic multi-armed bandit is used to assess in real time which algorithms or views can contribute useful information in collaborative clustering.The setting addresses the difficulty of predicting in advance whether collaborations between models will be beneficial or detrimental.Source: §3.5 · p. 6
3.6 Reinforcement learning
- A contextual-bandit orchestrator chooses between constraint-based and reward-based policies, while an epochal stochastic bandit selects an off-policy reinforcement-learning algorithm for each trajectory.The first approach learns implicit social constraints from behavior traces; the second freezes policy updates during each epoch.Source: §3.6 · p. 6
3.7 Bandit for Machine Learning:
- Table 2 summarizes the types of bandit problems used for the machine-learning tasks reviewed in this section.The accompanying discussion observes that contextual bandits were not used for feature selection or hyperparameter optimization, and non-stationary bandits were rarely considered.Source: Summary and Future Directions · p. 6, Table 2 · p. 6
Summary and Future Directions
- The review identifies that each surveyed technique addresses one machine-learning problem at a time and raises multitask, transfer, and continual learning as open directions.It suggests combinatorial bandits as one possible framework for solving multiple machine-learning problems simultaneously.Source: Summary and Future Directions · p. 6
4 Conclusions
The conclusion presents the article as a review of recent multi-armed and contextual bandit applications in real-life domains and automated machine learning. It also highlights open problems and future extensions in an active and promising research area.
4 Conclusions
- The article organizes notable recent multi-armed and contextual bandit applications across real-life domains and automated machine learning, and outlines open problems and future extensions.It summarizes applications by bandit setting and discusses advantages of bandit techniques in each domain.Source: §4 · p. 6
- The authors describe multi-armed and contextual bandits as active, promising research areas with novel techniques and applications emerging each year.Source: §4 · p. 6