Minimax Regret Bounds for Reinforcement Learning Article Swipe

MAKE IMPACT

Mohammad Gheshlaghi Azar , Ian Osband , Rémi Munos · YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1703.05449

We consider the problem of provably optimal exploration in reinforcement learning for finite horizon MDPs. We show that an optimistic modification to value iteration achieves a regret bound of $\tilde{O}( \sqrt{HSAT} + H^2S^2A+H\sqrt{T})$ where $H$ is the time horizon, $S$ the number of states, $A$ the number of actions and $T$ the number of time-steps. This result improves over the best previous known bound $\tilde{O}(HS \sqrt{AT})$ achieved by the UCRL2 algorithm of Jaksch et al., 2010. The key significance of our new results is that when $T\geq H^3S^3A$ and $SA\geq H$, it leads to a regret of $\tilde{O}(\sqrt{HSAT})$ that matches the established lower bound of $Ω(\sqrt{HSAT})$ up to a logarithmic factor. Our analysis contains two key insights. We use careful application of concentration inequalities to the optimal value function as a whole, rather than to the transitions probabilities (to improve scaling in $S$), and we define Bernstein-based "exploration bonuses" that use the empirical variance of the estimated values at the next states (to improve scaling in $H$).

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/1703.05449

PDF

https://arxiv.org/pdf/1703.05449

OA Status

green

Cited By

50

References

20

Related Works

20

OpenAlex ID

https://openalex.org/W2604884452

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2604884452

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.1703.05449

Digital Object Identifier

Title

Minimax Regret Bounds for Reinforcement Learning

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2017

Year of publication

Publication date

2017-03-16

Full publication date if available

Authors

Mohammad Gheshlaghi Azar, Ian Osband, Rémi Munos

List of authors in order

Landing page

https://arxiv.org/abs/1703.05449

Publisher landing page

PDF URL

https://arxiv.org/pdf/1703.05449

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1703.05449

Direct OA link when available

Concepts

Regret, Logarithm, Combinatorics, Upper and lower bounds, Scaling, Minimax, Reinforcement learning, Omega, Mathematics, Horizon, Function (biology), Key (lock), Discrete mathematics, Computer science, Mathematical optimization, Physics, Statistics, Machine learning, Mathematical analysis, Quantum mechanics, Computer security, Geometry, Biology, Evolutionary biology

Top concepts (fields/topics) attached by OpenAlex

Cited by

50

Total citation count in OpenAlex

Citations by year (recent)

2025: 1, 2024: 2, 2023: 2, 2022: 3, 2021: 13

Per-year citation counts (last 5 years)

References (count)

20

Number of works referenced by this work

Related works (count)

20

Other works algorithmically related by OpenAlex

Full payload