Let $\mathfrak{B}$ be a set, which will be called the set of bins. Suppose we have five maps \begin{align*} \mathrm{Value} &: \mathfrak{B} \to \mathbb{R} \\ \mathrm{Upper} &: \mathfrak{B} \to \mathbb{R} \\ \mathrm{Lower} &: \mathfrak{B} \to \mathbb{R} \\ \mathrm{Size} &: \mathfrak{B} \to (0,1] \\ \mathrm{Split} &: \mathfrak{B} \times\{0,1\} \to \mathfrak{B} \end{align*} such that \begin{align*} \forall b\in\mathfrak{B}, &\qquad \mathrm{Value}(b)= \mathrm{Value}\big(\mathrm{Split}(b,0)\big) + \mathrm{Value}\big(\mathrm{Split}(b,1)\big) \\ \forall b\in\mathfrak{B}, &\qquad \mathrm{Lower}(b) \le \mathrm{Value}(b) \le \mathrm{Upper}(b) \\ \forall b\in\mathfrak{B}, &\qquad \mathrm{Upper}(b) - \mathrm{Lower}(b) \le \big(\mathrm{Size}(b)\big)^2 \\ \forall s\in\{0,1\}, \forall b \in \mathfrak{B}, &\qquad \mathrm{Size}\big( \mathrm{Split}(b,s) \big)= \frac{1}{2} \cdot \mathrm{Size}(b) \\ \forall b \in \mathfrak{B}, &\qquad \sum_{s \in \{0,1\}}\Big(\mathrm{Upper}\big( \mathrm{Split}(b,s) \big) - \mathrm{Lower}\big( \mathrm{Split}(b,s) \big)\Big) \le \frac{1}{2} \cdot \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \end{align*}
Given a bin $\bar{b} \in \mathfrak{B}$ and we want to calculate $\mathrm{Value}(\bar{b})$.
Unfortunately, we don't have direct access to the function $\mathrm{Value}$, but we have black-box access to the functions $\mathrm{Upper}, \mathrm{Lower}$, and $\mathrm{Size}$.
We start with $B_0 :=\{\bar{b}\}$ and we proceed according to the following interaction protocol:
for $t=1,2,\dots$
- For each $b \in B_{t-1}$, observe $\mathrm{Upper}(b)$, $\mathrm{Lower}(b)$ and $\mathrm{Size}(b)$;
- Select $b_t\in B_{t-1}$;
- $B_t := \big(B_{t-1} \backslash \{b_t\} \big) \cup \{\mathrm{Split}(b_t,0),\mathrm{Split}(b_t,1)\}$;
Our goal is to be as efficient as possible (i.e., with less interactions as possible) to get a sharp estimate of $\mathrm{Value}(\bar{b})$.
A possible algorithm to solve this problem can be:
Algorithm 1
for $t=1,2,\dots$
- Select $b_t \in \mathrm{argmax}_{b \in B_{t-1}}\big(\mathrm{Size}(b)\big)$;
Algorithm 1 completely ignores the functions $\mathrm{Upper}$ and $\mathrm{Lower}$ in making its choices. Nonetheless, if $n \in \mathbb{N}$ and $t = 2^{n}-1$ we have that $\forall b \in B_t, \mathrm{Size}(b) \le 2^{-n}$, and the number of elements of $B_t$ is $2^n$, so \begin{equation*} \sum_{b \in B_t} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \le \sum_{b \in B_t} (2^{-n})^2 = 2^{-n} = \frac{1}{t+1}\;. \end{equation*} and \begin{equation*} \sum_{b \in B_t} \mathrm{Lower}(b) \le \sum_{b \in B_t} \mathrm{Value}(b) = \mathrm{Value}(\bar{b}) = \sum_{b \in B_t} \mathrm{Value}(b) \le \sum_{b \in B_t} \mathrm{Upper}(b)\;. \end{equation*} Furthermore, notice that up to worsening the constant, we can make work the previous bound for any $t \in \mathbb{N}$.
Since the previous algorithm completely fails to be adaptive to the information provided by $\mathrm{Upper}$ and $\mathrm{Lower}$, I think that a better algorithm should be the following one:
Algorithm 2
for $t=1,2,\dots$
- Select $b_t \in \mathrm{argmax}_{b \in B_{t-1}}\big(\mathrm{Upper}(b) - \mathrm{Lower}(b)\big)$;
The idea is that Algorithm 2 splits the bin where the current available estimate is the sloppiest.
However, the obvious idea to analyze it, namely that at each time $t \in \mathbb{N}$ we have $t$ bins in $B_{t-1}$, and given that we are selecting $b_t \in \mathrm{argmax}_{b \in B_{t-1}}\big(\mathrm{Upper}(b) - \mathrm{Lower}(b)\big)$, we have that: \begin{align*} \sum_{b \in B_{t}}& \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) = \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) - \big(\mathrm{Upper}(b_{t}) - \mathrm{Lower}(b_t)\big) \\ &\qquad+ \sum_{s \in \{0,1\}}\Big(\mathrm{Upper}\big( \mathrm{Split}(b_t,s) \big) - \mathrm{Lower}\big( \mathrm{Split}(b_t,s) \big)\Big) \\ &\quad\le \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big)-\frac{1}{2} \big( \mathrm{Upper}(b_t) - \mathrm{Lower}(b_t)\big) \\ &\quad\le \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big)-\frac{1}{2t} \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \\ &\quad= \frac{2t-1}{2t} \cdot \sum_{b \in B_{t-1}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \;, \end{align*} leads by induction to just \begin{equation*} \sum_{b \in B_{t}} \big( \mathrm{Upper}(b) - \mathrm{Lower}(b) \big) \le \frac{1\cdot 3 \cdot\ldots \cdot (2t-1)}{2\cdot4\cdot\ldots \cdot 2t} = \Theta(t^{-1/2}), \end{equation*} where the last equality follows from this and this. Now, this proof line leads to a rate of convergence for Algorithm 2 that is just a $\Theta(t^{-1/2})$, which is worse than the $O(1/t)$-bound we have obtained above for Algorithm 1.
What am I missing? Can it really be the case that Algorithm 2 has a worse rate of convergence than Algorithm 1?