In adaptive dynamic programming (ADP), traditional actor-critic methods make use of both policy gradient learning and value function approximation to search for near-optimal control policies in continuous spaces. Since neural networks are used to design the critic component, the generalization capability and learning efficiency of ADP need to be improved. In this paper, by integrating online kernel learning and approximately linear dependence (ALD) analysis to design critic module of ADP, a novel online sparse kernel-based ADP algorithm is presented. And then, the designing procedure of kernel-based heuristic dynamic programming (KHDP) is analyzed. Finally, in optimal control nonlinear discrete-time systems, an illustrated example is provided to demonstrate the effectiveness of the KHDP algorithm.