論文の概要: Online Algorithms with Unreliable Guidance

• arxiv url: http://arxiv.org/abs/2602.20706v1
• Date: Tue, 24 Feb 2026 09:11:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.68701
• Title: Online Algorithms with Unreliable Guidance
• Title（参考訳）: 信頼できない誘導を伴うオンラインアルゴリズム
• Authors: Julien Dallot, Yuval Emek, Yuval Gil, Maciej Pacut, Stefan Schmid,
• Abstract要約: 本稿では、信頼できないガイダンス付きオンラインアルゴリズム(OAG)と呼ばれるML強化オンライン意思決定の新しいモデルを提案する。 OAGアルゴリズムは、要求応答ゲームのレンズを通して定式化され、各要求に対して、問題の応答空間から取られたガイダンスを受信する。 我々は、オンラインアルゴリズムをOAGモデルにおける学習強化オンラインアルゴリズムに変換するDrop or Trustly (DTB)コンパイラと呼ばれる体系的手法について述べる。
• 参考スコア（独自算出の注目度）: 6.891896330885501
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper introduces a new model for ML-augmented online decision making, called online algorithms with unreliable guidance (OAG). This model completely separates between the predictive and algorithmic components, thus offering a single well-defined analysis framework that relies solely on the considered problem. Formulated through the lens of request-answer games, an OAG algorithm receives, with each incoming request, a piece of guidance which is taken from the problem's answer space; ideally, this guidance is the optimal answer for the current request, however with probability $β$, the guidance is adversarially corrupted. The goal is to develop OAG algorithms that admit good competitiveness when $β= 0$ (a.k.a. consistency) as well as when $β= 1$ (a.k.a. robustness); the appealing notion of smoothness, that in most prior work required a dedicated loss function, now arises naturally as $β$ shifts from $0$ to $1$. We then describe a systematic method, called the drop or trust blindly (DTB) compiler, which transforms any online algorithm into a learning-augmented online algorithm in the OAG model. Given a prediction-oblivious online algorithm, its learning-augmented counterpart produced by applying the DTB compiler either follows the incoming guidance blindly or ignores it altogether and proceeds as the initial algorithm would have; the choice between these two alternatives is based on the outcome of a (biased) coin toss. As our main technical contribution, we prove (rigorously) that although remarkably simple, the class of algorithms produced via the DTB compiler includes algorithms with attractive consistency-robustness guarantees for three classic online problems: for caching and uniform metrical task systems our algorithms are optimal, whereas for bipartite matching (with adversarial arrival order), our algorithm outperforms the state-of-the-art.
• Abstract（参考訳）: 本稿では、信頼できないガイダンス付きオンラインアルゴリズム(OAG)と呼ばれるML強化オンライン意思決定の新しいモデルを提案する。 このモデルは予測的コンポーネントとアルゴリズム的コンポーネントを完全に分離し、考慮された問題にのみ依存する単一の明確に定義された分析フレームワークを提供する。 OAGアルゴリズムは、要求応答ゲームのレンズを通して定式化され、各要求に対して、問題の応答空間から取り出されたガイダンスを受信する。 目的は、$β=0$(すなわち一貫性)と$β=1$(つまり堅牢性)の場合に、優れた競合性を認めるOAGアルゴリズムを開発することである。 次に、DTB(Drop or Trustly)コンパイラと呼ばれる系統的手法を説明し、任意のオンラインアルゴリズムをOAGモデルにおける学習強化オンラインアルゴリズムに変換する。 予測可能なオンラインアルゴリズムが与えられた場合、DTBコンパイラを適用した学習強化されたアルゴリズムは、受信したガイダンスを盲目的に追従するか、あるいは完全に無視し、初期アルゴリズムが持つように進行する。 我々の主要な技術的貢献として、DTBコンパイラによって生成されるアルゴリズムのクラスは、驚くほど単純ではあるが、3つの古典的なオンライン問題に対して魅力的な一貫性と損益性を保証するアルゴリズムを含んでいることを証明している。

関連論文リスト

• Online Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Health [3.534690532561709]
  オンライン一様サンプリング(OUS)の新たな課題として,未知の意思決定時間に一様にサンプリング予算を分散させることが目的である。 OUS問題では、アルゴリズムは予算$b$とタイムホライズ$T$を与えられ、敵は[b,T]$の値$tau*を選択し、それをオンラインに公開する。 この問題に対して設計された最初のランダム化アルゴリズムを提示し、その後、学習拡張を組み込むように拡張する。
  論文  参考訳（メタデータ） (2024-02-03T02:36:59Z)
• Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
  各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。 この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。 本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-31T22:59:23Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  動的後悔と適応的後悔を最適化する効率的な方法を提案する。 提案アルゴリズムでは,各ラウンドで1つの勾配クエリと1つの関数評価しか必要としない。 また、さらに強力な測度、すなわち「内部的動的後悔」を研究し、ラウンド当たりの射影数を$O(log2 T)$から$$$$に減らした。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Adversarial Deep Learning for Online Resource Allocation [12.118811903399951]
  私たちはディープニューラルネットワークを使って、リソース割り当てと価格の問題に対するオンラインアルゴリズムをゼロから学習しています。 私たちの研究は、最悪のパフォーマンス保証の観点から、ディープニューラルネットワークを使用してオンラインアルゴリズムを設計した初めてのものです。
  論文  参考訳（メタデータ） (2021-11-19T15:48:43Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)

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

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