Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper focus on the contextual multi-armed bandit with communication constraints. It provides some discussions and numerical results.
main_review: Major comments:
1. Most importantly, there is no complete theoretical analysis (e.g. the upper bound/lower bound on the regret of the algorithm.)
1. The algorithm should be explicitly written out with its pseudocode. 
1. By the end of Section 1, it states that the communication is one-way from the decision-maker towards to controller. However, as the decision-maker can observe the realization history, it is a bit strange not to consider that as communication. Besides, how the goal of this work is different from existing papers is confusing.
2. The problem setup is not clear: is the state i.i.d. sampled from the distribution $P_S$ or not?
3. The relation between the constraint quantities $(\rho,R)$ and the discussions in Section 3 is not clear.
4. The constraints seem to be placed in the posterior probabilities involved in the TS algorithms. What if we consider UCB-class algorithms?
5. The definitions of $D_\alpha$ and reverse KL divergence $D_{KL}$ is missing. Usually, we denote the original KL divergence by $D_{KL}$.
6. In Section 3.3, it states ''If $S$ and $A$ are independent...'', I don't think it's a common assumption in contextual bandits.

Minor comment:
1. The citation style is not so good: for instance, it should be "In Phan et al. (2019) ..." instead of "In (Phan et al., 2019)..."
 
summary_of_the_review: Overall, this works lacks complete analysis, which is not usual in a bandit paper, and the relation between the background and the discussions is not clear. Hence, the contribution of the work is not clear. The detailed comments are as above.



================================
I appreciate the efforts of authors to add on theoretical results during the rebuttal period, and decide to raise the ranking from 3 to 5.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies a contextual bandit problem where the decision-maker must communicate its intended actions (given observations of the contexts) to a controller through a constrained communication channel. The original part of the paper is that the “bandit algorithm” must encode its actions into a compressed version that then serves to the controller. 


main_review: Strength:
* The paper proposes an original problem that combines the challenges of bandit modelling and information constrained communication problems. I particularly like that this problem has achievability constraints and elegantly makes use of information theory to solve a contextual bandit problem. 
* The problem is motivated by a real real-world task

Weaknesses:
* There are some inconsistencies and imprecisions in the writing that make it hard to follow. Section 2 defines a lot of quantities and regrets and gains, etc. that are not really analyzed afterwards, or I missed it: what do you mean to say about G and \rho and R ? Also, how is R defined exactly (the “communication rate”), is it some ratio of N and B or something ? 
* The paper does not have regret bounds, I guess it was out of your scope, but can you comment on that ? You briefly talk about problems that are “achievable” but then we don’t really know what kind of regret we could expect it seems. 
* Algorithm needs to be clearly outlined: You give very detailed explanations on your algorithms but for the sake of readability we need a pseudo-code. At the moment, I am struggling mending the pieces between all the different optimization procedures to solve and what needs to be done when and by whom. Can you please outline a pseudo-code and upload it so I can check that my understanding corresponds to what you are doing ? 
* Minor: Lower-level literature review: I feel like the background is given in the related work but I am surprised you were not able to connect your work better with the existing literature on contextual bandit. Perhaps contextual bandits with context uncertainties, or Partially Observable MDPs ? 


Minor: 
* section 3.3 : “posterior \pi convergences” -> “converges”
summary_of_the_review: TL;DR: The paper is a bit hard to follow for the non-expert in compression that I am (arguably like many of the bandit community) so I am not sure of my evaluation and I hope to be able to clarify it during the rebuttal / discussion phase. I cannot make a strict recommendation for now but I will update my score after the rebuttal phase.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies a CMAB problem where the actions for multiple agents are sent from the decision-maker over a rate-limited communication channel. The authors developed information-theoretic performance bound for Thompson sampling based policies, which reduce the problem to transmitting conditional probability distributions over a communication channel. A practical coding method was also developed. Numerical experiments were carried out to validate the proposed design.
main_review: The paper is sound and of certain interest. One knock of this paper is that the results were largely adapted from known information-theoretic results: the optimal bound was derived based on Kramer&Savari; TS for RC-CMAB was based on the double minimization problem in Cover&Thomas as well as the well-known Blahut-Arimoto algorithm; the practical coding scheme was based on the well-known Lloyd algorithm for clustering. Putting these pieces together is not trivial, I must admit. However, the overall novelty is thus limited. 

Another question is about the problem setting. The assumption that each agent's state $s_{t,i}$ is observed by the decision-maker, but not the agent itself, is very strange. Since the state is agent-dependent, agent $i$ generally already has access to the state $s_{t,i}$, which then makes this problem a decentralized MP-MAB problem (with contextual MAB). The authors should clarify why they make the assumption that only the central decision-maker can observe all agents' states, but not the agents themselves. In fact, the practical coding scheme is about sending the state (via a compact state representation) to the corresponding agent. This may not be necessary to begin with in practice. Also, with the aforementioned argument, the controller "decoder" function $g_t^{(N)}$ should have the joint states of all agents as an input. This would enhance the decoder design.  
summary_of_the_review: A solid work overall, but with some questions on the novelty and assumptions. Will be open to author responses and adjust the score accordingly. 

======

Post-rebuttal update: I thank the authors for addressing my concerns on the availability of state information to the decision-maker versus the agent. I hope that the authors add these details, especially the factory example, to the paper. My other reviews remain the same.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work studies a rate-constrained contextual multi arm bandit (RC-CMAB) problem: the decision maker has to make action decisions for multiple parallel (independent and identical) CMAB problems (i.e. agents), but can only communicate the actions for each CMAB problem to a controller through a rate-constrained communication channel, from which the controller receives and decodes the actions of the decision maker, and applies such decoded decisions to each CMAB.  The paper first formulates the problem as a policy compression problem under an information theoretic framework, and then characterizes the optimal compression scheme for infinite agents. Next, the paper presents a practical coding scheme to communicate actions to finite agents under rate constraints, and finally benchmarks its performance against the compression scheme in the asymptotic regime. 

main_review: This is a well-written paper, and in particular I think the paper does a good job in the following aspects: 1. The RC-CMAB problem of interest is well-motivated in the introduction (e.g. with the personalized ad placement example); 2. The explanations for modelling the problem as a policy compression problem are clearly conveyed, and the relevant technical discussions on the distortion function as well as the clustering coding scheme (over states) are concise and easy to follow; 3. The analyses in the numerical result section are comprehensive and thorough, and I find the numerical illustrations related to the asymptotic rates to convey the considered policies (Fig. 4) quite insightful and interesting. Furthermore, I particularly liked the fact that the ideas behind the clustering coding scheme are simple and intuitive (since the idea of compressing states in clusters and transmitting a policy for each cluster is straightforward and natural), which is a huge plus from both a theory and practical perspective. 

In terms of weaknesses, my main concern is that the paper lacks theoretical performance guarantees for the clustering coding scheme. I believe including a characterization of how regret depends on the number of states, the rate constraint, number of actions, etc. would provide us with a more in depth understanding of the performances of the clustering scheme in various scenarios. On a related note, I am specifically interested in how the proposed clustering schemes’ performance decays as the total number of states grows, because intuitively, more states would induce larger clusters and hence larger distortion in the policy defined over the compressed states (compared to the target policy). I am bringing this up because the paper uses personalized ad placements as a motivating example, and in such markets, typically the content owner’s valuation for a user view (i.e. impression) or conversion serves as the ``context’’ (or state), and may take a wide range of values. If providing theoretical analyses for the dependence on the state space is infeasible, at least having some experiments that address related issues would be beneficial.

summary_of_the_review: The paper is well-written and well motivated. The technical discussions are concise and clear. The analyses for numerical results are comprehensive and thorough.

Weaknesses: the paper would be much stronger if it includes theoretical guarantees for the clustering scheme, and also results/discussions/experiments on how the cluster scheme’s performance decays with the number of states.
review_title: null

Meta-review: Summary: This paper studies a contextual bandit problem where the decision-maker must communicate its intended actions (given observations of the contexts) to a controller through a constrained communication channel. The original part of the paper is that the “bandit algorithm” must encode its actions into a compressed version that then serves to the controller. In that sense, the controller must cluster the problems for the decision maker to simplify communication.

Discussion: Most reviewers appreciated that the paper is well-written and proposes an original problem. The main commonly issue is that of a lack of regret analysis. The authors included an additional theoretical result giving a necessary condition for sublinear regret but the committee would still appreciate a more in-depth study of the performance of the proposed algorithm, given that the condition is satisfied. One possible direction is to connect this work with the literature on "Clustering of bandits" (CoB) as raised by reviewer mXFx. The authors claim that this paper is only mildly related but the committee would kindly insist that linear rewards are just a generalization of multi-armed bandits, that there is also a finite state space in CoB (finite population) and it seems possible to reduce the proposed problem to CoB under some assumptions. In that regards, it would be important that a more thorough review and comparison of that line of work is done in the main paper (note also "Latent Bandits" and related papers), even though we agree that the proposed approach is different and we appreciate its originality.

Overall, the paper is borderline, and the committee did not reach a consensus. 

Decision: Reject
Decision: Reject