Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913822704402432 |
|---|---|
| author | Lin, Max Qiushi Mei, Jincheng Aghaei, Matin Lu, Michael Dai, Bo Agarwal, Alekh Schuurmans, Dale Szepesvari, Csaba Vaswani, Sharan |
| author_facet | Lin, Max Qiushi Mei, Jincheng Aghaei, Matin Lu, Michael Dai, Bo Agarwal, Alekh Schuurmans, Dale Szepesvari, Csaba Vaswani, Sharan |
| contents | Policy gradient (PG) methods have played an essential role in the empirical successes of reinforcement learning. In order to handle large state-action spaces, PG methods are typically used with function approximation. In this setting, the approximation error in modeling problem-dependent quantities is a key notion for characterizing the global convergence of PG methods. We focus on Softmax PG with linear function approximation (referred to as $\texttt{Lin-SPG}$) and demonstrate that the approximation error is irrelevant to the algorithm's global convergence even for the stochastic bandit setting. Consequently, we first identify the necessary and sufficient conditions on the feature representation that can guarantee the asymptotic global convergence of $\texttt{Lin-SPG}$. Under these feature conditions, we prove that $T$ iterations of $\texttt{Lin-SPG}$ with a problem-specific learning rate result in an $O(1/T)$ convergence to the optimal policy. Furthermore, we prove that $\texttt{Lin-SPG}$ with any arbitrary constant learning rate can ensure asymptotic global convergence to the optimal policy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_03155 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation Lin, Max Qiushi Mei, Jincheng Aghaei, Matin Lu, Michael Dai, Bo Agarwal, Alekh Schuurmans, Dale Szepesvari, Csaba Vaswani, Sharan Machine Learning Policy gradient (PG) methods have played an essential role in the empirical successes of reinforcement learning. In order to handle large state-action spaces, PG methods are typically used with function approximation. In this setting, the approximation error in modeling problem-dependent quantities is a key notion for characterizing the global convergence of PG methods. We focus on Softmax PG with linear function approximation (referred to as $\texttt{Lin-SPG}$) and demonstrate that the approximation error is irrelevant to the algorithm's global convergence even for the stochastic bandit setting. Consequently, we first identify the necessary and sufficient conditions on the feature representation that can guarantee the asymptotic global convergence of $\texttt{Lin-SPG}$. Under these feature conditions, we prove that $T$ iterations of $\texttt{Lin-SPG}$ with a problem-specific learning rate result in an $O(1/T)$ convergence to the optimal policy. Furthermore, we prove that $\texttt{Lin-SPG}$ with any arbitrary constant learning rate can ensure asymptotic global convergence to the optimal policy. |
| title | Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.03155 |