Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits

Thanks for the detailed review and informative comments over the numerical experiments. We then present our response.

About numerical experiments: The overall computational cost of the algorithm is $O(K^2Td^2)$, where the major challenge is the linear dependence on the number of arms $K$. In the case $K$ is small, we conduct simple experiments using random feature vectors generated by np.random.rand(). However, due to computational cost, we can at most run with the configuration $T=4000, d = 20, K = 40$ and $M=7$. In such parameter regime, the regret bound depends mainly on the constant. As a result, our algorithm is no better than BatchLinUCB (the batch version of LinUCB), but better than the BatchPureExp (Algorithm 5 in Han et. al., 2020). We have added the code and result to the supplementary materials.

About the constants: For the constant in the upper bound, we provide a rough estimation of $C_{\mathrm{upper}} = 10000$ (see Lemma 5 and equation(30) and noting that $\alpha = \sqrt{50\ln(KTd/\delta)}, L = \frac{1}{200\ln(Td/\delta)}$ ); for the lower bound, the constant would be $C_{\mathrm{lower}} =1/100000$ (see Lemma 18). The constants are just absolute constants, which depends on the constants in the Lemmas, e.g., general equivalence lemma, concentration inequalitis and elliptical potential lemma. We remark that we also hide some logarithmic terms within the $\tilde{O}(\cdot)$ notation.

We thank the reviewer for careful review. We present the response as below.

About the comparison with the lower bound in [Han et. al., 2020]: Thanks for the suggestion. The lower bound in Hat et.al., is based on Gaussian contexts. Here we present a brief comparison, and will fix accordingly in the revision. The lower bound in [Han et. al., 2020] is $\Omega( T^{\frac{1}{2-2^{-M+1})}}d^{\frac{1-2^{-M+1}}{2-2^{-M+1}}} )$. In comparison, our lower bound is (assume $K\geq d$ for simplicity), where the first part $\min\\{\Omega(T^{\frac{1}{2-2^{-M+2}}}d^{\frac{1-2^{-M+2}}{2-2^{-M+2}}} ), \Omega( T^{\frac{1}{2-2^{-M+1}}}d^{\frac{1}{2-2^{-M+1}}} ) \\}$, which is strictly better than that in [Han et. al., 2020]. The reason is that, the context distribution in [Han et.al., 2020] is a non-mixed Gaussian distribution, which is easy to learn; while the context distribution in our case could be arbitrary distributions. In the counterexample, we let the context distribution be a mixture of a group of hard instances for different horizons. As a result, we obtain improved lower bounds.

About $\epsilon_t$ and $\mathcal{F}_k$: Thanks for the careful review. We have fixed accordingly in the revision.

Thanks for the careful review and insightful questions. We try to answer your question as follows.

About difference between $m$ and $n$ in Line 276-281: Here we restate the difference between $m$ and $n$. The learner have $m$ samples to learn the context distribution, and then have $n$ samples following this policy to conduct linear regression. Each sample here is a context $\\{x_1,x_2,...,x_K\\}$ and a pair $\\{a, r\\}$ such that $r=x_{a}^{\top}\theta+\epsilon$ ($\epsilon$ is a zero-mean noise) is the reward by playing $x_a$.

Write the $i$-th sample as $(x_{1,i},x_{2,i},...,x_{K,i}, a_i, r_i)$ for $1\leq i \leq m+n$.

For the first $m$ samples, we do not care the chosen arms and the reward feedback $(a_j, r_j)_{j=1}^m$, and use only the context information to learn the context distribution.

While in the next $n$ samples, the learner choose $a_j$ according to some certain policy, and compute $\hat{\theta} =(\lambda \mathbf{I}+\sum_{j=m+1}^{m+n}x_{a_j,j}x_{a_j,j}^{\top} )^{-1}\sum_{j=m+1}^{m+n}x_{a_j,j} r_j$.

In the case $m$ is larger than $n$, the width of the confidence region is dominated by the uncertainty in the $n$ samples. That is, even if assuming the full knowledge of the context distribution, the confidence region still has width $\Omega(\sqrt{d/n})$.

In the case $n$ is larger than $m$, the learner can not find the desired exploration policy (consider the case $m=1$ so that the learner can only play the local optimal-design policy), and the confidence width is limited by $\Omega(d/m)$.

We remark that, one can still get a $m$-free bound of $\tilde{O}(\sqrt{d^2/n})$ by the local optimal-design policy. So it is still open what is the real optimal possible width of the confidence region.

In our problem, $m,n$ are roughly the sizes of two consecutive batches. For example, $m = \Theta(T_3)$ and $n = \Theta(T_4)$. As a result, $n$ is generally much more larger than $m$, which implies an improvement over the result in [Zanette et.al., 2021].

About the restarting framework: Both algorithms take advantage of statistical independence from the restarting framework, which help simplify the analysis and remove the lower order terms.

We first thank the reviewer for constructive suggestions. We reply to the questions as below.

About time cost: The algorithm is based on arm elimination so the time cost depends on the number of arms $K$ polynomially. The exact time cost is $O(TK^2d^2)$, which is dominated by arm elimination in each round.

About motivation for stochastic contexts: The problem is motivated by stable environments with expensive policy deployment and communication cost, e.g., large-scale online advertisement and recommendation systems. In these cases, the distribution of user behavior changes slowly in a certain period, which allows assumption on stochastic contexts.