A regularized variance-reduced modified extragradient method for stochastic hierarchical games

Shisheng Cui, Uday V. Shanbhag, Mathias Staudigl

Introduction

Hierarchical games, most notably Stackelberg models, provide a robust mathematical framework for scenarios where a "leader" makes a decision first, and "followers" respond optimally. These models are critical in fields ranging from economic competition to power grid management. However, applying these models to real-world systems introduces three primary challenges: stochasticity (noisy data), non-smoothness (non-differentiable response maps), and computational bottlenecks (the requirement to solve follower problems perfectly at every iteration).

This paper introduces the Variance Reduced Hierarchical Game Solver (VRHGS), a novel algorithm designed to solve $N$-player hierarchical games in uncertain environments. By integrating iterative smoothing, Tikhonov regularization, and variance reduction, the authors provide a method that ensures almost-sure convergence to an equilibrium even when lower-level problems are solved inexactly.

Methodology: The VRHGS Framework

The VRHGS algorithm is built upon four foundational pillars designed to address the inherent complexities of stochastic hierarchical optimization:

1. Zeroth-Order Smoothing

In hierarchical games, the leader’s objective function depends on the follower’s optimal response. This "response map" is frequently non-differentiable, rendering standard gradient-based methods ineffective. VRHGS employs a randomized "finite-difference" approach, sampling directions on a unit sphere to estimate the "hypergradient" of the leader's objective without requiring explicit derivative information.

2. Tikhonov Regularization

To ensure the problem remains well-posed and to guide the algorithm toward a unique "least-norm" solution, the authors incorporate Tikhonov regularization. This technique adds a small penalty term to the objective functions, which is essential for stability in complex game-theoretic landscapes.

3. SVRG-style Variance Reduction

To manage stochastic noise without the prohibitive cost of massive datasets at every step, VRHGS utilizes a double-loop structure inspired by Stochastic Variance Reduced Gradient (SVRG) methods. A large mini-batch is processed in an outer loop to anchor gradient estimates, while a fast inner loop performs computationally inexpensive, single-sample updates.

4. Tseng’s Modified Extragradient (FBF)

Rather than traditional gradient descent, the algorithm utilizes a "Forward-Backward-Forward" (FBF) splitting method. This approach is more stable for Variational Inequalities and reduces the computational load by requiring only one projection step per iteration—a significant advantage when projecting onto feasible sets is the most expensive part of the calculation.

Key Theoretical Results

The paper provides rigorous proofs for the efficiency and reliability of VRHGS:

  • Convergence Rate: The algorithm achieves a convergence rate of $O(1/T)$ for the expected gap function, matching the state-of-the-art for non-hierarchical stochastic variational inequalities.
  • Oracle Complexity: To reach an $\epsilon$-accurate solution, the method requires $O(N/\epsilon^3)$ samples.
  • Almost-Sure Convergence: The authors demonstrate that the sequence of decisions generated by the algorithm converges to a hierarchical equilibrium with probability 1.

Practical Insights and Applications

A significant contribution of this work is its robustness to inexactness. The authors prove that the algorithm remains effective even if the lower-level follower problems are solved only approximately. This acknowledges the practical reality that "perfect" solutions are rarely attainable in large-scale systems.

While the paper is primarily theoretical, it presents a detailed structural model for Virtual Power Plants (VPPs) as a case study. This model illustrates how leaders (VPP operators) can optimize strategies even when they only observe follower outcomes as a "black box," rather than having a complete mathematical formula for follower reactions.

Limitations and Future Directions

Despite its theoretical strengths, the authors note several areas for future exploration:

  • Oracle Costs: The primary complexity analysis does not fully factor in the computational cost of the lower-level "oracle" that provides follower solutions.
  • Convexity Constraints: The current proofs rely on monotonicity and convexity; extending these results to non-convex hierarchical games remains a major challenge.
  • Numerical Validation: While the VPP model is sophisticated, empirical testing and numerical implementation of the model are left for future research.

Summary updated

BibTeX
@article{cui2025regularized,
  author = {Shisheng Cui and Uday V. Shanbhag and Mathias Staudigl},
  title = {{A regularized variance-reduced modified extragradient method for stochastic hierarchical games}},
  journal = {J. Optim. Theory Appl.},
  year = {2025},
  doi = {10.1007/s10957-025-02683-8},
}
Figure