HGFormer: A Hierarchical Graph Transformer Framework for Two-Stage Colonel Blotto Games via Reinforcement Learning

• URL: http://arxiv.org/abs/2506.08580v1
• Date: Tue, 10 Jun 2025 08:51:18 GMT
• Title: HGFormer: A Hierarchical Graph Transformer Framework for Two-Stage Colonel Blotto Games via Reinforcement Learning
• Authors: Yang Lv, Jinlong Lei, Peng Yi,
• Abstract summary: Two-stage Colonel Blotto game represents a typical adversarial resource allocation problem.<n>We propose a hierarchical graph Transformer framework called HGformer.<n>Our approach enables efficient policy generation in large-scale adversarial environments.
• Score: 4.144893164317513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Two-stage Colonel Blotto game represents a typical adversarial resource allocation problem, in which two opposing agents sequentially allocate resources in a network topology across two phases: an initial resource deployment followed by multiple rounds of dynamic reallocation adjustments. The sequential dependency between game stages and the complex constraints imposed by the graph topology make it difficult for traditional approaches to attain a globally optimal strategy. To address these challenges, we propose a hierarchical graph Transformer framework called HGformer. By incorporating an enhanced graph Transformer encoder with structural biases and a two-agent hierarchical decision model, our approach enables efficient policy generation in large-scale adversarial environments. Moreover, we design a layer-by-layer feedback reinforcement learning algorithm that feeds the long-term returns from lower-level decisions back into the optimization of the higher-level strategy, thus bridging the coordination gap between the two decision-making stages. Experimental results demonstrate that, compared to existing hierarchical decision-making or graph neural network methods, HGformer significantly improves resource allocation efficiency and adversarial payoff, achieving superior overall performance in complex dynamic game scenarios.

Related papers

• Fast State-Augmented Learning for Wireless Resource Allocation with Dual Variable Regression [83.27791109672927]
  We show how a state-augmented graph neural network (GNN) parametrization for the resource allocation policy circumvents the drawbacks of the ubiquitous dual subgradient methods.<n>Lagrangian maximizing state-augmented policies are learned during the offline training phase.<n>We prove a convergence result and an exponential probability bound on the excursions of the dual function (iterate) optimality gaps.
  arXiv  Detail & Related papers  (2025-06-23T15:20:58Z)
• SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy [24.465543841726355]
  We introduce SHIELD, a novel model that leverages both sparsity and hierarchy principles.<n>We develop a context-based clustering layer that exploits the presence of hierarchical structures in the problems to produce better local representations.<n>Our results demonstrate the superiority of our approach over existing methods on 9 real-world maps with 16 VRP variants each.
  arXiv  Detail & Related papers  (2025-06-10T03:55:14Z)
• CR-BLEA: Contrastive Ranking for Adaptive Resource Allocation in Bilevel Evolutionary Algorithms [9.411648722302711]
  Bilevel optimization poses a significant computational challenge due to its nested structure.<n>We propose a novel resource allocation framework for bilevel evolutionary algorithms.<n>Our framework significantly reduces computational cost while preserving -- or even enhancing -- solution accuracy.
  arXiv  Detail & Related papers  (2025-06-03T17:31:49Z)
• Towards Robust and Realistic Human Pose Estimation via WiFi Signals [85.60557095666934]
  WiFi-based human pose estimation is a challenging task that bridges discrete and subtle WiFi signals to human skeletons.<n>This paper revisits this problem and reveals two critical yet overlooked issues: 1) cross-domain gap, i.e., due to significant variations between source-target domain pose distributions; and 2) structural fidelity gap, i.e., predicted skeletal poses manifest distorted topology.<n>This paper fills these gaps by reformulating the task into a novel two-phase framework dubbed DT-Pose: Domain-consistent representation learning and Topology-constrained Pose decoding.
  arXiv  Detail & Related papers  (2025-01-16T09:38:22Z)
• An Efficient Dynamic Resource Allocation Framework for Evolutionary Bilevel Optimization [14.51523276196879]
  Bilevel optimization problems are characterized by an interactive hierarchical structure, where the upper level seeks to optimize its strategy while simultaneously considering the response of the lower level. This paper proposes an efficient dynamic resource allocation framework for evolutionary bilevel optimization, named DRC-BLEA.
  arXiv  Detail & Related papers  (2024-10-31T16:17:11Z)
• Pre-trained Graphformer-based Ranking at Web-scale Search (Extended Abstract) [56.55728466130238]
  We introduce the novel MPGraf model, which aims to integrate the regression capabilities of Transformers with the link prediction strengths of GNNs. We conduct extensive offline and online experiments to rigorously evaluate the performance of MPGraf.
  arXiv  Detail & Related papers  (2024-09-25T03:33:47Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• WLD-Reg: A Data-dependent Within-layer Diversity Regularizer [98.78384185493624]
  Neural networks are composed of multiple layers arranged in a hierarchical structure jointly trained with a gradient-based optimization. We propose to complement this traditional 'between-layer' feedback with additional 'within-layer' feedback to encourage the diversity of the activations within the same layer. We present an extensive empirical study confirming that the proposed approach enhances the performance of several state-of-the-art neural network models in multiple tasks.
  arXiv  Detail & Related papers  (2023-01-03T20:57:22Z)
• Multilevel-in-Layer Training for Deep Neural Network Regression [1.6185544531149159]
  We present a multilevel regularization strategy that constructs and trains a hierarchy of neural networks. We experimentally show with PDE regression problems that our multilevel training approach is an effective regularizer.
  arXiv  Detail & Related papers  (2022-11-11T23:53:46Z)
• Phase Retrieval using Expectation Consistent Signal Recovery Algorithm based on Hypernetwork [73.94896986868146]
  Phase retrieval is an important component in modern computational imaging systems. Recent advances in deep learning have opened up a new possibility for robust and fast PR. We develop a novel framework for deep unfolding to overcome the existing limitations.
  arXiv  Detail & Related papers  (2021-01-12T08:36:23Z)
• Dynamic Hierarchical Mimicking Towards Consistent Optimization Objectives [73.15276998621582]
  We propose a generic feature learning mechanism to advance CNN training with enhanced generalization ability. Partially inspired by DSN, we fork delicately designed side branches from the intermediate layers of a given neural network. Experiments on both category and instance recognition tasks demonstrate the substantial improvements of our proposed method.
  arXiv  Detail & Related papers  (2020-03-24T09:56:13Z)

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.