Technical Summary: Joint AP Probing and Scheduling via Contextual Bandits

Problem Definition

The paper addresses the challenge of efficiently allocating wireless resources in a scenario where a set of Access Points (APs) cooperatively serve a single mobile client. The core difficulty lies in the uncertainty of data rates: the capacity of each link follows an unknown distribution that varies based on the client's location and environmental factors (e.g., blockages, interference).

Unlike traditional link scheduling problems where the decision-maker must choose a link without prior observation, this work assumes a joint probing and play setting. In each time step, the decision-maker can probe a limited subset of $K$ APs (where $K < N$, and $N$ is the total number of APs) to observe their instantaneous rewards (data rates) before selecting a single AP to serve the client. The objective is to maximize the cumulative expected reward over a time horizon $T$ by learning an optimal policy that balances exploration (probing to learn distributions) and exploitation (serving the client).

The authors model this as a Contextual Bandit with Probing (CBwP) problem. The "context" is the client's location, and the "arms" are the APs. The reward distribution $\Phi(a|x)$ for arm $a$ given context $x$ is unknown.

Methodology

1. Offline Optimal Structure (MDP Formulation)

Before addressing the online learning problem, the authors analyze the offline setting where reward distributions are known. They model the joint probing and play decision at each time step as a Markov Decision Process (MDP).

• State: The history of probed arms and their observed rewards.
• Optimal Play Policy: They prove that for any probing history, the optimal strategy is deterministic: play the arm with the maximum observed reward among probed arms, or the arm with the highest expected reward among unprobed arms.
• Optimal Probing Policy: For the specific case of Bernoulli rewards (where the reward is 1 with probability $\mu(a|x)$ and 0 otherwise), they derive a simple non-adaptive optimal policy: probe the $K$ arms with the highest expected rewards $\mu(a|x)$, and if none yield a reward of 1, play the $(K+1)$-th best arm.

2. Online Learning Algorithm: Contextual Zooming

To handle the online setting with unknown distributions, the authors extend the Contextual Zooming algorithm (originally proposed for standard contextual bandits) to the CBwP framework.

• Space Partitioning: The algorithm maintains a set of "active balls" (regions in the context space) for each AP. Initially, the entire space is covered by a single ball of radius 1.
• Index Calculation: For each ball $B$, the algorithm computes an index $I_t(B)$ that combines the average observed reward, the ball's radius, and a confidence term (Upper Confidence Bound style).
• Three-Phase Decision Process per Round:
  1. Probing Rule: The algorithm selects up to $K$ arms to probe. It chooses the unprobed arm associated with the active ball containing the current context $x_t$ that has the highest index. Probing stops early if an arm yields a reward of 1 (for Bernoulli) or after $K$ probes.
  2. Playing Rule: After probing, the algorithm selects an arm to play. If a probed arm yielded a reward of 1, it is played. Otherwise, the algorithm plays the arm with the highest estimated value (either the observed reward if probed, or the index if not).
  3. Activation Rule: If an arm is probed or played, the algorithm updates statistics. If the confidence radius of the current ball is smaller than the ball's physical radius, the ball is "zoomed in" by activating a new child ball with half the radius centered at the current context.

3. Regret Analysis

The authors establish a theoretical regret bound for the algorithm under the assumption of Bernoulli rewards. They define "clean runs" where the estimated rewards are close to the true means (within a confidence interval). By bounding the probability of "bad runs" and analyzing the regret during clean runs using the Lipschitz continuity of the reward function with respect to context distance, they derive a sub-linear regret bound that depends on the covering number of the context space and the probing limit $K$.

Key Contributions

1. Novel Framework (CBwP): The paper introduces Contextual Bandits with Probing, a new extension of the classic contextual bandit model that explicitly incorporates a "probing" phase before the "play" phase. This models real-world constraints where limited channel sounding (e.g., beamforming) is possible before transmission.
2. Structural Insights: The authors provide structural properties of the offline optimal solution, demonstrating that for Bernoulli rewards, a greedy non-adaptive probing strategy is optimal.
3. Algorithm Design: They propose an efficient online learning algorithm that adapts the contextual zooming technique to the joint probing/play setting, handling the trade-off between probing cost and information gain.
4. Theoretical Guarantees: A formal regret bound is established for the proposed algorithm in the Bernoulli reward case.
5. Empirical Validation: The solution is evaluated using real-world channel traces from an 802.11ad testbed and a mmWave channel simulator.

Experimental Results

The evaluation was conducted in a "Student Hall" scenario using 802.11ad routers and laptops, simulating mobile clients moving through the environment.

• Baselines: The proposed CBwP algorithm was compared against four baselines: Random Probing/Random Play (RR), Random Probing/Greedy Play with Exploration (RG), Random Probing/Greedy Play without Exploration (RG2), and Greedy Probing/Play without Exploration (GNE).
• Performance:
  • Regret: CBwP consistently achieved lower cumulative regret than all baselines. While baselines showed higher regret that increased with the number of APs, CBwP remained stable.
  • Probing Limit ($K$): Increasing $K$ (the number of probes allowed) reduced regret for all algorithms, but CBwP maintained a significant advantage regardless of $K$.
  • Scalability: As the number of APs ($N$) increased, the performance of baselines degraded, whereas CBwP demonstrated robustness.
  • Dynamic Environments: The algorithm successfully adapted to new clients entering previously unexplored areas of the room, showing rapid convergence to low regret.

Significance and Claims

The paper claims that the CBwP model is a novel extension of the classic contextual bandit framework. Its primary significance lies in its ability to model and solve sequential decision-making problems where a decision-maker can acquire partial information (via probing) before acting, under uncertainty.

The authors assert that this framework is directly applicable to joint beamforming and scheduling in next-generation mmWave WLANs (802.11ad/ay), where full beamforming is too costly, but limited probing is feasible. Furthermore, they suggest the model has broader applicability to other domains involving joint probing and play, such as:

• Combinatorial Multi-Armed Bandits: For multi-AP, multi-client settings.
• Pathfinding in Road Networks: Where a searcher can query a server for limited traffic hints before choosing a path, balancing query costs against travel latency.

The work emphasizes that while probing reduces uncertainty, it does not eliminate it entirely; therefore, the proposed algorithm's integration of exploration into both the probing and playing stages is crucial for achieving optimal performance.