Corruption-tolerant bandit learning View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-04

AUTHORS

Sayash Kapoor, Kumar Kshitij Patel, Purushottam Kar

ABSTRACT

We present algorithms for solving multi-armed and linear-contextual bandit tasks in the face of adversarial corruptions in the arm responses. Traditional algorithms for solving these problems assume that nothing but mild, e.g., i.i.d. sub-Gaussian, noise disrupts an otherwise clean estimate of the utility of the arm. This assumption and the resulting approaches can fail catastrophically if there is an observant adversary that corrupts even a small fraction of the responses generated when arms are pulled. To rectify this, we propose algorithms that use recent advances in robust statistical estimation to perform arm selection in polynomial time. Our algorithms are easy to implement and vastly outperform several existing UCB and EXP-style algorithms for stochastic and adversarial multi-armed and linear-contextual bandit problems in wide variety of experimental settings. Our algorithms enjoy minimax-optimal regret bounds, as well as can tolerate an adversary that is allowed to corrupt upto a universally constant fraction of the arms pulled by the algorithm. More... »

PAGES

687-715

References to SciGraph publications

Journal

TITLE

Machine Learning

ISSUE

4

VOLUME

108

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10994-018-5758-5

DOI

http://dx.doi.org/10.1007/s10994-018-5758-5

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1106411050


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Indian Institute of Technology Kanpur", 
          "id": "https://www.grid.ac/institutes/grid.417965.8", 
          "name": [
            "Indian Institute of Technology Kanpur, Kanpur, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kapoor", 
        "givenName": "Sayash", 
        "id": "sg:person.013335746654.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013335746654.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Indian Institute of Technology Kanpur", 
          "id": "https://www.grid.ac/institutes/grid.417965.8", 
          "name": [
            "Indian Institute of Technology Kanpur, Kanpur, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Patel", 
        "givenName": "Kumar Kshitij", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Indian Institute of Technology Kanpur", 
          "id": "https://www.grid.ac/institutes/grid.417965.8", 
          "name": [
            "Indian Institute of Technology Kanpur, Kanpur, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kar", 
        "givenName": "Purushottam", 
        "id": "sg:person.07403060541.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07403060541.22"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/1970392.1970395", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007128073"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-75225-7_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029155399", 
          "https://doi.org/10.1007/978-3-540-75225-7_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-75225-7_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029155399", 
          "https://doi.org/10.1007/978-3-540-75225-7_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2009.01.016", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032851363"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2505515.2514700", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035146935"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1772690.1772758", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036208090"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1013689704352", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039349898", 
          "https://doi.org/10.1023/a:1013689704352"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/b13794", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043149989", 
          "https://doi.org/10.1007/b13794"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/b13794", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043149989", 
          "https://doi.org/10.1007/b13794"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.2013.2240435", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061654298"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.2013.2277869", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061654602"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539701398375", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879339"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/aoms/1177703732", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064400228"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3055399.3055491", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091877728"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/focs.2016.85", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094183130"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/ijcnn.2016.7727473", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094183266"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/focs.2016.76", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094887977"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611975031", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1100173102"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3188745.3188918", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1105021116"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/3188745.3188918", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1105021116"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109503092", 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109503092", 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109503092", 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/0470010940", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109503092"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/0470010940", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109503092"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-04", 
    "datePublishedReg": "2019-04-01", 
    "description": "We present algorithms for solving multi-armed and linear-contextual bandit tasks in the face of adversarial corruptions in the arm responses. Traditional algorithms for solving these problems assume that nothing but mild, e.g., i.i.d. sub-Gaussian, noise disrupts an otherwise clean estimate of the utility of the arm. This assumption and the resulting approaches can fail catastrophically if there is an observant adversary that corrupts even a small fraction of the responses generated when arms are pulled. To rectify this, we propose algorithms that use recent advances in robust statistical estimation to perform arm selection in polynomial time. Our algorithms are easy to implement and vastly outperform several existing UCB and EXP-style algorithms for stochastic and adversarial multi-armed and linear-contextual bandit problems in wide variety of experimental settings. Our algorithms enjoy minimax-optimal regret bounds, as well as can tolerate an adversary that is allowed to corrupt upto a universally constant fraction of the arms pulled by the algorithm.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10994-018-5758-5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1125588", 
        "issn": [
          "0885-6125", 
          "1573-0565"
        ], 
        "name": "Machine Learning", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "108"
      }
    ], 
    "name": "Corruption-tolerant bandit learning", 
    "pagination": "687-715", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "5d69896518372ad4b9c544c29c84b081528ce097455af7c149b9709a91f4a7d3"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10994-018-5758-5"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1106411050"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10994-018-5758-5", 
      "https://app.dimensions.ai/details/publication/pub.1106411050"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T10:39", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000349_0000000349/records_113679_00000005.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10994-018-5758-5"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10994-018-5758-5'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10994-018-5758-5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10994-018-5758-5'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10994-018-5758-5'


 

This table displays all metadata directly associated to this object as RDF triples.

133 TRIPLES      21 PREDICATES      46 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10994-018-5758-5 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author Nccc20061c45540e8b2889e6c8f02e4f3
4 schema:citation sg:pub.10.1007/978-3-540-75225-7_15
5 sg:pub.10.1007/b13794
6 sg:pub.10.1023/a:1013689704352
7 https://app.dimensions.ai/details/publication/pub.1109503092
8 https://doi.org/10.1002/0470010940
9 https://doi.org/10.1016/j.tcs.2009.01.016
10 https://doi.org/10.1109/focs.2016.76
11 https://doi.org/10.1109/focs.2016.85
12 https://doi.org/10.1109/ijcnn.2016.7727473
13 https://doi.org/10.1109/tit.2013.2240435
14 https://doi.org/10.1109/tit.2013.2277869
15 https://doi.org/10.1137/1.9781611975031
16 https://doi.org/10.1137/s0097539701398375
17 https://doi.org/10.1145/1772690.1772758
18 https://doi.org/10.1145/1970392.1970395
19 https://doi.org/10.1145/2505515.2514700
20 https://doi.org/10.1145/3055399.3055491
21 https://doi.org/10.1145/3188745.3188918
22 https://doi.org/10.1214/aoms/1177703732
23 schema:datePublished 2019-04
24 schema:datePublishedReg 2019-04-01
25 schema:description We present algorithms for solving multi-armed and linear-contextual bandit tasks in the face of adversarial corruptions in the arm responses. Traditional algorithms for solving these problems assume that nothing but mild, e.g., i.i.d. sub-Gaussian, noise disrupts an otherwise clean estimate of the utility of the arm. This assumption and the resulting approaches can fail catastrophically if there is an observant adversary that corrupts even a small fraction of the responses generated when arms are pulled. To rectify this, we propose algorithms that use recent advances in robust statistical estimation to perform arm selection in polynomial time. Our algorithms are easy to implement and vastly outperform several existing UCB and EXP-style algorithms for stochastic and adversarial multi-armed and linear-contextual bandit problems in wide variety of experimental settings. Our algorithms enjoy minimax-optimal regret bounds, as well as can tolerate an adversary that is allowed to corrupt upto a universally constant fraction of the arms pulled by the algorithm.
26 schema:genre research_article
27 schema:inLanguage en
28 schema:isAccessibleForFree false
29 schema:isPartOf N300d0ac856ca443ca7f7ee4c3d2a6d00
30 N3d974823ba8a46c1be757c1845226ac2
31 sg:journal.1125588
32 schema:name Corruption-tolerant bandit learning
33 schema:pagination 687-715
34 schema:productId N5efa07cfe3744867ab168161ec553f44
35 N6b1fafe7111c4c0b862965ef25c9e14b
36 Na59b3e8eb50a4ffbb054dfe4ca004c61
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106411050
38 https://doi.org/10.1007/s10994-018-5758-5
39 schema:sdDatePublished 2019-04-11T10:39
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher N08148c046d6b4a799f33e41d775b77d9
42 schema:url https://link.springer.com/10.1007%2Fs10994-018-5758-5
43 sgo:license sg:explorer/license/
44 sgo:sdDataset articles
45 rdf:type schema:ScholarlyArticle
46 N0145a726be76456181fa0d9a1d95cef2 schema:affiliation https://www.grid.ac/institutes/grid.417965.8
47 schema:familyName Patel
48 schema:givenName Kumar Kshitij
49 rdf:type schema:Person
50 N08148c046d6b4a799f33e41d775b77d9 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N300d0ac856ca443ca7f7ee4c3d2a6d00 schema:issueNumber 4
53 rdf:type schema:PublicationIssue
54 N3d974823ba8a46c1be757c1845226ac2 schema:volumeNumber 108
55 rdf:type schema:PublicationVolume
56 N5efa07cfe3744867ab168161ec553f44 schema:name readcube_id
57 schema:value 5d69896518372ad4b9c544c29c84b081528ce097455af7c149b9709a91f4a7d3
58 rdf:type schema:PropertyValue
59 N6b1fafe7111c4c0b862965ef25c9e14b schema:name doi
60 schema:value 10.1007/s10994-018-5758-5
61 rdf:type schema:PropertyValue
62 Na59b3e8eb50a4ffbb054dfe4ca004c61 schema:name dimensions_id
63 schema:value pub.1106411050
64 rdf:type schema:PropertyValue
65 Nb6692395080446c589ae00b71158a0b4 rdf:first N0145a726be76456181fa0d9a1d95cef2
66 rdf:rest Nc447a33d03b348df8138f5caf4d20ad4
67 Nc447a33d03b348df8138f5caf4d20ad4 rdf:first sg:person.07403060541.22
68 rdf:rest rdf:nil
69 Nccc20061c45540e8b2889e6c8f02e4f3 rdf:first sg:person.013335746654.33
70 rdf:rest Nb6692395080446c589ae00b71158a0b4
71 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
72 schema:name Mathematical Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
75 schema:name Statistics
76 rdf:type schema:DefinedTerm
77 sg:journal.1125588 schema:issn 0885-6125
78 1573-0565
79 schema:name Machine Learning
80 rdf:type schema:Periodical
81 sg:person.013335746654.33 schema:affiliation https://www.grid.ac/institutes/grid.417965.8
82 schema:familyName Kapoor
83 schema:givenName Sayash
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013335746654.33
85 rdf:type schema:Person
86 sg:person.07403060541.22 schema:affiliation https://www.grid.ac/institutes/grid.417965.8
87 schema:familyName Kar
88 schema:givenName Purushottam
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07403060541.22
90 rdf:type schema:Person
91 sg:pub.10.1007/978-3-540-75225-7_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029155399
92 https://doi.org/10.1007/978-3-540-75225-7_15
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/b13794 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043149989
95 https://doi.org/10.1007/b13794
96 rdf:type schema:CreativeWork
97 sg:pub.10.1023/a:1013689704352 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039349898
98 https://doi.org/10.1023/a:1013689704352
99 rdf:type schema:CreativeWork
100 https://app.dimensions.ai/details/publication/pub.1109503092 schema:CreativeWork
101 https://doi.org/10.1002/0470010940 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109503092
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/j.tcs.2009.01.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032851363
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1109/focs.2016.76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094887977
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1109/focs.2016.85 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094183130
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1109/ijcnn.2016.7727473 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094183266
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1109/tit.2013.2240435 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061654298
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1109/tit.2013.2277869 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061654602
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1137/1.9781611975031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100173102
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1137/s0097539701398375 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879339
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1145/1772690.1772758 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036208090
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1145/1970392.1970395 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007128073
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1145/2505515.2514700 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035146935
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1145/3055399.3055491 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091877728
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1145/3188745.3188918 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105021116
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1214/aoms/1177703732 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064400228
130 rdf:type schema:CreativeWork
131 https://www.grid.ac/institutes/grid.417965.8 schema:alternateName Indian Institute of Technology Kanpur
132 schema:name Indian Institute of Technology Kanpur, Kanpur, India
133 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...