One of the biggest limitations of BP algorithm is its low rate of convergence. The Variable Learning Rate (VLR) algorithm represents one of the well-known techniques that enhance the performance of the BP. Because the VLR parameters have important influence on its performance, we use learning automata (LA) to adjust them. The proposed algorithm named Adaptive Variable Learning Rate (AVLR) algorithm dynamically tunes the VLR parameters by learning automata according to the error changes. Simulation results on some practical problems such as sinusoidal function approximation, nonlinear system identification, phoneme recognition, Persian printed letter recognition helped us better to judge the merit of the proposed AVLR method.