Section  makes two contributions beyond the aforementioned literature. First, we show that the equilibrium of Chernoff's two player game has a simple structure in our problem. This result allows us to restrict to algorithms we call context independent. [1]} writes down the min-max optimization problems defining sample complexity under both context-dependent and context-independent sampling rules, but does not observe that these are equal. DTS satisfies this context independence property, which greatly simplifies our analysis of it. In particular, we can mostly follow [2]}, [3]} and [4]}, who showed that top-two sampling algorithms attain lower bounds in the style of [5]} in problems without contexts.
