TopRank+: A Refinement of TopRank Algorithm
This work provides an incremental improvement to an existing algorithm for online learning to rank, which is important for applications like search engines and recommendation systems.
The paper tackled the problem of improving the TopRank algorithm for online learning to rank by refining its self-normalized inequalities, resulting in a tighter bound and enhanced performance estimation.
Online learning to rank is a core problem in machine learning. In Lattimore et al. (2018), a novel online learning algorithm was proposed based on topological sorting. In the paper they provided a set of self-normalized inequalities (a) in the algorithm as a criterion in iterations and (b) to provide an upper bound for cumulative regret, which is a measure of algorithm performance. In this work, we utilized method of mixtures and asymptotic expansions of certain implicit function to provide a tighter, iterated-log-like boundary for the inequalities, and as a consequence improve both the algorithm itself as well as its performance estimation.