SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search

Technical Summary: SEArch – Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search

Problem Statement
Unmanned Aerial Vehicles (UAVs) equipped with radar sensors are increasingly deployed for target search missions in dynamic environments, such as maritime rescue and disaster response. These missions face a fundamental challenge: radar statistics shift as the UAV moves through non-stationary environments (e.g., changes in wall materials, clutter, or sea states), rendering fixed signal-processing strategies suboptimal. Furthermore, these adaptations must occur onboard resource-constrained nodes with ultra-low latency, precluding cloud offloading.

The core difficulty lies in balancing two distinct sources of uncertainty:

1. In-scene stochastic noise: Fluctuations within a stable scene caused by UAV micro-motions and clutter.
2. Inter-scene distributional shifts: Abrupt or gradual changes in the measurement distribution as the UAV transitions between different environmental regimes.

Existing methods typically address only one regime: adversarial online learning methods yield conservative bounds independent of actual difficulty, while stochastic models fail to capture sudden scene changes. The paper posits that no single detector performs well across all conditions, necessitating a multi-policy paradigm where the system must select the optimal policy from a pre-trained library in real-time without prior knowledge of scene drifts or noise scales.

Methodology
The authors formulate the UAV target search problem as an Online Convex Optimization (OCO) task over a finite library of $K$ specialized signal processing policies. The performance metric is regret, defined as the cumulative loss gap relative to the best fixed policy in hindsight for each specific scene segment.

To model the environment, the paper adopts the Stochastically Extended Adversary (SEA) framework. This framework decomposes problem difficulty into:

• $\bar{\sigma}_T^2$: Cumulative stochastic variance (in-scene noise).
• $\bar{\Sigma}_T^2$: Cumulative adversarial variation (inter-scene drift).

The paper introduces two algorithms instantiated within this framework:

1. SEARCH (Optimistic FTRL):

   • An optimistic Follow the Regularized Leader (OFTRL) selector with an adaptive learning rate.
   • It predicts the next loss based on the previous observation ($M_t = \ell_{t-1}$). This prediction is accurate within stable scenes but fails at transitions.
   • The adaptive learning rate automatically becomes conservative when prediction errors (indicating a transition or high noise) are detected, preventing oscillation.
   • Regret Bound: $O(\bar{\sigma}_T \sqrt{T} + \sqrt{J})$, where $J$ is the number of scene transitions. The switching penalty grows only as $\sqrt{J}$.

2. W-SEARCH (Windowed OFTRL):

   • Designed for missions with frequent scene changes where global history accumulation induces inertia (favoring outdated policies).
   • It restricts updates to the most recent $w$ observations, performing a "hard restart" every $w$ rounds.
   • This prunes obsolete measurements from previously traversed scenes, enabling rapid adaptation to irregular changes.
   • Regret Bound: $O(\bar{\sigma}_I \sqrt{w})$ on any contiguous interval of length $w$, assuming at most one transition per window.

Both algorithms are lightweight, requiring only $O(K \log K)$ computation per round and $O(K)$ memory state, with no online training or external accelerators. They rely on full-information feedback, where a single radar measurement evaluates all $K$ policies simultaneously, incurring no additional sensing costs.

Key Contributions

• Formulation: The authors cast UAV search as online policy selection over a finite library, modeling uncertainty via the SEA framework to derive problem-dependent regret bounds that scale with actual environmental difficulty rather than worst-case assumptions.
• SEARCH Algorithm: An OFTRL selector achieving a regret bound of $O(\bar{\sigma}_T \sqrt{T} + \sqrt{J})$, effectively decomposing the cost into stochastic noise and switching penalties.
• W-SEARCH Algorithm: A windowed variant that achieves adaptive regret $O(\bar{\sigma}_I \sqrt{w})$ on intervals of length $w$, specifically addressing the inertia problem in rapidly changing missions.
• Modularity: The approach is orthogonal to the policy library construction; it serves as an online selection layer that can sit atop any pre-trained pool of detectors.

Experimental Results
The authors validate their approach through simulations with $K=4$ policies across various non-stationary settings ($T=150$):

• Regret Reduction: Compared to non-adaptive baselines (UCB, Exp3, OMD), the proposed methods achieve up to 30% regret reduction.
• Adaptation Speed: SEARCH concentrates weight on the optimal policy within 10 steps of a regime shift.
• Windowed Performance: W-SEARCH demonstrates significant advantages in rapidly changing environments. In scenarios with frequent transitions, it reduced final regret by 60% to 72% compared to the global SEARCH algorithm.
• Robustness: The windowed approach remains robust to irregular switching patterns and varying noise levels ($\sigma \in [0.05, 0.4]$), though the relative advantage diminishes slightly at very high noise levels where more observations are required per segment.
• Scalability: Both algorithms scale well with the number of policies ($K$), with W-SEARCH showing superior performance as the action space grows to $K=16$.

Significance and Claims
The paper claims that by moving beyond purely adversarial or purely stochastic models, the SEA framework allows for a more nuanced understanding of UAV radar search environments. The primary significance lies in providing lightweight, onboard solutions that can track optimal policies in real-time without prior knowledge of scene dynamics. The authors emphasize that their approach achieves near-optimal stochastic rates in stationary environments while relaxing to non-stationary rates when changes are frequent, all while maintaining the computational constraints necessary for low-altitude IoT network nodes. The work specifically targets the "online selection layer," leaving the construction of the offline policy library to complementary works (e.g., [5]), thereby offering a modular solution for adaptive sensing.