A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation

2023-11-26 · Heyang Zhao, Jiafan He, Quanquan Gu

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.

📄 PDF Abstract BibTeX arXiv:2311.15238

Code (0)

등록된 구현이 없습니다.

Tasks

Q-LearningReinforcement Learning (RL)

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation

2026-02-23 · Haochen Zhang, Zhong Zheng, Lingzhou Xue arxiv

We study gap-dependent performance guarantees for nearly minimax-optimal algorithms in reinforcement learning with linear function approximation. While prior works have established gap-dependent regret bounds in this set…

Reinforcement Learning

Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning

2025-06-05 · Haochen Zhang, Zhong Zheng, Lingzhou Xue

Motivated by real-world settings where data collection and policy deployment -- whether for a single agent or across multiple agents -- are costly, we study the problem of on-policy single-agent reinforcement learning (R…

Q-Learning Reinforcement Learning (RL)

Combinatorial Semi-Bandit in the Non-Stationary Environment

2020-02-10 · Wei Chen, Li-Wei Wang, Haoyu Zhao, Kai Zheng

In this paper, we investigate the non-stationary combinatorial semi-bandit problem, both in the switching case and in the dynamic case. In the general case where (a) the reward function is non-linear, (b) arms may be pro…

Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes

2022-12-12 · Jiafan He, Heyang Zhao, Dongruo Zhou, Quanquan Gu

We study reinforcement learning (RL) with linear function approximation. For episodic time-inhomogeneous linear Markov decision processes (linear MDPs) whose transition probability can be parameterized as a linear functi…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs

2023-02-24 · Dan Qiao, Ming Yin, Yu-Xiang Wang

In many real-life reinforcement learning (RL) problems, deploying new policies is costly. In those scenarios, algorithms must solve exploration (which requires adaptivity) while switching the deployed policy sparsely (wh…