High-probability sample complexities for policy evaluation with linear function approximation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910430657511424 |
|---|---|
| author | Li, Gen Wu, Weichen Chi, Yuejie Ma, Cong Rinaldo, Alessandro Wei, Yuting |
| author_facet | Li, Gen Wu, Weichen Chi, Yuejie Ma, Cong Rinaldo, Alessandro Wei, Yuting |
| contents | This paper is concerned with the problem of policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes. We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms: the temporal difference (TD) learning algorithm and the two-timescale linear TD with gradient correction (TDC) algorithm. In both the on-policy setting, where observations are generated from the target policy, and the off-policy setting, where samples are drawn from a behavior policy potentially different from the target policy, we establish the first sample complexity bound with high-probability convergence guarantee that attains the optimal dependence on the tolerance level. We also exhihit an explicit dependence on problem-related quantities, and show in the on-policy setting that our upper bound matches the minimax lower bound on crucial problem parameters, including the choice of the feature maps and the problem dimension. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_19001 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | High-probability sample complexities for policy evaluation with linear function approximation Li, Gen Wu, Weichen Chi, Yuejie Ma, Cong Rinaldo, Alessandro Wei, Yuting Machine Learning Information Theory Optimization and Control Statistics Theory This paper is concerned with the problem of policy evaluation with linear function approximation in discounted infinite horizon Markov decision processes. We investigate the sample complexities required to guarantee a predefined estimation error of the best linear coefficients for two widely-used policy evaluation algorithms: the temporal difference (TD) learning algorithm and the two-timescale linear TD with gradient correction (TDC) algorithm. In both the on-policy setting, where observations are generated from the target policy, and the off-policy setting, where samples are drawn from a behavior policy potentially different from the target policy, we establish the first sample complexity bound with high-probability convergence guarantee that attains the optimal dependence on the tolerance level. We also exhihit an explicit dependence on problem-related quantities, and show in the on-policy setting that our upper bound matches the minimax lower bound on crucial problem parameters, including the choice of the feature maps and the problem dimension. |
| title | High-probability sample complexities for policy evaluation with linear function approximation |
| topic | Machine Learning Information Theory Optimization and Control Statistics Theory |
| url | https://arxiv.org/abs/2305.19001 |