Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.18186 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913928139767808 |
|---|---|
| author | Tiapkin, Daniil Belomestny, Denis Calandriello, Daniele Moulines, Eric Munos, Remi Naumov, Alexey Perrault, Pierre Valko, Michal Menard, Pierre |
| author_facet | Tiapkin, Daniil Belomestny, Denis Calandriello, Daniele Moulines, Eric Munos, Remi Naumov, Alexey Perrault, Pierre Valko, Michal Menard, Pierre |
| contents | In this paper, we introduce Randomized Q-learning (RandQL), a novel randomized model-free algorithm for regret minimization in episodic Markov Decision Processes (MDPs). To the best of our knowledge, RandQL is the first tractable model-free posterior sampling-based algorithm. We analyze the performance of RandQL in both tabular and non-tabular metric space settings. In tabular MDPs, RandQL achieves a regret bound of order $\widetilde{O}(\sqrt{H^{5}SAT})$, where $H$ is the planning horizon, $S$ is the number of states, $A$ is the number of actions, and $T$ is the number of episodes. For a metric state-action space, RandQL enjoys a regret bound of order $\widetilde{O}(H^{5/2} T^{(d_z+1)/(d_z+2)})$, where $d_z$ denotes the zooming dimension. Notably, RandQL achieves optimistic exploration without using bonuses, relying instead on a novel idea of learning rate randomization. Our empirical study shows that RandQL outperforms existing approaches on baseline exploration environments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_18186 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Model-free Posterior Sampling via Learning Rate Randomization Tiapkin, Daniil Belomestny, Denis Calandriello, Daniele Moulines, Eric Munos, Remi Naumov, Alexey Perrault, Pierre Valko, Michal Menard, Pierre Machine Learning In this paper, we introduce Randomized Q-learning (RandQL), a novel randomized model-free algorithm for regret minimization in episodic Markov Decision Processes (MDPs). To the best of our knowledge, RandQL is the first tractable model-free posterior sampling-based algorithm. We analyze the performance of RandQL in both tabular and non-tabular metric space settings. In tabular MDPs, RandQL achieves a regret bound of order $\widetilde{O}(\sqrt{H^{5}SAT})$, where $H$ is the planning horizon, $S$ is the number of states, $A$ is the number of actions, and $T$ is the number of episodes. For a metric state-action space, RandQL enjoys a regret bound of order $\widetilde{O}(H^{5/2} T^{(d_z+1)/(d_z+2)})$, where $d_z$ denotes the zooming dimension. Notably, RandQL achieves optimistic exploration without using bonuses, relying instead on a novel idea of learning rate randomization. Our empirical study shows that RandQL outperforms existing approaches on baseline exploration environments. |
| title | Model-free Posterior Sampling via Learning Rate Randomization |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2310.18186 |