On Learning the Optimal Waiting Time View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2014

AUTHORS

Tor Lattimore , András György , Csaba Szepesvári

ABSTRACT

Consider the problem of learning how long to wait for a bus before walking, experimenting each day and assuming that the bus arrival times are independent and identically distributed random variables with an unknown distribution. Similar uncertain optimal stopping problems arise when devising power-saving strategies, e.g., learning the optimal disk spin-down time for mobile computers, or speeding up certain types of satisficing search procedures by switching from a potentially fast search method that is unreliable, to one that is reliable, but slower. Formally, the problem can be described as a repeated game. In each round of the game an agent is waiting for an event to occur. If the event occurs while the agent is waiting, the agent suffers a loss that is the sum of the event’s “arrival time” and some fixed loss. If the agents decides to give up waiting before the event occurs, he suffers a loss that is the sum of the waiting time and some other fixed loss. It is assumed that the arrival times are independent random quantities with the same distribution, which is unknown, while the agent knows the loss associated with each outcome. Two versions of the game are considered. In the full information case the agent observes the arrival times regardless of its actions, while in the partial information case the arrival time is observed only if it does not exceed the waiting time. After some general structural observations about the problem, we present a number of algorithms for both cases that learn the optimal weighting time with nearly matching minimax upper and lower bounds on their regret. More... »

PAGES

200-214

Book

TITLE

Algorithmic Learning Theory

ISBN

978-3-319-11661-7
978-3-319-11662-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-11662-4_15

DOI

http://dx.doi.org/10.1007/978-3-319-11662-4_15

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Alberta", 
          "id": "https://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Department of Computing Science, University of Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lattimore", 
        "givenName": "Tor", 
        "id": "sg:person.010562254267.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010562254267.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Alberta", 
          "id": "https://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Department of Computing Science, University of Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gy\u00f6rgy", 
        "givenName": "Andr\u00e1s", 
        "id": "sg:person.014644354015.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014644354015.55"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Alberta", 
          "id": "https://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Department of Computing Science, University of Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Szepesv\u00e1ri", 
        "givenName": "Csaba", 
        "id": "sg:person.016202177221.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016202177221.23"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/pl00009249", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001656938", 
          "https://doi.org/10.1007/pl00009249"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10898-011-9769-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003209678", 
          "https://doi.org/10.1007/s10898-011-9769-z"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/aoms/1177728174", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046596475"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1735223.1735247", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049785470"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/9.16415", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061243163"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/aop/1176990746", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064403995"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2003.1238232", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095011296"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511546921", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098679346"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2014", 
    "datePublishedReg": "2014-01-01", 
    "description": "Consider the problem of learning how long to wait for a bus before walking, experimenting each day and assuming that the bus arrival times are independent and identically distributed random variables with an unknown distribution. Similar uncertain optimal stopping problems arise when devising power-saving strategies, e.g., learning the optimal disk spin-down time for mobile computers, or speeding up certain types of satisficing search procedures by switching from a potentially fast search method that is unreliable, to one that is reliable, but slower. Formally, the problem can be described as a repeated game. In each round of the game an agent is waiting for an event to occur. If the event occurs while the agent is waiting, the agent suffers a loss that is the sum of the event\u2019s \u201carrival time\u201d and some fixed loss. If the agents decides to give up waiting before the event occurs, he suffers a loss that is the sum of the waiting time and some other fixed loss. It is assumed that the arrival times are independent random quantities with the same distribution, which is unknown, while the agent knows the loss associated with each outcome. Two versions of the game are considered. In the full information case the agent observes the arrival times regardless of its actions, while in the partial information case the arrival time is observed only if it does not exceed the waiting time. After some general structural observations about the problem, we present a number of algorithms for both cases that learn the optimal weighting time with nearly matching minimax upper and lower bounds on their regret.", 
    "editor": [
      {
        "familyName": "Auer", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Clark", 
        "givenName": "Alexander", 
        "type": "Person"
      }, 
      {
        "familyName": "Zeugmann", 
        "givenName": "Thomas", 
        "type": "Person"
      }, 
      {
        "familyName": "Zilles", 
        "givenName": "Sandra", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-11662-4_15", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-11661-7", 
        "978-3-319-11662-4"
      ], 
      "name": "Algorithmic Learning Theory", 
      "type": "Book"
    }, 
    "name": "On Learning the Optimal Waiting Time", 
    "pagination": "200-214", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-11662-4_15"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "db02d8f1344cae391a29850104b9e292c6ffa0499fae0e6342902b1df7b6a995"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045977671"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-11662-4_15", 
      "https://app.dimensions.ai/details/publication/pub.1045977671"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T12:34", 
    "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/0000000001_0000000264/records_8663_00000271.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-11662-4_15"
  }
]
 

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/978-3-319-11662-4_15'

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/978-3-319-11662-4_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-11662-4_15'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-11662-4_15'


 

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

120 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-11662-4_15 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N856c8964430e484a9ad7e2d5ec6c3d6d
4 schema:citation sg:pub.10.1007/pl00009249
5 sg:pub.10.1007/s10898-011-9769-z
6 https://doi.org/10.1017/cbo9780511546921
7 https://doi.org/10.1109/9.16415
8 https://doi.org/10.1109/sfcs.2003.1238232
9 https://doi.org/10.1145/1735223.1735247
10 https://doi.org/10.1214/aoms/1177728174
11 https://doi.org/10.1214/aop/1176990746
12 schema:datePublished 2014
13 schema:datePublishedReg 2014-01-01
14 schema:description Consider the problem of learning how long to wait for a bus before walking, experimenting each day and assuming that the bus arrival times are independent and identically distributed random variables with an unknown distribution. Similar uncertain optimal stopping problems arise when devising power-saving strategies, e.g., learning the optimal disk spin-down time for mobile computers, or speeding up certain types of satisficing search procedures by switching from a potentially fast search method that is unreliable, to one that is reliable, but slower. Formally, the problem can be described as a repeated game. In each round of the game an agent is waiting for an event to occur. If the event occurs while the agent is waiting, the agent suffers a loss that is the sum of the event’s “arrival time” and some fixed loss. If the agents decides to give up waiting before the event occurs, he suffers a loss that is the sum of the waiting time and some other fixed loss. It is assumed that the arrival times are independent random quantities with the same distribution, which is unknown, while the agent knows the loss associated with each outcome. Two versions of the game are considered. In the full information case the agent observes the arrival times regardless of its actions, while in the partial information case the arrival time is observed only if it does not exceed the waiting time. After some general structural observations about the problem, we present a number of algorithms for both cases that learn the optimal weighting time with nearly matching minimax upper and lower bounds on their regret.
15 schema:editor N9afa3981fdfb4c568a30d7c87bea85dc
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf Ne1ba0c278697468b929b1865418480f9
20 schema:name On Learning the Optimal Waiting Time
21 schema:pagination 200-214
22 schema:productId N4508f414405340ba97067fe45b1b53f1
23 N769d3b42178f4e25b7e87e585558ae50
24 Neabe89c854e84d8e903f6f5f8f3ca838
25 schema:publisher N907fc921520a4b949f721ee45471999a
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045977671
27 https://doi.org/10.1007/978-3-319-11662-4_15
28 schema:sdDatePublished 2019-04-15T12:34
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher Na7e3d8a14fc043beb674267e0543435d
31 schema:url http://link.springer.com/10.1007/978-3-319-11662-4_15
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N2f4115c0c8634087828947ea104bce23 schema:familyName Zeugmann
36 schema:givenName Thomas
37 rdf:type schema:Person
38 N3ba7791638814ddabac241ec00a3d7a0 rdf:first Nca6f4d032e784118bdcfcb1830b9fa20
39 rdf:rest rdf:nil
40 N4508f414405340ba97067fe45b1b53f1 schema:name dimensions_id
41 schema:value pub.1045977671
42 rdf:type schema:PropertyValue
43 N45844fca25e44edeaba2800c131679eb rdf:first sg:person.016202177221.23
44 rdf:rest rdf:nil
45 N4d96d4526d6647ce868344b294034481 rdf:first sg:person.014644354015.55
46 rdf:rest N45844fca25e44edeaba2800c131679eb
47 N5df75b97017f4431a519fe7b46dd5c9f schema:familyName Auer
48 schema:givenName Peter
49 rdf:type schema:Person
50 N697d601decbc42f8a4af563ecd5bdac2 rdf:first Nd539976725b74d4081dc3510356003be
51 rdf:rest N81326d39197245378fe08584a6825a1b
52 N769d3b42178f4e25b7e87e585558ae50 schema:name readcube_id
53 schema:value db02d8f1344cae391a29850104b9e292c6ffa0499fae0e6342902b1df7b6a995
54 rdf:type schema:PropertyValue
55 N81326d39197245378fe08584a6825a1b rdf:first N2f4115c0c8634087828947ea104bce23
56 rdf:rest N3ba7791638814ddabac241ec00a3d7a0
57 N856c8964430e484a9ad7e2d5ec6c3d6d rdf:first sg:person.010562254267.14
58 rdf:rest N4d96d4526d6647ce868344b294034481
59 N907fc921520a4b949f721ee45471999a schema:location Cham
60 schema:name Springer International Publishing
61 rdf:type schema:Organisation
62 N9afa3981fdfb4c568a30d7c87bea85dc rdf:first N5df75b97017f4431a519fe7b46dd5c9f
63 rdf:rest N697d601decbc42f8a4af563ecd5bdac2
64 Na7e3d8a14fc043beb674267e0543435d schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 Nca6f4d032e784118bdcfcb1830b9fa20 schema:familyName Zilles
67 schema:givenName Sandra
68 rdf:type schema:Person
69 Nd539976725b74d4081dc3510356003be schema:familyName Clark
70 schema:givenName Alexander
71 rdf:type schema:Person
72 Ne1ba0c278697468b929b1865418480f9 schema:isbn 978-3-319-11661-7
73 978-3-319-11662-4
74 schema:name Algorithmic Learning Theory
75 rdf:type schema:Book
76 Neabe89c854e84d8e903f6f5f8f3ca838 schema:name doi
77 schema:value 10.1007/978-3-319-11662-4_15
78 rdf:type schema:PropertyValue
79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
80 schema:name Information and Computing Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
83 schema:name Artificial Intelligence and Image Processing
84 rdf:type schema:DefinedTerm
85 sg:person.010562254267.14 schema:affiliation https://www.grid.ac/institutes/grid.17089.37
86 schema:familyName Lattimore
87 schema:givenName Tor
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010562254267.14
89 rdf:type schema:Person
90 sg:person.014644354015.55 schema:affiliation https://www.grid.ac/institutes/grid.17089.37
91 schema:familyName György
92 schema:givenName András
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014644354015.55
94 rdf:type schema:Person
95 sg:person.016202177221.23 schema:affiliation https://www.grid.ac/institutes/grid.17089.37
96 schema:familyName Szepesvári
97 schema:givenName Csaba
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016202177221.23
99 rdf:type schema:Person
100 sg:pub.10.1007/pl00009249 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001656938
101 https://doi.org/10.1007/pl00009249
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/s10898-011-9769-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1003209678
104 https://doi.org/10.1007/s10898-011-9769-z
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1017/cbo9780511546921 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098679346
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1109/9.16415 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061243163
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1109/sfcs.2003.1238232 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095011296
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1145/1735223.1735247 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049785470
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1214/aoms/1177728174 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046596475
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1214/aop/1176990746 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064403995
117 rdf:type schema:CreativeWork
118 https://www.grid.ac/institutes/grid.17089.37 schema:alternateName University of Alberta
119 schema:name Department of Computing Science, University of Alberta, Canada
120 rdf:type schema:Organization
 




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


...