{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T17:26:19Z","timestamp":1790443579188,"version":"4.1.0"},"reference-count":50,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"name":"USA-Israeli BSF Grant"},{"name":"Oswald Veblen Fund"},{"name":"Israel Ministry of Science and Technology"},{"name":"Marie-Curie Career Integration Grant"},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011102","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["306638"],"award-info":[{"award-number":["306638"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["425\/13"],"award-info":[{"award-number":["425\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004007","name":"Instituto Nazionale di Fisica Nucleare","doi-asserted-by":"publisher","award":["2010N5K7EB_003"],"award-info":[{"award-number":["2010N5K7EB_003"]}],"id":[{"id":"10.13039\/501100004007","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>We introduce and study a partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions and observes some subset of the associated losses. This setting naturally models several situations where knowing the loss of one action provides information on the loss of other actions. Moreover, it generalizes and interpolates between the well-studied full-information setting (where all losses are revealed) and the bandit setting (where only the loss of the action chosen by the player is revealed). We provide several algorithms addressing different variants of our setting and provide tight regret bounds depending on combinatorial properties of the information feedback structure.<\/jats:p>","DOI":"10.1137\/140989455","type":"journal-article","created":{"date-parts":[[2017,11,28]],"date-time":"2017-11-28T13:06:03Z","timestamp":1511874363000},"page":"1785-1826","source":"Crossref","is-referenced-by-count":29,"title":["Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback"],"prefix":"10.1137","volume":"46","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicol\u00f2","family":"Cesa-Bianchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claudio","family":"Gentile","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shie","family":"Mannor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ohad","family":"Shamir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,11,28]]},"reference":[{"key":"atypb1","first-page":"23","author":"Alon N.","year":"2015","journal-title":"France"},{"key":"atypb2","unstructured":"N. Alon, N. Cesa-Bianchi, O. Dekel, and T. Koren,\n                      Online Learning with Feedback Graphs: Beyond Bandits\n                      , preprint,https:\/\/arxiv.org\/abs\/1502.07617, 2015."},{"key":"atypb3","first-page":"1610","author":"Alon N.","year":"2013","journal-title":"NV"},{"key":"atypb4","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , John Wiley and Sons, New York, 2004."},{"key":"atypb5","unstructured":"J.Y. Audibert and S. Bubeck,\n                      Minimax policies for adversarial and stochastic bandits\n                      , in Proceedings of COLT 2009, Montreal, Canada, 2009, online proceedings."},{"key":"atypb6","first-page":"2785","volume":"11","author":"Audibert J.-Y.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2014.0663"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1561\/2200000024"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/2637364.2591989"},{"key":"atypb11","unstructured":"Y. Caro,\n                      New Results on the Independence Number\n                      , Tech. report, Tel Aviv University, Tel Aviv, Israel, 1979."},{"key":"atypb12","unstructured":"S. Caron, B. Kveton, M. Lelarge, and S. Bhagat,\n                      Leveraging Side Observations in Stochastic Bandits\n                      , preprint,https:\/\/arxiv.org\/abs\/1210.4839, 2012."},{"key":"atypb13","unstructured":"S. Caron, B. Kveton, M. Lelarge, and S. Bhagat,\n                      Leveraging side observations in stochastic bandits\n                      , in Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), Catalina Island, CA, 2012, pp. 142-151."},{"key":"atypb14","first-page":"10","author":"Carpentier A.","year":"2016","journal-title":"Spain"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258179"},{"key":"atypb16","first-page":"465","author":"Cesa-Bianchi N.","year":"2017","journal-title":"The Netherlands"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"N. Cesa-Bianchi and G. Lugosi,\n                      Prediction, Learning, and Games\n                      , Cambridge University Press, Cambridge, UK, 2006.","DOI":"10.1017\/CBO9780511546921"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.01.001"},{"key":"atypb19","first-page":"217","author":"Cesa-Bianchi N.","year":"2005","journal-title":"Italy"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"atypb21","unstructured":"A. Cohen, T. Hazan, and T. Koren,\n                      Online Learning with Feedback Graphs without the Graphs\n                      , preprint,https:\/\/arxiv.org\/abs\/1605.07018, 2016."},{"key":"atypb22","unstructured":"O. Dekel, A. Tewari, and R. Arora,\n                      Online bandit learning against an adaptive adversary: From regret to policy regret\n                      , in Proceedings of ICML 2012, Edinburgh, Scotland, 2012, pp. 1503-1510."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996452"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90149-C"},{"key":"atypb27","first-page":"1323","author":"Hanawal M. K.","year":"2015","journal-title":"Monticello"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.016"},{"key":"atypb29","first-page":"137","author":"Kempe D.","year":"2003","journal-title":"New York"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a004"},{"key":"atypb31","first-page":"339","author":"Koc\u00e1k T.","year":"2016","journal-title":"New York"},{"key":"atypb32","first-page":"1186","author":"Koc\u00e1k T.","year":"2016","journal-title":"Spain"},{"key":"atypb33","first-page":"613","author":"Koc\u00e1k T.","year":"2014","journal-title":"Canada"},{"key":"atypb34","first-page":"817","author":"Langford J.","year":"2008","journal-title":"Canada"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"atypb36","first-page":"570","author":"Maillard O.","year":"2011","journal-title":"Fort Lauderdale, FL"},{"key":"atypb37","first-page":"684","author":"Mannor S.","year":"2011","journal-title":"Spain"},{"key":"atypb38","first-page":"3150","author":"Neu G.","year":"2015","journal-title":"Canada"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOS1101"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0446"},{"key":"atypb41","unstructured":"A. Said, E. W. De Luca, and S. Albayrak,\n                      How social relationships affect user similarities\n                      , in Proceedings of the International Conference on Intelligent User Interfaces Workshop on Social Recommender Systems, Hong Kong, 2010, online proceedings."},{"key":"atypb42","first-page":"679","author":"Slivkins A.","year":"2011","journal-title":"Hungary"},{"key":"atypb43","unstructured":"G. Stoltz,\n                      Information Incompl\u00e8te et Regret Interne en Pr\u00e9diction de Suites Individuelles\n                      , Ph.D. thesis, Universit\u00e9 Paris-XI Orsay, Orsay, France, 2005."},{"key":"atypb44","first-page":"46","author":"Valko M.","year":"2014","journal-title":"China"},{"key":"atypb45","first-page":"371","author":"Vovk V. G.","year":"1990","journal-title":"NY"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2004.10.004"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2005.844079"},{"key":"atypb48","first-page":"9","volume":"81","author":"Wey V. K.","year":"1981","journal-title":"Bell Lab. Tech. Memo"},{"key":"atypb49","first-page":"1360","author":"Wu Y.","year":"2015","journal-title":"Canada"},{"key":"atypb50","first-page":"1241","author":"Zolghadr N.","year":"2013","journal-title":"NV"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140989455","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:11:19Z","timestamp":1787339479000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140989455"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/140989455"],"URL":"https:\/\/doi.org\/10.1137\/140989455","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}