Upper Confidence Bound (UCB)

UCB operates on the principle of optimism in the face of uncertainty. Instead of relying on random exploration like epsilon-greedy, it systematically selects the action with the highest upper confidence bound. This bound is calculated as the sum of the estimated mean reward and an exploration bonus. The bonus is large for actions with high uncertainty (few trials) and small for actions with low uncertainty (many trials). This deterministic approach ensures that every action is eventually explored, but the algorithm quickly narrows its focus to the most promising options as confidence grows.

The classic UCB1 algorithm selects the arm a that maximizes the following quantity at time step t:

UCB Score = X̄ₐ + √(2 ln(t) / Nₐ)

• X̄ₐ: The empirical mean reward of arm a so far.
• t: The total number of trials played across all arms.
• Nₐ: The number of times arm a has been selected.

The square-root term is the exploration bonus. The natural logarithm ln(t) ensures that the bonus grows slowly over time, while the denominator Nₐ shrinks the bonus for frequently chosen arms. This elegantly balances exploitation (high X̄ₐ) and exploration (high uncertainty bonus).

UCB1 provides a strong theoretical guarantee: its expected cumulative regret grows logarithmically with time, specifically O(log t). This is provably optimal for the stochastic multi-armed bandit problem.

• Regret is the difference between the reward obtained and the reward that would have been obtained by always choosing the optimal arm.
• Logarithmic regret means the algorithm learns the optimal policy very quickly; the rate of mistakes decreases exponentially.
• This guarantee holds under the assumption that reward distributions are sub-Gaussian and stationary. This mathematical rigor makes UCB a preferred choice over heuristic methods like epsilon-greedy for mission-critical cognitive radio tasks.

Unlike Thompson Sampling, which is a probabilistic algorithm, UCB is fully deterministic. Given the same history of actions and rewards, UCB will always select the same next action.

• Deterministic Behavior: Easier to debug, audit, and replicate in simulation environments like RF Digital Twin Environments.
• No Random Seed Dependence: Results are perfectly reproducible, which is critical for mission assurance and regulatory compliance.
• Comparison: Thompson Sampling samples from a posterior distribution, which can be more robust to delayed feedback, but UCB's deterministic calculation is often computationally lighter and simpler to implement on edge hardware like FPGAs.

In cognitive radio, UCB is directly applied to the channel selection problem. Each frequency channel is treated as an arm in the bandit model.

• Action: Selecting a channel for transmission.
• Reward: The achieved throughput or signal-to-noise ratio (SNR) on that channel.
• Exploration Bonus: Channels that haven't been sensed recently have a high uncertainty bonus, prompting the cognitive engine to sample them.
• Primary User Protection: The algorithm naturally avoids channels with consistently low rewards (e.g., due to high primary user activity) and quickly identifies vacant spectrum holes. This enables autonomous Dynamic Spectrum Access (DSA) without a central coordinator.

Standard UCB assumes stationary reward distributions, which is often violated in real wireless channels due to mobility and fading. To handle non-stationary environments, variants like the Sliding-Window UCB (SW-UCB) are used.

• SW-UCB: Only considers the last τ observations, effectively forgetting old data.
• Discounted UCB: Applies a discount factor γ to weight recent rewards more heavily.
• These adaptations allow the cognitive radio to track changes in primary user activity patterns or jamming attacks. Without them, a standard UCB would become "stuck" on an outdated channel estimate after an environmental change, failing the exploration-exploitation tradeoff.

The fundamental dilemma requiring an agent to balance gathering new information against maximizing immediate reward.

• Exploration Cost: Every time a cognitive radio scans a new frequency, it incurs sensing overhead and potential throughput loss.
• Exploitation Risk: Sticking to a known good channel risks sudden interference if a primary user returns.
• Regret Minimization: UCB and Thompson Sampling both aim to minimize cumulative regret—the difference between the optimal reward and actual reward over time.
• Dynamic Environments: In non-stationary RF environments, sliding-window UCB variants discount old observations to track changing channel quality.

A simplified reinforcement learning framework where an agent allocates discrete trials among K competing options to maximize cumulative reward, with no state transitions between decisions.

• Stochastic MAB: Assumes each arm has a fixed but unknown reward distribution—the classic setting for UCB analysis.
• Adversarial MAB: Models a hostile environment where rewards are chosen by an opponent, requiring the EXP3 algorithm instead of UCB.
• Cognitive Radio Mapping: Each frequency channel is an arm; pulling it yields a binary reward (available or occupied).
• Regret Bound: UCB achieves a theoretical regret bound of O(log T), proving it is asymptotically optimal for stochastic bandits.

An extension of the MAB framework where the agent observes side information (context) before each decision, enabling adaptive selection based on environmental features.

• Feature Vector: Before choosing a channel, the radio observes context like time of day, historical occupancy patterns, or signal-to-noise ratio.
• LinUCB Algorithm: A linear variant of UCB that models expected reward as a linear function of context features, adding an exploration bonus based on parameter uncertainty.
• Practical Advantage: Outperforms standard UCB when channel quality correlates with observable features, such as diurnal usage patterns in cellular bands.
• Implementation: Requires maintaining a design matrix and computing matrix inversions, making it more computationally intensive than vanilla UCB.

A model-free reinforcement learning algorithm that learns optimal policies in stateful environments, extending beyond the stateless MAB model used by UCB.

• State-Action Values: Learns a Q-table mapping (state, action) pairs to expected cumulative rewards, enabling decisions that account for future consequences.
• Markov Decision Process: Unlike UCB's single-state assumption, Q-learning handles environments where actions cause transitions between distinct states.
• Spectrum Handoff: When a primary user reclaims a channel, the cognitive radio transitions to a new state requiring a different action—a scenario beyond UCB's scope.
• Exploration Mechanism: Typically uses epsilon-greedy exploration rather than UCB's confidence-bound approach, though UCB exploration can be integrated into Q-learning.

The mathematical framework for evaluating bandit algorithms by measuring the cumulative loss compared to an omniscient optimal strategy.

• Definition: Regret(T) = T × μ* − Σᵗ rₜ, where μ* is the mean reward of the best arm and rₜ is the reward at time t.
• UCB Guarantee: Achieves logarithmic regret of O(K log T / Δ), where Δ is the gap between the best and second-best arm.
• Lower Bound: Lai and Robbins proved that no algorithm can achieve better than logarithmic regret asymptotically, making UCB theoretically optimal.
• Practical Metric: In spectrum access, regret directly translates to lost transmission opportunities compared to always selecting the best available channel.