Experiment Planning with Function Approximation

Summary

The paper studies the problem of static experiment planning under the function approximation setting, which contrasts with the adaptive setting where the reward is not observable during the static planning phase. The paper proposes two static planning strategies: (1) EluderPlanner based on Eluder Dimension, and (2) Naive uniform sampler, and analyzes their regret, achieving a cumulative regret similar to the OLS and SquareCB algorithms in their adaptive counterparts. The paper takes a step further by designing a special tree-structured function class that highlights the gap between the proposed static planning algorithms and the lower bound of adaptive learning in terms of regret. Finally, the paper addresses the problem of model selection and demonstrates the possibility of constructing an $\varepsilon$-optimal policy.

Strengths

Clear motivation and good writing: - I enjoyed reading the motivational example in the introduction that explains why adaptive learning scenarios can be challenging. - All the problem setups and the relations with the related literature are clearly explained. - The structure of the paper is good and easy to follow. - Assumptions are well explained, and the definition of Eluder dimension is helpful. Novelty: - Combining Eluder dimension and static experiment planning appears to be a novel approach. - The lower bound construction in Section 5 is informative and demonstrates a fundamental gap between static planning and adaptive learning. Theoretical soundness: - I read through the main text, and all the derivations seem correct to me.

Weaknesses

Related work on reward-free RL: I found reward-free RL to be closely related, especially [1], which also describes reward-free RL under function approximation. It would be good to have a short paragraph discussing reward-free RL in general. [1] Shuang Qiu, Jieping Ye, Zhaoran Wang, Zhuoran Yang. "On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game."

Questions

I am not familiar with Eluder dimension, but I find the construction of the function class in Section 5 extremely interesting. Will there be a similar gap for some of our familiar non-linear function classes, such as neural networks or kernel spaces, between static planning and adaptive learning?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

n/a

Summary

The paper addresses the problem of experiment planning with function approximation in contextual bandit problems. It is intended to solve the scenario that the datasets include a large amount of contexts while no rewards. The authors propose two experiment planning strategies that are compatible with function approximation: an eluder planning and sampling procedure. The theoretical results guarantee that the policy converges to optimially under the time constrained by the eluder dimension.

Strengths

This algorithm achieves in this setting: the reward signal is not abundant while there are a large amount of the contexts. The uniform experiment planning algorithms help solve the setting. Two important questions are answered in this problem: (1)are existing adaptive cumulative regret algorithms already optimal for simple regret minimization? (2) is static experiment planning sufficient to match the simple regret guarantees of adaptive learning for realizable contextual bandits?

Weaknesses

1.The paper does not provide a detailed comparison with existing experiment planning algorithms to show the improvement of the algorithm, especially in the function approximation like linear function. Enough related works and comparisons are needed in this paper. 2.The main results and the proof is lack of proof intuition to highlight the keypoint. The results need a clear and intuitive proof sketch to help readers follow the idea. The results are lack of a lower bound to guarantee the optimality of the algorithm. A tight bound is needed. If not, the gap of the lower bound and the upper bound is needed to state. 3.The paper could benefit from a more detailed discussion of the limitations of the proposed approach.

Questions

1. Is there a specific experiment to show the performance of the algorithm?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No. The paper could benefit from a more detailed discussion of the limitations of the proposed approach.

Summary

The authors study the problem of planning for efficient data collection. Given initial data with a lot of contexts but no reward, the question is how do you devise a policy for data collection such that when executed in the real world, it learns the reward optimally to finally learn a policy with maximum rewards. They propose two methods for it, i) eluder planning and a sampling procedure ii) uniform sampler for the case when the number of actions is small

Strengths

Proposed algorithms for experiment planning and theoretically analyze them. They also showed suboptimality of the existing adaptive learning algorithms which is interesting. Line 138-139, the intuition of the eluder dimension helps to understand its use case

Weaknesses

The paper was hard for me to grab fully. Partially I lack background but majorly, I think it was the writing part. Some ideas to improve them: 1) Either go with a short, vague intro or a precise long intro: currently, it is a long but vague intro since the problem setting was not defined early, and it becomes difficult to understand. I have seen theoretical papers which define problem statements in the intro, and then it's a precise long intro. 2) Since you continuously refer to the sampling and planning phase, may be use a block diagram to represent them. In general, I believe the writing style can be improved. Secondly, I was wondering if it would make sense to also add at least a preliminary experiment showcasing your theory? It is hard to get intuition on how tight the bounds are.

Questions

Intuitively when is it possible to have $d_{eluder}(F, B/T)$ a sublinear function in T? I am not able to interpret theorem 4.1 properly, on what factors does $\tilde{c}$ depends. Consider writing it as: let T be the smallest integer satisfying the $T\geq....$, then \for all $T' \geq T$ $\pi_{T'}$ is optimal? line 94,166: typos

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

1 poor

Presentation

1 poor

Contribution

3 good

Limitations

no negative societal impact

Summary

The study focuses on the experiment planning problem for contextual bandits with function approximation. The paper gives two algorithms for the problem: (1) EluderPlanning algorithm whose sample complexity depends on the elder dimension of the function class and matches the sample complexity of OLS algorithm by a online-to-batch conversion. (2) It also suggest that simple uniform sampling is good when action space is small, and the sample complexity matches the SquareCB algorithm by online-to-batch conversion. Then, the paper suggest that there is an exponential gap between adaptive sampling and passive sampling (experimental planning) by finding a class of tree-structured function. Besides, for this class of function, the paper show that SquareCB and OLS (two adaptive sampling algorithm) have exponential large sample complexity while there exist an algorithm with reliability (called adaptive tree sampling in appendix) can achieve polynomial sample complexity in this tree-structured function class. This suggest the sub-optimality of SquareCB and OLS. Finally, address the problem of model selection when the learner is presented with a family of reward function classes and the true reward function is inside one of the reward function classes.

Strengths

The tree-structured function class constructed in section 5 is interesting and elegant. With this function class, the paper point out an exponential separation between adaptive sampling algorithm. Also, it points out that in realisable setting, the online-to-batch conversion of SquareCB and OLS is suboptimal for simple regret minimization.

Weaknesses

(1) The proof of Lemma A.4 has a *major flaw*: in Line 439, it is not valid to choose $\eta_t$ as a random variable that is dependent on the martingale difference sequence. This is because the moment generating function (MGF) is required to derive lemma A.3 and thus also for lemma A.4. It is valid only when the MGF coefficient $\eta$ is a fixed value, which is also reflected in the claim of lemma A.3 (eta is fixed outside the probability bound). More generally, MGF coefficient $\eta$ can be a random variable that is independent of whole martingale difference sequence and then distribution of sum of martingale difference sequence is not affected by conditioning on $\eta$. (2) Because of (1) and Lemma A.4 serves a fundamental step for most theoretical claims in appendix A, section 3 and section 6. All claims related to lemma A.4 may not be correct, including but not limited to Lemma A.5, Lemma A.7, Lemma A.8, Lemma 3.6, Theorem 3.4 and Proposition 6.1. (3) There are a few typos that would affect the understanding of the technical details. (4) Even if all claims can be corrected, the main contribution is not clean in the paper where too many issues are discussed.

Questions

(1) See weaknesses. If all problems can be correctly resolved, I would consider increasing the score. (2) There is a claim "Our results indicate the eluder dimension is not the sharpest statistical complexity measure to characterize learning in this setting." in line 326, but I don't find any support to this claim.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

N/A

Summary

We study the static experiment planning for policy learning problem in contextual bandits, with focus on the general realizable case. The paper first presents an algorithm using reward free, extending similar ideas in [37] and leveraging the eluder dimension. The paper then shares a few theoretical results, including the competitive guarantee for uniform sampling policy, the gap between static and adaptive policies in a special case, and the results in model selection.

Strengths

* The paper is technically sound. * The writing is very clear. * The paper studies an important problem and the first proposed algorithm is useful.

Weaknesses

Numerical results on the finite sample performance would be important to have. For example, although the asymptotic rate for uniform sampling is competitive and this fact might be surprising, it is expected that its finite-sample performance is worse. It is also not fully clear how significant these theoretical findings are. For example, it is expected that there is some performance gap between adaptive and static policies, when the task is hard (though I appreciate formally proving it).

Questions

1. It would be helpful to add outputs to your Algorithm tables 2. In the main text, it would help to discuss the connection to [37] in terms of the reward-free emulation idea. 3. "Extracting Policy from Data" - the intuition for this part is hard to understand. Why uniform sampling + optimistic, instead of just using the greedy (or pessimistic) policy?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Extensions to safe exploration and/or policy evaluation tasks would be meaningful and worthy some discussions.

About the major concern

If you are going to use Theorem 2.2 in "Bias no more" to replace the lemma A.4 in your paper, you might need to justify all of your result remain the same at least in the dominant term. It might need a huge amount of derivations from the beginning, which might be another paper then.

Constant $\tilde c$

Thank you so much for your question. The constant $\tilde c$ will be something like $100$ or so. This comes from a repeated application of Hoeffding bounds. Think of these constants as a substitute of $O$ or $\Omega$ notation. They are completely independent of $\mathcal{F}$, $\delta$ and any other problem dependent parameters. Instead of tracking the precise value of this constant (which would have made the computations tedious and burdensome) we instead substituted them by these symbols. We are happy to explain more if this is not clear.

Step by step explanation

Theorem 2.2 in Bias no More states that for any $\delta_T \in (0,1)$ $\sum_{t=1}^T X_t \leq C \sqrt{ V \ln(C/\delta_T) } + 2CB\ln(C/\delta_T) $ (1) with probability at least $1-\delta_T$ where $V = \sum_{t=1}^T E_t[X_t^2]$ and $B = \max{ | X_i|} \leq R$ and $C = \log^2(B) + \log(B)\log(T)$. The anytime version of this lemma is $\sum_{t=1}^T X_t \leq C \sqrt{ V \ln(6CT^2/\delta) } + 2CB\ln(6T^2C/\delta) $ (2) for all $T \in \mathbb{N}$ with probability at least $1-\delta$. This can be proven by applying (1) setting $\delta_T = \delta/6T^2$, a union bound and using the fact that $\sum_{t=1}^\infty \frac{1}{t^2} < 6$. Substiting the definitions of $V$ and $B$ into equation (2) yields, $\sum_{t=1}^T X_t \leq C' (\log^2(R )+ \log(R)\log(T))\sqrt{ \sum_{t=1}^T E_t[X_t^2] \ln(T*(\log^2(R )+ \log(R)\log(T)))/\delta)} + C' (\log^2(R )+ \log(R)\log(T))R\ln(T(\log^2(R )+ \log(R)\log(T)))/\delta) $ For some \textbf{universal constant} $C'$. This is because trivially $\ln(6CT^2/\delta) = \mathcal{O}( \ln( T*(\log^2(R )+ \log(R)\log(T)))/\delta ) )$. This recovers Lemma A.4 up to logarithmic factors (i.e. if we call $C = (\log^2(R )+ \log(R)\log(T)))$) the bound above looks like, $\sum_{t=1}^T X_t \leq C'C\sqrt{ \sum_{t=1}^T E_t[X_t^2] \ln(CT/\delta)} + C' C R\ln(CT/\delta) $. with probability at least $1-\delta$ for all $T \in \mathbb{N}$.

Follow up

Dear Reviewer, We wanted to reiterate our commitment to have the reviewer's questions addressed. Please let us know if the response above addressed the reviewer's concerns. If these have been adequately addressed we would very much appreciate any indication of this. Thanks so much! The Authors