A robot or phone that steers itself through a building by radio sees its position estimate jump around. Indoor signal strength is unreliable: walls reflect it, bodies absorb it, and a stationary device can see swings of 10 to 20 dBm. Reinforcement learning (RL) theory says little about this. Its strongest guarantees assume a linear model, meaning the next-state probabilities and rewards are fixed linear functions of a known feature vector, and they degrade by an extra term that grows with time once the world departs from that model. This proposal builds the missing link. Under a stated smoothness assumption, the departure from linearity that RF noise induces in a pose-based linear model should be governed mainly by the tail of the localization error, measured against the width of the spatial features, and much less by the median error that wireless papers usually report. If that holds, it gives an exchange rate between meters of localization error and the regret of a provably efficient learner. It also gives two design rules: pick the feature width to match the error tail, and gate out tail measurements before they reach the learner.
In two sentences: build linear RL features over the radio-estimated position, not over raw signal strength. Then show, by theory and by data-driven experiments, that the cost of radio instability in this design is set by how often the position estimate is badly wrong relative to the feature width, which tells you how wide to make the features and which measurements to throw away.
Core Claim
Provably Efficient Reinforcement Learning with Linear Function Approximation introduced LSVI-UCB, an optimistic least-squares value iteration method. It achieves $\tilde{O}(\sqrt{d^3H^3T})$ regret when transitions and rewards are linear in a $d$-dimensional feature map, where $H$ is the episode length and $T$ the total number of steps. Under an approximately linear MDP, whose transitions deviate by at most $\zeta$ in total variation, the paper adds a misspecification term that the file reports as $\tilde{O}(\zeta d H T\sqrt{K})$, with $K$ the number of episodes. That term grows linearly in $T$, so any non-vanishing $\zeta$ eventually dominates. Prior work leaves open what $\zeta$ actually is when the features come from noisy radio measurements.
Our claim has three parts. First, raw signal-strength vectors are a poor state representation, because multipath makes them non-monotone in position (Bing Li et al. show that converting RSSI to distance compounds errors). We therefore place smooth radial features of width $\sigma$ over the estimated pose $\hat{x} = x + e$, where $x$ is the true pose and $e$ the localization error. Second, under the explicit assumption that the motion dynamics are linear in these features evaluated at the true pose, we conjecture a bound of the form
$$\zeta(\sigma) \;\lesssim\; \Pr\big(\|e\| > c\,\sigma\big) \;+\; \frac{L}{\sigma}\,\mathbb{E}\big[\|e\|\,;\,\|e\|\le c\sigma\big],$$
where $L$ is a Lipschitz constant of the features in units of $\sigma$ and $c$ is a constant. The first term is a tail mass: errors larger than the feature width put the agent in the wrong part of feature space entirely. The second term is a smooth bias from small errors. Third, feature dimension scales roughly as $d \propto A/\sigma^2$ for a floor area $A$, so shrinking $\sigma$ inflates the $\sqrt{d^3}$ term while widening it raises $\zeta$. This yields an optimal width that depends on the error tail. It also predicts that a clipping gate, which discards estimates implausible under the motion model, reduces $\zeta$ by removing the tail term.
Proving this bound is part of the program. The outcome is not assumed; the conjecture may fail, and the experiments are designed to show whether it does. Even so, the claim makes a sharp, falsifiable prediction. Two localizers with equal median error but different 99th-percentile error should produce clearly different regret curves, and the one with the lighter tail should win.
How This Relates to Prior Work
No paper in the file joins the two directions. On the RL side, LSVI-UCB supplies both the learner and the misspecification penalty we try to make concrete. Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration supplies FRANCIS, a reward-free exploration algorithm whose cost depends on an explorability coefficient $\nu$. We reuse FRANCIS for an autonomous site-survey task and measure $\nu$ empirically, which that paper does only in synthetic settings. On Reward-Free Reinforcement Learning with Linear Function Approximation constrains the design: it proves that assuming only the optimal value is linear forces $\Omega(2^H)$ samples, while linear transitions allow polynomial cost. This is why we put the linear structure in the motion model over pose, not in a value-only fit over radio readings. Going Beyond Linear RL offers neural alternatives, but its strongest polynomial guarantees need deterministic transitions, which radio-driven state estimates do not provide. We therefore treat it as a contrasting reference rather than a method to reuse.
The gating idea draws on two sources. Clipped Q-Learning shows that clipping the Bellman backup at a threshold acts as a robust operator that limits error propagation. PEOPLEx fuses inertial odometry with BLE, Wi-Fi and UWB and treats radio loop closures within a 2-meter "trust radius" as costless, which brings RMSE from 2.88 m down to 1.05 m. Both are heuristics for discarding unreliable extremes. Our contribution is to tie the gate threshold to the $\zeta$ bound, so the threshold is chosen for its effect on regret rather than tuned by eye.
On the wireless side, the localizers motivate the tail-versus-median question. Attending to Routers Aids Indoor Wireless Localization reduces median error by 28.7% but 99th-percentile error by 39.4% on DLoc. Its improvement is therefore larger in the tail. If our claim is right, that tail improvement is the part that matters for a downstream learner. CAE-CNNLoc and the UJIIndoorLoc study (On the Use and Construction of Wi-Fi Fingerprint Databases) show how fingerprint error grows under added noise and missing access-point readings. These papers supply the error distributions we feed through the bound. None of them studies sequential decisions.
Research Program
The theoretical part has three steps. We will state the "linear in true pose" assumption precisely and prove the bound above, or a corrected version of it, for radial and cell-indicator features. Taking the reported misspecification term at face value, we will derive the width $\sigma^\star$ that minimizes total regret as a function of the error distribution's tail. We will then show that a gate rejecting estimates whose implied displacement exceeds a threshold $\tau$ removes the tail term, at the cost of missing observations, which we treat as a state-holding transition.
The empirical part builds data-driven simulators in which the true pose is known, so that $\zeta$ can be measured directly. We do this by fitting least-squares transition models in estimated-pose features and computing total-variation residuals against held-out transitions.
The first simulator comes from the UTIL dataset (UTIL). It contains about 150 minutes of quadrotor flight with UWB time-difference-of-arrival ranging, IMU, and motion-capture ground truth, including a cluttered constellation in which conventional positioning "deteriorated significantly." From it we fit location- and obstruction-conditioned error distributions, and the agent moves on a discretized arena.
The second simulator comes from UJIIndoorLoc. We place an agent on a graph of surveyed reference points, and each visit resamples a real fingerprint from that point. A fixed localizer turns the fingerprint into an estimate, so the localization error is the real empirical error rather than a synthetic one.
Two tasks run in both simulators. The first is goal-reaching with reward defined on the true pose, under unknown blocked edges such as closed doors, which forces exploration. The second is reward-free surveying with FRANCIS, followed by evaluation on held-out goal rewards.
Baselines
The naive reference is LSVI-UCB with raw signal-strength features, meaning the RSSI vector, normalized with the −105 dBm missing-value fill that the UJIIndoorLoc study found better than the default. It matches what a practitioner would try first. It receives the same episodes, regularization grid, and bonus-scale grid as our method. Beating it means lower cumulative regret at every budget, with non-overlapping 95% intervals over at least 20 seeds.
The strongest learned competitor is a deep Q-network on the same raw radio inputs. It has no guarantees but can in principle learn the nonlinearity itself. It gets matched environment steps and a hyperparameter search of equal trial count to ours. Our method beats it if it reaches lower regret within a fixed budget of $K$ episodes. A tie at the asymptote is acceptable, provided our method holds a sample-efficiency advantage early, because the claim concerns finite budgets.
The strongest non-learning competitor is a separation pipeline. It localizes with the best available estimator and plans a shortest path by certainty equivalence, re-planning when an edge proves blocked. For UJIIndoorLoc the localizer is CAE-CNNLoc, which reports 9.5 m mean positioning error with about 99% building and over 90% floor accuracy. For UTIL we use the dataset's conventional TDOA positioning, reported at about 10 cm error without obstacles. For our own LSVI-UCB variants on any radio benchmark, we found no reported result on Lacuna. An oracle planner with true pose and a known map serves as the upper reference.
Three ablations isolate the key ingredient. The first runs a fixed $\sigma$ against the tail-matched $\sigma^\star$. The second turns the gate on and off. The third and most decisive is the median-matched comparison: we hold the localizer fixed, then reshape its error distribution by resampling so that two versions share a median but differ in the 99th percentile, or share a 99th percentile but differ in median.
Why not just…?
Why not just localize first and then plan with a standard planner? This is the real threat, and we run it as a baseline. When the map is known and only position is uncertain, it may simply win. Our setting adds unknown dynamics, namely blocked passages that are discovered only by acting, and that is where exploration with confidence bonuses should matter. The separation pipeline also has no principled response to occasional wild estimates. If it matches LSVI-UCB with tail gating on the blocked-door tasks, we will report that the theory's practical value lies in choosing $\sigma$ and $\tau$, not in the learner itself.
Why not just use deep RL on raw signals and skip the theory? Deep RL can absorb the nonlinearity, but it carries no finite-sample guarantee, and Touati et al. document divergence when bootstrapping is combined with function approximation off-policy. The deep Q-network baseline tests this directly. Note that even if it matches us in final performance, it cannot answer the question of which localizer improvement to buy.
Why not just use a fine tabular grid, which is exactly a linear MDP? The tabular grid is the $\sigma \to 0$ end of our width sweep. The bound predicts it performs worst when error tails are wide, because almost every error then falls outside the cell. It also inflates $d$. The sweep shows directly whether the predicted interior optimum exists.
Why not just a linear contextual bandit? Moving changes the agent's position and therefore its future signals, so single-step bandits ignore exactly the path dependence that, as Jin et al. note, separates $H > 1$ from $H = 1$. We include LinUCB with a one-step lookahead only as a sanity floor.
Decisive Checks
The program succeeds if three things hold across both simulators. First, empirical $\zeta$ tracks the predicted tail-plus-bias expression, measured as rank correlation across widths and error reshapings, better than it tracks median error alone. Second, regret is minimized near the predicted $\sigma^\star$. Third, in the median-matched ablation, the lighter-tailed localizer yields clearly lower regret while the median-only variant does not. The program fails if regret ordering follows median error, or if the gate does not reduce measured $\zeta$. Either outcome would show that RF instability does not reach linear RL mainly through the error tail, and that is worth knowing too. For FRANCIS surveying, we additionally report the empirical explorability coefficient in UTIL's cluttered constellation against its obstacle-free ones, which gives the first measurement of $\nu$ in a physical radio environment.
References
- Provably efficient reinforcement learning with linear function approximation
- A Robust Wireless Sensor Network Localization Algorithm in Mixed LOS/NLOS Scenario
- Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
- On Reward-Free Reinforcement Learning with Linear Function Approximation
- Going Beyond Linear RL: Sample Efficient Neural Function Approximation
- Clipped Q-Learning: Your Value Clipping Is Secretly A Robust Operator
- PEOPLEx: PEdestrian Opportunistic Positioning LEveraging IMU, UWB, BLE and WiFi
- Attending to Routers Aids Indoor Wireless Localization
- CAE-CNNLoc: An Edge-based WiFi Fingerprinting Indoor Localization Using Convolutional Neural Network and Convolutional Auto-Encoder
- On the Use and Construction of Wi-Fi Fingerprint Databases for Large-Scale Multi-Building and Multi-Floor Indoor Localization: A Case Study of the UJIIndoorLoc Database
- UTIL: An ultra-wideband time-difference-of-arrival indoor localization dataset
- Convergent TREE BACKUP and RETRACE with Function Approximation