Multi-Armed Bandit (MAB)

The fundamental tension at the heart of every MAB algorithm. The cognitive radio must continuously decide between:

• Exploitation: Selecting the frequency channel with the highest known reward (e.g., throughput, SNR) to maximize immediate performance.
• Exploration: Selecting a less-tested or unknown channel to gather information about its quality, potentially discovering a superior option for future use. A pure exploitation strategy risks getting stuck on a suboptimal channel, while pure exploration sacrifices current throughput. MAB algorithms provide a principled balance.

The primary mathematical objective of a MAB algorithm is to minimize regret, which is formally defined as the difference between the cumulative reward obtained by an omniscient oracle that always selects the truly optimal arm and the cumulative reward actually achieved by the algorithm.

• Zero-regret algorithms guarantee that the average regret per time step tends to zero as time goes to infinity.
• In cognitive radio, regret translates directly to lost throughput or increased latency compared to a hypothetical perfect channel selection strategy.

A family of deterministic algorithms that selects arms based on an optimistic estimate of their potential reward. The UCB score for each channel is calculated as:

• Empirical mean reward + Exploration bonus The exploration bonus is proportional to the uncertainty in the channel's estimate, which decreases as the channel is sampled more frequently. UCB naturally shifts from exploration to exploitation as confidence grows. The UCB1 variant achieves logarithmic regret, making it provably efficient for stationary environments.

A Bayesian probabilistic approach that maintains a posterior distribution over the true reward probability of each channel. At each decision step, the algorithm:

• Samples a random value from each channel's posterior distribution.
• Selects the channel with the highest sampled value. This naturally balances exploration and exploitation: channels with high uncertainty have wider distributions and are more likely to produce a high sample. Thompson Sampling often outperforms UCB in practice and gracefully handles non-stationary environments common in dynamic spectrum access.

An extension of the basic MAB where the agent observes side information (context) before making a decision. In cognitive radio, context includes:

• Current spectrum occupancy readings
• Time of day or day of week
• Geographic location
• Historical interference patterns The algorithm learns a policy that maps context vectors to optimal channel selections, enabling it to generalize across similar states. This is critical for real-world cognitive radio where the best channel depends heavily on the current RF environment.

A robust variant designed for scenarios where channel rewards may be manipulated by an intelligent adversary, such as a jammer. Unlike stochastic bandits that assume fixed reward distributions, adversarial bandits make no statistical assumptions and instead compete against the best fixed action in hindsight.

• The EXP3 (Exponential-weight algorithm for Exploration and Exploitation) algorithm provides strong theoretical guarantees even when an attacker actively tries to degrade performance.
• Essential for electronic warfare and secure communications applications.

The simplest MAB algorithm for channel selection. The cognitive radio exploits the best-known channel with probability (1-ε) and explores a random channel with probability ε.

• Implementation: Select a random channel ε fraction of the time; otherwise, select the channel with the highest estimated reward
• Tuning parameter: ε is typically decayed over time (e.g., ε = 1/t) to shift from exploration to exploitation
• Limitation: Explores uniformly across all channels, including those known to be poor, wasting sensing time
• Use case: Baseline comparison for more sophisticated algorithms; effective in stationary environments with few channels

A deterministic algorithm that selects channels based on an optimism in the face of uncertainty principle. Each channel's selection score combines its estimated mean reward with an exploration bonus proportional to its uncertainty.

• Selection rule: Select channel maximizing μ̂ᵢ + √(2 ln(t) / nᵢ), where nᵢ is the number of times channel i has been sampled
• Advantage: Provides a theoretical guarantee on regret growing only logarithmically with time — O(log t)
• Spectrum application: Excels when channel quality is stationary; the confidence bound naturally shrinks as more samples are collected
• Variants: UCB1 (non-parametric), UCB-Tuned (variance-aware), and Sliding-Window UCB for non-stationary spectrum environments

A Bayesian probabilistic approach that maintains a posterior distribution over each channel's reward probability. Channels are selected by sampling from these distributions, naturally balancing exploration and exploitation.

• Mechanism: Model each channel's success probability with a Beta(α, β) distribution; sample θᵢ ~ Beta(αᵢ, βᵢ) for each channel and select the one with the highest sample
• Update rule: After observing a successful transmission, increment α; after a collision or failure, increment β
• Empirical performance: Often outperforms UCB in practice despite similar theoretical guarantees
• Spectrum advantage: Handles non-stationary environments well when combined with discount factors or sliding windows; naturally quantifies uncertainty for risk-aware channel selection

Designed for non-stochastic or adversarial environments where channel quality may be manipulated by a jammer. The Exponential-weight algorithm for Exploration and Exploitation (EXP3) makes no assumptions about reward distributions.

• Core idea: Maintain a probability distribution over channels and update weights exponentially based on observed rewards
• Jamming resistance: An intelligent jammer cannot exploit predictable patterns because EXP3 randomizes channel selection according to learned weights
• Regret bound: Achieves O(√T) regret against the best fixed channel in hindsight, even under adversarial conditions
• Spectrum context: Critical for contested electromagnetic environments where primary user emulation attacks or reactive jamming attempt to degrade cognitive radio performance

Extends the standard MAB framework by incorporating side information (context) about the environment before making a channel selection decision. The optimal channel may depend on observable features.

• Context features: Signal-to-noise ratio, time of day, geographic location, detected interference patterns, or spectrum occupancy history
• Algorithm: Use a linear model (LinUCB) or neural network to predict expected reward given context; select channel with highest predicted reward plus exploration bonus
• Spectrum application: Select different channels during business hours vs. nighttime based on learned primary user activity patterns
• Advantage over standard MAB: Generalizes across similar contexts rather than treating each situation independently, dramatically accelerating learning in complex spectrum environments

Addresses the distributed coordination problem where multiple cognitive radios independently select channels without explicit communication. Collisions occur when two or more radios transmit on the same channel simultaneously.

• Challenge: Radios must learn both channel quality and avoid collisions without a central coordinator
• Approaches: Orthogonalization algorithms (e.g., RhoRand, MEGA) where radios learn to occupy distinct channels through collision feedback
• Feedback model: Radios observe only their own transmission success/failure, not which other channels are occupied
• Regret decomposition: Combines channel selection regret with collision regret; theoretical guarantees require algorithms that converge to an orthogonal channel allocation
• Real-world parallel: Models uncoordinated Wi-Fi access points or LTE-U/LAA nodes competing for unlicensed spectrum

The fundamental dilemma at the heart of every MAB algorithm. The cognitive radio must balance exploration (sensing new, potentially superior frequency channels) against exploitation (transmitting on the current best-known channel).

• Exploration incurs an opportunity cost but discovers better long-term options.
• Exploitation maximizes immediate throughput but risks stagnation in a suboptimal channel.
• The goal is to minimize cumulative regret—the total throughput lost compared to an omniscient oracle that always selects the optimal channel.

The mathematical scaffolding used to formalize the channel selection problem. An MDP defines the environment as a tuple of states (channel occupancy), actions (selecting a frequency), transition probabilities (channel dynamics), and a reward function (successful throughput).

• Provides the theoretical guarantee that an optimal policy exists.
• Enables the use of dynamic programming solutions when the model is fully known.
• In model-free MAB contexts, the transition probabilities are unknown and must be learned online.

A model-free reinforcement learning algorithm that learns the value of taking a specific action in a given state without requiring a model of the RF environment. The cognitive radio maintains a Q-table mapping state-action pairs to expected cumulative rewards.

• Updates Q-values using the Bellman equation: Q(s,a) ← Q(s,a) + α[r + γ max Q(s',a') - Q(s,a)].
• The learning rate (α) controls how quickly new observations override old estimates.
• The discount factor (γ) balances immediate versus future rewards, critical for non-stationary spectrum environments.

A deterministic exploration strategy that selects channels based on an optimistic estimate of their potential reward. UCB calculates an upper confidence bound for each arm's mean reward and selects the arm with the highest bound.

• Formula: UCB_i = μ̂_i + √(2 ln(t) / n_i), where μ̂_i is the estimated mean, t is the total trials, and n_i is the number of times arm i was selected.
• The second term represents uncertainty, which shrinks as an arm is pulled more often.
• Naturally balances exploration and exploitation without requiring explicit randomization.

A Bayesian probabilistic approach to the exploration-exploitation dilemma. Instead of point estimates, Thompson Sampling maintains a probability distribution over each channel's true reward rate and selects arms by sampling from these posterior distributions.

• Typically uses a Beta-Bernoulli conjugate pair for binary success/failure rewards.
• Channels with higher uncertainty have wider distributions, increasing their chance of being sampled and explored.
• Empirically outperforms UCB in many non-stationary wireless environments due to its natural randomization.

An extension of the standard MAB where the agent observes side information (context) before making a decision. In cognitive radio, context includes SNR measurements, time of day, or geolocation data that correlate with channel quality.

• Models the expected reward as a function of context: E[r|a,x] = f(x,θ_a).
• Enables generalization across similar contexts, dramatically accelerating learning.
• Implemented using linear models or neural networks that map observed RF features to channel selection policies.