홈 › Papers

On the Convergence and Sample Complexity Analysis of Deep Q-Networks with $ε$-Greedy Exploration

2023-10-24 · Shuai Zhang, Hongkang Li, Meng Wang, Miao Liu, Pin-Yu Chen, Songtao Lu, Sijia Liu, Keerthiram Murugesan, Subhajit Chaudhury

This paper provides a theoretical understanding of Deep Q-Network (DQN) with the $\varepsilon$-greedy exploration in deep reinforcement learning. Despite the tremendous empirical achievement of the DQN, its theoretical characterization remains underexplored. First, the exploration strategy is either impractical or ignored in the existing analysis. Second, in contrast to conventional Q-learning algorithms, the DQN employs the target network and experience replay to acquire an unbiased estimation of the mean-square Bellman error (MSBE) utilized in training the Q-network. However, the existing theoretical analysis of DQNs lacks convergence analysis or bypasses the technical challenges by deploying a significantly overparameterized neural network, which is not computationally efficient. This paper provides the first theoretical convergence and sample complexity analysis of the practical setting of DQNs with $\epsilon$-greedy policy. We prove an iterative procedure with decaying $\epsilon$ converges to the optimal Q-value function geometrically. Moreover, a higher level of $\epsilon$ values enlarges the region of convergence but slows down the convergence, while the opposite holds for a lower level of $\epsilon$ values. Experiments justify our established theoretical insights on DQNs.

📄 PDF Abstract BibTeX arXiv:2310.16173

Code (0)

등록된 구현이 없습니다.

Tasks

Deep Reinforcement LearningQ-Learning

Methods 이 논문이 사용한 방법론

Dense Connections Dense Connections, or Fully Connected Connections, are a type of layer in a deep neural network that use a linear operation where every input is connected to every output…

Experience Replay Experience Replay is a replay memory technique used in reinforcement learning where we store the agent’s experiences at each time-step, $e\_{t} = \left(s\_{t}, a\_{t}, r\_{t},…

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} +…

Convolution A convolution is a type of matrix operation, consisting of a kernel, a small matrix of weights, that slides over input data performing element-wise multiplication with the…

DQN A DQN, or Deep Q-Network, approximates a state-value function in a Q-Learning framework with a neural network. In the Atari…

On the Convergence and Sample Complexity Analysis of Deep Q-Networks with $\epsilon$-Greedy Exploration

2023-09-21 · NeurIPS 2023 11

This paper provides a theoretical understanding of deep Q-Network (DQN) with the $\varepsilon$-greedy exploration in deep reinforcement learning. Despite the tremendous empirical achievement of the DQN, its theoretical c…

Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm

2021-01-26 · Sajad Khodadadian, Thinh T. Doan, Justin Romberg, Siva Theja Maguluri

Actor-critic style two-time-scale algorithms are one of the most popular methods in reinforcement learning, and have seen great empirical success. However, their performance is not completely understood theoretically. In…

Vocal Bursts Valence Prediction

Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity

2021-03-30 · ICLR 2021 1 · Shaocong Ma, Ziyi Chen, Yi Zhou, Shaofeng Zou

Greedy-GQ is a value-based reinforcement learning (RL) algorithm for optimal control. Recently, the finite-time analysis of Greedy-GQ has been developed under linear function approximation and Markovian sampling, and the…

Reinforcement Learning (RL)

Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms

2020-11-10 · Tengyu Xu, Yingbin Liang

Two timescale stochastic approximation (SA) has been widely used in value-based reinforcement learning algorithms. In the policy evaluation setting, it can model the linear and nonlinear temporal difference learning with…

reinforcement-learning Reinforcement Learning (RL)Vocal Bursts Valence Prediction

Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation

2022-06-19 · Christoph Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari 외

Myopic exploration policies such as epsilon-greedy, softmax, or Gaussian noise fail to explore efficiently in some reinforcement learning tasks and yet, they perform well in many others. In fact, in practice, they are of…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)