arXiv:2608.01802v2 Announce Type: replace-cross Abstract: Aerial search missions often require an unmanned aerial vehicle (UAV) to locate a target from only a brief description of its appearance and surroundings, a task known as target-oriented aerial vision-and-language navigation (VLN). The task demands city-scale exploration and grounding as well as collision-free close-range approach, two interleaved processes that are difficult to reconcile within a single agent. Most existing methods adapt the ground VLN paradigm to a single UAV and rely on external assistance to compensate for its inefficiency. A recent attempt deploys two UAVs at complementary altitudes but still depends on privileged sensing and trains the two agents independently, precluding any mutual adaptation. We propose CoNav-UAV, which models the task as a Stackelberg game between a high-altitude leader and a low-altitude follower to capture their sequential decisions and asymmetric observations and utilities, with both agents using only onboard sensing. We introduce Iterative Stackelberg Learning, which tailors optimization to each agent's role: the leader's high-level vision-language reasoning builds on pretrained capabilities and is refined through memory-based in-context learning, while the follower's precise motion control is fine-tuned through DAgger-style expert distillation. Alternating the two updates lets each agent continually adapt to the other's evolving behavior. CoNav-UAV outperforms single- and dual-agent baselines across three high-fidelity urban scenes from the AerialVLN benchmark. It improves success rate by up to 30.8 points on the learning scene and by up to 9.0 points under cross-scene transfer, where the leader reuses its learned memory and the follower is adapted with 2.6-3.7 times less target-scene data. Extensive ablations confirm the contributions of key components and the benefit of mutual adaptation, with consistent gains across VLM backbones.