Fetching the paper…
Reading the bibliography…
We establish that an optimistic variant of Q-learning applied to a fixed-horizon episodic Markov decision process with an aggregated state representation incurs regret $\tilde{\mathcal{O}}(\sqrt{H^5 M K} + \epsilon HK)$, where $H$ is the horizon, $M$ is the number of aggregate states, $K$ is the number of episodes, and $\epsilon$ is the largest difference between any pair of optimal state-action values associated with a common aggregate state.
Stable Function Approximation in Dynamic Programming
Gordon, G. J · 1995
Earlier work this paper cites.
Feature-Based Methods for Large Scale Dynamic Programming
Tsitsiklis, J. N. and Van Roy, B · 1996
Earlier work this paper cites.
Least-Squares Policy Iteration
Lagoudakis, M. G. and Parr, R · 2003
Earlier work this paper cites.
PAC Model-Free Reinforcement Learning
Strehl, A. L., Li, L., Wiewiora, E., Langford, J., and Littman, M. L · 2006
Earlier work this paper cites.
Performance Loss Bounds for Approximate Value Iteration with State Aggregation
Van Roy, B · 2006
Earlier work this paper cites.
Finite-Time Bounds for Fitted Value Iteration
Munos, R. and Szepesvári, C · 2008
Earlier work this paper cites.
A Unifying Framework for Computational Reinforcement Learning Theory
Li, L · 2009
Earlier work this paper cites.
Near-Optimal Regret Bounds for Reinforcement Learning
Jaksch, T., Ortner, R., and Auer, P · 2010
Cited alongside, same era.
Speedy Q-Learning
Azar, M. G., Munos, R., Ghavamzadaeh, M., and Kappen, H. J · 2011
Cited alongside, same era.
(More) Efficient Reinforcement Learning via Posterior Sampling
Osband, I., Russo, D., and Van Roy, B · 2013
Cited alongside, same era.
Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E · 2017
Cited alongside, same era.
Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalization
Wen, Z. and Van Roy, B · 2017
Cited alongside, same era.
Is Q-Learning Provably Efficient?
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I · 2018
Cited alongside, same era.
Provably Efficient Reinforcement Learning with Linear Function Approximation
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I · 2019
Closest in time.
Deep Exploration via Randomized Value Functions
Osband, I., Russo, D., Wen, Z., and Van Roy, B · 2019
Closest in time.
Worst-Case Regret Bounds for Exploration via Randomized Value Functions
Russo, D · 2019
Closest in time.
On Value Function Learning, 2019
Van Roy, B · 2019
Closest in time.
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
Yang, L. F. and Wang, M · 2019
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G · 2019
Cited alongside, same era.
Yang, Z., Xie, Y., and Wang, Z · 2019
Closest in time.
Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
Zanette, A., Brandfonbrener, D., Pirotta, M., and Lazaric, A · 2019
Closest in time.