Smooth Contextual Bandits: Bridging the Parametric and Nondifferentiable Regret Regimes

References

• Agarwal A, Hsu D, Kale S, Langford J, Li L, Schapire RE (2014) Taming the monster: A fast and simple algorithm for contextual bandits. Proc. 31st Internat. Conf. Machine Learn., vol. 32 (JMLR.org), II–1638–II–1646.Google Scholar
• Audibert JY, Tsybakov AB (2005) Fast learning rates for plug-in classifiers under the margin condition.Google Scholar
• Audibert JY, Tsybakov AB (2007) Fast learning rates for plug-in classifiers. Ann. Statist. 35(2):608–633.Crossref, Google Scholar
• Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Machine Learn. 47(2–3):235–256.Crossref, Google Scholar
• Auer P, Cesa-Bianchi N, Freund Y, Schapire RE (1995) Gambling in a rigged casino: The adversarial multi-armed bandit problem. Proc. IEEE 36th Annual Foundations Comput. Sci., 322–331.Google Scholar
• Bartlett PL, Bousquet O, Mendelson S (2005) Local Rademacher complexities. Ann. Statist. 33(4):1497–1537.Crossref, Google Scholar
• Bastani H, Bayati M (2020) Online decision making with high-dimensional covariates. Oper. Res. 68(1):276–294.Link, Google Scholar
• Bastani H, Bayati M, Khosravi K (2020) Mostly exploration-free algorithms for contextual bandits. Management Sci. 67(3):1329–1349.Google Scholar
• Belloni A, Chernozhukov V, Chetverikov D, Kato K (2015) Some new asymptotic theory for least squares series: Pointwise and uniform results. J. Econometrics 186(2):345–366.Crossref, Google Scholar
• Bertsimas D, Kallus N (2019) From predictive to prescriptive analytics. Management Sci. 66(3):1025–1044.Link, Google Scholar
• Beygelzimer A, Langford J, Li L, Reyzin L, Schapire R (2011) Contextual bandit algorithms with supervised learning guarantees. Gordon G, Dunson D, Dudík M, eds. Proc. 14th Internat. Conf. Artificial Intelligence Statist., Proc. Machine Learn. Res., vol. 15 (PMLR, Fort Lauderdale, FL), 19–26.Google Scholar
• Bubeck S, Cesa-Bianchi N (2012) Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations Trends® Machine Learn. 5(1):1–122.Google Scholar
• Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Chen X (2007) Large sample sieve estimation of semi-nonparametric models. Handbook of Econometrics, vol. 6, 5549–5632.Google Scholar
• Dudik M, Hsu D, Kale S, Karampatziakis N, Langford J, Reyzin L, Zhang T (2011) Efficient optimal learning for contextual bandits. Proc. 27th Conf. Uncertainty Artificial Intelligence (AUAI Press, Arlington, VA), 169–178.Google Scholar
• Fontaine X, Berthet Q, Perchet V (2019) Regularized contextual bandits. The 22nd Internat. Conf. Artificial Intelligence Statist., 2144–2153.Google Scholar
• Goldenshluger A, Zeevi A (2009) Woodroofe’s one-armed bandit problem revisited. Ann. Appl. Probab. 19(4):1603–1633.Crossref, Google Scholar
• Goldenshluger A, Zeevi A (2013) A linear response bandit problem. Stochastic Systems 3(1):230–261.Link, Google Scholar
• Gur Y, Momeni A, Wager S (2019) Smoothness-adaptive contextual bandits.Google Scholar
• Lai T, Robbins H (1985) Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6(1):4–22.Crossref, Google Scholar
• Langford J, Zhang T (2007) The epoch-greedy algorithm for contextual multi-armed bandits. Proc. 20th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc.), 817–824.Google Scholar
• Mammen E, Tsybakov AB (1999) Smooth discrimination analysis. Ann. Statist. 27(6):1808–1829.Crossref, Google Scholar
• Nadaraya E (1964) On estimating regression. Theory Probab. Appl. 9(1):141–142.Crossref, Google Scholar
• Perchet V, Rigollet P (2013) The multi-armed bandit problem with covariates. Ann. Statist. 41(2):693–721.Crossref, Google Scholar
• Reeve H, Mellor J, Brown G (2018) The k-nearest neighbour UCB algorithm for multi-armed bandits with covariates. Proc. Algorithmic Learn. Theory (PMLR), 83, 725–752.Google Scholar
• Rigollet P, Zeevi A (2010) Nonparametric bandits with covariates. Proc. 23rd Annual Conf. Learn. Theory, 54–66.Google Scholar
• Slivkins A (2011) Contextual bandits with similarity information. Proc. 24th Annual Conf. Learn. Theory (JMLR Workshop and Conference Proceedings), 679–702.Google Scholar
• Steinwart I, Hush D, Scovel C (2006) An explicit description of the reproducing kernel Hilbert spaces of Gaussian RBF kernels. IEEE Trans. Inform. Theory 52(10):4635–4643.Crossref, Google Scholar
• Stone CJ (1977) Consistent nonparametric regression. Ann. Statist. 5(4):595–620.Crossref, Google Scholar
• Stone CJ (1980) Optimal rates of convergence for nonparametric estimators. Ann. Statist. 8(6):1348–1360.Crossref, Google Scholar
• Stone CJ (1982) Optimal global rates of convergence for nonparametric regression. Ann. Statist. 10(4):1040–1053.Crossref, Google Scholar
• Tsybakov AB (2004) Optimal aggregation of classifiers in statistical learning. Ann. Statist. 32(1):135–166.Crossref, Google Scholar
• Tsybakov AB (2008) Introduction to nonparametric estimation. 1st ed. (Springer, New York).Google Scholar
• Valko M, Korda N, Munos R, Flaounas I, Cristianini N (2013) Finite-time analysis of kernelised contextual bandits. Proc. 29th Conf. Uncertainty Artificial Intelligence, 654–663.Google Scholar
• Wang CC, Kulkarni SR, Poor HV (2005) Bandit problems with side observations. IEEE Trans. Automatic Control 50(3):338–355.Crossref, Google Scholar
• Watson GS (1964) Smooth regression analysis. Sankhyā Indian J. Statist. Ser. A (1961–2002) 26(4):359–372.Google Scholar