Technical Summary: Distributed GNEP Algorithms without Multiplier Sharing and Applications to Multi-Robot Coordination and Contextual Bandit-Based Active Learning

1. Problem Statement

The thesis addresses two distinct but significant challenges in distributed optimization and machine learning:

Part I: Generalized Nash Equilibrium Problems (GNEPs)
In many multi-agent systems (e.g., power grids, traffic routing, multi-robot coordination), agents must minimize local cost functions subject to both individual constraints and shared coupling constraints. This formulation leads to the Generalized Nash Equilibrium Problem (GNEP). Existing distributed algorithms for solving GNEPs typically rely on enforcing consensus among Lagrange multipliers associated with shared constraints. This requirement necessitates the exchange of auxiliary variables and multipliers between agents, increasing communication overhead and potentially compromising privacy. Furthermore, most existing methods are restricted to computing variational Generalized Nash Equilibria (v-GNEs), a specific subclass of equilibria, rather than the full set of Generalized Nash Equilibria (GNEs).

Part II: Contextual Bandit-Based Active Learning
Active learning aims to reduce the labeling cost in supervised learning by selectively querying the most informative data points. While numerous hand-crafted strategies exist (e.g., uncertainty sampling, diversity sampling), their performance is highly dependent on the underlying data distribution, which is often unknown. Existing adaptive frameworks that combine these strategies often utilize adversarial bandit algorithms. These methods are overly conservative, maintaining persistent exploration without leveraging environmental context, often resulting in performance similar to random selection.

2. Methodology

Part I: Fully Distributed Algorithms for GNEPs

The author proposes a fully distributed continuous-time algorithm based on primal-dual dynamics that eliminates the need for multiplier sharing.

• Primal-Dual Dynamics: The algorithm models the system as a Projected Dynamical System (PDS). Agents update their decision variables ($z_v$) and local multipliers ($\lambda_v, \mu_v$) using only local information and data exchanged with neighbors over specific interaction graphs (cost-function graph and shared-constraint graph).
• Multiplier Transformation: A key theoretical innovation is the transformation of shared multipliers. Instead of enforcing consensus ($\lambda_v = \lambda_u$), the method decomposes multipliers into a common reference state and a deviation term ($\Delta_v$). The dynamics of the deviation terms are shown to be constant or non-increasing over time, depending on the constraint type (equality vs. inequality).
• Convergence Analysis:
  • Equality Constraints: For games with strongly monotone cost mappings and linear shared equality constraints, the author proves global asymptotic stability. The primal variables converge to a unique GNE, while dual variables converge to a set of valid multipliers. The limiting equilibrium depends on the initialization of the deviation terms.
  • Inequality Constraints: For shared inequality constraints with quadratic convex costs, the analysis utilizes bounded-input bounded-output (BIBO) arguments and trajectory boundedness to prove convergence to a GNE, even when the induced primal-dual dynamics are not monotone.
• Discretization: To enable practical implementation, the thesis develops three discretization schemes:
  1. Diminishing Step Size: Mimics continuous dynamics asymptotically but converges slowly ($O(1/\sqrt{k})$).
  2. Backward Euler (Resolvent): Uses a fixed step size and requires solving an inner Nash Equilibrium Problem (NEP) at each step. It achieves an $o(1/k)$ convergence rate.
  3. Forward-Backward Splitting: A hybrid scheme that avoids the inner solver requirement by treating parts of the operator explicitly and others implicitly. It requires a globally agreed step size but offers a balance between computational cost and convergence rate.

Part II: Contextual Adaptive Active Learning (CAAL)

The second part introduces Contextual Adaptive Active Learning (CAAL), a meta-strategy framework that uses contextual bandits to select the best hand-crafted active learning strategy dynamically.

• Framework: The problem is modeled as a contextual bandit where "arms" are different hand-crafted active learning strategies (e.g., K-Center, Informative Diversity).
• Context and Reward: Unlike adversarial bandit approaches, CAAL incorporates external context (e.g., the current size of the labeled dataset) to predict rewards. The reward is defined as the relative improvement in model performance (e.g., change in ROC-AUC) between iterations, rather than absolute performance, to address non-stationarity.
• Algorithm: The method employs a non-stationary linear Upper Confidence Bound (LinUCB) algorithm (specifically Sliding Window LinUCB) to estimate the reward function $\theta_a^\top c_k$. This allows the agent to exploit the predictability of rewards based on context, reducing the conservativeness inherent in adversarial bandit methods.

3. Key Contributions

For GNEPs:

1. First Multiplier-Free Distributed Algorithm: To the author's knowledge, this is the first distributed algorithm that computes GNEs without requiring consensus or exchange of Lagrange multipliers. This significantly reduces communication overhead (by approximately one-third in specific graph settings) and enhances privacy.
2. General GNE Convergence: The proposed method is not restricted to variational-GNEs. It converges to general GNEs, with the specific equilibrium reached depending on the initialization. This addresses the limitation of existing methods that only target the unique v-GNE.
3. Novel Proof Techniques: The thesis develops proof techniques to handle non-monotone induced dynamics and non-unique equilibria, utilizing Lyapunov stability analysis and bounded trajectory arguments.

For Active Learning:

1. Contextual Adaptation: The work proposes incorporating contextual information into bandit-based active learning to reduce the conservativeness of adversarial bandit frameworks.
2. Batch Selection Focus: Unlike many prior works focusing on single-sample selection, this approach emphasizes robustness across different batch sizes, which is more aligned with industrial applications.
3. Meta-Learner Approach: The method focuses on meta-learner-based selection rather than deep active learning, making it more suitable for tabular data, which dominates industrial datasets.

4. Results

GNEP Simulations:

• Multi-Robot Coordination: The algorithm was tested on multi-robot placement and half-space covering problems. Results demonstrated convergence to GNEs from various initializations, highlighting the non-uniqueness of solutions. The forward-backward discretization (Algorithm 4.10) showed comparable convergence rates to consensus-based methods but with significantly reduced communication per iteration.
• Cournot Competition: The method was applied to a Cournot game with 20 agents and 7 markets. The algorithm successfully converged to a GNE for any initialization, preserving agent privacy and demonstrating scalability.

Active Learning Experiments:

• Datasets: Experiments were conducted on public datasets (ILPD, I vs J, Australian Credit, German Credit) using logistic regression as the base classifier.
• Performance: CAAL was compared against the state-of-the-art adaptive baseline (ALBL) and hand-crafted strategies (K-Center, Informative Diversity).
  • CAAL outperformed ALBL and individual strategies on most datasets, particularly for batch sizes greater than 5.
  • The "Reward Prediction" analysis showed that the linear regression model could accurately predict reward trends based on context, validating the assumption of local linearity.
  • "Pull History" analysis indicated that CAAL successfully identified and exploited the optimal strategy after an initial exploration phase, whereas ALBL tended to select arms with near-equal probability due to its conservative nature.
• Deployment: The framework has been deployed in Amazon's internal production systems, though results from internal datasets are omitted due to confidentiality.

5. Significance and Claims

The thesis claims to bridge critical gaps in both distributed game theory and adaptive machine learning:

• In Distributed Optimization: By removing the requirement for multiplier sharing, the proposed framework offers a more scalable and privacy-preserving solution for large-scale multi-agent systems. The ability to converge to general GNEs rather than just v-GNEs expands the applicability of distributed equilibrium computation to scenarios where uniform pricing or centralized coordination is not feasible.
• In Active Learning: The work demonstrates that leveraging contextual information can significantly improve the adaptability of active learning strategies compared to purely adversarial approaches. The proposed CAAL framework provides a practical, industry-friendly solution for batch-mode active learning that adapts to unknown data distributions without requiring deep learning architectures.

The author notes that while the continuous-time analysis provides strong theoretical guarantees, the discretization schemes introduce specific assumptions (e.g., Lipschitz continuity, compactness) required for convergence. Similarly, for the active learning component, the exploration complexity depends on the number of candidate strategies (arms), and the framework currently relies on domain expertise to define the initial set of hand-crafted strategies. Future work is proposed to extend the GNEP algorithms to more general convex constraints and to refine the theoretical analysis of the contextual bandit framework.