Multi-Armed Bandit for Active Learning

In this formulation, each arm of the bandit corresponds to a distinct active learning query strategy or a specific region within the data distribution. Common arms include:

• Uncertainty Sampling: Selects points where the model is least confident.
• Diversity Sampling: Selects points to maximize coverage of the data space.
• Random Sampling: Serves as a baseline exploration arm. The bandit algorithm's job is to learn which of these strategies is most 'rewarding' for the current learning phase and data stream characteristics.

The core feedback mechanism is the reward signal. After querying a label using a selected arm (strategy) and updating the model, a reward is computed. Effective reward designs include:

• Immediate Accuracy Gain: The increase in model accuracy on a held-out validation set after incorporating the newly labeled point.
• Model Change Magnitude: The norm of the parameter update (gradient) induced by the new example.
• Estimated Error Reduction: A proxy for how much the new label is expected to reduce future generalization error. The reward must be computable quickly to support real-time, stream-based decision-making.

The bandit employs a policy to balance trying under-sampled arms (exploration) and selecting the historically best arm (exploitation). Key algorithms include:

• Upper Confidence Bound (UCB): Selects the arm with the highest estimated reward plus an exploration bonus that decays as the arm is pulled more often.
• Thompson Sampling: A Bayesian method that samples reward estimates from posterior distributions for each arm and selects the arm with the highest sample.
• Epsilon-Greedy: With probability ε, explores a random arm; otherwise, exploits the best-known arm. These algorithms dynamically adapt the allocation of the labeling budget across strategies.

In streaming environments, the optimal query strategy can change due to concept drift. Standard bandit algorithms assume stationary rewards, which is invalid here. Modified approaches include:

• Sliding-Window UCB: Only uses rewards from a recent window of time to estimate arm performance.
• Discounted UCB: Applies a temporal discount factor to older rewards, weighting recent evidence more heavily.
• Change-Point Detection: Monitors reward streams for each arm and resets estimates if a statistical change is detected. This ensures the bandit remains responsive to shifts in the data distribution.

A Contextual Bandit enhances the framework by allowing the decision to incorporate side information or context. In active learning, the context is the feature vector of the incoming data point.

• The algorithm learns a policy that maps the context (data point features) to the choice of which query strategy (arm) to use.
• This enables more granular decisions, such as using uncertainty sampling for points in sparse regions and diversity sampling for points in dense clusters.
• Linear models or neural networks can be used to approximate the reward function for each arm given the context.

The MAB is not a standalone component; it is integrated into the active learning feedback loop:

1. Observe: A new unlabeled data point arrives from the stream.
2. Select Arm: The bandit policy chooses a query strategy (arm) based on history and possibly the point's context.
3. Evaluate & Query: The chosen strategy evaluates the point (e.g., computes its uncertainty). If it meets the strategy's criteria, a label is requested from the oracle.
4. Update Model & Reward: The model is updated with the new labeled pair. A reward for the chosen arm is computed based on the utility of this update.
5. Update Bandit: The bandit algorithm updates its internal estimates for the pulled arm with the new reward, closing the loop.

A core application is dynamically selecting the best active learning query strategy from a set of candidates (the 'arms'). Instead of committing to a single strategy like Uncertainty Sampling or Query-By-Committee, the MAB algorithm treats each strategy as an arm. It explores strategies to evaluate their effectiveness and exploits the one that yields the most informative labels for the current data distribution. This is crucial when no single strategy dominates across all problem types or data drift phases.

MABs are inherently designed for non-stationary environments, making them ideal for stream-based active learning under concept drift. As the underlying data distribution changes, the utility of different data regions or query strategies shifts. A MAB algorithm (e.g., using a sliding window or discount factor) can detect when an arm's performance decays and re-allocate the query budget to explore new, potentially more relevant strategies or data subspaces, enabling drift-aware querying.

In real-world systems, the label acquisition cost is rarely uniform. Different data points or categories may require different oracles (e.g., a general annotator vs. a domain expert) with varying costs and latencies. A MAB can be formulated where each arm represents a data source or oracle type with an associated cost. The algorithm learns to balance the information gain of a query against its cost, optimizing for performance per unit cost rather than pure accuracy, a critical consideration in enterprise Human-in-the-Loop (HITL) systems.

The cold start problem in active learning—where initial uncertainty estimates are unreliable—can be mitigated using a MAB. Initially, the algorithm is forced into an exploration phase, sampling uniformly from different strategies or data regions to gather initial performance estimates. This structured exploration provides a robust foundation for later exploitation, preventing the model from getting stuck in a suboptimal querying loop due to poor initial assumptions. Techniques like epsilon-greedy or UCB (Upper Confidence Bound) provide tunable exploration guarantees.

When an active learning system must operate across multiple related tasks or data domains simultaneously, a hierarchical or contextual bandit approach can be effective. Each 'arm' might correspond to a specific task-domain pair. The algorithm learns to allocate the global labeling budget across these pairs, prioritizing queries for the tasks where labeling yields the highest marginal global improvement. This is applicable in federated learning scenarios or for models serving multiple client use cases from a shared oracle interface.

MABs can orchestrate the use of multiple weak supervision sources. Each weak labeler (e.g., a heuristic rule, a pre-trained model on related data) is an arm with an unknown reliability. The active learning system can use a bandit to decide which weak labeler to 'query' (apply) to a new unlabeled instance, or to decide between applying a cheap weak labeler and requesting an expensive human oracle. The bandit learns the accuracy-cost trade-off of each source in an online fashion, optimizing the overall label complexity.

The fundamental trade-off at the heart of any Multi-Armed Bandit problem. In active learning:

• Exploration involves querying labels for data points or using strategies to gather new information and reduce model uncertainty.
• Exploitation involves using the currently best-known strategy (or data region) to query labels that are most likely to improve immediate model performance. A bandit algorithm's policy, such as Upper Confidence Bound (UCB) or Thompson Sampling, mathematically balances this trade-off to minimize cumulative regret over time.

The operational paradigm for which MAB-based active learning is designed. It refers to systems where:

• Data arrives sequentially in a continuous stream.
• The model must make an immediate, irrevocable decision for each instance on whether to query its label.
• Model updates are incremental (online learning). This contrasts with pool-based active learning, where the algorithm can score and select from a static set. MAB frameworks are naturally suited for this sequential decision-making under uncertainty.

A mathematical criterion that scores the potential utility of labeling a given data point. In standard active learning, functions include maximum uncertainty or expected model change. In a MAB formulation:

• Each 'arm' can represent a different acquisition function or a region of the feature space.
• The bandit algorithm learns which acquisition function (arm) is most effective over time.
• The reward is the observed improvement in model performance from a queried label. This transforms the problem of choosing a function into a dynamic selection task.

A critical companion technology for MAB-based active learning in non-stationary streams. Concept drift refers to changes in the underlying data distribution over time.

• A pure MAB assumes stationary reward distributions for its arms.
• In real-world streams, the 'best' query strategy may change. Drift-aware MAB algorithms (e.g., sliding-window UCB, discounting Thompson Sampling) adapt by giving more weight to recent rewards.
• Active learning query budgets must be re-allocated to regions of the data space affected by drift.

A hard constraint defining the maximum number of labels that can be acquired. It is a primary driver for efficiency in active learning.

• In a MAB framework, the budget is the total number of pulls (rounds) across all arms.
• The bandit's goal is to maximize the total reward (cumulative model improvement) within this finite budget.
• Budget constraints make the exploration/exploitation trade-off more acute; excessive exploration wastes precious queries.

An advanced extension of the basic Multi-Armed Bandit highly relevant to active learning. A Contextual Bandit receives side information (context) with each round.

• In active learning, the context is the feature vector of the incoming data instance.
• The algorithm learns a policy mapping contexts (data points) to arms (query decisions: 'label' or 'ignore', or choice of strategy).
• This allows for personalized, instance-level decisions, moving beyond just selecting a global best strategy. It is the direct bridge between bandits and supervised learning.