Built on

Q-learning
Watkins, Chris J. and Dayan, Peter · 1992
Earlier work this paper cites.
Efficient reinforcement learning
Fiechter, Claude Nicolas · 1994
Earlier work this paper cites.
Markov Decision Processes - Discrete Stochastic Dynamic Programming
Puterman, Martin L · 1994
Earlier work this paper cites.
Reinforcement Learning: An Introduction
Sutton, Richard S. and Barto, Andrew G · 1998
Earlier work this paper cites.
On the Sample Complexity of Reinforcement Learning
Kakade, Sham · 2003
Earlier work this paper cites.
Almost optimal model-free reinforcement learning via reference-advantage decomposition
Original
Zhang, Zihan, Zhou, Yuan, and Ji, Xiangyang · 2004
Earlier work this paper cites.
Is reinforcement learning more difficult than bandits? A near-optimal algorithm escaping the curse of horizon
Original
Zhang, Zihan, Ji, Xiangyang, and Du, Simon S · 2009
Earlier work this paper cites.
Near-optimal regret bounds for reinforcement learning
Jaksch, Thomas, Ortner, Ronald, and Auer, Peter · 2010
Earlier work this paper cites.

Similar

Model-based reinforcement learning with nearly tight exploration complexity bounds
Szita, István and Szepesvári, Csaba · 2010
Cited alongside, same era.
Speedy Q-learning
Azar, Mohammad Gheshlaghi, Munos, Remi, Ghavamzadeh, Mohammad, and Kappen, Hilbert J · 2011
Cited alongside, same era.
Minimax regret bounds for reinforcement learning
Original
Azar, Mohammad Gheshlaghi, Osband, Ian, and Munos, Rémi · 2017
Cited alongside, same era.
Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning
Original
Dann, Christoph, Lattimore, Tor, and Brunskill, Emma · 2017
Cited alongside, same era.
Efficient bias-span-constrained exploration-exploitation in reinforcement learning
Original
Fruit, Ronan, Pirotta, Matteo, Lazaric, Alessandro, and Ortner, Ronald · 2018
Cited alongside, same era.

Then

Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds
Original
Zanette, Andrea and Brunskill, Emma · 2019
Later among the works it cites.
Regret bounds for kernel-based reinforcement learning
Original
Domingues, Omar D., Ménard, Pierre, Pirotta, Matteo, Kaufmann, Emilie, and Valko, Michal · 2020
Later among the works it cites.
Adaptive discretization for model-based reinforcement learning
Original
Sinclair, Sean R., Wang, Tianyu, Jain, Gauri, Banerjee, Siddhartha, and Yu, Christina Lee · 2020
Later among the works it cites.
Is long horizon reinforcement learning more difficult than short horizon reinforcement learning?
Original
Wang, Ruosong, Du, Simon S., Yang, Lin F., and Kakade, Sham M · 2020
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2021

UCB Momentum Q-learning: Correcting the bias without forgetting

Menard, Pierre, Domingues, Omar Darwiche, Shang, Xuedong et al.

Understand

We propose UCBMQ, Upper Confidence Bound Momentum Q-learning, a new algorithm for reinforcement learning in tabular and possibly stage-dependent, episodic Markov decision process.

UCBMQ is based on Q-learning where we add a momentum term and rely on the principle of optimism in face of uncertainty to deal with exploration.
Our new technical ingredient of UCBMQ is the use of momentum to correct the bias that Q-learning suffers while, at the same time, limiting the impact it has on the second-order term of the regret.
For UCBMQ, we are able to guarantee a regret of at most $O(\sqrt{H^3SAT}+ H^4 S A )$ where $H$ is the length of an episode, $S$ the number of states, $A$ the number of actions, $T$ the number of episodes and ignoring terms in poly-$\log(SAHT)$.

Built on

Q-learning
Watkins, Chris J. and Dayan, Peter · 1992
Earlier work this paper cites.
Efficient reinforcement learning
Fiechter, Claude Nicolas · 1994
Earlier work this paper cites.
Markov Decision Processes - Discrete Stochastic Dynamic Programming
Puterman, Martin L · 1994
Earlier work this paper cites.
Reinforcement Learning: An Introduction
Sutton, Richard S. and Barto, Andrew G · 1998
Earlier work this paper cites.
On the Sample Complexity of Reinforcement Learning
Kakade, Sham · 2003
Earlier work this paper cites.
Almost optimal model-free reinforcement learning via reference-advantage decomposition
Original
Zhang, Zihan, Zhou, Yuan, and Ji, Xiangyang · 2004
Earlier work this paper cites.
Is reinforcement learning more difficult than bandits? A near-optimal algorithm escaping the curse of horizon
Original
Zhang, Zihan, Ji, Xiangyang, and Du, Simon S · 2009
Earlier work this paper cites.
Near-optimal regret bounds for reinforcement learning
Jaksch, Thomas, Ortner, Ronald, and Auer, Peter · 2010
Earlier work this paper cites.

Similar

Model-based reinforcement learning with nearly tight exploration complexity bounds
Szita, István and Szepesvári, Csaba · 2010
Cited alongside, same era.
Speedy Q-learning
Azar, Mohammad Gheshlaghi, Munos, Remi, Ghavamzadeh, Mohammad, and Kappen, Hilbert J · 2011
Cited alongside, same era.
Minimax regret bounds for reinforcement learning
Original
Azar, Mohammad Gheshlaghi, Osband, Ian, and Munos, Rémi · 2017
Cited alongside, same era.
Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning
Original
Dann, Christoph, Lattimore, Tor, and Brunskill, Emma · 2017
Cited alongside, same era.
Efficient bias-span-constrained exploration-exploitation in reinforcement learning
Original
Fruit, Ronan, Pirotta, Matteo, Lazaric, Alessandro, and Ortner, Ronald · 2018
Cited alongside, same era.