Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling

• URL: http://arxiv.org/abs/2607.25835v1
• Date: Tue, 28 Jul 2026 15:15:43 GMT
• Title: Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling
• Abstract summary: Distributed optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically.<n>We revisit the connection between DCOPs and potential games, and adapt modern online learning algorithms for equilibrium finding to DCOPs.<n>We then turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling.
• Score: 39.28018254600072
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically. We address this challenge from two complementary directions. We revisit the connection between DCOPs and potential games, and adapt modern online learning algorithms for equilibrium finding to DCOPs. We show that these algorithms are competitive with representative incomplete DCOP algorithms. We then turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling. We propose a new framework that separates a DCOP into two interacting subproblems: a high-level meta-DCOP for task allocation, and independent local optimization problems for scheduling. To couple the two levels, we develop a novel iterative pricing method that updates the meta-level utilities using feedback from the local optimizers. Combining our online learning methods with our iterative pricing framework, we obtain near-optimal performance on real-world decentralized satellite scheduling problem instances, fulfilling over 99% of observation requests compared with 87% for state-of-the-art baselines.

Related papers

• Revisiting Decentralized Online Convex Optimization with Compressed Communication [68.72667170947358]
  We propose two FTRL-type algorithms for D-OCO with compressed communication.<n>Our first algorithm considers the full-information setting, and can match the existing regret bounds.<n>Our second algorithm is designed for the bandit setting, and can significantly improve both the regret bounds and communication costs.
  arXiv  Detail & Related papers  (2026-07-02T03:45:41Z)
• ARMATA: Auto-Regressive Multi-Agent Task Assignment [6.2002105625228845]
  We propose a fully end-to-end auto-regressive framework that jointly generates allocation decisions and routing sequences.<n>The core contribution of our approach is a multi-stage decoding mechanism that unifies high-level allocation and low-level routing in a single autoregressive pass.
  arXiv  Detail & Related papers  (2026-05-05T19:08:08Z)
• Large-Scale Continual Scheduling and Execution for Dynamic Distributed Satellite Constellation Observation Allocation [1.3467991712339638]
  Deploying autonomy to satellites requires efficient computation and communication.<n>We present the Dynamic Multi-Satellite Constellation Observation Scheduling Problem (DCOSP)<n>We also present the Dynamic Incremental Neighborhood Search algorithm (D-NSS)
  arXiv  Detail & Related papers  (2026-01-08T00:10:45Z)
• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  We study the problem of distributed multi-level optimization over a network, where agents can only communicate with their immediate neighbors. We propose a novel gossip-based distributed multi-level optimization algorithm that enables networked agents to solve optimization problems at different levels in a single timescale. Our algorithm achieves optimal sample complexity, scaling linearly with the network size, and demonstrates state-of-the-art performance on various applications.
  arXiv  Detail & Related papers  (2023-10-10T00:21:10Z)
• Joint Service Caching, Communication and Computing Resource Allocation in Collaborative MEC Systems: A DRL-based Two-timescale Approach [15.16859210403316]
  Meeting the strict Quality of Service (QoS) requirements of terminals has imposed a challenge on Multiaccess Edge Computing (MEC) systems. We propose a collaborative framework that facilitates resource sharing between the edge servers. We show that our proposed algorithm outperforms the baseline algorithms in terms of the average switching and cache cost.
  arXiv  Detail & Related papers  (2023-07-19T00:27:49Z)
• DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization [27.317118892531827]
  We develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale approximation with momentum and gradient-tracking) We show that the DIAMOND enjoys $mathcalO(epsilon-3/2)$ in sample and communication complexities for achieving an $epsilon$-stationary solution.
  arXiv  Detail & Related papers  (2022-12-05T15:58:00Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Deep Learning-based Resource Allocation For Device-to-Device Communication [66.74874646973593]
  We propose a framework for the optimization of the resource allocation in multi-channel cellular systems with device-to-device (D2D) communication. A deep learning (DL) framework is proposed, where the optimal resource allocation strategy for arbitrary channel conditions is approximated by deep neural network (DNN) models. Our simulation results confirm that near-optimal performance can be attained with low time, which underlines the real-time capability of the proposed scheme.
  arXiv  Detail & Related papers  (2020-11-25T14:19:23Z)
• On Population-Based Algorithms for Distributed Constraint Optimization Problems [12.21350091202884]
  We study an emerging class of incomplete algorithms that are broadly termed as population-based algorithms. Our first approach, Anytime Evolutionary DCOP or AED, exploits evolutionary optimization meta-heuristics to solve DCOPs. While in our second contribution, we show that population-based approaches can be combined with local search approaches.
  arXiv  Detail & Related papers  (2020-09-02T06:39:30Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

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.