Home > Research > Publications & Outputs > Apple Tasting Revisited

Research

Electronic data

  • 2109.14412v1

    Submitted manuscript, 814 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Keywords

View graph of relations

Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification

Research output: Working paper › Preprint

Published

Standard

Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification. / Grant, James A.; Leslie, David S.
Arxiv, 2021.

Research output: Working paper › Preprint

Harvard

Grant, JA & Leslie, DS 2021 'Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification' Arxiv. <https://arxiv.org/abs/2109.14412>

APA

Grant, J. A., & Leslie, D. S. (2021). Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification. Arxiv. https://arxiv.org/abs/2109.14412

Vancouver

Grant JA, Leslie DS. Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification. Arxiv. 2021 Sept 29.

Author

Grant, James A. ; Leslie, David S. / Apple Tasting Revisited : Bayesian Approaches to Partially Monitored Online Binary Classification. Arxiv, 2021.

Bibtex

@techreport{e67324be1b0045209eefcb54394ae5f7,
title = "Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification",
abstract = "We consider a variant of online binary classification where a learner sequentially assigns labels ($0$ or $1$) to items with unknown true class. If, but only if, the learner chooses label $1$ they immediately observe the true label of the item. The learner faces a trade-off between short-term classification accuracy and long-term information gain. This problem has previously been studied under the name of the `apple tasting' problem. We revisit this problem as a partial monitoring problem with side information, and focus on the case where item features are linked to true classes via a logistic regression model. Our principal contribution is a study of the performance of Thompson Sampling (TS) for this problem. Using recently developed information-theoretic tools, we show that TS achieves a Bayesian regret bound of an improved order to previous approaches. Further, we experimentally verify that efficient approximations to TS and Information Directed Sampling via P\'{o}lya-Gamma augmentation have superior empirical performance to existing methods.",
keywords = "cs.LG",
author = "Grant, {James A.} and Leslie, {David S.}",
year = "2021",
month = sep,
day = "29",
language = "English",
publisher = "Arxiv",
type = "WorkingPaper",
institution = "Arxiv",

}

RIS

TY - UNPB

T1 - Apple Tasting Revisited

T2 - Bayesian Approaches to Partially Monitored Online Binary Classification

AU - Grant, James A.

AU - Leslie, David S.

PY - 2021/9/29

Y1 - 2021/9/29

N2 - We consider a variant of online binary classification where a learner sequentially assigns labels ($0$ or $1$) to items with unknown true class. If, but only if, the learner chooses label $1$ they immediately observe the true label of the item. The learner faces a trade-off between short-term classification accuracy and long-term information gain. This problem has previously been studied under the name of the `apple tasting' problem. We revisit this problem as a partial monitoring problem with side information, and focus on the case where item features are linked to true classes via a logistic regression model. Our principal contribution is a study of the performance of Thompson Sampling (TS) for this problem. Using recently developed information-theoretic tools, we show that TS achieves a Bayesian regret bound of an improved order to previous approaches. Further, we experimentally verify that efficient approximations to TS and Information Directed Sampling via P\'{o}lya-Gamma augmentation have superior empirical performance to existing methods.

AB - We consider a variant of online binary classification where a learner sequentially assigns labels ($0$ or $1$) to items with unknown true class. If, but only if, the learner chooses label $1$ they immediately observe the true label of the item. The learner faces a trade-off between short-term classification accuracy and long-term information gain. This problem has previously been studied under the name of the `apple tasting' problem. We revisit this problem as a partial monitoring problem with side information, and focus on the case where item features are linked to true classes via a logistic regression model. Our principal contribution is a study of the performance of Thompson Sampling (TS) for this problem. Using recently developed information-theoretic tools, we show that TS achieves a Bayesian regret bound of an improved order to previous approaches. Further, we experimentally verify that efficient approximations to TS and Information Directed Sampling via P\'{o}lya-Gamma augmentation have superior empirical performance to existing methods.

KW - cs.LG

M3 - Preprint

BT - Apple Tasting Revisited

PB - Arxiv

ER -