Which Access Points to Trust Today: Best-of-Both-Worlds Selection for Drifting Radio Maps

Indoor positioning systems locate a phone or robot by comparing the radio signals it hears, such as Wi-Fi signal strength or 5G channel responses, against a stored map of what each location "sounds like." That map goes stale. Doors open, crowds pass, machinery moves, and access points get recalibrated or relocated. Some of these changes are slow and benign. Others are abrupt, localized, and transient. Today, systems usually pick which access points to rely on once, offline, using static statistics such as mutual information or signal variance. They then either retrain the whole model or hope that the remaining signals stay informative.

We propose to treat the choice of which $m$ access points to query, out of $K$ available, as an online learning problem. The learner sees a label-free reliability score only for the access points it actually used. It updates its choice with a best-of-both-worlds algorithm, meaning an algorithm that provably settles quickly on the right subset when conditions are stable, while keeping a worst-case guarantee when conditions are erratic, all without being told which regime it is in. The question is whether this machinery buys anything over simple sliding-window heuristics on real drifting radio data. We think it does in one specific case: when disruptions are bursty, a few access points at a time. Greedy rules then chase noise, and drift detectors can be fooled.

Core Claim

Under a hard query budget (energy, ranging time, or edge compute), we claim three things. First, access-point selection can be cast as a combinatorial semi-bandit. This is a repeated game in which the learner picks a subset of $m$ items and observes a loss only for those items. Second, a cheap per-access-point loss that needs no ground-truth position can be built from the tracking filter's own prediction. Third, running a best-of-both-worlds semi-bandit learner on this loss gives lower tail positioning error than three alternatives on temporally drifting benchmarks: static offline selection, greedy sliding-window selection, and purely adversarial or purely stochastic bandit learners.

The new parts are the label-free loss, the budgeted-selection formulation for localization, and the empirical test of whether "corrupted stochastic" is the right model of radio drift. The bandit algorithm itself is reused.

Relation to Prior Work

The method comes from the combinatorial best-of-both-worlds literature. Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits selects $m$-sets out of $K$ items. It uses a separable entropy regularizer whose projection reduces to one-dimensional bisection, and it guarantees $\widetilde{O}(\sqrt{T})$ regret against an adversary and $\widetilde{O}(\ln T)$ regret in stochastic settings with corruption. We reuse that solver unchanged. Its experiments are synthetic and linear, and the corrupted-stochastic regime it analyses has never been checked against physical signal drift.

The broader self-bounding approach motivates our choice to avoid explicit switching. In these analyses, regret is bounded by a function of the algorithm's own mistakes, so the bound tightens automatically when the environment is benign. Examples are Revisiting Online Submodular Minimization: Gap-Dependent Regret Bounds, Best of Both Worlds and Adversarial Robustness, Tsallis-entropy analyses such as A Best-of-Both-Worlds Proof for Tsallis-INF without Fenchel Conjugates, and Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?. The survey Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems documents the underlying trade-off: algorithms tuned for stationary losses break under adversarial sequences, and the reverse holds too.

Three localization papers motivate the gap.

Two works on continual model updating constrain how we position the proposal. Mean-teacher-based semi-supervised learning framework for scalable indoor localization using Wi-Fi RSSI fingerprinting updates the regression model online from unlabeled data. 5G-DIL: Domain Incremental Learning with Similarity-Aware Sampling for Dynamic 5G Indoor Localization adapts with replay and regularization, and degrades when physical shifts exceed 0.6 m. Both change the model, whereas we change which inputs it sees. They are complementary, so we test our selector on top of them rather than instead of them.

Research Program

At each time step $t$, the device holds a tracking estimate from a particle filter, of the kind used by the differential radio-map work. The filter's motion model gives a predicted position $\hat{x}_{t\mid t-1}$ before the current measurement arrives. The learner picks a set $S_t$ of $m$ access points, queries them, and charges each selected access point $i$ the loss

$$\ell_{t,i} = \min\Big(1,\ \big|r_{t,i} - \mu_i(\hat{x}_{t\mid t-1})\big| / \sigma_i\Big).$$

Here $r_{t,i}$ is the observed signal from access point $i$, $\mu_i(x)$ is the radio map's predicted signal at location $x$, and $\sigma_i$ is that access point's map noise scale. The loss is clipped to $[0,1]$ so the bandit's assumptions hold.

The loss uses the motion-model prediction, not the posterior. That makes it computable without labels and makes each access point's loss independent of which other access points were chosen in the same round. It is still not fully oblivious, because past selections shape $\hat{x}$. We will measure how much this matters by comparing against an oracle loss computed from the true position, which is available offline on every benchmark we use.

The semi-bandit learner keeps a distribution over $m$-subsets. It updates with the separable-entropy follow-the-regularized-leader solver from the combinatorial best-of-both-worlds paper, using importance-weighted loss estimates for unobserved access points. We will compare two regularizers. The paper's Shannon-entropy variant is the default. A 1/2-Tsallis variant is motivated by its steeper behaviour near the edges of the probability simplex, which lets it commit faster to a good subset. The context for the contextual variant is the coarse region of $\hat{x}$, because which access points are reliable is location-dependent.

The modelling assumption we must test, not assume, is that radio drift looks like "stationary per-access-point reliability plus a bounded corruption budget." Transient crowd and door effects fit this assumption. Permanent changes, such as a relocated access point, break it, because they change the best subset itself. We therefore add one variant that restarts the learner on a fixed doubling schedule, and we report regret against both the best fixed subset and the best subset recomputed per window.

Baselines

Do nothing. The naive reference is the same particle-filter localizer using all $K$ access points with no budget. It gives the accuracy ceiling at full cost. Its budgeted counterpart uses a uniformly random $m$-subset each step, which gives the floor.

Strongest existing method. The strongest existing selection method is static offline selection: LLDE-APS's mutual-information subset and the variance filter from the UJIIndoorLoc study, both computed once on the training period. LLDE-APS reports 73.7% of errors within 2 m on its own office testbed, against 57.5% for weighted k-nearest neighbours. No reported result was found on Lacuna for budgeted access-point selection on XJTLU or UJIIndoorLoc, so we re-run it ourselves. Every method receives the same training-period data, the same radio map and particle filter, and the same budget $m$. Each gets the same hyperparameter search budget, about 20 configurations, tuned on the first week of XJTLU and then frozen.

Strongest adaptive heuristic. The most dangerous competitor is a sliding-window greedy rule: rank access points by mean loss over the last $w$ steps, take the top $m$, and add ε-random exploration, with $w$ and ε tuned on the same budget.

Pure-regime bandits. We also run a combinatorial upper-confidence-bound learner, which suits only the stationary regime, and a combinatorial exponential-weights learner with a fixed rate, which suits only the adversarial regime.

Detector-triggered reselection. A Page–Hinkley drift detector on per-access-point loss triggers offline reselection whenever it fires.

Beating the baselines. Our method beats the baselines if, at equal $m$, its 90th-percentile and maximum 2D error are lower than every adaptive baseline over the full 44-day stream and under every injected-disruption protocol, with confidence intervals from bootstrap resampling over days. It must also be no worse than the best static selection on undisturbed periods.

Ablations. Ablations isolate the two key ingredients. First, replacing the label-free loss with the oracle loss measures how much the proxy costs. Second, replacing the self-tuning learning rate with a fixed one, while keeping the regularizer and solver, tests whether the regime adaptivity itself matters.

Why not just…?

Why not just use all access points with a robust estimator? If querying is free, this may well win, and we say so. Wi-Fi scans often return all access points at once. The proposal therefore targets budgeted settings: the energy and sensing-time constraint that motivated LLDE-APS, and ranging-based systems like the 6-access-point 5G testbed, where each query has a cost. We report the full-$K$ robust estimator as the ceiling, and we report the accuracy-versus-$m$ curve so readers can see where the budget actually binds.

Why not just a sliding window over recent residuals? This is the real threat. Our expectation is that greedy windows face a dilemma. A short window flips to whichever access point had a lucky stretch during bursty crowd interference. A long window is slow to drop an access point after a real disruption. The best-of-both-worlds learner needs no window length. The injected-burst experiment below decides this. If tuned greedy matches us there, the honest conclusion is that the theory adds nothing practical in this domain, and we will report it that way.

Why not detect drift and reselect? The bandit literature argues that explicit regime detection can be exploited: losses that look stationary for a long stretch lull a detector before a shift, as discussed in Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems. Physical environments are not adversaries, though, so this argument may not transfer. We test it directly. The detector baseline is tuned on the same budget and scored on recovery time after disruption and on its false-trigger rate during quiet nights.

Why not just update the model, as mean-teacher or 5G-DIL do? Model updating repairs the map. Selection decides which parts of the map to trust while the repair catches up. We will run our selector on top of the mean-teacher localizer to test whether the gains add.

Proposed Experiments

XJTLU stream. The main benchmark is the XJTLU 44-day database: 219 access points and 28 reference points, replayed in time order. Because all access points are logged, revealing only the selected $m$ gives an exact semi-bandit replay. Budgets are $m \in \{5, 10, 20\}$. As a reference point from the file, the mean-teacher method reports up to 49.227% improvement in maximum 2D error on this data. We will measure our gain both with and without that model underneath.

UJIIndoorLoc. The second benchmark is UJIIndoorLoc, ordered by timestamp. Its months-later validation set provides a natural long-gap shift, and its many missing-access-point records test how the selector handles missing beacons.

5G SDR testbed. If the data can be obtained, the 5G SDR testbed of 5G-DIL tests the ranging-cost regime with 6 access points and $m \in \{2, 3, 4\}$. Its realistic sites with moving vehicles supply genuine non-uniform disruption. 5G-DIL reports 0.261 m MAE there, which serves as the full-information model-update reference.

Decisive checks. Three checks decide the proposal, all using controlled perturbations injected into held-out XJTLU days.

The first injects bursty, non-uniform attenuation on random small groups of access points. Pairwise differences do not cancel this kind of attenuation. The check is whether we beat tuned sliding-window greedy on tail error, and whether the learner's measured cumulative loss stays close to the corrupted-stochastic shape: logarithmic growth plus a term proportional to the corruption budget.

The second is a long quiet period. The check is whether we lock in as fast as the upper-confidence-bound learner while the fixed-rate exponential-weights learner keeps exploring.

The third is a permanent relocation of a high-value access point. The check is how the restart variant compares with the plain learner in regret against the per-window oracle. This test exposes the stated limitation of the approach, rather than hiding it.

A last diagnostic compares the label-free loss with the oracle loss. If the proxy's selections diverge sharply from the oracle's under disruption, the bottleneck is the feedback signal, not the learner, and that finding redirects the work.