Thompson Sampling

Thompson Sampling selects an action with a probability proportional to that action being optimal given observed data. Unlike deterministic methods, it maintains a full probability distribution over each action's expected reward rather than a point estimate. For each decision, the algorithm draws a random sample from each action's posterior distribution and selects the action with the highest sampled value. This probability matching principle ensures that actions with high uncertainty but promising potential are explored naturally, while well-understood high-reward actions are exploited frequently. The approach is inherently self-correcting: as more data accumulates, the posterior distributions narrow, automatically shifting behavior from exploration toward exploitation without requiring an explicit schedule or hyperparameter tuning.

The algorithm operates within a Bayesian inference framework, updating beliefs about each action's reward distribution as new observations arrive. For binary reward scenarios common in channel access, the Beta-Bernoulli conjugate pair is standard: a Beta(α, β) prior represents uncertainty about success probability, and each observed success increments α while failures increment β. This conjugacy enables closed-form posterior updates without computationally expensive Markov Chain Monte Carlo methods.

• Beta(1,1) prior: Uniform distribution representing complete uncertainty
• Beta(α, β) posterior: Updated after α-1 successes and β-1 failures
• Gaussian-Gaussian conjugate pair: Used for continuous reward models with known variance

The mathematical elegance of conjugate priors makes Thompson Sampling computationally lightweight, suitable for real-time cognitive radio decisions where latency constraints preclude heavy inference.

Thompson Sampling achieves logarithmic expected regret in the stochastic multi-armed bandit setting, matching the theoretical lower bound established by Lai and Robbins. Regret measures the cumulative difference between the reward obtained and the reward that would have been achieved by always selecting the truly optimal action. Key theoretical properties include:

• Asymptotic optimality: The per-period regret approaches zero as time horizon increases
• Finite-time bounds: Provable regret bounds exist for finite decision sequences
• Empirical superiority: Outperforms UCB and ε-greedy in many practical scenarios, particularly with delayed feedback common in wireless environments

For cognitive radio applications, this translates to minimal lost transmission opportunities while learning which frequency channels are genuinely available, critical for maintaining throughput in dynamic spectrum access systems.

Unlike ε-greedy strategies that explore uniformly at random or UCB algorithms that add deterministic exploration bonuses, Thompson Sampling achieves balance through uncertainty-driven stochasticity. Actions with wide posterior distributions are sampled across a broad range of values, sometimes exceeding the mean estimates of apparently superior actions. This mechanism provides several advantages:

• Directed exploration: The algorithm preferentially explores actions that might plausibly be optimal rather than wasting trials on clearly inferior options
• Graceful degradation: Performance degrades smoothly rather than catastrophically when environment dynamics change
• No hyperparameter tuning: Eliminates the need to manually set exploration rates or confidence bounds, reducing engineering overhead

This property makes Thompson Sampling particularly suitable for non-stationary wireless environments where channel availability statistics shift over time due to changing primary user activity patterns.

Contextual Thompson Sampling extends the algorithm to incorporate side information or environmental features before making decisions. In cognitive radio, this enables the agent to condition channel selection on observable context such as time of day, geographic location, or recent spectrum sensing measurements. The implementation typically uses:

• Bayesian logistic regression: Models reward probability as a function of context features with a Gaussian prior over weights
• Bayesian neural networks: For non-linear relationships between context and expected reward
• Online Laplace approximation: Maintains tractable posterior updates in high-dimensional feature spaces

This contextual awareness allows the cognitive engine to learn feature-dependent policies, such as preferring certain frequency bands during business hours when primary user activity patterns differ from nighttime operation, significantly improving spectrum utilization efficiency.

Thompson Sampling maps naturally onto the channel selection problem in cognitive radio networks, where each frequency channel represents an arm of the bandit and successful transmission constitutes a reward. Practical implementations address several domain-specific challenges:

• Primary user protection: The algorithm can incorporate constraints ensuring that channels with high primary user occupancy probability are sampled less frequently
• Sensing overhead: Decisions balance the cost of spectrum sensing against potential transmission rewards
• Multi-user coordination: Distributed Thompson Sampling variants allow multiple secondary users to share spectrum without explicit coordination, using collision avoidance mechanisms
• Jamming resistance: The probabilistic action selection makes transmission patterns unpredictable to adversarial jammers, providing inherent anti-jamming robustness

Real-world deployments have demonstrated 15-30% throughput improvements over static channel allocation in congested spectrum environments.

Thompson Sampling maintains a Beta distribution over each channel's probability of being idle, updating the posterior after every sensing observation. When a secondary user needs to transmit, it samples a success probability from each channel's posterior and selects the channel with the highest sample. This natural probabilistic approach ensures channels with higher uncertainty are explored proportionally to their chance of being optimal, while well-characterized high-quality channels are exploited frequently. The algorithm automatically anneals exploration as more observations accumulate, concentrating probability mass around the true channel availability rate without requiring manually tuned exploration parameters.

In cognitive radio channel selection, the reward is typically binary—channel idle (1) or occupied (0)—making the Beta-Bernoulli conjugate pair computationally ideal. The Beta distribution serves as the prior over channel availability, and after each sensing period, the posterior updates trivially:

• Success count α: Incremented when channel sensed idle
• Failure count β: Incremented when channel sensed busy

This closed-form update requires no gradient descent, no matrix inversion, and minimal memory, making Thompson Sampling deployable on resource-constrained software-defined radio (SDR) platforms. The computational cost per decision is a single random sample from each channel's Beta distribution, enabling microsecond-scale decision latency for real-time spectrum access.

Thompson Sampling inherently adapts to non-stationary primary user traffic patterns without explicit change-point detection. When a previously reliable channel degrades due to increased primary user activity, the accumulating failure observations shift the Beta posterior mass downward, naturally reducing that channel's selection probability. Conversely, when a channel improves, success observations pull the posterior upward. For rapidly changing environments, a discounted Thompson Sampling variant applies exponential forgetting by periodically scaling down both α and β counts, preventing the posterior from becoming overconfident in stale observations and maintaining responsiveness to sudden spectrum occupancy shifts.

In decentralized cognitive radio networks with multiple secondary users, Thompson Sampling can incorporate collision events as negative feedback. When two users select the same channel simultaneously, both observe a collision (treated as a failure), updating their posteriors to reduce that channel's future selection probability. This creates an emergent implicit coordination mechanism without explicit message passing—users naturally diverge to orthogonal channels over time. The probabilistic nature of Thompson Sampling prevents deterministic collision loops that plague greedy algorithms, as the sampling step introduces sufficient randomness to break ties and explore alternative channel assignments.

When side information such as time of day, historical occupancy patterns, or geolocation is available, Contextual Thompson Sampling extends the algorithm by modeling channel reward as a function of observed features. A Bayesian logistic regression or neural network with dropout maintains a posterior distribution over model weights. At decision time, a weight vector is sampled from the posterior, and the channel with the highest predicted reward under that sampled model is selected. This enables the cognitive radio to learn that certain channels are reliably idle during off-peak hours while others open during specific temporal windows, dramatically improving spectrum utilization in patterned traffic environments.

Against reactive jammers that sense and target active transmissions, Thompson Sampling provides inherent anti-jamming robustness. The algorithm's stochastic channel selection makes the secondary user's behavior unpredictable to an adversary—unlike deterministic UCB or ε-greedy policies that follow fixed patterns. When jamming is detected as channel degradation, the Beta posterior rapidly shifts probability mass away from targeted channels. Adversarial bandit variants of Thompson Sampling explicitly model worst-case reward sequences, providing theoretical guarantees on cumulative regret even when a jammer adapts its strategy, making it suitable for contested electromagnetic environments in defense applications.