.png){kind=icon}
.png){kind=icon}
Return
Q-Learning With Uniformly Bounded Variance
.png){kind=icon}
PRE
AI
DOI：10.1109/TAC.2021.3133184.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Sample complexity bounds are a common performance metric in the reinforcement learning literature. In the discounted cost, infinite horizon setting, all of the known bounds can be arbitrarily large, as the discount factor approaches unity. These results seem to imply that a very large number of samples is required to achieve an epsilon-optimal policy. The objective of the present work is to introduce a new class of algorithms that have sample complexity uniformly bounded over all discount factors. One may argue that this is impossible, due to a recent min-max lower bound. The explanation is that these prior bounds concern value function approximation and not policy approximation. We show that the asymptotic covariance of the tabular Q-learning algorithm with an optimized step-size sequence is a quadratic function of a factor that goes to infinity, as discount factor approaches 1; an essentially known result. The new relative Q-learning algorithm proposed here is shown to have asymptotic covariance that is uniformly bounded over all discount factors.
Keywords:
Complexity theory
Convergence
Approximation algorithms
Upper bound
Reinforcement learning
Costs
Standards
Q-learning
reinforcement learning (RL)
stochastic optimal control
Journal
IF:
7
Papers:
1.3W
Citations:
6.7W
