Picture a team of drones, or a set of steerable cameras, that must spread out over a large scene and each lock onto a different tiny target: a 6-pixel car, a 4-pixel boat. They cannot talk to one another. If two of them aim at the same spot they "collide" and both waste the step. The math of decentralized bandits (learning by trial and error, with several players competing for the same options) already says how such a team can match a perfectly coordinated controller. The catch is an assumption: the reward must change gradually as an agent moves its aim, with a known bound on how fast it can change. Tiny-object vision breaks that assumption. The standard overlap score, intersection-over-union (IoU), falls from 0.53 to 0.06 when a 6×6 box shifts by one pixel diagonally. Once boxes stop overlapping, it gives no signal at all.
This note argues that the bound on how fast the reward changes is something the designer chooses through the localization metric, not a fixed property of the world. If agents score what they see with a Gaussian Wasserstein similarity, which treats each box as a blurred blob and compares blobs, then that bound is exactly one over the blur constant, whatever the object's size. The central idea is to shrink that blur constant in step with the agents' coarse-to-fine refinement and zoom. The hypothesis is that regret then no longer grows as targets get smaller. A fixed blur, IoU, or a grid cannot achieve this in dense scenes.
Core Claim
The closest existing work, Multi-Agent Lipschitz Bandits, solves decentralized search over a continuous space without communication. Its protocol has four stages: coarse random exploration, a "local peek" that zooms into promising regions, a musical-chairs seating step, and a single-agent continuous bandit inside each agent's cell. It reaches regret $\tilde{O}(T^{(d+1)/(d+2)})$ with a coordination cost that does not grow with the horizon. It assumes, however, an abstract scalar reward that is Lipschitz (changes at most $L$ per unit of movement) with a known $L$. The tiny-object literature shows that IoU-based feedback is the opposite: a step function with cliffs (A Normalized Gaussian Wasserstein Distance for Tiny Object Detection; Detecting tiny objects in aerial images: A normalized Wasserstein distance and a new benchmark).
The obvious bridge is to plug the normalized Wasserstein distance (NWD) in as the reward. That fixes one thing and breaks another. A single blur constant $C$ cannot serve both coarse discovery and final localization. The claim here is that the protocol's refinement stages are exactly where to anneal $C$. Doing so turns "known $L$" from an assumption into a design decision. It should also make regret measured against the true, non-smooth success criterion independent of target size.
Concretely, agent $i$ aims at location $x$ with footprint scale $c$. It runs a fixed tiny-object detector on the resulting crop and scores the detections $b_j$ (with confidences $q_j \in [0,1]$) as
$$r_c(x) = \max_j \; q_j \exp\!\Big(-\tfrac{W_2(\mathcal{N}_x, \mathcal{N}_{b_j})}{c}\Big),$$
where $\mathcal{N}_x$ is a Gaussian centred at the aim point and $W_2$ is the 2-Wasserstein distance between Gaussians. Because $W_2$ is a true distance, moving the aim by $\delta$ changes it by at most $\delta$. The exponential has slope at most $1/c$, and a maximum of such functions keeps the bound. So $r_c$ is $(1/c)$-Lipschitz with a constant the agents know exactly, and the reward is computed from detector output rather than ground truth.
The size-independence claim rests on a rescaling argument. Continuous-bandit regret on a cell of width $w$ with Lipschitz constant $L$ depends on the space only through the product $Lw$. The coarse-to-fine protocol shrinks $w$ at each stage. If $c$ shrinks proportionally, $Lw$ stays constant. The final stage then pays the same price whether targets are 48 pixels or 4 pixels, while earlier stages remain a horizon-independent cost.
Why a Single Blur Fails
The failure has two sides, and each connects to a known pathology.
If $c$ is small, around the size of a target, the reward is essentially zero except within a few pixels of a target. Coarse identification then becomes needle-in-a-haystack search, costing roughly $(W/c)^2$ probes for a scene of width $W$. This is the center-versus-maximum pathology of the Lipschitz bandit paper made extreme: sampling a cell's centre misses a sharp peak near its edge.
If $c$ is large, the reward is smooth, but its peaks are flat over a radius of about $c$. An agent can then settle anywhere within about $c$ of the target and still score nearly the maximum, which fails a pixel-level hit test. Worse, in dense scenes such as VisDrone crowds, two targets closer than roughly $c$ merge into one peak between them. Two agents are then drawn to the same non-target point and collide.
Annealing addresses both sides. A large $c$ with a wide footprint finds regions. A shrinking $c$ with a narrow footprint separates targets that sit close together. The physical zoom mirrors this schedule. A wide footprint at a fixed pixel budget means low resolution and poor tiny-object detection, which is the altitude-versus-resolution trade-off observed in Decentralized multi-agent active search for sparse signals. Tying $c$ to the footprint makes the blur honest: agents do not claim sharper localization than their current resolution supports.
Research Program
The work has three parts.
Theory. We will extend the analysis of Multi-Agent Lipschitz Bandits to a staged reward whose Lipschitz constant grows as cells shrink. Regret will be measured not against the surrogate $r_c$ but against a hit-based objective: an agent earns a target's value only while its aim lies within a size-proportional radius of that target. That objective is not Lipschitz at all. We will prove an upper bound whose final-stage term depends on the ratio $c_k/w_k$ between blur and cell width rather than on target size. We will also prove two lower-bound-style statements, one for each failure mode. First, any fixed small $c$ pays a discovery cost growing like $(W/s)^2$ for target size $s$. Second, any fixed large $c$ incurs linear regret on a family of two-target instances with separation below $c$. The Lipschitz paper's lower bound constrains us: we do not expect to beat $T^{(d+1)/(d+2)}$ in $T$, only to remove the dependence on target size.
Collisions. We keep the proximity collision model from that paper: agents whose aims fall within $r_c$ of each other both get zero reward. Seating uses its musical-chairs step unchanged. This isolates the reward metric as the only new ingredient.
Environment. We will build a replay environment from real imagery. Each large image from AI-TOD-v2 (mean object size 12.7 px), VisDrone, and frames from VISO (12,000×5,000 px satellite video with targets down to 4×4 px) becomes a scene. At each step, each of $N$ agents chooses an aim point and footprint. The environment downsamples that crop to a fixed pixel budget and runs one fixed detector: DetectoRS trained with NWD ranking-based assignment, as in Detecting tiny objects in aerial images. The agent receives $r_c$. Detector false positives and misses therefore supply realistic, non-Gaussian reward noise. Ground truth is used only for scoring.
Baselines
Naive references. The "do nothing" reference is independent agents, each running a single-agent continuous bandit on its own reward with no coordination. Evidence in Multi-Agent Lipschitz Bandits and Cooperative Multi-player Bandit Optimization indicates that such agents pile onto the best peaks and suffer linear regret. A second floor is uniform random aiming at the finest footprint.
Strongest existing decentralized method. This is the four-stage protocol of Multi-Agent Lipschitz Bandits, run as published with an IoU-based reward: the best IoU between the agent's aim box and any detection. It is the strongest competitor because it is the only decentralized method in the file with optimal regret over continuous space and collisions. Its assumed $L$ will be tuned on held-out scenes with the same budget we give our schedule. No reported result was found on Lacuna for its simulation regret values, so the comparison is entirely within our environment.
Grid baselines. We will overlay a grid and run Multi-Player Bandits - a Musical Chairs Approach and SIC-MMAB, with cell size swept.
Active-search baseline. We will run a decentralized Thompson-sampling searcher in the style of Multi-Agent Active Search using Detection and Location Uncertainty, with the collision penalty switched on.
Key ablation. The protocol is kept identical, but $r_c$ uses one fixed $c$, swept over a grid, with the best $c$ selected per dataset in hindsight. This ablation isolates annealing.
Centralized upper reference. Detection on the full image with Cascaded Zoom-in Detector for High Resolution Aerial Images, followed by optimal assignment of agents to targets. On the underlying detectors, the file reports 24.7 AP for DetectoRS with NWD ranking-based assignment on AI-TOD-v2 (Detecting tiny objects in aerial images), and 33.22 mAP for Cascaded Zoom-in on the VisDrone validation set (Cascaded Zoom-in Detector). These numbers bound which localizations are achievable at all.
Fairness. All methods get the same detector, the same number of detector calls per agent per step, the same pixel budget, and the same hyperparameter tuning budget on held-out scenes.
What beating the baselines means. The proposal succeeds if annealing achieves lower cumulative hit-based regret than the IoU-reward protocol at every target-size bin, and lower regret than the best fixed-$c$ ablation in dense scenes. It should also approach the centralized reference's steady-state hit rate without any communication.
Why not just…?
Why not just plug NWD with one well-tuned constant into the existing protocol? This is the real threat. On sparse scenes with isolated, similar-sized targets, a hindsight-tuned $c$ may match annealing, and we will report that honestly. The argument above predicts the gap appears in two places. The first is scenes whose targets are much smaller than the tuned $c$, where agents localize within about $c$ but miss pixel-level hits. The second is dense clusters, where peaks merge. The size-bin and density sweeps below test exactly these. If fixed $c$ still matches annealing there, the contribution shrinks to the simpler, still useful fact that NWD supplies a known Lipschitz constant, and we would publish that instead.
Why not just discretize the scene and use discrete multi-player bandits? Cells must shrink to roughly object size before a cell centre reliably lands on a 4-pixel target, which makes the number of arms enormous. Coarser cells run into the center-versus-maximum pathology documented in Multi-Agent Lipschitz Bandits. They also hit the boundary "swap" errors reported in Multi-Agent Active Search using Detection and Location Uncertainty. The cell-size sweep of the grid baselines will show where this breaks.
Why not just centralize and run a zoom-in detector on everything? When bandwidth and a reliable link exist, one should. The centralized reference is included as an upper bound, not as a competitor to beat. Decentralized multi-agent active search for sparse signals argues that links to a server fail in the field. Cascaded Zoom-in already drops from about 26 to about 11 FPS on VisDrone, which foreshadows the cost of full-scene high-resolution processing on 12,000×5,000 satellite frames. The question here is how close agents with no communication can get.
Proposed Experiments and Decisive Checks
Main experiment. This runs on AI-TOD-v2 and VisDrone scenes with $N \in \{2,4,8\}$ agents over horizons long enough to see the $T^{3/4}$ regime (the $d=2$ case). It reports three quantities. The first is cumulative hit-based regret against the centralized oracle assignment. The second is the fraction of steps with all agents seated on distinct true targets. The third is the collision count.
Size sweep. Ground-truth targets are binned by size, and regret is plotted per bin. The prediction is that IoU-reward and small-fixed-$c$ regret rises sharply as size shrinks, while annealed regret stays roughly flat.
Density sweep. VisDrone crops are sorted by nearest-neighbour target separation. The prediction is that large fixed $c$ fails once separation drops below $c$, and annealing does not.
Stability of the evaluation itself. Ground-truth boxes are jittered by one pixel, and we measure how often the ranking of methods flips when regret is scored with IoU hits versus NWD hits. Following the pixel-shift results in A Normalized Gaussian Wasserstein Distance for Tiny Object Detection, we expect IoU-scored regret to be unstable in its own right. That would argue for NWD-based regret as the reporting standard in this setting.
Stress test. VISO video provides a setting where targets move. It probes the static-reward assumption that both the Lipschitz paper and our analysis share. We report it as an honest limit rather than a claimed win.
References
- Multi-Agent Lipschitz Bandits
- A Normalized Gaussian Wasserstein Distance for Tiny Object Detection
- Detecting tiny objects in aerial images: A normalized Wasserstein distance and a new benchmark
- Decentralized multi-agent active search for sparse signals
- Cooperative Multi-player Bandit Optimization
- Multi-Player Bandits - a Musical Chairs Approach
- SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits
- Multi-Agent Active Search using Detection and Location Uncertainty
- Cascaded Zoom-in Detector for High Resolution Aerial Images