Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation

Heavy-tailed stochastic gradients can destabilize bilevel optimization by prop- agating lower-level errors into upper-level updates. We propose RQ-TTSA, a quantile-guided clipping framework for two-timescale stochastic approximation. The method uses a rolling buffer of gradient norms to adapt its clipping threshold, controlling the magnitudes of lower-level stochastic gradients while preserving their directions through radial rescaling. We further specify a predictable threshold variant that combines historical quantile estimates with bounded scale factors and an explicit polynomial growth schedule. This construction establishes pathwise threshold bounds and separates empirical scale adaptation from the growth con- ditions needed for convergence analysis. Experiments with the rolling-quantile implementation cover synthetic problems, vision benchmarks, stochastic games, and offline actor–critic learning. The reported results show lower mean final losses on the vision benchmarks and reduced actor-loss fluctuations in the offline re- inforcement learning experiment, while stability gains vary across tasks. These findings suggest that recent gradient statistics can provide useful scale information for robust bilevel updates.