Chasing Nested Convex Bodies Nearly Optimally

The convex body chasing problem, introduced by Friedman and Linial, is a competitive analysis problem on any normed vector space. In convex body chasing, for each timestep t∈mathbb N, a convex body Ktsubseteq mathbb Rd is given as a request, and the player picks a point xt∈ Kt. The player aims to ensure that the total distance sumt=0T-1||xt-xt+1|| is within a bounded ratio of the smallest possible offline solution. In this work, we consider the nested version of the problem, in which the sequence (Kt) must be decreasing. For Euclidean spaces, we consider a memoryless algorithm which moves to the so-called Steiner point, and show that in a certain sense it is exactly optimal among memoryless algorithms. For general finite dimensional normed spaces, we combine the Steiner point and our recent previous algorithm to obtain a new algorithm which is nearly optimal for all ℓpd spaces with p≥ 1, closing a polynomial gap.