Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iteration
Han-Dong Lim, Donghwan Lee · 2025
Read Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iteration by Han-Dong Lim, Donghwan Lee (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10865.txt.
Introduction
Han-Dong Lim and Donghwan Lee settle basic questions about the projected Bellman equation, a workhorse of reinforcement learning theory. When value functions are fit with a linear model, the Bellman equation must be projected onto that model, and the projected version may have no solution at all. Their 2025 paper studies two methods that chase it: linear Q-learning and approximate value iteration.
One condition, a strict dominance property of the projected map, ensures a solution exists and that Q-learning settles down. A second condition grows out of value iteration's own behavior, and the paper maps how the two relate. Side results cover what happens under an epsilon-greedy policy. RL theorists get firmer ground under methods practitioners already run.
Catalog record
| CREATOR | Han-Dong Lim, Donghwan Lee |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-10865
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Understanding the theoretical properties of projected Bellman equation, linear Q-learning, and approximate value iteration Han-Dong Lim, Donghwan Lee Abstract In this paper, we study the theoretical properties of the projected Bellman equation (PBE) and two algorithms to solve this equation: linear Q-learning and approximate value iteration (AVI). We consider two sufficient conditions for the existence of a solution to PBE : strictly negatively row dominating diagonal (SNRDD) assumption and a condition motivated by the convergence of AVI. The SNRDD assumption also ensures the convergence of linear Q-learning, and its relationship with the convergence of AVI is examined. Lastly, several interesting observations on the solution of PBE are provided when using ϵ {\epsilon} -greedy policy. 1 Introduction Reinforcement learning (RL) has achieved significant success, exemplified by the deep Q-network (DQN) ( Mnih et al.,, 2015 ) . This success can be largely attributed to two algorithms: Q-learning ( Watkins and Dayan,, 1992 ) and the approximate value iteration (AVI) ( Bertsekas,, 2011 ) . Understanding the behavior of these algorithms has been a central focus of extensive research. Q-learning, initially developed by Watkins and Dayan, (1992) in a tabular setup where Q -values are stored for every state-action pair, has since been the subject of considerable investigation. Both asymptotic and non-asymptotic analysis of the algorithm have been thoroughly explored in works such as ( Borkar and Meyn,, 2000 ; Even-Dar and Mansour,, 2003 ; Lee and He, 2020b, ; Chen et al.,, 2022 ; Lee,, 2024 ) , to list a few. Moving beyond the tabular setup, function approximation is commonly used to address the problem of large state-action spaces in practical scenarios. Specifically, we focus on the simplest form of approximation: the linear function approximation scheme. However, introducing function approximation brings several challenges. In the case of Q-learning with linear function approximation—referred to as linear Q-learning—two major issues arise: 1) the existence of a solution to the projected Bellman equation (PBE) that the algorithm aims to solve, and 2) the stability of the algorithm. While recent works have explored these challenges ( Melo and Ribeiro,, 2007 ; Meyn,, 2024 ) , there remains significant opportunity for further advancing our understanding in this area. Meanwhile, value iteration is one of the simplest algorithms in RL when the model is known. By incorporating linear function approximation into the value iteration framework, the approximate value iteration (AVI) scheme has been widely used Munos, (2007) ; Mann and Mannor, (2014) . AVI also seeks to solve the PBE as linear Q-learning does. Nonetheless, it is not well understood, when the AVI algorithm converges while linear Q-learning does not, and vice versa. Overall, the theoretical understanding of PBE and its related algorithms, specifically Q-learning and AVI, are not well-understood. This motivates our study, and the purpose of this paper is to extend our knowledge on these subjects. The main contributions of this study are outlined in the following: 1. A sufficient condition for existence and uniqueness of a solution to PBE: • We provide a thorough investigation of the existence and uniqueness of a solution to PBE under the assumption of a matrix having strictly negatively row dominating diagonals (SNRDD assumption), which is new in the literature. This assumption includes a wide class of settings: tabular and linear function approximation (with regularization). Moreover, our analysis considers various behavior and target policy scenarios including continuous or lispchitz policies. • A sufficient condition, derived from the AVI framework, is provided. We then explore its relationship to the SNRDD assumption, demonstrating that while the two are generally different, they can coincide under specific additional conditions. 2. We provide a new convergence proofs for a family of Q-learning algorithms and AVI algorithm, respectively. Furthermore, we provide examples where AVI converges while linear Q-learning does not, and vice-versa. • The proof of Q-learning relies on ODE arguments based on contraction theory ( Lohmiller and Slotine,, 1998 ) and the SNRDD assumption. This covers asynchronous tabular Q-learning, linear Q-learning with SNRDD assumption, and regularized Q-learning ( Lim and Lee,, 2024 ) . To author’s best knowledge, SNRDD is the first assumption that can be applied to prove convergence of both linear and tabular Q-learning in a unified way using a fixed behavior policy. Regarding regularized Q-learning, the existing assumptions on positiveness and orthogonality of feature matrix are relaxed. • We provide an example showing that, even though the SNRDD assumption ensures the convergence of Q-learning and the existence of a solution to the PBE, the resulting solution may still lead to a sub-optimal policy. • The convergence of AVI follows from the condition that guarantees existence and uniqueness of a solution to PBE. 3. Lastly, we provide two examples explaining the theoretical properties of solutions to PBE when {\epsilon} -greedy policy is used, which is not covered by previous analysis due to its discontinuity. The first example shows depending on the value of {\epsilon} , there is a chance of non-existence or multiplicity of the solution even though SNRDD condition is met. The second example shows a pathological phenomenon using {\epsilon} -greedy policy that increasing the parameter {\epsilon} can ensure a solution to PBE that yields an optimal policy, to which Q-learning cannot converge. Related Works: Melo and Ribeiro, (2007) ; Chen et al., (2022) studied the convergence of linear Q-learning with additional assumptions that might not be satisfied in the tabular setting. Meyn, (2024) ; Liu et al., (2025) considered using a version of {\epsilon} -softmax behavior policy, the so-called tamed-Gibbs policy, and established results that there exists a solution of PBE, and the learning parameters of Q-learning remain bounded. Nonetheless, the tamed-Gibbs policy requires several specific design choices. In contrast, we consider a different scenario and proof approach: existence of the solution is explored for continuous or lipschitz policy under the assumption of SNRDD. In proving the convergence of Q-learning, we consider an arbitrary fixed behavior policy, which is idealistic but different scenario, and this naturally extends the proof idea of Q-learning in the tabular setup. The proof relies on contraction theory ( Lohmiller and Slotine,, 1998 ) , and its connection offers new insights. Lim and Lee, (2024) studied Q-learning with an additional term that serves a similar role to l_{2} -regularization, referred to as regularized Q-learning. Under additional assumptions on the feature matrix, this ensures convergence to a unique point. Zhang et al., (2021) studied Q-learning using target network, projection and regularization. We show that target network, projection or any additional assumptions on feature matrix are not required to prove the convergence of regularized Q-learning. Several studies have proposed variations of linear Q-learning ( Chen et al.,, 2023 ; Maei et al.,, 2010 ; Devraj and Meyn,, 2017 ; Carvalho et al.,, 2020 ) which are summarized in the Appendix 15 . Although these methods ensure boundedness or convergence, the exact points to which the algorithm converges remain not well understood. The AVI scheme has been widely studied to tackle the challenges posed by large state-action spaces ( Bertsekas,, 2016 ) . Recent research has provided insights into the convergence properties of AVI, highlighting its close connection to algorithms that employ target network updates—a methodology inspired by the success of DQN. Lee and He, 2020a () explored