Multi-Armed Bandit (MAB)

A deterministic algorithm that selects channels based on an optimistic estimate of potential reward. UCB calculates an upper confidence bound for each channel's expected quality by adding an exploration bonus proportional to the uncertainty of the estimate.

• Mechanism: Selects the channel maximizing μ̂ᵢ + √(2 ln(t) / nᵢ), where μ̂ᵢ is the empirical mean reward and nᵢ is the number of times channel i has been selected.
• Key Property: Provides a logarithmic regret bound, meaning the cumulative performance loss grows slowly over time.
• Spectrum Application: Ideal for stationary primary user traffic patterns where channel statistics remain constant, such as TV white space access.

A Bayesian probabilistic algorithm that maintains a posterior distribution over each channel's reward probability and selects channels by sampling from these distributions. Channels with higher uncertainty are naturally explored through the sampling process.

• Mechanism: For each channel, sample a value from its Beta distribution (parameterized by success and failure counts) and select the channel with the highest sample.
• Key Property: Achieves state-of-the-art empirical performance and is provably asymptotically optimal for Bernoulli bandits.
• Spectrum Application: Excels in non-stationary environments where primary user activity patterns shift, as the posterior naturally adapts to changing statistics.

The simplest MAB strategy that selects the empirically best channel with probability 1-ε and explores a random channel with probability ε. Despite its simplicity, it remains widely deployed due to minimal computational overhead.

• Mechanism: With probability ε, uniformly randomly select any available channel; otherwise, select the channel with the highest historical average reward.
• Key Property: Constant per-step complexity of O(1), making it suitable for resource-constrained cognitive radio hardware.
• Spectrum Application: Effective when paired with an annealing schedule that decays ε over time, transitioning from exploration-dominated to exploitation-dominated behavior as the agent learns the spectrum environment.

An algorithm designed for the adversarial bandit setting where channel rewards may be deliberately degraded by a jammer or interferer. EXP3 maintains a probability distribution over channels and updates weights exponentially based on observed rewards.

• Mechanism: Assigns each channel a weight that is multiplied by exp(γ * estimated_reward) after each selection, then samples channels according to the normalized weight distribution.
• Key Property: Achieves a high-probability regret bound of O(√(TK log K)) against an adaptive adversary, where K is the number of channels and T is the time horizon.
• Spectrum Application: Critical for anti-jamming cognitive radio and contested electromagnetic environments where an intelligent adversary actively attempts to degrade secondary user performance.

Extends the standard MAB framework by incorporating side information or context features before each channel selection. LinUCB models the expected reward as a linear function of the observed context vector, enabling generalization across similar spectrum states.

• Mechanism: Maintains a ridge regression estimate of the coefficient vector θ and selects the channel maximizing xᵀθ̂ + α√(xᵀA⁻¹x), where x is the context and A is the covariance matrix.
• Key Property: Leverages feature-based generalization to make informed decisions about channels never previously selected, dramatically reducing cold-start exploration.
• Spectrum Application: Enables context-aware spectrum access where the agent conditions decisions on time of day, detected interference patterns, or geolocation data to predict channel quality before sensing.

Models each channel as an independently evolving Markov chain that changes state even when not selected, capturing the realistic behavior of primary user activity that continues regardless of secondary user observation. The Whittle index policy provides a computationally tractable heuristic.

• Mechanism: Computes a scalar index for each channel representing the marginal value of activating that channel in its current state, then selects channels with the highest indices.
• Key Property: Asymptotically optimal under an indexability condition and decouples the N-channel problem into N independent single-channel problems.
• Spectrum Application: The most realistic MAB variant for dynamic spectrum access because it correctly models primary user ON/OFF activity evolving as a continuous-time process independent of secondary user sensing actions.

The central dilemma that MAB algorithms are designed to solve. The agent must balance exploration—trying under-sampled frequency channels to gather occupancy statistics—against exploitation—transmitting on the channel currently known to have the highest signal-to-noise ratio. Pure exploitation risks getting stuck on a suboptimal channel that experiences periodic interference, while pure exploration forfeits immediate throughput. Advanced strategies like Upper Confidence Bound (UCB) and Thompson Sampling provide mathematically principled mechanisms to navigate this trade-off, guaranteeing that cumulative regret grows only logarithmically with time rather than linearly.

The formal mathematical framework that generalizes the Multi-Armed Bandit to sequential state transitions. While a classic MAB assumes independent and identically distributed rewards for each arm, an MDP models environments where the agent's action changes the underlying state. In spectrum access, this captures the reality that occupying a channel may trigger a primary user's protection mechanism, altering future availability. An MDP is defined by the tuple (S, A, P, R): a set of states, a set of actions, state transition probabilities, and a reward function. MABs are a special case of MDPs with a single state.

An extension of the MDP framework that explicitly models the uncertainty inherent in spectrum sensing. In a POMDP, the cognitive radio cannot directly observe whether a channel is truly occupied; it only receives noisy sensor readings. The agent must maintain a belief state—a probability distribution over possible true states—and update it using Bayesian inference after each observation. This makes POMDPs computationally intensive to solve exactly, but they provide the most accurate model for real-world dynamic spectrum access where sensing errors and hidden node problems are unavoidable.

A model-free reinforcement learning algorithm that learns the optimal action-value function without requiring a model of the environment's transition dynamics. The agent maintains a Q-table mapping state-action pairs to expected cumulative rewards and iteratively updates these values using the Bellman equation: Q(s,a) ← Q(s,a) + α[r + γ max Q(s',a') - Q(s,a)]. For channel selection, each frequency band represents an action, and the Q-value estimates the long-term throughput achievable by selecting it. Deep Q-Networks (DQN) extend this to high-dimensional state spaces by approximating the Q-function with a neural network.

The primary theoretical performance metric for evaluating MAB algorithms. Regret quantifies the cumulative difference between the reward the agent actually received and the reward it would have received by always selecting the optimal arm with perfect knowledge. Formally, after T rounds: R(T) = T·μ* - Σ μ_{a_t}, where μ* is the mean reward of the best arm. Algorithms like UCB1 achieve a theoretical regret bound of O(log T), proving that the per-round regret asymptotically approaches zero. In spectrum access, minimizing regret translates directly to maximizing secondary user throughput.

An extension of the MAB framework where the agent observes side information—or context—before making each arm selection. In spectrum access, context might include time of day, historical occupancy patterns, or geographic location. The agent learns a policy that maps context vectors to optimal actions, enabling it to generalize across similar situations. Linear UCB and neural contextual bandits are common algorithms. This framework is particularly powerful for spectrum occupancy prediction, where temporal and environmental features strongly correlate with channel availability.