- Rating
- 4(+1)
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies how to compare multiple adaptive policies while reducing the number of expensive reward observations. The paper proposes Tree-Coupled A/B Testing, that organizes candidate policies into a given tree and shares observations between connected policies according to the tree structure. The key insight is that candidate policies often behave similarly, that they can share an observed outcome whenever their context–action distributions can be coupled. The paper establishes theoretical guarantees for the expected reward-query cost and the expected proposal overhead.
Critical strengths
The topic studied is useful and of importance to applications.
The algorithm is elegent itself.
The authors made an effort to answer potential questions that reviewers may raise. This draft is quite complete from my viewpoint.
This draft is also clearly written.
Critical weaknesses
I found a potential flaw in the design of this current algorithm, and I wish the authors can TRY to improve the design during the discussion phase.
-
The algorithm itself adds latency to the A/B test, compared with standard A/B tests, policies are run independently and simultaneously. This may deserves few sentences of discussion.
-
The expectation of Proposal Overhead is discussed but it does not control the worst-case number of proposals or the tail latency. We know Proposal Overhead is related to \delta. Let \delta be very small but strictly larger than zero, once enter the residual branch (even though the chance is small but still no zero), the algorithm can get stuck at this step.
-
The optimal fixed tree, and regret bound both suggest to use edges with small \delta, but the chances of getting stuck at residual branch may increase. There seems to be a trade-off between reward-query complexity and tail latency under the current desgin. Perhaps the authors could propose alternatives to the current residual branch, such as truncation, early stopping with estimation, or sampling contexts according to policy disagreement.
Questions for authors
See above.
3 comments
I’m very happy with the relaxed coupling sampler. The complete pipeline now accommodates a broad range of situations, and I’m willing to raise my score. Just one minor comment: the text in Figure 5 is too small to read.
We sincerely appreciate the reviewer's positive feedback, and we will make Figure 5 into 2 row (MST & STAR) by 3 col for better visualization in the next revision.
We sincerely appreciate the reviewer's positive feedback and thoughtful concerns and questions raised in this review. We have uploaded a revised PDF submission (revised parts in blue) and hope to answer the questions below:
We agree that this deserves a few sentences of discussion. In the revision, we add a discussion on the sampling overhead and its delay in Section 4 and a potential remedy, and then we refer to Appendix B for more details. In Appendix B, we include a remark on asynchronous implementation (which is important to unblock the policies on the tree) at the end of page 16. In Figure 5, we plot the distribution of the run times of our algorithms and compare against the standard A/B; our original TCAB (with the asynchronous implementation) is very close to the standard A/B test up to machine measurement errors and hardware variance.
This is an excellent and important point! In the revision, we add a detailed discussion and analysis about the proposal overhead in Section 4, below Proposition 4.1. In particular, we give explicit dependency for the overhead variance on the policy TV δij,t. This rate implies that the variance scales inversely in the TV (as the policies saturate toward the same set of optimal actions); but the expected overhead remains 1. Then we add an impossibility result to illustrate that this variance is somewhat binding for maximal-coupling sampler under the single-exposure condition (that each context arrival can only be used for one reward query, which matches many real-world applications).
Finally, to remedy for this variance, we provide analysis and extensive experiments on an alternative Relaxed-coupling sampler. The relaxed sampler takes the insight from the impossibility result above and achieves zero variance by forfeiting maximality: it tries to use a new sample for the child first, whereas the maximal sampler tries to inherit from the parent first and only uses a new sample afterwards. More details and experiments are provided in Appendix B (Figure 4,5).
In a word, the alternative successfully controls the tail of the overhead count at the expenses of less reward-query-saving, but our original sampler was already good enough in terms of cumulative run time and estimation errors, because (1) for nonadaptive policies, the TV is constant; (2) for adaptive policies, they do not saturate to be identical within our horizon. If they do saturate, we believe the propose alternative in Appendix B would be a balanced solution, with guaranteed bounded variance.
To control the tail when the TV is small, we propose the relaxed sampler above and also include the truncation and a slack heuristic in Appendix D. The experiments in Figure 4, 5, and 7 indicate clear Pareto curves for the trade-off for all three datasets we use, for each of the three alternatives respectively.
We did not test the reviewer’s proposal on sampling contexts according to the policy disagreement, because it would require us to sample from X∼δijd(X)PX(X) where d(X)=TV(πi(⋅∣X)∥πj(⋅∣X)) and δij=EX[d(X)] (please correct us if we misunderstood the proposed idea). Using rejection sample, even when we know d(X), we would require 1/δij context proposals from PX on average for such a sample from the new distribution, which does not fix the overhead issue.
We truly appreciate the reviewer’s feedback, observations, and thoughtful questions. We are more than happy to discuss any question or unclarity further.