A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915531258331136 |
|---|---|
| author | Zhao, Heyang He, Jiafan Gu, Quanquan |
| author_facet | Zhao, Heyang He, Jiafan Gu, Quanquan |
| contents | The exploration-exploitation dilemma has been a central challenge in reinforcement learning (RL) with complex model classes. In this paper, we propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation. Our key algorithmic design includes (1) a general deterministic policy-switching strategy that achieves low switching cost, (2) a monotonic value function structure with carefully controlled function class complexity, and (3) a variance-weighted regression scheme that exploits historical trajectories with high data efficiency. MQL-UCB achieves minimax optimal regret of $\tilde{O}(d\sqrt{HK})$ when $K$ is sufficiently large and near-optimal policy switching cost of $\tilde{O}(dH)$, with $d$ being the eluder dimension of the function class, $H$ being the planning horizon, and $K$ being the number of episodes.
Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_15238 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation Zhao, Heyang He, Jiafan Gu, Quanquan Machine Learning Optimization and Control The exploration-exploitation dilemma has been a central challenge in reinforcement learning (RL) with complex model classes. In this paper, we propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation. Our key algorithmic design includes (1) a general deterministic policy-switching strategy that achieves low switching cost, (2) a monotonic value function structure with carefully controlled function class complexity, and (3) a variance-weighted regression scheme that exploits historical trajectories with high data efficiency. MQL-UCB achieves minimax optimal regret of $\tilde{O}(d\sqrt{HK})$ when $K$ is sufficiently large and near-optimal policy switching cost of $\tilde{O}(dH)$, with $d$ being the eluder dimension of the function class, $H$ being the planning horizon, and $K$ being the number of episodes. Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation. |
| title | A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2311.15238 |