Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910632253587456 |
|---|---|
| author | Chen, Suei-Wen Ross, Keith Youssef, Pierre |
| author_facet | Chen, Suei-Wen Ross, Keith Youssef, Pierre |
| contents | Monte Carlo Exploring Starts (MCES), which aims to learn the optimal policy using only sample returns, is a simple and natural algorithm in reinforcement learning which has been shown to converge under various conditions. However, the convergence rate analysis for MCES-style algorithms in the form of sample complexity has received very little attention. In this paper we develop a finite sample bound for a modified MCES algorithm which solves the stochastic shortest path problem. To this end, we prove a novel result on the convergence rate of the policy iteration algorithm. This result implies that with probability at least $1-δ$, the algorithm returns an optimal policy after $\tilde{O}(SAK^3\log^3\frac{1}δ)$ sampled episodes, where $S$ and $A$ denote the number of states and actions respectively, $K$ is a proxy for episode length, and $\tilde{O}$ hides logarithmic factors and constants depending on the rewards of the environment that are assumed to be known. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_02994 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning Chen, Suei-Wen Ross, Keith Youssef, Pierre Machine Learning Monte Carlo Exploring Starts (MCES), which aims to learn the optimal policy using only sample returns, is a simple and natural algorithm in reinforcement learning which has been shown to converge under various conditions. However, the convergence rate analysis for MCES-style algorithms in the form of sample complexity has received very little attention. In this paper we develop a finite sample bound for a modified MCES algorithm which solves the stochastic shortest path problem. To this end, we prove a novel result on the convergence rate of the policy iteration algorithm. This result implies that with probability at least $1-δ$, the algorithm returns an optimal policy after $\tilde{O}(SAK^3\log^3\frac{1}δ)$ sampled episodes, where $S$ and $A$ denote the number of states and actions respectively, $K$ is a proxy for episode length, and $\tilde{O}$ hides logarithmic factors and constants depending on the rewards of the environment that are assumed to be known. |
| title | Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2410.02994 |