Introduction
In the realms of economics and resource allocation, M♮-concave functions—often referred to as "gross substitute valuations"—represent a gold standard for discrete optimization. Unlike general submodular functions, which typically require approximation algorithms, M♮-concave functions are "well-behaved": their global maximum can be found exactly in polynomial time using a simple greedy algorithm.
However, real-world applications often require making decisions sequentially under uncertainty, a framework known as online learning. This paper provides the first comprehensive investigation into "no-regret" online maximization for M♮-concave functions. The authors explore whether the efficiency of offline M♮-concave optimization translates to the online setting, where an agent must learn the function through repeated interactions.
The Stochastic Bandit Setting
In the stochastic bandit setting, the underlying utility function remains fixed but is obscured by i.i.d. sub-Gaussian noise. The agent only receives feedback on the specific actions they take.
To address this, the authors develop an Explore-then-Commit (ETC) strategy. This approach utilizes a UCB-type algorithm (specifically MOSS) to explore the various "directions" available to the greedy algorithm. Once sufficient information is gathered to identify the optimal path with high probability, the algorithm commits to that sequence of actions.
Robustness of the Greedy Algorithm
A pivotal technical contribution of this work is the discovery that the greedy algorithm for M♮-concave functions is remarkably robust to local errors. The authors prove that if a sub-optimal choice is made at a single step of the greedy process due to noise, the resulting suboptimality in the final outcome grows only additively rather than exponentially. This resilience allows the use of noisy bandit feedback to guide discrete optimization effectively, resulting in a cumulative regret bound of $O(T^{2/3})$.
The Adversarial Hardness Result
While the stochastic setting yields positive results, the adversarial setting—where the utility function can change arbitrarily at each time step—presents a significant challenge. In a surprising departure from typical optimization problems, the authors prove that the online version of this problem is significantly harder than its offline counterpart.
Using a reduction from the 3-matroid intersection problem (a classic NP-hard problem in combinatorial optimization), the authors demonstrate that no polynomial-time algorithm can achieve standard no-regret performance in the adversarial full-information setting. Specifically, for any constant $\epsilon > 0$, no randomized polynomial-time algorithm can achieve $O(T^{1-\epsilon})$ regret. This reveals a "complexity gap": M♮-concave maximization is easy to solve offline but computationally intractable to learn online against an adversary.
Key Insights and Implications
Exact vs. Approximate Regret
For general submodular functions, researchers typically aim for $(1-1/e)$-regret because the underlying offline problem is NP-hard. Because M♮-concave functions are solvable exactly offline, this paper successfully targets "no-approximate" regret in the stochastic case—meaning the benchmark is the true global optimum, not an approximation.
The Summation Problem
The difficulty in the adversarial setting stems from a fundamental property of discrete convex analysis: the sum of two M♮-concave functions is not necessarily M♮-concave. In online learning, algorithms often rely on the aggregate performance of actions over time; since the aggregate of M♮-concave functions loses the structural properties of the individual functions, standard no-regret techniques fail.
Conclusion and Future Work
This research establishes the boundaries of online M♮-concave maximization. While stochastic environments allow for efficient learning with $O(T^{2/3})$ regret, adversarial environments are fundamentally restricted by computational complexity.
Future research may explore whether $T^{1/2}$ regret is achievable in the stochastic setting using non-greedy approaches or if the $T^{2/3}$ bound is indeed the fundamental limit for this class of functions. Additionally, there is potential to investigate "approximate" no-regret in adversarial settings to see if M♮-concavity allows for better approximation ratios than those available for general submodular functions.
Summary updated