{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T12:51:37Z","timestamp":1783947097598,"version":"3.55.0"},"reference-count":175,"publisher":"Emerald","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,12,12]]},"abstract":"<jats:p>Multi-armed bandit problems are the most basic examples of sequential decision problems with an exploration\u2013exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of bandit problems dates back to the 1930s, exploration\u2013exploitation trade-offs arise in several modern applications, such as ad placement, website optimization, and packet routing. Mathematically, a multi-armed bandit is defined by the payoffs process associated with each option. In this monograph, we focus on two extreme cases in which the analysis of regret is particularly simple and elegant: i.i.d. payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, we also analyze some of the most important variants and extensions, such as the contextual bandit model.<\/jats:p>","DOI":"10.1561\/2200000024","type":"journal-article","created":{"date-parts":[[2012,12,12]],"date-time":"2012-12-12T08:53:21Z","timestamp":1355302401000},"page":"1-122","source":"Crossref","is-referenced-by-count":1031,"title":["Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems"],"prefix":"10.1108","volume":"5","author":[{"given":"S\u00e9bastien","family":"Bubeck","sequence":"first","affiliation":[{"name":"Department of Operations Research and Financial Engineering, Princeton University , Princeton, 08544,","place":["NJ, USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicol\u00f2","family":"Cesa-Bianchi","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Milano , Milano 20135,","place":["Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","published-online":{"date-parts":[[2012,12,12]]},"reference":[{"key":"2026033014104698700_ref001","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Abbasi-Yadkori","year":"2011"},{"key":"2026033014104698700_ref002","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Abe","year":"1999"},{"key":"2026033014104698700_ref003","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Abernethy","year":"2008"},{"key":"2026033014104698700_ref004","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Abernethy","year":"2009"},{"key":"2026033014104698700_ref005","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 9.","author":"Agarwal","year":"2010"},{"key":"2026033014104698700_ref006","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Agarwal","year":"2010"},{"key":"2026033014104698700_ref007","author":"Agarwal","year":"2011","journal-title":"Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings Volume 19, 2011."},{"key":"2026033014104698700_ref008","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Agarwal","year":"2011"},{"key":"2026033014104698700_ref009","first-page":"1054","article-title":"Sample mean based index policies with O(log n) regret for the multi-armed bandit problem","volume":"27","author":"Agrawal","year":"1995","journal-title":"Advances in Applied Mathematics"},{"key":"2026033014104698700_ref010","article-title":"Analysis of Thompson sampling for the multi-armed bandit problem","volume":"23","author":"Agrawal","year":"2012","journal-title":"Proceedings of the Annual Conference on Learning Theory (COLT)"},{"key":"2026033014104698700_ref011","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Allenberg","year":"2006"},{"key":"2026033014104698700_ref012","article-title":"Bandits, query learning, and the haystack dimension","volume":"19","author":"Amin","year":"2011","journal-title":"Proceedings of the Annual Conference on Learning Theory (COLT)"},{"key":"2026033014104698700_ref013","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Antos","year":"2008"},{"key":"2026033014104698700_ref014","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Arora","year":"2012"},{"key":"2026033014104698700_ref015","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","article-title":"The multiplicative weights update method: A meta-algorithm and applications","volume":"8","author":"Arora","year":"2012","journal-title":"Theory of Computing"},{"key":"2026033014104698700_ref016","doi-asserted-by":"crossref","first-page":"213","DOI":"10.2307\/1905525","article-title":"Bayes and minimax solutions of sequential decision problems","author":"Arrow","year":"1949","journal-title":"Econometrica"},{"key":"2026033014104698700_ref017","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Audibert","year":"2009"},{"key":"2026033014104698700_ref018","first-page":"2635","article-title":"Regret bounds and minimax policies under partial monitoring","volume":"11","author":"Audibert","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014104698700_ref019","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Audibert","year":"2011"},{"key":"2026033014104698700_ref020","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Audibert","year":"2010"},{"key":"2026033014104698700_ref021","doi-asserted-by":"crossref","first-page":"1876","DOI":"10.1016\/j.tcs.2009.01.016","article-title":"Exploration-exploitation trade-off using variance estimates in multi-armed bandits","volume":"410","author":"Audibert","year":"2009","journal-title":"Theoretical Computer Science"},{"key":"2026033014104698700_ref022","first-page":"397","article-title":"Using confidence bounds for exploitation-exploration trade-offs","volume":"3","author":"Auer","year":"2002","journal-title":"Journal of Machine Learning Research"},{"issue":"2\u20133","key":"2026033014104698700_ref023","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1023\/A:1013689704352","article-title":"Finite-time analysis of the multi-armed bandit problem","volume":"47","author":"Auer","year":"2002","journal-title":"Machine Learning"},{"issue":"1","key":"2026033014104698700_ref024","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539701398375","article-title":"The non-stochastic multi-armed bandit problem","volume":"32","author":"Auer","year":"2002","journal-title":"SIAM Journal on Computing"},{"key":"2026033014104698700_ref025","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10998-010-3055-6","article-title":"UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem","volume":"61","author":"Auer","year":"2010","journal-title":"Periodica Mathematica Hungarica"},{"key":"2026033014104698700_ref026","volume-title":"Proceedings of the International Conference on Learning Theory (COLT)","author":"Auer","year":"2007"},{"key":"2026033014104698700_ref027","author":"Awerbuch","year":"2004"},{"key":"2026033014104698700_ref028","doi-asserted-by":"crossref","first-page":"1932","DOI":"10.1214\/aoms\/1177698023","article-title":"On pseudo-games","volume":"39","author":"Ba\u00f1\u00f3s","year":"1968","journal-title":"Annals of Mathematical Statistics"},{"key":"2026033014104698700_ref029","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"Babaioff","year":"2010"},{"key":"2026033014104698700_ref030","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"Babaioff","year":"2009"},{"key":"2026033014104698700_ref031","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Bach","year":"2011"},{"key":"2026033014104698700_ref032","first-page":"1","volume-title":"Flavors of Geometry","author":"Ball","year":"1997"},{"key":"2026033014104698700_ref033","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Bartlett","year":"2008"},{"key":"2026033014104698700_ref034","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Bart\u00f3k","year":"2010"},{"key":"2026033014104698700_ref035","volume-title":"Lecture notes.","author":"Bart\u00f3k","year":"2011"},{"issue":"3","key":"2026033014104698700_ref036","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","article-title":"Mirror descent and nonlinear projected subgradient methods for convex optimization","volume":"31","author":"Beck","year":"2003","journal-title":"Operations Research Letters"},{"key":"2026033014104698700_ref037","volume-title":"MINERVA Optimization Center Report","author":"Ben-Tal","year":"1999"},{"key":"2026033014104698700_ref038","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1214\/aos\/1069362389","article-title":"Bandit problems with infinitely many arms","volume":"25","author":"Berry","year":"1997","journal-title":"Annals of Statistics"},{"key":"2026033014104698700_ref039","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 15","author":"Beygelzimer","year":"2011"},{"key":"2026033014104698700_ref040","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 15","author":"Beygelzimer","year":"2011"},{"key":"2026033014104698700_ref041","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1051\/ps:2005018","article-title":"Theory of classification: A survey of recent advances","volume":"9","author":"Boucheron","year":"2005","journal-title":"ESAIM: Probability and Statistics"},{"key":"2026033014104698700_ref042","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"Boyd","year":"2004"},{"key":"2026033014104698700_ref043","volume-title":"PhD thesis,Universit\u00e9 Lille 1","author":"Bubeck","year":"2010"},{"key":"2026033014104698700_ref044","volume-title":"Lecture notes","author":"Bubeck","year":"2011"},{"key":"2026033014104698700_ref045","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings volume 23","author":"Bubeck","year":"2012"},{"key":"2026033014104698700_ref046","volume-title":"arXiv","author":"Bubeck","year":"2012"},{"key":"2026033014104698700_ref047","volume-title":"arXiv","author":"Bubeck","year":"2011"},{"key":"2026033014104698700_ref048","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Bubeck","year":"2010"},{"key":"2026033014104698700_ref049","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Bubeck","year":"2009"},{"key":"2026033014104698700_ref050","doi-asserted-by":"crossref","first-page":"1832","DOI":"10.1016\/j.tcs.2010.12.059","article-title":"Pure exploration in finitely-armed and continuously-armed bandits","volume":"412","author":"Bubeck","year":"2011","journal-title":"Theoretical Computer Science"},{"key":"2026033014104698700_ref051","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Bubeck","year":"2009"},{"key":"2026033014104698700_ref052","first-page":"1587","article-title":"X-armed bandits","volume":"12","author":"Bubeck","year":"2011","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014104698700_ref053","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedingsvolume 23","author":"Bubeck","year":"2012"},{"key":"2026033014104698700_ref054","volume-title":"arXiv","author":"Bubeck","year":"2012"},{"key":"2026033014104698700_ref055","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Bui","year":"2011"},{"key":"2026033014104698700_ref056","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1287\/moor.22.1.222","article-title":"Optimal adaptive policies for Markov decision processes","author":"Burnetas","year":"1997","journal-title":"Mathematics of Operations Research"},{"key":"2026033014104698700_ref057","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Busa-Fekete","year":"2011"},{"key":"2026033014104698700_ref058","volume-title":"arXiv","author":"Capp\u00e9","year":"2012"},{"key":"2026033014104698700_ref059","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Carpentier","year":"2011"},{"key":"2026033014104698700_ref060","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Carpentier","year":"2011"},{"key":"2026033014104698700_ref061","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546921","volume-title":"Prediction, Learning, and Games","author":"Cesa-Bianchi","year":"2006"},{"issue":"5","key":"2026033014104698700_ref062","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1016\/j.jcss.2012.01.001","article-title":"Combinatorial bandits","volume":"78","author":"Cesa-Bianchi","year":"2012","journal-title":"Journal of Computer and System Sciences"},{"key":"2026033014104698700_ref063","doi-asserted-by":"crossref","first-page":"2152","DOI":"10.1109\/TIT.2005.847729","article-title":"Minimizing regret with label efficient prediction","volume":"51","author":"Cesa-Bianchi","year":"2005","journal-title":"IEEE Transactions on Information Theory"},{"key":"2026033014104698700_ref064","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s10994-006-5001-7","article-title":"Improved second-order bounds for prediction with expert advice","volume":"66","author":"Cesa-Bianchi","year":"2007","journal-title":"Machine Learning"},{"key":"2026033014104698700_ref065","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Chapelle","year":"2011"},{"key":"2026033014104698700_ref066","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 15","author":"Chu","year":"2011"},{"key":"2026033014104698700_ref067","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718768","volume-title":"Introduction to Derivative-Free Optimization","author":"Conn","year":"2009"},{"issue":"6","key":"2026033014104698700_ref068","doi-asserted-by":"crossref","first-page":"1243","DOI":"10.1109\/TAC.2009.2019797","article-title":"Regret and convergence bounds for a class of continuum-armed bandit problems","volume":"54","author":"Cope","year":"2009","journal-title":"IEEE Transactions on Automatic Control"},{"key":"2026033014104698700_ref069","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)","author":"Coquelin","year":"2007"},{"key":"2026033014104698700_ref070","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Crammer","year":"2011"},{"key":"2026033014104698700_ref071","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Dani","year":"2008"},{"key":"2026033014104698700_ref072","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Dani","year":"2008"},{"key":"2026033014104698700_ref073","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"Devanur","year":"2009"},{"key":"2026033014104698700_ref074","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)","author":"Dud\u00edk","year":"2011"},{"key":"2026033014104698700_ref075","volume-title":"Proceedings of the Annual Conference on Computational Learning Theory (COLT)","author":"Even-Dar","year":"2002"},{"key":"2026033014104698700_ref076","first-page":"1079","article-title":"Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems","volume":"7","author":"Even-Dar","year":"2006","journal-title":"Journal of Machine Learning Research"},{"issue":"1","key":"2026033014104698700_ref077","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1109\/JSTSP.2010.2058091","article-title":"Optimally sensing a single channel without prior information: The tiling algorithm and regret bounds","volume":"5","author":"Filippi","year":"2011","journal-title":"IEEE Journal of Selected Topics in Signal Processing"},{"key":"2026033014104698700_ref078","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Filippi","year":"2010"},{"key":"2026033014104698700_ref079","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Flaxman","year":"2005"},{"key":"2026033014104698700_ref080","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS)","author":"Foster","year":"2012"},{"key":"2026033014104698700_ref081","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1093\/biomet\/85.2.379","article-title":"Asymptotic calibration","volume":"85","author":"Foster","year":"1998","journal-title":"Biometrika"},{"key":"2026033014104698700_ref082","author":"Gabillon","year":"2011"},{"key":"2026033014104698700_ref083","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings volume 19","author":"Garivier","year":"2011"},{"key":"2026033014104698700_ref084","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Garivier","year":"2011"},{"key":"2026033014104698700_ref085","volume-title":"INRIA Technical Report","author":"Gelly","year":"2006"},{"key":"2026033014104698700_ref086","doi-asserted-by":"crossref","DOI":"10.1002\/9780470980033","volume-title":"Multi-armed Bandit Allocation Indices","author":"Gittins","year":"2011","edition":"2"},{"key":"2026033014104698700_ref087","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1111\/j.2517-6161.1979.tb01068.x","article-title":"Bandit processes and dynamic allocation indices","author":"Gittins","year":"1979","journal-title":"Journal of the Royal Statistical Society. Series B (Methodological)"},{"key":"2026033014104698700_ref088","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1023\/A:1010844028087","article-title":"General convergence results for linear discriminant updates","volume":"43","author":"Grove","year":"2001","journal-title":"Machine Learning"},{"key":"2026033014104698700_ref089","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS)","author":"Gr\u00fcnew\u00e4lder","year":"2010"},{"key":"2026033014104698700_ref090","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)","author":"Gy\u00f6rgy","year":"2007"},{"key":"2026033014104698700_ref091","first-page":"2369","article-title":"The on-line shortest path problem under partial monitoring","volume":"8","author":"Gy\u00f6rgy","year":"2007","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014104698700_ref092","first-page":"97","article-title":"Approximation to Bayes risk in repeated play","volume":"3","author":"Hannan","year":"1957","journal-title":"Contributions to the Theory of Games"},{"key":"2026033014104698700_ref093","doi-asserted-by":"crossref","first-page":"1127","DOI":"10.1111\/1468-0262.00153","article-title":"A simple adaptive procedure leading to correlated equilibrium","volume":"68","author":"Hart","year":"2000","journal-title":"Econometrica"},{"key":"2026033014104698700_ref094","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1006\/jeth.2000.2746","article-title":"A general class of adaptive strategies","volume":"98","author":"Hart","year":"2001","journal-title":"Journal of Economic Theory"},{"key":"2026033014104698700_ref095","doi-asserted-by":"crossref","first-page":"287","DOI":"10.7551\/mitpress\/8996.003.0012","volume-title":"Optimization for Machine Learning","author":"Hazan","year":"2011"},{"key":"2026033014104698700_ref096","first-page":"38","author":"Hazan","year":"2009"},{"key":"2026033014104698700_ref097","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Hazan","year":"2011"},{"key":"2026033014104698700_ref098","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Hazan","year":"2010"},{"key":"2026033014104698700_ref099","author":"Helmbold","year":"1997"},{"key":"2026033014104698700_ref100","first-page":"1705","article-title":"Learning permutations with exponential weights","volume":"10","author":"Helmbold","year":"2009","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014104698700_ref101","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1023\/A:1007424614876","article-title":"Tracking the best expert","volume":"32","author":"Herbster","year":"1998","journal-title":"Machine Learning"},{"key":"2026033014104698700_ref102","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56468-0","volume-title":"Fundamentals of Convex Analysis","author":"Hiriart-Urruty","year":"2001"},{"key":"2026033014104698700_ref103","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Honda","year":"2010"},{"key":"2026033014104698700_ref104","volume-title":"Proceedings of the European Conference on Genetic Programming (EuroGP)","author":"Hoock","year":"2010"},{"key":"2026033014104698700_ref105","first-page":"1563","article-title":"Near-optimal regret bounds for reinforcement learning","volume":"11","author":"Jaksch","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014104698700_ref106","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/s11122-006-0005-2","article-title":"Recursive aggregation of estimators by the Mirror Descent algorithm with averaging","volume":"41","author":"Juditsky","year":"2005","journal-title":"Problems of Information Transmission"},{"key":"2026033014104698700_ref107","first-page":"1865","article-title":"Regularization techniques for learning with matrices","volume":"13","author":"Kakade","year":"2012","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014104698700_ref108","volume-title":"On the sample complexity of reinforcement learning","author":"Kakade","year":"2003"},{"key":"2026033014104698700_ref109","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Kakade","year":"2008"},{"key":"2026033014104698700_ref110","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.jcss.2004.10.016","article-title":"Efficient algorithms for online decision problems","volume":"71","author":"Kalai","year":"2005","journal-title":"Journal of Computer and System Sciences"},{"key":"2026033014104698700_ref111","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Kale","year":"2010"},{"key":"2026033014104698700_ref112","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 5","author":"Kanade","year":"2009"},{"key":"2026033014104698700_ref113","volume-title":"Proceedings of the Innovations in Theoretical Computer Science Conference","author":"Kanade","year":"2012"},{"key":"2026033014104698700_ref114","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS),JMLR Workshop and Conference Proceedings volume 22","author":"Kaufmann","year":"2012"},{"key":"2026033014104698700_ref115","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Kaufmann","year":"2012"},{"key":"2026033014104698700_ref116","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1023\/A:1017932429737","article-title":"A sparse sampling algorithm for near-optimal planning in large Markovian decision processes","volume":"49","author":"Kearns","year":"2002","journal-title":"Machine Learning"},{"issue":"3","key":"2026033014104698700_ref117","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1090\/S0002-9939-1953-0055639-3","article-title":"Sequential minimax search for a maximum","volume":"4","author":"Kiefer","year":"1953","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2026033014104698700_ref118","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1214\/aoms\/1177729392","article-title":"Stochastic estimation of the maximum of a regression function","volume":"23","author":"Kiefer","year":"1952","journal-title":"Annals of Mathematical Statistics"},{"key":"2026033014104698700_ref119","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1023\/A:1017938623079","article-title":"Relative loss bounds for multidimensional regression problems","volume":"45","author":"Kivinen","year":"2001","journal-title":"Machine Learning"},{"key":"2026033014104698700_ref120","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Kleinberg","year":"2004"},{"key":"2026033014104698700_ref121","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10994-010-5178-7","article-title":"Regret bounds for sleeping experts and bandits","volume":"80","author":"Kleinberg","year":"2010","journal-title":"Machine Learning"},{"key":"2026033014104698700_ref122","doi-asserted-by":"crossref","DOI":"10.1145\/1374376.1374475","article-title":"Multi-armed bandits in metric spaces","author":"Kleinberg","year":"2008"},{"key":"2026033014104698700_ref123","volume-title":"Proceedings of the European Conference on Machine Learning (ECML)","author":"Kocsis","year":"2006"},{"key":"2026033014104698700_ref124","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Koolen","year":"2010"},{"key":"2026033014104698700_ref125","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1016\/0196-8858(85)90002-8","article-title":"Asymptotically efficient adaptive allocation rules","volume":"6","author":"Lai","year":"1985","journal-title":"Advances in Applied Mathematics"},{"key":"2026033014104698700_ref126","author":"Langford","year":"2007"},{"key":"2026033014104698700_ref127","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1214\/aoap\/1028903453","article-title":"Chernoff-type bound for finite Markov chains","volume":"8","author":"Lezaud","year":"1998","journal-title":"Annals of Applied Probability"},{"key":"2026033014104698700_ref128","volume-title":"Proceedings of the International Conference on World Wide Web (WWW)","author":"Li","year":"2010"},{"key":"2026033014104698700_ref129","doi-asserted-by":"crossref","first-page":"2795","DOI":"10.1109\/TSP.2010.2041600","article-title":"Dynamic multichannel access with imperfect channel state detection","volume":"58","author":"Liu","year":"2010","journal-title":"IEEE Transactions on Signal Processing"},{"key":"2026033014104698700_ref130","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-0-387-49819-5_6","volume-title":"Foundations and Applications of Sensor Management","author":"Mahajan","year":"2008"},{"key":"2026033014104698700_ref131","volume-title":"JMLR Workshop and Conference Proceedings","author":"Maillard","year":"2011"},{"key":"2026033014104698700_ref132","volume-title":"JMLR Workshop and Conference Proceedings","author":"Maillard","year":"2011"},{"key":"2026033014104698700_ref133","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Mannor","year":"2011"},{"key":"2026033014104698700_ref134","first-page":"623","article-title":"The sample complexity of exploration in the multi-armed bandit problem","volume":"5","author":"Mannor","year":"2004","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014104698700_ref135","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"McMahan","year":"2004"},{"key":"2026033014104698700_ref136","volume-title":"Proceedings of the International Conference on Learning Theory (COLT)","author":"McMahan","year":"2009"},{"key":"2026033014104698700_ref137","article-title":"Efficient methods for large-scale convex optimization problems","volume":"15","author":"Nemirovski","year":"1979","journal-title":"Ekonomika i Matematicheskie Metody"},{"key":"2026033014104698700_ref138","doi-asserted-by":"crossref","first-page":"1574","DOI":"10.1137\/070704277","article-title":"Robust stochastic approximation approach to stochastic programming","volume":"19","author":"Nemirovski","year":"2009","journal-title":"SIAM Journal on Optimization"},{"key":"2026033014104698700_ref139","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovski","year":"1983"},{"key":"2026033014104698700_ref140","volume-title":"CORE Discussion Papers","author":"Nesterov","year":"2011"},{"key":"2026033014104698700_ref141","author":"Neu","year":"2010"},{"key":"2026033014104698700_ref142","volume-title":"arXiv","author":"Ortner","year":"2012"},{"key":"2026033014104698700_ref143","volume-title":"arXiv","author":"Perchet","year":"2011"},{"issue":"5","key":"2026033014104698700_ref144","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/1183907.1183911","article-title":"Combining expert advice in reactive environments","volume":"53","author":"Pucci de Farias","year":"2006","journal-title":"Journal of the ACM"},{"key":"2026033014104698700_ref145","volume-title":"Lecture notes on online learning","author":"Rakhlin","year":"2009"},{"key":"2026033014104698700_ref146","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1090\/S0002-9904-1952-09620-8","article-title":"Some aspects of the sequential design of experiments","volume":"58","author":"Robbins","year":"1952","journal-title":"Bulletin of the American Mathematical Society"},{"key":"2026033014104698700_ref147","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1214\/aoms\/1177729586","article-title":"A stochastic approximation method","volume":"22","author":"Robbins","year":"1951","journal-title":"Annals of Mathematical Statistics"},{"key":"2026033014104698700_ref148","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1287\/moor.1100.0446","article-title":"Linearly parameterized bandits","volume":"35","author":"Rusmevichientong","year":"2010","journal-title":"Mathematics of Operations Research"},{"key":"2026033014104698700_ref149","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Salomon","year":"2011"},{"key":"2026033014104698700_ref150","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Seldin","year":"2011"},{"key":"2026033014104698700_ref151","volume-title":"Online learning: Theory, algorithms, and applications","author":"Shalev-Shwartz","year":"2007"},{"key":"2026033014104698700_ref152","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT),JMLR Workshop and Conference Proceedings volume 19.","author":"Slivkins","year":"2011"},{"key":"2026033014104698700_ref153","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Slivkins","year":"2008"},{"key":"2026033014104698700_ref154","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Srebro","year":"2011"},{"key":"2026033014104698700_ref155","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Srinivas","year":"2010"},{"key":"2026033014104698700_ref156","volume-title":"Incomplete information and internal regret in prediction of individual sequences","author":"Stoltz","year":"2005"},{"key":"2026033014104698700_ref157","volume-title":"Reinforcement Learning: An Introduction","author":"Sutton","year":"1998"},{"key":"2026033014104698700_ref158","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01551-9","volume-title":"Algorithms for Reinforcement Learning","author":"Szepesv\u00e1ri","year":"2010"},{"key":"2026033014104698700_ref159","first-page":"773","article-title":"Paths kernels and multiplicative updates","volume":"4","author":"Takimoto","year":"2003","journal-title":"Journal of Machine Learning Research"},{"issue":"8","key":"2026033014104698700_ref160","doi-asserted-by":"crossref","first-page":"5588","DOI":"10.1109\/TIT.2012.2198613","article-title":"Online learning of rested and restless bandits","volume":"58","author":"Tekin","year":"2012","journal-title":"IEEE Transactions on Information Theory"},{"key":"2026033014104698700_ref161","first-page":"65","volume-title":"Advances in Computer Games","author":"Teytaud","year":"2009"},{"key":"2026033014104698700_ref162","first-page":"285","article-title":"On the likelihood that one unknown probability exceeds another in view of the evidence of two samples","volume":"25","author":"Thompson","year":"1933","journal-title":"Bulletin of the American Mathematical Society"},{"key":"2026033014104698700_ref163","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Uchiya","year":"2010"},{"key":"2026033014104698700_ref164","volume-title":"Sequential Analysis","author":"Wald","year":"1947"},{"issue":"4","key":"2026033014104698700_ref165","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1016\/j.aam.2004.10.004","article-title":"Arbitrary side observations in bandit problems","volume":"34","author":"Wang","year":"2005","journal-title":"Advances in Applied Mathematics"},{"issue":"3","key":"2026033014104698700_ref166","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1109\/TAC.2005.844079","article-title":"Bandit problems with side observations","volume":"50","author":"Wang","year":"2005","journal-title":"IEEE Transactions on Automatic Control"},{"key":"2026033014104698700_ref167","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Wang","year":"2008"},{"key":"2026033014104698700_ref168","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (ALT)","author":"Warmuth","year":"2011"},{"key":"2026033014104698700_ref169","first-page":"2287","article-title":"Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension","volume":"9","author":"Warmuth","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"2026033014104698700_ref170","volume-title":"ACM Conference on Electronic Commerce (EC)","author":"Wilkens","year":"2012"},{"key":"2026033014104698700_ref171","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Yu","year":"2011"},{"key":"2026033014104698700_ref172","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1287\/moor.1090.0397","article-title":"Markov decision processes with arbitrary reward processes","volume":"34","author":"Yu","year":"2009","journal-title":"Mathematics of Operations Research"},{"key":"2026033014104698700_ref173","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT)","author":"Yue","year":"2009"},{"key":"2026033014104698700_ref174","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Yue","year":"2011"},{"key":"2026033014104698700_ref175","volume-title":"Proceedings of the International Conference on Machine Learning (ICML)","author":"Zinkevich","year":"2003"}],"container-title":["Foundations and Trends\u00ae in Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftmal\/article-pdf\/5\/1\/1\/11448393\/2200000024en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftmal\/article-pdf\/5\/1\/1\/11448393\/2200000024en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:10:48Z","timestamp":1777486248000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftmal\/article\/5\/1\/1\/1332153\/Regret-Analysis-of-Stochastic-and-Nonstochastic"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,12]]},"references-count":175,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12,12]]}},"URL":"https:\/\/doi.org\/10.1561\/2200000024","relation":{},"ISSN":["1935-8237","1935-8245"],"issn-type":[{"value":"1935-8237","type":"print"},{"value":"1935-8245","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,12]]}}}