Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.04477 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911004207611904 |
|---|---|
| author | Lee, Jongmin Bravo, Mario Cominetti, Roberto |
| author_facet | Lee, Jongmin Bravo, Mario Cominetti, Roberto |
| contents | We study a new model-free algorithm to compute $\varepsilon$-optimal policies for average reward Markov decision processes, in the weakly communicating case. Given a generative model, our procedure combines a recursive sampling technique with Halpern's anchored iteration, and computes an $\varepsilon$-optimal policy with sample and time complexity $\widetilde{O}(|\mathcal{S}||\mathcal{A}|\|h^*\|_{\text{sp}}^{2}/\varepsilon^{2})$ both in high probability and in expectation. To our knowledge, this is the best complexity among model-free algorithms, matching the known lower bound up to a factor $\|h^*\|_{\text{sp}}$. Although the complexity bound involves the span seminorm $\|h^*\|_{\text{sp}}$ of the unknown bias vector, the algorithm requires no prior knowledge and implements a stopping rule which guarantees with probability 1 that the procedure terminates in finite time. We also analyze how these techniques can be adapted for discounted MDPs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04477 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Sample Complexity for MDPs via Anchoring Lee, Jongmin Bravo, Mario Cominetti, Roberto Optimization and Control Data Structures and Algorithms We study a new model-free algorithm to compute $\varepsilon$-optimal policies for average reward Markov decision processes, in the weakly communicating case. Given a generative model, our procedure combines a recursive sampling technique with Halpern's anchored iteration, and computes an $\varepsilon$-optimal policy with sample and time complexity $\widetilde{O}(|\mathcal{S}||\mathcal{A}|\|h^*\|_{\text{sp}}^{2}/\varepsilon^{2})$ both in high probability and in expectation. To our knowledge, this is the best complexity among model-free algorithms, matching the known lower bound up to a factor $\|h^*\|_{\text{sp}}$. Although the complexity bound involves the span seminorm $\|h^*\|_{\text{sp}}$ of the unknown bias vector, the algorithm requires no prior knowledge and implements a stopping rule which guarantees with probability 1 that the procedure terminates in finite time. We also analyze how these techniques can be adapted for discounted MDPs. |
| title | Near-Optimal Sample Complexity for MDPs via Anchoring |
| topic | Optimization and Control Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.04477 |