On testing transitivity in online preference learning

B. Haddenhorst, V. Bengs, E. Hüllermeier, Machine Learning (2021) 2063–2084.

Download
No fulltext has been uploaded.
Journal Article | Published | English
Author
; ;
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>
Publishing Year
Journal Title
Machine Learning
Page
2063-2084
LibreCat-ID

Cite this

Haddenhorst B, Bengs V, Hüllermeier E. On testing transitivity in online preference learning. Machine Learning. Published online 2021:2063-2084. doi:10.1007/s10994-021-06026-2
Haddenhorst, B., Bengs, V., & Hüllermeier, E. (2021). On testing transitivity in online preference learning. Machine Learning, 2063–2084. https://doi.org/10.1007/s10994-021-06026-2
@article{Haddenhorst_Bengs_Hüllermeier_2021, title={On testing transitivity in online preference learning}, DOI={10.1007/s10994-021-06026-2}, journal={Machine Learning}, author={Haddenhorst, Björn and Bengs, Viktor and Hüllermeier, Eyke}, year={2021}, pages={2063–2084} }
Haddenhorst, Björn, Viktor Bengs, and Eyke Hüllermeier. “On Testing Transitivity in Online Preference Learning.” Machine Learning, 2021, 2063–84. https://doi.org/10.1007/s10994-021-06026-2.
B. Haddenhorst, V. Bengs, and E. Hüllermeier, “On testing transitivity in online preference learning,” Machine Learning, pp. 2063–2084, 2021, doi: 10.1007/s10994-021-06026-2.
Haddenhorst, Björn, et al. “On Testing Transitivity in Online Preference Learning.” Machine Learning, 2021, pp. 2063–84, doi:10.1007/s10994-021-06026-2.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar