Organizations: Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India · Department of Electrical and Computer Engineering, Purdue University, IN, USA
Federated Reinforcement Learning (FRL) provides a promising way to speedup training in reinforcement learning when one has access to multiple edge devices that can operate in parallel. Recently, it has been shown that even when these edge devices have access to different dynamic models---such as cars or robots with differing system configurations---an optimal convergence rate that has a linear speedup proportional to the number of devices is achievable. However, this result requires that the algorithm's stepsize be chosen in a manner that depends on the unknown model parameters. Also, it applies only to a discounted setting, which has been argued to fit episodic tasks better than continuing control tasks. In this paper, we obtain finite-time bounds for heterogeneous FRL with average rewards. We show that optimal convergence rate and linear speedup are achievable even with a universal stepsize choice, independent of the underlying dynamics. To achieve our result, we modify the existing one-timescale FRL method to a novel two-timescale variant that additionally incorporates iterate averaging. We remark that this idea also extends to other settings already studied in the literature, such as the homogeneous FRL or the heterogeneous case with a discounted cost function.
Figures & tables
Constant
Definition
Heterogeneity and stability
Cd(ϵp)
(1−ϵp1+ϵp)∣S∣−1
CA,inv
max{i∈[N]max∥Ai−1∥,∥A−1∥}
CA(ϵp)
2min{2,Cd(ϵp)}+2ϵp
Cb(ϵp,ϵr)
2ϵr+3Rmaxmin{2,Cd(ϵp)}
Hr(ϵp,ϵr)
[ϵr+Rmaxmin{2,Cd(ϵp)}]2
TABLE I : Constants used in the finite-time analysis.
Fig. 1 : Comparison of our proposed two-timescale federated TD algorithm (left column) with the vanilla single-timescale federated TD algorithm described in Section III (right column). The top row corresponds to ϵp=ϵr=0.1 , while the bottom row corresponds to ϵp=ϵr=0.7 . We consider N∈{2,5,10,20} agents. The horizontal axis shows the number of iterations, while the vertical axis shows the mean-squared error relative to θ1∗ , computed using the Polyak–Ruppert averaged iterate for our algorithm and the raw iterate for the vanilla algorithm. Each curve is averaged over 10 independent runs, and the final 1000 iterations are magnified in the inset plots. Our algorithm uses β=0.3 . Both algorithms exhibit lower errors as N increases, with comparable performance despite our algorithm not requiring model-dependent stepsizes.
Fig. 2 : Effect of the stepsize exponent β on the performance of Algorithm 1 for N=5 agents. We vary β from 0.01 to 0.99 . The left panel corresponds to ϵp=ϵr=0.1 , while the right panel corresponds to ϵp=ϵr=0.7 . Each curve shows the mean-squared error averaged over 10 independent runs of 5000 iterations each. Smaller values of β generally lead to faster error reduction in both settings.
Fig. 3 : Long-term performance of our proposed Algorithm 1 (solid line) and the vanilla single-timescale federated TD algorithm (dotted line) for N=10 agents with ϵp=ϵr=0.7 . Each curve is averaged over 5 independent runs of 200,000 iterations. The errors eventually level off, consistent with the residual error due to heterogeneity predicted by our theoretical results. Our algorithm achieves a substantially lower error than the vanilla baseline in this experiment.
Carnegie Mellon University · Department of Electrical and Computer Engineering, Carnegie Mellon University. · Department of Statistics and Data Science, Yale University.