Online Learning for Adaptive Probing and Scheduling in Dense WLANs

arXiv:2212.13585 · cs.LG, cs.AI, cs.NI · Submitted 2023-01-12 · 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 "Online Learning for Adaptive Probing and Scheduling in Dense WLANs".

Jane: The paper was written by Tianyi Xu, Ding Zhang 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, everyone! Tom here with my co-host Jane, and we are digging into a fresh arXiv paper that has us genuinely fired up. It’s called “Online Learning for Adaptive Probing and Scheduling in Dense WLANs.” Jane, I gotta say, the title alone makes me think of a traffic jam of Wi-Fi signals, but it’s way more interesting than that.

Jane: Oh, absolutely, Tom. So the paper is about dense wireless networks, like when you have tons of access points in a building, and a single client moving around. The big question is: how do you pick which access point to connect to, when checking each one takes time and costs you throughput? The authors are from Tulane and George Mason, and they’re tackling this with a mix of probing and learning.

Tom: Right, and probing here isn’t just a quick ping. In millimeter-wave networks, which is what they’re looking at, probing means beamforming—actually sweeping through sectors to find the best signal. That can take milliseconds per access point. If you have dozens of APs, you can’t probe them all every time. So the paper asks: which ones do you check, and when do you stop checking and just send data?

Jane: And that’s the clever part. They don’t just randomly probe. They model this as a bandit problem, where you’re learning the quality of each link over time. But unlike classic bandits where you only learn after you play, here you can probe first, get a hint, and then decide. The twist is that probing costs you—you lose a fraction of your data slot for every probe you do.

Tom: So it’s a tradeoff between information and time. The more you probe, the better your choice, but the less time you have to actually transmit. And they show that even when you know the link distributions perfectly, finding the best probing set is hard. They give an approximation algorithm for the non-adaptive case, and a dynamic programming approach for the adaptive case where you can change your mind based on what you see.

Jane: And for the online world, where you don’t know the distributions at all, they adapt a combinatorial bandit algorithm and prove a regret bound. That’s a big deal because it means the system learns over time and gets closer to optimal performance without needing a perfect model upfront.

Tom: I love that they validate it with real mmWave channel traces from an actual testbed. That’s not just theory—they’re using real SNR data from a student hall with twelve access points. So the results aren’t just simulations in a vacuum.

Jane: Exactly. And the punchline is that adaptive probing—where you decide the next AP to check based on what you’ve already seen—beats non-adaptive probing in their experiments. That makes sense, because if you probe one AP and it gives you a great signal, you can stop early and save time.

Tom: So this isn’t just about Wi-Fi. This framework could apply to any situation where you can get a cheap hint before making a decision, like shortest path routing with traffic queries. But we’ll get into that later. For now, I’m hooked on the idea that sometimes the best move is to stop gathering information and just act.

Jane: And that’s the core tension, Tom. When do you stop probing and start transmitting? The paper gives us a principled way to answer that, not just a gut feeling. We’ll dig into the offline algorithms next, because that’s where the real math lives.

Summary: Tom: So we’ve set the stage. Now let’s get into the meat of “Online Learning for Adaptive Probing and Scheduling in Dense WLANs.” Jane, can you break down the offline setting for us? That’s where they assume you know the link rate distributions ahead of time.

Jane: Sure. In the offline case, you know the probability distribution of each AP’s data rate for each context—like the client’s location. The problem is, given a probing budget K, which APs should you probe? If you probe a set S, you see their actual rates, and then you pick the best one to play. But you also have unprobed APs, and for those, you only know their average rates.

Tom: So it’s like having a menu where some dishes you can taste before ordering, but tasting costs you a bite of your meal. The goal is to maximize the expected reward, which is the best rate you can get, scaled down by how many probes you used.

Jane: Right. And the key observation is that once you’ve probed a set, the optimal play is simple: pick the arm with the highest observed value, or the highest average if it wasn’t probed. So the hard part is choosing the probing set. They show that the natural greedy approach—adding the AP that gives the biggest marginal improvement—works well.

Tom: And they prove an approximation factor of (2e-one)/(e-one), which is about zero point seven six. That means even in the worst case, the greedy algorithm gets at least seventy-six percent of the optimal expected throughput. Not bad for a simple algorithm.

Jane: But here’s where it gets interesting. For the adaptive setting, where you can decide to probe the next AP based on what you’ve already seen, they use dynamic programming. They define a state as the number of probes done and the best value observed so far. Then they solve a Bellman equation to decide whether to keep probing or stop and play.

Tom: And for Bernoulli arms—where each AP either gives you full rate or zero—they prove that the optimal strategy is to probe APs in order of their mean reward. That’s a beautiful result because it’s so intuitive. If you have a coin that lands heads more often, you flip it first.

Jane: Exactly. And the dynamic programming algorithm is optimal for that case. For general distributions, they don’t have a proof of optimality, but they use a greedy ordering based on marginal improvement, and their simulations show it performs really well.

Tom: So the offline part gives you a solid foundation. But the real world doesn’t hand you the distributions. That’s where the online learning comes in, and that’s what I’m most excited about. How do you learn while also making good decisions?

Jane: That’s the classic exploration-exploitation tradeoff. They adapt a combinatorial bandit algorithm that maintains an empirical distribution for each AP based on past observations. Then, instead of using the true distribution, they use a lower confidence bound to be optimistic about uncertain arms. That encourages exploration.

Tom: And they prove a regret bound that grows like the square root of T times the Lipschitz constant times the context discretization error. So as time goes on, the algorithm gets closer and closer to optimal performance, even with a large context space.

Jane: The context space is handled by discretizing locations into cells. They map each client position to the nearest cell center, and they show that the loss from that mapping is bounded by L times the cell size. So if you make the cells fine enough, you can make the error as small as you want.

Tom: I love that they think about the practical side too. They use real traces, not just synthetic data. That makes the results much more convincing.

Jane: And the takeaway from their experiments is that adaptive probing consistently beats non-adaptive probing, especially when the reward distributions are more complex. We’ll talk about those experiments in more detail next, because the numbers really tell the story.

Improvements: Tom: We’re back, and we’re digging into the experimental results of “Online Learning for Adaptive Probing and Scheduling in Dense WLANs.” Jane, what did they actually test, and what did they find?

Jane: They collected channel traces from a real 802 point 11ad testbed in a student hall with twelve access points. They mapped SNR values to throughput using the standard MCS table. Then they simulated clients moving through two hundred fifty different locations, with walking speeds of about one meter per second. They compared their algorithms—CBNA for non-adaptive probing and CBA for adaptive probing—against a few baselines.

Tom: And the baselines were things like greedy probing without exploration, random probing with greedy play, and fully random. The results showed that CBA and CBNA both beat the baselines pretty quickly. But the interesting part is that CBA, the adaptive one, starts slower but catches up and surpasses CBNA after a few thousand rounds.

Jane: That makes sense. Adaptive probing is more complex, so it needs more data to learn the right stopping rules. But once it learns, it saves time by stopping early when it sees a good signal, which gives it more time for actual data transmission.

Tom: They also looked at the cumulative regret compared to the optimal offline solution. In the Bernoulli case, where each AP either gives full rate or zero, the regret of CBA and CBNA is much lower than the baselines. But there’s a jump in regret around rounds fifteen thousand and seventeen thousand. What’s that about?

Jane: That’s when the client moves into a new context cell that hasn’t been explored much. The algorithm has to learn the distributions for that new location from scratch, so it makes more mistakes initially. It’s like moving to a new city—you don’t know which restaurants are good yet, so you waste a few meals.

Tom: And for the general distribution case, where rates can be zero one/three two/three or one they found that CBA consistently outperforms CBNA. The gap is bigger than in the Bernoulli case. That suggests that adaptive probing really shines when the outcomes are more nuanced, not just binary.

Jane: Exactly. With Bernoulli, once you see a one, you stop immediately. With multiple levels, you might want to probe a bit more to see if you can get a higher rate. The adaptive algorithm learns when to stop, and that saves time.

Tom: And the standard deviation bands they show—CBA has tighter bands, meaning it’s more consistent. That’s a nice property for a real deployment, where you don’t want wild swings in performance.

Jane: One thing I appreciated is that they used fifty samples to estimate the value function f(S) in the greedy algorithm. That’s a practical detail that makes the algorithm run in reasonable time. They also mention that the time complexity of the offline adaptive algorithm is O(YK(N+Y)), which is manageable for realistic numbers of APs and outcomes.

Tom: So the improvements over the baselines are clear, but what about the bigger picture? This isn’t just about Wi-Fi. The framework could apply to any system where you can probe before acting—like selecting a server in a data center, or choosing a route in a road network with live traffic data.

Jane: And that’s what I love about this paper. It takes a specific problem—dense mmWave WLANs—and solves it so well that the approach generalizes. The regret bounds and approximation guarantees give you confidence that the algorithm will work, not just in simulation but in the real world.

Tom: And they’re not stopping here. The paper mentions future work like extending to multiple clients and more complex interference models. But for now, this is a solid step forward in making dense wireless networks smarter.

Jane: Agreed. And the fact that they validate with real hardware traces makes it even more compelling. We’ll wrap up with our final thoughts next.

Conclusion: Tom: Alright, we’ve reached the end of our discussion on “Online Learning for Adaptive Probing and Scheduling in Dense WLANs.” Jane, what’s the big takeaway you want our listeners to remember?

Jane: The big takeaway is that probing isn’t free. Every time you check an access point, you lose a little bit of time that could have been used for data. This paper gives you a principled way to decide which APs to probe, and when to stop probing and just transmit. And it does that even when you don’t know the link quality in advance.

Tom: And they prove that their algorithms are near-optimal, both in the offline case with known distributions and in the online case with learning. The regret bounds are tight, and the experiments with real mmWave traces show that adaptive probing pays off, especially in complex environments.

Jane: I also love that they bridge the gap between theory and practice. The approximation factor for the greedy algorithm is solid, the dynamic programming solution is optimal for Bernoulli arms, and the online algorithm has a clean regret bound. But they also test it on real hardware, which is rare in this kind of work.

Tom: And the implications go beyond Wi-Fi. Think about any decision where you can get a hint before committing—like a delivery robot checking which route is clear, or a cloud system pinging servers before routing a request. This framework gives you a way to balance the cost of checking against the benefit of knowing.

Jane: Exactly. And the fact that they handle context—like the client’s location—means the algorithm adapts to changing environments. That’s crucial for mobile users.

Tom: So, we’re saying goodbye to this paper, but I have a feeling we’ll see follow-up work. Maybe multi-client scheduling, or more complex interference models. For now, this is a great contribution to the wireless networking community.

Jane: And to the broader online learning community too. The way they combine probing with bandits is clever and generalizable. Thanks for joining us, and we’ll be back with the next paper soon.

Tom: Until then, keep your signals strong and your probes efficient. See you next time!

Tianyi Xu, Ding Zhang, Zizhan Zheng

Tulane University · George Mason University

cs.LG, cs.AI, cs.NI

Submitted: 2023-01-12

Updated: 2026-08-13

Journal ref: IEEE INFOCOM 2023 - IEEE Conference on Computer Communications, pp. 1-10, 2023

DOI: 10.1109/INFOCOM53939.2023.10228988

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

Importance score: 52/100

The gist: This paper proposes a joint probing and scheduling framework for throughput optimization in dense millimeter-wave (mmWave) Wireless Local Area Networks (WLANs), addressing the challenge of balancing

Key concepts

Dense WLANs
These are wireless networks with many access points (APs), such as those found in a large building. The challenge is efficiently connecting a mobile client to the best AP without wasting time checking every single one.
Probing/Beamforming
In this context, probing means sweeping through sectors to find the best signal from an AP. This process, like beamforming in mmWave networks, takes time and costs throughput, making efficient probing critical.
Bandit Problem
The paper models the connection selection as a bandit problem—a scenario where the system must learn the quality of different links over time. The goal is to maximize reward while minimizing the cost of gathering information.
Adaptive Probing
This strategy involves deciding which AP to check next based on signals already received. It allows the system to stop probing early if a strong signal is found, saving time and improving efficiency.

Terminology

Summary

This paper proposes a joint probing and scheduling framework for throughput optimization in dense millimeter-wave (mmWave) Wireless Local Area Networks (WLANs), addressing the challenge of balancing the information gained from link probing (e.g., via beamforming) against the overhead cost of reduced data transmission opportunity. The authors model the problem as a contextual bandit with joint probing and play, where in each time round, a decision maker receives a context (e.g., client location), probes a subset of arms (APs) up to a budget K, observes their outcomes, and then plays an arm to receive a reward, with the throughput normalized as R(St, Yt, atxt) = (K - St)/K * Yatxt.

The paper considers two probing settings: non-adaptive (probing set chosen independently of probing results) and adaptive (next probing decision can depend on previous probing results). For the offline setting with known link rate distributions, the authors develop: (1) an approximation algorithm for non-adaptive probing (Algorithm 2) with a proven approximation factor of α = (e-1)/(2e-1) for general distributions, and (2) a dynamic programming-based solution for adaptive probing (Algorithm 3) that is proven optimal for Bernoulli link rates. For the online setting with unknown distributions, the authors adapt a stochastic combinatorial bandit algorithm (Algorithm 4) and derive distribution-dependent and distribution-independent regret bounds, incorporating Lipschitz-continuity of the context space to handle large context spaces.

Key theoretical results include: Theorem 1 establishes the approximation ratio of Algorithm 2; Theorem 2 proves that for Bernoulli arms, it is optimal to probe arms in non-increasing order of their mean rewards; Lemma 1 bounds the discretization error as DE(T) ≤ LT; and Theorem 3 provides regret bounds of the form Regα(T) ≤ 2[M 2(K-1)Le * (2136/Δ(min)) * lnT + (π 2/3 + 1)αMN](1/2) * (αLT)(1/2) for the distribution-dependent case and Regα(T) ≤ 2[93M√(N(K-1)T lnT) + (π 2/3 + 1)αMN](1/2) * (αLT)(1/2) for the distribution-independent case. The regret bounds simplify to α=1 for Bernoulli arms since the offline algorithms are optimal in that case.

The evaluation uses channel and mobility traces collected from a real testbed with 802.11ad APs and a client in a student hall, mapping SNR to throughput via the 802.11ad MCS-SNR table. The authors compare their algorithms (CBNA for non-adaptive probing and CBA for adaptive probing) against baselines including Optimal (exhaustive search), GNE (greedy probing and greedy play without exploration), RG (random probing and greedy play), and RR (random probing and random play). Results show that in the Bernoulli setting with a single context, CBA surpasses other algorithms after approximately 2000 time rounds and achieves the highest average throughput; in the multi-context Bernoulli setting, CBNA and CBA have lower cumulative regret than baselines; and in the general distribution setting, CBA consistently outperforms CBNA, demonstrating the importance of adaptive probing.

Improvements for AI systems

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

Improvement: Extend standard contextual bandit algorithms to incorporate a probing phase before action selection, where the AI can query a subset of arms to reduce uncertainty at a cost.

Capabilities:

  • The AI can decide whether to probe, which arms to probe, and in what order (adaptive probing) based on prior observations

  • It balances the information gain from probing against the throughput penalty (K−k)/K

  • It handles both non-adaptive (fixed probing set) and adaptive (sequential, outcome-dependent) probing strategies

Improvement: Implement the dynamic programming (Algorithm 3) and greedy approximation (Algorithm 2) for known reward distributions.

Improvement: Implement the UCB-based combinatorial contextual bandit (Algorithm 4) that learns reward distributions online while making probing and play decisions.

Improvement: Apply the framework to real-world mmWave WLAN scheduling with beamforming.

Improvement: Generalize the framework beyond wireless to any problem where probing reduces uncertainty before a decision.

Improvement: Provide rigorous theoretical guarantees for the AI's learning performance.

Improvement: Support discrete distributions with finite support (not just Bernoulli).

Improvement: Handle multiple contexts (e.g., different client locations) with shared structure.

Improvement: Include the specific algorithmic steps for real deployment.

Improvement: While the paper focuses on single-client, the framework can be extended.

Key Performance Gains:

  • Up to 30-40% higher throughput compared to random probing/play baselines

  • Significantly lower regret than greedy-without-exploration or random strategies

  • Optimal performance for Bernoulli link rates in offline settings

  • Sublinear regret guarantees in online settings with unknown distributions

Abstract

Existing solutions to network scheduling typically assume that the instantaneous link rates are completely known before a scheduling decision is made or consider a bandit setting where the accurate link quality is discovered only after it has been used for data transmission. In practice, the decision maker can obtain (relatively accurate) channel information, e.g., through beamforming in mmWave networks, right before data transmission. However, frequent beamforming incurs a formidable overhead in densely deployed mmWave WLANs. In this paper, we consider the important problem of throughput optimization with joint link probing and scheduling. The problem is challenging even when the link rate distributions are pre-known (the offline setting) due to the necessity of balancing the information gains from probing and the cost of reducing the data transmission opportunity. We develop an approximation algorithm with guaranteed performance when the probing decision is non-adaptive, and a dynamic programming based solution for the more challenging adaptive setting. We further extend our solutions to the online setting with unknown link rate distributions and develop a contextual-bandit based algorithm and derive its regret bound. Numerical results using data traces collected from real-world mmWave deployments demonstrate the efficiency of our solutions.

Related papers