Fetching the paper…

Reading the bibliography…

Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs · Around

2020

Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs

He, Jiafan, Zhou, Dongruo, Gu, Quanquan

Original
PDF
Post on X

Understand

We study the reinforcement learning problem for discounted Markov Decision Processes (MDPs) under the tabular setting.

We propose a model-based algorithm named UCBVI-$\gamma$, which is based on the \emph{optimism in the face of uncertainty principle} and the Bernstein-type bonus.
We show that UCBVI-$\gamma$ achieves an $\tilde{O}\big({\sqrt{SAT}}/{(1-\gamma)^{1.5}}\big)$ regret, where $S$ is the number of states, $A$ is the number of actions, $\gamma$ is the discount factor and $T$ is the number of steps.
In addition, we construct a class of hard MDPs and show that for any algorithm, the expected regret is at least $\tilde{\Omega}\big({\sqrt{SAT}}/{(1-\gamma)^{1.5}}\big)$.

Built on

Q-learning with ucb exploration is sample efficient for infinite-horizon mdp
Original
Dong, K · 1901
Earlier work this paper cites.
Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds
Original
Zanette, A · 1901
Earlier work this paper cites.
Model-based reinforcement learning with a generative model is minimax optimal
Original
Agarwal, A · 1906
Earlier work this paper cites.
Variance-reduced q q -learning is minimax optimal
Original
Wainwright, M. J · 1906
Earlier work this paper cites.
Finite-sample convergence rates for q-learning and indirect algorithms
Kearns, M. J · 1999
Earlier work this paper cites.
R-max-a general polynomial time algorithm for near-optimal reinforcement learning
Brafman, R. I · 2002
Earlier work this paper cites.
On the sample complexity of reinforcement learning
Kakade, S. M · 2003
Earlier work this paper cites.
Almost optimal model-free reinforcement learning via reference-advantage decomposition
Original
Zhang, Z · 2004
Earlier work this paper cites.
Model-based reinforcement learning with value-targeted regression
Original
Ayoub, A · 2006
Earlier work this paper cites.
Prediction, learning, and games
Cesa-Bianchi, N · 2006
Earlier work this paper cites.
On optimism in model-based reinforcement learning
Original
Pacchiano, A · 2006
Earlier work this paper cites.

Similar

Pac model-free reinforcement learning
Strehl, A. L · 2006
Cited alongside, same era.
Model-free reinforcement learning: from clipped pseudo-regret to sample complexity
Original
Zhang, Z · 2006
Cited alongside, same era.
A unifying view of optimism in episodic reinforcement learning
Original
Neu, G · 2007
Cited alongside, same era.
An analysis of model-based interval estimation for markov decision processes
Strehl, A. L · 2008
Cited alongside, same era.
Empirical bernstein bounds and sample variance penalization
Original
Maurer, A · 2009
Cited alongside, same era.

Then

On lower bounds for regret in reinforcement learning
Original
Osband, I · 2016
Later among the works it cites.
Minimax regret bounds for reinforcement learning
Azar, M. G · 2017
Later among the works it cites.
Why is posterior sampling better than optimism for reinforcement learning?
Osband, I · 2017
Later among the works it cites.
Randomized linear programming solves the discounted markov decision problem in nearly-linear running time
Original
Wang, M · 2017
Later among the works it cites.
Is q-learning provably efficient?
Jin, C · 2018
Later among the works it cites.
Policy certificates: Towards accountable reinforcement learning
Dann, C · 2019

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…

Near-optimal regret bounds for reinforcement learning

Jaksch, T · 2010

Cited alongside, same era.

Model-based reinforcement learning with nearly tight exploration complexity bounds

Szita, I · 2010

Cited alongside, same era.

Pac bounds for discounted mdps

Lattimore, T · 2012

Cited alongside, same era.

Minimax pac bounds on the sample complexity of reinforcement learning with a generative model

Azar, M. G · 2013

Cited alongside, same era.

Sample complexity of episodic fixed-horizon reinforcement learning

Dann, C · 2015

Cited alongside, same era.

Near-optimal time and sample complexities for for solving discounted markov decision process with a generative model

Sidford, A

Cited in the paper.

Variance reduced value iteration and faster algorithms for solving markov decision processes

Sidford, A

Cited in the paper.

Later among the works it cites.

Worst-case regret bounds for exploration via randomized value functions

Russo, D · 2019

Later among the works it cites.

Non-asymptotic gap-dependent regret bounds for tabular mdps

Simchowitz, M · 2019

Later among the works it cites.

Regret bounds for discounted mdps

Liu, S · 2020

Closest in time.

Q-learning with logarithmic regret 1576–1584

Yang, K · 2021

Closest in time.