Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the setting where it is not possible (e.g. not allowed or difficult) to update a policy while it interacts with a system. The authors suggest to build, from a batch of historical contexts, an explorative policy, non-reactive, that is not updated online as it interacts with the system, to gather informative data that are finally used to build a near-optimal policy.

The explorative policy (Planner) consists in a mixture of policies built offline from the historical contexts so as to minimize the uncertainty. The main idea is that using this mixture of policies on the real system will also gather data so as to reduce the uncertainty.

Sample complexity bounds and bounds on the performance of the final policy are derived. The algorithm is also compared with other strategies in numerical experiments.



main_review: I think the setting studied by the authors is motivated by applications of policies in real life problems and such studies are missing from the literature. Therefore this could be a relevant contribution to the community.

The paper is well-written. Although the main ideas and algorithms are clear, some parts would benefit from more explanations, clarifications.

Major comments:
- please clarify the objective in the introduction: minimize the number of samples required to achieve a tolerance error of $\varepsilon$?
- the authors say that they apply LinUCB with an empirical reward function set to 0. Although I understand the algorithm, I am not sure to understand the part about setting the empirical reward function to 0.
- I would like the authors to elaborate on the necessity of using a mixture of policies.
-line 167 "in the presence of reward signal": I am confused because the reward is not used here by the fixed policy, it is just stored to build $\hat \pi$. I think the important thing is that the policy is fixed and non-reactive. It could be reactive by using the contexts only. The sentence used by the authors appear to be misleading here.
- Section 6: lots of typos, this section should be proof read. examples: through (line 201), at different speeds (line 211), missing or added $'$ at wrong places  (equation (9) and line 205), Lemma 2 (line 230).
- Experiments: can the author define "policy value"? The description of the synthetic dataset (lines 265-274) is hard to follow/understand. When the authors write "In category $i$, the action $a=i$", does $i$ belong to $\{1, 2, 3\}$. In Figure 2.(b), action 6 and 7 appear important while from the explanations and the setup it seems to me it should be action 5 and 6. For the learning to rank experiments, except for S-P 10 the result does not appear to be significant compared to the random strategy given the error bars. How are the error bars defined?
- Although the action space is state dependent $\mathcal{A}_s$ in the introduction, is it assumed in the bounds that we in fact have a product $\mathcal{S} \times \mathcal{A}$?
- How does the bounds/results compare with a strategy that would be able to update a policy online? the reactive policy could use the rewards and thus explore and reduce uncertainty where it is potentially useful for the reward. Whereas here we explore so as to reduce a global uncertainty not in the important directions? I think this is briefly mentionned in the conclusion, where such reward information could be used additionally to the contexts.

Minor comments:
- There is an issue with the biblio. 2 papers appear twice in the references. The issue is coming from "Szepesvári" vs "Szepesvari"
- line 35: a context-dependent action set $a \in \mathcal{A}_s$ -> although understandable this is not completely rigorous to put the $a$ here as you introduce a "set" in the text. please reformulate.
- Introduction: $d$ and $\epsilon$ are used at several places but are not defined.
- section 3. please define $\Omega$ notation.
- line 134: please explain the uncertainty (related to the G criterion from optimal design literature: minimizes the worst possible predicted variance).
- using both $\pi_e$ and $\pi_{mix}$ is confusing.
- Theorem 1: $\varepsilon$ should be defined at the beginning of the statement ("Let $\varepsilon \leq 1$) as it is used in $M$ and $N$.
limitations_and_societal_impact: -
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: [summary]

This paper considers the problem of efficient nonadaptive sampling to find the best bandit policy, given an offline context data is available. The authors propose an algorithm and provide its sample complexity analysis. Empirical results show the efficicay of the proposed method.

main_review: 

Originality 4/5: I think the problem is novel.

Quality 4/5: It's fine for the first paper on this problem.

Clarity 3/5: There are some typos in important places, but I am sure they are addressable.

Significance 3/5: this is hard to say, but I don't see an immediate clear application (see below for my comments)

Overall, the problem is novel, but I'd like to see a more specific scenarios where it make sense. Otherwise, the contribution seems solid as a first solution on this problem, modulo some details as I describe below.

I'd like to see a former argument on the lower bound. It's not immediately obvious how Chu'11 and Abbasi-Yadkori'11 would lead to the stated bound in line 179 (although I am convinced that the stated rate should be the right one).

I'd like to see some discussions on the tightness of M >= d^3/\eps^2 for small $S\times A$. Is it a technical difficulty or is it unimprovable?

Please identify the actual application of the proposed problem. The proposed problem is not reward maximization but policy identification, so I don't think one would like to use it for recommendation systems becuase it will not maximize the cumulative reward. It will have to be like $\epsilon$ greedy where one uses this sampler for $\epsilon$ portion of the traffic. Otherwise, there are pure exploration problems like A/B testing.

re: Eq (5).  consider the arm set consists of canonical vectors (e_1, ..., e_d) and when we pull arm $e_i$ like $N_i$ times and use the MLE to estimate $\hat\theta$. Consider that the context space is a singleton, so that $|S|\times|A|=d$. Then, we have 
$$\\|\hat\theta-\theta^*\\|^2_{\Sigma} = \sum_{i=1}^d N_i  (\hat{\theta}_i - \theta^\*_i)^2  \lessapprox \sum_i N_i \frac{1}{N_i} = d$$
, which I believe is not improvable. This seems to conflict Eq. (5) which implies that we should get $\log(d)$ instead of $d$. 

* reading the proof in later sections, I realized that perhaps the LHS of Eq (5) is a typo, and in the derivation one should not apply the cauchy-schwarz in Eq. (3) & (4).

The description of $\alpha$ is confusing because it was not explicitly defined in the main text (my apologies if I missed it). Although it was impilcitly mentioned in line 163, L155 says 'a key choice is the parameter $\alpha$...', which will confuse readers.  Theorem 1 should also explicitly state what  $\alpha$ one has to use.

[minor comments]

* why say 'nonreactive' rather than 'nonadaptive', which is the standard terminology..? 
* I would increase the resolution of Figure 1 for better readability.
* L199: \Sigma_M => \Sigma_m??
* L203: remove prime from U'_m
* Proof of Theorem 1
  * Eq (15): why do we have \log(N) instead of \sqrt{\log(N)}??
* experiments
  * clarification: for each trial, the arms are drawn and then fixed throughout, right?
  * L269-271: explanation here can be improved. It starts by 'in category i', but then it uses \Sigma_1 in the normal distribution. I would assume that it was meant to be \Sigma_i.
  * please define `policy value' mathematically.
* figure 2: (b) it sems like S-P would pull arm 6 and 7 for some time, but the description from the main text (L272) indicate that they should be 5 and 6. There seems to be a bug/typo here?

----
**after rebuttal**
I am satisfied with the rebuttal. I will keep the score.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the experimental design for the contextual linear bandits. The goal of the problem is to collect a dataset for identifying a good policy (an estimation of the reward vector). This paper provides algorithms for their goal and theoretically analyzes the sample complexity. Experimental results are also provided.
main_review: The paper is well-written. Although I didn't carefully check all the proofs, the theoretical results intuitively make sense to me. 

The problem can be viewed as a reward-free exploration in linear contextual bandits. My main concern is regarding the significance of the problem studied, given existing work on reward-free RL, i.e., see Jin et al 2020, "Reward-Free Exploration for Reinforcement Learning" and many follow-up works (some of them also study the case with linear function approximation, e.g., Wang et al 2020, "On reward-free reinforcement learning with linear function approximation"). Since contextual bandit can be viewed as a special case of RL by setting horizon H=1, I wonder if the results presented in this paper can be directly obtained from these existing results. Discussions/comparisons with respect to reward-free RL are missing in the paper.

Another question is with respect to Ruan et al 2020. The author mentioned that similar results can be derived from their Thm 6 and offline complexity O(d^{16}). I agree that d^16 is high-suboptimal. However, it seems that the more important parameter is 1/\epsilon. Their results completely get rid of dependence on 1/\epsilon. Results derived in this paper have 1/\epsilon^2 dependence, which looks suboptimal to me. 

====after rebuttal====

I have read the rebuttal and would like to keep my score at 5. I suggest a major revision of the current submission to include a detailed discussion of the reward-free RL literature, e.g., what can be directly obtained from existing results and what are the new results in the current submission. Personally, I would not take the problem setting as a main/novel contribution of this paper due to its similarity to existing papers.
limitations_and_societal_impact: See section 8.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a new setting for the stochastic contextual linear bandit problem: using past contexts only, design a non-reactive policy for future online data. They argue that this setting arises in practice since often it may be logistically too complicated to deploy an online machine learning algorithm. They measure the quality of the dataset by the performance of the greedy policy that uses the least-square predictor on the collected data in the online phase. They develop a new two-phase algorithm (a planner and a sampler) for this problem and provide sample complexity guarantees. They also demonstrate the performance of their algorithm empirically. 
main_review: I think that the setting is original and is convincingly related to practice and I consider it a contribution in and of itself. The algorithm is interesting, especially the application of reward-free LinUCB in the planner phase. Section 6 is helpful and clarifies the main steps in the argument. The experiments demonstrate the usefulness of the algorithm.

The authors claim that the algorithm achieves the minimax lower bound on the number of online samples, but do not state a bound or give a reference for this. This would be helpful to clarify. It is also not clear whether the number of offline contexts is optimal. Can something be said about this? A discussion would be helpful.

It seems that while the planner never uses either the rewards or the actions available in the offline. A discussion might be helpful highlighting this. Is there any reason to believe that these could be used in an algorithm to achieve improved performance? In practice, does one ever have only the contexts and not the rewards or actions?

After discussion: the algorithm seems useful, but the novelty of the setting and the technical contribution seem more limited than I originally thought. I think a detailed discussion of the connection to the reward-free RL literature would be helpful. 
limitations_and_societal_impact: Yes. They discuss using an algorithm that is robust to all values of regularization and the issue of the offline and online distributions potentially differing.
review_title: null

Meta-review: This paper considers the following variant of the linear contextual bandit problem: Given historical data, design a non-reactive policy that can be used on future gather data that can be used to learn a near-optimal policy. The reviews felt that the problem is well-motivated, and that the problem setting and techniques both have some novelty. However, concerns were raised regarding the overlap between the algorithmic ideas used here and in previous work on reward-free exploration in RL; this should be addressed in the final version of the paper.
Decision: Accept (Poster)