Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917840133554176 |
|---|---|
| author | John, Philips George Bhattacharyya, Arnab Maniu, Silviu Myrisiotis, Dimitrios Wu, Zhenan |
| author_facet | John, Philips George Bhattacharyya, Arnab Maniu, Silviu Myrisiotis, Dimitrios Wu, Zhenan |
| contents | Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomial-time reinforcement learning algorithm (namely, LSVI-UCB) for the setting of linear Markov decision processes, and provided theoretical guarantees regarding its running time and regret. In real-world scenarios, however, the space usage of this algorithm can be prohibitive due to a utilized linear regression step. We propose and analyze two modifications of LSVI-UCB, which alternate periods of learning and not-learning, to reduce space and time usage while maintaining sublinear regret. We show experimentally, on synthetic data and real-world benchmarks, that our algorithms achieve low space usage and running time, while not significantly sacrificing regret. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_10906 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs John, Philips George Bhattacharyya, Arnab Maniu, Silviu Myrisiotis, Dimitrios Wu, Zhenan Machine Learning Data Structures and Algorithms Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomial-time reinforcement learning algorithm (namely, LSVI-UCB) for the setting of linear Markov decision processes, and provided theoretical guarantees regarding its running time and regret. In real-world scenarios, however, the space usage of this algorithm can be prohibitive due to a utilized linear regression step. We propose and analyze two modifications of LSVI-UCB, which alternate periods of learning and not-learning, to reduce space and time usage while maintaining sublinear regret. We show experimentally, on synthetic data and real-world benchmarks, that our algorithms achieve low space usage and running time, while not significantly sacrificing regret. |
| title | Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.10906 |