2018/11/16 by Andrey Bernstein, Bernstein, Andrey, Niek J. Bouman +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Dynamical Systems (math.DS) #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1811.07734
openalex publication_date 2018/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper considers a discrete-time decision problem wherein a decision maker has to track, on average, a sequence of inputs selected from a convex set \mathcal X ⊂ ℝd by choosing actions from a possibly non-convex feasible set \mathcal Y⊂ ℝd, where \mathcal X is in fact the convex hull of \mathcal Y. We study some generalized variants of this problem, in which: (i) \mathcal X and \mathcal Y vary with time, and (ii) there might be a delay between them, in the sense that \mathcal X is the convex hull of the previous \mathcal Y. We investigate the conditions under which the greedy algorithm that minimizes, in an online fashion, the accumulated error between the sequence of inputs and decisions, is able to track the average input asymptotically. Essentially, this comes down to proving that the accumulated error, whose evolution is governed by a non-linear dynamical system, remains within a bounded invariant set. Applications include control of discrete devices using continuous setpoints; control of highly uncertain devices with some information delay; and digital printing, scheduling, and assignment problems.