論文の概要: Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries

• arxiv url: http://arxiv.org/abs/2504.00461v1
• Date: Tue, 01 Apr 2025 06:35:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-03 13:20:26.897218
• Title: Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries
• Title（参考訳）: アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・アダプティブ・グラフにおけるオンラインショート・パスの効率的な近似アルゴリズム
• Authors: Arnab Maiti, Zhiyuan Fan, Kevin Jamieson, Lillian J. Ratliff, Gabriele Farina,
• Abstract要約: 本稿では,適応的相手に対する帯域フィードバックの下で,有向非巡回グラフ(DAG)における最短経路問題について検討する。 我々は,任意の適応的敵に対して高い確率で$tilde O(sqrt|E|Tlog |X|)$の最小限の最小残差を求めるアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 34.38978643261337
• License:
• Abstract: In this paper, we study the online shortest path problem in directed acyclic graphs (DAGs) under bandit feedback against an adaptive adversary. Given a DAG $G = (V, E)$ with a source node $v_{\mathsf{s}}$ and a sink node $v_{\mathsf{t}}$, let $X \subseteq \{0,1\}^{|E|}$ denote the set of all paths from $v_{\mathsf{s}}$ to $v_{\mathsf{t}}$. At each round $t$, we select a path $\mathbf{x}_t \in X$ and receive bandit feedback on our loss $\langle \mathbf{x}_t, \mathbf{y}_t \rangle \in [-1,1]$, where $\mathbf{y}_t$ is an adversarially chosen loss vector. Our goal is to minimize regret with respect to the best path in hindsight over $T$ rounds. We propose the first computationally efficient algorithm to achieve a near-minimax optimal regret bound of $\tilde O(\sqrt{|E|T\log |X|})$ with high probability against any adaptive adversary, where $\tilde O(\cdot)$ hides logarithmic factors in the number of edges $|E|$. Our algorithm leverages a novel loss estimator and a centroid-based decomposition in a nontrivial manner to attain this regret bound. As an application, we show that our algorithm for DAGs provides state-of-the-art efficient algorithms for $m$-sets, extensive-form games, the Colonel Blotto game, shortest walks in directed graphs, hypercubes, and multi-task multi-armed bandits, achieving improved high-probability regret guarantees in all these settings.
• Abstract（参考訳）: 本稿では,適応的相手に対する帯域フィードバックの下で,有向非巡回グラフ(DAG)のオンライン最短経路問題について検討する。 DAG $G = (V, E)$ with a source node $v_{\mathsf{s}}$ and a sink node $v_{\mathsf{t}}$, let $X \subseteq \{0,1\}^{|E|}$は、$v_{\mathsf{s}}$から$v_{\mathsf{t}}$へのすべてのパスの集合を表す。 各ラウンド $t$ において、パス $\mathbf{x}_t \in X$ を選択し、損失 $\langle \mathbf{x}_t, \mathbf{y}_t \rangle \in [-1,1]$ に対する帯域フィードバックを受け取る。 私たちのゴールは、後見の最良のパスに関して、T$ラウンド以上の後悔を最小限に抑えることです。 我々は、任意の適応的敵に対して高い確率で$\tilde O(\sqrt{|E|T\log |X|})$の最小限の後悔境界を達成できる最初の計算効率のアルゴリズムを提案し、$\tilde O(\cdot)$はエッジ数$|E|$の対数係数を隠蔽する。 提案アルゴリズムは,新規な損失推定器とセントロイド分解を非自明な方法で利用して,この後悔の限界を達成する。 アプリケーションとして、DAGのアルゴリズムは、$m$-sets、ワイドフォームゲーム、Coloner Blottoゲーム、有向グラフにおける最短ウォーク、ハイパーキューブ、マルチタスクのマルチアームバンディットに対して、最先端の効率的なアルゴリズムを提供し、これらすべての設定において高い確率的後悔保証を実現する。

関連論文リスト

• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  本稿では,非退化関数に対するバッチ帯域学習問題について検討する。 本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-09T12:50:16Z)
• A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity [28.068960555415014]
  非定常環境下での線形包帯の固定予算ベストアーム識別問題について検討する。 アルゴリズムは、可能な限り高い確率で最適な腕 $x* := argmax_xinmathcalXxtopsum_t=1Ttheta_t$ を正しく識別することを目的としている。
  論文  参考訳（メタデータ） (2023-07-27T19:03:36Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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