Provably Efficient Learning in Partially Observable Contextual Bandit

Q: The problem setup is spread out into multiple sections and it takes the reader a long time to understand the main topic to be explored.

A: In response to this feedback, we have made improvements to help readers understand the problem setup more efficiently. We have included a notation table in Appendix A, which provides a concise overview of the main notations used in the paper. This addition aims to assist readers in understanding the contributions and key concepts.

Furthermore, we have a preliminaries section that outlines the basic settings related to transfer learning. This section provides foundational information to establish a common understanding before delving into the specifics of the transfer tasks.

To maintain coherence and clarity, we introduce the main contents of each transfer task separately, rather than presenting them all at once. This approach allows readers to grasp the relevant information progressively and maintain a logical flow throughout the paper.

We appreciate the feedback and have taken steps to enhance the organization and presentation of the problem setup in order to make it more accessible to readers.

Q: Since this paper is dealing with a subtle topic at the intersection of bandit, transfer learning, and partial monitoring, a thorough comparison with the existing work should be expected, detailing the connection and difference, which seems missing in the current version

A: We acknowledge the importance of comparing our work with existing literature in order to provide a comprehensive understanding of the field. While it is not feasible to compare every related work within the constraints of a 9-page limit, we have made efforts to provide relevant comparisons in terms of our approaches and theoretical results.

In the paper, we compare our causal bounds with those presented in [1]. We demonstrate the tightness of our bounds by showcasing the limitations of the bounds in [1] and provide a numerical experiment in Section 4 to support our claims.

Additionally, we compare our proposition 3.1 with the result presented in [2] and explain the practical implications of our findings. We also generalize the result in [3] through theorem 3.1 and compare the order dependence on policy space in our theorem 3.3 with [4], highlighting the intuitive improvement achieved.

[1] Bounds on causal effects and application to high dimensional data [2] Partial counterfactual identification from observational and experimental data. [3] Transfer learning in multi-armed bandit: a causal approach. [4] Bounding causal effects on continuous outcome.

Q: Some relevant references are missing

A: In the new version, we cite your mentioned papers in the related work and compare the difference in terms of settings.

Q: Suggestions on structures.

A: Thank you for your feedback. Following your suggestions, we utilize the additional one page allowed by ICLR to incorporate the necessary information, including a conclusion subsection and brief descriptions about appendix structure. The following content is added in the additional one page.

" In this paper, we investigate transfer learning in partially observable contextual bandits by converting the problem to identifying or partially identifying causal effects between actions and rewards. We derive causal bounds with the existence of partially observable confounders using our proposed Monte-Carlo algorithms. We formally prove and empirically demonstrate that our causally enhanced algorithms outperform classical bandit algorithms and achieve orders of magnitude faster convergence rates.

There are several future research directions we wish to explore. Firstly, we aim to investigate whether the solutions to discretization optimization converge to those of the original problem. While the approximation error can be exactly zero when all referred random variables are discrete, it is still unclear which conditions for general random variables and discretization methods can lead to convergence. We conjecture that this property may be related to the sensitivity of the non-linear optimization problem.

Lastly, we aim to extend our IGW-based algorithm to continuous action settings. IGW has been successfully applied to continuous action settings and has shown practical advantages in large action spaces. This extension may be related to complexity measures in machine learning. "

" In appendix A, we put the omitted information regarding the examples, algorithms, theorems, implementation details and numerical setup. We also put partial related work section due to the strict page limitation of ICLR. In appendix B, you can find all proofs about claimed theorems. In appendix B, you can find some related materials about causal tools. In appendix D, we generalize our sampling method on general simplex more than the special one defined by the special optimization (1). In appendix E, we put a conclusion section and discuss the future work. "

For other suggestions, we modify our paper accordingly according to the page limit and modification requirement.

Q: There are many pointers to Appendix which somewhat distracts the flow.

A: Thank you for your feedback. We understand your concern regarding the pointers to the appendix and their potential impact on the flow of the paper. We have included these pointers to ensure that important details and results are not omitted due to the strict page limitation. By providing references to the relevant sections in the appendix, we aim to maintain the logical flow of the paper while still providing comprehensive information. We will make sure that the pointers are clear and effectively guide readers to the corresponding sections in the appendix.

Q: In Page 8 near at the end, I don't get the argument here about instrumental variables. If they rely on IV, you may argue that your method is free of IV requirement. It is a bit unnecessary to mention that finding IV is an open problem in academia (Economics?).

A: We modify this sentence in the updated version. We actually want to show that our method does not rely on IVs as you mentioned in your reviews.

Q: this paper would be more like for AISTATS, CLeaR (causal conference), NeurIPS, ICML ... I wonder why the authors pick the ICLR as the 'best' revenue to present the results. I don't see any part 'representation learning' involved.

A: We appreciate your perspective on the suitability of the paper for different conferences. While ICLR is commonly associated with representation learning, it also welcomes submissions from various topics, including reinforcement learning, causal learning, and transfer learning. Our paper falls within the scope of ICLR as it addresses transfer learning in the context of causal reinforcement learning. We acknowledge that representation learning may not be explicitly mentioned in our paper, but the broader topics covered in ICLR encompass the themes and techniques we explore. Moreover, ICLR has accepted papers in the areas of reinforcement learning, causal learning, and transfer learning in the past.

Q: The transfer learning problem for PO Contextual bandits is not well motivated.

A: Transfer learning in partially observable contextual bandit settings is motivated by practical examples such as autonomous driving. In this scenario, human drivers possess experiential knowledge that is not captured by sensors alone. Works such as [1,2] have explored similar settings and investigated the problem.

Your mentioned "The expert summarizes ... to find the optimal policy faster" also serves as the motivation for this paper.

Q: The example on Page 3 is supposed to motivate, "direct approaches can lead to a policy function that is far from the true optimal policy". But I was not able to see this. How do you get the numbers 1.81? Rather, isn't the example motivating the need for considering U in the policy, if available?

A: Thanks for pointing out the typo. We mistakenly added the do notation. The intention of the example was to demonstrate that directly transferring the conditional expectation E[Y|A,W] can be suboptimal in certain cases. Of course, having more information about the models will generally be helpful. It is necessary to consider the knowledge of U if it is available, but the way to use U should be carefully designed.

Q: The claim on sample complexity of the joint distribution F(a, y , w, u) given F(u) as well as F(a, y ,w) separately, is quite different from learning the full joint distribution from scratch. Therefore the comparison with existing sample complexity analysis is slightly misleading.

A: The knowledge about the distribution only affects the width of the causal bounds. The key difference between existing methods [1,2] and ours lies in transferred online learning algorithms. As we explain, they treat each basis policy as an independent arm in bandit problems, which is often invalid as similar policies can provide information to each other. For example, the optimal policy and the second optimal policy typically yield similar actions and only differ in a small amount of contexts. This is the intuition behind how we improve this order dependence.

To address these challenges, we need to modify the classical IGW technique, which requires non-trivial modifications of its proof. We introduce the subspace of explored policies and show how the causal bounds can shrink its size. You can find the full proof in Appendix

Q: $x_{ijkl}$ is not very informative as a subscript.

A: $x_{ijkl}$ can be understood as representing the PMF of the joint distribution $F(a,y,w,u)$ on the space $\mathcal{A}_i \times \mathcal{Y}_j \times \mathcal{W}_k \times \mathcal{U}_l$.

Q: The authors claim improving regret from $\sqrt {|\Pi|}$ to $\sqrt{\log(|\Pi|)}$, but Table 1 shows regret proportional to sqrt(|A|) for the algorithms proposed.

A: $\Pi$ is the policy space and $A$ is the action space. The induced policy space in the function approximation setting is

\Pi = \{\pi_f(x): a= \mathop{argmax}_a f(x,a) }.

Since our order dependence on function space $\mathcal{F}$ is $\log |\mathcal{F}^*|$, it is shown in Table 1 that we can improve the order dependence from $\sqrt{|\Pi|}$ to $\sqrt{\ln |\Pi|}$, compared with existing methods.

Q: Question about numerical setup and baselines

A: The numerical setup is explicitly described in the main text, but we provides its details in Appendix A.6. For the first experiment, the values of distributions are randomly generated to provide a general setting. In the second experiment, some values are specifically chosen to demonstrate a significant improvement. This is because in certain cases where there is limited information about the distribution, the improvement achieved by the proposed algorithm may be negligible.

It is important to note that our method does not worsen performance with transferred knowledge. The numerical section of the paper demonstrates that naively transferring knowledge can lead to worse performance for classical algorithms. However, our proposed method does not suffer from negative transfer problems.

Q: In page 3 the authors say, "expert agent can observe the contextual variable in U,W". But also say in Figure 1 caption that "U is the unobserved context". Then why can any expert agent view this?

A: U is unobserved to the learner but may be observed by the expert in certain cases. Actually, how the learner obtain the required information is not the key factor of our paper.

Q: Page 4 para 2, what is "skewness from F(u)"?

A: It means P(U=0) differs a lot in P(U=1).

Q: In equation 1, can you specify what sets the sup and inf are over?

A: sup/inf is taken with respect to all compatible causal models, equivalently, all the joint distributions which satisfy the observations.

Q: Minor Suggestions/Typos

A: We follow your suggestions and modify our paper accordingly.

[1] Transfer learning in multi-armed bandit: a causal approach [2] Leaning without knowing: unobserved context in continuous transfer reinforcement learning

Q: The regret definition is written in terms of W only (not U). At each time slot, do you compete with a policy that has access to the true function and both realizations of W, U, or do you compete against a policy that has access to $f^*$, W, and take the expectation over U?

A: Since the learner cannot observe $U$, we compete against a policy that has access to $f^*$, W, and takes the expectation over U. The realizability assumption only needs to hold in the sense of taking expectation with respect to $U$.

Q: What is h(a) in Table (1)?

A: h(a) is the causal upper bound solved by the optimization problem (1). Please refer to the MAB part in section 3.1 for more details.

Q: What is sup/inf in equation (1)? Is it either inf or sup, and both will work? Do you mean that one will give an upper bound and the other a lower bound? This should be clearly stated. In the same paragraph you mention that (1) gives a bound on the causal effects. Causal effects between which variables? What is the mathematical formula for the causal effect to see that (1) gives an upper bound?

A: Equation (1) means we can get upper and lower bounds of its object by solving corresponding maximization and minimization problems, respectively. The object is the causal effect between action $A$ and reward $Y$ and both its upper and lower bounds are needed in the transfer learning algorithms. Theorem A.1 in Appendix shows the mathematical expression of the object and in the last sentence on page 4, we show the expression of the object in the discrete setting.

Q: If the algorithms are applied in the famous case of contextual linear bandits, what would be the resulting regret in that case?

A: We have provided the implementation of infinite function spaces in section A.5. It is worth noting that our algorithm and theorems can be easily extended to handle infinite $\mathcal{F}$ using standard learning-theoretic tools such as metric entropy. Let's assume $\mathcal{F}$ is equipped with a maximum norm $||\cdot||$. We can consider an $\epsilon$-covering $\mathcal{F}^*_{\epsilon}$ of $\mathcal{F}^*$ under the maximum norm. Since $|\mathcal{F}^*_{\epsilon}|$ is finite, we can directly replace $\mathcal{F}^*$ with $\mathcal{F}^*_{\epsilon}$ without changing any algorithmic procedures. Thanks to the property of $\epsilon$-covering, there exists a function $f_{\epsilon}^*\in \mathcal{F}^{\epsilon}$ such that $|| f_{\epsilon}^* - f^* || \leq \epsilon$. Hence, the regret can be bounded by the expression:

$$Reg(T) \leq 8 \sqrt{ \mathbb{E}_W[ \mathcal{A}(W) ] T \log (2\delta^{-1} |\mathcal{F}^*\_{\epsilon}| \log T ) } + \epsilon T.$$

By replacing the dependence on $\log |\mathcal{F}^*|$ in the algorithm's parameters with $\log|\mathcal{F}^*_{\epsilon}|$ and setting $\epsilon=\frac{1}{T}$, we obtain a similar result, up to an additive constant of 1.

In the context of linear spaces, the quantity $N(\mathcal{F}^*,||\cdot||,\epsilon)$, which represents the covering number, scales with $\sqrt{\log N(\mathcal{F}^,||\cdot|| ,\epsilon)}$. For linear spaces, such a quantity is of order $O(d\log(\frac{1}{\epsilon}))$. Hence, the improvement of regret order will be $N(\mathcal{F},||\cdot||,\epsilon) - N(\mathcal{F}^*,||\cdot||,\epsilon)$ in terms of function spaces.

It is important to note that $N(\mathcal{F}^*,||\cdot||,\epsilon) \leq N(\mathcal{F},||\cdot||,\epsilon)$ since $\mathcal{F}^* \subset \mathcal{F}$. The covering number clearly demonstrates how extra causal bounds help improve the algorithm's performance by shrinking the search space. The transfer learning algorithm only needs to search within a spherical shell with a thickness of at most $M-m$, where $m = \inf_{w,a} l(w,a)$ and $M=\sup_{w,a} h(w,a)$. The bounds chip away the surface of the unit sphere and scoop out the concentric sphere of radius $m$.

Q: The works in [1,2,3] consider contextual linear bandits with known context distribution without observing the realization. Even though the setup is more limited, I believe the authors need to provide a comparison when the results of the paper are limited to the setups of [1,2,3].

A: Thank you for your suggestion. We have added the mentioned papers to the related work section. Please refer to the updated version of our paper for more details.