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

Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-23 03:10:42

Abstract: M${}^{\natural}$-concave functions, a.k.a. gross substitute valuation functions, play a fundamental role in many fields, including discrete mathematics and economics. In practice, perfect knowledge of M${}^{\natural}$-concave functions is often unavailable a priori, and we can optimize them only interactively based on some feedback. Motivated by such situations, we study online M${}^{\natural}$-concave function maximization problems, which are interactive versions of the problem studied by Murota and Shioura (1999). For the stochastic bandit setting, we present $O(T^{-1/2})$-simple regret and $O(T^{2/3})$-regret algorithms under $T$ times access to unbiased noisy value oracles of M${}^{\natural}$-concave functions.  A key to proving these results is the robustness of the greedy algorithm to local errors in M${}^{\natural}$-concave function maximization, which is one of our main technical results. While we obtain those positive results for the stochastic setting, another main result of our work is an impossibility in the adversarial setting. We prove that, even with full-information feedback, no algorithms that run in polynomial time per round can achieve $O(T^{1-c})$ regret for any constant $c > 0$ unless $\mathsf{P} = \mathsf{NP}$.  Our proof is based on a reduction from the matroid intersection problem for three matroids, which would be a novel idea in the context of online learning.

Main paper: 
  
 Appendix:  


Decision: This paper studied the online bandit problem of maximizing M-concave functions. Through a new error decomposition, it established regret guarantees in the stochastic setting. More noteworthy was the hardness of regret minimization in the adversarial case, which the reviewers also appreciated. Happy to recommend this paper for acceptance.

Reviews: review: paper_summary: paper_summary: This paper studies the online optimization problem with $M^\natural$-concave function, which has many real-world implications such as maximum-flow on bipartite graphs, gross substitute valuation, resource allocation and bandit problem. $M^\natural$-concave function forms the fundamental basis of discrete concave analysis. In the stochastic bandit setting, they present algorithms with $O(T^-1/2)$ simple regret and $O(T^2/3)$ cumulative regret. These results leverage the robustness of the greedy algorithm to local errors, a significant technical contribution of the paper.

Additionally, the author also presents the result in the adversarial online learning setting, the paper proves that achieving sub-linear regret is NP-hard, even with full-information feedback, which establishes a distinct difference from the offline setting.
strength_weakness: strength_weakness: No obvious weaknesses.
questions: questions: I am more curious about the conclusion in the bandit example.

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

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

3. The theorem 4.3 claims that the proposed algorithm for stochastic bandit achieves cumulative regret as $O(K N^{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.
limitations: limitations: Please refer to Questions.
paper_summary: paper_summary: This paper studies the online version of M-concave function maximization. With the help of a new lemma that bounds local errors for greedy algorithms, the authors derive an efficient $T^{-1/2}$ simple regret algorithm together with a $T^{2/3}$ regret algorithm for stochastic settings. Moreover, the authors show an interesting computational hardness result for adversarial settings with full information.
strength_weakness: strength_weakness: 1. The regret bound for stochastic setting is not tight.
questions: 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?
limitations: limitations: Yes.
paper_summary: paper_summary: The authors consider online $M^\sharp$-concave optimization, similar to problems like online convex optimization and online DR-submodular optimization.  $M^\sharp$-concave function classes include resource allocation, valuation, and flow problems, and unlike DR-submodular functions can be exactly optimized (at least under a cardinality constraint) by a simple greedy algorithm.  The authors show standard online adaptation of the greedy algorithm analogous to similar work for submodular functions, though prove the robustness of the offline algorithm to oracle value errors in a manner distinct from previous robustness analyses (such as for submodular functions).  The authors also show that unlike OCO and online DR-submodular optimization, the adversarial setting is fundamentally harder than the stochastic setting – one cannot (with poly-time per round complexity) achieve sublinear regret.
strength_weakness: strength_weakness: 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.  

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.  

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.  

4. minor point – there is no implementation or experiments for toy flow/valuation/resource allocation problems.
questions: 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.
limitations: limitations: Yes
paper_summary: paper_summary: This paper considers online learning variants of ${\rm M}^\natural$-concave function maximization.  These types of function generalize maximum flows on graphs (where the variable is the vector of source values on each node), gross substitute valuations in economics, and have applications in resource allocation.

This paper has two main results:

 - A learning strategy with $O(K N^{1/3} T^{2/3})$-regret in the stochastic setting (here we can query a function at a given input and observe its output perturbed by mean 0, 1-subgaussian noise and we have $T$ rounds to perform these queries).  This is obtained by showing that the greedy algorithm is "robust to local errors", and is the key technical step for this result.  The regret bound follows by an application of known results for pure-exploration + the explore-then-commit paradigm.

 - NP-hardness for the adversarial setting.  Unless P=NP, it is impossible for any polynomial time learner to achieve sub-linear regret in the adversarial setting.  This is done via a clever reduction from the 3-matroid-intersection problem.
strength_weakness: strength_weakness: - 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.
- The stochastic online setting for this problem could be better motivated than the paragraph in lines 122-126.  More concrete examples would be helpful to clarify the applicability of these results beyond the nice mathematics.
- No experimental evaluation.  While this paper makes a nice theoretical contribution, it could be helpful to demonstrate that the theory is applicable to a problem that prior methods were not suitable for.
questions: questions: Please clarify the relationship between ${\rm 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.

Some very minor comments:
- ${\rm M}^\natural$-convexity is used in section 5, but not defined in the paper
limitations: limitations: The authors have adequately addressed and discussed limitations of their work.

Comments: comment: I have read the rebuttal.  Thanks to the authors for their response.  I have decided to increase my score.  I do not have 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.
Thanks for your detailed explanation of the tightness of the $O(KN^{1/3}T^{2/3})$ regret bound in Theorem 4.3. Please add a formal justification in your paper based on your findings from Tajdini et al. (2023) if you can. I will not change my score since I have already supported this paper in my original review.
Thank you for the detailed response. Yeah, my question is about the difficulty of getting $\sqrt{T}$ regret. I do not have further questions now.
Thank you for the detailed response to my specific questions and the general response above.  For the M-concave vs. submodular discussion above my issue was one of slight confusion with what is written in the text.  Your response has cleared this up.  My overall evaluation stays the same.