Multi-Armed Bandit Spectrum Access

The fundamental dilemma at the heart of MAB spectrum access. A secondary user must decide between exploiting a channel known to have high availability to maximize immediate throughput, or exploring other channels to discover potentially better opportunities.

• Exploitation: Tuning to the empirically best channel to guarantee short-term reward.
• Exploration: Sampling channels with uncertain statistics to improve long-term decision-making.
• Regret is the metric used to quantify the performance loss compared to an omniscient oracle that always selects the optimal channel.

A deterministic policy that selects channels based on an optimism in the face of uncertainty principle. The algorithm calculates an upper confidence bound for each channel's expected reward and selects the channel with the highest bound.

• The bound is computed as the empirical mean reward plus an exploration bonus that grows with the uncertainty of the estimate.
• Channels that have been sampled infrequently receive a larger bonus, forcing exploration.
• UCB achieves a logarithmic regret bound, meaning the rate of suboptimal selections decreases rapidly over time.

A Bayesian probabilistic approach that maintains a posterior distribution over each channel's availability parameter. At each decision step, the algorithm samples a value from each channel's posterior and selects the channel with the highest sample.

• Naturally balances exploration and exploitation through probability matching.
• Channels with high uncertainty have wider posteriors, increasing the chance they will be sampled and selected.
• Empirically outperforms UCB in many practical scenarios and is robust to non-stationary spectrum environments where channel statistics drift over time.

An extension of the classical MAB framework where the secondary user observes side information or context before making a channel selection decision. This context may include time of day, geographic location, or recent spectrum sensing measurements.

• The algorithm learns a mapping from context to expected channel reward using a function approximator such as a linear model or neural network.
• Enables generalization across similar contexts, dramatically accelerating learning in complex environments.
• Critical for practical deployments where spectrum availability patterns are correlated with observable environmental features.

A robust formulation that abandons the assumption of stochastic channel availability. Instead, the environment is modeled as an adversary that can arbitrarily choose channel rewards at each time step, subject only to computational or information constraints.

• The secondary user's performance is measured by external regret, comparing cumulative reward against the best fixed channel in hindsight.
• Algorithms like EXP3 (Exponential-weight algorithm for Exploration and Exploitation) maintain a probability distribution over channels and update weights based on observed losses.
• Provides worst-case guarantees essential for contested or jammed electromagnetic environments where statistical assumptions break down.

Extends the single-user MAB formulation to scenarios where multiple secondary users simultaneously select channels, introducing the challenge of collision avoidance. When two users select the same channel, both may experience degraded performance or complete transmission failure.

• Requires distributed coordination mechanisms such as orthogonalization protocols or collision feedback signals.
• Algorithms must balance individual exploration with global efficiency, often modeled as a multiplayer MAB game.
• Musical chairs algorithms provide theoretical guarantees that all users eventually settle on orthogonal, collision-free channel assignments without centralized control.

The fundamental dilemma at the heart of the Multi-Armed Bandit problem. The agent must decide between exploiting a known high-quality channel for immediate reward and exploring other channels to discover potentially better options.

• Exploitation: Selecting the channel with the highest historical data rate.
• Exploration: Sampling a rarely-used frequency to update its availability statistics.
• Regret Minimization: The mathematical goal is to minimize the cumulative difference between the optimal strategy and the agent's actual choices.

A deterministic action selection strategy that balances exploration and exploitation by choosing the channel with the highest upper confidence bound on its estimated reward. It applies the principle of optimism in the face of uncertainty.

• Mechanism: Adds an exploration bonus to channels that have been sampled less frequently.
• Advantage: Provides a provable logarithmic bound on cumulative regret.
• Application: Ideal for stationary environments where channel statistics remain constant over time.

A probabilistic Bayesian approach where the agent maintains a posterior distribution over each channel's true reward probability. It selects a channel by sampling a random value from each distribution and choosing the highest.

• Mechanism: Naturally balances exploration via the variance of the posterior.
• Advantage: Often outperforms UCB in practice due to efficient randomization.
• Contextual Bandits: Extends to cases where channel selection depends on external features like time of day or sensor readings.

An extension where the agent observes side information (context) before making a decision. In spectrum access, context includes Signal-to-Noise Ratio (SNR) history, time of day, or geolocation.

• Linear Bandits: Assumes expected reward is a linear function of the context vector.
• Neural Bandits: Uses deep neural networks to model complex, non-linear relationships between context and channel quality.
• Use Case: Adapting channel selection based on real-time interference patterns.

A non-stochastic formulation where channel rewards are not drawn from a fixed distribution but are chosen by an adversary. This models worst-case scenarios like primary user emulation attacks or intelligent jamming.

• Exp3 Algorithm: Exponential-weight algorithm for exploration and exploitation provides a robust strategy against adversarial sequences.
• No Statistical Assumptions: Does not require the environment to be stationary.
• Defense Application: Maintaining connectivity in contested electromagnetic environments.

A critical variant where the state of every channel evolves even when it is not selected. This accurately models primary user traffic where occupancy changes independently of sensing actions.

• Whittle Index Policy: A heuristic that decouples the problem into manageable sub-problems by calculating an index for each channel.
• Markovian Dynamics: Channels transition between idle and busy states according to a Markov chain.
• Real-World Fit: Essential for modeling bursty wireless traffic patterns.