Position-based Multiple-play Bandit Problem with Unknown Position Bias
Motivated by online advertising, we study a multiple-play multi-armed bandit problem with position bias that involves several slots and the latter slots yield fewer rewards. We characterize the hardness of the problem by deriving an asymptotic regret bound. We propose the Permutation Minimum Empirical Divergence (PMED) algorithm and derive its asymptotically optimal regret bound. Because of the uncertainty of the position bias, the optimal algorithm for such a problem requires non-convex optimizations that are different from usual partial monitoring and semi-bandit problems. We propose a cutting-plane method and related bi-convex relaxation for these optimizations by using auxiliary variables.
#Summary
This submission studies a multi-armed bandit problem, PBMU.
In this problem, there are L slots (to place ads) and K possible ads.
At each round, the player need to choose L from the K possible ads and place them into the L slots.
The reward of placing the i-th ad into the l-th slot is i.i.d. drawn from a Bernoulli distribution Ber(\theta_i \kappa_l), where \theta_i is the (unknown) quality of the i-th ad and \kappa_l is the (also unknown) position bias of the l-th slot.
The authors derived a regret lower bound and proposed two algorithms for PBMU. 
The second algorithm has a matching regret bound. 
The authors also discussed how to solve the related optimization problems appeared in the algorithms.
The authors give a complete characterization of the hardness of PMMAB in this paper. Their main contributions are:
1.A regret lower bound， which states that the expected regret of a strongly consistent algorithm for PMMAB is lower bounded by ClogT-o(log T). Where C is a parameter determined by every arm's mean profile and slot's position bias.
2.An algorithm for PMMAB. The authors called it Permutation Minimum Empirical Divergence(PMED) which can be compared with the Deterministic Minimum Empirical Divergence (DMED) algorithm for SMAB (see Honda and Takemura COLT2010).  They give an asymptotically upper bound of a modification of PMED  which is Clog T + o(log T).
From the technical point, I think the regret lower bound in this paper is a standard, which follows some techniques from Honda and Takemura COLT2010. In their upper bound analysis, the authors solve some new difficulties. In PMED algorithm, they compute Maximum Likelihood Estimator and use it to compute a K times K matrix which optimizes a corresponding optimization problem in the lower bound analysis. The authors then convert the matrix into a convex combination of permutation matrix (due to  Birkhoff–von Neumann Theorem). Though this idea is natural, the analysis is not straightforward. The authors analyze a modification of PMED in which they add additional terms to modify the optimization problems. They obtain a corresponding upper bound for this modified algorithm.
Experimental results are attached. 
#Treatment of related work
In the introduction part, the authors introduced some other related models and compared them with their new model.
They also gave convincing reasons why this new model deserves study.
To the best of my knowledge, their model is novel. 
However, the author did not make much effort in comparing their techniques with previous (closely related) results.
This made it difficult to evaluate the technical strength of their results.
#Presentation
The presentation of the paper still needs some work.
In Section 3, the authors defined a set \mathcal{Q}. 
However, it is dubious why they need to define this quality when deriving the regret lower bound (the definition of this quality is not furthered used in Section 3 and related parts in the appendix).  
On the other hand, the authors did use several properties of this quantity in Section 4 (to run Algorithm 2).
Thus, I advise the authors to place the definition of \mathcal{Q} into Section 4 in order to eliminate unnecessary confusion and change the claim of the lower bound correspondingly. 
Line 16-20 of Algorithm 1 (PMED and PMED-Hinge) is difficult to follow. 
To my understand, \hat{N}_{i, l} is the number of necessary drawings for the pair (i, l).
The algorithm then decomposes the matrix \hat{N} into a linear combination of permutation matrices and pull the arms according to the permutation matrices and the coefficients. 
When will c_v^{aff} be smaller than c_v^{req}? 
Shouldn't we pull (v_1, v_2, \ldots, v_L) for c_v^{req} times (instead of once)? 
Should c_v^{req} be rounded up to an integer?
There are some other typos/minor issues. See the list below.
1. Line 57-58: Non-convex optimization appears in your algorithm does not necessarily mean that PBMU intrinsically requires non-convex optimization. 
2. Line 63-65: Define K, or remove some details. 
3. Line 86-87: at round t -> of the first t rounds.
4. Line 102-105: According to the definition, (1), (2), \ldots, (L) is a permutation of {1, 2, 3, \ldots, L}, which is not what you want.
5. Line 115-117: The fact that d_{KL} is non-convex does not necessarily make PBMU intrinsically difficult.
6. Line 118, the definition of \mathcal{Q}: What do you mean by \sum (q_{i, l} = q_{i + 1, l})?
7. Line 122: (1) is not am inequality. Do you want to refer to the Inequality in Lemma 1? "the drawing each pair (i, l)", remove "the".
8. Line 124-127: Please elaborate on the reason why the constraint \theta_i?\kappa_i?= \theta_i \kappa_i is necessary. The argument given here is not easy to follow.
9. Line 138: is based on -> is closed related to
10. Line 141: what do you mean by "clarify"?
11. Algorithm 1, Line 12: Explicitly define \hat{1}(t), \ldots, \hat{L}(t). Currently it is only implicitly defined in Line 160.
12. Algorithm 1, Line 14: "where e_v for each v is a permutation matrix" -> "where for each v, e_v is a permutation matrix".
13. Line 172-174: Explicitly define the naive greedy algorithm.
14. Line 343: native->naive.
15. Algorithm 1, Line 17: \max_{c \ge 0} ... \ge 0 -> \max_{c \ge 0} s.t. ... \ge 0.
-------------------
The rebuttal addressed most of my major questions.
Score changed to 7.