<p>Online decision making with switching costs has received considerable attention in many practical problems that face uncertainty in the inputs and key problem parameters. Because of the switching costs that penalize the change of decisions, making good online decisions under such uncertainty is known to be extremely challenging. This thesis aims at providing new online algorithms with strong performance guarantees to address this challenge.</p>
<p><br></p>
<p>In part 1 and part 2 of this thesis, motivated by Network Functions Virtualization and smart grid, we study competitive online convex optimization with switching costs. Specifically, in part 1, we focus on the setting with an uncertainty set (one type of prediction) and hard infeasibility constraints. We develop new online algorithms that can attain optimized competitive ratios, while ensuring feasibility at all times. Moreover, we design a robustification procedure that helps these algorithms obtain good average-case performance simultaneously. In part 2, we focus on the setting with look-ahead (another type of prediction). We provide the first algorithm that attains a competitive ratio that not only decreases to 1 as the look-ahead window size increases, but also remains upper-bounded for any ratio between the switching-cost coefficient and service-cost coefficient.</p>
<p><br></p>
<p>In part 3 of this thesis, motivated by edge computing with artificial intelligence, we study bandit learning with switching costs where, in addition to bandit feedback, full feedback can be requested at a cost. We show that, when only 1 arm can be chosen at a time, adding costly full-feedback is not helpful in fundamentally reducing the Θ(<em>T</em>2/3) regret over a time-horizon <em>T</em>. In contrast, when 2 (or more) arms can be chosen at a time, we provide a new online learning algorithm that achieves a significantly smaller regret equal to <em>O</em>(√<em>T</em>), without even using full feedback. To the best of our knowledge, this type of sharp transition from choosing 1 arm to choosing 2 (or more) arms has never been reported in the literature.</p>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/19949975 |
| Date | 01 June 2022 |
| Creators | Ming Shi (12621637) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/thesis/On_the_Value_of_Prediction_and_Feedback_for_Online_Decision_Making_With_Switching_Costs/19949975 |
Page generated in 0.009 seconds