Optimizing Successive Over-Relaxation Q-Learning With Deterministic Perturbation Gradient Search

Successive Over-Relaxation Q-learning (SOR-QL) has been proposed recently as an alternative to the widely popular Q-learning algorithm as it is seen to provide better performance where applicable. However, several limitations exist in SOR-QL that make the algorithm less useful in real-world applications. In particular, SOR-QL requires knowledge of transition probabilities and a constraining requirement of having a positive probability of self-transition to each state. Further, the actual parameter utilized in SOR-QL is kept below an unknown optimal threshold. In order to overcome these limitations, we propose an optimized variant of SOR-QL that optimizes its associated relaxation parameter directly. Our algorithm does not make use of transition probabilities at all and directly optimizes the relaxation parameter. Further, we do not impose the aforementioned special structure on the transition probabilities. Our resulting proposed algorithm is a purely data-driven, two-timescale stochastic approximation scheme, where on the slower timescale, the relaxation parameter in SOR-QL is updated, and on the faster timescale, the SOR-QL update is performed. We prove the asymptotic convergence of our algorithm. Further, experimental results demonstrate the superiority of our algorithm over various existing state-of-the-art algorithms as it achieves better computational time in the majority of the cases and the least cost (as an error) performance. Our algorithm outperforms the next best-performing algorithm in terms of average error and standard error metrics by two to six times and three to ten times, respectively, across different RL environments.