Linear Reinforcement Learning with Ball Structure Action Space

Zeyu Jia, Randy Jia, Dhruv Madeka, Dean P. Foster
Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:755-775, 2023.

Abstract

We study the problem of Reinforcement Learning (RL) with linear function approximation, i.e. assuming the optimal action-value function is linear in a known $d$-dimensional feature mapping. Unfortunately, however, based on only this assumption, the worst case sample complexity has been shown to be exponential, even under a generative model. Instead of making further assumptions on the MDP or value functions, we assume that our action space is such that there always exist playable actions to explore any direction of the feature space. We formalize this assumption as a “ball structure” action space, and show that being able to freely explore the feature space allows for efficient RL. In particular, we propose a sample-efficient RL algorithm (BallRL) that learns an $\epsilon$-optimal policy using only $\tilde{\mathcal{O}}\left(\frac{H^5d^3}{\epsilon^3}\right)$ number of trajectories.

Cite this Paper

BibTeX
@InProceedings{pmlr-v201-jia23a, title = {Linear Reinforcement Learning with Ball Structure Action Space}, author = {Jia, Zeyu and Jia, Randy and Madeka, Dhruv and Foster, Dean P.}, booktitle = {Proceedings of The 34th International Conference on Algorithmic Learning Theory}, pages = {755--775}, year = {2023}, editor = {Agrawal, Shipra and Orabona, Francesco}, volume = {201}, series = {Proceedings of Machine Learning Research}, month = {20 Feb--23 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v201/jia23a/jia23a.pdf}, url = {https://proceedings.mlr.press/v201/jia23a.html}, abstract = {We study the problem of Reinforcement Learning (RL) with linear function approximation, i.e. assuming the optimal action-value function is linear in a known $d$-dimensional feature mapping. Unfortunately, however, based on only this assumption, the worst case sample complexity has been shown to be exponential, even under a generative model. Instead of making further assumptions on the MDP or value functions, we assume that our action space is such that there always exist playable actions to explore any direction of the feature space. We formalize this assumption as a “ball structure” action space, and show that being able to freely explore the feature space allows for efficient RL. In particular, we propose a sample-efficient RL algorithm (BallRL) that learns an $\epsilon$-optimal policy using only $\tilde{\mathcal{O}}\left(\frac{H^5d^3}{\epsilon^3}\right)$ number of trajectories.} }
Endnote
%0 Conference Paper %T Linear Reinforcement Learning with Ball Structure Action Space %A Zeyu Jia %A Randy Jia %A Dhruv Madeka %A Dean P. Foster %B Proceedings of The 34th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Shipra Agrawal %E Francesco Orabona %F pmlr-v201-jia23a %I PMLR %P 755--775 %U https://proceedings.mlr.press/v201/jia23a.html %V 201 %X We study the problem of Reinforcement Learning (RL) with linear function approximation, i.e. assuming the optimal action-value function is linear in a known $d$-dimensional feature mapping. Unfortunately, however, based on only this assumption, the worst case sample complexity has been shown to be exponential, even under a generative model. Instead of making further assumptions on the MDP or value functions, we assume that our action space is such that there always exist playable actions to explore any direction of the feature space. We formalize this assumption as a “ball structure” action space, and show that being able to freely explore the feature space allows for efficient RL. In particular, we propose a sample-efficient RL algorithm (BallRL) that learns an $\epsilon$-optimal policy using only $\tilde{\mathcal{O}}\left(\frac{H^5d^3}{\epsilon^3}\right)$ number of trajectories.
APA
Jia, Z., Jia, R., Madeka, D. & Foster, D.P.. (2023). Linear Reinforcement Learning with Ball Structure Action Space. Proceedings of The 34th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 201:755-775 Available from https://proceedings.mlr.press/v201/jia23a.html.

Related Material