Metraipolis › archive › dc_b8752e38669b
Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice — arXiv:2305.13185
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2305.13185
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T09:32:21.420Z
- SHA-256 of the archived text
659893657a5589cddfbb18b4dd00661e980b9885f0c41cbb01c008807ac38292- Stable URL of this page
https://metraipolis.com/documento/dc_b8752e38669b
How to cite
Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice — arXiv:2305.13185 — arXiv (en), https://arxiv.org/abs/2305.13185 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b8752e38669b (Metraipolis archive dc_b8752e38669b, sha256 659893657a5589cddfbb18b4dd00661e980b9885f0c41cbb01c008807ac38292)
BibTeX
@misc{dcb8752e38669b,
title = {Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice — arXiv:2305.13185},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2305.13185},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b8752e38669b; sha256 659893657a5589cddfbb18b4dd00661e980b9885f0c41cbb01c008807ac38292},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2305.13185. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Mirror descent value iteration (MDVI), an abstraction of Kullback-Leibler (KL) and entropy-regularized reinforcement learning (RL), has served as the basis for recent high-performing practical RL algorithms. However, despite the use of function approximation in practice, the theoretical understanding of MDVI has been limited to tabular Markov decision processes (MDPs). We study MDVI with linear function approximation through its sample complexity required to identify an $\varepsilon$-optimal policy with probability $1-\delta$ under the settings of an infinite-horizon linear MDP, generative model, and G-optimal design. We demonstrate that least-squares regression weighted by the variance of an estimated optimal value function of the next state is crucial to achieving minimax optimality. Based on this observation, we present Variance-Weighted Least-Squares MDVI (VWLS-MDVI), the first theoretical algorithm that achieves nearly minimax optimal sample complexity for infinite-horizon linear MDPs. Furthermore, we propose a practical VWLS algorithm for value-based deep RL, Deep Variance Weighting (DVW). Our experiments demonstrate that DVW improves the performance of popular value-based deep RL algorithms on a set of MinAtar benchmarks. Tema degli esploratori: statistica e scienza dei dati (elenco arXiv stat.ML, nuovi lavori del giorno). Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2305.13185 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-06T08:24:13.948Z dalla pagina https://arxiv.org/list/stat.ML/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).