Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments

2023/10/31 by Ali̇ Devran Kara, Serdar Yüksel, Kara, Ali Devran +1 · 2 citations
Decision Sciences · Economics, Econometrics and Finance · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Economic Policies and Impacts #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.2311.00123

openalex publication_date 2023/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

As a primary contribution, we present a convergence theorem for stochastic iterations, and in particular, Q-learning iterates, under a general, possibly non-Markovian, stochastic environment. Our conditions for convergence involve an ergodicity and a positivity criterion. We provide a precise characterization on the limit of the iterates and conditions on the environment and initializations for convergence. As our second contribution, we discuss the implications and applications of this theorem to a variety of stochastic control problems with non-Markovian environments involving (i) quantized approximations of fully observed Markov Decision Processes (MDPs) with continuous spaces (where quantization break down the Markovian structure), (ii) quantized approximations of belief-MDP reduced partially observable MDPS (POMDPs) with weak Feller continuity and a mild version of filter stability (which requires the knowledge of the model by the controller), (iii) finite window approximations of POMDPs under a uniform controlled filter stability (which does not require the knowledge of the model), and (iv) for multi-agent models where convergence of learning dynamics to a new class of equilibria, subjective Q-learning equilibria, will be studied. In addition to the convergence theorem, some implications of the theorem above are new to the literature and others are interpreted as applications of the convergence theorem. Some open problems are noted.

Cited by

• Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spaces
• Convergence of regularized agent-state-based Q-learning in POMDPs

Related

• Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity
• Approximate Q-Learning for Controlled Diffusion Processes and its Near Optimality
• Approximate information state based convergence analysis of recurrent Q-learning
• Convex Q Learning in a Stochastic Environment: Extended Version
• Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability