Multi-Armed Bandit (MAB)

Unlike full Markov Decision Processes (MDPs), MAB algorithms do not require modeling environmental state transitions. The agent treats each frequency channel as an independent arm, learning its quality solely through direct reward feedback. This eliminates the need for complex Radio Environment Map (REM) integration or propagation modeling, making MAB ideal for rapid deployment in unknown or highly dynamic spectral environments where building an accurate world model is computationally prohibitive.

The core dilemma in spectrum access: should the radio transmit on a known high-quality channel (exploit) or sample an unused channel that might offer better throughput (explore)? MAB algorithms formalize this mathematically:

• Epsilon-Greedy: Explores randomly with probability ε, exploits the best-known channel otherwise.
• Upper Confidence Bound (UCB): Selects channels based on an optimistic estimate, adding an uncertainty bonus for rarely sampled arms.
• Thompson Sampling: Maintains a posterior probability distribution over each channel's quality, sampling from these distributions to make selections. This structured approach prevents the radio from getting stuck on a suboptimal channel while minimizing wasted time on poor choices.

Standard MAB assumes stationary channel rewards, but real spectrum conditions vary with time, location, and interference. Contextual Bandits extend the framework by incorporating side information (context) before each decision:

• Context features: Time of day, detected energy levels, geolocation, or historical occupancy patterns.
• Decision function: A learned mapping from context to expected reward per channel, often implemented with a linear model or lightweight neural network. This enables the cognitive radio to adapt its channel selection strategy based on observable environmental conditions without requiring a full state-transition model, bridging the gap between simple bandits and full reinforcement learning.

When multiple secondary users independently run MAB algorithms, they may simultaneously select the same channel, causing collisions and degraded throughput. Multi-player MAB variants address this:

• Orthogonalization: Agents learn to occupy distinct channels through collision feedback as a negative reward signal.
• Distributed coordination: Each agent maintains estimates of other users' policies without explicit communication, converging to an orthogonal channel allocation.
• Time-division: Users learn access schedules that interleave transmissions on shared channels. This enables decentralized spectrum sharing without requiring a Common Control Channel (CCC) or centralized Fusion Center, preserving the lightweight nature of the MAB framework.

MAB algorithms provide inherent resilience against reactive jamming attacks. When a malicious actor jams a specific frequency, the channel's observed reward (throughput) drops sharply. The MAB agent naturally shifts its selection probability away from the jammed arm toward alternative channels:

• Rapid adaptation: Thompson Sampling and UCB quickly deprioritize jammed channels without requiring explicit jammer detection.
• Proactive evasion: By continuously exploring alternative arms, the agent maintains up-to-date quality estimates for backup channels, enabling seamless Spectrum Handoff when the primary channel is attacked.
• Adversarial bandit variants: Specialized algorithms like EXP3 provide theoretical regret bounds even against adaptive jammers that observe and react to the radio's channel selections.

MAB algorithms impose minimal computational and memory overhead compared to deep reinforcement learning approaches like Deep Q-Networks (DQN) or Proximal Policy Optimization (PPO). Key characteristics:

• O(K) memory: Only requires storing a running average reward and selection count per channel (K arms).
• O(1) decision time: Channel selection involves simple arithmetic comparisons, not neural network forward passes.
• No GPU requirement: Runs efficiently on embedded processors and FPGAs within software-defined radios. This makes MAB the preferred decision engine for resource-constrained cognitive radio nodes where milliwatt power budgets and microsecond decision latencies preclude deploying full deep learning inference pipelines.

The fundamental dilemma in online decision-making where an agent must balance exploring new channels to discover potentially higher rewards against exploiting known channels that currently yield high throughput. In cognitive radio, excessive exploration causes throughput loss, while pure exploitation risks missing a newly vacated, higher-quality channel. MAB algorithms provide a mathematical framework to optimize this balance.

A probabilistic MAB algorithm that maintains a posterior distribution over the reward probability of each channel. At each time step, it samples a value from each distribution and selects the channel with the highest sample. This naturally balances exploration and exploitation: channels with high uncertainty have wider distributions and are more likely to produce a high sample, encouraging exploration. Proven to be highly effective for dynamic spectrum access with non-stationary rewards.

A deterministic MAB algorithm that selects channels based on an optimistic estimate of expected reward. The UCB score combines the empirical mean reward with an exploration bonus that grows with the time since a channel was last selected. This ensures that neglected channels are eventually revisited. The UCB1 variant provides theoretical guarantees on regret—the difference between the optimal and achieved cumulative reward.

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

• Current time of day
• Historical spectrum occupancy patterns
• Geolocation data
• Recent sensing measurements This allows the policy to condition channel selection on environmental features, enabling more intelligent adaptation than a context-free MAB.

The primary mathematical objective in MAB problems. Regret is defined as the cumulative difference between the reward obtained by always selecting the optimal channel and the reward actually achieved by the algorithm. Minimizing regret ensures the agent learns the best channel quickly. In spectrum access, regret directly translates to lost transmission opportunities or increased interference events.

A model-free reinforcement learning algorithm that learns optimal action-value functions without requiring a model of the environment. While MAB handles single-step decisions, Q-Learning extends to sequential decision-making under the Markov Decision Process (MDP) framework. In cognitive radio, Q-Learning can optimize channel selection when state transitions—such as primary user arrival patterns—must be considered over multiple time steps.