Fetching the paper…

Reading the bibliography…

2016

On Lower Bounds for Regret in Reinforcement Learning

Osband, Ian, Van Roy, Benjamin

Original
PDF
Post on X

Understand

This is a brief technical note to clarify the state of lower bounds on regret for reinforcement learning.

In particular, this paper: - Reproduces a lower bound on regret for reinforcement learning, similar to the result of Theorem 5 in the journal UCRL2 paper (Jaksch et al 2010).
- Clarifies that the proposed proof of Theorem 6 in the REGAL paper (Bartlett and Tewari 2009) does not hold using the standard techniques without further work.
We suggest that this result should instead be considered a conjecture as it has no rigorous proof.

On Lower Bounds for Regret in Reinforcement Learning · Around

Built on

Asymptotically efficient adaptive allocation rules
Tze Leung Lai and Herbert Robbins · 1985
Earlier work this paper cites.
REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs
Peter L. Bartlett and Ambuj Tewari · 2009
Earlier work this paper cites.
Near-optimal regret bounds for reinforcement learning
Thomas Jaksch, Ronald Ortner, and Peter Auer · 2010
Earlier work this paper cites.

Similar

Regret analysis of stochastic and nonstochastic multi-armed bandit problems
Original
Sébastien Bubeck and Nicolò Cesa-Bianchi · 2012
Cited alongside, same era.
PAC bounds for discounted MDPs
Tor Lattimore and Marcus Hutter · 2012
Cited alongside, same era.
(More) efficient reinforcement learning via posterior sampling
Original
Ian Osband, Daniel Russo, and Benjamin Van Roy · 2013
Cited alongside, same era.

Then

Sample complexity of episodic fixed-horizon reinforcement learning
Christoph Dann and Emma Brunskill · 2015
Later among the works it cites.
Why is posterior sampling better than optimism for reinforcement learning
Original
Ian Osband and Benjamin Van Roy · 2016
Closest in time.

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…