論文の概要: Online Search With Best-Price and Query-Based Predictions

• arxiv url: http://arxiv.org/abs/2112.01592v1
• Date: Thu, 2 Dec 2021 20:18:37 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-06 15:00:21.677522
• Title: Online Search With Best-Price and Query-Based Predictions
• Title（参考訳）: ベストプライスとクエリベースの予測を備えたオンライン検索
• Authors: Spyros Angelopoulos and Shahin Kamali and Dehou Zhang
• Abstract要約: 本稿では,入力に関する誤予測が存在する可能性のある学習増強アルゴリズムについて検討する。 株式市場から得られたデータに関する実験結果を提供する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: オンライン(時系列)検索問題において、プレイヤーは、オンライン形式で明らかにされる一連の価格を提示される。 問題の標準的定義では、プレイヤーは将来の価格(上限値と上限値の低い値を除く)の知識なしに、各明らかにされた価格に対して、プレイヤーがそれを受け入れるか拒否するかを不当に決定し、その目的は、競合比、すなわち、シーケンスの最大価格とプレイヤーが選択した値の最悪のケース比を最小化することである。 この問題は、明らかにされたサンプルの不確実性に直面した意思決定のいくつかの応用を定式化する。 この問題に関する以前の研究は、プレイヤーが入力に関する情報をほとんど持っていない、またはプレイヤーが強力でエラーのないアドバイスを提供するという極端なシナリオを想定していた。 本研究では,入力に関する誤予測が存在する可能性のある学習増強アルゴリズムについて検討する。 具体的には、予測がシーケンス内の最大価格に関連付けられた設定と、複数のバイナリクエリに対する応答として予測が得られた設定の2つの異なる設定について検討する。 いずれの設定においても,予測誤差の関数として,検索アルゴリズムの最悪の性能に対して,厳密な上・下・下限を提供する。 また,提案手法が他の学習強化アプリケーションに適用可能かどうかを論証し,理論分析を裏付ける証券市場から得られたデータに関する実験結果も提示する。

関連論文リスト

• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Online Dynamic Acknowledgement with Learned Predictions [13.821981661594844]
  オンラインの動的認知問題を再考する。 問題の目標は、総要求遅延と承認コストを最小化することです。 このエレガントなモデルは、承認コストとリクエストで経験した待ち時間のトレードオフを研究します。
  論文  参考訳（メタデータ） (2023-05-25T20:05:47Z)
• Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
  本研究では,不確実性下でのソートとハイパーグラフ配向のための学習強化アルゴリズムについて検討する。 我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
  論文  参考訳（メタデータ） (2023-05-16T07:52:08Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。 このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。 上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
  論文  参考訳（メタデータ） (2023-02-02T16:30:33Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
  論文  参考訳（メタデータ） (2022-05-25T15:24:03Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。 目標は、予測を処理し、最小コストで予測を行うことです。 アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
  論文  参考訳（メタデータ） (2022-04-21T01:22:18Z)
• Online Optimization with Untrusted Predictions [7.895232155155041]
  本稿では, オンライン最適化の課題について検討し, 意思決定者は, ラウンドごと, 非競争的打撃コスト, ラウンド間切替コストの合計に対して, 一般的な計量空間内の点を選択する必要がある。 本稿では,新しいアルゴリズムであるAdaptive Online Switching (AOS)を提案し,予測が完全であれば$tildecalO(alphadelta)$が不正確であっても$tildecalO(alphadelta)$であることを示す。
  論文  参考訳（メタデータ） (2022-02-07T21:08:02Z)
• Online Bin Packing with Predictions [11.306212771477645]
  様々なサイズの項目の列を、一様容量のビンの最小限の個数に配置しなければならない問題について、オンライン版について検討する。 我々は、一貫性(すなわち、予測誤差を仮定しない競争比)と堅牢性(すなわち、逆誤差の下での競争比)の間の効率的なトレードオフを持つオンラインアルゴリズムを設計し、分析する。 これは、学習可能な予測の現実的な設定において、競争分析の下でのオンラインビンパッキングに関する最初の理論的、実験的研究である。
  論文  参考訳（メタデータ） (2021-02-05T17:32:52Z)
• A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Experts [0.6091702876917281]
  私たちはこれを"ストック予測問題"と呼び、そのシーケンスを、各ステップで1ユニットずつ上昇または下降するストックの価格履歴と見なします。 この問題では、投資家は2つ以上の「専門家」の予測にアクセスでき、最後の後悔を最小限に抑えようとしている。 我々は、歴史に依存した専門家が2人いる場合について考察し、その予測は最近のd株の動きによって決定される。
  論文  参考訳（メタデータ） (2020-07-24T18:46:28Z)
• Predictive Bandits [68.8204255655161]
  我々は,予測的盗賊と呼ばれる,新たな盗賊問題を紹介し,研究する。 各ラウンドで、意思決定者はまず、特定の武器の報酬に関する情報を集めるかどうかを決定する。 意思決定者は、ラウンドで実際にプレイされる腕を選択する。
  論文  参考訳（メタデータ） (2020-04-02T17:12:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。