Every Transmitter Is a Goal: Hindsight Relabeling for Sparse-Reward Wireless Indoor Navigation

A robot asked to find a radio transmitter inside a building faces two problems at once. The signal is a poor compass: walls and floors absorb it, and reflections off concrete and metal (multipath) produce false peaks. The reward is also sparse, because the agent learns nothing until it actually arrives. Current reinforcement learning (RL) systems for this task get a dense learning signal by hand-writing physics. One line of work runs a ray-traced "digital twin" of the building and adds reward terms for moving toward higher signal-to-noise ratio, following the angle of arrival, and changing from non-line-of-sight to line-of-sight. The other encodes the same intuitions as symbolic programs. Both help a great deal, but they depend on an accurate propagation simulator and on reward weights tuned by experts. They also assume that signal strength rises steadily as the agent gets closer, which is exactly what multipath breaks.

We propose a different source of dense feedback that requires no physics model of the reward. A real building contains many transmitters (WiFi access points, beacons), and any trajectory that fails to reach its assigned transmitter usually passes close to some other one. Borrowing the idea of hindsight relabeling from goal-conditioned RL, we relabel each failed episode as a success for whichever transmitter the agent actually reached, identified only by that transmitter's own signal. From these relabeled episodes we learn a goal-conditioned estimate of "steps remaining to the transmitter." We then use it as a shaping potential, which by construction cannot change which policy is optimal. The estimate measures travel distance around walls, not signal strength, so it does not assume that signal strength changes monotonically along the path.

Core Claim

In wireless indoor navigation, the environment's many transmitters supply free goals, and so free supervision. We make two claims. First, relabeling arrival events across transmitters removes the cold-start problem of sparse reward: nearly every episode yields at least one success. Second, a temporal-distance critic trained on these successes gives a dense, policy-invariant shaping signal. We expect this signal to reach the path efficiency of physics-engineered rewards on the static Gibson wireless navigation maps. We expect it to degrade less than those rewards when the attenuation pattern changes, because it never encodes a fixed model of how signal strength relates to distance.

The closest work shows why this is not already done. Digital Twin-Enhanced Wireless Indoor Navigation (PIRL) densifies reward with three hand-weighted terms computed from mmWave ray tracing. Reinforcement Learning with Physics-Informed Symbolic Program Priors (PiPRL) writes propagation priors as programs in a domain-specific language (RLang) that constrain actions and reweight rewards. Both motivate this proposal, since they show that sparse arrival reward alone (their NPRL baseline) gives long, erratic paths. Both also constrain it: whatever we build must match their path lengths to be worth using. Our method replaces their hand-built reward with one learned from arrival events.

Research Program

The environment follows the wireless indoor navigation setup on Gibson used by both papers above. Observations are RGB images, signal-to-noise ratio, and angle-of-arrival features for a designated target transmitter. We extend each map to host $K$ transmitters, roughly 8 to 16 per map, placed at plausible access-point locations. The agent observes signal features for all of them and is told which one is the target by an index. The propagation simulator still generates observations. It is not used to compute reward. The only reward event is "arrival," meaning the agent is within a fixed radius of a transmitter. In simulation, arrival is detected from ground truth. For a later real deployment it would be detected by a short-range proximity cue such as UWB ranging or a very high received signal level.

Training has three coupled parts. The first is multi-transmitter hindsight relabeling. An episode assigned to transmitter $k$ that arrives at transmitter $j$ is stored a second time as a success for $j$. Arrival also triggers relabeling at intermediate steps whenever the path passes within the arrival radius of any transmitter. This is the RF counterpart of the hindsight instruction relabeling in Language as an Abstraction for Hierarchical Deep Reinforcement Learning, which relabels unintended outcomes as achieved instructions but needs a separate ground-truth verifier. Here the verifier is the arrival event itself.

The second part is a temporal-distance critic $D_\theta(o_t, j)$. It is trained on relabeled segments to regress the number of steps between observation $o_t$ and arrival at transmitter $j$, using a Bellman-style target so that it learns shortest rather than average distances. The third part is shaping. The policy, trained with proximal policy optimization (PPO) as in the baselines, receives the sparse arrival reward plus a potential-based term:

$$F(o_t, o_{t+1}) = \gamma\,\Phi(o_{t+1}) - \Phi(o_t), \qquad \Phi(o) = -D_\theta(o, k),$$

where $\gamma$ is the discount factor and $k$ is the current target. Potential-based shaping leaves the optimal policy unchanged. This matters because reward hacking is one of the main failure modes of dense rewards.

This design responds to three weaknesses in the literature. Self-Supervised Online Reward Shaping in Sparse-Reward Environments (SORS) learns rewards by ranking trajectories. Its ranking has nothing to start from if no trajectory ever succeeds, and multi-transmitter relabeling supplies those early successes. A Generalist Pair-wise Progress Critic Model for Vision-Language-Action Robots (VLAC) reports that its progress critic fails when the task requires backtracking, because it assumes progress rises over time. Our critic predicts remaining steps to a goal, so a detour around a concrete wall correctly registers as being closer, even when signal strength drops along the way. That drop is exactly the case that PIRL's link-state monotonicity term penalizes.

Baselines

The naive reference point is NPRL, PPO trained on the sparse arrival reward with the same observations and network. It measures how much any densification helps. In the file it is reported with normalized path length (NPL, path length divided by shortest path) of 5.14 ± 1.21 on Map T under 2+ NLOS walls (Digital Twin-Enhanced Wireless Indoor Navigation) and 4.96 ± 1.37 on Map P under 2+ NLOS (Reinforcement Learning with Physics-Informed Symbolic Program Priors).

The strongest existing methods are PIRL and PiPRL, since they target exactly this task and benchmark. PIRL reports NPL 2.82 ± 0.04 on Map T (2+ NLOS) and a success rate of 1.0 in most scenarios. PiPRL reports NPL 2.13 ± 0.04 on Map P (2+ NLOS) and a training-time reduction of over 26% in GPU hours relative to NPRL. We will reimplement both on our multi-transmitter maps. They will get the same PPO backbone, the same perception stack, and the same environment-step budget, and each will receive an equal hyperparameter search over its reward weights or program parameters. We will also report their published numbers on the original single-transmitter split for calibration.

On static maps, beating them means matching their NPL within their reported variance and success rate without a hand-built reward. On perturbed maps it means a statistically significantly lower NPL and a higher success rate.

A privileged oracle, standard geometric hindsight relabeling with ground-truth target coordinates, bounds what goal relabeling can achieve when positions are known. Two ablations isolate the key ingredients. The first is relabeling without shaping, which tests whether the critic adds anything beyond extra successes. The second shapes with a learned critic trained only on the agent's own target episodes, with no cross-transmitter relabeling, which tests whether the free goals are what break the cold start. A further control shapes with raw signal-to-noise gain. It checks that the learned critic outperforms the obvious signal-based potential in NLOS rooms.

Why not just…?

Why not just use PIRL's physics rewards, since they already work? On static Gibson meshes they may well remain the best, and that is a real threat to the static result. They need a ray-traced digital twin to compute reward and weights tuned against that twin. The source paper notes that the weighting is sensitive and that dynamic attenuation is untested. Our claim is narrower: comparable static performance from arrival events alone, and better robustness when the attenuation pattern shifts. Experiment 2 below settles the second part directly. If PIRL holds up under perturbation as well as our method does, the robustness claim fails.

Why not just follow the signal greedily, climbing signal-to-noise or reversing the angle of arrival? PiPRL already uses reverse angle-of-arrival as a direct program policy and still needs RL on top of it, which suggests the greedy rule alone falls short in multi-wall NLOS. We include a pure greedy controller and the raw signal-to-noise potential as baselines. We expect both to stall at multipath peaks behind walls, and the NLOS breakdown will show whether they do.

Why not just build a fingerprint map offline and plan on it? A static radio map and roadmap cannot adapt when layouts or crowds change. Long-Range Indoor Navigation With PRM-RL shows that roadmaps with simple straight-line connections reach 12.4% success on dense floorplans. Its RL-validated roadmap reaches 91.7%, but it requires expensive Monte Carlo rollouts to rebuild. Fingerprint classifiers also struggle to tell rooms apart, reaching 71% space ID accuracy on UJIIndoorLoc in Machine Learning-Based WiFi Indoor Localization with FasterKAN. We do not claim to beat mapping when a fresh survey is available. We will include a nearest-neighbor fingerprint-plus-planner baseline built on the unperturbed map and tested on the perturbed one.

Why not just use SORS-style learned ranking? Ranking needs at least some successful trajectories to compare, and in multi-wall NLOS episodes early in training such successes are rare. We run SORS with the same budget and plot success rate over training. The cold-start comparison is the direct test.

Proposed Experiments

Experiment 1 uses the Gibson wireless navigation split of 15 training maps (A–O) and 6 unseen test maps (P–U), stratified into LOS, 1-NLOS, and 2+-NLOS targets. We report success rate, NPL with standard deviation over seeds, and environment steps and GPU hours to reach 90% success. The first decisive check is whether relabeling plus shaping reaches PIRL's reported NPL range on 2+-NLOS test maps without the physics reward. The second is whether the no-relabeling ablation fails to escape cold start there.

Experiment 2 tests robustness to non-stationary attenuation. At test time we insert moving human-sized attenuating bodies and door open/close changes, re-simulating propagation for the affected paths. The motivation comes from crowd effects documented in Large-Scale Localization Datasets in Crowded Indoor Spaces. The decisive check is the relative NPL degradation of our method versus PIRL and PiPRL.

Experiment 3 tests scale on a subset of multi-floor Habitat-Matterport 3D buildings. Here long horizons make sparse reward hardest, and PRM-RL's 8.5% end-to-end RL success rate shows how badly flat RL can fail at building scale. We measure whether relabeling across more transmitters increases the gain, as the free-goal argument predicts.

A final diagnostic tests whether the critic behaves as intended. We correlate $D_\theta$ with ground-truth geodesic distance, and separately with signal-to-noise ratio, in NLOS rooms. The critic should track geodesic distance, not signal strength. If it tracks signal strength instead, the method has learned the same monotonic assumption it was meant to avoid.