We propose a decentralized method for adaptive prediction of task processing times in dynamic environments. Each controller independently estimates the expected duration of incoming tasks using a gradient-free update rule based on the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm. To ensure coherence across the system, controllers synchronize their models through consensus over a time-varying communication graph. This approach enables efficient learning under limited observability and noisy feedback, without requiring access to gradients or global information. We provide theoretical guarantees for convergence under bounded noise, drawing on recent results for distributed SPSA with consensus. Simulations demonstrate the method’s resilience to abrupt changes in task behavior (“drift”) and show that it outperforms baseline methods in terms of prediction accuracy and inter-controller consistency. We further illustrate how the SPSA+Cons approach can be deployed in a modular multi-agent AI platform to align operational parameters across heterogeneous agents under uncertainty. The proposed solution is lightweight, fully decentralized, and suitable for a variety of settings where centralized control is infeasible or costly. Potential applications include collaborative scheduling, sensor coordination, and adaptive task routing in large-scale systems.