Adaptive Regret for Bandits Made Possible: Two Queries Suffice

Thank you for your valuable feedback!

Typos and ambiguous notations: thanks for pointing them out! We will fix the typos and make the notations precise and consistent. In particular, we will add more details to explaining the algorithm.

Thank you for your valuable feedback! Your comments are addressed below. We note that a log(T) to 2 improvement in the number of queries needed is significant for computational efficiency, for applications such as hyperparameter optimization in expensive settings.

Trade-off between regret and query: We believe such trade-off is in fact non-trivial; however we will add a brief discussion. For example, as shown in Daniely et al 15, there is an $\tilde{O}(\sqrt{T})$ regret upper bound with $O(\log T)$ queries, and an $\Omega(T^{1-\epsilon})$ regret lower bound with one query. Here an $O(\log T)$ save in query actually costs an $\Omega(T^{\frac{1}{2}-\epsilon})$ term in regret, and it's non-trivial to show with two queries the cost in regret becomes logarithmic. In addition, a $\log T$ to $2$ improvement in the number of queries needed is significant for computational efficiency, for applications such as hyperparameter optimization in expensive settings.

Intention of the bandits setting: the setting we consider is not the original bandit setting, for which a lower bound was already shown by Daniely et al 15. Instead, our main motivation is to reduce the number of queries when they are costly, which is naturally modeled by our multi-point feedback bandit-like setting.

Lower bound on $\tilde{r}_t(k)$: thank you for pointing it out! This issue can be easily resolved, and we describe two ways below and will use the second method to clarify our paper.

The straightforward way is by multiplying an $\frac{1}{2\log T}$ term to the choice of $\eta\_k$ in line 6 of Algorithm 1, at the cost of an additional $2\log T$ term in regret, which is negligible in our context. Let's lower bound $\tilde{r}\_t(k)$: by the definition of $\hat{\ell}\_t$ (line 11), it's a sparse vector where only the coordinate $x'\_t$ can have a positive value $\frac{1}{P(t)\_{x'\_t}}$. However, $P(t)\_{x'\_t}$ is lower bounded by $\frac{v(t,k)\_{x'\_t}}{2\log T}$ by its definition (line 9), thus $\tilde{r}\_t(k)\ge -2\log T$. Now, making $\eta\_k\le \frac{1}{4\log T}$ ensures the desired property that $\eta\_k \tilde{r}\_t(k)\ge-\frac{1}{2}$.

The better way is by hedging over only the range $k\in [2+2\log \log T, \log T]$ instead of $[0,\log T]$ in the algorithm. To see this, by the definition of $\eta_k$, this issue doesn't exist when $2^k \ge 4\log T$, and the only problematic case is when we consider very small intervals with length $2^k< 4\log T$. However, for small intervals with length $O(\log T)$, our regret bound holds trivially and automatically, therefore this method will address the issue with no cost at regret.

Thank you for your valuable feedback! Your comments are addressed below.

Non-negativity of $\tilde{w}\_t(k)$: thank you for pointing it out! This issue can be easily resolved, and we describe two ways below and will use the second method to clarify our paper.

The straightforward way is by multiplying an $\frac{1}{2\log T}$ term to the choice of $\eta\_k$ in line 6 of Algorithm 1, at the cost of an additional $2\log T$ term in regret, which is negligible in our context. To see this, notice the non-negativity of $\tilde{w}\_t(k)$ is guarded by the non-negativity of $1+\eta\_k \tilde{r}\_t(k)$. Let's lower bound $\tilde{r}\_t(k)$: by the definition of $\hat{\ell}\_t$ (line 11), it's a sparse vector where only the coordinate $x'\_t$ can have a positive value $\frac{1}{P(t)\_{x'\_t}}$. However, $P(t)\_{x'\_t}$ is lower bounded by $\frac{v(t,k)\_{x'\_t}}{2\log T}$ by its definition (line 9), thus $\tilde{r}\_t(k)\ge -2\log T$. Now, making $\eta\_k\le \frac{1}{4\log T}$ ensures the desired non-negativity.

The better way is by hedging over only the range $k\in [2+2\log \log T, \log T]$ instead of $[0,\log T]$ in the algorithm. To see this, by the definition of $\eta_k$, this issue doesn't exist when $2^k \ge 4\log T$, and the only problematic case is when we consider very small intervals with length $2^k< 4\log T$. However, for small intervals with length $O(\log T)$, our regret bound holds trivially and automatically, therefore this method will address the issue with no cost at regret.

Pessimistic lower bound: Note that to get our bound, we essentially pick the "better" of both query points since we get a query for free. Therefore, when the algorithm incurs any $\Omega(1)$ fraction of the cost of the "worst" of both queries, the lower bound would therefore hold. Since the average loss would incur half the cost of the best and worst queries, it follows that the regret of the lower bound will appear.

Black-box experts: by black-box we mean the expert can be any online optimization algorithm as long as it has the guarantee of Lemma 2, and EXP-3 is one of them. We will clarify this point.

Meaning of $2^k|t+1$: here it means when $k$ satisfies $t+1$ is divisible by $2^k$, we restart the $kth$ expert by re-initializing its weight to be $\eta_k$.

$w_t$ must be $x_t$: we will fix this typo.

Thank you for your valuable feedback! Your questions are addressed below.

Weak experiments: We will add experiments with higher time horizon and repeats, as well as looking at the practical tradeoff in the reward curve vs. computational/sample efficiency. Note that the theory there for optimal rates are non-trivial but in practice, we can use the naive lower-variance estimator.

Question 1: if we consider expected regret in MAB, it's equivalent to regret in simplex. We will clarify this point more carefully.

Question 2: we will make it clear the calling of Algorithm 2 only concerns the weight updating.

Question 3: we will add more details as you suggested.

Question 4: Thanks for the suggestion! The code is now already implemented as part of an open source package. We will add a link to that OSS package for the camera-ready version, to avoid anonymity issues.