論文の概要: Online Learning with Feedback Graphs: The True Shape of Regret

• arxiv url: http://arxiv.org/abs/2306.02971v1
• Date: Mon, 5 Jun 2023 15:35:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-06 14:15:03.984805
• Title: Online Learning with Feedback Graphs: The True Shape of Regret
• Title（参考訳）: フィードバックグラフによるオンライン学習: 後悔の真の形
• Authors: Tom\'a\v{s} Koc\'ak and Alexandra Carpentier
• Abstract要約: ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
• 参考スコア（独自算出の注目度）: 82.00098840619847
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sequential learning with feedback graphs is a natural extension of the multi-armed bandit problem where the problem is equipped with an underlying graph structure that provides additional information - playing an action reveals the losses of all the neighbors of the action. This problem was introduced by \citet{mannor2011} and received considerable attention in recent years. It is generally stated in the literature that the minimax regret rate for this problem is of order $\sqrt{\alpha T}$, where $\alpha$ is the independence number of the graph, and $T$ is the time horizon. However, this is proven only when the number of rounds $T$ is larger than $\alpha^3$, which poses a significant restriction for the usability of this result in large graphs. In this paper, we define a new quantity $R^*$, called the \emph{problem complexity}, and prove that the minimax regret is proportional to $R^*$ for any graph and time horizon $T$. Introducing an intricate exploration strategy, we define the \mainAlgorithm algorithm that achieves the minimax optimal regret bound and becomes the first provably optimal algorithm for this setting, even if $T$ is smaller than $\alpha^3$.
• Abstract（参考訳）: フィードバックグラフを用いた逐次学習は、問題が追加情報を提供する基礎となるグラフ構造を備えているマルチアームバンディット問題の自然な拡張である。 この問題は \citet{mannor2011} によって導入され、近年かなりの注目を集めている。 文献では、この問題のミニマックス後悔率は階数$\sqrt{\alpha T}$であり、$\alpha$はグラフの独立数、$T$は時間地平線である。 しかし、これは$t$のラウンド数が$\alpha^3$よりも大きい場合にのみ証明される。 本稿では,新しい量 $r^*$ を定義する。これは \emph{problem complexity} と呼ばれ,任意のグラフと時間軸 $t$ に対して,minimax の後悔が $r^*$ に比例していることを証明する。 複雑な探索戦略を導入することで,$t$ が$\alpha^3$ よりも小さい場合でも,minimax の最適後悔条件を満たし,この設定で証明可能な最初の最適アルゴリズムとなる \mainalgorithm アルゴリズムを定義する。

関連論文リスト

• Linear Causal Bandits: Unknown Graph and Soft Interventions [18.412177974475526]
  因果バンディットのアルゴリズムを 設計するのは 2つの前提に依る その一般的な形式、すなわち未知グラフと未知の介入モデルにおける問題は、まだ未解決のままである。 本稿は、この問題に対処し、N$ノードを持つグラフにおいて、最大$d$と最大$L$の因果経路長を持つグラフにおいて、$T$相互作用が後悔の上限スケールをラウンド化することを示す。
  論文  参考訳（メタデータ） (2024-11-04T18:50:39Z)
• On Interpolating Experts and Multi-Armed Bandits [1.9497955504539408]
  我々は、$mathbfm$-MABに対して厳密なミニマックス後悔境界を証明し、その純粋な探索バージョンである$mathbfm$-BAIに対して最適なPACアルゴリズムを設計する。 その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
  論文  参考訳（メタデータ） (2023-07-14T10:38:30Z)
• On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
  強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。 改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
  論文  参考訳（メタデータ） (2023-05-24T17:40:57Z)
• Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs [34.37963000493442]
  本研究では,汎用的なフィードバックグラフを用いたオンライン学習について考察する。 両世界のベスト・オブ・ワールドズ・アルゴリズムは、敵の環境に対してほぼ厳密な後悔の限界を達成できる。
  論文  参考訳（メタデータ） (2022-06-02T05:01:40Z)
• A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs [21.563733343861713]
  フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。 本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T15:14:32Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• 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)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。 我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-13T16:35:30Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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