Online Linear Programming with Unobserved Constraints

We consider online linear programming with unobserved constraints (LPUC) – a generalization of stochastic linear optimization – where in each round a learner chooses a solution and subsequently receives some feedback about the feasibility of the selected solution w. r. t. the unknown constraints, e. g. , indicating which constraint is violated or how much the solution deviates from the feasibility set. To tackle this problem, we develop two algorithms, namely, LPUC-ED based on the epsilon-decreasing strategy and LPUC-UCB based on the upper confidence bound strategy, and derive finite time bounds on the regret and the constraint violation.

Authors

• Wenzhuo Yang
• Shie Mannor Technion - Israel Institute of Technology NVIDIA Research
• Huan Xu

Keywords

No keywords are indexed for this paper.