No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting

We are truly grateful to the reviewer for the thoughtful comments and positive evaluation. First, we would like to address the following comment regarding weakness.

Weaknesses:

• For the upper bound, the techniques are fairly straightforward once we have Theorem 3.1. I am wondering if more can be done, e.g. regret that is sublinear in $K$, improving the bound for $T$ to $O(\sqrt{T})$, or sublinear approximate regret in the adversarial setting. These suggestions have been pointed out by the authors themselves, but they are relevant questions.

We appreciate the feedback and insights provided. As regards improving the $O(KN^{1/3}T^{2/3})$ regret bound in Theorem 4.3 for the stochastic bandit setting, we have discovered a recent preprint by Tajdini et al. (2023) that presents a relevant lower bound. In the submodular case, their lower bound implies that significant improvements to the $O(KN^{1/3}T^{2/3})$ regret bound are impossible without admitting exponential factors in $K$. While their result does not directly apply to our $\text{M}^\natural$-concave setting, we conjecture that a similar lower bound exists and that our $O(KN^{1/3}T^{2/3})$ regret bound is tight unless we admit exponential factors in $K$. For more details, please refer to the above global response.

Next, we would like to answer the following question.

Questions:

Please clarify the relationship between $\text{M}^\natural$-concave maximization and submodular function maximization. I found it hard to understand the relationship between these as it pertains to the results in this paper and the discussion therein. For example, the conclusion states that if the domain is restricted to ${0, 1}^V$ then we get online submodular function maximization as a special case. Here, the offline problem is NP-hard so I'm not sure how to interpret the fact that we can get sublinear-regret with respect to $\mathbb{E}[f^*(x^*)]$ with a polynomial-time algorithm.

We wish to clarify that the correct relationship we intended to describe in the conclusion is:

which is the opposite of the relationship mentioned in the reviewer's comment. We apologize for any confusion and appreciate it if you could notify us of any incorrect expressions in our manuscript.

Importantly, $\text{M}^\natural$-concave maximization on $\\{0, 1\\}^V$ is a special case that the greedy algorithm can exactly solve in polynomial time. This has been established by Murota and Shioura [33] and can also be derived from our Theorem 3.1 with $\mathrm{err}(i_k \mid x_{k-1}) = 0$. Since submodular maximization forms a larger problem class, sublinear regret with respect to $\mathbb{E}[f^*(x^*)]$ for stochastic bandit $\text{M}^\natural$-concave maximization does not imply exact algorithms for submodular maximization. Therefore, our sublinear regret bounds in Section 4 do not contradict any known results in $\text{M}^\natural$-concave or submodular maximization.

We hope this clarification has effectively addressed the reviewer's concerns. Please do not hesitate to let us know if further questions remain.

Some very minor comments:

• $\text{M}^\natural$-convexity is used in section 5, but not defined in the paper

We thank the reviewer for pointing this out. We will clarify that the $\text{M}^\natural$-convexity is defined by the negative of $\text{M}^\natural$-concavity, analogous to the standard convexity--concavity relationship.

We deeply appreciate the reviewer's dedication to reviewing our paper and providing many insightful comments.

First, we would like to respond to some comments regarding weaknesses.

Weaknesses:

1. The stochastic setting algorithms and analysis adapting a greedy algorithm from the offline setting (including an ETC method getting $T^{-2/3}$) are straightforward (once a robustness result is in hand), though the authors do acknowledge that in the main paper.

We acknowledge the reviewer's point. Indeed, while our algorithm is straightforward, significantly improving our $O(T^{2/3})$ regret seems challenging unless we admit exponential dependence on $K$. Please refer to the above global response for details.

2. This is a somewhat minor point – since the need for a novel robustness analysis arises due to the offline proof of the greedy algorithm’s not already being in a manner that can be easily adapted to account for local errors (which is unlike the proof of $1-1/e$ for the greedy approximation algorithm for cardinality constrained submodular maximization, as noted in Appendix A), I think it would have been helpful to include the proof(s) for constrained $M^\sharp$-concave maximization (specialized to cardinality constraint) so that this need would be more apparent, that no standard proof has a sequential exchange argument that would already lend itself more readily to analyzing robustness and that the robustness result used in the offline setting with exact value oracles clearly constitutes a distinct proof.

We appreciate this valuable suggestion. The original proof by Murota and Shioura [33 Section 3], which is based on a convexity argument along the trajectory of an augmenting-type algorithm, is a quite different approach that does not readily align with the robustness analysis. To add further, we wish to highlight that our proof of Theorem 3.1, with $\mathrm{err}(i_k \mid x_{k-1}) = 0$, serves as an alternative proof of the optimality of the greedy algorithm for the offline $\text{M}^\natural$-concave maximization.

3. minor point – it is not clear to what extent the positive result in the stochastic setting can be generalized beyond a simple cardinality constraint.

This is an interesting future direction. Indeed, in the offline setting, the greedy-type algorithm can solve more general $\text{M}^\natural$-concave maximization problems. When it comes to online/bandit settings, extending the robustness analysis akin to Theorem 3.1 will be a key point of investigation.

Next, we would like to respond to the following question.

Questions:

1. What is known about the hardness of offline optimization for maximizing sums of (possibly non-monotone) $M^\sharp$-concave functions? For the adversarial setting, the authors use an interesting construction based on matroid intersection to prove hardness for no-approximation sublinear regret (with poly-time per round computation). But I wonder if it could have been reached in a more straightforward manner. Namely, for the stochastic setting, the regret is based on a single $M^\sharp$-concave function $f^*$ for which in the offline setting the greedy algorithm can find the optimal solution. In the adversarial setting, however, the regret is based on a sum of $M^\sharp$-concave functions and in line 100 we are told that in general the class of $M^\sharp$ functions is not closed under addition.

In the offline setting, maximizing the sum of more than two $\text{M}^\natural$-concave functions is NP-hard in general. This is recognized as folklore within the field of discrete convex analysis; those familiar with $\text{M}^\natural$-concavity would readily infer this NP-hardness due to the connection to the 3-matroid intersection, by encoding a base family of a matroid with an $\text{M}^\natural$-concave indicator function $f:\\{0, 1\\}^V \to \\{0, -\infty\\}$. To our knowledge, however, no explicit proof exists in the literature (although the NP-hardness is mentioned in a seminar material by Kazuo Murota, titled "Discrete Convex Analysis," used in the 2015 Summer School at Hausdorff Institute of Mathematics). Our work would be the first to provide an explicit proof, although the NP-hardness itself is already widely recognized.

More importantly, our Lemma 5.5 implies a slightly stronger result: even if $\text{M}^\natural$-concave functions on $\\{0, 1\\}^V$ are restricted to take values in $[0, 1]$ (forbidden taking $-\infty$), maximizing the sum of more than two $\text{M}^\natural$-concave functions remains NP-hard. This restriction is crucial to ensure that our NP-hardness result is meaningful because, if $f_t$ can take $-\infty$, the learner who does not know $f_t$ a priori cannot achieve even a bounded regret, making the hardness result (Theorem 5.2) vacuous. The reduction from the 3-matroid intersection with $\text{M}^\natural$-concave functions that do not take $-\infty$ has not been even recognized in the literature. Thus, our Lemma 5.5, despite being somewhat specific, provides a new crucial technical result. We believe that no significantly more straightforward approach could establish meaningful NP-hardness.

We hope this clarification has effectively addressed the reviewer's question and highlighted the value of our technical contributions. Please do not hesitate to reach out during the discussion period if further questions remain.

We greatly appreciate the reviewer's insightful comments and positive evaluation. We address the questions below.

1. In theorem 4.2, does $sReg_T$ is equivalent to the error in the Best-arm identification problem?

Our ${\rm sReg}_T$ is essentially the same as the error measure in the best-arm identification, like the one used by Rejwan and Mansour [41]. To clarify the connection to Rejwan and Mansour [41] mentioned in the conclusion section, there is a bit of difference: they consider the $(\varepsilon, \delta)$-PAC guarantee, i.e., the high probability bound on the expected error, whereas our ${\rm sReg}_T$ focuses solely on the expected error. Nevertheless, their sample complexity lower bound [41, Theorem 10] of $T\gtrsim\Omega(N/\varepsilon^2)$ applies to any $K\le N/2$ and $\delta \in (0, 1/2)$, and hence Markov's inequality implies that our bound of ${\rm sReg}_T = O(K^{3/2}\sqrt{N/T})$ in Theorem 4.2 is tight with respect to $N$ and $T$ when $K=O(1)$.

2. Does the bit-O term in theorem 4.2 and 4.3 hide the logarithmic term?

The big-O notation in Theorems 4.2 and 4.3 does not hide any logarithmic terms. Our algorithms in Section 4 employ the minimax optimal strategy (MOSS) (e.g., Lattimore and Szepesvári [24, Chapter 9]), whose regret bound is free of $\log T$ factors that are typically present in the regret bounds of standard UCB-type algorithms. Consequently, our regret bounds do not involve logarithmic factors. To add further, this strategy could slightly improve previous explore-then-commit approaches for stochastic bandit submodular maximization [37, 38], which contain $\log T$ factors.

3. The theorem 4.3 claims that the proposed algorithm for stochastic bandit achieves cumulative regret as $O(KN^{1/2}T^{2/3})$. While according to [1], the tight lower bound of a consistent bandit algorithm is $\Theta(K^{1/2}T^{1/2})$. What kind of factor do you think causes the gap between your upper and lower bound?

[1] Auer, Peter, et al. "The nonstochastic multiarmed bandit problem." SIAM journal on computing 32.1 (2002): 48-77.

We greatly value this insightful question. In our opinion, the primary challenge stems from the presence of exponentially many arms: even if we restrict the domain to $\\{0, 1\\}^V$, there are about $N^K$ arms. This leads to the following dilemma:

1. If we aim to achieve $O(\sqrt{T})$ regret, we may naively apply a UCB-type algorithm to the multi-armed bandit problem with about $N^K$ arms. However, this approach results in $O(\sqrt{N^K T})$ regret, and the algorithm requires exponential time per round in general.
2. Alternatively, we can design more efficient strategies based on offline algorithms. In our case, we have designed a no-regret strategy by executing a UCB-type algorithm in each iteration in the greedy algorithm, as described in Section 4. This method employs $K$ no-regret learners; however, only a single bandit feedback is available in each round. Due to this limited feedback, we need sufficient exploration across $K$ iterations in the greedy algorithm, as the explore-then-commit strategy does. Consequently, we incur $T^{2/3}$ regret as in Theorem 4.3.

Furthermore, as detailed in the above global response, a recent lower-bound result by Tajdini et al. (2023) suggests that we cannot do significantly better than the above two strategies in the case of submodular maximization. While there might be a slight possibility of achieving better regret by focusing on the $\text{M}^\natural$-concave case, we conjecture that we cannot achieve $\sqrt{T}$ regret that depends only polynomially on $K$ and $N$.

We hope our responses have adequately addressed the reviewer's questions. Please do not hesitate to reach out during the discussion period if there are any further questions.

We deeply appreciate the reviewer's continued support of our paper. We will make every effort to include a rigorous discussion on the tightness of our $O(KN^{1/3}T^{2/3})$-regret bound based on Tajdini et al. (2023).

Just to be thorough, we would like to add to our previous response that the difficulty in achieving $O(\sqrt{T})$-regret arises not only from the exponentially many arms but also from the non-linearity of $\text{M}^\natural$-concave reward functions. While combinatorial bandits with linear rewards admit $O(\sqrt{T})$-regret algorithms such as COMBAND (Cesa-Bianchi & Lugosi, 2012), achieving $O(\sqrt{T})$-regret that depends polynomially on the problem size is significantly more challenging when dealing with non-linear rewards, as suggested by Tajdini et al. (2023) for the case of submodular rewards.

We really appreciate the reviewer's effort in reviewing our paper and providing thoughtful comments. Below is our answer to the question.

Questions:

1. What is the main technical challenge in getting $\sqrt{K}$ regret for stochastic settings? Specifically, what is the difficulty when implementing the UCB-type exploration on the fly rather than doing an explore-then-commit algorithm?

We appreciate this insightful question. Our response assumes the question refers to $\sqrt{T}$ regret (not $\sqrt{K}$). Please let us know if this is not your intended question!

The fundamental difficulty lies in the fact that there are exponentially many arms. Indeed, if the domain is restricted to $\\{0, 1\\}^V$, we can achieve a $\sqrt{T}$ regret bound by regarding all subsets of size up to $K$ as arms and naively applying a UCB-type algorithm to this multi-armed bandit problem. However, this approach leads to a regret bound of $O\left(\sqrt{\binom{N}{K}T}\right)$, which depends exponentially on $K$, and the resulting algorithm requires exponential time per round in general. By contrast, the explore-then-commit strategy can achieve the $O(KN^{1/3}T^{2/3})$ regret bound as in Theorem 4.3, albeit with the worse dependence on $T$, and the algorithm runs in polynomial time per round.

As detailed in the global response, a recent lower bound by Tajdini et al. (2023) implies that, in the submodular maximization case, we cannot do significantly better than the naive UCB applied to $\binom{N}{K}$ arms and the explore-then-commit strategy. While there is a slight possibility of achieving better regret bounds by focusing on the $\text{M}^\natural$-concave case, we conjecture that a similar lower bound likely exists and that our $O(KN^{1/3}T^{2/3})$ regret is essentially tight unless we allow the regret bound to depend exponentially on $K$.

We hope this explanation helps the reviewer better understand the challenge in stochastic bandit $\text{M}^\natural$-concave maximization and casts our results in a more favorable light. Please do not hesitate to ask further questions during the discussion period.