On-Policy AC. Several variants of AC were proposed in [1]}, [2]}, [3]}, [4]}, [5]}. In the tabular setting, [6]}, [7]}, [2]} studied the asymptotic convergence of AC algorithm. Furthermore, [9]}, [10]} characterize the asymptotic convergence of on-policy AC under function approximation. Recently, there has been a flurry of work studying the finite-sample convergence of AC and NAC [11]}. [12]}, [13]}, [14]} perform the finite sample analysis of NAC under tabular setting, and [15]}, [16]}, [17]}, [18]}, [19]}, [20]}, [21]}, [22]}, [23]} establish the finite-sample bounds of AC in function approximation setting. To the best of our knowledge, the best sample complexity bound of AC algorithms is provided in [13]}, where the authors characterize an \(\tilde{\mathcal {O}}(\epsilon ^{-2})\)  sample complexity. However, [13]} only studies tabular RL in the on-policy setting.
