Efficiently Solving Mixed-Hierarchy Games with Quasi-Policy Approximations

• URL: http://arxiv.org/abs/2602.01568v1
• Date: Mon, 02 Feb 2026 03:03:29 GMT
• Title: Efficiently Solving Mixed-Hierarchy Games with Quasi-Policy Approximations
• Abstract summary: We study N-robot forest-structured mixed-hierarchy games, in which each robot acts as a Stackelberg leader over its subtree.<n>We derive the Karush-Kuhn-Tucker (KKT) first-order optimality conditions for this class of games and show that they involve increasingly high-order derivatives of robots' best-response policies.<n>We introduce a quasi-policy approximation that removes higher-order policy derivatives and develop an inexact Newton method for efficiently solving the resulting approximated KKT systems.
• Score: 12.61459634168241
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-robot coordination often exhibits hierarchical structure, with some robots' decisions depending on the planned behaviors of others. While game theory provides a principled framework for such interactions, existing solvers struggle to handle mixed information structures that combine simultaneous (Nash) and hierarchical (Stackelberg) decision-making. We study N-robot forest-structured mixed-hierarchy games, in which each robot acts as a Stackelberg leader over its subtree while robots in different branches interact via Nash equilibria. We derive the Karush-Kuhn-Tucker (KKT) first-order optimality conditions for this class of games and show that they involve increasingly high-order derivatives of robots' best-response policies as the hierarchy depth grows, rendering a direct solution intractable. To overcome this challenge, we introduce a quasi-policy approximation that removes higher-order policy derivatives and develop an inexact Newton method for efficiently solving the resulting approximated KKT systems. We prove local exponential convergence of the proposed algorithm for games with non-quadratic objectives and nonlinear constraints. The approach is implemented in a highly optimized Julia library (MixedHierarchyGames.jl) and evaluated in simulated experiments, demonstrating real-time convergence for complex mixed-hierarchy information structures.

Related papers

• Coupled Hierarchical Search over Topology and Execution for Agentic Workflow Synthesis [64.2820121997882]
  We introduce HierFlow, a training-free, test-time hierarchical search architecture that automates agentic workflow design.<n> HierFlow maximizes efficiency through an intelligent gating module that selectively triggers execution-level searches based on contextual necessity.<n> Comprehensive testing across question answering, mathematical reasoning, and code generation benchmarks confirms that HierFlow consistently outperforms strong baselines.
  arXiv  Detail & Related papers  (2026-05-20T01:56:11Z)
• A Data Driven Structural Decomposition of Dynamic Games via Best Response Maps [0.0]
  This paper introduces a conceptually novel formulation for dynamic games by restructuring the equilibrium computation.<n>The proposed formulation is supported by mathematical proofs, accompanying a large-scale Monte Carlo study in a two-player open-loop dynamic game motivated by the autonomous racing problem.
  arXiv  Detail & Related papers  (2026-02-05T05:44:53Z)
• Multi-Action Self-Improvement for Neural Combinatorial Optimization [0.979731979071071]
  Self-improvement models iteratively refine their policies by generating and imitating high-quality solutions.<n>These approaches fail to exploit the structure of problems involving the coordination of multiple agents.<n>We extend self-improvement to operate over joint multi-agent actions.
  arXiv  Detail & Related papers  (2025-10-14T08:26:27Z)
• Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis [22.360309142419208]
  We study policy optimization in Stackelberg mean field games (MFGs)<n>We propose AC-SMFG, a single-loop actor-critic algorithm that operates on continuously generated Markovian samples.<n>We establish the finite-time and finite-sample convergence of the algorithm to a stationary point of the Stackelberg objective.
  arXiv  Detail & Related papers  (2025-09-18T19:58:31Z)
• Multi-Agent Collaboration via Evolving Orchestration [55.574417128944226]
  Large language models (LLMs) have achieved remarkable results across diverse downstream tasks, but their monolithic nature restricts scalability and efficiency in complex problem-solving.<n>We propose a puppeteer-style paradigm for LLM-based multi-agent collaboration, where a centralized orchestrator ("puppeteer") dynamically directs agents ("puppets") in response to evolving task states.<n> Experiments on closed- and open-domain scenarios show that this method achieves superior performance with reduced computational costs.
  arXiv  Detail & Related papers  (2025-05-26T07:02:17Z)
• Learning Multi-Robot Coordination through Locality-Based Factorized Multi-Agent Actor-Critic Algorithm [54.98788921815576]
  We present a novel cooperative multi-agent reinforcement learning method called textbfLocality based textbfFactorized textbfMulti-Agent textbfActor-textbfCritic (Loc-FACMAC)<n>We integrate the concept of locality into critic learning, where strongly related robots form partitions during training.<n>Our method improves existing algorithms by focusing on local rewards and leveraging partition-based learning to enhance training efficiency and performance.
  arXiv  Detail & Related papers  (2025-03-24T16:00:16Z)
• Multi-Task Off-Policy Learning from Bandit Feedback [54.96011624223482]
  We propose a hierarchical off-policy optimization algorithm (HierOPO), which estimates the parameters of the hierarchical model and then acts pessimistically with respect to them. We prove per-task bounds on the suboptimality of the learned policies, which show a clear improvement over not using the hierarchical model. Our theoretical and empirical results show a clear advantage of using the hierarchy over solving each task independently.
  arXiv  Detail & Related papers  (2022-12-09T08:26:27Z)
• Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
  In a Stackelberg congestion game (SCG), a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which the followers settle by playing a congestion game. Here, we attempt to tackle this computational challenge by marrying traditional methodologies with the latest differentiable programming techniques in machine learning. We propose two new local search algorithms for SCGs. The first is a gradient descent algorithm that obtains the derivatives by unrolling ILD via differentiable programming. The second algorithm adds a twist by cutting short the followers' evolution trajectory.
  arXiv  Detail & Related papers  (2022-09-15T21:32:23Z)
• Graph-based Reinforcement Learning meets Mixed Integer Programs: An application to 3D robot assembly discovery [34.25379651790627]
  We tackle the problem of building arbitrary, predefined target structures entirely from scratch using a set of Tetris-like building blocks and a robotic manipulator. Our novel hierarchical approach aims at efficiently decomposing the overall task into three feasible levels that benefit mutually from each other.
  arXiv  Detail & Related papers  (2022-03-08T14:44:51Z)
• Deep Imitation Learning for Bimanual Robotic Manipulation [70.56142804957187]
  We present a deep imitation learning framework for robotic bimanual manipulation. A core challenge is to generalize the manipulation skills to objects in different locations. We propose to (i) decompose the multi-modal dynamics into elemental movement primitives, (ii) parameterize each primitive using a recurrent graph neural network to capture interactions, and (iii) integrate a high-level planner that composes primitives sequentially and a low-level controller to combine primitive dynamics and inverse kinematics control.
  arXiv  Detail & Related papers  (2020-10-11T01:40:03Z)
• Follow the Neurally-Perturbed Leader for Adversarial Training [0.0]
  We propose a novel leader algorithm for zeros-sum training to mixed equilibrium without behaviors without perturbations. We validate our theoretical results by applying this training algorithm to games with convex and non-perturbed loss as well as generative adversarial architectures. We customize the implementation of this algorithm for adversarial imitation learning applications.
  arXiv  Detail & Related papers  (2020-02-16T00:09:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.