Online Search With Best-Price and Query-Based Predictions

• URL: http://arxiv.org/abs/2112.01592v1
• Date: Thu, 2 Dec 2021 20:18:37 GMT
• Title: Online Search With Best-Price and Query-Based Predictions
• Authors: Spyros Angelopoulos and Shahin Kamali and Dehou Zhang
• Abstract summary: We study learning-augmented algorithms in which there is a potentially erroneous prediction concerning the input. We provide experimental results on data obtained from stock exchange markets.
• Score: 2.3204178451683264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the online (time-series) search problem, a player is presented with a sequence of prices which are revealed in an online manner. In the standard definition of the problem, for each revealed price, the player must decide irrevocably whether to accept or reject it, without knowledge of future prices (other than an upper and a lower bound on their extreme values), and the objective is to minimize the competitive ratio, namely the worst-case ratio between the maximum price in the sequence and the one selected by the player. The problem formulates several applications of decision-making in the face of uncertainty on the revealed samples. Previous work on this problem has largely assumed extreme scenarios in which either the player has almost no information about the input, or the player is provided with some powerful, and error-free advice. In this work, we study learning-augmented algorithms, in which there is a potentially erroneous prediction concerning the input. Specifically, we consider two different settings: the setting in which the prediction is related to the maximum price in the sequence, as well as the setting in which the prediction is obtained as a response to a number of binary queries. For both settings, we provide tight, or near-tight upper and lower bounds on the worst-case performance of search algorithms as a function of the prediction error. We also provide experimental results on data obtained from stock exchange markets that confirm the theoretical analysis, and explain how our techniques can be applicable to other learning-augmented applications.

Related papers

• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Online Dynamic Acknowledgement with Learned Predictions [13.821981661594844]
  We revisit the online dynamic acknowledgment problem. The goal of the problem is to minimize the total request delay plus acknowledgement cost. This elegant model studies the trade-off between acknowledgement cost and waiting experienced by requests.
  arXiv  Detail & Related papers  (2023-05-25T20:05:47Z)
• Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
  We study learning-augmented algorithms for sorting and hypergraph orientation under uncertainty. Our algorithms provide improved performance guarantees for accurate predictions while maintaining worst-case guarantees that are best possible without predictions.
  arXiv  Detail & Related papers  (2023-05-16T07:52:08Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of $T$ days (or times) The goal is to make a prediction with the minimum cost, specifically compared to the best expert in the set. We show a space lower bound of $widetildeOmegaleft(fracnMRTright)$ for any deterministic algorithm that achieves regret $R$ when the best expert makes $M$ mistakes.
  arXiv  Detail & Related papers  (2023-03-03T04:39:53Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  We introduce a novel measure for quantifying the error in input predictions. The measure captures errors due to absent predicted requests as well as unpredicted actual requests.
  arXiv  Detail & Related papers  (2022-05-25T15:24:03Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  Online learning with expert advice is a fundamental problem of sequential prediction. The goal is to process predictions, and make a prediction with the minimum cost. An algorithm is judged by how well it does compared to the best expert in the set.
  arXiv  Detail & Related papers  (2022-04-21T01:22:18Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  We study the problem of online optimization, where a decision maker must choose points in a general metric space to the sum of per-round, non-competitive hitting costs and the costs of switching between rounds. We propose a novel algorithm, Adaptive Online Switching (AOS), and prove that, for any desired $delta 0)$competitive if predictions are perfect, it is $tildecalO(alphadelta)$ even when predictions are inaccurate.
  arXiv  Detail & Related papers  (2022-02-07T21:08:02Z)
• Online Bin Packing with Predictions [11.306212771477645]
  We study the online variant of the problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. We design and analyze online algorithms with efficient tradeoffs between the consistency (i.e., the competitive ratio assuming no prediction error) and the robustness (i.e., the competitive ratio under adversarial error) This is the first theoretical and experimental study of online bin packing under competitive analysis, in the realistic setting of learnable predictions.
  arXiv  Detail & Related papers  (2021-02-05T17:32:52Z)
• A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Experts [0.6091702876917281]
  We like to call it the'stock prediction problem,' viewing the sequence as the price history of a stock that goes up or down one unit at each time step. In this problem, an investor has access to the predictions of two or more 'experts,' and strives to minimize her final-time regret. We consider the case when there are two history-dependent experts, whose predictions are determined by the d most recent stock moves.
  arXiv  Detail & Related papers  (2020-07-24T18:46:28Z)
• Predictive Bandits [68.8204255655161]
  We introduce and study a new class of bandit problems, referred to as predictive bandits. In each round, the decision maker first decides whether to gather information about the rewards of particular arms. The decision maker then selects an arm to be actually played in the round.
  arXiv  Detail & Related papers  (2020-04-02T17:12:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.