Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: The paper addresses the multi-armed bandit problem where post-action contexts are observed and may or may not be a d-separator. When there is no d-separator, many algorithms including the UCB algorithm achieve the optimal regret. On the other hand when there is information on which variable is a d-separator, UCB style algorithms (such as C-UCB) have been proposed that achieve a regret bound that depends on the cardinality of the d-separator variable instead of the number of actions. 
However, there is no former algorithm that addresses the case where the learner does not know whether a post-action variable is a d-separator or not. A safe way would be to apply the original UCB algorithm, but this will achieve suboptimal regret in case there actually is a d-separator. On the other hand, authors prove that using the C-UCB algorithm can result in linear regret in case there is no d-separator. 
An adaptive algorithm is required to identify the d-separator variables and decide whether to implement original UCB or C-UCB for action selection. Authors propose a new algorithm based on consecutive hypothesis tests that identify whether a variable is a d-separator. The algorithm achieves optimal regret when there actually is a d-separator, and sublinear (O(T^{3/4})) regret when there is no d-separator. Authors also prove that their bound cannot be shaved off by more than T^{1/4} order.

strengths_and_weaknesses: Strength: The authors define the conditional benign property under which the proposed algorithm achieves optimal regret. This property is a weaker assumption than previous works. Also, the proposed algorithm does not require to know the exact marginal distribution of the d-separator variables. The optimal regret is achieved with approximate distributions as well.

questions: Were the experiments performed repetively, or was it just one run?

limitations: I did not find any discussion on the societal impact.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a novel algorithm for causal bandits that achieves “best of both worlds”: comparable performance to the benchmark C-UCB algorithm in conditionally benign environment while achieving a much better performance in the worst-case environment. In the causal bandit setting, the player observes some other post-action contexts after they play some action, rather than observing all contexts before they play an action. Under this setting, they introduce the conditional benign property which is closely tied with d-separability. They show that the benchmark C-UCB algorithm suffers linear regret when the environment is not conditionally benign, and it is impossible to achieve worst-case optimal regret and optimal regret in the conditional benign environment simultaneously. Then, they introduce the notion of Pareto optimality based on the Pareto frontier and show that their new algorithm, HAC-UCB, is Pareto optimal. 

strengths_and_weaknesses: In terms of originality, the paper provides several interesting contributons. Firstly, they introduce the idea of a "post-action" context. Secondly, they provide a novel algorithm, HACUCB to solve the post-action context problem with a specific application of causal bandits when observing a d-seperator of d-separators. Perhaps most interestingly is the new impossibility results for previous algorithms (C-UCB) which achieve optimality in the assumption of a conditional benign environment, and provide interesting lower bounds. 

Overall the paper is well written and easy to understand. The impossibility results are very surprising, including those about adaptive minimax adaptivity.  As far as the experiments, they are not extensive, however they demonstrate the advantage of HACUCB over CUCB in benign settings effectively. 

My only comment is that although this paper is a direct extension to the existing literature Lu et al, it needs more justification to show the significance. For example, I would love to see some real applications of their algorithm.

Overall, I would love to accept the paper based on the amount of work and technical contributions. I think this paper has interesting ideas and the paper is well written. 

questions: None in addition to the above.
limitations: The author could discuss more on the limitations of their proposed algorithm, e.g. in which situation does it work well, and in which situation does it work poorly, in theory and in simulation?
review_title: null

final_score: 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.
review_content: summary: The authors study adaptivity in the setting of causal bandits. They consider a bandit setting where after an action a is taken, a post-action context Z_a is observed. They propose a new property, a conditionally benign bandit environment that subsumes Z being a d-separator and other assumptions previously studied in the literature. They develop an algorithm that is adaptive to whether the bandit environment is conditionally benign. This allows the algorithm to obtain a regret bound matching C-UCB, a SOTA algorithm for causal bandits, when the bandit environment is conditionally benign and that has a sublinear regret otherwise. The authors also show that it is impossible to be minimax optimal at once for environments satisfying the conditionally benign property and violating the conditionally benign property. 
strengths_and_weaknesses: Strengths:

The paper initiates the study of adaptivity in causal bandits, a very important problem. 

The authors give a set of strong and novel results. In particular, their impossibility result on strict adaptivity is interesting.

The proposed notion of conditionally benign environments seems like a nice and simple generalization of prior assumptions in the literature. 

The authors give a very strong empirical validation of the theory. It is nice to see that existing algorithms do not adapt to the distinct settings, while the proposed algorithm does. 

Weaknesses:

The authors do not seem to give real-world examples of the bandit protocol, which may make it seem more like a mathematically convenient setting to study adaptivity in causal bandits. In what applications, would a post-action context be observed?

While the problem itself it important and nice theoretical progress has been made, it is unclear to me that the proposed algorithm would lead to practical gains on real-world problems. In the particular, the initial burn-in time of playing each arm $O(\sqrt{T}/|A|)$ times seems costly and the hypothesis test seems potentially loose. It would be nice to see the empirical performance of the algorithm on real-world problems or larger-scale simulations.

The algorithm uses fairly standard ideas in the literature. It uses a hypothesis test to determine whether the environment is conditionally benign. Therefore, the algorithmic novelty seems limited.

As the authors indicate, the rate $T^{3/4}$ may be suboptimal. I'm curious as to whether this result is tight for the algorithm and whether there may be an algorithm with an improved rate. 
questions: What are real-world examples of the protocol?

Do the authors believe the algorithm could make improvements on real-world problems? It would be nice to see the empirical performance of the algorithm on real-world problems or larger-scale simulations.
limitations: Yes.
review_title: null

final_score: 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.
review_content: summary: This paper studies the problem of online learning in causal bandits, i.e., multi-armed bandit models compatible with a certain set of structural constraints encoded in a causal graph. Existing methods assume that the correct causal graph is provided. This paper studies an important generalization of this problem setting where the causal graph could be misspecified. The authors propose an algorithm that could achieve a sub-linear regret in the most general cases where the graph is incorrect. It is also able to exploit the existence of independence constraints to improve the learning performance when the graph is accurate. The authors further provide the worst-case analysis showing that any online learning algorithm is unable to achieve the optimal regret bound with and without the causal graph simultaneously when the graph misspecification is possible.
strengths_and_weaknesses: This paper is clearly written and well-organized. It attempts to address a challenging problem: online learning combined with hypothesis testing on pre-specified domain knowledge, which could possibly be misspecified. Existing methods in the causal bandit literature mostly assume the correct causal graph is provided. Therefore, I think this paper could have an impact on both reinforcement learning and causal inference. The proposed algorithm, HAC-UCB, appears sound and demonstrates some desirable properties. That is, the algorithm is able to achieve a sub-linear regret in the most general bandit model while improving the regret bound by exploiting underlying independence constraints when assumptions in the graph are accurate, represented in the form of a set of d-separators. 

While it is sub-linear, the regret bound of HAC-UCB is still worst than UCB in the general case. To understand this observation, the authors also provide the worst-case analysis of this learning setting. The result is interesting. It suggests that there exists no online learning algorithm that could achieve the optimal regret bound with and without knowing the correct causal graph simultaneously.  This suggests that the performance gap between HAC-UCB and UCB might be expected.

As for the weakness, I think the lower bound result in Theorem 6.2 does not suggest that the regret of HAC-UCB could not be improved. Theorem 6.2 states that one could not design an online algorithm achieving regret $\mathcal{O}(\sqrt{|A|T})$ (without graph) and $\mathcal{O}(\sqrt{|Z|T})$ (with graph) simultaneously. However, this does not mean that it is infeasible to design a robust online algorithm capable of graph misspecification while achieving the same regret as UCB, which is $\mathcal{O}(\sqrt{|A|T\log(T)})$. The main reason is that the regret bound of UCB is not tight, containing a log factor $log(T)$. Therefore, the authors comment, "In Theorem 6.2, we will show that, up to logarithmic factors, it is impossible to improve the $T^{3/4}$ n this bound to $\sqrt{T}$ while still achieving the improved regret on conditionally benign environments", is somewhat misleading, and should be removed.
questions: In Definition 6.1, the constant C in Eqs 6.1 and 6.2 appear to be the same. While in Theorem 6.2, the negative result utilizes two different constraints C and C'. Is this a typo? Otherwise, Theorem 6.2 does not seem to show that "it is impossible to be adaptively minimax optimal with respect to the conditionally benign property."
limitations: The authors have clearly stated the assumptions behind the proposed methods. This work is mainly theoretical, and its long-term societal impact is unclear to see.
review_title: null

Meta-review: metareview: This paper exploits the causal structure in the multi-armed bandits setting and gives a set of novel and strong results, including (1) the conditional benign property -- a nice and simple generalization of prior assumptions; (2) an impossibility result for the previous algorithm C-UCB; and (3) a new algorithm gives sublinear regret in any cases and optimal regret when there actually is a d-separator.  The paper is well-organized and nicely written.  The reviewers are unanimously positive about this paper.
confidence: Certain
Decision: Accept