Stronger, Tractable Notions of Regret for Online Submodular Maximization

Online Submodular Maximization (OSM) is typically evaluated via static regret, which only guarantees competitiveness with the best fixed action in hindsight. While fundamental, this notion fails to capture more refined notions of rational behavior that arise naturally in combinatorial decision spaces. We revisit OSM through the lens of $\Phi$-regret, a family of stronger regret notions defined with respect to sets of action transformations. We identify rich yet tractable classes of transformations that encode natural operations on sets, including permutations and conditional trades, and show how to achieve sublinear $\Phi$-regret in polynomial time. Our algorithms combine classical machinery from online convex optimization with rounding schemes from combinatorial optimization.