Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity

Reinforcement learning algorithms often require finiteness of state and\naction spaces in Markov decision processes (MDPs) (also called controlled\nMarkov chains) and various efforts have been made in the literature towards the\napplicability of such algorithms for continuous state and action spaces. In\nthis paper, we show that under very mild regularity conditions (in particular,\ninvolving only weak continuity of the transition kernel of an MDP), Q-learning\nfor standard Borel MDPs via quantization of states and actions (called\nQuantized Q-Learning) converges to a limit, and furthermore this limit\nsatisfies an optimality equation which leads to near optimality with either\nexplicit performance bounds or which are guaranteed to be asymptotically\noptimal. Our approach builds on (i) viewing quantization as a measurement\nkernel and thus a quantized MDP as a partially observed Markov decision process\n(POMDP), (ii) utilizing near optimality and convergence results of Q-learning\nfor POMDPs, and (iii) finally, near-optimality of finite state model\napproximations for MDPs with weakly continuous kernels which we show to\ncorrespond to the fixed point of the constructed POMDP. Thus, our paper\npresents a very general convergence and approximation result for the\napplicability of Q-learning for continuous MDPs.\n