{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:37:34Z","timestamp":1764175054342,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T00:00:00Z","timestamp":1626048000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T00:00:00Z","timestamp":1626048000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["317046553"],"award-info":[{"award-number":["317046553"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008007","name":"Universit\u00e4t Paderborn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008007","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The efficiency of state-of-the-art algorithms for the dueling bandits problem is essentially due to a clever exploitation of (stochastic) transitivity properties of pairwise comparisons: If one arm is likely to beat a second one, which in turn is likely to beat a third one, then the first is also likely to beat the third one. By now, however, there is no way to test the validity of corresponding assumptions, although this would be a key prerequisite to guarantee the meaningfulness of the results produced by an algorithm. In this paper, we investigate the problem of testing different forms of stochastic transitivity in an online manner. We derive lower bounds on the expected sample complexity of any sequential hypothesis testing algorithm for various forms of stochastic transitivity, thereby providing additional motivation to focus on weak stochastic transitivity. To this end, we introduce an algorithmic framework for the dueling bandits problem, in which the statistical validity of weak stochastic transitivity can be tested, either actively or passively, based on a multiple binomial hypothesis test. Moreover, by exploiting a connection between weak stochastic transitivity and graph theory, we suggest an enhancement to further improve the efficiency of the testing algorithm. In the active setting, both variants achieve an expected sample complexity that is optimal up to a logarithmic factor.<\/jats:p>","DOI":"10.1007\/s10994-021-06026-2","type":"journal-article","created":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T19:14:13Z","timestamp":1626117253000},"page":"2063-2084","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On testing transitivity in online preference learning"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4023-6646","authenticated-orcid":false,"given":"Bj\u00f6rn","family":"Haddenhorst","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viktor","family":"Bengs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eyke","family":"H\u00fcllermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,12]]},"reference":[{"issue":"7","key":"6026_CR1","first-page":"1","volume":"22","author":"V Bengs","year":"2021","unstructured":"Bengs, V., Busa-Fekete, R., El Mesaoudi-Paul, A., & H\u00fcllermeier, E. (2021). Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research, 22(7), 1\u2013108.","journal-title":"Journal of Machine Learning Research"},{"key":"6026_CR2","first-page":"5","volume":"37","author":"JC Bermond","year":"1972","unstructured":"Bermond, J. C. (1972). Ordres \u00e0 distance minimum d\u2019un tournoi et graphes partiels sans circuits maximaux. Math\u00e9matiques et Sciences humaines, 37, 5\u201325.","journal-title":"Math\u00e9matiques et Sciences humaines"},{"issue":"3\/4","key":"6026_CR3","doi-asserted-by":"publisher","first-page":"324","DOI":"10.2307\/2334029","volume":"39","author":"RA Bradley","year":"1952","unstructured":"Bradley, R. A., & Terry, M. E. (1952). Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika, 39(3\/4), 324\u2013345.","journal-title":"Biometrika"},{"issue":"1","key":"6026_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000024","volume":"5","author":"S Bubeck","year":"2012","unstructured":"Bubeck, S., & Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1), 1\u2013122.","journal-title":"Foundations and Trends in Machine Learning"},{"key":"6026_CR5","first-page":"1071","volume-title":"Proceedings of the International Conference on Machine Learning","author":"R Busa-Fekete","year":"2014","unstructured":"Busa-Fekete, R., H\u00fcllermeier, E., Sz\u00f6r\u00e9nyi, B. (2014). Preference-based rank elicitation using statistical models: The case of Mallows. In: Proceedings of the International Conference on Machine Learning (ICML), pp 1071\u20131079."},{"issue":"3","key":"6026_CR6","first-page":"327","volume":"4","author":"FP Cantelli","year":"1993","unstructured":"Cantelli, F. P. (1933). Considerazioni sulla legge uniforme dei grandi numeri e sulla generalizzazione di un fondamentale teorema del sig. Paul L\u00e9vy. Giornale dell\u2019Istituto Italiano degli Attuari, 4(3), 327\u2013350.","journal-title":"Paul L\u00e9vy. Giornale dell\u2019Istituto Italiano degli Attuari"},{"issue":"2","key":"6026_CR7","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1037\/dec0000011","volume":"1","author":"DR Cavagnaro","year":"2014","unstructured":"Cavagnaro, D. R., & Davis-Stober, C. P. (2014). Transitive in our preferences, but transitive in different ways: An analysis of choice variability. Decision, 1(2), 102.","journal-title":"Decision"},{"key":"6026_CR8","unstructured":"Chen, L., & Li, J. (2015). On the optimal sample complexity for best arm identification. CoRR. (abs\/1511.03774)."},{"key":"6026_CR9","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1145\/2433396.2433420","volume-title":"Proceedings of ACM International Conference on Web Search and Data Mining","author":"X Chen","year":"2013","unstructured":"Chen, X., Bennett, P.N., Collins-Thompson, K., Horvitz, E. (2013). Pairwise ranking aggregation in a crowdsourced setting. In: Proceedings of ACM International Conference on Web Search and Data Mining (WSDM), pp 193\u2013202."},{"key":"6026_CR10","first-page":"14591","volume-title":"Proceedings of Advances in Neural Information Processing Systems","author":"R Degenne","year":"2019","unstructured":"Degenne, R., Koolen, W.M. (2019). Pure exploration with multiple correct answers. In: Proceedings of Advances in Neural Information Processing Systems (NeurIPS), pp 14591\u201314600."},{"key":"6026_CR11","first-page":"7060","volume-title":"Proceedings of Advances in Neural Information Processing Systems","author":"M Falahatgar","year":"2017","unstructured":"Falahatgar, M., Hao, Y., Orlitsky, A., Pichapati, V., Ravindrakumar, V. (2017a). Maxing and ranking with few assumptions. In: Proceedings of Advances in Neural Information Processing Systems (NIPS), pp 7060\u20137070."},{"key":"6026_CR12","first-page":"1088","volume-title":"Proceedings of International Conference on Machine Learning","author":"M Falahatgar","year":"2017","unstructured":"Falahatgar, M., Orlitsky, A., Pichapati, V., Suresh, A.T. (2017b). Maximum selection and ranking under noisy comparisons. In: Proceedings of International Conference on Machine Learning (ICML), pp 1088\u20131096."},{"key":"6026_CR13","first-page":"1426","volume-title":"Proceedings of International Conference on Machine Learning","author":"M Falahatgar","year":"2018","unstructured":"Falahatgar, M., Jain, A., Orlitsky, A., Pichapati, V., Ravindrakumar, V. (2018). The limits of maxing, ranking, and preference learning. In: Proceedings of International Conference on Machine Learning (ICML), pp 1426\u20131435."},{"issue":"1","key":"6026_CR14","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1214\/aoms\/1177703731","volume":"35","author":"RH Farrell","year":"1964","unstructured":"Farrell, R. H. (1964). Asymptotic behavior of expected sample size in certain one sided tests. The Annals of Mathematical Statistics, 35(1), 36\u201372.","journal-title":"The Annals of Mathematical Statistics"},{"key":"6026_CR15","volume-title":"Mathematical statistics: A decision theoretic approach Probability and mathematical statistics","author":"TS Ferguson","year":"1967","unstructured":"Ferguson, T. S. (1967). Mathematical statistics: A decision theoretic approach Probability and mathematical statistics. Cambridge: Academic Press."},{"issue":"4","key":"6026_CR16","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0022-2496(73)90021-7","volume":"10","author":"PC Fishburn","year":"1973","unstructured":"Fishburn, P. C. (1973). Binary choice probabilities: On the varieties of stochastic transitivity. Journal of Mathematical Psychology, 10(4), 327\u2013352.","journal-title":"Journal of Mathematical Psychology"},{"key":"6026_CR17","first-page":"998","volume-title":"Proceedings of Annual Conference on Learning Theory","author":"A Garivier","year":"2016","unstructured":"Garivier, A., Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. In: Proceedings of Annual Conference on Learning Theory (COLT), pp 998\u20131027."},{"key":"6026_CR18","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-642-33460-3_12","volume-title":"Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases","author":"S Guo","year":"2012","unstructured":"Guo, S., Sanner, S., Graepel, T., Buntine, W. (2012). Score-based Bayesian skill learning. In: Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases (ECML\/PKDD), pp 106\u2013121."},{"issue":"2","key":"6026_CR19","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0165-4896(85)90031-9","volume":"10","author":"G Iverson","year":"1985","unstructured":"Iverson, G., & Falmagne, J. C. (1985). Statistical issues in measurement. Mathematical Social Sciences, 10(2), 131\u2013153.","journal-title":"Mathematical Social Sciences"},{"key":"6026_CR20","first-page":"1001","volume-title":"Proceedings of International Conference on Artificial Intelligence and Statistics","author":"A Korba","year":"2017","unstructured":"Korba, A., Cl\u00e9men\u00e7on, S., Sibony, E. (2017). A learning theory of ranking aggregation. In: Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp 1001\u20131010."},{"key":"6026_CR21","volume-title":"Individual choice behavior: A theoretical analysis","author":"RD Luce","year":"1959","unstructured":"Luce, R. D. (1959). Individual choice behavior: A theoretical analysis. Amsterdam: Wiley."},{"issue":"1","key":"6026_CR22","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1093\/biomet\/44.1-2.114","volume":"44","author":"CL Mallows","year":"1957","unstructured":"Mallows, C. L. (1957). Non-null ranking models. Biometrika, 44(1), 114\u2013130.","journal-title":"Biometrika"},{"key":"6026_CR23","first-page":"2344","volume-title":"Proceedings of International Conference on Machine Learning","author":"L Maystre","year":"2017","unstructured":"Maystre, L., Grossglauser, M. (2017). Just sort it! A simple and effective approach to active preference learning. In: Proceedings of International Conference on Machine Learning (ICML), pp 2344\u20132353."},{"issue":"2","key":"6026_CR24","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1006\/cogp.1997.0669","volume":"34","author":"TP McNamara","year":"1997","unstructured":"McNamara, T. P., & Diwadkar, V. A. (1997). Symmetry and asymmetry of human spatial memory. Cognitive Psychology, 34(2), 160\u2013190.","journal-title":"Cognitive Psychology"},{"key":"6026_CR25","first-page":"2488","volume-title":"Proceedings of International Conference on Machine Learning","author":"S Mohajer","year":"2017","unstructured":"Mohajer, S., Suh, C., Elmahdy, A. (2017). Active learning for top-$$k$$ rank aggregation from noisy comparisons. In: Proceedings of International Conference on Machine Learning (ICML), pp 2488\u20132497."},{"issue":"1","key":"6026_CR26","first-page":"193","volume":"24","author":"RL Plackett","year":"1975","unstructured":"Plackett, R. L. (1975). The analysis of permutations. Journal of the Royal Statistical Society Series C (Applied Statistics), 24(1), 193\u2013202.","journal-title":"Journal of the Royal Statistical Society Series C (Applied Statistics)"},{"key":"6026_CR27","volume-title":"Stochastic processes. Wiley series in probability and statistics probability and statistics","author":"S Ross","year":"1996","unstructured":"Ross, S. (1996). Stochastic processes. Wiley series in probability and statistics probability and statistics. Amsterdam: Wiley."},{"key":"6026_CR28","volume-title":"Einf\u00fchrung in die Theorie der endlichen Graphen","author":"H Sachs","year":"1971","unstructured":"Sachs, H. (1971). Einf\u00fchrung in die Theorie der endlichen Graphen. Hanser."},{"key":"6026_CR29","first-page":"11","volume-title":"Proceedings of the International Conference on Machine Learning","author":"N Shah","year":"2016","unstructured":"Shah, N., Balakrishnan, S., Guntuboyina, A., Wainwright, M. (2016). Stochastically transitive models for pairwise comparisons: Statistical and computational issues. In: Proceedings of the International Conference on Machine Learning (ICML), pp 11\u201320."},{"key":"6026_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1862-1","volume-title":"Sequential analysis: Tests and confidence intervals. Springer series in statistics","author":"D Siegmund","year":"1985","unstructured":"Siegmund, D. (1985). Sequential analysis: Tests and confidence intervals. Springer series in statistics. Berlin: Springer."},{"key":"6026_CR31","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1093\/biomet\/48.3-4.303","volume":"48","author":"P Slater","year":"1961","unstructured":"Slater, P. (1961). Inconsistencies in a schedule of paired comparisons. Biometrika, 48, 303\u2013312.","journal-title":"Biometrika"},{"key":"6026_CR32","first-page":"5502","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Y Sui","year":"2018","unstructured":"Sui, Y., Zoghi, M., Hofmann, K., Yue, Y. (2018). Advancements in dueling bandits. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp 5502\u20135510."},{"key":"6026_CR33","first-page":"604","volume-title":"Proceedings of Advances in Neural Information Processing Systems","author":"B Sz\u00f6r\u00e9nyi","year":"2015","unstructured":"Sz\u00f6r\u00e9nyi, B., Busa-Fekete, R., El\u00a0Mesaoudi-Paul, A., H\u00fcllermeier, E. (2015). Online rank elicitation for Plackett-Luce: A dueling bandits approach. In: Proceedings of Advances in Neural Information Processing Systems (NIPS), pp 604\u2013612."},{"issue":"2","key":"6026_CR34","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s002650100346","volume":"50","author":"TA Waite","year":"2001","unstructured":"Waite, T. A. (2001). Intransitive preferences in hoarding gray jays (Perisoreus canadensis). Behavioral Ecology and Sociobiology, 50(2), 116\u2013121.","journal-title":"Behavioral Ecology and Sociobiology"},{"issue":"2","key":"6026_CR35","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1214\/aoms\/1177731118","volume":"16","author":"A Wald","year":"1945","unstructured":"Wald, A. (1945). Sequential tests of statistical hypotheses. The Annals of Mathematical Statistics, 16(2), 117\u2013186.","journal-title":"The Annals of Mathematical Statistics"},{"issue":"3","key":"6026_CR36","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1214\/aoms\/1177730197","volume":"19","author":"A Wald","year":"1948","unstructured":"Wald, A., & Wolfowitz, J. (1948). Optimum character of the sequential probability ratio test. The Annals of Mathematical Statistics, 19(3), 326\u2013339.","journal-title":"The Annals of Mathematical Statistics"},{"key":"6026_CR37","first-page":"1201","volume-title":"Proceedings of International Conference on Machine Learning","author":"Y Yue","year":"2009","unstructured":"Yue, Y., Joachims, T. (2009). Interactively optimizing information retrieval systems as a dueling bandits problem. In: Proceedings of International Conference on Machine Learning (ICML), pp 1201\u20131208."},{"key":"6026_CR38","first-page":"241","volume-title":"Proceedings of International Conference on Machine Learning","author":"B Yue","year":"2009","unstructured":"Yue, Y., Joachims, T. (2011). Beat the mean bandit. In: Proceedings of International Conference on Machine Learning (ICML), pp 241\u2013248."},{"issue":"5","key":"6026_CR39","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1016\/j.jcss.2011.12.028","volume":"78","author":"Y Yue","year":"2012","unstructured":"Yue, Y., Broder, J., Kleinberg, R., & Joachims, T. (2012). The $$k$$-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5), 1538\u20131556.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06026-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06026-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06026-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T21:34:49Z","timestamp":1632778489000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06026-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,12]]},"references-count":39,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["6026"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06026-2","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2021,7,12]]},"assertion":[{"value":"22 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}