Multi-Armed Bandit Spectrum Selection

The foundational MAB algorithm that selects the empirically best channel with probability 1-ε and a random channel with probability ε.

• Mechanism: Maintains a running average reward for each frequency channel. The ε parameter (typically 0.1) controls the exploration rate.
• Key Weakness: Explores uniformly at random, wasting time on known-poor channels even after sufficient learning. Does not adapt exploration based on uncertainty.
• Practical Use: Serves as a baseline benchmark in dynamic spectrum access simulations due to its simplicity and minimal computational overhead on resource-constrained cognitive radios.

A deterministic algorithm that selects channels based on an optimistic estimate of potential reward, explicitly accounting for estimation uncertainty.

• Mechanism: Chooses the channel maximizing μ̂ᵢ + √(2 ln(t) / nᵢ), where μ̂ᵢ is the mean reward and nᵢ is the selection count. The second term is an exploration bonus that shrinks as a channel is sampled more.
• Advantage: Systematically reduces exploration as confidence grows, unlike epsilon-greedy. Provides theoretical guarantees on regret bounded by O(log t).
• Spectrum Application: Effective for incumbent protection scenarios where confidently identifying a clear primary user channel is critical before secondary transmission.

A Bayesian probabilistic algorithm that maintains a posterior distribution over each channel's reward probability and samples from these distributions to make decisions.

• Mechanism: Models channel quality using a Beta(α, β) distribution for binary rewards (success/failure). Each round, it samples a random value from each channel's posterior and selects the highest. After observing the outcome, it updates the distribution parameters.
• Empirical Performance: Consistently outperforms UCB in many real-world tasks, including spectrum occupancy prediction with non-stationary traffic patterns, due to its randomized exploration that avoids systematic biases.
• Key Benefit: Naturally handles prior knowledge—a radio can initialize distributions based on a Radio Environment Map (REM) database before sensing begins.

Extends the MAB framework by incorporating side information (context) about the environment before making a channel selection decision.

• Mechanism: A model (e.g., linear regression or a neural network) maps a context vector xₜ—including time of day, device location, or recent spectrum sensing results—to expected rewards for each channel.
• Linear UCB: A popular variant that assumes a linear relationship between context and reward, computing an upper confidence bound on the predicted reward for each arm.
• Application: Enables a cognitive radio to learn that a specific frequency is only good during off-peak hours or at a particular geographic location, personalizing the dynamic spectrum access policy to the current operating environment.

Designed for non-stochastic environments where channel quality can be manipulated by an adversary or exhibit arbitrary, unpredictable fluctuations.

• Mechanism: The Exponential-weight algorithm for Exploration and Exploitation (EXP3) maintains a probability distribution over channels, weighting each by the exponential of its cumulative estimated reward. It selects channels probabilistically and updates weights based on an importance-weighted reward estimate.
• Robustness: Provides strong theoretical guarantees even against a Primary User Emulation Attack (PUEA) where a jammer adaptively targets the secondary user's chosen channel.
• Trade-off: Achieves a regret bound of O(√T) compared to the best fixed channel in hindsight, which is optimal for adversarial settings but converges slower than UCB in stochastic environments.

Extends the single-agent MAB to a distributed setting where multiple secondary users must select channels without central coordination and without colliding with each other.

• Challenge: Collisions occur when two radios select the same channel simultaneously, resulting in zero reward for both. Radios must learn an orthogonal channel allocation without explicit communication.
• Algorithms: Approaches like the Musical Chairs protocol or ρ-Rand use randomized backoff and statistical learning to converge to a collision-free orthogonal allocation.
• Application: Directly models cooperative spectrum sensing networks where multiple cognitive radios share the same spectrum pool and must self-organize to maximize aggregate throughput while protecting primary users.

The fundamental dilemma at the heart of the multi-armed bandit problem. The agent must balance exploration—sensing and testing new frequency channels to build an accurate interference map—against exploitation—transmitting on the known best channel to maximize immediate throughput. Algorithms like Upper Confidence Bound (UCB) and Thompson Sampling provide mathematically optimal strategies for this trade-off, ensuring the system does not get stuck on a suboptimal channel while still capitalizing on its learned knowledge.

An advanced variant where the bandit algorithm incorporates side information (context) before making a channel selection. The context vector might include:

• Current Channel State Information (CSI)
• Time of day and historical occupancy patterns
• Device mobility vector and location
• Active application QoS requirements This allows the policy to learn that a channel which is poor during business hours may be excellent at night, enabling truly adaptive, state-aware spectrum access.

The formal mathematical objective of a bandit algorithm. Regret is defined as the cumulative difference between the reward obtained by the algorithm and the reward that would have been obtained by an omniscient oracle always selecting the optimal channel. Minimizing regret ensures the learning algorithm converges to the optimal policy as quickly as possible. In spectrum access, high regret translates directly to lost throughput and increased latency for secondary users.

A robust formulation where channel rewards are not drawn from a fixed, stochastic distribution but are chosen by an adversary—such as a jammer or a malicious primary user emulator. Algorithms like EXP3 (Exponential-weight algorithm for Exploration and Exploitation) provide theoretical guarantees even in this hostile environment, making them critical for defense and secure communications applications where spectrum denial is a threat vector.

Extends the single-agent problem to a decentralized multi-agent setting where multiple secondary users independently select channels. Without explicit communication, agents must learn to avoid collisions—where two users select the same channel and cause mutual interference. Techniques like collision avoidance through orthogonalization and Gaussian process bandits allow a fleet of cognitive radios to converge to an efficient, collision-free channel allocation.