{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:08Z","timestamp":1750234208692,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T00:00:00Z","timestamp":1404172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Lord Rutherford Memorial Research Fellowship"},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-04-27129, CCF-09-64401","CCF-1116616"],"award-info":[{"award-number":["CCF-04-27129, CCF-09-64401","CCF-1116616"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>\n            We study the online decision problem in which the set of available actions varies over time, also called the\n            <jats:italic>sleeping<\/jats:italic>\n            <jats:italic>experts<\/jats:italic>\n            problem. We consider the setting in which the performance comparison is made with respect to the\n            <jats:italic>best<\/jats:italic>\n            <jats:italic>ordering<\/jats:italic>\n            of actions in hindsight. In this article, both the payoff function and the availability of actions are adversarial. Kleinberg et al. [2010] gave a computationally efficient no-regret algorithm in the setting in which payoffs are stochastic. Kanade et al. [2009] gave an efficient no-regret algorithm in the setting in which action availability is stochastic.\n          <\/jats:p>\n          <jats:p>\n            However, the question of whether there exists a\n            <jats:italic>computationally<\/jats:italic>\n            <jats:italic>efficient<\/jats:italic>\n            no-regret algorithm in the adversarial setting was posed as an open problem by Kleinberg et al. [2010]. We show that such an algorithm would imply an algorithm for PAC learning\n            <jats:italic>DNF<\/jats:italic>\n            , a long-standing important open problem. We also consider the setting in which the number of available actions is restricted and study its relation to agnostic-learning monotone disjunctions over examples with bounded Hamming weight.\n          <\/jats:p>","DOI":"10.1145\/2505983","type":"journal-article","created":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T13:03:31Z","timestamp":1409317411000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Learning Hurdles for Sleeping Experts"],"prefix":"10.1145","volume":"6","author":[{"given":"Varun","family":"Kanade","sequence":"first","affiliation":[{"name":"Harvard University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Steinke","sequence":"additional","affiliation":[{"name":"Harvard University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 23rd Annual Conference on Learning Theory. 318--319","author":"Abernethy J.","year":"2010","unstructured":"J. Abernethy . 2010 . Can we learn to gamble efficiently? (open problem) . In Proceedings of the 23rd Annual Conference on Learning Theory. 318--319 . J. Abernethy. 2010. Can we learn to gamble efficiently? (open problem). In Proceedings of the 23rd Annual Conference on Learning Theory. 318--319."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"volume-title":"Proceedings of the 22nd Annual Conference on Learning Theory.","author":"Ben-David S.","key":"e_1_2_1_3_1","unstructured":"S. Ben-David , D. P\u00e1l , and S. Shalev-Shwartz . 2009. Agnostic online learning . In Proceedings of the 22nd Annual Conference on Learning Theory. S. Ben-David, D. P\u00e1l, and S. Shalev-Shwartz. 2009. Agnostic online learning. In Proceedings of the 22nd Annual Conference on Learning Theory."},{"volume-title":"Proceedings of the 14th International Conference on Artificial Intelligence and Statistics. JMLR Proceedings Track, 19--26","author":"Beygelzimer A.","key":"e_1_2_1_4_1","unstructured":"A. Beygelzimer , J. Langford , L. Li , L. Reyzin , and R. E. Schapire . 2011. Contextual bandit algorithms with supervised learning guarantees . In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics. JMLR Proceedings Track, 19--26 . A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. E. Schapire. 2011. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics. JMLR Proceedings Track, 19--26."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1314498.1314543"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.833339"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"N. Cesa-Bianchi and G. Lugosi. 2006. Prediction Learning and Games. Cambridge University Press.   N. Cesa-Bianchi and G. Lugosi. 2006. Prediction Learning and Games . Cambridge University Press.","DOI":"10.1017\/CBO9780511546921"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.   D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms . Cambridge University Press.","DOI":"10.1017\/CBO9780511581274"},{"volume-title":"Proceedings of the 27th Conference on Uncertainty in Artificial Intelliegence, 169--178","author":"Dudik M.","key":"e_1_2_1_9_1","unstructured":"M. Dudik , D. Hsu , S. Kale , N. Karampatziakis , J. Langford , L. Reyzin , and T. Zhang . 2011. Efficient optimal learning for contextual bandits . In Proceedings of the 27th Conference on Uncertainty in Artificial Intelliegence, 169--178 . M. Dudik, D. Hsu, S. Kale, N. Karampatziakis, J. Langford, L. Reyzin, and T. Zhang. 2011. Efficient optimal learning for contextual bandits. In Proceedings of the 27th Conference on Uncertainty in Artificial Intelliegence, 169--178."},{"volume-title":"Proceedings of the 2nd European Conference on Computational Learning Theory. 23--37","author":"Freund Y.","key":"e_1_2_1_10_1","unstructured":"Y. Freund and R. E. Schapire . 1995. A decision-theoretic generalization of on-line learning and an application to boosting . In Proceedings of the 2nd European Conference on Computational Learning Theory. 23--37 . Y. Freund and R. E. Schapire. 1995. A decision-theoretic generalization of on-line learning and an application to boosting. In Proceedings of the 2nd European Conference on Computational Learning Theory. 23--37."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258616"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 25th Annual Conference on Learning Theory","volume":"23","author":"Hazan E.","unstructured":"E. Hazan , S. Kale , and S. Shalev-Shwartz . 2012. Near-optimal algorithms for online matrix prediction . In Proceedings of the 25th Annual Conference on Learning Theory , Vol. 23 , JMLR Proceedings Track, 38.1--38.13. E. Hazan, S. Kale, and S. Shalev-Shwartz. 2012. Near-optimal algorithms for online matrix prediction. In Proceedings of the 25th Annual Conference on Learning Theory, Vol. 23, JMLR Proceedings Track, 38.1--38.13."},{"volume-title":"Proceedings of the 22nd Annual Conference on Learning Theory.","author":"Kalai A. T.","key":"e_1_2_1_15_1","unstructured":"A. T. Kalai , V. Kanade , and Y. Mansour . 2009. Reliable agnostic learning . In Proceedings of the 22nd Annual Conference on Learning Theory. A. T. Kalai, V. Kanade, and Y. Mansour. 2009. Reliable agnostic learning. In Proceedings of the 22nd Annual Conference on Learning Theory."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.13"},{"volume-title":"Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. JMLR Proceedings Track, 272--279","author":"Kanade V.","key":"e_1_2_1_17_1","unstructured":"V. Kanade , B. McMahan , and B. Bryan . 2009. Sleeping experts and bandits with stochastic action availability and adversarial rewards . In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. JMLR Proceedings Track, 272--279 . V. Kanade, B. McMahan, and B. Bryan. 2009. Sleeping experts and bandits with stochastic action availability and adversarial rewards. In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. JMLR Proceedings Track, 272--279."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5178-7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380809"},{"volume-title":"Proceedings of the 20th Annual Conference on Learning Theory. 409--423","author":"Klivans A. R.","key":"e_1_2_1_21_1","unstructured":"A. R. Klivans and A. Sherstov . 2007. A lower bound for agnostically learning disjunctions . In Proceedings of the 20th Annual Conference on Learning Theory. 409--423 . A. R. Klivans and A. Sherstov. 2007. A lower bound for agnostically learning disjunctions. In Proceedings of the 20th Annual Conference on Learning Theory. 409--423."},{"volume-title":"Proceedings of the 23rd Annual Conference on Neural Information Processing Systems.","author":"Langford J.","key":"e_1_2_1_22_1","unstructured":"J. Langford and T. Zhang . 2007. The epoch-greedy algorithm for contextual multi-armed bandits . In Proceedings of the 23rd Annual Conference on Neural Information Processing Systems. J. Langford and T. Zhang. 2007. The epoch-greedy algorithm for contextual multi-armed bandits. In Proceedings of the 23rd Annual Conference on Neural Information Processing Systems."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/93335.93365"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"volume-title":"Proceedings of the 23rd Annual Conference on Learning Theory. 441--450","author":"Shalev-Shwartz S.","key":"e_1_2_1_25_1","unstructured":"S. Shalev-Shwartz , O. Shamir , and K. Sridharan . 2010. Learning kernel-based halfspaces with the zero-one loss . In Proceedings of the 23rd Annual Conference on Learning Theory. 441--450 . S. Shalev-Shwartz, O. Shamir, and K. Sridharan. 2010. Learning kernel-based halfspaces with the zero-one loss. In Proceedings of the 23rd Annual Conference on Learning Theory. 441--450."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2505983","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2505983","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:17Z","timestamp":1750232057000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2505983"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.1145\/2505983"],"URL":"https:\/\/doi.org\/10.1145\/2505983","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2014,7]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}