Zap Q-Learning for Optimal Stopping Time Problems
This work addresses the convergence bottleneck in reinforcement learning for optimal stopping, offering a faster algorithm that is incremental but proven effective in specific domains like finance.
The paper tackles the slow convergence of Q-learning for optimal stopping problems in Markov chains by proposing the Zap-Q-learning algorithm, which achieves optimal convergence rates and is proven to converge under linear function approximation, with fast convergence demonstrated in a finance example.
The objective in this paper is to obtain fast converging reinforcement learning algorithms to approximate solutions to the problem of discounted cost optimal stopping in an irreducible, uniformly ergodic Markov chain, evolving on a compact subset of $\mathbb{R}^n$. We build on the dynamic programming approach taken by Tsitsikilis and Van Roy, wherein they propose a Q-learning algorithm to estimate the optimal state-action value function, which then defines an optimal stopping rule. We provide insights as to why the convergence rate of this algorithm can be slow, and propose a fast-converging alternative, the "Zap-Q-learning" algorithm, designed to achieve optimal rate of convergence. For the first time, we prove the convergence of the Zap-Q-learning algorithm under the assumption of linear function approximation setting. We use ODE analysis for the proof, and the optimal asymptotic variance property of the algorithm is reflected via fast convergence in a finance example.