The emergence of smart grids has posed great challenges to traditional power system control given the multitude of new risk factors. This paper proposes an online supplementary learning controller (OSLC) design method to compensate the traditional power system controllers for coping with the dynamic power grid. The proposed OSLC is a supplementary controller based on approximate dynamic programming, which works alongside an existing power system controller. By introducing an action-dependent cost function as the optimization objective, the proposed OSLC is a nonidentifier-based method to provide an online optimal control adaptively as measurement data become available. The online learning of the OSLC enjoys the policy-search efficiency during policy iteration and the data efficiency of the least squares method. For the proposed OSLC, the stability of the controlled system during learning, the monotonic nature of the performance measure of the iterative supplementary controller, and the convergence of the iterative supplementary controller are proved. Furthermore, the efficacy of the proposed OSLC is demonstrated in a challenging power system frequency control problem in the presence of high penetration of wind generation.