Linear Contextual Bandits with Knapsacks
We consider the linear contextual bandit problem with resource consumption, in addition to reward generation. In each round, the outcome of pulling an arm is a reward as well as a vector of resource consumptions. The expected values of these outcomes depend linearly on the context of that arm. The budget/capacity constraints require that the total consumption doesn't exceed the budget for each resource. The objective is once again to maximize the total reward. This problem turns out to be a common generalization of classic linear contextual bandits (linContextual) [8,11,1], bandits with knapsacks (BwK) [3,9], and the online stochastic packing problem (OSPP) [4,14]. We present algorithms with near-optimal regret bounds for this problem. Our bounds compare favorably to results on the unstructured version of the problem [5,10] where the relation between the contexts and the outcomes could be arbitrary, but the algorithm only competes against a fixed set of policies accessible through an optimization oracle. We combine techniques from the work on linContextual, BwK and OSPP in a nontrivial manner while also tackling new difficulties that are not present in any of these special cases.
********************************************************* POST REBUTTAL:   Thanks for the corrections. I now vote for acceptance.   I hope the authors will spend the effort to improve the readability.  *********************************************************  A new linear contextual bandit setting is proposed that includes the addition of a d-dimensional budget. This generalises existing budgeted bandits to the linear case. Everything is assumed to be i.i.d., and the budget usage of an action is assumed to be a linear function of the context for that action and some unknown parameter.  Besides the setting (which is quite natural) the main contribution is a new algorithm and analysis showing that  ignoring logarithmic factors enjoys a regret of O((1+OPT/B) m Sqrt(T)) where m is the dimension of the action space, B is the budget and OPT is the payoff of the optimal static strategy. Although there are no lower bounds, by combining existing lower bounds the authors argue that this is not much improvable, which is quite convincing.
The algorithm operates mostly in a quite standard way. Constructing confidence ellipsoids around the unknown parameters and acting optimistically subject to a budget penalty. The latter part is the most interesting because one has to try and learn the direction in the budget space for which the algorithm is most constrained, for which the authors use online mirror descent. As far as I know this is a completely novel idea.  I found a lot to like in this paper. The setting and algorithm are interesting and the analysis is mostly quite good.    There were also some weaknesses, however. For of all, there is a lot of sloppy writing, typos and undefined notation. See the long list of minor comments below. A larger concern is that some parts of the proof I could not understand, despite trying quite hard. The authors should focus their  response to this review on these technical concerns, which I mark with ** in the minor comments below. Hopefully I am missing something silly.  One also has to wonder about the practicality of such algorithms. The main algorithm relies on an estimate of the payoff for the optimal policy, which can be learnt with sufficient precision in a "short" initialisation period. Some synthetic experiments might shed some light on how long the horizon needs to be before any real learning occurs.  A final note. The paper is over length. Up to the two pages of references it is 10 pages, but only 9 are allowed. The appendix should have been  submitted as supplementary material and the reference list cut down.   Despite the weaknesses I am quite positive about this paper, although it could certainly use quite a lot of polishing. I will raise my score once the **  points are addressed in the rebuttal.  Minor comments:  * L75. Maybe say that pi is a function from R^m \to \Delta^{K+1}  * In (2) you have X pi(X), but the dimensions do not match because you dropped the no-op action. Why not just assume the 1st column of X_t is always 0?   * L177: "(OCO )" -> "(OCO)" and similar things elsewhere  * L176: You might want to mention that the learner observes the whole concave function (full information setting)  * L223: I would prefer to see a constant here. What does the O(.) really mean here?  * L240 and L428: "is sufficient" for what? I guess you want to write that the sum of the "optimistic" hoped for rewards is close to the expected actual rewards.   * L384: Could mention that you mean |Y_t - Y_{t-1}| \leq c_t almost surely.  ** L431: \mu_t should be \tilde \mu_t, yes?  * The algorithm only stops /after/ it has exhausted its budget. Don't you need to stop just before? (the regret is only trivially affected, so this isn't too important).  * L213: \tilde \mu is undefined. I guess you mean \tilde \mu_t, but that is also not defined except in Corollary 1, where it just given as some point in the confidence ellipsoid in round t. The result holds for all points in the ellipsoid uniformly with time, so maybe just write that, or at least clarify somehow.  ** L435: I do not see how this follows from Corollary 2 (I guess you meant part 1, please say so). So first of all mu_t(a_t) is not defined. Did you mean tilde mu_t(a_t)? But still I don't understand. pi^*(X_t) is (possibly random) optimal static strategy while \tilde \mu_t(a_t) is the optimistic mu for action a_t, which may not be optimistic for pi^*(X_t)? I have similar concerns about the claim on the use of budget as well.  * L434: The \hat v^*_t seems like strange notation. Elsewhere the \hat is used for empirical estimates (as is standard), but here it refers to something else.   * L178: Why not say what Omega is here. Also, OMD is a whole family of algorithms. It might be nice to be more explicit. What link function? Which theorem in [32] are you referring to for this regret guarantee?  * L200: "for every arm a" implies there is a single optimistic parameter, but of course it depends on a  ** L303: Why not choose T_0 = m Sqrt(T)? Then the condition becomes B > Sqrt(m) T^(3/4), which improves slightly on what you give.  * It would be nice to have more interpretation of theta (I hope I got it right), since this is the most novel component of the proof/algorithm.