Online Decision-Making in General Combinatorial Spaces
Authors: Arun Rajkumar, Shivani Agarwal
NeurIPS 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 Perm ELearn algorithm of Helmbold and Warmuth (2009). |
| Researcher Affiliation | Academia | Department of Computer Science and Automation Indian Institute of Science, Bangalore 560012, India {arun r,shivani}@csa.iisc.ernet.in |
| Pseudocode | Yes | Figure 2: The LDOMD algorithm. Algorithm Low-Dimensional OMD (LDOMD) for Online Combinatorial Decision-Making |
| Open Source Code | No | The paper does not provide any information or links regarding open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not report on experiments using datasets, so no information about dataset availability is provided. |
| Dataset Splits | No | The paper is theoretical and does not report on experiments or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report on experiments, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not report on experiments, so no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis rather than empirical evaluation, so no experimental setup details like hyperparameters are provided. |