Multi-Armed Bandit (MAB)

A foundational and intuitive strategy that chooses the best-known arm (exploit) with probability 1 - ε, and selects a random arm (explore) with probability ε. The parameter ε is typically a small constant (e.g., 0.1).

• Simple & Computationally Cheap: No complex calculations required.
• Guaranteed Exploration: Always maintains a baseline chance of trying new options.
• Limitation: Explores suboptimal arms uniformly, regardless of their potential, and does not adapt exploration over time.

A deterministic, principle-driven algorithm that selects the arm with the highest Upper Confidence Bound. This bound is the current estimated reward plus an exploration bonus that shrinks as the arm is pulled more.

• Optimism in the Face of Uncertainty: Formally quantifies uncertainty and acts optimistically.
• No Parameters: Unlike ε-Greedy, UCB has no tuning parameter like ε.
• Theoretical Guarantees: Provides strong, provable bounds on cumulative regret (the total reward lost compared to the optimal arm).
• Common Variants: UCB1 (for bounded rewards), UCB-Tuned (empirically better variance handling).

A Bayesian probability matching algorithm. It maintains a probability distribution (posterior) over the expected reward of each arm. On each round, it samples a reward estimate from each distribution and pulls the arm with the highest sampled value.

• Elegant Balance: Naturally balances exploration and exploitation; arms with high uncertainty have wider distributions and are more likely to be sampled high.
• Excellent Empirical Performance: Often outperforms UCB in practice, especially for non-stationary problems.
• Bayesian Foundation: Requires specifying a prior belief, which can incorporate domain knowledge.
• Computational Cost: Can be higher than UCB if maintaining and sampling from complex posteriors.

An advanced extension where each arm's reward depends on contextual information (features) available at each decision point. The goal is to learn a mapping from context to the best arm.

• Personalization: Enables decisions tailored to specific situations (e.g., user profile, time of day).
• Algorithms: Often use linear models (LinUCB, LinTS) or neural networks (Neural Bandits) to estimate rewards from context.
• Key Application: The foundation for recommendation systems and dynamic ad placement, where the 'context' is user data.

Models a scenario where an opponent can arbitrarily assign losses to arms after the player's choice, with no statistical assumptions about reward generation.

• Worst-Case Guarantees: Algorithms are designed to perform well even under intentionally adversarial conditions.
• Key Algorithm: Exp3 (Exponential-weight algorithm for Exploration and Exploitation) uses exponential weighting to hedge bets across arms.
• Use Case: Essential for modeling non-stochastic environments like repeated auctions, game playing, or security settings where rewards are not i.i.d.

A simple but effective modification to the standard ε-Greedy where the exploration rate ε decays over time according to a schedule (e.g., ε = 1/t).

• Adaptive Exploration: Explores heavily at the start to gather information, then gradually shifts focus to pure exploitation.
• Convergence: Guarantees convergence to the optimal arm in the limit, as exploration probability tends to zero.
• Practical Tuning: Requires choosing a decay schedule, which can be a hyperparameter. Less theoretically grounded than UCB or Thompson Sampling but often effective in practice.

In a multi-agent system, a controller agent uses a MAB algorithm to select which specialist agent (the 'arm') to delegate a task to. Each agent has an unknown or time-varying success probability or execution latency. The MAB continuously explores to test agent performance and exploits the best-known performers to maximize cumulative system reward (e.g., task completion rate). This is superior to static round-robin allocation in environments where agent capabilities are non-uniform or change over time.

• Key Mechanism: Treats each agent as an arm with a reward distribution.
• Example: A customer service orchestrator choosing between a sentiment analysis agent, a FAQ retrieval agent, and a human escalation agent for each incoming query.

MAB algorithms are used to perform continuous, online optimization of agent or model parameters during live system operation. Instead of costly offline grid searches, each parameter configuration is an 'arm.' The system explores new configurations while exploiting the currently best-known one based on real-time performance metrics (e.g., inference accuracy, latency). This allows the multi-agent system to adapt autonomously to drifting data patterns or changing operational conditions without manual intervention.

• Key Mechanism: Contextual Bandits (like LinUCB) can use features of the current task or data state to inform the parameter selection.
• Benefit: Reduces operational overhead and maintains peak performance in non-stationary environments.

MAB provides a statistically efficient framework for multi-armed testing of new agent behaviors, prompt templates, or reasoning strategies. Unlike traditional A/B tests that split traffic evenly for a fixed period, MAB algorithms dynamically allocate more traffic to the better-performing variant, minimizing opportunity cost during the experiment. In a multi-agent context, this can be used to test different coordination protocols or communication templates between agents, quickly converging on the optimal strategy.

• Key Algorithm: Thompson Sampling is particularly popular for this use case due to its natural balance of exploration and exploitation.
• Outcome: Faster identification of superior configurations while reducing user exposure to underperforming variants.

In edge AI or federated learning scenarios, a central orchestrator must decide which edge devices or nodes to assign computational tasks to, considering variable and unknown factors like current network latency, device battery level, and local compute load. Modeling each edge node as a bandit arm allows the orchestrator to learn which nodes are most reliable and efficient over time, optimizing for system-wide objectives like minimizing job completion time or maximizing energy efficiency.

• Constraint: Often incorporates contextual information (e.g., time of day, task size) via contextual bandits.
• Challenge: Must handle non-stationary arms as device conditions change.

In security-critical or competitive multi-agent environments, some agents may become compromised or act maliciously (Byzantine agents), or external conditions may change adversarially. Adversarial Bandit algorithms (e.g., EXP3) are designed for these scenarios where reward sequences can be arbitrarily modified by an opponent. These algorithms provide worst-case performance guarantees, ensuring the orchestrator's task allocation strategy remains effective even when some 'arms' (agents) deliberately provide misleading feedback or poor performance.

• Use Case: Allocating tasks in a decentralized network where some participants may have incentives to game the system.
• Guarantee: Provides a bounded regret even under adversarial conditions.

Within a multi-agent assistant, a recommendation agent can use MAB to personalize content, tool suggestions, or response styles for individual users. Each possible recommendation is an arm, and user engagement (click, positive feedback) is the reward. The system explores to learn user preferences and exploits to maximize satisfaction. This is crucial for adaptive UI/UX in agentic systems, where the optimal way to present information or interact may vary significantly between users or contexts.

• Scale: Handles large action spaces (many possible recommendations) efficiently.
• Integration: Often combined with collaborative filtering or content-based features in a contextual bandit setup.

This is the fundamental trade-off at the heart of the Multi-Armed Bandit problem and many reinforcement learning systems.

• Exploration involves gathering new information by trying unknown or suboptimal options (agents/tasks) to improve future decisions.
• Exploitation involves leveraging current knowledge to choose the option with the highest known immediate reward.

MAB algorithms like Upper Confidence Bound (UCB) and Thompson Sampling mathematically balance this trade-off to maximize cumulative gain over time, a critical consideration when allocating tasks to agents with uncertain or evolving capabilities.

Regret is the primary performance metric for evaluating Multi-Armed Bandit algorithms. It quantifies the opportunity cost of not choosing the optimal action (the best "arm") at every time step.

• Cumulative Regret: The total reward lost compared to a hypothetical oracle that always selects the best arm.
• Algorithm Goal: A "good" MAB algorithm exhibits sub-linear regret growth, meaning the average regret per step approaches zero over time as the algorithm learns.

Minimizing regret is directly analogous to maximizing the efficiency of a task allocation system by rapidly identifying and consistently using the most capable agents.

A significant extension of the classic MAB where decisions are informed by contextual information (or "side information") available at each round.

• Mechanism: Before choosing an arm, the algorithm observes a feature vector (context) describing the current situation (e.g., task properties, agent state, environmental conditions).
• Application: In agent orchestration, this allows the allocator to make personalized decisions. For example, "Agent A is best for data analysis tasks, but Agent B is superior for creative writing tasks."

Algorithms like LinUCB model the expected reward as a linear function of the context, enabling more intelligent and adaptive task-agent matching.

Both are experimental frameworks for decision-making, but they optimize for different objectives.

• A/B (Split) Testing: A fixed-horizon, offline evaluation method. Traffic is split evenly (e.g., 50/50) between variants A and B for a predetermined period to gather statistically significant data for a final, one-time decision (e.g., which webpage design converts better).
• Multi-Armed Bandit: An adaptive, online optimization method. It dynamically shifts traffic towards better-performing variants during the experiment to minimize regret and maximize cumulative reward (e.g., continuously optimizing ad click-through rates in real-time).

MAB is superior for scenarios requiring continuous optimization, while A/B testing is designed for rigorous, unbiased hypothesis testing.

A foundational and highly effective Bayesian algorithm for solving the Multi-Armed Bandit problem.

• Principle: It maintains a probability distribution (posterior) over the expected reward of each arm. On each round, it samples a potential reward value from each arm's distribution and selects the arm with the highest sampled value.
• Process: After observing the actual reward, it updates the posterior distribution for that arm using Bayes' theorem.

This elegant approach naturally balances exploration and exploitation: arms with uncertain, high-reward potential will have broad distributions and are more likely to be sampled. It is widely used in real-world recommendation systems and clinical trials.

A premier frequentist algorithm for the Multi-Armed Bandit problem, known for its strong theoretical guarantees on regret.

• Principle: It constructs an optimistic estimate of each arm's true reward. The estimate is the current average reward plus a confidence interval that shrinks as the arm is pulled more often.
• Rule: On each round, select the arm with the highest Upper Confidence Bound.

The formula UCB = SampleMean + sqrt(2 * log(TotalPulls) / ArmPulls) ensures that less-explored arms receive a higher bonus, forcing exploration. As an arm is pulled, its confidence interval tightens, and exploitation takes over if it remains superior. It provides a deterministic alternative to the probabilistic Thompson Sampling.