{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:17Z","timestamp":1759637597852,"version":"build-2065373602"},"reference-count":23,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T00:00:00Z","timestamp":1707696000000},"content-version":"vor","delay-in-days":1472,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1016\/j.tcs.2019.11.017","type":"journal-article","created":{"date-parts":[[2019,11,11]],"date-time":"2019-11-11T19:05:41Z","timestamp":1573499141000},"page":"159-163","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":2,"special_numbering":"C","title":["New bounds on the price of bandit feedback for mistake-bounded online multiclass learning"],"prefix":"10.1016","volume":"808","author":[{"given":"Philip M.","family":"Long","sequence":"first","affiliation":[]}],"member":"78","reference":[{"issue":"4","key":"10.1016\/j.tcs.2019.11.017_br0010","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s00453-003-1038-1","article-title":"Reinforcement learning with immediate rewards and linear hypotheses","volume":"37","author":"Abe","year":"2003","journal-title":"Algorithmica"},{"issue":"Nov","key":"10.1016\/j.tcs.2019.11.017_br0020","first-page":"397","article-title":"Using confidence bounds for exploitation-exploration trade-offs","volume":"3","author":"Auer","year":"2002","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"10.1016\/j.tcs.2019.11.017_br0030","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539701398375","article-title":"The nonstochastic multiarmed bandit problem","volume":"32","author":"Auer","year":"2002","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.tcs.2019.11.017_br0040","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1023\/A:1007614417594","article-title":"Structural results about on-line learning models with and without queries","volume":"36","author":"Auer","year":"1999","journal-title":"Mach. Learn."},{"issue":"2\u20133","key":"10.1016\/j.tcs.2019.11.017_br0050","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1023\/A:1022851430087","article-title":"On the complexity of function learning","volume":"18","author":"Auer","year":"1995","journal-title":"Mach. Learn."},{"key":"10.1016\/j.tcs.2019.11.017_br0060","series-title":"Online Algorithms","first-page":"306","article-title":"On-line algorithms in machine learning","author":"Blum","year":"1998"},{"author":"Blum","key":"10.1016\/j.tcs.2019.11.017_br0070"},{"issue":"1","key":"10.1016\/j.tcs.2019.11.017_br0080","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000024","article-title":"Regret analysis of stochastic and nonstochastic multi-armed bandit problems","volume":"5","author":"Bubeck","year":"2012","journal-title":"Found. Trends Mach. Learn."},{"key":"10.1016\/j.tcs.2019.11.017_br0090","series-title":"Proceedings of the Ninth Annual ACM Symposium on Theory of Computing","first-page":"106","article-title":"Universal classes of hash functions","author":"Carter","year":"1977"},{"key":"10.1016\/j.tcs.2019.11.017_br0100","series-title":"AISTATS","first-page":"208","article-title":"Contextual bandits with linear payoff functions","volume":"vol. 15","author":"Chu","year":"2011"},{"issue":"3","key":"10.1016\/j.tcs.2019.11.017_br0110","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s10994-012-5321-8","article-title":"Multiclass classification with bandit feedback using adaptive regularization","volume":"90","author":"Crammer","year":"2013","journal-title":"Mach. Learn."},{"key":"10.1016\/j.tcs.2019.11.017_br0120","series-title":"COLT","first-page":"355","article-title":"Stochastic linear optimization under bandit feedback","author":"Dani","year":"2008"},{"key":"10.1016\/j.tcs.2019.11.017_br0130","series-title":"Conference on Learning Theory","first-page":"93","article-title":"The price of bandit information in multiclass online classification","author":"Daniely","year":"2013"},{"key":"10.1016\/j.tcs.2019.11.017_br0140","series-title":"Advances in Neural Information Processing Systems","first-page":"891","article-title":"Newtron: an efficient bandit algorithm for online multiclass prediction","author":"Hazan","year":"2011"},{"issue":"2","key":"10.1016\/j.tcs.2019.11.017_br0150","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/inco.2000.2870","article-title":"Apple tasting","volume":"161","author":"Helmbold","year":"2000","journal-title":"Inf. Comput."},{"key":"10.1016\/j.tcs.2019.11.017_br0160","series-title":"Proceedings of the 25th International Conference on Machine Learning","first-page":"440","article-title":"Efficient bandit algorithms for online multiclass prediction","author":"Kakade","year":"2008"},{"issue":"4","key":"10.1016\/j.tcs.2019.11.017_br0170","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1023\/A:1022869011914","article-title":"Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm","volume":"2","author":"Littlestone","year":"1988","journal-title":"Mach. Learn."},{"key":"10.1016\/j.tcs.2019.11.017_br0180","series-title":"Foundations of Computer Science, 1989, 30th Annual Symposium on","first-page":"256","article-title":"The weighted majority algorithm","author":"Littlestone","year":"1989"},{"year":"2006","series-title":"Pairwise Independence and Derandomization, vol. 4","author":"Luby","key":"10.1016\/j.tcs.2019.11.017_br0190"},{"key":"10.1016\/j.tcs.2019.11.017_br0200","series-title":"Proceedings of the 5th International Joint Conference on Artificial Intelligence-Volume 1","first-page":"305","article-title":"Version spaces: a candidate elimination approach to rule learning","author":"Mitchell","year":"1977"},{"key":"10.1016\/j.tcs.2019.11.017_br0210","first-page":"67","article-title":"Hypercubes of strength d leading to confounded designs in factorial experiments","volume":"38","author":"Rao","year":"1946","journal-title":"Bull. Calcutta Math. Soc."},{"key":"10.1016\/j.tcs.2019.11.017_br0220","doi-asserted-by":"crossref","first-page":"128","DOI":"10.2307\/2983576","article-title":"Factorial experiments derivable from combinatorial arrangements of arrays","author":"Rao","year":"1947","journal-title":"Suppl. J. R. Stat. Soc."},{"key":"10.1016\/j.tcs.2019.11.017_br0230","unstructured":"H. Shvaytser, Linear manifolds are learnable from positive examples, 1988. Unpublished manuscript."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397519307297?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397519307297?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T01:01:03Z","timestamp":1759626063000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397519307297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2]]},"references-count":23,"alternative-id":["S0304397519307297"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2019.11.017","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2020,2]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"New bounds on the price of bandit feedback for mistake-bounded online multiclass learning","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2019.11.017","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2019 Elsevier B.V.","name":"copyright","label":"Copyright"}]}}