Online Decision-Making in General Combinatorial Spaces

Arun Rajkumar, Shivani AgarwalNeurIPS 2014 · OpenReview

Introduction

In online combinatorial optimization, a learner is tasked with choosing a complex structure—such as a spanning tree in a graph or a specific permutation of items—in each round of a sequence, without prior knowledge of the associated costs. The ultimate goal is to minimize regret, defined as the difference between the learner's total accumulated loss and the loss of the best fixed structure chosen in hindsight.

Historically, this problem has faced two major hurdles. First is computational complexity: the number of possible structures often scales exponentially (e.g., $n!$ permutations), rendering naive approaches like the standard Hedge algorithm computationally intractable. Second is the representation gap: previous efficient algorithms were largely siloed. Some were strictly designed for Boolean (0-1) representations, while others were highly tailored to specific submodular functions. Until now, there has been no unified theoretical framework capable of handling arbitrary vector representations of a combinatorial space.

This paper bridges that gap by introducing Low-Dimensional Online Mirror Descent (LDOMD), a unified framework that represents complex decision spaces as low-dimensional convex polytopes, achieving tighter regret bounds and generalizing several state-of-the-art methods.

The LDOMD Framework

Instead of maintaining a probability distribution over every possible exponential structure, LDOMD operates within a lower-dimensional vector space where the combinatorial structures are represented simply as vertices of a convex polytope.

The algorithm is driven by two key geometric operations:

  1. Bregman Projection Step: After receiving a loss vector and updating the current "state" in the dual space, the algorithm projects that state back onto the polytope using a Bregman divergence (such as KL-divergence or squared Euclidean distance).
  2. Decomposition Step: The algorithm takes this projected point inside the polytope and efficiently expresses it as a convex combination (a weighted average) of the polytope's vertices. This allows the learner to sample and play a specific, valid combinatorial structure.

By formalizing these steps, LDOMD generalizes previous methods like the Component Hedge algorithm (typically used for 0-1 polytopes) and recent advances in submodular polytopes. It provides a universal "recipe" for online learning: if one can find an efficient way to decompose and project for a specific polytope, one can derive a regret-optimal algorithm.

Key Insights and Theoretical Applications

A central insight of the paper is that the polytope is the key. The framework shifts the analytical focus away from the discrete structures themselves and toward the geometry of the convex polytope formed by their vector representations. The "shape" of the regret bound is fundamentally determined by whether a representation is Boolean or continuous.

While most prior work focused exclusively on 0-1 (Boolean) vectors, this paper demonstrates that LDOMD is equally powerful for general polytopes where vertices are not necessarily 0-1. The authors evaluate their framework by deriving regret bounds and algorithmic complexities for several fundamental combinatorial structures:

  • Matroid Polytopes (e.g., Spanning Trees)
  • Submodular Base Polytopes
  • Permutahedrons (useful for ranking and scheduling)
  • Transportation Polytopes (a novel application introduced in this work)

Main Results

The theoretical guarantees provided by LDOMD match or exceed the best-known specialized algorithms:

  • Optimal Regret for 0-1 Polytopes: For 0-1 polytopes of "size" $m$ in $d$ dimensions, LDOMD achieves a regret bound of $O(m\sqrt{T \ln(d/m)})$, which is essentially optimal.
  • Breakthrough in Online Transportation: The authors provide the first specialized treatment of the online transportation problem. They develop a novel $O(m^3n^3)$ decomposition algorithm based on spanning forests in bipartite graphs, utilizing Sinkhorn balancing for efficient projection.
  • Transportation Regret Bounds: For a transportation problem with a total supply $q$, the framework guarantees a regret bound of $O(q\sqrt{T \ln(\max(mn, q))})$.

Limitations and Future Directions

While LDOMD offers a powerful unifying theory, its practical application is entirely dependent on the algorithmic efficiency of the decomposition and projection steps. For many complex polytopes, these operations remain computationally expensive or currently lack known polynomial-time algorithms.

Furthermore, for the online transportation problem, the projection step relies on Sinkhorn balancing, which is an approximate method. Although the authors argue this approximation does not significantly degrade the regret, a more rigorous theoretical analysis of the trade-off between approximation error and regret is a promising area for future research. Finally, the current framework operates in the "full information" setting, where the learner observes the entire loss vector after each round. Adapting LDOMD to the "bandit" setting—where the learner only observes the loss of the specific structure they chose—remains a critical next step for the field.

Summary updated

Abstract

We study online combinatorial decision problems, where one must make sequential decisions in some combinatorial space without knowing in advance the cost of decisions on each trial; the goal is to minimize the total regret over some sequence of trials relative to the best fixed decision in hindsight. Such problems have been studied mostly in settings where decisions are represented by Boolean vectors and costs are linear in this representation. Here we study a general setting where costs may be linear in any suitable low-dimensional vector representation of elements of the decision space. We give a general algorithm for such problems that we call low-dimensional online mirror descent (LDOMD); the algorithm generalizes both the Component Hedge algorithm of Koolen et al. (2010), and a recent algorithm of Suehiro et al. (2012). Our study offers a unification and generalization of previous work, and emphasizes the role of the convex polytope arising from the vector representation of the decision space; while Boolean representations lead to 0-1 polytopes, more general vector representations lead to more general polytopes. We study several examples of both types of polytopes. Finally, we demonstrate the benefit of having a general framework for such problems via an application to an online transportation problem; the associated transportation polytopes generalize the Birkhoff polytope of doubly stochastic matrices, and the resulting algorithm generalizes the PermELearn algorithm of Helmbold and Warmuth (2009).
BibTeX
@inproceedings{rajkumar2014online,
  author = {Arun Rajkumar and Shivani Agarwal},
  title = {{Online Decision-Making in General Combinatorial Spaces}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=H1WOdubOWH},
}
Figure