Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers the multi-task bandit setting with a contextual information related to the task. The setting is defined in a fully Bayesian way, pathing the way to a Thompson Sampling (TS) bandit algorithm to handle this setting. A worst-case regret bound with respect to the parameters of the task-generator is proven and experiments on synthetic data show that the proposed model has smaller regret than baselines independently of the entropy of the task with respect to the contextual information.

main_review: Having access to a contextual information regarding tasks, the proposed Bayesian model and the corresponding TS algorithm are strait-forward. However, the theoretical analysis and the experiments demonstrate the interest of the proposed approach with respect both to meta-learning approaches overlooking the contextual information, and to non-meta-learning approaches.

At first read, the presence of both $d$ and $K$ in the regret bound is surprising as a task is defined by its context and the unknown vector $\theta$ of dimension $d$. Obviously, this reasoning is wrong, as a task also depends on the randomness in its generation which may be expressed by a vector $\delta_i$ of size $K$ (see by example Equation (3)). This point could be stressed out in the paper.

Note that the contextual multi-task setting may be reduced to standard contextual setting using (i) the extended context $\Phi'(x_i, a) := (1_{i,a}^T, \phi(x_i,k)^T)^T$, where $1_{i,a}^T$ is a length $NK$ indicator vector taking value 1 at $((i-1)*N+a)$-th entry, and (ii) the extended parameter $\theta' = (\delta_1^T, \dots, \delta_N^T, \theta)$. Such reduction inflates the size of the contextual information, leads to badly conditioned context-vectors, and is somehow equivalent to considering the tasks as independent. However, I'm wondering how it would compare to the proposed approach in terms of regret.

## typos
* L230: I guess the parameter of the indicatrice function should be $i(l) = i(m)$  


limitations_and_societal_impact: Recommender systems are typical application of bandit algorithms. However, by recommending the preferred items to users, they tend to restrain the user to these preferences which may raise concerns regarding the corresponding societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
The paper studies the multi-task multi-armed bandits, where tasks are played sequentially and each task is governed by some unknown hidden parameter (metadata) which follows certain prior distribution.

1. The paper comes up with a Bayesian framework for the metadata-based multi-task multi-armed bandits. 
2. The paper designs Thompson sampling-type algorithm, called MTTS, and demonstrates its supremacy over other algorithms, by proving regret bounds for the common Bernoulli / Gaussian prior cases. 
3. The paper shows detailed experimental results to corroborate the effectiveness of the algorithm MTTS.
main_review: 
The paper proposes a new setting of multi-task bandits, and provides a rather complete answer to it by showing both theoretical and empirical results. The proofs are easy to read and easy to follow. The writing is very well. The paper also provides the codes for the experiments, which is appreciated. 


Assumption 1 is a little bit annoying to me. It is possible to remove it under other multi-task bandit setting [arXiv:2102.04132]. Since the setting in this paper is not like transfer learning (i.e. all tasks follow the same distribution), I wonder if it is possible to remove Assumption 1? The authors claim it is standard, but there are indeed some papers that does not require a counterpart of Assumption 1 (like [arXiv:2102.04132]). I think the authors should further justify it.

The paper seldom mentions the upper confidence bound (UCB) algorithms, which can definitely be used to solve this setting  (though it might get worse regret bound). I suggest the authors add a discussion about them. Also, the paper lacks a lower bound. Since the authors propose a novel notion of regret, the lower bound cannot be immediately seen, and thus I suggest the authors discuss about it.


limitations_and_societal_impact: 
### Limitations

Please refer to Main Review.

### Societal Impact

The paper focuses on general framework of a wide class of problems, so I do not see any potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a Bayesian hierarchical modelling framework to learn shared information across multiple multi-armed bandits. It extends both meta MAB that doesn't uses task specific metadata and linear bandit models that does not assume inter-task heterogeneity. It defines a new regret, called multi-task regret and provides theoretical analysis on the regret bound compared to other methods. Simulated experiments confirm the superior performance against other baselines when the model is well specified. It also shows robustness when under some model specification. Unfortunately, there are no real data experiments to show the performance in practice.
main_review: This paper is well written. It has a good motivation and a general introduction to the problem. It has sufficient discussions on related work. The general hierarchical Bayesian model framework is natural under the problem setting, and the inference algorithm is standard in the Bayesian literature. It discusses two concrete and simple problem instantiations under linear Gaussian and Beta-Bernoulli assumptions with more extensions in the appendix.

One of the main contribution is the regret analysis using the MTR. It shows the advantage of the proposed method when the model is well specified. It would actually be useful to comment in the scenario with model misspecification, in which case I guess it will reduces to the same bound as individual TS in Table 1 (or worse depending on the type of misspecification).

I am a bit disappointed about the lack of empirical evaluation on real problems.
Experiments in the main text shows the advantage of the proposed method when the data generation process is the same as the model prior. In my opinion, it merely serves as a sanity check that the Bayesian inference algorithm works as expected. The additional experiments in E.1 to show the robustness under misspecified reward structure is actually more interest and I would suggest move it to the main text. Nonetheless, I think it would make the paper much stronger if the authors could show it outperforms contextual bandit methods by modelling the additional inter-task heterogeneity in common problems studied in that literature.

As a minor comment, as many concepts and proving techniques are inspired by [6], it maybe be helpful to the reader by mentioning it in the related work section and explaining the difference from this work.
limitations_and_societal_impact: See my comments above about the lack of real data evaluation.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Authors provide a new solution of the problem of transfer learning across different bandit tasks. Specifically they assume policy to leverage external task-features describing task similarities. They focus on Bernoulli and Gaussian bandits as learning instances.
The theoretical findings have been tested on synthetic data.
main_review: Authors claimed to introduce two novel ingredients with respect to traditional works on meta-learning with bandit tasks. First they say to consider a more general setting thanks to the presence of metadata. Secondly, here task interactions are allowed to arrive in arbitrary order. Yet, they are not forced to arrive sequentially. 
To the best of my knowledge I am not aware of the usage of metadata to explain bandit task similarites. I found the idea interesting and novel. That beind said, I would not say that this is a more general framework as it does not incorporate all the task-similarities assumptions that have been investigated in the literature. Indeed, I would consider it an alternative framework.

In the state of the art about meta-learning with bandit tasks I would incorporate the following recent works:
- Simchowitz et al.. Bayesian decision-making under misspecified priors with applications to meta-learning. https://arxiv.org/abs/2107.01509
- L Cella, M Pontil. Multi-Task and Meta-Learning with Sparse Linear Bandits. UAI 2021.
- Moradipari et al.. Parameter and Feature Selection in Stochastic Linear Bandits. https://arxiv.org/abs/2106.05378

As far as the MTTS regret bound is concerned, I wonder if there is a lower bound result in the literature to better understand the quality of the proposed solution. For instance, it seems to me that setting $d=N$ the MTTS regret bound would be of order N\sqrt{TK} which is the same of individual-TS. Am I wrong?

Finally, I wonder if there are clear limitations in running experiments over real data.
I found the paper clear and well written. 
limitations_and_societal_impact: See above.
review_title: null

Meta-review: Thank you to the authors and the reviewers for their contributions to the conference! This paper proposes a new bandit formulation with metadata, which they solve using a Bayesian hierarchical framework. They then propose a meta Thompson sampling algorithm and show regret guarantees using prior alignment. The reviewers uniformly appreciated the paper, so my recommendation is to accept the paper. A few concerns were raised regarding the lack of a lower bound and experiments on real data. For the former, I would suggest that the authors add some discussion on why this is challenging to do. For the latter, please add the new MovieLens experiments. Additional clarifications based on the rebuttal response are of course welcome as well.
Decision: Accept (Poster)