Our online BST learns the metric induced by the optimal reference tree using a multiplicative weights update (MWU) scheme. The technique has a rich history, and a recent emergence as a powerful algorithmic tool (we refer to the survey of Arora, Hazan, and Kale [@AroraSurvey]). MWU or closely related techniques have been used previously in data structures (including for BST-related questions), see e.g. [@Blum; @BlumBurch; @in_pursuit; @Kalai]. Specifically, Iacono [@in_pursuit] obtains, using MWU, an online BST that is constant-competitive on sufficiently long sequences, *if any online BST is constant-competitive*. As we relate online BSTs with an offline strategy, the results are not directly comparable.

##### Further open questions and structure of the paper. {#further-open-questions-and-structure-of-the-paper. .unnumbered}

The main open question raised by our work is whether natural algorithms such as Splay or Greedy match the properties of our new BST algorithms. (This must be the case, if Splay and Greedy are, as conjectured, $O(1)$-competitive). We suggest the following easier questions. Do Splay or Greedy satisfy the unified bound with a time-window of $2$ steps? Does Splay satisfy the lazy finger or the $2$-monotone bounds? Does Greedy satisfy the $2$-finger bound?

Except for Theorems \[thm: LF simulation\] and \[thm:decomp\], the factors in 