MPLS automatic bandwidth allocation (or provisioning) refers to the process of dynamically updating the bandwidth allocation of a label switched path on the basis of actual aggregate traffic demand on this path. Since bandwidth updates require signaling, it is common to limit the rate of updates to reduce signaling costs. In this article, we propose a model-free asynchronous adaptive hysteresis algorithm for MPLS automatic bandwidth allocation under bandwidth update rate constraints. We validate the effectiveness of the proposed approach by comparing it against existing schemes in (i) voice and (ii) data traffic scenarios. The proposed method can also be used in more general GMPLS networks.