Online Learning under Budget and ROI Constraints via Weak Adaptivity

arXiv:2302.01203v3 Announce Type: replace-cross
Abstract: We study online learning problems in which a decision maker has to make a sequence of costly decisions, with the goal of maximizing their expected reward while adhering to budget and return-on-investment (ROI) constraints. Existing primal-dual algorithms designed for constrained online learning problems under adversarial inputs rely on two fundamental assumptions. First, the decision maker must know beforehand the value of parameters related to the degree of strict feasibility of the problem (i.e. Slater parameters). …

abstract adversarial algorithms arxiv budget constraints cs.gt cs.lg decision decisions investment maker online learning primal roi study type via