On the instability of local learning algorithms: Q-learning can fail in infinite state spaces
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908622145978368 |
|---|---|
| author | Ayesta, Urtzi Foss, Sergey Jonckheere, Matthieu Puricelli, Vittorio |
| author_facet | Ayesta, Urtzi Foss, Sergey Jonckheere, Matthieu Puricelli, Vittorio |
| contents | We investigate the challenges of applying model-free reinforcement learning algorithms, like online Q-learning, to infinite state space Markov Decision Processes (MDPs). We first introduce the notion of Local Learning Processes (LLPs), where agents make decisions based solely on local information, and we show that Q-learning can be seen as a specific instance of an LLP. Using renewal techniques, we analyze LLPs and demonstrate their instability under certain drift and initial conditions, revealing fundamental limitations in infinite state spaces. In particular, we show that while asymptotically optimal in finite settings, Q-learning can face instability and strict sub-optimality in infinite spaces. Our findings are illustrated through queueing system examples drawn from load balancing and server allocation. The study underscores the need for new theoretical frameworks and suggests future research into nonlocal Q-learning variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25572 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the instability of local learning algorithms: Q-learning can fail in infinite state spaces Ayesta, Urtzi Foss, Sergey Jonckheere, Matthieu Puricelli, Vittorio Probability We investigate the challenges of applying model-free reinforcement learning algorithms, like online Q-learning, to infinite state space Markov Decision Processes (MDPs). We first introduce the notion of Local Learning Processes (LLPs), where agents make decisions based solely on local information, and we show that Q-learning can be seen as a specific instance of an LLP. Using renewal techniques, we analyze LLPs and demonstrate their instability under certain drift and initial conditions, revealing fundamental limitations in infinite state spaces. In particular, we show that while asymptotically optimal in finite settings, Q-learning can face instability and strict sub-optimality in infinite spaces. Our findings are illustrated through queueing system examples drawn from load balancing and server allocation. The study underscores the need for new theoretical frameworks and suggests future research into nonlocal Q-learning variants. |
| title | On the instability of local learning algorithms: Q-learning can fail in infinite state spaces |
| topic | Probability |
| url | https://arxiv.org/abs/2510.25572 |