The authors tackle decentralized solving of large fixed-point equations (like those in reinforcement learning or optimization) by splitting the problem across agents. Standard "strict decomposition" assigns each agent disjoint variables, but this creates structural bias because updating one block often depends on variables in other blocks. They propose Core-Halo decomposition: each agent owns a "core" (writes updates) but reads from an overlapping "halo" (neighbors' variables), eliminating bias while keeping parallelism.
Main takeaways:
- Strict decomposition (each agent owns disjoint variables and only uses those) changes the underlying fixed-point operator and creates bias that can't be fixed by more data or smaller stepsizes
- Core-Halo decomposition lets agents write to their own core but read from an overlapping halo, faithfully implementing the original centralized problem in a decentralized setting
- They characterize when strict decomposition fails via a "Bellman closure" condition and prove a bias lower bound
- Experiments across multiple settings show Core-Halo achieves near-centralized performance while retaining parallel speedup
- The method applies to reinforcement learning, consensus optimization, and other fixed-point problems