Reproduce “Replicable Reinforcement Learning with Linear Function Approximation” on OpenResearch

About this paper

Eric Eaton, Marcel Hussing, Michael Kearns, Aaron Roth, Sikata Bela Sengupta, Jessica Sorrell

Researchers from the University of Pennsylvania and Johns Hopkins University developed the first provably replicable reinforcement learning algorithms for linear function approximation, addressing the instability of RL by integrating novel replicable statistical tools into value iteration and UCB-based methods. The framework provides theoretical guarantees for policy replicability and sub-optimality in linear MDPs, with empirical results showing that rounding and regularization can improve consistency in deep RL without sacrificing performance.

Key insights

• Provable replicability can be achieved in linear function approximation settings by applying randomized rounding to fundamental statistical building blocks like regression coefficients and covariance matrix entries.
• The strong convexity of ridge regression and careful perturbation analysis are essential to bound the error introduced by rounding and to maintain performance guarantees of RL algorithms.
• Replicability in sequential decision-making can be established inductively, where the replicability of each step's statistical estimation leads to the replicability of the overall policy.

Summary by alphaXiv.