🤖 machine learning

Link Adaptation Using Joint-Thompson Sampling

This paper proposes the Joint-Thompson Sampling (Joint-TS) algorithm for link adaptation, which improves upon traditional multi-armed bandit approaches by utilizing a multivariate ordered Beta distribution to preserve the inherent monotonicity of Modulation and Coding Scheme success probabilities, thereby achieving robust and consistent throughput across various channel conditions.

Original authors: Vignatha Vinjam, Manjunath Kolavennu, Myna Vajha, Karthik Periyapattana Narayanaprasad

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vignatha Vinjam, Manjunath Kolavennu, Myna Vajha, Karthik Periyapattana Narayanaprasad

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message across a noisy, shifting playground. You have a toolbox full of different "codes" (called Modulation and Coding Schemes, or MCS) to use. Some codes are super fast but very fragile (they break if the playground gets a little bumpy), while others are slow but super tough (they survive the bumps but take forever to send).

Your goal? To pick the perfect code for the current moment to send the most data possible without the message getting garbled. This is called Link Adaptation.

The Old Way: Guessing and Checking

Traditionally, the person sending the message (the transmitter) would use a rigid rulebook. If the playground looked calm, pick the fast code. If it looked rough, pick the slow code. If a message failed, they'd nudge the rulebook slightly.

But here's the problem: playgrounds change fast! If the wind picks up (a "Doppler shift"), the old rulebook is too slow to react. It's like trying to drive a car using a map from yesterday.

The New Idea: The "Ordered" Gamble

Recently, scientists started treating this like a game of Multi-Armed Bandits (think of a row of slot machines). Each code is a slot machine. You pull a lever (send a message), and you either win (it arrives) or lose (it fails). The goal is to figure out which machine pays out the most right now.

Most existing algorithms treat each slot machine as a totally separate mystery. They don't know that the machines are actually related. In reality, there's a golden rule: If a "slow and tough" code works, the "fast and fragile" code might work, but if a "fast and fragile" code fails, the "slow and tough" one definitely still works. The success rates are naturally ordered.

The authors of this paper say, "Why ignore that order?" They propose a new algorithm called Joint-Thompson Sampling (Joint-TS).

The Magic Trick: The "Ordered" Dice

Imagine you have a bag of dice, one for each code.

Old Method (Classical Thompson Sampling): You roll each die independently. Sometimes, the math gets weird, and you might roll a "high success" number for a fragile code and a "low success" number for a tough code. That breaks the laws of physics!
The New Method (Joint-TS): The authors use a special trick called a Multivariate Ordered Beta (MOB) distribution. Instead of rolling dice separately, they roll them as a team. They force the results to stay in order: the "tough" code always gets a higher success number than the "fragile" code.

To do this, they use a mathematical dance called Gibbs sampling. It's like a game of "hot potato" where they pass the dice around, adjusting each one based on its neighbors, until the whole group settles into a perfect, ordered line. This ensures the algorithm never makes a physically impossible guess.

What the Simulations Showed

The team ran these ideas through a computer simulation (using a library called pyitpp) to see how they fared in two worlds: a calm, static playground and a wild, windy one (high Doppler).

1. The Calm Playground (Static Channels):
When the wind was still, the old rulebooks (OLLA) and the new "ordered" method (Joint-TS) were both pretty good. Joint-TS was slightly behind the absolute best possible score but was very close. For example, at a signal strength of 10dB, Joint-TS hit 2.54 bps/Hz, while the "perfect" method hit 2.68 bps/Hz. It's a tight race, but Joint-TS holds its own.

2. The Windy Playground (Doppler Channels):
This is where the magic happens. When the wind picked up (simulating a fast-moving car or train), the old methods started to stumble.

The "Lookup Table" Method (LTS): This method relies on a pre-written map of how the wind affects the codes. When the wind got really strong (111 Hz Doppler shift), this map became useless. The algorithm crashed, dropping to 1.29 bps/Hz.
The "Independent" Method (UTS): This method, which ignores the order of the codes, also struggled, dropping to 1.56 bps/Hz.
The "Joint" Method (Joint-TS): Because it respected the natural order of the codes, it stayed steady. Even in the strongest wind (111 Hz), it maintained 1.56 bps/Hz.

3. The "No Clues" Scenario (No CQI):
Sometimes, the sender doesn't get a weather report (Channel Quality Index or CQI) at all. They have to guess blindly.

Without CQI, the "Lookup Table" method (LTS) actually did surprisingly well in calm winds but still struggled in high winds.
The "Independent" method (UTS) fell apart completely, dropping to 1.04 bps/Hz in calm winds and 1.21 bps/Hz in windy ones.
Joint-TS remained the most robust. Even without a weather report and with high wind, it kept delivering 1.32 bps/Hz, outperforming the others in the toughest conditions.

The Bottom Line

The paper doesn't claim to have "solved" the problem of wireless communication forever. Instead, the simulations suggest that Joint-TS is a smarter way to gamble on which code to use. By respecting the fact that "tougher codes are always more likely to succeed than fragile ones," it avoids the mistakes that other algorithms make when the environment gets chaotic.

While other methods might fail when the wind blows hard or when they lack a weather report, Joint-TS keeps the data flowing. It's not a magic wand, but in the simulations, it proved to be the most reliable teammate for a bumpy ride.

Technical Summary: Link Adaptation Using Joint-Thompson Sampling

Problem Formulation
Link Adaptation (LA) is a critical Medium Access Control (MAC) layer function responsible for selecting optimal transmission parameters, specifically the Modulation and Coding Scheme (MCS), to maximize throughput under a Block Error Rate (BLER) constraint. In downlink scenarios, the base station (gNB) lacks direct channel state information and relies on Channel Quality Index (CQI) feedback from the User Equipment (UE). Traditional approaches, such as Outer Loop Link Adaptation (OLLA), utilize ACK/NACK statistics to adjust Signal-to-Interference-plus-Noise Ratio (SINR) offsets. However, OLLA is often slow to adapt to rapidly changing channels (high Doppler shifts) and lacks per-CQI state granularity.

Recent literature has modeled LA as a Multi-Armed Bandit (MAB) problem, where each MCS represents an "arm" with an unknown success probability. While algorithms like Upper Confidence Bound (UCB) and standard Thompson Sampling (TS) have been applied, they typically treat MCS arms as independent. This independence assumption fails to capture a fundamental physical property of wireless channels: the monotonicity of success probabilities. Specifically, lower MCS indices (more robust modulations) inherently possess higher success probabilities than higher MCS indices (higher spectral efficiency) for a given channel condition ( $\theta_1 \ge \theta_2 \ge \dots \ge \theta_K$ ). Existing MAB solutions that ignore this constraint may sample infeasible configurations or converge sub-optimally, particularly when CQI feedback is unavailable or channel conditions are highly dynamic.

Methodology: Joint-Thompson Sampling (Joint-TS)
The paper proposes Joint-Thompson Sampling (Joint-TS), an algorithm designed to explicitly preserve the monotonicity of MCS success probabilities throughout the learning process.

Multivariate Ordered Beta (MOB) Prior: Unlike classical TS, which assumes independent Beta distributions for each arm, Joint-TS utilizes a Multivariate Ordered Beta (MOB) distribution as the prior. This distribution is defined over the simplex $S = \{ \theta \in [0, 1]^K \mid \theta_1 \ge \theta_2 \ge \dots \ge \theta_K \}$ . By sampling from this joint distribution, the algorithm guarantees that every sampled set of success probabilities satisfies the physical monotonicity constraint.
Gibbs Sampling for Inference: Direct sampling from the MOB distribution is non-trivial. The authors employ a Gibbs sampling technique (a Markov Chain Monte Carlo method) to generate samples. The core of this approach relies on the lemma that the conditional distribution of any single arm $\Theta_i$ , given the others, follows a Restricted Beta distribution bounded by the values of its neighbors ( $\theta_{i+1} \le \Theta_i \le \theta_{i-1}$ ).
Algorithm Flow: At each time step, Joint-TS:
- Samples a vector of success probabilities $(\Theta_1, \dots, \Theta_K)$ from the current MOB posterior using Gibbs sampling.
- Selects the MCS arm $I_t$ that maximizes the expected reward ( $s_i \cdot \Theta_i$ ).
- Observes the reward (ACK/NACK) and updates the parameters of the selected arm. Due to the joint distribution, this update implicitly influences the posterior of all other arms, maintaining the monotonicity constraint without requiring explicit re-ordering.

Key Contributions

Monotonicity-Aware MAB: The paper introduces Joint-TS, the first MAB-based LA algorithm to rigorously enforce the ordered nature of MCS success probabilities using a multivariate prior, rather than treating arms as independent entities.
Sampling Mechanism: The authors propose a practical Gibbs sampling method to draw samples from the MOB distribution, addressing the computational challenge of sampling from ordered multivariate distributions.
Robustness to CQI Limitations: The work demonstrates that Joint-TS maintains performance even when CQI feedback is unavailable, a scenario where state-of-the-art unimodal algorithms (like UTS) and table-dependent algorithms (like Latent-TS) degrade significantly.

Simulation Results
The authors evaluated Joint-TS against OLLA, Modified Thompson Sampling (MTS), Unimodal Thompson Sampling (UTS), and Latent-TS (LTS) using 5G NR MCS configurations (29 levels) in both static and Doppler-shifted channel environments.

Static Channels: In static conditions with perfect CQI, Joint-TS achieved competitive throughput (e.g., 2.54 bps/Hz at 10 dB SINR) comparable to LTS (2.68 bps/Hz).
High Doppler (Mobile) Scenarios:
- With Perfect CQI: While UTS and LTS performed well at low Doppler shifts, LTS degraded significantly at high Doppler shifts (111 Hz). Joint-TS maintained stable throughput (1.56 bps/Hz) comparable to UTS, outperforming LTS (1.29 bps/Hz).
- Without CQI: In the absence of CQI feedback, UTS struggled significantly (dropping to 1.34 bps/Hz at 111 Hz). LTS maintained high throughput in low-mid Doppler settings but showed degradation. Joint-TS demonstrated consistent robustness across all Doppler shifts, maintaining throughput (1.32 bps/Hz at 111 Hz) superior to UTS and MTS, and competitive with LTS.

Significance and Claims
The paper claims that Joint-TS offers a principled approach to Link Adaptation that leverages the inherent structure of wireless channels. By utilizing the MOB distribution, the algorithm avoids the inefficiencies of exploring infeasible MCS combinations. The authors highlight that while existing algorithms (like CoTS) attempt to exploit monotonicity, their sampling techniques may not strictly adhere to the joint distribution properties.

The primary significance of Joint-TS lies in its robustness. The simulations indicate that while other algorithms fail in specific scenarios—such as high-mobility environments or when CQI feedback is missing—Joint-TS delivers consistent, competitive throughput. The authors position Joint-TS as a solution that does not rely on pre-existing, potentially inaccurate lookup tables (unlike LTS) and adapts quickly to changing channel dynamics without manual parameter tuning. The work suggests that enforcing physical constraints (monotonicity) within the probabilistic framework of MAB leads to superior performance in practical, dynamic wireless environments.