An Engineered Empirical Bernstein Bound

Mark A. Burgess; Archie C. Chapman; Paul Scott

doi:10.1007/978-3-030-46133-1_6

An Engineered Empirical Bernstein Bound

Mark A. Burgess^*
, Archie C. Chapman
, Paul Scott

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

2 Citations (Scopus)

Abstract

We derive a tightened empirical Bernstein bound (EBB) on the variation of the sample mean from the population mean, and show that it improves the performance of upper confidence bound (UCB) methods in multi-armed bandit problems. Like other EBBs, our EBB is a concentration inequality for the variation of the sample mean in terms of the sample variance. Its derivation uses a combination of probability unions and Chernoff bounds for the mean of samples and mean of sample squares. Analysis reveals that our approach can tighten the best existing EBBs by about a third, and thereby halves the distance to a bound constructed with perfect variance information. We illustrate the practical usefulness of our novel EBB by applying it to a multi-armed bandit problem as a component of a UCB method. Our method outperforms existing approaches by producing lower expected regret than variants of UCB employing several other bounds, including state-of-the-art EBBs.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings
Editors	Ulf Brefeld, Elisa Fromont, Andreas Hotho, Arno Knobbe, Marloes Maathuis, Céline Robardet
Publisher	Springer
Pages	86-102
Number of pages	17
ISBN (Print)	9783030461324
DOIs	https://doi.org/10.1007/978-3-030-46133-1_6
Publication status	Published - 2020
Event	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2019 - Wurzburg, Germany Duration: 16 Sept 2019 → 20 Sept 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11908 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2019
Country/Territory	Germany
City	Wurzburg
Period	16/09/19 → 20/09/19

Access to Document

10.1007/978-3-030-46133-1_6

Cite this

Burgess, M. A., Chapman, A. C., & Scott, P. (2020). An Engineered Empirical Bernstein Bound. In U. Brefeld, E. Fromont, A. Hotho, A. Knobbe, M. Maathuis, & C. Robardet (Eds.), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings (pp. 86-102). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11908 LNAI). Springer. https://doi.org/10.1007/978-3-030-46133-1_6

Burgess, Mark A. ; Chapman, Archie C. ; Scott, Paul. / An Engineered Empirical Bernstein Bound. Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings. editor / Ulf Brefeld ; Elisa Fromont ; Andreas Hotho ; Arno Knobbe ; Marloes Maathuis ; Céline Robardet. Springer, 2020. pp. 86-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f94446e498cc431985000ff04ec34167,

title = "An Engineered Empirical Bernstein Bound",

abstract = "We derive a tightened empirical Bernstein bound (EBB) on the variation of the sample mean from the population mean, and show that it improves the performance of upper confidence bound (UCB) methods in multi-armed bandit problems. Like other EBBs, our EBB is a concentration inequality for the variation of the sample mean in terms of the sample variance. Its derivation uses a combination of probability unions and Chernoff bounds for the mean of samples and mean of sample squares. Analysis reveals that our approach can tighten the best existing EBBs by about a third, and thereby halves the distance to a bound constructed with perfect variance information. We illustrate the practical usefulness of our novel EBB by applying it to a multi-armed bandit problem as a component of a UCB method. Our method outperforms existing approaches by producing lower expected regret than variants of UCB employing several other bounds, including state-of-the-art EBBs.",

keywords = "Chernoff bounds, Concentration inequality, Empirical Bernstein bound, Hoeffding{\textquoteright}s inequality",

author = "Burgess, \{Mark A.\} and Chapman, \{Archie C.\} and Paul Scott",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2019 ; Conference date: 16-09-2019 Through 20-09-2019",

year = "2020",

doi = "10.1007/978-3-030-46133-1\_6",

language = "English",

isbn = "9783030461324",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "86--102",

editor = "Ulf Brefeld and Elisa Fromont and Andreas Hotho and Arno Knobbe and Marloes Maathuis and C{\'e}line Robardet",

booktitle = "Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings",

address = "Germany",

}

Burgess, MA, Chapman, AC & Scott, P 2020, An Engineered Empirical Bernstein Bound. in U Brefeld, E Fromont, A Hotho, A Knobbe, M Maathuis & C Robardet (eds), Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11908 LNAI, Springer, pp. 86-102, European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2019, Wurzburg, Germany, 16/09/19. https://doi.org/10.1007/978-3-030-46133-1_6

An Engineered Empirical Bernstein Bound. / Burgess, Mark A.; Chapman, Archie C.; Scott, Paul.
Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings. ed. / Ulf Brefeld; Elisa Fromont; Andreas Hotho; Arno Knobbe; Marloes Maathuis; Céline Robardet. Springer, 2020. p. 86-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11908 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

TY - GEN

T1 - An Engineered Empirical Bernstein Bound

AU - Burgess, Mark A.

AU - Chapman, Archie C.

AU - Scott, Paul

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

N2 - We derive a tightened empirical Bernstein bound (EBB) on the variation of the sample mean from the population mean, and show that it improves the performance of upper confidence bound (UCB) methods in multi-armed bandit problems. Like other EBBs, our EBB is a concentration inequality for the variation of the sample mean in terms of the sample variance. Its derivation uses a combination of probability unions and Chernoff bounds for the mean of samples and mean of sample squares. Analysis reveals that our approach can tighten the best existing EBBs by about a third, and thereby halves the distance to a bound constructed with perfect variance information. We illustrate the practical usefulness of our novel EBB by applying it to a multi-armed bandit problem as a component of a UCB method. Our method outperforms existing approaches by producing lower expected regret than variants of UCB employing several other bounds, including state-of-the-art EBBs.

AB - We derive a tightened empirical Bernstein bound (EBB) on the variation of the sample mean from the population mean, and show that it improves the performance of upper confidence bound (UCB) methods in multi-armed bandit problems. Like other EBBs, our EBB is a concentration inequality for the variation of the sample mean in terms of the sample variance. Its derivation uses a combination of probability unions and Chernoff bounds for the mean of samples and mean of sample squares. Analysis reveals that our approach can tighten the best existing EBBs by about a third, and thereby halves the distance to a bound constructed with perfect variance information. We illustrate the practical usefulness of our novel EBB by applying it to a multi-armed bandit problem as a component of a UCB method. Our method outperforms existing approaches by producing lower expected regret than variants of UCB employing several other bounds, including state-of-the-art EBBs.

KW - Chernoff bounds

KW - Concentration inequality

KW - Empirical Bernstein bound

KW - Hoeffding’s inequality

UR - https://www.scopus.com/pages/publications/85084853869

U2 - 10.1007/978-3-030-46133-1_6

DO - 10.1007/978-3-030-46133-1_6

M3 - Conference Paper

SN - 9783030461324

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 86

EP - 102

BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings

A2 - Brefeld, Ulf

A2 - Fromont, Elisa

A2 - Hotho, Andreas

A2 - Knobbe, Arno

A2 - Maathuis, Marloes

A2 - Robardet, Céline

PB - Springer

T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2019

Y2 - 16 September 2019 through 20 September 2019

ER -

Burgess MA, Chapman AC, Scott P. An Engineered Empirical Bernstein Bound. In Brefeld U, Fromont E, Hotho A, Knobbe A, Maathuis M, Robardet C, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019, Proceedings. Springer. 2020. p. 86-102. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-46133-1_6

An Engineered Empirical Bernstein Bound

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this