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

arXiv: https://arxiv.org/abs/2607.25835 · HTML: https://mlsanity.com/paper/2607.25835/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 52 references that are in the map.
- First posted on arXiv 28 Jul 2026.

## Builds on (most cited first, 14 of 14)

- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Distributed Constraint Optimization Problems and Applications: A Survey](https://mlsanity.com/paper/1602.06347/) (2016)
- [Agile Earth observation satellite scheduling over 20 years: formulations, methods and future directions](https://mlsanity.com/paper/2003.06169/) (2020)
- [A Maximum Independent Set Method for Scheduling Earth Observing Satellite Constellations](https://mlsanity.com/paper/2008.08446/) (2020)
- [Auction-based and Distributed Optimization Approaches for Scheduling Observations in Satellite Constellations with Exclusive Orbit Portions](https://mlsanity.com/paper/2106.03548/) (2021)
- [Asynchronous Forward Bounding for Distributed COPs](https://mlsanity.com/paper/1401.3442/) (2014)
- [Real-Time Instrument Planning and Perception for Novel Measurements of Dynamic Phenomena](https://mlsanity.com/paper/2509.03500/) (2025)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Scalable Dynamic Distributed Constraint Optimization with Metareasoning and Application to Continual Satellite Operations](https://mlsanity.com/paper/2601.06188/) (2026)
- [Dynamic Targeting of Satellite Observations Using Supplemental Geostationary Satellite Data and Hierarchical Planning](https://mlsanity.com/paper/2603.06719/) (2026)
- [Free-Placement Optimization of Ground Station Locations for Low-Earth Orbit Satellites](https://mlsanity.com/paper/2606.12667/) (2026)

## Abstract (arXiv)

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.