Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.19254 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916761010438144 |
|---|---|
| author | Liu, Xinyu Xie, Zixuan Zhang, Shangtong |
| author_facet | Liu, Xinyu Xie, Zixuan Zhang, Shangtong |
| contents | $Q$-learning is one of the most fundamental reinforcement learning algorithms. It is widely believed that $Q$-learning with linear function approximation (i.e., linear $Q$-learning) suffers from possible divergence until the recent work Meyn (2024) which establishes the ultimate almost sure boundedness of the iterates of linear $Q$-learning. Building on this success, this paper further establishes the first $L^2$ convergence rate of linear $Q$-learning iterates (to a bounded set). Similar to Meyn (2024), we do not make any modification to the original linear $Q$-learning algorithm, do not make any Bellman completeness assumption, and do not make any near-optimality assumption on the behavior policy. All we need is an $ε$-softmax behavior policy with an adaptive temperature. The key to our analysis is the general result of stochastic approximations under Markovian noise with fast-changing transition functions. As a side product, we also use this general result to establish the $L^2$ convergence rate of tabular $Q$-learning with an $ε$-softmax behavior policy, for which we rely on a novel pseudo-contraction property of the weighted Bellman optimality operator. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_19254 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set Liu, Xinyu Xie, Zixuan Zhang, Shangtong Machine Learning Artificial Intelligence $Q$-learning is one of the most fundamental reinforcement learning algorithms. It is widely believed that $Q$-learning with linear function approximation (i.e., linear $Q$-learning) suffers from possible divergence until the recent work Meyn (2024) which establishes the ultimate almost sure boundedness of the iterates of linear $Q$-learning. Building on this success, this paper further establishes the first $L^2$ convergence rate of linear $Q$-learning iterates (to a bounded set). Similar to Meyn (2024), we do not make any modification to the original linear $Q$-learning algorithm, do not make any Bellman completeness assumption, and do not make any near-optimality assumption on the behavior policy. All we need is an $ε$-softmax behavior policy with an adaptive temperature. The key to our analysis is the general result of stochastic approximations under Markovian noise with fast-changing transition functions. As a side product, we also use this general result to establish the $L^2$ convergence rate of tabular $Q$-learning with an $ε$-softmax behavior policy, for which we rely on a novel pseudo-contraction property of the weighted Bellman optimality operator. |
| title | Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2501.19254 |