Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs
We define and study the problem of predicting the solution to a linear program (LP) given only partial information about its objective and constraints. This generalizes the problem of learning to predict the purchasing behavior of a rational agent who has an unknown objective function, that has been studied under the name "Learning from Revealed Preferences". We give mistake bound learning algorithms in two settings: in the first, the objective of the LP is known to the learner but there is an arbitrary, fixed set of constraints which are unknown. Each example is defined by an additional known constraint and the goal of the learner is to predict the optimal solution of the LP given the union of the known and unknown constraints. This models the problem of predicting the behavior of a rational agent whose goals are known, but whose resources are unknown. In the second setting, the objective of the LP is unknown, and changing in a controlled way. The constraints of the LP may also change every day, but are known. An example is given by a set of constraints and partial information about the objective, and the task of the learner is again to predict the optimal solution of the partially known LP.
The paper provides learning algorithm for predicting the solution of linear program with partial observation and provides some mistake bounds for these algorithms. Two different problems are considered: 1) The objective function of LP is known but the constraint sets are not known.  At each time a new constraint is revealed and the goal is to predict the optimal solution of the LP including all known and unknown constraints. 2) The objective function is unknown (it can be a linear combination of different subsets of a collection of fixed but unknown vectors), but the learner observes the changing constraints at each day and again the goal is to predict the optimal solution of the LP.   In the first problem, the mistake bounds are obtained for two cases: when the new constraints are selected adversarially, in which case the authors show that given a uniform bound on the precision of the constraints and some other assumptions such as non-degeneracy of the constraints, there exists an algorithm with mistake bound and running time linear in terms of the number of edges of the underlying unknown polytope and the number of precision bits. It is shown that uniform upper bound on the precision bits is essential for dimensions higher than 2. To relax this issue, the authors consider the known objective LP problem in stochastic scenario where the revealed constraints at each time are independently chosen from an underlying unknown distribution, in which case a learning algorithm by expanding convex hulls is provided which attains in expectation at most linear mistakes in terms of the number of edges and grows only logarithmic in time. Moreover, this algorithm has been derandomized to give a deterministic algorithm with high probability bounds.      In the case of unknown setting, the authors use a variant of ellipsoid method to design a learning algorithm with polynomial bounds on running time and number of mistakes in terms of parameters of the problem (dimension, precision bits, etc).    
The proposed bounds scale linearly with the number of edges of the unknown polytope. As is mentioned, only when the number of edges is within an additive constant of the dimension, the results in this paper give polynomial bounds in terms of the dimension of the space, and finding an efficient algorithm with polynomial mistakes in terms of dimension is left as an open question. Could the authors please comment on this issue a bit further that what do they think about the existence of such algorithm based on their observations? Also, line 55 talks about halving technique with some performance guarantee. Is there any specific reference for this result?     Could you please explain why theorem 18 does not work for d=1, or d=2?  The idea of designing learnhull algorithm and its analysis is very interesting. Is there any similar approach which has been used earlier for a similar type of problem?    The definition of set \mathcal{F} and the intuition behind it in line 355 is not very clear. Could the authors please clarify it a bit further and explain how it is related to [5]?