Factored Bandits
We introduce the factored bandits model, which is a framework for learning with limited (bandit) feedback, where actions can be decomposed into a Cartesian product of atomic actions. Factored bandits incorporate rank-1 bandits as a special case, but significantly relax the assumptions on the form of the reward function. We provide an anytime algorithm for stochastic factored bandits and up to constants matching upper and lower regret bounds for the problem. Furthermore, we show how a slight modification enables the proposed algorithm to be applied to utilitybased dueling bandits. We obtain an improvement in the additive terms of the regret bound compared to state-of-the-art algorithms (the additive terms are dominating up to time horizons that are exponential in the number of arms).
The paper proposes to take a step back from several existing combinatorial bandit problems involving factored sets of actions (e.g. Rank-1 bandits). A meta algorithm based on sequential elimination is given and analyzed in two major settings: in general factored problems and in the dueling bandits setting.   TL;DR: The whole algorithmic structure is extremely hard to parse… The improvement over Rank-1 bandits is not clear at all, and I am not an expert in Dueling Bandits to fully judge the impact of TEM on the ``constant” term in the analysis.   Major comments:  1/ One recurrent inconsistency in the writing is that you define atomic arms at the beginning of section 2 and you barely use this vocabulary thereafter ! Arms and atomic arms are often called arms, especially in Definition 1 that actually defines gaps for atomic arms on each dimension.   1/ Algorithm description: For me, this is the main problem of this paper. The algorithm is extremely hard to parse for many reasons: many small inconsistencies (some are listed below) that do not help reading and a quite unclear description (l 130-137). Typically, I 134 : do you use comparisons between arms or atomic arms ? Algorithm 3 (function feedback) seems to do comparisons between atomic arms.  - Algorithm 1 (and 2) :      - M_s is not defined     - This encapsulation of every step of your algorithm is actually more confusing than helping: basically you’re pulling all remaining atomic arm of each factor on each round. This is quite similar to Rank1Elim as far as I understand, and rather natural, but it took me quite some time making sure it was not more complicated than that.  - Algorithm 3: If I understand well, you’re keeping track of all couples of atomic arms in each Module (so for each factor). That’s a quadratic memory complexity, typically of the order of LxK^2. Isn’t it an issue when K (number of atomic arm per factor) becomes large ? This is actually the interesting case of this type of structure I believe.      - In function feedback, the indexing of N^i_s is inconsistent (sometimes N^s_i).      - Using N_{i,j} and N^s_i for two different counters is quite confusing  2/ Link with Rank-1 bandits: TEA does not behave like rank1Elim but it could have been nice to explain better where is the improvement. Indeed, the rank-1 bandits is not a closed problem yet: there is still a gap between the lower bound of [Katariya et al.] and their algorithms (rank1Elim(KL)). If you think you are improving on this gap, it should be stated. If you are not, we would like you to tell us in which setting you are improving on the state of the art. I am really surprised by the empirical results. I see no reason why the rank1ElimKL would perform similarly as your policy, this is not discussed.   3/ Regret bound : It seems like your bound scales in 1/\Delta^2, which looks optimal but it is actually not. Typically, take the stochastic rank-1 bandits problem (which is a subclass of your setting). The deltas you defined are actually the smallest gaps while in [Katariya et al.] they consider the largest gaps (u_1v_1 - u_iv_1 = \Delta^U_i). They show a lower bound in 1/\Delta for such largest-gap definition. Their regret bound does not match their lower bound but it is still a bit tighter than yours as it scale as 1/(mean{u_1,…,u_K}) instead of 1/(min{u_1,…,u_K}).   Minor comments:  - l.22 Player The  - It’s just my personal opinion but I think this paper tries to cover too wide of a scope. I am not an expert in dueling bandit but I know quite well the combinatorial / factored bandits literature in general. I think both contributions you make would be clearer if split in two separate papers. That would give you some space to explain better the behavior of your algorithm and where the improvement comes from.   EDIT: Thank you for the detailed answers to my comments and remarks in the rebuttal. I raised my score a little bit because they were convincing :)