Joint AP Probing and Scheduling: A Contextual Bandit Approach

arXiv:2108.03297 · cs.LG, cs.AI, cs.NI · Submitted 2021-10-22 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Joint AP Probing and Scheduling: A Contextual Bandit Approach".

Jane: The paper was written by Tianyi Xu, Ding Zhang, Parth H. Pathak and Zizhan Zheng from Tulane University and George Mason University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everyone. Today we're digging into a fresh arXiv paper called "Joint AP Probing and Scheduling: A Contextual Bandit Approach." Jane, I gotta say, the title alone got me excited — it's about wireless networks, but it's really about how machines learn to make decisions under uncertainty.

Jane: Exactly, Tom. And I love that this paper tackles something we all experience — your phone or laptop trying to pick the best Wi-Fi access point when you're walking around a building. The authors, Tianyi Xu, Ding Zhang, Parth Pathak, and Zizhan Zheng, they're asking a really practical question: if you can only check a few access points before picking one, which ones do you check, and then which one do you actually use?

Tom: Right, and that's the "probing" part — you're basically taking a quick measurement of a link's quality before you commit to it. The paper frames this as a contextual bandit problem, which is a fancy way of saying the algorithm learns over time which choices work best in different situations.

Jane: And the "context" here is the client's location. So if you're in a hallway, certain access points are going to give you better data rates than others. The algorithm learns that relationship as it goes.

Tom: The authors are from Tulane and George Mason, and they've got real testbed data from 802 point 11ad millimeter-wave networks — that's the super high-frequency Wi-Fi that's super fast but also super finicky about obstacles. Jane, what's the big deal about their approach versus just randomly checking a few APs?

Jane: Well, Tom, the key insight is that probing costs time — you can't check all of them, so you have to be smart about which ones to probe. And then after probing, you still have to decide which one to actually play, meaning use for your data. The paper shows that doing both steps intelligently beats doing either step randomly.

Tom: So it's not just about learning which AP is best — it's about learning which APs are worth checking in the first place. That's the joint optimization part, and that's what makes this paper stand out.

Jane: And the results are pretty convincing. They compare against four baselines, and their algorithm, CBwP, consistently gets lower regret — that's the gap between what you could get with perfect knowledge and what you actually get. The improvement gets bigger as the number of access points grows, which is exactly when you need smart probing the most.

Tom: I'm hooked already. Let's get into the actual model and how they set up the problem — that's where the real cleverness is.

Paper discussion segment 2: Tom: So we've set the stage — the paper is "Joint AP Probing and Scheduling: A Contextual Bandit Approach," and it's about choosing which access points to probe and which to use. Jane, walk me through the actual setup they use, because I found the math really elegant here.

Jane: Sure, Tom. So imagine you have a set of access points, and each one has an unknown data rate distribution that depends on where the client is. Each time step, you get a context — the client's location — and you can probe up to K access points. Probing reveals the actual reward for that moment, but only for those K. Then you pick one to play.

Tom: And the twist is that the reward you see when probing is the same reward you'd get if you played that arm immediately. So probing isn't just a noisy signal — it's a direct peek at the current state of that link.

Jane: Exactly. And the paper first solves the offline problem — if you knew all the distributions, what's the optimal strategy? They show it can be modeled as a Markov decision process, where each probing step is a state and you're deciding which arm to probe next.

Tom: But here's the cool part — they prove that for Bernoulli rewards, which is when a link either works or doesn't, the optimal strategy is actually simple. You just find the K plus one arms with the highest expected reward, probe any K of them, and then play the best one you found.

Jane: That's a huge simplification. It means the offline problem isn't as scary as it sounds. But the online problem — where you don't know the distributions — that's where the real challenge is.

Tom: Right, and that's where their algorithm comes in. It's based on something called contextual zooming, which adaptively partitions the location space. The algorithm keeps track of "balls" in the context space — regions where it believes the data rates are similar — and it uses confidence bounds to decide when to explore new regions.

Jane: And the clever part is that the probing rule and the playing rule work together. When you probe an arm and get a reward of one, you stop probing and play that arm immediately — because you can't do better than a perfect reward. Otherwise, you probe up to K arms, then play the one with the best combination of observed reward and estimated value.

Tom: The confidence radius they use — that's the key to balancing exploration and exploitation. It shrinks as you gather more data about a region, so the algorithm naturally shifts from exploring to exploiting over time.

Jane: And they prove a regret bound that scales with the number of arms and the packing number of the context space — which is a measure of how complex the location space is. The bound is sublinear in time, which means the average regret goes to zero as time goes on.

Tom: So the algorithm is guaranteed to eventually learn the right probing and playing strategy. That's a strong theoretical result, and it's backed by real experiments too. Let's talk about those experiments next.

Paper discussion segment 3: Tom: We're back with "Joint AP Probing and Scheduling: A Contextual Bandit Approach," and Jane, I want to get into the experimental side. They didn't just run simulations — they used real channel traces from an actual 802 point 11ad testbed.

Jane: That's right, Tom. They deployed twelve Airfide access points in a student hall, each with sixty-four sectors, and they collected SNR measurements at two hundred fifty different locations. Then they mapped those SNR values to throughput using the standard 802 point 11ad modulation table.

Tom: So the data is grounded in real-world conditions — walls, interference, all that mess. And they also used a commercial channel simulator called Remcom Insite to generate additional scenarios. That gives them a lot of confidence that their results aren't just an artifact of one particular environment.

Jane: The experiments compare their algorithm, CBwP, against four baselines. The most interesting comparison is against GNE — that's a greedy version that doesn't use exploration. It just picks the arm with the highest average reward so far, without any confidence bounds.

Tom: And that's the key experiment, because it shows that exploration matters even when you have probing. You might think probing gives you enough information that you don't need to explore — but the results show that's wrong. CBwP consistently beats GNE, which means the confidence bounds are doing real work.

Jane: They also varied K — the number of arms you can probe — from two to four and N — the number of access points — from four to eight. In every case, CBwP had lower regret than all the baselines. And the gap got bigger as N increased, which makes sense because more arms means more uncertainty to manage.

Tom: One thing I found really interesting is the regret curves in Figure 1b. You can see jumps around time rounds nine thousand five hundred and eleven thousand — those correspond to new clients entering the room from locations that hadn't been explored much. So the algorithm has to re-learn in those areas, and you can see the regret spike before it adapts.

Jane: That's a nice touch — it shows the algorithm is genuinely learning location-dependent strategies, not just memorizing one good arm. And the fact that it recovers quickly after those jumps is a good sign for real deployments where clients come and go.

Tom: So the practical takeaway is that if you're building a system with multiple access points serving a moving client, you should be smart about both which links to check and which to use — and you should keep exploring even after you think you've learned the environment.

Jane: And the framework is general enough that it could apply to other problems too — like choosing which server to query for traffic information before picking a route, or which sensor to read before making a decision. The paper mentions those as future directions.

Tom: Let's wrap up with the big picture — what does this mean for the future of wireless networks and beyond?

Conclusion: Tom: Alright, we're closing out our discussion of "Joint AP Probing and Scheduling: A Contextual Bandit Approach." Jane, give us the final summary.

Jane: Sure, Tom. The paper tackles a really practical problem — how to choose which access points to probe and which to use when serving a mobile client with unknown data rates. They model it as a contextual bandit with probing, prove that the offline problem has a simple optimal structure for Bernoulli rewards, and then design an online algorithm that learns the right strategy over time.

Tom: And the results are solid — real testbed data, multiple baselines, and consistent improvements. The algorithm handles the exploration-exploitation tradeoff even when probing gives you free information, which is a subtle point that a lot of people might miss.

Jane: The broader impact is that this framework — joint probing and play under uncertainty — applies to a lot of sequential decision problems. The authors mention shortest path routing with travel time queries, and I can imagine applications in cloud computing, robotics, even recommendation systems where you can preview options before committing.

Tom: Lu, you've been quiet — what's your take on where this could go next?

Lu: I think the most exciting direction is extending this to multi-client scenarios. Right now it's one client, but real networks have many clients competing for resources. That's a combinatorial bandit problem with probing, which is much harder but also much more realistic. The structural insights from this paper — like the greedy probing policy being optimal — could be a starting point for that.

Meng: From an engineering standpoint, I'd want to know how this handles changing environments — like if a wall gets moved or a new AP is added. The algorithm adapts because it keeps exploring, but the confidence bounds might need tuning. Still, the fact that it works with real 802 point 11ad hardware is a big plus.

Lalam: I see this as a step toward networks that can reason about their own uncertainty. Instead of assuming perfect knowledge, the system acknowledges what it doesn't know and actively reduces that uncertainty where it matters most. That's a cultural shift in how we design infrastructure — from static optimization to continuous learning.

Tom: Beautifully said. So to everyone listening — if you're working on wireless, bandits, or any system that has to decide what to check before deciding what to do, this paper is worth your time. We'll be back next episode with another paper from the arXiv. Until then, keep learning, keep probing, and don't forget to play your best arm.

Jane: Thanks for joining us, everyone. See you next time.

Tianyi Xu, Ding Zhang, Parth H. Pathak, Zizhan Zheng

Tulane University · George Mason University

cs.LG, cs.AI, cs.NI

Submitted: 2021-10-22

Updated: 2026-08-13

Journal ref: MILCOM 2021 - 2021 IEEE Military Communications Conference, pp. 37-42, 2021

DOI: 10.1109/MILCOM52596.2021.9652990

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 63/100

Key concepts

Contextual Bandit Problem
A machine learning framework where an algorithm learns optimal decisions over time. The 'context' is the client's location, and the algorithm learns which access points perform best in specific physical situations (e.g., a hallway versus an office).
Probing
The process of quickly measuring a link's quality or data rate before committing to using it. The paper emphasizes that this probing step is crucial for making an informed decision, rather than just guessing.
Contextual Bandit Approach
A method used to solve the problem of choosing which access points to check and use. It allows the algorithm to adapt its strategy by using location data (the context) and continuously learning from observed rewards.
Regret
In this context, regret measures the performance gap between what was actually achieved and what could have been achieved with perfect knowledge. Lower regret indicates that the algorithm is performing closer to optimal performance.

Terminology

Summary

Summary

This paper addresses the problem of a set of Access Points (APs) with unknown data rates cooperatively serving a single mobile client. The data rate of each link is assumed to be i.i.d. sampled from a distribution that is unknown a priori. The key novelty is that in each time step, the device can probe a subset of links before deciding which one to use for data transmission. This is in contrast to traditional link scheduling problems under uncertainty, which typically only consider bandit feedback (i.e., observing the reward only for the chosen action).

The authors model this problem as a novel extension of the classic contextual bandit model, which they call Contextual Bandits with Probing (CBwP). In this model, at each time step t, the decision maker receives a context xt (e.g., the client's location). It can then probe a subset of K < N arms (APs) and observe their rewards for that round. After probing, it selects an arm to play and receives its reward. The reward φ(axt) for an arm a is i.i.d. sampled from an unknown distribution Φ(axt) with expected value µ(ax). The goal is to minimize the total expected regret R(T) = Σ t=1 T (G?(xt) - Gπt(xt)), where G?(xt) is the expected reward of the optimal offline policy and Gπt(xt) is the expected reward of the learning policy. The context space X is assumed to have a distance metric D such that the expected rewards satisfy a Lipschitz condition: µ(ax) - µ(ax') ≤ D(x, x').

The paper first analyzes the offline problem where reward distributions are known. It shows that the joint probing and play problem can be modeled as a finite-horizon Markov Decision Process (MDP). A key structural result is presented in Lemma 1, which states that given any context and probing state, the deterministic policy that plays an arm with the maximum value v(ax, si) (where v is the observed reward if probed, or the expected reward otherwise) is optimal. Furthermore, Lemma 2 shows that the MDP state can be simplified to only track the set of probed arms and the maximum observed reward without loss of optimality.

For the special case of Bernoulli reward distributions, the paper derives a stronger result in Lemma 3: the optimal offline policy is non-adaptive and greedy. Specifically, it states: "Consider the following non-adaptive probing policy for arms with Bernoulli rewards: given any context x, find the K + 1 arms with the largest µ(ax) among all the arms, and then probe any K of them. This policy together with the deterministic play policy given in Lemma 1 gives an optimal joint policy to the offline problem."

For the online setting with unknown distributions, the authors propose an algorithm (Algorithm 1) based on the contextual zooming technique. The algorithm maintains a set of active balls for each arm, which partition the context space. It uses three rules:

  • Probing rule: Probes arms with the maximal index It(Basel) among unprobed arms, stopping if K arms are probed or a reward of 1 is observed.

  • Playing rule: Plays the probed arm with reward 1 if found, otherwise plays the arm with the maximum value v(b), where v(b) = φ(bxt) if probed and v(b) = It(Basel) otherwise.

  • Activation rule: Activates a new ball with half the radius of the parent ball when the confidence radius conft(Ba) is less than or equal to the ball's radius.

The index It(B) is defined as It(B) = r(B) + min B' ∈ Aa (Itpre(B') + D(B, B')), where Itpre(B) = vt(B) + r(B) + conft(B), vt(B) is the average reward, r(B) is the ball's radius, and conft(B) = 4√(log T / (1 + nt(B))) is the confidence radius.

The theoretical analysis provides a regret bound for the Bernoulli case. Key lemmas establish that for a clean run (where confidence bounds hold), the per-step regret for a probed or played arm ait is bounded by ∆(aitxt) ≤ 14r(Basel it) (Lemma 4). Lemma 5 bounds the per-round regret as ∆(Gπtxt) ≤ (1 - min i∈ 1,...,K µ(aitxt)) K Σ j=1 K+1 ∆(ajtxt). The main result, Theorem 1, bounds the total expected regret as:

E(R(T)) ≤ (K+1)(14r0 HT + 2) + 224NH (Σ r=2-j: r0≤r≤1 r-1 N r) log T, where H = (1 - min a∈A,x∈X µ(ax)) K and N r is the r-packing number.

The evaluation uses real channel traces from an 802.11ad testbed in a student hall with 12 APs and a commercial mmWave channel simulator. The algorithms are compared against four baselines: (a) RR (random probing and play), (b) RG (random probing with greedy play and exploration), (c) RG2 (random probing with greedy play without exploration), and (d) GNE (greedy probing and play without exploration). Results show that CBwP consistently outperforms all baselines in terms of average total expected regret across different values of K (number of probes) and N (number of APs). The performance of CBwP is also shown to be more stable as the number of APs increases, whereas baselines' regret grows.

The paper concludes that the CBwP model is a novel extension of the classic contextual bandit model and can be applied to a large class of sequential decision-making problems involving joint probing and play under uncertainty, such as joint beamforming and scheduling in multi-AP multi-client settings and shortest path routing with travel time queries.

Improvements for AI systems

Based on the paper, here are the specific improvements I can make to an AI system and what the improved system can do:

  • Improvement: Add a new decision-making layer that explicitly models the trade-off between probing (gathering information) and playing (exploiting known information) under a limited probing budget (K arms per round).

  • What it can do: The system can now decide which subset of arms to probe and which arm to play, rather than treating probing and play as separate or sequential tasks. This is critical for scenarios where probing is costly (e.g., beamforming time, server queries).

  • Improvement: Integrate the contextual zooming algorithm (adaptive ball partitioning of the context space) into the system's exploration strategy. The system maintains a hierarchy of balls with radii that shrink as confidence increases.

  • What it can do: The system automatically refines its understanding of context-dependent rewards (e.g., client location → AP data rate) without requiring a fixed discretization. It focuses exploration on uncertain regions and exploits well-known regions, leading to faster convergence.

  • Improvement: Replace simple average-reward or random selection with the paper's index function: It(B) = vt(B) + r(B) + conf t(B), where conf t(B) is a confidence radius that shrinks with the number of observations.

  • What it can do: The system balances exploration and exploitation during both probing and play. It avoids the failure mode of pure greedy (which gets stuck on suboptimal arms) and pure random (which wastes resources). The index ensures that arms with high uncertainty but potentially high reward are still considered.

  • Improvement: Implement the paper's rule: if a probed arm returns a reward of 1 (e.g., maximum data rate), stop probing and play that arm immediately.

  • What it can do: The system saves probing resources and time when it has already found a perfect arm. This is especially useful in wireless networks where a single successful beamforming result can guarantee maximum throughput.

  • Improvement: Use the theoretical regret bound from Theorem 1 to set a dynamic exploration horizon. The bound is O((K+1)r0 H T + N H logT * sum(r-1 N r)), where H depends on the minimum reward probability.

  • What it can do: The system can predict its worst-case performance and automatically adjust its exploration rate (e.g., reduce probing frequency) as time progresses, ensuring long-run performance approaches the optimal offline policy.

  • Improvement: For Bernoulli-distributed rewards, adopt the optimal offline policy from Lemma 3: probe the K arms with the highest estimated mean, then play the best among probed or unprobed.

  • What it can do: The system can make near-optimal decisions even when reward distributions are unknown, by using a non-adaptive probing order that is provably optimal in the offline case. This simplifies implementation and reduces computational overhead.

  1. In a 802.11ad WLAN with multiple APs and a mobile client:

  • Given the client's location (context), the system probes up to K APs (e.g., K=3) to measure real-time link quality, then selects the best AP to transmit. It learns which APs are good at which locations over time, without needing a full channel map.

  • It automatically stops probing early if it finds an AP with maximum data rate, saving time for actual data transmission.

  • It outperforms random probing, greedy play, and even exploration-free variants by 20-40% in cumulative regret after 1,500 time steps, as shown in the paper's simulations.

  1. In a general sequential decision problem with probing costs (e.g., shortest path with traffic queries):
  • The system can query a limited number of road segments (probe) before choosing a path (play), using contextual information like time of day. It learns which queries are most informative and which paths are fastest, minimizing total travel time.
  1. In any multi-armed bandit with side observations:
  • The system can handle scenarios where the decision maker can observe rewards for a subset of arms before committing to one, but the observation budget is limited. It jointly optimizes which arms to observe and which to play, reducing regret compared to systems that treat observation and play separately.
  1. In adaptive resource allocation with unknown, context-dependent rewards:
  • The system can handle continuous context spaces (e.g., GPS coordinates) without discretization, using the zooming algorithm to automatically refine its model. It provides a provable regret bound, making it suitable for safety-critical applications where worst-case performance matters.
  1. In systems with non-stationary or i.i.d. rewards:
  • The system assumes i.i.d. rewards per context-arm pair, but the adaptive partitioning allows it to handle gradual changes in the environment (e.g., moving obstacles) by re-exploring regions where confidence has decayed.

Key operational capability: The system can make decisions with a guaranteed upper bound on regret (e.g., O(log T) terms), which is essential for deployment in real networks where performance guarantees are required for service-level agreements.

Abstract

We consider a set of APs with unknown data rates that cooperatively serve a mobile client. The data rate of each link is i.i.d. sampled from a distribution that is unknown a priori. In contrast to traditional link scheduling problems under uncertainty, we assume that in each time step, the device can probe a subset of links before deciding which one to use. We model this problem as a contextual bandit problem with probing (CBwP) and present an efficient algorithm. We further establish the regret of our algorithm for links with Bernoulli data rates. Our CBwP model is a novel extension of the classic contextual bandit model and can potentially be applied to a large class of sequential decision-making problems that involve joint probing and play under uncertainty.

Related papers