No-Regret and Incentive-Compatible Combinatorial Online Prediction

• The algorithm description is not very clear to me. Several points are as follows:

  • What does $p$ mean in the notation $\mathbb{H}_r(p)$? What is the choice of $p$ in the algorithm?
  • What is the exact sampling scheme for $S_t$? While in Assumption 4.1, the authors claim certain properties for EXT, I do not understand the sampling scheme here. In addition, more examples of such EXT should be included to show that Algorithm 1 is effectively runnable.
  • No code is provided in the supplementary material.

• From the theoretical result side, one main disadvantage is the bad 1/2-approximation ratio of the regret, since 1-1/e is typical for monotone submodular maximization problem. Moreover, even in the linear reward case, the obtained results in Section 6 are 1/2-approximated regret, which is not ideal.

• As for the regret rate, while $T^{3/4}$ is the same as the BCO algorithm using one-point gradient estimation from [Flaxman et al., 2005],

  • there are more advanced algorithms for BCO achieving \sqrt{T} type regret (e.g. [Fokkema et al.,2024, Online Newton Method for Bandit Convex Optimisation]). I wonder whether these algorithms are applicable to this case?
  • for the linear case, the T^{3/4} rate may not be ideal. Also, I wonder why the first term in the bound in Theorem 6.1 is T^{2/3}? From the analysis, it seems to be still T^{3/4}.

• There are some writing typos:

  • Line 400: unfinished sentence.
  • Algorithm 2 title: not full-bandit feedback.
  • Line 477: T^{(3/4)} should be $O(T^{3/4}).

1. [Results] The approximation factor is only $1/2$, which is usually far from the offline optimal one $1-c_f/e$. Even using the metric of $1/2$-regret, the algorithms are still only able to secure a $\mathcal O(T^{3/4})$ bound, which is much worse than the previous $\mathcal O(\sqrt T)$ ones.
2. [Techniques] Technically, the main innovation seems to be replacing the ordinary gradient descent (available in full-information setups, but can make the new action infeasible due to importance sampling under bandit feedback) with an OMD with $1/2$-Tsallis entropy regularizer. From the main text, it is hard to understand why it is hard to develop this technique here.
3. [Writing] The writing is often unclear. For example, the setup part is written in a pretty confusing way -- the word "each expert incurs a loss" sounds like the loss is the metric of experts instead of the learner; but it actually turns out that it is used to construct the submodular utility f(S,r) and experts are only interested in maximizing the probability of being selected. Also, what's the intuitive explanation of proper losses? Does it imply things more than "if your belief is correct, then being honest minimizes the loss"? I feel it'd be good to add some informal statements around such definitions.
4. [Related Work] The comparison with the literature is not well-organized and makes it hard to evaluate the role of this paper in the literature. For example, the comparison between this work and the closest one (Sadeghi & Fazel, 2024) was divided into Lines 104 -- 110 and Lines 150 -- 156, where the first part only mentioned loss functions & feedback models and the second one only says approximation factors & incentive-compatibility. I suggest the authors make a table to summarize the many previous works together with this paper, including setups (standard online learning or combinatorial one), feedback models, approximation factors, and when they're incentive-compatible, for a fair comparison with previous works.

Therefore, because of these issues, I do not feel it is possible to fully evaluate the real novelty of the contributions of the current version of this paper, hence my initial rating.

While this work definitely makes progress towards the combinatorial setting, their seems to be some assumptions needed. Firstly, I'm not sure about how strong they are. Moreover, since they are relatively heavy in maths, it would be great to give more intuition to help readers better understand them.

1. Assumption 4.1 looks like a very strong assumption. The extension mapping assumption might be hard to verify in practice.

2. The safety hypercube is used to ensure that perturbation points are always feasible. However, I don't see how p and r are used in the simulation section or can be estimated in practical applications.

3. The problem setting is not new; it extends a previous m-combinatorial bandit paper that used quadratic losses [Sadeghi & Fazel (2024)]. However, no simulation comparisons are provided for quadratic losses.